ParadisEO vs HyperSpark : analysis and benchmarking of two frameworks for distributed metaheuristics

Computing power has grown exponentially following Moore's law and it has given rise to opportunities to leverage commodity hardware by executing computationally intensive operation in a parallel fashion. Nonetheless, setting up a distributed computation cluster used to be a time consuming process that required expert knowledge. Developing applications capable of running on those clusters also required in-depth understanding of the frameworks available. In this work, I will analyze under several points of view two frameworks; one of them is ParadisEO, a C++ white-box object-oriented framework dedicated to design and execution of metaheuristics that supports parallel and distributed architectures using the Message Passing Interface (MPI), a popular standard inside the High Performance Computing community. Recently, there have been important developments in open source systems capable of handling distributed problems in an efficient way with a higher level application programmer interface (API), while providing cluster management tools aiming at reducing the level of expertise required to develop applications for those systems. HyperSpark, the second reference framework considered in the comparison, is a general, extensible and portable solution for scalable execution of user-defined, computationally-intensive algorithms build on top of Apache Spark and developed at Politecnico di Milano. For both platforms I will report the efforts required to develop a solution for a well-known scheduling optimisation problem: Permutation Flow Shop Problem (PFSP). I will as well expand into the empirical results obtained on 120 instances of a common benchmark for this type of problem introduced by Talliard. The applications developed have been evaluated using the relative difference to the best solution found. The overhead introduced by each platform will also be analysed.

Negli anni, la potenza di calcolo disponibile in funzione del cost è cresciuta in modo esponenziale seguendo la legge di Moore. In particolare è possibile disporre, a costi relativamente contenuti, di commodity hardware di buona qualità collegato tramite reti ad alta velocità. Questa situazione ha portato alla nascita di piattaforme che semplificano la realizzazione di applicazioni parallele di calcolo intensivo Ciò nonostante, la realizzazione di un cluster per il calcolo distribuito restea un'operazione tutt'altro che semplice e richiede utenti esperti. Allo stesso modo anche lo sviluppo di applicazioni per questi sistemi è complesso e richiede di l'utilizzo di strumenti (framework) con una curve di apprendimento ripide. Lo scopo di questo lavoro è analizzare sotto diversi punti di vista due piattaforme; la prima, ParadisEO, è un framework orientato agli oggetti, sviluppato in C++, dedicato alla progettazione ed esecuzione di metaeuristiche su architetture parallele e distribuite utilizzando la interfaccia per il trasporto dei messagi (MPI). MPI è da considerarsi uno standard all'interno della communità di calcolo ad alte prestazioni (HPC). HyperSpark, il secondo framework considerato, è una soluzione generale, estensibile e portatile per l'esecuzione scalabile e parallela di algoritmi di ottimizzazione definiti dall'utente; è stato realizzato sviluppato presso il Politecnico di Milano e funziona su Apache Spark. Recentemente, infatti, ci sono stati importanti sviluppi nei sistemi open source in grado di gestire esecuzioni distribuite in modo efficiente con un interfaccia di programazzione di alto livello (API), fornendo strumenti di gestione dei cluster che riducono il livello di conoscenza e competenza necessarie per sviluppare applicazioni parallela; Spark è uno di questi sistemi, è stato realizzato per supportare applicazioni Big Data ma ha un paradigma abbastanza flessibile da permettere la realizzazione anche di applicazioni generiche. Per entrambe le piattaforme verranno descritte le operazioni necessare per sviluppare una soluzione per un problema di ottimizazione in particolare: Permutation Flow Shop Problem (PFSP). Inoltre verranno presentati e commentati alguni risultati empirici ottenuti su un benchmark di 120 istanze di riferimento comune per questo tipo di problema (istanze di Talliard). Le applicazioni sviluppate sono state confrontate usando come indice la differenza percentuale relativa rispetto alla migliore soluzione trovata. L'overhead introdotto da ogni piattaforma verrà anche misurato e analizzato.