Early completion

From Wikipedia, the free encyclopedia

Early completion is a property of some classes of asynchronous circuit. It means that the output of a circuit may be available as soon as sufficient inputs have arrived to allow it to be determined. For example, if all of the inputs to a mux have arrived, and all are the same, but the select line has not yet arrived, the circuit can still produce an output. Since all the inputs are identical, the select line is irrelevant.

[edit] Example: an asynchronous ripple-carry adder

A ripple carry adder is a simple adder circuit, but slow because the carry signal has to propagate through each stage of the adder:

This diagram shows a 5-bit ripple carry adder in action. There is a five-stage long carry path, so every time two numbers are added with this adder, we need to wait for the carry to propagate through all five stages.

By switching to dual-rail signalling for the carry bit, we can have each stage signal its carry out as soon as it knows. If both inputs to a stage are 1, then the carry out will be 1 no matter what the carry in is. If both inputs are 0, then the carry out will be zero. This early completion cuts down on the maximum length of the carry chain in most cases:

We know two of the carry out bits as soon as the input arrives, for the input shown in the picture. This means that the maximum carry chain length is three, not five. If we use dual-rail signalling for inputs and outputs, we can indicate completion as soon as all the carry chains have completed.

On average, an n-bit asynchronous ripple carry adder will finish in O(log n) time. By extending this approach to carry-lookahead adders, it is possible to add in O(log log n) time.