| |
Как уже было упомянуто, древовидная структура вычислений для контроля процессов также во многих случаях соответствует коммуникационным шаблонам. Для иллюстрирования этой модели рассматривается алгоритм параллельной сортировки, который заключается в следующем. Один процесс (вручную запущенный в PVM) обладает (вводит или генерирует) список для сортировки. Он порождает второй процесс и передает ему половину списка. На этом этапе существуют уже два процесса, каждый из которых также порождает свой процесс и передает ему одну половину от уже разделенного списка. Процесс передачи продолжается до тех пор, пока не построено дерево соответствующей разветвленности. При этом каждый процесс независимо сортирует свою порцию списка, а фаза слияния наступает, когда отсортированные подсписки передаются в обратном направлении по ветвям дерева с промежуточными слияниями, делаемыми на каждой из станций. Этот алгоритм является показательным алгоритмом с заранее известной загрузкой; диаграмма с изображением процесса дана на рис. 13; алгоритмическая схема дается ниже.
широковещательной передачи шаблона дерева}
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
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
endfor
Закладки на сайте Проследить за страницей |
Created 1996-2024 by Maxim Chirkov Добавить, Поддержать, Вебмастеру |