论文部分内容阅读
随着电子科技的迅速发展,集成电路得到大规模应用。现场可编程门阵列(FPGA,Field-Programmable Gate Array)作为可编程逻辑器件得到了广泛的应用,同时要求FPGA有一个较小的设计周期,才能跟上科技的进步。FPGA的设计流程中一个重要的环节就是布局,FPGA布局位于工艺映射和布线之间,是一个承上启下的过程,对最终的线长、CPU运行时间、时序等布局结果都有着重要的影响。本文主要对适用于FPGA的布局算法进行研究,在研究分析基础上实现三种布局算法。FARPLACE布局算法采用二次线长加扰动节点的力矢量法(FARPLACE)来完成布局,对芯片内可移动单元加扰动节点,使可移动单元受外力作用移动到芯片内新的位置,达到布局的效果,完成了对线长模型和密度模型进行研究设计,当用户设计输入比较复杂时候此算法布局的结果性能不是很好。因此,在FARPLACE算法基础上完成基于FARPLACE多层次布局算法(MFARPLACE)研究与设计,多层次算法根据单元之间的连接强度对单元进行打包,把所有打包看成一个单元进行布局,迭代FARPLACE布局流程就可以获得更好的布局结果。上述两种算法对线长和密度分步进行优化,由于线长和密度的相关性,导致不能同时获得很好的布局效果,另外,上述两种算法需要增加额外的节点会使得算法复杂度增大,而NTUPLACE布局算法把线长和密度通过加权来构造代价函数,并利用共轭梯度算法来找到最优解,避免了增加额外节点的复杂过程,通过同时优化两个目标来获得更好的布局结果。布局算法的实现基于FPGA的建模,我们使用建模语言对所要使用的FPGA进行建模,主要包括层次模型设计、结构模型设计、实现模型设计和目标模型设计;接着就是对布局算法的实现,在开源FPGA开发平台Fab上利用C++编程语言分别实现三种布局算法,在实现的每一种算法的软件上对线长、布局时间、布线时间和时序等进行测试比较,得出NTUPLACE布局算法具有最好的布局特性这一结论,将此布局算法投入到FPGA支持软件流程当中供用户使用。本文完成了FPGA建模,此建模方案的完整性使得FPGA支持软件得以实现;对线长和密度共同优化来实现布局算法是一个重大突破,使得支持软件布局流程具有更好的效果,对FPGA芯片的发展奠定基础。本文的创新点有两个:完整的FPGA建模方案,此方案的完成,使得FPGA支持软件的实现成为可能;布局算法的采用线长和密度同时优化,对于之前的线长和密度分别优化的方案是一个突破,而且布局效果较之前有很大的改善。