Concurrència, Paral·lelisme i Sistemes Distribuïts

Esteu aquí

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS;DAC
Aquest curs té com a objectiu proporcionar les bases sobre la computació com un conjunt de tasques que poden estar executant al mateix temps i que poden interactuar entre elles. Aquestes tasques poden ser executades en un o multiples processadors o distribuïts a través d'una xarxa. El curs presenta els models, els problemes, els algoritmes i sistemes que es centren en tres aspectes/mòduls principals: concurrència (múltiples processos que interactuen entre si), paral·lelisme (multiples nuclis o processadors), i distribució (multiples ordinadors en una xarxa).

Despres d'unes sessions on es presenten els fonaments, el curs consta de 3 mòduls: concurrència, paral.lelisme i distribució. L'estudiant ha de seleccionar dos dels tres mòduls. Les lliçons es complementen amb pràctiques de programació per il·lustrar els problemes i avaluar les solucions.

Professorat

Responsable

  • Jordi Guitart Fernandez ( )

Altres

  • Jorge Castro Rabal ( )
  • Josep Ramon Herrero Zaragoza ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0.5
Aprenentatge autònom
8

Competències

Competències Tècniques de cada especialitat

Xarxes de computadors i sistemes distribuïts

  • CEE2.1 - Capacitat per a entendre els models, problemes i algoritmes relacionats amb els sistemes distribuïts, així com poder dissenyar i avaluar algoritmes i sistemes que tractin la problemàtica de la distribució i ofereixin serveis distribuïts.
  • CEE2.3 - Capacitat d'entendre els models, problemes i eines matemàtiques que permeten analitzar, dissenyar i avaluar xarxes de computadors i sistemes distribuïts.

Computació d'altes prestacions

  • CEE4.2 - Capacitat d'analitzar, avaluar, dissenyar i optimitzar programari considerant l'arquitectura i de proposar noves tècniques d'optimització.

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG5 - Capacitat per aplicar solucions innovadores i realitzar avenços en el coneixement que explotin els nous paradigmes de la Informàtica, particularment en entorns distribuïts.

Competències Transversals

Treball en equip

  • CTR3 - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.

Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

Objectius

  1. Entendre la definició de sistema distribuït i les seves possibles aplicacions, a més dels desafiaments que s'han d'afrontar pel seu disseny i implementació.
    Competències relacionades: CEE2.1, CG5,
    Subcompetences:
    • Conèixer les possibles aplicacions d'un sistema distribuït
    • Entendre els desafiaments per dissenyar i implementar un sistema distribuït: heterogeneïtat, absència de visió global, concurrència, absència d'un únic punt de control, seguretat, asincronia, obertura, transparència, tolerància a fallades, escalabilitat
    • Posar exemples de sistemes distribuïts
    • Entendre la definició de sistema distribuït
  2. Entendre la problemàtica del temps i l'ordenació d'events en un sistema distribuït i explicar i implementar els mecanismes de rellotges lògics per atacar aquesta problemàtica i els algorismes per sincronitzar rellotges físics en un sistema distribuït.
    Competències relacionades: CEE2.3, CEE2.1,
    Subcompetences:
    • Entendre la problemàtica del temps i l'ordenació d'events en un sistema distribuït
    • Explicar i implementar els mecanismes de rellotges lògics per atacar aquesta problemàtica: relació happened-before, rellotges lògics de Lamport (escalars, vectorials)
    • Explicar i implementar els algorismes per sincronitzar rellotges físics en un sistema distribuït: Cristian (NTP), Berkeley
  3. Entendre la problemàtica d'obtenir un estat global consistent en un sistema distribuït i explicar el mecanisme de snapshot distribuït per atacar aquesta problemàtica, a més de definir predicats globals per l'avaluació de propietats en un sistema distribuït.
    Competències relacionades: CEE2.3, CEE2.1,
    Subcompetences:
    • Entendre la problemàtica d'obtenir un estat global consistent en un sistema distribuït
    • Definir predicats globals per l'avaluació de propietats en un sistema distribuït: propietats dels predicats (estabilitat), ocurrència dels predicats (possibly, definitely)
    • Explicar el mecanisme de snapshot distribuït de Chandy i Lamport per atacar aquesta problemàtica
  4. Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït, incloent la coordinació necessària per elecció de líder, comunicació en grup multicast, i consens.
    Competències relacionades: CEE2.3, CEE2.1, CTR3,
    Subcompetences:
    • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per la comunicació en grup multicast: multicast fiable bàsic, multicast fiable escalable, multicast ordenat (FIFO, causal, total), atomic multicast
    • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per garantir el consens: problema dels dos exèrcits, algorisme de Dolev & Strong, problema dels generals Byzantins, Paxos
    • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per l'elecció de líder: Bully, Chang & Roberts, Ring
  5. Comprendre la problemàtica de l'execució concurrent de transaccions i descriure, comparar i implementar diferents mecanismes de control de concurrència.
    Competències relacionades: CEE2.3, CEE2.1, CTR6,
    Subcompetences:
    • Descriure, comparar i implementar diferents mecanismes de control de concurrència: two-phase locking (incloent detecció i tractament de deadlock), optimistic concurrency control, timestamp ordering
    • Comprendre la problemàtica de l'execució concurrent de transaccions: lost update, inconsistent retrievals, equivalència sèrie, recuperació d'aborts (dirty read, premature write)
  6. Ampliar el concepte de transacció, el protocol de commit i els mecanismes de control de concurrència a un sistema distribuït.
    Competències relacionades: CEE2.3, CEE2.1,
    Subcompetences:
    • Ampliar els mecanismes de control de concurrència a un sistema distribuït: two-phase locking (incloent detecció i tractament de deadlock distribuït), optimistic concurrency control, timestamp ordering
    • Ampliar el concepte de transacció a un sistema distribuït
    • Descriure, comparar i implementar diferents protocols de commit distribuït: one-phase i two-phase
  7. Comprendre l'aplicació de la replicació en un sistema distribuït, a més de la problemàtica que s'introdueix a nivell de consistència, i descriure els models de consistència corresponents i la seva implementació.
    Competències relacionades: CEE2.3, CEE2.1,
    Subcompetences:
    • Descriure implementacions concretes de models de consistència: protocols basats en primari (remote-write, local-write) i protocols d'escriptura replicada (replicació activa, protocols basats en quòrum)
    • Descriure els models de consistència forta centrats en les dades: estricta, linearizability, seqüencial
    • Descriure els models de consistència relaxada centrats en les dades: ús de variables de sincronització
    • Comprendre l'aplicació de la replicació en un sistema distribuït, a més de la problemàtica que s'introdueix a nivell de consistència
    • Descriure els models de consistència centrats en el client: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads
  8. Comprendre els problemes que pot causar l'accés concurrent de diversos agents (threads) als recursos. Conèixer les estratègies de disseny que asseguren una correcta coordinació dels agents i eviten les inconveniències de l'accés concurrent
    Competències relacionades: CG1, CEE4.2,
    Subcompetences:
    • Utilitzar el formalisme dels sistemes de transicions per descriure la semàntica d'un sistema concurrent. Emprar una eina de modelatge per poder analitzar propietats.
    • Comprendre el benefici d'usar models per representar un sistema concurrent i poder analitzar les seves propietats.
    • Ser capaç de representar un sistema concurrent utilitzant un model abstracte formal i d'analitzar les seves propietats
    • Entendre els trets fonamentals a tractar en un sistema concurrent: exclusió mútua, seccions crítiques, interferències, així com les primitives bàsiques de disseny de programes concurrents.
  9. Adquirir destresa en el disseny de programes concurrents en el paradigma de memòria compartida.
    Competències relacionades: CEE2.3, CEE4.2, CTR3,
    Subcompetences:
    • Entendre la definició de fil (thread), així com el disseny de programes concurrents que utilitzen fils. Entendre les primitives bàsiques existents en un llenguatge de programació modern (com JAVA) per a garantir una correcta coordinació entre fils.
    • Entendre les interferències i bloquejos en un sistema concurrent així com saber dissenyar programes concurrents lliures d'aquests problemes.
    • Entendre i aplicar les tècniques que ofereixen els llenguatges de programació moderns pel disseny de programes concurrents: threads, semafors, seccions crítiques, monitors i condicions de sincronització.
  10. Adquirir destresa en el disseny de programes concurrents en el paradigma de pas de missatges
    Competències relacionades: CEE2.3, CEE2.1, CEE4.2, CTR3,
    Subcompetences:
    • Reconèixer i aplicar patrons de disseny concurrent que són freqüents en l'arquitectura de pas de missatges: client/servidor, filter pipeline, supervisor/worker, announcer/listener.
    • Comprendre el paradigma de pas de missatges que és característic d'alguns llenguatges de programació concurrent (Erlang). Entendre el concepte de procés en Erlang. Ser capaç de dissenyar programes de complexitat limitada en aquest llenguatge.
    • Saber traslladar algoritmes coneguts al paradigma de pas de missatges, com ara l'algoritme d'ordenació quicksort.
  11. Entendre i mesurar el paral.lelisme potencial en una aplicacion sequencial, i tambe el rendiment obtingut per una implementació paral.lela
    Competències relacionades: CG1, CEE4.2,
    Subcompetences:
    • Entendre el rendiment d'una aplicació paral.lela i els factor que intervenen en la seva degradació
    • Entendre els conceptes de descomposició en tasques i l'estimació del seu paral.lelisme potencial
    • Us d'instrumentació, visualització i anàlisi per entendre el paral.lelisme i el seu rendiment
  12. Decidir l'estrategia de descomposició per expressar el paral.lelisme d'una aplicació
    Competències relacionades: CEE4.2, CTR3, CTR6, CG5,
    Subcompetences:
    • Establir l'ordre correcte d'execució de tasques i la compartició de dades que garanteix les dependències entre tasques
    • Establir la comunicació necessària entre tasques i els esquemes de comunicació: punt-a-punt o col·lectius
    • Us de la descomposició en tasques i dades
  13. Especificar usant un model de programació paral.lela la paral.lelització d'una aplicació, d'acord amb una descomposició basada en tasques i/o dades
    Competències relacionades: CEE4.2, CTR3, CTR6, CG5,
    Subcompetences:
    • Us del paradigma message-passing interface (MPI) per a aplicacions intensives en calcul i us de dades en arquitectures de memoria distribuida
    • Us del llenguatge de programació CUDA per paral.lelitzar una aplicació a executar en una arquitectura basada en acceleradors de tipus GPU

Continguts

  1. Sistemes de transició i algebra de processos
    Processos seqüencials i sistemes de transició. Contruccions prefix i choice. Concurrència de processos, concepte i construcció. Anàlisi de sistemes de transició. Implementacions en Java i Erlang.
  2. Comprensió del paral·lelisme
    Introducció a arquitectures paral·leles: arquitectures i acceleradors de memòria compartida i distribuïda. Gràfic de tasques: nodes i arestes. Mètriques. Speed-up i eficiència. Llei Amdahl.
  3. Conceptes de sistemes distribuïts
    Definició de sistema distribuït. Possibles aplicacions d'un sistema distribuït. Exemples de sistemes distribuïts. Desafiaments per dissenyar i implementar un sistema distribuït: heterogeneïtat, seguretat, absència de visió global, concurrència, absència d'un únic punt de control, asincronia, obertura, transparència, tolerància a fallades, escalabilitat.
  4. Propietats de seguretat (safety) i vivacitat (liveness).
    Descripció i exemples de propietats de seguretat. Anàlisi propietats de seguretat sobre sistemes de transició. Descripció de les propietats de vivacitat i especialment de les propietats de progrés. Anàlisi de propietats de progrés en sistemes de transició.
  5. Concurrència, exclusió mútua i condicions de sincronització. Deadlock.
    El problema de la interferència destructiva. Locks i exclusió mútua. Semàfors, monitors i condicions de sincronització. El problema del deadlock i la seva anàlisi sobre sistemes de transició. Estratègies de disseny per impedir deadlocks.
  6. Pas de missatges. Arquitectures
    Descripció del paradigma de pas de missatges. L'arquitectura client/servidor. Introducció a altres arquitectures: Filter pipeline, supervisor/worker, announcer/listener. Pas de missatges en Erlang. Dissenys d'arquitectures en Erlang.
  7. Predicció i anàlisi del rendiment
    Utilització de models i eines per comprendre el paral·lelisme i el rendiment (Tareador, Extra, Paraver i Dimemas).
  8. Programació de memòria distribuïda mitjançant MPI
    Descripció general de l'arquitectura del clúster. Creació, identificació i resolució de processos. Operacions col·lectives punt a punt. Comunicacions síncrones vs asincròniques.
  9. Programació de dispositius GPU per a l'acceleració de la computació mitjançant CUDA
    Descripció de l'arquitectura GPU. Descomposicions adequades per a l'acceleració GPU. Principis de programació CUDA. Model d'execució paral·lela CUDA: amfitrió i dispositiu.
  10. Algorismes distribuïts: Temps, estat global, coordinació i consens
    Temps i l'ordenació d'events en un sistema distribuït. Rellotges lògics: relació happened-before, rellotges lògics de Lamport (escalars, vectorials). Algorismes per sincronitzar rellotges físics en un sistema distribuït: Cristian (NTP), Berkeley. Estat global consistent en un sistema distribuït. Mecanisme de snapshot distribuït de Chandy i Lamport. Predicats globals per l'avaluació de propietats en un sistema distribuït: propietats dels predicats (estabilitat), ocurrència dels predicats (possibly, definitely). Coordinació de processos en un sistema distribuït per l'elecció de líder: Bully, Ring. Coordinació de processos en un sistema distribuït per la comunicació en grup multicast: multicast fiable bàsic, multicast fiable escalable, multicast ordenat (FIFO, causal, total), atomic multicast. Coordinació de processos en un sistema distribuït per garantir el consens: problema dels dos exèrcits, algorisme de Dolev & Strong, problema dels generals Byzantins, Paxos
  11. Dades compartides distribuïdes: Transaccions, consistència i replicació
    Execució concurrent de transaccions: lost update, inconsistent retrievals, equivalència sèrie, recuperació d'aborts (dirty read, premature write). Mecanismes de control de concurrència: two-phase locking (incloent detecció i tractament de deadlock), optimistic concurrency control, timestamp ordering. Transacció distribuïda. Protocols de commit distribuït: one-phase i two-phase. Mecanismes de control de concurrència en un sistema distribuït: two-phase locking (incloent detecció i tractament de deadlock distribuït), optimistic concurrency control, timestamp ordering. Replicació i consistència en un sistema distribuït. Models de consistència forta centrats en les dades: estricta, linearizability, seqüencial. Models de consistència relaxada centrats en les dades: ús de variables de sincronització. Models de consistència centrats en el client: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads. Implementacions de models de consistència: protocols basats en primari (remote-write, local-write) i protocols d'escriptura replicada (replicació activa, protocols basats en quòrum)

Activitats

Activitat Acte avaluatiu


Conceptes fonamentals de concurrència, paral.lelisme i distribució

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del tema per la seva aplicació posterior
Objectius: 1 8 11
Continguts:
Teoria
4h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
12h

Primer mòdul escollit: Concurrència o Paral·lelisme o Distribució

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del temes associats al mòdul corresponent per la seva aplicació posterior en les sessions pràctiques.

Teoria
10h
Problemes
0h
Laboratori
10h
Aprenentatge dirigit
0h
Aprenentatge autònom
30h

Segon mòdul escollit: Concurrència o Paral·lelisme o Distribució

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del temes associats al mòdul corresponent per la seva aplicació posterior en les sessions pràctiques.

Teoria
10h
Problemes
0h
Laboratori
10h
Aprenentatge dirigit
0h
Aprenentatge autònom
30h

Mòdul I: Concurrencia

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del temes associats al Mòdul I (concurrència) per la seva aplicació posterior en les sessions pràctiques.
Objectius: 8 9 10
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Mòdul II: Paral.lelisme

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del temes associats al Mòdul II (paral.lelisme) per la seva aplicació posterior en les sessions pràctiques.
Objectius: 11 12 13
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h

Mòdul III: Distribució

Preparació de la classe amb l'ajuda del material de suport. Comprensió i assimilació dels continguts del temes associats al Mòdul III (distribució) per la seva aplicació posterior en les sessions pràctiques.
Objectius: 1 2 3 4 5 6 7
Continguts:
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
0h


Examen final

Assimilació dels conceptes dels curs i realització de l'examen
Objectius: 1 2 3 4 5 6 7 8 9 10 11 12 13
Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
16h

Metodologia docent

Durant el curs es realitzaran dos tipus d'activitats:

a) Activitats centrades en l'adquisició de coneixements teòrics.
b) Activitats centrades en l'adquisió de coneixements mitjançant experimentació amb la implementació i avaluació empírica al laboratori dels mecanismes explicats a nivell teòric.

Les activitats teòriques inclouen classes expositives participatives on s'expliquen els continguts bàsics del curs. Les activitats pràctiques inclouen seminaris de laboratori on els alumnes implementen els mecanismes descrits a les classes expositives. Els seminaris requereixen d'una preparació prèvia mitjançant la lectura de l'enunciat i la documentació de suport, i una elaboració posterior de les conclusions obtingudes en un informe.

Mètode d'avaluació

La nota final es calcula a partir de la nota dels dos mòduls cursats per l'estudiant: NF=0.5*M1+ 0.5*M2

Per cada mòdul, hi haurà un examen (EF) i nota de laboratori (L). L'exàmen serà de problemes sobre la teoria explicada. La nota de laboratori reflectira el treball realitzat en les pràctiques de laboratori. La nota final del mòdul serà Mi=0.6*EF+ 0.4*L.

Bibliografia

Bàsica:

Complementaria:

Capacitats prèvies

Concurrència: coneixements de Java a nivell de classes i objectes.
Paral·lelisme: coneixements bàsics d'arquitectures paral·leles, incloent multiprocessadors amb memòria compartida i distribuïda.
Distribució: coneixements de l'estructura interna i el funcionament d'un sistema operatiu i d'una xarxa de computadors.