Name
Abstract | ||
|---|---|---|
In this wrok, we develop methods to reduce interconnect delay and noise caused by coupling. First, we explain the Coupling-Free Routing (CFR) problem. CFR takes a set of nets and tries to find a one-bend couple-free routing for a subset of nets. A routed net must not couple with any other routed net. We define coupling as a boolean variable which is true when the coupling of two nets is greater than some threshold. Any pair-wise coupling definition can be used. We argue that this problem is useful in both global and detailed routingWe develop an exact algorithm for the CFR decision problem via a transformation to 2-satisfiability. This algorithm runs in linear time. The decision problem determines whether the given set of nets is coupling-free routable. Next, we present the implication graph which models the dependencies associated with CFR. Also, we look at some of the properties associated with the graph.Finally, we develop a new algorithm for the Maximum Coupling-Free Layout (MAX-CFL) problem. Given a set of nets, the MAX-CFL is defined as finding a subset of nets that are coupling-free routable. The subset should have maximum size and/or critically. The new algorithm, called implication algorithm, uses properties assoicated with the implication graph and experiments show that it consistently finds the best solution in terms of number of nets routed as compared to previous algorithms |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/369691.369711 | ISPD |
Keywords | Field | DocType |
coupling-free routing,implication algorithm,decision problem,cfr decision problem,coupling-free routable,new algorithm,pair-wise coupling definition,previous algorithm,exact algorithm,implication graph,linear time,satisfiability | Graph,Decision problem,Mathematical optimization,Coupling,Exact algorithm,Computer science,Implication graph,Interconnection,Time complexity,Boolean data type | Conference |
ISBN | Citations | PageRank |
1-58113-347-2 | 20 | 1.29 |
References | Authors | |
19 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ryan Kastner | 1 | 1779 | 147.73 |
| Elaheh Bozorgzadeh | 2 | 630 | 37.93 |
| Majid Sarrafzadeh | 3 | 3103 | 317.63 |