Лекции по параллельным вычислениям. Гергель В.П - 150 стр.

UptoLike

Составители:

Рубрика:

150

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

В качестве подзадач могут быть взяты строки матрицы A, каждая из кото-

рых при этом закрепляется за одним процессором. Если число строк матрицы

больше, чем число доступных процессоров (s<n), подзадачи можно укрупнить,

объединив несколько строк матрицы. Если при этом используется последова-

тельная схема разделения данных, при которой в одной подзадаче оказываются

соседние строки матрицы, по мере исключения (в прямом ходе) или определе-

ния (в обратном ходе) неизвестных, все большая часть процессоров, для кото-

рой вычисления завершены, окажется простаивающей.

Для достижения хорошей балансировки процессоров целесообразно при-

менить ленточную циклическую схему распределения данных между укрупнен-

ными подзадачами. Матрица A делится на полосы таким образом, чтобы в каж-

дой полосе содержались как строки, обработка которых завершается раньше,

так и обрабатываемые в последнюю очередь (см. рис. 11.2).

Рис. 11.2. Пример использования ленточной циклической схемы

разделения строк матрицы между тремя процессорами

Распределение подзадач между процессорами должно также учитывать ха-

рактер обмена данными между подзадачами. В рассматриваемом методе Гаусса

взаимодействие подзадач заключается в передаче данных от одного процессора

всем процессорам вычислительной системы. Поэтому в данном случае целесо-

образна топология сети передачи данных в виде гиперкуба или полного графа.