| Title | Fast Analytic Placement using Minimum Cost Flow |
| Author | *Ameya R Agnihotri, Patrick H Madden (SUNY Binghamton, United States) |
| Page | pp. 128 - 134 |
| Keyword | Placement, Physical Design, Analytic placement |
| Abstract | Many current integrated circuits designs, such as those released
for the ISPD2005 placement contest, are extremely large
and can contain a great deal of white space.
These new placement problems
are challenging; analytic placers perform well, but can
suffer from high run times.
In this paper, we present a new placement tool called Vaastu.
Our approach combines continuous and discrete optimization techniques.
We utilize network flows, which incorporate
the more realistic half-perimeter wire length objective, to
facilitate module spreading in conjunction with
a log-sum-exponential function based analytic approach.
Our approach obtains wire length results that are competitive with the
best known results, but with much lower run times. |
| PDF file |
| Title | FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Placement Congestion Control |
| Author | *Natarajan Viswanathan, Min Pan, Chris Chu (Iowa State University, United States) |
| Page | pp. 135 - 140 |
| Keyword | Quadratic Placement, Iterative Local Refinement, Multilevel Placement |
| Abstract | In this paper, we present FastPlace 3.0 - an efficient and scalable multilevel quadratic placement algorithm for large-scale mixed-size designs. The main contributions of our work are:
(1) A multilevel global placement framework, by incorporating a two-level clustering scheme within the flat analytical placer FastPlace.
(2) An efficient and improved Iterative Local Refinement technique that can handle placement blockages and placement congestion constraints.
(3) A congestion aware standard-cell legalization technique in the presence of blockages.
On the ISPD-2005 placement benchmarks, our algorithm is 5.12X, 11.52X and 16.92X faster than mPL6, Capo10.2 and APlace2.0 respectively. In terms of wirelength, we are on average, 2% higher as compared to mPL6 and 9% and 3% better as compared to Capo10.2 and APlace2.0 respectively. We also achieve competitive results compared to a number of academic placers on the placement congestion constrained ISPD-2006 placement benchmarks. |
| PDF file |
| Title | Hippocrates: First-Do-No-Harm Detailed Placement |
| Author | Haoxing Ren (IBM, United States), *David Pan (University of Texas at Austin, United States), Charles J Alpert, Gi-Joon Nam, Paul Villarrubia (IBM, United States) |
| Page | pp. 141 - 146 |
| Keyword | placement, timing, detailed placement |
| Abstract | Physical synthesis optimizations and engineering change orders
typically change the locations of cells, resize cells or add more
cells to the design after global placement. Unfortunately, those
changes usually lead to wirelength increases; thus another pass of
optimizations to further improve wirelength, timing and routing
congestion characteristics is required. Simple wirelength-driven
detailed placement techniques could be useful in this scenario.
While such techniques can help to reduce wirelength, ones without
careful timing constraint considerations might degrade the timing
characteristics (worst negative slack, total negative slack, etc)
and/or introduce more electrical violations (exceeding maximum
output load constraints and maximum input slew constraints). In this
paper, we propose a new detailed placement paradigm, which use a set
of pin-based timing and electrical constraints in detailed placement
to prevent it from degrading timing or violating electrical
constraints while reducing wirelength, thus dubbed as Hippocrates:
FIRST-DO-NO-HARM optimizations. Our experimental results show great
promises. By honoring these constraints, our detailed placement
technique not only reduces total wirelength (TWL), but also
significantly improves timing, achieving 37% better total negative
slack (TNS). |
| PDF file |
| Title | ECO-system: Embracing the Change in Placement |
| Author | *Jarrod Roy, Igor Markov (University of Michigan, United States) |
| Page | pp. 147 - 152 |
| Keyword | Placement, ECO, Physical Synthesis |
| Abstract | In a realistic design flow, circuit and system optimizations must interact with physical aspects of the design. For example, improvements in timing and power may require replacing large modules with variants that have different power/delay trade-off, shape and connectivity. New logic may be added late in the design flow, subject to interconnect optimization. To support such flexibility in design flows we develop a robust system for performing Engineering Change Orders (ECOs). In contrast with existing stand-alone tools that offer poor interfaces to the design flow and cannot handle a full range of modern VLSI layouts, our ECO-system reliably handles fixed objects and movable macros in instances with widely varying amounts of whitespace. It detects geometric regions and sections of the netlist that require modification and applies an adequate amount of change in each case. Given a reasonable initial placement, it applies minimal changes, but is capable of re-placing large regions to handle pathological cases. ECO-system can be used in the range from high-level synthesis, to physical synthesis and detail placement. |
| PDF file |
| Title | Bisection Based Placement for the X Architecture |
| Author | *Satoshi Ono (SUNY Binghamton CSD, United States), Sameer Tilak (Supercomputer Center, United States), Patrick H. Madden (SUNY Binghamton CSD, United States) |
| Page | pp. 153 - 158 |
| Keyword | placement, x architecture |
| Abstract | Rising interconnect delay and power consumption have motivated the
investigation of alternative integrated circuit routing
architectures. In particular, the X Architecture, which features
preferred routing in diagonal directions, has gained a measure of
industry support, and has even been validated at 65nm.
While there has been extensive study of Manhattan design
methods, there are markedly fewer published results for non-Manhattan
design. To help fill this gap,
we study a patented placement method for the X
Architecture; to our knowledge, there have been no prior published
results for the method. Surprisingly, we find that the patented
method
in fact performs worse than
traditional Manhattan methods -- for both Manhattan and X routing
metrics. We also present a theoretic formulation which explains why
solution quality is degraded.
Many groups in industry are evaluating the merits of non-Manhattan
routing architectures.
By providing concrete
experimental results, we hope to improve the accuracy of these
evaluations. |
| PDF file |