（计算机系统结构专业论文）分片式流处理器体系结构.pdf

摘要 摘要 纳米工艺所带来的功耗、线延迟和设计复杂度等问题制约了处理器体系结构 的发展，分片式结构设计是解决这些问题的一种方法。分片式流处理器作为一种 面向数据密集型应用的处理器结构，可以利用摩尔定律的发展带来的丰富而廉价 的晶体管资源，实现处理器结构的可扩展。分片式结构设计的基本思想是将计算、 存储和互连资源组织成片式的基本结构单元，这些片式单元是相对简单的、分布 式控制且可重用的；大量的片式单元由高能效、可扩展的片上网络连接起来。分 片式流处理器的性能是否也具有可扩展性依赖于其支持的编程模型、片上存储层 次、片上互连网络以及计算模型。本文分别从分片式流处理器的计算模型、指令 系统、体系结构、流编程模型映射四个方面开展研究。主要研究内容和成果包括 以下四个部分。 ( 1 ) 研究了类数据流计算模型的原理，提出了一种适合组织分片式流处理 器中计算资源的单块多数据( s i n g l eb l o c km u l t id a t a ，s b m d ) 计算模型，设计 了支持此计算模型的指令系统d i s c d 。s b m d 指在一个超块内部处理多份数据， 每份数据根据自己对应的数据流依赖关系执行。谓词技术把程序中每份数据所对 应的控制流依赖转化为数据流依赖，在超块内部消除控制流转移，这样每份数据 可以按照不同的控制流路径执行。s b m d 模型支持程序中循环体间显式的消息传 递。 ( 2 ) 设计了一种分片式流处理器体系结构t p a p d 。t p a p d 采用类数据流 驱动的计算模型来组织计算资源，使用软件管理的片上存储层次开发应用中的数 据局部性。t p a p d 采用分片式的设计思想，使用多个片上互连网络把片上的各 种资源互连起来。 ( 3 ) 设计并实现了流编程模型在t p a p d 上的映射。t p a p d 支持流编程模 型s t r e a m c k e m e l c 。s t r e a m c k e m e l c 是为i m a g i n e 流处理器开发的，为了能在 t p d p d 上运行s t r e a m c k e m e l c 语言编写的代码，我们实现了流级翻译器和 k e r n e l 级二进制翻译器，把在i m a g i n e 平台上的流级指令信息和k e r n e l 级微码翻 译到t p a p d 平台上，翻译后的代码膨胀率小于2 。 ( 4 ) 实现了t p a p d 的软件模拟环境，并评估了类数据流驱动计算模型及 t p a p d 体系结构设计的有效性。文章讨论了物理块资源、计算资源、网络资源 的可扩展性，分析了流访存部件的参数设置，提出了优化单个超块执行时间的机 制，研究了指令调度算法对程序性能的影响。通过在模拟器上做实验，我们发现 t p a p d 在结构可扩展的同时，性能上超过集中控制计算资源的流处理器。 摘要 关键词：分片式流处理器体系结构类数据流计算模型s b m d 二进制翻译 i i a b s 西r a c t a b s t r a c t t h ed e v e l o p m e n to ft r a d i t i o n a lp r o c e s s o ra r c h i t e c t u r e i sr e s t r i c t e db ym a n y p r o b l e m sa r o s ei nn a n o m e t e rt e c h n o l o g yd e s i g n s ，s u c ha sp o w e rd i s s i p a t i o n ，w i r e d e l a y ，d e s i g nc o m p l e x i t y ，e r e t i l e dp r o c e s s o ra r c h i t e c t u r ei sap o t e n t i a ls o l u t i o nt o t h e s ec h a l l e n g e s t i l es t r e a mp r o c e s s o ri sa na r c h i t e c u t e rf o r c o m p u t e i n t e n s i v e a p p l i c a t i o n t i l es t r e a mp r o c e s s o rc a l lu t i l i z ep l e n t i f u lb u tc h e a pt r a n s i s t o rr e s o u r c e s i n t r o d u c e db ym o o r e sl a wa n db e c o m es c a l a b l e t i l e dd e s i g nm e t h o do r g a n i z e s c o m p u t a t i o n ，s t o r a g ea n di n t e r c o n n e c t sr e s o u r c e si n t ob a s i ct i l e da r c h i t e c t u r a lu n i t s ， w h i c ha r er e l a t i v e l ys i m p l e ，d i s t r i b u t e da n dr e u s a b l e ah i g h p r o d u c t i v i t yp r o c e s s o r c a nb ec o m p o s e do fp l e n t yo fs u c ht i l e du n i t s ，i n t e r c o n n e c t e db yh i g h l ye f f i c i e n ta n d s c a l a b l eo n - c h i pn e t w o r k s t h ep e r f o r m a n c eo ft i l e ds t r e a mp r o c e s s o ri sd e t e r m i n e d b yp r o g r a m m i n gm o d e l ，m e m o r yh i e r a r c h y ，n o c ( n e t w o r o n - c h i p ) a n dc o m p u t a t i o n m o d e l c o m p u t a t i o nm o d e l ，i n s t r u c t i o ns e t ，a r c h i t e c t u r ea n dm a p p i n go fs t r e a m p r o g r a m m i n gm o d e la r es t u d i e di nt h j sd i s s e r t a t i o n t h em a j o rr e s e a r c hc o n t r i b u t i o n s i n c l u d e ： ( 1 ) b a s e do nt h e o r yo fd a t a f l o w - l i k ec o m p u t a t i o nm o d e l s i n g l eb l o c km u l t i d a t a ( s b m d ) c o m p u t a t i o nm o d e li sp r o p o s e dw h i c hi su s e dt oo r g a n i z ec o m u p a t a t i o n r e s o u r c eo ft i l e ds t r e a mp r o c e s s o r a ni n s t r u c t i o ns e tw h i c hs u p p o r t sd a t a f l o w - l i k e d r i v e nc o m p u t a t i o nm o d e li sd e s i g n e d s b m di n d i c a t e sp r o c e s s i n gm u l t id a t ai na s u p e r - b l o c ki nw h i c he a c hd a t ac a nb ep r o c e s s e da c c o r d i n gt oi t sd a t af l o w d e p e n d e n c e c o n t r o lf l o wd e p e n d e n c eo fe a c hd a t ac a nb ec o n v e r t e di n t od a t af l o w d e p e n d e n c eb yp r e d i c t e de x e c u t i o nw h i c he l i m a t e st r a n s f e ro fc o n t r o lf l o w t h u s ， e a c hd a t ac a nb ep r o c e s s e di nd i f f e r e n tc o n t r o lf l o wp a t h e x p l i c i tm e s s a g ep a s s i n gi s s u p p o r t e d i ns b m dm o d e lb e t w e e n l o o p si np r o g r a m ( 2 ) ad a t a f l o w - l i k ed r i v e na r c h i t e c t u r ef o rt i l e ds t r e a mp r o c e s s o rc a l l e dt p a p d i sd e s i g n e d ad a t a f l o wd r i v e n c o m p u t a t i o nm o d e li se m p l o y e df o ro r g i n z i n g c o m p u t a t i o n a lr e s o u r c e t om a k eu s eo fd a t a l o c a l i t y o f a p p l i c a t i o n s s o f t w a r e m a n a g em e m o r yh i e r a r c h yi su s e d t h et i l e dm e t h o di sa p p l i e dt ot p a p d i nw h i c hs e v e r a ln e t w o r k so nc h i pa r eu s e dt oc o n n e c tv a r i o u sr e s o u r c e s ( 3 ) m a p p i n go fs t r e a mp r o g r a m m i n gm o d e li sd e s i g n e da n di m p l e m e n t e do n t p a p d t h es t r e a m c k e r n e l ci sat w o - l e v e lp r o g r a m m i n gl a n g u a g e ，w h i c hi s s t r e a mp r o g r a m m i n gm o d e lo ft p a p d s t r e a m c k e m e l ci s d e v e l o p e df o ri m a g i n e i i i a b s t r a c t p r o c e s s o r i no r d e rt o r u ns t r e a m c k e m e l cp r o g r a mo nt p a - p d ，s t r e a ml e v e l t r a n s l a t o ra n db i n a r yt r a n s l a t o ro fk e r n e l l e v e la r ei m p l e m e n t e d t h ei n f o ro fs t r e a m l e v e li n s t r u c t i o na n db i n a r ym i c r o c o d eo fk e r n e ll e v e lo ni m a g i n ep l a t f o r ma r e t r a n s l a t e db yt w ol e v e lt r a n s l a t o rs e p e r a t e l y c o d es i z eo ft p a - p de x p a n d sl e s st h a n2 t i m e si na v e r a g e ( 4 ) e x p e r i m e n t a lp l a t f o r mo ft p a p di si m p l e m e n t e d t h ee f f e c t i v e n e s so f d a t a f l o w - l i k ec o m p u t a t i o nm o d e la n da r c h i t e c t u r a ld e s i g ni se v a l u a t e d t h es c a l a b i l i t y o fp h y s i c a lb l o c kr e s o u r c e ，c o m p u t a t i o n a lr e s o u r c e ，n e t w o r kr e s o u r c ei sd i s c u s s e d t h ep a r a m e t e rs e x i n go fs t r e a ml o a d s t o r eu n i ti sa n a l y z e d t h em e c h a n i s mo f o p t i m i z i n ge x e c u t i o nt i m ef o rs i n g l es u p e r b l o c ki sp r o p s e d t h es c h e d u l ea l g o r i t h m o fi n s t r u c t i o n si ss t u d i e dt oa c c e l e r a t ep e r f o r m a n c e t h r o u g he x p e r i m e n to ns i m u l a t o r ， i ti sf o u n dt h a tn o to n l ya r c h i t e c t u r eo ft p a - p di ss c a l a b l e ，b u ta l s op e r f o r m a n c eo f t p a - p de x c e e d ss t r e a mp r o c e s s o ri nw h i c hc o m p u t a t i o n a lr e s o u r c ei sc e n t r a l i z e d c o n t r o l l e d k e y w o r d s ：t i l e d ，s t r e a mp r o c e s s o ra r c h i t e c t u r e ，c o m p u t a t i o nm o d e lo fd a t a f l o w - l i k e d r i v e n ，s b i v i d ，b i n a r yt r a n s l a t o r ， i v 图目录 图目录 图1 1 超块举例5 图1 2 流编程模型举例8 图2 1i m a g i n e 处理器的结构图1 1 图2 2s p is t o r m 处理器的结构图1 3 图2 3c e l l 处理器的结构图1 4 图2 49 8 0 0 g t x 处理器的结构图1 7 图2 5c u d a 程序的组织1 7 图2 6g p u 上线程映射18 图2 7t r i p s 处理器的结构一1 9 图2 8t f l e x 的动态配置方式2 0 图2 9r a w 处理器的结构图2 1 图2 1 0t i l e 6 4 处理器的结构图2 2 图2 1 lt i l e 6 4 处理器上程序映射2 3 图2 1 2t i l e 6 4 支持的、混合的存储模型2 3 图2 1 3p o l a r i s 处理器的结构图2 4 图2 1 4l a r r a b e e 处理器的结构图2 5 图3 1 程序执行模型2 8 图3 2 循环体间交换数据的例子3 5 图3 3 程序源码和b l o c k 0 在s b m d 模型下的指令3 6 图3 4s b m d 模型下b l o c k l 的指令3 7 图3 5s b m d 模型下的数据流图和控制流3 8 图3 6 超块结构图3 9 图3 7 流指令长度4 0 图3 8t p a p d 的k e r n e l 级指令4 3 图3 9 指令的目标域4 4 图4 1t p a p d 的结构图4 5 图4 2c t 的结构图4 6 图4 3 主机接口4 7 图4 4 块执行的状态转化4 9 图目录 图4 5e t 的结构图4 9 图4 6e t 的流水线阶段图5 4 图4 7r t 的结构图5 5 图4 8i t 的结构图5 6 图4 9i t 中指令发射部件的状态机5 7 图4 1 0d t 的结构图5 8 图4 1 1m t 的结构图5 9 图4 1 2 写入流和读出流6 0 图4 1 3 条件流的硬件结构6 4 图4 1 4s u 的结构图6 5 图4 1 5b a n k 的结构图6 6 图4 1 6o t nr o u t e r 的结构图6 7 图4 17i d n 6 9 图4 18g c n 7 0 图4 1 9g s n 7 1 图5 1t p a p d 的编译框架7 3 图5 2i m a g i n e 中c l u s t e r 的结构7 6 图5 3 循环间迭代依赖8 0 图5 4 条件流输入、输出在i m a g i n e 处理器和t p a - p d 上软件实现的比较8 1 图5 5t p a p d 和i m a g i n e 的计算单元间对比8 2 图6 1 应用中指令分布图9 2 图6 2 支持多个超块并行执行的物理块资源。9 4 图6 3 不同物理块个数的加速比9 5 图6 4 应用在不同e t 规模下的加速比9 6 图6 5 应用在e t 内部不同的发射宽度下的加速比9 6 图6 6 操作数传递网络( o t n ) 的网络拓扑图9 7 图6 7 应用在不同结构的操作数传递网络条件下的性能9 8 图6 8 操作数网络和e t 个数间的关系。9 9 图6 9 操作数网络和物理块个数间的关系1 0 0 图6 1 0 地址产生器不同发射宽度的影响。1 0 1 图6 1 l 不同访存调度算法的影响1 0 1 图6 1 2 操作数早于指令到达的情况1 0 3 x 图目录 图6 1 3 将超块的指令发射、指令执行并行所带来的加速1 0 3 图6 1 4 超块内写操作不等待情况下的加速比1 0 4 图6 。1 5k s a l 和k s a 2 两种算法的对比1 0 5 图6 1 6 网络延迟系数对性能的影响1 0 5 图6 1 7t a p p d 和i m a g i n e 性能对比图1 0 7 图6 1 8k e r n e l 微码的代码膨胀率1 0 8 图6 1 9t p a p d 的扩展图1 0 9 x 1 表目录 表目录 表2 1g p u 的存储层次1 9 表2 2 多款处理器对比2 7 表3 1s t r e a m c 语言的基本类型2 9 表3 2s t r e a m c 语言的语法2 9 表3 3 流级指令可见的寄存器4 0 表4 1e t 的指令列表5 0 表4 2 流描述寄存器( s c r ) 5 9 表4 3 输入流的s b 状态位6 2 表4 4 读出流的s b 状态位6 3 表4 5 内存系统控制寄存器( m s c r ) 6 5 表4 6o t n 包的格式6 7 表4 7d n 包的格式6 9 表4 8g c n 包的格式7 0 表5 1 流级指令信息7 5 表6 1 模拟器部分函数列表8 9 表6 2b e n c h m a r k 说明9 2 表6 - 3k e r n e l 函数中块内及块间依赖特征9 3 表6 4d r a m 调度策略1 0 1 表6 5t p a p d 的模拟器参数配置1 0 6 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 d 公开口保密( 年) 作者签名：邀 签字日期： 西乜：茎：递 导师签名： 签字日期：丛j 叟：堇：圣墨 第1 章绪论 第1 章绪论 1 1 研究背景 1 1 1 半导体工艺的发展 半导体工业在过去几十年中不断使用新的工艺，使得片上集成的晶体管数目 按照摩尔定律每十八个月翻一番。根据2 0 0 8 年国际半导体技术发展路线图 ( i t r s ) 预测到2 0 2 0 年后，片上可集成超过2 0 0 多亿个晶体管。b i l ld a l l y 在s c 0 9 上预测2 0 1 7 的g p u 片上可以集成7 2 0 0 个f p u 。如何利用这些不断增长的晶体 管资源来提高处理器性能一直是工业界和学术界的共同目标。 2 0 世纪8 0 年代以后，处理器性能提升主要来自于提高处理器主频和多条指 令并行执行，x 8 6 和r i s c 处理器从1 9 8 6 到2 0 0 2 年间，性能每年平均提高5 2 。 从2 0 0 2 年以后，x 8 6 和r i s c 处理器每年性能提高不到2 0 ( a s a n o v i ce t a l 2 0 0 6 ) ， 这说明随着工艺的发展，提高主频以及单核复杂度的处理器设计方法遇到了性能 增长的瓶颈。在纳米工艺条件下，处理器设计者面临功耗墙( p o w e rw a l l ) 、线 延迟( w i r ed e l a y ) 、存储墙( m e m o r yw a l l ) 和i l p 墙( i l pw a l l ) ，这几个问题 导致采用传统超标量结构的单核处理器难以继续扩展单核的性能。2 0 0 5 年计算 机工业发生了历史性的方向转变，几乎所有的微处理器芯片公司都宣布它们未来 的产品将采用片上多处理器( c h i pm u l t i p r o c e s s o r s ，c m p ) 结构。 1 1 2 流处理器体系结构的发展 从1 9 9 8 年学术界提出流处理器( r i x n e re ta 1 1 9 9 8 ) 以来，工业界及学术界 提出了多种流处理器体系结构。流处理器( k h a i l a n yb r u c e ke ta 1 2 0 0 1 ) 最初提 出的目标是利用片上不断增长的晶体管资源，开发多媒体及信号处理应用的多级 并行性。在结构上，流处理器使用软件管理的片上存储层次捕获应用中数据局部 性。按照体系结构来分，流处理器大致可以分为五种，它们分别以i m a g i n e 、c e l l ( h eh o f s t e ee ta 1 2 0 0 5 ) 、r a w ( t a y l o re ta 1 2 0 0 2 ) 、n v i d i a 支持c u d a 的 g p u ( l i n d h o l mee ta 1 2 0 0 8 ) 、a m d 的流处理器为代表。以i m a g i n e 的体系结 构为基础而发展来的流处理器包括m e r r i m a c ( e r e zm e ta 1 2 0 0 7 ) 、s t o r m 、f t 6 4 ( y a n gx u e j u ne ta l ，2 0 0 8 ) 、m a s a ( w e nm e ie ta 1 2 0 0 4 ) 。 以上各种流处理器都采用控制流计算模型来开发指令级并行性( i n s t r u c t i o n l e v e lp a r a l l e l i s m ，i l p ) ，i m a g i n e 处理器依靠v l i w 组织指令，完全依赖编译器 开发i l p 。c e l l 处理器中单个s p e 、支持c u d a 的g p u 在单个s m 内、a m d 的 流处理器硬件上都使用记分板结构开发i l p 。记分板结构结构简单，但如果以开 第1 章绪论 发应用中的i l p 为目的，其功耗、可扩展性方面不适合组织大量的计算资源。以 i m a g i n e 为代表的一类流处理器使用集中式的结构组织计算资源，在计算簇内部 使用v l i w 开发i l p ，在簇间依靠s i m d 开发d l p ( d a t al e v e lp a r a l l e l i s m ，d l p ) 。 为了支持s i m d ，在结构上v l l w 解码后的控制信号需要跨越多个计算簇，计算 簇间使用的交叉开关来通讯。这种集中式的结构一方面限制了计算资源对应用中 的不规则控制流及不规则通讯的适应性，另一方面结构的线延迟可扩展性差。 现有的流处理器大部分核数较少，其单核结构较为复杂。支持c u d a 的g p u 虽然有几百个小核，但是核间不支持直接通讯，限制结构了对不规则应用的适应 性。所以面向未来工艺，研究支持规则及不规则应用、结构和性能高度可扩展的 流处理器体系结构成为了研究的热点。 1 1 3 处理器的分片式设计及其意义 半导体工艺的发展导致集中控制的单核结构难以继续扩展单核的性能，处理 器设计者很自然地想到使用多个单核集成到一个芯片内的方法来设计芯片。依据 处理器核的体系结构特征和芯片级的可扩展能力，c m p 结构被分成两大类：多 核( m u l t i c o r e s ) 结构和众核( m a n y c o r e s ) 结构。工业界当前实现的通用c m p 芯片主要采用多核结构。为兼容传统的应用和系统级环境，通用多核芯片的处理 器核仍然采用传统的集中控；i ；j 与指令级并行体系结构，通过逐步继承和改进传统 对称多处理器( s y m m e t r i cm u l t i p r o c e s s o r ，s m p ) 并行系统的设计方法，使每一 工艺代的片上有效核数增加一倍。据美国 b n , j i , i 大学伯克利分校的研究人员( k r s t e a s a n o v i c 2 0 0 6 ) 估计，这种设计方法可能对2 8 核有效，当核数增加到1 6 - 3 2 时将达到性能的极限。与此不同的是，众核结构是对可扩展能力达到数千个核、 计算能力达到万亿次级的微处理芯片体系结构发展道路的探索。流处理器发展至 今，也面临着从集中式单核结构向分片式众核结构的跨越。 总结目前学术界的研究和工业界的实践，未来众核芯片的结构特点是采用分 片式的设计思想：将计算、存储资源组织成片式的基本单元( t i l e ) ，并分别称为 计算单元、存储单元。相对于超标量处理器而言，片式单元是相对简单的、可重 用的。大量的片式单元由高能效、可扩展的片上互连网络连接起来。逻辑上，我 们可以把相邻的计算单元、存储单元以及片上互连网络的路由器组合成一个复杂 核，比如s m p 结构中的核。 分片式的设计思想能较好地缓解功耗墙和线延迟的问题：分片式的体系结构 强调结构的层次化、功能部件的模块化和分布化，每个功能部件结构都相对简单， 部件内部尽可能保持连线的局部性，从而可以合理控制单核的时钟频率，把单位 面积功耗限制在一定范围内。同时，基于分片式处理器的低功耗技术应用，如敢 态电压频率调节( d y n a m i cv o l t a g ef r e q u e n c ys c a l i n g ) 和门控电源( p o w e rg a t i n g ： 2 第1 章绪论 态电压频率调节( d y n a m i cv o l t a g ef r e q u e n c ys c a l i n g ) 和门控电源( p o w e rg a t i n g ) 等，也比传统处理器上更容易实现。简单的、可复用的固定单核结构能够有效降 低设计复杂度和降低单个核内的长线延迟。由于每个片式单元只占据芯片上很小 的面积，因此信号只需穿过片上很短的距离，既避免了全局的长线延迟，又更易 于实现相邻核间的高速数据通信。 分片式的设计思想有效地利用大量的晶体管资源，将各种资源分簇 ( c l u s t e r i n g ) 和去耦( d e c o u p l i n g ) ，实现了芯片结构的高度可扩展性。芯片设 计人员可以通过片式单元数量的增加来大幅提升芯片的性能，从而降低设计和制 造成本。不仅如此，这样的结构还易于实现分布的时钟控制、均匀的功率分布和 低功耗设计，降低芯片设计、验证和测试的复杂度和成本，实现对系统可靠性的 控制。 1 2 分片式流处理器设计的几个关键问题 如何在分片式流处理器上进行并行程序设计成为决定分片式流处理器性能 的关键，要解决这个关键问题只有通过硬件和软件的协同设计才能找到突破口。 从编程模型中对程序的划分以及并行性的描述，到计算模型及指令系统中如何表 示并行性，最后到分片式处理器中如何设计和组织计算、存储、互连这三种资源 以利用指令系统表示出的并行性都是硬件和软件的协同设计需要重点考虑的。 1 2 1 计算模型 程序的计算模型及其指令系统用来组织和描述程序中并行性。计算机的计算 模型可以分为控制流和数据流两大类。图灵机理论是控制流计算机的基础，控制 流计算机也被称为冯诺伊曼型( v o nn e l l l i l a n l l ) 计算机，它是主流计算机一直采 用的基本体系结构。在这种结构中，编译器静态确定指令的执行顺序，完全依赖 硬件或者软件来发掘指令间的依赖关系。在指令执行时，程序计数器( 指令指针) 控制着指令的执行次序，需要存储器或者寄存器暂存指令间的操作数传递。在二 十世纪六十年代末，学术界提出了数据流计算模型。在数据流计算模型中，指令 间天然的依赖关系决定了指令的执行顺序，指令按照数据流图执行。生产者指令 和消费者指令之间的操作数不是通过存储器进行暂存，计算结果直接传送到消费 者指令的操作数域中。当指令执行需要的所有操作数被生产者指令送到后，指令 就可以被发射，不需要软硬件去寻找指令间的并行性。 控制流计算机以指令为表达并行性的单位、以指令为执行单位是开发并行性 的瓶颈。超标量、超流水、超长指令字、乱序发射以及分支预测等技术都是基于 控制流计算模型而提出的，这些技术都想通过增大指令窗口从串行指令流中来发 第1 章绪论 掘更多的指令级并行性，但是增大指令窗口会带来硬件复杂性以及软件复杂度的 提高，使得结构设计难于扩展。 纯数据流的计算模型存在以下问题：在纯数据流的计算模型中，每个数据都 需要在消费者指令处有个备份，无法利用数据局部性。纯数据流的计算模型将完 整的数据流图在指令中编码，硬件需要存储整个数据流图需要的指令和操作数， 同时还要能够支持未知数目的乱序执行带来的并发读写请求，这超出了现有的硬 件实现能力。在软件方面，纯数据流的计算模型需要编程人员学习专用的数据流 程序设计语言，虽然这些数据流编程语言正逐渐在科学计算领域流行起来，但是 仍然不能被绝大多数用户熟练掌握。 鉴于纯控制流和纯数据流两类指令模型的特点，学术界提出了一种类数据流 的计算模型。它的基本思想是根据控制流图将串行程序划分为多个控制相关的超 块。超块指利用谓词执行技术将多个基本块集合在一起组成的一段指令序列，它 仅有一个控制流控制入口，可以有多个出口。每个超块内部是局部的数据流驱动 执行，而超块之间仍然维持控制流计算模型，即把全局的控制流与局部的数据流 结合起来。 类数据流计算模型具有以下特点：超块内部的指令显式描述超块的数据流 图。编译器将超块内部的指令静态映射到多个分片式计算单元。当指令对应的操 作数准备好后，计算单元可以开始执行指令。这种静态放置、动态发射的机制使 得结构方面不需要超标量处理器核中集中式的指令发射窗口、重命名表，实现了 计算单元组织上可扩展，同时降低了功耗。类数据流计算模型将数据流计算局限 在较短的超块中，使用寄存器依赖表示块间的数据依赖，不需要存放全局数据流 图和全局的中间结果。这不但控制了纯数据流计算对硬件资源的需求，也降低了 编译的复杂度。如果将超块当做微线程单位，多个超块间可以并发执行以开发超 块间的并行性，容忍访存和通讯延迟。其次，将检测控制依赖的粒度加大，硬件 上不需要对每条指令进行控制依赖同步，而是每个超块同步一次，降低了控制转 移指令带来的代价，块内部使用谓词执行将控制流转化成数据流，减少了处理控 制流转移所带来的硬件开销。 类数据流驱动的计算模型首先需要编译器将程序编译得到以超块为单位的 指令块。超块是指在控制流上只有1 个入口、可以有多个出口的指令块。编译器 按照数据流图，将超块内部指令间的依赖关系在指令中静态编码，不需要硬件重 新判断块内指令的依赖关系，超块内部的控制流依赖通过谓词执行技术转换为数 据依赖。块间依赖数据采用寄存器暂存。图1 1 的左上、右上、下半部分别是源 码、控制流图、数据流图。数据流图中块内的数据依赖关系使用带箭头的直线表 示，块间数据依赖采用带箭头的虚线表示。 4 第1 章绪论 s = ：；再一一一一一一一一一： l z 寸5 ：i l ：二： i： b = 一+ - ； ： ：。 m = ； ： ： l z y ；ii z 。5 i it 皇z + s ： l i m4 t + l l i ： 图1 1 超块举例 现有的流处理器都采用控制流计算模型来开发i l p ，v l i w 和记分板结构分 别是使用软件和硬件开发i l p 。类数据流计算模型允许处理器的软件和硬件系统 更有效的协同开发i l p ，使处理器能够充分地借用软件系统的力量，来减轻工艺 进步带来的线延迟、功耗等问题的压力，使处理器技术在结构上和性能上都具有 良好的扩展性。 ii-_iiiljrli_-_-iiil 第1 章绪论 现有流处理器依靠s i m d 结构以及s p m d 结构开发应用中的d l p 。s i m d 结 构指同一个控制器同步地控制所有的处理器阵列，执行相同指令，来开发空间上 的并行性。s p m d 结构是m i m d 结构的一个子类，指不同的控制器异步地控制 相应的处理单元，虽然不同控制器中程序的微码是相同的，但是可以按照不同控 制流路径执行。i m a g i n e 处理器中8 个运算簇被微控制器按照s i m d 方式集中控 制。c e l l 处理器中单个s p e 内采用s i m d 控制计算资源。支持c u d a 的g p u 在 两个维度开发d l p ，即多个s m 间依靠s p m d 以及在s m 内部采用s i m d 。s i m d 要求硬件同步执行，需要指令解码后的控制信号要跨越多个运算部件，不利于结 构扩展。当程序中相邻数据遇到不同的控制流转移时，会增加程序员优化程序的 难度。s i m d 概念侧重于底层结构使用向量部件实现，s p m d 概念侧重于在并行 编程中组织计算，其底层可以依靠s i m d 结构实现。 s b m d 模型的定义如下：依赖编译系统把源程序中对不同数据进行计算的相 邻循环体展开并组成超块；以类数据流计算模型为基础，要求在指令中显示编码 依赖关系；支持谓词执行，可以把每份数据对应循环体中的控制流依赖转化成数 据依赖，允许相邻数据执行不同的控制流转移。由于每份数据，都有一份循环体 对应的指令用于组织计算，那么支持s b m d 模型的硬件不需要s i m d 结构中集 中式控制器，结构上具有可扩展性，而且不需要同步执行。由于循环展开后暴露 了相邻循环体间的数据依赖关系；s b m d 模型支持在指令中显示编码相邻循环体 间的数据交换，避免到下一级存储空间交换数据。 1 2 2 片上存储层次 有两类重要的应用属于计算密集型，一类是多媒体应用，另一类是科学计算。 多媒体应用包括图像处理、图形变换、信号处理、加解密等，科学计算包括分子 动力学、流体力学、电磁分析、近场光学计算等。这两类应用具有明显的生产者 消费者局部性特点：程序中一段计算产生中间数据，这部分数据能够被下一段 计算使用，不会被生产它的计算再次使用。这种数据局部性是可预测的，可以被 程序员和编译器所捕获。充分利用这种数据局部性，可以减少不必要的访存次数， 降低访存压力，提高芯片能耗的实际利用率。 流处理器的一个重要特征是具有软件管理的片上存储区域，它可以利用应用