Article

Free access

Regularity extraction via clan-based structural circuit decomposition

Authors:

Soha Hassoun,

Carolyn McCrearyAuthors Info & Claims

ICCAD '99: Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design

Pages 414 - 419

Published: 07 November 1999 Publication History

PDF eReader

Abstract

Identifying repeating structural regularities in circuits allows the minimization of synthesis, optimization, and layout efforts. We introduce in this paper a novel method for identifying a set of repeating circuit structures, referred to as templates, and we report on using an efficient binate cover solver to select an appropriate subset of templates with which to cover the circuit. Our approach is comprised of three steps. First, the circuit graph is decomposed in a hierarchical inclusion parse tree using a clan-based decomposition algorithm. This algorithm discovers clans, grouping of nodes in the circuit graph that have a natural affinity towards each other. Second, the parse tree nodes are classified into equivalence classes. Such classes represent templates suitable for circuit covering. The final step consists of using a binate cover solver to find an appropriate cover. The cover will consist of instantiated templates and gates that cannot be covered by any templates. We describe the results of applying this algorithm to several circuits, and show that the algorithm is effective in extracting structural regularity.

References

[1]

S. Arikati and R. Varadarajan. "A Signature Based Approach to Regularity Extraction". In IEEE International Conference on Computer-Aided Design, pages 542-5, 1997.

Digital Library

Google Scholar

[2]

A. Chowdhary, S. Kale, P. Saripella, N. Sehgal, and R. Gupta. "A General Approach for Regularity Extraction in Datapath Circuits". In IEEE International Conference on Computer-Aided Design, pages 332-339, 1998.

Digital Library

Google Scholar

[3]

M. Corazao, M. Khalaf, L. Guerra, M. Potkonjak, and J. Rabaey. "Perofrmance Optimization Using Ternplate Mapping for Datapath-Intensive High-level Synthesis". IEEE Transactions on Computer-Aided Design, 15(8):877-87, August 1996.

Digital Library

Google Scholar

[4]

O. Coudert and J. Madre. "New Ideas for Solving Covering Problems". In A CM-IEEE Design Automation Conference, pages 641-6, 1995.

Digital Library

Google Scholar

[5]

A. Deutz, A. Ehrenfeucht, and G. Rozenberg. "Clans and Regions in 2-Structures". Tehoretical Computer Science, (129):207-262, March 1994.

Digital Library

Google Scholar

[6]

T. Kutzschenbauch. "Logic Optimization Using Regularity Extraction". In "Proc. of the 1999 International Workshop on Logic Synthesis", 1999.

Google Scholar

[7]

C. McCreary, R. Chapman, and F.-S. Shieh. "Using Graph Parsing for Automatic Graph Drawing". IEEE Transactions on Systems, Man, and Cypernetics - Part A: Systems and Humans, 28(5):545-61, September 1998.

Digital Library

Google Scholar

[8]

C. McCreary and A. Reed. "A Graph Parsing Algorithm and Implementation". Technical Report TR-93- 04, Auburn University, Auburn, AL, 1993.

Digital Library

Google Scholar

[9]

R. Nijssen and J. Jess. "Two-Dimensional Datapath Regularity Extraction". In "Proc. of the 1996 A CM~SIGDA Physical Design Workshop", 1996.

Google Scholar

[10]

D. Rao and F. Kurdahi. "On Clustering for Maximal Regularity Extraction". IEEE Transactions on Computer-Aided Design, 12(8):1198 -1208, August 1993.

Digital Library

Google Scholar

Cited By

View all

Xiang HCho MRen HZiegler MPuri RKoh CSze C(2013)Network flow based datapath bit slicingProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451954(139-146)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451954
Chakrabarti AGodefroid PMin SYi W(2006)Software partitioning for effective automated unit testingProceedings of the 6th ACM & IEEE International conference on Embedded software10.1145/1176887.1176925(262-271)Online publication date: 22-Oct-2006
https://dl.acm.org/doi/10.1145/1176887.1176925
Das SKhatri SSapatnekar SWiesel M(2001)A regularity-driven fast gridless detailed router for high frequency datapath designsProceedings of the 2001 international symposium on Physical design10.1145/369691.369752(130-135)Online publication date: 1-Apr-2001
https://dl.acm.org/doi/10.1145/369691.369752
Show More Cited By

Index Terms

Regularity extraction via clan-based structural circuit decomposition

Recommendations

Extraction of functional regularity in datapath circuits

Datapath circuits exhibit a very high degree of regularity, which is exploited by designers to generate layouts with a high density and performance as well as to reduce the overall design effort. Regularity in a datapath circuit manifests itself at ...
Pairwise decomposition of toffoli gates in a quantum circuit
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

Quantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are ...
Proposed low power, high speed adder-based 65-nm Square root circuit

This paper focuses on the design of a 1-bit full adder circuit using Shannon's theorem and adder-based non-Restoring and Restoring Square Rooter circuits. The proposed adder and Square Rooter schematics were developed using DSCH2 CAD tool, and their ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '99: Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design

November 1999

613 pages

ISBN:0780358325

Publisher

IEEE Press

Publication History

Published: 07 November 1999

Check for updates

Qualifiers

Article

Conference

ICCAD '99

Sponsor:

IEEE-EDS
SIGDA
IEEE-CAS
IEEE-CS

ICCAD '99: The International Conference on Computer Aided Design.

November 7 - 11, 1999

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
149
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)9

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xiang HCho MRen HZiegler MPuri RKoh CSze C(2013)Network flow based datapath bit slicingProceedings of the 2013 ACM International symposium on Physical Design10.1145/2451916.2451954(139-146)Online publication date: 24-Mar-2013
https://dl.acm.org/doi/10.1145/2451916.2451954
Chakrabarti AGodefroid PMin SYi W(2006)Software partitioning for effective automated unit testingProceedings of the 6th ACM & IEEE International conference on Embedded software10.1145/1176887.1176925(262-271)Online publication date: 22-Oct-2006
https://dl.acm.org/doi/10.1145/1176887.1176925
Das SKhatri SSapatnekar SWiesel M(2001)A regularity-driven fast gridless detailed router for high frequency datapath designsProceedings of the 2001 international symposium on Physical design10.1145/369691.369752(130-135)Online publication date: 1-Apr-2001
https://dl.acm.org/doi/10.1145/369691.369752
Ye TDe Micheli GSentovich E(2000)Data path placement with regularityProceedings of the 2000 IEEE/ACM international conference on Computer-aided design10.5555/602902.602962(264-271)Online publication date: 5-Nov-2000
https://dl.acm.org/doi/10.5555/602902.602962

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

Extraction of functional regularity in datapath circuits

Pairwise decomposition of toffoli gates in a quantum circuit

Proposed low power, high speed adder-based 65-nm Square root circuit