Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Current consumer-grade computers and game devices incorporate very powerful processors that can be used to accelerate many classes of scientific codes. However, programming multi-core chips, hybrid multi-processors or graphical processing units is not an easy task for those programmers that deal mainly with sequential codes. In this paper, we explore the ability of the Cell Broadband Engine to run a particular Estimation of Distribution Algorithm. From an initial sequential version, we develop a multi-threaded one that is afterwards reworked to run on a Cell. The multi-threaded version is capable of efficiently use current multi-core chips, such as those used in desktop PCs. However, the efficiency of the Cell version is very low. We analyze the causes of these discouraging results, and provide some clues about the class of problems that could be efficiently ported to the Cell.

REFERENCES

• 1: FixstarsCorp. homepage. http://www.fixstars.com/.
• 2: GA-CBEhomepage. http://ga-cbe.sourceforge.net/.
• 3: Enrique Alba , José M. Troya, A survey of parallel distributed genetic algorithms, Complexity, v.4 n.4, p.31-52, Mar./Apr. 1999 [doi>10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.3.CO;2-W]
• 4: Filip Blagojevic , Dimitris S. Nikolopoulos , Alexandros Stamatakis , Christos D. Antonopoulos, Dynamic multigrain parallelization on the cell broadband engine, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229445]
• 5: W. Bossert. Mathematical optimization: Are there abstract limits on natural selection? In P. S. Moorehead and M. M. Kaplan, editors, Mathematical Challenges to the Neo-Darwinian Interpretation of Evolution, pages 35--46. The Wistar Institute Press, Philadelphia, PA, 1967.
• 6: D. R. Butenhof. Programming with POSIXÆ AÝo Threads. Addison-Wesley Professional Computing Series, 1997.
• 7: Erick Cantu-Paz, Efficient and Accurate Parallel Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• 8: L. DelaOssa, J. A. Gamez, and J. M. Puerta. Migration of probability models instead of individuals: Analternative when applying the island model to EDAs. In X. Yao, E. K. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervos, J. A. Bullinaria, J. E. Rowe, P. Tino, A. Kaban, and H. P. Schwefel, editors, PPSN, volume 3242 of Lecture Notes in Computer Science, pages 242--252. Springer, 2004.
• 9: L. J. Fogel. Autonomous automata. Industrial Research, 4:14--19, 1962.
• 10: Ka-Ling Fok , Tien-Tsin Wong , Man-Leung Wong, Evolutionary Computing on Consumer Graphics Hardware, IEEE Intelligent Systems, v.22 n.2, p.69-78, March 2007 [doi>10.1109/MIS.2007.28]
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: J Grefenstette, Optimization of control parameters for genetic algorithms, IEEE Transactions on Systems, Man and Cybernetics, v.16 n.1, p.122-128, Jan./Feb. 1986 [doi>10.1109/TSMC.1986.289288]
• 13: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 14: IBM. Software Development Kit for Multicore Acceleration. Programming Tutorial. Version 3.1. 2008.
• 15: J. A. Kahle , M. N. Day , H. P. Hofstee , C. R. Johns , T. R. Maeurer , D. Shippy, Introduction to the cell multiprocessor, IBM Journal of Research and Development, v.49 n.4/5, p.589-604, July 2005
• 16: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 17: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 18: Jose A. Lozano , Pedro Larrañaga , Iñaki Inza , Endika Bengoetxea, Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 19: Heinz Mühlenbein, The equation for response to selection and its use for prediction, Evolutionary Computation, v.5 n.3, p.303-346, Fall 1997 [doi>10.1162/evco.1997.5.3.303]
• 20: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 21: J. Ocenasek and J. Schwarz. The parallel Bayesian optimization algorithm. In Proceedings of the European Symposium on Computational Intelligence, pages 61--67, 2000.
• 22: J. Ocenasek and J. Schwarz. The distributed Bayesian optimization algorithm for combinatorial optimization. In EUROGEN -- Evolutionary Methods for Design, Optimisation and Control, CIMNE, pages 115--120, 2001.
• 23: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 24: Martin Pelikan , Kumara Sastry , Erick Cantú-Paz, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 25: I. Rechenberg. Evolutions strategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart, 1973.
• 26: J. Rudin. Accelerating persistent surveillance radar with the cell broadband engine. Embedded Technology Journal, 2008.
• 27: W. Darrell Whitley , Soraya B. Rana , Robert B. Heckendorn, Island Model genetic Algorithms and Linearly Separable Problems, Selected Papers from AISB Workshop on Evolutionary Computing, p.109-125, April 07-08, 1997
• 28: A. Wirawan, K. C. Keong, and B. Schmidt. Parallel dna sequence alignment on the cell broadband engine. In PPAM, pages 1249--1256, 2007.
• 29: 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]
• 30: A. A. Zhigljavsky. Theory of Global Random Search. Kluwer Academic Publishers, 1991.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
cell broadband engine, estimation of distribution algorithms, parallel programming