A Highly Parallel Reuse Distance Analysis Algorithm on GPUs

Huimin Cui, Qing Yi, Jingling Xue, Lei Wang, Yang Yang, Xiaobing Feng
SKL Computer Architecture, Institute of Computing Technology, CAS, Beijing, China
26th IEEE International Parallel and Distributed Processing Symposium (IPDPS’12), 2012


   title={A Highly Parallel Reuse Distance Analysis Algorithm on GPUs},

   author={Cui, Huimin and Yi, Qing and Xue, Jingling and Wang, Lei and Yang, Yang and Feng, Xiaobing},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: