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

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (16): 74-79.

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

冷明1，2，孙凌宇1，郭恺强1，边计年2，朱平1

1.井冈山大学计算机科学系，江西吉安 343009
2.清华大学计算机科学与技术系，北京 100084

出版日期:2012-06-01 发布日期:2012-06-01

Comparative experiment of weighted hypergraph partitioning algorithms based on circuit partitioning

LENG Ming1，2, SUN Lingyu1, GUO Kaiqiang1, BIAN Jinian2, ZHU Ping1

1.Department of Computer Science, Jinggangshan University, Ji’an, Jiangxi 343009, China
2.Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Online:2012-06-01 Published:2012-06-01

摘要/Abstract

摘要： 给出了赋权超图优化划分问题的形式化描述，并结合电路划分的具体应用，采用赋权超图来构造ISPD98电路测试基准的数学模型。阐述了基于迁移方法和多水平方法的赋权超图优化划分算法，并重点讨论了粗化阶段的不同结点匹配策略、迁移优化阶段的不同结点迁移优化策略。基于ISPD98测试基准给出的18 组电路，进行了迁移方法和多水平方法的对比实验，以及五种结点匹配和三种结点迁移优化不同组合策略的对比实验，实验数据对比充分验证了多水平方法的可行性和效率。

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

Abstract: 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.

Key words: netlist, hypergraph, partitioning algorithm, move-based approach, multilevel method

冷明1，2，孙凌宇1，郭恺强1，边计年2，朱平1. 赋权超图划分算法的电路划分实验比较研究[J]. 计算机工程与应用, 2012, 48(16): 74-79.

LENG Ming1，2, SUN Lingyu1, GUO Kaiqiang1, BIAN Jinian2, ZHU Ping1. Comparative experiment of weighted hypergraph partitioning algorithms based on circuit partitioning[J]. Computer Engineering and Applications, 2012, 48(16): 74-79.

[1]	冷明，孙凌宇，郭晨. XDL网表的前向电路图生成算法[J]. 计算机工程与应用, 2021, 57(10): 75-80.
[2]	李建，习文风. 钻井液设计专家系统规则库的检测算法[J]. 计算机工程与应用, 2020, 56(4): 256-261.
[3]	张喆程，马自堂. GPLP：基于标签传播的大图多级划分算法[J]. 计算机工程与应用, 2016, 52(7): 79-85.
[4]	李志慧，杨丽杰. 参与者人数为五的超图存取结构的最优信息率[J]. 计算机工程与应用, 2015, 51(8): 109-112.
[5]	孙凌宇1，冷明1，2，朱平1，李金忠1. 基于赋权有向超图的云计算依赖任务调度研究[J]. 计算机工程与应用, 2015, 51(24): 34-39.
[6]	王昌龙1，2，冯志勇1，王鑫1，饶国政1. 混合的本体原子分解方法[J]. 计算机工程与应用, 2015, 51(16): 11-16.
[7]	代东锋，詹永照，柯佳. 基于时序概率超图模型的视频多语义标注[J]. 计算机工程与应用, 2013, 49(4): 197-201.
[8]	郑伟1，张丽1，田华1，郝冬梅2，吴颂红2. 基于改进归一化割的甲状腺肿瘤B超图像分割[J]. 计算机工程与应用, 2013, 49(22): 190-193.
[9]	冷明^1，2，孙凌宇¹，郁松年². 一种VLSI剖分系统的研究与实现[J]. 计算机工程与应用, 2010, 46(3): 62-66.
[10]	孙强¹，周涛²，马光胜¹，李海军¹. 一种兼顾可测性和互连造价的资源分配算法[J]. 计算机工程与应用, 2007, 43(19): 23-25.
[11]	杨挺，孙雨耕，张志东. 基于超图的同步无线传感器网络路由算法研究[J]. 计算机工程与应用, 2007, 43(17): 151-153.
[12]	牛振国,符海芳,崔伟宏. 面向区域可持续发展的数据模型研究[J]. 计算机工程与应用, 2006, 42(2期): 11-13.
[13]	宋剑锋,张维明. 分布式卫星组网管理域划分算法 [J]. 计算机工程与应用, 2006, 42(28期): 1-.