Вид РИД
Изобретение
Изобретение относится к вычислительной технике и предназначено для построения быстродействующих многооперандных параллельно-конвейерных сумматоров, для обработки массивов целых положительных чисел.
Известен итерационный способ суммирования массива целых положительных чисел, при котором первое m-разрядное слагаемое суммируется со вторым m-разрядным слагаемым, затем полученная сумма суммируется с третьим m-разрядным слагаемым и так далее, пока не будет получена (m-поразрядная искомая сумма. Недостаток состоит в том, что, во-первых, при итерационном способе суммирования чисел выполняется n-1 операций суммирования, а с учетом последовательного способа последовательного способа переносов в старшие разряды - количество тактов суммирования равно (m-1)·n. Во-вторых, процесс формирования суммы является последовательным процессом.
Техническим результатом от использования способа организации вычислений суммы n m-разрядных чисел является повышение скорости вычисления за счет замены серии из n арифметических операций сложения m параллельно исполняемыми операциями подсчета количества единичных бит в разрядных срезах, формируемых из разрядов суммируемых чисел. На основании анализа и модификации полученных значений сумм количества единиц во всех разрядных срезах выполняется формирование значения двоичного числа, являющегося значением искомой суммы. В результате количество тактов необходимых для формирования значения суммы массива целых двоичных чисел будет равно (log2n)·m тактов. Таким образом, предлагаемый способ обеспечивает выполнение операции формирования суммы массива n m-разрядных чисел быстрее известного итерационного способа в ((m-1)·n)/((log2n)·m) раз, например, при m=100, n=64 вычисления будут выполняться в 8 раз быстрее.
Описание работы устройства: каждое i-oe двоичное позиционное слагаемое можно представить в виде последовательности бит Ai(am, am-1, …, a2, a1), где m-разрядность числа, i∈[1, n]. Тогда n слагаемых можно представить в виде матрицы:
Способ организации конвейерных вычислений суммы n m-разрядных чисел заключается в параллельном подсчете количества единиц в m двоичных векторах, являющихся столбцами приведенной выше матрицы. В результате формируется m двоичных чисел bi - значений количества единиц в соответствующих n-разрядных векторах, где i∈[1, m].
Младший разряд числа b1 является первым разрядом s1 искомой суммы, затем выполняется сдвиг первого двоичного числа b1 на один разряд вправо, после чего полученный результат суммируется с числом b2, младший разряд полученной суммы является вторым разрядом s2 суммы n m-разрядных исходных чисел.
Затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом b3, младший разряд полученной суммы является третьим разрядом s3 суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы , младший разряд которой является k-м разрядом sk суммы n m-разрядных исходных чисел.
Затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом bk+1, младший разряд полученной суммы является (k+1)-м разрядом sk+1 суммы n m-разрядных исходных чисел. И так далее вычисления продолжаются аналогичным образом до вычисления суммы , младший разряд которой является (m-1)-м разрядом Sm-1 суммы n m-разрядных исходных чисел.
Затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом bm, младший разряд полученной суммы является m-м разрядом sm суммы n m-разрядных исходных чисел.
Затем выполняется сдвиг двоичного числа на один разряд вправо, и в случае, если , то вычисление прекращается, иначе младший разряд является sm+1-м разрядом суммы n m-разрядных исходных чисел.
если , то выполняется сдвиг двоичного числа и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда искомой суммы. В итоге через m тактов сдвига будет сформирована сумма n m-разрядных исходных чисел - число s1, s2, …, sk, …, sm.
Пример: необходимо сложить четыре (m=4) трехбитных (n=3) операнда: a1=111, а2=101, а3=001, а4=111. Запишем их в виде матрицы с элементами ai,j
Параллельно подсчитывается число единиц в столбцах матрицы: b1=100, b2=010, b3=011. Так как младший бит b1 равен нулю, то бит результата s1=0.
Число b1 сдвигается на один разряд вправо и результат сдвига суммируется с числом b2=010. Сумма , ее младший разряд является вторым битом результата s2=0.
Число сдвигается на один разряд вправо и результат сдвига суммируется с числом b3=011. Сумма , ее младший разряд является третьим битом результата s3=1.
Число сдвигается на один разряд вправо и младший разряд результата сдвига является четвертым битом результата s4=0. Так как не равно нулю, то сдвиг повторяется: , младший бит является пятым битом результата s5=1. Так как не равно нулю, то сдвиг повторяется: , после чего операция прекращается, так как равно нулю. В итоге получена искомая сумма (s3,3, s3,2, s3,1, s2,1, s1,1)=10100.
Если принять за время суммирования пары n-разрядных чисел n тактов работы устройства, то время вычисления суммы в устройстве на базе описанного способа равно p-m тактов, где p=log2n, в то время как время суммирования итерационным способом равно m·n тактов. Таким образом, быстродействие устройства на базе описанного способа в n/(log2n) раз выше по сравнению с быстродействием устройства на базе известного итерационного способа суммирования.
Примером построения устройства на базе способа организации вычислений суммы n m-разрядных чисел может служить ее программирование на программируемых логических интегральных схемах (ПЛИС).
На фигуре представлен вариант структурной схемы устройства, реализующего способ организации вычислений суммы n m-разрядных чисел в общем виде, где 1 - счетчик единичный бит в двоичных векторах, 2 - p-разрядный двухплечевой сумматор, где p=log2n, 3 - сдвиговый p-разрядный регистр, a1-an - m-разрядные информационные входы схемы, s1-Sm - одноразрядные информационные выходы схемы, b1-bm - р-разрядные выходы счетчиков 1, - разрядные выходы сумматоров 2.
Способ суммирования n m-разрядных целых положительных двоичных чисел в позиционной системе счисления в суммирующем устройстве, заключающийся в том, что в суммирующем устройстве параллельно выполняется подсчет количества единиц в m n-разрядных двоичных векторах, составленных из первых разрядов n чисел, вторых разрядов n чисел, …, k-х разрядов n чисел, …, m-х разрядов n чисел; в результате параллельного подсчета количества единиц в m двоичных векторах формируется m двоичных чисел - значений количества единиц в соответствующих n-разрядных векторах, причем первое двоичное число b - значение количества единиц в первом n-разрядном векторе, второе двоичное число b - значение количества единиц во втором n-разрядном векторе, …, k-e двоичное число b - значение количества единиц в k-м n-разрядном векторе, …, m-е двоичное число b - значение количества единиц в m-м n-разрядном векторе; младший разряд числа b является первым разрядом s суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа b на один разряд вправо, после чего полученный результат суммируется с числом b, где младший разряд полученной суммы является вторым разрядом s суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы является третьим разрядом s суммы n m-разрядных исходных чисел и так далее вычисления продолжаются аналогичным образом до вычисления суммы , где младший разряд которой является k-м разрядом s суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы является (k+1)-м разрядом s, суммы n m-разрядных исходных чисел и так далее вычисления продолжаются аналогичным образом до вычисления суммы , где младший разряд которой является (m-1)-м разрядом s суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа на один разряд вправо, после чего полученный результат суммируется с числом b, младший разряд полученной суммы является m-м разрядом s суммы n m-разрядных исходных чисел; затем выполняется сдвиг двоичного числа на один разряд вправо, и в случае, если , то вычисление прекращается, иначе младший разряд является s-м разрядом суммы n m-разрядных исходных чисел; если , то выполняется сдвиг двоичного числа и полученное число является значениями старших разрядов искомой суммы, начиная с m+1 разряда искомой суммы; в итоге через m тактов сдвига будет сформирована сумма n m-разрядных исходных чисел - число s, s, …, s, …, s.