存储墙问题的思考.pptx

存储墙问题的思考,杨学军,主要内容,存储墙提升计算速度的第一难题 结构与优化缓解“存储墙”的对策 使能技术解决“存储墙”可能的出路,存储墙仍然是 提升计算速度的第一难题,Insufficient memory bandwidth Ignore performance features Ignore Littles Law Hide faults in low level Over synchronization globally Over synchronize communication Choose bad algorithms Dont rethink algorithms Choose “hard” applications Use overly-general processors, Kathy Yelick (UC Berkeley) ISCA 09 Keynote: Ten Ways to Waste a Parallel Computer,存储墙问题,处理器单个引脚的信号传输速度受限 处理器的引脚数受限,IBM Zurich Research Laboratory 2009,在结点内部：存储器读写速度远远低于CPU处理速度，90ns VS 0.3ns 在结点之间：处理器之间的通信速度远远低于本地存储访问速度，2000ns VS 90ns,主要内容,存储墙提升计算速度的第一难题 结构与优化缓解“存储墙”的对策 使能技术解决“存储墙”可能的出路,集中式Cache 纯硬件管理，难以实现大容量 AMD Opteron,当前主要的片上末级层次存储器,分布式Cache (Non-Uniform Cache Architecture) 需要软硬件配合管理，管理复杂 Texas大学Austin分校 TRIPS,便笺存储器 (Scratch-Pad Memory) 纯软件管理，管理复杂，开销大 IBM Cyclops64,流寄存器文件 纯软件管理，随机访问困难 NUDT FT64,冯诺依曼计算机的固有瓶颈,数据在存储器中编址存储，使得数据访问不得不在tube中传送数据地址等“无用”信息。 John Backus 1977 ACM Turing Award Lecture,数据访问特性的分析理论与方法 是解决存储墙问题的基础,冯诺依曼计算机简单模型,我们归纳了数据访问的六种特性,依赖性的分析,依赖性的表示 Wolfe等提出了利用距离向量和方向向量来刻划循环嵌套迭代空间中依赖的方法 从循环嵌套迭代i中语句S1到迭代j中语句S2有依赖 距离向量：d(i,j)k=jk-ik 方向向量： “0 D(i,j)k= “=”,如果d(i,j)k=0 “”,如果d(i,j)k0,数据依赖图也是常用的依赖分析和优化的表示形式,依赖性的分析,依赖测试 根据数组下标判断循环中对数组的两次引用之间是否存在依赖 单下标测试 ZIV测试、SIV 测试和MIV 测试 耦合下标测试 基于依赖的程序变换 循环变换 循环倾斜 并行化 ,依赖性的优化举例,在依赖性指导的循环变换理论下，利用计算重组，可以大幅降低Cache的失效率, Chen Ding and Maksim Orlovich The Potential of Computation Regrouping for Improving Locality ,时间重用性,空间重用性,重用性的分析,Wolf等提出了基于矩阵的数据重用模型,针对循环中的一致生成访问给出了重用性的分类和求解方法,区分了重用性和局部性的不同 重用性是程序中数据访问的固有属性之一，而局部性是重用性在程序运行时在某一级存储层次中的具体体现,for (i1=0; i1N1; i1+) for (i2=0; i2N2; i2+) A2i1i1+1 ,自时间重用的条件,访问矩阵,自时间重用向量空间,重用性的分析,我们将重用性模型扩展至了并行程序,证明了OpenMP程序在Static，chunk1调度模式下块边界定理,证明了OpenMP程序在Static，chunk=1调度模式下线程内重用与线程间重用的互斥性,通过定义循环并行化矩阵，我们导出了各种类别并行数据重用的求解方法,针对并行程序的特点，我们增加了重用的一维分类,重用性的优化举例,根据重用性指导循环Tiling，优化Cache 单机性能提高约20% 性能随处理器的增加接近线性, Michael E. Wolf and Monica S. Lam A Data Locality Optimizing Algorithm,MPI程序 MPI_Init(); a = 1; ,进程0 a = 1; ,进程1 a = 1; ,相似性,相似性的分析,我们研究了与“相似”互补的另一个概念 “差异” 建立了程序中的差异传播模型 根据差异在程序中的传播类型对其进行了分类,相似性的分析,通过前向数据流分析的方法研究了数据流生差异的求解方法,通过后向数据流分析的方法研究了控制流生差异的求解方法,基于加权依赖图研究了数组元素间的差异传播规律,相似性的优化举例,共享具有相似性的数据，缓解共享Cache和共享主存中的数据保存量 优化共享Cache时，加速比达到1.2775 优化共享主存时，加速比达到4.2126,CPU 0,CPU 1,a,b,a,a,b,b,b,a,a对CPU 0的亲和性更强 b对CPU 1的亲和性更强,亲和性的分析,我们定量分析了数据访问的亲和性 从单个处理器访问数据的角度定义了纵直亲和度 从多个处理器竞争访问数据的角度了水平亲和度,亲和性的分析,纵直亲和度的计算 证明了数组访问纵直亲和度与访问元素个数之间的关系,通过极大迭代点法子空间集合导出了纵直亲和度的计算,水平亲和度的计算 证明了水平亲和度等于两两处理器的数据访问次数的乘积之和，揭示了水平亲和度的本质,证明了水平亲和度和纵直亲和度的定量关系,亲和性的优化举例,我们面向亲和性问题优化分布Cache中的数据分布 系统性能平均增长6.24%,一致性的分析,Cache一致性决定了读操作返回什么值，使多个处理器看到的数据是一致的 最早的Cache一致性协议是目录协议，IBM 3081 Goodman 等最早描述了基于侦听协议的Cache Agarwal 等提出了分布目录的思想，用于构建可扩展的Cache 一致性协议,一致性的分析,Dubois 等提出了弱一致性模型的思想 Gharachorloo 等提出了第一个释放一致性模型 为了提高性能，两种模型都放松了对RW 和RR顺序的要求,存储一致性决定写操作的数什么时候能够被读返回，使得多个处理器什么时候看到的数据是一致的 Lamport 第一次介绍了顺序一致性模型 严格保持RW, RR, WR, WW四种顺序,一致性的分析,首届全国百篇优秀博士论文获得者胡伟武关于存储一致性的研究 利用集合论中序关系的一些基本概念和结果，研究了有关顺序一致共享存储系统中的乱序执行技术的基本理论 给出了共享存储系统中判断一个执行正确与否的充要条件 给出了在共享存储系统中保证一个执行正确的访存次序条件 在执行正确性模型的基础上，提出了一种乱序执行的方案,一致性的优化举例,胡伟武的研究中，在顺序一致共享存储系统中使用乱序执行技术，系统效能提高50%左右, 胡伟武、夏培肃 顺序一致共享存储系统中的 乱序执行技术模拟实现,a = b = = a = b,a = = a b = = b,a与b的活跃 周期相交,a与b的活跃 周期不相交,生存性的描述,相干图（Interference Graph) 每个结点表示一个数据的生存期 结点的权值表示对应数据对象的大小 如果两个生存期可能同时存活(相干)，用一条边相连 运用 标量寄存器分配：对应到对相干图的图着色问题 聚合数据对象(数组，流)存储分配：对应到对相干图的区间着色问题,生存性的分析,我们研究了面向嵌入式应用的便笺存储器分配问题 大部分嵌入式应用的相干图满足包含相干性 我们首次证明了满足包含相干性的相干图为置换图(Permutation Graph) 首次提出了一个线性时间复杂性的，基于置换图着色的便笺存储器分配算法 该算法在大部分嵌入式应用相干图上能取得最优，相对国际最新的基于超完美图(Superperfect Graph)的算法，复杂性更低，性能更好,生存性的分析,我们研究了面向流应用的流寄存器文件分配问题 首次提出了一个基于存储器着色的流寄存器文件分配框架 巧妙地将开发复用和并行整合到对相干图的操作中 首次证明了绝大部分流应用的相干图为可比图(comparability graph)，或可以降解为多个可比子图 首次将流寄存器文件分配问题建模为最佳有向路径寻找问题，提出了一个最优或近似最优的流寄存器文件分配算法 该算法相对国际上普遍采用的基于Bin-Packing的First-Fit算法，具有更好的性能,生存性的优化举例,我们算法的效果 能在除QMR外的所有已有实际流应用相干图上取得最优流寄存器文件分配(用C表示) 在QMR上，能取得近似最优分配(用F表示),生存性的优化举例,在随机产生的1200个满足流应用特性的相干图中，我们的算法在98%以上的图中能取得最优，而First-Fit只在约25%的图中能取得最优,综合考虑六种数据访问特性,主要内容,存储墙提升计算速度的第一难题 结构与优化缓解“存储墙”的对策 使能技术解决“存储墙”可能的出路,一则新闻,2009年9月1日英国工程和物理科学研究委员会EPSRC出资6 million研制光计算机 研究单位：帝国理工学院 & 英国皇后大学 关键部分：纳米等离子器件 应用：未来超快计算机 时间：为期6年,铜互连,光互连,光互连的优势,物理属性 频率高 多维多重复用 弱衰减 自由空间传播,应用潜力 传输带宽高 并行通信 远距离通信 动态互连/可重构,光互连在计算机系统中的应用,机柜间光互连的应用已经非常广泛 板间光互连的应用正在逐渐兴起 芯片间光互连技术具备解决存储墙问题的巨大潜力，仍处于探索阶段,芯片间光互连技术的难点,现有光互连器件主要基于III-V、II-VI族化合物 机柜间、板间光互连用到的光收发器与调制器等 这些技术应用于芯片间光互连的问题 材料昂贵，不兼容CMOS工艺 器件尺寸较大 器件功耗较大,硅光器件技术取得一系列突破,2004年 Intel 1GHz硅光子调制器 Nature 此前的记录为20MHz 提高了50倍 2005年 Intel 硅基拉曼激光源Nature 单模模式下，80MHz激光线宽 光学性质优良,硅光器件技术取得一系列突破,2006年 美国Cornell大学 宽带光放大器 Nature 极大地拓宽了光信号放大 和变换的波长范围 显著提高了硅基光集成电路的信号处理能力 2008年 Intel 硅光子探测器Nature 340GHz增益带宽积 性能与传统的商业化光 探测器相当,硅光器件技术取得一系列突破,2008年 IBM 最小的光开关Nature Photonics 器件尺寸：45um x 22um 吞吐率：1Tbps 开关延迟：2ns 误码率：10-12 交调失真：-25dB,国际上芯片间光互连的研究项目,自1998年以来，美国DAPRA先后投入了2亿6千多万美元用于光互连相关的项目研究，其中4500万美元用于2003至2007年的芯片间光互连研究,国际上芯片间光互连的研究项目,美国：UNIC项目 2007-2012，美国DAPAR & SUN 4700万美元 高带宽、低延迟、低功耗、CMOS兼容，片内及片间光互连技术 美国其它多所企业和高校研究机构参与,国际上芯片间光互连的研究项目,欧盟：OPERA2015 合作计划 2005年启动，欧盟多个国家参与 旨在通过加强光学与光子学领域的合作，提高欧洲在信息技术领域的综合影响力 数十个芯片间光互连相关项目在研或已完成 欧盟：HELIOS项目 2008-2012，耗资1200万欧元 解决光器件的CMOS工艺制备与集成问题 40Gb/s调制器、10x10Gb/s收发器 等光器件,日本 ：Keisoku 10PFLOPS 超级计算机计划 NEC等预测到2010年CPU的 处理能力将达到100GFlops。 CPU与存储器之间需要至少 25000根数据传输线才能满 足CPU的处理速度 目标是实现CPU和存储器之 间1000个光通道，每个通道 20Gbps，总带宽达20Tbps 的光互连,国际上芯片间光互连的研究项目,国内芯片间光互连的研究进展,中科院微电子所、中科院深圳技术研究院 国家863 芯片间光互连技术与试验平台 单通道10Gb/s， 12路并行，误码率10-10 2007年 新型光电探测器EVPD 其它单位 天津大学、北京邮电大学、上海交通大学、东南大学、华中科技大学、国防科技大学等单位都进行了光互连相关技术研究,IBM对光互连发展趋势的观点,IBM关于2020年光互连技术的观点,在3-D堆叠技术的背景下通过芯片间和芯片内光互连进一步缩小计算部件和存储器件之间的速度差距，提高信号传输的带宽,纳米电子学的发展也可能推动 存储墙问题的解决,纳米电子学 2008年斯坦福大学制备出基于碳纳米管互联线的原型芯片，工作频率达到1GHz以上 2008年IBM