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