（计算机系统结构专业论文）分片式处理器上指令调度器的设计与优化.pdf

摘要 摘要 随着半导体技术和计算机体系结构技术的发展，分片式处理器逐渐成为多核 领域的一个发展方向。分片式处理器有效解决和缓解了线延迟、功耗、可扩展性 等现代处理器面临的主要问题。本文研究工作围绕一款典型的分片式处理器 t p a p i 展开。t p a p i 采用了全局控制流和局部数据流相结合的类数据流执行模 型，将程序划分成单入口、多出口的超块结构，超块之间维护控制依赖关系，超 块内部采用数据流驱动的方式执行以开发指令级并行性。这种分片式处理器结构 上的类数据流执行模型对编译器提出了更多的要求，指令调度器作为该处理器编 译系统的重要组成部分，是完成软硬件协同设计提高程序性能的关键。 本文围绕分片式处理器t p a p i ，分析影响指令调度的各种因素，设计并实 现适用于t p a p i 结构的指令调度器，并通过量化分析的方法对指令调度算法进 行改进。 论文的主要研究内容和成果包括以下几个方面：( 1 ) 研究了t p a p i 处理器 结构和程序执行模型，针对t p a p i 的d i s c i 指令集和程序表示方式特点，设计 并实现了t p a p i 处理器的指令调度器。t p a p i 指令调度器采用启发式方法将程 序以超块为单位映射到处理器单元阵列上，在映射时要综合考虑超块内指令级并 行性和硬件资源的利用率之间的关系。( 2 ) 对影响程序执行性能的因素进行量化 分析，包括关键路径、负载平衡、数据局部性、寄存器指令、锚点指令、加权路 径和平均路径、片上网络等，衡量这些参数对程序执行性能的影响( 3 ) 提出了 两种启发式函数的指令调度算法：a v b l o n 和a r b l o n 算法。a v b l o n 算法 将锚点指令( a ) 、加权路径信息( v ) 、负载平衡( b ) 、数据局部性( l ) 、寄存器依赖 ( o ) 、片上网络( n ) 等参数加入到启发式函数中。实验表明，基于a v b l o n 启发 式指令调度器比基于贪心算法的调度器的程序性能提高了2 8 。a r b l o n 算法 通过使用平均路径参数代替加权路径参数解决了必须由程序剖析信息得到加权 路径参数的问题，对程序性能也有显著提升。 本文的研究工作为t p a p i 提供了可用的指令调度器，为处理器开发更多的 指令级并行性提供帮助。实验得到的结果也可以指导编译系统设计者和处理器结 构设计者对编译系统和处理器结构进行进一步优化。 关键词：分片式处理器，类数据流执行模型，指令调度，启发式函数。 a b s t r a c t a b s tr a c t a st h ed e v e l o p m e n to f t h es e m i c o n d u c t o rt e c h n o l o g ya n dc o m p u t e ra r c h i t e c t u r e t e c h n o b g y ，t i l e dp r o c e s s o ra r c h i t e c t u r e ( t p a ) b e c o m e sad i r e c t i o no fm u l t i - c o r e p r o c e s s o r s t i l e dp r o c e s s o re f f e c t i v e l ys o l v e st h ew i r ed e h y , p o w e rc o n s u m p t i o n , s c a l a b i l i t y , a n dm a n yo t h e rp r o b l e m st h a tm o d e r np r o c e s s o r sf a c e t i l e dp r o c e s s o r a r c h i t e c t u r e i m p l e m e n t sag b b a lc o n t r o lf l o wa n dj o c a ld a t a f l o wc o m b i n e d c o m p u t i n gm o d e l ，w h i c hd i v i d e st h ep r o g r a mi n t om a n yh y p e r b l o c k s ah y p e r b b c ki s ap r o g r a ms t r u c t u r eh a v i n gas i n g l ee n t r ya n ds e v e r a le x i t s t h e r ea r ec o n t r o l d e p e n d e n c e sa m o n gh y p e r b l o c k s t oe x p b s i v et h ei n s t r u c t i o nl e v e lp a r a l l e l i s m , w e t a k eo v e rc o n t r o ld e p e n d e n c e sw i t hd a t ad e p e n d e n c ei n s i d et h eh y p e r b b c k a sa n i m p o r t a n tc o m p o n e n to fc o m p i l e rs y s t e m , i n s t r u c t i o ns c h e d u l e r i st h e k e yo f i m p r o v i n gp r o c e d u r ep e r f o r m a n c e t h i s d i s s e r t a t i o nf o c u s e so nd e s i g n i n ga n d i m p l e m e n t i n ga ni n s t r u c t i o ns c h e d u l e rf o rat i l e dp r o c e s s o rt p a p i ，i n c l u d i n gh o w t o m a pi n s t r u c t i o n s o n t ot h ec h i p ，h o wt ou s es o r w a r ea b i l i t i e s t o m a n a g et h e c o m p u t a t i o na n ds t o r a g er e s o u r c e so nt h ec h i p t h em a j o rc o n t r 而u t i o n so f t h i sw o r ka r ea sf o l l o w s ：( 1 ) d e s i g na n di m p l e m e n t a l li n s t r u c t i o ns c h e d u l e rf o rat i l e dp r o c e s s o rt p a - p i t p a - p ii n s t r u c t i o ns c h e d u l e r t a k e sh y p e r b b c ka sau n i ta n dm a p st h eb b c ko n t ot h et p a - p ip r o c e s s o re x e c u t i o n a r m y i tt a k e st p a - ca si n p u t , o u t p u ta s s e m b l yl a n g u a g et p a - s ( 2 ) a n a l y s i ss e v e r a l f a c t o r sw i t hq u a n t i t a t i v ea p p r o a c h t h e s ef a c t o r sc a na f f e c tt h ep e r f o r m a n c eoft h e p r o c e d t u e s w ec a ni m p r o v et h eh e u r i s t i c sf u n c t i o n so fi n s t r u c t i o ns c h e d u l e rw i t ht h e r e s u l t s w et a k ec r i t i c a lp a t h , l o a db a l a n c e ，d a t al o c a l i t mr e g i s t e ri n s t r u c t i o n s ，a n c h o r p o i n ti n s t r u c t i o n s ，w e i g h t e dp a t h , a v e r a g ep a t ha n do n - c h i pn e t w o r ka sa n a l y z e d f a c t o r s ( 3 ) p r o p o s ea ni n s t r u c t i o ns c h e d u l i n ga l g o r i t h mb a s e do nh e u r i s t i c sf u n c t i o n s ， r a i s et w oh e u r i s t i c sf u n c t i o n s ：a v b l o na n da r b l o n ，w et a k ea n c h o rp o i n t i n s t r u c t i o n s ( a ) ，a v e r a g ep a t h ( v ) ，b a db a h n c e 0 3 ) ，d a t al o c a l i t y ( l ) ，r e g i s t e r i n s t r u c t i o n s ( o ) ，o n c h i pn e t w o r k ( n ) a sp a r a m e t e r so f h e u r i s t i c sf u n c t i o n e x p e r i m e n t s s h o wt h a ta v b l o ni n s t r u c t i o ns c h e d u l e ri m p r o v e st h ep e r f o r m a n c e2 8 ，c o m p a r e d w i t hag r e e d yi n s t r u c t i o ns c h e d u l e r t om o d i f y t h ed r a w b a c kt h a ta v b l o n i n s t r u c t i o ns c h e d u l e rn e e d sp r o f i l i n gi n f o r m a t i o n , s o m e t i m e sw eu s ea v e r a g ep a t h i n s t e a dofw e i g h t e dp a t h t h ew o r ki nt h ed i s s e r t a t i o np r o v i d e sa na v a i l a b l ei n s t r u c t i o ns c ，h e d u l e rf o r i i t p a - p i ，w h i c hc a nb eu s e df o r e x p l o d i n gi n s t r u c t i o nl e v e lp a r a l l e l i s m p l u s , e x p e r i m e n tr e s u l t sc a ng u i d ed e s i g n e r so ft h ep r o c e s s o ra n dc o m p i l e rt oi m p r o v et h e c o m p i l e rs y s t e ma n dt h ea r c h i t e c t u r e k e yw o r d s ：t i l e dp r o c e s s o ra r c h i t e c t u r e ，d a t a f l o w - l k e c o m p u t i n gm o d e l , i n s t r u c t i o ns c h e d u l e r , h e u r i s t i cf u n c t i o n s i i i 图目录 图目录 图2 1r a w 处理器结构9 图2 2r a w 编译器结构示意图l0 图2 3w a v e s c a l a r 处理器结构示意图1 2 图2 - 4t r i p s 处理器体系结构1 4 图2 5t - f l e x 的处理器微体系结构1 6 图2 - 61 f i o s 代码示例1 9 图3 1t p a p i 处理器结构图2 4 图3 2t p a p i 程序表示方式2 6 图3 3t p a p i 超块存储方式2 7 图4 1 ij 编译器后端流程3 2 图4 2 耵狐p i 编译器结构3 4 图4 3 超块形成示例图3 5 图4 4t p a c 与t p a s 代码对比3 8 图4 5t p a p i 指令调度器与软硬件方面的关系图3 9 图4 6t p a p i 指令调度器主程序流程图4 l 图4 7s p e cc p u 2 0 0 0 中m o v 指令所占的比例4 5 图4 8s p e cc p u 2 0 0 0m i c r o b e n c h 中m o v 指令所占的比例4 5 图4 - 9 几种软件扇出树算法构造结果4 6 图4 1 0 超块内启发式指令调度算法流程图。4 8 图5 1 基本指令调度算法5 3 图5 2 关键路径优化对程序性能的影响5 4 图5 3 关键路径重计算对程序性能的影响5 5 图5 - 4 负载平衡优化对程序性能的影响5 6 图5 5 存储优化对程序性能的影响5 7 图5 - 6 寄存器优化对程序性能的影响5 8 图5 7 锚点指令优化对程序性能的影响5 9 图5 8 加权指令调度算法示例6 0 图5 - 9 加权路径优化对程序性能的影响6 l 图5 1 0 平均路径优化对程序性能的影响一6 1 v i 图目录 图5 1 1 片上网络管理对程序性能的影响6 3 图5 1 2a v b l o n 指令调度算法与启发式指令调度算法比较6 3 i 表目录 表目录 表3 1t p a p i 片上网络功能及工作原理2 4 表3 2d i s c i 主要指令域介绍2 5 表3 3 高性能超块的特征2 8 表4 1t p a p i 编译前端使用的优化模块3 4 表4 2 超块构造采用的转换和优化模块3 6 表4 3 指令调度器使用的指令参数4 4 表5 1t p a p i 软件模拟器配置5l 表5 2 本实验选取的基准测试程序5 2 i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：显垒礁 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 乩磊口保密( ) 作者签名：遂丝 签字目期：2 刁p s 一2 宫 导师签名： 拉 签字日期：丛_ i ! 二生碍 第1 章绪论 第1 章绪论 1 1 研究背景 1 1 1 分片式处理器体系结构成为众核发展的一种趋势 在过去的几十年中，芯片内的晶体管集成度一直在遵循摩尔定律( m o o r e s l a w ) ，以每1 8 个月翻一番的速度飞速提高。2 0 世纪的最后的2 0 年，超标量处 理器体系结构作为工业界和学术界的主流，随着片上晶体管资源的日益增加，也 以每年5 0 6 0 的速度提升。超标量处理器性能提升主要依赖于工业界和学术界 在两个方面的努力：一方面是通过改进超大规模集成电路制造工艺和优化逻辑电 路的级数来提高处理器时钟频率；另一方面是通过改进编译技术和利用高速增长 的片上晶体管资源来发掘指令级并行度( i n s t r u c t i o n sp e rc y c l e ) ( h e n n e s s y , p a t t e r s o n , 2 0 0 3 ；g a u d i o t , k a n g ，e ta 1 ，2 0 0 5 ) 。然而，进入2 l 世纪后传统的超标量 处理器的两种性能提升方法都走到了尽头0 t 群i _ a d d i - a d d 。指令调度器将前两条指令放置在 同一个执行单元，把后两条指令放置在相邻的一个执行单元，这样可以尽可能将 指令之间通过片上网络传输的数据量减少到最少一个数据传输一跳。图 2 6 ( e ) 显示了一段源程序经过t r i p s 编译器和调度器后产生的汇编代码。如图所 示，指令对消费者指令的执行单元进行编码，而不是传统上指令的操作数，这也 是t r i p s 指令集的特殊之处。 t r i p s 通过超块内数据流驱动来开发指令级并行，编译器生成的超块的质量 决定了程序能够开发的并行性。t r i p s 的超块指只有一个入口、一个或者多个出 口的代码段。为了生成大的超块，以提供更大的调度区域和分摊块检测、提交的 开销，t r i p s 编译器使用了大量的优化技术，包括函数内联、循环展开、循环剥 离等。t r i p s 处理器为了简化硬件结构对超块进行了些限制：超块内最多包含 1 2 8 条指令，最多包含3 2 个寄存器读和寄存器写指令，每条路径最多含有3 2 条 存储器读和存储器写指令。这些条件在一定程度上限制了大超块的生成，但是却 1 8 第2 章相关工作 极大的简化了硬件设计，这是软硬件协同设计带来好处的一个实例。 图2 - 6 t r i p s 代码示例 t r i p s 编译器在构造超块时，要充分考虑超块构造给分支预测器带来的影 响。t r i p s 采用超块内数据流、超块间控制流的执行模型，并对超块进行推测执 行。处理器在执行一个超块时需要分支预测器预测下一个超块的地址，并推测执 行预测超块，以获得多个超块并行执行带来的好处。超块级分支预测器以超块为 单位进行推测，推测失败带来的开销很大，同时超块的多个出口又增加了超块级 推测的难度。所有这些要求编译器设计者在选择基本块时根据一定的策略，以提 高分支预测的准确率。研究表明，通过基于路径频率和出口数的方法可以提高分 支预测的准确率，从而提高整个处理器的性能。 t r i p s 使用谓词执行消除控制转移指令以支持块内指令数据流驱动执行。谓 词生产者指令将谓词作为数据流操作数发送给消费者指令一即源程序中由分 支指令决定的整条路径上的所有指令。谓词执行解决了块内控制转移指令带来的 问题，同时也造成了软件扇出树的问题。t r i p s 编译器将消费者指令的物理地址 1 9 第2 章相关工作 编码到指令码中，由于指令长度的限制，一般每条指令只能加入2 到3 条消费者 指令。对于普通的指令之间的数据依赖关系，这样的编码格式基本可以满足需要。 但是谓词执行后的数据依赖关系使得原来整条路径上的指令全部依赖该谓词。受 到指令编码和片上网络的限制，谓词生产者指令不可能同时将谓词传递给消费者 指令。t r i p s 编译器使用m o v 指令转发解决这个问题。m o v 指令是t r i p s 指 令集中的一类特殊指令，它是专门为了一些生产者指令不能将全部消费者指令编 码进指令而设的转发指令。m o v 指令解决了单条指令需要传输数据过多的问题， 但是过多的m o v 指令会降低块内有效指令的条数，延长关键路径的长度，降低 指令级并行性和程序性能。这些问题需要传统的谓词执行技术上加入一些优化来 解决。 t r i p s 指令调度器负责将编译器生成好的超块转化成机器代码形式映射到 处理器执行单元阵列上。指令调度器在调度过程中，需要注意开发指令级并行性 和减少网络通信之间的矛盾。指令调度器要综合注意软硬件多方面的因素，尽可 能的利用软件固有的并行性和硬件结构的特点，加速程序的并行执行。编译器在 生成超块时，为了减少超块间的数据依赖关系，需要将相互数据依赖较多的指令 集中在一个超块内。指令调度器要将有数据依赖的指令尽可能放置在相同或者相 邻近的执行单元上，这样可以缩短数据传输的距离，减少因数据传输而消耗的时 间和功耗。超块内的有些指令可能还存在天然的数据级并行性，这是t r i p s 开 发数据流并行的驱动力，指令调度器要将这些指令放置在不同的执行单元，以避 免并行执行时产生冲突。指令调度器还要将读写寄存器、存储器输入输出指令等 特殊指令根据硬件的位置加以调整，以减少数据在片上网络上的传输，提高处理 器的效率。 此外，t f l e x 根据其结构特点，为了提高硬件资源的利用率，增加了运行 时的动态调度器，用以动态管理资源分配等。动态调度器根据程序本身固有的并 行性和硬件资源的使用率，为该程序合理分配硬件资源。在程序本身固有并行性 较低的时候减少硬件资源的分配，这样不仅节省硬件资源，程序中的指令在处理 器上的物理距离也更近，可以有效减少网络传输，加快程序执行。在处理器硬件 资源使用率较高的情况下减少硬件资源的分配，对处理器可以减少竞争冲突，提 高有效利用率，对程序来讲虽然减少了分配的硬件资源，但是也减少了冲突的机 会，因此不会降低性能。总之，t f l e x 的动态指令调度器有效的对运行时硬件 资源进行了管理和分配。 2 4 几种分片式处理器指令调度器比较 只有在软件系统和硬件结构之间的分工恰好与体系结构的设计相匹配时，才 2 0 第2 章相关工作 能反映出处理器体系结构的优势。随着体系结构技术的发展，研究人员都不约而 同的把他们的目光转向了分片式处理器，但是选择什么样的编程模型，现在业界 还没有定论。上一节介绍的几款处理器中，r a w 处理器继承自超长指令字结构， 采用控制流计算模型，w a v e s c a l a r 采用基于数据流的计算模型，t r i p s 和t f l e x 采用类数据流的计算模型。 r a w 、w a v e s c a l a r 、t 对p s 和t f l e x 等分片式处理器编译系统中都使用了 超块构造和谓词执行技术。超块构造技术在超长指令字处理器编译器技术中为了 扩大指令调度的范围提出的。编译器通过按照一定的规则合并基本块得到超块， 不同的处理器结构根据硬件特点和执行模型的不同按照不同的规则合并超块。 r a w 结构和超长指令字结构需要特别考虑不同路径上关键路径的平衡， w a v e s c a l a r 结构要特别考虑超块内数据局部性，t r i p s 和t f l e x 要考虑指令级 并行性。r a w 结构的超块作为线程级并行执行，超块规模比较大。t r i p s 因为 硬件结构的原因，对超块增加了额外的限制，超块规模较小。 分片式处理器结构暴露了更多的硬件结构给软件系统，指令调度器就是软件 系统中参与硬件管理的不同，它按照一定的规则将超块映射到硬件资源上。我们 对几种分片式处理器以及与其相关的部分做了一下横向的比较，可以看出，指令 调度器的执行方式和影响因素跟处理器执行模型、硬件结构( 如片上网络) 、编译 系统等都有密切关系。基于控制流的r a w 处理器指令调度器只需按照静态的自 底向上的顺序进行调度，它的执行瓶颈完全依赖于关键路径的长度。基于数据流 的w a v e s c a l a r 处理器更看重数据依赖，它的执行性能依赖于数据局部性和通信 局部性，所以要根据依赖指令的位置进行调度。基于类数据流的t r i p s 和t f l e x 处理器对于州和w a v e s c a l a r 遇到的情况都要考虑，关键路径长度和数据、通 信局部性对处理器性能都有很大的影响，因此，要需要衡量更多的因素，采用更 加复杂的调度方案。w a v e s c a l a r 和t r i p s 的指令调度器都需要对处理器硬件的 拓扑结构和相应代价有非常细致的理解，r a w 结构在指令调度时对这些信息需 求度较低。这是软硬件接口划分带来的区别之一，砘州的指令调度器更加关注 软件并行性带来的性能提升，而w a v e s c a l a r 和t r i p s 需要软硬件协同带来性能 提升。 指令调度器作为分片式处理器开发并行性和管理硬件资源的重要组成部分， 必须具备以下主要能力：首先，它应该具有从划分好的超块中找到指令之间的并 行性和指令之间数据依赖的能力。只有准确的找到并定位指令之间的关系，指令 调度器才能有效的调度指令。其次，应该具有通过合理的指令调度提高程序的执 行性能的能力。分片式处理器的最终目标是提高处理器的性能，能够使程序在更 短的时间内计算出结果。指令调度器需要通过有效的指令调度帮助设计者提高处 2 1 第2 章相关工作 理器的性能。最后，指令调度器应该具有高效分配管理硬件资源的能力，包括计 算资源、存储资源以及片上网络等。不同的分片式处理器管理片上网络的方式也 有所不同，r a w 通过特殊的通信指令管理，w a v e s c a l a r 通过数据流方式编码， t r i p s 通过指令编码。负载平衡是分片式处理器设计的一大目标，只有实现负载 平衡，才能有效提高硬件资源的利用率。这个任务在软件方面主要有指令调度器 完成。 2 s 本章小结 本章首先介绍几种典型的分片式处理器结构：r a w 、w a v e s c a l a r 、t r i p s 和 t f l e x ，对它们的处理器结构、编译系统和指令调度器做了详细的介绍，并对 它们的优缺点做了详细的说明。通过对这些处理器结构和编译系统的分析可以看 出，分片式处理器将计算资源、存储资源等均匀分布在整个芯片上是解决当前处 理器面临的线延迟、功耗等问题的有效途径。编译器在分片式处理器设计中发挥 着很大的作用，处理器依赖编译器开发程序的并行性，分配硬件资源等工作。而 随着处理器对编译器的依赖越来越严重，编译器的设计复杂度和难度也逐渐变 大。如何选择合适的执行模型，划分软硬件之间的关系，使得编译器和体系结构 之间的分工与他们的能力相匹配，从而真正发挥分片式处理器的优势是分片式 处理器设计者面临的问题。 本章还对各种分片式处理器编译器中与硬件相关最紧密的部分指令调 度器进行了分析和比较。通过比较可以发现，指令调度器作为分片式处理器开发 并行性和管理硬件资源的重要组成部分，必须具备以下主要能力：首先，它应该 具有从程序中找到指令之间的并行性和指令之间依赖的能力。只有准确的找到并 定位指令之间的关系，指令调度器才能有效的调度指令。通过合理的指令调度提 高程序的执行性能的能力。分片式处理器的最终目标是提高处理器的性能，能够 使程序在更短的时间内计算出结果，指令调度器可以通过有效的指令调度帮助设 计者提高处理器的性能。最后，指令调度器应该具有高效分配管理硬件资源的能 力，包括计算资源、存储资源以及片上网络等。负载平衡是分片式处理器设计的 一大目标，只有实现负载平衡，才能有效提高硬件资源的利用率。这个任务在软 件方面主要有指令调度器完成。 本文的研究工作将围绕着如何为分片式处理器设计一个同时兼备有效指令 调度和硬件资源管理的指令调度器展开。 第3 章t p a - p i 体系结构概述 第3 章t p a p i 体系结构概述 t p a p i 处理器结构( t i l e dp r o c e s s o ra r c h i t e c t u r e p r o c e s s o rf o ri l p ) 是中国科学 技术大学先进计算机系统结构实验室设计的一款分片式处理器结构。它采用基于 d i s c i 的类数据流执行模型，采用超块作为程序的原子执行结构，支持多层次、 多粒度的程序并行执行。t p a p i 的分片式处理器结构有效解决了线延迟、可扩 展性等问题，将处理器实现细节暴露给上层软件系统，通过软件系统和硬件系统 协同开发指令级并行性。 本章对t p a p i 的处理器体系结构和程序表示方式做简单的介绍。 3 1t p a p i 处理器体系结构 t p a p i 处理器结构是一款基于e d g e 执行模型的分片式处理器结构，它充 分利用分片式处理器的优点，将计算资源、存储资源等以t i l e 为单位均匀分布在 整个芯片上，避免使用集中式的控制逻辑等硬件结构，从而克服线延迟等硬件设 计的困难。t p a p i 处理器充分利用分布式的计算资源，为执行串行程序提供巨 大的计算窗口和发射宽度，从而利用硬件资源开发程序的指令级并行性。本节简 要介绍t p a p i 处理器的总体结构和指令集系统。 3 1 1t p a - p i 处理器总体结构 t p a p i 处理器结构如图3 1 所示，处理器上共有1 6 个计算单元( c o r et i l e ) 通过一个二维m e s h 网络连接，每个计算单元包括四个单发射的执行单元、一个 寄存器文件、一个指令c a c h e 和数据c a c h e 、一个存储控制单元、一个逻辑控制 单元和一个控制片上网络的路由器。 t p a p i 处理器将硬件模块分布化，避免出现传统处理器中的一些集中式部 件。计算单元中的指令和数据c a c h e 、寄存器文件分别是整个处理器全局c a c h e 和全局寄存器文件的一部分。t p a p i 的计算单元包括4 个整型和浮点计算部件， 共有1 2 8 ( 4 3 2 ) 个指令槽，从功能上相当于一个简单的4 发射的处理器核，每个 处理器核负责自身对应的指令队列的计算。每个计算单元包含1 2 8 个整型和浮点 型通用的寄存器，用于存放超块之间的数据。超块内部的临时数据不需要存储在 寄存器中，而是在片上网络上通过显式的数据流编码直接传输。寄存器读写指令 保存在寄存器文件的访问队列里，用于访问寄存器文件，并将读取的数据通过片 上网络传输给消费者指令。计算单元的指令c a c h e 存放将要映射到本计算单元的 指令块，共包括块头和指令块两部分。其中块头用于快速获取指令块的信息，比 第3 章t p a - p i 体系结构概述 如指令块数目、跳转出口个数、访存操作个数等。每个计算单元都有一个独立的 控制逻辑，用于对计算单元内部的指令进行管理控制，并配合全局控制逻辑，对 超块的预测、取指、检测、提交等操作进行管理。 t p a p i 处理器 c o r et i l e 逻辑视图 图3 1t p a - p i 处理器结构图 表3 1t p a - p i 片上网络功能及工作原理 网络名称 网络功能工作原理 o p n 网络指令之间或者指令与寄存 一个4 * 4 的二维m e s h 网络，由计算单元之间 器、c a c h e 之间传输操作数的物理连线和计算单元内部的路由节点组 成，相邻节点的传输延迟为一个时钟周期， 数据采用控制包先于数据包一拍的方式以 y - x 路由策略传输，数据包经由一个或者多 个节点转发后到达目的节点。 g d n 网络传输指令到执行单元或者覆盖整个处理器核，收到控制模块的取值命 寄存器模块上( 访问寄存器令后用于将指令传输到执行单元和寄存器模 指令) 块上。 g r n 网络重填c a c h e 用于全局控制模块和指令c a c h e 之间传输重 填命令，进行指令c a c h e 的缺失管理 g c n 网络在控制逻辑的命令传输到一个执行完成的超块到达队头时发出提交指 寄存器阵列、数据c a c h e 及 令；在执行时发生异常情况需要取消整个指 执行单元上 令窗口时，对c a c h e ，寄存器、执行单元等 部件的刷新进行管理。 g s n 网络指令c a c h e 、数据c a c h e 、 指令c a c h e 重填完成、寄存器或数据c a c h e 寄存器模块向控制逻辑报 的数据全部到达等情况发生时，向控制逻辑 告状态 报告状态，控制逻辑收到状态报告后进行下 一步操作。 2 4 第3 章t p a - p i 体系结构概述 t p a p i 处理器采用复杂的类数据流执行模型，采用分布式的计算、存储和 控制逻辑，特别是采用块内指令之间通过指令编码直接进行通信，需要功能多样 的高速片上网络的支持，本文将t p a p i 的片上网络功能及工作原理总结成一张 表，如表3 1 所示： t p a p i 充分利用了分布化和模块化带来的好处。计算单元由模块化的功能 部件组成，重复使用的模块化部件有效降低了硬件设计和验证的复杂度和处理器 设计周期。计算单元和存储资源均匀分布在整个芯片上，计算单元的直径和计算 单元之间的网络连接的长度小于一个时钟周期内信号可达的距离，消除了线延迟 和时钟周期带来的限制。分布多体的存储方案提供多端口高带宽的存储访问系 统，计算资源与存储资源分布在一起，大大降低了存储器访问的延迟，有效解决 和缓解了存储器墙的问题。 3 1 2d i s c i 指令集系统 表3 - 2d i s c i 主要指令域介绍 指令域位数功能 操作码 7 b i t 用于条独立指令或者一组指令的操作码，其中共享操作码的指令 必须包含扩展操作码。 目标域9 b i t 编码消费者指令的位置，其中4 位用于编码计算单元阵列的位置， 3 位用于编码指令在指令槽中的位置，l 位用于编码目标是指令的 哪一个操作数( o p 0 或者o p l ) 。 谓词域l b i t 用于指明该指令的执行是否需要谓词，当谓词域为1 时，不但所有 源操作数都到达，而且要谓词为真时才能发射执行。 l s i d5 b i t 记录访存操作在原程序中的位置，标识l o a d s t o r e 队列入口，保证 存储语义的串行性，每个超块最多可以包含3 2 条l o a d s t o r e 指令。 e x i d 3 b i t 每个分支指令含有一个e x i t 号，用于区别不同的出口；每个超块中 可以有任意数目的出口，但只有8 个e x i ti d ，不同的出口可以共 享同个e x i ti d 。 寄存器域 5 b i t 寄存器读写指令中通用寄存器编号，读写寄存器必须位于同一个 b a n k ，每个b a n k 含有3 2 个通用寄存器 常数域 1 6 b i t 用于编码常数值，对于不同的指令，该值可以被看做是无符号的或 者有符号的 t p a p i 的指令集系统d i s c i 继承了e d g e 指令集体系结构的优势与特 点，综合硬件动态执1 2 j “b r 力和编译器静态分析能力来提高程序的并行性。本节简 第3 章t p a - p i 体系结构概述 单介绍一下d i s c i 指令集系统及其特点和优势。 d i s c i 指令集是定长的r i s c 指令集，一般每条指令长度为3 2 位( 寄存器读 写指令的长度分别为2 2 位和6 位) ，共包含8 种指令格式：一般指令、访存指令、 寄存器读指令、寄存器写指令、比较指令、分支指令、常数指令和数据传递指令。 其中寄存器写指令只需要编码目标寄存器，而寄存器读指令不仅要编码源寄存 器，还要编码目标指令的地址，因此寄存器读指令和寄存器写指令分为两类。 d i s c i 指令集采用了块原子执行和显式数据流通信的执行模型，除了传统的操 作码、操作数等指令域，还具有许多与c i s c 和r i s c 不同的指令域，表3 2 简 要介绍了各个指令域。 与传统的r i s c 和c i s c 指令集不同，d i s c i 指令集中的指令不对操作数进 行编码，而是对消费者指令的位置进行编码。这种编码方式使编译器将程序中的 数据依赖的关系通过指令编码的方式显式的传递给硬件结构，使编译器可以通过 指令编码的方式对处理器片上网络进行管理，节省了硬件动态发掘并行性和管理 片上网络的集中式部件，加强了软硬件之间的协作关系。 3 2t p a p i 程序表示方式 ( a ) 源程序 ( b ) 两层程序表示：超 块为币化的控制流i ! f i + 硒 部数据流圈 图3 2t p a p i 程序表示方式 ( c ) 超块内部的局 ；| ：数据流陶盎硬件 l 映射 t p a p i 采用了新型的分片式处理器结构，其处理器结构与传统的结构有很 大的不同。为了适应这种结构，t p a - p i 基于一种新的指令集体系结构_ e d g e ， 设计出与传统指令集风格迥异的d i s c i 指令集。另外，t p a p i 的程序表示方式 也与传统的程序表示方式不同，它打破了控制流程序由程序计数器决定指令执行 顺序的传统，将程序划分成若干个指令块，超块之间保留串行程序的控制依赖关 2 6 第3 章t p a - p i 体系结构概述 系，超块内部表示成数据流的形式。图3 2 中，( a ) 为原来的串行程序，( b ) q h 将 原来的串行程序划分成超块，超块之间的虚线表示控制依赖关系，超块内部的实 线表示数据流依赖关系，( c ) 中将超块按照一定的规则映射到硬件结构上。由图 3 - 2 可以看出，超块在t p a p i 程序表示中占有很重要的地位，下面对t p a p i 处 理器中的超块的特性做一些介绍。 3 2 1 t p a p i 处理器中的超块 类数据流执行模型以指令块为原子单位执行，t p a p i 的指令块是超块( h y p e r b b c k ) 。超块是将若干个基本块组合在一起形成的单入口、多出口的指令序列。 t p a - p i 的超块只能有一个出口，超块的执行必须从这个入口开始。超块可以有 多个出口，每个出口对应一个后继模块，这些后继模块可以相同，也可以互不相 同。超块没有出口数目的限制，但每个出口对应一个出口号，每个超块最多有8 个出口号，因此可能存在多个出口对应一个出口号的情况。每个出口号对应一个 超块级分支预测器，当多个出口对应一个出口号时，会降低分支预测器的准确率。 超块在t p a p i 处理器上以数据流驱动的方式执行，因此不允许超块内部出现控 制转移指令。有两种情况会出现控制转移指令，一种是条件分支结构，另一种是 循环结构。一般通过循环展开或者循环剥离的方式解决超块内部的循环结构，通 过谓词执行解决超块内部的条件分支结构。 程序计数器 块头 指令片1 指令片2 图3 3t p a - p i 超块存储方式 在控制流执行模型中，当程序计数器指向程序的返回指令时，整个程序执行 结束。数据流执行模型中没有程序计数器，如何判断超块是否执行完毕是t p a p i 处理器的一个难点。超块对程序上下文的改变是通过输出指令( 包括寄存器输出、 存储器输出和分支指令) 实现的，t p a - p i 要求编译器生成的超块中每条出e l 路径 2 7 第3 章t p a - p i 体系结构概述 都具有相同数目的输出，通过检测已经完成的输出指令的个数来确定超块是否执 行完毕。编译器在构建超块时会将不同路径添加到同一个超块中，不同路径上的 输出指令很可能不一样。超块执行时若干条不同的路径中只有一条会执行。编译 器通过添加w r i t en u l l i f i c a t i o n 和s t o r en u l l i f i c a t i o n 两条特殊指令来保证每条路径 上的输出指令个数一致。w r i t en u l l i f i c a t i o n 和s t o r en u l l i f i c a t i o n 不会对寄存器文件 和c a c h e 产生任何效果，去可以让控制逻辑认为超块执行了寄存器和存储器输出 指令。 超块是t p a p i 程序中可寻址的最小单位，它由一个块头和若干个指令片组 成，如图3 3 所示。块头中包含指令片的数目、输出指令的数目、分支预测的相 关信息、异常处理相关信息等与超块执行的相关信息，以及该超块的寄存器读写 指令。超块内的指令片数目由超块内指令数目和占用计算分片单元数目决定。 表