Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10340560 | Computers & Electrical Engineering | 2005 | 19 Pages |
Abstract
This paper presents the evaluation of the solution quality of heuristic algorithms developed for scheduling multiprocessor tasks for a class of multiprocessor architectures designed to exploit temporal and spatial parallelism simultaneously. More specifically, we deal with multi-level or partitionable architectures where MIMD parallelism and multiprogramming support are the two main characteristics of the system. We investigate scheduling a number of pipelined multiprocessor tasks with arbitrary processing times and arbitrary processor requirements in this system. The scheduling problem consists of two interrelated sub-problems, which are finding a sequence of pipelined multiprocessor tasks on a processor and finding a proper mapping of tasks to the processors that are already being sequenced. For the solution of the second problem, various techniques are available. However, the problem remains of generating a feasible sequence for the pipelined operations. We employed three well-known local search heuristic algorithms that are known to be robust methods applicable to various optimization problems. These are Simulated Annealing, Tabu Search, and Genetic Algorithms. We then conduct computational experiments and evaluate the reduction achieved in completion time by each heuristic. We have also compared the results with well-known simple list-based heuristics.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
M. Fikret Ercan, Ceyda OÄuz,