A "Greedy" Channel Router
作者： Ronald L. Rivest , Charles M. Fiduccia , Charles M. Fiduccia
关键词: Communication channel 、 Grid 、 Heuristics 、 Simple (philosophy) 、 Engineering 、 Router 、 Track (rail transport) 、 Routing (electronic design automation) 、 Computer network 、 Column (database)
摘要: We present a new, "greedy", channel-router that is quick, simple, and highly effective. It always succeeds, usually using no more than one track required by channel density. (It may be forced in rare cases to make few connections "off the end" of channel, order succeed.) assumes all pins wiring lie on common grid, vertical wires are layer, horizontal another. The greedy router up left-to-right, column-by-column manner, each column completely before starting next. Within tries maximize utility produced, "greedy" heuristics. place net for columns, "collapse" single later on, jog. also use jog move closer its pin some future column. occasionally add new avoid "getting stuck".
acm.org
sci-hub.st 参考文章(19)
A. S. LaPaugh, ALGORITHMS FOR INTEGRATED CIRCUIT LAYOUT: AN ANALYTIC APPROACH Massachusetts Institute of Technology. ,(1980)
Ronald L. Rivest, Alan E. Baratz, Gary Miller, Provably Good Channel Routing Algorithms VLSI Systems and Computations. pp. 153- 159 ,(1981) , 10.1007/978-3-642-68402-9_18
James Joseph Koschella, A placement/interconnect channel router : cutting your PI into slices Massachusetts Institute of Technology. ,(1981)
Donna J. Brown, Ronald L. Rivest, New Lower Bounds for Channel Width VLSI Systems and Computations. pp. 178- 185 ,(1981) , 10.1007/978-3-642-68402-9_20
Ron Y. Pinter, Optimal Routing in Rectilinear Channels VLSI Systems and Computations. pp. 160- 177 ,(1981) , 10.1007/978-3-642-68402-9_19
Martin Tompa, An optimal solution to a wire-routing problem☆ Journal of Computer and System Sciences. ,vol. 23, pp. 127- 150 ,(1981) , 10.1016/0022-0000(81)90010-6
Martin Tompa, An optimal solution to a wire-routing problem (preliminary version) symposium on the theory of computing. pp. 161- 176 ,(1980) , 10.1145/800141.804664
T. Yoshimura, E.S. Kuh, Efficient Algorithms for Channel Routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 1, pp. 25- 35 ,(1982) , 10.1109/TCAD.1982.1269993
Sartaj Sahni, Atul Bhatt, The complexity of design automation problems Proceedings of the seventeenth design automation conference on Design automation - DAC '80. pp. 402- 411 ,(1980) , 10.1145/800139.804562
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)