Parallel greedy graph matching using an edge partitioning approach

M.M.A. Patwary; R.H. Bisseling; F. Manne

doi:10.1145/1863482.1863493

Parallel greedy graph matching using an edge partitioning approach

M.M.A. Patwary, R.H. Bisseling, F. Manne

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We present a parallel version of the Karp-Sipser graph matching heuristic for the maximum cardinality problem. It is bulksynchronous, separating computation and communication, and uses an edge-based partitioning of the graph, translated from a twodimensional partitioning of the corresponding adjacency matrix. It is shown that the communication volume of Karp–Sipser graph matching is proportional to that of parallel sparse matrix–vector multiplication (SpMV), so that efficient partitioners developed for SpMV can be used. The algorithm is presented using a small basic set of 7 message types, which are discussed in detail. Experimental results show that for most matrices, edge-based partitioning is superior to vertex-based partitioning, in terms of both parallel speedup and matching quality. Good speedups are obtained on up to 64 processors.

Original language	English
Title of host publication	HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications
Subtitle of host publication	September 25, 2010, Baltimore, Maryland, USA
Editors	Frédéric Loulergue
Place of Publication	New York
Publisher	Association for Computing Machinery
Pages	45-54
Number of pages	10
ISBN (Print)	978-1-4503-0254-8
DOIs	https://doi.org/10.1145/1863482.1863493
Publication status	Published - 2010

Keywords

bulk-synchronous parallel
graph
heuristics
Karpsipser
matching
partitioning
sparse matrix

Access to Document

10.1145/1863482.1863493

Hlpp02-patwary
Closed Access
Final published version, 211 KB

Cite this

Patwary, M. M. A., Bisseling, R. H., & Manne, F. (2010). Parallel greedy graph matching using an edge partitioning approach. In F. Loulergue (Ed.), HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications: September 25, 2010, Baltimore, Maryland, USA (pp. 45-54). Association for Computing Machinery. https://doi.org/10.1145/1863482.1863493

Patwary, M.M.A. ; Bisseling, R.H. ; Manne, F. / Parallel greedy graph matching using an edge partitioning approach. HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications: September 25, 2010, Baltimore, Maryland, USA. editor / Frédéric Loulergue. New York : Association for Computing Machinery, 2010. pp. 45-54

@inproceedings{5a674c1ab6eb4eedbcb8bfb17e954ad8,

title = "Parallel greedy graph matching using an edge partitioning approach",

abstract = "We present a parallel version of the Karp-Sipser graph matching heuristic for the maximum cardinality problem. It is bulksynchronous, separating computation and communication, and uses an edge-based partitioning of the graph, translated from a twodimensional partitioning of the corresponding adjacency matrix. It is shown that the communication volume of Karp–Sipser graph matching is proportional to that of parallel sparse matrix–vector multiplication (SpMV), so that efficient partitioners developed for SpMV can be used. The algorithm is presented using a small basic set of 7 message types, which are discussed in detail. Experimental results show that for most matrices, edge-based partitioning is superior to vertex-based partitioning, in terms of both parallel speedup and matching quality. Good speedups are obtained on up to 64 processors.",

keywords = "bulk-synchronous parallel, graph, heuristics, Karpsipser, matching, partitioning, sparse matrix",

author = "M.M.A. Patwary and R.H. Bisseling and F. Manne",

year = "2010",

doi = "10.1145/1863482.1863493",

language = "English",

isbn = "978-1-4503-0254-8",

pages = "45--54",

editor = "Fr{\'e}d{\'e}ric Loulergue",

booktitle = "HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications",

publisher = "Association for Computing Machinery",

address = "United States",

}

Patwary, MMA, Bisseling, RH & Manne, F 2010, Parallel greedy graph matching using an edge partitioning approach. in F Loulergue (ed.), HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications: September 25, 2010, Baltimore, Maryland, USA. Association for Computing Machinery, New York, pp. 45-54. https://doi.org/10.1145/1863482.1863493

Parallel greedy graph matching using an edge partitioning approach. / Patwary, M.M.A.; Bisseling, R.H.; Manne, F.
HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications: September 25, 2010, Baltimore, Maryland, USA. ed. / Frédéric Loulergue. New York: Association for Computing Machinery, 2010. p. 45-54.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Parallel greedy graph matching using an edge partitioning approach

AU - Patwary, M.M.A.

AU - Bisseling, R.H.

AU - Manne, F.

PY - 2010

Y1 - 2010

N2 - We present a parallel version of the Karp-Sipser graph matching heuristic for the maximum cardinality problem. It is bulksynchronous, separating computation and communication, and uses an edge-based partitioning of the graph, translated from a twodimensional partitioning of the corresponding adjacency matrix. It is shown that the communication volume of Karp–Sipser graph matching is proportional to that of parallel sparse matrix–vector multiplication (SpMV), so that efficient partitioners developed for SpMV can be used. The algorithm is presented using a small basic set of 7 message types, which are discussed in detail. Experimental results show that for most matrices, edge-based partitioning is superior to vertex-based partitioning, in terms of both parallel speedup and matching quality. Good speedups are obtained on up to 64 processors.

AB - We present a parallel version of the Karp-Sipser graph matching heuristic for the maximum cardinality problem. It is bulksynchronous, separating computation and communication, and uses an edge-based partitioning of the graph, translated from a twodimensional partitioning of the corresponding adjacency matrix. It is shown that the communication volume of Karp–Sipser graph matching is proportional to that of parallel sparse matrix–vector multiplication (SpMV), so that efficient partitioners developed for SpMV can be used. The algorithm is presented using a small basic set of 7 message types, which are discussed in detail. Experimental results show that for most matrices, edge-based partitioning is superior to vertex-based partitioning, in terms of both parallel speedup and matching quality. Good speedups are obtained on up to 64 processors.

KW - bulk-synchronous parallel

KW - graph

KW - heuristics

KW - Karpsipser

KW - matching

KW - partitioning

KW - sparse matrix

U2 - 10.1145/1863482.1863493

DO - 10.1145/1863482.1863493

M3 - Conference contribution

SN - 978-1-4503-0254-8

SP - 45

EP - 54

BT - HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications

A2 - Loulergue, Frédéric

PB - Association for Computing Machinery

CY - New York

ER -

Patwary MMA, Bisseling RH, Manne F. Parallel greedy graph matching using an edge partitioning approach. In Loulergue F, editor, HLPP '10 : proceedings of the Fourth International Workshop ACM SIGPLAN Workshop on High-level Parallel Programming and Applications: September 25, 2010, Baltimore, Maryland, USA. New York: Association for Computing Machinery. 2010. p. 45-54 doi: 10.1145/1863482.1863493

Parallel greedy graph matching using an edge partitioning approach

Abstract

Keywords

Access to Document

Fingerprint

Cite this