Title :
A parallel lookahead line search router with automatic ripup-and-reroute
Author :
Date, Hiroshi ; Taki, Kazuo
Author_Institution :
Inst. for New Generation Comput. Technol., Tokyo, Japan
Abstract :
A parallel routing method is proposed and evaluated. A key feature is object-oriented modeling. All line segments are modeled as independent objects communicating with each other through message exchanges. A distributed routing algorithm is designed based on a lookahead line search method that includes automatic ripup-and-reroute to retain the rotating order. The program was implemented in a concurrent logic language, KL1, and was executed on PIM/m (Parallel Inference Machine), a distributed memory machine with 256 processors. The evaluation results for several industrial data are given
Keywords :
circuit layout CAD; integrated circuit layout; network routing; object-oriented methods; parallel algorithms; parallel processing; KL1; PIM/m; automatic ripup-and-reroute; concurrent logic language; distributed routing algorithm; message exchanges; object-oriented modeling; parallel inference machines; parallel lookahead line search router; Algorithm design and analysis; Concurrent computing; Inference algorithms; Large-scale systems; Logic; Object oriented modeling; Parallel processing; Routing; Search methods; Systems engineering and theory;
Conference_Titel :
Design Automation, 1993, with the European Event in ASIC Design. Proceedings. [4th] European Conference on
Conference_Location :
Paris
Print_ISBN :
0-8186-3410-3
DOI :
10.1109/EDAC.1993.386490
