TL;DR
This paper tackles the challenge of efficiently scheduling parallel tasks in sparse linear algebra, specifically focusing on multifrontal factorization. They introduce a novel, simplified proof for an optimal scheduling strategy for "malleable" tasks (tasks that can dynamically adjust their processor allocation) on shared-memory systems, and extend this to distributed systems, offering approximation algorithms and demonstrating significant performance gains over existing methods.
What Problem Does This Paper Address?
Scientific computing often involves complex workloads that can be represented as directed acyclic task graphs. A key challenge is efficiently mapping these tasks onto parallel computing architectures to minimize the overall execution time (makespan). This paper specifically addresses the scheduling of task trees arising from multifrontal factorization of sparse matrices. The core difficulty lies in the "malleable" nature of these tasks, meaning they can utilize a varying number of processors over time. Existing models often simplify this by assuming tasks are either sequential or have fixed processor requirements, or they rely on complex optimal control theory for malleable tasks. This paper aims to provide a more accessible and practical approach to scheduling these malleable tasks, particularly by simplifying existing proofs and extending the problem to distributed environments.
Methods
The authors build upon the $p^\alpha$ speedup model for malleable tasks, where $p$ is the processor share and $\alpha$ is a parameter reflecting the efficiency of parallelization.
- Simplified Proofs for Shared-Memory Systems: They present a new, purely scheduling-based proof for the optimal allocation strategy proposed by Prasanna and Musicus. This approach avoids complex optimal control theory, offering more intuitive insights into why the optimal schedule is unique and how it can be computed.
- Extension to Distributed Memory: The paper extends the problem to distributed memory platforms where a task cannot be split across multiple nodes. This introduces significant complexity.
- NP-Completeness and Approximation Algorithms: For distributed settings, they prove the NP-completeness of the scheduling problem and propose approximation algorithms. This includes a $(3^\alpha)$-approximation for homogeneous nodes and an FPTAS for independent tasks on heterogeneous nodes.
- Experimental Validation: The relevance of the $p^\alpha$ model is validated through experiments on real multicore platforms using dense linear algebra kernels.
Datasets
The paper uses experimental data from dense linear algebra kernels (Cholesky and QR factorization) on a specific multicore platform (4 Intel E7-4870 processors with 10 cores each). For simulations, they utilize a dataset of assembly trees from the University of Florida Sparse Matrix Collection, comprising over 600 trees with varying sizes and depths.
Key Insights and Ideas
- The $p^\alpha$ Model is Realistic: The paper provides experimental evidence that the $p^\alpha$ speedup model, with $\alpha$ typically between 0.85 and 0.95, accurately reflects the performance of dense kernels used in sparse matrix factorization on modern multicore architectures. This validates the core assumption of their work.
- Scheduling-Based Proofs are Powerful: By simplifying the proofs for optimal scheduling using only scheduling arguments, the authors make the problem more accessible and provide clearer intuition about the underlying mechanisms.
- Distributed Scheduling is Hard: The introduction of the constraint that tasks cannot be distributed across nodes in a distributed system significantly increases the problem's complexity, leading to NP-completeness.
- Approximation is Necessary and Effective: For distributed systems, the paper demonstrates that approximation algorithms can provide good solutions, achieving significant performance gains over naive strategies.
Key Results
- Optimal Schedule for Shared Memory: The paper provides a simplified proof for an optimal scheduling strategy for malleable tasks on shared-memory systems, showing that it can be computed efficiently.
- NP-Completeness for Distributed Systems: The scheduling problem for trees of malleable tasks on distributed memory systems is proven to be NP-complete.
- Approximation Algorithms: A $(3^\alpha)$-approximation algorithm is presented for homogeneous distributed nodes, and an FPTAS is developed for independent tasks on heterogeneous nodes.
- Performance Gains: Simulations show that the proposed optimal allocation strategy can achieve performance gains of up to 16% compared to existing solutions that are unaware of the $p^\alpha$ speedup function, particularly for $\alpha = 0.9$.
Limitations and Future Work
- Assumed $p^\alpha$ Model: The paper relies on the assumption that the $p^\alpha$ speedup model holds and that $\alpha$ is constant for a given task or application. While validated experimentally, real-world scenarios might exhibit more complex speedup behaviors.
- Computational Cost of $p^\alpha$ and $p^{1/\alpha}$: The proofs assume that computing $x^\alpha$ and $x^{1/\alpha}$ can be done in polynomial time. While this is often true in practice with reasonable precision, it's a theoretical simplification.
- Distributed System Complexity: The extension to distributed systems introduces NP-completeness, necessitating approximation algorithms. The proposed algorithms are for specific scenarios (two nodes, homogeneous/heterogeneous).
- Future Work: The authors suggest extending the work to more than two nodes and to more heterogeneous nodes, which is crucial for modern architectures with accelerators like GPUs. They also highlight the importance of implementing the proposed PM allocation scheme in actual sparse solvers to realize these performance gains in practice.
Summary updated