ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems

Abstract

Efficient scheduling is critical for achieving improved performance of distributed applications where an application is to be considered as a group of interrelated tasks and represented by a task graph. In this work, we present a clustering-based scheduling algorithm called effective critical path (ECP) to schedule precedence constrained tasks on multiprocessor computing systems. The main aim of the algorithm is to minimize the schedule length of the given application. It uses the concept of edge zeroing on the critical path of the task graph for clustering the tasks of an application. An experimental analysis is performed using random task graphs and the task graphs derived from the real-world applications such as Gaussian Elimination, fast Fourier transform and systolic array. The results illustrate that the ECP algorithm gives better performance than the previous algorithms, considered herein, in terms of the average normalized schedule length and average speedup. © 2018, Springer-Verlag GmbH Austria, part of Springer Nature.