Abstract: 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日'GA, 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-13oolcan Satisfiability algorithm. Moreover, technique of static symmetry-breaking was added to carry out pretreatment of pseudo-l3oolean constraints, detecting and breaking the symmetries in the routing flow. The purpose was to prune search path, and the cost was consectuently 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.

Key words: Benchmarking,I3oolean function,Field programmable gate arrays,Routing algorithms