On space constrained computations

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].