Deployment of CPU and GPU-based genetic programming on heterogeneous devices

ABSTRACT

A widely available and economic means of increasing the computing power applied to a problem is to use modern graphics processing units (GPUs) for parallel processing. We present a new, optimized general methodology for deploying genetic programming (GP) to the PC, Xbox 360 video game console, and Zune portable media device. This work describes, for the first time, the implementation considerations necessary to maximize available CPU and GPU (where available) usage on the three separate hardware platforms. We demonstrate the first instance of GP using portable digital media device hardware. The work also presents, for the first time, an Xbox 360 implementation that uses the GPU for fitness evaluation. Implementations on each platform are also benchmarked on the basis of execution time for an established GP regression benchmark.

REFERENCES

• 1: Andre, D. and Koza, J. A Parallel Implementation of Genetic Programming that Achieves Super-linear Performance. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, CSREA (1996), 1163--1174.
• 2: Jeff Andrews , Nick Baker, Xbox 360 System Architecture, IEEE Micro, v.26 n.2, p.25-37, March 2006 [doi>10.1109/MM.2006.45]
• 3: Banzhaf, W., Harding, S., Langdon, W., and Wilson, G. Accelerating Genetic Programming Through Graphics Processing Units. In Genetic Programming Theory and Practice (GPTP) VI. Springer, 2008, 229--248.
• 4: Harding, S. and Banzhaf, W. Fast Genetic Programming on GPUs. Proceedings of the 10th European Conference on Genetic Programming, Springer (2007), 90--101.
• 5: Malcolm I. Heywood , A. Nur Zincir-Heywood, Register Based Genetic Programming on FPGA Computing Platforms, Proceedings of the European Conference on Genetic Programming, p.44-59, April 15-16, 2000
• 6: Microsoft Corporation. XBox 360 Device Capabilities. http://msdn2.microsoft.com/en-us/library/bb313967.aspx, 2007.
• 7: Microsoft Corporation. Zune Networking Overview. http://msdn.microsoft.com/en--us/library/dd282499.aspx, 2008.
• 8: Microsoft Corporation. XBox 360 Programming Considerations. http://msdn.microsoft.com/en-us/library/bb203938(XNAGameStudio.10).aspx, 2009.
• 9: Wilson, G. and Banzhaf, W. Linear Genetic Programming GPGPU on Microsoft's Xbox 360. Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2008), IEEE Press (2008), 378--385.
• 10: Man Leung Wong, Parallel multi-objective evolutionary algorithms on graphics processing units, Proceedings of the 11th annual conference companion on Genetic and evolutionary computation conference, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1570256.1570354]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
GPGPU, XBOX 360, ZUNE, genetic programming, graphics processing unit, heterogeneous devices