Optimizing the barnes-hut algorithm in UPC

Junchao Zhang, Babak Behzad, Marc Snir

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

Abstract

PGAS languages'support of a global name space facilitates the expression of parallel algorithms, since communication is implicit. 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. 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 the Barnes-Hut algorithm. A literal port of a good quality shared-memory implementation (merely replacing shared arrays with partitioned global arrays) achieves abysmal performance - more than 1000 times worse than a message-passing implementation. We achieve in UPC a performance comparable to message-passing with a series of optimizations. Most of these optimizations could be performed with limited changes in the source code using an enhanced run-time and a few language extensions or pragmas. We discuss the implications to the programmer, the compiler and PGAS languages themselves.

Original languageEnglish (US)
Title of host publicationProceedings of 2011 SC - International Conference for High Performance Computing, Networking, Storage and Analysis
DOIs
StatePublished - Dec 14 2011
Event2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC11 - Seattle, WA, United States
Duration: Nov 12 2011Nov 18 2011

Publication series

NameProceedings of 2011 SC - International Conference for High Performance Computing, Networking, Storage and Analysis

Other

Other2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC11
CountryUnited States
CitySeattle, WA
Period11/12/1111/18/11

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Optimizing the barnes-hut algorithm in UPC'. Together they form a unique fingerprint.

  • Cite this

    Zhang, J., Behzad, B., & Snir, M. (2011). Optimizing the barnes-hut algorithm in UPC. In Proceedings of 2011 SC - International Conference for High Performance Computing, Networking, Storage and Analysis [75] (Proceedings of 2011 SC - International Conference for High Performance Computing, Networking, Storage and Analysis). https://doi.org/10.1145/2063384.2063485