Design and evaluation of a parallel HOP clustering algorithm for cosmological simulation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

Clustering, or unsupervised classification, has many uses in fields that depend on grouping results from large amount of data, an example being the N-body cosmological simulation in astrophysics. In this paper, we study a particular clustering algorithm used in astrophysics, called HOP, and present a parallel implementation to speed up its current sequential implementation. Our approach first builds in parallel the spatial domain hierarchical data structure, a three-dimensional KD tree. Using a KD tree, the core of the HOP algorithm that searches for the highest density neighbor can be performed using only subsets of the particles and hence the communication cost is reduced. We evaluate our implementation by using data sets from a production cosmological application. The experimental results demonstrate up to 24× speedup using 64 processors on three parallel processing machines.

Original languageEnglish (US)
Title of host publicationProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)0769519261, 9780769519265
DOIs
StatePublished - 2003
EventInternational Parallel and Distributed Processing Symposium, IPDPS 2003 - Nice, France
Duration: Apr 22 2003Apr 26 2003

Publication series

NameProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2003

Other

OtherInternational Parallel and Distributed Processing Symposium, IPDPS 2003
Country/TerritoryFrance
CityNice
Period4/22/034/26/03

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Software

Fingerprint

Dive into the research topics of 'Design and evaluation of a parallel HOP clustering algorithm for cosmological simulation'. Together they form a unique fingerprint.

Cite this