Теория и практика параллельных вычислений



Масштабирование и распределение подзадач по процессорам


Размер блоков матрицы А может быть подобран таким образом, чтобы общее количество базовых подзадач совпадало с числом процессоров p. Так, например, если определить размер блочной решетки как p=s·q, то

k=m/s, l=n/q,

где k и l есть количество строк и столбцов в блоках матрицы А. Такой способ определения размера блоков приводит к тому, что объем вычислений в каждой подзадаче является равным, и, тем самым, достигается полная балансировка вычислительной нагрузки между процессорами.

Возможность выбора остается при определении размеров блочной структуры матрицы А. Большое количество блоков по горизонтали приводит к возрастанию числа итераций в операции редукции результатов блочного умножения, а увеличение размера блочной решетки по вертикали повышает объем передаваемых данных между процессорами. Простое, часто применяемое решение состоит в использовании одинакового количества блоков по вертикали и горизонтали, т.е.

Следует отметить, что блочная схема разделения данных является обобщением всех рассмотренных в данной лекции подходов. Действительно, при q=1 блоки сводятся к горизонтальным полосам матрицы А, при s=1 исходные данные разбиваются на вертикальные полосы.

При решении вопроса распределения подзадач между процессорами должна учитываться возможность эффективного выполнения операции редукции. Возможный вариант подходящего способа распределения состоит в выделении для подзадач одной и той же горизонтальной полосы блоков множества процессоров, структура сети передачи данных между которыми имеет вид гиперкуба или полного графа.




Содержание  Назад  Вперед