Task stalling for a batch of task makespan minimisation in heterogeneous multigrid computing
Volume 8 (2021), pp. 631–638
Pub. online: 14 September 2021
Type: Article
Open Access
Received
1 June 2021
1 June 2021
Accepted
18 June 2021
18 June 2021
Published
14 September 2021
14 September 2021
Abstract
This paper presents a new algorithm for a batch of task makespan minimisation in heterogeneous multigrid computing. Heterogeneous grids are known to cause straggling task problem that increases task execution makespan. Existing task distribution algorithms solve this problem by using information about the compute node capacities or task sizes. However, such information may not always be available. Task stalling solves both problems. However, this method is described for queuing systems consisting of only two heterogeneous servers or grids. Our proposed algorithm is based on an improved task stalling method, allowing it to distribute tasks in systems consisting of two or more grids. Experiment results show reduced task execution makespan by up to 19,92% compared to FIFO. This allows us to conclude that the new algorithm is suitable for a batch of task makespan minimisation in heterogeneous multigrid computing.