存储墙问题的思考

存储墙问题的思考杨学军HPCC‘09主要内容•存储墙——提升计算速度的第一难题•结构与优化——缓解“存储墙”的对策•使能技术——解决“存储墙”可能的出路HPCC‘09存储墙仍然是提升计算速度的第一难题1.Insufficientmemorybandwidth2.Ignoreperformancefeatures3.IgnoreLittle'sLaw4.Hidefaultsinlowlevel5.Oversynchronizationglobally6.Oversynchronizecommunication7.Choosebadalgorithms8.Don’trethinkalgorithms9.Choose“hard”applications10.Useoverly-generalprocessors——KathyYelick(UCBerkeley)ISCA’09Keynote:《TenWaystoWasteaParallelComputer》HPCC‘09存储墙问题•处理器单个引脚的信号传输速度受限•处理器的引脚数受限——IBMZurichResearchLaboratory2009HPCC‘09•在结点内部：存储器读写速度远远低于CPU处理速度，90nsVS0.3ns•在结点之间：处理器之间的通信速度远远低于本地存储访问速度，2000nsVS90ns并行计算效率下降，目前大规模并行计算机在实际应用中的并行效率在5%左右HPCC‘09存储墙问题之可能的解决途径体系结构技术的发展使能技术的发展HPCC‘09主要内容•存储墙——提升计算速度的第一难题•结构与优化——缓解“存储墙”的对策•使能技术——解决“存储墙”可能的出路HPCC‘09Multicoreputsusonthewrongsideofthememorywall.WillCMPultimatelybeasphyxiatedbythememorywall?（多核将我们放在了存储墙问题的错误一面。多核处理器最终是否会因为存储墙问题窒息而死？）——ThomasSterlingHPCC‘09•集中式Cache–纯硬件管理，难以实现大容量–AMDOpteron当前主要的片上末级层次存储器•分布式Cache(Non-UniformCacheArchitecture)–需要软硬件配合管理，管理复杂–Texas大学Austin分校TRIPS•便笺存储器(Scratch-PadMemory)–纯软件管理，管理复杂，开销大–IBMCyclops64•流寄存器文件–纯软件管理，随机访问困难–NUDTFT64HPCC‘09冯诺依曼计算机的固有瓶颈CPUStoretubeVonNeumannbottleneck数据在存储器中编址存储，使得数据访问不得不在tube中传送数据地址等“无用”信息。——JohnBackus1977ACMTuringAwardLecture数据访问特性的分析理论与方法是解决存储墙问题的基础冯诺依曼计算机简单模型HPCC‘09我们归纳了数据访问的六种特性依赖性重用性相似性亲和性一致性生存性HPCC‘09这六种数据访问特性并不独立，而是相互关联、相辅相成的，它们从不同侧面反映了数据访问的特征依赖性一致性重用性相似性生存性亲和性时间空间地址值时间空间值地址时间空间地址值HPCC‘09依赖性描述了包含写访问的数据单元访问之间的相对顺序关系，约束了程序执行的正确性a==a流依赖=aa=反依赖a=a=输出依赖如果程序某条执行路径上的两个语句访问了相同的数据单元，并且至少有一个语句是对这个单元的写操作，那么这两个语句之间存在数据依赖。数据依赖的约束保证了数据按正确的顺序生产和消费，保证程序变换不改变用计算结果表示的程序含义读读依赖=a=aHPCC‘09依赖性的分析•依赖性的表示–Wolfe等提出了利用距离向量和方向向量来刻划循环嵌套迭代空间中依赖的方法•从循环嵌套迭代i中语句S1到迭代j中语句S2有依赖•距离向量：d(i,j)k=jk-ik•方向向量：“”,如果d(i,j)k0D(i,j)k=“=”,如果d(i,j)k=0“”,如果d(i,j)k0{–数据依赖图也是常用的依赖分析和优化的表示形式HPCC‘09依赖性的分析•依赖测试–根据数组下标判断循环中对数组的两次引用之间是否存在依赖–单下标测试•ZIV测试、SIV测试和MIV测试–耦合下标测试•基于依赖的程序变换–循环变换–循环倾斜–并行化–…HPCC‘09依赖性的优化举例•在依赖性指导的循环变换理论下，利用计算重组，可以大幅降低Cache的失效率——ChenDingandMaksimOrlovich《ThePotentialofComputationRegroupingforImprovingLocality》HPCC‘09重用性描述了对同一个数据单元或相邻数据单元集合的多次访问之间的关系，是数据访问在存储层次中表现出局部性的前提aaa访存序列abab访存序列时间重用性空间重用性如果两次数据访问的是同一个数据单元或相邻的数据单元集合，那么这两次数据访问具有重用性。重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现HPCC‘09重用性的分析•Wolf等提出了基于矩阵的数据重用模型–针对循环中的一致生成访问给出了重用性的分类和求解方法–区分了重用性和局部性的不同•重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现for(i1=0;i1N1;i1++)for(i2=0;i2N2;i2++){…A[2i1][i1+1]…}2010H0Hr自时间重用的条件0ker1Hspan访问矩阵自时间重用向量空间HPCC‘09重用性的分析•我们将重用性模型扩展至了并行程序–证明了OpenMP程序在Static，chunk1调度模式下块边界定理–证明了OpenMP程序在Static，chunk=1调度模式下线程内重用与线程间重用的互斥性–通过定义循环并行化矩阵，我们导出了各种类别并行数据重用的求解方法–针对并行程序的特点，我们增加了重用的一维分类自/组时间/空间自/组时间/空间执行体内/执行体间#pragmaompparallelforfor(i1=0;i1N1;i1++)for(i2=0;i2N2;i2++){…A[2i1][i1+1]…}1000LPM0LPMr迭代内重用的条件0ker1LPMspan循环并行化矩阵迭代内向量空间HPCC‘09重用性的优化举例•根据重用性指导循环Tiling，优化Cache–单机性能提高约20%–性能随处理器的增加接近线性——MichaelE.WolfandMonicaS.Lam《ADataLocalityOptimizingAlgorithm》HPCC‘09相似性描述了程序的多个执行体中对应的多个数据单元内容之间的关系，用于优化多个执行体对存储器的占用量MPI程序MPI_Init(…);…a=1;…进程0…a=1;…进程1…a=1;…相似性当同一个程序派生多个执行体时，如果这些执行体内和程序中某个变量对应的多个数据单元在同一段代码的执行过程中拥有相同的值，那么对这些数据单元的访问具有相似性。相似的数据单元只是在访问时具有相同的值，而属于不同的存储地址HPCC‘09相似性的分析•我们研究了与“相似”互补的另一个概念——“差异”–建立了程序中的差异传播模型•根据差异在程序中的传播类型对其进行了分类差异的分类原生差异继生差异数据流生差异控制流生差异HPCC‘09相似性的分析•通过前向数据流分析的方法研究了数据流生差异的求解方法•通过后向数据流分析的方法研究了控制流生差异的求解方法•基于加权依赖图研究了数组元素间的差异传播规律HPCC‘09相似性的优化举例•共享具有相似性的数据，缓解共享Cache和共享主存中的数据保存量–优化共享Cache时，加速比达到1.2775–优化共享主存时，加速比达到4.2126HPCC‘09亲和性描述了数据单元在多个处理器中访问频度之间的关系，决定了数据分布对处理器访问性能的影响CPU0CPU1abaabbbaa对CPU0的亲和性更强b对CPU1的亲和性更强给定多个处理器，一个数据单元被某个处理器访问得越频繁，该数据对这个处理器的亲和性就越强。在分布存储结构中，这个数据单元越靠近这个处理器，系统对这个数据单元的访问开销就越小。同时，当某个数据单元对多个处理器都表现出较强的亲和性时，就容易发生数据在处理器间的抖动问题HPCC‘09亲和性的分析•我们定量分析了数据访问的亲和性–从单个处理器访问数据的角度定义了纵直亲和度–从多个处理器竞争访问数据的角度了水平亲和度HPCC‘09亲和性的分析•纵直亲和度的计算–证明了数组访问纵直亲和度与访问元素个数之间的关系–通过极大迭代点法子空间集合导出了纵直亲和度的计算•水平亲和度的计算–证明了水平亲和度等于两两处理器的数据访问次数的乘积之和，揭示了水平亲和度的本质–证明了水平亲和度和纵直亲和度的定量关系HPCC‘09亲和性的优化举例•我们面向亲和性问题优化分布Cache中的数据分布–系统性能平均增长6.24%HPCC‘09一致性描述了数据的单个或多个副本访问的数据内容之间的关系，影响着程序执行的正确性CPU0CPU1CacheCache主存a一致性aa如果系统中对数据单个或多个副本的多次访问的值与程序的行为不一致，那么它们就违反了数据访问的一致性。Cache一致性和存储一致性是系统设计的重要方面，对软件的编程正确性和硬件的运行效率都有着重要的影响HPCC‘09一致性的分析•Cache一致性——决定了读操作返回什么值，使多个处理器看到的数据是一致的–最早的Cache一致性协议是目录协议，IBM3081–Goodman等最早描述了基于侦听协议的Cache–Agarwal等提出了分布目录的思想，用于构建可扩展的Cache一致性协议HPCC‘09一致性的分析–Dubois等提出了弱一致性模型的思想–Gharachorloo等提出了第一个释放一致性模型•为了提高性能，两种模型都放松了对R→W和R→R顺序的要求•存储一致性——决定写操作的数什么时候能够被读返回，使得多个处理器什么时候看到的数据是一致的–Lamport第一次介绍了顺序一致性模型•严格保持R→W,R→R,W→R,W→W四种顺序HPCC‘09一致性的分析•首届全国百篇优秀博士论文获得者胡伟武关于存储一致性的研究——利用集合论中序关系的一些基本概念和结果，研究了有关顺序一致共享存储系统中的乱序执行技术的基本理论•给出了共享存储系统中判断一个执行正确与否的充要条件•给出了在共享存储系统中保证一个执行正确的访存次序条件•在执行正确性模型的基础上，提出了一种乱序执行的方案HPCC‘09一致性的优化举例•胡伟武的研究中，在顺序一致共享存储系统中使用乱序执行技术，系统效能提高50%左右——胡伟武、夏培肃《顺序一致共享存储系统中的乱序执行技术——模拟实现》HPCC‘09生存性描述了多个数据访问的活跃程度之间的关系，是资源分配类问题求解的重要约束a=b==a=ba==ab==ba与b的活跃周期相交a与b的活跃周期不相交如果多个数据的生命周期重叠，那么它们在程序运行过程中同时活跃，表现出对某些资源占用的互斥性。因此，生存性是很多资源分配类问题的重要约束，如寄存器分配等HPCC‘09生存性的描述•相干图（InterferenceGraph)–每个结点表示一个数据的生存期–结点的权值表示对应数据对象的大小–如果两个生存期可能同时存活(相干)，用一条边相连•运用–标量寄存器分配：对应到对相干图的图着色问题–聚合数据对象(数组，流)存储分配：对应到对相干图的区间着色问题HPCC‘09生存性的分析•我们研究了面向嵌入式应用的便笺存储器分配问题–大部分嵌入式应用的相干图满足包含相干性–我们首次证明了满足包含相干性的相干图为置换图(P