Accelerating minimum spanning forest computations on multicore platforms

Guojing Cong; Ilie Tanase; Yinglong Xia

doi:10.1007/978-3-319-27308-2_44

Accelerating minimum spanning forest computations on multicore platforms

Guojing Cong, Ilie Tanase, Yinglong Xia

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

Abstract

We propose new approaches for accelerating minimum spanning forest algorithms on shared-memory platforms. Our approaches improve cache performance and reduce synchronization overhead of the base algorithms. On our target platform these optimizations achieve up to an order of magnitude speedup over the best prior parallel Borůvka implementation.

Original language	English
Title of host publication	Euro-Par 2015
Subtitle of host publication	Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers
Editors	Sascha Hunold, Josef Weidendorfer, Domingo Gimenez, Laura Ricci, Stefan Lankes, Alexandru Costan, Ana Lucia Varbanescu, Stephen L. Scott, María Engracia Gómez Requena, Vittorio Scarano, Alexandru Iosup, Michael Alexander
Publisher	Springer Verlag
Pages	541-552
Number of pages	12
ISBN (Print)	9783319273075
DOIs	https://doi.org/10.1007/978-3-319-27308-2_44
State	Published - 2015
Externally published	Yes
Event	International Workshops on Parallel Processing Workshops, Euro-Par 2015 - Vienna, Austria Duration: Aug 24 2015 → Aug 25 2015

Publication series

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

Conference

Conference	International Workshops on Parallel Processing Workshops, Euro-Par 2015
Country/Territory	Austria
City	Vienna
Period	08/24/15 → 08/25/15

Keywords

Locality
Minimum spanning forest
Synchronization

Access to Document

10.1007/978-3-319-27308-2_44

Cite this

Cong, G., Tanase, I., & Xia, Y. (2015). Accelerating minimum spanning forest computations on multicore platforms. In S. Hunold, J. Weidendorfer, D. Gimenez, L. Ricci, S. Lankes, A. Costan, A. L. Varbanescu, S. L. Scott, M. E. G. Requena, V. Scarano, A. Iosup, & M. Alexander (Eds.), Euro-Par 2015: Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers (pp. 541-552). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9523). Springer Verlag. https://doi.org/10.1007/978-3-319-27308-2_44

Cong, Guojing ; Tanase, Ilie ; Xia, Yinglong. / Accelerating minimum spanning forest computations on multicore platforms. Euro-Par 2015: Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers. editor / Sascha Hunold ; Josef Weidendorfer ; Domingo Gimenez ; Laura Ricci ; Stefan Lankes ; Alexandru Costan ; Ana Lucia Varbanescu ; Stephen L. Scott ; María Engracia Gómez Requena ; Vittorio Scarano ; Alexandru Iosup ; Michael Alexander. Springer Verlag, 2015. pp. 541-552 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ec085cbc1c3b4dc091445d118a68ff10,

title = "Accelerating minimum spanning forest computations on multicore platforms",

abstract = "We propose new approaches for accelerating minimum spanning forest algorithms on shared-memory platforms. Our approaches improve cache performance and reduce synchronization overhead of the base algorithms. On our target platform these optimizations achieve up to an order of magnitude speedup over the best prior parallel Borůvka implementation.",

keywords = "Locality, Minimum spanning forest, Synchronization",

author = "Guojing Cong and Ilie Tanase and Yinglong Xia",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; International Workshops on Parallel Processing Workshops, Euro-Par 2015 ; Conference date: 24-08-2015 Through 25-08-2015",

year = "2015",

doi = "10.1007/978-3-319-27308-2_44",

language = "English",

isbn = "9783319273075",

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

publisher = "Springer Verlag",

pages = "541--552",

editor = "Sascha Hunold and Josef Weidendorfer and Domingo Gimenez and Laura Ricci and Stefan Lankes and Alexandru Costan and Varbanescu, {Ana Lucia} and Scott, {Stephen L.} and Requena, {Mar{\'i}a Engracia G{\'o}mez} and Vittorio Scarano and Alexandru Iosup and Michael Alexander",

booktitle = "Euro-Par 2015",

}

Cong, G, Tanase, I & Xia, Y 2015, Accelerating minimum spanning forest computations on multicore platforms. in S Hunold, J Weidendorfer, D Gimenez, L Ricci, S Lankes, A Costan, AL Varbanescu, SL Scott, MEG Requena, V Scarano, A Iosup & M Alexander (eds), Euro-Par 2015: Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9523, Springer Verlag, pp. 541-552, International Workshops on Parallel Processing Workshops, Euro-Par 2015, Vienna, Austria, 08/24/15. https://doi.org/10.1007/978-3-319-27308-2_44

Accelerating minimum spanning forest computations on multicore platforms. / Cong, Guojing; Tanase, Ilie; Xia, Yinglong.
Euro-Par 2015: Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers. ed. / Sascha Hunold; Josef Weidendorfer; Domingo Gimenez; Laura Ricci; Stefan Lankes; Alexandru Costan; Ana Lucia Varbanescu; Stephen L. Scott; María Engracia Gómez Requena; Vittorio Scarano; Alexandru Iosup; Michael Alexander. Springer Verlag, 2015. p. 541-552 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9523).

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

TY - GEN

T1 - Accelerating minimum spanning forest computations on multicore platforms

AU - Cong, Guojing

AU - Tanase, Ilie

AU - Xia, Yinglong

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - We propose new approaches for accelerating minimum spanning forest algorithms on shared-memory platforms. Our approaches improve cache performance and reduce synchronization overhead of the base algorithms. On our target platform these optimizations achieve up to an order of magnitude speedup over the best prior parallel Borůvka implementation.

AB - We propose new approaches for accelerating minimum spanning forest algorithms on shared-memory platforms. Our approaches improve cache performance and reduce synchronization overhead of the base algorithms. On our target platform these optimizations achieve up to an order of magnitude speedup over the best prior parallel Borůvka implementation.

KW - Locality

KW - Minimum spanning forest

KW - Synchronization

UR - http://www.scopus.com/inward/record.url?scp=84951981928&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-27308-2_44

DO - 10.1007/978-3-319-27308-2_44

M3 - Conference contribution

AN - SCOPUS:84951981928

SN - 9783319273075

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

SP - 541

EP - 552

BT - Euro-Par 2015

A2 - Hunold, Sascha

A2 - Weidendorfer, Josef

A2 - Gimenez, Domingo

A2 - Ricci, Laura

A2 - Lankes, Stefan

A2 - Costan, Alexandru

A2 - Varbanescu, Ana Lucia

A2 - Scott, Stephen L.

A2 - Requena, María Engracia Gómez

A2 - Scarano, Vittorio

A2 - Iosup, Alexandru

A2 - Alexander, Michael

PB - Springer Verlag

T2 - International Workshops on Parallel Processing Workshops, Euro-Par 2015

Y2 - 24 August 2015 through 25 August 2015

ER -

Cong G, Tanase I, Xia Y. Accelerating minimum spanning forest computations on multicore platforms. In Hunold S, Weidendorfer J, Gimenez D, Ricci L, Lankes S, Costan A, Varbanescu AL, Scott SL, Requena MEG, Scarano V, Iosup A, Alexander M, editors, Euro-Par 2015: Parallel Processing Workshops - Euro-Par 2015 International Workshops, Revised Selected Papers. Springer Verlag. 2015. p. 541-552. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-27308-2_44

Accelerating minimum spanning forest computations on multicore platforms

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this