Research On Placement And Routing Algorithms For Antifuse FPGA And CAD Software Development

Field Programmable Gate Arrays(FPGAs) comprise massive programmable logic resources and routing resources and can be programmed by the uses. FPGAs can not only decrease the design cycle of ASIC, but also greatly reduce the design cost and design risk. Antifuse FPGAs have been widely adopted in a lot of fields due to their high radiation tolerance, high and low temperature bearing, low power, high speed and high security, such as military, satellite communication and aeronautics and space. However, the research of antifuse FPGA is just beginning, especially associated CAD software, and a number of key technical problems need to be solved. Based on this background, this paper conducted an intensive study on associated algorithms and CAD software development for antifuse FPGA. This paper includes following aspects.(1) A wire-length driven placement algorithm was proposed. Unlike the conventional island style FPGA, antifuse FPGA had much more horizontal routing resources than vertical routing resources. Based on this unique characteristics of the antifuse FPGA architecture, the algorithm modified the simulated annealing algorithm in VPR, and introduced a new cost factor in the linear congestion cost function, thus effectively improved the usage of vertical routing resources. The experimental results showed that compared to the placement results of VPR, the proposed algorithm could not only improve the total wire length by 12% on average, but also reduce the number of programmed horizontal antifuses.(2) A novel fault tolerance approach for the antifuse FPGA was proposed. This approach could deal with the stuck-open fault of the antifuse in the antifuse FPGA, and its basic idea was to reserve more symmetrical routing resources during FPGA routing. When a faulty antifuse is found, symmetrical routing resources were used to implement a signal path and therefore the faulty antifuse was bypassed. Although the approach introduced extra signal delay, the performance of the circuit after fault tolerance remained the same. The experimental results showed that when the routing resources in the FPGA are fixed, the percentage of the reserved symmetrical routing resource could be increased by 30.4% on average while for some instances the percentage can reach 100%. Our method can bypass any single faulty antifuse in the FPGA when the percentage of reserved resource is 100%.(3) A multilevel pseudo-boolean satisfiability-based routing algorithm was proposed. The algorithm formulated the segmented channel routing problem of antifuse FPGA as a pseudo-Boolean optimization(PBO) problem, which was solved by a modern PBO solver. The proposed algorithm could not only find an optimal routing solution, but also check unroutability of a given circuit. Moreover, in order to improve the solution quality and reduce the execution time, the algorithm constructed several levels of hierarchy amongst the nets and each time a subset of nets was routed. If the algorithm failed to find any solution, it would backtrack to a higher level. The experimental results showed that the proposed algorithm could provide optimal routing solutions within a reasonable time and achieved the best convergence rate.(4) A complete CAD system for antifuse FPGA was developed. The CAD system took full advantage of commercial software and open source software from academia, and some new tools were also designed to complete the FPGA design flow. The generic library and the target library for ACT2 FPGA were built and users could update the configuration file to generate a new technology mapping library. In order to support the antifuse FPGA, the placement and routing algorithm of VPR were modified and replaced by the proposed wire-length driven placement algorithm and the multilevel pseudo-boolean satisfiability-based routing algorithm respectively. A novel bitstream generation algorithm was used in Streamline and it determined the coordinates of each antifuse by dividing the FPGA into several regions. Users could easily complete the entire design flow in the graphical user interface. The CAD system had been successfully used to program the A1240 A chip and the test result validated the effectiveness and practicality of the proposed CAD framework.(5) A novel bit cell circuit based on the gate oxide antifuse was proposed. Since the resistance of the gate oxide antifuse after programming was very large and widely distributed, the gate oxide antifuse could not be used in the antifuse FPGA directly. The proposed bit cell circuit overcame the weakness of the gate oxide antifuse and it was composed of two antifuses, a selection transistor and a blocking transistor, and it outputted stable logic levels to control the state of each node in FPGA. Thus gate oxide antifuse could be successfully used in the antifuse FPGA as a bit cell circuit. The circuit of the antifuse FPGA was designed and the layout was implemented by using HHNEC 0.18μm CMOS process. The test result verified the feasibility of the proposed bit cell circuit.