| | | |  corso | | | |
Algoritmi paralleli e Distribuiti
| Codice: | AA276 | Crediti: | 6 | Semestre: | 2 | Sigla: | ADI | |
| |
| Settore disciplinare: | INF/01 - Informatica |
Docente
Linda Pagli
Tel. 0502212735Prerequisiti
Algoritmi e Strutture Dati, Architettura
Obiettivi di apprendimento
Si introducono i modelli di computazione parallela (PRAM, reti a
grado limitato e memoria secondaria
multi-disco) e distribuita per studiare la progettazione e la
valutazione di algoritmi in tali modelli.
Il confronto di questi modelli tra loro e con altri possibili
dovrebbe fornire allo studente la capacitą di
selezionare il modello opportuno nello sviluppo di applicazioni che
impiegano contemporaneamente
pił processori .
Descrizione
Introduzione all'analisi e alla complessità degli algoritmi paralleli e distribuiti. Definizione e confronto dei più diffusi modelli di calcolo con particolare riferimento alle reti a grado limitato, al modello PRAM, al modello distribuito e al modello di memoria secondaria miltidisco. Principali tecniche algoritmiche e studio di problemi di base. Limiti inferiori e problemi difficilmenti parallelizzabili.
English Description
Introduction to analysis and design of parallel and distributed
algorithms. Definition and
comparison among the most important models of parallel computation as
bounded degree network,
PRAM model, distributed model and the multi-disk secondary starage
model. Basic algorithmic
techniques and important problems. Lower bounds and P-complete problems.
Programma
- Algoritmi Paralleli (20 ore)
Modello VLSI: Limiti fisici di calcolo sul silicio.
Layout di circuiti. moltiplicazione sistolica di matrici;
Algoritmi per reti di interconnessione a grado limitato:Array lineari, Alberi
Mesh e mesh-of-trees, Ipercub e butterfly.
Il modello PRAM e le sue varianti.
Tecniche di base per la costruzione di algoritmi PRAM efficienti:
Prefix Sum, List Ranking,
Tree Contraction. Partitioning, Pipelining, Divide and Conquer
Modello di memoria secondaria multidisco: Mergesort, Greedsort.
- Algoritmi Distribuiti (20 ore)
Definizione di sistema distribuito
Algoritmo di calcolo del leader. Dimostrazione di calcolo di
complessita' in messaggi e tempo.
Definizione di knowledge. Algoritmi di elezione del leader su anello.
Algoritmi di spanning tree. Algoritmi di elezione del leader su grafo generico.
Interval routing.
Sistema distribuito sincrono e tecniche di waiting.
Algortmi sincroni.
Protocolli randomizzati.
Bibliografia
- Joseph Jaja': "An Introduction to Parallel algorithms" Addison Wesley
publishing Company 1992.
- Nancy Lynch: "Distributed Algorithms" Morgan Kaufmann Publisher 1996.
Alan Bertossi: "Algoritmi e Strutture Dati" Utet-Libreria 2000.
- F. Thompson Leigthon, Introduction to Parallel algorithms and
architectures: array, trees, hypercubes,
Morgan-Kaufman Pub., 1992.
Modalità di esame
Scritto e orale
