（计算机科学与技术专业论文）asip指令集自动扩展系统的研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 近年来，p d a 、手机、数码相机以及其它数字产品得到了广泛应用在这些 产品中，往往采用具有特定功能的硬件来满足性能、面积与功耗等多方面的要求。 最常用的策略是设计专用集成电路来解决这些问题但是随着工艺发展，设计专 用集成电路的成本越来越高，而且这些专用集成电路的可编程性也不好 因而人们提出a s i p 来解决上述问题。a s i p 以一个通用的处理器核为基础， 设计者在这个核的基础上根据应用的具体特征进行指令集扩展以提高应用中频繁 执行代码段的性能。 由于同一应用领域中不同应用程序之间的计算方式往往存在很大的相似性， 通过这种修改便可以使其在面向某一应用领域时的性能大大提高，而且这种设计 方式只需在原有芯片的基础上进行少量修改就可以快速设计出适应特定应用的新 芯片，大大缩短了芯片开发周期和上市时间a s i p 结合了通用处理器和a s i c 的 优点，受到了越来越多的研究设计人员及芯片厂商的关注。 面向应用扩展指令集是a s i p 设计过程的一个重要环节，这- - t 作的自动实现 对于缩短产品开发周期具有非常重要的意义。 现有的技术未能实现该过程的完全自动化，而且在选择指令时并没有全面考 虑指令对处理器面积和功耗的影响。本文设计并实现了一个面向特定应用的指令 集自动扩展系统，该系统不仅可以根据应用特征自动扩展新指令，而且可以自动 完成编译器的修改。 模拟结果显示，扩展的新指令能够在保持功耗、面积基本不变的前提下，带 来4 7 , - - 1 6 4 的性能提升 关键字：a s i p ，编译器，指令集自动扩展 第i 页 国防科学技术大学研究生院学位论文 i nr e c e n ty e a r s ，t h em a r k e t sf o rp d a s , c e l l u l a rp h o n e s , d i g i t a lc a m e r a s , n e t w o r k n m i t e r 3a n do t h e rh i g h - p e r f o r m a n c eb u ts 御i a l - p u r p o s ed f f 慨$ h a sg r o w ne x p l o s i v e l y i nt h e s es y s t e m s , a p p l i c a t i o ns p e c i f i ch a r d w a r ed e s i g ni su s e dt om e e tt h ec h a u c o g i n g c o s t , p e r f o r m a 麟，a n dp o w e rd e m a n d s t h em o s tp o p u l a rd e s i g ns t r a t e g yi st ob u i l da s y s t e mc o n s i s t i n go fan u m b e ro fs p e c i a l - p u r p o s ea s i c sc o u p l e dw i t hal o w c o s tc o r e p r o c e s s o r w h i l et h i sa p p r o a c hi se f f e c t i v e , a s i c sa 把c o s t l yt od e s i g na n do f f e ro n l ya h a r d w a r es o l u t i o nt h a tp e r m i t sa l m o s tn op o s tp r o g r a m m a b i l i t y a p p l i c a t i o n - s p e c i f i ci n s t r u c t i o n s - s o tp r o c e s $ o r ( a s i p ) w a sp r o p o s e dt om e e tt h e s e c h a l l e n g e s u s u a l l y , a s i pi s m a d eo nab a s i cc p uc o b yd e s i g n i n ga p p l i c a t i o n s p e c i f i ch 塔n u c 吐咖d e s i g n e r s 锄i m p r o v ec p up e r f o r m a n c e o nt h e s ea p p l i c a t i o n s t h ec o m p u t a t i o ni n t e n s i v ep o r t i o n so ft h e 蛐ed o m a i na r eo f t e l ls i m i l a ri nt h e s t r u c t u r e t h u s t h ec u s t o m i z e di i 塔缸俐彻sc a no 矗f c nb eg e n e r a l i z e di ns m a l lw a y st o m a k et h e i ru s eh a v ea p p l i c a b i l i t ya c r o s sas e to f a p p l i o a t i o d e s i g n i n ga p p l i c a t i o n - s p e c i f i ci l l s u l l c f i o n si sc r i t i c a lt oa s i pd e s i g 几a u t o m a t i l l g t h ed e s i g np r o c e s si so fg r e a ti m p o r t a n c 世t os h o r t e n i n gt h et i m e - t o - m a r k e to ft h e p r o d u c t c u r r e mt e c h n o l o g i e sa r cn o ta b l et om a l d n gt h ep r o c e s sf u l l ya u t o m a t i c ，a n dt h e i m p a c to fa r e aa n dp o w e ra r ea l s on o tf u l l yc o n s i d e r e dw h e ns e l e c t i n gi n 删o n s w e p r e s e n taf u l l ya u t o m a t i ci n s t m c f i o ng e n e r a t i o ns y s t e mf o rs p e c i f i ca p p l i c a t i o n si nt h i s p a p e r , a n di no u rs y s t e m , t h em o d i f i c a t i o no f c o m p i l e ri sa l s oa u t o m a t i c t h er e s u l ts h o w st h a tt h en o w1 1 1 s t r u c t i o n sc 缸b r i n g4 弼t o1 6 7 i m p r o v e m e n t , w h i l ek e e p i n ga 嗽a n dp o w e ra l m o s tu n c l 篮m g e d k e yw o r d s ：a s i p ，c o m p i l e r , a u t o m a t i ci n s t r u c t i o ng e n e r a t i o n 第n 页 国防科学技术大学研究生院学位论文 图目录 图1n i o s 处理器a s i p 扩展指令的实现 图2 指令模板合并过程。 图3 一个典型的数据流图 图4 对应于图4 的搜索树 图5 加法操作的时序 图6 1 1 渔处理器内核逻辑框图 图7 4 阶段混合流水线的示意图 图8 编译工具链示意图 图9 前端编译器的各个阶段 图1 0 调度器的工作示意图 图1 1 并行指令格式 图1 2t t a 并行指令结构。 图1 3 指令集扩展系统框架图 图1 4 指令集扩展器的工作流程 图1 5 程序表示的层次结构 图1 6p r o c 对象与p r o g 对象的关系 图1 7 控制流的表示： 图1 8 一个数据流图 图1 9 指令模板比较的例子 图2 0 g c c 编译器的结构 图2 l 乘累加指令示意图 图2 2 目标t t a 处理器的配置 2 4 3 l 3 3 3 6 4 1 第页 o j 巧j b m=2垮侈侈毖筋 田防科学技术大学研究生院学位论文 表目录 表l 部分硬件单元面积与功耗的计算公式 表2 基本指令集 1 7 表3 各个扩展阶段的统计数据 表4 指令集扩展前后的性能统计 表5 不同大小的指令模板对程序性能影响统计 4 0 4 l 4 l 4 2 第页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题日 堑! 瞳螽垒缁麴缝錾筮，绱茏查塞迢 学位论文作者签名：姿丝辇： 日期：2 彩年r 月l 仃日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：三匕挡叁延函红垃6 l 丕垃。如盟g 盐塞弛 学位论文作者签名： 作者指导教师签名： 甚翔：沙u 毛年r 其1 f b 日期：妒莎年r 月f 扣 国防科学技术大学研究生院学位论文 1 1 1a s i p 的出现背景 第一章绪论 1 1 课题研究背景与意义 近年来，p d a 、手机、数码相机等数字产品的市场日趋繁荣。这些产品中的 芯片往往要根据不同的应用背景处理不同类型的应用程序，有时还要求这些处理 器对特定的应用有较强的处理能力，甚至在特定的环境下满足功耗、芯片面积等 设计约束，这都给现有的通用处理器提出了新的挑战。虽然通用处理器对各种应 用的适用性很强，但是往往无法达到在特定应用环境下对芯片性能、面积及功耗 的要求。人们试图通过专用集成电路( a s i c ，a p p l i c a t i o ns p e 碰ci n g r a n dc i r c u i t ) 解决这一问题。但是，随着集成电路工艺发展到深亚微米甚至超深亚微米，一个 全新芯片的设计与验证复杂度越来越高，主要表现在以下5 个方面【l 】： ( 1 ) 深亚微米效应：当电路设计进入到深亚微米的范围内时，面临许多设计 上的挑战，其中最主要的是互联线延迟。在传统的设计流程中，前端的设计者创 建了r t l 网表，然后交给后端的设计者。这种网表中不含有任何物理信息，导致 在前端和后端设计之间需要进行多次的迭代如果在前端设计中没有互联线延迟 的相关数据，将导致r t l 网表不能满足后端设计的时序需要在某些极端的情况 下，在逻辑( 前端) 设计和物理( 后端) 设计之间的迭代将永远不会收敛 ( 2 ) 晶体管数的增加：集成电路工艺的进步虽然使得可以在同样的面积下集 成更多的晶体管，但是这所带来的设计问题是：不但单个晶体管越来越难设计， 而且设计单个芯片所面临的晶体管总数呈指数级增长趋势。这也使得集成电路设 计工具难于应付这种情况 ( 3 ) 系统集成度的增加：电路工艺的进步可以使许多不同的功能都可以集成 到一个芯片上。例如为了增强芯片功能，往往需要在原有数字电路的基础上需要 增加一些数模混合电路。这一方面使芯片的设计变得复杂，另一方面对数字电路 设计人员也提出了更高的要求。 “) 制造费用的增加：随着工艺的不断进步，一个新芯片的制造费用越来越 高。在1 3 0 - 1 8 0 n m 工艺下，光是一个芯片的封装费用就要上百万元人民币，这还 不包括随之增长的测试费用。按照目前的发展趋势估计，即使设计技术有所进步， 到2 0 1 0 年时，一个新芯片的设计与制造费用也要达到上亿元人民币田。 ( 5 ) 开发周期的限制：随着数字产品市场竞争的日趋激烈，一个芯片产品的 上市时间往往决定了其产品的成败，所以，当今芯片的开发周期都有着严格的时 间限制，否则芯片一上市便面临被淘汰的危险。 第1 页 国防科学技术大学研究生院学位论文 此外，a s i c 还具有通用性差的痼疾 综上所述，无论是通用处理器还是a s i c ，都难以满足竞争日趋激烈的数字产 品市场对芯片的各种要求。而a s i p d 】( a p p l i c a t i o ns p e c i f i c1 1 3 s t r u c t i o n - s e tp r o c e s s o r ) 能够很好地解决这些问题。 1 1 2a s i p 的优势 a s i p 设计通常以一个通用的处理器核为基础，这个通用处理器核能支持某个 基本且完备的指令集，而且能满足绝大部分应用环境下对芯片面积和功耗的要求， 然后设计者在这个通用核的基础上根据应用的具体特征增加具有特定功能的硬件 以满足应用的需求这些增加的特定功能硬件从编程层次来看，就是一些在原有 指令集上扩展出的实现某种特定功能的指令这些扩展指令可以是基本指令的组 合，如在d s p 芯片中经常出现的乘累加指令，也可以是某些特殊的指令，如三角 函数指令和子字并行指令等这种设计方式的好处【4 】主要体现在以下两个方面： ( 1 ) 同一领域中不同的应用程序所采用的算法以及计算方式往往存在很大的 相似性，通过分析应用中频繁执行的代码段，增加特定功能硬件并扩展指令集便 可以较小的代价大幅度提升处理器面向该领域应用的性能。 ( 2 ) 在这种设计方式下，只需在原有芯片的基础上进行少量修改就可以快速 设计出适应特定应用的新芯片，省去了大量的芯片设计、验证与测试工作，大大 缩短了芯片开发周期和上市时间，从而节省了芯片的开发成本与费用，增强了新 的芯片在竞争日趋激烈的数字产品市场中的竞争力 总之，a s i p 不但结合了通用处理器和a s i c 的优点，而且能够解决两者所面 临的问题，因而受到了越来越多的研究设计人员及芯片厂商的关注。在目前商业 领域，t e n s i l i c a 公司的x t e n s a 5 】 3 2 1 系列处理器就是成功运用a s i p 设计思想的一个 典型例子。其主要特点是可自由配置，扩展强，且设计自动化程度高。应用x t e n s a 的技术，系统设计人员可根据自己的应用需要，配置内部c a c h e 大小，总线位宽， 浮点运算单元，d s p 引擎，中断数量等等，进而可以针对应用扩展添加全新的指 令、寄存器和i o 端口，从而设计出具有专用功能的处理器内核。 1 1 3 指令集自动扩展的意义 面向应用扩展指令集是a s i p 设计过程中至关重要的一个环节，所以，设计 a s i p 的关键问题在于，如何设计一组有效的扩展指令以及如何评估这些扩展指令 带来的性能提升这就需要分析不同应用的特点以决定如何扩展出有效的指令。 指令集的改变也给软件带来了新的问题，即如何快速地为新设计的处理器开发出 一个配套的软件工具链。如果上述过程完全由手工来完成的话将是一项十分耗时 第2 页 国防科学技术大学研究生院学位论文 的工作，这样a s i p 设计所带来的开发周期短的优势就会大打折扣。因此如何设计 一种在# , s i p 上自动扩展指令集的方式对于a s i p 的设计来说显得十分重要。 1 2 国内外研究现状及分析 1 2 1 指令集扩展技术的发展 早在2 0 世纪八十年代国外学术机构就开展了指令集自动设计问题的研究。不 过，这些早期研究更多地集中在通过设计出复杂指令从而在机器语言级更好地支 持高级语言以改善两者的界面1 6 1 1 7 1 。例如在j p b e n n e t t 的论文m 中，通过以自动 或半自动的方式设计指令集来分别解决加速程序运行速度、缩小代码体积等问题 嘲阴，但是其所运用的指令集自动设计方法是面向c i s c 一类的通用处理器的，不 适用于a s i p 这样的处理器。 而真正面向a s i p 的指令集扩展的研究始于九十年代。早期大量指令集扩展方 面的研究针对可重构处理器( r e c o n f i g u r a b l ep r o c e s s o r ) 体系结构，指令扩展工作往 往完全由设计人员手工完成m g - s e h w i n d ! l o 】通过以下步骤实现指令集扩展：首先 分析应用程序，找出程序中最频繁执行的代码段，然后分析这些代码段的特点以 决定扩展哪些指令，最后修改处理器的a l u 单元，使之能够支持新的指令。这些 步骤完全是设计人员手工完成 早期a s i p 设计面向的主要是嵌入式领域。受工艺限制，早期嵌入式处理器的 处理能力有限。运行的程序都比较简单，完全用手工汇编编写，所以整个指令集 扩展过程通过设计人员用手工来完成是可以接受的。然而，随着工艺技术的不断 进步，嵌入式处理器的处理能力不断增强，其运行的程序也变得日趋复杂起来， 并且，目前已经有研究人员将a s i p 应用于高性能处理器的计算内核，例如c e l l 处理器i i ”如果依然由设计人员一步步地手工完成指令集扩展的各个过程，尤其 是人工分析应用程序的代码执行特征，将会大大影响处理器的设计效率与开发周 期。因而近年来，研究人员开始逐步地进行如何将a s 口指令集扩展过程自动化的 研究。 1 2 2 研究现状分析 总的说来，a s i p 指令集扩展的过程可以分为三个步骤：首先是分析目标应用 生成候选指令；然后是对候选指令进行评估，并根据评估结果选择扩展指令；最 后添加扩展指令并修改编译器。而进行a s i p 指令集自动扩展的目的就是自动地完 成上述过程以提高a s i p 的开发效率。早期研究主要集中在自动实现第一步工作， 而目前的研究则将工作延伸到扩展指令的自动选取上不同研究之间的区别主要 第3 页 国防科学技术大学研究生院学位论文 在于所采用何种体系结构，选择什么生成候选指令的算法以及如何选取扩展指令。 ha s 口的体系结构 采用何种体系结构决定了a s i p 扩展指令的实现方式。按照传统的体系结构分 类，a s i p 处理器的体系结构可分为两类：流水线结构的处理器和v l i w 结构的处 理器【1 2 1 。 无论是面向嵌入式领域，还是在作为高性能芯片的协处理器，a s i p 在硬件设 计上往往受到功耗和面积的限制，所以采用流水线结构的a s i p 处理器，一般都是 采用简单的单发射5 段流水线，且大多数研究者都把a s i p 的所有扩展指令作为一 个特殊的功能单元在a l u 单元之外实现。例如，j c o n g 在习中以n i o s t l 4 1 商用嵌 入式处理器作为基础，在其a l u 运算单元之外加入实现a s i p 扩展指令的运算逻 辑，如图l 所示 图1n i o s 处理器a s i p 扩展指令的实现 这种以流水线结构为基础的a s i p 处理器存在的问题在于，扩展指令时会受到 指令编码的限制，因为流水线结构处理器原有指令格式多是比较规整的r i s c 指令 结构，一条指令的长度是固定的，且一般形式是( 操作，操作数l ，操作数2 ) 。 而扩展的复杂指令往往需要多个操作数，一方面会破坏原有规整的指令结构，另 一方面也会受到指令长度的限制。 另一类常见的a s 口体系结构是w 结构嘲【1 6 1 1 7 1 在v l i w 的结构下，可 以不受指令编码对扩展指令的限制，a s i p 扩展指令可以用数个功能单元来实现， 因而其实现的灵活性也比采用流水线结构的a s i p 处理器要好本文就采用了类似 v l i w 结构的传输触发体系结构( t r a n s p o r tt r i g g e r e da r h i c t e c t u r e ) ，在后面的章 节中会具体介绍该体系结构。 第4 页 图防科学技术大学研究生院学位论文 。候选指令生成算法 候选指令生成算法的主要作用是通过分析应用程序的特征，生成一个可以作 为扩展指令的候选指令集候选指令生成算法基本可以归为两类，基于基本指令 的组合进行模板匹配和基于程序的数据流图进行搜索。 ( 1 ) 用模板匹配的方式生成候选指令 以这种方式生成候选指令的主要思想是，预先生成一个候选指令的超集，然 后用这个超集中的候选指令去匹配数据流图的结点，最后得到候选指令集。这类 算法最典型的是m a r n o l d 所提出的候选指令生成算法【l 耵。 在乩a r n o l d 提出的算法中，首先把一些基本指令作为基本指令模板，然后通 过不断地合并基本指令模板得到复杂指令模板，最后得到一个由各种指令模板组 成的候选指令模板库。合并过程如图2 ( a ) 与图2 ( b ) 所示，图2 ( a ) 是未合并之前的 基本指令模板，图2 是将基本指令模板经过组合之后得到的复杂指令模板，所有 的基本指令模板与复杂指令模板共同组成候选指令模板库 “一5 。- 一，i ：i 一；j 。o 。獭，i i ：曼：。，二：； 图2 指令模板合并过程 当构建完成候选指令模板库之后，算法用这些指令模板在程序的数据流图上 进行匹配，通过匹配可以统计出各个模板的出现频率，当把出现频率低的模板筛 去之后，就可以得到候选扩展指令集。 这类通过模板匹配方式生成候选指令集的算法往往需要预先定义好一个候选 指令模板的超集，虽然以这种方式生成候选指令的速度较快( 一般这类算法的复 杂度为o ( 1 q z ) ，但如果这个候选指令模板的超集定义的不完整时，指令扩展所带来 的性能提升就会大打折扣。 ( 2 ) 用搜索的方式生成候选指令 以搜索方式生成候选指令的主要思想是，先建立程序的数据流图，然后按照 一定的约束条件在数据流图上搜索生成候选指令这类算法能够避免生成那些不 必要的候选指令模板，但其算法复杂度比较高。如何对搜索过程加以控制从而避 第5 页 国防科学技术大学研究生院学位论文 免搜索时间过长，是这类算法所主要解决的问题。 i 盎= ；二一、；一7 ：睁uv ：i i j 图3 一个典型的数据流图 采用搜索方式生成候选指令的研究中，比较典型的是ka t a s u 1 9 1 提出的算法。 他对于数据流图的搜索过程加入了三点限制： i 指令模板子图的出边数目要小于给定限制 i i 指令模板子图的入边数目要小于给定限制。 i i i 指令模板子图要满足封闭性，所谓封闭性是指，在该子图所有两个结点 之间的路径中，不能含有子图之外的结点。 例如对于图3 的数据流图，其搜索树如图4 所示。其中黑色结点是满足搜索 限制的结点。根表示不选择任何结点，0 分支表示不选择当前层所代表的结点，1 分支表示选择当前层结点。下面给出了ka t a s u 的搜索算法： 的复杂性，但在加入种种限制之后，搜索时间并不长。 是指数级 第6 页 国防科学技术大学研究生院学位论文 圈4 对应于圈4 的搜索树 候选指令的选择 候选指令的选择方式是指令集自动扩展的另外一个重要方面，但它被很多研 究者所忽视。在早期的研究中，候选指令的选择是由手工来完成的( 瑚而另外一 些研究者在处理候选指令选择的问题时，把这个过程与候选指令的生成合为了一 个过程，即在进行候选指令生成的同对，直接用生成的候选指令进行替换劂。这 样做所带来的问题是，无法在其他的程序中重复利用已生成的候选指令。从编译 的角度来看，这种做法是行不通的。 一个比较好的方法是对候选指令集进行筛选后得到一个扩展指令集，然后在 目标代码生成阶段从扩展指令集中选取指令对中间代码进行替换。大多数研究者 以中间代码的数据流图为基础进行候选指令的选择从而生成目标代码。下面以j c o n g 在论文【u l 中所提到的方法为例来说明指令选择过程 首先计算每个候选指令的加速比，其加速比的计算方法为： s p e e d u p 雌i l = t 青井- tl 蝴 这里t 音井- 是在合并之前该候选指令所对应的数条指令以周期为单位的执行时间， 而t 髓n + 是该候选指令所需的时钟周期数 然后计算每个候选指令的优先级，优先级由加速比与该候选指令出现频率的 乘积决定，乘积越大优先级越高 最后对候选指令进行选择来替换中间代码，从而生成目标代码，而选择候选 指令时就是依照之前计算出来的优先级用贪婪的策略进行选择。 显而易见，以上面的方式选择指令无法保证得到最优解。其实，对于最优候 选指令选择的闯题可以这样表述：对于候选指令1 1 1 2 ，1 3 k ，每个指令对于程序 的性能提升为g 1 ，g 2 ，0 3 g n ，每个候选指令的开销( 主要是面积) 为 c 1 ，c 2 ，c 3 c n ，如何从中选取一组指令，使得在不超过总开销c 。i 的限制下，对 于整个程序的性能提升最大。这看起来是个o 1 背包问题，但实际上要比背包问题 复杂的多。因为，候选指令之间往往存在着相关关系，当选择了一个候选指令后， 第7 页 国防科学技术大学研究生院学位论文 另外一些候选指令的性能提升就可能不再是原来的值。因而。求候选指令选择最 优解的问题实际上是个n p 难的问题。 大部分研究者在进行指令匹配时，采用的方法是把数据流图划分为树，然后 用树覆盖1 2 1 删】的方法把数据流图的结点用候选指令进行覆盖，从而生成目标代码 这种方法生成代码的速度很快，但数据流图毕竟不是树，采用这种方法只能满足 局部最优解有些研究者试图避免这个情况，例如在文献c 2 2 】所提出的算法中，把 一条条指令拆分为寄存器传输“原语”，通过用整数规划的方法重新组合这些。原 语”来求得最优解，但这种算法在最坏情况下的复杂度是指数级的，实际的编译 器不适合采用这种方法 1 2 3 现有研究的不足之处 前面提到过，早期研究主要集中在实现候选指令生成的自动化上，其他的工 作还是依赖手工完成。目前的研究则将工作延伸到扩展指令的自动选取上，其共 同的方式是设计一个算法进行候选指令模板的评估与选择，然后用这些选择出来 的模板在数据流图上进行匹配替换，最后生成目标代码。不过绝大部分研究工作 忽略了指令集扩展过程中的两个重要问题扩展指令对硬件开销的影响以及相 应编译器的修改生成。 许多研究工作都倾向于通过生成复杂的指令模板来提高程序性能，而这些复 杂模板从测试结果看起来似乎可以大幅提高性能，但是却给硬件设计带来了很大 的开销，而且这些复杂模板往往只适用于某个特定的程序，对其他程序性能提升 不高。从本文后面第4 章第2 节的测试数据中可以看出。最频繁出现且对性能影 响较大的往往还是一些简单的指令模板。 另外，若想在新设计出的处理器上开发应用，则必须要有编译器及配套工具 的支持。为缩短a s i p 的开发周期和上市时间，快速完成编译器的修改及生成配套 的软件工具是非常重要的。这一点也是很多研究者所忽视的。 第8 页 国防科学技术大学研究生院学位论文 1 3课题研究主要内容 前面提到过，面向a s i p 的指令集自动扩展主要包含三个过程：候选指令的生 成、候选指令的选取以及编译工具的修改候选指令生成的两个主要问题是指令 的生成方法和评价方式，如何生成候选指令以及能否制定出一个客观的评价标准 直接决定了最终硬件的实际实现如果不能很好地解决这两个问题将使得模拟结 果与硬件实现有较大差距而指令选取过程的主要问题包括：如何在满足各种设 计限制的同时更好地改善程序的运行效率以及如何设计一个启发式算法来有效地 避免选取过程中的组合爆炸问题。另外，在指令集扩展后如何快速地生成相应的 编译工具也是一个值得关注的问题。 本课题在t r a 体系结构的基础上深入研究基于 ir a 的a s i p 的指令集自动扩 展方法，解决指令扩展过程中的各种关键闯题，并研究了a s i p 软件工具的自动生 成方法本课题的研究内容主要分以下几个方面： 1 候选指令的生成算法 候选指令的生成是a s i p 指令集自动扩展过程中至关重要的一步，如何在一定 的体系结构模型中定义候选指令的延迟和硬件代价等参数，如何从应用中提取特 征来指导指令扩展，以及扩展出的指令是否能由硬件以估计的代价实现都是需要 研究的重要问题。本文设计并实现了一个候选指令生成算法，该算法的一个显著 特点是在硬件信息的指导下生成候选指令，这使得不但在生成候选指令时避免了 盲目搜索，而且充分考虑了候选指令在硬件实现上的开销。 2 候选指令的选取算法 指令的选取过程一方面要考虑使选出的指令能优化应用程序的性能，另一方 面还要考虑选取指令时的各种诸如芯片面积和指令集大小之类的限制综合以上 的考虑，往往需要在选取指令时有一个启发式的算法，该算法既要能避免组合爆 炸问题又要能达到加速程序运行的目的因此，设计一个优秀的启发式算法是候 选指令选取过程要解决的主要问题。 & 编译器等软件工具的自动修改技术 基于同一个基本体系结构而设计出的不同a s i p 之间具有相同的基本指令集， 其区别之处在于它们的扩展指令不同，因此没有必要为新设计的a s i p 开发一个全 新的编译器。如何以一种较快的方式生成新的编译器对于a s i p 的设计而言也是一 个重要问题。 第9 页 国防科学技术大学研究生院学位论文 1 4论文结构 全文共分为5 章： 第一章主要介绍本课题的研究背景及研究意义。 第二章主要介绍传输触发操作的思想以及根据此思想提出的t r a 体系结 构，这是本课题工作的基础。 第三章详细阐述了本课题的主要工作旨令集自动扩展系统的设计与实 现，主要包括指令集扩展系统的组成，内部数据结构，指令集自动扩 展的流程以及关键算法的设计实现。 第四章主要介绍对本系统的测试，主要包括测试方案、基准程序的选择方法 以及对测试结果的分析。 第五章总结全文，并介绍将来的研究工作。 第l o 页 国防科学技术大学研究生院学位论文 第二章t 1 l a 体系结构及编译工具链 2 1t t a 体系结构概述 2 1 1 传输触发的思想 当前处理器技术的进步主要依赖三个方面 2 3 1 ；更高的处理器时钟频率、体系 结构技术的进步以及编译器技术的进步。其中，开发指令级并行是a s i p 所采用的 一种主要的体系结构技术。 时钟频率的提升主要依赖两个方面：一方面是超大规模集成电路设计技术以 及工艺的进步，另一方面则通过设计超长流水线来减少流水段闻的逻辑门数来提 升频率。 指令级并行( i n s t r u c t i o nl e v e lp a r a l l e l i s m ) 的开发基于这样一个事实：随着工 艺技术的进步，单个芯片上可以集成越来越多的逻辑，因而可以通过重复设置大 量的功能单元和数据通路来支持指令级并行，所以开发指令级并行的实质是如何 把应用程序中潜在的指令级并行更好地映射到目标体系结构上去这种映射过程 可以由硬件来完成也可以由软件来完成。 超标量技术是典型的采用硬件来完成影射过程的技术。在采用超标量技术的 处理器中，大量的硬件负责检测操作之间的依赖关系并完成资源分配，但这一技 术的缺点是硬件资源消耗比较大，且设计复杂。v l i w 结构的处理器则主要是采用 软件编译器来完成指令闻的冲突检测和资源分配，降低了硬件设计与实现的复杂 度，但其缺点是编译器在进行指令调度时所获得的静态信息要比硬件进行调度时 少得多。 通过编译器技术提升处理器性能的关键在于，设计一种可以使编译器获得更 多硬件资源信息的体系结构，这样可以使编译器采用更多的编译优化策略。例如， 当编译器知道详细的功能单元结构时。便可以在生成代码时减少不必要的流水线 停顿。 传输触发体系结构( t t a ，t r a n s p o r tt r i g g e r e da r c h i t e c t u r e ) 2 3 1 的提出正是基 于以上三个方面的考虑，它是源于传输触发的思想。 在v l i w 、超标量等体系结构中，操作的执行将会触发一系列的数据传输。以 加法操作“r i = 1 1 2 + r 3 ”为例，它的执行将会隐含地触发“读r 1 ”，“读r 2 ” 和“写r 3 ”共三个数据传输。可以认为，这类结构的实质是“操作触发传输” 现有的体系结构描述都是按照这种思想进行的。 而“传输触发操作”思想与之正好相反，只有在所有的源操作数都被写入寄 存器后，操作才可以开始。此时加法操作的执行方式变为：加法功能单元a d d 带 第l l 页 国防科学技术大学研究生院学位论文 有三个寄存器a d d o 、a d d t 和a d d r ，分别用于保存被加数、加数和运算结果： 只有当两次数据传输“r l - a d d o ”与“r 2 - a d d t ”完成后，即被加数与加数均 己被写入a d d 的相应寄存器后，加法操作才能被触发；当加法操作完成后，操作 结果被写入a d d 单元的结果寄存器a d d 。r ，可以通过另一次数据传输。a d d r - r 3 ” 将结晨写回目的寄存器上述操作完成的时序如图5 所示 圈5 加法操作的时序 为实现传输触发操作，每个功能单元中都应提供专门的o r t 寄存器保存操 作数，其中o 寄存器和t 寄存器用于保存源操作数，而r 寄存器保存运算结果。 我们约定，当且仅当操作数被写入t 寄存器后，相应的操作才能被触发。因此， 每个功能单元有且仅有一个t 寄存器，而可以有多个o r 寄存器。 2 1 21 - r a 体系结构 hn a 的逻辑结构 t t a 体系结构是以传输触发操作思想为基础提出的【参考文南叼。1 1 a 的一条 指令中可以包含多个数据传输，其结构类似v l i w 图6 显示了1 1 、a 结构的逻辑 框图，它可以同时传输4 个数据功能单元( f r o ) 和寄存器文件( r e g i s t e r f i l e ) 通过s o c k e t 连接在互连网络( t r a n s p o r tn e t w o r k ) 上。数据通过总线在功能单元和 寄存器文件之间传输并触发相应的操作。如果每条t r a 指令中的数据传输都来 自于同一操作，这种代码称为。串行代码”，否则被称为。并行代码”显然， 并行代码的执行效率高，因此1 1 a 结构使用并行代码作为目标代码，而串行代码 被用作优化过程中的中间代码 第1 2 页 国防科学技术大学研究生院学位论文 一。”。v ：- = r r 、 圈6t i a 处理器内核逻辑框图 t t a 体系结构的优势有以下几个方面：( 1 ) 结构简单、灵活，便于参数化描 述；( 2 ) 每个对钟周期只进行数据传输，时钟周期短，因此工作主频高； ( 3 ) 所有的数据传输均是编译器可见的，不仅可以开发指令级并行，还可以开发粒度 更细的数据级并行性( d a t al e v e lp a r a l l e l i s m ) ，有利于进一步提高性能；( 4 ) 功 能单元提供了额外的寄存器保存操作数，减少了对通用寄存器的访问次数。t r a 结构的上述优点使得我们能够设计出高性能、低功耗的a s i p 。 o 功能单元的设计 在 i r a 体系结构中，功能单元( f u ，f u n c t i o nu l 血) 是执行运算的主体，单个 功能单元的操作执行方式是基于传输触发，而不是基于操作触发的。因此，每个 功能单元包含一个或者多个操作数寄存器c o ) 、唯一触发寄存器i f ) 和若干个结果寄 存器( r ) 。当数据传输到触发寄存器时，就会触发该功能单元将操作数寄存器和触 发寄存器中的值作为源操作数，来完成相应的操作，并将结果放入结果寄存器。 同一个功能单元通常可以执行多种操作( 比如加法和减法) ，这需要通过不同的 控制码来区分 根据所保存操作数的不同，f u 中的寄存器可分为三类： ( 1 ) 操作数寄存器( o p e r a n dr e g i s t e r , o r ) ：保存源操作数每个f u 有且仅有 n 1 个o r 这里n - - m a x h iln i 为该f u r 支持操作中源操作数的最大个数 。 ( 2 ) 触发寄存器( t r i g g e rr e g i s t e r , t r ) - 保存源操作数。源操作数写入该寄存 器表明f u 的所有操作数都已准备好，可以开始操作。从这个意义上讲，数据写入 该寄存器将触发f u 的一次操作，因此将其称为。触发寄存器”每个f u 有且仅 有1 个t r 具体执行哪个操作由控制信息指定注意：源操作数被写入o r 的时 问不得晚于t r 中数据准备好的时间 ( 3 ) 结果寄存器( r e s e tr e g i s t e r , r r ) ：保存结果操作数。每个f u 有且仅有一 个r r 。 n a 的功能单元均是可以流水的，不同的功能单元延迟表示其流水级数，并 且编译器对功能单元的延迟是可见的。t t a 还支持一种称为混合流水( h y b r i d p i p e l i n e ) 的功能单元实现方式。在混合流水方式中，每个流水段都被赋予一个有 第1 3 页 国防科学技术大学研究生院学位论文 效位来标识该流水段是否包含有效的结果数据。这种混合流水方式赋予了编译器 更大代码调度自由性。图7 是一个包含4 阶段混合流水线的功能单元的示意图 2 1 3t 1 a 编译器的优势 图74 阶段混合流水线的示意图 r j j ：_ ， ：三 一。一：。；：罾 ， 弩誓q _ - 一l 单- 咚； 一：一 t - 硇劈勘蛹5 - i _ 埘缸畸= 7 。f v 一 蛾哇囊震： 1 ：? 一” j - 知常_ 棚- 囊一j 每翻嘲汹岫l 雌： 一 x，。 ：； 毒毫_ j 二o 一。 基于t t a 体系结构自身透明性强以及结构简单的特点，使得t r a 的编译器有 以下一些特色优势搿；： 1 软件旁路( s o f t w a r eb y p a s s i n g ) ：由于r r a 结构的操作是以数据传输为 单位的，且功能单元自身的寄存器就可以用来保存数据，所以编译器在代码调度 时可以把中间结果保存到功能单元的寄存器中，从而减少传输次数并省去了硬件 旁路部件。 2 作废结果传输消减( d e a dr e s u l tm o v e ：e l i m i n a t i o n ) ：当对某个值的使用与 该值的生成传输在同一个周期时。对该值的使用传输便可以被删除。 3 操作数共享( o p e r a n ds h a r i n g ) ：一个功能单元通常可以完成多种操作， 比如一个加法器可以执行加法和减法操作，它们通过不同的操作码来区分如果 在功能单元上执行的多个不同操作使用相同的操作数，那么该操作数只需要移动 一次而不是多次，即实现了操作数共享。同时也减少了操作次数，提高了性能。 4 操作数交换( o p e r a n ds w a p p i n g ) ：编译器可以根据代码调度的需要随时 交换两个操作数的位置，只有把一个操作数放到功能单元的触发寄存器中才触发 相应操作。 5 s o c k e t 共享( s o c k e t s h a r i n g ) ：当在不同的总线上读取同一个寄存器，或 者读取连接在同一个输出s o c k e t 上的不同寄存器内容时，多个读操作可以共享同 一个s o c k e t 。这样虽然没有减少操作数量，但是放宽了硬件资源的限制尺度，因 此利于编译效能的提高。 6 更大的调度自由性( m o r es c h e d u l i n gf l e e d o m ) ：在这种体系结构中，操 作数的移动和结果的移动是可以完全独立的，因此在调度时编译器获得了更大的 自由度。操作数的传输和结果的传输均可以在不同的时钟周期完成。 第1 4 页 国防科学技术大学研究生院学位论文 2 2 。1 概述 2 2t t a 软件工具链 t r a 编译工具链的主要作用是把高级语言编写的源程序编译成可在t r a 结构 的处理器上运行的并行代码。该工具链主要由4 部分组成： ( 1 ) 前端编译器前端编译器负责把高级语言( 例如c 、e h ) 编写的源程序 编译成串行代码。 ( 2 ) 调度器。调度器负责把串行代码调度成并行代码。 ( 3 ) 模拟器模拟器可对串行代码与并行代码进行模拟验证 ( 4 ) 评估器评估器可对目标 ir a 处理器硬件开销进行评估。 图8 展示了该工具链中4 部分之闻的关系，前端编译器和调度器都可以由一 系列参数来控制例如，对于前端编译器而言，可以用参数来选择是产生硬件支 持的除法指令还是通过调用库函数来软件模拟除法调度器的参数可以控制在代 码调度时采用何种优化策略，而机器描述文件则用来描述目标处理器具体的体系 结构配置，包括各个功能单元的支持的操作、功能单元的延迟以及互联总线的连 接情况。调度器根据机器描述文件的信息把串行代码调度成并行目标代码。从图 中还可以看出，模拟器除了对串行代码与并行代码进行模拟验证外，它还可以为 调度器提供p r o f i l e 信息，调度器可以利用这些p r o f i l e 信息采用更好的调度策略 最后，评估器还可以对处理器的硬件开销进行初步评估。 图8