Transcript Introduction - UNC Computer Science

COMP790-084
Clockless Computing
(and Silicon Compilers)
or
How do I take “hard” out of hardware design?
Montek Singh
Tue, Aug 21, 2007
1
Course Information (1)
Course Number: COMP790-084 (formerly 290-084)
Time and Place
 Tue/Thu 2-3:15pm, Sitterson Hall 252 (will try another rm)
 Any conflicts?
Instructor
 Montek Singh
 [email protected] (not singh@cs!)
 SN 245, 962-1832
Teaching Assistant
 None
Course Web Page (soon…)
 http://www.cs.unc.edu/~montek
2
Course Information (2)
Prerequisites:
 undergraduate knowledge of: digital logic, algorithms,
discrete math (sets and graphs), programming languages
 you are assumed to know the following topics:
 digital logic: Boolean algebra, logic gates, and latches and registers
 algorithms: search techniques, enumeration, divide and conquer,
and time complexity
 discrete math: elementary set theory and graph theory
 no knowledge of advanced circuit design or of VLSI is
assumed
 relevant topics will be covered in class as needed
 VLSI primer included in this class
 no knowledge of compilers is assumed
 only undergraduate programming languages required
3
Course Information (3)
Reading Material:
 Lecture notes
 Papers and technical reports supplied by instructor
Reference Textbooks (optional):
 Principles of Asynchronous Circuit Design  A Systems
Perspective.
 Jens Sparsø and Steve Furber (eds.). Kluwer. (ASK ME!)
 Principles of CMOS VLSI Design: A Systems Perspective
 Weste and Eshraghian. Addison-Wesley, 1993.
 Computer Aids for VLSI Design
 Steven M. Rubin. Static Free Software.
http://www.rulabinsky.com/cavd (Free, online)
4
Course Information (4): Content
Clockless logic:
 Introductory concepts
 Data representation, and control signaling
 Graphical representation of asynchronous systems
 Petri nets, state transition graphs, burst-mode machines, etc.
 Algorithms for logic synthesis
 Combinational and sequential
 Pipelining and Architecture
Silicon Compilers:
 High-level description languages
 Compilation from algorithms to hardware
 State-of-the-art compilers and analysis tools
Optional topics:
 Formal methods
 Performance analysis
 Verification
 Case studies of real-world asynchronous processors
5
Course Information (4)
Grading
 Homework: 35%
 Project: 35%
 Presentation: 20%
 Class participation: 10%
Honor Code is in effect
 encouraged to discuss ideas/concepts
 work handed in must be your own
 acknowledge all help
6
Lecture 1: Introduction
 What is asynchronous design?
 Why do we want to study it?
 How is data represented in an asynchronous system?
 How is information exchanged?
7
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
8
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
9
Challenges to Clocked Design
Breakdown of Single-Clock Paradigm:
 Chip will be partitioned into multiple timing domains
 challenge: gluing together multiple timing domains
– glue logic is susceptible to “metastability” (=incorrect values
transferred) and latency overheads
Increasing Difficulties with Clocked Design:
 Clock distribution: requires significant designer effort
 Performance bottleneck: a single slow component
 Clock burns large fraction of chip power (~40-70%)
 Fixed clock rate: poor match for
 designing reusable components
 interfacing with mixed-timing environments
10
What is Asynchronous Design?
 Digital design with no centralized clock
 Synchronization using local “handshaking”
handshaking
interface
clock
Synchronous System
(Centralized Control)
Asynchronous System
(Distributed Control)
11
Why Asynchronous Design? (1)
 Higher Performance
 May obtain “average-case” operation (not “worst-case”)
 not limited by slowest component
 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, smartcards]
 Greater Flexibility/Modularity
 Naturally adapt to variable-speed environments
 Supports reusable components
12
Why Asynchronous Design? (2)
 The world already is mostly asynchronous!
 Events at the level of (or in between) large-scale systems are
asynchronous
 several seconds to several milliseconds
 e.g., PC-printer communication, keyboard inputs, network comm.
 Events at the board level (or between chips) are often
asynchronous
 milliseconds to 100 nanoseconds
 e.g., CPU-memory interface, interface with I/O subsystem (interrupts)
 Events within a chip, at the level of functional units (e.g., adders,
control logic) are currently mostly synchronous
 several nanoseconds to 100 picoseconds
 Events at the level of a single logic gate are asynchronous
 10 picoseconds
 Events at the quantum level are asynchronous
 picoseconds to femtoseconds
 So, why bother with clocks at all?!
 make everything asynchronous  greater elegance and robustness13
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
14
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]
 recent DARPA program [Boeing,Philips,UNC,Columbia,…]
 Successful Fabricated Chips:
 embedded processors, high-speed pipelines, consumer electronics…
15
Recent Commercial Interest (1)
Several commercial asynchronous chips:
 Philips: asynchronous 80c51 microcontrollers
 used in commercial pagers [1998] and smartcards [2001]
 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/UNC: asynchronous digital FIR filter
Several recent startups:
 Handshake Solutions, Theseus Logic, Codetronix, Fulcrum,
Silistix, …
16
Recent Commercial Interest (2)
Major DARPA program:
 ~$13M
 Goals:
 commercial-strength automated CAD tool (=silicon compiler)
– direct translation from algorithms to chip layout
– capable of producing chips with 50M transistors or more
– rich suite of analysis and optimization tools
 demonstration chip
– Boeing application
– show dramatic improvements in: design time, power consumption,
noise pollution, speed (?)
 Team:
 led by Boeing
 async startups: Theseus, Handshake Solutions, Codetronix
 universities: UNC, Columbia, UW, OrSU
17
Data Representation and
Communication
18
A 5-minute 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.
19
Solution 1
Alice uses 2 lamps:
 1 to indicate that she is ready with the message, and
 1 for the message itself
Bob uses 1 lamp:
 to indicate that he has received the message
Alice
Bob
20
Solution 2
Alice uses 2 lamps:
 Green lamp to indicate “yes”
 Red lamp to indicate “no”
Bob uses 1 lamp:
 to indicate that he has received the message
Alice
Bob
21
Solution 3
What if Alice and Bob could keep time?
Alice uses 1 lamp for the message:
 At 12 midnight: turns on lamp if message = “yes”
 At 12:01: turns lamp off
Bob needs no lamps!
 Takes down the message between 12 and 12:01
Pros: Fewer signals, lesser processing needed
Cons: Alice and Bob must keep their clocks closely synchronized
 If Bob’s watch is off by a minute, incorrect communication possible
22
Homework #1 (due Thu Aug 23)
 Discuss all scenarios in which Solution #1 can fail
 [Approx. 1 page answer; one “bullet” and a couple of
sentences for each scenario.]
 Are any of those scenarios a problem for Solution #2
as well?
23