Asynchronous circuit

From Wikipedia, the free encyclopedia
Jump to: navigation, search

An asynchronous circuit, or self-timed circuit, is a sequential digital logic circuit which is not governed by a clock circuit or global clock signal. Instead they often use signals that indicate completion of instructions and operations, specified by simple data transfer protocols. This type is contrasted with a synchronous circuit in which changes to the signal values in the circuit are triggered by repetitive pulses called a clock signal. Most digital devices today use synchronous circuits. However asynchronous circuits have the potential to be faster, and may also have advantages in lower power consumption, lower electromagnetic interference, and better modularity in large systems. Asynchronous circuits are an active area of research in digital logic design.

Synchronous vs asynchronous logic[edit]

Digital logic circuits can be divided into combinational logic, in which the output signals depend only on the current input signals, and sequential logic, in which the output depends both on current input and the past history of inputs. In other words, sequential logic is combinational logic with memory. Virtually all practical digital devices require sequential logic. Sequential logic can be divided into two types, synchronous logic and asynchronous logic.

  • In synchronous logic circuits, an electronic oscillator generates a repetitive series of equally-spaced pulses called the clock signal. The clock signal is applied to all the memory elements in the circuit, called flip-flops. The output of the flip-flops only change when triggered by the edge of the clock pulse, so changes to the logic signals throughout the circuit all begin at the same time, at regular intervals synchronized by the clock. The outputs of all the memory elements in a circuit is called the state of the circuit. The state of a synchronous circuit changes only on the clock pulse. The changes in signal require a certain amount of time to propagate through the combinational logic gates of the circuit. This is called propagation delay. The period of the clock signal is made long enough so the output of all the logic gates have time to settle to stable values before the next clock pulse. As long as this condition is met, synchronous circuits will operate stably, so they are easy to design.
However a disadvantage of synchronous circuits is that they can be slow. The maximum possible clock rate is determined by the logic path with the longest propagation delay, called the critical path. So logic paths that complete their operations quickly are idle much of the time. Another problem is that the widely distributed clock signal takes a lot of power, and must run whether the circuit is receiving inputs or not.
  • In asynchronous circuits, there is no clock, and the state of the circuit changes as soon as the input changes. Since they don't have to wait for a clock pulse to begin processing inputs, asynchronous circuits can be faster than synchronous circuits, and their speed is theoretically limited only by the propagation delays of the logic gates. However, asynchronous circuits are more difficult to design and subject to problems not found in synchronous circuits. This is because the resulting state of an asynchronous circuit can be sensitive to the relative arrival times of inputs at gates. If transitions on two inputs arrive at almost the same time, the circuit can go into the wrong state depending on slight differences in the propagation delays of the gates. This is called a race condition. In synchronous circuits this problem is less severe because race conditions can only occur due to inputs from outside the synchronous system, asynchronous inputs. Although some fully asynchronous digital systems have been built (see below), today asynchronous circuits are typically used in a few critical parts of otherwise synchronous systems where speed is at a premium, such as signal processing circuits.

Theoretical foundation[edit]

The term asynchronous logic is used to describe a variety of design styles, which use different assumptions about circuit properties.[1] These vary from the bundled delay model – which uses 'conventional' data processing elements with completion indicated by a locally generated delay model – to delay-insensitive design – where arbitrary delays through circuit elements can be accommodated. The latter style tends to yield circuits which are larger than bundled data implementations, but which are insensitive to layout and parametric variations and are thus "correct by design".

Asynchronous logic is the logic required for the design of asynchronous digital systems. These function without a clock signal and so individual logic elements cannot be relied upon to have a discrete true/false state at any given time. Boolean logic is inadequate for this and so extensions are required.[clarification needed] Karl Fant developed a theoretical treatment of this in his work Logically determined design in 2005 which used four-valued logic with null and intermediate being the additional values. This architecture is important because it is quasi-delay insensitive.[2] Scott Smith and Jia Di developed an ultra-low-power variation of Fant's Null Convention Logic that incorporates multi-threshold CMOS.[3] This variation is termed Multi-threshold Null Convention Logic (MTNCL), or alternatively Sleep Convention Logic (SCL).[4] Vadim Vasyukevich developed a different approach based upon a new logical operation which he called venjunction. This takes into account not only the current value of an element, but also its history.[5]

Petri nets are an attractive and powerful model for reasoning about asynchronous circuits. However, Petri nets have been criticized for their lack of physical realism (see Petri net: Subsequent models of concurrency). Subsequent to Petri nets other models of concurrency have been developed that can model asynchronous circuits including the Actor model and process calculi.

Benefits[edit]

A variety of advantages have been demonstrated by asynchronous circuits, including both Quasi Delay Insensitive (QDI) circuits (generally agreed to be the most "pure" form of asynchronous logic that retains computational universality) and less pure forms of asynchronous circuitry which use timing constraints for higher performance and lower area and power:

  • Robust handling of metastability of arbiters.
  • Higher performance function units, which provide average-case (i.e. data-dependent) completion rather than worst-case completion. Examples include speculative completion[6][7] which has been applied to design parallel prefix adders faster than synchronous ones, and a high-performance double-precision floating point adder'[8] which outperforms leading synchronous designs.
  • Early completion of a circuit when it is known that the inputs which have not yet arrived are irrelevant.
  • Lower power consumption because no transistor ever transitions unless it is performing useful computation. Epson has reported 70% lower power consumption compared to synchronous design.[9] Also, clock drivers can be removed which can significantly reduce power consumption. However, when using certain encodings, asynchronous circuits may require more area, which can result in increased power consumption if the underlying process has poor leakage properties (for example, deep submicrometer processes used prior to the introduction of High-k dielectrics).
  • "Elastic" pipelines, which achieve high performance while gracefully handling variable input and output rates and mismatched pipeline stage delays.[10]
  • Freedom from the ever-worsening difficulties of distributing a high-fan-out, timing-sensitive clock signal.
  • Better modularity and composability.
  • Far fewer assumptions about the manufacturing process are required (most assumptions are timing assumptions).
  • Circuit speed adapts to changing temperature and voltage conditions rather than being locked at the speed mandated by worst-case assumptions.
  • Immunity to transistor-to-transistor variability in the manufacturing process, which is one of the most serious problems facing the semiconductor industry as dies shrink.
  • Less severe electromagnetic interference (EMI). Synchronous circuits create a great deal of EMI in the frequency band at (or very near) their clock frequency and its harmonics; asynchronous circuits generate EMI patterns which are much more evenly spread across the spectrum.
  • In asynchronous circuits, local signaling eliminates the need for global synchronization which exploits some potential advantages in comparison with synchronous ones. They have shown potential specifications in low power consumption, design reuse, improved noise immunity and electromagnetic compatibility. Asynchronous circuits are more tolerant to process variations and external voltage fluctuations.
  • Less stress on the power distribution network. Synchronous circuits tend to draw a large amount of current right at the clock edge and shortly thereafter. The number of nodes switching (and thence, amount of current drawn) drops off rapidly after the clock edge, reaching zero just before the next clock edge. In an asynchronous circuit, the switching times of the nodes are not correlated in this manner, so the current draw tends to be more uniform and less bursty.

Disadvantages[edit]

  • Area overhead may be up to double the number of circuit elements (transistors), due to addition of completion detection and design-for-test circuits.[11]
  • Fewer people are trained in this style compared to synchronous design.[11]
  • Synchronous designs are inherently easier to test and debug than asynchronous designs.[12][dubious ]
  • Clock gating in more conventional synchronous designs is an approximation of the asynchronous ideal, and in some cases, its simplicity may outweigh the advantages of a fully asynchronous design.
  • Performance (speed) of asynchronous circuits may be reduced in architectures that require input-completeness (more complex data path).[13]
  • Incompatible with commercial EDA tools [13]

Communication protocols[edit]

There are several ways to create asynchronous communication channels. Usually, the sender signals the availability of data with a request, Req, and the receiver indicates completion with an acknowledgement signal, Ack, indicating that it is able to process new requests; this process is called a handshake. The differences lie in the way this signals are coded.

Protocols[edit]

There are two protocol families in asynchronous circuits, which differ in the way events are encoded:

  • They may be represented by any transition on a wire, from 0 to 1 as well as 1 to 0. This is called transition signalling, the two-phase protocol, a half-handshake or Non-Return-to-Zero encoding
  • Or the signals may require a reset before other operations are performed. For example, the sender resets the request wires once the acknowledgement is received, and the receiver resets the acknowledgement afterwards. This is the four-phase protocol, four-phase handshake, or Return-to-Zero encoding. Despite being apparently more complicated, the circuit-level implementations are usually faster and simpler.

This basic distinction doesn't account for the wide variety of protocols. These events may encode requests and acknowledgements only or encode the data, which leads to the popular multi-wire encodings. A lot of other, less common protocols have been proposed. Those include using a single wire for request and acknowledgment, using several significant voltages, using only pulses or balance timings in order to remove the latches.

Data encoding[edit]

There are several ways to encode data in asynchronous circuits. The most obvious encoding, similar to what can be found in synchronous circuits, is the bundled-data encoding, which uses one wire per bit of data and a separate request wire. Another common way to encode the data is to use multiple wires to encode a single digit: the value is determined by the wire on which the event occurs. This avoids some of the delay assumptions necessary with bundled-data encoding, since the request and the data are not separated anymore.

Bundled-data encoding[edit]

This is the same encoding as in synchronous circuits: it uses one wire per data bit. The request and the acknowledgement are sent on separate wires with various protocols. These circuits usually assume a bounded delay model, the completion signals being delayed long enough for the calculations to take place.

Such circuits are often referred to as micropipelines, whether they use a two-phase or four-phase protocol, even if the word was initially introduced for two-phase bundled-data.

Multi-rail encoding[edit]

Here, the request isn't sent on a dedicated wire: it is implicit, when a transition happens on one wire. Any m of n encoding can be used, where a digit is represented by m transitions on n wires, and the reception of these transitions is equivalent to a request, with the advantage that this communication is delay-insensitive. Usually, a one-hot (1 of n) encoding is preferred. They can represent a digit in radix n.

Dual-rail encoding is by far the most common, mostly with a four-phase protocol which is also called three-state encoding, since it has two valid states (10 and 01, after a transition) and a reset state (00). Another common encoding, which leads to simpler implementation than one-hot two-phase dual-rail, is four state encoding, or level encoded dual-rail, which uses a data bit and a parity bit to achieve a two-phase protocol.

Asynchronous CPU[edit]

Asynchronous CPUs are one of several ideas for radically changing CPU design.

Unlike a conventional processor, a clockless processor (asynchronous CPU) has no central clock to coordinate the progress of data through the pipeline. Instead, stages of the CPU are coordinated using logic devices called "pipeline controls" or "FIFO sequencers." Basically, the pipeline controller clocks the next stage of logic when the existing stage is complete. In this way, a central clock is unnecessary. It may actually be even easier to implement high performance devices in asynchronous, as opposed to clocked, logic:

  • components can run at different speeds on an asynchronous CPU; all major components of a clocked CPU must remain synchronized with the central clock;
  • a traditional CPU cannot "go faster" than the expected worst-case performance of the slowest stage/instruction/component. When an asynchronous CPU completes an operation more quickly than anticipated, the next stage can immediately begin processing the results, rather than waiting for synchronization with a central clock. An operation might finish faster than normal because of attributes of the data being processed (e.g., multiplication can be very fast when multiplying by 0 or 1, even when running code produced by a naive compiler), or because of the presence of a higher voltage or bus speed setting, or a lower ambient temperature, than 'normal' or expected.

Asynchronous logic proponents believe these capabilities would have these benefits:

  • lower power dissipation for a given performance level, and
  • highest possible execution speeds.

The biggest disadvantage of the clockless CPU is that most CPU design tools assume a clocked CPU (i.e., a synchronous circuit). Many tools "enforce synchronous design practices".[14] Making a clockless CPU (designing an asynchronous circuit) involves modifying the design tools to handle clockless logic and doing extra testing to ensure the design avoids metastable problems. The group that designed the AMULET, for example, developed a tool called LARD[15] to cope with the complex design of AMULET3.

Despite the difficulty of doing so, numerous asynchronous CPUs have been built, including:

  • the ORDVAC and the (identical) ILLIAC I (1951)[16][17]
  • the Johnniac (1953)[18]
  • the WEIZAC (1955)
  • the ILLIAC II (1962)[16]
  • The Victoria University of Manchester built Atlas
  • The Honeywell CPUs 6180 (1972)[19] and Series 60 Level 68 (1981)[20][21] upon which Multics ran asynchronously
  • The Caltech Asynchronous Microprocessor, the world-first asynchronous microprocessor (1988);
  • the ARM-implementing AMULET (1993 and 2000);
  • the asynchronous implementation of MIPS R3000, dubbed MiniMIPS (1998);
  • several versions of the XAP processor experimented with different asynchronous design styles: a bundled data XAP, a 1-of-4 XAP, and a 1-of-2 (dual-rail) XAP (2003?);[22]
  • an ARM-compatible processor (2003?) designed by Z. C. Yu, S. B. Furber, and L. A. Plana; "designed specifically to explore the benefits of asynchronous design for security sensitive applications";[22]
  • the "Network-based Asynchronous Architecture" processor (2005) that executes a subset of the MIPS architecture instruction set;[22]
  • the ARM996HS processor (2006) from Handshake Solutions
  • the HT80C51 processor (2007???) from Handshake Solutions[23]
  • the SEAforth multi-core processor (2008) from Charles H. Moore.[24]
  • the GA144[25] multi-core processor (2010) from Charles H. Moore.

The ILLIAC II was the first completely asynchronous, speed independent processor design ever built; it was the most powerful computer at the time.[16]

DEC PDP-16 Register Transfer Modules (ca. 1973) allowed the experimenter to construct asynchronous, 16-bit processing elements. Delays for each module were fixed and based on the module's worst-case timing.

The Caltech Asynchronous Microprocessor (1988) was the first asynchronous microprocessor (1988). Caltech designed and manufactured the world's first fully Quasi Delay Insensitive processor.[citation needed] During demonstrations, the researchers amazed viewers by loading a simple program which ran in a tight loop, pulsing one of the output lines after each instruction. This output line was connected to an oscilloscope. When a cup of hot coffee was placed on the chip, the pulse rate (the effective "clock rate") naturally slowed down to adapt to the worsening performance of the heated transistors. When liquid nitrogen was poured on the chip, the instruction rate shot up with no additional intervention. Additionally, at lower temperatures, the voltage supplied to the chip could be safely increased, which also improved the instruction rate—again, with no additional configuration.

In 2004, Epson manufactured the world's first bendable microprocessor called ACT11, an 8-bit asynchronous chip.[26][27][28][29][30] Synchronous flexible processors are slower, since bending the material on which a chip is fabricated causes wild and unpredictable variations in the delays of various transistors, for which worst case scenarios must be assumed everywhere and everything must be clocked at worst case speed. The processor is intended for use in smart cards, whose chips are currently limited in size to those small enough that they can remain perfectly rigid.

See also[edit]

References[edit]

  1. ^ van Berkel, C.H. and M.B. Josephs and S.M. Nowick (February 1999), "Applications of Asynchronous Circuits", Proceedings of the IEEE, 87 (2): 234–242 
  2. ^ Karl M. Fant (2005), Logically determined design: clockless system design with NULL convention logic (NCL), John Wiley and Sons, ISBN 978-0-471-68478-7 
  3. ^ Smith, Scott and Di, Jia (2009). Designing Asynchronous Circuits using NULL Conventional Logic (NCL). Morgan & Claypool Publishers. ISBN 978-1-59829-981-6. 
  4. ^ Scott, Smith and Di, Jia. "U.S. 7,977,972 Ultra-Low Power Multi-threshold Asychronous Circuit Design". Retrieved 2011-12-12. 
  5. ^ Vasyukevich, V. O. (April 2007), "Decoding asynchronous sequences", Automatic Control and Computer Sciences (Allerton Press) 41 (2): 93–99, doi:10.3103/S0146411607020058, ISSN 1558-108X 
  6. ^ Nowick, S.M. and K.Y. Yun and P.A. Beerel and A.E. Dooply (March 1997), "Speculative Completion for the Design of High-Performance Asynchronous Dynamic Adders", Proceedings of the IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems ('Async'),: 210–223 
  7. ^ Nowick, S.M. (September 1996), "Design of a Low-Latency Asynchronous Adder Using Speculative Completion", IEE Proceedings -- Computers and Digital Techniques,: 301–307 
  8. ^ Sheikh, B. and R. Manohar (May 2010), "An Operand-Optimized Asynchronous IEEE 754 Double-Precision Floating-Point Adder", Proceedings of the IEEE International Symposium on Asynchronous Circuits and Systems ('Async'),: 151–162 
  9. ^ "Epson Develops the World's First Flexible 8-Bit Asynchronous Microprocessor" 2005
  10. ^ Nowick, S.M. and M. Singh (Sep–Oct 2011), "High-Performance Asynchronous Pipelines: an Overview", IEEE Design & Test of Computers, special issue on asynchronous design, 28 (5): 8–22 
  11. ^ a b Furber, Steve. "Principles of Asynchronous Circuit Design". Pg. 232. Retrieved 2011-12-13. 
  12. ^ "Keep It Strictly Synchronous: KISS those asynchronous-logic problems good-bye". Personal Engineering and Instrumentation News, November 1997, pages 53–55. http://www.fpga-site.com/kiss.html
  13. ^ a b van Leeuwen, T.M. (2010). Implementation and automatic generation of asynchronous scheduled data ow graph. Delft. 
  14. ^ "ASIC to FPGA migration"
  15. ^ LARD
  16. ^ a b c "In the 1950and 1960s, asynchronous design was used in many early mainframe computers, including the ILLIAC I and ILLIAC II ... ." Brief History of asynchronous circuit design
  17. ^ "The Illiac is a binary parallel asynchronous computer in which negative numbers are represented as two's complements." – final summary of "Illiac Design Techniques" 1955.
  18. ^ Johnniac history written in 1968
  19. ^ "Entirely asynchronous, its hundred-odd boards would send out requests, earmark the results for somebody else, swipe somebody else's signals or data, and backstab each other in all sorts of amusing ways which occasionally failed (the "op not complete" timer would go off and cause a fault). ... [There] was no hint of an organized synchronization strategy: various "it's ready now", "ok, go", "take a cycle" pulses merely surged through the vast backpanel ANDed with appropriate state and goosed the next guy down. Not without its charms, this seemingly ad-hoc technology facilitated a substantial degree of overlap ... as well as the [segmentation and paging] of the Multics address mechanism to the extant 6000 architecture in an ingenious, modular, and surprising way ... . Modification and debugging of the processor, though, were no fun." "Multics Glossary: ... 6180"
  20. ^ "10/81 ... DPS 8/70M CPUs" Multics Chronology
  21. ^ "The Series 60, Level 68 was just a repackaging of the 6180." Multics Hardware features: Series 60, Level 68
  22. ^ a b c "A Network-based Asynchronous Architecture for Cryptographic Devices" by Ljiljana Spadavecchia 2005 in section "4.10.2 Side-channel analysis of dual-rail asynchronous architectures" and section "5.5.5.1 Instruction set"
  23. ^ "Handshake Solutions HT80C51" "The Handshake Solutions HT80C51 is a Low power, asynchronous 80C51 implementation using handshake technology, compatible with the standard 8051 instruction set."
  24. ^ SEAforth Overview "... asynchronous circuit design throughout the chip. There is no central clock with billions of dumb nodes dissipating useless power. ... the processor cores are internally asynchronous themselves."
  25. ^ "GreenArrayChips" "Ultra-low-powered multi-computer chips with integrated peripherals."
  26. ^ "Seiko Epson tips flexible processor via TFT technology" by Mark LaPedus 2005
  27. ^ "A flexible 8b asynchronous microprocessor based on low-temperature poly-silicon TFT technology" by Karaki et al. 2005. Abstract: "A flexible 8b asynchronous microprocessor ACTII ... The power level is 30% of the synchronous counterpart."
  28. ^ "Introduction of TFT R&D Activities in Seiko Epson Corporation" by Tatsuya Shimoda (2005?) has picture of "A flexible 8-bit asynchronous microprocessor, ACT11"
  29. ^ "Epson Develops the World's First Flexible 8-Bit Asynchronous Microprocessor"
  30. ^ "Seiko Epson details flexible microprocessor: A4 sheets of e-paper in the pipeline by Paul Kallender 2005

External links[edit]