Research Of Timing Driven FPGA Placement Algorithm

With the development of technology,the FPGA circuit design's logic elements have substantially increased from several hundreds to tens of thousands or even hundreds of thousands,which made chips more complicated at the same time,and raised higher standards for FPGA automatic designing tools.As a crucial part in FPGA designing,placement decides the actual physical location of logic elements on FPGA chips.The result of placement will largely influence the overall performance of circuit design.The classic placement algorithm takes the shortest wire length as its optimal goal to obtain the better circuit performance.However,the method of reducing the total wire length between logic elements to improve circuit performance is not ideal.In comparison,timing driven placement algorithm takes minimal delay as its optimal goal,obtaining the timing information of circuit design directly through timing analysis,which can reduce the size of delay effectively for better performance.The timing driven placement algorithm is the main research content of this thesis,which studies the circuit's optimization brought by timing driven FPGA placement algorithm,and putting the algorithm into practical circuit designing for a better circuit performance.Considering the running time and placement quality of placement algorithm,this thesis makes a detail analysis and comparison of the mainstream FPGA placement algorithms.Featuring in high-quality placement and rapid running,the force directed placement algorithm will be the focus of research in this thesis.Then,allowing for the overall performance of FPGA circuit designing,this thesis takes timing driven as placement algorithm's optimal goal.By applying the timing driven to force directed placement algorithm to study timing driven FPGA placement algorithm.Starting from implementation principle and process of timing driven,this thesis makes a study on the realization of static timing analysis,and analyzes every parameters of critical path of net based on the actual circuit designing.Meanwhile,based on FPGA automatic designing tools,this thesis studies the designing of timing constraint and the influence on placement result brought by timing constraint.And also analyzes how timing driven optimizes circuit designing.Finally,from the implementation process of timing driven FPGA placement algorithm,this thesis studies the timing driven placement algorithm through the process of global placement and detailed placement.Among which the global placement can achieve the effect of timing driven by improving force directed placement algorithm and updating the circuit net's weight through timing analysis.Based on the result of global placement,detailed placement can remove the overlap of logic elements in placement result and further optimize the timing of circuit by the methods of area-traversal and timing analysis.Ultimately,the overall performance of circuit can be improved.