Lezione 8 marzo 2010
Richiami sul modello di calcolo PRAM: astrazione del modello, tipi di PRAM rispetto all'accesso in memoria per lettura e scrittura.
Requisiti delle reti di interconnessione per la realizzazione di multiprocessori. Nodi e funzioni di un nodo. Rete crossbar, rete completamente connessa, rete di Kautz. Lezione 11 marzo 2010
Definizioni sulle caratteristiche topologiche e sulle proprietà funzionali delle reti di interconnessione. Definizione di reti multistadio con log N stadi. Lezione 18 marzo 2010
Caratterizzazione di reti multistadio con log N stadi, N-MIN. Proprietà Banyan delle N-MIN. Equivalenza topologica tra N-MIN secondo Bermond-Forneau-Jean Marie. Definizione del Layered Cross Product, LCP, di Even & Litman, Articolo LCP. Equivalenza topologica tra N-MIN usando LCP. Lezione 23 marzo 2010
Decomposizione di grafi rispetto al LCP. Decomposizione di N-MIN come prodotto di alberi binari. Algoritmo di decomposizione di una N-MIN come prodotto di alberi binari. Articolo equivalenza e decomposizione Lezione 25 marzo 2010
Decomposizione di grafi in fattori primi. Definizione di grafo X partendo da fattori primi. Decomposizione di N-MIN come prodotto di X_i. Instradamento su N-MIN secondo la rappresentazione binaria della destinazione (self-routing). Bloccanza delle N-MIN: conflitti sui nodi. Reti con (2logN - 1) stadi. Rete di Benes: caratteristiche, algoritmo Loop. Lezione 8 aprile 2010
Costruzione ricorsiva della rete di Benes. versione ricorsiva dell'algoritmo Loop e riarrangiabilità. Decomposizione della rete di Benes secondo LCP. Algoritmo di routing per la rete di Benes usando la decomposizione in fattori. Correttezza e complessità dell'algoritmo. Articolo algortimo di routing Lezione 12 aprile 2010
Algoritmo di equivalenza di reti con 2logN -1 stadi: decomposizione in fattori nabla-delta e delta-nabla e decomposizione del fattore delta-nabla in fattori primi. Classificazione delle reti con 2logN -1 stadi secondo i fattori Xij. Articolo equivalenza e decomposizione - lez. 23 marzo Lezione 15 aprile 2010
Classificazione delle reti con 2logN -1 stadi secondo le due decomposizioni (tramite nabla-delta e delta-nabla e tramite i fattori Xij).
Riarrangiabilità della seconda classe di reti per N=8: algoritmo di instradamento rispetto alla decomposizione nabla-delta e delta-nabla. Problemi aperti sulla riarrangiabiltà. Riarrangiabilità seconda classe di reti con N=8 Lezione 23 aprile 2010
Reti di Clos: definizione, condizione di non bloccanza e di riarrangiabilità. Reti ricircolanti. Algoritmo di ordinamento di Batcher (Bitonic merge sorting): descrizione e complessità temporale. Lezione 29 aprile 2010
Dall'algoritmo alla rete di Batcher. Considerazioni e confronto sulle reti di Benes e di Batcher. Efficienza e probabilità di bloccaggio di una rete bloccante. Efficienza delle reti banyan. Schemi basati sulle reti banyan: concatenazione, d-dilatazione, r-replicazione. Lezione 3 maggio 2010
Descrizione di una struttura di interconnessione quasi-nonbloccante basata su reti butterfly. Rete quasi-nonbloccante Lezione 6 maggio 2010
Il modello analitico di Szymanski & Hamacher per il calcolo della probabilità di bloccaggio in una rete multistadio. Lezione 10 maggio 2010
Descrizione di una struttura di interconnessione asintoticamente non bloccante. Rete asintoticamente nonbloccante Lezione 17 maggio 2010
Definizione di efficienza temporale. Descrizione di una struttura di interconnessione virtualmente non bloccante. Rete virtualmente non bloccante Lezione 24 maggio 2010
Procedura di ritrasmissione per reti asintoticamente non bloccanti rispetto alle permutazioni. Realizzazione di un randomizzatore tramite utilizzazione una stringa binaria.
Lezione 27 maggio 2010
Introduzione all'architettura di una GPU. Guardare le slide (usate a lezione) e i primi due capitoli linkati alle prime due lezioni del corso all'indirizzo http://courses.ece.illinois.edu/ece498/al/Syllabus.html
-- AnnalisaMassini - 11 Mar 2010