WikiSort.ru - Не сортированное

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

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

Предположим, что нам требуется решить задачу вычисления функции ${\displaystyle y=f(x)}$ . Время вычисления зависит от числа операций, которое в свою очередь, зависит от некоторого числового параметра или набора параметров ${\displaystyle n=(n_{1},n_{2},...)}$ , характеризующих исходные данные ${\displaystyle x}$ . Пусть время выражается зависимостью ${\displaystyle t(n)}$ . Параметр ${\displaystyle n}$ можно выбрать так, что функция ${\displaystyle t(n)}$ будет расти с ростом ${\displaystyle n}$ . Например, если ${\displaystyle y=f(x)=f(x_{1},x_{2})}$ — решение системы линейных алгебраических уравнений с матрицей коэффициентов ${\displaystyle x_{1}}$ и вектором свободных членов ${\displaystyle x_{2}}$ , которое вычисляется одним из прямых методов, то в качестве ${\displaystyle n}$ можно взять порядок системы. Если же система решается итерационным методом, то в качестве ${\displaystyle n}$ можно взять пару — порядок системы и число итераций.

Допустим, что распределить вычисление функции ${\displaystyle y=f(x)}$ равномерно между процессорами возможно так, что каждый из процессоров ${\displaystyle p}$ будет работать время ${\displaystyle t_{p}(n)=t(n)/p}$ . В реальной системе стоит также учитывать накладные расходы связанные с обменом информации между процессорами. Представим время потраченое на накладные расходы как ${\displaystyle w_{p}(n)}$ , оно включает в себя собственно время необходимое для передачи данных, время на синхронизацию. Время решения задачи на системе из ${\displaystyle p}$ процессоров обозначим как ${\displaystyle T_{p}(n)}$ , тогда ускорение ${\displaystyle a_{p}=a_{p}(n)}$ при решении задачи с параметром ${\displaystyle n}$ можно выразить формулой:

${\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.}$

Формула имеет смысл только если ${\displaystyle p<k(n)}$ , где ${\displaystyle k(n)}$ — максимальное число процессоров, допускающее разумное разделение вычислительной работы при заданном размере задачи. Если ${\displaystyle w_{p}(n)/t_{p}(n)<1}$ , то при изменении ${\displaystyle p}$ от 1 до ${\displaystyle k(n)}$ производительность растет не медленней, чем линейно с коэффициентом эффективности ${\displaystyle b_{p}(n)>1/2}$ . Если же время, затрачиваемое на обмен, растет медленнее, чем время вычислений, то с ростом ${\displaystyle n}$ коэффициент эффективности приближается к 1. Приведенная формула не учитывает многие дополнительные факторы, но она позволяет вести поиск эффективных алгоритмов для решения задач на многопроцессорных распределенных системах.

Примечания

Литература

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

См. также

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