Linear time algorithms for floor-planning and routing problems

Abstract

The designer of an integrated circuit (IC) transforms a circuit description to a geometric description, called the VLSI layout. The task of converting the specification of an electrical circuit into a layout is called the physical design. In physical design cycle a circuit specification is converted into a VLSI layout in the four phases: partitioning, floorplanning, routing (global routing and detailed routing) and compaction. A large circuit is divided into a set of smaller blocks and the interconnections (nets) between them in the partitioning phase. Each block is then placed (floorplanning phase) in a plane so that interconnections can be routed (routing phase) through the remaining space. Most of the works that appear in the literature deal floorplanning and global routing in two different phases. Although there are some linear time floorplanning algorithms, but the known best algorithms for global routing and detailed routing run in O(N2) time, where N is the number of given nets. In this thesis, we present an integrated algorithm based on orthogonal drawing of plane graph that handle floorplanning and global routing in a single phase. The time complexity of our algorithm is linear. We also develop a linear time detailed routing algorithm.