存储墙问题思考

主要内容存储墙——提升计算速度的第一难题结构与优化——缓解“存储墙”的对策使能技术——解决“存储墙”可能的出路第一页，共60页。存储墙仍然是

提升计算速度的第一难题InsufficientmemorybandwidthIgnoreperformancefeaturesIgnoreLittle'sLawHidefaultsinlowlevelOversynchronizationgloballyOversynchronizecommunicationChoosebadalgorithmsDon’trethinkalgorithmsChoose“hard”applicationsUseoverly-generalprocessors——KathyYelick

(UCBerkeley)ISCA’09Keynote:《TenWaystoWasteaParallelComputer》第二页，共60页。存储墙问题处理器单个引脚的信号传输速度受限处理器的引脚数受限——IBMZurichResearchLaboratory2009第三页，共60页。在结点内部：存储器读写速度远远低于CPU处理速度，90nsVS0.3ns在结点之间：处理器之间的通信速度远远低于本地存储访问速度，2000nsVS90ns并行计算效率下降，目前大规模并行计算机在实际应用中的并行效率在5%左右第四页，共60页。存储墙问题之

可能的解决途径体系结构技术的发展使能技术的发展第五页，共60页。主要内容存储墙——提升计算速度的第一难题结构与优化——缓解“存储墙”的对策使能技术——解决“存储墙”可能的出路第六页，共60页。Multicoreputsusonthewrongsideofthememorywall.WillCMPultimatelybeasphyxiatedbythememorywall?

（多核将我们放在了存储墙问题的错误一面。多核处理器最终是否会因为存储墙问题窒息而死？）

——ThomasSterling第七页，共60页。集中式Cache纯硬件管理，难以实现大容量AMDOpteron当前主要的片上末级层次存储器分布式Cache(Non-UniformCacheArchitecture)需要软硬件配合管理，管理复杂Texas大学Austin分校TRIPS便笺存储器(Scratch-PadMemory)纯软件管理，管理复杂，开销大IBMCyclops64流寄存器文件纯软件管理，随机访问困难NUDTFT64第八页，共60页。冯诺依曼计算机的固有瓶颈CPUStoretubeVonNeumannbottleneck数据在存储器中编址存储，使得数据访问不得不在tube中传送数据地址等“无用”信息。——JohnBackus1977ACMTuringAwardLecture数据访问特性的分析理论与方法

是解决存储墙问题的基础冯诺依曼计算机简单模型第九页，共60页。我们归纳了数据访问的六种特性依赖性重用性相似性亲和性一致性生存性第十页，共60页。这六种数据访问特性并不独立，而是相互关联、相辅相成的，它们从不同侧面反映了数据访问的特征影响性能影响正确性资源相容资源相斥依赖性一致性重用性相似性生存性亲和性时间空间地址值时间空间值地址时间空间地址值第十一页，共60页。依赖性

描述了包含写访问的数据单元访问之间的相对顺序关系，约束了程序执行的正确性a=

=a流依赖=aa=反依赖a=

a=输出依赖如果程序某条执行路径上的两个语句访问了相同的数据单元，并且至少有一个语句是对这个单元的写操作，那么这两个语句之间存在数据依赖。数据依赖的约束保证了数据按正确的顺序生产和消费，保证程序变换不改变用计算结果表示的程序含义读读依赖=a

=a第十二页，共60页。依赖性的分析依赖性的表示Wolfe等提出了利用距离向量和方向向量来刻划循环嵌套迭代空间中依赖的方法从循环嵌套迭代i中语句S1到迭代j中语句S2有依赖距离向量：d(i,j)k=jk-ik方向向量：“<”,如果d(i,j)k>0 D(i,j)k=“=”,如果d(i,j)k=0 “>”,如果d(i,j)k<0{数据依赖图也是常用的依赖分析和优化的表示形式第十三页，共60页。依赖性的分析依赖测试根据数组下标判断循环中对数组的两次引用之间是否存在依赖单下标测试ZIV测试、SIV测试和MIV测试耦合下标测试基于依赖的程序变换循环变换循环倾斜并行化…第十四页，共60页。依赖性的优化举例在依赖性指导的循环变换理论下，利用计算重组，可以大幅降低Cache的失效率——ChenDingandMaksimOrlovich《ThePotentialofComputationRegroupingfor

ImprovingLocality》第十五页，共60页。重用性描述了对同一个数据单元或相邻数据单元集合的多次访问之间的关系，是数据访问在存储层次中表现出局部性的前提aaa访存序列abab访存序列时间重用性空间重用性如果两次数据访问的是同一个数据单元或相邻的数据单元集合，那么这两次数据访问具有重用性。重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现第十六页，共60页。重用性的分析Wolf等提出了基于矩阵的数据重用模型针对循环中的一致生成访问给出了重用性的分类和求解方法区分了重用性和局部性的不同重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现for(i1=0;i1<N1;i1++)for(i2=0;i2<N2;i2++){…A[2i1][i1+1]…}自时间重用的条件访问矩阵自时间重用向量空间第十七页，共60页。重用性的分析我们将重用性模型扩展至了并行程序证明了OpenMP程序在Static，chunk1调度模式下块边界定理证明了OpenMP程序在Static，chunk=1调度模式下线程内重用与线程间重用的互斥性通过定义循环并行化矩阵，我们导出了各种类别并行数据重用的求解方法针对并行程序的特点，我们增加了重用的一维分类自/组时间/空间自/组时间/空间执行体内/执行体间#pragmaompparallelforfor(i1=0;i1<N1;i1++)for(i2=0;i2<N2;i2++){…A[2i1][i1+1]…}迭代内重用的条件循环并行化矩阵迭代内向量空间第十八页，共60页。重用性的优化举例根据重用性指导循环Tiling，优化Cache单机性能提高约20%性能随处理器的增加接近线性——MichaelE.WolfandMonicaS.Lam《ADataLocalityOptimizingAlgorithm》第十九页，共60页。相似性描述了程序的多个执行体中对应的多个数据单元内容之间的关系，用于优化多个执行体对存储器的占用量MPI程序MPI_Init(…);…a=1;…进程0…a=1;…进程1…a=1;…相似性当同一个程序派生多个执行体时，如果这些执行体内和程序中某个变量对应的多个数据单元在同一段代码的执行过程中拥有相同的值，那么对这些数据单元的访问具有相似性。相似的数据单元只是在访问时具有相同的值，而属于不同的存储地址第二十页，共60页。相似性的分析我们研究了与“相似”互补的另一个概念

——“差异”建立了程序中的差异传播模型根据差异在程序中的传播类型对其进行了分类差异的分类原生差异继生差异数据流生差异控制流生差异第二十一页，共60页。相似性的分析通过前向数据流分析的方法研究了数据流生差异的求解方法通过后向数据流分析的方法研究了控制流生差异的求解方法基于加权依赖图研究了数组元素间的差异传播规律第二十二页，共60页。相似性的优化举例共享具有相似性的数据，缓解共享Cache和共享主存中的数据保存量优化共享Cache时，加速比达到1.2775优化共享主存时，加速比达到4.2126第二十三页，共60页。亲和性描述了数据单元在多个处理器中访问频度之间的关系，决定了数据分布对处理器访问性能的影响CPU0CPU1abaabbbaa对CPU0的亲和性更强b对CPU1的亲和性更强给定多个处理器，一个数据单元被某个处理器访问得越频繁，该数据对这个处理器的亲和性就越强。在分布存储结构中，这个数据单元越靠近这个处理器，系统对这个数据单元的访问开销就越小。同时，当某个数据单元对多个处理器都表现出较强的亲和性时，就容易发生数据在处理器间的抖动问题第二十四页，共60页。亲和性的分析我们定量分析了数据访问的亲和性从单个处理器访问数据的角度定义了纵直亲和度从多个处理器竞争访问数据的角度了水平亲和度第二十五页，共60页。亲和性的分析纵直亲和度的计算证明了数组访问纵直亲和度与访问元素个数之间的关系通过极大迭代点法子空间集合导出了纵直亲和度的计算水平亲和度的计算证明了水平亲和度等于两两处理器的数据访问次数的乘积之和，揭示了水平亲和度的本质证明了水平亲和度和纵直亲和度的定量关系第二十六页，共60页。亲和性的优化举例我们面向亲和性问题优化分布Cache中的数据分布系统性能平均增长6.24%第二十七页，共60页。一致性描述了数据的单个或多个副本访问的数据内容之间的关系，影响着程序执行的正确性CPU0CPU1CacheCache主存a一致性aa如果系统中对数据单个或多个副本的多次访问的值与程序的行为不一致，那么它们就违反了数据访问的一致性。Cache一致性和存储一致性是系统设计的重要方面，对软件的编程正确性和硬件的运行效率都有着重要的影响第二十八页，共60页。一致性的分析Cache一致性——决定了读操作返回什么值，使多个处理器看到的数据是一致的最早的Cache一致性协议是目录协议，IBM3081Goodman等最早描述了基于侦听协议的CacheAgarwal等提出了分布目录的思想，用于构建可扩展的Cache一致性协议第二十九页，共60页。一致性的分析Dubois等提出了弱一致性模型的思想Gharachorloo等提出了第一个释放一致性模型为了提高性能，两种模型都放松了对R→W和R→R顺序的要求存储一致性——决定写操作的数什么时候能够被读返回，使得多个处理器什么时候看到的数据是一致的Lamport第一次介绍了顺序一致性模型严格保持R→W,R→R,W→R,W→W四种顺序第三十页，共60页。一致性的分析首届全国百篇优秀博士论文获得者胡伟武关于存储一致性的研究——利用集合论中序关系的一些基本概念和结果，研究了有关顺序一致共享存储系统中的乱序执行技术的基本理论给出了共享存储系统中判断一个执行正确与否的充要条件给出了在共享存储系统中保证一个执行正确的访存次序条件在执行正确性模型的基础上，提出了一种乱序执行的方案第三十一页，共60页。一致性的优化举例胡伟武的研究中，在顺序一致共享存储系统中使用乱序执行技术，系统效能提高50%左右——胡伟武、夏培肃《顺序一致共享存储系统中的乱序执行技术——模拟实现》第三十二页，共60页。生存性描述了多个数据访问的活跃程度之间的关系，是资源分配类问题求解的重要约束a=b=

=a=ba==a

b==ba与b的活跃周期相交a与b的活跃周期不相交如果多个数据的生命周期重叠，那么它们在程序运行过程中同时活跃，表现出对某些资源占用的互斥性。因此，生存性是很多资源分配类问题的重要约束，如寄存器分配等第三十三页，共60页。生存性的描述相干图（InterferenceGraph)每个结点表示一个数据的生存期结点的权值表示对应数据对象的大小如果两个生存期可能同时存活(相干)，用一条边相连运用标量寄存器分配：对应到对相干图的图着色问题聚合数据对象(数组，流)存储分配：对应到对相干图的区间着色问题第三十四页，共60页。生存性的分析我们研究了面向嵌入式应用的便笺存储器分配问题大部分嵌入式应用的相干图满足包含相干性我们首次证明了满足包含相干性的相干图为置换图(PermutationGraph)首次提出了一个线性时间复杂性的，基于置换图着色的便笺存储器分配算法该算法在大部分嵌入式应用相干图上能取得最优，相对国际最新的基于超完美图(SuperperfectGraph)的算法，复杂性更低，性能更好第三十五页，共60页。生存性的分析我们研究了面向流应用的流寄存器文件分配问题首次提出了一个基于存储器着色的流寄存器文件分配框架巧妙地将开发复用和并行整合到对相干图的操作中首次证明了绝大部分流应用的相干图为可比图(comparabilitygraph)，或可以降解为多个可比子图首次将流寄存器文件分配问题建模为最佳有向路径寻找问题，提出了一个最优或近似最优的流寄存器文件分配算法该算法相对国际上普遍采用的基于Bin-Packing的First-Fit算法，具有更好的性能第三十六页，共60页。生存性的优化举例我们算法的效果能在除QMR外的所有已有实际流应用相干图上取得最优流寄存器文件分配(用C表示)在QMR上，能取得近似最优分配(用F表示)第三十七页，共60页。生存性的优化举例在随机产生的1200个满足流应用特性的相干图中，我们的算法在98%以上的图中能取得最优，而First-Fit只在约25%的图中能取得最优第三十八页，共60页。综合考虑六种数据访问特性传统优化技术往往只考虑单一数据访问性质被优化的性质其它性质综合度量六种数据访问特性和谐的

优化算法新的软硬件配合的体系结构第三十九页，共60页。主要内容存储墙——提升计算速度的第一难题结构与优化——缓解“存储墙”的对策使能技术——解决“存储墙”可能的出路第四十页，共60页。一则新闻2009年9月1日英国工程和物理科学研究委员会EPSRC出资£6million研制光计算机

研究单位：帝国理工学院&英国皇后大学关键部分：纳米等离子器件应用：未来超快计算机时间：为期6年该项目围绕纳米光源、纳米光调制器、纳米光放大器等展开研究，第一阶段旨在芯片间光互连领域取得重要突破第四十一页，共60页。芯片间光互连是解决存储墙问题最具潜力的技术之一铜互连光互连第四十二页，共60页。光互连的优势物理属性频率高多维多重复用弱衰减自由空间传播应用潜力传输带宽高并行通信远距离通信动态互连/可重构功耗带宽带宽密度电磁兼容重量/体积价格光互连低高高无轻低电互连高低低严重重高光互连的物理依据光互连V.S.电互连第四十三页，共60页。光互连在计算机系统中的应用机柜间光互连的应用已经非常广泛板间光互连的应用正在逐渐兴起芯片间光互连技术具备解决存储墙问题的巨大潜力，仍处于探索阶段机柜间板间芯片间第四十四页，共60页。芯片间光互连技术的难点现有光互连器件主要基于III-V、II-VI族化合物机柜间、板间光互连用到的光收发器与调制器等这些技术应用于芯片间光互连的问题材料昂贵，不兼容CMOS工艺器件尺寸较大器件功耗较大芯片间光互连研究的关键

——硅光器件技术第四十五页，共60页。硅光器件技术取得一系列突破2004年Intel1GHz硅光子调制器《Nature》此前的记录为20MHz提高了50倍2005年Intel硅基拉曼激光源《Nature》单模模式下，80MHz激光线宽光学性质优良第四十六页，共60页。硅光器件技术取得一系列突破2006年美国Cornell大学宽带光放大器《Nature》极大地拓宽了光信号放大 和变换的波长范围显著提高了硅基光集成电路的信号处理能力

2008年Intel硅光子探测器《Nature》340GHz增益带宽积性能与传统的商业化光 探测器相当第四十七页，共60页。硅光器件技术取得一系列突破2008年IBM最小的光开关《NaturePhotonics》器件尺寸：45umx22um吞吐率：1Tbps开关延迟：<2ns误码率：<10-12交调失真：<-25dB第四十八页，共60页。国际上芯片间光互连的研究项目自1998年以来，美国DAPRA先后投入了2亿6千多万美元用于光互连相关的项目研究，其中4500万美元用于2003至2007年的芯片间光互连研究

第四十九页，共60页。国际上芯片间光互连的研究项目美国：UNIC项目2007-2012，美国DAPAR&SUN4700万美元高带宽、低延迟、低功耗、CMOS兼容，片内及片间光互连技术美国其它多所企业和高校研究机构参与第五十页，共60页。国际上芯片间光互连的研究项目欧盟：OPERA2015合作计划2005年启动，欧盟多个国家参与旨在通过加强光学与光子学领域的合作，提高欧洲在信息技术领域的综合影响力数十个芯片间光互连相关项目在研或已完成欧盟：HELIOS项目2008-2012，耗资1200万欧元解决光器件的CMOS工艺制备与集成问题40Gb/s调制器、10x10Gb/s收发器等光器件第五十一页，共60页。日本：Keisoku10PFLOPS

超级计算机计划NEC等预测到2010年CPU的

处理能力将达到100GFlops。

CPU与存储器之间需要至少

25000根数据传输线才能满

足CPU的处理速度目标是实现CPU和存储器之

间1000个光通