Strumenti Utente

Strumenti Sito


ccp:lezioni0607

Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

Link a questa pagina di confronto

Entrambe le parti precedenti la revisione Revisione precedente
Prossima revisione
Revisione precedente
ccp:lezioni0607 [10/05/2007 alle 17:41 (17 anni fa)]
Massimo Coppola
ccp:lezioni0607 [21/05/2007 alle 08:30 (17 anni fa)] (versione attuale)
Massimo Coppola aggiornamento lezione 16-5
Linea 30: Linea 30:
   * **7/05** __Ambienti di programmazione per memoria esterna__\\ Confronto tra tre sistemi diversi per astrazione fornita, metodologia di implementazione (run-time, compilatore, libreria), tipo di problemi e piattaforma di esecuzione. TPIE; modello di programmazione concreto derivato da PDM, implementazione ad alto livello. VIC*. FG come approccio che unisce parallelismo e gestione della memoria esterna; parallelismo pipeline/Dag, concetto di buffer gestito dal supporto, thumbnail come puntatore e meccanismo di controllo del trasferimento dati. Moduli funzionali e replicazione automatica (farm implicito). Confronto con l'approccio ASSIST in termini di espressività e complessità del supporto dell'ambiente. \\ Modelli derivati dal BSP con costo di comunicazione più realistico: modello BSP*, concetto di critical block size, misura del costo in termini del numero di blocchi scambiati. Modello D-BSP, parametri di costo G(n) e L(n) funzioni della dimensione della (sotto)macchina e decomponibilità in insiemi di processi indipendenti. Cenni alla simulabilità in memoria esterna del BSP-*, ed al modello EdD-BSP (decomponibilità associata a skeleton).    * **7/05** __Ambienti di programmazione per memoria esterna__\\ Confronto tra tre sistemi diversi per astrazione fornita, metodologia di implementazione (run-time, compilatore, libreria), tipo di problemi e piattaforma di esecuzione. TPIE; modello di programmazione concreto derivato da PDM, implementazione ad alto livello. VIC*. FG come approccio che unisce parallelismo e gestione della memoria esterna; parallelismo pipeline/Dag, concetto di buffer gestito dal supporto, thumbnail come puntatore e meccanismo di controllo del trasferimento dati. Moduli funzionali e replicazione automatica (farm implicito). Confronto con l'approccio ASSIST in termini di espressività e complessità del supporto dell'ambiente. \\ Modelli derivati dal BSP con costo di comunicazione più realistico: modello BSP*, concetto di critical block size, misura del costo in termini del numero di blocchi scambiati. Modello D-BSP, parametri di costo G(n) e L(n) funzioni della dimensione della (sotto)macchina e decomponibilità in insiemi di processi indipendenti. Cenni alla simulabilità in memoria esterna del BSP-*, ed al modello EdD-BSP (decomponibilità associata a skeleton). 
   * <del>**9/05** Lezione cancellata</del>.   * <del>**9/05** Lezione cancellata</del>.
-  * **11/05** __ __ +  * **11/05** __Data Mining Parallelo - Parallelizzazione dell'algoritmo DBSCAN__ \\ Metodo di clustering per densità. Approccio, problemi per //dataset// e //spazi// di dimensioni elevate. Strutture dati per indicizzazione spaziale: gli R-tree come classe di strutture efficienti, struttura generale ed operazioni base, lo R*-tree, proprietà specifiche. Il concetto di range e neighborhood query. Utilizzo nell'algoritmo DBSCAN: algoritmo sequenziale; procedura ExpandCluster; complessità; costo computazionale in pratica. Cenni alle parallelizazioni basate sul partizionamento del dataset (pDBSCAN), sull'esplorazione in parallelo di più punti; il problema della ricostruzione dei cluster. Decomposizione master-slave, con replicazione dello R*-tree (esecuzione delle query con un farm). Collo di bottiglia e ridondanza dei risultati, strategie di filtraggio distribuito dei dati. Prestazioni.\\ Introduzione al problema della classificazione per induzione di alberi.\\ Trovate vari link ad articoli sull'algoritmo DBSCAN sulla mia pagina personale (corso di CCP  05-05) 
-  * **14/05** __ __ + 
-  * **16/05** __ __ +| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/SpatialDM.invited.pdf|Articolo introduttivo al Data Mining Spaziale]] | 
-  * **18/05** __ __+| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/p322-beckmann.pdf|La struttura dati R*-tree]] | 
 +| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/kdd-96.pdf|Algoritmo DBSCAN]] | 
 +| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/LNCS2150_21500326.pdf|Parallelizzazione a skeleton di DBSCAN]] | 
 +| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/p25-chakrabarti.pdf|Gestione della concorrenza in metodi di accesso spaziale]] | 
 + 
 +  * **14/05** __Problemi dividi e conquista__ \\ I problemi dividi e conquista (D&C) in parallelo, ipotesi generali (cardinalità arbitraria e/o variabile di divisione, alberi non bilanciati, peso computazionale non omogeneo). N-body, algoritmo esatto, O(N²) per passo; quad-tree e oct-tree, decomposizione spaziale dei dati; algoritmo Barnes-Hut, approssimazione con centro di massa, informazioni riassuntive nell'oct-tree; ricostruzione dell'albero ad ogni passo, costo computazionale O(N log N) per passo. \\ Classificazione come problema di data mining (supervised learning), modello di riferimento dei dati (casi/attributi nominali e continui), il modello di classificazione ad albero; C4.5; test su singolo attributo, esplorazione esaustiva dei test nell'intorno della soluzione parziale, ricerca greedy, formulazione D&C; espressione formale del criterio di split (information gain), algoritmo sequenziale per attributi nominali O(N) e continui O(N log N). Conseguenze del sorting per l'applicazione sequenziale e il caso parallelo. Possibili strategie di parallelizzazione di problemi D&C e loro problemi nel caso di D&C irregolare. \\ Alcuni riferimenti: 
 + 
 +| [[http://www.di.unipi.it/~coppola/didattica/ccp0506/papers/ML_1.1.81_Quinlan.pdf|Introduzione alla classificazione]] | 
 + 
 +  * **16/05** __C 4.5 parallelo, DM parallelo e gestione dei dati__ \\ Analisi dell'algoritmo C4.5 e delle implementazioni in  parallelo (SLIQ, SPRINT, ScalParC). Criterio di costo e necessità di calcolare gli istogrami delle classi sulle partizioni. Strategie di espansione in parallelo per task, per sottoalberi, per livelli; vantaggi e svantaggi, rispetto al massimo parallelismo esplicitabile, alla maggiore o minore sincronizzazione tra i nodi di calcolo, alla quantità di comunicazioni necessarie. Partizionamento del database verticale (sugli attributi) e orizzontale (sui casi), conseguenze sulle comunicazioni necessarie al calcolo degli istogrammi. \\ Meccanismi di gestione dei dati nel Data Mining: flat files, sistemi di DBMS, introduzione di primitive dedicate nei due casi; vantaggi e svantaggi delle diverse scelte tecnologiche e pratiche (complessità di implementazione degli algoritmi, delle primitive di accesso ai dati, overhead di accesso). Meccanismi di Parallel data management, cenni alle scelte fatte nel prototipo Parallel Data Repository (portabilità inter applicazione ma non inter-architetturale, orientamento ai blocchi, primitive di accesso type-aware ottimizzate per il DM). \\ Riferimenti: 
 + 
 +| //TO DO// |  
 + 
 +  * **18/05** __Architetture Multicore__ \\ Introduzione ai multicore, richiami alle motivazioni tecnologiche. Multicore simmetrici e asimmetrici. Core multipli, hypertreading, cenni ad approcci differenti (architettura Tera, Transputer). Architetture multicore asimmetriche: IBM CELL, Intel IXP2400; descrizione (in particolare la differene struttura di interconnessione nelle due CPU), discussione delle scelte di progettazione determinanti nelle due architetture (elavata banda di calcolo vs bassa potenza di calcolo rispetto alla banda di trasferimento). Cenni alle problematiche di programmazione a basso livello, e framework di programmazione più astratti. Architetture multicore simmetriche ad elevato parallelismo: Sun Niagara, Azul Vega 2; utilizzo prevalente per applicazioni multithread, database, supporto a macchine virtuali (Java, .Net) senza modifiche al modello di programmazione.
   * **21/05** __ __   * **21/05** __ __
   * **23/05** __ __   * **23/05** __ __
 +  * **25/05** __ __
ccp/lezioni0607.1178818868.txt.gz · Ultima modifica: 27/06/2007 alle 12:16 (17 anni fa) (modifica esterna)