Back to search

University of Patras

Methodologies for mapping and scheduling applications on multicore systems

Abstract

dc:description

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.

Degree

thesis:*
Grantor dc:publisher
University of Patras
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Emeretlis, Andreas
  • Εμερετλής, Ανδρέας

Subjects

dc:subject × 21

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/59799

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Emeretlis, Andreas; Εμερετλής, Ανδρέας. Methodologies for mapping and scheduling applications on multicore systems. University of Patras, 2025. http://hdl.handle.net/10442/hedi/59799