（微电子学与固体电子学专业论文）层次式fpga映射算法.pdf

摘要 摘要 随着现场可编程逻辑门阵列( f p g a ) 在功能、密度、速度上的不断提升和成 本的降低，使得它的应用越来越广泛。同时f p g a 结构也越来越复杂多变，这就 要求其电子设计自动化( e d a ) 系统功能需要扩充、性能需要提高。对e d a 工具 中运用算法的深入研究势在必行。 本文针对其e d a 系统中映射环节的算法进行深入研究，并且实现了此模块。 首先，根据x i l l l 血v i n c x 器件逻辑块结构建立了一种层次式f p g a 逻辑块结构模 型) ( v c l b 。在这种结构模型中分别用可量化参数描述逻辑块，数学矩阵描述局部 互连开关矩阵，有向图描述逻辑单元的输入输出和逻辑单元的电路结构。然后在 已有查找表( u j t ) 映射算法f 1 0 w m a p 、c u 缸l a p 的基础上获得了x v c m a p ，此算法 提高了映射速度，减少了资源占有率。本文还运用了逻辑单元功能电路( x v g 肌 算法可以从逻辑块结构模型生成逻辑单元功能电路集) 的概念来描述逻辑功能， 且得到了适用于x v c l b 模型的逻辑单元映射算法x v m a p 。此算法将电路抽象成 有向图的数学模型后，采用子图同构算法实现电路匹配。此外本文还改进了已有 c 1 u s t e r 结构模型中开关矩阵的模型，获得了适用于x v c l b 模型的逻辑单元装箱 算法x v p a c k 。算法核心是在考虑各类约束条件下采用贪婪算法将逻辑单元装箱到 层次逻辑块中。经实验表明，本文提出的结构模型和算法更适用于商用f p g a 。 关键词：f p g al u t 映射算法 逻辑单元映射算法 逻辑装箱算法 j 址s t r a c t i l i a b s t r a c t w 池t h ec o n t i n u o u su p 舀a d i n gi n 如n c t i o n ，d e l l s i 够，v e l o d t y 趾dc o s tr e d u c t i o n ， t l l ea p p l i c a t i o no ff p g a ( f i e l dp r o 伊锄m a b e1 0 西cg a t ea 玎a y ) w 私m o r ea n dm o r e 嘶d e l y i nt h em e 锄t i m e ，i t s 蛐r u c t u r eh 勰b e c o m ei n c r e a u s i n 酉yc o m p l e x 觚dv 0 1 a t i l e ， w h i c hr e q u i r e sm ee d a ( e 1 e c 昀n i cd e s i 黟a u t o m a t i o n ) s y s t e m 缸l 嘶o nn e e dt o e x p a n d ，p e r f o 彻锄c en e e dt 0b eu p 伊a d e d i ti s 油p c r a t i v et oi n d 印t l ls t u d yt h eu s e o f a l g o r i t h m si i le d a t 0 0 1 s t h e l e s i so fm i sw o r ki si n 廿l ef p g ae d as y s t e m sr e s p o n s i b l ef o rm a p p i n gm e l o 百c a ld e s i g no ft h em o d u l e a c c o r d i n gt 0 l e1 0 西cb l o c k 咖c t i 鹏o fx i i l l i n xv i r t e xd e v i c e ，a1 1 i e r a r c h i c a l s 仇l c t u r em o d e lo ff p g al o 百cb l o c kw h i c hn 锄ei sx v c l bw 笛e s t a b l i s h e di n t h i s p a p 既t h e 曲伽i ts t r l l c t i l r eo fi n p u t 锄d0 u t p 鸭l o c a li n t 黝e c ts 硒t c hm 撕x 锄d l o 百cu i l i tw e r cd 鼯c r i b e dr e s p e c t i v e l y 硒q u a n t i f i a ：b l ep 踟懈，m 础锄a t i c a lm 枷x 趾d d i 黟a p h i nt h i sp a p an e wl u t ( l 0 0 k u p - t a b l e ) m a p p i n ga l g o r i t h i l l 一x v c i i l 印w a s 0 b t 咖e db a s e do nf l o 、m 叩趾d 咖n 印，i t sm 印p i n gs p e c dw 硒i m p r 0 v e d 锄dn l es h a r e o fr c s o u r c e sw a sr e d u c e d b 觞e do nt h ec o n c 印tt 0u s el o 舀c a ll m i tf h n c t i o nc i r c u i tt 0 d e s c r i b e 也ei d e ao fl o 百c 缸n c t i o n ，t l l el o 百c 出u n i tm 印p i n ga l g o r i t h ，x m 印，w 雒 o b 缸e d ，w h i c hu s e di l lx v c l b m o d e l a f t e ra b s 仃a c tc i - c u i ti n t 0d i g r a p hm a t h e m a t i c a l m o d e l ，m er e a l i z a t i o no fc i r c u i t sm a t c hw 嬲u s e d i i ls u b g r a p hi s o m o 咄i s ma l g o r i m m 1 1 1 a d d i t i o n ，t h es w i t c hm 枷xm o d e li nc l u s t e rs t n l c t u r em o d e lw a si n l p r 0 v e di nt h i sp a p e r ， 锄d 也el o 西c a lu n i tp a c l 【i n ga l g o r i t h mx v p a c kw 豁a c h i v 酣w h i c hw a s 印p l i e dt 0 x v c l bm o d c l i nc 0 n s i d 耐n gv 撕o u st ) r p e so fc o n s t r a i n t s ，t h ec o r eo fa l g o r i t h mi st 0 p a c k e dl o 西c a lu n i tt 0n l el e v e lo f1 0 百cb l o c kw h i c ha d o p t e d 伊e e d ya l g o r i t l l i n t h ee x p 醯n e n t si 1 1 d i c a t em a tm i sp 印e rp r e s e n t st l l es 仃i l c t u r em o d e la i l dm e a l g 嘶也mi sm o r ea p p l i c a b l et oac o 础咀e r d a lf p g a k e y w o r d ：f p g al u t m a p p i n ga l g o r i t h m sl o g i c c e um a p p i n g8 l g o r i t h m s f p g ap a c l 血ga l g o r i t h m 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 型阻日期上蚪 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在 年解密后适用本授权书。 本人签名： 麴l 墨丝 名：毒萝溉 ，- 。0 乞- t t ：， ，珥审。 ，o i ；1 ， l r j ：1l 导师签名：羔! ! ：望 日期幽 日期堡! ：! ：三罕 第一章绪论 1 1 1f p g a 发展状况 第一章绪论 1 1f p g a 简介 现场可编程逻辑门阵列( f p g a ，f i e l dp r o g r a m m a b l eg a t ea r r a y ) 芯片是x i l i l l ) 【 ( 赛灵思) 公司在1 9 8 5 年首先推出的，它是一种新型的高密度p l d ，采用 c m o ss 洲工艺制作。f p g a 可以方便地通过下载不同的配置位流文件( b i t s 仃e 锄) 而实现不同逻辑功能。 f p g a 能够很好的利用最前沿的制造工艺和封装工艺，并通过全定制的电路和 版图设计方法优化设计，因此f p g a 的逻辑密度、性能、功能和功耗都已经得到 大幅改进，成本显著下降。2 0 0 1 年之后，f p g a 产品加快了从一个工艺节点向更 先进工艺节点迈进的步伐，从1 5 0 姗、1 3 0 n m 跃进到9 0 i 皿。之后在2 0 0 6 年，6 5 i l i n 工艺又在第一时间被引入。时至今日，两大主流f p g a 企业的6 5 衄已经获得了大 量应用。其中，x i l i l l ) 【公司的6 5 n m 产品集中在其高端系列v i n c ) 【5 上，并己发展 到了4 个系列1 5 个平台；而a l t e r a 公司的6 5 n m 产品涵盖中低端c v c l o n e 系列和 高端产s 删x 系列。采用6 5 i 皿工艺技术，使f p g a 产品的性能再次获得了飞跃， 成本和功耗也大幅降低。例如，x i l m 公司6 5 衄工艺的f p g a 与9 0 m n 产品相比， 速度平均提高了3 0 ，容量增加了6 5 ，与此同时，动态功耗降低了3 5 ，静态 功耗保持相同的低水平，而芯片使用面积减少了4 5 。a l t e f a 采用6 5 1 1 n l 工艺的 c y c l o n e i i i 系列比前一代产品每逻辑单元成本降低2 0 ，含有2 8 8 个数字信号处理 乘法器，存储器达到4 ，它使设计人员能够更多地在成本敏感的应用中使用 f p g a 。工艺技术推动的创新还在不断延续。今年5 月，a l t e r a 向业界发布了全球 首款采用4 0 n m 工艺的f p g a ，即s 仃a t i x f p g a 系列和h a r d c o p y f p g a 系列， 将于2 0 0 9 年第三季度开始接受客户投片。f p g a 产品已经进入4 5 l 蚰时代，而3 2 l 瑚 产品的研发也在紧锣密鼓地进行着【l 】。 随着f p g a 在功能、密度、速度上的不断提升和成本的降低，以及用户需求、 协议标准等的变化越来越快，f p g a 芯片不但被用来制作原型机，而且还被大量地 应用到无线通信、工业、科学及测量、医疗设备、音视频广播、汽车、计算、存 储应用和快速发展的消费品市场中，成为一系列电子系统的核心。由于在上市时 间、成本、高集成度和灵活性等多方面f p g a 明显优于专用集成电路( a s i c ， 2 层次式f p g a 映射算法 印p l i c a t i o ns p e c i f i ci n t e 伊a t e dc i r c u i t ) 。对a s i c 厂商而言，6 5 衄工艺带来的性能提 升和成本降低是可以预见的，但在同样的管芯面积上集成更多的逻辑单元，芯片 设计的复杂度大幅提升，这将导致a s i c 在设计环节的出错率提升。而开发a s i c 膜板费用居高不下也使得a s i c 的应用开始“紧缩”。随着工艺不断提升，f p g a 将 加快取代传统的a s i c 这一趋势【2 1 。 1 1 2f p g a 基本结构 f p g a 一般由三种可编程电路和一个用于存放可编程数据的存储器组成，这三 种可编程电路是：可编程逻辑块( c l b ，c o n f i g i l r a b l el o 百cb 1 0 c k ) 、输入输出模 块( i o b ，i ob l o c k ) 和丰富的互连资源( 瓜，1 1 1 t 黝l l n e c tr e s o u r c e ) 。f p g a 整 体结构如图1 1 所示： 图1 1f p g a 整体结构图 c l b 是f p g a 的主要组成部分，用来实现逻辑功能的基本单元。i o b 提供了 器件引脚和内部逻辑阵列之间的连接，通常排列在芯片四周。可编程互联资源瓜 包括了各种长度的金属连线线段和一些可编程连接开关( s m ，s w i t c hm a t r i x ) ， 它们将c l b 与c l b ，c l b 与1 0 b 相互连接起来。除基本组成部分，还包括有嵌 入式块洲，底层嵌入功能单元( 如p l l 、d l l 和d s p 等) 内嵌专用硬核等。 f p g a 的编程工型3 】主要有：静态随机存储器方式( s 黜蝴，s 删c 删) ； 翻熔丝方式( a i l t i 一如s e ) ，可擦可编程只读存储器( e p r o m ) 方式和电可擦除可编程只 读存储器( e e p r r o m ) 方式。其中最为广泛的就是基于s r a m 的编程工艺。 第一章绪论 1 2f p g ae d a 软件简介 伴随着集成电路技术的发展，e d a 逐渐成为重要的设计手段，已经广泛应用 于模拟与数子电路系统等许多领域。e d a 技术的发展始于7 0 年代，至今经历了 c a d ( 计算机辅助设计) 、c a e ( 计算机辅助工程) 和e d a 三个阶段。e d a 技术是以 计算机为工具，代替人完成数字系统的逻辑综合、布局布线和设计仿真等工作， 设计人员只需完成系统的功能描述，就可以由计算机软件进行处理，得到设计结 果，而且修改设计只需对其设计描述进行修改，可以极大的提高设计效率。 f p g a 设计流程分为功能定义、设计输入、功能仿真、逻辑综合、综合后仿真、 布局布线、布局布线后仿真、下载验证等8 个步骤【4 】，其流程图如下： 图1 2 f p g a 设计流程图 功能定义：在f p g a 设计项目开始实施之前，要对系统功能进行定义和模块 划分。 设计输入：包括实用硬件描述语言( h d l ，包括v h d l 和v 嘶l o gh d l 两种) 和原理图输入两种方式。 功能仿真：仅对逻辑功能进行测试模拟，以了解其实现功能是否满足设计要 求，仿真过程没有加入时序信息，不涉及具体器件的硬件特性( 如延时) 。 4 层次式f p g a 映射算法 逻辑综合：针对给定电路实现功能和实现此电路的约束条件( 速度、功耗、 成本、电路类型等) ，通过计算机进行优化处理，获得一个满足上述要求的电路 设计方案。综合的结果是一个硬件电路的实现方案( 最优或者最接近) 。 综合后仿真：其目的是检查综合结果是否与原设计思路一致，仿真时，仿真 工具会把综合生成的时延文件反标到仿真模型文件中。仿真完成，确信电路正确 后，进行逻辑映射。 逻辑映射将电路中的元件映射到f p g a 的逻辑块之中。优化逻辑块数目的映 射将尽量减少使用的逻辑块数目；优化时延特性的映射将尽量减少信号经过的逻 辑块的数目。 布局阶段将各逻辑单元和原始输入输出端放到适当的位置。 布线阶段实现逻辑单元之间的连线。 布局布线后仿真：在布局布线后，提取有关的器件延迟、连线延时等时序参 数，生成延时文件，并在此基础上把延时文件反标到仿真模型中去。时序验证正 确无误，即可进行编程下载。 下载验证：下载是在功能仿真与时序仿真正确的前提下，将综合后形成的位 流下载到具体的f p g a 芯片中，也叫做芯片配置。 1 3 本文主要研究工作 本文主要研究f p g a 厂家工具中映射工具的设计。 图1 3f p g a 映射工具框图 映射工具的功能定义包括： 1 在约束条件的限制下，将网表中除预配置宏单元( 功能宏块) 外的全部逻辑映 射到f p g a 的逻辑块中去。 2 生成映射后的网表文件，该文件包括全部逻辑块的配置信息，和逻辑块间的 互连信息。映射后的网表与本模块的输入网表位于不同的描述层次上，但具有相 同的逻辑功能。 第一章绪论 3 产生相应的结果统计数据。 4 可以处理v i r t e x 系列f p g a 结构的工艺映射，从门级网表的l u t 映射到逻 辑单元映射一直到最后生成逻辑簇级网表的逻辑单元装箱。 逻辑映射模块的输入包括： 1 综合后输出的门级电路网表。 2 约束文件。 逻辑映射模块的输出包括： 1 逻辑映射结果网表。 2 统计报告。 逻辑映射模块的难点，即本文需要解决的问题和工作重点如下： 1 v e n i x 器件逻辑块的结构与之前学术模型相差很大，需要根据x i l i i u 【公司的 v i n c x 系列f p g a 的c l b 结构建立一个结构模型，该模型可以准确地描述该器件 的逻辑块。 2 逻辑映射模块中采用的算法要能适用于根据v i r t c x 系列f p g a 的c l b 结构 建立的逻辑块结构模型，模型的复杂度大于之前已有的模型必然要求相应算法的 时间复杂度要优于之前所使用的。因此结构模型的实用性和采用的算法的适用性， 是本论文工作的关键，在保证可以实现映射的前提下，追求更好的性能。 1 4 论文组织 本论文的章节安排如下所示： 第二章研究分析了f p g a 逻辑映射问题的技术现状，这是本文工作基础。 第三章研究x i l i l l ) 【v i r t 既器件c l b 结构和根据该结构建立了层次式f p g a 逻 辑块模型。 第四章研究分析了与f p g a 结构无关的u j t 映射算法，并且提出改进的l u t 算法x v c m 印。 第五章实现了适用于根据v n e x 器件c l b 结构建立的逻辑单元模型的逻辑单 元映射算法x n 印。 第六章在已有f p g a 装箱算法的基础上获得了适用于v i r t e x 器件的逻辑单元 装箱算法x ，a c k 。 第七章是实验结果。 第八章是总结和展望。 其中第三到第六章为本文的工作和创新点。 第二章基本映射模型分析 7 第二章基本映射模型分析 从f p g a 芯片问世以来，针对它的e d a 软件研究就开始了，比较有名的课题 组有多伦多大学的j o n a t l l 觚r o s e 、u c l a 的j 邪o nc o n g 、华盛顿大学的s c o o t th a u c k 和u b c 的s t c v 髓j e w i l t o n 。本章所做的工作就是详细分析了逻辑映射问题相关 的技术现状。 2 1映射流程 这一节主要详细研究映射的一般流程，在介绍映射流程之前首先介绍了逻辑 块的概念和分类。 2 1 1 逻辑块 f p g a 逻辑块实现布尔逻辑主要有两种方式：分别为基于查找表( 1 0 0 k - u p t a b l e ，l u t ) 和基于( m u l t i p l e x e r ) 的算法。本文要介绍的算法是应用于l u t 的算法。一个四输入查找表的结构如下图所示。基于d ( 的逻辑块结构如图2 1 所示。 f 图2 1 四输入查找表结构图 f 层次式f p g a 映射算法 m 1 图2 2 基于m u x 逻辑结构 f p g a 按照其逻辑块内是否含有连线资源可以分为平面f p g a 和层次f p g a 。 逻辑块内部不含有互连资源，称为平面逻辑块( 也称逻辑单元) 。层次逻辑块( 也称 逻辑簇，内含多个逻辑单元和局部互连开关矩阵) 。逻辑块、逻辑单元、逻辑簇这 几个比较容易混淆的概念间的关系如图所示： 2 1 2 映射流程 图2 3 逻辑块分类示意图 工艺映射将网表中逻辑门映射成物理元素，即把逻辑设计分割到构成可编程 逻辑阵列内的可配置逻辑块与输入输出块及其它资源中的过程。工艺映射的一般 e a d 流程如图2 4 所示，逻辑映射分为三个步骤，分别介绍如下。 基本元件级映射 将用户电路由门级网表转为以l u t ( 或胍) 为最小单元的网表，即把基本 门电路网表用u 丌( 或) 来覆盖，称为l l r r 映射( 或肌映射) 。l u t 0 久 o 江 b o 1 肿舭 队 即m 阻 吼 第二章基本映射模型分析 9 ( 或姗( ) 映射时并不需要知道逻辑块的具体结构，因此它是与f p g a 结构无关 的。u j t ( 或) 映射的输出是基本元件级网表。l u t 映射和m u x 映射都与 f p g a 结构无关的逻辑映射。其中学术界历来对l i j t 映射问题有深入研究，按照 优化目标的不同，大致分为以下4 类： 1 面积最小化为目标，如c h o m e c r f 【5 1 ，m i s - p g a 【6 1 ，x m a p 【7 1 ，v i s m a p 【8 1 ， t e c h m a p f 9 】，p r a e t o l l l 0 1 等。 2 延时最小化为目标，如c h o r t l e d f l l l ，m i s - p a g d e l 1 2 1 ，t e c h m a p l 【9 1 ， d a g m a p 【1 3 1 ，p r a e t o r 【1 4 1 等。 3 功耗最小化为目标，如p o w e r m a p 【1 5 】，p o w e r m i i 州印【1 6 】，e m a p 【1 7 1 ，d v m a p 【1 8 】 等。 4 延时和面积同时最小为目标，f l o w m 印r 【19 1 ，c u t m 印【2 0 】，b 0 0 l m 印【2 l 】， f l o w s y n 【2 2 1 ，d o a m 印【2 3 】等。 m 结构与u j t 结构不同点在于) ( 结构能够实现的函数不如l u ，r 结构 规则，不能够依据函数的输入变量的数目判断这个函数是否能用一个md ( 结构的 逻辑单元实现，算法的难度比u j t 映射算法大。映射算法有a m a p 【2 4 1 ， p r o s e 巾i n e 【2 5 1 ，m i s - p g a 2 6 】等。 r 百丽n 。 门级网表 j ) 叵垂圃 t ( 基本元件级网表) 、 - _ _ - _ _ - _ _ _ _ - _ _ _ _ - - - _ - - - - _ - 。_ 。- _ _ 一 历面藐磊溺 磁盔盔叫- _ _ 山_ 血五_ 。止_ 出捌 彳日卵r r l r + 万，7 劢 匿怒辑单元级网表笏 、毪驰。- _ 。- 。l 。_ 。_ 五彩 医曩因 逻辑单元级映射 图2 4 映射流程图 在于结构无关的优化映射算法产生一个l u t 网表以后，接着要进行的就是把 这个l u t 网表映射到具体的f p g a 结构中。其中要考虑的两个主要约束条件还是 打包所用可编成逻辑单元数目的最小化和在一个逻辑单元中有效的用多级l u t 互 1 0 层次式f p g a 映射算法 连所得到的逻辑单元级网表时延的最小化。将用户电路由基本元件级网表转为以 逻辑单元为最小单元的网表，即把电路中的基本元件全放到逻辑单元中，称为逻 辑单元映射，如图2 5 所示。逻辑单元映射时需要知道逻辑单元的具体结构，因此 它是与f p g a 结构相关的。逻辑单元映射的输出是逻辑单元级网表。 a b c d e c i 逻辑单元装箱 图2 5 逻辑单元级映射示意图 如果f p g a 的逻辑块是层次的( 层次结构的逻辑块中包含了逻辑单元和局部 互连开关矩阵，而平面结构的逻辑块只包含有逻辑单元) ，则将用户电路由逻辑 单元级网表转为以逻辑块为最小单元的网表，即把电路中的逻辑单元放到层次逻 辑块中，称为逻辑单元装箱。也就是把由映射和划分后得到的电路网表中的器件， 比如l u t 、d 触发器等；用逻辑模块来实现，并根据需要保证网表中的洲以 及宏模块信息不变，装箱时也要考虑时延。逻辑单元装箱时需要知道层次逻辑块 的具体结构，因此它也是与f p g a 结构相关的。逻辑单元装箱的输出是逻辑簇级 网表。如果f p g a 的逻辑块是平面的，则逻辑单元装箱的这一步骤可以省略。 图2 6 逻辑单元装箱示意图 b c d 日 第二章基本映射模型分析 2 2 基本映射模型 这一节研究了两种基本映射模型c l u 贻模型 2 7 和c o n l p l e xp l b 模型 2 8 以 及它们所运用的映射系统和算法，并且详细分析了它们各自的优缺点。 2 2 1c 1 u s t 盯模型 a l t e r a 的逻辑块 a 1 t e r a 是世界二大f p g a 厂商之一。舢t e r a 的f l e x l o k 系列f p g a 的逻辑块 是层次逻辑块，内部含有8 个逻辑单元和一个局部互连开关矩阵，a 1 t e r af p g a 的 逻辑块有个专门的名称叫l a b ( l 0 百c 恕t a yb l o c k ) ，a l t e r af p g a 的逻辑单元有 个专门的名称叫l e ( l 0 西ce l 锄t ) 。l a b 中的一个逻辑单元，含有l u t 、d 触 发器，进位链、级联链等基本元件。 根据a l t e mf p g a 的l a b 和l e 的结构，t o r o n t 0 的r o s e 等人提出了一个逻 辑块结构模型，逻辑块是层次的，称为c l l l s t e r ，c l u s t e r 中有n 个逻辑单元，称为 b l e 他商c1 0 西ce l 锄e n t ) ，每个b l e 有k 个输入端，1 个输出端。c l u s t e r 中的内部 互连是每个b l e 的唯一输出端都可以输出到c l u s t 盯外部或者是进行反馈，同 c l u s l c r 的1 个输入端一起经过一个( 1 + 忉圳的全连通的局部互连开关矩阵 ( l o c a li i l t e r c 0 衄e c tm a t r i x ) 选通到n 个b l e 的任一输入端。通过实验方法得出 结论，当i = 2 n + 2 时可以提供逻辑簇足够的输入信号；特别地，当n = 4 ，i - 1 0 时， 逻辑簇的结构是面积上最有效的。每个b l e 内部含有一个k 输入l u t 仪l u t ) 和 一个d 触发器( df l i p 1 f l o p ，d f f ) ，经过开关多路选通器( s c i t c h d ( ，s m 【) ，可 以实现组合或时序逻辑输出。 t o r o n t 0 大学的f p g ac a d 流程 适用于c l u s t c r 模型的逻辑映射算法，对于t o r o n t oc 1 u s t e r 模型来说，逻辑单 元映射就是指b l e 的映射，即把一个触发器和一个l u t 尽可能地配对放入一个 b l e 中；逻辑单元装箱就是b l e 的装箱，即把这些b l e 在约束条件下组合放到 c l u s t c r 中。由于b l e 结构非常简单，b l e 的映射相对b l e 的装箱来说处理也是 非常简单，因此现有的基于t o r o r l t 0c l u s t c r 的逻辑映射算法都是把b l e 映射和b l e 装箱合在一起，统称为c l u s t c r 装箱算法。 c l u s t c r 装箱算法有，a c k ，t 、伊a c k ，i 冲a c k ，i r a c 等等，v p a c k 算法将含有 u j t 和触发器的网表转换为含有c l b 的网表并输出，v p a c k 的目标有两个，尽量 填充c l b 以最小化c l b 数目；最小化c l b 输入数以最小化c l b 之间的线网连接。 1 2 层次式f p g a 映射算法 t p a c k 是对v p a c k 的改进，将时延和面积同时考虑，因此效果较好：i 冲a c k 是基 于布通率的c l u s t e r 装箱算法，将影响电路布通率的几种因素同时考虑到目标函数 中，其布通率相对于v p a c k 有很大改进，但是结果要比t p a c k 差。i r a c 采用通 过控制装箱到每个c l u s t c r 中的l u t 数目来改善电路的布通率，相对于前面的几种 算法在布通率方面有很大的改进，面积也比较小。 t o r o n t 0 大学的f p g ac a d 流程如下： 1 对用户电路进行逻辑优化，使用的工具是s i s p 1 2 l u t 映射，使用的算法是f l o w m a p i 憎j 。 3 将电路中的u j t 和d f f 装箱到c l u s t e r 中，使用的算法是t - v p a c k 。 4 对由c l u s t e r 组成的电路进行布局和布线，使用的工具是v p r 【3 1 】。 其中第2 、3 两步的工作就是逻辑映射。其中t o r o r l t o 大学的f p g ac a d 流程 副3 2 】如图2 7 所示。 c a 口r t 图2 7 r o r o n t o 的f p g ac a d 流程 第二章基本映射模型分析 2 2 2 c o m p l c xp l b 模型 x i l i n x 的逻辑块 x i l i i 是世界两大f p g a 供应商之一。x c 4 0 0 0 系列f p g a 是x i l i n x 早期的一 个经典产品，它的逻辑块是平面的，x c 4 0 0 0 的c l b 里有2 个4 输入l u t ，1 个3 输入l u t ，2 个d 触发器和多个开关，此外还有进位链结构。 基于x i l i i l xf p g a 的平面c l b 和s l i c e 的结构，u c l a 的c o n g 等人提出了一 种基于u 丌的逻辑单元结构模型称为c o m p l e xp l b 伊锄m a b l el o 百cb l o c k ) ，可 以描述逻辑单元中的不同数量、大小的l u t 以及l i j t 间的不同连接方式。 适用于c o m p l e ) 【p l b 模型的逻辑映射算法 c o m p l e xp l b 是平面的，因此基于c o m p l e xp l b 模型的逻辑映射就是逻辑单 元映射，即c o m p l e xp l b 的映射。r a s p 中的启发式算法是基于c o m p l e xp l b 的 逻辑单元映射算法，可以将一个u 仃级的网表映射到多种不同类型的p l b 中。算 法步骤如下： 构造“兼容图( c o m p 袖i l 时g a p h ) 。兼容图的顶点代表着将会被合并的不 饱和p l b ( 初始时就是所有l u t ) 。如果两个u j t 能够放进一个p l b ，兼容图中 的两个顶点间就存在对应的一条边。如果两个l i j t 没法被放进一个p l b ，例如它 们违反了一些限制规则，像p l b 的输入线。 给兼容图的边加上不同的权重。权重表示将两个u j t 映射到同一p l b 中的迫 切度，它是一个目标函数。根据不同的优先考虑，例如最小化延时、最小化面积 或者最大化可布性等等，可以计算出兼容图中每条边的权重。 装箱在兼容图上用匹配算法，每次选择权重最大的边所代表的一对不饱和 p l b 进行合并，直到无法再合并为止。这个算法的复杂度是d ( 玎肌) ，其中n 是l u t 的数目，m 是某一个l u t 在兼容图中与其他不饱和p l b 的边的个数。 除此以外c o m p l e ) 【p l b 映射的算法还有：p d d m a p 和p d d s y n ，分别采用的 是部分变量相关的布尔函数的分解方法和布尔匹配方法。 u c l a 的f p g ac a d 流程 u c l a 的c o n g 等人开发了一个通用的f p g a 综合和映射系统r a s p ，可以处 理与f p g a 结构无关的u j l r 映射和基于c o m p l e xp l b 结构模型的逻辑映射。 r a s p 的软件系统框架，它是基于c o m p l e xp l b 结构的f p g a c a d 流程，大 致步骤如下： 1 输入网表格式转换，将电原理图方式或h d l 方式的电路网表进行分割，分 为结构化的逻辑( 类似用户定义的宏单元) 和随机逻辑两部分网表。前者保持) 【n f 格 1 4 层次式f p g a 映射算法 式不变，送至6 ；后者转成b l i f 格式送至2 ； 2 时序逻辑优化，采用s i s p 。 3 组合逻辑的提取。将随机逻辑b l i f 格式网表中的组合和时序逻辑部分分开， 并产生输出端口约束信息。其中时序逻辑部分直接送至6 。 4 l u t 映射，使用f l o w m 印r 将组合逻辑用l u t 实现。 5 p l b 映射，将u j t 级网表在考虑输出端约束信息条件下变成p l b 级的网表 6 输出网表格式转换，将) 【n f 格式结构化逻辑、b l i f 格式随机逻辑的时序部分 以及随机逻辑的组合部分p l b 级的网表三部分合在一起，得到逻辑映射完成后 的x n f 格式电路网表。 2 2 3 两种模型对比 图2 8u c l a 的f p g ac a d 流程 1 c l u s t e r 模型的优点： 1 ) c l u s t e r 模型的逻辑块是层次逻辑块，符合现今f p g a 的结构由平面逻辑块 第二章基本映射模型分析 向层次逻辑块发展的趋势和主流情况。 2 ) c l u s t e r 模型的逻辑单元( 即b l e ) 含基本的组合元件l u t 和时序元件d 触发 器，可以实现完备的电路逻辑。 3 ) 基于c l u s t e r 模型的c l u s t c r 装箱算法支持逻辑簇的输入端数目和逻辑簇中的 b l e 数目变化参数。 2 c 1 u s t e r 模型的缺点： 1 ) 逻辑单元b l e 采用了实现组合和时序逻辑的最简单的结构，不含有任何 专用的基本元件，属于细粒度逻辑单元，这样对f p g a 的实际应用领域并不优化， 与商用f p g a 的粗粒度逻辑单元的结构差别很大。 2 ) 逻辑簇的内部互连开关矩阵是全连通的，虽然适用于大部分商用f p g a ，但 是仍有一部分商用f p g a 的内部互连开关矩阵是非全连通的。 3 ) c l u s t e r 模型的逻辑簇是层次逻辑块的一种最简单的结构模型，基于c l u s t e r 模型的逻辑映射流程和算法有着结构模型相同的局限性。 3 c o m p l e xp l b 模型的优点： c o m p l e x p l b 内支持多个l u t 的不同连接方式，复杂度要大于b l e 。 基于c o m p l e x p l b 的f p g a c a d 流程里，加入了对结构化逻辑( 宏单元) 的处理。 4 c o m p l e ) 【p l b 模型的缺点： 1 ) c o m p l e xp l b 只是一个逻辑单元结构模型，或者称为平面逻辑块模型，无 法描述层次逻辑块。 2 ) 模型中只有l u t ，没有d 触发器，逻辑功能上不完备，这与实际的逻辑单 元差别很大。 3 ) 模型的参数化和描述方法比较简单，所能描述的逻辑单元结构范围狭窄。 基于c o m p l e xp l b 的逻辑单元映射算法是一些启发式算法，受结构模型制约，通 用性很差目前只提供了处理x c 3 0 0 0 和x c 4 0 0 0 逻辑单元结构的两种启发式算法。 2 3商用f p g a 从f p g a 结构角度来说，商用f p g a 的逻辑块结构复杂度要大于学术模型。 具体表现在：1 ) 商用f p g a 的逻辑单元内部往往包含多个l u t 和多个d 触发器， 以及一些特殊用途的基本元件，输入端、输出端和开关的数目也较多。2 ) 商用f p g a 的层次逻辑块，内部互连开关矩阵大部分是全连通的，也有一部分不是全连通的。 针对学术界c l 跚t e r 模型和c o m p l e ) 【p l b 模型的不足，结合商用f p g a 逻辑块 的特点，f p g ac a d 模拟系统逻辑映射模块的目标是： 对x i n l i i l 】【公司的v r i t e x 系列器件f p g a 逻辑块结构建立一个数学模型，可以 1 6 层次式f p g a 映射算法 准确的描述这款f p g a 芯片的逻辑块结构；逻辑映射模块中的逻辑单元映射和装 箱算法要适用于上述的模型，也就说对上述的模型描述下的各种逻辑块结构做到 算法上的适用。 2 4小结 本章介绍了f p g a 逻辑块结构模型以及工艺映射流程。着重介绍了已有的 f p g a 逻辑块结构模型和映射算法及流程。归纳总结了它们的特点和不足之处，并 提出了本文工作适用于t e x 器件的c l b 结构的映射算法。 第三章v i n c xc l b 结构模型研究 1 7 第三章 v i r t e xc l b 结构模型研究 x i l i m 【公司的v i r t e x 系列器件【2 9 】是市面上较流行的f p g a 芯片，本章就是对 此器件c l b 的结构进行详细研究分析，并对其逻辑块结构和开关矩阵建立数学模 型。 3 1 1 可编程逻辑模块 3 1v i r t e x 逻辑块结构 可配置逻辑模块( c l b ) 是f p g a 的主要组成部分，是f p g a 实现逻辑功能 的基本单元。c l b 的基本构建模块是逻辑单元l c ( b 百cc e l l ) ，一个l c 包括1 个四输入的函数发生器、1 个进位逻辑和1 个存储单元，每2 个l c 组成1 个切片 ( s l i c e ) ，每个c l b 包括4 个l c ，即由2 个s l i c e 组成。 图3 1v i n e x f p g a c l b 结构图 除了4 个基本的l c 外，c l b 中还包括一些逻辑电路，与函数发生器一起实 现任意去5 输入或6 输入的逻辑函数。因此，当计算一个v i r t e x 器件的系统门数 量时，可认为每个c l b 包括4 5 个逻辑单元l c 。 层次式f p g a 映射算法 c t r u 图3 2l u t 结构图 v i r t c x 器件中，查找表( u j t ) 被用作函数发生器。为实现这一功能，每个 l u t 提供1 个1 6 1 位同步r a m 。同时，每个s l i c c 的2 个l u t 可以组合成一个 1 6 2 或3 2 1 的同步i 认m 、或者是1 6 1 的双端口同步洲。在理想情况下， u j t 还可以配制成1 个1 6 位移动寄存器，用来捕获突发模式下的高速数据。这种 模式还可用在数字信号处理中存储数据。v i r t e x 函数发生器工作原理类似于r o m ， u j t 的输入等效于r o m 的地址码，通过查找r o m 中的地址表可以得到相应的组 合逻辑输出。另一方面v i r t e x 函数发生器还可以作为器件内高速洲或小的可读 写存储器使用，由信号控制电路。 v i r t e xs l i c e 的详细结构如图3 3 所示。v i n e xs l i c e 中的存储单元可被配置为边 沿触发的d 触发器( dn i p n o p s ) 或是电平触发的锁存器。d 触发器的d 输入可 被s l i c c 内的函数发生器驱动，也可以跳过函数发生器而直接被s l i c e 输入驱动。 除时钟和时钟使能信号以外，每个s l i c e 的时钟和时钟使能信号可以同步置位( s r ) 和复位( b y ) 。这些信号还可被配置成异步操作方式。s l i c e 内的两个d 触发器共 用所有的控制信号。 第三章v i r t e xc l b 结构模型研究 1 9 图3 3v i r t e ) 【器件s l i c e 结构图 v i n c x 器件的c l b 专用的进位逻辑为高速运算提供了快速的算术进位能力。 每个c l b 支持两个独立的进位链，进位链高度为2 b i t s