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.

[PDF]

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: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Aug 21, 2019 News!

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

  • Jun 25, 2019 News!

    Vol.13, No.9 has been indexed by EI (Inspec).   [Click]

  • Aug 01, 2018 News!

    [CFP] 2020 the annual meeting of JSW Editorial Board, ICCSM 2020, will be held in Rome, Italy, July 17-19, 2020   [Click]

  • Jul 10, 2019 News!

    Vol 14, No.8 has been published with online version 4 original aritcles from 2 countries are published in this issue.    [Click]

  • Sep 12, 2019 News!

    Vol 14, No 10 has been published with online version 4 original aritcles from 2 countries are published in this issue      [Click]