Optimizing the Barnes-Hut algorithm in UPC
Optimizing the Barnes-Hut algorithm in UPC
复制标题
优化 UPC 中的 Barnes-Hut 算法
DOI：
10.1145/2063384.2063485
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Snir
中科院分区：
文献类型：
--
作者：
Junchao Zhang;Babak Behzad;M. Snir
PGAS语言对全局命名空间的支持促进了并行算法的表达，因为通信是隐式的。这在编写具有数据依赖性、动态变化的通信模式的不规则应用程序时特别方便。然而，在没有显式通信控制的情况下，以共享内存风格编程可能会导致较差的性能。这个问题可能是由于PGAS语言当前实现的弱点或这些语言固有的限制。为了澄清这是什么情况下，我们讨论了在UPC的Barnes-Hut算法的实现。一个高质量的共享内存实现的文字端口（仅仅用分区的全局数组替换共享数组）实现了糟糕的性能-比消息传递实现差1000倍以上。通过一系列优化，我们在UPC中实现了与消息传递相当的性能。这些优化中的大多数都可以通过使用增强的运行时和一些语言扩展或杂注对源代码进行有限的更改来执行。我们讨论的影响，程序员，编译器和PGAS语言本身。
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.