Article

Free access

Net partitions yield better module partitions

Authors:

J. Cong,

L. Hagen,

A. KahngAuthors Info & Claims

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

Pages 47 - 52

Published: 01 July 1992 Publication History

PDF eReader

References

[1]

E. R. Barnes, "An Algorithm for Partitioning the Nodes of a Graph", SIAM J. AIg. Disc. Meth. 3(4) (1982), pp. 541-550

Crossref

Google Scholar

[2]

J. Blanks, "Partitiomng by Probability Condensation", Proc. ACM/IEEE Design Automatton Conf., 1989, pp 758-761

Digital Library

Google Scholar

[3]

B.B. Boppana, "Eigenvalues and Graph Bisection: An Average-Case Analysis", IEEE Syrup. on Foundatzons of Computer Scsenee, 1987, pp. 280-285.

Google Scholar

[4]

T. N. Bui, S. Chaudhuri, F. T. Leighton and M Sipser, "Graph Bisection Algorithms with Good Average Case Behavior", Combinatomca 7(2) (1987), pp. 171-191.

Digital Library

Google Scholar

[5]

J. Cong, L. Hagen and A. B. Kahng, "Net Partitions Yield Better Module Partitions", UCLA CS Dept. TR-910075, November 1991.

Google Scholar

[6]

W.E. Donath, "Logic Partitioning", in Physical Des,gn Automatson of VLSI Systems, B. Press and M. Lorenzetti, eds., Benjamin/Cummings, 1988, pp. 65-86.

Google Scholar

[7]

W.E. Donath and A.J. Hoffman, "Lower Bounds for the Partitioning of Graphs", IBM J. Res. Dev. (1973), pp. 420-425.

Digital Library

Google Scholar

[8]

C.M Flduccia and P~.M. Mattheyses, "A Linear Time Heuristic for Improving Network Partitions", ACM/IEEE Deszgn Au. tomatton Conf., 1982, pp. 175-181.

Digital Library

Google Scholar

[9]

J. Frankle and R.M. Karp, "Circuit Placement and Cost Bounds by Eigenvector Decomposition", IEEE Intl. Conf. on Computer-Azded Deszgn, 1986, pp. 414-417

Google Scholar

[10]

G. Golub and C. Van Loan, Matrzx Computatzons, Baltimore, Johns Hopkins Univermty Press, 1983.

Google Scholar

[11]

L. Hagen and A B Kahng, "Fast Spectral Methods for Ratio Cut Partitioning and Clustering", Proc. IEEE Intl. Conf. on Computer-Aided Deszgn, Santa Clara, 1991, pp. 10-13.

Google Scholar

[12]

L. Hagen and A. B. Kahng, "New Spectral Methods for Ratio Cut Partitioning and Clustering", to appear in IEEE Transactzons on CAD; also available as UCLA CSD TR-910073.

Digital Library

Google Scholar

[13]

K. M. Hall, "An r-dlmenmonal Quadratic Placement Algorithm", Management Sczence 17(1970), pp 219-229

Crossref

Google Scholar

[14]

F. Harary, Graph Theory, Addison-Wesley, 1969.

Google Scholar

[15]

N. Hasan and C L. Liu, "Minimum Fault Coverage in Reconfigurable Arrays", Proc. 18th IEEE Intl. Syrup. on Fault- Tolerant Computzng Systems, 1988, pp. 348-353

Crossref

Google Scholar

[16]

A. B. Kahng, "Fast Hypergraph Partition", Proc. ACM/IEEE Design Automation Conf., 1989, pp. 762-766

Digital Library

Google Scholar

[17]

J. M. Kleinhans, G. Sigl, F. M. Johannes and K. J Antreich, "GORDIAN: VLSI Placement by Quadratm Programming and Slicmg Optimizatmn", IEEE Trans. on CAD 10(3) (1991), pp. 356-365.

Digital Library

Google Scholar

[18]

T. Lengauer, Combznatorzal Algorzthms for Integrated Csrcuzt Layout, Wfley-Teubner, 1990.

Digital Library

Google Scholar

[19]

C. L. Liu, Introductzon to Combznatorzat Mathematzcs, McGraw-Hill, 1968.

Google Scholar

[20]

L T. Pillage and R. A. Rohrer, "A Quadratm Metric with a Simple Solution Scheme for Initial Placement", Proc. A CM/IEEE Deszgn Automatzon Conf., 1988, pp. 324-329.

Digital Library

Google Scholar

[21]

R S. Tsay and E; S Kuh, "A Unified Approach to Partitmmng and Placement", Prznceton Conf. on Inf. and Comp., 1986

Google Scholar

[22]

Y. C. Wei, "Circmt Partitioning and Its Apphcatmns to VLSI Designs", Ph.D. Thesis, UCSD CSE Dept., September 1990.

Digital Library

Google Scholar

[23]

Y. C. Wei and C. K. Cheng, "Ratio Cut Partitioning for Hierarchical Designs", IEEE Trans. on CAD, July 1991, pp. 911- 921

Digital Library

Google Scholar

[24]

C. W Yeh, C K Cheng and T. T. Lin, "A GenerM Purpose Multiple Way Partltmnmg Algorithm", Proc. A CM/IEEE Deszgn Automatzon Conf., June 1991, pp. 421-426

Digital Library

Google Scholar

Cited By

View all

Gill SChandel RChandel A(2012)Netlist bipartitioning using particle swarm optimisation techniqueInternational Journal of Artificial Intelligence and Soft Computing10.1504/IJAISC.2012.0481783:1(1-15)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1504/IJAISC.2012.048178
Tan SShi C(2003)Balanced multi-level multi-way partitioning of analog integrated circuits for hierarchical symbolic analysisIntegration, the VLSI Journal10.1016/S0167-9260(03)00002-634:1-2(65-86)Online publication date: 1-May-2003
https://dl.acm.org/doi/10.1016/S0167-9260%2803%2900002-6
Alupoaei SKatkoori S(2002)Net Clustering Based Macrocell PlacementProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835380Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835380
Show More Cited By

Index Terms

Net partitions yield better module partitions

Recommendations

Judicious k-partitions of graphs

Judicious partition problems ask for partitions of the vertex set of graphs so that several quantities are optimized simultaneously. In this paper, we answer the following judicious partition question of Bollobas and Scott [B. Bollobas, A.D. Scott, ...
M-partitions: optimal partitions of weight for one scale pan

An M-partition of a positive integer m is a partition with as few parts as possible such that any positive integer less than m has a partition made up of parts taken from that partition of m. This is equivalent to partitioning a weight m so as to be ...
The boolean hierarchy of NP-partitions

We introduce the boolean hierarchy of k-partitions over NP for k>=3 as a generalization of the boolean hierarchy of sets (i.e., 2-partitions) over NP. Whereas the structure of the latter hierarchy is rather simple the structure of the boolean hierarchy ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

July 1992

752 pages

ISBN:089791516X

Chairman:
Daniel G. Schweikert
Cadence Design Systems, Inc., San Jose, CA

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 1992

Check for updates

Qualifiers

Article

Conference

DAC92

Sponsor:

EDAC
SIGDA
IEEE-CAS
IEEE-CS

DAC92: The 29th ACM/IEEE-CS Design Automation Conference

June 8 - 12, 1992

California, Anaheim, 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

14
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gill SChandel RChandel A(2012)Netlist bipartitioning using particle swarm optimisation techniqueInternational Journal of Artificial Intelligence and Soft Computing10.1504/IJAISC.2012.0481783:1(1-15)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1504/IJAISC.2012.048178
Tan SShi C(2003)Balanced multi-level multi-way partitioning of analog integrated circuits for hierarchical symbolic analysisIntegration, the VLSI Journal10.1016/S0167-9260(03)00002-634:1-2(65-86)Online publication date: 1-May-2003
https://dl.acm.org/doi/10.1016/S0167-9260%2803%2900002-6
Alupoaei SKatkoori S(2002)Net Clustering Based Macrocell PlacementProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835380Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835380
Mak WWong DRutenbar ROtten R(1997)Minimum replication min-cut partitioningProceedings of the 1996 IEEE/ACM international conference on Computer-aided design10.5555/244522.244557(205-210)Online publication date: 1-Jan-1997
https://dl.acm.org/doi/10.5555/244522.244557
Ober UHerpel J(1996)Hierarchical Partitioning in a Rapid Prototyping EnvironmentProceedings of the 7th IEEE International Workshop on Rapid System Prototyping (RSP '96)10.5555/827259.828073Online publication date: 19-Jun-1996
https://dl.acm.org/doi/10.5555/827259.828073
Agrawal PNarendran BShivakumar N(1996)Multi-way partitioning of VLSI circuitsProceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication10.5555/525699.834704Online publication date: 3-Jan-1996
https://dl.acm.org/doi/10.5555/525699.834704
Eben-Chaime MTovey CAmmons J(1996)Circuit Partitioning Via Set Partitioning and Column GenerationOperations Research10.1287/opre.44.1.6544:1(65-76)Online publication date: 1-Feb-1996
https://dl.acm.org/doi/10.1287/opre.44.1.65
Yang HWong DRudell R(1995)New algorithms for min-cut replication in partitioned circuitsProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.224883(216-222)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.224883
Ober UGlesner MMusgrave G(1995)Multiway netlist partitioning onto FPGA-based board architectureProceedings of the conference on European design automation10.5555/224270.224309(150-155)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224270.224309
Cong JLabio WShivakumar NJess JRudell R(1994)Multi-way VLSI circuit partitioning based on dual net representationProceedings of the 1994 IEEE/ACM international conference on Computer-aided design10.5555/191326.191357(56-62)Online publication date: 6-Nov-1994
https://dl.acm.org/doi/10.5555/191326.191357
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

Judicious k-partitions of graphs

M-partitions: optimal partitions of weight for one scale pan

The boolean hierarchy of NP-partitions