Paging on Complex Architectures

Progressi tecnologici permettono la costruzione di sistemi di calcolo sempre piu' performanti. Tuttavia, l'uso efficace delle risorse di calcolo viene spesso reso difficoltoso dalla complessita' del sistema stesso. Cruciale verso l'ottenimento di buone performance e' la gestione del flusso di dati all'interno del sistema di memoria del calcolatore. In particolare, data una piccola ma veloce memoria (una cache), attraverso la quale tutti i dati che devono essere elaborati devono passare, e' necessario stabilire una serie di regole, che poi devono essere implementate da un algoritmo, che definiscono quali dati devono essere eliminati da tale memoria per fare posto a nuovi eventuali dati. L'obiettivo e' minimizzare il numero di volte che un dato viene richiesto e non si trova in cache (fault), perche' recuperare dati da memorie piu' lente e' costoso, sia in termini di tempo che di energia. Questa tesi studia due generalizzazioni di questo problema, conosciuto col nome di paging. Tale problema e' intrinsecamente online, poiche' le future richieste di dati da parte di un processo non sono tipicamente note. Motivati dalla recente diffusione di architetture di calcolo multi-threaded e multi-core, dove diversi thread o processi possono essere eseguiti simultaneamente, e/o dove sono presenti diverse unita' di calcolo, e dal recente interesse verso la riduzione del consumo energetico dei sistemi di calcolo, nella prima parte della tesi studiamo una variante del problema del paging dove viene premiato l'uso efficiente delle risorse di memoria. In questo problema l'obiettivo consiste nel minimizzare una combinazione sia del numero di fault che dell'occupazione in memoria dei dati di un processo. Due sono i risultati principali di questa parte: il primo e' un risultato di impossibilita' che indica che, nella pratica, algoritmi online non riescono competere con algoritmi che conoscono in anticipo le richieste di dati fatte dal processo; il secondo e' la definizione di un algoritmo online che ottiene all'incirca le migliori prestazioni tra tutti i possibili algoritmi online. Nella seconda parte della tesi ci concentriamo sulla gestione di una cache condivisa tra molteplici processi concorrenti. Come anticipato in precedenza, questo ha un'applicazione diretta nelle architetture multi-threaded e multi-core. In questo problema la memoria veloce deve servire una sequenza di richieste che provengono, in un certo ordine, da t diversi processi. Attreverso le scelte che opera, l'algoritmo di gestione alloca dinamicamente lo spazio disponibile in cache tra i vari processi, e questo ha un chiaro impatto sul loro avanzamento. Qui l'obiettivo principale e' minimizzare il tempo necessario alla completa esecuzione dei processi. Dimostriamo lower e upper bound stretti sulle performance raggiunte da algoritmi online per diversi varianti del problema.