next up previous
Next: Conclusions Up: Performance Comparison Previous: Communication Speed of

Results on the VLSI Floorplan Optimization Problem

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.

Tue May 16 19:29:30 MET DST 1995