[Перевод] Разработка высокоскоростного ведического умножителя с использованием техник ведической математики
Реферат: Эта статья посвящена разработке высокоскоростного ведического умножителя, использующего технику древнееиндийской ведической математики, модифицированной для улучшения быстродействия.
Ведическая математика — это древняя система математики с уникальной системой вычислений, основанной на 16-и сутрах. В статье показана эффективность Урдхва Триагбхайам (Urdhva Triyagbhyam) — ведического метода умножения, и выделяется разница с обычным умножением. Метод основан на параллельной генерации независимых произведений, устранении шагов с нулевым результатом и масштабировании к старшим битам с использованием алгоритма Карацубы (Karatsuba), совместимого с различными типами данных. Сутра Урдхва Триагбхайам является самым эффективным алгоритмом, дающим минимальную задержку для умножения всех типов чисел, и больших, и малых. Далее приводится код алгоритма на Verilog HDL для умножения 32×32 бита и реализация на FPGA с помощью Xilinx Synthesis Tool на Spartan 3E с выводом результата на LCD. Синтез результата показывает, что время вычислений для произведения 32×32 бита равно 31.526 ns.
Ключевые слова: ведическая математика, сутра урдхва триагбхайам, алгоритм Карацубы-Офмана
1. Введение
Умножение — это важная фундаментальная арифметическая операция. Основанные на умножении операции, такие, как умножение с накоплением (MAC) и скалярное произведение являются одними из самых часто используемых операций, использующихся во многих применениях цифровой обработки сигналов (DSP), таких, как свёртка, быстрое преобразование Фурье (FFT), фильтрация, и, в микропроцессорах, в арифметическо-логических устройствах. Так как умножение занимает наибольшее время в большинстве алгоритмов DSP, существует необходимость в высокоскоростных умножителях. В настоящее время, умножение по-прежнему является основным фактором, определяющим время цикла в чипах DSP. Необходимость быстрой обработки возрастает по мере распространения компьютеров и приложений обработки сигналов.
Высокопроизводительные арифметические операции важны для достижения желаемого быстродействия во многих приложениях обработки сигналов и изображений в реальном времени [2]. Одной из ключевых арифметических операций в таких приложениях является умножение и разработка схем быстрого умножения была предметом особого интереса в течение десятилетий. Уменьшение задержек времени и потребления энергии является очень существенным требованием для многих приложений [2, 3]. В этой работе представлены различные архитектуры умножения. Умножитель, основанный на ведической математике — один из быстрых и малопотребляющих умножителей. Уменьшение потребления энергии для цифровых систем включает в себя оптимизацию на всех уровнях дизайна. Оптимизация включает технологию, используемую для реализации цифровых цепей, стиль и топологию, архитектуру реализации схемы т, на самом высоком уровне, алгоритм, реализуемый схемой. Цифровые умножители являются самыми часто используемыми компонентами во всех цифровых схемах. С их помощью быстро и эффективно реализуются любые операции. существуют различные типы реализации умножителей. Конкретная архитектура умножителя выбирается в зависимомти от приложения.
Во многих алгоритмах DSP, умножитель расположен на критическом пути и определяет быстродействие алгоритма. Скорость операции умножения очень важна в DSP и в процессорах общего назначения. В прошлом умножение выполнялось как серия сложений, вычитаний и сдвигов. В литературе предлагаются множество алгоритмов для реализации умножнения, и каждый из них имеет свои преимущества и компромиссы между скоростью, сложностью схемы, площадью ии портебляемой мощностью.
Умножитель представляет собой довольно большой блок вычислительной системы. Количество цепей в схеме пропорционально квадрату разрядности, т.е. умножитель на N бит будет иметь N^2 вентилей (с точностью до постоянного коэфф. прим. перев.). Для алгоритмов умножения, используемых в приложениях DSP основными параметрами являются латентность (latency) и пропускная способность (throughput). Латентность — это реальная задержка вычисления функции, измеряемая временем, прошедшим от подачи данных на вход до появления результата на выходе. Пропускная способность определяет, сколько умножений может быть выполнено за данный период времени. Умножитель, это не просто блок с задержкой, он также потребляет мощность, и потребляемую мощность желательно уменьшить, но больший интерес представляет снижение задержки путём различных оптимизаций.
Цифровые умножители являются центральными элементами процессоров цифровой обработки сигналов (DSP) и быстродействие DSP в значительной степени определяется быстродействием умножителя [11]. Два самых распространенных алгоритма умножения в цифровой схемотехнике — это алгоритм матричного умножения и алгоритм Бута (Booth). Время вычисления при матричном умножении меньше, потому что частичные произведения вычисляются параллельно. Задержка в матричном умножителе, это время, требуемое для прохождения сигнала через логические элементы, формирующие матрицу. Умножение Бута — другой важный алгоритм умножения. Для высокоскоростого умножения требуются большие массивы, и экспоненциальное количество операций, в обмен на большие частичные суммы и регистры частичного переноса. Умножение двух n-битных операндов с использованием алгоритма Бута с основанием 4 требует приблизительно n / (2m) тактовых циклов для генерации младшей половины конечного произведения, где m — количество стадий суммирования. В силу важности цифрового умножения в DSP, алгоритмы умножения всегда были области активных исследований, и в литературе [4] описано множество интересных алгоритмов умножения.
В этой статье сутра Урдхва триагбхайам впервые применена к двоичной системе счисления и использована для разработки архитектуры цифрового умножителя. Показано сходство этой архитектуры с популярной архитектурой матричного умножителя. Эта сутра также показывает эффективность уменьшения умножения MxM до эффективной структуры умножителя 4×4. Затем обсуждается сутра Никхилам, и показана её большая эффективность для умножения больших чисел сведение умножения двух больших чисел к умножению меньших чисел. Предлагаемый алгоритм умножения проиллюстрирован для того, чтобы показать его вычислительную эффективность на примере сведения умножения 4×4 бит до одного умножения 2×2 бит [4]. Эта работа представляет систематическую методологию разработки быстрых и эффективных по площади цифровых умножителей, основанных на ведической математике. Архитектура умножителя основана на вертикально-перекрёстном алгоритме древнеиндийской ведической математики [5].
2. Ведическая математика
Ведическая матиматика является частью четырёх Вед (книг мудрости). Она является частью Стхапатья Веда (книга по архитектуре), которая является приложением к Атхарваведа. Она даёт объяснения некоторым математическим терминам, включая арифметику, геометрию, тригонометрию, квадратные уравнения, факторизацию и вычисления.
Его святейшество Джагадгуру Свами Бхарати Кришна Тиртхаджи Махараджа (1884–1960) объединил все эти работы вместе и дал им математическое объяснение и обсудил их применение для различных прикладных задач. Он сконструировал 16 сутр (формул) и 16 Упа Сутр (субформул) после широких исследований Атхарваведа. Очевидно, эти формулы не присутствуют в текте Атхарваведа, так как были сформулированы самим Свами.
Ведическая математика математически удивительна и логична. Поэтому она, бесспорно, столь возвышенна. Благодаря своим феноменальным характеристикам, ведическая математика стала известна за границами Индии и вызывает интерес зарубежных исследователей.
Ведическая математика имеет дело со сложными математическими операциями. Основные арифметические методы просты и мощны[2, 3]. Слово «ведический» происходит от слова «Веда», что означает хранилище всех знаний. Ведическая математика в основном базируется на 16 сутрах (афоризмах), в которых идёт речь о различных разделах математики, таких, как арифметика, алгебра, геометрия и т.п. [15]. Сутры и их краткое содержание перечислены ниже в алфавитном порядке.
Русский перевод этих сутр или хотя бы их названий найти не удалось, поэтому я оставил их без перевода, чтобы избежать ошибок, так как для некоторых из них по короткому названию трудно понять, о чём там речь. Прим. перев.
2. Chalana-Kalanabyham — Differences and Similarities.
3. Ekadhikina Purvena — By one more than the previous One.
4. Ekanyunena Purvena — By one less than the previous one.
5. Gunakasamuchyah — The factors of the sum is equal to the sum of the factors.
6. Gunitasamuchyah — The product of the sum is equal to the sum of the product.
7. Nikhilam Navatashcaramam Dashatah — All from 9 and last from 10.
8. Paraavartya Yojayet — Transpose and adjust.
9. Puranapuranabyham — By the completion or noncompletion.
10. Sankalana- vyavakalanabhyam — By addition and by subtraction.
11. Shesanyankena Charamena — The remainders by the last digit.
12. Shunyam Saamyasamuccaye — When the sum is the same that sum is zero.
13. Sopaantyadvayamantyam — The ultimate and twice the penultimate.
14. Urdhva-tiryagbhyam — Vertically and crosswise.
15. Vyashtisamanstih — Part and Whole.
16. Yaavadunam — Whatever the extent of its deficiency.
Эти методы и идеи могут напрямую применяться в тригонометрии, плоской и сферической геометрии, конических сечениях, дифференциальном и интегральном исчислениях, и прикладной математике разного рода. Как упоминалось ранее, все эти сутры были реконструированы из древних ведических текстов в начале прошлого века. Многие субсутры были открыты в то же время, и они не обсуждаются здесь. Красота ведической математики в том, что она сокращает традиционные вычисления классической математики до очень простых. Так происходит потому, что ведические формулы основаны на естественных принципах, по которым работает человеческий разум. Это очень интересная область, и она позволяет создавать эффективные алгоритмы, применимые к различным областям инженерии, таким, как вычислительная техника и цифровая обработка сигналов [1,4].
Архитектура умножителей может быть классифицирована в три категории. Первая — это последовательный умножитель, который минимизирует количество аппаратного обеспечения и, соответственно, площадь. Вторая категория — это параллельный умножитель (матрица или дерево), который имеет максимальную скорость математических операций. Но его недостатком является большая занимаемая площадь. Третьей категорией является параллельно-последовательный умножитель, который имеет хорошее соотношение между временем вычислений, занимаемым последовательными вычислениями, и площадью, занимаемой параллельным умножителем.
3. Разработка ведического умножителя
Сутра Урдхва Триагбхайам (вертикально-перекрёстный метод)
Сутра Урдхва Триагбхайам является общей формулой умножения, применимой ко всем случаям умножения. Буквально её название означает «вертикально-перекрёстный». Для иллюстрации этой схемы умножения, рассмотрим умножение двух десятичных чисел (5498 × 2314). Обычные, известные нам методы потребуют 16 умножений и 15 сложений. Альтернативный метод умножения с использованием сутры Урдхва Триагбхайам показан на рис. 1. Сомножители записываются на двух смежных сторонах квадрата, как показано на рисунке. Квадрат делится на строки и столбцы, и каждый столбец/строка соответствует одной цифре соответствующего сомножителя. Таким образом, каждая цифра первого сомножителя имеет клетку в квадрате, общую с одной цифрой второго сомножителя. Клетки разделены на половины диагональными линиями. Теперь каждая цифра первого сомножителя умножается на цифру второго сомножителя и двузначное произведение записывается в клетку. Все цифры, лежащие на пунктирных диагональных линиях, складываются друг с другом и с разрядом переноса. Младший разряд суммы записывается в соответствующий разряд результата, а старший переносится на следующий шаг. Разряд переноса для первого шага (то есть для самой правой пунктирной линии) равно нулю [9].
Рис. 1. Альтернативный способ умножения по сутре Урдхва Триагбхайам.
Начнём разработку с умножителя 2×2 бита, как показано на рис. 2. Здесь использован алгоритм сутры Урдхва Триагбхайам или «вертикально-перекрёстный алгоритм» [4] для построения эффективного цифрового умножителя. Этот алгоритм отличается от традиционного метода умножения с суммированием и сдвигом частичных произведений.
Рис. 2. Аппаратная реализация блока 2×2.
Для дальнейшего масштабирования используется алгоритм Карацубы-Офмана [6]. Алгоритм Карацубы-Офмана является одним из наиболее быстрых способов умножения длинных целых чисел. Он основан на стратегии «разделяй и влавствуй».
Умножение целых длиной 2n преобразуется в два умножения разрядностью n, одно умножение разрядностью (n + 1), два вычитания длиной n, две операции сдвига влево, два сложения длиной n и два сложения длиной 2n.
Алгоритм объясняется следующим образом:
Пусть X и Y являются двоичным представлением двух длинных целых:
Мы хотим вычислить произведение XY. Используя стратегию «разделяй и влавствуй», операнды X и Y могут быть разделены на равные части XH и XL, YH и YL, где H и L означают старшие и младшие разряды соответственно. Пусть k=2n. Если k нечётное, число может быть дополнено справа нулём.
Для умножителя сначала делаем базовые блоки 2×2 бита и затем, используя эти блоки, 4×4, затем 8×8, 16×16 и, наконец, умножитель 32×32, как показано на рис. 3 [7].
https://habrahabr.ru/post/121950/ — Алгоритм Карацубы для умножения двух чисел
Умножение Карацубы — описание в Википедии
Рис. 3. Ведический умножитель 32×32 бита
4. Реализация ведического умножителя
Умножитель был реализован с помощью двух различных техник: традиционных сдвигов и сложений и ведической техники для 4, 8, 16 и 32-битного умножения. Результаты симуляции для 8, 16 и 32-битных умножителей показаны на рис 4a, 4b, 4c соответственно.
Результаты симуляции
Рис. 4а. 8-битный ведический умножитель
Рис. 4b. 16-битный ведический умножитель
Рис. 4c. 32-битный ведический умножитель
Результаты синтеза
Selected Device: 3s500efg320–5
Number of Slices: 25 out of 4656 0%
Number of Slice Flip Flops: 36 out of 9312 0%
Number of 4 input LUTs: 48 out of 9312 0%
Number used as logic: 41
Number used as Shift registers: 7
Number of IOs: 9
Number of bonded IOBs: 9 out of 232 3%
Number of GCLKs: 1 out of 24 4%
Результат на LCD-экране: A0A0A09F5F5F5F60 (hex)
Таблица 1. Задержка в различных умножителях
В наихудшем случае задержка оптимизированного ведического умножителя составила 31.526ns. Сравнение с другими реализациями умножителя проводилось путём синтеза для на XILINX SPARTAN xc3s500e-5fg320 [17]. В таблице 1 приведены результаты синтеза для различных реализаций. Результат, полученный для предлагаемого ведического умножителя быстрее, чем для алгоритма Карацубы.
5. Заключение
Проект ведического умножителя 32×32 был реализован на Spartan XC3S500–5-FG320. Разработка основана на ведическом методе умножения [3]. Для наихудшего случая задержка в оптимизированном ведическом умножителе составила 31.526ns. Показано, что ведический умножитель намного быстрее традиционного умножителя. Это позволяет нам строить иерархический дизайн умножителя. Сложность умножителя меньше, а модульность больше, чем у традиционной схемы. Сутры Урдхва Триагбхайам, Никхилам и Анурупья представляют алгоритмы, которые могут уменьшить задержку, портебляемую мощность и аппаратные требования для умножителей. Показано, что реализация на FPGA легко достижима. Показана высокая скорость алгоритма умножения.
Литература
1. Wallace, C.S., «A suggestion for a fast multiplier,» IEEE Trans. Elec. Comput., vol. EC-13, no. 1, pp. 14–17, Feb. 1964.
2. Booth, A.D., «A signed binary multiplication technique,» Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, pt. 2, pp. 236– 240, 1951.
3. Jagadguru Swami Sri Bharath, Krsna Tirathji, «Vedic Mathematics or Sixteen Simple Sutras From The Vedas», Motilal Banarsidas, Varanasi (India),1986.
4. A.P. Nicholas, K.R Williams, J. Pickles, «Application of Urdhava Sutra», Spiritual Study Group, Roorkee (India),1984.
5. Neil H.E Weste, David Harris, Ayan anerjee, «CMOS VLSI Design, A Circuits and Systems Perspective», Third Edition, Published by Person Education, PP-327–328]
6. Mrs. M. Ramalatha, Prof. D. Sridharan, «VLSI Based High Speed Karatsuba Multiplier for Cryptographic Applications Using Vedic Mathematics», IJSCI, 2007
7. Thapliyal H. and Srinivas M.B. «High Speed Efficient N x N Bit Parallel Hierarchical Overlay Multiplier Architecture Based on Ancient Indian Vedic Mathematics», Transactions on Engineering, Computing and Technology, 2004, Vol.2.
8. «A Reduced-Bit Multiplication Algorithm For Digital Arithmetic» Harpreet Singh Dhilon And Abhijit Mitra, International Journal of Computational and Mathematical Sciences, Waset, Spring, 2008.
9. «Lifting Scheme Discrete Wavelet Transform Using Vertical and Crosswise Multipliers» Anthony O«Brien and Richard Conway, ISSC, 2008, Galway, June 18–19.
10. D. Zuras, On squaring and multiplying large integers, In Proceedings of International Symposium on Computer Arithmetic, IEEE Computer Society Press, pp. 260–271, 1993.
11. Shripad Kulkarni, «Discrete Fourier Transform (DFT) by using Vedic Mathematics«Papers on implementation of DSP algorithms/VLSI structures using Vedic Mathematics, 2006, www.edaindia.com, IC Design portal.
12. S.G. Dani, Vedic Maths»: facts and myths, One India One People, Vol 4/6, January 2001, pp. 20–21; (available on www.math.tifr.res.in dani).
13. M.C. Hanumantharaju, H. Jayalaxmi, R.K. Renuka, M. Ravishankar, «A High Speed Block Convolution Using Ancient Indian Vedic Mathematics,» ICCIMA, vol. 2, pp.169–173, International Conference on Computational
Intelligence and Multimedia Applications, 2007.
14. Himanshu Thapliyal, «Vedic Mathematics for Faster Mental Calculations and High Speed VLSI Arithmetic», Invited talk at IEEE Computer Society Student Chapter, University of South Florida, Tampa, FL, Nov 14 2008.
15. Jeganathan Sriskandarajah, «Secrets of Ancient Maths: Vedic Mathematics», Journal of Indic Studies Foundation, California, pages 15 and 16.
16. S. Kumaravel, Ramalatha Marimuthu, «VLSI Implementation of High Performance RSA Algorithm Using Vedic Mathematics,» ICCIMA, vol. 4, pp.126–128, International Conference on Computational Intelligence and Multimedia Applications (ICCIMA 2007), 2007.
17. www.xilinx.com
Авторы
Г. Ганеш Кумар — бакалавр электроники и связи в MITS College of Engineering, 2009 и степень магистра в VLSI, 2011 из Sree Vidyanikethan College of Engineering, Тирупати, Индия.
В настоящее время занят исследованиями малопотребляющего дизайна VLSI. Работает в должности Associate professor на факультете электроники и связи в SVEC College of Engineering, Тирупати, Индия, в течение 1 года. Имеет 1 публикацию в международном и 1 публикацию в национальном журналах.
