一、Popcorn DSM:distributed shared memory
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
https://www.ssrg.ece.vt.edu/papers/icdcs20.pdf
(0) Migrating Execution Contexts
要跨计算机边界迁移线程,我们需要获取描述原始节点上线程当前状态的执行上下文。幸运的是,现代操作系统维护这样
的执行上下文,以在系统调用和上下文切换之间保留线程状态。特别是,Linux使用结构pt regs和结构mm_struct分别
在系统调用和上下文交换机之间保留寄存器和虚拟地址状态。我们利用这些机制来获取执行上下文。
DEX通过消息层在节点之间传输执行上下文(有关详细信息,请参见第III-E节)。我们将引用创建进程线程的节点作为
线程的原点。进程中的所有线程都具有相同的起源,即第一次创建进程的节点。我们将将线程迁移到的节点称为远程节
点。例如,在图1中,节点1是线程的起源,节点0是线程0的远程,节点2是线程2和3的远程。在将执行上下文发送到远程
后,源端的原始线程等待来自远程的配对线程的传入请求。
在远程节点,DEX从接收到的执行上下文重建原始线程。它首先创建一个使用接收到的上下文初始化的远程线程。然后,
远程线程被放入作业调度程序的运行队列中,以便最终可以调度它。请注意,DEX仅传输在远程开始执行线程所必需的最
小执行上下文;应用程序的虚拟内存数据在此阶段不传输。
远程线程可以要求其相应的原始线程代表其在原点工作。例如,远程线程可能需要来自源的虚拟内存区域(VMA)信息来
复制其地址空间,如图1中的3所示。当远程线程向源发送工作请求时,请求将被调度到迁移或处理最后一个工作请求后处
于睡眠状态的原始线程。原始线程被唤醒,在原始线程的上下文中处理请求,并返回结果。原始线程再次进入睡眠状态,
等待来自对等远程线程的下一个请求。
此工作委托设计最大限度地减少了对内核的更改,但透明地支持分布式环境中的有状态操作系统功能。实际上,重新实现
所有操作系统功能(如futex和文件I/O)以支持分布式执行环境是不可行的。相反,DEX通过工作委托重用现有实现。当
远程线程需要有状态内核功能时,请求将移交给原始线程,在源端执行,只有其结果才会传回远程线程。从内核的角度来
看,这与处理来自本地线程的请求相同。通过这种方式,DEX可以透明地向分布式线程提供许多操作系统功能,而无需进
行重大的内核修改。例如,DEX支持futex(快速用户空间互斥体),这是Linux [18]上实现线程同步原语的核心机制。
当远程线程调用线程同步操作时,该操作将有效地转换为一个或多个futex系统调用。futex操作被转发到其原始线程,
并通过原始futex实现在原点处理。因此,应用程序可以使用基于futex的线程同步原语,而不管它们的位置如何。
尽管为工作委派配对线程,DEX仍然需要远程处的额外线程来处理节点范围的操作。考虑原点上的线程收缩VMA的情况。更
新应应用于所有远程线程,以防止非法内存访问操作。但是,从源的角度来看,不清楚哪个远程线程应该更新每个远程节
点上的VMA。因此,DEX为每个远程节点中的每个分布式进程创建一个名为远程工作程序的线程。节点范围的操作,如VMA
修改和,原始进程退出,将传递给远程工作进程,并在远程工作进程的上下文中处理。
迁移的执行也可以带回原点。这种向后迁移几乎与正向迁移相同;DEX在远程收集远程线程的执行上下文,将上下文传输
到源,用最新的上下文更新原始线程的上下文,并恢复原始线程的执行。远程线程在向后迁移完成后退出。恢复的原始线
程可以继续到原点,也可以再次迁移到任何节点。
在当前实现中,正向和反向迁移都是由系统调用启动的。我们相信,它可以很容易地扩展,以便操作系统调度程序或用户
空间库自动启动迁移。当进程中的线程首次迁移到节点时,DEX使用给定的地址空间信息启动远程工作程序,并使用克隆
线程从远程工作程序分叉远程线程,允许它们共享地址空间。来自同一进程的后续迁移请求可以通过简单地从远程工作线
程分叉来处理。通过这种方式,DEX以较低的开销处理多次和重复迁移,这通常在具有多个并行执行区域的应用程序中找
到。
DSM:
> 前置条件:
(1) 只支持sequential memory consistency model
(2) 由于线程共享相同的虚拟地址空间,因此所有线程必须具有相同的内存视图。
> Popcorn限制
1. 编译CONFIG的限制
```c
//https://github.com/ssrg-vt/popcorn-kernel/wiki/VM-Setup
You can use your own configuration file, but MAKE SURE that the following configurations are disabled:
CONFIG_SWAP
CONFIG_TRANSPARENT_HUGEPAGE
CONFIG_CMA
CONFIG_MIGRATION
CONFIG_COMPACTION
CONFIG_KSM
CONFIG_MEM_SOFT_DIRTY
Page should be 4 KB.
ARM should select ARM64_4K_PAGES
PPC should use CONFIG_PPC_4K_PAGES.
- 代码编写限制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
//https://github.com/ssrg-vt/popcorn-kernel/wiki/Compiler-Setup Limitations 1.Bring back migrated-away threads to their original node before exiting from the program. //1.在migrate到远程节点的线程回迁之前, 进程不能退出。 2.A migrated thread should be brought back to the original node to be relocated to other node. For example, to migrate a thread which was created at node 0 and is running at node 1, the thread should be migrated back to node 0 before it is migrated to node 2 again. //2.线程不能直接从node1迁到node2,需要先将node1线程迁回node0(origin)后,从node0迁移到node2; 3.You can do file I/O at any location, but file descriptors are not synchronized between migrated threads. This means, console is not migrated and printf() might not work neither. To check the execution progress, we recommend to open() a file at an absolute path, write() to the file, and close() for each print-out. File operations (e.g., fopen(), fwrite()) might not work neither. //3. 不支持线程中间共享文件,因此printf可能无法使用;文件读写只能在该线程内进行fopen,fwrite,fcolse. 4.You cannot create a thread while the thread is running at a remote node. //4.在remote节点执行的线程不能在创建新线程。 5.Networking is not supported. //5.这个是通信层导致的。
**works: **
(1) 维护页面的所有权来跟踪最新页面的位置, 基于the multi-reader single-writer memory model. 初始时,origin独占进程的所有页面,远程节点必须联系origin获取页面数据和页面所有权。 如果请求是读取访问,则源将共同所有权授予远程,以便源和远程都可以同时访问该页。当远程请求一个要写入的页面 时,源通过发送所有权撤销请求从其他节点(包括自身)撤销所有权,授予它独占所有权。 为了使网络流量最小化,当远程节点已经拥有最新的页面数据时,源节点只需授予所有权,而无需转移页面数据。信息, 如所有者列表和页面状态维护在每进程基树中,该基树通过虚拟页面地址索引信息。
(2) memory consistency protocol是通过page fault hander来触发的。 leader-follower model解决页面错误处理中固有的并发问题。 i. 页面错误处理中固有的并发问题的影响 这种并发的错误处理使DEX中的所有权跟踪变得复杂。在内存一致性协议中,页面准备时,需要更新页面所有权。但是, 节点中的多个线程可能同时请求同一页。这可以发起多个协议请求,即使所有每线程的请求都是针对同一个页面的。如果 一个线程由于更改了PTE或线程之间的冲突而必须放弃读取的页面,则这会变得更加复杂;为了安全地放弃读取的页面或 解决冲突,内核应该维护per PTE元数据以标识哪个线程由于任何原因更改了PTE。这可能会减慢页面错误处理程序,这 是不能接受的。 ii. leader-follower model 为了有效地抑制页面错误处理中固有的并发性,我们在页面错误处理程序中采用了领导者-跟随者模型。DEX维护一个每个 进程的哈希表,以跟踪所有正在进行的故障处理。触发页面第一个故障的线程成为该页面的页面故障处理的leader。需要 具有相同访问类型(即读或写)的相同页面的后续线程成为领导者的追随者。leader执行准备页面的操作;它通过发送请 求和失效来从其他节点带出页面。leader处理故障后,同时更新对应的PTE。在领导者恢复执行之前,它会唤醒所有追随 者。追随者不会再次处理错误,相反,他们只是使用更新的PTE恢复执行。这样, DEX聚合了类似的页面错误类型,并通 过单个页面错误处理来处理它们。
(3)On-Demand VMA Synchronization Linux中的VM子系统在两个级别管理内存:虚拟内存区域(即VMA)和页表条目(PTE)。VMA维护地址空间范围的权限、备 份文件、文件中的偏移量等。另一方面,PTE保持当前的每页状态。由于VMA信息必须由进程中的线程共享,DEX需要一种 类似于上一节中解释的内存一致性协议的机制。但是,线程通常使用不相交的VMA(例如,线程本地存储),这使得在所 有线程中完全同步VMA是不必要的(甚至是禁止的)。出于这些原因,我们部署了按需VMA同步。
1
2
3
4
5
6
7
在执行上下文迁移期间,不会将VMA信息传输到远程。当远程线程看到丢失的VMA(即,正在访问的地址不属于它拥有的任
何VMA)时,它将联系源检查访问是否合法。如果访问是合法的地址范围,并且存在与该地址对应的VMA,则意味着远程节
点具有过时的VMA信息。在这种情况下,源端回复有关VMA的最新日期信息,远程相应地更新其VMA。如果访问无效,源将
向远程发送错误代码,该错误代码将终止远程线程,就像执行了非法内存访问一样。
所有VMA操作都是通过使用第III-A节中解释的工作委托在原点执行的。仅当操作收缩VMA区域(例如,munmap)或降级
(例如,m保护)其访问权限时,源端才广播更新的VMA信息;许可操作(例如,mmap)不会急于同步,而是通过按需VMA
同步机制更新。
(4)Inter-node Communication 通信层在分布式系统中对性能至关重要。此外,通信层应足够灵活,以支持DEX实现中高度并发和复杂的通信使用。为 此,我们设计并实施了一个基于InfiniBand的节点间消息传递系统,以利用现代互连技术的高带宽和低延迟。 在系统启动时,节点读取配置,以在InfiniBand可靠连接(RC)模式下为每个节点对建立通信通道。消息通过相应的连 接路由到目标节点,节点上的消息处理程序处理传入的消息。 与传统套接字不同,用于通过InfiniBand发送和接收的I/O缓冲区必须显式映射到支持DMA的地址空间范围,以便 InfiniBand主机控制器适配器(HCA)可以从缓冲区执行DMA。此外,要执行远程DMA (RDMA),我们还必须将缓冲区与 RDMA内存区域关联,远程节点可以使用远程密钥从缓冲区执行RDMA。以前的研究表明,DMA映射和RDMA区域关联成本高昂 [20]–[22];因此,我们的设计旨在最大限度地减少这些操作。 在DEX中,消息的大小是双峰的;控制消息很小,范围可达数十字节,而页面数据以4KB消息传输。由于RDMA区域关联和 RDMA完成控制路径【21】的高开销,通过RDMA传输小消息对DEX来说成本太高。相反,DEX使用InfiniBand VERB传输小消息。为了避免昂贵的DMA映射,我们在消息层中使用了发送缓冲池。每个连接都有自己的专用发送缓冲池,在初始设置 期间配置。在内部,池由映射到支持DMA的地址空间范围的物理连续页面块组成,池将这些块作为环形缓冲区管理。上下 文(例如,捕获到页面错误处理程序的线程)可以从池分配缓冲区,并在缓冲区中编写出站消息。由于缓冲区是DMA就绪 的,因此可以在没有DMA映射的情况下发送消息。发送完成时,池将回收缓冲区。
1
2
3
4
5
6
7
8
9
10
11
12
13
类似地,DEX维护入站消息的接收缓冲池。每个连接在初始设置阶段通过发布使用DMA映射内存区域构建的接收工作请求来
设置接收缓冲池。InfiniBand HCA通过DMA将传入数据写入缓冲区,并通过完成队列将事件通知主机。在处理传入消息
事件后,DEX通过使用缓冲区重新初始化接收工作请求并再次发布请求来回收DMA就绪缓冲区。通过这种方式,DEX消除了
小消息的DMA映射和内存副本。DEX利用RDMA传输大型消息,如页面数据。与特定于域的RDMA工作[20]–[24]不同,DEX必
须支持任意用户应用程序。因此,不可能预先确定进程的虚拟内存占用空间和生存期,这些进程会随着时间的推移而动态
变化,并且彼此不同。此外,在物理内存中保持应用程序的虚拟内存地址空间连续实际上是不可行的。因此,我们排除了
这些域特定系统常用的RDMA内存区域关联的静态方法。另一方面,动态RDMA区域关联的成本如此之高,以至于它可以抵
消RDMA的好处。
基于这些观察,我们设计了一种使用RDMA和内存复制的混合方法。每个连接都有一个RDMA接收器,该接收器在连接初始
化期间设置。RDMA接收器由物理连续页面的块组成,在设置期间,这些块与RDMA内存区域关联。要执行RDMA, DEX从
RDMA接收器分配缓冲区,并要求其对等体对位置执行RDMA。当对等方通知RDMA完成时,RDMA接收器中的数据将复制到其
最终目的地(即应用程序虚拟内存中的页面)并释放。即使这种方法涉及一个内存副本,但它比为内存一致性协议中的每
个页面执行RDMA关联更快。
IV. ADAPTING APPLICATIONS 我们将在第五节中展示的BA,许多应用程序都是可扩展的,因此它们可以轻松地扩展到DEX上的单机性能之外。但是,某些 应用程序不会不修改地扩展,因为DEX以页面粒度提供内存一致性。这可能导致(1)竞争页面,其中对同一页面上程序对象 的冲突访问(读/写和写/写)会导致跨节点干扰,(2)内存一致性协议开销,其中多节点读取,单节点写入模式导致一致 性协议向网络泛洪所有权无效消息。DEX提供了一组工具,帮助开发人员识别和消除应用程序中的这些瓶颈。由于DEX提供了 共享内存编程模型,开发人员在分析时可以花费最小的精力,通过使用DEX提供的工具和调整应用程序以实现群集上的可扩 展性,而不是MPI等其他编程模型,后者可能需要对整个应用程序进行全面检查。 A.分析页面故障 首先,对应用程序进行分析,以确定哪些组件导致了最多的跨节点流量。DEX提供了一个分析工具,该工具为需要DEX中内 存一致性协议的每个观察到的页面错误收集包含六元组的页面错误跟踪。每个元组包含页面故障发生时的系统时间、故障 发生的节点ID、故障任务的任务ID、故障类型(即读/写/无效)、故障指令的内存地址、导致故障的内存地址,以及用于 标记应用程序的单个部分的用户指定的标识符。DEX可以配置为收集每个故障的此信息,并通过ftrace将其移交给用户空 间。 对于分析,应用程序是使用调试信息构建的,并使用DEX的分析工具运行的。执行后,分析工具将跟踪与二进制文件一起 后处理,以提供丰富的分析集,例如识别导致最多页面错误的程序对象或源代码位置、随时间推移的页面错误频率、每线 程内存访问模式、等。使用这些跟踪,我们可以识别跨节点流量的来源,并应用一组小而有效的优化,以获得更好的可扩 展性。 应用程序数据通常可以分为两类:(1)所有线程使用的全局数据,通常由数组或自定义数据结构(例如,图形)组成, (2)每节点数据,其中包括节点上所有线程的每线程数据和其他数据结构(例如,NUMA感知应用程序【16】中的过滤图或逻辑分区堆)。优化数据访问模式的方法因每个类别而异。对于每个节点的数据,分析工具有助于识别放置在同一页面 上的多个节点的数据;然后,开发人员可以轻松地将这些数据分离到不同的页面上,以避免争用。对于全局数据,该工具 帮助开发人员找到次优的数据访问模式,然后可以优化这些模式以进行横向扩展。此外,开发人员还可以通过数据访问提 示将这些模式表达到DEX系统,以减少协议开销。
B.减少虚假页面共享 在许多共享内存应用程序中,有几种常见的错误共享来源,这些来源很容易使用页面故障跟踪识别和删除。以下方法有助 于消除将多个节点的每个节点数据共定位到同一页面上所导致的错误共享。 堆栈。每个应用程序线程都被分配自己的本地运行时堆栈以执行。但是,通常,在分叉子线程时,父线程将使用自己的堆 栈将数据传递给子线程,例如,传递给p线程创建或OpenMP共享变量的数据指针。当子线程读取/写入共享程序对象,而父线程在同一页面上的其他位置写入自己的堆栈时,这将导致错误共享。为了消除这种类型的错误共享,我们识别并将有 问题的堆栈数据重新定位到全局内存中,或将数据下推到子线程的线程本地存储中。特别是对于OpenMP,我们修改了编译 器,以在并行区域的持续时间内自动将共享变量卸载到全局内存。 全局数据和堆。如果将两个访问类型冲突的程序对象分配给同一页面,则全局程序状态(包括静态和动态分配的数据)可 能会导致错误共享。这个问题很容易纠正:用户可以简单地使用静态数据的对齐声明属性添加填充和对齐对象到页面边 界,并使用posix memign分配动态数据。但是,盲目地将这些修复程序应用于所有程序对象可能会导致严重的内存膨 胀。将每个声明的程序对象移动到单独的页面将导致二进制文件的大小膨胀,而动态分配其自己页面中的每个对象将导致 分配大量小对象的程序的极端内部内存碎片和内存不足错误。更糟糕的是,将所有对象移动到单独的页面可能会通过降低 空间局部性和污染缓存而导致性能下降。我们没有将页面对齐应用于每个程序对象,而是根据页面错误跟踪识别并有选择 地对齐造成干扰最大的每个节点对象。
C.优化全局内存 分析工具还通过识别发生故障数量最多的源代码位置,帮助开发人员优化以前未见过的应用程序的全局内存使用情况。通常, 两个瓶颈位置会出现在一起——一个位置会引起大量写入故障,而另一个位置会引起相关数量的读/写故障。另一个争用来源是 全局共享标志;一些应用程序在某些条件保持的情况下继续迭代(例如,图计算继续,直到节点数据没有更改)。与其盲目检 查和设置标志,不如在本地存储每个线程的标志更新,并在迭代结束时执行全局标志更新。该工具有助于识别应用程序中导致 瓶颈的数据访问模式,并纠正它们。由于DEX的可编程性优势,开发人员可以轻松、渐进地优化这些模式以进行横向扩展。
V. EVALUATION D. Performance of DEX’s Mechanisms Thread migration overhead. 为了测量线程迁移开销,我们使用了一个微基准,它每秒重复迁移一个线程。我们测量了在源节点和远程节点处理线程迁 移的时间。表II总结了使用10个线程迁移的平均值的结果。 第一次正向迁移总共需要812.1μs,而第一次反向迁移总共只需要24.7μs。当线程再次迁移到同一节点时,第二次正向迁 移只花了230.0μs,仅占第一次迁移总时间的28.3%。第二次向后迁移的时间几乎与第一次向后迁移的时间相同。随后向 同一节点迁移的延迟与第二次迁移的延迟相似。 第一次和第二次正向迁移之间的延迟差异来自构建每进程数据结构的时间。在第一次迁移期间,DEX处理大多数每个进程 的过程,如创建远程工作程序、设置地址空间和设置其他进程级数据结构。图3显示了分解延迟的评估结果,该结果确认 了620.0μs的第一次迁移被每个进程的过程占用,由符号键“Remote Worker”表示。 正向和反向迁移延迟之间的延迟差异来自于每种迁移类型所需的工作量。在正向迁移期间,DEX创建线程并使用原始执行 上下文设置线程。相反,向后迁移只需要更新原始线程的状态,这比正向迁移快得多。
Page fault handling overhead. 页面故障分析处理性能,我们创建了另一个微基准,它分叉两个线程,并将其中一个线程重新定位到远程。然后,两个线 程都会不断更新单个全局变量,强调内存一致性协议,以在节点之间洗牌页面,以获得独占所有权。在执行微基准的30秒 期间,我们从源收集了大约154,676个页面错误。 我们观察到故障处理时间的双峰分布;尽管我们的消息层一直需要13.6μs来检索4KB页面,但27.5%的故障在19.3μs内处 理。然而,当两个节点争用同一页面,其中一个节点必须回退重试时,故障处理平均扩展到158.8μs。这意味着减少错误 页面共享在DEX中至关重要,因为它不仅加快了故障处理,而且还减少了故障的发生。
VI. RELATED WORK 分布式共享内存(DSM)系统为跨多台计算机的分布式执行上下文(即进程和线程)提供了一致的内存视图,过去已经进 行了彻底的讨论。这些系统中的绝大多数侧重于通过自定义内存管理API利用远程内存来显式获取、锁定和释放共享内存 区域[8]–[14]。通常,此类API限制了可以在分布式上下文之间共享的虚拟内存类型(例如,只能共享堆分配的数据), 并且只保证共享内存区域的宽松内存一致性。这就要求开发人员使用针对每个系统的内存模型定制的API和语义编写应用 程序,这使得应用程序的开发和调试变得复杂。与以前的DSM工作相比,DEX的独特之处在于,分布式线程可以透明地访问 一致的内存原样,而无需重写远程内存访问和分布式同步的应用程序。此外,分布式线程可以按原样使用同步原语,而不 管其实际位置如何。 大多数DSM系统专注于在进程之间共享数据;只有少数系统考虑DSM上下文中的线程[9], [28]。通常,后者仅支持静态线 程放置,在这种情况下,远程创建的线程一旦在节点上生成,就无法重新定位。此外,它们需要应用程序重构,以将数据 放置在可共享虚拟内存区域中,以便在迁移后访问[28]。相比之下,DEX允许线程动态放置自己,从而大大提高了灵活性 和可编程性。 最近提出的分类内存系统等利用现代高速低延迟互连,为应用程序提供超出单台计算机可用内存的大量内存。特别是, Grappa [29]、LITE [22]、HotPot [24]、偏远地区【30】和乐高OS[3]通过探索具有RDMA支持互连和/或DSM概念的新 兴内存系统体系结构来激励我们在现代背景下。尽管它们显示出有希望的结果,但它们不允许开发人员利用单个计算机的 纵向扩展设计的简单性和效率;每个应用程序都必须考虑底层网络[20]、[21]、【24】的低级细节,和/或开发人员必须 从头重新设计整个应用程序[21]、[29]、[30]。例如,在Graappa[29]中,开发人员必须使用其数据寻址模式、委托操 作和构建在MPI编程模型上的通信接口完全重写应用程序。这损害了可编程性[31]–[33],使现有应用程序难以适应框 架。此外,许多分类的内存系统没有提供利用内存以外的远程系统资源(即处理器和底层存储的计算能力)的机制;因 此,必须手动分发应用程序,否则系统资源仍然未充分利用【3】。 单系统映像(SSI)系统具有灵活的进程放置和迁移功能,通过平衡节点之间的负载,有效利用群集。然而,这些系统中 的大多数都在进程级别工作;一个进程不能同时利用多个节点,而只能在给定时刻在单个节点上运行。因此,即使群集中 存在空闲节点,应用程序性能也仅限于单机性能。Kerrighed [34], [35]唯一支持线程级迁移来处理这种情况;但是, 与传统的DSM系统一样,它需要显式声明的内存区域来在分布式线程之间共享数据。这再次损害了可编程性,并为重写应 用程序带来了开销。在虚拟化[36]–[39]和检查点/重新启动系统[40]–[42]的上下文中,还对重新定位运行上下文进行 了广泛的研究。但是,它们也不能同时利用多个节点,在任何给定时刻将执行边界限制在单个计算机上。vNUMA [43]提 出了虚拟机管理程序级DSM系统,但是,目前还不清楚它如何以分布式方式处理关键的操作系统级功能,如futex。 ScaleMP [44]允许通过利用虚拟化技术从多个节点中创建软件定义的服务器。尽管ScaleMP提供了与DEX非常相似的功 能,但其内部功能尚不清楚,因为它是专有软件。
七、结论 我们引入了DEX,一个Linux内核扩展,允许应用程序将其执行边界扩展到单个计算机之外。任何应用程序都可以通过简单的函 数调用转换为跨多个节点执行。使用许多现实应用程序的评估结果证实,DEX提供了一种直观而有效的方法来利用机架规模系 统中的分散资源。
我们认为,DEX的执行重新定位能力可以在许多场景中利用,例如在数据附近重新定位计算,通过卸载加速计算,以及通过使 用具有异构功率配置文件的节点来节省能源。
1
2
3
4
5
6
7
```c
https://www.ssrg.ece.vt.edu/papers/systor20.pdf
http://www.popcornlinux.org/
integrating non-cache-coherent heterogeneous computing elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
https://www.cnblogs.com/zhengshuangxi/p/11180610.html
缓存强一致:
3、MESI协议
MESI协议是一种常用的缓存一致性协议,它通过定义一个状态机来保证缓存的一致性。在MESI协议中有四种状态,这些状态都
是针对缓存行(缓存由多个缓存行组成,缓存行的大小单位与机器的位数相关)。
(I)Invalid状态:缓存行无效状态。要么该缓存行数据已经过时,要么缓存行数据已经不在缓存中。对于无效状态,可直接
认为缓存行未加载进缓存。
(S)Shared状态:缓存行共享状态。缓存行数据与内存中对应数据保持一致,多个缓存中的相应缓存行都是共享状态。该状
态下的缓存行只允许读取,不允许写。
(E)Exclusive状态:缓存行独有状态。该缓存行中的数据与内存中对应数据保持一致,当某缓存行是独有状态,其他缓存对
应的缓存行都必须为无效状态。
(M)Modified状态:缓存行已修改状态。缓存行中的数据为脏数据,与内存中的对应数据不一致。如果一个缓存行为已修改
状态,那么其他缓存中对应缓存行都必须为无效状态。另外,如果该状态下的缓存行状态被修改为无效,那么脏段必须先回写
入内存中。
MESI协议的定律:所有M状态下的缓存行(脏数据)回写后,任意缓存级别中的缓存行的数据都与内存保持一致。另外,如果
某个缓存行处于E状态,那么在其他的缓存中就不会存在该缓存行。
MESI协议保证了缓存的强一致性,在原理上提供了完整的顺序一致性。可以说在MESI协议实现的内存模型下,缓存是绝对一致
的,但是这也会导致一些效率的问题,我们平时使用的机器往往都不会采用这种强内存模型,而是在这个基础上去使用较为弱
一些的内存模型:如允许CPU读写指令的重排序等。这些弱内存模型可以带来一定的效率提升,但是也引入了一些语义上的问
题。
1
https://www.cnblogs.com/miaolong/p/12545208.html
1
https://zhuanlan.zhihu.com/p/95435168
缓存一致性MSI状态机转化:
现在主要用于类似arm + x86芯片的异构设备中进程迁移,
二、Popcorn linux
1
2
https://github.com/ssrg-vt/popcorn-kernel
https://github.com/systems-nuts/popcorn-tutorial/blob/master/popcorn-tutorial.pdf
三、others
1
2
http://www.vldb.org/pvldb/vol11/p1604-cai.pdf
Efficient Distributed Memory Management with RDMA and Caching
四、DSM解决的问题
1、一致性
对于数据复制的情况有两种基本的协议 ,即写无效和写更新协议.对于写无效与写更新的选择 ,利用竞争算法 ( competitiv e alg orithm)可以有自适应的优 点.其结果在某些情况达到最优结果 ,最坏也不超过全用写更新方式开销的两倍.
2、false share
假共享 :就是指对于同一数据共享粒度中的不相关变量 ,当一个结点对其中一个变量进行写操作时 ,另外一个结点就不能同时对另外一个变量进行访问 .另外 ,数据的共享粒度也影响到目录的大小.共享粒度可以为 cache行、页或一个对象.
五、已有机制及待补充功能考虑
六、DSM的技术点
1
2
3
分布式共享内存的技术和实现
李 群 谢 立 孙钟秀
(南京大学计算机科学与技术系及软件新技术国家重点实验室 南京 210093)
1.复制问题 共享粒度、一致性协议、颠簸
颠簸 ( thrashing )是指当两个结点同时对数据页进行写访问时引起的页面在两个结点之间频繁的传输 ,这种情况严重影响了系统的性能.
2.存储一致性 ( coherence)模型
有效地提供内存一致性是 DSM 系统的一个重要任务 .为了能对存储器的性能进行优化 ,即利用写缓存技术、存储访问重叠技术、流水线技术等严格的一致性 ,无法开发程序的语义 ,因而出现了减弱了的一致性模型[ 2].其目的是为了解决三个问题: ①减少昂贵的消息发送次数 .②掩盖对非本地内存访问的长等待时间.③解决因为一致性单元而潜在引起的假共享问题.已有的一致性模型有: 原子一致性、顺序一致性、处理机一致性、弱一致性、释放一致性、进入一致性 .
3.系统界面
DSM 虽然能够提供给用户一个方便的编程模型 ,但由于应用程序的行为过于复杂繁多 ,很难有一种统一的方法能够有效地处理这些问题 .因此DSM系统实现时往往要在实现统一地址空间的基础上 ,提供给程序员一些额外的措施 ,以供用户依照程序的具体知识选择使用.
七、DSM 的实现常见三种方案
(1)用硬件实现 ,实际上是传统的高速缓存 ( cache )技术在可扩展体系结构中的延伸 .
(2)操作系统和程序库的实现方法 ,通过虚拟内存管理机制实现共享和一致性.
(3)编译实现 ,自动将共享访问转变为同步和一致性原语.