Simultaneous Floor Planning and Global Routing for Hierarchical Building-Block Layout

A new methodology for hierarchical floor planning and global routing for building block layout is presented. Unlike the traditional approach, which separates placement and global routing into two consecutive stages, our approach accomplishes both jobs simultaneously in a hierarchical fashion. The global routing problem is formulated at each level as a series of the minimum Steiner tree problem in a special class of partial 3-trees, which can be solved optimally in linear time. The floor planner with a maximum of five rooms per level has been implemented in the C language, running on a VAX 8650 under 4.3 BSD UNIX. The experimental results on examples with a large number of irregular blocks show that our approach out-performs other well-known deterministic algorithms, and gives results that are comparable to random-based algorithms but with a computing time an order of magnitude less. Due to the unique goal-oriented and pattern-directed features of our floor planner, it accepts specifications for overall aspect ratio and I/O pad positions, thus making our approach suitable for hierarchical design.