Asynchronous Circuit Design: Table of Contents

Asynchronous Circuit Design

Chris J. Myers

University of Utah

John Wiley & Sons, Inc.


Table of Contents


Preface

Acknowledgments

1 Introduction

1.1 Problem Specification

1.2 Communication Channels

1.3 Communication Protocols

1.4 Graphical Representations

1.5 Delay-Insensitive Circuits

1.6 Huffman Circuits

1.7 Muller Circuits

1.8 Timed Circuits

1.9 Verification

1.10 Applications

1.11 Let's Get Started

1.12 Sources

Problems

2 Communication Channels

2.1 Basic Structure

2.2 Structural Modeling in VHDL

2.3 Control Structures

2.3.1 Selection

2.3.2 Repetition

2.4 Deadlock

2.5 Probe

2.6 Parallel Communication

2.7 Example: MiniMIPS

2.7.1 VHDL Specification

2.7.2 Optimized MiniMIPS

2.8 Sources

Problems

3 Communication Protocols

3.1 Basic Structure

3.2 Active and Passive Ports

3.3 Handshaking Expansion

3.4 Reshuffling

3.5 State Variable Insertion

3.6 Data Encoding

3.7 Example: Two Wine Shops

3.8 Syntax-Directed Translation

3.9 Sources

Problems

4 Graphical Representations

4.1 Graph Basics

4.2 Asynchronous Finite State Machines

4.2.1 Finite State Machines and Flow Tables

4.2.2 Burst-Mode State Machines

4.2.3 Extended Burst-Mode State Machines

4.3 Petri Nets

4.3.1 Ordinary Petri Nets

4.3.2 Signal Transition Graphs

4.4 Timed Event/Level Structures

4.5 Sources

Problems

5 Huffman Circuits

5.1 Solving Covering Problems

5.1.1 Matrix Reduction Techniques

5.1.2 Bounding

5.1.3 Termination

5.1.4 Branching

5.2 State Minimization

5.2.1 Finding the Compatible Pairs

5.2.2 Finding the Maximal Compatibles

5.2.3 Finding the Prime Compatibles

5.2.4 Setting Up the Covering Problem

5.2.5 Forming the Reduced Flow Table

5.3 State Assignment

5.3.1 Partition Theory and State Assignment

5.3.2 Matrix Reduction Method

5.3.3 Finding the Maximal Intersectibles

5.3.4 Setting Up the Covering Problem

5.3.5 Fed-Back Outputs as State Variables

5.4 Hazard-Free Two-Level Logic Synthesis

5.4.1 Two-Level Logic Minimization

5.4.2 Prime Implicant Generation

5.4.3 Prime Implicant Selection

5.4.4 Combinational Hazards

5.5 Extensions for MIC Operation

5.5.1 Transition Cubes

5.5.2 Function Hazards

5.5.3 Combinational Hazards

5.5.4 Burst-Mode Transitions

5.5.5 Extended Burst-Mode Transitions

5.5.6 State Minimization

5.5.7 State Assignment

5.5.8 Hazard-Free Two-Level Logic Synthesis

5.6 Multilevel Logic Synthesis

5.7 Technology Mapping

5.8 Generalized C-Element Implementation

5.9 Sequential Hazards

5.10 Sources

Problems

6 Muller Circuits

6.1 Formal Definition of Speed Independence

6.1.1 Subclasses of Speed-Independent Circuits

6.1.2 Some Useful Definitions

6.2 Complete State Coding

6.2.1 Transition Points and Insertion Points

6.2.2 State Graph Coloring

6.2.3 Insertion Point Cost Function

6.2.4 State Signal Insertion

6.2.5 Algorithm for Solving CSC Violations

6.3 Hazard-Free Logic Synthesis

6.3.1 Atomic Gate Implementation

6.3.2 Generalized C-Element Implementation

6.3.3 Standard C-Implementation

6.3.4 The Single-Cube Algorithm

6.4 Hazard-Free Decomposition

6.4.1 Insertion Points Revisited

6.4.2 Algorithm for Hazard-Free Decomposition

6.5 Limitations of Speed-Independent Design

6.6 Sources

Problems

7 Timed Circuits

7.1 Modeling Timing

7.2 Regions

7.3 Discrete time

7.4 Zones

7.5 POSET Timing

7.6 Timed Circuits

7.7 Sources

Problems

8 Verification

8.1 Protocol Verification

8.1.1 Linear-Time Temporal Logic

8.1.2 Time-Quantified Requirements

8.2 Circuit Verification

8.2.1 Trace Structures

8.2.2 Composition

8.2.3 Canonical Trace Structures

8.2.4 Mirrors and Verification

8.2.5 Strong Conformance

8.2.6 Timed Trace Theory

8.3 Sources

Problems

9 Applications

9.1 Brief History of Asynchronous Circuit Design

9.2 An Asynchronous Instruction-Length Decoder

9.3 Performance Analysis

9.4 Testing Asynchronous Circuits

9.5 The Synchronization Problem

9.5.1 Probability of Synchronization Failure

9.5.2 Reducing the Probability of Failure

9.5.3 Eliminating the Probability of Failure

9.5.4 Arbitration

9.6 The Future of Asynchronous Circuit Design

9.7 Sources

Problems

Appendix A VHDL Packages

A.1 nondeterminism.vhd

A.2 channel.vhd

A.3 handshake.vhd

Appendix B Sets and Relations

B.1 Basic Set Theory

B.2 Relations

References

Index