（计算机科学与技术专业论文）面向循环级数组访问的数据预取技术研究.pdf

国防科学技术大学研究生院学位论文 捅晏 微处理器和d r a m 之间日趋增大的性能差距促使人们探索新的技术以减少或 者隐藏访存延迟。c a c h e 层次存储结构能够有效减少大部分运用程序的访存延迟， 但是在科学计算程序中，访存延迟在程序执行时间中占很大比重，c a c h e 的利用率 低。这类程序中存在大量的线性访问的数组，数组规模越大，强制失效和容量失 效的次数也就越多。数据预取技术是解决这类访存失效的有效方法，它预测可能 的失效情况，提前发出数据访问操作，将访存与计算重叠起来，有效地隐藏了访 存延迟。 本文对科学计算程序中循环级数组访问的数据预取技术进行了深入研究和探 讨。文章详细分析了各种预取方案的优劣，讨论了研究对象的特点和各种影响因 素，提出了一种软硬件结合的数据预取方法。以此方法为指导，本文首先对预取 调度问题进行了重点研究，提出了一种新的预取度算法，改进了预取距离计算公 式，并在s u i f 2 平台上实现了预取分析算法。其次，本文还设计了一个自适应型的 顺序预取硬件单元，并移植了s i m p l e s c a l a r 模拟器，模拟验证了该硬件单元的功能 行为。 实验评测结果表明，本文的数据预取方法可以有效地减少循环级数组访问的 访存延迟，降低程序的执行时间，提高系统性能。 主题词：数据预取，局部性分析，l o o ps p l i t t i n g ，顺序预取单元，s i m p l e s c a l a r 模拟器，s u i f 2 平台 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t t h ee x p a n d i n gg a pb e t w e e nm i c r o p r o c e s s o ra n dd r a mp e r f o r m a n c eh a s n e c e s s i t a t e dt h eu s eo fi n c r e a s i n g l ya g g r e s s i v et e c h n i q u e sd e s i g n e dt or e d u c eo rh i d et h e l a t e n c yo fm e m o r ya c c e s s e s a l t h o u g hl a r g ec a c h eh i e r a r c h i e sh a v ep r o v e nt ob e e f f e c t i v ei nr e d u c i n gt h i sl a t e n c yf o rt h em o s ta p p l i c a t i o n s ，i ti ss t i l ln o tu n c o m m o nf o r s c i e n t i f i cp r o g r a m st os p e n dm o r et h a nh a l ft h e i rr u nt i m e ss t a l l e do nm e m o r yr e q u e s t s t h e r ea r eal a r g en u m b e ro fl i n e a r l yr e f e r e n c e da r r a y si ns c i e n t i f i ca p p l i c a t i o n s a r r a y s o fal a r g e rs i z eo n l yl e a dt om o r ec a c h em i s s e sb e c a u s eo fp o t e n t i a lc o m p u l s o r y c o n f l i c t sa n dc a p a c i t yc o n f l i c t s d a t ap r e - f e t c h i n gi sa ne f f e c t i v em e t h o df o rh i d i n gs u c h a c c e s sl a t e n c i e s i ta n t i c i p a t e sp o s s i b l ec a c h em i s s e sa n di s s u e saf e t c ht ot h em e m o r y s y s t e mi na d v a n c eo f t h ea c t u a lm e m o r yr e f e r e n c e d a t ap r e - f e t c h i n gh a st h ep o t e n t i a lt o s i g n i f i c a n t l yi m p r o v eo v e r a l lp r o g r a me x e c u t i o nt i m eb yo v e r l a p p i n gc o m p u t a t i o n 、兢t h m e m o r y a c c e s s e s t h i sp a p e rc a r r i e so u tac o m p r e h e n s i v er e s e a r c ho nd a t ap r e - f e t c h i n gt e c h n i q u e s f o rl o o p l e v e la r r a yr e f e r e n c e s a f t e ri n v e s t i g a t i n gt h ea d v a n t a g e s d i s a d v a n t a g e so f d i f f e r e n tk i n d so fp r e f e t c h i n gs c h e m e sa n da n a l y z i n gf e a t u r e so fl o o p - l e v e la r r a y r e f e r e n c e s ，as o f t w a r e h a r d w a r ec o o p e r a t i v ep r e - f e t c h i n ga p p r o a c hi sb r o u g h tf o r w a r d f o rl o o p l e v e la r r a yr e f e r e n c e s f i r s t ，t h i sp a p e rf o c u s e so nt h es t u d yo fp r e - f e t c h i n g s c h e d u l i n g i ti m p r o v e st h et r a d i t i o n a la l g o r i t h mo fp r e f e t c h i n gd i s t a n c ea n dp r o p o s e sa n o v e lm e t h o df o rc a l c u l a t i n gp r e f e t c h i n gd e g r e e a l la l g o r i t h m sa r ei m p l e m e n t e do n t h es u i f 2 i n f r a s t r u c t u r e s f i n a l l y ，as e l f - a d a p t i v eh a r d w a r e u n i tf o r s e q u e n t i a l p r e f e t c h i n g i s d e s i g n e da n di t s f u n c t i o n a lb e h a v i o r sa r es i m u l a t e db a s e do nt h e s i m p l e s c a l a rp l a t f o r m e x p e r i m e n t a lr e s u l t ss h o w t h a to u rs c h e m ee f f e c t i v e l yr e d u c e st h en u m b e ro fc a c h e m i s s e sf o rl o o p - l e v e la r r a yr e f e r e n c e sa n di m p r o v e so v e r a l ls y s t e mp e r f o r m a n c e s i g n i f i c a n t l y k e yw o r d s ：d a t ap r e - f e t c h i n g ，l o c a l i t ya n a l y s i s ，l o o ps p l i t t i n g ，s e q u e n t i a l p r e f e t c h i n gu n i t ，s i m p l e s c a l a rt o o l s e t ，s u i f 2p l a r m 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1l f e t c h 指令局部性提示取值1 4 表2 2p r e f 指令局部性提示取值l5 表2 3a l p l l a 平台的预取指令l5 表3 1 预取谓词2 8 表3 2 对不同类型的局部性进行的循环变形方法2 9 表5 1 测试程序f o r 循环结构特征统计5 7 表5 2 实验时各p a s s 的施加顺序5 8 表5 3s i m p l e s c a l a r 模拟器参数5 9 表5 4 实验结果统计表j 6 0 第1 i i 页 国防科学技术大学研究生院学位论文 图目录 图1 1 处理器和主存之间的性能差距1 图1 2 层次存储结构2 图2 1 程序片段执行框图7 图2 2 内积计算代码变形1 0 图2 3 内积循环变形最终版1 2 图3 1 重用分析示例2 4 图3 2 局部迭代空间示例2 6 图3 3 计算循环迭代中的数据访问量2 7 图3 4 预取谓词示例2 8 图3 5l o o p - p e e l i n g 变形图解2 9 图3 6l o o p u n r o l l i n g 变形图解2 9 图3 7s t r i p - m i n i n g 循环变形图解3 0 图3 8 流水调度后的循环代码示例3 0 图3 9 改进后的预取调度示例3 4 图4 1 c l i s 算法伪码3 6 图4 2t l t 算法伪码3 6 图4 3t l 算法伪码3 7 图4 4f c 算法伪码。3 7 图4 5s p 算法伪码3 8 图4 6u n r o l l 算法伪码3 9 图4 7p e e l 算法伪码3 9 图4 8s u i f 2 系统构架4 0 图4 9s u i f 中间表示的高层对象层次结构4 1 图4 1 0 一个典型的s u i f 2 编译器结构4 4 图4 11s u i f 2 中的p a s s 程序结构4 4 图4 1 2f o r s t a t e m e n t 结构4 5 图4 13 函数s h o w e x p r e s s i o n 算法描述一4 6 图4 1 4d op r ep a s s 流程图4 7 图4 15f o r 循环结构中的执行路径4 8 图4 16c a lr 算法伪码4 8 图5 1 预取单元构架框图5 1 图5 2 预取指令5 1 第1 v 页 国防科学技术大学研究生院学位论文 图5 3 预取硬件单元的工作流程图5 2 图5 4s i m p l e s c a l a r 模拟工具框图5 4 图5 5s i m p l e s c a l a ri 具集工作流程图5 4 图5 6 实验验证流程图。5 7 图5 7c a c h e 失效率对比柱状图6 0 图5 8i p c 对比柱状图。6 l 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 终发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 仁或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 串阼了明确的说明并表示谢意。 学位论文题目： 亘囱遁堡拯邀塑边闻的数量亟墼整盔亟窥 学位论文作者签名：z 垦丛日期：- 二，年 月，9 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅o ，可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 日期： 如 年 ，月彤日 日期：如d 苫年7 月细日 ，l o 国防科学技术大学研究生院学位论文 第一章引言 本章首先说明课题的研究背景及意义，然后在介绍国内外相关研究的基础上，概括本 文的主要工作，给出全文的组织结构。 1 1 课题背景及意义 存储器是“冯诺伊曼计算机系统结构中不可或缺的重要部分。遗憾的是，长久以来， 存储器访问速度和处理器的工作频率之间存在严重的不平衡，它们之间的性能差距逐年增 大，如图1 1 所示【n 。从1 9 8 0 年到1 9 8 6 年间，处理器频率每年增长约3 5 ，1 9 8 7 到2 0 0 2 年间，每年增长约5 5 。自2 0 0 3 年，增速回落至每年约3 5 。与此同时，d r a m 的性能 ( 比如，数据访存延迟) 却进展缓慢，约为7 每年。“存储墙问题已经成了现代计算 机系统性能提升的瓶颈。 图1 1 处理器和主存之间的性能差距 通常计算机的层次存储结构由寄存器、多层c a c h e 和主存组成，离处理器越近，访问 速度越快，但容量越小，离处理器越远，访问速度越慢，但容量也越大，如图1 2 所示 2 1 。 程序运行时，经常喜欢重复访问最近访问过的数据，重复使用最近使用过的指令，这种性 质叫做程序的局部性【4 5 】。访存的局部性主要是针对数据而言。层次存储结构将处理器最近 最常访问的数据放在最靠近它的地方，减少了平均数据访问时间。但是，即使使用多层 c a c h e ，许多程序的执行时间依然大多花在数据访问的延迟上。从m o w r y 3 1 的论文所用测试 用例的执行时间分类可以看出，平均有近5 0 的执行时间都是存储延迟造成的，个别案例 v p e n t a 的存储延迟时间占了执行时间的7 0 。 第l 页 国防科学技术大学研究生院学位论文 图1 2 层次存储结构 我们从程序的执行时间公式2 1 出发来寻找解决存储延迟问题的方法。程序的执行时间 公式： 执行时间= ( c p u 执行时钟周期+ 访存延迟周期) 时钟周期时间 访存延迟周期= c a c h e 失效次数失效开销 平均访存时间是衡量性能的一个间接指标，它的两个组成部分既可以用绝对时间( 如 命中时间为2 n s ) ，也可以用时钟周期数( 如失效开销为5 0 个时钟周期) 来衡量。 平均访存时间= 命中时间+ 失效率失效开销 由这两个公式可知，c a c h e 失效开销大或者失效次数多都会增加程序执行时间，影响 系统性能。减少c a c h e 失效开销，或者减少c a c h e 的失效次数，都能够有效的降低程序的 执行时间，提高系统性能。 为了降低程序的执行时间，可以采用多种方法。通过软件的方式，比如局部性优化技 术，增加程序中访存的局部性，可以减少程序的执行时间，提高性能。虽然局部性优化技 术可以改善程序的访存性能，却并不能改变命中时间和失效损失，本质上只是减少c a c h e 失效次数。而且访存的局部性受多种因素影响，极易变化，对源代码或者机器平台的看似 轻微的修改却会导致局部性的巨大变化。 数据预取技术是另一种减少存储延迟的方法。它和局部性优化技术不同，局部性优化 的目标是减少主存访问的次数，而数据预取技术则是隐藏访存延迟。像非阻塞c a c h e 、软 件预取、硬件预取和流缓冲器等技术，它们将访存和计算重叠起来，隐藏了访存延迟，提 升了访存性能。预取是建立在利用存储器的空闲频带的基础上的，数据预取操作的目的是 提前将数据从远离处理器的存储层次上移动到靠近处理器的存储层次上，甚至是寄存器 中，以减少数据使用时的访存延迟等待。预取操作和处理器的计算过程并发进行，存储系 第2 页 国防科学技术大学研究生院学位论文 统提前一定的时钟周期将数据从主存读取到c a c h e 中。理想情况下，数据预取能够为微处 理器及时提供所需的数据，从而避免处理器阻塞。 1 2 研究现状 多媒体应用和科学计算程序都是微处理器的主要负载，其中多媒体应用工作负载已经 占据了大多数个人电脑计算量的9 0 左右，并且这一比例还在增长。循环处理是多媒体应 用和科学计算应用的核心，在程序的运行过程中几乎占用了9 0 以上的时间。核心循环体 是循环的核心与关键，大多数多媒体应用在最内层循环花费了8 0 - - 9 0 的执行时间，而在 最内层和次内层循环中则合计花费了几乎9 5 的执行时间p 引。 循环处理是多媒体应用程序的关键，也是整个计算机应用程序的核心，循环处理能力 的好坏在很大程度上决定了一个计算机系统整体性能的好坏。有的研究人员甚至在体系结 构方面了展开了尝试，提出了一种专门针对核心循环的新的体系结构模型叫，e a p ( l o o p e n g i n eo l la r r a yp r o c e s s o r ) 【4 1 。l e a p 是一个可以加速核心循环程序的单芯片阵列处理器体 系结构，它包含一个循环控制部件和若干计算单元( p e ) ，每个计算单元( p e ) 仅是一个 具有指令和操作数存储功能的a l u ，执行基本表达式语句，各计算单元通过高速通道连接， 直接传递数据。循环控制部件负责将最内层循环的数据相关图直接映射到循环阵列上执 行。l e a p 面向最内层简单循环，可以很好的挖掘出程序中广泛存在着的面向循环的粗粒度 数据级并行性。l e a p 循环控制部件是该体系结构的一个关键和难点。因为实现将最内层 循环内数据相关图到循环阵列的映射，首先必须识别出最内层循环，并获得最内层循环内 的数据相关图，这需要软件的协作。 这样的创新研究很有学术意义，但在通用微处理平台上，预取技术依然是解决循环级 数组访问延时问题的有效手段。 。 硬件预取主要利用程序的实时运行信息，推断可能的预取对象，进行预取调度，插入 预取操作。硬件预取大都采用顺序预取的方式，即预取当前正在访问的数据块的相邻块， 适合于线性访问模式。它不需要在指令流中插入明显的预取指令，指令开销小，除了能有 效预取线性数组外，还适用于多种数据结构的预取，比如指针访问型、链表型。但是硬件 预取实现代价巨大，而且预取操作具有盲目性。预取操作的有效性和程序特点有关，如果 指令流中分支跳转指令较多的话，硬件预取操作很难提高程序性能。 软件预取首先对程序进行静态的编译分析，获取其数据访问的全局信息，寻找发觉那 些可能会失效的访存操作集合，针对这些可能的失效访问，提前一定的时间量插入预取指 令，确保数据在实际需要时，可以在c a c h e 中访问到。软件预取可以准确的确定预取对象， 使预取操作更加有针对性。在高效的编译算法帮助下，软件预取技术能够有效的处理链表 指针类数据结构的访存失效问题。但是由于预取指令是静态插入的，不能对程序执行过程 箱3 页 国防科学技术大学研究生院学位论文 中系统的动态信息做出及时反应，比如共享主存多处理器系统中，当存储带宽竞争比较严 重时，预取指令的执行不但不能隐藏延时，而且使这种竞争更加恶化。此外，预取指令会 增大代码体积，带来很大的指令开销。 混合型方案，即软硬件系统协同的预取方案，利用了编译分析时的全局信息，同时避 免了纯软件预取的指令开销，也减少了纯硬件方案中的模糊推断类型的预取操作，提高了 预取效率。虽然，目前没有商用系统支持这种类型的预取，但模拟评测的结果依然表明， 这种方案比纯硬件或纯软件的预取方案更能显著提高系统性能。混合型方案大都依赖于各 种各样的体系结构假设，很难对这些方案做出公正的评价。 目前，有许多商用微处理器，都支持预取操作。比如i a 6 4 中的l f e t c h 指令【5 】，m i p s 3 2 和m i p s 6 4 中的p r e f 指令【6 儿，都是预取操作指令，它们在执行过程中有一些共同特点， 它们或多或少的都需要一定的程序访存的局部性信息提示。 有效的预取方案必须及时，开销小( 无论硬件的，还是软件的) 。然而，预取操作也可 能带来c a c h e 污染和访存带宽竞争等副作用，这些问题也必须予以考虑。尽管如此，数据 预取技术将计算和访存重叠起来，隐藏了访存延时，确实能够有效减少程序执行时间，提 高系统的性能。 如前所述，软件预取技术虽然可以准确分析出那些可能会失效的数据访问操作，但是 该类方案受系统平台参数( 比如，访存延迟周期，存储带宽等) 的影响很大，不能高效的 插入预取操作。很多时候，预取的数据过早到达c a c h e ，导致严重的c a c h e 污染问题。如 果预取过于频繁的话，平均访存时间将会增大，预取的数据很晚才到达c a c h e ，造成严重 的浪费。硬件预取方案根据程序运行的动态信息，自动推断可能会发生失效的访存操作， 并发出预取操作。由于不了解程序的全局信息，这样的预取具有盲目性，效率不高，而且 硬件代价大。但是通过程序特征分析和实践都很容易知道，科学计算程序里，循环中的数 组访问模式比较规整，线性访问模式占绝大部分，具有很强的空间局部性，很适合于顺序 预取方案。基于以上的认识，为了有效的隐藏循环中的数据访问的延时，提高数据c a c h e 利用率，本课题采取的是一种软、硬件协同的预取方案。 该方案包括硬件和软件两个部分。软件部分的工作主要是由编译器完成，负责确定预 取对象，进行预取调度，插入预取指令。而硬件预取单元主要负责预取指令的执行工作， 一旦接收到预取指令，就按照指令的要求将数据读入c a c h e 中。总的说来，编译器可以根 据访存的全局信息，选择最有可能失效的数据访问操作进行预取，高效的预取分析算法可 以剔除不必要的预取操作，减少指令开销。同时，准确的预取调度可以确保预取操作的及 时性，隐藏访存延时，提升系统的性能。科学计算程序中的访存绝大多数是以顺序访问为 主的，而顺序预取硬件单元可以有效地处理这类访存模式的预取问题，在编译分析的指导 下，更是大大减少了预取的盲目性，提高了预取效率。这样种软硬件协同的工作模式， 在处理科学计算中循环级数组访问的预取问题上很有优势。 第4 页 国防科学技术大学研究生院学位论文 1 3 课题研究内容和主要工作 课题的目标是设计并实现一种针对循环级数组访问的数据预取技术方案，同时对该方 案的性能进行验证。数据预取技术需要考虑的关键问题有三个，什么时候预取，预取对象 是什么，预取对象存放位置。本文的研究内容就从这三个方面展开，具体来说包括两个部 分，即编译分析部分和顺序预取单元的设计与模拟验证部分。 编译分析部分包括： 1 预取对象。预取对象是指循环中，那些可能会导致c a c h e 访问失效的数据访问操 作集合。程序的局部性原理告诉我们，程序中数据存在重用关系，在c a c h e 无限 大的情况下，再次访问该数据时，可以在c a c h e 中找到它，不会失效。但是，c a c h e 的容量是有限的，使用过的数据会被替换出去。此外那些第一次被访问的数据， 也会导致c a c h e 失效。在映射规则中，许多数据会映射到相同的c a c h e 位置，导 致该位置原有的数据也会被替换。不论是哪种原因的失效，都会导致很长的访存 延时。编译分析的一个重要工作就是，确定这些潜在的失效访问操作组成的集合。 2 预取调度。在确定预取对象后，最简单的方法就是将预取指令包装在条件语句中， 直接插入到循环内部。但是这种做法带来巨大的指令开销，不是最好的方案。预 取调度过程中，如何在尽可能不增大代码量的前提下，插入预取指令也是一个值 得讨论的问题。+ 3 预取度问题。预取度是指一次预取操作读入的数据量，一般以c a c h el i n e 为基本 单位。具体的c a c h el i n e 大小与硬件实现有关。在不同的c a c h e 配置下，同一个 测试程序的失效次数是不同的，有的研究人员把这类问题叫做c a c h e 的多态性。 合适的预取度可以弥补c a c h e 的多态性对程序造成的影响，此外也可以减少程序 对访存带宽的压力，同时弥补预取调度时一些模糊因素对预取效率的影响，提高 预取准确性。 预取硬件单元部分包括： 1 预取指令的设计。预取指令的作用主要是启动预取智能体，它携带了硬件单元执 行预取操作所需的各种信息。同时，预取指令也有其特殊性，比如说，预取指令 执行时，如果遇到缺页等异常，它是不需要处理的 2 顺序预取单元的软件模拟验证。前面讨论的各种算法和设计，都需要一个模拟验 证环境来验证其有效性。如何正确建模预取单元的行为也是本课题的一个重点。 第5 页 国防科学技术大学研究生院学位论文 1 4 论文结构 全文共分为六章。 第一章，首先说明课题的研究背景及意义，然后在介绍国内外相关研究的基础上，概 括本文的主要工作和创新，最后给出文章的组织结构。 第二章主要介绍国内外关于预取技术方面的研究现状，包括软件预取技术、硬件预取 技术、混合型预取方案，同时也介绍了典型体系结构平台如i a 6 4 、m i p s 3 2 对预取操作的 支持。该章节最后介绍了著名开源编译器g c c 对预取的支持。 第三章首先讨论了循环级数组访问预取的特点，然后结合例子介绍了各种相关的编译 分析过程，包括重用分析、局部性分析、预取条件、预取调度、循环分裂等。该章节最后 重点讨论了预取调度的问题，针对现有研究中的不足，改进了预取距离算法，并提出新的 预取度算法。 第四章详细描述了编译分析过程中的主要算法，讨论了各个算法对预取的影响并结合 s u i f 2 编译平台，介绍了算法实现情况。 第五章主要是包括两个部分，第一部分介绍顺序预取硬件单元的设计和模拟问题。首 先介绍了预取指令设计、指令执行过程，然后讨论了硬件单元的工作模型，最后介绍了硬 件单元在s i m p l e s c a l a r 平台上建模及其模拟验证问题。第二部分是实验部分，首先介绍了 实验用的测试程序，然后对实验流程和实验结果进行了说明，最后针对实验结果进行讨论 总结。 第六章是总结。该章节总结了本课题的主要工作的和贡献，同时也对存在的问题进行 了反思，最后对后续工作进行了展望。 第6 页 国防科学技术大学研究生院学位论文 第二章相关研究工作 本章首先讨论了预取技术的三个关键问题，接着介绍了国内外关于数据预取技术方面 的研究现状，包括软件预取技术、硬件预取技术、混合型预取方案、g c c 对预取的支持等 嘲，同时也介绍了典型体系结构平台如认6 4 【5 1 、m i p s 3 2 6 1 、m i p s 6 4 t t 、舢p h a 例对预取操 作的支持。该章节最后对预取技术进行了总结。 2 1 预取的三个基本问题 数据预取不是在c a c h e 失效时才进行访存操作，而是预测这些失效情况，提前访问主 存，读取数据。预取访存操作和处理器的计算过程并发进行，存储系统提前一定的时钟周 期将数据从主存读取到c a c h e 中。理想情况下，数据预取能够为微处理器及时提供所需的 数据，从而避免处理器阻塞。 ol o2 0；o 4 0 li 叵亟二二亘匠亘! j 至登亟三二】 图2 1 程序片段执行框图( a ) 没有预取( b ) 理想预取( c ) 非理想预取 图2 1 ( a ) 和图2 1 ( b ) 的对比，直观的显示了预取可以减少执行时间。这里，计算和访存 的并行隐藏了访存延迟，提高了程序执行效率。图中显示的是一种理想情况，即预取的数 据恰好及时响应微处理器的访问请求。图2 1 ( c ) 显示的是一种不太乐观的情景，r l ，r 2 的 预取操作发出的太晚，以至于不能完全避免处理器的空转。而r 3 又预取的过早，虽然隐藏 了访存时延，但在被使用之前，它将保存在c a c h e 中一段时间，这段时间内，预取的数据 第7 页 国防科学技术大学研究生院学位论文 依然受c a c h e 替换策略( l r u ，f i f o 等) 的管理，有可能在使用之前被替换出c a c h e ，这 样的预取毫无意义。同时，如果预取的数据直接放到c a c h e 中，由于c a c h e 容量有限，有 可能导致有用数据被预取数据替换，引起c a c h e 污染，增加失效率，这样的预取同样意义 不大。另外，预取访存操作加剧了对总线等共享资源的竞争，访存带宽占用问题不容忽略。 预取技术的研究主要围绕三个问题展开，即什么时候预取，预取对象是什么，预取对 象存放位置。 预取有多种发起方式，由程序中的嵌入的预取指令发起，或者由一直监视处理器访存 模式的硬件逻辑推断发起，或者这两种方式的组合。不论由什么方式发起，预取操作必须 及时发出。预取过早，则有可能预取数据会替换有用数据，或者在使用之前被替换掉。预 取过晚，在需要访问数据时，它尚未到达，可能引入定的处理器延迟。另外，软件预取 和硬件预取的精度不同，软件预取的对象是那些可能会使用到的数据，而硬件预取采用一 种推断的方式进行。 预取数据在存储层次中何处存放是一个重要的问题。为了提升性能，数据应该放在离 处理器近的地方。绝大部分的方案将预取的数据放在某种形式的c a c h e 存储器中。有的方 案将预取数据放在专用的缓冲当中，避免c a c h e 的提前替换或者避免c a c h e 污染。当预取 数据放到命名了的空间时，比如处理器的寄存器或者主存中，称之为绑定型预取，使用数 据时，必须考虑一些额外的限制条件。多处理器系统在单机存储层次结构基础上引入了新 的问题，考虑多处理器系统的预取问题，必须把这些问题考虑进去。 数据可以以多种粒度为单位预取，单字、c a c h e 块、内存的连续块或者程序中的数据 对象。通常情况下，预取数据的量是由底层c a c h e 和主存系统的结构决定的。对s m p 和 单处理器系统而言，c a c h e 块是最适合的大小，而对分布式存储多处理机而言，预取更大 块的内存数据可以弥补互联网络传输数据的开销。 在下面介绍的各种方案中，无论是软件预取还是硬件预取，都是围绕着这三个基本问 题展开的。 2 2 硬件数据预取 硬件预取利用专门的硬件单元，跟踪程序的实时访存行为，推测并执行可能的预取操 作。它的特点是不需要插入明显的预取指令，指令开销小，但是预取操作的准确度不高。 2 2 1 顺序型硬件预取 顺序预取主要是利用了程序的空间局部性特点，最简单的顺序预取是o b l ( o n eb l o c k l o o k a h e a d ) t 10 1 ，即在访问块b 时，预取块b + l 。一般来说，o b l 顺序预取实现方案有两种 1 l l ，“失效时预取( p r e f e t c ho nm i s s ) 和“标志型预t r ( t a g g e dp r e f e t c h ) 。“失效时预取” 第8 页 国防科学技术大学研究生院学位论文 是指当访问c a c h e 块b 不命中时，预取块b + l 。如果块b + l 已经存在于c a c h e 中，则不访 问主存。“标志型预取 为每一个主存块加一个标志位，如果某块是适时取( d e m a n d f e t c h e d ) 或者某预取块被第一次访问，则其随后的数据库块也将被取到c a c h e 中。 o b l 方案并不一定能及时的预取到所需要的数据，从而也就不能避免处理器的访存阻 塞。比如，对一个很紧密的循环来说，访问块b 和块b + l 的时间间隔很小，o b l 方案并不 能消除访存延迟带来的空转。为了解决这个问题，可以增大预取块的数目k 。k 也叫做预 取度【1 0 1 ，一次预取k ( k 1 ) 个数据块可以使得c a c h e 能及时满足处理器的访存请求。当 k = i 时，该方案等同于标志位o b l 预取。 对于空间局部性高的程序，增大预取度，可减少失效率。对空间局部性差的程序而言， 大的预取粒度不但不能降低失效率，还会带来额外的访存开销和c a c h e 污染问题。为此， d a h l g r e n 和s t e i l s 仃d m 【1 2 】提出“自适应型顺序预取策略，其中，k 可以根据程序运行当前 时刻的空间局部性自动变化。j o u p p i l l 3 】在此基础上提出了一种新的预取方案，即将k 个预 取块暂时存放在一个先进先出的缓冲队列中。当访问的数据是队列的起始块时，该块被调 入c a c h e 中，后续块在队列中往前移动一个位置，同时预取一个新的数据块放入末尾位置。 这种方案可以避免c a c h e 污染。但是如果c a c h e 不命中时，而且所需访问的数据也不是队 列起始块的话，f i f o 队列将被清空。这样的限制影响了该方案的性能。 2 - 2 2 任意步长的预取 在循环计算结构中，数组的访问一般都是按照固定步长进行的。很多种硬件数据预取 方案( 参考文献 1 4 ，1 5 ，1 6 】) 采用专门的逻辑电路跟踪循环结构中数组的访问模式，推测访 存步长，同时进行预取操作。 c h e n 和b a e r 的方案是这类预取方案中的一个典型代表。假设某访存指令m i ，在连 续三遍循环中访问的地址为a 1 ，a 2 ，a 3 ，如果( a 2 一a 1 ) = a o ，其中假设为数组访问 的步长，则对m i 指令就可以发起预取。第一次预取的地址为a 3 = a 2 + ，也就是循环中 第三遍的访存地址a 3 。预取一直持续到a n = a n 不再成立为止。这种方案需要保存上次访 存指令使用的地址和最近一次推测的步长，可是记录每条访存指令使用的地址信息显然是 不现实的。为此，专用一个名为“访存预测表( 简称r p t ) ”的c a c h e 来保存最近使用的 访存指令的信息。 d a h l g r e n 和s t e n s c r o m 【1 7 】将i 冲t 预取和标志型预取( t a g g e dp r e f e t c h ) 在分布式共享主存 多处理机环境中进行了对比试验。6 个标准测试程序的运行结果显示，r p t 预取的性能和 标志位预取的相差无几。这主要是因为大部分的数组访问步长都小于c a c h el i n e 的大小， 而标志位预取方案是以c a c h el i n e 为单位的，可以很好的处理这种类型的预取。此外，如 果存储带宽有限的话，保守型的r p t 预取方案表现较好，因为它产生的无效预取操作较少。 第9 页 国防科学技术大学研究生院学位论文 和软件预取相比，绝大多数硬件方案专注于解决规整的数组访存的预取问题，也有少 数研究者尝试使用硬件方案解决链表和稀疏矩阵类的访存问题，这类做法往往花费巨大的 硬件代价，效果却不甚理想。 2 3 软件数据预取 这里讨论的软件数据预取主要指的是编译器指导数据预取。编译指导的数据预取一般 分为两种情况，如果目标平台支持预取操作，则编译器可以在指令流中生成相应的预取提 示或者直接是预取指令。如果目标平台不支持预取操作，则编译器可以通过访存指令调度 达到预取的效果。 下面举例说明预取在循环中的作用，以图2 2 ( a ) 中代码段为例。该代码计算两向量a ， b 的内积，采用类似矩阵乘运算最内层循环的方式进行计算。如果假定c a c h e 块的大小为 四个字长，则执行该代码段时，每四次循环会导致一次c a c h e 失效。如图2 2 ( b ) ，如果加 入一些预取指导语句，则可以避免相应的c a c h e 失效情况。 f o r ( i = 0 ；i n ；i + + ) i p = i p + a i 】+ b 【i 】， f o r ( i = 0 ，i n ji + = 4 ) f e t c h ( a i + 4 】) ， f e t c h ( b 【i + 4 】) ； i p = i p + a i 】+ b 【i 】； i p = i p + a 【i + 1 + b i + 1 】， i p = i p + a 【i + 2 】+ b i + 2 】； i p = i p + a 【i + 3 】+ b i + 3 1 ， f o r ( i = 0 ；i n ；i + + ) f e t c h ( a i + 1 】) ， f e t c h ( b i + 1 】) ， i p = i p + a i 】+ b i 】， ) ( b ) f e t c h ( i p ) 7 f e t c h ( a 0 】) ； f e t c h ( b 0 】) ； f o r ( i = 0 ；i n - 4 ；i + = 4 ) f e t c h ( a i + 4 】) ； f e t c h ( b i + 4 ) ， i p = i p + a i + b 【i 】7 i p = i p + a i + l 】+ b i + i 】； i p = i p + a i + 2 】+ b 【1 + 2 ； i p = i p + a i + 3 】+ b 【i + 3 】； f o r ( ，i n ；i + + ) i p 。i p + a 【i 】+ b 【i 】7 ( c )( d ) 图2 2 内积计算代码变形 ( a ) 没有预取( b ) 简单预取( c ) 循环展开( d ) 软件流水 不论是手工插入还是编译器自动生成，预取对于有大量数组参与的循环计算最有效。 这种循环在科学计算中很常见，并且其c a c h e 利用率很低，但由于其数组访问模式具有很 强的可预测性，因此最适合于通过预取进行优化。大部分软件数据预取的研究都是围绕着 这个主题进行的。我们可以认为图2 2 ( b ) 中的代码包含了循环中所有的访存请求，不会导 致c a c h e 失效，因为任何一次访存前都有相应的预取操作。但是，有一个问题却被忽略了。 图2 2 ( b ) 中的代码之所以写成那个样子是因为我们假定了提前一个周期时间的预取就足以 第1 0 页 国防科学技术大学研究生院学位论文 隐藏相应的访存延迟，但大多数情况并非如此。许多早期的研究【拇1 就是基于这个假设丽，。 而k l a i b e r 和l e v y h a l 研究发现这样的假设并不满足一般情形。因此，必须研究预取距离问 题。 2 3 1 预取距离 当循环中包含的计算体较小时，往往需要在数据被访问前万个周期进行预取。8 也叫 做预取距离2 0 1 ，一般表示为多少个循环周期。循环运算中预取距离万可以这样来计算，首 先假设下面四个变量： 是没有预取时，一次循环所需的时钟数。假定所需的数据都在c a c h e 中。 k 是一次循环中从循环开始到某数据第一次使用经过的时钟数 锄是发射预取指令的延时 。 易万是执行预取指令所需的时钟数，在预取指令发射( 易矿知劫时钟后，预取的数 据到达c a c h e 没有预取时，假设某数据的第i 次使用时间为 k + j 幸k ，i = o ，1 ，2 则有预取时，第i 次使用时间为 k + f