Methodologies for mapping and scheduling applications on multicore systems
Loading...
Date
2025-09-01
Authors
Εμερετλής, Ανδρέας
Journal Title
Journal ISSN
Volume Title
Publisher
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 scheduling on heterogeneous multicore systems, offering practical tools for solving large-scale, real-world applications with provable optimality guarantees.
Description
Keywords
Application mapping and scheduling, Task scheduling, Multicore systems, Heterogeneous systems, Integer linear programming, Constraint programming, Benders decomposition