@unpublished{upm52114,
           title = {A multi-language and multi-platform framework for resource consumption analysis and its application to energy-efficient software development},
          author = {Umer Liqat},
          school = {ETSI\_Informatica},
            year = {2018},
        abstract = {La reducci{\'o}n y el control del consumo de energ{\'i}a de las tecnolog{\'i}as de la informaci{\'o}n, as{\'i} como de su impacto medioambiental, se han convertido en todo un desaf{\'i}o a nivel mundial. Es un problema importante en sistemas que van desde peque{\~n}os dispositivos de Internet de las Cosas, sensores, relojes y tel{\'e}fonos inteligentes, dispositivos m{\'e}dicos portables o implantables, hasta grandes centros de c{\'a}lculo y sistemas inform{\'a}ticos de altas prestaciones. A pesar de los r{\'a}pidos avances en hardware eficiente en consumo de energ{\'i}a, incluyendo nuevas bater{\'i}as y tecnolog{\'i}as de recolecci{\'o}n de energ{\'i}a, es el software el que controla el hardware, por lo que se consiguen mayores ahorros de energ{\'i}a al desarrollar aplicaciones software que realicen una mejor gesti{\'o}n de las caracter{\'i}sticas de ahorro de energ{\'i}a y recursos proporcionados por el hardware. El ahorro de energ{\'i}a ser{\'a} potencialmente mucho mayor trabajando en los niveles de abstracci{\'o}n m{\'a}s altos en la pila del sistema. Por ello, existe un creciente inter{\'e}s en considerar la eficiencia energ{\'e}tica como un objetivo prioritario de dise{\~n}o de software, lo cual plantea importantes desaf{\'i}os de investigaci{\'o}n. Esta tesis aborda dichos desaf{\'i}os, proporcionando t{\'e}cnicas y herramientas para el desarrollo de software consciente del consumo de energ{\'i}a. En primer lugar, como t{\'e}cnica base fundamental, la tesis se centra en la estimaci{\'o}n de cotas inferiores y superiores de la energ{\'i}a consumida por las aplicaciones software. El enfoque propuesto realiza una combinaci{\'o}n de t{\'e}cnicas de an{\'a}lisis est{\'a}tico de programas con t{\'e}cnicas de modelado de plataformas hardware. Los modelos de energ{\'i}a se utilizan para expresar el efecto, en t{\'e}rminos del consumo de energ{\'i}a en el hardware, de la ejecuci{\'o}n de elementos software b{\'a}sicos, como por ejemplo, instrucciones ensamblador o bloques de bajo nivel, y hacen que el sistema desarrollado sea param{\'e}trico respecto a la plataforma de ejecuci{\'o}n. El an{\'a}lisis est{\'a}tico propaga dicha informaci{\'o}n (en tiempo de compilaci{\'o}n, sin ejecutar el programa con datos concretos, sino realizando una interpretaci{\'o}n abstracta del mismo) a trav{\'e}s de segmentos de c{\'o}digo, estructuras de control condicionales, bucles, recursiones, etc., para inferir el consumo de energ{\'i}a de todo el programa. Dicha informaci{\'o}n se obtiene en forma de funciones que dependen de los tama{\~n}os de datos de entrada de los programas y posiblemente de otros par{\'a}metros, como la frecuencia de reloj, voltaje, etc. El marco para la estimaci{\'o}n del consumo de recursos propuesto es muy general, multi-lenguaje y param{\'e}trico respecto a recursos y plataformas de ejecuci{\'o}n, y se especializa para la inferencia de funciones que calculan cotas del consumo de energ{\'i}a a dos niveles de abstracci{\'o}n, lenguaje ensamblador y c{\'o}digo intermedio (LLVM IR), las cuales se reflejan luego a nivel de c{\'o}digo fuente. Para ello la tesis desarrolla traducciones de estos dos niveles a una representaci{\'o}n intermedia (cl{\'a}usulas de Horn) en la que opera el an{\'a}lisis. Adem{\'a}s, realiza un estudio experimental de dicho an{\'a}lisis, que proporciona informaci{\'o}n {\'u}til sobre el compromiso existente entre la precisi{\'o}n de las estimaciones frente a la analizabilidad a estos dos niveles, y concluye que el an{\'a}lisis a nivel LLVM IR es un buen compromiso. Para recursos que son independientes del hardware (como los pasos de ejecuci{\'o}n), el an{\'a}lisis estima cotas inferiores y superiores seguras. Para que las cotas sean tambi{\'e}n seguras para recursos dependientes del hardware, como la energ{\'i}a, se necesita incorporar modelos de energ{\'i}a que proporcionen tambi{\'e}n cotas seguras. En este sentido, la tesis propone un enfoque de modelado novedoso que consiste en dividir un programa en bloques b{\'a}sicos (sin ramificaciones), estableciendo el consumo de energ{\'i}a m{\'a}ximo (o m{\'i}nimo) para cada bloque usando un algoritmo evolutivo. Dicho modelo a nivel de bloques es utilizado por el an{\'a}lisis est{\'a}tico para inferir cotas del consumo de energ{\'i}a m{\'a}s ajustadas, que son pr{\'a}cticas para su apliaci{\'o}n en verificaci{\'o}n y optimizaci{\'o}n del consumo de energ{\'i}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{\'o}n. Los resultados experimentales muestran que, en la pr{\'a}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{\'i}a. Tradicionalmente, los an{\'a}lisis de recursos est{\'a}ticos estiman el uso total de los recursos consumidos por una llamada a un programa. En esta tesis se desarrolla tambi{\'e}n un novedoso an{\'a}lisis de recursos cuyo objetivo es, en cambio, el perfilado est{\'a}tico del coste acumulado, es decir, la estimaci{\'o}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{\'a}lisis de recursos tradicionales son param{\'e}tricos, en el sentido de que los resultados pueden ser funciones que dependen de los tama{\~n}os de datos de entrada. El perfilado est{\'a}tico aqu{\'i} propuesto tambi{\'e}n es param{\'e}trico, y las estimaciones de coste acumulado dependen de los tama{\~n}os de datos de entrada del programa principal. El m{\'e}todo se basa en el concepto de centros de coste y una transformaci{\'o}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{\'a}lisis de tama{\~n}os y se inferen los costes acumulados en funci{\'o}n de los tama{\~n}os de datos de entrada del programa principal. La informaci{\'o}n de coste acumulado es mucho m{\'a}s {\'u}til para el desarrollador de software que el coste est{\'a}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{\'o}n de una llamada al mismo. La t{\'e}cnica propuesta tambi{\'e}n se ha implementado e integrado en el sistema CiaoPP, y se ha realizado una evaluaci{\'o}n experimental. Finalmente, utilizando las estimaciones del consumo de energ{\'i}a obtenidas mediante las t{\'e}cnicas mencionadas se pueden realizar diferentes tipos de optimizaciones, tanto est{\'a}ticas como din{\'a}micas, en los correspondientes niveles de la pila del sistema. La tesis explora algunas de ellas, en particular, propone nuevos m{\'e}todos basados en algoritmos evolutivos para mejorar la planificaci{\'o}n y asignaci{\'o}n de tareas a procesadores en arquitecturas multi-n{\'u}cleo que ofrecen la posibilidad de modificar la frecuencia de reloj y el voltaje (DVFS). Dichos m{\'e}todos son capaces de gestionar la migraci{\'o}n y apropiaci{\'o}n de tareas. Para las aplicaciones que permiten ciertos niveles de variabilidad en la precisi{\'o}n de sus resultados, la tesis tambi{\'e}n propone algoritmos que explotan el compromiso entre la precisi{\'o}n y el consumo de energ{\'i}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.},
             url = {https://oa.upm.es/52114/}
}