A highly efficient routing algorithm

Abstract

Routing is a challenging problem in today's circuit system design. ULSI, MCM and PCB are requiring over a hundred thousand interconnections within several tens of routing layers. Sluggish and memory devouring routing programs cannot fulfill these up-to-date design requirements. On the other hand, the performance of advanced circuit systems is directly related to the scheme of circuit interconnections. Therefore, routing without careful examination of circuit performance requirements results in low quality circuit systems. In this thesis, a Highly-Efficient Routing Algorithm(HERA) for general, large-scale multi-layer routing is presented. Its efficiency is based on an effectively organized data structure, optimized Steiner tree construction and an efficient obstacle-searching algorithm. Experimental results show that HERA outperforms all well-known routing algorithms in terms of execution time and routing quality. It runs over a hundred times faster than V 4R on big industrial routing benchmarks. HERA also produces uniformly distributed interconnections of shorter wiring length.