Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

| Crea un account

Versaci, Francesco (2009) Applications of Control Theory to Computer Systems Optimization. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF
929Kb

Abstract (inglese)

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.

Abstract (italiano)

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.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Bilardi, Gianfranco
Dottorato (corsi e scuole):Ciclo 22 > Scuole per il 22simo ciclo > INGEGNERIA DELL'INFORMAZIONE > SCIENZA E TECNOLOGIA DELL'INFORMAZIONE
Data di deposito della tesi:NON SPECIFICATO
Anno di Pubblicazione:2009
Parole chiave (italiano / inglese):optimal control; replacement policy; Bellman equation; LRU Stack Model
Settori scientifico-disciplinari MIUR:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Struttura di riferimento:Dipartimenti > Dipartimento di Ingegneria dell'Informazione
Codice ID:2712
Depositato il:21 Set 2010 12:57
Simple Metadata
Full Metadata
EndNote Format

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record