【摘要】 提出了一种用于求解大规模VLSI模块布局问题的确定性方法.该方法在“最小自由度优先”原则的基础上,模拟人工布局过程提出了“分阶段布局”的思想.分阶段布局就是将布局过程按照布局完成的比例划分成若干个阶段,再将各种启发式策略适当地应用到各个阶段中,从而改善算法的整体性能.理论上,算法的时间复杂为(N1+N2) O(n2)+N3O(n4lgn) ,其中N1,N2,N3为各个阶段的模块数目,N1+N2+N3=n,且N3 n,比原有的最小自由度优先算法复杂度O(n5lgn)小很多.实验结果也表明该方法很有潜力.更多还原

【Abstract】 We present a deterministic algorithm for large-scale VLSI module placement.Following the less flexibility first （LFF） principle,we simulate a manual packing process in which the concept of placement by stages is introduced to reduce the overall evaluation complexity.The complexity of the proposed algorithm is （N₁+N₂）× O（n2）+N₃×O（n4lgn）,where N₁,N₂,and N₃ denote the number of modules in each stage,N₁+N₂+N₃=n,and N₃n.This complexity is much less than the original time complexity of O（n5lgn）.Experimental results indicate that this approach is quite promising.更多还原