Title :
An implicit connection graph maze routing algorithm for ECO routing
Author :
Cong, J. ; Jie Fang ; Kei-Yong Khoo
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Abstract :
ECO routing is a very important design capability in advanced IC, MCM and PCB designs when additional routings need to be made at the latter stage of the physical design. ECO is difficult in two aspects: first, there are a large number of existing interconnects which become obstacles in the region. A hierarchical approach is not applicable in this situation, and we need to search a large, congested region thoroughly. Second, advances in circuit designs require variable width and variable spacing on interconnects. Thus, a gridless routing algorithm is needed. We propose to use an implicit representation of a non-uniform grid graph for a gridless maze routing algorithm. A novel slit-tree plus interval-tree data structure is developed, combined with a cache structure, to support efficient queries into the connection graph. Our experiments show that this data structure is very small in memory usage while very fast in answering maze expansion related queries. This makes the framework very useful in the ECO type of routing.
Keywords :
circuit layout CAD; graph theory; network routing; tree data structures; ECO routing; IC design; MCM design; PCB design; cache structure; circuit design; experiments; gridless routing algorithm; implicit connection graph maze routing algorithm; interval-tree data structure; non-uniform grid graph; Circuit synthesis; Computer science; Contracts; Data structures; Databases; Design engineering; Integrated circuit interconnections; Process design; Routing; Tiles;
Conference_Titel :
Computer-Aided Design, 1999. Digest of Technical Papers. 1999 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA, USA
Print_ISBN :
0-7803-5832-5
DOI :
10.1109/ICCAD.1999.810642