一种优化时序的FPGA布局布线方法

专利主权项内容

1.一种优化时序的FPGA布局布线方法，其特征在于，执行以下步骤：1)用布局器对簇级网表中的簇进行初始布局，并完成温度以及交换半径的初始化；2)布局器进入内循环，将簇级网表中的簇进行关键度标记；根据选择策略选择一个簇，并按照移动策略将其移动到任意位置，若该位置为空则直接移动到该位置上，否则，将选择的簇以及该位置上的簇互换位置；布局器遍历当前簇连接的所有低扇出线网，找到其中延时最大的路径对应的引脚，将其时序关键度作为簇关键度，所述簇关键度由组成该簇的相关路径中的路径关键度最大值确定；簇的选择策略为以λ的概率选取位于簇关键度大于crit1的簇，(1-λ)的概率从簇级网表中随机选取。式中，clusters为簇级网表中所有的簇，crit_clusters为簇级网表中簇关键度大于crit1的簇；布局器根据交换函数判断是否允许本次移动；交换函数由时序代价和线长代价两部分组成；时序代价为电路中所有路径的预估延时；线长代价为电路中预估消耗的总线长；当内循环达到设置的次数时，结束循环；当外循环温度降到预设值时，结束循环，并生成含位置信息的簇级网表；3)布线器根据步骤2)生成的簇级网表构建布线资源图；布线资源图由节点以及节点之间的线组成。布线资源图通常包含多条路径，每条路径由一个或多个节点和线组成。4)代价标记，依次更新节点代价值及路径关键度；5)拆线；拆线时拆除拥塞节点、路径关键度低于普通路径下限crit_n的路径上的节点以及会造成关键路径延时增加的路径上的节点；6)重布线；对未布线的线网进行布线；布线器以节点代价为依据使用Dijkstra算法在线网边框内进行布线；7)判断是否拥塞；是，回步骤4)；否，完成布线，生成含有布线信息的电路网表；所述节点代价是指由该节点的历史拥塞、基本成本以及该节点当前成本构成；所述路径关键度的大小依据与延迟高低成正比。