A multi-language and multi-platform framework for resource consumption analysis and its application to energy-efficient software development

La reducción y el control del consumo de energía de las tecnologías de la información, así como de su impacto medioambiental, se han convertido en todo un desafío a nivel mundial. Es un problema importante en sistemas que van desde pequeños dispositivos de Internet de las Cosas, sensores, relojes y teléfonos inteligentes, dispositivos médicos portables o implantables, hasta grandes centros de cálculo y sistemas informáticos de altas prestaciones. A pesar de los rápidos avances en hardware eficiente en consumo de energía, incluyendo nuevas baterías y tecnologías de recolección de energía, es el software el que controla el hardware, por lo que se consiguen mayores ahorros de energía al desarrollar aplicaciones software que realicen una mejor gestión de las características de ahorro de energía y recursos proporcionados por el hardware. El ahorro de energía será potencialmente mucho mayor trabajando en los niveles de abstracción más altos en la pila del sistema. Por ello, existe un creciente interés en considerar la eficiencia energética como un objetivo prioritario de diseño de software, lo cual plantea importantes desafíos de investigación. Esta tesis aborda dichos desafíos, proporcionando técnicas y herramientas para el desarrollo de software consciente del consumo de energía. En primer lugar, como técnica base fundamental, la tesis se centra en la estimación de cotas inferiores y superiores de la energía consumida por las aplicaciones software. El enfoque propuesto realiza una combinación de técnicas de análisis estático de programas con técnicas de modelado de plataformas hardware. Los modelos de energía se utilizan para expresar el efecto, en términos del consumo de energía en el hardware, de la ejecución de elementos software básicos, como por ejemplo, instrucciones ensamblador o bloques de bajo nivel, y hacen que el sistema desarrollado sea paramétrico respecto a la plataforma de ejecución. El análisis estático propaga dicha información (en tiempo de compilación, sin ejecutar el programa con datos concretos, sino realizando una interpretación abstracta del mismo) a través de segmentos de código, estructuras de control condicionales, bucles, recursiones, etc., para inferir el consumo de energía de todo el programa. Dicha información se obtiene en forma de funciones que dependen de los tamaños de datos de entrada de los programas y posiblemente de otros parámetros, como la frecuencia de reloj, voltaje, etc. El marco para la estimación del consumo de recursos propuesto es muy general, multi-lenguaje y paramétrico respecto a recursos y plataformas de ejecución, y se especializa para la inferencia de funciones que calculan cotas del consumo de energía a dos niveles de abstracción, lenguaje ensamblador y código intermedio (LLVM IR), las cuales se reflejan luego a nivel de código fuente. Para ello la tesis desarrolla traducciones de estos dos niveles a una representación intermedia (cláusulas de Horn) en la que opera el análisis. Además, realiza un estudio experimental de dicho análisis, que proporciona información útil sobre el compromiso existente entre la precisión de las estimaciones frente a la analizabilidad a estos dos niveles, y concluye que el análisis a nivel LLVM IR es un buen compromiso. Para recursos que son independientes del hardware (como los pasos de ejecución), el análisis estima cotas inferiores y superiores seguras. Para que las cotas sean también seguras para recursos dependientes del hardware, como la energía, se necesita incorporar modelos de energía que proporcionen también cotas seguras. En este sentido, la tesis propone un enfoque de modelado novedoso que consiste en dividir un programa en bloques básicos (sin ramificaciones), estableciendo el consumo de energía máximo (o mínimo) para cada bloque usando un algoritmo evolutivo. Dicho modelo a nivel de bloques es utilizado por el análisis estático para inferir cotas del consumo de energía más ajustadas, que son prácticas para su apliación en verificación y optimización del consumo de energía. El enfoque ha sido evaluado con programas XC ejecutando en chips XMOS, pero es lo suficientemente general como para ser aplicado a cualquier microprocesador y lenguaje de programación. Los resultados experimentales muestran que, en la práctica, las cotas obtenidas por el prototipo desarrollado son precisas, a la vez que se mantienen en el lado seguro del consumo real de energía. Tradicionalmente, los análisis de recursos estáticos estiman el uso total de los recursos consumidos por una llamada a un programa. En esta tesis se desarrolla también un novedoso análisis de recursos cuyo objetivo es, en cambio, el perfilado estático del coste acumulado, es decir, la estimación, para partes seleccionadas del programa, denominadas centros de coste, de cotas del uso de recursos acumulados en cada uno de esos centros, que indican como se distribuye el coste total entre los mismos. Los análisis de recursos tradicionales son paramétricos, en el sentido de que los resultados pueden ser funciones que dependen de los tamaños de datos de entrada. El perfilado estático aquí propuesto también es paramétrico, y las estimaciones de coste acumulado dependen de los tamaños de datos de entrada del programa principal. El método se basa en el concepto de centros de coste y una transformación de programa que instrumenta el mismo para calcular el coste acumulado en cada uno de dichos centros. Al programa transformado se le aplica luego un análisis de tamaños y se inferen los costes acumulados en función de los tamaños de datos de entrada del programa principal. La información de coste acumulado es mucho más útil para el desarrollador de software que el coste estándar (tradicional), ya que permite identificar las partes de un programa que deben optimizarse en primer lugar, debido a su mayor impacto en el coste total de la ejecución de una llamada al mismo. La técnica propuesta también se ha implementado e integrado en el sistema CiaoPP, y se ha realizado una evaluación experimental. Finalmente, utilizando las estimaciones del consumo de energía obtenidas mediante las técnicas mencionadas se pueden realizar diferentes tipos de optimizaciones, tanto estáticas como dinámicas, en los correspondientes niveles de la pila del sistema. La tesis explora algunas de ellas, en particular, propone nuevos métodos basados en algoritmos evolutivos para mejorar la planificación y asignación de tareas a procesadores en arquitecturas multi-núcleo que ofrecen la posibilidad de modificar la frecuencia de reloj y el voltaje (DVFS). Dichos métodos son capaces de gestionar la migración y apropiación de tareas. Para las aplicaciones que permiten ciertos niveles de variabilidad en la precisión de sus resultados, la tesis también propone algoritmos que explotan el compromiso entre la precisión y el consumo de energía. ----------ABSTRACT---------- Reducing and controlling the energy consumption and the environmental impact of computing technologies have become a challenging problem worldwide. It is a significant issue in systems ranging from small Internet of Things devices, sensors, smart watches, smart phones and portable/implantable medical devices, to large data centers and high-performance computing systems. In spite of the recent rapid advances in energy-efficient hardware, including battery and energy harvesting technology, it is software that controls the hardware, so that the greatest savings are expected from developing software applications that perform a better management of the energy-saving features and resources provided by the hardware. For a given system, the potential for energy savings is likely to be much greater at the higher levels of abstraction in the system stack. Thus, promoting energy efficiency to a first class software design goal has become an important research challenge. This thesis addresses this challenge and provides tools and techniques for energy-aware software development. First, the thesis focuses on the development of techniques for the estimation of lower and upper bounds on the energy consumed by software applications, as well as the verification that such applications meet some energy budgets (given as specifications). Addressing a challenging objective, such techniques perform the estimations statically (i.e., at compile-time, without running the program with concrete data), and give such information in the form of functions on the input data sizes of programs (and possibly other parameters, such as clock frequency, voltage, etc.). The proposed approach performs a combination of techniques for static program analysis with techniques for modeling hardware platforms. The energy models are used to represent the effect, regarding energy consumption on the hardware, of running basic software elements (e.g., low-level assembly instructions or blocks). The static analysis propagates such information through code segments, conditionals, loops, recursions, etc., in order to infer the energy consumption of the whole program. One of the main contributions of the thesis is a multi-language general resource consumption analysis, and a specialization that infers both lower- and upper-bound energy functions at two levels, the instruction set architecture (ISA) and the intermediate code (LLVM IR) levels, and reflects it upwards to the higher source code level. To achieve this, we develop translations from both ISA and the LLVM IR to an intermediate representation (Horn clauses) on which the analysis operates on. Another contribution is the experimental assessment of such analysis, which provides insights into the trade-off of precision versus analyzability at these levels, and concludes that the LLVM IR level analysis is a good compromise. The analysis estimates safe lower and upper bounds on the use of resources that are independent from the hardware, such as execution steps. However, in order to infer safe bounds for hardware-dependent resources, such as energy, the analysis needs to be fed with energy models that provide safe bounds too. To this end, the thesis proposes a novel modeling approach that consists in dividing a program into basic (branchless) blocks, establishing the maximal (resp. minimal) energy consumption for each block using an evolutionary algorithm. Then, such block-level model is used by the static analysis to infer tight energy bounds that are practical for energy verification and optimization applications. The approach has been tested on XC programs running on XMOS chips, but it is general enough to be applied to any microprocessor and programming language. The experimental results show that the bounds obtained by our prototype tool can be tight while remaining on the safe side of actual energy consumption in practice. Traditional static resource analyses estimate the total resource usage of a call to a program, without executing it. The thesis presents a novel resource analysis whose aim is instead the static profiling of accumulated cost, i.e., to discover, for selected parts of the program (named cost centers), bounds on the resource usage accumulated in each of those parts, which express how the total cost of a call to the main program is distributed among the different cost centers. Traditional resource analyses are parametric in the sense that the results can be functions on input data sizes. Our static profiling is also parametric, i.e., our accumulated cost estimates are also parameterized by input data sizes of the main program. Our proposal is based on the concept of cost centers and a program transformation that instruments programs to compute accumulated costs for each cost center. A size analysis is then applied to the transformed program to infer functions that return bounds on accumulated costs depending on input data sizes of the main program. Accumulated cost information is much more useful to the software developer than the standard (traditional) resource usage functions, as it allows identifying the parts of a program that should be optimized first, because of their greater impact on the total cost of program executions. We also report on our implementation and integration of the proposed techniques in the CiaoPP system, and provide some experimental results. Finally, using the energy estimations provided by the aforementioned multi-level and multi-language energy consumption analysis, different types of optimisations, both static and dynamic, can be performed at different levels of the system stack. The thesis explores some of them and makes original contributions. In particular, the thesis proposes new methods based on evolutionary algorithms to improve energy-efficient task allocation and scheduling for DVFS-enabled multicore environments. These algorithms are able to deal with task migration and preemption. For applications that allow certain levels of variability in the accuracy of their results, the thesis also proposes algorithms to exploit the trade-off between accuracy and energy consumption