《面向嵌入式系统的绿色编译理论与方法研究》大部分内容是作者近年来的最新研究成果，具有较强的原创性，可作为高等院校和科研院所计算机科学与技术、软件工程、计算机应用技术等相关学科高年级本科生或研究生的教材，也可供软件优化等相关领域的研究人员借鉴。

编译器作为软件开发和构建的重要工具，在对软件进行系统化、结构化的优化方面具有无可比拟的优势。随着嵌入式系统的广泛普及和应用，其绿色指标已受到人们的广泛关注。而嵌入式系统是软硬件的结合体，其绿色指标不但受硬件工艺和技术的制约，更受到其上运行软件的影响。《面向嵌入式系统的绿色编译理论与方法研究》从能耗以及资源的均衡使用度这两个影响嵌入式系统绿色指标的问题出发，系统而全面地介绍绿色编译优化理论及其关键技术在嵌入式系统中的应用。

《信息科学技术学术著作丛书》序
前言
第1章 绪论1
1.1 研究背景1
1.1.1 绿色需求对现代嵌入式系统的重要性1
1.1.2 编译器对嵌入式软件绿色优化的重要性2
1.2 国内外研究现状3
1.2.1 面向总线系统的绿色优化技术研究3
1.2.2 面向存储系统的绿色优化技术研究8
1.2.3 面向处理器的绿色优化技术研究13
1.2.4 软件自动化测试及能耗调试相关研究16
1.3 组织结构18
1.4 本章小结18
参考文献18
第2章 绿色编译及评估模型26
2.1 绿色编译器定义26
2.2 绿色编译优化框架27
2.3 绿色评估模型31
2.3.1 绿色编译优化评估模型31
2.3.2 能耗错误检测评估模型32
2.4 本章小结33
参考文献33
第3章 面向嵌入式系统的指令调度方法35
3.1 面向时序推测处理器绿色指标的指令调度方法35
3.1.1 时序推测处理器简介35
3.1.2 图博弈模型38
3.1.3 编译器可控的时序推测处理器绿色评估指标39
3.1.4 基于图博弈模型的指令调度方法41
3.1.5 实验与结果分析55
3.2 面向总线翻转编码的绿色指令调度方法59
3.2.1 总线绿色评估模型59
3.2.2 总线翻转编码61
3.2.3 反馈信息指导的面向总线的绿色指令调度算法61
3.2.4 实验结果与分析65
3.3 本章小结68
参考文献69
第4章 多目标数据分配优化方法71
4.1 数据分配对系统绿色指标的影响71
4.2 绿色评估模型指导的多目标数据分配优化方法73
4.2.1 多目标数据分配总体优化框架73
4.2.2 可交换类指令操作数重排优化74
4.2.3 面向绿色需求的寄存器重分配方法76
4.2.4 面向存储系统绿色指标的栈数据分配方法85
4.2.5 实验结果与分析89
4.3 本章小结93
参考文献93
第5章 面向新型存储技术的绿色编译优化方法96
5.1 新型存储体系结构对绿色优化的影响96
5.1.1 PCM面临的挑战及解决方案99
5.1.2 STTRAM面临的挑战及解决方案100
5.2 面向混合便签式存储器的低能耗数据分配方法100
5.2.1 背景知识101
5.2.2 数据分配整数线性规划方法103
5.2.3 迭代图着色算法105
5.2.4 实验结果与分析111
5.3 面向易失性STTRAM缓存的低功耗编译优化方法114
5.3.1 缓存刷新机制简介115
5.3.2 数据分配方案同刷新频度的关系117
5.3.3 数据分配整数线性规划解决方案119
5.3.4 启发式分配方法122
5.3.5 实验结果与分析125
5.4 面向混合缓存的低功耗编译技术136
5.4.1 混合缓存简介137
5.4.2 混合缓存中迁移操作导致的负载138
5.4.3 基于缓存加锁的方法142
5.4.4 实验结果与分析145
5.5 本章小结150
参考文献150
第6章 基于符号执行的能耗错误检测及反例生成技术研究154
6.1 能耗错误简介154
6.2 符号执行技术155
6.3 基于符号执行技术的能耗错误分析方法157
6.3.1 能耗错误过程内分析157
6.3.2 能耗错误过程间分析164
6.4 应用举例165
6.5 实验评估171
6.5.1 实验构建171
6.5.2 结果分析172
6.6 本章小结172
参考文献173
第7章 绿色编译新型优化方法探究175
7.1 基于计算博弈论的分块多层次绿色编译优化175
7.2 基于总线翻转编码和多维度集成学习的绿色编译技术177
7.3 基于编译的多核环境下的并行程序绿色优化178
7.3.1 基于数据依赖的程序数据级并行性挖掘178
7.3.2 基于编译的异构多核环境下的低能耗多因素优化180
7.4 基于编译的动静态结合能耗错误检测和定位方法182
7.5 本章小结183
参考文献183
第8章 总结与展望185
后记——三言两语188

第1章绪论
第1章绪论
1.1研究背景
1.1.1绿色需求对现代嵌入式系统的重要性
在信息化、电子化高速发展的今天，各种便携式移动设备，如智能手机、平板电脑等被广泛应用于人们的日常生活和工作当中，极大地方便和丰富了人们的物质、文化生活。与此同时，电子产品的快速普及不但消耗了巨大的能源（仅个人计算机消耗的能源就占到全部电力的12%［1］），释放了大量的温室气体，而且废弃的电子垃圾中含有铅、铬、镉和汞等有毒物质，任意排放将严重污染土壤、水等环境资源，给人们的正常生活带来不可忽视的负面影响［2］。全球权威技术调查机构高德纳（Gartner）对IT业碳排放量的统计结果显示，IT业的二氧化碳排放量已经占全球碳排放总量的2%，比重等同于航空业［3］。而且巨大的能源消耗大大增加了IT产品本身的成本，2010年全球IT技术的花费已经达到3万亿美元。McKinsey报告指出，到2020年，手提电脑、智能手机、平板电脑等各种IT设备将成为温室气体排放量最大的源头之一［4］。在电子垃圾方面，联合国环境规划署（UNEP）［5］相关资料指出，2010年美国产生了300万吨电子垃圾，中国产生了230万吨的电子垃圾，全球每年将产生4000万吨的电子垃圾。据其预测，如果仍不采取相应保护手段，到2020年，各个国家在各个领域产生的电子垃圾将是现在的2～18倍。
进入21世纪以来，随着半导体技术的进步，移动智能终端设备得到了迅猛发展，其产品种类越来越多，功能越来越丰富，应用范围也越来越广泛，涉及人们工作、学习和生活的方方面面，同时人们对其使用的频度和数量也稳步增长。日本市场调研机构富士总研（FujiChimeraResearch）发表的研究报告称，2012年全球手机市场规模为15.9亿部，其中智能手机为7.4亿部，占46.6%。报告预计，2017年全球手机销量将达19.7亿部，与2012年相比增长24.1%；其中智能手机将达15.05亿部，增长103%［6］。就电子垃圾而言，由于手机、平板电脑、车载导航仪等便携式移动嵌入式设备数量多、损耗快，因此其造成的电子垃圾不但数量大，而且增速快。据高德纳预计，2020年我国仅废弃手机产生的电子垃圾将为2007年的7倍左右，而印度将达到2007年的18倍。2013年绿色计算所带来的市场份额有可能达到了48亿美元［7］。
1.1.2编译器对嵌入式软件绿色优化的重要性
针对上述严峻的能源环境问题，以低能耗、低污染、低成本和高功效为主要目标的绿色技术已经成为人们关注的焦点。从2008～2010年高德纳公布的技术发展趋势报告可以看出，绿色IT技术已经成为了十大IT关键技术之首［7］。在硬件设备和体系结构的设计上，各主要IT公司及计算机供应商均相应的采取了各种措施，以提高产品的绿色指标，减少对环境的污染。戴尔公司致力于其提出的零碳计划，以求最大化能量利用的效率。苹果公司将减少其新产品中有毒重金属的使用，同时增加对旧产品的回收，以减少电子垃圾及其对环境的影响［1］。三星、诺基亚、索尼等主要移动嵌入式设备制造商［8～10］均建立了自己的绿色产品研究实验室，研究新型产品，降低对环境的影响。然而，随着各种IT设备自动化智能化程度的不断提升，设备的能耗、功效不仅受具体的硬件设备材质的影响，而且也同其上运行的软件息息相关，相同功能的硬件模块采用不同的软件实现方式将产生不同的能耗以及资源的损耗。因此，如何从软件方面提高电子设备的绿色指标也是一个不容忽视的重要问题。
早期的嵌入式软件由于功能比较单一，逻辑相对简单，很多熟练的程序员能够凭借经验，使用较为低级的汇编语言进行编程获得较高质量的可执行程序。随着嵌入式处理器芯片、存储芯片等关键设备制作工艺和性能的飞速发展，嵌入式系统得到广泛普及，其功能越来越全面，运行的应用程序也越来越复杂，但其开发和调试的难度也随之增大。传统的用低级语言进行编程的方式已经很难满足需求，目前的大部分嵌入式程序均采用高级语言，如C、Java等进行编写，然后再利用交叉编译器将该程序转换为对应平台的可执行目标程序。因此，编译器作为软件开发和语言转换的工具，不但能够结合具体的嵌入式系统硬件设备信息进行针对性的绿色优化，指导最终的目标程序朝着绿色需求的方向生成，而且能够利用其在程序转换中对源程序的分析结果，提高错误检测的速度和定位精度，帮助程序员尽早发现和修正程序错误，减少软件开发过程中资源和能源的消耗。
然而，传统的编译优化技术主要是针对通用机设计的，利用这类编译器改良的嵌入式交叉编译器虽然能够生成性能较好的嵌入式程序，但相比于直接用低级语言编写的程序，在现有的绿色需求方面仍然有较大的优化空间。究其原因，主要有三个方面。首先，嵌入式系统由于受到体积、功耗等因素的影响，相对于通用机在体系结构上有很大的区别，其可用资源也少了很多，因而导致某些通用机上可以实现的优化在嵌入式系统中难以进行。其次，传统编译优化技术为简化编译器的实现，把代码生成分为指令选择、寄存器分配、指令调度三个独立的阶段。这三个阶段其实是彼此关联的，某个阶段的优化结果可能会影响其他阶段的优化效果。最后，由于传统编译优化技术主要以性能优化为主，较少的考虑能耗、资源等绿色相关因素的影响。性能优化与绿色优化并非完全一致，一般的性能优化是以资源和能源的消耗（如使用较多的寄存器资源，提高处理器运行速率等）为代价的，难以满足资源和体积受限的嵌入式系统的需求，更难以满足绿色计算的需求。因此，我们在后续章节将详细阐述几种面向嵌入式系统绿色需求的编译优化技术，以弥补现有编译优化技术的不足。
同时，绿色需求的不断增长也给编译调试带来了新的挑战。首先，随着人们对低能耗等绿色需求的不断增长，一类新的错误——能耗错误（ebug）已经逐步受到人们的重视。该类错误不同于传统的功能性错误，它不会引起程序运行结果出错，但会导致大量程序功能无关的能源消耗，而这些功能无关的能源消耗正是绿色需求要解决的问题。这种情况下程序的运行结果是正确的，因此传统以检测程序功能性错误为主要目标的编译调试信息已经无能为力，难以满足绿色编译的需求。其次，随着编程语言朝着自动化、智能化方法的不断改进，编程语言学习的难度越来越低，越来越多的业余人员参与到嵌入式程序特别是各种智能手机应用程序，如Android和iOS平台App的开发中来，而传统的编译调试需要大量的人机交互，程序员首先需要根据出错的测试用例估计出错的大概位置，然后通过断点、变量监视等编译器提供的调试接口逐步跟踪程序运行，以找出程序中的错误。但这些工作对于业余开发人员将是十分困难的工作，他们将花费十倍甚至更多的时间才能完成一个相同错误的检测，而更多的时间花费则意味着更多的资源与能源的消耗。因此，如果能根据能耗错误的特点，提供更为丰富和友好的编译调试和警告信息，对减少开发人员错误查找的时间，提高能耗错误发现的精度和速度，减少软件开发过程中资源和能源的消耗，提高开发过程的绿色程度将是十分必要的。我们将在第6章对这类绿色相关的能耗错误检测和定位方法进行详细讨论。
1.2国内外研究现状
为从软件方面提高计算机系统能源和资源使用的绿色指标，众多学者从组成计算机系统的三个主要部分，即总线、存储器以及处理器均进行了一定的研究，分别从各自的角度针对不同的体系结构对如何提高计算机系统的绿色指标进行分析和尝试，提出了一些新的面向绿色需求的优化及相关错误检测方法。以下我们分别从总线系统、存储系统、处理器和软件自动化测试及能耗调试这四个方面对相应的研究现状进行分析和介绍。
1.2.1面向总线系统的绿色优化技术研究
总线是电子设备各模块内部以及各模块之间信号和数据传输的通道，其工作性能直接影响到整个系统的效率及能耗，据文献［11］所述，芯片内部总线的动态能耗约占芯片总能耗的70%。随着半导体工艺逐步进入深亚微米甚至是纳米时代，芯片的体积越来越小，总线布局也越来越密集，其能耗所占比例将越来越大，因此总线的能耗、工作的稳定性及可靠性对整个系统的影响愈发重要，要实现绿色计算机系统，有必要对总线传输进行对应的优化处理。
根据总线上传输的数据类型，总线可以分为数据总线、地址总线和控制总线。数据总线主要传输的是各种通信数据，包括各种存储器（如指令存储器、数据存储器等）存储的数据。地址总线主要传输地址数据，包括指令地址以及数据地址等。控制总线主要传输的是控制信息，以控制相关部件的工作状态。无论哪种类型的总线，其能耗及工作的可靠性和稳定性主要受两方面因素的影响，即单根总线本身的影响以及并行传输的相邻总线之间（总线串扰）的影响。
1.单根总线本身的优化
针对于单根总线本身，主要以CMOS电路的动态能耗模型式（1.1）为基础［12，13］，即
Edyn=αCfV2ddt（1.1）
其中，α是翻转因子，表示该总线由0变为1或者由1变为0的频率；C是负载电容；f和Vdd分别是工作频率和工作电压；t是工作时间。
由式(1.1)可以看出，在电压、频率和电容相同的情况下，α越小，总线的动态能耗也将越小，因此大部分针对单根总线本身的优化主要是根据不同总线类型传输数据的特点，通过减少总线翻转次数来达到减少总线能耗的目的。
减少总线翻转次数的主要方法之一是编码技术。例如，Stan和Burleson［14］提出翻转编码，Lv等［15］提出基于字典查找的总线编码，Suresh等［16］提出VALVE和TUBE编码，Benini等［17］提出固定步长增长的T0编码，Mehta等［18］及Guo等［19］提出相邻数据海明距离最短的格雷编码。总线编码的基本思想是对待传输的数据在传输前通过编码电路进行编码，使相邻传输的数据引起的总线翻转次数尽可能少。然后在传输接收端利用解码模块对编码后的数据进行解码，以保证传输数据的正确性。
由于采用硬件编码的方法或者需要增加额外的编码以及解码电路，或者需要采用定制的模块结构，这些增加的硬件设备不但需要额外的能耗开销，而且相对于越来越小的芯片尺寸，其体积开销也将影响到整个系统的设计难度。此外，定制的模块结构，如文献［19］中采用格雷编码的内存地址将影响该设备的适用范围。总线数据的传输与通信，主要是由其上运行的软件控制的，不少研究者开始从软件方面考虑如何减少总线翻转次数的问题。编译器作为软件生成的主要手段也成为他们选择的主要工具。
目前基于编译技术减少总线翻转次数的方法主要是通过指令调度来减少相邻指令访问时代码段数据总线之间的翻转次数。Parikh等［20］总结了各种低能耗指令调度算法，并通过与性能优先指令调度算法进行的对比，指出性能最佳的指令调度序列并不一定是能耗最低的调度序列。LEE等［21］针对VLIW体系结构，提出水平调度和垂直调度两种调度方法来减少总线翻转次数，达到降低总线能耗的目的。Shao等［22］证明低能耗指令调度问题是NP完全问题，并在VLIW体系结构中针对总线翻转次数和调度长度，提出三种启发式调度算法，以尽可能获得较低的功耗。最近，Chabini和Wolf针对汇编级基本块内的指令调度，将最小化基本块内总线翻转次数的指令调度问题转化为一个整数线性规划（integerlinearprogramming，ILP）问题。同时，由于该问题是一个NP完全问题，使用整数线性规划求解需要大量的时间开销，因此Chabini和Wolf［23］又设计了两种启发式调度算法，以求快速获得总线翻转次数较少的调度方案。
然而，这些基于编译减少总线翻转的方法主要是单纯从软件的角度出发，并未考虑底层的硬件结构。虽然硬件编码需要额外的电路，但有些编码和解码电路十分简单，开销很低，如01翻转编码，在体系结构中实现并不困难。因此，我们可以结合这些已经实现的编码技术，在编译优化的过程中采取适应该编码方案的优化方法，将有可能获得更好的优化效果。
除直接的动态能耗外，随着芯片体积的缩小，电子工艺已经进入深亚微米阶段，总线之间的布局越来越密集，因泄露电流而产生的能耗所占比例也越来越大，使每根总线本身的负载也将对系统总的能耗产生重要影响。如果某根总线的翻转频率远大于其他总线，