A Graph Algorithm for a New Architecture and New Algorithms for Quantum State Evolution
Claire Ralph, Cornell University
I will give a brief overview of my practicum work and then talk about my latest work in quantum chemistry. While I spent my practicum (Sandia National Labs Albuquerque) working on developing Subgraph Isomorphism (SI) algorithms for the Cray XMT, my thesis research is in the field of electronic structure theory; developing high performance methods for quantum chemical computations.
Subgraph isomorphism (SI) is an important graph query problem that appearsin many disparate application fields. While formally NP-complete, there is a need for practical methods to handle large graphs. Unfortunately, graph algorithms tend to suffer poor performance due to the irregularity of access patterns within general graph data structures, arising from poor data locality, which translates to high memory latency. Distributed memory machines using the MPI-style programming paradigm also suffer poor performance because large general-purpose graphs are difficult to partition effectively. The result is that advances in high-performance solutions for graph algorithms are most likely to come through advances in both architectures and algorithms. One such architecture, the Cray XMT, is a specialized massively multithreaded shared memory machine that offers a potentially transformative environment in which to approach the problem. In particular, the XMT attempts to minimize the effects of poor partitioning through the use of globally addressable shared memory and a high thread-to-processor ratio which “tolerates” memory latency. Here, we explore the challenges of implementing SI algorithms based on the Ullmann and VF2 algorithms in the Cray XMT environment, where issues of memory contention, scheduling, and compiler parallelizability must be optimized. Viewing the Ullmann and VF2 algorithms as differing mainly in techniques used to prune the search space, we also explore the cost-benefit ratio of different levels of pruning. Our studies show that optimizing pruning, which is the main consideration in a serial environment, is often less important than minimizing memory contention. Indeed, on the Cray XMT architecture, we find the relatively simple Ullmann algorithm is scalable to thousands of threads and is most optimal on the graphs studied here.
Exact quantum chemical calculations also suffer from an exponentially scaling search space. This means the calculation of the exact Nuclear Magnetic Resonance (NMR) spectra is restricted to systems of size twenty spins. Here I discuss methods of employing physical knowledge (e.g., systems in their ground state inhabit a small, low energy, section of the Hilbert space) to truncate this search space. When used to calculate NMR spectra, these methods are known as State Space Restriction (SSR) and extend the range of tractability to systems of size forty spins. We would, however, like to extend this range to systems of size one hundred as well as find methods for predicting the results of the related, but more difficult to compute, spectroscopic method, Electronic Paramagnetic Resonance (EPR). I present new theoretical algorithms for these calculations using the Matrix Product State, a specialized computationally efficient tensor. I also present promising initial numerical results.
Abstract Author(s): Claire C. Ralph