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

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

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

Как упомянуто выше, дерево вычислений обычно представляет собой древовидную структуру для контроля процессов, которая также во многих случаях удовлетворяет коммуникационные шаблоны. Для иллюстрирования этой модели рассматривается алгоритм параллельной сортировки, который заключается в следующем. Один процесс (процесс, вручную запущенный в ПВМ) обладает (вводит или генерирует) список для сортировки. После этого он порождает второй процесс и передает ему половину списка. На этом этапе, существуют уже два процесса, каждый из которых также порождает процесс и передает ему одну половину от уже разделенного списка. Этот процесс продолжается до тех пор, пока не построено дерево соответствующей глубины. При этом каждый процесс независимо сортирует свою порцию списка, а фаза слияния наступает, когда отсортированные подсписки передаются в обратном направлении по ветвям дерева с промежуточными слияниями, делаемыми на каждой из станций. Этот алгоритм является показательным алгоритмом с заранее известной загрузкой; диаграмма с изображением процесса дана на рис. 86; алгоритмическая схема дается ниже.

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

Рис. 86. Пример древовидного вычисления

{Порождение и разделение списка на базе широковещательной передачи

шаблона дерева}

for i := 1 to N, причем 2^N = NumProcs

forall processors P, причем P < 2^i

pvm_spawn(...) {идентификатор процесса P XOR 2^i}

if P < 2^(i-1) then

midpt := PartitionList(list);

{Send list[0..midpt] to P XOR 2^i}

pvm_send((P XOR 2^I,999)

list := list[midpt+1..MAXSIZE]

else

pvm_recv(999) {Прием списка}

endif

endfor

{Сортировка оставшегося списка}

Quicksort(list[midpt+1..MAXSIZE])

{Сбор/слияние отсортированных подсписков}

for i := N downto 1, причем 2^N = NumProcs

forall processors P, причем P < 2^i

if P >2^(i-1) then

pvm_send((P XOR 2^i),888)

{Send list to P XOR 2^i}

else

pvm_recv(888) {Прием временного списка}

merge templist into list

endif

endfor

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

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

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

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