Information Technology Reference
In-Depth Information
Kapees: A New Tool for Standard Cell
Placement
Sameer Pawanekar
1
,
, Kalpesh Kapoor
2
, and Gaurav Trivedi
1
1
Department of Electronics and Electrical Engineering
Indian Institute of Technology Guwahati, India
{
p.sameer,trivedi,kalpesh
}
@iitg.ernet.in
2
Department of Mathematics
Indian Institute of Technology Guwahati, India
Abstract.
We consider the well-known problem of ecient cell place-
ment on a fixed die. We investigate minimization of half perimeter that
is required for a design that in turn results into minimal routed wire
length and thus wire delay. We describe a new method,
Kapees
,forlarge
scale standard cell placement. Our technique is based on recursive par-
titioning of placement circuit which is modeled as a hypergraph. It uses
partitioning during the global placement phase and a greedy approach
is followed to reduce the wire length during detailed placement phase.
Our results show a significant improvement in comparison to Cadence
Encounter's Amoeba and Capo tools by 9% and 5%, respectively.
1 Introduction
Standard Cell Placement is a well studied problem over several years. The objec-
tive of standard cell placement is to find coordinates of all the standard cells in
a netlist in such a way that the wire length connecting them is minimum. The
wire length is modeled as Half Perimeter wire length (HPWL) which can be de-
fined as sum of all the perimeters of the smallest bounding box enclosing each net
of the design. There are four broad approaches to solve this problem: 1. Min-cut
[1-3], 2. Simulated annealing [4], 3. Analytic [5], and 4. Force directed [6]. Al-
though both academic and commercial tools for placement are available, there is a
scope for improvement because of inherent complexity of the problem [7]. This is
also apparent from the ISPD placement contests held in the recent past in which
none of the placers dominated across the entire benchmark set. A comparative
study has also shown that the current state of the art is far from optimal [8].
Our approach to solve this problem is based on partition driven placement. Net
cut objective follows wire length objective at initial hierarchical levels. At later
hierarchical levels, net cut objective no longer follows wire length objective. This
is when the number of cells are less than say 10. After this step detail placement
(DP) follows. The existing placers such as Capo [1], Dragon [2] and feng shui [3]
use different approaches during detailed placement.
Sameer Pawanekar is currently a senior engineer with SiConTech, Bangalore. He is
enrolled as a part-time Ph.D. student at IIT Guwahati.
