Spherical region queries on multicore architectures

Hao Lu; Sudip K. Seal; Wei Guo; Jonathan D. Poplawsky

doi:10.1145/3149704.3149772

Spherical region queries on multicore architectures

Hao Lu, Sudip K. Seal, Wei Guo, Jonathan D. Poplawsky

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

2 Scopus citations

Abstract

In this short paper, we report the performance of multiple threadparallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.

Original language	English
Title of host publication	Proceedings of IA3 2017
Subtitle of host publication	7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis
Publisher	Association for Computing Machinery, Inc
ISBN (Electronic)	9781450351362
DOIs	https://doi.org/10.1145/3149704.3149772
State	Published - Nov 12 2017
Event	7th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2017 - Denver, United States Duration: Nov 12 2017 → Nov 17 2017

Publication series

Name	Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis

Conference

Conference	7th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2017
Country/Territory	United States
City	Denver
Period	11/12/17 → 11/17/17

Funding

This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

Funders	Funder number
LLC
UT-Battelle

Keywords

Kd-tree
Multicore architecture
Range tree
Spherical region queries

Access to Document

10.1145/3149704.3149772

Cite this

Lu, H., Seal, S. K., Guo, W., & Poplawsky, J. D. (2017). Spherical region queries on multicore architectures. In Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis Article 3149772 (Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis). Association for Computing Machinery, Inc. https://doi.org/10.1145/3149704.3149772

Lu, Hao ; Seal, Sudip K. ; Guo, Wei et al. / Spherical region queries on multicore architectures. Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc, 2017. (Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis).

@inproceedings{7ade152313764523bb278e8f4e3701a2,

title = "Spherical region queries on multicore architectures",

abstract = "In this short paper, we report the performance of multiple threadparallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.",

keywords = "Kd-tree, Multicore architecture, Range tree, Spherical region queries",

author = "Hao Lu and Seal, {Sudip K.} and Wei Guo and Poplawsky, {Jonathan D.}",

note = "Publisher Copyright: {\textcopyright} 2017 Association for Computing Machinery.; 7th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2017 ; Conference date: 12-11-2017 Through 17-11-2017",

year = "2017",

month = nov,

day = "12",

doi = "10.1145/3149704.3149772",

language = "English",

series = "Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis",

publisher = "Association for Computing Machinery, Inc",

booktitle = "Proceedings of IA3 2017",

}

Lu, H, Seal, SK, Guo, W & Poplawsky, JD 2017, Spherical region queries on multicore architectures. in Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis., 3149772, Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis, Association for Computing Machinery, Inc, 7th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2017, Denver, United States, 11/12/17. https://doi.org/10.1145/3149704.3149772

Spherical region queries on multicore architectures. / Lu, Hao; Seal, Sudip K.; Guo, Wei et al.
Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc, 2017. 3149772 (Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis).

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

TY - GEN

T1 - Spherical region queries on multicore architectures

AU - Lu, Hao

AU - Seal, Sudip K.

AU - Guo, Wei

AU - Poplawsky, Jonathan D.

PY - 2017/11/12

Y1 - 2017/11/12

N2 - In this short paper, we report the performance of multiple threadparallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.

AB - In this short paper, we report the performance of multiple threadparallel algorithms for spherical region queries on multicore architectures motivated by a challenging data analytics application in materials science. Performances of two tree-based algorithms and a naive algorithm are compared to identify the length scales at which these approaches perform optimally. The optimal algorithm is then used to scale the driving materials science application, which is shown to deliver over 17X speedup using 32 OpenMP threads on data sets containing many millions of atoms.

KW - Kd-tree

KW - Multicore architecture

KW - Range tree

KW - Spherical region queries

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

U2 - 10.1145/3149704.3149772

DO - 10.1145/3149704.3149772

M3 - Conference contribution

AN - SCOPUS:85040128463

T3 - Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis

BT - Proceedings of IA3 2017

PB - Association for Computing Machinery, Inc

T2 - 7th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2017

Y2 - 12 November 2017 through 17 November 2017

ER -

Lu H, Seal SK, Guo W, Poplawsky JD. Spherical region queries on multicore architectures. In Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, Inc. 2017. 3149772. (Proceedings of IA3 2017: 7th Workshop on Irregular Applications: Architectures and Algorithms, Held in conjunction with SC 2017: The International Conference for High Performance Computing, Networking, Storage and Analysis). doi: 10.1145/3149704.3149772

Spherical region queries on multicore architectures

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this