next up previous
Next: N x N--Puzzle Up: Applications Previous: Applications

VLSI Floorplan Optimization

The floorplan area optimization [23,27] is a stage in the design of VLSI chips. Here the relative placements and areas of the building blocks of a chip are known, but their exact dimensions can still be varied over a wide range. A floorplan is represented by two dual polar graphs and , and a list of potential implementations for each block. As shown in Figure 1, the vertices in and represent the vertical and horizontal line segments of the floorplan. There exists an edge in the graph , if there is a block in the floorplan, whose left and right edges lie on the corresponding vertical line segments. For a specific configuration (i.e. a floorplan with exact block sizes), the edges are weighted with the dimensions of the blocks in this configuration. The solution of the floorplan optimization problem is a configuration with minimum layout area, given by the product of the longest paths in the graphs and .

Figure 1: A floorplan and the graphs and

Our implementation builds a tree where the leaves are complete configurations and the inner nodes at depth d represent partial floorplans consisting of blocks . The depth-first branch-and-bound (DFBB) solution algorithm employs a heuristic cost-function to eliminate unnecessary parts of the search space that are known not to contain an optimal solution. When a new (possibly non-optimal) solution has been found, the search continues with the improved cost-bound, now pruning all subtrees with cost-estimates higher than the new cost-bound. Newly established cost-bounds are broadcasted, so that all processors share the best available bound at any stage in the search.

Tue May 16 19:29:30 MET DST 1995