Макроконвейер

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

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

Предположим, что нам требуется решить задачу вычисления функции $y=f(x)$. Время вычисления зависит от числа операций, которое в свою очередь, зависит от некоторого числового параметра или набора параметров $n=(n_1, n_2, ...)$, характеризующих исходные данные $x$. Пусть время выражается зависимостью $t(n)$. Параметр $n$ можно выбрать так, что функция $t(n)$ будет расти с ростом $n$. Например, если $y=f(x)=f(x_1, x_2)$ — решение системы линейных алгебраических уравнений с матрицей коэффициентов $x_1$ и вектором свободных членов $x_2$, которое вычисляется одним из прямых методов, то в качестве $n$ можно взять порядок системы. Если же система решается итерационным методом, то в качестве $n$ можно взять пару — порядок системы и число итераций.

Допустим, что распределить вычисление функции $y=f(x)$ равномерно между процессорами возможно так, что каждый из процессоров $p$ будет работать время $t_p(n)=t(n)/p$. В реальной системе стоит также учитывать накладные расходы связанные с обменом информации между процессорами. Представим время потраченое на накладные расходы как $w_p(n)$, оно включает в себя собственно время необходимое для передачи данных, время на синхронизацию. Время решения задачи на системе из $p$ процессоров обозначим как $T_p(n)$, тогда ускорение $a_p=a_p(n)$ при решении задачи с параметром $n$ можно выразить формулой:

$a_p(n)=\frac{T_1(n)}{T_n(n)}=\frac{t(n)}{t_p(n)+w_p(n)}=\frac{1}{1+\tfrac{w_p(n)}{t_p(n)}}p=b_p(n) \cdot p.$

Формула имеет смысл только если $p<k(n)$, где $k(n)$ — максимальное число процессоров, допускающее разумное разделение вычислительной работы при заданном размере задачи. Если $w_p(n)/t_p(n)<1$, то при изменении $p$ от 1 до $k(n)$ производительность растет не медленней, чем линейно с коэффициентом эффективности $b_p(n)>1/2$. Если же время, затрачиваемое на обмен, растет медленнее, чем время вычислений, то с ростом $n$ коэффициент эффективности приближается к 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

См. также

• ЕС-2701
• Вычислительный конвейер
• Институт кибернетики им. В. М. Глушкова