Fonaments de la Programació Concurrent (FPC)
Professors Responsables: |
JOAQUIM GABARRÓ VALLÉS (gabarrolsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
|
Departament:
LSI
|
Tipus d'assignatura
Optativa per la EI
Requisits de l'assignatura
FP
- Pre-requisit per la EI
|
|
PC
- Pre-requisit per la EI
|
|
Objectius docents
Aprendre els fonaments dels algoritmes concurrents. Per això presentem els dos models teòrics principals: CSP i CCS. També presentem breument altres models: Xarxes de Petri, Monoides Parcialment Commutatius, Linda i Unity. Cap a la fi considerem el lligam que hi ha entre els algoritmes síncrons i els asíncrons. Concloem amb un aspecte pràctic veient breument dues (d'entre les principals) llibreries per a pas de missatges.
Programa
1. 1.- CSP: Communicating Sequential Processes.
- Operador de CSP. - Lleis de CSP. - Model de traces. - Model de divergències. - Exemples d'aplicació.
2. 2.- CCS: Calculus of Communicating Systems.
- Operador en CCS. - Semàntica de transicions. - Bisimulacions. - Exemples d'aplicació.
3. 3.- Altres models.
- Xarxes de Petri. - Monoides parcialment commutatius. - Linda. - Unity.
4. 4.- Connexió entre algoritmes síncrons i asíncrons.
- Problema del "load balancing". - La idea de "gossiping". - PRAMS versus algoritmes distribuïts. - Llibreries per a pas de missatges: PMI i PVm.
Avaluació
La nota és sobre 10 i dependrà de: - Un 25% donada a les classes de problemes. - Un 75% com a resultat d'una prova que es realitzarà al final del quadrimestre. Cas que els estudiants ho desitjin, a mitjans del quadrimestre, es farà una prova curta. En aquest cas el resultat servirà per ponderar la nota final.
Càrrega
El curs està separat en dues parts que es van intercalant en el temps. Classes de Teoria. Es preveu que es podran fer unes 13 classes de 2 hores setmanals cadascuna. Es presentarà els corpus teòric bàsic. Classes de Problemes. Es preveu que es podran fer unes 13 de 2 hores setmanals cadascuna. S'intentarà que siguin els mateixos estudiants els que resolguin els problemes encara que sigui parcialment o amb incorreccions. La feina del professor serà completar i corretgir les errades que puguin aparèixer.
Bibliografia
Bibliografia bàsica
- Foster, I Designing and Building Parallel Programs Addison-Wesley, 1995 - Hoare, C.A.R Communicating Sequential Processes Prentice Hall
International, C.A.R. Hoare Series tor, 1985 - Milner, R Communication and Concurrency Prentice Hall
International, C.A.R. Hoare Series tor, 1989
Bibliografia complementària
- Baeten, J.C.M.; Weijland Process Algebra Cambridge Tracts in
Theoretical Computer Science., - Carriero, N., Gelernter, D How to Write Parallel Programs MIT-Press, 1990 - Chandy, K.M.; Misra, J Parallel Program Design: A Foundation Addison-Wesley, 1988 - Henessy, M Algebraic Theory of Processes MIT-Press, 1988 - Olderog, E.R Nets, Terms and Formulas Cambridge Tracts in
Theoretical Computer Science 23, 1991 - Peterson, J.L Petri Net Theory and the Modeling of Systems Prentice
Hall, 1981 - Skillircon Foundations of Parallel Programming Cambridge
International Series on Parallel Computing 6, 1995 - Monien, B Mapping and Load Balancing on Distributed Memory Machines Paderborn Spring School, 1995
|