Task Tree Scheduling for Completion Time Saving on Multi-Node Computing Environments

Task trees are widely used as paradigms on multi-node computing environments for various computational domains, such as the sparse linear algebra and the Cholesky factorizations. These domains provides support for the computation in the Internet of Things. Meanwhile, efficient task tree scheduling approaches are the key to reducing the completion time in the environments. An algorithm for splitting a task tree into a certain number of subtrees for distributed computing on multi-node computing environments with given memory capacity is proposed. The proposed algorithm initially splits a task tree into subtree graphs, then constructs the corresponding reduction tree. The further splitting works on each subtree, which is the critical path element of the reduction tree, since the critical path is dominated by the computation and communication time. If a subtree requires more memory to process, the subtree is further split by removing the maximum node. Finally, the subtrees are merged based on the preference on the minimum increase of completion time. Extensive experimental evaluations show that the completion time can be reduced by up to 36.52% on real-world dataset, and by up to 22.92% on randomly generated instances when the proposed algorithm is applied.