Early completion

Uses your system voice; voice and rate in settings.

Q5326797Snapshot

≈ 3 min read

Names in other languages

  • EnglishEarly completion

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

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, it needs to wait for the carry to propagate through all five stages. By switching to dual-rail signalling for the carry bit, it 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: Two of the carry-out bits can be known as soon as input arrives, for the input shown in the picture. This means that the maximum carry chain length is three, not five. If it uses dual-rail signalling for inputs and outputs, it 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 adders, 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1049312808 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot early-completion-606605-4835850c9e5ea736 · hash 4835850c9e5ea73609c73b9b208c337a6f984ec9fb1a8d78c3dc849bfa4941cc · captured 1633915358.0 · version history

Cite this page as: encyclopegia.org, “Early completion”, snapshot early-completion-606605-4835850c9e5ea736. https://encyclopegia.org/a/early-completion

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.