Current challenges in parallel graph partitioning

François Pellegrini

doi:10.1016/j.crme.2010.11.004

Current challenges in parallel graph partitioning

François Pellegrini ¹

¹ Université de Bordeaux, IPB, LaBRI & project Bacchus, INRIA Bordeaux – Sud-Ouest, 351, cours de la Libération, 33405 Talence, France

Comptes Rendus. Mécanique, High Performance Computing, Volume 339 (2011) no. 2-3, pp. 90-95.

Abstract
Résumé

Graph partitioning is a technique used for solving many problems in scientific computing, such as the decomposition of a mesh into domains so as to evenly balance the compute load on the processors of a parallel architecture. Because of the ever increasing size of the meshes to handle, partitioning tools themselves had to be parallelized. The parallel versions of these software provide good results for and on several thousands of processors, but the advent of architectures comprising more than a million processing elements raises new problems. Not only do the partitioning results produced by these software have to take into account the heterogeneity of these architectures, but also does the efficient execution of the partitioning software on these architectures require much more sophisticated algorithms. The purpose of this note is to present the challenges to overcome in order to reach these goals.

Le partitionnement de graphes est une technique utilisée pour la résolution de nombreux problèmes en calcul scientifique, tels que la décomposition d'un maillage en sous-domaines pour répartir la charge de calcul sur les processeurs d'une architecture parallèle. La taille des maillages à traiter augmentant sans cesse, les logiciels de partitionnement ont eux-mêmes dû être parallélisés. Les versions parallèles de ces logiciels fournissent de bons résultats sur et pour plusieurs milliers de processeurs, mais l'arrivée imminente d'architectures hétérogènes comprenant plus d'un million d'unités de traitement pose de nouveaux problèmes. Non seulement les résultats de partitionnement produits par ces logiciels doivent-ils tenir compte de l'hétérogénéité de ces architectures, mais l'exécution efficace du logiciel de partitionnement sur cette même architecture doit-elle nécessiter une algorithmique bien plus sophistiquée. L'objet de cette note est de présenter les défis à surmonter afin d'atteindre ces objectifs.

Published online: 2011-01-03

DOI: 10.1016/j.crme.2010.11.004

Keywords: Computer science, Graph partitioning, Parallel architecture
Mots-clés : Informatique, Partitionnement de graphes, Architecture parallèle

Author's affiliations:

François Pellegrini ¹

¹ Université de Bordeaux, IPB, LaBRI & project Bacchus, INRIA Bordeaux – Sud-Ouest, 351, cours de la Libération, 33405 Talence, France

@article{CRMECA_2011__339_2-3_90_0,
     author = {Fran\c{c}ois Pellegrini},
     title = {Current challenges in parallel graph partitioning},
     journal = {Comptes Rendus. M\'ecanique},
     pages = {90--95},
     publisher = {Elsevier},
     volume = {339},
     number = {2-3},
     year = {2011},
     doi = {10.1016/j.crme.2010.11.004},
     language = {en},
}

TY  - JOUR
AU  - François Pellegrini
TI  - Current challenges in parallel graph partitioning
JO  - Comptes Rendus. Mécanique
PY  - 2011
SP  - 90
EP  - 95
VL  - 339
IS  - 2-3
PB  - Elsevier
DO  - 10.1016/j.crme.2010.11.004
LA  - en
ID  - CRMECA_2011__339_2-3_90_0
ER  -

%0 Journal Article
%A François Pellegrini
%T Current challenges in parallel graph partitioning
%J Comptes Rendus. Mécanique
%D 2011
%P 90-95
%V 339
%N 2-3
%I Elsevier
%R 10.1016/j.crme.2010.11.004
%G en
%F CRMECA_2011__339_2-3_90_0

François Pellegrini. Current challenges in parallel graph partitioning. Comptes Rendus. Mécanique, High Performance Computing, Volume 339 (2011) no. 2-3, pp. 90-95. doi : 10.1016/j.crme.2010.11.004. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.1016/j.crme.2010.11.004/

References
Cited by

[1] M.R. Garey; D.S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979

[2] S.W. Bollinger; S.F. Midkiff Processor and link assignment in multicomputers using simulated annealing, Proc. 11th Int. Conf. on Parallel Processing, The Penn. State Univ. Press, August 1988 , pp. 1-7

[3] S. Kirkpatrick; C.D. Gelatt; M.P. Vecchi Optimization by simulated annealing, Science, Volume 220 ( May 1983 ) no. 4598, pp. 671-680

[4] T.N. Bui; B.R. Moon Genetic algorithm and graph partitioning, IEEE Trans. Comput., Volume 45 (1996) no. 7, pp. 841-855

[5] A.E. Langham; P.W. Grant Using competing ant colonies to solve k-way partitioning problems with foraging and raiding strategies, ECAL'99: Proc. 5th European Conference on Advances in Artificial Life, LNCS, vol. 1674, Springer, 1999, pp. 621-625

[6] R. Battiti; A.A. Bertossi Greedy prohibition, and reactive heuristics for graph partitioning, IEEE Trans. Comput., Volume 48 (1999) no. 4, pp. 361-385

[7] M. Laguna; T.A. Feo; H.C. Elrod A greedy randomized adaptive search procedure for the two-partition problem, Oper. Res., Volume 42 ( August 1994 ), pp. 677-687 | DOI

[8] C. Fahrat A simple and efficient automatic FEM domain decomposer, Comput. Struct., Volume 28 (1988) no. 5, pp. 579-602

[9] G. Karypis, V. Kumar, Multilevel graph partitioning schemes, in: Proc. 24th Intern. Conf. Par. Proc. III, CRC Press, 1995, pp. 113–122.

[10] B. Nour-Omid; A. Raefsky; G. Lyzenga Solving finite element equations on concurrent computers (A.K. Noor, ed.), Parallel Computations and Their Impact on Mechanics, ASME Press, 1986, pp. 209-227

[11] S.T. Barnard; H.D. Simon A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurrency: Practice and Experience, Volume 6 (1994) no. 2, pp. 101-117

[12] R. Diekmann; R. Preis; F. Schlimbach; C. Walshaw Aspect ratio for mesh partitioning, Proc. Euro-Par'98, LNCS, vol. 1470, Springer, 1998, pp. 347-351

[13] B. Hendrickson, R. Leland, A multilevel algorithm for partitioning graphs, in: Proc. ACM/IEEE Conference on Supercomputing (CDROM), December 1995, 28 pp.

[14] G. Karypis; V. Kumar A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput., Volume 20 (1998) no. 1, pp. 359-392

[15] B.W. Kernighan; S. Lin An efficient heuristic procedure for partitioning graphs, BELL System Technical Journal, Volume 49 ( February 1970 ) no. 2, pp. 291-307

[16] C.M. Fiduccia; R.M. Mattheyses A linear-time heuristic for improving network partitions, Proc. 19th Design Automation Conference, IEEE, 1982, pp. 175-181

[17] B. Hendrickson; E. Rothberg Improving the runtime and quality of nested dissection ordering, SIAM J. Sci. Comput., Volume 20 (1998) no. 2, pp. 468-489

[18] Chaco: Software for partitioning graphs, http://www.sandia.gov/~bahendr/chaco.html.

[19] metis: Family of multilevel partitioning algorithms, http://glaros.dtc.umn.edu/gkhome/views/metis.

[20] jostle: Graph partitioning software, http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/.

[21] scotch: Static mapping, graph partitioning, and sparse matrix block ordering package, http://www.labri.fr/~pelegrin/scotch/.

[22] B. Vastenhouw; R.H. Bisseling A two-dimensional data distribution method for parallel sparse matrix–vector multiplication, SIAM Rev., Volume 47 (2005) no. 1, pp. 67-95

[23] C. Chevalier; F. Pellegrini PT-Scotch: A tool for efficient parallel graph ordering, Parallel Comput., Volume 34 (2008), pp. 318-331

[24] J.-H. Her, F. Pellegrini, Efficient and scalable parallel graph partitioning by recursive bipartitioning, http://www.labri.fr/~pelegrin/papers/scotch_parallelbipart_parcomp.pdf, Parallel Computing (2011), in press.

[25] F. Pellegrini A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries, Proc. Euro-Par'07, LNCS, vol. 4641, Springer, August 2007 , pp. 191-200

[26] C. Chevalier; F. Pellegrini Improvement of the efficiency of genetic algorithms for scalable parallel graph partitioning in a multi-level framework, Proc. Euro-Par'06, Dresden, LNCS, vol. 4128, Springer, September 2006 , pp. 243-252

[27] F. Pellegrini, Static mapping by dual recursive bipartitioning of process and architecture graphs, in: Proc. SHPCC'94, IEEE, May 1994, pp. 486–493.

[28] C. Walshaw; M. Cross; M.G. Everett; S. Johnson; K. McManus Partitioning and mapping of unstructured meshes to parallel machine topologies, Proc. Irregular'95, LNCS, vol. 980, Springer, 1995, pp. 121-126

Cited by Sources:

Comments - Policy