A new approach to global routing for three-metal-layer gate arrays
1996
We propose a new global routing approach for three-metal-layer gate arrays. A gate array chip handled in this paper consists of rows of cells of a uniform height, megacells such as RAMs or ROMs, and routing channels. The proposed approach breaks the gate array chip into a two-dimensional array of rectangular global routing cells (in short, G cells) by coarse grid lines and constructs global routes for all the nets on the array of G cells. The feature of our approach is that the capacities of G-cell boundaries corresponding to routing channels are variable. Utilizing freedom in the capacities of G-cell boundaries, our global routing algorithm changes the capacities at a certain stage of its execution and reduces the number of nets rerouted in the subsequent rerouting phase, in order to speed up the global routing process. The effectiveness of our approach is demonstrated by our experimental results on 400 K-gate sea-of-gates array chips.
Keywords:
- Routing table
- Link-state routing protocol
- Multipath routing
- Dynamic Source Routing
- DSRFLOW
- Static routing
- Mathematics
- Equal-cost multi-path routing
- Distributed computing
- Destination-Sequenced Distance Vector routing
- Topology
- Electronic engineering
- Zone Routing Protocol
- Enhanced Interior Gateway Routing Protocol
- Control theory
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
0
Citations
NaN
KQI