Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

9.6 SUMMARY

In message-passing multiprocessor systems, properly assigning tasks among processors and determining their execution order are important factors for utilizing resources efficiently. In this chapter we have introduced two scheduling approaches using genetic algorithms for homogeneous and heterogeneous systems, respectively.

The first approach, called the PGS algorithm, is designed based on the recombinative nature of a GA, which can potentially determine an optimal scheduling list leading to an optimal schedule. Using well-defined crossover and mutation operators, the PGS algorithm judiciously combines good building blocks of scheduling lists to construct better lists. Parallelization of the algorithm is based on a novel approach in that the parallel processors communicate to exchange the best chromosomes with exponentially decreasing periods. As such, the parallel processors perform exploration of the solution space at the early stages and exploitation at the later stages. In our experimental studies, we have found that the PGS algorithm generates optimal solutions for more than half of all the cases in which random-task graphs were used. In addition, the PGS algorithm demonstrates an almost linear speedup and is therefore scalable. Finally, it is worth mentioning that using parallel approaches for scheduling is a new research direction and that a few such schemes have recently been suggested [5, 19].

The second approach, called PSGA (problem space genetic algorithm), ...