Article

Free access

A proper model for the partitioning of electrical circuits

Authors:

D. G. Schweikert,

B. W. KernighanAuthors Info & Claims

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

Pages 57 - 62

https://doi.org/10.1145/800153.804930

Published: 26 June 1972 Publication History

PDF eReader

Abstract

Partitioning algorithms for electrical circuits are often based on the heuristic manipulation of a simple element-to-element interconnection matrix. However, the element-to-element interconnection matrix does not properly represent an electrical interconnection, or “net”, among more than two elements. This paper expands on several aspects of the discrepancy: 1) its source, 2) the circumstances under which it is likely to be significant, and its magnitude for typical circuits, and 3) the comparative difficulty and expense of using a more appropriate representation.

A physically correct “net-cut” model is presented. This model is computationally straightforward and is easily adapted to the typical heuristic solution strategies. The “net-cut” model is coupled with the Kernighan-Lin partitioning algorithm [3]; using the same algorithm, comparisons with the “edge-cut” model demonstrate that the correct model reduces net-cuts by 19 to 50% for four digital logic circuits.

References

[1]

M. Hanan and J. M. Kurtzberg, A review placement and quadratic assignment problems. IBM Report RC-3046, 20 April 1970. (This report was the basis of a tutorial given by Hanan at the 8th Design Automation Workshop, June 1971, but did not appear in the Proceedings.)

Google Scholar

[2]

R. A. Rutman, An algorithm for placement of interconnected elements based on minimum wire length. Proc. SJCC (1964), 477-491.

Digital Library

Google Scholar

[3]

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. Feb. 1970, pp. 291-308. U. S. Patent 3,617,714 (Nov. 1971).

Google Scholar

[4]

A. H. Scheinman, Private communication.

Google Scholar

Cited By

View all

Gottesbüren LHeuer TMaas NSanders PSchlag S(2024)Scalable High-Quality Hypergraph PartitioningACM Transactions on Algorithms10.1145/362652720:1(1-54)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3626527
Schlag SHeuer TGottesbüren LAkhremtsev YSchulz CSanders P(2023)High-Quality Hypergraph PartitioningACM Journal of Experimental Algorithmics10.1145/352909027(1-39)Online publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1145/3529090
Deng KRen KZhu MSong J(2020)A Data and Task Co-Scheduling Algorithm for Scientific Cloud WorkflowsIEEE Transactions on Cloud Computing10.1109/TCC.2015.25117458:2(349-362)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TCC.2015.2511745
Show More Cited By

Index Terms

A proper model for the partitioning of electrical circuits
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits

We present a new complexity measure for Boolean functions based on partitions of combinatorial circuits into subcircuits, and give upper and lower bounds on the complexity for Boolean functions. Roughly speaking, for a function g whose range is the set ...
Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [Fidducia and Mattheyses 1982] and Krishnamurthy's Look-Ahead (LA) algorithm [Krishnamurthy 1984], are widely used in VLSI CAD applications, ...
Multi-way partitioning of VLSI circuits
VLSID '96: Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication

Partitioning is one of the critical phases of hierarchical design processes like VLSI design. Good partitioning techniques can positively influence the performance and cost of a VLSI product. This paper proposes a partitioning algorithm with a new cost ...

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

141
Total Citations
View Citations
1,171
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gottesbüren LHeuer TMaas NSanders PSchlag S(2024)Scalable High-Quality Hypergraph PartitioningACM Transactions on Algorithms10.1145/362652720:1(1-54)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3626527
Schlag SHeuer TGottesbüren LAkhremtsev YSchulz CSanders P(2023)High-Quality Hypergraph PartitioningACM Journal of Experimental Algorithmics10.1145/352909027(1-39)Online publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1145/3529090
Deng KRen KZhu MSong J(2020)A Data and Task Co-Scheduling Algorithm for Scientific Cloud WorkflowsIEEE Transactions on Cloud Computing10.1109/TCC.2015.25117458:2(349-362)Online publication date: 1-Apr-2020
https://doi.org/10.1109/TCC.2015.2511745
Pavithra Guru RVaithianathan V(2020)An efficient VLSI circuit partitioning algorithm based on satin bowerbird optimization (SBO)Journal of Computational Electronics10.1007/s10825-020-01491-9Online publication date: 18-Apr-2020
https://doi.org/10.1007/s10825-020-01491-9
Heuer TSanders PSchlag S(2019)Network Flow-Based Refinement for Multilevel Hypergraph PartitioningACM Journal of Experimental Algorithmics10.1145/332987224(1-36)Online publication date: 5-Sep-2019
https://dl.acm.org/doi/10.1145/3329872
Ghoshdastidar DDukkipati A(2017)Uniform hypergraph partitioningThe Journal of Machine Learning Research10.5555/3122009.315300618:1(1638-1678)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3153006
Nguyen VKirner R(2016)Throughput-Driven Partitioning of Stream Programs on Heterogeneous Distributed SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.241672627:3(913-926)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2416726
Deveci MRajamanickam SDevine KCatalyurek U(2016)Multi-JaggedIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2015.241254527:3(803-817)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1109/TPDS.2015.2412545
Nie TLu ZZhou L(2016)Fingerprinting methods for intellectual property protection using constraints in circuit partitioningIET Circuits, Devices & Systems10.1049/iet-cds.2015.003610:3(237-243)Online publication date: 1-May-2016
https://doi.org/10.1049/iet-cds.2015.0036
Sangwan DVerma SKumar R(2014)An Efficient Approach to VLSI Circuit Partitioning Using Evolutionary AlgorithmsProceedings of the 2014 International Conference on Computational Intelligence and Communication Networks10.1109/CICN.2014.195(925-929)Online publication date: 14-Nov-2014
https://dl.acm.org/doi/10.1109/CICN.2014.195
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Complexity Based on Partitioning of Boolean Circuits and their Relation to Multivalued Circuits

Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

Multi-way partitioning of VLSI circuits