多处理机同步机制

基本硬件原语

  • 原子交换(Atomic Exchange)
    它的功能是将一个存储单元的值和一个寄存器的值进行交换。
  • 测试并置(test_and_set)
    先测试一个值,如果符合条件则修改其值。
  • 读取并加1(fetch_and_increment)
    返回存储单元的值并自动增加该值。

    • 指令对LL&SC
      从第二条指令的返回值可以判断该指令对的执行是否成功。
  • 比较并交换(compare and swap)
    将内存中的值与指定数据进行比较,当数值一样时将内存中的数据替换为新的值

LL&SC详解

LL(load linked或load locked)

LL 指令的功能是从内存中读取一个字,以实现接下来的 RMW(Read-Modify-Write)1 操作;
SC(store conditional)
SC 指令的功能是向内存中写入一个字,以完成前面的 RMW 操作。
LL/SC 指令的独特之处在于,它们不是一个简单的内存读取/写入的函数,当使用 LL 指令从内存中读取一个字之后,比如 LL a, off(b),处理器会记住 LL 指令的这次操作(会在 CPU 的寄存器中设置一个不可见的 bit 位),同时 LL 指令读取的地址 off(b) 也会保存在处理器的寄存器中。接下来的 SC 指令,比如 SC X, off(b),会检查上次 LL 指令执行后的 RMW 操作是否是原子操作(即不存在其它对这个地址的操作),如果是原子操作,则X的值将会被更新至内存中,同时X的值也会变为1,表示操作成功;反之,如果 RMW 的操作不是原子操作(即存在其它对这个地址的访问冲突),则 t 的值不会被更新至内存中,且 t 的值也会变为0,表示操作失败。

利用LL/SC指令对我们可以构造其他原语**

原子交换

 try:  OR     R3,R4,R0     ;R4送交换值给R3
        LL     R2,0(R1)     ;load linked 取R1指向的值给R2
        SC     R3,0(R1)     ;store conditional 向R3存入(R1)值,若(R1)改变,则存失败
        BEQZ   R3,try       ;存失败转移
        MOV    R4,R2        ;将取的值送往R4
        最后完成了R4和(R1)指向的值原子交换

读取并加1

try:           LL      R2,0(R1)     ;load linked
        DADDUI  R2,R2,#1    ;增加
        SC      R2,0(R1)     ;store conditional(检测R1指向的值是否改变)
        BEQZ    R2,try       ;存失败转移

利用LL/SC指令和一致性实现锁

lockit:   LL      R2,0(R1)     ;load-linked (R1)中保存锁值
           BNEZ    R2,lockit    ;锁无效  锁值为1被占用,此处实现了spin locks
           DADDUI  R2, R0,#1   ;加锁值
           SC      R2,0(R1)     ;存
           BEQZ    R2,lockit    ;如果存失败则转移,此处实现了锁竞争

如何利用Cache一致性?
我们将锁缓冲进入Cache,并通过Cache一致性保持锁一致性。这样即可以充分利用Cache的速度减少访存时间又可以利用程序局部性原理(最近使用的锁不久内还会使用)。

这样的锁在环绕过程中仅对本地Cache中锁的备份进行读,直到返回0确认锁可用。一旦某个处理器写入0,释放该锁,所有处理器对应的Cache备份块均被作废,需要重新更新锁备份。其中一个处理器会先加锁值,其他Cache处理器发现已被加锁必须再次不停进行环绕测试。

步骤处理器P0处理器P1处理器P2锁状态总线/目录操作
1占用锁环绕锁测试lock=0环绕锁测试lock=0Shared
2释放锁收到作废命令收到作废命令ExclusiveP0发锁变量作废
3 Cache失效Cache失效Shared锁从P0写会,总线处理P2Cache失效
4 未抢到lock=0SharedP2 Cache失效处理
5 lock = 0执行交换,Cache失效SharedP1 Cache失效处理
6 执行交换,Cache失效交换完毕。lock = 0Exclusive总线处理P2Cache失效,发作废消息
7 交换完毕。lock = 1处理Shared总线处理P2Cache失效,写回
8 环绕锁测试lock=0

性能问题

假设总线上有X个相同的处理器同时准备对同一变量加锁,时间0时锁已释放并且所有处理器都在旋转等待,求着这些请求完成时间多长。

解:当进行到 i 个处理器竞争锁的时候他们分别完成下列操作。

访问该锁的 i 个LL指令
试图释放该锁的 i 个 SC指令
1 个释放锁的存指令

总线事务共有

$$ \sum_{i=1}^{n}(2 i+1)=n(n+1)+n=n^{2}+2 n $$

栅栏

并行循环程序的另一个常用同步操作是栅栏同步,栅栏即为强制所有到达该栅栏的进程等待,直到所有的进程到达栅栏,然后释放所有的进程,从而形成同步。

栅栏典型模型
两个Spin locks,一个用来记录到达栅栏的进程数,另一个用来封锁进程直到最后一个进程进入栅栏。

Lock(counterlock);              /*确保增量更新的原子性*/
if(count=0)  release=0; /*第一个进程则重置release*/
count++;                  /*到达进程记数*/
unlock(counterlock);            /*释放锁*/
if(count==total){                /*进程全部到达*/
      count=0;                  /*重置计数器*/
      release=1;                /*释放进程*/
 }
else {                            /*还有进程未到达*/
      spin(release==1);           /*等待别的进程到达*/
     }

在实际中进程经常反复使用同一个栅栏,这就带来了一个问题。如果一个进程B速度较快,在它第二次到达栅栏时,第一次的某个进程A还挂在栅栏上未能离开(例如该进程还在旋转操作中等待离开,B进程发现count = 0,将release置位0,A进程则继续旋转检测)。那么该栅栏的进程就进入了无限的等待状态,因为进程总是达不到total(A进程未能离开导致第二轮的计数少了1)。

这个问题可以采用sense_reversing栅栏解决,每个进程添加一个私有变量local_sense来将较辨认该进程的上一轮是否离开。

local_sense != local_sense;            /*local-sense取反*/
lock(counterlock);                    /*确保更新的原子性*/
count++;                              /*计算到达进程数*/
unlock(counterlock);                  /*解锁*/
if(count==total) {                     /*进程全部到达*/
       count=0;                       /*重置计数器*/
       release=local_sense;           /*释放进程*/
 }
else {                                 /*还有进程未到达*/
       spin(release==local_sense);     /*等待信号*/
     } 

例题:假设总线上有X个相同的处理器同时执行一个sense_reversing栅栏,计算10个处理器全部到达栅栏并被释放的总线事务数。
解:当进行到 i 个处理器分别完成下列操作。

事件数量对应源代码说明
LLilock(counterlock)所有处理器抢锁
SCilock(counterlock)所有处理器抢锁
LD1count++;一个成功
LLi-1lock(counterlock)不成功的处理器再次抢锁
SD1count++;获得专有访问的产生的失效
SD1unlock(counterlock)获得锁产生的失效
LD2spin(release==local)读释放:初次和最后写产生的失效

注:最后一个到达的进程少一个事务

共有总线事务数

$$ \left[\sum_{i=1}^{n}(3 i+4)\right]-1=\left(3 n^{2}+11 n\right) / 2-1 $$

同步操作最严重的问题的是进程的串行性。当出现竞争时,就会出现串行性问题。它极大地增加了同步操作的时间。比如,在无竞争的条件下,10个处理器加解锁的同步操作仅需20个总线事务。总线的使用是这个问题关键所在。在基于目录的Cache一致性机器中,串行性问题也同样严重.

大规模机器同步的改进

软件实现

  • 人为增加加锁失败后的指数延迟
                DADDUI   R3,R0, #1      ;R3=初始延迟值;
lockit:  LL       R2,0(R1)        ;load linked
                BNEZ     R2,lockit       ;无效
                DADDUI   R2,R2,#1      ;取到加锁值
                SC       R2,0(R1)        ;store conditional
                BNEZ     R2,gotit        ;存成功转移
                DSLL     R3,R3,#1     ;将延迟时间加倍(左移1位)
                PAUSE    R3               ;延迟R3中时间值      
               J        lockit
gotit:   使用加锁保护的数据
  • 组合树栅栏
    通过组合树(Combing tree)技术减少读取release的冲突,即将多个请求放在组合树(预定义的K叉树)中。树中每个节点组合K个进程,提供个单独的计数器和锁,因而在每个节点有K个进程进行竞争。当第K个进程都到达树中对应节点时则进入父节点,然后递增父节点的计数器,当父节点计数到达K时,置 release标志。每个节点的计数器在最后一个进程到达时被初始化。

硬件实现

  • 排队锁
    排队锁的工作过程如下:在第一次取锁变量失效时,失效被送入同步控制器。同步控制器可集成在存储控制器中(基于总线的系统)或目录控制器中。如果锁空闲,将其交给该处理器;如果锁忙,控制器产生一个节点请求记录(比如可以是向量中的某一位)并将锁忙的标志返回给处理器,然后该处理器进入旋转等待。当该锁被释放时,控制器从等待的进程排队中选出一个使用该锁。这可以通过更新所选进程 Cache中的锁变量或者作废锁的备份来完成。(排队锁也可软件实现)

例题:求N个处理器使用排队锁的情况下所需总线事务数

解:对n个处理器,每个处理器都初始加锁产生1个总线事务,其中1个成功获得锁并在使用后释放锁,第1个处理器将有n+1个总线事务。每一个后续的处理器需要2个总线事务:1个获得锁,另1个释放锁。因此总线事务的总数为(n+1)+2(n-1)=3n-1

注:这里的总线事务总数随处理器数量成线性增长,而不是前面旋转锁那样成二次方增长。

  • 使用fetch_and_increment
local_sense != local_sense /*local_sense变反*/
    fetch_and_increment(count); /*原子性更新*/
    if(count==total){               /*进程全部到达*/
      count=0;                          /*初始化计数器*/
        release=local_sense;          /*释放进程*/
    }
    else  {                               /*还有进程未到达*/
      spin(releaze==local_sense); /*等待信号*/
}

同时多线程

同时多线程技术是一种在多流出、动态调度处理器上开发线程级并行和指令级并行的改进的多线程技术
同时多线程使多个线程以重叠的方式共享单个处理器的功能单元

超标量处理器的四种流出槽使用方法


注:粗粒度指仅仅在发生阻塞时切换线程,细粒度指交替执行线程

同时多线程(SMT)开发的基础是使用动态调度技术的处理器已经具有了开发线程级并行所需的硬件设置。具体来说,动态调度超标量处理器有大量的虚拟寄存器组,可以用来保存每个独立线程的寄存器状态(假设每个线程都有一个独立的重命名表)。
由于寄存器重命名机制提供了唯一的寄存器标识符,多个线程的指令可以在数据路径上混合执行,而不会导致各线程间源操作数和目的操作数的混乱。这表明多线程技术可以通过在一个乱序执行的处理器上为每个线程设置重命名表、保留各自的PC值、提供多个线程的指令结果提交的能力来实现。

相比于SMT,细粒度并行需要

  • 保存多个上下文所需的庞大的寄存器文件
  • 必须保持每个时钟周期的低开销,特别是在关键步骤上,如指令流出和指令完成。前者有更多的候选指令需要考虑,后者要选择提交哪些指令的结果
  • 需要保证由于并发执行多个线程带来的cache冲突不会导致显著的性能下降。

并行处理器的性能评测

  1. 存储受限评测法
    保持每个处理器使用的存储器资源恒定
  2. 时间受限评测法
    在理想的加速比下,保持总运行时间恒定

运用这两种方法,研究处理器数量和问题规模变化的情况下系统的性能和加速比的相应变化

多处理器实例

SUN公司推出的T1处理器
SGI Origin 2000


  1. 必须要先读操作的一个原因是,系统架构往往只允许字(word)级的读写,必须先读出那些不做修改的比特,保持不变再写回。
Last modification:April 23rd, 2020 at 08:29 pm
如果觉得我的文章对你有用,请随意赞赏