（计算机软件与理论专业论文）可布性驱动的层次式fpga布局算法研究.pdf

华北电力大学硕士学位论文 摘要 在超深亚微米技术工艺下，布局成为超大规模集成电路物理设计中至关重要的 一步。由于现场可编程门阵列( f i e l dp r o g r a m a b l eg a t ea r r a y ，f p g a ) 布线资源的 预先确定性，使得f p g a 的布局更为重要。本文以建立高性能、低拥挤的布局为目 标，从f p g a 芯片结构和布局算法两方面进行了深入研究。论文提出了一种通用的 层次式f p g a ( h f p g a ) 结构模型及布局模型，并且给出了该模型的数学计算公式； 提出将元件之间的层次距离转化为线长的方法，实现了基于线网模型的高精度布局 算法：提出利用矩形的对角线元件之间层次来代替线长，从而达到优化线长的同时 提高布通率的快速布局算法。实验结果表明，两种算法均在北卡罗来纳微电子中心 ( m c n c ) 学术芯片测试案例上取得了较理想的布局实验效果，为下一步的布线工 作建立了良好的基础接口，并且完成了初始布线的工作。本f p g a 结构模型的提出 和布局算法的实现也都为工业界提供了借鉴价值。 关键词：现场可编程门阵列，拥挤度，层次式，对角线快速布局，高精度布局 a b s t r a c t u n d e rt h ev e 巧d e e ps u b - m i c r o nt e c h n o l o g y , p l a c e m e n tb e c o m e st h ek e yp a r to f v l s id e s i g n i na d d i t i o n ，t h a n k st ot h ep r e d i c t a b i l i t yo ft h er o u t i n gr e s o u r c e s ，p l a c e m e n t p l a y sa ni m p e r a t i v er o l ei nf p g ad e s i g n a i m i n ga tt h eh i g h e rp e r f e r m o n c ea n dl o w e r c o n g e s t i o n ，t h i st h e s i sm a i n l yf o c u s e so nt h ef p g aa r c h i t e c t u r em o d e la n dr e l a t e d p l a c e m e n ta l g o r i t h m t h et h e s i sp r o p o s e s av e r s a t i l eh i e r a r c h i c a lf p g a ( h f p g a ) a r c h i t e c t u r em o d e la n dg i v e st h ec o r r e s p o n d i n gm a t h e m a t i c a lm o d e l i ti m p l e m e n t st h e h i g ha c c u r a c yr o u t a b i l i t y d r i v e np l a c e m e n ta l g o r i t h mf o rh f p g a b a s e do ni n t e r c o n n e c t w i r em o d e la n dt h ef a s td i a g o n a lp l a c e m e n ta l g o r i t h mu s i n gt h ed i a g o n a lh i e r a r c h i c a l l e v e li n s t e a do ft h ew i r e l e n t h t h ea l g o r i t h m se f f e c t i v e n e s si se v a l u a t e db yt h e e x p e r i m e n t a lr e s u l t so fm c n cb e n c h m a r k f i n a l l y , i te s t a b l i s h e st h ei n t e r f a c ef o rt h e r o u t i n ga n dc a nf i n i s hg l o b a lr o u t i n gf o u n d e do ni t sd a t as t r u c t u r e t h ep r o p o s e df p g a a r c h i t e c t u r em o d e la n dt h er e l a t e da l g o r i t h mp r o v i d et h eu s ef o rr e f e r e n c ef o ri n d u s t r y w a n gy a n h u a ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f q uj u n h u a k e y w o r d s ：f p g a ，c o n g e s t i o n ，h i e r a r c h i c a ll e v e l ， d i a g o n a lf a s tp l a c e m e n t ，h i g l la c c u r a c yp l a c e m e n t 华北电力大学硕士学位论文 摘要 在超深亚微米技术工艺下，布局成为超大规模集成电路物理设计中至关重要的 一步。由于现场可编程门阵列( f i e l dp r o g r a m a b l eg a t ea r r a y ，f p g a ) 布线资源的 预先确定性，使得f p g a 的布局更为重要。本文以建立高性能、低拥挤的布局为目 标，从f p g a 芯片结构和布局算法两方面进行了深入研究。论文提出了一种通用的 层次式f p g a ( h f p g a ) 结构模型及布局模型，并且给出了该模型的数学计算公式； 提出将元件之间的层次距离转化为线长的方法，实现了基于线网模型的高精度布局 算法：提出利用矩形的对角线元件之间层次来代替线长，从而达到优化线长的同时 提高布通率的快速布局算法。实验结果表明，两种算法均在北卡罗来纳微电子中心 ( m c n c ) 学术芯片测试案例上取得了较理想的布局实验效果，为下一步的布线工 作建立了良好的基础接口，并且完成了初始布线的工作。本f p g a 结构模型的提出 和布局算法的实现也都为工业界提供了借鉴价值。 关键词：现场可编程门阵列，拥挤度，层次式，对角线快速布局，高精度布局 a b s t r a c t u n d e rt h ev e 巧d e e ps u b - m i c r o nt e c h n o l o g y , p l a c e m e n tb e c o m e st h ek e yp a r to f v l s id e s i g n i na d d i t i o n ，t h a n k st ot h ep r e d i c t a b i l i t yo ft h er o u t i n gr e s o u r c e s ，p l a c e m e n t p l a y sa ni m p e r a t i v er o l e i nf p g ad e s i g n a i m i n ga tt h eh i g h e rp e r f e r m o n c ea n dl o w e r c o n g e s t i o n ，t h i st h e s i sm a i n l yf o c u s e so nt h ef p g aa r c h i t e c t u r em o d e la n dr e l a t e d p l a c e m e n ta l g o r i t h m t h et h e s i sp r o p o s e s av e r s a t i l eh i e r a r c h i c a lf p g a ( h f p g a ) a r c h i t e c t u r em o d e la n dg i v e st h ec o r r e s p o n d i n gm a t h e m a t i c a lm o d e l i ti m p l e m e n t st h e h i g ha c c u r a c yr o u t a b i l i t y d r i v e np l a c e m e n ta l g o r i t h mf o rh f p g a b a s e do ni n t e r c o n n e c t w i r em o d e la n dt h ef a s td i a g o n a lp l a c e m e n ta l g o r i t h mu s i n gt h ed i a g o n a lh i e r a r c h i c a l l e v e li n s t e a do ft h ew i r e l e n t h t h e a l g o r i t h m s e f f e c t i v e n e s si se v a l u a t e db yt h e e x p e r i m e n t a lr e s u l t so fm c n cb e n c h m a r k f i n a l l y , i te s t a b l i s h e st h ei n t e r f a c ef o rt h e r o u t i n ga n dc a nf i n i s hg l o b a lr o u t i n gf o u n d e do ni t sd a t as t r u c t u r e t h ep r o p o s e df p g a a r c h i t e c t u r em o d e la n dt h er e l a t e da l g o r i t h mp r o v i d et h eu s ef o rr e f e r e n c ef o ri n d u s t r y w a n gy a n h u a ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f q uj u n h u a k e yw o r d s ：f p g a ，c o n g e s t i o n ，h i e r a r c h i c a ll e v e l ， d i a g o n a lf a s tp l a c e m e n t ，h i g l la c c u r a c yp l a c e m e n t 声明户明 本人郑重声明：此处所提交的硕士学位论文可布性驱动的层次式f p g a 布局算法 研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取 得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：墨氆华日 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 导师签名： 日期： 华北电力大学硕士学位论文 第一章引言 1 1 课题的背景、意义和目标 1 1 1 集成电路技术与e d a 工具的发展 二十一世纪，世界全面进入信息时代。作为信息产业的支柱，超大规模集成电 路( v e r y l a r g e s c a l ei n t e g r a t e dc i r c u i t s ，v l s i ) 的设计和制造在推动经济发展、社会 产业结构和生活方式的变革中的作用日益增长。据报道，世界国民生产总值增值部 分的6 5 与集成电路有关。集成电路行业对我国国民生产总值的贡献是计算机行业 的2 倍、钢铁行业的2 0 0 0 倍。集成电路技术已成为衡量一个国家科学技术进步和 综合国力的重要标志。大力发展集成电路产业，深入研究集成电路设计及其制造技 术，将会有力地推动我国信息产业的发展，对我国国民经济的发展具有极其重要的 意义。 自从1 9 5 8 年集成电路发明以来，为了提高电子集成系统的性能，降低成本，集成 电路的特征尺寸不断缩小，制造工艺的加工精度不断提高，同时硅片的相对面积不断增 大。4 0 多年来，集成电路芯片的发展基本上遵循了m o o r e 定律，即每隔三年集成度增 加4 倍，特征尺寸缩小了万倍。在经历t d , 规模集成( s s d 、中规模集成( m s d 、大规模 集成( l s i ) 、超大规模集成( v l s i ) 和特大规模集成( u l s i ) 阶段，进入了片上系统( s y s t e m o nc h i p s o c ) 的时代，微电子科学技术在短短半个世纪的时间里已经形成了一个有一千 五百亿美元的i c 产业。美国半导体工业协会s i a 组织给出了“1 9 9 7 年到2 0 0 9 年美国 集成电路工艺发展趋势”如表1 - 1 所示【。 表1 - 11 9 9 7 年到2 0 0 9 年美国集成电路工艺发展趋势 年份 1 9 9 71 9 9 92 0 0 12 0 0 32 0 0 62 0 0 9 工艺特征尺寸( r i m ) 2 5 01 8 01 5 01 3 0 1 0 0 7 0 最小线间距( r i m ) 3 4 02 4 02 1 01 7 01 4 01 0 0 晶体管数目( m ) 1 l2 14 07 6 2 0 05 2 0 芯片面积( r a m 2 ) 3 0 03 4 03 8 54 3 05 2 06 2 0 金属布线层数66 7 777 8 8 9 随着集成度的提高，芯片内部晶体管数目越来越多，集成电路设计的复杂度越 来越高，计算机辅助设计技术愈发变得重要。2 0 世纪9 0 年代初，电子系统设计自 动化( e l e c t r o n i cd e s i g n a u t o m a t i o n ，e d a ) 技术伴随着计算机、集成电路、电子系 统设计的发展，在经历了计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，简称c a d ) 之后， 华北电力大学硕士学位论文 进入了一个崭新的发展阶段。这一阶段就是以e d a 软件工具为开发环境，以硬件 描述语言为设计语言，以可编程器件为实验载体，以s o c 芯片为设计目标、以电子 系统设计为应用方向的电子产品自动化设计过程，包括系统综合、逻辑综合和物理 综合( 布局与布线) 。 1 1 2f p g a 的发展现状及趋势 f p g a ( f i e l dp r o g r a m a b l e g a t ea r r a y ) ，即现场可编程门阵列，是在可编程阵列逻 辑p a l ( p r o g r a m a b l ea r r a yl o g i c ) 、门阵列逻辑g a l ( g a t ea r r a yl o g i c ) 、可编程逻辑 器件p l d ( p r o g r a m a b l el o g i cd e v i c e ) 等可编程器件的基础上进一步发展的产物。它 作为专用集成电路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 ) 领域中的一种半定制 电路，既解决了定制电路的不足，又克服了原有可编程器件的门电路数有限的缺点， 能完成任何数字器件的功能，上自高性能c p u ，下至简单的7 4 系列电路都可以用 f p g a 实现。f p g a 工程师可以通过传统的原理图输入法，或是硬件描述语言自由 设计一个数字系统，利用e d a 工具进行仿真，可以达到事先验证系统设计的正确 性的目的。印刷电路板p c b ( p r i n t e dc i r c u i tb o a r d ) 等硬件电路设计完成以后，还 可以利用f p g a 的在线修改能力，随时修改设计而不必改动既定硬件电路。 使用f p g a 来开发数字电路，可以大大缩短设计时间，减少p c b 电路面积，提 高系统的可行性和稳定性。自1 9 8 5 年x i l i n x 公司推出第一片f p g a 芯片x c 2 0 0 0 己有2 0 多年的时间，在这2 0 多年中，f p g a 技术取得了惊人的发展。f p g a 从最 初的1 2 0 0 个可利用门，到现在数百万门的单片f p g a ，使得不同的硬件算法可以在 同一块芯片上实现，很多系统具有自恢复、自组织和自适应的功能 2 , 3 1 。由于f p g a 具有开发周期短、开发软件投入少、芯片价格不断降低等优点，尤其是其功能和性 能的快速提高，促使f p g a 越来越多地取代a s i c 市场，特别针对小批量、多品种 的产品需求，f p g a 已成为首选。在v l s i 设计仿真和验证阶段，必然会多次修改电 路和系统查错，利用f p g a 等可编程器件进行设计验证成为必然选择。 自从f p g a 问世以来，f p g a 布局研究一直是s o c 设计自动化研究的热点，有 很多大学、研究机构以及一些产品开发部门已经对此进行了相关研究。首先从工业 界而言，a l t e r a 与x i l n x 这两家大型f p g a 产商，有自己比较完善的布局算法，而 且在相应的软件开发工具i s e 和q u a r t e r 中都已经得到了较好的应用，但鉴于商 业用途，这些布局算法对外开放的比较少。而在国内，目前尚无成熟的f p g a 产业， 我国对自主产权的f p g a 的研究和设计仍处在开始阶段，工业界迫切需要针对我国 f p g a 发展的需求，研究相应的设计自动化技术，开发自动设计工具。鉴于以上原 因，本文研究课题是国家自然科学基金重大计划“半导体集成化芯片系统基础研究 下的一个重点项目“可编程可重构s o c 芯片系统结构及关键技术”( 9 0 6 0 7 0 0 1 ) 中的一 2 华北电力大学硕士学位论文 部分，对于发展我国自己的f p g a 产业，具有重要的意义。 1 2f p g a 的物理设计 f p g a 的设计流程遵循v l s i 设计流程模式，包括系统描述、功能设计、逻辑设 计、电路设计、物理设计、设计验证、芯片制造和测试封装【5 1 ，如图1 1 所示。整 个v l s i 设计流程是一个反复迭代的过程，如果进行到某个阶段不能完成就必须返 回到前面步骤重新设计。设计者应当尽量减少反复设计的次数以缩短产品进入市场 的时间。 图i - i 集成电路设计流程 物理设计是v l s i 设计中重要的一环，也是v l s i 设计中最费时的一步，它的质 量很大程度上决定了电路的性能。在物理设计中，输入是电路元件说明和网表，输 出是设计好的版图。由于物理设计过程复杂，通常将其分为多个子模块进行，包括： 划分( l o g i cp a r t i t i o n i n g ) 、布图规划( f l o o 叩l a n n i n g ) 、布局( p l a c e m e n t ) 、布线( r o u t i n g ) 和压缩( c o m p a c t i o n ) 。划分将电路分为几个子部分，布图规划将这些子部分进行安 放，布局为电路中的模块寻找合理的位置，布线则得到所有互连线的确切位置，最 后通过压缩以减小芯片面积。 布局是物理设计中极为重要的一步，它的性能很大程度上决定了后续过程的设 计质量。布局通常分为两个阶段：总体布局和详细布局。总体布局中为电路元素安 排一个全局合理的相对位置，详细布局中电路元素被分配到具体位置并满足布局模 式要求。布局的目标很多，包括减小芯片的总线长、芯片面积、最大时延、减小芯 3 华北电力大学硕士学位论文 片拥挤度等等。 1 3 本文的研究内容及贡献 本论文的研究是在清华大学e d a 实验室完成，基于国家自然科学基金的重大 研究计划重点项目“可编程可重构s o c 芯片系统结构及关键技术 课题。该课题主 要研究内容包括：混合可编程可重构s o c 体系结构；互连结构设计和优化； 性能和功耗驱动的系统划分及综合技术研究：面向混合可编程阵列的布图优化技 术；开发环境和设计环境等几方面内容。 本课题“可布性驱动的层次式f p g a 布局算法”属于研究内容的第二条和第五 条，本论文作者所在课题组为布局( p l a c e m e n t ) 工作组。课题主要参与布局模型的 提出和布局算法的研究，需要从以下五个方面入手工作： ( 1 ) 了解布局算法的基础知识，掌握国内外的研究情况，对布局模型进行深 入分析和研究。 ( 2 ) 针对层次式f p g a 结构的特点，详细分析和研究其系统结构及可提取的 数据结构，期望提出一个通用的层次式f p g a 的系统结构作为布局的模型。 ( 3 ) 期望能够在通用的层次式布局模型的基础上，提出在布局算法中可以采 用的数据结构，并且实现满足多种驱动要求的布局算法。 ( 4 ) 对布局算法的结果进行分析，提出改进方案 ( 5 ) 生成布局文件，为下一步的布线工作建立接口。 围绕工作组的工作要求，本文主要做出了如下贡献： ( 1 ) 打破了以往固定格式的f p g a 结构，提出了一种通用的层次式f p g a 结 构及布局模型，并且给出了通用结构之间的数学计算公式，增强了代码对不同芯片 结构的通用性。 ( 2 ) 在国内，首次提出将层次转化为线长的方法。利用确定初步走线的方式， 实现高精度的可布性控制的布局算法( v p h ：a v e r s a t i l er o u t a b i l i t y d r i v e np l a c et o o l f o rh i e r a r c h i c a lf p g a s ) ，已经发表在了2 0 0 7 的c a d c g 会议上。 ( 3 ) 提出利用矩形的对角线层次来代替线长，从而实现在优化线长的同时真 正提高布通率的布局算法( w - v p h ：e f f i c i e n tw i r e l e n g t hd r i v e np l a c ea l g o r i t h mf o r v e r s a t i l eh i e r a r c h i c a lf p g a s ) ，该算法已经应用在了后续的项目中，并且取得了理想 的效果。 ( 4 ) 为下一步的布线工作建立了良好的接口，并且完成了初始布线的工作。 4 华北电力大学硕士学位论文 1 4 论文的组织结构 论文共分为六章，其内容组织如下： 第一章，引言，阐述课题的背景、意义和目标，以及论文完成的工作。 第二章，不同的f p g a 结构对f p g a 布局的影响，提出了一种通用的层次式 f p g a 结构及布局模型，并且给出了通用结构之间的数学计算。 第三章，拥挤度驱动的布局算法研究，分析了目前常见的布局算法在本论文中 的存在形式，归纳目前几种主要的预估拥挤度的模型，提出层次式f p g a 的拥挤度 模型，分析降低拥挤度的几类有效策略。 第四章，提出并实现一种应用于f p g a 布局的高精度布局算法，即v p h 算法， 并且分析了布局过程，给出实验数据并对结果进行分析。 第五章，提出并实现一种应用于f p g a 布局的快速对角线布局算法，即w v p h 算法，而且分析了布局过程，给出实验数据并对结果进行分析。 第六章，对整个论文进行了总结，已提出的通用的层次式f p g a 结构及其对应 的布局算法，提升了我国在芯片技术的研究和应用上的水平。进一步展望了未来的 研究前景。 5 华北电力大学硕士学位论文 第二章通用的h f p g a 结构及布局模型 f p g a 的结构有多种，比如：对称式的( s y m m e t r i c a la r r a y ) 、基于行结构的 ( r o w b a s e d ) 、门海式的( s e a o f - g a t e s ) 及层次式的( h i e r a r a c h i c a lf p g a ) 等【6 】。相 对于其他结构而言，层次式的f p g a 在速度和面积方面有更好的性能【7 】。 本章首先介绍几种现有的而且也是极为普遍的f p g a 结构，而后给出布局的模 式；第二节简要介绍一下层次式f p g a 在各国的研究概况；第三节重点介绍本课题 所提出的通用层次式结构及布局模型，以及相应的数学说明。 2 1 目前常见的f p g a 结构及布局模式 表2 1 给出了目前世界上几家著名的f p g a 芯片生产厂商的具有代表性的 f p g a 结构，而图2 1 分别给出了这四种结构的具体表现形式以及它们的布线资源 分布，其中( a ) ( b ) ( c ) ( d ) 分别为对称型结构、行排列结构、门海结构和层次结构。 表2 - 1 常见的商业芯片 公司可编程逻辑器件结构逻辑模块类型编程技术 典型产品 a c t e lf p g ar o w b a s e d m u l t i p l e x e r a n i t i f u s ea c t 3 l u c e n tf p g a s y m m e t r i c a la r r a yl o o k - u pt a b l e s r a mo r c a 3 m o t o r a l af p g ah i e r a t c h i c a lb a s i cg a t e ss r a mm p a l 0 0 0 q u i c k l o g i c f p g a s y m m e t r i c a la r r a ym u l t i p l e x e r a n i t i f u s e p a s i c 2 s y m m e t r i c a la r r a yl o o k u pt a b l e s r a mx c 4 0 0 0 x i l i n xf p g a s e a - o f - g a t e m u l t i p l e x e r s r a m x c 6 2 0 0 s e a - o f - g a t e b a s i cg a t e sa n i t i f u s e x c 8 1 0 0 2 1 1 对称型f p g a x i l i n x 公司的x c 4 0 0 0 系列是对称型f p g a 的典型代表，其结构如图2 1 ( a ) 所示。 对称型结构的f p g a 是目前学术界研究最多的一种结构，又称为孤岛型结构 ( i s l a n d s t y l ef p g a ) 。本文中，在提到非层次式的f p g a 结构时，若没有特别申明， 都表示为这种i s l a n d s t y l ef p g a 。 6 华北电力大学硕士学位论文 ff lf f 卜jlj il r o u t i n gr e s o 喇 o v e r l a y e do n l o g i cm o d u l e s ( i ) 对称型结构l o g i cm o u d l e( b ) 行捧列结构 l o g i c m o d d e 卜i (c)门海结构d)层次结构 图2 1 四种主要的f p g a 结构 r o u t i n g c h a r m e l r ，一 。凡、 r o u t i n g c 1 1 a n n d r 一一 对称型结构的f p g a 包含了行排和列排的逻辑单元c l b ( c l u s t e r e dl o g i cb l o c k ) ， 水平和垂直的布线通道包含不同长度的布线段。对称型结构在基于s r a m 编程方式 的f p g a 中较为常见，s r a m 单元通过控制连通晶体管( p a s st r a n s i s t o r ) 达到线间互 连的目的。理想情况下，在每一个开关模块( s w i t c hb o x ) d e ，对称型结构的f p g a 应 该能够为任何两个布线轨道( t r a c k ) 在交汇处提供一个连接开关：同样也应该能够在 布线通道( c h a n n e l ) 上为逻辑模块( 1 0 9 i cb l o c k ) 的每个引脚( p i n ) 与布线通道的连接提供 连接开关。事实上，由于f p g a 的结构越来越紧凑，信号通过晶体管电容性负载等 因素的影响，并非布线通道中的每一个轨道都能够和逻辑模块的每一个引脚进行连 接，所以考虑到布通率时就要有一个误差值。 对称型结构的f g p a 所体现出来的特点决定了其在布局时将受到一定的约束。 对于待布的线网网表，布局通道上有限的开关数目限制了逻辑模块各个引脚到布线 轨道之间的连接；开关模块处有限的连接方式限制了c l b 布局时的布通率。 总之，对称型的f p g a 布局问题不能够简单地分割为空间问题( 在典型的门阵列 布局中，可分成几个独立的问题) 。针对这种结构的布局算法必须要同时考虑c l b 单元所在位置周边的通道选择和通道中的线轨选取。 2 1 2 行 4 列f p g a a c t e l 公司的a c t z 系列是行排列结构f p g a 的典型代表。行排列结构f p g a 7 华北电力大学硕士学位论文 主要是通过反熔丝实现连接。反熔丝是一种一次性编程器件，大电流通过时导通。 反熔丝尺寸小，电容低，使用较自由，f p g a 可以在每一个水平或垂直线段的交汇 处使用。除其尺寸小之外，反熔丝还具有很好的连续阻抗特性，因此各种分段的通 道可以连接构成不同长度的布线通道，这就是行排列结构的f p g a ，又称为分段通 道式的f g p a 。 如图2 1 ( b ) 所示，行阵列中每一行都有标准单元组成，这些单元的逻辑功能、 电路性能及几何设计规则都经过验证和分析。行与行之间是称之为通道的布线区。 同行或相邻两行的单元互连可通过单元行之间的上或下通道或相邻两行之间的通 道进行连线完成。 2 1 3 门海式f p g a x i l i n x 公司的x c 6 2 0 0 系列是门海结构f p g a 的典型代表。与行结构的f p g a 相比较，门海阵列进一步改进了宏单元阵列的版图结构，如图2 1 ( c ) 所示。它 取消了水平方向上的通道，成为一种无通道的门阵列。阵列上一些区域为功能块区， 其他区域为布线区。门海模式的功能块大小、形状和位置都比较灵活，允许在f p g a 设计中嵌入其他的硬核，在这类其他硬核嵌入的应用中有广泛的用途。 层次式结构的f p g a 将在下一节重点研究。 2 1 4 布局模式 布局问题就是基于给定的输入、输出和电路的连接关系，把单元安放在芯片的 适当位置上并满足一定的目标函数。布局阶段的输入是一组模块、网表和模块上的 引脚信息，输出是所有模块的坐标。f p g a 布局用于决定每个逻辑块的物理位置， 图2 2 说明了一个电路网表映射到f p g a 中的过程。典型的布局工具应该努力达到 以下目标： 最小化逻辑块之间互连的连线数。 平衡使用交叉的f p g a 的布线以避免拥塞。 放置时间比较关键的逻辑块尽可能靠近，以优化关键路径的时延。 8 华北电力大学硕士学位论文 电路网表 映射至w j f p g a 图2 - 2 电路网表到f p g a 映射过程 f p g a 的整体架构会对布局布线效率产生很大影响。j r o s e 等人将每个c l b 所 能连接的线道数定义为连通模块的布线灵活度f c ，将开关模块引出端所能连接到其 他引出端数目定义为开关模块布线灵活度f s ，他们的实验结果表明，f s = 3 的开关模 块配以高灵活度的连通模块是较好的选择，能获得最少的布线开关总数【6 】。连通模 块和开关模块内开关分布的拓扑结构对布通率的影响很大，d f w o n g 等人对开关模 块拓扑结构进行了深入研究，提出了用最少开关构造通用开关模块( u n i v e r s a ls w i t c h m o d u l e ，u s m ) 的算法，并基于网络流理论分析了开关模块的可布通性【8 】。对于每边 都有w 引出端的方形开关模块，如果对于任何不超过模块引出端的网线均能布通， 就称之为u s m 。但这些研究都基本上仅限于普通的非层次式f p g a 结构，也就是 i s l a n d s t y l ef p g a 结构。然而随着目前研究的深入发现相对于其他结构而言，层次 式的f p g a 在速度和面积方面有更好的性能，所以本文将在借鉴i s l a n d s t y l e 研究成 果的基础上，把重点放在研究层次式的结构上。 2 2 层次式f p g a 结构 已有的研究认为，和经典的f p g a 相比，层次式f p g a 能够更充分地利用电路 的局部性原理，所以具备更好的硬件描述能力，即能以较少的交换开关完成等同的 电路连接关系。层次式f p g a ( h f p g a ：h i e r a r c h i c a lf p g a ) 自从上世纪9 0 年代以 来，一直是s o c 设计自动化研究的热点，已经有很多大学、研究机构对此进行了相 关研究，为f p g a 的发展做出了贡献。下面是目前已有的主要研究情况。 加拿大的t o r o n t o 大学【9 】【1 0 】【1 l 】和g u e l p h 大学【1 2 】：d a v i dm l e w i s 等人基于 类似图2 - 31 9 】所示的结构进行研究。该研究包含与布局相关方向两方面的内容。一部 9 华北电力大学硕士学位论文 分是布局前期的研究：自顶向下的二分法的划分，与以往的划分法相比较，该方法 重视的是一个划分的总体结果，即每一层进行递归划分后的结果，而不是各个层面 上的划分结果；另一个研究为时间驱动的布局算法( t d p i a c e m e n t ：t i m i n gd r i v e n p l a c e m e n t ) ，在最小割的算法基础上，引入了时间花费函数。 洲1o a u 啪l l i 蛔i c b b c k l 妇删0 ) g i o b a if b v 3 o k a n n e i 。 国j殴冱j 圆 鳓j蹬避j嘲迫垣j 图 图2 - 34 宰2 ( 2 + 2 ) 的h f p g a 示例 l e v e l l 8 l o c k 咖1 2 b b 啪 e o n n o a i o n b o x 美国的u c s b 大学【1 3 1 和s o u t hf l o r i d a 大掣1 4 】：a m i ts i n g h 等人在基于r e n t 规则的基础上进行了结群，在此结群的基础上利用模拟退火算法进行层次式f p g a 布局，可以有效的节约面积资源【”l 。l ih a o 等人在基于x i l i n xv i r t e xs e r i e s 结构的基 础上进行了研究【1 4 1 。 台湾的n a t i o n a lc h e n gk u n gu n i v e r s i t y 大学1 5 】i l6 】【1 7 1 和台湾n a t i o n a lt s i n gh u a u n i v e r s i t y 大学【1 8 】以及台湾的s o u t h e r nt a i w a nu n i v o f t e c h n o l o g y 大学【1 9 】。y e n t a i l a i 和p i n g t s u n gw a n g 等人对层次式f p g a 结构的提出与发展做出了重要的贡献， 而且给出了合理的实验值，每种层次式f p g a 结构都为当时的研究提供了很大的借 鉴。文献【1 8 】重点对结群进行了研究。 研究现状表明，通用性的h f p g a 算法很少，绝大部分的研究基于a l t e r a 和x i l i n x 这些产品结构，不能直接移植到新的产品结构上。尤其是在国内，基本上没有公开 发表过的通用性结构的算法，使得本文有极大的研究空间。 1 0 华北电力大学硕士学位论文 2 3 通用层次式f p g a 结构及布局模型 2 3 1 通用层次式f p g a 的结构特点 在研究了已有的层次式f p g a 结构的基础上，本文提出了一个通用的h f p g a 结构，如图2 4 所示。它的基本组成为可编程逻辑单元c l b s ( c l u s t e r e dl o g i cb l o c k s ) ， 开关模块( s w i t c hb o x ) 和输入输出模块( i op a d s ) 。c l b s 是核心的逻辑模块，可 以通过自己的输入输出端口与s w i t c hb o x 和i op a d s 相连接；而s w i t c hb o x 是布线 资源，每个s w i t c h b o x 有固定数量的引脚( p i n s ) 与其他s w i t c hb o x 和c l b s 相连， s w i t c hb o x 根据线路的连接方向，又细化为向上的连接通路( u ps w i t c hb o x ) 和向下 的连接通路( d o w ns w i t c hb o x ) ；i op a d s 负责芯片的输入输出。 图2 _ 4 通用的h f p g a 结构图 这种结构可以表示成一个k i n 的层次式构造。n 代表着电路芯片总的层次，第 i t h 层的结群中包含有k i 个子结群，每一个子结群再分为r i 行和c i 列。区别于 以往的研究结构，对于芯片中不同的层次，k i 的值可以不同，这种结构具备了极大 的灵活性，可以更好的满足用户的需求。一个n 层的h f p g a 可以包含有 硒幸k 1 奎k n - 1 个c l b s 。假设每一层的层次用l ( o = l = n 1 ) 表示，最高层的结群 表示为n 1 ，这样最高层n 1 层就包含了所有的c l b s ，而且可以进行k n 1 的划分， 从而划分为有k n 1 个n 2 层的结构，依次类推到最后的第0 层时，表示一个具体的 c i b 。 华北电力大学硕士学位论文 2 3 2 层次式f p g a 布局模型 采用了h f p g a 后，使得布线变得简单起来，布局算法变得重要起来。布局的 结果要求布置好的逻辑单元之间的逻辑关系尽可能的接近于器件中单元的连接关 系。如果目标电路也能整理出一颗树型结构出来，它应该和器件本身的数型结构尽 可能的相似。只有这样，才有可能充分利用h f p g a 的层次结构，不至于产生大量 的跨越模块之间的连线请求。 在提出h f p g a 结构的基础上，本文提出了布局模型为双子树结构。即数据的 下行网络和上行网络都是一颗胖树，上行网络中的节点簇与上一级下行网络对应的 节点簇之间可以进行任意的全连接，如图2 5 。 图2 5h f p g a 双子树布局模型 最低层也就是零层的c l b 可以通过第一层向上的u ps w i s h b o x 连接到其它的s w i t c h b o x 上或者连接到其它的c l b 上，第一层的s w i t c hb o x 可以通过向上的u ps w i t c hb o x 连 接到第二层的s w i t c hb o x 或者通过向下的d o w ns w i t c hb o x 连接到第零层c l b 上。依次 类推，最上层的s w i t c hb o x 将会只有向下的d o w ns w i t c hb o x 用来连接它的下一层，而没 有向上的u ps w i t c hb o x 。理论上来说，最上面一层的s w i s hb o x 可以通过自己的d o w n s w i s h b o x 向下连接到每一个c l b 上，所以最上一层的s w i t c h b o x 数目是最多的，而后 依次是次高层，第一层的s w i t c hb o x 个数最少。 2 3 3h f p g a 布局数学拓扑关系 层次式f p g a ( h i e r a r c h i c a lf p g a ，h f p g a ) ，顾名思义，就是基本的逻辑单 元的组织方式不再是一种平面的二维网格结构，而是从上到下构成一种层次结构。 h f p g a 的逻辑关系，与数据结构中的“树”非常类似，所以，大多数层次式f p g a 的 描述和研究也选用“树”作为数据结构而开展研究。然而作为数结进行研究，真正实 1 2