58437 - Parallel Calculus

Learning outcomes

At the end of the course, students know the main high performance computing architectures; can design and analyze parallel algorithms for different models of parallel computation; can implement parallel algorithms on shared and distributed memory architectures using the most suitable languages, tools and technologies

Course contents

Syllabus

• Parallel algorithms and parallel models of computation.
  
• Introduction to HPC architectures: Flynn taxonomy, shared memory and distributed memory architectures; GPGPU.
• Parallel programming patterns (embarassingly parallel; stencil; work farm; scan; reduce).
• Programming shared-memory architectures with C/OpenMP.
• Programming distributed-memory architectures with C/MPI
• GPGPU programming.
• Brief introduction to SIMD programming using compiler intrinsics or auto-vectorization (GCC compiler).
• Performance evaluation of parallel programs.

Prerequisites

This course assumes the following prerequisites:

• Programming in C.
• Unix/Linux environment (how to use the shell, how to write a basic Makefile, etc.).
• Computer architectures.
• Concurrent programming (deadlock, mutual exclusion, data race, etc.).
• Algorithms and data structures (asymptotic notation, basic data structures, sorting algorithms, analysis of iterative and recursive algorithms, Master Theorem).
• Basic knowledge of calculus (limits and series).

Readings/Bibliography

Selected topics from the following textbooks:

• Peter Pacheco and Matthew Malensek, An Introduction to Parallel Programming, Morgan Kauìffman, 2nd edition, 2021, ISBN 9780128046050; the first edition is fine, too: Peter Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann, 2011, ISBN 978-0123742605
• CUDA C++ programming guide (freely available on NVidia web site).
• Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, Introduction to Parallel Computing, 2nd Edition, Addison-Wesley, 2003, ISBN 978-0201648652.
• Joseph Jaja, An Introduction to Parallel Algorithms, ‎Addison-Wesley, 1st edition, 1992, ISBN 978-0201548563.
• Georg Hager, Gerhard Wellein, Introduction to High Performance Computing for Scientists and Engineers, CRC Press; 1 edition (July 2, 2010), ISBN 978-1439811924

Additional teaching material (including lecture slides and programming exercises) will be made available on the course web site and on the "Virtuale" E-Learning platform.

Teaching methods

The lectures introduce the foundations of parallel programming and several parallel programming costructs. Then, the same concepts are applied during practice sessions (BYOD-Bring Your Own Device) through a set of small programming assignments under the supervision of the instructor. Solutions are provided after the lab sessions, order to support self-study.

Due to the the type of activity and teaching methods adopted, participation to this course requires that students attend the training modules 1 and 2 on safety in the study places, through the e-learning platform https://elearning-sicurezza.unibo.it/ .

Assessment methods

Written exam and programming project. The two parts are independent and can be given in any order.

Written Exam

Structure: The written exam consists of quizzes and/or open questions. Open questions may address both methodological/theoretical aspects of the topics covered in the classes, or require the design of short parallel codes, or simple calculations (the use of a calculator is not required).

Exam Procedure: The written exam lasts 90 minutes. To take the exam, students must bring an identification document (e.g., university ID) and a pen. The exam is closed-book: students are not allowed to consult books, notes, or other materials. The use of electronic devices of any kind, including computers, tablets, cell phones, smartwatches, smartglasses, or similar devices, is forbidden. Violation of these requirements will result in immediate exclusion from the exam and a "FAILED" grade. Exclusion may occur even after the exam has been completed, if evidence of improper behavior is discovered.

Grading: The written exam is graded out of 30; the maximum score assigned for each correct answer is indicated in the exam text. Attendance of a written exam implies refusal of any previous valid grade in the written exam (the project grade, however, remains valid); this applies even if a student withdraws from the new written exam or obtains a lower grade than the previous one.

Programming Project

Structure: The programming project requires the development of a parallel application based on specifications provided by the instructor at the end of the course, using the tools discussed in class and the lab. The source code and compilation instructions must be provided. The application must be accompanied by a written report that describes and motivates the design choices and analyzes the performance of the programs using the appropriate metrics from those discussed in class.

Project Procedure: The project must be completed individually and can be submitted at any time up to the deadline indicated in the specifications (typically, the last day of the last exam session before the start of the new course edition).

Grading: The project is graded out of 30. The evaluation will take into account the correctness of the implementation, the clarity and efficiency of the code, and the quality of the presentation. If the grade is refused, a new project will be assigned based on new specifications.

Overall Grade

The exam is passed if the student receives a grade greater than or equal to 18/30 on each of the two tests. The final grade is the weighted average of the written exam (weight 0.6) and the project (weight 0.4). Honors are awarded at the instructor's discretion for exams of particularly high quality.

Teaching tools

Lectures: slides and practical programming demos will often be used, integrated with exercises and Q&A sessions at the whiteboard.

Practice: all programming activities will use the development tools provided by the Linux environment. Students will be given access to a compute server. All tools are freely available, in order to support self-study activities on own hardware, if available.

Links to further information

https://www.moreno.marzolla.name/teaching/CP/

Office hours

See the website of Moreno Marzolla