Comments on “IPPTS: An Efficient Algorithm for Scientific Workflow Scheduling in Heterogeneous Computing Systems”
Rajesh Devaraj, Arnab Sarkar · IEEE Transactions on Parallel and Distributed Systems · 2022
IPPTS(Improved Predict Priority Task Scheduling) is a list scheduling algorithm that schedules task graphs on fully connected heterogeneous distributed systems, with an objective of minimizing the overall makespan (i.e., schedule length). With respect to the literature on list scheduling techniques for task graphs,IPPTSimproves the task prioritization by considering the“out-degree”of a task. However, we have observed that the IPPTS algorithm contains an ambiguity which introducesthe possibility of assigning higher priority to a task compared to its predecessors in a task graph. This priority inversionmay lead to the generation of an incorrect scheduledue to the violation of precedence-constraints among tasks. In this note, we first highlight this issue using a counter example. Then, we discuss two possible ways to fix the ambiguity in the algorithm.