Paral·lelisme

Esteu aquí

Crèdits
6
Tipus
Obligatòria
Requisits
  • Prerequisit: AC
Departament
AC
L'assignatura Paral·lelisme cobreix els aspectes fonamentals relacionats amb la programació paral·lela, eina bàsica avui en dia per treure profit de les arquitectures multi-nucli que constitueixen els computadors actuals. Es treballen les principals estratègies de descomposició per tasques i de dades, així com els mecanismes necessaris per assegurar la correctesa (sincronització, exclusió mútua, ...) i formes de millorar el seu rendiment.

Professorat

Responsable

  • Daniel Jimenez Gonzalez ( )

Altres

  • Adrián Munera Sánchez ( )
  • Eduard Ayguadé Parra ( )
  • Gladys Miriam Utrera Iglesias ( )
  • Jordi Tubella Murgadas ( )
  • Josep Ramon Herrero Zaragoza ( )
  • Lluc Álvarez Martí ( )
  • Mario Cesar Acosta Cobos ( )
  • Pedro José Martínez Ferrer ( )
  • Rosa Maria Badia Sala ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Tècniques

Competències tècniques comunes

  • CT1 - Demostrar coneixement i comprensió de fets essencials, conceptes, principis i teories relatives a la informàtica i a les seves disciplines de referència.
    • CT1.1B - Demostrar coneixement i comprensió dels conceptes fonamentals de la programació i de l'estructura bàsica d'un computador. CEFB5. Coneixement de l'estructura, funcionament i interconnexió dels sistemes informàtics, i dels fonaments de la seva programació.
  • CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
    • CT5.1 - Triar, combinar i explotar diferents paradigmes de programació, en el moment de construir software, tenint en compte criteris com la facilitat de desenvolupament, l'eficiència, la portabilitat i la mantenibilitat.
    • CT5.3 - Dissenyar, escriure, provar, depurar, documentar i mantenir codi en un llenguatge d'alt nivell per a resoldre problemes de programació aplicant esquemes algorísmics i utilitzant estructures de dades.
    • CT5.6 - Demostrar coneixement i capacitat d'aplicació dels principis fonamentals i de les tècniques bàsiques de la programació paral·lela, concurrent, distribuïda i en temps real.
  • CT6 - Demostrar coneixement i comprensió del funcionament intern d'un computador i del funcionament de les comunicacions entre ordinadors.
    • CT6.2 - Demostrar coneixement, comprensió i capacitat d'avaluar l'estructura i l'arquitectura dels computadors, i els components bàsics que els componen.
  • CT7 - Avaluar i seleccionar plataformes de producció hardware i software per a l'execució d'aplicacions i de serveis informàtics.
    • CT7.2 - Avaluar sistemes hardware/software en funció d'un criteri de qualitat determinat.
  • CT8 - Planificar, concebre, desplegar i dirigir projectes, serveis i sistemes informàtics en tots els àmbits, liderar-ne la posada en marxa, la millora contínua i valorar-ne l'impacte econòmic i social.
    • CT8.1 - Identificar tecnologies actuals i emergents i avaluar si són aplicables, i en quina mesura, per a satisfer les necessitats dels usuaris.

Competències Transversals

Tercera llengua

  • G3 [Avaluable] - Conèixer l'idioma anglès amb un nivell adequat de forma oral i escrita, i en consonància amb les necessitats que tindran els graduats i les graduades en Enginyeria Informàtica. Capacitat de treballar en un grup multidisciplinar i en un entorn multilingüe i de comunicar, tant per escrit com de forma oral, coneixements, procediments, resultats i idees relacionats amb la professió d'enginyer tècnic en informàtica.
    • G3.2 - Estudiar amb materials escrits en anglès. Redactar un informe o un treball de tipus tècnic en anglès. Participar en una reunió tècnica en anglès.

Objectius

  1. Capacitat de formular models senzills de rendiment donada una estratègia de paral.lelització per una aplicació, que permetin estimar la influència dels principals aspectes arquitectònics: numero d'elements de proces, cost d'accés a les dades, cost de la interacció entre elements de procés, entre d'altres.
    Competències relacionades: CT7.2,
  2. Capacitat de mesurar, emprant eines de instrumentació, visualització i anàlisi, el rendiment assolit amb l'execució paral.lela d'una aplicació i detectar els factors que limiten aquest rendiment: granularitat de tasques, distribució equitativa de càrrega de treball, interacció entre tasques, entre d'altres.
    Competències relacionades: CT7.2,
  3. Capacitat de compilar i executar un programa paral.lel, utilitzant les eines bàsiques a nivell de línia de comandes per mesurar el temps d'execució.
    Competències relacionades: CT7.2, CT5.3,
  4. Capacitat d'aplicar optimitzacions senzilles en fragments de codi paral.lel per tal de millorar el seu rendiment en arquitectures paral.leles, atacant els factors que limiten el seu rendiment.
    Competències relacionades: CT7.2, CT6.2,
  5. Capacitat d'escollir l'estratègia de descomposió mes apropiada per expressar el paral.lelisme en una aplicació (tasques, dades).
    Competències relacionades: CT5.1,
  6. Capacitat d'aplicar les tècniques bàsiques que permeten sincronitzar l'execució paral.lela, evitant les condicions de carrera i abraçada mortal, i afavorint el solapament entre càlcul i interacció, entre d'altres.
    Competències relacionades: CT5.1,
  7. Capacitat d'implementar en OpenMP la versió paral.lela d'una aplicació seqüencial.
    Competències relacionades: CT5.3, CT5.6,
  8. Capacitat d'identificar els diferents tipus de paral.lelisme que es poden explotar en una arquitectura de computador (ILP, DLP i TLP dins d'un processador, multiprocessador i multicomputador) i descriure els seus principis bàsics de funcionament.
    Competències relacionades: CT8.1, CT6.2, CT1.1B,
  9. Capacitat d'entendre els mecanismes bàsics que permeten la compartició coherent de dades en una arquitectura paral·lela de memoria compartida, amb accés uniforme i no uniforme a memòria.
    Competències relacionades: CT8.1, CT6.2, CT1.1B,
  10. Capacitat de seguir l'assignatura emprant els materials proporcionats en anglès (transparències, enunciats de pràctiques, problemes, ...) aixì com realitzar els actes d'avaluació (controls i exàmen final) amb l'enunciat escrit en anglès.
    Competències relacionades: G3.2,
  11. En cas d'optar per la competència transversal Tercera Llengua, capacitat d'elaborar els entregables de les pràctiques de laboratori (parcial o totalment) en anglès.
    Competències relacionades: G3.2,

Continguts

  1. Introducció i motivació
    Necessitat del paral.lelisme, paral.lelisme vs. concurrència, possibles problemes en l'us concurrència: deadlock, lifelock, starvation, fairness, data races
  2. Anàlisi d'aplicacions paral.leles
    Mètriques bàsiques: paral·lelisme, temps d'execució, speedup i escalabilitat. Análisi de l'impacte dels overheads associats a la creació de tasques i la seva sincronització i la compartició de dades. Eines per la predicció i l'anàlisi de paral.lelisme i visualització de comportament: Paraver i Tareador
  3. Programació amb memòria compartida: OpenMP
    Regions paral.leles, threads i tasques. Mecanismes de sincronització entre tasques i threads. Distribució de feina estàtica/dinàmica, granularitat.
  4. Introducció a les arquitectures paral.leles
    Paral.lelisme dins d'un processador (ILP, DLP i TLP) i entre els processadors que formen els multiprocessadors de memòria compartida SMP i ccNUMA (coherència de cache, consistència de memòria, sincronització).
  5. Principis de programació paralela: descomposició en tasques
    Task decomposition vs. data decomposition. Descomposcio en tasques, granularitat i anàlisi de dependències. Identificació de patrons de paral.lelisme: iterative vs. divide and conquer task decompositions. Mecanismes per implementar la descomposició en tasques: creació de regions paral·leles i tasques; mecanismes per garantir task ordering i data sharing.
  6. Principis de programació paralela: descomposició de dades
    Descomposició de dades (descomposició geomètrica vs. estructures recursives) per arquitectures amb memoria compartida. Localitat en l'accés a les dades en arquitectures paral·leles de memòria compartida. Generació de codi en funció de la descomposició de dades. Breu introducció a les arquitectures de memòria distribuïda i la seva programació (cas concret: MPI).
  7. Revisió de problèmes d'examens
    En aquestes sessions es resoldran dubtes que l'estudiantat pugui tenir alhora de resoldre problemes d'examens.

Activitats

Activitat Acte avaluatiu


Assimilació del conceptes fonamentals i eines per modelar i analitzar el comportament d'aplicacions paral.leles

Participar activament en les sessions de teoria/problemes. Estudiar els continguts del temes 1 i 2 i realitzar els exercicis proposats. Resolució de les pràctiques proposades en les sessions de laboratori i extracció de conclusions dels resultats obtinguts.
Objectius: 1 3 2 10
Continguts:
Teoria
6h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Ús d'OpenMP per l'expressio de paral.lelisme en memòria compartida

Participar activament en les sessions de laboratori. Fer els treballs/lectures prèvies proposades, resoldre els exercicis durant les sessions de laboratori, analitzar resultats, extreure conclusions dels experiments i elaboració dels lliuraments corresponents.
Objectius: 4 7 10 11
Continguts:
Teoria
0h
Problemes
0h
Laboratori
22h
Aprenentatge dirigit
0h
Aprenentatge autònom
22h

Assimilació dels aspectes fonamentals en les arquitectures paral.leles

Participar activament en les sessions de teoria/problemes. Estudiar els continguts del tema 4 i realitzar els exercicis proposats.
Objectius: 8 10
Continguts:
Teoria
6h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h

Examen parcial


Objectius: 9 1 5 6 7 10
Setmana: 7
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Assimilació dels principis de descomposicio en tasques

Participar activament en les sessions de teoria/problemes. Estudiar els continguts del tema 5 i realitzar els exercicis proposats. Aplicar els nous coneixements per la resolució de les pràctiques de laboratori associades.
Objectius: 5 6 10
Continguts:
Teoria
8h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Assimilació dels principis de descomposió de dades

Participar activament en les sessions de teoria/problemes. Estudiar els continguts del tema 6 i realitzar els exercicis proposats. Aplicar els nous coneixements per la resolució de les pràctiques de laboratori associades.
Objectius: 5 6 10
Continguts:
Teoria
8h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Revisió de problèmes del control

Estudiar la solució proposada pels problemes del control i contrastar-la amb la solució lliurada. Discussió de les diferències observades.
  • Aprenentatge dirigit: Realització d'activitats pràctiques dirigides, en grups petits, sobre altres models de programació
Objectius: 9 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
4h

Examen final


Objectius: 8 9 4 5 6 7 10
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
3h
Aprenentatge autònom
16h

Metodologia docent

Les classes de teoria introdueixen tots els coneixements, les tècniques, els conceptes necessaris que es posen en pràctica en les hores dedicades a problemes i de laboratori, així com amb treball personal utilitzant una col·lecció de problemes. Les dues hores de classes de teoria/problemes es fan setmanalment. Les dues hores de classes de laboratori també es fan setmanalment, i es valorarà la participació activa i rendiment durant les sessions de laboratori (treball en la pràctica, avançant en la mesura de lo possible per tal d'assolir els objectius de cada sessió). El curs utilitza el llenguatge de programació C i el model de programació paral·lela OpenMP.

Mètode d'avaluació

La nota de l'assignatura (NF) es calcula a partir dels components següents (tots avaluats sobre 10):
- P: nota de l'examen parcial (inclou temes 1 a 3)
- F: nota de l'examen final (temes 1 a 5)
- L: nota de laboratori
- AA: nota de les activitats online via Atenea realitzades dins del període establert

aplicant la ponderació indicada a continuació:
N = 0,75*max(F, 0,35*P+0,65*F) + 0,25*L
Si N>=5,0 llavors NF = MIN(10, N * (1 + AA/100)); si no NF=N.

La nota de laboratori (L) s'obté a partir de les notes dels entregables modulada per l'assistencia a les sessions de laboratori, la participació activa i rendiment i el resultat d'una possible entrevista a final de curs. Com participació activa durant les sessions ens referim a la demostració fefaent d'estar treballant en la pràctica, avançant en la mesura de lo possible per tal d'assolir els objectius de cada sessió.

La competència transversal de tercera llengua s'avaluarà a partir dels informes de pràctiques. Aquests informes s'haurà d'escriure en anglès i requeriran la lectura prèvia de l'enunciat de la pràctica (també en anglès). S'avaluarà tant l'estructura del document escrit com la capacitat de transmetre els resultats i les conclusions de la pràctica, seguint les rúbriques publicades amb antelació. La competència s'avaluarà amb valors A, B, C, D, NA on:

- A indica que la competència s'ha superat amb un nivell d'excel·lència
- B indica que la competència s'ha superat amb el nivell desitjat
- C indica que la competència s'ha superat amb un nivell suficient
- D indica que la competència no s'ha superat
- NA indica que la competència no s'ha avaluat

Bibliografia

Bàsica:

Complementaria:

  • Parallelism - Unit 1: Why Parallel Computing - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 2: Understanding Parallelism - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 3: Introduction to parallel architectures - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 4: Mastering your task decomposition strategies: going some steps further - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 5: Data-aware task decomposition strategies - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Collection of Exercises - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Selection of Exams (with Solutions) - Eduard Ayguade, Josep Ramon Herrero, Daniel Jimenez and Gladys Utrera, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism Laboratory Assignments - Eduard Ayguadé et al., Departament d'Arquitectura de Computadors , 2022.
  • Computer architecture: a quantitative approach - Hennessy, J.L.; Patterson, D.A, Elsevier, Morgan Kaufmann , 2019. ISBN: 9780128119051
    https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004117509706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
  • Parallel computer architecture: a hardware/software approach - Culler, D.E.; Singh, J.P.; Gupta, A, Morgan Kaufmann Publishers , 1999. ISBN: 9781558603431
    https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001862689706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacitats prèvies

Les capacitats prèvies són les definides pels pre-requisits de l'assignatura.