赋权超图划分算法的电路划分实验比较研究  

Comparative experiment of weighted hypergraph partitioning algorithms based on circuit partitioning

作　　者：冷明平[1,2] 孙凌宇[1] 郭恺强[1] 边计年[2] 朱平[1] 

机构地区：[1]井冈山大学计算机科学系,江西吉安343009 [2]清华大学计算机科学与技术系,北京100084

出　　处：《计算机工程与应用》2012年第16期74-79,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61063007;No.61163062;No.61106030);江西省自然科学基金(No.2009GQS0060);江西省教育厅科学技术研究(No.GJJ12474;No.GJJ10201;No.GJJ09590;赣教技字[2007]320号)

摘　　要：给出了赋权超图优化划分问题的形式化描述,并结合电路划分的具体应用,采用赋权超图来构造ISPD98电路测试基准的数学模型。阐述了基于迁移方法和多水平方法的赋权超图优化划分算法,并重点讨论了粗化阶段的不同结点匹配策略、迁移优化阶段的不同结点迁移优化策略。基于ISPD98测试基准给出的18组电路,进行了迁移方法和多水平方法的对比实验,以及五种结点匹配和三种结点迁移优化不同组合策略的对比实验,实验数据对比充分验证了多水平方法的可行性和效率。The formal description of weighted hypergraph partitioning problem is presented and the hypergraph model of ISPD98 benchmark is built on the weighted hypergraph. Furthermore, the weighted hypergraph partitioning algorithms based on the move-based approach and multilevel method are described. Different matching strategies of coarsening phase and different refinement strategies of uncoarsening and refinement phase are emphatically discussed. It carries out two comparative experiments of the weighted hypergraph partitioning algorithms based on ISPD98 benchmark, which focus on the combination of five matching strategies and three refinement strategies, the efficiency of the move-based approach and multilevel method. The experiment and analysis show the feasibility and efficiency of multilevel method.

关 键 词：电路网表 超图 划分算法 迁移方法 多水平方法 

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