ABSTRACT
We introduce a mutation-based approach to automatically discover and expose `deep' (previously unavailable) parameters that affect a program's runtime costs. These discovered parameters, together with existing (`shallow') parameters, form a search space that we tune using search-based optimisation in a bi-objective formulation that optimises both time and memory consumption. We implemented our approach and evaluated it on four real-world programs. The results show that we can improve execution time by 12\% or achieve a 21\% memory consumption reduction in the best cases. In three subjects, our deep parameter tuning results in a significant improvement over the baseline of shallow parameter tuning, demonstrating the potential value of our deep parameter extraction approach.
- A. Arcuri and G. Fraser. On parameter tuning in search based software engineering. In Search Based Software Engineering. 2011. Google ScholarDigital Library
- E. D. Berger and B. G. Zorn. Diehard: Probabilistic memory safety for unsafe languages. In Programming Language Design and Implementation, PLDI '06, 2006. Google ScholarDigital Library
- E. D. Berger, B. G. Zorn, and K. S. McKinley. Reconsidering custom memory allocation. In Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '02, 2002. Google ScholarDigital Library
- N. Brake, J. R. Cordy, E. Dan Y, M. Litoiu, and V. Popes U. Automating discovery of software tuning parameters. In Workshop on Software Engineering for Adaptive and Self-managing Systems, SEAMS '08, 2008. Google ScholarDigital Library
- J. M. Colmenar, J. L. Risco-Mart n, D. Atienza, and J. I. Hidalgo. Multi-objective optimization of dynamic memory managers using grammatical evolution. In Conference on Genetic and Evolutionary Computation, GECCO '11, 2011. Google ScholarDigital Library
- C. T apu s, I.-H. Chung, and J. K. Hollingsworth. Active harmony: Towards automated performance tuning. In Conference on Supercomputing, Supercomputing '02, 2002. Google ScholarDigital Library
- K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. Evolutionary Computation, IEEE Transactions on, 6(2), 2002. Google ScholarDigital Library
- H. Do, S. Elbaum, and G. Rothermel. Supporting controlled experimentation with testing techniques: An infrastructure and its potential impact. Empirical Software Engineering, 10(4), 2005. Google ScholarDigital Library
- C. Fonseca and P. Fleming. On the performance assessment and comparison of stochastic multiobjective optimizers. In PPSN. Springer Berlin Heidelberg, 1996. Google ScholarDigital Library
- M. Harman. The current state and future of search based software engineering. In 2007 Future of Software Engineering, FOSE '07, 2007. Google ScholarDigital Library
- M. Harman, Y. Jia, and W. Langdon. Babel pidgin: Sbse can grow and graft entirely new functionality into a real world system. In Search-Based Software Engineering, volume 8636 of Lecture Notes in Computer Science, pages 247--252. Springer International Publishing, 2014.Google ScholarCross Ref
- M. Harman, Y. Jia, and W. B. Langdon. Strong higher order mutation-based test data generation. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE '11, pages 212--222, 2011. Google ScholarDigital Library
- M. Harman, Y. Jia, W. B. Langdon, J. Petke, I. H. Moghadam, S. Yoo, and F. Wu. Genetic improvement for adaptive software engineering (keynote). In Symposium on Software Engineering for Adaptive and Self-Managing Systems, SEAMS, 2014. Google ScholarDigital Library
- M. Harman, Y. Jia, and Y. Zhang. Achievements, open problems and challenges for search based software testing (keynote). In 8th IEEE International Conference on Software Testing, Verification and Validation (ICST 2014), Graz, Austria, April 2015.Google Scholar
- H. Hoffmann, S. Sidiroglou, M. Carbin, S. Misailovic, A. Agarwal, and M. Rinard. Dynamic knobs for responsive power-aware computing. In Architectural Support for Programming Languages and Operating Systems, 2011. Google ScholarDigital Library
- F. Hutter, D. Babic, H. H. Hoos, and A. Hu. Boosting verification by automatic tuning of decision procedures. In Formal Methods in Computer Aided Design, 2007. FMCAD '07, Nov 2007. Google ScholarDigital Library
- F. Hutter, H. H. Hoos, K. Leyton-Brown, and T. Stützle. ParamILS: an automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36(1), 2009. Google ScholarDigital Library
- Y. Jia and M. Harman. MILU: A Customizable, Runtime-Optimized Higher Order Mutation Testing Tool for the Full C Language. In Proceedings of the TAIC PART'08, pages 94--98, Windsor, UK, 29--31 August 2008. Google ScholarDigital Library
- Y. Jia and M. Harman. An analysis and survey of the development of mutation testing. Software Engineering, IEEE Transactions on, 37(5), 2011. Google ScholarDigital Library
- T. Katagiri, K. Kise, H. Honda, and T. Yuba. Fiber: A generalized framework for auto-tuning software. In High Performance Computing. 2003.Google ScholarCross Ref
- W. B. Langdon, M. Modat, J. Petke, and M. Harman. Improving 3d medical image registration cuda software with genetic programming. In Conference on Genetic and Evolutionary Computation, GECCO '14, 2014. Google ScholarDigital Library
- D. Lea and W. Gloger. A memory allocator, 2000. http://g.oswego.edu/dl/html/malloc.html.Google Scholar
- M. Papadakis, Y. Jia, M. Harman, and Y. L. Traon. Trivial Compiler Equivalence: A Large Scale Empirical Study of a Simple Fast and Effective Equivalent Mutant Detection Technique. In Proceedings of the 37th International Conference on Software Engineering, 15. To appear.Google Scholar
- J. Petke, M. Harman, W. Langdon, and W. Weimer. Using genetic improvement and code transplants to specialise a c++ program to a problem class. In Genetic Programming. 2014.Google Scholar
- J. L. Risco-Mart n, D. Atienza, J. M. Colmenar, and O. Garnica. A parallel evolutionary algorithm to optimize dynamic memory managers in embedded systems. Parallel Computing, 36(10 - 11), 2010. Parallel Architectures and Bioinspired Algorithms. Google ScholarDigital Library
- J. L. Risco-Mart n, D. Atienza, R. Gonzalo, and J. I. Hidalgo. Optimization of dynamic memory managers for embedded systems using grammatical evolution. In Conference on Genetic and Evolutionary Computation, GECCO '09, 2009. Google ScholarDigital Library
- J. L. Risco-Mart n, J. M. Colmenar, J. I. Hidalgo, J. Lanchares, and J. D az. A methodology to automatically optimize dynamic memory managers applying grammatical evolution. Journal of Systems and Software, 91(0), 2014. Google ScholarDigital Library
- E. Schulte, Z. Fry, E. Fast, W. Weimer, and S. Forrest. Software mutational robustness. Genetic Programming and Evolvable Machines, 15(3), 2014. Google ScholarDigital Library
- R. Vuduc, J. W. Demmel, and J. Bilmes. Statistical models for automatic performance tuning. In International Conference on Computational Science (ICCS), 2001. Google ScholarDigital Library
- R. C. Whaley and J. J. Dongarra. Automatically tuned linear algebra software. In Conference on Supercomputing, Supercomputing '98, 1998. Google ScholarDigital Library
- X. Yao, M. Harman, and Y. Jia. A study of equivalent and stubborn mutation operators using human analysis of equivalence. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pages 919--930, 2014. Google ScholarDigital Library
- E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4), Nov 1999. Google ScholarDigital Library
- B. Zorn and D. Grunwald. Empirical measurements of six allocation-intensive C programs. SIGPLAN Not., 27(12), Dec. 1992. Google ScholarDigital Library
Index Terms
- Deep Parameter Optimisation
Recommendations
When parameter tuning actually is parameter control
GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computationIn this paper, we show that sequential parameter optimization (SPO), a method that was designed for (offline) parameter tuning, can be successfully used as a controller for multistart approaches of evolutionary algorithms (EA). We demonstrate this by ...
Meta-optimization for parameter tuning with a flexible computing budget
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computationMeta-optimization techniques for tuning algorithm parameters usually try to find optimal parameter settings for a given computational budget allocated to the lower-level algorithm. If the available computational budget changes, parameters have to be ...
Bio-inspired Optimization Techniques for SVM Parameter Tuning
SBRN '08: Proceedings of the 2008 10th Brazilian Symposium on Neural NetworksMachine learning techniques have been successfully applied to a large number of classification problems. Among these techniques, Support Vector Machines (SVMs) are well know for the good classification accuracies reported in several studies. However, ...
Comments