Saltar al contingut Menu
Map
  • Home
  • Information
  • Contact
  • Map

Multiprocessors (MP)

Credits Dept. Type Requirements
7.5 (6.0 ECTS) AC
  • Elective for DIE
  • Elective for DCSYS
 AC - Prerequisite for DIE , DCSFW

Instructors

Person in charge:  (-)
Others:(-)

General goals

In this subject, students should gain an understanding of the basic concepts of multiprocessors: their terminology, structure and most common problems, as well as the most common solutions. The aim is for students to get to know and learn how to use current systems. Students must develop a critical approach to the analysis of the true functioning of these systems, so as to improve their performance.

Specific goals

Knowledges

  1. Parallelism and the structures of multiprocessor systems.
  2. Programming models: Shared memory (OpenMP) and message passing (MPI).
  3. Coherence and consistency: Bus and directory-based systems.
  4. Synchronisation and implementation of programming models.
  5. Interconnection networks.
  6. Operating Systems for multiprocessors: Planning.
  7. Examples of some real systems.

Abilities

  1. Ability to write simple parallel programmes in OpenMP, MPI, or combination thereof.
  2. Analyse their performance and justify/explain the effects observed.
  3. Identify system bottlenecks and estimate their impact when using a given computer.

Competences

  1. Being honest with oneself: being able to distinguish between what one knows for certain and what is merely speculation or a working hypothesis. Ability to make the best of one"s knowledge (which is necessarily incomplete).
  2. Ability to speculate on the causes of observed behaviour. Ability to design experiments / make measurements to test hypotheses.
  3. Ability to work in a small group.

Contents

Estimated time (hours):

T P L Alt Ext. L Stu A. time
Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Parallelism and multiprocessors
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 2,0 0 6,0
Parallelism: Concept, work overload, synchronisation, load balance, Amdahl"s Law.



Multiprocessors: Basic structures, top500.



Programming models: direction space structures requiring code parallelisation.

2. OpenMP
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 4,0 0 12,0
Description of the language



Example of the impact of each directive on each thread.



Implementation: Compiler and run time.

3. MPI (Message-Passing Interface)
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 4,0 0 12,0
Description of primitives: Collective communication primitives and point-to-point primitives.



Example of the impact of the primitives on each process.



Run-time implementation.

4. Coherence and consistency in shared-memory multiprocessors
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 6,0 0 0 0 6,0 0 18,0
Issue: the concept of time.



Basic solutions to guarantee coherence in bus-based systems and directory-based systems.



Advanced solutions: buffering calls, multi-level caches, simple buses (shared clock-cycle).

5. Sychronisation
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 2,0 0 6,0
Synchronisation algorithms (mutual exclusion, point-to-point barriers) and their interaction with the coherence mechanism.

6. Interconnection networks
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 4,0 0 0 0 4,0 0 12,0
Components.



Topologies.



Routing algorithms.



Commutation strategies.



Flow control.



Network interface.

7. Operating Systems for multiprocessors
T      P      L      Alt    Ext. L Stu    A. time Total 
2,0 2,0 0 0 0 2,0 0 6,0
Maleability.



Policies for planning long-term jobs.



Planning policies for short/medium-term processes.



Co-ordination between levels.



Memory management: page collocation.

8. Some real systems
T      P      L      Alt    Ext. L Stu    A. time Total 
4,0 0 0 0 8,0 0 0 12,0
Selection of a pair of current multiprocessors and description of their structure and workings in relation to the concepts dealt with in the course.











  • Additional laboratory activities:
    Selection of another multiprocessor not described in class. The assignment will involve students describing the options chosen in the design of the multiprocessor, relating these to the structures seen in class.

9. Performance analysis.
T      P      L      Alt    Ext. L Stu    A. time Total 
0 0 6,0 0 0 6,0 0 12,0

  • Laboratory
    Visualisation and analysis using Paraver: Navigation, configuration files (metrics: state, user functions and run time, hardware counter derivatives, etc.).
    Application of a sequential programme, OpenMP and MPI.
    Trace obtaining.

10. Parallelisation with OpenMP.
T      P      L      Alt    Ext. L Stu    A. time Total 
0 0 6,0 0 0 6,0 0 12,0

  • Laboratory
    Parallelisation of a give sequential source with OpenMP.
    Performance optimisation.
    Adjusting results using Amdahl's Law.

11. Parallelisation with MPI.
T      P      L      Alt    Ext. L Stu    A. time Total 
0 0 6,0 0 0 6,0 0 12,0

  • Laboratory
    Parallelisation of a give sequential source with MPI.

    Performance optimisation. Adjusting results using Amdahl's Law.

12. Programming communication/synchronisation basic primitives.
T      P      L      Alt    Ext. L Stu    A. time Total 
0 0 6,0 0 6,0 0 0 12,0

13. Advanced concepts
T      P      L      Alt    Ext. L Stu    A. time Total 
6,0 4,0 0 0 0 6,0 0 16,0
Description of advanced aspects of all of the foregoing themes: Multi-level parallelism in OpenMP, One-sided Communications in MPI, MPI+OpenMP, Relaxed consistency systems, SDSM.


Total per kind T      P      L      Alt    Ext. L Stu    A. time Total 
34,0 28,0 24,0 0 14,0 48,0 0 148,0
Avaluation additional hours 4,0
Total work hours for student 152,0

Docent Methodolgy

(-)

Evaluation Methodgy

A course exam will be held. Students will be permitted to use notes during one part, lasting an hour. Notes will not be allowed during the remainder of the exam. The grade awarded will range between 0 and 10.







A short report must be submitted for each of the three practical assignments. An integer grade ranging between 0 and 3 will be awarded. The grade will be based on each report and on work in the lab class. The overall grade for the practical work will be the average of those for the three assignments.







The final grade will be calculated as follows:







- If the three practical assignments have been submitted and the average grade exceeds 0, then:







Final = min(10, exam + Practical work/2)







- If this is not the case (i.e., failure to submit all three assignments, or a zero grade for the three):







Final = Exam / 2

Basic Bibliography

  • David E. Culler, Jaswinder Pal Singh Parallel computer architecture : a hardware/software approach, Morgan Kaufmann Publishers, 1999.

Complementary Bibliography

(no available informacion)

Web links

  1. http://www.openmp.org


  2. http://www-unix.mcs.anl.gov/mpi/


  3. http://www.netlib.org/utk/papers/mpi-book/mpi-book.html


  4. http://people.ac.upc.es/jesus/multiprocesadores


Previous capacities

(-)


Compartir
Share

 
logo FIB © Barcelona school of informatics - Contact - RSS
This website uses cookies to offer you the best experience and service. If you continue browsing, it is understood that you accept our cookies policy.
Classic version Mobile version