This dissertation is part of a long-termresearch, that aims at a deeper use of the feedback control theory in both the management and the design of computing systems. More in detail, this work mainly deals with resource management in computing systems, in particular by means of advanced control techniques, i.e., for example, adaptive and predictive ones. In the literature a significant number of contributions can be found on “control of computing systems”. However, those contributions almost invariantly refer to situations where some control loop is closed around an existing computing system, in order to guarantee the achievement of some properties. Examples can be found in several domains, starting from process scheduling, up to Service Level Agreements, and so forth. In other words, in (virtually) the totality of the available contributions, the computing system is treated exactly the same as the “process” is in control design problems referring to other domains, without taking into account that in a computing system a controller may already exist (in the scheduling context, the scheduler itself ), which is not to be confound with the process, yet “re-designed” in a control-oriented view. Having established that the (control) problems addressed in this dissertation are quite peculiar with respect to the mainstream literature, the first task to accomplish is to somehow classify those problems. To this end, a taxonomy that divides control problems for computing systems into three main categories can be sketched out, on the basis of the level of complexity of the examined problem. The first one contains problems where the control specifications readily take the form of Set-Point signals and requirements on their tracking, while there is little or no uncertainty on the controlled system, any desirable feedback signal is accessible - in one word, the sole justification for introducing feedback are exogenous disturbances. The second category contains problems that can still be formulated as Set-Point tracking in the presence of disturbances, but where uncertainty and/or time-variability in the controlled system is relevant. The third type of problems, the most complex one, is when there may (or may not) be some time-varying and/or uncertain dynamics of the system, but the key point is that the control behaviour is not naturally expressed as Set-Point to be followed by controlled variables, but the objective is a functional to beminimised (or maximised). The first category of problems has already been addressed in previous works of the research to which this dissertation pertains. However, the same problems are further analysed, in spite of a more complex and computationally intensive control structure, with more sophisticated control techniques, showing the advantages of this new approach. The main subject of this dissertation is conversely constituted by the second category of problems, for which the model plays more relevant a role than in the previous one, and their solution require (not just suggest) the use of advanced techniques, including adaptive control. The third category of problem is finally left to future works, as it requires a formalisation effort that definitely exceeds the scope of this dissertation. In this particular work, advanced control techniques, i.e., predictive and adaptive ones, are applied to the problem of the process scheduling in the operating system (which belongs to the first category) and to the resource management problem (which belongs to the second category). In such a context, the aim of the dissertation is to sketch out an innovative and unitary design framework to provide an “end-to-end” control based methodology which starts from the analysis of the application and ends with the design of a control law. One of the main steps of said framework is the identification of a “macro-physical” model which is able to describe the system dynamics at a high level, suitable for control synthesis purposes. For example, in the resource management case, the model of the instructions’ execution or even of the processor electronics, is a correct “micro-physical” model, but unsuitable for control. This is a key aspect of this work, in which it is evidenced the absence of a “macro-physical” model in the computing systems domain. Another fundamental, yet critical aspect in the proposed methodology, is the design of sensors able to measure the system performance. To this end, we have used the “Heartbeats framework”, developed at the Massachusetts Institute of Technology (MIT), a software framework that provides a simple and standardised way for applications to monitor their performance, and make that information available to external observers. After presenting mathematical and theoretical considerations, some selected applications instrumented in the “Heartbeats framework” are chosen, for which a predictive adaptive control system is designed and validated through simulations. The thesis ends with an analysis a posteriori of the opportunities offered by the considered advanced control techniques in the computing systems domain, with some guidelines for future developments. In one word, at the end of the work the authors are convinced that many concepts of the control of anything but a computing system may and should be transposed to such systems. Doing it is not easy, yet in this work the authors have at least in part explained the reasons for such a difficulty, and sketched out some possible research future works, which attempt to bridge, in some sense, the distance between the control and the computer science community.

Questa tesi è parte di un progetto di ricerca a lungo termine che mira ad un impiego ragionato della teoria del controllo sia nella gestione che, soprattutto, nella progettazione dei sistemi informatici (o meglio nei “computing systems”, termine in un simile contesto di non facile traduzione). In dettaglio, la tesi tratta il problema dell’allocazione di risorse, nel senso più generale possibile, mediante tecniche basate sul controllo in retroazione, in particolare di tipo “avanzato” (per esempio, predittivo e adattativo). La letteratura offre diversi spunti, specialmente in merito al tema del controllo dei sistemi informatici. Nonostante ciò, nella maggior parte di questi lavori, l’obiettivo primario è “chiudere degli anelli” intorno a sistemi informatici già esistenti, al fine di garantire alcune proprietà dell’intero sistema, come il mantenimento di predeterminati livelli di qualità (Quality of Services). Si pensi, ad esempio, allo scheduling dei processi in un sistema operativo o al soddisfacimento dei Service Level Agreements. In altre parole, il sistema informatico viene considerato semplicemente come quello che, nella teoria del controllo, è considerato il processo. Questa visione non tiene conto del fatto che all’interno del sistema informatico, in realtà, spesso esiste già una componente legata al controllo (nel caso dello scheduling lo scheduler stesso), che non deve essere inclusa nel (e confusa con il) processo, ma deve essere ripensata e riprogettata in un’ottica di teoria del controllo. A questo proposito, un’attenta analisi dei problemi che si possono incontrare in questo contesto si rende necessaria. Una simile analisi porta a una classificazione molto generale, organizzata in base ai livelli di complessità e di dettaglio della problematica di interesse. Si possono, quindi, individuare tre categorie di problemi. La prima riguarda i problemi in cui i desideri si possono esprimere come inseguimento di un segnale di riferimento e in cui non sono presenti (o lo sono in piccola misura) incertezze sul sistema. La seconda riguarda i problemi in cui i desideri sono sempre esprimibili come inseguimento di un segnale di riferimento, ma nel sistema sono presenti incertezze e/o tempo varianze significative e difficilmente modellabili. La terza categoria riguarda i problemi in cui invece non è più possibile esprimere le richieste sul sistema come un’uscita desiderata, ma che hanno come obiettivo la minimizzazione (o massimizzazione) di un funzionale. La prima tipologia di problemi è già stata affrontata all’interno del progetto di ricerca a cui questo lavoro appartiene. Tuttavia, nel seguito verranno ripresi e affrontati, mostrando come, in casi particolari, anche in questo tipo di problemi si trae vantaggio dall’utilizzo di tecniche di controllo più sofisticate. Ciò nonostante, nel corso della tesi ci focalizzeremo principalmente sui problemi della seconda categoria, applicando, approfondendo e specializzando alcune tecniche già impiegate nei problemi precedenti. Infine, la terza categoria di problemi è lasciata a sviluppi futuri. In particolare, il lavoro si propone di utilizzare tecniche di controllo avanzate, ad esempio tecniche predittive ed adattative, a due particolari problemi: quello dello scheduling di processi nel sistema operativo (problema che appartiene alla prima categoria) e quello della gestione di risorse, come processori, frequenza di clock e memoria, richieste dalle applicazioni (problema che appartiene alla seconda categoria). In tale contesto si vuole delineare una metodologia di progetto completa, organica e generale di un sistema informatico. Uno dei passi fondamentali della metodologia di progetto descritta è quello dell’individuazione di un modello “macro-fisico”, capace di descrivere le dinamiche del sistema ad un livello di dettaglio accettabile per la sintesi del controllo. Per esempio, nel caso della gestione delle risorse da attribuire ad una applicazione software, la descrizione elettronica del processore e delle comunicazioni a livello hardware, o modelli legati alle microistruzioni del programma costituirebbero un modello “micro-fisico” sicuramente corretto ma inadatto alla sintesi di un controllore. Questo è un contributo chiave di questo lavoro, in cui viene evidenziata (forse per la prima volta) l’assenza di un modello in grado di astrarsi dai “micro-fenomeni” del sistema (nell’esempio le microistruzioni), da quelli che sono i “macro-fenomeni” di interesse per il controllo. Un altro aspetto fondamentale e critico all’interno della metodologia di progetto descritta è quello della progettazione di sensori adatti a misurare le performance del sistema in questione. A questo proposito, si è fatto riferimento a un framework, sviluppato al Massachusetts Institute of Technology (MIT), per l’instrumentazione di applicazioni per monitorare l’avanzamento della loro esecuzione: “Heartbeats framework”. Dopo le considerazioni teoriche, vengono analizzate alcune significative applicazioni instrumentate nel contesto dell’“Heartbeats framework”, per le quali viene progettato, in seguito, un sistema di controllo adattativo e predittivo per far fronte alla loro tempo varianza. Il lavoro si conclude con un’analisi a posteriori delle potenzialità offerte dalle tecniche di controllo analizzate e con alcune indicazioni per sviluppi futuri. In una parola, si potrebbe sintetizzare tutto ciò dicendo che a valle del lavoro gli autori sono ancora più convinti di prima che moltissimi aspetti e concetti propri del controllo “tradizionele”, ossia “di tutto meno che di un computing system”, possano e debbano essere trasposti nel contesto di tali sistemi. Farlo ovviamente non é come dirlo; in questo lavoro si ritiene (umilmente) di avere almeno in parte spiegato perché e in che senso, nonché di aver individuato alcune linee di ricerca “a mezza via” tra le comunità della computer science e dei controlli che possono rispondere alle domande rimaste aperte.

Advanced control techniques for resource management in computing systems

PAPADOPOULOS, ALESSANDRO VITTORIO;NEGRO, SARA
2009/2010

Abstract

This dissertation is part of a long-termresearch, that aims at a deeper use of the feedback control theory in both the management and the design of computing systems. More in detail, this work mainly deals with resource management in computing systems, in particular by means of advanced control techniques, i.e., for example, adaptive and predictive ones. In the literature a significant number of contributions can be found on “control of computing systems”. However, those contributions almost invariantly refer to situations where some control loop is closed around an existing computing system, in order to guarantee the achievement of some properties. Examples can be found in several domains, starting from process scheduling, up to Service Level Agreements, and so forth. In other words, in (virtually) the totality of the available contributions, the computing system is treated exactly the same as the “process” is in control design problems referring to other domains, without taking into account that in a computing system a controller may already exist (in the scheduling context, the scheduler itself ), which is not to be confound with the process, yet “re-designed” in a control-oriented view. Having established that the (control) problems addressed in this dissertation are quite peculiar with respect to the mainstream literature, the first task to accomplish is to somehow classify those problems. To this end, a taxonomy that divides control problems for computing systems into three main categories can be sketched out, on the basis of the level of complexity of the examined problem. The first one contains problems where the control specifications readily take the form of Set-Point signals and requirements on their tracking, while there is little or no uncertainty on the controlled system, any desirable feedback signal is accessible - in one word, the sole justification for introducing feedback are exogenous disturbances. The second category contains problems that can still be formulated as Set-Point tracking in the presence of disturbances, but where uncertainty and/or time-variability in the controlled system is relevant. The third type of problems, the most complex one, is when there may (or may not) be some time-varying and/or uncertain dynamics of the system, but the key point is that the control behaviour is not naturally expressed as Set-Point to be followed by controlled variables, but the objective is a functional to beminimised (or maximised). The first category of problems has already been addressed in previous works of the research to which this dissertation pertains. However, the same problems are further analysed, in spite of a more complex and computationally intensive control structure, with more sophisticated control techniques, showing the advantages of this new approach. The main subject of this dissertation is conversely constituted by the second category of problems, for which the model plays more relevant a role than in the previous one, and their solution require (not just suggest) the use of advanced techniques, including adaptive control. The third category of problem is finally left to future works, as it requires a formalisation effort that definitely exceeds the scope of this dissertation. In this particular work, advanced control techniques, i.e., predictive and adaptive ones, are applied to the problem of the process scheduling in the operating system (which belongs to the first category) and to the resource management problem (which belongs to the second category). In such a context, the aim of the dissertation is to sketch out an innovative and unitary design framework to provide an “end-to-end” control based methodology which starts from the analysis of the application and ends with the design of a control law. One of the main steps of said framework is the identification of a “macro-physical” model which is able to describe the system dynamics at a high level, suitable for control synthesis purposes. For example, in the resource management case, the model of the instructions’ execution or even of the processor electronics, is a correct “micro-physical” model, but unsuitable for control. This is a key aspect of this work, in which it is evidenced the absence of a “macro-physical” model in the computing systems domain. Another fundamental, yet critical aspect in the proposed methodology, is the design of sensors able to measure the system performance. To this end, we have used the “Heartbeats framework”, developed at the Massachusetts Institute of Technology (MIT), a software framework that provides a simple and standardised way for applications to monitor their performance, and make that information available to external observers. After presenting mathematical and theoretical considerations, some selected applications instrumented in the “Heartbeats framework” are chosen, for which a predictive adaptive control system is designed and validated through simulations. The thesis ends with an analysis a posteriori of the opportunities offered by the considered advanced control techniques in the computing systems domain, with some guidelines for future developments. In one word, at the end of the work the authors are convinced that many concepts of the control of anything but a computing system may and should be transposed to such systems. Doing it is not easy, yet in this work the authors have at least in part explained the reasons for such a difficulty, and sketched out some possible research future works, which attempt to bridge, in some sense, the distance between the control and the computer science community.
MAGGIO, MARTINA
ING V - Facolta' di Ingegneria dell'Informazione
22-ott-2010
2009/2010
Questa tesi è parte di un progetto di ricerca a lungo termine che mira ad un impiego ragionato della teoria del controllo sia nella gestione che, soprattutto, nella progettazione dei sistemi informatici (o meglio nei “computing systems”, termine in un simile contesto di non facile traduzione). In dettaglio, la tesi tratta il problema dell’allocazione di risorse, nel senso più generale possibile, mediante tecniche basate sul controllo in retroazione, in particolare di tipo “avanzato” (per esempio, predittivo e adattativo). La letteratura offre diversi spunti, specialmente in merito al tema del controllo dei sistemi informatici. Nonostante ciò, nella maggior parte di questi lavori, l’obiettivo primario è “chiudere degli anelli” intorno a sistemi informatici già esistenti, al fine di garantire alcune proprietà dell’intero sistema, come il mantenimento di predeterminati livelli di qualità (Quality of Services). Si pensi, ad esempio, allo scheduling dei processi in un sistema operativo o al soddisfacimento dei Service Level Agreements. In altre parole, il sistema informatico viene considerato semplicemente come quello che, nella teoria del controllo, è considerato il processo. Questa visione non tiene conto del fatto che all’interno del sistema informatico, in realtà, spesso esiste già una componente legata al controllo (nel caso dello scheduling lo scheduler stesso), che non deve essere inclusa nel (e confusa con il) processo, ma deve essere ripensata e riprogettata in un’ottica di teoria del controllo. A questo proposito, un’attenta analisi dei problemi che si possono incontrare in questo contesto si rende necessaria. Una simile analisi porta a una classificazione molto generale, organizzata in base ai livelli di complessità e di dettaglio della problematica di interesse. Si possono, quindi, individuare tre categorie di problemi. La prima riguarda i problemi in cui i desideri si possono esprimere come inseguimento di un segnale di riferimento e in cui non sono presenti (o lo sono in piccola misura) incertezze sul sistema. La seconda riguarda i problemi in cui i desideri sono sempre esprimibili come inseguimento di un segnale di riferimento, ma nel sistema sono presenti incertezze e/o tempo varianze significative e difficilmente modellabili. La terza categoria riguarda i problemi in cui invece non è più possibile esprimere le richieste sul sistema come un’uscita desiderata, ma che hanno come obiettivo la minimizzazione (o massimizzazione) di un funzionale. La prima tipologia di problemi è già stata affrontata all’interno del progetto di ricerca a cui questo lavoro appartiene. Tuttavia, nel seguito verranno ripresi e affrontati, mostrando come, in casi particolari, anche in questo tipo di problemi si trae vantaggio dall’utilizzo di tecniche di controllo più sofisticate. Ciò nonostante, nel corso della tesi ci focalizzeremo principalmente sui problemi della seconda categoria, applicando, approfondendo e specializzando alcune tecniche già impiegate nei problemi precedenti. Infine, la terza categoria di problemi è lasciata a sviluppi futuri. In particolare, il lavoro si propone di utilizzare tecniche di controllo avanzate, ad esempio tecniche predittive ed adattative, a due particolari problemi: quello dello scheduling di processi nel sistema operativo (problema che appartiene alla prima categoria) e quello della gestione di risorse, come processori, frequenza di clock e memoria, richieste dalle applicazioni (problema che appartiene alla seconda categoria). In tale contesto si vuole delineare una metodologia di progetto completa, organica e generale di un sistema informatico. Uno dei passi fondamentali della metodologia di progetto descritta è quello dell’individuazione di un modello “macro-fisico”, capace di descrivere le dinamiche del sistema ad un livello di dettaglio accettabile per la sintesi del controllo. Per esempio, nel caso della gestione delle risorse da attribuire ad una applicazione software, la descrizione elettronica del processore e delle comunicazioni a livello hardware, o modelli legati alle microistruzioni del programma costituirebbero un modello “micro-fisico” sicuramente corretto ma inadatto alla sintesi di un controllore. Questo è un contributo chiave di questo lavoro, in cui viene evidenziata (forse per la prima volta) l’assenza di un modello in grado di astrarsi dai “micro-fenomeni” del sistema (nell’esempio le microistruzioni), da quelli che sono i “macro-fenomeni” di interesse per il controllo. Un altro aspetto fondamentale e critico all’interno della metodologia di progetto descritta è quello della progettazione di sensori adatti a misurare le performance del sistema in questione. A questo proposito, si è fatto riferimento a un framework, sviluppato al Massachusetts Institute of Technology (MIT), per l’instrumentazione di applicazioni per monitorare l’avanzamento della loro esecuzione: “Heartbeats framework”. Dopo le considerazioni teoriche, vengono analizzate alcune significative applicazioni instrumentate nel contesto dell’“Heartbeats framework”, per le quali viene progettato, in seguito, un sistema di controllo adattativo e predittivo per far fronte alla loro tempo varianza. Il lavoro si conclude con un’analisi a posteriori delle potenzialità offerte dalle tecniche di controllo analizzate e con alcune indicazioni per sviluppi futuri. In una parola, si potrebbe sintetizzare tutto ciò dicendo che a valle del lavoro gli autori sono ancora più convinti di prima che moltissimi aspetti e concetti propri del controllo “tradizionele”, ossia “di tutto meno che di un computing system”, possano e debbano essere trasposti nel contesto di tali sistemi. Farlo ovviamente non é come dirlo; in questo lavoro si ritiene (umilmente) di avere almeno in parte spiegato perché e in che senso, nonché di aver individuato alcune linee di ricerca “a mezza via” tra le comunità della computer science e dei controlli che possono rispondere alle domande rimaste aperte.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2010_10_Negro_Papadopoulos.pdf

accessibile in internet solo dagli utenti autorizzati

Descrizione: Testo della tesi
Dimensione 4.59 MB
Formato Adobe PDF
4.59 MB Adobe PDF   Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/5784