Макроконвейер (Bgtjktkufywyj)

Перейти к навигации Перейти к поиску

Макроконвейерраспределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу.[1] Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами.[1]:320 Последовательное применение принципа макроконвейера позволяет получить линейное ускорение в зависимости от числа процессоров, используемых для решения задачи.

Математическое описание

[править | править код]

Предположим, что нам требуется решить задачу вычисления функции . Время вычисления зависит от числа операций, которое в свою очередь, зависит от некоторого числового параметра или набора параметров , характеризующих исходные данные . Пусть время выражается зависимостью . Параметр можно выбрать так, что функция будет расти с ростом . Например, если — решение системы линейных алгебраических уравнений с матрицей коэффициентов и вектором свободных членов , которое вычисляется одним из прямых методов, то в качестве можно взять порядок системы. Если же система решается итерационным методом, то в качестве можно взять пару — порядок системы и число итераций.

Допустим, что распределить вычисление функции равномерно между процессорами возможно так, что каждый из процессоров будет работать время . В реальной системе стоит также учитывать накладные расходы связанные с обменом информации между процессорами. Представим время потраченое на накладные расходы как , оно включает в себя собственно время необходимое для передачи данных, время на синхронизацию. Время решения задачи на системе из процессоров обозначим как , тогда ускорение при решении задачи с параметром можно выразить формулой:

Формула имеет смысл только если , где — максимальное число процессоров, допускающее разумное разделение вычислительной работы при заданном размере задачи. Если , то при изменении от 1 до производительность растет не медленней, чем линейно с коэффициентом эффективности . Если же время, затрачиваемое на обмен, растет медленнее, чем время вычислений, то с ростом коэффициент эффективности приближается к 1. Приведенная формула не учитывает многие дополнительные факторы, но она позволяет вести поиск эффективных алгоритмов для решения задач на многопроцессорных распределенных системах.

Примечания

[править | править код]
  1. 1 2 Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5.

Литература

[править | править код]
  • Глушков В. М., Погребинский С. Б., Рабинович З. Л. О развитии структур многопроцессорных вычислительных машин, интерпретирующих языки высокого уровня. — Управляющие системы и машины. 1978 г. № 6 — с.61-66.
  • Глушков В. М. Об архитектуре высокопроизводительных машин. — Препринт Института Кибернетики № 78-65, Киев, 1978. — 41 с.
  • Михалевич В. С., Капитонова Ю. В., Летичевский А. А., Молчанов И. Н., Погребинский С. Б. Организация вычислений в многопроцессорных вычислительных системах. Кибернетика. 1984 г. № 3 — с. 1-10