• 并行多核体系结构基础 Yan Solihin 第3章 共享存储并行编程 摘录

    重点在于通过分析代码或算法来识别出可以并行的任务、确定变量的范围、协调并行任务，以及向编译器展现并行性。

    3.1 并行编程的步骤

    共享存储并行编程步骤如下。创建并行程序的第一步是识别代码中的并行性来源。程序员可以在不同层面（如代码层面和算法层面）执行多种分析技术以识别并行性。识别并行任务之后，如果任务很小，还需要将其组合成规模较大的任务。在这一步中，任务将成为一个线程可以执行的最小单元。然后确定任务使用的每个变量的范围。由于两个任务可能由两个不同的线程执行，需要确定每个变量是为所有线程共享还是单个线程私有。接下来就是通过线程同步协调任务的执行。本章将讨论线程需要使用什么类型的同步，以及同步在线程中的使用位置。最后，本章将讨论如何将任务分配给线程以及如何将线程映射到处理器。整体而言，并行性识别、变量范围的确定和同步可以统称为任务创建，通过这些步骤线程可以相互合作完成一个完整的计算任务。任务创建相对来说是独立于机器的，程序员不需要了解处理器数量、处理器互连方式以及数据组织形式。

    下一步就是将任务分配给线程。通常情况下，任务比可用的处理器要多，并且产生比处理器数量更多的线程（这将导致线程分时复用单个处理器），这样往往性能很差，因此需要将多个任务分配给同一个线程处理。任务到线程映射的目标是实现线程间的负载均衡。并行编程的最后一步是进行线程到处理器的映射，以及在存储中组织好数据。这步骤的目标是实现局部通信，即通信的处理器之间彼此靠的很近，以及局部数据，即每个处理器访问的数据尽可能靠近处理器。最后这两步骤称为任务映射。有时，任务映射对程序员是透明的，如通过使用系统默认的映射方式。但是，这种默认映射有时会产生次优的性能和可扩展性。

    任务创建的第一步是识别并行任务，可以从三个层次做到：程序级、算法级和代码级。文件的并行编译时程序级并行任务的一个例子。例如，并行make工具产生的进程可以并行编译不同的源文件。程序级并行虽然有效，但是只能应用于程序的多个实例可以同时运行的情况。此外，利用程序级并有时并不能产生明显的性能改善。因此，本章重点讨论代码级和算法级上识别并行性。识别代码级并行是一种通用技术，因为我们只需要分析代码结构，而不需要了解代码所表示的算法。然而，了解算法有时会带来代码级并行无法发现的其他并行机会。

     3.2 依赖分析

    依赖分析的目标是发现是否有可用并行的的代码段。一般而言，两个没有依赖关系的代码段可用并执行，而两个具有依赖关系的代码段可能无法并行执行。

    依赖分析仅使用源代码中嵌入的信息来识别代码级并行性，对于其他信息，如算法的知识，并没有考虑在内。

    依赖分析需要处理的第一个问题是确定代码分析的粒度。这个选择很大程度上取决于程序员，但也有一些限制。例如，最小的粒度可能是单个机器指令。机器指令之间的依赖很大程度上取决于寄存器依赖，如一条指令产生另一条指令需要读取的寄存器值。发掘寄存器值上的依赖或非依赖多需要一个通用寄存器，这特别适合单个处理器上的指令级并行。因此，对于并行编程的最小粒度是源代码语句级别。更大粒度可以是循环体（循环的不行）。更进一步甚至可以是大型函数体或抽象算法步骤级别。

    为了能够系统地执行依赖分析，有必要定义一个框架。在源代码中用S表示一个语句或一组语句。如果有两个语句S1和S2，那么S1-->S2表示程序执行语句S1和S2之前出现。此外，定义下面的依赖关系（或简称为“依赖”）。

    S1\rightarrow ^TS2：表示真依赖，即S1写入S2读取的位置。

    S1\rightarrow^AS2：表示反依赖，即S1读取S1写入的位置。

    S1\rightarrow ^OS2：表示输出依赖，即S1写入S2写入的位置。

    1. S1: x = 2;
    2. S2: y = x;
    3. S3: y = x + z;
    4. S4: z = 6;

    反依赖和输出依赖也被称为反依赖，因为后续指令并不依赖与先前指令产生的任何值，该依赖关系只是因为它们涉及相同的变量或存储位置。因此，通过重命名变量实际上可以消除假依赖。真依赖一般难以消除，因为它们是并行化的真正障碍。

    在一个并行程序中，只有两条语句可以在不同的线程上并行执行时，重命名才是必须的。因此，重命名通常会为每个线程创建一个变量的“私有”副本。为此，并行程序中消除假依赖的典型方法称为私有化。

    通过组合相邻的语句来实现更大粒度上的依赖分析。这样做的一个原因是可以在语句组之间识别出并行性，而不是语句之间。

    直觉是，语句组越大，相对来说并行开销越小。此外，如果语句组非常大，语句组之间将越来越多样化，进而可能产生更多的跨组依赖。因此，需要确定合适的语句组粒度从而在语句组之间识别出更多的并行性。

    一种语句组粒度是循环或循环嵌套体。循环结构能够展现出比较好的特征。首先，它们通常是规则的且易于分析。其次，它们占据了许多科学应用的大部分执行时间。许多物理现象的模型大量使用矩阵作为其主要数据结构对物理空间中的物体进行建模。访问这些多维数据结构需要使用嵌套循环遍历不同维度并以时间步长迭代。非数值应用程序很少使用矩阵，相反，它们使用链式数据结构，如链表、散列表、数和图。虽然遍历这些结构也经常涉及循环，但是这些循环的代码结构要复杂许多，因为许多指针的地址只有在运行时才能获得，并且有时循环还要涉及递归。因此，循环级代码分析在识别非数值应用中的并行性方面效果不佳。

     3.2.1 循环级依赖分析

    循环传递依赖可以定义为一次迭代中的语句与另一次迭代中的语句之间存在的依赖关系，而循环独立依赖为循环迭代内部语句之间存在的依赖关系。

    1. for (int i = 0; i < n; i++){
    2.     S1: a[i] = a[i - 1] + 1;
    3.     S2: b[i] = a[i];
    4. }
    5.  
    6. for (int i = 1; i < n; i++)
    7.     for (int j = 1; j < n; j++)
    8.         S3: a[i][j] = a[i][j - 1] + 1;
    9.  
    10. for(int i = 1; i < n; i++)
    11.     for(int j = 1; j < n; j++)
    12.         S4: a[i][j] = a[i - 1][j] + 1;

    在第一个循环中，对a[i]写入并读取a[i-1]，即循环传递依赖S1[i]\rightarrow ^TS1[i+1]。此外，在同一次迭代S1写入的a[i]，被S2语句读取，因此S1[i]\rightarrow ^TS2[i]。

    在第二个循环中，a[i][j]中写入的值会在接下来的第j次迭代中读取，因此S3[j] \rightarrow ^TS3[j+1]，这对于for j循环是循环传递依赖，而对for i循环是循环独立依赖。

    在第三层循环中，a[i][j]中写入的值会在第i次迭代中读取，因此S4[i] \rightarrow ^TS4[i+1]。对于for i循环是循环传递依赖，而对for j循环是循环独立依赖。

    3.2.2 迭代空间遍历图和循环传递依赖图

    迭代空间遍历图ITG（iteration graph）以图形方式展示了迭代空间中的遍历顺序。ITG不能显示依赖，它只显示循环迭代的访问顺序。

    循环传递依赖图LDG（loop dependency graph）以图形方式展示了真/反/输出依赖，其中一个节点就是迭代空间的一个点，而有向边显示依赖的方向。换句话说，LDG将最内层循环中国的所有语句视为一个语句组。由于一个节点代表依次迭代中的所有语句，所以LDG不显示循环独立依赖。LDG本质是依赖的一个展开版本。LDG图中并没有给出精确的迭代次数，而是以增加i或者增加j来替代。

    1. 例1：
    2. for(int i = 0; i < 4; i++)
    3.     for (int j = 1; j < 4; j++)
    4.         S3: a[i][j] = a[i][j - 1] + 1;
    5.  
    6. 例2:
    7. for(int i = 0; i < n; i++)
    8.     for (int j = n - 2; j >= 0; j--){
    9.         S3: a[i][j] = b[i][j] + c[i][j];
    10.         S4: b[i][j] = a[i][j + 1] * d[i][j];
    11. }
    12.  
    13. 例3:
    14. for(int i = 1; i < n; i++)
    15.     for (int j = 1; j < n; j++){
    16.         S1: a[i][j] = a[i][j - 1] + a[i][j + 1] + a[i - 1][j] + a[i + 1][j];
    17. }

    例1本质的依赖是S3[i,j] \rightarrow ^TS3[i,j+1]

    例2本质的依赖是b[i][j]上S3[i,j] \rightarrow ^AS3[i,j]，以及a[i][j]上S3[i,j+1] \rightarrow ^TS3[i,j]。

    例3本质的依赖是S1[i,j] \rightarrow ^TS1[i,j+1], S1[i,j] \rightarrow ^TS1[i+1,j]，以及S1[i,j] \rightarrow ^AS1[i,j-1], S1[i,j] \rightarrow ^AS1[i-1,j]

    3.3 识别循环结构中的并行任务

    分析循环结构来识别各种类型的并行，包括DOALL，DOACROSS和DOPIPE、程序员需要对循环嵌套结构来执行拆分、重写等操作。

    3.3.1 循环迭代间的并行和DOALL并行

    分析哪些循环迭代可以被并行执行是识别并行的最有效的方法之一。为了做到这一点，首先需要分析循环传递依赖。第一个原则是必须遵守依赖关系，特别是真依赖。注意反依赖和输出依赖可以通过私有化移除。

    在LDG中可以通过观察连接代表迭代的两个节点的边直观地看出两个迭代之间的依赖关系。迭代之间的依赖关系也可以被看作连接两个节点的路径(一组边)。只有当两个节点之间没有连接边或路径时。才可以说两个节点之间没有依赖。

    1. for(int i = 2; i <= n; i++)
    2.     S: a[i] = a[i - 2];

    从LDG可知，技术迭代没有指向偶数迭代的边，偶数迭代也没有指向奇数迭代的边。因此，这里可以提取两个并行任务：一个执行奇数迭代，另一个执行偶数迭代。为了实现这一点，可以将循环分成两个比较小的循环。这两个循环可以相互并行执行，尽管每个循环内仍然需要顺序执行。

    当一个循环的所有迭代都是可以并行的任务时，则该循环表现出DOALL并行。如之前的例2的for i循环。

    例3的LDG，显示i次迭代和j次迭代的循环传递依赖。可以注意到，反对角线循环迭代之间不存在循环传递依赖。在每个反对角线循环迭代之间不存在循环传递依赖。在每个反对角线中，图中没有任何两个节点存在彼此指向的边或路径。但是，同等的情况对于对角线却不成立。因为尽管对角线的中的节点没有直连边，但它们存在路径。

    不幸的是，为编译器指定这样的并行任务并不容易。解决上述缺陷的一个方法就是重构代码，即一个循环变量反对角线，而另一个内层循环遍历一个反对角线的节点。然后可以为内存循环指定DOALL并行。

    1. 计算反对角线的数量；
    2. 对每条反对角线{
    3.     计算当前反对角线上的点数量
    4.     对当前反对角上的每个点
    5.         计算矩阵中的当前点
    6. }

    3.3.2 DOARCOSS：循环迭代间的同步并行

    通常，DOALL并行循环中并行任务的数量非常大，因此在识别其他类型的并行之前应该先尝试识别DOALL并行。然后，在一些循环中，由于循环迭代中的循环传递依赖，导致DOALL并行不可行。对于存在传递依赖的循环，DOACROSS并行也可以提取并行任务。

    例如：

    1. for (int i = 1; i <= N; i++)
    2.     S: a[i] = a[i - 1] + b[i] * c[i];

    该循环存在循环传递依赖：S[i] \rightarrow ^TS[i+1]。仔细观察后发现b[i]*c[i]相乘语句没有循环传递依赖，有两种办法可以利用。第一种选择时将循环拆分成两个循环：第一个循环只执行没有循环传递依赖的部分，而第二个循环只执行有循环传递依赖的语句部分。结果如下所示：

    1. // 该循环有DOALL并行
    2. for (int i = 0; i <= N; i++)
    3.     S: temp[i] = b[i] * c[i];
    4.  
    5. // 该循环无DOALL并行
    6. for (int i = 1; i <= N; i++)
    7.     S: a[i] = a[i - 1] + temp[i];

    另一种在具有邠循环传递依赖的循环中提取并行任务的解决方案是采用DOACROSS并行性。其中每个迭代仍然是并行任务，但插入了同步以确保使用者迭代consumer iteration只读取产生者迭代producer iteration产生的数据。这可以通过在有循环传递依赖的语句部分之间插入点对点同步实现。所需要的的同步原语是：提交，由数据产生者调用，表示数据已准备好了，等待，由使用者调用，并阻塞直到数据就绪。只有当一个相应的post(x)时，wait(x)才会解锁，其中x是唯一标识同步的变量名。一个简单的实现方法是，当有post(x)操作时，递增与x关联的计数器，而wait(x)操作等待直至计数器值非零，之后递减与x有关的计数器值。

    1. post(0);
    2. for (int i  = 1; i < N; i++){
    3.     S1: temp = b[i] + c[i];
    4.     wait(i - 1);
    5.     S2: a[i] = a[i - 1] + temp;
    6.     post(i);
    7. }

    应用DOACROSS之后，temp变为一个私有变量，而不是共享数组。因此，存储开销值随着线程数量的增加而增加，而不是迭代的数量。注意语句post(i),post(i)相当于生产者发出的信号，a[i]的值已经产生，并且已经准备好被等待使用者使用。还需要注意注意的语句是wait(i-1)，wait(i-1)相当于使用者发出的信号，即使用者必须等待生产者产生a[i-1]的值，在这种情况下是之前的第i此迭代。此外还需要注意在第一次迭代中，语句S2读取a[0]，而a[0]不由任何迭代产生。因此，我们需要添加post(0)来确保第一次迭代不会永远阻塞。随着转换和同步的插入，循环的迭代变成并行任务。

    该方法可以节省多少时间呢？假设同步延迟为0。T_{S1}和T_{S2}分别表示语句S1和语句S2的执行时间。如果循环顺序执行，执行时间为N*(T_{S1} + T_{S2})，如果使用DOACROSS执行，则对于其他迭代中所有语句可以并行执行S1。S2语句被顺序执行，其中每个S2等待，直到来自先前迭代的相同语句产生了它所等待的数据。因此，执行时间是T_{S1} +N* T_{S2}。

    实践证明，实际性能能够得到多少改进取决于循环中没有循环传递依赖的部分（例如T_{S1}）的执行时间与由于循环传递依赖而必须被串行执行的部分（T_{S2}）的执行时间的比例大小，以及同步开销的大小。由于同步开销通常很大，程序员在使用DOACROSS并行时必须小心。减少同步开销的一种方法是将许多组并行任务分组到一个线程，这样同步可以在线程之间而不再任务之间执行，所以同步的频率的可以大大降低。

    3.3.3 循环中语句间的并行

    当一个循环具有循环传递依赖时，另一种并行化的方法是将一个循环分支(distribution)到几个循环中，这些循环执行来自原始循环体的不同语句。

    1. for(int i = 0; i < n; i++){
    2.     S1: a[i] = b[i + 1] + a[i - 1];
    3.     S2: b[i] = b[i] * coef;
    4.     S3: c[i] = 0.5 * (c[i] + a[i]);
    5.     S4: d[i] = d[i - 1] * d[i];
    6. }

     这段循环中有S1[i] \rightarrow ^TS1[i+1],S4[i] \rightarrow ^TS4[i+1]的循环传递依赖，还有S1[i] \rightarrow ^AS2[i+1]反依赖。除此之外，还有S1[i] \rightarrow ^TS3[i]循环独立依赖。语句中缺少的循环传递依赖为并行提供了机会。例如，注意到S4与循环体中的其他语句没有依赖关系，可以将循环分发到两个循环。其中，一个循环执行前三条语句，另一个循环执行最后一条语句。修改后的如下：

    1. for(int i = 0; i < n; i++){
    2.     S1: a[i] = b[i + 1] + a[i - 1];
    3.     S2: b[i] = b[i] * coef;
    4.     S3: c[i] = 0.5 * (c[i] + a[i]);
    5. }
    6.  
    7. for(int i = 0; i < n; i++){
    8.     S4: d[i] = d[i - 1] * d[i];
    9. }

     与DOALL并行和DOACROSS并行中每个并行任务对不同的数据执行相似的计算(称为数据并行)不同，这里每个并行任务在不同的数据集上执行不同计算(称为函数并行)。函数并行的特点是并行度通常是适中的，而且不会随着输入规模的增大而增加。这是因为函数并行的来源是代码结构，而不是代码操作的数据。由于不同的并行任务执行不同的计算，通常很难在任务间平衡负载。因此，大多数可扩展的程序具有丰富的数据并行。然而，当数据并行有限时，函数并行可以增加并行性。

    串行执行时间为：N*(T_{S1} + T_{S2} + T_{S3} + T_{S4})

    分发循环之后并行：max(N*(T_{S1} + T_{S2} + T_{S3}), N*T_{S4})

    注意到S1[i] \rightarrow ^AS2[i+1]表示迭代i+1中的语句S2必须在迭代S1之后执行。因此，如果所有S2都是在S1之后执行，那么就不会违反该依赖。类似的S1[i] \rightarrow ^TS3[i]表示迭代i中的语句必须在迭代i中的S1之后执行。即，执行语句S1和S4的前两个循环可以相互并行执行。第1个循环完成后，第3个循环语句S2和第4个循环S3都可以DOALL并行方式执行。确保第3个和第4个循环仅在第1个循环完成之后执行，依靠点对点同步或栅栏来实现。

    此时循环的时间为：max(N*T_{S1} + max(T_{S2}, T_{S3}), N*T_{S4})

     3.3.4 DOPIPE:循环中语句间的流水线并行

    对于存在依赖传递的循环，还可以利用流水线并行。

    1. for (int i = 1; i <= N; i++){
    2.     S1: a[i] = a[i - 1] + b[i];
    3.     S2: c[i] = c[i] + a[i];
    4. }

     循环中存在传递依赖：S1[i] \rightarrow ^TS1[i+1]，以及独立依赖S1[i] \rightarrow ^TS2[i]，此时若仅使用循环分发，第2个循环在第1个循环结束之后利用DOALL并行执行，此时执行时间：N*T_{S1}+\frac{N}{P}*T_{S2}

    另外一种更好的解决方法是分发循环并引入流水线并行。利用流水线并行机制，在第1个循环中语句S1产生a[i]之后，第2个循环执行语句S2，S2读取刚生成的a[i]的值。这种并行性称为DOPIPE，代码如下：

    1. for (int i = 1; i <= N; i++){
    2.     S1: a[i] = a[i-1] + b[i];
    3.     post(i);
    4. }
    5.  
    6. for (int i = 1; i <= N; i++){
    7.     wait(i);
    8.     S2: c[i] = c[i] + a[i];   
    9. }

    不过DOPIPE并行的并行性有限，其难以确保并行任务间的负载均衡。

    DOPIPE并行可以通过引入同步间隔来减少开销。这里可以每n次迭代后使用一次post(a[i])(n即同步间隔)，而不是每产生一个a[i]时就调用一次post(a[i])。这种方法很简单，程序员只需要用if(i % n == 0)语句来封装post和wait即可。

    在多核架构中，多处理器核心通常共享最后一级高速缓存。在这样的架构中，DOPIPE并行的一个独特好处是它的缓存效率较高，因为由生产者任务产生的数据值几乎立刻被使用者任务所使用。DOPIPE的局部性很好。这和DOALL并行是相反的，在DOALL并行中，每个任务在不同的迭代中处理大量不同的数据集。如果分配给一个线程的任务很多，那么许多线程将竞争高速缓存空间，并且有可能属于不同线程的工作集在高速缓存中不断被换入换出。

    DOPIPE并行是应用在循环层面的一种流水线并行机制。也可能存在其他层次上，如跨循环、跨函数或跨算法中的逻辑段。这种任务层的流水线机会需要通过依赖分析进行识别。

    3.4 识别其他层面的并行

    尽管循环层面上的并行通常是最有成效的，但有时由于其关键数据结构的设计，有些应用程序没有规则的循环结构。当循环几乎没有并行机会时，程序员可能要在非循环粒度上进行分析。

    例如，假设要分析一些函数及其调用者之间的依赖关系，需要分析函数之间或者函数与函数调用者之间是否可以并行执行。为此，可以将代码分成三组语句：简述调用之前的代码（前置代码）、被调用的每个函数、以及函数调用之后的代码（后置代码）。前置代码、函数、后置代码之间的依赖关系决定了可以识别的并行任务。任何前置代码、函数和后置代码之间缺少真依赖都会带来并行机会。

    对于深度优先的搜索方式遍历整个数，并计算和存储了与被搜索的数据相匹配的节点数目。在函数体内有两个递归函数调用，处理前置语句组S1和后置语句组S4之外，可以将递归调用函数看成两个语句组S2和S3。

    1. int serach_tree(struct tree* p, int data)
    2. {
    3.     int count = 0;
    4.     if (p == NULL)
    5.         return 0;
    6.     if (p->data == data)
    7. S1:     count = 1;
    8. S2: count = count + search_tree(p->left);
    9. S3: count = count + search_tree(p->right);
    10. S4: return count;
    11. }

    依赖分析揭示，对于count变量而言：

    S1\rightarrow ^TS2，S1\rightarrow ^TS3，S1\rightarrow ^TS4；

    S2\rightarrow ^TS3，S2\rightarrow ^TS4；

    S3\rightarrow ^TS4；

    幸运的是，对count的依赖可以通过重命名来消除，从而得到下例代码：

    1. int serach_tree(struct tree* p, int data)
    2. {
    3.     int count1 = 0, count2, count3;
    4.     if (p == NULL)
    5.         return 0;
    6.     if (p->data == data)
    7. S1:     count1 = 1;
    8. S2: count2 = search_tree(p->left);
    9. S3: count3 = search_tree(p->right);
    10. S4: return count1 + count2 + count3;
    11. }

    新代码中真依赖数目减少，如下：

    S1\rightarrow ^TS4，S2\rightarrow ^TS4，S3\rightarrow ^TS4；

    可以进一步利用更大的代码粒度来寻找更深层次的并行，如查看对search_tree的第一个函数调用是否与周围的前置代码和后置代码以及其他附近的函数调用有任何依赖关系。确定执行依赖分析的粒度并基于此识别出并行任务是一个复杂的决策，这取决于可并行化的代码规模。可并行度、负载不均衡的程度以及特定目标机器上的并行开销。

    3.5 通过算法知识识别并行

    有时只分析代码并不能带来最大限度的并行性。分析算法可以带来更多机会以提取并行任务。这是因为代码结构中嵌入了不必要的串行，这是串行编程语言的产物。

    例如，假设一个算法来更新一个粒子受到相邻4个水粒子的作用力。

    1. while 未收敛到一个解do:
    2.     for each时间步do：
    3.         for each横截面do一次扫描；
    4.             for each横截面中的点do；
    5.                 计算与邻居粒子的相互作用力；
    6. for (int i = 1; i <= N; i++){
    7.     for (int j = 1; j <= N; j++){
    8.         S1: temp = A[i][j];
    9.         S2: A[i][j] = 0.2 * (A[i][j] + A[i][j - 1] + A[i - 1][j] + A[i][j + 1] + A[i + 1][j])
    10.         S3: diff += abs(A[i][j] - temp);
    11.     }
    12. }

     分析代码表明唯一的并行机会再反对角线上，因此必须重构代码来利用这个并行机会。然而，计算的基本事实上并没有指定任何特定的顺序，从而确定必须优先更新的横截面的元素。该算法仅指定在一次扫描中，横截面中的每个点必须通过考虑与其相邻的交互来更新一次。一旦算法被翻译成代码，则人为地引入一个特定的遍历顺序：首先按照这个列排序，然后是行顺序，这可以从ITG观察到。

    首先，可以在迭代空间中为每次迭代分配一个颜色：黑色或红色。如果迭代的行号加上列号是偶数，那么将其置为黑色，否则将其置为红色。红色和黑色之间没有直接依赖关系(LDG的直连边)，但它们之间有间接依赖关系(LDG中的路径)。由于在单次扫描中，只有直接依赖是相关的。所以任何黑色迭代的新值与所有其他黑色迭代的旧值都不相关。红色依然如此，因此，并行地遍历黑色迭代或红色迭代不会违反循环传递依赖。如果首先使用循环扫描黑色迭代，那么循环表现DOALL并行。同样，如果使用一个循环扫描红色迭代，那么循环表现出DOALL并行。但是，在更新任何红色之前更新所有黑色迭代，就必须要更改更改横截面中点的遍历顺序。如果算法允许，可以采用下列代码变换。

    另一种可能产生更多并行性的算法分析技术是分析算法是否可以容许非确定性执行，也就是说，是否可以容忍更新顺序的动态变化。如果可以，我们可以简单地忽略依赖，并行执行所有扫描迭代，而不需要将扫描分成黑色或红色扫描。有人可能会认为这样会导致结果混乱。然而，结果可能不像人们所想的那样混乱，因为非确定性被限制在一次扫描中，而不是跨扫描。

    1. // 带有DOALL并行的外部和内部循环的黑色扫描
    2. for (int i = 1; i <= N; i++){
    3.     int offset = (i + 1) % 2;
    4.     for (int j = 1 + offset; j <= N; j += 2){
    5.         S1: temp = A[i][j];
    6.         S2: A[i][j] = 0.2 * (A[i][j] + A[i][j - 1] + A[i - 1][j] + A[i][j + 1] + A[i + 1][j])
    7.         S3: diff += abs(A[i][j] - temp);
    8.     }
    9. }
    10.  
    11. // // 带有DOALL并行的外部和内部循环的红色扫描
    12. for (int i = 1; i <= N; i++){
    13.     int offset = i % 2;
    14.     for (int j = 1 + offset; j <= N; j += 2){
    15.         S1: temp = A[i][j];
    16.         S2: A[i][j] = 0.2 * (A[i][j] + A[i][j - 1] + A[i - 1][j] + A[i][j + 1] + A[i + 1][j])
    17.         S3: diff += abs(A[i][j] - temp);
    18.     }
    19. }

    另一个例子是图像平滑算法，即一个点需要9个点数据。 

    1. for (int i = 1; i < N - 1; i++){
    2.     for (int j = 1; j < N - 1; j++){
    3.         S1: temp = A[i][j];
    4.         S2: A[i][j] = A[i][j] + A[i][j - 1] + A[i - 1][j] + A[i][j + 1] + A[i + 1][j] + 
    5.                                 A[i - 1][j - 1] + A[i - 1][j + 1] + A[i + 1][j + 1] + A[i + 1][j - 1];
    6.         S3: diff += abs(A[i][j] - temp);
    7.     }
    8. }

    分析代码后发现并没有并行任务，因为跨行、列甚至反对角线都存在循环传递依赖，所以该例甚至不能使用红黑分区。ITG在更新像素过程中，引入了人为的序列化。可以再次考虑是否任何更新顺序都会产生可接受的结果。在本例中，答案是肯定的，因为有平滑引起的图像轻微变化可能并不明显。因此，我们可以忽略所有关系，并同时在for i循环和for j循环中提取DOALL并行。

    3.6 确定变量的范围

    并行任务数量多于可用处理器的数量，因此多个任务在分配给线程执行之前经常会合并为大任务。执行任务的线程数通常等于或小于可用处理器的数量。

    下一步骤就是变量分区，这一步确定变量应该具有线程私有作用域还是线程共享作用域。这一步是共享存储编程特有的；在消息传递模型中，所有变量都是线程私有的，因为每个进程都有自己的地址空间。

    在这一步中，需要通过已经确定的并行任务来分析不同变量的使用，并将其分类到以下类别中：

            只读：变量只有所有任务读取；

            读写/非冲突：变量只由一个任务读取、写入或者即读取又写入，如果变量为矩阵，则其中不同的元素别不同的任务读取/写入；

            读写/冲突：如果任务并行执行，有一个任务写入的变量可能有不同的任务读取；

    对于下列代码，如果将for i循环中每个迭代定义为并行任务，那么只读变量包括n，矩阵c和d。因为它们并未被任何任务修改。读写/非冲突包括矩阵a和b。最后循环索引变量i和j是读写/冲突变量。

    1. for(int i = 0; i < n; i++)
    2.     for (int j = 0; j < n; j++){
    3.         S2: a[i][j] = b[i][j] + c[i][j];
    4.         S3: b[i][j] = a[i][j-1] * d[i][j];
    5. }

    读写/冲突变量阻碍并行，因为它引入了线程之间依赖。因此，这里需要相关的技术来消除这种依赖。其中一种技术就是私有化。私有化为每个读写/冲突变量创建单线程副本，以便每个线程可以单独工作在自己的副本上。另外一种技术就是归约reduction，归约为每个读写/冲突变量创建当线程副本，使得每个线程都能够在自己的副本中产生部分结果，并且在并行部分的结尾处，所有的部分结果合并全局结果。

    3.6.1 私有化

    私有化创建共享变量的私有副本，以便每个线程在本地副本而不是共享副本上工作。这样做消除了读写/冲突并允许并行。

    在什么情况下一个变量可以私有化呢？一种情况是，在原始的顺序程序执行次序中，变量由一个任务首先定义（或写入），然后才能被该任务使用（或读取）。

    变量可以私有化的另一种情况是变量在被同一个任务读取之前没有被定义，但是任务应该从变量中读取的值是事先知道的。

    私有化可以应用于标量变量和数组或矩阵。当然，在应用于变量时，额外的空间开销很小。当应用于数组或矩阵时，额外的空间开销和初始化它们的开销可能很大。

    一个理解创建私有副本的方式是可以认为将标量变量替换成以任务ID为索引的变量数组的引用。

    私有化消除了线程间的依赖，因为每个线程都在自己的变量副本上工作。由于没有线程需要读取另一个线程产生的值，所以线程相互独立并且可以相互并行操作。但是，如果读写/冲突变量不能被私有化，则必须通过同步来保护对其的访问，以确保使用变量值的线程等待直到该变量值由另一个线程产生。

    3.6.2 归约变量和操作

    归约是与私有化相关的一种技术。归约的计算结果可以由多个并行任务计算的部分结果组成。归约操作的并行策略即每个线程计算一个部分结果并将其存储在变量的私有副本中，最后将所有任务的部分结果合并以形成最终结果。与常规私有化不同，私有副本中的值使用归约运算符合并到共享变量副本中。由于保存最终计算结果涉及共享副本，所以归约变量有时候被称为半私有。

    那些操作可以归约呢？操作必须是可交换和可结合的。比如加法、乘法、最大值、最小值、逻辑与或非。

    3.6.3 准则

    只读变量，读写/非冲突变量应声明为共享，以避免可能降低性能的存储开销。

    对于读写/冲突变量必须格外小心。通常情况下，这样的变量需要声明为共享，当必须由临界区保护对它的访问，此外，如果程序执行的正确性依赖于指令执行的正确顺序，则可能需要点对点同步。注意临界区是昂贵的，因为它将序列化对共享变量的访问，并且锁的实现往往不能扩展到大量的处理器中。因此，应最大限度地减少临界区的使用，对其执行操作应视为归约操作，如果不是归约变量，下一步则检查它是否可以私有化。若私有化带来的额外存储开销可以容忍，并且小于拥有临界区后对性能的影响，则将其私有化。

    另一种选择是重新分析代码并选择一个不同的并行区域。当并行范围改变时，读写/冲突变量通常会变为读写/非冲突变量。例如矩阵乘法中for i循环和for k循环。

    3.7 同步

    注意同步是在线程间而不是在任务间执行。

    三种类型的同步原语应用广泛。第一种是两个并行任务的点对点同步，如DOACROSS和DOPIPE并行时用到的提交和等待。提交操作相当于存放了一个表示数据已经产生的标记，等待操作会阻塞直到有标记被存放，这样可以保证数据准备就绪时使用者才能继续执行操作。

    第二种流行的同步是锁。一个锁只能由一个并行线程获得，一旦该线程持有锁，其他线程无法获得它，直到当前线程释放该锁。

    第三种流行的同步是栅栏。栅栏定义了一个点，只有在线程都到达该点时才允许线程通过。它使并行执行的总时间取决于最慢线程的执行时间，因此使用栅栏时，负载均衡是非常重要的。

    3.8 任务到线程的映射

    任务映射涉及两个方面。第一个方面是如何将任务映射到线程。通常任务比线程更多，这带来了两个问题：那些任务应该分配给同一个线程，以及如何分配？其中需要解决的问题包括任务管理开销(较大的任务会带来较低的开销)、负载均衡(较大的任务可能会减少负载均衡)以及数据局部性。第二个方面是如何将线程映射到处理器，以确保通信处理器尽可能地相互靠近。

    任务映射的一个考量是静态还是动态地将任务分配给线程。静态任务映射意味着任务在执行之前预先分配给线程。例如这可以通过指定一个线程执行DOALL循环的一个迭代实现。动态任务映射意味着任务在执行之前不会分配给线程。相反，任务队列将在执行期间被创建和保持尚未分配给线程的任务。在执行期间，无论哪个线程变为空闲队列，都会从任务队列中抓取一个任务并执行该任务，这一操作一直重复，直到任务队列为空。动态任务队列映射给任务队列管理带来了额外的开销。但有时更容易确保所有线程的负载均衡。动态任务映射往往会增加通信量并减少局部性，因为在编译时不知道数据将由那个线程使用，因为很难将该数据放置在将要使用它的线程中。最后，也可以采用混合映射，其中映射大部分是静态的，当周期性评测负载均衡情况，然后相应地调整映射。

    接下来考虑如何将任务分配给线程。在静态分配中，任务固定分配给线程。对于由循环迭代或连续迭代组成任务的DOALL循环，任务可以以轮询方式分配给线程。这里将被分组的单个任务的连续迭代的数量称为块大小。

    不均衡度：由两个线程执行的迭代次数之差除以所有迭代来衡量。

    较小的块大小往往达到更好的负载均衡。

    实现更好的负载均衡的另一种方法是采用动态任务分配。但是，即便在动态分配的情况下，块大小仍然是一个重要参数。如果块太小，任务可能太少，负载不均衡仍然有可能发生。

    负载均衡和任务开销并不是任务映射中唯一重要的因素，通信成本也是一个重要因素。通信开销分为两种，来自于任务映射对算法影响的固有通信和来自任务映射对数据布局方式和架构影响的人为通信。

    评估固有通信的一个有用指标是通信-计算比CCR。为了计算CCR，可以用通信量除以该线程的计算量。参数是处理器的数量和输入规模。

    在一次扫描中，循环遍历i和j来访问矩阵的所有元素，假设有p个处理器，N*N矩阵维数远远大于p。这里至少有三种可能的方法将任务分配给线程，块划分，行划分，列划分。对于所有情况，每个线程的计算量是相同的，N*N/p。在块划分中，所有边界元素都被多于一个线程访问，内部元素只能由分配给该块的线程访问。在边界上大约有4*N/sqrt(p)。该线程和其他线程之间的通信的元素数量表示通信量为4*N/sqrt(p)，因此CCR被计算为：        CCR=\Theta (\sqrt{p}/N)

    对于行划分的每个分区N/p，有2N个边界元素与其他线程通信。CCR计算为：CCR=\Theta (p/N)

    对于按列划分，通信与按行划分一致。

    在按块划分中，CCR随处理器数量沿sqrt(p)增长，而在按行和按列中，增大比例是p。因此，就固有通信而言，分块映射性能更好。

    但是，如果将人为通信考虑在内，答案就不同了。人为通信必须考虑两个处理器之间共享数据的“乒乓效应”，即在通信处理器之间来回交换数据。这种通信开销不仅取决于数据交换的频率，还取决于每个数据交换的延迟。数据交换的频率取决于存储中的数据布局。此时的总通信量不取决于矩阵元素的数量，而是取决于处理器之间共享缓存块的数量。

    假设每个处理器需要计算8*8的64个元素，并且有一个可以容纳2个元素的连续矩阵元素的缓存块。按块划分，在顶行和底行中，矩阵元素被包含在10个缓存块中，左右边界每个矩阵元素都需要一个缓存块。这样共有22个缓存块与其他处理器共享。在按行划分中，顶行和底行的元素占用16个缓存块。最后按列划分中，每个元素占用1个缓存块，共有2*16=32个缓存块。因此，按行划分实现了最少的人工通信，其次是按块划分。

    这个例子说明一下几点。首先，尽管具有相同规模的固有通信，但是就总通信而言，按行划分和按列划分差别很大。因此，选择使通信最小化的划分策略是非常重要的。其次，如果块内边界列的矩阵元素通信产生大量的人为 通信，则按块划分块内比按行划分的缓存效率低。总的来说，固有通信虽然反映了算法的通信需求，但实际性能更多地取决于总通信量，其不一定与固有通信的行为相同。

    总之，将任务映射到线程时需要考虑多个因素，负载均衡、任务管理开销以及线程之间的通信成本。

    3.9 线程到处理器的映射

     如何将线程映射到处理器。解决这个问题的一个简单方法就是什么都不做，即让操作系统线程调度器去决定。操作系统决定调度器决定何时就绪线程应该运行，以及就绪线程应该运行在那些处理器上，操作系统将响应时间、公平性、线程优先级、处理器的利用率以及上下文切换的开销考虑在内。对于运行来自不同进程的线程集合的系统，操作系统线程调度器在将线程映射到处理器方面做得相当不错。

    然而，在并行编程的情况下，将线程映射到处理器有几个独特的挑战。第一个挑战是如何安排线程相对于彼此的调度时间。并行线程通常会同步，无论使用锁、栅栏还是其他方法。并行程序中的线程必须被协同调度才能避免调度效率低下。例如，当一个持有全局锁的线程被切换出去时会导致低效率。其他想要获得该锁的线程无法获得，因此即使这些线程在处理器上运行，也无法取得进展。另一种情况是当多个线程到达栅栏时，其中一个没有到达栅栏的线程被切换出去了。被切换出去的线程阻止了其他线程的切换。处理器资源再次被浪费，直到该线程被切换进来。最后，在点对点同步中，如果想要发送消息的线程被切换出去，另一个希望接受该信息的线程可能被阻塞等待，无法取得进展。因此，对于一个并行程序，需要确保它的所有线程同时运行或者都不运行。

    一些操作系统线程调度器增加了成组调度的功能，在成组调度中要么所有线程都被调度运行，要么没有线程运行。这消除了对处理器资源的浪费。对于大型系统来说，更需要这种成组调度的支持，因为系统越大，调度错误的成本越高。

    每个计算阶段相对于其他计算节点可能会产生异步的自身噪声。每次当某个节点收到噪声影响时，参与同一个栅栏的所有节点上的所有线程都会变慢。当不同节点中的噪声得到同步时，即推迟操作系统活动并将其在节点上一起调度，线程变慢的频率会小很多，线程的性能也会有所提高。

    将线程映射到处理器的另一个重要方面是数据局部性。这适用于NUMA系统，其中对远程存储的访问可能要比访问本地存储花费的时间要长的多。此时，通过数据映射或线程到处理器的显式映射。

    数据映射允许将数据分配或映射到访问该数据的线程运行所在的节点。在某些情况下，编程模型PGAS可能允许指定数据映射。

    另一种方法是分配或迁移数据到访问该数据的线程。实现该方法可采用分配和迁移策略。一个并行程序开始执行时，因为它的页还未分配，所以会有很多页错误。操作系统通过页分配策略来选择帧处分配页。该帧上的旧页被替换出来，为新页腾出空间。在NUMA系统中，这样的策略不知道页与需要该页的处理器的远近，因此可能不会达到最佳分配。所以，在NUMA系统中需要使用其他策略。一种策略是在导致页错误的节点上分配帧，如在访问该页的处理器所在的同一节点上分配帧，即首次访问策略，基本原理是首次访问页中数据的处理器可能是访问该页中数据最多的处理器。

    另一种页分配策略是轮询调度，其中页以轮询调度的方式分配在不同的存储节点中国。轮询调度均衡地跨节点分配页，因此在此策略中很少发生特定节点上的争用。

    非最佳页分配策略的另一种解决方法是自适用策略，即监控页的使用，并且可以从当前被分配的节点迁移到最多访问该页的节点。

    在NUMA系统中，线程映射的目标是将线程映射到具有该线程将要访问的节点，并将相互通信的线程映射到物理上相邻的节点，线程映射可以使用命令行工具或通过编程语言扩展来实现。

  • 相关阅读:
    Vue_事件修饰符
    go gin 单图上传
    leecode#Excel表列名称#多数元素
    SpringBoot 教程及其相关知识整理
    伯俊ERP和金蝶云星空接口打通对接实战
    【操作系统-进程】进程的概念
    UE5中实现沿样条线创建网格体2-SplineMesh版本
    matlab相机标定实验
    STM32F030F4驱动TIM1637数码管芯片
    nacos 拉取配置失败
  • 原文地址：https://blog.csdn.net/weixin_47955824/article/details/126184209