Loop Parallelism

发表于 更新于 本文字数： 671 阅读时长 ≈ 2 分钟

Parallel Loops

未知循环次数，利用了指针的for循环
每一个迭代当作一个子任务，finish约束整个循环

1
2
3
4
finish {
    for (p = head; p != null ; p = p.next) 
        async compute(p);
}

已知循环次数n，可以利用forall

1
2
3
// vector addition
forall (i : [0:n-1]) 
    a[i] = b[i] + c[i]

利用 Java streams，上述功能有更加简洁的表达方式

1
2
...
a = IntStream.rangeClosed(0, N-1).parallel().toArray(i -> b[i] + c[i]);

Parallel Matrix Multiplication

假设两个n*n的矩阵相乘，有

$$
c[i][j] = \sum_{k=0}^{n-1} a[i][k] * b[k][j]
$$
伪代码表示为

1
2
3
4
5
6
7
for(i : [0:n-1]) {
  for(j : [0:n-1]) { c[i][j] = 0;
    for(k : [0:n-1]) {
      c[i][j] = c[i][j] + a[i][k]*b[k][j]
    }
  }
}

要替换成并行计算，可以简单地将外两层的for循环改成forall

for-k 必须是线性的，因为这里有写数据（data race

Barriers in Parallel Loops

下面有一个简单的并行任务

1
2
3
4
5
forall (i : [0:n-1]) {
    myId = lookup(i); // convert int to a string 
    print HELLO, myId;
    print BYE, myId;
}

在不同的执行下会有不同顺序的结果（相同myId对应的HELLO一定在BYE之前

barriers可以将一个parallel loop分为不同的阶段

在两个print之间插入一个barrier，可以保证所有的HELLO出现在BYE之前

两种写法：

  • 在一个forall循环中插入barriers分为不同的阶段 (两个对应的print共享myId

  • 为每个阶段写自己的forall循环 (借助 intermediate data structure to communicate the myId values from one forall to another forall

Parallel One-Dimensional Iterative Averaging

Solve the recurrence
$$
X_i=\frac{X_{i-1}+X_{i+1}}2
$$

with boundary conditions
$$
X_0=0\ and\ X_n=1
$$

Jacobi method利用两个数组oldX[] and newX[]迭代求解该问题，并行伪代码如下：

1
2
3
4
5
6
for (iter: [0:nsteps-1]) {
  forall (i: [1:n-1]) {
    newX[i] = (oldX[i-1] + oldX[i+1]) / 2;
  }
  swap pointers newX and oldX;
}

上述方法创建了 nsteps × (n − 1) 个任务

使用Barriers可以减少需要创建的任务个数

1
2
3
4
5
6
7
forall ( i: [1:n-1]) {
  for (iter: [0:nsteps-1]) {
    newX[i] = (oldX[i-1] + oldX[i+1]) / 2;
    NEXT; // Barrier
    swap pointers newX and oldX;
  }
}

上述方法只需要创建 (n-1) 个任务

This is a significant improvement since creating tasks is usually more expensive than performing barrier operations.

Iteration Grouping/Chunking in Parallel Loops

对于向量相加问题

1
forall (i : [0:n-1]) a[i] = b[i] + c[i]

上述方法创建了n个任务，当n很大时overheads也会很大

解决方法

分组（loop chunking or iteration grouping

1
2
forall (g:[0:ng-1])
  for (i : mygroup(g, ng, [0:n-1])) a[i] = b[i] + c[i]

上述方法将任务个数从 n 降到了 ng（分组个数

分组方法有两种：

  • block
    • 将连续的迭代分为一组
  • cyclic
    • 将同余类迭代（ iterations in the same congruence class，分为一组