Solving the Fundamental Problem of Digital Design A Systematic Review of Design Methods

Martin Delvai Andreas Steininger Vienna University of Technology Institute of Computer Engineering A-1040 Vienna, Austria {delvai, steininger}@[Link]
During the last decade various asynchronous circuit structures and design methods have been proposed that seem to be quite different. In essence, however, all these methods contribute to solving the same fundamental design problem in one way or another. In this paper we use a simple communication model to gure out what this fundamental design problem actually is and to highlight its roots. We show how each of the related sub-problems can be conceptually solved in the time domain and in the information domain. Having this model in mind we nally develop a common framework to classify the most popular asynchronous design methods and gure out which sub-problem they actually solve and in which respect they differ from each other.

Abstract

2. Terminology
2.1. Signal model
We call the input of a Boolean function an input vector. This vector is constituted by a number of individual signals (see Fig. 1). The Boolean function denes a specic mapping from the input vector to an output signal. This mapping is implemented by a logic function unit. We use the term logic function unit in a broader sense to describe the implementation of parallel Boolean functions with a common semantic context (datapath elements like adder, e.g.) as well. We call the smallest unit of information conveyed on a signal a bit, and the (consistent) vector of bits conveyed on an input (or output) vector a data word. A signal can be physically represented by one or more rails, whose logic levels dene the signals logic state. The two mandatory logic states of a signal are high (HI) and low (LO), but states such as NULL or illegal are permissible as well. A signal-level code relates the logic levels of the rails to the logic state of the corresponding signal. For the digital rails we consider here the logic level may be either 0 or 1. In the conventional single-rail encoding a signal is represented by one rail whose logic level is directly mapped to the signal state.
input vector
LOGIC FUNCTION UNIT DW 1 DW 2 DW 3

1. Introduction
Asynchronous design approaches have been studied for many decades, and a lot of publications exist in this eld (see [4][3][1], e.g.). Many of them are dedicated to theoretical properties and abstract design techniques, while relatively few are concerned with implementation issues. A comparison, however, looks completely different, as soon as implementation issues are taken into account as well. Moreover, using one or the other method alone does not solve the whole design problem. It is important to understand which issues are being solved by a particular method and which are not. Therefore the contribution we want to make in this paper is not a new technique, but rather a different namely hardware-related and systematic view on existing techniques. In contrast to existing publications [8][1] where the authors provide an all-in one design solution, we analyze and highlight all subproblems separately. After briey providing the required terminology in Section 2 we identify in Section 3 the fundamental problems of digital design that make the employment of specic design techniques necessary from a hardware point of view. In Section 4 we identify possible conceptual approaches to overcome these problems. In Section 5 we study the synchronous design paradigm and the most relevant clockless design methods in the light of these strategic options, while Section 6 concludes the paper.

output signal
DW m

signal 1 signal 2 signal n DW .. data word rail 1 rail n bit

5V 0V 5V 0V

Figure 1. Signal Model We call an input vector consistent at instant ti , if the states of all its signals belong to the same context at instant ti , i.e. if they represent one single valid data word, and inconsistent otherwise. We call a signal valid at instant ti , if its state at instant ti is the stable output of a logic function performed on a consistent input vector, and invalid otherwise.

2.2. Data ow model

From the point of view of information ow every logic function unit F U is preceded by a data source SRC that provides its input vector, and followed by a data sink SN K that processes its output as illustrated in Fig. 2. Both SN K and SRC represent an abstraction of the remaining circuit and may internally consist of further logic function units. We call a bit bi from the output of F U consumed by SN K at ti , if bi is still properly considered in the ow of information in SN K, regardless of whether bi is overwritten by a subsequent bit bi+1 after ti or not. Usually consumption implies the transfer of the information to a storage element. We call
DATA SOURCE (SRC) TRIGGER SRC FUNCTION UNIT (FU) DATA SINK (SNK) TRIGGER SNK

some point in time ttrgsnk,x = tsnkrdy,x + snk (with snk being the sink safety margin the sink trigger T RGsnk,x event is issued, causing the consumption of DWsnk,x to be actually started at instant tcons,x . We call the interval between ttrgsnk,x and tcons,x the sink trigger delay snktrig . The actual consumption process is assumed to occur during the consumption period cons , such that it is nished at instant tsaf e,x = tcons,x + cons . At instant ttrgsrc,x+1 > tsaf e,x it is safe to request the next data word DWsrc,x+1 from SRC. We call the interval between tsaf e,x and ttrgsrc,x+1 the source safety margin src . Due to the pipeline nature of the data path DWsnk,x does not become inconsistent immediately at ttrgsrc,x+1 but is conserved until the rst signal of DWsrc,x+1 has propagated through F U we call the interval between ttrgsrc,x+1 and the point in time tinvalid when DWf u,x actually gets invalid the invalidation delay invalid .

Figure 2. Data ow model an information ow lossless, if all pertaining bits are properly consumed. We call a signal path Pk lossless, if the information ow along Pk is lossless. To achieve this, SRC and SN K must be triggered appropriately.

3. The Fundamental Design Problem

The fundamental problem of digital logic design consists in ensuring a lossless information ow in the system. Under this fundamental constraint the designer has to coordinate the triggers of source and sink appropriately to attain maximum information throughput and implementation efciency. In context with the timed data ow model presented above, this implies the following fundamental requirements: (i) The source trigger must be controlled such that at the sink a data word is not overwritten by the subsequent one before it has been consumed (issue condition). The condition for this is tinvalid,x > tsaf e,x . According to our model this yields the formal condition src > invalid for the source safety margin. Although a negative src is irritating at rst glance, it simply reects the option to pipeline data words due to the above-mentioned conservation of data during invalid . (ii) The sink trigger must be controlled such that a new data word is latched only after it has become consistent (capture condition). Formally this implies tcons,x > tsnkrdy,x , yielding snk > snktrig as a limit for the sink safety margin. Here the negative limit reects the additional margin we gain from the delayed reaction of the sink trigger.
SRC TRIGGER data consumed ? FU signal valid ? 1 signaln valid ? input vector consistent ? SNK TRIGGER

2.3. Timed data ow model

Considering the temporal relations and delays involved in the data transfer between SRC and SN K (see Fig. 3) we have to extend our model by timing issues. Upon a source
TRG src,x

SRC FU

src

DW src,x

TRG src,x+1

src
DW fu,x TRG snk,x

src
time

proc

SNK

invalid
x

snk

snk snktrg cons

DW snk,x

time

t trgsrc,

1 +1 x x ,x id,x oc,x dy, t gsnk, t ons,x t afe,x t gsrc,x t issue t inval t snkr t pr s c tr tr

time

Figure 3. Timed data ow model trigger event T RGsrc,x a new data word is requested from SRC. As soon as SRC is ready, it will react by issuing DWsrc,x . We call the interval between ttrgsrc,x and the instant tissue,x when DWsrc,x is consistent at the output of SRC the source delay src . Next DWsrc,x propagates to the logic function unit F U where it is processed. The corresponding result, DWf u,x , propagates from the output of F U to the input of SN K, where it is available at tproc,x . We subsume all delays between tissue,x and tproc,x in the processing delay proc . After having propagated through the SN Ks input path (and after a setup time, if applicable) DWsnk,x is nally ready for storage at instant tsnkrdy,x . We denote the interval between tproc,x and tsnkrdy,x as sink delay snk . At 2

Figure 4. Fundamental design problem

3.1. Signal delay and skew

Two constituents of signal delay are commonly distinguished, namely gate delay and interconnect delay. While gate delay is mainly determined by technology and output load, interconnect delay depends on many parameters that

are specic to a given signal path, such as driver strength, capacitance and resistance of potential switch elements or vias along the wire, length and physical arrangement of the particular wire, and capacitance of the connected inputs. In addition, overall signal delay is a function of the operating conditions (supply voltage, temperature). As a consequence of the uncertainties with respect to signal delays no pair of signals will exhibit exactly the same delay. The difference of delays within signals of the same input vector is called skew. Notice that by denition skew distorts the temporal relations between signal transitions. As a result the transition from one data word to the next one will never occur at once. The edges on the individual rails will rather arrive sequentially, creating inconsistent intermediate signals and input vectors

trigger is used as an indirect measure, yielding the condition tT RG SRC,x+1 = tT RG SN K,x + SN K , where SN K = trgsnk + cons + src (1)

For a proper choice of SN K it is necessary to determine trgsnk and cons by means of a delay analysis for a given implementation. Time reference (open loop) An essentially different solution to the issue condition is the use of a rigid time reference for controlling the source trigger. As a consequence the actual instant of data consumption is not explicitly considered during operation any more. Instead, a timing analysis is performed during circuit design to determine a safe temporal position of the source trigger relative to other events (the sink trigger, e.g.) on the same time reference. This approach is characteristic for the synchronous design. In essence this is an open-loop control for the source trigger. Since every unit embedded within a pipeline acts as both sink and source, the time references need to be aligned along the whole pipeline. This suggests to use of one global time reference rather than multiple local references. In principle equation 1 applies here as well. Notice, however, that skew effects within the global time distribution directly map to an uncertainty of trgsnk . In practice the issue condition has turned out to be relatively easily fullled by an appropriate circuit structure (micropipeline, e.g.), while the capture condition is a notorious problem that we will analyze more closely in the following.

3.2. Formal incompleteness of Boolean logic

In essence a Boolean function is a time-free mapping (truth table, e.g.) from an input vector to an output signal. The output continuously reacts to any change of the input there is no such thing as a trigger. This implies that only consistent data words are applied to the logic function. In fact, due to signal delay and skew, this assumption is not fullled in a physical circuit implementation and intermediate states cause invalid outputs (glitches). Boolean logic, however, does neither provide any means for expressing or considering validity or consistency nor for expressing temporal relationships. For this reason Boolean logic is called formally incomplete in [2]. In conclusion, Boolean logic does not solve any of the fundamental requirements, and it is the very task of the design methods to compensate for this shortcoming in one way or another.

4.2. Controlling the Sink Trigger

Time Domain Like above one option here is to establish appropriate temporal relations during the design process and then use a (local or global) time reference for judging consistency and hence for controlling the sink trigger. Having gured out timing issues namely delay and skew as a root of the fundamental design problem, this idea of compensating for their undesired effects directly in the time domain is a consequent solution. However, a xed time reference cannot provide any exibility (other than safety margins) for adapting to the delay variations in a physical implementation. In practice the usual approach here is to determine all relevant delays between ttrgsrc,x and tsnkrdy,x . The sum of these delays (plus the sink safety margin) constitutes the time we have to wait after T RGsrc,x until we can safely apply T RGsnk,x : src = src + proc + snk + snk (2)

4. Strategic Options
We have traced back the fundamental design problem to the ow control: What we need are appropriate triggers for data sources and data sinks.

4.1. Controlling the Source Trigger

Handshake (closed loop) The source can be aided in meeting issue condition by providing it with information on whether the sink has consumed the current data word. A very natural approach to convey this information is to use a dedicated control signal (REQ) for this purpose. In conjunction with a feed-forward signal (ACK) from the source to the sink (see later) a handshake between source and sink can be established, effectively yielding the type of closedloop control for the data ow that is characteristic for all asynchronous design styles. In practice the generation of the REQ signal is somewhat problematic, since normally there is no event directly associated with tsaf e,x . Instead, the sink 3

In conjunction with the above options for the source trigger this yields two different approaches: (see Fig. 5): (a) Closed loop/local: The use of coupled timers that started with the one trigger event generate the respective other trigger event after the appropriate delay.

(b) Open loop/global: The use of a common global time reference from which periodic triggers for both, SRC and SN K are derived with an appropriate phase alignment. These approaches are capable of solving the fundamental deCoupled timer
SRC

Global time reference

TRGsrc,x SRC TRG snk TRGsrc,x+1

Timer SRC TRG src Timer SNK

TRGsnk,x TRGsnk,x+1

time Period

SNK t

t issue,x trgsnk,x t

t trgsnk,x+1 issue,x+1

time

SNK src = src + proc + snk + snk snk = trgsnk + cons + src

= src + proc + snk + snk + = src proc+ snk +snk + trgsnk+ cons+ src

Figure 5. Solutions in the time domain sign problem on all levels, since all delays have passed and the circuit is stable at the trigger instants. In some sense we have thus overcome the formal incompleteness of Boolean logic by using additional control signals. The required information on validity and consistency is condensed in the timer settings (snk , src , or ) that are determined during circuit design. The substantial difference between the two approaches is that the coupled timers are matched to local delays between each source/sink pair, while the use of a global time reference necessitates to consider the entire circuit for calculating and . Notice, however, that both approaches postulate that the input vector will be consistent and all signals valid after a calculated delay. In fact we have no means to directly assess consistency and validity. As a result the determination of the timer settings (in particular the choice of the safety margins) implies a fundamental tradeoff between performance and restrictive assumptions on environment and implementation. Information domain Alternatively we can tackle the formal incompleteness of Boolean logic: (a) Validity of a single signal can be solved by: (i) Ensuring continuous validity: If we can manage to build the logic function unit in such a way that it produces only valid outputs, judgement of the output signals validity becomes obsolete. A function unit of this type must change its output only in response to a consistent input word (Notice that ensuring continuous validity does not enforce continuous consistency, since the combination of valid signals pertaining to a different context does not yield a consistent data word). To this end it must (a) be able to judge on the consistency of the input word or ensure that the input signals are always consistent and (b) avoid spikes at the output signal. The latter can be achieved by using glitch-free logic or by buffering the outputs, hiding in this way invalid transitions. (ii) Extending the signal code Alternatively we can establish a more comprehensive alphabet than the binary Boolean 4

logic (by using more than one rail per signal, e.g.) and dene a subset of all expressible codewords as valid. In contrast to the previous approach, a direct transition from one valid codeword on the rail-level to the next is not mandatory, (invalid) intermediate states are allowed, since they can be identied. The only condition is that if a valid codeword has been reached after a number of single transitions on k of n rails of a signal, there must be no other valid codeword that can be reached by transitions on the remaining n k rails. This allows us to unambiguously identify when a codeword is complete, irrespective of the order in which the transitions occur. The transition to the next codeword must include another transition on at least one of the k rails. This condition though in a different formulation has been given in [10]. (iii) Current sensing: This method exploits the fact that transient effects in a circuit are associated with dynamic current ow. However, it may well happen that one slow rail transition arrives after the circuit has been considered stabilized, or that the lack of an event separating two successive identical data words upsets the ow control. (b) Consistency To judge consistency, a circuit must be able to differentiate between two consecutive bits carried on a signal line, even if they hold the same information. In other words we have to choose a signal-level code that relates information to context. So in order to be applicable for our purpose, a coding scheme must meet two conditions: Consistency Condition 1: Identication of a context switch. There must be at least one indication for a context switch (such as a signal transition) between any two successive code words. While this naturally happens in transition based coding schemes, it requires special efforts in state based coding schemes. A usual solution is to introduce a neutral spacer between any two data words in a return to zero manner. Consistency Condition 2: Identication of membership to contexts. The processing of sequential data words implies, that at least two data words (belonging to a different context) will transiently coexist between SRC and SNK, when the new data word has already been issued and is propagating through the FU, but the previous one is still valid at SNKs input. Therefore, to accommodate for the distortion of the data words wave front by skew effects we need at least two disjoint code sets on the rail level, which allows us to unambiguously assign every bit to different contexts.

4.3. Hybrid solutions

It is not necessary to solve the fundamental design problem in one domain only. Quite on the contrary, many design approaches are based on a hybrid solution. Huffman codes [4], e.g., solve only a part of the fundamental design problem and only their combination with other methods yields the desired result. Furthermore, we have to take into consideration that several design approaches solve the fundamental design problem not only in different domains but also on different

abstraction levels of a circuit implementation. We are not aware of truly delay insensitive implementations of basic library cells , such as AND, OR, latches; i.e. ones that operate properly with arbitrary internal delays. At the same time it is not a problem in practice to enforce timing assumptions like e.g. isochronic fork [5] or fast local feedbacks [2] within such atomic cells. On a higher level it may then be assumed that the basic gates fulll specic requirements with respect to consistency and validity. Under this provision it is possible to build circuits, such as an ALU, for which the fundamental design problem is entirely solved in the information domain (on this higher level of abstraction).

SRC

FU src

SNK

SRC (FF)

FU

SNK (FF)

Figure 6. Delay element vs clock signal

5.3. Micropipeline Approach

Basically micropipelines are a means for structuring complex logic designs in general and data paths in particular. The original concept proposed by Sutherland in [9]
R(in)
C C Pd Cd P

5. Design Techniques
Obviously we cannot cover all existing design techniques. Instead, we analyze some popular approaches in the light of our system model and show how they can be compared.

delay
C C Pd Cd P

delay

R(out)

Reg

Reg

Reg

Data in

Reg

Data out

Cd

Pd

Cd

Pd

5.1. Synchronous Approach

The synchronous approach solves both, the issue condition as well as the capture condition in the time domain, or more precisely by means of a global time reference. This time reference is established by a periodic clock signal that is globally distributed. Consequently all drawbacks of the open loop time controlled approach apply for the synchronous design style. Every active clock transition is directly used for both source trigger and sink trigger (see Fig. 6). So in fact in Fig. 5 is chosen equal to . This allows a remarkably efcient implementation one single-rail signal controls the complete data ow , but only works under certain restrictions. With respect to the capture condition it must be guaranteed by design (static timing analysis) that all signals are valid and consistent one period after the respective source trigger event. With respect to the issue condition src = (snktrg + cons ) must be chosen to facilitate = (see Fig. 5). This is safe only as long as src > invalid still holds, which is quite aggressive but realistic in practice.

A(out)

delay

delay

A(in)

Figure 7. Micropipeline (Fig. 7) solves both, the capture condition and the issue condition in the time domain through the use of local delay elements. It adopts the bundled data approach for the data path. More generally, however, the micropipeline can be viewed as a generic closed loop solution with respect to the issue condition that can be combined with information domain solutions of the capture condition as well (see later).

5.4. Human Approach

Huffman circuits (for a comprehensive review see [7]) are intended to be used for asynchronous state machines. Huffman circuits have primary inputs, primary outputs and a feedback loop from the outputs to the inputs. The current state is stored in the feedback path. The fundamental mode requires that only one input signal (including the feedback) changes at a time. An input change followed by a resulting state change might violate this requirement, if the state change is fed back to the input too soon. Therefore delay elements need to be inserted in the feedback loop. For the same reason only one signal may change when passing from one to the next state. A new transition at a primary input is not allowed before the whole circuit has reached a stable state. thus allowing to ensure continuous validity. The Huffman approach is an important aid in solving the capture condition, but it needs to be complemented by external means to enforce the input restrictions.

5.2. Bundled Data Approach

In the bundled-data approach [8] a single explicit control signal is added to each signal vector, indicating its validity and consistency. This results in a race condition between control signal and data path that can only be mitigated by enforcing that the control path is slower than the data path. Hence, matching delays are inserted in the control path. Bundled-data solves the capture condition in the time domain. In contrast to the synchronous approach it is based on local delays for every source/sink pair rather than a global time reference, and represents a closed loop control. To enforce the issue condition bundled-data needs to be complemented by another method (such as micropipeline). 5

5.5. NCL Null Convention Logic Approach

Null Convention Logic extends the Boolean logic by a socalled NULL state [2]. In particular an NCL signal can assume a DATA state which is either a valid HI or a valid LO, in NCL called TRUE or FALSE, respectively or a

NULL state. For encoding these three states a two-rail signal representation is used. The NULL state does not convey any information, it serves only as a spacer between codewords.
X Y Z
NULL NULL NULL DATA DATA DATA NULL NULL NULL DATA DATA DATA

X Y

NCL Gate

there exists a well established theoretical background, which allows to analyze the circuit and to prove the correct behavior. However, the graphical representation is a high leveldescription of a circuit for projecting this description to a hardware implementation one of the previously described methods must be used.

Figure 8. DATA and NULL wave sequence NCL solves the capture condition entirely in the information domain (no timing assumptions!) and therefore suggests itself for delay insensitive circuits. On the rail level the coding scheme proposed for NCL ensures that only a single rail changes upon a transition from NULL to DATA and vice versa, regardless of the actual data values. As a result consistency on the rail level is maintained even during transitions. On the signal level continuous validity of the output is maintained through the use of so called threshold gates. These ensure that a new input vector is not processed before it is consistent. This, however, also necessitates storage cells in combinational gates. Finally, the use of a multi-valued signal coding with the unique NULL-spacer between DATA words enforces both consistency conditions. The price here is a substantial overhead for the two-rail coding. Moreover NCL does not address the issue condition and must hence be combined with an appropriate strategy such as micropipelines. A similar approach is the Four State Logic (FSL)[6]. Instead of using the NULL spacer it alternates between two different encodings each for TRUE and FALSE.

6. Summary and Conclusion

Based on a simple communication model we have identied two requirements that extend the purely functional description by the temporal aspects of data ow control: The issue condition expresses the need to know whether a data word is valid and consistent before being consumed. The capture condition ensures that a data word is not overwritten by the subsequent one. Both conditions can in principle either be fullled by a global time reference (synchronous logic) or by a local handshake (asynchronous logic). In the latter case the handshake signals can be generated either by coupled timers or by direct assessment of data consistency in the information domain. Solutions in the information domain are (largely) independent from assumptions and hence tend to be more robust. The price is the signicantly increased hardware overhead for multi-valued signal coding and for ensuring validity on signal-level and rail level. We have used this general framework to classify existing approaches. This makes it easier to assess the coverage of a given approach with respect to the fundamental design problem and to gure out efcient combinations that fully utilize the particular strengths of the involved methods.

5.6. Transition Signaling Approach

Transition signaling [8] uses two-rail coding on the signal level. A transition on one rail indicates a HI, a transition on the other rail a LO. This one-hot encoding scheme retains validity on the code level. The neutral state between consecutive codewords is implicitly dened by the absence of transitions. This principle fullls both consistency conditions and hence solves the capture condition in the information domain. The issue condition is not addressed and requires explicit loopback of an acknowledge transition. In this context [5] has shown that the only single-output gates applicable with transition signaling circuits are Muller-C-Gate and inverter. This substantially limits the usability of this scheme in practice.

References
[1] A. Davis and S. M. Nowick. An introduction to asynchronous circuit design. Technical Report UUCS-97-013, University of Utah, Department of Computer Science, 1997. [2] K. M. Fant and S. A. Brandt. Null convention logic: A complete and consistent logic for asynchronous digital circuit synthesis. In Proc. International Conference on Application Specic Systems, Architectures and Processors, 1996. [3] S. Hauck. Asynchronous design methodologies: An Overview. In Proc. of the IEEE, volume 83, 1995. [4] D. A. Huffman. The synthesis of sequential switching circuits. Journal of the Franklin Institute, March/April 1954. [5] A. J. Martin. The limitations to delay-insensitivity in asynchronous circuits. In Proc. of the sixth MIT conference on Advanced research in VLSI, pages 263278. MIT Press, 1990. [6] A. McAuley. Four state asynchronous architectures. IEEE Transactions on Computers, Volume 41(Issue 2), 1992. [7] C. J. Myers. Asynchronous Circuit Design. John Wiley & Sons, inc., 2001. [8] J. Sparso and S. Furber. Principles of Asynchronous Circuit Design. Dimes, 2001. [9] I. E. Sutherland. Micorpipelines. In Communications of the ACM, volume 32, pages 720 738, 1989. [10] T. Verhoeff. Delay-insensitive codesan overview. Distributed Computing, 3(1):18, 1988.

5.7. Graphical Description Approach

There are many possibilities to represent a circuit using a graphical description, such as Petri Nets, STG, I Nets, e.g. [7]. There are differences between representation, working conditions and requirements, but the basic principle is always the same: In contrast to hardware description languages, graphs yield a pictorial high level description of the circuit. The main advantage of such a graphical description is that 6