Originating as lecture notes for a one-semester course at the University of Wuppertal, this brief introductory textbook on algorithms for molecular dynamics and Monte Carlo methods stresses the importance of what the authors call “geometrically inspired parallelizations.” What they mean is that the connectivity or topology of the physical problem determines the most natural and most efficient topology for the parallel algorithm. We agree that physical partitioning is key to parallelizing algorithms in computational physics.
Chapter 1, “Introduction,” contains elementary, well-known material. Unfortunately, problem 1.1 contains an error, in that “O(k)” appears where “O(lg(k))” should. A few other typographical errors appear in this textbook, but none will be so annoying to the student.
Chapter 2, “Computer Simulation Methods,” introduces the Ising model to provide an illustration of the Monte Carlo method. The key words and phrases for this chapter are Hamiltonian, Boltzmann probability, partition function, Monte Carlo algorithms, Metropolis algorithm, and Verlet algorithm.
Chapter 3, “Physics and Parallelism,” opens with the statement, “Many of the methods to solve problems, both in physics and in other branches of science, lend themselves naturally to parallelization,” and continues in this vein to explain why geometrically inspired parallelizations are so natural.
Chapter 4, “Concepts of Parallelism,” begins with “the question…whether for a given physical system there is a formulation…and a method…that is optimal, in the sense that it has the highest degree of parallelism.” Next, the authors give some basic definitions of efficient and optimal parallel algorithm, NC class, inherent parallelism, and speedup. Section 4.3 poses two questions. First, given a formulation or description D (such as a molecular description or a continuum formulation of the dynamics of a material), does a computational method M (for instance, a Monte Carlo method or a finite element method) exist such that for all other methods M′, IP(D,M) ≥ IP (D,M′), where IP(D,M) is the inherent parallelism of the computational model (D,M)? Second, does an optimal pair (D,M) exist such that for all other pairs, IP(D,M) ≥ IP(D′,M′)? These open questions are fundamental and important, perhaps the most important, questions in parallel computational science.
Chapter 5, “Parallel Machines and Languages,” discusses the taxonomy and topology of parallel architectures in an elementary introductory fashion; a too-brief, superficial treatment of parallel languages is presented here. Chapter 6, “Replication Algorithms,” is an explanation of the sentence “The replication algorithm is the assignment of the algorithm A to all processors P1,…, PN and the assignment of the set of parameters {p1,…, pn} to the set of processors in a one-to-one (or many-to-one) mapping.” Chapter 7, “Geometrically Parallel Algorithms,” contains the following key words and phrases: domain decomposition, data parallelism, dynamic load balancing, granularity, topology, supernode, scattered domain decomposition, communication-to-computation ratio, grid topology, hypercubes, strips, stripes, slabs, slithering snakes, and reptation methods.
Chapter 8, “Data Parallel Algorithms,” discusses algorithms for long-range interactions and for polymers. Section 8.1 discusses an algorithm with a ring topology for two-body interactions of the inverse square law type. Section 8.2 considers other algorithms with ring topologies and discusses the desirability of an adaptable topology. Chapter 9, “Introduction to a Parallel Language,” is an introduction to Occam. The book contains three appendices: (A) “A Parallel Ising Model Program,” (B) “Random Number Generator,” and (C) “A Parallel Molecular Dynamics Program.” The authors provide eight pages of chapter-by-chapter references. The five-page subject index has some interesting omissions, such as the word “topology,” which appears on 16 pages of this book.
Our main criticism is that this book is not well written. Overall, however, it is a good brief introduction to Monte Carlo and molecular dynamics algorithms. We recommend it to the computational or computer scientist interested in learning about this area of computational physics.
