Οptimization of scheduling in workflow management systems using reinforcement learning

Abstract

A workflow is defined as the execution of a sequence of tasks, the order of which is determined by data interdependencies and the target outcome. The execution of workflows can be managed by a Workflow Management System (WMS) which undertakes the scheduling of tasks, handling of failures and monitoring health status. Scheduling workflows involves mapping tasks to available execution sites in respect to a cost function that optimizes an objective such as the total execution time. In the era of multi-core architectures, accelerated computing is largely driven by scaling across distributed resources. For a WMS, identifying and exploiting opportunities for parallelism becomes a critical necessity. At the same time, distributed execution introduces new challenges as workflow execution should be agnostic to the software and hardware on the execution sites. Additionally, machine learning based approaches to scheduling optimization have not been explored to the same extent as heuristic algorithms. The aim of this dissertation is to exploit opportunities for parallelism and leverage machine learning in scheduling scientific workflows across distributed heterogeneous execution sites. The outcome of this endeavor is Hermes, a novel WMS capable of exploiting opportunities for parallelism, supporting distributed execution and leveraging machine learning to profile tasks and computational resources and perform scheduling decisions. Although capable of supporting any workflow, Hermes is evaluated with bioinformatics workflows as they comprise most of its user base. A methodology is proposed for addressing data and pipeline parallelism by compartmentalizing computational flows into pipelines with minimal data interdependencies. The methodology is applicable to workflows with multiple sequential processes that can be applied individually on fragments of the original input. A comparison against a high-performance framework for distributed computing is performed evidencing reduced execution time and costs. Hermes provides an environment agnostic solution to seamlessly create, share and reproducibly execute scientific workflows. Distributed execution is made possible via container-based virtualization technologies that accomplish standardization of the execution environment. Hermes employs binary classification models to predict task failures and regression models for predicting task runtime given variable task input sizes and execution sites of varying computational capabilities. The results confirm that useful and directional metrics can be achieved that can influence scheduling decisions. The use of seq2seq neural architectures is proposed for modelling task to execution site scheduling decisions. Expected failure probabilities and runtimes of combinations of tasks mapped to execution sites are the inputs to the neural architecture and the outputs are the selected mappings. As generating high quality labeled data can be prohibitively expensive when dealing with NP-Hard problems, supervised learning can be challenging. For this reason, a reinforcement learning training approach is adopted. Hermes implements an environment for distributed workflow execution simulation which can simulate not only task execution times but also task failures and the cost of network communications. The trained neural network is evaluated at performing scheduling decisions when executing real workflows. As demonstrated, it significantly outperforms traditional scheduling algorithms used in WMSes in execution time, failed tasks, and size of network traffic.

Μια ροή διεργασιών (ΡΔ) ορίζεται ως η εκτέλεση μιας σειράς διεργασιών, η σειρά των οποίων καθορίζεται από τις αλληλεπιδράσεις δεδομένων και το τελικό αποτέλεσμα. Η εκτέλεση ΡΔ μπορεί να γίνει μέσω ενός Συστήματος Διαχείρισης Διεργασιών (ΣΔΔ) το οποίο αναλαμβάνει την χρονοδρομολόγηση των διεργασιών, τον χειρισμό των βλαβών και την εποπτεία του συστήματος. Η χρονοδρομολόγηση ΡΔ περιλαμβάνει την ανάθεση διεργασιών σε υπολογιστικούς πόρους με σκοπό την βελτιστοποίηση μιας συνάρτησης κόστους όπως αυτή του συνολικού χρόνου εκτέλεσης. Η επιτάχυνση της εκτέλεσης ΡΔ καθοδηγείται σε μεγάλο βαθμό από τον παραλληλισμό και την χρήση κατανεμημένων πόρων. Για τον λόγο αυτό, η επίτευξη παραλληλισμού γίνεται καθοριστική. Ταυτόχρονα, η κατανεμημένη εκτέλεση εισάγει νέες προκλήσεις καθώς η εκτέλεση ΡΔ θα πρέπει να είναι πλήρως αποσπασμένη από το λογισμικό και το υλικό των υπολογιστικών πόρων. Επιπλέον, οι προσεγγίσεις μηχανικής μάθησης για τη βελτιστοποίηση της χρονοδρομολόγησης ΡΔ δεν έχουν εξερευνηθεί στον ίδιο βαθμό με τους ευρετικούς αλγορίθμους. Σκοπός της παρούσας διατριβής είναι η εκμετάλλευση ευκαιριών παραλληλισμού κατά την εκτέλεση και η χρήση μηχανικής μάθησης για το πρόβλημα της χρονοδρομολόγησης σε ΡΔ επιστημονικών εφαρμογών που εκτελούνται σε κατανεμημένους ετερογενείς υπολογιστικούς πόρους. Το αποτέλεσμα αυτής της προσπάθειας είναι το ΣΔΔ Hermes, ένα καινοτόμο ΣΔΔ ικανό να εκμεταλλευτεί ευκαιρίες παραλληλισμού, υποστηρίζοντας την απρόσκοπτη κατανομή της εκτέλεσης σε κάθε κατανεμημένη ομάδα υπολογιστικών πόρων. Ταυτόχρονα, χρησιμοποιεί μηχανική μάθηση για την δημιουργία προφίλ διεργασιών και υπολογιστικών πόρων και για την εκτέλεση αποφάσεων χρονοδρομολόγησης. Παρόλο που το ΣΔΔ Hermes μπορεί να υποστηρίξει οποιαδήποτε ΡΔ, αξιολογείται χρησιμοποιώντας ΡΔ από το πεδίο της βιοπληροφορικής, καθώς αποτελούν το μεγαλύτερο μέρος της βάσης χρηστών του. Προτείνεται μια μεθοδολογία διαχείρισης δεδομένων, με σκοπό την επίτευξη παραλληλισμού δεδομένων, διαχωρίζοντας την υπολογιστική ροή σε υπό-ροές με ελάχιστες αλληλεπιδράσεις δεδομένων. Η μεθοδολογία εφαρμόζεται σε κατηγορίες ΡΔ με μεγάλο αριθμό διαδοχικών βημάτων που μπορούν να εφαρμοστούν μεμονωμένα σε τμήματα των δεδομένων εισόδου. Οι βελτιώσεις της απόδοσης της προτεινόμενης προσέγγισης αξιολογούνται χρησιμοποιώντας ΡΔ από το πεδίο της βιοπληροφορικής. Πραγματοποιείται σύγκριση με ένα σύστημα εκτέλεσης ΡΔ υψηλών επιδόσεων για κατανεμημένα υπολογιστικά περιβάλλοντα η οποία αποδεικνύει μειωμένο χρόνο και κόστος εκτέλεσης. Το ΣΔΔ Hermes προσφέρει μια αποσπασμένη από το περιβάλλον εκτέλεσης μεθοδολογία για την απρόσκοπτη δημιουργία, κοινή χρήση και αναπαραγωγή των ΡΔ επιστημονικών εφαρμογών. Η κατανεμημένη εκτέλεση καθίσταται δυνατή μέσω τεχνολογιών εικονικοποίησης που επιτυγχάνουν την τυποποίηση του περιβάλλοντος εκτέλεσης. Tο ΣΔΔ Hermes χρησιμοποιεί μοντέλα μηχανικής μάθησης για να προβλέψει την πιθανότητα αποτυχίας και τον χρόνο εκτέλεσης διεργασιών. Τα αποτελέσματα επιβεβαιώνουν ότι είναι δυνατή η εκπαίδευση μοντέλων χρησιμοποιώντας αρχεία καταγραφής εκτέλεσης διεργασιών και ότι μπορούν να επιτευχθούν χρήσιμα αποτελέσματα που μπορούν να κατευθύνουν αποφάσεις χρονοδρομολόγησης. Η χρήση των seq2seq νευρωνικών αρχιτεκτονικών προτείνεται για τη μοντελοποίηση του προβλήματος χρονοδρομολόγησης. Οι είσοδοι του νευρωνικού δικτύου είναι οι αναμενόμενες πιθανότητες αποτυχίας και οι χρόνοι εκτέλεσης των διεργασιών εκτελούμενων σε καθένα από τους διαθέσιμους υπολογιστικούς πόρους. Η νευρωνική αρχιτεκτονική εκπαιδεύεται με ενισχυτική μάθηση σε περιβάλλον προσομοίωσης. Το εκπαιδευμένο νευρωνικό δίκτυο ενσωματώνεται στο ΣΔΔ Hermes με σκοπό να χρησιμοποιηθεί στη λήψη αποφάσεων χρονοδρομολόγησης κατά την εκτέλεση πραγματικών ΡΔ. Η προτεινόμενη προσέγγιση ξεπερνά σημαντικά τους παραδοσιακούς αλγόριθμους χρονοδρομολόγησης που χρησιμοποιούνται σε ΣΔΔ.