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

7.1 INTRODUCTION

Constructing efficient algorithms for scheduling tasks of a parallel program in a multiprocessor architecture remains an unsolved issue in parallel computing. The problem of multiprocessor scheduling, even limited to a two-processor systems but any parallel program, is known to be NP complete [4, 11]. Despite many studies, progress in this area due to an NP completeness of a scheduling problem is slow and insufficient to automatize corresponding functions of operating systems designed for multiprocessor systems.

Current works [1, 4, 11, 16] concerning the scheduling problem are focused either on selecting problems for which exact solutions can be constructed or designing heuristic algorithms to find near-optimal solutions for more general cases. In particular, scheduling algorithms based on applying techniques derived from nature, such as simulated annealing, genetic algorithms, or neural networks [6, 13, 15], belong to the latter area of research. While most of the proposed scheduling algorithms are sequential algorithms, a new direction in this area is developing parallel and distributed scheduling algorithms [2, 20].

In this chapter I develop parallel and distributed scheduling algorithms using a recent and very promising technique based on combining evolutionary computation and cellular automata (CAs). CAs present a distributed system of single, locally interacting units that are able to produce global behavior. CAs can be considered a model of naturally existing ...