Composable Locality Optimizations for Accelerating Parallel Forest Computations

Guojing Cong; Ilie Tanase

doi:10.1109/HPCC-SmartCity-DSS.2016.0037

Composable Locality Optimizations for Accelerating Parallel Forest Computations

Guojing Cong, Ilie Tanase

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

3 Scopus citations

Abstract

Graph algorithms with large, sparse inputs oftentimes perform poorly on cache-based platforms. For parallel spanning forest and minimum spanning forest computations, we propose three locality optimizations, Update, Stages, and PSM, that improve the cache performance. Update exploits the 'graft-and-shortcut' pattern of the base algorithms. PSM transforms irregular accesses into regular ones. Stages is a meta approach based on evolution random graph theory that we use to combine Update and Stages. On the target platform, our combined optimization achieves up to 19 times speedups over the base algorithms.

Original language	English
Title of host publication	Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016
Editors	Laurence T. Yang, Jinjun Chen
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	190-197
Number of pages	8
ISBN (Electronic)	9781509042968
DOIs	https://doi.org/10.1109/HPCC-SmartCity-DSS.2016.0037
State	Published - Jan 20 2017
Externally published	Yes
Event	18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016 - Sydney, Australia Duration: Dec 12 2016 → Dec 14 2016

Publication series

Name	Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016

Conference

Conference	18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016
Country/Territory	Australia
City	Sydney
Period	12/12/16 → 12/14/16

Keywords

Cache performance
Locality
Minimum spanning forest
Spanning forest

Access to Document

10.1109/HPCC-SmartCity-DSS.2016.0037

Cite this

Cong, G., & Tanase, I. (2017). Composable Locality Optimizations for Accelerating Parallel Forest Computations. In L. T. Yang, & J. Chen (Eds.), Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016 (pp. 190-197). Article 7828378 (Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/HPCC-SmartCity-DSS.2016.0037

Cong, Guojing ; Tanase, Ilie. / Composable Locality Optimizations for Accelerating Parallel Forest Computations. Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016. editor / Laurence T. Yang ; Jinjun Chen. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 190-197 (Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016).

@inproceedings{d812a31cb5ab427f81b181ad64b1b85d,

title = "Composable Locality Optimizations for Accelerating Parallel Forest Computations",

abstract = "Graph algorithms with large, sparse inputs oftentimes perform poorly on cache-based platforms. For parallel spanning forest and minimum spanning forest computations, we propose three locality optimizations, Update, Stages, and PSM, that improve the cache performance. Update exploits the 'graft-and-shortcut' pattern of the base algorithms. PSM transforms irregular accesses into regular ones. Stages is a meta approach based on evolution random graph theory that we use to combine Update and Stages. On the target platform, our combined optimization achieves up to 19 times speedups over the base algorithms.",

keywords = "Cache performance, Locality, Minimum spanning forest, Spanning forest",

author = "Guojing Cong and Ilie Tanase",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2017",

month = jan,

day = "20",

doi = "10.1109/HPCC-SmartCity-DSS.2016.0037",

language = "English",

series = "Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "190--197",

editor = "Yang, \{Laurence T.\} and Jinjun Chen",

booktitle = "Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016",

}

Cong, G & Tanase, I 2017, Composable Locality Optimizations for Accelerating Parallel Forest Computations. in LT Yang & J Chen (eds), Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016., 7828378, Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016, Institute of Electrical and Electronics Engineers Inc., pp. 190-197, 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016, Sydney, Australia, 12/12/16. https://doi.org/10.1109/HPCC-SmartCity-DSS.2016.0037

Composable Locality Optimizations for Accelerating Parallel Forest Computations. / Cong, Guojing; Tanase, Ilie.
Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016. ed. / Laurence T. Yang; Jinjun Chen. Institute of Electrical and Electronics Engineers Inc., 2017. p. 190-197 7828378 (Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016).

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

TY - GEN

T1 - Composable Locality Optimizations for Accelerating Parallel Forest Computations

AU - Cong, Guojing

AU - Tanase, Ilie

PY - 2017/1/20

Y1 - 2017/1/20

N2 - Graph algorithms with large, sparse inputs oftentimes perform poorly on cache-based platforms. For parallel spanning forest and minimum spanning forest computations, we propose three locality optimizations, Update, Stages, and PSM, that improve the cache performance. Update exploits the 'graft-and-shortcut' pattern of the base algorithms. PSM transforms irregular accesses into regular ones. Stages is a meta approach based on evolution random graph theory that we use to combine Update and Stages. On the target platform, our combined optimization achieves up to 19 times speedups over the base algorithms.

AB - Graph algorithms with large, sparse inputs oftentimes perform poorly on cache-based platforms. For parallel spanning forest and minimum spanning forest computations, we propose three locality optimizations, Update, Stages, and PSM, that improve the cache performance. Update exploits the 'graft-and-shortcut' pattern of the base algorithms. PSM transforms irregular accesses into regular ones. Stages is a meta approach based on evolution random graph theory that we use to combine Update and Stages. On the target platform, our combined optimization achieves up to 19 times speedups over the base algorithms.

KW - Cache performance

KW - Locality

KW - Minimum spanning forest

KW - Spanning forest

UR - https://www.scopus.com/pages/publications/85013664204

U2 - 10.1109/HPCC-SmartCity-DSS.2016.0037

DO - 10.1109/HPCC-SmartCity-DSS.2016.0037

M3 - Conference contribution

AN - SCOPUS:85013664204

T3 - Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016

SP - 190

EP - 197

BT - Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016

A2 - Yang, Laurence T.

A2 - Chen, Jinjun

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016

Y2 - 12 December 2016 through 14 December 2016

ER -

Cong G, Tanase I. Composable Locality Optimizations for Accelerating Parallel Forest Computations. In Yang LT, Chen J, editors, Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016. Institute of Electrical and Electronics Engineers Inc. 2017. p. 190-197. 7828378. (Proceedings - 18th IEEE International Conference on High Performance Computing and Communications, 14th IEEE International Conference on Smart City and 2nd IEEE International Conference on Data Science and Systems, HPCC/SmartCity/DSS 2016). doi: 10.1109/HPCC-SmartCity-DSS.2016.0037

Composable Locality Optimizations for Accelerating Parallel Forest Computations

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this