Grappa是一个基于远程直接数据存取技术RDMA[Remote Direct Memory Access]的分布式共享内存系统DSM[Distributed Shared Memory]。由University of Washington团队开发，描述整体系统的paper, Latency-Tolerant Software Distributed Shared Memory获得ATC 2015 Best Paper Award，虽然现在已经停止维护，但是整个系统还是值得学习。

Global Memory

Grappa最重要的功能就是Global Memory。在Grappa中，一个locale就是一个server，一个locale可以有多个process来处理任务，称为core。所有core，尽管在不同的locale都可以访问一个统一的Global Memory，通过***GlobalAddress***来生成，Grappa提供三种Global address，**2D Addresses**，**Linear Addresses**，**Symmetric Addresses**。在Grappa提供的application中，使用最广泛的是Symmetric address，这也是为什么Grappa可以提供比较高的读的速度。

2D Addresses

通过make_gobal()函数来对一个变量分配global address，此函数会返回地址的指针和这个地址所在的core。

long count = 0;
GlobalAddress<long> g_count = make_global( &count );

Linear Addresses

相对于2D address只在一个core上分配地址，linear address是每个core都会贡献一块内存（以及一个地址起始指针）来组成一个global heap，每个core贡献的内存大小相同，通过global_heap_fraction来控制。内存分配机制采用轮询制(round-robin)，通过global_alloc来完成。

auto array = global_alloc<long>(48);
for (auto i=0; i<48; i++) {
  std::cout << "[" << i << ": core " << (array+i).core() << "] ";
}
std::cout << "\n";

上述代码为array开辟了一个大小为48的linear global address，分布在所有的core上。

Symmetric Addresses

此种address可以提供最快的数据访问速度但是会占用更多的内存空间，因为所有的数据结构在所有的core上会有拥有一个备份，比如一个core有一个tree的数据结构，那么其余所有的core也有都会有，这样每一个core就都维护了一个global heap。使用的时候，要在分配symmetric address的数据结构后面追加宏定义GRAPPA_BLOCK_ALIGNED。通过symmetric_global_alloc分配，但是这里还没有进行初始化，需要使用init()初始化后才可以使用。

GlobalAddress<Data> d = symmetric_global_alloc< Data >();
on_all_cores([d]{
	// use `->` overload to get pointer to local copy to call the method on
   d->init(1024);
});

Delegate Operations

Delegate是Grappa的一个非常重要的功能，它解决了系统的并发控制和同步问题。其基本思想是，在每个server的core上，不同的数据结构都会拥有一个delegate，当其他的特别是远程的core想访问本地core的数据时，delegate会发一个请求到需要访问的core上，然后接受返回结果。这样每个core都会有一个来自不同core的request的队列，并保证了顺序一致性[sequential consistent]。

最基本的delegate操作是call()，

T call(Core dest, []() -> T {  (on 'dest')  })
U call(GlobalAddress<T> gp, [](T *p) -> U { (on gp.core(), p = gp.pointer()) })

参数中的lambda function指定执行在core dest上，

Tasking

Bound Task

一般情况下，task会和创造这个task的core绑定在一起。也就是说，这个任务会在这个core的本地任务队列等待，直到在这个core上的一个worker空闲并且开始执行这个task。

Unbound Task

Grappa也会产生unbound的task，也就说不会局限某一个core来执行，他们会被放进一个全局任务队列，任何一个core中的可用worker都可以访问并执行他们。全局执行的时候Grappa会考虑load-balance。

CompletionEvent

在Grappa中，产生任务[spawn]的方式是异步的[asynchronous]，也就说不用等待上一个任务执行完毕再产生并运行下一个任务。任务会一直产生然后放入等待执行的队列中，但是还是需要保证一些操作要在某些任务完成后执行。Grappa提供了一些同步机制，比如CompletionEvent。基本思路很简单，在主程序生成任务后，会传给CompletionEvent一个指针，将生成的任务在CompletionEvent进行登记，然后主程序进入等待状态。如果一个任务完成，他就会发送一个completion的信息。直到所有任务都发送了这个信息，CompletionEvent收集到所有completion信息再唤醒主程序，进行下一步操作。

/// Synchronization primitive useful for waking a worker after a number of other things complete.
/// All waiting tasks will be woken as soon as the count goes to 0. 
CompletionEvent(int64_t count = 0): count(count) {}

FlatCombiner

Grappa采用了一个Flat Combining的机制来解决同步和并发操作问题。Flat Combining这个概念最先于2010年发表的文章Flat Combining and the Synchronization-Parallelism Tradeoff中提出，后来Grappa项目引入了此设计，并且做了修改使之适合Grappa。

Flat Combining的基本思想是如果一个线程获得锁后，并不是执行操作然后释放锁；而是执行所有在跟它竞争的线程的操作。文章中说，这个思路是改变传统的竞争关系[contention]为合作关系[cooperation]。

在Grappa，Flat Combining被稍作修改[具体实现在类FlatCombiner中]，每一个全局的数据结构实例都会在每个core上拥有一个proxy，这个proxy负责管理处理各种请求。

Misc

  1. Grappa原论文中指出，使用GASNet来进行通信，现在根据代码和作者在Github上面的回复可以确定GASNet已经不再被支持，取而代之的是MPI[Message Passing Interface]。

本文部分内容来源于Grappa项目的Github