Titulo Estágio
On the energy efficiency of dynamic programming algorithms
Áreas de especialidade
Engenharia de Software
Local do Estágio
DEI-FCTUC
Enquadramento
Modern society has built its intensive development pace on top of the widespread use of energy resources. The problem is that the growing energy demands have significant side-effects such as global warming, but even more importantly that the world’s resources are simply not able to match such demands on the produc- tion side. This can be confirmed in recent Key world energy statistics, a report compiled by the International Energy Agency (IEA), and has raised awareness in multiple contexts, that recently include the community acknowledgement of the need for sustainable software development.
Energy as a resource is particularly relevant for small battery-dependent devices with computing capabilities, such as smartphones and sensors, as well as for large data centers.
The goal of this work is to study and to optimize the energy consumption of algorithms for discrete optimization problems, with particular emphasis on dynamic programming approaches. This is a relevant subject as dynamic programming approaches are often found in tools that run on smartphones, but that make use of remote features that are available through data-centers (e.g., GPS/Galileo-based routing applications).
Of particular interest is to develop algorithms that are not only fast and use few memory as possible but also consume a reduced amount of energy. There has been some evidence that an increase of computation time of an algorithm may not correspond to a proportional increase on energy consumption.
S. Roy et al [1] proposed an energy complexity model that takes into account the computation time and the number of parallel accesses to memory made by the algorithm. Some experimental analysis is performed in [2], which validates the theoretical model and provides guidelines to design energy-aware algorithms.
In this work, the goal is to follow the guidelines in [2] to design algorithms under this model and validate their performance using state of the art energy consumption measurement and estimation tools and frameworks. These include, but are not limited to, Intel’s Runtime Average Power Limit [3] and the Trepn Profiler [4].
The algorithms to be tested are based on dynamic programming paradigm.
References
[1] Swapnoneel Roy, Atri Rudra, Akshat Verma, An energy complexity model for algorithms, Proceedings of the 4th conference on Innovations in Theoretical Computer Science,283-304, ACM, 2013
[2] Swapnoneel Roy, Atri Rudra, Akshat Verma, Energy Aware Algorithmic Engineering, IEEE 22nd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, 321-330, IEEE, 2014 [3] M. Dimitrov, C. Strickland, S.-W. Kim, K. Kumar, and K. Doshi, “Intel power governor,” https://software.intel.com/en-us/ articles/intel-power-governor [4] Qualcomm, Trepn Profiler. https://developer.qualcomm.com/trepnprofiler.
Objetivo
The interested candidate will explore otimization guidelines that are available in the literature to build an experimental setting to compare standard algorithm implementations against their optimized versions. In this comparison, we are not only interested in measuring runtime performance, but mainly energy efficiency.
As an essential result of this work, it is anticipated that the candidate is able to document the conditions upon which (runtime) optimizations are alig- ned with, or against, energy consumption concerns. The goal is that such docu- mentation can benefit and assist software developers when writing source code with energy efficiency non-functional requirements.
The main goals to achieve within this project are:
- to study and critically analyse the state of the art in the dynamic program- ming paradigm and in measuring and analyzing the energy efficiency of source code;
- to devise and implement a framework for comparing the (energy included) efficiency of different versions of dynamic programming algorithms;
- to use such a framework to propose a catalogue of good/bad program refactorings and/or editions;
- to provide strategies for improving dynamic programming implementation patterns in terms of reducing energy consumption.
Plano de Trabalhos - Semestre 1
- Trimester 1: Study the literature on dynamic programming, and the tools and the frameworks that are available for measuring energy consumption.
- Trimester 2: Design a framework for comparing the efficiency of different versions of dynamic programming algorithms;
- Trimesters 1 and 2: Write an intermediate report.
Plano de Trabalhos - Semestre 2
- Trimester 3: Implement the designed framework; Implement a representative set of dynamic programming algorithms and their energy-optimized versions;
- Trimester 4: Run the set of implementations and extensively analyse the obtained results to provide strategies for reducing energy consumption. Thesis writing.
Condições
The eligible student will have at disposal all the necessary computational platforms, tools and devices.
He/she will work within a research team that is working on related issues.
Orientador
João Fernandes (jpf@dei.uc.pt,), Luís Paquete (paquete@dei.uc.pt)
jpf@dei.uc.pt 📩