Clustering and linear placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Clustering and linear placement

Full text

Pdf (436 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 9th Design Automation Workshop table of contents

Pages: 50 - 56

Year of Publication: 1972

Authors

Donald M. Schuler
Ernst G. Ulrich

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 43

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/800153.804929 What is a DOI?

ABSTRACT

This paper presents two algorithms, one for clustering a set of interconnected nodes and the other for forming a linear placement of clustered interconnected nodes. The linear placement algorithm requires the output of clustering as an input. The two algorithms were designed to analyze the structure of digital logic for automatic placement of logic functions on a MOS/LSI chip as part of an automatic layout system8 and so far have only been used for that application. However, the clustering algorithm could be used to analyze any undirected graph. Both algorithms are noniterative and provide very good results with small amounts of computer time.

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.

	1	M. A. Breuer, "General Survey of Design Automation of Digital Computers," Proceedings IEEE, Vol. 54, pp. 1708-1721, December 1966.
	2	Howard R. Charney , Donald L. Plato, Efficient partitioning of components, Proceedings of the 5th annual workshop on Design automation, p.16.1-16.21, July 15-18, 1968, Washington, D. C., United States [doi>10.1145/800167.805401]
	3	R. Mitchell, Personal Notes.
	4	Murray A. Milne, CLUSTR: A program for structuring design problems, Proceedings of the 8th workshop on Design automation, p.242-249, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805078]
	5	E. L. Lawler, "Electrical Assemblies with a Minimum Number of Interconnections," IEEE Transactions on Electronic Computers, Vol. EC-11, pp. 86-88, February 1962.
	6	R. L. Russo , P. K. Wolff, Sr., ALMS: Automated logic mapping system, Proceedings of the 8th workshop on Design automation, p.118-130, June 28-30, 1971, Atlantic City, New Jersey, United States [doi>10.1145/800158.805066]
	7	D. M. Schuler, "The Clustering of Interconnected Nodes," GTE Laboratories Technical Memorandum 70-468.1, December 1970.
	8	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 [doi>10.1145/800153.804934]
	9	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997

CITED BY 43

	Y. E. Cho , A. J. Korenjak , D. E. Stockton, Floss: An approach to automated layout for high-volume designs, Proceedings of the 14th conference on Design automation, p.138-141, January 1977
	T. Kambe , T. Chiba , S. Kimura , T. Inufushi , N. Okuda , I. Nishioka, A placement algorithm for polycell LSI and ITS evaluation, Proceedings of the 19th conference on Design automation, p.655-662, January 1982
	G. Persky , D. N. Deutsch , D. G. Schweikert, LTX - a system for the directed automatic design of LSI circuits, Proceedings of the 13th conference on Design automation, p.399-407, June 28-30, 1976, San Francisco, California, United States
	Bernhard M. Riess , Konrad Doll , Frank M. Johannes, Partitioning very large circuits using analytical placement techniques, Proceedings of the 31st annual conference on Design automation, p.646-651, June 06-10, 1994, San Diego, California, United States
	A. J. Goldstein , A. B. Lesk, Common feature techniques for discrete optimization, Proceedings of the 13th conference on Design automation, p.232-244, June 28-30, 1976, San Francisco, California, United States
	Yu-Wen Tsay , Wen-Jong Fang , Allen C.-H. Wu , Youn-Long Lin, Preserving HDL synthesis hierarchy for cell placement, Proceedings of the 1997 international symposium on Physical design, p.169-174, April 14-16, 1997, Napa Valley, California, United States
	Chi-Song Horng , Margaret Lie, An automatic/interactive layout planning system for arbitrarily-sized rectangular building blocks, Proceedings of the 18th conference on Design automation, p.293-300, June 29-July 01, 1981, Nashville, Tennessee, United States
	J. Song , Z. Shen , W. Zhuang, An effective general connectivity concept for clustering, Proceedings of the conference on Design, automation and test in Europe, p.398-405, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Sivanarayana Mallela , Lov K. Grover, Clustering based simulated annealing for standard cell placement, Proceedings of the 25th ACM/IEEE conference on Design automation, p.312-317, June 12-15, 1988, Atlantic City, New Jersey, United States
	Yasushi Ogawa , Tatsuki Ishii , Yoichi Shiraishi , Hidekazu Terai , Tokinori Kozawa , Kyoji Yuyama , Kyoji Chiba, Efficient placement algorithms optimizing delay for high-speed ECL masterslice LSIs, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.404-410, July 1986, Las Vegas, Nevada, United States
	Tokinori Kozawa , Hiroshi Horino , Tadakatu Ishiga , Junya Sakemi , Shoji Sato, Advanced LILAC - an Automated Layout Generation system for MOS/LSIs, Proceedings of the 11th workshop on Design automation, p.26-46, January 1974
	Hsiao-Pin Su , Allen C.-H. Wu , Youn-Long Lin, Performance-driven soft-macro clustering and placement by preserving HDL design hierarchy, Proceedings of the 1998 international symposium on Physical design, p.12-17, 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
	I. H. Kirk , P. D. Crowhurst , J. A. Skingley , J. D. Bowman , G. L. Taylor, Placement of irregular circuit elements on non-uniform gate arrays, Proceedings of the 20th conference on Design automation, p.637-643, June 27-29, 1983, Miami Beach, Florida, United States
	D. G. Schweikert, A 2-dimensional placement algorithm for the layout of electrical circuits, Papers on Twenty-five years of electronic design automation, p.102-110, June 1988
	Daniel G. Schweikert, A 2-dimensional placement algorithm for the layout of electrical circuits., Proceedings of the 13th conference on Design automation, p.408-416, June 28-30, 1976, San Francisco, California, United States
	G. Persky, PRO - an automatic string placement program for polycell layout, Proceedings of the 13th conference on Design automation, p.417-424, June 28-30, 1976, San Francisco, California, United States
	G. Persky , H. K. Gummel, GRAFOS - A symbolic routing language, Proceedings of the 10th workshop on Design automation, p.173-181, June 25-27, 1973
	G. Persky , D. N. Deutsch , D. G. Schweikert, LTX-A system for the directed automatic design of LSI circuits, Papers on Twenty-five years of electronic design automation, p.93-101, June 1988
	Hidekazu Terai , Michiyoshi Hayase , Tokinori Kozawa, A routing procedure for mixed array of custom macros and standard cells, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.503-508, June 1985, Las Vegas, Nevada, United States
	Bryan T. Preas , Patrick G. Karger, Automatic placement a review of current techniques (tutorial session), Proceedings of the 23rd ACM/IEEE conference on Design automation, p.622-629, July 1986, Las Vegas, Nevada, United States
	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
	Y. E. Cho , A. J. Kroenjak , D. E. Stockton, FLOSS: an approach to automated layout for high-volume designs, Papers on Twenty-five years of electronic design automation, p.138-141, June 1988
	Kenneth A. Roberts , Thomas E. Baker , David H. Jerome, A vertically organized computer-aided design data base, Proceedings of the 18th conference on Design automation, p.595-602, June 29-July 01, 1981, Nashville, Tennessee, United States
	Bill D. Richard, A standard cell initial placement strategy, Proceedings of the 21st conference on Design automation, p.392-398, June 25-27, 1984, Albuquerque, New Mexico, United States
	Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
	Glenn W. Cox , B. D. Carroll, The Standard Transistor Array (star) (Part II automatic cell placement techniques), Proceedings of the 17th conference on Design automation, p.451-457, June 23-25, 1980, Minneapolis, Minnesota, United States
	Jason Cong , Sung Kyu Lim, Edge separability based circuit clustering with application to circuit partitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.429-434, January 2000, Yokohama, Japan
	Hsiao-Pin Su , Allen C.-H. Wu , Youn-Long Lin, A timing-driven soft-macro resynthesis method in interaction with chip floorplanning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.262-267, June 21-25, 1999, New Orleans, Louisiana, United States
	Yoichi Shiraishi , Jun'ya Sakemi , Makoto Kutsuwada , Akira Tsukizoe , Takashi Satoh, A high packing density module generator for CMOS logic cells, Proceedings of the 25th ACM/IEEE conference on Design automation, p.439-444, June 12-15, 1988, Atlantic City, New Jersey, United States
	Bo Hu , Malgorzata Marek-Sadowska, Fine granularity clustering for large scale placement problems, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA
	Bo Hu , Malgorzata Marek-Sadowska, Wire length prediction based clustering and its application in placement, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	T. Kozawa , H. Terai , T. Ishii , M. Hayase , C. Miura , Y. Ogawa , K. Kishida , N. Yamada , Y. Ohno, Automatic placement algorithms for high packing density V L S I, Proceedings of the 20th conference on Design automation, p.175-181, June 27-29, 1983, Miami Beach, Florida, United States
	R. P. Goré , K. Ramaamohanarao, Automatic synthesis of Boolean equations using programmable array logic, Proceedings of the 26th ACM/IEEE conference on Design automation, p.283-289, June 25-28, 1989, Las Vegas, Nevada, United States
	Gotaro Odawara , Kazuhiko Iijima , Kazutoshi Wakabayashi, Knowledge-based placement technique for printed wiring boards, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.616-622, June 1985, Las Vegas, Nevada, United States
	Thomas Kutzschebauch , Leon Stok, Congestion aware layout driven logic synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Charles Alpert , Andrew Kahng , Gi-Joon Nam , Sherief Reda , Paul Villarrubia, A semi-persistent clustering technique for VLSI circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA
	H. Yoshizawa , H. Kawanishi , K. Kani, A heuristic procedure for ordering MOS arrays, Proceedings of the 12th conference on Design automation, p.384-393, January 1975
	Tadakatsu Ishiga , Tokinori Kozawa , Shoji Sato, A logic partitioning procedure by interchanging clusters, Proceedings of the 12th conference on Design automation, p.369-377, January 1975
	Youssef G. Saab, A Fast and Robust Network Bisection Algorithm, IEEE Transactions on Computers, v.44 n.7, p.903-913, July 1995
	M. Y. Yu , X. L. Hong , Y. E. Lien , Z. Z. Ma , J. G. Bo , W. J. Zhuang, A new clustering approach and its application to BBL placement, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	Shinichi Murai , Hiroo Tsuji , Morio Kakinuma , Kazumichi Sakaguchi , Chiyoji Tanaka, A hierarchical placement procedure with a simple blocking scheme, Proceedings of the 16th Conference on Design automation, p.18-23, June 25-27, 1979, San Diego, CA, United States
	Henning Fernau, Parameterized algorithmics for linear arrangement problems, Discrete Applied Mathematics, v.156 n.17, p.3166-3177, October, 2008