Article

Free access

Geometric embeddings for faster and better multi-way netlist partitioning

Authors:

C. J. Alpert,

A. B. KahngAuthors Info & Claims

DAC '93: Proceedings of the 30th international Design Automation Conference

Pages 743 - 748

https://doi.org/10.1145/157485.165115

Published: 01 July 1993 Publication History

PDF eReader

References

[1]

J P. Benz~cri, "Construction d'une Classification Ascendante Ht~rarchique par la Rechereche en Chaine des Volsms R~clproques", m Les Cah~ers de l'Analyse des Donndes (VII)2, 1982, pp. 209-218.

Google Scholar

[2]

T. N Bin, "Improving the Performance of the Kermghan- Lln and Simulated Anneahng Graph Bmectlon Algorithms", in Proc A CMfIEEE Desagn Automat,on Conf., 1999, pp. 775-778.

Digital Library

Google Scholar

[3]

P. Brucker, "On the Complexity of Clustering Problems", m Opt~m~zatzon and Operations Research, 1977, pp 45-54

Google Scholar

[4]

P K. Chan, M. D F Schlag and J. Zien, "Spectral K-Way Ratio Cut Partitiomng and Clustering", to appear m Proc. Syrup. on Integrated Systems, Seattle, March 1993.

Digital Library

Google Scholar

[5]

T Feder and D H Greene, "Optimal Algorithms for Approximate Clustering", m Proc 20th Annual A CM Syrup Theory Computing, 1988, pp 434-444.

Digital Library

Google Scholar

[6]

C M Flduccla and R.M. Mattheyses, "A Linear Time Heumstic for Improving Network Partitions", m Proc. A CM/IEEE Des,gn Automation Conf., 1982, pp 175-18t

Digital Library

Google Scholar

[7]

T. F Gonzalez, "Clustering to Minimize the Maximum Intercluster Distance", in TheoretscaI Computer Scsence, 38, 1985, pp. 293-306.

Crossref

Google Scholar

[8]

A. Gu~noche, P. Hansen and B Jaumard, "Efficmnt Algorithms for Divisive Hierarchical Clustering with the Diameter Criterion", in Journal of Classification, 8, 1991, pp. 5-30. 1990.

Digital Library

Google Scholar

[9]

S. W. Hadley, B. L. Mark and A. Vanelli, "An Efficient Elgenvector Approach for Finding Netlist Partitions", in IEEE Trans. on CAD, 11(7), July 1992, pp. 885-892.

Digital Library

Google Scholar

[10]

L Hagen and A B Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", in IEEE Trans. on CAD 1I(9), Sept 1992, pp. 1074-1085.

Digital Library

Google Scholar

[11]

L. Hagen and A. B. Kahng, "A New Approach to Effective Circuit Clustering", in Proc. IEEE Intl. Conf. on Computer- A,ded Design, Santa Clara, Nov. 1992, pp. 422-427.

Digital Library

Google Scholar

[12]

K M Hall, "An r-dimensional Quadratic Placement Algorithm", in Manag. Sc, 17, 1970, pp.219-229.

Digital Library

Google Scholar

[13]

J. Hershberger, "Minimizing the Sum of Diameters Efficmntly" in Proc, 3rd Canadian Conference on Computational Geometry, 1991, pp 62-65.

Google Scholar

[14]

S. C. Johnson, "Hierarchical Clustering Schemes", in Psychometmka 32(3), 1967, pp 241-254.

Crossref

Google Scholar

[15]

T Lengauer, Comb:natomal Algomthms for Integrated Circuit Layout, Wiley-Teubner, 1990

Digital Library

Google Scholar

[16]

N. Megiddo and K. J. Supowit, "On the Complexity of Some Common Geometric Location Problems", in Szam Journal of Computzng, 13(1), 1984, pp. 182-196.

Google Scholar

[17]

F. P. Prep,rata and M. I. Shamos, Computational Geometry, Springer Verlag, New York, NY, 1985.

Google Scholar

[18]

L.A. Sanchis, "Multiple-way Network Partitioning", In IEEE Trans. on Computers, 38, 1989, pp. 62-81.

Digital Library

Google Scholar

[19]

D G. Schweikert and B W Kernighan, "A Proper Model for the Partitioning of Electrtcal Circmts", in Proc. Design Automation Conf., 1972, pp. 57-62.

Digital Library

Google Scholar

[20]

Y C. We1 and C K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs", m IEEE Trans. on CAD 10(7), July 1991, pp 911-921.

Digital Library

Google Scholar

[21]

C. W. Yeh, C. K. Cheng and T. T. Lm, "A General Purpose Multiple Way Partitioning Algorithm", in Proc. A CMfIEEE Deszgn Automation Conf., June 199I, pp. 421-426.

Digital Library

Google Scholar

[22]

C. W. Yeh, C. K. Cheng and T. T. Lm, "A Probabilistic Multicommodity-Flow Solution to Circuit Clustering Problems", in Proc. IEEE Intl. Conf. on Computer-A~ded Design, Santa Clara, November 1992, pp. 428-431.

Digital Library

Google Scholar

[23]

J. Zien, "Spectral K-Way Ratio Cut Graph Partitiomng", M.S. Thesis, Computer Engineering Dept, UC Santa Cruz, March 1993

Google Scholar

Cited By

View all

Cakir BMalik S(2019)Revealing Cluster Hierarchy in Gate-level ICs Using Block Diagrams and Cluster Estimates of Circuit EmbeddingsACM Transactions on Design Automation of Electronic Systems10.1145/332908124:5(1-19)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1145/3329081
Cakir BMalik S(2018)Reverse Engineering Digital ICs through Geometric Embedding of Circuit GraphsACM Transactions on Design Automation of Electronic Systems10.1145/319312123:4(1-19)Online publication date: 18-Jul-2018
https://dl.acm.org/doi/10.1145/3193121
Srinivasan SKamakoti VBhattacharya A(2013)A Novel Algorithm for Fast Synthesis of DNA Probes on MicroarraysACM Journal on Emerging Technologies in Computing Systems10.1145/2422094.24220959:1(1-17)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1145/2422094.2422095
Show More Cited By

Index Terms

Geometric embeddings for faster and better multi-way netlist partitioning
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Partitioning and floorplanning
  2. Very large scale integration design
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Multi-way VLSI circuit partitioning based on dual net representation
ICCAD '94: Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design

In this paper, we study the area-balanced multi-way partitioning problem of VLSI circuits based on a new dual netlist representation named the hybrid dual netlist (HDN). Given a netlist, we first compute a K-way partition of the nets based on the HDN ...
Application of fusion-fission to the multi-way graph partitioning problem
PPAM'07: Proceedings of the 7th international conference on Parallel processing and applied mathematics

This paper presents an application of the Fusion-Fission method to the multi-way graph partitioning problem. The Fusion-Fission method was first designed to solve the normalized cut partitioning problem. Its application to the multi-way graph ...
Multi-way graph and hypergraph partitioning

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '93: Proceedings of the 30th international Design Automation Conference

July 1993

768 pages

ISBN:0897915771

DOI:10.1145/157485

Chairman:
Alfred E. Dunlop
AT&T Bell Labs., Murray Hill, NJ

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: 01 July 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC93

Sponsor:

EDAC
SIGDA
IEEE-CAS

DAC93: The 30th ACM/IEEE Design Automation Conference

June 14 - 18, 1993

Texas, Dallas, USA

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

53
Total Citations
View Citations
333
Total Downloads

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

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cakir BMalik S(2019)Revealing Cluster Hierarchy in Gate-level ICs Using Block Diagrams and Cluster Estimates of Circuit EmbeddingsACM Transactions on Design Automation of Electronic Systems10.1145/332908124:5(1-19)Online publication date: 12-Jun-2019
https://dl.acm.org/doi/10.1145/3329081
Cakir BMalik S(2018)Reverse Engineering Digital ICs through Geometric Embedding of Circuit GraphsACM Transactions on Design Automation of Electronic Systems10.1145/319312123:4(1-19)Online publication date: 18-Jul-2018
https://dl.acm.org/doi/10.1145/3193121
Srinivasan SKamakoti VBhattacharya A(2013)A Novel Algorithm for Fast Synthesis of DNA Probes on MicroarraysACM Journal on Emerging Technologies in Computing Systems10.1145/2422094.24220959:1(1-17)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1145/2422094.2422095
Shuiping LXiaoxue W(2010)A global method for the limited K‐partitioning of hypergraphs representing optimal design problems in complex machine systemsKybernetes10.1108/0368492101104675339:6(980-989)Online publication date: 15-Jun-2010
https://doi.org/10.1108/03684921011046753
Zhou XWang YYang H(2009)DCCB and SCC based fast circuit partition algorithm for parallel SPICE simulation2009 IEEE 8th International Conference on ASIC10.1109/ASICON.2009.5351211(1247-1250)Online publication date: Oct-2009
https://doi.org/10.1109/ASICON.2009.5351211
Kahng AMandoiu IReda SXu XZelikovsky A(2006)Computer-Aided Optimization of DNA Array Design and ManufacturingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85594025:2(305-320)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.855940
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
Charles J. Alpert (2006)Spectral Partitioning: The More Eigenvectors, The Better32nd Design Automation Conference10.1109/DAC.1995.250089(195-200)Online publication date: Dec-2006
https://doi.org/10.1109/DAC.1995.250089
Bui TMoon B(2006)GRCAIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.70071817:3(193-204)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.700718
Hagen LHuang DKahng A(2006)On implementation choices for iterative improvement partitioning algorithmsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/43.66268216:10(1199-1205)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/43.662682
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

Multi-way VLSI circuit partitioning based on dual net representation

Application of fusion-fission to the multi-way graph partitioning problem

Multi-way graph and hypergraph partitioning