Parallel Algorithms in Computational Science

ISBN-13: 9783642762673 / Angielski / Miękka / 2011 / 183 str.

Dieter W. Heermann; Anthony N. Burkitt

Opis

Our aim in this book is to present and enlarge upon those aspects of parallel computing that are needed by practitioners of computational science. Today al most all classical sciences, such as mathematics, physics, chemistry and biology, employ numerical methods to help gain insight into nature. In addition to the traditional numerical methods, such as matrix inversions and the like, a whole new field of computational techniques has come to assume central importance, namely the numerical simulation methods. These methods are much less fully developed than those which are usually taught in a standard numerical math ematics course. However, they form a whole new set of tools for research in the physical sciences and are applicable to a very wide range of problems. At the same time there have been not only enormous strides forward in the speed and capability of computers but also dramatic new developments in computer architecture, and particularly in parallel computers. These improvements offer exciting prospects for computer studies of physical systems, and it is the new techniques and methods connected with such computer simulations that we seek to present in this book, particularly in the light of the possibilities opened up by parallel computers. It is clearly not possible at this early stage to write a definitive book on simulation methods and parallel computing."

Spis treści

1. Introduction.- 2. Computer Simulation Methods.- 2.1 Essential Features of Simulation Methods.- 2.1.1 Ensemble Averages on a Computer.- 2.1.2 Simulation Algorithms.- 2.2 The Monte Carlo Algorithm.- 2.2.1 Simple Sampling.- 2.2.2 Importance Sampling.- 2.2.3 Interpretation of the Monte Carlo Process as a Dynamical Process.- 2.3 Molecular Dynamics.- 2.3.1 The Microcanonical Ensemble.- 2.3.2 Discretization and Systematic Effects.- 2.3.3 Molecular Dynamics Algorithms.- 2.4 Hybrid Molecular Dynamics.- 2.5 Accuracy Considerations and Finite-Size Problems.- 2.5.1 Choosing the Boundary Conditions.- 2.5.2 Effects of Finite Simulation Time.- 2.5.3 Statistical Errors and Self-Averaging.- 2.5.4 Finite-Size Scaling: Using Finite-Size Effects.- 2.6 Monte Carlo Algorithm for the Ising Model.- 2.6.1 The Ising Model.- 2.6.2 Implementing the Monte Carlo Algorithm for the Ising Model.- 2.6.3 The Swendsen-Wang Algorithm and the Equivalence Between the Ising Model and Percolation.- 2.6.4 Cluster Identification.- 2.6.5 Other Cluster Update Algorithms.- 3. Physics and Parallelism.- 4. Concepts of Parallelism.- 4.1 Some Basic Definitions.- 4.2 The Complexity of Computation.- 4.3 More on Models and Methods.- 4.4 Performance Measurements.- 5. Parallel Machines and Languages.- 5.1 General Purpose Parallel Computers.- 5.1.1 Processor Concepts.- 5.1.2 Communication Networks.- 5.2 Parallel Machines for Special Physics Problems.- 5.2.1 Monte Carlo Machines.- 5.2.2 Molecular Dynamics Computers.- 5.3 Languages for Parallel Computers.- 5.4 The Matching Problem.- 6. Replication Algorithms.- 7. Geometrically Parallel Algorithms.- 7.1 Geometric Parallelization.- 7.2 Strips, Squares and Checker-Boards.- 7.2.1 Detailed Balance and the Checker-Board.- 7.2.2 Strips.- 7.2.3 Squares.- 7.2.4 Communication Procedures.- 7.2.5 Timing and Efficiency Considerations.- 7.2.6 Geometric Parallelism in Higher Dimensions.- 7.3 Non-local and Cluster Algorithms.- 7.3.1 Parallel Algorithms for Cluster Identification.- 7.3.2 The Public Stack Cluster Algorithm.- 7.3.3 The Binary Tree Cluster Algorithm.- 7.3.4 Performance Measurements.- 7.4 Parallel Molecular Dynamics Algorithms.- 7.4.1 Short-Range vs Long-Range Interactions.- 7.4.2 A Geometrically Parallelized Algorithm for Molecular Dynamics.- 7.5 Hybrid Molecular Dynamics.- 7.6 Polymers on the Lattice.- 7.6.1 Single Polymers.- 7.6.2 Dense Polymer Systems.- 7.7 Off-Lattice Polymers.- 7.8 Hybrid Molecular Dynamics for Polymers.- 7.9 Limits of Geometric Parallelization.- 8. Data Parallel Algorithms.- 8.1 Data Parallel Algorithm for Long-Range Interactions.- 8.2 Polymers.- 9. Introduction to a Parallel Language.- 9.1 Transputer-Based Parallel Machines.- 9.2 Parallel Programming in Occam.- 9.2.1 The Process and the Channel Concepts.- 9.2.2 Two Elementary Processes.- 9.2.3 A Trivial Example ..- 9.2.4 Repetition and the Conditional.- 9.2.5 An Occam Program for the Ising Model.- 9.2.6 More on Choices and Selection.- 9.2.7 Further Language Elements.- 9.2.8 Arithmetic.- 9.2.9 Placements.- Appendices.- A. A Parallel Ising Model Program.- B. Random Number Generator.- C. A Parallel Molecular Dynamics Program.- References.