A Hybrid Hypergraph Partitioning Algorithm for Scientific Computing

被引：0

作者：

Zeng Yao-yuan ^{[1
]}

Zhao Wen-tao ^{[2
]}

Wang Zheng-hua ^{[1
]}

机构：

[1] Natl Univ Def Technol, Inst Comp Sci, Changsha 410073, Hunan, Peoples R China

[2] Acad Equipment, Laser Propuls & Appl Lab, Beijing 101416, Peoples R China

来源：

MATERIALS PROCESSING AND MANUFACTURING III, PTS 1-4 | 2013年 / 753-755卷

基金：

中国国家自然科学基金;

关键词：

multiway hypergraph partitioning; simulated annealing; global optimization; tabu search; local optimization;

D O I：

10.4028/www.scientific.net/AMR.753-755.2900

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

Hypergraph partitioning is an increasingly important and widely studied research topic in parallel scientific computing. In this paper, we present a multiway hypergraph partitioning algorithm, mixed simulated annealing algorithm for global optimization and tabu search algorithm for local optimization. Experiments on the benchmark suite of several unstructured meshes show that, for 2-, 4-, 8-, 16- and 32-way partitioning, the quality of partition produced by our algorithm are on the average 6% and the maximum 17% better than those produced by partitioning software hMETIS in term of the cutsize metric.

引用

页码：2900 / +

页数：2

共 6 条

[1]

Catalyurek U.V., 2007, PROC 21 INT PARALLEL, DOI DOI 10.1109/IPDPS.2007.370258

[2]

Devine K. D., 2006, P 20 IEEE INT PAR DI, P10, DOI [10.1109/IPDPS.2006.1639359, DOI 10.1109/IPDPS.2006.1639359]

[3]

Fiduccia C.M., 1982, DES AUT C, V7, P175

[4] Tabu search with multi-level neighborhood structures for high dimensional problems [J].

Hedar, Abdel-Rahman ;

Ali, Ahmed Fouad .

APPLIED INTELLIGENCE, 2012, 37 (02) :189-206

[5]

Karypis G, 2009, Metis-a software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing ordering of sparse matrices

[6] Comparative Performance of Modified Simulated Annealing with Simple Simulated Annealing for Graph Coloring Problem [J].

Pal, Anindya Jyoti ;

Ray, Biman ;

Zakaria, Nordin ;

Sen Sarma, Samar .

PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE, ICCS 2012, 2012, 9 :321-327

← 1 →