Quarks, GPUs and Multigrid
by Prof. Richard Brower
Triple-A of Computational Science
This is a short course on multi-grid algorithms and GPU (data parallel) computing using Lattice QCD as the illustration. Advances in computational science require an artful synthesis of three elements: an application, advanced architectures and new algorithms. This course will be a case history for finding the intersection in the triple-A’s challenge of computational science.
Application ↔ Architecture ↔ Algorithm
Quarks ↔ GPUs ↔ Multigrid
Quarks and Beyond
“Quarks and beyond” physics is described by a space-time Quantum Field Theory (QFT). This is the goal of the new Large Hadron Collider (LHC) in Geneva, Switzerland.
Mysteries abound concerning the nature of mass, the source of dark matter, etc. Many quantum field theories, believed to be possible candidates for future physics, require numerical methods similar to Quantum Chromodynamics (QCD), the theory of quarks in the nucleus.
To numerically solve a QFT, a stochastic algorithm on a 4D space-time grid is required, resulting in very large sparse matrix equations that are solved with multigrid methods. This huge computational demand has inspired the development of computer architectures beginning in the 1980s with the Connection Machine, to the present with the IBM BlueGene series.
Data Parallel Architecture
Remarkable similarities to the data parallel idea of the Connection Machine have re-emerged with the modern GPU. But now many cores reside in a single chip, rather than a huge black cube! This is the beginning of a disruptive technology. The era of many-core computing and the rapid progress made over recent years in algorithmic research means that it is now possible to solve problems in computational science that were almost unimaginable a fews years ago.
A key computational algorithm needed to explore higher and higher resolutions, multigrid is a multi-resolution method. In this course, we will give an introduction to the classical multigrid methods. The new tricks used to adapting it for LFT and the intersection of the MG algorithm and GPU computing will also be discussed.
No prior experience will be assumed in this tail of the intersection of Quarks + GPUs + Multigrid.