Argonne National Laboratory

PGAS with Lightweight Threads and the Barnes-Hut Algorithm

TitlePGAS with Lightweight Threads and the Barnes-Hut Algorithm
Publication TypeReport
Year of Publication2014
AuthorsDang, H, Brooks, A, Dryden, N, Snir, M
Other NumbersANL/MCS-P5217-1014

We describe a novel runtime system that integrates lightweight threads with a partitioned global address space (PGAS) mode of computation and apply it to the Barnes-Hut (BH) algorithm. Our model combines the power of low-latency, zero-copy, one-sided communication via PGAS with the power of fast context-switching and user-managed preemptive lightweight threads into a hybrid interface. We describe the challenges in designing such a runtime system, analyze approaches and trade-offs, and present benchmark results. Our BH application exemplifies the usage of the model and shows how we can obtain a simple, yet efficient and scalable, algorithm. Our implementation improves on a state-of-the-art implementation by up to 13 times. The hybrid model also improves the performance of various multi-threaded micro-benchmarks on a distributed memory cluster.