Paral·lelisme

Esteu aquí

Inici » Estudis » Graus » Grau en Enginyeria Informàtica » Pla d'estudis » Assignatures » Paral·lelisme
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 ( )
  • Jesus Jose Labarta Mancho ( )
  • Jordi Tubella Murgadas ( )
  • Josep Ramon Herrero Zaragoza ( )
  • 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).

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
10h

Ú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
1h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

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

Sessió extra de dubtes per l'examen parcial

L'estudiant podrà fer la petició dels problemes que vulgui repassar per avançat, però també podrà realitzar peticions durant la sessió.
Objectius: 8 9 1 3 2 4 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
0h

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

Sessió formativa: repàs de les solucions dels problemes de l'examen parcial i retroacció general dels errors trobats.

Amb aquesta sessió formativa l'estudiantat podrà acabar d'assimilar conceptes de la primera meitat del quadrimestre.
  • Aprenentatge dirigit: Realització d'una sessió de repàs amb les solucions de les preguntes del control parcial. Aquesta sessió extra de resolució de problemes ha d'ajudar a donar una retroacció general del control parcial a tots els alumnes que vulguin venir a la sessió.
Objectius: 8 9 1 3 2 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
0h

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
6h
Problemes
0h
Laboratori
10h
Aprenentatge dirigit
0h
Aprenentatge autònom
20h

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
6h
Problemes
0h
Laboratori
10h
Aprenentatge dirigit
0h
Aprenentatge autònom
14h

Sessió extra de dubtes per l'examen final

L'estudiant podrà fer la petició dels problemes que vulgui repassar per avançat, però també podrà realitzar peticions durant la sessió.
Objectius: 8 9 1 3 2 4 5 6 7 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
0h

Examen final (Teoria i Laboratori)

La part de laboratori estarà diferenciada de la part de teoria i serà una prova escrita sobre paper, relacionada amb el que l'estudiantat ha treballat durant el curs.
Objectius: 8 9 1 3 2 4 5 6 7 10
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen de teoria
Teoria
3h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
20h

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)
- FT: nota de l'examen final de la part de teoria (temes 1 a 5)
- FL: nota de l'examen final de la part de laboratori (25%)

Addicionalment, s'avaluaran de forma continua:

- SL: informes de seguiment del laboratori (10%) que també servirà per avaluar la competència tranversal de la tercer llengua
- AA: nota de les activitats online via Atenea realitzades dins del període establert

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

L'examen final de laboratori serà un examen escrit (sobre paper) que es realitzarà el mateix dia que l'examen final.


La competència en llengua estrangera s'avaluarà a partir dels informes lliurats per als treballs de laboratori. Aquests informes han d'estar escrits en anglès i requeriran la lectura de la descripció de l'assignació del laboratori (també en anglès) i les especificacions d'OpenMP. Tant l'estructura del document escrit com la capacitat de transmetre els resultats i les conclusions del treball s'utilitzaran per avaluar la competència. La qualificació de la competència serà A (excel·lent), B (bo), C (satisfactori), D (suspens) o NA (No avaluat).

Bibliografia

Bàsica:

Complementaria:

  • Parallelism - Unit 1: Why Parallel Computing - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 2: Understanding Parallelism - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 3: Introduction to parallel architectures - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 4: Mastering your task decomposition strategies: going some steps further - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism - Unit 5: Data-aware task decomposition strategies - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Collection of Exercises - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism: Selection of Exams (with Solutions) - Ayguade, E.; Ramon Herrero, J.R.; Jimenez, D.; Utrera, G, Departament d'Arquitectura de Computadors , 2022.
  • Parallelism Laboratory Assignments - Ayguadé, E... [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.