Strumenti Utente

Strumenti Sito


ccp:lezioni0708

Questa è una vecchia versione del documento!


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.
Tutorial di ASSIST
aggiungere riferimenti
  • 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 di calcolo Bulk - Synchronous
    BSP e modelli derivati: BSP*, D-BSP. Cenni ai modelli CGM, LogP.
  • 24/04
  • 28/04
  • 5/05
  • 8/05
  • 12/05
  • 15/05
  • 19/05
  • 22/05
  • 26/05
  • 29/05
ccp/lezioni0708.1209451840.txt.gz · Ultima modifica: 29/04/2008 alle 06:50 (14 anni fa) da Massimo Coppola