Improving synchronization and data access in parallel programming models

Today, parallel architectures are the main vector for exploiting available die area. The shift from architectures tuned for sequential programming models to ones optimized for parallel processing follows from the inability of further enhance sequential performance due to power and memory walls. On the other hand, efficient exploitation of parallel computing units looks a hard task. Indeed, to get performance improvements it is necessary to carefully tune applications, as proven by years of High Performance Computing using MPI. To lower the burden of parallel programming, parallel programming models expose a simplified view of the hardware, by relying on abstract parallel constructs, such as parallel loops or tasks. Mapping of those constructs on parallel processing units is achieved by a mix of optimizing compilers and run-time techniques. However, due to the availability of an huge number of very different parallel architectures, hiding low-level details often prevents performance to be comparable with the one of hand-tuned code. This dissertation aims at analyzing inefficiencies related to the usage of parallel computing units, and to optimize them from the runtime perspective. In particular, we analyze the optimization of reduction computations when performed together with barrier synchronizations. Moreover, we show how runtime techniques can exploit affinity between data and computations to limit as much as possible the performance penalty hidden in NUMA architectures, both in the OpenMP and MapReduce settings. We then observe how a lightweight JIT compilation approach could enable better exploitation of parallel architectures, and lastly we analyze the resilience to faults induction of synchronization primitives, a basic building block of all parallel programs.

Oggigiorno le architetture parallele sono il principale mezzo utilizzato per sfruttare il crescente numero di transitori disponibili all'interno dei circuiti integrati. Il cambiamento epocale da architetture ottimizzate per l'esecuzione di programmi sequenziali ad architetture pensate per l'esecuzione di codice parallelo è da imputare alla non sostenibilità delle crescenti richieste di potenza elettrica e dall'inabilità del sottosistema di accesso alla memoria di fornire dati al ritmo richiesto dall'unità di esecuzione centrale. D'altronde, l'utilizzo efficiente di multiple unità di esecuzione parallele non è un compito banale. Infatti, per ottenere dei guadagni prestazionali è spesso necessario ottimizzare attentamente le applicazioni, come dimostrato da anni nel campo del calcolo ad alte prestazioni. Per mascherare tutta questa complessità, i modelli di programmazione parallela espongono una visione semplificata dell'architettura. Invece di mostrare tutte le singole unità parallele, essi si avvalgono di costrutti di alto livello, come ad esempio i cicli paralleli. La traduzione di questi concetti sulle unità di esecuzione parallele è attuato tramite una combinazione di compilatori ottimizzanti e librerie di supporto progettate per guidare l'esecuzione del programma. Tuttavia, data la disponibilità di un grande e variegato numero di architetture parallele, mascherare i dettagli di basso livello spesso limita le prestazioni, che quindi non sono comparabili con quelle ottenibili attraverso una ottimizzazione manuale. Lo scopo ti questa tesi è analizzare le inefficienze legate all'utilizzo di unità di esecuzione parallele, ed ottimizzarle tramite tecniche da applicare durante l'esecuzione del programma. In particolare si analizza ed ottimizza, l'esecuzione di riduzioni contestualmente ad una operazione di sincronizzazione tramite barriere. Dopodiché, si mostra come l'utilizzo di tecniche dinamiche permette di sfruttare l'affinità tra dati e computazioni per limitare il più possibile la penalità di accesso alla memoria nel contesto di architetture NUMA, dal punto di vista di due modelli di programmazione parallela: OpenMP e MapReduce. Segue quindi una proposta di utilizzo di tecniche leggere di compilazione dinamica per massimizzare l'utilizzo delle architetture parallele, ed infine si analizza la robustezza ai guasti delle primitive di sincronizzazione primitivi, un meccanismo fondamentale utilizzato da ogni programma parallelo.