Article

Free access

Decomposition methods for library binding of speed-independent asynchronous designs

Authors:

Giovanni De MicheliAuthors Info & Claims

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

Pages 558 - 565

Published: 06 November 1994 Publication History

Abstract

We describe methods for decomposing gates within a speed-independent asynchronous design. The decomposition step is an essential part of the library binding process, and is used both to increase the granularity of the design for higher quality mapping and to ensure that the design can be implemented. We present algorithms for simple hazard-free gate decomposition, and show results which indicate that we can decompose most of the gates in our benchmark set by this simple method. We then extend these algorithms to work for those cases in which no simple decomposition exists.

References

[1]

P. Beerel and T. H.-Y. Meng, "Automatic gate-level synthesis of speed-independent circuits," in ICCAD, Proceedings of the International Conference on Computer-Aided Design, pages 581-586, Nov. 1992.

Digital Library

[2]

P. Beerel and T. H.-Y. Meng, "Logic transformations and observability don't cares in speed-independent circuits," in TAU, Aug. 1993.

[3]

T.-A. Chu, "Synthesis of self-timed VLSI circuits from graph-theoretic specifications," Technical Report MIT-LCS-TR-393, MIT, 1987.

Digital Library

[4]

W.S. Coates, A. L. Davis, and K. S. Stevens, "Automatic synthesis of fast compact self-timed control circuits," in IFIP Workshop on Asynchronous Circuits, Manchester, UK, 1993.

Digital Library

[5]

W.S. Coates, A. L. Davis, and K. S. Stevens, "The post office experience: Designing a large asynchronous chip," INTEGRATION, the VLSIjournal, 15(4):341-366, 1993.

Digital Library

[6]

K. Keutzer, "DAGON: Technology binding and local optimization by DAG matching," in 24th Design Automation Conference, pages 341-347, IEEE/ACM, 1987.

Digital Library

[7]

L. Lavagno and A. Sangiovanni-Vincentelli, Algorithms for Synthesis and Testing of Asynchronous Circuits, Kluwer Academic Publishers, 1993.

Digital Library

[8]

F. Mailhot and G. De Micheli, "Algorithms for technology mapping based on binary decision diagrams and on boolean operations,"IEEE Transactions on CAD/ICAS, pages 599-620, May 1993.

[9]

E.J. McCluskey, Logic Design Principles With Emphasis on Testable Semicustom Circuits, Prentice-Hall, 1986.

Digital Library

[10]

T.H. Meng, Synchronization Design for Digital Systems, Kluwer Academic, 1990.

[11]

S.M. Nowick and D. L. Dill, "Synthesis of asynchronous state machines using a local clock," in ICCD, Proceedings of the International Conference on Computer Design, pages 192-197, IEEE Computer Society Press, 1991.

Digital Library

[12]

J. K. Ousterhout, Tcl and the Tk Toolkit, Addison Wesley, 1993.

Digital Library

[13]

R. Rudell, Logic Synthesis for VLSI Design, PhD thesis, U. C. Berkeley, Apr. 1989, Memorandum UCB/ERL M89/49.

Digital Library

[14]

P. Siegel, Technology Mapping for Asynchronous Designs, PhD thesis, Stanford University, 1994.

Digital Library

[15]

P. Siegel, G. De Micheli, and D. Dill, "Automatic technology mapping for generalized fundamental-mode asynchronous designs," in DAC, Proceedings of the Design Automation Conference, pages 61- 67, June 1993.

Digital Library

[16]

S.H. Unger, Asynchronous Sequential Switching Circuits, New York: Wiley-Interscience, 1969.

Digital Library

[17]

V. I. Varshavsky, editor, Self-Timed Control of Concurrent Processes, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1990.

[18]

K. Yun and D. Dill, "Automatic synthesis of 3D asynchronous finite-state machines," in ICCAD, Proceedings of the International Conference on Computer-Aided Design, pages 576-580, Nov. 1992.

Digital Library

Cited By

Cortadella JKishinevsky MKondratyev ALavagno LYakovlev A(1997)Technology Mapping of Speed-Independent Circuits Based on Combinational Decomposition and ResynthesisProceedings of the 1997 European conference on Design and Test10.5555/787260.787643Online publication date: 17-Mar-1997
https://dl.acm.org/doi/10.5555/787260.787643
Cortadella JKishinevsky MKondratyev ALavagno LPastor EYakovlev AOtten RYasuura H(1997)Decomposition and technology mapping of speed-independent circuits using Boolean relationsProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266476(220-227)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266476
Beerel PYun KChou W(1996)Optimizing average-case delay in technology mapping of burst-mode circuitsProceedings of the 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems10.5555/785164.785216Online publication date: 18-Mar-1996
https://dl.acm.org/doi/10.5555/785164.785216
Show More Cited By

Index Terms

Decomposition methods for library binding of speed-independent asynchronous designs
1. Hardware
  1. Integrated circuits
    1. Logic circuits

Recommendations

Decomposition and technology mapping of speed-independent circuits using Boolean relations
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

Presents a new technique for the decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The proposed ...
Technology Mapping of Speed-Independent Circuits Based on Combinational Decomposition and Resynthesis
EDTC '97: Proceedings of the 1997 European conference on Design and Test

This paper presents a solution to the problem of sequential multi-level logic synthesis of asynchronous speed-independent circuits. The starting point is a technology-independent speed-independent circuit obtained using, e.g., the monotonous cover ...
Decomposition and technology mapping of speed-independent circuits using Boolean relations

This paper presents a new technique for decomposition and technology mapping of speed-independent circuits. An initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 1994

771 pages

ISBN:0897916905

Chairmen:
Jochen A. G. Jess
Eindhoven Univ. of Technology, Eindhoven, The Netherlands
,
Richard Rudell
Synopsys, Inc., Mountain View, CA

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS: Computer Society

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 06 November 1994

Check for updates

Qualifiers

Article

Conference

ICCAD '94

Sponsor:

SIGDA
IEEE-CS

ICCAD '94: International Conference on Computer Aided Design

November 6 - 10, 1994

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
167
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)5

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cortadella JKishinevsky MKondratyev ALavagno LYakovlev A(1997)Technology Mapping of Speed-Independent Circuits Based on Combinational Decomposition and ResynthesisProceedings of the 1997 European conference on Design and Test10.5555/787260.787643Online publication date: 17-Mar-1997
https://dl.acm.org/doi/10.5555/787260.787643
Cortadella JKishinevsky MKondratyev ALavagno LPastor EYakovlev AOtten RYasuura H(1997)Decomposition and technology mapping of speed-independent circuits using Boolean relationsProceedings of the 1997 IEEE/ACM international conference on Computer-aided design10.5555/266388.266476(220-227)Online publication date: 13-Nov-1997
https://dl.acm.org/doi/10.5555/266388.266476
Beerel PYun KChou W(1996)Optimizing average-case delay in technology mapping of burst-mode circuitsProceedings of the 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems10.5555/785164.785216Online publication date: 18-Mar-1996
https://dl.acm.org/doi/10.5555/785164.785216
Beerel PChou WYun KSymonds GNebel W(1996)A heuristic covering technique for optimizing average-case delay in the technology mapping of asynchronous burst-mode circuitsProceedings of the conference on European design automation10.5555/252471.252522(284-289)Online publication date: 20-Sep-1996
https://dl.acm.org/doi/10.5555/252471.252522

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents