Ricerca | Progetti Finanziati

ALGORITMI DI BIN-PACKING SEMIONLINE RELAXED PER IL CLOUD COMPUTING

Esistono diversi modelli di Bin-Packing semionline: bounded-repacking, lookahead, preordering, conoscenza di OPT, tra questi. In particolare, alcuni di essi contraddicono direttamente la definizione di bin-packing online, perché permettono di assegnare un elemento a un bin usando conoscenze future su elementi non ancora arrivati, mentre altri modelli semplicemente riorganizzano il packing attuale senza sfruttare nessuna conoscenza futura. Con questa ricerca si vuole, innanzitutto, classificare gli algoritmi semionline sulla base della loro distanza dalla definizione di online “puro”.Si vuole, inoltre, ridefinire il modello di bin packing semionline detto “relaxed”, introdotto da Gambosi, Postiglione e Talamo in SIAM J. Comput., vol 30 (5), 2000, sulla base del nuovo criterio di classificazione degli algoritmi di bin-packing introdotto da Balogh, Bekesi, Galambos e Reinelt, in SIAM J. Comput., vol 38 (1), 2008 e che prevede la presenza di due componenti, lo scheduler e il loader, i cui comportamenti definiscono la tipologia di algoritmo.Si vuole, inoltre, verificare l'applicabilità dei modelli semionline alla gestione delle risorse in un ambiente di cloud computing. Noi riteniamo che, tra tutti, proprio il modello relaxed, grazie alla operazione di grouping, sia particolarmente adatto.Si vorrebbe anche migliorare le prestazioni di tempo degli algoritmi semionline con un numero costante di spostamenti (attualmente pari a 1,33 per algoritmi non lineari e 1.5 per algoritmi lineari).Il modello di Bin Packing Relaxed (il cui miglior algoritmo è 1.333) permette di ottenere prestazioni molto vicine a quelle degli algoritmi offline (1.222) pur mantenendo una sostanziale appartenenza alla classe online (il cui miglior algoritmo è 1.58). Relaxed impone di assegnare un elemento a un bin, non appena esso arriva, senza sfruttare nessuna conoscenza futura, ma semplicemente riorganizzando il packing attuale tramite due operazioni: moving e grouping. Relaxed permette, in un tempo successivo al suo arrivo, di spostare un elemento verso altri bin. Ovviamente il costo dell’operazione è conteggiato nelle prestazioni dell’algoritmo e, inoltre, ad ogni passo, il numero massimo di spostamenti effettuabili è limitato da una (piccola) costante.Il grouping permette di raggruppare elementi di dimensioni molto ridotte in un unico gruppo che verrà trattato come un’unica unità indivisibile. Si noti che, nel bin-packing, tale operazione è possibile e conveniente. Ad esempio per caricare una flotta di camion è utile imballare oggetti piccoli in un’unica scatola e da quel momento in poi considerarla come un unico elemento.Il modello Relaxed funziona molto bene in tutte le situazioni in cui la lista di input non è nota in anticipo (potrebbe essere infinita) e ciascun elemento (che potrebbe arrivare con notevole ritardo rispetto al precedente) deve essere elaborato immediatamente, mentre il rendimento garantito deve essere mantenuto per il sottoinsieme di elementi fino a quel momento arrivati. Il modello Relaxed permette di sfruttare il tempo di inattività tra l’arrivo di due elementi consecutivi di ingresso. Più in dettaglio, esso è particolarmente adatta quando il tempo trascorso tra due elementi consecutivi è > HK, dove il costo massimo per spostare un elemento e K è il numero massimo di movimenti ammessi ad ogni passo è H.Un'importante applicazione del modello Relaxed potrebbe essere nel mondo cloud. In un cloud, il movimento di dati da un dispositivo (disco) ad un altro è costoso ed è, potenzialmente, una fonte di errori, ma è necessario per mantenere bilanciato il peso di ciascun dispositivo. Ovviamente, se alcune informazioni vengono perse a causa di spostamento dei dati, esse possono essere recuperate grazie ad operazioni di rollback, che sono, però, molto costose. Il modello Relaxed dovrebbe permettere di ottenere rendimenti molto buoni, in termini di tempo di esecuzione, ma anche di ridurre al minimo il rischio di perdita di dati.