工程设计最大公约数.docx
- 文档编号:16991503
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:15
- 大小:612.55KB
工程设计最大公约数.docx
《工程设计最大公约数.docx》由会员分享,可在线阅读,更多相关《工程设计最大公约数.docx(15页珍藏版)》请在冰点文库上搜索。
工程设计最大公约数
课程设计报告
题目:
用硬件设计一个最大公约数计算的算法电路
班级:
姓名:
学号:
合作者:
摘要:
本文论述的是采用二元的最大公约数算法,即欧基理德算法(EucldeanGCDAlgorithm)设计一个计算两个32位整数最大公约数(GCD)的处理器。
首先给出了欧几里得算法的描述,阐述了欧几里得算法原理;接着阐述了基本功能单元的选取和实现;随后详细的描述了设计过程和软硬件代码并对设计结果进行了分析、验证以及用QUARTUS软件对该程序进行仿真综合得出电路图。
要求设计一种的VLSI实现方案,该方案须使用Altera公司的FPGA设计流程实现,技术和功能上总体要求低功耗优先。
具体指标取下:
DC
Astro
工艺
SMIC.13tt1.2V
SMIC.13tt1.2V
单元库
SIMIC13IO_line_02_tt
SMIC13STDLIBM6
关键路径
2.79ns(约358MHz)
4.32ns(约230MHz)
静态功耗
1.86uw
动态功耗
3.99mw
area
39087um2
236um*236um=55696um2
利用率
N/A
82%
一、设计要求
1、目标:
设计一个计算两个32位整数最大公约数(GCD)的处理器。
2、输入:
OPA:
32-bit,操作数一;
OPB:
32-bit,操作数二;
START:
启动信号;
RESET:
复位信号;
CLK:
系统时钟。
3、输出:
DONE:
指示输出。
RESULT:
32-bit,最大公约数(GCD);
4、要求:
(1)采用二元的最大公约数算法,即欧基理德算法(EucldeanGCDAlgorithm);
(2)设计一种的VLSI实现方案,该方案须使用Altera公司的FPGA设计流程实现。
二、欧几里得算法描述
欧几里得算法的基础是下面这个定理:
设a,b,c为3个正整数,且
a=bq+c,
其中q为整数,则(a,b)=(b,c)。
另外,(b,0)=b。
给定两个正整数a,b,假设a≥b,求其最大公约数(gcd),使用欧几里得算法,先计算amodb得到c,再计算bmodc得到d,再计算cmodd得到e,……直到模的结果为0,那么0之前的那个数就是所求的最大公约数。
例如,求174和136的最大公约数,174→136→38→22→16→6→4→2→0
最大公约数是2。
在实现上,求模的方法就是做除法,保留余数。
如果细看一般求余数的方法,就是做减法,比如求amodb的过程(假设a>=b),从a中减去b的尽量大的倍数就得到模的结果。
但是,在实际中,这个“尽量大的倍数”(就是商)比较难找,所以,一般拿b的(……8倍、4倍、2倍、1倍)去试,每次减掉尽量大的一个,这样从大到小试,试完一遍就可以得到结果。
三、基本功能单元
1、基本功能单元的选取
基于这个理解,我们选取的基本单元完成的功能是:
从大数中减去小数尽量大的倍数(1倍、2倍、4倍、8倍……)。
我们不妨把这个操作叫做“贪婪减法”。
除此之外,对减法的结果,如果小于b,要和b交换位置,以保证每次运算都在a≥b前提下开始。
运算数a和b被模块读取后,先排序,使得a>=b,然后,a和b被基本功能单元反复运算,直到b变为0。
这时的a就是最大公约数。
图1基本功能单元
我们的方案使用一个基本单元,在控制电路控制下,反复计算,经过几个周期得到一个计算结果。
2、基本功能单元的实现
前面已经介绍了基本功能单元实现的功能,即“贪婪减法并排序”。
这可以通过组合逻辑实现。
最直观的想法是,a和b、2b、4b、8b、……(即b左移0位、1位、2位、3位、……后的结果)分别比较,找到满足b*2k≤a
但是,如果采用32个比较器并行地比较,
消耗的硬件资源将很大。
为了节省硬件,可以先检测a和b前导0的数目,相减得到b需要左移的位数,然后移位b到和a对齐的位置。
比较一次,就能找到需要的b*2k(记为bk)。
图2寻找尽量大的bk
如果balign≤a,则bk=balign;
否则,balign>a,这时bk=balign_sub。
基本功能单元的结构图(图3),头0编码和对数移位器用于找出和a第一个1对齐的balign,这个值和a比较,找到需要的bk(=b*2k),做减法得到a-bk,这个结果还需要和b比较进行排序。
也就是说,还要做a-bk-b的运算。
数据流如图4。
为了缩短流水线的长度,把可能需要的结果提前运算,然后根据需要选择相应的数据。
也就是,提前计算a-balign、a-balign_sub、a-balign-b、a-balign_sub-b。
这样改进后,组合逻辑的延时缩短了,代价是使用了更多的减法器。
最终的结构就是图3的形式。
图3基本功能单元(贪婪减法并排序)的硬件结构
图4初始的设计,太长的延时
四、设计过程描述
1、总体结构
使用一个“贪婪减法并排序”的基本功能单元,加上附加的控制,构建出我们的方案(图5)。
更加具体的内部结构如图6,图中的“预处理”是对OPA和OPB排序,保证进入寄存器a、b的值满足a≥b,通过简单的比较和选择逻辑就能实现。
图5方案模块图
图6方案的具体内部结构图
2、工作流程
在该方案中,完成一次运算需要多个周期。
运算数a和b被基本功能单元反复运算,直到b==0,运算完成,输出结果。
该方案的操作时序如图7,GCD模块作为一个对象受到MASTER的控制,START信号拉高后,GCD模块读取操作数OPA和OPB并开始运算,经过多次迭代运算,到b==0后,运算完成,DONE信号被置1,MASTER读取结果,然后撤销START,接着GCD模块撤销DONE信号。
图7方案的操作时序
图8方案的状态转换图
五、软硬件代码描述
1、求最大公约数的C语言算法
首先编写程序,用以描述所要实现的计算任务。
图9所示为求最大公因数(GreatestCommonDivisor,GCD)的系统框图,其输入为go_i、x_i和y_i,输出为d_o。
其中go_i为控制信号,x_i和y_i为两个输入的正整数,d_o为两个输入正整数的公因数。
图9最大公因数系统框图
求最大公约数的C语言算法如下:
intx,y,r;
while
(1){
while(!
go_i);
if(x_i≥y_i){
x=x_i;
y=y_i;
}
else{
x=y_i;
y=x_i;
}
while(y!
=0){
r=x%y;
x=y;
y=r;
}
d_o=x;
}
程序说明:
(1)该算法的功能很简单:
求两个输入数的最大公因数,并输出。
如果输入是12和9,则输出应该是3;如果输入是13和3,则输出应该为1。
可以利用C语言的集成开发环境(如VC++6.0)验证算法的正确性。
(2)程序中,go_i、x_i、y_i均为输入,d_o为输出,与图9框图中的输入输出一致。
go_为控制信号,只有该信号为有效电平(即高电平)时,才启动求最大公约数的进程,若为无效电平,则程序暂停直到该信号有效。
2、求最大公约数的Verilog代码(简稿,更加详细优化的Verilog代码见附件)
modulegcd(clk,x_i,y_i,go_i,d_o);
parameterN=6;//用于定义输入数的范围,最大为2**N-1
input[N-1:
0]x_i,y_i;
inputclk,go_i;
outputreg[N-1:
0]d_o;
parameters0=3'b111,s1=3'b001,s2=3'b010,s3=3'b011,s4=3'b100,s5=3'b101,s6=3'b110;
reg[2:
0]current_state,next_state;
reg[N-1:
0]x,y,r;
always@(posedgeclk)//状态寄存器
current_state=next_state;
always@(current_state,x_i,y_i,go_i,x,y,r)//产生下一个状态的组合逻辑
case(current_state)
s0:
if(go_i)next_state=s1;
elsenext_state=s0;
s1:
if(x_i>=y_i)next_state=s2;
elsenext_state=s3;
s2:
next_state=s4;
s3:
next_state=s4;
s4:
if(y>0)next_state=s5;
elsenext_state=s6;
s5:
next_state=s4;
s6:
next_state=s0;
default:
next_state=s0;
endcase
always@(negedgeclk)//产生输出和中间变量的组合逻辑
case(current_state)
s2:
begin
x=x_i;
y=y_i;
end
s3:
begin
x=y_i;
y=x_i;
end
s5:
begin
r=x%y;
x=y;y=r;
end
s6:
d_o=x;
default
endcase
endmodule
程序说明:
(1)部分注释见程序的旁注。
(2)本程序中的状态与图13(b)(见八、设计过程中遇到的问题与解决办法)中的状态一一对应关系如下:
s0—>2,s1—>3,s2—>4,s1—>6,s1—>8,s1—>9,s1—>12。
对照状态图阅读程序,一目了然。
六、设计结果的分析、验证及设计电路图
1、仿真波形图如图10所示。
图10QUARTUS仿真波形图
(1)从仿真波形可以看出,33和55的最大公约数为11,33和9的最大公约数为3,9和10的最大公约数为1,18和32的最大公约数为2,18和17的最大公约数为1,结果均正确。
(2)从仿真波形可以看出,得出最大公约数有一个延迟时间,这个延迟时间跟状态机有关,因为一个时钟周期状态机转换一次状态,而得到最大公约数需要完成一个完整的状态图,所以需要若干个时钟周期。
可以分析得出最大公约数与延迟两者之间的关系,并从仿真波形中得到验证。
(3)在仿真波形中,也将程序中用到的一些信号(比如状态机、中间信号x和y等)加了进去,这些信号用于分析状态机的运行过程非常有效。
(4)这里采用多进程的方式来描述状态机,每个进程功能明确。
另外,需要特别说明的是,在程序中既用到clk的上升沿,又用到了clk的下降沿,这样是为了使状态转换及输出的时序关系更清晰。
2、设计电路图
通过QUARTUS软件对该程序compile编译成功后,进行该程序的仿真综合,得到该算法的电路图如图11所示:
图11系统总体电路图
由于图片过大,不便于在word中显示,系统总体电路图和各模块电路图以附件的形式发过去。
七、性能估计
使用DC对设计进行综合,估计芯片的性能。
结果列于表1中。
表1方案的性能估计
DC
Astro
工艺
SMIC.13tt1.2V
SMIC.13tt1.2V
单元库
SIMIC13IO_line_02_tt
SMIC13STDLIBM6
关键路径
2.79ns(约358MHz)
4.32ns(约230MHz)
静态功耗
1.86uw
动态功耗
3.99mw
area
39087um2
236um*236um=55696um2
利用率
N/A
82%
可以分析得出,操作数是2537720636和4106118243将产生最坏情况,需要46次迭代才能得出运算结果。
在modelsim中仿真,随机产生10000组数,利用我们的模块求最大公约数,测试结果显示,共用了290656个周期,平均每次运算花费29个周期。
结合频率的估计值,运算速率约8Mop/s。
可见,该方案在技术和功能上总体满足低功耗优先的要求。
八、课程设计过程中遇到的问题与解决办法
<一>如何将C语言算法转换成Verilog硬件描述语言?
这个问题还是第一次接触,一点没有思路。
于是我在网上搜了一些资料,了解它的思路,参考了它的写法。
其中贺敬凯,王瑞春等人写的《将C算法转换为Verilog实现的一种方法》对我的帮助很大,下面给出将C语言算法转换成Verilog的实现方法。
1、C算法转换为Verilog实现的转换原理
将C语言算法转换成Verilog硬件实现,应该从C语言的特征着手。
C语言有三种基本的程序结构:
顺序结构、选择结构、循环结构;而且使用这三种基本结构可以实现任何复杂的算法。
因此,如果能够将这三种基本结构转换成可综合的Verilog表述,那么任何复杂的算法都可以用Verilog硬件来实现。
三种基本程序结构向状态图转换,如图12所示。
图12三种基本程序结构向状态图转换的模板
在以上转换模板的基础上,用硬件来实现程序算法,则需要以下4个步骤:
(1)首先将解决问题的算法用C语言程序或程序流程图表示。
(2)使用三种基本程序结构向状态图转换的模板,将C语言算法转换成一个复杂的状态图,图中的状态和边可包含算术表达式,表达式中可使用外部输入、输出以及变量。
这一步又分为如下两个子步骤:
A.先将所有语句分为赋值语句、循环语句或分支语句。
B.对于赋值语句、循环语句和分支语句,分别套用图2所示的转换模板将相应的程序语句转换为状态图。
(3)对于上一步得到的状态图进行化简。
这一步需要对以下状态化简:
①没有做任何事情的状态,可以删除;②两个状态间没有循环运算的或者是两个状态没有先后逻辑顺序关系的,可以合并。
(4)对于化简后的状态图,采用状态机实现。
对于这一步,建议采用3进程状态机实现。
2、下面具体说明由上面介绍的转换步骤将C语言描述的最大公约数算法转化为Verilog硬件描述语言实现。
(1)将程序算法转换成一个复杂的状态图
采用图12的模板,将C语言描述的最大公约数算法可以方便转换成状态图,如图13(a)所示。
(2)状态图化简
在图13(a)所示的状态图中,可以看出,该状态图中有几个状态根本没有做任何事情,因此可以将其删除;另外有一些状态可以合并。
下面对图13(a)的状态图进行化简。
显然,状态1没有做任何事情,没有必要存在;状态2和状态2-J可以合并为一个状态,因为在两者之间没有循环运算;状态4和状态5也可以合并,因为它们所执行的赋值运算彼此无关,同理,状态6和状态7也可以合并,状态9、状态10和状态11也可以合并;状态3-J和状态8可以合并;状态1-J可以去掉。
化简后的状态图如图13(b)。
图13(a)求最大公约数的状态图图13(b)化简后的状态图
(3)使用VerilogHDL语言实现状态图。
得到化简的状态图后,下一步骤就是使用VerilogHDL状态机实现该状态图,具体的Verilog实现代码如五、2。
3、总结
这里提出将C语言算法转换为Verilog硬件实现的方法有通用性,对于数字系统来说,可以首先采用C语言来描述算法,然后再使用本文介绍的方法予以转换。
提出的方法,可以大大提升数字系统的设计效率,同时也可以借鉴成熟的软件设计技术。
仅就C算法转换为Verilog实现的转换原理作了重点介绍,如果能够在此基础上将这种方法编制成自动化软件,则在硬件设计技术方面是一个重大的突破。
<二>如何编写详细优化的Verilog代码?
这一部分也是难点,因为从未写过这么长的verilog代码。
平时学习verilog,书本和上机作业都是一些很简单的程序,一般不超过100行的。
这个工程文件分为好几个模块,这一部分我参考了武汉大学电工电子基础课程教学基地的曹华伟老师指导的实验报告。
参考着写了出来,详见附件。
参考文献与资料列表
[1]基于C/C++语言最大公约数算法的研究陶洁襄樊职业技术学院学报JournalofXiangfanVocationalandTechnicalCollege第5卷第1期2006年1月。
[2]将C算法转换为Verilog实现的一种方法贺敬凯、王瑞春、万学元、潘晓宁、郑芙蓉、李晓堂深圳信息职业技术学院电子通信技术系广东深圳2010,46(30)71页。
[3]两种求解最大公约数算法的比较及实际应用吴殿红、刘阳滨州学院计算机科学技术系山东滨州256600
[4]武汉大学电工电子基础课程教学基地实验报告曹华伟2010年6月18日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工程设计 最大公约数