Performance evaluation of a list scheduling algorithm in distributed memory multiprocessor systems

Since it has been shown that the multiprocessor scheduling problem is NP-complete, research efforts have resulted in numerous scheduling algorithms based on heuristics. The need for measuring the effectiveness of the various task scheduling algorithms leads to a great demand on modeling and evaluation tools. This paper proposes to use the stochastic Petri net (SPN) model and its equivalent continuous time Markov chain (CTMC) as the tool for modeling and evaluation of task scheduling algorithms. The proposed approach is applied to DPS (decisive path scheduling) algorithm to investigate its effectiveness. The proposed approach is verified by comparing the result obtained using the SPN model with that obtained by actually running DIPS algorithm. The performance comparison reveals that the proposed approach provides very accurate performance evaluation for the scheduling algorithm when the CCR (communication to computation ratio) value is small. (C) 2003 Elsevier B.V. All rights reserved.