论文部分内容阅读
提出了一种用于求解大规模VLSI模块布局问题的确定性方法.该方法在“最小自由度优先”原则的基础上,模拟人工布局过程提出了“分阶段布局”的思想.分阶段布局就是将布局过程按照布局完成的比例划分成若干个阶段,再将各种启发式策略适当地应用到各个阶段中,从而改善算法的整体性能.理论上,算法的时间复杂为(N1+N2) O(n2)+N3O(n4lgn) ,其中N1,N2,N3为各个阶段的模块数目,N1+N2+N3=n,且N3 n,比原有的最小自由度优先算法复杂度O(n5lgn)小很多.实验结果也表明该方法很有潜力.
A deterministic method for solving large-scale VLSI module layout problem is proposed.The idea of “phased layout” is put forward based on the principle of “minimum degree of freedom first” and simulated artificial layout process.The staged layout is The layout process is divided into several stages according to the proportion of the completed layout, and various heuristic strategies are properly applied to each stage to improve the overall performance of the algorithm.In theory, the time complexity of the algorithm is (N1 + N2) O (n2) + N3O (n4lgn), where N1, N2 and N3 are the number of modules in each stage, N1 + N2 + N3 = n, and N3n is smaller than the original minimum degree of freedom algorithm complexity O A lot of experimental results also show that the method has great potential.