Tree Computations

As mentioned earlier, tree computations   typically exhibit a tree-like process control structure which also conforms to the communication pattern in many instances. To illustrate this model, we consider a parallel sorting algorithm that works as follows. One process (the manually started process in PVM) possesses (inputs or generates) the list to be sorted. It then spawns a second process and sends it half the list. At this point, there are two processes each of which spawns a process and sends them one-half of their already halved lists. This continues until a tree of appropriate depth is constructed. Each process then independently sorts its portion of the list, and a merge phase follows where sorted sublists are transmitted upwards along the tree edges, with intermediate merges being done at each node. This algorithm is illustrative of a tree computation in which the workload is known in advance; a diagram depicting the process is given in Figure ; an algorithmic outline is given below.

  
Figure: Tree-computation example

{ Spawn and partition list based on a broadcast tree pattern. }
for i := 1 to N, such that 2^N = NumProcs
	forall processors P such that P < 2^i
		pvm_spawn(...) {process id 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)    {receive the list}
		endif
	endfor
endfor

{ Sort remaining list. }
Quicksort(list[midpt+1..MAXSIZE])

{ Gather/merge sorted sub-lists. }
for i := N downto 1, such that 2^N = NumProcs
	forall processors P such that 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)    {receive temp list}
			merge templist into list
		endif
	endfor
endfor