（计算机系统结构专业论文）类数据流驱动的分片式处理器上的编译及优化技术.pdf

摘要 摘要 分片式处理器体系结构能够很好地应对纳米工艺代的功耗、线延迟、设计和 验证复杂度等一系列问题，是一种具有良好性能扩展潜力的片上多处理器结构设 计方案。如何在分片式处理器体系结构上支持通用目的程序设计是决定这种结构 成败的关键。要解决这个问题，只有通过软硬件的协同设计才能找到突破e l 。分 片式处理器结构上软硬件协同设计的首要问题就是要设计能高度暴露程序并行 性、降低能耗的指令集体系结构；其次是为这种体系结构设计和实现一个高效的 编译系统。本文围绕一种分片式处理器t p a p i ，研究一种类数据流指令集体系 结构及其编译和优化技术，包括如何通过软硬件系统协同工作，管理片上大量计 算、存储和网络资源；如何利用并行编译器挖掘和表示程序中的并行性；以及如 何开发适合新结构新应用的编译优化技术，进一步提高处理器性能等。主要研究 内容和成果包括： ( 1 ) 为分片式处理器t p a p i 设计了指令集系统d i s c i 。d i s c i 是一种类 数据流指令集体系结构，具有块原子执行、指令间直接通信的特点，并具有高效 支持指令级并行性、降低单条指令的执行开销、简化硬件结构，以及支持多粒度、 多层次开发程序并行性等众多优势。 ( 2 ) 基于l l v m 编译框架，设计和实现了t p a p i 并行编译器。该编译器 将程序划分为多个超块，为每个超块分配硬件资源，并将每个超块内的指令映射 到硬件衬底上。t p a p i 编译器最重要的特点是称为t p a c 的中间表示，将程序 表示成以超块为单位的控制流图和超块内部以指令为单位的局部数据流图两层 结构；以及一种面向硬件结构和应用的指令空间调度方法，使编译器能够根据应 用程序的计算特征为其分配硬件资源，在充分开发程序并行性的同时，提高硬件 资源利用率。 ( 3 ) 研究了编译技术对程序控制流可预测性的影响，提出了根据应用程序 特征选用与之相适应的基本块选择算法构造超块的准则，提高超块控制流可预测 性。实验表明，构造超块时使用路径执行频率、路径宽度等作为选择基本块的启 发式算法，可以提高构造出的超块的控制流可预测性，从而提高超块级分支预测 器的成功率，特别是多级预测时的成功率；同时应用程序本身的控制流特征对基 本块选择启发式效果有很大影响。本文由此总结出根据应用程序本身的控制流特 征选用合适的基本块选择启发式的准则：当程序关键路径较多时选择以路径执行 频率主导的启发式，当程序关键路径很少时选择以路径宽度主导的启发式。 ( 4 ) 研究了如何利用编译器简化硬件分支预测器结构，提出了一种软硬件 摘要 协同的超块级分支预测器。该预测器既有软件预测器实现代价小的优势，又有硬 件预测器的灵活性和高效率。实验表明，该预测器能在保持预测成功率的同时， 将硬件分支预测器使用的存储空间降低到1 2 ，将硬件分支预测器的调用次数减 少o 1 到1 5 ，从而降低超块级分支预测器的硬件开销和功耗。 ( 5 ) 针对d i s c i 指令集的类数据流编码风格，提出了在t p a p i 体系结构 中实现谓词执行技术的方法。该方法对指令集的改动很小，只需要1 b i t 谓词位； 不需要额外的微体系结构支持，因此开销很小。本文还提出了一种利用剖析技术， 有选择地为指令指定谓词的编译优化方案，进一步降低谓词执行带来的软件输出 树开销。该优化方法能够维持程序的高并行度，并降低无效执行的代价。 本文的研究工作研究结果可用于指导分片式处理器上的并行编程模型和并 行编译系统软件的设计，帮助结构设计人员设计高效能的片上多处理器体系结 构，以尽可能小的并行程序设计难度、系统软件复杂性和硬件实现代价尽可能多 地从应用程序中开发出分片式处理器结构上可利用的并行性。 关键词：分片式处理器，类数据流执行模型，编译器设计，编译优化，超块级 分支预测，谓词执行 a b s t r a c t t i l e dp r o c e s s o ra r c h i t e c t u r ei sa ne f f e c t i v er e s p o n d e n c et ot h ew i r ed e l a y , d o w e t c o n s u m p t i o n ，a n dd e s i g na n di m p l e m e n t a t i o nc o m p l e x i t yc h a l l e n g e s i ti sa ne f f i c i e n t c h i p - m u l t i p r o c e s s o rs c h e m ew i t hg o o dp e r f o r m a n c ep o t e n t i a l t h ek e yp o i n ti n c u r r e n tr e s e a r c h e so ft i l e dp r o c e s s o ra r c h i t e c t u r ei sh o wt oa c c e l e r a t eg e n e r a lp u r p o s e a p p l i c a t i o n s o n ec a ns o l v et h i sp r o b l e mo n l yb yh a r d w a r e s o f t w a r ec o d e s i g n t h e p r i m a r yc h a l l e n g ei nh a r d w a r e s o f t w a r ec o d e s i g ni st od e s i g na l li n s t r u c t i o ns e t s y s t e mw i t hh i g hp a r a l l e l i s me x p o s e da n dl o w e n e r g yc o n s u m p t i o n ，a n dt od e s i g na n d i m p l e m e n tah i g hp e r f o r m a n c ep a r a l l e l i s mc o m p i l e r _ t a r g e t e di t t h i sd i s s e r t a t i o n f o c u s e so nd e s i g n i n gad a t a f l o w l i k ei n s t r u c t i o ns e ta r c h i t e c t u r ea n dt h ec o m p i l a t i o n a n do p t i m i z a t i o nt e c h n i q u e st a r g e t i n gi tf o rt 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 wt o u s es o f t w a r e sa b i l i t yt om a n a g et h ec o m p u t a t i o na n ds t o r a g er e s o u r c eo nac h i p ，h o w t oe x p l o i ta n de x p l o r ep a r a l l e l i s mi na p p l i c a t i o n s ，h o wt od e v e l o pn e w c o m p i l a t i o n t e c h n i q u e st h a ts u i t a b l ef o rt i l e dp r o c e s s o r t h em a j o rc o n t r i b u t i o n so ft h i sw o r ka r e a s 内l l o w s ： ( 1 ) d e s i g n e d a ni n s t r u c t i o ns e td i s c if o rt p a p i p r o c e s s o r , w h i c hi sa d a t a f l o w l i k ei n s t r u c t i o ns e t d i s c ii n s t r u c t i o ns e ti sc h a r a c t e r i z e da si n s t m c t i o n b l o c ka t o m i ce x e c u t i o na n dd i r e c t c o m m u n i c a t i o na m o n gi n s t r u c t i o n s i tc a n e f f i c i e n t l ys u p p o r ti n s t r u c t i o nl e v e lp a r a l l e l i s m ，a n dr e d u c et h ec o s to fc a c hs i n g l e i n s t r u c t i o nt h r o u g hb l o c ka t o m i ce x e c u t i o n ，e x p l o r em u l t i 1 e v e la n dm u l t i g r a n u l a r i t y p a r a l l e l i s mi na p p l i c a t i o n s ，a n dc a nf u r t h e rs i m p l i f yt h ec o m p l e x i t yo fh a r d w a r e d e s i g n ( 2 ) d e s i g n e da n di m p l e m e n t e dap a r a l l e lc o m p i l e rt oa u t o m a t i c a l l yp a r a l l e l i z e s e r i a la p p l i c a t i o n sb a s e do nl l v mf r a m e w o r k ，w h i c hc a nb r e a ka na p p l i c a t i o ni n t oa s e r i a lo fh y p e r b l o c k s ，a s s i g nh a r d w a r er e s o u r c ef o re a c hh y p e r b l o c k , a n dm a pe a c h i n s t r u c t i o ni n t oh a r d w a r e t h ef e a t u r e so ft p a p ic o m p i l e ra r ei t s i n t e r m e d i a t e r e p r e s e n t a t i o nt p a - c ，w h i c hr e p r e s e n t sap r o g r a mi nat w o 1 e v e ls t r u c t u r e ：t h e c o n t r o l f l o wg r a p hi nu n i to fh y p e r b l o c ka n dt h el o c a ld a t a f l o wg r a p hi n u n i to f i n s t r u c t i o nw i t h i ne a c ho ft h e h y p e r b l o c k ；a n dt h eh a r d w a r er e s o u r c ea n d a p p l i c a t i o n o r i e n t e di n s t r u c t i o nm a p p i n gm e t h o d ( 3 ) p r o p o s e dac h o o s i n gd i s c i p l i n eo fh y p e r b l o c kc o n s t r u c t i o na l g o r i t h mf o r h i g h e rc o n t r o l f l o wp r e d i c t a b i l i t y w ed e s i g n e d5d i f f e r e n ta l g o r i t h m st oc o n s t r u c t 1 1 a b s t r a c t h y p e r b l o c k , a n da n a l y z et h e i ri n f l u e n c et ot h ec o n t r o lp r e d i c t a b i l i t yo fc o n s t r u c t e d h y p e r b l o c k s e x p e r i m e n t sp o i n to u tt h a tu s i n gp a t he x e c u t i o n 仔e q u e n c yo rp a t hw i d t h a sh e u r i s t i ca l g o r i t h mc a ni m p r o v eb r a n c hp r e d i c t i o na c c u r a c y , e s p e c i a l l yi n d e e p p r e d i c t i o n b u tt h e i rs t r e n g t hi sa f f e c t e db yt h ec o n t r o lb e h a v i o ro fa p p l i c a t i o n s w e f i n dt h er u l et oc h o o s eh e u r i s t i ca l g o r i t h mf o rd i f f e r e n tk i n d so f a p p l i c a t i o n s ：w h e n t h e r ea r eaf e wh o tp a t h si na na p p l i c a t i o n ，c h o o s i n gp a t hw i d t h - o r i e n t e da l g o r i t h m ， a n dw h e nt h e r ea r es e v e r a lh o tp a t h si na na p p l i c a t i o n ，c h o o s i n gp a t he x e c u t i o n 仔e q u e n c y o r i e n t e da l g o r i t h m ( 4 ) d e s i g n e das o f t w a r e h a r d w a r ec o - o p e r a t eh y p e r b l o c k l e v e lb r a n c hp r e d i c t o r , w h i c hc a nt a k et h ea d v a n t a g eo fs o f t w a r e sl o wo v e r h e a d ，a n dh a r d w a r e sf l e x i b i l i t y a n de f f i c i e n c y t h i sp r e d i c t o rn e e d so n l y1 2o fs t o r a g er e s o u r c e ，a n dr e d u c e st h e a m o u n to f h a r d w a r e p r e d i c t o ri n v o k i n gb y0 1 t o1 5 t or e d u c eb o t h i m p l e m e n t a t i o nc o s ti nh a r d w a r ea n dp o w e rc o n s u m p t i o n ，w h i l ek e e p i n gp r e d i c t i o n a c c u r a c y ( 5 ) p r o p o s e da ni m p l e m e n t a t i o nm e t h o do fp r e d i c a t e de x e c u t i o nt e c h n i q u ef o r t p a - p ia r c h i t e c t u r e i th a sm a n ya d v a n t a g e s ，s u c ha sl o wo v e r h e a da n df u l l s u p p o r t o fe a c hi n s t r u c t i o ni nt p a p ii s a b u ti ta l s oi n d u c e st h ec o s to fs o f t w a r ef a n o u tt r e e t or e m o v et h e s es o f t w a r ef a n o u tt r e e s ，w ep r o p o s eap r o f i l i n g - g u i d e do p t i m i z a t i o n ， w h i c hc a nk e e ph i g hp a r a l l e l i s m ，w h i l er e m o v i n gu s e l e s se x e c u t i o n 。 a l lt h ew o r k si nt h i sd i s s e r t a t i o nc a nb eu s e dt og u i d et h ed e s i g n i n go fp a r a l l e l p r o g r a m m i n gm o d e la n dc o m p i l e ro nt i l e dp r o c e s s o ra r c h i t e c t u r e ，t ob eh e l p f u lf o rt h e d e s i g n i n go fh i g h - p e r f o r m a n c eo n c h i pm u l t i - p r o c e s s o ra r c h i t e c t u r e ，a n dt oe x p o s e m o r ep a r a l l e l i s mf r o ma p p l i c a t i o nw i t hl e s sh a r d w a r e ，s o f t w a r ec o m p l e x i t ya n dl e s s h a r d n e s si np a r a l l e lp r o g r a m m i n g 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 i k ec o m p u t i n gm o d e l ，c o m p i l e r , c o m p i l e ro p t i m i z a t i o n s ，h y p e r b l o c k - l e v e lb r a n c hp r e d i c t i o n ，p r e d i c a t e de x e c u t i o n i v 图表目录 图表目录 图i - i 几个应用循环优化技术的例子6 图i - 2 应用谓词执行的简单例子7 图1 - 3 不同工艺条件下，各抽象层次在处理器设计中扮演的角色8 图2 - im u l t i s c a l a r 体系结构图1 2 图2 - 2m u l t i s c a l a r 执行模型示意图1 3 图2 - 3t r i p s 结构示意图1 8 图2 - 4t f l e x 结构示意图1 8 图2 - 5r a w 处理器结构2 0 图2 6r a w 编译器生成的程序代码组成部分，及到硬件结构的映射2 1 图2 7 一个简单的w a v e s c a l a r 结构模型2 3 图2 8w a v e c a c h e 结构片上网络系统2 3 图2 - 9t a r t a n 结构示意图2 5 图3 - 1t p a p i 超块指令组成3 2 图3 - 2t p a - p i 超块的格式和存储方式3 4 图3 3w 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 的简单例子3 6 图3 - 4 软件输出树示意图3 7 图3 5t p a - p i 处理器执行过程及各过程的状态3 8 图3 - 6t p a - p i 结构抽象示意图4 1 图4 - 1t p a - p i 结构中串行程序表示方式4 5 图4 - 2t p a - p i 编译器结构及编译流程4 7 图4 - 3 超块构造流程5 l 图4 - 4 超块构造阶段总体算法：c r e a t e h y p e r b l o c k s 5 2 图4 - 5 平均有效指令数计算示例5 4 图4 - 6 在超块构造中应用尾复制消除超块内部的入口5 6 图4 - 7 尾复制算法5 7 图4 - 8 尾复制带来的代码膨胀问题5 8 图4 - 9 循环剥离技术在t p a - p i 编译器中的应用5 9 图4 - 1 0 循环剥离技术实现算法6 0 图4 - 1 1 在t p a - p i 编译器中应用循环展开技术6 0 图4 - 1 2 循环展开技术实现算法6 1 图4 - 1 3 必经及后必经节点6 3 v m 图表目录 图4 - 1 4 根据必经节点和后必经节点等控制流信息，为超块内每个基本块指定谓 词的算法。6 4 图4 - 1 5 根据超块内基本块的谓词信息，插入谓词计算指令和为每条指令指定谓 词的算法6 5 图4 - 1 6l s i d 分配算法6 8 图4 - 1 7 应用l s i d 分配算法的例子6 9 图4 - 1 8e x i ti d 分配算法7 0 图4 - 1 9t p a p i 程序中超块内分支指令数与目标地址数的比较7 l 图4 - 2 0t p a - p i 指令空间调度器流程图7 2 图4 - 2 1 超块内指令间数据流图示例7 4 图4 - 2 2 将指令映射到计算t i l e 上的调度算法7 6 图5 - 1 预测器基本构造示意图7 9 图5 - 2t p a - p i 中出口预测器结构7 9 图5 - 3t p a - p i 中分支目标地址预测器结构8 0 图5 - 4 不同基本块选择算法构造出的超块8 3 图5 - 5 不同构造算法下超块级分支预测器成功率8 7 图5 61 7 5 v p r 基准测试程序中，不同构造算法下超块级分支预测器多级预测的 成功嚣8 8 图5 - 71 8 1 m c f 基准测试程序中，不同构造算法下超块级分支预测器多级预测的 成功率8 8 图5 81 9 7 p a r s e r 基准测试程序中，不同构造算法下超块级分支预测器多级预 测的成功率8 9 图5 - 92 5 6 b z i p 2 基准测试程序中，不同构造算法下超块级分支预测器多级预测 的成功率8 9 图5 - 1 0 软硬件协同分支预测器结构9 1 图5 - 1 1 软硬件结合超块级分支预测器中选择器设计方案一9 4 图5 - 1 2 软硬件结合超块级分支预测器中选择器设计方案二9 5 图5 - 1 3 使用a l w a y s 选择器，不同硬件配置下超块级分支预测器成功率9 6 图5 - 1 4 使用s i n g l e 选择器，不同硬件配置下超块级分支预测器成功率9 6 图5 - 1 5 使用s e t 选择器，不同硬件配置下超块级分支预测器成功率9 6 图5 - 1 6a l w a y s 选择策略下，m c f 程序的超块级分支预测成功率9 8 图5 - 1 7s i n g l e 选择策略下，m c f 程序的超块级分支预测成功率9 8 图5 - 1 8s e t 选择策略下，m c f 程序的超块级分支预测成功率9 8 i x 图表f i 录 图6 - 1 类数据流计算模型中实现谓词执行的简单例子1 0 3 图6 - 2s p e c 2 0 0 0 中，不同类型指令的消费者指令数目1 0 6 图6 - 3 隐式谓词方法1 0 7 图6 - 4 推测提升方法1 0 7 图6 - 5 基于边剖析的谓词执行优化技术结构图1 0 9 图6 - 6 基于边剖析技术的谓词执行优化方法1 0 9 图6 - 7 程序可执行代码中m o v e 指令的比率儿o 图6 - 8 一个周期内同时有两个或两个以上指令可以发射的概率1 1 1 图6 - 9 通信网络延迟1 l l 图6 - 1 0 三种优化技术的加速比1 1 2 表2 - 1 新兴分片式处理器结构比较2 7 表5 - 1t p a - p i 软硬件协同分支预测器中硬件预测器配置9 3 表5 - 2 软件预测器减少的硬件预测器访问比例1 0 0 表6 - 1m o v 指令占静态指令总数的比例1 0 5 x 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特另f j d e i 以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已存论文中作了明确 的说明。 作者签名：m l 一碲 签字同期：蝉受f 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向困家有关部门或机构送交 论文的复印件和电子版，允许论文被杏阅和借阅，可以将学俯论文编入有关数据 库进行检索，可以采用影印、缩印或手- 描等复制手段保存、7 【：编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 岖仫丌口保密( 年) 作者签名：抽 签字同期： j 驴止 导师签名：瓤a 册穸伊侈 第一章绪论 第一章绪论 1 1 研究背景 1 1 1 分片式处理器体系结构出现的必然性 从7 0 年代第一块微处理器诞生之日起，提升程序在硬件系统上的执行性能 就一直是微处理器研究和制造领域孜孜不倦追求的目标。微处理器的性能在过去 的2 0 年里以每年5 0 6 0 的速度增长。7 0 年代，更宽的数据通路和更高效地管 理存储系统的硬件支持是提升微处理器性能的主要途径；8 0 年代之后，微处理 器性能提升主要来自于处理器主频的提升和多条指令并行执行( h e n n e s s ya n d p a t t e r s o n ，2 0 0 3 ；g a u d i o t ，k a n ge ta 1 ，2 0 0 5 ) 。但是到了今天，这两种提升性能的方 法都面临着巨大的挑战限a n dr ，2 0 0 6 ) 。除了传统的“存储器墙”问题，随着半 导体工艺的发展，线延迟问题( a g a r w a l ，h r i s h i k e s he ta 1 ，2 0 0 0 ；h o ，m a ie ta 1 ， 2 0 0 1 ) ，功耗问题( g o n z a l e z ，1 9 9 7 ；t r a v o r , 2 0 0 1 ) ，硬件复杂度过高、开发周期长问 题( p a t t ，1 9 9 6 ；p a r t ，p a t e le ta 1 ，1 9 9 7 ) 等也成为限制单核处理器发展的因素。因此必 须寻找新的方法，采用新的思路来进一步满足处理器性能提升的需求，而多核 ( m u l t i c o r e ) 和众核( m a n y c o r e ) 结构有望能够克服上面的瓶颈( k a n dr ， 2 0 0 6 ) ，微处理器的发展已经进入了多核和众核时代。 多核及众核结构有多种不同的实现方案，分片式处理器体系结构( t i l e d p r o c e s s o r a r c h i t e c t u r e ) 是其中一种。相比于其他片上多核结构，分片式处理器体 系结构强调结构的层次化、功能部件的模块化和分布化，每个功能部件都相对简 单，部件内部尽可能保持连线的局部性，因此它具有更好的可扩展性和灵活性， 更容易在芯片上集成更多的计算能力。 分片式处理器体系结构的设计思想是将芯片划分为几十甚至上百个分片单 元( t i l e ) ，并通过片上互连网络将这些分片单元连接成一个整体。每个分片单元 可以是计算分片或存储分片，从而将计算资源和存储资源均匀分布在整个芯片 上。每个计算分片可以是一个乱序( o u t - o r d e r ) 超标量处理器陔，也可以是一个 简单的顺序( i n o r d e r ) 处理器核心，甚至在更细粒度的分片式处理器核中可以 是一个或几个计算部件。每个计算分片的周围分布着多个存储分片，提高了存储 器带宽，因此更有利于提高数据级并行应用的性能，如信号处理、多媒体处理等 应用。 分片单元之间通过高速片上网络互连，其中最简单容易实现的互连方式是二 维m e s h 网络。为了进一步降低通信延迟和增加通信局部性，还可以构造多层次 第一章绪论 的片上网络，例如将几个相邻的计算或存储分片通过点对点网络连接，使信号可 以通过单跳到达相邻的分片单元，然后多个这样的分片单元的组合再通过二维 m e s h 网络连接，组成范围更大但延迟也较大的通信区域。分片式处理器与传统 超标量处理器的一个区别也正体现在对片上网络的管理，大部分分片式处理器依 赖软件系统，如编译器和运行时环境来协助管理分片单元之间的通信。 分片式处理器比较方便地解决了线延迟、功耗、硬件设计复杂度和可扩展性 等问题：( 1 ) 首先是它充分的“分布”化，将计算资源均匀的分布在整个芯片上， 既可以提高片上大量资源的利用率，构建更大的指令窗口和发射宽度；又可以实 现分布式管理，从而避免集中控制结构的不可扩展性，因此分片式处理器结构的 一个突出的优势就是良好的可扩展性。( 2 ) 分片式处理器中通过大量计算分片并 行工作可以获得很高的指令吞吐率，而每个计算分片本身却可以很简单，面积也 很小，可控制在信号单周期可达的面积内，这样通过把大部分数据通信限制在单 个分片内部或相邻的少数分片之间的局部范围内，以及使用多跳的片上网络实现 全局的数据通信，可以解决线延迟的问题，适应未来十几年线延迟的影响。( 3 ) 分片式处理器的另一个好处也是由它的分布化带来的：不仅计算资源可以分布， 存储资源也可以分布，通过将存储分片分布在计算分片的周围，可以提供更高的 存储带宽；同时通过将寄存器文件、一级数据c a c h e 、指令c a c h e 分布化，还可 以高效且低开销地实现多体的寄存器和c a c h e 等，从而提供更多的寄存器、c a c h e 读写端口。( 4 ) 分片式处理器通过复用单个小核来构建强大计算资源，通过扩展 网络来实现更大的处理器规模，将硬件设计复杂度降到了最低，缩短了整个处理 器核设计、验证到制造的周期。( 5 ) 通过增加计算分片的数量和访存宽度来增加 指令发射宽度，提高性能，而不是复杂耗能的硬件部件，或者更高的时钟频率， 也就避免了令人头疼的功耗问题，具有更好的可扩展性。 1 1 2 类数据流计算模型及其优势 现代主流的处理器均采用传统的冯诺依曼式控制流计算模型。冯诺依曼控 制流计算模型具有两个特征：一是把程序看成线性的可寻址的指令序列，这些指 令可以用于描述对数据的各种不同操作，或者用于说明下一条指令的位置。程序 执行过程中通过称为程序计数器的寄存器( p c ) 来寻址下一条指令，并通过控 制转移指令来修改程序计数器，控制程序中指令的执行顺序。这种全序关系极大 的限制了程序中可用的并行性。另一个特征是使用第三方存储设备如寄存器、存 储器集中存储每个操作的中间结果，由于寄存器、存储器容量的限制，使得两条 独立的操作争喟同一个存储位置而造成了称为输出相关和反相关的伪数据依赖。 现代超标量处理器中大多采用了复杂的体系结构技术来解决控制流计算模 型带来的问题。首先，使用分支预测技术来解决控制依赖的问题，但是硬件分支 2 第一章绪论 预测器占用芯片面积很大、复杂度高，为了提高分支预测器性能，分支预测器向 着更大更复杂更耗能的方向发展。虽然现在分支预测器的精确度可以达到9 5 以上，但是在深度流水处理器中推测失败的开销仍然很大。其次，引入寄存器重 命名技术解决集中存储带来的伪数据相关，这种技术需要额外的物理寄存器文 件。再次，为了打破指令串行顺序，开发指令级并行性，必须使用如指令窗口、 动态检测机制等硬件结构，重建指令之间的依赖关系，检测可并行指令。这些复 杂耗能的硬件部件的大量应用使得超标量处理器的扩展性较差，目前大多数超标 量处理器的发射宽度一般只能做到4 - 6 发射，且实际开发出的并行度不到2 。 除了控制流计算模型，在7 0 年代学者们对数据流计算模型( j a c ka n dd a v i d ， 1 9 7 5 ；a r t h u r , 1 9 8 6 ) 做了深入的研究。与控制流计算模型中程序表示成顺序指令流 和使用程序计数器来控制指令的执行顺序不同，在数据流计算模型中，程序被表 示成一个有向图，图中每个节点是一个动作或操作或指令，而节点之间的边对应 这些节点之间的数据流动，即数据依赖关系。数据流计算机中没有与程序计数器 对应的结构，指令的执行只由操作数的可用性驱动，当一个动作或指令需要的所 有输入都己得到时它就被触发，即每个动作或指令由操作数的可用性局部控制。 数据流计算模型通过“数据”来驱动操作的发射和执行，程序表示中没有控制依 赖，没有伪数据依赖，不需要维持指令之间的控制流顺序，而只需要维护指令之 间真数据依赖引起的偏序关系。所有指令的执行顺序完全由它们之间对数据的使 用关系决定，还原了最本质的程序依赖，暴露出更多的并行性。同时，数据流计 算模型中没有程序计数器、分支预测器这样的集中控制部件，指令的发射、执行、 提交都可以被完全分布，具有良好的扩展性，更适合多核及众核结构。 数据流的思想可以提供一些传统控制流机器不具备的性能潜力，但是数据流 机器也有它本身的局限性( a r v i n da n dr o b e r t ，1 9 8 8 ) 。首先，数据流计算模型失去 了控制流计算模型集中存储带来的数据局部性，使纯粹的数据流计算机对硬件资 源尤其是存储资源的需求极其庞大，因为每个数据都需要在它的消费者指令处有 个备份，因此它的性能受到功能单元数目、存储带宽的限制。其次，数据流计算 模型需要特别的数据流程序设计语言支持，虽然这些数据流编程语言正逐渐在科 学计算领域流行起来，但是仍然不能被绝大多数用户熟练掌握。对大量的命令式 程序设计语言编写的串行代码，需要特别的数据流编译器将它们编译成数据流 图，但是将整个程序转换成数据流图的工作量和复杂程度不是目前的编译器可以 完成的，更别提还有很多难以静态分析的别名依赖。 数据流计算模型与控制流计算模型有很大差别，但它们的关系并不是完全正 交，而足处于处理器设计方法的两个极端。处理器设计者可以设计一种处于纯粹 数据流计算模型与控制流计算模型之间的新型计算模型，同时利用数据流和控制 第一章绪论 流计算模式中的优点而规避他们的缺点( b u e h r e ra n de k a n a d h a m ，1 9 8 7 ；i a n n u c c i ， 1 9 8 8 ；n i k h i l ，1 9 8 9 ) 。一种方法是数据流驱动的多线程( s h i ha n dp a p a c h r i s t o u ，1 9 8 8 ； l e ea n dh u r s o n ，1 9 9 4 ；k a v i ，h y o n g s h i ke ta 1 ，1 9 9 9 ) 计算模型，这种计算模型根据 数据依赖将程序划分成多个控制独立的线程，线程之间只有数据依赖，线程内部 是控制依赖。这种结构是随着多线程技术一起发展起来，可以利用现有的超标量 处理器来处理一个数据流线程，但不适合更细粒度、更分布化的多核及众核结构。 另一种方法称为类数据流计算模型，它的基本思想是根据控制依赖将串行程 序划分为多个控制相关的指令段，每个指令段内部是一个局部的数据流计算机， 而指令段之间仍然维持控制流计算模型，即全局的控制流与局部的数据流结合。 类数据流计算模型可以很好的减弱和消除控制流计算模型和数据计算模型 的局限性，而发展它们的优势。首先，类数据流计算模型将数据流计算局限在较 短的指令段中，限制了数据流计算对硬件资源的需求，也有效的限制了编译的复 杂度。同时这种计算模型能够不改变目前的串行编程模式，可以很方便地应用于 命令式编程语言。其次，将控制依赖的粒度加大，不需要对每条指令进行控制依 赖同步，而是每个指令段同步一次，这降低了控制转移指令带来的局限性，从而 降低了分支预测器的负担，减少了分支预测失败的开销。再次，每个指令段内部 是完全的数据流图表示形式，不需要硬件结构来重构数据依赖、探测可并行指令， 只要这个指令段足够大就可以充分利用程序中的指令级并行性。更重要的是，类 数据流计算模型为分布式众核结构的软件和硬件系统提供了良好的接口，使处理 器能够更充分的借用软件系统的力量，来降低工艺进步带来的线延迟、功耗等种 种问题，使处理器技术在结构上和性能上都具有良好的扩展性。因此，类数据流 计算模型是一种更适合分片式处理器结构的计算模型。 1 1 3 常用编译方法 这节将简单介绍一些常用编译及优化技术，这些方法在分片式处理器结构中 仍然发挥着重要作用，当然在多核及众核环境下，并行编译器和编译优化技术的 设计需要根据结构特征和应用特征做相应的调整。 通常来说编译系统( a l f r e d ，r a v ie ta 1 ，1 9 8 6 ) 是一个将高级语言编写的程序转 化为等价目标指令集结构代码或可在一台目标计算机上执行的机器代码的软件 系统。广义上说它还包括把一种高级语言转换为另一种高级语言，把一种机器语 言转换为另一种机器语言，把一种高级语言转换为中间代码等各种形式的系统。 使用编译优化方法、在目标机器上生成高质量并确保正确的目标代码是获得处理 器性能的一个重要手段。例如一种指令级并行处理器v l i w ( j o s e p h ，1 9 8 3 ) 和 e p i c ( m i c h a e la n dr a u ，2 0 0 0 ) 的性能就极大程度地依赖于编译器的后端优化能力 o o h n ，1 9 8 5 ；p o h u a ，s c o ae ta 1 ，1 9 9 1 ) 。 4 第一章绪论 优化阶段由控制流分析( s h i v e r s ，1 9 8 8 ) 、数据流分析( r o s s a l b e r t ，1 9 7 6 ) 和优化 转换三部分组成。编译优化算法的提出是建立在对程序行为特征的分析和了解之 上，充分分析程序中的控制流和数据流信息是一切编译优化方法的前提。下面我 们简单介绍一下控制流、数据流依赖的含义和基本方法。 程序中的依赖关系描述了指令之间执行顺序的限制。控制依赖决定了跟分支 指令相关的执行顺序，即非分支指令决定于它所控制依赖的分支指令，只能在该 执行的时候才能执行。串行程序中除了第一个基本块的每一条指令外，均控制依 赖于某条或某些分支指令。在编译过程中分析控制依赖的方法通常是先建立控制 流图( c f g ) ( b r u c e ，d o u g l a se ta 1 ，1 9 9 4 ) ，然后通过在这个控制流图上为每个基 本块确定必经和后必经基本块( m i c h a e lj o s e p h