``Беспорядочные'' вычисления

Каталог документации / Раздел "Программирование в Linux" / Оглавление документа

Next: ``Древовидные'' вычисления Up: Общие парадигмы параллельного программирования Previous: Общие парадигмы параллельного программирования Contents

``Беспорядочные'' вычисления

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

Модель ``ведущий-ведомый'' иллюстрируется ниже с использованием хорошо известной последовательности вычислений Манделброта, которая является представительницей класса задач под названием ``смущающий'' параллелизм. Само вычисление сводится к применению рекурсивной функции к группе вершин на некоторой комплексной плоскости до тех пор, пока значения функции не достигнут определенных величин либо начнут отклоняться. В зависимости от этого условия строится графическое представление каждой вершины на плоскости. По существу, так как результат работы функции зависит только от начального значения вершины (и не зависит от других вершин), задача может быть разделена на полностью независимые порции, алгоритм может быть применен к каждой порции, а частичные результаты комбинируются с помощью простых комбинационных схем. Однако эта модель допускает балансировку динамической нагрузки, тем самым позволяя обрабатывающим элементам разделять нагрузку неравномерно. В текущем и последующих примерах в пределах этого раздела показаны только скелеты алгоритмов и, кроме того, допускаются некоторые синтаксические вольности в подпрограммах PVM - в интересах облегчения понимания. Управляющая структура класса приложений ``ведущий-ведомый'' показана на рис 11.

$\includegraphics[scale=0.6]{pic41.eps}$

Рис. 11. Структура приложения для алгоритма Манделброта

{Алгоритм Манделброта для ведущего}

{Начальное размещение}

for i := 0 to NumWorkers - 1

pvm_spawn(<worker name>} {Запуск рабочего i}

pvm_send(<worker tid>,999) {Передача задачи рабочему i}

endfor

{Прием-передача}

while (WorkToDo)

pvm_recv(888) {Прием результата}

pvm_send(<available worker tid>,999)

{Передача следующей задачи доступному рабочему}

display result

endwhile

{Сбор оставшихся результатов}

for i := 0 to NumWorkers - 1

pvm_recv(888) {Прием результата}

pvm_kill(<worker tid i>) {Завершение рабочего i}

display result

endfor

{Алгоритм Манделброта для рабочего}

while (true)

pvm_recv(999) {Прием задачи}

{Вычисление результата}

result := MandelbrotCalculations(task)

{Передача результата ведущему}

pvm_send(<master tid>,888)

endwhile

Пример ``ведущий-ведомый'', описанный выше, не предполагает коммуникаций между ведомыми. Большинство беспорядочных вычислений любой сложности требуют взаимодействия между вычислительными процессами; структура таких приложений проиллюстрирована на примере использования ``только станции'' для матричного умножения по алгоритму Каннона (подробности программирования похожих алгоритмов даются в другом разделе). Пример ``умножения матриц'' графически показан на рис. 12 (локально умножаются подматрицы матриц и используется широковещательная построчная передача строк подматриц A в связке с постолбцовыми сдвигами подматриц матрицы B):

$\includegraphics[scale=0.57]{pic42.eps}$