一种基于最大独立集的面向FPGA布线优化布局方法

本发明公开了一种基于最大独立集的面向FPGA布线优化布局方法，它包括以下步骤：S1、FPGA的架构定义详细布局优化对象；S2、高效解析合法化布局逻辑单元占用情况；S3、求解FPGA网表的最大独立集；S4、选取移动的优化对象和侯选位置；S5、确定线长评估算法；S6、设计面向布线优化的移动代价；S7、利用最大独立集全局优化布局；S8、定向优化布局；S9、输出详细布局结果。本发明与现有技术相比的优点在于：该算法寻找全局最大独立集构造优化对象，为优化对象寻找合适的移动过目标位置，避免陷入了线长优化的局部最优解，本发明提出的算法能在不扰动FPGA电路网表的全局合法性和时序的前提下，明显优化布线阶段需要的整体线长，并且降低全局电路网表的拥塞密度。