Observations from parallelising three maximum common (Connected) subgraph algorithms

Ruth Hoffmann; Ciaran McCreesh; Samba Ndojh Ndiaye; Patrick Prosser; Craig Reilly; Christine Solnon; James Trimble

doi:10.1007/978-3-319-93031-2_22

Observations from parallelising three maximum common (Connected) subgraph algorithms

Ruth Hoffmann, Ciaran McCreesh^*, Samba Ndojh Ndiaye, Patrick Prosser, Craig Reilly, Christine Solnon, James Trimble

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We discuss our experiences adapting three recent algorithms for maximum common (connected) subgraph problems to exploit multi-core parallelism. These algorithms do not easily lend themselves to parallel search, as the search trees are extremely irregular, making balanced work distribution hard, and runtimes are very sensitive to value-ordering heuristic behaviour. Nonetheless, our results show that each algorithm can be parallelised successfully, with the threaded algorithms we create being clearly better than the sequential ones. We then look in more detail at the results, and discuss how speedups should be measured for this kind of algorithm. Because of the difficulty in quantifying an average speedup when so-called anomalous speedups (superlinear and sublinear) are common, we propose a new measure called aggregate speedup.

Original language	English
Title of host publication	Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication	15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings
Editors	Willem-Jan van Hoeve
Place of Publication	Cham
Publisher	Springer
Pages	298-315
Number of pages	18
ISBN (Electronic)	9783319930312
ISBN (Print)	9783319930305
DOIs	https://doi.org/10.1007/978-3-319-93031-2_22
Publication status	Published - 2018
Event	15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018 - Delft, Netherlands Duration: 26 Jun 2018 → 29 Jun 2018 Conference number: 15 https://sites.google.com/view/cpaior2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10848
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018
Abbreviated title	CPAIOR
Country/Territory	Netherlands
City	Delft
Period	26/06/18 → 29/06/18
Internet address	https://sites.google.com/view/cpaior2018

Access to Document

10.1007/978-3-319-93031-2_22

Cite this

Hoffmann, R., McCreesh, C., Ndiaye, S. N., Prosser, P., Reilly, C., Solnon, C., & Trimble, J. (2018). Observations from parallelising three maximum common (Connected) subgraph algorithms. In W.-J. van Hoeve (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings (pp. 298-315). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10848). Springer. https://doi.org/10.1007/978-3-319-93031-2_22

Hoffmann, Ruth ; McCreesh, Ciaran ; Ndiaye, Samba Ndojh et al. / Observations from parallelising three maximum common (Connected) subgraph algorithms. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings. editor / Willem-Jan van Hoeve. Cham : Springer, 2018. pp. 298-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4dae15ecfd674bdbbeabcbb1285c5630,

title = "Observations from parallelising three maximum common (Connected) subgraph algorithms",

abstract = "We discuss our experiences adapting three recent algorithms for maximum common (connected) subgraph problems to exploit multi-core parallelism. These algorithms do not easily lend themselves to parallel search, as the search trees are extremely irregular, making balanced work distribution hard, and runtimes are very sensitive to value-ordering heuristic behaviour. Nonetheless, our results show that each algorithm can be parallelised successfully, with the threaded algorithms we create being clearly better than the sequential ones. We then look in more detail at the results, and discuss how speedups should be measured for this kind of algorithm. Because of the difficulty in quantifying an average speedup when so-called anomalous speedups (superlinear and sublinear) are common, we propose a new measure called aggregate speedup.",

author = "Ruth Hoffmann and Ciaran McCreesh and Ndiaye, {Samba Ndojh} and Patrick Prosser and Craig Reilly and Christine Solnon and James Trimble",

year = "2018",

doi = "10.1007/978-3-319-93031-2_22",

language = "English",

isbn = "9783319930305",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "298--315",

editor = "{van Hoeve}, Willem-Jan",

booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research",

address = "Netherlands",

note = "15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018, CPAIOR ; Conference date: 26-06-2018 Through 29-06-2018",

url = "https://sites.google.com/view/cpaior2018",

}

Hoffmann, R, McCreesh, C, Ndiaye, SN, Prosser, P, Reilly, C, Solnon, C & Trimble, J 2018, Observations from parallelising three maximum common (Connected) subgraph algorithms. in W-J van Hoeve (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10848, Springer, Cham, pp. 298-315, 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018, Delft, Netherlands, 26/06/18. https://doi.org/10.1007/978-3-319-93031-2_22

Observations from parallelising three maximum common (Connected) subgraph algorithms. / Hoffmann, Ruth; McCreesh, Ciaran; Ndiaye, Samba Ndojh et al.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings. ed. / Willem-Jan van Hoeve. Cham: Springer, 2018. p. 298-315 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10848).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Observations from parallelising three maximum common (Connected) subgraph algorithms

AU - Hoffmann, Ruth

AU - McCreesh, Ciaran

AU - Ndiaye, Samba Ndojh

AU - Prosser, Patrick

AU - Reilly, Craig

AU - Solnon, Christine

AU - Trimble, James

N1 - Conference code: 15

PY - 2018

Y1 - 2018

N2 - We discuss our experiences adapting three recent algorithms for maximum common (connected) subgraph problems to exploit multi-core parallelism. These algorithms do not easily lend themselves to parallel search, as the search trees are extremely irregular, making balanced work distribution hard, and runtimes are very sensitive to value-ordering heuristic behaviour. Nonetheless, our results show that each algorithm can be parallelised successfully, with the threaded algorithms we create being clearly better than the sequential ones. We then look in more detail at the results, and discuss how speedups should be measured for this kind of algorithm. Because of the difficulty in quantifying an average speedup when so-called anomalous speedups (superlinear and sublinear) are common, we propose a new measure called aggregate speedup.

AB - We discuss our experiences adapting three recent algorithms for maximum common (connected) subgraph problems to exploit multi-core parallelism. These algorithms do not easily lend themselves to parallel search, as the search trees are extremely irregular, making balanced work distribution hard, and runtimes are very sensitive to value-ordering heuristic behaviour. Nonetheless, our results show that each algorithm can be parallelised successfully, with the threaded algorithms we create being clearly better than the sequential ones. We then look in more detail at the results, and discuss how speedups should be measured for this kind of algorithm. Because of the difficulty in quantifying an average speedup when so-called anomalous speedups (superlinear and sublinear) are common, we propose a new measure called aggregate speedup.

U2 - 10.1007/978-3-319-93031-2_22

DO - 10.1007/978-3-319-93031-2_22

M3 - Conference contribution

AN - SCOPUS:85048634638

SN - 9783319930305

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 298

EP - 315

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research

A2 - van Hoeve, Willem-Jan

PB - Springer

CY - Cham

T2 - 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2018

Y2 - 26 June 2018 through 29 June 2018

ER -

Hoffmann R, McCreesh C, Ndiaye SN, Prosser P, Reilly C, Solnon C et al. Observations from parallelising three maximum common (Connected) subgraph algorithms. In van Hoeve WJ, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018, Proceedings. Cham: Springer. 2018. p. 298-315. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2018 Jun 8. doi: 10.1007/978-3-319-93031-2_22

Observations from parallelising three maximum common (Connected) subgraph algorithms

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this