Русская Википедия:Макроконвейер
Макроконвейер — распределенная многопроцессорная система, обладающая программной и аппаратной поддержкой организации вычислений по макроконвейерному принципу.[1] Этот принцип был предложен в 1978 году советским математиком В. М. Глушковым. Его суть состоит в том, что при распределении вычислительных заданий между процессорами каждому процессору на очередном шаге вычислений дается такое задание, которое может загрузить его работой на определенное время, без взаимодействия с другими процессорами.Шаблон:R Последовательное применение принципа макроконвейера позволяет получить линейное ускорение в зависимости от числа процессоров, используемых для решения задачи.
Математическое описание
Предположим, что нам требуется решить задачу вычисления функции <math>y=f(x)</math>. Время вычисления зависит от числа операций, которое в свою очередь, зависит от некоторого числового параметра или набора параметров <math>n=(n_1, n_2, ...)</math>, характеризующих исходные данные <math>x</math>. Пусть время выражается зависимостью <math>t(n)</math>. Параметр <math>n</math> можно выбрать так, что функция <math>t(n)</math> будет расти с ростом <math>n</math>. Например, если <math>y=f(x)=f(x_1, x_2)</math> — решение системы линейных алгебраических уравнений с матрицей коэффициентов <math>x_1</math> и вектором свободных членов <math>x_2</math>, которое вычисляется одним из прямых методов, то в качестве <math>n</math> можно взять порядок системы. Если же система решается итерационным методом, то в качестве <math>n</math> можно взять пару — порядок системы и число итераций.
Допустим, что распределить вычисление функции <math>y=f(x)</math> равномерно между процессорами возможно так, что каждый из процессоров <math>p</math> будет работать время <math>t_p(n)=t(n)/p</math>. В реальной системе стоит также учитывать накладные расходы связанные с обменом информации между процессорами. Представим время потраченое на накладные расходы как <math>w_p(n)</math>, оно включает в себя собственно время необходимое для передачи данных, время на синхронизацию. Время решения задачи на системе из <math>p</math> процессоров обозначим как <math>T_p(n)</math>, тогда ускорение <math>a_p=a_p(n)</math> при решении задачи с параметром <math>n</math> можно выразить формулой:
- <math>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.</math>
Формула имеет смысл только если <math>p<k(n)</math>, где <math>k(n)</math> — максимальное число процессоров, допускающее разумное разделение вычислительной работы при заданном размере задачи. Если <math>w_p(n)/t_p(n)<1</math>, то при изменении <math>p</math> от 1 до <math>k(n)</math> производительность растет не медленней, чем линейно с коэффициентом эффективности <math>b_p(n)>1/2</math>. Если же время, затрачиваемое на обмен, растет медленнее, чем время вычислений, то с ростом <math>n</math> коэффициент эффективности приближается к 1. Приведенная формула не учитывает многие дополнительные факторы, но она позволяет вести поиск эффективных алгоритмов для решения задач на многопроцессорных распределенных системах.
Примечания
Литература
- Глушков В. М., Погребинский С. Б., Рабинович З. Л. О развитии структур многопроцессорных вычислительных машин, интерпретирующих языки высокого уровня. — Управляющие системы и машины. 1978 г. № 6 — с.61-66.
- Глушков В. М. Об архитектуре высокопроизводительных машин. — Препринт Института Кибернетики № 78-65, Киев, 1978. — 41 с.
- Михалевич В. С., Капитонова Ю. В., Летичевский А. А., Молчанов И. Н., Погребинский С. Б. Организация вычислений в многопроцессорных вычислительных системах. Кибернетика. 1984 г. № 3 — с. 1-10
См. также
