Transcript Seminar on High-Speed Asynchronous Pipelines

Seminar on High-Speed
Asynchronous Pipelines
Montek Singh
Thursdays 10-11, SN325
1
Lecture 1: Introduction
 What is asynchronous design? Why do we want to
study it?
 What is pipelining? How can it be used to design
really fast hardware?
2
Introduction: Clocked Digital Design
Most current digital systems are synchronous:
 Clock: a global signal that paces operation of all components
clock
Benefit of clocking: enables discrete-time representation


all components operate exactly once per clock tick
component outputs need to be ready by next clock tick
 allows “glitchy” or incorrect outputs between clock ticks
3
Microelectronics Trends
Current and Future Trends: Significant Challenges
 Large-Scale “Systems-on-a-Chip” (SoC)
 100 Million ~ 1 Billion transistors/chip
 Very High Speeds
 multiple GigaHertz clock rates
 Explosive Growth in Consumer Electronics
 demand for ever-increasing functionality …
 … with very low power consumption (limited battery life)
 Higher Portability/Modularity/Reusability
 “plug ’n play” components, robust interfaces
4
Challenges to Clocked Design
Breakdown of Single-Clock Paradigm:
 Chip will be partitioned into multiple timing domains
Increasing Difficulties with Clocked Design:
 Clock distribution: will require significant designer effort
 Performance bottleneck: a single slow component
 Clock burns large fraction of chip power
 Fixed clock rate: poor match for
 designing reusable components
 interfacing with mixed-timing environments
5
What is Asynchronous Design?
 Digital design with no centralized clock
 Synchronization using local “handshaking”
clock
Synchronous System
(Centralized Control)
handshaking
interface
Asynchronous System
(Distributed Control)
6
Why Asynchronous Design?
 Higher Performance
 May obtain “average-case” operation (not “worst-case”)
 Avoids overheads of multi-GHz clock distribution
 Lower Power
 No clock power expended
 Inactive components consume negligible power
 Better Electromagnetic Compatibility
 Smooth radiation spectra: no clock spikes
 Much less interference with sensitive receivers [e.g., Philips
pagers]
 Greater Flexibility/Modularity
 Naturally adapt to varied environments
 Supports reusable components
7
Challenges of Asynchronous Design
 Hazards: potential “glitches” on wire
clock tick
clean signals
hazardous signals
no problem
for clocked
systems
 communication must be hazard-free!
 special design challenge = “hazard-free synthesis”
 Testability Issues:
 absence of clock means no “single-stepping”
 Lack of Commercial CAD Tools:
 chicken-and-egg problem
8
Asynchronous Design: Past & Present
Async Design: In existence for 50 years, but …
… many recent technical advances:
 Hazard-Free Circuit Design:
 several practical techniques for controllers [Stanford/Columbia]
 Design for Testability:
 several test solutions, e.g. Philips Research
 Maturing Computer-Aided-Design (“CAD”) Tools:
 software tools for automated design [Philips,Columbia,Manchester]
 Successful Fabricated Chips:
 embedded processors, high-speed pipelines, consumer electronics…
9
Recent Commercial Interest
Several commercial asynchronous chips:
 Philips: asynchronous 80c51 microcontrollers
 used in commercial pagers [1998] and cell phones [2000]
 Univ. of Manchester: async ARM processor [2000]
 Motorola: async divider in PowerPC chip [2000]
 HAL: async floating-point divider
 in HAL-I and II processors [early 1990’s]
Recent experimental chips:
 IBM, Sun and Intel:
 fast pipelines, arbiters, instruction-length decoder…
 IBM/Columbia Univ.: asynchronous digital FIR filter
Several recent startups:
 Theseus Logic, ADD, AmuCo…
10
Seminar Focus
Overall Goal:
Asynchronous Design for Very High-Speed Systems
Focus: High-Throughput Pipelines
Motivation: Pipelining is at the heart of nearly all
high-performance digital systems
Additional Benefits:
 Low power
 Interfacing with mixed systems
 Modular and scalable design
11
Background: Pipelining
What is Pipelining?: Breaking up a complex operation on a
stream of data into simpler sequential operations
fetch
decode
execute
A “coarse-grain” pipeline (e.g. simple processor)
Storage elements
(latches/registers)
A “fine-grain” pipeline (e.g. pipelined adder)
Throughput = #data items processed/second
+ Throughput: significantly increased
– Latency: somewhat degraded
12
Seminar Focus (contd.)
Particular Focus: Extremely fine-grain pipelines
 “gate-level” pipelining = use narrowest possible stages
 each stage consists of only a single level of logic gates
 some of the fastest existing digital pipelines to date
Application areas:
 multimedia hardware (graphics accelerators, video DSP’s, …)
 naturally pipelined systems, throughput is critical
 input is often “bursty”
 optical networking
 serializing/deserializing FIFO’s
 genomic string matching?
 KMP style string matching: variable skip lengths
13
Homework Problem
Alice and Bob live on opposite sides of a wide river:
Alice
Bob
Alice is supposed to send a message (say, a “Yes”/”No”) across
to Bob around midnight. Both have flashlights, but neither
owns a watch. What should they do?
Suggest several strategies, and discuss pros and cons of each.
14