Algoritmi paralleli e distribuiti

Algoritmi paralleli e distribuiti, motivazioni. Architetture parallele e distribuite vs. architettura von Neumann. Risorse computazionali nei due contesti.
Algoritmi e architetture parallele:
- Problematiche nel disegno di algoritmi paralleli: sintesi, universalità, valutazione
- Architetture parallele a memoria condivisa e distribuita; la comunicazione nei due contesti
- Architetture a memoria condivisa, Il modello PRAM (Parallel RAM), struttura
- PRAM come architettura SIMD vs. architetture MIMD
- Modelli di PRAM: EREW, CREW, CRCW (common, priority, ... )
- Risorse di calcolo: complessità in numero di processori e tempo
- Confronto con algoritmi sequenziali: speed-up ed efficienza
- Soluzione parallela efficiente su PRAM di alcuni problemi fondamentali
- Calcolo di operazioni binarie associative, il problema SOMMATORIA, struttura ed analisi di un algoritmo parallelo
- Algoritmi paralleli efficienti per: algebra lineare, teoria dei grafi, ottimizzazione,...
- Calcolo di operazioni binarie associative prefisse, il problema SOMME PREFISSE
- Struttura ed analisi dell'algoritmo di Kogge-Stone (pointer doubling)
- Valutazione parallela efficiente di polinomi. Algoritmi di ricerca paralleli
- Il problema dell'ORDINAMENTO (ranking), soluzioni sequenziali efficienti
- Algoritmi di ordinamento paralleli efficienti. L'ordinamento bitonico di Batcher, struttura e analisi dell'algoritmo
- Tecnica del circuito euleriano nel progetto di algoritmi paralleli
- Architetture parallele a memoria distribuita, rete di interconnessione e parametri di valutazione: grado, diametro
e ampiezza di bisezione
- Reti di ordinamento e il principio 0-1 (Knuth)
- Array lineari di processori, struttura, funzionalità e parametri di rete
- Soluzione parallela dei problemi di ORDINAMENTO, calcolo del massimo e SHUFFLE
- Gli algoritmi di ordinamento ODD-EVEN e MERGE-SPLIT, struttura ed analisi
- Mesh di processori, tipologie, struttura, funzionalità e parametri di rete
- Calcolo del massimo su mesh
- L'algoritmo di ordinamento LS3, sruttura ed analisi
Algoritmi e architetture distribuite:
- Modellazione di un'architettura distribuita
- Entita' e canali di comunicazione
- Risorse computazionali, tempo e complessità di messaggi
- Struttura ed analisi di soluzioni distribuite per i problemi fondamentali
- BROADCASTING, lower bound per soluzioni distribuite
- L'algoritmo di flooding
- WAKE-UP, l'algoritmo di wflooding
- ATTRAVERSAMENTO, l'algoritmo depth-first
- SPANNING TREE, l'algoritmo shout e depth-first
- ELECTION, risultati di impossibilità, elezione per minimo
- ROUTING, algoritmi di gossiping