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

Арифметико-логическая схема

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle T_{SK}=T_{AND}(m)+T_{MUX}}$

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

${\displaystyle T_{CSK}=T_{MUX}=2D}$.

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

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

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

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

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

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

${\displaystyle 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

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

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

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

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

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

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

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

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

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

${\displaystyle 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] В этой ссылке также показано, что добавление переноса-пропуска аналогично параллельному добавлению префиксов и, таким образом, связано, а для некоторых конфигураций, идентичных Хану-Карлсону, ^{[3] [4]} Бренту -Кунгу , ^[5] сумматор Когге -Стоуна ^[6] и ряд других типов сумматоров.

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

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

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

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

Примечания

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

Рекомендации

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

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

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