Volume 5 Number 10 (Oct. 2010)
Home > Archive > 2010 > Volume 5 Number 10 (Oct. 2010) >
JSW 2010 Vol.5(10): 1128-1136 ISSN: 1796-217X
doi: 10.4304/jsw.5.10.1128-1136

Multiprocessor Scheduling by Simulated Evolution

Imtiaz Ahmad1, Muhammad K. Dhodhi2, Ishfaq Ahmad3

1Department of Computer Engineering Kuwait University, P. O. Box: 5969, Safat 13060 Kuwait
2Ross Video Ltd., 9 Slack Road, Ottawa, ON, K2G 0B7 Canada
3Department of Computer Science and Engineering Box 19015, CSE, University of Texas at Arlington, Arlington, TX 76019 USA

Abstract—This paper presents a variant of simulated evolution technique for the static non-preemptive scheduling of parallel programs represented by directed acyclic graphs including inter-processor communication delays and contention onto a multiprocessor system with the dual objectives of reducing the total execution time and scaling with the number of processors. The premise of our algorithm is Simulated Evolution, an effective optimization method based on the analogy with the natural selection process of biological evolution. The proposed technique, named Scheduling with Simulated Evolution (SES), combines simulated evolution with list scheduling, wherein simulated evolution efficiently determines suitable priorities which lead to a good solution by applying list scheduling as a decoding heuristic. SES is an effective method that yields reduced length schedules while scaling well and incurring reasonably low complexity. The SES technique does not require problem-specific parameter tuning on test problems of different sizes and structures. Moreover, it strikes a balance between exploration of the search space and exploitation of good solutions found in an acceptable CPU time. We demonstrate the effectiveness of SES by comparing it against two existing static scheduling techniques for the test examples reported in literature and on a suite of randomly generated graphs. The proposed technique produced good quality solutions with a slight increase in the CPU time as compared with the competing techniques.

Index Terms—Software, Scheduling, Allocating Parallel Programs, Simulated Evolution.


Cite: Imtiaz Ahmad, Muhammad K. Dhodhi, Ishfaq Ahmad, "Multiprocessor Scheduling by Simulated Evolution," Journal of Software vol. 5, no. 10, pp. 1128-1136, 2010.

General Information

ISSN: 1796-217X (Online)
Frequency:  Quarterly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, CNKIGoogle Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsweditorialoffice@gmail.com
  • Mar 01, 2024 News!

    Vol 19, No 1 has been published with online version    [Click]

  • Apr 26, 2021 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Nov 18, 2021 News!

    Papers published in JSW Vol 16, No 1- Vol 16, No 6 have been indexed by DBLP   [Click]

  • Jan 04, 2024 News!

    JSW will adopt Article-by-Article Work Flow

  • Nov 02, 2023 News!

    Vol 18, No 4 has been published with online version   [Click]