SRAM-based FPGA Routing Algorithm Optimization And Implementation

Field programmable gate array(FPGA) has high integration, excellent design flexibility and can reduce the risk of project development and non-recurring engineering(NRE). Therefore, FPGA has become an increasingly popular in digital circuit design today. As the semiconductor technology has developed into the deep sub-micron size even nanoscale, the logic capacity of FPGA becomes bigger and bigger to meet the needs of the larger design. In order to make full use of these new technologies in deep submicron and even nanometer, it’s essential to rebuild the FPGA hardware structure in the corresponding electronic design automation(EDA) tools. However, layout and routing have been one of the technical difficulties in these EDA tools. As the circuit scale becomes larger, the routing phase costs mor e time in process of compiling circuit, therefore, it is necessary to continuously optimize efficiency of the routing algorithm in order to achieve timing optimization and improve the efficiency of development.This thesis works on the special structure of SRAM-based FPGA. The research focuses on optimizing routing algorithm of router tool locally. This paper first introduces how to model the hardware structure of FPGA in software, it adopts the structural description language(SDL) in EDA tools, the hardware structure is mapped into the software tools. The author, considering the special structure of the FPGA’s look-up table(LUT), puts forward the strategy of using PERMUX entity based on this description of SDL, the test shows that it can effectively improve the routing flexibility after using this strategy, thus it improves the efficiency of routing algorithm. What’s more, considering the routing of geometrical lookup algorithm can be influenced easily by rou ting order of wire net, the author studies on the properties of various sorting method on routing by comparing in experimental test and determine the optimal routing order of wire net; Finally, this paper also focuses on large net span. The thesis takes the strategy of the global routing and proved the effectiveness of the proposed strategy in practical use.As to the aspect of implementing the algorithm, this paper first introduces the basic routing algorithm. Then the author presents the implementation process in detail and local optimized details which have been proposed in the process of implementation, such as taking routing search box to reduce the search depth. In a word, the actual test data shows that all kinds of optimizations have improved the overall efficiency of the router.