Досрочное завершение

Раннее завершение — свойство некоторых классов асинхронных схем . Это означает, что выход схемы может быть доступен, как только поступит достаточно входных данных, чтобы его можно было определить. Например, если все входы мультиплексора поступили и все одинаковы, но линия выбора еще не прибыла, схема все равно может выдавать выходной сигнал. Поскольку все входные данные идентичны, строка выбора не имеет значения.

Пример: асинхронный сумматор с пульсирующим переносом.

Сумматор со пульсирующим переносом представляет собой простую схему сумматора, но медленную, поскольку сигнал переноса должен распространяться через каждый каскад сумматора:

На этой диаграмме показан 5-битный сумматор с пульсирующим переносом в действии. Существует длинный путь переноса, состоящий из пяти этапов, поэтому каждый раз, когда с помощью этого сумматора складываются два числа, ему необходимо дождаться, пока перенос пройдет через все пять этапов.

Переключившись на двухканальную сигнализацию для бита переноса, он может выполнить сигнал каждого этапа, как только он узнает. Если оба входа на этап равны 1, то перенос будет равен 1 независимо от того, какой входной перенос. Если оба входа равны 0, то выполнение будет равно нулю. Такое раннее завершение в большинстве случаев сокращает максимальную длину несущей цепи:

Два бита выполнения могут быть известны сразу после поступления ввода для ввода, показанного на рисунке. Это означает, что максимальная длина несущей цепи равна трем, а не пяти. Если он использует двухканальную сигнализацию для входов и выходов, он может указать на завершение, как только завершится выполнение всех цепочек переноса.

В среднем n -битный асинхронный сумматор с пульсирующим переносом завершает работу за время O(log n). Расширив этот подход, добавив в него упреждающие сумматоры , можно добавить время O(log log n).

Внешние ссылки

• « Самосинхронные сумматоры с переносом и прогнозированием » Фу-Чиунг Ченг, Стивен Х. Унгер, Майкл Теобальд.