IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Optimizing the Barnes-Hut Algorithm in UPC

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/18699

Files in this item

File Description Format
PDF BH-UPC.pdf (1MB) (no description provided) PDF
Title: Optimizing the Barnes-Hut Algorithm in UPC
Author(s): Zhang, Junchao; Behzad, Babak; Snir, Marc
Subject(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.
Issue Date: 2011-02-27
Genre: Technical Report
Type: Text
Language: English
URI: http://hdl.handle.net/2142/18699
Publication Status: unpublished
Peer Reviewed: not peer reviewed
Date Available in IDEALS: 2011-02-27
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 391
  • Downloads this Month: 3
  • Downloads Today: 0

Browse

My Account

Information

Access Key