Article

Free access

Clustering and linear placement

Authors:

Donald M. Schuler,

Ernst G. UlrichAuthors Info & Claims

DAC '72: Proceedings of the 9th Design Automation Workshop

Pages 50 - 56

https://doi.org/10.1145/800153.804929

Published: 26 June 1972 Publication History

PDF eReader

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 system⁸ 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

[1]

M. A. Breuer, "General Survey of Design Automation of Digital Computers," Proceedings IEEE, Vol. 54, pp. 1708-1721, December 1966.

Crossref

Google Scholar

[2]

H. R. Charney and D. L. Plato, "Efficient Partitioning of Components," Proceedings 5th Annual Design Automation Workshop, July 1968.

Digital Library

Google Scholar

[3]

R. Mitchell, Personal Notes.

Google Scholar

[4]

M. A. Milne, "CLUSTR: A Program for Structuring Design Problems," Proceedings 8th Annual Design Automation Workshop, pp. 242-249, June 1971.

Digital Library

Google Scholar

[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.

Crossref

Google Scholar

[6]

R. L. Russo and P. K. Wolff, Sr., "ALMS: Automated Logic Mapping System," Proceedings 8th Annual Design Automation Workshop, pp. 118-130, June 1971.

Digital Library

Google Scholar

[7]

D. M. Schuler, "The Clustering of Interconnected Nodes," GTE Laboratories Technical Memorandum 70-468.1, December 1970.

Google Scholar

[8]

R. L. Mattison, "A High Quality, Low Cost Router for MOS-LSI," Proceedings 9th Annual Design Automation Workshop, June 1972.

Digital Library

Google Scholar

[9]

D. E. Knuth, The Art of Computer programming, Vol. I, (Reading, Mass.: Addison-Wesley, 1968).

Digital Library

Google Scholar

Cited By

View all

Singhal LIyer MAdya S(2017)LSCProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062279(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062279
Kahng AReda S(2016)Digital Layout: PlacementElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-7(109-132)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-7
Subbaraj PSivakumar P(2011)Multithreaded memetic algorithm for VLSI placement problemProceedings of the Second international conference on Swarm, Evolutionary, and Memetic Computing - Volume Part I10.1007/978-3-642-27172-4_67(569-576)Online publication date: 19-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-27172-4_67
Show More Cited By

Index Terms

Clustering and linear placement
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing

Recommendations

An effective clustering algorithm for mixed-size placement
ISPD '07: Proceedings of the 2007 international symposium on Physical design

Placement is a crucial step for the VLSI circuit physical design and it has a deep impact on the overall circuit performance. Numerous clustering techniques have been proposed and applied to placement to deal with the increasing circuit sizes and ...
Simultaneous placement with clustering and duplication
DAC '04: Proceedings of the 41st annual Design Automation Conference

Clustering, duplication, and placement are critical steps in a cluster-based FPGA design flow. Clustering has a great impact on the wirelength, timing, and routability of a circuit. Logic duplication is an effective method for improving performance ...
Fine granularity clustering for large scale placement problems
ISPD '03: Proceedings of the 2003 international symposium on Physical design

In this paper we present a linear-time Fine Granularity Clustering (FGC) algorithm to reduce the size of large scale placement problems. FGC absorbs as many nets as possible into Fine Clusters. The absorbed nets are expected to be short in any good ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '72: Proceedings of the 9th Design Automation Workshop

June 1972

406 pages

ISBN:9781450374583

DOI:10.1145/800153

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 1972

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

113
Total Citations
View Citations
668
Total Downloads

Downloads (Last 12 months)57
Downloads (Last 6 weeks)8

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Singhal LIyer MAdya S(2017)LSCProceedings of the 54th Annual Design Automation Conference 201710.1145/3061639.3062279(1-6)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3061639.3062279
Kahng AReda S(2016)Digital Layout: PlacementElectronic Design Automation for IC Implementation, Circuit Design, and Process Technology10.1201/b19714-7(109-132)Online publication date: 14-Apr-2016
https://doi.org/10.1201/b19714-7
Subbaraj PSivakumar P(2011)Multithreaded memetic algorithm for VLSI placement problemProceedings of the Second international conference on Swarm, Evolutionary, and Memetic Computing - Volume Part I10.1007/978-3-642-27172-4_67(569-576)Online publication date: 19-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-27172-4_67
Serhal CChehab AKayssi A(2009)Clustering techniques for improving transient current testing2009 4th International Design and Test Workshop (IDT)10.1109/IDT.2009.5404121(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/IDT.2009.5404121
Fernau H(2008)Parameterized algorithmics for linear arrangement problemsDiscrete Applied Mathematics10.1016/j.dam.2008.05.008156:17(3166-3177)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.dam.2008.05.008
Shiraishi YSakemi JKutsuwada MTsukizoe A(2007)A transistor‐island growing algorithm in a CMOS cell pattern generationElectronics and Communications in Japan (Part III: Fundamental Electronic Science)10.1002/ecjc.443075050875:5(82-95)Online publication date: 22-Feb-2007
https://doi.org/10.1002/ecjc.4430750508
Nam GReda SAlpert CVillarrubia PKahng A(2006)A fast hierarchical quadratic placement algorithmIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2006.87007925:4(678-691)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2006.870079
Hu BMarek-Sadowska M(2006)Fine granularity clustering-based placementIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.82586823:4(527-536)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.825868
Cong JLim S(2006)Edge separability-based circuit clustering with application to multilevel circuit partitioningIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2004.82335323:3(346-357)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2004.823353
Odawara GHiraide TNishina O(2006)Partitioning and Placement Technique for CMOS Gate ArraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.1987.12702806:3(355-363)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.1987.1270280
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An effective clustering algorithm for mixed-size placement

Simultaneous placement with clustering and duplication

Fine granularity clustering for large scale placement problems