简单并行计算

要求

一个计算任务：

• 可以很容易地分为诸多小组
• 每个组完全独立的部分，
• 每个部分使用一个处理器完成。
• 各个进程之间的通信很少
• 自然并行

基本模式

示例

1. 像素的平移旋转缩放
   1. 复杂度分析
      1. 串行O(n^2)
      2. 并行O(n^2 + p + n^2/p)
         1. 通信复杂度
            1. 总线程scatter:O(p)
            2. 工作线程上传:O(n^2)
         2. 计算复杂度O(n^2/p)
   2. 加速比
      1. 加速比为1,没有加速
      2. 原因:通信复杂度

通信方式

• 主进程：
  • 发送：
    • 使用阻塞的，标准的即缓冲的发送。发送能够立刻返回，只要不去更改发送到变量，其发送工作能够在后台完成，也无需wait或test。
  • 接受：
    • 使用阻塞的接收，但往往可以指定Pany，即从任意进程接收。不至于因为某子进程的延误而耽搁其他进程。
• 从进程：
  • 接受：
    • 使用阻塞的接受
  • 发送：
    • 使用阻塞的缓冲的发送，同样不要去改变发送变量。

动态任务分配

简单并行计算基本模式的问题

1. 子进程每次发送一个节点，效率低。
   • 考虑按组发送。
2. 服务器阻塞在接收进程上，
   • 可考虑使用非阻塞的方式。
3. 每个点的计算次数不相同。但是事先并不清楚。计算节点的计算能力亦不相同。 计算效率以最慢点节点为准。
   • 动态任务分配

概念

工作池，处理器农庄。 线程池，进程池。

进程向工作池请求任务，取走任务，计算，提交结果，再次请求任务。

示例

1. Mandelbrot集合
   • 混沌和分形
   • 是自然界的普适现象。其根本规律仍然在研究中。 （Feigenbaum Constant ） 费根鲍姆常数。
   • Manderbrot集合以一种简单的方式揭示了自然界的奇妙现象。
   • 
   • 基本算法：

     1. **已知复平面上的点c，** 对其着色n，其颜色n的确定方法如下：
     2. 选定固定的模值a a>0
     3. 选定固定的初始点Z0
     4. 进行如下迭代Zk+1 =Zk^2+ c
     5. 直到超过迭代次数或者Zk的模超过a
     6. 记录下c的迭代次数n。
     7. 以某种事先确定的方式将n映射为颜色。
     8. 在二维平面上对c着色
     9. 对某区域中所有的点均作如上操作。
     10. 所得图像即Mandelbrot集合。
     

     1. Julia集合

        • 基本算法

        • 已知复平面上的点Z0， 对其着色n，其颜色n的确定方法如下：

        • 选定固定的模值a a>0
        • 选定固定的初始偏移点c
        • 进行如下迭代Zk+1 =Zk^2+ c
        • 直到超过迭代次数或者Zk的模超过a
        • 记录下Z0的迭代次数n。
        • 以某种事先确定的方式将n映射为颜色。
        • 在二维平面上对Z0着色
        • 对某区域中所有的点均作如上操作。
        • 所得图像即Julia集合。

Monte Carlo Method

每个处理器各自计算，求均值即可

应用

1. 计算pie

2. 随机方法计算定积分

   1. 定积分转换为求和
   2. 要求
      • 注意这里不是无限划分区间！ （面积积分是这种方法，见MPI计算Pi的例子）。
      • 随机性必须好。
      • 次数足够多。

Pie计算

• 面积积分
• 幂级数
• 改进的幂级数
• 蒙特卡罗方法
• 随机积分方法

并行伪随机数计算

• 假设有k个进程同时参加计算
• 算法：
  1. 先顺序计算出x1,x2,……. xk.
  2. 第i个进程（1<=i<=k) 负责完成 x_(n*k+i) 其中n=1，2，…… 的计算
     • x_(k+i)= （A_xi +C） mod m
     • 其中A=a^kmod m ，C=c（a^(k-1)+a^(k-2)+……+a+1)
     • 即X_(k+i) 用Xi 来表示。下标相隔k个，原始公式中下标只相隔1个
  3. x_(2k+i) , x_(3k+i)等 依次计算。（X_(2k+i) 与X_(k+I) 下标也相隔k个）
  4. 其他进程对不同的i 分别计算。由此实现并行计算。