Research Of FPGA Packing Algorithm

Compared to the ordinary ASIC circuit and full-custom circuit, the design of FPGA circuit has greater flexibility and is easier to design and implement,the design cycle is short and has low cost. However, on a given process environment, the power consumption and chip area of FPGA are not dominant, especially the running speed. This thesis developed a new FPGA packing algorithm based T-VPack, during the package step of designing FPGA circuits, it can be able to compress the overall length of the critical path, in order to optimize the FPGA chip to enhance the performance.At the beginning of this thesis, we introduce the structure of FPGA and CAD design flow.Then we introduce the current general FPGA packing algorithm, focusing on the T-VPACK packing algorithm. T-VPACK algorithm can be packed on circuit timing optimization, however, the algorithm based on circuit timing information is not updated in real time, but rather updated in sequence. T-VPACK algorithm can not get accurate timing information in the package process. This article as a starting point, hope can be updated in real-time to change the situation and make up any shortfall of T-VPACK algorithm.In the second part, this thesis describes three different ideas of new packing algorithm, in which the third is the most efficient and practical.The third way to package optimization algorithm by copying output, in to compress the length of the critical path. It is better than T-VPACK algorithm is that it can be updated in real time timing information in the optimization process, so that the optimization results more accurate. At the same time, every once optimized, will be on the copy obtained logic output do some compression, so as to achieve the purpose of cutting costs.At the last, we introduce a CAD tool called VPR and general place and route algorithm. The place algorithm usually use simulated annealing algorithm and the route algorithm is based on pathfinder negotiated congestion algorithm.