Nonrectangular Shaping and Sizing of Soft Modules for Floorplan-Design Improvement.

Many previous works on floorplanning with non rectangular modules [1]-[12] assume that the modules are predesignated to have particular non rectangular shapes, e.g., L-shaped, T-shaped, etc. However, this is not common in practice because rectangular shapes are more preferable in many designing steps. Those non rectangular shapes are actually generated during floor planning in order to further optimize the solution. In this paper, we study this problem of changing the shapes and dimensions of the flexible modules to fill up the unused area of a preliminary floor plan, while keeping the relative positions between the modules unchanged. This feature will also be useful in fixing small incremental changes during engineering change order modifications. We formulate the problem as a mathematical program. The formulation is such that the dimensions of all of the rectangular and, nonrectangular modules can be computed by closed-form equations in O(m) time in each corresponding Lagrangian relaxation sub problem (LRS) where m is the total number of edges in the constraint graphs. As a result, the total time for the whole shaping and sizing process is O(k × m), where k is the number of iterations on the LRS. Experimental results show that the amount of area reused is 3.7% on average, while the total wirelength can be reduced by 0.43% on average because of the more compacted result packing. [ABSTRACT FROM AUTHOR]