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

Как уже было упомянуто, древовидная структура вычислений для контроля процессов также во многих случаях соответствует коммуникационным шаблонам. Для иллюстрирования этой модели рассматривается алгоритм параллельной сортировки, который заключается в следующем. Один процесс (вручную запущенный в 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