FPGA Placement Algorithms

With the continuous progress of IC technology, modern FPGA presents atendency of high speed, high density, low cost. The complication of the structure andthe expanded scale of the chip bring about more new challenges to physical design ofthe FPGA. Placement is one of the key link in physical design, the quality impact theperformance of final circuit directly. Aiming at cluster problems,2-D placementproblems and3-D placement problems of FPGA physical design, this thesis presentsthe following innovative work base island-style FPGA:(1)Presents physical information based cluster algorithm. Through iterativebi-partition and two traversals, this provides logical physical location information forlogic cell. According to the interconnection, we carry out two stages partition, whichimproves the accuracy of the algorithm. The cluster policy which considering thephysical location information produces better cluster results. This algorithm decreasesthe average external net number of the logic cell and the wire-length of the finalcircuit.(2)Presents wirelength-driven fast placement for island style FPGAs. With theconsidering of the terminal node, we can describe the net weight more accurately,the algorithm improves the partition results based on wire-length and bring thepartition process and final optimization objective together. Using the mappingrelationship between logic cell and physical cell, designing the capacity and cost ofthe arc, a Minimum Cost Network Flow (MCNF) graph can be set up correspondingto the2-D FPGA placement. The MCNF method can achieve more rationale result ofthe initial placement. The initial placement is optimized by low temperatureSimulated Annealing (SA) rapidly and the final placement result is obtained. Thisalgorithm decreases the wire-length of initial placement by24.5%and the runtime ofthe final placement by33.6%.(3)Presents wirelength-driven force-directed3D FPGA placement. The algorithmchanges the traditional algorithm of3-D placement, and adjusts the partition stageafter global placement stage. Through the3-D adjustment on the2-D analyticalplacement method, the force-driven algorithm transforms to three-dimensional spacesuccessfully. In order to improve the partition quality, we use the adjustedforce-driven global placement algorithm to acquire the relative physical locationinformation between models quickly. After that, a legalization and space filling curve are used, the3-D initial placement stage ends. A low temperature SA is used topartition the level and optimizes the placement result. The parameters of The SA areadjusted. This reduces the solution space and promotes the efficiency of thealgorithm. The final3-D circuit wire-length decreases by8.57%.In summary, this thesis aims at modern FPGA physical design, providesoptimization objective based on circuit wirelength and optimization algorithmsapplied from cluster stage to placement stage.