Figure 6: VLSI floorplan optimization on GC/PowerPlus
Figure 6 shows the results obtained with the
VLSI floorplan optimization algorithm. We used a
standard VLSI benchmark problem from [26]
with 25 building blocks
and six different implementations per block. This gives a search
space of 
nodes.
Compared to the 15-puzzle application, more communication is necessary in the floorplan optimization, because the solution speed depends much on the availability of efficient bound values. Each time a new bound is found by any of the worker tasks, it is broadcasted to all others.
The Parix implementation uses a torus topology for submitting work requests and for transferring work packets. Our PVM implementation, in contrast, makes use of the implicit clique topology. A master process hands out work packets to the slaves which search their assigned subtrees and broadcast newly found bound values.
As can be seen in Figure 6,
this simple farming approach yields sufficient performance results on
small systems with 
processors. Beyond, a hierarchy of
master processes should be implemented to eliminate potential
communication bottlenecks.