DAG Scheduling for Synchronous Communication in the Network Computing Environment

Although the advance in high-speed networks is rapid, parallel computing on the network computing environments is not so reliable as that performed on parallel machines. Therefore, many applications must rely on synchronous communication in the form of application-level handshaking. In general, application-level handshaking may enhance the reliability of executing parallel programs on the network computing environments, but also simplify the error handling for communication, maintaining easy programability. However, synchronization introduces a waiting time for the sender and an overhead to the already high cost of message-passing. Furthermore, synchronization may result in deadlock among communicating tasks. Most heuristics for scheduling address asynchronous communication DAG is proposed, but they are not suitable for the synchronous ones. Proposed in this paper is a novel algorithm for the synchronous scheduling problem, which is called parameters relation graph-based synchronous clustering (PRGSC). The PRGSC algorithm introduces a parameter relation graph (PRG), which represents relations of timing parameters of tasks and dynamically varies in the scheduling process, for the deadlock detection. In every scheduling step, PRGSC algorithm avoids the deadlock caused by the synchronous communication through examination of the PRG. Meanwhile, it could alleviate the impact of synchronous communicating delay on the makespan by simultaneously considering the ready tasks and scheduled tasks. Simulation shows that the PRGSC algorithm has better performance than the CASC algorithm which deals with the same type of problems.