Сравнение разных методов умножения по модулю - 2^n-1,индексный,по методу разности квадратов и позиционный.

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «На основе [http://vscripts.ru/w/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BD%D1%8B%D1%85_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4…»)
 
 
(не показаны 4 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
На основе [http://vscripts.ru/w/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BD%D1%8B%D1%85_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%B2_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E прошлого исследования] было добавлено сравнение результатов с умножителем по модулю вида 2<sup>n</sup>-1.
 
На основе [http://vscripts.ru/w/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BD%D1%8B%D1%85_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D0%BE%D0%B2_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E прошлого исследования] было добавлено сравнение результатов с умножителем по модулю вида 2<sup>n</sup>-1.
Сравнение производилось для модулей с разрядностью от 2 до 10 бит.
+
Сравнение производилось для модулей с разрядностью от 2 до 9 бит.
 
Запуск производился на Synopsys Design Compiler.  
 
Запуск производился на Synopsys Design Compiler.  
  
== Генератор Verilog-модулей ==
+
== Типовой Verilog-модуль ==
 +
Для n = 3
 +
<pre>
 +
module mod_multiplier_7 (a,b,out);
 +
output wire [2:0] out;
 +
input  wire [2:0] a,b;
 +
wire [2:0] p_out0;
 +
wire [2:0] p_out1;
 +
wire [2:0] p_out2;
 +
reg  [3:0] res0;
 +
reg  [3:0] res1;
 +
 
 +
 +
assign p_out0[0] = a[0] && b[0];
 +
assign p_out0[1] = a[1] && b[0];
 +
assign p_out0[2] = a[2] && b[0];
 +
 
 +
 +
assign p_out1[0] = a[2] && b[1];
 +
assign p_out1[1] = a[0] && b[1];
 +
assign p_out1[2] = a[1] && b[1];
 +
 
 +
 +
assign p_out2[0] = a[1] && b[2];
 +
assign p_out2[1] = a[2] && b[2];
 +
assign p_out2[2] = a[0] && b[2];
 +
 
 +
always @ (*)
 +
begin
 +
res0=p_out0+p_out1;
 +
if(res0[3]==1)
 +
begin
 +
res0[3]=0;
 +
res0=res0+1;
 +
end
 +
res1=res0+p_out2;
 +
if(res1[3]==1)
 +
begin
 +
res1[3]=0;
 +
res1=res1+1;
 +
end
 +
if(res1==7)
 +
res1=res1+1;
 +
end
 +
assign out = res1[2:0];
 +
endmodule
 +
 
 +
</pre>
 +
 
 +
 
 +
Testbench
 +
<pre>
 +
module atest_bench();
 +
reg  [2:0] inp1,inp2;
 +
wire [2:0] out;
 +
integer fori,forj,i,l;
 +
reg dummy;
 +
 +
mod_multiplier_7 m1(inp1,inp2,out);
 +
 
 +
initial
 +
begin
 +
begin
 +
for (fori=1; fori < 7; fori = fori + 1)
 +
for (forj=1; forj < 7; forj = forj+1)
 +
begin
 +
inp1=fori;
 +
inp2=forj;
 +
#1 dummy = 1;
 +
i=(fori * forj)%7;
 +
//$display ("a=(%d) b=(%d) Res=(%d) expect=(%d)",fori,forj,out,i);
 +
l = out;
 +
if (l != i)
 +
begin
 +
$display ("Error i=(%d) l=(%d)",i,l);
 +
end
 +
#1 dummy = 1;
 +
end
 +
end
 +
end
 +
endmodule
 +
</pre>
 +
 
 +
== Генератор Verilog-модулей на языке TCL/TK ==
 
<pre>
 
<pre>
 
for { set n 2} {$n < 11} {incr n} {
 
for { set n 2} {$n < 11} {incr n} {
Строка 137: Строка 220:
 
<td style='border: 1px solid black; padding: 2px;'>Битность</td>
 
<td style='border: 1px solid black; padding: 2px;'>Битность</td>
 
<td style='border: 1px solid black; padding: 2px;'>Модуль для индексного умножителя</td>
 
<td style='border: 1px solid black; padding: 2px;'>Модуль для индексного умножителя</td>
<td style='border: 1px solid black; padding: 2px;'>Модуль для DS умножителя</td>
+
<td style='border: 1px solid black; padding: 2px;'>Модуль для DS и 2<sup>n</sup>-1 умножителя</td>
<td style='border: 1px solid black; padding: 2px;'>Модуль для 2<sup>n</sup>-1 умножителя</td>
+
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td style='border: 1px solid black;'>2</td>
 
<td style='border: 1px solid black;'>2</td>
<td style='border: 1px solid black;'>3</td>
 
 
<td style='border: 1px solid black;'>3</td>
 
<td style='border: 1px solid black;'>3</td>
 
<td style='border: 1px solid black;'>3</td>
 
<td style='border: 1px solid black;'>3</td>
Строка 148: Строка 229:
 
<tr>
 
<tr>
 
<td style='border: 1px solid black;'>3</td>
 
<td style='border: 1px solid black;'>3</td>
<td style='border: 1px solid black;'>7</td>
 
 
<td style='border: 1px solid black;'>7</td>
 
<td style='border: 1px solid black;'>7</td>
 
<td style='border: 1px solid black;'>7</td>
 
<td style='border: 1px solid black;'>7</td>
Строка 155: Строка 235:
 
<td style='border: 1px solid black;'>4</td>
 
<td style='border: 1px solid black;'>4</td>
 
<td style='border: 1px solid black;'>13</td>
 
<td style='border: 1px solid black;'>13</td>
<td style='border: 1px solid black;'>15</td>
 
 
<td style='border: 1px solid black;'>15</td>
 
<td style='border: 1px solid black;'>15</td>
 
</tr>
 
</tr>
Строка 166: Строка 245:
 
<td style='border: 1px solid black;'>6</td>
 
<td style='border: 1px solid black;'>6</td>
 
<td style='border: 1px solid black;'>61</td>
 
<td style='border: 1px solid black;'>61</td>
<td style='border: 1px solid black;'>63</td>
 
 
<td style='border: 1px solid black;'>63</td>
 
<td style='border: 1px solid black;'>63</td>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
 
<td style='border: 1px solid black;'>7</td>
 
<td style='border: 1px solid black;'>7</td>
<td style='border: 1px solid black;'>127</td>
 
 
<td style='border: 1px solid black;'>127</td>
 
<td style='border: 1px solid black;'>127</td>
 
<td style='border: 1px solid black;'>127</td>
 
<td style='border: 1px solid black;'>127</td>
Строка 178: Строка 255:
 
<td style='border: 1px solid black;'>8</td>
 
<td style='border: 1px solid black;'>8</td>
 
<td style='border: 1px solid black;'>251</td>
 
<td style='border: 1px solid black;'>251</td>
<td style='border: 1px solid black;'>255</td>
 
 
<td style='border: 1px solid black;'>255</td>
 
<td style='border: 1px solid black;'>255</td>
 
</tr>
 
</tr>
Строка 184: Строка 260:
 
<td style='border: 1px solid black;'>9</td>
 
<td style='border: 1px solid black;'>9</td>
 
<td style='border: 1px solid black;'>509</td>
 
<td style='border: 1px solid black;'>509</td>
<td style='border: 1px solid black;'>511</td>
 
 
<td style='border: 1px solid black;'>511</td>
 
<td style='border: 1px solid black;'>511</td>
 
</tr>
 
</tr>
Строка 194: Строка 269:
 
[[Изображение:2n-1_power.jpg]]
 
[[Изображение:2n-1_power.jpg]]
 
[[Изображение:2n-1_timing.jpg]]
 
[[Изображение:2n-1_timing.jpg]]
 +
 +
* [http://vscripts.ru/res/files/2^n-1-mul-results.zip Excel файл с табличками]
  
 
[[Категория:Результаты]]
 
[[Категория:Результаты]]

Текущая версия на 17:23, 25 февраля 2013

На основе прошлого исследования было добавлено сравнение результатов с умножителем по модулю вида 2n-1. Сравнение производилось для модулей с разрядностью от 2 до 9 бит. Запуск производился на Synopsys Design Compiler.

Содержание

[править] Типовой Verilog-модуль

Для n = 3

module mod_multiplier_7 (a,b,out);
output wire [2:0] out;
input  wire [2:0] a,b;
wire [2:0] p_out0;
wire [2:0] p_out1;
wire [2:0] p_out2;
reg  [3:0] res0;
reg  [3:0] res1;

	
assign p_out0[0] = a[0] && b[0];
assign p_out0[1] = a[1] && b[0];
assign p_out0[2] = a[2] && b[0];

	
assign p_out1[0] = a[2] && b[1];
assign p_out1[1] = a[0] && b[1];
assign p_out1[2] = a[1] && b[1];

	
assign p_out2[0] = a[1] && b[2];
assign p_out2[1] = a[2] && b[2];
assign p_out2[2] = a[0] && b[2];

always @ (*)
begin
	res0=p_out0+p_out1;
	if(res0[3]==1)
	begin
	res0[3]=0;
	res0=res0+1;
	end
	res1=res0+p_out2;
	if(res1[3]==1)
	begin
	res1[3]=0;
	res1=res1+1;
	end
if(res1==7)
		res1=res1+1;
end
assign out = res1[2:0];
endmodule


Testbench

module atest_bench();
	reg  [2:0] inp1,inp2;
	wire [2:0] out;
	integer fori,forj,i,l;
	reg dummy;
		
mod_multiplier_7 m1(inp1,inp2,out);

initial
	begin
		begin
		for (fori=1; fori < 7; fori = fori + 1)
			for (forj=1; forj < 7; forj = forj+1)
				begin
					inp1=fori;
					inp2=forj;
					#1 dummy = 1;
					i=(fori * forj)%7;
					//$display ("a=(%d) b=(%d) Res=(%d) expect=(%d)",fori,forj,out,i);
					l = out;
					if (l != i)
						begin
							$display ("Error i=(%d) l=(%d)",i,l);
						end
					#1 dummy = 1;
				end
		end
	end
endmodule

[править] Генератор Verilog-модулей на языке TCL/TK

for { set n 2} {$n < 11} {incr n} {

set q [expr round(pow(2,$n)-1)]
set b [expr $n-1]

set file1 "mod_multiplier_$q.v"
set out1 [open $file1 "w"]
puts $out1 "module mod_multiplier_$q (a,b,out);
output wire \[$b:0\] out;
input  wire \[$b:0\] a,b;"
			
	for {set pt 0} {$pt < $n} {incr pt} {
		puts $out1 "wire \[$b:0\] p_out$pt;"
	}
	for {set r 0} {$r < $b} {incr r} {
		puts $out1 "reg  \[$n:0\] res$r;"
	}
	for {set i 0} {$i < $n} {incr i} {
	puts $out1 "
	"
		for {set j 0} {$j < $n} {incr j} {
			set k [expr ($j -$i + $n)%$n]
			puts $out1 "assign p_out$i\[$j\] = a\[$k\] && b\[$i\];"
		}
	}
puts $out1 "
always @ (*)
begin"
for {set i 0} {$i < $n} {incr i} {
	set arr($i) "p_out$i"
}
	set arr_count $n
	set z 0
		
	while {1} {
		set arr_count1 0
		for {set i 0} {$i< [expr $arr_count-1]} {incr i 2} {
			set p_internal "res$z"
			set tmp1 [expr $i+1]
			puts $out1 "	$p_internal=$arr($i)+$arr($tmp1);"
			set RES "res$z\[$n\]"
			puts $out1 "	if($RES==1)
	begin
	res$z\[$n\]=0;
	res$z=res$z+1;
	end"
			set arr1($arr_count1) $p_internal
			incr arr_count1	
			incr z
		}
	set copy [expr $arr_count%2]
	if {$copy == 1} {
		set count2 [expr $arr_count-1]
		set arr1($arr_count1)  $arr($count2)
		incr arr_count1
	}
	if {$arr_count1 <= 1} {
		break;
		}
	# copy
	for {set i 0} {$i < $arr_count1} {incr i} {
		set arr($i) $arr1($i)
		set arr_count $arr_count1
	}
	}
set z [expr $z-1]
puts $out1 "if(res$z==$q)
		res$z=res$z+1;"
puts $out1 "end
assign out = res$z\[$b:0\];
endmodule
"
puts $out1 "module atest_bench();
	reg  \[$b:0\] inp1,inp2;
	wire \[$b:0\] out;"
puts $out1 "	integer fori,forj,i,l;
	reg dummy;
		
mod_multiplier_$q m1(inp1,inp2,out);
"
puts $out1 "initial
	begin
		begin
		for (fori=1; fori < $q; fori = fori + 1)
			for (forj=1; forj < $q; forj = forj+1)
				begin
					inp1=fori;
					inp2=forj;"
puts $out1 "					#1 dummy = 1;
					i=(fori * forj)\%$q;
					//\$display (\"a=(\%d) b=(\%d) Res=(\%d) expect=(\%d)\",fori,forj,out,i);
					l = out;"
puts $out1 "					if (l != i)
						begin
							\$display (\"Error i=(\%d) l=(\%d)\",i,l);
						end
					#1 dummy = 1;
				end
		end
	end
endmodule"	
}
close $out1

[править] Библиотека стандартных ячеек

NangateOpenCellLibrary_typical_conditional_nldm.lib

[править] Скрипт для запуска

analyze -f verilog <имя модуля>.v
elaborate <имя модуля>
uniquify
current_design <имя модуля>
check_design
set_load [load_of [get_lib_pins NangateOpenCellLibrary/INV_X4/A]] [all_outputs]
set_driving_cell -lib_cell DFFRS_X2 -library NangateOpenCellLibrary -pin Q  [all_inputs] 
set_max_delay -to [all_outputs] 0 
set_max_area 0 
compile
report_timing -significant_digits 6 > timing_<имя модуля>.rpt
report_area > area_<имя модуля>.rpt
report_power -analysis_effort high > power_<имя модуля>.rpt
remove_design -all

[править] Модули для эксперимента

Битность Модуль для индексного умножителя Модуль для DS и 2n-1 умножителя
2 3 3
3 7 7
4 13 15
5 31 31
6 61 63
7 127 127
8 251 255
9 509 511

[править] Результаты

2n-1 area.jpg 2n-1 power.jpg 2n-1 timing.jpg


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

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