CS4435b - CS9624b - High Performance Computing with a Focus on Hardware Acceleration Technologies

University of Western Ontario
Computer Science Department
Date: January 4, 2010

Current hardware improvements focus on increasing the number of computations that can be performed in parallel rather than on increasing clock speed alone. This change has brought multi-processor workstations to the desktop, expanding interest in parallel algorithms and software capable of exploiting these computing resources. At the same time, these new hardware acceleration technologies stress the need of a deeper understanding of performance issues in software design.

The aim of this course is to introduce you to the design and analysis of algorithms and software programs capable of taking advantage of these new computing resources. The following concepts will guide our quest for high performance: parallelism, scalability, granularity, locality, cache complexity, synchronization, scheduling and load balancing.

Out of the course, you are anticipated to have an in depth understanding of the following subjects:

• Multi-threaded parallelism (theoretical model such as work and span, the cilk/cilk++ concurrency platform and its development tools, scheduling by work stealing)
• Cache complexity (memory hierarchy, cache complexity, cache-oblivious algorithms)
• Code optimization for parallelism and locality (including performance evaluation by tools like Cilkscreen and VTune).

A quarter part of the course will give an overview of other hot topics in high performance computing, including the following ones:

• hardware acceleration technologies (GPGPU, FPGA)
• auto-tuning techniques (as in the FFTW or SPIRAL)
• other concurrency platforms (TBB, OpenMP, MPI)

Prerequisites for undergraduate students

CS 210, 211, 305. A good familiarity with linear algebra and complexity analysis of algorithms is recommended.

Outline

This presents the contents of the course, its assignments, quizzes and projects. outline.html

Schedule of Lectures

Week Jan. 4-10	Introduction to software performance
Week Jan. 11-17	Introduction to multicore programming
Week Jan. 18-24	Multithreading parallelism and performance
Week Jan. 25-31	Analysis of multithreaded algorithms
Week Feb. 1-7	Practical issues in parallelism
	Case Study
Week Feb. 8-14	Synchronizing without locks
Week Feb. 22-28	Cache memories
Week Mar. 1-7	Practical issues with locality
Week Mar. 8-14	Cache complexity
Week Mar. 15-21	Bit Hacks
Week Mar. 22-28	Space-time tradeoffs
Week Mar. 29-4	Experiences with coding high-performance numerical libraries
Week Apr. 19-26	Project presentations

Student evaluation

The course is very oriented toward quizzes, assignments and projects. For CS 4435, assignments and projects constitute 40% and 40% of the course mark, respectively. There is no midterm examination and no final examination. However, there will be at least four quizzes. Quizzes constitute 20% of the course mark. For CS 9624, quizzes and projects constitute 20% and 80% of the course mark, respectively.

Some keywords (to be completed)

These are links to the Wikipedia pages of some keywords for this course.

• High-performance computing
• Parallel computing
• Stream processing
• Single Instruction, Multiple Data (SIMD or vector instructions)
• Instruction level parallelism
• Distributed computing
• Multi-core
• Multi-threading
• Hyper-threading
• Cycles per instruction
• CPU Cache
• Cache coherency
• Cache-oblivious algorithm
• Instruction pipeline
• Speculative execution
• GPU
• GP-GPU
• FPGA
• Silicon Valley

Some other courses on HPC and parallelism

These are links to courses on HPC and Parallelism, which have inspired this CS4435b - CS9624b. In particular, I am grateful to Saman P. Amarasinghe (MIT), Matteo Frigo (Intel), Charles E. Leiserson (MIT) Markus Pueschel (CMU) for sharing with me the sources of their course notes and other documents.

• MIT OpenCourseWare
• MIT 6.895 Fall 2003 by Charles E. Leiserson
• MIT 6.172 Fall 2009 by Saman P. Amarasinghe and Charles E. Leiserson
• MIT 18.337 Applied Parallel Computing Spring 2009 by Alan Edelman
• MIT 6.852 Distributed Algorithms by Nancy A Lynch
• CMU 18-645 How to Write Fast Code (Spring 2008) by Markus Pueschel
• Drexel University CS 540 High Performance Computing by Jeremy Johnson
• Stony Brook University CSE 690 - General Purpose Computing on Graphics Hardware by Klaus Mueller
• U.C. Berkeley CS267/EngC233 Home Page by James Demmel
• CS 402/CS 535: Parallel and Distributed Computing at UWO
• U. Illinois ECE 498 Programming Massively Parallel Processors by Wen-Mei Hwu.
• Parallel Algorithms (WISM 459, 2005/2006)by Rob Bisseling
• Topics in Parallel Computing (CS 838, Univ. of Wisconsin-Madison, Spring 1999)by Pavel Tvrdik
• Parallel Algorithms (CS 662, San Diego Univ., Spring 1996)by Roger Whitney
• Computer Systems: A Programmer's Perspective (CS:APP) by Randal E. Bryant and David R. O'Hallaron

Concurrency platforms

These are links to programming languages for multi-threaded parallelism.

• The Cilk Project at MIT
• The Multicore Programming Blog
• Cilk Arts
• The Wikipedia page of Cilk
• The Intel Cilk++ Software Development Kit
• Download Intel Cilk++ SDK
• Kernel for Adaptative, Asynchronous Parallel and Interactive programming (KAAPI)
• The Open MP Web site
• Open MP Tutorial
• Pthreads page from Wikipedia
• PThread Tutorial
• MPICH-A Portable Implementation of MPI
• Development Tools for MPICH

Some HPC libraries in scientific computing

These are links to some HPC libraries in scientific computing.
These software makes use of auto-tuning techniques.

• ATLAS
• FFTW
• SPIRAL

Performance analyzers and debuggers

These are links to some HPC libraries in scientific computing.
These software makes use of auto-tuning techniques.

• GDB tutorial
• Another GDB tutorial
• And another GDB tutorial
• Intel Cilkscreen Race Detector for Cilk++ programs
• Visualizing Parallel Speedup with Cilkview
• PIN: a tool for the dynamic instrumentation of programs
• Performance Application Programming Interface (PAPI)
• The Performance Counter Library: PCL
• Intel VTune Performance Analyze

Some links to hardware architecture pages

These are links to hardware architecture pages related to this course.

• History of computing hardware
• Electronic Numerical Integrator And Computer (ENIAC)
• Harvard Mark I
• Multi-core processor watch at U.C. Berkeley
• Intel Streaming SIMD Extensions 2 (SSE 2)0
• gpgpu.org
• NVIDIA GeForce 200 Series
• Intel Larrabee

Some conferences on HPC and parallelism

• 39th International Conference on Parallelism Processing (ICPP 2010)
• 38th International Conference on Parallelism Processing (ICPP 2009)
• 37th International Conference on Parallelism Processing (ICPP 2008)
• 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010)
• 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009)
• 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2008)
• Super Computing (SC 2010)
• IEEE International Parallel & Distributed Processing Symposium (IPDPS 2010)
• Parallel and Distributed Computing, Applications and Technologies (PDCAT 2010)
• SIAM Conference on Parallel Processing and Scientific Computing (PP10)
• High Performance Computing Symposium (HPCS 2009)
• High Performance Computing Symposium (HPCS 2010)
• ACM Workshop on Parallel Symbolic Computation (PASCO 2010)
• ACM Workshop on Parallel Symbolic Computation (PASCO 2007)
• Some Theoretical Computer Science Conferences