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

Классы МПК:G06F7/72 с помощью арифметического остатка
G06F7/523 только для умножения
Автор(ы):,
Патентообладатель(и):Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Вятский государственный университет ФГБОУ ВПО "ВятГУ" (RU)
Приоритеты:
подача заявки:
2012-07-27
публикация патента:

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных умножителей. Техническим результатом является повышение скорости вычисления. Способ содержит этапы: осуществляют параллельную запись остатка по основанию p1 множимого в элементы памяти, параллельно выполняют подсчет количества единиц b i в каждом столбце i-ой матрицы, сдвигают двоичное число b1 на один разряд вправо, суммируют с числом b 2, полученную сумму способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 сдвигают на один разряд вправо и суммируют с числом b 3. Аналогичным образом осуществляют сдвиг полученных сумм и суммирование их с последующими числами до получения суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , при этом младший разряд числа b1 является первым разрядом s1 произведения, младший разряд каждой полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является i-ым разрядом произведения. Сдвигают двоичное число способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , младший разряд полученного числа является (2*m)-м разрядом искомого произведения S2*m. В случае если s больше p1, производится коррекция полученного произведения s путем последовательного вычитания из s основания p1 до тех пор, пока s не станет меньше p1, иначе коррекция не производится, аналогично вычисляются и корректируются произведения m-разрядных остатков по остальным основаниям, одновременно суммируют порядки сомножителей, полученная сумма является порядком искомого произведения. 2 ил. способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018

способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018

Формула изобретения

Способ организации умножения двоичных чисел с плавающей запятой, представленных в системе остаточных классов по основаниям p 1, p2, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pk, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pn, заключающийся в том, что в умножающем устройстве:

происходит параллельная запись остатка по основанию p1 множимого в ячейки матрицы на элементах памяти, размерность матрицы составляет (2·m-1) столбцов и m строк, где m - разрядность первого основания системы остаточных классов, причем

в ячейки с 1 по m первой строки матрицы записывается m-разрядный остаток по основанию p1 множимого в том случае, когда первый разряд множителя равен единице, иначе записываются нули,

в ячейки с 2 по m+1 второй строки матрицы записывается m-разрядный остаток по основанию p1 множимого в том случае, когда второй разряд множителя равен единице, иначе записываются нули, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 ,

в ячейки с k по (m+k-1) k-й строки матрицы записывается m-разрядный остаток по основанию p1 множимого в том случае, когда k-й разряд множителя равен единице, иначе записываются нули, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 ,

в ячейки с m по (2·m-1) m-й строки матрицы записывается m-разрядный остаток по основанию p1 множимого в том случае, когда n-й разряд множителя равен единице, иначе записываются нули,

во все остальные ячейки матрицы записываются нули,

затем параллельно выполняется подсчет количества единиц в первом столбце матрицы, втором столбце матрицы, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , k-м столбце матрицы, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , (2·m-1)-м столбце матрицы; в результате параллельного подсчета количества единиц в (2·m-1) столбцах матрицы формируется (2·m-1) двоичных чисел - значений количества единиц в соответствующих m-разрядных столбцах матрицы, причем первое двоичное число b 1 - значение количества единиц в первом m-разрядном столбце матрицы, второе двоичное число b2 - значение количества единиц во втором m-разрядном столбце матрицы, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , k-е двоичное число bk - значение количества единиц в k-м m-разрядном столбце матрицы, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , m-е двоичное число b2·m-1 - значение количества единиц в (2·m-1)-м m-разрядном столбце матрицы;

младший разряд числа b1является первым разрядом s1произведения m-разрядных остатков по основанию p1исходных чисел;

затем выполняется сдвиг двоичного числа b1 на один разряд вправо, после чего полученный результат суммируется с числом b2, где младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является вторым разрядом s2произведения m-разрядных остатков по основанию p1 исходных чисел;

затем выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 на один разряд вправо, после чего полученный результат суммируется с числом b3, младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является третьим разрядом s3произведения m-разрядных остатков по основанию p1 исходных чисел;

и так далее вычисления продолжаются аналогичным образом до вычисления суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , младший разряд которой является k-м разрядом s kпроизведения m-разрядных остатков по основанию p1исходных чисел;

затем выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 на один разряд вправо, после чего полученный результат суммируется с числом bk+1, младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является (k+1)-м разрядом sk+1 произведения m-разрядных остатков по основанию p1 исходных чисел;

и так далее вычисления продолжаются аналогичным образом до вычисления суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 младший разряд которой является (2·m-1)-м разрядом s2·m-1 произведения m-разрядных остатков по основанию p1исходных чисел;

затем выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 на один разряд вправо, и полученное число является значением старшего разряда искомого произведения S2·m ,

в итоге будет сформировано произведение m-разрядных остатков по основаниюp1 исходных чисел - число s1, s2, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , sk, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , S2·m;

в том случае, если s больше p1, производится коррекция полученного произведения s, для невыхода за пределы основания, путем последовательного вычитания из s основания p 1до тех пор, пока s не станет меньше p1, иначе коррекция не производится,

одновременно с вычислением и коррекцией произведения m-разрядных остатков исходных чисел по основанию p1 аналогичным образом вычисляются и корректируются произведения m-разрядных остатков исходных чисел по основаниям p2 , p3, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pk, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pn;

одновременно с вычислением произведения m-разрядных остатков суммируются порядки сомножимых, полученная сумма является порядком искомого произведения.

Описание изобретения к патенту

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных умножителей, обрабатывающих массивы положительных чисел с плавающей запятой в системе остаточных классов (СОК).

Операция умножения производится параллельно по нескольким основаниям pi , их количество n определяется диапазоном P представления чисел: Р=p1*p2*способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 *pn. Представление числа в СОК обеспечивается наименьшими неотрицательными остатками Ai по системе взаимно простых оснований pi (iспособ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 [1,n]).

Числа в системе остаточных классов представляют собой позиционный порядок и мантиссу, состоящую из набора остатков по основаниям pi.

Известен итерационный способ умножения целых чисел с плавающей запятой, который применим к числам, представленным как в позиционной системе счисления, так и в системе остаточных классов. В этом способе умножение сводится к последовательности сложений с накоплением, которые выполняются последовательно. При сдвигах множителя освободившиеся разряды заполняются нулями. Если первый бит m-разрядного множителя равен единице, то первое слагаемое является множимым, иначе первое слагаемое равно нулю. Если второй бит множителя равен единице, то второе слагаемое является множимым, сдвинутым на один разряд влево, иначе второе слагаемое равно нулю. К сумме первого и второго слагаемого прибавляется множимое, сдвинутое на два разряда влево, если второй бит множителя равен единице, иначе прибавляется нуль. Затем к полученной сумме прибавляется множимое, сдвинутое на три разряда влево, если третий бит множителя равен единице, иначе прибавляется нуль. И так далее до k-ого разряда множителя, к накопленной сумме прибавляется множимое, сдвинутое на k разрядов влево, если k-ый бит множителя равен единице, иначе прибавляется нуль. И так далее до m-ого разряда множителя, к накопленной сумме прибавляется множимое, сдвинутое на n разрядов влево, если m-ый бит множителя равен единице, иначе прибавляется нуль. В итоге накопленная сумма является искомым произведением сомножителей. Недостаток состоит, в том что, во-первых, при итерационном способе умножения чисел выполняется m-1 операций суммирования, а с учетом последовательного способа переносов в старшие разряды - количество тактов суммирования равно (m-1)*2*m. Во-вторых, процесс формирования суммы является последовательным процессом.

Техническим результатом от использования способа организации умножения чисел с плавающей запятой, представленных в системе остаточных классов, является повышение скорости вычисления за счет замены серии из m-1 арифметических операций сложения 2*(m-1) параллельно исполняемыми операциями подсчета количества единичных бит в разрядных срезах, формируемых из разрядов множимого. Данная операция выполняется параллельно для всех остатков по основаниям системы остаточных классов, формирующих сомножители. На основании анализа и модификации полученных значений сумм количества единиц во всех разрядных срезах выполняется формирование значения двоичного числа, являющегося значением искомого произведения. В результате количество тактов, необходимых для формирования значения суммы массива целых двоичных чисел - произведения, будет равно (log2m)*2*m тактов. Таким образом, предлагаемый способ обеспечивает выполнение операции формирования произведения быстрее известного итерационного способа в ((m-1)*2*m)/((log2m)*2*m)=(m-1)/log2m раз, например, при m=64 вычисления будут выполняться в 8 раз быстрее.

Описание работы устройства: каждый i-ый двоичный позиционный остаток по основанию pi можно представить в виде последовательности бит Ai(a m, am-1, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , a2, a1), где m - разрядность остатка, iспособ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 [1,n].

Происходит параллельная запись остатка по основанию p1 множимого в ячейки матрицы на элементах памяти, размерность матрицы составляет (2*m-1) столбцов и m строк, где m - разрядность первого основания системы остаточных классов. В ячейки с 1 по m первой строки матрицы записывается m-разрядный остаток по основанию pi множимого в том случае, когда первый разряд множителя равен единице, иначе записываются нули.

В ячейки с 2 по m+1 второй строки матрицы записывается m-разрядный остаток по основанию pi множимого в том случае, когда второй разряд множителя равен единице, иначе записываются нули.

И так далее, в ячейки с k по (m+k-1) k-ой строки матрицы записывается m-разрядный остаток по основанию p1 множимого в том случае, когда k-ый разряд множителя равен единице, иначе записываются нули.

И так далее, в ячейки с m по (2*m-1) второй строки матрицы записывается поразрядный остаток по основанию p1 множимого в том случае, когда m-ый разряд множителя равен единице, иначе записываются нули.

Во все остальные ячейки матрицы записываются нули, в общем виде размещение множимого в ячейках матрицы на элементах памяти выглядит следующим образом:

способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018

Затем производится параллельный подсчет количества единиц в 2*m-1 двоичных векторах, являющихся столбцами приведенной выше матрицы. В результате формируется 2*m-1 двоичных чисел bi - значений количества единиц в соответствующих m-разрядных векторах, где iспособ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 [1,2*m-1].

В результате параллельного подсчета количества единиц в (2*m-1) столбцах матрицы формируется (2*m-1) двоичных чисел - значений количества единиц в соответствующих m-разрядных столбцах матрицы, причем, первое двоичное число b 1 - значение количества единиц в первом m-разрядном столбце матрицы, второе двоичное число b2 - значение количества единиц во втором m-разрядном столбце матрицы, k-ое двоичное число bk - значение количества единиц в k-ом m-разрядном столбце матрицы, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , m-ое двоичное число b2*m-1 - значение количества единиц в (2*m-1)-ом m-разрядном столбце матрицы.

Младший разряд числа b1 является первым разрядом s 1 произведения m-разрядных остатков по основанию p 1 исходных чисел;

затем выполняется сдвиг двоичного числа b1 на один разряд вправо, после чего полученный результат суммируется с числом b2, где младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является вторым разрядом s2 произведения m-разрядных остатков по основанию p1 исходных чисел;

затем выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 на один разряд вправо, после чего полученный результат суммируется с числом b3, младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является третьим разрядом s3 произведения m-разрядных остатков по основанию p1 исходных чисел.

И так далее вычисления продолжаются аналогичным образом до вычисления суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , младший разряд которой является k-м разрядом sk произведения m-разрядных остатков по основанию p1 исходных чисел.

Затем выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , на один разряд вправо, после чего полученный результат суммируется с числом bk+1, младший разряд полученной суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является (k+1)-м разрядом sk+1 произведения m-разрядных остатков по основанию p1 исходных чисел.

И так далее вычисления продолжаются аналогичным образом до вычисления суммы способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , младший разряд которой является (2*m-1)-м разрядом s 2*m-1 произведения m-разрядных остатков по основанию p 1 исходных чисел.

Выполняется сдвиг двоичного числа способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 на один разряд вправо и полученное число является значением старшего разряда искомого произведения s2*m.

В итоге будет сформировано произведение m-разрядных остатков по основанию p1 исходных чисел - число s1 , s2, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , sk, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , s2*m.

Одновременно с вычислением произведения m-разрядных остатков исходных чисел по основанию p1 аналогичным образом вычисляются произведения m-разрядных остатков исходных чисел по основаниям p2, p3 , способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pk, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , pn.

Одновременно с вычислением произведения m-разрядных остатков суммируются порядки сомножимых, полученная сумма является порядком искомого произведения.

Пример: необходимо умножить два бинарных трехбитных (m=3) операнда: множимое a1=111, множитель a2 =101 по основанию p=10001. Запишем их в виде матрицы размерностью m=3 строк и 2*m-1=5 столбцов, в ячейки с 1 по m=3 первой строки записывается множимое, так как первый бит множимого равен единице. В ячейки с 2 по m+1=4 второй строки записываются нули, так как второй бит множимого равен нулю. В ячейки с 3 по 2*m-1=5 третьей строки записывается множимое, так как третий бит множителя равен единице. Во все остальные ячейки матрицы записываются нули:

способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018

Затем параллельно подсчитывается число единиц в столбцах матрицы: b1=001, b2=001, b3=010, b4=001, b5=001. Так как младший бит b1 равен единице, то бит результата s1=1.

Число b1 сдвигается на один разряд вправо и результат сдвига способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 суммируется с числом b2=001. Сумма способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , ее младший разряд является вторым битом результата s 2=1.

Число способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 сдвигается на один разряд вправо и результат сдвига способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 суммируется с числом b3=010. Сумма способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , ее младший разряд является третьим битом результата s 3=0.

Число способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 сдвигается на один разряд вправо и результат сдвига способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 суммируется с числом b4=001. Сумма способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , ее младший разряд является четвертым битом результата s4=0.

Число способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 сдвигается на один разряд вправо и результат сдвига способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 суммируется с числом b5=001. Сумма способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 , ее младший разряд является пятым битом результата s 5=0.

Число способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 сдвигается на один разряд вправо и младший разряд результата сдвига способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 является шестым битом результата s6=1. В итоге получено операндов произведение s=(s6, s5 , s4, s3, s2, s1)=100011. Так как s>p, необходима коррекция произведения, заключающаяся в вычитании из s основания p, то есть s'=s-p=100011-10001=10010, так как s'<p, то s' является искомым произведением исходных операндов по модулю p.

Если принять за время сложения пары m-разрядных остатков m тактов работы устройства, то время вычисления произведения в устройстве на базе описанного способа равно р*2*m тактов, где p=log2m, в то время как время умножения итерационным способом равно 2*(m-1)*m тактов. Таким образом, быстродействие устройства на базе описанного способа в (m-1)/log2m раз выше по сравнению с быстродействием устройства на базе известного итерационного способа умножения.

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

На фиг.1 представлен вариант структурной схемы устройства, реализующего операцию вычисления произведения остатков по основанию в общем виде, где 1 - счетчик единичный бит в двоичных векторах, 2 - р-разрядный двухплечевой сумматор, где p=log2n, 3 - сдвиговый р-разрядный регистр, a1-an - m-разрядные информационные входы схемы, s1-s m - одноразрядные информационные выходы схемы, b1 -bm - р-разрядные выходы счетчиков 1, способ организации умножения чисел с плавающей запятой, представленных   в системе остаточных классов, патент № 2500018 - (р+1)-разрядные выходы сумматоров 2.

На фиг.2 представлен вариант структурной схемы матрицы на элементах памяти для трехбитного остатка (m=3), где 1 - логический элемент И, 2 - информационный триггер с одним входом данных, одним входом синхронизации и одним выходом данных, 3 - информационный вход триггера, 4 - вход синхронизации триггера, 5 - информационный выход триггера, x13 - входы схемы, на которые подается остаток множимого по трехбитному основанию, y1-y3 - входы схемы, на которые подается остаток множителя по трехбитному основанию, ai,j - выходы матрицы на элементах памяти.

Класс G06F7/72 с помощью арифметического остатка

устройство для преобразования из полиномиальной системы классов вычетов в позиционный код -  патент 2513915 (20.04.2014)
способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах -  патент 2509345 (10.03.2014)
устройство для определения знака модулярного числа -  патент 2503995 (10.01.2014)
устройство для сравнения чисел, представленных в системе остаточных классов -  патент 2503992 (10.01.2014)
накапливающий сумматор по модулю -  патент 2500017 (27.11.2013)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2485574 (20.06.2013)
полный одноразрядный сумматор по модулю -  патент 2484519 (10.06.2013)
устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в эвм, функционирующих в системе остаточных классов -  патент 2483346 (27.05.2013)
ячейка однородной вычислительной среды, однородная вычислительная среда и устройство для конвейерных арифметических вычислений по заданному модулю -  патент 2477513 (10.03.2013)
устройство для формирования остатка по произвольному модулю от числа -  патент 2445730 (20.03.2012)

Класс G06F7/523 только для умножения

способ перемножения десятичных чисел -  патент 2525477 (20.08.2014)
устройство предсказания исключительной ситуации "потеря точности" блока операции "умножение с накоплением" -  патент 2498392 (10.11.2013)
способ и устройство умножения чисел в коде "1 из 4" -  патент 2467377 (20.11.2012)
умножитель на два по модулю -  патент 2445681 (20.03.2012)
способ и устройство умножения двоично-десятичных кодов -  патент 2386998 (20.04.2010)
функциональная структура умножителя, в котором входные аргументы имеют формат двоичной системы счисления f(2n), а выходные аргументы сформированы в формате позиционно-знаковой системы счисления f(+/-) -  патент 2373563 (20.11.2009)
устройство для умножения чисел по модулю -  патент 2338241 (10.11.2008)
устройство для умножения чисел по произвольному модулю -  патент 2316042 (27.01.2008)
устройство для умножения чисел по модулю -  патент 2313124 (20.12.2007)
умножитель по модулю -  патент 2299461 (20.05.2007)
Наверх