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:  Bimonthly (Since 2020)
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, Google Scholar, ProQuest, INSPEC(IET), ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Apr 26, 2021 News!

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

  • Jun 22, 2020 News!

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

  • Sep 13, 2021 News!

    The papers published in Vol 16, No 6 have all received dois from Crossref    [Click]

  • Jan 28, 2021 News!

    [CFP] 2021 the annual meeting of JSW Editorial Board, ICCSM 2021, will be held in Rome, Italy, July 21-23, 2021   [Click]

  • Sep 13, 2021 News!

    Vol 16, No 6 has been published with online version     [Click]