编译期SPM管理方法及功耗模型研究

论文摘要

随着嵌入式技术的发展,嵌入式系统已经广泛应用于国防电子、数字家庭、工业自动化、汽车电子、医学科技、消费电子、无线通讯、电力系统等国民经济的主要行业。在高速发展过程中,对嵌入式系统的尺寸、工作时间、稳定性提出了更高的要求,而能耗问题是影响上述指标的主要瓶颈之一。为了解决嵌入式系统能耗不断增长的问题,出现了使用SPM （Scratchpad Memory）替代Cache的设计趋势。本文围绕这一主题,重点研究与降低存储子系统能耗和提高系统实时性能密切相关的编译期SPM管理方法与相关技术。论文的主要工作包括：（1）提出了一种基于电路实际活跃度的体系结构级SPM动态功耗模型。现有功耗模型仅提供SPM的平均访问功耗值,不能反映程序实际输入输出值以及SPM内容布局对电路动态功耗的影响,限制了降低SPM操作能耗的优化效果。针对该问题,本文通过从性能模拟器获取程序运行时的电路翻转情况,计算电路实际活跃度值,提出了一种基于电路实际活跃度的体系结构级SPM动态功耗模型。该模型有效地反映了电路功耗随电路活跃度变化的特征,有助于指导编译器通过采取合适的优化技术降低程序运行时电路活跃度来减少电路功耗,提高对SPM的功耗优化效果。实验结果表明,仅通过改变地址编码方式来降低SPM地址解码器电路活跃度的方法,即可将部分程序运行时功耗降低9%左右。（2）在低功耗动态SPM管理方法研究中,提出了降低程序运行时存储需求的存储空间合并操作方法；提出了一种新的能有效降低SPM动态管理代价的优化置换候选集计算方法；提出了降低SPM电路活跃度的SPM布局优化方法。首先,针对如何降低程序运行时对存储空间需求的关键问题,提出了基于调用链关联分析的函数局部变量存储空间合并的方法。对于彼此间不存在调用链关联的函数内局部变量,执行共享全局存储单元空间合并操作,该方法能有效减少程序运行所需总的存储空间,其中部分程序经过优化后其所需的存储空间减小率高达69%,从而将单位存储空间的平均访问频度提高到原来的3倍。其次,针对已有避免SPM管理代码失效的方法会导致较高管理代价以及存在使用限制的问题,提出了一种新的基于节点执行序图的节点动态置换候选集计算方法。基于扩展流程图来生成程序节点执行序图,选取图中基本节点的入口和出口处两个位置作为SPM与外存置换操作的插入点,并按照节点在执行序图中的特征来计算其置换候选集。示例分析表明,该种结合对象生命周期以及执行路径上节点关联关系的候选集计算方法能有效减少运行时SPM与外存间的置换操作,而且不存在其他的使用限制问题。最后,根据不同存储对象在SPM中位置安排将影响其电路活跃度、进而影响SPM操作能耗的事实,提出了一种采用遗传算法进行SPM布局优化的方法。该方法通过优化存储对象在SPM中的位置可以有效降低程序运行时SPM的电路活跃度,从而提高能耗优化效果。实验结果显示,当SPM容量小于8KB时,本文在SPM低功耗管理中提出的合并方法和置换候选集计算方法,能有效改善现有管理方法在SPM容量较小时优化效果不佳的问题。已有能耗优化方法的功耗减少率仅为30%-40%,本文提出的方法其功耗减少率在此基础上提高了7%-20%,部分程序的功耗减少率可以达到70%以上；采用遗传算法来优化存储对象在SPM布局的方法,能进一步将功耗节省率提高6%左右,而且其优化效果总体上呈现出随SPM容量增加而愈明显的趋势。（3）提出了一种基于禁忌搜索、面向程序WCET值优化的SPM分配算法。嵌入式实时系统实时性能优化方法主要通过分析与优化程序最差情况执行路径的执行时间来提高系统的实时性。现有方法往往忽略了程序最差情况执行路径动态变化的情况,致使过度优化某些路径而影响了全局优化效果。针对上述问题,提出一种基于禁忌搜索策略的SPM分配算法。通过对“先计算程序WCET路径,再选择程序数据元素分配至SPM”的程序WCET值优化过程分析,并基于SPM分配结果集特征分析,构造了能反映变量分配至SPM时对降低程序WCET值的期望值的效用函数,利用该函数生成了分配算法中候选集的筛选方法。实验结果表明,结合合并函数部分局部数据变量共享存储空间的方法,相比现有分配算法,本文提出的分配算法能取得更好的优化效果,部分程序的WCET值优化效果可提高5%左右。（4）基于SUIF系统,实现了编译期SPM管理的原型系统。通过对SUIF （Stanford University Intermediate Format）系统的扩展,实现了编译期SPM管理优化的原型系统,该系统可与原系统集成,实现成果共享。

论文目录

• 摘要
• ABSTRACT
• 图表索引
• 术语中英对照表
• 第一章 绪论
• 1.1 课题研究的背景
• 1.2 论文的主要工作
• 1.3 论文的组织结构
• 第二章 编译期SPM管理的研究综述
• 2.1 SPM存储器
• 2.1.1 SPM与Cache的比较
• 2.1.2 采用SPM的片上存储系统结构
• 2.1.3 SPM的管理机制
• 2.2 SPM的功耗模型
• 2.2.1 功耗估计方法
• 2.2.2 SPM功耗模型
• 2.3 编译期SPM管理
• 2.3.1 编译期SPM管理方法
• 2.3.2 面向功耗优化的SPM管理
• 2.3.3 面向实时性能优化的SPM管理
• 2.4 本章小结
• 第三章 基于实际电路活跃度的SPM动态功耗模型
• 3.1 电路功耗
• 3.2 动态功耗模型
• 3.2.1 SPM部件结构
• 3.2.2 SPM各子部件功耗模型
• 3.2.3 功耗模型中a系统因子的设计
• 3.3 基于SimpleScalar的功耗模型实现
• 3.3.1 SimpleScalar简介
• 3.3.2 SimpleScalar结构
• 3.3.3 SPM部件扩展
• 3.4 模拟实验
• 3.4.1 实验环境设置
• 3.4.2 实验结果
• 3.4.3 模型用于优化应用示例
• 3.5 本章小结
• 第四章 编译期SPM低功耗管理方法
• 4.1 整体研究框架
• 4.2 变量识别
• 4.2.1 变量及操作类型分析
• 4.2.2 访问频度计算
• 4.3 一种基于调用链关联分析的函数局部变量存储空间合并方法
• 4.3.1 问题描述
• 4.3.2 生成调用图
• 4.3.3 函数间调用链关联
• 4.3.4 生成无调用链关联函数集
• 4.3.5 实现合并操作
• 4.4 一种基于节点执行序图的动态置换候选集计算方法
• 4.4.1 生成节点执行序图
• 4.4.2 执行序图的节点类型
• 4.4.3 候选集计算
• 4.4.4 示例分析
• 4.5 一种采用遗传算法进行布局优化的两阶段SPM分配方法
• 4.5.1 生成SPM分配方案
• 4.5.2 布局优化
• 4.5.3 分配方案的实现
• 4.6 模拟实验
• 4.6.1 基于SUIF平台的SPM分配管理系统
• 4.6.2 实验参数设置
• 4.6.3 实验结果及分析
• 4.7 本章小结
• 第五章 面向WCET值优化的SPM分配算法
• 5.1 面向WCET值优化的编译期SPM管理
• 5.1.1 WCET分析
• 5.1.2 SPM分配算法
• 5.2 基于禁忌搜索的SPM分配算法
• 5.2.1 优化效用函数
• 5.2.2 禁忌搜索
• 5.2.3 分配算法的实现
• 5.3 模拟实验
• 5.3.1 实验环境设置
• 5.3.2 参数分析
• 5.3.3 性能分析
• 5.4 本章小结
• 第六章 结论
• 6.1 工作总结
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读博士学位期间主要的研究成果