On space constrained computations

Since the advent of the digital computer, its supporting technology has been characterized by steady and impressive growth. Although most parameters are still being improved, there is an emerging consensus that physical limitations to signal propagation speed and device size are becoming increasingly significant. Ultimately, the access time to the memory associated to a digital computer is bound to increase with the size of the memory. Therefore, when a large overall memory is required, it becomes convenient to organize it hierarchically into a sequence of levels whose size and access time increase progressively. Typically, the levels of memory hierarchy include the CPU registers, two or three cache levels, main memory and disks. Compared to the CPU registers, main memory is a few hundred times slower and disks are a few million times slower, hence, effective use of the fastest levels of the memory hierarchy is becoming a key concern in the design and implementation of algorithms. Physical limitations are a concern also in the context of multiprocessor architectures and parallel computing, due to the delay introduced by the speed of the signals used for the communication between the various processing units. Furthermore, while Moore's Law predicts an exponential speedup of hardware in general, the annual improvement rate of time per-arithmetic-operation has, over the years, consistently exceeded that of time-per-word read/write. The fraction of running time spent on communication is thus expected to increase further, becoming more and more of a bottleneck for the performance of both multi-level memory and parallel computing architectures. When considering the complexity of algorithms, two kinds of costs are therefore to be considered: the arithmetic cost which depends on the number of required computational steps, and the communication cost which depends on the required movement of data within the execution of an algorithm, either between levels of a memory hierarchy (in the sequential case), or over a network connecting processors (in the parallel case). In both of these applicative scenarios, the communication component of an algorithm often costs significantly more time than its arithmetic component. It is therefore of interest to investigate the minimum memory space required for computation of algorithms on the one hand (the space complexity), and then the tradeoff between the memory space actually being used and the data communication needed for the algorithm execution (the I/O complexity). In addition to a purely theoretic interest of such an analysis, the pursuit of good lower bounds techniques is also crucial for the pursuit of high performances algorithms, since they enable to evaluate the distance from optimality of a proposed solution. In our study we focus on computations done with straight-line programs (opposed to branching programs) in a data-independent fashion, where the succession of the operations to be executed is thus not influenced by the specific value of input values (opposed to data-dependent computations), which can be modeled as Computational Directed Acyclic Graph (CDAG) G( V,E), whose set of vertices represents operations (of both input/output and processing type) and whose set of edges represents data dependencies. In this thesis we investigate various aspects of CDAG computations, among which their memory requirements and the amount of data movement (either between levels of a memory hierarchy or between various processors executing a program in parallel) required in situations in which only a limited amount of memory space is available. This thesis is organized as follows. In Chapter 1, we introduce the notation and the main definitions which will be used through the presentation. In Chapter 2, we study lower bounds on the size of the memory space which is necessary to compute various CDAGs. We introduce the Pebble Game, a theoretical device used in literature to study the space requirements of CDAGs computations. We then describe the Marking Rule approach originally introduced by Bilardi et. al. in [10] and we apply it in order to obtain lower bound on the space complexity of Superconcentrators-Stack CDAGs [68,40]. In order to study the limits of the Marking Rule approach, we introduce the concept of visit of a CDAG, and we prove various upper bounds on the memory space required for visiting a CDAG under appropriate conditions. In Chapter 3, we study upper bounds on the minimum memory space necessary to compute any CDAG. After reviewing the main contributions in literature [35, 40, 43], we present a novel algorithm which allows to pebble any CDAG with |E|=m edges using at most O(m\log m) memory space. In Chapter 4, we direct our attention towards the input-output cost (I/O cost) of CDAGs computations, intended either as the data exchange between different levels of a memory hierarchy, or as the communication of data between various processors executing a program in parallel. In particular, we obtain lower bounds for the input-output (I/O) complexity of CDAGs computations with respect to the classical model by Hong and Kung [37]. We begin by studying the I/O complexity of Strassen's algorithm when executed sequentially on a machine equipped with a two level memory hierarchy. We provide an alternative technique to those in [7, 62] to obtain a tight lower bound to the I/O complexity of Strassen's matrix multiplication algorithm for computations in which no intermediate result is ever recomputed. We then obtain the first asymptotically tight lower bound to the I/O complexity of Strassen's algorithm for general computations, that is, computations without any restriction on the recomputation of intermediate values. We also study the I/O complexity of Strassen's algorithm when executed in parallel by P processors each equipped with a finite memory. We obtain an lower bound which holds for any computation (no restriction on recomputation), without any assumption regarding the distribution of the input data among the P processors at the beginning of the computation. Furthermore, in the main contribution of Chapter 4, we provide a novel lower bound for the I/O complexity of Strassen's matrix multiplication algorithm, which holds for all possible computations, without constraints on the number of times an immediate result can be computed. In Chapter 5, we consider the effect of opportune memory utilization in the context of error resilient algorithms, which provide (almost) correct solutions even when silent memory errors occur. In particular, we provide a brief overview of the results published by the author in [22].

A partire dall'avvento del calcolatore digitale (computer), la sua tecnologia costitutiva e stata caratterizzata da un ritmo di sviluppo costante e impressionante. Sebbene la maggior parte dei parametri siano ancora in via di miglioramento, vi è un crescente consenso che i limiti fisici alla velocità di propagazione dei segnali ed alla dimensione dei dispositivi integrati stiano diventando sempre piu significativi. In definitiva, il tempo di accesso alla memoria associata ad un calcolatore digitale è destinato ad aumentare con la dimensione della memoria. Pertanto, quando e richiesta una memoria di grandi dimensioni, risulta conveniente organizzarla gerarchicamente in piu livelli, caratterizzati da dimensione e tempo di accesso progressivamente crescenti. Tipicamente, i livelli di gerarchia di memoria comprendono i registri della CPU, due o tre livelli di cache, la memoria principale (RAM) e i dischi. Rispetto ai registri della CPU, le memorie cache sono qualche centinaia di volte piu lente, la memoria RAM e qualche migliaio di volte piu lenta, mentre i dischi sono qualche milione di volte piu lenti. L'uso efficace dei livelli piu veloci della gerarchia di memoria e pertanto un punto chiave nella progettazione ed implementazione di algoritmi. I limiti fisici sono un problema anche nel contesto delle architetture multiprocessore e del calcolo parallelo, a causa del ritardo introdotto dalla velocità dei segnali usati per la comunicazione tra le varie unita di elaborazione. Inoltre, nonostante la Legge di Moore predica un aumento di velocità esponenziale per l'hardware in generale, il tasso di miglioramento annuale del tempo-per-operazione-aritmetica (miglioramento CPU), nel corso degli anni, ha costantemente superato quella del tempo-per-lettura/scrittura-dato. Appare legittimo aspettarsi che la percentuale di tempo consumata per la comunicazione diventi sempre piu rilevante, costituendo sempre piu un collo di bottiglia per le prestazioni sia delle memorie multilivello che delle architetture di calcolo parallelo. Nel valutare la complessità degli algoritmi, si devono pertanto considerare due tipi di costo: il costo aritmetico, che dipende dal numero di passi computazionali richiesti, ed il costo di comunicazione (I/O), che dipende dal movimento dei dati richiesto nell'ambito dell'esecuzione di un algoritmo, tra livelli diversi della gerarchia di memoria (nel caso sequenziale), o nella rete di collegamento tra diversi processori (nel caso parallelo). In entrambi questi scenari applicativi, la componente di I/O ha spesso un impatto sulle prestazioni dell'algoritmo molto piu significativo del tempo della componente aritmetica. E' quindi di grande interesse indagare da un lato lo spazio di memoria minimo richiesto per il calcolo di un algoritmo (space complexity), e dall'altro il tradeoff tra lo spazio di memoria effettivamente utilizzato e il volume di comunicazione dei dati necessari per l'esecuzione dell'algoritmo (I/O complexity). Oltre all'interesse puramente teorico di tale analisi, il perseguimento di buone tecniche per individuare limiti inferiori (lower bounds techniques) e anche fondamentale per il perseguimento di algoritmi ad alte prestazioni, in quanto consentono di valutare la distanza di una soluzione proposta dal livello ottimale. Nel nostro studio ci focalizziamo sui calcoli eseguiti con programmi straight-line (in contrapposizione ai programmi branching) in modalità indipendente dai dati, dove quindi la successione delle operazioni da eseguire non e influenzata dal valore specifico di valori di ingresso (in contrapposizione alle computazioni data-dependent), che possono essere rappresentati grafi diretti aciclici computazionali (CDAG) G(V;E), i cui vertici rappresentano operazioni (sia di input/output che di elaborazione) e i cui archi rappresentano dipendenze tra i dati (data dependencies). In questa tesi analizziamo vari aspetti dei calcoli di CDAG, tra cui i loro requisiti di memoria e la quantità di movimento di dati (tra diversi livelli di una gerarchia di memoria o tra diversi processori che eseguono un programma in parallelo) richiesti in situazioni in cui e disponibile solo una quantità limitata di spazio di memoria. La tesi e organizzata come segue. Nel Capitolo 1, si introduce la notazione e le principali definizioni che verranno utilizzati nella presentazione. Nel Capitolo 2, si studiano limiti inferiori (lower bounds) per le dimensioni dello spazio di memoria che è necessario per calcolare vari CDAGs. Introduciamo il Pebble Game, uno strumento concettuale utilizzato in letteratura per studiare i requisiti di spazio di memoria dei calcoli su CDAG. Successivamente si descrive l'approccio Marking Rule (Regola di Marcatura) originariamente introdotta da Bilardi et. al. [10], e lo si applica per ottenere limiti inferiori (lower bounds) per la lo spazio di memoria necessario per la valutazione dei CDAG Superconcentrators-Stack [68, 40] . Al fine di studiare i limiti dell'approccio con Marking Rule, introduciamo il concetto di visita di un CDAG, e dimostriamo vari limiti superiori (upper bounds) per lo spazio di memoria necessario per visitare un CDAG in condizioni appropriate. Nel Capitolo 3, si studiano limiti superiori (upper bounds) per lo spazio di memo ria minimo necessario per calcolare qualsiasi CDAG. Dopo aver esaminato i principali contributi della letteratura [35, 40, 43], si presenta un nuovo algoritmo che permette di valutare (pebble) qualsiasi CDAG con |E| = m archi usando al massimo uno spazio di memoria O(m log m). Nel Capitolo 4, si rivolge l'attenzione al costo legato alla comunicazione I/O cost per le computazioni di CDAG, inteso come scambio di dati tra i diversi livelli di una gerarchia di memoria, o come la comunicazione di dati tra diversi processori che eseguono un programma in parallelo. In particolare, otteniamo limiti inferiori (lower bounds) per la complessità di ingresso-uscita (I/O) dei calcoli di CDAG, in relazione al modello classico di Hong e Kung [37]. Si studiano quindi le esecuzioni sequanziali dell' algoritmo di Strassen per la moltiplicazione di matrici quadrate su una piattaforma equipaggiata con una memoria gerarchica a due livelli. In tale modello, si ottiene quindi un limite inferiore (lower bound) per la complessità di I/O dell'algoritmo di Strassen, sotto il vincolo che nessun risultato intermedio venga calcolato piu di una volta durante l'esecuzione dell'algoritmo. Sebbene il limite inferiore ottenuto sia gia stati presentato in letteratura [7, 62], la nostra tecnica permette di ottenere dimostrazioni piu pulite, basate sulla struttura ricorsiva degli algoritmi anzichè sulle proprietà combinatorie dei CDAG che li rappresentano. Sempre per il modello sequenziale, nel contributo principale del Capitolo 4, si fornisce un nuovo limite inferiore (lower bound) per la complessità di I/O dell'algoritmo di moltiplicazione matriciale di Strassen, che vale per tutte le possibili computazioni, senza vincoli sul numero di volte in cui un risultato immediato può essere calcolato. Sfruttando la stessa tecnica usata per il risultato appena menzionato, si ottiene un limite inferiore per la complessità di I/O per computazioni dell'algoritmo di Strassen eseguite in parallelo da P, ciascuno equipaggiato con una memoria finita, processori connessi tra loro. Nessuna assunzione è necessaria riguardo l'iniziale distribuzione dei dati di input fra i P processori. Nel Capitolo 5, si considera l'effetto di un utilizzo opportuno della memoria nel contesto di algoritmi resilienti agli errori (di memoria), che forniscono soluzioni (quasi) corrette anche quando si verificano errori di memoria "silenziosi" (corruzioni di dati memorizzati), ovvero che non causano il blocco dell'esecuzione del programma. In particolare, si va a fornire una panoramica dei risultati ottenuti nell'articolo [22].