Searching for resource-efficient programs: low-power pseudorandom number generators

ABSTRACT

Non-functional properties of software, such as power consumption and memory usage, are important factors in designing software for resource-constrained platforms. This is an area where Search-Based Software Engineering has yet to be applied, and this paper investigates the potential of using Genetic Programming and Multi-Objective Optimisation as key tools in satisfying non-functional requirements. We outline the benefits of such an approach and give an example application of evolving pseudorandom number generators and performing power-functionality trade-offs.

REFERENCES

• 1: Ent: A pseudorandom number sequence test program.http://www.fourmilab.ch/random/.
• 2: Mersenne Twister PRNG, University of Hiroshima. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html.
• 3: Michael Berthold , David J. Hand, Intelligent Data Analysis: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 4: Bruno Bouyssounouse , Joseph Sifakis, Embedded Systems Design: The ARTIST Roadmap for Research and Development (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 5: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 6: D. Burger, T. M. Austin, and S. Bennett. Evaluating Future Microprocessors: The Simple Scalar Tool Set.Technical Report CS-TR-1996-1308, Computer Sciences Department. University of Wisconsin-Madison, 1996.
• 7: J. Clark, J. Dolado, M. Harman, R. Hierons, B. Jones, M. Lumkin, B. Mitchell, S. Mancoridis, K. Rees, M. Roper, and M. Shepperd. Reformulating software engineering as a search problem. Software, IEE Proceedings, 150:161--175, 2003.
• 8: Carlos A. Coello, An updated survey of GA-based multiobjective optimization techniques, ACM Computing Surveys (CSUR), v.32 n.2, p.109-143, June 2000 [doi>10.1145/358923.358929]
• 9: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 10: Réjane Forré, The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.450-468, August 21-25, 1988
• 11: J. C. Hernandez, P. Isasi, and A. Seznec. On the design of state-of-the-art pseudo random number generators by means of genetic programming. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation, pages 1510--1516, 2004.
• 12: Jan Jannink, Cracking and co-evolving randomizers, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 13: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: J. R. Koza. Hierarchical genetic algorithms operating on populations of computer programs. In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, volume 1, pages 768--774. Morgan Kaufmann, 1989.
• 15: J. R. Koza. Evolving a computer program to generate random numbers using the genetic programming paradigm. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 37--44. Morgan Kaufmann, 1991.
• 16: C. Lamenca-Martinez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda. Lamar: A new pseudorandom number generator evolved by means of genetic programming. In Parallel Problem Solving from Nature IX, volume 4193, pages 850--859. Springer-Verlag, 2006.
• 17: S. Luke. ECJ: A Java-based Evolutionary Computation Research System. http://cs.gmu.edu/~eclab/projects/ecj/, 2007.
• 18: B. Mesman, L. Spaanenburg, H. Brinksma, E. Deprettere, E. Verhulst, F. Timmer, H. van Gageldonk, L. Eggermont, R. van Leuken, T. Krol, and W. Hendriksen. Embedded Systems Roadmap - Vision on technology for the future of PROGRESS. STW Technology Foundation, 2002.
• 19: Michael O'Neill , Conor Ryan, Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, Kluwer Academic Publishers, Norwell, MA, 2003
• 20: Amit Sinha , Alice Wang , Anantha P. Chandrakasan, Algorithmic transforms for efficient energy scalable computation, Proceedings of the 2000 international symposium on Low power electronics and design, p.31-36, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344188]
• 21: Moshe Sipper , Marco Tomassini, Co-evolving Parallel Random Number Generators, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.950-959, September 22-26, 1996
• 22: A F Webster , S E Tavares, On the design of S-boxes, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.523-534, June 1986, Santa Barbara, California, United States
• 23: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Technical Report 103, Swiss Federal Institute of Technology, 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming

General Terms:
Design

Keywords:
automatic programming, genetic programming, multi-objective optimisation, non-functional requirements, search based software engineering