Просмотр исходного текста страницы Комплексное исследование умножителей в диапазоне 3 - 64 бит

В рамках работы по разработке эффективных модулярных устройств было проведено исследование различных вариантов построения однотактовых двоичных и модулярных умножителей с входными операндами в диапазоне 3-64 бит. Такие устройства чрезвычайно важны в современной микроэлектронике. Каждый современный микропроцессор имеет такую операцию в составе своего набора инструкций, а продвинутые DSP процессоры содержат специальные вычислительные блоки для ускоренного вычисления [1]. Исследовались 4 варианта однотактовых умножителей:

* Встроенный умножитель в САПР Synopsys Design Compiler.
* Иерархический двоичный умножитель [1].
* Модулярный умножитель со стандартным спец. базисом из трех модулей (''3 moduli set'') <math>(2^n-1, 2^n, 2^n+1)</math>
* Модулярный умножитель с продвинутым спец. базисом из 4-х модулей (''4 moduli set'') <math>(2^n-1, 2^n+1, 2^{n+1}-1, 2^{n+1}+1)</math>
Синтез проводился в базисе 45 нм. в библиотеке NangateOpenCellLibrary.lib с помощью САПР Synopsys Design Compiler. Синтез проводился дважды для каждой из схем, на разных настройках "усилий" синтезатора - ''medium'' и ''ultra high effort''. Таким образом, также проверялась способность САПРа по минимизации задержек для различных схем. Общее количество тестов выглядит следующим образом.

{| border="1" cellpadding="5" cellspacing="0"
|-
|colspan="4" align="center"| Модулярный
|colspan="4" align="center"| Двоичный
|-
|colspan="2" align="center"|  3 moduli set
|colspan="2" align="center"|  4 moduli set
|colspan="2" align="center"|  Встроенный
|colspan="2" align="center"|  Иерархический
|-
| medium effort
| ultra effort
| medium effort
| ultra effort
| medium effort
| ultra effort
| medium effort
| ultra effort
|-
|}


== Ссылки на генераторы Verilog описаний исследуемых схем  ==
Для каждой из схем были написаны генераторы поведенческих описаний на языке Verilog:

* [http://vscripts.ru/2013/high-bit-int-multiplication.php Модулярный умножитель со стандартным спец. базисом из трех модулей (''3 moduli set'')]
* [http://vscripts.ru/2013/high-bit-int-multiplication-4-mod-generator.php Модулярный умножитель с продвинутым спец. базисом из 4-х модулей (''4 moduli set'')]
* [http://vscripts.ru/2013/high-bit-int-multiplication-hierarchical.php Иерархический двоичный умножитель]
* [http://vscripts.ru/dima/binary_mult.php Встроенный умножитель в САПР Synopsys Design Compiler.]


== Общие результаты  ==

[[Изображение:all_timing_mult.JPG]]
[[Изображение:all2.JPG]]

== Сравнение двоичных схем  ==
Иерархический умножитель прекрасно себя показал в сравнении с встроенным вариантом. Несмотря на возрастающую площадь, задержка сократилась примерно вдвое. Однако, на ULTRA настройках синтезатора все преимущества сошли на нет. И в площади и в задержке встроенный вариант "Synopsys DC" значительно превзошел иерархическую схему. Встроенный вариант оказался наиболее "восприимчив" к настройкам синтезатора.   


[[Изображение:bin1.JPG]]
[[Изображение:bin2.JPG]]


== Сравнение модулярных схем  ==
Модулярная структура, основанная на 3-х основаниях <math>(2^n-1, 2^n, 2^n+1)</math> показала себя намного лучше, чем предлагаемая в 
[2] структура с 4-мя основаниями <math>(2^n-1, 2^n+1, 2^{n+1}-1, 2^{n+1}+1)</math>. Задержка на критическом пути для 4-модульного набора больше в два раза. Возможно, причиной тому послужила недостаточно эффективная реализация преобразователей. Так же есть вероятность, что такая структура будет более эффективна для больших задач с значительным количеством арифметических операций. Эти предположения требуют дальнейших исследований.

[[Изображение:mod1.JPG]]
[[Изображение:mod2.JPG]]


== Анализ эффективности САПР в режиме ULTRA high effort  ==
Графики скомпонованы для иллюстрации эффективности ULTRA режима. 

[[Изображение:ultra_compl_mult1.JPG]]

[[Изображение:ultra_compl_mult2.JPG]]

[[Изображение:ultra3.JPG]]

[[Изображение:ultra4.JPG]]


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



<table style='border: 1px solid black; text-align: center;'>
<tr>
<td style='border: 1px solid black; padding: 2px;'>'''Схема умножителя'''</td>
<td style='border: 1px solid black; padding: 2px;'>'''Средний коэффициент увеличения производительности'''</td>
</tr>
<tr>
<td style='border: 1px solid black;'>Встроенный умножитель в САПР Synopsys Design Compiler.</td>
<td style='border: 1px solid black;'>68</td>
</tr>
<tr>
<td style='border: 1px solid black;'>Иерархический двоичный умножитель</td>
<td style='border: 1px solid black;'>31</td>
</tr>
<tr>
<td style='border: 1px solid black;'> Модулярный умножитель со стандартным спец. базисом из трех модулей</td>
<td style='border: 1px solid black;'>28</td>
</tr>
<tr>
<td style='border: 1px solid black;'>Модулярный умножитель с продвинутым спец. базисом из 4-х модулей</td>
<td style='border: 1px solid black;'>38</td>
</tr>
</table>
Площадь также сокращается. Наибольшее сокращение продемонстрировал иерархический умножитель.


== Выводы  ==
Наилучшими результатами в стандартном режиме обладают иерархические сумматоры. В режиме ULTRA high effort, наилучшими показателями обладает обычный встроенный умножитель. Наихудшие показатели оказались у 4-х модульного набора. Вероятно, это связанно с недостаточной оптимизацией и в дальнейшем удастся исправить ситуацию. Трехмодульный набор неплохо показал себя в сравнении с встроенным вариантом в стандартном режиме, после 32 бит выигрывая в производительности. Однако, иерархический подход не оставил шансов. А в ULTRA effort и вовсе все двоичные схемы оказались в преимуществе. Таким образом, модулярная арифметика вновь проигрывает двоичной. 


== UPDATE 07.06.13 ==
Добавлены результаты тестов [http://vscripts.ru/2013/high-bit-int-multiplication-recur.php рекурсивного умножителя.]

[[Изображение:all_timing_mult_with_rec.JPG]]
[[Изображение:all_area_mult_with_rec.JPG]]

Можно видеть, что рекурсивный вариант является "чемпионом" по занимаемой площади схем. А по временным характеристикам - на втором месте с конца. В плане задержки хуже рекурсивного - только 4-х модульный базис. Хотя, если приглядеться, то можно видеть что рекурсивный умножитель после 58-го бита начинает выигрывать у двоичного. Это в принципе согласуется с идеей того что рекурсивная арифметика начинает выигрывать на еще более масштабных задачах, нежли традиционная модулярная арифметика.

== Используемая литература  ==
[1] [http://opencores.org/websvn,filedetails?repname=pyramid_unit&path=%2Fpyramid_unit%2Ftrunk%2FInteger+multiplication+algorithms.pdf Vladimir V.Erokhin "Integer multiplication algorithms. Methodology and implementation results"]

[2] [http://www2.lirmm.fr/arith18/papers/Sousa-RNS.pdf Leonel Sousa, "Efﬁcient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli", 2007]