Стр. 48 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
46
p1 p2 p3 p4 p5 p6 p7 p1 p2 p3 p4 p5 p6 p7
p8 p9 p 10 p11 p12 p13 p 14 p8 p9 p10 p11 p12 p 13 p 14
Рис. 5.4. Блочная схема распределения матриц по процессорам
Ленточная схема
Для матрицы A используется горизонтальное разбиение, для матрицы
B – вертикальное разбиение.
Возможные способы распределения данных (частей матриц) по процессорам.
Размер полосы (количество строк или столбцов) p n / .
На процессор для вычислений передается по одной полосе матриц A и B ; при
распределении данных каждая полоса матрицы A должна пересечься с каждой поло-
сой матрицы B – всего p вариантов.
Каждый процессор вычисляет блок результирующей матрицы C размером
p np n / / × . Здесь и далее n – размер матрицы; p – количество процессоров.
Блочная схема
Размер блоков - p np n / / × .
На процессор для вычислений передается по одному блоку матриц A и B; при
распределении данных блоки матрицы A встречаются однократно.
В ходе вычислений блоки матриц передаются между процессорами
(всего p итераций); схема коммуникационного взаимодействия соответствует
топологии типа двумерной прямоугольной решетки-тора.
Рассмотрим алгоритм Фокса, который использует блочную схему перемноже-
ния матриц. Пусть p=k2 , n=mk и процессоры образуют логическую прямоугольную
решетку размером k×k (обозначим через pij процессор, располагаемый на пересече-
нии i строки и j столбца решетки). Основные правила метода, известного как
алгоритм Фокса, состоят в следующем:
• каждый из процессоров решетки отвечает за вычисление одного блока
матрицы C;
• в ходе вычислений на каждом из процессоров pij располагается четыре
матричных блока:
o блок Cij матрицы C, вычисляемый процессором;