Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,916

ОСОБЕННОСТИ РЕАЛИЗАЦИИ ОПЕРАЦИИ УМНОЖЕНИЯ НА ПЛИС

Система проектирования Quartus II, используемая для разработки устройств на основе ПЛИС фирмы Altera, включает библиотеку стандартных подпрограмм, предназначенных для выполнения основных математических операций. В частности, для реализации операции умножения используют подпрограмму lpm_mult. Эта подпрограмма позволяет синтезировать схему устройства, реализующего на аппаратном уровне умножитель двух двоичных чисел заданной разрядности. Очевидно, что чем больше разрядность сомножителей, тем сложнее устройство и при его реализации расходуются большие аппаратные ресурсы ПЛИС и возрастает время вычисления. Поэтому проблема сокращения аппаратных затрат и времени вычисления является весьма важной.

Согласно выдвинутой А. Н. Колмогоровым гипотезе n² [1] сложность операции умножения, то есть количество простых операций выполняемых для получения произведения, пропорциональна квадрату разрядности сомножителей. Следовательно и аппаратные затраты на реализации умножителя должны расти пропорционально квадрату разрядности сомножителей. Желание упростить реализацию умножителей привело к разработке методов быстрого умножения, для которых сложность реализации пропорциональна nlog23. [2].

Ниже рассмотрены результаты реализации метода быстрого умножения, базирующиеся на использовании выражения:


.


Суть метода базируется на том, что для позиционной системы счисления умножение на число, равное основанию этой системы равносильно сдвигу записи числа на один разряд, то есть его выполнение не требует применения дополнительных средств. Практически при реализации умножителя двоичные 2*n разрядные числа A и B записывают в виде  и . Тогда алгоритм умножения приобретает вид:


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

Исследование критического пути, параллельной канонической формы графа данного алгоритма, показало, что время получения результата определяется выражением:

,

где: , ,

 - время суммирования n разрядных аргументов,

 - время умножения n разрядных аргументов.

Для исследования зависимости аппаратных затрат, требуемых на реализацию данного алгоритма, от разрядности аргументов использовалась написанная на языке AHDL параметризированная программа. Исследования проводились для ПЛИС семейств Cyclone II и Stratix II. Эти ПЛИС предполагают выполнение операции умножения либо с использованием только логических блоков (ЛБ), либо с использованием специализированных встроенных умножителей, разрядности 9 х 9 бит.

Исследования показали, что в первом случае при увеличении разрядности аргументов использование алгоритмa быстрого умножения позволяет уменьшить затраты на реализацию умножителя для ПЛИС Cyclone II при  n>15 (параметр maximize_speed = 0) и для ПЛИС Stratix II при n>35. При использовании встроенных умножителей применение метода быстрого умножения также позволяет снизить затраты на реализацию. В этом случае, например для ПЛИС семейства Cyclone II существует несколько областей (20≤n≤34 ,56≤n≤70, n>90) где его применение предпочтительнее стандартной мегафункции.

Полученные аналитические зависимости времени выполнения операции от разрядности аргументов для алгоритма быстрого умножения и стандартной мегафункции позволили найти минимальное число разрядов аргументов (nгр) для которого применение метода быстрого умножения позволяет уменьшить время вычисления относительно стандартной мегафункции lpm_mult :


  • для ПЛИС Cyclone II, случай только ЛБ и maximize_speed = 0 ;nгр ≥ 24
  • для ПЛИС Cyclone II, случай только ЛБ и maximize_speed = 10 ;nгр ≥42
  • для ПЛИС Cyclone II, случай встроенных умножителей ;nгр ≥90
  • для ПЛИС Stratix II, случай только ЛБ ;nгр ≥170
  • для ПЛИС Stratix II, случай встроенных умножителей nгр ≥107

Подытоживая сказанное можно сделать вывод, что при увеличении разрядности сомножителей применение метода быстрого умножения позволяет получить выигрыш как по требуемым аппаратным ресурсам ПЛИС, так и по скорости вычисления.

 

СПИСОК ЛИТЕРАТУРЫ:

  1. http://mech.math.msu.su/probab/Kolmogorov/kolmogorov.html
  2. http://www.ccas.ru/personal/karatsuba/alg.htm

Библиографическая ссылка

Мо Чжо Чо ОСОБЕННОСТИ РЕАЛИЗАЦИИ ОПЕРАЦИИ УМНОЖЕНИЯ НА ПЛИС // Современные наукоемкие технологии. – 2008. – № 4. – С. 114-116;
URL: http://top-technologies.ru/ru/article/view?id=23779 (дата обращения: 27.05.2020).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074