Lecture: Understanding self-timed systems

Ivan Sutherland


The “clocked” paradigm for hardware design insists that the state of each and every part of a system may change only upon the “tick” of a clock. Each clock tick changes the global system state atomically; between clock ticks the global state remains stable. Global state is a convenient mental model for complex digital systems. However, each new circuit technology makes logic faster and communication relatively slower, making atomic changes to a global state harder to approximate. The clocked paradigm focuses attention on global state but lacks reality by ignoring space.

A few research teams, including our own, explore a “self-timed” alternative design paradigm. The self-timed paradigm gains modularity by allowing each task to start as soon as it gets data and to take as much or as little time as it needs for each particular data set. Global state is undefined because concurrent tasks separated in space may change local state at their own convenience. A self-timed system in operation can be as disorderly as a kindergarten playground during recess. How are we to understand, design and test self-timed systems?

Our group distinguishes two kinds of self-timed components that we call Links and Joints. Links form the edges of a directed graph and joints form its nodes. Links don’t compute; they only store and transport data values between joints. Joints don’t store data; they only use data values from their input links to compute new values for their output links. All known circuit families for self-timed systems fit our Link – Joint model.

This talk reports a fully-testable, working, chip experiment to show how our Link – Joint model for self-timed systems simplifies understanding, design, and test. Our Link – Joint model replaces evolving global state by a mental model of data elements moving through a sequence of steps distributed in space. Our Link – Joint model focuses attention on data transport, the most costly part of modern computing equipment.