| 一种加速FPGA布线的不可满足子式求解算法 |
| |
| 引用本文： | 张建民,黎铁军,马柯帆,肖立权.一种加速FPGA布线的不可满足子式求解算法[J].电子学报,2021,49(6):1210-1216. |
| |
| 作者姓名： | 张建民 黎铁军 马柯帆 肖立权 |
| |
| 作者单位： | 国防科学技术大学计算机学院,湖南长沙410073 |
| |
| 摘 要： | 随着VLSI(Very Large Scale Integrated)芯片设计的规模越来越大,功能越来越复杂,在FPGA(Field Pro-grammable Gate Array)上实现或进行原型验证时,往往会出现布线拥塞或无法布通的情况.而不可满足子式能够迅速诊断FPGA无法布通的原因,并且精确定位关键线网.针对如何加速FPGA详细布线过程,提出了一种基于消解否证的启发式局部搜索算法,能够快速从布尔公式中提取不可满足子式.基于典型的FPGA布线测试集,与两种求解最小不可满足子式效率最高的算法进行了比较,结果表明局部搜索算法在运行效率方面显著优于分支限界算法与贪心遗传算法,而局部搜索算法也能得到最小不可满足子式;并且深入分析了不可满足子式在FPGA详细布线中的作用,能够加速芯片的设计与验证过程.
|
| 关 键 词： | FPGA布线 布线约束 布尔可满足性 不可满足子式 局部搜索 消解否证 |
An Unsatisfiable Subformula Computing Algorithm to Accelerate FPGA Routing |
| |
| ZHANG Jian-min,LI Tie-jun,MA Ke-fan,XIAO Li-quan.An Unsatisfiable Subformula Computing Algorithm to Accelerate FPGA Routing[J].Acta Electronica Sinica,2021,49(6):1210-1216. |
| |
| Authors: | ZHANG Jian-min LI Tie-jun MA Ke-fan XIAO Li-quan |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
