一种用于FPGA的新型混合布线算法

摘要

布尔可满足性是计算机科学中最基础的问题之一,已经出现了包括著名的基于查找的SAT算法在内的各种算法.对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优点,例如:同步线网嵌入及可布通性确定.然而基于SAT的布线法在可扩展性方面有很大缺陷.而另一方面,几何查找布线算法即使具有广泛的拆线重布线的能力,但当北一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难.文章提出了将一种布尔可满足性算法与VPR430相结合的新型、有效的混合布线算法.试验结果表明与相应的纯几何布线算法相比,这种算法在运行时间上有了极大的改善(减少了29%),并且对布线整体方案无不良影响.