Chapter 6 同步计算

1. 同步栅栏
   1. 定义
   2. 计数器
   3. 树形栅栏
   4. 蝶形栅栏
   5. 局部同步
   6. 死锁
2. 同步计算 数据并行
3. 同步计算例子
   1. 前缀求和
   2. 迭代法解线性方程组
   3. 热分布问题

1.1 同步栅栏

MPI_Barrier 栅栏

1.2 线性计数器实现

集中式计数器,直观理解签到

栅栏工作的两个阶段：

• 到达阶段：
  • 进程进入此阶段，表明己方已经就绪。
• 离开阶段：
  • 所有的进程都可以离开，进程知晓其他进程已就绪。

1.3 树实现

复杂度降为 O(log p)

1. check in

   1. 两两结对，形成小组
   2. 小组两两结对，形成大组
   3. ......
   4. 根节点只处理两个超大组。

   同学交作业不是直接交给学习委员课代表，而是先交给小组长，小组长们再交给学习委员。

2. check out

   以上过程的相反过程，逐级往下通知即可。

   蝶形栅栏

   • 蝶形结构，
   • 所有的步骤，所有的节点均处于工作状态。 只要一个阶段

   局部同步

   死锁

   两种解决方式

3. 一个进程（比如偶数编号的）先发送后接收，一个进程（比如奇数编号的）先接收后发送。

4. MPI_Sendrecv

同步计算-数据并行

并行程序设计语言中：(注意forall)

forall (i = 0; i < n; i++)
{
   a[i] = a[i] + k; 
}

在每个循环体实例中被赋予不同的值。 以上操作隐着全局的栅栏：

i = myrank;
a[i] = a[i] + k; 
barrier(mygroup);

同步计算-前缀求和

求解线性方程组

1. 对方程组进行变形,如下
2. 将方程组改写为X = BX
3. 对于Xi，利用X=BX，可以计算出Xi+1
4. 若迭代收敛,则可以认为已经求解
   1. 收敛条件(充分)
      1. | x_i^t –x_i^{t-1} |< 误差范围
      2. 

实现

每个未知数分配给一个进程。 对进城 i而言：

x[i] = b[i];                                          // 初始化  
for (iteration = 0; iteration < limit; iteration++) {
    sum = -a[i][i] * x[i];
    for (j = 0; j < n; j++)
        sum = sum + a[i][j] * x[j];
    new_x[i] = (b[i] - sum) / a[i][i];    //新的临时值   broadcast_recv(&new_x[i]);        /*bcast/rec values */
    global_barrier();                          /* wait for all procs */
}

复杂度线性

热分布问题

问题描述

计算机对热传导方程离散化模拟。

• 正方形的金属薄片。
• 四条边的温度已知。特别地，如果四边的温度相等，最终每个点的温度都与边的温度相等。
• 任一点的温度依赖于周围点的温度：
• 正方形划分为正方形的小网格，每个内部网格的温度为周围网格温度的均值。

而中间过程，则随着模拟的顺序和方式的不同会不同。