A new approach to global routing for three-metal-layer gate arrays

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.