【作者】 陈勇；

【导师】 何炎祥；

【作者基本信息】 武汉大学 ， 计算机软件与理论， 2013， 博士

【摘要】 随着各种手持嵌入式智能设备的广泛普及和应用,人们的生活质量得到了大幅度提升,但由此而引起的资源和环境问题也越来越严重。以低能耗、低污染为主要目标的绿色需求已经成为现代社会可持续发展的必然选择。为降低嵌入式系统的能耗,提高嵌入式设备中各种资源的利用率,减少不必要的设备损耗,降低电子垃圾等有害物质的排放速度,一方面需要从材料的选取、设备的制造工艺等硬件部分进行改进,另一方面更需要对其上运行的软件进行相关优化,以充分发挥各种低能耗硬件设备的功效,适应不断增长的绿色需求。编译器作为软件开发和语言转换的工具,不但能够结合具体的嵌入式系统各部分硬件的特性进行针对性的优化,以指导生成的目标程序具有较高的绿色指标,而且能够利用其对源程序的分析结果,帮助程序员在程序开发过程中尽早的发现源程序中可能存在的能耗等绿色相关错误,提高软件的质量,减少其开发过程中因测试和调试而造成的资源和能源消耗。要系统化、自动化的对软件进行优化,必然离不开编译器的支持。但传统编译优化技术主要以性能优化为主,较少的考虑能耗、资源等绿色相关因素的影响。而性能优化与绿色优化并不总是一致的。通常情况下,性能优化是以资源和能源的消耗为代价的(如使用较多的寄存器资源,提高处理器运行速率),因而不能仅仅依靠传统编译优化来满足绿色优化的需求。其次,传统编译辅助信息主要集中于对程序语言语法错误以及可能的空指针、数组越界等功能性错误的检测。而能耗错误等绿色相关错误并非功能性错误,传统编译器给出的信息对于检测这类错误,提高软件开发效率以及质量几乎无能为力。为弥补传统编译器在绿色优化中的不足,本文将对嵌入式系统的绿色需求进行分析,通过在编译的过程中对嵌入式系统中的软件进行针对性优化,减少其运行时的能耗,均衡设备中各种资源的使用,提高系统整体资源的利用度,以满足日益增长的绿色需求。主要研究内容和创新点包括以下四个方面：1、结合了现有绿色需求的相关概念以及编译器本身的主要功能,给出了一种绿色编译器的定义,明确了该编译器优化的主要目标及其特点。同时,在该定义的指导下,对编译器指导的总体绿色评估模型进行了形式化描述,以有效的指导和评估绿色编译优化的顺利进行。2、为充分发挥时序推测处理器的低能耗特性,减少其因为流水线的数据向前推送机制而导致的时序错误,降低因此而消耗的无效能源,对形式化的绿色评估模型进行了具体化,构建了以数据依赖为主要指标的时序推测处理器的绿色评估指标,并在此基础上提出了一种基于图博弈模型的指令调度算法。通过提高数据之间“写后读”依赖的时钟周期,减少因此而产生的数据向前推送操作,获得时序推测处理器绿色指标的大幅度提升。此外,针对带有总线翻转编码的总线系统,分析了绿色评估模型中总线相关的绿色评估指标,并以此为标准,设计了一种反馈信息指导的绿色指令调度算法。利用程序执行的动态反馈信息,结合总线翻转编码的特点,充分减少相邻总线之间的翻转次数,均衡各根总线之间的翻转负载,以提高该系统的绿色指标。3、不同的数据分配方案对存储资源的使用、系统总的能源消耗等绿色相关指标将产生重要影响。为进一步提高系统的绿色指标,针对存储器层次存储单元的特点,分析了绿色评估模型中影响存储系统绿色指标的相关因子,设计了可交换类指令重排优化方法、基于扩展图着色的寄存器重分配优化方法和栈数据重分配方法,对编译器后端的寄存器以及栈数据进行重新调整,以获得较均衡的寄存器访问频度和栈存储单元访问频度,减少指令数据总线的动态翻转能耗。同时,为进一步提升系统的绿色指标,在前两种优化的基础上增加了迭代式优化,通过迭代优化使得寄存器使用更加均衡,相邻指令间的动态能耗更小。4、为提高软件开发的质量,减少能耗错误导致的无用能源损耗,总结了能耗相关错误的相关特征,并以该特征为基础,结合符号执行技术,设计了能耗错误检测和定位方法。该方法首先利用过程内分析,获得单个函数的符号执行信息,然后利用过程间分析对单个函数的符号执行信息进行全局分析,以获得较为准确的执行开销、锁变量匹配等相关信息,检测出对应的能耗相关错误。同时,符号执行记录了对应的分支路径信息,利用该信息不但能够较好的生成对应的测试用例,而且可以结合约束求解器快速定位错误位置,为开发出高绿色指标的软件提供保障。更多还原

【Abstract】 As the widely popularization and application of portable smart embedded devices, the quality of people’s life has been greatly improved. However, it makes the problems of resources and environments get worse. The green demands with the target of low energy and low pollution has become the inevitable choice for sustainable development of modern society.To reduce the energy consumption of embedded systems, improve the utilization of various resources, and reduce unnecessary equipment wear and tear for reducing e-waste and other harmful substances emission rates, on the one hand, we need to improve the materials and manufacturing of hardware devices. On the other hand, suitable software optimizations are also needed to maximize the effectiveness of various low-power hardware devices to meet the growing demand for green. As the software development and language translation tools, compiler can not only apply the suitable optimizations to guide the generated program has a high green indeicators by combining the specific embedded system hardware characteristics, but also help the programmer find the green-related errors such as energy bug as early as possible by using the analysis results form the program translation. It can improve the software quality and reduce resource and energy consumption by testing and debugging. To optimize the software systemically and automatically, compiler is one of best selection.However, tranditional compilers mainly focus on the performance of software and fewer consider the green factors such as energy and utilization of resource. Performance optimization and green optimization are not always the same. Performance optimization often needs to sacrifice the green targets that need more registers and higher processor’s voltage to increase the running speed. We cannot simply apply the traditional optimization methods to get the green factors improved. Secondly, the traditional auxiliary information supplied by compiler mainly concentrated on programming language syntax errors and other security related information such as null pointer, array bounds and other functional errors. The green related errors such as energy bug are often, not functional errors, the information given in the traditional compiler is useless for the detection of such errors, so the new detecting methods needed to further studied. To compensate for the drawback of traditional compiler in green optimization, the paper analyzes the green demands of embedded systems and optimizes the software in compiling processes to meet the growing demand for green such as getting low energy consumption, balancing the utilization of varied resources to increase the resources utilizations. The mainly contents and innovations are as follows.1. Combining with green related conception and the functional of compiler itself, it gives the definition of green compiler and illustrate the mainly objection of optimizations and features. Then, the formal green evaluation model is described according to the definition to effectively guide the green compilation optimization.2. To maximize the energy efficiency of timing speculative processor, reduce the timing errors caused by forwarding, a data dependency based green evaluation factor is constructed and a game model based instruction scheduling method is proposed. It formalizes the instruction scheduling to strategies selection in game model and increases the clock cycle of read-after-write dependency that can reduce the forwarding to improve the power efficiency of timing speculative processor. And for bus system by bus-invert coding, the invert information based green evaluation model is constructed and a feedback guided instruction scheduling method is proposed. It combines the characteristical of bus-invert coding and dynamic feedback profiling information to reduce the frequency of buses and also balance the inverts between buses which can improve the green indicator significantly.3. Different data assignment strategies significantly influence the utilization of storage resourses and also total energy. In order to further improve the green indicator of the system, memory hierarchy characteristics and green related factors of memory are analyzed. Based on the green evaluation model, the exchangeable class instruction reordering optimization method, extended graph coloring register reallocation optimization method and stack data reallocation method are designed to reorder the memory cells and registers in the backend of compiler. It can obtain a more balanced access frequency to registers and stack memory cell, reduce the dynamic power of instruction data bus invert. Meanwhile, to further improve green indicators of the system, the iterative optimization on the first two optimization method is applied which makes the utilization of registers get more balanced and dynamic energy get lower.4. In order to improve the green quality of software, reduce the energy consumption caused energy bug, the paper concludes the characteristics of energy bugs, and designs the energy bug detection and location methods combined with the symbolic execution technology. It firstly analyzes one single function to get its symbolic execution information. And then based on the single function symbol information, the interprocedural analysis is processed to obtain the global accurate execution overhead, lock variable matching and other related information to detect the corresponding energy bugs. Meanwhile, the symbolic execution records corresponding branch path information. It can not only be used to generate the corresponding test cases, and also to locate the position of errors combined with constraint solver which helps to develop the high green indicator software.更多还原