Synchronization Design for Digital Systems

Synchronization is one of the important issues in digital system design. While other approaches have always been intriguing, up until now synchro­ nous operation using a common clock has been the dominant design philo­ sophy. However, we have reached the point, with advances in technology, where other options should be given serious consideration. This is because the clock periods are getting much smaller in relation to the interconnect propagation delays, even within a single chip and certainly at the board and backplane level. To a large extent, this problem can be overcome with care­ ful clock distribution in synchronous design, and tools for computer-aided design of clock distribution. However, this places global constraints on the design, making it necessary, for example, to redesign the clock distribution each time any part of the system is changed. In this book, some alternative approaches to synchronization in digital sys­ tem design are described and developed. We owe these techniques to a long history of effort in both digital system design and in digital communica­ tions, the latter field being relevant because large propagation delays have always been a dominant consideration in design. While synchronous design is discussed and contrasted to the other techniques in Chapter 6, the dom­ inant theme of this book is alternative approaches.

Preface.- Acknowledgements.- 1 Introduction.- 1.1 Asynchronous and Synchronous Design.- 1.2 Motivation for Asynchronous Design.- 1.2.1 Scaling and Technological Reasons.- 1.2.2 Design Complexity and Layout Factors.- 1.2.3 Applicability to Board Level System Design.- 1.2.4 Programmable Architecture Considerations.- 1.3 Plan of the Book.- 2 Synchronization.- 2.1 Synchronization in Digital Systems.- 2.2 Abstraction in Synchronization.- 2.2.1 Boolean Signals.- 2.2.2 Signal Transitions.- 2.2.3 Phase and Frequency.- 2.2.4 Synchronism.- 2.3 Timing Abstraction in Digital Systems.- 2.3.1 Equipotential Region.- 2.3.2 Ordering of Signals.- 3 Synthesis of Self-Timed Circuits.- 3.1 An Interconnection Scheme.- 3.1.1 Computation Blocks.- 3.1.2 Interconnection Blocks.- 3.2 Circuit Behavioral Description.- 3.2.1 Signal Transition Graphs.- 3.2.2 Speed-Independent Circuits.- 3.3 Interconnection Circuit Specifications.- 3.4 Weakest Semi-Modular Constraints.- 3.4.1 Consistent State Assignments.- 3.4.2 Maximum Concurrency.- 3.5 Synthesis Procedure and the C-Element.- 3.5.1 The Synthesis Procedure.- 3.5.2 SR-Latches vs. C-Elements.- 3.5.3 The Synthesis of OR Constructs.- 3.5.4 The Automated Synthesis Program.- 3.6 Interconnection Design Examples.- 3.6.1 Pipeline and Non-Pipeline Connections.- 3.6.2 Multiple-Input Block.- 3.6.3 Multiple-Output Block.- 3.6.4 Multiplexer.- 3.6.5 Demultiplexer.- 4 Self-Timed Programmable Processors.- 4.1 A Programmable Signal Processor.- 4.2 Data Flow Control.- 4.2.1 Data Latching Mechanism.- 4.2.2 Bus Control: Multiplexers and Demultiplexers.- 4.2.3 Memory Management.- 4.2.4 Initialization and Feedback.- 4.3 Program Flow Control.- 4.3.1 Unconditional Branch.- 4.3.2 Conditional Branch.- 4.3.3 I/O Interface.- 4.4 Processor Architecture.- 4.4.1 Data-Stationary Architectures.- 4.4.2 Time-Stationary Architectures.- 4.4.3 Multiple Function Units.- 4.5 simulation and performance evaluation.- 4.5.1 Simulation of Processor Operations.- 4.5.2 Throughput of Pipelined Architecture.- 5 A Chip Set for Adaptive Filters.- 5.1 Properties of Self-Timed Designs.- 5.1.1 Properties of Computation Blocks.- 5.1.2 Properties of Interconnection Blocks.- 5.1.3 Speed-Independence.- 5.1.4 System Initialization.- 5.2 A Self-Timed Array Multiplier.- 5.2.1 Architecture of the Multiplier.- 5.2.2 Circuit Design for the Multiplier Core.- 5.2.3 Circuit Design for the Accumulate-adder.- 5.3 A Vectorized Adaptive Lattice Filter.- 5.3.1 The Filter Architecture.- 5.3.2 The Pipeline Chip.- 5.3.3 The Computation Chips.- 5.4 Performance Evaluation.- 5.4.1 Testing Circuitry.- 5.4.2 Chip Performance Evaluations.- 5.4.3 Board Level Interconnection.- 6 Isochronous Interconnect.- 6.1 Synchronous Interconnect.- 6.1.1 Principle of Synchronous Interconnect.- 6.1.2 Pipelining.- 6.1.3 Clock Skew in Synchronous Interconnect.- 6.1.4 Parallel Signal Paths.- 6.2 Anisochronous Interconnect.- 6.3 Synchronization in Digital Communication.- 6.4 Non-Synchronous Interconnect.- 6.4.1 Mesochronous Interconnect.- 6.4.2 Heterochronous and Plesiochronous Interconnect.- 6.5 Architectural Issues.- 6.5.1 Command-Response Processing.- 6.6 Conclusions.- 6-A Certainty Region for Clock Skew.- 7 Automatic Verification.- 7.1 Verification of Self-Timed Circuits.- 7.2 Trace Theory of Finite Automata.- 7.2.1 Trace Structures.- 7.2.2 Operations on Trace Structures.- 7.2.3 Verification with Trace Theory.- 7.2.4 An Automatic Verifier.- 7.3 Tree Arbiter.- 7.3.1 Specification of the Tree Arbiter.- 7.3.2 Bad Implementation of the Arbiter.- 7.3.3 Correct Arbiter Implementation.- 7.4 Arbiter with Reject.- 7.4.1 Specification.- 7.4.2 Implementation.- 7.4.3 Flat Verification.- 7.4.4 Hierarchical Verification.- 7.5 Performance Summary.- Permuted Index.