Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

In this presentation, a VLSI floorplanning problem for a given layout with L-shaped soft modules is discussed. The area of each rectangular or L-shaped building block is assumed to be fixed. By dividing an L-shaped cell into two rectangular cells, the specification of an L-shaped problem can be described in terms of its corresponding layout problem with only rectangular blocks. In such a description, the width and the height of each rectangular block are allowed to vary subject to aspect ratio constraints. Also, a rectangular block may be arbitrarily oriented in parallel to the horizontal and vertical axes, subject to partition constraints with associated adjacency relationships. The objective is to minimize the rectangular area of the entire layout. Such a global optimization problem is considered very difficult to solve. We will try to obtain an approximated global optimal solution by using solvable mixed integer linear programming (MILP). The problem is first transformed into an almost linear programming problem. Its nonlinear portion is then approximated by piecewise linear functions. Thus, the overall problem becomes a solvable MILP problem. Numerical examples are used to illustrate some features of such an approach.