task scheduling and resource allocation on parallel and distributed machines

Abstract

Task scheduling is a significant problem for parallel and distributed systems. As a mature and important topic, scheduling has attracted much attention among scholars. How to examine this topic in depth has become interesting and challenging. In this thesis, the author discusses it from three different aspects. Firstly, as a core question in high-performance computing, the scheduling algorithms are the main concern. The author proposes a novel algorithm called `the look-forward algorithm'. Different from other algorithms, the look-forward algorithm provides a novel way of task allocation, which fully considers the DAG structure and incoming and outgoing communications. Experimental results show that the look-forward algorithm can get up to 40\% improvement compared to the benchmark HEFT algorithm \cite{Topcuoglu2002}, especially when the number of tasks increases. Secondly, the author considers scheduling using a communication contention model \cite{Sinnen2005,Sinnen2004,Choudhury2012}. Research has shown the contention model has more stability and accuracy than the classic model in describing communication but it is also more complicated than the classic model because of the communication contention. The author extends the look-forward algorithm for contention model scheduling so that the algorithm can appropriately consider communication. Thirdly, after this algorithm and scheduling model, the author focuses on communication data. A new problem, the identical data problem, is proposed. Identical data means that exactly the same data is sent from one task to other tasks, which can be used to reduce the communication among processors. Taking this into account, a new algorithm based on the look-forward algorithm is proposed. All three algorithms in this thesis are evaluated using simulation.

Date of Award	1 Aug 2022
Original language	English
Awarding Institution	The University of Manchester
Supervisor	John Gurd (Supervisor) & Rizos Sakellariou (Supervisor)