Harnessing adaptivity analysis for the automatic design of efficient embedded and HPC systems

Embedded Systems (ESs) and High-Performance Computing (HPC) systems belong to two distinct areas of the Information Technology (IT). On one side, embedded systems are usually designed as hardware implementation of a specific functionality, with the aim of either reducing power consumption, or accelerating the most frequently executed portion of an application. On the other side, high-performance computing systems are designed as massively parallel supercomputers with tens of thousands of processors, usually employed to solve complex, highly parallel scientific problems. Due to the distinct nature of the two domains, these systems have historically evolved following different trends. However, many issues and design challenges are lately arising, which affect both the domains. Among the examples, increasing computational demands and large parallelism degrees, together with the growing capabilities of silicon technology, led to the design of increasingly complex architectures and applications. As a consequence, modern embedded systems exploit the potentialities of hundreds or thousands of processing units, often heterogeneous and physically distributed, which run in parallel on the many-core platform. These same factors led to massively parallel systems in HPC domain. As another example, power constraints, which have always been a critical requirement for embedded systems design, are becoming more and more relevant also in the high-performance domain. As a consequence, communication minimization techniques are required also for modern HPC systems design. This trend suggests that HPC systems design techniques can be exploited, at a different abstraction level, by embedded systems designers to address shared issues, and vice versa. In other words, designing modern supercomputers, as well as modern embedded systems, requires a holistic approach that relies on tightly coupled hardware-software co-design methodologies. Among the numerous issues which are shared between the ES and the HPC domains, this thesis focuses on unknown, uncertain and unpredictable behaviors. Modern computing systems have to deal with this kind of behaviors, which are often related to incomplete information at design/compiler time. Unknown, uncertain and unpredictable information can be originated by different sources. For example, the interaction with external modules (e.g., sensors, IPs, memories) generates variable and possibly unpredictable communication latency. Moreover, the nature of high-level applications is inherent uncertain (e.g., unknown number of loop iterations, unknown values of the incoming arguments of a function, unknown outcome of conditional instructions evaluation, or unpredictable memory accesses). Incomplete information at design or compile time often leads to suboptimal designs: to prevent the system from a failure, the designer must either consider all the possible scenarios, with consequent increase in area and complexity of the circuit, or take a conservative approach, with consequent decrease in performance. Moreover, this approach is error prone, since the correctness cannot be guaranteed in all the situations (such as run-time events which the designer cannot predict, or technology parameters which change unpredictably during the life cycle of the device, for example due to component degradation). In this scenario, systems able to dynamically adjust their behavior at run-time appear to be good candidates for the next computing generation in both the domains. This work aims at defining efficient design methodologies for modern embedded systems and high-performance computing systems, able to deal with unknown, uncertain and unpredictable behaviors. For such purpose, this thesis introduces the concept of Adaptivity Analysis, which provides a formal approach to study the adaptivity properties of the applications. Given the different scale of the problem in the ESs and HPCs domain, Adaptivity Analysis is defined at two distinct abstraction levels. In the embedded systems domain, Adaptivity Analysis addresses the problem of designing efficient adaptive hardware cores. More in detail, this analysis identifies, at design-time, the conditions that each instruction (or group of instructions) must satisfy to execute, according to their dependences. Such conditions, called Activating Conditions (ACs), are logic formulas. Since unknown information may occur at design-time, the ACs provide parametric results, which depend on conditions that will be resolved at run-time (e.g., outcome of the evaluation of a conditional instruction). At run-time, as soon as the unknown information is resolved, the ACs are evaluated. Once an AC is satisfied, the corresponding instruction can safely execute, thus providing an explicit activation mechanism for the instruction, which allows their dynamic auto-scheduling. Such a scheduling technique, called dynamic AC-scheduling, provides support for the High-Level Synthesis (HLS) of adaptive hardware cores. Moreover, this thesis defines a prototype for this kind of system. Furthermore, this work defines a proper Intermediate Representation (IR), called Extended Program Dependence Graph (EPDG), able to provide a parallel execution model for adaptive hardware cores. Finally, the dynamic AC-scheduling has been implemented as part of the PandA framework, thus providing a fully automated design methodology. In the HPC domain, Adaptivity Analysis is used as automatic compiler-based generation of parallel irregular applications. In HPC design, run-time systems are entitled for managing unknown, uncertain and unpredictable behaviors. Hence, adaptivity analysis is used in this context as a compiler technique for the support of run-time systems. More in detail, this work focuses on the automatic parallelization of a particular class of applications, known as Irregular Applications. Due to their irregular nature (i.e., irregular data structures, irregular control flow, irregular accesses to the communication network), the parallelization of irregular applications is significantly challenging. This thesis introduces the Yet Another Parallel Programming Approach (YAPPA) compilation framework. YAPPA aims at efficiently parallelizing irregular applications running on commodity clusters. The novel parallel programming approach supported by YAPPA is defined by the underlying run-time library, called Global Threading and Memory (GMT). GMT cross combines different parallel programming approaches, which are usually exploited separately in the literature: it integrates Global Address Space (GAS) across cluster nodes, lightweight multithreading for tolerating memory and network latencies, and support for a fork/join programming model. YAPPA extends the LLVM compiler with a set of transformations and optimizations, which at first instrument the sequential code to run GMT primitives (parallelization phase), and then apply a novel set of transformations to improve the efficiency of the generated parallel code (optimization phase).

Embedded Systems (ESs) e High-Performance Computing (HPC) systems appartengono a due aree distinte dell’Information Technology (IT). Da un lato, i sistemi embedded sono di solito progettati come implementazioni hardware di funzionalità specifiche, con lo scopo di ridurre il consumo di potenza, o di accelerare l’esecuzione delle porzioni di codice che vengono eseguite più di frequente. Dall’altro lato, i sistemi high-performance computing sono progettati come supercomputer massicciamente paralleli, con decine di migliaia di processori, e vengono di solito impiegati per risolvere problemi scientifici complessi ed altamente paralleli. Per via della diversa natura dei due domini, l’evoluzione di questi sistemi ha storicamente seguito strade divergenti. Ultimamente, tuttavia, un numero sempre più consistente di problematiche sta interessando entrambi i domini. Tra gli esempi, la crescente domanda di potenza computazionale, assieme ai miglioramenti nella tecnologia del silicio, hanno portato allo sviluppo di architetture ed applicazioni sempre più complesse. Di conseguenza, i sistemi embedded moderni sfruttano le potenzialità di migliaia di unità di elaborazione, spesso eterogenee e fisicamente distribuite, che lavorano in parallelo sulla piattaforma many-core. Questi stessi fattori hanno portato allo sviluppo di sistemi altamente paralleli nel dominio HPC. I vincoli di potenza sono un altro esempio di problematiche comuni. Da sempre un requisito stretto per la progettazione di sistemi embedded, i vincoli di potenza stanno diventando sempre più rilevanti anche nel dominio HPC. Di conseguenza, la progettazione dei sistemi HPC di oggi richiede tecniche di minimizzazione della comunicazione. Questa tendenza suggerisce che le tecniche di progetto tipiche dei sistemi high-performance computing possano essere sfruttate, ad un diverso livello di astrazione, per il progetto di sistemi embedded, e viceversa. In altre parole, la progettazione dei supercomputer moderni, così come quella dei sistemi embedded moderni, richiede un approccio olistico basato su metodologie di co-design hardware-software strettamente accoppiate. Tra i numerosi problemi condivisi dai domini ES e HPC, questa tesi si concentra su comportamenti incogniti, incerti e imprevedibili. Le architetture di oggi devono fare i conti con questo tipo di comportamenti, che spesso sono legati alla presenza di informazione incompleta a design/compile time. Informazione incognita, incerta o imprevedibile può essere originata da diverse fonti. Per esempio, l’interazione con moduli esterni (es., sensori, IPs, memorie) genera latenza di comunicazione variabile e potenzialmente imprevedibile. Inoltre, le applicazioni scritte in linguaggi ad alto livello hanno natura intrinsecamente incerta (es., numero incerto di iterazioni di un loop, valore incognito dei parametri di ingresso di una funzione, risultato incognito della valutazione di una istruzione condizionale, o accessi a memoria impredicibili). La presenza di informazioni incomplete a design o compile time comporta risultati subottimi: per prevenire errori, il progettista deve considerare tutti i possibili scenari, con conseguente aumento in area e complessità del circuito. Alterna- tivamente, è possibile considerare l’approccio conservativo, con conseguente perdita in performance. Oltretutto, questo approccio è soggetto ad errori, in quanto la correttezza del design prodotto non può essere garantita in tutte le situazioni (es., eventi dinamici che il progettista non può prevedere, o cambiamenti nei valori dei parametri tecnologici durante il ciclo di vita del dispositivo, ad esempio a causa di degradazione dei componenti). In questo scenario, i sistemi che sono in grado di adattare dinamicamente il proprio comportamento a run time sembrano essere buoni candidati per la prossima generazione computazionale in entrambi i domini. Questo lavoro mira a definire metodologie di progetto efficienti per sistemi embedded e high-performance computing moderni, capaci di gestire comportamenti incogniti, incerti e imprevedibili. A tal proposito, questa tesi introduce il concetto di Adaptivity Analysis, la quale fornisce un approccio formale per lo studio delle proprietà adattative delle applicazioni. Data la diversa scala del problema nei due domini, l’Adaptivity Analysis è definita a due diversi livelli di astrazione. Nel dominio dei sistemi embedded, la tecnica di Adaptivity Analysis affronta il problema della progettazione efficiente di hardware core adattativi. Più in dettaglio, questa analisi identifica, a design time, le condizioni che ciascuna istruzione (o gruppo di istruzioni) deve soddisfare per poter essere eseguita, a seconda delle sue dipendenze. Queste condizioni, chiamate Acti- vating Conditions (ACs), sono formule logiche. Dato che alcune informazioni a design time possono essere incognite, le AC forniscono risultati parametrici, dipendenti da condizioni che saranno note a run time (es., risultato della valutazione di una istruzione condizionale). A run time, non appena le informazioni incognite diventano note, le AC vengono valutate. Quando una AC è soddisfatta, l’istruzione ad essa associata può essere eseguita in modo sicuro, fornendo quindi un meccanismo di attivazione esplicito delle istruzioni, che permette il loro auto-scheduling dinamico. Questa tecnica di scheduling, chiamata dynamic AC-scheduling, rappresenta il supporto per la sintesi ad alto livello di hardware core adattativi. Inoltre, questa tesi definisce un prototipo per questo tipo di sistemi. Oltretutto, questo lavoro definisce una rappresentazione intermedia opportuna, chiamata Extended Program Dependence Graph (EPDG), capace di fornire un modello di esecuzione parallelo per hardware core adattativi. Infine, la tecnica di dynamic AC-scheduling è stata implementata come parte del framework PandA, quindi fornendo una metodologia di progetto interamente automatizzata. Nel dominio HPC, la tecnica di Adaptivity Analysis viene usata per la generazione automatica di codice parallelo basata su compiletore, per applicazioni irregolari. Nell’ambito HPC, i sistemi run time sono intitolati per la gestione di comportamenti incogniti, incerti e imprevedibili. Quindi, l’Adaptivity Anal- ysis è usata in questo contesto come tecnica di compilazione per il supporto di sistemi run time. In particolare, questo lavoro si concentra sulla parallelizzazione automatica di una specifica classe di applicazioni, note come applicazioni irregolari. Per via della loro natura irregolare (es., strutture dati irregolari, flusso di controllo irregolare, accessi irregoalri alla rete di comunicazione), la parallelizzazione di applicazioni irregoari risulta particolarmente complessa. Questa tesi introduce il framework di compilazione Yet Another Parallel Programming Approach (YAPPA). YAPPA mira a parallelizzare ef- ficientemente applicazioni irregolari su commodity cluster. L’innovativo approccio di programmazione parallela supportato da YAPPA è definito dalla sottostante libreria di run time, chiamata Global Threading and Memory (GMT). GMT combina differenti approcci di programmazione parallela, che sono di solito utilizzati separatamente in letteratura: integra Global Address Space (GAS) sui nodi del cluster, lightweight multithreading per tollerare latenze di memoria e di rete, e supporto per un modello di programmazione fork/join. YAPPA estende il compilatore LLVM con una serie di trasformazioni e ottimizzazioni, che innanzitutto instrumentano il codice sequenziale in modo da supportare primitive GMT (fase di parallelizzazione), e poi applicano un insieme di nuove trasformazioni per migliorare l’efficienza del codice parallelo generato (fase di ottimizzazione).