The Improvements And Application Of Less Flexibility First Algorithm

With the rapid development of nanometer technology, the design of VLSI meets a great deal challenge. Physical design is an important step of IC layout manufacturing and placement is one of the key technologies in VLSI physical design. VLSI placement is a quite complicated combination optimization problem, which is proved to be a NP-Hard problem.The deterministic placement algorithm based on Less Flexibility First (LFF) Principles has polynomial complexity. The results of the algorithm present the better performance on area usage than the stochastic optimization algorithm. In order to meet the requirements of the further developments, improvements and extension are definitely necessary to this algorithm. And that's the essence of this article.First of all LFF algorithm uses the KD-Tree as the basic data structure and correspondingly designs the whole fitness evaluation based on KD-Tree. Though KD-Tree is an efficient data structure we still don't think it's performance is good enough for LFF flow. We plan to reduce the time complexity more. At the same time since LFF is a deterministic placement algorithm we hope the every deterministic step of LFF can be more rational and efficient. So this article focuses on improving the data structure and decisive evaluation on the purpose of the better results.Secondly the original LFF algorithm was applied to 2D rectilineal placement in the beginning. With the new development, the brand new hexagon circuit was presented by far which bring the new challenges to placement algorithm. It's the other subject of this article to apply the improved LFF algorithm to Hexagon/Triangle placement.