Paper Info
Title
A Highly Parallel Reuse Distance Analysis Algorithm on GPUs
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.
Year
DOI
Venue
2012
10.1109/IPDPS.2012.100
IPDPS
Keywords
Field
DocType
traditional reuse distance analysis,hybrid data structure,probabilistic model,traditional tree representation,memory access trace,highly-parallel reuse distance analysis,original sequential algorithm,spmd execution model,traditional sequential algorithm,parallel reuse distance analysis,reuse distance analysis,parallel algorithms,merging,hash table,instruction sets,probabilistic logic,tree data structures,algorithm design and analysis
SPMD,Algorithm design,Computer science,Parallel algorithm,Parallel computing,Tree (data structure),Algorithm,Graphics processing unit,Sequential algorithm,Speedup,Distributed computing,Hash table
Conference
ISSN
Citations 
PageRank 
1530-2075
9
0.50
References 
Authors
22
6
Name
Order
Citations
PageRank
Huimin Cui111911.40
Qing Yi219011.89
Jingling Xue31627124.20
Lei Wang4866.56
Yang Yang5482.81
Xiaobing Feng6906112.55