Shared_Memory_consistency_models_A_Tutorial 中文意译版

2009-12-20 13:26| 发布者: admin| 查看: 35| 评论: 0|原作者: 潇潇雨

2008-7-16 WRL-TR-95.7-Shared_Memory_consistency_models_A_Tutorial.pdf通过直觉扩展而来的sequential consistency模型在很大程度上限制了许多硬件和编译器的优化手段,这些手段在单cpu系统上本是可以使用的. 为了缓和这些问题, 许多当前的多processor结构支持许多relaxed consistency model.不幸的是这些模型各自有自己的表述手段,并难以理解.本文原作者试图通过一致的术语去抽象这些模型.原文着重于那些基于硬件的shared memory系统所提出的内存模型.文章的最后从程序员的视角出发,program behavior的术语对这些模型进行了一些讨论.1 introduction share memory 系统得以广泛的应用,得益于单一的地址空间使得从单processor系统到多processor系统的过渡非常自然.想要写出正确高效的并行程序,程序员必须清楚多processor发起的内存读写到底是个什么样的行为. 试举一例:
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://docs.google.com/File?id=dcbsxfpf_257z574z3xs_b');}" onmousewheel="return imgzoom(this);" alt="" />

P1创建一个任务, Task->Data, 然后把任务放入一个队列,最后把队头赋值到Head, 从而使得P2...Pn通过Head(在临界区内,故无竞争)获得自己的任务. 在这个例子里, 程序员对内存系统的期望是什么? 最重要的一点, Pi获取的task->Data应该是P1写入的值不幸,许多现存的许多share memory系统都不能满足程序员的期望, 有可能读到的还是data的老的值.共享内存系统的memroy consistency model提供了一个描述内存系统语义的正式标准,从而消除程序员的过高期望.consistencymodel 给read操作又可能的返回值加上了一些限制, 最直观的要求就是read操作应该返回最后一次写入同一地址的值. 在单cpu系统中, '最后'的含义完全是由program order来决定的.但是在多cpu系统这中不是这样:上面例子中,对Data域的读写操作不是完全由program order决定的.(原因后面章节会提到,但是有一点: 我们不能假定程序以任何时序运行,也不能假定多cpu系统有某些想象中的限制). 然而,一个单处理器模型的直观扩展在多处理器环境下也是可以应用的,这个模型就是sequential consistency,简称SC. 用非正是的语言来描述SC模型就是:SC保证所有的内存操作都是原子性的(注:不是通常说的cpu原子操作),即从整个系统的角度看在同一时刻只进行一个内存操作,使得单一处理器执行的内存操作顺序符合program order.SC的含义在下面章节将会具体讨论,最重要的是SC足以保证上面的例子中的程序得以正确运行,通过后面的章节我们将看到SC到底是一个什么样的限制.本文原作者试图通过一致的术语去抽象这些模型.原文着重于那些为了硬件的shared memory系统所提出的内存模型,这些模型大多强调什么样优化可以在这种模型下得以实施.文章的最后也从程序员的视角出发,以program behavior的术语对这些模型进行了一些讨论.2 Memory Consistency Models - Who Should Care?内存一致性模型会影响到可编程性,因为程序员需要使用内存一致性模型去推测程序的正确性, 也影响到性能,因为内存一致性模型决定了何种优化可以在硬件和编译器上实现,最后还会影响程序的可移植性. 内存一致性模型影响到程序员和系统之间的一切接口, 在机器码层面,内存一致性模型影响硬件的设计者和写机器码的程序员;高级语言层面,内存一致性模型影响编译器的设计,高级语言的使用.总之,内存一致性模型从程序员的角度影响了些并行程序的设计,从系统设计着的角度来看,内存一致性模型实际上影响一个并行系统的各个方面: 处理器, 内存系统,interconnection network(互联cpu的网络),编译器,编程语言.3 Memory Semantics in Uniprocessor Systems在单处理器系统中,只要能够保证data dependency 和control dependency, 处理器和编译器便可以乱序执行不同位置的内存访问操作. 这样, 编译器的优化手段:egister allocation, code motion, loop transformations ,以及处理器的优化手段:pipelining,multiple issue, write buffer bypassing and forwarding, lockup-free caches便可以得以实施. 这些手段都会导致内存操作的overlappi和reorder. 总之,在单处理器系统上,SC模型得以保持,并且容许大量采用各种有效的设计.4 Understanding Sequential ConsistencySC 定义 by LamportDefinition: [A multiprocessor system is sequentially consistent if] the result of any execution isthe same as if the operations of all the processors were executed in some sequential order, and theoperations of each individual processor appear in this sequence in the order specified by its program.这个个定义有两个方面的含义:1. 保持单个cpu的内存操作以programe order得以执行2. 确保发自所有理器的内存操作,在所有的处理器(系统)看来,是以一个唯一的顺序执行的第二条规则使得一个内存操作看起来像是原子操作,是立即完成的. (主义这里的原子性不是指像r-modify-w这样的原子操作,而是cpu发的内存操作执行的原子性, 是内存的r/w从开始执行到执行结束的原子性)注:整个定义在于保证'顺序',无任何其他保证SC的系统模型就如同下图所示,每个处理器都以program order发起内存操作, 到内存的唯一通道保证所有内存操作的全局序列化
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://docs.google.com/File?id=dcbsxfpf_258dc98rqdg_b');}" onmousewheel="return imgzoom(this);" alt="" />

下图提供了两个例子来说明SC的内存语义:图(4)a演示了保持单处理器访存以program order执行的重要性.这是Dekker的临界区算法,这个算法依赖于在P1(P2)上对flag1的写操作一定会在对flag2的读操作之前完成. 即W->R的顺序得以保持.
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://pk.linuxpk.com/image/zoom.gif');}" onmousewheel="return imgzoom(this);" alt="" />

screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://docs.google.com/File?id=dcbsxfpf_259hfqvh6g9_b');}" onmousewheel="return imgzoom(this);" alt="" />

图(4)b演示了内存的原子操作的重要意义. 看一下P3, 如果B等于1, 根据P2, 那么A也必然等于1, 所以P3上应该看到register1等于1. 但是这个里面的隐含条件是: 对A=1的赋值操作,在系统级别上是原子执行的. 也就是说A=1应该立即,同时的传播到P2,和P3上. 在后面的讨论中多出引用这两个例子,留待后面详解.5 Implementing Sequential Consistency本章节讨论如何在多处理器环境下实现SC模型, 通过讨论SC模型和硬件优化的关系, 我们将看到在多处理器系统中只保持对同一地址的操作顺序是不够的.讨论分成带cache 和不带cache 两个部分. 先讨论不带cache的.5.1 Architectures Without Caches原文作者选取了3个比较经典的硬件优化手段来说明硬件优化和SC的关系.作者同时指出其他的各种优化手段都会导致相类似的结果.下图就是典型的三个例子:
screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://docs.google.com/File?id=dcbsxfpf_261fkbngwfs_b');}" onmousewheel="return imgzoom(this);" alt="" />

screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onmouseover="if(this.width>screen.width*0.7) {this.resized=true; this.width=screen.width*0.7; this.style.cursor='hand'; this.alt='Click here to open new window\nCTRL Mouse wheel to zoom in/out';}" onclick="if(!this.resized) {return true;} else {window.open('http://docs.google.com/File?id=dcbsxfpf_262z9k7bcfm_b');}" onmousewheel="return imgzoom(this);" alt="" />

5.1.1 Write buffers with Bypassing Capability这个例子说明了保证W->R顺序的重要性. 这个硬件优化容许cpu在写入write buffer后无须等待write完成,条件是read的地址不匹配write buffer中任一个地址就可以.这个条件在单处理器系统下可以有效的隐藏write的延迟,但在多处理器环境就会带来问题.见图5(a),以图示顺序执行的操作就会违背SC的要求, SC要保证对不同位置的读写也要保序. 这个优化在单处理器环境是不违背datadependency的,单在多处理器环境下,这种reorder违背了SC的要求. 5.1.2 Overlapping Write Operations图5(b)给出了另一种典型的硬件优化方式, 通过一个处理器互联网络把两个处理器链接到2个内存模块上,这样就容许内存模块同时处理两个内存访问操作.这种情况下即使P1按照program order发起内存操作,但是由于处理器可以在write DATA之后,但是DATA还没有进入内存模块时,发起对另一个内存模块的写操作,这样对HEAD的写操作就有可能先于DATA到达另一个内存模块, 导致P2看到HEAD的新值,但是却看到老的DATA.这种违背SC的reorder可以通过一种手段来修正:处理器在发起写操作的后续操作前,等待内存模块给一个ack信号,这个手段对于在存在general interconnection network的系统保持W->R,W->W的操作的program order都有效. 注意这个 write ack是内存模块发送给发起写操作的处理器的.

收藏分享邀请

		自动登录	找回密码
密码			注册

Shared_Memory_consistency_models_A_Tutorial 中文意译版

最新评论

相关分类