Files in this item



application/pdfBH-UPC.pdf (1MB)
(no description provided)PDF


Title:Optimizing the Barnes-Hut Algorithm in UPC
Author(s):Zhang, Junchao; Behzad, Babak; Snir, Marc
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.
Issue Date:2011-02-27
Genre:Technical Report
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Date Available in IDEALS:2011-02-27

This item appears in the following Collection(s)

Item Statistics