Fpga Back-end Algorithm Research

Field Programming Gate Arrays(FPGAs)is one of the widest used configurable logic device. With continually developing of semiconductor FPGA is of larger scale and more and more complicated structure.The performance of user design is mostly dependent on CAD. Thus continually improving the performance and flows of CAD is significant. This paper is concern on backend of FPGA CAD flow, including discussing goods/cons of current mainstream backend algorithms and proposing related algorithms to solve specific difficulties.With complicated structures of configurable logic block(CLB)it becomes a challenge to develop adaptable packing algorithm for various structures of CLB.We proposed a novel packing algorithm base on CSP graph matching for the purpose.It packed the user design firstly by matching sub circuits described in files.Then it executed corresponding instructions to rewrite the user design to achieve packing. Experimental result showed our CSP packing algorithm could pack for various CLB structure, meanwhile achieve 1.4% logic block reduction and 6.1% timing performance improvement by defining specific optimizing rules.The classical FPGA placement algorithms are insufficient for placement of various block granularities.We proposed using CSP to solve placement problem. It resolved position conflicts problem, which is common in various granularities placement, easily by using CSP modeling.We also add open cost function and timing analysis to improve the placement result. By running low temperature SA algorithm after generating initial placement using CSP placement, comparative quality can be achieved to VPR placement.Routing accounts for more and more runtime with the ever-increasing FPGA scale. Thus it is more significant to speed up FPGA routing.We proposed a novel routing algorithm on compact routing resource graph(RRG).By introducing the concept of compact graph, we achieve efficient searching space reduction when performing routing on RRG.Experimental result showed average 40.39% on XC4000 series and as high as 33.67% on Spartan2 runtime saving can be achieved compared to VPR routing.