Characterizing the Parallel Speedup of the Genetic Programming Environment for FIFTH on a High Performance Computing Cluster, 16-R9827

Printer Friendly Version

Principal Investigator
Kenneth L. Holladay

Inclusive Dates:  06/02/08 – 10/02/08

Background - SwRI recently completed a proof-of-concept demonstration of a vector-based Genetic Programming Environment (GPE5) using a new programming language called FIFTH. This software tool has the potential to open the field of genetic programming to solving problems that were previously intractable. The first version of GPE5 used a distributed architecture based on CORBA. The code base proved to be robust for heterogeneous groups of computing platforms connected in a local area network (LAN), exhibiting reasonable efficiency for small numbers of resources. However, it is well known that applying genetic programming to large problems can require a significant amount of computational effort. In order to reduce the wall clock time required to solve problems, this quick look project investigated the performance enhancements resulting from modifying GPE5 to run on a High-Performance Computing Cluster (HPC) with hundreds of processors.

Approach - The goal for the software conversion was to achieve a code base that could be compiled on multiple operating systems (Windows, Linux, Sun) and produce three operational systems: a stand-alone version for a single computer, a distributed version using CORBA (the original implementation), and a parallel HPC version using the Message Passing Interface (MPI). The first step was to restructure the code to decouple the communication requirements from the genetic programming logic. The result was a core FIFTH library that contained all of the GP components including data set management, fitness calculation and genetic manipulation. This core consists of 45 files with approximately 20,000 source lines of code (SLOC). Constructing the CORBA version requires an additional 11 files (approximately 3,000 SLOC).

The design of the MPI version required evaluation of three different architectures. The most effective used an approach that does not require centralized control; the entire GP algorithm is run on each processor. After a configurable number of generations, each process gives a copy of its best programs to each of its four neighbors, where each of the processors is abstractly connected in a toroidal grid. Each processor acts as an island of GP activity, with cross breeding between islands providing essential genetic material migration.

Accomplishments - All of the goals were successfully achieved. SwRI now has a genetic programming environment that can be deployed in three configurations: stand-alone, distributed, and parallel. Additional performance improvements implemented during the HPC testing phase achieved an almost linear speedup relationship for classes of problems where significant portions of the data set can be held entirely in memory.

For linear regression problems, the parallel version of GPE5 exhibited a linear speedup as a function of the number of processors.

2008 Program Home