Paral·lelisme

Crèdits
6
Tipus
Obligatòria
Requisits
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

Altres

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 5 i realitzar els exercicis proposats.
    Objectius: 8 10
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    6h

    Assimilació dels principis de descomposicio en tasques

    Participar activament en les sessions de teoria/problemes. Estudiar els continguts del tema 4 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

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

    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 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)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    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)
    - FP1: nota de l'examen final de la part de teoria (temes 1 a 3)
    - FP2: nota de l'examen final de la part de teoria (temes 4 i 5)
    - FL: nota de l'examen final de la part de laboratori. L'examen final de laboratori serà un examen escrit (sobre paper) que es realitzarà el mateix dia que l'examen final.

    Addicionalment, s'avaluaran de forma continua:

    - SL: informes de seguiment del laboratori que també servirà per avaluar la competència transversal de la tercera llengua. IMPORTANT: La realització i presentació de tots els informes de seguiment del laboratori és condició necessària per superar l'assignatura. Només es considera informe elaborat i presentat aquell informe amb un mínim de contingut. Informes buits o amb només les preguntes, per exemple, no es consideren realitzats ni presentats.
    - AA: nota de les activitats online via Atenea realitzades dins del període establert

    aplicant la ponderació indicada a continuació:

    NL, nota laboratori:
    Si (FL>4)
    NL = MAX(SL,FL)
    si no
    NL = 0.35*SL+0.65*FL

    N, nota de l'assignatura sense tenir en compte els qüestionaris Atenea:
    Si P<5,0
    N = 0,65*(0.5*FP1 + 0.5*FP2) + 0.35*NL
    si no
    N = 0,65*(0.5*max(P,FP1)+0,5*FP2) + 0.35*NL

    NF: nota final de l'assignatura incorporant el factor Atenea de seguiment, si escau.
    Si N>=5,0 i FP2>=5,0 llavors NF = MIN(10, N * (1 + AA/100)); si no NF=N.


    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àsic

    Complementari

    • 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.