Methodologies for mapping and scheduling applications on multicore systems

Abstract

Mapping and scheduling applications on multicore systems is a fundamental problem in parallel computing, directly impacting performance, energy efficiency, and resource utilization. While homogeneous architectures allow uniform task execution, the increasing prevalence of heterogeneous multicore systems—comprising processing elements with diverse performance characteristics, instruction sets, and communication costs—introduces significant additional complexity. In such systems, determining both the mapping of tasks to cores and the execution schedule requires accounting for heterogeneity in processing speeds, communication delays, and task precedence constraints. Static scheduling is particularly valuable in domains where applications are well-defined in advance and predictable execution is critical, such as embedded real-time systems, signal processing pipelines, and scientific workflows. In these contexts, high-quality static schedules enable predictable performance, reduced runtime decision overhead, and improved system reliability. However, producing such schedules is computationally challenging: even without heterogeneity, task scheduling with precedence and resource constraints is NP-hard, and the addition of varying processing capabilities and communication delays further increases problem complexity. This makes the design of efficient and scalable exact solution methods both necessary and nontrivial.Exact optimization methods are essential for deriving provably optimal schedules, which serve as performance benchmarks and guide the evaluation of heuristic methods. However, conventional exact approaches—such as monolithic Integer Linear Programming (ILP) formulations—often fail to scale beyond small or medium-sized instances, especially when heterogeneity and communication costs are modeled in detail. This limitation motivates the exploration of alternative exact frameworks capable of maintaining optimality guarantees while improving scalability. This thesis introduces a Logic-Based Benders Decomposition (LBBD) framework tailored to heterogeneous task scheduling. The proposed model decomposes the problem into an assignment (master problem) and a sequencing (subproblem) component, enabling more efficient search and better exploitation of problem structure compared to monolithic formulations.It further proposes a set of enhancements that strengthen bounds and accelerate convergence. These include stronger Benders cuts, execution window refinement, processor overload prevention, and dependency-aware relaxations, which together reduce the search space and improve both solution quality and computational efficiency. Finally, it develops advanced strategies that combine the complementary strengths of decomposition and monolithic formulations. These include speculative bound tightening, a three-stage LBBD procedure, and a hybrid ILP--LBBD integration, each aimed at improving performance in the later stages of the search and enabling the solution of more challenging instances.Extensive computational experiments on diverse Directed Acyclic Graph (DAG) benchmarks, covering both communication-agnostic and communication-aware settings, demonstrate that the proposed methods consistently outperform conventional ILP models and baseline LBBD, achieving higher scalability, faster convergence, and tighter bounds. The contributions of this work advance the state of the art in exact mapping and schedulingon heterogeneous multicore systems, offering practical tools for solving large-scale, real-world applications with provable optimality guarantees.

Η απεικόνιση και ο χρονοπρογραμματισμός εφαρμογών σε πολυπύρηνα συστήματα αποτελεί θεμελιώδες πρόβλημα στην παράλληλη επεξεργασία, με άμεσο αντίκτυπο στην απόδοση, την ενεργειακή αποδοτικότητα και την αξιοποίηση των πόρων. Ενώ οι ομογενείς αρχιτεκτονικές επιτρέπουν ομοιόμορφη εκτέλεση των εργασιών, η αυξανόμενη διάδοση των ετερογενών πολυπύρηνων συστημάτων, που αποτελούνται από υπολογιστικές μονάδες με διαφορετικά χαρακτηριστικά απόδοσης, σύνολα εντολών και κόστη επικοινωνίας, εισάγει πρόσθετη πολυπλοκότητα. Σε τέτοια συστήματα, ο καθορισμός τόσο της ανάθεσης των εργασιών στους πυρήνες όσο και του χρονοπρογραμματισμού εκτέλεσης απαιτεί τη συνεκτίμηση της ετερογένειας στις ταχύτητες επεξεργασίας, στις καθυστερήσεις επικοινωνίας και στους περιορισμούς προτεραιότητας μεταξύ εργασιών. Ο στατικός χρονοπρογραμματισμός είναι ιδιαίτερα πολύτιμος σε τομείς όπου οι εφαρμογές είναι προκαθορισμένες και η προβλέψιμη εκτέλεση είναι κρίσιμη, όπως στα ενσωματωμένα συστήματα πραγματικού χρόνου, στις εφαρμογές ψηφιακής επεξεργασίας σήματος και στις επιστημονικές ροές εργασίας. Σε αυτά τα πλαίσια, τα υψηλής ποιότητας στατικά χρονοπρογράμματα εξασφαλίζουν προβλέψιμη απόδοση, μειώνουν το κόστος αποφάσεων κατά τη διάρκεια εκτέλεσης και βελτιώνουν την αξιοπιστία του συστήματος. Ωστόσο, η παραγωγή τέτοιων λύσεων χρονοπρογραμματισμού είναι υπολογιστικά απαιτητική: ακόμη και χωρίς ετερογένεια, ο χρονοπρογραμματισμός εργασιών με περιορισμούς προτεραιότητας και πόρων είναι NP-hard, ενώ η προσθήκη διαφορετικών δυνατοτήτων επεξεργασίας και καθυστερήσεων επικοινωνίας αυξάνει περαιτέρω την πολυπλοκότητα. Αυτό καθιστά τον σχεδιασμό αποδοτικών και επεκτάσιμων ακριβών μεθόδων επίλυσης τόσο αναγκαίο όσο και μη τετριμμένο. Οι ακριβείς μέθοδοι βελτιστοποίησης είναι απαραίτητες για την παραγωγή αποδεδειγμένα βέλτιστων λύσεων χρονοπρογραμματισμού, τα οποία χρησιμεύουν ως ορόσημα απόδοσης και καθοδηγούν την αξιολόγηση ευριστικών μεθόδων. Ωστόσο, οι συμβατικές ακριβείς προσεγγίσεις, όπως οι μονολιθικές διατυπώσεις Ακέραιου Γραμμικού Προγραμματισμού (ILP), συχνά αδυνατούν να επεκταθούν πέρα από μικρά ή μεσαίου μεγέθους προβλήματα, ιδίως όταν η ετερογένεια και τα κόστη επικοινωνίας μοντελοποιούνται λεπτομερώς. Αυτός ο περιορισμός υποκινεί την εξερεύνηση εναλλακτικών ακριβών πλαισίων που μπορούν να διατηρήσουν τις εγγυήσεις βέλτιστου αποτελέσματος, βελτιώνοντας ταυτόχρονα την επεκτασιμότητα. Η παρούσα διατριβή εισάγει ένα πλαίσιο λογικού διαχωρισμού τύπου Benders (Logic-Based Benders Decomposition, LBBD), προσαρμοσμένο στην ανάθεση και τον χρονοπρογραμματισμό εργασιών σε ετερογενή συστήματα. Το προτεινόμενο μοντέλο διαχωείζει το πρόβλημα σε ένα σκέλος ανάθεσης (κύριο πρόβλημα) και ένα σκέλος χρονοπρογραμματισμού (υποπρόβλημα), επιτρέποντας αποδοτικότερη αναζήτηση και καλύτερη εκμετάλλευση της δομής του προβλήματος σε σύγκριση με τις μονολιθικές διατυπώσεις. Επιπλέον, προτείνει ένα σύνολο βελτιώσεων που ενισχύουν τα όρια και επιταχύνουν τη σύγκλιση. Αυτές περιλαμβάνουν ισχυρότερες τομές Benders, βελτίωση των παραθύρων εκτέλεσης, αποτροπή υπερφόρτωσης επεξεργαστών και χαλαρώσεις βασισμένες στις εξαρτήσεις, οι οποίες από κοινού περιορίζουν τον χώρο αναζήτησης και βελτιώνουν τόσο την ποιότητα των λύσεων όσο και την υπολογιστική αποδοτικότητα. Τέλος, αναπτύσσει προχωρημένες στρατηγικές που συνδυάζουν τα συμπληρωματικά πλεονεκτήματα του διαχωρισμού και των μονολιθικών διατυπώσεων. Αυτές περιλαμβάνουν τη υποθετική σύσφιξη ορίων, μια διαδικασία πολλαπλών σταδίων βασισμένη στη μέθοδο του LBBD και μια υβριδική ενσωμάτωση ILP–LBBD, καθεμία από τις οποίες στοχεύει στη βελτίωση της απόδοσης στα μεταγενέστερα στάδια της αναζήτησης και στην επίλυση πιο απαιτητικών περιπτώσεων. Εκτενείς υπολογιστικές δοκιμές σε ένα ευρύ φάσμα ακυκλικών κατευθυνόμενων γράφων (Directed Acyclic Graphs – DAG), που καλύπτουν τόσο περιπτώσεις όπου δεν λαμβάνεται υπόψη η καθυστέρηση επικοινωνίας μεταξύ των εργασιών όσο και παραμέτρους με επίγνωση της επικοινωνίας, δείχνουν ότι οι προτεινόμενες μέθοδοι υπερτερούν σταθερά των συμβατικών μοντέλων ILP και του βασικού LBBD, επιτυγχάνοντας μεγαλύτερη επεκτασιμότητα, ταχύτερη σύγκλιση και αυστηρότερα όρια. Οι συνεισφορές αυτής της εργασίας προάγουν την επιστημονική γνώση ως προς το πρόβλημα της ακριβούς ανάθεσης και χρονοπρογραμματισμού εφαρμογών σε ετερογενή πολυπύρηνα συστήματα, προσφέροντας πρακτικά εργαλεία για την επίλυση μεγάλων και πραγματικών εφαρμογών με αποδεδειγμένες εγγυήσεις βέλτιστου αποτελέσματος.