StanFord CS149 Assignment4 简记

Github

Part 1

串行实现根据伪代码即可, 难度不大

并行化的部分也可以直接看代码

重点是其中一个 reduction 的操作

使用 reduction 而不是直接 parallel for 的原因是后者会不断对 global_diff 做原子操作, 而 reduction 效率更高

Part 2

朴素并行化

1. 在 top_down_step 下的第一个循环加上 #pragma omp parallel for
2. 把 访问 distance 的部分加上 #pragma omp critical

优化

注意到 new_frontier->count 这个变量被访问很多次, 不断进行原子自增操作

可以拆分, 每个线程在本地做这些操作, 然后在最后通过 memcpy 和 __sync_fetch_and_add 与全局的信息做合并

优点: 每个线程多次访问 new_frontier->count 变成 每个线程只需要访问一次

Part 3

实现细节见代码

区别

1. top_down: 从 frontier 中向外探索
2. bottom_up 看所有的点是否是 frontier 中的后继结点

自底向上的优缺点

1. 优点
   • 写的时候只改变 distances[i], 不需要复杂的 CAS 操作
   • 看到一个满足条件的 frontier 就可以直接退出循环
   • 自己的 distance 不是 -1 的时候也可以退出循环
2. 缺点
   • 需要遍历所有的点, 计算量大

Part 4

综上所述

1. 如果 frontier 中点不多, 最好使用 top_down
2. 如果 frontier 中点很多, 那就不如使用 bottom_up

多不多的界限可以实验, 这里取 10000000 作为分界点