Optimization of Placement Driven by the Cost of Wire Crossing.
Abstract
We conjecture that good column-based placements can be produced by minimizing two wire crossing numbers: (1) the total wire crossing of all edges between cells in the wiring channel, and (2) the maximum wire crossing on the imaginary cutlines that separate cells on the opposite ends of the channels. We leverage the canonical form of the multi-level bipartite directed graph to formalize a unit-grid model that allows us to define and evaluate parameters such as total wire crossing, critical wire crossing, total wire length, critical wire length, critical wire density, total wire density, as well as height, width, and area of the embedded graph. We implemented a prototype placement algorithm TOCO that minimizes the cost of wire crossing, and a universal unit-grid based placement evaluator place_eval. We have designed a number of statistical experiments to demonstrate the feasibility and the promise of the proposed approach
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1997
- Accession Number
- ADA344498
Entities
People
- Debabrata Ghosh
- Franc Brglez
- Nevin Kapur
Organizations
- North Carolina State University