Research And Analysis On FPGA Placement Algorithm

ABSTRACT:Field-Programmable Gate Array(FPGA), a new programmable logic device, was introduced in the mid-term of the 1980s. The features of FPGA are integrated architecture, flexible logic units, high integration and extensive applicability. It is compatible with the advantages of PLD and all-purpose gate array, so it can implement the larger scale circuit and program flexibly. It has advantages of short period in design and development, low-price of design and manufacture, advanced developing tools, non-necessary about normal products, stable quality and so on, comparing with such as gate array and other ASIC, therefore it is widely used in the process of production. FPGA can be applied to almost occasion such as gate array, PLD and small and middle scale of general digital integrated circuit. The programming can configure a universal PLD to become the digital circuit required by users, so as to speed the R&D cycle greatly, reduce the NRE(Non-Recurring Engineering)cost, decrease the Time-to-Market cost of electronic products. The flexible capability of re-configurability provides the opportunity that one chip can be applicable to different uses, especially suitable for different product development.An efficient CAD system is the basis for using FPGA. The flexibility of FPGA brings about many challenges to its corresponding CAD system. As an important section of the process of FPGA CAD design, layout has an important impact on the final routability. The layout software of FPGA implements the operating efficiency of the whole process of FPGA and has a non-neglect impact on the scalability of algorithm. Although the placement of the existing algorithms is very effective, there are still many problems for FPGA design. FPGA placement and routing is the most time-consuming stage in chip design. To design faster,smaller size, less delay,and low-power algorithm is a very hot research topic.This thesis research the algorithms for FPGA, and analysis of the basic idea of these algorithms and their advantages and disadvantages. Most of these algorithms are improved algorithms of the basic placement algorithms. Including the algorithms optimized the path delay:timing driven placement algorithm for FPGA:T-Vplace and Fast timing-driven partitioning-based placement for island style FPGAs; Followed by three timing-driven placement algorithms:ultra-fast placement for FPGAs, Parallel Placement for Field-Programmable Gate Arrays and Hardware assisted simulated annealing with application for fast FPGA placement; Finally, an algorithm to reduce leakage energy and GASA hybrid placement method are introduced. Another analysis used to quantify the relationship of the run time and the quality of the placement.This approach introduce a tuning parameter used to control the quality vs. runtime tradeoff to determine for a given run time, to make how much sacrifice of the placement quality.