Improving Data Locality for Irregular Partitioned Global Address Space Parallel Programs

This paper describes a technique for improving the data ref-erence locality of parallel programs using the Partitioned Global Address Space (PGAS) model of computation. One of the principal challenges in writing PGAS parallel appli-cations is maximizing communication efficiency. This work describes an on-line technique based on run-time data ref-erence profiling to organize fine-grained data elements into locality-aware blocks suitable for coarse-grained communi-cation. This technique is applicable to parallel applications with large, irregular, pointer-based applications. The de-scribed system can perform automatic data relayout using the locality-aware mapping with either iterative (timestep) based applications or as a collective data relayout opera-tion. An empirical evaluation of the approach shows that the technique is useful in increasing data reference local-ity and improves performance by 10-17 % on the SPLASH-2 Barnes-Hut tree benchmark