Principles of Parallel Scientific Computing: A First Guide to Numerical Concepts and Programming Methods (Undergraduate Topics in Computer Science)

Preface
	Why This Book
	Mission Statement
	Structure and Style
	Acknowledgements
	Learning and Teaching Mode
Contents
Part I Introduction: Why to Study the Subject
1 The Pillars of Science
	1.1 A Third Pillar?
	1.2 Computational X
	1.3 About the Style of the Text and Some Shortcomings
2 Moore Myths
	2.1 Moore's Law
	2.2 Dennard Scaling
	2.3 The Three Layers of Parallelism
3 Our Model Problem (Our First Encounter with the Explicit Euler)
	3.1 The N-Body Problem
	3.2 Time Discretisation: Running a Movie
	3.3 Numerical Versus Analytical Solutions
Wrap-up
Part II How the Machine Works
4 Floating Point Numbers
	4.1 Fixed Point Formats
	4.2 Floating Point Numbers
		4.2.1 Normalisation
		4.2.2 The IEEE Format
		4.2.3 Realising Floating-Point Support
	4.3 Machine Precision
	4.4 Programming Guidelines
5 A Simplistic Machine Model
	5.1 Blueprint of a Computer's Execution Workflow
	5.2 A Working SISD Example
	5.3 Flaws
Wrap-up
Part III Floating Point Number Crunching
6 Round-Off Error Propagation
	6.1 Inexact Arithmetics
	6.2 Round-Off Error Analysis
	6.3 Programming Recipes
7 SIMD Vector Crunching
	7.1 SIMD in Flynn's Taxonomy
	7.2 Suitable Code Snippets
	7.3 Hardware Realisation Flavours
		7.3.1 Large Vector Registers
		7.3.2 Lockstepping
		7.3.3 Branching
8 Arithmetic Stability of an Implementation
	8.1 Arithmetic Stability
	8.2 Stability of Some Example Problems
		8.2.1 The N-Body Model Problem
		8.2.2 Logistic Growth
		8.2.3 Scalar Product
9 Vectorisation of the Model Problem
	9.1 Compiler Feedback
	9.2 Explicit Vectorisation with OpenMP
		9.2.1 The simd Pragma
		9.2.2 Loop Collapsing
		9.2.3 Aliasing
		9.2.4 Reductions
		9.2.5 Functions
Wrap-up
Part IV Basic Numerical Techniques and Terms
10 Conditioning and Well-Posedness
	10.1 Condition Number
	10.2 The Condition Number for Linear Equation Systems
	10.3 Backward Stability: Arithmetic Stability Revisited
11 Taylor Expansion
	11.1 Taylor
	11.2 Functions with Multiple Arguments
	11.3 Applications of Taylor Expansion
12 Ordinary Differential Equations
	12.1 Terminology
	12.2 Attractive and Stable Solutions to ODEs
	12.3 Approximation of ODEs Through Taylor Expansion
13 Accuracy and Appropriateness of Numerical Schemes
	13.1 Stability
	13.2 Convergence
	13.3 Convergence Plots
Wrap-up
Part V Using a Multicore Computer
14 Writing Parallel Code
	14.1 MIMD in Flynn's Taxonomy
	14.2 BSP
	14.3 Realisation of Our Approach
15 Upscaling Models and Scaling Measurements
	15.1 Strong Scaling
	15.2 Weak Scaling
	15.3 Comparison
	15.4 Data Presentation
16 OpenMP Primer: BSP on Multicores
	16.1 A First (Working) OpenMP Code
	16.2 Suitable For-Loops
	16.3 Thread Information Exchange
		16.3.1 Read and Write Access Protection
		16.3.2 Variable Visibility
		16.3.3 All-to-One Thread Synchronisation
	16.4 Grain Sizes and Scheduling
17 Shared Memory Tasking
	17.1 Task Graphs Revisited
	17.2 Basics of OpenMP Tasking
		17.2.1 The Task Dependency Graph and Ready Tasks
		17.2.2 Task Synchronisation
		17.2.3 Variations of the Example
	17.3 Task Properties and Data Visibility
	17.4 Task Dependencies
18 GPGPUs with OpenMP
	18.1 Informal Sketch of GPU Hardware
		18.1.1 Memory
		18.1.2 Streaming Multiprocessors
		18.1.3 Core Design
	18.2 GPU Offloading
	18.3 Multi-SM Codes
	18.4 Data Movement and Management on GPUs
		18.4.1 Moving Arrays to and From the Device
		18.4.2 Data Management and Explicit Data Movements
		18.4.3 Explicit data transfer
		18.4.4 Overlapping data transfer and computations
	18.5 Collectives
	18.6 Functions and Structs on GPUs
Wrap-up
Part VI Faster and More Accurate Numerical Codes
19 Higher Order Methods
	19.1 An Alternative Interpretation of Time Stepping
	19.2 Adams-Bashforth
	19.3 Runge-Kutta Methods
		19.3.1 Accuracy
		19.3.2 Cost and Parallelisation
	19.4 Leapfrog
20 Adaptive Time Stepping
	20.1 Motivation: A Very Simple Two-Grid Method
	20.2 Formalisation
	20.3 Error Estimators and Adaptivity Strategies
		20.3.1 Adaptive Time Stepping
		20.3.2 Local Time Stepping
		20.3.3 p-Refinement
	20.4 Hard-Coded Refinement Strategies
Wrap-up
A Using the Text
	A.1 Course Organisation
	A.2 What I Have Not Covered (But Maybe Should Have Done)
	A.3 Notation Used Throughout the Book
	A.4 Useful Software
B Cheat Sheet: System Benchmarking
	B.1 Looking Up Your Hardware
	B.2 Compute the Theoretical Capability (Peak Performance)
	B.3 Determine Effective Bandwidth
C Cheat Sheet: Performance Assessment
	C.1 Compiler Options
	C.2 Getting OpenMP Right
	C.3 Assessing the Code
		C.3.1 Code Characterisation
		C.3.2 Diving into the Code
		C.3.3 Next Steps
D Cheat Sheet: Calibrating the Upscaling Models
	D.1 Two-Point Calibration
	D.2 Runtime Normalisation
E Cheat Sheet: Convergence and Stability Studies
	E.1 Construct Test Scenarios
	E.2 Choosing the Right Norms
	E.3 Interpreting Your Data
F Cheat Sheet: Data Presentation
	F.1 Tables
	F.2 Graphs
	F.3 Formulae
	F.4 Integrating Figures and Tables into Your Write-Up
Index