Loading...
Please wait, while we are loading the content...
Similar Documents
A Multi-layer Area Routing Methodology using a Boolean Satisfiability based Router
| Content Provider | Semantic Scholar |
|---|---|
| Author | Khatri, Sunil P. Sangiovanni-Vincentelli, Alberto |
| Copyright Year | 2017 |
| Abstract | We propose an area routing technique which is suitable for deep sub-micron applications. In its most gen eral form, the routing problem can be viewed as finding wiring connections between electrically equivalent pins, utilizing one or more layers of metal, while avoiding obstacles present possibly on every layer of metal. This general formulation (called area routing) has been traditionally used for routing printed circuit boards (PCBs) and multi-chip modules (MCMs). This formulation is general enough to encompass routing in integrated circuits as well. However, more specialized forms of routers have traditionally been used for ICs. We argue why the traditional IC routing methodology of first performing a global routing step, then utilizing switch-box or channel routers, is inadequate in this new scenario. Insteadof performinga global-then-detailedrouting approach, we choose a routing technique that partitions all the nets into smaller clusters, and then routes all the nets in a cluster using a Boolean satisfiability (SAT) based search strategy. In our scheme, we first assign each net to a routing layer pair. The set of nets on each layer pair is now partitioned into several clusters such that the overlap between nets in different clusters is minimized. All the nets in any cluster are routed simultaneously, and each net cluster is routed independently. The ordering of net clusters is done using a simple heuristic. Within a cluster, all nets are routed simultaneously using SATRE, our SAT based routing engine. Routes for a net can be chosen from predetermined set of routing patterns, which utilize 2, 3 or 4 vias. We assign Boolean variables to represent all the possible routes that the net can use, and create SATclauses to represent the routing constraints for each net. This step requiresonly 0{log2{N)) Booleanvariables, whereN is the size of the routing problem. The transformation of the area routing probleminto an instance of BooleanSatisfiability (SAT) is thus performed veryefficiently. Next,we perform a binarysearchto find a satisfying solutionof theSATinstance, using non-chronologicalbacktrackto give rise to an efficientsearch procedure. The novel feature of this scheme is that it eliminates the global-then-detailed routing paradigm used in earlier generations of routers. Rather, it proposes a newrouting methodology, where the set of all nets is partitioned into net clusters, followed by the simultaneous routing of all the nets in a singlecluster. Further, the scheme is easily adapted to a situation where several metal layers are available for routing. In our experiments,we assume that 4 metal layers are availablefor routing. We show that our router is able to obtainextremely denseroutes with reasonable run-times. The highquality of our results is evidenced by the fact that over all the exampleswe tried, the total net length was on average 1.47% larger than the sum of Manhattan length for all the nets. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://digitalassets.lib.berkeley.edu/techreports/ucb/text/ERL-99-16.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
