New Improved Pseudo-boolean Satisfiability Algorithm for FPGA Routing
一种改进的伪布尔可满足性算法用于FPGA布线

为了避免伪布尔可满足性算法在布线过程中带来的增加转换成本的负面影响，提出了一种用于FPGA的新的布线算法，该算法结合了伪布尔可满足性算法与几何布线算法的优点。在布线过程中，先选用PathFinder这种几何布线方法对FPC}A进行布线，如果不能成功再采用伪布尔可满足性算法。并在布线流程中增加了静态对称破缺技术对伪布尔约束进行预处理，侦测并破缺其中的对称，从而达到减少搜索路径，消减成本的目的。初步的实验结果表明，这种混合布线方法可以显著减少运行时间，加速求解过程，并且对整体方案无不良影响。