WikiDer > Сумматор-скип

Carry-skip adder

А сумматор[nb 1] (также известный как сумматор с байпасом) является сумматор реализация, которая улучшает задержку сумматор с волновым переносом с небольшими усилиями по сравнению с другими сумматорами. Улучшение задержки в наихудшем случае достигается за счет использования нескольких сумматоров с пропуском переноса для формирования сумматора с пропуском блока.

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

Одиночный сумматор с пропуском переноса

Наихудший случай для простого одноуровневого сумматора с переносом пульсаций имеет место, когда условие распространения[1] верно для каждой пары цифр . Затем переносится рябь через -битовый сумматор и отображается как перенос после .

Полный сумматор с дополнительными сигналами генерации и распространения.

Для каждой пары входных битов операнда условия распространения определяются с помощью XOR-гейта. Когда все условия распространения правда, то бит переноса определяет выносной бит.

В п-bit-carry-skip сумматор состоит из п-bit-carry-ripple-chain, а п-входной логический элемент И и один мультиплексор. каждый бит распространения , который обеспечивается цепочкой переноса пульсации, подключен к п-вход И-вентиль. Результирующий бит используется как бит выбора мультиплексора, который переключает либо последний бит переноса. или ручной клади к сигналу выполнения .

Это значительно уменьшает задержку сумматора на его критическом пути, поскольку бит переноса для каждого блока теперь может «пропускать» блоки с группа распространять сигнал, установленный на логическую 1 (в отличие от длинной цепочки переноса с пульсацией, которая требует, чтобы перенос проходил через каждый бит в сумматоре). Количество входов логического элемента И равно ширине сумматора. Для большой ширины это становится непрактичным и приводит к дополнительным задержкам, потому что логический элемент И должен быть построен в виде дерева. Хорошая ширина достигается, когда логика суммы имеет такую ​​же глубину, как и п-вход И-вентиль и мультиплексор.

4-битный сумматор с пропуском переноса.

Спектакль

Критический путь сумматора с пропуском переноса начинается с первого полного сумматора, проходит через все сумматоры и заканчивается на суммирующем бите. . Сумматоры с пропуском переноса объединены в цепочку (см. Сумматоры с пропуском и пропуском блока), чтобы уменьшить общий критический путь, поскольку один -bit Carry-Skip-Adder не имеет реального преимущества в скорости по сравнению с -битный сумматор с переносом пульсации.

Логика пропуска состоит из -вход И-вентиль и один мультиплексор.

Поскольку распространяемые сигналы вычисляются параллельно и становятся доступными раньше, критический путь для логики пропуска в сумматоре пропуска переноса состоит только из задержки, налагаемой мультиплексором (условный пропуск).

.

Сумматоры с пропуском блоков

16-битный сумматор фиксированного блока с пропуском переноса с размером блока 4 бита.

Сумматоры с пропуском переноса состоят из ряда сумматоров с пропуском переноса. Существует два типа сумматоров с пропуском и переносом блоков. и разделены на блоки биты.

  • Почему используются сумматоры с пропуском блоков?
  • Должен ли размер блока быть постоянным или переменным?
  • Фиксированная ширина блока против переменной ширины блока

Сумматоры фиксированного размера с пропуском блока

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

Оптимальный размер блока для заданной ширины сумматора п выводится приравниванием к 0

Возможны только положительные размеры блока

Сумматоры переменного размера с пропуском блоков

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

Многоуровневые сумматоры с пропуском переноса

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

Таким образом, сумматор стал еще быстрее.

Оптимизация переноса

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

Проблема оптимизации пропусков переноса для блоков переменного размера и нескольких уровней для произвольного технологического узла устройства была решена Томасом В. Линчем.[2] Эта ссылка также показывает, что добавление пропуска переноса аналогично добавлению параллельного префикса и, таким образом, связано и для некоторых конфигураций идентично Хан – Карлсон,[3][4] то Брент-Кунг,[5] то Гадюка Когге-Стоуна[6] и ряд других типов сумматоров.

Обзор реализации

Разбив это на более конкретные термины, чтобы построить 4-битный сумматор с обходом переноса, 6 полные сумматоры будет необходимо. Входные шины будут 4-битными. А и 4-битный B, с ручной кладью (CIN) сигнал. На выходе будет 4-битная шина X и сигнал выполнения (COUT).

Первые два полных сумматора суммируют первые два бита. Сигнал переноса от второго полного сумматора () будет управлять сигналом выбора для трех мультиплексоров 2: 1. Второй набор из 2 полных сумматоров добавит последние два бита, предполагая является логическим 0. И последний набор полных сумматоров предполагает, что логическая 1.

Затем мультиплексоры определяют, какой выходной сигнал используется для COUT, и .

Заметки

  1. ^ Сумматор-скип часто сокращенно CSA, однако его можно спутать с переносной сумматор.

использованная литература

  1. ^ Пархами, Бехруз (2000). Компьютерная арифметика: алгоритмы и устройства. Oxford University Press. п.108. ISBN 0-19-512583-5.
  2. ^ Линч, Томас Уокер (май 1996 г.). "Бинарные сумматоры" (Тезис). Техасский университет. В архиве (PDF) из оригинала на 2018-04-14. Получено 2018-04-14.
  3. ^ Хан, Такдон; Карлсон, Дэвид А .; Левитан, Стивен П. (октябрь 1982 г.). «Разработка СБИС высокоскоростной схемы сложения малой площади». Труды 1981 Международная конференция IEEE по компьютерному дизайну: СБИС в компьютерах и процессорах. IEEE: 418–422. ISBN 0-81860802-1.
  4. ^ Хан, Такдон; Карлсон, Дэвид А. (октябрь 1987 г.). «Быстрые СБИС-сумматоры с эффективностью по площади». Труды 8-го симпозиума по компьютерной арифметике. IEEE: 49–56.
  5. ^ Брент, Ричард Пирс; Кунг, Сян Дэ (март 1982 г.). «Обычная раскладка для параллельных сумматоров». Транзакции IEEE на компьютерах. С-31 (3): 260–264. Дои:10.1109 / TC.1982.1675982.
  6. ^ Когге, Питер Майкл; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах. С-22 (8): 786–793. Дои:10.1109 / TC.1973.5009159.

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