April 06, 2012

Algorithm that is 10 to 100 times faster than state of the art for determining the optimal circuit block shape in VLSI fixed-outline floor-planning

The best paper award for the IEEE International Symposium on Physical Design 2012 was given to Professor Chirs Chu at Iowa State University, who proposed an algorithm for determining the optimal circuit block shape in VLSI fixed-outline floor-planning, achieving a 10-to-100 increase over previous state-of-the-art techniques.

Specifically formulated for fixed-outline floorplanning
* Optimal, efficient and scalable for non-slicing floorplan

* Main contributions
- Basic Slack-Driven Shaping
- Three Optimality Conditions
- Slack-Driven Shaping (SDS)

* Promising Experimental Results
- Obtain optimal solutions for both MCNC & HB benchmarks simply by the basic SDS.
- For MCNC benchmarks, 253x faster than Young’s, 33x faster than Lin’s, to produce results of similar quality.

Future Work
* Embed SDS (Slack-Driven Block Shaping)into a floorplanner.
* Use the duality gap as a better stopping criterion.
* Propose a more scalable algorithm to replace the geometric programming method.
* Extend SDS (Slack-Driven Block Shaping) to handle non-fixed outline floorplanning.
* Applied on buffer/wire sizing for timing optimization

Optimal Slack-Driven Block Shaping Algorithm in Fixed-Outline Floorplanning (31 pages)

This paper presents an efficient, scalable and optimal slack-driven shaping algorithm for soft blocks in non-slicing floorplan. The proposed algorithm is called SDS. Different from all previous approaches, SDS is specifically formulated for fixed-outline floorplanning. Given a fixed upper bound on the layout width, SDS minimizes the layout height by only shaping the soft blocks in the design. Iteratively, SDS shapes some soft blocks to minimize the layout height, with the guarantee that the layout width would not exceed the given upper bound. Rather than using some simple heuristic as in previous work, the amount of change on each block is determined by systematically distributing the global total amount of available slack to individual block. During the whole shaping process, the layout height is monotonically reducing, and eventually converges to an optimal solution. We also propose two optimality conditions to check the optimality of a shaping solution. To validate the efficiency and effectiveness of SDS, comprehensive experiments are conducted on MCNC and HB benchmarks. Compared with previous work, SDS is able to achieve the best experimental result with significantly faster runtime.