СПОСОБ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ СУММЫ N M-РАЗРЯДНЫХ ЧИСЕЛ
METHOD OF CALCULATING SUM N OF M-BIT NUMBERS

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих многооперандных параллельно-конвейерных сумматоров, для обработки массивов целых положительных чисел.
Известен итерационный способ суммирования массива целых положительных чисел, при котором первое m-разрядное слагаемое суммируется со вторым m-разрядным слагаемым, затем полученная сумма суммируется с третьим m-разрядным слагаемым и так далее, пока не будет получена (m-поразрядная искомая сумма. Недостаток состоит в том, что, во-первых, при итерационном способе суммирования чисел выполняется n-1 операций суммирования, а с учетом последовательного способа последовательного способа переносов в старшие разряды - количество тактов суммирования равно (m-1)·n. Во-вторых, процесс формирования суммы является последовательным процессом.
2
2
Техническим результатом от использования способа организации вычислений суммы n m-разрядных чисел является повышение скорости вычисления за счет замены серии из n арифметических операций сложения m параллельно исполняемыми операциями подсчета количества единичных бит в разрядных срезах, формируемых из разрядов суммируемых чисел. На основании анализа и модификации полученных значений сумм количества единиц во всех разрядных срезах выполняется формирование значения двоичного числа, являющегося значением искомой суммы. В результате количество тактов необходимых для формирования значения суммы массива целых двоичных чисел будет равно (logn)·m тактов. Таким образом, предлагаемый способ обеспечивает выполнение операции формирования суммы массива n m-разрядных чисел быстрее известного итерационного способа в ((m-1)·n)/((logn)·m) раз, например, при m=100, n=64 вычисления будут выполняться в 8 раз быстрее.
i
m
m-1
2
1
Описание работы устройства: каждое i-oe двоичное позиционное слагаемое можно представить в виде последовательности бит A(a, a, …, a, a), где m-разрядность числа, i∈[1, n]. Тогда n слагаемых можно представить в виде матрицы:
<mrow><mrow><mo>(</mo><mtable columnalign="left"><mtr><mtd><msub><mi>a</mi><mrow><mn>1,</mn><mi>m</mi></mrow></msub><mo>,</mo><msub><mi>a</mi><mrow><mn>1,</mn><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><mtext> </mtext><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mn>1,1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>a</mi><mrow><mn>2,</mn><mi>m</mi></mrow></msub><mo>,</mo><msub><mi>a</mi><mrow><mn>2,</mn><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><mtext> </mtext><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mn>2,1</mn></mrow></msub></mtd></mtr><mtr><mtd><mtable><mtr><mtd><mrow /></mtd><mtd><mrow /></mtd><mtd><mrow /></mtd><mtd><mo>…</mo></mtd></mtr></mtable></mtd></mtr><mtr><mtd><msub><mi>a</mi><mrow><mi>n</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mo>,</mo><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>,</mo><mtext> </mtext><mo>…</mo><mo>,</mo><msub><mi>a</mi><mrow><mi>n</mi><mn>,1</mn></mrow></msub></mtd></mtr></mtable><mo>)</mo></mrow></mrow>
i
Способ организации конвейерных вычислений суммы n m-разрядных чисел заключается в параллельном подсчете количества единиц в m двоичных векторах, являющихся столбцами приведенной выше матрицы. В результате формируется m двоичных чисел b - значений количества единиц в соответствующих n-разрядных векторах, где i∈[1, m].
1
1
1
2
2
<mrow><msubsup><mi>b</mi><mn>2</mn><mi>s</mi></msubsup></mrow>
Младший разряд числа b является первым разрядом s искомой суммы, затем выполняется сдвиг первого двоичного числа b на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы
является вторым разрядом s суммы n m-разрядных исходных чисел.
<mrow><msubsup><mi>b</mi><mn>2</mn><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mi>k</mi><mi>s</mi></msubsup></mrow>
3
3
k
Затем выполняется сдвиг двоичного числа
на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы
является третьим разрядом s суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы
, младший разряд которой является k-м разрядом s суммы n m-разрядных исходных чисел.
<mrow><msubsup><mi>b</mi><mi>k</mi><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow><mi>s</mi></msubsup></mrow>
k+1
k+1
m-1
Затем выполняется сдвиг двоичного числа
на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы
является (k+1)-м разрядом s суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы
, младший разряд которой является (m-1)-м разрядом S суммы n m-разрядных исходных чисел.
<mrow><msubsup><mi>b</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mi>m</mi><mi>s</mi></msubsup></mrow>
m
m
Затем выполняется сдвиг двоичного числа
на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы
является m-м разрядом s суммы n m-разрядных исходных чисел.
<mrow><msubsup><mi>b</mi><mi>m</mi><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mi>m</mi><mi>s</mi></msubsup><mo>=</mo><mn>0</mn></mrow>
m+1
Затем выполняется сдвиг двоичного числа
на один разряд вправо, и в случае, если
, то вычисление прекращается, иначе младший разряд является s-м разрядом суммы n m-разрядных исходных чисел.
<mrow><msubsup><mi>b</mi><mi>m</mi><mi>s</mi></msubsup><mo>≠</mo><mn>0</mn></mrow>
<mrow><msubsup><mi>b</mi><mi>m</mi><mi>s</mi></msubsup></mrow>
1
2
k
m
если
, то выполняется сдвиг двоичного числа
и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда искомой суммы. В итоге через m тактов сдвига будет сформирована сумма n m-разрядных исходных чисел - число s, s, …, s, …, s.
1
2
3
4
i,j
Пример: необходимо сложить четыре (m=4) трехбитных (n=3) операнда: a=111, а=101, а=001, а=111. Запишем их в виде матрицы с элементами a
<mrow><mrow><mo>(</mo><mrow><mtable><mtr><mtd><mrow><mn>111</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>101</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>001</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>111</mn></mrow></mtd></mtr></mtable></mrow><mo>)</mo></mrow></mrow>
1
2
3
1
1
Параллельно подсчитывается число единиц в столбцах матрицы: b=100, b=010, b=011. Так как младший бит b равен нулю, то бит результата s=0.
1
2
2
<mrow><msubsup><mi>b</mi><mn>1</mn><mo>'</mo></msubsup><mo>=</mo><mn>010</mn></mrow>
<mrow><msubsup><mi>b</mi><mn>2</mn><mi>s</mi></msubsup><mo>=</mo><mn>100</mn></mrow>
Число b сдвигается на один разряд вправо и результат сдвига
суммируется с числом b=010. Сумма
, ее младший разряд является вторым битом результата s=0.
<mrow><msubsup><mi>b</mi><mn>2</mn><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mn>2</mn><mrow><mi>s</mi><mo>'</mo></mrow></msubsup><mo>=</mo><mn>010</mn></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mi>s</mi></msubsup><mo>=</mo><mn>101</mn></mrow>
3
3
Число
сдвигается на один разряд вправо и результат сдвига
суммируется с числом b=011. Сумма
, ее младший разряд является третьим битом результата s=1.
<mrow><msubsup><mi>b</mi><mn>3</mn><mi>s</mi></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo></mrow></msubsup><mo>=</mo><mn>010</mn></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo></mrow></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo><mo>'</mo></mrow></msubsup><mo>=</mo><mn>001</mn></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo><mo>'</mo></mrow></msubsup></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo><mo>'</mo><mo>'</mo></mrow></msubsup><mo>=</mo><mn>000</mn></mrow>
<mrow><msubsup><mi>b</mi><mn>3</mn><mrow><mi>s</mi><mo>'</mo><mo>'</mo><mo>'</mo></mrow></msubsup></mrow>
4
5
3,3
3,2
3,1
2,1
1,1
Число
сдвигается на один разряд вправо и младший разряд результата сдвига
является четвертым битом результата s=0. Так как
не равно нулю, то сдвиг повторяется:
, младший бит является пятым битом результата s=1. Так как
не равно нулю, то сдвиг повторяется:
, после чего операция прекращается, так как
равно нулю. В итоге получена искомая сумма (s, s, s, s, s)=10100.
2
2
Если принять за время суммирования пары n-разрядных чисел n тактов работы устройства, то время вычисления суммы в устройстве на базе описанного способа равно p-m тактов, где p=logn, в то время как время суммирования итерационным способом равно m·n тактов. Таким образом, быстродействие устройства на базе описанного способа в n/(logn) раз выше по сравнению с быстродействием устройства на базе известного итерационного способа суммирования.
Примером построения устройства на базе способа организации вычислений суммы n m-разрядных чисел может служить ее программирование на программируемых логических интегральных схемах (ПЛИС).
2
1
n
1
m
1
m
<mrow><msub><mi>b</mi><mn>1</mn></msub><msup><mrow /><mi>s</mi></msup><mo>−</mo><msub><mi>b</mi><mi>m</mi></msub><msup><mrow /><mi>s</mi></msup><mo>−</mo><mrow><mo>(</mo><mrow><mi>p</mi><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow>
На фигуре представлен вариант структурной схемы устройства, реализующего способ организации вычислений суммы n m-разрядных чисел в общем виде, где 1 - счетчик единичный бит в двоичных векторах, 2 - p-разрядный двухплечевой сумматор, где p=logn, 3 - сдвиговый p-разрядный регистр, a-a - m-разрядные информационные входы схемы, s-S - одноразрядные информационные выходы схемы, b-b - р-разрядные выходы счетчиков 1,
- разрядные выходы сумматоров 2.