虫虫首页| 资源下载| 资源专辑| 精品软件
登录| 注册

您现在的位置是：虫虫下载站 > 资源下载 > 学术论文 > 几种用于FPGA的新型有效混合布线算法

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

  • 资源大小：3406 K
  • 上传时间： 2013-05-18
  • 上传用户：wzy1
  • 资源积分：2 下载积分
  • 标      签： FPGA 布线算法

资 源 简 介

采用现场可编程门阵列(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<

相 关 资 源

您 可 能 感 兴 趣 的

虫虫下载站版权所有 京ICP备2021023401号-1