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

Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу.^[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. Приведенная формула не учитывает многие дополнительные факторы, но она позволяет вести поиск эффективных алгоритмов для решения задач на многопроцессорных распределенных системах.

Примечания править

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

Литература править

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

См. также править

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

[1]