This paragraph describes the how parallel lil-gp distributes the different subpopulations among the CPU's available in the PVM. Since it is difficult to predict the evolution of the individuals of a population the mapping of subpopulation to CPU's may not guarantee an optimal load balancing.
Indeed, the individuals within a population can for example become bigger than in other subpopulations or that they tend to use more computational expensive functions. As a result the computation power needed for the differen subpopulation may differ over tiem and result in a suboptimal balance of the computational load.
In the first place parallel lil-gp will try to distribute the subpopulations in an even manner over the different CPU's. It should be note that the exact assignment of populations to CPU's occurs is determined by PVM in the current version of the software. And as such not be influenced by the user of parallel lil-gp. Parallel lil-gp determines the distribution of the subpopulations onto different CPU's but does not take into account which CPU to will be used.
To illustrate how the parallel kernel will distribute the subpopulations in a PVM, we will start with a simple situation. We have N subpopulation and N CPU's, this will result in 1; subpopulation per CPU as one might expect. Suppose now that we have M subpopulations and N CPU's and that the we have twice as much subpopulations than CPU's (M=2xN). Now parallel lil-gp will of course assign 2 subpopulations per CPU. But it will also make sure that neighbouring subpopulations reside in the same CPU. This will reduce the number of exchanges between the CPU's which are more costly than normal exchanges. In the previous example subpopulation 1 and 2 would end up on the same CPU and so would 3 and 4 etc...
In situations where the number of subpopulations is not a multiple of the number of CPU's parallel lil-gp will distribute the subpopulation in a non even manner. Parallel lil-gp will assign as many subpopulation as possible to the first CPU's. Although there will be an unequal load on the different CPU this this difference in the number of subpopulations per CPU is at most 1!
Some example distribution are represented in the table underneath.
|
#subpopulations |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
It is obvious that parallel lil-gp can be faced with the need to transfer one or several individuals to subpopulations that reside on different CPU. To make this possible the necessary functions had to be implemented using PVM.
Note: the above mentioned function only transfers individuals or trees. If the individuals were to be modified by the user in any way this would preclude the correct operation of parallel lil-gp!