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