mathematics
and
computer
science

LANS

LANS Publications

"Improving Random Walk Performance"

I. Safro, P. Hovland, J. Shin, and M. Strout

Preprint ANL/MCS-P1585-0209

Preprint Version: [pdf]

Random walk simulation is employed in many experimental algorithmic applications. Ecient execution on modern computer architectur es demands that the random walk be implemented to exploit data locality for improving the cache performance. In this research, we demonstrate how different one-dimensional data reordering functionals can be used as a preprocessing step for speeding the random walk runtime.