【学习课件】第十一章分布式共享内存

Chapter11第十一章分布式共享内存DistributedSharedMemory(DSM)Contents课程目录第十一章分布式共享内存01并行计算背景与动机02共享内存体系结构基础03分布式共享内存核心原理04DSM架构设计与实现05内存一致性与协议06关键技术挑战与优化07典型系统案例分析08前沿应用与总结展望Chapter01并行计算背景与动机从单核瓶颈到多核并行：理解共享内存系统的时代需求COMPUTERARCHITECTURE摩尔定律放缓与多核时代到来半导体工艺逼近物理极限导致单核性能增长放缓，处理器厂商从2005年起全面转向多核架构，并行计算成为应用获取性能提升的唯一路径。Intel多核处理器芯片实物01摩尔定律预测晶体管密度每18-24个月翻倍，但先进制程已进入纳米级物理极限，单核主频从2005年起增长明显放缓200502Intel、AMD等厂商全面转向多核架构策略，当前消费级CPU普遍配备4-16核，服务器CPU可达64核以上64核+03应用性能提升不再依赖硬件换代，而需主动设计并行算法以充分利用多核处理能力并行ApplicationScenarios大规模内存计算的典型应用场景MapReduce、图计算、深度学习等数据密集型应用对计算资源需求激增，这些场景共同特点是多处理器需频繁访问共享数据结构，使得共享内存抽象成为并行编程的核心基础设施。01MapReduce框架：Hadoop/Spark处理TB级数据集，需要多个Worker节点协同访问中间结果和共享状态。TB级数据集02图计算应用：社交网络分析与PageRank具有不规则内存访问模式，对共享内存系统的低延迟访问提出高要求。低延迟访问03深度学习训练：参数服务器需支持数百个GPU同时读写模型参数，共享内存成为参数同步的关键瓶颈。参数同步瓶颈数据中心服务器集群·机房实拍DistributedSharedMemory多处理器系统的两种基本形式多处理器系统分为单机共享内存（UMA/NUMA）和分布式共享内存两类。前者编程简单但扩展性受限，后者突破物理边界实现弹性扩展，但需要解决内存一致性等核心挑战。架构特征单机多处理器系统在一台计算机内集成多个处理器核心，典型代表包括多核（Multi-core）和众核（Many-core）架构Multi-core性能特点共享内存与互连所有处理器共享同一物理内存空间，通过片上总线或环形互连通信，延迟低但受限于单机物理容量UMA/NUMA架构特征分布式多处理器系统使用计算机网络将多台独立计算机连结成松耦合系统，每台节点拥有自己的私有内存LooselyCoupled核心挑战弹性扩展与一致性突破单机内存容量限制，可通过增加节点实现弹性扩展，但网络延迟和一致性维护成为核心挑战ConsistencyCHAPTER02共享内存体系结构基础从UMA到NUMA：理解共享内存架构的演进脉络SharedMemory共享内存的基本概念共享内存允许多个处理器通过读写同一内存区域进行通信，相比消息传递模式编程更直观，但需要处理同步与数据竞争问题。它是并行编程中最基础也最广泛的抽象模型。计算机主板上的内存条与内存插槽实拍共享内存定义：多个处理器可访问同一块物理或逻辑内存区域，通过共享变量实现进程间通信与数据交换与消息传递对比：消息传递需显式Send/Recv操作，共享内存通过Load/Store指令隐式通信，编程模型更贴近顺序程序核心挑战：多个处理器同时访问共享数据时可能产生数据竞争，需要锁、信号量等同步机制保证正确性MEMORYARCHITECTUREUMA架构：均匀内存访问UMA（UniformMemoryAccess）架构中所有处理器访问任何内存位置的延迟相同，通过共享总线或交叉开关连接统一内存。编程简单但受总线带宽限制，适用于处理器数量较少的系统。01核心特征：所有处理器对任意内存地址的访问延迟、带宽完全相同，无需关心数据的物理位置02互连方式：通过共享总线（Bus）或交叉开关（Crossbar）将所有处理器连接到统一的内存控制器03扩展性限制：共享总线带宽固定，处理器数量增多后争用加剧，通常适用于8核以下的小规模系统UMAvsNUMA架构特性对比UMA在延迟一致性和编程简便性上占优，NUMA在扩展性上显著领先MEMORYARCHITECTURENUMA架构：非均匀内存访问NUMA架构为每个处理器配置本地内存，访问本地内存延迟低、访问远程内存延迟高。它在保持共享内存编程模型的同时突破了UMA的总线瓶颈，是现代多路服务器的标准架构，也是DSM的设计基础。支持NUMA架构的双路服务器主板实拍01架构特征每个处理器节点拥有自己的本地内存，通过高速互连网络（如QPI、UPI）访问其他节点的远程内存02性能差异访问本地内存延迟约100ns，访问远程内存延迟可达200-300ns，存在明显的访问不对称性03DSM关联DSM本质上是在分布式网络环境下模拟NUMA行为，将物理分离的内存抽象为逻辑统一的地址空间ARCHITECTURECOMPARISON多处理器架构对比总结UMA、NUMA和消息传递代表了多处理器系统的三种基本范式，各有适用场景。DSM的核心价值是在分布式环境下融合NUMA的扩展性与共享内存的编程简便性。UMA/NUMA/消息传递架构特性对比特性维度UMANUMA消息传递内存访问延迟均匀一致本地快/远程慢显式通信扩展性低（<8核）中（数十核）高（数千节点）编程模型Load/StoreLoad/StoreSend/Recv硬件复杂度低中低典型应用桌面多核CPU多路服务器超算集群三种架构各有优劣，DSM试图在分布式环境下实现类似UMA/NUMA的共享内存编程体验CHAPTER03分布式共享内存核心原理从物理分离到逻辑统一：DSM的核心抽象与设计哲学DISTRIBUTEDSHAREDMEMORY分布式共享内存的定义分布式共享内存（DSM）将物理分离的多个内存模块抽象为逻辑统一的地址空间。'共享'指地址空间统一而非物理集中，使得分布式系统上的程序员可以像使用单机共享内存一样编程。01DSM全称DistributedSharedMemory，物理上分离的内存可被寻址为逻辑上统一的地址空间，使多个节点共享同一虚拟内存视图。02'共享'本质是地址空间共享而非物理集中：两个处理器上相同地址指向逻辑上的同一内存位置，而非同一物理芯片。03也称分布式全局地址空间（DGAS），涵盖软件层（操作系统、运行时）和硬件层（互联网络、缓存一致性协议）多种实现方式。分布式系统中多台服务器通过网络互联的物理场景DISTRIBUTEDSHAREDMEMORYDSM的核心设计思想：透明性DSM追求对程序员完全透明——开发者无需感知底层分布式架构，像编写单机程序一样使用共享变量，系统自动处理数据分布、传输与一致性维护，大幅降低分布式编程门槛。程序员编写代码的真实工作场景——DSM让开发者在分布式环境中获得同样的编程体验01透明性目标程序员无需感知程序运行在单机还是分布式集群，编程接口与单机共享内存完全一致接口一致02系统职责DSM底层自动处理数据定位、网络传输、缓存一致性等复杂问题，对应用层完全隐藏自动管理03实际权衡完全透明会牺牲性能，实际系统常采用"半透明"设计，允许程序员提供访问模式提示以优化性能半透明Chapter11·DistributedSharedMemory分布式全局地址空间（DGAS）DSM属于更广泛的分布式全局地址空间（DGAS）范畴，DGAS涵盖从硬件级到语言级的多种实现方案，共同目标是在分布式环境下提供统一可寻址的内存抽象。01上位概念：DGAS是DSM的上位概念，泛指所有在分布式系统上实现全局地址空间访问的技术方案02PGAS语言：UPC、Co-ArrayFortran、X10等语言级实现，显式区分本地与全局地址空间03技术谱系：涵盖硬件DSM、软件DSM、PGAS语言等多个层次，各有适用场景与性能特征支持DGAS技术的高性能计算中心环境编程模型DSMvs消息传递：编程模型对比DSM通过共享变量实现隐式通信，相比消息传递的显式Send/Recv模式，代码量减少50%以上，逻辑更直观。01消息传递模式Worker计算完局部结果后，需显式调用Send()发送给Master节点，通信代码侵入业务逻辑。Master需循环调用Recv()接收各Worker数据，再逐一累加到全局变量，需手动管理消息缓冲和通信顺序。代码冗长且易出错，开发者需自行处理死锁、乱序到达等复杂同步问题，调试困难。显式Send/Recv02DSM共享内存模式所有Worker直接对全局共享变量执行原子加操作，无需显式通信，编程模型与单机多线程一致。系统自动处理数据位置、网络传输和并发控制，对程序员完全透明，屏蔽分布式细节。代码简洁直观，逻辑与单机程序一致，显著降低分布式编程的认知负担和开发门槛。隐式共享变量COREARCHITECTUREDSM系统的核心组件DSM系统由地址映射、分布式缓存、一致性协议三大核心组件构成，辅以目录服务和网络传输层。这些组件协同工作，实现"物理分散、逻辑统一"的共享内存抽象。01地址映射模块：将逻辑地址转换为物理地址，确定数据实际存储在哪个节点，支持静态和动态映射策略02分布式缓存：每个节点维护远程数据的本地副本，利用时间/空间局部性减少网络访问，是性能优化的关键03一致性协议：核心中的核心，确保多节点上的缓存副本保持同步，不同协议在一致性强度与性能间权衡服务器内存硬件物理形态CHAPTER04DSM架构设计与实现从操作系统到编程库：软件DSM的多种实现路径COMPARISON软件DSMvs硬件DSM硬件DSM依赖专用网络接口与一致性控制器，性能优异但成本高、灵活性差；软件DSM通过操作系统或编程库实现，更具灵活性和可移植性，是当前研究与应用的主流方向。硬件DSM实现01需要专用网络接口卡（NIC）和缓存一致性控制器，硬件成本高但延迟极低，适合对性能要求苛刻的场景02典型代表：SGIOrigin、StanfordDASH，适用于高端服务器和超级计算环境03扩展性受硬件互连拓扑限制，通常支持数十到数百个节点，部署维护复杂数十~数百节点软件DSM实现01基于标准以太网和通用服务器构建，成本低、可移植性强，适合大规模集群部署02操作系统级实现对程序员透明，编程库级实现需调整编程方式但更灵活可控03典型代表：TreadMarks、JIAJIA、Kerrighed，可运行于普通Linux集群环境大规模集群DistributedSharedMemory操作系统级DSM：虚拟内存扩展操作系统级DSM通过扩展虚拟内存管理实现共享内存：当节点访问的共享页面不在本地时触发缺页异常，DSM内核模块从远程节点获取页面并映射到本地。整个过程对应用程序完全透明。Linux内核开发与虚拟内存管理环境01核心机制：利用操作系统的缺页异常（PageFault）机制，当访问的共享页面不在本地时触发异常02页面获取：DSM内核模块捕获异常后，通过网络从Owner节点或缓存节点获取页面副本并映射到本地03完全透明：应用程序无需任何修改，使用标准的Load/Store指令即可访问分布式共享内存LIBRARY-LEVELDSM编程库级DSM：显式API调用编程库级DSM通过显式API（如dsm_malloc、dsm_lock）实现共享内存管理，虽增加编程复杂度，但具有更好的可移植性、更精细的性能优化空间和更易调试的特点。01显式API：程序员需调用dsm_malloc()分配共享内存，dsm_lock()/dsm_unlock()进行同步控制02可移植优势：不依赖特定操作系统的虚拟内存机制，可跨平台运行于Linux、Windows等多种系统03优化空间：程序员可通过API提供访问模式提示（如只读/读写），系统据此做更精细的缓存与一致性优化程序员通过显式API进行系统编程与调试DISTRIBUTEDSHAREDMEMORY共享内存区域的三种组织方式DSM系统提供三种共享内存组织方式：基于页（固定大小）、基于对象（可变大小）、基于元组（协调单元）。不同方式适用于不同场景，在实现复杂度与编程灵活性之间权衡。基于页（based）将共享内存划分为固定大小页面（通常4KB-64KB），复用操作系统的虚拟内存管理机制。实现简单、与OS集成度高，但可能存在内部碎片和falsesharing问题。4KB–64KB基于对象（Object-based）将共享区域组织为存储可变大小对象的抽象空间，更贴合面向对象编程范式。减少falsesharing，但需要对象序列化/反序列化开销，实现复杂度较高。可变大小基于元组（Tuple-based）以元组为基本共享单位，常用于Linda等协调式并行编程模型。天然支持生产者-消费者模式，但编程模型与传统共享内存差异较大。LindaDISTRIBUTEDSHAREDMEMORYDSM内存分布策略DSM系统采用两种内存分布策略：部分共享（私有内存+分布式共享区+集中主存）和全部分布（所有内存分布于各节点）。前者实现简单但扩展性受限，后者扩展性优但管理复杂度高。MODE01部分共享模式每个节点保留私有内存，同时划出部分内存作为共享区域分布在集群中存在集中式主存作为后备存储，共享数据可从主存加载或写回实现简单，但集中主存可能成为性能瓶颈，扩展性受限扩展性受限MODE02全部分布模式所有内存完全分布于各节点，无集中式主存，每个节点包含私有和共享两部分共享数据以页面或对象粒度在节点间动态迁移和复制扩展性优异，可随节点增加线性扩展总内存容量，但一致性管理更复杂线性扩展DataManagementOwner-Replica数据管理模型DSM中每个共享数据单元有唯一的Owner节点（权威管理者）和多个Replica副本（缓存加速）。读操作可从任意副本获取，写操作需经Owner授权，这种模型是DSM数据管理与一致性维护的基础。分布式系统中数据分布的物理承载环境Owner节点：每个共享页面或对象有唯一的Owner，负责管理该数据的一致性状态和权限分配OwnerReplica副本：其他节点可缓存数据副本以加速本地访问，但修改前需向Owner申请写权限Replica动态迁移：Owner身份可根据访问模式动态迁移，将数据移向访问最频繁的节点以减少网络开销MigrateCHAPTER05内存一致性与协议从严格一致到松弛一致：理解DSM一致性模型的设计权衡MEMORYCONSISTENCY什么是内存一致性内存一致性定义多处理器同时访问共享内存时的"可见性规则"——即一个处理器的写入何时对其他处理器可见。并发编程的软件开发与调试场景核心问题：多个处理器并发读写共享变量时，系统应保证怎样的操作顺序和可见性语义分布式挑战：网络延迟导致写入不能瞬间传播，缓存副本可能过期，不同节点看到的数据版本可能不同一致性契约：一致性模型定义了"写入何时对其他处理器可见"的规则，是程序员与系统之间的语义约定SEQUENTIALCONSISTENCY严格一致性（SequentialConsistency）严格一致性要求所有处理器操作按某一全局顺序执行，且每个处理器的操作保持程序顺序。它对程序员最友好、行为完全可预测，但要求每次写入全网同步确认，性能代价极高，实际DSM系统很少采用。01全局顺序定义：存在一个全局操作顺序，所有处理器看到的操作序列相同，且每个处理器的操作保持程序顺序。02编程友好：程序行为完全可预测，程序员无需考虑内存模型细节，调试简单。可预测性100%03性能代价：每次写入需等待全网同步确认，网络延迟直接成为性能瓶颈，实际DSM系统极少采用严格一致性。极少采用一致性模型多维度对比严格一致性编程简易但性能差，松弛一致性性能优但编程复杂DistributedSharedMemory松弛一致性模型松弛一致性放松操作顺序约束，允许写入延迟传播，仅在同步点保证一致性。弱一致性和释放一致性是两种典型实现，在性能与编程复杂度之间取得更好平衡。弱一致性WeakConsistency只在同步操作（如acquire/release）时保证所有之前的写入对其他处理器可见同步操作之间的普通读写不保证顺序，允许乱序执行和延迟传播性能优于严格一致性，但程序员需在关键位置插入同步操作释放一致性ReleaseConsistency获取锁（acquire）时从Owner拉取最新数据，释放锁（release）时将修改推送给其他节点临界区内的读写操作完全本地化，无网络开销，性能接近单机共享内存是TreadMarks等经典DSM系统采用的一致性模型，实践证明性能优异DISTRIBUTEDSHAREDMEMORY一致性协议：写无效vs写更新一致性协议通过写无效或写更新策略维护缓存一致性。写无效减少网络流量，写更新保持副本最新。大多数DSM系统采用写无效策略。WRITE-INVALIDATE写无效节点写入前，向所有持有副本的节点发送无效化消息，使远程副本失效写入节点获得独占权限后可连续写入，无需每次通知，适合写密集型场景其他节点再次访问时需重新获取数据，可能增加读延迟写密集优先WRITE-UPDATE写更新节点写入时，将新值广播给所有持有副本的节点，远程副本同步更新副本始终保持最新状态，读取时无需额外获取，适合读密集型场景每次写入都需网络广播，频繁写入时网络开销大，可能导致带宽瓶颈读密集优先DirectoryProtocol目录协议（DirectoryProtocol）目录协议通过维护每个共享页面的状态信息（Owner、副本位置、共享/独占状态）来跟踪数据分布。节点访问共享数据前先查询目录获取路由信息，再与目标节点通信。目录可集中或分布式存储，各有优劣。数据中心网络基础设施·分布式系统的物理载体01目录功能：记录每个共享页面的Owner节点、持有副本的节点列表、当前共享/独占状态等元信息02访问流程：节点访问共享数据前先查询目录获取路由信息，再直接与Owner或副本持有者通信03存储策略：集中式目录实现简单但可能成为性能瓶颈；分布式目录（每个节点管理部分目录）扩展性更优CHAPTER06关键技术挑战与优化从FalseSharing到网络延迟：DSM系统的性能瓶颈与突破DSMPERFORMANCEFalseSharing：虚假共享问题FalseSharing因共享页面触发无效缓存失效与网络传输，是基于页的DSM最常见性能陷阱。FalseSharing对DSM性能的影响严重FalseSharing可导致执行时间增加12倍01问题本质：两个处理器访问同一页面中的不同变量，虽无实际数据依赖但因共享页面而互相触发缓存失效02性能影响：每次写入导致对方副本无效化，频繁触发网络传输和页面重新获取，性能可能下降10倍以上12×延迟03解决方案：增大页面粒度、使用基于对象的细粒度共享、编程时注意数据对齐使独立变量分布在不同页面DSM·PerformanceOptimization网络延迟优化策略网络延迟是DSM的天然瓶颈，跨节点访问延迟可达单机NUMA的10-100倍。预取、批量传输、流水线三大策略通过减少处理器等待时间来缓解延迟影响，是DSM性能优化的核心手段。预取根据访问模式预测即将访问的数据，在处理器实际需要前发起网络获取请求可有效隐藏网络延迟，但预测不准确时会浪费带宽并污染缓存适用于规则访问模式，需权衡预取深度与缓存开销Prefetching批量传输将多个小的内存请求合并为一次大的网络传输，减少网络往返次数在同步点一次性传输所有修改，显著提高网络利用率降低协议开销，减少网络拥塞，提升整体吞吐性能BulkTransfer流水线重叠计算与通信操作，在当前数据计算时预取下一批数据需要程序具有良好的并行结构，编译器或运行时系统辅助识别流水线机会最大化资源利用率，实现计算与通信的高效重叠PipeliningDistributedSharedMemory·ConsistencyStrategies页面迁移与复制策略DSM通过页面迁移（独占写入场景）和副本创建（只读共享场景）来平衡数据局部性与一致性开销。混合策略根据访问模式动态选择，是实际系统的主流实现方式。页面迁移Migration当某节点频繁写入远程页面时，将页面整体迁移到该节点，后续写入变为本地操作，减少远程访问延迟。适合写密集型访问模式，但迁移开销大且可能导致"乒乓效应"（页面在两节点间反复迁移）。写密集型副本创建Replication当多个节点只读访问同一页面时，在各节点创建本地副本，读取变为本地操作，显著提升读性能。适合读密集型访问模式，但写入时需维护多副本一致性，写操作开销增大。读密集型SCALABILITYDSM可扩展性挑战与对策DSM可扩展性受一致性通信开销（O(n²)）、目录查询延迟、网络带宽等因素制约。层次化目录、分组一致性、自适应协议等技术通过减少全局同步、增加局部化操作来提升大规模集群下的扩展能力。01扩展性瓶颈：一致性协议通信开销随节点数呈O(n²)增长，目录服务查询延迟随规模增大，网络带宽成为共享资源02层次化目录：将全局目录组织为树状层次结构，局部查询在子树内完成，减少跨集群通信03分组一致性：将节点按访问模式分组，组内严格一致、组间松弛一致，平衡一致性与性能04自适应协议：根据运行时访问模式动态切换一致性策略，写密集时迁移、读密集时复制DSM系统可扩展性表现64节点时实际加速比约为理想值的65%CHAPTER07典型系统案例分析从TreadMarks到Kerrighed：经典DSM系统的设计与实现DISTRIBUTEDSHAREDMEMORY·§11TreadMarks：经典软件DSM系统TreadMarks是普林斯顿大学开发的经典软件DSM，采用基于页的组织、释放一致性模型和写无效协议。其LazyReleaseConsistency创新将一致性维护延迟到锁获取时批量执行，显著减少网络通信，成为后续DSM系统的设计范本。系统定位运行于普通工作站集群的软件DSM，无需特殊硬件支持，可移植性强。采用4KB标准页大小，与操作系统内存管理无缝衔接，降低实现复杂度。软件DSM·4KB页普林斯顿大学·TreadMarks系统诞生地核心创新LazyReleaseConsistency将一致性维护延迟到锁获取时批量执行，合并多次写操作为一次网络传输，显著降低通信开销，提升多节点扩展性。LazyRC技术特征基于页的共享组织、写无效协议、分布式目录管理，支持动态页面迁移与复制，实现高效的内存一致性维护。写无效·目录管理CHAPTER11·DISTRIBUTEDSHAREDMEMORYJIAJIA：国产高性能DSM系统JIAJIA由中科院计算所开发，在国际DSM评测中多次取得优异成绩。它采用基于锁的释放一致性和Home-based协议，在保持高性能的同时简化实现复杂度，展示了国产系统软件在高性能计算领域的竞争力。中国科学院计算技术研究所01研发背景：中科院计算所胡伟武团队开发，旨在让普通集群也能运行大规模并行应用胡伟武团队02技术特色：采用Home-based释放一致性协议，每个页面有固定的Home节点，简化目录管理和一致性维护Home-based03性能表现：在国际DSM评测基准（如SPLASH-2、NASParallelBenchmarks）上多次取得领先成绩SPLASH-2SINGLESYSTEMIMAGEKerrighed：单系统映像操作系统Kerrighed是基于Linux的单系统映像（SSI）操作系统，将多台物理机器融合为一台"虚拟大机器"。它在内核层面实现DSM、进程迁移和负载均衡，用户无需修改代码即可在集群上运行任何Linux程序。运行KerrighedSSI系统的Linux集群物理环境01系统定位：基于Linux内核的单系统映像操作系统，将多台物理机器融合为一台逻辑统一的"虚拟大机器"02核心能力：内核级DSM实现、透明进程迁移、全局进程管理、自动负载均衡，对应用程序完全透明03用户体验：用户登录集群如同登录单机，无需修改代码即可运行任何Linux程序，极大降低使用门槛DistributedSharedMemory典型DSM系统特性对比不同DSM系统在实现层次、一致性模型、透明性等方面各有侧重，但共同目标是在分布式环境下提供简化的共享内存编程体验。学术系统注重创新验证，工业系统注重稳定可用。典型DSM系统关键特性对比系统名称实现层次一致性模型透明性研发机构TreadMarks编程库LazyRelease半透明普林斯顿大学JIAJIA编程库Home-basedRC半透明中科院计算所Kerrighed操作系统based完全透明INRIA法国OpenSSI操作系统based完全透明Compaq/开源社区MOSIX操作系统based完全透明希伯来大学编程库级DSM灵活性高但需修改代码，操作系统级DSM完全透明但需定制内核CHAPTER08前沿应用与总结展望从云计算到异构计算：DSM技术的现代化演进CHAPTER11·DSMAPPLICATIONSDSM在云计算与大数据中的应用DSM技术在云计算时代焕发新生：分布式数据库的内存缓存层、机器学习参数服务器都是DSM的现代应用形态。RDMA技术的普及使跨节点内存访问延迟大幅降低，推动DSM在云环境下性能持续提升。分布式缓存RedisClusterRedisCluster、Memcached等分布式缓存系统本质上实现了DSM的共享内存抽象，为Web应用提供全局内存访问能力。参数服务器TensorFlowTensorFlow、PyTorch等深度学习框架的参数服务器是DSM在机器学习领域的典型应用，支持多GPU共享模型参数。RDMA加速μsLatency远程直接内存访问技术使跨节点内存访问延迟降至微秒级，显著提升DSM在云环境下的性能表现。云计算数据中心基础设施·