ECTS credits ECTS credits: 4.5
ECTS Hours Rules/Memories Student's work ECTS: 74.2 Hours of tutorials: 2.25 Expository Class: 18 Interactive Classroom: 18 Total: 112.45
Use languages English
Type: Ordinary Degree Subject RD 1393/2007 - 822/2021
Center Higher Technical Engineering School
Call: Second Semester
Teaching: Sin Docencia (En Extinción)
Enrolment: No Matriculable (Sólo Alumnado Repetidor)
This course has as main objective to introduce students into the topic of parallel programming for shared memory multicore systems and for multiprocessors. We will make special emphais in developing high level abstractions to facilitate the detection of concurrency in applications. Furthermore, students will learn the schemes that allow to use concurrency in computer systems.
PROGRAM
The program of theory concepts will be developed during a total of 12 classes. A total of 27 hours will de devoted to labs and resolution of practical cases.
THEORY
Part 1. Mechanisms for Implementing Parallel Programming (6 hours).
- Parallel programming for shared memory systems: OpenMP.
- Parallel programming for message passing systems: MPI.
- Parallel programming for manycore systems: OpenMP.
- Scaling and Amdahl law.
Objective: to show the interfaces for concurrency programming in two well-known and widely accepted paradigms: message passing and shared memory. To introduce the concept of scaling and its limits.
Part 2: Theoretical Introduction to Parallel Programming (2 hours)
- Problem Analysis.
- Problem Decomposition.
- Task Guided Deocomposition.
- Data Guided Decomposition.
- Communitation.
- Synchronization.
- Data Dependences.
- Load Banced.
- Granularity.
- Input/Output.
- Dubugging.
- Performance Analysis and Tuning.
Objective:To dive a high level introduction of the main theoretical concepts of parallel programming. Our main goal is to give a minimmal theoretical basis to approach parallel programming from a full practical point of view.
Part 3: Examples of Parallelization (4 hours)
Objective: present several examples, starting from a pure serial version, obtaining different parallel versions, with differnt degree of efficiency.
LABS
The labs will be carried out at the multiprocessors of CESGA and in multicore systems available at the ETSE.
BLOCK 1: Basic programming with OpenMP, MPI (6 hours)
Objective: to become familiar with message passing programing (MPI), share memory programming (OpenMP).
BLOCK 2: Parallel programming of basic algorithms (6 hours).
Objective: to apply the methodology for parallel programming described in the theory classes to simple examples, using OpenMP and MPI.
BLOCK3: Parallel programming project (12 hours).
Objective: to parallelize an application of certain complexity, applying the methodology described in the course. To optimize the implementation to obtain good scaling characteristics. To make a detailed study of scaling with number of processors and problem size. The project can be carried out in groups of two students.
Basic:
T.G. Mattson, B.A. Sanders and B.L. Massingill, Patterns for Parallel Programming, Addison-Wesley, 2005.
This is the fundamental reference for the theory classes. It shows a methodology based on patterns for parallel programming, that corresponds directly with the contents of the course. This is the methodology that Intel, is trying that all programmers assimilate, to overcome the grand challenge of parallel programming. Taking into account the contents of the book, we could say that the most of it is atemporal, and we could say that the methodology for parallalel programming is not progressing in a clear way during the last years.
P. Pacheco, "An Introduction to Parallel Programming", Morgan Kaufmann Publishers, 2011.
Introductory book on parallel programming that omplements the book listed above. Simple methodologies and examples are introduced for parallel programming with OpenMP and MPI.
https://computing.llnl.gov/tutorials/parallel_comp/. Blaise Barney, Lawrence Livermore National Laboratory
Web of the Lawrence Livermore National Laboratory that includes an introduction to parllel programming.
Complementary:
S. Akhter and J. Roberts, Multi-core Programming. Increasing Performance through Software Multi-threading, Intel Press, 2006.
This is a book edited by Intel, that complements the previous one, where more low level details for the implementation of parallel programs are described.
Kirk, D. B., & Wen-mei, W. H. (2010). Programming massively parallel processors: a hands-on approach. Morgan Kaufmann Publishers.
Basic concepts of parallel programming and GPU architecture. Several techniques for constructing parallel programs are explored in detail.
M.J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill, 2004.
This books is a reference for programming with MPI and OpenMP, with description of simple parallel programming examples.
B. Chapman, G. Jost and . van der Pas, "Using OpenMP: Portable Shared Memory Parallel Programming", The MIT Press, 2007
This is reference book for programming with OpenMP, with focus in programming for high performance, with a significant number of examples and detailed explanation of the functionalities of OpenMP.
J. Levesque, Aaron Vose, "Programming for Hybrid Multi/ManyCore Mpp Systems", CRC, 2018.
Libro recente que aborda exemplos complexos de paralelización con OpenMP e MPI.
To contribute to achieve the competences described in the document "Grao de Enxeñería Informática na USC" (CG4, CG9, TR1, TR2, TR3, RI1, RI6, RI7, RI8, RI14).
Competences associated to the Computer Engineering module:
- To know how to determine the computational complexity of an algorithm and to evaluate the most suitable implementation of a given algorithm according to the available resources (memory and execution time).
- To know the diferent programming paradigms and to be able to choose the most appropriate in every situation.
- Knowledge of the different programming paradigms.
This course has a focus on learn by doing. We have the following type of classes:
Regular Classes (12 hours): during these classes, the professor will present briefly the contents of the program of theory. The students will have access to all the class material beforehand, so that it is expect a high participation of the students in the discussion of the different topics. The professor will incentivate participation, and some parts of the program will be assigned to students to make a brief presentation in the class.
Labs (24 hours): these classes will be devoted to develop the labs proposed for the course. Basically they will consist in performing increasingly complex parallel programs up to a point of assigning a parallel programming project to groups with two students each. The students will be the active elements in these classes, and the professor will guide the learning process by answering the different questions raised by them. Labs guides and objectives will be provided through the virtual campus of the USC.
Discussion classes (3 hours): In these classes the students will present their projects, discussing the implementation at different levels and the scaling properties of the application.
The office ours ("tutorias" in spanish) may be held in the professor's office (schedule in agreement with the students or determined by the School), through e-mail or through the Virtual Campus.
Regular (at the end of the course):
Contributions to the final grade and evaluation criteria (for a maximun of 10 points):
- Participation in the development of the theory classes (1.5p): the student can be graded up to 1.5 points for participation on the theory classes. They may participate by presenting some concepts or discussing and asking questions or solving questions raised by other peers. In this section the following competences, implicitly or explicitly, are evaluated: CG4, TR1, RI1, RI6, RI7, RI8 e RI14, PROG1, PROG2, PROG3.
- Adqusition of knowledge with OpenMP and MPI and CUDA (1.5p): aspects to be taken into account will be the degree of knowledge adquired while performing the proposed exercises and its quality. In this section the following competences, implicitly or explicitly, are evaluated: TR1, TR3, RI6, RI8, RI14, PROG3.
- Programming simple parallel programs (2p): aspects to be taken into account are the application of the described methodology, and the use of efficient structures for programming with OpenMP and MPI. In this section the following competences, implicitly or explicitly, are evaluated: TR1, TR3, RI6, RI14.
- Parallel programming project (5p): aspects to be taken into account are the application of the described methodology for parallel programming, the degree of dificulty selected by the students for the project (the project proposal by the professor will be somehow open, and the students will decide the degree of dificulty they want to implement), quality of the analysis of scaling and characterizaton of the program, and presentation of resutls. In this section the following competences, implicitly or explicitly, are evaluated: CG9, TR1, TR2, TR3, RI1, RI7, RI14, PROG1, PROG2, PROG3.
There is not a minimum requirement in each part. To pass the course, a minimum of five points should be achieved.
Students that have been enrolled in this course in previous years do not keep achieved gradings in the different parts.
Recovery (July) and Extraordinary evaluation:
Same criteria as for the ordinary evaluation. The deadline for presenting the project and the results of the labs will be data of the exam. The students will make a presentation of the proyect the day of the exam.
Conditions for the qualification “Non presentado”: not to deliver any lab nor perform the project.
The interation during office hours, the resolution of exercises and practical cases in the class, and the labs will allow the professor to know informally the dregree of assimilation of the contents that students achieve during the development of the course.
For 4.5 ECTS credits, the personal work of a student should be about 67.5 hours, distributed in the following way:
- Autonomous work: 20 hours, devoted to the assimilation of the theoretical contents of the course, and preparation of assigments by the professor to make presentations of different topics at class.
- Writing exercises, conclusions and other assigments: 5 hours, basically devoted to prepare the presentation of the results of the project.
- Programming/experimentation: 35 hours, devoted to the resolution of the labs and project.
- Avaliation activities: 7.5 hours, devoted to the presentation of results of the project, and modifications required after correction and presentation, incorporating the feedback received by the professor and other students.
The scheduling of tasks will try to achieve a uniform distribution of workload during the course. However, this distribution may vary at some hot spots such us when preparing the project and when presenting its results.
It is highly recomendable to have knowledge of C. It is also of interest to have taken the course Parallel Systems or Sistemas Distribuídos e Paralelos (ETIS).
This course is designed to achieve a high student participation during its development.
The delivery of course material and electronic communications with the students will be carried out through the tools of the virtual campus of the USC.
English will be used for some topics and class notes.