kernel e una libreria a livello userspace, uno scheduler di tipo EDF (Earliest Deadline First) e permette di utilizzarne le sue funzionalità • Il modulo QoS manager, anch’esso implementato in parte nel kernel ed in parte in userspace. Si occupa di fornire le varie funzionalità di controllo basate sul feedback e su alcuni predittori definiti dal sistema.
Le varie applicazioni dovranno usare le API fornite dal framework per definire le richieste d’uso del processore, i vari parametri riguardanti le strategie di controllo e i predittori usati. L’applicazione quindi dovrà attivarsi periodicamente e chiamare le varie funzionalità del sistema per controllare le sue perfomance e fornire questi risultati al predittore e al controllore dell’applicazione. I test degli autori mostrano che questa tecnica fornisce uno scheduling corretto con soltanto il 3% di overhead sul tempo d’esecuzione.
3.3
Livello applicativo
Come già descritto nella Sezione 3.2, è possibile astrarre le funzionalità di resource e run-time management sino al livello applicativo. In questo caso non sarà sempre possibile modificare parametri specifici del sistema come quelli relativi allo scheduling ma ci si dovrà affidare a tecniche diverse per raggiungere i risultati sperati. In questo ambito sono state sviluppate sia soluzioni diverse da quelle usate nelle sezioni precedenti sia altre tecniche più generali già usate nei precedenti livelli d’astrazione. Nel primo caso si parla ad esempio di compilatori specializzati o tecniche di Design Space Exploration, mentre nel secondo di teoria del controllo o di machine learning. Questa sezione descriverà alcuni lavori di ricerca svolti a livello applicativo sia riguardo la pura gestione delle risorse e delle applicazioni sia riguardo ad altre tecniche affiancate alle soluzioni standard.
Il lavoro di Baek e Chilimbi consiste in un framework, chiamato Green, che tramite l’estensione del linguaggio C/C++ permette di implementare una modalità di approssimazione per le funzioni e i loop [24]. Lo sco- po di questo framework è quello di fornire una modalità per dichiarare semplicemente la qualità del servizio (QoS) al variare di diverse versioni approssimate delle stesse funzioni o di cicli eseguiti con meno iterazioni. Come è possibile notare nella Figura 3.9, il flusso di sviluppo all’interno di Green si svolge in più fasi. Prima di tutto lo sviluppatore deve fornire sia le
Fig. 3.9: Schema del sistema Green [24]
diverse approssimazioni delle funzioni che le informazioni necessarie per determinare il guadagno o la perdita di qualità in base all’approssimazione scelta. La fase successiva consiste nella calibrazione dell’applicazione con lo scopo di creare un modello della QoS basato sul variare delle appros- simazioni. Mentre le funzioni devono essere fornite in diverse versioni, tante quante le approssimazioni volute, i cicli vengono invece approssimati riducendo il numero di iterazioni mediante una conclusione anticipata del ciclo stesso. La stessa tipologia di approssimazione è eseguita nel lavoro di Misailovic et al. [25] dove vengono saltate regolarmente alcune iterazioni dai cicli ma non viene effettuata nessuna approssimazione delle funzioni. Per concludere, una volta che il modello è stato creato, l’applicazione viene ricompilata assieme a queste informazioni; in questo modo l’applicazione varierà la qualità dei suoi risultati in base ai vincoli precedentemente forniti e allo stato della QoS monitorata ad intervalli regolari.
Sezione 3.3. Livello applicativo 33 Il middleware ControlWare [26] è un’architettura basata sulla teoria del controllo specializzata su servizi internet. La Figura 3.10 delinea la metodologia di sviluppo per applicazioni che sfruttano ControlWare. La
Fig. 3.10: Metodologia di sviluppo di ControlWare [26]
prima fase consiste nella specifica dei diversi livelli di qualità del servizio che l’applicazione può fornire. Successivamente il blocco chiamato nel- l’immagine QoS mapper si occupa di leggere ed interpretare le precedenti informazioni trasformandole in un insieme di valori obiettivo e di cicli di controllo a feedback. Questa fase è svolta tramite l’utilizzo di una libreria di modelli, ognuno che descrive una diversa caratteristica di QoS e defini- sce un sistema di controllo ad anello chiuso (come in [27]) atto a risolvere tale problema. La fase successiva consiste nella configurazione dei vari monitor e degli attuatori forniti da ControlWare in modo da soddisfare la configurazione del QoS mapper. Dopo aver stimato matematicamente un modello per il sistema tramite le sue prestazioni generali, il controllore dell’applicazione viene creato ed ottimizzato per garantire la stabilità e la risposta ai disturbi dovuti alle variazioni del carico. Tutte queste in- formazioni verrano poi usate dal GRM (Generic Resource Manager) per decidere come allocare le risorse alle varie applicazioni. Il carico di lavoro
di un’applicazione verrà inserito in opportune code, una per ogni classe di servizio, che verranno monitorate dal GRM il quale prenderà le dovute decisioni in base alla quantità di task presenti nella coda e il numero di risorse assegnate per quel processo.
Un’altra strategia di gestione delle applicazioni a run-time è quella proposta in [7, 28, 29]. Il lavoro descritto dagli autori utilizza una fase di Design Space Exploration dettagliata ed automatizzata, atta a fornire le informazioni necessarie ad un run-time manager che opera a basso overhead e che alloca le diverse risorse alle applicazioni. La Figura 3.11 rappresenta il flusso che collega la fase di design a quella d’esecuzione. L’input del sistema è un insieme di diverse versioni della stessa applica-
Fig. 3.11: Flusso di sviluppo tra fase di design e d’esecuzione [29]
zione sviluppata con livelli di parallelizzazione differenti. Queste versioni della stessa applicazione vengono usate per analizzare il comportamen- to dell’applicazione alle diverse frequenze dei processori. Questa fase può essere svolta da diversi motori di Design Space Exploration come ad esempio Multicube [30, 31], illustrato più avanti in questa sezione. La fase d’esplorazione viene effettuata interfacciandosi con dei simulatori della
Sezione 3.3. Livello applicativo 35 piattaforma a due diversi livelli. Il primo simulatore è usato per fornire una prima classificazione dell’applicazione ad alto livello e per fornire le caratteristiche di un numero elevato di configurazioni. Il secondo, invece, effettua una simulazione molto più accurata, quindi più lenta, per le sole configurazioni precedenti che sono pareto-ottimali rispetto ai vari para- metri. A questo punto tramite le informazioni ricavate a design-time, il run-time resource manager deciderà quale configurazione di frequenze e parallelizzazione usare per ogni applicazione tramite uno scheduling gui- dato dalle deadline delle applicazioni stesse. La configurazione scelta sarà quella col minor consumo di potenza e la capacità rispettare le deadline.
Il framework ARTE, sviluppato da Mariani et al. [32], consiste invece in un sistema per la gestione a run-time delle applicazioni in base alla co- noscenza fornita dai dati acquisiti a design-time. Il lavoro utilizza la teoria delle code e ha lo scopo di migliorare le prestazioni delle applicazioni dal punto di vista del tempo di risposta medio. La Figura 3.12 rappresenta
Fig. 3.12: Flusso di progettazione nel framework ARTE [32]
il flusso di progettazione di un’applicazione all’interno del framework. La strategia utilizzata è simile in alcuni aspetti a quella usata nel nostro
lavoro di tesi. In ARTE, lo spazio di progettazione è formato da diverse versioni della stessa applicazioni ma con parallelizzazione diversa se il programma lo prevede. Il motore d’esplorazione si occupa di generare una lista di punti operativi che caratterizzano l’applicazione in base al tipo di parallelizzazione scelta. In base a questi punti e allo stato del sistema il Resource Manager presente nel sistema operativo deciderà quante risorse e quanti thread allocare per ogni applicazione.
Il motore di Design Space Exploration usato da Mariani et al. è quello fornito dal framework Multicube [30,31]. Esso consiste in un’infrastruttura per l’esplorazione automatica dello spazio di progetto così da ottenere una velocizzazione ed ottimizzazione della fase di design. I vantaggi di un’esplorazione automatica rispetto ad una manuale sono rappresentati in Figura 3.13 dove è possibile osservare come automatizzare questa proce- dura permetta di diminuire al minimo i tempi morti tra una simulazione e l’altra, garantendo un’accurata analisi delle applicazioni in tempi minori. Multicube è un framework avanzato per l’ottimizzazione multi-obiettivo,
Fig. 3.13: Confronto tra una Design Space Exploration manuale ed una automatica [30]
interamente comandato da linea di comando o da script. Mediante la configurazione degli opportuni file xml è possibile modellizzare una qual- siasi piattaforma e definirne il suo simulatore. La Figura 3.14 rappresenta una panoramica della struttura di questo framework. Come già descritto
Sezione 3.3. Livello applicativo 37
Fig. 3.14: Struttura del framework Multicube explorer [31]
precedentemente, Multicube integra un’interfaccia a linea di comando (M3Explorer Shell nell’immagine) che permette la costruzione automatica delle strategie d’esplorazione. Il kernel dell’infrastruttura si occupa invece di leggere i file di configurazione ed esporre i parametri del design space ai vari moduli che implementano il processo d’ottimizzazione, quali i bloc- chi Design of Experiment, Optimization algorithm e Use Case Simulator. La Design Space Exploration è eseguita utilizzando il livello d’astrazione esportato dal modello dell’architettura. Queste informazioni verrano usate dal modulo di ottimizzazione per eseguire l’esplorazione. A questo punto le metriche del sistema verranno visualizzate nella shell di Multicube e salvate su disco.
Un raffinamento di queste strategie di Design Space Exploration è stato proposto da Palermo et al. e consiste nel framework ReSPIR [33]. Questo framework si concentra sullo studio di una corretta esplorazione che permetta di ottimizzare, col minor numero d’esecuzioni possibile, alcuni parametri applicativi come ad esempio il throughput o il consumo di potenza. La strategia usata consiste in un campionamento dello spazio di design, con lo scopo diminuire il numero di simulazioni da effettuare. I risultati forniti da questa fase permetteranno di effettuare un’appros-
simazione del comportamento del sistema tramite una tecnica chiamata Response Surface Methodology (RSM). Queste due fasi vengono effettuate iterativamente, migliorando l’approssimazione del modello all’aumentare dell’iterazioni effettuate. I test effettuati su questo framework confermano la bontà di questa tecnica rispetto ad altre metodologie euristiche allo stato dell’arte come MOSA [34] e NSGA-II [35]. Questi risultati sono ancor più validi soprattutto nel caso di un numero di simulazioni non elevato, dove i precedenti algoritmi soffrono la mancanza di un numero sufficiente di simulazioni necessarie per la convergenza del risultato.
Le tecniche di Design Space Exploration fornite da Multicube sono state utilizzate oltre che in [7, 28, 29, 32, 33] anche nel nostro lavoro di tesi. Il framework d’esplorazione utilizzato comprende le caratteristiche di Multicube ma ne estende le funzionalità rendendo più semplice la definizione di una Design of Experiment e di una successiva esplorazione. Nel Capitolo 6 verranno spiegati più dettagliatamente alcuni di questi concetti.
Come ultimo esempio di adattività a livello applicativo presentiamo il framework SEEC. Tra i vari sistemi autonomi a livello applicativo è uno tra quelli con le potenzialità maggiori. SEEC è un framework sviluppa- to in collaborazione tra il Computer Science and Artificial Intelligence Laboratory del Massachussetts Institute of Technology e dal Dipartimen- to di Elettronica e Informazione del Politecnico di Milano. Consiste in un sistema autoadattivo capace di gestire a run-time applicazioni che espongono diversi goal al sistema [36–39]. Uno dei perni principali di questo framework è il ciclo ODA Observe-Decide-Act, tipico dei sistemi autoadattivi, che consiste nelle tre tipiche fasi della teoria del controllo ad anello chiuso. Queste tre fasi coincidono in parte con quelle del ciclo MAPE già descritto nel Capitolo 2, dove la fase di decisione è formata dai blocchi Analyze e Plan.
In Figura 3.15 possiamo vedere il ciclo di controllo di un’applicazione self-aware composto da tre diverse fasi:
Sezione 3.3. Livello applicativo 39
Fig. 3.15: Ciclo Observe-Decide-Act
• Osserva: in questa fase viene monitorata l’esecuzione dell’applica- zione. Vengono impiegati dei sensori, chiamati anche monitor, che osservano lo stato interno fornendo un’indicazione utile al blocco di decisione.
• Decidi: nella fase decisionale vengono elaborati i dati ricavati dalla fase di osservazione e vengono valutate le modifiche dei parametri di controllo per la successiva esecuzione del programma.
• Agisci: questa fase si occupa della modifica effettiva dei parametri, di sistema o dell’applicazione, decisi dal blocco precedente.
Riprendendo la classificazione fornita in [38], le caratteristiche interes- santi di questo framework sono:
• l’inclusione di meccanismi di dichiarazione dei goal e del feedback necessario al controllo
• l’utilizzo di un controllo adattativo abile nel rispondere velocemente a nuove applicazioni o a diverse fasi operative delle applicazioni stesse
• l’implementazione di un motore decisionale capace di decidere se allocare proporzionalmente le risorse o minimizzare il tempo d’e- secuzione di una applicazione fornendo più risorse e permettendo quindi all’applicazione di liberare il sistema il prima possibile • l’inclusione di tecniche basaste sul feedback e sul reinforcement
learning per adattare il modello del sistema dinamicamente.
SEEC utilizza un’infrastruttura di monitoring sviluppata dal stesso grup- po: Application Heartbeat , [40–42]. Questo framework si basa sul concetto di Heartbeat che consiste in un’indicazione del progresso dell’esecuzione di un programma verso un goal definito in termini di throughput o latenza tra Heartbeat.
Fig. 3.16: Schema concettuale del framework SEEC [38]
La Figura 3.16 fornisce uno schema concettuale della modalità di funziona- mento del framework SEEC. É possibile vedere come il run-time manager implementato in SEEC fornisca diversi livelli possibili d’adattamento. Essi variano da un uno schema di controllo ad anello chiuso fino ad un più raffinato sistema di machine learning. La scelta di utilizzare un livello
Sezione 3.4. Conclusioni 41 rispetto ad un altro dipenderà dal massimo overhead richiesto e dalle caratteristiche del modello del sistema fornito al framework. Ad esempio, nel caso in cui questo modello sia accurato, l’utilizzo delle tecniche di machine learning comporterebbe soltanto un peggioramento del tempo d’esecuzione, dovuto alla fase di training, mentre l’uso di uno dei livelli sottostanti fornirebbe gli stessi risultati ma in minor tempo. Il controllore usato in SEEC utilizza i dati forniti dal blocco Observe, quindi da Heart- beat, assieme alle informazioni fornite dai diversi livelli di controllo per decidere come cambiare l’allocazione di risorse o la configurazione dei parametri dell’applicazione. Queste operazioni verranno effettuate dal blocco di attuatori (Actuator nell’immagine).
3.4
Conclusioni
In questo capitolo sono stati illustrati alcuni lavori dello stato dell’arte nei diversi ambiti a cui fa riferimento questa tesi. Le diverse tecniche proposte variano ad esempio tra soluzioni hardware, software, statiche o dinamiche. I lavori analizzati si focalizzano spesso su problemi specifici e risultano quindi molto specializzati. Altri invece, nonostante cerchino di risolvere un problema più generale, garantiscono una certa efficienza e velocità d’esecuzione soltanto nel caso sia stato fornito un modello accurato dell’applicazione. Nonostante questa caratteristica essi non propongono nessuna strategia sul come creare questo tipo di modello. Poichè non esiste un’implementazione finale che risolva ottimamente questi problemi, abbiamo cercato di sfruttare al meglio le varie idee presenti in questo capitolo per proporre il nostro framework ARGO.
Capitolo 4
Metodologia proposta
Questo capitolo si pone l’obiettivo di descrivere la metodologia e le stra- tegie seguite durante le fasi di progettazione e di sviluppo di questo framework. La descrizione di queste idee chiave saranno molto utili per capire meglio i concetti che verranno descritti nei capitoli seguenti. Più in dettaglio verrà esaminata e definita l’architettura del framework ARGO, descrivendone componenti e usi. Verrà inoltre effettuata una suddivisione concettuale del framework di monitoring creato. Per concludere verrà de- scritta la metodologia usata per supportare la creazione e l’ottimizzazione di un’applicazione dalla fase di design fino alla sua esecuzione.
4.1
Architettura di riferimento
L’architettura di riferimento per questo lavoro di tesi è quella illustrata in Figura 4.1. In questa piattaforma è presente un Run-Time Resource manager (RTRM) come quello descritto in [4] e nel Capitolo 2. I compiti del Run-Time Resource Manager sono svolti da due diverse entità del- l’architettura: il System-Level Run-Time Resource Manager (SYS-RTRM) e un Application-Specific Run-Time Managers (AS-RTM) per ogni appli- cazione. Mentre il primo si concentra sulla allocazione delle risorse alle
Fig. 4.1: Panoramica dell’architettura di riferimento
applicazioni, il secondo è responsabile di impostare dinamicamente i loro parametri al fine di raggiungere gli obiettivi prefissati. Ogni AS-RTM si basa su due componenti principali del framework: un gestore di Operating Point (OP Manager) e una serie di Monitor. Le loro funzioni e i loro usi saranno spiegati più in dettaglio nel Capitolo 5 e 7. Come è possibile notare inoltre dalla Figura 4.1, questa architettura si basa su due concetti: i punti operativi chiamati Operating Points (OPs) e le modalità di funzio- namento, chiamate Working Modes (WMs). Gli Operating Point sono un concetto strettamente legato al dominio applicativo. Essi consistono in una struttura di base che descrive la combinazione dei diversi parametri di configurazione per l’applicazione corrente e contengono sia i parametri dell’applicazione che le metriche prodotte in fase di profiling a design-time. Queste metriche, quali il consumo di potenza o il throughput, possono essere usate per derivare un modello del comportamento dell’applicazione sotto diverse combinazioni di configurazioni. L’insieme di Operating Point
Sezione 4.1. Architettura di riferimento 45 fa parte della conoscenza minima necessaria al nostro Application-Specific Run-Time Manager per operare correttamente.
A differenza degli Operating Point, i Working Mode hanno un dominio diverso da quello applicativo. Essi infatti rappresentano comunque un insieme di scenari dell’applicazione ma hanno parametri e uso differenti. I Working Mode rappresentano la conoscenza necessaria al System-Level Run-Time Resource Manager per decidere quante risorse allocare per una precisa applicazione. Ogni Working Mode è legato ad una insieme di punti operativi e rappresenta il massimo utilizzo di risorse in quella serie di punti. Nel caso del SYS-RTRM utilizzato nel nostro lavoro di tesi le risorse controllate sono solamente CPU e memoria. Ogni Working Mode ha un valore specifico che rappresenta la preferenza di un’applicazione ad essere eseguita con tale punto rispetto ad un altro. Il numero di Working Mode è per definizione inferiore o uguale al numero di Punti Operativi. Questo capitolo tratterà in particolar modo il livello applicativo dando qualche informazione sul livello di sistema quando necessario.
Analizzando più in dettaglio l’architettura proposta è necessario fare una precisazione riguardo la parte di monitoring. La nostra idea è stata quella di rendere il framework il più generale possibile ed usabile sia in fase di progettazione che d’implementazione. Inoltre, nonostante il lavoro sia stato svolgo nell’ambito di un particolare Resource Manager, abbiamo cercato di rendere il tutto più indipendente possibile. Per questo motivo abbiamo fornito anche delle funzionalità per monitorare non solo le prestazioni pure dell’applicazione ma anche altre caratteristiche più legate al sistema e alle risorse. La Figura 4.2 rappresenta graficamente la suddivisione logica e concettuale dei nostri monitor. Com’è possibile vedere dall’immagine, i monitor sono divisi logicamente in due gruppi: un gruppo di monitor orientato all’applicazione (MOA) ed uno orienta- to al sistema e alle risorse in generale (MOR). La classe base Monitor, istanziabile ed usabile come monitor generale, è stata invece considerata neutrale poiché i suoi usi sono dipendenti dal tipo di dato contenuto.
Fig. 4.2: Panoramica dell’architettura di monitoring
Le due tipologie di monitor sopracitate si differenziano per il loro uso; i monitor MOA si occupano di monitorare in generale metriche che sono tipiche dell’applicazione stessa e che possono essere influenzate in qualche modo tramite la modifica di alcuni parametri interni. In questo caso questi monitor verranno usati sia in fase di design per profilare e caratterizzare il comportamento dell’applicazione, sia in fase d’esecuzione per modifi- carne dinamicamente il comportamento e rispondere a variazioni delle performance dell’applicazione stessa.
Per descrivere il comportamento e gli utilizzi dei monitor MOR è meglio effettuare una breve precisazione riguardo a due possibili scenari d’utilizzo del nostro framework. Il primo è quello di un sistema in cui il System-Level Resource Manager si occupa sia di scegliere una allocazione adatta delle risorse dei processi che del monitorare e controllare il superamento di tali limiti. Il secondo invece, è dato da Resource Manager