Asynchronous Circuit Design
Asynchronous Circuit DesignA TutorialJens Sparsø
iAsynchronous circuit designA TutorialJens SparsøTechnical University of Denmarkc 2006 Jens Sparsø, Technical University of Denmark.Copyright All rights reserved.The material protected by this copyright notice may be used unmodified andin its entirety for non-commercial educational purposes only. For such usepermission is granted to distribute printed or electronic copies.All other use requires the written permission of the author.Copies may be downloaded from the following url:http://www.imm.dtu.dk/pubdb/views/publication details.php?id 855or http://www.imm.dtu.dk/ jsp/ and follow link to download.
iiASYNCHRONOUS CIRCUIT DESIGN
iiiForewordThis material in this booklet originally appeared as:J. Sparsø. Asynchronous circuit design - a tutorial. Chaptes 1-8 inJ. Sparsø and S. Furber (eds.), Principles of asynchronous circuit design - A systems perspective. Kluwer Academic Publishers,2001. 337 pages.The writing of this textbook was initiated as a dissemination effort within theEuropean Low-Power Initiative for Electronic System Design (ESD-LPD) asexplained in the acknowledgements. As this author was neither involved innor funded by any of the projects under the ESD-LPD cluster, and hence notcontractually obliged to contribute to the book, copyright for chapters 1-8 wastransferred to Kluwer Academic Publishers for a limited period. For this reasonit is now possible for me to make the material available in the public domain(for non-commercial educational use). By doing this it is my hope that manymore can benefit from it.Apart from a few bug fixes everything (including page numbering) is thesame. I have included the original preface and epilogue sections as they communicate the aim and perspective of the text. I have also included the originalacknowledgements as they still apply.Since its publication in 2001 the material has been used in courses taughtat a number of universities including: The University of Manchester (UK),Technion (Israel), FORTH (Greece). It has also been used at a summer schoolin Grenoble in 2003 and a winter school at Cambridge University in 2005; bothorganized by the ACiD-WG network of excellence. At the Technical Universityof Denmark the author is teaching a 5 ECTS credit point one semester courseusing the material supplemented a couple of articles and by manuals and tutorialson the Balsa and Petrify synthesis tools. For laboratory exercises and designprojects we have used Petrify, Balsa, and VHDL.If you use the material for regular class teaching, I would be grateful if youdrop me an email. Any comments, suggestions for improvements or extensions,bug reports etc. are also welcomed. When citing the material please refer tothe original book mentioned above.Jens SparsøTechnical University of DenmarkApril 2006Email: jsp@imm.dtu.dk
ivASYNCHRONOUS CIRCUIT DESIGN
t I Asynchronous circuit design – A tutorialAuthor: Jens Sparsø1Introduction1.1Why consider asynchronous circuits?1.2Aims and background1.3Clocking versus handshaking1.4Outline of Part I334582Fundamentals2.1Handshake protocols2.1.1 Bundled-data protocols2.1.2 The 4-phase dual-rail protocol2.1.3 The 2-phase dual-rail protocol2.1.4 Other protocols2.2The Muller C-element and the indication principle2.3The Muller pipeline2.4Circuit implementation styles2.4.1 4-phase bundled-data2.4.2 2-phase bundled data (Micropipelines)2.4.3 4-phase dual-rail2.5Theory2.5.1 The basics of speed-independence2.5.2 Classification of asynchronous circuits2.5.3 Isochronic forks2.5.4 Relation to 25262627283Static data-flow structures3.1Introduction3.2Pipelines and rings292930v
viASYNCHRONOUS CIRCUIT DESIGN3.33.43.5Building blocksA simple exampleSimple applications of rings3.5.1 Sequential circuits3.5.2 Iterative computationsFOR, IF, and WHILE constructsA more complex example: GCDPointers to additional examples3.8.1 A low-power filter bank3.8.2 An asynchronous microprocessor3.8.3 A fine-grain pipelined vector nce4.1Introduction4.2A qualitative view of performance4.2.1 Example 1: A FIFO used as a shift register4.2.2 Example 2: A shift register with parallel load4.3Quantifying performance4.3.1 Latency, throughput and wavelength4.3.2 Cycle time of a ring4.3.3 Example 3: Performance of a 3-stage ring4.3.4 Final remarks4.4Dependency graph analysis4.4.1 Example 4: Dependency graph for a pipeline4.4.2 Example 5: Dependency graph for a 3-stage ke circuit implementations5.1The latch5.2Fork, join, and merge5.3Function blocks – The basics5.3.1 Introduction5.3.2 Transparency to handshaking5.3.3 Review of ripple-carry addition5.4Bundled-data function blocks5.4.1 Using matched delays5.4.2 Delay selection5.5Dual-rail function blocks5.5.1 Delay insensitive minterm synthesis (DIMS)5.5.2 Null Convention Logic5.5.3 Transistor-level CMOS implementations5.5.4 Martin’s adder5.6Hybrid function blocks5.7MUX and DEMUX5.8Mutual exclusion, arbitration and metastability5.8.1 Mutual exclusion5.8.2 Arbitration5.8.3 Probability of 071737577777979803.63.73.83.9
Contents6Speed-independent control circuits6.1Introduction6.1.1 Asynchronous sequential circuits6.1.2 Hazards6.1.3 Delay models6.1.4 Fundamental mode and input-output mode6.1.5 Synthesis of fundamental mode circuits6.2Signal transition graphs6.2.1 Petri nets and STGs6.2.2 Some frequently used STG fragments6.3The basic synthesis procedure6.3.1 Example 1: a C-element6.3.2 Example 2: a circuit with choice6.3.3 Example 2: Hazards in the simple gate implementation6.4Implementations using state-holding gates6.4.1 Introduction6.4.2 Excitation regions and quiescent regions6.4.3 Example 2: Using state-holding elements6.4.4 The monotonic cover constraint6.4.5 Circuit topologies using state-holding elements6.5Initialization6.6Summary of the synthesis process6.7Petrify: A tool for synthesizing SI circuits from STGs6.8Design examples using Petrify6.8.1 Example 2 revisited6.8.2 Control circuit for a 4-phase bundled-data latch6.8.3 Control circuit for a 4-phase bundled-data 9898991011011021041041061091137Advanced 4-phase bundled-dataprotocols and circuits7.1Channels and protocols7.1.1 Channel types7.1.2 Data-validity schemes7.1.3 Discussion7.2Static type checking7.3More advanced latch control circuits7.4Summary1151151161161181191218High-level languages and tools8.1Introduction8.2Concurrency and message passing in CSP8.3Tangram: program examples8.3.1 A 2-place shift register8.3.2 A 2-place (ripple) FIFO8.3.3 GCD using while and if statements8.3.4 GCD using guarded commands8.4Tangram: syntax-directed compilation8.4.1 The 2-place shift register8.4.2 The 2-place FIFO8.4.3 GCD using guarded repetition123123124126126126127128128129130131115
viiiASYNCHRONOUS CIRCUIT DESIGN8.58.6Martin’s translation processUsing VHDL for asynchronous design8.6.1 Introduction8.6.2 VHDL versus CSP-type languages8.6.3 Channel communication and design flow8.6.4 The abstract channel package8.6.5 The real channel package8.6.6 Partitioning into control and data8.7SummaryAppendix: The VHDL channel packagesA.1 The abstract channel packageA.2 The real channel e153References155Index165
PrefaceThis book was compiled to address a perceived need for an introductory texton asynchronous design. There are several highly technical books on aspects ofthe subject, but no obvious starting point for a designer who wishes to becomeacquainted for the first time with asynchronous technology. We hope this bookwill serve as that starting point.The reader is assumed to have some background in digital design. We assumethat concepts such as logic gates, flip-flops and Boolean logic are familiar. Someof the latter sections also assume familiarity with the higher levels of digitaldesign such as microprocessor architectures and systems-on-chip, but readersunfamiliar with these topics should still find the majority of the book accessible.The intended audience for the book comprises the following groups:Industrial designers with a background in conventional (clocked) digitaldesign who wish to gain an understanding of asynchronous design inorder, for example, to establish whether or not it may be advantageous touse asynchronous techniques in their next design task.Students in Electronic and/or Computer Engineering who are taking acourse that includes aspects of asynchronous design.The book is structured in three parts. Part I is a tutorial in asynchronousdesign. It addresses the most important issue for the beginner, which is howto think about asynchronous systems. The first big hurdle to be cleared isthat of mindset – asynchronous design requires a different mental approachfrom that normally employed in clocked design. Attempts to take an existingclocked system, strip out the clock and simply replace it with asynchronoushandshakes are doomed to disappoint. Another hurdle is that of circuit designmethodology – the existing body of literature presents an apparent plethoraof disparate approaches. The aim of the tutorial is to get behind this and topresent a single unified and coherent perspective which emphasizes the commonground. In this way the tutorial should enable the reader to begin to understandthe characteristics of asynchronous systems in a way that will enable them toix
xASYNCHRONOUS CIRCUIT DESIGN‘think outside the box’ of conventional clocked design and to create radical newdesign solutions that fully exploit the potential of clockless systems.Once the asynchronous design mindset has been mastered, the second hurdle is designer productivity. VLSI designers are used to working in a highlyproductive environment supported by powerful automatic tools. Asynchronousdesign lags in its tools environment, but things are improving. Part II of thebook gives an introduction to Balsa, a high-level synthesis system for asynchronous circuits. It is written by Doug Edwards (who has managed the Balsadevelopment at the University of Manchester since its inception) and AndrewBardsley (who has written most of the software). Balsa is not the solution to allasynchronous design problems, but it is capable of synthesizing very complexsystems (for example, the 32-channel DMA controller used on the DRACOchip described in Chapter 15) and it is a good way to develop an understandingof asynchronous design ‘in the large’.Knowing how to think about asynchronous design and having access tosuitable tools leaves one question: what can be built in this way? In Part III weoffer a number of examples of complex asynchronous systems as illustrations ofthe answer to this question. In each of these examples the designers have beenasked to provide descriptions that will provide the reader with insights into thedesign process. The examples include a commercial smart card chip designedat Philips and a Viterbi decoder designed at the University of Manchester. PartIII closes with a discussion of the issues that come up in the design of advancedasynchronous microprocessors, focusing on the Amulet processor series, againdeveloped at the University of Manchester.Although the book is a compilation of contributions from different authors,each of these has been specifically written with the goals of the book in mind –to provide answers to the sorts of questions that a newcomer to asynchronousdesign is likely to ask. In order to keep the book accessible and to avoid itbecoming an intimidating size, much valuable work has had to be omitted. Ourobjective in introducing you to asynchronous design is that you might becomeacquainted with it. If your relationship develops further, perhaps even into thefull-blown affair that has smitten a few, included among whose number are thecontributors to this book, you will, of course, want to know more. The bookincludes an extensive bibliography that will provide food enough for even themost insatiable of appetites.JENS SPARSØ AND STEVE FURBER, SEPTEMBER 2001
xiAcknowledgmentsMany people have helped significantly in the creation of this book. In addition to writing their respective chapters, several of the authors have also readand commented on drafts of other parts of the book, and the quality of the workas a whole has been enhanced as a result.The editors are also grateful to Alan Williams, Russell Hobson and SteveTemple, for their careful reading of drafts of this book and their constructivesuggestions for improvement.Part I of the book has been used as a course text and the quality and consistency of the content improved by feedback from the students on the spring2001 course “49425 Design of Asynchronous Circuits” at DTU.Any remaining errors or omissions are the responsibility of the editors.The writing of this book was initiated as a dissemination effort within theEuropean Low-Power Initiative for Electronic System Design (ESD-LPD), andthis book is part of the book series from this initiative. As will become clear,the book goes far beyond the dissemination of results from projects withinin the ESD-LPD cluster, and the editors would like to acknowledge the support of the working group on asynchronous circuit design, ACiD-WG, that hasprovided a fruitful forum for interaction and the exchange of ideas. The ACiDWG has been funded by the European Commission since 1992 under severalFramework Programmes: FP3 Basic Research (EP7225), FP4 Technologiesfor Components and Subsystems (EP21949), and FP5 Microelectronics (IST1999-29119).
IASYNCHRONOUS CIRCUIT DESIGN– A TUTORIALAuthor: Jens SparsøTechnical University of Denmarkjsp@imm.dtu.dkAbstractAsynchronous circuits have characteristics that differ significantly from thoseof synchronous circuits and, as will be clear from some of the later chaptersin this book, it is possible exploit these characteristics to design circuits withvery interesting performance parameters in terms of their power, performance,electromagnetic emissions (EMI), etc.Asynchronous design is not yet a well-established and widely-used design methodology. There are textbooks that provide comprehensive coverage of the underlying theories, but the field has not yet matured to a point where there is an established currriculum and university tradition for teaching courses on asynchronouscircuit design to electrical engineering and computer engineering students.As this author sees the situation there is a gap between understanding the fundamentals and being able to design useful circuits of some complexity. The aim ofPart I of this book is to provide a tutorial on asynchronous circuit design that fillsthis gap.More specifically the aims are: (i) to introduce readers with background in synchronous digital circuit design to the fundamentals of asynchronous circuit designsuch that they are able to read and understand the literature, and (ii) to providereaders with an understanding of the “nature” of asynchronous circuits such thatthey are to design non-trivial circuits with interesting performance parameters.The material is based on experience from the design of several asynchronouschips, and it has evolved over the last decade from tutorials given at a number ofEuropean conferences and from a number of special topics courses taught at theTechnical University of Denmark and elsewhere. In May 1999 I gave a one-weekintensive course at Delft University of Technology and it was when preparing forthis course I felt that the material was shaping up, and I set out to write thefollowing text. Most of the material has recently been used and debugged in acourse at the Technical University of Denmark in the spring 2001. Supplementedby a few journal articles and a small design project, the text may be used for aone semester course on asynchronous design.Keywords:asynchronous circuits, tutorial
Chapter 1INTRODUCTION1.1.Why consider asynchronous circuits?Most digital circuits designed and fabricated today are “synchronous”. Inessence, they are based on two fundamental assumptions that greatly simplifytheir design: (1) all signals are binary, and (2) all components share a commonand discrete notion of time, as defined by a clock signal distributed throughoutthe circuit.Asynchronous circuits are fundamentally different; they also assume binary signals, but there is no common and discrete time. Instead the circuitsuse handshaking between their components in order to perform the necessarysynchronization, communication, and sequencing of operations. Expressed in‘synchronous terms’ this results in a behaviour that is similar to systematicfine-grain clock gating and local clocks that are not in phase and whose periodis determined by actual circuit delays – registers are only clocked where andwhen needed.This difference gives asynchronous circuits inherent properties that can be(and have been) exploited to advantage in the areas listed and motivated below.The interested reader may find further introduction to the mechanisms behindthe advantages mentioned below in [106].Low power consumption, [102, 104, 32, 35, 73, 76]. . . due to fine-grain clock gating and zero standby power consumption.High operating speed, [119, 120, 63]. . . operating speed is determined by actual local latencies rather thanglobal worst-case latency.Less emission of electro-magnetic noise, [102, 83]. . . the local clocks tend to tick at random points in time.Robustness towards variations in supply voltage, temperature, and fabrication process parameters, [62, 72, 74]. . . timing is based on matched delays (and can even be insensitive tocircuit and wire delays).3
4Part I: Asynchronous circuit design – A tutorialBetter composability and modularity, [67, 57, 108, 97, 94]. . . because of the simple handshake interfaces and the local timing.No clock distribution and clock skew problems,. . . there is no global signal that needs to be distributed with minimalphase skew across the circuit.On the other hand there are also some drawbacks. The asynchronous controllogic that implements the handshaking normally represents an overhead in termsof silicon area, circuit speed, and power consumption. It is therefore pertinent toask whether or not the investment pays off, i.e. whether the use of asynchronoustechniques results in a substantial improvement in one or more of the aboveareas. Other obstacles are a lack of CAD tools and strategies and a lack of toolsfor testing and test vector generation.Research in asynchronous design goes back to the mid 1950s [68, 67], butit was not until the late 1990s that projects in academia and industry demonstrated that it is possible to design asynchronous circuits which exhibit significant benefits in nontrivial real-life examples, and that commercialization of thetechnology began to take place. Recent examples are presented in [80] and inPart III of this book.1.2.Aims and backgroundThere are already several excellent articles and book chapters that introduceasynchronous design [40, 24, 25, 26, 106, 49, 94] as well as several monographsand textbooks devoted to asynchronous design including [80, 7, 17, 10, 70] –why then write yet another introduction to asynchronous design? There areseveral reasons:My experience from designing several asynchronous chips [93, 77], andfrom teaching asynchronous design to students and engineers over thepast 10 years, is that it takes more than knowledge of the basic principlesand theories to design efficient asynchronous circuits. In my experiencethere is a large gap between the introductory articles and book chaptersmentioned above explaining the design methods and theories on the oneside, and the papers describing actual designs and current research onthe other side. It takes more than knowing the rules of a game to playand win the game. Bridging this gap involve
viii ASYNCHRONOUS CIRCUIT DESIGN 8.5 Martin’s translation process 133 8.6 Using VHDL for asynchronous design 134 8.6.1 Introduction 134 8.6.2 VHDL versus CSP-type languages 135 8.6.3 Channel communication and design ow 136 8.6.4 The abstract channel package 138 8.6.5 The real channel package 142 8.6.6 Partitioning into control and data 144
1.1 Basic block diagram of an Asynchronous Circuit 5 1.2 (a) A synchronous circuit, (b) a synchronous circuit with clock drivers and clock gating, (c) an equivalent asynchronous circuit, and (d) an abstract data-flow view of the asynchronous circuit. 9 2.1 CMOS in
2005 SystemVerilog standard[3], making SVA a little tricky to use for describing asynchronous behaviors. Asynchronous behaviors usually fall into two categories: (1) asynchronous control, and (2) asynchronous communication. SystemVerilog assertions can be used for either, but each presents its own set of challenges.
Multiphase buck converter: Asynchronous phase control 14 / 21 - analog-asynchronous interfaces - synthesised hazard-free components l asymmetric delays elements. Multiphase buck converter: Design of asynchronous
counter. Synchronous counter is faster than the asynchronous counter. Because Asynchronous counter has more delay of the pulse from one Flip flop to another Flip flop. Fig. 8. Simulated output of Conventional Two-bit Asynchronous Counter. D. Two-bit Synchronous Counter . In synchronous counter
Asynchronous File Transfer Protocols Older microcomputer file transfer protocols used asynchronous point-to-point circuits, typically across telephone lines via a modem. y XMODEM x XMODEM-CRC (CRC-8) x XMODEM-1K (CRC 1K blocks) y YMODEM(CRC-16) y ZMODEM (CRC-32) y KERMIT (CRC -24) Asynchronous
circuit protection component which cars he a fusible link, a fuse, or a circuit breaker. Then the circuit goes to the circuit controller which can be a switch or a relay. From the circuit controller the circuit goes into the circuit load. The circuit load can be one light or many lights in parallel, an electric motor or a solenoid.
Series Circuit A series circuit is a closed circuit in which the current follows one path, as opposed to a parallel circuit where the circuit is divided into two or more paths. In a series circuit, the current through each load is the same and the total voltage across the circuit is the sum of the voltages across each load. NOTE: TinkerCAD has an Autosave system.
development teams. In Agile Product Management with Scrum, you’ll see how a product owner differs from a traditional product manager having a greater level of responsibility for the success of the product. The book clearly outlines and contrasts the different behav-iors between the traditional and the agile role.
