Paral·lelisme

Esteu aquí

Crèdits
6
Tipus
Obligatòria
Requisits
  • Prerequisit: AC
  • Prerequisit: EDA
  • Prerequisit: SO
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, ...).

Professors

Responsable

  • Eduard Ayguadé Parra ( )

Altres

  • Daniel Jimenez Gonzalez ( )
  • Gladys Miriam Utrera Iglesias ( )
  • Jordi Tubella Murgadas ( )
  • Josep Ramon Herrero Zaragoza ( )
  • Julian David Morillo Pozo ( )
  • Lluc álvarez Martí ( )
  • 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 - 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. L'alumne ha de ser capaç 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.
    Related competences: CT7.2,
  2. L'alumne ha de ser capaç 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.
    Related competences: CT7.2,
  3. L'alumne ha de ser capaç 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ó.
    Related competences: CT7.2, CT5.3,
  4. L'alumne ha de ser capaç 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
    Related competences: CT7.2, CT6.2,
  5. L'alumne ha de ser capaç d'escollir l'estratègia de descomposió mes apropiada per expressar el paral.lelisme en una aplicació (tasques, dades).
    Related competences: CT5.1,
  6. L'alumne ha de ser capaç 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.
    Related competences: CT5.1,
  7. L'alumne ha de ser capaç d'implementar en OpenMP la versió paral.lela d'una aplicació seqüencial
    Related competences: CT5.3, CT5.6,
  8. L'alumne ha de ser capaç 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.
    Related competences: CT8.1, CT6.2, CT1.1B,
  9. L'alumne ha de ser capaç 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.
    Related competences: CT8.1, CT6.2, CT1.1B,
  10. L'alumne ha de ser capaç 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.
    Related competences: G3.2,
  11. En cas d'optar per la competència transversal Tercera Llengua, l'alumne haurà de ser capaç d'elaborar els entregables de les pràctiques de laboratori (parcial o totalment) en anglès.
    Related competences: 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. 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.
  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ó 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).
  6. Programació amb memòria compartida: OpenMP
    Regions paral.leles, threads i tasques. Task/thread barriers. Exclusió mútua i locks. Distribuïdors de feina: bucles.
  7. Revisió de problèmes de controls
    En aquestes sessions es resoldran dubtes que els estudiants puguin tenir en els problemes dels controls

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ó dels exercicis proposats en les sessions de laboratori i extracció de conclusions.
Objectius: 1 3 2 10
Continguts:
Teoria
6h
Problemes
0h
Laboratori
8h
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 teoria/problemes. Estudiar els continguts del tema 6 i preparar la realització dels exercicis proposats per les sessions de laboratori. Resolució del exercicis proposats en les sessions de laboratori i extracció de conclusions.
Objectius: 4 7 10 11
Continguts:
Teoria
0h
Problemes
0h
Laboratori
22h
Aprenentatge dirigit
0h
Aprenentatge autònom
22h

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ó dels exercicis de laboratori del tema 6.
Objectius: 5 6 10
Continguts:
Teoria
8h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
10h

Control temes 1, 2 i 3


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

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 descomposió de dades

Participar activament en les sessions de teoria/problemes. Estudiar els continguts del tema 5 i realitzar els exercicis proposats. Fer ús de OpenMP per l'expressió de descomposicions de dades per arquitectures amb memòria compartida.
Objectius: 5 6 10
Continguts:
Teoria
6h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Control temes 4 i 5


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

Revisió de problèmes dels controls

Participar activament en les sessions de problemes.
  • 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
12h

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.

El curs utilitza el llenguatge de programació C i principalment el model de programació paral·lela OpenMP.

Mètode d'avaluació

La nota de l'assignatura es calcula a partir de 2 notes:
- Nota de continguts teòrics (pes 70%).
- Nota de laboratori (pes 30%).

La nota de laboratori (Lab) s'obté bàsicament a partir de les notes dels entregables, modulada pel rendement durant les sessions de laboratori i el resultat d'una possible entrevista a final de curs per part del professor de laboratori.

Durant el curs es fan 2 controls C1 i C2. La nota d'avaluació contínua (AC) es calcula com la mitjana de les notes obtingudes en els 2 controls:

AC = 0.5*C1 + 0.5*C2

Si AC>=5, llavors la nota final (NF) de l'alumne serà:

NF = 0.3*Lab + 0.7*AC

L'alumne haurà de fer l'examen final (EF) en cas de que AC<5. En aquest cas, la nova nota final es calcularà:

NF = 0.3*Lab + 0.7*max(EF, 0.25*AC + 0.75*EF)

Si algun alumne que hagi aprovat l'avaluació continua (AC>=5) vol fer l'examen final amb l'objectiu de pujar nota, te que avisar al coordinador de l'assignatura per e-mail com a mínim amb una setmana d'antelació a la data de l'examen. En aquest cas, la nova nota final es calcularà tal como s'indica a continuació:

NF = 0.3*Lab + 0.7*max(EF, AC)

La competència transversal de tercera llengua s'avaluarà a partir del lliurament dels informes de les pràctiques. Aquests informes s'haurà d'escriure (parcial o totalment) en anglès i podràn requerir la lectura prèvia d'un document (també en anglès) sobre el contingut de la pràctica. 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, NO on:
- A indica que la competència s'ha superat amb un nivell d'execel.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:

Capacitats prèvies

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