scientific article; zbMATH DE number 1737496

MaRDI QIDQ4529609zbMATH OpenFDO

Authors Tomasz Kalinowski

Publication date 5 May 2002

zbMATH Keywords

genetic algorithmparallel programming environmentsscheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph theory (including graph drawing) in computer science (68R10)

Review text

Genetic Algorithms (GAs) are probabilistic search techniques modelling a natural process of evolution to reach an optimum solution (according to given criteria). List scheduling relies on initial task ordering with respect to a given priority and then, at each step, the task with the highest priority is assigned to a free processor. The author presents a task scheduling heuristic which is based on a parallel GA. The heuristic belongs to those scheduling strategies that simultaneously allocate tasks to computational nodes and communications to interprocessor link connections in such a way that the program execution time is minimized. A combination of two methods is used: a list scheduling (which constructs schedules) and a GA (which works on the search space for the list algorithm). The algorithm schedules parallel programs onto multi-processor systems with dynamic interconnection networks (BINs), this means that system connections are organized via DINs. It takes into account interprocessor communication cost, link contention (number, capacity) and changes of interprocessor connections. (Before, scheduling algorithms have been designed for fixed interprocessor connections.) Parallel programs are represented as weighted directed acyclic graphs (each node represents a task and each edge represents a communication; computational costs are weights assigned to nodes and communication costs are weights assigned to edges). They can be constructed in a graphical way and merged with text code. A multi-processor system is composed of \(n\) homogeneous processor and each processor is equipped with independent units for computation and communication, a private memory and \(k\) bi-directional communication links \((k < n)\). The presented experimental results consist of a comparison of schedules obtained with five heuristics: serial GA, parallel GA and three list scheduling heuristics. Parallel GA computes the shortest schedules.

Recommendations

• Scheduling of parallel programs on configurable multiprocessors by genetic algorithms
• Genetic algorithms for task scheduling problem
• A comparison of multiprocessor task scheduling algorithms with communication costs
• A modified hybrid genetic algorithm for parallel task scheduling of multiprocessors
• Multiprocessor scheduling in a genetic paradigm

Cited in

(11)

• Scheduling of parallel programs on configurable multiprocessors by genetic algorithms
• A genetic-algorithm approach to scheduling communications for embedded parallel space-time adaptive processing algorithms.
• Conventional and multirecombinative evolutionary algorithms for the parallel task scheduling problem
• Genetic algorithm based parallel jobs scheduling in distributed computing system
• The Research of Solution to the Problems of Complex Task Scheduling Based on Self-adaptive Genetic Algorithm
• A parallel genetic simulated annealing hybrid algorithm for task scheduling
• A modified hybrid genetic algorithm for parallel task scheduling of multiprocessors
• scientific article; zbMATH DE number 5284166 (Why is no real title available?)
• scientific article; zbMATH DE number 1323826 (Why is no real title available?)
• scientific article; zbMATH DE number 2079887 (Why is no real title available?)
• scientific article; zbMATH DE number 2078922 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4529609)