Multiprocessor scheduling in a genetic paradigm

Parallel ComputingPublished 1 March 1996

Imtiaz Ahmad, M.K. Dhodhi

DOI10.1016/0167-8191(95)00068-2

Source URL

Citations64

SJR quartileQ2

SJR score0.54

SNIP1.30

TL;DR

A technique based on the problem-space genetic algorithm (PSGA) for the static scheduling of directed acyclic graphs onto homogeneous multiprocessor systems to reduce the response-time is presented.

Abstract

In this paper, we present a technique based on the problem-space genetic algorithm (PSGA) for the static scheduling of directed acyclic graphs onto homogeneous multiprocessor systems to reduce the response-time. The PSGA based approach combines genetic algorithms with a list scheduling heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable cpu time. Comparison of results with the genetic algorithm (GA) based scheduling technique for the Stanford manipulator and the Elbow manipulator examples shows a significant improvement in the response-time. We also demonstrate the effectiveness of our algorithm by comparing it with the Critical Path/Maximum Immediate Successor First (CP/MISF) list scheduling technique for randomly generated graphs. The proposed scheme offers on the average a 3.6% improvement in the response-time as compared to the CP/MISF technique for all the random graphs.

Keywords

Computer ScienceEngineering

Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning

49,278 Citations1989

This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.

SIAM Journal on Applied MathematicsBounds on Multiprocessing Timing Anomalies

2,342 Citations1969Ron Graham

IEEE Transactions on Parallel and Distributed SystemsA genetic algorithm for multiprocessor scheduling

685 Citations1994E.S.H. Hou, Nirwan Ansari +1 more

An efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem and results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented.

IEEE Transactions on Software EngineeringMultiprocessor Scheduling with the Aid of Network Flow Algorithms

682 Citations1977Harold S. Stone

This paper shows that this program module assignment problem can be solved efficiently by making use of the well-known Ford–Fulkerson algorithm for finding maximum flows in commodity networks as modified by Edmonds and Karp, Dinic, and Karzanov.

Communications of the ACMA comparison of list schedules for parallel processing systems

613 Citations1974Thomas L. Adam, K. Mani Chandy +1 more

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks and a dynamic programming solution for the case in which execution times are random variables is presented.

View PDF

Acta InformaticaOptimal scheduling for two-processor systems

610 Citations1972E. G. Coffman, Ronald Graham

It is proved that the algorithm gives optimal solutions and its application to preemptive scheduling disciplines is discussed.

IEEE Transactions on ComputersPractical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing

453 Citations1984Hironori Kasahara, Narita

A heuristic algorithm CP/MISF (Critical Path/Most Immediate Successors First) and an optimization/approximation algorithm DF/IHS (Depth First/ Implicit Heuristic Search) are proposed which can reduce markedly the space complexity and average computation time.

IEEE Journal on Robotics and AutomationParallel processing of robot-arm control computation on a multimicroprocessor system

193 Citations1985Hironori Kasahara, S. Narita

The proposed algorithms are applied to the computation of the Newton-Euler equations of motion for the Stanford manipulator and implemented on a multimicroprocessor system and it is shown that the proposed parallel-processing scheme is applicable to an arbitrary number of processors.

ACM Computing SurveysModels of machines and computation for mapping in multicomputers

167 Citations1993Michael G. Norman, Peter Thanisch

View PDF

Parallel ComputingList scheduling with and without communication delays

154 Citations1993Tao Yang, Apostolos Gerasoulis

Two new list scheduling heuristics are proposed, the RCP and RCP∗ that use critical path information and ready list priority scheduling and are shown to be similar to CP when communication is zero.