2021¶
IPCC Preliminary SLIC Optimization 6: Non-blocking MPI
非阻塞MPI
MPI_Send & MPI_receive
MPI_AllTogether()更慢，需要4s
手动向量化对齐
debug
发现不对劲，打印更多输出。第一次循环肯定是对的因为和DBL_MAX比较。
需要进一步的研究学习
为什么明明有56GB的IB网，传输速度还是这么慢呢？写比较慢？
7*8=56 8条通道
遇到的问题
暂无
开题缘由、总结、反思、吐槽~~
参考文献
无
Hybrid Multithreaded/OpenMP + MPI parallel Programs
混合编程需要注意的问题
https://www.nhr.kit.edu/userdocs/horeka/batch_slurm_mpi_multithread/ 看这个
还有个ppt 16
google hydrid openmpi openmp
intelmpi 编译
这里值得要注意的是，似乎直接用mpif90/mpicxx编译的库会报错，所以需要用
icc -openmp hello.cpp -o hello -DMPICH_IGNORE_CXX_SEEK -L/Path/to/mpi/lib/ -lmpi_mt -lmpiic -I/path/to/mpi/include 其中-DMPICH_IGNORE_CXX_SEEK为防止MPI2协议中一个重复定义问题所使用的选项，为了保证线程安全，必须使用mpi_mt库
对于intel的mpirun，必须在mpirun后加上-env I_MPI_PIN_DOMAIN omp使得每个mpi进程会启动openmp线程。
通过export OMP_NUM_THREADS来控制每个MPI产生多少线程。
OpenMPI 如何实现mult-thread(OpenMP)2
检查编译安装支持mult-thread
shell$ ompi_info | grep "Thread support"
Thread support: posix (MPI_THREAD_MULTIPLE: yes, OPAL support: yes, OMPI progress: no, Event lib: yes)
shell$
在C程序里支持mult-thread
#include <mpi.h>
int MPI_Init_thread(int *argc, char ***argv,
int required, int *provided)
argc
C/C++ only: Pointer to the number of arguments.
argv
C/C++ only: Argument vector.
required
Desired level of thread support (integer).
provided
Available level of thread support (integer).
MPI_THREAD_SINGLE
Only one thread will execute.
MPI_THREAD_FUNNELED
If the process is multithreaded, only the thread that called MPI_Init_thread will make MPI calls.
MPI_THREAD_SERIALIZED
If the process is multithreaded, only one thread will make MPI library calls at one time.
MPI_THREAD_MULTIPLE
If the process is multithreaded, multiple threads may call MPI at once with no restrictions.
注意
3.1.6的多线程支持还在初级阶段。开销很高（虽然我不知道为什么）
需要进一步的研究学习
学习MapReduce或者Hadoop？ pthread vs openmp?
遇到的问题
暂无
开题缘由、总结、反思、吐槽~~
参考文献
https://blog.csdn.net/Morizen/article/details/113863591
IPCC Preliminary SLIC Optimization 5: MPI + OpenMP
AMD
| 技术路线 | 描述 | 总时间 | 加速比 | 备注 |
|---|---|---|---|---|
| Baseline | 串行程序 | 161.7s s | 1 | |
| more3omp | 前面都是可以证明的有效优化 omp_num=32 | 14.08s | ||
| more3omp | 前面都是可以证明的有效优化 omp_num=64 | 11.4s | ||
| deletevector | 把sz大小的3个vector,移到全局变量，但是需要提前知道sz大小/声明一个特别大的 | 10.64s | 可以看出写成全局变量也不会影响访问时间 | |
| enforce_Lscan | IPCC opt 4 | 8.49s | 19 | |
| enforce_Lscan_MPI_intel | intel icpc | 3.8s | 42.36 | |
| Baseline2-max ppm | 1.2GB ppm 10*1024*40*1024 | 928s | ||
| enforce_Lscan | Baseline2 | 43.79s | 21.2 | |
| enforce_Lscan_MPI_intel | intel icpc + 双节点两个时间 + MPI(DoRGBtoLABConversion) | 18.8s / 20s | 46.4 | |
| enforce_Lscan_intel | intel icpc + 单节点 | 15.8s | 58.74 | MPI(DoRGBtoLABConversion)负优化了2s |
| manualSIMD | 13.9s | |||
| stream | 13.6s | |||
| vec2mallocOMP | 11.0s | |||
| mmap | 10.6s | |||
| + -O3 | enforce_Lscan_intel | 16.2s | ||
| + -xHost | 结果不对 | 17.8s | ||
| -Ofast | 16.9s | |||
| -ipo | 15.9s | |||
| -O3 -ipo | 16.8s | |||
| -O3 -march=core-avx2 -fma -ftz -fomit-frame-pointer | 16.0s | |||
| g++ suggested options | -O3 -march-znver1 -mtune=znver1 -fma -mavx2 -m3dnow -fomit-frame-pointer | 18.1s | ||
| g++ suggested options2 | -O3 -march-znver2 -mtune=znver2 -fma -mavx2 -m3dnow -fomit-frame-pointer | 19.79s | ||
| g++ -Ofast | 16.9s | |||
| aocc -Ofast | 16.3s | |||
| aocc suggested options | 16.2s |
MPI编程
由于是打算两节点两进程MPI，虽然没有OpenMP的共享内存，但是也希望通信能少一点。
PerformSuperpixelSegmentation_VariableSandM
下面关于同步区域的想法是错误的： 因为中心点移动会十分不确定，所以全部同步是最好的。
- 第一部分core的思路
- 上面numk个中心点直接一分为2，需要同步的是中间相连的\(\(width*(3S)\)\)个中心点(由于PerturbSeeds扰动，而且offset比较大，应该是中间相邻的2排，大约3S的高度的区域,上下1.5S高度)。
- distlab需要后面覆盖前面的(当然是计算了的区域)。klabels是取distvec更小对应的那个，应该要写个自定义归约。
- numk个中心点有奇数行和偶数行，经过思考后是一样的。
- 第二部分各中心maxlab的思路（从sz里提取numk个中心的数据）
- sz直接一分为2,最小同步的话，就是中间相邻中心点maxlab要max归约。
- 第三部分计算sz里的numk个中心点的质心和
- 同理，sz直接一分为2，vector相加归约同步
DoRGBtoLABConversion 0.61s
用MPI_Send写，但是一开始没注意是阻塞的，但是为什么这么慢呢？
对比之前的enforce_Lscan 8.49s
- DoRGBtoLABConversion 0.56s
- PerformSuperpixelSegmentation_VariableSandM 5.52s
- core 0.53s
- maxlab 0.02s
- sigma 0.03s
- DetectLabEdges 0.31s
- EnforceLabelConnectivity 1.19s
- PerformSuperpixelSegmentation_VariableSandM 0.88s
慢了10~20倍猜测：
1. printf的原因？ no 不打印也一样
2. omp_num的值不对？ maybe no
3. 不在两个节点上？ no 
4. g++ mpicxx? no
5. 没有用IB ？ 貌似也不是
6. openmpi不支持openmp ? 探究方向
好像是openmp没正常运行omp_num的值为 1，32，64时间都一样。感觉是混合编程的编译问题， 而且好像是假Openmp并行，哪里有锁的样子。突然想起来，Quest的混合变成cmake需要打开multthread类似的支持，但是这里并没用。
好像也不是mpi_init_thread的问题
尝试intelmpi
果然有奇效。(结果是对的，后面我没截图了)。看到这里，可能你会觉得这个问题是OpenMPI有地方不支持openmp。但是后面有神奇的事情，如果NODELIST是fa,而不是fb就不能跑，会直接卡住。😰
首先没找到官方手册说明不同，然后研究一下这两个分区的不同。好吧从IB,cpu,内存都没区别。
限制nodelist再跑一遍。
加上打印时间，用fb分区
这个问题又没有了,但是fa分区由于经常跑可能会热一些。
最大的ppm例子
由于时间已经进5s了。所以我们需要更大的例子，再讨论2节点的开销收益，之前的例子是256034000。
这里生成了1024040960的ppm.再大ppm程序的数组都申请不到栈空间了,需要重新数据结构。
重跑当前最快的enforce_Lscan
icpc + enforce_Lscan_MPI(DoRGBtoLABConversion)
icpc + enforce_Lscan
g++ suggested options
icpc + manualSIMD + lessLscan
icpc + manualSIMD + LscanSimple
icpc + manualSIMD + LscanSimple + stream
icpc + manualSIMD + LscanSimple + stream + mallocOMPinit
icpc + manualSIMD + LscanSimple + stream + mallocOMPinit + mmap
icpc + manualSIMD + LscanSimple + stream + mallocOMPinit + mmap + unrollLoop
放弃的原因
https://www.bilibili.com/video/BV1a44y1q782 58mins-58min50s
需要进一步的研究学习
暂无
遇到的问题
- 混合编程写的有问题，双节点不快反慢。怎么写呢？
- 那段串行代码真的不能并行吗？
- 向量化为什么没有提升呢，是要循环展开吗？
姜师兄建议
- MPI非阻塞通信 gather reduce
- 手动向量化
开题缘由、总结、反思、吐槽~~
参考文献
无
IPCC Preliminary SLIC Optimization 4: EnforceLabelConnectivity
node5/6
| 技术路线 | 描述 | 总时间 | 加速比 | 备注 |
|---|---|---|---|---|
| Baseline | 串行程序 | 207 s | 1 | |
| more3omp | 0.4+5+0.3 | 23.0s | ||
| 时间细划，初始化omp | 0.03+5+0.1 | 21.2s | ||
| 不换算法，必须加锁 | 特别满 | |||
| 扫描行算法 | 0.03+2.2+0.1 | 18.5s | ||
| 扫描行算法 + task动态线程池 | 26s | |||
| 扫描行算法 + task动态线程池 + 延迟发射 | 26s | |||
| 扫描行算法 + task动态线程池 + 延迟发射 | 26s | |||
| 扫描行算法 + 化解重复，提高粒度：每个线程一行，不同线程杜绝同一行扫描行算法 | 但是没并行起来 | 106s | ||
| 扫描行算法 + 常驻64线程 | 86s | |||
| ## 初始时间 | ||||
| ## 时间细划，初始化omp | ||||
| 细致划分,malloc size大小的空间不耗时，是初始化为-1耗时 | ||||
| 修改后 | ||||
| ## 改 dx4，dy4 实现访存连续性 | ||||
| 但是可能会导致adjlabel的值不对，导致结果不对 |
flood fill
openmp线程池+不加锁
4分钟+, 满核结束不了，已经混乱了。
openmp线程池+加锁（单/多个）
5分钟+，满核结束不了，大翻车。
可能的原因： 1. 本来不是计算密集型，加锁导致是串行，而且还有sz次锁的获取与释放的开销。 2. 某个线程改了nlabels，其余运行时读取可能还要同步修改。
我又想到是不是只有一个锁，有没有多个锁的实现。还是超时结束不了。
omp_set_lock(&lock[nindex]); //获得互斥器
if( 0 > nlabels[nindex] && labels[oindex] == labels[nindex] )
{
xvec[count] = x;
yvec[count] = y;
nlabels[nindex] = label;
count++;
}
omp_unset_lock(&lock[nindex]); //释放互斥器
openmp线程池+队列+(不)加锁
好耶，segmentation fault (core dumped)。果然读到外面去了。
不好耶了，并行的地方加了锁，还是会
debug 不加锁
200~400行不等seg fault。
debug 加锁
然后我打了时间戳
可以看出至少前面是正常的。
多运行几次，有时候segfault，有时corruption，我服了。
但是位置好像还是在上面的循环
每次报错位置还不一样，但是迭代的点还是对的。
队列的原子性操作需要自己加锁定义
https://stackoverflow.com/questions/32227321/atomic-operation-on-queuet
openmpfor+双队列+(不)加锁
黑人问号？纳尼没办法，只能加锁，读取，写入都加锁，但是就是特别慢,4分钟+。
omp_set_lock(&lock); //获得互斥器
qindex = workq.front();
workq.pop();
omp_unset_lock(&lock); //释放互斥器
omp_set_lock(&lock2); //获得互斥器
if( 0 > nlabels[nindex] && labels[oindex] == labels[nindex] )
{
nlabels[nindex] = label;
workq2.push(nindex);
saveq.push(nindex);
}
omp_unset_lock(&lock2); //释放互斥器
队列换成栈是一样的
q.front()变成了q.top()
扫描行实现
扫描线算法至少比每像素算法快一个数量级。
Time taken is 16.144375 13.062605 PerformSuperpixelSegmentation_VariableSandM 循环
Time taken is 16.144399 0.000025 EnforceLabelConnectivity numlable
Time taken is 16.177300 0.032901 EnforceLabelConnectivity xvec yvec
Time taken is 48.978709 32.801409 EnforceLabelConnectivity iteration
Time taken is 49.086252 0.107543 EnforceLabelConnectivity klabelsComputing time=49086 ms
There are 86475718 points' labels are different from original file.
Time taken is 15.670141 0.000024 EnforceLabelConnectivity numlable
Time taken is 15.718014 0.047873 EnforceLabelConnectivity xvec yvec
Time taken is 22.103680 6.385666 EnforceLabelConnectivity iteration
Time taken is 22.219160 0.115480 EnforceLabelConnectivity klabelsComputing time=22219 ms
There are 0 points' labels are different from original file.
优化一下变量，快了3秒，大胜利！！！
Time taken is 16.203514 0.000029 EnforceLabelConnectivity numlable
Time taken is 16.234977 0.031463 EnforceLabelConnectivity xvec yvec
Time taken is 18.428990 2.194013 EnforceLabelConnectivity iteration
Time taken is 18.527664 0.098674 EnforceLabelConnectivity klabelsComputing time=18527 ms
There are 0 points' labels are different from original file.
扫描行并行实现 + 上下建线程，左右在线程里跑
用task写
虽然我在总结里写了，很难控制。但是，哎，我就是不信邪，就是玩😉
喜提segfault,打印task调用，发现task从上到下，之字形调用，而且没用一个结束的。按照设想，横向x增加比调用task快的，现在好像task堵塞的样子。
好像是没加,但是结果不对
让我们仔细分析一下是怎么偏离预期的：
1. (0,2)调用（0，3），（0，3）调用（0，4）很正常。但是（0，3）竟然调用了（2，4），这说明（0，3）循环到（1，3）时，发现（1，4）是已经处理的，而（2，4）是未处理的。进一步说明了（0，4）在被（0，3）创建了之后，先一步循环到（1，4），并将其处理。
2. （0，4）先循环到(1,4),反手还调用（1，3）。然后由于（0，3）调用了（2，4）。导致（0，4）循环到后面以为到（2，4）就截止了。
3. 虽然我说不出有什么问题，但是这不受控制的混乱调用，肯定不是我们想见的。
尝试把占用时间的print去掉。时间不短（重复调用），还是错的。(后面才发现，错误是threadcount，threadq里，每次循环完忘记清空了。日~)
Time taken is 16.226124 0.000024 EnforceLabelConnectivity numlable
Time taken is 16.258697 0.032573 EnforceLabelConnectivity xvec yvec
Time taken is 26.320222 10.061525 EnforceLabelConnectivity iteration
Time taken is 26.401399 0.081177 EnforceLabelConnectivity klabelsComputing time=26401 ms
There are 86588716 points' labels are different from original file.
Time taken is 15.743455 0.000025 EnforceLabelConnectivity numlable
Time taken is 15.773654 0.030198 EnforceLabelConnectivity xvec yvec
Time taken is 26.348979 10.575326 EnforceLabelConnectivity iteration
Time taken is 26.442129 0.093150 EnforceLabelConnectivity klabelsComputing time=26442 ms
There are 0 points' labels are different from original file.
延迟发射
- 把发射任务(x+delay,y)用队列存储，每次循环check一下，最后循环结束后，在全部发射。
- 或者标记(x+delay,y)发射(x,y)。但是对于循环结束后的，不好处理。
Time taken is 17.344073 0.000027 EnforceLabelConnectivity numlable
Time taken is 17.377535 0.033462 EnforceLabelConnectivity xvec yvec
Time taken is 28.461901 11.084366 EnforceLabelConnectivity iteration
Time taken is 28.544698 0.082797 EnforceLabelConnectivity klabelsComputing time=28544 ms
There are 86588716 points' labels are different from original file.
把delay的值从10调整到750,甚至是2600，大于宽度了，结果还是不对。这是不对劲的，因为这时相当于把对(x,y)一行都处理完，再发射task。
这时我才感觉到是其他地方写错了，错误是threadcount，threadq里，每次循环完忘记清空了。日~
delay = 2600 结果是对了，但是也太慢了，至少要比串行快啊？
Time taken is 15.538704 0.000026 EnforceLabelConnectivity numlable
Time taken is 15.577671 0.038968 EnforceLabelConnectivity xvec yvec
Time taken is 28.233859 12.656188 EnforceLabelConnectivity iteration
Time taken is 28.332256 0.098396 EnforceLabelConnectivity klabelsComputing time=28332 ms
delay = 20 快了一点，哭
Time taken is 15.631368 0.000025 EnforceLabelConnectivity numlable
Time taken is 15.661496 0.030128 EnforceLabelConnectivity xvec yvec
Time taken is 26.788105 11.126609 EnforceLabelConnectivity iteration
Time taken is 26.869487 0.081382 EnforceLabelConnectivity klabelsComputing time=26869 ms
There are 0 points' labels are different from original file.
逆向优化分析
-
打上时间戳
说明还是并行没写好。 -
检查是否调用64核,htop显示是64核
- 猜测原因
- 产生了大量重复的任务，还是划分的原因，上下限制了之后，左右的重复情况如何化解。
- 每个进程一行，task分配到y%64号线程去。但是openmp的task好像不能指定线程号。
- 任务压入第y%64个队列，线程从队列取任务。
- eg,第3行的后面两个线程，threadcount=0，无作用。
- 有许多任务量过小的情况，粒度不够，次数还多，导致调用产生的开销大
- task的线程池就是不靠谱
- 产生了大量重复的任务，还是划分的原因，上下限制了之后，左右的重复情况如何化解。
- 可以行分割或列分割，根据输入
化解重复，提高粒度：每个线程一行，不同线程杜绝同一行
- 任务压入第y%64个队列，线程从队列取任务。
- 但是这里同一队列的写入与读取又冲突了。可以用64个双队列，一写一读。在交换的时候等待+同步。
- 不同线程写入同一个也冲突，每个线程再来64个队列保存，同步的时候再汇总写入。
想法很美好，但是最后的效果并不是每次64线程，基本都只有1-5个任务。导致近似单线程还有调用开销。（node6有人，node5慢些）
Time taken is 36.212269 32.876626 PerformSuperpixelSegmentation_VariableSandM 循环
Time taken is 36.212297 0.000028 EnforceLabelConnectivity numlable
Time taken is 36.247536 0.035239 EnforceLabelConnectivity xvec yvec
Time taken is 106.097341 69.849805 EnforceLabelConnectivity iteration
Time taken is 106.204154 0.106813 EnforceLabelConnectivity klabelsComputing time=106204 ms
There are 0 points' labels are different from original file.
这个原因感觉是一开始只有1个，然后一般也就产生1/2个任务。将其初始任务改成64个就行。
但是如何一开始启动64个呢，我又提前不知道任务。
常驻64线程
写完又是segFault，debug 1. [64][64][10000]太大了，每次的队列应该没这么多[64][64][100] 2. 对于结束的统计，要用同步一下，需要加critical。结果就对了 但是，这也太慢了
Time taken is 28.219408 0.000017 EnforceLabelConnectivity numlable
Time taken is 28.271994 0.052586 EnforceLabelConnectivity xvec yvec
Time taken is 83.591540 55.319546 EnforceLabelConnectivity iteration
Time taken is 83.696990 0.105450 EnforceLabelConnectivity klabelsComputing time=83696 ms
There are 0 points' labels are different from original file.
受控的分段任务
没时间研究
openmpfor+特殊双数组(1+4?)
没时间研究
需要进一步的研究学习
感觉要自己写个结构体 1. 数据可以无序 2. 最好数据各异 3. 支持并行读每个元素（数组？ 4. 支持并行写一堆元素，并且维护size大小
遇到的问题
暂无
并行总结
在这次并行中，让我意识到几点 1. 任务的划分一定不能重复，相互干扰。比如，四邻域泛洪任务重复会导致竞争问题，需要加锁。但是，描绘线，任务不重复，直接避免了加锁的低效。而且重复会导致计算重复，同时占用线程。 2. 并行任务的结果，如果不是一定要存在同一个变量就分开存，既不需要线程私有变量，最后归约；也不会存同一个位置导致竞争。比如，这次的任务会产生一堆不相关的index，那直接每个线程一个数组存，既不会冲突，之后还能接着并行。或者用更大的sz大小数组存index，结果更不会冲突了。 3. 对于任务数增加且不确定的情况，不推荐使用task进程。因为自动调度很难控制，既不知道迭代了多少，也不确定之后会不会有隐藏的竞争。 推荐类似双队列的调度，确定一批任务，并行一批任务，同步一批任务的结果，然后重新并行。 1. 问题：中间并行一批任务的时候还是记得分开存结果。同步的时候再处理一下就行。 2. 双队列可能有任务量过少的问题，导致变单线程。 3. 想到了一种启动64常驻线程，产生任务又等待任务的结构。但是问题是：任务的保存要满足产生任务的写入和处理任务的读取。在不考虑写爆的情况(循环)，维护数组的写入与读取位置是可行的。任务的结束通过每个线程在读取不到任务时，判断自己发布的所有任务也被完成了，标记自己发布的任务完成了。所有发布的任务都完成，再结束。
好吧，我感觉我分析了一堆，就是在放屁。还是串行快，这个问题就难划分。就不是并行的算法。
编程总结
这次编程遇到的问题，大多数如下：
- 对每次循环开始时所以变量的清空，重新赋初值
- 结束时，全部清空。
参考文献
无
Dynamic pool dispatch
池调度的实现
需要： 1. 知道总进程/线程数， 2. 增加任务的api 3. 队列
网上的实现c++ : https://zhuanlan.zhihu.com/p/95819747
队列的一种实现
OpenMP 动态线程池调度
不知道 #pragma omp parallel for num_threads(ndata) schedule(dynamic)行不行
这个动态调度，和openmp的线程池的概念，让我感觉应该是有线程动态调度池的概念的，因为只要有个for子句加任务的api。但是for指令在进行并行执行之前，就需要”静态“的知道任务该如何划分。
for和sections指令的”缺陷“：无法根据运行时的环境动态的进行任务划分，必须是预先能知道的任务划分的情况。
所以OpenMP3.0提供task指令，主要适用于不规则的循环迭代和递归的函数调用。OpenMP遇到了task之后，就会使用当前的线程或者延迟一会后使用其他的线程来执行task定义的任务。
#pragma omp parallel num_threads(2)
{
#pragma omp single
{
for(int i = 0;i < N; i=i+a[i])
{
#pragma omp task
task(a[i]);
}
}
}
#pragma omp single
{
i = 0;
while (i < p.n)
{
for (; i < p.n; ++i)
{
#pragma omp task
DoSomething(p, i);
}
#pragma omp taskwait
#pragma omp flush
}
}
int count(1);
#pragma omp parallel num_threads(64)
{
#pragma omp single
{
int c = 0;
while(c < count)
{
for( ; c < count; c++ )
{
#pragma omp task{
for( int n = 0; n < 4; n++ )
{
int x = xvec[c] + dx4[n];
int y = yvec[c] + dy4[n];
if( (x >= 0 && x < width) && (y >= 0 && y < height) )
{
int nindex = y*width + x;
if( 0 > nlabels[nindex] && labels[oindex] == labels[nindex] )
{
xvec[count] = x;
yvec[count] = y;
nlabels[nindex] = label;
count++;
}
}
}
}
}
#pragma omp taskwait
#pragma omp flush
}
}
}
MPI 动态进程池调度
python的多进程里有动态进程管理
池调度的存在意义
我感觉，意义在于对于完全不相关的，或者没有顺序关系的任务，可以用池调度来并行。
C++与OpenMP配合的for子句最简线程池
实现每个线程执行完全不同的任务
#include <iostream>
#include <functional>
#include <vector>
using namespace std;
void fun (int a, int b)
{
cout<< "fun exec :"<< a << '+' << b << '=' << a + b <<endl;
}
class C{
private:
float m_c = 2.0f;
public:
void mp( float d)
{
cout<<"c::mp exec :"<< m_c << 'x' << d << '=' << m_c * d <<endl;
}
};
int main(int argc, char * argv[])
{
const int task_groups = 5;
C c [task_groups];
vector<function<void (void) > > tasks;
for (int i=0;i<task_groups;++i)
{
tasks.push_back(bind( fun , 10, i * 10 ) );
tasks.push_back(bind( &C::mp , &c[i], i*2.0f ) );
tasks.push_back(bind(
[=] (void) {cout << "lambada :" <<i << endl; }
) );
}
size_t sz = tasks.size();
#pragma omp parallel for
for (size_t i=0;i<sz;++i)
{
tasks[i]();
}
return 0;
}
输出：
fun exec :10+0=10
c::mp exec :2x0=0
lambada :0
fun exec :10+10=20
c::mp exec :2x2=4
lambada :1
fun exec :10+20=30
c::mp exec :2x4=8
lambada :2
fun exec :10+30=40
c::mp exec :2x6=12
lambada :3
fun exec :10+40=50
c::mp exec :2x8=16
lambada :4
当然可以根据 num_threads 和 omp_get_thread_num()实现不同线程执行完全不同类型任务
#pragma omp parallel num_threads(2)
{
int i = omp_get_thread_num();
if (i == 0){
do_long(data1, sub_threads);
}
if (i == 1 || omp_get_num_threads() != 2){
do_long(data2, sub_threads);
}
}
void do_long(int threads) {
#pragma omp parallel for num_threads(threads)
for(...) {
// do proccessing
}
}
int main(){
omp_set_nested(1);
int threads = 8;
int sub_threads = (threads + 1) / 2;
#pragma omp parallel num_threads(2)
{
int i = omp_get_thread_num();
if (i == 0){
do_long(data1, sub_threads);
}
if (i == 1 || omp_get_num_threads() != 2){
do_long(data2, sub_threads);
}
}
return 0;
}
需要进一步的研究学习
openmp 对不同的子句的关系种类没弄清。
遇到的问题
暂无
开题缘由、总结、反思、吐槽~~
对于for循环次数增加的情况，这么处理呢。
OpenMP由于是fork/join结构，fork的线程数可以一开始设置，但是for循环任务总数是一开始固定的吗？还是可以中途增加，
参考文献
https://www.it1352.com/359097.html
https://blog.csdn.net/gengshenghong/article/details/7004594
Parallel BFS
常规广度优先搜索的局限性
简单bfs是每次从队列中取出当前的访问节点后，之后就将它的邻接节点加入到队列中，这样明显不利于并行化。
实现一： 两队列
使用了两个队列，第一个队列存当前同一层的节点，第二个队列用来存储当前层节点的所有邻接节点(下一层节点)，等到当前层的节点全部访问完毕后，再将第一个队列与第二个队列进行交换，即可。
这样做的优势在于便于以后的并行化。同一层的节点可以一起运行，不会受到下一层节点的干扰。
但是写有问题，并行计算要储存下一层节点时，push操作不是原子的，需要加锁。
q1.push(1);
distance[1]=0;
while(!q1.empty()){
clear(q2);
for(int i=0;i<q1.size();i++){
int node=q1.front();
q1.pop();
cout<<node<<"->";
int start_edge=g.outgoing_starts[node];
int end_edge=(node==g.num_nodes-1)?g.num_edges:g.outgoing_starts[node+1];
for(int j=start_edge;j<end_edge;j++){
int outgoing=g.outgoing_edges[j];
if(distance[outgoing]==-1){
distance[outgoing]=1;
q2.push(outgoing);
}
}
}
swap(q1, q2);
}
实现二：PBFS
思想和实现一一样，但是对并行时竞争情况有处理。
思想：都是将并行处理的一层节点bag的相邻节点存到下一次处理的bag中。
竞争：
- 第 18 行的 v.dist 更新为 d+1。
- 幸运的是，由于都是设置为同一个值，该竞争不影响结果。
- 第19行，可能同时将同一个节点加入out-bag,导致额外的工作
- 但是这个bag数据结构是具有元素各异的性质，正好解决这个问题。
- 根本没有元素各异好吧。
- 第19行，可能同时将同一个节点加入out-bag,不会写同一个地方吗？insert
最后还是要加锁，屮。
辅助数据结构 - pennant
辅助数据结构，称为 "pennant"， 是一个\(2^k\)个节点的特殊树。根只有个left子节点，该子节点有个完整是二叉树。
通过这个辅助数据结构，可以实现动态无序集的 bag 数据结构
注意，普通的k层完全二叉树，有\(\(1+2+4+2^{k-1}=2^k-1\)\)个节点。
数据结构 - bags
bag是pennant的集合，其中没有相同大小的pennant。PBFS采用固定大小的数组S[0...r]称作 backbone 骨干。
数组中的第k元素S[k]为空或者保存着指向大小为\(2k\)的pennant。可知，整个数组S[0...r]最多保存\(2\)元素。
所以BAG-CREATE分配了保存空指针固定大小的数组backbone,会花费Θ(r)时间。
This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.
BAG-Insert类似二进制计数器递增的过程
BAG-INSERT(S,x)
1 k = 0
2 while S[k] != NULL
3 x = PENNANT-UNION(S[k],x)
4 S[k++] = NULL
5 S[k] = x #不执行循环 S[0] = x,不是在图7这种插入。
其中FA(x,y,z)相当于三个数的加法，c是进位，s是余位。
函数解释
函数时间开销
BAG-CREATE O(1) BAG-INSERT(n) O(1)-O(lgn) BAG-UNION(n) ~O(lgn)
函数时间开销
需要进一步的研究学习
暂无
遇到的问题
PBFS: 1. 11行为什么是lg呢，全部遍历不好吗？ 1. 因为存的是\(2^r\)的元素
This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.
开题缘由、总结、反思、吐槽~~
flood fill的需要
参考文献
https://www.cnblogs.com/JsonZhangAA/p/9016896.html
https://zhuanlan.zhihu.com/p/134637247
A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) from ACM SPAA 2010
Flood fill Algorithm
算法介绍
泛洪算法——Flood Fill，（也称为种子填充——Seed Fill，其中基于栈/队列的显式实现（有时称为“Forest Fire算法”））是一种算法，用于确定连接到多维数组中给定节点的区域。用于填充具有不同颜色的连接的，颜色相似的区域。泛洪算法的基本原理就是从一个像素点出发，以此向周边的像素点扩充着色，直到图形的边界。
算法参数及特点
参数：
- 起始节点（start node）
- 目标颜色（target color）
- 替换颜色（replacement color）
数据结构：
明确地或隐式地使用队列或堆栈数据结构。
常见实现
四邻域泛洪
将像素点(x,y)周围的上下左右四个点分别进行着色。
八邻域泛洪
将一个像素点的上下左右，左上，左下，右上，右下都进行着色。
描绘线算法(Scanline Fill)
（我感觉就是满足访存局部性原理，然后就快一些
void floodFillScanline(int x, int y, int newColor, int oldColor){
if(newColor==oldColor) return;
if(screen[x][y]!=oldColor) return;
emptyStack();
int x1;
bool spanAbove, spanBelow;
if(!push(x,y)) return;
while(pop(x,y)){
x1=x;
while(x1>0&&screen[x1][y]==oldColor) x1--;
x1++;
spanAbove = spanBelow = 0;
while(x1<w&&screen[x1][y]==oldColor){
screen[x1][y]=newColor;
if(!spanAbove&&y>0&&screen[x1][y-1]==oldColor){ //这里判断出了上行的元素可以被染色，可能为了修改screen的访存连续性，所以这里没修改。而且你改了上行的值，却没考虑其四周，会有完备性的问题。
if(!push(x1,y-1)) return;
spanAbove=1;
}
else if(spanAbove&&y>0&&screen[x1][y-1]!=oldColor){
spanAbove=0; //不压入重复过多的元素
}
if(!spanBelow&&y<h-1&&screen[x1][y+1]==oldColor){
if(!push(x1,y+1)) return;
spanBelow=1;
}
else if(spanBelow&&y<h-1&&screen[x1][y+1]!=oldColor){
spanBelow=0;
}
x1++;
}
}
}
但是程序是上下行同时入栈/队列，写成两个，先pop一个，访存更好。
描绘线算法(Scanline Fill)的并行实现
直接将push变成用新线程重新调用程序task。
讨论数据冲突(IPCC)
每行各自修改自己行screen，不会冲突。 访问隔壁行screen，但是只在意oldColor，对是否染色不关心。？
记录修改过的数据，是每个线程每行中的连续一个范围，index1~index2。由于每个线程的任务变成每行，任务量多了，这里加个锁，应该不会影响性能，维护一个行数大小的数组，每个元素存每行被标记的index,要不要有序呢?这主要看cache页能不能存下一行。然后后面还原就可以对每行omp,保证访存连续性。但这不是最优的，详见ipcc10总结。
大规模行为（Large-scale behaviour）
以数据为中心（data-centric）
小并行，每个像素一次检查4个或者8个
以流程为中心（process-centric）
使用堆栈。使用邻接技术和堆栈作为其种子像素存储的4路泛洪填充算法产生具有“后续填充的间隙”行为的线性填充。 这种方法尤其适用于较旧的8位计算机游戏。
需要进一步的研究学习
最后的以流程为中心方法没懂，怎么实现
并行BFS(广度优先搜索)
遇到的问题
暂无
开题缘由、总结、反思、吐槽~~
IPCC 初赛 EnforceLabelConnectivity函数需要改成并行的图填充算法
参考文献
https://www.pianshen.com/article/172962944/
IPCC Preliminary SLIC Optimization 3
node6
因为例子太小，导致之前的分析时间波动太大。所以写了个了大一点的例子，而且给每个函数加上了时间的输出，好分析是否有加速。(Qrz,node5有人在用。
| 技术路线 | 描述 | 总时间 | 加速比 | 备注 |
|---|---|---|---|---|
| Baseline | 串行程序 | 207 s | 1 | |
| simpleomp | 两处omp | 57s | ||
| more1omp | maxlab | 48s | ||
| more2omp | sigma + delete maxxy | 24.8s | 8.35 | |
| more3omp | DetectLabEdges + EnforceLabelConnectivity(该算法无法并行) | 21.2s | ||
| icpc | 13.4s | |||
| + -O3 | 13.2s | |||
| + -xHost | 13.09s | |||
| + -Ofast -xHost | 基于icpc | 12.97s | ||
| + -ipo | 12.73s | 16.26 | ||
| -no-prec-div -static -fp-model fast=2 | 14.2s | 时间还多了，具体其他选项需要到AMD机器上试 | ||
| ### Baseline 207s | ||||
| 1. DoRGBtoLABConversion 10.4s | ||||
| 2. PerformSuperpixelSegmentation_VariableSandM 187.3s | ||||
| 1. core 15.3s | ||||
| 2. maxlab 1s | ||||
| 3. sigma 2.3s | ||||
| ### simpleomp 57s | ||||
| 1. DoRGBtoLABConversion 0.89s | ||||
| 2. PerformSuperpixelSegmentation_VariableSandM 46s | ||||
| 1. core 0.94-1.8s | ||||
| 2. maxlab 1s | ||||
| 3. sigma 2.3-2.6s | ||||
| ### more1omp 48s | ||||
| 1. DoRGBtoLABConversion 0.82s | ||||
| 2. PerformSuperpixelSegmentation_VariableSandM 37s | ||||
| 1. core 1-2.3s | ||||
| 2. maxlab 0.04-0.1s | ||||
| 3. sigma 2.3s | ||||
| ### more2omp 24.8s | ||||
| 1. DoRGBtoLABConversion 0.85s | ||||
| 2. PerformSuperpixelSegmentation_VariableSandM 13.5s | ||||
| 1. core 0.8-1.7s | ||||
| 2. maxlab 0.02-0.1s | ||||
| 3. sigma 0.1s | ||||
| 3. DetectLabEdges 3.7s | ||||
| 4. EnforceLabelConnectivity 5.2s |
more2omp 21.2s
- DoRGBtoLABConversion 0.74s
- PerformSuperpixelSegmentation_VariableSandM 12.3s
- core 1.1s
- maxlab 0.02-0.1s
- sigma 0.1s
- DetectLabEdges 0.7s
- EnforceLabelConnectivity 5.8s (需要换算法
- PerformSuperpixelSegmentation_VariableSandM (vector声明的时间,可以考虑拿到外面去） 1.6s
icpc 13.4s
- DoRGBtoLABConversion 0.44s
- PerformSuperpixelSegmentation_VariableSandM 8.49s
- core 0.5-1.1s
- maxlab 0.04s
- sigma 0.05s
- DetectLabEdges 0.54s
- EnforceLabelConnectivity 2.79s (需要换算法
- PerformSuperpixelSegmentation_VariableSandM (vector声明的时间,可以考虑拿到外面去） 1.16s
12.7s
- DoRGBtoLABConversion 0.42s
- PerformSuperpixelSegmentation_VariableSandM 7.98s
- core 0.5-1.1s
- maxlab 0.04s
- sigma 0.05s
- DetectLabEdges 0.49s
- EnforceLabelConnectivity 2.69s (需要换算法
- PerformSuperpixelSegmentation_VariableSandM (vector声明的时间,可以考虑拿到外面去） 1.13s
IPCC AMD
| 技术路线 | 描述 | 总时间 | 加速比 | 备注 |
|---|---|---|---|---|
| Baseline | 串行程序 | 161.7s s | 1 | |
| more3omp | 前面都是可以证明的有效优化 omp_num=32 | 14.08s | ||
| more3omp | 前面都是可以证明的有效优化 omp_num=64 | 11.4s | ||
| deletevector | 把sz大小的3个vector,移到全局变量，但是需要提前知道sz大小/声明一个特别大的 | 10.64s | 可以看出写成全局变量也不会影响访问时间 | |
| enforce_Lscan | ipcc opt 4 | 8.49s | ||
| ### Baseline 161.7s | ||||
| 1. DoRGBtoLABConversion 11.5s | ||||
| 2. PerformSuperpixelSegmentation_VariableSandM 143s | ||||
| 1. core 11.5s | ||||
| 2. maxlab 0.8s | ||||
| 3. sigma 1.7s | ||||
| 3. DetectLabEdges 2.74s | ||||
| 4. EnforceLabelConnectivity 3.34s | ||||
| 5. PerformSuperpixelSegmentation_VariableSandM 1.11s |
more2omp 14.08s
- DoRGBtoLABConversion 0.69s
- PerformSuperpixelSegmentation_VariableSandM 8.08s
- core 0.73s
- maxlab 0.02s
- sigma 0.05s
- DetectLabEdges 0.37s
- EnforceLabelConnectivity 3.8s
- PerformSuperpixelSegmentation_VariableSandM 1.1s
more2omp 11.4s
- DoRGBtoLABConversion 0.61s
- PerformSuperpixelSegmentation_VariableSandM 5.86s
- core 0.53s
- maxlab 0.02s
- sigma 0.03s
- DetectLabEdges 0.33s
- EnforceLabelConnectivity 3.5s
- PerformSuperpixelSegmentation_VariableSandM 1.02s
deletevector 10.64s
- DoRGBtoLABConversion 0.59s
- PerformSuperpixelSegmentation_VariableSandM 5.75s
- core 0.53s
- maxlab 0.02s
- sigma 0.03s
- DetectLabEdges 0.41s
- EnforceLabelConnectivity 3.84s
- PerformSuperpixelSegmentation_VariableSandM 0s
enforce_Lscan 8.49s
- DoRGBtoLABConversion 0.56s
- PerformSuperpixelSegmentation_VariableSandM 5.52s
- core 0.53s
- maxlab 0.02s
- sigma 0.03s
- DetectLabEdges 0.31s
- EnforceLabelConnectivity 1.19s
- PerformSuperpixelSegmentation_VariableSandM 0.88s
需要进一步的研究学习
- 外面声明vector
- EnforceLabelConnectivity 换并行算法
- 数据结构要求：
- 保存已经染色区域的位置，之后可能要还原
- 可以无序，有序最好，会访存连续
- x,y或者index也行。还是xy好判断边界
- 是4分还是8分，既然有重复，记录来的方向/路径,只向某方向移动。4是符合理论的，8不和要求，2有情况不能全部遍历。
- 3分倒是可以，但是实现小麻烦
- 保存已经染色区域的位置，之后可能要还原
- flood fill 与 PBFS 特定结合
- openmp线程池+锁(sz 大小的两个数组存 x y，nlabels存新的分类结果)+计时声明与flood+把这些在sz声明放外面
- openmp线程池+队列(最后可以并行处理吧，要一个个pop?)+需要锁吗(这取决于队列的实现有没有靠计数器)
- openmpfor+双队列*4/2？+需要锁吗
- 扫描行实现 + 上下建线程，左右在线程里跑
- 多线程的访问存储连续性
- 队列/栈是怎么实现代码的，速度怎么样（写入读取push pop，还有size）
- 栈有size吗
- 在AMD机器加入MPI进行混合编程，运行2节点
遇到的问题
暂无
开题缘由、总结、反思、吐槽~~
参考文献
无
Git Lfs
安装
mkdir git-lfs | cd git-lfs
wget https://github.com/git-lfs/git-lfs/releases/tag/v2.13.3
tar -zxvf git
sudo ./install.sh
使用
git lfs install
git lfs track “*.rar” # 这个是要指定的大文件
git lfs track "*.txt" # 对一批，然后正常add commit
git add .gitattributes # 关联这个文件
git commit -m “aaa”
git 恢复
-
工作区修改了文件（add之前），但是发现文件是你不想修改的，或者修改错误的，执行git checkout - 文件名，在工作区把文件恢复到修改之前的状态;
-
工作区修改了文件，并且已经添加到缓存区（add之后，承之前），执行git reset HEAD文件名（HEAD表示最新的版本），此操作是把缓存区修改的内容返回到工作区，如果此时你还是不想修改此文件的话，就再次执行第一步操作，就可以恢复到文件修改前的状态;
-
已经把文件提交给了分支（commit之后，推之前），执行git reset - hard HEAD ^（HEAD ^表示上一个版本），或者先用git log查看已经提交的版本号，执行git reset - -hard版本号的ID，就可以恢复到之前的版本，此时工作区和缓存区也是干净的;
-
推的时候忽略文件的操作:(忽略大文件操作.gitignore不好使的时候），在commit提交之后push推之前，输入命令：
需要进一步的研究学习
暂无
遇到的问题
很搞笑的是node5的IPCC/SLIC我就是弄不好，明明是按照步骤来的。
开题缘由、总结、反思、吐槽~~
大于100MB的文件上传不了github
参考文献
无