Workshop 7: Analysis Techniques for Energy Aware Computing

The Special focus of this workshop is on analysis techniques for energy efficient software and systems with the aim to foster knowledge exchange between the TACLe and the EACO communities, and to establish new research collaborations to join forces in advancing the state of the art in energy-aware computing.The programme contains a series of presentations from TACLe members, from members of the EACO community, and also invited presentations from guest speakers.

This workshop is being held on Weds 10th and Thurs 11th September 2014. The agenda is available in EACO Workshop 7 Agenda (PDF, 51kB). EACO W7 Travel and Hotels (PDF, 41kB) is also now available. Any further information updates will follow in due course.

Abstracts

Energy Efficient Software
Lee Smith, ARM Fellow

Presentation: EACO W7 Lee Smith (PDF, 503kB)

These days, I work mostly where technology meets business. Technology has value when it creates or enables business capabilities that in turn generate products. Technology does not change the world: products change the world. I spend most of my working week figuring out what technology means for my business-oriented colleagues â€" lawyers, salespeople, marketers, product managers, and engineering managers. As a company, ARM 's views of technology are unusually informed by the views of our most important partners and customers. Our 2013 revenues were more than $1Bn but the our partners did 10-20x this much business based on our technology. ARM might well "punch above its weight" but we also represent an industry consensus focussed around the boundary between technology that differentiates the products produced by our industry and technology that is non-differentiating. ARM both leads and follows! This sets the context for a rapid tour of what Energy Efficient Software might mean for ARM, focussing on emerging markets for our technology: HPC, servers, and internet of things. Surprisingly, at an abstract level there are some common threads. While I have not set out to be controversial, I hope that some of my simplifications will provoke push-back during the workshop. I look forward to the discussion!

A high-level model of embedded flash energy consumption
James Pallister, University of Bristol

Presentation: EACO W7 James Pallister (PDF, 1,982kB)

The alignment of code in the flash memory of deeply embedded SoCs can have a large impact on the total energy consumption of a computation. We investigate the effect of code alignment in six SoCs and find that a large proportion of this energy (up to 15% of total SoC energy consumption) can be saved by changes to the alignment.

A flexible model is created to predict the read-access energy consumption of flash memory on deeply embedded SoCs, where code is executed in place. This model uses the instruction level memory accesses performed by the processor to calculate the flash energy consumption of a sequence of instructions. We derive the model parameters for five SoCs and validate them. The error is as low as 5%, with a 11% average normalized RMS deviation overall.

The scope for using this model to optimize code alignment is explored across a range of benchmarks and SoCs. Analysis shows that over 30% of loops can be better aligned. This can siagnificantly reduce energy while increasing code size by less than 4%. We conclude that this effect has potential as an effective optimization, saving significant energy in deeply embedded SoCs.

Power & energy modelling of multi-core processors for system-level design space exploration
Oscar Palomar Perez, BSC

Presentation: EACO W7 Oscar Palomar Perez (PDF, 3,218kB)

We present a novel power/energy based DSE methodology with better trade-off between accuracy and speed. First, we developed generic functional-level power models for the different parts of system to estimate the power/energy. Second, we built a System-based virtual platform prototype of the processor architecture to extract accurately the functional activities needed by the power model. Third, we designed a runtime task-dependencies management technique based on programming model for multi-core execution. This is used to estimate the effect of DVFS and optimize scheduling of the tasks to the multi-core.

Timing Analysis of Parallel Software Using Abstract Execution
Björn Lisper, Mälardalen University

Presentation: EACO W7 Björn Lisper (PDF, 193kB)

A major trend in computer architecture is multi-core processors. To fully exploit this type of parallel processor chip, programs running on it will have to be parallel as well. This means that even hard real-time embedded systems will be parallel. Therefore, it is of utmost importance that methods to analyze the timing properties of parallel real-time systems are developed. We present an algorithm that is founded on abstract interpretation and derives safe approximations of the execution times of parallel programs. The algorithm is formulated and proven correct for a simple parallel language with parallel threads, shared memory and synchronization via locks.

Using Static Program Analysis Techniques for Energy Analysis
Simon Wegener, AbsInt Angewandte Informatik GmbH

Presentation: EACO W7 Simon Wegener (PDF, 6,493kB)

Static program analysis has been successfully applied to compute safe upper bounds of a program's worst-case execution time (WCET). This talk explores some ideas in how to carry over the established techniques used for WCET analysis into the field of energy analysis. In particular, we will discuss two possible ways of transforming our timing analysis framework into an energy analysis framework, depending on whether power consumption is seen as a property of the hardware or as part of program semantics.

Static Analysis of Energy Consumption
Manuel Hermenegildo, IMDEA

Presentation: EACO W7 Manuel Hermenegildo (PDF, 3,985kB)

We present our overall approach for the inference and verification of upper- and lower-bounds on the energy consumption of programs, as well as some current results from our tools. The bounds we infer and check are functions of the sizes of the input data to the program. Our tools are based on translating the program to a block-based intermediate representation, expressed as horn clauses. We also present some recent improvements to resource bounds inference, including casting the cost analysis more fully within abstract interpretation frameworks and using sized shape data abstractions. The energy analysis makes use of ISA- and LLVM-level models of the cost of instructions or sequences of instructions. The inferred bounds compare well to measurements on the hardware.

Hardware parametric static energy analysis
Marko van Eekelen, University of Nijmegen

Presentation: EACO W7 Marko van Eekelen (PDF, 4,246kB)

Energy inefficient software implementations may cause battery drain for small systems and high energy costs for large systems. Dynamic energy analysis is often applied to mitigate these issues. However, this is often hardware-specific and requires repetitive measurements using special equipment.

We present a static analysis deriving upper-bounds for energy consumption based on an introduced energy-aware Hoare logic. Software is considered together with models of the hardware it controls. The Hoare logic is parametric with respect to the hardware. Energy models of hardware components can be specified separately from the logic. Parametrised with one or more of such component models, the analysis can statically produce a sound (over-approximated) upper-bound for the energy-usage of the hardware controlled by the software. The EcaLogic tool implementing this analysis is parametric with respect to a set of hardware component models. Its results are symbolic over the program parameters.

Energy Modelling and Static Analysis for Energy Transparency - Part 1, Part 2
Kyriakos Georgiou, Steve Kerrison and Jeremy Morse, University of Bristol

Presentations:

Part 1: EACO W7 Steve Kerrison (PDF, 1,241kB)
Part 2: EACO W7 Kyriakos Georgiou (PDF, 2,501kB)

We give an overview of the work at the University of Bristol on energy transparency of multi-core embedded systems at various levels in the software-hardware stack. An Instruction Set Architecture (ISA) level energy model for the multi-threaded XS1 architecture is presented, along with current work into modelling multi-core networks of these processors, including communication costs. These models can be utilised by instruction set simulation and static analysis techniques to predict the energy consumption of a program. We then present two static analysis approaches to predict the Worst Case Energy Consumption (WCEC) of programs at ISA level, and a mapping technique that lifts this analysis to a higher level of abstraction within the software toolchain, namely LLVM IR. Finally, we are reporting on a preliminary investigation into the construction of a WCEC version of our current energy model.

Coordination for Energy
Clemens Grelck, Universiteit van Amsterdam

Presentation: EACO W7 Clemens Grelck (PDF, 202kB)

Coordination is an established methodology for assembling concurrent applications for today's prevalent parallel machines from conventionally implemented sequential building blocks. S-Net is such a coordination language that achieves a near-complete separation of concerns between the engineering of application-specific components and their orderly dynamic interaction in a concurrent execution environment. S-Net promotes reasonably coarse-grained but otherwise fairly conventional functions into stream-processing components and provides a small combinator language derived from first principles that allows the definition of streaming networks. The S-Net compiler and runtime system jointly organise program execution through mapping of component instances to execution resources. We suggest to carry over the idea of coordination to energy-aware computing. The idea is to augment specifications of components with energy information. This information could be annotated (somewhat guessed) or inferred by component-level tools. We anticipate that energy information is with respect to certain execution resource architecture and that multiple functionally equivalent implementations of the same component may exist with different energy-wise behaviour when run on different execution units of a heterogeneous computing system. It would then be the task of the coordination compiler and runtime system to make adequate implementation selection and mapping decisions with respect to desired application behaviour in terms of execution performance and energy consumption in a given execution environment.

Compositional resource analysis in Hume using automatic amortisation
Kevin Hammond, University of St Andrews

Presentation: EACO W7 Kevin Hammond (PDF, 5,977kB)

This talk shows how amortised analysis can be automated using type inference. Building on an operational semantics for Hume and extending previous work by Hoffmann and Jost, we develop an associated cost model and thus derive an automatic analysis for worst-case behaviours in terms of e.g. memory usage and execution time. The analysis is compositional and scalable. Using e.g. dependent types, resource information can be associated with language constructs that can inform and direct the resource analysis.

Machine Guided Energy Efficient Compilation
Simon Hollis, University of Bristol

Presentation: EACO W7 Simon Hollis (MAGEEC) (PDF, 3,757kB)

The MAGEEC project at the University of Bristol has successfully applied machine learning techniques to popular compilers in order to automatically improve the energy efficiency of embedded code.

In this talk, I will discuss the flow, how real energy measurement and machine learning can help, and what can be learnt to improve future compiler design.

Declarative Machine Learning for Energy Efficient Compilation
Kerstin Eder, University of Bristol

Presentation: EACO W7 Craig Blackmore (PDF, 409kB)

This presentation shows early results of applying Inductive Logic Programming (ILP), a declarative machine learning technique, to learn general rules that relate effective compiler flags to specific program features, with the aim to minimize the energy consumption of code. An advantage of declarative techniques is that the rules inferred are human readable. The ILP prototype developed in the context of an initial case study outperforms the state of the art in over half of the benchmarks. We aim to further develop this approach to take full advantage of the fact that ILP can exploit the inherent relational structure of code.

This is joint work with Craig Blackmore and Oliver Ray.