PT-SCOTCH: A tool for efficient parallel graph ordering

被引：230

作者：

Chevalier, C. ^{[1
]}

Pellegrini, F. ^{[1
]}

机构：

[1] LaBRI & Project ScAlApplix INRIA Futurs, ENSEIRB, F-33400 Talence, France

来源：

PARALLEL COMPUTING | 2008年 / 34卷 / 6-8期

关键词：

parallel graph ordering; parallel nested dissection; distributed-memory computer; multi-threading;

D O I：

10.1016/j.parco.2007.12.001

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which arc also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-SCOTCH software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-SCOTCH produces consistently better orderings than PARMETIS on large numbers of processors. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：318 / 331

页数：14

共 32 条

[1] An approximate minimum degree ordering algorithm [J].

Amestoy, PR ;

Davis, TA ;

Duff, IS .

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1996, 17 (04) :886-905

[2] Multifrontal parallel distributed symmetric and unsymmetric solvers [J].

Amestoy, PR ;

Duff, IS ;

L'Excellent, JY .

COMPUTER METHODS IN APPLIED MECHANICS AND ENGINEERING, 2000, 184 (2-4) :501-520

[3]

[Anonymous], 1981, COMPUTER SOLUTION LA

[4] FAST MULTILEVEL IMPLEMENTATION OF RECURSIVE SPECTRAL BISECTION FOR PARTITIONING UNSTRUCTURED PROBLEMS [J].

BARNARD, ST ;

SIMON, HD .

CONCURRENCY-PRACTICE AND EXPERIENCE, 1994, 6 (02) :101-117

[5]

CHEN TY, 1999, P 9 SIAM C PAR PROC

[6]

Chevalier C, 2006, LECT NOTES COMPUT SC, V4128, P243

[7]

Davis Tim., U FLORIDA SPARSE MAT

[8]

*EU ESPRIT 4 LTR, 1996, 20160 EU ESPRIT 4 LT

[9]

Fiduccia C., 1982, P 19 IEEE DES AUT C, P175, DOI [10.1109/DAC.1982.1585498, DOI 10.1109/DAC.1982.1585498]

[10] THE EVOLUTION OF THE MINIMUM DEGREE ORDERING ALGORITHM [J].

GEORGE, A ;

LIU, JWH .

SIAM REVIEW, 1989, 31 (01) :1-19

← 1 2 3 4 →