（微电子学与固体电子学专业论文）层次化fpga装箱问题研究.pdf

摘要 随着现场可编程逻辑阵列( f p g a ) 的规模越来越大，可编程逻辑的结构也 发生了很大的变化。目前，层次化的可编程逻辑结构已经占据了主流地位。相比 较单一的可编程逻辑结构，层次化的结构更有利于大型的数字系统的实现，有效 地降低了整个系统的连线延迟。与层次化的硬件结构相对应的是f p g a 软件设计 流程。针对单一的逻辑结构，设计流程相对简单；但引入了层次化的概念咀后， 整个设计流程需要进行调整，在工艺映射和布局布线之间加入了装箱这模块。 装箱作为设计流程中的重要一环，能够对层次化的结构提供很好的支持，通过考 虑各种不同的目标吸收函数，可以实现面积、延迟、布通率或者功耗的优化。从 现在的f p g ai p 核的发展角度来说，针对有限的口核面积进行优化显得尤为重 要。 本文在f d t 2 0 0 k 逻辑单元结构的基础上，提出了一种能够优化组合电路结 构的装箱工具f p a c k ，并嵌入在整个f d t 2 0 0 k 的设计环境中。它利用了组 合电路经常存在的输入端共享，通过抽象出层次化c l b 结构的数学模型，减少 了实现用户电路所需要的可编程逻辑单元的数量，同时因为减少了单元的数量， 外部连线的压力也得到了一定的缓解。 另外，本文还对层次化c l b 结构的内部互连进行了研究，建立了处理层次 化e l l 3 结构内部互连的数学模型。在此模型的基础上提出了一套能够初步处理各 种内部互连结构的装箱工具d p a c k ，通过试验结果初步确定了能够协调层次化可 编程逻辑结构的面积、延迟以及灵活性的非全通内部互连结构。 关键词：可编程逻辑层次化装箱输入端共享非全连通 a b s t r a c t a st h ei n c r e a s i n gs c a l eo ft h ef i l e dp r o g r a m m a b l eg a t ea r r a y s ( f p g a ) ，t h e s t r u c t u r eo ft h ef p g al o g i cb l o c kh a sb e e nc h a n g e dal o t t h eh i e r a r c h i c a ll o g i c b l o c kh a st a k e nt h ea d v a n t a g en o w c o m p a r e dt ot h es i n g l es t r u c t u r eo ft h el o g i c b l o c k ，h i e r a r c h i c a ls t r u c t u r ei sm o r eb e n e f i tf o ri m p l e m e n t i n gt h el a r g ed i g i t a ls y s t e m ， d e c r e a s i n gt h ed e l a yo ft h es y s t e m a tt h es a m et i m e ，t h ed e s i g ne n v i r o n m e n to f t h e f p g ah a sb e e nm o d i f i e da c c o r d i n gt ot h en e ws t r u c t u r e an o v e lm o d u l ec a l l e d p a c k i n gs h o u l d b ea d d e di nb e t w e e nt e c h n o l o g ym a p p i n ga n dp l a c e m e n t r o u t i n g a sa ni m p o r t a n ts t e po ff p g ac a df l o w , p a c k i n gc o u l dg i v ep e r f e c ts u p p o r tt ot h e h i e r a r c h i c a ls t r u c t u r e i tc a no p t i m i z et h er e s u l tw i t ht h eg o a lo fa r e a ，d e l a y , m u t a b i l i t yo rp o w e r t h ea r e ao p t i m i z a t i o nw o u l db em o r eu s e f u li na p p l i c a t i o no f f p g ai pc o r eb e c a u s eo f k sl i m i t e dc h i ps i z e t h i sp a p e rp r o p o s e sat o o lc a l l e df p a c kt h a tc a no p t i m i z ec o m b i n a t i o n a l c i r c u i t s t h i st o o li se m b e d d e di nt h ed e s i g ne n v i r o n m e n to ft h ec h i pf d t 2 0 0 k i t u s e st h ef e a t u r eo fi n p u t - s h a r i n gt h a ti sc o m m o ni nc o m b i n a t i o n a lc i r c u i t st or e d u c e t h en u m b e ro fc l bt h a tn e e d e df o ri m p l e m e n t a t i o no ft h ec i r c u i tb ya b s t r a c t i n gt h e m a t h e m a t i c a lm o d e lo ft h eh i e r a r c h i c a lc l bs t r u c t u r e a tt h es a l n l et i m e ，i n t e r c o n n e c t c o u l da l s ob eo p t i m i z e da st h er e d u c t i o no f t h ec e l l s ， i na d d i t i o n ，ar e s e a r c ho fi n t e r c o n n e c ti n s i d et h ec l bh a sb e e n d o n ei nt h i sp a p e r am o d e lh a sb e e nb u i l t a n dat o o lc a l l e dd p a c kh a sb e e np r o p o s e dt od e a lw i t h k i n d so ft h ei n t e r c o n n e c tm a t r i xb a s e do nt h em o d e l s o m ed e p o p u l a t e di n t e r c o n n e c t m a t r i xh a sb e e ne v a l u a t e dt ot r a d e - o f f t h ea r e i l ，d e l a ya n df l e x i b i l i t yo f t h eh i e r a r c h i c a l c i ，bs t r u c t u r e k e y w o r d s ：p r o g r a m m a b l el o g i c ，h i e r a r c h i c a l ，p a c k i n g ，i n p u t - s h a r i n g ，d e p o p u l a t i o n u 第一章引言 第一章引言 1 1 可编程逻辑器件结构以及设计流程 自从1 9 8 5 年x i l i n x 公司f x m i l 推出世界上第一块现场可编程逻辑阵列 ( f p g a ) 芯片以来，可编程逻辑领域已经发展了2 0 多年。二十多年来，可编程 领域从结构特征来看有两大阵营：f p g a 和c p l d ( c o m p l e xp r o g r a m m a b l el o g i c d e v i c e ) 【h u a n g 9 7 。前者是基于门级的可编程，后者是基于逻辑块级的可 编程，但从发展上来看，二者越来越融合，现在所谈论的可编程逻辑器件一般 指f p g a ，但它已经包含了c p l d 的很多特性。相对应的，可编程逻辑器件的 电路网表 逻辑优化 山t 瞀端数卜匝目i 7 i二= 。： 黜卜- 压输入端数目ll= ： 锹卜丁了丽他约束信息广1 川叫刚口域 编程下载 图1 1 可编程逻辑器件设计流程 物理设计流程一般包含电路网表输入( g e r i l o g 、v h d l 或b l i f 格式) 、逻辑优 化 s e n t 9 2 、工艺映射 c o n g 9 4 c o n g 0 3 】、布局布线 b e t z 9 7 b 。一个电子 系统配置在f p g a 的硬件资源上，就是由可编程器件的设计软件根据用户的 输入来实现的。 当进入深亚微米工艺以后，随着阵列规模的不断扩大，阵列结构也发生了 很大的变化。过去的阵列结构大多采用“细粒度”结构，即一个c l b ( c o n f i g u r a b l el o g i cb l o c k ) 只包含一个基本逻辑单元，阵列中的所有c l b 第一章引言 通过布线资源连接在一起。这样的阵列结构对实现小规模的电路系统是适用 的，但“细粒度”结构实现较大的设计时，一个不可避免的问题是对布线造成 了巨大的压力，既影响了布通率又增加了连线的延迟。因此，“粗粒度”的可 编程逻辑器件结构逐渐被学术界和商业界所采用【b e t z 9 7 a b e t z 9 8 a 【a l t e 】 【x i l i 。所谓“粗粒度”可编程逻辑器件结构，就是将若干个基本逻辑单元通过 高速互连连接在一起构成一个c l b ，再用外部互连将所有的c l b 构成一个完整 的阵列。一般意义上来说，不论是“细粒度”结构还是“粗粒度”结构，基本逻 辑单元都是组合逻辑l u t 和时序逻辑d f f 一种组合关系。对于实现大型的电子 系统设计，利用这种层次化结构内部互连的使用，大大降低了连线延迟，同时由 于相关逻辑使用同一个c l b 实现，减轻了外部布线资源的利用，对提高布通率 也很有帮助。 基于新的结构特点，可编程逻辑器件的设计流程也有调整，层次化结构的可 编程逻辑器件的设计流程见图1 1 所示，在工艺映射和布局布线之间，加入了装 箱步骤。这一步骤的加入正是为了实现从基本逻辑单元到c l b 的一次转换。它 所考虑是如何将工艺映射完成后得到的基本逻辑单元网表转换为c l b 级的网 表。一般意义上来说，装箱所基于的工艺映射算法是以u j t ( l o o ku pt a b l e 查 找表) 作为考虑目标的。图1 2 直观的反映了这一过程。 ( a ) 原始网表 ( c ) 基本逻辑单元网表 l ( b ) 工艺映射后网表 i c 、i i e l k c i - b ( d ) c l b 网表 图1 2 装箱示意图 图1 2 中，原始的电路网表( a ) 经过工艺映射后得到( b ) ，经过整合，得 到一个基本逻辑单元的网表( c ) ，在此基础上装箱后即得到c l b 级的网表。 瘸 第一章引言 1 2 装箱算法的发展 装箱问题是一个经典的n p 难解问题，在实际生活中应用很广泛，它可以这 样表述：给定h 个物品的集合l 。= ( 口l ，a 2 ，a n ) ，物品矗，( 1 f ) 的大小j f ) e ( o ，1 ，即s ( a 1 ) 为( o ，1 之间任意一个实数。要求将这些物品装入单位容量的箱子 中并要求箱子的数量最小。例如，把物品序列中的物品分别放入箱予集合 ( 矗l ，b z ，b t ) 中，使得每个箱子中的物品大小之和不超过1 ，且所用的箱孑数目 z 最d 、 g u 0 1 。解决装箱问题的下次适应( n e x tf i t ) 算法：先按照物品大小顺序 对集合中的元素进行降序排序；而在装箱过程中，每次只保持一个箱子为打开的。 在处理物品a f ( 1 f n ) 时，假设当前打开的箱子为局( 1 f 1 - 1 ) ，检查a ，能 否放入且中，若能，则将a ，放入夙中，仍保持日为当前打开的箱子；否则，关 闭且，打开新的箱子曰州，把ar 放入b “中，曰。t 变为当前打开的箱子。如此循 环下去，直至所有的物品都装入箱子。这样一种贪婪思想的运用，保证了每一步 都能构造一个最优解，最后得到的解也是最优解的逼近 x i n g 9 8 。 层次化f p g a 的设计流程中，引入装箱思想，并将其发展成设计流程中一个 独立的模块。它所关心不再是如何用可编程逻辑单元中的组合逻辑l u t 来实现 原始网表中的组合部分，而是如何用层次化的结构去实现这些组合部分。多伦多 大学提出的v p a c k 算法 b e t z 9 7 a 是这一领域的先驱。该算法以网表中各个基 本逻辑单元之间的连接线网的相关程度作为吸收函数来展开的。 接下来，多伦多大学又提出了v p a c k 算法的改进版一一tv p a c k 【m a r q 9 9 】。它在原有的基础上增加了对时延的考虑，减小了装箱后关键路径的 延迟。tv p a c k 的吸收函数折中考虑了相关度和延迟度，通过实验数据确定了 折中因子，并得到了较好的结果。 另一方面，以布通率为主要优化目标的装箱算法也相继提出， r p a c k b o z 0 0 1 和i r a c s i n g 0 2 都是这方面的代表。他们考虑的对象不再是 基本逻辑单元，而是连接基本逻辑单元的连线。通过考察这些线网的端子数，确 定连接这些线网的基本逻辑单元的吸收因子从而完成装箱。其结果对布局布线有 很好的指导作用。 最近，随着低功耗研究越来越热门，以低功耗为优化目标的装箱算法也有提 出，a c t i v i t y p a c k i n g h a s s 0 5 是这方面的代表。他通过计算出网表中基本逻辑单 元的活动度，来判断哪些单元适合装箱在一起。每一个c l b 都整合了同一种活 动度的基本逻辑单元，就可以结合电路的特点让某些c l b 在不活动的情况下处 于关断状态，降低功耗的产生。 第一章引言 1 3 工作重点 由于现有的装箱算法都是基于学术上通用的基本逻辑单元模型，而 f d t 2 0 0 k 却提出了与学术界截然不同的模型，故这些装箱算法不适用于 f d t 2 0 0 k 基本逻辑单元模型的。f d t 2 0 0 k 的基本逻辑单元组合部分采用了两个 小规模的l u t 组成一个稍大规模的l u t 的形式，并增加了一个输出管脚，可以 针对组合电路进行优化。因此本文的工作之一，就是在f d t 2 0 0 k 的逻辑单元结 构的基础上提出了一种装箱工具f p a c k ，它作为整个f d t 2 0 0 k 的设计环境一部 分，实现整个流程中的装箱操作部分，并能大大降低组合电路装箱后c l b 的使 用数目。对于面积有限的f p g ai p 核而言，减少编程使用的可编程逻辑单元数 目不仅可以有效的减小所需的芯片面积；另外较少的逻辑单元数目意味着较少的 单元间接口，因此它还能缓减布线资源的需求。 另外，考虑到现有的c l b 模型大都采用全连通的内部布线资源结构，对于 面积和延迟的影响较大。因此，本文的工作重点之二就是提出了一个基于非全连 通模型的装箱算法d p a c k 。通过分析内部布线资源的结构关系以及各种连通关 系下的装箱结果，能够很好的指导c l b 结构的设计，以达到面积、延迟和灵活 性的统一。 1 4 论文组织 本文组织结构如下：第二章作为整个研究背景的介绍，提出了装箱的数学模 型，并介绍了各种已有的装箱算法及其特点。第三章提出了基于f d t 2 0 0 k 的可 编程逻辑单元模型的装箱工具f p a c k ，并将其和学术上的一些模型的结果进行 了比较。第四章则对非全连通可编程逻辑单元的装箱问题进行了研究，提出了 d p a c k 算法评估各种非全连通结构对装箱结果的影响。第五章对自己的工作进 行了总结，并对未来进一步工作的方向提出了展望。 4 第一二章研究背景 第二章研究背景 由于层次化的f p g a 结构的迅猛发展 b e t z 9 7 a b e t z 9 8 a 】，尤其是a l t e r a 的f l e x 系列 a u 、e 】和x i l i n x 的v i r t e x 系列 x i l q 等商业化产品的推出，针对层 次化f p g a 的研究显得越来越重要。其中，涉及f p g a 设计流程中初始映射到布 局布线之间的装箱算法的研究也涌现了很多。有着眼于面积优化的 v p a c k b e t z 9 7 a ，以及以时延为驱动目标的tp a c k m a r q 9 9 ，也有着眼于 整个芯片布通率的优化算法r p a c k b o z 0 0 1 和i r a c s i n g 0 2 1 ，后来又发展了 面向低功耗的装箱算法a c t i v i t yp a c i n g h a s s 0 5 1 。本章就这些已有的算法进行介 绍，以引出后面自己的工作。 n p c ( a ) b l e ( b ) c l b 图2 1 装箱算法模型 首先，我们对装箱问题进行数学抽象，假设基本逻辑单元集合如下： b = b l ，6 2 ，仇) ，式中b 表示一个基本逻辑单元b l e ( b a s i cl o # ce l e m e m ) ， 如图2 1 ( a ) 所示。 而所要求解的c l b 的集合是由m 个c l b 构成的，每个c l b 包含的基本逻 辑单元个数为，输入端数目限制在，以内，即： c = c l ，c 2 ，c 卅) ，式中c 表示一个可配置逻辑块c l b ( c o n f i g u r a b l el o g i c b l o c k ) ，如图2 1 ( b ) 所示。 第二章研究背景 j c i n i = 1 ，m ， i n p u t ( q ) ，江1 ，m ， 同时还有如下的约束条件，它们表示任何一个基本逻辑单元只可能属于唯一 的c l b ： c f n c ，= gf ，= 1 ，m ，f j ， 红u 2 。c i = 1 ，挖，j = l ，m 装箱的目标就是在各种目标函数的约束下获得最小的c 的集合，即m 值最 小。下面我们将分析介绍已有的几种装箱算法。 第二章研究背景 2 1 基于面积优化的装箱 v p a c k b e t a 9 7 a 是关于层次化f p g a 设计中最早提出来的装箱算法，由 b e t z 等人于1 9 9 7 年提出，具有里程碑的意义。由于f p g a 的结构发展得很迅速， 过去的那种单一结构的“细粒度”颗粒的f p g a 逻辑结构虽然在逻辑利用率上较 高，但是对布线资源的制约越来越明显，布线越来越难，成为f p g a 软件设计流 程的一道瓶颈。基于此情况，层次化的“粗粒度”颗粒的f p g a 逻辑单元结构应 运而生。图2 1 所示的( a ) 、( b ) 两图即可说明此问题，它实际上包括了两个层 次。第一层就是图2 1 ( a ) 所示的b l e ( b a s i cl o g i ce l e m e n t 基本逻辑单元) ， 针对“细粒度”f p g 认，这一层就是c l b 。若干个图2 1 ( a ) 的b l e 结合布线资 源组成整个f p g a 阵列。第二层就是将原来的b l e 进行组合，形成一种既包含 了若干b l e ，又包含了若干内部连线资源的c l b 结构如图2 1 ( b ) 。从图中c l b 的角度来说，已经可以看作一个小型的f p g a 了。现在的问题就是通过对电路的 分析，将一部分有关联的部分“装入”此c l b ，再将整个电路的c l b 通过外部 布线连接起来，形成一个真正的f p g a 实现。 如前所述，对于装箱问题可以引入贪婪算法，故v p a c k 在算法运行过程中 使用贪婪算法逐步构造每个c l b ，以达到每个c l b 的最大化利用。该算法适用 图2 1 所示模型，参数如下： nc l b 中b l e 的数目 kb l e 的l u t 输入端数目 ，c l b 输入端数目 需要注意的是，v p a c k 的c l b 模型对于时序逻辑的时钟线网c l o c k 和输出 端的考虑比较简单。尤其是其输出，每个b l e 只有一根输出线网，这主要囿于 b l e 的模型。同时，在c l b 的输入线网和所有b i l e 的输入线网之间的m u x 采 用了全连通的连接方式，即所有的外部输入和输出反馈都可以无障碍的连接到 b l e 的输入端。另外，n 、k 、i 之间的关系为厅，k n o 在此基础上，v p a c k 定义如下吸收函数作为c l b 中包含b l e 的依据。 a t t r a c g o n ( 曰) = l j 捃( 卸n n e u ( c ) i ( 2 1 ) 式( 2 1 ) 中，b 和c 分别代表b l e 和c l b ，肌船倒表示口的输入线网集合， 他船r o 表示c 的输入线网集合。a t t r a c t i o n ( b ) 代表口和c 的输入线网集合的交集。 这个交集越大，表示这个吸收因子越大。对于每个c l b ，装箱初始时需要选择 一个b l e 作为该c l b 的“种子”。在装箱过程中，利用吸收函数( 2 1 ) 去判断 哪个b l e 更适合装入正在操作的c l b 。式( 2 1 ) 越大，表明该b l e 装入此c l b 的几率越大。除此之外，该算法还在最开始加上一个排序过程以降低时间复杂度。 图2 2 的流程图说明了v p a c k 的算法思想。 7 第二章研究背景 虽然考虑的问题比较简单，但v p a c k 还是开创了层次化f p g a 装箱算法的 先河，后续的很多算法都是在此基础上演化而来的。 图2 2 v p a c k 流程图 第一二章研究背景 2 2 延迟优化的装箱算法 堆 ( a ) c l b 以及b l e 模型时延参数的选择 c l b b a s e 。口n 7 5 b l e l 06 5 一- 厂_ 一。 一b l eb l e 一一一 0 9 7 7 i a s eb l ec r i t i c 捕i i t v = o9 7 ( b ) b l e 关键度的选择 图2 3 tv p a c k 延迟模型 多伦多大学的f p g a 研究小组再接再厉，m a r q u a r d t 等人在9 9 年提出了新的 层次化f p g a 逻辑单元装箱算法t v p a c k ，与前者不同之处在于引入了时延驱动作为优化目标。如图2 3 ( a ) 所 示，在他们所讨论的c l b 以及b l e 模型的基础上，提出了时延参数的假设。 不考虑外部布线的延迟，针对层次化结构的c l b ，我们可以按照信号的走 向将数据通路划分为图2 3 ( a ) 中所示的三段：a 到b 表示不同的c l b 的b l e 之间的延迟，b 到c 表示c l b 内部的布线延迟，也就是相同的c l b 的b l e 之 间的延迟，c 到d 表示b l e 本身的逻辑延迟。根据s l a c k 的定义 f r a n 9 2 h i t c 8 3 】，我们可以定义每条驱动b l e 输入管脚的线网时延松弛度 s l a c k 如式( 2 2 ) 所示，其中z 乙。i r e d 表示从目标点( 输出管脚或者寄存器输入管 脚) 传输到该线网的时间，疋州。，表示到从源点( 输入管脚或者寄存器输出管脚) 传输到该线网的时间，二者的差值即为s l a c k ： s l a c k = 乇。删一z 删 ( 2 2 ) 从( 2 2 ) 式可以看出，越靠近关键路径的线网，其松弛度越小。通过计算 每根线网的s l a c k ，确定其中的最大值m a x s l a c k 后，通过归一化得到每根线网的 关键度c o n n e c t i o nc r i t i c a l i t y 如下式： 第二章目f 究背景 c o n n e c t i o ”c r i t i c a l i t y ：1 一塑竺 ( 2 3 ) m a x s z 口c 庀 线网的关键度值越大，表明约需要考虑其对系统时延的影响，在装箱过程中 越需要考虑。在图2 2 ( b ) 中我们看到，b l e 的关键度c r i t i c a l i t y ( b l e ) 的选择就 是按照上面的原则进行的。需要装箱的b l e 的关键度为其与c l b 相交线网的关 键度中的最大值。这样确定了每个b l e 的关键度的值后，将作为装箱吸收函数 中间的权重因子之一。 时延权重因子得到以后，再和相关度因子加权得到整个装箱算法的吸收函数 a t t r a c t i o n ( b l e ) 如式( 2 4 ) 所示，式中“表示加权因子，通过a 值得选取，可以 权衡时延权重和非时延权重对于吸收函数的影响，同时非时延权重因子也进行了 归一化处理： a t t r a c t i o ”( s l e ) ：口c r i t i c a l i t y ( b l e ) + ( 1 一口) n e t s ( b l e ) n = n e t s ( c l b 一) ( 2 4 ) b g = 挣b l ei n p u t s + # b l eo n t p u t s + # b l ec l o c k s ( 2 5 ) 在 m a r q 9 9 的文献中，他们通过实验证明了当a 为o 7 5 时，所得到的结果 是tv p a c k 中最优化的。 第二章研究背景 2 3 基于布通率的装箱 2 3 1r p a o k ( a ) 相关线网吸收示例 爿 ，| - 一 - 制 们 v 1 一 c l b c o ) 不相关线网吸收示例 图2 4r p a c k 线网增益示例图 基于布通率的装箱算法以装箱完成后外部线网的数目减少为另一优化目标 来考虑的 b o z o o u 。在该算法中，吸收函数以增益g a i n 的形式定义如式( 2 6 ) 所示： g a i n ( b ，c ) = f ( n e t s ( b ) ，n e t s ( c ) ) = ：g ( f ，n e t s ( c ) ，b ) ( 2 6 ) i e n e t s ( b ) ( 2 6 ) 式说明一个基本逻辑单元与一个c l b 之间的增益g a i n 佃，a 通过该 基本逻辑单元的每条线网i 与c l b 之间计算的增益g ( i , n e t s ( c ) ，剧得到的，而后 第二章研究背景 者的定义如式( 2 7 ) ： 觯，酬c 胁 ：蔫怒印，o 翱卜烈以功尸“f 耍篇嚣眨， ( 2 7 ) 式中凡定义为输入线网的增益，尼定义为输入线网的增益，当这根 线网同时属于c l b 时，要加上固定增益l 。如果这根线网不属于c l b ，则根据 其吸收进入c l b 后为输入还是输出将其置为一l 或者0 。反映在式( 2 7 ) 中，即 耶，剧这个变量在这根线网吸收进入c l b 后为输入时，设为1 ；为输出时设为0 。 为了解释式( 2 7 ) 中各个参数的意义，图2 4 列出了所有可能的情况并在表2 1 种进行了说明。 从图2 4 中我们可以看到，( a ) 中表示了n 1 、n 2 、n 3 、n 4 四种情况，( b ) 中表示了n 5 、n 6 两种情况。n 1 表示b l e 输入端线网被c l b 中输入线网吸收 ( 即二者为同一根线网) 的情况，n 2 表示b l e 输出端线网被c l b 中输入线网 吸收的情况，n 3 表示b l e 输入端线网被c l b 输出端线网吸收的情况，n 4 表示 b l e 输入端线网无法被吸收的情况，n 5 表示b l e 输出端线网被c l b 输入端线 网吸收的情况，n 6 表示b l e 输出端线网无法被吸收的情况。表2 1 种列出了每 一中情况的增益。( 2 7 ) 式的增益值即可从表2 1 种获得，从而获得整个b l e 对 c l b 的增益。r p a c k 选择最大增益值的b l e 装箱。 表2 1 各种线网增益表 线网输入线网增 输出线网增固定增益 总增益 益盆 n 10ol1 n 2lo12 n 3o112 n 41oo一1 n 51l13 n 6oo00 2 3 2 ir a c 虽然r p a c k 考虑到了装箱对布通率的影响，当时它对于布通率的考虑还不 是很精确。i r a c s i n g 0 2 很好的解决了这一问题。在这篇文献中，作者更精确 地描述了线网对于装箱的影响。因为多端线网情况的存在，因此只有建立一个多 端线网的模型才能得到一般情况下的解，双端线网是建立在此基础上的特例。作 者定义了b l e 结构的连通度c 如( 2 8 ) 式所示： c ：s e p e r a t i o - n( 2 _ 8 ) d e g r e e 2 。 式中d e g r e e 定义为一个b l e 连接的所有线网，s e p e r a t i o n 定义为所有线网的 端点数。在图2 5 中，我们可以看到，( a ) 中的a 所拥有的d e g r e e 是4 ，s e p e r a t i o n 是1 8 ( a 本身要计算4 次) ，所以c 为1 1 2 5 ；而( b ) 中的b 的d e g r e e 是4 ，s e p e r a t i o n 是8 ，则c 为o 5 。这就比r p a c k 更近了一步，使得一个c l b 初始的b l e 的选 第二章研究背景 择更有说服力。如果c l b 的容量为5 ，显然选择b 为初始b l e ，可以完全吸收 周围的4 个b l e ，比选a 为初始b l e 有优化作用。 口u + 厂 厂k田 厂_ 厂 n 广 一l 一 ￥ 南v叫叫￥l j 几l z 厂水p 3 下 厂一l r 。 琢 ( a ) 部分吸收示例 ( b ) 完全吸收不例 图2 5i r a c 装箱吸收示例图 当初始b l e 选择好以后，对后面每一个b l e 的吸收，i r a c 采用如式( 2 9 ) 所示的吸收函数： g ( x ，c ，石) = 2 刀c o ( x ) ( 1 + 口，) ( 2 9 ) 式中( x ) 定义为2 r ，r 为线网x 端点总数，定义为线网x 已经被吸收入 c l b 中的端点数目。如图2 5 ( a ) 所示，y 要吸收入a 所在的c l b ，就要分别 计算y ，、弦，归三根线网的吸收函数的值后向加即得y 的吸收函数。通过这样 的分析，i r a c 测试后得到的结果大大优于r p a c k 。 第二章研究背景 2 4 功耗优化的装箱算法 随着近年来低功耗研究的热门，f p g a 领域低功耗的研究也做出了一定的成 果。尤其是前端的设计流程，包括映射和装箱，都有相应的以低功耗为目标的算 法被提出。装箱领域低功耗的研究主要是文献 h a s s 0 5 】中提出的。文中作者定 义了活动度这个概念，反映一个逻辑模块随其输入向量而变化的程度。它将一些 活动度相同的b l e 装箱到一个c l b 中，使得电路在用f p g a 实现以后，动态得 开关某些c l b ，以达到功耗的降低。当然这样设计的前提是需要相应的硬件结 构的支持的，如图2 6 所示，在原先的c l b 结构中的每个b l e 都加上一个n m o s 管子接地并用一个睡眠信号控制栅极电压，就是一种开关c l b 结构的实现。 c 图2 6a c t i v i t yp a c k i n g 装箱模垄r 4 第三章f d t 2 0 0 k 的逻辑单元装箱工具 第三章f d t 2 0 0 k 的逻辑单元装箱工具 3 1f d t 2 0 0 k 逻辑单元特点 可编程逻辑单元是f p g a 的核心功能单元。f p g a 主要由阵列式的可编程逻 辑单元组成，通过对可编程逻辑单元的不同配置和连接，编程成为不同的电路来 实现设计者所需的功能。在研究和商业领域提出了众多不同的可编程逻辑单元结 构，f d t 2 0 0 k 实验芯片的可编程逻辑单元就是在对各主流产品进行了充分的调 研的基础上提出的。它是基于层次化f p g a 结构，采用查找表( l u t ) 的结构模 型而设计的。本课题就其逻辑单元装箱问题进行了研究，在结构模型的基础上提 出了一套工具进行支持。 3 1 1 层次化f p g a 结构 口口口口口口口口口口口口 l 目c e 爿l 巨爿c 巨| l c 目s 目c 目s 目c se 爿c e 爿l 目c e 爿s c e 爿se 爿c e 刍se 刍c l 曰c 目l 目c 目l 口口口口口口口口口口口口 图3 1 对称式f p g a 结构 图3 1 所示是经典的对称式f p g a 结构 x i l i ，该结构最早由是j r o s e 等人 b r o w 9 2 提出，由可编程逻辑单元( 图中l 所示) 、连接盒( c o n n e c t i o nb o x ， 图中c 所示) 、开关盒( s w i t c h b o x ，图中s 所示) 以及连接它们的金属线组成。 可编程逻辑单元能够实现一定的组合逻辑函数和时序逻辑，连接盒将可编程逻辑 单元的输入输出连接到连线金属上，开关盒使得不同的连线之间进行信号的连 接。这是一种平面化的结构，其中所有可编程功能模块都在同一个层次上进行组 织。这种结构得到了最多的关注，多数f p g a 结构的研究在这样的结构框架下进 行。它灵活性好，在不同应用领域中都能得到比较好的面积利用率而且与这种结 构的f p g a 结构相配合的f p g ac a d 软件也较为简单，但是速度性能相对较差 口口口口口口口口口口口口口口口口口口口口口口口口 第三章f d t 2 0 0 k 的逻辑单元装箱工具 m a 0 4 w a n g 0 4 a g g a 9 4 b r o w 9 2 【c h a n 9 6 】 w i l t 9 7 b e t z 9 8 b 】 【b e t z9 9 。 口口口口 、 麟 口口口口。口口口口、 口口口口i口口口口 口口口口、口口口口j 口。v 口玉口；口。v 口玉口； 、， 口口口口：口口口口、。 口口口口、口口口口 口口口口口口口口 、 爹i 口。v 口玉口口。v 口立矗口? 口口口口 口口口口 口。v 口晶口 i 、 口口口口 、 、 口口口口 口口口口 、 口。习旦口 、 、 、 、“i 一 曩譬蠢躐 繁 j 囊酷镬露热鬟i 篙妻：囊粪嚣嚣i ，一- 。 口口口口口口口口、口口口口 口口口口口口口口口口口口 口口口口口口口口、口口口口 口。v 口默 口。v 口王矗口、口。v 口旦口 图3 2 层次式f p g a 结构 层次式的f p g a 结构如图3 2 中所示，是通过分层的方法组织可编程功能模 块。每一个层次的可编程逻辑单元都由低一层次上的若干可编程逻辑单元和可编 程连线构成，整个器件由最顶层的可编程逻辑单元、可编程连线和可编程i o 组 成。这种结构面积小、速度性能较好，在f p g a 的规模很大时也能够方便c a d 软件对可编程功能模块进行处理，但所需的软件算法也较为复杂。 f d t 2 0 0 k 可编程资源采用层次化结构。层次式连线结构结合了对称式连线 和长线连线的特点。采用层次式连线结构的f p g a 主要有x i l i n x 公司的v i r t e x 、 s p a r t a n l y l i i 系列和a l t e r a 公司的f l e x 、a p e x 系列。层次式f p g a 结构的模块 内部的连接用低层次的连线完成，由于低层次的连线较短，寄生电阻电容较小所 以能够实现小跨度的快速连线；跨模块的连接用高一层的跨度较大的连线完成， 可以减小连线经过的可编程开关数目，提高速度。这用针对不同类型的线网能够 采用不同层次的连线进行优化实现，使层次式的连线结构有良好的速度性能，同 时其时延也具有一定的可预测性。所以层次式连线结构的f p g a 芯片速度普遍高 于采用对称式结构的f p g a m a r q 0 0 1 。 f d t 2 0 0 k 采用了如图3 3 所示的可编程逻辑单元簇( c l u s t e r ) 结构 第三章f d t 2 0 0 k 的逻辑单元装箱工具 w a n g 0 5 】，它由上下两个完全相同的可编程逻辑片( s l i c e ) 以及一个时序控 制部件s c u ( s e q u e n t i a lc o n t r o lu n i t ) 构成。一个s l i c e 包含上下两个基本逻辑 单元l c ( l o g i cc e l l ) 以及两者间的关联电路，可以完成两个独立4 输入组合逻 辑或者一个5 输入组合逻辑。c l u s t e r 内部的4 个时序单元作为完全独立对称 的单元分布在4 个l c 中，其可以统一配置成带有异步复位或置位以及使能的d 触发器( d f f ) 或者电平锁存器( l a t c h ) 。c l u s t e r 的s c u 处理从互连、专 用时钟网络、全局复位网络送来的时序控制信号，从而为4 个l c 产生统一的时 钟、 图3 3f d t 2 0 0 kc l u s t e r 内部结构 该结构的优点主要体现在速度和面积方面。 第三章f d t 2 0 0 k 的逻辑单元装箱工具 速度方面：由于c l u s t e r 内4 个l c 紧紧相连，版图紧凑。而对称式结构 中的4 个相邻l c 之间有连接盒和开关盒相隔，其版图连线长度要远远大于 c l u s t e r 结构。在深亚微米工艺下，连线电阻、电容大大增加，尤其是长连线 电容已经大于管子栅电容，长连线延迟大于器件延迟，连线长度已经成为电路性 能分析不可忽略的问题。根据o 1 8 u m 工艺参数计算可得：一个标准反向器的栅 电容大约4f f ，而5 0 u m 长度的连线电容保守估计( 平行板间距大于l u m ) 都大 于5f f 。由版图经验估算，o 1 8 u r n 工艺下对称式结构l c 间间距在1 0 0 u r n 以上， 而c l u s t e r 结构内部连线间距在5 0 u r n 以内。因此c l u s t e r 结构和对称式结 构相比，c l u s t e r 内部l c 间的专用快速信号传输路径延迟要小的多。 面积方面：对于c l u s t e r 内部l c 组合逻辑功能来说，其和平面化对称式 结构的l c 没有太大的不同，二者在面积方面基本相当；而c l u s t e r 内4 个时 序逻辑单元只采用一个s c u 来控制，相比于对称式结构l c 每个都需要一个s c u 来说，面积要小的多( 一个功能强大的s c u 版图面积相当于i 4 1 3 的l c 面积) 。 虽然4 个时序逻辑单元只采用一个s c u ，即使用共同的时钟、复位、d f f l a t c h 选择信号，表明c l u s t e r 内部只能设计成同步电路工作模式，但这并不会对 c l u s t e r 的利用率造成大的影响。因为，对于现在的时序电路设计来说，基本 上都采用同步电路设计方法：而对于异步电路设计来说，以一个c l u s t e r ( 4 个触发器) 作为一个同步电路单元，粒度已经足够小。例如：以异步电路设计中 的2 “分频器为例，如果全部采用异步电路设计，需要n 个级联触发器；若用 f d t 2 0 0 kc u j s t e r 结构实现，则先用c l u s t e r 实现同步1 6 分频模块，然后 c l u s t e r 间可采用异步工作模式，需要h n + 一个c l u s t e r ，所以无论多少分频， 其比对称式独立l c 结构最多多用一个c l u s t e r 。但它和上面提到的f p g a 内 部每个c l u s t e r 可节省3 个s c u 来比较已经显得微不足道，因此，c l u s t e r 结构在面积方面优势非常明显。 3 1 2 基于查找表( i u t ) 的可编程逻辑单元结构模型 f d t 2 0 0 kc l u s t e r 内部的l c 基于l u t 查询表结构。图3 4 是f d t 2 0 0 k 的一个s u c e 结构( 内部悬空点由编程点控制) ，由两个相同的l c 以及两者中 间的连接电路组成。不同于常见的基于四输入查询表结构的l c ，f d t 2 0 0 k 一个 l c 是由两个具有相同输入的3 输入l u t 、多个数据选择器、快速进位链、以及 一个可编程控制时序逻辑单元构成。两个独立三输入查询表和数据选择器可完成 最高4 输入任意组合逻辑，也可以产生两个相同输入的任意3 输入函数。快速进 位单元可以结合1 个3 输入l u t