论文部分内容阅读
随着集成电路的快速发展,FPGA的规模不断扩大,FPGA芯片的复杂性也随之日益增加。因此给电子设计自动化工具(EDA)带来了更大的挑战。布局是FPGA自动化中的关键一环,它的主要功能是确定逻辑元件在芯片中的物理位置。布局的主要作用就是在优化目标下将综合产生的网表文件中的逻辑单元一一映射到FPGA芯片的实际物理坐标上。线长与芯片的功耗,时延,性能等都密切相关,如何在花费较少时间内减少互连线总长度,同时保证布局质量是布局算法需要考虑的关键问题。本文考虑到布局算法的运行时间及布局质量,通过对目前主流的FPGA布局算法的研究分析,做了如下主要工作:(1)通过对几种算法的优缺点的比较,针对现代FPGA逻辑资源种类多且复杂的结构特点,在局部装箱网表基础上建立布局逻辑单元,与传统的全装箱网表相比,即保证了特定逻辑的固定组合,又不至于降低布局可行解的数量。相对于物理坐标系的概念,建立了逻辑坐标系,对不同类型的逻辑单元进行分层处理。(2)基于XILINX Virtex-5系列的芯片架构,提出了一种快速布局组合算法。将二次解析式算法与模拟退火算法相结合,根据两种算法的优点,将两种算法分别应用于全局布局和局部的优化过程中。以总线长为优化目标,对传统的二次解析式算法进行改进,通过添加伪固定点作为力矢量,产生伪线网,从而对需要移动的逻辑单元产生一个拉力,并根据虚拟边界平滑移动实现模块的扩张伸缩的二次解析式算法完成全局布局,将逻辑单元在芯片中快速展开并允许逻辑模块之间有少量的重叠,然后通过对全局布局的结果进行广度搜索,对那些少量的重叠或者信号不匹配的不合法逻辑单元进行合法化处理。(3)利用低温模拟退火算法实现BLE级别的局部优化,与传统的模拟退火算法相比,本文算法直接从低温开始,并缩短了邻域解搜索的交换半径,加快了退火速度。同时引入模拟回火的过程,允许温度上升,增加了低温搜索的范围及次数,能更接近于全局最优解。实验结果表明,该算法与仅使用模拟退火和二次解析式算法相比的质量更高,速度相对模拟退火也更快,在时间和性能上能得到很好的权衡,并能有望运用到实际工业上。