Strumenti Utente

Strumenti Sito


ccp:lezioni0708

CCP 07-08: elenco delle lezioni

La struttura del corso e' abbastanza naturalmente suddivisa in piu' moduli, ma i rimandi ed i collegamenti tra di essi sono essenziali.

MPI : Message Passing Interface

  • 18/02 Panorama del corso.
    Panoramica del corso, obiettivi, tecnologie principali (MPI, ASSIST).
    Forme di parallelismo e implementazione nei diversi modelli/linguaggi di programmazione parallela. Esempi di problemi che verranno esaminati del corso: algoritmi di Data Mining, simulazione computazionale, ricerca combinatoria ed ottimizzazione, algoritmi in memoria esterna. Modalità di superamento dell'esame. Programmazione parallela strutturata e non strutturata, cenni a vari modelli di programmazione. MPI: modello a scambio di messagi, motivazioni dello sviluppo, descrizione ad alto livello dello standard e del modello di programmazione SPMD.
  • 21/02 MPI: Introduzione, concetti essenziali e comunicazione punto a punto.
    MPMD (multiple program multiple data) e SPMD in MPI. Master slave e data parallel come casi particolari di programmi SPMD. Utilizzo strutturato di MPI e realizzazione di librerie parallele. Concetto di comunicatore, esempi di primitive punto a punto di MPI: send e receive sincrona e asincrona, receive asimmetrica. Standard di riferimento: MPI 1.1 (cap.3) con integrazione MPI 2 (cap.3).
    Caratteristiche di ordinamento relativo, (non) fairness e uso delle risorse delle primitive MPI. Alcuni concetti base di MPI:
    • tipi di dato (tipi base, definiti dall'utente, tipi opachi e handle)
    • comunicatori (rank, inter/intra-comunicatori, gruppi)
    • primitive punto a punto (concetti: envelope, completamento locale e globale, primitive bloccanti e non bloccanti, modalità della send)
    • tipi base delle send (cenni): standard, sincrona, ready, buffered
  • 26/02 MPI: oggetti opachi, MPI Datatypes e loro costruttori
    Tipi di dato generali, concetto di datatype (sequenza di tipi base e displacement) e typemap associata. Supporto ad MPI multi-linguaggio e multi architettura: la definizione a run-time dei tipi di dato (validità locale) come meccanismo di integrazione tra il programma nel linguaggio ospite (compilato) e la libreria di comunicazione (collegata). Rappresentazione interna alla libreria MPI, e come tipi opachi; uso dei costruttori forniti da MPI: MPI_TYPE_COMMIT e MPI_TYPE_FREE. MPI_TYPE_ (contiguous, vector, hvector, indexed, hindexed, struct). Concetti di size ed extent. Modificatori di extent (_LB ed _UB). Matrici a blocchi, triangolari, diagonali, uso di datatype per realizzare stencil e riorganizzazione di dati associata alla comunicazione.
  • 28/02 MPI: comunicatori e gruppi
    Differenza tra comunicatori e gruppi, concetto di attributo di un gruppo; primitive di creazione dei gruppi (operazioni booleane, aggiunta), conversione tra gruppi e comunicatori, creazione di comunicatori. Primitive di split e merge degli intra-comunicatori. Inter-comunicatori: creazione, semantica relativa al gruppo locale delle primitive sui comunicatori (MPI_COMM_SIZE, MPI_COMM_RANK) e primitive dedicate. Operazioni collettive: significato, semantica non sincronizzante, ordinamento dei messaggi. Barrier, broadcast, gather, scatter, gatherv, scatterv, alltoall.
  • 3/03 MPI operazioni collettive e operatori MPI
    Primitive collettive Reduce, ReduceAll. Operatori MPI predefiniti, operatori utente, loro definizione ed applicazione, polimorfismo e meccanismi per la gestione dei datatype. Operazione di scan (parallel prefix). Varianti della semantica delle comunicazione: approfondimento su send sincrona e buffered. Ready-send ed esempio di utilizzo: emettitore di un farm. Operazioni di comunicazione incomplete (receive e varianti della send); meccanismo delle MPI_request. Controllo delle comunicazioni in sospeso e primitive WAIT e TEST. Varianti multiple WAIT_ANY, TEST_ANY, WAIT_ALL, TEST_ALL. Primitive CANCEL e MPI_FREE_REQUEST. Introduzione al controllo del nondeterminismo ed alle primitive MPI_WAIT_SOME ed MPI_TEST_SOME.
  • 6/03 MPI - primitive incomplete e persistenti e controllo del nondeterminismo
    MPI_TEST_SOME, MPI_WAIT_ALL. Operazioni persistenti, semantica, MPI_START e MPI_STARTALL. MPI_request attive e non attive relazione con le varianti di MPI_WAIT ed MPI_TEST, e con la MPI_CANCEL. Implementazione di meccanismi di comunicazione a canali tramite MPI, differenze nella semantica. Esempi con il linguaggio LC: implementazione del canale, delle primitive sincrone ed asincrone (via buffered send e processo buffer), del comando alternativo (variante con send incomplete e permanenti, MPI_TEST_SOME).

Programmazione a skeleton paralleli, ASSIST

  • 10/03 Applicazioni; skeleton e programmazione parallela
    Costrutto farm in MPI, varianti di implementazione, uso di comunicatori e struttura del programma SPMD. Uso di comunicatori per strutturare programmi più complessi (annidamento di forme di parallelismo) mantenendo la portabilità del codice. Un benchmark “classico”, il calcolo dell'insieme di Mandelbrot: proprietà matematiche, parallelismo e bilanciamento del carico. Introduzione ai Parallel Skeletons e formalismi di programmazione parallela strutturata.
  • 13/03 Parallel Skeletons
    Breve storia della programmazione parallela strutturata. Parallel skeletons di Cole, applicabilità a vari modelli di programmazione (funzionale, imperativo) di esecuzione (completamente compilato, a libreria di template, interpretato, a macchina virtuale) e di supporto del parallelismo (a template, macro-dataflow, via librerie di supporto standard come MPI).
    Brevi cenni a vari gruppi di ricerca e sistemi: SCL/Fortran S, Skipper, BMF, Skil, Muesli. La ricerca a Pisa: P3L, SkiE, ASSIST; Lithium e Muskel.
  • 17/03 Sistemi a Skeleton di prima e seconda generazione: Muskel, ASSIST
    Processo di compilazione di meccanismi a skeleton / template in reti di processi, a la P3L / SkIE. Ottimizzazioni a livello degli skeleton: composizione di skeleton, valutazione delle composizioni e regole di riscrittura; forma normale di composizioni farm/pipeline. Ottimizzazione statica e dinamica. Cenni alle ottimizzazioni a livello di template. Cenni all'aspect programming ed aspetti individuabili: parallelismo, gestione di dinamicità, sicurezza, fault tolerance. Integrazione del codice utente e del codice di supporto, tramite linker o tramite bytecode e macchine virtuali.
    Parallel skeleton di seconda generazione. Muskel, approccio macro-dataflow, strategia di compilazione ed esecuzione, estendibilità dell'insieme di skeleton. Accenni agli esperimenti sulla dinamicità e la fault tolerance, possibilità di implementazione di toke repository distribuiti.
    ASSIST: approccio a moduli paralleli e canali, con parallel skeleton “generico” configurabile. Grafo di moduli di programma non ristretto: cicli e archi multipli. Panoramica della semantica base del parmod : sezioni di ingresso e uscita con guardie, distribuzioni e collezioni, set di processori virtuali.
  • 20/03 ASSIST : semantica essenziale
    Composizione di costrutti paralleli e livelli di annidamento, collegamento a formalismi a componenti. Approccio a linguaggio di coordinamento: meccanismo di compilazione a due fasi, integrazione di linguaggi sequenziali diversi in compilazione. Blocchi fondamentali: moduli sequenziali e proc. Parmod, esempi: input e output section; topologia (array, none, one) e concetto di processore virtuale (VP); distribuzioni (broadcast, on demand, scatter) e collezioni (from any, from all); parallelismo task-parallel (topologia none) e data-parallel (topologia array), definizioni dei VP associate.
  • 27/03 non ci sarà lezione
  • 7/04 ASSIST: Processori Virtuali e Deployment
  • 10/04 Modelli astratti di calcolo parallelo ed in memoria secondaria
    La PRAM (Parallel Random Access Machine). Assunzioni (parallelismo e memoria illimitati, sincronia, scalabilità); scopo del modello e varianti standard (EREW, CREW, CRCW e regole di risoluzione dei conflitti). Modelli di calcolo per memoria secondaria. Il PDM (Parallel Disk Model). Struttura essenziale, parametri M,B,N,Z e derivati m=(M/B), n=(N/B), z=(Z/B). Misura di complessità orientata ai blocchi, algoritmi base e loro complessità. Effetto pratico dei termini logaritmici a base elevata (M/B) nella complessità algoritmica.
  • 17/04 lezione annullata
  • 21/04 Modelli astratti di calcolo parallelo e in memoria secondaria
    PRAM, esempi di algoritmi, complessità in processori e tempo, work ed efficienza. Aumento di efficienza con riduzione del numero di processori (esempio di riduzione logaritmica). Modello PDM, complessità di operazioni di permutazione e sort, relazione con il modello BSP.
  • 24/04 Modelli di calcolo Bulk - Synchronous
    Modelli coarse parallel (o bulk-synchronous). Modello BSP, schema e parametri, valutazione del costo algoritmico. Bridging models: Cenni a CGM e LogP. Realisticità del modello BSP, cenni alle estensioni: BSP*, D-BSP. Implementabilità, cenni a BSPlib. Cenni all'uso di modelli BSP-like per la valutazione del costo di skeleton paralleli [Tesi di dottorato di Andrea Zavanella]. Cenni alla possibilità di simulazione efficiente in memoria esterna di algoritmi BSP-* (vedi riferimenti su M.Coppola, M.Schmollinger “Hierarchical Models and Software Tools for Parallel Programming” LNCS 2625, cap 15 ).
  • 29/04 Memorie Condivise Distribuite
    Concetto di DSM (distributed shared memory). [ capitolo 9 del libro, escluso 9.6.3 ]
    Vantaggi e svantaggi (portabilità, prestazioni, scalabilità). Modelli di consistenza (weak, strict / sequential), unità di coerenza (pagine, variabili, oggetti), livello dei meccanismi di implementazione (hardware, sistema operativo, libreria, linguaggio di programmazione). Problema del false sharing. Eager and lazy release consistency (associata alle operazioni), entry consistency (data dalla struttura dei dati), scope consistency (data dalla struttura del programma). [Tesi Dottorato Marco Aldinucci , Capitolo 3]
    Implementazione su meccanismi (hw/sw) di tipo message passing. Supporto ad hardware, supporto tramite librerie, supporto tramite thread/ processi serventi. Uso del supporto DSM in Assist: libreria smReference per l'interfacciamento ad una DVSM. Astrazione esposta, modello di consistenza esplicita, suo uso da ASSIST. Primitive, confronto tra due implementazioni: la DSM DVSA, il supporto DSM AdHoc. Impatto sulla gestione di strutture dati dinamiche, sulla dimensione dello spazio condiviso, sulla riconfigurabilità dinamica dell'insieme di nodi che supportano l'astrazione DSM. Strutture dati in memoria condivisa ed algoritmi out-of core; esempio: implementazione di Shared Tree in SkIE / ASSIST.
  • 5/05 lezione annullata
  • 8/05 Introduzione al Data Mining
  • 12/05 Clustering Parallelo : K-means
Dhillon, Modha Technical Report su K-means parallelo A Data-Clustering Algorithm On Distributed Memory Multiprocessors. I.S. Dhillon, D.S.Modha, LNAI 1759, pag 245. Nota: la versione disponibile online via LNCS riporta un algoritmo errato, il technical report è corretto.
Ottimizzazioni sequenziali e parallele per K-means Large-Scale Parallel Data Clustering. Dan Judd, Philip K. Mckinley, Anil K. Jain. Ieee Transaction On Pattern Analysis And Machine Intelligence, Vo. 20, No. 8 August 1998.
  • 15/05 Context-aware High Performance Computing
Lucidi sul progetto InSyEme Prima versione delle slide in pdf; N.B. le animazioni non si vedono correttamente.
  • 19/05 Multi-core CPUs
Intel IXP 2400 Documentazione dal sito Intel
IBM Cell
Articolo sul Cell Kistler, Perrone, Petrini, IEEE Micro May/June 2006 (Vol. 26, No. 3) “Cell Multiprocessor Communication Network: Built for Speed”
  • 22/05 GPU programming
GPU Programming GEMS 2, fotocopie distribuite a lezione
ACM Queue March/April 2008 Numero di ACM Queue su parallel programming e GPU
  • 26/05 Data Mining : Parallel Tree Induction
  • 29/05
ccp/lezioni0708.txt · Ultima modifica: 29/05/2008 alle 09:03 (10 anni fa) da Massimo Coppola