Strumenti Utente

Strumenti Sito


apd:lezioni0809

APD 08-09: 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

  • 26/02 Presentazione del corso.
    Panoramica del corso, obiettivi, metodologia, tecnologie principali. Prerequisiti. Modalità di superamento dell'esame: progetto.
    Approcci a basso livello (MPI) e ad alto livello (Assist, modelli a componenti), distributed e shared memory. Collegamenti con il corso di CCP 08/09.
    Implementazione del parallelismo come programming aspect nei diversi modelli/linguaggi di programmazione parallela. Programmazione parallela strutturata e non strutturata, uso di MPI in modo strutturato. MPI: modello a scambio di messagi, motivazioni dello sviluppo, descrizione ad alto livello dello standard e del modello di programmazione SPMD. Approcci skeleton based e component based, l'ambiente Assist. Estensioni shared memory.
    Possibili approfondimenti: (1) Sistemi operativi di griglia, calcolo distribuito, Cloud computing; (2) Architetture Multi-core e meccanismi di programmazione; (3) GPU general processing; (4) Esecuzione su macchine virtuali (Java, .NET, mono) e parallelismo.
    Alcune classi di problemi usati come esempi durante il corso: algoritmi di Data Mining, simulazione computazionale, ricerca combinatoria ed ottimizzazione, algoritmi in memoria esterna.
  • 27/02 MPI: Introduzione, concetti essenziali e comunicazione punto a punto.
    MPMD (multiple program multiple data) e SPMD in MPI. Modello di esecuzione library-based. 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. Parti dello standard da usare come 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:
    • 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 di dato (tipi base, definiti dall'utente, tipi opachi e handle) da completare
    • tipi base delle send (cenni): standard, sincrona, ready, buffered
  • Per la prossima lezione: individuare e/o installare su un computer a propria disposizione almeno una delle versioni di MPI citate a lezione (mpich, lam-mpi, OpenMPI).
  • 05/03 MPI: comunicazioni punto a punto, modalità e funzioni ausiliarie.
    Costanti Datatype e tipi di dato predefiniti, cenni ai datatype definiti dall'utente; mapping dei tipi di dato sui linguaggi, conversioni di rappresentazione in ambiente eterogeneo; oggetti opachi e handle.
    mpirun, caricamento ed inizializzazione: handshaking iniziale; MPI_Init, MPI_Finalize; funzioni accessorie elementari: MPI_Comm_rank. Send e receive standard bloccanti, significato e uso degli MPI_Status (MPI_Get_count, status.MPI_SOURCE, MPI_TAG, MPI_ERROR). Differenza espressiva in MPI tra send e receive; descrizione e significato dei modi della send (sincrona, buffered, ready); asimmetria nella receive (any source, any tag). Operazioni incomplete (MPI_Request, MPI_Wait, MPI_Test, MPI_Request_free).
Rif. MPI standard 2.1 sezioni 3 → 3.3, 3.4 (parte), 3.5
  • 06/03 MPI: controllo di operazioni incomplete, comunicatori, datatype utente
    Gestione delle operazioni incomplete, completamento multiplo e nondeterminismo. Datatype utente più semplici, creazione, commit, deallocazione.
    (MPI_Wait* e MPI_Test*, versioni *any, *all e *some, MPI_Request_get_status; MPI_Type_contiguous, MPI_Type_vector, MPI_Type_create_hvector, MPI_Type_indexed, MPI_Type_create_hindexed; MPI_Get_address, MPI_Type_size, MPI_Type_get_extent, MPI_Type_create_resized, MPI_Type_commit, MPI_Type_free)
Rif. MPI standard 2.1 sezioni 3.4 (parte), 3.7.3 , 3.7.4, 3.7.5, 3.7.6, 3.7.7; 4 → 4.1.2 (parte); 4.1.5 → 4.1.7, 4.1.9
  • Esercitazione: implementare una applicazione basata su pipeline e farm in MPI
  • 12/03 MPI: comunicatori e gruppi
    Creazione, modifica e distruzione di gruppi e comunicatori (completamento locale vs globale). Operazioni collettive in MPI: semantica, ordinamento totale, indipendenza dall'implementazione, esempi di implementazione e di stallo. Eccezione: MPI_Barrier.
    (MPI_Group_size, MPI_Group_rank, MPI_Group_translate_ranks, MPI_Group_compare, MPI_Comm_group, MPI_Group_union, MPI_Group_intersection, MPI_Group_difference, MPI_Group_incl, MPI_Group_excl, MPI_Group_free; MPI_Comm_size, MPI_Comm_rank, MPI_Comm_compare, MPI_Comm_dup)
Rif. MPI standard 2.1 sezioni 6 → 6.2, 6.3.1, 6.3.2 (parte), 6.3.3, 6.4.1, 6.4.2 (parte), 6.4.3, 5.1
  • 13/03 MPI: operazioni collettive
    Significato, semantica non sincronizzante, ordinamento dei messaggi. Collettive per intra-comunicatori. MPI_Barrier, MPI_Broadcast, MPI_Gather, MPI_Scatter, MPI_Gatherv, MPI_Scatterv, MPI_Allgather, MPI_Allgatherv, MPI_Alltoall, MPI_Alltoallv, MPI_Alltoallw
Rif. MPI standard 2.1 sezioni 5 → 5.2 (non 5.2.2), 5.3 - 5.8
  • 19/03 MPI: operazioni collettive
    Collettive con comunicazione e calcolo: reduce e parallel prefix. Operatori predefiniti; Minloc e Maxloc. Definizione di operatori utente. Primitive MPI: MPI_Reduce e MPI_Allreduce, MPI_Reduce_scatter, MPI_Scan
Rif. MPI standard 2.1 sezioni 5.9 - 5.12 (non 5.11.2)
  • 20/03 Esempi di applicazioni
    Sample sort parallelo. Algoritmo di Strassen. Calcolo dell'insieme di Mandelbrot (cenni); algoritmo K-means e sua parallelizzazione elementare.
Rif. Sample sort parallelo dal testo Introduction to Parallel Computing A. Grama, A. Gupta, G. Karypis, V. Kumar.
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.

Programmazione a skeleton paralleli, ASSIST

  • 17/04 Skeleton Paralleli e Programmazione Parallela Strutturata
    Richiami agli skeleton paralleli, caratteristiche dei linguaggi/ambienti di programmazione a skeleton. Discussione sulle fondamentali per l'espressività e l'implementazione (linguaggi funzionali/imperativi; approccio procedurale/oggetti/componenti; gradi di separazione degli aspetti parallelo e sequenziale del programma; supporto su macchine virtuali JVM, mono/.NET). Sistemi a skeleton di seconda generazione.
    Due alternative di implementazione: template e data-flow. Muskel, approccio macro-dataflow, strategia di compilazione ed esecuzione, estendibilità dell'insieme di skeleton, possibilità di implementazione di token repository distribuiti.
    ASSIST : obiettivi, approccio a linguaggio di coordinamento parallelo + linguaggi sequenziali ospiti; compilazione e meta-compilazione.
Rif. Bringing – M. Cole, Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming, Parallel Computing 30 (2004) 389–406
2ndGen – M. Danelutto, ”Second-generation” Skeleton Systems, in Parallel Computing: Current & Future Issues of High-EndComputing, Proceedings of the International Conference ParCo 2005
muSkel – M. Aldinucci, M. Danelutto and P. Dazzi, Muskel: an expandable skeleton environment (2007), in: Scalable Computing: Practice and Experience, 8:4(325-341)
Tutorial di ASSIST
Tutorial ASSIST Febbraio 2007
GEA, versione Novembre 2006
Tutorial ASSIST Febbraio 2008
  • 23/04 ASSIST : panoramica e semantica essenziale
    Evoluzione dell'approccio parallelo strutturato legata alle griglie ed all'adattività: da P3L, a SkIE, ad ASSIST. Semantica funzionale pura, skeleton rigidi. Processo di compilazione due fasi, uso di compilatori convenzionali (gcc) come back-end e/o librerie (MPI) per il supporto al parallelismo. ASSIST: approccio a moduli paralleli e canali, con parallel skeleton “generico” configurabile. Grafo di moduli di programma non ristretto: cicli e archi multipli. Concetto di parmod come skeleton “configurabile” (meta-skeleton). Meccanismo di compilazione a due fasi e integrazione di linguaggi sequenziali diversi in compilazione. Blocchi fondamentali: moduli sequenziali e proc. Implementazione delle interfacce tra linguaggi, uso del sistema di tipi CORBA in ASSIST.
Rif. Un articolo recente da Computing Now Joel Falcou Parallel Programming with Skeletons
  • 24/04, 28/04 (preliminare per le due lezioni)
    ASSIST: Panoramica della semantica base del parmod : sezioni di ingresso e uscita con guardie, distribuzioni e collezioni, set di processori virtuali. Composizione di costrutti paralleli e livelli di annidamento, collegamento a formalismi a componenti. 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. Processori Virtuali e Deployment. Struttura dell'applicazione multi architettura come albero di directory; metadati di descrizione dell'applicazione, elementi del linguaggio ALDL; processi, attributi dei processi (vincoli hardware e software), vincoli collettivi (coallocazione), esistenza di vincoli specifici di ASSIST. Server di deployment: GEA, accenni alle versioni precedenti, confronto con i caricatori MPI; obiettivi (generalità, portabilità, eterogeneità dei supporti) e schema base (parse/query/filter/map/deploy); cenni di deployment tramite middleware di griglia.
  • 30/04 (preliminare)
    Esempi di programmazione in ASSIST
  • 05/05
  • 08/05 Data Mining Parallelo : componenti algoritmiche, regole di associazione, classificazione, clustering
  • 14/05

Sistemi operativi distribuiti, Grid e Cloud

  • 15/05 Sistemi operativi distribuiti e di griglia. Il progetto XtreemOS
  • 19/05 Il progetto XtreemOS (2)
  • 21/05
  • 22/05

Parallelismo su chip: CPU multi-core e GPU computing


Elenco delle lezioni previste ancora da effettuarsi

I giorni 26 e 27/3 NON ci sarà lezione.

  • 02/04 16/04 07/05
apd/lezioni0809.txt · Ultima modifica: 20/04/2010 alle 17:57 (9 anni fa) da Massimo Coppola