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

A New Hybrid Routing Algorithm for FPGA Routing

作　　者：刘战[1] 于宗光[1] 顾晓峰[1] 王国章[1] 须自明[1] 

机构地区：[1]江南大学信息工程学院,江苏无锡214036

出　　处：《电子器件》2008年第2期432-435,440,共5页Chinese Journal of Electron Devices

摘　　要：布尔可满足性是计算机科学中最基础的问题之一,已经出现了包括著名的基于查找的SAT算法在内的各种算法。对于传统的一次布通一条线网的方法,基于布尔可满足性的算法有着独特的优点,例如:同步线网嵌入及可布通性确定。然而基于SAT的布线法在可扩展性方面有很大缺陷。而另一方面,几何查找布线算法即使具有广泛的拆线重布线的能力,但当一个问题具有严格的布线约束条件时,它在布线方案收敛方面存在很大困难。文章提出了将一种布尔可满足性算法与VPR430相结合的新型、有效的混合布线算法。试验结果表明与相应的纯几何布线算法相比,这种算法在运行时间上有了极大的改善(减少了29%),并且对布线整体方案无不良影响。The Boolean Satisfiability is one of the most fundamental problems in computer science and a variety of algorithms-including the well-known search-based SAT algorithms-have been proposed. Boolean Satisfiability （SAT）-based routing has unique advantages over conventional one-net-at-a-time approaches such as simultaneous net embedding or routability decision. Yet SAT-based routing has been criticized for scalability issues. On the other hand, geometric search routing algorithms, even with extensive rip-up-reroute capabilities, have difficulty achieving routing solution convergence when a problem has tight routing constraints. We propose a new and efficient Hybrid Routing algorithm for FPGAs by integrating a Boolean satisfiability algorithm with VPR430. Experiment results show that relative to the corresponding pure geo- metric algorithm, our hybrid approach shows dramatic （29%） speedup in execution time without negative impact on the quality of the solution.

关 键 词：布尔可满足性 几何查找布线算法 可编程逻辑门阵列 

分 类 号：TN703[电子电信—电路与系统]