（微电子学与固体电子学专业论文）通用的fpga逻辑映射方法研究.pdf

摘要 现场可编程门阵列( f p g a ) 能够减少电子系统的开发风险和开发成本，缩短 上市时间，降低维护升级成本，故广泛地应用在电子系统中。随着半导体集成电路 规模的不断扩大，f p g a 的发展有二个趋势：一是由单一的通用的可编程逻辑器件 逐渐发展为多种面向不同应用领域的专用逻辑器件：二是作为可编程皿核嵌入到片 上系统( s o c ) 中，成为s o p c 的部分。这种发展趋势使得f p g a 的结构比传统 上有了很大变化，也更加复杂。 f p g a 结构的复杂和多变性，迫【刃需要一套对广泛范围里的不同结构f p g a 都 能够运行的c a d 系统。通过在该c a d 系统上运行特定应用领域的大量网表，模拟 出电路在不同结构f p g a 中实现时的性能参数，从而指导f p g a 结构的选用、改进 和设计，这就是本论文所在的课题项目f p g a c a d 模拟系统。该软件系统对通用度 ( 即所能处理的f p g a 结构的范围) 有非常高的要求。 本论文的工作是在f p g a c a d 模拟系统中负责逻辑映射模块的设计。本文建立 了一种f p g a 逻辑块结构模型f d u l b ，用可量化参数、数学矩阵和有向图分别描 述逻辑块和逻辑单元的输入输出、局部互连开关矩阵和逻辑单元的电路结构。本文 提出了逻辑单元的功能电路的概念以及用功能电路来描述逻辑单元所能实现的逻辑 功能的思想，并给出了从逻辑块结构模型生成逻辑单元的功能电路集的算法 f c g e n 。基于逻辑单元的功能描述( 功能电路集) ，本文提出了适用于f d u l b 模型 的逻辑单元映射算法f d u m a p 。f d u m a p 的输入项是基本元件级的用户电路以及逻 辑单元的多个功能电路。f d u m a p 的核心思想是在用户电路中依次匹配逻辑单元的 每个功能电路，因此归结为两电路匹配问题。将电路抽象成有向图的数学模型后， 采用了子图同构算法实现电路匹配。本文还在结构参数和局部互连开关矩阵的连通 度两方面改进了已有的适用于学术界c l u s t e r 结构模型的装箱算法，得到了适用于 f d u l b 模型的逻辑单元装箱算法f d u p a c k ，算法核心是在考虑各类约束条件下采 用贪婪算法将逻辑单元装箱到层次逻辑块中。 f d u l b 模型，比学术界已有的两种逻辑块结构模型更加通用。f c g e n 算法成 为分析逻辑单元的功能的好方法。经实验表明，适用于f d u l b 模型的f d u m a p 和 f d u p a c k 算法，与适用于原有的逻辑块结构模型的几种逻辑映射算法相比，在性能 上基本相当，但是在通用度上却大大提高。最终，本文完成了f p g a c a d 模拟系统 中的逻辑映射模块的流程和设计要求。 关键词逻辑映射；逻辑块结构模型；工艺映射；装箱；电路匹配；子图同构；现 场可编程门阵列；集成电路计算机辅助设计 中图分类号t n 4 0 2 a b s t r a c t f i e l dp r o g r a m m a b l el o g i ca r r a y , f p g a ，c a nr e d u c et h en r ec o s t ，d e s i g nr i s k t i m e - t o - m a r k e ta n dm a i n t e n a n c ec o s to fe l e c t r o n i cs y s t e m s of p g ai sw i d e l yu s e di n e l e c t r o n i cs y s t e m sw i t ht h es c a l eo fi n t e g r a t e dc i r c u i t sb e i n gl a r g e ra n dl a r g e r , t h e r ea r e t w od e v e l o p m e n tt r e n d sf o rf p g a o n ei st h a tf p g a sh a v eb e e nc o n v e r t e dt 。a p p l i c a t i o n s p e c i f i cl o g i cd e v i c e sf o rm a n yd i f f e r e n ta p p l i c a t i o nd o m a i n sf r o mt h eo r i g i n a lg e n e r i c p r o g r a m m a b l el o g i cd e v i c e s t h e s et r e n d sm a k et h ef p g a a r c h i t e c t u r ec h a n g eg r e a t l ya n d b e c o m em o r es o p h i s t i c a t e d t h ec o m p l e x i t ya n dv a r i e t yo ft h ef p g aa r c h i t e c t u r ed e m a n di m m i n e n t l yac a d s y s t e ma d a p t e d f o raw i d er a n g eo f f p g a sw i t hd i f f e r e n ta r c h i t e c t u r e s b yr u n n i n gal a r g e n u m b e ro fb e n c h m a r k so fs p e c i f i cd o m a i no nt h ec a ds y s t e m ，t h es y s t e mc a l lo u t p u ta p e r f o r m a n c er e p o r t s ot h es y s t e mh a sag o o dd i r e c t i o n0 nt h ec h o i c e ，i m p r o v e m e n ta n d r e d e s i g no ff p g aa r c h i t e c t u r e t h i ss y s t e m ，c a l l e df p g a c a ds i m u l a t i o ns y s t e m ，i sa r e s e a r c ht o p i cr e l a t e dw i t ht h i st h e s i s t h i ss y s t e mh a sah i g hd e m a n do nt h eu n i v e r s a l i t y , w h i c hm e a d st h ea b i l i t yt od e a lw i t hal a r g er a n g eo f d i f f e r e n tf p g aa r c h i t e c t u r e s t h ew o r ko ft h i st h e s i si st h ed e s i g no fl o g i cm a p p i n gm o d u l ei nt h ef p g a c a d s i m u l a i o ns y s t e mp r o j e c ti nt h i st h e s i s ，af p g a l o g i cb l o c ks t r u c t u r em o d e l ，f d u l b ，i s p r o v i d e d q u a n t i f i e dp a r a m e t e r s ，m a t h e m a t i cm a t r i xa n dd i r e c t e dg r a p ha r es e p a r a t e l y u s e dt od e s c r i b et h ei n p u t so u t p u t sn u m b e r , l o c a li n t e r c o n n e c ts w i t c hm a t r i xa n dl o g i cc e i l s t r u c t u r eo fal o g i cb l o c k ac o n c e p to ff u n c t i o nc i r c u i t so fal o g i cc e l l ，t o g e t h e rw i t ha n i d e at h a tu s i n gf u n c t i o nc k c u l t st od e s c r i b et h el o g i cf u n c t i o n sal o g i cc e l lc a r li m p l e m e n t ， i sp r o p o s e d a na l g o r i t h mf c g e ni sp r o v i d e dt og e n e r a t et h es e to ff u n c t i o nc i r c u i t so fa l o g i cc e l lf r o mt h el o g i cb l o c ks t r u c t u r em o d e l b a s e do nt h ef u n c t i o nd e s c r i p t i o no fa l o g i cc e l l ，al o g i cc e l lm a p p i n ga l g o r i t h mf d u m a p ，w h i c hi sa d a p t e dt o t h ef d u l b m o d e l ，i sp r o v i d e d t h ei n p u tt e r mo ff d u m a pi st h eu s e rn e t l i s to fb a s i ce l e m e n tl e v e l a n dm u l t i p l ef i m c t i o nc i r c u i t so f al o g i cc e l l t h ec o r ei d e ao f f d u m a pi st om a t c he v e r y f u n c t i o nc i r c u i to f t h el o g i cc e l lb ys e q u e n c ei nt h eu s e rc i r c u i t ，w h i c hi sr e f e r r e da sat w o c i r c u i t sm a t c h i n gp r o b l e m a f t e rt h ec i r c u i ti sa b s t r a c t e da sad i r e c t e dg r a p h ，c i r c u i t s m a t c h i n gp r o b l e mi ss o l v e db ys u b g r a p hi s o m o r p h i s ma l g o r i t h m f u r t h e r m o r e ，t h i st h e s i s p r o v i d e al o g i cc e l lp a c k i n ga l g o r i t h mf d u p a c k a d a p t e dt of d u l bm o d e lb yi m p r o v i n g t h ee x i s t e n tp a c k i n ga l g o r i t h ma d a p t e dt oc l u s t e rs t r u c t u r em o d e lo fa c a d e m i cf i e l di nt h e f o l l o w i n gt w oa s p e c t s ：s t r u c t u r ep a r a m e t e ra n dc o n n e c t i v i t yo ft h el o c a li n t e r c o n n e c t e d s w i t c hm a t r i x t h ec o r ei d e ao ff d u p c ki st ou s eg r e e d ya l g o r i t h mt op a c kt h el o g i cc e l l s i i t h e o r e t i c s b a s e d o nc h a n g i n go fu n i v e r s a lv i e w ，h e i m b i b e da n d r e b u i l tg u aq it h e o r y a n dn aj i at h e o r ya n dt h e nc r e a t e dy u e t 1n a i at h e o r y a c c o r d i n g t oy u et i n a j i at h e o r y w ec a nd e c l p h e r z h o u y il e c t i o ni n r a t i o n a lw a y y u gt in a i at h e o r yi n f l u e n c e dy uf a n st h e o r y a n dz h o uy i 。a nt o n gq 1 a f f e c t e dt h ep l a n so fz h o u y ii n t r o d u c ei l l u s t r i o u sp o s i t i o ni nz h o u y i t h e o r e t i c s h i s t o r y k e y w o r d s ：z h 。uy ic a nt o n gq i w e ib o y a n g h u nt i a nt h e 。r y “y u 。w 。iy i y u e t in aj i at h e o r y c l cn u m b e r ：b 2 2 1b 2 3 4 1 l i 绪论 1 绪论 1 1f p g a 简介 1 1 1f p g a 的发展 1 9 8 5 年，x i l i n x 公司推出了世界上第一块现场可编程门阵列( f p g a , f i e l d p r o g r a m m a b l eg a t ea r r a y ) 芯片，可以方便地通过下载不同的配置位流文件( b i ts t r e a m ) 而实现不同逻辑功能。由于f p g a 能够减少电子系统的开发风险和开发成本( n r e ) ； 缩短上市时间( t i m et om a r k e t ) ；通过在系统编程、远程在线重构等技术降低维护升 级成本，因此在通信、控制、数据计算等领域得到了广泛的应用。 f p g a 能够很好的利用最为前沿的制造工艺和封装工艺，并通过全定制的电路 和版图设计方法优化设计，因此f p g a 的逻辑密度、性能、功能和功耗都已经得到 大幅改进，成本显著下降。目前，芯片的集成度已达到1 0 0 0 万等效门、速度可达到 4 0 0 - - 5 0 0 m h z 1 1 1 2 ，在制造上采用了9 0 r i m 、9 层铜连线工艺【3 】，并且应用新的封 装技术提供了数千管脚的f p g a 芯片。 随着f p g a 在功能、密度、速度上的不断提升和成本的降低，以及用户需求、 协议标准等的变化越来越快，f p g a 芯片不但被用来制作原型机，而且还破大量地 应用到网络、消费电子、科研、航天及国防的许多最终产品中，成为一系列电子系 统的核心。【4 】中指出，在上市时间、成本、高集成度和灵活度方面f p g a 明显优于 专用集成电路( a s i c ，a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) ，而根据业界通用的标准 判断，最适合使用a s i c 的情况是：门和储存位的数量超过两百万门、千兆位；在 最低功耗下，主时钟频率高于3 0 0 m h z ：对成本很敏感的应用。 另一方面，基于f p g a 的s o p c ( 可编程片上系统) 与传统的s o c 相比，具备 很多优点，如设计周期短、产品上市速度快，设计风险和设计成本低、集成度高， 灵活性大，维护和升级方便，硬件缺陷修复和排除简单等，开始成为设计者的新宠， 并逐渐蚕食传统s o c 的领地【5 】。 1 1 2 f p g a 结构 f p g a 有三大组成部分【6 】：逻辑块o o g i cb l o c k , l b ) ，用来实现用户电路的逻 辑功能；连线资源( i n t e r c o n n e c t i o nr e s o u r c e ) ，用来提供逻辑块间的连接关系；输入 输出块( b l o c k ) ，用来让用户定义输入输出信号。f p g a 的整体结构如图i - i 所 示。 l 绪论 图1 - 1 概念上的f p g a 整体结构 f p g a 的编程工艺有 6 】：静态随机存储器( s t a t i cr a m ，s r a m ) 方式；反熔丝 ( a n t i f u s e ) 方式；可擦可编程只读存储器( e r a s a b l ep r o g r a m m a b l er o m e p r o m ) 方式和电可擦除可编程只读存储器( e e p r o m ) 方式。其中，应用最广泛的是s r a m 编程工艺，如图1 - 2 中所示。如不特别指出，以下讨论的f p g a 都是基于s r a m 编 程工艺的。 绪论 l o g i cc e l ilogiccell 广弋4 h ! 竺竺l l !“。# ；一q。 妒 j ” 蓦 。要。；i i i j 一滞m 1 日掣 !i 烈i 卜 ii。目l广一 i!lj ； i l 一 ： i i ii 擎8 ”4 ”一。 酽 ； b_ 弋+ # 一，一厂。 i j 藩。o l o o j cc e l i 图1 - 2s r a m 编程工艺 f p g a 逻辑块实现布尔逻辑主要有2 种方式：基于查找表( 1 0 0 k - u pt a b l e ，l u t ) 和基于m u x ( m u l u p l e x e r ) 。一个4 输入查找表( 4 - l u t ) 的结构如图1 3 所示。 基于m u x 的逻辑块如图l _ 4 所示。若不特别指出，以下讨论的f p g a 的逻辑块实 现组合逻辑都是基于l u t 方式或者基于m u x 方式的。 4 ：1 图1 - 34 - l u t 的结构 4 1 绪论 a b c a n d y = ( 矗& b l c y 图1 4 基于m u x 的逻辑块 y 1 1 3f p g a c a d f p g a 计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，c a d ) t 勺流程一般包括设计输入、 逻辑综合、功能仿真、划分、映射、布局、布线、时序验证、编程下载等过程，如 图1 5 所示。 1 绪论 图1 - 5f p g a c a d 流程 原理图输入、逻辑综合、功能仿真等部分和一般电子线路设计一样，只是对特 定可编程逻辑器件厂家的特定型号器件，最好使用特定的元件库，如不使用特定元 件库，有些厂家的软件也可以通过e d i f 格式文件和元件库映射来完成第三方软件 到可编程逻辑器件软件的衔接。元件库中有许多功能宏块( 如加法器、乘法器、比 较器、计数器、译码器等) ，应尽量使用这些现成的功能宏块。 功能仿真完成，确信电路正确后，进行逻辑映射。逻辑映射将电路中的元件映 射到f p g a 的逻辑块之中。优化逻辑块数目的映射将尽量减少使用的逻辑块数目； 优化时延特性的映射将尽量减少信号经过的逻辑块的数目。 布局阶段将各l b 和原始输入输出端( i op a d ) 放到适当的位置。一般隋况下， l 绪论 由于可编程逻辑器件布线资源的有限性，布局阶段的优化目标首先是布通率，通道 密度的均匀性。但是实用中还有一些其它问题要考虑，例如用户对某些路径的时延 提出限制，或指定一些线网的重要程度，或要求管脚锁定。这样布局算法就要综合 考虑。自然，各种约束条件和布通率之间是存在矛盾的，怎样兼顾各方面的要求又 能最大程度的提高布通率是一个很值得研究的方向。 布线阶段实现l b 之间的连线。布线要求百分之百的布通率，否则就是布图失 败。因为可编程逻辑器件布线资源的特殊性布线资源都已确定，布线实际上只 是确定哪些编程点接通而哪些不接通。由于可编程逻辑器件布线资源的有限性和多 样性，其布线算法也有特殊性，与普通的布线算法有很大的不同，相应的也有许多 值得研究的问题。 布线完成以后，各路径的时延值才能最后确定。这时，需要进行时序验证，以 检查电路在有时延的情况下工作是否正常。如正常，进入下一步编程下载；如不正 常，需仔细检查各相关点，找出问题所在，用适当的方法解决( 如加入时延约束、 关键线网、调整线网的重要程度、指定某些逻辑单元的位置，或人工干预，拆除某 些线网、移动某些逻辑单元，重新布线) 等。这样的修改可能要反复多次。 时序验证确证无误，即可进行编程下载。通过编程器将编程信息固化在可编程 逻辑器件的某种存储介质上。 对延约束和其它约束( 如管脚位置约束等) 将根据需要，在设计的各实现阶段 产生作用。 1 2f p g a c a d 模拟系统 1 2 1 系统目标 开发一个通用度很强的f p g a c a d 系统，该系统能够针对各种f p g a 结构，对 特定应用领域的大量电路网表进行逻辑映射、布局布线，并统计出编译后的面积、 时间等性能参数。f p g a c a d 模拟系统的目标如图1 _ 6 所示。 i 绪论 图1 6f p g a c a d 模拟系统的目标 1 2 2 系统模块划分 根据f p g a c a d 流程，f p g a c a d 模拟系统分为以下一些模块：网表转换模块、 逻辑映射模块、布局模块、布线模块和性能统计模块，模块划分如图1 7 所示。 1 绪论 图1 - 7f p g a c a d 模拟系统的模块划分 1 3 主要研究工作 作者在f p g a c a d 模拟系统项目中独立负责逻辑映射模块的设计。 逻辑映射模块的功能定义包括：1 ) 在约束条件的限制下，将网表中除预配置宏 单元( 功能宏块) 外的全部逻辑映射到f p g a 的逻辑块中去。2 ) 生成映射后的网 表文件，该文件包括全部逻辑块的配置信息，和逻辑块间的互连信息。映射后的网 表与本模块的输入网表位于不同的描述层次上，但具有相同的逻辑功能。3 ) 产生相 应的结果统计数据。4 ) 可以处理不同结构的逻辑块。 逻辑映射模块的输入包括：1 ) 网表转换模块输出的电路网表。2 ) 逻辑块结构 1 绪论 的描述。3 ) 约束文件。 逻辑映射模块的输出包括：1 ) 逻辑映射结果网表。2 ) 统计报告。 逻辑映射模块的难点，即本文需要解决的问题和工作重点如下： 1 ) 逻辑块的各种结构之间相差很大，需要建立一个通用度大的结构模型，该模 型可以描述各种不同结构的逻辑块。 2 ) 逻辑映射模块中采用的算法要能适用于我们的逻辑块结构模型，模型的通用 度必然要求相应的算法也要对各种结构有同样的通用度。 因此，结构模型的通用性和采用的算法的通用性，是本论文工作的关键，在保 证通用的前提下，追求更好的性能。 1 4 论文组织 第二章介绍学术界在f p g a 逻辑映射问题上相关的技术现状，这是本文工作的 基础；第三章介绍作者提出的f p g a 逻辑块结构模型f d u l b ；第四章介绍作者提 出的逻辑单元功能模型和逻辑单元功能电路的生成算法；第五章详细介绍作者提出 的适用于f d u l b 的逻辑单元映射算法；第六章介绍改进的适用于f d u l b 的逻辑 单元装箱算法；第七章是实验结果；第八章是总结和展望。其中第三到第六章为本 文的工作和创新点。 2 技术背景 2 技术背景 学术界对f p g a 结构和f p g a c a d 的诸多研究课题组中，比较有名的有t o r o n t o u r a v e r s a y 的j o n a t h a nr o s e 【7 1 、u c l a 的j a s o nc o n g 【8 】、w a s h i n g t o nu n i v e r s i t y 的 s c o t th a u c k 【9 】和u b c 的s t e v e nj e w i l t o n 【1 0 。 2 1 相关概念 2 1 1 逻辑块的分类 f p g a 按照其逻辑块内部是否含有连线资源可分为平面f p g a 和层次化f p g a 。 相应地，逻辑块按其内部是否含有互连资源来分，分为平面逻辑块( 也称逻辑单元， 不含内部互连) 和层次逻辑块( 也称逻辑簇，内含多个逻辑单元和局部互连开关矩 阵) 。逻辑块、逻辑单元、逻辑簇这几个比较容易混淆的概念间的关系如图2 1 所 示。 图2 - l 逻辑块的分类 本文所讨论的f p g a 的逻辑块结构，就是指逻辑块中的各种单元和拓扑连接。 2 1 2 逻辑映射的流程 逻辑映射的一般流程如图2 - 2 所示f 5 5 】。逻辑映射可以划分为三个子步骤，分 别介绍如下。 2 技术背景 ( 门级网表 ： 上 e u t 或m u x 映酬 上 ( 基本元件级网表： 上 i 逻辑单元的映射 上 ( 逻辑单元级网表： 图2 - 2 逻辑映射的c a d 沉程 i ) 将用户电路由门级网表转为以l u t ( 或m u x ) 为最小单元的网表，即把基 本门电路网络( n e t w o r k ) 用l u t ( 或m u x ) 来覆盖，称为l u t 映射( m u x 映射) 。 l u t ( 或m u x ) 映射时并不需要知道逻辑块的具体结构，因此它是与f p g a 结构 无关的。u 玎( 或m 【) 映射的输出是基本元件级网表。一个u 映射的例子如 图2 3 所示。 塑爱 的 一娜：墨兀下王麴 单一 鞠 疆舜 一一。一一一 2 技术背景 图2 - 3 一个3 输入l u t 映射的例子 2 ) 将用户电路由基本元件级网表转为以逻辑单元为最小单元的网表，即把电路 中的基本元件全放到逻辑单元中，称为逻辑单元映射。逻辑单元映射时需要知道逻 辑单元的具体结构，因此它是与f p g a 结构相关的。逻辑单元映射的输出是逻辑单 元级网表。一个逻辑单元映射的例子如图2 4 所示。 。m 图2 - 4 个逻辑单元映射的例子 3 ) 如果f p g a 的逻辑块是层次的，则将用户电路由逻辑单元级网表转为以逻 辑块为最小单元的网表，即把电路中的逻辑单元放到层次逻辑块中，称为逻辑单元 装箱。逻辑单元装箱时需要知道层次逻辑块的具体结构，因此它也是与f p g a 结构 相关的。逻辑单元装箱的输出是逻辑簇级网表。如果f p g a 的逻辑块是平面的，则 逻辑单元装箱的这一步骤可以省略。一个逻辑单元装箱的例子如图2 - 5 所示。 b c d 图2 - 5 一个逻辑单元装箱的例子 1 4 2 技术背景 2 2 与f p g a 结构无关的逻辑映射 2 2 1l u t 映射算法 l u t 映射算法跟逻辑块结构无关，学术界历来对l u t 映射问题有深入研究， 按照优化目标的不同，大致分为以下4 类： 1 ) 面积最小化为目标，如c h o r d e - c r f 1 1 】，m i s - p g a 【12 】，x m a p 【1 3 ，v i s m a p 【1 4 ，t e e h m a p 1 5 ，p r a e t o r 【1 6 等。 2 ) 延时最小化为目标，如c h o r d e - d 1 7 ，m i s - p a g - d e l a y 【1 8 ，t e c h m a p - l 1 5 ， d a g - m a p 【1 9 ，f l o w m a p 【2 0 】，e d g e m a p 2 q ，s e q m a p i i 【2 2 等。 3 ) 功耗最小化为目标，女1 1 2 3 ，【2 4 】，p o w e r m a p 2 5 】，p o w e r m i n m a p 【2 6 】，e m a p 【2 刀，d v m a p 【2 8 等。 4 ) 延时和面积同时最小化为目标，如f l o w m a p - r 【2 9 】，c u t m a p 【3 0 1 ，b o o l m a p 【3 1 ，f l o w s y n 【3 2 ，【3 3 ，d a o m a p 3 4 】等。 2 2 2m u x 映射算法 m u x 结构与u 结构不同点在与m u x 结构能够实现的函数不如l u t 结构规 则，不能够依据函数的输入变量的数目判断这个函数是否能用一个i v l u x 结构的逻 辑单元实现，算法的难度比l u t 映射算法大。 m u x 映射算法有a m a p 3 5 1 ，p r o s e r p i n e 3 6 ，m i s - p g a 3 7 。 2 3 基于c l u s t e r 模型的逻辑映射 2 3 1a l t e r a 的逻辑块 a l t e r a 是世界二大f p g a 厂商之一。图2 - 6 是a l t e r a 的f l e x l o k 系列f p g a 的 逻辑块1 ，它是层次逻辑块，内部含有8 个逻辑单元2 和一个局部互连开关矩阵。 a i t e r a f p g a 的逻辑块有个专门的名称叫l a b ，l o g i c a n a y b l o c k 。 2 a l t e r a f p g a 的逻辑单元有个专门的名称叫l e ，l o g m e l e m e n t 。 1 5 瑚i n c a 娃- f 蝌秘 朋伽删 卸m o e d 船t e 1 ) 个输入端和1 个输出端， k 输入查找表可以实现k 变量的任意布尔逻辑。 f f i a t c h 触发器锁存器是逻辑单元中实现时序逻辑的元件，有1 个数据输入端和1 个数 据输出端，此外还有时钟、置位和复位等控制输入端。 m u x 这里的m u x 是指实现布尔逻辑的多路选通器。m u x 是一种重要的逻辑配置方 式，如数据通路等类型的应用，采用m u x 方式可得到较好的速度。m u x 和上面提 到的s m u x 的区别在于，m l r x 的控制端连接的是输入信号，而s m u x 的控制端连 接的是s r a mb i t 。图2 1 5 中就含有一个m u x 。 c o n 仃o f l e r 在逻辑单元内部需要大量的控制，使能，片选信号，故统一定义一个控制信号 生成单元。图2 1 4 中就含有一个c o n t r o l l e r 。 c a r r yc h a i n 专用进位链单元。a l t e r ac y c l o n e 系列，x a l m xx c 4 0 0 0 和v i r t e x 系列的逻辑单 3 逻辑块结构模型 元中都含有快速进位链结构，如图2 - 1 4 中所示。 a d d e r l 1 位全加器单元。有2 个加数输入端，1 个进位输入端，1 个和位输出端，1 个 进位输出端，如图3 - 5 所示。 a d d e r l 图3 - 5 一位全加器 将来扩充的其他功能元件单元，可以扩充定义类型关键字。 3 2 1 2 元件名称n a m e 元件名称就是某类型的元件实例的标识符，相同类型的元件实例的名称是唯一 的。一个元件实例用元件类型+ 元件名称表示，即t y p es u b t y p en a m e 。 3 2 1 3 元件引脚p i n 所有的元件都定义有引脚，引脚的具体参数为： 输入输出，输入引脚( 用【1 表示) 或者输出引脚( 用 表示) 。 类别p m c l a s s ，可以在【 或 中用序数表示。类别定义了相同输入或相同输 出的多个引脚间是否可以相互交换这一关系。相同类别的引脚可以相互交换，彼此 是等价的。值得注意的是，本文将元件引脚类别作为基本元件中的最小单元，而非 实际的引脚。 容量p i n v o l u m e ，某一类别引脚的数量。某引脚类别a 的容量用v o l ( a ) 表示。 元件实例的引脚类别可以用元件类型+ 元件名称+ 引脚输入输出+ 引脚类别的表 达式表示，即t y p e ：s u b t y p e ：n a m e ： p m c l a s s 。例如，类型为a d d e r l 元件实例x 的加 数输入端( 第1 类输入引脚) 表示为f d a d d e r lx 1 】，进位输出端( 第2 类输出引脚) 表示成f d a d d e r l ：y 。v o l ( f o a d d e r l ：x 1 ) = 2 表示加数输入端有2 个，而 v o l ( f da d d e r l ：x t 2 p 1 ，因为元件的输出端一般不会有等价的情况。 3 2 _ 2 基本元件的图表示方法 一个基本元件实例x 可以用有向图( = 0 ，xe x ) 表示，假设x 有m 个不同的输 入引脚类别，n 个不同的输出引脚类别，定义 v ) f x i 】l i = l ，m ) u x 勺 f j 2 l ，n ， e x = x 【i 】，x ，l i = l ，m ；j 2 l ，n ) 。 例如一位全加器实例f d a d d e r l ：a d d 的有向图g 删中，v 。a d = f d ：a d d e r l ：a d d 1 ， f da d d e r l ：a d d 2 ，f da d d e r l a d d ，f d ：a d d e r l ：a d d ，e a a d = t f da d d e r l 。a d d i l ， 3 逻辑块结构榨型 f d a d d e r l ：a d d ) ， ， f d ：a d d e r l ：a d d 2 ， f d a d d e r l ：a d d ) _ ，c f d ：a d d e r l ：a d d 2 ，f d ：a d d e r l a d d ) = 1 x 1 1 x x 2 l 圈3 6 一位加法器的有向图表示 3 2 ，3 逻辑单元的结构模型图 有了基本元件的参数和有向图表示方法后，逻辑单元的电路可以用一个有向图 6 k 表示，以逻辑单元中所有元件实例的引脚类别作为图的顶点，引脚类别间的实 际连接作为图的有向边，即 6 k ，e l c ) ， v t c = uv x ( 工是逻辑单元中的每一个元件实例) ， 既c = 饵pl x 毛j ，e 班c 。 把6 k 作为逻辑单元的结构模型图。 例如，c l u s t e r 模型【3 9 】的逻辑单元b l e ( 参见图2 - 1 0 ) 的结构模型图如图3 - 7 所示。图中，顶点f d ：l u t ：l u t l 1 表示的是札u t 的所有等价的输入引脚， v o l ( f d ：l u t l u t l 1 1 ) = 4 ，表示等价的输入引脚有4 个。逻辑单元结构模型图中，所 有输入引脚类别顶点的入度不能大于该顶点的容量，例如f d ：l u t 1 u t l 1 顶点的入 度要小于等于v o i ( f d ：l u t ：l u t l 1 ) ，这是因为入度表示电路中元件引脚类别中每个 具体引脚的实际使用数量，这当然不能超出该类别引脚的数量。而输出引脚类别顶 点的出度没有限制。 3 逻辑块结构模型 图3 刁b l e 的结构模型图 3 3 三种逻辑块模型的比较 表3 - 1 列出了f d u l b 模型和c l u s t e r 模型【3 9 】、c o m p l e xp l b 模型【4 9 】的一些 比较。 表3 - 1 三种逻辑块模型的比较 c l u s t e r 模 c o m p l e xp l b 模型 f d u l b 模型 珏! l 是否层次化是 否是 内部互连开关 全连通无支持非全连通 矩阵 逻辑单元的逻组合和时 组合逻辑组合和时序逻辑 辑完备性序逻辑 逻辑单元结构结构固定，只有多个l u t 的数种连接 内部的基本元件参数化， 及灵活性无灵活性模式，灵活性小用有向图模型描述内部 电路，灵活性很好 对商用f p g a无仅能描述y a l m x 早期的一些对已知的主流f p g a 的 逻辑块的描述平面f p g a ，如x c 3 0 0 0 ，逻辑块都可以描述 程度x c 4 0 0 0 的c l b 可扩展性无无好 3 逻辑块结构模型 3 ，4 本章小结 本章提出了一种通用的逻辑块结构模型f d i i i _ b 。 f d u l b 的局部互连开关矩阵可以是非全连通的，采用数学的矩阵方式描述， 开关设置可以任意，比c l u s t e r 模型中的局部互连开关矩阵更灵活和通用。f d u l b 中的逻辑单元结构采用数学的有向图描述，比c l u s t e r 模型中的l e 以及c o m p l e x p l b 模型都更通用。 f d u l b 模型达到了2 5 4 节的目标l 的要求，并且具有非常好的扩展性。 4 逻辑单元的功能模型 4 逻辑单元的功能模型 上一章讲述了逻辑块结构模型以及逻辑单元的结构模型图，本章提出了逻辑单 元的功能模型的思想 5 3 】【5 4 ，尝试从逻辑单元所实现的功能角度对逻辑单元建模。 这种想法的出发点是，在进行逻辑映射，特别是逻辑单元映射时，直接关注的是逻 辑单元实现的功能，而不是逻辑单元的结构。本章还重点讲述了是逻辑单元的功能 模型的生成算法。 4 。1 逻辑单元的功能电路 逻辑单元在编程配置( 所有s m u x 的控制端连接的s r a m 中存储了一组二进 制值) 后，功能元件间的实际连接称为逻辑单元在这组编程值下的功能电路( f u n c t i o n e i r e u a t , f c ) 。每一个功能电路就反映了逻辑单元在被编程配置后的实际功能。 4 1 1 功能电路集的描述 逻辑单元在不同配置值下对应的功能电路是不同的。一个逻辑单元的功能元件 间所有可能的连接情况就是它的功能电路的集合，简称功能电路集。逻辑单元对应 的所有功能电路可以用有向图集s f c 描述： 昂f 魄 s = l ，2 ， r ) ， c , ：c ( o - 气v f c ( o ，r f c ( o ) ， ( 沪印u 9 气o ( v f c ( o c ) ， e f c ( i ) = e f c l ( ou e f c 2 ( o ( e f c i ( oc 蚴， 风i 妒 pi x , y e 州j ) ， 扉文沪 川乃，呸p 趾，z 8 m u x ) ； 1 ) 和y f c 唧) ( 0 分别表示逻辑单元的第f 个功能电路中功能元件和原始输入 输出端类型的元件实例引脚类别集合，p 如5 m u x 表示逻辑单元的s m u x 元件实例引 脚类别集合。 功能电路和逻辑单元结构模型的最大区别就是，功能电路中已经没有s m u x 类 型的元件。 4 1 2 功能电路集实例 4 1 2 1b l e 的功能电路集 b l ef 3 9 是一种最简单的逻辑单元( 参见图2 - 1 0 ) ，内部只有一个s m u x ，当 s m u x 的配置信息为0 ，则得到的功能电路就是一个札u t ；当s m u x 配置信息为 1 ，得到的功能电路就是4 - l u t + 触发器。b l e 的两个功能电路如图4 1 所示。 4 逻辑单元的功能模型 i n p u t s 4 - i n p u t l u t 功能电路一 i n p u t s 4 一i n p u t l u t d f f c l o c k 功能电路二 图4 - 1b l e 的2 个功能电路 4 1 2 2x c 4 0 0 0c l b 的功能电路集 图4 - 2 是x c a 0 0 0c l b 结构，图上标出了s m u x 控制端r 1 到r 1 0 ，它们都连 接着s 鼬州编程点。r 1 到r 1 0 取一组值，就能得到一个对应的功能电路。r l 到 r 1 0 共有2 1 0 组值，而对应的2 1 0 个功能电路中存在着重复的情形。例如，当r g = 0 ， r 1 0 = 0 时，r 3