27 Фев

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




Номер части:
Оглавление
Содержание
Журнал
Выходные данные


Науки и перечень статей вошедших в журнал:

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

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

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

Рисунок 1. Обобщенная структура стандартного soft – ядра.

Рисунок 2. Архитектура стандартного soft – ядра, расширенного блоками для ускоренной операции умножения.

Для понимания принципа работы функционального блока умножения составим его модель (рисунок 3) используя теорию недетерминированных автоматов [3]. Согласно данной модели центральными блоками для вычислений являются два стека. По этой причине они вынесены из основного АЛУ.

Рисунок 3. Модель функционального блока умножения.

Описание событий, показанных на граф-схеме модели:

Ответ – Вывод ответа

Система канонических уравнений (СКУ) математической модели алгоритма Карацубы на основе модели:

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

Рисунок 4. Схема функционального блока умножения.

Исходя из вышеперечисленного, устройство работает следующим образом: исходные данные А и В подаются на информационные входы блока 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 и на выходе получается конечный ответ.

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

Для иллюстрации сравнения временной сложности различных алгоритмов умножения больших чисел построена диаграмма (рисунок 5) [4].

Рисунок 5. Временная сложность алгоритмов Карацубы, Шёнхаге-Штрассена и Тоома-Кука.

В заключении требуется отметить, что данный вид устройств распространён повсеместно т.к. одно 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
    БЛОК АРИФМЕТИКО-ЛОГИЧЕСКОГО УСТРОЙСТВА ДЛЯ РЕАЛИЗАЦИИ УМНОЖЕНИЯ БОЛЬШИХ ЧИСЕЛ
    Актуальность и цели. В статье представлен способ реализации функционального блока умножения специализированного АЛУ. Необходимость в проектировании данного вида блоков возникает в результате того, что диапазон чисел, который используется в реальных задачах, порой доходит до нескольких тысяч и даже сотен тысяч десятичных цифр. Такой диапазон чисел не соответствует базовым типам данных современных архитектур АЛУ. Материалы и методы. Построение модели функционального блока умножения Карацубы было произведено с использованием теории недетерминированных автоматов. Результаты. Получена модель функционального блока умножения Карацубы. Было произведено построение системы канонических уравнений на основе математической модели алгоритма умножения. Также была произведена схемная реализация с подробным описанием действий в алгоритме. Произведена реализация с использованием средств САПР Altera Quartus. Выводы. Полученная реализация алгоритма умножения может быть интегрирована в soft-ядро в виде специализированного блока АЛУ. Это позволит сократить время вычислений при работе с большими числами.
    Written by: Войнов Артем Сергеевич, Сенокосов Илья Владимирович, Калачев Андрей Валентинович
    Published by: Басаранович Екатерина
    Date Published: 12/27/2016
    Edition: euroasia-science.ru_26-27.02.2016_2(23)
    Available in: Ebook