This course will be of interest to students who want to explore the fundamental aspects of programming for parallel architectures. Almost all modern computers contain multiple processing units, since individual processors have effectively reached peak performance.

Prerequisites:  COMP 2001 and  COMP 2004

Availability: This course is usually offered once per year, in Fall or Winter.

Course Objectives

This course will focus on the considerations and challenges of writing parallel programs, particularly for multicore processors and graphics processing units.

Representative Workload

• Assignments (4) 50%
• Midterm examination 20%
• Final examination 30%

Representative Course Outline

• Introduction (1 hour)
• Types of parallelism (1 hour)
  • task, data, instruction and thread-level parallelism, Flynn’s taxonomy
• Shared-memory programming (2 hours)
  • Threaded programming, explicit and implicit thread control, trivially parallel
    algorithms
• Explicit threading (4 hours)
• Synchronization (2 hours)
  • race conditions, mutual exclusion, deadlocks, livelocks, starvation,
    atomicity
• Synchronization design patterns (3 hours)
  • divide and conquer, locks, critical sections, semaphores
• Work sharing and load balancing (3 hours)
  • data distribution, interleaving, task distribution, task time estimation
• Performance and scaling (2 hours)
  • efficiency, speedup, Amdahl’s Law, weak scaling, strong scaling, compute vs memory bound computation
• Implicit threading (4 hours)
  • OpenMP
• Memory hierarchy (2 hours)
  • cache coherency, memory optimization, multi-core processors, hyper-
    threading
• Vectorization (3 hours)
  • single instruction, multiple data, AVX instruction set
• Graphics processing units (2 hours)
  • GPU architecture, memory hierarchy
• CUDA (4 hours)
  • data transfer, threads, blocks, single instruction multiple thread

Notes

• Credit cannot be obtained for both Computer Science 3730 and Electrical and Computer Engineering 7400.