Skip to Main content Skip to Navigation
Reports

Minimizing I/Os in Out-of-Core Task Tree Scheduling

Abstract : Scientific applications are usually described as directed acyclic graphs, where nodes represent tasks and edges represent dependencies between tasks. For some applications, such as the multifrontal method of sparse matrix factorization, this graph is a tree: each task produces a single output data, used by a single task (its parent in the tree). We focus on the case when the data manipulated by tasks have a large size, which is especially the case in the multifrontal method. To process a task, both its inputs and its output must fit in the main memory. Moreover, output results of tasks have to be stored between their production and their use by the parent task. It may therefore happen, during an execution, that not all data fit together in memory. In particular, this is the case if the total available memory is smaller than the minimum memory required to process the whole tree. In such a case, some data have to be temporarily written to disk and read afterwards. These Input/Output (I/O) operations are very expensive; hence, the need to minimize them. We revisit this open problem in this paper. Specifically, our goal is to minimize the total volume of I/O while processing a given task tree. We first formalize and generalize known results, then prove that existing solutions can be arbitrarily worse than optimal. Finally, we propose a novel heuristic algorithm, based on the optimal tree traversal for memory minimization. We demonstrate good performance of this new heuristic through simulations on both synthetic trees and realistic trees built from actual sparse matrices.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01462213
Contributor : Frédéric Vivien <>
Submitted on : Wednesday, February 8, 2017 - 5:26:45 PM
Last modification on : Tuesday, November 19, 2019 - 2:39:11 AM
Long-term archiving on: : Tuesday, May 9, 2017 - 1:51:43 PM

File

INRIA-9025.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01462213, version 1

Collections

Citation

Loris Marchal, Samuel Mccauley, Bertrand Simon, Frédéric Vivien. Minimizing I/Os in Out-of-Core Task Tree Scheduling. [Research Report] RR-9025, INRIA. 2017. ⟨hal-01462213⟩

Share

Metrics

Record views

515

Files downloads

258