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;AC
Aquest curs té com a objectiu proporcionar les bases sobre la computació com una conjunt de tasques que poden estar executant al mateix temps i que poden interactuar entre ells. Aquestes tasques poden ser executats 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 (comú), paral.lelisme (opcional) i distribució (opcional). L'estudiant ha de seleccionar un dels dos mòduls opcionals (paral.lelisme o distribució). Les lliçons es complementen amb pràctiques de programació per il·lustrar els problemes i avaluar les solucions.

Professors

Responsable

  • Jordi Guitart Fernandez ( )

Altres

  • Joaquin Gabarró Vallés ( )
  • Jorge Castro Rabal ( )
  • Josep Ramon Herrero Zaragoza ( )
  • Marc Gonzàlez Tallada ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0.15
Aprenentatge autònom
5.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ó.
    Related competences: CEE2.1, CG5,
    Subcompetences:
    • Entendre la definició de sistema distribuït
    • Conèixer els diferents tipus de comunicació en un sistema distribuït: directa vs. indirecta (desacoblament espacial i temporal), persistent vs. transitòria, síncrona vs. asíncrona, discreta vs. contínua
    • 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
    • Conèixer les arquitectures de sistema bàsiques en els sistemes distribuïts: centralitzades (client-servidor), descentralitzades (peer-to-peer), híbrides
    • Conèixer els paradigmes de comunicació bàsics en els sistemes distribuïts: invocació remota de procediment, pas de missatges, cues de missatges, comunicació de grups, publicació/subscripció, espais de dades compartits, memòria compartida, codi mòbil, orientat a stream
    • Posar exemples de sistemes distribuïts
  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.
    Related competences: 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 algorismes per sincronitzar rellotges físics en un sistema distribuït: Cristian (NTP), Berkeley
    • Explicar i implementar els mecanismes de rellotges lògics per atacar aquesta problemàtica: relació happened-before, rellotges lògics de Lamport (escalars, vectorials)
  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.
    Related competences: 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 garantir exclusió mútua, elecció de líder, comunicació en grup multicast, i consens.
    Related competences: CEE2.3, CEE2.1, CTR3,
    Subcompetences:
    • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per l'elecció de líder: Bully, Ring
    • 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, problema dels generals Byzantins, consens usant detectors de fallades, Paxos
    • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per garantir exclusió mútua: algorismes basats en permís (centralitzat, Lin, Maekawa, Ricart & Agrawala), algorismes basats en token (token ring)
    • 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
  5. Comprendre la problemàtica de l'execució concurrent de transaccions i descriure, comparar i implementar diferents mecanismes de control de concurrència.
    Related competences: 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.
    Related competences: 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
    • Descriure, comparar i implementar diferents protocols de commit distribuït: one-phase i two-phase
    • Ampliar el concepte de transacció a un sistema distribuït
  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ó.
    Related competences: CEE2.3, CEE2.1,
    Subcompetences:
    • 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 forta centrats en les dades: estricta, seqüencial, causal, FIFO
    • Descriure els models de consistència relaxada centrats en les dades: ús de variables de sincronització
    • Descriure els models de consistència centrats en el client: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads
    • 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)
  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
    Related competences: CG1, CEE4.2,
    Subcompetences:
    • 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
    • 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.
    • 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.
    Related competences: 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
    Related competences: 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
    Related competences: CG1, CEE4.2,
    Subcompetences:
    • Entendre els conceptes de descomposició en tasques i l'estimació del seu paral.lelisme potencial
    • Entendre el rendiment d'una aplicació paral.lela i els factor que intervenen en la seva degradació
    • 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ó
    Related competences: CEE4.2, CTR3, CTR6, CG5,
    Subcompetences:
    • Us de la descomposició en tasques i dades
    • 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
  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
    Related competences: 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, 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. Arquitectures de sistema bàsiques en els sistemes distribuïts: centralitzades (client-servidor), descentralitzades (peer-to-peer), híbrides. Tipus de comunicació en un sistema distribuït: directa vs. indirecta (desacoblament espacial i temporal), persistent vs. transitòria, síncrona vs. asíncrona, discreta vs. contínua. Paradigmes de comunicació bàsics en els sistemes distribuïts: invocació remota de procediment, pas de missatges, cues de missatges, comunicació de grups, publicació/subscripció, espais de dades compartits, memòria compartida, codi mòbil, orientat a stream.
  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 garantir exclusió mútua: algorismes basats en permís (centralitzat, Lin, Maekawa, Ricart & Agrawala), algorismes basats en token (token ring). 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, problema dels generals Byzantins, consens usant detectors de fallades, 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, two-phase, i three-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, seqüencial, causal, FIFO. 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
6h
Problemes
0h
Laboratori
6h
Aprenentatge dirigit
0h
Aprenentatge autònom
18h

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

Mòduls alternatius: 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 II (paral.lelisme) o III (distribució) 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 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
3h
Aprenentatge autònom
12h

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ó

Hi haurà examen final (EF) i nota de laboratori (L). L'exàmen final serà de problemes sobre la teoria explicada. La nota de laboratori reflectira el treball realitzat en les pràctiques de laboratori. La nota final serà NF=0.6*EF+ 0.4*L.

Bibliografia

Bàsica:

  • Distributed Systems: Principles and Paradigms, 2nd Edition - Tanenbaum, A.S. and Van Steen, M., Pearson Prentice Hall, 2007. ISBN: 9780132392273
    http://cataleg.upc.edu/record=b1303976~S1*cat
  • Distributed Systems: Concepts and Design, 5th edition - Coulouris, G.F. and Dollimore, J. and Kindberg, T. and Blair, G., Addison-Wesley, 2011. ISBN: 9780132143011
    http://www.cdk5.net/wp/
  • Concurrency : State Models & Java Programming (Second Edition) - Magee, J. and Kramer, J., John Wiley & Sons, 2006.
  • Programming Erlang: software for a concurrent world (2nd ed) - Armstrong, Joe, Pragmatic Bookshelf, cop. 2013. ISBN: 9781937785536
    http://cataleg.upc.edu/record=b1431659~S1*cat
  • Java Concurrency In Practice - Goetz, B. and Peierls, T. and Bloch, J. and Bowbeer, J. and Holmes, D. and Lea, D., Addison-Wesley-Professional, 2006.
  • Introduction to Parallel Computing - Grama, A. and Karypis, G. and Kumar, V. and Gupta, A., Pearson Education, 2003. ISBN: 0201648652
    http://cataleg.upc.edu/record=b1340978~S1*cat

Complementaria:

  • Erlang Programming: A Concurrent Approach to Software Development - CESARINI, Francesco; THOMPSON, Simon, O'Reilly , 2009. ISBN: 9780596518189
    http://cataleg.upc.edu/record=b1366603~S1*cat
  • The Art of Multiprocessor Programming - Herlihy, M. and Shavit, N., O'Reilly , 2006.

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.