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

2.3 PARALLEL GLOBAL SELECTION

So far we have described three different models for evolutionary algorithms: single-population model, island model, and diffusion model. Each of those models maps naturally to a specific hardware architecture, namely, single workstation, workstation cluster, and massively parallel single instruction stream, multiple data stream (SIMD) computer, respectively (cf. Fig. 2.5).

But often it is desirable to run a specific model on some other than the corresponding hardware, either for performance reasons or because no other hardware platform is available. Of course, one can easily simulate parallel execution and run any EA-model on a single processor. The opposite way, however, e.g., running the single-population model on a massively parallel processor array, requires that global operations like selection be parallelized, and is not at all trivial.

In this section we look at the problem of parallelizing the global operations in evolutionary algorithms. In particular, we consider the selection of parents for reproduction, and we assume that the population is distributed over a fine-grained massively parallel machine (a 2-dimensional mesh-connected array) such that every processor hosts one individual only. That means we have the maximally reasonable number of processors available and want to check whether we can use them efficiently to perform the global operations that were grouped earlier into the farmer process (cf. Section 2.2.1). This section is based ...