存储墙问题的思考PPT课件

.,1,存储墙问题的思考,杨学军,.,2,主要内容,存储墙提升计算速度的第一难题结构与优化缓解“存储墙”的对策使能技术解决“存储墙”可能的出路,.,3,存储墙仍然是提升计算速度的第一难题,InsufficientmemorybandwidthIgnoreperformancefeaturesIgnoreLittlesLawHidefaultsinlowlevelOversynchronizationgloballyOversynchronizecommunicationChoosebadalgorithmsDontrethinkalgorithmsChoose“hard”applicationsUseoverly-generalprocessors,KathyYelick(UCBerkeley)ISCA09Keynote:TenWaystoWasteaParallelComputer,.,4,存储墙问题,处理器单个引脚的信号传输速度受限处理器的引脚数受限,IBMZurichResearchLaboratory2009,.,5,在结点内部：存储器读写速度远远低于CPU处理速度，90nsVS0.3ns在结点之间：处理器之间的通信速度远远低于本地存储访问速度，2000nsVS90ns,.,6,.,7,主要内容,存储墙提升计算速度的第一难题结构与优化缓解“存储墙”的对策使能技术解决“存储墙”可能的出路,.,8,.,9,集中式Cache纯硬件管理，难以实现大容量AMDOpteron,当前主要的片上末级层次存储器,分布式Cache(Non-UniformCacheArchitecture)需要软硬件配合管理，管理复杂Texas大学Austin分校TRIPS,便笺存储器(Scratch-PadMemory)纯软件管理，管理复杂，开销大IBMCyclops64,流寄存器文件纯软件管理，随机访问困难NUDTFT64,.,10,冯诺依曼计算机的固有瓶颈,数据在存储器中编址存储，使得数据访问不得不在tube中传送数据地址等“无用”信息。JohnBackus1977ACMTuringAwardLecture,冯诺依曼计算机简单模型,.,11,我们归纳了数据访问的六种特性,.,12,.,13,.,14,依赖性的分析,依赖性的表示Wolfe等提出了利用距离向量和方向向量来刻划循环嵌套迭代空间中依赖的方法从循环嵌套迭代i中语句S1到迭代j中语句S2有依赖距离向量：d(i,j)k=jk-ik方向向量：“0D(i,j)k=“=”,如果d(i,j)k=0“”,如果d(i,j)k0,数据依赖图也是常用的依赖分析和优化的表示形式,.,15,依赖性的分析,依赖测试根据数组下标判断循环中对数组的两次引用之间是否存在依赖单下标测试ZIV测试、SIV测试和MIV测试耦合下标测试基于依赖的程序变换循环变换循环倾斜并行化,.,16,依赖性的优化举例,在依赖性指导的循环变换理论下，利用计算重组，可以大幅降低Cache的失效率,ChenDingandMaksimOrlovichThePotentialofComputationRegroupingforImprovingLocality,.,17,时间重用性,空间重用性,.,18,重用性的分析,Wolf等提出了基于矩阵的数据重用模型,针对循环中的一致生成访问给出了重用性的分类和求解方法,区分了重用性和局部性的不同重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现,for(i1=0;i1N1;i1+)for(i2=0;i2N2;i2+)A2i1i1+1,自时间重用的条件,访问矩阵,自时间重用向量空间,.,19,重用性的分析,我们将重用性模型扩展至了并行程序,证明了OpenMP程序在Static，chunk1调度模式下块边界定理,证明了OpenMP程序在Static，chunk=1调度模式下线程内重用与线程间重用的互斥性,通过定义循环并行化矩阵，我们导出了各种类别并行数据重用的求解方法,针对并行程序的特点，我们增加了重用的一维分类,.,20,重用性的优化举例,根据重用性指导循环Tiling，优化Cache单机性能提高约20%性能随处理器的增加接近线性,MichaelE.WolfandMonicaS.LamADataLocalityOptimizingAlgorithm,.,21,MPI程序MPI_Init();a=1;,进程0a=1;,进程1a=1;,相似性,.,22,相似性的分析,我们研究了与“相似”互补的另一个概念“差异”建立了程序中的差异传播模型根据差异在程序中的传播类型对其进行了分类,.,23,相似性的分析,通过前向数据流分析的方法研究了数据流生差异的求解方法,通过后向数据流分析的方法研究了控制流生差异的求解方法,基于加权依赖图研究了数组元素间的差异传播规律,.,24,相似性的优化举例,共享具有相似性的数据，缓解共享Cache和共享主存中的数据保存量优化共享Cache时，加速比达到1.2775优化共享主存时，加速比达到4.2126,.,25,CPU0,CPU1,a,b,a,a,b,b,b,a,a对CPU0的亲和性更强b对CPU1的亲和性更强,.,26,亲和性的分析,我们定量分析了数据访问的亲和性从单个处理器访问数据的角度定义了纵直亲和度从多个处理器竞争访问数据的角度了水平亲和度,.,27,亲和性的分析,纵直亲和度的计算证明了数组访问纵直亲和度与访问元素个数之间的关系,通过极大迭代点法子空间集合导出了纵直亲和度的计算,水平亲和度的计算证明了水平亲和度等于两两处理器的数据访问次数的乘积之和，揭示了水平亲和度的本质,证明了水平亲和度和纵直亲和度的定量关系,.,28,亲和性的优化举例,我们面向亲和性问题优化分布Cache中的数据分布系统性能平均增长6.24%,.,29,.,30,一致性的分析,Cache一致性决定了读操作返回什么值，使多个处理器看到的数据是一致的最早的Cache一致性协议是目录协议，IBM3081Goodman等最早描述了基于侦听协议的CacheAgarwal等提出了分布目录的思想，用于构建可扩展的Cache一致性协议,.,31,一致性的分析,Dubois等提出了弱一致性模型的思想Gharachorloo等提出了第一个释放一致性模型为了提高性能，两种模型都放松了对RW和RR顺序的要求,存储一致性决定写操作的数什么时候能够被读返回，使得多个处理器什么时候看到的数据是一致的Lamport第一次介绍了顺序一致性模型严格保持RW,RR,WR,WW四种顺序,.,32,一致性的分析,首届全国百篇优秀博士论文获得者胡伟武关于存储一致性的研究利用集合论中序关系的一些基本概念和结果，研究了有关顺序一致共享存储系统中的乱序执行技术的基本理论给出了共享存储系统中判断一个执行正确与否的充要条件给出了在共享存储系统中保证一个执行正确的访存次序条件在执行正确性模型的基础上，提出了一种乱序执行的方案,.,33,一致性的优化举例,胡伟武的研究中，在顺序一致共享存储系统中使用乱序执行技术，系统效能提高50%左右,胡伟武、夏培肃顺序一致共享存储系统中的乱序执行技术模拟实现,.,34,a=b=a=b,a=ab=b,a与b的活跃周期相交,a与b的活跃周期不相交,.,35,生存性的描述,相干图（InterferenceGraph)每个结点表示一个数据的生存期结点的权值表示对应数据对象的大小如果两个生存期可能同时存活(相干)，用一条边相连运用标量寄存器分配：对应到对相干图的图着色问题聚合数据对象(数组，流)存储分配：对应到对相干图的区间着色问题,.,36,生存性的分析,我们研究了面向嵌入式应用的便笺存储器分配问题大部分嵌入式应用的相干图满足包含相干性我们首次证明了满足包含相干性的相干图为置换图(PermutationGraph)首次提出了一个线性时间复杂性的，基于置换图着色的便笺存储器分配算法该算法在大部分嵌入式应用相干图上能取得最优，相对国际最新的基于超完美图(SuperperfectGraph)的算法，复杂性更低，性能更好,.,37,生存性的分析,我们研究了面向流应用的流寄存器文件分配问题首次提出了一个基于存储器着色的流寄存器文件分配框架巧妙地将开发复用和并行整合到对相干图的操作中首次证明了绝大部分流应用的相干图为可比图(comparabilitygraph)，或可以降解为多个可比子图首次将流寄存器文件分配问题建模为最佳有向路径寻找问题，提出了一个最优或近似最优的流寄存器文件分配算法该算法相对国际上普遍采用的基于Bin-Packing的First-Fit算法，具有更好的性能,.,38,生存性的优化举例,我们算法的效果能在除QMR外的所有已有实际流应用相干图上取得最优流寄存器文件分配(用C表示)在QMR上，能取得近似最优分配(用F表示),.,39,生存性的优化举例,在随机产生的1200个满足流应用特性的相干图中，我们的算法在98%以上的图中能取得最优，而First-Fit只在约25%的图中能取得最优,.,40,综合考虑六种数据访问特性,.,41,主要内容,存储墙提升计算速度的第一难题结构与优化缓解“存储墙”的对策使能技术解决“存储墙”可能的出路,.,42,一则新闻,2009年9月1日英国工程和物理科学研究委员会EPSRC出资6million研制光计算机研究单位：帝国理工学院&英国皇后大学关键部分：纳米等离子器件应用：未来超快计算机时间：为期6年,.,43,铜互连,光互连,.,44,光互连的优势,物理属性频率高多维多重复用弱衰减自由空间传播,应用潜力传输带宽高并行通信远距离通信动态互连/可重构,.,45,光互连在计算机系统中的应用,机柜间光互连的应用已经非常广泛板间光互连的应用正在逐渐兴起芯片间光互连技术具备解决存储墙问题的巨大潜力，仍处于探索阶段,.,46,芯片间光互连技术的难点,现有光互连器件主要基于III-V、II-VI族化合物机柜间、板间光互连用到的光收发器与调制器等这些技术应用于芯片间光互连的问题材料昂贵，不兼容CMOS工艺器件尺寸较大器件功耗较大,.,47,硅光器件技术取得一系列突破,2004年Intel1GHz硅光子调制器Nature此前的记录为20MHz提高了50倍2005年Intel硅基拉曼激光源Nature单模模式下，80MHz激光线宽光学性质优良,.,48,硅光器件技术取得一系列突破,2006年美国Cornell大学宽带光放大器Nature极大地拓宽了光信号放大和变换的波长范围显著提高了硅基光集成电路的信号处理能力2008年Intel硅光子探测器Nature340GHz增益带宽积性能与传统的商业化光探测器相当,.,49,硅光器件技术取得一系列突破,2008年IBM最小的光开关NaturePhotonics器件尺寸：45umx22um吞吐率：1Tbps开关延迟：2ns误码率：10-12交调失真：-25dB,.,50,国际上芯片间光互连的研究项目,自1998年以来，美国DAPRA先后投入了2亿6千多万美元用于光互连相关的项目研究，其中4500万美元用于2003至2007年的芯片间光互连研究,.,51,国际上芯片间光互连的研究项目,美国：UNIC项目2007-2012，美国DAPAR&SUN4700万美元高带宽、低延迟、低功耗、CMOS兼容，片内及片间光互连技术美国其它多所企业和高校研究机构参与,.,52,国际上芯片间光互连的研究项目,欧盟：OPERA2015合作计划2005年启动，欧盟多个国家参与旨在通过加强光学与光子学领域的合作，提高欧洲在信息技术领域的综合影响力数十个芯片间光互连相关项目在研或已完成欧盟：HELIOS项目2008-2012，耗资1200万欧元解决光器件的CMOS工艺制备与集成问题40Gb/s调制器、10 x10Gb/s收发器等光器件,.,53,日本：Keisoku10PFLOPS超级计算机计划NEC等预测到2010年CPU的处理能力将达到100GFlops。CPU与存储器之间需要至少25000根数据传输线才能满足CPU的处理速度目标是实现CPU和存储器之间1000个光通道，每个通道20Gbps，总带宽达20Tbps的光互连,国际上芯片间光互连的研究项目,.,54,国内芯片间光互连的研究进展,中科院微电子所、中科院深圳技术研究院国家863芯片间光互连技术与试验平台单通道10Gb/s，12路并行，误码率10-102007年新型光电探测器EVPD其它单位天津大学、北京邮电大学、上海交通大学、东南大学、华中科技大学、国防科技大学等单位都进行了光互连相关技术研究,.,55,IBM对光互连发展趋势的观点,.,56,IBM关于2020年光互连技术的观点,在3-D堆叠技术的背景下通过芯片间和芯片内光互连进一步缩小计算部件和存储器件之间的速度差距，提高信号传输的带宽,.,57,纳米电子学的发展也可能推动存储墙问题的解决,纳米电子学2008年斯坦福大学制备出基于碳纳米管互联线的原型芯片，工作频率达到1GHz以上2008年IBM制备出基于石墨烯的