Parallel computation

The reason for parallellazing lil-gp is obvious and has already been mentioned earlier. But maybe it is useful to introduce some term that are relevant in the field of parallel computing in general. (I keep it brief I promise :)

• speedup and efficiency: Speedup refers the ratio of the computation time on a single CPU and on several CPU's. The effeciency is the ratio of the speedup and the number of CPU's used to achieve this speedup. What do these measures tell you. The speedup will be bigger than 1 whenever the parallel implementation is faster the the sequential one. (Note that the speedup is not necessarily >1) The efficiency allows you the determine how well the used computational resources are used. This can easily be understood with an extreme example. Everyone would agree the a speedup of 3 using 100 CPU's would be a serious waste of computation resources. Especially if you achieve a speedup of 2 using 20 CPU's for example.
• Embarrasingly parallel: Some problems may very well be hard to parallellize and thus exhibit some very low speedups no matter the number of CPU being used. (This has been formally described by Amdalh) At the other side of the spectrum of parallellisation one finds the the embarrasingly parallel problems. These problem are by nature parallel so that a parallel implemention can be done very efficiently. Examples of that are : 1) cracking of keys, the group of all possible keys can be divided and distributed over all the available CPU's. All the CPU's can then work independently from each other. 2) Evoluationary computations are also good canditates (well what do you know :). The idea of subpopulations (or island model) implies the parallel evolution of different populations with relatively infrequent exchanges between the populations.
• PVM: Which stands for Parallel Virtual Machine is a software package that provides both a API (C/C++ and Fortran) for developing  parallel programs and the environment to execute these programs. PVM has been ported to several platforms (OS and hardware) including massively parallel computers.  PVM is freely available and can be found very easily on each and every search engine on the web.