ПВМ ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

Параллельная виртуальная машина, PVM

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

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

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

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

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

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

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

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

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

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

Рис. 85. Общие беспорядочные вычисления

{Матричное умножение с использованием алгоритма

"сдвинуть-умножить-повернуть"}

{Процессор 0 запускает другие процессы}

if (<my processor number>) = 0) then

for i := 1 to MeshDimension*MeshDimension

pvm_spawn(<component name>, ...)

endfor

endif

forall processors Pij, 0 <= i,j < MeshDimension

for k := 0 to MeshDimension-1

{Сдвиг}

if myrow = (mycolumn+k) mod MeshDimension

{Передача A во все Pxy, x = myrow, y <> mycolumn}

pvm_mcast((Pxy, x = myrow, y <> mycolumn,999)

else

pvm_recv(999) {Прием A}

endif

{Умножение. Обработка всего, содержащегося в C}

Multiply(A,B,C)

{Вращение}

{Передача B в Pxy, x = myrow-1, y = mycolumn}

pvm_send((Pxy, x = myrow-1, y = mycolumn),888)

pvm_recv(888) {Прием B}

endfor

ПВМ ОКМ ДМ экономическая информатика 4GL Теория и практика обработки информации

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

НОВОСТИ ФОРУМА

Рыцари теории эфира