Electronics Guide

Handshaking Protocols

The foundation of asynchronous communication is the handshake, a protocol where sender and receiver exchange signals to coordinate data transfer. Two primary handshaking schemes dominate asynchronous design:

Four-phase (return-to-zero) handshaking uses two control signals: request from sender to receiver and acknowledge from receiver to sender. The protocol proceeds through four phases: request goes high to indicate valid data, acknowledge goes high to confirm receipt, request returns low, and acknowledge returns low. This level-sensitive protocol is robust and straightforward to implement but requires four signal transitions per data transfer.

Two-phase (non-return-to-zero) handshaking signals events with transitions rather than levels. Each request transition indicates new data, and each acknowledge transition confirms receipt. This transition-sensitive protocol halves the number of signal changes per transfer, potentially doubling throughput. However, it requires edge detection circuitry that must distinguish rising from falling edges or track toggle state.

The choice between four-phase and two-phase protocols affects circuit complexity, power consumption, and performance. Four-phase designs use simpler logic but more switching activity, while two-phase designs trade circuit complexity for reduced transitions.

Delay Models

Asynchronous design methodologies are classified by their assumptions about circuit delays. Stronger delay assumptions enable simpler circuits but risk failure if delays violate assumptions. Weaker assumptions create more robust circuits at the cost of complexity.

Delay-insensitive (DI) circuits operate correctly regardless of gate and wire delays, assuming only that delays are finite and positive. This strongest robustness guarantee comes with severe limitations: truly delay-insensitive circuits can implement only trivial functions without additional timing assumptions.

Quasi-delay-insensitive (QDI) circuits assume isochronic forks, where wires branching from a single source have equal delays. This practical relaxation enables useful circuits while maintaining high robustness. QDI designs dominate practical asynchronous implementations.

Speed-independent (SI) circuits assume arbitrary gate delays but zero wire delays. This model suits integrated circuits where interconnect delays are small relative to gate delays, though modern deep-submicron technology challenges this assumption.

Bounded-delay circuits assume maximum delays for gates and wires, enabling timing analysis similar to synchronous design. This approach allows simpler circuits but requires careful timing verification and may fail with process, voltage, or temperature variations.

Completion Detection

A crucial challenge in asynchronous design is determining when a computation has finished. Without a clock that implicitly allows time for logic to settle, circuits must actively detect completion. Several approaches address this challenge:

Dual-rail encoding represents each data bit with two wires. The encoding distinguishes between valid data (one wire high) and the empty or spacer state (both wires low or both high). Completion occurs when all bit pairs reach valid states. This encoding doubles wire count but enables straightforward completion detection.

Bundled-data designs use single-rail data encoding with a separate completion signal. A matched delay line alongside the data path generates the completion indication. This approach uses fewer wires but requires careful delay matching and provides weaker robustness guarantees.

Delay-based completion assumes computation completes within a bounded time, using a fixed delay to generate completion signals. This technique sacrifices delay insensitivity for simplicity but must conservatively account for worst-case delays.

Basic Micropipeline Structure

A micropipeline stage consists of a data latch controlled by a Muller C-element that implements the handshaking protocol. The C-element outputs high when both inputs are high and low when both inputs are low, holding its previous state otherwise. This behavior naturally implements the rendezvous required for handshaking: the element waits for both sender ready and receiver ready before proceeding.

In the basic configuration, each stage's C-element receives the request from the previous stage and the acknowledge from the next stage. When both arrive, the C-element triggers the latch to capture data and propagates the handshake. An inverter in the acknowledge path converts the four-phase protocol at each stage into two-phase signaling between stages.

The key insight of micropipelines is that this simple structure creates a distributed FIFO behavior. Data tokens flow through the pipeline, with each stage holding at most one token. The pipeline naturally stretches and compresses as data arrives and departs at varying rates.

Bundled-Data Micropipelines

Practical micropipelines typically use bundled-data encoding, where conventional single-rail data accompanies matched delay request signals. The delay element on the request path must exceed the worst-case data path delay to ensure data stability when latched. This timing margin is analogous to setup time in synchronous design.

The advantages of bundled-data micropipelines include:

• Standard single-rail data paths compatible with conventional logic synthesis
• Lower wire count compared to dual-rail alternatives
• Familiar design flow for engineers experienced with synchronous design
• Efficient use of existing cell libraries and IP blocks

The primary disadvantage is sensitivity to delay variations. The matched delay must account for worst-case process, voltage, and temperature conditions, potentially sacrificing average-case performance. Careful delay matching and verification are essential.

Micropipeline Performance

Micropipeline throughput depends on the forward and backward latency through each stage. Forward latency is the time for data and request to propagate through the stage. Backward latency is the time for acknowledge to return to the previous stage. The maximum throughput equals one token per cycle time, where cycle time is the sum of forward and backward latencies.

Pipeline latency for a single token is the number of stages multiplied by the forward latency. Unlike synchronous pipelines where latency is measured in clock cycles, micropipeline latency is measured in actual propagation time, potentially offering advantages when processing time varies.

The elastic nature of micropipelines provides natural tolerance to timing variations. Slower stages simply accumulate tokens upstream while faster stages drain tokens downstream. This self-regulating behavior contrasts with synchronous pipelines where all stages must meet the same clock period.

Control Circuit Variations

Several variations on the basic micropipeline control structure address different requirements:

Capture-pass latches replace level-sensitive latches with edge-triggered flip-flops, providing cleaner timing behavior but requiring pulse generation from the C-element output.

Asymmetric C-elements modify the basic symmetric behavior to optimize for different input arrival patterns, reducing latency when one input typically arrives before the other.

GasP (Gasp-style Asynchronous Pipeline) uses a more aggressive timing approach with reduced transistor count, achieving higher performance at the cost of tighter timing margins.

Click elements combine the C-element and latch control into a single structure, reducing circuit complexity and potentially improving performance through tighter integration.

Dual-Rail Encoding in NCL

NCL represents each Boolean signal using two wires, conventionally labeled rail0 and rail1. The encoding uses three states:

• NULL: Both rails low (rail0=0, rail1=0), representing no valid data
• DATA0: Rail0 high, rail1 low (rail0=1, rail1=0), representing logic 0
• DATA1: Rail0 low, rail1 high (rail0=0, rail1=1), representing logic 1

The fourth combination (both rails high) is illegal and never occurs in correct operation. This encoding enables completion detection simply by checking that all signal pairs have left the NULL state, indicating valid data throughout the circuit.

NCL alternates between DATA and NULL wavefronts. A DATA wavefront carries actual computation results, while the following NULL wavefront resets all signals in preparation for the next computation. This return-to-null behavior corresponds to four-phase handshaking at the signal level.

Threshold Gates

NCL computation uses threshold gates, also called C-elements or Muller elements, that exhibit hysteresis behavior. A threshold gate with threshold T of N inputs (written THmn where m is the threshold) asserts its output when at least m inputs are high, and deasserts when all inputs are low. The output holds its previous value for intermediate input counts.

Common threshold gates include:

• TH12: Two-input OR gate (threshold 1 of 2)
• TH22: Two-input AND/C-element (threshold 2 of 2)
• TH23: Majority gate (threshold 2 of 3)
• TH33: Three-input AND (threshold 3 of 3)
• TH34w2: Weighted threshold gate where one input counts double

The hysteresis property ensures that threshold gates maintain their output during the transition between DATA and NULL wavefronts. When inputs begin transitioning to NULL, the gate holds its DATA output until all inputs reach NULL, preventing glitches and races.

NCL Circuit Design

Designing NCL circuits involves mapping Boolean functions to threshold gate networks operating on dual-rail signals. The design must ensure that DATA outputs are produced only when all necessary inputs have valid DATA values, and NULL outputs are produced only when all inputs are NULL.

The completion detection mechanism emerges naturally from the dual-rail encoding. When all outputs of a combinational block have reached DATA states, the computation is complete. A completion detector simply ANDs the logical OR of each output rail pair, generating a completion signal when all outputs are valid.

Pipeline stages in NCL use registration elements that pass data forward when the next stage is empty (NULL) and hold when the next stage contains valid data. This creates the same elastic behavior as micropipelines but with delay-insensitive guarantees rather than timing assumptions.

Advantages and Challenges of NCL

NCL offers several compelling advantages:

• Complete delay insensitivity eliminates timing closure problems
• Natural tolerance to process, voltage, and temperature variations
• Inherent glitch-free operation from the hysteresis property
• Zero standby power as gates switch only during active computation
• Reduced electromagnetic interference from data-dependent switching
• Modular composition without timing constraints between modules

Challenges include:

• Approximately twice the wire count due to dual-rail encoding
• Larger gate count from threshold gates and completion detection
• Specialized design tools required for synthesis and verification
• Limited availability of proven IP cores and design flows
• Learning curve for engineers trained in synchronous design

Burst-Mode State Machines

Burst-mode machines represent a practical approach to asynchronous FSM design. They allow multiple inputs to change simultaneously in a burst, with outputs and state changing in response to complete input bursts rather than individual bit changes. This model matches many real-world scenarios where related signals transition together.

A burst-mode specification defines transitions as (current_state, input_burst) to (next_state, output_burst). The machine waits in each state for a specified set of inputs to change, then transitions atomically to the next state while updating outputs. Between bursts, all inputs and outputs must be stable.

Burst-mode machines require careful input and output encoding to avoid critical races where different state bit arrival times could lead to incorrect states. Extended burst-mode (XBM) techniques handle conditional transitions and directed dont-cares, enabling more complex control specifications.

Signal Transition Graphs

Signal Transition Graphs (STGs) provide a formal model for specifying asynchronous control circuits. An STG is a Petri net where transitions represent signal edges (rising or falling) rather than abstract events. Places represent causal relationships between signal changes.

STG synthesis produces speed-independent circuits that implement the specified behavior. The synthesis process analyzes reachability, checks for hazards and races, and generates a circuit that correctly implements the signal ordering without timing assumptions on gate delays.

STGs excel at specifying interface controllers, handshake circuits, and reactive systems. The graphical notation clearly shows causality and concurrency, helping designers understand and verify complex control sequences. Tools like Petrify and Workcraft support STG specification and synthesis.

Huffman-Style Machines

The Huffman model, developed for asynchronous sequential circuits before the dominance of synchronous design, uses fundamental-mode operation where only one input changes at a time. The circuit must reach a stable state before the next input change occurs.

Huffman machines use combinational logic with feedback to implement state storage. The state variables feed back as inputs alongside primary inputs, and the combinational logic computes next state and outputs. Stability occurs when state variables equal their computed next values.

Designing hazard-free Huffman machines requires ensuring that state variables never glitch during transitions, as glitches could cause incorrect state capture. Static hazard elimination and careful encoding prevent most problems, but critical races require specific state assignments that guarantee correct sequencing.

State Encoding for Asynchronous FSMs

State encoding critically affects asynchronous FSM correctness. Unlike synchronous machines where flip-flops isolate encoding from timing, asynchronous machines must avoid races where different state bits change at different times.

One-hot encoding uses one flip-flop per state, eliminating most race conditions since only one state variable changes per transition. The overhead of extra state variables is often acceptable given the design simplicity.

Minimum-transition encoding assigns state codes to minimize the number of bit changes between adjacent states. This reduces switching activity and potential race conditions but may not eliminate all critical races.

Race-free encoding ensures that no state transition causes a critical race by carefully choosing state assignments. Tools can automatically find valid encodings or insert intermediate states to break unavoidable races.

Completion Signal Generation

The key to self-timing is generating a signal that indicates when computation has finished. Several techniques accomplish this:

Dual-rail completion uses encoded data that distinguishes between valid and empty states. Completion detection logic determines when all outputs have reached valid states. This approach provides true delay insensitivity but doubles wire count.

Matched delay paths replicate critical path delays to generate completion signals. A delay element matched to the data path produces the completion signal after the data has settled. This technique requires careful delay matching but works with standard single-rail logic.

Current-sensing completion monitors the supply current to detect when switching activity has ceased. When transistors stop switching, current drops, indicating computation is complete. This analog approach senses actual completion without explicit logic but requires careful analog design.

Dual-rail with return-to-zero pipelines alternate between data and spacer (null) wavefronts, with completion detected when all signals reach the expected state. The spacer phase separates successive data values and simplifies completion detection.

Self-Timed Arithmetic

Arithmetic circuits benefit significantly from self-timing because operation delays vary widely with operand values. A ripple-carry adder, for example, takes much longer when carries propagate through all bit positions than when carries are absorbed quickly. Self-timing allows the circuit to signal completion based on actual carry propagation.

Self-timed adders achieve average-case rather than worst-case performance. Studies show that random operands cause average carry chains much shorter than the worst case, providing significant speedup. For specific applications with known operand distributions, the benefits can be even greater.

Completion detection for adders can use carry-completion sensing, where special circuits detect when all carry signals have resolved. Alternatively, dual-rail encoding throughout the adder provides inherent completion indication at the cost of additional hardware.

Speculative Completion

Speculative completion techniques predict when computation will finish rather than waiting for definitive completion. The circuit produces a preliminary completion signal based on typical timing, with error detection and correction if the speculation was premature.

This approach trades correctness complexity for performance gains. When speculation is usually correct, the circuit achieves high throughput. When speculation fails, error recovery adds latency but maintains correctness. The technique works well when delay distributions have short tails and speculative failures are rare.

Speculative completion resembles synchronous timing in assuming bounded delays but adds error detection that synchronous design lacks. This combination can achieve better performance than either pure synchronous or pure asynchronous approaches.

GALS Motivation

Several factors drive interest in GALS architectures:

• Clock distribution to large dies consumes significant power and area
• Clock skew management becomes difficult as feature sizes shrink
• Voltage and frequency scaling benefits from independent domain control
• IP reuse is simplified when blocks can run at their natural frequencies
• Modular design supports independent development and verification
• EMI reduction from eliminating global periodic switching

GALS offers a practical migration path for existing synchronous designs. Engineers can leverage proven synchronous blocks and tools while addressing system-level timing challenges through asynchronous interconnection.

Synchronizer-Based GALS

The simplest GALS approach connects synchronous domains through conventional synchronizers and asynchronous FIFOs. Each domain runs on its independent clock, and data crossing between domains passes through synchronization circuits that handle the asynchronous clock relationship.

This approach uses well-understood synchronization techniques including two-flip-flop synchronizers, Gray-code FIFO pointers, and handshaking protocols. The design challenge lies in managing synchronization latency and throughput at domain boundaries while maintaining overall system performance.

Synchronizer-based GALS accepts metastability risk at domain boundaries, requiring MTBF analysis to ensure acceptable reliability. For most applications, properly designed synchronizers achieve MTBF values far exceeding system lifetime, but safety-critical applications may require additional measures.

Pausible Clocking

Pausible clocking eliminates metastability risk by stretching clock cycles when data transfers occur at domain boundaries. Rather than allowing flip-flops to sample asynchronous signals, the clock itself pauses to ensure synchronous sampling of stable data.

A pausible clock wrapper surrounds each synchronous domain. When data arrives from another domain, the wrapper stretches the current clock period until proper handshaking completes. The synchronous logic sees only complete clock cycles, never sampling during metastable conditions.

Pausible clocking requires careful design to avoid deadlock where domains wait for each other indefinitely. The technique adds latency compared to speculative synchronizers but guarantees correct operation without MTBF concerns. It is particularly valuable for safety-critical applications where metastability failures are unacceptable.

Loosely Synchronous GALS

Loosely synchronous approaches maintain approximate phase relationships between domain clocks, reducing the probability of problematic sampling without requiring pausible clocking or accepting metastability. Clock adjustment circuits periodically align domain clocks to prevent excessive drift.

Mesochronous clocking uses identical frequencies with unknown phase relationships. Since frequencies match, phase differences remain constant, enabling fixed-phase synchronization schemes. This approach suits systems where a common reference frequency is available but phase distribution is impractical.

Pleisiochronous clocking tolerates slightly different frequencies, with phase drifting slowly over time. Periodic resynchronization or elastic buffering accommodates the drift while maintaining communication. This model matches practical scenarios where independent oscillators have similar but not identical frequencies.

Elastic Pipeline Principles

An elastic pipeline augments each pipeline register with valid and stop handshaking signals. The valid signal propagates forward with data, indicating when register contents are meaningful. The stop signal propagates backward, indicating when a stage cannot accept new data.

A stage transfers data when valid is asserted and stop is deasserted. When stop is asserted, upstream stages hold their values rather than advancing. This creates backpressure that propagates through the pipeline, naturally handling variable-latency operations and rate mismatches.

The key insight is that elastic pipelines remain synchronous: all registers clock on the same edge. The handshaking determines which registers update each cycle, but timing is still governed by the global clock. This preserves the timing closure and verification advantages of synchronous design.

Elastic Buffer Design

The elastic buffer (EB) is the basic building block for elastic circuits. An EB stores data when backpressure prevents forward progress, providing the slack that enables elastic behavior. Multiple EB designs offer different tradeoffs:

FIFO-based EBs provide maximum elasticity through multi-entry buffering. When downstream stalls, the EB fills with waiting data. When downstream resumes, the EB drains. The FIFO depth determines how much rate mismatch can be absorbed.

Register-based EBs use minimal logic for single-entry buffering. A master-slave or double-register configuration provides one cycle of slack. These simpler EBs suit applications where brief stalls are common but extended buffering is unnecessary.

Capacity-zero EBs add handshaking without buffering, enabling elastic control flow without the cost of storage elements. They pass data through combinationally when not stalled, adding minimal latency during normal operation.

Variable-Latency Operations

Elastic circuits naturally accommodate operations with unpredictable latency. A divider, memory access, or external interface that takes varying cycles simply asserts stop until its result is ready. The pipeline stretches to accommodate the delay, then compresses when fast operations follow.

This flexibility contrasts with fixed-latency synchronous design, where all operations must complete within their allocated cycles. Elastic design eliminates the need to pad fast operations to match slow ones, improving average throughput when operation times vary significantly.

Exception handling and control flow changes also benefit from elastic design. Branch mispredictions, cache misses, and interrupts naturally create bubbles that propagate through elastic pipelines without complex stall logic.

Synthesis and Verification

Elastic circuit design leverages standard synchronous tools with modifications for handshaking logic. Synthesis adds EB elements based on latency requirements and inserts handshaking signals. The data paths remain conventional synchronous logic subject to normal timing analysis.

Verification must confirm that elastic control correctly handles all stall scenarios. Formal methods can prove deadlock freedom and liveness properties. Simulation with randomized stall injection exercises backpressure paths that might otherwise see limited coverage.

Performance analysis for elastic circuits considers both throughput and latency. Throughput depends on stall frequency and duration. Latency varies with pipeline occupancy and backpressure. Understanding these dynamics requires simulation or analytical modeling beyond traditional synchronous analysis.

Dataflow Execution Model

In dataflow computation, programs are represented as graphs where nodes are operations and edges carry data tokens. A node fires when tokens are present on all input edges, consuming inputs and producing outputs. Multiple nodes can fire concurrently when their inputs are independently available.

This token-based execution naturally expresses fine-grained parallelism. Operations throughout the graph can proceed simultaneously without explicit thread management or synchronization primitives. The data dependencies implicit in the graph edges provide all necessary ordering.

Dataflow graphs can be static, where the graph structure is fixed, or dynamic, where graph structure changes during execution. Static dataflow suits regular computations like signal processing. Dynamic dataflow handles conditionals and data-dependent control flow.

Token Matching and Firing

Implementing dataflow requires mechanisms to match tokens arriving at node inputs and trigger firing when complete sets are available. Several approaches address this challenge:

Static dataflow assumes single tokens on each edge, simplifying matching to presence detection. Each edge holds at most one token, and firing consumes all inputs while producing all outputs atomically. This model suits regular streaming computations.

Tagged tokens associate context information with each token, enabling multiple simultaneous activations of the same node. Tokens match when their tags correspond, allowing pipelined and parallel execution of the same graph structure.

Colored tokens extend tagging with color information that controls routing and matching. This generalization supports complex control structures while maintaining the dataflow abstraction.

Dataflow Pipeline Implementation

Asynchronous dataflow pipelines implement dataflow semantics in hardware using handshaking for token flow. Each pipeline stage represents one or more dataflow nodes, with tokens flowing through stages as handshaking permits.

The implementation must handle:

• Fork: Splitting a token stream to multiple consumers, ensuring all receivers get copies
• Join: Combining multiple token streams, waiting for all inputs before proceeding
• Merge: Combining streams where tokens from either source can proceed
• Conditional: Routing tokens based on control values
• Iteration: Looping tokens back through processing stages

These primitives compose to implement arbitrary dataflow graphs, with asynchronous handshaking ensuring correct token flow regardless of timing variations.

Applications of Dataflow

Dataflow architectures excel in specific application domains:

Signal processing maps naturally to dataflow, with streaming samples flowing through filter and transform operations. Regular data rates and predictable operations enable efficient implementations.

Neural network accelerators use dataflow for matrix operations and activation functions. The regular structure of neural network computations suits dataflow implementation.

Network processing handles packet data as tokens flowing through parsing, lookup, and forwarding operations. Variable packet sizes and rates benefit from dataflow flexibility.

Database query processing implements relational operations as dataflow nodes. Streaming query execution processes large datasets without materializing intermediate results.

Comparing Design Styles

Each asynchronous design style offers distinct characteristics:

Micropipelines provide familiar pipeline behavior with modest complexity overhead. They work well with existing synthesis flows and offer good average-case performance. The bounded-delay assumption requires timing verification similar to synchronous design.

NCL achieves maximum robustness through delay insensitivity at the cost of area and design tool maturity. It excels in harsh environments and applications where timing closure is difficult. The dual-rail overhead limits applicability for area-sensitive designs.

GALS enables practical asynchronous benefits with synchronous design flows within each domain. It suits large systems with natural partitioning and varying performance requirements. The domain boundaries add latency and complexity.

Elastic circuits extend synchronous methodology with minimal change, offering a gentle migration path. They handle variable latency naturally while preserving timing closure procedures. The handshaking overhead is small compared to full asynchronous design.

Dataflow matches specific application patterns exceptionally well. Streaming and parallel computations benefit most. The model may be awkward for control-intensive or sequential applications.

When to Use Asynchronous Design

Asynchronous design is particularly valuable when:

• Clock distribution is impractical due to die size, power, or integration constraints
• Low electromagnetic interference is required for regulatory or system reasons
• Power must scale with activity rather than being dominated by clock distribution
• Robustness to process, voltage, and temperature variation is critical
• Average-case rather than worst-case performance provides significant benefit
• Modularity and composability are high priorities
• Interface timing is inherently asynchronous

Synchronous design remains preferable when mature tool support is essential, area efficiency is paramount, design teams lack asynchronous experience, or timing requirements are well matched to clock-based design.

Hybrid Approaches

Many successful designs combine synchronous and asynchronous techniques. A primarily synchronous system might use asynchronous interfaces for external communication. An asynchronous datapath might use synchronous control. GALS explicitly combines both styles.

This pragmatic hybridization applies each technique where it provides the most benefit. Rather than ideological commitment to one paradigm, effective designers choose based on specific requirements and constraints of each portion of the system.

Asynchronous Synthesis Tools

Several tools support asynchronous design synthesis:

Petrify synthesizes speed-independent circuits from Signal Transition Graph specifications. It handles hazard-free logic synthesis and state assignment for asynchronous controllers.

Workcraft provides an integrated environment for Petri net modeling and synthesis, supporting STGs, NCL, and other asynchronous models with graphical editing and simulation.

Balsa is a synthesis system for asynchronous circuits from high-level descriptions. It compiles a concurrent language into handshake circuits with channel-based communication.

Commercial tools from vendors like Tiempo and Jedat support NCL and other delay-insensitive styles with production-quality synthesis and verification flows.

Verification Challenges

Asynchronous verification differs from synchronous verification in several ways:

Timing verification for quasi-delay-insensitive circuits focuses on ensuring delay assumptions hold rather than meeting clock period constraints. Isochronic fork analysis and delay matching verification replace setup and hold checks.

Functional verification must exercise concurrent behaviors that may be order-dependent. Test coverage must address different arrival orders and interleaving patterns that synchronous designs avoid.

Formal verification proves properties like deadlock freedom and liveness that are essential for asynchronous correctness. Model checking and theorem proving techniques verify that handshaking protocols complete successfully.

Hazard checking verifies that no static or dynamic hazards exist in speed-independent circuits. Glitches that synchronous designs ignore can cause incorrect state transitions in asynchronous machines.