More Web Proxy on the site http://driver.im/

Article

Free access

Asynchronous interface specification, analysis and synthesis

Authors:

Michael Kishinevsky,

Jordi Cortadella,

Alex KondratyevAuthors Info & Claims

DAC '98: Proceedings of the 35th annual Design Automation Conference

Pages 2 - 7

https://doi.org/10.1145/277044.277046

Published: 01 May 1998 Publication History

Abstract

Interfaces, by nature, are often asynchronous since they serve for connecting multiple distributed mod ules/agents without common clock. However, the most recent developments in the the ory of asynchronous design in the areas of specifications, mo dels, analysis, verification, synthesis, technology mapping, timing optimization and performanc e analysis are not widely known and r arely accepted by industry.

The go al of this tutorial is to fill this gap and to present an overview of one p opular systematic design methodology for design of asynchronous interface controllers. This metho dology is based on using P etri nets (PN) a formal mo del that, from the engine ering standpoint, is a formalization of timing diagrams (waveforms) and from the system designer standpoint is a concurrent state machine, in which lo cal comp onents can perform indep endent or interdependent concurrent actions, changing their local states asynchronously. We will introduce this mo del informally b ased on a simple example: a VME-bus controller serving reads from a devic e to a bus and writes f rom the bus into the devic e.

References

[1]

P.A. Beerel and T. H-Y. Meng. Automatic gate-level synthesis of speed-independent circuits. In Proceedings of the International Conference on Computer-Aided Design, November 1992.]]

Digital Library

[2]

Kees van Berkel. Handshake Circuits: an Asynchronous Architecture for VLSI Pro~, volume 5 of International Series on Parallel Computation. Cambridge Univer~ sity Press, 1993.]]

Digital Library

[3]

Randal Bryant. Symbolic boolean manipulation with or. dered binary-decision diagmn~. ACM Computing Surveys, 24(3):293-318, September 1992.]]

Digital Library

[4]

S. Burns. General conditions for the decomposition of state holding elements. In International Symposium on Advanced Research in Asynchronous Circuits and Systems, Aizu, Japan, March 1996.]]

Digital Library

[5]

A Cortadella, M. Kishinevsky, A. Kondratyev, I~ Lavagno, E. Pastor, and A. Yakovlev. Decomposition and tedmology mapping of speed-independent circuits using boolean relations. In Pro~dings of the International Conference on Computer-Aided Design, pages 220-227, November 1997.]]

Digital Library

[6]

A Cortadella, M. Kishinevsky, A. Kondratyev, I~ Lavagno, and A. Yakovlev. A region-based theory for state assignment in speed-independent circuits. IEEE Transactions on Computer-Aided Design, 16(8):793-812, August 1997.]]

Digital Library

[7]

A Cortadella, M. Kishinevsky, A. Kondratyev, I~ Lavagno, and A. Yakovlev. Synthesis of control circuits from STG specifications. In handouts of the Summer School on Asynchronous Circuit Design, August 1997. h~tp://yew, lsi. upc. es/' j ordic/petrify/ref s/ summer97, ps. gz.]]

[8]

A Cortadella, M. Kishinevsky, I~ Lavagno, and A. Yakovlev. Synthesizing Petri nets from state-based models. In Proceedings of the International Conference on Computer-Aided Design, pages 164-171, November 1995.]]

Digital Library

[9]

A Desel and A Esparza. he-choice Petri Nets, volume 40 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1995.]]

Digital Library

[10]

David I~ Dill. Trace Theory for Automatic Hierarchical Verification of Speed-Independent Circuits. ACM Distinguished Dissertations. MIT Press, 1989.]]

Digital Library

[11]

P. Godefroid. Using partial orders to improve automatic ve~ ification methods. In E.M Clarke and R.P. Kurshan, editors, Proc. International Workshop on Computer Aided Verification, 1990. DIMACS Series in Discrete Mathematica and Theoretical Computer Science, 1991, pages 321-340.]]

Digital Library

[12]

H. Hulgaard, S. M. Bums, T. Amon, and G. Borriello. An algorithm for exact bounds on the time separation of events in concurrenct systems. IEEE Transactions on Computers, 44( 11):1306-1317, November 1995.]]

Digital Library

[13]

M. Kishinevsky, ~{ Cortadella, A. Kondratyev, and I. Lavag~o. Asynchronous interface specification, analysis and synthesis. Technical Report LSI-98-14-R, Technical University of Catalonia, March 1998. ht~p://wue.lsi.upc, es/dept/techreps/ps/R98-14, p s.gz.]]

Digital Library

[14]

M. A. Kishinevsky, A. Y. Kondratyev, A. R. Taubin, and V. I. Varshavsky. Concurrent Hardware. The Theory and Practice of Self-Timed Design. John Wiley and Sons Ltd., 1994.]]

Digital Library

[15]

A. Kondratyev, M. Kishinevsky, B. Lin, P. Vanbekbergen, and A. Yakovlev. Basic gate implementation of speedindependent circuits. In Proceedings of the Design Automation Conference, pages 56-62, Jhne 1994.]]

Digital Library

[16]

A. Kondratyev, M. Kishinevsky, A. Taubin, and S. Tern Analysis of Petri nets by ordering relations in reduced unfoldings. Formal Methods in System Design, 12(1):5-38, 1997.]]

Digital Library

[17]

1. Lavagno and A. Sangiovanni-Vincentelli. Algorithms jor synthesis and testing of asynchronous circuits. Kluwer Academic Publishers, 1993.]]

Digital Library

[18]

A. Martim Program~ in VLSh From communicating processes to delay-insensitive circuits. In C. A. R. Hoare, editor, Developments in Concurrency and Communications, The UT Year of Prong Series. Addison-Wesley, 1990.]]

Digital Library

[19]

K. McMillan. Symbolic Model Checking. Kluwer Academic Publishers, 1993.]]

Digital Library

[20]

David E. Muller and W. S. Bmtky. A theory of asynchronous circuits. In Proceedings of an International Symposium on the Theory of Switching, pages 204-243. Harvard University Press, April 1959.]]

[21]

T. Murata. Petri Nets: Properties, analysis and applications. Proceedings oj the IEEE, pages 541-580, April 1989.]]

[22]

Chris,I Myers and Teresa H.-Y. Meng. Synthesis of timed asynchronous circuits. IEEE Transactions on VLSI Systems, 1(2):106-119, Jhne 1993.]]

Digital Library

[23]

Steven M. Nowick and David 1. Dill. Exact two-level rainimization of hazard-free logic with multiple-input changes. IEEE Transactions on Computer-Aided Design, 14(8):986- 997, August 1995.]]

Digital Library

[24]

Oriol Roig, Jordi Cortadella, and Enric Pastor. Verification of asynchronous circuits by BDD-based model checking of Petri nets. In 16th International Conference on the Application and Theory of Petri Nets, volume 815 of Lecture Notes in Computer Science, pages 374-391,1995.]]

Digital Library

[25]

S. H. Unger. Asynchronous Sequential Switching Circuits. Wiley-Interscience, John Wiley & Sons, Ina, New York, 1969.]]

Digital Library

[26]

Antti Valmari. Stubborn sets for reduced state space generation~ Lecture Notes in Computer Science; Advances in Petri Nets 1990, 483:491-515, 1991.]]

Digital Library

[27]

P. Vanbekbergen, B. Lin, G. Goossens, and H. De Marl A generalized state assignment theory for transformations on Signal Transition Graphs. Journal of VLSI Signal Processing, 7( 1-2):101-116, 1994.]]

Digital Library

[28]

Peter Vanbekbergen, Albert Wand, and Kurt Keutzer. A design and validation system for asynchronous ciz,~uits. InProc. ACM/IEEE Design Automation Conference, &me 1995.]]

Digital Library

[29]

If, Y. Yun and D. L. Dill. Automatic synthesis of 3D asynchronous state machines. In Proceedings of the International Conference on Computer-Aided Design, November 1992.]]

Digital Library

Cited By

Akgun O(2018)An Asynchronous Pipelined Time-to-Digital Converter Using Time-Domain Subtraction2018 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2018.8351554(1-5)Online publication date: May-2018
https://doi.org/10.1109/ISCAS.2018.8351554
Kao C(2012)Interface circuit synthesis of system-on-chipInternational Journal of Electronics10.1080/00207217.2011.65169299:7(957-970)Online publication date: Jul-2012
https://doi.org/10.1080/00207217.2011.651692
Venkataramani GGoldstein SGebotys CMartin G(2008)Slack analysis in the system design loopProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450189(231-236)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450189
Show More Cited By

Index Terms

Asynchronous interface specification, analysis and synthesis

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '98: Proceedings of the 35th annual Design Automation Conference

May 1998

820 pages

ISBN:0897919645

DOI:10.1145/277044

Chairmen:
Basant R. Chawla
Lucent Technologies, Warren, NJ
,
Randal E. Bryant
Carnegie Mellon Univ., Pittsburgh, PA
,
Jan M. Rabaey
Univ. of California, Berkeley
,
Editor:
M. J. Irwin

Copyright © 1998 ACM.

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]

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC98

Sponsor:

EDAC
SIGDA
IEEE-CS

DAC98: The 35th ACM/IEEE-CAS/EDAC Design Automation Conference

June 15 - 19, 1998

California, San Francisco, 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

12
Total Citations
View Citations
114
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Akgun O(2018)An Asynchronous Pipelined Time-to-Digital Converter Using Time-Domain Subtraction2018 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2018.8351554(1-5)Online publication date: May-2018
https://doi.org/10.1109/ISCAS.2018.8351554
Kao C(2012)Interface circuit synthesis of system-on-chipInternational Journal of Electronics10.1080/00207217.2011.65169299:7(957-970)Online publication date: Jul-2012
https://doi.org/10.1080/00207217.2011.651692
Venkataramani GGoldstein SGebotys CMartin G(2008)Slack analysis in the system design loopProceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis10.1145/1450135.1450189(231-236)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1450135.1450189
Dick RJha NDick RJha N(2008)MOCSYN: Multiobjective Core-Based Single-Chip System SynthesisDesign, Automation, and Test in Europe10.1007/978-1-4020-6488-3_22(291-311)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6488-3_22
Radcliffe PXinghuo Yu (2007)A New Time Independent Asynchronous Protocol and Its ApplicationsIEEE Transactions on Industrial Informatics10.1109/TII.2007.8984393:2(143-153)Online publication date: May-2007
https://doi.org/10.1109/TII.2007.898439
Radcliffe PYu X(2006)A Novel Time Independent Asynchronous Communication Protocol&Its ApplicationsIECON 2006 - 32nd Annual Conference on IEEE Industrial Electronics10.1109/IECON.2006.347420(3574-3579)Online publication date: Nov-2006
https://doi.org/10.1109/IECON.2006.347420
Varea MAl-Hashimi BCortés LEles PPeng ZHenkel JHu XGupta RParameswaran S(2002)Symbolic model checking of Dual Transition Petri NetsProceedings of the tenth international symposium on Hardware/software codesign10.1145/774789.774799(43-48)Online publication date: 6-May-2002
https://dl.acm.org/doi/10.1145/774789.774799
Starodoubtsev NBystrov SGoncharov MKlotchkov ISmirnov A(2001)Towards synthesis of monotonic asynchronous circuits from signal transition graphsProceedings Second International Conference on Application of Concurrency to System Design10.1109/CSD.2001.981775(179-188)Online publication date: 2001
https://doi.org/10.1109/CSD.2001.981775
Stevens KRotem SBurns SCortadella JGinosar RKishinevsky MRoncken M(1999)CAD directions for high performance asynchronous circuitsProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.309893(116-121)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/309847.309893
Dick RJha N(1999)MOCSYNProceedings of the conference on Design, automation and test in Europe10.1145/307418.307502(55-es)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1145/307418.307502
Show More Cited By

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