Когге – Каменная гадюка

В вычислениях сумматор Когге-Стоуна ( KSA или KS ) представляет собой параллельную префиксную форму сумматора с упреждающим переносом . Другие параллельные сумматоры префиксов (PPA) включают сумматор Склански (SA), ^{[ 1 ]} сумматор Брента – Кунга (БКА), ^{[ 2 ]} сумматор Хана – Карлсона (HCA), ^{[ 3 ]}^{[ 4 ]} самый быстрый из известных вариантов - Линча – Шварцлендера сумматор связующего дерева (STA), ^{[ 5 ]}^{[ 6 ]} Сумматор Ноулза (КНА) ^{[ 7 ]} и сумматор Бомонта-Смита (BSA) (например, сумматор Склански (SA), система счисления-4). ^{[ 8 ]}

Сумматор Когге-Стоуна требует больше места для реализации, чем сумматор Брента-Кунга, но имеет меньшее разветвление на каждом этапе, что повышает производительность типичных узлов процесса CMOS. Однако перегрузка проводки часто является проблемой для сумматоров Когге – Стоуна. Конструкция Линча-Шварцландера меньше по размеру, имеет меньшее разветвление и не страдает от перегрузки проводки; однако для использования узел процесса должен поддерживать реализации манчестерской цепочки переноса . Общая проблема оптимизации параллельных сумматоров префиксов идентична многоуровневой задаче оптимизации сумматора переменного размера блока с пропуском переноса , решение которой можно найти в диссертации Томаса Линча 1996 года. ^{[ 6 ]}

Дизайн

Как и все сумматоры с упреждающим переносом, сумматор Когге-Стоуна внутренне отслеживает «генерацию» и «распространение» битов для диапазонов битов. Мы начинаем с 1-битных интервалов, где один столбец в сложении генерирует бит переноса, если оба входа равны 1 (логическое И ), и распространяет бит переноса, если ровно один вход равен 1 (логическое исключающее ИЛИ ). Затем соседние диапазоны объединяются для создания битов генерации и распространения для более широких диапазонов.

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

Разница между различными конструкциями сумматоров с упреждающим переносом заключается в том, как происходит объединение интервалов. В большинстве проектов используется $log 2 n$ этапов, удваивая ширину объединенных пролетов на каждом этапе, но они отличаются тем, как пролеты, размер которых не равен степени двойки, делятся на подпролеты. Конструкция Когге-Стоуна усекает менее значимые промежутки и всегда использует более значимые промежутки полной ширины.

Начиная с 1-битных диапазонов, все соседние диапазоны объединяются для получения 2-битных диапазонов. Наименее значащий диапазон обрабатывается особым образом: он объединяется с переносом в сложение и создает только бит генерации, поскольку распространение невозможно. На следующем этапе каждый 2-битный диапазон объединяется с предыдущим 2-битным диапазоном, чтобы получить 4-битный диапазон. Это за исключением трех наименее значимых пролетов. Наименее значимый диапазон уже вычислен, а следующие два объединяются с переносом и ранее вычисленным наименее значимым диапазоном соответственно, создавая генерируемые биты для 3- и 4-битных диапазонов, включая перенос.

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

Поскольку на следующем этапе каждый диапазон объединяется не более чем с двумя другими диапазонами (один более значимый и один менее значимый), разветвление минимально. Однако наблюдается значительная перегрузка проводки; на предпоследнем этапе 64-битного сумматора для каждой наиболее значимой половины объединяемых диапазонов требуется отдельная генерация и распространение сигналов из диапазонов на расстоянии 16 бит, что требует 32 горизонтальных проводов через сумматор. Заключительный этап аналогичен; хотя необходимы только биты генерации, для пересечения сумматора требуется 32 из них.

Примеры

Пример 4-битного сумматора Когге – Стоуна показан на схеме. Как показано, каждый вертикальный этап создает бит «распространения» и «генерации». Кульминационные биты генерации ( переносы ) создаются на последнем этапе (по вертикали), и эти биты подвергаются операции XOR с начальным распространением после ввода (красные прямоугольники) для получения битов суммы. Например, первый (наименее значимый) бит суммы вычисляется путем выполнения операции XOR распространения в крайнем правом красном поле («1») с переносом («0»), в результате чего получается «1». Второй бит вычисляется путем выполнения XOR распространения во втором блоке справа («0») с C0 («0»), в результате чего получается «0».

Двоичный, система счисления-2, 4-битный

4-битный сумматор Когге-Стоуна, Radix-2, без Cin на Borland Turbo Basic 1.1 :

'--- Step=0 --------------------------------------------
P00 = A0 XOR B0                    '1dt, dt - delay time 
G00 = A0 AND B0                    '1dt
P01 = A1 XOR B1                    '1dt
G01 = A1 AND B1                    '1dt
P02 = A2 XOR B2                    '1dt
G02 = A2 AND B2                    '1dt
P03 = A3 XOR B3                    '1dt
G03 = A3 AND B3                    '1dt
'--- Step=1, Valency-2, Distance=Radix^(Step-1)=2^0
G10 = G00                          '1dt
G11 = G01 OR (P01 AND G00)         '3dt      Distance=2^0=1
P12 = P02 AND P01                  '2dt      Distance=2^0=1
G12 = G02 OR (P02 AND G01)         '3dt      Distance=2^0=1
'     1dt     1dt     1dt
P13 = P03 AND P02                  '2dt      Distance=2^0=1
G13 = G03 OR (P03 AND G02)         '3dt      Distance=2^0=1
'     1dt     1dt     1dt
'--- Step=2, Valency-2, Distance=Radix^(Step-1)=2^1=2
G20 = G10                          '1dt, C1
G21 = G11                          '3dt, C2
G22 = G12 OR (P12 AND G10)         '4dt, C3  Distance=2^1=2
'     3dt     2dt     1dt
G23 = G13 OR (P13 AND G11)         '5dt, C4  Distance=2^1=2
'     3dt     2dt     3dt
'--- Sum ------------------------------
S0 = P00                           '1dt
S1 = P01 XOR G20                   '2dt
S2 = P02 XOR G21                   '4dt
S3 = P03 XOR G22                   '5dt
S4 =         G23                   '5dt. S4=C4=Cout
^[9]

Двоичный, система счисления-2, 4-битный, с Cin

4-битный сумматор Когге-Стоуна, Radix-2, с Cin:

'--- Step Pre -------------------
G0a = A0 AND Cin             '1dt
G0b = B0 AND Cin             '1dt
G0c = A0 AND B0              '1dt
'--- Step 0 ---------------------
P00 = A0 XOR B0              '1dt
G00 = G0a OR G0b OR G0c      '2dt
P01 = A1 XOR B1              '1dt
G01 = A1 AND B1              '1dt
P02 = A2 XOR B2              '1dt
G02 = A2 AND B2              '1dt
P03 = A3 XOR B3              '1dt
G03 = A3 AND B3              '1dt
'--- Step 1 ---------------------
G10 = G00                    '2dt
G11 = G01 OR  P01 AND G00    '4dt
P12 = P02 AND P01            '2dt
G12 = G02 OR  P02 AND G01    '3dt
P13 = P03 AND P02            '2dt
G13 = G03 OR  P03 AND G02    '3dt
'--- Step 2 -------------------------
G20 = G10                    '2dt, C1
G21 = G11                    '4dt, C2
G22 = G12 OR P12 AND G00     '5dt, C3
G23 = G13 OR P13 AND G11     '6dt, C4
'--- Sum ------------------------
S0 = P00 XOR Cin             '2dt
S1 = P01 XOR G20             '3dt
S2 = P02 XOR G21             '5dt
S3 = P03 XOR G22             '6dt
S4 =         G23             '6dt, S4=C4=Cout

Двоичный, система счисления-2, 8-битный

8-битный сумматор Когге-Стоуна, основание системы счисления-2, валентность-2:

'---Step 0 ---------------------
P00 = A0 XOR B0             '1dt
G00 = A0 AND B0             '1dt
P01 = A1 XOR B1             '1dt
G01 = A1 AND B1             '1dt
P02 = A2 XOR B2             '1dt
G02 = A2 AND B2             '1dt
P03 = A3 XOR B3             '1dt
G03 = A3 AND B3             '1dt
P04 = A4 XOR B4             '1dt
G04 = A4 AND B4             '1dt
P05 = A5 XOR B5             '1dt
G05 = A5 AND B5             '1dt
P06 = A6 XOR B6             '1dt
G06 = A6 AND B6             '1dt
P07 = A7 XOR B7             '1dt
G07 = A7 AND B7             '1dt
'--- Step 1, Distance=2^0=1 --------
G10 = G00                   '1dt
G11 = G01 OR (P01 AND G00)  '3dt
P12 = P02 AND P01           '2dt
G12 = G02 OR (P02 AND G01)  '3dt
P13 = P03 AND P02           '2dt
G13 = G03 OR (P03 AND G02)  '3dt
P14 = P04 AND P03           '2dt
G14 = G04 OR (P04 AND G03)  '3dt
P15 = P05 AND P04           '2dt
G15 = G05 OR (P05 AND G04)  '3dt
P16 = P06 AND P05           '2dt
G16 = G06 OR (P06 AND G05)  '3dt
P17 = P07 AND P06           '2dt
G17 = G07 OR (P07 AND G06)  '3dt
'--- Step 2, Distance=2^1=2 ----
G20 = G10                   '1dt
G21 = G11                   '3dt
G22 = G12 OR (P12 AND G10)  '4dt
'     3dt     2dt     1dt
G23 = G13 OR (P13 AND G11)  '5dt
'     3dt     2dt     3dt
P24 = P14 AND P12           '3dt
G24 = G14 OR (P14 AND G12)  '5dt
'     3dt     2dt     3dt
P25 = P15 AND P13           '3dt
G25 = G15 OR (P15 AND G13)  '5dt
'     3dt     2dt     3dt
P26 = P16 AND P14           '3dt
G26 = G16 OR (P16 AND G14)  '5dt
'     3dt     2dt     3dt
P27 = P17 AND P15           '3dt
G27 = G17 OR (P17 AND G15)  '5dt
'     3dt     2dt     3dt
'--- Step 3, Distance=2^2=4 --------
G30 = G20                   '1dt, C1
G31 = G21                   '3dt, C2
G32 = G22                   '4dt, C3
G33 = G23                   '5dt, C4
G34 = G24 OR (P24 AND G20)  '6dt, C5
'     5dt     3dt     1dt
G35 = G25 OR (P25 AND G21)  '6dt, C6
'     5dt     3dt     3dt
G36 = G26 OR (P26 AND G22)  '6dt, C7
'     5dt     3dt     4dt
G37 = G27 OR (P27 AND G23)  '7dt, C8
'     5dt     3dt     5dt
'---Sum ------------------------
S0 = P00                    '1dt
S1 = P01 XOR G30            '2dt
S2 = P02 XOR G31            '4dt
S3 = P03 XOR G32            '5dt
S4 = P04 XOR G33            '6dt
S5 = P05 XOR G34            '7dt
S6 = P06 XOR G35            '7dt
S7 = P07 XOR G36            '7dt
S8 =         G37            '7dt, S8=C8=Cout
^[10]

Двоичный, система счисления-4, 4-битный

4-битный сумматор PPA по основанию-4 (валентность-2,3,4) (это 4-битный сумматор CLA по основанию-4 (валентность-2,3,4) и 4-битный сумматор Склански-4 (валентность-2,3) ,4) сумматор и 4-битный сумматор Когге-Стоуна-4 (валентности-2,3,4) и 4-битный сумматор Бомонта-Смита сумматор по основанию-4 (валентность-2,3,4):

'--- Step 0 ----------
P00 = A0 XOR B0   '1dt
G00 = A0 AND B0   '1dt
P01 = A1 XOR B1   '1dt
G01 = A1 AND B1   '1dt
P02 = A2 XOR B2   '1dt
G02 = A2 AND B2   '1dt
P03 = A3 XOR B3   '1dt
G03 = A3 AND B3   '1dt
'--- Step 1 --------------------------------------------------------
G10 = G00                            '1dt, C1, valency-1, distance-0 
G11 = G01 OR_
      P01 AND G00                    '3dt, C2, valency-2, distance-0,1
G12 = G02 OR_
      P02 AND G01 OR_
      P02 AND P01 AND G00            '3dt, C3, valency-3, distance-0,1,2
G13 = G03 OR_
      P03 AND G02 OR_
      P03 AND P02 AND G01 OR_
      P03 AND P02 AND P01 AND G00    '3dt, C4, valency-4, distance-0,1,2,3
'--- Sum ------------------------------------
S0 = P00         '1dt
S1 = P01 XOR G10 '2dt
S2 = P02 XOR G11 '4dt
S3 = P03 XOR G12 '4dt
S4 =         G13 '3dt, S4=C4=Cout
^[11]

Двоичный, система счисления 4, 8-битный

8-битный сумматор Когге-Стоуна, система счисления-4, валентность-2,3,4:

'--- Step 0 -----------
P00 = A0 XOR B0    '1dt
G00 = A0 AND B0    '1dt
P01 = A1 XOR B1    '1dt
G01 = A1 AND B1    '1dt
P02 = A2 XOR B2    '1dt
G02 = A2 AND B2    '1dt
P03 = A3 XOR B3    '1dt
G03 = A3 AND B3    '1dt
P04 = A4 XOR B4    '1dt
G04 = A4 AND B4    '1dt
P05 = A5 XOR B5    '1dt
G05 = A5 AND B5    '1dt
P06 = A6 XOR B6    '1dt
G06 = A6 AND B6    '1dt
P07 = A7 XOR B7    '1dt
G07 = A7 AND B7    '1dt
'--- Step 1 ---------------------------
G10 = G00                          '1dt
G11 = G01 OR_
      P01 AND G00                  '3dt
G12 = G02 OR_
      P02 AND G01 OR_
      P02 AND P01 AND G00          '3dt
G13 = G03 OR_
      P03 AND G02 OR_
      P03 AND P02 AND G01 OR_
      P03 AND P02 AND P01 AND G00  '3dt
P14 = P04 AND P03 AND P02 AND P01  '2dt
G14 = G04 OR_
      P04 AND G03 OR_
      P04 AND P03 AND G02 OR_
      P04 AND P03 AND P02 AND G01  '3dt
P15 = P05 AND P04 AND P03 AND P02  '2dt
G15 = G05 OR_
      P05 AND G04 OR_
      P05 AND P04 AND G03 OR_
      P05 AND P04 AND P03 AND G02  '3dt
P16 = P06 AND P05 AND P04 AND P03  '2dt
G16 = G06 OR_
      P06 AND G05 OR_
      P06 AND P05 AND G04 OR_
      P06 AND P05 AND P04 AND G03  '3dt
P17 = P07 AND P06 AND P05 AND P04  '2dt
G17 = G07 OR_
      P07 AND G06 OR_
      P07 AND P06 AND G05 OR_
      P07 AND P06 AND P05 AND G04  '3dt
'--- Step 2 -----------------------
G20 = G10                  '1dt, C1
G21 = G11                  '3dt, C2
G22 = G12                  '3dt, C3
G23 = G13                  '3dt, C4
G24 = G14 OR (P14 AND G10) '4dt, C5
G25 = G15 OR (P15 AND G11) '4dt, C6
G26 = G16 OR (P16 AND G12) '4dt, C7
G27 = G17 OR (P17 AND G13) '5dt, C8
'--- Sum --------------------------
S0 = P00                   '1dt
S1 = P01 XOR G20           '2dt
S2 = P02 XOR G21           '4dt
S3 = P03 XOR G22           '4dt
S4 = P04 XOR G23           '4dt
S5 = P05 XOR G24           '5dt
S6 = P06 XOR G25           '5dt
S7 = P07 XOR G26           '5dt
S8 =         G27           '5dt, S8=C8=Cout
^[12]

Двоичный, система счисления-8, 8-битный

8-битный сумматор PPA по основанию 8 с валентностью 2,3,4,5,6,7,8 (это 8-битный сумматор CLA с валентностью 2,3,4,5,6,7,8 и 8-битный сумматор Склански сумматор валентности 2,3,4,5,6,7,8 и 8-битный сумматор Когге-Стоуна валентности 2,3,4,5,6,7,8):

'--- Step 0 ---------------------------
P00 = A0 XOR B0                    '1dt
G00 = A0 AND B0                    '1dt
P01 = A1 XOR B1                    '1dt
G01 = A1 AND B1                    '1dt
P02 = A2 XOR B2                    '1dt
G02 = A2 AND B2                    '1dt
P03 = A3 XOR B3                    '1dt
G03 = A3 AND B3                    '1dt
P04 = A4 XOR B4                    '1dt
G04 = A4 AND B4                    '1dt
P05 = A5 XOR B5                    '1dt
G05 = A5 AND B5                    '1dt
P06 = A6 XOR B6                    '1dt
G06 = A6 AND B6                    '1dt
P07 = A7 XOR B7                    '1dt
G07 = A7 AND B7                    '1dt
'--- Step 1 ---------------------------
G10 = G00                          '1dt
G11 = G01 OR P01 AND G00           '3dt, C2, valency-2, distance-1
G12 = G02 OR_                      '3dt, C3, valency-3, distance-1,2
      P02 AND G01 OR_
      P02 AND P01 AND G00                                         '3-in AND
G13 = G03 OR_                      '3dt, C4, valency-4, distance-1,2,3
      P03 AND G02 OR_
      P03 AND P02 AND G01 OR_
      P03 AND P02 AND P01 AND G00                                 '4-in AND
G14 = G04 OR_                      '3dt, C5, valency-5, distance-1,2,3,4
      P04 AND G03 OR_
      P04 AND P03 AND G02 OR_
      P04 AND P03 AND P02 AND G01 OR_
      P04 AND P03 AND P02 AND P01 AND G00                         '5-in AND
G15 = G05 OR_                      '3dt, C6, valency-6, distance-1,2,3,4,5
      P05 AND G04 OR_
      P05 AND P04 AND G03 OR_
      P05 AND P04 AND P03 AND G02 OR_
      P05 AND P04 AND P03 AND P02 AND G01 OR_
      P05 AND P04 AND P03 AND P02 AND P01 AND G00                 '6-in AND
G16 = G06 OR_                      '3dt, C7, valency-7, distance-1,2,3,4,5,6
      P06 AND G05 OR_
      P06 AND P05 AND G04 OR_
      P06 AND P05 AND P04 AND G03 OR_
      P06 AND P05 AND P04 AND P03 AND G02 OR_
      P06 AND P05 AND P04 AND P03 AND P02 AND G01 OR_
      P06 AND P05 AND P04 AND P03 AND P02 AND P01 AND G00         '7-in AND
G17 = G07 OR_                      '3dt, C8, valency-8, distance-1,2,3,4,5,6,7
      P07 AND G06 OR_
      P07 AND P06 AND G05 OR_
      P07 AND P06 AND P05 AND G04 OR_
      P07 AND P06 AND P05 AND P04 AND G03 OR_
      P07 AND P06 AND P05 AND P04 AND P03 AND G02 OR_
      P07 AND P06 AND P05 AND P04 AND P03 AND P02 AND G01 OR_
      P07 AND P06 AND P05 AND P04 AND P03 AND P02 AND P01 AND G00 '8-in AND
'--- Sum --------------
S0 = P00           '1dt
S1 = P01 XOR G10   '2dt
S2 = P02 XOR G11   '4dt
S3 = P03 XOR G12   '4dt
S4 = P04 XOR G13   '4dt
S5 = P05 XOR G14   '4dt
S6 = P06 XOR G15   '4dt
S7 = P07 XOR G16   '4dt
S8 =         G17   '3dt, S8=C8=Cout
^[13]

Двоичный, 16-битное счисление-16, 32-битное счисление-32, 64-битное счисление-64,...

'--- Step 0 -----------------------------------------------------------
FOR I=0 TO N 'N=15 (31 for radix-32 32-bit, 63 for radix-64 64-bit,...)
  P0[I] = A[I] XOR B[I]  '1dt
  G0[I] = A[I] AND B[I]  '1dt
NEXT I
'--- Step 1 ----------------------------------------------------------
FOR I=0 TO N                        'G1[I]
  G1[I] = 0
  FOR J=0 TO I                      'String J
    OUT1[J] = 1
    FOR K=I TO I-J STEP -1          'Number of up to 16-in AND
      IF K<>I-J THEN
        OUT1[J] = OUT1[J] AND P0[K]   'AND'ing, 2dt
        ELSE
          OUT1[J] = OUT1[J] AND G0[K] 'AND'ing, 2dt
      END IF
    NEXT K
    IF J=0 THEN G1[I] = OUT1[J] ELSE G1[I] = G1[I] OR OUT1[J] 'OR'ing, 3dt 
    'G1[15]=S[16]=C[16]=Cout, 3dt
  NEXT J
NEXT I
'--- Sum -----------------------------
FOR I=0 TO N     'Shift Left 1 bit
  G1[N+1-I] = G1[N-I]
NEXT I
G1[0] = 0
P0[N+1] = 0
FOR I=0 TO N+1
  S[I] = P0[I] XOR G1[I] 'XOR'ing, 4dt (Kogge-Stone, binary, radix-2, 64-bit - 14dt)
NEXT I
^[14]

Скорость сумматоров Когге-Стоуна с параллельными операторами G

Numbers of bits     n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps    s=1 s=2 s=3 s=4  s=5  s=6
Adding time         4dt 6dt 8dt 10dt 12dt 14dt  
Radix-4
Numbers of steps        s=1 s=2 s=2  s=3  s=3   
Adding time             4dt 6dt 6dt  8dt  8dt 
Radix-8   
Numbers of steps            s=1 s=2  s=2  s=2
Adding time                 4dt 6dt  6dt  6dt
Radix-16
Numbers of steps                s=1  s=2  s=2
Adding time                     4dt  6dt  6dt
Radix-32
Numbers of steps                     s=1  s=2
Adding time                          4dt  6dt
Radix-64
Numbers of steps                          s=1
Adding time                               4dt

Скорость сумматоров Когге-Стоуна на инвертирующих КМОП-вентилах

Numbers of bits     n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps    s=1 s=2 s=3 s=4  s=5  s=6
Adding time         5dt 6dt 7dt 8dt  9dt  10dt   
Radix-4
Numbers of steps        s=1 s=2 s=2  s=3  s=3   
Adding time             5dt 6dt 6dt  7dt  7dt
Radix-8   
Numbers of steps            s=1 s=2  s=2  s=2
Adding time                 5dt 6dt  6dt  6dt
Radix-16
Numbers of steps                s=1  s=2  s=2
Adding time                     5dt  6dt  6dt
Radix-32
Numbers of steps                     s=1  s=2
Adding time                          5dt  6dt
Radix-64
Numbers of steps                          s=1
Adding time                               5dt

Скорость сумматоров Когге-Стоуна при инвертировании КМОП-вентилей с парафазными входными битами

Numbers of bits     n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps    s=1 s=2 s=3 s=4  s=5  s=6
Adding time         4dt 5dt 6dt 7dt  8dt  9dt  
Radix-4
Numbers of steps        s=1 s=2 s=2  s=3  s=3   
Adding time             4dt 5dt 5dt  6dt  6dt
Radix-8   
Numbers of steps            s=1 s=2  s=2  s=2
Adding time                 4dt 5dt  5dt  5dt
Radix-16
Numbers of steps                s=1  s=2  s=2
Adding time                     4dt  5dt  5dt  
Radix-32
Numbers of steps                     s=1  s=2
Adding time                          4dt  5dt
Radix-64
Numbers of steps                          s=1
Adding time                               4dt

Скорость сумматоров Когге-Стоуна на неинвертирующих вентилях Ключа

Numbers of bits     n=2 n=4 n=8 n=16 n=32 n=64
Radix-2
Numbers of steps    s=1 s=2 s=3 s=4  s=5  s=6
Adding time         3dt 4dt 5dt 6dt  7dt  8dt
Radix-4
Numbers of steps        s=1 s=2 s=2  s=3  s=3   
Adding time             3dt 4dt 4dt  5dt  5dt 
Radix-8   
Numbers of steps            s=1 s=2  s=2  s=2
Adding time                 3dt 4dt  4dt  4dt
Radix-16
Numbers of steps                s=1  s=2  s=2
Adding time                     3dt  4dt  4dt
Radix-32
Numbers of steps                     s=1  s=2
Adding time                          3dt  4dt
Radix-64
Numbers of steps                          s=1
Adding time                               3dt

Концепция сумматора Когге-Стоуна была разработана Питером М. Когге и Гарольдом С. Стоуном , которые опубликовали ее в основополагающей статье 1973 года под названием « Параллельный алгоритм для эффективного решения общего класса рекуррентных уравнений» . ^{[ 15 ]}

Улучшения

Усовершенствования исходной реализации включают увеличение системы счисления и разреженности сумматора. Система счисления сумматора показывает, сколько результатов предыдущего уровня вычислений используется для генерации следующего. В исходной реализации используется система счисления 2, хотя можно создать систему счисления 4 и выше. Это увеличивает мощность и задержку каждой ступени, но уменьшает количество необходимых ступеней. В так называемом разреженном сумматоре Когге-Стоуна ( SKA ) разреженность сумматора относится к тому, сколько бит переноса генерируется деревом переноса. Генерация каждого бита переноса называется разреженностью-1, генерация каждого другого — разреженностью-2, а каждого четвертого — разреженностью-4. Полученные переносы затем используются в качестве входных сигналов переноса для гораздо более коротких сумматоров с пульсирующим переносом или какой-либо другой конструкции сумматора, которая генерирует окончательные биты суммы. Увеличение разреженности уменьшает общее количество необходимых вычислений и может уменьшить перегрузку маршрутизации.

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

16-битный сумматор Когге-Стоуна валентность-2 без Cin:

 P00 =  A0 XOR  B0               '1dt, S0, dt - type delay time
 G00 =  A0 AND  B0               '1dt, C0
 P10 =  A1 XOR  B1               '1dt   
 G10 =  A1 AND  B1               '1dt
 P20 =  A2 XOR  B2               '1dt 
 G20 =  A2 AND  B2               '1dt  
 P30 =  A3 XOR  B3               '1dt
 G30 =  A3 AND  B3               '1dt
 P40 =  A4 XOR  B4               '1dt
 G40 =  A4 AND  B4               '1dt
 P50 =  A5 XOR  B5               '1dt  
 G50 =  A5 AND  B5               '1dt
 P60 =  A6 XOR  B6               '1dt
 G60 =  A6 AND  B6               '1dt 
 P70 =  A7 XOR  B7               '1dt
 G70 =  A7 AND  B7               '1dt 
 P80 =  A8 XOR  B8               '1dt
 G80 =  A8 AND  B8               '1dt   
 P90 =  A9 XOR  B9               '1dt  
 G90 =  A9 AND  B9               '1dt
P100 = A10 XOR B10               '1dt
G100 = A10 AND B10               '1dt
P110 = A11 XOR B11               '1dt
G110 = A11 AND B11               '1dt  
P120 = A12 XOR B12               '1dt
G120 = A12 AND B12               '1dt
P130 = A13 XOR B13               '1dt 
G130 = A13 AND B13               '1dt
P140 = A14 XOR B14               '1dt  
G140 = A14 AND B14               '1dt
P150 = A15 XOR B15               '1dt 
G150 = A15 AND B15               '1dt

G11 = G10 OR P10 AND G00         '3dt, C1
P21 = P20 AND P10                '2dt
G21 = G20 OR P20 AND G10         '3dt
P31 = P30 AND P20                '2dt
G31 = G30 OR P30 AND G20         '3dt
P41 = P40 AND P30                '2dt 
G41 = G40 OR P40 AND G30         '3dt
P51 = P50 AND P40                '2dt 
G51 = G50 OR P50 AND G40         '3dt
P61 = P60 AND P50                '2dt
G61 = G60 OR P60 AND G50         '3dt
P71 = P70 AND P60                '2dt
G71 = G70 OR P70 AND G60         '3dt
P81 = P80 AND P70                '2dt   
G81 = G80 OR P80 AND G70         '3dt
P91 = P90 AND P80                '2dt 
G91 = G90 OR P90 AND G80         '3dt
P101 = P100 AND P90              '2dt 
G101 = G100 OR P100 AND G90      '3dt 
P111 = P110 AND P100             '2dt  
G111 = G110 OR P110 AND G100     '3dt
P121 = P120 AND P110             '2dt
G121 = G120 OR P120 AND G110     '3dt
P131 = P130 AND P120             '2dt
G131 = G130 OR P130 AND G120     '3dt
P141 = P140 AND P130             '2dt
G141 = G140 OR P140 AND G130     '3dt
P151 = P150 AND P140             '2dt
G151 = G150 OR P150 AND G140     '3dt

G22 = G21 OR P21 AND G00         '4dt, C2
G32 = G31 OR P31 AND G11         '5dt, C3
P42 = P41 AND P21                '3dt
G42 = G41 OR P41 AND G21         '5dt
P52 = P51 AND P31                '3dt
G52 = G51 OR P51 AND G31         '5dt
P62 = P61 AND P41                '3dt
G62 = G61 OR P61 AND G41         '5dt
P72 = P71 AND P51                '3dt
G72 = G71 OR P71 AND G51         '5dt
P82 = P81 AND P61                '3dt
G82 = G81 OR P81 AND G61         '5dt
P92 = P91 AND P71                '3dt
G92 = G91 OR P91 AND G71         '5dt
P102 = P101 AND P81              '3dt
G102 = G101 OR P101 AND G81      '5dt
P112 = P111 AND P91              '3dt  
G112 = G111 OR P111 AND G91      '5dt
P122 = P121 AND P101             '3dt
G122 = G121 OR P121 AND G101     '5dt
P132 = P131 AND P111             '3dt
G132 = G131 OR P131 AND G111     '5dt
P142 = P141 AND P121             '3dt
G142 = G141 OR P141 AND G121     '5dt
P152 = P151 AND P131             '3dt 
G152 = G151 OR P151 AND G131     '5dt

G43 = G42 OR P42 AND G00         '6dt, C4
G53 = G52 OR P52 AND G11         '6dt, C5
G63 = G62 OR P62 AND G22         '6dt, C6
G73 = G72 OR P72 AND G32         '7dt, C7
P83 = P82 AND P42                '4dt
G83 = G82 OR P82 AND G42         '7dt
P93 = P92 AND P52                '4dt
G93 = G92 OR P92 AND G52         '7dt
P103 = P102 AND P62              '4dt
G103 = G102 OR P102 AND G62      '7dt 
P113 = P112 AND P72              '4dt
G113 = G112 OR P112 AND G72      '7dt
P123 = P122 AND P82              '4dt  
G123 = G122 OR P122 AND G82      '7dt
P133 = P132 AND P92              '4dt
G133 = G132 OR P132 AND G92      '7dt
P143 = P142 AND P102             '4dt
G143 = G142 OR P142 AND G102     '7dt
P153 = P152 AND P112             '4dt
G153 = G152 OR P152 AND G112     '7dt

G84 = G83 OR P83 AND G00         '8dt, C8
G94 = G93 OR P93 AND G11         '8dt, C9
G104 = G103 OR P103 AND G22      '8dt, C10
G114 = G113 OR P113 AND G32      '8dt, C11
G124 = G123 OR P123 AND G43      '8dt, C12
G134 = G133 OR P133 AND G53      '8dt, C13
G144 = G143 OR P143 AND G63      '8dt, C14
G154 = G153 OR P153 AND G73      '9dt, C15

S0 = P00                         '1dt
S1 = P10 XOR G00                 '2dt
S2 = P20 XOR G11                 '4dt
S3 = P30 XOR G22                 '5dt
S4 = P40 XOR G32                 '6dt
S5 = P50 XOR G43                 '7dt
S6 = P60 XOR G53                 '7dt
S7 = P70 XOR G63                 '7dt 
S8 = P80 XOR G73                 '8dt
S9 = P90 XOR G84                 '9dt
S10 = P100 XOR G94               '9dt 
S11 = P110 XOR G104              '9dt
S12 = P120 XOR G114              '9dt
S13 = P130 XOR G124              '9dt
S14 = P140 XOR G134              '9dt
S15 = P150 XOR G144              '9dt

Ссылки

^ Логика сложения условной суммы. Склански Дж. Транзакция IRE на электронном компьютере. 1960. с.226.
^ Брент, Ричард Пирс ; Кунг, Сян Те (март 1982 г.). «Обычная схема для параллельных сумматоров» (PDF) . Транзакции IEEE на компьютерах . С-31 (3): 260–264. дои : 10.1109/TC.1982.1675982 . ISSN 0018-9340 . S2CID 17348212 . Архивировано из оригинала 24 сентября 2017 года.
^ Хан, Тэкдон; Карлсон, Дэвид А.; Левитан, Стивен П. (октябрь 1982 г.). «Разработка СБИС высокоскоростных схем сложения малой площади» . Материалы Международной конференции IEEE 1981 года по компьютерному дизайну: СБИС в компьютерах и процессорах . IEEE : 418–422. ISBN 0-81860802-1 .
^ Хан, Тэкдон; Карлсон, Дэвид А. (октябрь 1987 г.). «Быстрые и эффективные по площади сумматоры СБИС». Материалы 8-го симпозиума по компьютерной арифметике . IEEE : 49–56.
^ Линч, Томас Уокер; Шварцлендер-младший, Эрл Э. (август 1992 г.). «Промежуточное дерево переносит упреждающий сумматор». Транзакции IEEE на компьютерах . 41 (8): 931–939. дои : 10.1109/12.156535 .
^ Jump up to: ^а ^б Линч, Томас Уокер (май 1996 г.). «Двоичные сумматоры» (Диссертация). Техасский университет . Архивировано (PDF) из оригинала 14 апреля 2018 г. Проверено 14 апреля 2018 г.
^ Семья змей. Саймон Ноулз. Элемент 14, Ацтекский центр, Бристоль, Великобритания.
^ Проект параллельного префиксного сумматора. Бомонт-Смит А., Ченг-Чью Л. Кафедра электротехники и электроники, Университет Аделаиды, Австралия. 2001 г.
^ https://andserkul.narod.ru/R2KS4.bas ^{[ только URL ]}
^ https://andserkul.narod.ru/R2KS8.bas ^{[ только URL ]}
^ https://andserkul.narod.ru/R4KS4F.bas ^{[ только URL ]}
^ https://andserkul.narod.ru/R4KS8F.bas ^{[ только URL ]}
^ https://andserkul.narod.ru/R8KS8F.bas ^{[ только URL ]}
^ https://andserkul.narod.ru/R16KSFM.bas ^{[ только URL ]}
^ Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. дои : 10.1109/TC.1973.5009159 . S2CID 206619926 .

Дальнейшее чтение

Зейдель, Барт Р. (2006). «Характеристики задержки энергии КМОП-сумматоров». В Оклобдзе - Вожин Г.; Кришнамурт, Рам К. (ред.). Высокопроизводительный энергоэффективный микропроцессор . Серия по интегральным схемам и системам. Дордрехт, Нидерланды: Springer . стр. 147–169. дои : 10.1007/978-0-387-34047-0_6 . ISBN 0-387-28594-6 .

[1] Логика сложения условной суммы. Склански Дж. Транзакция IRE на электронном компьютере. 1960. с.226.

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

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

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

[Lynch-Swartzlander_1991-5] Линч, Томас Уокер; Шварцлендер-младший, Эрл Э. (август 1992 г.). «Промежуточное дерево переносит упреждающий сумматор». Транзакции IEEE на компьютерах . 41 (8): 931–939. дои : 10.1109/12.156535 .

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

[7] Семья змей. Саймон Ноулз. Элемент 14, Ацтекский центр, Бристоль, Великобритания.

[8] Проект параллельного префиксного сумматора. Бомонт-Смит А., Ченг-Чью Л. Кафедра электротехники и электроники, Университет Аделаиды, Австралия. 2001 г.

[9] ttps://andserkul.narod.ru/R2KS4.bas ^{[ только URL ]}

[10] ttps://andserkul.narod.ru/R2KS8.bas ^{[ только URL ]}

[11] ttps://andserkul.narod.ru/R4KS4F.bas ^{[ только URL ]}

[12] ttps://andserkul.narod.ru/R4KS8F.bas ^{[ только URL ]}

[13] ttps://andserkul.narod.ru/R8KS8F.bas ^{[ только URL ]}

[14] ttps://andserkul.narod.ru/R16KSFM.bas ^{[ только URL ]}

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[9]

[10]

[11]

[12]

[13]

[14]

[ 15 ]