分布式chap-6

埃拉托斯特尼筛法

串行算法

1. 列出 2 以后的所有序列：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. 标出序列中的第一个质数，也就是 2，序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 将剩下序列中，划摽 2 的倍数（用红色标出），序列变成：
   • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
4. 如果现在这个序列中最大数小于等于最后一个标出的素数的平方，那么剩下的序列中所有的数都是质数，否则回到第二步。

时间复杂度：（nlnlnn)

---

并行性来源

• 区域划分

  • 将数据分成几部分

  • 将计算步骤和数据关联

• 每个数组元素一个原始任务

实现并行

Making 3(A) parallel
Mark all multiples of k between k2 and n

    to

for all j where k2  j  n do
   if j mod k = 0 then
      mark j (it is not a prime)
   endif
endfor

Making 3(B) parallel
Find smallest unmarked number > k

to

Min-reduction (to find smallest unmarked number > k)

Broadcast (to get result to all tasks)

聚合的目标

• 合并任务
• 降低通信开销
• 平衡进程之间的计算

---

数据分解选项

• 交错（循环）

  • 易于确定每个索引的“所有者”
  • 导致此问题的负载不平衡

• 堵塞

  • 平衡负载
  • 易于标记倍数
  • 如果 n 不是 p 的倍数，则确定所有者更复杂

块划分选项

• 想要在 n 不是 p 的倍数时平衡工作量
• 每个进程得到 n/p 上界 或 n/p 下界 元素
• 寻求简单的表达
  • 查找给定所有者的低、高指数
  • 给定索引查找所有者

方式 1

• 让 r = n mod p
• 如果 r = 0，则所有块的大小相同
• 别的
  • 前 r 个块的大小为 n/p 上界
  • 剩余的 p-r 个块的大小为 n/p 下界

方式 2

• 进程 i 的第一个元素

• 进程 i 的最后一个元素

• 给出元素 j，求对应的进程号

比较（数值为运算次数）

Operations	Method 1	Method 2
Low index	4	2
High index	6	4
Owner	7	4

• 运算次数最少的选择第二个方法

块分解宏命令

#define BLOCK_LOW(id,p,n)  ((i)*(n)/(p))
#define BLOCK_HIGH(id,p,n) \
        (BLOCK_LOW((id)+1,p,n)-1)
#define BLOCK_SIZE(id,p,n) \
        (BLOCK_LOW((id)+1)-BLOCK_LOW(id))
#define BLOCK_OWNER(index,p,n) \
        (((p)*(index)+1)-1)/(n))

本地与全局索引

循环元素

分解影响实现

• 用于筛分的最大素数是$\sqrt{n}$
• 第一个进程有 n/p 下界 元素
• 如果 p < $\sqrt{n}$，那么第一个进程包含可以筛掉所有非素数的素数
• 第一个进程总是广播下一个筛选素数
• 不需要规约过程

快速标记

块分解允许与串行算法相同的标记：

j, j + k, j + 2k, j + 3k, …

来代替

对于块中的所有 j
如果 j mod k = 0 那么标记 j（它不是素数）

---

并行算法开发

广播函数 MPI_Bcast

int MPI_Bcast (
   void *buffer, /* Addr of 1st element */
   int count,    /* # elements to broadcast */
   MPI_Datatype datatype, /* Type of elements */
   int root,     /* ID of root process */
   MPI_Comm comm)  /* Communicator */

MPI_Bcast (&k, 1, MPI_INT, 0, MPI_COMM_WORLD);

任务通道图

分析

• $\chi$是标记一个单元格所需的时间
• 串行执行时间是$\chi$ n ln ln n
• 广播次数 ：$\sqrt{n}$ / $ln\sqrt{n}$
• 广播时间：$\lambda$ 乘 $\log$p 的上界
• 预计执行时间：

性能

• 执行串行算法
  确定 $\chi$ = 85.47 纳秒
• 执行系列广播
  确定 $\chi$ = 250 $\mu$sec

不同进程数执行时间

Processors	Predicted	Actual (sec)
1	24.900	24.900
2	12.721	13.011
3	8.843	9.039
4	6.768	7.055
5	5.794	5.993
6	4.964	5.159
7	4.371	4.687
8	3.927	4.222

改进

• 删除偶数
  • 将计算次数减半
  • 较大的 n 值可以自由的存储
• 每个过程都能找到自己筛选的素数
  • 将素数的计算复制到 $\sqrt{n}$
  • 消除广播
• 重组循环
  • 提高缓存命中率
    

优化比较