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

Professorat

Responsable

• Jordi Guitart Fernandez ( jguitart@ac.upc.edu )

Altres

• Jorge Castro Rabal ( castro@cs.upc.edu )
• Josep Ramon Herrero Zaragoza ( josepr@ac.upc.edu )

Hores setmanals

Competències

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

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsic

• Distributed systems: principles and paradigms - Tanenbaum, A.S.; Steen, M. van, Pearson Prentice Hall, 2007. ISBN: 0136135536
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003206969706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Distributed systems: concepts and design - Coulouris, G.F.; Dollimore, J.; Kindberg, T.; Blair, G, Addison-Wesley/Pearson Education, 2012. ISBN: 0273760599
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000675069706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Concurrency: state models & Java programs - Magee, J.; Kramer, J, John Wiley & Sons, 2006. ISBN: 0470093552
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003172149706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Programming Erlang: software for a concurrent world - Armstrong, J, Pragmatic Bookshelf, 2013. ISBN: 9781937785536
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004002229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Java concurrency in practice - Goetz, B.; Peierls, T.; Bloch, J.; Bowbeer, J.; Holmes, D.; Lea, D, Addison-Wesley, 2006. ISBN: 0321349601
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003104049706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to parallel computing - Grama, A.; Karypis, G.; Kumar, V.; Gupta, A, Pearson Education, 2003. ISBN: 0201648652
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003524559706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementari

• Erlang programming - Cesarini, F.; Thompson, S, O'Reilly, 2009. ISBN: 9780596518189
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003712929706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• The art of multiprocessor programming - Herlihy, M. [i 3 més], Morgan Kaufmann Publishers is an imprint of Elsevier, 2021. ISBN: 9780124159501
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991005136978806711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Capacitats prèvies