Сумматор с пропуском переноса

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

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

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

Худший случай для простого одноуровневого сумматора с пульсирующим переносом возникает, когда условие распространения ^[1] верно для каждой пары цифр $(a_{i},b_{i})$ . Затем перенос распространяется по $n$ -битный сумматор и появляется как перенос после $\tau _{CRA}(n)\approx n\cdot \tau _{VA}$ .

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

Для каждой пары входных битов операнда $(a_{i},b_{i})$ условия распространения $p_{i}=a_{i}\oplus b_{i}$ определяются с помощью XOR-вентиля. Когда все условия распространения истинны , тогда бит переноса $c_{0}$ определяет бит переноса.

Сумматор с n -битным переносом и пропуском состоит из n -битной цепи переноса пульсаций, n -входного И-вентиля и одного мультиплексора.Каждый бит распространения $p_{i}$ , который обеспечивается цепочкой переноса пульсаций, подключен к n -входу И-вентиля. Результирующий бит используется в качестве бита выбора мультиплексора, который переключает либо последний бит переноса, либо последний бит переноса. $c_{n}$ или переноска $c_{0}$ к сигналу о проведении $c_{out}$ .

$s=p_{n-1}\wedge p_{n-2}\wedge \dots \wedge p_{1}\wedge p_{0}=p_{[0:n-1]}$

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

Производительность

Критический путь сумматора переноса-пропуска начинается с первого полного сумматора, проходит через все сумматоры и заканчивается битом суммы. $s_{n-1}$ . Сумматоры переноса-пропуска объединены в цепочку (см. сумматоры блочного переноса-пропуска), чтобы уменьшить общий критический путь, поскольку один $n$ -битный сумматор переноса-пропуска не имеет реального преимущества в скорости по сравнению с $n$ -битный сумматор с пульсирующим переносом.

\tau _{CSA}(n)=\tau _{CRA}(n)

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

T_{SK}=T_{AND}(m)+T_{MUX}

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

T_{CSK}=T_{MUX}=2D

.

Блокировать сумматоры с пропуском переноса

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

Сумматоры с пропуском переноса по блоку состоят из нескольких сумматоров с пропуском переноса. Существует два типа сумматоров с блочным переносом и пропуском.Два операнда $A=(a_{n-1},a_{n-2},\dots ,a_{1},a_{0})$ и $B=(b_{n-1},b_{n-2},\dots ,b_{1},b_{0})$ разделены на $k$ блоки $(m_{k},m_{k-1},\dots ,m_{2},m_{1})$ биты.

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

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

Сумматоры фиксированного размера с переносом блоков и пропуском разделяют $n$ биты входных битов в блоки $m$ бит каждый, что приводит к $k={\frac {n}{m}}$ блоки.Критический путь состоит из волнистого пути и элемента пропуска первого блока, путей пропуска, заключенных между первым и последним блоком, и, наконец, пульсирующего пути последнего блока.

T_{FCSA}(n)=T_{CRA_{[0:c_{out}]}}(m)+T_{CSK}+(k-2)\cdot T_{CSK}+T_{CRA}(m)=3D+m\cdot 2D+(k-1)\cdot 2D+(m+2)2D=(2m+k)\cdot 2D+5D

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

{\frac {dT_{FCSA}(n)}{dm}}=0

2D\cdot \left(2-n\cdot {\frac {1}{m^{2}}}\right)=0

\Rightarrow m_{1,2}=\pm {\sqrt {\frac {n}{2}}}

Реализуемы только положительные размеры блоков.

\Rightarrow m={\sqrt {\frac {n}{2}}}

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

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

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

Используя дополнительные блоки пропуска на дополнительном слое, сигналы распространения блоков $p_{[i:i+3]}$ далее суммируются и используются для выполнения больших пропусков:

p_{[i:i+15]}=p_{[i:i+3]}\wedge p_{[i+4:i+7]}\wedge p_{[i+8:i+11]}\wedge p_{[i+12:i+15]}

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

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

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

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

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

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

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

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

Примечания

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

Ссылки

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

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

Объяснение критического пути сумматора с пропуском переменных

[NB_CSA-1] Сумматор с пропуском переноса часто сокращается как CSA, однако его можно спутать с сумматором с сохранением переноса .

[Parhami_2000-2] Пархами, Бехруз (2000). Компьютерная арифметика: алгоритмы и конструкции аппаратного обеспечения . Издательство Оксфордского университета . п. 108 . ISBN 0-19-512583-5 .

[Lynch_1996-3] Линч, Томас Уокер (май 1996 г.). «Двоичные сумматоры» (Диссертация). Техасский университет . Архивировано (PDF) из оригинала 14 апреля 2018 г. Проверено 14 апреля 2018 г.

[Han-Carlson_Levitan_1981-4] Хан, Тэкдон; Карлсон, Дэвид А.; Левитан, Стивен П. (октябрь 1982 г.). «Разработка СБИС высокоскоростных схем сложения малой площади» . Материалы Международной конференции IEEE 1981 года по компьютерному дизайну: СБИС в компьютерах и процессорах . IEEE : 418–422. ISBN 0-81860802-1 .

[Han-Carlson_1987-5] Хан, Тэкдон; Карлсон, Дэвид А. (октябрь 1987 г.). «Быстрые и эффективные по площади сумматоры СБИС». Материалы 8-го симпозиума по компьютерной арифметике . IEEE : 49–56.

[Brent-Kung_1982-6] Брент, Ричард Пирс ; Кунг, Сян Те (март 1982 г.). «Обычная схема параллельных сумматоров» (PDF) . Транзакции IEEE на компьютерах . С-31 (3): 260–264. дои : 10.1109/TC.1982.1675982 . S2CID 17348212 . Архивировано из оригинала 24 сентября 2017 года.

[Kogge-Stone_1973-7] Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. дои : 10.1109/TC.1973.5009159 . S2CID 206619926 .

[номер 1]

[1]

[2]

[3]

[4]

[5]

[6]