A new one-and-half layer channel routing algorithm based on assigning resources for CMOS gate array

It is demonstrated that sufficient and reasonable utilization of the constrained horizontal and vertical routing resources is the key to achieving a high completion rate in this one-and-one-half layer routing approach. By using the minimum intersection graph to order the nets, the number of intersections among the nets is minimum, the number of intersection columns is as small as possible, and the total length of poly-bars used in wiring is as short as possible. From this the requirements for the horizontal and vertical routing resources are as few as possible. A reasonable assignment of the horizontal routing resources can be achieved by operating the active track matrices of the nets at the predicted columns, while the optimal assignment of the vertical routing resources is obtained by using the cluster assignment algorithm of the incidence intersection columns. Guided by the wiring tracks in the predicted columns and using the poly-bars assigned, the channel routing can be implemented with high performance by scanning the channel from left to right and column by column