2° modulo (I semestre)
A. A. 1998-99
Prof. Alan Bertossi
Programma:
INTRODUZIONE AI SISTEMI PARALLELI
Sistemi e algoritmi paralleli. Memoria condivisa e distribuita. Sistemi
sincroni e asincroni. Multiprocessori e multicalcolatori. Classificazione
di Flynn (SIMD, MIMD) e di Schwartz (paracomputer, ultracomputer).
MODELLI SINCRONI
Modello PRAM. Reti sincrone con struttura d'internonnessiobne a grado
limitato. Mesh, albero, ipercubo, shuffle. Rete di Batcher. Algoritmi
paralleli per ordinamento, moltiplicazione di matrici, cammini minimi,
e
trasformate veloci di Fourier. Sistemi VLSI (very large scale integration).
Il modello a griglia e problemi di layout. Algoritmi per sistemi VLSI.
MODELLI ASINCRONI
Sistemi MIMD e algoritmi concorrenti. Sincronizzazione, scheduling,
stallo.
Algoritmi concorrenti per ordinamento e cammini minimi. Branch-and-bound
su
MIMD. Reti di calcolatori e algoritmi distribuiti. Anelli, stelle,
reti
complete. Algoritmi distribuiti per mutua esclusione ed elezione del
leader.