Cristobal A. Navarro, Fabrizio Canfora, Nancy Hitschfeld Kahler
Computing the partition function of a spin lattice is known to be a \textit{NP-hard} problem that becomes intractable as the size of the lattice increases. More in detail, the time needed to compute the transfer matrix for a given \textit{strip lattice} grows exponentially as a function $T(|V|,|E|)$ of vertices and edges. There is a high interest in knowing the exact partition functions of many different strip lattices since they provide a first approach on knowing the eventual phase transitions at the thermodynamical equilibrium in the full plane. With the fast evolution of CPUs and GPUs towards a higher number of cores, parallel computing becomes fundamental for reducing the computational time of $T(|V|,|E|)$. In this work, we implement a parallel method for computing the transfer matrix of any strip lattice. The solution utilizes a forest of subtrees of heigh $h=1$ that work as a cache for the computation of the rows. Also, the implementation is NUMA-aware and achieves scalable performance in multi-socket machines. Our experiments report speedups of up to $3x$ using a quad core machine and there is also an extra speedup of $2x$ when the problem is symmetric in topology.
View original:
http://arxiv.org/abs/1305.6325
No comments:
Post a Comment