Syllabus for Ph. D. Preliminary Examination
in High Performance Computing
within Computational Science Cluster
of Mathematical Computer Science

1. MCS 571 Numerical Methods for Partial Differential Equations
2. MCS 572 Introduction to Supercomputing
3. MCS 575 Computer Performance Evaluation

Students are required to answer 5 questions.
Your five best answers determine your score.
A nearly complete answer carries more weight than several partial answers adding to the same numerical score.
Syllabi for each of the areas:
1. Numerical Methods for PDEs and Related Numerical Analysis
   • Normal Preparation: MCS 571 Numerical Methods for Partial Differential Equations.
   • Other Background: MCS 471 Numerical Analysis, MCS 472 Advanced Numerical Analysis.
   • Topics:
     1. Floating point arithmetic, chopping, rounding, error propagation, operation counts.
     2. Matrix Iteration Methods. Methods of Jacobi, Gauss-Siedel.
     3. Numerical solution of Parabolic PDE. Finite Differences, Finite Element Methods, Explicit Methods, Convergence, Stability, Fourier Stability, Crank-Nicolson Implicit, Alternating Directions Implicit, Successive-Over-Relaxation, Eigenvalue Decompositions, Higher Level Schemes, Artificial Boundaries, Irregular Regions.
     4. Numerical solution of Elliptic PDE. Finite Differences, Explicit Methods, Iterative Methods (Jacobi, Gauss-Seidel), Conjugate Gradient Method, Multigrid Method, Finite Element (Galerkin) Method, Stability.
     5. Numerical solution of Hyperbolic PDE. Finite Differences, D'Alembert's exact Solution, Method of Characteristics, Courant-Friedrichs-Lewy Condition, Lax-Wendroff Method, Characteristic Meshes, Nonlinear Problems, Artificial Viscosity, Stability.
     6. Numerical Solution of Nonlinear PDE. Quasi-Linearization, Predictor- Corrector.
     7. Computer Implementation.
   • References:
     1. G. D. Smith, Numerical Solution of Partial Differential Equations, Oxford, 1985
     2. A. R. Mitchell and D. F. Griffiths, The Finite Difference Method in Partial Differential Equations, Wiley, 1980.
     3. C. F. Gerald and P. O. Wheatley, Applied Numerical Analysis, Addison-Wesley, 1994.
     4. W. L. Briggs, A Multigrid Tutorial, SIAM, 1987.
     5. G. Strang and G. Fix, An Analysis of the Finite Element Method, Prentice-Hall, 1973.
2. Parallel Processing and Supercomputing.
   • Normal preparation: MCS 572 Introduction to Supercomputing.
   • Topics:
     1. Supercomputer Architecture. Vector Machines. Parallel Processors. Data Parallel Processors. Single-Instruction-Multiple-Data. Multiple-Instruction-Multiple-Data. Pipelining. Vectorization. Parallelization.
     2. Comparison of Serial, Parallel and Vector Architectures.
     3. Performance Measures and Models. Speed-up limitations. Theoretical Timings. Efficiencies. Amdahl's Law and Extensions. Scaled Speed-up. Pipeline Speed-up.
     4. Data Dependency Reduction. Data flow. Loop reordering.
     5. Parallelization of Algorithms. Parallel linear algebra routines. Loop optimizations. Implementation. Principal of Locality. Caches and Buffers.
     6. Massively Data Parallel Algorithms. Array notation. Fortran90 and HPC Fortran, Parallel and Vector C Code, Layout, Align, Replicate, Masking, Shifting, Spreading, Broadcasting, Forall Loops.
     7. Purely Parallel Algorithms.
     8. Block Decomposition Methods.
     9. Parallel Programming Packages.
   • References:
     1. J. J. Dongarra, I. B. Duff, D. C. Sorensen and H. A. van der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, SIAM, 1991.
     2. K. Hwang, Advanced Computer Architecture: Parallelism, Scalability, Programmability, McGraw-Hill, 1993.
     3. D. A. Patterson and J. L. Hennessy, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publ., 1990.
     4. D. Kuck, The Structure of Computers and Computations, Wiley, 1978.
     5. Levesque and Williamson, A Guidebook to FORTRAN on Supercomputers, Academic Press, 1988.
     6. Metcalf, FORTRAN Optimization, Academic Press, 1985.
     7. J. M. Ortega, Introduction to Parallel and Vector Solution of Linear Systems, Plenum, 1988.
     8. Quinn, Designing Efficient Algorithms for Parallel Computers, McGraw-Hill, 1987.
     9. P. J. Hatcher and M. J. Quinn, Data-Parallel Programming on MIMD Computers, MIT Press, 1991.
     10. Dongarra et al, Implementing linear algebra algorithms for dense matrices on a vector pipeline machine, SIAM Review 26(1984) 91-112.
3. Queueing Theory and Computer Performance Evaluation.
   • Normal Preparation: MCS 575 Computer Performance Evaluation.
   • Other Background: working knowledge of probability and statistics is required (e.g., Stat 401 Introduction to Probability ) along with an introduction to stochastic processes (Stat 461-462 Applied Probability Models I-II). This should include Markov processes and birth-death processes.
   • Topics:
     1. Operational Analysis - Little's Theorem, Utilization Law, forced flow law. Application of these results to computer systems (bottleneck analysis, etc.)
     2. Basic Queueing Theory - state variables - number in system and unfinished work (virtual waiting time), stationary solutions.
        1. simple queues - M/M/1, M/M/s, finite-source M/M/s, finite-capacity M/M/s, and feedback mechanisms.
        2. queueing disciplines - FCFS, LCFS, SRTF, RR, PS, BATCH, and priority queues.
        3. cyclic queues - models of a multiprogramming environment and models of interactive systems.
     3. Queueing Networks - Markovian networks, Jackson's Theorems, detailed balance, time reversability, and product form solutions.
        1. analysis of complex computer system - applications
        2. normalizing constant technique and mean value analysis.
     4. M/G/1 Queues - supplementary variable technique, embedded chain, Pollaczeh-Khinchin formula, busy period analysis, Erlang distributions, hyperexponential distributions, method of stages, Takacs equation for waiting times, and loss systems.
     5. Simulation Techniques - event driven, random number generators, GPSS.
   • References:
     1. S.M. Ross, Introduction to Probability Models.
     2. K. Chandy and C. Sauer, Computer Systems Performance Modeling, Prentice-Hall, 1981.
     3. L. Kleinrock, Queueing Systems, Vols. I and II, Wiley, 1987.
     4. E. Coffman and P. Denning, Operating Systems Theory, Prentice Hall, 1973.

Web Source: http://www.math.uic.edu/~hanson/prelhpcsyl.html

Email Comments or Questions to Professor Hanson