Premium
An edge priority‐based clustering algorithm for multiprocessor environments
Author(s) -
Maurya Ashish Kumar,
Tripathi Anil Kumar
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5060
Subject(s) - computer science , multiprocessing , cluster analysis , scheduling (production processes) , multiprocessor scheduling , algorithm , job shop scheduling , dynamic priority scheduling , speedup , computation , parallel computing , rate monotonic scheduling , schedule , mathematical optimization , mathematics , artificial intelligence , operating system
Summary In multiprocessor environments, the scheduling algorithms play a significant role in maximizing system performance. In this paper, we propose a clustering‐based task scheduling algorithm called Edge Priority Scheduling (EPS) for multiprocessor environments. The proposed algorithm extends the idea of edge zeroing heuristic and uses the concept of edge priority to minimize the makespan of the task graph. The complexity of the EPS algorithm is O (| V || E |(| V | + | E |)), where | E | represents the number of edges and | V | denotes the number of nodes in the task graph. The experiments are performed for random task graphs and the task graphs generated from some representative real‐world applications such as Gaussian Elimination and Fast Fourier Transform. The performance of the EPS algorithm is compared with six well‐known algorithms such as EZ (Edge Zeroing), LC (Linear Clustering), CPPS (Cluster Pair Priority Scheduling), DCCL (Dynamic Computation Communication Load), RDCC (Randomized Dynamic Computation Communication), and LOCAL. The results show that the EPS algorithm outperforms the compared algorithms in terms of the normalized schedule length and speedup.