（计算机系统结构专业论文）基于动态指令集的自适应处理器的关键技术研究.pdf

摘要 摘要 专用指令集处理器( a s i p ) 既继承了通用处理器( g p p ) 的编程灵活、上市时问短 等优点，又集成了专用集成电路( a s i c ) 的功耗低、执行高效等特性，它的出现给 系统开发、设计等不同层次的人员带来了许多益处，因此越来越受到学术界和工 业界的欢迎和关注。但是，a s i p 的设计实现难度较大，其中难度最大的是快速 的工具链实现和验证。如何降低或避免a s l p 工具链开发所带来的额外开销，是 a s i p 应用中一个重要的问题。 新技术领域的兴起对程序与计算提出了更严格的要求，频繁变化的用户需求 使处理器执行的任务具有高度的动态性。传统的基于静态指令集设计的处理器已 经无法够满足这些应用的需求。如何设计新的架构来满足用户动态变化的需求， 是处理器设计中的重要问题。 本文针对上述两个问题，提出了种基于自适应a s i p 处理器( a p p i i c a t o n ， s p e c i f i ca d a p t i v ep r o c e s s o a s 的解决方案。a s a p 将a s i p 技术与可重构技术 结合到一起，让处理器能够动态的扩展自定义指令以适应变化的应用需求；同时 保证底层硬件的重构对上层软件透明，使自定义指令能够动态的映射而不改变对 应用程序的接口，以重用原有工具链，从而减少开发者负担并缩短研发周期。 本文开展的主要研究工作和创新特色如下： ( 1 ) 本文首先分析研究了目前a s i p 的典型开发流程，指出了其中的关键问 题，然后针对其中的问题来寻找相应的解决方案。首先，针对工具链中验证难的 问题，本文结合目前常见的基于体系结构描述语言( a d l ) 工具的设计流程，提出 了一种基于a d l 的指令集规范验证方法，协同验证了指令集规范，处理器模型 及工具链。然后，针对工具链开发负担大和用户需求动态变化犬的问题，本文提 出了一个基于动态指令集的自适应处理器架构a s a p 的方案，该方案能避免工具 链的问题并适应用户的动态需求。 ( 2 ) 本文详细分析研究了应用的特征和已有的剖析技术，结合a s a p 处理器 架构，设计并实现了个可配置的硬件剖析器c h p ，使之能够与微处理器低耦 合的工作，并在占用较少硬件资源的情况下，正确的找出目标应用的热点路径。 本文通过详尽的实验确定了剖析器各个部件中关键参数的设置。实验表明。对于 适合优化的应用，c h p 找出的热点路径的覆盖率都能够达到8 0 以上，为指令 集优化工作奠定了很好的基础。 ( 3 ) 本文详细分析了常见的指令集扩展技术，对其中的自定义指令生成和自 定义指令选择问题进行了深入的研究。首先结合a s a p 处理器架构给出了一个自 摘要 定义指令生成算法，通过数据流分析、指令簇标记、子图枚举、子图合并的方法， 找出了符合自定义扩展指令多约束要求的候选指令集合。实验数据表明，该算法 能够高效的找出目标应用的所有非平凡自定义指令集合。然后，针对目前自定义 指令选择问题中，常见的启发式算法无法找到最优解的情况，给出了一种贪心的 启发式算法g r e e d y h e u r 和一种结合贪心策略和差分进化思想的i s d e 算法。实 验表明，g r e e d y h e u r 算法能快速的选择比原有启发式算法更优的候选指令集合， 而i s d e 算法在指令数目约束较强时能在较低的时间复杂度下选出性能提升值远 远超过其他启发式算法的候选指令组合。 本文还分析研究了常见的可重构阵列架构。结合a s a p 处理器架构，描述了 一种实用的可重构阵列架构的设计与实现，然后针对这种架构，给出了一种利用 硬件表格来分析指令间寄存器的生产者消费者关系，从而实现自定义指令自动 映射的方法。 关键词：专用指令集处理器自适应处理器硬件剖析指令集扩展 插图目录 插图目录 图1 1设计复杂度与设计生产率的差距l 图1 2时空域计算模式4 图1 3可重构器件与处理器的耦合方式5 图1 4a l t e r a 的自定义指令架构6 图1 5处理器性质比较7 图1 6a s a p 概念图9 图2 1a s i p 的典型设计流程13 图2 2基于设计空间搜索的a s i p 设计过程1 4 图2 3基于a d l 的验证方法示例l8 图2 4 基于位域的中间表示示例l 1 9 图2 5基于位域的中间表示示例2 1 9 图2 6a s a p 处理器框架2 l 图2 7a s a p 关键技术2 3 图2 8d i s c 硬件架构2 6 图2 9r i s p p 的动态指令示意2 7 图2 10 s y s t e m o r p h 概念图2 7 图2 1 1透明指令集自定义架构2 8 图3 1c 语言层剖析示例3 0 图3 2边剖析缺点示例3 1 图3 3静态代码分支指令频率3 4 图3 。4分支指令频率比较3 5 图3 5 动态分支指令分析3 6 图3 6c h p 总体架构- 3 7 图3 7分支历史编码示例4 0 图3 8路径描述符4l 图3 9路径描述符的生成示意图4 1 图3 1 0不同路径长度的冲突次数4 4 图3 11不同路径长度的覆盖率4 5 图3 1 2 不同路径长度限制和循环扩展次数的覆盖率( c r c ) 4 5 v t i i 插图目录 图4 1 4 图4 。1 5 图4 1 6 图4 1 7 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图5 1 5 热点函数运行时间比例8 2 候选指令实例数目8 3 算法选择结果比较8 3 i s d e 结果分布图8 4 单上下文器件配置示意图8 8 多上下文器件配置示意图8 8 部分重构器件配置示意图8 9 细粒度可重构单元示例8 9 中粒度可重构单元示例9 0 粗粒度可重构单元示例9l 混合粒度可重构单元示例一9 2 基于l u t 的粗粒度重构9 3 模块间连接关系9 8 可重构部件架构9 8 可重构阵列上的执行示意图9 9 指令动态映射过程示例1 0 0 n p b e n c h 中逻辑操作的累计百分比1 0 1 n e t b e n c h 中逻辑操作的累计百分比1 0 2 配置生成器的一种方案1 0 3 x 表格目录 表格目录 表1 1a s i p 与g p p 、a s i c 的对比3 表3 1 n e t b e n c h 热点分支信息3 6 表3 2配置成n i o s 2 译码器对应的c a m 内容5 5 表3 3 m d 5 路径统计信息( 部分) 5 7 表4 1 可扩展指令信息( c r c 3 2 ) 7 3 表4 2基本操作参数7 7 表4 3候选指令参数7 7 表4 4i s d e 算法结果和时间分布8 5 表4 5算法效率比较8 6 表5 1不同深度阵列的累计百分比9 6 表5 2重构阵列中部件的利用率9 7 表5 _ 3自定义指令中部分指令比例1 0 2 x i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 力活年厂月堵日 第1 章绪论 1 1 引言 第1 章绪论 随着数字化技术的普及，人们的通讯、工作和娱乐方式都发生了革命性的变 化，这些变化，特别是针对语音、视频和信息流等的数字化处理，导致了不断增 长的带宽和计算能力需求【1 】，从而使得数字设备的设计复杂度不断增长。随着 设计复杂度的不断增长，传统设计方法的生产效率与设计复杂度的差距也越来越 大：如图1 1 所示，设计复杂度平均以每年6 8 的速度增长，而传统的设计方法 的生产效率增长速度仅仅是每年2 1 【2 】。传统的设计方法已经无法满足在设计 代价、上市时间、功耗和计算性能上的需求：基于通用处理器( g e n e r a lp u r p o s e p r o c e s s o r g p p ) 的设计往往无法满足快速增长的性能要求：而基于专用集成电路 ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) 的设计在灵活性和上市时间 ( t i m e t o m a r k e t ，t t m ) 上又很难跟上市场的变化 3 】。 p o t e r 吐i a ld e s i a nc o m p l e x j t ya n dd e s i g n e rp r o d u c t i v 耐 1 = ；黜比pf 翻笋 c 叫亡i j t y 矿。啪r t e 一 厂 一 簖一7 i 孑 么鬈铲_兹露 f 焉：憨 一 一， rnharn蚺卜西f -n岫卜 雾誉嚣嚣笤象雾雾客嚣g2 2 g 8 p_- ppr-p- 一 hn“ 图1 1设计复杂度与设计生产率的差距 x 皇 甾 u 3 屯 o - 氖 专用指令集处理器( a p p l i c a t i o ns p e c i f i ci n s t r u c t i o n s e tp r o c e s s o r ，a s i p ) 的出 现，在一定程度上满足了性能和灵活性的需求。但是，面向a s i p 的硬件设计和 相应的软件工具链的移植和验证等又引入了一次性开发成本( n o n r e c u r r i n g e n g i n e e r i n g ，n r e ) ，限制了其上市时间【4 】。 如何能够快速有效的提供一个面向特定应用的系统是个亟待解决的难题：即 不仅要求能够低代价的设计和实现可满足特定应用性能、功耗需求的处理器，而 且要求能够保持处理器的灵活性和扩展性，以满足t t m 的要求，并快速提供适 合开发者使用的相关工具链。 1 o嫠。扛霾的|fmc为k卜一望一 一 一 墓 。 一 m ， 1 1 1 0 ， o o 矗coia。o：inc眄-卜u口。一 第1 章绪论 1 1 1a s l p 专用指令集处理器( a s i p ) 是为一个或一组特定的应用而设计的专用处理器， 它通过挖掘应用的特性来满足性能、代价和功耗的需求。a s i p 是以应用为中心， 在传统的指令集体系结构( i n s t r u c t i o ns e t c h i t e c t u r e ，i s a ) 的基础上，通过添加专 用硬件、修改存储架构等定制手段，以满足适应具体应用对功能、成本、功耗、 可靠性等多方面要求的处理器。 a s i p 既继承了g p p 的编程灵活、上市时间短等优点，又集成了a s i c 的功 耗低、执行高效等特性，它的出现解决了a s i c 和g p p 固有的一些问题，给系统 开发、设计等不同层次的人员带来了许多益处。 对于应用开发人员，a s i p 为他们提供了更多的设计自由度。a s i p 能够通过 定制指令集来满足系统性能和代码尺寸等约束的需求，去除了传统处理器的计算 性能上界限制，使得应用开发人员能够有更多的设计自由度：开发人员能够选择 是通过牺牲可扩展性的传统优化方法或者使用定制指令集保持可扩展性的方法 来满足系统在性能和代码尺寸等约束上的需求。 对于处理器设计人员，a s i p 降低了开发的难度、风险和代价，缓解了1 v r m 的压力。a s i p 基于传统的指令集体系结构，设计人员可以在体系结构层次上展 开设计，避免了大量的低层设计工作；而且专门定制硬件等手段使之能够更容易 的满足诸如性能、功耗等一些重要的设计约束，从而降低了设计难度；同时a s i p 的设计保持了一定的灵活性，能够避免a s i c 设计的局限性：即当设计进入后期， 设计约束发生改变或设计错误会带来巨大的重设计开销。a s i p 设计难度、风险 的降低使设计者能够有更高的设计效率，满足1 v r m 要求的难度就降低了。 对于平台提供商，a s i p 降低了开发成本。a s i p 基于传统指令集的架构，通 过指令执行的方式来完成一些特定的功能，使得它仍具有一定的可编程性，只需 通过适当的编程，一个处理器可以被重新应用于多个相关的领域，避免了为所有 不同的应用设计开发专用处理器的开发成本。 表1 1 给出了a s i p 在性能、灵活性、功耗、设计代价等多个方面与g p p 和 a s i c 的比较【5 】。从表中可以看出，a s i p 是g p p 和a s l c 的一种折衷，填补了 g p p 和a s i c 间的多项空白，同时保证了系统性能和灵活性。 a s i p 的优点使得其具有良好的发展前景，被广泛应用于嵌入式系统中，特 别是音频处理、图像处理，网络处理和通讯领域。目前已有众多商用的a s l p 6 】， 如t b n s i l i c a 的x t e n s a ，b o p s 的m a n a r r a ma r c 的a r q a n g e n t ，i m p r o v 的j a z z 处理器和p h i l i p s 的r e a ld s p 等。 虽然a s i p 相比g p p 和a s i c 有着众多的优点，但是a s i p 的设计本身难度 仍然还是比较大的。硬件设汁方面，a s i p 的硬件设计代价相比a s l c 降低了不 2 第l 章绪论 少，但是其设计代价还是较高。软件设计方面，相比g p p 和a s i c ，a s i p 的软 件设计代价最大：为了保持a s i p 可编程性，a s i p 提供商需要在处理器应用之前 为之提供一套定制的工具链，并针对a s i p 体系结构对其优化；有时为了支持体 系结构设计，需要进行反复的迭代设计，对工具链的需求时间更是被提前到了设 计阶段。如何降低a s i p 工具链的设计和实现难度的问题，是a s i p 设计的一个 关键问题。1 | 表1 1a s l p 与g p p 、a s l c 的对比 g p pa s i pa s i c 性能低 古 非常高同 灵活性非常好好差 功耗大中等小 重用性非常好好差 市场非常大相对大 小 硬件设计代价无大非常大 软件设计代价 小大无 a s i p 通过为不同的应用提供自定义指令( c u s t o mi n s t r u c t i o n s ，c i ) 的方式 来提高处理性能如果指令集设计不符合实际应用的要求，那么性能将会大打折 扣另一方面，传统的a s i p 设计中指令评估往往集中于通过软件仿真的方法， 但是仿真时的输入很难和实际应用保持一致，而且仿真速度很慢 可重构计算给a s i p 这些设计问题带来了解决方案。不论是仿真验证还是实 际运行，可重构器件可以帮助a s i p 设计者获得一个较优的指令集，甚至能够做 到动态地切换指令集，为设计实现具有更高性能和灵活性的a s i p 提供了籼出 1 1 2 可重构计算 可重构计算( r e c o n f i g u r a b l ec o m p u t i n g ，r c ) 【7 ，8 ，9 ，1 0 ，1 1 】作为一种新的计 算形式，将传统通用微处理器的可编程性同硬件设计中基于空间并行的计算方式 结合起来，打破了传统的硬件和软件之间的划分界线，为嵌入式系统提供了拥有 更高计算能力的硬件平台。动态可重构器件 1 2 ，1 3 】及运行时重构技术 1 4 】的出现 则更模糊了这个界线，大大增加了系统的灵活性。 基于可重构硬件的计算平台，即可重构计算系统，其本质是利用可编程器件 可多次重复配置逻辑状态的特性，在运行时根据需要动态改变系统的电路结构， 从而使系统兼具灵活、简捷、硬件资源可复用、易于升级等多种优良性能。它既 3 第1 章绪论 能提供近似于专用集成电路的执行效率，又可以通过编程来改变其内部功能和互 连结构，针对不同计算任务进行不同的优化，拥有类似于通用微处理器的灵活性。 可重构系统( r e c o n f i g u r a b l es y s t e m ) 在高速数字滤波器、图像压缩、硬件演化 计算、定制计算( c u s t o mc o m p u t j n g ) 、嵌入式系统等方面有着广泛的应用前景。 随着微电子技术、计算机技术的发展，尤其是大规模高性能可编程器件的出现、 软硬件设计方法和设计工具上的改进，可重构计算技术逐渐成为国际上计算系统 研究中的一个新热点 1 5 】。 从本质而言，可重构计算是一种时空域上的计算模式，而传统的通用处理器 计算是时域上的计算模式，a s i c 则位于空域上。两种计算模式的差别如图1 2 所示 1 5 】。图1 2a ) 显示了传统处理器计算表达式y = a 十x 木x + b 木x + c 的过程。 处理器被简单的表示为由保存数据的寄存器和执行运算功能的a l u 部件组成。 该问题被分解为5 条指令，依次执行每条指令将得出最终结果。图1 2b ) 则是在 硬件上专门制作3 个乘法器，2 个加法器，并按照计算要求的通讯关系安排乘法 器和加法器之间的连接，能够在一个周期内完成所有的运算过程。静态的可重构 器件和a s i c 都属于这种空域计算。假设我们开始要求计算y = a 木x x + b 聿x + c ， 随后随着时间的推移要求计算y = ( a + x 幸x ) 木( b 奉x + c ) 等式。如果使用a s i c ，则 需要重新定制一个运算电路。而动态可重构计算允许在运行时改变硬件的功能， 匹配目标算法的动态特征，如图1 2c ) 所示。动态可重构计算的这种在时域上高 度灵活的特点，更能充分发挥硬件的高速计算的能力。 阿题i y t ，t j + 占+ c i i = x 1 2 ：一a - 1 2 ：f 2 + 眨：_ 1 2 _ y ：t 2 + x a y 问题2 、) ，。u 竹k + c ) y b c a ) 传统处璀器：时域计算b ) 静态r c ( 或a s i c ：守境计算c ) 动态r c ：时空域计算 图1 2 时空域计算模式 可重构计算的时空域计算模式，能够充分发挥硬件的并行高速计算的能力： 这一点和a s i p 利用专用指令来提高处理性能的思想是完全一致的。因此，可重 4 第1 章绪论 能和功耗方面一般无法达到嵌入式系统中特定应用的需求。 近年来，可重构计算技术，特别是动态可重构器件及运行时重构技术的发展， 使得基于可重构硬件的自适应技术在国外成为研究的趋势和热点【2 8 ，2 9 ，3 0 】。早 期的r a c e 【3 1 】由主机和可重构平台组成，它有效的提高了计算效率。最近的一 个专利则给出了一个将可重构技术应用于环境监测的自适应系统 3 2 】。还有在计 算部件级【3 3 】或系统级技术的相关研究。 如果能将自适应技术应用于可重构指令集处理器设计与实现，使处理器能够 根据用户需求或任务变化，动态地生成相应的自定义指令，并重构硬件，实现自 适应处理，则能够大大提升处理器的灵活性。我们称这种处理器为自适应处理器 ( a d a p t i v ep r o c e s s o r a p ) 。目前已有部分商用的自适应处理器：虽然编程难度较 大，a c m 【3 4 提供了3 层芯片架构，可以通过重组内部节点来进行自适应计算， 可以说是一款较典型的自适应处理器。s t e t c h 发布的s 6 0 0 0 系列芯片 3 5 1 ，基于 t e n s i i i 9 a 3 6 】公司的可扩展处理器x t e n s al x ，并针对多媒体应用提供了多个可编 程的加速单元，也实现了一定意义上的自适应处理。 如图1 5 所示，自适应处理器的出现，充分利用了动态可重构器件的时空域 计算特性结合自适应技术，使砌s p 能够针对特定应用优化，在对s p 的基础 上又提高了处理器的性能，使之能够同时满足性能、效率和灵活性的需求。 图1 5 处理器性质比较 自适应处理器结合了a s i p 、可重构技术、自适应技术，兼具了三者的优点。 研究自适应处理器设计及相关技术，对提高专用处理器的重用率，降低研发周期 和开销，降低开发人员难度都有着重要的意义；其中的相关技术也可以直接应用 于专用指令集处理器的设计中；同时，对促进可重构计算模式的应用也具有重要 的理论意义和使用价值。呵 7 第l 章绪论 2 面向特定应用的指令集优化方案 常见的指令集优化技术一般可以分为两步，首先是根据动态剖析的结果生成 可以被扩展的候选扩展指令集合，然后是从这些可以扩展的候选指令中选取一系 列的扩展指令，使处理器获得最大的性能提升。 拟解决的关键问题为： ( 1 ) 面向特定应用的自定义指令的生成问题： 令数据流图g ( y ，e ) 表示指令间的数据依赖关系，结点y 代表指令，边e 代 表数据依赖关系，其中g ( y ，e ) 是有向无环图。g ( 矿，e ) 中可以被包含在扩展指令 中的结点为有效结点y ，不能被包含的则为无效结点矽。令p 是当前处理的结点 集合。在尸中所有从p 外输入操作数的结点为输入结点集吖( 尸) ，所有从p 中向 p 外输出操作数的结点为输出结点集d 叮( 尸) 。微体系结构上对可扩展指令的输 入输出限制分别为：m 加和帆，。朋册 ，y ) 表示图g ( y ，e ) 中“到v 的路径。则 自定义指令生产问题即寻找合适的节点集合p ，使得： p ) i m 加 p 沂p ) i m 刚 v 缈，妒仨p v v ，尸，- 1 j v t 仨尸，s t 了朋册( ，j ，v t ) 了剐鹏( v ，) 目前常见的指令集扩展技术一般将访存操作和i o 指令等列为无效指令，但 是在许多特定的应用中，访存操作占用的比例是非常高的，去掉了访存指令之后 所获得的可扩展指令对性能的提升贡献较小。而且这样做所能获得的候选指令都 包含较少的指令数。如何处理好占比例较高的访存操作对扩展指令的影响，从而 可以得到包含更多指令的可扩展指令，将是自定义指令生成的关键问题之一。对 目前扩展指令生成算法的性能进行优化，使之能够适应于自适应处理器也是指令 生成需要研究的问题之一。 ( 2 ) 自定义侯选指令的选择问题： 候选指令选择问题可以抽象为以下优化问题：令自定义候选指令为c l 一，c 。， 它们在程序中出现的一个实例分别为c fl ，c j 每个实例的执行频率记为，。 令4 是自定义指令c ，的面积需求，只是选中c 所获得的性能提高( 将c ，使用硬件 实现，相比软件实现的性能提升，以时钟数的形式给出) ，彳为面积上限，m 为 自定义指令数目上限；二进制变量j ，表示是否选中自定义指令的实例( 如果在实 例c ，上选中自定义指令，则墨，为l ，否则为o ；s 为是否选中自定义指令c f ： 自定义指令的选择问题可以抽象为多约束的最优化问题： 1 0 第l 章绪论 nn m a x ：( j “e z 。j ) 置l = l v f ，s k l ， 肝 再= l ， ( s 4 ) 彳， k n c 。厶 h = j s ，= s oh i h ； - m ，= _ oi s i i _ n ； f = l 设计一种高效的选择算法，能够解决这个多约束的最优化问题，快速的从候 选指令系列里面选取出对系统性能提升最有利的扩展指令集合，将是面向特定应 用的指令集优化的关键问题之一。 3 实用的可重构阵列架构 生成并选择出了面向特定应用的可扩展指令之后，我们就需要在可重构硬件 上实现这些指令，以最大程度的发挥可重构硬件的高密度计算和并行计算优势， 提升自适应处理器的处理性能。 拟解决的关键问题为： 选择合适的可重构粒度：细粒度的架构要求的配置流相对较大，而且综合时 所需要的计算资源也相对较大，但是它能更好的实现候选指令，获得较好的性能 提升。粗粒度的架构则能更快的完成即时综合和配置。能否确定一个合适的可重 构粒度，对于自适应处理器的整体性能有很大的影响。 支持快速的动态重配置：自适应处理器针在动态剖析并生成了优化指令之 后，如何能让处理器在不中断上层应用的情况下，快速的重新配置到目标指令集 上，提升处理器性能，也是自适应处理器设计中的关键的问题之一。 1 2 3 论文的组织结构 本文共分六章，首先从研究背景出发，提出a s i p 设计中存在的问题与挑战， 给出解决方案的框架，然后针对其中的关键技术进行详细的描述。具体的组织结 构如下： 第l 章绪论：简要介绍了论文的研究背景，包括a s i p 的优点、可重构计 算及自适应计算技术，比较了几种不同的处理器技术，引入自适应处理器的研究。 然后描述了本文的研究目标和拟解决的关键问题，最后给出本文的组织结构。 第2 章a s i p 工具链问题及解决方案：主要介绍了本论文研究的动机。首 先分析a s i p 设计中存在的问题与挑战，指出了其中的关键问题。给出了一种基 第1 章绪论 于a d l 的指令集规范验证方法。然后，提出了一种新的解决方案：基于动态指 令集的自适应处理器a s a p 。描述了解决方案的框架，分析了其中的关键技术。 第3 章动态剖析技术：分析了目前常见的剖析技术，指出了其中的异同及 尚存的一些问题。描述了a s a p 框架中可配置硬件剖析器的详细设计与实现，通 过详实的数据和图表说明了各个部件的设计及关键参数的设置，最后通过实验对 剖析器的资源需求，剖析质量进行了验证。 第4 章指令集扩展技术：首先分析了目前已有的指令集扩展技术和相关工 作，结合a s a p 框架，给出了一个指令集扩展的算法。然后对指令集扩展选择的 另一个关键问题自定义指令选择进行了研究，针对目前常见的启发式算法无法找 到最优解的情况，给出了一种结合贪心策略和差分进化思想的i s d e 算法。 第5 章动态重构和映射：首先简要分析介绍了目前常见的动态重构技术， 然后结合a s a p 框架，描述了一种实用的可重构阵列架构的设计与实现，最后针 对这种架构，给出了一种利用硬件表格分析生产者消费者关系来自动映射指令 的方法。 第6 章总结与展望：对全文的工作进行了总结，并提出了进一步的研究方 向和设想。 1 2 第2 章a s i p 工具链问题及解决方案 第2 章a s i p 工具链问题及解决方案 如何降低或避免a s i p 工具链开发所带来的额外开销是a s i p 中的关键问题。 本章第一节介绍a s i p 的开发流程，并指出其中存在的工具链问题。然后分别给 出两种可能的解决方案：第二节针对目前常见的基于a d l 工具的设计流程提出了 一种基于a d l 的指令集规范验证方法；第三节则提出了本文的重点研究内容一 基于动态指令集的自适应处理器a s a p 的解决方案，并简要分析了三大关键技术 a s i p 的应用领域给它带来了许多非功能性的约束，如t t m 、低功耗、硬实 时性、容错等，其中1 t m 是其最重要的非功能性约束。此外，虽然与a s i c 相比， a s i p 的硬件设计代价有较大程度的降低，但是其总的设计，尤其是在软件设计 方面，代价还是较高。从a s i p 的设计过程我们可以了解到，除了要能够快速地 提供软件工具链之外，往往还要求对工具链进行验证。为了满足a s i p 应用所带 来的各种非功能性约束，如何降低a s i p 工具链的设计实现以及验证的难度，是 a s i p 设计的一个关键问题。 2 1a 剑p 的设计流程及问题 从图2 1 中我们可以了解到a s i p 从设计到应用的典型过程 5 】。由于目前的 设计方法一般采用基于设计空间搜索的“描述- 搜索- 细化”【4 9 】，设计时往往需 要迭代地进行设计空间搜索( 如图2 2 所示) 图2 1a s i p 的典型设计流程 1 3 第2 章a s i p 工具链问题及解决方案 件未忑诗扈h 用户圈彤鼻舾 一一- 。 整体拽赢 | i 空 用 可量足向工a 篮耋晓嚣ik 搴t 烯语义转疑嚣 篓膀 绽泽刁u i r l ，r 幢譬 坤伽m l l l “”。 ， 图2 2基于设计空间搜索的a s i p 设计过程 a s i p 的设计是个复杂的问题，目前国内外已有许多相关的研究 3 7 】 6 1 ，主 要集中在其设计的四大步骤中：应用剖析 3 8 】 3 9 】、体系结构设计【4 0 】【4 l 】【4 2 】 4 3 】 4 4 】【4 5 】、代码综合 4 6 】 4 7 】和硬件综合【4 8 】 4 3 】。具体的设计过程包括： ( 1 ) 抽取应用特征 要获得应用本身的特点和需求，进行应用特征的分析和提取是非常重要的， 它对后面的专用指令或硬件设计有着指导作用。一般情况下，输入到a s i p 设计 流程的是一个或一组应用程序，以及它们的测试数据和设计约束。设计者必须先 通过对特定应用程序( 一般采用高层语言描述) 进行静态或动态的分析，获取应用 程序的特征；然后通过某种方式将这些信息表示并存储起来，供后续步骤使用。 通常使用仿真工具对应用和它们的数据进行动态和静态的分析，提供给后续设计 步骤。这一步在图2 2 的设计过程中由应用分析器来完成。图2 1 中虽然没有画 在流程中，但也明显的标记出了a p p l i c a t i o n ( s ) 。 ( 2 ) 定制体系结构 根据前一步剖析得到的应用特征，定制体系结构，包括定制硬件资源和专用 指令等，给出处理器体系结构的描述规范。这一过程对应于图2 ，1 中的p r o c e s s o r s p e c s 步骤，在图2 2 的设计过程中则是由用户图形界面进行输入、使用体系结 构描述语言( 如l i s a ，x p a d l 等) 进行描述，然后利用体系结构库生成对应的体系 结构描述。 1 4 l l i l i i， 娶 第2 章a s i p 工具链问题及解决方案 ( 3 ) 描述设计实现相应的硬件 根据体系结构描述规范进行详细的处理器设计，使用硬件描述语言 ( h a r d w a r ed e s c r j p t i o nl a n g u a g e ，h d l ) 仿真验证等。在一些基于语言或环境的设 计方法中，这一步可以有工具自动生成以代码质量来换取设计时间。对应于图 2 1 的p r o c e s s o rd e s i g n 步骤，在图2 2 的设计过程中则是通过工具自动生成h d l 的。 ( 4 ) 剖析新设计的体系结构 为了获得较好地满足应用需求的处理器，在图2 1 的p r o c e s s o rd e s 噜n 过程 中，一般需要进行反复地迭代搜索。其过程在图2 2 的设计过程中体现为通过相 应的仿真器重新剖析、评估所描述的处理器，根据评估结果反馈到处理器描述和 设计上。 ( s ) 芯片设计 完成了处理器设计之后就可以进行芯片设计。如果在前一步的处理器设计中 进行了比较好的迭代设计，则会大大简化这一步的工作。 ( 6 ) 工具链 在完成了处理器设计和芯片设计之后，还需要根据设计的体系结构优化和定 制编译器等相关的软件工具链。 从上述的a s i p 的设计流程和方法中，我们可以看出a s i p 主要的设计问题主 要包括三个方面： ( 1 ) 体系结构相关技术 如何根据应用的特征为应用设计一个恰当的体系结构是设计者最关心的一 个问题。 ( 2 ) 性能分析技术 如何在设计过程中快速的评估体系结构设计的好坏将直接影响设计的效率 和处理器最终的性能。 ( 3 ) 工具链的快速实现和验证 如何能够快速地为处理器提供可靠的工具链将影响到设计的迭代过程和最 终用户的满意度。 其中难度最大的问题是：工具链的快速实现和验证。如何降低或避免a s i p 工具链开发所带来的影响对a s i p 的设计是至关重要的。 本章首先针对工具链中验证困难的问题，提出了一种基于a d l 的指令集规 范验证方法。降低了指令集规范的验证难度，加速了验证的过程，有利于缩短 a s i p 的兀- m ；然后，针对工具链开发负担大和用户需求动态变化大的问题，提 出了一个基于动态指令集的自适应处理器架构a s a p 来避免工具链带来的问题 并适应用户的动态需求。 1 5 第2 章a s i p 工具链问题及解决方案 2 2 基于a d l 的指令集规范验证 在a s i p 设计和应用的过程中，验证起着至关重要的作用，它贯穿了整个后 半阶段。从图2 1 中我们可以看到，设计时往往需要对指令集规范和工具链进行 反复的验证。其中指令集规范的验证尤其重要。 指令集规范是对处理器指令集的详细描述，是处理器体系结构的一种体现。 它是体系结构设计人员与软硬件开发人员之间沟通的规范约定，所有的软硬件设 计都应该和指令集规范一致。 指令集规范的书写是一个极其繁琐且极易出错的过程。指令集规范中一个小 小的不致，可能导致一个软件或固件开发团队花上多周的工作时间来跟踪和调 试整个系统的问题。因此，保证指令集规范与工具链的一致性是至关重要的。 尽管指令集规范验汪是a s i p 提供商都应该做的事情，却很少有比较系统的 方法。f e r n a n d e z 等提供了一种s l e d 语言【5 0 】，并提供了新泽西工具【5 l 】来操纵 机器代码。这套工具可实现自动的指令集规范检查【5 2 】，至今为止它找出了多 个通用处理器的错误。虽然，这套工具能够比较全面的描述指令集规范，并实现 自动的检查，但是它主要是面向通用处理器设计的，相对比较复杂，要移植到 a s i p 上难度较大。 考虑到目前常见的a s i p 设计方法中通常会使用高层体系结构描述语言( 如 l i s a 等) 先实现处理器模型，如果能同时验证该处理器模型和相应的指令集规范 及工具链将大大提高验证的效率。因此，我们详细分析了指令集规范，并提出了 一种简单实用的方法来协同验证指令集规范、处理器模型及工具链。 2 2 1 指令集规范 指令集规范通常包含语法、编码、描述、使用示例等不同的部分。尽管不同 的处理器的指令集规范会各不相同，但是一般都会包含以下几个主要的部分： ( i ) 语法 语法部分定义了指令的词法元素，包括助记符、格式、参数、标记等。 ( 2 ) 编码 编码是词法元素( 汇编码) 和机器码之间的对应关系，它定义了操作码、 位置和每个参数的位宽等。 ( 3 ) 约束 约束部分描述了指令的限制。对于a s i p 来说，自定义的指令可能会引 入一些约束。主要会包含两类约束：操作数约束和指令约束。操作数约束一 般限制了某些操作数的值域范围。而指 x 第2 章a s i p 工具链问题及解决方案 ( 4 ) 行为 行为部分描述了指令具体的操作、指令的功能以及影响到的处理器和内 存状态等。有些更详细的描述甚至包括了在微体系结构，如流水线上的操作 世 1 1 。o 指令集规范的验证主要包含了对上述若干重要方面的验证。利用a d l 可以 很方便的实现对指令集的验证。目前研究得比较多的是对行为的验证，因此我们 将重点描述对其他部分的验证。 2 2 2 基于a d l 的验证方法 a d l 可以用来描述处理器模型并自动生成相应的工具链，因此我们在它的基 础上可以方便地实现协同验证。主要步骤包括以下四个阶段： ( 1 ) 翻译阶段： 将指令集规范翻译成中间表示，我们定义了一种简单直观的基于位域的 表示方法，可以方便的用来描述指令集规范。 ( 2 ) 测试例生成阶段： 基于中间表示自动生成测试用例。 ( 3 ) 模型验证阶段： 通过修改a d l 模型，使之符合指令集规范。在此之后，我们就可以利 用a d l 工具自动生成相应的工具链。 ( 4 ) 验证阶段： 使用a d l 工具生成的工具链来验证目标工具，如果发现有不一致的地 方，就是指令集规范和工具链的不一致。 2 2 3 验证方法示例 一种基于上述方法的汇编器验证方法如图2 3 所示。我们将指令集规范使用 基于位域的表示方法描述后，利用测试例生成器自动生成测试例来验证l i s a 模 型，然后再利用l i s a 模型生成的汇编器来检测已有的汇编器。 汇编器中需要验证的主要有两方面，一个是指令编码，另一个就是约束检查。 指令编码错误将导致机器状态的不可预测性；而约束检查如果错误，会漏报或多 报约束，将使开发人员花费很多时间用于调试一些不小心违反的约束。 1 7 第2 章a s i p 工具链问题及解决方案 图2 3 基于a d l 的验证方法示例 2 2 3 1 基于位域的中间表示 为了能够实现测试例的自动生成，我们分析研究了常见指令集的语法和编 码，给出了一种直观的基于位域的中间表示法，能方便的用于测试例自动生成。 在基于位域的表示中，每条指令由多个位域组成。 对于一个配置文件，主要包含域定义( f i e l d s ) 和语法定义( s y n t 似) 两个部 分。域定义在指令定义之前，主要包含名称域和值域两部分。名称域可以是任意 的可见字符，但是我们建议使用一些比较有意义的名称，如r s ，r d 等。值域部分， 主要用于测试例自动生成，可以是独立的值或值区间。语法部分，每一行用来定 义一种语法，我们可以通过使用域的任意组合来形成不同的指令语法。语法中的 每一个字符都必须是前面显示定义过的，包括空白符。一条实际的机器指令可以 在语法部分有多条不同的表示用来测试不同的属性和限制等。 一个简单的示例表示如图2 4 所示： 1 8 第2 章a s i p 工具链问题及解决方案 墨l 蕞a = r o i i 5 ： r s b = i o i 1 5 ： r d = l l1 - ： s p = 、订l i t e 却a c e 。； = 【： 】= 】： 一钥f 咒d s p s y n b x a d d 印r ( 1s 1 ) r ：as 1 ) r s b ： l d 印【r d s p 风； 1 w k t e 印a c e 是为空格符丽设i 酌保留字 图2 4 基于位域的中间表示示例1 这种基于位域的表示方法非常简单，而且很灵活。对于一条相同的指令，可 以有多种不同的表示方式，从而用来测试不同的特殊情况。 例如：如果我们有两个寄存器组( b a n l ( ) ，对于a d d 操作，我们要求它的源 寄存器和目标寄存器必须在同一个组里面。为了检测这种约束，我们可以定义两 个不同的寄存器组域r b a n l ( a 和r b a n l ( b ，然后定义两条不同的语法来描述对不 同寄存器组的访问。这样定义之后，我们的工具就可以检测出“a d dr 0r 1r l ” 是不允许的指令，并找出所有的违反约束的地方。这样我们就能够很好的检测指 令集规范里面的操作数约束。示例的配置文件如图2 5 所示。 j r b a n k a = r or 2 ：一 r b a l l l 盂：b = i ur 3 ：+ i s p = w 1 1 i t e s p a c c ；j j j a d d s pr b a l 止as pr b a n k a 印r b a l 止a a d d 叩i 出a l l k bs pr b a l 她s pr b a l l k j 阻 s y n t a x j 图2