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

Описание

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

Известен итерационный способ умножения чисел, представленных в одном из позиционных двоичных форматов с плавающей точкой, определенных стандартом IEEE-754. В этом способе умножение состоит из последовательности сложений с накоплением мантисс сомножителей, которые выполняются последовательно, сложения порядков и сложения по модулю два знаков сомножителей. Последовательность сложений с накоплением мантисс сомножителей выполняется следующим образом. При сдвигах мантиссы множителя освободившиеся разряды заполняются нулями. Если первый бит t-разрядной позиционной мантиссы множителя равен единице, то первое слагаемое является мантиссой множимого, иначе первое слагаемое равно нулю. Если второй бит мантиссы множителя равен единице, то второе слагаемое является мантиссой множимого, сдвинутой на один разряд влево, иначе второе слагаемое равно нулю. К сумме первого и второго слагаемого прибавляется мантисса множимого, сдвинутая на два разряда влево, если второй бит мантиссы множителя равен единице, иначе прибавляется нуль. Затем к полученной сумме прибавляется мантисса множимого, сдвинутая на три разряда влево, если третий бит мантиссы множителя равен единице, иначе прибавляется нуль. И так далее до t-го разряда мантиссы множителя, к накопленной сумме прибавляется мантисса множимого, сдвинутая на ν разрядов влево, если t-й бит мантиссы множителя равен единице, иначе прибавляется нуль. В итоге накопленная сумма является искомым произведением мантисс сомножителей. Далее выполняется сложение смещенных позиционных порядков сомножителей, тем самым получается порядок результата. Знак результата определяется сложением по модулю два знаков сомножителей.

Недостаток итерационного способа умножения позиционных двоичных чисел с плавающей точкой состоит в том, что, во-первых, при умножении мантисс выполняется (t-1) операций суммирования t-разрядных операндов. Если принять, что операция суммирования t-разрядных операндов выполняется за t тактов процессора, то общее время выполнения операции умножения мантисс позиционных операндов с плавающей точкой составит t⋅(t-1) тактов. Во-вторых, процесс формирования суммы является последовательным процессом.

Наиболее близким к заявленному способу является способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах (А.С. RU №2509345. БИ №7, 10.03.2014), в котором операция умножения t-разрядных позиционных мантисс сомножителей заменяется n параллельно выполняемыми операциями умножения q-разрядных знакопозиций чисел в системе счисления в остаточных классах. Недостаток данного способа состоит в том, что необходимо выполнение операции умножения по модулю на каждом вычислительном ядре. Если принять за время суммирования пары q-разрядных чисел q тактов работы процессора, то операция умножения q-разрядных чисел может быть выполнена посредством q⋅(q-1) тактов. Операция умножения по модулю в случае, если произведение также имеет разрядность q, также может быть выполнена за q⋅(q-1) тактов. В случае, если произведение имеет разрядность больше, чем q, необходимо выполнить процедуру нахождения остатка от деления на целое число, что является достаточно трудоемкой операцией.

Техническим результатом применения способа организации выполнения операции умножения двух чисел в модулярно-индексном формате представления с плавающей точкой на универсальных многоядерных процессорах является повышение скорости вычисления за счет замены операции умножения t-разрядных позиционных мантисс сомножителей n параллельно выполняемыми операциями сложения по модулю q-разрядных знакопозиций чисел в индексной системе счисления в остаточных классах, причем q≈t/n. Если принять за время суммирования пары t-разрядных чисел t тактов работы процессора, а за время суммирования пары q-разрядных чисел q тактов работы процессора, то, при условии, что число вычислительных ядер универсального многоядерного процессора не меньше n, а операция сложения по модулю q-разрядных чисел может быть выполнена посредством двух операций сложения q-разрядных чисел, то предельное ускорение вычислений S составляет:

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

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

В позиционных двоичных форматах с плавающей точкой стандарта IEEE-754 любое вещественное число представляется трехэлементным набором:

где М - рациональная мантисса, е - порядок числа, e_min=2-2^w-1 и е_max=2^w-1-1, s - знак числа.

Величина чисел, записанных в таком формате, выражается формулой -1^s⋅М⋅2^е. Машинными представлениями чисел вида (1) являются (w+t+1)-разрядные двоичные векторы

, где разряды с d₁ по d_t отводятся под представление рациональных двоичных мантисс М=d_td_t-1 … d₂d₁, разряды с r₁ по r_w отводятся под представление целочисленных двоичных порядков е, записанных в форме с избытком Е=r_wr_w-1 … r₂r₁=e+e_max, разряд s выражает знак числа.

Определим целочисленную мантиссу М'=d_td_t-1 … d₂d₁ как t-разрядное неотрицательное целое двоичное число, такое, что М=М'⋅2^1-t. Определим перемещенный порядок λ как целое двоичное число со знаком, такое, что λ=е-t+1, где е - w-разрядный порядок числа, представленного в двоичном формате (1).

Зададим n целочисленных положительных q-разрядных оснований системы остаточных классов р_1, р₂, …, р_n, таких, что

q≤k где - наибольший общий делитель для и и , k - размер разрядной сетки процессора.

Целочисленную мантиссу М'=d_td_t-1 … d₂d₁ преобразуем в систему остаточных классов с заданными основаниями р₁, р₂, …, р_n, получая тем самым модулярную мантиссу

где m_i∈[0, p_i-1], i=1, 2, …, n - q-разрядные цифры (модулярные разряды) модулярной мантиссы

q - разрядность оснований р₁, р₂, …, p_n, - операция получения остатка от деления М' на i-е основание р_i.

Определим индекс im числа m следующим образом:

где m∈[1, р-1], im∈[0, р-2], g - первообразный корень р.

Тогда

ind m=im,

ind 0=х,

где m∈[1, р-1], im∈[0, р-2], γ - специальный символ, обозначающий индекс нуля. Индексы вычисляются для каждого основания р_i, i=1, 2, …, n заранее и хранятся в соответствующих таблицах.

Индексы обладают следующими свойствами:

γ+im=im+γ=γ,

Пример. Вычислим индексы для модуля р₁=7. Первообразными корнями числа 7 являются числа 3 и 5. Выберем в качестве первообразного корня число 3. Тогда согласно определению индекса:

, , , , , .

Соответствующие индексы будут равны:

ind 0=7, ind 1=0, ind 2=2, ind 3=1, ind 4=4, ind 5=5, ind 6=3.

Преобразуем полученную модулярную мантиссу в модулярно-индексное представление:

где ind (m_i) - операция выборки данных из таблицы индексов по модулю р_i, im_i ∈{0, 1, 2, …, p_i-2, γ} - q-разрядные индексы (разряды модулярно-индексной мантиссы).

Таким образом, число с плавающей точкой вида (1) можно преобразовать к следующему модулярно-индексному формату:

∈{-1,0,1}],

где

- набор знакопозиций (модулярно-индексных разрядов) модулярно-индексной мантиссы , при этом для представления индекса нуля γ используется значение 2^q-1, ind (0)=2^q-1=111…11₂ (данный код может быть использован, поскольку ни одно из оснований p₁, p₂, …, р_n не равно 2^q), λ - позиционный перемещенный порядок, представляющий собой целое двоичное число со знаком, σ - знак числа (двухразрядное двоичное число со знаком), причем если σ=-1, то число отрицательное, α=1 - положительное, α=0 - машинный ноль.

Диапазон допустимых значений индексных мантисс

в системе остаточных классов с основаниями p₁, p₂, …, p_n определяется интервалом , таким образом, t-разрядная позиционная мантисса М=d_td_t-1 … d₂d₁ может быть представлена в системе остаточных классов набором из n взаимно независимых q-разрядных знакопозиций , причем q≈t/n (для случая, если все основания p_l, р₂, …, р_n q-разрядные).

Примеры преобразования позиционных чисел с плавающей точкой в модулярно-индексный формат: пусть числа представлены в 10-разрядном двоичном формате вида (1), в котором под смещенный порядок Е, отводится четыре бита (максимальный порядок е_max=2^4-1-1=7, соответственно е=Е-7), под дробную часть мантиссы - пять бит (т.е. t=6, причем целая часть d₆ рациональной мантиссы М в явном виде не записана) и под знак числа - один бит. Пусть для представления модулярно-индексных мантисс в модулярно-индексном формате

используются три основания: р₁=7, р₂=13, р₃=31. Предварительно вычисленные индексы для оснований представлены в табл. 1.

Пример 1: необходимо перевести число X=2.25₁₀=[1.125,1,0]=-1⁰⋅1.125⋅2¹, представленное в двоичном формате [M,e,s], в модулярно-индексный формат

С учетом принятых характеристик двоичного формата [М, e,s], число X будет записано в памяти ЭВМ в виде двоичного вектора

. Для его преобразования в модулярно-индексный формат (2) необходимо выполнить следующие действия:

1. Выделить составные части числа X: знак числа s=0, дробная часть рациональной мантиссы d₅ … d₂d₁=00100₂, смещенный (избыточный) порядок Е=1000₂=8.

2. Восстановить целую часть d₆ мантиссы М=d₆d₅ … d₂d₁: d₆=1, т.к. Е>0, следовательно М=1.00100₂.

3. Определить порядок е:е=Е-е_max=8-7=1, т.к. Е>0.

4. Определить знак σ, перемещенный позиционный порядок λ и целочисленную мантиссу М':σ=1,λ=е-t+1=1-6+1=-4, М'=d₆d₅ … d₂d₁=100100₂=36.

5. Найти модулярную мантиссу

: .

6. Найти модулярно-индексную мантиссу

Для этого осуществить выбор индексов по таблицам (табл. 1) (первообразные корни соответственно 3,2,3):

В результате получается число X, представленное в модулярно-индексном формате с плавающей точкой:

Пример 2: необходимо перевести число X=0,013671875₁₀=[0.875, -6,1]=-1¹⋅0.875⋅2^-6 из двоичного формата [M,e,s] в модулярно-индексный формат

С учетом принятых характеристик двоичного формата [M,e,s], число X будет записано в памяти ЭВМ в виде двоичного вектора

Для его преобразования в модулярно-индексный формат (2) необходимо выполнить следующие действия:

1. Выделить составные части числа X: знак числа s=1, дробная часть d_5… d₂d₁=11100₂, смещенный порядок Е=0000₂=0.

2. Восстановить целую часть d₆ мантиссы М=d₆d₅ … d₂d₁: d₆=0, т.к. Е=0, следовательно, М=0.11100₂.

3. Определить порядок е: е=e_min=2-2^4-1=-6, т.к. Е=0.

4. Определить знак σ, перемещенный порядок λ и целочисленную мантиссу М': σ=-1, λ=e-t+1=-6-6+1=-11, М'=d₆d₅ … d₂d₁=011100₂=28.

5. Найти модулярную мантиссу

.

6. Найти модулярно-индексную мантиссу

Для этого осуществить выбор индексов по таблицам (табл. 1) (первообразные корни соответственно 3,2,3):

В результате получается число X, представленное в модулярно-индексном формате с плавающей точкой:

Пусть

- числа, представленные в модулярно-индексном формате с плавающей точкой, где и - модулярно-индексные мантиссы чисел A и В соответственно. Тогда способ умножения С=А⋅В чисел А и В, представленных в модулярно-индексном формате с плавающей точкой (2), на универсальном k-разрядном процессоре, содержащем g вычислительных ядер, определяется следующим образом.

1. Множитель

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

1.1. Если число g вычислительных ядер процессора превышает число n оснований p₁, p₂, …, p_n системы остаточных классов, используемых для представления модулярно-индексных мантисс

и чисел А и В соответственно, то:

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

и модулярно-индексных мантисс и чисел А и В соответственно, а также основание системы остаточных классов р₁, разрядность q которого не превышает размер k разрядной сетки процессора;

- параллельно с этим во второе ядро универсального многоядерного процессора загружают q-разрядные двоичные представления вторых знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также основание системы остаточных классов р₂, разрядность q которого не превышает размер k разрядной сетки процессора;

- и т.д.;

- параллельно с этим в n-е ядро универсального многоядерного процессора загружают q-разрядные двоичные представления n-ых знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также основание системы остаточных классов р_n, разрядность q которого не превышает размер k разрядной сетки процессора;

- параллельно с этим в (n+1)-е ядро универсального многоядерного процессора загружают k-разрядные двоичные порядки λ^А и λ^B, а также знаки σ^А и σ^B чисел А и В соответственно.

1.2. Если число n оснований p₁, p₂, …, p_n системы остаточных классов, используемых для представления модулярно-индексных мантисс

и , равно числу g вычислительных ядер универсального вычислителя либо превышает его, то:

- q-разрядные двоичные представления первых знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также q-разрядное основание системы остаточных классов р₁ загружают в первое ядро универсального многоядерного процессора;

- параллельно с этим q-разрядные двоичные представления вторых знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также q-разрядное основание системы остаточных классов р₂ загружают во второе ядро универсального многоядерного процессора;

- и т.д.;

- параллельно с этим q-разрядные двоичные представления (g-1)-х знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также q-разрядное основание системы остаточных классов р_g-1 загружают в (g-1)-е ядро универсального многоядерного процессора;

- q-разрядные двоичные представления g-х знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также q-разрядное основание системы остаточных классов р_g загружают в первое ядро универсального многоядерного процессора;

- q-разрядные двоичные представления (g+1)-х знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно, а также q-разрядное основание системы остаточных классов р_g+1 загружают во второе ядро универсального многоядерного процессора;

- и т.д., пока не будут загружены n-е знакопозиций

и модулярно-индексных мантисс и чисел А и В соответственно;

- параллельно с этим k-разрядные двоичные порядки λ^А и λ^B, а также знаки σ^А и σ^B чисел А и В соответственно загружают в g-e ядро универсального многоядерного процессора.

2. После того, как множитель

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

2.1. Если число g вычислительных ядер процессора превышает число n оснований p₁, p₂, …, p_n системы остаточных классов, используемых для представления модулярно-индексных мантисс

и чисел А и В соответственно, то:

- в первом вычислительном ядре процессора выполняется операция целочисленного сложения

по модулю p₁-1 q-разрядных двоичных представлений знакопозиций и модулярно-индексных мантисс и чисел А и В соответственно следующим образом:

если

то ,

если

, то ,

если

то

если

, то ,

все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- параллельно с этим во втором вычислительном ядре процессора выполняется операция целочисленного сложения

по модулю р₂-1 q-разрядных двоичных представлений знакопозиций и модулярно-индексных мантисс и чисел А и В соответственно; все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- и т.д.;

- параллельно с этим в n-м вычислительном ядре процессора выполняется операция целочисленного сложения

по модулю р_n-1 q-разрядных двоичных представлений знакопозиций и модулярно-индексных мантисс и чисел А и В соответственно; все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- параллельно с этим в (n+1)-м вычислительном ядре процессора выполняется сложение двоичных порядков λ^А и λ^B, а также умножение σ^C=σ^А⋅σ^B знаков σ^А и σ^B чисел A и В соответственно.

2.2. Если число n оснований p₁, p₂, …, p_n системы остаточных классов используемых для представления модулярно-индексных мантисс

и , равно числу g вычислительных ядер универсального вычислителя либо превышает его, и в каждое j-е вычислительное ядро из первых (g-1) вычислительных ядер процессора загружено w_j знакопозиций и i=0,1, …, w_j-1, то:

- в первом вычислительном ядре процессора последовательно выполняются операции сложения

по модулям p_i⋅(g-1)+1-1, i=0, 1, …, w₁-1, q-разрядных двоичных представлений всех w₁ загруженных в него знакопозиций и , i=0, 1, w₁-1 модулярно-индексных мантисс и чисел А и В соответственно следующим образом:

если

то

если

то

если

то

если

то

все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- параллельно с этим во втором вычислительном ядре процессора последовательно выполняются операции сложения

по модулям p_i⋅(g-1)+2-1, i=0, 1, …, w₂-1, q-разрядных двоичных представлений всех w₂ загруженных в него знакопозиций и w₂-1 модулярно-индексных мантисс и чисел А и В соответственно; все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- и т.д.;

- параллельно с этим в (g-1)-м вычислительном ядре процессора последовательно выполняются операции сложения

по модулям p_{i⋅(g-1)+g-1}-1, i=0, 1, …, w_g-1-1, q-разрядных двоичных представлений всех w_g-1 загруженных в него знакопозиций и i=0, 1, …, w_g-1-1 модулярно-индексных мантисс и чисел A и В соответственно; все операции являются целочисленными и выполняются в позиционной двоичной системе счисления;

- параллельно с этим в g-м вычислительном ядре процессора выполняется сложение двоичных порядков λ^А и λ^B, а также умножение σ^C=σ^А⋅σ^B знаков σ^А и σ^B чисел А и В соответственно.

В результате выполнения данных операций получается произведение

чисел и , представленное в модулярно-индексном формате с плавающей точкой.

Пример. Необходимо выполнить операцию умножения С=А⋅В в модулярно-индексном формате с плавающей точкой на универсальном процессоре, содержащем четыре 5-разрядных вычислительных ядра. Для представления мантисс операндов заданы следующие 5-разрядные основания системы остаточных классов: используется три основания: р₁=7, р₂=13, р₃=31. Р=р₁⋅р₂⋅p₃=2821 - произведение оснований (верхний предел допустимого диапазона представления модулярно-индексных мантисс). Сомножители заданы в модулярно-индексном формате следующим образом:

1. Множитель

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

- в первое ядро загружаем первые знакопозиций

и модулярно-индексных мантисс и а также основание системы остаточных классов р₁=7;

- параллельно с этим во второе ядро загружаем вторые знакопозиций

и модулярно-индексных мантисс и а также основание системы остаточных классов р₂=13;

- параллельно с этим в третье ядро загружаем третьи знакопозиций

и модулярно-индексных мантисс и а также основание системы остаточных классов р₃=31;

- параллельно с этим в четвертое ядро универсального многоядерного процессора загружаем 5-разрядные двоичные порядки λ^А=-4 и λ^A=-11, а также знаки σ^А=1 и σ^B=-1.

2. Так как число вычислительных ядер процессора превышает число оснований p₁, p₂, …, p_n системы остаточных классов, используемых для представления модулярно-индексных мантисс

и чисел А и В соответственно, то операцию умножения выполняем следующим образом:

- в первом вычислительном ядре процессора выполняем операцию целочисленного сложения по модулю р₁-1: Поскольку

,

- параллельно с этим во втором вычислительном ядре процессора выполняем операцию целочисленного сложения по модулю р₂-1:

;

- параллельно с этим в третьем вычислительном ядре процессора выполняем операцию целочисленного сложения по модулю р₃ - 1:

;

- параллельно с этим в четвертом вычислительном ядре процессора выполняем сложение двоичных порядков λ^А и λ^B, а также умножение σ^C=σ^А⋅σ^B знаков σ^А и σ^B чисел А и В соответственно: λ^C=λ^А+λ^B=-4+(-11)=-15, σ^C=σ^А⋅σ^B=1⋅(-1)=-1.

Получен результат

в модулярно-индексном формате с плавающей точкой, соответствующий позиционному числу -1¹⋅1.96875⋅2^-6.

Если принять за время сложения пары q-разрядных остатков q тактов работы универсального процессора, содержащего g k-разрядных вычислительных ядер, причем q≤k, то время вычисления произведения t-разрядных мантисс чисел с плавающей точкой А и В, при t≈q⋅n, при условии, что время вычитания равно времени сложения, по описанному способу равно q+q=2⋅q тактов, тогда как время умножения итерационным способом равно t⋅(t-1)≈q⋅n⋅(q⋅n-1) тактов. Для вычисления порядков и знаков операндов потребуется k+1 тактов: (k-1) такт для суммирования порядков, и 2 такта для суммирования знаков), причем их вычисление будет осуществляться параллельно с вычислением знакопозиций модулярных мантисс, поэтому время на вычисление порядков и знаков результата умножения операндов с плавающей точкой не учитывается. Таким образом, время умножения чисел с плавающей точкой на базе описанного способа в

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

Реферат

Изобретение относится к средствам для выполнения операции умножения чисел, представленных в модулярно-индексном формате с плавающей точкой, на универсальных многоядерных процессорах. Техническим результатом является повышение скорости вычисления. В способе, выполняемом на универсальном многоядерном вычислителе, содержащим q k разрядных вычислительных ядер, осуществляют операции алгебраического умножения и n параллельно выполняемых операций сложения по модулю q-разрядных знакопозиций чисел в индексной системе счисления в остаточных классах, причем q≈t/n. 1 ил., 1 табл.

Формула