Task Tree Partition and Subtree Allocation for Heterogeneous Multiprocessors
Suna He, Jigang Wu, Bing Wei, Jiaxin Wu · 2021
Tree-shaped task graphs become a paradigm to be utilized in distributed platform for various computational domains, such as the electronic structure calculations and the factorization of sparse matrices. However, the scheduling of the tree-shaped task graph has been rarely studied for the more realistic heterogeneous multiprocessor platform (HEMP). This paper proposes an efficient algorithm named Partition-Allocation (PA) for parallel computing on HEMP with limited memory. Algorithm PA consists of two stages: partitioning and allocation. In the partitioning stage, a task tree is split into several subtrees. In the allocation stage, these subtrees are assigned to different processors for execution. Our algorithm PA can reduce makespan by prioritizing subtrees on the critical path, both in the partitioning and in the allocation. Based on randomly generated trees and real-world dataset, experimental results show that the proposed PA is significantly better than the latest work in terms of average makespan. The proposed algorithm can successfully reduce the average makespan by up to 67.01% on real-world dataset, and 52.35% on randomly generated trees.