A solution to line-routing problems on the continuous plane

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A solution to line-routing problems on the continuous plane

Full text

Pdf (799 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 6th annual Design Automation Conference table of contents

Pages: 1 - 24

Year of Publication: 1969

Author

David W. Hightower

Sponsors

IEEE : Institute of Electrical and Electronics Engineers
SHARE : SHARE
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 88, Citation Count: 83

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800260.809014 What is a DOI?

ABSTRACT

This paper discusses a new line-routing algorithm. The algorithm has been programmed in FORTRAN II for the IBM 7094 and in FORTRAN IV for the IBM 360/65. It has given good results when applied to many line-routing problems such as mazes, printed circuit boards, substrates, and PERT diagrams. The main advantages of this algorithm, which is based on the continuous plane, over conventional algorithms based on the discrete plane are twofold: 1. Since the algorithm is based on the continuous plane, there is theoretically no limit to the degree of precision used to describe the position of points. In practice, the only factor restricting the precision is the magnitude of the largest (or smallest) number which may be stored in a computer. As a result, the nodes on a printed circuit board, for example, can be input with mil accuracy. If this feat were to be accomplished by existing methods on a 9×9 inch board, a matrix of 81,000,000 cells would have to be stored (and searched) in the computer. 2. The algorithm stores only line segments; therefore to find a path, only the segments that are currently defined need be investigated. Usually with conventional methods, every cell that lies on every possible minimal path must be investigated. The net result is that this algorithm is much faster than the conventional method.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

C. Y. Lee, "An Algorithm for Path Connections and Its Applications," IRE Transactions on Electronic Computers; pp. 346 through 365, September, 1961.

CITED BY 83

	Venkat V. Venkataraman , Craig D. Wilcox, GEMS: an automatic layout tool for MIMOLA schematics, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.131-137, July 1986, Las Vegas, Nevada, United States
	Narendra V. Shenoy , William Nicholls, An efficient routing database, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	S. Aranoff , Y. Abulaffio, Routing of printed circuit boards, Proceedings of the 18th conference on Design automation, p.130-136, June 29-July 01, 1981, Nashville, Tennessee, United States
	Atreyi Chakraverti , Moon Jung Chung, Routing algorithm for gate array macro cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.658-662, June 12-15, 1988, Atlantic City, New Jersey, United States
	Joseph Dao , Nobu Matsumoto , Tsuneo Hamai , Chusei Ogawa , Shojiro Mori, A compaction method for full chip VLSI layouts, Proceedings of the 30th international conference on Design automation, p.407-412, June 14-18, 1993, Dallas, Texas, United States
	J. F. Naveda , K. C. Chang , H. C. Du, A new approach to multi-layer PCB routing with short vias, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.696-701, July 1986, Las Vegas, Nevada, United States
	Ulrich Lauther, A data structure for gridless routing, Proceedings of the 17th conference on Design automation, p.603-609, June 23-25, 1980, Minneapolis, Minnesota, United States
	B. Lin , A. R. Newton, KAHLUA: a hierarchical circuit disassembler, Proceedings of the 24th ACM/IEEE conference on Design automation, p.311-317, June 28-July 01, 1987, Miami Beach, Florida, United States
	R. S. Fisher, A multi-pass, multi-algorithm approach to PCB routing, Papers on Twenty-five years of electronic design automation, p.172-181, June 1988
	Akihiro Hashimoto , James Stevens, Wire routing by optimizing channel assignment within large apertures, Proceedings of the 8th workshop on Design automation, p.155-169, June 28-30, 1971, Atlantic City, New Jersey, United States
	A. Hashimoto , J. Stevens, Wire routing by optimizing channel assignment within large apertures, Papers on Twenty-five years of electronic design automation, p.35-49, June 1988
	Roland L. Mattison, A high quality, low cost router for MOS/LSI, Proceedings of the 9th workshop on Design automation, p.94-103, June 26-28, 1972
	Ikuo Nishioka , Takuji Kurimoto , Hisao Nishida , Seiji Yamamoto , Toru Chiba , Toshiaki Nagakawa , Takatsugu Fujioka , Masashi Uchino, An automatic routing system for high density multilayer printed wiring boards, Proceedings of the 17th conference on Design automation, p.520-527, June 23-25, 1980, Minneapolis, Minnesota, United States
	Thorsten Adler , Hiltrud Brocke , Lars Hedrich , Erich Barke, A current driven routing and verification methodology for analog applications, Proceedings of the 37th conference on Design automation, p.385-389, June 05-09, 2000, Los Angeles, California, United States
	J. Luhukay , W. J. Kubitz, A layout synthesis system for NMOS gate-cells, Proceedings of the 19th conference on Design automation, p.307-314, January 1982
	Lorenz Ladage , Rainer Leupers, Resistance extraction using a routing algorithm, Proceedings of the 30th international conference on Design automation, p.38-42, June 14-18, 1993, Dallas, Texas, United States
	Martin J. Welt, NOMAD: A printed wiring board layout system, Proceedings of the 12th conference on Design automation, p.152-161, January 1975
	William A. Dees, Jr. , Robert J. Smith, II, Performance of interconnection rip-up and reroute strategies, Proceedings of the 18th conference on Design automation, p.382-390, June 29-July 01, 1981, Nashville, Tennessee, United States
	William Swartz , Carl Sechen, A new generalized row-based global router, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.491-498, November 07-11, 1993, Santa Clara, California, United States
	A. Hetzel, A sequential detailed router for huge grid graphs, Proceedings of the conference on Design, automation and test in Europe, p.332-339, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Y. Fujihara , Y. Sekiyama , Y. Ishibashi , M. Yanaka, DYNAJUST: an efficient automatic routing technique optimizing delay conditions, Proceedings of the 26th ACM/IEEE conference on Design automation, p.791-794, June 25-28, 1989, Las Vegas, Nevada, United States
	Michel T. Doreau , Luther C. Abel, A topologically based non-minimum distance routing algorithm, Proceedings of the 15th conference on Design automation, p.92-99, June 19-21, 1978, Las Vegas, Nevada, United States
	Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States
	W. M. vanCleemput, On the topological aspects of the circuit layout problem, Proceedings of the 13th conference on Design automation, p.441-450, June 28-30, 1976, San Francisco, California, United States
	Le-Chin Eugene Liu , Hsiao-Ping Tseng , Carl Sechen, Chip-level area routing, Proceedings of the 1998 international symposium on Physical design, p.197-204, April 06-08, 1998, Monterey, California, United States
	William V. Herrick , James R. Sims, A successful automated IC design system, Proceedings of the 13th conference on Design automation, p.74-78, June 28-30, 1976, San Francisco, California, United States
	Lawrence E. Druffel , Douglas C. Schmidt , Robert A. Wagner, A simple, efficient design automation processor, Proceedings of the 11th workshop on Design automation, p.127-136, January 1974
	H-J. Rothermel , D. A. Mlynski, Computation of power supply nets in VLSI layout, Proceedings of the 18th conference on Design automation, p.37-42, June 29-July 01, 1981, Nashville, Tennessee, United States
	Thorsten Adler , Erich Barke, Single step current driven routing of multiterminal signal nets for analog applications, Proceedings of the conference on Design, automation and test in Europe, p.446-450, March 27-30, 2000, Paris, France
	Donald P. Peterson, Computer/interactive cleanup of non-gridded PWB's after automatic routing, Proceedings of the 14th conference on Design automation, p.43-57, January 1977
	B. W. Kernighan , D. G. Schweikert , G. Persky, An optimum channel-routing algorithm for polycell layouts of integrated circuits, Papers on Twenty-five years of electronic design automation, p.57-66, June 1988
	J. Dion, Fast printed circuit board routing, Proceedings of the 24th ACM/IEEE conference on Design automation, p.727-734, June 28-July 01, 1987, Miami Beach, Florida, United States
	Michael J. Lorenzetti , Robert J. Smith, II, An implementation of a saturated zone multi-layer printed circuit board router, Proceedings of the 17th conference on Design automation, p.255-262, June 23-25, 1980, Minneapolis, Minnesota, United States
	D. W. Hightower , B. A. Unger, A method for rapid testing of beam crossover circuits, Proceedings of the 9th workshop on Design automation, p.144-156, June 26-28, 1972
	David W. Hightower , Robert L. Boyd, A generalized channel router, Proceedings of the 17th conference on Design automation, p.12-21, June 23-25, 1980, Minneapolis, Minnesota, United States
	Kaoru Kawamura , Masanobu Umeda , Hiroshi Shiraishi, Hierarchical dynamic router, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.803-809, July 1986, Las Vegas, Nevada, United States
	David W. Hightower, The interconnection problem - a tutorial, Proceedings of the 10th workshop on Design automation, p.1-21, June 25-27, 1973
	Takumi Watanabe , Yoshi Sugiyama, A new routing algorithm and its hardware implementation, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.574-580, July 1986, Las Vegas, Nevada, United States
	David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States
	D. N. Deutsch, A “DOGLEG” channel router, Papers on Twenty-five years of electronic design automation, p.111-119, June 1988
	W. Heyns , W. Sansen , H. Beke, A line-expansion algorithm for the general routing problem with a guaranteed solution, Proceedings of the 17th conference on Design automation, p.243-249, June 23-25, 1980, Minneapolis, Minnesota, United States
	B. W. Kernighan , D. G. Schweikert , G. Persky, An optimum channel-routing algorithm for polycell layouts of integrated circuits, Proceedings of the 10th workshop on Design automation, p.50-59, June 25-27, 1973
	B. Ramakrishna Rau, A new philosophy for interconnection on multilayer boards, Proceedings of the 13th conference on Design automation, p.225-231, June 28-30, 1976, San Francisco, California, United States
	J. C. Foster, A router for multilayer printed wiring backplanes, Proceedings of the 10th workshop on Design automation, p.44-49, June 25-27, 1973
	K. Bedard , S. Fournier , B. Shastry , U. Stockburger, A production PCB layout system on a minicomputer, Proceedings of the 14th conference on Design automation, p.168-173, January 1977
	K. R. Stevens , W. M. vanCleemput , T. C. Bennett , J. A. Hupp, Implementation of an interactive printed circuit design system, Proceedings of the 15th conference on Design automation, p.74-81, June 19-21, 1978, Las Vegas, Nevada, United States
	G. Persky , C. Enger , D. M. Selove, The Hughes Automated Layout System - automated LSI/VLSI layout based on channel routing, Proceedings of the 18th conference on Design automation, p.22-28, June 29-July 01, 1981, Nashville, Tennessee, United States
	Gordon T. Hamachi , John K. Ousterhout, A switchbox router with obstacle avoidance, Proceedings of the 21st conference on Design automation, p.173-179, June 25-27, 1984, Albuquerque, New Mexico, United States
	Gary W. Clow, A global routing algorithm for general cells, Proceedings of the 21st conference on Design automation, p.45-51, June 25-27, 1984, Albuquerque, New Mexico, United States
	Xiong Ji-Guang , Tokinori Kozawa, An algorithm for searching shortest path by propagating wave fronts in four quadrants, Proceedings of the 18th conference on Design automation, p.29-36, June 29-July 01, 1981, Nashville, Tennessee, United States
	Shih-Ping Lin , Yao-Wen Chang, A novel framework for multilevel routing considering routability and performance, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.44-50, November 10-14, 2002, San Jose, California
	Andrew J. Matthews, A human engineered PCB design system, Proceedings of the 14th conference on Design automation, p.182-186, January 1977
	Jason Cong , Jie Fang , Yan Zhang, Multilevel approach to full-chip gridless routing, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	W. G. Cage , R. J. Smith, II, A rectangle-probe router for multilayer P.C. boards*, Proceedings of the 14th conference on Design automation, p.13-22, January 1977
	Kai-Win Lee , Carl Sechen, A global router for sea-of-gates circuits, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Jason Cong , Min Xie , Yan Zhang, An enhanced multilevel routing system, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.51-58, November 10-14, 2002, San Jose, California
	Wenliang Wu , Douglas C. Schmidt, A new routing algorithm for two-sided boards with floating vias, Proceedings of the 13th conference on Design automation, p.151-160, June 28-30, 1976, San Francisco, California, United States
	W. L. Schiele , Th. Krüger , K. M. Just , F. H. Kirsch, A gridless router for industrial design rules, Proceedings of the 27th ACM/IEEE conference on Design automation, p.626-631, June 24-27, 1990, Orlando, Florida, United States
	Robert S. Fisher, A multi-pass, multi-algorithm approach to PCB routing, Proceedings of the 15th conference on Design automation, p.82-91, June 19-21, 1978, Las Vegas, Nevada, United States
	Jer Min Jou , Jau Yien Lee , Yachyang Sun , Jhing Fa Wang, An Efficient VLSI Switch-Box Router, IEEE Design & Test, v.7 n.4, p.52-65, July 1990
	L. Stok , G. P. Koster, From network to artwork, Proceedings of the 26th ACM/IEEE conference on Design automation, p.686-689, June 25-28, 1989, Las Vegas, Nevada, United States
	James A. Smith , James G. Linders, Automatic generation of logic diagrams, Proceedings of the 13th conference on Design automation, p.377-391, June 28-30, 1976, San Francisco, California, United States
	Yiyu Shi , Tong Jing , Lei He , Zhe Feng , Xianlong Hong, CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Michael F. Kelly, Comparative router performance, ACM SIGDA Newsletter, v.5 n.2, p.12-22, June 1975
	Hardy Kwok-Shing Leung, Advanced routing in changing technology landscape, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Chi-Ping Hsu, A new two-dimensional routing algorithm, Proceedings of the 19th conference on Design automation, p.46-50, January 1982
	Kenneth J. Supowit, A minimum-impact routing algorithm, Proceedings of the 19th conference on Design automation, p.104-112, January 1982
	H. G. Adshead, Optimising automatic tracking of multilayer boards, ACM SIGDA Newsletter, v.5 n.3, p.14-28, September 1975
	William A. Dees, Jr. , Patrick G. Karger, Automated rip-up and reroute techniques, Proceedings of the 19th conference on Design automation, p.432-439, January 1982
	Ivan R. Dobes, A multi-contouring algorithm, ACM SIGDA Newsletter, v.7 n.2, p.2-11, June 1977
	Yu Hu , Tong Jing , Xianlong Hong , Zhe Feng , Xiaodong Hu , Guiying Yan, An-OARSMan: obstacle-avoiding routing tree construction with good length performance, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Tai-Chen Chen , Yao-Wen Chang, Multilevel full-chip gridless routing considering optical proximity correction, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Zhe Feng , Yu Hu , Tong Jing , Xianlong Hong , Xiaodong Hu , Guiying Yan, An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA
	Zahir Syed , Abbas El Gamal , M. A. Breuer, On routing for custom integrated circuits, Proceedings of the 19th conference on Design automation, p.887-893, January 1982
	Chung-Wei Lin , Szu-Yu Chen , Chi-Feng Li , Yao-Wen Chang , Chia-Lin Yang, Efficient obstacle-avoiding rectilinear steiner tree construction, Proceedings of the 2007 international symposium on Physical design, March 18-21, 2007, Austin, Texas, USA
	Xin Jia , Ranga Vemuri, Studying a GALS FPGA architecture using a parameterized automatic design flow, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Tsung-Yi Ho , Yao-Wen Chang , Sao-Jie Chen , D. T. Lee, A Fast Crosstalk- and Performance-Driven Multilevel Routing System, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.382, November 09-13, 2003
	Wei Chen , Massoud Pedram , Premal Buch, Buffered Routing Tree Construction Under Buffer Placement Blockages, Proceedings of the 2002 conference on Asia South Pacific design automation/VLSI Design, p.381, January 07-11, 2002
	T C. Bennett , K. R. Stevens , W. M. vanCleemput, Dynamic design rule checking in an interactive printed circuit editor, Proceedings of the 16th Conference on Design automation, p.330-336, June 25-27, 1979, San Diego, CA, United States
	W. A. Dees , K. M. Parmar , A. Goyal , R. Y. Tsui , B. D. Rathi , R. J. Smith, II, A computer-aided VLSI layout system, Proceedings of the May 4-7, 1981, national computer conference, May 04-07, 1981, Chicago, Illinois
	Yiyu Shi , Paul Mesa , Hao Yu , Lei He, Circuit-simulated obstacle-aware Steiner routing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.12 n.3, p.1-18, August 2007
	Tom Tong Jing , Yu Hu , Zhe Feng , Xian-Long Hong , Xiaodong Hu , Guiying Yan, A full-scale solution to the rectilinear obstacle-avoiding Steiner problem, Integration, the VLSI Journal, v.41 n.3, p.413-425, May, 2008
	Daniel M. Tracy , W. Randolph Franklin , Barbara Cutler , Franklin T. Luk , Marcus Andrade, Path planning on a compressed terrain, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California