（微电子学与固体电子学专业论文）基于初始验证的自动流水线生成.pdf

摘要 摘要 随着大规模集成电路事业的飞速发展，在单一l s i 芯片上集成完整的系统已 经成为可能。而作为其中重要组成部分的验证，尤其是对于大规模系统的验证过 程往往要消耗大量的时间，甚至占据了整个设计时间的百分之六十以上。为了减 少验证过程，利用f p g a 验证是一种较为可行且普遍的功能性测试模式，但这种 方法也存在其相应的弊端，就是在验证大规模系统的时候由于结构的限制往往需 要较长的时间来完成。本论文将讨论一种全新的电路验证加速方法，即自动生成 流水线结构。在这种方法中，输入端是f p g a 的生成结果，且通过在电路中增添 逻辑单元来将电路分割成流水线的结构，从而达到增加处理速度、改进处理结果 的目的。在这里我们必须注意的是这种建立流水线结构的方法将把系统中的某个 需要改进的组合电路分割成两个甚至多个部分从而达到降低延迟以及增大速度的 结果，但相应的电路的最高频率也会增加。通过用这种流水线结构，电路的数据 处理量被大幅度的提高了。另外，为了减少流水线结构所带来的附加资源损耗， 本文还提出了一种基于基础逻辑单元( l u t ) 或者f p g a 逻辑单元的电路改进方 法，该方法从基本算法上对电路实施了“切割”以达到增加运算速度的目的。除 此之外，本文还讨论了一些在改进流水线结构时可能出现的问题以及条件。 关键词：流水线结构基本逻辑单元验证切入点数据前进法 a b s t r a c t w i t ht h er a p i dp r o g r e s si nl s ip r o c e s s ，w ec a ni n t e g r a t eal a r g es y s t e mo no i l e l s ic h i p v e r i f i c a t i o no fal a r g es y s t e mi st i m ec o n s u m i n g ，a n dt a k e sm o r et h a n6 0 o f t h et o t a ld e s i g nt i m e t or e d u c et h ev e r i f i c a t i o np e r i o d ，t h ef u n c t i o n a lt e s tu s i n gf p g a p r o t o t y p i n gi sw i d e l yu s e d ，b u tt h es p e e di sn o te n o u g hf o rl a r g es y s t e m s i n t h i st h e s i s ， w ep r o p o s ean e wa p p r o a c hf o rt h ea c c e l e r a t i o no fc i r c u i t sb ya u t o m a t i c a l l yg e n e r a t i n g p i p e l i n es t r u c t u r e i nt h em e t h o d ，i n p u t sa le t h ef p g am a p p i n gr e s u l t s ，a n dt h el u t b a s e dc i r c u i t sa r ec o n v e r t e dt op i p e l i n es t r u c t u r et oi m p r o v et h ep e r f o r m a n c e n o t et h a t t h em e t h o dw i l ld i v i d ec o m b i n a t i o n a lp a r to fac i r c u i ti n t ot w oo rm o r ep a r t sw i t h s h o r t e rd e l a y , a n dt h eh i g h e s tf r e q u e n c yw i l li n c r e a s e b ye x e c u t i n gt h ec i r c u i tu s i n g t h e p i p e l i n e dw a y , t h ed a t at h r o u g h p u to ft h ec i r c u i tc a nb ei m p r o v e d w ea l s od e v i s et h e r e s o u i c er e d u c t i o nm e t h o di nt h ep i p e l i n ec i r c u i tg e n e r a t i o nb a s e do nt h ep r o p e r t yo f l u t so rl o g i ce l e m e n t so ff p g a w e c i r c u i t si n t ot w oo rm o r ep a r t s ，a n d b e h a v i o r d e v i s e dac u t s e tb a s e da l g o r i t h mt od i v i d et h e d i s c u s ss o m ec o n d i t i o n sf o rc o r r e c tp i p e l i n e k e y w o r d s ：p i p e l i n e s l u tc u t - s e tp r o t o t y p i n gv e r i f i c a t i o n d a t af o r w a r d i n g 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：盈里日期砂：至：! 兰 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期丝：至：! 兰 ， 日期垒! f 翌：；：! 兰 一锋 第一章绪论 第一章绪论 1 1 课题背景 随着计算机技术、电子技术的迅速发展以及集成电路生产工艺的不断提高， 电子产品的更新换代以及电路规模也获得了日新月异的发展。在过去的二十年 中，基于摩尔定律的超大规模集成电路研究和开发获得了极大程度上的进步，这 种革命性的发展使得我们在系统设计中大规模的使用硬件资源成为了可能。与此 同时，为了保证设计过程的顺利进行，验证已经成为了v l s i 研究中非常重要的 组成部分，在通常的设计规划中，验证要占整个设计流程的百分之六十以上，从 某种程度上说，它甚至比设计本身更加重要。但随着芯片规模呈现指数式的上 升，验证能力已经远远落后于设计能力，并且正在成为制造功能更复杂、规模更 庞大的芯片的瓶颈。另一方面，电子器件及芯片的面市时间却要求以令人震惊的 速度缩短，设计周期缩短的比其他任何细分市场都快。这些都对现有的验证手段 提出了严峻的挑战，同时也促使新型的验证思想和验证手段应运而生。但在各种 各样的验证方法当中，仅仅采用软件仿真和形式验证是很不够的，还需做其他一 些不同的验证，这些验证方法互相补充，以尽可能提高芯片验证的覆盖率，其中 很重要的就是系统级的f p g a 验证。由于f p g a 验证系统与实际的系统很接近， 在这样一个系统上，芯片运行的速度和实际系统可比拟甚至一样，这有助于发现 一些出现概率很低的b u g ，很容易运行一些在软件仿真中不太实际的测试；其 次，对于一个f p g a 验证系统，可以把它视为一个实际芯片构成的系统，完全可 以在此基础上利用各种相对应的算法或者开发工具开发出相应的测试平台和改善 模式，这就使得芯片代码的验证与实际芯片的测试类似，并且这种用于代码验证 的所开发的工具和算法完全可以用于芯片设计之后的测试，因而大大减小了工作 量，提高了工作效率。其实无论选择开发工具或者改进算法，最终的目的都是为 了降低验证时间这样一个极为重要的课题。另外，在各种验证方法中，初始验证 是一种在设计过程中被广泛应用的验证方式，但一般的在f p g a 中生成大规模的 原始电路的初始验证模式已经被证明是一种非常缓慢的方法，需要耗费大量的时 间，对于设计周期日渐缩短的当前形势来说，效率成为了初始验证模式的最大问 题。因此加速化就成为f p g a 初始验证中个非常重要的组成部分。众所周知， 电路加速化的方法有很多，设计者可以通过硬件或者仿真等各种方式对要求电路 2基于初始验证的自动流水线生成 进行优化。这里将讨论一些用于电路加速化的基本方法，并对这些方法进行总 结，进而引出本文所要讨论的主要内容。 1 1 1 用于电路加速化的再综合 综合在大规模集成电路设计中扮演着非常重要的角色。从2 0 世纪7 0 年代开 始，应用于数字电路系统中的生成有效可执行结果的综合工具就已经开始被广泛 的应用，其中的很多种则是专门为一般数字电路系统的数据路径生成所开发的。 众所周知，在电路设计中常常要用到一些硬件描述语言如v h d l ，v e r i l o g h d l 等等，用这些硬件描述语言完成设计以及优化进程时，都必须要经过综合的步 骤。但是，综合的结果往往却不能总是尽如人意。设计及优化的过程都必须在增 大运算速度和减小芯片面积两方面作出取舍，而这种取舍对于设计者而言往往非 常复杂并且很难抉择。所谓的再综合过程就是一种在商业综合工具以及研究综合 工具中被广泛应用的方法，简单说来就是应用综合工具对一个具体到门级的电路 进行优化。利用再综合方法，可以使得数项工作在同一时间内完成，从而达到加 速化的效果。 1 】，【2 】。图1 表示了综合和再综合的基本流程。 t r a d i t i o n a ld e s i g nf l o w r e - s y n t h e s i sd e s i g nf l o w s c r i p t i o n0 c i r c u i t h i c l hl e v e is v n t h e s i s i o c li cs v n t h e s i s f l o o rd l a n n i p l a c e m e n t r 0 u t i 奢y o u tp a t t e r n 石 一 ac h i p - 一 否s c r i p t i o n0 c i r c u i t h i a hi e v e is v n t h e s i s a c e m e n t r o u t i n a y o u ip a t t e r no ac h i p ， r e - s 舳e 9 b 图1 综合与再综合的流程比较 f i g u r e1 c o m p a r i s o nw i t hs y n t h e s i sa n dr e s y n t h e s i s 再综合是一种改进初始验证进程的非常有效的方法，当然，如果可以进一步 的减少再综合过程中组合电路部分的电路路径延迟的话，就完全可以使验证进程 获得更大程度的提高和改进。目前已经研究出了一些改善再综合的方法，如系统 单元代换，核心路径辨别及选择等等，这里不再一一赘述。 堂 i 薹 忙一 一o 型 一b b 一 一同 第一章绪论 1 2 流水线技术的概念 流水线技术是一种用于高效数字电路的优化方法，同时它也可以被用来改进 初始验证的运行流程。一般说来，流水线技术是将一个复杂的或者非常耗时的工 作分割成数个子模块，然后将这些子模块同时独立的进行处理，从而达到增大处 理速度以及优化系统资源的目的。举例来说，在一个流水线处理器设计中，一个 执行命令可以被分为数个相互独立的子命令，比如命令获取，命令解码以及命令 存储等等，通过这种方法，处理器的速度可以在很大程度上被提高【3 】。另外，通 过将工作分割成数量不同的子模块，系统频率也会相应的增大。 在流水线技术中，一个单一的组合电路模块将首先被寄存器( 例如锁存器 或触发器) 分割成数个子组合电路，如果这样的分割方法确实可以将最大延迟 时间降低至预估时间的一半左右，那么在此电路中应用流水线技术的目标就算 达成。图2 表示的是流水线技术降低系统延迟的基本概念。 c 图2 用流水线结构减小延迟 f i g u r e2 d e l a yr e d u c t i o nw i t hp i p e l i n es t r u c t u r e 在图2 中，t 是预估的运算时间，通过增添触发器，使得运算时间被降低至 预估时间t 的一半，即t 2 。这里需要注意的是所有的数据在通往下一个单元的 同时，必须首先在增添的触发器中进行存储，等待发出指令的时钟信号到达之后 才可以继续前进至下一个单元。 综上所述，流水线技术的核心内容就是通过寄存器的加入从而分割原始电 4 基于初始验证的自动流水线生成 路，增大电路的运算速度，提高工作频率。与此同时，原本的电路工作的流程也 从较为单一的单线运行模式转化为了多线同时运行模式。但不可否认的是，由于 在提高运行速度的时候需要额外寄存器的加入，电路面积不可避免的得到了增 大。对于超大规模集成电路设计而言，过大的面积意味着该芯片无法在某些原本 适用的电路中使用。因此在使用流水线技术的时候要考虑速度和面积的折衷关 系，选择合适的流水线分割位置可以使得额外需要添加的寄存器数目降到最小。 从而合成面积更小的流水线电路，即在电路中实现最佳流水线化。 第二章初始延迟测量的方法 第二章初始延迟测量的方法 上一章已经简单的说明，在初始验证的加速化过程中可以通过流水线技术来 提高运算效率，基本方法就是通过将一个原始的组合电路分割成两个几乎拥有同 样大小延迟的子电路。为了达到这个目的，首先应该明确需要进行优化的组合电 路的延迟的大小。本章将讨论组合电路中测量延迟的一种方法，即基本逻辑单元 的极限深度判断法。 2 1 图论的概念 数字电路是一种相当复杂的电路结构，尤其在超大规模集成电路设计越发进 展的今天，一般在芯片中使用的电路结构已经上升到了动辄百万门级的程度，像 这样巨大的电路按照常规的观察和分析几乎是不可能完成的任务。为了解决这样 的问题，我们引入了图的概念来分析和解决相关的问题。 简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是 一种数据结构，定义为：g r a p h = ( v ，e ) ，v 是点( 称为“顶点 ) 的非空有限集 合，e 是线( 称为“边”) 的集合，边一般用( v x ，v y ) 表示，其中v x ，v y 属于 v 。如果边是没有方向的，称此图为“无向图，用一对圆括号表示无向边，如果 边是有方向( 带箭头) 的，则称此图为“有向图”，用一对尖括号表示有向边， 如果两个顶点u 、v 之间有一条边相连，则称u 、v 这两个顶点是关联的。与此 同时，一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图 ( c ) ，这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边 的权。边上带有权的图称为带权图，也称为网( 络) 。 在了解了图的概念之后，我们需要进一步了解路径的概念以便能够更加快捷 的认识图与数字电路之间的关系。在一个g = ( v ，e ) 的图中，从顶点v 到顶点 v 的一条路径是一个顶点序列v i 0 ，v i l ，v i 2 ，v i m ，其中v i 0 = v ， v i m = v ，若此图是无向图，贝j j ( v i j l ，v i j ) e ，1 j m ；若此图是有向图，n e ，l i m 。路径长度是指路径上的边或弧的数目。序列中顶点不重复出 现的路径称为简单路径，顶点v 和顶点v 相同的路径称为回路( 或环) 。除了第 一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路( 或 简单环) 。在无向图g 中，如果从顶点u 到顶点v 有路径，则称u 和v 是连通 6 基于初始验证的自动流水线生成 的。如果对于图g 中的任意两个顶点u 和v 都是连通的，则称图g 是连通图， 否则称为非连通图。在有向图g 中，如果对于任意两个顶点u 和v ，从u 到v 和从v 到u 都存在路径，则称图g 是强连通图。 作为应用数学中一个非常重要的组成部分，图论就是以图为研究对象进而阐 述相关的理论和算法的。图论中的图是由若干给定的点及连接两点的线所构成的 图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用 连接两点的线表示相应两个事物间具有这种关系。而对于数字电路系统而言，数 以百万计的逻辑单元如果以图论的方式表达可以看作为是图中的一个个节点，而 逻辑单元之间的布线则可看作为是点与点之间的连线。通过这种表达方式，我们 就将数字电路结构与图紧密的结合在一起，进而通过图的基本算法来对数字电路 的变化和进程进行理论上的分析和计算。 数字电路系统的一大特征就是无论组合电路抑或是反馈电路，逻辑门与逻辑 门之间的布线都可以被人为地看做可分离的，也就是说在根据电路需要可以在门 与门之间的布线中添加一定数量的寄存器或者基本逻辑单元，进而起到分割延迟 或者增大时钟频率的目的。为了讨论每个延迟是否具有分割意义，首先应当对于 延迟进行一个适当的定义，在图论中，如果以路径的深度来代表电路的延迟大 小，那么逻辑单元深度就成了一种被广泛应用的测量延迟的方法。具体来说，一 个单元的最大深度m n ( v ) 可以通过如下方式定义： ( 1 ) 对于原始输入p i ， m a ( p i ) = 0 m a ( p i ) = 0 ( 2 ) 对于内部节点v ，即其他内部的所有节点“t ，v 2 ，v h ) ， m a ( v ) = m r x m a ( v i ) + 1 j = l 图3 表示了个比较典型的可以说明上述定义的电路。当逻辑门a 是所有输 入端的初始输入时，m d ( a ) 的最大延迟就为1 ，与此同时相应的m d ( b ) 的最大延迟 也是l ，而此时m 一( c ) 的最大延迟就为2 ，这是因为它的两个输入端的最大延迟都 是1 。与此相对应的当m d ( d ) 的的两个输入端的延迟为1 的时候，它最大延迟也 为2 。 在明确了最大延迟的定义之后，最小延迟的定义也可以用相似的方法进行描 述。 第二章初始延迟测量的方法 7 ( 1 ) m d ( p i ) = 0 ( 2 ) m d ( v ) 2m 。i n ， m a ( v i ) ) + l 在这种定义模式下，m d ( a ) = m a ( b ) = 1 ，m a ( c ) = 2a n dm a ( d ) = 1 一般情况下，当一个电路某个逻辑门m a ( v ) 的最大深度为v 的时候，我们就 可以使用这种定义方法。在图3 所表示的电路结构中，该电路的最大延迟为4 ， 同时，从图3 中也可以看出它的最小延迟为2 1 6 。 2 2 最大路径 d e l a y = 4 图3 最大延迟的概念 f i g u r e3 m a xd e l a y 在明确了最大延迟的定义方法之后，现在让我们将注意的焦点转向关键路径 的判断。众所周知，流水线技术就是一种在一个电路的某个最佳位置插入寄存器 从而控制电路的运行以达到最佳的优化效果的方法。因此，如何找到这个“最 佳”的位置就变成了该技术能否得到有效广泛的应用的关键。为了解决这个问 题，我们可以通过计算最大深度的方法来确定。为了能更好的理解最大路径的定 义和计算，我们采用从图的角度进行分析的方法。 在带权图g = ( v ，e ) 中，若顶点，v j 是图g 的两个顶点，从顶点到 v j 的路径长度定义为路径上各条边的权值之和。从顶点v i 到v j 可能有多条路 径，其中路径长度最小的一条路径称为顶点到v j 的最短路径。求最短路径具 有很高的实用价值，在各种竞赛中经常遇到。一般有两类最短路径问题：一类是 求从某个顶点( 源点) 到其它顶点( 终点) 的最短路径；另一类是求图中每一对 顶点间的最短路径。对于不带权的图，只要人为的把每条边加上权值1 ，即可当 8基于初始验证的自动流水线生成 作带权图一样处理了【1 7 】。 关于计算最大路径的方法，世界上目前已经开发出了很多很多有效的模式。 一种最常见也最为流行的方法被称为d i j k s t r a 算法思想。在这个算法中，对于一 个含有1 1 个顶点和e 条边的图来说，从某一个顶点到其余任一顶点v j 的最短 路径，可能是它们之间的边( v i ，v j ) ，也可能是经过k 个中间顶点和k + l 条边 所形成的路径( 1 k n 2 ) 。 设图g 用邻接矩阵的方式存储在g a 中，g a i , j - - m a x i n t 表示，是不关 联的，否则为权值( 大于o 的实数) 。设集合s 用来保存已求得最短路径的终点 序号，初始时s = 】表示只有源点，以后每求出一个终点v j ，就把它加入到集合 中并作为新考虑的中间顶点。设数组d i s t 1 n 】用来存储当前求得的最短路径，初 始时，v j 如果是关联的，则d i s t j 等于权值，否则等于m a x i m ，以后随着新考 虑的中间顶点越来越多，d i s t j 可能越来越小。再设一个与d i s t 对应的数组 p a t h 1 n 】用来存放当前最短路径的边，初始时为到v j 的边，如果不存在边则 为空。 执行时，先从s 以外的顶点( 即待求出最短路径的终点) 所对应的d i s t 数组 元素中，找出其值最小的元素( 假设为d i s t m 】) ，该元素值就是从源点到终点 v m 的最短路径长度，对应的p a t h m 】中的顶点或边的序列即为最短路径。接着把 v m 并入集合s 中，然后以v m 作为新考虑的中间顶点，对s 以外的每个顶点 v j ，比较d i s t m + g a m , j 的d i s t j 的大小，若前者小，表明加入了新的中间顶点 后可以得到更好的方案，即可求得更短的路径，则用它代替d i s t j ，同时把v j 或 边( v m ，v j ) 并入到p a t h j 中。重复以上过程n - 2 次，即可在d i s t 数组中得到从 源点到其余各终点的最段路径长度，对应的p a t h 数组中保存着相应的最段路径。 为了能更好的理解d i j k s t r a 算法思想的含义，我们在下面给出具体的d i j k s t r a 算法框架为了实现上的方便，我们用一个一维数组s 【1 n 】代替集合s ，用来保存 已求得最短路径的终点集合，即如果s d 】- 0 表示顶点v j 不在集合中，反之， s d 】_ l 表示顶点v j 已在集合中。 p r o c e d u r ed i j k s t r a ( g a ，d i s t , p a t h ，矽? 表示求到图g 中其余顶点的最短路 径，g a 为图g 的邻接矩阵，d i s t 和p a t h 为变量型参数，其中p a t h 的基类型为集 合， 第二章初始延迟测量的方法9 b e g i n f o r j ：= it on d o b e g i n i f j it h e ns f i l ：= o e l s es d j ：= l ： d i s t b l ：= g a f 珀17 i f d i s t j m a x i n t t h e np a t h j ：= l q + j l e l s ep a t h j ：= i t e n d f o rk ：= lt on - 2 d o b e g i n 初始化 m a x i m 为假设的一个足够大的数) w ：= m a x i n t rm ：= i r 而啊可t o 尼d o 求出第k 个终点v m ) ut s d l - o ) a n d ( d i s t j l w ) t h e nb e g i nm ：- - y w ：= d i s t j e n d i f 肌叫t h e ns l m l ：= le l s ee x i t r 若条件成立，则把v m 加入到s 中，否 则退出循环，因为剩余的终点，其最短路径长度均为m a x i n t ，无需再计算下去) 而，户可t on d o 对s t j = o 的更优元素作必要修改 i fl s l l = 0 ) a n d ( d i s t l m l + g a l m , y l m a x _ d ) ； m a x _ d = d ；i r e t u r n ( m a x j + 1 ) ； 2 3 图论对于流水线结构的简单解释 在大规模集成电路的研究和发展中，图论一直是被广泛应用的一个描述逻辑 电路的方法，当然，这里的逻辑电路不能存在“环”。通过检查一个图的集合中 所有的连接点m ，我们可以很容易的确定这个电路的最大延迟，进而发现这个图 的集合所代表的电路的运行方式和过程。与此同时，最小延迟也可以用相同的方 式进行计算和确定。 这里定义一个随机的图( ve ) ，其中v 是一系列的节点，而e 则是节点v 和 v 之间的连线，我们称其为切入点的边。如果( vj ，v 2 ) e e ，那么就可以说v l 和v 2 相连。由节点v l ，v 2 ，v n 所组合而成的点的集合称为一条路径。如果( v i ， 第二章初始延迟测量的方法 v i + 1 ) ee ，就称从节点v l 到v 1 1 有一条路径。 环形图就是一条节点组合为v l ，v 2 ，v n 的路径。需要注意的是对于环形图v l ， v 2 ，v n , v l 来说，( v i i ，v 1 ) e 。如果图g r a p h ( v ，e ) 没有环，那么这样的无环图就 称为d a g ( d i r e c t e da c y c l i cg r a p h ) 。 一个有n 个输入的电路所完成的功能就是从 0 ，1 ) n 到 0 ，1 ) 。如果我们考虑 节点集合f 和一个d a g ( v , e ) ，且在这样的组合中，由v 到f 存在布线g ，那么 我们就可以定义一个逻辑电路。需要注意的是g ( v ) 表示的是输入和输出的关联节 点为v 。 一个d a g ( ve ) 的切入点集合c v 由节点集合e 组成，它满足下列特性：在 图g r a p h ( ve c v ) 中，v 被分割成两个不相连的部分v 1 和v 2 ( v ln v 2 = 咖) ， 且从v 1 到v 2 之间没有任何的路径，相同的，从v 2 到v l 也没有任何相通的路 径。 第三章f p g a 的流水线结构 第三章f p g a 的流水线结构 在f p g a 领域中，初始验证已经得到越来越多设计者的青睐，不仅因为它具 有一般验证方法所不能比拟的便捷性，而且相比其他验证方法，初始验证对于系 统资源的低占有率也是众多硬件设计者开始逐渐重视初始验证的原因。一般说 来，f p g a 是一种建立在一组逻辑单元阵列上的设计方式，这些逻辑单元包括了 一个l u t ( l o o k u pt a b l e 查找表) 和一个寄存器。图4 表示了一个逻辑单元的 基本结构。如图所示，这个l u t 通常包含了四个输入，并且可以执行任何输入 为四的逻辑功能。在某些情况下，一些基于阵列链结构的设计也是可以用这样的 l u t 来执行。l u t 的输出有两种利用方式，通常情况下可以被直接当做输出使 用，另外可以在l u t 的输出上增添一个寄存器，这样就可以利用时钟信号来控 制结果的输出，从而更加方便的达到设计的目标。这里需要注意的是如果l u t 的输出被直接作为组合电路的一个部分来使用，l u t 内所包含的寄存器是被忽略 的，也就是说结果可以跳过寄存器直接进入选择器或者其他的逻辑单元。而这些 没有被使用的寄存器就可以以几乎无溢出的代价来建立流水线结构，从而大大提 高了逻辑单元的使用率。为了验证这种想法是否能够真正付诸于实践，首先我们 需要在一个组合电路中手动建立一个流水线结构。一旦这个包含流水线结构的电 路能够更有效率的完成原先组合电路的功能，我们将研究如何自动生成一个流水 线结构 1 9 】。 图4 f p g a 的逻辑单元 f i g u r e4 al o g i ce l e m e n ti nf p g a 3 1f p q a 上的流水线加法器 作为数字电路系统中最基本、也是最常用的模块之一，加法器如何成功地被 1 4 基于初始验证的自动流水线生成 流水线结构优化自然成了需要解决的首要问题。众所周知，加法器是按二进制加 法运算规则，对两个二进制操作数进行处理的器件，它是计算机算术逻辑部件中 的基本组成部分。此外，它还可以用于数字系统中的多种逻辑电路。按照输入和 输出方式的不同，加法器可以被分为半加器和全加器两种类型，即加数和被加数 为输入，和数与进位为输出的装置为半加器；若加数、被加数与低位的进位数为 输入，而和数与进位为输出则为全加器。需要注意的是半加器有两个二进制的输 入，将其输入的值相加，并输出结果到和s 以及进位c o u t 。半加器虽然能产生 进位值，但它本身并不能处理这个进位。而全加器则有三个二进制的输入，其中 一个就是进位值的输入，所以全加器可以处理进位值，其实从某种意义上来说， 全加器就是由两个半加器组合而成的。 加法器的算法原理是比较简单的。对于一位的二进制加法而言，相关的有五 个的量，即被加数a ，被加数b ，前一位的进位c i n ，此位二数相加的和s 以及 此位二数相加产生的进位c o u t 。前三个量为输入量，后两个量为输出量，五个 量均为1 位。对于稍高位数稍高一些的加法来说，例如三十二位的二进制加法， 一种自然的想法就是将1 位的二进制加法重复3 2 次，也就是我们经常说的逐位 进位加法器。这样做无疑是可行且易行的，但由于每一位的c i n 都是由前一位的 c o u t 提供的，所以第2 位必须在第1 位计算出结果后，才能开始计算；第3 位 必须在第2 位计算出结果后，才能开始计算，等等。而最后的第3 2 位必须在前 3 l 位全部计算出结果后，才能开始计算。这样的方法，使得实现3 2 位的二进制 加法所需的时间是实现1 位的二迸制加法的时间的3 2 倍。可以看出，逐位进位 加法是将3 2 位的加法1 位1 位串行进行的，要缩短进行的时间，就应设法使上 叙进行过程并行化。逐位进位加法器在每一位的计算时，都在等待前一位的进 位。那么不妨预先考虑进位输入的所有可能，对于二迸制加法来说，就是0 与1 两种可能，并提前计算出若干位针对这两种可能性的结果。等到前一位的进位来 到时，可以通过一个双路开关选出输出结果，这就是进位选择加法器的思想。 作为本文所重点讨论的内容，流水线结构的一个最基本的目的就是要将电路 的运算性能进行优化处理，因此就需要从最基本的结构入手来达到这样的效果。 图5 表示的是一个标准的流水线结构的例子。在一个时钟周期为t 的6 4 位全加 器中，通过将操作符，也就是“+ 的运算分割成两部分，就可以把该电路变成 一个流水线结构的全加器。如图所示，加数a 可以用a 6 3 ：0 表示，其中a 6 3 代 第三章f p g a 的流水线结构 表最高比特数，a 0 代表最低比特数，当然加数b 也可以用上述方式来表示。然 后把加数a 和b 的高位部分加在一起，并且将结果放入下一个步骤中，同时我们 也对a 和b 的低位部分进行相同的运算。通过这种分割方法，所需的周期就从t 变成了t 2 ，当然能否标准的达到t 2 还要取决于实际电路的最大路径是否比t 2 要长。这样的方法可以极大地改进时钟频率【2 0 】。 图5 添加了流水线之后的6 4 比特全加器结构 f i g u r e5 6 4 - b i tf u l la d d e rs t r u c t u r ei n s e r t e dw i t hp i p e l i n e 通过下面的算法描述以及图6 的分析，我们就可以明白流水线结构是怎样在 全加器电路中发挥它的作用的。 a l w a y s ( p o s e d g ec l o c k ) b e g i n i n t e r c o m ，i n t e r s u m l = a l + b l + c i n ； i n t e r _ a h = a h ； i n t e r _ b h = b h ； e n d a l w a y s ( p o s e d g ec l o c k ) b e g i n s u m l = i n t e r s u m l ； c o u t ，s u m h 8 ) ； h 8 ) ； e _ a 7 ：o 】； g _ b 7 ：o 】； e n d b e g i n c - e 木g ；d _ f 宰g ； p _ h 木e ；q - ( p ，d ) 8 ) ； q - ( q “1 6 ) ； e n d m = p + q + c + d ； e n d 基于初始验证的自动流水线生成 a s s i g ny = m ； 需要注意的是，上述算法是以硬件