FLOORPLANNING BY ANNEALING ON A HYPERCUBE MULTIPROCESSOR.

The design, parallel implementation, and performance evaluation of annealing-based floorplanning algorithms on a hypercube multiprocessor are described. Partitioning strategies are developed to map an annealing algorithm onto a hypercube topology efficiently. Because the state of the evolving floorplan configuration is distributed across the processors of the hypercube, updating the views of this global system state seen by individual processors requires expensive interprocessor message traffic. Hence, errors are tolerated in these locally held views of the system state to reduce the frequency of expensive global updates. Novel parallel state-updating schemes are introduced that permit fast partial updates to be interleaved with expensive, complete updates. Results from experiments on an Intel iPSC hypercube show relative speedups of between 4 and 7. 5 times for 16 processors, with solutions of comparable quality to those produced by a serial version of the floorplanner.