Applications of Control Theory to Computer Systems Optimization

Computer systems complexity is growing rapidly, thus making the efficient use of their resources an increasingly challenging task. In many cases the optimization of the management in such systems has been developed with ad-hoc techniques and heuristics. In this thesis, a more general and flexible approach is explored to resource management, based on the powerful framework of stochastic optimal control. This approach requires a careful modeling of the system of interest as a dynamical system with appropriate cost functions and stochastic descriptions of the inputs that are imposed by the external environment. Then, the question of an optimal management policy that minimizes the expected cost becomes mathematically well posed and can be systematically investigated. Two cases studies illustrating the approach are developed, as summarized below. In Chapters 1–5, the classical replacement problem for memory hierarchies is cast within the framework of optimal control theory. Memory references are assumed to comply with the Least Recently Used Stack Model (LRUSM); arbitrary stack-distance distributions are considered. An optimal policy is derived to minimize the miss rate for an infinite trace (a control over an infinite horizon). We call it a K-L policy where K(C) and L(C) are parameters, whose value is a function of the buffer (cache) size C, determined by the stack-distance distribution. Then, the concept of Least Profit Rate (LPR) policy is introduced and it is shown that, for the LRUSM model, LPR is an optimal policy over an infinite horizon which, in steady state, coincides with the K-L policy. The LPR satisfies the inclusion property whereby the content of a given buffer is also contained in all larger buffers. This property is known to enable the efficient computation of the number of misses for a given address trace, simultaneously for all buffer sizes. Furthermore, the LPR formulation leads to a linear time computation of the values K(C) and L(C) for all relevant values of C, improving on the cubic bound that naturally arises within the K-L derivation. Furthermore, the properties of LPR are exploited to derive an efficient algorithm to optimally partition a buffer concurrently accessed by multiple processes. Finally, the miss rate of LPR is compared with that of OPT, the well-known optimal off-line policy, to investigate the difference between an exact and a statistical knowledge of the future of the trace. Obtaining a closed form characterization of the optimal replacement policy over a finite horizon has proved to be rather more difficult than over the infinite horizon. The problem has been solved for monotone stack-distance distributions. Separate arguments establish the optimality of the Least Recently Used (LRU) policy for all nonincreasing distributions and of the Most Recently Used (MRU) policy for all nondecreasing distributions. Interestingly, LRU and MRU are special cases of LPR, within the LRUSM model, for nonincreasing and non decreasing distributions, respectively. The results have been obtained by introducing a significant variant of the standard Bellman’s equation, potentially useful for other control problems. In Chapters 6–7 it is studied the problem of processors allocation for the Galois System, a tool for automatically parallelizing, by means of speculative execution, algorithms that present data amorphous parallelism. The Galois System is modeled using graph-theoretic concepts and the optimization goal is identified in trying to maximize the parallelism, while keeping a constant conflict ratio. This is linked to a function for which we analytically derive some properties that are then used to design an algorithm that controls the number of processors in a quick and stable way. For this purpose an extension to the well known Turán’s theorem is developed.

La complessità dei sistemi informatici sta crescendo rapidamente, rendendo l’uso efficiente delle loro risorse un compito sempre piú proibitivo. In molti casi la gestione ottimizzata di questi sistemi è stata sviluppata con tecniche ad-hoc ed euristiche. In questa tesi viene esplorato un approccio piú generale e flessibile alla gestione delle risorse, fondato sul potente quadro teorico del controllo ottimo stocastico. Questo approccio richiede un’attenta modellizzazione del sistema di interesse come sistema dinamico, con appropriate funzioni di costo e descrizioni stocastiche degli ingressi imposti dall’ambiente esterno. A questo punto la ricerca di una politica di gestione ottima che minimizzi il costo aspettato è matematicamente ben posta e può essere risolta sistematicamente. Vengono sviluppati due casi di studio, come riassunto di seguito. Nei Capitoli 1–5 il classico problema di sostituzione (replacement) per le gerarchie di memoria viene formulato nel quadro della teoria del controllo ottimo. Si assume che i riferimenti di memoria rispettino il Least Recently Used Stack Model (LRUSM) e vengono considerate distribuzioni arbitrarie sullo stack. Una politica ottima per minimizzare il tasso di miss (accessi fuori dal buffer) per una traccia di lunghezza infinita viene derivata e chiamata K-L, dove K(C) ed L(C) sono parametri il cui valore è un funzione, determinata dalla distribuzione di accessi allo stack, della taglia C del buffer. In seguito viene introdotto il concetto di politica a tasso di profitto minimo (Least Profit Rate – LPR) e si dimostra che, nell’LRUSM, LPR è una politica ottima su orizzonte infinito che, allo stato stazionario, coincide con la politica K-L. LPR soddisfa la proprietà di inclusione: i contenuti di buffer di dimensione minore sono inclusi in quelli maggiori. Questa proprietà consente di calcolare efficientemente il numero di miss per una data traccia in contemporanea per tutte le taglie del buffer. Inoltre le proprietà della LPR vengono sfruttate per derivare un efficiente algoritmo di partizionamento per buffer condivisi concorrentemente fra piú processi. Infine il tasso di miss di LPR viene confrontato con quello di OPT, la nota politica ottima off-line, per indagare la differenza fra una conoscenza esatta e una statistica del futuro della traccia. Ottenere una forma chiusa per la politica di sostituzione su orizzonte finito si è dimostrato un problema ben piú difficile che su orizzonte infinito, ed è stato risolto nel caso di distribuzioni di accesso monotone. Argomenti diversi dimostrano rispettivamente l’ottimalità della politica Least Recently Used (LRU) per distribuzioni non crescenti e quella di Most Recently Used (MRU) per distribuzioni non decrescenti. I risultati sono stati ottenuti grazie all’introduzione di una significativa variante dell’usuale equazione di Bellman, potenzialmente utile in altri problemi di controllo. Nei Capitolo 6–7 viene studiato il problema dell’allocazione dei processori nel sistema Galois, uno strumento per la parallelizzazione automatica, per mezzo di esecuzione ottimistica (speculative execution), di algoritmi che presentino un cosiddetto parallelismo amorfo sui dati (data amorphous parallelism). Il sistema Galois viene modellizzato tramite concetti di teoria dei grafi e l’obiettivo dell’ottimizzazione è identificato nella massimizzazione del parallelismo col vincolo di mantenere basso il tasso di conflitti. Questo viene collegato ad una funzione, per cui vengono analiticamente derivate alcune proprietà che sono poi usate nella progettazione di un algoritmo capace di controllare il numero di processori in maniera stabile e veloce. A tal fine viene sviluppata un’estensione del noto teorema di Turán.