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.
