next up previous index
Next: What this Course is Up: Introduction Previous: Introduction

   
The Syllabus

Computer Science graduates have one more reason to attend the course, that is a preparation for the Qualifying Exam . To this extent I will attempt to cover most of the syllabus listed below within this course, i.e., P573, and within the following course, Advanced Scientific Computing, B673, to be given in the Spring semester of 1999.

B673  will cover parallel programming, parallel libraries, libraries for Automatic Mesh Refinement codes, libraries for Finite Elements, and so on.

Now, to the syllabus: 

1.
Basic computer concepts and tools
(a)
  Measuring time on computers  (cf. Chapter 3)
i.
wall clock, user, system times
ii.
clock resolution and overhead of timing
iii.
other basic performance data: page faults, block I/O operations, memory/space integrals
(b)
  Data sets and characteristics: ASCII, binary, sequential, random access, record addressability  (cf. Section 2.3)
(c)
floating point data: IEEE standard, range and precision, infinity, +0 and -0, denormalised numbers, NaN  (cf. Section 2.6)
2.
High performance computer architecture   
(a)
Organisation of computer memory hierarchy
i.
Memory banks and interleaving
ii.
Caches and registers
a.
Direct mapped, set associative
b.
Cache lines
c.
Replacement policies
d.
Write-through and write-back
e.
Snooping
iii.
Enhancing data locality in codes
iv.
I/O architectures
(b)
Microprocessors 
i.
CISC versus RISC versus EPISC (Merced)
ii.
Pipelining of data and instructions
iii.
Superscalar organisation
iv.
Address computations and pointers
(c)
Supercomputer organisation 
i.
Vectorisation  (cf. Section 2.2.1)
ii.
Shared memory, distributed memory
iii.
Task versus data parallelism: SIMD versus MIMD
iv.
Topologies: mesh, hypercube, tree
v.
Synchronisation and communication: MPI, PVM, blocking communication, broadcasting
vi.
Examples: CM2, CM5, SGI PC, Sun E10000, SP2, Cray T3E, SGI O2000, HP Exemplar, Fujitsu VPP300, NEC SV6
3.
  Numerical methods  overview (here the emphasis is on implications for data structures and mapping of computations to machine architectures and less on the mathematical analysis of the methods)
(a)
Common models, prototypes and implications for computer codes: for each of these be able to discuss implementation issues, choice of data structures, performance prediction, impact on structure of computational kernels (cf. Chapter 3)
i.
heat equation: parabolic PDEs 
ii.
wave equation: hyperbolic PDEs 
iii.
laplace equation: elliptic PDEs 
iv.
planetary motion: systems of ODEs 
v.
double pendulum: chaotic ODEs
vi.
N-body systems: particle methods, reduced order methods (e.g., Barnes-Hut, multipole) 
vii.
signal processing: Fourier analysis (FFT, butterfly pattern) 
(b)
Discretisations  (cf. Chapter 3)
i.
time discretisation: explicit versus implicit methods
ii.
spatial discretisation: finite differences, finite elements, finite volumes, spectral elements
iii.
uniform and quasi-uniform meshes
iv.
irregular and adaptive meshing
v.
integral equation methods
(c)
Sparse matrix data structures and their manipulation  (cf. Chapter 3)
i.
operations needed on sparse matrices: matrix-vector products, Gaussian elimination, triangular solvers
ii.
coordinatewise, compressed sparse row, modified sparse row, jagged diagonals
iii.
load/store analysis and pipelining for sparse matrix data structures
4.
Performance analysis and improvement  (cf. Chapter 3)
(a)
Profiling (cf. Chapter 3)
i.
instrumentation and sampling-based tools: gprof, tprof, pixie, CASE tools
ii.
interpreting profiling information
(b)
Benchmarking, MFLOPS, MIPS, theoretical peak performance
(c)
Analysing and improving performance
i.
using compiler optimisations
ii.
typical techniques: common sense, loop interchange, unrolling, splitting, blocking, jamming
iii.
validation of results
5.
Programming language and systems issues in scientific computing  (cf. Chapter 2)
(a)
 Fortran 90 concepts: vector and array operators, modules and interfaces, operators and when and how to use them  (cf. Section 2.2.1)
(b)
  data parallelism in High Performance Fortran
(c)
  languages for interactive scientific experiments: Matlab, Mathematica, Maple (cf. Section 2.6)
(d)
object oriented scientific programming techniques
(e)
  understanding libraries: templates, macros, BLAS, LAPACK, and related resources (cf. Section 2.3, Chapter 3)
(f)
the role of the programmer in understanding the compiler, preprocessors and optimisers
(g)
  programming support for large scientific data bases (cf. Section 2.3)
(h)
software support for parallel programs  (cf. Section 2.2.1)
i.
parallelising compiler techniques: synchronisation methods, types of data dependencies, compiler directives
ii.
communicating processes: PVM, MPI
iii.
POSIX threads (Pthreads)
6.
Parallelism in scientific algorithms
(a)
Modeling of parallelism in theory and practice
i.
speed-up
ii.
parallel efficiency
iii.
Amdahl's law
iv.
computation/communication ratio
(b)
Parallel algorithmic techniques
i.
speed-up
ii.
recursive doubling, parallel prefix
iii.
divide-and-conquer
iv.
domain decomposition
v.
data distribution (cf. Section 2.2.1, Chapter 3)
(c)
parallel algorithms
i.
parallel sorting
ii.
basic linear algebra operations (cf. Chapter 3)
iii.
fast Fourier transforms (cf. Chapter 3)
iv.
particle methods (cf. Chapter 3)

The listing above is enough to make anyone sigh ``Oh me gawd''. But fear not! Most of the stuff in the syllabus can be discussed and illustrated while working on various projects, and this is exactly what we are going to do. Our preference will be to learn, discover, and comment on various points of the syllabus, while working on a number of simple scientific applications that will take us on a leisurely tour through cosmology, electrodynamics, optics, and image processing. Whatever science and mathematics will be required in these projects will be explained in sufficient (though not overwhelming) detail.


next up previous index
Next: What this Course is Up: Introduction Previous: Introduction
Zdzislaw Meglicki
2001-02-26