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

Loris Marchal, Samuel McCauley, Bertrand Simon, Frédéric Vivien

Abstract

Scientific applications are often modeled as directed acyclic graphs, specifically trees, where nodes represent tasks and edges represent dependencies. In out-of-core execution, where data exceeds available memory, temporary results must be written to and read from disk. This paper addresses the challenge of minimizing the total volume of these expensive Input/Output (I/O) operations. We formalize the problem, prove that existing peak-memory minimization strategies can be suboptimal for I/O, and introduce a novel heuristic, FullRecExpand, which demonstrates near-optimal performance across synthetic and realistic scientific datasets.

Introduction

In high-performance computing domains such as sparse matrix factorization and computational physics, applications are frequently structured as task trees. Each node in these trees represents a computation that consumes data from its children to produce a result for its parent. As datasets scale, they often encounter the "memory wall," where the total data required for processing exceeds available RAM. This necessitates out-of-core execution, involving the temporary storage of data on disk.

Because disk access is significantly slower than RAM, minimizing the total volume of data moved (I/O volume) is critical for performance. While minimizing peak memory is a well-studied area, minimizing total I/O volume for heterogeneous data—where tasks produce results of varying sizes—remains a complex, open challenge. This research investigates the MinIO problem: finding a task execution order that minimizes total I/O.

Methodology

The study approaches the MinIO problem through a multi-layered methodology:

  1. Theoretical Formalization: The authors prove that while a simple post-order traversal is optimal for "homogeneous" trees (uniform data sizes), it can be arbitrarily worse than optimal for general trees. They demonstrate that algorithms designed to minimize peak memory do not necessarily minimize total I/O volume.
  2. Integer Linear Programming (ILP): An ILP formulation was developed to provide exact optimal solutions for small-scale trees, serving as a benchmark for heuristic performance.
  3. The FullRecExpand Heuristic: The core contribution is a heuristic that leverages an existing optimal peak-memory scheduler (OptMinMem). When memory limits are reached, the algorithm "expands" the bottleneck node into a chain of three tasks representing production, disk storage, and reloading. By iteratively re-running the scheduler on this modified tree, the algorithm converges on an I/O-optimized schedule.

Experimental Evaluation

The proposed algorithms were evaluated using three distinct datasets:

  • SmallSynth: 30,000 synthetic binary trees (30 nodes) for comparison against ILP optima.
  • Synth: 330 larger synthetic binary trees (3,000 nodes) to test scalability.
  • Trees: 133 realistic "elimination trees" from the University of Florida Sparse Matrix Collection (2,000 to 40,000 nodes).

Key Results

  • Performance: The FullRecExpand heuristic and its faster variant, RecExpand, consistently outperformed standard methods. On the Synth dataset, RecExpand achieved lower I/O volumes than OptMinMem in 90% of cases.
  • Accuracy: Against the ILP baseline, the heuristics were non-optimal in less than 1% of cases, with deviations of less than 1% when they did occur.
  • Real-World Application: On realistic matrix trees, the heuristics matched or exceeded the best known strategies, providing significant savings in the 10% of cases where standard traversals struggled.

Discussion and Future Work

The research highlights that peak memory minimization is not a perfect proxy for I/O minimization. The "expansion trick" introduced provides a clever way to adapt existing memory-aware schedulers for the harder MinIO problem.

Future work will address the computational complexity of the FullRecExpand heuristic for extremely large trees and seek a formal proof for the conjectured NP-hardness of the MinIO problem. Additionally, extending these sequential scheduling techniques to parallel out-of-core execution on modern supercomputers remains a primary objective.

Summary updated

Abstract

Scientific applications are usually described using directed acyclic graphs, where nodes represent tasks and edges represent dependencies between tasks. For some applications, this graph is a tree: each task produces a single result used solely by its parent. The temporary results of each task have to be stored between their production and their use. We focus on the case when the data manipulated are very large. Then, during an execution, all data may not fit together in memory. In such a case, some data have to be temporarily written to disk and evicted from memory. These data are later read from disk when they are needed for computation. These Input/Output operations are very expensive; hence, our goal is to minimize their total volume. The order in which the tasks are processed considerably influences the amount of such Input/Output operations. Finding the schedule which minimizes this amount is an open problem that we revisit in this paper. We first formalize and generalize known results, and prove that existing solutions can be arbitrarily worse than the optimal. We then present an Integer Linear Program to solve it optimally. Finally, we propose a novel heuristic algorithm. We demonstrate its good performance through simulations on both synthetic and realistic trees built from actual scientific applications.
BibTeX
@article{marchal2022minimizing,
  author = {Loris Marchal and Samuel McCauley and Bertrand Simon and Frédéric Vivien},
  title = {{Minimizing I/Os in Out-of-Core Task Tree Scheduling}},
  journal = {International Journal of Foundations of Computer Science},
  year = {2022},
  doi = {10.1142/s0129054122500186},
}
Figure