Department of Computer Science & Engineering

Description:At the end of the course, students would learn techniques to analyze parallel programs written in languages like Java/ OpenMP/ X10.

CourseContent:

I. Parallel programming constructs basics (2 weeks) Introduction to concurrent programming, processes, threads, tasks, mutual-exclusion, synchronization, shared-memory communication, distributed memory communication
II. Program analysis basics (3 weeks) Abstract Interpretation, forward analysis (example, reaching definition analysis), backward analysis (example, liveness analysis), dimensions of different analysis (context sensitivity, flow sensitivity points-to analysis, dependence analysis, call graph construction.
III. Parallel program representation (1 week). Introduction to traditional intermediate representation (IR). Representation of parallel programs – program structure trees/graphs, parallel program graphs,
IV. MHP analysis and its impact on traditional analysis (4 weeks) May Happen in Parallel (MHP) analysis. Intra-procedural, inter-procedural analysis, whole-program analysis and incremental analysis, impact of MHP analysis on points-to analysis, alias analysis, call-graph construction, and dependence analysis.
V. Parallel-Program Specific analysis (2 weeks) Data-race detection – static and dynamic, Deadlock detection.
VI.Advanced Topics: (2 weeks) Performance Analysis: Amdahl’s law, memory consistency models, impact of memory consistency on program optimizations, reducing communication overheads, analyzing irregular programs. Verification: Owicki-Gries Method, Rely-guarantee.

TextBooks:None.
ReferenceBooks:

1) Advanced Compiler Design and Implementation, Muchnick, Morgan Kaufmann 1997.
2) Principles of Program Analysis: Nielson, Nielson, Hankin, Springer 2004.
3) The Art of Multiprocessor Programming, by Maurice Herlihy and Nir Shavit, Morgan Kaufmman Publishers, 1st Edition, Indian Reprint 2012.
4) Java Concurrency in Practice by Brian Goetz, Tim Peierls, Joshua Block, Joseph Bowbeer, David Holmes and Doug Lea, Addison Wesley, 1st Edition, 2006
5) OpenMP 5.0 Spec: https://www.openmp.org/wp-content/uploads/OpenMP-API-Specification-5.0.pdf
6) Research papers.