论文部分内容阅读
采用现场可编程门阵列(FPGA)可以快速实现数字电路,但是用于生成FPGA编程的比特流文件的CAD工具在编制大规模电路时常常需要数小时的时间,以至于许多设计者甚至通过在给定FPGA上采用更多的资源,或者以牺牲电路速度为代价来提高编制速度。电路编制过程中大部分时间花费在布线阶段,因此有效的布线算法能极大地减少布线时间。许多布线算法已经被开发并获得应用,其中布尔可满足性(SAT)布线算法及几何查找布线算法是当前最为流行的两种。然而它们各有缺点:基于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的详细布线公式,即基于轨线公式(T-SDR)和基于路线公式(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的布线时间及布线时间标准误差分别为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、VPR430、Frontier相比,P-R-SDR、V-R-SDR、F-R-SDR分别节省了CPU时间32.0%、28.9%、25.0%,并在稳定性上分别提高了24.1%、25.0%、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<<N)个不可满足时,这一问题是可满足的。将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布线的十分有效的新算法。