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:
- 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.
- 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.
- The
FullRecExpandHeuristic: 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
FullRecExpandheuristic and its faster variant,RecExpand, consistently outperformed standard methods. On theSynthdataset,RecExpandachieved lower I/O volumes thanOptMinMemin 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