Перенос пропустить сумматор [NB 1] (также известный как ручной обходной сумматор ) является сумматор реализация , которая улучшает на задержке пульсаций переноса сумматора с небольшим усилием по сравнению с другими сумматоров. Улучшение задержки в наихудшем случае достигается за счет использования нескольких сумматоров с пропуском переноса для формирования сумматора с пропуском блока.
В отличие от других быстрых сумматоров, производительность сумматора с пропуском переноса увеличивается только с некоторыми комбинациями входных битов. Это означает, что повышение скорости носит вероятностный характер .
Одиночный сумматор с пропуском переноса
Наихудший случай для простого одноуровневого сумматора с переносом пульсаций имеет место, когда условие распространения [1] выполняется для каждой пары цифр.. Затем переносится рябь через-битовый сумматор и отображается как перенос после .
Для каждой пары входных битов операнда условия распространения определяются с помощью XOR-гейта. Когда все условия распространения истинны , бит переноса определяет выносной бит.
П -битный-перенос пропустить сумматор состоит из п -битный-кэрри-Пульсации-цепи, п -input И-затвора и одного мультиплексора. Каждый бит распространения, который обеспечивается цепочкой переноса пульсаций, соединен с n- входным логическим элементом И. Результирующий бит используется как бит выбора мультиплексора, который переключает либо последний бит переноса. или ручной клади к сигналу выполнения .
Это значительно снижает задержку сумматора на его критическом пути, поскольку бит переноса для каждого блока теперь может «пропускать» блоки с сигналом группового распространения, установленным на логическую 1 (в отличие от длинной цепочки переноса пульсации, которая потребовала бы перенос до пульсации через каждый бит в сумматоре). Количество входов логического элемента И равно ширине сумматора. Для большой ширины это становится непрактичным и приводит к дополнительным задержкам, потому что логический элемент И должен быть построен в виде дерева. Хорошая ширина достигается, когда логика суммирования имеет ту же глубину, что и n- входной логический элемент И и мультиплексор.
Представление
Критический путь сумматора с пропуском переноса начинается с первого полного сумматора, проходит через все сумматоры и заканчивается на суммирующем бите. . Сумматоры с пропуском переноса объединены в цепочку (см. Сумматоры с пропуском блока), чтобы уменьшить общий критический путь, поскольку один-bit Carry-Skip-Adder не имеет реального преимущества в скорости по сравнению с -битный сумматор с переносом пульсации.
Логика пропуска состоит из -вход И-вентиль и один мультиплексор.
Поскольку распространяемые сигналы вычисляются параллельно и становятся доступными раньше, критический путь для логики пропуска в сумматоре пропуска переноса состоит только из задержки, налагаемой мультиплексором (условный пропуск).
- .
Сумматоры с пропуском блоков
Сумматоры с пропуском переноса состоят из ряда сумматоров с пропуском переноса. Есть два типа сумматоров с пропуском и переносом блоков Два операнда а также разделены на блоки биты.
- Почему используются сумматоры с пропусканием и пропуском блоков?
- Должен ли размер блока быть постоянным или переменным?
- Фиксированная ширина блока по сравнению с переменной шириной блока
Сумматоры фиксированного размера с пропуском блока
Сумматоры фиксированного размера с пропуском блоков разделяют биты входных битов в блоки бит каждый, в результате блоки. Критический путь состоит из волнового пути и элемента пропуска первого блока, путей пропуска, заключенных между первым и последним блоком, и, наконец, волнового пути последнего блока.
Оптимальный размер блока для заданной ширины сумматора n получается приравниванием к 0
Возможны только положительные размеры блока
Сумматоры переменного размера с пропуском блоков
Производительность может быть улучшена, т. Е. Все переносы распространяются быстрее, изменяя размеры блоков. Соответственно, начальные блоки сумматора делаются меньше, чтобы быстро обнаруживать генерации переноса, которые необходимо распространять дальше, средние блоки делаются больше, потому что они не являются проблемным случаем, а затем наиболее значимые блоки снова делаются меньшими, чтобы опоздавшие вводы переноса могут быть обработаны быстро.
Многоуровневые сумматоры с пропуском переноса
Используя дополнительные пропускаемые блоки на дополнительном уровне, сигналы блочного распространения далее суммируются и используются для выполнения больших пропусков:
Таким образом, сумматор стал еще быстрее.
Оптимизация переноса
Проблема определения размеров блоков и количества уровней, необходимых для создания физически самого быстрого сумматора с пропуском переноса, известна как «проблема оптимизации сумматора с пропуском переноса». Эта проблема усложняется тем фактом, что сумматоры с пропуском переноса реализованы с помощью физических устройств, размер и другие параметры которых также влияют на время сложения.
Проблема оптимизации пропусков переноса для блоков переменного размера и нескольких уровней для произвольного технологического узла устройства была решена Томасом В. Линчем. [2] Эта ссылка также показывает , что перенос пропустить добавление такой же , как параллельный префикс Кроме того , и, таким образом , связана с, а для некоторых конфигураций , идентичных Han-Carlson , [3] [4] Брент-кунг , [5] Kogge-камень сумматор [6] , а также ряд других типов сумматора.
Обзор реализации
Если разбить это на более конкретные термины, то для создания 4-битного сумматора с обходом переноса потребуется 6 полных сумматоров . Входные шины будут 4-битными A и 4-битными B с сигналом переноса ( CIN ). На выходе будет 4-битная шина X и сигнал переноса ( COUT ).
Первые два полных сумматора суммируют первые два бита. Сигнал переноса от второго полного сумматора () будет управлять сигналом выбора для трех мультиплексоров 2: 1. Второй набор из 2 полных сумматоров добавит последние два бита, предполагая является логическим 0. И последний набор полных сумматоров предполагает, что логическая 1.
Затем мультиплексоры определяют , какой выходной сигнал используется для COUT , а также .
Заметки
- ^ Сумматор с пропуском переноса часто обозначается сокращенно как CSA, однако его можно спутать с сумматором с сохранением переноса .
Рекомендации
- ^ Parhami, Behrooz (2000). Компьютерная арифметика: алгоритмы и устройства . Издательство Оксфордского университета . п. 108 . ISBN 0-19-512583-5.
- ^ Линч, Томас Уокер (май 1996). «Бинарные сумматоры» (дипломная работа). Техасский университет . Архивировано (PDF) из оригинала на 2018-04-14 . Проверено 14 апреля 2018 .
- ^ Хан, Такдон; Карлсон, Дэвид А .; Левитан, Стивен П. (октябрь 1982 г.). «Проектирование СБИС высокоскоростной схемы сложения малой площади» . Труды 1981 Международная конференция IEEE по компьютерному дизайну: СБИС в компьютерах и процессорах . IEEE : 418–422. ISBN 0-81860802-1.
- ^ Хан, Такдон; Карлсон, Дэвид А. (октябрь 1987 г.). "Быстрые СБИС-сумматоры с эффективностью по площади". Материалы 8-го симпозиума по компьютерной арифметике . IEEE : 49–56.
- ^ Брент, Ричард Пирс ; Кунг, Сян Дэ (март 1982 г.). «Штатная раскладка для параллельных сумматоров» . Транзакции IEEE на компьютерах . С-31 (3): 260–264. DOI : 10.1109 / TC.1982.1675982 .
- ^ Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. DOI : 10.1109 / TC.1973.5009159 .