HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Partitioning tree-shaped task graphs for distributed platforms with limited memory

Abstract : Scientific applications are commonly modeled as the processing of directed acyclic graphs of tasks, and for some of them, the graph takes the special form of a rooted tree. This tree expresses both the computational dependencies between tasks and their storage requirements. The problem of scheduling/traversing such a tree on a single processor to minimize its memory footprint has already been widely studied. Hence, we move to parallel processing and study how to partition the tree for a homogeneous multiprocessor platform, where each processor is equipped with its own memory. We formally state the problem of partitioning the tree into subtrees such that each subtree can be processed on a single processor and the total resulting processing time is minimized. We prove that the problem is NP-complete, and we design polynomial-time heuristics to address it. An extensive set of simulations demonstrates the usefulness of these heuristics.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Friday, April 5, 2019 - 2:50:57 PM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM


Files produced by the author(s)


  • HAL Id : hal-01644352, version 4



Anne Benoit, Changjiang Gou, Loris Marchal. Partitioning tree-shaped task graphs for distributed platforms with limited memory. [Research Report] RR-9115, Inria Grenoble Rhône-Alpes. 2019, pp.1-34. ⟨hal-01644352v4⟩



Record views


Files downloads