VICTOR: A three-layer over-the-cell router

A new algorithm, VICTOR, is presented for three-layer over-the-cell routing. VICTOR is designed to maximize track utilization in the over-the-cell routing region using graph theoretic approach combined with a channel decomposition and analysis scheme. VICTOR has been implemented in C on a SUN Sparc 1+ workstation and tested on several benchmarks. For the MCNC benchmark PRIMARY 1, VICTOR produces 92% and 91% reductions as compared to the two-layer over-the-cell routers presented by J. Cong et al. (Proc. 27th ACM/IEEE Design Automation Conf., p.709-715) and by N. Holmes et al. (Proc. 28th ACM/IEEE Design Automation Conf., p.126-131), respectively, and a 74% reduction as compared to the three-layer over-the-cell router of N. Holmes et al. (TCCAD-91, p.428-431)