High Performance Computing
(cod. 90535, 9 CFU, autumn semester)

Goals

The traditional sequential computer model is now confined to application environments where low information processing capabilities (industrial equipment, mobile phones, netbooks) are sufficient. In all other cases, computing platforms make use of multiple computing units simultaneously. These parallel computers require specific programming techniques, in order to obtain more processing power through the (explicit or implicit) control of cooperation between the various computing units.

For a computer scientist it is therefore important to know the various types of parallel architectures available today and to be able to program parallel computers, and generally have some knowledge of the high performance computing sector, considering also today's emphasis of large-size and high-dimensional datasets.

The aim of this course is to provide basic knowledge on the architecture of parallel processing systems, along with a minimum of programming skills essential to using such systems. As far as the programming part is concerned, the emphasis is on parallel message-passing programming using MPI, but the OpenMP shared memory paradigm is also practiced. GPU architecture is also presented, and GPU programming with OpenCL is practiced too. Lastly, the problem of parallel I/O is dealt with in an introductory way.

Topics

Some of the topics below might not have been considered during this years' edition of the course. Please refer to the syllabus for the actual list valid for the current year.

  1. Performance of a computer:
    Direct and inverse, absolute and relative performance indices. Benchmarks.
  2. Pipeline processor architecture:
    Performance of a pipeline system and its analytical evaluation. Overall structure of a pipeline processor. Pipeline hazards (structural, data, control) and their impact on performance. Reducing hazards and/or their impact: hardware techniques. Instruction-level parallelism in sequential programs. How to make better use of instruction-level parallelism when using pipeline processors: loop unrolling, instruction reordering.
  3. Advanced pipeline processors:
    Dynamic Instruction Scheduling with Tomasulo Architecture.
    Branch Prediction.
    Speculative execution of instructions.
  4. Superscalar processors:
    Multiple-issue processors. Scheduling instructions on multiple-issue processors. VLIW processors.
  5. Cache Memory and Computer Performance:
    Hardware techniques to reduce cache miss penalties. Hardware and software techniques to reduce cache miss frequency. Hardware techniques to hide cache miss overheads. Practicals with matrix multiplication.
  6. Multiprocessor computers:
    The purpose of a parallel computer. Limits of parallel computers: Amdahl's law, communication delays. MIMD computers: shared memory, distributed memory with shared address space, distributed memory with message-passing.
  7. MIMD shared-memory computers:
    Overall organization. Reducing memory access contention. Cache coherency: snooping-based protocols.
  8. MIMD computers with distributed memory and shared address space:
    Overall organization. Directory-based cache coherence protocols.
  9. Cooperation among processes on shared address space:
    Communication and synchronization. Synchronization algorithms: lock/unlock and barrier synchronization on shared address space and their performance.
  10. Consistency in main memory. Weak consistency models and their performance benefits.
  11. High-level parallel programming on shared address space: the OpenMP directives. Practicals with OpenMP.
  12. Message-passing MIMD computers:
    Overall organization. Cooperation among processes: message-passing communication and synchronization. Blocking vs. non-blocking, point-to-point vs. collectives, implementation aspects. Non-blocking communication and instruction reordering.
  13. High-level parallel programming with message-passing:
    the SPMD paradigm, the Message Passing Interface (MPI) standard. Practicals with MPI.
  14. The concept of load balancing and its impact on performance.
    Dynamic load balancing: the "farm" parallel structure and its performance analysis.
  15. SIMD parallel computers: vector processors. Modern descendants of SIMD computers: vector extensions, GPUs.
    GPU programming with OpenCL. Practicals with OpenCL on a GPU.
  16. Parallel I/O and MPI-I/O.

Exam

The exam consists of an oral discussion on the topics of the course. The evaluation takes into account the work done during the practicals. Those who do not participate in the practicals shall take an additional practical exam on parallel programming, or shall take additional assignments on parallel programming to be accomplished before the oral exam.

Textbooks

John Hennessy, David Patterson: Computer architecture: a quantitative approach (fifth edition), Morgan Kaufmann.
Order online the book at a modest price (less than 30 euros) from India.
The website of the book contains the appendices (not present in the paper book) along with additional material.

Ian Foster: Designing and Building Parallel Programs, Addison Wesley. Online here.

Slides, tutorials, and code samples, that can be found on Aulaweb, integrate but do not replace the textbooks.

Prerequisites

Basic knowledge of computer architecture, fair programming skills.
Last update: June 2017