Early completion
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.
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 look-ahead adder
s, it is possible to add in O(log log n) time.
Asynchronous circuit
An asynchronous circuit is a circuit in which the parts are largely autonomous. They are not governed by a clock circuit or global clock signal, but instead need only wait for the signals that indicate completion of instructions and operations. These signals are specified by simple data transfer...
. It means that the output of a circuit
Electrical network
An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, transmission lines, voltage sources, current sources and switches. An electrical circuit is a special type of network, one that has a closed loop giving a return path for the current...
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
Multiplexer
In electronics, a multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2n inputs has n select lines, which are used to select which input line to send to the output...
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.
Example: an asynchronous ripple-carry adder
A ripple carry adderAdder (electronics)
In electronics, an adder or summer is a digital circuit that performs addition of numbers.In many computers and other kinds of processors, adders are used not only in the arithmetic logic unit, but also in other parts of the processor, where they are used to calculate addresses, table indices, and...
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 look-ahead adder
Carry Look-Ahead Adder
A carry-lookahead adder is a type of adder used in digital logic. A carry-lookahead adder improves speed by reducing the amount of time required to determine carry bits...
s, it is possible to add in O(log log n) time.
External links
- "Self-timed carry-lookahead adders" by Fu-Chiung Cheng, Stephen H. Unger, Michael Theobald.