Title :
A maze routing method of combined unity and infinity expansion distances
Author :
Vai, Man-Kuan ; Aybay, Gunes ; Chu, Sai-Man
Author_Institution :
Dept. of Electr. & Comput. Eng., Northeastern Univ., Boston, MA, USA
Abstract :
A method for maze routing problems which combines unity and infinity distances into the wavefront expansion phase of a generic Lee´s algorithm is described. A unity distance wavefront is maintained at each step of the expansion to guarantee finding minimum-length paths, while an infinity distance labeling scheme is adapted to ensure that the labels can be used to determine a minimum-corner path among them. Since the originally proposed three sequential expansions are replaced by a single one, the routing time is significantly improved
Keywords :
circuit layout; network topology; generic Lee´s algorithm; infinity expansion distances; labeling scheme; maze routing method; minimum-corner path; minimum-length paths; routing time; sequential expansions; unity distance wavefront; wavefront expansion phase; Application specific integrated circuits; Design automation; H infinity control; Integrated circuit reliability; Labeling; Process design; Routing; Signal processing; Turning; Very large scale integration;
Conference_Titel :
Custom Integrated Circuits Conference, 1990., Proceedings of the IEEE 1990
Conference_Location :
Boston, MA
DOI :
10.1109/CICC.1990.124812
