Research And Implementation On FPGA Placement Algorithm

With the rapid development of Electronic Technology, the application of integrated circuit is on a large scale, the FPGA( Field-Programmable Gate Array)has been widely used as Field Programmable Gate Array devices. At the same time, also require a small design cycle of the FPGA, so it is possible to keep up with the progress of science and technology. Placement is an important step during design procedure of FPGA, which is a connecting link between process Mapping and Routing, and has an important influence on wire-length, the CPU run time, Timing and so on.This article research and implement the algorithm for FPGA, realizing three algorithms based on research analysis. FARPLACE layout algorithm adopts the quadratic wire-length and disturbed nodes to complete the layout, adding disturbed nodes to movable units inside of the chip, making movable units which in chip to new locations by the external force and achieve layout. After researching wire-length model and the density model and then design all of them. When the design is complex, the result on performance of above algorithm is not so good. Therefore, on the basis of FARPLACE algorithm completed, we research and design multi-level layout algorithm based on FARPLACE. Multi-level algorithm is based on the connection strength between the unit and unit, all packaged units as a unit for layout, iterative FARPLACE process can obtain better results. The above two algorithms of wire-length and density is optimized step by step, because of the correlation of wire-length and density, leading to cannot get a good effect on layout at the same time, in addition, the above two algorithms need to add additional nodes which will make the algorithm complexity increase. We construct the cost function by the wire-length and density called as NTUPLACE layout algorithm through weighted and conjugate gradient algorithm is used to find the optimal solution. To avoid the complex process of additional nodes, we optimize wire-length and density at the same time to gain better results.The implementation of the layout algorithm is based on FPGA modeling, we use the modeling language to achieve FPGA modeling, mainly including the design of the hierarchical mode, structure model, implementation model and target model design; Then there is the realization of the algorithm for layout on the open source FPGA development platform overall using of C plus programming language, three layout algorithm is implemented. We compared wire-length, layout time, routing time and timing on each kind of layout algorithm software we have achieved. We got conclusion that NTUPLACE layout algorithm is the best layout in above three layout algorithm, to put this layout algorithm into FPGA supporting software used by user.This article completed modeling on FPGA, The integrity of the modeling schemes enables implementation on the FPGA supporting software to be achieved; it is a major breakthrough to realize the layout algorithm by wire-length and density at the same time, it makes the support software process layout has a better effect, foundation for the development of the FPGA chip. Innovations of this paper are as follows: first, we completed the FPGA modeling scheme, make it possible to achieve FPGA supporting software implementation; second, Layout algorithm adopts the wire-length and density of optimization at the same time, this bring a great improvement than before on layout property.