（计算机科学与技术专业论文）合并与分割——访存数据流优化方法研究.pdf

国防科学技术大学研究生院学位论文 摘要 并行是提高计算机性能的有效途径之一，并行技术可分为单处理器内的并行以及将 多个处理器互连构成的并行两个层次。本文将单处理器内的并行称为结点内并行，将利 用多个处理器互连构成的并行称为结点间并行。结点内并行的一种发展趋势是同时支持 指令级并行和数据级并行，s t a n f o r d 大学研制的i m a g i n e 流处理器是同时支持指令级并 行和数据级并行的典型代表。结点间广泛应用的一种并行体系结构是分布共享存储 ( d s m ) 多处理机，其主要优势是可扩展性好并且并行编程模型简便。两个层次的并 行性能的充分发挥都受到存储访问延迟和带宽的约束( 所谓的“存储墙”问题) 。对结 点间并行，除了“存储墙”问题外，伪共享是严重影响并行性能的另一个问题。 为了解决“存储墙”问题，当前的计算机大都采用层次存储结构。支持结点内并行 的层次存储结构有c a c h e 层次存储和流式层次存储( 本文中统称为结点内层次存储) ， 其中，c a c h e 层次存储强调降低存储延迟，流式层次存储则强调提高存储带宽。支持结 点间并行的层次存储( 简称为结点间层次存储) 在结点内层次存储的基础上增加远地内 存，本文将由本地内存和远地内存构成的层次称为分布存储。层次存储结构的有效利用 依赖于访存数据流的优化，有两种方法可以优化访存数据流：改变程序对内存单元的访 问顺序和改变数据在内存中的布局。前一种优化方法起步早，相对较成熟，数据布局优 化则是近年来研究较多的一种优化方法。 本文面向结点内层次存储和分布存储，着重研究了通过优化数据的布局来有效利用 各级存储器、优化访存数据流性能的编译优化方法。对强调提高存储带宽的流式层次存 储，除了研究数据布局优化外，还研究了通过计算核心( k e r n e l ) 合并来优化访存数据 流的方法。本文的创新工作主要体现在如下几个方面： 1 ) 面向分布存储的访存数据流优化 结合在软件分布共享存储( s d s m ) 系统上实现o p e n m p 并行编译器的过程中遇到 的性能问题，研究了如何通过共享数组的合理布局来优化访存数据流的问题，提出了如 下两种优化方法： 针对s d s m 系统上大粒度共享单元( 共享页) 导致小共享数组的伪共享问题， 以及大步长数组访问模式导致的共享页利用率低的问题，提出了共享数组交叉合并优化 方法，此方法将程序中总是同时出现的多个共享数组按照一定的规则进行合并。测试结 果表明，此方法能有效减少分布共享存储多处理机上小共享数组应用的伪共享、提高大 步长数组访问应用的本地局部性。 针对某些s d s m 系统上共享单元粒度较小( 例如c a c h e 块) 以及o p e r a 程序 中共享数组分布的对准问题，分析了共享数组交叉合并优化方法的不足，提出了基于数 据访问轨迹对准的数组融合方法。此方法能在数组合并的同时对准数组的访问轨迹，使 第1 页 国防科学技术大学研究生院学位论文 得融合后的数组能提高c a c h e 块等小粒度共享单元的利用率。对于大粒度共享页，此方 法能对准共享数组的分布，减少处理机之间的通信。测试结果表明，基于数据访问轨迹 对准的数组融合方法能够获得比共享数组交叉合并方法更高的性能提升。 2 ) 面向结点内层次存储的访存数据流优化 面向结点内的c a c h e 层次存储和流式层次存储，提出了如下访存数据流优化方法： 面向结点内的c a c h e 层次存储，结合f o r t r a n 语言中并行语法成分的优化实现问 题，提出了利用临时数据空间合并来提高编译器目标代码性能的优化方法，并在g 9 5 开放源码编译器中实现了这种优化。g 9 5 和i n t e le f c 编译器的对比测试结果表明，对 f o r t r a n 语言中典型的并行语法成分包含数组赋值语句的f o r a l l 结构，临时数据 空间合并优化能有效提高编译器产生的目标代码的性能。测试结果还表明，循环排序优 化和l f 缶时数据空间合并优化的综合运用，进一步提高了目标代码的性能。 面向结点内支持数据并行的流式层次存储，分析了典型的流体系结构及其编程 模型，提出了流分割和线性k e r n e l 合并两种优化方法，并使用i m a g i n e 软件模拟平台， 测试了两种方法的优化效果。测试结果表明：流分割优化能显著提高带宽层次存储的利 用率，改善流处理器内的并行；线性k e r n e l 合并优化能有效减少k e r n e l 的调用次数和流 在各级存储器中切换所花费的时间，从而提高流应用在流处理器上的性能。 关键词：编译优化，访存数据流优化，数据布局优化，层次存储，分布共享存储，伪共 享，流处理器 第1 l 页 里堕型兰丝查盔兰婴壅生堕堂垒丝苎 a b s t r a c t p a r a l l e l i s mi so n eo ft h ee f f e c t i v et e c h n o l o g i e st oi m p r o v et h ep e r f o r m a n c eo fc o m p u t e r s t h et e c h n o l o g yo fp a r a l l e l i s mo a nb ec l a s s i f i e di n t o i n t r a - p r o e e s s o rp a r a l l e l i s ma n d i n t e r - p r o e e s e rp a r a l l e l i s m o n eo ft h et r e n d so fi n t r a - p r o c e s s o rp a r a l l e l i s mi st os u p p o r tb o t h 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 ) a n dd a t a - l e v e lp a r a l l e l i s m ( d l p ) t h ei m a g i n es t r e a m p r o c e s s o rd e v e l o p e db ys t a n f o r du n i v e r s i t yi sa ni l p - d l pr e p r e s e n t a t i v e d i s t r i b u t e ds h a r e d m e m o r y ( d s m ) m u l t i p r o e e s s o rb c t 3 0 m e saw i d e s p r e a di n t e r - p r o c e s s o rp a r a l l e la r c h i t e c t u r e b e c a u s eo fi t ss e a l a b i l i t ya n ds t r a i g h t f o r w a r dp r o g r a m m i n gm o d e l t h ep e r f o r m a n c eo fb o t h i n t r a - p r o c e s s o ra n di n t e r - p r o c e s s o rp a r a l l e l i s mi sr e s t r a i n e db yt h el a t e n c ya n db a n d w i d t ho f m e m o r ya c c e s s t h i si sc o m m o n l yc a l l e dt h em e m o r y 砌盯p r o b l e m f o ri n t e r - p r o c o s s o r p a r a l l e l i s m , f a l s es h a r i n gi sa n o t h e ro b s t a c l et og a i n i n gh i g hp e r f o r m a n c e t os o l v et h em e m o r yw a l lp r o b l e m , m e m o r yh i e r a r c h yh a sb e e nu s e de x t e n s i v e l yi n c u r r e n t c o m p u t e rs y s t e m s f o ri n t r a - p r o c e s s o rp a r a l l e l i s m , t h el a t e n c y - o r i e n t e d c a c h e h i e r a r c h yi su s e di nt r a d i t i o n a lp r o c e s s o r s a n dt h eb a n d w i d t h - o r i e n t e ds t r e a mh i e r a r c h yi s u s e di ns t r e a mp r o c e s s o r s t h ec a c h eh i e r a r c h ya n dt h es t r e a mh i e r a r c h ya r eg e n e r a l l yc a l l e d t h em e m o r yh i e r a r c h yi nap r o c e s s o r ( m h p ) f o ri n t e r - p r o c e s s o rp a r a l l e l i s m , d i s t r i b u t e d m e m o r ya m o n gp r o c e s s o r s ( d m p ) i s u s e d t h ee f f e c t i v e n e s so f m e m o r yh i e r a r c h i e si sm a i n l y d e t e r m i n e db yt h eo p t i m i z a t i o no fm e m o r y - a c c e s s s e q u e n c e t h em e m o r y - a c c e s s - s e q u e n c e o fap r o g r a mc a l lb ei m p r o v e db yi n s t r u c t i o no p t i m i z a t i o na n dd a t a - l a y o u to p t i m i z a t i o n t h e d a t a - l a y o u to p t i m i z a t i o ni sr e c e n t l ym o r ea c t i v et h a n t h ei n s t r u c t i o no p t i m i z a t i o n i nt h i sp a p e r , s e v e r a ld a t a - l a y o u ta p p r o a c h e sa r ep r o p o s e dt om a k ef u l lu s eo fm e m o r y h i e r a r c h i e s a n dt o i m p r o v et h ep e r f o r m a n c eo fm e m o r y a c c e s s s c q u e n c , e f o r b a n d w i d t h - o r i e n t e ds t r e a mh i e r a r c h y , l i n e a rk e r n e lf u s i o na p p r o a c hi sa l s or e s e a r c h e db e s i d e s d a t a - l a y o u ta p p r o a c h e s 低舯呻i n n o v a t i v ew o r ki nt h i sp a p e rc a nb es u n l m a r i t 捌a s f o l l o w s ： 1 ) d m p - o r i e n t e dm e m o r y - a c c e s s - s e q u e n c eo p t i m i z a t i o n t os o l v et h ep e r f o r m a n c ep r o b l e m so fo u ro p e n m p s d s mc o m p i l e r , t h ef o l l o w i n gt w o a p p r o a c h e sa l ep r o p o s e d ml a r g es h a r e dg r a n u l a r i t y ( u s u a l l ym e m o r yp a g e ) i ns d s mo f t e nc a u s e sf a l s e s h a r i n gf o rp r o g r a m sw i t hs m a l ls h a r e da r r a y s ，a n dc a u s e sp o o rm e m o r yl o c a l i t yf o rp r o g r a m s w i t hl a r g e s t r i d ea r r a ya c e e s s s h a r e da r m yf u s i o n ( s a f ) ，m e r g i n gs h a r e da r r a y sw h i c h a l w a y sa p p e a r e dt o g e t h e ra c c o r d i n gt oc e r t a i nr u l e s i su s e dt oe l i m i n a t ef a l es h a r i n ga n dt o i m p r o v em e m o r yl o c a l i t y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ts a f i se f f e c t i v e 第1 i i 页 国防科学技术大学研究生院学位论文 s a fi sn o ts u f f i c i e n te n o u g hf o rs d s mw i t hs m a l ls h a r e dg r a n u l a r i t y ，e g ，c a c h el i n e a r r a y f u s i o nb a s e do nd a t aa c c e s st m c ea l i g n m e n t ( b d a t a - a f ) i sp r o p o s e d i tc a na l i g n t h ed a t aa c c e s st r a c ew h i l em e r g i n ga r r a y s 1 1 l i sa p p r o a c hc a l li n c r e a s et h eu t i l i t yo fs m a l l s h a r e dg r a n u l a r i t y f o rs d s mw i t hl a r g es h a r e dg r a n u l a r i t y , b d a t a a fc a na l i g nt h e d i s t r i b u t i o no fs h a r e da r r a y sa n dt h e nr e d u c et h en u m b e ro fr e m o t em e m o r ya c c e s s 啊1 e e x p e r i m e n t a lr e s u l t ss h o wt h a tb d a t a - a f i sm o r ee f f i c i e n tt h a ns a f 2 、m h p o r i e n t e dm e m o r y - a c c e s s - s e q u e n c eo p t i m i z a t i o n t om a k ef u l lu s eo f t h em e m o r yh i e r a r c h i e si nap r o c e s s o r , t h ef o l l o w i n ga p p r o a c h e sa r e p r o p o s e d f o rt h ec a c h eh i e r a r c h yi nt r a d i t i o n a lp r o c e s s o r s ，t h eo p t i m a li m p l e m e n t a t i o no ft h e p a r a l l e ls y n t a xi nf o r t r a ni sm a i n l yr e s e a r c h e d ，a n dt e m p o r a r yd a t as p a c ef u s i o n ( t d s f ) i s p r o p o s e dt oi m p r o v et h ep e r f o r m a n c eo ft h eo b j e c tc o d e w ei m p l e m e n t e dt h i sa p p r o a c hi n g 9 5o p e ns o u r c ec o m p i l e r t h et e s tr e s u l t so fg 9 5a n di n t e le f cc o m p i l e rs h o wt h a tt d s f c a no b v i o u s l yi m p r o v et h ep e r f o r m a n c eo ft h o s ef o r a l l st h a ti n c l u d ea r r a ya s s i g n m e n t s t a t e m e n t s a n dt h ep e r f o r m a n c eo ff o r a l l sc a nb ef u r t h e ri m p r o v e db yc o m b i n i n gt d s f a n dt h el o o ps o r t i n go p t i m i z a t i o n f o rt h es t r e a mh i e r a r c h yi ns r e a i up r o c e s s o r , b ya n a l y z i n gt h ea r c h i t e c t u r ea n d p r o g r a m m i n gm o d e lo ft y p i c a ls t r e a mp r o c e s s o r , s t r e a mp a r t i t i o n ( s p ) a n dl i n e a rk e r n e l f u s i o n ( l k r ) a r ep r o p o s e d 1 1 1 et e s tr e s u l t so ni m a g i n es i m u l a t o rs h o wt h a tns pc a nm a k e t h eb e s tu s eo ft h eb a n d w i d t ha n d 豇i h 锄c et h ep a r a l l e l i s mi ns t r e a n lp r o c e s s o r 2 1l k fc a n r e d u c et h en u m b e ro f k e r n e lc a l l s , a n dr e d u c et h et i m ew h i c ht h es t r e a ms p e n d si ns w i t c h i n g b e t w e e nv a r i o u s m e m o r yl e v e l s k e y w o r d s ：c o m p i l e ro p t i m i z a t i o n s ，m e m o r y - a c e e s s - s e q u e n c eo p t i m i z a t i o n s ， d a t a - l a y o u to p t i m i z a t i o n s ，m e m o r yh i e r a r c h i e s ，d i s t r i b u t e ds h a r e dm e m o r y ( d s m ) ， f a l s es h a r i n g ，s t r e a mp r o c e s s o r 第1 v 页 国防科学技术大学研究生院学位论文 图表索引 典型的结点间层次存储结构4 典型的流式层次存储结构4 f i e l dr e o r d e r i n g 优化1 l i n s t a n c ei n t e r l e a v i n g 优化1 l 文章的组织结构图1 8 共享数组交叉合并前后数组元素之间的对应关系3 0 t e s t l 的数据分布3 1 t e s t l 中数组合并后的数据分布3 2 s a g 叶+ 对源代码的转换过程3 8 s d s m 系统上共享数组交叉合并优化性能测试结果4 0 s d s m 系统上共享数组交叉合并优化后测试题的性能提高情况4 l c c - n u m a 系统上共享数组交叉合并优化性能测试结果4 l c c 小m a 系统上共享数组交叉合并优化后测试题的性能提高情况4 2 共享数组分布和数据访问模式4 4 数组空间变形示意图4 5 数组合并前的数组空间和数据访问轨迹4 7 数组合并后的数组空间和数据访问轨迹4 7 平面平移前后的数据访问轨迹4 8 编译分析结构图5 6 两种优化方法的性能测试结果比较5 8 两种优化方法的性能提高比较5 9 临时空间的分配情况6 2 临时数据空间合并后的内存空间图6 2 f o r a l l 结构实现时的两种临时空间组织方法6 9 f o r a l l 结构实现时的两种循环嵌套方法6 9 g c c 编译器内部结构7 l 临时数据空间合并和嵌套循环排序优化效果7 5 r a w 处理器结构及其互连模块7 8 流处理器i m a g i n e 的体系结构7 9 i m a g i n e 的三级层次存储连接关系。8 1 i m a g i n ec l u s t e r 的内部实现细节8 1 流处理器编程模型例子8 3 i s i m 编程模型8 4 单条流时的s r f 利用情况8 6 两条流时s r f 的利用情况8 7 f i r - 2 算法两种实现方式下的k e r n e l 代码。9 0 流的不同组织方式对k e r n e l 指令数及k e r n e l 代码装入时间的影响比较9 2 例5 1 中的数掘组织成2 输入流1 输出流时i m a g i n e 资源使用情况9 3 例5 1 中的数据组织成4 输入流1 输出流时i m a g i n e 资源使用情况9 3 第i i i 页 l 2 3 4 5 l 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 l 2 3 4 5 6 1 2 3 4 5 6 7 8 9 l l l 1 1 l 1 l 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图图 里堕型堂垫查盔堂塑茎竺堕兰堡丝茎 图5 1 3 例5 1 中的数据组织成4 输入流2 输出流时i m a g i n e 资源使用情况9 4 图5 1 4 例5 1 中的数据组织成6 输入流2 输出流时i m a g i n e 资源使用情况9 4 各种数据布局优化的比较1 2 s d s m 系统上o p e n m p 测试程序情况说明2 7 s d s m 系统上o p e n m p 测试程序测试结果2 7 s d s m 系统上o p e n m p 测试程序对应的加速比2 7 t e s t l 和t e s t 2 在8 处理机s d s m 上的测试结果3 3 共享数组交叉合并优化测试程序特征3 9 e f c 编译器和g 9 5 编译器比较7 2 i a 6 4 服务器的层次存储结构及特性。7 4 循环排序对t e s t l 的性能影响，7 4 临时空间合并优化对t e s t l 的影响7 5 队p i 收集的关于t e s t 2 的信息7 6 p a p i 收集的关于t e s t 3 的信息7 6 流的不同组织方式对k e r n e l 程序运行时间的影响9 2 f i r - 2 算法i m a g i n e 实现方式l 的性能数据。9 4 f i r - 2 算法i m a g i n e 实现方式2 的性能数据。9 4 例5 1 的模拟性能数据9 7 第i v 页 l l 2 3 4 5 l 2 3 4 5 6 l 2 3 4 1 2 2 2 2 2 4 4 4 4 4 4 5 5 5 5 表表表表表表表表表表表表表表表表 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：佥羞当金耋| = = 边盔熬堡速佳丝友洼盈究 学位论文作者签名：羔譬- j 啦 日期：加名年争月日 学位论文版权使用授权书 本入完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：佥羞曼金割= = 边盔熬堑速盐毡左洼丑窒 学位论文作者签名：耍匦茎 作者指导教师签名 日期：锄名年勿月日 b 瓤：的s 年警al b 里堕型兰垫查查兰竺窒竺堕兰生堡茎 第一章绪论 1 1 研究背景 1 1 1 并行处理层次及其瓶颈问题 并行是提高计算机性能的有效途径之一，并行技术可分为处理器内的并行和由多个 处理器互连构成的并行两个层次，文中将处理器内的并行称为结点内并行，将利用多个 处理器互连构成的并行称为结点间并行。两个层次的并行性能的充分发挥都受到存储访 问延迟和带宽的约束( 即所谓“存储墙”问题) ，对结点间并行，除了“存储墙”问题 外，伪共享是严重影响并行性能的另一个问题。 1 1 1 1 结点内的并行 目前，通用处理器通常通过开发指令级并行( i l p ) 来提高性能，常用的并行结构 包括流水超流水、超标量和超长指令字( v l l w ) 。流水超流水结构用于提高主频， 开发指令间的时间并行性；超标量和v l i w 结构用于增加指令发射和执行的并行度，开 发指令间的空问并行性。 指令级并行技术使得处理器运算速度增长很快。然而，处理器运算速度和访存速度 上的不匹配，使得处理器因等待存储访问而经常出现停顿，不能充分利用多发射硬件提 供的i l p 能力，存储系统因此而成为影响计算机系统整体性能的个关键因素【”。 另外一个方面，硬件的复杂度 9 1 ( 大指令窗口和大寄存器文件) 制约了i l p 的进一步 提高，应用领域的扩展又使得传统的i l p 处理器不足以支持新应用( 如多媒体领域的流 应用) 中大量的并行，因而，处理器有必要开发指令级并行以外的其它并行( 如数据并 行) 。i n t e l 公司的m m x 和s s e 技术【1 2 1 就是面向多媒体领域的数据并行特征，通过对传统 i l p 处理器进行扩展，使得一条指令可以同时对多个数据进行操作，从而增强处理器对多 媒体信息的处理能力( 这类并行被称为s u b w o r d 并行) ，但由于处理器中运算单元的匮乏， m m x 和s s e 不能很好地开发大粒度的数据并行性。向量处理器采用编码效率极高的向量 指令，提供大量的运算部件和高带宽的数据访问能力以匹配计算密集的数据并行应用， 能很好地支持数据并行。s 恤曲r d 大学研制的i 删培i n e 流处理器1 1 1 , 1 3 j 则对向量体系结构进 行改进，将向量指令扩展为v l i w 指令，综合利用了多种并行技术来支持流应用。总而 言之，为支持新应用中大量的并行，结点内并行技术的一种发展趋势是同时支持指令级 并行和数据级并行。 结点内并行技术的发展将大大提高处理器内部指令执行的并行度，但是指令和数据 第1 页 国防科学技术大学研究生院学位论文 的供应进一步成为影响并行性能发挥的关键因素。综合利用多种并行技术的处理器不仅 对存储延迟有较高的要求，还对存储带宽提出了更高的要求。虽然已有许多研究工作致 力于减d 隐藏存储延迟并增加存储带宽，比如，利用非阻塞c a c h e 、c a c h e 旁路、硬件 和软件的指令和数据预取、乱序取指、取数推测和推测执行、流式缓存、多线程技术等 来减小或隐藏存储延迟，利用多体交叉并行存储和层次存储带宽来增加存储带宽，但是， 处理器运算速度与访存速度的差距仍在增大，使得存储系统仍将成为未来提高处理器性 能的主要瓶颈。 1 1 1 2 结点间的并行 对于大规模的科学计算及事务处理应用，单个处理器无法满足其计算和存储要求， 因而，出现了将多个处理器进行互连而构成的多处理器并行机。并行机中的多个处理器 共同配合完成同一个大型任务。根据存储器的组织方式和提供给用户的地址空间的不 同，多处理器并行机可以分为以下几类： 1 ) 对称多处理机( s m p ) 对称多处理机把多个处理器与一个集中的存储器相连，各处理器完全平等，无主从 之分。所有的处理器都可以访问任何存储单元和i o 设备，并且，处理器访问存储器中 任何地址所需的时间都是一致的，因此s m p 有时也被称为均匀存储访问( u m a ) 系统。 s m p 的主要优点是数据一致性由硬件专门管理，比较容易实现，而且与单处理器具有 很好的兼容性，为单处理器系统编写的应用程序可以毫无改变地在s m p 中运行。s m p 的缺点是硬件一致性成本较高，而且可扩展性有限。 2 ) 分布存储多处理机 分布存储多处理机采用分布的存储器，存储器一般为处理器私有，处理器之间通过 网络连接起来，用消息传递的方式通信。不同的分布存储结构的不同之处在于其通讯方 式和分布存储逻辑结构的不同。分布存储多处理机的最大特点是可扩展性好。其最大的 问题是处理器之间的通信变得复杂，通讯延迟增大，并且，体系结构特征暴露给程序员， 程序员必须合理地分布数据和计算，尽量减少处理器之间的通信，才能获得较高的性能。 换句话说，并行程序高性能的获得依赖于程序员对应用领域、并行体系结构的熟悉程度， 因而，很多用户觉得编写高性能消息传递并行程序是一件很困难的事情。 3 ) 分布共享存储( d s m ) 多处理机 分布共享存储多处理机的主要特点是它的存储器物理上分布，但是通过硬件和软件 为用户提供一个单一的地址空间，即形成一个虚拟的共享存储器，从而支持共享编程模 型。在分布共享存储多处理机中，虽然每个处理器都可以访问到所有内存，但因为内存 物理上分布在各个处理结点上，访问远地内存需要的延迟大于访问本地内存所需的延 迟，因而，这类系统又称为非均匀存储访问( n u m a ) 系统。 c a c h e 一致的非均匀存储访问( c c - n u m a ) 是n u m a 的一种。c a c h e 一致是指不 需要软件来保持多个数据拷贝的一致性，如同在s m p 中一样，单一操作系统和多个处 第2 页 国防科学技术大学研究生院学位论文 理器完全在硬件级实现管理。当将n u m a 中的分布内存换成高速缓存时就得到了 c o m a ，在c o m a 中，每个处理结点上只配置了大容量的高速缓冲，所有的高速缓存 构成了全局地址空间，访问远地高速缓存要借助于分布的高速缓存目录。 根据硬件对共享存储支持的不同，d s m 又可分为硬件支持共享的d s m 和软件支持 共享的d s m ，后者通常被简称为s d s m ( s o f t w a r ed i s t r i b u t e ds h a r e dm e m o r y ) 。c r a y t 3 e 【l6 j 和o r i g i n 2 0 0 0 3 0 0 0 1 4 , 1 5 j 是硬件d s m 的典型代表。硬件d s m 提供硬件全局地址 空间及硬件同步原语或硬件c a c h e 一致性，需要定制的硬件功能。s d s m 则通过软件将 分布存储抽象成一个共享存储系统，不需要额外的硬件支持。典型的s d s m 有 t r e a d m a r k l l 8 1 、o m n i s c a s h 1 9 1 、p a r a d e 2 0 1 、j i a j i a 2 1 1 等。s d s m 的c a c h e 一致性、同 步等都完全由软件来实现，使得s d s m 的系统开销大于硬件d s m 的系统开销。 d s m 系统通过分布存储来提高存储带宽，支持更大规模的并行计算，具有良好的 可扩展性，同时，它又通过提供单一的地址空间来支持简便的并行编程模型，因而，是 近年来被广泛采用的一种并行体系结构。由于d s m 系统中远地内存访问延迟远远大于 本地内存访问延迟，太多的远地内存访问将使得处理器因等待远地数据而经常停顿，影 响了并行性能的发挥，所以，“存储墙”问题仍然是影响d s m 系统并行性能发挥的主 要问题之一。影响d s m 系统并行性能发挥的另一个问题是伪共享问题，伪共享问题将 在1 1 1 4 节中介绍。 1 1 1 3 层次存储结构 为了解决“存储墙”问题，当前的计算机大都采用层次存储结构。支持结点内并行 的层次存储结构有c a c h e 层次存储f 蹦o l 和流式层次存储【1 3 】( 本文中统称为结点内层次存 储) ，其中，c a c h e 层次存储强调降低存储延迟，流式层次存储则强调提高存储带宽。 支持结点问并行的层次存储( 简称为结点间层次存储) 在结点内层次存储的基础上增加 远地内存层次，典型的结点间层次存储结构如图1 1 所示，本文将由本地内存和远地内 存构成的层次称为分布存储。 在图1 1 中，存储层次从上往下变得离c p u 越来越远、容量越来越大、速度越来 越慢、代价越来越低。层次存储结构发挥作用的基本原理是程序的局部性原理：程序中 循环、数组的使用以及指令的顺序执行特性使得c p u 访问存储器时，无论是取指令还 是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中，这就是程序的局 部性原理。局部性可分为时间局部性和空间局部性两类，最近被访问的数据在不久的将 来会被再次访问的性质称为存储访问的时间局部性，而最近被访问数据的相邻数据在不 久的将来会被访问的性质称为存储访问的空间局部性【2 忿2 3 1 。这些局部性都是程序的固 有局部性，然而，程序的固有局部性只有能在层次存储中实现并用于提高程序性能时才 变得有意义。本文将程序固有局部性在c a c h e 中的实现情况称为c a c h e 局部性，将编译 器实施的旨在提高c a c h e 利用率的优化称为c a c h e 局部性优化，将程序固有局部性在 本地内存中的实现情况称为本地局部性，将编译器实施的旨在提高本地内存利用率的优 第3 页 垦堕型兰丝查奎主要塞尘堕兰垡笙苎 化称为本地局部性优化。 图1 1 典型的结点间层次存储结构 典型的流式层次存储结构是i m a g i n e 的三级带宽层次存储，如图1 2 所示。流式层 次存储提供了三级带宽层次：片外存储器( d r a m ) 带宽( 2 6 7 g b s ) ，流寄存器文件 ( s i 强) 带宽( 3 2 g b s ) ，局部寄存器文件( u 江) 在运算单元间的传输带宽( 5 4 4 g b s ) 。 其中，s r f 通过流缓冲器( s b ) 和运算簇组( c l u s t e r ) 中的l r f 交换数据，l r f 直接 为c l u s t e r 中的功能部件提供数据。i m a g i n e 共有2 2 个流缓冲器，允许2 2 个流客户同时 访问s r f ，其中，有8 个流缓冲器与c l u s t e r 连通，即允许同时有8 个流为c l u s t e r 算术 逻辑单元提供数据。 图1 2 典型的流式层次存储结构 上述几种层次存储结构需要编译优化的配合才能真正发掘出性能潜力。编译优化的 范围很广，面向层次存储的编译优化主要是访存数据流的优化，即通过改变程序对内存 数据单元的访问顺序或改变数据在内存中的布局，使得那些离计算单元( c p u ) 较近、 第4 页 小快高越越越量度价容速代 -niiiiiu 大慢低越越越量度价容速代 niiiiiinv- 国防科学技术大学研究生院学位论文 速度较快或带宽较高的存储层次得到充分利用，从而减少存储访问时间、充分发掘各类 并行性能。通过改变程序的访存顺序来优化访存数据流的方法通常被称为程序变换优 化，通过改变数据在内存中的布局来优化访存数据流的方法通常被称为数据布局优化。 对于强调减少存储延迟的c a c h e 层次存储结构，程序变换优化的目标是将访问同一内存 单元或相邻内存单元的指令集中起来执行，使得进入高速存储层次中的内存块能尽可能 多地被重复使用，从而减少访存时间；数据布局优化的目标是将程序同时访问的内存单 元放到相邻的物理存储区( 比如同一c a c h e 块或同一内存页) ，增加访存数据的空间局 部性。对于强调提高存储带宽的流式层次存储结构，程序变换优化的目标除了减少访存 时间外，还需尽量增加并行性；数据布局优化的目标则是充分利用高带宽来支持大量的 并行。对分布存储，程序变换优化和数据变换优化的主要目标是对准计算划分和数据划 分，提高数据访问的本地局部性、减少处理机之间的通信。程序变换优化由于起步早而 相对成熟，数据布局优化则是近年来研究较多的一种优化方法。 本文面向层次存储，从结点内和结点间两个层次研究访存数据流的优化，重点研 究通过数据的合理布局来优化访存数据流。对于新兴的流式层次存储，除了研究数据 布局优化外，还研究了通过计算核心( k e r n e l ) 合并来优化访存数据流的方法。 1 1 1 4 伪共享 当前，在支持c c - n u m a 的多处理器并行机中，c a c h e 块是缺省的一致性维护单元， 当一个处理器进行写操作时，被写数据所在的整个c a c h e 块将在其它所有处理器的 c a c h e 中被作废掉。c a c h e 块大小一般为1 6 至1 2 8 个字节长，当两个或两个以上的处理 器访问( 至少有一个写访问) 同一个c a c h e 块中的不同数据元素时，即使处理器之间的 访问操作没有数据相关，但仍旧需要某种形式的同步以保证访问操作的正确执行。 在s d s m 系统中，共享数据的分布往往以内存页( 一般为4 0 9 6 8 1 9 2 个字节