Efficient Multi-Processor Scheduling in Increasingly Realistic Models
<|reference_start|>Efficient Multi-Processor Scheduling in Increasingly Realistic Models: We study the problem of efficiently scheduling a computational DAG on multiple processors. The majority of previous works have developed and compared algorithms for this problem in relatively simple models; in contrast to this, we analyze this problem in a more realistic model that captures many real-world aspects, such as communication costs, synchronization costs, and the hierarchical structure of modern processing architectures. For this we extend the well-established BSP model of parallel computing with non-uniform memory access (NUMA) effects. We then develop a range of new scheduling algorithms to minimize the scheduling cost in this more complex setting: several initialization heuristics, a hill-climbing local search method, and several approaches that formulate (and solve) the scheduling problem as an Integer Linear Program (ILP). We combine these algorithms into a single framework, and conduct experiments on a diverse set of real-world computational DAGs to show that the resulting scheduler significantly outperforms both academic and practical baselines. In particular, even without NUMA effects, our scheduler finds solutions of 24%-44% smaller cost on average than the baselines, and in case of NUMA effects, it achieves up to a factor $2.5\times$ improvement compared to the baselines. Finally, we also develop a multilevel scheduling algorithm, which provides up to almost a factor $5\times$ improvement in the special case when the problem is dominated by very high communication costs.<|reference_end|>
@article{papp2024efficient,
    title={Efficient Multi-Processor Scheduling in Increasingly Realistic Models},
    author={P'al Andr'as Papp, Georg Anegg, Aikaterini Karanasiou, A. N. Yzelman},
    journal={arXiv preprint arXiv:2404.15246},
    year={2024},
    doi={10.1145/3626183.3659972},
    archivePrefix={arXiv},
    eprint={2404.15246},
    primaryClass={cs.DC}
}