Раннее завершение - Early completion

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

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

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

Схема сумматора с переносом пульсации

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

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

Схема сумматора переноса пульсации, нечувствительного к задержке

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

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

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