ПВМ ОКМ ДМ экономическая информатика 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 Теория и практика обработки информации

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

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

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