存储墙问题的思考杨学军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)k>0D(i,j)k=“=”,如果d(i,j)k=0“>”,如果d(i,j)k<0{–数据依赖图也是常用的依赖分析和优化的表示形式HPCC‘09依赖性的分析•依赖测试–根据数组下标判断循环中对数组的两次引用之间是否存在依赖–单下标测试•ZIV测试、SIV测试和MIV测试–耦合下标测试•基于依赖的程序变换–循环变换–循环倾斜–并行化–…HPCC‘09依赖性的优化举例•在依赖性指导的循环变换理论下，利用计算重组，可以大幅降低Cache的失效率——ChenDingandMaksimOrlovich《ThePotentialofComputationRegroupingforImprovingLocality》HPCC‘09重用性描述了对同一个数据单元或相邻数据单元集合的多次访问之间的关系，是数据访问在存储层次中表现出局部性的前提aaa访存序列abab访存序列时间重用性空间重用性如果两次数据访问的是同一个数据单元或相邻的数据单元集合，那么这两次...
