Страница: 1/3
1. Умножение матриц. (гипотетический пример)
A * B =: C
Где А (m*s), B (s*n), C(m*n)
Алгоритм:
For i := 1 to s do
<Умножить вектор-строку на матрицу – A[i]*B = C[i]>
Граф зависимостей по данным (Data Flow Graph)
 |
A[1] C[1]
 |
A[2] C[2]
 | |||
 |
A, B C
 |  | ||||||||
 | |||||||||
 | |||||||||
 | |||||||||
A[k] C[k]
Д – диспетчер. Коммутирует каналы связи и распределяет строки A[i] по процессорам.
П – приёмник (вполне может быть тем же диспетчером), формирует матрицу С из полученных строк.
K – число процессоров минус 2 (или 1), которые выполняют умножение строки на матрицу.
1) Если k ³ m. Тогда каждый процессор один раз выполняет перемножение A[i]*B и передаёт результат процессору “П” . Далее процесс “П” формирует матрицу С и выдаёт результат пользователю.
2) Если k < m, то вначале просчитываются первые k строк.
Когда вычисления закончится на одной из k процессоров, то ей передаётся следующая строка – т.е. A[k+1].
И так далее, в освободившиеся процессоры передаются строки
A[k + i], i = 1 … m-k.
Достоинства данной схемы.
1) Однократеая загрузка матрицы B в процессоры-вычислители, и дальнейшая загрузка только векторов-строк A[i] (минимизация потока данных).
2) Автоматически учитывается производительность процессоров. Если процессор работает быстро, то он загружается дополнительно (случай при k < m).
2. Цели оптимизации параллельных вычислений.
1) Минимизация потока данных в DFG.
2) Учёт производительности процессоров. Включая случай зависимости её от времени (динамика).
3) Учёт скорости обмена по каналам связи между процессорами. Включая случай зависимости её от времени (динамика).
4) Коррекция DFG в реальном времени (пояняется на следующем примере итерационных методов).
далее на следующей странице…
3. Итерационные алгоритмы.
Общий случай графа потоков данных.
Реферат опубликован: 7/01/2009