В настоящее время стандартных ресурсов процессора недостаточно для выполнения сложных математических операции (таких как умножение и деление) над данными большой разрядности. К таким данным относятся числа разрядности больше 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-ядро используется для решения множества практических задач. Вместе с тем, в мире вычислительной техники всегда найдутся задачи, для которых потребуется реализация нетривиальных и в чем-то уникальных вычислительных систем.
Список литературы:
- Zimmermann, P. Modern computer arithmetic / R. P. Brent, P. Zimmermann // version 0.5.3 – 2010.
- Федюнин Р. Н., Войнов А. С., Сенокосов И. В. СПОСОБ РЕАЛИЗАЦИИ SOFT-ЯДРА СРЕДСТВАМИ ТЕОРИИ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ //Международные индексы. – С. 3.
- Вашкевич Н. П. Недетерминированные автоматы в проектировании систем параллельной обработки. – П.: Издательство Пензенского государственного университета, 2004. – С. 62-115.
- Федюнин Р.Н., Войнов А.С., Сенокосов И.В. Оценка производительности алгоритмов умножения больших данных с помощью Марковских процессов, Новые информационные технологии и системы: Сб. трудов XI Международной научно-технической конференции. – 14:00-18:00 Пензенский Государственный Университет, Пенза : Изд-во ПГУ, 2014. – С. 13-18[schema type=»book» name=»БЛОК АРИФМЕТИКО-ЛОГИЧЕСКОГО УСТРОЙСТВА ДЛЯ РЕАЛИЗАЦИИ УМНОЖЕНИЯ БОЛЬШИХ ЧИСЕЛ» description=»Актуальность и цели. В статье представлен способ реализации функционального блока умножения специализированного АЛУ. Необходимость в проектировании данного вида блоков возникает в результате того, что диапазон чисел, который используется в реальных задачах, порой доходит до нескольких тысяч и даже сотен тысяч десятичных цифр. Такой диапазон чисел не соответствует базовым типам данных современных архитектур АЛУ. Материалы и методы. Построение модели функционального блока умножения Карацубы было произведено с использованием теории недетерминированных автоматов. Результаты. Получена модель функционального блока умножения Карацубы. Было произведено построение системы канонических уравнений на основе математической модели алгоритма умножения. Также была произведена схемная реализация с подробным описанием действий в алгоритме. Произведена реализация с использованием средств САПР Altera Quartus. Выводы. Полученная реализация алгоритма умножения может быть интегрирована в soft-ядро в виде специализированного блока АЛУ. Это позволит сократить время вычислений при работе с большими числами.» author=»Войнов Артем Сергеевич, Сенокосов Илья Владимирович, Калачев Андрей Валентинович» publisher=»Басаранович Екатерина» pubdate=»2016-12-27″ edition=»euroasia-science.ru_26-27.02.2016_2(23)» ebook=»yes» ]