Комплексное исследование умножителей в диапазоне 3 - 64 бит

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
 
(не показаны 28 промежуточных версий 1 участника)
Строка 4: Строка 4:
 
* Иерархический двоичный умножитель [1].
 
* Иерархический двоичный умножитель [1].
 
* Модулярный умножитель со стандартным спец. базисом из трех модулей (''3 moduli set'') <math>(2^n-1, 2^n, 2^n+1)</math>
 
* Модулярный умножитель со стандартным спец. базисом из трех модулей (''3 moduli set'') <math>(2^n-1, 2^n, 2^n+1)</math>
* Модулярный умножитель с продвинутым спец. базисом из 4-х модулей (''3 moduli set'') <math>(2^n-1, 2^n+1, 2^{n+1}-1, 2^{n+1}+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''. Таким образом, также проверялась способность САПРа по минимизации задержек для различных схем. Таким образом, общее количество тестов выглядит следующим образом.
+
Синтез проводился в базисе 45 нм. в библиотеке NangateOpenCellLibrary.lib с помощью САПР Synopsys Design Compiler. Синтез проводился дважды для каждой из схем, на разных настройках "усилий" синтезатора - ''medium'' и ''ultra high effort''. Таким образом, также проверялась способность САПРа по минимизации задержек для различных схем. Общее количество тестов выглядит следующим образом.
  
 
{| border="1" cellpadding="5" cellspacing="0"
 
{| border="1" cellpadding="5" cellspacing="0"
Строка 27: Строка 27:
 
|-
 
|-
 
|}
 
|}
 +
 +
 +
== Ссылки на генераторы 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 high effort  ==
[[Изображение:ultra1.JPG]]
+
Графики скомпонованы для иллюстрации эффективности 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"]
 
[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, "Efficient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli", 2007]

Текущая версия на 18:37, 7 июня 2013

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

  • Встроенный умножитель в САПР Synopsys Design Compiler.
  • Иерархический двоичный умножитель [1].
  • Модулярный умножитель со стандартным спец. базисом из трех модулей (3 moduli set) (2^n-1, 2^n, 2^n+1)
  • Модулярный умножитель с продвинутым спец. базисом из 4-х модулей (4 moduli set) (2^n-1, 2^n+1, 2^{n+1}-1, 2^{n+1}+1)

Синтез проводился в базисе 45 нм. в библиотеке NangateOpenCellLibrary.lib с помощью САПР Synopsys Design Compiler. Синтез проводился дважды для каждой из схем, на разных настройках "усилий" синтезатора - medium и ultra high effort. Таким образом, также проверялась способность САПРа по минимизации задержек для различных схем. Общее количество тестов выглядит следующим образом.

Модулярный Двоичный
3 moduli set 4 moduli set Встроенный Иерархический
medium effort ultra effort medium effort ultra effort medium effort ultra effort medium effort ultra effort


Содержание

[править] Ссылки на генераторы Verilog описаний исследуемых схем

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


[править] Общие результаты

All timing mult.JPG All2.JPG

[править] Сравнение двоичных схем

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


Bin1.JPG Bin2.JPG


[править] Сравнение модулярных схем

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

Mod1.JPG Mod2.JPG


[править] Анализ эффективности САПР в режиме ULTRA high effort

Графики скомпонованы для иллюстрации эффективности ULTRA режима.

Ultra compl mult1.JPG

Ultra compl mult2.JPG

Ultra3.JPG

Ultra4.JPG


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


Схема умножителя Средний коэффициент увеличения производительности
Встроенный умножитель в САПР Synopsys Design Compiler. 68
Иерархический двоичный умножитель 31
Модулярный умножитель со стандартным спец. базисом из трех модулей 28
Модулярный умножитель с продвинутым спец. базисом из 4-х модулей 38

Площадь также сокращается. Наибольшее сокращение продемонстрировал иерархический умножитель.


[править] Выводы

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


[править] UPDATE 07.06.13

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

All timing mult with rec.JPG All area mult with rec.JPG

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

[править] Используемая литература

[1] Vladimir V.Erokhin "Integer multiplication algorithms. Methodology and implementation results"

[2] Leonel Sousa, "Efficient Method for Magnitude Comparison in RNS Based on Two Pairs of Conjugate Moduli", 2007


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация