Building on previous findings of HPC experts at RRZE, researchers from the University of Würzburg (Institute of Theoretical Physics) were able to optimize one of the bottlenecks in their code, the MARQOV software package. With this optimization, a speedup of a real-world example by about 15% was achieved.
Background – The Metropolis update rule applied to an exponential probability distribution forms the backbone of numerous Markov chain Monte Carlo techniques across all sciences. In the context of the MARQOV software package, we tried to optimize this basic building block further.
Analysis – In this context, the Metropolis update rule, r < e-dE, requires the comparison of a random real number r with the exponential of a real energy difference dE, and hence necessitates the evaluation of a special function, although both numbers often differ largely in magnitude.
Optimization – It turns out that this mismatch in the magnitudes of r and e-dE can be quantified and exploited for optimization. By using the bit representations of real numbers x = m*2^c on a computer in terms of a mantissa m and an exponent c it can often be decided by comparing c in the representation of the random number r with a suitably scaled version of the energy difference dE and hence the exact evaluation of the exponential is often not necessary.
Summary – Using this trick the throughput of the update rule could be improved by approximately 50%. Applied to the real-world example of simulations of the Heisenberg Model at the critical point with the Wolff-cluster update, in which the metropolis rule forms the kernel which is evaluated for a large amount of random numbers, this translates to a speedup of about 15%.
Building on previous findings of HPC experts at RRZE, researchers from the University of Würzburg (Institute of Theoretical Physics) were able to optimize one of the bottlenecks in their code, the MARQOV software package. With this optimization, a speedup of a real-world example by about 15% was achieved.
Background – The Metropolis update rule applied to an exponential probability distribution forms the backbone of numerous Markov chain Monte Carlo techniques across all sciences. In the context of the MARQOV software package, we tried to optimize this basic building block further.
Analysis – In this context, the Metropolis update rule, r < e-dE, requires the comparison of a random real number r with the exponential of a real energy difference dE, and hence necessitates the evaluation of a special function, although both numbers often differ largely in magnitude.
Optimization – It turns out that this mismatch in the magnitudes of r and e-dE can be quantified and exploited for optimization. By using the bit representations of real numbers x = m*2^c on a computer in terms of a mantissa m and an exponent c it can often be decided by comparing c in the representation of the random number r with a suitably scaled version of the energy difference dE and hence the exact evaluation of the exponential is often not necessary.
Summary – Using this trick the throughput of the update rule could be improved by approximately 50%. Applied to the real-world example of simulations of the Heisenberg Model at the critical point with the Wolff-cluster update, in which the metropolis rule forms the kernel which is evaluated for a large amount of random numbers, this translates to a speedup of about 15%.