HyperSpark : a framework for scalable execution of computationally intensive algorithms over Spark

Nowadays computing platforms are available to many companies and individuals wanting to process vast amounts of data sets. With the term Big Data we refer to the analysis of huge datasets, allowing the extraction of information of utmost importance for business purposes. The focus of Big Data community has turned to providing high performance over the cluster of computing resources that was previously used only for data-intensive computations. A newly developed technology, Apache Spark, with its characteristic property of executing computation and data-processing in main memory, unconsciously allowed users to execute computationally-intensive algorithms in a distributed fashion. For solution quality considerations, a common approach entails instantiating multiple parallel user algorithms, as long as the computational time overhead does not surpass the allowed time limit. Such a common technique should provide every user a way to build and run custom algorithms in parallel, at the same time ensuring fault tolerance and out of the box scalability. In this work we describe HyperSpark - a general, extensible and portable framework for scalable execution of user-defined, computationally-intensive algorithms over the cluster of commodity hardware. Our goal is the utilisation of computing resources of the whole cluster in order to deliver high-performance (i.e., solution quality) in a limited amount of computational time. The parallel algorithm execution, fault-tolerance, data distribution, cooperation between algorithms and results aggregation are provided by the underlying technology and the framework in a very transparent way to the user. The ground case for the conducted experiments is Permutation Flow Shop Problem (PFSP), an extremely hard optimisation problem from scheduling theory that can not be solved optimally with conventional methods when limited time is provided. Together with the framework we provide a library for distributed solving of PFSP, that contains many efficient approximate algorithms, known as (meta- )heuristics. The preliminary tests show the encouraging results. Further improvements could be gained by taking into account an asynchronous communication between algorithms, which can greatly decrease the computational time overhead caused by the introduction of unnecessary synchronisation points.

Al giorno d’oggi molte compagnie e singoli professionisti hanno a disposizione piattaforme di calcolo per il processamento di grandi quantità di dati. Con il termine Big Data si intende l’insieme di processi e strumenti che permettono l’analisi di basi di dati di grandissime dimensioni; l’obiettivo finale consiste nell’estrazione di informazioni di grande importanza (business, sicurezza, ecc.). L’interesse della comunità di Big Data si è concentrato negli ultimi anni nell’offrire agli utenti piattaforme non sono dedicate all’analisi di date ma che forniscano allo stesso tempo alte prestazioni di calcolo. Tra le nuovo proposte tecnologiche in quest’ambito, Apache Spark è una delle più promettanti; questo strumento permette agli utenti di usufruire un paradigma di programmazione più completo e di un set di strutture distribuite efficienti, tale da poter permettere la realizzazione e l’esecuzione di applicazioni distribuite sia per l’analisi di dati sia per il calcolo distribuito. Per quanto riguarda il calcolo distribuito, in questa tesi abbiamo utilizzato Spark per realizzare un framework in cui molti algoritmi di ottimizzazione (CPU intensive) possano essere eseguiti in parallelo e sincronizzati per poter affrontare con successo problemi di ottimizzazione complessi. Spark permette in maniera trasparente il deployment degli esecutori e la loro comunicazione, inoltre siccome per la particolare categoria di algoritmi considerati i dati da gestire sono di piccole dimensioni e possono essere distribuiti con il codice, Spark permette anche una scalabilità praticamente illimitata degli algorimi. L’altra faccia della medagglia è sicuramente l’altro costo, in termini di tempo, che è richiesto dal framework per poter garantire i suoi servizi. In questa tesi, presentiamo HyperSpark, un framework generale ed estendibile che permette di realizzare ed eseguire algorimi paralleli ed estremamente scalabili su cluster di hardware non specializzato. Il framwork è stato pensato, in particolare, per permettere l’esecuzione parallela e la comunizazione all’interno di un’applicazione distribuita per l’ottimizzazione. L’obiettivo è quello di realizzare uno strumento flessibile ed indipendente dal harwdare a disposizione e dalla sua configurazione per realizzare applicazioni distribuite ad alte prestazioni. HyperSpark si basa su Spark per la (trasparente all’utente) distribuzione del codice eseguibile tra i nodi, per la relativa esecuzione, la distribuzione dei dati, la fault-tolerance, la cooperazione fra i nodi e l’aggregazione dei risultati. HyperSpark è stato quindi utilizzato per realizzare una libreria di algoritmi euristici e metaeuristici dedicati all’ottimizzazione del problema di Permutation Flow Shop (PFSP), un problema NP-hard per il quale un approccio esatto non è possibile se non per casi molto piccoli. All’interno di tale libreria sono presenti alcuni dei più conosciuti algoritmi per il PFSP. Una campagna preliminare di test è stata realizzata allo scopo di verificare la validità dell’approccio incarnato in HyperSpark sia in termini di overhead che come strumento per realizzare algoritmi competitivi rispetto allo stato dell’arte. I risultati di tali esperimenti sono incoraggianti sebbene il paradigma basato sulla sincronizzazione, imposto dalla attuale versione di Spark è evidente fonte di overhead. Recentemente però, sono apparse in letteratura delle soluzioni che permettono di implementare un livello di comunicazione asincrona tra gli esecutori in Spark. HyperSpark potrebbe in futuro adottare un approccio simile riducendo il punti di sincronizzazione al fine di ottenere un miglioramento globale delle prestazioni.