"Древовидные" вычисления. Параллельная виртуальная машина, 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

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