基于动态指令集的自适应处理器

1、基于动态指令集的自适应处理器指令集优化关键技术研究答辩人：答辩人： 薛薛 辉辉 导导 师：周学海师：周学海 教授教授 专专 业：计算机系统机构业：计算机系统机构嵌入式系统实验室嵌入式系统实验室2/30v背景介绍与研究目标v指令集扩展算法v总结与展望嵌入式系统实验室嵌入式系统实验室3/30提纲提纲v 指令集扩展算法 指令集扩展算法概述 自定义指令生成算法l 指令生成算法的问题定义l 遍历搜索的指令生成算法l 遗传进化的指令生成算法 自定义指令选择算法l 指令选择算法的问题定义l 空间搜索的指令选择算法l 关联启发的指令选择算法l 进化补全算法v 总结与展望嵌入式系统实验室嵌入式系统实验室4/30

2、ASAP的提出的提出v专用指令集处理器（专用指令集处理器（ASIP）应用中的问题）应用中的问题设计代价高设计代价高l工具链开发工具链开发 、验证代价高、验证代价高无法满足动态变化的处理需求无法满足动态变化的处理需求l环境的变化环境的变化移动计算系统移动计算系统l用户需求的变化用户需求的变化可穿戴计算系统、网络处理器可穿戴计算系统、网络处理器v基于动态指令集的自适应处理器基于动态指令集的自适应处理器ASAP（Application Specific Adaptive Processor ）自动适应环境和需求的变化自动适应环境和需求的变化降低设计代价降低设计代价嵌入式系统实验室嵌入式系统实验室5/

3、30v 嵌入式通用处理器嵌入式通用处理器v 自适应控制器自适应控制器v 可重构阵列可重构阵列嵌入式系统实验室嵌入式系统实验室6/30ASAP自适应的关键技术自适应的关键技术v自适应控制器自适应控制器-自适应的核心自适应的核心动态剖析器动态剖析器l应用特点应用特点l运行时变化运行时变化指令集优化技术指令集优化技术l指令集扩展指令集扩展可重构控制器可重构控制器l扩展指令硬化扩展指令硬化嵌入式系统实验室嵌入式系统实验室7/30研究目标研究目标v 指令集优化技术指令集优化技术 地位地位l 自适应处理的决策者自适应处理的决策者l 关系自适应处理性能关系自适应处理性能 实现实现l 扩展指令集扩展指令集 问

4、题问题l 如何快速的找到最适合扩展的指令簇？如何快速的找到最适合扩展的指令簇？研究目标研究目标v 指令集扩展算法研究指令集扩展算法研究 快速产生可扩展指令快速产生可扩展指令 快速选取性能最优的扩展指令快速选取性能最优的扩展指令嵌入式系统实验室嵌入式系统实验室8/30提纲v 背景介绍与研究目标 ASAP介绍 自适应处理器架构 研究目标v 指令集扩展算法 指令集扩展算法概述 自定义指令生成算法l 指令生成算法的问题定义l 遍历搜索的指令生成算法l 遗传进化的指令生成算法 自定义指令选择算法l 指令选择算法的问题定义l 空间搜索的指令选择算法l 关联启发的指令选择算法l 进化补全算法v 总结与展望嵌

5、入式系统实验室嵌入式系统实验室9/30v 指令集扩展算法指令集扩展算法从应用程从应用程序的数据流图中找到：序的数据流图中找到： 满足约束条件满足约束条件 提升系统性能提升系统性能 指令簇指令簇v 指令扩展算法的两个子问题指令扩展算法的两个子问题 自定义指令生成自定义指令生成l 找出所有符合约束条件的候选自找出所有符合约束条件的候选自定义指令定义指令 自定义指令选择自定义指令选择l 从候选自定义指令集合中选取使从候选自定义指令集合中选取使系统性能提升最优的子集系统性能提升最优的子集嵌入式系统实验室嵌入式系统实验室10/30提纲提纲v 背景介绍与研究内容 ASAP介绍 自适应处理器架构 研究内容v

6、 指令集扩展技术 指令集扩展概述 自定义指令生成算法l 指令生成算法的问题定义l 遍历搜索的指令生成算法l 遗传进化的指令生成算法 自定义指令选择算法l 指令选择算法的问题定义l 空间搜索的指令选择算法l 关联启发的指令选择算法l 进化补全算法v 总结与展望嵌入式系统实验室嵌入式系统实验室11/30指令生成算法的问题定义指令生成算法的问题定义v 在程序的数据流图在程序的数据流图(DFG)中查找满足以下中查找满足以下约束条件指令集合：约束条件指令集合： 输入输出约束输入输出约束 指令的最大输入、输出操作数指令的最大输入、输出操作数 闭包约束闭包约束 保证执行原子性保证执行原子性 不存在无效指令不

7、存在无效指令 访存、访存、IO指令指令描述描述ASAP应用应用枚举枚举检查所有可能组合检查所有可能组合空间爆炸空间爆炸匹配匹配基于预定义模版匹配基于预定义模版匹配受限于模板库受限于模板库启发启发基于计算权值改进产生指令基于计算权值改进产生指令计算量大计算量大2003-Automatic application specific instruction-set extensions under microarchitectural constraintsDAC2001-instruction generation for hybrid reconfigurable systemsICCAD200

8、5-ISEGEN:Generation of high-quality instruction set extension by iterative improvementDATE典型算法典型算法嵌入式系统实验室嵌入式系统实验室12/30遍历搜索的指令生成算法遍历搜索的指令生成算法v 枚举枚举DFG中指令结点的组合，输出符合约束的组合中指令结点的组合，输出符合约束的组合 一层对应数据流图中的一个结点一层对应数据流图中的一个结点 左右分支表示当前层结点是否选入当前生成指令集合左右分支表示当前层结点是否选入当前生成指令集合 从树根到树叶的路径代表一种指令结点的组合从树根到树叶的路径代表一种指令结点

9、的组合 递归遍历二叉树递归遍历二叉树2003-Automatic application specific instruction-set extensions under microarchitectural constraintsDAC嵌入式系统实验室嵌入式系统实验室13/30递归遍历不足递归遍历不足v 堆栈操作耗费过大堆栈操作耗费过大v 堆栈回溯多次出现重复堆栈回溯多次出现重复输出示例：输出示例：No No 输出的顺序输出的顺序 Result Result 生成指令生成指令嵌入式系统实验室嵌入式系统实验室14/30迭代遍历搜索迭代遍历搜索v 迭代遍历迭代遍历 去除堆栈操作去除堆栈操作 删

10、除重复状态删除重复状态v 算法评述算法评述 相对递归算法相对递归算法l 性能有所提高，但改性能有所提高，但改进有限进有限 算法搜索空间算法搜索空间l 空间爆炸空间爆炸 仅适合小规模应用仅适合小规模应用 解决思路解决思路引入引入遗传算法遗传算法尝试解尝试解决大子图问题决大子图问题n2嵌入式系统实验室嵌入式系统实验室15/30遗传算法和划分合并算法遗传算法和划分合并算法v 遗传算法遗传算法 染色体编码染色体编码 染色体位长染色体位长=子图有效结点数子图有效结点数 适应度评价适应度评价l 指令加速比指令加速比l 输入输出输入输出l 占用资源占用资源 终止条件终止条件 N代不超过最高评价代不超过最高评

11、价 只适合小规模应用只适合小规模应用v 划分合并算法划分合并算法 算法流程算法流程l 划分连通域划分连通域l 枚举连通子图枚举连通子图l 合并连通子图合并连通子图局部解局部解 全局解全局解 时间复杂度时间复杂度 l 适合大子图，满足适合大子图，满足ASAP应用的要求应用的要求 n2log2004-Scalable Custom Instructions Identification for Instruction Set Extensible ProcessorsCASES 缩减搜索空间缩减搜索空间嵌入式系统实验室嵌入式系统实验室16/30提纲提纲v 背景介绍与研究内容 ASAP介绍 自适应处

12、理器架构 研究内容v 指令集扩展技术 指令集扩展概述 自定义指令生成算法l 指令生成算法的问题定义l 遍历搜索的指令生成算法l 遗传进化的指令生成算法 自定义指令选择算法l 指令选择算法的问题定义l 空间搜索的指令选择算法l 关联启发的指令选择算法l 进化补全算法v 总结与展望嵌入式系统实验室嵌入式系统实验室17/30概念概念v自定义指令与自定义指令实例自定义指令与自定义指令实例v自定义实例互斥自定义实例互斥,321CCC指令集合6, 5,4, 38, 7,5, 44, 3, 23231222111ccccc实例集合1s2111 s覆盖约束嵌入式系统实验室嵌入式系统实验室18/30指令选择算法

13、的问题定义指令选择算法的问题定义v 选取候选指令集合的子集并符合以下条件：选取候选指令集合的子集并符合以下条件： 自定义指令数目约束自定义指令数目约束扩展空间有限扩展空间有限 面积约束面积约束硬件资源稀缺硬件资源稀缺 覆盖集约束覆盖集约束结果的正确性结果的正确性描述描述针对针对ASAP应用之不足应用之不足ILPILP整数线性规划整数线性规划计算复杂度高计算复杂度高启发启发特权级评价，迭代特权级评价，迭代已选待选集合的关联已选待选集合的关联贪心贪心面积约束，迭代面积约束，迭代忽略指令实例的影响忽略指令实例的影响典型算法典型算法2004-Characterizing Embedded Applic

14、ations for Instruction Set Extensible ProcessorsDAC2008-Study on Differential Evolution and Greedy Strategy Based Custom Instruction Selection Algorithms2003-Rapid configuration and instruction selection for an asip: A case studyDATE嵌入式系统实验室嵌入式系统实验室19/30空间搜索的指令选择算法空间搜索的指令选择算法v 空间搜索指令选择空间搜索指令选择 基于指令空

15、间基于指令空间 树形递归搜索树形递归搜索 类似遍历生成算法类似遍历生成算法v 优点优点 可得到最优解可得到最优解 满足小规模应用满足小规模应用v 缺点缺点 时间复杂度差时间复杂度差 不满足大规模应用需求不满足大规模应用需求 解决？解决？ 贪心、启发、遗传进化贪心、启发、遗传进化)(mnCO嵌入式系统实验室嵌入式系统实验室20/30GreedyHeur指令选择算法指令选择算法v GreedyHeur算法算法 左图为算法框架左图为算法框架v GreedyHeur的不足的不足 启发函数的局限启发函数的局限2008-Study on Differential Evolution and Greedy

16、Strategy Based Custom Instruction Selection Algorithms嵌入式系统实验室嵌入式系统实验室21/30v 关联启发算法流程 计算权值、初始化记录信息 选取指令 删除互斥实例 更新记录信息嵌入式系统实验室嵌入式系统实验室22/30嵌入式系统实验室嵌入式系统实验室23/30实验结果对比实验结果对比v 符号说明 M指令选取约束 P选取结果加速比l 单位1e+07 Time算法运行时间v RelevanceHeur 10%的执行时间嵌入式系统实验室嵌入式系统实验室24/30差分进化选择算法（ISDE）v ISDE算法算法 离散差分产生子代离散差分产生子代

17、 群体搜索群体搜索 贪心策略评价贪心策略评价v 不足不足 无法选取足够指令无法选取足够指令嵌入式系统实验室嵌入式系统实验室25/30进化补全算法v 补全方式补全方式 贪心、贪心、启发选择启发选择9%，1.5%10%，1%符号说明符号说明M指令选取约束指令选取约束P选取结果加速选取结果加速比单位比单位1e+07Time算法运行算法运行时间时间嵌入式系统实验室嵌入式系统实验室26/30提纲提纲v 背景介绍与研究目标 ASAP介绍 自适应处理器架构 工作内容v 指令集扩展算法 指令集扩展概述 自定义指令生成算法l 指令生成算法的问题定义l 遍历搜索的指令生成算法l 遗传进化的指令生成算法 自定义指令

18、选择算法l 指令选择算法的问题定义l 空间搜索的指令选择算法l 关联启发的指令选择算法l 进化补全算法v 总结与展望嵌入式系统实验室嵌入式系统实验室27/30总结总结v 工作内容工作内容 面向面向ASAP的自定义指令生成算法、指令选择算法的自定义指令生成算法、指令选择算法1. 改进遍历指令生成算法改进遍历指令生成算法2. 遗传进化的指令生成算法遗传进化的指令生成算法3. 空间搜索的指令选择算法空间搜索的指令选择算法4. 关联启发的指令选择算法关联启发的指令选择算法5. 进化补全算法进化补全算法嵌入式系统实验室嵌入式系统实验室28/30展望展望v下一步工作下一步工作指令生成算法指令生成算法 进一步深入进一步深入l基于遗传进化的指令生成算法基于遗传进化的指令生成算法 遗传算子遗传算子 引入辅助操作引入辅助操作指令选择算法指令选择算法 改进改进l空间搜索的选择算法空间搜索的选择算法 减少搜索空间减少搜索空间 启发？启发？嵌入式系统实验室嵌