Optimizing the Barnes-Hut Algorithm in UPC

Zhang, Junchao; Behzad, Babak; Snir, Marc

Permalink

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

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

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

Language

en

Permalink

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

Owning Collections