Exploring architectural support for applications with irregular memory patterns on distributed manycore systems

With computing systems becoming ubiquitous, numerous data sets of extremely large size are becoming available for analysis. Often the data collected have complex, graph based structures, which makes them difficult to process with traditional tools. Moreover, the irregularities in the datasets, and in the analysis algorithms, hamper the scaling of performance in large distributed high-performance computing (HPC) systems, optimized for locality exploitation and regular data structures. The aim of the PhD research has been proposing an approach to system design that enable efficient execution of applications with irregular memory patterns on a distribute, many-core architecture, based on off-the-shelf cores. A secondary goal for the architecture design has been simplifying the programming using a simple Shared Memory model. The four key elements of the proposed architecture are: (1) a global address space that allows the use of simple programming models, (2) prevention of dynamic formation of hotspots, (3) latency tolerance through lightweight multitheading and finally (4) fine-grained synchronization. The feasibility and effectiveness of the approach has been evaluated with a prototype implemented with 4 FPGAs, which uses off-the-shelf cores and communication subsystem, with the addition of a set of custom-designed components. These components offer the fore-mentioned four capabilities with a minimal impact on the chip architecture. In spite of the small size of the prototype, the performance scaling of typical irregular kernels proved the effectiveness of the approach. In addition, the FPGA prototype allowed to evaluate the technical issues related to the implementation of the proposed architecture, suggesting the technical details required for supporting other commodity processors, like Intel o ARM cores. The performance data obtained from the prototype have also be used to formulate an analytical model, which identify the system bottlenecks and can be used for dimensioning a large scale distributed system. The research has moved on with the creation of a lightweight system simulator, in order to evaluate additional features using high level performance models instead of a full HDL implementation. The simulator neglects modelling the details of cache and memory hierarchy, which are irrelevant for applications which lack data locality, thus improving the simulation speed. On the other hand, it models the extended memory behaviour and the fine-grained locking routines introduced by the custom hardware components. The simulator allowed to evaluate the impact of additional architectural features, such as the support for atomic operations on the global address space. The use of remote atomic operations, in place of lock routines, allowed to significantly reduce the synchronization overhead and exposed larger amounts of parallelism enhancing the effectiveness of the many-core system.

Grazie all'estrema diffusione odierna di dispositivi elettronici, una quantità enorme di dati diventando disponibile per analisi automatiche. Spesso questi set di dati hanno strutture complesse, basate su grafi od alberi, molto diverse dalle tabelle usate dai database relazionali. Ciò rende difficile la loro analisi con strumenti tradizionali. In aggiunta, le irregolarità nei dataset e negli algoritmi di analisi ostacola la scalabilità nell'utilizzo di sistemi distribuiti di calcolo ad alte prestazioni (HPC), i quali sono ottimizzati per sfruttare località degli accessi e regolarità nelle strutture dati. Lo scopo della ricerca di dottorato è stato proporre un approccio alla progettazione di architetture di calcolatore che permetta una esecuzione efficiente di applicazioni con pattern di memoria irregolari su architetture many-core distribuite, e basate su componenti disponibili in larga scala sul mercato. Un ulteriore obiettivo tenuto in considerazione è stato la semplificazione del modello di programmazione, applicando il semplice modello a memoria condivisa al sistema distribuito. I quattro elementi principali dell'architettura proposta sono: (1) uno spazio di indirizzi globale, che permette l'uso di modelli di programmazione semplici, (2) la riduzione della formazione dinamica di punti caldi (hotspots) nel sistema, (3) la copertura delle latenze di memoria grazie all'uso di multithreading con basso overhead, e (4) primitive di sincronizzazione a grana fine, parzialmente supportate in hardware. La fattibilità ed efficacia dell'approccio sono state valutate realizzando un prototipo su FPGA, il quale usa dei processori ed un sistema di comunicazione pre-esistenti e largamente utilizzati, ai quali aggiunge un set di componenti appositamente progettati. Questi componenti offrono le quattro funzionalità sopra menzionate con un impatto minimo sull'architettura on-chip. Nonostante la piccola dimensione del prototipo (4 nodi), la scalabilità delle prestazioni di tipici algoritmi irregolari prova l'efficacia dell'approccio. In aggiunta, il prototipo ha permesso di valutare le difficoltà incontrabili nell'implementazione dell'architettura proposta, suggerendo dettagli tecnici richiesti per supportare altri processori commerciali, come Intel o ARM. I dati di prestazione ottenuti dal prototipo sono stati usati anche per formulare un modello analitico, il quale permette di identificare i colli di bottiglia e dimensionare il sistema. La ricerca ha proseguito con lo sviluppo di un simulatore di sistema per valutare l'inserimento di funzionalità aggiuntive, usando modelli di prestazione ad alto livello invece della più costosa implementazione in linguaggi HDL. Il simulatore ignora dettagli architetturali come la gerarchia di cache e memoria, irrilevanti per applicazioni che mancano di località negli accessi, permettendo quindi di ottenere una maggiore velocità di simulazione. Al loro posto il simulatore modella il comportamento esteso dei modelli di memoria e multi-threading, e le routine di locking a grana fine introdotte dai componenti aggiuntivi. Il simulatore ha permesso di valutare l'impatto di funzionalità aggiuntive, come il supporto per operazioni atomiche sullo spazio di indirizzi globale. La sostituzione delle routine di lock con operazioni atomiche, ha ridotto significativamente il costo della sincronizzazione ed ha esposto un maggiore parallelismo negli algoritmi, aumentando l'efficacia della architettura many-core proposta.