多级划分算法的后处理与评价方法  

Post-processing and Evaluation for Multilevel Partitioning Algorithm

作　　者：蒿杰[1] 彭思龙[1] 

机构地区：[1]中国科学院自动化研究所国家专用集成电路设计工程研究中心,北京100190

出　　处：《小型微型计算机系统》2010年第1期160-163,共4页Journal of Chinese Computer Systems

基　　金：国家科技支撑计划重点项目(2006BAK07B04)资助

摘　　要：多级划分算法需要进行多次实验以得到最优值.本文根据网表顶点在多次实验中的倾向性将其分为:活跃点、固定点和亚固定点,并提出只对活跃点重新划分的后处理方法.另外,通过将固定点和亚固定点分配到相应簇中,得到一种算法评价方法.实验表明,本文的后处理方法可有效减小hMetis算法的最小割,而评价方法能够客观评价hMetis算法在不同聚类策略下的划分结果.Multilevel partitioning algorithm obtains an optimal solution from a lot of experiments. According to the tendency of vertices in all experiments, vertices are classified into three categories ： active vertices, fixed vertices and semi-fixed vertices. We propose a post-processing method by re-partitioning only for active vertices. Besides, by assigning fixed vertices and semi-fixed vertices to the corresponding clusters, we can obtain an evaluation method for partitioning algorithm. Experiment shows that our post-processing method can effectively reduce the min-cut of hMetis algorithm. In addition, we objectively evaluate the result of hMetis algorithm with different clustering strategies.

关 键 词：多级划分算法 收敛性 后处理 超图 超大规模集成电路 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]