Βελτιστοποίηση ροών εργασιών για ανάλυση δεδομένων

Abstract

The big data analysis with the help of automated mechanisms attracts a lot of attention because of the growing need for end-to-end processing of this data. Modern workflows for data analysis, or simply data flows, are adopted in order to process and analyze large volumes of data. However, the data flows become more and more complex and operate in highly dynamic parallel, distributed and heterogeneous environments. This thesis deals with the data flow cost-based optimization and propose task ordering techniques that aim to minimize the total execution cost of the data flow tasks. Additionally, a set of engine selection techniques are proposed for task allocation to specific heterogeneous engines that aim to minimize the flow execution cost. More specifically, the contributions of the thesis are summarized as follows: (i) a thorough survey of data flow optimization research area is presented, (ii) they are presented effective accurate algorithms for finding the optimal order of tasks that minimize the total cost of the flow, (iii) they are proposed for the same problem a set of effective heuristic algorithms that scale for large number of data flow tasks, (iv) a set of effective solutions with low overhead for engine selection among multiple heterogeneous engines is proposed, (v) the proposed techniques are evaluated against the best of the techniques of the state-of-art and finally, (vi) it is proposed a cost model that aims to accurately reflect the response time of a data flow that is executed in parallel.

Η αύξηση των δεδομένων με ραγδαίο ρυθμό συντέλεσε στην ανάγκη για την ανάπτυξη αυτοματοποιημένων μηχανισμών επεξεργασίας και ανάλυσης δεδομένων. Γι' αυτό το λόγο, υιοθετήθηκαν οι ροές εργασιών για ανάλυση δεδομένων (ή πιο απλά οι ροές δεδομένων). Όμως, οι ροές δεδομένων είναι αρκετά πολύπλοκες και γίνονται ολοένα πολυπλοκότερες, καθώς η εκτέλεσή τους πραγματοποιείται σε παράλληλα, κατανεμημένα και ετερογενή περιβάλλοντα. Η παρούσα διατριβή πραγματεύεται τη βελτιστοποίηση των ροών δεδομένων μέσα από την πρόταση τεχνικών αναδιάταξης των εργασιών των ροών με σκοπό τη μείωση του συνολικού κόστους εκτέλεσής τους και της επιλογής των μηχανών εκτέλεσης των εργασιών. Πιο αναλυτικά, οι συνεισφορές της διατριβής κωδικοποιούνται ως εξής: (i) παρουσιάζεται μία συστηματική ανασκόπηση του χώρου της βελτιστοποίησης των ροών δεδομένων, (ii) προτείνονται αποδοτικοί ακριβείς αλγόριθμοι για την εύρεση της βέλτιστης διάταξης των εργασιών για τη μείωση του κόστους της ροής, (iii) προτείνονται, για το ίδιο πρόβλημα, αποδοτικοί ευριστικοί κλιμακώσιμοι αλγόριθμοι, (iv) προτείνονται αποδοτικές λύσεις χαμηλού επιπλέον κόστους για την επιλογή μηχανών εκτέλεσης σε περιβάλλοντα με πολλές εναλλακτικές, (v) αξιολογούνται οι προτάσεις μέσω σύγκρισής τους έναντι των καλύτερων υπαρχόντων τεχνικών στη βιβλιογραφία, και τέλος, (vi) προτείνεται ένα μοντέλο κόστους που περιγράφει ακριβέστερα το χρόνο εκτέλεσης των ροών σε σύγχρονες μηχανές.