一种改进的伪布尔可满足性算法用于FPGA布线  

New Improved Pseudo-boolean Satisfiability Algorithm for FPGA Routing

作　　者：唐玉兰[1] 刘战[2] 于宗光[1,3] 陈建慧[1,4] 

机构地区：[1]江南大学信息工程学院,无锡214122 [2]五邑大学信息学院,江门529020 [3]中国电子科技集团公司第五十八研究所,无锡214035 [4]无锡职业技术学院,无锡214121

出　　处：《计算机科学》2010年第10期297-300,F0003,共5页Computer Science

基　　金：江苏省自然科学基金(资助号:BK2007026);江苏省‘333高层次人才培养工程’专项(资助号:2007124)资助

摘　　要：为了避免伪布尔可满足性算法在布线过程中带来的增加转换成本的负面影响,提出了一种用于FPGA的新的布线算法,该算法结合了伪布尔可满足性算法与几何布线算法的优点。在布线过程中,先选用PathFinder这种几何布线方法对FPGA进行布线,如果不能成功再采用伪布尔可满足性算法。并在布线流程中增加了静态对称破缺技术对伪布尔约束进行预处理,侦测并破缺其中的对称,从而达到减少搜索路径,消减成本的目的。初步的实验结果表明,这种混合布线方法可以显著减少运行时间,加速求解过程,并且对整体方案无不良影响。In order to avoid the negative effect of increasing transformation cost of pseudo-Boolean Satisfiability algorithm in the routing process,a new routing algorithm was proposed for FPGA,which combines advantages of pseudo-Boolean Satisfiability and geometric routing algorithm.In the routing process,PathFinder,one of geometric routing algorithm was chosen firstly for FPGA routing.If not successful,then used pseudo-Boolean Satisfiability algorithm.Moreover,technique of static symmetry-breaking was added to carry out pretreatment of pseudo-Boolean constraints,detecting and breaking the symmetries in the routing flow.The purpose was to prune search path,and the cost was consequently reduced.Preliminary experiments results show that the hybrid approach can reduce the runtime observably,speed up the solving process,and have no adverse affect on overall program.

关 键 词：基准 布尔函数 现场可编程门阵列 布线算法 

分 类 号：TN405.97[电子电信—微电子学与固体电子学]