Title: An intelligent multi-layer net routing method based on minimum spanning tree

Authors: Wei Qiu, Ping Yang

Addresses: Laboratory of Advanced Design, Manufacturing & Reliability for MEMS/NEMS, Jiangsu University, Zhenjiang, 212013, P.R. China. ' Laboratory of Materials & Micro-Structural Integrity, School of Mechanical Engineering, Jiangsu University, Zhenjiang, 212013, P.R. China

Abstract: Multi-layer net routing is a common style in very large-scale integration (VLSI) net routing. In this paper, a systematic method to intelligent multi-layer net routing approach for VLSI physical design is provided. We take two-layer net routing for example. One layer is for horizontal lines and the other is for vertical lines. Vias are used for the connection between different layers. A new mixed intelligent algorithm called tabu-ant colonies system is presented by combining ant colonies algorithm and tabu search algorithm. Computer experiments show that the intelligent algorithm based on MST is a valid algorithm to solve the multi-layer routing problem.

Keywords: multi-layer routing; tabu search; ant colonies; hybrid modelling; optimal path; VLSI physical design; VLSI net routing.

DOI: 10.1504/IJMSI.2008.022994

International Journal of Materials and Structural Integrity, 2008 Vol.2 No.4, pp.332 - 344

Published online: 06 Feb 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article