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

Материал из Модулярная арифметики
Перейти к: навигация, поиск

На основе прошлого исследования было добавлено сравнение результатов с умножителем по модулю вида 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