Tag Archives: SBSE

Opacitor: search-based energy optimization of some ubiquitous algorithms #SBSE

DAASE project blogpost by Dr Sandy Brownlee, Senior Research Assistant, DAASE project, Stirling University

As more of our time is spent on our smart phones, the curse of empty batteries is increasingly important. While battery technology is continually advancing, we can also tackle the problem by reduce the power consumed by the phone. Several factors (like the display, wifi and GPS) impact on power consumption, but the CPU that runs the phone’s software is still a big consumer of energy. For example, the maximum CPU power of a Samsung Galaxy S3 is 2,845 mW, 2.53× the maximum power consumption of the screen and 2.5× that of the 3G hardware.

At the other end of the scale, electricity consumed by server centres run by the likes of Google and Facebook impacts on global climate change: in fact, the electricity consumed by servers was between 1.1 and 1.5% of global electricity production in 2010. So, reducing the energy consumed by CPUs is important!

Much of the code that’s being run relies on the same few algorithms, reimplemented for particular applications and hardware. Ideally code should be retuned for each new application but there are a few things that mean this is difficult in practice, so automated approaches are needed. We already have this for making software run faster – a tool called a “compiler” takes human readable source code and turns it into machine code, making speed improvements along the way. Often making a program run faster will mean it consumes less energy, but some instructions are more power hungry than others, so simply speeding the code up doesn’t guarantee a longer-lasting battery.

We have developed a tool called Opacitor, designed to measure the energy consumed by programs written in Java, one of the most popular programming languages. Opacitor estimates the energy each instruction will consume on a live system. This can be combined with search-based techniques to explore possible changes to a given program, finding a low-energy variation. The work is reported in a journal paper published this month, which focuses on three aspects of reducing the energy consumed by software.

Firstly, programs perform differently depending on the data they process. A common software task is sorting data, and variants of the Quicksort algorithm are a popular way to do this. Quicksort repeatedly chooses a point in the data called the pivot, and rearranges the data around it. The choice of the pivot and the “distribution” of the data being sorted affect how well this works. Our approach generated an automatic way to choose the pivot: this can be tuned to different distributions of data, with the sorting operation using up to 70% less energy than conventional approaches.

Secondly, energy consumption relates to other software properties. Would you exchange a lower quality camera or a few more speech recognition mistakes for another few minutes of battery when it’s nearly empty? We were able to show how multi-layer perceptrons, the core of deep learning and applications like text recognition, can be tuned to balance accuracy and energy use. In fact, sometimes we could get the best of both, but this relationship is complicated enough that automatically exploring the trade-off between the two properties is very helpful.

Thirdly, different components of an application interact in very subtle ways. Modern software typically makes use of libraries (software written by others to do common tasks), and there are often many alternatives doing the same job. It isn’t as simple as choosing the most energy efficient libraries and assembling them into one application, because two parts might be more energy efficient together than separately, perhaps because they share a common resource. We showed that by searching different combinations of “container classes” (software components for storing data), we were able to reduce energy consumption by almost 40%.

Overall then, this seems to be an area ripe for further development, and we hope that this work represents a step towards the ideal where software compilers include energy improvements as a matter of course.

 

 

 

DAASE research team and spinout MaJiCKe move to Facebook

mark and team at facebookDAASE research group MaJiCKe have moved to work with Facebook in London. MaJiCKe have developed software that uses Search Based Software Engineering (SBSE) to help engineers find bugs while reducing the inefficiencies of writing test code. Their product Sapienz automatically generates test sequences using SBSE to find crashes using the shortest path it can find. Sapienz is the world’s first automated test tool able to minimise the length of tests which simultaneously maximising the amount of code checked.

“We are very excited to have this outstanding opportunity to achieve real world impact for UCL’s excellent software engineering research”

Professor Mark Harman

The MaJiCKe team comprise Professor Mark Harman – Scientific Advisor, Yue Jia – CEO and Ke Mao – CTO from the department of Computer Science at University College London (UCL). Professor Harman cofounded the area of SBSE in 2001.

“We provide an atmosphere to nurture collaborations with industry, its great to see a team like this taking their world leading expertise to Facebook”

Jane Butler, UCL Engineering Vice Dean

All at DAASE wish Mark, Yue and Ke the very best of luck and look forward to hearing all about their contribution to Facebook’s goal of connecting the world.

 

 

DAASE SBSE Workshop – Day 2 – live blog

10am One minutes silence held at the beginning of the workshop for our beloved colleague Professor David Notkin who died yesterday. Our thoughts are with his family and friends at this very sad time.

Our first speaker this morning is Juergen Branke from Warwick Business School “Optimization in dynamic environments”

20130423-101939.jpg

Evolutionary algorithms have grown into a mature field of research in optimization and have proven to be effective and robust problem solvers for a broad range of static real world optimization problems. Yet, since they are based on the principles of natural evolution and since natural evolution is a dynamic process in a changing environment they are also well suited to dynamic optimization problems.

With appropriate adjustments evolutionary computation is able to continuously adapt and is promising for applications where very few function evaluations are possible.

Next is Robert Feldt from Chalmers University of Technology, Sweden with ” Interactive and Adaptive Automated Testing Environments”

15 years ago Robert wanted to automatically generate program code, He failed but learnt a lot from that. He developed an IDE where you could automatically generate test cases.

Fitness guidance – f-Equalizer – being developed which can compare test case similarity.

20130423-105226.jpg

It is implemented using a Javascript library called D3, it has a Ruby backend.

– break –

Next is Michael Orlov from Department of Computer Science, Ben-Gurion University, Israel

Evolving unrestricted Java software with FINCH

FINCH is a methodology for evolving Java bytecode enabling the evolution of extant unrestricted Java programs or programs.

Michael wanted to evolve some Java source code and improve some existing Java software.

The team decided to use Java – JVM bytecode rather than parse trees.

20130423-114734.jpg

They used bytecode because it is less fragile than source code but must be correct in order to run correctly so genetic operators are still delicate. Good genetic operators are needed to produce correct offspring.

20130423-122926.jpg

Java Wilderness, Artificial Ant

They found that completely unrestricted Java programs can be evolved via bytecode and extant Java programs can be improved.

– lunch –

First up after lunch is David White from Computing Sciences, University of Glasgow, UK talking about “The Programming Game: an alternative to GP for Expression Search”

David asks how well do we understand GP genetic programming search and talks about an alternative program search method. Monte Carlo tree search achieves some amazing results in the game of Go. It works by looking at game trees.

20130423-141235.jpg

Advantages of Monte Carlo tree search are concise solutions, the game tree is human readable and parallelisation.

Future work includes adapting Monte Carlo tree search for program search.

Our last speaker is Justyna Petke from CREST Centre, SSE Group, Department of Computer Science, UCL. She will be speaking about “Genetic improvement of software: a case study”

Genetic improvement programming aims to improve code. Code is changed by reusing lines of the original code and adding, deleting, mutation, crossover etc.

20130423-145049.jpg

Findings of the study were that genetic improvement programming automatically improves system behaviour in selected cases.

-Workshop wrap up –

Professor Mark Harman, DAASE project PI, thanks our speakers and everyone for coming.

20130423-151203.jpg

Our workshop is now finished. Many thanks to all of our speakers and session chairs and of course our audience. See you at #COW27 😃

Live Blog – Dynamic Adaptive Automated Search Based Software Engineering (joint DAASE/COW workshop)

Please refresh page for updates – Live blog commencing 10.30am on 22nd April 2013

The DAASE COW will be running all day 22nd and 23rd April at UCL

Program here: http://crest.cs.ucl.ac.uk/cow/26/

Professor Mark Harman, DAASE project PI introduces the day by welcoming everyone to UCL, to London and to #CREST26.

Prof Mark Harman welcomes everyone

Prof Mark Harman welcomes everyone

Professor Harman asks everyone at the workshop to introduce themselves.

20130422-110315.jpg

11:15 Keynote: Living with change and uncertainty, and the quest for incrementality. Prof Carlo Ghezzi, Dipartimento di Elettronica e Informazione, Politecnico di Milano, Italy

Prof Ghezzi begins by asking everyone to interrupt if they have any questions.

Basic findings from his research of the last 4 years. Software is everywhere, there are cyber-physical systems, new behaviours emerge dynamically and systems need to run continuously.

The challenge: continuous change and uncertainty in the requirements, the infrastructure, the platform. At the same time our systems need to be dependable.

Change and dependability don’t go together very well.

Slide: The questions and the answers

The traditional separation between development time and runtime must be broken.

20130422-111633.jpg

You need to convince yourself that your specification and your assumptions entail the specification of the requirements.

20130422-112151.jpg

Hidden assumptions need to be made explicit. Assumptions are heavily affected by change and uncertainty. Changes lead to software evolution, adaptation is a special case of evolution. Changes matter because they may affect dependability.

Professor Carlo Ghezzi on Google Scholar

Continuous verification needs to be performed to detect the need for evolution.

Q: is it possible to identify a subset of priorities at runtime?

A: verification needs to be made incremental. It is a challenge.

We have focused mainly on non-functional requirements quantitatively stated in probabilistic terms. These things all change out of your control and the users profile is also subject to change.

Prof Ghezzi’s team’s approach, there are several models with different viewpoints, focusing on non-functional properties and Markov models.

The DMTC Model

20130422-115606.jpg

The problem: is it affordable everytime you have a change to run the model checker from scratch? Can changes be handled incrementally? This requires revisiting verification procedures.

Running the model checker can be impractical. Verification needs to have an agile approach, it must be incremental.

Incrementality by parameterization: requires anticipation of changing parameters, you can do a partial evaluation of the model with transitions as variables. Things that may change are represented as variables. Values are partly numeric and partly symbolic represented in matrices.

Prof Ghezzi states we must move verification to runtime, thru incrementality formal specification/verification can be reconciled with agility.

[SB This reminds me of our 2009 paper “Formal vs Agile: survival of the fittest?”]

Summary: self adaptation requires continued reasoning and verification at runtime because of the detected changes. Verification has to be the driver, if you want it to be safe, the only way to be dependable is to use a model view. Mainstream verification approaches must be adapted.

Prof Carlo Ghezzi can be contacted via Twitter: @carloghezzi

Next is Gabriela Ochoa from Stirling University talking about “Hyper-heuristics and cross-domain optimisation”

20130422-124833.jpg

There are various autonomous/adaptive search approaches.

Hyper heuristics work well on different problems and are bespoke. They comprise heuristic selection followed by heuristic generation.

20130422-125608.jpg

Gabriela describes several case studies in hyper-heuristics. The university course timetabling case study which looked at minimising conflicts. Many operators were available which could be selected on the fly. The five best operators were identified.

Gabriela has found that good algorithms are hybrid and dynamic, adaptive approaches can beat state of the art algorithms.

LUNCH

Prof Marc Schonauer from INRIA speaks next about “Adaptive operator selection with rank based multi armed bandits”

Why do we want to set parameters online? Because there is no single best operator.

20130422-141331.jpg

Operator selection factors to consider: the exploration vs exploitation balance, dynamical setting, using a change detection test eg Page-Hinkley which enforces the efficient detection of changes in time series.

The Area Under the Curve AUC in machine learning can be used to evaluate binary classifiers with performance a percentage of missclassification. This is equivalent to the MannWhitneyWilcoxon test, where two sequences have the same order.

Rank based AUC can be used with Multi Armed Bandits MAB.

20130422-143134.jpg

The goals of the experiments, carried out were: performance, and robustness/generality.

The results show that MAB outperforms other methods.

Sasa Misailovic talks next about “Accuracy aware program transformations“.

Current trends are big data sets and energy consciousness.

This gives an opportunity to automatically transform snd adapt programs. This can also help with energy related problems like battery life etc.

20130422-145010.jpg

To optimize transformations a code perforation framework has been developed to enable automatic discovery of profitable trade-offs between the time required to perform a computation and the accuracy of the final result. The process has three main stages: find candidates, analyse effects, navigate tradeoff space.

Results of a code perforation experiment showed that performance improved by a factor of over two for a range of applications, but there is no guarantee of accuracy or safety with changing the result that the application produces by less than 10%.

TEA BREAK [Yay! This is thirsty work]

UCL CREST’s Yuanyuan Zhang is next presenting “Hyper-heuristic based strategic release planning”

Difficulties with release planning: complex constraints, incompletexinformation, multiple objectives and large decision space.

20130422-155424.jpg

Strategic Release Planning: using hyper heuristic algorithms in selecting and assigning requirements.

A model has been developed which has been used with five different data sets, including two from Motorola and Ericsson.

20130422-160840.jpg

The data sets all have multiple stakeholders with multiple needs and requirements. Yuanyuan presents a detailed breakdown of the results.

Another experiment compares the performance of hyper heuristic algorithms.

Leandro Minku from CERCIA, University of Birmingham presents on “Ensemble learning for software effort estimation: from static to dynamic analysis”

followed by

Simon Poulding from Iniversity of York on “Searching for strategies that verify MDE Toolchains”

DINNER and see you all tomorrow….