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

几种用于FPGA的新型有效混合布线算法

  • 1星
  • 日期: 2014-03-05
  • 大小: 3.33MB
  • 所需积分:1分
  • 下载次数:0
  • favicon收藏
  • rep举报
  • 分享
  • free评论
标签: 几种用于FPGA的新型有效混合布线算法

采用现场可编程门阵列(FPGA)可以快速实现数字电路,但是用于生成FPGA编程的比特流文件的CAD工具在编制大规模电路时常常需要数小时的时间,以至于许多设计者甚至通过在给定FPGA上采用更多的资源,或者以牺牲电路速度为代价来提高编制速度。电路编制过程中大部分时间花费在布线阶段,因此有效的布线算法能极大地减少布线时间。 许多布线算法已经被开发并获得应用,其中布尔可满足性(SAT)布线算法及几何查找布线算法是当前最为流行的两种。然而它们各有缺点:基于SAT的布线算法在可扩展性上有很大缺陷;几何查找布线算法虽然具有广泛的拆线重布线能力,但当实际问题具有严格的布线约束条件时,它在布线方案的收敛方面存在很大困难。基于此,本文致力于探索一种能有效解决以上问题的新型算法,具体研究工作和结果可归纳如下。 1、在全面调查FPGA结构的最新研究动态的基础上,确定了一种FPGA布线结构模型,即一个基于SRAM的对称阵列(岛状)FPGA结构作为研究对象,该模型仅需3个适合的参数即能表示布线结构。为使所有布线算法可在相同平台上运行,选择了美国北卡罗来纳州微电子中心的20个大规模电路作为基准,并在布线前采用VPR399对每个电路都生成30个布局,从而使所有的布线算法都能够直接在这些预制电路上运行。 2、详细研究了四种几何查找布线算法,即一种基本迷宫布线算法Lee,一种基于协商的性能驱动的布线算法PathFinder,一种快速的时延驱动的布线算法VPR430和一种协商A

江南大学 博士学位论文 几种用于FPGA的新型有效混合布线算法 姓名:刘战 申请学位级别:博士 专业:轻工信息技术与工程 指导教师:于宗光 20070601 摘要 摘要 采用现场可编程门阵列(FPGA)可以快速实现数字电路,但是用于生成FPGA编 程的比特流文件的CAD工具在编制大规模电路时常常需要数小时的时间,以至于许多 设计者甚至通过在给定FPGA上采用更多的资源,或者以牺牲电路速度为代价来提高编 制速度。电路编制过程中大部分时问花费在布线阶段.因此有效的布线算法能极大地减 少布线时间。 许多布线算法已经被开发并获得应用,其中布尔可满足性(sAT)布线算法及几何 查找布线算法是当|j{『最为流行的两种。然而它们各有缺点:基于SAT的布线算法在可扩 展性上有很大缺陷;几何查找布线算法虽然具有广泛的拆线重布线能力,但当实际问题 具有严格的布线约束条件时,它在布线方案的收敛方面存在很大困难。基于此,本文致 力于探索一种能有效解决以上问题的新型算法,具体研究工作和结果可归纳如下。 1、在全面调查FPGA结构的最新研究动态的基础上,确定了一种FPGA布线结构 模型,即一个基于SRAM的对称阵列(岛状)FPGA结构作为研究对象,该模型仅需3 个适合的参数即能表示布线结构。为使所有布线算法可在相同平台上运行,选择了美国 北卡罗来纳州微电子中心的20个大规模电路作为基准,并在布线前采用VPR399对每 个电路都生成30个布局,从而使所有的布线算法都能够直接在这些预制电路上运行。 2、详细研究了四种几何查找布线算法,即一种基本迷宫布线算法Lee,一种基于协 商的性能驱动的布线算法PathFinder,一种快速的时延驱动的布线算法VPR430和一种 协商A’布线算法Frontier,并且在相同的大规模基准电路上对这四种算法进行评估。对 比实验表明:一方面,相比Lee,PathFinder的布线时间要少得多,且大大减少了布线 时间的标准误差;另一方面,相比PathFinder,VPR430及Frontier可分别减少59.7%及 86.9%的布线时间,且在稳定性上分别提高了41.0%及81.3%。从布线速度及稳定性上看, 四种算法的优劣顺序是:Frontier、VPR430、PathFinder、Lee。 3、研究了一种通用的基于布尔的布线概念及把它用于FPGA详细布线的方法。对 两种典型的基于SAT的详细布线公式,即基于轨线公式(ToSDR)和基于路线公式 (R-SDR)进行了分析对比。T-SDR具有同步嵌入网线、可布线性判定(或评估)及灵 活的公式化能力的优点:但是,对于一些大规模基准电路,因为在布线方案空间的可选 择性过大往往会造成布线时间过长。与T-SDR相比,R.SDR能够有效地将排他性布线 约束条件仅仅通过2-文字的CNF子句表示,产生更加紧致的SAT实例,因而显得更加 有效。对比实验的结果表明T-SDR的布线时间及布线时间标准误差分别为R.SDR的31.4 倍及36.8倍,因此R—SDR比T-SDR更加稳定而有效。 4、将R.SDR与传统几何查找布线算法PathFinder、VPR430、Frontier进行了比较 研究。实验结果表明:R.SDR的布线时问及布线时|’日J标准误差分别为PathFinder的1.2 倍及1.1倍。从布线速度及稳定性上看,R.SDR次于几何查找布线算法。这一现象的主 要原因是R—SDR是一种详细布线算法,受由不考虑其特性的全局布线法提供的单一全 局布线配置所约束。 5、提出了将基于布尔函数的布线法R—SDR与目前最高水平的常规FPGA布线算法 PathFinder、VPR430及Frontier相结合的三种混合算法,即P—R.SDR、V-R.SDR和 F.R.SDR。混合算法不仅克服了基于布尔函数的FPGA布线算法的主要缺点,即可扩展 性问题,而且补偿了传统布线法的典型缺陷,即布线顺序依赖性及不能证明不可布线性。 实验结果表明,与单纯的几何查找布线法PathFinder、vPIⅥ30、Frontier相比,P.R.SDR、 V-R.SDR、F—R-SDR分别节省了CPU时间32.O%、28.9%、25.O%,并在稳定性上分别 提高了24.1%、25.O%、29.1%。另外,还对P.R-SDR,V-R.SDR,F.R.SDR进行了相互 江南大学博±:学位论文 比较,发现F.R.SDR、V-R-SDR、P.R.SDR的优劣顺序与Frontier、VPR430、PathFinder 相似。 6、针对SAT方法不支持局部方案的缺陷,给出了一种用于“子集可满足性”的布 尔SAT公式(sub-SAT),即将一个具有N个变量的“严格”的SAT问题变换成一个新 的“松弛”的SAT问题,仅当在原始问题中的变量有不超过k(k<心J)个不可满足时, 这一问题是可满足的。将sub.SAT用于R.SDR并与PathFinder、VPR430、Frontier相结 合可生成三种新型混合算法,即P—sub.R—SDR、V-sub-R.SDR和F—sub-R-SDR。实验表 明,虽然P.sub.R-SDR、V-sub.R.SDR、F.sub-R-SDR的布线时间分别为P-R-SDR、 V-R.SDR、F.R-SDR的1.74倍、1.79倍及1.76倍,但前者可以有效解决“不存在部分 方案”的问题,因而是可用于FPGA布线的十分有效的新算法。 关键词:可编程逻辑门阵列;几何查找布线算法;布尔可满足性;子集可满足性 H Abstraet Abstract Digital eircuits can be realized almost instantly using Field.Programmable Gate Arrays (FPGAs).HoweveL it usually takes a couple of hours for CAD tools to generate FPGA programming bit-streams during compiling the large—scale circuits.Some designers even have to use more resources on a given FPGA or sacrifice the circuit speed in order to increase the compilation speed.Since a significant portion of the compilation time is spent on the routing stage.an e币eient routing algorithm may reduce the roming time remarkably. A variety of routing algorithms have been developed and applied.among them the Boolean Satisfiability(SAT)一based routing algorithm and the geometric search routing algorithm are two most popular methods.However,they have different disadvantages.The SAr.based routing algorithm has problems in scalability,while the geometric search routing algorithm,though having the extensive rip-up-rerouting capability,has difficulty in achieving convergent routing solutions when the practical problem possesses tight routing constraints. Thus。in this thesis。we make efforts to explore a new and e伍cient algorithm to solve the above.stated problems.Detailed research work and results are listed below. Firstly,progress on the FPGA architectures is thoroughly reviewed.An FPGA routing architectural model.which is a symmetrical array(island.style)FPGA architeeture based on SRAM.is determined to be the investigating object.111e model needs only three appropriate parameters to represent the target routing architeeture.The benchmarks from twenty large—scale circuits of Microelectronics Center of North Caroiina(MCNC)are selected so that all the routing algorithms can work on the same platform.TIlirty placements for each cireuit are generated using VPR399 before running any routing algorithms.Thus all the routing algorithms can be run directly on these pre.placed circuits. algorithms Seeondly’four geometric search routing arc studied in detail,including a basic maze·running routing algorithm(Lee),a negotiation—based performance-driven routing algorithm(PathFinder),a fast timing-driven routing algorithm(VPIH30)and a negotiated A’ routing algorithm for FPGAs(Frontier).n忙four routing algorithms are evaluated based on tlleir performance onⅡle same large benchmark circuits.Compadson results suggest that PathFinder spends much les¥CPU time and has a significant reduction in the standard deviation ofthe CPU time than Lee.On the other hand,comparing to Pathfinder,VPR430 and Frontier can save CPU time bv 59.7%and 86.9%.and improve the stability by 41.0%and 81.3%.respectively.So.from the viewpoint of routing speed and stability,the ordel'of algorithms excellence of the fou.r can be ranked in the following sequence,Frontier,VPR430, PathFinder,Lee. Thirdly,we investigate a general SAT-based routing concept and introduce this concept into the detailed routing method for FPGA.Two typical SAr-based detailed routing formulas. the track—based formula(T-SDR)and the route.based fornlula fR—SDRl were analyzed and compared.The distinguishable advantages of■SDR arc:1)simultaneous net embedding,21 routability decision(or estimatiom and 3)flexible formulation ability.However’the running benchmark time for some large circuits is often too long due to the enormous flexibility captured in the routing solution space.In contrast to T-SD&R.SDR is able to represent ”exclusivity”routing constraints in e币cient expressions requiting onlY 2-literal CNF clauses. so yields more compact SAT inst.aIlces,and is.thus.more efficient.Experiment results show 江南大学博士学位论文 that the CPU time spent by T=SDR and the corresponding standard deviation are 3 1.4 and 36.8 times of tho辩by R—SDR respeelively,indicating that R-SDR is more stable and e茄cient than T-SDR. We also performed experiment comparisons between R-SDR and tIle conventional geometric routing algorithms.PathFindex,VPR430 and Frontier.Results show that the CPU time and its standard deviation bv R.SDR is 1.2 and 1.1 times of those by PatIlFind瓯 respectively.So.from the viewpoint of routing speed and stability,R.SDR is inferior to the algorithm.The geometric search routing primary reason is that R-SDR is a detailed routing algorithm,which is usually constrained more by the single global routing configuration provided by the global router regardless ofquality. Then,we proposed three hybrid approaches that integrated Boolean.based FPGA routing fR—SDR)with the state-of-the-arc routine FPGA routing algorithms(PathFinder,VPR430 and Frontier),abbreviated as P-R-SD&V.R—SDR and F—R-SD艮respectively.By doing this.we are not only able to overcome the major shortcoming of the Boolean.baste FPGA routing algorithm(f.巴,the sealability problem),but also able to compensate the typical defeels of conventional routing algorithms,te.,the net-ordering dependence and the disability of proving urtroutability.Experiment results show that,comparing to those pure geometric routing algorithms(PathFinder,VPR430 and Frontier),the new hy晰d algorithms。P.R-SD& 、,-R—SDR and F-R—SDR can reduce CPU time by 32.O%,28.9%,25.O%,and increase the stability by 24.1%,25.0%,29.1%,respectively.Further comparisons among the hybrid methods suggest that the order ofexcellence ofF.R—SD&V.R.SDR and P.R.SDR is similar to that of Frontier,VPR430 and PathFinder. Finally,we presented a formula suitable for subset.satisfiable Boolean SAr fsub.SAT)to solve the problem that SAr.based approaches cannot supPOrt partial solutions.By doing this. a“strict”SAT problem witll N constraints can be transformed into a new“relaxed”one which is satisfiable only when no more than k variables化<<N)cannot be satisfied in the original problem.Moreover,sub.SAT was used in R—SD&and three new hybrid methods were generated by combining it with PathFinder.VPR430 and Frontier,namely,P.sub.R.SDI乙 V-sub.R.SDR and F.sub—R.SDR.Experiment results show that although the CPU time spent by P-sub—R·SD&V-sub—R—SDR and F—sub.R-SDR is 1.74.1.79 and 1.76 times of that by P—R-SDlL V-R.SDR and F—R,SD&respectively,the new hybrid methods can effeelively solve the“no partial solutions”problem,mming to be very useful for FPGA routing. Key words:Field Programmable Gate Array;Geometric Search Routing Algorithm;Boolean Satisfiability;sub·SAT iv 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地 方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名: 型越。 日期:2。。7年g,9/占日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定:江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘,允许论文被查阅和借阅,可以将学位论文的全部或部分内容编 入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文,并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名:』过址 导师签名:≤}窨0芝L 日期:20。7r年<月/占日 第一章绪论 第一章绪论 1.1前言 FPGA[I-31是Field Programmable Gate Array的简称,即指现场可编程门阵列,是可以 实现不同的电路功能的可编程逻辑器件。一个FPGA由一系列由用户任意配置的预制逻 辑块及布线资源构成。目前越来越多的研发人员将FPGA视为一大利器,因为它能解 决许多系统设计人员的问题,可以将庞大且复杂的逻辑电路浓缩在单一芯片内,大大缩 减电路设计及产品上市的时间。近年来由于生产FPGA的公司一直在推出新的产品, 在体积越缩越小的同时,功能也越来越强大,甚至可以在FPGA里面内建DSP及ARM Processor,这也使FPGA应用范围由以前的国防、军用扩展到其它应用领域【4叫。在这 一章中,我们首先阐述FPGA研究的意义及现状,重点说明在VLSI系统设计使用FPGA 的优缺点。然后,我们介绍了FPGA的CAD(计算机辅助设计)流程并显示了它与一 个典型的ASIC(专用集成电路)设计流程的区别。最后,我们将探讨这篇论文是如何 解决FPGACAD流程中的布局布线问题。 1.2 FPGA研究的意义及现状 1.2.1 FPGA的现状及发展 1985年Xilinxll-61公司首家推出了现场可编程逻辑器件FPGA,它是一种新型的高密 度PLD(可编程逻辑器件),采用CMoS.SRAM工艺制作,其结构和阵列型PLD不同, 内部由许多独立的可编程逻辑模块组成,逻辑块之间可以灵活地相互连接,具有密度高、 编程速度快、设计灵活和可再配置设计能力等许多优点。FPGA出现后立即受到世界范 围内电子设计工程师的普遍欢迎,并得到迅速发展。 许多人仍然将FPGA视为仅作为一个系统的仿真或制模的设计工具,并且认为 FPGA市场现在处于饱和状况。他们甚至对是否能用FPGA设计出任意的器件实体表示 怀疑。所有这些错误的看法可能来自对于FPGA己发现的缺点的担忧:逻辑密度及设计 速度。然而,目前市场状况显示出一种不同的情况。实际上,FPGA现在被用于诸如网 络、电信、DSP(数字信号处理)、模拟器件17叫等主流产品及消费者电子产品,只是以 之命名的很少。象图1.1(a),仅有33%的FPGA用于仿真或制模,其余的被用于受到严 格的性能限制的实际生产和试生产中。 FPGA不断向新市场渗透,并继续成为电子系统的核心。根据In.Stat报告,全球 FPGA交货值将从2005年的19亿美元增长到2010年的27.5亿美元Il…,其中大部 分将来源于小批量交货。最大的最终用户细分市场将是通信业和工业。 FPGA市场实力的增长有两个因素:它们比PLD有更高的密度和性能,因而它们 能实现更多的功能,而其它替代品(例如ASIC和ASSP)的成本则在多数情况下过于 昂贵。 目前世界各著名半导体器件公司。如Xilinx、Altera[11-12]、Actel[13-14]等公司,均可提供 不同类型的FPGA产品。Xilinx公司生产的FPGA从最初的1200个可利用门发展到现 在已达千万个可利用门。系统内可编程技术、边界扫描技术的出现也使器件在编程技术 和测试技术及系统可重构技术方面有了很快的发展。 众多公司的竞争促进了可编程集成电路技术的提高,使其性能不断完善,产品日益 江南大学博上学位论文 丰富。可以预计,可编程逻辑器件将在结构、密度、功能、速度和性能等各方面得到进 一步发展,并在现代电子系统设计中得到更广泛的应用。 总 成 本 0 2 4 6 8 10 12 14 16 开发费用(百万美元) (c) (d) 图1.1 FPGA的应用及ASIC与FPGA总成本的比较 comp幽n (a)FPGA的应用图;(b)FPGA的生产成本;(c)ASIC的开发费用:(d)ASIC与FPGA总成本的比较 Figure 1.1 FPGA usage pie chart and cost between ASICs and FPGAs. pr洳tion (a)FPGA usage chart;(b)111e comp豳n cost cosE ofFPGA;(c)ne deveI叩mem costs ofASIC;(d)Total between ASICs锄d FPGAs 1.2.2 FPGA的优点 ①上市时问短 ②成本高效的设计及验证方法 ⑨可重复编程性 上市时间短是FPGA的一个最大优点。在ASIC设计方法中,即使已经得到了目标 系统的一个验证过的最终设计方案,也要花费几个月甚至1年的时间来生产实现系统的 实际芯片。 与ASIC不同,使用FPGA,一旦我们有了对于一个系统的有效设计,最终芯片可 以通过可编程逻辑单元及互连单元的配置在一天内生产出来。最终用户无需第三方供应 商的任何帮助就可完成FPGA的制作。这种“非定制”的设计方法使得产品能以比用 ASIC方法制作短得多的周期时I.日J进入市场。另~方面,这种短时间上市的优点让FPGA 设计软件承担了很大的压力。为了达到产品的快速周期时间,FPGA设计软件必须能快 速地将HDL(硬件描述语占)描述编辑成配置比特流。 高效的设计及验证是“非定制”FPGA设计方法的另~直接成果。如图1.1(b)所示, 2 第一章绪论 随着半导体制造技术的进步,硅器件的单位面积制造成本迅速降低,FPGA厂商不断采 用新工艺使得FPGA的单片价格不断下降。相反随着设计复杂性的增加,ASIC的开发 费用逐渐增加,如图1.1(c)所示。图11(d)比较了ASIC与FPGA之间的总体成本115】。由 于FPGA设计系统不需要任何定制的掩模制造,所以就没有相应的工装费用。随着技术 进步,由于生产设备越来越先进,ASIC的起动费用持续走高而FPGA起动费用近似不 变。FPGA和ASIC的交叠容量也不断增长,这使得FPGA在越高的容量越能高效的利 用成本。就系统测试和验证而言,使用FPGA的设计者比ASIC设计者有更多的自由度 和灵活性。考虑到实体制造成本,ASIC设计必须花费很多成本在时序仿真上以在生产 阶段之前保证设计的正确性。FPGA设计在一个较小风险下工作。首先,由于FPGA的 可再编程性,任何在设计中发现的缺陷都可以不用附加成本进行修正。其次,用以FPGA 设计好的芯片对整个系统进行在线测试是可行的。因此,整个系统可以全速运行并且时 间精确。比纯粹基于仿真的检验方法更彻底地排除可能的系统错误。 在当前市场上可能得到的大多数FPGA一基于SRAM或基于EPROM[13-19J一可以提 供可再编程性。这种可再编程性在减少产品的生命周期成本上是十分重要的。另一方面, 由于产业动态在快速地变化,新产品在较短时间内达到大容量,这时生命周期逐渐变得 更短。更糟的是,由于缺乏工业标准,有时一个简单的产品需要多次实现。在这种情况 下,可再编程为系统设计者提供了巨大的灵活性。一个VLSI设计者在通过现场已配置 好的系统中重新配置FPGA能够以最小的成本自由地修改现存的设计或彻底重新设计 一个产品。 1.23 FPGA的缺点 ①低逻辑密度 ②低电路速度 逻辑密度是指在芯片上能配置的逻辑数。由于FPGA必须提供可编程性,因此有相 当大的面积惩罚。可编程电路单元为逻辑设计者提供了很大的灵活性用以实现任意的逻 辑功能及线网模式。但同时,这些可编程电路单元比ASIC定制的电路单元占据更大的空 间,特别是在一个固定FPGA面积中留下较少的空间用以实现有用的电路逻辑。当前的 FPGA结构研究揭示:在一个简单的FPGA中,逻辑面积仅占可编程互连面积的10%。由 于这一有限的逻辑容量,为了实现完全的逻辑功能,相比于ASIC技术FPGA需要具有更 高逻辑容量的芯片。实现一个系统需要多重FPGA是十分普遍的。在一个FPGA中使用额 外的逻辑单元或布线资源的边际成本为O,但是如果设计与单个硬模不匹配则成本会快 速增加。因此,有限的逻辑容量成为在显著增长的系统成本中的一个主要因素。 相对较慢的电路速度是FPGA技术的另一个众所周知的缺点。FPGA的连接线路由可 编程互连点(PIP)及线网段构成。除金属线网段的寄生电阻、电容之外,每个可编程 互连点也包含电阻及电容,这导致较长的信号传播延迟。不幸的是,在FPGA设计中, 来自这些可编程互连点的扩大的延迟决定着线网互连延迟(即,布线延迟),而布线延 迟是远远超过逻辑延迟的。因此这些可编程互连单元虽然提供了设计灵活性但也是 FPGA设计低效的首要因素。 1.2.4当前FPGA器件特征及研究方向 FPGAj下在从一个系统的单一胶合逻辑进入千万门级系统器件。可编程逻辑的每个 逻辑单元的成本持续下降,FPGA已逐渐成为推动半导体制造业前进的最新动力。具有 各种系统IP(知识产权)特征的内部器件对于大多数前沿应用己足够快了。因此,由于 其提供给最终用户的灵活性,FPGA日益被看作是解决ASIC设计上市时间问题的一个极 江南大学博士学位论文 好的方案并且逐渐被当作ASIC技术的一个替代设计方法。 FPGA产业的研究人员及商家不仅努力提高逻辑密度而且尽力提高FPGA电路速度。 这使得这两个领域在过去十年都取得了重大进展。逻辑密度以数量级提升。例如,2006 年,65纳米FPGA上市。FPGA的两大供应商Xilinx公司和Altera公司先后推出采用65纳 米的FPGA系列Virtex.5和Stratix III。其中,Virtex.5含有33万个逻辑单元,可用I/O已达 到1200个。Stratix Ill含有33万个等效逻辑单元,500多个18X 18乘法器,用户可用I/O达 到1100个f191。表1.1显示了一组来I刍Xinlinx的典型FPGA的逻辑密度15J。除了逻辑密度上 的提高,现在大多数FPGA供应商在他们的FPGA上还提供很多种类的系统级特征,现在 嵌入式块RAM已成为标准。支持多重I/O标准以及甚至是嵌入式微处理器的多重系统时 钟、I,o系统出现在先进的FPGA中,这便利了系统设计。 在电路速度方面取得的进展虽不如逻辑密度方面的那么显著,但也足以引起VLSI 设计者的注意。采用FPGA可以快速实现数字电路,但是用于生成FPGA编程的比特流文 件的cAD工具在编制大型电路时常常需要数小时的时间。许多设计者甚至通过在给定 FPGA上采用更多的资源或者以牺牲电路速度为代价来提高编制速度。由于FPGA的布线 资源占用了FPGA约70%--80%的芯片面积和约50%--60%的信号时延,因此编制电路过程 中,大部分的编制时间花费在布线阶段。表1.2显示了采用Xilinx Mi CADI具对MCNC[201 中部分基准电路的总体布局布线时间。一个好的布线算法能够在减少布线资源占用的同 时快速完成信号配置从而缩短信号时延,因此当Iji『在工艺条件一定的情况下,布线算法 的改进及优化对FPGA的设计者有着很大的吸引力。这也是本论文研究的重点。 表1.1来自Xinlinx的典型FPGA的逻辑密度 Table 1.1 Logic densities oftypical Xilinx FPGAs . Dev. l。。 XC5VLX30T CLB阵列大小 逻辑单元 (列×行)LC(3) 80×30 30720 XC5VLX50T 120×30 46080 XC5VLX85T 120×54 82944 XC5VLXllOT 160×54 110592 XC5VLX330T 240×108 331776 … s11。。8 4800 7200 12960 17280 51 840 CLB触 发器 19,200 28,800 51.840 69,120 207。360 Circuit Alu4 frisc ¥38417 clma 表1.2采用Xilinx Ml工具的布局布线时间 11able 1.2 Place and route times for Xilinx M1(using 300 MHz UltraSPARC) Approximate Gate Count 18.000 Xilinx M1(ver.4.12)Place and Route Time(s) 214 42.000 1058 76.000 1660 1 00。000 4229 4 第一章绪论 1.3FPGA设计的CAD流程 在这一节,我们描述一典型的FPGA设计流程120-26]并将之与ASIC流程相比较。通 常VLSI系统设计将设计步骤分隔成一连串易处理的的步骤。这个通用规则也适用于 FPGA设计流程。总的来说,FPGA设计流程由3个主要步骤组成:系统设计、设计实 现及设计验证(图1.2)。在这些步骤中,系统设计阶段与基本的FPGA结构无关,而设 计实现和验证阶段与目标FPGA结构密切相关。 1.3.1系统设计 在对可编程逻辑器件的芯片进行设计之前,首先要进行方案论证、系统设计和器件 选择等设计准备工作【2””。设计者首先要根据任务要求,如系统所完成的功能及复杂程 度,对工作速度和器件本身的资源、成本及连线的可布线性等方面进行权衡,选择合适 的设计方案和合适的器件类型。系统设计阶段由两个子过程组成:设计输入及逻辑综合 及优化。 设计输入阶段是在尽力满足一系列约束条件的同时,模型化并描述目标系统的过 程。这些描述通常用HDL或原理图级电路设计编辑程序表示。设计输入通常有以下几 种方式:(1)原理图输入方式;(2)硬件描述语言输入方式;(3)波形输入方式。考虑 到当代设计的复杂性,HDL例如Verilog或VHDL是当前设计输入普遍采用的方法。现 已存在大量各种各样的设计输入程序。事实上,由于设计输入与基本的FPGA结构无关, 因此第三方EDA供应商已成为设计输入商品的主要供应者。 化简所有的逻辑方程或用户自建的宏,使设计所占用的资源最少即为逻辑优化。综 合的目的是将多个模块化设计文件合并为一个网表文件,并使层次设计平面化(即展平)。 一旦目标系统用HDL或原理图级电路形式表示出来,逻辑综合过程将其转化为布尔表 达式,随后通过布尔代数处理做面积及速度优化。这些过程与ASIC设计流程中的几乎 完全一样,用于ASIC设计的综合优化算法很容易直接采用于或作较小的修改后用于 FPGA。 1.3.2设计实现 设计实现阶段与基本FPGA结构129-311联系紧密,这是本论文的主要内容。设计实现 阶段可以进一步分为3个子步骤:工艺映射【320 61、布局口7-461、布线【47-7丑。 工艺映射从字面上讲是指将由逻辑综合产生的布尔功能图绘制成基本逻辑单元,例 如:查找表(LUTs)、触发器、I/O块等。自然地,工艺映射工具应当能识别出目标FPGA 结构尤其是上面列出的基本逻辑单元以保证能成功地实现设计功能。FPGA的大多数工 艺映射工具的优化目标或者是基本逻辑单元数的最小化(面积优化)或者是最大逻辑门 延迟的最小化(延迟优化)。FPGA工艺映射流程的独特特征之一是:与ASIC流程不同, 为了减少信号延迟,为了使设计能符合每个器件的要求,采用冗余逻辑单元。换句话说, 在FPGA中,逻辑资源的优化使用比资源的最小化更重要。然而,逻辑单元的冗余不能 影响后面阶段设计的可布线能力。 一个已映射好的设计必须通过一个网表建模,这个网表捕捉FPGA结构的基本逻辑 单元之间的所需互连线的信息。这个网表用作设计实现下一阶段的输入,该阶段将每个 逻辑单元放在目标FPGA芯片的特殊物理位置上。利用网表信息,典型的布局算法尽量 减少互连线的总长度,以最小化信号延迟以及在最后布线阶段提高可布线能力。大多数 FPGA布局工具采用仍与传统ASIC布局算法十分相似的算法。例如,一种流行的FPGA 布局方法是基于一种具有标准度量的迭代移动筛选算法,如模拟退火算法【7M21。出现这 江南大学博士学位论文 一情况的主要原因是:(1)相比ASIC设计,在典型的FPGA设计中有许多可少许移动 的对象:(2)模拟退火算法可以容易地实现在运行时间和方案质量之间的交换。然而, 在FPGA与ASIC之间的局部度量上有很重要的区别:布线延迟估计。为了估计在ASIC 设计中信号的延迟,通常在布局过程中构造~个R-C树来模拟信号的拓扑结构,并计算 相应的R-C延迟值。其所包含的计算虽然在计算上细致但不够精确,并且当特征尺寸降 至DSM(深亚微米)范围后这种情况更为严重。FPGA的延迟计算要简单的多,这是因 为每个连接线仅有有限个信号模式,而且FPGA的延迟可以得到更精确地计算,这是因 为在FPGA中大多数延迟因子是布线开关(即传输管)及构成信号网的金属线段部分。 因此,延迟主要决定于连接模式并必然与连接线长度成比例。相比ASIC,在FPGA中 的DSM效应例如耦合电容更容易被屏蔽。在FPGA布局算法中,一个更为重要的要素 为拥挤度量,这是因为最终设计中,所有信号在满足了作用时间约束条件的同时,必须 分享有限个可利用的布线资源。虽然一般认为,FPGA的结构应该会对布局度量产生重 大影响(即,评估布局方案的质量),但是现今采用的FPGA布局工具仍在直接借用于 ASIC流程而没有对目标FPGA作出重大适应性调整。 设计实现的最后阶段是将布局好了的设计进行布线。布线阶段在布局好了的网表中 为每个连线选定适当的布线资源(即,金属线段及可编程开关)。布局布线工序产生了 一个“比特组态流”,它描述的是如何配置逻辑单元及布线资源以实现设计。在FPGA 布线领域中以结构为依据的算法是必不可少的。FPGA布线问题可定义为:找到将布线 资源分配给每个线网连线的一种配置方法,同时满足所有其上的时延约束条件。FPGA 与ASIC布线算法的虽大差别是:ASIC布线法尽力将布线资源(电路的布线路径,线 路的数目等)的使用最小化。而FPGA布线主要致力于优化可用资源的使用以将获得可 布线布局的可能性最大化。这一差别来自这样一个事实:FPGA布线资源使用的最小化 不一定意味着在设计中就可以提高可布线能力。换句话说,由于FPGA上的线资源数是 固定的,拥挤控制及解决资源竞争132d6l是FPGA布线法中必须综合考虑的重要因素。在 布局中布线延迟的计算也会出现类似的问题,这是因为实际延迟依赖于线网模式多过线 段的拓扑长度。大多数流行的FPOA布线方法仍基于来自ASIC设计流程的基本迷宫布 线算法。迷宫布线由于其优良的表现及易于实现是一种十分流行的算法。当布线层的几 何结构是具有许多障碍物的复杂图形时,迷宫布线算法[s3删在找寻一条连线的复杂(弯 路)路径时也是极为优秀的。然而象当前大多数可利用的布线算法一样,迷宫布线算法 的一个最大缺点是他们依赖于线网顺序。换句话说,先前已布好线的线网其作用就像是 障碍物一样并且被这些线网消耗了的布线资源不能用于将被布线的线网。线网次序严重 影响了最终的布线方案的质量,然而获得一个最优化的线网顺序的方法仍然未知。迷宫 布线算法也可以被归类为一种寻找每条连线的最短(最小成本)路径的资源最小化算法。 但不幸的是,迷宫布线法不能提供关于一个给定布局的可布通性(可行性)的任何信息。 虽然通过复杂的功耗度量,它有可能考虑到一个对一条连线作出的布线决定对另一条连 线产生的副作用,但是迷宫布线法不能同时考虑到线网的所有布线副作用。结果,迷宫 布线法不能确定在给定布局及FPGA结构条件下一给定电路是否能布通。 1.3.3设计验证 设计验证过程包括功能仿真和时序仿真,这两项工作是在设计处理过程中间同时进 行的。 功能仿真是在设计输入完成之后,选择具体器件进行编译之前进行的逻辑功能验 证,因此又称为前仿真。此时的仿真没有延时信息,对于初步的功能检测非常方便。仿 真前,要先利用波形编辑器或硬件描述语言等建立波形文件或测试向量(即将所关心的 6 第一章绪论 输入信号组合成序列),仿真结果将会生成报告文件和输出信号波形,从中便可以观察 到各个节点的信号变化。若发现错误,则返回设计输入中修改逻辑设计。 时序仿真是在选择了具体器件并完成布局、布线之后进行的时序关系仿真,因此又 称后仿真或延时仿真。由于不同器件的内部延时不一样,不同的布局、布线方案也给延 时造成不同的影响,因此在设计处理以后,对系统和各模块进行时序仿真,分析其时序 关系,估计设计的性能以及检查和消除竞争冒险等是非常有必要的。实际上这也是与实 际器件工作情况基本相同的仿真。 图1.2 FPGA设计流程图 Figure 1.2 FPGA design flow diagram 7 江南大学博t学位论文 1.4本论文的研究目的及内容 在此论文中,我们着重于FPGA的最后阶段,即布线问题。认识至UFPGA芯片不断增 长的复杂性,必须开发具有下列特征的FPGA布线算法: (1)对FPGA结构的适应性:布线算法必须能很容易适应不同的布线结构而不在性 能(方案及运行时间的质量)上出现任何下降。事实上,FPGA结构与物理设计实现工 具应该共同发展。换句话说,新型结构与FPGACAD工具应该并行发展。如果不将FPGA 结构与物理设计实现工具相结合,就很难控制布线方案的质量。而且,FPGA CADI具 能够对某些结构特征的增/减提出对策,以提高设计应用过程的综合有效性。 (2)更精确的拥挤模式:FPGA布线的目标是实现一个满足特殊设计约束条件的可 布线设计。为了将设计的可布线几率最大化,布线资源的冲突应减至最小。因此,相比 现存的物理实现工具,基本的布局布线算法花费更多的成本在衡量布线资源的竞争上。 (3)可布线性的判定与估计:能在一给定布局上表明设计的可行性的新布线算法 是十分有吸引力的。还在布局阶段就可以估计每个布局结构的可布线性的能力十分有助 于生成~个较好的布局方案。普通的一次一线布线算法(例如迷宫布线法)由于其对布 线顺序的依赖而不能确定可布线性。换句话说,对于一给定的布局,为确定一种设计是 否可布线的布线算法必须是与布线顺序无关的并行的方法。 当前,在FPGA布线算法中,布尔可满足性(SAT)布线算法及几何查找布线算法 是两种最为流行的算法。然而,这两种算法都存在各自缺陷,不能完全满足FPGA布线 特征的要求:一方面基于SAT的布线算法在可扩张性上有很大缺陷:而另一方面,几何 查找布线算法即使具有广泛的拆线重布线的能力,但当一个问题具有严格的布线约束条 件时,它在御线方案收敛方面存在很大困难。 论文中心是对满足以上特征的一种新的FPGA布线算法的提出与分析。这种算法采 用将一种基于线路的布尔可满足性算法(SAT[91“”1)算法R.SDR[116-121]与传统的几何查 找布线算法PathFinderll22‘1261、VPR430[127。13 21、FrontierI‘33’138l相结合,这样既克服了SAT 算法在可扩展性方面不可避免的局限性,又弥补了传统的几何查找布线算法在可布线性 判定方面的缺陷。然后对不可布线的线网采用子集可满足性方法(sub—SAT)【I”1屏蔽部 分线网,使得由于有少数线网不能布线的电路得以布通。 1.5本论文的编捧 论文其余部分构成如下: 第2章全面阐述FPGA结构特征、结构模型以及产品供应商在FPGA结构上的研究 动态。展示了论文布线试验中所采用的布线基准。 在第3章中,详细介绍了用于FPGA布线的基本迷宫布线算法Lee及现今最为流行 的PathFinder、VPR430算法及最新开发的Frontier算法,并在同一平台上对其在布线时 间及稳定性上进行研究。 在第4章中,研究了基于轨线的布尔函数布线方法,并展示这个方法是如何应用于 FPGA详细布线的。接着研究了一种可替代的基于路线的详细的布线公式。与基于轨线 的公式相比,基于路线的公式产生了更加紧密的SAT实例,并因此更加有效。给出基于 轨线与基于路线公式之间对比实验的结果。将这些SAT算法与传统几何布线法进行了 比较,得到了详细的试验结果并深入地分析了此方法相对于传统布线法的优缺点,提出 其改进的方向。 在第5章中,提出了将基于布尔函数的布线法与目前最高水平的常规几何查找 8 第一章绪论 FPGA布线算法相结合的方法,不仅克服了基于布尔函数FPGA布线算法的主要缺点, 即可扩展性问题,而且补偿了传统布线法的典型缺陷:布线顺序依赖性及不能证明不可 布线性。换句话说,这两种方法相互补充。为了验证这种方法,给出了将结合后的算法 应用于现实基准的结果。 第6章给出了一种将一种子集可满足性方法用于第5章的混合算法,生成一种新型 混合算法,这种方法有效地解决了电路中存在少数不可布线线网的问题。 参考文献 【1】Xilinx Corporation,The Programmable 12。gic Data Book.1996. 【2】Xilinx Corporation,The Xilinx Foundation Series 1.4,1998. 13】Xilinx Inc.,The Programmable Logic Data Book.1 994. 【4】Xilinx,XC4000E and XC4000X Series Field Programmable Gate Arrays。Product Specification,November 1997,available from www.xilinx.eora. 【5】Xilinx Inc,Virtex II Data Book,2004. [61 Xilinx Corporation,The Programmable Logic Data Book,1998. 【7】刘战,须自明,王国章,等.高阶紧致差分与ADI结合的器件模拟方法【J】.固体电 子学研究与进展.2006。26(2):230.233. 【8】 于宗光,刘战,王国章,等.适于薄膜SOI RESURF器件击穿电压模拟的高阶紧 致差分格式离散的ADI方法【J】.半导体学报,2006,27(2):354.357。 【9】刘战,须自叽王国章,于宗光.适于半导体器件模拟的高阶紧致差分方法【c】.第 十届计算机工程与工艺学术年会.2006(1):277.279. 【10】www.guangdongdz.oora 【ll】Altera Data Book.Altera Corporation,1996. 112]AItera Corporation,Stratix II Device Handbook.Volume 1.Jul 2004. 【l 3】Actel Inc,Axcelerator family FPGA,2004. I 14】Actel Corporation,MX FPGA Data Sheet,version 5.0,February 2001 【15】Electronics Weekly;ABI/INFORM Trade&Industry,Feb 25,2004,12.13. 【16】Brown S,Rose J.Architecture ofFPGAs and CPLDs:A Tutorial.IEEE Design and Test ofComputers.1996.13(2):42.57. 【l 7】Lucent Technologies,Field.Programmable Gate Arrays Data Book.Oct.1996. 【l 8】Borriello G Ebeling C,Hauck S,et a1.The triptych FPGA architecture.IEEE Trans.on VLSI Systems,Deeembet 1995,3(4):491.501. r1 91 http://www.blogchina.com/idea/moore40/ 【20】Yang S.Logic Synthesis and Optimization Benchmarks,Version 3.0.Technique Report, MicroelectroniCS Center ofNorth Carolina,1991. [2l】Brown S,Francis R Rose J,et a1.Field.Programmable Gate Arrays.Kluwer Academic Publishers.1992. 【22】Atrael Corporation,Configurable Logic Design and Alication Book,1994. 【23】Betz V,Rose J,Marquardt A.Architecture and CAD for deep-submicron FPGAs. KIuwgr Academic Publishers.ISBN 0-7923.8460.1.1 999. 【24】Cong J.Technology Maing for FPGAs砸tIl Embedded Memory Blocks.Proe.FPGA.98, ACM. 【25]Kumthekar B.In—Place Power Optimization for LUT.Bascd FPGAs.Proceedings 9 江南大学博士学位论文 Design Automation Conference,ACM/IEEE,1998,5(2):15—18. 【26】Zlli-Hong Wang Power Minimization in LUT·Based FPGA Technology Making. Proceedings ofthe ASP.DAC.200l,3:635—640. [271 http://www.ilog.com. (281 Brown S,Francis R J’Rose J,et a1.Field-Programmable Gate Arrays.Kluwer Aeademie Publishers.Boston,Ma'1992. 『291 Lai Y T,Wang P T.Hierarchieal Interconneetion Structures for Field Programmable Gate Arrays,IEEE Transactions on VLSI,June 1997,5(2):186—196. 『30]Rose J,HilJ D.Architectural and Physical Design Challenges for One-Million Gate FPGAs and Beyond.In 5th International Workshop on Field—Programmable Gate Arrays. [311 Monterey.C丑2005.5:129.132. Wilton S.Architeetures and Algorithms for Field.Programmable Gate Arrays with Embedded Memories。Ph.D.Dissertation,University of Toronto,1 997.(Available for download from http://www.ee.ube.ca/--stevew/publications.html). 【32】Chang Y, Wong D, Wong C. Universal Switch·Module Design for Symmetric.Array.Based FPGAs.Proceedings of the Intemational Symposium on [331 Field.Programmable Gate Arrays.1996.2:80·86. Nilsson N.Problem.Solving Methods in Artificial McGraw—Hill.1971.6:255—260. Intelligence.New York: [34】Pe盯l J.Heuristics:Intelligent Search Strategies for Computer Problem Solving. Reading.MA:Addison Wesley.1984. 051 f361 [371 Jayaraman R.Physical Design For FPGAs,ISPD 200l,Sonoma,CA. Devadas S.Logic Synthesis.McGraw-Hill,NeW YorL NY,l 994. Alexander M,Cohoon J.,GaMey J.,el a1.Performance—Oriented Placement and Routing for Field—Programmable Gate Arrays. European Design Automation Conf.. 1995.12:80.85. 【38】Ebeling C,McMurchie L.,Hauck S.A.et a1.Placement and Routing Tools for the Tnptvch FPGA.IEEE Tram.on VLSI,Dee.1995,12:473-482. 【39】Betz v.Architectures and Algorithms for Field—Programmable Gate Arrays.Ph.D. Dissertation,University ofToronto.1998. [40】Gudise V,Venayagamoorthy G.FPGA Placement and Routing Using Particle Swarm Symposium Optimization.In Proceedings of the IEEE Computer Society Annual on VLSI Emerging Trends in VLSI Systems Design,2004.12:307—308. 【41】Donath W E.Placement and Average Interconnect Lengths of Computer LOgic.IEEE Transactions on Circuits and Systems,CAS—Apr.1979,26(4):272-277. 『421 Frankle J.Iterative and Adaptive Slack Allocation for Performance.driven Layout and FPGA Routing.In Proceedings.ACM/IEEE 298t Design Automation Conference. 1992.3:536.542. 『43]Nag S,Rutenbar R.Performance—Dfivell Simulataneous Place and Route for Island.St3,le FPGAs.In ICCAD.1995.6:142.151. Ⅲ1 Sankar Y.Fast Placement for FPGAs.In Proceedings:University of Toronto FPGA Research Review,Peterborough,Ontario,1997,6:221-232. 『451 Sankar Y.Ultm-Fast Placement for FPGAs.MaSterIS thesis,University of Toronto, Department ofElectrical and Computer Engineering,1998. 10 第一章绪论 【46】Sherwani N.Algorithms for Physical Design Automation.Kluwer Academic Publishers, Boston,Ma,1 992. 【47】Cohoon J P,Heck P L.BEAVER:A eomputational geometry based tOOl for switch-box routing.IEEE Transactions on Computer Aided design,1988.7:684.697. [48】Shin H,San#ovanni V.A detailed router based on ineremental router modifications. IEEE Transactions on Computer-Aided design,1987.6:942.955 【49】Lin Y,Hsu Y,Tsaj F.Hybrid Routing.IEEE Transactions on Computer-Aided Design, 1990,9(2):151-157. 【50】Kuh E S,Marek·Sadowska M.Global routing.In Layout Design and Verification,T. Ohtsuki,Ed.New York:Elsevier Science,1986,5:169.198. [51】Linsker R.An iterative-improvement penalty-function driven wire routing system.IBM J.Res.Develop,1984,8(5):613-624. 【52】Nair R.A Simple Yet Effective Technique for Global Wiring.IEEE Trans.on cAD, 1987.3:165.172. 【53】Brown S,Rose J,Z,Vranesic G A Detailed Router for Field.Programmable Gate Arrays. IEEE Trans.on CAD,May 1992,11(5):620.628. 【54】Rose J S.Parallel Global Routing for Standard Cells.IEEE Trans.on CAD。. 1990.10:1085—1095. 【55】谭向东,童家榕,唐璞山.适用于数字电路的通用划分算法【J】电子学报 1996.8(24):98·101. 【56】Brown S,Khellah M,Lemieux G,Segmented Routing for Speed.Performance and Routability in Field-Programmable Gate Arrays.Journal of VLSl Design,1 996,4(4): 275.291. 【57】Arslan H,Dutt S.ROAD:An Order-Impervious Complete Detailed Router for FPG舳. ICCD 2003。1】:350-356. S.An 【58】Arslan H,Dutt Effective Hop—Based Detailed Router for FPGAs for Optimizing Track Usage and Circuit Performance.GLSVLSI.2004.4:208.213. 【59】Swartz J,Betz V,Rose J.A fast routability-driven router for FPGAs.In 6th International Workshop On FPG缸,1998.2:140.149. 【60】Alexander M.,Robins G.New Performance-driven FPGA routing algorithms.32nd ACM/IEEE Design Automation Conference,San Francisco,CA,1995,6:562—567. [61】Lysecky R Vahid F,Tan S.Dynamic FPGA Routing for Just-in-Time FPGA Compilation.DAC,San Diego,CA.2004.1l:954.959. 【62】Brown S.Routing Algorithm and Architectures for Field programmable Gate Arrays. PhD thesis,Department ofElectrical Engineering.University ofToronto.1992. 【63】Betz V,Rose J.On Biased and Non·Uniforill Global Routing Architectures and CAD Tools for FPGAs.University of Toronto Department of Electrical Engineering, Technical Report,1 996,6:358—362. 【64】Lemieux G,Brown S.A Detailed Router for Allocating wire Segments in FPGAs.Proe. ACM Physical Design Workshop.California,1993.4:215-226. 【65】Brown S,Rose J.Vranesic Z.A detailed router for field·progranunable gate arrays. IEEE Tram.on CAD,1992。11(5):620.628. 【66】Clow G W.A Global Routing Algorithm for General Cells.In Proceedings.ACM/IEEE 21“DesignAutomationConference,1984。21:45.51. 江南大学博士学位论文 【67】Swartz J.Rapid Routing for FPGAs.In Proceedings:University of Toronto FPGA Research Review,Peterborough,Ontario.1 997,6:22 1—232. 【68】Aggarwal A,Lewis D.Routing Architectures for Hierarchical Field-Programmable Gate Arrays.In Proceedings IEEE Custom Intgerated Circuits Conference。I 994,6:475-478. 【69】Betz V,Rose J.FPGA Routing Architecture:Segmentation and Buffering to Optimize Speed and Density.ACM/SIGDA Intemational Symposium on Field Programmable GateArrays.Monterey,CAl999.11:59.68. [701 Gomez—Prado D,Ciesielski M.A Tutorial on FPGA Routing.Department of Electrieal and Computer Engineering,Urdversity ofMassachusetts,Amherst,USA.2004. 【71】Tseng B,Rose J,Brown S.Using Architcctural and CAD Interactions to Improve FPGA Routing Arcllitectures. First International ACM/SIGDA Workshop on Field-Programmable Gate Arrays.1992,2:3.8. [72】Aggarwland A,Lewis D.Routing Architectures for Hierarchical Field Programmable Gate Arrays. In Proceedings IEEE Custom Intgerated Circuits Conference, 1994.5:475-478. [731 Cook S A,Mitchell D G.Finding Hard Instances ofthe Satisfiability Problem:A Survey. DIMACS Ser.Discr.Math.&Theor.Comp.Sci..1997.6:1-17. 【74】DIMACS Boolean Satisfiability Challenge Benchmarks:fip://dimacs.rutgers.edu/pub/ challengUsat/benchmarks/cnf [751 Kravets V,Sakallah K.Generalized Symmetries of Boolean Functions.ICCAD, 2000.10:526—532. 【76】Soicher L H.GRAPE:A System For Computing With Graphs and Groups.in Groups and Computation,DIMACS Ser. in Discr. Math. &Theor. Comp. Sci.. 1993.11:287.291. [771 Goldberg E,Novikov Y.BerkMin:A Fast and Robust SAT.solver.in Proc.Design Automation and Test In Europe.2002,9:142—149. [781 Bem J。Meinel C,Slobodova A.Efficient OBDD.Based Boolean Manipulation in CAD Beyond Current Limits.Proc ACM/IEEE DAC.1995,6:408-413. f791 Berman L.Ordered Binary Decision Diagrams and Circuit Structure.Proe.IEEE ICCD, 1989.10:392.395. 『801 Ghan P K.On Routability Prediction for Field Programmable gate Arrays.Proe.IEEE DAC.1 993.6:326.330 f811 Glenn Wood R.Routing for FPGAs via Boolean Satisfiability.M.S.Thesis,Dept.of ECE.Carnegie Melton University.May 1996. 【82】Benini L,Micheli G D.A survey of Boolean matching techniques for library binding. ACM Trans.Des.Autom.Electron.Syst..1997,2(3):193.226. f831 Soukup J.Fast Maze Router,Proc.1 5th Design Automation Conf.,1978,6:100-102. f841 C Lee.An Algorithm for Path Conneetions and its Applications,IRE 7Funsactions on Electronic Computers.1961.9:346-356. f851 Rubin F.nle Lee Path Connection Algorithm,IEEE Trans.Computers,1974,9:907—914. [861 Soukup J.Fast maze router,In Proe.Design Automation Conf.,1978,6:100.102. [87】Dijkstra E.W.A note on two problems in connexion、ⅣitIl graphs,Numerische Mathematik.1959(1):269.27l 【88】Swartz J.A Hi曲Speed TiIIling-Aware Router for FPGAs,Master's Thesis,Department 12 第一章绪论 ofElectrical and Computer Engineering,1998. 『891 Plaezewsk M.Plane Parallel A。Maze Router and Its Alieation to FPGAs,DAC, 1992.69l-697. 【90】Mo F,Tabbara气Bmyton&A Force-Directed Maze Router,Department of EECS, University ofCalifomia at Berkeley.2001.404-407. f911 Garey M R,Johnson D.S.Computers and Intractability:A Guide to the Theory of NP.Completeness.W.H.Freeman and Company.1 979. f921 Bryant R E.Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. ACM Computing Surveys,Sept.1992。24(3):293—318. 【93】hRp://www.eecg.toronto.edu/一vaughn/challenge/challenge.html [941 Wood R G,Rutenbar R A.FPGA Routing and Routability Estimation Via Boolean Satisfiability.IEEE Transactions on VLSI Systems.1998.6:222.231. 【95】Bryant R E.Binary decision diagrams and beyond:enabling technologies for formal verification.in Proc.ACMAEEE Int.Conf.Computer-Aided Design,1995.11:236—243. 【96】Marques-Silva J P,Silva L G.Algorithms for satisfiability in eombinational circuits based on backtrack search and recursive learning.in Proc.12也Symp.Integrated Circuits Syst.Design,1999.9:192-195. 【97】Zhao Y,Zhang L,Malik S.C11a僚engineering all efficient SAT solver.in Proc ACM/IEEE 39th Design Automation Conf.,Las Vegas,2001,6:530.535. [981 Velev M,Bryant R E.,Effective use of Boolean satisfiability procedures in the foFinal verification of supersealar and VLIW microprocessors.in Proc.ACM/IEEE Design Automation Conf..2001.6:226.231. 【99】Devadas S.Optimal layout via Boolean satisfiability.in Proc.ACM/IEEE Int.Conf. Computer-Aided Design,1989.1l:294.297. 【100]Hansen P,Jaumard B.Algorithms for the maximum satisfiability problem.Computing, 1990.44:279.303. [1011CIla B,1wama K Kambayashi Y,et a1.Local search algorithms for partial MAXSAT.iIl Proe.14th Nat.Coaf.Artificial Intell..1997.8:263.268. [102]Hooker J N.Resolution and the integrality of satisfiability problems.Math.Progra, 1996(74):1.10. f1031Wilton S.Architectures and Algorithms for Field.Programmable Gate Arrays with Embedded Memories.Ph.D.Dissertation,University ofToronto.1997. 【104]Pearl J.Heuristics:Intelligent Search Strategies for Computer Problem Solving. Reading.MA:Addison Wesley.1984. 【105]Yang S.Logic Synthesis and Optimization Benchmarks,Version 3.0,Technique Report, Microelectronies Center ofNorth Carolina,l 991. 【1 06】Bryant IL Graph—Based Algorithms for Boolean Function Manipulation.IEEE Trans.on Computers.1986.3:677.691. [1 07】Silva J,Sakallah K.GRASP:A Search Algorithm for Propositional Satisfiability.IEEE Trans.on Computers.May 1999.48(5):506.521. 【108]Aloul F,Markov I。Sakallah K.Faster SAT and Smaller BDDs via Common Structure. ICCAD 2001.7:443.448. 【1 09】Beame P,Karp R’Pitassi T,et a1.The efficiency of Resolmion and Davis.Putnam Procedare.SIAM Journal on Computing.2002,4(3n:1048.1057. 江南大学博士学位论文 【1 10]Brisoux L,Gregoire E,Sals L.Improving backtrack search for SAT by means of redundancy.Foundations of Intelligent Systems.1 lth Intl.Symp.,JSMIS’99.Berl氓 Germany:Springer I 999.】1:301-309. 『l 11 1Brown C A,Finkelstein L,Purdom P W.Backtrack scarehing.m the presence of symmetry.(T.Mora,editor),Alied algebra,algebraic algorithms and glTor correcting codes,6th intl.conf.,Springer-Verlag,1988,6:99.110. 【1 12]Cong J,Hwang Y Y.Boolean matching for LUT-based logic blocks埘tll alications to architectare evaluation and technology maing.IEEE Tram.on CAD.2001. 20(9):1077-1090. f1 13]Vemuri N,Kalla P,Tessier R.BDD.based logic synthesis for LUT.based FPGAs.ACM Tram.on Design Automation ofElectronic Systems.2002.7(4):50卜525. 【1 14]Brown S,Rose J,Vranesic z,A detailed router for field programmable gate arrays. IEEE Trans.Computer.Aided Design.May 1992(1 1):620-628.. 『1 15]Swartz J S,Betz V,Rose J.A fast routability driven router for FPGA5.in Int.Symp. FPGAs.1998.5:140.149. 【l 16]Nam G,Sakallah K Rutenbar R.Hybrid Routing for FPGAs by Integrating Boolean Satisfiability witll Geometric Search.International Conference on Field Programmable Logic and Alications。2002,9:360—369. 『l 17]Nam G,Sakallab l(,Rutenbar R.A New FPGA Detailed Routing Approach Via Search.Based Boolean Satisfiability.IEEE Transactions on computer.aided design of integrated circuits and systems,June 2002,21(6):674.684. n l 8]Nam G,Sakallah k Rutenbar R.A Satisfiability.based layout revisited:routing complex FPGA’s via search—based Boolean SAT.in Proc.ACM hat.Symp.FPGAs. 1999.2:167-175. 『1 19]Nam G,Sakallah k Rutenbar R.A Boolean satisfiability based incremental rerouting aroach with alication to FPGAs.In Proc.Design Automation Test Ear..200】.3:560—564. n20]Nam G.A Boolean Based Layout Aroach and its Alication to FPGA Routing.Ph.D. dissertation,Dept.of Elect.Eng.Comp.Sci.,Urtiv.ofMichigan,Ann Arbor,MI,2001. 『121]Nam G,A10ul F,Sakallah l('et a1.A comparative study oftwo Boolean formulations of FPGA detailed routing constraints.in Proc.ACM Int.Symp.Physical Design, 2001.4:222—227. f1221Lemieux G,Brown S,Vranesic D.On Two-Step Routing for FPGAs.In Proceedings: International Symposium on Physical Design,Napa,Ca.,】997,4:60.66. 【123】Sechen C.VLSI Placement and GIobal Routing Using Simulated Annealing.KIuwer Academic Publishers.Boston,M扎1988. 『1 241 McMarchie L,Ebeling C.PathFinder:A Negotiation-Based Perforrnance.Driyen Router for FPGAs.ACM/SIGDA International Symposium on Field.Programmable Gate Arrays。ACM Press,New York NY.1995.12:1l 1.117. 【125]Eheling C,McMurchie L,Hauck S A,el a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(TVLSI).1995.12:473-482. 『1261Betz V Rose J.VPR:A New Packing。Placement and RoIlting 1bol for FPGA Research. International Workshop on FPL,1997.7:213-222. 【127】Betz V.Architectures and Algorithms for Field—Programmable Gate Arrays.Ph.D. Dissertation,University ofToronto.1 998. 14 第一章绪论 【1 281 Betz V.VPR and T-VPack User’s manual—version 4.30,2000. 『129]Andy Gear Ye,Jonathan Rose.Using bus.based connections to improve field—programmable gate array density for implementing datapath circuits.FPGA 2005.6:3-13. 【1301Betz V,Rose J,Marquardt A,Arehilecture and CAD for deep-submicron FPGAs. KIuwer Academic Publishers.1999. [131】Eheling C,McMurehie L,Hauck S气ct a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions On Very Large Scale Integration(TVLSI),1995.12:473-482. 【1321Li G.Heuristics and Experimental Design for FPGA Routing Algorithms.Master's thesis,University ofCincinnati。Computer Science。2001. n 331 DIMACS http:加LMACS.Rutgers.EDU. 【1 34]Nilsson N.Principles of Artificial Intelligence.Morgan Kaufrnmm,San Francisco C气 1980. 【135]Ahmed E,Rose J.The E仃ect of LUT and Cluster Size on Deep.Submicron FPGA Performance and Density.IEEE Transactions on Very Large Seale(VLSI)Systerns。 Marcll,l 2.2004(3):288—298. 【136]Swartz J.A High—Speed Timing—Aware Router for FPGA5.Master's thesis,University ofToronto,Department ofElectrical and Computer Engineering,1998.in preparation. fl 37]Tessier R.Fast Place and Route Aroaches for FPGAs.Ph.D.thesis。Massachusetts Institute ofTechnology,1998. 【l 38】Tcssier R Negotiated A’Routing for FPGAs.In Proceedings of the Fifth Canadian Workshop on Field-Programmable Devices,Montreal,Quebec,Canada,1998,6:14·19. 『139】Xu H,Rutenbar R气Sakallah K.Sub.SAT:A formulation for relaxed Boolean satisfiability、Ⅳitll applications in routing.IEEE Transactions on Computer-aided Design ofIntegrated Circuits and Systems.2003.22(6):814.820. 15 江南人学博土学位论文 第二章FPfiA器件的总体结构及布线基准 2.1前言 这一章的目的在于介绍FPGA结构特征及其相关结构模型。这对理解论文后面章节 的布线公式是十分重要的。首先我们按照可编程互连点(PIPS)的综合组建及实现技巧 对FPGA进行简单的分类。然后展示了一种基于SRAM的FPGA的详细结构特征以及 一个与其相对应的布线结构模型。在本章最后给出论文布线试验中所采用的布线基准。 2.2FPGA的分类 一方面,按照互连线编程工艺,即它们制作的基本方法,FPGA可分为三类:基于 SRAM型、反熔丝型及基于EPROM/EEPROM型【”J。 基于SRAM型:可编程互连线由一个传输晶体管(或传输门)及一个控制它们的 SRAM比特构成(图2.1(a)),由存储在RAM单元中的比特值决定传输晶体管是开还是 关。这一技术的优点是1)通过简单地下载一批新RAM位单元值就可以实现在线电路 的重新配置:2)可以用标准的CMOS(互补型会属氧化物半导体)技术生产。然而, 由于每个SRAM位单元需要至少5个晶体管,相比其他方法需要的面积大的多。而且 由于SRAM的挥发特性,使其需要借助外部电源以维持数据,且操作上需由外部进行 数据下载。应用于实际产品上时,往往需要搭配另一个专用的ROM将程序永久保存, 并且在每次系统启动时,也必须花费许多时『日J将程序从外部的ROM读到FPGA的SRAM 中,对程序的保密性造成不良的影响。 反熔丝型:反熔丝是具有通孔(或接触孔)大小的一次可编程单元(图2.1(b))在 编程lj{『,反熔丝具有高阻抗相当于“未连接”。一旦编程后,反熔丝熔断并在终端之间 建立一个低阻抗连线。此技术的优点为:1)所需面积比开关晶体管小的多:2)它产生 了相当低的R.C线路延迟,这是由于熔丝上的电阻及电容较低。主要缺点是一次可编程 性,即一旦FPGA配置形成一个设计,就不可能将FPGA重新用于不同的设计。 基于EPROM/EEPROM型:与EPROM存储器中所采用的方法相同。EPROM单元 通过浮栅电荷注入而起作用。一个EPROM的晶体管由两个栅组成(图2.I(c)):一个浮 栅及一个选择栅。在非编程状态下通过控制选择栅,晶体管打开。然而,当晶体管流过 大电流编程时,它永久关闭而对其选择门上的信号没有响应。这一技术的优点是它可再 编程而不需要额外存储配置的位。并且其开关所需面积比SRAM开关少的多。然而, 与SRAM FPGA不同的是:EPROM/EEPROM FPGA是非在线可再编程。 另一方面,我们可以按照逻辑单元和互连资源的组建方式将FPGA大体分成四种不 同的类型【1,2,6-9J:对称阵列型FPGA、行排型FPGA、门海型FPGA以及层次化PLD型 FPGA(图2.2)。 对称逻辑阵列型FPGA由芯片围绕着I/O单元的二维阵列可配置逻辑块构成。互连 资源位于逻辑块之间,这些逻辑块在水平方向及垂直方向形成允许任意布线模式的布线 通道。这一类FPGA被称为岛状FPGA,其主要厂家是Xilinx公司[10-15]。 行排型FPGA的结构与标准单元ASIC的非常相似。可编程逻辑组件被排列成多重 行排并且大多数互连线通过它们之间的水平布线资源建立。也存在垂直馈通连线资源, 但它们比水平通道布线明显少得多。Actel公司的大多数FPGA属于这一类¨6.”J。 16 第二章FPGA器件的总体结构及布线摹准 门海型FPGA除可以向最终用户提供可编程灵活性外,在概念上与MPGA(掩模可 编程门阵列)完全相同。芯片的第一层是一个通用可编程单元的“海”,这些单元的连 线在第二层生成。换句话说,互连资源重叠在逻辑单元场的上面。然而,这一类型不像 其他类型那么普遍¨”。 层次化PLD型FPGA与其它FPGA类型有相当大的不同,这是因为他们中每一个 逻辑块都由层次化PLD器件组成。因此这种类型的FPGA可视为一个CPLD(复杂可编 程逻辑器件)的层次化分组。然而,从结构方面来说,这些器件与对称阵列FPGA十分 相似,因为其可配置逻辑单元围绕于可编程互连资源周围。换句话说,尽管在逻辑单元 结构上存在相当大的不同,对称阵列FPGA与层次化PLD FPGA有着一个相似的整体结 构。这种类型的FPGA的主要厂商是Alterall9-23]。 在以上FPGA中,互连资源及他们编程的办法各不相同。 表2.1列出了商用FPGA的特征。Xilinx是市场占有份额最大主要厂商ll捌。因此, 本论文着重于对称阵列型FPGA结构的研究。 Routing 广] Routing wi·re■■■■■■●-—一L-·-■■●■■I · wlre (a) BitLine] elect l I厂J 抛 --1 EPROM I|i L1 Transistor Cord l/ ±l 1ne , 一 Floating gate (c) 图2.】互连线编程工艺 (a)SRAM型;(b)反熔丝型;(e)EPROM型 Figure 2.h Programmable interconnection technologies. (a)SRAM technology,,(b)Anti·Fuse technology:(c)EPROM technology 17 垩壹查堂堡主兰竺笙兰 口口 口口 口 口 口口 口口口口口口口口一I/OB (a) Interconnet js overlaid Oll logic blocks (c) (d) 图2.2商用FPGA的分类 (a)对称阵列型FPGA:(b)行排型FPGA:(cy J海型FPGA:(d)层次PLD型FPGA Figure 2.2 Classification ofcommercial FPGAs. (a)Symmetrical Array;(b)Row-based:(c)Sea-of-gates;(d)Hierarchical PLD 公司 Actel Actera Quick Logic Xinlinx 表2.1商用FPGA特征 Table 2.1:Commercial FPGA Characteristics. 通用结构 逻辑块类型 行排型 基于多路复用器 层次PLD型PLD块 对称阵列型 基于多路复用器 对称阵列型 查找表 编程技术 反熔丝 EPROM 反熔丝 SRAM 18 第二章FP(;A器件的总体结构及布线基准 口口 口口 口口 口口 Channel Segment (a)S block, Fs=3 (a)C block, Input logic pin:Fc=W=4 Output logic pin Fe=2 图2.3岛状FPGA结构模型 Figure 2.3 Island·style FPGA Architecture Model. 2.3 FPGA的结构模型 2.3.1研究目标 在这一章节中,将描述文章中所采用的FPGA结构模型。我们采用的模型是基于一 个标准的对称阵列(岛状)FPGA结构Ii.4,7,22,24-26】(即,Xinlinx XC4000系列)。图2.3 描述了全面的配置。一个岛状FPGA包含一个由三种不同的块类型组成的二维阵列:可 编程逻辑块结构(CLB)、连接块结构(C.块结构)及开关块结构(S.块结构)。每个CLB (图2.3中记为“L”)包含实现电路功能的组合时序逻辑。包含可编程开关(即:可编 程互连点或PIP)的连接块及开关块结构形成基本的布线资源。C.块结构将CLB引脚连 至邻近通道的轨线(线段)上。S.块结构被C.块结构所包围,它允许信号通过或作90 度翻转。连续的连接块即开关结构的行(列)称为水平(垂直)布线通道。每条布线通 19 江南大学博士学位论文 道由一系列金属线段构成而一系列在水平/垂直通道中相同行/列的会属线段代表一条轨 线。在FPGA的布线通道中具有不同长度的金属线段十分普遍。可编程I/O单元位于阵 列边界上。 接着,我们重点论述Xinlinx XC4000系列FPGA的布线公式及实验。这是市场上使 用最广的FPGA之一。在随后的章节,我们提供这一系列FPGA的每种块结构的详细说 明以及相应的描述其特征的结构参数。 薪YAO A1 BO B1 (a) 唠盼 Y 厶 &一 △R n U A0 Al Aj ab c f 0 O 0 l f OO 1 O O l O l O l l 0 1 OO l 1 O 1 0 1 l O l (c) 图2.4可编程逻辑块的典型结构 (a)Actel Act-I逻辑块:(b)Altera MAX5000系列逻辑块;(c)查找表逻辑块 Figure 2.4:Typical organizations ofeonfigurable logic block. (a)Actel Aet-I logic blockt(b)Altem MAX 5000 Series logic block;(c)Look-up table logic block 2.3.2逻辑块结构 在FPGA中,可配置逻辑块(CLB)是实现电路功能的地方。本文的主要工作是布 线方面,为了整篇论文的完整性我们也对其进行了说明。CLB的结构必须相当普遍以提 供种种不同的组合时序逻辑结构。FPGA中的CLB结构从简单的逻辑门到复杂的微处理 器核各不相同。显而易见,在CLB所需面积与可实现逻辑功能数之|'日J有一个交换。例 如,一个简单的2输入NAND门CLB可以实现5种不同的逻辑功能,f=a·“厂=石, ,=石,f=0。与之相比,由一个3输入查找表组成的CLB可以实现27=256个功能。 如果单个CLB可实现的功能数增加,则CLB所需面积扩张。但同时,设计所需 20 第二章FPGA器件的总体结构及布线基准 CLB数可以减少。因此关于可配置逻辑块结构的研究工作已集中于开发一种能实现最大 范围的任意逻辑功能同时占用尽可能小面积的灵活且通用的结构。现今存在的最流行的 CLB结构为:a)基于多路复用器,b)宽扇入与一非结构及c)查找表。 Actel公司的一类基于多路复用器CLB如图2.4(a)。具有单个控制信号的2输入多 路复用器通过将适当的信号用于数据输入可以实现多种逻辑功能。将许多多路复用器与 基本逻辑门连接起来,可以构筑大量的逻辑功能。这种类型的CLB的优点是它用相对 较少量的晶体管实现大量的功能。然而,由于基于多路复用器逻辑块需要大量的输入信 号,例如在图2r4(a)中为8个,因此它趋向于对逻辑块周围的布线资源有很高的要求。 多输入AND.OR类型CLB由传统PLD的PLA(可编程逻辑阵列)结构演化而来, 如图2.4(b)在底部的任何输入信号可以通过基于浮栅晶体管的可编程开关技术和任意其 它(非)信号实现线与(AND)阱】而这些乘积项在第二阶段通过逻辑运算符“OR”进 而构筑任意的逻辑函数。最后的异或门用于将前面的逻辑函数反向。多输入与门对于形 成具有较低级逻辑的逻辑函数是很有用的。但与层越多,逻辑单元的利用效率越差。而 且,大家都知道这种类型的CLB由于浮栅上拉器件中的静态功耗损失而产生不必要的 功耗。 查找表CLB[27.30]如图2.4(c)。查找表一般由存储单元,例如一系列SRAM单元构成。 一个2k×1 SRAM可通过将k输入信号连入SRAM的地址线而很容易表述具有k输入 信号的任意逻辑函数的真值表。一般来说,具有k个输入信号的查找表叫做K输入LUT。 k输入LUT是最常见的逻辑块,它能实现任何具有k输入的22k个逻辑函数。另外,由 于SRAM可以用标准CMOS技术构筑,它方便了FPGA的制造。基于LUT的CLB的 最大缺点是面积惩罚。表述单个函数需要2k个存储单元,资源利用率相当低。而且, 对于任意大于5的k值,k.LUT过大而不能用于实际FPGA结构。Xinlinx是使用基于 LuT的CLB的主要厂商,它使用4.LuT或5.LuT的CLB结构。 除了组合逻辑单元外,大多数CLB也包含某些形式的时序逻辑单元。图2.5显示了 XilinxXC4000系列CLB的简化结构图。其中,G.LUT和F.LUT可以用来生成任意的4 输入的组合函数或用作内置分布式凡~M:触发器可用来构成时序逻辑的基本元胞;多 路选择器用于配置CLB的不同的逻辑功能。 (1)函数发生器:两个16×1的存储器查找表(F.LUT和G.LUT)用于实现4输入的 函数发生器,它们每一个都能实现由任意4个独立的输入信号(FI~F4或GI~G4)组合 产生的任意布尔逻辑功能。并且,使用存储器查找表的传输延迟与其实现的函数功能无 关。一个3输入的函数发生器(H.LUT)可以实现任意3个输入所有布尔逻辑功能。其中 两个输入受到可编程多路选择器的控制。这两个输入信号可以是F.LUT或G.LuT的输 出,也可以是直接来自CLB的输入。而第三个输入信号直接来自于CLB的输入。因 此,CLB可以实现多达9个输入的特定功能,如实现奇偶校验。在CLB中的3个LUT 可以组合实现5输入的任意布尔逻辑功能。 总之,一个CLB可以实现四种功能:实现任意的4变量函数;实现一个输出的任 意5变量函数;实现6变量的部分函数;实现某些9变量的函数。在一个CLB中能实 现多种函数功能,这样在设计中,既可以减少所需的CLB块的个数,又可以缩短信号 的延迟时间,提高系统速度。 (2)触发器:每个CLB中包含两个触发器,它们用于存储函数发生器的输出。触发 器和函数发生器也可以独立使用。CLB的输入信号DIN可用作两个触发器的直接输入 信号;H1也可以通过H.LUT驱动任意一个触发器,但带有一个微量的附加延迟。两个 触发器共享一个时钟信号(CLK)、时钟使能信号(CE)和置位/复位信号(SR)。一开始,两 个触发器均由一个全局初始化信号(aSR)控制。 江南大学博士学位论文 (3)控制信号:由4个输入信号的多路选择器决定CLB的输入控制信号。这4个内 部信号是:CE-一时钟使能信号;SR.一异步置位/复位信号或是H函数发生器输入O; DrN-一直接输入信号或是H函数发生器输入2;Hl—.H函数发生器输入1。 Q Q 图2.5 Xilinx XC4000系列CLB的简化模璎 Figure 2.5:Simplified black diagram ofXilinx XC4000 series CLB 2.3.3输入,输出模块 输入/输出模块(I/OB)提供了器件引脚和内部逻辑阵列之问的连接,通常排列在芯 片的四周。其结构如图2.6所示,主要由输入触发器、输入缓冲器、输出触发/锁存器和 输出缓冲器组成。每个FOB控制一个引脚,可被配置为输入、输出或双向I/O功能。 当从)B控制的引脚被定义为输入时,通过该引脚的输入信号先送入输入缓冲器,缓 冲器的输出分为两路,一路直接送到MUX(多路复接器);另一路经延时几纳秒后(或 不延时)送到输入通路D触发器,再送到数据选择器。通过编程给数据选择器不同的控 制信息,可确定送至CLB阵列的11和12是来自输入缓冲器还是来自触发器。D触发 器可通过编程来确定是边沿触发还是电平触发,且由于配有独立的时钟,也可任选上升 沿或下降沿有效。 当FOB控制的引脚被定义为输出时,CLB阵列的输出信号OUT也可以有两条传输 途径:一条是直接经MUX送至输出缓冲器,另一条是先存入输入通路D触发器,再送 至输出缓存器。输出通路D触发器也有独立的时钟,且可任选触发边沿。输出缓冲器既 受CLB阵列送来的信号OE控制,使输出}1脚有高阻状态,还受转换速率(摆率)控制 电路的控制,使它可高速或低速运行。转换速率控制电路有抑制噪声的作用。 UOB输出端配有两只MOS管,它们的栅极均可编程,使MOS管导通或截止,分 别经上拉电阻和下拉电阻接通VCC、地线或者不接通,用以改善输出波形和负载能力。 第二章FP6A器件的总体结构及布线基准 图2.6XC4000的FOB基本结构 Figure 2.6 Xilinx XC 4000 series FPGAs’FOB architecuJre 2.3.4布线结构f3l_341 一个设计好的FPGA结构的布线能力一般可以由3个参数表示:W、只及Fs[141。 这些通用的结构参数能使我if]flE模拟各种商业FPGA。通道宽度矿是一个垂直或水平通 道中的轨线数。C一块结构柔性砟被定义为:每个逻辑引脚可连接的轨线数。s.块柔性只 表示每条进入S.块的线段能连至其它轨线的数目。实际XC4000系列结构与我们的布线 模型之间唯一的不同是我们假定每一条线都被完全分割而XC4000 FPGA在每个通道中 包含不同长度的金属连线。这一限制是为了更方便地与其它普通的布线法进行性能比 较。而不是详细布线地布尔公式中固有的。图2.6显示了Xilinx XC4000系列FPGA的 布线结构。 连接块(C.块)通过可编程开关将CLB逻辑引脚与水平或垂直布线通道连接起来 (如节2.1所述)。这些布线结构中每个输入逻辑引脚可以被连至通道中的任意轨线,而 在总共包含4条轨线的2条不同布线通道中,CLB输入引脚(例如图2.7中的XQ,YQ, x及Y)可以被连至每条通道中的2条线路。因为必需要有两个B参数值来模拟C一块 中的输入及输出引脚。图2.3(a)演示了c.块的模拟过程。输入逻辑引脚柔性值为 耳=4=W,而输出逻辑引脚值为B=2<W。 开关块结构(S.块结构)提供在水平和垂直线段之间的连接。在图2.3(b),进入s. 江南大学博}学位论文 块结构的每条线段仅可以连接至其它3条线段,每边一条。因此一个S-块结构的相应柔 性值为Fs=3。这一布线线路柔性是由一系列布线开关构筑的。例如,在图2.3中,在 s.块结构中的每条线路通过6个晶体管布线开关与其它线段连接并允许信号直接通过或 向左转或向右转。 图2.7 Xinlinx XC4000系列FPGA的布线结构 Figure 2.7 Xilinx XC 4000 series FPGAs’muting architecture. 2.4布线基准 论文后面实验中采用的布线基准来自美国北卡罗来纳州微电子中心的20个大规模 电路【35l。用VPACK封装入逻辑块并且每一个电路采用了VPR工具进行30种不同的布 局。由于此基准提供了相同的封装及布局,所以论文中的各个FPGA布线算法就可以在 同一平台上进行比较。 表4.2按照电路规模大小顺序给出这些基准电路,这些基准电路的逻辑块数由1135 到8527,网线数由1072到8445。表4.3按照字母顺序给出了的这些基准电路的详细信 息。电路中的“Blocks”(逻辑块数)为引脚(源输入和源输出)数与CLB数之和。“Array Size”(阵列规模)为电路布局的行列数。 第二章FPGA器件的总体结构及布线摹准 在此布线基准下的实验结果适用于所有的XC4000系列的FPGA 型些堕!竺!堡!!!坠 1 000.2000 2000-3000 3000-4000 4000.5000 5000.6000 6000.7000 7000.8000 >8000 表2.2按逻辑块规模大小顺序排列的基准电路 竺!!:::!墅坚!!!!竺!坐堡旦!唑!璧 型旦: 些!生!g旦!堡!堡!!塑 10 ALU4,APEX2,APEx4,DIFFEQ,DSIP,EXSP, MIsEx3,¥298,SEQ,TSENG 2 BIGKEYDES 3 ELLIPTIC.FRISC.SPLA 2 EXl010.PDC NfA 2 ¥38417.¥38584 NfA l CLMA 表2.3基准电路列表 T曲1e 2.3 FPGA Benchmarks List ALU4 APEX2 APEX4 BICKEY CLMA DES DIFFEQ DSIP ELLlPTIC EXl010 EX5P FRISC MISEX3 PDC ¥298 ¥38417 ¥38584 SEQ SPLA TSENG 1544 1919 1290 2133 8527 2092 1600 1796 3849 4618 1135 3692 1425 463l 194l 6541 6789 1826 3752 1221 1536 1916 1271 1936 8445 1847 156l 1599 3735 4608 1072 3576 141l 459l 1935 6435 6485 179l 3706 1099 1522 1878 1262 1707 8383 1591 1497 1370 3604 4598 1064 3556 1397 4575 193l 6406 6447 1750 3690 1047 14 38 9 229 62 256 64 229 13l 10 8 20 14 16 4 29 38 41 16 52 8 3 19 197 82 245 39 197 114 10 63 116 14 40 6 106 304 35 46 122 40×40 44X44 36×36 54X 54 92×92 63×63 39×39 54×54 61×61 68×68 33×33 60×60 38×38 68×68 44×44 8l×81 8l×81 42×42 61×6l 33×33 2.5本章小结 1)概括地评述了各种商业FPGA的结构特征及它们的主要系列。 2)介绍了这些FPGA的结构模型。说明所用模型的柔性足以模拟大多数商业 江南大学博士学位论文 FPGA。这个模型构成了论文其余部分的基础,这是因为布线公式的复杂度由 基础布线模型决定。 3)介绍了论文实验所采用的布线基准。 参考文献 『11 Lucent Technologies。Field.Programmable Gate Arrays Data Book.1996. f21 Xilinx Corporation,The Programmable Logic Data Book.1 996. 『31 Borriello Q Ebeling C,Hauck S,et a1.The triptych FPGA architecture.IEEE Trans.on VLSI Systems,v01.3。no.4.December】995.491.501. 『41 Btown S,Francis&ROse J.Field.Programmable Gate Arrays.KIuwer Academic Publishers.1992. 『51 ElectroniCS Weekly:ABI,INFORM Trade&Industry,Feb 25,2004,12-13. 『61 Gomez·Prado D,Ciesielski M.A Tutorial on FPGA Routing.Department of Electrical and Computer Engineering,University of Massachusetts,Amherst,USA.2004. 【7】Atmel Corporation,Configurable Logic Design and Alication Book,1994. 【8】Aggarwal A,Lewis D.Routing Architectures for Hierarchical Field—Programmable Gate Arrays.In Proceedings IEEE Custom Intgerated Circuits Conference.1994.6:475.478. [9】Cong J.Technology Making for FPGAs埘lll Embedded Memory Blocks.Proe. FPGA.98,ACM 『101 Xilinx Inc.,The Programmable Logic Data Book,1994. 『1 11 Xilinx,XC4000E and XC4000X Series Field Programmable Gate Arrays,Product Specification。November 1 997.availane from www.xilinx.com. 2】 Xilinx Inc.Vinex II Data Book 2004. 3】 Xilinx.Virtex-4 user guide.http://direct.xilinx.corn/bvdocs/userguides/u9070.pdf,2005. 4】 Xilinx,The Programmable Gate Array Data Book.San Jo∞,CA:Xilinx,Inc.,1 993. 5】 http://www.xilinx.com 6】 Actel Inc.Axcelerator family FPGA.2004. 7】 Actel Corporation.MX FPGA Data Sheet.version 5.0。February 200l 8】 Rose J.Hill D.Architectural and Physical Design Challenges for One—Million Gate FPGAs and Beyond.In 5th Intemational Workshop on Field.Programmable Gate Arrays. Monterey.Ca,1997.2:129.1 32. 【19】 Altera Corporation,Altera Data Book.1 996. 【20】 AItem Corporation,Stratix II Device Handbook Volume 1.Jul 2004. 【21】 Aggarwland A,Lewis D.Routing Architectures for Hierarchical Field Programmable Gate Arrays. In Proceedings IEEE Custom Intgerated CifclIits Conference. 1994.5:475-478. 『221 Brown S,Francis R J,J Rose.Vranesic.Field.Programmable Gate Arrays.KIuwer Academic Pubtishers.Boston,Ma’1992. f23】Lai Y T,Wang P T.Hierarchical Interconnection Structures for Field Programmable Gate Arrays.IEEE Transactions on VLSI.June 1997,5(2):186.196. 【24】Betz V,ROse J,Marquardt A.Architecture and CAD for deep-submieron FPGAs, KIUWer Academic Publishers.ISBN 0.7923.8460.1.1999. [25】Lucent Technologies,Field—Programmable Gate Arrays Data Book Oet.1996. 第二章FPGA器件的总体结构及布线基准 【26】Wilton S.Architectures and algorithms for field-programmable gate arrays谢th embedded memories.Ph.D.dissertation,Univ.Toronto.1997. 『271 Kumthekar B.In.Place Power Optimization for LUT.Based FPGAs.Proceedings Design Automation Conference,ACMnEEE,1998,5(2):15.18. 【28】Wang Zlli—Hong.Power Minimization in LUT—Based FPGA Technology Making. Proceedings ofthe ASP.DAC,2001,3:635-640. 【29】Brown S,Francis艮Rose J.Field Programmable Gate Arrays.Boston,MA:gluwer, 1992. f301 Xilinx Corporation。The Programmable Logic Data Book.1998. 【31】Betz V,Rose J.FPGA Routing Architecture:Segmentation and Bufiering to Optimize Speed and Density.ACM/SIGDA International Symposium on Field Programmable Gate Arrays,Monterey,CA,1999,11:59.68. 1321 Xilinx Corporation,111e Xilinx Foundation Series 1.4,1 998。available from www.xilinx.tom. [331 Wilton S.Architectures and Algorithms for Field.Programmable Gate Arrays嘶th Embedded Memories.Ph.D.Dissertation,University of Toronto.1997.(Available for download from http://www.ee.ubc.ca/-stevew/publications.html). [341 Tseng B,Rose J,Brown S.Using Architectural and CAD Interactions to Improve FPGA Roming Architectures. First International ACM/SIGDA Workshop on Field.Programmable Gate Arrays.1992.2:3—8. 【35】Yang S.Logic Synthesis and Optimization Benchmarks,Version 3.0,Technique Report, MicroelectroniCS Center ofNorth Carolina,1991. 江南大学博上学位论文 第三章几何查找布线算法的研究 3.1前言 在采用布局工具对FPGA布局[i-11】之后,就确定了电路模块的绝对位置和模块引脚 的位置,接下来就是要实现各模块问的连接,即进入布线阶段,这是本论文研究的重点。 所谓的布线问题就是经过布局将模块相对位置确定之后,经由布线器来做这些模块 的连线工作。布线问题的前提是必须知道终端节点的位置,以及电路的线网列表。线网列 表是由电路中每个线网所构成的集合,而一个线网的组成可能包含一些终端节点和一个 来源端点,一个线网列表可以提供各个端点之间的连接关系并且可以知道布局时每一层 可以供布线的面积。布线一般来说可以分成两个阶段。 第一个阶段我们称为全局布线 [12-22】或是宽松布线,主要是用来决定要经过那个通道,也就是说它仅提供一个方向做为 指引,而不是真J下在布局后的位置。例如某人要从甲地到乙地有很多方向,但只有一个 方向的路径相对比其它方向来的短,那么我们就会朝这个方向去走,但这个方向的路不 只一条。究竟要选哪一条呢?前面的这个疑问就要靠第二个阶段的布线器来帮我们解决 我们称这个阶段叫做详细布线f23-30]或局部布线,这个步骤相当于由甲地开车到乙地必须 走什么路比较方便且比较省油。从工程上来讲,这罩必须决定的是模块连接在信道中的 精确位置,比如要经过在哪个布线轨道以及必须走哪个金属层。 FPGA主要由三大部分组成11 J:可编程逻辑单元CLB(Configurable Logic Block)、布 线资源IR(Interconneetion Resource)和可编程I/OB(I/O Block)。由于布线资源占用了 FPGA约70%~80%的芯片面积和约50%.-60%的信号时延[31,321,所以布线资源是FPGA 中非常重要的一部分。而一个好的布线算法能够在减少布线资源的占用的同时快速完成 信号配置从而缩短信号时延,因此在工艺条件一定的情况下,布线算法对FPGA的设计 起着至关重要的作用。 在本章节的研究中,采用了几种几何查找布线算法对文献133]提供的FPGA布线基 准进行布线。比较了传统的Lee布线算法、常用的商用布线算法PathFinder及其改进型 算法VPR430和一种最新的御线算法Frontier之问的优劣,为建立一种新型混合算法打 下了基础。 3.2基本布线算法 现今出现的几何查找布线方法,如CGE[311、SEGA 135州、TRACERf37】、GBPp引、 SROUTE 139】、PathFinder 140,4“、VPR 142J、Frontied431等都是基于一种迷宫布线算法【*521, 即在一个平面矩形网格上的顶点之问寻找一条路径。用迷宫布线法布通单独一条线网的 伪码,如图3.1所示。每条线网路线始于线网的源端逻辑块。并且通过可利用的布线资 源执行搜索以找出从源端到终端的最低成本路径。用于扩张现有局部路线的候选线段或 逻辑块引脚被保存在基于预先指定成本函数的一个扩充列表(一个典型的例子是优先队 列)中。由图3.2可知,搜索的布线资源的平面范围特别地被限定在一个边界框中,这 一边界框包含的矩形区域中的所有布线资源被线网的源端、所有终端及-d,块边界区域 所限定。 一般来说,迷宫布线法可定义为图论中的一个问题【4518,49】,一个FPGA中的布线资 源及其连线可以用一个图G=(矿,E)表示,这里矿表示布线节点或轨线而E表示路线或 第三章几何查找布线算法的研究 Put track segments attached to SOUrCe onto expansion list. segment Remove lowest cost track from expansion list. WhiIe still more destinations to reach for this net. WhiIe a net input has not been reached. Put neighbors ofcurrent track under eValuation onto expansion list Remove Iowest cost track segment from expansion list. Endwhile Endwhile Empty the expansion list. 图3.1一条连线的基本迷宫布线程序 Figure 3.1 Basic Maze Routing Sequence foraNet 图3.2扇出为2的线网边框图 Figure 3.2:Bounding Box for Net with Fanout of2 开关之间的连接线。而且,每个节点有一个相应的成本C,,它表示目标器件中的线网之 间该结点当前使用率或占用率。为了能够成功布线,每个节点应该最多被一条线网占用。 在早期的研究成果[53-55J中,可以看到算法A。可以被用于这一个布线问题,这一算法是 通过在从一条二引脚线网源端到终端的局部路线中的每个节点n,的一个评估函数厂实 现的,可表示为: Z=g.+d。 (3.1) 这里要是从源端到n,的路径成本,而一是由啊到终端路径的估计成本。 江南大学博上学位论文 在大多数迷宫布线算法153·划中,值g,可表示成前面的路径的总成本Z一.加上下一候 选节点的成本,即: g,=.,:一1+c, (3.2) 特别地,忽略由节点到终端的成本dj,使得Z=g,。由于迷宫布线算法是通过延着 所能考虑到的最低成本路径(,)扩张来进行的,那么仅考虑gf的净效应是~种广度优先 搜索,由此得到~条最低成本、最短路径的路线。 若反过来,忽略先前的路径成本(方程3.2中的Z一。)并且路径成本的估算(方程 3.1中的d,)被设定为从节点到终端的曼哈顿距离145],最低成本的迷宫路线扩张将导致 与终端最近的最低成本节点的扩张。遵循这一规则,可以实现一种不是最理想但运算速 度快得多的深度优先搜索法。 用一个在0和l之间的缩放比例因子口(o≤口≤】)对晶及d,的组合进行加权可以生 成在深度优先和广度优先之问的搜索方法‘55】: Z=(1一口)×(,一l+c.)+盯Xdl (3.3) 节点成本C,的作用是避免使用被先I;{『路线占用了的节点。 由于在迷宫布线过程中为了躲避障碍总需要将至少某一拥挤考虑在内,因此口不能 精确设定为1,在本章的其余部分,深度优先布线是指用偏向于距离而不是拥挤(口>0.5) 的最小代价函数布线。由后面的计算结果可知,口=O.62可以在最少的布线运算时间内 得到最优质的布线结果。 3.3 PathFinder:一种基于协商的性能驱动FPGA布线方法 将图3.1中的基本迷宫布线算法用于方程3.3中的成本函数,在对所有线网进行一 次布线迭代之后,将频繁出现节点被多于一条线网占用的情况。为了消除这一拥挤状况, 至少一些线网必须被拆线重布线以找到较不拥挤的路径。一般来说,迷宫布线对线网布 线顺序极为敏感。迷宫布线的最初的意图主要是通过在每一次迭代中对小部分子集的线 网进行拆线重布线来消除拥挤。但是这种方法在用于FPGA时的成功率十分有限。采用 这种渐进式算法的基本问题是:布线的成功不仅取决于选择那些线网进行布线,而且依 赖于重新布线的顺序。 为了克服顺序依赖性,Pathfinder算法【柏,42,56-59J由于其能成功地完成布线并且操作简 便,已经成为用于岛状FPGA的~种适合的迷宫布线方法。Pathfinder算法是布线工具 VPR399中采用的一种广度优先搜索的迭代迷宫布线方法。它使用了一种尝试平衡竞争 目标:消除拥挤与虽小化关键路线延迟的迭代算法。与典型的二步布线法【56J不同,这种 算法同时进行全局布线及详细布线。在这一构架中,允许信号初步分享布线资源。然而, 随后他们必须与其他信号协商以及决定那个信号最需要分享资源。在每次迭代中都要进 行一次时序分析以维持对那些未检查但可能是十分关键的路线持续施加影响。在协商中 第三章几何查找布线算法的研究 通过使得越是关键的电路越具有更优先的次序可以将延迟最小化。 价国两 斯 。纭 A) 含≮. !鲥扒) D1) (D2 1 f D3 酞詹!掀◇彭越拿 Dl】 【D2) 【D3 酞毋献◇越饬 Dl l (D2】 f D3 (c) 图3,3 PathFinder迭代例子 (a)PathFinder算法的首次迭代:失败;(b)PathFinder算法的二次迭代:失败;(c)PathFinder算法的最 后一次迭代:成功 Figure 3.3 PathFinder iteration example. (a)The first iteration ofPathFinder:Unsuccessful;(b)The second iteration ofPathFinder:Unsuccessfuh (c)The third and final iteration ofPathFinder:Successful PathFinder起源于由Nairl58l开发的定制IC芯片的全局布线的一种迭代法。这一方法 与大多数拆线重布线法在几个方面有所不同,布线是采用多次布线迭代来完成。在每次 迭代过程中,每条线网被拆线并按照预定的顺序布线。在布线网格的每一布线节点的成 江南大学博士学位论文 本c,被不断更新以反映每条线网布线后以及每条线网被布通的一次完整迭代之后的拥 挤状况。通过对每一个节点指定一个单调非减成本因子,这一新增成本的更新允许线网 路线从器件的拥挤区域迁移致较离散分布的区域。采用这种方法,通过拥挤区域的线网 可以转而为当前J下处于拥挤区域的其他线网腾出空间。PathFinder算法与Nair的方案在 成本函数与延迟处理的结构上有所不同。 整体算法可以用图3.3中所述的简单例子来说明。在这个例子中,我们要连接3个 信号(s.,D.)对。边线的成本在括号中明确说明,而粗体线表示分配给每个信号的路线。 PathFinder算法的首次迭代中,在对每个信号都运用最短路径算法之后,由于顶点B(图 3.3(a))周围的资源竞争,布线结果是不合理的。这一竞争资源的结果是B周围相应的 布线资源的成本被增加(图3.3(b))并且相同的迭代被重复。仅当全部3个信号被最终 布线而不共享任何布线资源这一过程才会结束(图3.3(c))。 【1】While shared i'eSoLlrces exist(global router) 【2】 Loop over all signals i(signal router) 【3】 Rip up muting tree月兀 【4】 RT,=西 【5】 Lo叩until all sinks白have been found 【6】 Initialize priority queue PQ to RT,at cost 0 【7】Loop until new t,j is found 【8】 Remove lowest cost node m from JpQ 【9】Loop over fanouts H ofnode所 【10】 Add HtoP9 at cost“+‰ 【11】 End 【12】 End 【13】Loop over nodes t/in path tv to si(backtrace) 【14】 Update“ 【15】 AddntoRT, 【16】 End 【17】 End 【18】 End 【19】End 图3.4 PathFinder算法的伪码 Figure 3.4 PathFinder pseudo code 图3.4给出了PathFinder算法的伪码1401。PathFinder由两部分组成:一个信号布线 法,它用最短路径算法一次布通一个信号;一个全局布线法,它调用信号布线法将所有 信号布通,同时调整资源成本以取得一个完整的布线。给定每个布线资源的拥挤成本及 延迟,信号布线法采用一种宽度优先搜索法以找出最短路径。根据资源上的信号要求, 全局布线法动态地调整每条布线资源的拥挤惩罚。在全局布线法的每次迭代过程中,不 存在共享布线资源的成本以及个别的布线资源可能被超过一个信号使用。然而在随后的 迭代,惩罚逐渐增大,这样信号实际是在协商使用资源。信号可以使用处于高需求的共 第三章几何查找布线算法的研究 享资源,只有当所有可替换路线使用处于更高需求的资源。其它信号将逐步扩展并使用 处于低需求的资源。全局布线法采用信号布线法将信号重新布线直到没有更多的资源可 被共享。除了最小拥挤外,信号布线法确保了所有信号路径的延迟处在关键路径延迟范 围之内。计算电路中每条连接线的松弛率,即采用该连线的最长路径的延迟与电路中最 长(即,最关键)的路径的延迟之比值。 松弛率的倒数显示了电路减速前路径延迟增大的因素。此信号布线法的关键思想 是:松弛率接近1的连接线在协商资源中权值较高,并将被源端到终端直接布线(即, 使用最小延迟路线)。具有较小松弛率的连接线将被分配信号的权值较低并更注重在布 线过程中避免拥挤。 (a) 图3.5布线选择 (a)广度优先算法;(b)深度优先算法 Figure 3.5:Routing Options (a)Breadth-fast Router;O)Depth·first Router 3.4 VPR430:一种快速的时延驱动布线算法 VPR430160-651是VPR399142,59】的一个改进版本,也是由多伦多大学的研究人员研发 的。VPR广度优先布线法(VPR399)仅仅关注于将一设计电路成功布线,而时延驱动 布线法(VPR430)是一种深度优先布线法,它既关注于取得成功布线也关心取得较好 的电路速度。广度优先布线法能够用比时延驱动布线法稍微少一点的轨线布线(时延驱 动布线法采用的默认参数为5%;而当时延驱动布线法更关注于可布通性而不是布线面 积时,该默认值可降为2%[601)。由时延驱动布线法生成的电路要快得多,并且它使用更 少的CPU时『日J进行布线。 一般有两种增强方法可以加快基本广度优先迷宫布线搜索的速度。第一种是采用 A’深度优先搜索,它引导布线法朝向指定的目标搜索。A’算法与PathFinder算法相似, 但成本函数的选择更注重于搜索目标,后面介绍的Frontier算法采用的就是这种方法。 在理论上,深度优先搜索法也被称为一种定向搜索法,它始于线网的源端并不断地选择 较为邻近的线段一直到达目标终端。第二种方法是通过将线段放置在目标端邻近范围的 :控制网延时及可布线性之间平衡的一个松弛函数,如果值_exp<float> 江南丈学博士学位论文 扩张列表中,从而减少用于较高扇出线网的布线扩张列表的更新次数142J,VPR430采用 的是这种方法。 与VPR399相比, VPR430时延驱动布线法中采用了三个新的参数【”J,如下所示: 一a.star fac<float>:设定了由时延驱动布线法采用的定向搜索的搜寻程度。值取在1与2 之间较合理,取的值较高则可牺牲某些性能以换取减少CPU时间。本论文中VPR430 采用的默认值分别为1.2(纯VPR430算法)及1.17(混合算法)。 .-max criticality<float>:对于一条线网,设定了(相对来自可布通性的布线成本)来自 时延的布线成本的最大比例值。值“0”意味着忽略延时;值“1”意味着在关键路径忽 略拥挤。本文中VPR430采用的默认值分别为O.99(纯VPR430算法)及O.98(混合算 法)。 .-criticality 为O,所有线网以相同的方式处理,不考虑其松弛(即每条连线都考虑延时)。如果这一 值很大,则仅在关键路径上的连线布线时考虑延时。取中间的其它值将得到两者『白J适中 的平衡。本文中VPR430采用的默认值分别为1(纯VPR430算法)及0.99(混合算法)。 3.5 Frontier:用于FPGA的协商A’布线算法 3.5.1 Frontier算法的原理 Frontiert43,66,671是Tessier博士在Massachuseets技术学院攻读博士学位期间开发的一 种算法。它与时延驱动布线法相类似,但它采用了一个区域协商步骤。它也是一种基于 深度优先搜索的改进的迷宫布线算法,相比传统的广度优先的迷宫布线法,它大大减少 了FPGA布线所需的搜索空间,减少了运行时问。大多数迷宫布线法采用对布线图的一 种广度优先搜索算法以生成连接线,虽然这保证了最佳连接(对二引脚线网),但这也 意味着这一布线法花费许多时『白J在错误的方向探索路径。 在2.3节中,可以看到岛状FPGA的开关盒结构将线段分成了不相交的布线区域, 这些区域是可以连接起来形成一条布线路径的线段组。由于有限的内部线段的连接性, 在一条布线通道中的每条线段都属于不同的区域,这表明FPGA中的区域数与其通道宽 度矿相等。从广度优先布线法转换成深度优先布线法需要将布线结构的不相交性考虑在 内。考虑从源端到终端的一条广度优先路线,假定所有的布线节点有相同的成本c,并且 横跨一个逻辑块。图3.51a)表明节点扩张发生在距离终端曼哈顿距离的所有轨线区域中。 因此,最终布线在沿着源端到终端路径的区域内具有最低成本的的轨线完成。 另一方面,在采用深度优化方法的情况下,在具有相同曼哈顿距离的其它节点扩张 之前,距离终端最近的节点首先扩张。如图3.5(b),这一扩张方法及布线开关的不相交 性的净效应是生成一条限制在从线网输出端到输入端的同一轨线区域内的定向路线。如 果沿着最初区域布线失败,其后的深度优先布线将在不同的区域尝试直到成功布线。 这种深度优先布线的关键在于确定了尝试布线的区域顺序。由于区域在布线过程中 是不能改变的,所以有必要在有很可能成功完成布线的区域内首先尝试布线,这样就不 需要在其余的区域中进行节点扩张了。为了实现这一区域选择,我们引入了区域协商的 概念,可概述如下: 区域协商:对于在线网终端逻辑块周围的一条基于布线拥挤的线网,评价FPGA器件中 布线区域的布线能力行为。 为了实现区域协商,在对每条线网布线之前,按照与线网输入引脚相邻的轨线占有 率对区域进行次序排列。如果在一区域中输入端周围的当前轨线占有率低,这种局部搜 第三章几何查找布线算法的研究 索的次序排列区域在深度优先布线中更可能取得成功布线,但如果占有率高则成功的可 能性较低。 如图3.6是一个有关区域协商的例子。这里,一条线网起始于阵列的底部左端的源 端逻辑块并且终端逻辑块位于顶部右端。在这个例子中,深度优先布线最初尝试采用区 域0中的轨线(虚线段)当路线接近终端时,它由已被占用的终端周围的高成本线段(表 示为粗划线)所阻挡。由于这一拥挤的存在,我们采用了一条新的深度优先路线,它采 用区域1中的轨线,尝试寻找一条低成本,无拥挤路线。如果一开始就选择区域l,则 区域0的搜索时问就可以避免。这一例子阐明了对于一条扇出为1的线网进行布线所消 耗的搜索时间,对于更高扇出的线网,布线效率则更低。 0l 2 图3.6一个区域协商布线的例子 Figure 3.6:Dommn Negotiation Example 【l】Loop OVCI"track domains 【2】 InitiMize domain cost o to O 【3】 Loop over each destination input block 【4】Loop over tracks删acem to input pins 【5】 Add tracks occupancy to cost o 【6】 End 【7】 If all tracks adjacent to inputs have occupancy>l 【8】 AddpenaltyPtoCd 【9】 End 【10】End 【11】Assign each domain a rank rd based on Cost ca,r咖ACd) 图3.7区域协商算法 Figure 3.7 Algorithm:Domain Negotiation 江南大学博t=学位论文 区域协商算澍明如图3.7。由于这些逻辑块具有逻辑上等效的多输入引脚,因此在 一个给定区域,对于一个逻辑块输入引脚相邻的单个区域轨线的占有不会阻止布线的完 成,但会使其完成的困难增加。布线资源的竞争可以用给每一区域指定的一个成本值白 来反映。在访问每条线网输入逻辑块时,区域的q值随着与逻辑块输入引脚相邻的区域 轨线数的占有率而递增。如果在一给定区域内所有逻辑块输入引脚的相邻轨线都被占 用,那么在此区域内的布线不能完成,除非能生成占有率大于1的轨线,然而这在物理 实现上是不可行的。为了反映这一不理想的问题,对于每个输入逻辑块采用一个惩罚因 子增加区域勺的值,其中的输入逻辑块具有与被至少一条线网占用的输入引脚相邻接的 全部区域节点。惩罚值P>pins。(这里,pins。,是具有最高扇出的线网所占用的引脚 数)被用于将布线完成所需的节点扩充数最小化以及生成最小的轨线宽度路线。 作为区域协商之后的深度优先布线的第一步,所有的区域按照其成本值C。排列。具 有最小臼值的布线区域被设定为最低级的白值,而具有最大乃值的区域被设定了最高 级的白值。其它中间区域用表示其相对应c。值的等级值表示。 【1】Orderthe sinks usingPrim’sAlgodthm. 【2】Perform Domain Negotiation. 【3】Target=sink closest to source. 【4】Put tmck segments attached to source onto expansion list with cost given by(3.4). segment 【5】Remove lowest cost track from expansion list. 【6】While the net input has not been reached. 【7】Put neighbors ofthis track onto expansion list with cost昏ven by(3.3). 【8】 Remove lowest cost track segment from expansion list. 【9】Endwhile 【10]Empty the expansion list. ¨1]Whlie stillmore sinksto routefortllisnet. 【12】Target=next sinkdeterminedfrom Prim。sAlgorithm. 【13】Put whole net created to this poim onto expansion list with COM 2Ⅱx4. segments 【14]Put track attached to souree onto expansion list with cost given by(3.4). 【15】 segment Remove lowest cost track from expansion list. 【16】 While the net input has not been reached. 【17】Put nei曲bors ofthis track onto expansion list with cost given by(3.3). 【18】 segment Remove lowest cost track from expansion list. 【19】 Eudwhile 【20】 Empty the expansion list. 【21】Endwhile 图3.8 Frontier算法的伪码 Figure 3.8 Frontier pseudo code 第三章几何查找布线算法的研究 3.5.2 Frontier算法的实现 Frontier布线法与广度优先算法最初在其多终端线网的赋值中就有很大不同。在深 度优先算法中,必须确定一个特定的目标输入端以计算方程3.3中的间距Z。结果,必 须采用一个单独的布线步骤使每个输入端与线网相连。为将总线长最小化,Frontier布 线法按照采用Prim的最短路径算法14 5J所搜索的距离将目标输入端排序。最接近线网输 出端的目标输入端被选定为第一个目标输入端。其后的目标输入端都是选择距离线网输 出端有最短路径的输入端。一般地,当存在较少布线拥挤时,高扇出线网较容易布线。 按照文献【55】中所提出的方法,线网按递减扇出数的顺序布线。 Frontier算法的伪码如图3.8。采用一个扩张列表来保存扩张的可能轨线及其相应成 本。对每条线网输入,扩张表初始化为包含输出引脚的多扇出线网的现存路线。如果布 线在由前面的线网输入端所采用的区域内不能完成,那么为了能变换区域必须生成一条 能返回多引脚线网的输出引脚的新路径。 专用于区域协商的伟线步骤在图3.8中用斜体字表示。区域被搜索的顺序由区域的 等级0决定。正如区域协商阶段所决定的一样,低拥挤的区域将有较低的等级屹,因此 首先在低拥挤区域内开始布线。通过修改方程3.3中的成本函数以包含屹,使与线网资 源相关的轨线可以将这一等级因数考虑在内。 ,=(1一盯)×(Z—l+c.)+口×dl+ra (3.4) 采用方程3_3的成本函数可以将所有其余的轨线归入扩充列表。 除了用斜体表示的区域协商步骤之外,图3.8所表示的布线算法与Toronto大学开 发的即文献【55】中所讨论的算法相似,文献[551中的算法是针对一种改进的FPGA布线 结构,但这种布线结构不包括在商业结构(例如Xilinx XC4000系列)中普通存在的不 相交开关盒。Fontier布线法正在被改进以将线网延迟信息考虑在内。 3.6实验结果及分析 为了评估我们在本章所介绍的四种几何查找布线算法:Lee、PathFinder、VPR430、 Frontier在布线时间上的有效性,我们采用来自美国北卡罗来纳州微电子中心的20个大 规模电路作为布线基准(已经在第二章中给出),为了能使以上各个FPGA布线算法就 可以在同一平台上进行比较,在进行布线之前我们统一采用VPR399对每个电路生成30 个布局,四种算法直接采用这些布局进行布线。所有的实验在频率为1GHz的Pentium IlI 上运行,采用了LINUX系统及512M内存。 由于实际运算过程中发现Lee耗时过多,因此仅用Lee算法对五个较小规模的电路 进行布线,表3.1显示了Lee及PathFinder算法的布线时间(记为“mean”)及标准误 差(记为“Std”),从表中的数据可见,Lee算法的总体布线时间是PathFinder的近47 倍,标准误差是其48倍。图3.9、图3.10分别显示了在不同电路基准下的综合布线时间 及其标准误差分布。 图3.11、图3.12更形象的对两种算法的总体布线时问及其标准误 差作出比较,表明Lee算法的布线时间及稳定性已经与流行的商业布线算法PathFinder 有很大差距。 由以上分析可知Lee算法无论在整体布线时间上还是在布线稳定性上与当前算法相 差太远,所以这里重点在PathFinder、VPR430、Frontier这三种算法之间进行比较。 37 江南大学博t学位论文 由表3.2可见,PathFinder、VPR430、Frontier三种算法的综合布线时间分别为5319.36 秒、16340.85秒、40585.17秒,三种算法的标准误差上分别为1037.56秒、3273.73秒、 5547.89秒。因此,相比现在较为流行的PathFinder算法,在布线时间及稳定性上VPR430 分别提高了59.7%、41.O%,Frontier分别提高了86.9%、81.3%。 图3.13给出了针对20个基准电路中一个典型电路SEQ,三种算法在置信度为99% 的条件下的综合布线时J'日J的置信区『白J分布情况。图中横条的宽度直接反应了布线时间的 稳定性,代表Frontier的横条最窄因此最稳定,而代表PathFinder的横条最宽因此布线 稳定性最差。 更直观地,由图3.14可见三种算法在布线时间上的优劣是:Frontier优于VPR430, VPR430优于PathFinder。从图3.15可见在稳定性上是PathFinder最差,Frontier最佳。 图3.16、图3.17从整体上对三种算法进行的比较更充分显示了这一点。 虽然,相比基本迷宫布线算法Lee,三种布线算法PathFinder、VPR430、Fronticr 算法尤其是VPR430、Frontier两种算法在布线时间及稳定性上都有很大改善,但由于其 属于几何查找布线算法因此对布线顺序有很强的依赖性,而另一方面,几何查找布线算 法当一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难。例如 如果对于一个给定电路布局存在一个布通方案,则Frontier在经历足够的迭代次数后, 最终将向其收敛。但是如果问题是不可布通的,算法将不会收敛并在一个合适的时间限 制下停止执行,例如:当时间界限是10000秒,在电路不可布通的情况下,VPR430一 直会持续迭代到10000秒为止,而不会在此时间段中自行判断是否可布通。因此Frontier 在布线时间及稳定性上仍然有提高的空『自J,这就是论文后面第五章提出混合布线算法的 原因。 表3.1 PathFinder与Lee的综合布线时间比较 Table 3.1 Overall Computing Time Comparisons for PathFinder and Lee Total 1 192.44 147.06 55968.26 7067.14 图3.9 PathFinder与Lee在不同电路逻辑块规模F的综合布线时间 Figure 3.9 Overall Computing Time for PathFinder and Lee vs.Circuit Block Size 第三章几何查找布线算法的研究 图3.10 PathFinder与Lee在不同电路逻辑块规模F的综合计算时间的标准误差 Figure 3.10 StandardDeviationofOverallComputingTimeforPathFinderand Lee vs.CircuitBlockSize 图3.1l PathFinder与Lee的总体布线时间比较 Figure 3.11 Total Computing Times comparison for PathFinder and Lee 图3.12 PathFinder与Lee的综合布线时问的总体标准误差比较 Figure 3.12 Total Standard Deviation eomparisom for PathFinder and Lee 垩堕查兰堡主兰竺堡塞 表3.2 PathFinder、VPR430、Frontier的综合布线时间比较 型!!:::旦兰翌!!!竺£!!!g三!竺!兰!竺£塑:!!!生:!!尘!!!!!!∑!墨!!!竺!!:竺!!!!: Circuit 是]iozeck—赢FroFnti—er(s]eco丽nd—)—iV品PR-43—0(sleco丽nd)——iPat;h五F-inder(secsotdnd)一 !!趔 i!!!:i! !!i!:!! !箜竺:!: :!!!::! 兰!!!i:!: :!!::!! 图3.1 3 PathFinder、VPR430、Frontier的综合布线时间比较(SEQ,ci---9们/o) Figure 3.130verallComputingTimeComparisonsforPathFinder,VPR430 and Frontier(SEQ,C1299%) 40 第三章几何查找布线算法的研究 图3.14 PathFinder、VPR430、Frontier在不同电路块规模下的综合布线时间 Figure 3.140verallComputingTimeforPathFinder,VPR430 and Frontier vs.CircuitBlock Size 图3.15PathFinder、VPR430、Frontier在不同电路块规模F的综合计算时间的标准误差 Figure 3.15 StandardDeviation ofOverallComputingTimeforPathFinder,VPR430andFrontierVS. Circuit Block Size 图3.16 PathFinder、VPR430、Frontier的总体布线时间比较 Figure 3.16 Total Computing Times comparison for PathFinder,VPR430 and Frontier 4l 江南大学博士学位论文 图3.17 PathFinder、VPR430、Frontier的综合布线时间的总体标准误差比较 Figure 3.17 Total Standard Deviation comparisons for PathFinder,VPR430 and Fmnfi日 3.7本章小结 1)研究了用于FPGA布线的四种几何查找布线算法:一种基本迷宫布线算法Lee, 一种基于协商的性能驱动的布线算法PathFinder。一种快速的时延驱动的布线 算法VPR430,一种协商A’布线算法Frontier。 2)用各种算法对采用了相同布局后的同一FPGA基准电路进行布线,由于基本迷 宫布线算法Lee的布线时『白J过长(Lee算法的总体布线时间及标准误差分别是 PathFinder 47倍及48倍)已经不胜任现今大型的FPGA布线。而在对其余三种 电路的详细对比中可见相比现在较为流行的PathFinder算法,在布线时『日J及稳 定性上VPR430分别提高了59.7%、41.O%,Frontier分别提高了86.9%、81.3%, 因此无论从整体布线时间上还是从布线稳定性上,三种算法从优到次的排序都 是:Frontier、VPR430、PathFinder。 参考文献 【1】Alexander M,Cohoon J,Ganley J,et a1.Performance—Oriented Placement and Routing for Field—Programmable Gate Arrays. European Design Automation Conf., 1995.12:80·85. 【2】Ebeling C,McMurchie L,Hauck S气el a1.Placement and Routing Tools for the Triptych FPGA.IEEE Trans.on VLSI.1995,12:473-482. 『31 V Belz.Architectures and Algorithms for Field-Programmable Gate Arrays.Ph.D. Dissertation,University ofToronto.1998. 【4】Gudise V,Venayagamoorthy G.FPGA Placement and Routing Using Particle Swarm Optimization.in Proceedings of the IEEE Computer Society Annual Symposium On VLSI Emerging Trends in VLSI Systems Design,2004.12:307.308. 【5】Donath W E.Placement and Average Interconnect Lengths of Computer Logic.IEEE Transactions on Circujts and Systems,CAS.。Apr.1979,26(4):272.277. 【61 Frankle J.Iterative and Adaptive Slack Allocation for Performance-driven Layout and FPGA Routing.In Proceedings,ACM/IEEE 29st Design Automation Conference, 1992.3:536—542. 【71 Wilton S.Architectures and algorithms for field·programmable gate arrays with 42 第三章几何查找布线算法的研究 embedded memories.Ph.D.dissertation,Univ.Toronto.1997. f81 N醒S,Rutenbar R.Performance.Drivgll Simulataneons Place and Route for Island.Style FPGAs.In ICCAD.1995.6:142-151. 『91 Sankar Y.Fast Placement for FPGAs.In Proceedings,University of Toronto FPGA Research Review.Peterborough,Ontario。1997,6:221.232. [101 Sankar Y.Ultra-Fast Placement for FPGAs.Master's thesis,University of Toronto, Department ofElectrical and Computer Engineering,1998.in preparation. f1 11 Sherwani N.Algorithms for Physical Design Automation.K1uwar Academic PublIshers, Boston,Ma.1 992. [121 Kuh E S,Marek.Sadowska M.Global routing.in Layout Design and Verification,T. Ohtsuld.Ed.New York:EIsevier Science.1986.5:169.198. 『131 R Nair.A Simple Yet Effective Technique for Global Wiring.IEEE Trans.on CAD, March 1987.3:165.172. [141 Ro辩J.Parallel Global Routing for Standard Cells.IEEE Tram.on CAD, 1990.10:1085.1095. 【15】Brown S,Khellah M,Lemieux G Segmented Routing for Speed-Performance and Routability in Field—Programmable Gate Arrays. Joumal of VLSI Design. 1996.4(4):275.291. 【16]Betz V,Rose J.On Biased and Non-UnifoITn Global Routing Architectares and CAD Tools for FPGAs.University ofToronto Department ofElectrical Engineering,Technical Report.1996.6:358-362. 【17】Clow G W.A Global Routing Algorithm for General Cells.In Proceedings,ACM/IEEE 21“DesignAutomation Conference.1984,21:45.51. f1 81 Cohoon J P,Heek P L.BEAVER:A computational geometry based tool for switch.box muting.1EEE Transactions on Computer Aided design.1988(7):684.697. 【1 9】Lin Y,Hsu Y,Tsai F.Hybrid Routing.IEEE Transactions on Computer—Aided Design, 1990,9(2):15l-157. 【20】Linsker&An itemtive-improvement penalty—function driven wire routing system,IBM J.Res.Develop.1984.28(5):613.624. 『211 Alexander M,Robins G.New Performance枷veil FPGA routing algorithms.32nd ACM【,IEEE Design Automation Conference,San Francisco,CA,1995,6:562.567. [221 Lysecky I乙Vahid F,Tan S.Dynamic FPGA Routing for Just.in-Time FPGA Compilation.DAC 2004.11:954-959. 『231 Breucr elvin A.A class of min-eut placement algorithms,Proceedings of the 14th conference Oli Design automation,1977.1:284.290. f24】Swartz J.Rapid Routing for FPGAs.In Proceedings:University of Toronto FPGA Research Review,Peterborough,Ontario.1997.6:221.232. 【251 Shin H,Sangiovanni V.Mighty,A detailed muter based on incremental router modifications.IEEE Transactions on Computer-Aided design.V01.CAD,1 987.6:942.955 【26】Biowa S,RIlse J。Vranesic Z G A Detailed Router for Field.Programmable Gate Arrays. IEEE Tram.on CAD.Mav 1992.11(5):620.628. Segments 『27]G Lemieux。Brown S.A Detailed Router for Allocating Wire in FPGAs. ACM/SIGDAPhysical Design WorkshoP.1993.4:215.226. 【28】Arslan H,Dutt S.ROAD:An Order-Impervious Complete Detailed Router for FPGAs. 江南大学博士学位论文 ICCD 2003.1 1:350.356. 『291 Arslan H,Dutt S.An Effective Hop—Bused Detailed Router for FPGAs for Optimizing Track Usage and Circuit Performance.GLSVLSI.2004.4:208.213. 【30】周峰,童家榕,唐璞山.带时延约束的FPGA布线算法【J】.半导体学报,1999,20(9): 831.836. f311 Mo F,Tabbara A,Brayton R.A Force.Directed Maze Router.Department of EECS, University of Califomia at Berkeley.2001.1 l:404-407. [321 Nilsson N.Problem-Solving Methods in Artiflcial Intelligence.New York: McGraw-Hill.1971.6:255.260. 【33】Yang S.Logic Synthesis and Optimization Benchmarks.Version 3.0,Technique Report, MicroelectroniCS Center ofNorth Carolina,1991. [341 Brown S.Rose J,Vranesic G Z.A Detailed Router for Field Progranunable Gate Arrays. IEEE Transactions on CAD.Mav 1992.Il(5):620.628. [351 Lemieux G Brown S.A Detailed Router for Allocating Wire Segments in FPGAS. ACM/SIGDA Physical Design Workshop.1993.4:215-226. 【36】Brown S,Khellah M,Lemieux G Segmented Routing for Speed—Performance and Routability in Field-Programmable Gate Arrays.Journal of VLSI Design,1996, 4(4):275-291. 【371 Lee Y S,Alien C,wu H.A Performance and Routsbility Driven Router for FPGAs Considering Path Delays,”lEEE Transactions on ComputePAided Design of Integrated Circuits and Systems,, February,1997。l 6(2):179.185. f381、Ⅳu Y L,Marek—Sadowska M.An Efticient Router for 2一D Field—Programmable Gate Arrays.European Design Automation Con£.1994.2:412.416. 『391 Wilton S.Architectures and Algorithms for Field-Programmable Gate Arrays with Embedded Memories.Ph.D.Dissertation.University ofToronto.1997. 『401 MeMtirehie L。Ebeling C.PathFinder:A Negotiation-Based Performance—EIriven Router for FPGAs.ACM/SIGDA IntemationaI Symposium on Field—Programmable Gate Arrays. ACM Press.New York NY。1995.12:11 1.117. 【4l】郭斌林,童家榕.一种基于扩展查询表的可编程逻辑单元【J】.计算机学 报,2003.26(101:1372一1378.. 『421 Betz V Rose J.VPR:A New Packing。Placement and Routing ToOl for FPGA Research. International Workshop OB FPL.1997,7:213-222. 『43】Tessier&Negotiated A’Routing for FPGAs.In Proceedings of the Fifth Canadian Workshop on Field.Programmable Devices。Montreal,Quebec,Canada,1998,6:14.19. 『44】Soukup J.Fast Maze Router.Proc.15th DesignAutomation Conf.,1978,6:100.102. 『45】Lee C.An Algorithm for Path Connections and iIs Applications.IRE 7Fansactions on Electronic Computers.1961.9:245—265. 【46】RubiIl F.11le Lee Path Connection Algorithm.IEEE Trarts.Computers,1974,9:907.914. 【47】Hwang C H,Allen C.A Predictive System Shutdown Method for Energy Saving of Event.Driven Computation.ACM Transactions on Design Automation of Electronic Systems.April 2000.5(2):226-241. 【48】Dijkstra E W.A note 0n two problems in connexion 1Ⅳim graphs.Numerische Mathematik,1959(1):269-271. 【49】Swartz J.A Hi曲Speed Timing-Aware Router for FPGAs.Master's Thesis,Department 第三章几何查找布线算法的研究 ofElectrical and Computer Engineering.1998. 『50]Placzewsl【i M.Plane Parallel A Maze Router and Its Application to FPG舢.DAC, 1992.691.697. 『5 l】Mo F,RIbbara A。Brayton IL A Force—Directed Maze Router.Department of EECS, University ofCalifomia at Berkeley.2001.1 l:404-407. 【52】谭向东,童家榕,唐璞山.适用于数字电路的通用划分算法川.电子学报, 1996.8(24):98.101. 『531 http://www.ilog.com 【541 Nilsson N.Principles of Artificial Intelligence,Morgan Kaufmann,San Francisco CA.1980. 【551 Swartz J,Betz V,Rose J.A Fast Routability—Driven Router for FPGAs.In 6th Intemational Workshop on Field-Programmable Gate Arrays,Monterey,C八 1998.2:140.149 【56】Lemieux G,Brown S,Vranesic D.On Two—Step Routing for FPGAs.In Proceedings: International Symposium on Physical Design,Napa,Ca..1997.4:60.66. 【57】Sechen C.VLSI Placement and Global Routing Using Simulated Annealing.Kluwer Academic Publishers.Boston,M也l 988. 【58】Eheling C,McMurchie L,Hauck S~et a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(TVLSI).1995.12:473-482. 【591 Betz V,Rose J,Marquardt A.Architectare and CAD for Deep—Submicron FPGAs. Kluwer Academic Publishers。Feb.1999. f601 Betz V.Architectures and Algorithms for Field.Programmable Gate Arrays.Ph,D. Dissertation.University ofToronto.1998. f611 Betz V.VPR and T.VPack U¥er’s manual—version 4.30,2000. 【62】Betz V,Rose J.FPGA Routing Architecture:Segmentation and Buffering to Optimize Speed and Density.Kluwer Academic Publishers.1999.1 1:59.68. [631 Betz V,Rose J,Marquardt A.Architecture and CAD for deep.submicron FPGAs. KIuwer Academic Publishers.1 999. 【64】Eheling C,McMarchie L,Hauek S A'et a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(TVLSI).1995.12:473-482. 【65】“G.Heuristics and Experimental Design for FPGA Routing Algorithms.Master’s thesis。University ofCincinnati.Computer Science。2001. [66】Swartz J.A High—Speed Timing-Aware Router for FPGAs.Master'¥thesis,University ofToronto,Department ofElectrical and Computer Engineering,1998.in preparation. 『671 Tessier 1L Fast Place and Route Approaches for FPGAs.Ph.D.thesis,Massachusetts Institute ofTechnology,1998. 45 江南大学博士学位论文 第四章基于布尔可满足性的FPGA详细布线算法 4.1前言 本章的目的是阐述基于布尔函数布线的概念及其是如何应用于FPGA详细布线的。 首先我们介绍布尔可满足性(SAT)的基本原理以及基于布尔函数布线的一般概念及其 特征,然后介绍了两种用于FPGA详细布线的SAT算法:基于轨线的SAT算法(T—SDR) 和基于路线的SAT算法(R.SDR)。将这两种算法方法应用于实际的FPGA详细布线问 题中并比较优劣。最后将这些SAT算法与传统几何查找布线法进行比较,提供了广泛的 试验结果及分析,分析此方法相对于传统布线法的优缺点,提出其改进的方向。 4.2布尔可满足性的基本原理 近年来,特别是近六年,布尔可满足性(Boolean Satisfiability,SAT)[1-10J模型和 算法被电子设计自动化EDA公司和大学等研发组织广泛研究,以便解决EDA中的各种问 题,如测试向量自动生成(Automatic Test Pattern Generation)Ill,组合等价性检查 (Combinational Equivalenee Checking)121、有限模型检查(Bounded Model Checking)141、 时序分析(Time Series Analysis)19]、延时故障测试(Delay Test)1101和逻辑验证(Logic Verification)111】等。 广义地说,布尔可满足性问题(SAT)主要研究寻找对于满足一系列给定的布尔约 束条件的二元变量分配。在经典的布尔SAT问题中,这些约束条件用CNF(合取范式) 表示。这罩每个约束条件都是文字的析取(二元变量的正例集合或反例集合)。这种形 式的约束条件一般被称为条款。 现今SAT群体十分庞大并在不断地蓬勃发展【12-16],这是由于可以模拟成SAT事例的 问题的范围十分之广。值得注意的是在二叉判别图(BDD)ILl“2uJ与布尔约束条件问题 的基于查找的SAT模型之问的不同操作策略。BDD通过BDD有向非循环图(DAG)明确 的将满足分配的所有可能性表述为路径。一个BDD是不可满足的当且仅当它是平凡 “0”BDD时。与此相反,基于查找的方法探索输入变量的布尔空间以找出一个满足性分 配或必须全面地查找以得出不存在满足性分配的结论。 SAT问题属于经典的NP完全问题,在最坏情况下.其复杂度随指数级增长。为求解 SAT问题研究人员提出了不少成功的求解程序。如GRASPl6J,GRAPEu“,C}la停“J, Zchaffl2l】.SAT[22】。这些程序大多是属于Davis Putmarm Logemann Loveland(DPLL)算法18j 的变异型,即一类查找型算法。现今,基于查找的SAT方案【18,19,23,;U-2Sl在健壮性及可扩 展性上有极大优势。许多查找型方案已被SAT所采用,已知最好的方法是基于回溯搜索 算法,在查找树的每个节点,通过反复应用单句及纯文字规则【29j…,选择一个分配并删 减后面的查找。 在实验中,我们应用GRASP(可满足性问题的通用查找算法)16J,一种综合的基于 查找的SAT算法构架,解决SAT实例。GRASP是建立在假设研究过程中冲突的不可避免 性为前提的,其突出特征是具有高效的冲突分析程序的增强型基本回溯搜索能力。分析 冲突决定了它们的子句能够使GRASP无时间顺序地回溯至查找树中的较早级,潜在删减 了大部分查找空间。而且,通过记录冲突子句,GIUSP能够识别并抢占研究中稍后出现 的类似的冲突事件。最后,简捷地记录导致冲突的因果关系链使GRASP可以识别出将要 找到方案所必须的分配。 第四章基于布尔可满足性的FPGA详细布线算法 ADBAD C——1——1_————————一 D..................I------------—·-·----------l-一 C C —B B (a) A;(A1.A0)=2A1+A0 B=-(B1.B0)=281+B0 Ci(C1.CO)=2C1+C0 D{(D1.DO)=2DI+D0 (b) (c) E=(A≠C)^(A≠D)八(A≠B)^ (c≠D)八(D≠B) (d) V=(A>B)^(A>C)A (D>B)A(D>C) (e) IbE八V (f) A D B AD A D B A D —i一 日]口。日]口 C C —B B C C —B B A=2,B=C=0,D=l A-2,B=C=0,D一3 @ 图4.1通道布线问题的布尔模型 (a)用于布线的通道;(b)轨线数的二元编码:(c)垂直约束条件图(VCO);(d){j}他性约束条件;(e) 垂直顺序约束条件;(f)通道可布线性约束条件;心)两个可行方案 Figure 4.1 Boole∞modeling oftbe channel routing problem (a)Channel to be routed;(b)Binary encoding oftrack numbers:(c)Vertical Constraint Graph(VCG);(d) Exclusivity constraint:(e)Vertical ordering constraint:(D Channel mutability constraint:∽Two feasible solutions 4.3基于布尔函数的布线 基于布尔函数的布线通过将布线约束条件表示为庞大而功能强大的布尔函数把几 江南大学博士学位论文 何查找布线工作变换成一个布尔可满足性(SAT)问题。生成的布尔函数是可满足的(具 有对输入变量的一个分配,使得产生的函数赋值为常数“1”)当且仅当布局是可布线的。 布尔函数的二元变量的任何满足性分配表示一个合理的布线方案。而且对于一个产生的 布线布尔函数通过证明不存在可满足性分配,我们可以表明不存在布线方案。这一方法 的特殊优点是:目标之间相互作用的大部分几何复杂性用布尔约束条件函数隐藏并隐性 提出。这样所有的目标被同时考虑。换句话说,基于布尔函数的布线法是一种同步法, 与常规的一次一网法相比,它允许每个目标有较高的自由度。 大体上,基于布尔函数的布线法由三个主要过程组成pu”。 (1)布线约束条件分析:在处理一个布线实例时,我们仔细分析布线问题的特征并研 究一组布线约束条件。这样满足这些约束条件的任何方案必然是合理的布线方案。 (2)布线约束条件表达式:公式化的布线约束条件被表示成布尔函数。布线问题通常 需要多重约束条件并且每个约束条件分别采用布尔SAT CNF子句表示。所有布线条件必 须同时满足。因此,相应的布尔SAT子句的合取组成了一个强大的布尔可布线性函数。 我们将这个函数称作布线约束条件的布尔函数并将它记为Routable(X),这里j表示一个 合适的布尔变量的矢量,它将在后面定义。 (3)布线约束条件赋值:~个布尔SAT方法是通过布线约束条件的布尔函数Routable(X) 实现的。对这一函数的任何满足性分配必然被重新解释成一个布线方案。如果Routable(X) 被证明是不可满足的,这就表示不存在布线方案。 相比普通的一次一网布线法,基于布尔函数布线法有下列独特的优点: (1)同步线网嵌入:众所周知,传统的一次一网饰线法对线网顺序有很强的依赖性, 这是因为以前布好的线网成为未布好的线网的障碍。采用这一方法,布尔SAT方法同时 考虑了所有的布线约束条件,使其与线网顺序无关。 (2)可布线性判定:产生的布线布尔约束条件函数Routable(X)的不可满足性,就如布 尔SAT方法所证明的一样,直接表示对于给定的布局及总线布置不存在可行的布线方 案,另一方面,对于给定的布局及全局布线配置,满足Routable(X)的布尔函数变量X的 分配都与完整可行的详细布线方案相对应。 (3)灵活的公式化能力:通过简单的布尔函数处理,基于布尔函数的布线法可以很容 易地适应各种不同的布线结构。这一特征在FPGA布线中极为有用,这是由于FPGA的 结构特征快速地发展。例如,针对具有不同C.及S.块结构的FPGA,只需要对布线约束 条件的布尔表达式作少量的修改。 4.4以前对基于布尔SAT布线方法的研究 在解决布线问题上,布尔函数法的应用不如基于整数线性规划(Integer Linear Programming,ILP)IllJ或启发式查找(Heuristic Search,HS)1331的方法那么普遍。 Szymarlskit34】是第一个将几何查找布线与布尔函数公式联系起来的人。在这一工作中, 通过简化其中的3.可满足性问题…021,即给定一个3.可满足性公式,他证明了通常的折 线布线问题属于NP完全级问题,他展示了如何构筑通道布线问题,即当且仅当原始公式 可满足时,这一问题可采用一定数量的轨线布通。利用这一观点,Davadas【l”将传统的 2.层通道布线的公式设计成一个几何布尔SAT问题,实现的方法是通过将一个通道中的 垂直约束条件图、水平约束条件图及预期通道宽度的信息编码成一组n.比特布尔函数矢 量的布尔约束条件公式,并且每个要布线的线网都有一个公式。因此,如果产生的布尔 函数公式是可满足的,那么任何满足性分配相当于通道的一个可行布线,否则(即,函 数公式被证明是不可满足的)通道在预期的通道宽度下是被证明不可布通的。 第四章基于布尔可满足性的FPGA详细布线算法 图4.1描述了将一种布尔SAT技术应用于一个简单的布线问题的核心思想p“。它是一 个具有四条线网A,B,C,D的通道布线问题。其目的是为每个线网指定轨线数,这样 在水平及垂直方向的不同的线网都是不重叠的。假定一个4.轨线通道,每个线网需要2 个二元变量(例如,对应于网络A的A1、Ao)来编码其轨线数(图4.1(b))。两种类型的 约束条件定义确保了一个合理的通道布线方案。首先,排他性约束条件确保了水平横跨 重叠的线网被分配给不同的轨线。这一约束条件可以典型地用一个水平约束条件图来描 述,并通常被表示为一个布尔函数(图4.1(d))。另一个约束条件确保在通道相对边上 的相同列中带引脚的任意两条线网中,与项部引脚相关联的那条线网被指定了较高的轨 线数。这一约束条件一般通过垂直约束条件图(VCG)得到,如图4.1(c),依次与图4.1(e) 中的布尔函数V相等。这两个函数的合取(AND)是通道的完全可布线性约束条件布尔 函数R(图4.1(f))。使得R=I的变量AI,Ao,...,Do的任意二元分配对应于一个可行布线方 案,并完全确定了线网到轨线的映射。两个这样的分配如图4.1(g)。 延l'申Davadas的观点,Woodl25.351将布尔函数模拟技术应用于FPGA布线问题以解决 FPGA可布线性的问题。他将详细布线约束条件表示成一个布尔函数方程,这个方程当 且仅当布局方案可靠线时是可满足的。这个观点本质上是一种在版图、芯片级布线中长 期使用的模式布线法的变型。每条--7l脚连线被分配给可数的一组贯穿FPGA布线结构 的可能路径。每个分配项都可用唯一的二元向量编码;这些变量决定了精确的最终布线。 既然路径模式会很快变得复杂并且其数量变得难以控制,那么模式仅能通过小区域结构 进行评估,再“会聚”起来形成完整的线网。在文献【7,17,18】中由此产生的布尔问题是通 过创建一个二叉判别图(BDD)以表述可满足性方程来解决的。然而对于大型布线问题, BDD很难构筑。由于很难取得变量顺序,并且在中间计算过程中,BDD图表自身变得庞 大,难以控制的。在文献[351q=为了克服这一缺点,FPGA布局被分解成分开处理的逐个 通道片。 显然,更可取的方法应该是用一个布尔函数模拟全部FPGA布线问题。但是对于大 型设计使用BDD作为布线工具显得不切实际。基于BDD的方法本质上“生成”了产生所有 满足分配的函数。如果仅对找到一个满足性分配的函数感兴趣,那么我们代替以在输入 变量的”维布尔函数空间进行隐式系统搜索,以找出一个这样的分配或证明它不存在。 虽然基于搜索的SAT与基于BDD的SAT在运行特性上存在很大差异,但其结果是相同 的:一个满足性分配是FPGA的一个完备布线:若不存在这样一个分配则说明不可布线。 在以上的初步研究中,回顾了基于SAT的布线思想,并从其推广应用更复杂的FPGA 布线。下一节我们将应用两种新的基于SAT的公式给出了将整个FPGA布线一所有线网 同时嵌入一的结果,并详细描述这两种基于SAT的公式如何对指定全局布线及轨线总数 的布局进行不可布线性判定。 4.5两种用于FPGA详细布线的SAT算法 4.5.1基于轨线的详细布线SAT算法(T-sDR)Is,31,361 4.5.1.1 T-SDR的布尔函数公式 对表述FPGA详细布线问题的最初尝试促使了SDR(基于可满足性的详细布线法) 的开发。SDR将FPGA详细布线问题转化为可以输入至布尔SAT方案的一个CNF满足性 问题。FPGA详细布线问题可以按最简单的形式变换成一个线网到轨线的分配问题。布 线中的每一线段用一轨线变量表示,这一轨线变量是其上线段可以被布线的水平或垂直 轨线指数。于是,布线约束条件函数定义在这些变量上。一个FPGA中仅有有限量的布 线资源,并且每个布线资源是离散且严格的。FPGA的这些独特的特征表明对于确保一 江南大学博士学位论文 个合理的FPGA详细布线方案,下列两个布线约束条件是必要且充分的。 1)连通性约束条件:对于贯穿由全局布线法指定的C.及S.块序列的每条二引脚连线,连 通性约束条件确保了导电路径的存在。这些约束条件基本上模拟在C一块及S.块可得的布 线柔性。它还确保了每条二引脚连接线仅被分配给布线通道里的有效布线轨线。一个连 通性约束条件由线网的每条二引脚连线构筑。 2)排他性约束条件:确保了在同一通道中具有重叠的垂直或水平跨距的电功能不同的 线网被分配给不同的轨线。此类约束条件本质上是通道布线问题的实例,并且每条水平 /垂直通道都存在一个排他性约束条件函数。 陌习 2 l(o,2)l I.........-J …NetC—Net吐一一 ×等IlHo O |i陌 I l I.........一 0 1 2 3 4 Row Index NetA:[pin 0 ofCLB(4,2),C·block(4,1),S-Block(3,1), C—block(2,1),S-block(1,1),C—block(1,2), pinl ofCLB(2,2)】 Net B:[pin 2 ofCLB(4,O),C—block(4,1),S-Block(3,1), C—block(3,0),pin3 ofCLB(2,O)】 AH.AV,//Net A track variables BH.BV//Net B track variables CH.CV.//Net C track variables Veftical Channel 1 Ol2 (a) Vertical Channel 3 Ol 2 旧CLB, 勺一 l DST SDR O 董-id 2。 、、 ~\ - l \ _ 星6 0 旧CLB, CLB (2,0) CLB (4,O) Conn(A)=[(An-=0)V(AH-=-I)V(AH---2)】^ 【AH=AV】A [(AV-=0)V(AWl)V(AV=--2)】 (b) //Horizontal channel 1 //S-block(1,1) //Vertical channel 1 50 第四章基于布尔可满足性的FP(;A详细布线算法 ExcI(HI)=(AH:≠B啪A(AH≠CH) (c) 图4.2连通性约束条件及排他性约束条件的生成 (a)线网A,B,C的全局布线配置及相应的变量描述;(b)线网A的可能详细路线及其相应的连通性约 束条件;(c)排他性约束条件 Figure 4.2 Generation ofConnectivity and Exclusivity Constraints (a)Global routing configuration for acts A,B and C and corresponding variable declarations:(b)Possible detailed routes ofnet A and the corresponding connectivity constraint;(c)Exclusivity 针对W=B=最=3的一个FPGA,图4.2显示了一个阐明FPGA布线约束条件结构 的例子。假设每条线网都由全局布线法指定了一条全局路径(一个C.块及s.块序列)(图 4.2(a)。于是针对每条线段都生成了轨线变量以模拟对由其全局布线指定的每条通道中 的特殊轨线的可能分配。例如,在此例中,两条轨线变量与线网A相关联:AH表示它在 水平通道l中的轨线分配,而AV表示它在垂直通道l的轨线分配。每个轨线变量都是域 {o,…,W一1j中的值。 线网A的连通性约束条件结构如图4.2fb)。对于一个给定线网,连通性约束条件将轨 线变量限制在线网引脚之『自J确保一条连续传导性线路的那些值的范围之内。例如,网络 A可以被分配给水平通道1及垂直通道1中的任意轨线,只要两条通道使用相同的轨线数。 这反映了柔性分别为足=W及B=3的C一块(4,1)、S.块(1,1)及C.块(1,2)的连通必要条 件。(见图4.2(b))。用类似的方法,可以将线网B及C的连通性约束条件用公式表示。 在这个例子中排他性约束条件确保了线网A、B及线网B、C分别被重新分配给水平 通道l中不同的轨线号。一般来说,当在任何通道中两个不同的线段有重叠的跨距,就 一定存在一个不等式约束条件函数(例如,AH≠BH)。一条水平/垂直通道的排他性约 束条件函数是通道中的一组这样的不等式约束条件的合取(逻辑“与”)。图4.2(c)显示了 对于实例FPGA,水平通道1中实际排他性约束条件函数。 模拟所有线网的布线能力的布线约束条件布尔函数现在可以简单表示为所有连接 性及排他性必要条件的合取。对于当前的例子,这三条线网的可布线性约束条件布尔函 数是: Routable(X)=Corm(A)^Conn(B1^Conn(C)^Excl(H1) 这里X是轨线变量AH、AV、BH、BV、CH及CV的矢量。一个电路共有n条二引脚连接 线且每条--7I脚连接线的每条全局路径平均通过m条通道, (即,每条二引脚连接线有 L 一.1 m个网段),在基于轨线的公式中,可布线性函数所需的布尔变量数近似为加ri092W J。m。 基于布尔函数的FPGA布线中另一个值得一提的问题是引脚变轨。引脚变轨允许我 们线网布线时每个CLB逻辑引脚使用超过一个外出轨线。Betz[291指出在诸如Xinlinx XC4000系列及Lucent ORCA FPGAs 1371的商业FPGA中,CLB的输入逻辑引脚是通过多路 复用器而不是一组独立的传输晶体管连至布线线段。这样输入引脚不会变轨而CLB的输 出引脚允许被变轨(见图4.3)。变轨能减少FPGA中每条通道所需的轨线数,但在以往 的文献中,它没有得到太多的关注。 图4.4(a)及(b)阐述了引脚变轨对减少轨线需求数是如何起作用的。线网N包括SRC 江南大学博士学位论文 CLB的一个源引脚和DSTI和DST2 CLB中的两个终端引脚。虚线表示在相应通道中己被 其它线网使用的那些轨线,这样线网N不允许使用它们。图4.4(a)给出一个例子,这罩源 引脚不允许被变轨,而图4.4(b)是源引脚允许被变轨的例子。在例(a)中,轨线2不能用于 垂直通道3中,这是因为垂直通道l中的轨线2已被另一线网使用。注意到由于假设采用 对称S.块结构,每条连接的线段必须使用相同的轨线号。在例(b)中,通过使用在源引脚 的变轨,线网N能够按照每条通道减少一条轨线进行布线。 一般来说,为了充分利用CLB逻辑引脚的变轨,多引脚线网应被分解成多重二弓1脚 连接线,并且每条二引脚连接线必须被分别分配一组约束条件轨线变量。如图4.4(b)所 示,我们首先将线网N分解成2条不同的二引脚连接线:NCI及NC2,然后对于NCI及NC2 中每一个都分别采用约束条件轨线变量构筑一个连接线约束条件函数,如图4.4(c)。这 种方法增加了需要用于模拟一给定线网的约束条件变量数(在这一例子中有3至1J4个), 但它使来自相同线网的两条不同的二引脚连接线能够甚至在同一通道中选择使用不同 的轨线。由实验可见,这一技术被证明对减少每条通道所需轨线数是极为有用的。 然后,我们将这个公式称为基于轨线的SAT的FPGA详细布线公式(简称为T-SDR) 以强调这样一个事实:它是定义在代表布线可用轨线指标的一组变量之上的。 CLB l_ .SegmentA , SegmentB. (a) 图4.3 CLB上引脚连线的布线结构 (a)输出引脚连线;(b)输入引脚连线 Figure 4.3 Pin connection routing architecture at CLB (a)Output pin connectioll;(b)Input pin connection Vertical Channel 1 Vertical Channel 3 l CLB I(o,2) i一 墨{ 呈6 SRC ^ 一 、 , 、 , 、 、 CLB (4,2) I。s佗一一c CLB (2,0) , 】‘P DSTl 0 l23 (a) Cl 23 52 第四章基于布尔可满足性的FPGA详细布线算法 Vertical Channel l Vemical Channel 3 l CLB l(o,2) l 菲 星6 l l DST2 4 c l SRC CLB (4,2) I 山 T 、 - 、 一 、 CLB (2,2) :●。 DSTl (b) Two—pin connection l:NCl={NClH,NClV} Two—pin connection 2:NC2={NC2H,NC2V} Conn(NCl)=【(NCIHi-0)V(NCIH-=I)V(NClH=-2)】A//Horizontal channel l 【NClH=NClV】^ //S-block(3,1) 【(NCl v:-o)v(NCIV=-I)V(NClV-=2)】 //Vertical channel 3 Conn(NC2)=【(NC2H-=0)V(NC2HiI)V(NC2H---2)】A//Horizontal channel l [NC2H=NC2V】八 //S-block(1,1) 【(NC2V-=0)V(NC2V=-I)V(NC2Vi2)】 //Vertical channel 1 (c) 图4.4变轨减少通道所需的轨线数及其相应布线约束条件数的例子(假设布线结构为:W=4, 尼=4,B=3) (a)源引脚被允许变轨的情况;Co)源引脚不允许被变轨的情况;(c)控制(b)中引脚变轨的连通性约束条 件函数 Figure 4.4 Example illustrating haw a dogleg reduces the track counts in channels and corresponding routing constraint formulation(Routing Architecture Assumption:W=4,足=4,B=3) (a)When a dogleg is NOT allowed at source pin:(b)When a dogleg is allowed at sourc2 pin: (c)Connectivity constraint functions which handles pin dogleggings is(b) 4.5.1.2布线约束条件的CNF表达式 在这一节中,我们描述将上述的这些布尔布线约束条件函数转化为CNF形式 [11,20,21,36,38-46]。通过单纯的布尔函数处理,每个布线约束条件都能用CNF子句表示。图4.5 说明了如何由FPGA布线约束条件生成CNF布尔SAT子句。我们假设采用与图4.2中相同 的布线结构参数:W=3,辱=W,只=3。 具有一条有3条轨线宽度通道的两个布尔函数变量被分别分配给轨线变量X及Y以 编码轨线号O、l及2(图4.5(a))。连通性约束条件有两种不同的形式,这依赖于逻辑块 类型:C一块连通性约束条件列举了对于在一条给定通道中布线可用的轨线,而S.块连通 性约束条件对于R=3强制进、出去部分的路线数相等。 江南大学博士学位论文 每个连通性约束条件的CNF表达式如图4.5(b)及(c)。用于表示一个C.块连通性约束 条件的CNF子句个数依赖于∥的实际值而且很难仅仅用一个方程作为公式表示。在大多 数情况下,一个C.块连通性约束条件需要少于3条CNF子句,每条子句至多有2·[1092 W J 个字节。然而,形式为两个线路变量之间的一个等式的S.块连通性约束条件可用 2.[109,Wl条2.字节CNF子句表示,每条子句有2.[109:w1个字节(图4.5(d))。 一旦知道了目标FPGA的布线结构参数,采用CNF子句空间优化并表示每个布线约 束条件函数,就能够建立一个用于多种布线约束条件布尔函数演绎的模版表格。这样, 无论什么时候需要一个新的布线约束条件函数,我们可以仅仅查找表格获得相应的空闲 CNF子句组而避免了公式化过程中冗长的布尔函数处理。用这种方法,我们可以更有效 地将布线约束条件转变成SAT问题实例。 X=[xo.Xd---2Xl+Xo Y可Yo,YI]=-2YI+Y0 (a) f(x)=(X-=0)VO(---1)V()(=-2) =(X=-3) =(x0八xi) =(XoVX0 (b) f(X,Y)=(X=Y) =[Xo;Yol A IXl--_yj】 =【()(o—Y0)八(Yo—x0)】^【(Xl—Y1)八(Yl—X1)】 =[(一XoVYo)八(xoV瓦)】^[(:_lVYl)^(xlV可)】 (c) f(x,Y)彳X≠Ⅵ =(X-=0AY-=0)V(X=I八Y---I)V(X---2八Y;21 =(X=-0AY;0)A(X;1八Y;1)八(X;2八Y;2) =(xovxlVYoVYl)A(gVXlv-VYl)A(XoV瓦VYo v-1) (d) 图4.5布线约束条件的CNF表达式 (a)轨线变量x,Y及相应布尔变量;(b)C.块中连通性约束条件的CNF表达式:(c)s-块中连通性约束条 件的CNF表达式:(d)fl}他性约束条件的CNF表达式 Figure 4.5 Routing constraint representation in CNF: (a)Track variable X,Y and corresponding Boolean variables;(b)Connecfivity con,slmint at C-block in CNF:(c)Connectivity constraint at S-block in CNF:(d)Exclusivity constraint in CNE 第四章基于布尔可满足性的FPGA详细布线算法 4.5.1.3基于布尔函数的FPGA详细布线的综合流程 T-SDR的综合流程图如图4.6。在图中,矩形块表示一个步骤而椭圆形块表示由前面 步骤生成的对象。考虑到引脚变轨,输入网表采用二引脚连接线表示。 (1)全局布线:给定一个布局,采用任意一个布局布线法将每一条二引脚连接线分配给 由C.块及S.块构成的布线区域序列。全局布线法不选择或确定任何具体的详细资源。 (2)线网分布这一步骤将每个线网分成几个水平和垂直线网段,然后在每个通道将其 分类。在此步骤之后,我们在每条通道都有一组线网段,不考虑通道类型(水平或垂直 的)并且给每个线段分配一个轨线变量(即,一组编码的布尔变量)。 (3)轨线总数估计:如果用户没有提供目标FPGA结构,我们应用一个左边通道布线算 法确定通道宽度W1291.假设每条通道都充分分割,左边算法对于在需要用于对给定电路 布线的线路数给出较低的临界值阡孟,并且我们设∥=阡■。 (4)约束条件生成:连接性及排他性约束条件布尔函数的生成,如第4.3节所述,产生 了布线约束条件布尔函数Routable(X)。 (5)约束条件赋值:采用GRASP SAT方法找至ljRoutable(X)的一个可满足性分配或证明 goutable(X)是不可满足的。 (6.)方案说明:假设Routable00是可满足性的,源于布尔SAT方法的方案是对编码轨 线变量的布尔变量的二元值(“1”或…0’)的一个分配。这一信息被转化为对形成实际 FPGA布线方案的线网的一个实际布线资源(布线轨线及相应的布线开关)的一个分配。 如果Routable·(幻是不可满足的,那么对于给定布局及全局布线拓扑结构不存在布线方 案。 2.网线分配器 //i丽趴 、\少~轨线.数// I 4.连通性及排他性 约束条件生成器 图4.6 T.SDR的综合流程图 Figure 4.6:Overall Flow Diagram ofT-SDR 江南大学博士学位论文 4.5.2基于路线的详细布线SAT算法(R-SDR)13,5.31,36A7] 4.5.2.1研究目的 在4.5.1节中,我们给出了基于布尔SAT模式的FPGA详细布线的一种新策略,即采 用SAT方法的CNF形式表示布线约束条件并输入到一个布尔可满足性方法。 另外,通过将基于BDD的技术移植到基于查找技术,可以解决更加庞大的SAT实例, 利用函数输入变量的n.维布尔空间中的隐式系统搜索Ⅲ舶J的先进技术,SAT方法克服了 BDD的内存爆炸问题。并得出了大型布线函数的成功表达式及解法。这使得首次可以将 整个FPGA布线问题用公式表示,并同时嵌入所有线网,并且还可以证明一些实例的不 可布通性。 尽管有这些优点,用于FPGA布线的布尔SAT方法有某些局限。对于一些基准电路, 相比电路尺寸生成的布线约束条件,布尔函数过于庞大,并且运行时间过长。事实上, 布线约束条件布尔函数的CNF子句数仅是对运行时问的一种较差的预测方法:实际上是 路线嵌入本身的结构复杂度决定了运行时间。然而十分庞大的子句组很可能花费更长的 时间。考虑到当前的技术发展趋势:在一个设计中,每天都需要多重FPGA配置,这是 不可接受的,所以业界呼唤一个更有效、更快速的评估布线的公式。 2 l菡l I.............一 l 器qIH暑lI三o O 回…圜 O 1 2 3 4 Row Index (a) 网 一2 耋 I..............J A1RO i1 A1Rl AlR2 吾 O 囱…固…回 O l 2 3 4 Row Index AIR0,AIRl,A1R2//Two-pinconnectionAI routevariables (b) 第四章基于布尔可满足性的Flea详细布线算法 ×2 耋 i1 吾 O ROW Index A2R0.A2Rl。A2R2//Two—Pin connection A2 route variables (c) 图4.7基于路线公式的变晕描述 (a)线网A的全局布线配置;(b)首个二引脚连接线A I的三条详细路线及相应的布尔变量描述;(c)第二 个二引脚连接线A2的三条详细路线及相应的布尔变量描述 Figure4.7Route-basedformulation variableassignment:(a)Global routing configurationforherA:(b)The threepossible detailed routesforthefirsttwo-pin connectionAl and correspondingvariabledeclarations; (c)the three possible detailed routes for the second two-pin connection A2 and corresponding variable declarations 菩 三 lJ rack k in C-block(i,j) 舌 l Row Index Ak,BbCk//Route variableofnet气BandC (a) (Ak_Bk·Ck)。(Bk-÷Ak’Ck)。(Ck—Ak‘8k) =(AkVBk)·(AkVCk)‘(BkVAk)‘(BkVCk)‘(CkVAk)。(CkVBk) =(AkVBd‘(Akvcd’(BkVAd (b) 图4.8排他性约束条件公式 (a)采用C-块(iJ)中的轨线资源k的三条线网:(b)C·块(iJ)中轨线K的相应排他性约束条件 Figure 4.8 Exelusivity constraint formulation example (a)Three nets using a track resollrge k in C-block(ij);(b)Exclusivity constraint for仃ack k in C—block(ij) 江南大学博士学位论文 4…5 2 2 R.SDR的布尔函数公式 按照新的布线公式,一个网表的可布线性可以由代表全局布线方案采用的所有可能 的详细路线的布尔变量直接模拟。选择这种方式的变量生成了比在第4.5.1节中描述的基 于轨线的公式更为简单的一组约束条件,并使方案能用于更大型的布线实例。此新公式 的描述如图4.7,其结构参数为形=耳=只=3。线网A由驱动两个终端引脚的两条二引 脚连接线组成。二引脚连接线Al和A2的三条详细路线分别列举于图4.7(b)及(c)。布尔函 数变量现在被分配代表这样的详细路线:例如,A1R1代表正使用轨线1的A1的详细路线。 这些布尔变量作为选择变量。一条详细路线包含在最终布线方案中,如果其相应变量被 分配逻辑变量l,否则该详细路线就不能作为最终布线选择。通过这样的变量选择,FPGA 详细布线问题由轨线分配转化成可布线性检测问题。 采用这些路线变量,一个网表的可布线性就可用两类约束条件表示: 1)活性约束条件:以确保每条--4I脚连接线有至少一条被选用于最终布线方案的详细 路线。一条给定二引脚连接线的活性约束条件采取~种简单的形式,即:连接线的E线 路变量之间采用“OR”。对于一个具有n条二引脚连接线的网表,活性约束条件产生一组 聆个CNF子句,每个子句包含厅个正文字。 2)排他性约束条件:以保证在相同通道中具有重叠垂直或水平跨距的电学性质不同的 线网被分配给不同的轨线。这些约束条件与前面那些关于基于轨线的公式的描述完全相 同,但有一个简单得多的CNF表达式。一般来说,如果来自不同线网的k条详细路线 厂}、 竞争同一布线资源,则须生成一组l=1个排他性约束条件CNF子句以确保那些详细路线 \2/ 中至多有一条被分配给该资源。这些约束条件的每一个依次是两个负文字组成的一个简 单CNF子句。 排他性约束条件的构造如图4.8。资源是一个布线通道中的一条轨线。在这个例子中, 存在3条可在c.块(‘,)中的轨线k上布线的--4l脚连接线。线路变量Ak、Bk及Ck被分别分 配给这些线网。轨线k的相应排他性约束条件如图4.8(b)。这一约束条件的意思是如果轨 线k被分配给线网A、B或C之一,那么它不能同时分配给其余的线网。 对于给定布局及全局布线配置的一个网表的可布线性用一个由活性及排他性约束 条件的合取组成的布尔函数表示: 厂 ] Routable(X)=l A Live,(x)^^Exclf(x)l L19如 l‘J如 J 这里Live,(X)是-41脚连接线f的一个活性约束条件,荫姊(.jf)是资物对的一个排他性约束条 件,而Ⅳ是每条线网的可能详细路线的布尔变量的一个矢量。假设一个基准电路有总共 胛条二引脚连接线,在基于路线的公式的可布线函数中的布尔变量的总数为行.形。 R.SDR的可布线性函数的公式如图4.9,同样设结构参数为∥=足=B=3。例如, 在线网A指定的全局布线区域内,仅存在由三个布尔变量AR0,ARI,AR2表示的三条可能 的详细路线。线网B和C都产生了相似的一组路线及相应的路线变量。图4.9(b)及(c)阐述 了采用CNF形式表示的活性及排他性约束条件。Live0)=(AROvARIvAR2)表示在 第四章基于布尔可满足性的FPGA详细布线算法 AR0,ARl及AR2中至少有一条详细路线必定被选为最终详细布线方案的一部分,而 Excl(ResourcP(4,1,o)):G丽v丽i)表示布线资源,即c.块(4,1)的轨线o,仅能被线网A 的详细路线0或者线网B的详细路线0所使用,但不能被二者同时使用。 另一方面,这一基于路线的公式也是一种基于布尔函数的布线方法因此保存了在第 4.5.1节中介绍的一般基于布尔函数的布线方法的所有优点。 坷o≈I H lIoU Row Indcx NetA:[pin 0 ofCLB(4,2),C-block(4,1),S-Block(3,1), C·block(2,1),S—block(1,1),C—block(1,2), pinl ofCLB(2,2)】 Net B:【pin 2 ofCLB(4,O),C-block(4,1),S-Block(3,1), C·block(3,O),pin3 ofCLB(2,O)】 Net C:【pin 3 ofCLB(0,O),C-block(1,O),S—Block(1,1), C—block(2,1),pin2 ofCLB(2,O)】 ARo,ARl,AR2//NetA routevariables BRo,BRl,BR2//Net B route variables (a) Live(A)=(AROVARlVAR2)//Atleastonedetailed routefornetAmustbe select Live(B)=(BROVBRI VBR2)//Ditto for net B Live(C)=(CROVCRl VCR2)//Ditto for net C (b) Exel(Resource(4,1,O))=(AROVBR0)//Track 0 ofC.block(4,1) Excl(Resource(4,1,1)):(ARl VBRI)//Track 1 ofC.block(4。1) Exel(Resouree(4,l,2))=(AR2VBR2)//Track 2 ofC—block(4。1) Excl(Resource(2,l,0)户(AROVCR0)//Track 0 ofC.block(2,1) Excl(Resource(2,l,1))=(ARl VCRl)//Track l ofC.block(2,1) Excl(Resource(2,1,2))=(AR2VCR2)//Track 2 ofC.block(2,1) 江南大学博士学位论文 Found SAT Solution: AR0=1.ARl=1.AR2=o Routing Solution: NetA:AR00rARl BRO=o.BRl=o.BR2=1 CR0--0.CRl:o.CR2=I Net B:BR2 Net C:CR2 (d) 图4.9一例基于路线的详细布线约束条件公式 (a)线网A、B、C的全局布线配置及线阿A的三种可能详细路线;(b)活性约束条件的C"NF表达式;(c) 排他性约束条件的CNF形式:(d)最终SAT方案及布线方案 Figure 4.9 Example ofroute-based detailed routing eonsWaint formulation (a)Global routing configuration for nets A,B,and C showing the three possible detailed routes for net A; (b)Liveness constraints in CNF=(c)Exclusivity constraints in CNF:(d)Final SAT and routing solution 4.6实验结果及分析 为了评估我们在本章所介绍的两种SAT算法:T-SDR与R.SDR在布线时间上的有效 性,我们采取了与第三章实验中相同的布线基准【4引,为了能使以上两种FPGA布线算法 就可以在同一平台上进行比较,在进行布线之前我们统一采用VPR399对每个电路生成 30个布局,四种算法直接采用这些布局进行行线。所有的实验在频率为lGHZ的Pentium III上运行,采用了LINUX系统及512M内存。 4.6.1两种SAT布线算}法T-SDR与R-SDR的比较 由于实际运算过程中发现T-SDR耗时过多,因此仅用T.SDR算法对五个相对较小 规模的电路进行布线。表4.1显示了采用两种布线算法的平均布线时间及其标准误差, 可知T-SDR的布线时问及标准误差分别约是R.SDR的31.4倍及36.8倍。图4.10、图 4.11清楚显示了在不同电路规模下两种布线算法的平均布线时间及其标准误差的变化, 可以看出,随着电路规模的增大,两种算法在平均布线时『日J上及其稳定性(标准误差越 大稳定性越差)上的差异十分之明显。这从图4.12总体布线时间及图4.13的总体标准 误差可以更加清楚的显示出来,因此,相比T-SDR算法,R.SDR算法不仅极大的缩短 了布线时间,并且在稳定性上也有很大的提高。 表4.1 T-sDR与R.SDR的综合布线时间比较 Table 4.1 Overall Computing Time Comparisons for T-SDR and R—SDR 第四章基于布尔可满足性的FPGA详细布线算法 图4.10T-SDR与R-SDR在不同电路逻辑块规模下的综合布线时间 Figure 4.10 Overall Computing Time for T-SDR and R-SDR vs.Circuit Block Size 图4.1l T-SDR与R-SDR在不同电路逻辑块规模下的综合计算时间的标准误差 Figure 4.1l Standard Deviation ofOvemll Computing Time for T-SDR and R-SDR vs.Circuit Block Size 图4.12 T-SDR与R.SDR的总体布线时间比较 Figure 4.12 Total Computing Times comparison for T-SDR and R-SDR 61 江南大学博士学位论文 图4.13 T-SDR与R.SDR的综合布线时间的总体标准误差比较 Figure 4.1 3 Total Standard Deviation comparisons for T-SDR and R-SDR 4.6.2 SAT算法与常规几何查找布线算法的比较 4.6.1节中我们从布线时间及稳定性上对两种SAT算法进行了比较,但这不足以说 明SAT算法的优劣,为此我们将两种SAT算法中较优的R.SDR算法与常规的几何查找 布线算法PathFinder、VPR430、Frontier进行了综合比较。 表4.2显示了这四种算法的平均布线时间及其标准误差。 图4.14给出了针对20个基准电路中一个典型电路SEQ,四种算法在置信度为99% 的条件下的综合布线时『日J的置信区间分布情况。图中横条的宽度直接反应了布线时间的 稳定性,代表Frontier的横条最窄,因此最稳定,而代表R.SDR的横条最宽因此布线稳 定性最差。 根据4.2的数据可以得到R.SDR算法在布线时间及标准误差上分别为PathFinder算 法的120%、110%,VPR430的297%、186%及Frontier的912%、587%。图4.15及 图4.16给出了在不同电路规模下两种布线算法的平均布线时|'日J及其标准误差的变化。可 以看出,R.SDR算法无论在平均布线时间还是在稳定性上比三种给出的几何查找布线法 算法都要差,仅与PahtFinder算法较为接近。图4.17、图4.18从整体上对三种算法进行 的比较更充分地显示了这一点。 虽然R.SDR在平均布线时间及稳定性上不如几何查找布线法,但由于其具有可布 线性判定的特性,在处理某些不可不通的线网上有着明显的优势,如表4.3中CLMA、 PDC、SPLA三个基准中共10个布局是不可布通的,而PathFinder、VPR430、Frontier 算法在布线迭代过程中不能判定其是否能够布通,一直要运算到临界时『日J才停止(本文 采用的是10000秒)。而R.SDR算法在运算过程中就可以判定布局的可布通性,因此为 运算节省了大量的时间。 相对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优 点,例如:同步线网嵌入及可布线性判定。然而,在本实验中R—SDR的在布线延迟上 的性能不如几何查找布线法算法,这是因为R-SDR仅完成一个详细布线任务,而几何 查找布线法PathFindel'、VPR430、Frontier完成了所有的布局及全局/详细布线,这样当 几何查找布线法不能很容易地找到一个详细布线方案时,它能够改变全局布线配置。因 此为了减少(或消除)几何查找布线法与R.SDR之间的差距,我们需要设计一种方法 对每条二引脚连接线同时提供多重布局布线配置。用这种方法,我们期望R.SDR能考 虑不同的总线选择,即使其中一些是不合需要的全局布线配置。尽管有这个局限,基于 路线的公式仍然看来能产生十分有竞争力的布线结果。 第四章摹于布尔可满足性的FP(;A详细布线算法 表4.2 PathFinder、VPR430、Frontier、R-SDR的综合布线时间比较 Table 4.2 Overall Computing Time Comparisons for PathFinder,VPR430,Frontier and R·SDR FroraJ盯VPR430 PathFmda R-SDR 图4.14 PathFinder、VPR430、Frontier、R-SDR的综合布线时间比较(SEQ,CI=99%) Overall Figure 4.14 Computing Time Comparisons for PathFinder,VPR430,Frontier and R-SDR(SEQ, 江南大学博士学位论文 图4.15 PathFinder、VPR430、Frontier、R.SDR在不同电路块规模下的综合布线时间 Figure 4.15 Overall Computing Time for PathFinder,VPR430.Frontier and R-SDR vs.Circuit Block Size 图4.16 PathFinder、VPR430、Frontier、R—SDR在不同电路块规模卜I的综合计算时间的标准误差 ofOverall Figure 4.16 Standard Deviation Computing Time for PathFinder,VPR430.Frontier and R—SDR vs.Circuit Block Size 图4.17 PathFinder、VPR430、Frontier、R.SDR的总体布线时间比较 Figure 4.17 Total Computing Times comparison for PathFinder,VPR430。Frontier and R-SDR 第四章基于布尔可满足性的FPGA详细布线算法 图4.18 PathFinder、VPR430、Frontier、R-SDR的综合布线时间的总体标准误差比较 Figure 4.18 Total Standard Deviation comparisons for PathFinder,VPR430.Frontier and R-SDR 表4.3判定lO个电路的不可布线性所需时间 Table 4.3 Computing Times for deciding the unroutability often circuits 4.7本苹小结 1)介绍了两种布尔基于SAT的FPGA详细布线法,即基于轨线的公式T-SDR及 基于路线的公式R.SDR。这两种方法中都采用了SAT方法的CNF形式表示布 线约束条件。另外,通过将基于BDD的技术移植到基于查找技术,可以解决 更加庞大的SAT实例,这使得能够将整个FPGA布线问题用公式表示,并同时 嵌入所有线网。初步结果令人鼓舞:我们可以布通各种FPGA基准,并且还可 以证明一些实例的不可布通性。 2)相比T-SDR,在R.SDR公式中可布线约束条件用一组“路线”变量表示,对于 一给定线网,其中每个变量都指定一条特定的详细路线。对比实验表明,基于 路线的公式R.SDR产生了一种更容易评估可布线性的公式,T-SDR的布线时 间及标准误差分别约是R.SDR的31.4倍及36.8倍,因此R-SDR公式比基于轨 线的T-SDR公式缩短了布线时间,极大的提高了布线稳定性。 3)尽管R.SDR取得了很大的成功,在应用于大规模FPGA上他们仍然不能与传统 布线法相比,实验结果表明R.sDR算法在布线时间及标准误差上分别为 PathFinder算法的120%、110%,VPR430的297%、186%及Frontier的912%、 587%。这一现象的主要原因是R-SDR受由不考虑其特性的全局布线法提供的 单一全局布线配置所约束条件。因此一个更可取的方法是同时提供多个全局布 线选项以向R.SDR提供更多的路线探查自由度。将布尔方法延伸致更大型的 FPGA的一种可能的方法是将基于路线的FPGA详细布线公式与传统的布线方 法相结合。这将是下一章的主题。 江南大学博士学位论文 参考文献 【l】Larrabee T.Test pattern generation using Boolean satisfiability.IEEE Trans On Computer-Aided Design ofIntegrated Circuits and Systems,1995,14(1):4-15. 【2】Goldberg E,Prasad M,Brayton RK.Using SAT for combinational equivalence checking. In:Proceedings ofthe Design,Automation and Test in Europe Conference and Exhibition, MunicIL Germany,2001.10:1141.112l 【3】 Nam G,Sakallah l(,Rutenbar 1L A New FPGA Detailed Routing Approach Via Search-Based Boolean Satisfiability.IEEE Transactions on computer-aided design of integrated circuits and systems.June 2002.2l(6):674-684. 【4】Shtrichman O.Tuning sat checkers for bounded model—checking,in Computer Aided Verification.12th International Conference(CAV’00),Spfinger,Verlag,Bedin,2000. 【5】 Narn G,Sakallah k Rutenbar R.Satisflability.Based Layout Revisited:Detailed Routing of Complex FPGAs Via Search—Based Boolean SAT.Intl’Symposium on FPGAS.1999.2:167.175. 【61 Silva J,Sakallah K.GRASP:A Search Algorithm for Propositional Satisfiability.IEEE Trans.on Computers.May 1999,48(5):506.521. [7】 Aloul F,Markov I,Sakallah K.Faster SAT and Smaller BDDs via Common Structure. ICCAD 2001.7:443.448. a1.m 【8】 Beume P,Karp,Pitassi T,et efficiency of Resolution and Davis—Putnam Procedure.to aear in SIAM Joumal on Computing.2002.4(3n:1048.1057. 【9】Kantz H,Schreiber T.Nonlinear Time Series Analysis,Cambridge University Press, 2001. 【1 0】Yang l(,Cheng KT,Wang LC.TranGen:A SAT-Based ATPG for Path-Oriented Transition Faults.Proe.Asian and South Pacific Design Automation Conference,Jan. 2004.1:92-97. [1l】Wilton S.Architectures and Algorithms for Field.Programmable Gate Arrays with Embedded Memories.Ph.D.Dissertation.University ofToronto.1997. f121 Cook S A,Mitchell D G.Finding Hard Instanccs ofthe Satisfiability Problem:A Survey. DIMACS Ser.Discr.Math.&Theor.Comp.Sci..1997.6:1.17. 【13】DIMACS.Boolean Satisflability Challenge Benehmarks:ftp://dimacs.mtgers.edu/ pub/challenge/sat/benchmarks/cnf f141 Kravets V,Sakallah K.Generalized Symmetries of Boolean Functions.ICCAD 2000.10:526—532. 【15】Soicher L H.GRAPE:A System For Computing w油Graphs and Groups.in Groups and Computation(L.Finkelstein and W.M.Kantor,eds),DIMACS Ser.in Discr.Math. &Theor.Comp.Sci..1993.11:287—291. [16】Goldberg E,Novikov Y.BerkMin:A Fast and Robust SAT-solver.In Proe.Design Automation and Test In Europe.2002.9:142.149. 【1 7】Bern J,MeineI C,Slobodova A.E硒cient OBDD—Based Boolean Manipulation in CAD Beyond Current Limits.Proc ACM[,IEEE DAC.1995.6:408-413. 【l 8】Berman L.Ordered Binary Decision Diagrams and Circuit Structure.Proe.1EEE ICCD, 1989.1l:392.395. 【1 9】Vemuri N,Kalla P,Tessier R.BDD-based logic synthesis for LUT—based fpgas.ACM 第四章基于布尔可满足性的FPGA详细布线算法 Trans.on Design Automation ofElectronic Systems.2002.7(4)501.525. 【20】Bryant R E.Binary decision diagrams and beyond:enabling technologies for formal verification.in Proc.ACM/IEEE Int.Conf.Computar-Aided Design,1995.11:236.243. 【21】Zhao Y,Zhang L,Malik S.Ch艘engineering all efficient SAT solver.in Proc ACM/IEEE 39th Design Automation Conf..Las Vegas。2001.6:530.535. 【22】http://www.eecg toronto.edu/~vaughn/challenge/challenge.html 【23】Brace KS,Rude R L,Bryant R E.Efficient Implementation of a BDD package.P l'oc. ACM/IEEE DAC.1990.6:40-45. [24】Ghan P K.On Routability Prediction for Field Programmable Gate Arrays.Proc.IEEE DAC.1993.6:326—330. 【25】Wood R.Routing for FPGAs via Boolean Satisfiabiliry.M.S.Thesis,Dept.of ECE, Camegie Melton University.May 1996. 【26】Benini L,Micheli G D.A survey of Boolean matching techniques for library binding. ACM Trans.Des.Autom.Electron.Syst.,1997,2(31:193.226. 【27】Cong J,Hwang Y Y.Boolean matching for LUT—based logic blocks诵tll alications to architt戈-qure evaluation and lgchnology maing. IEEE Trans.On CAD.2001. 20(91:1077.1090. 【28】Brown S,Rose J,Vranesic Z.A detailed router for field programmable gate arrays, IEEE Trans.Computer—Aided Design,May 1992(1 1):620.628. f291 Swartz J S,Betz V,Rose J.A fast routability driven router for FPGAs.in Int.Symp. FPG舡.Feb.1998.5:140.149. [301 Garey M凡Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness.W.H.Freeman and Company.1 979. 【311 Nanl G,Aloul F,Sakallah K气et a1.A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints.International Symposium on Physical Design,2001。4:222.227. f321 Bryant R E.Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. ACM Computing Surveys.Sept.1 992.3(24):293-3 l 8. 『331 Pearl J.Heuristics:Intelligent Search Strategies for Computer Problem Solving. Reading.MA:Addison Wesley.1984. 【34】Szymanski T.Dogleg Channel Routing is NP—Complete.IEEE Transactions on Computer-Aided Design,Jan.1985.4(11:31-41. 『35]Wood R G,Rutenbar R A.FPGA Routing and Routability Estimation Via Boolean Satisfiability.IEEE Transactions on VLSI Systems.1998.6:222.231. 『361 Naln G.A Boolean Based Layout Aroaeh and its Alication to FPGA Routing.Ph.D. dissertation,Dept.ofElect.Eng.Comp.Sci..Univ.ofMichigan,Ann Arbor.MI,2001. f371 Lucent Technologies,Field.Programmable Gate Arrays Data Book,Oct.1 996. [381 Marques-Silva J P,Silva L G.Algorithms for satisfiability in combinational eircuits based on backtrack search and recursive learning.in Proc.12th Symp.Integrated Circuits Syst.Design,1999.9:192.195. 【39】Velev M,Bryant R E.Efieetive use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors.in Proc.ACM/IEEE Design Automation Conf..200 1.6:226.23 1. 【401 Devadas S.Optimal layout via Boolean satisfiability.in Proc.ACM/IEEE hat.Conf. 江南大学博士学位论文 Computer-Aided Design,1989.1l:294-297. 【41】Brisoux L,Gregoire E,Sais L Improving backtrack search for SAT by means of redundancy.Foundations of Intelligent Systems.1 lth Intl.Symp.。ISMIS’99.Warsaw, Poland,June‘99.Berlin,Germany:Springer 1999.11:301.309. 【42】Crawford J,Ginsberg M,Luks E,et a1.Symmetry-breaking predicates for search problems.5th Intl Conf.Principles of Knowledge Representation and Reasoning(KR’96), Cambridge,MA.1996,5:148—159. 【43】Nam G,Sakallah k Rutenbar R A.A Boolean satisfiability based incremental rerouting aroach with alication to FpGAs.in Proe.Design Automation Test Eur..2001.3:560.564. 【44】Hansen P,Jaumard B.Algorithms for mc maximum satisfiability problem.Computing. 1 990(44):279-303. 【45】Cha B,1wama k Kambayashi Y,et a1.Local search algorithms for partial MAXSAT.In Proe.14th Nat.Conf.Artificial Intell.。1997.8:263-268. 【46】Hooker J N.Resolution and the integrality of satisfiability problems.Math.Program. 1996(74):1-10. 【47】Nam G,Sakallah K,Rutenbar R.Hybrid Routing for FPGAs by Integrating Boolean Satisfiability with Geometric Search.International Conference on Field Programmable Logic and Alications,2002,9:360·369. 【48】Yang S.Logic Synthesis and Optimization Benchmarks,Version 3.0,Technique Report, MicroelectroniCS Center ofNorth Carolina,1991. 第五章将布尔可满足性与几何查找相结合的混台布线算法 第五章将布尔可满足性与几何查找相结合的混合布线算法 5.1前言 在第4章中,我们介绍了两种采用CNF形式的SAT方法表示布线约束条件的FPGA 布线算法。其中R-SDR生成了更容易评估的布尔SAT实例,使得对于每一条连接线在 全局布线区域内捕获全部可用的详细路线组成为可能。然而这种方法在可扩展性方面有 不可避免的局限性(即在用于大规模电路布线上所耗时间过长)。因为R.SDR是一个详 细布线公式,如果一个全局布线法以某种方式提供了一种不符合需求的布线方案, R.SDR将无法摆脱这一非理想的上层决策。事实上,这也是R.SDR的布线方案不如几 何查找布线算法PathFinder、VPR430及Frontier的主要原因。 为了克服这一缺陷,本章将提出三种将SAT算法与传统几何查找布线算法相结合的 新型混合布线算法。 5.2混合布线算法的研究目的 基于SAT布线法是一种并行方’法I”】,它能够同时嵌入多条连线。也就是说,与传 统的一次嵌入一条网线的算法不同的是,这种算法与连线顺序无关。更令人关注的是基 于布尔SAT布线法是一种“精确”方法;一旦我们生成表示所有可能的布线约束条件的 一个布尔公式,任何满足对变量值的布尔分配都代表一个有效的布线方案。这在布线领 域中是十分少见的。事实上,在给定布局的情况下可布线性判定是非常重要的。例如, 在布线阶段,能够评估每个布线结构的可布线性对于生成一个较佳的布线方案是很有帮 助的。传统的一次布通一条网线的布线算法(例如,LeeH-“l。CGE!”】。SEGAll3,14]. TRACERI”i,GBP[16】’SROUTEIl7】,PathFinder[18,1蚴】,VPR[25;6。301,Frontier[31-371等),由 于其对连线顺序直接或间接的依赖而不能判定可布线性。尽管有这样独特的优点,单纯 的基于SAT的布线法有一个根本的局限:由基于SAT布线法生成的问题的可控规模相 比常规布线法要小得多。这就是为什么基于SAT布线法仅用于少量的并且是经过仔细选 择的布线问题,例如,在通道布线实例及FPGA布线中。 而另一方面,传统的几何查找布线算法虽然具有广泛的拆线重布线的能力,由于其 对连线顺序直接或『自J接的依赖而不能判定可布线性。 例如,如果对于一个给定电路布局存在一个布通方案,则几何查找布线算法在经历 足够的迭代次数后,最终将收敛于这一方案。但是如果问题是不可布通的,算法将不会 收敛并在一个合适超时处理之后停止运行。这种收敛问题是在所有几何查找的一次线网 布线法中都存在的:即这些算法不能判定给定电路布局的可布通性。即使在一个电路中 当仅有少数线网不可布线,这些算法也必须采取耗时的拆线重布线的步骤,而且也不一 定就能得到一个布线方案。 因此本章尝试将一种基于线路的SAT算法R-SDR与传统的几何查找布线算法相结 合以取长补短、克服彼此的缺点。 5.3混合布线算法 5.3.1混合算法的主要思想 在某次迭代中,几何查找布线算法对于每条连接线仅考虑一条布线路线。这一考虑 江南大学博士学位论文 的路线被当作对于基于最新拥挤及延迟成本度量的连接线的最佳路线。随着迭代的推 进,每条连接线都可以探索出更多的布线选择(可能沿着不同的全局布线路径)。结合 算法的主要思想是:在几何查找布线算法的每次迭代过程中,都可以列举出针对每条连 接线探索出一直到当前的迭代为止的所有布线路径并通过布尔SAT技术对他们全部进 行检测。这一方法的基本原理是:既然每次迭代仅生成每条--4l脚连接线的最佳路线, 那么如果在某一点找不到布线方案,则就值得将它们同时进行考虑。 (a)PathFinder or VPIH30 or Frontier flow (b)SAT routing flow 图5.1三种混合算法的综合流程图 Figure 5.1 Overall flow diagrams ofthree combined algorithms 5.3.2 PathFinder与R.SDR相结合的混合布线算法(P.R.SDR) 结合算法的综合流程图如图5.1。左半边表示基本pathFinder流程而右半边对应于 基于SAT布线流程。事实上,不是每次迭代都必须运行基于SAT流程因为将布线问题 转换成布尔SAT实例的成本较高。因此,在对于每个信号都积累了足够多的新的详细路 线之后,运行基于SAT布线流程是最有效的。 结合算法的伪码如图5.2。我们保持了一个称为Pathlist的数据结构以记录到目前为 止所探索出的多个详细路线。Pathlist由每条二引脚连接线所控制并且它有一个冗余校验 能力可以避免将针对每条二引脚连接线的恰好相同的两次布线路线包含在内。首先在行 0,Pathlist被复位为空。伪码的行l到18对应于原来的PathFinder算法,在行19,一 旦判定存在至少一个被共享的布线资源,我们就进入布尔R.SDR阶段。每条线网的详 细路线首先被分解成--4f脚连接线组(行20)然后被插入相应的PathList桶模型。在行 26,执行基于路线的布线约束条件公式并生成一个可布线性布尔函数Roumb跆(X)。生 成的布线约束条件布尔函数Routable(X)捕捉到针对每条二引脚连接线到目前为止所探 第五章将布尔可满足性与几何查找相结合的混合布线算法 索到的一组详细路线的所有布线约束条件。换句话说,在第i次迭代,针对每条二引脚 连接线至多考虑珀∈不同的详细路线。在行27,用一个布尔SAT方法求布尔函数的值。 如果找到了任何布线方案,则算法返回方案。否则,执行PathFinder算法的下一次迭代。 这一新方法可以通过布尔SAT技术给予一个强有力的可布线性判定。一旦找到了SAT 方案,这一方案可以很容易地表示为一个布线方案。如果SAT实例是不可满足的,则表 示不存在具有以下条件的布线方案:1)当前的布局配置及2)每条--9l脚连接线探索出 的当前的详细路线组。来自不可布线性实例的信息能够对后面的重布线程序有很大的价 值。 【0】Path List PL=empty 【1】w11ile shared resources exist(global router) 【2】Loop over all signals f(signal router) 【3】 Rip up routing tree R乃 【4】 月乃钢 【5】Loop until all sinks咯have been found 【6】 Initialize砸甜ty queue PO tO RTt at cost 0 【7】Loop until new t“is found 【8】 Remove lowest cost node m from PQ [9】Loop over fanouts n ofnode m 【10】 AddntOPQatcost“+Ph 【1l】 End [12】 End 【1 3】Loop over nodes n in path 0 tO毋Coacktrace) [14】 Update“ 【15】 Add ntoRTj 【16】 End 【17】 End 【18】 End 【19】 Ifthere is no shared resource,then return [20】Loop over all signals, 【21】Decompose R瓦intO a set oftwo—pin connections tpc#’s 【22】Loop over all two·pin connections枷p 【23】 Add tpc,!,tO Path List凡F 【24】 End 【25】 End 【26】 Route·based routing constraint formulation f27】 Routing constraint evaluation 【28】 If Routable then return 【29】End 图5.2 PathFinder与R-SDR相结合的算法 Figure 5.2 The combined algorithm ofPathFinder and R-SDR 江南大学博士学位论文 5.3.3 VPR430与R-sDR相结合的混合布线算法(v-R-sDR) 结合算法的流程图如图5.1。左半边表示基本VPR430流程而右半边对应于基于SAT 布线流程。这与PathFirider与R.SDR相结合的混合布线算法相似。相对于纯VPR430 布线算法,在并入混合算法后VPR430的新增参数一astar fac<float>、 一max criticality<float>、--criticality (见 3.4 节)所采用的默认值分别为1.17、_exp<float> O.98、0.99。 结合算法的伪码如图5.3。首先按照采用Prim的最短路径算法p8】所搜索到的节点到 终端的距离将初始化的目标输入端排序,然后运行VPR430布线法整个程序开始对所有 t1 、 线网进行布线,判断是否能布通,若不能布通则将每条线网用己route(‘J的SAT公式表示, 从而可以采用R.SDR算法进行布线,即使仍不能布通则也可以找出布线竞争点(即: 被多条线网占用的布线资源),增加布线成本重新布线。 【0】Hybrid Algorithm{ 【1】 read problem(): 【2】 initialize(); 【3】 Order the sinks using Prim’S Algorithm; 【4】 While still more sinks tO route; 【5】 run VPR430(); 【6】 Ifthere is no sink tO route for this net,then return; 【7】 run R—SDR(); 【8】 Routing constraint evaluation; 【9】 Ifroutable,then return; 【10】 return Solution(); 【11】End while 【12】) 图5.3 VPR430与R.SDR相结合的算法 Figure 5.3 The combined algorithm ofVPR430 and R—SDR 5.3.4 Frontier与R.SDR相结合的混合布线算法(F.R-SDR) 结合算法的综合流程图如图5.1。左半边表示基本Frontier流程而右半边对应于基于 SAT布线流程。这也同PathFindex与R.SDR相结合的混合布线算法相似。 结合算法的伪码如图5.4。首先按照采用Prim的最短路径算法所搜索到的节点到终 端的距离将初始化的目标输入端排序,然后执行区域协商布线,并采用一个扩张列表来 保存扩张的可能轨线及其相应成本。伪码的行1到19对应于原来的Frontier算法。在行 19,一旦判定存在至少一个被共享的布线资源,则在行2l,将扩张列表转化为由每条二 引脚连接线组成的Pathlist,我们就进入布尔R.SDR阶段。在行22,执行R-SDR公式 生成一个可布线性布尔函数Routable(X)。在行23,用一个布尔SAT方法(本文中采用 的是GRASP算法)求布尔函数的值。如果找到了任何布线方案,则算法返回方案。否 则,执行Frontier算法的下一次迭代。 第五章将布尔可满足性与几何查找相结合的混合布线算法 【1】Order the sinks using Prim。s Algorithm. 【2】Perform Domam Negotiation. 【3】Target=sink closest to source. 【4】Put track segments attached to source onto expansion list、vitll cost given by(3.4). 【5】Remove lowest cost track segment from expansion list. 【6】W11ile the net input has not been reached. 【7】Put neighbors ofthis track onto expansion list、vitll cost given by(3.3). 【8】 Remove lowest cost track segment from expansion list. 【9】Endwhile 【10]Empty the expansion list. 【l 1]While still more sinks to route for this net. 【12】Target=next sink determined from Prim’s Algorithm. 【13】Put whole net created to this point onto expansion list、vitll cost=口×dj. segments 【14】Put track attached to source onto expansion list诵th cost given by (3.4). 【15】 Remove lowest cost track segment from expansion list. 【1 6】 While the net input has not been reached. 【17】Put neighbors ofthis track onto expansion list、vitIl cost given by(3.3). 【1 8】 segment Remove lowest cost track from expansion list. 【19】 【20】 Endwhile Ifthere is no sink to route for this net,then return. 【21】 [22】 Convert expansion list into pathlist consist ofa set oftwo-pin connections. Round—based routing constraint formulation. 【23】 Routing constraint evaluation. [24】 [25】 Ifroutable,then retu_rn. Empty the pathlist. [26】 Empty the expansion list. 【27]Endwhile 图5.4 Frontier与R.SDR相结合的算法 Figure 5.4 The combined algorithm ofFrontier and R-SDR 5.4实验结果及分析 5.4.1三种新型混合布线算法之间的比较 为了对比本章提出的三种新型混合布线算法:P.R.SDR、V-R.SDR、F.R.SDR的有 效性,我们采取了与第三章实验中相同的布线基准,在进行布线之前我们统一采用 VPR399对每个电路生成30个布局,三种混合算法直接采用这些布局进行布线。所有的 实验在频率为1GHZ的Pentium III上运行,采用了LINUX系统及512M内存。 表5.1给出了在不同基准电路三种混合算法的30布局下各自的综合布线时间及其标 准误差值。 图5.5给出了针对20个基准电路中一个典型电路SEQ,三种算法P.R.SDR、 V-R-SDR、F—R.SDR在置信度为99%的条件下的综合布线时间的置信区间分布情况。图 中横条的宽度直接反应了布线时间的稳定性,代表F.R-SDR的横条最窄因此最稳定, 73 江南大学博士学位论文 而代表P.R.SDR的横条最宽因此布线稳定性最差。 从表5.1可知,相比P.R.SDR,V-R.SDR及F.R.SDR在布线时间上分别减少了57.9% 及85.5%,并在稳定性上分别提高了41.7%及82.5%,这是由于在布线时间及稳定性上 VPR430、PathFinder本身就优于PathFinder。从图5.6可以清楚地看出随着逻辑块规模 的增大,布线所耗时间的优劣越来越明显:Frontier与R-SDR相结合的混合布线算法 F.R.SDR可以在最短的时间内完成布线,而PathFinder与R.SDR相结合的混合布线算 法P.R.SDR所耗时间最长。 从图5.7可知,随着逻辑块规模的增大,从布线时间的标准误差值的走势,我们可 以看出,三种算法的稳定性从高到低低排序是:F—R.SDR、V-R.SDR、P—R.SDR。 图5.8、图5.9给出了三种算法在总布线时间及其总标准误差的对比情况。由此,我 们可以更清楚的看出三种算法的比较结果:F.R—SDR最优,P—R.SDR最差。 由第三章中的分析可知,三种纯几何查找布线算法PathFinder、VPR430、Frontier 在布线所耗时间上递减及其稳定性上递增,受此影响,其各自与R.SDR相结合的混合 算法也表现出相似的特性。 表5.1 P.R.SDR、V-R.SDR、F-R.SDR的综合布线时间比较 Table 5.1 Overall Computing Time Comparisons for P-R-SD&V-R·SDR and F-R—SDR … Si:。—i五■—百i——i品■——丽■——i瓦■——]丽_ c眦un Block F—R—SDR(second) V.R.SDR(second)P-R-SDR(second) 第五章将布尔可满足性与几何查找相结合的混合布线算法 图5.5 P-R·SDR、V-R—SDR、F-R-SDR的综合布线时间比较(SEQ.ct--99%) Figure 5.5 Overall Computing Time Comparisons for P-R-SDR,V-R-SDR and F-R-SDR(SEQ,C1--99%) 图5.6 P.R-SDR、V-R-SDR、F.R.SDR在不同电路块规模卜.的综合布线时间 Overall Figure 5.6 Computing Times for P-R—SDR,V-R-SDR and F-R·SDR vs.Circuit Block Size 图5.7P-R.SDR、V-R.SDR、F—R.SDR在不同电路块规模下的综合计算时间的标准误差 Figure 5.7 Standard Deviation ofOverall Computing Time for P-R·SDP..V-R·SDR and F-R-SDR vs. Cireuit Block Size 江南人学博±二学位论文 图5.8 P—R.SDR、V-R.SDR、F.R.SDR的总体布线时间比较 Figure 5.8 Total Computing Time comparisons for P-R-SDR,V-R·SDR and F-R·SDR 图5.9 p-R.SDR、V-R.SDR、F-R.SDR的综合布线时间的总体标准误差比较 Figure 5.9 Total Standard Deviation comparisons for P-R-SDR,V-R-SDR and F-R_SDR 5.4.2混合布线算法与纯几何查找布线算法的比较 为了克服传统的一次布通一条网线的布线算法由于其对连线顺序直接或间接的依 赖而不能判定可布线性,我们采用了将详细布线算法R-SDR并入其中的方法,得到三 种混合算法P.R.SDR、V-R.SDR、F—R.SDR。将表4.1的数据与第三章中的表3.1的数 据进行对比,可以得出混合算法与单纯几何查找布线算法的优劣。 图5.10、图5.11.、图5.12分别显示了三种混合算法P-R.SDR、V-R—SDR、F·R—SDR 及其分别相应的纯几何查找御线算法PathFinder、VPR430、Frontier对不同规模的逻辑 块基准下布线时间的变化,可以看出,在布线时间上三种混合算法明显优于纯几何查找 布线算法。 图5.13、图5.14.、图5.15分别显示了三种混合算法P-R—SDR、V-R—SDR、F—R-SDR 及其分别相应的纯几何查找布线算法PathFinder、VPR430、Frontier在不同规模的逻辑 块基准下布线时间的标准误差。随着逻辑块规模的增大,混合算法的优势越来越明显: 相对于纯几何查找布线算法,混合算法在布线的稳定性方面有很大提高。 图5.16、图5.17显示各个算法的总体布线时间及稳定性的对比。由表3.2及表5.1 的数据可知,相对于PathFinder、VPR430、Frontier,P—R-SDR、V-R·SDR、F—R—SDR在 布线时间上分别缩短了32.O%、28.9%、25.O%,在布线稳定性上分别提高了24.1%、25.O%、 29.1%。 从另一个角度看,分别与第三章图3.13中的算法PathFinder、VPR430、Frontier对 第五章将布尔可满足性与几何查找相结合的混台布线算法 比,图5.5中的算法P.R.SDR、V-R—SDR、F.R-SDR的横条宽度都要较窄,这就说明了 混合算法在稳定性上相对传统布线算法更佳。 相对于纯几何查找布线算法,结合算法在布线性质上的提高主要是由于结合了具有 可布线性判定的SAT算法:R.SDR,在遇到某些不可布通的网线时能及时判定其不可布 通性而不需要将布线迭代运算进行到临界时间点。表5.2给出了三个布线基准下共10 个不可布通的布局,P.R.SDR、V-R.SDR、F.R.SDR在判定其不可布通时所耗时间。而 如果采用PathFindel"、VPR430、Frontier则无一例外的都要运算至10000秒。 对比表5.2与表5.1中相应基准布线所耗时间可以观察到一个非常有趣的事:对于 不可布通的布局,花费在判定布局的不可布线性上的时间较布通一个可布通布局的时间 要短。这是因为这种SAT方法是检测被多个线网共享的关键布线资源的一种快速高效的 方法。显然,这一信息可用于后面的拆线重布线阶段。一旦探索出一条关键的资源,仅 仅对那些正在使用着已确定的具有更复杂绕线路径的关键资源的线网执行拆线重布线 程序。不断地重复这个程序直到布线问题变得可布通。 图5.10 F-R.SDR和Frontier在不同电路块规模下的综合布线时间 Figure 5.10 Overall Computing Time for F-R-SDR and Frontier vs.Circuit Block Size 图5.1l V-R-SDR和VPR430在不同电路块规模下的综合布线时间 Figure5.11 OverallComputingTimeforV-R—SDR andVPR430”.CircuitBlockSize 江南大学博士学位论文 图5.12 P.R.SDR和PathFinder在不同电路块规模F的综合布线时间 Figure5.120verallComputingTimeforP-R-SDRandPathFinder vs.CircuitBlockSize 图5.13 F-R-SDR和Frontier在不同电路块规模卜I的综合计算时间的标准误差 Figure 5.13 Standard Deviation ofOverall Computing Time for F-R-SDR and Frontier vs.Circuit Block Size 图5.14 V-R.SDR和VPR430在不同电路块规模F的综合计算时间的标准误差 ofOverall Figure5.14 Standard Deviation Computing Ttme for V-R-SDR and VPR430 vs.Circuit Block Size 第五章将布尔可满足性与几何查找相结合的混合布线算法 图5.15P.R.SDR和PathFinder在不同电路块规模下的综合计算时间的标准误差 Figure 515 StandardDeviation ofOverallComputingTimeforP-R-SDR andPathFindervs.CircuitBlock Size 图5.16六种算法的总体布线时间比较 Figure 5.16 Total Computing Times comparison for six algorithms 图5.17六种算法的综合布线时间的总体标准误差比较 Deviation Figure 5.17 Total Standard comparisons for six algorithms 江南大学博士学位论文 表5.2 P—R.SDR、V-R.SDR、F-R.SDR判定10个电路的不可布线性所需时间 Table 5.2 Computing Times for deciding the unroutability often circuits by P-R·SDIL V-R-SDR and F.R.SDR 将P.R.SDR、V-R.SDR和F.R.SDR应用于Xinlinx公司的XC4006E、XC2S200、 XC3064及Altera公司的F10K50都取得了良好的效果。因此新型算法的适用性很广 虽然目前20万门以内的FPGA布线技术已经相当成熟,其中PahtFinder、VPR430、 Frontier属于目lji『最为先进的布线算法,但是对于一些较复杂的电路,例如在基准电路 CLMA、PDC、sPLA上布线所耗时间过长且稳定性较差,新型混合算法可以有效的提 高布线速度及稳定性;另一方面,通过新型混合算法中结合了SAT基于布尔函数的布线 法R.SDR,可以更加精确有效的预测布线延迟,这是当前FPGA设计的主要研究方向之 5.5本苹小结 11描述了通过利用布尔可满足性得到的三种新型可布线性检测算法。这一方法与 以Iji『用于FPGA布线的常规几何查找御线算法的不同之处在于:它将基于SAT 的FPGA布线算法R.SDR嵌入三种几何查找布线算法PathFinder、VPR430、 Frontier。这一新方法的直接好处在于:(1)这种结合算法与单纯的布尔基于SAT 布线法相比具有更佳的可扩展性:(2)它通过布尔SAT技术准确判定可布线性, 解决了常规的几何查找布线算法的收敛问题:(3)新型的混合算法无论在布线 时l’日J还是布线稳定性上都有极大地提高。换句话说,结合算法(PathFinder、 VPR430、Frontier及R.SDR)相辅相成。实验表明相对于PathFinder、VPR430、 Frontier,P.R.SDR、V-R—SDR、F.R.SDR在布线时间上分别缩短了25%,29%, 32%,在布线稳定性上分别提高了29%,25%,24%。 2)从基于SAT布线的观点来看,R.SDR有能力对于每条二引脚连接线同时考虑多 条详细路线以判定布线任务的可行性。问题是对于每条二引脚连接线如何生成 理想的一组详细路线以检测可布线性。几何查找布线算法PathFinder、VPR430、 Frontier通过其优秀的拥挤度量,对于每条连接线,生成少量高性能的详细路线。 特别是对关键时序线网,可选择使用时序驱动布线法。 参考文献 【1】Nam G,Sakallah K Rutenbar R.Hybrid Routing for FPGAs by Integrating Boolean Satisfiability with Geometric Search.Intemational Conference on Field Programmable Logic and Alications,2002,9:360·369. 【2】 Nam G,Sakallah k Rutenbar R.A New FPGA Detailed Routing Approach Via Search.Based Boolean Satisfiability.IEEE Transactions on computer-aided design of integrated cireuits and systems,June 2002,21(6):674-684. 第五章将布尔可满足性与几何查找相结合的混合布线算法 『31 Nam G。Aloul F,Sakallah K气et a1.A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints.International Symposium on Physical Design,April 2001. 『41 SoIll(up J.Fast Maze Router.Proe.15th DesignAutomation Conf.,June 1978.100.102. 『51 Lee C.An Algorithm for Path Connections and its Applications.IRE 7Fansactions on Electronic Computers。1 961.9:346.365. 『61 Rubin F.111e Lee Path Connection Algorithm.IEEE Tram.Computers,1974,9:907—914. 『71 Soukup J.Fast maze router.in Proc.Design Automation Conf.,1978,6:100.102. 『81 Dijkstra E W.A note on two problems in connection with graphs.Numerische Mathematik 1959.1:269.271. 【9】 Swarm J.A Hi【gh Speed Tuning-Aware Router for FPGAs.Master's Thesis,Department ofElectrical and Computer Engineering.1998. f101 Placzewski M.Plane Parallel A‘Maze Router and Its AIication to FPGAs.DAC. 1992.691.697. f1 11 Mo F,Tabbara八Bmyton R.A Force.Directed Maze Router.Department of EECS, UniversityofCalifomiaatBerkeley.2001.11:404-407 『121 Browu S,Rose J,Vranesic Z G.A Detailed Router for Field Programmable Gate Arrays. 1EEE Transactions on CAD.May 1992.1 1(5):620—628. 【1 3】Lemieux G Brown S.A Detailed Router for Allocating Wire Segments in FPGA5. ACM/SIGDA Physical Design Wjrkshop.1993.4:215.226. f141 Brown S,Khellah M,Lemieux G Segmented Routing for Speed.Performance and Routability in Field.Programmable Gate Arrays. Journal of VLSI Design, 1996.4(4):275.291. 『1 51 Lee Y S。Alien C,Wu H.A Performance and Routability Drivefl Router for FPGAs Considering Path Delays。’’IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems。,February,199716r2):179.185. 『1 61 Wu Y L’Marek.Sadowska M.An E币cient Router for 2.D Field.Programmable Gate Arrays.European Design Automation Conf..1994.2:412-416. f171 Wilton S.Architectures and Algorithms for Field—Programmable Gate Arrays、】lrith Embedded Memories.Ph.D.Dissertation,University ofToronto.1997. 『l 81 McMurchie L,Ebeling C.PathFinder:A Negotiation.Based Performance.Drivffn Router Symposium for FPGAs.ACM/SIGDA Intemational on Field.Programmable Gate Arrays. ACM Press.New York NY。1995.12:1 11.1 17. 『191 Lemieux G,Browll S。Vranesic D.On Two.Step Routing for FPGAS.In Proceedings: Intemational Symposium on Phyileal Design.Napa,Ca..1997。4:60.66. 『201 Sechen C.VLSI Placement and Global Routing Using Sireulated Annealing.Kluwer Academic Publishers.Boston,Ma.1 988. [21]郭斌林,童家榕.一种基于扩展查询表的可编程逻辑单元叨.计算机学 报,2003,26(10):1372.1378. [22]Eheling,C,McMurchie,Hauck S A,et a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(1VLSI)。1995.12:473.482. 【23】Betz v,Rose J.VPR:A New Packing,Placement and Routin2 Tool for FPGA Research. Intemational Workshop on FPL.1997,7:213.222. 【24】Betz V,Rose J,Marquardt A.Architecture and CAD for Deep.Submicron FPGAs. 81 江南大学博士=学位论文 K/UWCI"Academic Publishers.Feb.1999. f251 Betz V.Architectures and Algorithms for Field.Programmable Gate Arrays.Ph.D. Dissertation。University ofToronto.1998. 『261 Betz V.VPR and T.VPack Uscr’s manual—version 4.30.2000. [27】Betz V,Rose J.FPGA Routing Architecture Segmentation and Buffeting to Optimize Speed and Density.Kluwer Academic Publishers.1 999. 『281 Betz V,ROse J,Marquardt A.Archilecture and CAD for deep.submicron FPG舡. Kluwer Academic Publishers.1 999. 【29】Eheling C,McMurchie L,Hauck S气et a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(TVLSI),1995.12:473-482. 【30】Li G.Heuristics and Experimental Design for Fpga Routing Algorithms.Master's thesis, University ofCincinnati,Computer Science.2001. 【3 l】Tessier R.Negotiated A。Routing for FPGAs.In Proceedings of the Fiilia Canadian Workshop on Field—Programmable Devices,Montreal,Quebec,Canada,1998,6:14·19. [32】Nilsson N J.Principles ofArtificial Intelligence.Tioga Publishing,Palo Alto,Ca.,1980. 【33】Nilsson N.Principles of Artificial Intelligence,Morgan Kaufmann,San Francisco CA, 1980. 【341 Swartz J’Betz V,ROse J.A Fast Routability.Driven Router for FPGAs.In 6th Intemational Workshop on Field.Programmable Gate Arrays, Monterey, C九 1998.2:140.144. 【35】Swartz J.A High—Speed Timing-Aware Router for FPGAs.Master’S thesis,University ofToronto,Departmem ofElectrical and Computer Engineering,1998.in preparation. [361 Tessier R.Fast Place and Route Aroaches for FPGAs.Ph.D.thesis,Massachusetts Institute ofTechnology,l 998. 『371 Tessier R.Negotiated A’Routing for FPGAs.In Proceedings of the Fiful Canadian Workshop on Field-Programmable Devices,Montreal,Quebec,Canada,1998,6:14-19. Syst.Tech…J 【381 Prim R.Shortest Connecting Networks and Some Generalizations.Bell 1957,36(6):1389.1401. 第六章将子集可满足性线与几何查找相结合的混台布线算法 第六章将子集可满足性与几何查找相结合的混合布线算法 6.1前言 在第五章,我们采用将一种基于线路的SAT算法R-SDR与传统的三种几何查找布 线算法相结合既克服了SAT算法在可扩展性方面有不可避免的局限性,又弥补了传统的 几何查找布线算法在可布线性判定方面的缺陷。实验结果表明,相对于传统的几何查找 布线算法,这三种算法处理大规模布线问题时在布线时间及其稳定性上都得到了极大的 提高。可以说这是用布尔满足性解决大型布线问题方法方面取得的重大突破。 然而,即使假设这一类有关SAT的方法能够不断快速的取得进展并且我们能够将大 型几何问题公式化为可解的SAT问题,但这些方法的总是存在着一个缺点,那就是他们 不支持局部方案,即SAT公式或者满足或者不满足而不存在中间方案。例如对具有1000 条线网的FPGA问题进行布线时,我们可能会对1000条线网中布通999条的方案感到 满意,但在一个SAT公式中,整个问题若不可完全布通,则SAT方案只是得出否定的 答案,而不是一个有用的999条线网的部分方案。 本章介绍一种。子集可满足性” (subset.satisfiability,sub.SAT)111的布尔SAT 公式,将一个具有N个变量的“严格”的SAT问题变换成一个新的“松弛”的SAT问 题,仅当在原始问题中的变量的不可满足个数不超过闽值k(k<<N)时,这一问题是可 满足的。针对所需的SAT松弛,给出了一种基于明确阈值及计数的变换。 然后将这种子集可满足性方法用于前面第五章中提出的混合算法,即将sub.SAT用 于R.SDRt2j'4】再分别与PathFindert5。1 01、VPR430t11‘1 51、Frontierll睨”相结合得到三种新型 混合算法。并将其用于不可布通的大型基准电路中。 6.2研究目的和方法 当在分析一个中等规模的过拥挤布线区时,例如对具有1000条线网的FPGA进行 布线时,假设这个FPGA布线问题本质上是不可布通的,但1000条线网中有999条能 被嵌入布线。在这种情况下,放弃这种“几乎可布通”的方案十分可惜。因此对于解决 这一类问题必须要有一个部分方案的SAT公式。 有两个强有力的论据说明了为什么部分方案是必需的。 (1)与传统布线法更协调。如果在实际中我们试图将SAT用于详细布线,部分方案将 与传统布线法的特征及流程更协调瞄埘J。目前布线采用的方法一般是:我们通过一系列 递增的尝试级逐步地进行详细布线。如果某些线网不能布通,则下一个尝试级通过消耗 一定的CPU时间来增强搜索过程的强度。若是早一点终止这一布线过程,就可以得到 某种部分布线方案。 (2)SAT型布线法L-I:JL何型布线法更加抽象1251。将几何形式转化为布尔约束条件的映 射过程必然将问题抽象化,这导致对某些未布尔约束化的几何方案造成精确度上的损 失。 事实上,1000条线网中只要有1条不能布线就意味着不能完成对几何约束条件的 SAT抽象。我们将尝试寻找把这l条不可布通的线网屏蔽的部分方案,而被屏蔽的线网 将可以采用其它布线方法或者外设的方法布通。 首要关心的是那些“几乎可满足”的部分方案:几乎所有的约束条件都可满足。假 江南大学博七学位论文 设用户给出了一个临界点k,用于说明有多少个约束条件可以违反,而k相对整个约束 条件数而言是十分小的。我们将原始的SAT问题转变成~个新的SAT问题,若这个新 的SAT问题是可满足性的则它对于原始任务产生一个适合的完备的部分方案。 在本文中,我们处理“不存在部分方案”的问题的方法是将原始的问题转化为一个 增广的松弛的SAT问题,仅当原始约束条件的一些小的任意子集不符合要求而其余的约 束条件都符合时,这一问题是可满足的。我们将此称为子集可满足性(subset. satisfiability),或简称为sub-SAT。 此方法主要思想是允许基于SAT方案的使用者设置生成不完整但有用的SAT方案 的阈值。其关键是找出通用的转换方法使产生的新的SAT问题能采用目前SAT工具加 以解决。 6.3通过变换及计数生成的sub.SAT 6.3.I基本公式 假设我们的SAT问题是采用标准的合取范式(CNF)公式化表示【24060_7l,这罩的每 个约束条件都是由多个文字(多个布尔变量的真值或其补值的实例)的一个逻辑加。用 这种形式构成的约束条件常被称为子句,当然这两种个术语可以替换使用。有5个变量 及4个子句的一个简单例子如下: 阮v丘v置)^∽v冠)v阮V墨vⅣ。)^k v墨) (6.1) 设一个常见的CNF子句包含M个变量{z.,x:,…,x。}。并且共有N条子句。 图6.1描述了我们所采用的部分方案的方法,并更精确的阐述了松弛SAT子句问题。 采用一种常规的紧致形式的公式,对于每个变量我们必定可以找出一种分配方法使每条 CNF子句都恒等于l。从数字逻辑的角度思考有助于理解CNF子句:我们必须满足每 一条子句,而检查所有子句的可满足性的器件仅是一个N输入与门。为了将CNF子句 松弛,我们将某些任意的不超过k个变量的子集脱离合取。从逻辑上讲,我们将单个与 门替换成允许屏蔽一个变量子集的新的逻辑形式,使得这些屏蔽变量满足与否对最终合 取形式没有影响。 如图6.1(b)所示,通过一个变量屏蔽位的“或”将其跨越。设置这样一个位自动使 得该子句能够被满足,并且生成了一个我们后面能计数的值。我们将这些称为被屏蔽的 约束条件。一个单独的逻辑部分决定了屏蔽约束条件数是否不超过任意一个阈值七。当 且仅当非屏蔽约束条件全部都是可满足的并且屏蔽(可能不满足)约束条件数不超过一 个任意阈值k时新的松弛后问题是可满足的。 图6.2显示了控制计数任务的逻辑块。由于我们假设了k(k<<Ⅳ)个脱离子句,因此 我们不需要一个庞大的加法器结构。我们采用了来自文献[28】的“within—k”线性计数 器电路的一种变体。每个∑,块本质上是一个增量编码器电路,在一个[109:(七+1)卜位值s. 块上运行。每个块记录下一个屏蔽位。一些附加的逻辑检测确保了我们的小计数器不会 被溢出。C,值分阶段逐步传递,这样就确保了我们最终的计数值小于或等于k。每一阶 ‘ 段的计算如下: 第六章将子集可满足性线与几何查找相结合的混台布线算法 l 矿 S=2№:(“H and mask.=1 C』 p。 else S “)矿0,<2晒出州1)and mask,=1 S h胎● H墨 。 else Clauses (6.2) maskm mask! masks 箪 (b) 图.6.1通过采用屏蔽及计数来扩张原始CNF形式的方法将子集可满足性公式化 (a)紧致形式的SAT公式;(b)松弛(扩张子句)形式的SAT公式 Figure 6.1 Formulating subset satisfiability by augmenting the original CNF form with masking and counting (a)Strict SAT formulation;(b)Relaxed(augmented CNF)SAT formulation 江南大学博£学位论文 秘…举…秘 Within-k counter:N blocks,1 per clause;Si=[I092(k+1)】bit sum. mask 图6.2作为阕值计数器的一个线性within—k结构(在图6.I(b)的左下角) Figure 6.2 Implementing the threshold counter(at bottom-left ofFig.6.1(b))as a linear within-k structure 在CNF公式中我们将这些增量编码器结构用附加子句表示。这些附加的屏蔽变量、 计数器变量,以及生成这一逻辑的子句扩充了最初的CNF表达式。将原始的CNF公式 松弛是因为这样相比原始的严格形式,它将允许采用更多的方案,但其代价是生成一个 较庞大的变形CNF公式。设s=[109:忙+1)1;一个详细的计算表明总的来说我们的扩充 将如下几项加入了CNF形式。 变量:我们加入N.G+2)个新的变量。对于公式中N条从句中的每一条,我们创 建了一个具有s.位和、1个屏蔽位及一个c.位的within—k计算器的一个进程阶段。 子句:我们增加了G+2)+(Ⅳ一1b+3+sG+3))+G+1)条新子句。第一项表示首个 within—k块,第二项表示剩余的Ⅳ一1个计数器块,而最后一项是指图6.2右侧最后的 比较器。 因此,在对原始的含M个变量、Ⅳ条子句的CNF公式的扩充中,我们增加了 o(Ⅳ109 Ji})个变量及O(Nl092 t J条子句。既然我们首要关心的是“几乎”可满足性问题, 我们期望k<<N。无论如何,松弛阈值k仍然决定着生成的扩充SAT公式的规模。 这一类型变换的主要优点在于这一松弛仅是另一个较大的SAT问题。考虑到布尔 SAT(CNF可满足性)上己取得的进步,这是一个重要的优点:因为我们能采用相同的 SAT工具。 处理这类问题其它可供选择的公式有最大化可满足性(MAX.SAT[29】)及其部分变 体130-32】,它们采用的方法是对约束用加权处理并搜索最大加权的可行子集。但是,在此 领域研究所取得的进展中还没有得到与布尔SAT具有相同成熟性、通用性及容量特性的 方法。 6.3.2一个布线实例 一个小型布线例子有助于说明我们采用的扩充CNF的详情,并能阐明其中细节。图6.3 显示了一个小型的未能完成的布线问题:三条线网竞争两条轨线,而仅有两条能嵌入布 线。例如,变量A0是指将线网A分配给路径0;A0则意味着该线网不在路径0上,等 等。我们设定一个松弛阈值k=l,并且试着解决这个仅有一条线网不能布线的问题。图 6.4显示了由松弛生成的CNF公式的扩充形式,这一扩充形式提出了新的变量及子句并 第六章将子集可满足性线与几何查找相结合的混台布线算法 给出了within一七计数器的一个简单表达式。值得注意的重要的一点是虽然在最糟糕的 情况下一个松弛可能增加o(Ⅳlog:k)个变量,但我们真正所需要的变量数由实际情况决 定。由于他们中任何一个都可能被松弛,因此不是所有子句都是均一的。这些复杂的问 题生成一个庞大的非均一的子句组。我们也许能够将某些子句松弛从而得到一个有用的 部分方案但对于其它的子句则不行。就象上面显示的那样,很明显我们只需要将3个子 旬屏蔽,以确保每条线网被分配给某一条轨线。(事实上,我们可以将所有这些子句都 屏蔽并得到相同的结果,但这么做是不必要的)。图6.5显示了满足这一松弛问题的结果: 我们找到了恰好仅有一条未能布线线网的方案。 3 nets,2track A B B ■■ 豳 l I 』 ~、———一/ 、——厂、、i—————、 ∥ ’ 鬻 圈一 厂] C A C A0 V B0 V CO V 、L,J 盅 n E叭n言|甜 e.Ⅱ n e 武饥 .呐;軎 l 0—A—0V—B—O 丛V坠l 1—A—OV—C—0\ 盟Ⅵ堕r BOVCO l B1 VCl I Ensure no net-net conflicts in any track 图6.3一个小型不可满足性布线例子及其相关紧致形式的CNF表达式 Figure 6.3 A small tmsatisfiable routing example and its associated strict CNF representation xA xB xC 黼AOVAl mask bits 鬻黼8”…翟Initialize∑A¥1111[1, s)澄VBOVBl 溺熬COVCl AOVB0 AlVBl AOVCO A1VCl BOVC0 ≥DA=O ≤娜≈cBVsA 鬃and overflow 礞罗R sum。 leB=eAV(x]3AsA);and overflow !sc剐cVsB 罐罗f sum, §eC=eBV(xCAsB)瑚and overflow ≥§eVsC i Comparator:check k曼1(trivial) ≥§Q;㈣测and overflow B1VCl 图6.4将上面的布线问题松弛以允许存在k=1个不可布线线网时采用的扩张CNF形式 Figure 6.4.Augmented CNF when above muting problem is relaxed to allow七=1 unrouted nets 87 江南大学博上学位论文 {xA,A0,AI,sA,cA}=(O,1,O,O,O} {xB,B0,BI,sB,ca}=(1,0,0,l,O) {xC,CO,C1,sC,cc}={O,l,0,0,O} 图6.5用扩张CNF形式生成恰好k=1条不可布线线网的部分布线方案的SAT方法 Figure 6.5 SAT solution for augmented CNF yields a partial muting with exactly k=1 unroute.,d nets (a)PathFinder or VPR430 or Frontier flow (b)sub-SAT routing flow 图6.6三种sub-SAT混合算法的综合流程图 Figure 6.6 Overall flow diagrams ofthree combined sub-SAT algorithms 6.4新型混合算法 第五章中提出的三种混合算法P—R-SDR、V-R.SDR、F.R.SDR虽然在扩展性及可布 线判定方面取得突破性进展,并且在布线时间及稳定性上得到很大的提高,但是对于那 些本身不可布通的电路却缺乏有效的手段。本文将子集一可满足性sub—SAT用于SDR 算法(简称sub.R.SDR)中,再分别与PathFinder、VPR430、Frontier三种几何算法相 船 第六章将子集可满足性线与几何查找相结合的混合布线算法 结合,生成的新型混合算法(简称P.sub-R.SDR、V-sub-R-SDR、F.sub-R.SDR)通过屏 蔽个别线网可以有效的解决存在少数不可布通线网的电路布线问题。 图6.6显示了这种新型混合算法的流程。左半边表示三种几何查找布线算法的流程 而右半边对应于sub-SAT布线流程。与图5.1相比较,其中的差别是将R-SDR算法部分 换成了sub.R.SDR。首先采用R.SDR方法将电路用一组CNF约束条件表示,求布尔函 数的值。如果找到了任何布线方案,则算法返回方案。否则,采用sub.SAT将这一组 CNF子句松弛,并设定一个闽值k将不可布线的线网屏蔽。若在设定时间内不可布通, 则执行几何查找算法的下一次迭代。 6.5实验结果及分析 为了评估我们在本章所提出的三种新型混合算法:P.sub.R.SDR、V-sub.R.SDR、 F.sub.R.SDR在解决存在少数不可布通线网的电路布线问题方面的有效性。我们对与第 二章中给出的布线基准中个别不可布通的布局进行布线。 对第五章的实验中三个基准中的10个不可布通布局(见表5.1)进行布线,表6.1 显示了布线结果。我们可以看出,原本不可布通的布局在屏蔽了1到3条线网后变得可 以布通。对比表6.1及表5.1可见从布线时间上来看,相对判断一个电路的不可布通性, 布通其所需时恻较长。图6.7形象的比较了两类混合布线算法花费的总体布线时间。由 表6.2可知,在总体布线时间上P-Sub—R—SDR、V-Sub—R.SDR、F.Sub.R.SDR分别为 P.R.SDR、V-R.SDR、F.R.SDR的1.74、1.79、1.76倍。这是因为每当遇到一条线网在 临界时间内不可布通,则需要将其屏蔽,然后继续布线算法的迭代,而在这一步采用之 前的算法仅能作出不可布通的结论。 由此可见,这种方法虽然能够有效的解决少量线网不可布通的电路,但其布线时间 也相应增加,尤其当用在原本可以布通的电路时,浪费了很多布线时间。克服这一缺点 将是今后我们工作的方向。 表6.1 P-sub-R-SDR、V-sub-R.SDR、F-sub-R.SDR及sub.R.SDR的综合布线时间比较 Table 6.1 Overall Computing Time Comparisons for P-sub-R-SDI乙V-sub-R·SDIL F-sub-R-SDR and sub..R.SDR 表6.2七种布线方法的总体布线时间比较 Table 6.2 Total Computing Times comparison for seven routing methods 江南大学博上学位论文 图6.7七种布线方法的总体布线时间比较 Figure 6.7 Total Computing Times comparison for seven routing memods 6.6本章小结 1)阐述了一种子集可满足性方法sub.SAT,描述其如何将一个任意的SAT问题的 CNF表达式转换为一个新的松弛了的SAT问题,它仅当公式中的某些k个条件 子句忽略时是可满足的。 2)将子集可满足性sub.SAT用于SDR算法中再与几何算法相结合,得到一种新型 混合算法,实验证明这种算法能够在屏蔽若干条线网后有效的将原本不可布通 的电路布通。这可以减少布线资源的浪费,提高FPGA的利用率。 3)虽然能够有效的解决少量线网不可布通的电路,但这种方法的布线时间相应增 加,尤其当用在原本可以布通的电路时浪费了很多布线时间,克服这一缺点将 是今后我们工作的方向。 参考文献 【11 Xu H,Rutenbar R A,Sakallah K.Sub.SAT:A formulation for relaxed Boolean satisfiability witll applications in routing.IEEE Transactions on Computer-aided Design ofIntegrated Circuits and Systems.2003.22(6):814.820. 【2】Nam G,Sakallah K Rutenbar R.Hybrid Routing for FPGAs by Integrating Boolean Satisfiability、ⅣitIl Geome砸c Search.Intemational Conference on Field Programmable Logic and AlicatiOIlS,2002,9:360-369. 【31 Nanl G,Sakallah K Rutenbar R.A New FPGA Detailed Routing Aroach Via Search.Based Boolean Satisfiability.IEEE Transactions on computer.aided design of integrated circuits and systems。June 2002.2lf6):674—684. 【41 NalTI G,AIOUl F,Sakallah K A,et a1.A Comparative Study of Two Boolean Formulations of FPGA Detailed Routing Constraints.International Symposium on Physical Design,April 2001. 【5】 McMurchie L,Ebeling C.PathFinder:A Negotiation—Based Performance·Driven Router 第六章将子集可满足性线与几何查找相结合的混合布线算法 for FPGAs.ACM/SIGDA International Symposium on Field·Programmable Gate Arrays. ACM Press.New York NY。1995,12:11 1.117. 【6】Lemieux G,Brown S,Vranesic D.On Two-Step Routing for FPGAs.In Proceedings: Symposium International on Physical Design,Napa,Ca.,1997,4:60—66. 【7】Sechan C.VLSI Placement and Global Routing Using Simulated Annealing.Kluwer Academic Publishers.Boston,Ma’1 988. 【8】Eheling C,McMurchie L,Hauek S~et a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(TVLSI),1995,12:473-482. [91 Betz V,Rose J.VPR:A New Packing,Placement and Routing Tool for FPGA Research. International Workshop on FPL.1997.7:213.222. f101 Betz V,Rose J,Marquardt A.Architecture and CAD for Deep.Submicron FPGAs. KIuwer Academic Publishers.Feb.1999. fl 11 Betz V Architecture¥and Algorithms for Field—Programmable Gate Arrays.Ph.D. Dissertation.University ofToronto。1998. 『1 21 Betz V.VPR and T-VPack Uset’S manual—version 4.30,2000. 『1 31 Betz V,Rose J,Marquardt A.Architecture and CAD for deep-submicron FPGAs. Kluwer Academic Publishers.1999. 【14】Eheling C,McMurchie L,Hauck S气ct a1.Placement and Routing Tools for Triptych FPGA.IEEE Transactions on Very Large Scale Integration(1VLSI)。1995,12:473-482. 【l 5】Li G,Heuristics and Experimental Design for Fpga Routing Algorithms.Master's thesis, University ofCincinnati.Computer Science.2001. 【16】周峰,童家榕,唐璞山.带时延约束的FPGA布线算法【J】.半导体学报,1999,20(9): 831.836. 【17】Nilsson N.Principles of Artificial Intelligence,Morgan Kaufmann,San Francisco C凡 1980. 『1 81 Swartz J。Betz V,Rose J.A Fast Routability.Driven Router for FPGAs.In 6th International Workshop on Field—Programmable Gate Arrays, Monterey.CA. 1998.2:140.149. 【19】Swartz J.A High·Speed Timing—Aware Router for FPGAs.M嬲ter's thesis,University ofToronto,Department ofElectrical and Computer Engineering,1998.in preparation. [201 Tessier R.Fast Place and Route Aroaches for FPGAs.Ph.D.thesis.Massachusetts Institute ofTechnology,1998. [211 Tessier I乙Negotiated A’Routing for FPGAs.In Proceedings of the Fifib Canadian Workshop on Field.Programmable Devices,Montreal,Quebec,Canada,1998,6:14.19. 『22]Bryant IL Graph-Based Algorithms for Boolean Function Manipulation.IEEE Trans.on Computers.1986.3:677-691. f231 Naln G。Sakallah K,Rutenbar R.Satisfiability.Based Layout Revisited:Detailed Routing of Complex FPGAs Via Search.Based Boolean SAT.Intl’Symposium on FPGAs.Feb.1 999. 1241 Silva J,Sakallah K.GRASP:A Search Algorithm for Propositional Satisflability.IEEE Trans.on Computers.Mav 1999.48(5):506.521. [251 A10ul F.Markov I.Sakallah K.Faster SAT and Smaller BDDs via Common Structure. ICCAD 2001.7:443-448. 【261 Beame P,Karp R Pitassi T,ct a1.The e佑ciency of Resolution and Davis.Putnam 垩堕查兰堡主兰竺堡苎 Procedure.to Ileal"in SIAM Journal on Computing.2002,4(3 n:1 048.1075. 【27】Brisoux L,Gregoire E,Sais L.Improving backtrack search for SAT by mealls of redundancy.FoundatiOIlS of Intelligent Systems.11tll Inu.Symp.,ISMIS’99.Warsaw. Poland,June‘99.Berlin,Germany:Springer 1999.11:301.309. 【28】Bryant R E.Symbolie Boolean Manipulation with Ordered Binary-Decision Diagrams. ACM Computing Surveys,September 1992.24(3):293.318. 【29】Cha B,1wama K Karnbayashi Y,et a1.Local search algorithms for partial MAXSAT.in Proc.14th Nat.Conf.Artificial Intell..1997.8:263.268. 【30】Brown C气Finkelstein L,Purdom P W.Backtrack searching in the presence of symmetry.(T.Mora,editor),Alied algebra,algebraic algorithms and error correcting codes,6th intl.conf.,Springer-Veriag,1988,6:99.1lO. 【3 l】Glenn Wood R.Routing for FPGAs via Boolean Satisfiabiliry.M.S.Thesis,DeDt.of ECE,Carnegie Melton University.May 1 996. 【32】Bemm L,Micheli G D.A survey of Boolean matching techniques for library binding. ACM Trans.Des.Autom.Electron.Syst.,1997。2f3):193.226. 附录AVPR布局与布线工具 附录A、,PR布局与布线工具 A.1VPR综合流程 VPR是个现今市场上最为流行的FPGA布局与布线工具之一。VPR基于新的模拟 退火(simulated annealing)布局算法和Pathfinde:协商拥挤布线算法,与其它FPGA布局布 线工具相比,在合理计算时间内产生了高质量的布局,减小了布线面积。VPR工具适用 于众多FPGA日标结构,已经被广泛应用于大量的FPGA结构研究工作中。其运行流程 如图A.1。注意:图中工具可以用实现相同功能的其它工具代替,选择准确的工具是至 关重要的。 具体步骤总结如下: ①使用SIS软件执行独立于工艺的电路的逻辑优化。 SIS是一种交互式时序电路综合和优化工具,给定一个时序电路的状态转换表或者 逻辑级描述,可以产生最佳网表。 ②使用Flowmap软件将通过逻辑优化的电路映射到查找表LUT和触发器FF,输出 由LUT和FF组成的.blif格式的网表。 Flowmap是一种基于LUT的FPGA深度最小化工艺映像算法,通过采用很多面积 优化技术大大减小了LUT的数目。与其它基于LUT的FPGA工艺映射算法相比, Flowmap7%降低了LUT网络的深度,50%减少了LUT数,且需要很短执行时间。 ③使用T-Vpack程序将LUT和FF聚合形成给定参数的逻辑块,并输出.net格式的 网表。 T-Vpack是一种聚合算法,它将LUT和FF聚合起来形成逻辑块,它的输入是由LUT 和FF组成的.blif格式的网表,输出是.net格式的网表。T-Vpack工具采用命令行方式调 用,调用方法是: t-vpack input.blifoutput.net-lut_size<int> 其中input.blif是输入网表文件,output.net是输出网表文件,可变参数lut size表示逻辑 块中LUT的尺寸。如果没有—lut size项,默认LuT尺寸为4。 ④使用VPR软件读取.net网表,并将电路布局布线到给定结构参数的FPGA结构中, VPR也可以对己存在的电路布局进行布线。VPR可以只执行全局布线,或者同时执行 全局布线和局部布线。VPR的输出包含布局文件、布线文件及各种统计信息,例如成功 布线电路每个通道所需最小线道数、总导线长度等。 VPR工具也采用命令行方式调用,调用方法是: vpr netlist.net architecture.arch placement.P routing.r【r-options】 其中,netlist.net是逻辑块组成的电路网表,architecture.arch描述FPGA结构。VPR将 最终的布局和布线分别输出到placement.P和routing.r中。另外,VPR工具存在大量布 局布线可变参数,可以根据实际需要设置。命令行中如果没有输入可变参数,这些参数 取默认值。 VPR可以以两种基本模式运行,第一种模式:VPR在FPGA上完成电路布局后, 为了找到成功布线电路所需最小线道数,重复执行布线,如果布线不成功,VPR增加每 个布线通道的线道数,重新执行布线,如果布线成功,VPR减小线道数再次布线,一旦 最小线道数找到,布线结束,VPR退出。第二种模式:指定通道宽度进行布线,VPR 只执行一次给定通道宽度的布线,如果电路布线成功,输出统计信息,否则,如果电路 江南大学博上学位论文 不能在给定通道宽度的结构上成功布线,VPR输出不可布线的信息。 电路 图A.1 VPR设计流程 Figure A.1 VPR design flow diagram A.2模拟退火算法 VPR所使用的布局算法为模拟退火算法,而布线所使用的方法为Pathfinder、 VPR430算法。其中Pathfinder及VPR430算法已经在本论文详细研究,下面具体介绍 模拟退火算法。 模拟退火算法是一种非确定的(nondeterministic)算法,它利用目前的方案,经过 迭代找出更有效的方案,其基本流程如图A.2。 图A.2中COST用来评估一个方案所需要的成本,所要求的是成本越低越好;而 ALTER会对某个方案稍微改变;PROB则是接受改变方案的机率,其方程式为: 附录AVPR布局与布线工具 .,.C...a..—-C— PRoB=e T 其中Ca、C、T都是算法内的参数。值得一提的是,当Ca小于C,也就是改变后的方 案优于原本的方案时,PROB的值会大于1。r表示目前系统温度,当温度越高时,接 受改变方案的机率越高,反之则越低,其值变化是根据退火进度表(annealing schedule), 图A.2所示T=T×口为指数冷却(exponential cooling)。当所接受新方案次数E到达Er 次时,r即进入下个阶段。 变量 图A.2模拟退火算法的综合流程 FigureA.2 Overall flow diagrams ofsimulated annealing 表A.1VPR的a值对应表 TableA.1 Listing ofa in VPR Fraction ofmoves accepted(心∽州) O.置8<mRⅢⅧ>≤O.09.696 0.15<足。Ⅲ≤O.8 胄d∞∞,≤0.15 a 0.5 0.9 0.95 0.8 在模拟退火算法下,初始化时方案的成本很高,经过一次次的迭代,温度慢慢降低, 所得出的方案会跟着迭代次数增加,越来越精炼,趋近某个区域最佳方案。 以下描述VPR布局方式的细节。 评估一个布局所需要的成本时,所使用的成本函数称为线性拥挤成本函数(1inear congestion cost function),其公式如下: 江南大学博t学位论文 一蕾,[器+丽bby(n)] 对于各个线网,6以与bOy分别表示该线网所跨越的工轴与Y轴范围方块(bo岫ding box),G。(疗)及e。(胛)为范围内x轴与y轴平均各个布线通道所包含的轨道数目。g(疗) 是补偿系数,用于补偿线网有三个以上的节点时所低估的成本,决定其值的方程式为 g(玎)=2.79+0.02616X(n一50) 其初始r值(T—initial)的产生方式如下:首先,为目标电路建立一个随机布局, 再对该布局内的组件做^‰出次一对一的交换(pair-wise swap),M,o出为FPGA内部组 件的个数,再计算该坼抛b个布局的标准误差,最后将T—initial设定为标准误差的20 倍。 预设的ET=10X(Nbto曲,)1 33,而退火进度表使用指数冷却,但口会随着新方案的接 受率(R一=naccepted)改变,对应的口值如表A.1。 ’‘evalutned 退火过程在温度r<竺等兰旦停止,M一为线网总个数,c为当前布局的成本。 主要工作与结论 主要工作与结论 本学位论文主要对FPGA布线算法的布线时间及稳定性进行了研究,得到以下主要 结论: (1)在相同的大规模基准电路上详细对比了四种几何查找布线算法:一种基本迷宫布 线算法Lee,一种基于协商的性能驱动的布线算法PathFinder,一种快速的时延 驱动的布线算法VPR430,一种协商A’布线算法Frontier。实验结果表明,由于 基本迷宫布线算法Lee的布线时问过长(总体布线时间及标准误差分别是 PathFinder 47倍及48倍)已经不胜任现今大规模的FPGA布线。而在对其余三 种电路的详细对比中可见:相比流行的PathFinder算法,在布线时间及稳定性上 VPR430分别提高了59.7%、4t.O%,而Frontier分别提高了86.9%、81.3%,因此 无论从整体布线时间上还是从布线稳定性上,三种算法从优到次的排序都是: Frontier、VPR430、PathFinder。 (2)在相同的大规模基准电路上详细对比了两种布尔基于SAT的FPGA详细布线法, 即基于轨线的公式T-SDR及基于路线的公式R-SDR。ToSDR具有同步嵌入网线、 可布线性判定(或评估)、灵活的公式化能力等主要优点。但对于一些大型基准 电路,在布线方案空间的可选择性过大,造成布线时间过长。与T-SDR相比, R-SDR将排他性布线约束条件仅仅通过2.文字CNF子句表示,能够产生更加紧 致的SAT实例,因而更加有效。对比实验表明,基于路线的公式R-SDR产生了 一种更容易评估可布线性的公式,T-SDR的布线时间及标准误差分别约是 R-SDR的31.4倍及36.8倍,因此R.SDR公式相比T.SDR公式缩短了布线时间, 极大的提高了布线稳定性。 (3)在相同的大规模基准电路上将R.SDR与几何布线查找布线算法PathFinder, VPR430,Frontier进行详细对比。实验结果表明R.SDR算法在布线时间及标准 误差上分别为PathFinder算法的120%、110%,VPR430的297%、186%及Frontier 的912%、587%。从布线速度及稳定性上看,R—SDR次于几何查找布线算法。 其主要原因是R.SDR是一种详细布线算法,受由不考虑其特性的全局布线法提 供的单一全局布线配置所约束。 (4)提出了将基于布尔函数的布线法R-SDR与目前最高水平的几何查找FPGA布线 算法:PathFinder、VPR430及Frontier,相结合的三种方法,即P.R.SDR、V-R.SDR、 F.R-SDR。这样,不仅克服了基于布尔函数FPGA布线算法的主要缺点,即可扩 展性问题,而且补偿了传统布线法的典型缺陷:布线顺序依赖性及不能证明不可 布线性。换句话说,这两种方法相互补充。实验结果表明与单纯的几何布线法 PathFinder、VPR430、Frontier相比,P.R.SDR、V-R.SDR、F.R.SDR分别节省了 CPU时间32.O%、28.9%、25.O%并在稳定性上分别提高了24.1%、25.O%、29.1%。 另外,还在三种算法P.R.SDR、V-R-SDR、F.R.SDR之间进行了比较,结果表明 与P.R—SDR相比,V-R.SDR及P.R.SDR分别能节省布线时间57.9%及85.5%, 在稳定性上分别提高了41.7%及82.5%。这是由于在布线时间及稳定性上 VPR430、PathFinder本身就优于PathFinder。因此F.R-SDR、V-R.SDR、P-R—SDR 的优劣顺序与Frontier、VPR430、PathFinder十分相似。 (5)基于SAT方法的存在不支持局部方案的固有缺陷,即能满足大部分但不是所有的 约束条件都能用SAT形式表示。一种用于“子集可满足性”的布尔SAT公式 (sub.SAT)可以有效的解决这一问题。提出了将一种子集一可满足性方法 sub.SAT用于SDR算法中再与几何算法P.R.SDR,V-R.SDR及F.R.SDR相结合, 江南大学博上学位论文 得到三种新型混合算法F-Sub-R-SDR、V-Sub—R.SDR、P—Sub.R.SDR,实验证明 虽然在布线时间上F-Sub-R.SDR、V-Sub.R—SDR、P.Sub.R.SDR分别为P.R-SDR、 V-R.SDR、F-R.SDR的1.76、1.79、1.74倍,但其能够在屏蔽若干条网线后有效 的将原本不可布通的电路布通。这可以减少布线资源的浪费,提高FPGA的利用 率。因此在从总体上来看对FPGA的布线是十分有用的。 论文创新点 论文创新点 (1)提出了一种将基于路线的布线方法R-SDR与几何查找FPGA布线算法VPR430 相结合的混合布线算法V-R.SDR。不仅克服了基于布尔函数FPGA布线算法的主 要缺点,即可扩展性问题,而且补偿了传统布线法的典型缺陷:布线顺序依赖性 及不能证明不可布线性。与单纯的几何布线法VPR430相比,V-R—SDR在布线时 间及稳定性上有了显著提高。由于在布线时间及稳定性上VPR430本身优于市面 上最为流行的PathFinder布线算法(vPR399采用的算法),因此相应的混合算法 V-R.SDR优于P.R.SDR(RoSDR与PathFinder相结合的算法),提高了布线速度 及稳定性。另外由于VPR430是VPR399的改进版本,因此V-R-SDR可以在 P.R-SDR的基础上改进,实现十分方便。 (2)提出了一种将基于路线的布线方法R.sDR与几何查找FPGA布线算法Frontier 相结合的混合布线算法F.R-SDR。同样不仅克服了基于布尔函数FPGA布线算法 在可扩展性上缺点而且补偿了传统布线法在布线顺序依赖性及不能证明不可布 线性上的缺陷。与单纯的几何布线法Frontier相比,F.R-SDR在布线时间及稳定 性上有了显著提高。由于在布线时间及稳定性上Frontier本身优于VPR430及 PathFinder,因此在三者与布尔可满足性算法相结合的混合算法P.R-SDR、 V-R.SDR、F.R.SDR中,F.R.SDR在布线时间及稳定性上最佳。 (3)提出了一种能有效解决电路中存在少数线网不可布通问题的方法:将一种子集可 满足性方法sub.SAT用于R.SDR算法中再与几何查找布线算法PathFinder、 VPR430及Frontier相结合,得到三种新型混合算法P-Sub—R-SDR、V-Sub·R—SDR、 F.Sub.R.SDR,实验证明虽然在布线时间上P-Sub—R-SDR、V-Sub-R—SDR、 F.Sub.R.SDR分别相比P.R.SDR、V-R.SDR、F—R.SDR稍长,但其能够在屏蔽若 干条网线后有效的将原本不可布通的电路布通,这可以大大减少布线资源的浪 费,提高FPGA的利用率。因此在从总体上来看这种新型混合算法对FPGA的布 线是十分有效的。 江南大学博t学位论文 后续工作与展望 (1)将子集可满足性sub.SAT用于SDR算法中再与几何算法相结合得到的一种新型 混合算法,虽然能够有效的解决少量网线不可布通的电路,但这种方法的布线时 间相应增加,尤其当用在原本可以布通的电路时浪费了很多布线时间。如果能够 在采用混合算法之前判定电路是否可御通就可以避免出现这种情况。因此找到一 种能够短时间内先行判定电路的可布通性的布线算法十分诱人。 (2) 由于基于查找的布尔SAT方法的特性,任何可行的布线方案都必须采用查找的方 式获得。这是因为用该方法产生的布线约束条件布尔函数所表述的方案中,不存 在那个有优先的特性。通过在布线约束条件函数上附加一个优先布尔表达式,我 们相信能够获得更高质量的布线方案。例如,一个显著的应用是在时序方面,对 于时序起关键作用的线网,我们优先选择较短的连线。如何能将这样有关时序的 信息在当前的布尔约束条件公式中体现出来,而不降低方案查找性能,这将是我 们今后研究的方向之一。 100 攻读博士学位期间发表的论文 攻读博士学位期间发表的论文 1.Zhan Lh Zongguang Yu,Xiaofeng Gu.A New and E伍eient Algorithm for FPGA Routing. the 2nd IEEE Conference on Industrial ElectroniCS and Applications(ICIEA 2007).(已录用). 2.刘战,须自明,王国章,于宗光.高阶紧致差分与ADI结合的器件模拟方法. 固体电 子学研究与进展(EI核心库期刊),2006,26(2):230-233. 3.刘战,于宗光,王国章,须自明.一种用于FPGA的新型混合布线算法.电子器件(El 核心库期刊).(已录用). 4.刘战,须自明,王国章,于宗光.3.D寄生电容的高阶紧致差分格.电子器件(EI核心 库期刊)(已录用). 5.刘战,须自明,王国章,于宗光.一种基于迷宫算法的有效FPGA布线方法.微计算 机信息(中文核心期刊),(己录用) 6.刘战,王国章,须自明,于宗光.一种用于FPGA布局的模拟退火算法.微计算机信 息(中文核心期刊),2007,23(2):184.186. 7.刘战,须自明,王国章,于宗光.适于半导体器件模拟的高阶紧致差分方法.第十届 计算机工程与工艺学术年会,2006(1). 8.于宗光.刘战,王国章,须自明.适于薄膜SOl RESURF器件击穿电压模拟的高阶 紧致差分格式离散的ADI方法.半导体学报,2006,27(2):354—357. 101 江南大学博士学位论文 参与的科研项目 研究课题1:0603NJ0004一JS30“现场可编程门阵列 达到水平:已经通过用户使用,反应良好 研究课题2:0529NJ0008--JSl032专用译码电路 达到水平:已经通过鉴定,达到国内领先水平。 研究课题3:系统集成芯片(SOC)中IP模块的功能设计鉴定技术 达到水平:准备验收 科研成果奖励 获得中国电子集团第五十八研究所2005年技术基础研究成果优秀奖 致谢 致谢 古人言:师者,所以传道、授业、解惑也。本论文自始至终都是在我的导师于宗光 教授的悉心指导下完成的。论文的选题、研究方案的设计、试验结果的分析以及论文的 撰写都倾注了导师大量的心血。几年来于老师不仅在学习和科研工作中给予无私的指导 和辛勤的培养,而且在生活上给予极大的关怀和帮助。恩师宽宏的胸襟、渊博的知识、 严谨的治学态度、诲人不倦的人梯精神、管理有方的行政经验将指导我今后的人生道路。 多年来恩师在学术方面和做人方面所给予的教育和影响将使我终身受益,在此表示深深 的敬意和衷心的感谢。 在课题开展和论文撰写等过程中,得到了课题组王士同教授、顾晓峰教授、薛忠杰 教授、封晴总工、黄嵩仁高工、魏敬和高工的关心、帮助和支持,在此表示衷心的感谢。 感谢中国电予集团第五十八研究所各位领导和职工们等给予我的帮助和指导。 感谢王国章、须自明、臧佳锋、唐玉兰、万书芹等同学及虞志国高工、刘明峰高工 在这几年时间里给予的关心、帮助与理解。感谢课题组的所有师弟、师妹在学习期间所 给予的诸多方便,与他们一起度过的岁月令人留恋。 最后,还要特别感谢养育我的父母双亲,特别感谢亲人们对我的理解和帮助,这将 是我永远前进的动力。在此衷心祝愿他们身体健康,生活幸福。 感谢所有关心、帮助和支持过我的人。艰辛的播种和耕耘,总有收获的时候。在完 成这篇论文时,我真诚地想起他们,由衷的感谢他们,深深的祝福他们,祝他们健康、 快乐,祝他们一生平安。 103 几种用于FPGA的新型有效混合布线算法 作者: 学位授予单位: 刘战 江南大学 相似文献(10条) 1.期刊论文 张良庆.宋开臣.ZHANG Liang-qing.SONG Kai-chen 基于双DSP和FPGA的导航处理系统设计 -机电工程 2010,27(5) 机电技术的发展为惯性测量系统的大量应用奠定了基础.针对深海导航应用场合,为了提高深海惯性导航的精度和实时性,设计了基于双数字信号处理 器(DSP)和可编程逻辑门阵列(FPGA)的捷联惯性导航计算机,成功构建了低成本、小型化的捷联惯性导航系统(SINS).重点描述了双DSP和FPGA导航计算机 的硬件设计思路.扼要介绍了系统软件的框架结构.与目前大多数的惯性导航系统相比,该系统体积小、重量轻、功耗低,适用于运算复杂的嵌入式惯性导 航系统.实验室车载实验结果证明了上述设计的正确性和可行性. 2.学位论文 徐新民 FPGA资源动态重构及低功耗研究 2007 随着可编程逻辑门阵列(FPGA,Field Programmanle Gate Array)应用的不断普及,便携式设备和无线设备的涌现,过去对于FPGA主要关心的速度、 单片容量、费用以及可靠性等,现在对于低功耗FPGA的需求,与速度、容量、费用等到了一样的高度,成为FPGA设计者和使用者主要关心的问题之一。 功耗分析和优化是FPGA低功耗分析的两大主要问题。功耗分析主要关心如何准确估计设计过程中的能量消耗,确保设计不违反设计要求的功耗指标 ,关于VLSI功耗估计方法和 EDA工具较多,本文是针对可编程逻辑而有所不同,本文主要研究FPGA的静态重构和动态重构的功耗问题,以及FPGA布局布 线的面积利用率提高而间接对功耗的影响。 本文的主要工作如下: 首先分析了CMOS电路功耗的组成和相应的功耗模型,总结了功耗估计的静态方法和动态方法。 其次,分析了FPGA架构,动态可重构机理。利用传统模拟退火算法对FPGA进行布线轨道分布的研究,利用布线轨道在FPGA内部的不同分布,考察对 于FPGA实现逻辑占用面积的影响,来达到低功耗的目的。 第三,将先进的FPGA结构与高效的低功耗方法结合起来,经过分析和实践,建立电容模型,再成功利用统计方法,实现FPGA资源重构的低功耗估算 方法。设计人员可以根据估计结果,修改设计。通过设计专门的利于降低功耗的电路模块,以减小电路的功耗。 第四,通过对于FPGA资源动态重构的分析,修改对于静态使用FPGA重构低功耗估算框架模型,提出一种适合FPGA资源动态使用的低功耗模型,实现 了动态重构的FPGA的低功耗计算方法。 由于此方法与FPGA的体系结构紧密结合相连,在整个的方法中,无疑也给FPGA体系结构方面提供许多新的思路、建议和指导。进一步在论文的最后 对以后的工作和有待解决的问题也提出讨论。 3.期刊论文 张丹.胡旭东.ZHANG Dan.HU Xu-dong 一种基于FPGA的并行通讯模块的实现 -机电工程2010,27(5) 针对横机控制系统内部存在高速、海量的数据通讯的特点,利用可编程逻辑门阵列(FPGA)丰富的逻辑资源,构造了一个双口RAM并行通讯模块,设计了 配套的通讯协议,并对双口RAM存储空间进行了划分.研究结果表明,该模块具有通讯效率高、集成度高和通用性强的优点.实际应用结果表明,该模块完全 满足横机控制系统的通讯要求. 4.期刊论文 冯俊威.蒋志翔.FENG Jun-wei.JIANG Zhi-xiang 面向屏幕拼接的数字视频插值算法及FPGA实现 -计算 机工程与设计2009,30(22) 针对多屏幕拼接显示系统中高分辨率、高清晰、低失真的显示需求,提出了一种基于FPGA实现的实时视频处理算法.在介绍了DVI接口屏幕拼接显示的 系统结构及FPGA算法的主要功能后,针对算法处理对象具有视频像素流的特点,重点讨论了实时数字视频像素流的分割算法和基于滑动窗口的插值放大算 法的实现.实验结果表明,该算法能够满足屏幕拼接显示的需求. 5.期刊论文 龙昭华.王国锋.雷维嘉 RS-CC的级联编码设计及其嵌入式FPGA实现 -计算机工程与设计2009,30(23) 分析了802.16e无线通信系统,针对设计过程中经常出现的数据信息不同步问题,提出了一种基于RS(64,48,8)+CC(2,1,7)+交织的级联编码设计方案 .该方案利用功能模块化的设计理念,达到了在不增加译码复杂度的情况下实现有效而可靠的通信.通过将各级编解码模块化,利用FPGA技术实现了整个级 联纠错编译码系统.实验结果表明,模块化的FPGA嵌入式设计不仅提高了系统的稳定性,还大大缩短了开发周期. 6.期刊论文 崔俊杰.郭宏.CUI Jun-jie.GUO Hong 基于FPGA的实时数据采集与远程传输系统设计 -数据采集与处理 2005,20(3) 针对CT机扫描过程中对数据采集的快速性和传输的精确性的严格要求,提出了一种基于可编程逻辑门阵列(FPGA)技术的实时数据采集与远程传输的设 计方案.该方案采用了ARM+FPGA的体系结构,利用FPGA实现了数据采集、缓冲、格式转换、前向纠错编码和HOTLink传输控制等实时信号处理的线性流水阵 列,并在数据链路的物理接口和远程传输的精确度保障等方面提出了可靠的解决方法.同时,给出了一种利用FPGA进行高速高精度模拟量采集的方法.该方 案成功地应用到通用电气公司某型号CT机中. 7.期刊论文 严家明.李菁.YAN Jia-ming.LI Jing 基于FPGA的指示空速测量系统的研究 -传感器与微系统 2010,29(2) 介绍了一种基于现场可编程(逻辑)门阵列(FPGA)的指示空速测量系统的设计与实现,阐述了该测量系统的工作原理和硬件与软件设计.针对指示空速 与动压的函数关系式,提出了基于插值法逼近的系统设计方案,逼近函数的相对误差小于0.1%.此外,基于FPGA的硬件平台具有很高的计算速度和准确性.测 试结果表明:系统性能稳定,效率好,精度高,优于传统的测量装置. 8.期刊论文 商尔科.李健.安向京.SHANG Er-ke.LI Jian.AN Xiang-jing 一种面向FPGA的快速Hough变换 -计算机 工程与应用2010,46(7) 在FPGA上设计并实现了一种用于直线检测的快速Hough变换方法.使用分类滤波器把直线目标分成多个方向,使多个方向上的运算在空间上实现了并行 处理;在每个方向上,设计实现了一种用于Hough变换的流水线处理结构;提出了一种基于直方图统计的两阶段搜索算法.大量的实验验证了提出的Hough变 换实现方法的可行性,结果证明该方法占用空间少,实时性高. 9.学位论文 郑晓 基于FPGA的B-DOFS实时数据采集远程控制系统 2006 针对“基于布里渊的分布式光纤传感器”(B-DOFS)的研制过程中对数据采集的实时性和传输的精确性的严格要求,提出了一种基于可编程逻辑门阵 列(FPGA)技术的实时数据采集与远程传输的设计方案。该方案采用了ARM+FPGA的体系结构,利用FPGA实现了数据采集、缓冲、降噪处理、传输控制等实 时信号处理的线性流水操作,并将Linux操作系统应用到基于ARM9的嵌入式数据控制系统完成数据远距离传送。本论文先阐述了基于FPGA的数据处理子系 统的各个模块和相互关系,访问方式,地址分配情况等,然后从软件编程的眼光,进一步分析了在Linux环境下如何实现对FPGA子系统的驱动设计,主控 制程序,服务进程的设计及其三个软件模块之间的交互方式等。为了实现FPGA子系统与ARM子系统之间的快速数据搬运,本系统把FPGA子系统挂接到 ARM总线上,并设计了一种自定义的总线应答协议,来实现两者之间的通信和大数据量搬运问题。本系统通过TCP/IP提供数据服务,并采用了ActiveX控 件的形式发布客户端软件,使得客户可以方便的通过IE浏览器远程访问和控制传感器的工作。 10.期刊论文 李伟.陈明.杨恒.LI Wei.CHEN Ming.YANG Heng 基于ARM的嵌入式系统中FPGA配置方式研究 -计测技 术2006,26(3) 介绍了基于SRAM LUT结构的FPGA的几种在线配置方式,同时给出了在嵌入式系统中利用ARM7TDMI微处理器产生FPGA配置时序的方法;给出了最小系统 应用电路;结合程序,分析如何产生FPGA的配置时序;本方案的实用性在本文得到充分说明. 本文链接:http://d.g.wanfangdata.com.cn/Thesis_Y1195855.aspx 授权使用:北京理工大学(北京理工大学),授权号:f37d736c-7593-49b5-95c1-9e2e000eacca 下载时间: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); }) })