БЛОК АРИФМЕТИКО-ЛОГИЧЕСКОГО УСТРОЙСТВА ДЛЯ РЕАЛИЗАЦИИ УМНОЖЕНИЯ БОЛЬШИХ ЧИСЕЛ

В настоящее время стандартных ресурсов процессора недостаточно для выполнения сложных математических операции (таких как умножение и деление) над данными большой разрядности. К таким данным относятся числа разрядности больше 10000 знаков в двоичном представлении. Существуют специальные алгоритмы для обработки таких массивов данных [1].

В данной статье предложена реализация алгоритма Карацубы в виде отдельного модуля, прикреплённого soft – ядру. Данный алгоритм был выбран ввиду своей эффективности при работе с данными больше 10000 знаков в двоичном виде, а также ввиду того, что более сложные алгоритмы (Тоома-Кука, Шенхаге-Штрассена и др.) для значений меньше их порогового используют алгоритм Карацубы.

Для иллюстрации рассматриваемого способа реализации функционального блока умножения, в качестве примера, возьмем схему стандартного soft – ядра, разрабатываемого для эксплуатации в виде аппаратно-программного модуля вычислительного устройства [2]. Обобщенная структура варианта soft – ядра, предназначенного для применения в составе встраиваемых микропроцессорных систем, реализуется на базе ПЛИС. Предложенный вариант вычислительного устройства реализован на базе стандартного soft – ядра, но включает в себя дополнительные функциональные блоки для работы со специализированным АЛУ.

Устройство работает следующим образом: исходные данные А и В подаются на информационные входы блока 1, где данные сравниваются с пороговым значением Р (порог задается исходя из потребностей реализации) и если они превышают его, то A и B передаются в блок 2, иначе данные коммутируются в блок 13, где обрабатываются по правилам чисел с малой разрядностью. В блоке 2 данные разбиваются на части: A разбивается на a и b, B разбивается на c и d. После чего, определяется разрядность полученных промежуточных значений: a, b, c, d. Далее полученные промежуточные результаты блока 2 (a, b, c, d) поступают в блок 3. В блоке 3 производится сложение поступивших данных по формулам A1 = a + b, B1 = c + d. Далее данные поступают в блок 4, где в зависимости от значений управляющих сигналов происходит работа с ЗУ. Поступившие промежуточные результаты обрабатываются блоком 5 по формуле C1 = A1·B1 — a·b. Далее данные передаются в блок 6, где происходит их сдвиг на половину значащих разрядов большего числа. В блоке 7 происходит повторный сдвиг полученного в блоке 6 числа. Затем в блоке 8 происходит вычисление по формуле C1 = C1 — b · d. Далее в блоке 9 происходит сдвиг числа, полученного в 8 блоке, на половину значащих разрядов большего числа. В последующем блоке 10 происходит вычисление по формуле C2 = a · b · T² + b · d. Результаты вычисленные в предыдущих блоках (С1 и С2) суммируются в блоке 11 и на выходе получается конечный ответ.

Тестирование показало полную работоспособность реализованного блока умножения.

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

Список литературы

1. Zimmermann, P. Modern computer arithmetic / R. P. Brent, P. Zimmermann // version 0.5.3 – 2010.
2. Федюнин Р. Н., Войнов А. С., Сенокосов И. В. СПОСОБ РЕАЛИЗАЦИИ SOFT-ЯДРА СРЕДСТВАМИ ТЕОРИИ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ //Международные индексы. – С. 3.
3. Вашкевич Н. П. Недетерминированные автоматы в проектировании систем параллельной обработки. – П.: Издательство Пензенского государственного университета, 2004. – С. 62-115.
4. Федюнин Р.Н., Войнов А.С., Сенокосов И.В. Оценка производительности алгоритмов умножения больших данных с помощью Марковских процессов, Новые информационные технологии и системы: Сб. трудов XI Международной научно-технической конференции. – 14:00-18:00 Пензенский Государственный Университет, Пенза : Изд-во ПГУ, 2014. – С. 13-18