FACOLTA DI SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di Laurea Specialistica in Informatica
TESI DI LAUREA SPECIALISTICA
Validation skeleton-based parallel framework: Muskel 2
Validazione dell’ambiente di sviluppo parallelo basato su
skeleton: Muskel 2
Laureando
Relatore
Antonio Nicoletti
Marco Danelutto
SOMMARIO
SOMMARIO ... 2
INDICE DELLE FIGURE ... 4
INDICE DELLE TABELLE ... 5
INDICE DELLE EQUAZIONI ... 6
INDICE DEL CODICE ... 7
PREFAZIONE ... 9
CAPITOLO 1 INTRODUZIONE ... 10
1.1 INTRODUZIONE ... 10
1.2 IL PUNTO DI PARTENZA ... 11
1.3 CONTENUTO DELLA TESI ... 12
CAPITOLO 2 STATO DELL’ARTE ... 14
2.1 PROGRAMMAZIONE PARALLELA ... 14
2.2 MODELLI DI PROGRAMMAZIONE PARALLELA ... 20
2.3 PARALLELISMO IN JAVA: ORIGINI ... 23
2.4 PARALLELISMO IN JAVA OGGI ... 26
2.5 MUSKEL 2–BASI ... 31
2.6 MUSKEL 2–INTERFACCE ... 36
2.7 MUSKEL 2–SKELETON ... 39
2.8 MUSKEL 2–ANALISI DEL CONTESTO ... 49
2.9 MUSKEL 2–ARCHITETTURE UTILIZZATE ... 55
CAPITOLO 3 APPLICAZIONI UTILIZZATE E IMPLEMENTAZIONE SEQUENZIALE ... 58
3.1 RANGE DI APPLICAZIONI ... 58
3.2 FATTORIZZAZIONE IN NUMERI PRIMI ... 61
3.2.1 Problema ... 61
3.2.2 Approccio risolutivo ... 62
3.3.3 Implementazione ... 63
3.3 RISOLUZIONE DI SISTEMI LINEARI ... 64
3.3.1 Problema ... 64 3.3.2 Approccio risolutivo ... 65 3.3.3 Implementazione ... 68 3.4 K-NEAREST NEIGHBOR ... 73 3.4.1 Problema ... 73 3.4.2 Approccio risolutivo ... 75 3.4.3 Implementazione ... 76 3.5 HIERARCHICAL CLUSTERING ... 78 3.5.1 Problema ... 78 3.5.2 Approccio risolutivo ... 82 3.5.3 Implementazione ... 86 3.6 CHIUSURA TRANSITIVA ... 89
3.6.1 Problema ... 89
3.6.2 Approccio risolutivo ... 90
3.6.3 Implementazione ... 91
3.7 CONCLUSIONI ... 92
CAPITOLO 4 PARALLELIZZAZIONE DELLE APPLICAZIONI ... 93
4.1 INTRODUZIONE ... 93
4.2 FATTORIZZAZIONE NUMERI PRIMI ... 94
4.2.1 Parallelizzazione locale ... 94
4.2.2 Parallelizzazione remota... 103
4.3 RISOLUZIONE DI SISTEMI LINEARI ... 103
4.3.1 Parallelizzazione locale ... 103 4.3.2 Parallelizzazione remota... 112 4.4 K-NEAREST NEIGHBOR... 114 4.4.1 Parallelizzazione locale ... 114 4.4.2 Parallelizzazione remota... 118 4.5 HIERARCHICAL CLUSTERING ... 120 4.5.1 Parallelizzazione locale ... 120 4.5.2 Parallelizzazione remota ... 128 4.6 CHIUSURA TRANSITIVA ... 132 4.6.1 Parallelizzazione locale ... 132 4.6.2 Parallelizzazione remota ... 134
CAPITOLO 5 VALIDAZIONE SPERIMENTALE ... 136
5.1 PREMESSE ... 136
5.2 FATTORIZZAZIONE IN NUMERI PRIMI ... 142
5.2.1 Sperimentazione locale ... 142
5.2.2 Sperimentazione remota ... 144
5.3 RISOLUZIONE DI SISTEMI LINEARI ... 150
5.3.1 Sperimentazione locale ... 151 5.3.2 Sperimentazione remota ... 155 5.4 K-NEAREST NEIGHBOR ... 156 5.4.1 Sperimentazione locale ... 157 5.4.2 Sperimentazione remota ... 160 5.5 HIERARCHICAL CLUSTERING ... 161 5.5.1 Sperimentazione locale ... 162 5.5.2 Sperimentazione remota ... 166 5.6 CHIUSURA TRANSITIVA ... 167 5.6.1 Sperimentazione locale ... 168 5.6.2 Sperimentazione remota ... 169
CAPITOLO 6 CONCLUSIONI E SVILUPPI FUTURI ... 170
BIBLIOGRAFIA ... 173
RINGRAZIAMENTI ... 177
APPENDICE A ... 178
INDICE DELLE FIGURE
FIGURA 1-ARCHITETTURE UMA/NUMA ... 18
FIGURA 2-ARCHITETTURA DISTRIBUITA ... 19
FIGURA 3-STREAM LAZY EVALUATION [30] ... 28
FIGURA 4-PATTERN PUBLISHER-SUBSCRIBER ... 37
FIGURA 5-FLATMAP ... 44
FIGURA 6-GAUSS-ELIMINATION PHASE ... 67
FIGURA 7-BACK SUBSTITUTION PHASE ... 68
FIGURA 8-KNN SU UNO SPAZIO DIMENSIONALE CLASSIFICATO IN 3 CLASSI DIFFERENTI ... 74
FIGURA 9-MISURE DI DISTANZA SPAZIALI [42] ... 75
FIGURA 10–METRICA [46] ... 81
FIGURA 11-CHIUSURA TRANSITIVA WARSHALL ALGORITHM [48] ... 91
FIGURA 12-FATTORIZZAZIONE NUMERI PRIMI, SCHEMA LOGICO PATTERN PARALLELI UTILIZZATI (CASO FARM) ... 96
FIGURA 13-RIPARTIZIONE ALTERNATA DEI TASK ... 98
FIGURA 14-FATTORIZZAZIONE DI NUMERI PRIMI, SCHEMA LOGICO PATTERN UTILIZZATI (CASO MAP) ... 99
FIGURA 15-FATTORIZZAZIONE NUMERI PRIMI, SCHEMA LOGICO PATTERN UTILIZZATI (CASO IBRIDO)... 101
FIGURA 16-RISOLUZIONE SISTEMI LINEARI, SCHEMA LOGICO PATTERN UTILIZZATI (CASO SCANSIONE PER RIGHE) ... 105
FIGURA 17-GESTIONE ARRAY IN JAVA ... 110
FIGURA 18-RISOLUZIONE DI SISTEMI LINEARI, SCHEMA LOGICO PATTERN UTILIZZATI (SOLUZIONE SISTEMA X=A-1B) ... 113
FIGURA 19-KNN, SCHEMA LOGICO PATTERN UTILIZZATI (CASO MAP) ... 115
FIGURA 20-KNN, SCHEMA LOGICO PATTERN UTILIZZATI (CASO FARM) ... 117
FIGURA 21-KNN, SCHEMA LOGICO PATTERN UTILIZZATI (CASO REMOTO) ... 119
FIGURA 22-HIERARCHICAL CLUSTERING, SCHEMA LOGICO PATTERN UTILIZZATI (FASE PRE-CLUSTERIZZAZIONE) ... 123
FIGURA 23-HIERARCHICAL CLUSTERING, SCHEMA LOGICO PATTERN UTILIZZATI (VERSIONE FUNZIONALE - FASE DI MERGING) .. 132
INDICE DELLE TABELLE
TABELLA 1-PARAMETRI DI CONFIGURAZIONE NODO SERVER ... 34 TABELLA 2-LISTA OPERATORI IN MUSKEL 2, LA PIPELINE È IMPLICITAMENTE COSTRUITA ... 39 TABELLA 3-ARCHITETTURE DEI NODI USATI NEI CLUSTER PER LA SPERIMENTAZIONE REMOTA ... 56INDICE DELLE
EQUA-ZIONI
EQUAZIONE 1-HIERARCHICAL CLUSTERING UPDATING FORMULA ... 81
EQUAZIONE 2-PASSO ITERATIVO WARSHALL ALGORITHM ... 90
EQUAZIONE 3-TEMPI DI PARALLELIZZAZIONE IDEALI ... 138
EQUAZIONE 4-FORMULA SPEED-UP IN PARALLEL COMPUTING ... 138
EQUAZIONE 5-FORMULA SCALABILITÀ IN PARALLEL COMPUTING ... 138
INDICE DEL CODICE
CODICE 1-USO DEL PUBLISHER E SUBSCRIBER ... 32
CODICE 2-ESEMPIO PIPELINE ... 40
CODICE 3-ESEMPIO PIPELINE ... 41
CODICE 4-ESEMPIO FARM ... 41
CODICE 5-ESEMPIO FARM ... 42
CODICE 6-ESEMPIO MAP ... 43
CODICE 7-ESEMPIO REDUCE ... 44
CODICE 8-ESEMPIO FLATMAP ... 45
CODICE 9-ESEMPIO GROUPBY ... 47
CODICE 10-ESEMPIO GROUPBY ... 49
CODICE 11-ESEMPIO NELL'USO DEL CONTESTO LOCALE ... 50
CODICE 12-ESEMPIO NELL'USO DEL CONTESTO REMOTO ... 52
CODICE 13-ESEMPIO CON CONTESTO REMOTO ... 52
CODICE 14-ESEMPIO DI COMPUTAZIONE REMOTA ... 54
CODICE 15-ESEMPIO DI COMPUTAZIONE REMOTA ... 54
CODICE 16-ESEMPIO DI COMPUTAZIONE REMOTA ... 55
CODICE 17-FATTORIZZAZIONE NUMERI PRIMI, IMPLEMENTAZIONE SEQUENZIALE ... 63
CODICE 18-FATTORIZZAZIONE NUMERI PRIMI, METODI AUSILIARI ... 64
CODICE 19-METCODICE DELLA GAUSS ELIMINATION PHASE ... 67
CODICE 20-METACODICE DELLA BACK SUBSTITUTION PHASE ... 68
CODICE 21-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE SEQUENZIALE 1 ... 70
CODICE 22-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE SEQUENZIALE 2 ... 71
CODICE 23 -RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE SEQUENZIALE 3 ... 72
CODICE 24-RISOLUZIONE SISTEMI LINEARI, METODI AUSILIARI ... 73
CODICE 25-KNN, IMPLEMENTAZIONE SEQUENZIALE ... 76
CODICE 26-HIERARCHICAL CLUSTERING, IMPLEMENTAZIONE SEQUENZIALE (FASE 1) ... 87
CODICE 27-HIERARCHICAL CLUSTERING, IMPLEMENTAZIONE SEQUENZIALE (FASE 2) ... 88
CODICE 28-HIERARCHICAL CLUSTERING, IMPLEMENTAZIONE SEQUENZIALE (FASE 3) ... 89
CODICE 29-CHIUSURA TRANSITIVA, IMPLEMENTAZIONE SEQUENZIALE ... 92
CODICE 30-FATTORIZZAZIONE NUMERI PRIMI, IMPLEMENTAZIONE PARALLELA (CASO MAP) ... 97
CODICE 31-FATTORIZZAZIONE NUMERI PRIMI, IMPLEMENTAZIONE PARALLELA (CASO FARM) ... 100
CODICE 32-FATTORIZZAZIONE NUMERI PRIMI, IMPLEMENTAZIONE PARALLELA (CASO IBRIDO) ... 102
CODICE 33-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE PARALLELA (CASO SCANSIONE PER RIGHE) ... 107
CODICE 34-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE PARALLELA (CASO SCANSIONE PER COLONNE) ... 109
CODICE 35-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE PARALLELA (CASO SCANSIONE PER COLONNE TRASPOSTE) ... 112
CODICE 36-RISOLUZIONE SISTEMI LINEARI, IMPLEMENTAZIONE PARALLELA (SOLUZIONE SISTEMA X=A-1B) ... 113
CODICE 37-KNN, IMPLEMENTAZIONE PARALLELA (CASO MAP) ... 116
CODICE 38-KNN, IMPLEMENTAZIONE PARALLELA (CASO FARM) ... 118
CODICE 39-KNN, IMPLEMENTAZIONE PARALLELA (CASO REMOTO) ... 120
CODICE 40-HIERARCHICAL CLUSTERING, IMPLEMENTAZIONE PARALLELA (FASE PRE-CLUSTERIZZAZIONE E FASE ITERATIVA) ... 126
CODICE 41-HIERARCHICAL CLUSTERING, IMPLEMENTAZIONE PARALLELA (FASE DI MERGING) ... 127
CODICE 42 - HIERACHICAL CLUSTERING, IMPLEMENTAZIONE PARALLELA (VERSIONE FUNZIONALE - FASE ITERATIVA E PRE -CLUSTERING) ... 130
CODICE 44-CHIUSURA TRANSITIVA, IMPLEMENTAZIONE PARALLELA (CASO MAP) ... 133
CODICE 45-CHIUSURA TRANSITIVA, IMPLEMENTAZIONE PARALLELA (CASO FARM) ... 134
CODICE 46-CHIUSURA TRANSITIVA, IMPLEMENTAZIONE PARALLELA (VERSIONE FUNZIONALE) ... 135
Prefazione
Il mondo dell’Informatica è in continuo mutamento. Anno dopo anno schiere di ri-cercatori estendono le conoscenze e le possibilità offerte da tecnologie sempre più in espansione. Ogni ramo è soggetto a questa continua evoluzione in diversa misura e con tempi differenti: noi andremo a focalizzarci, in particolare, sulla transizione da un approc-cio programmativo seriale a uno che mira a sfruttare le sempre maggiori risorse e unità di calcolo che vanno a comporre i calcolatori attuali. E’ possibile oggi trarre vantaggio da unità di calcolo più potenti come le GPU oppure realizzare delle GRID computazionali for-mate da centinaia, se non migliaia di calcolatori diversi e davvero distanti fra loro. Servo-no dunque ambienti di programmazione parallela e distribuita capaci di astrarre a livelli sempre più alti le nuove tecnologie così da rendere anch’esse “programmer-friendly”. Questo è fra gli obiettivi dell’ambiente di sviluppo parallelo basato su skeleton, Muskel 2, il quale sarà ampiamente analizzato in questa tesi rivelandone meccanismi e funziona-mento, espandendone la documentazione, introducendo nuove categorie di esempi che mostrino le reali capacità e possibilità del framework, dibattendone, infine, eventuali mi-gliorie e lacune. Vedremo, nel corso della tesi, come questo è solo uno dei numerosi stru-menti a favore di un modus-operandi programmativo ancora difficile da gestire, ma capa-ce di attrarre sempre più utilizzatori. Essi sviluppano nuovi applicativi e introducono nuovi paradigmi come quello forse più efficace adesso per semplicità e potenza espressiva: gli algorithmic skeleton, su cui Muskel 2 poggia le proprie basi. Infine i più comuni linguaggi di programmazione tentano di uniformarsi se non precedere gli accadimenti nell’evoluzione tecnologica dedicando intere e molteplici API sull’argomento: fra questi abbiamo il noto linguaggio Java dal quale la libreria in oggetto trae ancora ispirazione e fondamenta. Insomma andremo ad analizzare ed eseguire un’opera di verifica, validazio-ne e testing, su questo connubio di tecnologie che Muskel 2 incarna, dimostrando la sua validità in kernel di applicativi davvero distanti fra loro, nell’umile speranza di portare all’attenzione un lavoro ben fatto e soprattutto utile a studi futuri.
Capitolo 1
INTRODUZIONE
1.1 Introduzione
Con la fine della validità della cosiddetta legge di Moore termina l’era nella quale l’unico scopo dei progettisti di CPU era quello di ridurre, con una cadenza regolare, le di-mensioni dei circuiti integrati nei microprocessori incrementandone le prestazioni. L’intuizione di Moore del 1965 [1] ha dovuto scontrarsi con la dura realtà delle leggi fisi-che le quali impediscono la miniaturizzazione dei transistor al di sotto delle dimensioni di un atomo ossia 1-2 nanometri, traguardo quasi raggiunto nel 2016 con la sesta genera-zione dei processori Intel i cui circuiti arrivano a 14 nanometri.
Ovviamente il consolidarsi di una simile certezza non ha fermato l’innovazione che ha trovato nella “legge di Dally” [2] il suo nuovo mantra. Essa scandisce l’incremento delle prestazioni dei calcolatori, non attraverso la miniaturizzazione dei propri transistor, bensì andando a incrementare il numero dei core contenuti nei processori. Questa legge va to-talmente a stravolgere una metodologia di programmazione, assimilata da intere genera-zioni di programmatori, secondo la quale un applicativo dovesse evolvere in maniera se-quenziale, a vantaggio di un nuovo paradigma nel quale occorre identificare le attività concorrenti insiti all’interno di un’applicazione per tentare di eseguirle parallelamente sui
vari core oppure in maniera distribuita fra una moltitudine di calcolatori collegati tramite una rete: nasce in questo modo la computazione parallela [3] e distribuita [4].
Per ottemperare a queste nuove esigenze e per agevolare il passaggio dalla com-putazione seriale a quella parallela, in pochi anni, si comincia a parlare di parallel design pattern, capaci di fornire ai programmatori le più comuni logiche che possono sfruttare per riuscire a risolvere un problema di natura parallela [5]. Inoltre nascono una moltitudi-ne di framework che permettono di implementare alcuni di questi pattern moltitudi-nello svariato mondo dei linguaggi di programmazione esistenti, sotto forma dei cosiddetti algorithmic skeletons [6]. L’evoluzione di questi strumenti e in particolare di validi framework per la programmazione parallela strutturata [7], è fondamentale per venire incontro al prepon-derante e incalzante problema del passaggio dalla computazione seriale a quella parallela nella quale l’intera comunità di ricercatori si è imbattuta. Questo problema non è di im-mediata soluzione vista la profondità con cui la programmazione seriale è radicata, es-sendo anche più affine al ragionamento umano ma essenziale per continuare a progredire nello sfruttamento delle nuove risorse di calcolo disponibili.
1.2 Il punto di partenza
Come anticipato nel paragrafo precedente sfruttare il parallelismo su larga scala è un procedimento complesso per il quale le tecniche algoritmiche standard e le loro corri-spondenti strutture dati non sono sufficienti. E’ stato necessario sviluppare nuovi stru-menti e metodi, sia nel campo hardware per costruire processori all’avanguardia capaci di rendere disponibile uno scaling delle performance che non contasse più su un aumento della frequenza di calcolo bensì su una modifica architetturale sostanziale, che nel campo software, attraverso lo sviluppo di librerie e linguaggi capaci di incarnare il nuovo para-digma emergente. Una comunità di ricercatori sempre più attiva e ispirata dal lavoro di Murray Cole [8], il quale introduceva gli algorithmic skeletons come strumento capace di attenuare la complessità della programmazione parallela e uniformarla a un comune set di pattern componibili, atti a formarne di nuovi, comincia a sviluppare veri e propri
lin-guaggi paralleli, come P3L, ASSIST, Intel TBB e così via, nonché librerie assestanti come Li-thium, Muesli, SkePU e il punto di partenza della tesi ossia Muskel.
Muskel [9] è una libreria Java sviluppata a Pisa nel lontano 2005 che è stata in gra-do di implementare efficacemente il paradigma di programmazione a skeleton introgra-dotta da Cole e capace di eliminare una delle criticità individuate dall’autore stesso. Il costo di una metodologia così attraente ed efficiente per affrontare i programmi paralleli veniva pagata in termini di libertà programmativa. Ebbene questo framework, in modo pioneri-stico, rendeva disponibile al programmatore, oltre ad un insieme predefinito di skeleton, la possibilità di implementarne di propri, così da ampliare l’espressività del linguaggio. D’altro canto la libreria si basava su una versione Java che ancora non aveva mosso i suoi primi passi nella direzione parallela, lacuna parzialmente colmata con il rilascio della ver-sione 8 nella quale vengono introdotti ed implementati tutta una serie di strumenti di cui avremo modo di approfondire nel Capitolo 2. Una così allettante opportunità offerta da Java è stata colta nel 2015 quando è stata sviluppata una nuova, più performante, versio-ne di Muskel capace di fondere i vantaggi di quella originale con una migliore implemen-tazione dei meccanismi paralleli di basso livello: si passa, infatti, dall’utilizzo dei Java Thread a quello dei Java Stream, si migliora l’esperienza di programmazione sfruttando la Fluent Interface e così via. Questa nuova versione sviluppata sempre a Pisa prende il no-me di Muskel 2 [10]. Il Capitolo 2 ci perno-metterà di esplorare cono-me questo frano-mework sia necessario per rafforzare la programmazione parallela in Java e quali sono le sue principa-li dinamiche e meccanismi.
1.3 Contenuto della tesi
La tesi nasce con lo scopo di esplorare e validare opportunamente il nuovo fra-mework Muskel 2, cercando di raggiungere i seguenti obiettivi:
In prima istanza testare il framework attraverso un insieme di applicazioni banali ma che coprono un vasto range di kernel, al fine di dimostrare la va-lenza dell’ambiente di programmazione nell’affrontare diverse categorie di
problemi. Il Capitolo 3 presenterà tali kernel, descrivendo gli applicativi af-frontati e fornendone una personale implementazione sequenziale. Nel
Er-rore. L'origine riferimento non è stata trovata., invece, gli applicativi
evol-veranno nella loro veste parallela analizzando nel dettaglio i design pattern utilizzati.
Dimostrare attraverso un insieme di dati sperimentali, legati ai termini di efficienza nella trasformazione di un programma da sequenziale a paralle-lo, come il framework possa essere in grado, attraverso l’utilizzo di oppor-tuni skeleton, di parallelizzare efficacemente gli applicativi proposti. Le me-todologie con cui questi dati vengono strutturati e raccolti, nonché le di-namiche con cui gli applicativi vengono eseguiti e su quali architetture hardware, vengono dettagliatamente descritti nel paragrafo 2.8 . Il Errore.
L'origine riferimento non è stata trovata., invece, esporrà tali dati in
ma-niera sistematica e quanto più chiara possibile analizzando altresì perché si sono ottenuti simili risultati e come, sia il framework, sia l’implementazione abbiano inciso su di essi.
Migliorare ulteriormente il framework individuando eventuali bug presenti nel sistema sia in ambito locale che distribuito coordinandosi con il proget-tista. Una descrizione sommaria dei bug individuati verrà fornita nel Capi-tolo 6.
Espandere il numero di esempi messi a disposizione del progettista di Mu-skel 2 cosicché i meccanismi del framework nonché la relativa filosofia di programmazione possano apparire più chiari ai programmatori in erba.
Infine mostrare come il framework possa essere usato in un applicativo reale, più complesso, in cui lo svisceramento della componente seriale non è banale e l’individuazione degli skeleton da usare richiede maggior impe-gno. Tutto ciò verrà mostrato nel Capitolo 6 insieme ad una descrizione delle lacune ancora presenti nel framework e di come questo possa essere ulteriormente migliorato in eventuali sviluppi futuri.
Capitolo 2
STATO DELL’ARTE
2.1 Programmazione parallela
Abbiamo già discusso le motivazioni che hanno spinto ricercatori e programmatori a passare dal paradigma di programmazione sequenziale, in cui un problema viene parti-zionato in un discreto insieme di istruzioni per poi essere eseguite su un nodo (per nodo s’intende un calcolatore dotato di uno o più processori, con memoria, funzionalità I/O e un sistema operativo allo stato dell’arte) al paradigma parallelo, dove il problema viene partizionato in più chunk (ossia una serie di istruzioni, una funzione oppure una funziona-lità del programma a seconda della granularità adottata) che possono essere eseguiti concorrentemente su un hardware predisposto al parallelismo sotto forma di un nodo multiprocessore oppure di un cluster (con questo termine intendiamo un insieme di nodi interconnessi tramite una rete veloce LAN). La differenza sostanziale fra i due paradigmi computativi è che nel secondo è necessario risolvere tutta una serie di problematiche completamente nuove che ora andremo a sviscerare [11] [12]:
Il non determinismo: il programma può evolvere in una serie di stati non prevedibili a priori.
Le comunicazioni: ogni singola unità elaborativa cui viene affidata l’esecuzione di un chunk può avere bisogno di comunicare con altre unità contemporaneamente in esecuzione per terminare la propria. In generale i problemi che necessitano una comunicazione inter-chunk sono più com-plessi della propria controparte ossia quei problemi dotati di task indipen-denti (Embarrassingly Parallel) e presentano vari svantaggi. Le comunica-zioni introducono overhead, frequentemente richiedono una sincronizza-zione fra i vari chunk che sovente dovranno “rimanere in attesa” e quando la computazione avviene su nodi collegati in rete il traffico derivante da questo scambio di dati può rallentare anche in maniera significativa la con-nessione. Essendo uno degli aspetti critici del parallel computing questa tema è stato ampiamente dibattuto dai ricercatori classificandone e indivi-duandone varie forme, per ognuna delle quali si possono adottare oppor-tuni pattern [13].
Le sincronizzazioni: in questa sfera rientrano tutte quelle operazioni, che introducono ancora overhead, necessarie a coordinare il lavoro fra più chunk e consentire loro di generare il risultato atteso dal programmatore, facendo evolvere lo stato del programma in maniera corretta. Si pensi ad esempio alla barriera, operazione necessaria nel modello fork-join [14] do-ve ad un certo punto il flusso di esecuzione si divide in più chunk, ognuno eseguito concorrentemente, per poi ricongiungersi quando tutti terminano la propria attività: ebbene lo stato del programma potrà avanzare solo in questo momento. Oppure si pensi alla sincronizzazione necessaria quando due o più chunk devono comunicare fra loro.
Il partizionamento dei dati e la loro distribuzione: mentre nella zione sequenziale i dati vengono fruiti da una singola istanza di computa-zione, in quella parallela è spesso necessario condividere una struttura dati fra più unità elaborative. Tutto ciò richiede l’introduzione di meccanismi e l’utilizzo di politiche ad-hoc che facilitino e riducano la complessità nel par-tizionamento e/o nella distribuzione dei dati. Doveroso a questo punto sof-fermarci su due forme di parallelismo nelle quali questi meccanismi sono più o meno necessari. Da una parte abbiamo il Data Parallelism [15], un
ti-po di parallelismo che si focalizza totalmente sulla distribuzione di dati fra chunk differenti in cui sovente eseguiamo la medesima operazione su dif-ferenti sezioni di una struttura dati molto grande in maniera parallela. D’altra parte abbiamo il Task Parallelism [15] il quale lavora ad un “code granularity” più alto, nel senso che andiamo ad eseguire in parallelo diversi task ossia diverse attività del nostro applicativo parzialmente o totalmente slacciate le une dalle altre.
Il load-balancing: con questo termine s’intende la capacità del program-matore o dell’utility software che si utilizza, di distribuire in maniera ap-prossimativamente equa il carico di lavoro fra i chunk cosicché tutti possa-no terminare “quasi” nello stesso momento. Esso è un paramento fonda-mentale, cui molto spesso si farà riferimento nei capitoli successivi, poiché è direttamente connesso con le performance che la versione parallela di un programma è in grado di raggiungere. Ogni framework che implementi un modello di programmazione parallela dispone delle proprie routine per ot-timizzare il load-balancing e molte sono le tecniche presenti in letteratura alle quali ci si può ispirare come [16].
La fault-tolerance: questo termine viene annoverato fra le proprietà non funzionali di un programma parallelo e con esso viene indicata la capacità dello stesso di gestire e sopperire a qualsivoglia eccezione possa soprag-giungere di natura hardware o software. Bisogna infatti ricordare che uno degli obbiettivi fondamentali della computazione parallela è quello di otte-nere un vantaggio dalla combinazione di risorse hardware anche molto di-stanti fra loro in modo da poter risolvere fenomeni complessi. Ragion per cui ogni eventualità come il crash di un nodo appartenente al cluster oppu-re un suo qualunque errooppu-re interno deve poter esseoppu-re opportunamente gestita. Una proprietà siffatta è stata tenuta in alta considerazione nel fra-mework Muskel 2, come vedremo, avendo messo appunto validi meccani-smi per la programmazione distribuita.
Eterogeneità: l’indebolirsi della legge di Moore ha avuto diverse conse-guenze che non si sono limitate a orientarsi verso calcolatori che vedevano incrementare solo il numero delle proprie unità logiche (CPUs) bensì si è
assistito ad un’integrazione con altre PUs, come le GPU, generando un si-stema eterogeneo ma fondamentale per lavorare in high-performance computing. La collaborazione CPU-GPU oggi è sempre più stretta, nascono sempre più calcolatori capaci di ottimizzare la propria esecuzione acceden-do contemporaneamente ad entrambe le PUs e questo deve ovviamente essere reso possibile anche per gli applicativi paralleli. Pochi framework sono ancora in grado di realizzare questo compito ma sempre più tecniche stanno emergendo in letteratura a sostegno di ciò [17].
Gestione della memoria: in questo caso entriamo nell’ambito dell’architettura della memoria di un calcolatore (o cluster) parallelo multi-processore. Le tre tipologie più apprezzate sono le seguenti:
o Shared Memory: in parole povere processori multipli possono ope-rare indipendentemente ma condividono la medesima memoria; Se il tempo di accesso di ciascun processore alla memoria è costante, inoltre tutte le CPU sono collegate ad un'unica memoria, parliamo di architettura UMA (Figura 1), altrimenti se più unità UMA sono in-terconnesse fra di loro in maniera tale che tutte le CPU abbiano ac-cesso totale a ciascuna memoria ma prioritario e più rapido ad una di esse parliamo di architettura NUMA (Figura 1). Questa è l’architettura più semplice e consente un data sharing fra chunk di-versi veloce e uniforme data la prossimità delle CPUs con la/e me-moria/e. Il problema sta nella perdita di scalabilità fra memoria e CPUs, infatti, se aggiungiamo più unità elaborative aumenta il nu-mero degli accessi alla memoria condivisa con conseguente rallen-tamento per tutto il sistema ergo ogni attività parallela. Inoltre ai programmatori è affidato l’arduo compito di gestire l’accesso alle variabili globali da parte di chunk eseguiti in parallelo.
o Distributed Memory: in quest’architettura (Figura 2) ogni processore possiede un accesso esclusivo alla propria memoria e non esistono variabili globali condivise da tutte le CPUs. Tutte le PUs sono colle-gate mediante una rete e nessuna di esse ha l’accesso a memorie che non sono le proprie. Sarà il programmatore, all’occorrenza, a stabilire come e quando un’informazione debba essere spedita da un processore all’altro o meglio da un chunk all’altro, in altre parole le operazioni di comunicazione e sincronizzazione fra le attività pa-rallele sono a completo carico del programmatore e ciò costituisce uno dei principali svantaggi di questa tipologia di architettura oltre ad un accesso non uniforme alla memoria da parte dei processori remoti, dipendente dalla rete. Fra i vantaggi abbiamo invece una migliore scalabilità fra processori e memoria e il fatto che ogni pro-cessore può accedere istantaneamente alla propria memoria senza la possibilità di errori dovuti all’interferenza di altri. E’ ovvio che questa è l’architettura adottata anche da Muskel 2 quando, la com-putazione parallela, passa da un singolo nodo ad un cluster in rete, anche se in questo caso la complessità relativa alla comunicazione e sincronizzazione fra nodi è mascherata all’utente.
o Abbiamo poi anche la versione ibrida che fonde svantaggi e vantag-gi di ambo le architetture ma realizzando un sistema al contempo più compresso e potente.
Deadlock e race condition: questo è forse uno dei pericoli più insidiosi con cui si ha a che fare quando si programma in parallelo. La possibilità che tut-te le attività concorrenti rimangano bloccatut-te contut-temporaneamentut-te poiché dipendenti in maniera ciclica da altre attività. Per evitare una simile even-tualità bisogna sempre accertarsi che il computational graph del proprio applicativo non contenga mai cicli oppure realizzare opportune eccezioni atte a gestire l’insorgenza del deadlock. La scelta del modello di program-mazione parallela adottato può evitare a priori questo problema. La stessa cosa vale per il race condition, ossia l’eccezione che si verifica quando due chunk tentano di accedere contemporaneamente alla medesima risorsa in memoria. Ovviamente questo è un problema solo quando il risultato finale dell’esecuzione dei processi dipende dalla temporizzazione o dalla sequen-za con cui vengono eseguiti.
Vista la complessità dell’argomento il parallel computing può avere realmente successo solo a fronte dello sviluppo di software paralleli capaci di sostenere il program-matore con una computazione parallela ad alto livello oppure procedere autonomamen-te. Possiamo infatti distinguere due approcci trasversali per parallelizzare le applicazioni [18]:
1. L’auto-parallelization o implicit parallelization, si propone di trasformare automaticamente una serie di istruzioni, ovvero un programma di natura sequenziale in un programma parallelo. Questa è un’operazione molto
ficile da realizzare vista la grande varietà di kernel con cui si ha a che fare e certamente non esiste una tecnica univoca per identificare nel codice quel-le componenti la cui computazione può essere paralquel-lelizzata. Finora poche case, come la Intel, hanno sviluppato delle valide tecniche capaci di perse-guire quest’obiettivo, i propri compilatori sono in grado, ad esempio, in maniera più efficace rispetto ad altri, di analizzare il flusso dati di un loop per capire se è un buon candidato al worksharing (vectorization [19]) oppu-re no. D’altro canto questa tipologia di parallelizzazione esenta totalmente il programmatore dal conoscere o mettere in pratica alcuna nozione legata alla risoluzione delle problematiche precedenti, tutto viene fatto dal siste-ma.
2. Programmazione parallela o explicit parallelization: questo è il caso in cui al programmatore è affidato l’onere di realizzare la parallelizzazione : egli si dovrà occupare della chunk decomposition, del mapping dei chunk ai vari processori e di implementare le strutture di comunicazione. Qui entrano in gioco i modelli di programmazione parallela e i software che li implemen-tano. Il loro utilizzo è fondamentale per trovare un compromesso fra la complessità della materia, completamente mascherata nella parallelizza-zione implicita, e la resa di un certo grado di libertà al programmatore: solo così si possono raggiungere le migliori performance in fatto di efficienza e scalabilità.
2.2 Modelli di programmazione parallela
Andiamo ad analizzare in prima istanza i più comuni modelli di programmazione parallela oggi maggiormente usati ed implementati dalle moderne APIs. Come suggerisce il [18] i vari modelli sono valutabili sulla base di 7 criteri fondamentali: l’architettura
hardware sottostante ossia come i processori accedono alla memoria incide fortemente
sulle scelte computative del programmatore (shared o distributed memory),
paralleli, worker management aspetto che riguarda la creazione delle singole unità paral-lele, workload partition scheme ossia come gli eventuali dati vengono partizionati,
task-to-worker mapping e quindi come vengono distribuiti fra i vari worker. Vediamo quelli più
comuni:
Message Passing: questo modello pone particolare enfasi sui processi di comunicazione e sincronizzazione quindi risulta particolarmente adatto per le applicazione distribuite, dove il punto fondamentale diventa la trasmis-sione di pacchetti di informazioni da un processore all’altro. Attualmente i sistemi alto-livello che meglio implementano questo modello e ampiamen-te utilizzati in campo scientifico sono PVM (Parallel Virtual Machine) e so-prattutto MPI (Message Passing Interface). Sono sistemi complessi che ri-chiedono alte competenze al programmatore oppure l’affiancamento di al-tre utility che ne facilitano l’utilizzo. Anche perché come in C al program-matore è affidata la totale gestione delle locazioni di memoria, in questo modello esso dovrà preoccuparsi di come spedire i messaggi da un worker all’altro, definirne il modo, sincrono o asincrono e sincronizzare la trasmis-sione affinché i dati non vengano corrotti.
Shared Memory: questo modello si pone agli antipodi rispetto al preceden-te infatti in questo caso ci si fonda su un’archipreceden-tettura shared-memory e i principali problemi da affrontare riguardano la corretta gestione dell’accesso asincrono da parte di più worker alla medesima locazione di memoria attraverso monitors, semafori, operazioni atomiche e mutexes. Le più comunemente note API in quest’ambito sono OpenMP (Open Multi-processing) [20] per soluzioni multicore, oppure OpenCL o CUDA per solu-zioni riguardanti l’uso della GPU (le GPU normalmente non sono a memoria condivisa solo nelle ultime versioni è stato introdotto un modo di accedere alla memoria dell’host).
Algorithmic skeleton: è comunemente definito come un modello di pro-grammazione parallela assestante e nella tesi vi si farà maggiormente rife-rimento. Esso fornisce la migliore astrazione per implementare un algorit-mo parallelo. Ora tutti i meccanismi relativi alla comunicazione,
sincroniz-zazione, task scheduling e così via verranno automaticamente gestiti dall’API (con la possibilità, da parte del programmatore, di tarare tali mec-canismi in base ai propri scopi ma con mecmec-canismi ad alto livello) e il pro-grammatore dovrà solamente focalizzarsi sulla scelta di una strategia paral-lela per risolvere il proprio problema. Le migliori Skeleton API implementa-no nativamente i pattern più usati in una black box che può essere usata e personalizzata dal programmatore (skeleton). Ma non è tutto: questi og-getti possono anche essere combinati, secondo opportune regole, per for-mare strutture più complesse (skeleton compositions). I più comuni pattern verranno analizzati nel Errore. L'origine riferimento non è stata trovata. mentre i software che oggi sono maggiormente usati circa il modello in og-getto sono eSkel ideato dal gruppo di lavoro di Murray Cole, ASSIST, P3L,
Li-thium, Skepu, Muesli e Sketo maturati da gruppi di lavoro nell’università di
Pisa e infine Muskel e Muskel 2. La programmazione a skeleton si trova ad un livello di astrazione superiore rispetto ai modelli precedenti pertanto i maccanismi interni alle APIs possono riferirsi anche ad alcuni di questi mo-delli, inoltre gli skeleton (definiti in [8] come una struttura che nasconde all’utente un pattern comune e parametrico non solo nel numero di pro-cessori che userà ma in altri fattori come la granularità, la topologia, la di-stribuzione dei dati fra i worker interni e così via) forniscono un modello template-based di programmazione riusabile in diverse applicazioni, porta-bile da una piattaforma all’altra senza manomissioni rilevanti ed efficiente avendo dimostrato come possa garantire performance parallele ottimali. A prescindere dal modello o dal paradigma cui ci si riferisce ogni software parallelo si basa su delle specifiche scelte tecniche e affronta più o meno bene ogni criticità del cal-colo parallelo: molto dipende dalla categoria di applicativi cui ci si rivolge oppure al livello di competenza che un eventuale programmatore deve possedere nel proprio utilizzo. Pra-tica comune consiste nell’affiancare ad un linguaggio di programmazione preesistente, come Java, una libreria o framework che supporti il parallelismo, come Muskel 2. Prima di scendere nel dettaglio di tale framework andiamo ad analizzare i meccanismi offerti dall’ultima versione di Java.
2.3 Parallelismo in Java: origini
L’ambiente Java ha investito molto nell’introduzione di meccanismi e framework nativi volti a rendere la programmazione parallela parte del proprio background. Quest’obiettivo è stato parzialmente raggiunto nella versione 8 dove le funzioni di aggre-gazione, ossia l’implementazione dei più comuni pattern paralleli, applicati ai Java Stream [21], ossia la manipolazione di una sequenza di oggetti virtualmente infiniti, supera tutte le limitazioni imposte dai tentativi precedenti nell’approcciarsi a questo nuovo mondo.
In Java storicamente il parallelismo, o meglio la concorrenza parlando di un perio-do perio-dove ancora i multicore non erano così diffusi, ha esordito con l’utilizzo dei Thread ma questi non sono stati particolarmente apprezzati dagli sviluppatori a causa dell’eccessiva complessità di gestione dei vari meccanismi in essi contenuti e della totale responsabilità del programmatore nell’uso di quest’ultimi. La gestione della threadpool, l’inizializzazione di un Thread implementando la classe Runnable o Thread, la manipolazione dei risultati, nonché lo scheduler dei Thread era totalmente a carico del programmatore che molto presto si ritrovava imprigionato in un sistema tedioso e error-prone. E’ ovvio che tutti i meccanismi moderni in Java si basato su questa struttura a basso livello ma era necessa-rio astrarre con qualche ultenecessa-riore layer per poter rendere appetibile il tutto agli sviluppa-tori. [22]
Questo è stato fatto a partire da Java 1.5 quando la Concurrency API introduce il concetto di ExecutorService come un più alto livello di astrazione che inglobava l’uso dei Thread.
Vediamone brevemente i punti salienti [23]:
Ogni istanza della suddetta classe è in grado di eseguire task asincroni e ge-stire una threadpool cosicché il programmatore non dovesse più creare i vari Thread manualmente.
Ogni Thread all’interno del pool è riutilizzabile finché l’Executor non termi-na la propria esecuzione fin quando non gli viene esplicitamente imposto dal programmatore, rimanendo in attesa di nuovi task da eseguire.
La classe Executor fornisce diverse factory per istanziare un suo oggetto a seconda delle esigenze dell’utente.
La definizione di un task, inteso come l’attività che un Thread deve esegui-re, può avvenire ora non solo grazie alla classe Runnable ma anche me-diante quella Callable. Essa rispetto alla precedente consente di restituire un valore di ritorno che non sia void. L’aspetto interessante di Callable è la possibilità di monitorare lo stato di esecuzione del task inglobato.
La sottomissione di un task all’oggetto ExecutorService, per la sua ese-cuzione nella corrispondente pool, per prima cosa può essere effettuata at-traverso vari metodi: quello banale submit() e poi invokeAll() e in-vokeAny() per sottomettere contemporaneamente un insieme di task. In secondo luogo questi metodi dovrebbero restituire il valore di ritorno del/i task sottomessi ma siccome non sappiamo a priori quando l’esecuzione di ognuno sarà terminata essi restituiscono uno o più oggetti Future.
Future è un oggetto molto speciale che custodisce il valore di ritorno di un qualche task fino a quando la sua esecuzione non deterministica non sia realmente terminata: solo a quel punto applicandovi il metodo get() pos-siamo ottenere il valore di ritorno del tipo con cui abbiamo parametrizzato in origine l’oggetto Callable.
Essendo Java un ambiente shared-memory nel quale tutti i Thread possono acce-dere a locazioni di memoria condivise dai vari processori, era necessario sviluppare degli strumenti che consentissero di sincronizzare l’accesso alle shared mutable variables, ope-razione ancora a carico del programmatore non solo armeggiando con la classe Thread ma anche con gli ExecutorService. Gli strumenti utilizzabili a tale scopo sono:
La parola chiave synchronized è la soluzione più vecchia usata da Java per consentire la thread-synchronization: aggiungendola nell’intestazione di un metodo, lo si rende accessibile da un solo Thread alla volta evitando così casi di race condition.
Abbiamo poi i Locks che realizzano varie forme di sincronizzazione: mu-tualmente esclusiva come nel caso precedente racchiudendo un pacchetto di istruzioni fra l’invocazione dei metodi lock() e unlock(), oppure di ti-po ReadWrite nella quale al pacchetto di istruzioni ti-possono accedere più Thread alla volta per operazioni di lettura a patto che nessuno esegua su di esso operazioni di scrittura (questo viene usato per migliorare le perfor-mance riducendo l’overhead introdotto dalla sincronizzazione).
Ancora i semafori che semplicemente limitano il numero di accessi concor-renti alla medesima risorsa ad un numero preimpostato di Thread.
Poi come soluzioni alternative si può fare ricorso, laddove possibile, alle cosiddette Atomic Variable di Java le quali sono Thraed-safe anche senza l’utilizzo di alcuno degli strumenti precedenti.
Un ulteriore livello di astrazione nella programmazione parallela è stato aggiunto con il fork/join framework, introdotto nella versione 1.7 di Java. Il paradigma su cui si fon-da questo framework è fra quelli più semplici e conosciuti di sempre: infatti si usa la tec-nica del divide et conquire, nella prima fase (FORK), per dividere ricorsivamente un task in più sotto task fino a quando l’overhead introdotto dallo splitting non supera l’effettivo guadagno in performance ottenibile dall’esecuzione di ogni sotto task su un processore o Thread differente. Nella seconda fase (JOIN) il risultato parziale restituito da ogni sotto task viaggia verso la radice dell’albero, ricostruendo il risultato totale desiderato dal pro-grammatore. L’oggetto fondamentale in quest’ambito diventa il ForkJoinPool molto si-mile all’ExecutorService ma ottimizzato per quei kernel di applicazioni che necessitano di un pattern fork/join. Quest’oggetto gestisce una Thread pool come al solito ed è in grado di ricevere task incapsulati in due tipologie di oggetti differenti: le RecursiveAction ca-pace di incorporare task che non devono restituire un valore e i RecursiveTask dotati, invece, di un valore di ritorno. [24] Sfortunatamente per Java nemmeno questo fra-mework ha ottenuto il successo desiderato, gli sviluppatori hanno ricalcato solo decine di problemi che hanno impedito una sua reale diffusione e che sono stati raccolti in [25].
2.4 Parallelismo in Java oggi
Finalmente giungiamo alla versione di Java 1.8 nella quale sembra che sia stato fatto un reale passo avanti, ancora non privo di criticità, verso una vera integrazione del parallel computing.
Abbiamo visto come il fork/join framework permetteva più o meno facilmente di implementare porzioni di codice in parallelo e abbiamo visto quali erano le sue criticità legate principalmente ad una non sempre ottimale gestione delle pool e ad un’eccessiva complessità di utilizzo da parte del programmatore dei suoi meccanismi interni. Tali criti-cità sono state ereditate in qualche modo anche dai Java Stream perché si basano su un layer che fondamentalmente implementa lo stesso framework, accusati di possedere un meccanismo sottostante troppo statico in grado di affrontare nativamente i vari kernel di problemi solo con il pattern fork/join per cui altri pattern devono essere in qualche modo simulati dai programmatori e questo come al solito genera complessità [26].
Nonostante questo, gli Stream rimangono uno dei migliori strumenti di program-mazione parallela che Java abbia mai fornito e le criticità possono essere superate proprio grazie all’affiancamento da parte di framework come Muskel 2. Oggi infatti, con le
fun-zioni di aggregazione la Java runtime realizza il partizionamento e il ricompattamento dei
risultati in maniera automatica. Un altro problema riguardava la manipolazione parallela delle collezioni non thread-safe, ossia delle collezioni il cui l’accesso parallelo da parte di un gran numero di thread portava con sé errori di thread interference o memory
consi-stency errors, il problema veniva risolto in maniera farraginosa dal programmatore
inse-rendo in punti strategici porzione di codice synchronized, accessibile da un solo thread alla volta. Lasciare questi aspetti al programmatore significava che egli non poteva dedi-carsi totalmente alla logica del programma ma era necessaria anche una manipolazione gestionale dei meccanismi intimi capaci di realizzare il parallelismo e generava una com-putazione parallela i cui parametri di efficienza non dipendevano solo da come venisse impostato il problema ma anche da come il programmatore implementasse taluni mec-canismi. Ebbene anche le problematiche legate alle collezioni non thread-safe sono state affrontate e risolte mediante l’utilizzo dei Java Stream [21]. Sono i meccanismi interni a
questa classe a occuparsi della thread contention nell’accesso ad una collezione, della sin-cronizzazione di porzioni di codice delicate o ancora la gestione delle operazioni interme-die, che trasformano lo stream iniziale in accordo ad opportuni Predicate, e infine, dell’operazione terminale la quale effettivamente agisce sui dati trasformando lo stream in ciò che il programmatore desidera. Dietro le quinte agisce, come detto, sempre il fork/join framework ma in una maniera velata al programmatore e in una versione stan-dardizzata e ottimizzata non più soggetta alle problematiche dello stesso. [27]
Analizziamo le principali novità nel dettaglio [28] [29]:
In prima istanza abbiamo le lambda expression forse la più stravolgente novità introdotta nel linguaggio nell’ultima decade, un linguaggio notoria-mente basato sul paradigma OO che ora vede affrontare le problematiche della programmazione funzionale. Una lambda expression altro non è che una funzione anonima la cui esecuzione non può mutare lo stato generale del programma. Ognuno di esse corrisponde ad un dato tipo, definito per mezzo di una cosiddetta “functional interface”. Questo è lo strumento che gli sviluppatori hanno scelto per rendere un rudimento della programma-zione funzionale comprensibile al sistema Java. Questa interfaccia deve contenere esattamente un metodo astratto la cui implementazione è defi-nita nella lambda expression cui ci riferiamo. Per quanto riguarda, invece, il loro scope esse possono far riferimento a variabili final o implicitamente fi-nal, oppure a variabili statiche dichiarate nel contesto superiore. Le lambda expression insieme alla Fluent Interface sono due strumenti fondamentali usati da Muskel 2 per gli skeleton che il framework ci mette a disposizione in una forma allettante.
Veniamo quindi allo Stream, definito come un potenzialmente infinito ana-logo di una lista di oggetti, ma maggiormente incline ad essere gestito in un ambiente concorrente (stream()) o parallelo (parallelStream()). La fu-sione fra Java Stream, Fluent Interface e Lambda Expression permette di definire in modo non ambiguo una concatenazione di un insieme di opera-zioni che verranno applicate a questo insieme “infinito” di oggetti in ma-niera sequenziale, concorrente o parallela, a seconda delle specifiche del
programmatore. Le operazioni si dividono in due categorie: le prime sono definite intermedie (o funzioni di aggregazione); Esse restituiscono ancora uno stream di elementi opportunamente editato e possono essere stateful (se la valutazione degli elementi dipende da valutazioni di operazioni pre-cedenti) o stateless. Possiamo concatenare quante operazioni intermedie desideriamo ad uno stream a patto che seguano una logica ben definita. In seconda istanza abbiamo le operazioni terminali che sfruttano le informa-zioni maturate nelle operainforma-zioni precedenti per fornire un risultato di un certo tipo, ogni catena può concludersi con un'unica operazione terminale. Anche i Java Stream introducono un comportamento atipico per Java, un linguaggio notoriamente alle prese con la eager evaluation; Questo perché la generazione e la computazione di uno stream avviene solo quando gli viene applicata l’operazione terminale, adottando al contrario la lazy
eva-luation. Ciò implica una differenza sostanziale: quando associamo una
fun-zione ad uno Stream, nell’ambito di un’operafun-zione intermedia, questo vie-ne trattato da Java 8 come un metodo ((Function<A,B>, Stream<A>) -> Stream<B->) i cui argomenti sono valutati immediatamente, ma ciò non accade per lo stream in output (nessuna iterazione occorre nell’applicazione della funzione agli elementi dello stream). In altre parole gli elementi dello stream non vengono iterati tutti ogni volta, per ogni ope-razione intermedia, ma una sola volta alla fine concatenando in maniera funzionale tutte le funzioni da qualche parte mantenute in attesa (Figura 3).
Figura 3 - Stream Lazy evaluation [30]
L’introduzione di una filosofia di programmazione funzionale siffatta può solo giovare alla causa parallela: in questo modo da una parte si
massimiz-za l’uso di variabili immutabili dall’altra si riducono gli eventuali punti di sincronizzazione nel codice rendendo la sua parallelizzazione più perfor-mante. E’ ovvio che ciò rappresenta un vantaggio o meno a seconda della categoria kernel in oggetto ma sicuramente l’ambiente funzionale è quello ottimale e meno complesso ove realizzare il parallelismo grazie alla
traspa-renza referenziale.
Tirando le somme, conviene usare gli stream quando possiamo trarre van-taggio dallo stile di programmazione funzionale, per migliorare le perfor-mance. Grazie ad essi possiamo collegare decine di funzioni prevenendo la loro computazione in ogni fase ma relegandola alla fine, sono utili per pa-rallelizzare task molto lenti, e grazie alla valutazioni lazy nemmeno stream particolarmente lunghi possono spaventare. Questo strumento va, invece, utilizzato con cautela per data-intensive task poiché per default tutti gli stream condividono la medesima ForkJoinPool configurata per usare tan-ti thread quantan-ti sono i processori nel calcolatore in uso. Se la valutazione di uno stream parallelo è molto lunga, a causa della natura del fork/join fra-mework sottostante, il task può essere diviso in vari sotto task che andran-no a impiegare i thread liberi all’interandran-no della pool, in questo modo se gli altri parallel stream dovessero averne bisogno troverebbero tutte le risorse occupate. Una soluzione non banale consiste nell’utilizzare più ForkJoin-Pool in questi casi specifici.
Un altro strumento importante, utilizzato ampiamente in Muskel 2, è la classe CompletableFuture. Essa rappresenta un’implementazione della classe Future grazie alla quale è possibile registrarsi come listener di even-ti asincroni, quindi eseguire pareven-ticolari procedure al loro completamento oppure gestire un eventuale stato di errore del Future, inoltre viene fornita anche la possibilità di decidere a quale threadpool attiva l’esecuzione di un simile compito vada affidato. Quindi parliamo di uno strumento molto po-tente soprattutto quando ci troviamo di fronte ad un sistema fortemente asincrono che è proprio quello che si vuole realizzare in Muskel 2.
Infine vengono introdotti molti strumenti utili per migliorare le operazioni di sincronizzazione come gli AtomicValue oppure nuove tipologie di
sema-fori. Tante altre feature sono state aggiunte al linguaggio, non qui citate poiché esulano dall’oggetto della tesi.
Ebbene quando sembra che Java sia riuscita ad incapsulare abbastanza bene i principali pattern paralleli e averli resi capaci di fruire su uno stream di elementi, ci accor-giamo che la versatilità e l’espressività fornita al programmatore per definire un’applicazione parallela e mascherare la propria complessità nonché le capacità struttu-rali di tali strumenti nel fondersi e formarne di nuovi, sono ancora limitati e non raggiun-gono gli standard del modello di programmazione parallela basata su skeleton [30]. Java infatti non riesce ancora a implementare appieno un simile modello di alto livello, in cui la gestione e la sincronizzazione delle attività parallele è implicitamente definita da
skele-ton. Il programmatore non deve più preoccuparsi degli aspetti legati alla sincronizzazione
o alla gestione di una thread pool come avveniva in passato ma solo nella scelta della poli-tica/pattern da applicare alla propria applicazione e poi nella rispettiva implementazione attraverso il corrispondente algorithmic skeleton. Tutto questo da una parte facilita la va-lutazione in termini di efficienza di un’applicazione parallela poiché ogni skeleton porta con sé un modello di costo strutturabile in combinazioni più complesse, dall’altra vengo-no vengo-notevolmente ridotti gli errori di programmazione rispetto ai tradizionali modelli di programmazione parallela a basso/medio livello [31]. Da sottolineare ancora una volta la proprietà strutturale degli skeleton per mezzo della quale viene data la possibilità al pro-grammatore di realizzare, in accordo a politiche di composizione ben definite, skeleton sempre più complessi: lacuna ancora debolmente colmata in Java 8.
Muskel 2, così come tanti altri framework, serve proprio a colmare questo gap fra la computazione parallela definita in Java e quella che possiamo definire “orientata agli skeleton”, senza però ignorare le innovazioni introdotte da questo linguaggio di pro-grammazione nel campo parallelo negli ultimi anni come faceva Muskel. Con l’apporto di una simile libreria, Java diventa così uno strumento maggiormente adatto a sviluppare applicativi paralleli grazie alla possibilità offerta al programmatore di incapsulare facil-mente le porzioni di codice da eseguire parallelafacil-mente, sfruttare la maggior parte dei pa-rallel design pattern più comuni, oppure creare dei nuovi skeleton compositions che ven-gano maggiormente incontro alle esigenze atipiche della propria applicazione.
2.5 Muskel 2 – Basi
Muskel 2 è un framework Java che consente di implementare applicazioni
le attraverso una programmazione “orientata a skeleton” in maniera sequenziale, paralle- paralle-la e distribuita. Le caratteristiche fondamentali su cui fonda il proprio funzionamento so-no le seguenti:
Come anticipato sfrutta tutte le nuove potenzialità di Java quali le Lambda Expression, la Fluent Interface e i Java Stream, dei quali si è già ampiamen-te discusso nei paragrafi precedenti, introducendo loro ulampiamen-teriori migliorie come la possibilità di configurare la pool associata ad ogni stream.
L’implementazione adottata per gli algorithmic skeleton è la macro data
flow implementation dando la possibilità al programmatore di realizzare
programmi data-flow asincroni.
Si propone di realizzare un tipo di programmazione definita “reattiva”, che supera le limitazioni di Java per giungere in un sistema: responsivo, ossia in grado di fornire una risposta agli input quanto più rapida possibile,
resilien-te, nel senso che il sistema è responsivo anche in caso di guasti, elastico
os-sia il sistema mantiene degli standard costanti al variare del carico di lavoro e message-driven dove ogni forma di comunicazione fra diverse sezioni del-lo stesso avviene attraverso messaggi asincroni [32].
Il framework cerca di ricalcare la filosofia del Functional Reactive
Pro-gramming ossia si fonda sull’utilizzo di stream di dati per modellare eventi
continui ai quali è possibile applicare varie funzioni di trasformazioni, in li-nea al modus-operandi di Java Stream, adottando tecniche però della pro-grammazione funzionale. Ma questo non è tutto, siccome, puntiamo alla realizzazione di applicazioni reattive, la concatenazione e l’esecuzione di queste trasformazioni devono poter essere gestite in maniera asincrona: ed è proprio quello che viene fatto mediante l’utilizzo dei seguenti stru-menti:
o La classe CompletableFuture introdotta in Java8 e di cui abbiamo già avuto modo di discutere;
o RxJava ossia una libreria appositamente costruita per la composi-zione di eventi asincroni usando sequenze di Observable. I mecca-nismi di questa libreria sono stati presi come modello nella realizza-zione di Muskel 2 proprio perché consente di modellare un proble-ma come avviene con i Java Stream, con funzioni di trasforproble-mazione, aggregazione e filtraggio, tuttavia, in più, è in grado di processare in modo asincrono i vari stati della computazione.
o Reactive Stream: con questo termine intendiamo un iniziativa, in-trapresa da vari ricercatori, di fornire uno standard per l’elaborazione di una sequenza di trasformazioni asincrone e non bloccanti a partire da uno stream di dati, esattamente ciò cui il fra-mework sta puntando. In questa standardizzazione non rientrano specifiche tecniche nella programmazione delle varie funzioni di manipolazione bensì vengono definite le entità, che in qualche mo-do si vengono a creare. Un flusso data-flow asincrono che da una sorgente di dati, attraverso una serie di trasformazioni asincrone, giunge all’output richiesto dall’utente diventa così un continuo scambio fra due entità fondamentali: il Publisher il quale genera un continuo di dati (fornitore di un servizio) sotto richiesta esplicita del
Subscriber (utente del servizio). Immaginiamo un codice siffatto: 1. MuskelProcessor.from(1, 2, 3, 4, 5, 6)
2. .map(i -> "Hello World " + i)
3. .toList()
4. .subscribe(s -> System.out.println(s));
Codice 1 - Uso del publisher e subscriber
Nello specifico il codice genera uno stream di stringhe che vengono scritte a video in maniera asincrona grazie all’operatore map() il quale può eseguire la medesima funzione sullo stream entrante in una maniera parallela. Ogni funzione, nella catena data-flow, è un operatore che rappresenta un Subscriber nei confronti di quello
precedente ed un Publisher per il successivo. In questo modo, senza addentrarci troppo negli aspetti tecnici, un oggetto iniziale viaggia lungo le varie entità, che vi applicheranno ogni volta una certa fun-zione di trasformafun-zione, fino ad arrivare all’operatore di termina-zione. Ovviamente per evitare l’insorgenza di errori, il tipo di dato restituito dall’operatore precedente nella catena, deve essere lo stesso di quello entrante nell’operatore successivo.
Infine il supporto all’esecuzione distribuita viene fornito dalla libreria
Hazelcast:
o Essa sfrutta il pattern client/server dove la computazione nasce da un nodo (client) il quale potrà sfruttare, nella smistamento delle proprie attività parallele, thread pool residenti su altri nodi remoti. La totalità dei nodi interconnessi sulla rete sui quali verrà eseguita la computazione parallela viene definita cluster. Un cluster in Mu-skel 2 può contenere anche nodi residenti su reti differenti, cosa che non era consentita in Hazelcast.
o L’inizializzazione di un cluster avviene attraverso un insieme di pas-saggi fondamentali: 1) innanzitutto ciascun nodo server viene inizia-lizzato attraverso l’esecuzione di un opportuna command line diret-tamente da terminale; tale inizializzazione è configurabile dal pro-grammatore sotto vari punti di vista (Tabella 1 mostra i parametri che possiamo utilizzare). Fondamentale è l’inserimento delle cre-denziali le quali devono essere comuni a tutti i nodi dello stesso clu-ster. 2) a questo punto abbiamo una fase di discovery fra i nodi ser-ver avviati affinché possano interconnettersi correttamente gli uni con gli altri. Tale fase può avvenire in due modi differenti: attraver-so un indirizzo di multicast comune fornito come parametro di con-figurazione all’atto di avvio di ciascun nodo (metodo usato come default ma all’atto pratico non molto utile essendo valido solo se tutti i nodi remoti vivono nella stessa rete), oppure utilizzando di-rettamente l’indirizzo TCP/IP del/dei nodo/i al quale vogliamo inter-connetterci, sempre fornito come parametro di configurazione. 3)
una volta che i nodi server si conoscono vicendevolmente, ognuno ha gli indirizzi TCP/IP degli altri, il client può collegarsi all’indirizzo TCP/IP di uno qualunque di essi ottenendo successivamente la tota-lità dei riferimenti ai nodi del cluster, che a questo punto può dirsi attivo.
o La comunicazione tra i nodi così instauratasi, si basa sul protocollo
Hazelcast Open Binary Client Protocol. Esso definisce sia per la fase
di discovery che per ogni altra forma di comunicazione formato e tipologia dei messaggi scambiati.
o Tutto ciò viene implementato in Muskel 2 nell’interfaccia Hazelca-stMuskelContext usando alla base i rudimenti della libreria Hazel-cast. Fra le principali attività ricordiamo il discovery dei nodi appar-tenenti al cluster, il class loading ovvero un servizio client che può essere richiamato da qualunque dei nodi server per il recupero del-le classi usate nel task da eseguire, executor service che fornisce il supporto a run-time per l’effettiva esecuzione dei task lato server, inoltre permette di inoltrare all’occorrenza tali task in altri nodi re-moti appartenenti allo stesso gruppo di quello corrente (la defini-zione dei gruppi di lavoro è ancora una volta delegata al program-matore attraverso un corretto utilizzo dei parametri di configura-zione usati per avviare un server), infine la gestione dei processi di serializzazione necessari per inviare in maniera compatta e sicura un messaggio, task, o funzione dal client al server.
Tabella 1 - Parametri di configurazione nodo server
Comando Descrizione Default
name Username da utilizzare per l'autenticazione dei client e server muskel
Comando Descrizione Default
portNumber Numero porta da aprire per la ricezione delle connessioni in ingresso 5701
portAutoIncrement Se true il sistema cerca un nuova porta nel caso fosse già in uso true
groups Lista separata da , dei nomi di gruppi ai quali il server aderisce
discoveryMulticastGroup Il nome del gruppo di multicast utilizzato per la ricerca degli altri nodi server 224.2.2.3
discoveryMulticastPort Il numero di porta del gruppo di multicast utilizza-to per la ricerca degli altri nodi server 54327
discoveryTcpMembers
In alternativa al multicast è possibile configurare direttamente gli indirizzi i tcp ai quali il nodo deve
collegarsi. Esempio host1 (in questo caso il nodo tenterà l'accesso a host1 dalla porta 5701 fino alla
5801), host1:7895, 192.168.1.0-9 (range di ip ad-dress)
logging.path E' il path dove scrivere il file di log spring.log /tmp
localexecutors
E' possibile definire i nomi dei thread pool locali e il loro pool size. Il formato è nome:poolsize
oppu-re nome (in questo caso poppu-rende il pool size della macchina). E' possibile definire più threadpool
lo-cali che devono essere separati da ,
local:Numero Thread
clientPoolSize E' il numero massimo di Thread, per client, che il server rende disponibili 16
sslEnabled
Se true abilita la comunicazione ssl tra i nodi e i client. Se abilitato è necessario configurare anche
le properties contenute nell'esempio
networkInterfaces
La lista delle interfacce di rete, separata da virgola, su cui aprire la porta del server e dove effettuare il
discovery dei nodi. Esempi di utilizzo: 172.16.33.205, 172.*.*.*
2.6 Muskel 2 – Interfacce
Prima di esporre i principali skeleton implementati da Muskel 2 e usati nella risolu-zione delle nostre applicazioni, vediamo brevemente le API con cui la libreria mette a di-sposizione le sue funzionalità all’utente:
Classe MuskelProcessor: questa classe emula i Java Stream poiché per-mette di gestire una sequenza di oggetti provenienti da una sorgente che può essere una lista oppure un range generator, quindi consente di appli-carvi da zero a più operazioni intermedie connesse attraverso una pipeline fino a giungere ad un operazione terminale, in modo seriale o parallela. Attraverso una serie di factory la classe permette di interfacciarsi con una vasta gamma di sorgenti dati fra cui oggetti Stream<T>, Iterable<T>, Pu-blisher<T> e così via. L’avanzare della computazione fra gli operatori con-tenuti nella pipeline della nostra istanza MuskelProcessor avviene median-te il patmedian-tern Publisher-Subscriber. Analizziamone in breve le dinamiche poiché sarà utilizzato come generatore di stream in molti applicativi. In pratica ogni operatore che interviene nella pipe rappresenta un Subscriber (ente che consuma un oggetto) nei confronti di quello precedente e un
Pu-blisher (ente che produce un oggetto) per quello successivo (lo stream
ini-ziale può essere generato anche da un Publisher personalizzato dall’utente come avverrà in molti applicativi). Possiamo distinguere varie fasi:
o La fase di inizializzazione: l’operatore terminale, avendo noto il proprio Publisher p, invoca il metodo p.subscribe(Subscriber s), generando una sequenza di chiamate a cascata che permettono ad ogni stadio di avere il riferimento nei confronti del successivo Subscriber. Fatto ciò avviene il procedimento a cascata inverso: una volta che il Publisher sorgente dispone del riferimento al proprio Subscriber s, invoca su di esso, in maniera asincrona il metodo s.onSubscribe (Subscription c), invocazione che continua
fi-no all’operatore terminale e che permette a ciascufi-no stadio di di-sporre dell’oggetto Subscription. Quest’ultimo possiede l’insieme dei metodi con cui il Subscriber può richiedere elementi da proces-sare al Publisher.
Figura 4 - Pattern Publisher-Subscriber
o La fase di comunicazione: in questa fase ogni stadio può richiedere elementi dello stream da consumare attraverso il metodo c.request(n), dove n rappresenta il numero degli elementi richie-sti al momento (n viene posto a Long.MAX_VALUE dal Subscriber
quando non conosce a priori il numero di elementi di cui ha bisogno oppure li desidera tutti). Tale richiesta viaggia a ritroso lungo gli operatori disponibili fino a giungere al Publisher sorgente che emet-te gli elementi richiesti tramiemet-te i metodi esposti dal Subscriber (s) richiedente: s.onNext(T t) per segnalare la presenza di un nuovo elemento da processare, s.onError(Throwable t) per notificare un errore oppure s.onComplete() per segnalare la fine dello stream in ingresso. Tutto ciò reiterato sull’intera pipe genera quel flusso di informazioni sulla cui base applichiamo la logica di compu-tazione definita. (Una visione più chiara del procedimento si ottiene analizzando la Figura 4 - Informazioni sull’argomento sono state re-perite in [33]).
Classe MuskelContext: questa classe è strettamente collegata con la pre-cedente poiché essa consente al programmatore di definire il contesto su cui un istanza MuskelProcessor (o più istanze) andrà a lavorare. Con con-testo intendiamo l’ambiente locale o remoto su cui verterà la computazio-ne, ma non solo. Essa consente di configurare in profondità un simile am-biente attraverso un certo numero di parametri. In ambito locale ad esem-pio il programmatore potrà inizializzare nuovi thread pool o usare solo quello di default, definirne il thread size e così via, in ambito remoto invece l’istanza MuskelContext è ancora più importante poiché qui inseriremo i parametri necessari alla connessione al cluster, come indirizzo TCP/IP e le credenziali di accesso. Una simile istanza verrà associata ad un’istanza Mu-skelProcessor per mezzo della funzione withContext().
Come ultima componente abbiamo gli operatori (Tabella 2Errore. L'origine riferimento non è stata trovata.) che possono avvicendarsi nella pipeline
di un istanza MuskelProcessor e da cui dipende la logica e la strategia adottata nella risoluzione di un problema. Quest’ultimi non sono altro che gli skeleton messi a disposizione dalla libreria. Ognuno di essi, a fronte di un contesto ibrido, può generare attività parallele da eseguire localmente o da trasferire sui nodi remoti. Per questo motivo gli operatori paralleli si distinguono da quelli seriali per l’aggiunta di un ulteriore argomento in
