Title :
A Highly Parallel Reuse Distance Analysis Algorithm on GPUs
Author :
Cui, Huimin ; Yi, Qing ; Xue, Jingling ; Wang, Lei ; Yang, Yang ; Feng, Xiaobing
Author_Institution :
SKL Comput. Archit., Inst. of Comput. Technol., Beijing, China
Abstract :
Reuse distance analysis is a runtime approach that has been widely used to accurately model the memory system behavior of applications. However, traditional reuse distance analysis algorithms use tree-based data structures and are hard to parallelize, missing the tremendous computing power of modern architectures such as the emerging GPUs. This paper presents a highly-parallel reuse distance analysis algorithm (HP-RDA) to speedup the process using the SPMD execution model of GPUs. In particular, we propose a hybrid data structure of hash table and local arrays to flatten the traditional tree representation of memory access traces. Further, we use a probabilistic model to correct any loss of precision from a straightforward parallelization of the original sequential algorithm. Our experimental results show that using an NVIDIA GPU, our algorithm achieves a factor of 20 speedup over the traditional sequential algorithm with less than 1% loss in precision.
Keywords :
graphics processing units; parallel algorithms; parallel architectures; tree data structures; HP-RDA; NVIDIA GPU; SPMD execution model; hash table; highly-parallel reuse distance analysis algorithm; hybrid data structure; local arrays; memory access traces; memory system behavior; probabilistic model; runtime approach; sequential algorithm; tree representation; tree-based data structures; Algorithm design and analysis; Arrays; Graphics processing unit; Instruction sets; Merging; Probabilistic logic; GPU acceleration; Reuse distance; hash table;
Conference_Titel :
Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International
Conference_Location :
Shanghai
Print_ISBN :
978-1-4673-0975-2
DOI :
10.1109/IPDPS.2012.100