Introduction to High Performance Scientific Computing

Free

Description

Contents

Reviews

Language

English

ISBN

978-1-257-99254-6

I Theory

Single-processor Computing

The Von Neumann architecture

Modern processors

The processing cores

8-bit, 16-bit, 32-bit, 64-bit

Caches: on-chip memory

Graphics, controllers, special purpose hardware

Superscalar processing and instruction-level parallelism

Memory Hierarchies

Busses

Latency and Bandwidth

Registers

Caches

Prefetch streams

Concurrency and memory transfer

Memory banks

TLB and virtual memory

Multicore architectures

Cache coherence

Computations on multicore chips

Locality and data reuse

Data reuse and arithmetic intensity

Locality

Programming strategies for high performance

Peak performance

Pipelining

Cache size

Cache lines

TLB

Cache associativity

Loop tiling

Optimization strategies

Cache aware and cache oblivious programming

Case study: Matrix-vector product

Case study: Goto matrix-matrix product

Power consumption

Derivation of scaling properties

Multicore

Total computer power

Review questions

Parallel Computing

Introduction

Quantifying parallelism

Definitions

Asymptotics

Amdahl's law

Scalability

Simulation scaling

Parallel Computers Architectures

SIMD

MIMD / SPMD computers

The commoditization of supercomputers

Different types of memory access

Symmetric Multi-Processors: Uniform Memory Access

Non-Uniform Memory Access

Logically and physically distributed memory

Granularity of parallelism

Data parallelism

Instruction-level parallelism

Task-level parallelism

Conveniently parallel computing

Medium-grain data parallelism

Task granularity

Parallel programming

Thread parallelism

OpenMP

Distributed memory programming through message passing

Hybrid shared/distributed memory computing

Parallel languages

OS-based approaches

Active messages

Bulk synchronous parallelism

Program design for parallelism

Topologies

Some graph theory

Busses

Linear arrays and rings

2D and 3D arrays

Hypercubes

Switched networks

Cluster networks

Bandwidth and latency

Locality in parallel computing

Multi-threaded architectures

Co-processors

A little history

Bottlenecks

GPU computing

Intel Xeon Phi

Remaining topics

Load balancing

Distributed computing, grid computing, cloud computing

Usage scenarios

Characterization

Capability versus capacity computing

FPGA computing

MapReduce

The top500 list

The top500 list as a recent history of supercomputing

Heterogeneous computing

Computer Arithmetic

Integers

Real numbers

They're not really real numbers

Representation of real numbers

Limitations

Normalized and unnormalized numbers

Representation error

Machine precision

The IEEE 754 standard for floating point numbers

Round-off error analysis

Correct rounding

Addition

Multiplication

Subtraction

Examples

Roundoff error in parallel computations

Compilers and round-off

More about floating point arithmetic

Programming languages

Other computer arithmetic systems

Extended precision

Fixed-point arithmetic

Complex numbers

Conclusions

Numerical treatment of differential equations

Initial value problems

Error and stability

Finite difference approximation: Euler explicit and implicit methods

Boundary value problems

General PDE theory

The Poisson equation in one space dimension

The Poisson equation in two space dimensions

Difference stencils

Other discretization techniques

Initial boundary value problem

Discretization

Stability analysis

Numerical linear algebra

Elimination of unknowns

Linear algebra in computer arithmetic

Roundoff control during elimination

Influence of roundoff on eigenvalue computations

LU factorization

The algorithm

The Cholesky factorization

Uniqueness

Pivoting

Solving the system

Complexity

Block algorithms

Sparse matrices

Storage of sparse matrices

Sparse matrices and graph theory

LU factorizations of sparse matrices

Iterative methods

Abstract presentation

Convergence and error analysis

Computational form

Convergence of the method

Choice of K

Stopping tests

Theory of general iterative methods

Iterating by orthogonalization

Coupled recurrences form of iterative methods

The method of Conjugate Gradients

Derivation from minimization

GMRES

Complexity

Further Reading

High performance linear algebra

Collective operations

Broadcast

Reduction

Allreduce

Allgather

Reduce-scatter

The sparse matrix-vector product

Parallel dense matrix-vector product

Implementing the block-row case

Scalability of the dense matrix-vector product

LU factorization in parallel

Solving a triangular system

Factorization

Parallel sparse matrix-vector product

Parallel efficiency of the sparse matrix-vector product

Memory behaviour of the sparse matrix-vector product

The transpose product

Setup of the sparse matrix-vector product

Parallelism in solving linear systems from PDEs

Computational aspects of iterative methods

Vector operations

Finite element matrix construction

Parallel preconditioners

Jacobi preconditioning

The trouble with parallel ILU

Block Jacobi methods

Parallel ILU

Ordering strategies and parallelism

Nested dissection

Variable reordering and colouring: independent sets

Operator splitting

Parallelism and implicit operations

Wavefronts

Recursive doubling

Approximating implicit by explicit operations, series expansion

Grid updates

Analysis

Communication and work minimizing strategy

Block algorithms on multicore architectures

II Applications

Molecular dynamics

Force Computation

Force Fields

Computing Short-Range Nonbonded Forces

Computing Long-Range Forces

Parallel Decompositions

Atom Decompositions

Force Decompositions

Spatial Decompositions

Neutral Territory Methods

Parallel Fast Fourier Transform

Parallel 1-D FFT

Parallel 3-D FFT

Integration for Molecular Dynamics

Sorting

Brief introduction to sorting

Quicksort

Quicksort in shared memory

Quicksort on a hypercube

Quicksort on a general parallel processor

Bitonic sort

Graph analytics

Traditional graph algorithms

Shortest path algorithms

Parallelization

Floyd-Warshall all-pairs shortest path

Spanning trees

`Real world' graphs

Properties of random graphs

Concepts

Hypertext algorithms

HITS

PageRank

Large-scale computational graph theory

N-body problems

The Barnes-Hut algorithm

The Fast Multipole Method

Full computation

Implementation

Vectorization

Shared memory implementation

Distributed memory implementation

Monte Carlo Methods

Parallel Random Number Generation

Examples

Integration by statistics

Monte Carlo simulation of the Ising model

Computational biology

Dynamic programming approaches

Suffix tree

Big data

Recommender systems

Stochastic gradient descent

Alternating least squares

Other physics applications

Lattice Boltzmann methods

Hartree-Fock / Density Functional Theory

III Appendices

Linear algebra

Norms

Gram-Schmidt orthogonalization

The power method

Nonnegative matrices; Perron vectors

The Gershgorin theorem

Householder reflectors

Complexity

Partial Differential Equations

Partial derivatives

Poisson or Laplace Equation

Heat Equation

Steady state

Taylor series

Graph theory

Definitions

Common types of graphs

Graph colouring and independent sets

Graphs and matrices

Spectral graph theory

Fourier Transforms

Automata theory

Finite State Automatons (FSAs)

General discussion

Parallel Prefix

IV Tutorials

Unix intro

Files and such

Text searching and regular expressions

Command execution

Scripting

Expansion

Shell interaction

The system and other users

The sed and awk tools

Review questions

Compilers and libraries

An introduction to binary files

Simple compilation

Libraries

Managing projects with Make

A simple example

Makefile power tools

Miscellania

Shell scripting in a Makefile

A Makefile for LaTeX

Source code control

Workflow in source code control systems

Subversion or SVN

Mercurial or hg

Scientific Data Storage

Introduction to HDF5

Creating a file

Datasets

Writing the data

Reading

Scientific Libraries

The Portable Extendable Toolkit for Scientific Computing

Libraries for dense linear algebra: Lapack and Scalapack

Plotting with GNUplot

Usage modes

Plotting

Workflow

Good coding practices

Defensive programming

Guarding against memory errors

Testing

Debugging

Invoking gdb

Finding errors

Memory debugging with Valgrind

Stepping through a program

Inspecting values

Breakpoints

Further reading

Performance measurement

Timers

Accurate counters

Profiling tools

Tracing

C/Fortran interoperability

Linker conventions

Arrays

Strings

Subprogram arguments

Input/output

Fortran/C interoperability in Fortran2003

LaTeX for scientific documentation

The idea behind LaTeX, some history

A gentle introduction to LaTeX

A worked out example

Where to take it from here

Review questions

V Projects, codes, index

Class projects

Cache simulation and analysis

Evaluation of Bulk Synchronous Programming

Heat equation

The memory wall

Codes

Hardware event counting

Test setup

Cache size

Cachelines

Cache associativity

TLB

Unrepresentible numbers

Index and list of acronyms

The book hasn't received reviews yet.