FPGA Placement Algorithm Research Based On Agent And Multimedia Technology

FPGA appears in the mid-1980s as a new type of programmable logic device. 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.The VPR is common software for the FPGA placement and routing.It puts forward a comprehensive method of FPGA placement and routing solution.Simulated annealing algorithm is applied to VPR. The advantage of algorithm is that it can jump out of local optimal solution to be close to the optimal solution,but the drawback is that it takes a long time.In order to address the issue,some algorithms,such as fast simulated annealing algorithm,general simulated annealing algorithm,force directed annealing algorithm and ascending temperature tempering annealing algorithm,are applied in the FPGA placement.Compared to classical simulated annealing algorithm,fast simulated annealing algorithm model is based on the reception probability given by the generalized Gibbs distribution.Its disturbance model is similar to the Cauchy distribution.Its cooling model is T(K)=T₀a^k1/N.The new algorithm convergence rate is faster than the old algorithm.General simulated annealing algorithm is also based on the generalized Gibbs distribution.Its disturbance model is Tsallis-Stariolo distribution.It is more effective than classical simulated annealing algorithm when there are multi-objective function and lots of local minimum.Classical simulated annealing algorithm and fast simulated annealing algorithm are a special case of general simulated annealing algorithm.Force directed annealing algorithm is force directed relaxation method combined with simulated annealing method.The core of force directed relaxation method is that the current unit exchange to the location where it has smallest force.Combination of simulated annealing method is to use simulated annealing acceptance strategy to determine whether or not to accept the solution after swap.Ascending temperature tempering annealing algorithm changes the cooling strategy.Firstly,it uses low temperature annealing,the optimized solution is as the initial solution of the next annealing.Then the initial temperature gradual increase and repeated annealing.The experimental results of large-scale circuit placement show that fast simulated annealing algorithm can run 1.9 times than that of VPR,while the quality of solution reduces 4%.General simulated annealing algorithm can run 1.9 times than that of VPR,while the quality of solution reduces 15%.And ascending temperature tempering annealing algorithm runs 3 times faster with the same quality of VPR.The result of force directed annealing algorithm is the same as VPR.Ascending temperature tempering annealing algorithm can run 3 times than that of VPR,while the quality of solution doesn't reduce.The above algorithms can speed up the FPGA placement.