datasheet
超过460,000+ 应用技术资源下载
pdf

FPGA布线研究与实现

  • 1星
  • 日期: 2014-03-05
  • 大小: 2.28MB
  • 所需积分:1分
  • 下载次数:10
  • favicon收藏
  • rep举报
  • 分享
  • free评论
标签: FPGA

现场可编程门阵列(FPGA)能够减少电子系统的开发风险和开发成本,缩短上市时间,降低维护升级成本,故广泛地应用在电子系统中。最新的FPGA都采用了层次化的布线资源结构,与以前的结构发生了很大的变化。由于FPGA布线资源的固定性和有限性,因此需要开发适用于这种层次化的FPGA结构并提高布线资源有效利用率的布线算法。同时由于晶体管尺寸的不断减小,有必要在FPGA布线算法中考虑功耗和时序问题。 本论文所作的研究工作主要包括:提出一种基于Tile的FPGA结构描述方法,对FPGA功耗模型和时序模型进行了研究,实现了考虑FPGA功耗、布线资源利用率的布线算法。 在FPGA结构描述方面,本文在分析现代商用FPGA层次化结构及学术上对FPGA描述方法的基础上,提出一种基于Tile的FPGA结构描述。由于基本Tile的重复性,采用该方法可以简化FPGA结构的描述,同时由于该方法是以硬件结构为根据,为FPGA软硬件提供了简单而灵活的接口,该方法在原型系统中测试证明是正确的。 在FPGA功耗模型方面,本文研究了ASIC中关于电路功耗计算的基本方法,并将其应用到FPGA功耗分析中。在模型中的采用了混合的功耗模型,包括动态功耗模型和静态功耗模型。动态功耗的计算采用基于节点状态转换率的开关级动态功耗计算和逻辑块宏模型,静态功耗则采用基于公式计算的晶体管漏电功耗模型和逻辑块基于仿真的LUT/MUX表达式计算模型。这些功耗模型将运用到我们后面的功耗计算和基于功耗驱动的布线算法中。 在FPGA布线算法研究和实现方面,本文在介绍基本的搜索算法之后,介绍了将FPGA硬件结构转变为FPGA布线程序可识别的布线资源图的方法,并将基本的搜索算法运用的FPGA布线资源图上,实现FPGA的基于布通率的布线算法。在此基础上,借鉴了FPGA时序分析方法,将时序分析作为布线算法的一子模块,对基于时序的布线算法进行了研究;同时采用了FPGA功耗模型,在布线算法实现中考虑了动态功耗的问题。最后在布线算法中实现两种启发式策略以提高可布线资源有效利用率。

复旦大学 硕士学位论文 FPGA布线研究与实现 姓名:胡欣 申请学位级别:硕士 专业:微电子学与固体电子学 指导教师:来金梅 20070522 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特另Ⅱ加以标注和致谢的地方外,不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 R期 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定,即:学校有权保留 送交论文的复印件,允许论文被查阅和借阅;学校可以公布论文的全部或部分内 容,可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 群 作者签名 政 z 6 07.‘,,, 摘要 摘要 现场可编程门阵列(FPGA)能够减少电子系统的开发风险和开发成本,缩短 上市时间,降低维护升级成本,故广泛地应用在电子系统中。最新的FPGA都采用 了层次化的布线资源结构,与以前的结构发生了很大的变化。由于FPGA布线资源 的固定性和有限性,因此需要开发适用于这种层次化的FPGA结构并提高布线资源 有效利用率的布线算法。同时由于晶体管尺寸的不断减小,有必要在FPGA布线算 法中考虑功耗和时序问题。 本论文所作的研究工作主要包括:提出一种基于Tile的FPGA结构描述方法, 对FP6A功耗模型和时序模型进行了研究,实现了考虑FPGA功耗、布线资源利用率 的布线算法。 在FPGA结构描述方面,本文在分析现代商用FPGA层次化结构及学术上对FPGA 描述方法的基础上,提出一种基于Tile的FPGA结构描述。由于基本Tile的重复性, 采用该方法可以简化FPGA结构的描述,同时出于该方法是以硬件结构为根据,为 FPGA软硬件提供了简单而灵活的接口,该方法在原型系统中测试证明是正确的。 在FPGA功耗模型方面,本文研究了ASIC中关于电路功耗计算的基本方法,并 将其应用至UFPGA功耗分析中。在模型中的采用了混合的功耗模型,包括动态功 耗模型和静态功耗模型。动态功耗的计算采用基于节点状态转换率的开关级动态 功耗计算和逻辑块宏模型,静态功耗则采用基于公式计算的晶体管漏电功耗模型 和逻辑块基于仿真的LUT/MUX表达式计算模型。这些功耗模型将运用到我们后面 的功耗计算和基于功耗驱动的布线算法中。 在FPGA布线算法研究和实现方面,本文在介绍基本的搜索算法之后,介绍了 将FPGA硬件结构转变为FPGA布线程序可识别的布线资源图的方法,并将基本的搜 索算法运用的FPGA布线资源图上,实现FPGA的基于布通率的布线算法。在此基础 上,借鉴了FPGA时序分析方法,将时序分析作为布线算法的一子模块,对基于时 序的布线算法进行了研究;同时采用了FPGA功耗模型,在行线算法实现中考虑了 动态功耗的问题。最后在布线算法中实现两种启发式策略以提高可句线资源有效 利用率。 关键字现场可编程门阵列;功耗模型;布线算法;集成电路计算机辅助设计 中图分类号TN402 第1页(共91页) Abstract Abstract FPGA,Field programmable logic array,can reduce the NRE cost,design risk,Time—tO—Market and maintenance cost of electronic system.Therefore。 FPGA is widely used in electronic systems.The latest FPGA architectures have hierachical routing resources different from the former generations. Since routing resources in FPGAS are fixed and limited.it is very important for the routing algorithms to fully exploit the new architectures and improve the efficient utilization of routing resources. Meanwhile,with the scaling down of transistor,it’S necessary to consider the power and timing in the FPGA routing algorithms. This thesis works on the method of FPGA architecture description based on the Ti le.The research and development on FPGA routing algorithms considering the FPGA power,timing and the efficient utilization of routing resources are also included. After analyzing the commercial FPGA and the academic architecture with hierarchical routing resource,the method of arch—description iS established with the basic Tile.Since the repeatability of the basic Tile, it’S easy to describe the FPGA arch.At the same time,thiS method provides a simple,flexible and improved interface between FPGA hardware and software,as the descript ion is L嫩sed on the hardware archi tecture.The method is belieyed to be feasible in the current prototype. In the FPGA power model,the author studies on the ASICs’power and applies the power model to FPGA power analysis.The mixed—level power model iS used to consider both dynamic and static power.It combines switch—level models for interconnects,macro-models for logic block,and the formula calculation for the transistor leakages and simulation—based LUT/MUX leakages’calculation.The power model is used in the later FPGA power—driven routing algorithm. The thesiS also focuses on the research and implement of FPGA routing algorithm.The author giyes an introduction to the basic search algorithm firstly,and then presents the method of how to convert the FPGA hardware architecture to the routing resource graph used in the software.The FPGA 第2页<共91页) Abstract routability—driven routing is implemented in the routing resource graph. Using the timing—analyzer as a sub—module in the routing algorithm, improvement of the timing~driven routing is studied,and power—driven routing using the FPGA power model is realized in the algorithm.In the end,two dynamic weight update based heuristics are introduced to achieve the efficient utilization of routing resources. Keywords FPGA;Power model;Routing algorithm;ICCAD 第3页(共91页) 第1章引言 第1章引言 1.1现场可编程逻辑阵列FPGA 1985年,Xilinx公司推出了世界上第一块现场可编程门阵列(FPGA field programmable gate array)芯片,可以方便地通过下载不同的配置位流文件(bit stream)而实现不同逻辑功能。由于FPGA能够减少电子系统的开发风险和开 发成本(NRE): 缩短上市时间(time to market);通过在系统编程、远程在线 重构等技术降低维护升级成本,因此在通信、控制、数据计算等领域得到了广泛 的应用。 FPGA能够很好的利用最为|;{『沿的制造工艺和封装工艺,并通过全定制的电 路和版图设计方法优化设计,因此FPGA的逻辑密度、性能、功能和功耗都已经 得到大幅改进,成本显著下降。目前,芯片的集成度已达到1000力.等效门、速度 可达至t]400一一500MHz【1][21,在制造上采用了90rim、9层铜连线工艺【3】,并且应 用新的封装技术提供了数千管脚的FPGA芯片。 随着FPGA在功能、密度、速度上的不断提升和成本的降低,以及用户需求、 协议标准等的变化越来越快,FPGA芯片不但被用柬制作原型机,而且还被大量 地应用到网络、消费电子、科研、航天及国防的许多最终产品中,成为一系列电 子系统的核心。f4]qh指出,在上市时间、成本、高集成度和灵活度方面FPGA明 显优于专用集成电路(ASIC。application specific integrated circuit),而根据业界 通用的标准判断,最适合使用ASIC的情况是:门和储存位的数量超过两百万门、 千兆位:在最低功耗下,主时钟频率高于300MHz;对成本很敏感的应用。 另一方面,基于FPGA的SOPC(可编程片上系统)与传统的SOC相比,具备 很多优点,如设计周期短、产品上市速度快,设计风险和设计成本低、集成度高, 灵活性大,维护和升级方便,硬件缺陷修复和排除简单等,开始成为设计者的新 宠,并逐渐蚕食传统SOC的领地f51。 1.2 FPGA软件系统 FPGA软件系统又称为FPGA计算机辅助设计(Computer Aided Design,CAD) 系统,是指对应于FPGA硬件结构的一整套软件的流程[6],以实现电路设计人员 完成电路前端设计(包括硬件描述语言HDL、原理图等设计方法)并将电路设计 第6页(共91页) 第1章引言 下载到相应的FPGA芯片中。 如图卜1为FPGA的基本硬件结构[7],包括实现逻辑功能的逻辑块LB(Logic Block),输入输出引脚IOB(I/O Block)和用于连接各个逻辑块『自J引脚的布线资 源(Routing Resource)。 口口 口口……口口 口口 r--i 影孑口…·口[3 Routing 言B口….口 Resoul:ce : ; : : 口广] 口L.J 口…·口 零"*,l ; i ogic 醛: 昌口口…·口 口口 口口……口口 图I-I FPGA基本硬件结构 口r10呔 口口 FPGA软件系统流程一般包括设计输入、逻辑综合、功能仿真、映射、布局、 布线、时序验证、编程下载等过程,如图卜2所示。 第7页(共91贞) 第1章引言 图卜5 FPGA软件系统流程 原理图输入、逻辑综合、功能仿真等部分和一般电子线路设计一样,只是对 特定可编程逻辑器件厂家的特定型号器件,最好使用特定的元件库,如不使用特 定元件库,有些厂家的软件也可以通过EDIF格式文件和元件库映射来完成第三 方软件到可编程逻辑器件软件的衔接。元件库中有许多功能宏块(如加法器、乘 法器、比较器、计数器、译码器等),应尽量使用这些现成的功能宏块。 电路设计及功能仿真完成,确信电路正确后,进行逻辑映射即Mapping。逻 辑映射将电路中的元件映射到目标FPGA的逻辑块之中,基于逻辑块数目的映射 将尽量减少使用的逻辑块数目,而优化时延特性的映射将尽量减少信号经过的逻 辑块的数目。 布局阶段将各LB和10B放到适当的位簧。一般情况下,由于可编程逻辑器件 布线资源的有限性,布局阶段的优化目标首先是布通率,通道密度的均匀性。但 第8页(共91页) 第l章引言 是实用中还有一些其它问题要考虑,例如用户对某些路径的时延提出限制,或指 定一些线网的重要程度,或要求管脚锁定。这样布局算法就要综合考虑。由于各 种约束条件和布通率之间是存在矛盾的,怎样兼顾各方面的要求又能最大程度的 提高布通率是一个很值得研究的方向。 布线阶段实现LB之间的连线。布线要求百分之百的布通率,否则就是布图失 败。因为可编程逻辑器件布线资源的特殊性——稚线资源都已确定,布线实际上 只是确定哪些编程点接通而哪些不接通。由于可编程逻辑器件布线资源的有限性 和多样性,其布线算法也有特殊性,与普通的布线算法有很大的不同,相应的也 有许多值得研究的问题。 布线完成以后,各路径的时延值才能最后确定。这时,需要进行时序验证, 以检查电路在有时延的情况下工作是否正常。如j下常,进入下一步编程下载;如 不正常,需仔细检查各相关点,找出问题所在,用适当的方法解决(如加入时延 约束、关键线网、调整线网的重要程度、指定某些逻辑单元的位置,或人工干预, 拆除某些线网、移动某些逻辑单元、重新布线等)。 时序验证确证无误,进行FPGA编程点的值的确定即位流生成,再进行编程下 载。通过编程器将编程信息固化在可编程逻辑器件的某种存储介质上。 时延约束和其它约束(如管脚位置约束等)将根据需要,在设计的各实现阶 段产生作用。 1.3主要研究和工作内容 本论文所作的研究工作是:提出一种基于Tile的FPGA结构描述方法,对FPGA 功耗模型和时序模型和FPGA布线算法进行了研究及实现。研究及工作内容主要包 括如下几个方面: 第一、作者在研究商用FPGA结构和学术常用的FPGA结构的基础上,在了解学 术FPGA结构描述的方法后,提出一种基于Tile的FPGA结构描述方法,该方法可以 使FPGA的结构描述和硬件结构相对应起来,有利于FPGA软硬件结构的同步升级。 第二、作者同时研究了ASIC中常用的功耗分析方法、时序分析方法和FPGA布 线算法,并将功耗分析和时序分析方法应用到FPGA布线算法中,实现FPGA的功耗 分析:并引入可分割线网利用率的概念,通过改进FPGA布线算法,完成基于功耗 驱动、时序驱动及提高线网有效利用率和长线有效利用率的FPGA布线算法。 第9页(共91页) 第1章引a 1.4论文组织 本文的结构如下:在第2章中对FPGA布线资源结构的技术背景进行简述,包 括经典的岛式结构和层次化结构,并对逻辑单元结构和基本互连结构进行了介 绍。第3章介绍了在FP(;A布线模块中用到的FPGA结构描述方法一基于Tile的 FPGA结构描述。第4章介绍了FPAG的功耗模型,包括FPGA中的动态功耗和静态功 耗的计算方法。第5章介绍了在FPGA省1/线中所采用的时延模型,包括基于查找表 的逻辑块内部时延模型和基于RC网络的Elmore模型。第6章介绍了基本的FPGA布 线算法一一基于布通率的布线算法,和基于时序驱动、功耗驱动及提高线网利用 率的改进型FPGA御线算法。第7章和第8章分别为结果测试和工作总结并提出了未 来进一步工作的方向。 第10页<共9l焚) 第2章技术背景 第2章技术背景 FPGA的硬件整体结构如图1·1所示,主要有三大组成部分:逻辑块(Lo#c block,LB),用束实现用户电路的逻辑功能;连线资源(Routing Resource),用 来提供逻辑块间的连接关系;输入输出块(I/O Block),用来让用户定义输入输 出信号。 2.1 FPGA整体结构 2.1.1经典对称式结构【8】 FPGA的整体结构确定了器件中的各个可编程功能模块如何组织在一起。 图2-1所示是“经典的”对称式FPGA结构,该结构最早由J.Rose等人提出 【71,由可编程逻辑单元(图中L所示)、连接盒(ConnectionBox,图中c所 示)、开关盒(Switch Box,图中S所示)以及连接它们的会属线组成。可编 程逻辑单元能够实现一定的逻辑函数,连接盒将可编程逻辑单元的输入输出 连接到会属线上,开关盒在不同的金属线之间进行连接。 口口口口口口口口口口口口 L E刍cE刍L E刍CE刍L C目S目C目S目C S E爿cE爿L E爿CE爿S cE爿S目C目S E爿C L目C目L E剖C目L 口口口口口口 口口口口口口 口口口口口口口口口口口口 图2-1经典对称式FPGA结构 图2-1对称式结构是一种平面化的结构,其中所有可编程功能模块都在同 一个层次上进行组织。这种结构得到了最多的关注,多数FPGA结构的研究 在这样的结构框架下进行。它灵活性好,在不同应用领域中都能得到比较好 第11页(共91页) 第2章技术背景 的面积利用率而且与这种结构的FPGA结构相配合的FPGA CAD软件 【91110111111121也较为简单,但是速度性能相对较差。 2.1.2层次式结构 层次式的FPGA结构[1][21113][141如图2.2中所示,是通过分层的方法组 织可编程功能模块,层次式结构为本文的目标结构。每一个层次的可编程逻 辑单元都由低一层次上的若干可编程逻辑单元和可编程互连资源构成,整个 器件由最顶层的可编程逻辑单元、可编程连接线和可编程IO组成。这种结构 速度性能较好,在FPGA的规模很大时也能够方便CAD软件对可编程功能模 块进行处理,所需的软件也较为复杂。 圄h虱一口口口二口口口一一口毋口二口~口一 一旧旧旧£旧旧旧~一口~口二口~口一一口口口二口口口一 同同 lJ口 吕口 吕口 吕I|Il口 吕口 吕口 吕II 同同 l口口口I I口口口I 园m园 一口口口二口口口一一口~口二口~口一 一旧旧旧[旧旧旧一 一口口口=口口口一 l口口口I l口口口l =jLevel=2= l口日口I I口曰口I I口口口I I口口口I 画画 图2.2层次式FPGA结构 图2.2中共3个层次,第一层Level 1互连为最基本的逻辑块之『自J的互连 关系,第二层逻辑单元由多个第一层基本块构成,第二层逻辑单元之间的互 连形成Level 2互连,第三层由最顶层的可编程逻辑单元、可编程互连及可编 程lO组成,其中可编程互连构成这种层次化的Level3互连。 第12页(共9l页) 第2章技术背景 2.2 FPGA可编程逻辑单元结构 FPGA技术中,可编程逻辑单元LC(Logic Cell)的结构非常多,但典型 地可分为基于多路选择器MUX(Multiplex)【15】、基于查询表LUT(Look—Up Table)、基于与阵歹lJ[161=类。uC是实现逻辑功能的核心,对其研究一般都要 考虑芯片面积利用率、速度、函数实现能力及有利于算法实现等几方面因素。 本文对应的目标硬件结构中LC是采用查询表LUT结构。 2.2.1查询表LUT结构 查询表LUT结构由XilinxTM公司最早提出,并把这种LUT加入到它们的 产品中,提出了基于LUT的可配置逻辑块CLB(Configurable Logic Block) 结构。UJT在原理上可以把它看作一个按位寻址的SRAM,其输入端相当于 SRAM的地址。一个n输入的查询表是由2n×1个SRAM单元组成,n个输 入通过译码电路来决定从哪一个SRAM单元读出信息送到输出端,而SRAM 单元则按地址顺序记录函数的真值表。n个输入端的LuT可以实现所有n变 量的函数,共有2 2。种。由于LUT具有结构规则、工艺映射方便等优点,它 是一种非常适宜于可编程逻辑器件的逻辑发生器,目前在FPGA中使用很广。 一个4输入uJT的典型逻辑结构及其符号如图2.3所示。 (a) (b) 图2.3一个四输入查询表的逻辑结构及其符号 第13页(共91页) 第2章技术背景 2.2.2基于多路选择器的逻辑单元 基于多路选择器的逻辑单元是Actel公司提出的,在其FPGA产品中,主 要采用基于多路选择器MUX(Multiplexer)的逻辑单元,编程方式采用反熔 丝(Anti.Fuse)的一次编程技术,LC的结构如图2-4所示。 :却 :臼 ” n●● 图2-4基于MUX的逻辑单元结构 该结构与LUT相比除了在结构上不同外,在实现逻辑的方式上也是不同 的,它本身不编程,是一种固定逻辑块。其逻辑的实现是通过输入端和连线 资源的不同连接来实现的。这种结构能够实现四种基本的逻辑函数(NAND, AND,OR及NOR),其中包括任意二输入的函数,大部分三输入函数和部分 四~八输入函数,总共可实现702种逻辑函数。由于反熔丝编程结构占用的 面积要比SRAM小得多,且编程点的电阻较小(<20Q),这种结构能取得较 好的面积利用率及速度性能。反熔丝一次编程后不可改变,编程的灵活性不 够,但可靠性很好,因此,常被用于可靠性要求高的场合,如航空、航天及 军事等领域。 2.2.3基于与阵列的逻辑块 在复杂可编程逻辑器件CPLD(Complex Programmable Logic Device)中, 往往采用由与阵列等模块构成基本的逻辑块。由于该逻辑块的粒度较大,在 Altera、Xilinx等公司的产品中,把这种逻辑块称作宏单元(MacroCell)。CPLD 中的宏单元是在PLD中逻辑块的基础上发展而束的,这种宏单元由与逻辑平 面、乘积项选择器及时序模块等部件组成。与阵列产生基本的乘积项(与逻 辑),乘积项选择器提供乘积项分配、共享、扩展的功能。这种宏单元在实现 高输入的函数时非常有利,而基于uJT的模块随着输入的增加MOS管数呈 指数增长,代价十分高昂。CPLD与FPGA器件相比各有特色,但界限已越来 越模糊,CPLD往往也可以被看作是一种FPGA。商用CPLD器件~般还提供 ~些复杂的逻辑功能,如,与平面共享输入端,输出可编程反相,可编程的 触发器实现时序等功能。典型的宏单元结构如图2.5所示。 第14页(共91页) 第2章技术背景 图2-5基于与阵列的宏单元结构 2.3基本互连线结构 FPGA的连线结构是影响连线布通率、面积利用率及速度等性能的重要因 素,不同的单元结构、编程方式都对连线结构提出了不同的要求,因此,连 线结构的形式很多。但从连线的拓扑结构上来分,一般地可以分为对称式、 行式及层次式三类。 2.3.1对称式连线结构 图2-1中C、L及S分别代表连通模块、逻辑单元及开关块,它们之间通 过对称式互连结构11711181091连接起来。其中,连通块C为连接逻辑单元L 与布线资源的一组布线开关。开关块S为一组连接布线通道中连线之间互连 的开关,开关块位于水平布线通道和垂直布线通道的交汇处。将每个逻辑单 元端口所能连接的连线数,定义为连通模块c的布线灵活度Fc;将开关块s 的引脚与其它连线的连接数,定义为开关块的布线灵活度FS。连通模块和开 关块的拓扑结构对连线布通率的影响很大,Fs=3的开关盒与连通模块配合 时,所需的布线丌关数最少。图2.1的对称式结构中,包含有短线、中长线及 长线等连线资源。 在对称式结构中,开关块是连线资源的一个重要组成部分,其结构的好坏 将对连通能力、速度等指标产生影响。【201提出了用最少开关构造通用丌关块 USM(Universal Switch Module)的算法,并基于网络流理论分析了丌关块的 可布通性。即一个w边的丌关块成为通用开关块的必要条件是其内部的开关 数目不能少于6W。图2.7为一个通道密度为4,通道连线为可交换的一个通 用开关块(a)。及其两个子模块(b)的模型结构。 第15页(共91页) 第2章技术背景 圈圜,圈 C 任1 ‘bl 图2.7 w为4的通用开关块USM及子模块模型 2.3.2行式连线结构 基于行的连线结构,非常类似于ASlC的标准单元设计结构,这种连线结 构也分成水平和垂直连线。但水平连线通过专用的水平通道来连接水平单元 或垂直连线,而垂直连线则无专用的连线通道,对隔行的单元或水平线段的 连接,是穿越逻辑模块进行的。Actei公司型号为ACT-I/ACT2及40MX系列 的FPGA器件中,采用行式连线结构。基于行的FPGA及对应的连线结构, 分别如图2.8a、2—8b所示。 S b H 嬲㈨“ R计 脚∞呈,o m}\ 。,\ [二二冱匿=二二] (a) 垤M Ro‰g M/ (b) 图2.8行式FPGA结构 在Actel公司基于行的FPGA结构中,水平线段最短的为一个模块的宽度, 最长的为整个通道的长度,大于1/3通道长度的线段为长线,水平线段的长度 可通过反熔丝连接。垂直连线都通过模块走线,分成一个或多个段,垂直连 线共可分成三类,即:输入线、输出线及长线。输入线段专用于模块的输入, 输出线段专用于模块的输出,每个输出段跨越四个通道(两个在上,两个在 下)。垂直长连线能在布线时编程确定。Actel的FPGA结构采用反熔丝的编程 技术,导通电阻较小,能实现比其它编程技术更快的速度。由于布线结构规 则,也容易较准确地估算时延性能。 第16页(共91页) 第2章技术背景 2.3.3层次式连线结构 层次式的连线结构最大的优点是具有可预测的固定延时,从而芯片速度普 遍高于对称式FPGA结构。本文采用的互连结构为层次式互连结构。 Xilinx公司采用层次式互连来改进其经典的对称式FPGA短线互连结构, 在XC3000/4000的基础上,XC4000X新增四倍长互连并加大直接互连和长线 的数量,使得布图器的运行时间减少了72.87%,并且增加了连线时延的可预 测性。 而Altera公司的FPGA产品(FLEX系列)中,则将8个基本单元和丰富 的局部互连组成逻辑阵列块LAB,LAB按阵列化排列。为了进一步吸收短线 互连的优势,该公司的最新产品Apex系列中宏单元中的LAB又增加了局部 互连,形成多层次互连资源。短线和长线的作用起到互补的作用,并可以通 过层次化互连来配置。图2.9为Altera公司的FLEXl0K的层次式结构。 口口口口口口口口口口口 瞎If霞||匾 隔||霞《匿 口口口口口口 口口口口口口口口口口口口 图2-9 FLEXl0K的层次式FPGA结构 2.4编程工艺 FPGA的编程工艺有【9】:静态随机存储器(static RAM,SRAM)方式;反 熔丝(anti—fuse)方式;可擦可编程只读存储器(erasable programmable ROM, EPROM)方式和电可擦除可编程只读存储器(EEPROM)方式。其中,应用 最广泛的是SRAM编程工艺,如图2—10所示。如不特别指出,以下讨论的 FPGA都是基于SRAM编程工艺的。 第17页(共91页) 第2章技术背景 图2—10 SRAM编程工艺 2.5本章小节 本章介绍了学术和商用FPGA的整体结构、可编程逻辑单元结构、FPGA 基本互连结构和FPGA编程工艺,指出本文所参考的目标硬件结构为层次式 结构、基本逻辑单元由LuT实现、采用层次化的互连结构及采用基于SRAM 的编程工艺,为我们在接下来的章节提供了FPGA的基本硬件知识和技术背 景。 第18页(共91页) 第3章FPGA结构描述 第3章FPGA结构描述 在FPGA软件系统中,FPGA硬件设计者需要提供FPGA的结构描述文件给软 件设计成员,FPGA软件成员根据FPGA结构描述文件,通过逻辑等价、逻辑抽象 在软件系统中重新构建PPGA的结构,得到计算机可以识别的单元、图或树的结 构,以便完成FPGA软件系统整体流程。本章在学术上经典的结构描述的基础上, 并根据对商用FPGA结构的调研研究后,提出一种基于Ti 1e的结构描述方法。 3.1 VOR中结构描述文件 通用的布局布线VPR[21](Versatile Placement and Routing)是Toronto 大学提出的一种布局布线软件,其描述的结构主要是对应于对称式的FPGA结构, 并对商用的FP6A结构进行了简化,是学术上常用的一种FPGA结构。下面就学术 上[193[21]的FPGA结构描述做一简单介绍。 图3-1所示为VPR的目标FPGA结构,其为对称式的平面化结构。 第19页(共9l页) 第3章FPGA结构描述 IoPAD … 口口 lCLB f‘。 l l CLB 口 I ll 盆口口 ICLB l jCLB I l l CLB 8厂] 一L———_J I lI Il 口 口 CLB 口 CLB CLB 图3-1VPR目标FPGA结构 3.1.1 FPGA整体描述 FPGA的整体描述是对FPGA最顶层的结构进行的抽象描述,包括如下几个方 面: 1)FPGA阵列规模大小,表示为芯片中CLB阵列横向和纵向的CLB个数; 2)一个CLB对应的pad的个数,等价于10和clb大小的比率; 3)芯片通道宽度,以通道中互连资源的数目表示;CLB之间的通道宽度、 CLB与10B之I.日J的通道宽度可以单独设置;且假定CLB之『自J各处的通道宽度是相 同的,四周CL8与108之闯的通道宽度也是相同的。 4)逻辑单元的整体描述:图3-2所示为VPR所采用的逻辑单元结构,在描 述中包括,逻辑块输入输出引脚数目I、所属类型及在逻辑单元上的物理位置, 同一类型的引脚在逻辑上是否等效的(如LUT的输入),每个逻辑块中子逻辑块 或BLE的最大数目N,每个子逻辑块BLE的LUT输入的数目等。 第20页(共91页) 第3章FPGA结构描述 o哪Ⅳ 图3-2逻辑单元的整体描述 3.1.2详细布线结构描述 御线资源结构描述,由于FPGA结构中大部分都是FPGA的布线资源,布线 资源在FPGA中是最重要的一部分,因此布线资源的结构描述也就成为FPGA结构 描述中最关键的一部分。 开关盒描述了FPGA中水平通道和垂直通道中线网的连接关系,VPR中描述 了三种典型的开关盒:disjoint[22]、universal[20]、wilton[23],各种开关 模块的类型如图3—3所示: 擀擀鞲 a}Di和删 bJ t砸~Pf崩 cl wmo“ 图3-3三种典型开关盒结构 为了简化处理,三种典型的开关盒的连接度Fs都为3,即任何一条线都连接 到其它的三个通道。 VPR中描述逻辑块的每个引脚连接通道track的连接关系引入了一个参数 Fc,根据引脚的输入输出属性又可以分为Fc—input和Fc_output:表示引脚可 以连接的通道中track数与通道宽度的比值,具体哪些track可以连接则通过连 第21页(共91页) 第3章FPGA结构描述 接盒来确定。 结构描述中,可以为FPGA布线通道指定多种不同的布线资源,每种布线资 源用一行segment语句描述: segment frequency:<float)length:<int longline>wire—switch:<int>opin_switch: <int>Frac cb:<float)Cmetal:<float) 具体含义如下: frequency:描述该种布线资源所占的比率; Iength:描述这种布线资源的长度,用该布线资源跨越的LC的个数来表示, 如果该布线资源是长线的话,就用关键词longline表示,长线将跨越FPGA的 整个芯片; wire—switch:其它线段用来驱动此类线段的开关类型(具体类型由switch 语句描述); opin_switch:CLB和pad输出引脚用来驱动此类线段的开关类型(具体类型 由switch语句描述); Frac_cb:描述布线资源上的连接模块分布的密度,值在0和1之间。这个 值表示经过此线段的逻辑块的比例; Frac—sb:描述布线资源上的开关模块分布的密度,值在0和1之『日J。这个 值表示在此线段上有(1ength+1)*(num)个switch box。水平、垂直track之 『自J连接方式由switch_bOX—type语句决定。 Rmetal:单位布线长度的阻抗(所谓的单位长度是一个LC的长度); Cmetal:单位布线长度的电容; 如图3—4所示对通道中2倍线和4倍线进行了描述: 囟NHIlchm~ o“、nnc ̄IlIln I如、 segllIent segment frequency;0·5 length:2 Frac—gb:0—666 wlre—switch:0 Opln_swltch;0 Rmetal:5 Cmetal:Se一15 frequency:0·5 length#4 wlre_swltch:0 opln_swltch:0 Frac—sb:1. Rmetal:3 Cmecal:2e一15 图3-4可分割线描述示例 Yrac_cb:1·\ Prac cb:0·5、 VPR结构描述对可编程布线资源的开关类型描述方法如下: Switch<int>buffered:{yes no}R:<float>Cout:<float>Tdel:<float) 其中包括对开关类型是否为三态缓冲开关还是传输晶体管的双向开关,连接 第22页(共91页) 第3章FPGA结构描述 开关的电阻、输入输出电容及开关内部延时,和开关的等效最小宽度nmos管阻 抗(计算FPGA面积时使用)。 3.2基于Tile的层次化结构描述 3.2.1最新FPGA布线资源介绍 随着FPGA阵列规模及布线资源的不断扩大,最新的FPGA均采用层次化的 FPGA整体结构,其中包括xilj rlx”公司的Spartan系列、Virtex系列及Alter8,TM 公司的Cyclone系列和Stratix系列,布线资源也越来越丰富。下面以VirtexII 作为例子就最新FPGA布线资源结构作介绍。 Virtex II的所有逻辑功能块,包括CLB,IOB,DCM,BRAM,Muitipl ier,都 连接到各自相同的全局布线矩阵Global Routing Matrix(GRM)(或者称为开关 矩阵Switch Matrix),再通过GRM连接到全局互联资源。整体结构就是逻辑功 能块和与其相连的GRM组成的阵列,其中一个GRM与CLB或者一个GRM与一个 IOB构成一个Tile,如图3-7所示: S…witch恫 l 淞H啪 I 徽H,∞ I 湫H m 湫H,∞ II S蚴witmch恫 湫H c。。 I 粼H c嵋 JJ 湫H c嵋 l Switch J cL8 I 湫卜冈 徽H m 湫H。嵋 lJ S鼬wit。ch IILH=J c旧 sMwi猷耙。。h lL__,ll。。。 s们chL+ DCM I [vlatnx 。。—— Swil柏1.+ l Mal’懈l L s翻c}1 。! Matrix Z 杀} 叠三 羔j l- Swildn 意互 Matdx 湫卜 -—— 粼卜 J lL SMw。i。lc。h l 粼卜 I ¥wkch Ip Switch M8t眦l。 图3—7 VirtexII整体结构 下面介绍Virtexll系列芯片所包含的御线资源,其包括长线,六倍线,两 倍线、相邻CLB的直接连线及快速互连。 长线:水平和竖直方向各有24根双向长线,每个tile的GRM和其中的四根 相连,即每根长线每隔6个t订e和一个tile的GRM相连。对水平长线来说,它 第23页(共91贞) 第3章FPGA结构描述 可以驱动水平HEX线,可以被水平double线和相邻CLB直接连线驱动;对竖直 长线来说,它可以驱动竖直HEX线,可以被水平HEX线,水平double线和相邻 CLB直接连线所驱动。如图3-8所示为长线的连接关系: 图3-8长线连接关系 六倍线HEX:水平和呸直方向各有6组120根HEX线,HEX线均为单向,某 根HEX线在若在源端被驱动,则每隔3个tile或者6个tile,信号可以传输到 相应CLB。HEX线可以被与之方向垂直或平行的HEX线,与之方向平行的长线, 相邻CLB的快速互连线和CLB的输出所驱动;也可以驱动与之方向垂直或平行的 HEX和double线。如图3—9所示为6倍线的连接关系: 图3-9六倍线连接关系 两倍线Double:水平和竖直方向各有40根两倍线,double线也是单向线, 某根double线若在源端被驱动,则每个一个tile和两个tile,信号可以传输 到相应CLB。double线可以被与之方向垂直或平行的HEX和double线,相邻CLB 的快速互连和CLB的输出所驱动;也可以驱动与之垂直或平行的double线,和 CLB的输入端。如图3—10所示为2倍线的连接关系: 图3-10两倍线连接关系 相邻CLB的直接互连线:每个CLB都可以通过这种直接互连线和与其相邻的 上,下,左,右,斜对角的共8个tile的CLB直接相连,从每个tile输出的这 种直接互连线共有16根。这种直接互连线均由CLB的输出来驱动,它可以驱动 HEX线,double线和CLB输入端。如图3-1 l所示为相邻CLB的直接互连关系: 第24页(共91贞) 第3章FPGA结构描述 图3-11相邻CLB的直接互连关系 VirtexII的互连资源中的输入选择器IMUX的输入包括水平和竖直方向的 double线,竖直HEX线,全局时钟线,相邻CLB之『自j的直接互连线和CLB的输 出,输出则为CLB的输入端和三态Buffer的输入端,其框图如图3—12所示: 图3-12 IMUX连接关系 图3—12中的F、G等为FPGA中基本逻辑块Slice的输入引脚,Double、Hex 等为布线资源连线,它们之间通过IMUX作为输入选择器决定具体的连接关系。 3.2.2 FPGA布线资源描述思考 按照VPR基于线网的描述方式,我们需要对各种布线资源进行描述,需要根 据硬件结构进行抽象,对各种可分割线、不同的逻辑块的互连资源进行单独描述, 基本方法如下: 1、需要知道各个逻辑块的输入、输出引脚的连接度,在FPGA对应软件中还 需要根据各个逻辑块所处位置的连接盒关系来决定各个逻辑块引脚具体连接到 第25页(共91页) 第3章FPGA结构描述 通道的情况,在软件实现中需要对引脚的连接规则做很多假设/j’能使软件构建出 的逻辑块引脚连接关系与具体硬件结构中逻辑块的连接关系相一致,这不利于软 硬件的扩展。 2、对于不同的可分割线,直接线、双倍线、六倍线等的描述,其中六倍线 有可以分为单向六倍线和双向六倍线,各种不同分割线之间在通道中的分配情 况、同种可分割线及不同种可分割线之间的连接关系、驱动关系需要通过对开关 盒及连接开关进行描述,由于其开关盒的方式描述陷于3种基本结构,而且同1) 一样,各种不同分割线的分配规则、开关盒连接关系也在软件中进行了假设,不 利有软硬件的协同扩展。 3、对于其他逻辑单元的描述,硬件宏模块,如图3一13所示的硬件宏模块与 布线资源的连接关系,其中硬件宏模块包括块RAM、乘法器、STARTUP、BSCAN、 DLL等描述,布线资源的连接关系描述应当包括逻辑块引脚描述和连接到通道布 线资源上的描述,VPR的结构不能描述这种结构,对于这些特殊的描述需要完全 的描述。 Macro 官|、 毒I[:) d铲 p 图3一13硬件宏模块及连接关系 4,对其他布线资源的描述都需要完全描述或者在软件中做相应的假设,不 利于软硬件的同步扩展,如下图3一14为总线的连接关系。 第26页(共91页) 第3章FPGA结构描述 }-态总线 图3一14总线连接关系 3.3基于Tile的结构描述 基本Tile的结构描述的思想来源于FPGA硬件版图结构,FPGA硬件结构由于 其规则性,在其版图的制作过程中,将相应的相同的Tile画成一个基本Tile, 基本Tile之问通过顶层的金属互连连接起来,构成整体的FPGA硬件结构。在这 里基本Tile包括CENTER(即内部CLB TILE)、TOP—IOB、LEFT一10B、RIGHT— IOB、BorroM—IOB、BRAM、MULT等,这些都是可以重复利用的T“e,还包含其 他特殊的、没有重复利用的Tile,如STARTUP、BSCAN、DLL等。 下面介绍一下基本Ti le的构成,基本Ti le由可配置逻辑单元及其相应的布 线资源构成,由于基本Tile的重复性,所以对于FPGA中重复相同T订e的描述 只需要描述一次即可。基本Tile由基本逻辑单元、输入选择矩阵IMUX、输出选 择矩阵OMUX和线网切换矩阵GRM组成。下面以中心Tile为基本对象进行基本 Tile的描述方法介绍。 3.3.1基本逻辑单元描述 可配蜀逻辑单元称为CLB(Configurable Logic Block),CLB功能等效与前 面提到的LB,其功能是为了实现电路的基本逻辑功能,包括组合电路和时序电 路,其中CLB继续往底层划分,可以由更顶层的逻辑单元构成。如图3-15所示 为Xilinx公司的Spartan系列的CLB结构,其构成包括两个slice和两个TBuf 等构成,其中S1ice由两个四输入LUT和两个D触发器及其他逻辑单元构成,TBUF 为实现总线的基本逻辑单元,对于Xilinx公司的Virtex系列,CLB则由4个S1ice 构成。图4一15中箭头表示为可配置逻辑单元的引脚的输入输出属性,具体与外 界其他模块的连接的关系将后面介绍,图中G4…G、X、Y等表示为CLB及其底层 逻辑单元的端口名称,对于底层逻辑单元的端口与CLB端口的连接关系也在这里 进行描述。 第27页(共91页) 第3章FPGA结构描述 图3—15可配置逻辑单元CLB结构 上面介绍的CLB的基本结构,如果仅仅考虑电路在FPGA芯片上的布通问题, 只需要描述CLB的对外端口属性就可以,如果考虑基于时序驱动的FPGA命线算 法时,则需要对CLB的延时信息进行描述,关于时序模型参考后面相关章节。 CLB是FPGA的基本逻辑单元,下面将介绍FPGA的布线资源的描述情况,正 如前面提到的,基于Tile的结构描述考虑到Tile的重复性,在描述过程中重复 Tile仅需要描述一次即可,而不相同的Tile的基本结构的数目有限,因此给我 们的描述提供了方便。 3.3.2输入选择矩阵IMUX描述 在下面的描述中,基本逻辑单元将作为一个整体块出现,根据上面的描述可 知基本逻辑单元的输入输出引脚等对外的连接关系,作为基本逻辑单元的各个输 入引脚通过IMUX选择哪些线网输入,如图3一16所示,箭头所指方向表示IMUX 作为整体单元其对外端口Port的输入输出属性,从图中可以看出IMUX的输入来 源于布线资源线网,根据我们稍后对GRM和Wire模块的描述可知,其输入对于 我们的描述方法来说是来自于相邻Wire模块和GRM模块输出(图中标识为 DUMMY),由于线网资源属性(线网的长度及其采用单向或双向开关等的不同区分 不同的布线资源)的不同,将输入线网归类,分别对不同类型线网组进行描述。 图3—16中,S1ice/tbuf--inputs连接到图3一15中的输入端口,它们直接是 以金属线直接相连接,图中表示的GcLK、OUT等表示的是线网的属性名,n1……n7 等表示的该类线网的数目。 第28页(共91页) 第3章FPGA结构描述 —cl—IⅡ可暑酉互舀> lo—z一蔓∞一_皇u—a9A DUMMY wJ““sJ“”E_P““NJ’ 图3-16输入选择矩阵IMUX结构 3.3.3输出选择矩阵OMUX描述 IMUX矩阵描述的是布线资源外部通道中不同类型线及CLB输出反馈到CLB 输入引脚的选择连接方式;输出矩阵OMUX描述的则是可配置逻辑块输出到布线 资源外部通道中不同类型线的连接关系,也包含了总线及全局线网输入的连接关 系。图3-17表示为基本OMUX的结构,其中箭头方向表述端口输入输出属性,由 于OMUX中采用了OUT#(#表示一个数字)作为OMUX的输出端口,其连接到后面 提到的GRM矩阵中,在通过GRM的描述来连接其他布线资源中的各类型线网,这 样一方面是和硬件结构完全对应起来,另一方面可以使布线资源的描述层次分 明,使布线资源的描述清晰,也保证了以后的硬件结构升级时,结构描述修改的 容易性和简单性。 第29页(共91页) 第3章FPGA结构描述 图3.17输山选择矩阵OIvflJX结构 3.3.4线网切换矩阵GRM描述 通道中同种类型线、不同类型线之间的连接关系通过不同线网问的切换矩阵 GRM来进行描述,GRM中也包含了CLB输出连接到不同类型线上的连接关系,GRM 是布线资源描述中最关键的一部分,而GRM的设计的好坏也影响到电路在FPGA 中是否可布通及电路时序的问题,因此设计一个好的GRM将是设计出好的FPGA 布线资源关键的一步,而以前的对线网切换关系的描述受到开关盒SB的约束太 多,不利于GRM的重新设计与优化,因此采用我们这种GRM的描述,可以不受开 关盒sB的约束,可以根据FPGA硬件设计人员的设计灵活的进行修改。 GRM描述的各类线之间的连接关系,如图3一18所示为基本的线网切换矩阵结 构,其中箭头同样是表示GRM模块端口的输入输出属性,DUMMY表示GRM连接到 IMUX中DUMMY的线网,它们之间的连接是采用金属线直接相连的,OUT#是0MUX 中的输出端口连接,其他标识符H(Horizontal):表示水平方向线网,V (Vertical)表示垂直方向线网,N(North)表示上方的线网,S(South)表示 下方的线网,E(East)表示来自右边的线网,而w(West)则表示来自左边的 线网。nl……n8等表示为同类型线网的数目。 第30页(共91页) 第3章FPGA结构描述 ★Z{≯;{_^I{>;{∞{≯ 《}∞★.:《}7目}:《}Z 【0Ill2131415蚓71819IlOIlll 图3—18线网切换矩阵GRM结构 在我们的描述中,对于IMUX、OMUX、GRM中的连接线之间的驱动方式,可以 通过对不同丌关进行描述来识别,基本开关驱动连接方式可分为: ==:双向且无缓冲器开关 =>:双向且一个方向有缓冲器的开关 一:双向且两个方向均有缓冲器的开关 一>:单向且有缓冲器 当然如果有其他方式的连接开关,可以灵活的增加开关类型,同时对于开关 的其他属性(输入、输出电阻、电容等)还需要单独列出,在此不做详述。 对于其他逻辑单元块、输入输出Pad、硬件宏模块(BRAM、Mult)等同样采 用了上述的描述方法,分别对逻辑模块、输入矩阵模块、输出矩阵模块及对于线 网切换模块GRM进行描述。 第31页(共91页) 第3章FPGA结构描述 3.3.5 Tile连接关系描述 至此为止,我们已经完成对基本Tile中,逻辑单元块、输入选择矩阵IMUX、 输出选择矩阵OMUX及线网切换矩阵GRM的描述,接下来的任务就是要将这些基 本Tile拼接成整个FPGA芯片,因此需要对Tile连接进行描述,图3一19所示中, 用圈圈起来的部分构成了一个可重复的Tile。 图3—19可重复Tile 图3—20所示为Tile的拼接方式,Tile的概念来源与硬件的版图设计,Tile V 之间的连接关系描述的顶层的连接关系,图中wire模块J下是表示了各个Tile 之间的连接关系,包括各个可重复的Tile(CENTER、TOP、BOTTOM、LEFT、RIGHT、 LBR胱、RBRAM、L删LT、删LT等)、没有重复的、独立的各个Tile(BSCAN、STARTUP) 之间的连接关系以及Tile与其他布线资源之间(全局时钟等)的连接关系。 第32页(共91页) 第3章FPGA结构描述 詈 昌 睦 詈 图3—20 Tile的拼接方式 这种基于Tile的描述方式,使各个Tile可以与硬件完全对应起来,同时避 J 免了过多的对通过软件来构建FPGA布线资源图的依赖,可以很好的实现FPGA 软硬件的协同升级扩展。 3.4结构描述实例 下面是以Xilinx公司的SpartanII系列芯片为目标结构进行的FPGA基于 Tile的结构描述,其中描述语言为可扩展性表示语言XML(Extensible Markup Language)。 以第1行第2列也目标Tile作为实例,这罩的CLB只描述了顶层的输入输 出端口,如下所示: s1…O (TILE Rt“1”C=”2“namet”R1C1”pos一“CEHTER“> (PORT> <input>S1一O R1 B2 S1 B_83 s1一。一呐Sl—SR—B <output>S1一XB S1一XQ S1一Y S1一YB S1一Vq TBUF—OUTl se bx_e SO_BY—B……(/input> TBUF—OUTO……</output> </PORT) 第33页(共91页) 箜!童!坠堕塑堂堕 下面是输入选择矩阵IMUX的部分描述: (PFROM name-”E_rF‘> <PTO>->Sl—G_B1 i I->s1』_B1II一>so G_e4Il一>s口_F—B々II一>T¥_B1I卜>TS BO(/PTO> </PFROH> <PFROM ilameo。E-P1”> <PTO>一>s1一G_B2I I一>s1一F-B2ll一’s日二LB3Il一>s--时一BIl一>so_BX_BI I.>SO_F—B3(/PTO> (/PFROl4> (PFROH nallte=“E P1 r。> <PRO>~>s1一G B2I 1.>SI F_B21 I一,S1 SR_DI卜>SO_G_OSI l->SO_F B3I I一>SO_SR B</PTO) </PFROl4> (PFROM nai"m”E—Pll”> <PTO>->s1-G_aslI一)s1』_e3II一'SO_G-B2II一>SO_F-B2</PTO) (IPFROH) (PFROH ilal帷=“E-_P12“> (PTO>->s1一c_e4Il一>Sl F_B≈lI—S1一CE-BII一>s0_cEJII一>SO G_B1I卜>SO F—BI<IPTO> </PFROHO 下面是输出选择矩阵OMUX的部分描述: <PFROH nalite=”S1 XB”> <PTO>->OUT6I卜>OUT7I I一>OUT3I l一>OUT5l I一>OUT2l卜>OUT4</PTO> (/PFROH> <PFROH name=”S1 Xn”) <PTO>一>OUT6I一1->OUT7II->OUT5II一>OUTOII一>OUT2I卜>ouT4II一>OUT4II一>OUT3(/PTO> ‘,PFROH> <PFROH nalse,“S1一YB”> <PTO)一>OUT6 I卜’OUT7 I I一>OUT5 I I一>OUTOl I一>OUT4l卜>OUTI</PTO} (/PFROH> <PFROH name一’s1-vq“> <PTO>一)OUT6II一>OUT7II一>OUTlII一>OUT8lI一>OUT5I卜>OUTOII一>OUT2II一>OUT4</PTO> <IPFROH> 下面是GRM的部分描述,其中第一部分为单倍线之间直接的切换关系,第二 部分为6倍线与单倍线或6倍线之削的切换关系。 <PFROH naRe=“S1”> <PT0>=一W7I I=一E3I I==H4</PTO> </PFROH> <PFROH name=”S1 0¨’ <PT0>=="8l I==N1BI 122 E4(IPTO> <IPFROI_I> <PFROH name=”S11”> <PTO)=-W13I I I l;=H11 I I==E9</PTO> (/PFROH> 第34页(共91页) 第3章FPGA结构描述 (PFROH name=”U6pm”> <PTO>一>W2I I一>H6H4I l一>EOI I一>H6ES(/PTO> </PFROM> <PFROH name=¨U6H5”> <PTO>一>¨0l l一>H6W4I I一>E22I I一>H6ES<IPTO> </PFROM> <PFROM name=“U6H6”> {PTO>一>W14I I一>H6W6l I一>E12I I一>H6ET(IPTO> <IPFROM> <PFROH name=¨U6H7“> (PTO>一>W12l I一>H6W6I l一>H6E7l I一>E10</PTO> (/PFROM> (PFR014 name=“U6H8“> {PTO>一>W13I I一>H6W8I l一>X6E9I I一>Eg</PTO> </PFROH> (PFROM name=”U6H9”> {PTO>一>¨6I I一>H6W8I卜>H6E9I I一>E4(/PTO> (/PFROH> 下面是Wire的描述关系,左边是相邻Tile单倍线之间的连接关系,右边是 相邻Tile6倍线之间的连接关系。 <¨FROH nane一”E21”> <WTO>R1C2.¨21<,虮0> </WFROH> ("FROH name=“E22”> {WTO>R1C2.”22<,WT0> <IWFROH> <¨FROH Dame=”E23“> <¨TO>R1C2."23(,WT0> <IWFROH> <¨FROH name=“E3“> <WTO>R1C2."3<,WT0> (/I,dFROH> <¨FRO¨name=“EV。> ‘¨TO>R1C2.W4</矿r0> I<WFROM name=”H6A8”> <仉0>R1C2.H6Ba<I”TO> 《,"FROH> <"FROH name=”H6n9”> (WT0>R1C2.H6Bg{I¨T0> <IWFROH> <”FROH name=”H6B 0”> <WT0>R1 C2.H6HO<IWT0> <,¨FROH> <"FROH napie=”H681”> <WTO>R1C2.H6H1<,WTO> (,WFROI-l> <协:ROH name=”H681 F’> <II,,/TO>R1C2.¨6H1日<,UT0> <IWFR0141} 3.5本章小节 本章在分析现代FPGA层次化结构及学术上对FPGA描述方法的基础上,提出 一种基于Tile的FPGA结构描述,由于基本Tile的重复性可以简化FPGA结构的 描述,同时由于该方法是以硬件结构为根据,为以后的FPGA软硬件的同步升级 提供了简单而灵活的接口,该方法在原型系统中测试证明是可行且正确的。 第35页(共91页) 第4章FPGA功耗模型 第4章FPGA功耗模型 随着半导体工艺的不断发展,系统时钟频率的不断提高,功耗问题已经成为 芯片设计的约束条件,也是芯片设计者要考虑的首要问题。与ASIC相比较,由 于FPGA有大量的晶体管用作可编程的互连资源,其功耗的效率很低。因此研究 FPGA的功耗模型并对FPGA的功耗进行评估进而研究如何降低FPGA中的功耗已 经成为越来越重要的课题。 低层功耗分析软件有电路级的PowerMill[24],Verilog级的 QuickPower[25]。虽然它们能够提供很高的精确度,然而这些工具对于上百万乃 至上千万门的FPGA来说是不适用。因此需要提出一种实用的FPGA功耗模型,本 文的工作不是为了和这些软件进行比较,而是给FPGA结构的设计者和降低功耗 的FPGA软件开发人员提供基本的功耗模型。 4.1 FPGA功耗分类 在纳米(深亚微米)的条件下,我们既要考虑电路动念功耗,也考虑到电路的 静念功耗,所以我们采用了混合级的功耗模型(Mixed—level power model),即 对互连资源采用开关级模型(Switch—level power model)和对S1ice内部逻辑采 用宏模型(Macro—models)。研究表明在纳米(深亚微米)级互连功耗占重要部分和 漏电流功耗也占很大的比重。 表4—1所示为电路中消耗的功耗类型: 动态功耗 Dynamic Power 静态功耗 Static Power 功耗源 开关功耗 (Switching Power) 短路功耗 (short·Circuit Power) 反向漏电流 功能传递 毛刺(Glitch) 功能传递 毛刺(Glitch) 亚阈值漏电功耗(Sub-threshold Lea!f.age Power) 表4.1电路中功耗的类型 电路中的动态功耗是指当信号发生转变时会对其负载电容、寄生电容进行充 放电,在此过程中会消耗能量,因此动态功耗与电路中的各个节点的转换率有密 第36页(共91页) 第4章FPGA功耗模型 切的关系,其每个周期内的动态功耗可以用公式4一l[26]表示为 DynamicPower一∑一0日.知5+c,4圪p脚+p二咖4D(y)‘厶I 公式4-1 ,’ T, T, 。,为节点Y处的充放电电容,r蛐,力为电源电压,…my/rig为节点处信号转变时的电 压跳变幅度,D(),)为节点y处的信号转换密度,,m为时钟频率(受到关键路径 时延的限制)。 静态功耗又称为漏电功耗是指当电路或一个逻辑门的各信号不发生变化时, 电路所消耗的功耗,随着晶体管特征尺度向100nm以下发展,静态功耗在功耗中 所占的比例越来越大,将与动态功耗相比拟。 表4-1中的功能传递(Functional Transition)是指在连续的两个信号跳 变时电路逻辑功能的传递,其为电路功能能正确传递的首要条件,而毛刺(Glitch 或Spurious transition):是由于各信号到达逻辑门的各个输入不平衡(不是 同时到达)而引起的信号的跳变,这在电路逻辑功能传递时是不希望出现的。 在FPGA中,由于其结构的特殊性,对于各种类型的功耗源,在计算时我们 采用了混合型的功耗模型,开关级(Switching level model)运用各种公式和提 取得到的参数(如电阻、电容)求得相应信号跳变功耗。而宏模型(Macro—Model) 是用SPICE仿真得到电路模型,并建立各功耗的查寻表和公式计算的方法。表 4—2所示为FPGA混合型功耗模型: I 动态功耗 Dynamic Power 静态功耗 Static Power 逻辑块 (Logic Blocks) 宏模型 (Macro-Modd) 宏模型 (Macro—ModeD 表4-2 FPGA混合功耗模型 互连/时钟 (Interconnect&CIoc¨ 开关级模型 Switch.1evel Modd 宏模型 (Macro-Modd) 4.2动态功耗的计算 在基于仿真的功耗分析中,需要电路的表示方法。电路可以有不同的抽象层 次,如可以是逻辑层次或者是结构层次。由于没有特定的信号,也不知道信号发 生转变的具体时刻,所以基于事件驱动的动态功耗计算仿真方法行不通,因此在 我们的模型中,动态功耗的计算采用基于概率的计算方法[27]。根据前面的介绍 动态功耗的计算可以按照公式4一l计算得到,下面我们将就基于概率的功耗计算 方法介绍公式4一l中的各个参数的计算方法。 第37页(共91页) 第4章FPGA功耗模型 4.2.1静态几率传输模型 众所周知,电路中一个逻辑信号可以被看作是由两个参数决定的0,1随机 过程,所谓信号静态几率(Static Probability)就是指信号处于高电平的几率, 可以由如下公式计算得到: p“)。“t+1f1 公式牝 其中tO、t1分别表示统计时间内信号处于低电平和高电平的时间长度。 在几率信号传输模型(Probabilistic Signal Propagation Model)中,我 们假设电路原始输入端口的信号以一定的几率出现,信号从主要的输入端口依次 向电路的中间节点及电路输出端口传送,根据输入信号的静态几率及逻辑块的函 数,可以求出零延时[28][29][30]理想情况下的逻辑块输出静态几率。 如图4-1所示为一简单电路示意图,其中p。表示该节点的信号的静态几率, £表示该节点处信号的功能函数,原始输入功能函数就是输入信号本身,如图假 设输入信号的统计特性为:{日,fl},{昱,艺},{只,f3},中间节点及输出节点的统 计特性为:{只,fi},{0,‘},{只,fk}。 图4-1简单电路示意图 对于任意的一个逻辑函数y=f(xl,..….,xn),进行香农分解后的函数为 Y一而厶+乏,_,因此输出静态几率计算公式可表示为公式4-3: 而 P(y)一P@厶)+P@厶)=P@)P(‘)+JP@)P(厶) 公式4-3 概率传输分析早期应用于晶体管网络级的功耗分析[311,其基本思想是将每 个晶体管看作是由其栅信号概率控制的开关,信号从晶体管的源向漏的传输几率 第38页(共91页) 第4章FPGA功耗模型 以栅信号概率得到。通过这种方式,电路中所有的节点都可以计算得到,节点处 信号转变几率可以通过公式f=p’(1一p),计算得到,于是功耗的计算也就通过公 式P=C×Vz×f得到。 4.2.2转变密度传输模型 按照静态几率传输模型可以计算出各个节点的静态几率,利用f-P·(1.p)和 P=CXvz×f公式可以计算单个节点的信号跳变几率,但是输出信号的转变可能 是因为原始输入的变化,也可能是由于其他门的输出作为该门输入的变化(假定 输入没有同时的变化);且如果输入处于一个不恰当的状态,则即使其他输入信 号发生变化,输出也不发生变化。例如:一个与门,如果其中一个输入被置为O, 则不论其他的输入信号发生变化,其输出信号也不发生变化。 Najm[32][331针对这种情况,最早提出了基于门级电路的转变密度分析,其 在节点静态几率的基础上提出了节点转变密度的概念,所谓转变密度(Transition Density)是指信号在单位时间内跳变的次数T(xi)。 假设布尔函数y=f(xl…….,xn),其输入变量xi的静态几率和转变密度分别为 P(xi)和D(xi),通过计算求出其输出信号Y的静态几率P(y)和转变密度D(y)。为 了避免严格的统计分析,在计算输出信号的转变密度时,采用零门延迟模型,即 不考虑信号从输入到输出的延迟,实际情况中可能由于时延而产生毛刺信号,影 响输出信号的转变密度。 句尔函数y=f(xl,..….,xn)可以写成:),一薯‘,“一1)+墨+,“一o)。假定输 入信号t由1变化为O或由0变为1时,触发输出。如柒输出y发生变化,即 为1,即,“)o,@)一1;如果输出Y没有变化,即,“)…1 ,“)-1一一,,“)一0或者,“)=0一一,,“)-1,也就是说两个函数的异或 ,f(xt)一1或 ,纯)=0一).,纯)一0,则异或厂@)el如)一O。该异或公式称为y的布尔差 分二}一,∽)o,@)。 线 ’ 所以,从上面的推导过程中,可知要使输入墨的变化能够传输到输出的话, 必须满足M。厕乩令以却为忑ay的髀叫脚懒凇,’假定 输入是不相关,则对于t的变化得到的y的转变密度为P(譬虢),D瓴),于是可以 得到对于n个输入的函数,其输出的转变密度为: 第39页(共91页) 第4章FPGA功耗模型 她)=薹尸(耖荆 公式禾3 4.2.3运用转变密度的功耗分析 在运用转变密度进行门级的功耗分析时,其基本思想是从原始输入求出各中 间节点及其输出的转变密度,再将该转变密度作为节点的转变频率运用到公式 P—C,V2·,中(假设原始输入之间的静态几率和转变密度是相互无关的),将 该方法运用于组合电路的分析时,其步骤如下: 1)找出每个节点关于原始输入的布尔函数 2)对于每个节点,求出其转变密度 P。∑委·c,·VZ*Dry) 对所有的节点求出总功耗 所省市点r z 该方法在时间复杂度上不大,实践证明该方法在组合电路中是合理的;在实 际的电路中,如果采用实际电路原始输入的静态几率及其转变密度的话,其结果 也是非常精确的。与基于事件驱动的逻辑仿真相比,计算效率更高,但精度有所 降低。 模型中最主要的缺点是由于假设信号传输的零延时,所以毛刺信号没有考 虑,关于信号相关性问题在[34]有所考虑,但其计算复杂度增加,效率降低。 由于逻辑门各个输入信号具有不同的路径时延而导致一个逻辑门单元的输 入端口信号在不同时间达到,在逻辑门输出信号达到平衡之融,会产生毛刺信号, 尽管缓冲器只有一个输入端口,它们也会传送毛刺信号,所以也会消耗功耗,但 是其信号的跳变并非全幅跳变(Vdd专GND或GND专Ydd),所以在计算其功耗 时,我们不能用全幅信号计算,而采用一个参数计算。 同时由于毛刺信号只有在能够保持~定的时间长度时,其信号才能被传递过 去,因此我们需要采用一个低通滤波模块[33][35](Low Pass Filter Block), 如图4—2所示。低通滤波模块可以保证对布尔函数输出节点的转变密度的检查和 限制,以至对于某些节点n,通过公式4—3的计算处理的节点的转变密度可能会 很高进行了限制,使评估计算结果更加接近实际值。 第柏页(共91页) 第4章FPGA功耗模型 图4-2低通滤波模块 为了模拟电路本身存在的时延而产生的滤波现象,如图在逻辑单元输出端加 入一个低通滤波模块;只有当输入信号在一定时间长度内保持稳定时,Y处的信 号转变才能够传递过去,在此我们引入了以脉冲宽度为变量的几率分布函数来确 定输入脉冲是否能够传递。 在实际中由于时延引起的毛刺信号可能不会出现,因为模块不能及时的响应 该信号。所以,引入低通滤波模块来描述这种情况,当模块输入由0一一,1或由 1一一>0时模块输出要经过『1(%)的延时,只有当在这个时『日J过程中,其输入 没有变化,输入的变化才能传出来。所以,在低通滤波模块中,引入输出的最小 脉冲宽度%(q)。 逻辑脉冲宽度分布:脉冲宽度分布函数是积累的分布函数(Cumulative distribution function(cdf)互O)),假定‘是与E(f)具有相同分布的随机变 量P饥《f}2正∽,则概率密度函数(Probability Density Function(pdf))为 ^O)一aFl(t),同理假定ro为低电平的随机变量:P{%cf);Fo(t), “‘ ,, .to(O;÷磊O)。 ⅡI 正O)。上^(f)其中/gl是高电平脉冲的宽度,五(f)是上面得到 Eo);foz一,f1(z地 【33】文中假定:每个并O)的脉冲宽度与其过去和将来的脉冲宽度无关,在实 第41页(共91页) 第4章FPGA功耗模型 际的情况中,如果两个脉冲在时间上分开,则这种假设是合理的。 对于一个滤波块(Filter Block)其输入xO)、输出yO),其状态有四种情况, 图4.3状念转换图 其中晶OlO,y。o)、墨@_1,y。1)是稳定的状态,墨010,Y。1)、 Se(x-1,y。0)是不稳定态。如果滤波块进入墨或是状态,则该状态持续时间为气 (%),之后自动转变为晶、S,所以只有在这种自动转变的条件下,输出Y才 有所转变。 【33]推出如下定理,对于输入x,输出Y的滤波块,在给定的假设条件下, 得到其输出几率和转变密度为: P(y)=P(x)一{E(‘)+三L【1一互瓴)】) 一 +』警剖kP@) 1-,0瓴)E瓴)】、’ 公式¨ +{岛Oi)+:堑【1一昂(%)】} 芦o ,—警譬k(1一P@)…) 【1一R‰)墨瓴)】、 。(y)=旦亏鲁睾黼。@) 公式¨ 为了计算输出的几率和状态密度,需要知道脉冲的分布函数,在缺少必要的 信息条件下,认为其高低脉冲是指数分布的,这是合理的。 因此对于考虑毛刺信号的节点静态几率和转换密度可以表示为: D(y)=D(x)+PF 第42页(共9l页) 第4章FPGA功耗模型 P(y)_斥+(西丽1一Po)) 其中PF为比例因子,其表达式为: 足,!!二墨亟!】堕二墨鱼塑 ’ 1一磊‰)曩瓴) 如果采用节点转换密度计算动态功耗运用到门级功耗分析中,我们可以发现 模型中最主要的缺点之二是该公式没有考虑到逻辑单元复杂电路(如UJTs)的 内部节点信息,而且该公式仅考虑了电平从Vdd到GND或GND到Vdd的全幅 情况,因此为了得到好的计算效率,我们仅将该公式用于互连和时钟网络功耗的 计算。我们采用了LUTs的宏模型及运用LUTs转变密度的方法计算动态功耗。 对于时序电路的计算,其基本原理是运用迭代分析的方法试图预测出所有时 序元件输出的几率极其转变密度。 对于D触发器,其输出几率与输入几率相等,输出的转变密度可以认为与其 转变几率是相等的。所以D触发器的输出转换密度u【yJ可以看作是其输出转换 几率PAy),所以可以运用如下公式计算D(y)4只(y)#2+PO)‘(1一P@))。对于 具有时序反馈环的电路,可以通过多次跌代的方法求出其输出转换几率,尽管该 方法是一种近似算法,研究表明运用该算法经过三次跌代,其平均误差在5%以 内。 4.3 FPGA动态功耗计算 为了求出FPGA总的动态功耗,我们将其分为三部分:布线资源的动态功耗、 逻辑块的动态功耗、时钟网络的动态功耗及短路功耗。 4.3.1布线资源的动态功耗 FPGA中大部分的动态功耗消耗在线网信号跳变的布线资源上,对与该部分的 动态功耗可以用线网信号转变密度及线网(track)电容采用动态功耗公式求得。 由于布线track的电容随着track的长度及track上所连接的缓冲器buffer有 关,单独采用一个电容值是不精确的,因此我们通过FPGA的布线资源图提取 track的电容信息。如图4-4所示为一条跨越4个逻辑块的金属线track,其上 第43贞(共91页) 第4章FPGA功耗模型 连接有很多的可编程开关。 SH'd嗨sen:a。sub§鲥 图4-4布线资源线网示例 一般而言,决定线网track的电容的因素有:可分割长线跨越的逻辑块的数 目、逻辑块的大小、每个逻辑块的引脚数目、开关盒及连接盒的连通性、采用的 工艺等,其中还采用了buffer以提高速度。所以每条track的最终电容为track 的金属线电容及其连接到该track上的开关的寄生电容。 4.3.2逻辑模块的动态功耗 对于逻辑模块的动态功耗建模,其模型也应该具有通用性,例如应该包含LUT 大小、LUT数目及cluster输入端口数目的信息。其逻辑块上消耗的功耗包括四 个方面:LUT上消耗的能量、输入MUX消耗的能量、触发器消耗的能量及逻辑块 内部节点和线网消耗的能量。 图4—5所示为LUT和MUX的简单结构图:从中可以看出其实际上为一个MUX, 所以我们可以采用转移密度的方法来计算LUT中各节点的转变几率,而对于LUT 中各节点电容可以看作是三个源/漏电容和一个栅电容之和(如图所示的两个红 色节点电容) ~ ~ ~ ~ 图4—5(a)两输入LUT结构图 b)四输入Multiplexer 实际电路中由于这种电路NMOS晶体管的串接,会使电平移位比较严重,所 第44页(共91页) 第4章FPGA功耗模型 以要在最后接~个Level—Shift电路,这种功耗模型采用了SPICE仿真的方式。 输入多路选择器上的功耗:在布线时输入多路选择器用于选择LUT的输入信 号,从结构中可知删X的结构与LUT是相似的,因此其功耗模型也是相似的。不 同点之一在于LUT中的传输晶体管栅极直接连接到布线,因此LUT中的中问节点 受到传输晶体管体效应的影响,所以其电平的跳变小于电源电压,而输入选择器 的传输晶体管的栅极是连接到SRAM上的,我们假定SRAM是由电源电压供电的, 因此在输入选择器中的中间节点不会受到体效应和电压损失swing的影响;不同 点之二在于输入选择器有多种功耗行为,因为在输入多路选择器中,一旦一个输 入被选中(如InO),就会用三个晶体管同时导通,而在LUT中,有且仅有两个 晶体管同时导通。 触发器消耗的功耗:为了求出FPGA中逻辑块中DFF的功耗,通过HSPICE对 DFF在不同的频率下进行晶体管级的仿真,找出其输入密度与功耗之间的关系, 基于仿真结果及Matlab曲线匹配得到计算DFF功耗的公式。 %。云1 +%。‰‘%+%~+厶 D嘞‰。一(-o.074)’DhⅢ+5.2486’D:m 其中Df『w为触发器的输入转变密度,2黼为等效转变密度,%为当DFF状态 发生变化时,电路中发生变化的所有节点电容之和(这个计算需要选择合适的晶 体管大小及DFF电路中的源漏交叠电容)。 4.3.3时钟网络的功耗 假定为H时钟树,时钟网络由一系列的缓冲器来连接时钟可分割线,优化时 钟网络中缓冲器的多少与可分割线的长度取决于FPGA的大小。由于我们要对各 种大小的FPGA都可以计算其功耗,所以要在知道FPGA的大小之后,有方法可以 得到时钟缓冲器的个数及可分割时钟线的长度。得到FPGA中逻辑块个数后,计 算从时钟源到DFF的时钟端的最长路径,然后以RC楼梯网络(Ladder Network) 对该时钟路径进行建模。 第45页(共91页) 第4章FPGA功耗模型 t—ti跳-J--删tax 叩圭主叩筹圭工丽叩主主r—叩i等p-主-一工L丽CwX“ M..f』墨兰N;/盥二 V2’R。(q+q) 、『凡4q 凡、q分别表示单位长度的线电阻和电容,R表示时钟缓冲器的电阻,q、q 4.3.4短路功耗 短路功耗是另一类动奁功耗,当逻辑门输出信号在发生转变时,上拉晶体管 和下拉晶体管在一个很短的时l'日J内同时导通时,电流就会直接从电源流到地,这 个过程中所消耗的功耗就是短路功耗,短路功耗是输出信号转变上升时间、下降 时『自J及负载电容的函数[36][37]。在互连和时钟刚络上,我们用丌关级模型描述 之,而对逻辑单元的短路功耗我们采用的是宏模型的方式考虑之。 为了计算短路功耗,我们对互连上不同size的缓冲器(最小尺寸晶体管构 成的缓冲器)及负载电容(如接一个或多个最小尺寸晶体管构成的反向器为负载) 进行仿真,再对信号转变计算动态功耗。 在我们的编程过程中,为了简便起见,我们认为短路功耗占据动态功耗的 10%[38]。这个百分比可以通过HSPIC仿镇及FPGA的数据表得到,文章[38][39] 运用了该方法,设定短路功耗与动态功耗的比例的平均值。文章[40]引入另一个 参数“”,该参数是输入信号转变时间‘,的线性函数,可以通过线性曲线匹配来 得到该参数值。其方法是,x轴为输入转变时间,Y轴为动态功耗,假定转变时 间为0时的短路功耗为0,因此Y轴的交点即为丌关动态功耗,从而得到“”。 然而运用短路功耗模型计算功耗时,我们需要精确的转变时间‘,[38]文章中假 定输出信号转变时间为缓冲器延时的两倍。于是得到的短路功耗公式为: 第46页(共91页) 第4章FPGA功耗模型 巴一j1+a。以)+%+‰;+∑e 8巨 公式4-6 我们采用SPICE对FPGA中的典型布线通道进行仿真,布线通道上布线开关 连接驱动一个可分割线及其他布线开关。我们发现输入信号是前一级布线开关的 输出信号,其不再是一个阶越信号,而且在FPGA中其输出信号连接大的负载电 容,其也不再是一个斜坡信号,而且输出信号转变信号的10%-90%大大于2倍的 缓冲器延时时间,因此我们对输出信号转变时间进行模型化为‘40’‘啪,其中 ‘哺为接负载时的缓冲器延迟时间,通过SPICE仿真得到不同缓冲器延迟时间对 应的口。 4.4 FPGA静态功耗计算 当电路或一个逻辑门的各信号不发生变化时,电路所消耗的功耗,随着晶体 管特征尺度向lOOnm以下发展,静念功耗在功耗中所占的比例越来越大,将与动 态功耗相比拟[4I]。 在纳米级CMOS器件中,漏电功耗包含反向漏电功耗(Reverse—biased Leakage Power)、亚阈值漏电功耗(Sub—threshold Leakage Power)、漏端引起 势垒降低漏电流(Drain induced barrier lowering leakage)、栅极隧道漏电流 <Gate tunneling leakage)及栅极引入的漏电流(Gate Induced Drain leakage)。 逻辑门的总漏电流是工艺、温度、静念输入矢量及(stake effect of the gate type)的函数。 4.4.1晶体管漏电流计算 研究表明,在上述提到的各种漏电流中,亚阈值漏电功耗占绝大部分 [41][42],反向漏电功耗可以忽略不计。因此采用一阶的亚阂值漏电流模型去估 算其电流的大小F,43],公式为: k@eak_inversfon)=L*exp(等竽)卿-7 其中屹是弱反型与强反型的临界电压值,其公式为;圪;K+型塑 q 第47页(共91页) 第4章FPGA功耗模型 厅,1+q*Nrs+旦 c。 c。 其中,肼是当%:‰时的漏电流;我们采用速度饱和模型[44]来计算该值: , ∥+吃+乞‘(%一巧)2 。(%一K)+E 8k %为栅源电压,K为阈值电压,W为晶体管的宽度,%为等效源漏沟道长度, ‰为电子的速度,E为载流子漂移电流, G为与耗散区相关的电容, k为玻尔兹曼常数1.38e一25 q为电子电荷 T为Kelvins绝对温度 “m为快界面态数目,决定亚阈值电压电流幅度特性的匹配参数,对于每一个温 度都有其对应的“”值。 因此漏电功耗等于电源电压与亚阈值漏电流的乘积: Leakage—Power t I m(weak—inversion)’v,u≯t,ty mlq* 所有的逻辑块、布线开关,不论其是否被使用到,在计算漏电功耗时都应该 被计算在内。而对于各个SRAM单元,用户可以在结构文件中定义其漏电电流以 便在计算SRAM漏电功耗时用到。 f, 但是这种设定…一值等于阈值电压的一半的方法在考虑到stake effect时就 不对了。因此对于开关晶体管的漏电流计算可以采用该公式近似计算得到。 4.4.2 LUT/MUX静态功耗模型 由于FPGA中采用的LUT和MUX都是采用类似的MUX树构成,因此其在静态 功耗模型上也可以采用类似的方法,以下仅以LUT为例来说明MUX的静态功耗模 型。 FPGA中构成组合逻辑的基本单元为LUT,对于一个n输入的LUT,其配置SRAM 共有2n位,根据其2n位SRAM的不同配置,可以表示出2,种函数表达式。 当FPGA完成布局布线,编程配置,位流下载后LUT的SRAM位即被配置为0 第镐页(共91页) 第4章FPGA功耗模型 或l,根据不同的配置n输入LUT可以被配置成27种情况,同时n位输入可以 有2n种组合情况,也就是说对于一个n输入的LUT一共有2r×2n种静态组合 状态。 对于一个rl输入的LUT,假定其输入为口o,..。,q,..4一。,sRAM配置位分别位 %,..’,5,,..‘,5r一,,根据表示02可以知道对于n输入的LUT其表达式为: 2m_1 ,(4。'..q,..以一)5磊。o..q··以一t),乳 公式4—8 其中(口。”q—q—t),表示由40,.-q,..4一构成的二进制数值等于十进制数值j, 。j表示第j为的配置信息,其值可以取1或0;如当口o,..‘ai,--.an_-的值全为0时, 其表示的十进制数为0,则此时j=O,根据此条件可知j的取值范围为[0,2n-1]。 当n输入LUT被配置以后,%,..’,5,,..’,5∥一-分别被置位1或0,为了求解n输 入LUT的静态功耗,我们认为SRAM被置为高电平,其值为电源电压,若SRAM 被置为低电平,其值为0;显然这是合理的。 由于n位输入端连接到传输晶体管的栅级,当晶体管处于漏电状态下,其栅 极有栅极漏电流,但是与漏级的电流相比较,其值也时可以忽略的,因此可以得 到rl输入LUT的漏电功耗为: ‰电功耗。』@)屹+薹,(f少@) 公式们 其中,@)%为Level shift消耗的静态功耗,荟7(f少@)为所有sRAM消耗 的静态功耗,,(f)为通过第i位漏电流,y@)为第i位SRAM的电压,若第i为 SRAM配置为1则y(S)=Vdd,若为0,则y(S):o。 对于一个n输入的LUT,其输入为‰,..…aI~q—t,函数表达式为表达式4-8, SRAM配置为: s,(%,”q,”4一):o(或1) 公式4.10 当输入变量中的一个或多个变量变化时,例如假定输入变为口0,..田一..,吒一-, 其相应的SRAM配置为5』’0。,..一,..-,口一一):O(或1),如果 第49页(共91页) 第4章FPGA功耗模型 3』【40,..4{,.‘4¨J=5,(口。,..’q,..‘,4“) 公式4-ll 根据公式4-9可知,这两种情况下的静念功耗是相等的。 对于n输入的LUT,根掘输入变量的变化,一共有2n种输入组合,SRAM配 置一共有2,种输入组合,根据公式4-10可知,?·2r种组合中,只有22。种独 立的情况。 如图4—7所示,为1输入的LUT电路结构, stare0 sraml ,a 图钾1输入uJlr 表4_3为图4—7所示的l输入LUT电路的静态功耗SPICE仿真得到的结果, 从表中可以看到LOT的静态功耗不仅与SRAM的配置相关而且与输入的高低电平 相关。 \啦入a 1 0 sR盎h 1.8 1.35 1-8 1.35 01 26.72p 17.36p 31.31p 17.35p 10 31.32p 17.36p 26.69p 17.35p 11 716.7f 1.372f 730.4f 1.209f 表4—3 1输入LUT静念功耗 根据图4—7所示1输入LUT电路可知,/ao口=I,由于当sramOosraml=1时, 在sramO和sraml高低电平之间形成了一个通路,所以此时LUT消耗的静态功耗 较sramO‘sraml一1时的静态功耗高。 因此当输入为‰,..‘,q,..4一时,通过5j 1%,..q,..以一-J的电流与公式4-10的 值相关,假定aO最低位,an一1为最高为,5,I%,...as,..4一J为40,...,q,..·an一·信号 输入对应的SRAM配置位。 s』(口o….ai,...an一1)o Sj*00,…q,…,an—I) 其中i∈[0,n-1]。 如果按照公式4—10计算:根据i的不同取值,需要对sj位进行n次电流计 算。根据LUT的基本电路结构可知,如果5,(口。,..q,”·an—t)位与5,‘0 o,.“”..,口一) 位能形成通路,其通路中一共需要经过2(i+1)个晶体管,其中i+1个晶体管处 于截至状态,其漏电流对一I%,..丑一’·au—t J位总漏电流影响可以忽略不计,因此 第50页(共9l页) 第4章FPGA功耗模型 为了简化模型,我们采用了低2位取反对应SRAM异或表达式来近似计算通过sj 位的漏电流。 :扛:扛 图4—8相邻SRAM互异的情况 图4-8所示为相邻SRAM互异的两种情况,图a中上晶体管处于导通状态, 但SRAM接低电平,下晶体管处于关断状态,总的输出端口为低电平,通过该通 路上的漏电流与5,‘ao,a1...ai,..·,4一)位的配置情况的影响可以忽略不计;但是对 于图(b),上晶体管处于关断状态,下晶体管处于导通状态,其总体输出端口的 电平受到已+(口。,4一”q,..·,%一-)位配置的情况较大,因此在我们的模型中对这两种 情况要分别考虑。 根据以上的分析,当LUT输入为“。,..埘一.卫一,SRAM配置为3,(%,..q,..以一t) 时,通过SRAM s(n o,.·.61f,.·五¨)、s(a0,.·五∥·.口¨)端口的漏电流分别为: ‘(5。。”‘q”』一J)。Lj(Ⅱ””q”·以一)‘o) 。‘·j‘(口。,a—l。q,...,‘一.)+‘·(1-,。(4。,互.,q,…,Ⅱ。)) t(s瓴,.q,.q。·o,s(五,¨q,“q。;t) -之 f(,D∥.q,。一·一Lj(五,q,.也。一1) .‘·,(‰,二.。q川~aH,)+j。·(1-j’14。,a—i..q,¨~aM。)) 其中iO、i1、i2、i3、i4我们通过SPICE仿真得到的漏电流。 由于我们是采用了低2位取反对应SRAM异或表达式(07),同时考虑到 s(口。,..4一·aftn—t)位对漏电流的影响,因此通过任意的两个相邻的SRAM s0。,..口一·4一一、s(Ⅱo,.·ai,..露一)的漏电流可以表示为: z(‰五%M靠矗¨l。) -∑f‘f(s一:) f(s(a。,…i,~—,一一-)l。,s(蠢,…i,“—z一一·)11) 一i2 第5l页(共91页) 第4章FPGA功耗模型 z(‰纛¨都“知一M) z Vi‘厂(s。,j:) 其中,@,Jz)表示配置位sI、s2配置信息之间的关系式,i对应于不同配置 得到漏电流值,s1、s2分别为: st—s(ao,…,ai-i,af,...an—1) 屯=s(ao,…ai 2ai-1a∥.4m一1) 如果30。,..q,-.丑一-1)与5(%,..q,..4一)只有一位取反,即只有ai位不同时, 需要考虑5(口o,..q,..以一,)配置位对其漏电流的影响,因此此时的f(s1,s2)变为 f(sO,sl,s2)。 得到各个SRAM漏电流后,根据公式4—9计算便可以得到LUT的漏电功耗。 4.5本章小节 本章主要介绍了电路功耗计算的基本方法和概念,介绍了应用到FPGA功耗 模型中的混合是功耗模型,包括动态功耗模型和静态功耗模型。动态功耗的计算 采用基于节点状念转换率的丌关级动态功耗计算和逻辑块宏模型,静态功耗则采 用基于公式计算的晶体管漏电功耗模型和逻辑块基于仿真的LUT/MUX表达式 计算模型。这些功耗模型将运用到我们后面的功耗计算和基于功耗驱动的布线算 法中。 第52贞(共91页) 第5章FPGA布线研究々实现 第5章FPGA布线研究与实现 布线模块是FPGA软件系统中的关键部分,位于逻辑映身寸模块、布局模块之 后。其功能是在已经布局好的用户设计网表结果的基础上,利用FPGA芯片中的 可编程连线资源来实现布线。布线模块接受来自布局模块的输出文件,输出各线 网在芯片中的具体连线方式。 布线模块以第3章FPGA芯片的布线资源结构为设计原型,在此基础上进行 布线算法的研究与实现。 在布线过程中主要考虑线网的布通率及电路速度,算法上采用迷宫算法实 现,对于速度的优化主要是通过寻找最短路径来达到的。 5.1基本搜索算法 关于搜索算法有宽度优先搜索算法[45](Breadth—First Search)、深度优 先搜索算法[46](Depth First Search)、Dijkstra最短路径搜索算法[473等。 对于FPGA布线模块来说,可以将布线问题转换为一个有向图上的多源点多终点 的路径搜索问题,下面我们首先对基本的搜索算法作一简单回顾。 宽度优先搜索算法是处理有向图、无向图中,从一个顶点出发,识别所有可 到达顶点的方法,这种算法可以保证源点和终点之I’日J连接的存在。 Dijkstra最短路径搜索解决了具有权重的有向图、无向图中,单源节点的最 短路径问题,其中边的权重值为非负值,如果是具有负值权重的边可以利用 Bellman—Ford算法解决。当所有边具有相同的权重时,采用宽度优先搜索即可 实现最短路径搜索。 直接搜索算法又称A术算法,是人工智能中一种典型的启发式搜索算法。 启发式搜索就是在状态空间中的搜索对每一个搜索的位雹(节点)进行评估, 得到认为最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏 的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用 了不同的估价可以有不同的效果。 启发中的估价是用估价函数表示的,如: f(n)=g(n)+h(n) 其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点 的实际代价,h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n) 体现了搜索的启发信息,因为g(i1)是已知的。如果当h(n)>>g(n)时,就可以 第53贞(共91页) 第5章FPGA布线研究与实现 省略g(n)而提高效率。 启发式搜索其实有很多的算法,比如:局部择优搜索法、最好优先搜索法等 等。这些算法都使用了启发函数,但在具体的选取最佳搜索节点时的策略不同。 局部择优搜索法,是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点, 父亲节点,而一直得搜索下去。这种搜索的结果很明显,由于舍弃了其他的节点, 可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不一 定是全局的最佳。最好优先搜索算法时,并不舍弃节点(除非该节点是死节点), 在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳 的节点”。这样可以有效的防止“最佳节点”的丢失。 如果一个估价函数可以找出最短的路径,称之为可采纳性。 A}算法是一种最好优先算法,但是加上一些约束条件,同时胁算法是一个可 采纳的最好优先算法。 A}算法的估价函数可表示为: f’(n)=g’(n)+h’(n) 其中,f’(r1)是估价函数,g’(n)是起点到终点的最短路径值,h’(n)是n到目标 的最短路经的启发值。由于这个f’(n)其实是无法预先知道的,所以我们用阿面 的估价函数f(n)做近似。g(n)代替g’(n),但g(n)>=g’(n)才可(大多数情况 下都是满足的,可以不用考虑),h(n)代替h’(n),但h(n)<=h’(n)彳可。 在FPGA时序驱动的算法中,由于考虑到算法复杂度问题,我们也采用了[48] 中提到的斛算法来代替了基本的宽度优先搜索算法[49],具体实现在本章后面 将会介绍。 迷宫算法Maze[50]:是基于线网的布线算法的代表,原始的Pathfinder算 法[51][52]、VPR布线算法均是基于该算法而实现的,本文提到的布线算法核心 也是采用Maze算法来实现的,只是针对特定的目标要求在节点代价函数上作了 改进也满足命线要求。 5.2基本概念 如何将FPGA布线问题转换为图论上算法实现的问题,是我们实现FPGA柿线 的首要问题。根据我们在第3章FPGA结构描述的介绍可知,FPGA硬件结构是由 重复的逻辑单元和布线资源构成,因此下商我们将介绍FPGA硬件和电路转换为 图论上可以处理的图的方法。 第54页(共91页) 第5章FPGA布线研究LJ实现 5.2.1布线资源图 布线资源图(Routing Resource Graph)是在程序内部实现具体的FPGA芯 片结构的一种方式,布线资源图描述了FPGA芯片内部的连接关系。在构建柿线 资源图的过程中,每一个硬件资源,包括逻辑单元的输入输出端口,每一条连线, 都对应于一个节点;而每一个编程开关则对应于有向边;这样布线模块所用到的 硬件资源都已经包括在布线资源图中。布线模块的所有具体实现都在布线资源图 上进行。 图5-1列出一个简单逻辑单元及其连线资源和对应的布线资源图的例子。在 布线资源图中每一个节点都有各自的编号而这个编号的值是唯一的,也就是说只 要知道节点的编号的值,就可以找到是哪一条布线轨道或逻辑单元的输入输出管 脚。在另一方面,只要知道布线轨道或逻辑单元的输入输出管脚,就可以找到是 哪一个节点。 wire3 wire4 wirel wire2 图5-1布线资源图实例 sink 5.2.2逻辑块 逻辑块对应着一定的硬件部件,如CLB、I/OB、MULT、BRAM等,在转换为布 线资源图时我们主要考虑节点的连接度,即节点的扇入和节点的扇出度,而如果 还要考虑时序等问题,则需要在节点上添加属性即可,图5-2表示一个逻辑块的 第55页(共91页) 第5章FPC谴布线研究与实现 一个输出节点和一个输入节点的属性,从图中可以看出输出节点outpinl可以连 接到布线通道中的track0、track2、track4三条布线资源线网,而输入节点 inpinl也可以连接到布线通道中的track0、track2、track4三条布线资源线网, 但是它们的连接关系一驱动关系不同,根据前面对布线资源图的介绍可知,布线 资源线网track0……track5有唯一的标识,其在布线资源图中也是一个唯一的 节点,如图5—3分别为逻辑块上输出节点和输入节点构成的有向图,有向边分布 表示开关的类型(具体参看第3章FPGA结构描述)。 outpinI inpinl lI ll 图5-2逻辑块节点描述实例 track0 trackl tracJ(2 track3 track4 track5 第56页(共91页) 第5章FPGA布线研究与实现 4 图5—3逻辑块输出、输入节点图 5.2-3布线资源线网 布线资源线网是指FPGA中的不同类型布线资源线的总称,根据第3章中介 绍可知,基于Tile的FPGA结构描述方法中各个基本T订e和相应Wire模块是一 样,但是由于Wire模块实现的是各个Tile之间的拼接工作,它们是以金属线直 接相连的,中间没有编程开关,因此在布线资源线网上是属于同一条线,在布线 资源图中是相同的标识来表示它们。 图5—4所示为两个相邻的T订e之『自J的拼接,拼接通过Wire模块来实现,Tile 内部本身具有线网与逻辑块引脚、线网之问的驱动关系,如图中track0…… track5表示就是佰线资源线网,track2、track3与相邻T订e的track2*、track3* 之问是通过会属线网连接的。 wire 图5—4基本Tile的拼接及布线资源线网实例 因此在将这些track之间的驱动连接关系在布线资源图中表示出来如图5—5 第57页(共91页) 第5章FPGA布线研究与实现 所示,其中的会属线相连的track用唯一标识表示,图中track2和track2*、 track3和track3*分别用track2、track3表示,以此类推可以得到 track4……track7等线网的布线资源图。 图5—5布线资源线网布线资源图实例 5.2.4电路线网 电路线网NET(s):在逻辑电路连接关系上,线网表现为一种连接关系,不同 逻辑单元的引脚端口连接在一起构成一条线网,一般的线网只可以有一个源端 Source作为信号的驱动端,线网可以有多个终端Sink作为信号的被驱动端,逻 辑块的输出引脚可以作为Source,逻辑块的输入引脚可以作为Sink。而对于特 殊线网比如总线是具有多个Source而只有一个Sink(该Sink为总线BUS通道)。 如图5—6所示为BUS电路线网,图5—7所示为普通电路线网,图中箭头表示为引 脚的属性,同时也表示出线网的驱动关系,图中的虚线表示为FPGA布线的一种 可能实现方式。 第58页(共91页) 第5章FPGA布线研究’j实现 Bus 图5-6多源单终点电路线网实例 口口口一口 图5—7普通电路线网实例 在布线模块中,输入的文件包含了逻辑块的具体位置及线网的逻辑连接关 系,但是没有具体线网的走线方式,布线模块就是要确定这些线网在FPGA布线 资源上的具体走线方式,即确定图5-6、5-7中虚线的具体连接关系。如下图5—8 表示为一个具有1个源节点5个终节点的线网、一个具有4个源节点1个终节点 的电路线网图。 第59页(共91页) 第5章FPGA布线研究与实现 源 ◇ 终点 图5-8多端线网实例 5.3 FPGA布线算法 在介绍了基本搜索算法和FPGA布线资源图的概念之后,我们将介绍FPGA布 线的基本算法。 根据前面的介绍,我们已经知道FPGA的布线实际上是在布线资源图一有向 图上,根据电路线网的源节点和终节点的位置,搜索出可行的走线方式,同时要 保证各个电路线网之间没有节点的冲突和拥挤。 因此在FPGA布线中,首先要考虑的就是FPGA的布通问题,只有在此基础上, 对其他目标的优化才显得有意思。随着电路频率的增大,在电路布通的前提下, 电路时序问题也越来越显得重要了,而随着晶体管工艺尺寸的下降对于功耗的问 题也渐渐成为电路设计者需要考虑的对象;在行通的前提下,如何充分利用各种 线网资源,做到线网资源的有效利用,也是近来研究的一个方向,因此在接下的 几个小节中,我们将介绍FPGA布线中需要考虑的几个方面,包括最基本的基于 布通率的FPGA布线算法、时序驱动的布线算法及在考虑功耗和线网有效利用率 的基础上对算法的改进,同时就具体算法实现过程中的一些算法优化也做介绍。 5.3.1布线算法背景 学术上的FPGA器可以分为两大类,其一是全局一详细组合布线,这种布线方 式一步就可以完成FPGA的布线,这种方法以[21][53]等为代表。另一种方法是 分为两步实现布线:第一步运行全局布线决定每条线网所使用的备个逻辑单元的 引脚和可使用的可分割线通道,第二步运行详细布线根据第一步的结果,在允许 的使用的可分割通道中连接各个线网。由于FPGA布线通道资源的有限性,详细 布线在FPGA布线中显示出其重要性和难度。 不管采用那种布线方法,FPGA布线算法中,其核心算法都是采用各式各样的 第60页(共91贞) 第5章FPGA布线研究与实现 Maze布线器来连接各条线网的各个终点,而Maze布线器其核心又是采用 Dijkstra的算法,在线网的源节点和终节点之间搜索最短耗费(cost)的路径。 在各种算法中,为了衡量布线结果好坏的函数而提出目标函数 (costFunction)的概念,通常值越低表示布线结果越好,而对于不同布线优先 考虑对象,目标函数也相应发生改变。 5.3.2基于布通率的布线算法 根据前面的介绍,FPGA的布线资源及其连接关系可以转换为布线资源图来描 述,假设其为有向图G=(V,E),其中V就是布线资源图中的节点,E表示连接 节点之间的开关。而电路线网以Ni来表示(其中i表示第i条电路线网),根据 I;i『面的定义可知,Ni是线网源节点s。和终节点t,。的集合,Ni是V的一个子集。 因此布线算法就是要在有向图G中寻找连接所有Ni的轨迹,而且要保证所有轨 迹不冲突。 在这罩首先引入节点的费用的概念, 节点费用函数又称为节点代价函数,是 指使用该节点所需要的代价,代价越小, 说明使用该节点完成御线的可能性、成 功性越商,相反代价越大,则表示我们尽量不要采用该节点。因此代价函数实际 上表示的是资源可用度因子,用于表达布线资源的富裕程度,需要使用某一个布 线资源的线网越多,该资源的可用度越小。为了算法中计算Cost的时候方便, 规定如果某布线资源的资源可用度越大,相应的资源可用度因子数值越小,线网 从该布线资源经过的Cost就越小。在这罩,我们定义节点的代价函数为如下公 式: Cost(n)=b(n)宰h(13)木p(n) 公式5-1 其中b(n)表示使用该节点的基本代价,该值可以根据节点不同类型或目标 函数的不同设定不同值,也可以设置相同值,在这罩我们设定为1;h(11)是在 迭代过程中,前一次的拥挤度(节点被使用的情况),P(n)为节点当前被使用 的次数。 在我们的FPGA路径搜索算法中,由于是多线网问题,所以算法实际可包含 两个部分:单个线网布线和整体布线。前者在一次布线中采用最短路径算法(宽 度优先搜索)仅完成单一线网的布线,后者是通过调整稚线费用Cost在调用前 者的基础上完成电路中所有线网的布线,直到所有节点都没有冲突,所有线网都 可以布成功。 在这两个过程中,对于多端线网调整节点布线费用Cost的方法,所有布线 算法都采用撕裂(Ripped—up)和重布线的方式,采用不同的路径以解决布线资 源的冲突(或者是为了减小关键路径时延、提高电路速度或为满足其他要求而作 第61页(共91页) 第5章FPGA布线研究与实现 的优化)。而对于所有的撕裂和重新布线的目的都只是改变线网的布线顺序,其 布线器均是采用Maze布线算法。 从这里可以看出,基于线网的布线算法都无法避免布线顺序对布线质量的影 响,可以单独或并用以下方法提高性能:一、布线之前对线网排序,精心设计排 序算法;二、应用“拆线重布”算法。 布线算法的排序策略包括两点:多个线网布线时的排序策略和一个线网的多 个Sink布线时的排序策略。 一般说来,对多端线网布线的时候,如果线网的扇出数目(即Sink数目) 大,则线网在FPGA芯片上分布的范围也大,对布线资源的要求也越高。如果将 扇出大的线网放在后面布线,这时芯片上许多区域的布线资源已经被占用,线网 布线的成功率不高。所以,算法在对多个线网进行布线的时候,将根据线网扇出 数目进行递减排序。实验证明,这样排序后对布通率有一定的改进。 在对多端线网进行布线的时候,实际上是将多端线网分成多个两端线网依次 布线。采用Maze布线算法(Oijkstra)来对每一条net进行布线时,线网出输出 开始向外扩展直到找到目标节点,然后算法把先前稚好的路径上的所有节点作为 源节点使用Maze布线算法进行下一节点的搜索。如图5-9所示,在完成终节点 a时,将所有从源节点s到a路径上的所有节点将作为当前线网下一个终节点搜 索的源节点(Cost=0),使得对终节点b的搜索扩展从图中只需要从X节点丌始即 可,而不需要从源S重新丌始搜索扩展;同理对于C的搜索只需要从节点y丌始 即可,这样有可以节省搜索的时间。 第62页(共91页) 第5章FPGA布线研究与实现 口口佃 口|口口 口口口 图5—9多端线网搜索扩展 对于图5—8中,同时又设计另外一个问题,即在对多个Sink进行布线的时 候,就涉及到先布近的Sink还是先布远的Sink的问题。在我们的算法中是先布 近的Sink,这样可以减少布线结果拥挤度,有利于布通率。因为先钷近的Sink, 如图5-10a所示,在布完这条两端线网后,现有的布线结果可以自然的扩展到远 的Sink。而如果先布远的Sink,如图5-10b所示,则其后所句的各个Sink都离 第一个Sink较远,在这种的布线结果中布线资源的复用率很低,将影响布通率。 口口口口口口口口 口口口口口口口口 口●口口口口口口 口口l口口口口一口 口口l口口口口口口 口口l口口口口口口 口口l口口口口口口 口■口口口口口口 口口l口口口口■口 口口l口口口口l口口 口口l口口口口l口口 口口I口口口口I口口 口口I口口口口口口 口口■口口口口口 Source 口口I口口口口I口口 口口■口口口口口 Souroe (a) (b) 图5—10多端线网布线示例 第63页(共91页) 第5章FPGA布线研究与实现 布线算法伪代码 定义:b(n)为使用节点11的基本代价 p(n)为节点13的当前拥挤度 h(n)为节点n的历史拥挤度 Cost(n)表示使用节点n的代价 令net(i)表示当前布线线网 RT(i)表示该线网上的所有节点 Crit(i,j)表示该线网J节点的关键度 对所有线网和线网终节点初始化Crit(i,j)=1 While(存在拥挤度时){ For每条线网net(i){ 分裂原有布线,更新相关节点的P(11) RT(i)只包含源节点 对线网net(i)的每个终点,按Crit(i,j)降序排列{ PriOueue=RT(i)中按Cost(n)的优先队列{ While(终点J没有找到){ 移除PriOueue中Cost最小节点,赋值给节点m f 将节点m的所有扇出添加到PriQueue } }End While For(从RT(i)到节点j的所有相关节点){ 更新P(n) 将节点加到RT(i)中 }End While } } }End For 更新所有h(11) 更新Crit(i,j)//如果采用时序驱动布线 }End While 从上面的伪代码可以看出,在迷宫布线算法中,一条两端线网布线的复杂度 是0(N2),其中N是有向布线资源图中端点的数目,而FPGA的布线资源图中节 第64页(共91页) 第5章FPGA布线研究‘,实现 点数目将会是很多大的,所以如果有效减少N(去掉布线资源图中,不可能的用 来实现当li{『线网布线的节点),就可以有效的减少布线时问。为了提高布线的速 度,我们的布线算法中采取了布线范围约束以提高布线的速度。即:线网布线仞 始布线时不允许线网从超过线网边界框(Bounding—Box)n个以上布线通道以外 的地方走线,如图5一ll所示。如果本次布线失败,则下次拆线重向的时候,将 n增大,即增加可用的布线区域。n的大小和实际的芯片结构有关,如果芯片布 线资源丰富,布线压力小,则n可以取较小的值,反之取较大的值。 布线约束区域 口口 ●口-●口-●口-●口… 口口 口口 口口口口 口口 口口 口口口口 图5-11布线约束区域示意图 口口口口口口一口 口~口口口口一口 口口口口口 在FPGA布线中,当布线资源不足时,我们还可以考虑利用FPGA逻辑块来实 现布线,如图5-12所示当源节点和终结点附近的布线资源都被使用时,如果仅 仅依靠布线资源无法完成布线时,考虑到逻辑块内部可以通过编程节点控制,使 该逻辑块作为一个布线资源来使用,完成输入到输出的编程直通 (ROUTING-THROUGH)。 第65页(共91页) 口 第5章FPGA布线研究与实现 口 ● ● 口 图5—12利用逻辑块实现布线 5.3.3时序驱动的布线算法 前一小节介绍的是基于布通率考虑的FPGA布线算法,随着电路工作频率的 不断提高,用户对下载到FPGA上的电路的时序要求也不断提高,因此在实现电 路在FPGA布通的基础上,也需要考虑电路的时序问题。本小节将介绍FPGA基于 时序驱动的布线算法,基于时序的布线算法是采用线网、逻辑块的延时模型,运 用时序分析器计算各条线网路径的时延,确定哪些线网处于或接近关键路径延 时,在靠线过程中给这些线网更高的布线优先权,以降低关键路径延时,提高下 载到芯片上的电路工作频率。因此本小节将首先介绍时序驱动布线中用到的时序 模型,再介绍时序驱动算法。 5.3.3.1 FPGA时序模型 FPGA中时延包括逻辑块内部时延和布线资源上线网时延。在本时延模型中分 第66页(共91页) 第5章FPGA布线研究与实现 别这两种时延采用不同的计算方法:对于逻辑块内部,由于其路径的有限性,可 以通过SPICE模拟仿真得至Ⅱ逻辑块内部所有路径的时延;布线资源上的线网时延 是FPGA时延的主要部分,线网时延是指从线网的源端source到该线网的终端 Sink之间的时延,其目的是决定布线后的电路的速度、决定布线时的不同线网 拓扑结构的时延。理想情况下,通过SPICE仿真可以得到精确的仿真值,但是布 线线网数目有成千上万条,用SPICE仿真是不明智的,因此采用了在布线中广泛 应用的的时延模型是一--Elmore模型[54]。 采用Elmore模型进行连线延时计算时,对FPGA布线资源中的传输晶体管、 三态门及金属线进行Rc电路的等效替换,以得到布线资源线网的Rc树 (RC—Tree)。图5~12至图5一14所示为FPGA布线资源中传输晶体管、三态缓冲器 及金属线的Rc等效电路。 础{ }diff (a)馅输晶体管 (b)譬通时 (c)关闭时 图5一12传输晶体管时延等效电路 至R, L// (a)三态门 Cbu面厂 Cbu本ut 上 上 一(”导通时 一 ‰ C 上呵一 上雷一 (c)必闭时 图5—13三态门时延等效电路 厂——^^^r] cwire陀】 Rwhe Icwir眈 T T 占一((””等等效效模 模型 型’ 占 图5—14传输线时延等效电路 因此,线网源点与终点路径的Elmore时延可以采用如下公式: E“¨焉芝:nt mn Ri。C(subtree,)+K 公式5—1 其中Tdi为第i个元件的时延,则Tdi为缓冲器,则Tdi为其时延,否则Tdi 第67页(共91页) 第5章FPGA布线研究与实现 等于0;Ri为第i个元件(Rwire,Rbuf或Rpass)的等效电阻;C(subtreei)为第 i个元件处的子树的电容总和。 5.3.3.2 FPGA时序驱动布线中的时序分析 在进行FPGA时序驱动布线中时序分析模块前,我们需要在5.2小节的基础 上,引入时序分析图(Timing Analyzer Graph)的概念。 源 图5—15时序分析图 时序分析图是为计算线路线网时序而引入的一个概念,图如5—15所示(该 图和5—7和图5—8类似),其中每个逻辑块引脚都是一个时序节点(Timing Node), 两个引脚之间不论其具体走过的路径,用一条时序边(Timing Edge)连接,构成 电路的时序分析图。正如图5一15所示,表示一个线网的时序分析图,线网的驱 动节点为源节点,线网所驱动的逻辑块引脚作为被驱动节点在时序图中为终节 点,它们之间用一条边来表示,而所有边是通过FPGA布线资源来连接起来的, 所有边的时延都标注在边上,而不是标注在节点上。 从时序分析的起点到目标节点所需的延时称为目标节点的达到时间 (Arrival Time),时序分析的起点可以是电路的原始输入节点,也可以是触发 器的输出节点,我们规定时序分析的起点的到达时『自J为0,其他节点的达到时间 计算公式如下: 乇砌,(f)=讹%∈扣nin(f){乙砌Ⅲ)+de切(埘) 协音;, 其中:delay(j,i)为节点j到节点i所通过的路径上的时延。 根据该公式可以计算出时序分析的终点(电路的原始输出节点、DFF的输入 节点)的达到时间,定义该时间为电路的最大延迟时间Dmax,以此确定电路下 第68页(荚91页) 第5章FPGA布线研究与实现 载到芯片上的工作频率。 通过以上的方法可以求出基于Elmore模型的电路最大延时、最小时钟周期 和电路的最大工作频率,同时也可以求出任意两个节点之间的延时。 但是在基于时序驱动的布局布线算法实现中,我们同时希望知道两个节点之 间的连接时延对整个电路时延影响的情况,即如果该对节点的时延增加,是否会 引起对整个电路时延的增加,以及该源终节点之间延时可以在哪个范围内变化而 不引起整个电路时延的变化,即不会引起关键电路路径的改变,因此引入了要求 时问(Required Time)和松弛时间(Slack)的概念。 要求时间的计算公式如下: Z掣ired(O=施行W的删(f){Z哪删(,)一如忉O,.,)) 公式5-3 其中规定时序分析的终点的要求时间为Onyx,采用反向宽度优先搜索计算其 他节点的要求时间。 图5—16逻辑块内部延时实例 公式5—3中的delay(i,j)不仅表示边延时,而且可能是逻辑块的内部延时; 如图5一16所示,时序分析的终点(电路的原始输出节点、DFF的输入节点)的 要求时间为Dmax,通过反向搜索求出时序分析图中各个节点的要求时间。 松弛时间是用来度量节点与关键路径节点之『自J的关系,松弛时间为0的节点 处于关键路径上;松弛时间大于0的节点如果在增加一定范围内的延时,不会影 响电路的工作频率;松弛时间计算公式如下: slack(i,歹)2‰删(圹瓦砌,(i)一delay(i,j『) 公式5.4 综上所述,通过延时模型及线网的具体连接关系,可以得到该线网的源节点 第69页(共91页) 第5章FPGA布线研究与实现 到线网所有终点之间的延时,最终求出电路的最大延时路径和最大延时时『自J;通 过反向宽度优先搜索可以计算出各个节点的要求时间,进而计算出线网源节点与 线网所有终节点之间的松弛时间,至此我们FPGA布线所用到的时序分析已经结 束,要特别提醒的是,我们这里的时序分析并不要求与稚线结束后的时序分析的 模型一样精确,这里的时序分析只是和线模块的一个子模块,在每次布线迭代完 成后都要重新作一次布线时序分析,因此需要在保证一定准确度的情况下尽可能 提高时序分析的速度。 5.3.3.3 FOGA时序驱动布线 由于在FPGA布线算法中,电路能够在FPGA布线资源上布通永远都处于优先 考虑的位置,因此在FPGA时序驱动布线中,我们需要采用延时和拥挤度综合考 虑算法。在算法中通过每种连接的拥挤度一延时折中度来控制节点的选取,而每 种连接的拥挤度一延时折中度是由其与关键路径相比的危险程度(critical)来 控制,即关键路径的连接采用尽可能短的延时路径,即使这种情况会产生其他节 点拥挤度问题,而对非关键路径的线网就用长一点却不会产生拥挤度问题的路径 柬连接。 考虑时序的布线算法需要对节点Cost进行修改,使Cost中包含节点的时序 信息,以便在布线搜索中优先考虑时延小的节点,修改后的代价函数表达式如下 所示: Cost∽)搴一Crit(i,,)·delayO,topology)+【1一Crit(i,,)】‘Cost0) 公式5-5 Cost0)一60)·矗O)·pO) 公式5-6 删∽;一(№m一卷笋㈣ 公式s刁 其中Cost(n)和基于布通率的代价函数表达式一样的,包含节点的基本代价、 上一次拥挤度、当前拥挤度;公式5—7中Dmax为关键路径时延,slack(i,j)为 第i条线网源与第j个终节点的松弛时『自J,rI、MaxCrit表示该连接的时延与拥 挤度折中系数。当公式5-7中的MaxCrit=1、Tl=1时,则节点危险度表达式转 变为: 啪叫M一篙} 该种情况表示具有0松弛时间,即关键路径上的连接可以完全忽略拥挤的费 第5章FPGA布线研究卜j实现 用,而当MaxCrit=O时,算法完全忽略所有线网连接延时,而仅仅考虑拥挤度 费用,算法就变成了基于布通率的布线算法。经验表明,MaxCrit=0.99、rl=l 比MaxCrit=l具有更好布通率;而当MaxCrit=l时,有两条关键路径上的节点共 享一个节点时,将没办法解决布通率问题。 接下来还有定义一个路径费用的概念,路径费用表示已靠线资源路径1到节 点n的代价值的总和,其表达式如下所示: PathCost(n)= >1 Cost(1) 1Epam fr盖RT(i)to“ 公式5—8 当每次找到线网的一个sink时,Crit(i,j)和delay(n)都会发生变化,因此 当一个sink到达时对于优先队列中存储的每个PathCost值都将变得无效,因此 不能采用基于布通率中提到的将已布线的路径上节点作为下次扩展的源节点,即 将所有路径上节点Cost设置为0的方法。因为在基于时序驱动的布线算法完成 时,即每当一个sink到达时,优先队列被清空,而不能继续作为扩展的节点使 用,算法需要重新计算每个节点COSt后再进行搜索,这样会导致搜索速度变慢。 因此在时序驱动的稚线算法中,我们采用了直接搜索算法,在每一次节点扩 展时对节点进行评估,减小没有必要的搜索。 为了在布线中使用直接搜索算法,需要预计出从当前节点到目标节点总共的 估计费用值ExpectedCost(n),对于源节点和逻辑块输出节点定义其估计费用值 为0,因为一条线网只有一个源节点、大多数情况下输出节点在MAZE扩展中不 需要进行尝试搜索。 为计算ExpectedCost(n),假定:1、从当前节点n出发,连接目标节点J, 使用与n具有相同类型的可分割线;2、沿最短路径上的各个节点不存在拥挤度 问题,即对于所有节点P(m),h(111)均等于1。 由于当前布线节点(n)和目标节点(j)都在FPGA芯片资源表示的范围内,通 过计算在连接目标节点和当前布线节点,所使用的与当前节点具有相同类型的可 分割线的总数,根据该信息,我们可以计算出连接两节点所使用的所有开关,因 此可以计算出目标节点的Elmore延时;作为目标估计费用,使用如下公式计算 出节点n的总费用。 TotalCost0)一PathCostO)+a’ExpectedCost0,J) 公式5-9 其中a表示采用直接搜索的程度,a=0即变成宽度优先搜索算法。 时序驱动的布线算法伪代码如下: RT(i):当前处理的线网i的结点集合,同时储存了延时信息; PQ:是一个储存了当前扩展Ij{『沿结点信息的队列 第71页(共91页) 第5章FPGA布线研究与实现 包含TotalCost(n)、PathCost(B)等信息,按TotalCost(n)排序: StoredTotalCost和StoredPathCost:储存布线资源图结点的使用成本信息 Crit(i。J)=MaxCrit//初始化所有线网所有终节点危险度为最大值 Whi le(存在布线资源节点的冲突){ For(每条线网i){ 撕裂RT(i)并更新受影响节点的P(n)值 RT(i)=NetSource(i): For(按照crit(i,J)排序){ 计算PathCost(n)、TotalCost(n) PQ=RT(i)//TotalCost(n)=Patheost(n)+@*ExpectedCost(n) While(终点sink(i,j)没有找到){ 移除PQ队列首元素m if(TotalCost(m)<StoredTotalCost(m) 而且PathCost(m)<StoredPathCost(m)){ StoredTotalcost(m)=TotalCost(m) StoredPathCost(m)=PathCost(m) For(节点nl的所有扇出节点n){ 将节点n存入PQ } } ) For(到终节点sink(i,j)的所有路径上节点n){ 更新P(n): 将节点n存入RT(i) } 更新RT(i)中节点Elmore模型Rc值 For(对扩展中的所有节点){ StoredTotalCost(m)=无穷大 StoredPathCost(m)=无穷大 } ) } 更新所有节点的h(n)值 第72页(共91页) 第5章FPGA布线研究与实现 运行时序分析计算Crit(i,j)值 ) 5.3.4基于功耗的布线算法改进 随着半导体工艺水平的不断提高,晶体管尺寸的不断减小,FPGA功耗已经越 来越成为硬件设计者需要考虑的问题,从FPGA结构上考虑的低功耗设计学术上 也有很多研究,包括双阈值电压、双电源电压等方法,还有其他结构上的改进, 但这些都是在改变FPGA结构的基础上的,我们这罩提出的基于功耗的布线算法 是在第四章功耗模型的基础上,对电路动态功耗的考虑,是从算法上的考虑,与 具体的硬件结构没有关系。 在基于功耗布线中,我们在考虑到延时关键度和线网拥挤度的情况下,我们 将目标代价函数修改为: Cost∞)一Crit(i,,)‘delay0)+[1-Crit(i,1)1‘ 【ActCritff)‘capO)+(1-ActCrit(i))。6∽)‘JIl0)‘pO)1 公式5一lo 其中cap(r1)表示与布线资源节点n相关的电容,ActCrit(i)表示第i条线网的 转换密度指数(参考第4章),其表达式如下: ActCrit(i);mill(-Activity(i!..,。MaxActCri)vy 其中Activity(i)是线网i的转换密度,MaxActivity是所有线网的最大转 换密度,MaxActCrit为最大转换密度线网对应的最大转换密度指数,我们设定 其为0.99,这正如时序驱动布线中设定MaxCrit为0.99一样,设定为0.99可 以避免最大密度转换率线网完全忽略拥挤度参数,而引起无法布线。 在该公式中时序相关项没有变化,还是使用采用Elmore模型计算得到的时 序分析。 5.3.S提高线网使用率的改进 最新研究表明:不同布线可分割线的延时基本上是个常数,因此在源点和终 点之间所经过的可分割线的总数,而不是两点之间的Manhattan距离,是控制布 线延时和费用的关键所在。因此布线目标函数可以确定为:使用最少的可分割线 第73页(共9l贞) 第5章FPGA布线研究々实现 总数并且合理分配各种布线可分割线。 有效的布线资源利用率(Efficient Routing Resource Utilization)包括 可分割线的有效使用效率和可分割线的使用效率两个概念。 5.3.5.1 提高可分割线的有效使用效率 提高可分割线的有效使用效率,可分割线的有效使用效率是指可分割线实际 使用的长度与可分割线的比值,因为一旦可分割线的一部分被使用,其他部分将 不可以再被用作布线资源使用,降低了分割线的有效长度。如图5—17所示:6 倍线、双倍线和单倍线作为一倍线时的有效使用情况,其有效使用率分别为1/6、 1/2、1,因此从提高线网使用率的情况来看,在选择布线资源时,要考虑实际分 割线的有效使用情况。 图5一17分割线有效利用率使用情况 下面为提高可分割线有效使用效率的策略,在原算法基础上,根据节点的相 对位置动念调整节点基本费用,而在原有算法中节点的基本费用根据节点的类型 来确定的。 nodeWeight[Node][DisteFromCLB]:表示目标节点的权重随目标节点与原节点距 离而变化 (xl,y1):表示节点n在FPGA中的坐标 (x2,y2):表示终点sink在FPGA中的坐标 wireType:表示可分割线的类型 clbSide:表示节点对CLB的相对位置 deltaX=x2一xl:表示终点与节点n的水平相对距离 deltaY=y2一yl:表示终点与节点n的垂直相对距离 IF(deltaX f-0&&deltaY==O){//更新水平方向上节点的基本费用 获得节点相对终点的相对位置及水平相对距离 bw[n]=nodeWeight[Node][OistanceFromCLB]//更新水平方向上节点的基 本费用 Cost(n)=bw[n]木P(n)木h(n) 第74页(共91页) 第5章FPGA布线研究与实现 } Else IF(deltaY!=0&&deltaX==0){//更新水平方向上节点的基本费用 Cost(n)=bw[n]木P(n)半h(n) ) Else IF(deltaX!=0&&deltaY!=O){//同时更新水平方向和垂直方法上 节点的基本费用 Cost(n)=bw[n]木P(n)拳h(n) } 5.3.5.2 提高长线的使用率 长线的使用率是指通道中使用的长线与通道中长线资源的比值,这里所说的 通道中使用的长线是指长线被利用到,其可以作为任意倍线来使用。如图5-18 所示假设通道中长线的布线资源为4,其中有一条长线作为2倍线使用,一条长 线作为2倍线使用,则长线的使用率为2/4,但是两条长线的有效使用效率则分 别为2/L,3/L。 ! I I ! ! I I I ) I I I ! I 图5—18长线使用率情况 下面为在保证长线有效使用效率的情况下,提高通道中长线的使用率的启发 式策略。 令bbCost:线网边界框半周长 L:长线的长度 El:改变长线基本费用的临界参数 IF(wireType==LONG){ B(10ng)=(bbCost>=Q术L宰2)?0.1:1.0 ) ELSE B(n)=1.0 第75页(共91页) 第5章FPGA布线研究弓实现 5.4本章小节 本章在介绍基本的搜索算法之后,介绍了将FPGA硬件结构转变为FPGA布线 程序可识别的布线资源图的方法,并将基本的搜索算法运用的FPGA布线资源图 上,实现FPGA的基于布通率的布线算法。在此基础上,借鉴了FPGA时序分析方 法,将时序分析作为布线算法的一子模块,实现基于时序的布线算法改进,同时 采用了第4章FPGA功耗模型,在布线算法实现中考虑了动态功耗的问题。最后 在提高可分割线有效利用率和提高长线利用率上对布线算法进行了改进。 第76页(共91页) 第6章实验结果 第6章实验结果 本文从第3章到第5章逐一介绍了FPGA的结构描述模型、FPGA功耗模型 和FPGA布线算法及其改进,本章将就FPGA功耗和基于功耗布线及其提高线 网利用方面进行测试,基于时序驱动的布线将是以后工作的重点,在此没有给出 实验的测试结果。同时需要指出的是布线算法的实现及测试只能说明算法流程的 正确性,对于下载到FPGA芯片上的电路逻辑功能及测试数据的正确性和准确性 还需要软硬件的协同测试。 6.1 FPGA功耗测试 实验中我们分布对学术界MCNC的常用20个最大测试电路进行了测试,前 端输入网表通过FlowMap、TVPack和VPR的Placement的修改版,FPGA结构 经过简化为一个CLB包含四个LUT和4个触发器,布线资源包括1倍线、2倍 线、6倍线和长线,其中功耗分析和基于功耗的FPGA布线中,我们假设原始输 入节点的静态几率和节点转换密度为O.5。 表6-1为在不固定芯片大小,而是根据电路测试电路的大小来确定芯片大小 的情况下,得到的最小FPGA阵列规模的条件下得到的电路的基本信息。 CirctlitName alu4 apex2 apex4 bigkey clma des diffeq dsip e11iptic exl010 exop frisc misex3 pdc s298 s38417 CrtiPath 7.97E-08 1.05E-07 1.12E-07 1.43E-07 7.58E-07 7.11E-08 5.93E一08 1.05E-07 1.49E-07 2.88E-07 6.82E—08 2.83B—07 8.27E一08 2.18E—07 1.44E-07 1.27E-07 Chip-Size 21 x 21 24 x 24 19 x 19 27 x 27 58 x 58 32 x 32 22 x 22 27 x 27 33 x 33 35 x 35 18 x 18 39 x 39 20 x 20 38 x 38 25 x 25 46 x 46 Inports 14 38 9 229 62 256 64 229 13l 10 8 20 14 16 4 29 0utPorts 8 3 19 197 82 245 39 197 114 10 63 116 14 40 6 106 CLBs 407 531 339 510 3340 554 473 405 1055 1222 301 1477 38l 1392 617 2039 第77页(共91页) Nets 1052 1519 978 1417 9422 1860 1407 1321 2701 3499 920 3617 1056 3719 1326 6354 第6章实验结果 S38584.1 seq spla tseng 9.64E一08 42 x 42 38 304 1.22E-07 23 x 23 41 35 I.59E-07 32 x 32 16 46 4.32E-08 19 x 19 52 122 表6-1测试电路基本属性 1731 488 995 353 4978 1371 2617 1010 表6-2、表6.3是表6.1情况下电路在基于布通率条件下和考虑节点转换率的 条件下进行的功耗分析,其中Rt-Pw列为电路的布线资源所消耗的功耗,CLB.Pw 为CLB内部消耗的共耗,CLK-Pw为时钟网络消耗的功耗,Total为总功耗,Rt.u【 为布线资源上的漏电功耗,CLB.U【为CLB内部的漏电功耗。需要说明的是,布 线资源我们考虑的是基本传输管和缓冲开关的,CLB内部暂时没有考虑XOR等 器件,仅考虑LUT、DFF、MUX等的漏电功耗计算,时钟网络是基于H树型的 时钟网络的,所有功耗单位为瓦(w)。 CircuitName alu4 apex2 apex4 bigkey clma des diffeq dsiP e11iptic exl010 exSp frise misex3 pdc s298 s38417 s38584.1 seq spla tseng Rt-Pw(w) 0.058827 0.063394 0.027945 0.034117 0.13324 0.104509 0.052833 0.0486755 0.0779102 0,0501905 0.0392695 0.0565128 0.0553793 0.0892219 0.0537445 0.201435 0.169219 0.0482314 0.0637772 0.0658974 CLB一~ CLK—PW Total一~ 0.0074281 0.0034 0.069656 0.0066495 0.00505 0.075092 0.0035749 0.00236 0.033882 0.0078702 0.0037 0.045689 0.0199006 0.00285 0.155989 0.0157041 0.01491 0.135121 0.0088206 0.00457 0.066222 0.0084301 0.00507 0.06218 0.0124748 0.00711 0.097495 0.0081039 0.00368 0.061974 0.0049401 0.00389 0.048101 0.0099025 0.00375 0.070167 0.0060261 0.00327 0.06468 0.0101321 0.00488 0.104235 0.0073386 0.00369 0.064773 0.0352231 0.0167 0.253363 0.0323349 0.0112 0.212753 0.0057859 0.00436 0,058375 0.0076911 0.00666 0.078125 0.0120149 0.00614 0.084051 表6-2FPGA功耗分析 Rt—Lk 0.001788 0.002331 0.001454 0.002263 0.01484l 0.002426 0.002067 0.001791 0.004601 0.005302 0.001308 0.006527 0.001662 0.006061 0.00273 0.008996 0.007671 0.002148 0.004364 0.001534 CLB—Lk 0.008337 0.013663 0.008367 0.007647 0.096574 0.014568 0.0087 19 0.010597 0.024187 0.030454 0.007925 0.037794 0.008946 0.049836 0.01314 0.041815 0.032388 0.012007 0.029912 0.006238 CircuitName alu4 apex2 apex4 bi gl【ey Rt一~(W) 0.0441419 0.0779469 0.0266848 0.0684581 cLB-~ 0.0058336 0,0077952 0.0034791 0.0126067 CU(一~ 0.0024 0.00649 0.00223 0.00683 Total—Pw 0.052377 0.092232 0.032394 0.087898 Rt-Lk 0.001788 0.002331 0.001454 0.002263 CLB—Lk 0.00849l 0.013289 0.008378 0.007981 第78页(共91页) 第6章实验结果 clnla des diffeq dsio e11iptie exl010 exbp frise Inisex3 pde s298 s38417 s38584.1 seq spla tseng 0.176066 0.0232189 0.00528 0.204562 0.014841 0,096721 O.10297 O.0152402 0.01437 0.132582 0.002426 0.Oi382 0.0595154 0.0t00956 0.00544 0.075055 0.002067 0.00885l 0.0571763 0.0089557 0.00548 0.071609 0.00179l 0.009999 0.0804798 0.0125221 0.00715 0.100155 0.004601 0.024326 0.0498888 0.0080857 0.00364 0.061612 0.005302 0.030076 0.0292504 0.0038945 0.00269 0.035834 0.001308 0.007693 0.0611442 0.0105603 0.00454 0.076241 0.006527 0.038287 0.0558547 0.0060879 0.00332 0.065266 O.001662 0.008719 0.0832371 0.0097857 0.00428 0.0973 0.00606l 0.048747 0.0442175 0.0063171 0.00283 0.053364 O.00273 O.Oi2919 0.149843 0.0278436 O.01195 0.189641 0.008996 0.041833 0.158219 0.0311064 0.01064 0.199966 0.007671 0.032611 0.0615827 0.006918 0.00581 0.07431l 0.002148 O.012106 0.0609036 0.0075042 0.00619 0.074595 0,004364 0,03015 0.0636"/87 0.Ol 13627 0.00575 0.080796 0.001534 0.006123 表6.3考虑节点线网转换率的布线及功耗分析 表岳4所示的结果与表6-1的区别在于FPGA芯片的通道宽度是固定的,表 6—5、表6-6分别为这种情况下的FPGA功耗分析和考虑节点转换率情况下的布 线及功耗分析。 CircuitName alu4 bigkey des diffeq dsip exSp lRisex3 s298 s38417 s38584.1 seq tseng apex2 aoex4 clma e11iptic exl010 frisc spla CrtiPath 5.60E—08 Chip 21^21 Width 40 Inports 14 2,80E一08 27 x 27 40 229 3.80E一08 32 X 32 40 4,68p08 22 x 22 40 1.83E-08 27 X 27 40 9.17E一08 18 x 18 40 256 64 229 8 6.65E一08 20 x 20 40 14 1,42E一07 25 x 25 40 4 1,02p07 46 x 46 40 29 9.74E一08 42 x 42 40 38 9.73E一08 23 x 23 40 41 4.36E一08 19 x 19 40 52 5,36E一08 24 x 24 60 38 3.94E一08 19 x 19 60 9 3.60E一07 58 x 58 60 62 7.94E-08 33 x 33 60 131 9.15E一08 35 x 35 60 10 1.10E一07 39 X 39 60 20 1.80E一07 32 x 32 60 16 表6.4固定通道情况下电路信息 OutPorts 8 197 245 39 197 63 14 6 106 304 35 122 3 19 82 114 10 116 46 CLBs 407 510 554 473 405 301 381 617 2039 1731 488 353 531 339 3340 1055 1222 1477 995 第79页(共9】页) 第6章实验结果 CircuitName alu4 bigkey des diffeq dsip exSp misex3 s298 s38417 s38584.1 seq tseng apex2 apex4 clfna elliotic exlOlO frisc spla Rt—Pw(w) CLB—Pw CLK—P霄Total—Pw Rt—Lk(2LB—Lk 0.084576 0.009714 0.004833 0.099123 0.001788 0,009406 0.18665 0.030913 0.018932 0.236496 0.002263 0.014482 0.193442 0.026969 0.027906 0.248318 0.002426 0.0191 0.060904 0.010604 0.005793 0.077302 0,002067 0.009963 0.25828 0.039776 0.029056 0.327113 0.001791 0.014485 0.030402 0.004072 0.002892 0.037366 0.001308 0.007701 0.067964 0.007026 0.004075 0.079064 0.001662 0.00922 0.05783 0.007406 0.003747 0.068983 0.00273 0.013617 0.244209 0.041607 0.020818 0.306634 0.008996 0.044186 0.169756 0.03209 0.011088 0.212933 0.007671 0.034724 0.058201 0.006642 0.005455 0.070298 0.002148 0.012123 0.067586 0.01 1926 0.006086 0.085599 0.001534 0.007363 0.125822 0.010512 0.009908 0.146242 0.002331 0.016439 0.071948 0.006754 0.006728 0.08543 0.001454 0.010664 0.191355 0.024201 0.005996 0.22155l 0.01484l 0.098509 0.137853 0.019199 0.013353 0.170406 0.004601 0.027104 0.113859 0.011516 0.011594 0.136968 0.005302 0.034235 0.103206 0.014872 0.009679 0.127758 0.006527 0.041958 0.060182 0.007382 0.005881 0.073445 0.004364 表6.5固定通道时的布线及功耗分析 0.031057 CircuitName llt—Pw(w) CLB一~(w) CLK-PW(w)Total—Pw(w) Ilt—Lk(w) CLB—Lk(w) aIu4 0.094602 0.010428 0.00528 0.11031 0.001788 0.00959 apex4 bigkey des 0.034586 0.232 13 O.22157 0.004189 0.038669 0.030664 0.003205 0.024059 0.03217 0.04198 0.294858 0.284404 0.001454 0.002263 0.002426 0.008446 0.014278 0.019242 diffeq dsip misex3 0.063591 0.174233 0.082321 0.010504 0.026815 0.008415 0.005724 0.01914 0.005188 0.079819 0.220188 0.095924 0.002067 0.001791 0.001662 0.009876 O.014873 0.009129 s298 0.084843 0.010031 0.005959 0.100834 0.00273 0.013497 s38417 0.223929 0.039231 0.019286 0.282446 0.008996 0.04465 s38584.1 0.230613 0.041615 0.015416 0.287644 0.00767l 0.035054 seq tseng apex2 clira 0.056395 0.067501 0.123075 0.181823 0.006473 0.005239 0.012培0.006235 0.010508 0.009903 0.023761 0.005673 0.068107 0.085916 0.143486 0.21 1257 0.002148 0.001534 0.002331 0.014841 0.012158 0.007392 0.016441 0.098728 e11iptie 0.161334 0.02 1365 0.015366 0.198065 0.004601 0.027809 exl010 0.122537 0.012067 0.012874 0.147478 0.005302 0.034176 frisc 0.102393 0.015398 0.010306 0.128097 0.00652"/ 0.041503 spla 0.061842 0.007447 0.006043 0.075332 0.004364 表6-6固定通道考虑线网转换率情况下布线及功耗分析 0.031335 第舳页(共9l页) 第6章实验结果 从表6.2与表6.3、表6-5与表6.6的比较中可以看出,有些电路的功耗确实 有所下降,而有些则反而提高了,这是由于在考虑功耗的布线算法时,由于节点 的选取优先考虑了节点的转换密度,而导致其他其他线网布线时需要经过更长的 轨迹而引起的,因此需要进一步改进。 6.2线网使用率测试 本小节就提高线网有效使用率和提高长线使用率方面进行了测试,表6.7、 表岳8所示为普通布线算法的线网使用率和线网有效利用率情况,表6.9、表6.10 所示为提高线网使用率和提高线网有效利用率情况。其中可分割线网包括单倍 线、两倍线、6倍线(可做单个1倍线和3倍线使用两种情况),表中Drt.utl表 示单倍线的使用率,Dbl.utl表示双倍线使用率、H1.utl表示可做为单倍线使用的 6倍线使用率、H2.utl为可做3倍线使用的6倍线使用率、Lg-utl表示长线的使 用率,Ef-Drt表示单倍线的有效使用率,Ef-Dbl表示双倍线有效使用率、El-H1 表示可做为单倍线使用的6倍线有效使用率、Ef-H2为可做3倍线使用的6倍线 使用率、Ef-Lg表示长线的使用率。 CktName alu4 apex2 apex4 bigkey clma des diffeq dsip e11iptie exl010 exSp frisc misex3 pdc s298 s38417 s38584.1 seq spla tseng Drt——utl 2.3934 2.7637 2.5877 0.1596 2.6507 0.2184 2.7075 0.1756 1.2423 3.1576 2.5282 2.4512 2.1743 2.5732 1.9271 3.1152 1.3411 2.4854 2.606 0.7922 Dbl——utl 3.8691 4.3717 4.03 0.2222 4.0583 0.2579 3.8815 0.2305 1.7003 5.058 4.2643 3.6131 4.0716 4.2178 3.4603 3.9337 1.5648 4.0899 3.9026 1.2365 Hl-utl H2-utl 1.67 6.2872 1,696 7.4675 1.7581 7.2917 0.1437 0.8242 2.1226 9.7564 0.1231 0.5274 1.0334 4.4395 0.1623 0.6519 0.8497 4.2579 2.1035 9.6478 1.5245 7.2049 1.6463 7.6923 1.5129 6.527 2.5329 11.759 1.4421 5.4167 1.1277 5.1343 0.5628 2.7565 1.8056 7.829 2.1289吼5462 0.3515 1.3749 Lg-utl 0 0 0 1.79 6.81 9.99 0 1.79 0 0 0 0 0 0 0 0 1.1l 0 0 0 第81页(共91页) 第6帝实验结果 表6.7普通布线线网使用率情况 Cktt,lame Ef—Drt Ef—Dbl Ef-Hl Ef—H2 Ef—Lg alu4 apex2 apex4 bigkey 100 75.374 100 76.098 100 75.146 100 74.551 66.708 65.835 65.282 75.81 65.407 liaR 65.613 nan 65.008 nan 76.278 3.24 elma 100 74.291 71.805 69.528 4.74 des diffeq dsip elliptie exlOlO ex5p frise 100 70.383 100 73.855 100 71.356 100 75.212 100 75.1 100 74.682 100 74.546 79.158 62.8 81.967 69.379 6"1.539 66.014 68.474 75.004 2.8 62.399 nail 77.024 2,34 68.328 nan 65.663 64.144 nan nail 68.158 ilan misex3 100 75.381 66.393 65.221 ilan pde s298 100 76.332 100 75.306 71.45 70.655 69.982 65.976 nan nan s38417 100 71.209 68.533 67.667 nan s38584.1 100 72.233 71.154 67.804 3.33 seq spla tseng 100 100 100 75.827 75.735 73.343 66.397 70,274 61.917 66.208 68.132 63.091 flaiR nail nan 表6.8普通布线线网有效利用率情况 CktName alu4 apex2 apex4 bigkey clma des diffeq dsip e11iptic exl010 exbp frisc misex3 pdc s298 s38417 s38584.1 Drt—titl 2.98446 Dbl-utl 1.89319 ltl-utl 0.669643 f12-utl 4.2328 Long—utl 94.0972 4.26107 3.19987 1.11979 5.66406 98.75 3.91686 2.64894 0.904977 5.72681 96.6912 0.279042 0.137692 0.122725 0.81085 3.56801 4.46014 2.71294 1.52027 8.45277 99.6622 0.383746 0.172254 0.07749 O.51454 15.6672 4.72884 2.33962 0.648975 3.10433 44.8413 0.342899 0.128712 0.101439 0.632583 5.47174 2.06413 1.31144 0.668203 3.79608 15.0058 5.30599 3.69389 1.5563 7.71949 97.0982 4.09071 2.88086 0,971137 4.97504 94.5312 4.07379’ 2.39292 1.09994 6.28824 91.9143 3.44329 2.58763 0.892857 4.38575 96.5278 4.47979 3.13895 1.73921 10.8181 85.026 2.42839 1.68945 0.592448 3.25195 94.6875 5.278 2.2627 2.1247 1.01383 0.690091 0.392236 3.77591 2.12869 53.2328 25.4484 第82页(共91页) seq spla tseng 笙!!兰望竺墨 4.17398 2.86915 1.18787 5.71272 4.30507 2.88462 1.47327 8.17854 1.55157 0.928759 0.253132 1.07809 表6-9提高线网利用率情况 98.6842 91.4773 0 CktNarne alu4 apex2 Ef—I)rt El-I)bl 100 92.1397 100 91.7599 Ef—H1 73.1481 73.4012 Ef—{{2 67,9688 67.5958 Ef-Long 46.7053 25.4945 apex4 100 93.6833 71.875 68.7106 31.6467 bigkey 100 92.9952 81.9783 76.9757 3.13199 circa lOO 93.1132 76,908 72.4045 20.8885 des diffeq 100 89.8281 100 91.6961 81.3694 69.7452 79.0168 67.6653 3.1566 28.3186 dsip elliptic exl010 100 100 100 87.0801 92.0937 92.6983 85,082 74.9282 73.0578 77.401 70.8818 69.1232 3.42815 23.6468 22.8927 exap 100 93.9736 68.9944 66.9211 29.9242 frisc 100 93.0365 75.9934 70.1564 19.7337 misex3 100 94,3291 70.1389 68.3003 33.5046 ode s298 s38417 s38584.1 100 100 100 100 93.4568 90.6551 93.417 94.2806 79.0107 75.8242 71.2934 73.1932 71.228 69.7531 71.154 72.7724 i9.4268 44.1625 22.9542 15.2509 seo 100 92.7389 75.6923 69.3218 29.6 spla 100 92.7715 76.9468 70.5671 21.5958 tseng 100 90.8824 69.7842 68.8908 nan 表6.10 提高布线线网有效利用率情况 从表6-7与表6-9、表6-8与表6.10的比较中可以看出,考虑线网使用率的 改进算法有利于提高长线的使用率,并有利于提高可分割线网的有效使用率。 6.3本章小节 本章给出了FPGA的功耗分析测试结果,基于功耗的布线算法测试结果和提 高线网利用率的布线算法测试结果。结果显示,在功耗方面,布线算法还有待于 进一步考虑,而在提高利用率方面,实验结果表明,算法能够极大的提高线网的 有效使用率。 第83页(共91页) 第7章总结和展埋 第7章总结和展望 7.1工作总结 本论文作者的主要工作是在FPGA软件系统中负责布线模块算法的开发与设 计,本论文所作的研究工作主要包括:提出一种基于Tile的FPGA结构描述方法, 对FPGA功耗模型和时序模型和FPGA命线算法进行了研究及实现。 本文研究及工作内容主要包括如下几个方面: 1)在FPGA结构描述方面,作者在分析现代商用FPGA层次化结构及学术上对 FPGA描述方法的基础上,提出~种基于Tile的FPGA结构描述。在基于Tne的FPGA 结构描述中,根掘硬件结构层次化和FPGA稚线资源层次化的结构,由底层基本逻 辑单元LUT、DFF、XOR及其他单元构成S1ice层,再由S1ice层构建CLB层,同时在 布线资源结构上,分成逻辑块输入选择矩阵IMUX、逻辑块输出选择矩阵OMUX和线 网切换矩阵GRM,由此构成基本rile。由于摹本Tile的重复性,所以采用该方法 可以简化FPGA结构的描述,同时由于该方法是以硬件结构为根据,为以后的FPGA 软硬件的同步升级提供了简单而灵活的接口,该方法在原型系统中测试证明是可 行且正确的。 2)在FPGA功耗模型方面,作者研究了ASIC中关于电路功耗计算的基本方 法和概念,并将其应用到FPGA功耗分析中。在功耗模型中的采用了混合的功耗 模型,包括动态功耗模型和静念功耗模型。动念功耗的计算采用基于节点状态转 换率的开关级动态功耗计算和逻辑块宏模型,静态功耗则采用基于公式计算的晶 体管漏电功耗模型和逻辑块基于仿真的LUT/MUX表达式计算模型。这些功耗模 型将运用到我们后面的功耗计算和基于功耗驱动的布线算法中。 3)在FPGA布线算法研究和实现方面,作者在介绍基本的搜索算法之后,介 绍了将FPGA硬件结构转变为FPGA布线程序可识别的布线资源图的方法,并将基本 的搜索算法运用的FPGA布线资源图上,实现FPGA的基于布通率的布线算法。在此 基础上,借鉴了FPGA时序分析方法,将时序分析作为布线算法的一子模块,实现 基于时序的布线算法改进,同时采用了第4章FPGA功耗模型,在布线算法实现中 考虑了动态功耗的问题。最后在提高可分割线有效利用率和提高长线利用率上对 布线算法进行了改进。 第84页(共91页) 第7章总结和展望 7.2工作展望 FPGA布线始终是FPGA软件系统中最重要、最关键的模块之一,不仅需要对 FPGA硬件结构要求很深的了解,同时要求对搜索算法有一定的研究,因此FPGA 布线一直是学术界和工业界研究的课题之一。 随着工艺晶体管尺寸的不断下降,在实现FPGA/ff线的同时需要考虑的问题也 越来越多。从功耗方面来看,如何降低功耗,包括动态功耗和静态功耗,本文提 出的基于节点转换率降低动态功耗的方法还需要进一步研究,另一方面,功耗很 大程度上是和FPGA的结构相关系的,因此如何提出一种低功耗的FPGA结构、在此 结构上实现FPGA布线算法,也是研究的方向。和工艺相关的另外一个不可回避的 问题是FPGA的时序问题,用户设计的电路频率越来越高,要求布线算法不能只是 简单的考虑布通,同时还需要考虑线网之间信号的串扰问题。 从FPGA布线算法上来看,至今为止我们都是采用基本的线网搜索算法,其核 心还是宽度优先搜索算法,随着FPGA阵列规模的不断扩大,布线算法需要考虑实 现过程中的速度问题,如何加快粕线算法或采用其他算法使用到FPGA布线中也是 研究的~个方向。 第85页(共91页) 参考文献 参考文献 [1] Xilinx co。Virtex-ll ProTM X Platform FI'GAs:Complete Data Sheet.Mar.2004. [2] Altera Co..Stratix II Device Handbook.Volume 1.Feb.2004. [3] John Daane.决策入观点_6变革市场创造新的挑战与机遇【J】.屯子工程专 辑,2004-01. [4] 冯远辉.FPGA的现状及展望[EB/OL】.电子设计应用. http://www.99eda.com/show.aspx?id--507&cid=29,2006-03. [5] 陆楠.Altera:FI'GA正进一步蚕食ASIC和ASSP的应用市场[EB/OL].电子经理 世界.www.chinsecuet.com/zf/zf0511—1.asp,2006-04. [6] Mike Hutton,Altera,"Architecture and CAD for FPGAs”,【c】.SBCCI’04,Sep.7—11, 20()4 [7] J.Rose,A S.Vincentelli,“Architecture of Field-Programmable Gate Arrays”,【J】. [8] Proceedings of the IEEE,v01.81,No.7,July 1993, Xilinx Corporation,"XC4000E Field Programmable Gate Array Family”,Data Book, Sep.1995 [9] S.Brown,R.Francis,J.Rose and Z.Vranesic.Filed—Programmable Gate Arrays fMl. [10] [1l】 Kluwer Academic Publishers,1992. A.Aggarwal and D.Lewis,Routing Architectures for Hierarchical Field Programmable Gate Arrays[J].Proc.IEEE Custom Integrated Circuits Conference,1994. CAD v.Betz,Architectures and for Speed and Area Optimization of FeGArID],Ph.D. [123 Thesis,University ofToronto,1998. V.Betz,J.Rose,Circuit Design,Transistor Sizing and Wire Layout of FPGA Interconnect[J],Custom Integrated Circuits,1999.Proceedings of the 1EEE 1999 16-19 May 1999,ppl71—174. [13] [14] 丸九Aggarwal,Routing Architectures for Hierarchical FPGAs[D】'MA.Sc.Thesis, Department ofElectrical and Computer Engineering,University ofToronto,1994. K Chang.S.Singh,J.Rose and E Chow,"Using Hierarchical Logic Blocks to Improve the Speed of Field-Programmable Gate Arrays,’,【MI.Proceedings of the First Intemational Workshop on Field Programmable Logic and Applications,Oxford,Se:pt. [15] [16] 1991,PP.103-113. Actel Corporation,Introduction to Actel FPGAArchitecture,【M】.Sep.1997. S.Brown and J.Rose,“FPGA and CPLD Architecture-tures:A Tutorial”,【M】.IEEE 第86页(共91页) 参考文献 [17] [18] Design&Test of Computers,Jul.1996:pp42-57 V lktz,J.Rose,and A Morquardt,Architecure and CAD for Deep-Submicron FPGAs. 【M】.Boston"KluwerAcademic,1999. YW:Chang.D.E Wong,and C.K.Wong,“Universal Switch Modules for FPGA Design,"【q ACM Trans.Design Automation of Electronic Systems,v01.1,no.1,pp. [19] [20] [21] 86-101,fan.1996. V Betz and J.Rose."Automatic Generation of FPGA Routing Architectures from High-Level Descriptions,”【c】.ACM/SIGDA Int.Syrup.on FPGAs,2000,PP.175- 184. Y:W:Chang,D.E Wong,and C.K Wong,“Universal Switch Modules for FPGA Design,”【C1.ACM Trans.Design Automation of Electronic Systems,v01.1,no.I,PP. 80-101,Jan.1996. V Betz and J.Rose,‘'VPR-A New Pacbn&Placement and Routing Tool for FPGA Research,"【c1.Proc.7th Infl.Workshop on Field—Programmable Logic and [22] Applications,1997. Q Q Lomieux and S.D.Brown,“A detailed router for allocating wire segments in field-programmable gate arrays,”【c】Proceedings of the ACM Physical Design [23] Workshop,April 1993. S.J.E.Wilton,Architectures and Algorithms for Field·Programmable Gate Arrays with [24] [253 [26] Embedded Memory.[D].PhD thesis,University ofToronto,1997. Synopsys Coq】oratiou.Powermill Data Sheet 1999 Mentor Graphics Corporation,1999 EN.Najm,“A Survey of Power Estimation Techniques in VLSI Circuits,”【c1. Proceeding of IEEE Transactions oil VLSI Systems,December,1994,v01.2,no.4, [27] [28] [29] [30] 446-455. G Ycap,Practical Low Power Digital纥田Des喀n,【M】.Kinwer Academic Publishers. 1998 S.Vmdlmla and H Xie.‘‘A Fast and Accurate Technique for Estimating Signal Activity in CMOS Logic Circuits”,Tcchmcal Report,CENG-95—109,University of Arizona,Jan. 1995. A.Shen,A Ghosh,S.Devadas and K Keutzer,“On Average Power Dissipation and Random Pattern Testability of CMOS Combinational Logic Networeks”,【C】. Proceedings ofInternational o)nference ofComputer-Aided Design,pp.402—407,1992 R.Marculescu,D.Marculeseu and M.Pcdram,“Logic Level Power Estimation 第87页(共91页) 参考文献 Considering Spatiotemporal Correlations”,【c】.Proceedings of International Conference [31] [322 of Computer-Aided Design,PP.294-299,1994 M.Cirit,“Estimating Dynamic Power Consumption of CMOS Circuits",【c】. Proceedings of International Conference of Computer-Aided Design,PP.534-537,1987 ENajm,"TransitionDensity:ANewMeasureofActivityinDi垂talCircuits'’,【J】.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,v01.12, [33] no.2,pp.310·323,Feb.1993 E Najm,“Low·pass Filter for Computing the Transition Density in Digital Circuits'’, IJ】.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, [343 [353 voL 13,no.9,PP-1123—1131,Sep.1994 R.Marculescu,D.Marculescu and M.Pedram,“Logic Level Powet Estimation Considering Spatiotemporal Correlations”,【C1.Proceeding of International Conference of ComputerAided Design,1994 E Najm,“Improved Estimation of the Switching Activity for Reliability Prediction in VLSI Circuits'’,【J】.1EEE Transactions on Computer Aided Design of Integrated [363 [37] [38] Circuits and Systems,1994 D.Eekerbert.,P.L Eefors,“Interconnect—Driven Shofl·Circuit Power Modeling'’,【C】. Proceedings of Euromicro Symposium ou Digital Systems Design,pp412-421.2001 O.Wang,k Vrudhulas,“A New Shoo Circuit Power Model for Complex CMOS Gates,”【C1.Proceedings of IEEE Alessandro Volta Memorial Workshop on Low Power Design(Volta99),pp98·106.1999 ICPoon,A.Yah,SJ.E.Wilton,“A Flexible Power Model for FPGAs”,【M】. International Workshop on Field-Programmable Logic and Applications,September 2毗 [39] F.Lj,D.Chen,LHe,and J.Cong,“Architecture Evaluation for Power Efficient FPGAs”,【c】.Proc.ACM Intl.Symp.Field Programmable Gate Array,Feb 2003. [40] F Li and L He,“Power Modeling and Characteristics of Field Programmable Gate Arrays'’,【J】.IEEE Transactions on ComputerAided Design ofIntegrated Circuits,2005 [41] T.Tuan and B.Lai,“Leakage power analysis of a 90 mn FPGA,”【c】.Proc.IEEE [42] Custom Integrated Circuits Con£,San Jose,CA,2003,PP.57--60. A Lcshavarzi.k Roy,S.Hawkinc.“Intrinsic Leakage in Low Power Deep Submicron CMOS ICs”,【C】.Proceedings of the IEEE International Test Conference,1997, [43] 146.155. S.M.Kang,Y.Leblebici.CMOS Digiml Integrated Circuits:Analysis and Design,【M】. 第88页(共91页) 参考文献 McGraw-Hill.1999 [441 kY.Toh,EK.Ko,R.G Meyer,"An Engineering Model for Short-Channel MOS [45] Devices'’,[J1.IEEE Journal of Solid-State Circuits,V01.23,No.4,August 1988. E.Moore,The shortest path through a maze,International Symposium on the Theop/of [46] Switching(1959),【M】.Harvard University Prc% l乙E"rarjan,Depth tint search and linear graph algorithms.SIAM lout'aM oil Computing,Pi.ppl46-160,1972 [47] E.Dijkstra.‘‘A note on two problems in connexion with graphs",[MI.Numerische [48] Mathematik,pp269—271,1959. E Rubin,‘'The Lee Path Connection Algorithm",p1.IEEE Trans.Computers,Sep. [49] [503 1974,PP.90%914 J.Swartz,V.Betz,and J.Rose,“A Fast Routabllit)’-Driven Router for FPGAs”,【q. ACM Symp.On FPGAs,1998,PP.140-149. c.Y Lee,‘'An Algorithm for Path Connections and its Applications”,闭.IRE Trails. 1-51] Electron.Compute,v01.10,1961,pp.346 365. L E.McMurchie and C.Ebeling,“PathFinder:A Negotiation-Basod Path Driven [52] Router for FPGAs”,【c】.Proc.ACM/IEEE Intl.Symp.On FPGAs,1995. C.Ebeling,L McMurchie,S.A.Hauck and S.Bums,“Placement and Routing Tools [53] for the Triptych FPGA,”【J】.IEEE Trans.Oll VLSI,Dec.1995,即.473—482. M.J.Alexander,G Robins,“New Performance—Ddven FPGA Routing Algorithms”, [54] 【C1.DAC,1995,IV562·-567 w.Elmore.UThe Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers”,[J].Journal ofApplied Physics,Jan.1948,PP.55—63 第89页(共91页) 攻读学位期问的科研成果 攻读学位期间的科研成果 【1】胡欣,来金梅,陈苑锋,王波,蕈家榕。适用于数据通路的可编程逻辑器件 FDPIOOK软件系统【J】。电子学报,已录用。 第90页(共91页) 致谢 致谢 在论文完成之际,我要深深感谢我的导师来会梅副教授、童家榕教授。在我 进入ICCAD研究室攻读硕士学位的三年期间,来老师给我确定了正确的研究方 向,在学术和课题的难点上与我进行了多次深入的讨论,对我有很大启发。在我 参加FPGA评估项目组和FPGA硬件辅助设计系统期间,来老师在项目和学术上给 了我精心的指导和诚挚的鼓励。我要感谢耄家榕教授,他为人师表,虽然工作繁 忙,但仍非常关心学生的成长。他们在项目和学术上都给了我精心的指导和诚挚 的鼓励,我的点滴进步,无不凝聚着他们的心血。他们严谨的治学风范、真诚热 情的待人接物、对待工作的热情和孜孜以求的态度给我树立了很好的榜样。 非常感谢王伶俐副教授、黄均鼐教授对我学业方面的帮助,两位老师认真负 责的工作态度及丰富的知识给了我很大的影响。感谢唐璞山教授以及曾璇教授, 正是他们生动的课程为我打下了坚实的ICCAD理论基础,而他们渊博的学识,诲 人不倦的精神和平易近人的作风也将使我终身受益。感谢谭道珍老师对我生活方 面的关怀。 感谢FPGA课题组的同窗杨铭、王健、陈利光、屠睿、胡云、王恰、张军营、 于薇在求学道路上给我的帮助、鼓励和启发。感谢曾经帮助过我的师兄师姐们和 师弟师妹们,包括陈苑锋、倪刚、侯慧、王元、蔡月、谈瑗、谢丁、徐嘉伟等等, 本文完成的工作中同样凝聚着你们智慧的结晶。感谢FPGA课题组其他所有成员 及与我一起求学的其他同窗好友给我的帮助。 最后,还要感谢ICCAD实验室所有研究生以及已经毕业的师兄师姐们给我的 关心、帮助和支持,感谢大家共同创造了和谐、开放的工作环境。感谢所有帮助 过的人们! 最后,我要把这篇论文献给我的父母,感谢他们二十多年来对我的精心培育。 第91页(共91页) FPGA布线研究与实现 作者: 学位授予单位: 胡欣 复旦大学 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1169617.aspx 授权使用:北京理工大学(北京理工大学),授权号:597f189d-6c57-42fd-aeb9-9e2e000bab4a 下载时间:2010年11月14日
更多简介内容

评论

下载专区


TI最新应用解决方案

工业电子 汽车电子 个人电子
$(function(){ var appid = $(".select li a").data("channel"); $(".select li a").click(function(){ var appid = $(this).data("channel"); $('.select dt').html($(this).html()); $('#channel').val(appid); }) })