Устройство для основного деления модулярных чисел в формате системы остаточных классов

Устройство для основного деления модулярных чисел в формате системы остаточных классов

Иллюстрации

Показать все

Реферат

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

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

Известно изобретение «Нейронная сеть для деления чисел, представленных в системе остаточных классов» (патент RU 2318239, G06F, опубл. 27.02.2008), содержащее нейронную сеть для расширения кортежа числовой системы вычетов, нейронные сети конечного кольца для суммирования и умножения.

Недостатком устройства является низкая скорость деления чисел и ограниченная функциональная возможность, так как в качестве делителя выбирается один их модулей системы остаточных классов (СОК).

Наиболее близкой к данному изобретению является «Нейронная сеть основного деления модулярных чисел» (патент RU 2400813, G06F 3/02, G06F 7/72, опубл. 27.04.2010). Недостатком устройства является большой объем оборудования. Известная нейронная сеть предназначена для деления модулярных чисел в случае, когда в качестве делителя используется целое положительное число, попарно простое с p₁, p₂, …, p_n, либо целое положительное число, представляющее собой произведение чисел, попарно взаимно простых с p_i. Для выполнения этого условия возникает необходимость нахождения приблизительного делителя путем использования обобщенной позиционной системы счисления (ОПСС). При вычислении приблизительного делителя нарушается регулярность структуры устройства деления, так как используются модульные и немодульные операции.

Техническим результатом данного изобретения является упрощение устройства за счет использования регулярной структуры, расширения функциональных возможностей и сокращения оборудования, что позволяет использовать предложенное изобретение в динамике вычислительного процесса. Указанный технический результат достигается тем, что устройство использует только модульные операции, то есть вычисления выполняются параллельно, в формате СОК. Предлагается устройство для основного деления модулярных чисел в формате системы остаточных классов, содержащее входные регистры делимого и делителя, выходы которых коммутируются мультиплексором для поочередного преобразования делимого и делителя, представленных в основной СОК, во вспомогательную СОК, выход мультиплексора соединен со входом блока расширения, расширяющего базу СОК, выход которого соединен со входом демультиплексора, выходы которого соединены с регистрами хранения остатков по расширенным основаниям, выход регистра делимого по расширенным основаниям соединен со входом умножителя, а выходы регистра делителя соединены с LUT-таблицей, преобразующей делитель по расширенным основаниям в мультипликативную инверсию, выходы которой соединены с умножителем, где реализуется вычислительная модель c i ' = a i ' b i ' − 1 , где a i ' ≡ ( a   mod   p i ) mod   p i ' , b i ' ≡ ( b   mod   p i ) mod   p i ' , a - делимое, b - делитель, b i ' − 1 - мультипликативная инверсия делителя b i ' , p_i - основные модули СОК, p i ' - модули вспомогательной СОК, а выходы умножителя соединены через мультиплексор со входом блока расширения для перехода от вспомогательной СОК к основной СОК, выход которого через демультиплексор соединен с регистрами хранения значений b″^-1 и c, где b i " − 1 ≡ b i ' − 1   mod p i и c i ≡ c i '   mod p i , представленных в основной СОК, выходы регистра b″^-1 соединены с первыми входами умножителей, на вторые входы которого поступают соответственно делимое и делитель, где реализуется вычислительная модель a i b i " − 1 и b i b i " − 1 , выходы которых соединены через схемы ключей с входными регистрами делимого и делителя соответственно, а также с первыми входами схем вычитания и умножения, а на вторые входы которых, соответственно, поступают данные регистра с и константа 1, на третьи входы поступает q i − 1 , где реализуются вычислительные модели ( a i b i " − 1 − c i ) ⋅ q i − 1 и ( b i b i " − 1 − 1 ) ⋅ q i − 1 , где q i = ( ∏ i = 1 m p i ' ) mod p i , q i − 1 - мультипликативная инверсия q_i, выходы которых подключены, соответственно, к выходному ключу и схеме сравнения с единицей, если результат схемы сравнения равен 1, то подается управляющий сигнал на вход выходного ключа, на выходе которого формируется результат деления (частное), в противном случае, если результат сравнения не равен 1, то формируется управляющий сигнал, который открывает схемы ключей, выходы которых подключены к входным регистрам делимого и делителя, представленных в основной СОК.

Устройство для основного деления модулярных чисел в формате системы остаточных классов содержит: входные шины для подачи делимого, шина 1, входные шины для подачи делителя, шина 2, и выходную шину частного, шина 53; регистр делимого 3 и регистр делителя 4; мультиплексор 5 для коммутации делимого и делителя на вход блока расширения 6, который коммутирует шины 28 и 29 на шину 30, являющуюся входом блока расширения 6, который преобразует делимое и делитель из основной системы оснований во вспомогательную систему оснований; демультиплексор 7 коммутирует выход блока расширения 6, шина 32, на вход 34 регистра делимого 8 и вход 35 регистра делителя 9, которые временно хранят делимое и делитель, представленные во вспомогательной СОК; умножитель 11, который выполняет операцию умножения делимого и мультипликативной инверсии делителя, представленных во вспомогательной СОК, поданных соответственно по шинам 36 и 37, 38 через LUT-таблицу 10, в которой происходит выборка мультипликативной инверсии делителя; шины 38 и 39 подаются на вход мультиплексора 12, который поочередно их коммутирует на выход 40, являющийся входом блока расширения 13, осуществляющего расширение поданных значений, представленных во вспомогательной СОК, в основную СОК; выход блока расширения 13, шина 42, поочередно коммутируется демультиплексором 16 на вход регистра 15, шина 44, и вход регистра 17, шина 45, для временного хранения, соответственно, мультипликативной инверсии и произведения делимого и мультипликативной инверсии, представленных в основной СОК; выход регистра 15, шина 46, подается на первые входы умножителей 18, 19, на вторые входы которых поступает делимое и делитель, представленные в основной СОК, шины 28 и 29; выходы умножителей 18 и 19, шины 48 и 49, произведений, соответственно, делимого и делителя на мультипликативную инверсию, представленных в основной СОК поступают через схемы ключей 24 и 25 на вход, соответственно, регистра делимого 3 и регистра делителя 4 по шинам 26 и 27, и одновременно данные по шинам 48 и 49, соответственно, поступают на первые входы схем вычитания и умножения 20 и 21, а на вторые входы поступает, соответственно, выход регистра 17, шина 47, хранящий произведения делимого и мультипликативной инверсии, преобразованные в основную СОК, и константа «1»; в схемах вычитания и умножения 20 и 21 полученные значения умножаются на константу q i − 1 , шина 50; выходы схемы вычитания и умножения 20 подаются на выходной ключ 22, а выходы схемы вычитания и умножения 21 - на вход схемы сравнения 23; если результат сравнения равен 1, то подается управляющий сигнал по шине 51 на вход выходного ключа 22, на выходе которого, шина 53, формируется частное, если результат не равен 1, то формируется управляющий сигнал по шине 52, который открывает схемы ключей 24 и 25 и подает на вход регистров делимого 3 и делителя 4 новые значения, необходимые для следующей итерации.

Управление процессом деления осуществляется блоком управления 14, который формирует адресные входы мультиплексоров 5, 12, шины, соответственно, 31 и 41, и адресные входы демультиплексоров 7, 16, шины, соответственно, 33 и 43.

Рассмотрим новый алгоритм основного деления модулярных чисел для случая, когда делимое и делитель представляют собой произвольные целые числа и делитель не приводится к случаю попарно простого с модулями СОК.

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

Специализированные процессоры на основе арифметики СОК могут сыграть важную роль в высокоскоростных системах обработки данных в режиме реального времени. Операции сложения, вычитания и умножения, называемые модульными операциями, могут быть реализованы очень быстро, без распространения межразрядных переносов. Немодульные операции деления, сравнения чисел, определения знака и переполнения диапазона остаются сравнительно медленными. Любое улучшение скорости этих медленных алгоритмов значительно улучшает производительность многомодульных арифметико-логических устройств (АЛУ) и расширяет приложения СОК. Обычно при рассмотрении деления в СОК выделяют три категории: деление с нулевым остатком, масштабирование и деление в общем случае. Проблема деления в СОК в общем виде привлекает внимание многих исследователей для разработки высокопроизводительных многомодульных АЛУ. Известные алгоритмы деления в СОК, основанные на масштабировании, округлении, расширении и других операциях, являются медленными и требуют выполнения большого количества арифметических действий. Большинство известных алгоритмов работает путем рекурсивного вычитания числа, кратного делителю, из делимого до тех пор, пока разность не станет меньше, чем делитель. В связи с этим возникает необходимость упростить структуру вычислений при делении. Одно из направлений упрощения структуры устройства деления состоит в том, что делимое, делитель и остаток представлены только в формате СОК.

Рассмотрим параллельный алгоритм деления в СОК, преимущество которого состоит в том, что делимое, делитель и все промежуточные вычисления выполняются в СОК.

Параллельный алгоритм.

1. Пусть p₁, p₂, …, p_m есть набор модулей, (a₁, a₂, …, a_m) - делимое и (b₁, b₂, …, b_m) - делитель.

2. Определим вспомогательную систему оснований ( p 1 ' ,     p 2 ' ,     … ,     p m ' ) , где Н О Д ( p i ,   p j ' ) = 1 для i, j=1, 2, …, m.

3. Вычислим (q₁, q₂, …, q_m), где q i = p 1 ' ⋅ p 2 ' ⋅ … ⋅ p m '     mod p i .

4. Переведем (a₁, a₂, …, a_m) по основаниям p₁, p₂, …, p_m в ( a 1 ' ,     a 2 ' ,     … ,     a m ' ) по основаниям p 1 ' ,   p 2 ' ,   … ,   p m ' методом расширения базы СОК.

5. Переведем (b₁, b₂, …, b_m) по основаниям p₁, p₂, …, p_m в ( b 1 ' ,   b 2 ' ,   … ,   b m ' ) по основаниям p 1 ' ,     p 2 ' ,     … ,     p m ' методом расширения базы СОК.

6. Вычисляем ( b 1 − 1 ,     b 2 − 1 ,     … ,     b m − 1 ) по основаниям p₁, p₂, …, p_m, ( b 1 ' − 1 ,     b 2 ' − 1 ,     … ,     b m ' − 1 ) по основаниям p 1 ' ,     p 2 ' ,     … ,     p m ' и ( q 1 − 1 ,     q 2 − 1 ,     … ,     q m − 1 ) по основаниям p₁, p₂, …, p_m.

7. Вычисляем ( c 1 − 1 ,     c 2 − 1 ,     … ,     c m − 1 ) = ( a 1 ' ,     a 2 ' ,     … ,     a m ' ) ⋅ ( b 1 − 1 ,     b 2 − 1 ,     … ,     b m − 1 ) .

8. Переведем ( b 1 ' − 1 ,     b 2 ' − 1 ,     … ,     b m ' − 1 ) по основаниям p 1 ' ,     p 2 ' ,     … ,     p m ' в ( b 1 " − 1 ,     b 2 " − 1 ,     … ,     b m " − 1 ) по основаниям p₁, p₂, …, p_m и ( c 1 ' ,   c 2 ' ,   … ,   c m ' ) по основаниям p 1 ' ,   p 2 ' ,   … ,   p m ' в (c₁, c₂, …, c_m) по основаниям p₁, p₂, …, p_m методом расширения базы СОК.

9. Вычисляем ( a 1 ,   a 2 ,   … ,   a m ) = ( ( a 1 ,   a 2 ,   … ,   a m ) ⋅ ( b 1 " − 1 ,   b 2 " − 1 ,   … ,   b m " − 1 ) − ( c 1 ,   c 2 ,   … ,   c m ) ) ⋅ ( q 1 − 1 ,   q 2 − 1 ,   … ,   q m − 1 ) .

10. Вычисляем ( b 1 ,   b 2   … ,   b m ) = ( ( b 1 ,   b 2   … ,   b m ) ⋅ ( b 1 " − 1 ,   b 2 " − 1 ,   … ,   b m " − 1 ) ) − ( 1,   1,   … ,   1 ) ) ⋅ ( q 1 − 1 ,   q 2 − 1 ,   … ,   q m − 1 ) .

11. Если (b₁, b₂, …, b_m)=(1, 1, …, 1), то (a ₁, a ₂, …, a _m) есть частное; иначе - перейти к шагу 4.

Пример.

Возьмем исходную систему оснований (p₁, p₂, p₃)=(7, 11, 13) и вспомогательную систему оснований ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 5,   17,   19 ) . Для делимого a=212, равного в СОК (2, 3, 4)_{(7, 11, 13),} и делителя b=16, равного в СОК (2, 5, 3)_{(7, 11, 13),} частное z = ⌊ 212 16 ⌋ = 13 равно в СОК (6, 2, 0)_{(7, 11, 13)}.

Операция деления выполняется следующим образом.

1. Вычисляем ( q 1 ,   q 2 ,   q 3 ) ( p 1 ,   p 2 ,   p 3 ) = ( 5,   9,   3 ) ( 7,   11,   13 ) и ( q 1 − 1 ,   q 2 − 1 ,   q 3 − 1 ) ( p 1 ,   p 2 ,   p 3 ) = ( 3,   9,   3 ) ( 7,   11,   13 ) .

2. Переводим ( a 1 ,   a 2 ,   a 3 ) ( p 1 ,   p 2 ,   p 3 ) = ( 2,   3,   4 ) ( 7,   11,   13 ) в ( a 1 ' ,   a 2 ' ,   a 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 2,   8,   3 ) ( 5,   7,   19 ) .

3. Переводим ( b 1 ,   b 2 ,   b 3 ) ( p 1 ,   p 2 ,   p 3 ) = ( 2,   5,   3 ) ( 7,   11,   13 ) в ( b 1 ' ,   b 2 ' ,   b 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 1,   16,   16 ) ( 5,   7,   19 ) .

4. Переводим ( b 1 ' ,   b 2 ' ,   b 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 1,   16,   16 ) ( 5,   7,   19 ) в ( b 1 ' − 1 ,   b 2 ' − 1 ,   b 3 ' − 1 ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 1,   16,   16 ) ( 5,   7,   19 ) .

5. Вычисляем ( c 1 ' ,   c 2 ' ,   c 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( a 1 ' ,   a 2 ' ,   a 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) ⋅ ( b 1 ' − 1 ,   b 2 ' − 1 ,   b 3 ' − 1 ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = = ( 2,   8,   3 ) ⋅ ( 1,   16,   6 ) = ( 2,   9,   18 ) ( 5,   17,   19 ) .

6. Переводим ( b 1 ' − 1 ,   b 2 ' − 1 ,   b 3 ' − 1 ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 1,   16,   16 ) ( 5,   7,   19 ) в ( b 1 " - 1 ,   b 2 " − 1 ,   b 3 " − 1 ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 1,   16,   16 ) ( 5,   7,   19 ) .

7. Переводим ( c 1 ' ,   c 2 ' ,   c 3 ' ) ( p 1 ' ,   p 2 ' ,   p 3 ' ) = ( 2,   9,   18 ) ( 5,   7,   19 ) в ( c 1 ,   c 2 ,   c 3 ) ( p 1 ,   p 2 ,   p 3 ) = ( 4,   10,   1 ) ( 7,   11,   13 ) .

8. Вычисляем ( a 1 ,   a 2 ,   a 3 ) = ( ( a 1 ,   a 2 ,   a 3 ) ⋅ ( b 1 " - 1 ,   b 2 " − 1 ,   b 3 " − 1 ) − ( c 1 ,   c 2 ,   c 3 ) ) ⋅ ( q 1 − 1 ,   q 2 − 1 ,   q 3 − 1 ) = = ( | ( 2 ⋅ 3 − 4 ) ⋅ 3 | 7 ,   | ( 3 ⋅ 2 − 10 ) ⋅ | 11 ,   | ( 4 ⋅ 10 − 1 ) ⋅ 9 | 13 ) = ( 6,   2,   0 ) .

9. Вычисляем ( b 1 ,   b 2 ,   b 3 ) = ( ( b 1 ,   b 2 ,   b 3 ) ⋅ ( b 1 " - 1 ,   b 2 " − 1 ,   b 3 " − 1 ) − ( 1,   1,   1 ) ) ⋅ ( q 1 − 1 ,   q 2 − 1 ,   q 3 − 1 ) = ( 1,   1,   1 ) .

Так как (b₁, b₂, b₃)=(1, 1, 1), то частное вычисляется как (6, 2, 0).

На чертеже (фиг. 1) представлена схема устройства для основного деления модулярных чисел в формате системы остаточных классов. Схема устройства пунктирной линией разделена на левую и правую части. В левой части вычисления ведутся в основной системе СОК, а в правой части во вспомогательной СОК. Принцип работы данного устройства излагается ниже.

Делимое a и делитель b, представленные в основной системе остаточных классов, по шинам 1 и 2 поступают на входные регистры делимого 3 и делителя 4. Выходные данные с регистров делимого 3 и делителя 4 по шинам соответственно 28 и 29 поступают на информационные входы мультиплексора 5. Под действием адресного входа, шина 31, формируемого блоком управления 14, мультиплексор 5 вначале подает делимое по шине 30 на вход блока расширения 6, который представляет собой нейронную сеть для расширения кортежа числовой системы вычетов (патент RU 2256226, Бюл. №19 от 10.07.2005). Блок расширения 6 преобразует делимое a_i, представленное в основной СОК, в делимое a i ' , представленное во вспомогательной СОК, где i=1, 2, …, m. С выхода блока расширения 6 по шине 32 данные через демультиплексор 7 и шину 34 поступают на регистр делимого 8, который служит для временного хранения делимого, представленного во вспомогательной СОК. Адресные входы демультиплексора 7 подключены к блоку управления 14 посредством шины 33.

После преобразования делимого аналогичным образом осуществляется преобразование делителя b, представленного в основной СОК, в делитель b′, представленный во вспомогательной СОК. При этом демультиплексор 7 через шину 35 помещает данные делителя в регистр делителя 9. С выхода регистра делителя 9 по шине 37 делитель b i ' , представленный во вспомогательной СОК, поступает на вход LUT-таблицы 10, где происходит преобразование делителя в мультипликативную инверсию b i ' − 1 , и далее по шине 38 поступает на информационный вход мультиплексора 12 и первый вход умножителя 11, на вход которого поступают данные делимого a i ' , представленные во вспомогательной СОК. Результат умножения в умножителе 11 c i ' = a i ' ⋅ b i ' − 1 по шине 39 поступ