@inproceedings{papp24a, author = {Papp, P\'{a}l Andr\'{a}s and Anegg, Georg and Karanasiou, Aikaterini and Yzelman, A. N.}, title = {Efficient Multi-Processor Scheduling in Increasingly Realistic Models}, year = {2024}, isbn = {9798400704161}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3626183.3659972}, doi = {10.1145/3626183.3659972}, abstract = {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\texttimes{} improvement compared to the baselines. Finally, we also develop a multilevel scheduling algorithm, which provides up to almost a factor 5\texttimes{} improvement in the special case when the problem is dominated by very high communication costs.}, booktitle = {Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures}, pages = {463–474}, numpages = {12}, keywords = {bsp model, dag scheduling, integer linear programming, multilevel scheduling}, location = {, Nantes, France, }, series = {SPAA '24} }