Algoritmi e Strutture Dati: Algoritmi Paralleli e Distribuiti

Linda Pagli      Tel. 0502212735

Algoritmi e Strutture Dati, Architettura

Si introducono i modelli di computazione parallela (PRAM) e distribuita per apprendere 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 nell= o sviluppo di applicazioni che impiegano contemporaneamente più processori.

Introduzione all'analisi e alla complessit=E0 degli algoritmi paralleli e distribuiti. Definizione e confronto tra i pi=F9 diffusi modelli di calcolo con particolare riferimento al modello PRAM e distribuito. Tecniche algoritmiche principali e studio di problemi importanti. Limiti inferiori e problemi difficilmente parallelizzabili.

Introduction to analysis and design of parallel and distributed algorithms. Definition and comparison among the most important models of parallel computation as PRAM model and distributed model. Basic algorithmic techniques and important problems. Lower bounds and P-complete problems.

1. Algoritmi Paralleli (25 ore)

Il modello PRAM e le sue varianti Tecniche di base per la costruzione di algoritmi PRAM efficienti: Prefix Sum, List Ranking,Tree Contraction, Symmetry Breaking, Pipelining.
Sorting, Merging e Selection.
Tecniche per la dimostrazione di limiti inferiori: Il problema dell'OR. Algortimi NC e problemi P-completi.
Cenni al modello BSP.

2. Algoritmi Distribuiti (15 ore)

Il modello distribuito punto-punto.
Misure di complessità: tempo e comunicazione.
Definizione di algoritmo distribuito.
Algoritmi base per reti con diverse topologie come anelli, alberi e grafi.
Spanning tree e Elezione del leader.

Joseph Jajà: "An Introduction to Parallel algorithms" Addison Wesley publishing Company 1992. Attiya H., Welch J.: "Distributed computing : foundamentals, simulations and advanced topics" 1998.