工程设计——最大公约数.doc

课程设计报告题目：用硬件设计一个最大公约数计算的算法电路班级：姓名：学号：合作者：摘 要：本文论述的是采用二元的最大公约数算法，即欧基理德算法（Eucldean GCD Algorithm）设计一个计算两个 32位整数最大公约数（GCD）的处理器。 首先给出了欧几里得算法的描述，阐述了欧几里得算法原理；接着阐述了基本功能单元的选取和实现；随后详细的描述了设计过程和软硬件代码并对设计结果进行了分析、验证以及用QUARTUS 软件对该程序进行仿真综合得出电路图。要求设计一种的 VLSI实现方案，该方案须使用 Altera公司的FPGA 设计流程实现，技术和功能上总体要求低功耗优先。具体指标取下：DCAstro工艺SMIC.13 tt 1.2VSMIC.13 tt 1.2V单元库SIMIC13IO_line_02_ttSMIC13STDLIBM6关键路径2.79ns（约 358MHz）4.32ns（约 230MHz）静态功耗1.86uw动态功耗3.99mwarea39087 um2236um*236um=55696 um2利用率N/A82%一、设计要求 1、目标： 设计一个计算两个 32位整数最大公约数（GCD）的处理器。 2、输入： OPA：32-bit，操作数一； OPB：32-bit，操作数二； START：启动信号； RESET：复位信号； CLK：系统时钟。 3、输出： DONE：指示输出。 RESULT：32-bit，最大公约数（GCD）；4、要求： l (1)采用二元的最大公约数算法，即欧基理德算法（Eucldean GCD Algorithm）； l (2)设计一种的 VLSI实现方案，该方案须使用 Altera公司的FPGA 设计流程实现。二、欧几里得算法描述 欧几里得算法的基础是下面这个定理：设a,b,c为3 个正整数，且a=bq+c ,其中q为整数，则(a,b)=(b,c)。另外，(b,0)=b。 给定两个正整数 a,b,假设ab ，求其最大公约数（gcd），使用欧几里得算法，先计算a mod b得到 c,再计算b mod c 得到d，再计算c mod d 得到e，直到模的结果为0，那么0之前的那个数就是所求的最大公约数。 例如，求 174 和136的最大公约数，1741363822166420 最大公约数是 2。 在实现上，求模的方法就是做除法，保留余数。 如果细看一般求余数的方法，就是做减法，比如求 a mod b 的过程（假设 a=b），从a 中减去b的尽量大的倍数就得到模的结果。但是，在实际中，这个“尽量大的倍数”（就是商）比较难找，所以，一般拿 b 的（8 倍、4 倍、2 倍、1 倍）去试，每次减掉尽量大的一个,这样从大到小试，试完一遍就可以得到结果。三、 基本功能单元 1、 基本功能单元的选取 基于这个理解，我们选取的基本单元完成的功能是：从大数中减去小数尽量大的倍数（1 倍、2 倍、4 倍、8 倍）。我们不妨把这个操作叫做“贪婪减法”。除此之外，对减法的结果，如果小于 b，要和 b 交换位置，以保证每次运算都在ab 前提下开始。 运算数a 和b 被模块读取后，先排序，使得 a=b，然后，a 和b 被基本功能单元反复运算，直到 b 变为0。这时的a 就是最大公约数。图 1 基本功能单元我们的方案使用一个基本单元，在控制电路控制下，反复计算，经过几个周期得到一个计算结果。2、 基本功能单元的实现前面已经介绍了基本功能单元实现的功能，即“贪婪减法并排序” 。这可以通过组合逻辑实现。 最直观的想法是，a 和b、2b、4b、8b、（即 b 左移0 位、1 位、2 位、3 位、后的结果）分别比较，找到满足b*2kaa，这时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 的值满足ab ，通过简单的比较和选择逻辑就能实现。图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语言算法如下：int x，y，r；while（1）while（!go_i）；if （x_i y_i） x=x_i；y=y_i；elsex=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代码见附件）module gcd(clk,x_i,y_i,go_i,d_o);parameter N=6; /用于定义输入数的范围， 最大为2*N-1inputN-1:0x_i,y_i;input clk,go_i;output regN-1:0d_o;parameter s0=3b111,s1=3b001,s2=3b010,s3=3b011,s4=3b100,s5=3b101, s6=3b110;reg2:0current_state,next_state;regN-1:0x,y,r;always(posedge clk)/状态寄存器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; else next_state=s0;s1：if(x_i=y_i) next_state=s2;else next_state=s3;s2: next_state=s4;s3: next_state=s4;s4:if(y0) next_state=s5; else next_state=s6;s5: next_state=s4;s6: next_state=s0;default:next_state=s0;endcasealways(negedge clk) /产生输出和中间变量的组合逻辑case (current_state)s2： begin x=x_i; y=y_i; ends3： begin x=y_i; y=x_i; ends5： begin r=x%y; x=y;y=r; ends6： d_o=x;defaultendcaseendmodule程序说明：（1） 部分注释见程序的旁注。（2） 本程序中的状态与图13(b)（见八、设计过程中遇到的问题与解决办法）中的状态一一对应关系如下：s02，s13，s24，s16，s18，s19， s112。对照状态图阅读程序，一目了然。六、设计结果的分析、验证及设计电路图1、仿真波形图如图10所示。图10 QUARTUS仿真波形图(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 方案的性能估计DCAstro工艺SMIC.13 tt 1.2VSMIC.13 tt 1.2V单元库SIMIC13IO_line_02_ttSMIC13STDLIBM6关键路径2.79ns（约 358MHz）4.32ns（约 230MHz）静态功耗1.86uw动态功耗3.99mwarea39087 um2236um*236um=55696 um2利用率N/A82%可以分析得出，操作数是 2537720636 和 4106118243 将产生最坏情况，需要46次迭代才能得出运算结果。在modelsim中仿真，随机产生10000组数，利用我们的模块求最大公约数，测试结果显示，共用了 290656 个周期，平均每次运算花费29 个周期。结合频率的估计值，运算速率约 8M op/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状态机实现该状态图，具体的Verilo