University of Illinois Urbana-Champaign

Optimizing the Barnes-Hut Algorithm in UPC

Zhang, Junchao; Behzad, Babak; Snir, Marc

Content Files
BH-UPC.pdf

Permalink

https://hdl.handle.net/2142/18699

Description

Title
Optimizing the Barnes-Hut Algorithm in UPC
Author(s)
  • Zhang, Junchao
  • Behzad, Babak
  • Snir, Marc
Issue Date
2011-02-27
Keyword(s)
  • N-body
  • Barnes-Hut
  • PGAS
  • UPC
Date of Ingest
2011-02-27T22:02:10Z
Abstract
Partitioned global address space (PGAS) languages like UPC or Fortran provide a global name space to the user. This facilitates the expression of parallel algorithms, since communication is implicit, as compared to message passing where communication is explicit. This is especially convenient when writing irregular applications with data-dependent, dynamically changing communication patterns. However, programming in a shared memory style, with no explicit control of communication, may result in poor performance in PGAS languages. The problem may be due to weaknesses of current implementations of PGAS languages or limitations inherent in these languages. To clarify which is the case, we discuss an implementation in UPC of a representative irregular application, namely the Barnes-Hut algorithm. We have implemented a series of optimizations that have improved the performance of this application above 1600 times compared with a baseline, naive, shared-memory style implementation. We then discuss the implications to the programmer, the compiler and PGAS languages themselves.
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/18699

Owning Collections

Research and Tech Reports - Computer Science PRIMARY