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

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

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

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

Для каждой пары битов входного операнда условия распространения определяются с помощью XOR-gate. Когда все условия распространения истинны , бит переноса определяет бит переноса.${\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}\клин p_{n-2}\клин \точки \клин p_{1}\клин p_{0}=p_{[0:n-1]}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle p_{[i:i+15]}=p_{[i:i+3]}\клин p_{[i+4:i+7]}\клин p_{[i+8:i+11]}\клин p_{[i+12:i+15]}}$

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

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

Задача оптимизации переноса-пропуска для блоков переменного размера и нескольких уровней для произвольного узла процесса устройства была решена Оклобджией и Барнсом в IBM и опубликована в 1985 году.

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

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

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

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