面向多核并行程序的确定性懒惰释放一致性实现方法

摘要

本发明公开了一种面向多核并行程序的确定性懒惰释放一致性实现方法，步骤包括：在多核并行程序初始化时为各个线程分配独立的地址空间，进程的虚地址空间划分成页面统一管理，将多核并行程序进程的每个线程通过页表项映射至指定页面的一个版本，为多核并行程序的每个线程设置初始向量版本号并维护一个向量时钟，利用同步语句划分为执行切片；在多核并行程序运行后，如果在执行切片中线程第一次修改页面或者线程同步时导致版本合并时，针对线程访问的页面生成新的向量版本；在执行切片开始时，为线程选择符合DLRC内存一致性的页面向量版本。本发明能够解决采用内存修改传播算法在空间上和时间上的开销问题，缩小内存空间使用，减少内存读写次数。

说明书

技术领域

本发明涉及多核体系结构的确定性并行技术，具体涉及一种面向多核并行程序的确定 性懒惰释放一致性实现方法。

背景技术

确定性懒惰释放一致性即DLRC(DeterministicLazy-ReleaseConsistency)内存一致性。 多线程程序符合DLRC内存一致性是指：任何线程T1对于内存的修改可以被其他线程T2 看到当且仅当这个内存修改依据happens-before时序关系发生在T2当前执行的指令之前。 其中，Happens-before时序关系是并行程序中的一种事件时序关系，A→B表示事件A发生 在事件B之前。在并行程序执行中，任何两条指令A和B如果要有A→B，必须满足以下 三个条件中的任何一个：(1)A和B是发生在同一个线程中，且A在B之前执行。(2)A 和B是两个不同线程中的同步语句(例如unlock和lock)，它们执行了关于同一个共享对象 的同步操作，且B的开始必须发生在A的结束之后。(3)存在一个指令序列C1，C2…Cn， 使得A→C1,C1C2,…,Cn→B。Happens-before关系是数学上的一种偏序关系(partial order)。集合论中，如果一个集合中的任意两个元素a和b都能比较大小，那么这个集合中 的元素就具有全序关系(Totallyordered)，否则，集合中的元素就具有偏序关系(partial order)，也称半序关系。对于具有偏序关系的集合A，如果集合中的元素a和b，有a>b,则 a是b的上界(Upperbound)；如果a是b的上界，且对于任意b的上界x都有a<＝x，则 a是b的上确界(Leastupperbound)；如果a<b,则a是b的下界(Lowerbound)；如果a是b 的下界，且对于任意b的下界x都有a>＝x，则a是b的下确界(Greatestlowerbound)；a 是集合A中的元素，集合A中不存在其他元素b，有a<b，则a是集合A的极大元(Maximal element)；a是集合A中的元素，若集合A中不存在其他元素b，有b<a，则a是集合A 的极小元(Minimalelement)。

卢凯等人的《EfficientDeterministicMultithreadingWithoutGlobalBarriers》(PPoPP2014) 公开的RFDet方法在软件层面上实现了DLRC内存一致性模型，该方法首先使用页面保护 技术隔离线程的内存空间，通过copy-on-write技术记录线程对于本地内存的修改，当发生 线程之间的同步时，利用内存修改传播技术使本地内存修改严重线程同步所形成的 happens-before关系边从一个线程传递到另一个线程，从而实现内存修改可见性的延迟程度 符合DLRC内存一致性模型的定义。DLRC内存一致性模型的时空开销主要来自于内存修 改传播算法，即在线程同步引起happens-before时序关系时执行内存修改传播，使一个线程 的内存修改沿着happens-before边传播到另一个线程。这个算法需要为共享变量在每个线程 中创建副本，需要专门的缓冲区来存放未传播的内存修改，并且导致了大量的内存读写， 造成较大的内存空间开销和一定的性能开销。理论上讲，DLRC内存一致性模型的内存空间 开销为S*N+M。其中S为程序的共享内存大小，N为线程数量，而M为运行时系统用于存 放未内存修改所占用的空间。而且，该方法的内存页面版本管理采用的是整数，修改一次 版本号就增加1，版本之间是全序关系。在并行程序中，事件之间的关系并不是全序关系而 是半序关系，这是因为完全并行的事件之间是不存在时序关系的，因此全序关系的版本号 在反映并行程序中事件的半序关系时会出现偏颇，导致内存修改传播技术的访存数量增加。

发明内容

本发明要解决的技术问题：针对现有技术的上述问题，提供一种能够解决采用内存修 改传播算法在空间上和时间上的开销问题，缩小内存空间使用，减少内存读写次数的面向 多核并行程序的确定性懒惰释放一致性实现方法。

为了解决上述技术问题，本发明采用的技术方案为：

一种面向多核并行程序的确定性懒惰释放一致性实现方法，步骤包括：

1)在多核并行程序初始化时为多核并行程序的各个线程分配独立的地址空间以隔离线 程的地址空间，将多核并行程序进程的虚地址空间划分成页面统一管理，每一个页面都具 有一个初始版本，且将多核并行程序进程的每个线程通过页表项映射至指定页面的一个版 本，使得每个线程在任一时刻只能看到指定页面的一个版本；同时，为多核并行程序的每 个线程设置初始向量版本号并维护一个向量时钟，利用多核并行程序的同步语句将多核并 行程序的执行流划分为执行切片，使得每一个执行切片都具有唯一的向量时钟值；

2)在多核并行程序运行后，如果在执行切片中线程第一次修改页面或者线程同步时导 致版本合并时，针对线程访问的页面生成新的向量版本；在执行切片开始时，为线程选择 符合DLRC内存一致性的页面向量版本。

优选地，所述步骤2)中针对线程访问的页面生成新的向量版本的详细步骤包括：

S1)首先判断触发针对线程访问的页面生成新版本的条件，如果条件为在执行切片中 线程第一次修改页面，则通过copy-on-write技术针对线程访问的页面生成新版本，基于该 执行切片的向量时钟生成新版本的向量版本号，并修改页表将该页面对应的虚地址指向新 版本的向量版本号，退出；如果条件为在线程同步时导致版本合并，则跳转执行步骤S2)；

S2)首先找到需要同步的各个线程访问页面当前版本的共同前驱版本，分别计算各个 线程访问页面当前版本和共同前驱版本之间的差别，将这些差别分别合并到共同前驱版本 生成新版本，基于该执行切片的向量时钟生成新版本的向量版本号，并修改页表将该页面 对应的虚地址指向新版本的向量版本号。

优选地，所述步骤2)中为线程选择符合DLRC内存一致性的页面向量版本时，针对当 前执行切片S，从访问的页面P的所有版本PV1～PVn中选择S当前向量时钟的下确界版 本PVk，所述下确界版本PVk满足以下条件：(1)执行切片S的向量时钟大于或等于PVk 的版本号；(2)不存在向量时钟大于下确界版本PVk的向量时钟的版本PVx。

优选地，所述步骤1)中的向量时钟的值用形如<x1,x2,x3,…,xn>的向量形式描述，所述 向量时钟中向量元素的个数为多核并行程序的线程数量，且所述向量时钟中第n个线程Tn 对应于向量时钟的第n个元素xn。

本发明面向多核并行程序的确定性懒惰释放一致性实现方法具有下述优点：本发明为 每个线程分配独立的地址空间，隔离线程的地址空间，为每个线程维护一个向量时钟，利 用同步语句将程序的执行流执行切片，每个执行切片拥有唯一的一个向量时钟值，而且与 现有技术相比，本发明在多核并行程序初始化时为多核并行程序的各个线程分配独立的地 址空间以隔离线程的地址空间，将多核并行程序进程的虚地址空间划分成页面统一管理， 每一个页面都具有一个初始版本，在多核并行程序运行后，如果在执行切片中线程第一次 修改页面或者线程同步时导致版本合并时，针对线程访问的页面生成新的向量版本；在执 行切片开始时，为线程选择符合DLRC内存一致性的页面向量版本，在页面统一管理的基 础上，实现了向量版本技术在线程同步时对于内存修改的处理，由于本发明采用页面的向 量版本技术来替代内存修改传播算法，能够解决采用内存修改传播算法在空间上和时间上 的开销问题，缩小内存空间使用，减少内存读写次数。

附图说明

图1为本发明实施例方法的基本流程示意图。

图2为本发明实施例中的内存空间布局示意图。

图3为本发明实施例中的执行切片示意图。

图4为现有技术普通的版本的全序关系示意图。

图5为本发明实施例中向量版本的偏序关系示意图。

具体实施方式

如图1所示，本实施例面向多核并行程序的确定性懒惰释放一致性实现方法的步骤包 括：

1)在多核并行程序初始化时为多核并行程序的各个线程分配独立的地址空间以隔离线 程的地址空间，将多核并行程序进程的虚地址空间划分成页面统一管理，每一个页面都具 有一个初始版本，且将多核并行程序进程的每个线程通过页表项映射至指定页面的一个版 本，使得每个线程在任一时刻只能看到指定页面的一个版本；同时，为多核并行程序的每 个线程设置初始向量版本号并维护一个向量时钟，利用多核并行程序的同步语句将多核并 行程序的执行流划分为执行切片，使得每一个执行切片都具有唯一的向量时钟值；

2)在多核并行程序运行后，如果在执行切片中线程第一次修改页面或者线程同步时导 致版本合并时，针对线程访问的页面生成新的向量版本；在执行切片开始时，为线程选择 符合DLRC内存一致性的页面向量版本。

本实施例中，将多核并行程序进程的虚地址空间划分成页面统一管理。如图2所示， 每个页面P维护多个版本{PV1,PV2...PVn}，同一个页面的不同版本之间具有偏序关系 (Partialorder)，采用向量版本描述其时序关系。所有页面的版本由运行时系统统一管理， 每个线程在任一时刻只能看到一个页面的一个版本。本实施例通过硬件的页面映射机制为 每个线程选择可以看到的页面版本，从而确保其所看到的内存修改延迟符合DLRC内存一 致性。例如，如果在某一时刻，线程T1根据DLRC内存一致性模型只能看到页面P2的一 个版本P2V<1,0>，那么本实施例中就修改线程T1的页表项，使其与页面P1对应的虚地址 映射到P2V<1,0>所对应的物理内存上。对于页面P的多个版本{PV1,PV2...PVn}来说，线程 T能看到哪个版本由当前线程T的向量时钟和这些版本的向量时钟所决定。要符合DLRC 内存一致性模型，必须保证页面版本PVk的向量时钟是线程T当前向量时钟的下确界 (GreatestLowerbound)。

本实施例中，步骤1)中利用多核并行程序的同步语句将多核并行程序的执行流执行切 片，使得每一个执行切片都具有唯一的向量时钟值，其中执行切片是指线程执行中的一段 指令序列，这段指令执行序列以一个同步语句开始，并以另一个同步语句结束。如图3所 示，执行切片是一个动态的指令执行序列，在程序执行时以同步语句为边界自动划分，例 如在线程代码执行方向上，执行切片n和执行切片n+1为相邻的两个执行切片，执行切片n 和执行切片n+1之间即为一个同步语句，每个执行切片拥有唯一的向量时钟值与之对应。

本实施例中，步骤2)中针对线程访问的页面生成新的向量版本的详细步骤包括：

S1)首先判断触发针对线程访问的页面生成新版本的条件，如果条件为在执行切片中 线程第一次修改页面，则通过copy-on-write(写时复制，下同)技术针对线程访问的页面生 成新版本，基于该执行切片的向量时钟生成新版本的向量版本号，并修改页表将该页面对 应的虚地址指向新版本的向量版本号，退出；如果条件为在线程同步时导致版本合并，则 跳转执行步骤S2)；

S2)首先找到需要同步的各个线程访问页面当前版本的共同前驱版本，分别计算各个 线程访问页面当前版本和共同前驱版本之间的差别，将这些差别分别合并到共同前驱版本 生成新版本，基于该执行切片的向量时钟生成新版本的向量版本号，并修改页表将该页面 对应的虚地址指向新版本的向量版本号。

如图4所示，目前普通的版本技术为全序关系，版本P1～P4的版本号是整数，修改一 次版本号就增加1。但是在并行程序中，事件之间的关系并不是全序关系而是偏序关系 (partialorder)，这是因为完全并行的事件之间是不能判断时序关系的。因此全序关系的版 本号在反映并行程序中事件的偏序关系时会出现偏颇。本实施例中采用向量版本技术管理 内存页面，向量版本之间就能够形成偏序关系，恰好用于描述程序执行中生成版本的事件 之间的偏序关系。如图5所示，每一个方块表示一个页面版本，箭头方向表示版本的增长 方向，也表示了版本之间的偏序关系。其中箭头1、2、4表示由于线程修改本地内存导致 的版本增长，而箭头3、5表示由于线程同步合并内存修改导致的版本增长。

在本实施例中，每个页面P都有一个初始版本。页面新版本的生成有两种情况，一是 在执行切片中线程第一次修改页面时，这时通过copy-on-write技术生成新的版本；二是在 线程同步时导致版本合并，由多个老版本合并成一个新的版本。以图5为例，本实施例中 新版本的生成过程具体如下：在初始状态下页面P的版本列表中只有一个版本，即PV<0,0>。 线程T1和线程T2初始的向量时钟分别为<0,0>和<0,0>。此时线程T1和线程T2开始并行 执行，它们访问页面P的同一个版本PV<0,0>。当线程T1进入第一个执行切片时，它的向 量时钟为<1,0>，当线程T1第一次写页面P时，它会创建页面P的一个新版本P<1,0>，表 示该版本是在向量时间为<1,0>时被创建的，同时它会修改自己的页表，将页面P对应的虚 地址指向版本PV<1,0>。同样，当线程T2进入第一个执行切片时，它的向量时钟为<0,1>， 当线程T2第一次写页面P时，它会创建一个新的版本PV<0,1>，并修改页表将页面P对应 的虚地址指向版本PV<0,1>。此时线程T1和线程T2仍然并行执行，但是访问的是页面P 的不同版本。接下来线程T2在第二个执行切片生成了页面P的第三个版本P<0,2>。此时， 线程T1和线程T2发生了同步：线程T2释放锁，而线程T1获得锁，因此形成了线程间两 个同步语句的happens-before关系。根据DLRC内存一致性模型，线程T1的向量时钟变为 <2,3>，本实施例需要创建页面P的一个新的版本PV<2,3>。创建方法如下：首先找到PV<1,0> 和PV<0,2>这两个版本的共同前驱版本P<0,0>(也可以看作是这两个版本的下确界)，计算 PV<1,0>和PV<0,0>之间的差别，即Diff(PV<1,0>,PV<0,0))，以及PV<0,2>和PV<0,0>之间 的差别，即Diff(PV<0,2>,PV<0,0>)，并把这些差别合并到PV<0,0>上以产生新的版本 PV<2,3>＝PV<0,0>+Diff(PV<1,0>,PV<0,0))+Diff(PV<0,2>,PV<0,0>)。最后把新版本加入 到页面P的版本列表中。

本实施例中，步骤2)中为线程选择符合DLRC内存一致性的页面向量版本时，针对当 前执行切片S，从访问的页面P的所有版本PV1～PVn中选择S当前向量时钟的下确界版 本PVk，下确界版本PVk满足以下条件：(1)执行切片S的向量时钟大于或等于PVk的版 本号；(2)不存在向量时钟大于下确界版本PVk的向量时钟的版本PVx。在选择PVk之后， 修改线程T的页表，使得页面P的虚地址指向PVk所对应的物理地址。同时调用Linux系 统调用mprotect函数保护页面PVk，使其不具有写权限，以便在执行切片S中线程T第一 次写PVk时，对PVk做copy-on-write。

本实施例中，步骤1)中的向量时钟的值用形如<x1,x2,x3,…,xn>的向量形式描述，向量 时钟中向量元素的个数为多核并行程序的线程数量，且向量时钟中第n个线程Tn对应于向 量时钟的第n个元素xn。向量元素的个数取决于分布式系统中并行执行个体的数量，在多 线程程序中，也就是线程数。线程Tn对应于向量时钟中的第n个元素。在实现中，每个线 程T维护一个向量时钟V，跟踪它所看到的时间值，并用这个时间值给线程T中发生的事 件做时间戳。两个事件的向量时钟如果能比较大小，则说明它们之间有时序关系，否则说 明它们没有时序关系(没有时序关系表明系统不能判断两个事件发生的先后顺序)。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例， 凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的 普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应 视为本发明的保护范围。