Welcome to the Parallel PIKAIA Homepage. If you are interested in using the genetic algorithm based FORTRAN-77 optimization subroutine PIKAIA, and the modeling fitness-function that you want to maximize is computationally intensive, you have come to the right place. Here you will find all that you need to run PIKAIA in parallel (using the "Full Generational Replacement" evolutionary strategy) on your Linux cluster or supercomputer.
PIKAIA was developed by Paul Charbonneau and Barry Knapp at the High Altitude Observatory of the National Center for Atmospheric Research, and version 1.2 was released in April 2002. The parallel implementations found here were developed by Travis Metcalfe: the PVM version was part of his doctoral thesis in astronomy at the University of Texas at Austin, and the MPI version was developed during a postdoctoral fellowship at the Harvard-Smithsonian Center for Astrophysics
PVM
MPI
In practice, this recipe for dividing the workload between the available processors proved to be very scalable. Since very little data is exchanged between the master and slave tasks, our 64-node Linux cluster provided a speedup factor of about 53 over the performance on a single processor.
After starting the slave program on every available processor, pvm_fitness.f sends an array containing scaled values of the parameters to each slave job over the network. In the first generation, these values are completely random; in subsequent generations, they are the result of the selection, crossover, and mutation of the previous generation, performed by the non-parallel portions of PIKAIA. Next, the subroutine listens for responses from the network and sends a new set of parameters to each slave job as it finishes the previous calculation. When all sets of parameters have been sent out, the subroutine begins looking for jobs that may have crashed and re-submits them to slaves that have finished and would otherwise sit idle. If a few jobs do not return a fitness after an elapsed time much longer than the average runtime required to compute a model, the subroutine assigns them a fitness of zero. When every set of parameters in the generation have been assigned a fitness value, the subroutine returns to the main program to perform the genetic operations -- resulting in a new generation of models to calculate. The process continues for a fixed number of generations, chosen to maximize the success rate of the search.
Slave Program
To allow many instances of our code to run simultaneously, we added a
front end that communicates with the master program through PVM routines.
This code (ff_slave.f) combined with the fitness
function (userff.f) constitutes the slave program,
and is run on each node of our Linux cluster.
The operation of the slave program is relatively simple. Once it is
started by the master program, it receives a set of parameters from the
network. It then calls the fitness function (a parallel version of the
sample fitness function twod in this distribution) with these
parameters as arguments, and returns a fitness value to the master
program.
Compiling and Running
This distribution of PVM-PIKAIA was developed to work under
PVM 3.4.4. Once you
have obtained and installed this software, you can compile the sample
program using aimk (architecture independent make), which comes
with the distribution. Place all of the source code for Parallel
PIKAIA and our Makefile.aimk in the
$PVM_ROOT/examples directory, and type aimk pikaia_ff.
The code can then be run in parallel once the pvm daemon has been started
on every available node of your machine.
Master Subroutine
The master subroutine for MPI (pikaia_master.f)
is nearly identical to the PVM version -- instead of evaluating the fitnesses
of the population one at a time in a DO loop, we make a single call to a new
subroutine that evaluates the fitnesses in parallel. For the MPI version,
there is simply a different parallel fitness evaluation subroutine
(mpi_fitness.f).
Just as with the PVM version mpi_fitness.f sends an array containing scaled values of the parameters to each slave job over the network. In the first generation, these values are completely random; in subsequent generations, they are the result of the selection, crossover, and mutation of the previous generation, performed by the non-parallel portions of PIKAIA. Next, the subroutine listens for responses from the network and sends a new set of parameters to each slave job as it finishes the previous calculation. When all sets of parameters have been sent out, the subroutine begins looking for jobs that may have crashed and re-submits them to slaves that have finished and would otherwise sit idle. If a few jobs do not return a fitness after an elapsed time much longer than the average runtime required to compute a model, the subroutine assigns them a fitness of zero. When every set of parameters in the generation have been assigned a fitness value, the subroutine returns to the main program to perform the genetic operations -- resulting in a new generation of models to calculate. The process continues for a fixed number of generations, chosen to maximize the success rate of the search.
Slave Subroutine
The slave subroutine communicates with the master task through MPI calls.
This code (ff_slave.f) relies on a user-defined
fitness function (userff.f), and runs simulataneously
on every available processor.
The operation of each slave task is relatively simple. Once it is
started, it waits to receive a set of parameters from the master task
over the network. It then calls the fitness function (a parallel version
of the sample fitness function twod in this distribution) with
these parameters as arguments, and returns a fitness value to the master
task.
Compiling and Running
This distribution of MPI-PIKAIA was developed to work under
MPICH 1.2.5.
Once you have obtained and installed this software, you can compile the
sample program using make with the provided
Makefile. Simple place all of the source code
for MPI-PIKAIA in the directory where you want it to run,
and type make pikaia. The code can then be run in parallel by
issuing a command like: mpirun -np <#proc> pikaia