Programming for Performance

CS 610, Semester 2023-24-I, IIT Kanpur

Class hours: WedFri 10:30-12:00 PM in KD 102

Instructor Information

Name	Swarnendu Biswas
Email	swarnendu AT cse.iitk.ac.in

TA Information

Name	Email (AT cse.iitk.ac.in)
Vipin Patel	vipinpat
Nibir Baruah	nibir

Course Description

To obtain good performance, one needs to write correct but scalable parallel programs using programming language abstractions like threads. In addition, the developer needs to be aware of and utilize many architecture-specific features like vectorization to extract the full performance potential. This course will discuss programming language abstractions with architecture-aware development to learn to write scalable parallel programs. This is not a “programming tips and tricks” course.

We will have five or more assignments to use the concepts learned in class and appreciate the challenges in extracting performance.

Prerequisites

Exposure to the following courses (or equivalent) is desirable: CS220 (Computer Organization), and CS330 (Operating Systems).
Programming maturity with popular programming languages like C, C++, and Java.

Course Syllabus and Policies | Academic Integrity | Evaluation Scheme | Resources | References

Course Syllabus and Policies

Syllabus

The course will primarily focus on the following topics.

Introduction: Challenges in parallel programming, correctness and performance errors, understanding performance, performance models
Exploiting spatial and temporal locality with caches, analytical cache miss analysis
Compiler transformations: Dependence analysis, Loop Transformations
Compiler vectorization: vector ISA, auto-vectorizing compiler, vector intrinsics, assembly
Shared-memory programming and Pthreads
OpenMP: Core OpenMP, Advanced OpenMP, Heterogeneous programming with OpenMP
Parallel Programming Models and Patterns: Intel Threading Building Blocks
GPU programming: GPU architecture and CUDA Programming
Performance bottleneck analysis: PAPI counters, performance analysis tools

We may add new, drop existing, or reorder topics depending on progress and class feedback. The course may also involve reading and critiquing related research papers.

Policies

Please be on time for class.
Please try to avoid using laptops and/or mobile devices in class, they are distracting for both the instructor and other students who want to concentrate.
You are allowed up to two late days to submit your assignment, with a 25% penalty for each day.

Feedback

I am open to constructive feedback about the course content and presentation. Feel free to provide suggestions for improvements.

Academic Integrity

You may discuss concepts with classmates, but all submissions must be your own or your team's work when teamwork is permitted.
You should not search online for existing solutions related to the assignments, even as a reference.
Students caught cheating or plagiarizing will receive penalties, automatically fail the course, and will be reported to the institute.

Evaluation Scheme

Class participation/quizzes	5%
Assignments	40%
Midsem	25%
Endsem	30%

Resources

NOTE: Our first class is on Wednesday, Aug 2, at KD 102 from 10:30 AM. I will be traveling from Aug 2-9. We will conduct the second class on Aug 4 online because it falls within the add/drop period. There will be no class on Aug 9. The third and fourth classes will be on Aug 11 (regular schedule) and 12 (extra class, 10:30-12 PM in KD 102, Saturday).

Date	Topic	Resources	Recommended Reading
		First Course Handout
02/08	Compiler Challenges for Parallel Architectures	Slides	AK Chap 1
04/08 (online), 11/08	Write Cache-Friendly Code	Slides	CSAPP Chap 6 HP APP B DRAG 11.1, 11.2
12/08 (extra), 16/08	Dependence Testing	Slides	DRAG 11.3, 11.4, 11.6 AK Chap 2
	POSIX Threads	Slides	PP Chapter 4 (IITK has subscribed to the ebook) OSTEP Thread API, Condition Variables LLNL Pthreads Tutorial
18/08, 23/08, 25/08	Loop Transformations	Slides	AK 5.2-5.4, 5.7.2, 5.9, 6.2.1, 6.2.2, 6.2.5, 6.3.1-6.3.4 AP 4.1, 4.2, 4.5, 5.1-5.6 HP 4.5 Compiler Transformations for High-Performance Computing
25/08, 30/08, 01/09	Vectorization	Slides	HP 4.3 Intel oneAPI DPC++/C++ Compiler Developer Guide and Reference Intel C++ Compiler Classic Developer Guide and Reference Guide for Intel Compilers
06/09, 08/09, 13/09, 15/09	OpenMP	Slides	OpenMP Application Programming Interface v5.2 OpenMP Application Programming Interface Examples v5.2.1 PP Chapter 5 (IITK has subscribed to the ebook) LLNL OpenMP Tutorial
27/09, 29/09, 04/10, 06/10, 11/10, 13/10	GPU Programming with CUDA	Slides	NVIDIA CUDA C Programming Guide NVIDIA CUDA C Best Practices Guide KH Chapters 1-5 (IITK has subscribed to the ebook) HP 4.3
18/10, 01/11, 03/11	Cache Coherence and False Sharing	Slides	MCM Chapters 2, 6, 8 (IITK has subscribed to the ebook)
03/11, 04/11, 08/11, 10/11, 11/11	Concurrent Data Structures	Slides	MP Chapters 9, 10, 13 (IITK has subscribed to the ebook)

References

I have listed (NOT in any particular order) a few popular references.

[CSAPP] Computer Systems: A Programmer's Perspective, 3rd edition - R. Bryant and D. O'Hallaron
[DRAG] Compilers: Principles, Techniques, and Tools - A. Aho, M. Lam, R. Sethi, and J. Ullman
[HP] Computer Architecture: A Quantitative Approach, 6th edition - J. Hennessy and D. Patterson
[AK] Optimizing Compilers for Modern Architectures - R. Allen and K. Kennedy
[AP] Automatic Parallelization: An Overview of Fundamental Compiler Techniques - Samuel P. Midkiff
[PP] An Introduction to Parallel Programming - Peter S. Pacheco
[KH] Programming Massively Parallel Processors: A Hands-on Approach, 3rd edition - David B. Kirk and Wen-mei W. Hwu
[MCM] A Primer on Memory Consistency and Cache Coherence, 2nd edition - Vijay Nagarajan, Daniel J. Sorin, Mark D. Hill and David A. Wood
[MP] The Art of Multiprocessor Programming, 1st edition - Maurice Herlihy and Nir Shavit

We may read and discuss related materials and research papers which we will announce in class.