Applications of Control Theory to Computer Systems Optimization

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.