abstract
- Directed acyclic graphs are commonly used to model scientific workflows, by expressing dependencies between tasks, as well as the resource requirements of the workflow. As a special case, rooted directed trees occur in several applications. Since typical workflows are modeled by huge trees, it is crucial to schedule them efficiently. We investigate the partitioning and mapping of tree-shaped workflows on target architectures where each processor can have a different memory size. Our three-step heuristic adapts and extends previous work for homogeneous clusters. In particular, we design a novel algorithm to assign subtrees to processors with different memory sizes, and we show how to select appropriate processors when splitting or merging subtrees. The experiments demonstrate that exploiting the heterogeneity reduces the makespan significantly compared to the state of the art for homogeneous memories. This work is partially supported by Collaborative Research Center (CRC) 1404 FONDA - Foundations of Workflows for Large-Scale Scientific Data Analysis, which is funded by German Research Foundation (DFG). Corresponding author: Svetlana Kulagina. Access provided by Humboldt Universität zu Berlin. Download conference paper PDF Similar content being viewed by others Algorithms for tree-shaped task partition and allocation on heterogeneous multiprocessors Article 22 March 2023 Precise makespan optimization via hybrid genetic algorithm for scientific workflow scheduling problem Article Open access 08 July 2023 Fast tree aggregation for consensus hierarchical clustering Article Open access 20 March 2020 Explore related subjects Discover the latest articles, books and news in related subjects, suggested using machine learning. Combinatorial Libraries Data Structures Enterprise Architecture Graph Theory Register-Transfer-Level Implementation Processor Architectures Task Scheduling in Cloud Computing Environments