High level physical design of very large scale integrated circuits

Abstract

This dissertation explores various problems in high level physical design, in particular, floorplanning and placement problems. In floorplanning, we focus our attention to a new concept known as the dual graph approach. The method is based on transforming a structural circuit description to a dual graph which describes the adjacency relations of the floorplan cells. The floorplanning problem for general non-rectangular shaped cells is examined. Theoretical results related to this method are presented. The results demonstrate that the dual floorplanning approach is robust, without resorting to general rectilinear shaped cells. The dual graph technique is also adapted to the class of sliceable floorplans, which has important practical application. The sliceable floorplanning algorithm serves as the basis for enumerating floorplans satisfying the dual connectivity requirements. An integrated algorithm is implemented for area optimal floorplan sizing and enumeration. Experimental results using standard benchmark circuits show superior solution quality and computation efficiency. Some difficulties involving complex triangle elimination problems of dual graphs are discussed. For an important class of dual graphs, an algorithm for optimal solution is presented. Traditionally, many placement algorithms have not been able to exploit the enormous amount of structural regularity observed in digital VLSI circuits. A placement algorithm exploiting such structures is proposed, implemented and tested. Again, experimental observation with the benchmark circuits suggests that this technique produces placement with net-terminal characteristics appropriate for high performance circuits.