论文部分内容阅读
现场可编程门阵列(FPGA)是一种包含有可配置逻辑模块和布线模块的数字集成电路,它支持可编程重复配置,并且节省了流片时间和费用,因此以灵活、风险低、开发周期短等优势在通信、工业控制、汽车电子、数据处理、消费电子等领域得到了广泛应用。然而,随着FPGA内部可配置资源容量的增加,对应的计算机辅助设计(CAD)工具也需要升级和优化。随着设计复杂程度的提高,将一个设计配置到FPGA上往往需要CAD工具计算很长时间(如数小时)方可满足各种参数要求。布线阶段通常消耗整个CAD流程近30%的时间,因此,高效的布线算法对缩减整个FPGA开发流程的时耗和满足各种约束条件至关重要。当今广泛采用的FPGA布线算法主要包括基于几何查找的布线算法和基于布尔可满足性(SAT)的布线算法;两者各有优缺点。基于几何查找的布线算法均由基本迷宫(Maze)算法演化而来,它虽然可经过优化提高布线速度,但由于一次只能布一根线,可布线性较难确定,通常依靠设定运行时间上限来实现算法终止。另外,其它由迷宫算法优化而来的各种几何查找算法也均存在依赖布线顺序的缺点。相比之下,基于SAT的算法由于可同时给所有线网布线,因此能从理论上证明可布线性。但是,这种算法需要大量变量和约束条件公式,所以可扩展性并不好。最近,一种基于伪布尔可满足性(PB-SAT)的布线算法成为FPGA布线算法的研究热点。和布尔SAT算法类似,PB-SAT算法可同时给所有线网进行布线,因此也能准确判断可布线性。和布尔SAT算法不同的是,它将约束条件用精简的表达式予以表示,需要的布线变量和式子大大减少,因此显著降低了内存需求,提高了扩展性。但是,PB-SAT算法在布线速度上仍然慢于传统的几何查找算法。为了吸收几何布线算法和伪布尔布线算法的优点,本文又提出了一种新型的混合算法(P-PB-SAT)。下面归纳本文的主要研究工作和结论。?介绍了FPGA的特点,并与专用集成电路(ASIC)进行了比较;分析了常见的FPGA编程工艺、架构及特点;在此基础上确定了采用Xilinx的岛状FPGA架构作为研究的布线对象。?详细介绍和比较了三种几何算法,即Lee迷宫算法、A*算法和基于协商的性能驱动的布线算法Pathfinder;分析了两种基于布尔SAT的详细布线算法,即基于轨线的详细布线SAT算法(T-SDR)和基于路线的详细布线SAT算法(R-SDR)。实验结果表明,在总布线时间和稳定性方面上R-SDR略弱于Pathfinder,分别为Pathfinder的117.9%、0.901倍。然而在不可布线的电路布局基准上,R-SDR能够准确判定可布线性,而Pathfinder则不能。?研究了最新的PB-SAT布线算法,并在约束表示方面和布尔SAT算法进行了比较。实验结果表明,PB-SAT算法在布线时间和稳定性方面的表现处于R-SDR和Pathfinder之间:PB-SAT算法在总时间上分别是R-SDR的89.5%和Pathfinder的105.5%;在总体稳定性方面,PB-SAT分别为R-SDR的1.042倍和Pathfinder的0.939倍;PB-SAT判定不可布线的总时间为R-SDR的91.9%。?最后,基于PB-SAT和几何算法的结合,提出了P-PB-SAT新型混合算法。实验结果表明,P-PB-SAT算法在时间和稳定性上都优于Pathfinder、R-SDR、PB-SAT。在总布线时间上,P-PB-SAT分别为Pathfinder、R-SDR和PB-SAT的55.3%、47.4%、52.5%;在稳定性方面,分别为三者的1.65、1.83、1.76倍;P-PB-SAT判定不可布线的总时间分别为PB-SAT和R-SDR的88.2%、81.0%;证明了该新型混合算法的高效性。