Large Scale VLSI Module Placement Using LFF Heuristics by Stages  

基于分阶段LFF策略的大规模模块布局方法(英文)

作　　者：魏少俊[1] 董社勤[1] 洪先龙[1] 吴有亮[2] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]香港中文大学计算机科学与工程系

出　　处：《Journal of Semiconductors》2006年第5期812-818,共7页半导体学报（英文版）

基　　金：国家自然科学基金委与香港RGC联合资助项目(批准号:60218004) ;国家自然科学基金(批准号:90307005);国家高技术研究发展计划(批准号:2004AA1Z1050)资助项目~~

摘　　要：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 （N1 ＋ N2 ） × O（ n^2 ） ＋ N3× O（n^4lgn） ,where N1, N2 ,and N3 denote the number of modules in each stage, N1 ＋ N2 ＋ N3 = n, and N3〈〈 n. This complexity is much less than the original time complexity of O（n^5lgn）. Experimental results indicate that this approach is quite promising.提出了一种用于求解大规模VLSI模块布局问题的确定性方法.该方法在“最小自由度优先”原则的基础上,模拟人工布局过程提出了“分阶段布局”的思想.分阶段布局就是将布局过程按照布局完成的比例划分成若干个阶段,再将各种启发式策略适当地应用到各个阶段中,从而改善算法的整体性能.理论上,算法的时间复杂为(N1+N2) O(n2)+N3O(n4lgn) ,其中N1,N2,N3为各个阶段的模块数目,N1+N2+N3=n,且N3 n,比原有的最小自由度优先算法复杂度O(n5lgn)小很多.实验结果也表明该方法很有潜力.

关 键 词：FLOORPLANNING placements large scale LFF principle deterministic placement algorithm 

分 类 号：TN47[电子电信—微电子学与固体电子学]