Paging on Complex Architectures

Advances in technology allow to build computer systems of ever increasing performances and capabilities. However, the effective use of such computational resources is often made difficult by the complexity of the system itself. Crucial to the performance of a computing device is the orchestration of the flow of data across the memory hierarchy. Specifically, given a fast but small memory (a cache) through which all the data that have to be processed must pass, it is necessary to establish a set of rules, then implemented by an algorithm, that define which data has to be evicted from such a memory to make room for new incoming data. The goal is that of minimizing the number of times that requested data is outside the cache (faults), since fetching data from farther levels of the memory hierarchy incurs high costs, in terms of time and also of energy. This thesis studies two generalizations of this problem, known as the paging problem. This problem is intrinsically online, as future data requests issued by a computer program are typically unknown. Motivated by the recent diffusion of multi-threaded and multi-core architectures, whereby several threads or processes can be executed simultaneously, and/or there are several processing units, and by the recent and rapidly growing interest in reducing power consumptions of computer systems, in the first part of the thesis we study a variation of paging which rewards the efficient usage of memory resources. In this problem the goal is that of minimizing a combination of both the number of faults and the cache occupancy of the process' data in fast memory. The main results of this part are two: the first is an impossibility result that indicates that, roughly speaking, online algorithms cannot compete in practice with algorithms that know in advance all the data requests issued by the process; the second is the design of an online algorithm that has almost the best performance among all the possible online algorithms. In the second part of the thesis we concentrate on the management of a cache shared among several concurrent processes. As outlined above, this has direct application in multi-threaded or multi-core architectures. In this problem the fast memory has to service a sequence of requests which is the interleaving of the requests issued by t different processes. Through its replacement decisions, the algorithm dynamically allocates the cache space among the processes, and this clearly impacts their progress. The main goal here is to minimize the time needed to complete the service of all the request sequences. We show tight lower and upper bounds on the performance of online algorithms for several variants of the problem.

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.