（微电子学与固体电子学专业论文）基于lisa的定制处理器研究.pdf

摘要 摘要 随着通信、视频等高复杂度应用的出现，通用c p u 已无法满足计算密集型嵌入式应用的要求， 单纯通过提高处理器主频达到性能提升，势必会引起整个嵌入式系统功耗增加；单纯使用a s i c 设 计，则会使系统灵活性下降。针对目标应用定制处理器，可以在性能、功耗、成本和灵活性等多个 方面获得最佳的平衡。指令集扩展并精确评估其性能是定制处理器设计的关键环节，分析目标应用 算法采用手工指令集扩展和等待处理器硬件设计完成再评估其性能必然会影响处理器的设计周期。 自动指令集扩展技术通过自动分析目标应用程序，快速搜索程序中满足约束的结构，获得候选指令 集，再在候选指令集中选择出能够有效提升处理器性能的指令，并通过结构描述语言建立精确的处 理器模型，在设计之初快速精确的评估处理器性能，可以大大缩短处理器的设计周期。 本文建立了基于结构描述语言l i s a 的周期精确的基本处理器模型，包括：存储器子模型、资 源子模型、行为子模型、指令集子模型和时序子模型。指令集子模型使用a n a l o gd e v i c e s ( a d i ) 公 司的1 6 位处理器a d s p 2 1 9 1 指令集作为基本指令集，包括：a l u 指令、m a c 指令、s h i f t e r 指令、 m u l t i f u n c t i o n 指令、d a t am o v e 指令和p r o g r a mf l o w 指令。设计了搭建虚拟原型平台需要的周期精 确的e m i 模型和s d r a m 模型。虚拟原型平台是处理器模型优化、目标应用程序优化和自动指令集 扩展的基础。 在候选指令集生成过程中，本文提出了基于关系矩阵的候选指令集生成算法，加速候选指令集 的生成。关系矩阵代表了程序数据流图中各个顶点之间的关系，对于没有关系的顶点，在建立搜索 二叉树时次序可以调换，因而它们对当前节点子树的影响相同。算法保证对当前节点搜索时，与其 相关的节点都已搜索结束，如果与当前节点相关的两个节点中有一个不满足约束条件，并且当前节 点相对于相关节点引入的两个新顶点无关，那么当前节点肯定不满足约束条件，可以忽略其子树的 搜索，因此算法可以大大减少搜索不满足约束条件的节点个数。与a t a s u 算法相比，在m p 3 解码中 的子带综合示例、m p e g 4 解码中的i d c t 示例、a d p c m 解码示例、m d 5 算法示例、f f f 变换示例 和y u v 2 r g b 示例的候选指令集生成过程中，获得了相同的满足约束的节点数，在定义不同的输出 约束条件下，搜索不满足约束节点的个数平均减少7 9 、4 0 、8 2 、4 1 、5 9 、6 0 。 在候选指令选择过程中，本文提出了基于空间限定算法的候选指令选择方法，加快候选指令的 选择。算法建立以候选指令为顶点的搜索二叉树，通过先判断每个子树能够获得的性能上限，决定 是否搜索当前子树，达到加快搜索的目的。如果当前节点的性能上限已小于或等于目前记录的最优 性能，则整个子树不需要再搜索。子树性能上限的判断是通过先对候选指令按照单位面积性能参数 从大到小排序，因此总能从可选指令集中先选到参数最大的候选指令，当候选指令不能选中时，则 考虑部分选中，虽然不是可行的选择，但可以计算出当前子树能够获得的性能上限。与c l a r k 启发 式贪婪算法相比，本文算法是精确算法，在m p 3 解码中的子带综合示例、m p e g 4 解码中的i d c t 示例、a d p c m 解码示例、m d 5 算法示例、f f t 变换示例和y u v 2 r g b 示例的候选指令选择过程中， 都搜索出了性能更优的指令扩展，并且比完全搜索所有节点平均减少搜索节点数9 7 7 6 。 本文通过在a r me s l 虚拟原型平台上处理器模型运行在6 6 m h z 频率下连续解码2 0 帧m p 3 文 件进行验证。相对于1 6 位a d s p 2 1 9 1 基本处理器模型，扩展为3 2 位处理器模型后解码需要的周期 数减少5 7 9 ，扩展向量乘法特殊指令后，解码需要周期数减少2 7 5 ，此时解码一帧需要2 2 m s ， 满足m p 3 解码实时性要求。m p e g 4 解码应用中针对消耗c p u 资源最大的i d c t 模块扩展指令后， 运行二维8 x 8 的i d c t 需要周期数减少2 0 5 。 关键词；定制处理器，结构描述语言，数据流图、自动指令集扩展 a b s t r a c t a b s t r a c t w i t ht h ee m e r g e n c eo fh i g h - c o m p l e x i t ya p p l i c a t i o n s ，t h eg e n e r a l - p u r p o s ec p uh a sb e e nu n a b l et o m e e tt h ed e m a n d so fc o m p u t e i n t e n s i v ee m b e d d e da p p l i c a t i o n s t oi m p r o v et h ep e r f o r m a n c eb yi n c r e a s i n g t h ef r e q u e n c y t h ep o w e rw i l lb eh i g h a n du s i n ga s i cd e s i g n ，t h ef l e x i b i l i t yw i l lb ed e c l i n e d f o rt a r g e t a p p l i c a t i o n s ，c u s t o m i z a b l ep r o c e s s o r sc a na c c e s st ot h eb e s tb a l a n c ea m o n gp e r f o r m a n c e ，p o w e r c o n s u m p t i o n ，c o s ta n df l e x i b i l i t y t h ei n s t r u c t i o ns e te x t e n s i o n sa n di t sp e r f o r m a n c ee v a l u a t i o na r et h ek e y p r o c e s s e si nt h ed e s i g no fc u s t o m i z a b l ep r o c e s s o r s t h r o u g ha n a l y z i n gt h ea l g o r i t h mo fa p p l i c a t i o n s ，u s i n g m a n u a li n s t r u c t i o ns e te x t e n s i o n sa n de v a l u a t i n gi t sp e r f o r m a n c ea f t e rh a r d w a r ed e s i g ni sf i n i s h e d ，t h e t i m e t o m a r k e tw i l lb et o ol a t e t h ea u t o m a t i ci n s t r u c t i o ns e te x t e n s i o n si n c l u d i n gc a n d i d a t ei n s t r u c t i o n s g e n e r a t i o na n dc a n d i d a t ei n s t r u c t i o n ss e l e c t i o n ，a n da r c h i t e c t u r ed e s c r i p t i o nl a n g u a g em o d e lw h i c hi su s e d t oe v a l u a t et h ep e r f o r m a n c ei nt h ee a r l ys t a g e ，c a na c c e l e r a t et h ed e s i g no fp r o c e s s o r s i nt h i s p a p e r , ac y c l e a c c u r a t eb a s i cp r o c e s s o rm o d e li sb u i l tb a s e do na r c h i t e c t u r ed e s c r i p t i o n l a n g u a g el i s a i ti n c l u d e sm e m o r ys u b m o d e l ，r e s o u r c e ss u b m o d e l ，b e h a v i o rs u b m o d e l ，i n s t r u c t i o ns e t s u b m o d e la n dt i m i n gs u b m o d e l a d s p 2 1 9 1 si n s t r u c t i o ns e ti su s e da sb a s i ci n s t r u c t i o ns e ti n c l u d i n ga l u i n s t r u c t i o n s ，m a ci n s t r u c t i o n s ，s h i f ti n s t r u c t i o n s ，m u l t i f u n c t i o ni n s t r u c t i o n s ，d a t am o v ei n s t r u c t i o n sa n d p r o g r a mf l o wi n s t r u c t i o n s t h e nt h ec y c l e a c c u r a t ee m im o d e la n ds d r a m m o d e la r ed e s i g n e dw h i c hi s e s s e n t i a lf o rb u i l d i n gt h ev i r t u a lp r o t o t y p ep l a t f o r m an e wa l g o r i t h mb a s e do nr e l a t i o nm a t r i xi sp r o p o s e di nt h ep a p e r , w h i c hi sa b l et oa c c e l e r a t e c a n d i d a t ei n s t r u c t i o n sg e n e r a t i o n t h er e l a t i o nm a t r i xr e p r e s e n t st h er e l a t i o n s h i pb e t w e e nt w ov e r t i c e s t h e o r d e rc a nb er e v e r s e df o rt h ev e r t i c e sw h i c hh a v en or e l a t i o n s h i pd u r i n gt h ee s t a b l i s h m e n to fb i n a r ys e a r c h t r e e t h ea l g o r i t h me n s u r e st h a tt h ea s s o c i a t e dn o d e sh a v eb e e nc h e c k e db e f o r ec h e c k i n gt h ec u r r e n tn o d e i fo n eo ft h ea s s o c i a t e dn o d e sd o e sn o tm e e tt h ec o n s t r a i n t sa n dt w ov e r t i c e sd on o th a v er e l a t i o n s h i p ，t h e c u r r e n tn o d ea l s od o e sn o tm e e tt h ec o n s t r a i n t sa n di t ss u b t r e ec a nb ei g n o r e d c o m p a r e dw i t ha t a s u s a l g o r i t h m ，t h es e a r c h i n gn u m b e r o fn o d e sw h i c hd on o tm e e tt h ec o n s t r a i n t si sd e c r e a s e d7 9 、4 0 、8 2 、 4 1 、5 9 、6 0 a v e r a g e l yf o rs u b b a n ds y n t h e s i si nm p 3d e c o d i n g ，i d c ti nm p e g 4d e c o d i n g ，a d p c m d e c o d i n g ，m d 5a l g o r i t h m ，f f ra n dt r a n s f o r m a t i o nf r o m t or g b an e wa l g o r i t h mb a s e do ns p a c el i m i t a t i o na l g o r i t h mi sp r e s e n t e di nt h ep a p e r , w h i c hi sa b l et o a c c e l e r a t ec a n d i d a t ei n s t r u c t i o n ss e l e c t i o n t h eb i n a r ys e a r c ht r e ei sa l s ob u i l ta n dt h ec a n d i d a t e i n s t r u c t i o n sa r eu s e da sv e r t i c e s f o re a c hs u b t r e et h em a x i m u mp e r f o r m a c ei se v a l u a t e df i r s t l y i ft h e m a x i m u mv a l u ei sl e s st h a no re q u a lt ot h er e c o r d e dp e r f o r m a n c ev a l u e ，t h es u b t r e ec a nn o tb es e a r c h e d i n c o n t r a s tt oc l a r k sa l g o r i t h m ，t h ea l g o r i t h mi nt h ep a p e ri se x a c ls ot h em o s to p t i m a li n s t r u c t i o ns e t e x t e n s i o n sc a nb eo b t a i n e d a n dt h es e a r c h i n gn u m b e ro fn o d e si sd e c r e a s e d9 7 7 6 a v e r a g e l yc o m p a r e d w i t hn o tu s i n gs p a c el i m i t a t i o na l g o r i t h mf o rs u b b a n ds y n t h e s i si nm p 3d e c o d i n g ，i d c ti nm p e g 4 d e c o d i n g ，a d p c md e c o d i n g ，m d 5a l g o r i t h m ，h 叩a n dt r a n s f o r m a t i o nf r o my u v t or g b i nt h i sp a p e r , t h ev e r i f i c a t i o ni sc a r d e do u tb yd e c o d i n g2 0f r a m e sa t6 6 m h zf r e q u e n c yf o rm p 3o n a r me s l i nc o n t r a s tt ot h eb a s i c16 b i tp r o c e s s o rm o d e l t h ep e r f o r m a n c ei se n h a n c e d5 7 9 o n3 2 b i t p r o c e s s o rm o d e l a f t e re x t e n d i n gv e c t o rm u l t i p l i c a t i o ni n s t r u c t i o n s t h ep e r f o r m a n c ei se n h a n c e d2 7 5 a n dm e e t st h en e e d so fm p 3d e c o d i n g f o rm p e g 4d e c o d i n g ，i d c ti st h em o s tt i m e - c o n s u m i n gm o d u l e a f t e ra u t o m a t i ci n s t r u c t i o ns e te x t e n s i o n s t h ep e r f o r m a n c ei se n h a n c e d2 0 5 f o rt w o - d i m e n s i o n a l8 x 8 i d c t k e yw o r d s ：c u s t o m i z a b l ep r o c e s s o r s ，a r c h i t e c t u r ed e s c r i p t i o nl a n g u a g e ，a u t o m a t i ci n s t r u c t i o ns e t e x t e n s i o n s ，d a t af l o wg r a p h 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：日期： 2 q d 2 ：2 垒：! 兰 东南大学学位论文使用授权声明 东南人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大 学研究生院办理。 繇她名黪 第一章绪论 1 1 课题研究的背景与意义 第一章绪论 嵌入式系统【l 】【2 】( e m b e d d e ds y s t e m s ) 是以应用为中心，以计算技术为基础，软硬件可裁剪，适 应应用系统对功能、成本、体积、功耗等严格综合性要求的专用计算机系统。嵌入式系统经过十几 年的迅速发展，已从最初的简单应用( 如电子表、电子计算器) 发展到现在具有高数据吞吐量和密 集计算的复杂应用( 如个人多媒体中心、智能手机) 。嵌入式核心处理器也从简单的z 8 0 、8 0 5 1 单片 机发展到如今以3 2 位为主的高性能处理器( 如a r m 、m i p s 、x 8 6 等) 。嵌入式系统可以分为软件 占优和硬件占优两类，在软件占优系统中，整个系统在已有的硬件平台上开发，新功能完全由软件 实现；在硬件占优系统中，整个系统的开发集中在硬件设计。嵌入式系统还可以划分为控制占优系 统( 系统的主要功能是响应外部事件) 、数据占优系统( 系统的主要功能是完成复杂的数据处理，如 信号处理和路由计算) 和混合系统( 系统兼有外部事件的响应处理和数据转换功能，如移动电话和 汽车控制) 。嵌入式处理器是整个嵌入式系统的核心，其性能直接决定整个系统的运行效果，嵌入式 系统的多样性决定了通用处理器不可能满足所有应用的要求。对于控制占优的嵌入式系统，需要处 理器具有很强的灵活性，可以采用常见的精简指令集( r i s c ) 处理器：而对于数据占优的嵌入式系 统，需要处理器具有很强的运算能力，可以采用数字信号处理器( d s p ) 。m o o r e 定律”j 1 4 1 显示集成 电路上可容纳的晶体管数目约每隔1 8 个月增加一倍，性能也将提升一倍。然而s h a n n o n 定律显示算 法复杂度的增长速度远远快于处理器性能的提高速度，例如蜂窝无线标准从1 g 到2 g 再到3 g ，处 理复杂度是按3 阶的级数增长的，如图1 1 所示。目前，主要采用三种方法解决算法复杂度和处理 器性能之间的冲突：在一个嵌入式系统中容纳两个处理器或更多处理器、针对具体的目标应用定制 处理器1 5 1 6 i i 】1 7 】l8 】和专用硬件【9 l | 1 0 1 ( a s i c ) 。两个或多个处理器势必带来功耗增加，功耗如果过大，除 了会缩短电池供电时间外，还会引发系统发热量过大，系统稳定性等问题；专用硬件的最人缺陷是 设计难度大，特别是进入深亚微米f l l 】乃至超深亚微米【1 2 1 时代，互连延迟主导系统性能的问题随着工 艺技术的不断进步变得越来越突出，而且专用硬件缺乏灵活性，需要为不同的系统设计不同硬件。 定制处理器因为其在性能，功耗、灵活性等综合性能上的优势，已得到越来越广泛的应用。 a l g o r i t h m i cc o m p l e x i t yp r o c e s s o rp e r f o r m a n c e 图1 - 1 算法复杂图和摩尔定律 定制处理器以应用为中心，以传统指令集体系结构为设计基础，利用并行处理、添加特定功能 单元和定制存储结构等手段，满足具体应用对功能、成本、功耗、可靠性等多个方面的严格要求。 一1 东南大学博士学位论文 并行处理一般分为三个层次：处理单元级( p r o c e s s i n ge l e m e n t ，p e ) 、指令级和字臆级。在处理单 元级，利用流水线或多个处理单元提高系统性能。在指令级，采用单指令多数据( s i m d ) 1 1 3 1 1 4 、 多指令多数据( m i m d ) 1 1 5 1 1 16 1 ，超长指令字( v l i w ) 1 1 7 1 1 8 1 和超标量( s u p e r s c a l a r ) i i 9 】等方法提 高系统性能。字，位级主要是依赖应用中的数据类型和操作来提高系统性能。添加特定功能单元处理 算法中最占用c p u 资源的部分，可以有效减少c p u 的负担。定制存储结构可以减少处理器访问存 储器的时间。相对于通用处理器【2 ，定制处理器通过专用功能单元完成特定操作，而不是使用标准 部件a l u ，因此具有更高性能和更低功耗；相对于a s i c ，定制处理器具有可复用性和灵活性。如 图1 2 所示，定制处理器的性能、灵活性和功耗介于通用处理器和专用硬件之间，具有较大的设计 空间，与数字信号处理器【2 2 】具有一定的重叠，是因为数字信号处理器也是为特定应用专门设计，在 一定意义上也可以认为是定制处理器。设计人员可以根据目标应用的要求搜索设计空间，寻找性能、 灵活性和功耗等方面都满足条件的最优处理器。事实上定制处理器早在1 9 8 2 年已出现，主要为音频 处理领域的定点信号处理定制，通过引入专用功能部件、多数据块存储结构和定制循环优化单元， 满足f f t 、滤波器等算法对速度的要求。由于受到当时设计方法约束，定制处理器虽然具有巨大优 势，但无法得到广泛使用。 图1 - 2 a s i p 与g p p 、d s p 和a s i c 比较 性能 早期定制处理器设计主要面向嵌入式领域，受工艺限制，当时嵌入式处理器处理能力有限，运 行程序简单，可以完全使用手t 设计。随着嵌入式处理器结构越来越复杂，功耗、成本和性能要求 不断增大，使用传统方法定制处理器越来越凼难。在处理器结构定义之前，需要分析目标应用算法， 根据经验划分软硬件变得越来越吃力；手动编写r t l 代码、软件模拟器代码和工具链代码的工作量 也越来越大，而且使用不同语言设计出的硬件模型和软件工具之间的一致性也无法得到保证。定制 处理器设计正从r t l 语言向结构描述语言和电子系统级转移。结构描述语言和电子系统级设计工具 可以帮助设计者从更高抽象层次设计电路结构，能够协助工程师进行系统级设计、结构定义、算法 开发、软硬件划分和协同技术、建立虚拟原型机和验证不同架构方案的可行性等。结构描述语言模 型中不仅仅可以描述处理器硬件结构信息，同时也可以加入软件工具链信息，使自动生成汇编器、 链接器、模拟器成为可能。采用结构描述语言和电子系统级设计方法可以快速为特定嵌入式系统定 制最优处理器，因此越来越受到众多公司欢迎，如诺基亚研究中心t o m m im a k e l a i n e n 表示电子系统 级设计在诺基亚产品中所占分量比以往任何时候都要大，开发人员不能等到硬件交付之后才开始开 发；三星s o c 研发中心高级副总裁s o o k w a ne o 表示采用更高级的抽象改变原有设计模式来降低成 本。 目前，结构描述语言没有形成通用的标准，世界许多知名高校、处理器设计公司和e d a 工具设 计公司都纷纷推出自己的结构描述语言，如m i m o l a 、i s d l 、c s d l 、l i m e 、e x p r e s s i o n 、l i s a 等。不同的结构语言建立的模型抽象层次有所不同，因此生成的硬件描述语言代码和工具链的高级 语言代码效率也各不相同。抽象层次越高，忽略硬件结构的细节越多，生成的硬件描述语言代码效 率越低，但模型仿真速度越快，迭代设计越方便：抽象层次越低，因为考虑众多的硬件细节，生成 的硬件描述语言的代码效率越高，但模型仿真速度越慢，迭代设计越困难。同一种结构描述语言可 以建立不同抽象层次的模型，指令集模型能够快速模拟处理器的功能，适合软件设计人员早期调试 目标应用程序；周期精确模型能够精确评估处理器运行目标应用的性能，适合硬件工程师评估处理 器的结构。图l 一3 所示，抽象层次越低，模型的体积越大。 2 o 厶o 第一章绪论 抽象层次 图1 3 抽象层次与模型体积关系 模型体积 面对不同的目标应用，扩展指令集是定制处理器设计过程中一个至关重要的环节，定制处理器 能够有效处理目标应用正是通过特殊指令完成的。如图l _ 4 ，传统指令集扩展是设计人员根据具体 应用的特点，统计其在基本处理器上的性能，根据经验在基本处理器中加入新功能单元，获得目标 应用的性能提升，但直接修改r t l 硬件代码，修改汇编器、模拟器等工具链软件代码都是相当复杂 的过程，在r t l 模型上仿真目标应用虽然可以获得详细的硬件运行参数，但速度很慢，并不适合搜 索处理器结构，而且如果最终获得的性能不满足要求，则必须重新扩展指令，但每次指令集扩展都 需要相当长时间，而且针对不同目标应用，算法差异比较大，因此通过研究目标应用算法的特点设 计定制处理器，会影响到处理器的上市时间。为了解决复杂算法的指令集扩展问题，自动指令集扩 展技术应运而生，目的是让设计人员摆脱对目标应用算法的研究，让软件_ t 具根据目标程序的特点， 按照设计者提供的约束条件，如输入输出个数、扩展指令最大个数等，从中自动搜索出满足约束条 件并且适合指令集扩展的模块，再从这些模块中选择出性能提升最人的结构。如t e n s i l i c a 公司的 x t e n s a 系列处理器和a r c 公司的a r c t a n g e n t 系列处理器。设计人员除了可以在x t e n s a 基本处理器 上根据需要配置内部c a c h e 大小、总线位宽、浮点运算单元、d s p 引擎、中断向量等，还可以通过 编译器针对应用扩展全新指令、寄存器和i o 端口，设计全新的针对具体应用的定制处理器。 a r c t a n g e n t 系列处理器是可综合、用户定制的3 2 位处理器，开发人员可以增加扩展指令、配置高 速缓存器、集成外设、利用a r c h i t e c t 配置工具增加d s p 扩展功能。x t e n s a 处理器和a r c t a n g e n t 处理器的自动指令集扩展技术都是基于各自已有的基本处理器和预先定义并高度优化的库模块，每 个库模块都有几种模型形式，c c + + 模型为软件开发提供信息，包含二进制指令、汇编格式以及时 序信息；每个模块还包含可综合的硬件描述语言模型，提供扩展硬件结构的基础。通过分析目标应 用的程序结构，在库模块中匹配，搜索出能够提高性能的模块。 、一 修改目标应用软件代码 目标应用 一 i 目标应用协议 f 代码c c d d l n o 一 赫( r 舰t l ) 器】皇 性能分析，寻找可以进行指令 扩的模块 乞：未达到要求 图1 _ 4 传统的指令集扩展流程 3 东南大学博士学位论文 本文探索了结构描述语言、e s l 工具以及自动指令集扩展算法三者结合快速搜索处理器的结构， 设计出针对目标应用的最优定制处理器的方法，如图1 5 。本文将设计以a d s p 2 1 9 1 指令集作为基 本指令集的l i s a 模型，在a r me s l 评估其性能，深入研究自动指令集扩展算法并且针对不同应用 扩展特殊指令。 e s l 工具 基本处理器 一 自动搜索最有效的 ( a d l )( 扩展指令 存储器资源行为指令集时序 n 模型 模型模型模型模型 修e g a d l 模塑 j l a h b 模型i ie m i d g e i | s 。l 认m 模型 ， 一一毕未达到要求t 图1 5 本文结合a d l 、e s l 和自动指令扩展流程 1 2 论文的主要工作及创新点 使用结构描述语言和电子系统级设计可以在设计之初搜索处理器结构，并评估其性能。自动指 令集扩展算法让设计人员摆脱了对复杂目标应用算法的研究，加快处理器设计周期。本文将探索结 构描述语言、e s l 工具以及自动指令集扩展算法三者结合快速搜索处理器结构的方法，设计出针对 目标应用最佳的定制处理器，因此建立结构描述语言模型、搭建虚拟原型平台和自动指令集扩展算 法研究将成为本文的主要工作。 1 2 1 论文的主要工作 本文以结构描述语言模型和虚拟原型平台为基础，针对目标应用使用自动指令集扩展算法搜索 能够有效提高处理器性能的指令扩展结构。当获得指令扩展结构后，修改处理器模型，在虚拟原型 平台上重新评估性能，确定自动指令集扩展算法的有效性。 以下详细描述本文的结构描述语言模型设计、虚拟原型平台搭建、自动指令集扩展算法研究等 方面的工作： 建立基于l i s a 的周期精确级处理器模型。处理器模型包括存储子模型、资源子模型、行为 子模型、指令集子模型和时序子模型等，其中存储子模型采用哈佛结构、资源子模型定义 处理器能够使用的寄存器、行为子模型模拟真实硬件中各种指令的运行、指令集子模型定 义各种指令的二进制码和汇编格式、时序子模型模拟处理器的流水线结构，特别是跳转指 令带来的流水线变化。 搭建验证处理器性能的虚拟原型平台。虚拟原型平台除了处理器模型外，还需要建立周期 精确的e m i 模型和s d r a m 模型。在对1 6 位基本处理器模型验证时，选择了m p 3 解码程 4 一 第一章绪论 序作为目标应用，通过优化和定点化m p 3 解码程序后，分别在a r m 7 t d m i 处理器模型和 a d s p 2 1 9 1 处理器模型上评估性能，分析1 6 位a d s p 2 1 9 1 处理器模型在完成m p 3 解码中的 缺陷，把1 6 位处理器模型扩展为3 2 位处理器模型，进而分析3 2 位加法指令、3 2 位乘法指 令和3 2 位乘加指令分别对m p 3 解码性能的优化。 自动指令集扩展算法研究。本文研究了自动指令集扩展流程中的主要环节，包括程序转换 成三地址码、三地址码转换成数据流图、候选指令生成和候选指令选择。在候选指令生成 过程中，本文提出了基于关系矩阵的候选指令生成算法，关系矩阵记录了各个顶点之间的 关系，并且充分利用了已判断的节点信息，决定当前节点的子树是否需要继续搜索，从而 减少对不满足约束节点的检查。在候选指令选择过程中，本文提出了基于空间限定算法的 候选指令选择方法，通过判断当前子树能够获得的性能上限，并且与己记录的最优结果比 较，确定当前子树是否需要继续检查，达到减少搜索节点的目的。 1 2 2 本文的创新点 论文的主要创新点体现在： 探索了结构描述语言模型、e s l 工具和自动指令集扩展技术三者结合快速搜索处理器结构 的方法。 早期处理器结构比较简单，大部分采用全手t 设计，但随着目标应用越来越复杂，处理器 结构以及工具链设计也日益复杂，传统定制处理器的设计方法已无法满足要求。本文采用结构 描述语言、e s l 工具和自动指令集扩展算法三者结合探索处理器结构，并且在设计之初评估处 理器性能。文中不仅仅使用结构描述语言l i s a 建立了基本处理器模犁，针对不同目标应用评 估性能，并且在自动指令集扩展过程中提出了新的候选指令生成算法和候选指令选择算法。 提出了基于关系矩阵的候选指令生成算法，加速候选指令生成。 a t a s u 等人提出的算法基于子图枚举方法，算法具有顶点的指数级复杂度，虽然加入了额外 的删减技术，减少搜索节点，但在定义指令有多输出的情况下，该算法的性能变得很差。c l a r k 等人和b i s w a s 等人都使用了贪婪算法，算法虽然快但往往不能获得最优结果。c h o i 等人通过限 制子图深度加快搜索，同样也限制了算法有效性。本文提出基于关系矩阵的候选指令生成算法， 建立所有顶点的关系矩阵，对于没有关系的顶点在生成搜索二叉树的过程中可以互换位置。在 判断当前节点是否满足约束要求时，与其相关的节点都已判断结束，如果其中一个相关节点不 满足约束而且引入的两个顶点无关，则当前节点也不满足约束，其子树可以忽略。实验显示， 使用本文的候选指令生成算法，与a t a s u 算法相比，在搜索满足约束的= 肖点个数相同的情况下， 大大减小了搜索不满足约束节点的个数。在m p 3 解码中的子带综合示例、m p e g 4 解码中的i d c t 示例、a d p c m 解码示例、m d 5 算法示例、开t 变换示例和y u v 2 r g b 示例的候选指令生成过 程中，在定义不同的输出约束条件下，搜索不满足约束节点的个数平均减少7 9 、4 0 、8 2 、 4 1 、5 9 、6 0 。 提出了基于空间限定算法的候选指令选择方法，加快候选指令选择。 候选指令的选择是经典的0 1 背包问题。p a n 等人定义了性价比、执行时间、加速比等启发 函数，使用启发式算法选出候选集合；l e e 等人也提出了一种启发式算法，并且和i l p 算法比 较；c l a r k 等人使用了启发式贪婪算法。启发式算法和贪婪算法虽然速度快但往往不能选择剑最 优的指令扩展。本文提出了基于空间限定算法的候选指令选择方法，算法对候选指令按照单位 面积性能参数从大到小排序，因此在候选指令选择时，总能从可选指令中先选到参数最大的候 选指令，如果当前候选指令不能选中时，可以考虑部分选中的情况，虽然不是可行的选择，但 可以计算出当前子树能够获得的性能上限，如果性能上限小于等于已记录的最优结果，则整个 子树都不需要再搜索。与c l a r k 启发式贪婪算法相比，本文算法是精确算法，在m p 3 解码中的 子带综合示例、m p e g 4 解码中的i d c t 示例、a d p c m 解码示例、m d 5 算法示例、f f f 变换示 例和y u v 2 r g b 示例候选指令选择过程中，都搜索出了性能更优的指令扩展结构，并且比完全 搜索所有节点平均减少搜索节点数9 7 7 6 。 5 东南大学博士学位论文 1 3 论文结构 本文总共包含六个部分，除去本章绪论所介绍的课题研究背景和意义以及论文的主要工作和创 新外，后续各章的内容如下： 第二章归纳和总结了定制处理器设计方法，比较了传统设计方法和基于结构描述语言的设 计方法，介绍了目前出现的主要结构描述语言，分析了各自建立模型的优缺点，以及建立 高层模型评估性能的方法。同时文中还介绍了目前加入自动指令集扩展技术的主要商用处 理器，总结了主要的自动指令集扩展算法。 第三章详细叙述了基于l i s a 的周期精确处理器模型的设计过程，包括存储子模型、资源子 模型、行为子模型和时序子模型等。描述了组成处理器模型的主操作和指令操作树的设计， 主操作中结构段、资源段和行为段的设计，指令操作树中组成段、编码段、语法段、和指 令行为段的设计。 第四章搭建了评估处理器性能的虚拟原型平台，设计除了处理器模型、a h b 总线模型外的 e m i 模型和s d r a m 模型。在对1 6 位基本处理器模型验证时，选择了m p 3 解码程序作为 目标应用，并优化和定点化m p 3 解码程序。分别使用a r m 7 t d m i 处理器模型和a d s p 2 1 9 1 处理器模型验证m p 3 解码算法优化前后的性能，不考虑和考虑读写外部s d r a m 延迟的性 能，以及测试两个处理器是否可以达到实时性。扩展了a d s p 2 1 9 1 模犁为3 2 位处理器模型， 评估了3 2 位加法指令、3 2 位乘法指令和3 2 位乘加指令对m p 3 解码的性能提升。 第五章介绍了自动指令集扩展算法，描述了数据流图的构建方法，提出了基于关系矩阵的 候选指令生成算法和基于空间限定算法的候选指令选择方法。采用本文算法对m p 3 解码中 的子带综合示例、m p e g 4 解码中的i d c t 示例、a d p c m 解码示例、m d 5 算法示例、f f t 变换示例和y u v 2 r g b 示例进行候选指令生成和候选指令选择，并与a t a s u 算法和c l a r k 算 法比较。 最后，对论文进行总结，并对进一步的研究方向进行说明。 6 第一二章定制处理器设计方法综述 2 1 前言 第二章定制处理器设计方法综述 传统定制处理器完全由设计人员手工完成，通常是在基本处理器上运行和分析应用程序，找出 程序中消耗资源最大的代码段，然后根据其特点决定扩展指令。随着算法复杂度的提升，定制处理 器的结构越来越复杂，传统设计方法已无法满足需求，如何缩短产品开发周期成为定制处理器设计 的关键。指令集扩展是定制处理器能够有效处理不同目标应用的主要手段。2 0 世纪八十年代指令集 自动设计问题开始被研究。j p b e n n e a 通过以自动或半自动方式设计指令集来加快程序运行速度、 缩小代码体积，但其所有指令集自动设计方法都面向复杂指令集处理器，并不适合嵌入式处理器。 直到近些年，冈为高清、3 g 等复杂应用的出现，市场对定制处理器需要越来越多样化。此时，定制 处理器的自动指令集扩展技术获得了突飞猛进的发展，出现了像t e n s i l i c ax t e n s a 、a r ca r c t a n g e n t 、 s t m i c r o e l e c t r i c ss t 2 0 0 、m i p sc o r e x t e n d 等结合自动指令集扩展技术的处理器。 2 2 定制处理器设计方法比较 处理器开发是一个相当复杂的过程，可以分为以下4 个阶段： 处理器结构的定义 处理器结构的实现 处理器工具链设计 系统的搭建和验证 硬件结构 定义 硬件开发 ( v h d i j v e r i l o g ) 应用软件开发 ( c a s s e m b l y ) 系统搭建 验证 性能评估 处理器设计时间 图2 1 传统的处理器设计流程 在传统处理器1 2 3 设计过程中，处理器开发的4 个阶段分别由硬件工程师、软件工程师和系统工 程师手工完成，如图2 1 所示，其中涉及多种设计语言：v h d l v e r i l o g ，c ，c + + ，c a s s e m b l y 。采 用传统方法设计处理器是一件非常耗时的事情，无法实现设计空间搜索，因此处理器结构的定义成 为处理器设计中最关键的环节，是后续步骤的基础。首先由设计人员根据经验对具体应用划分软硬 件，决定应用中哪些部分由硬件实现，一般是目标应用中对性能影响最大的部分；其次根据软硬件 划分结果定义指令集；最后实现指令集的硬件结构。根据处理器结构的定义，硬件t 程师采用硬件 描述语言v h d l v e r i l o g 设计处理器，硬件设计采用从顶层到底层逐层描述的设计思想，用一系列分 层次的模块表示极其复杂的电路；软件工程师根据不同要求采用高级语言c ，c + + 设计不同抽象层次 7 固圜圉囝 东南大学博士学位论文 的处理器工具链，如针对程序开发，仅仅需要快速的功能模拟器；而针对性能评估，则需要设计时 钟周期精确的模拟器。软件设计方法是对高级语言程序通过词法分析瞄】i 冽【2 6 1 ，语法分析1 27 1