跳转至

Tutorials

  • 分类于 Tutorials
  • 需要 6 分钟阅读时间

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
## 初始时间 
Time taken is 21.364595 6.066717 EnforceLabelConnectivityComputing
## 时间细划，初始化omp
细致划分,malloc size大小的空间不耗时，是初始化为-1耗时 
Time taken is 16.963094 0.000025 EnforceLabelConnectivity   numlable
Time taken is 17.395982 0.432887 EnforceLabelConnectivity   xvec yvec
Time taken is 22.668060 5.272079 EnforceLabelConnectivity iteration
Time taken is 23.001499 0.333438 EnforceLabelConnectivity klabelsComputing
修改后 
Time taken is 16.063057 0.000026 EnforceLabelConnectivity       numlable
Time taken is 16.095485 0.032428 EnforceLabelConnectivity       xvec yvec
Time taken is 21.116599 5.021114 EnforceLabelConnectivity iteration
Time taken is 21.237874 0.121275 EnforceLabelConnectivity klabelsComputing
## 改 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]); //释放互斥器
多个锁满足了nlabels的竞争，但是count的竞争还是只能一个锁。除非将数组保存变成队列才有可能，因为没计数器了。

openmp线程池+队列+(不)加锁

好耶，segmentation fault (core dumped)。果然读到外面去了。

不好耶了，并行的地方加了锁，还是会 

double free or corruption (out) //内存越界之类的

debug 不加锁

200~400行不等seg fault。

debug 加锁

然后我打了时间戳 可以看出至少前面是正常的。 多运行几次，有时候segfault，有时corruption，我服了。 但是位置好像还是在上面的循环 每次报错位置还不一样，但是迭代的点还是对的。

队列的原子性操作需要自己加锁定义

https://stackoverflow.com/questions/32227321/atomic-operation-on-queuet

openmpfor+双队列+(不)加锁

munmap_chunk(): invalid pointer
黑人问号？纳尼

没办法，只能加锁，读取，写入都加锁，但是就是特别慢,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); //释放互斥器
读取，写入不是同一个队列，尝试用2个锁，还是特别慢，5分钟根本跑不完。

队列换成栈是一样的

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.
不知道哪里错了，需要debug。简单debug,发现小问题。 
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堵塞的样子。

好像是没加,但是结果不对 

#pragma omp parallel num_threads(64)
{
    #pragma omp single
让我们仔细分析一下是怎么偏离预期的： 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,y)一行都处理完，再发射task。或者采取延迟发射的。

延迟发射
  1. 把发射任务(x+delay,y)用队列存储，每次循环check一下，最后循环结束后，在全部发射。
  2. 或者标记(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的值太小。

把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.

逆向优化分析

  1. 打上时间戳 

    end Time 84 32839 taken is 0.000000 dxy4
end Time 84 32839 taken is 0.000000 threadcount
end Time 84 32839 taken is 0.031285 core
end Time 84 32839 taken is 0.000023 count
    说明还是并行没写好。

  2. 检查是否调用64核,htop显示是64核

  3. 猜测原因
    • 产生了大量重复的任务，还是划分的原因，上下限制了之后，左右的重复情况如何化解。
      • 每个进程一行，task分配到y%64号线程去。但是openmp的task好像不能指定线程号。
      • 任务压入第y%64个队列，线程从队列取任务。
      • eg,第3行的后面两个线程，threadcount=0，无作用。
    • 有许多任务量过小的情况，粒度不够，次数还多，导致调用产生的开销大
    • task的线程池就是不靠谱
  4. 可以行分割或列分割，根据输入

化解重复，提高粒度：每个线程一行，不同线程杜绝同一行

  • 任务压入第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常驻线程，产生任务又等待任务的结构。但是问题是：任务的保存要满足产生任务的写入和处理任务的读取。在不考虑写爆的情况(循环)，维护数组的写入与读取位置是可行的。任务的结束通过每个线程在读取不到任务时，判断自己发布的所有任务也被完成了，标记自己发布的任务完成了。所有发布的任务都完成，再结束。

好吧，我感觉我分析了一堆，就是在放屁。还是串行快，这个问题就难划分。就不是并行的算法。

编程总结

这次编程遇到的问题，大多数如下：

  1. 对每次循环开始时所以变量的清空，重新赋初值
  2. 结束时，全部清空。

参考文献

无

  • 分类于 Tutorials
  • 需要 3 分钟阅读时间

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]);
            }
        }
   }
另一个例子，DoSomething()，导致p.n可能会增加。taskwait是为了防止某个task导致p.n增加了，但是for循环已经结束的情况。 
#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 
      }
   }
}
但是中间的if判断以及内部入队列，需要原子操作（xvec写入x时，别的线程count++了）。这就属于串行BFS的局限性了，导致并行不起来。

MPI 动态进程池调度

python的多进程里有动态进程管理 

from mpi4py import MPI

池调度的存在意义

我感觉，意义在于对于完全不相关的，或者没有顺序关系的任务，可以用池调度来并行。

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

  • 分类于 Tutorials
  • 需要 2 分钟阅读时间

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

  1. DoRGBtoLABConversion 0.74s
  2. PerformSuperpixelSegmentation_VariableSandM 12.3s
  3. core 1.1s
  4. maxlab 0.02-0.1s
  5. sigma 0.1s
  6. DetectLabEdges 0.7s
  7. EnforceLabelConnectivity 5.8s (需要换算法
  8. PerformSuperpixelSegmentation_VariableSandM (vector声明的时间,可以考虑拿到外面去） 1.6s

icpc 13.4s

  1. DoRGBtoLABConversion 0.44s
  2. PerformSuperpixelSegmentation_VariableSandM 8.49s
  3. core 0.5-1.1s
  4. maxlab 0.04s
  5. sigma 0.05s
  6. DetectLabEdges 0.54s
  7. EnforceLabelConnectivity 2.79s (需要换算法
  8. PerformSuperpixelSegmentation_VariableSandM (vector声明的时间,可以考虑拿到外面去） 1.16s

12.7s

  1. DoRGBtoLABConversion 0.42s
  2. PerformSuperpixelSegmentation_VariableSandM 7.98s
  3. core 0.5-1.1s
  4. maxlab 0.04s
  5. sigma 0.05s
  6. DetectLabEdges 0.49s
  7. EnforceLabelConnectivity 2.69s (需要换算法
  8. 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

  1. DoRGBtoLABConversion 0.69s
  2. PerformSuperpixelSegmentation_VariableSandM 8.08s
  3. core 0.73s
  4. maxlab 0.02s
  5. sigma 0.05s
  6. DetectLabEdges 0.37s
  7. EnforceLabelConnectivity 3.8s
  8. PerformSuperpixelSegmentation_VariableSandM 1.1s

more2omp 11.4s

  1. DoRGBtoLABConversion 0.61s
  2. PerformSuperpixelSegmentation_VariableSandM 5.86s
  3. core 0.53s
  4. maxlab 0.02s
  5. sigma 0.03s
  6. DetectLabEdges 0.33s
  7. EnforceLabelConnectivity 3.5s
  8. PerformSuperpixelSegmentation_VariableSandM 1.02s

deletevector 10.64s

  1. DoRGBtoLABConversion 0.59s
  2. PerformSuperpixelSegmentation_VariableSandM 5.75s
  3. core 0.53s
  4. maxlab 0.02s
  5. sigma 0.03s
  6. DetectLabEdges 0.41s
  7. EnforceLabelConnectivity 3.84s
  8. PerformSuperpixelSegmentation_VariableSandM 0s

enforce_Lscan 8.49s

  1. DoRGBtoLABConversion 0.56s
  2. PerformSuperpixelSegmentation_VariableSandM 5.52s
  3. core 0.53s
  4. maxlab 0.02s
  5. sigma 0.03s
  6. DetectLabEdges 0.31s
  7. EnforceLabelConnectivity 1.19s
  8. PerformSuperpixelSegmentation_VariableSandM 0.88s

需要进一步的研究学习

  1. 外面声明vector
  2. EnforceLabelConnectivity 换并行算法
  3. 数据结构要求：
    1. 保存已经染色区域的位置，之后可能要还原
      1. 可以无序，有序最好，会访存连续
      2. x,y或者index也行。还是xy好判断边界
    2. 是4分还是8分，既然有重复，记录来的方向/路径,只向某方向移动。4是符合理论的，8不和要求，2有情况不能全部遍历。
    3. 3分倒是可以，但是实现小麻烦
  4. flood fill 与 PBFS 特定结合
  5. openmp线程池+锁(sz 大小的两个数组存 x y，nlabels存新的分类结果)+计时声明与flood+把这些在sz声明放外面
  6. openmp线程池+队列(最后可以并行处理吧，要一个个pop?)+需要锁吗(这取决于队列的实现有没有靠计数器)
  7. openmpfor+双队列*4/2？+需要锁吗
  8. 扫描行实现 + 上下建线程，左右在线程里跑
    1. 多线程的访问存储连续性
  9. 队列/栈是怎么实现代码的，速度怎么样（写入读取push pop，还有size）
  10. 栈有size吗
  11. 在AMD机器加入MPI进行混合编程，运行2节点

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

无

  • 分类于 Tutorials
  • 需要 1 分钟阅读时间

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推之前，输入命令： 

     git filter-branch --force --index-filter "git rm --cached --ignore-unmatch 有关文件"  --prune-empty --tag-name-filter cat -- --all # 如果git提示包含未提交的更改，需要再提交一下

 git commit --amend -CHEAD # 这个文件将会从你的提交记录里移除，并且以后commit都将不会再提交

 git push

需要进一步的研究学习

暂无

遇到的问题

很搞笑的是node5的IPCC/SLIC我就是弄不好，明明是按照步骤来的。

开题缘由、总结、反思、吐槽~~

大于100MB的文件上传不了github

参考文献

无

  • 分类于 Tutorials
  • 需要 2 分钟阅读时间

OpenMP Reductions

遇到竞争写情况怎么办

critical section

最简单的解决方案是通过声明一个critical部分来消除竞争。 

double result = 0;
#pragma omp parallel num_threads(ndata)
{
  double local_result;
  int num = omp_get_thread_num();
  if (num==0)      local_result = f(x);
  else if (num==1) local_result = g(x);
  else if (num==2) local_result = h(x);
#pragma omp critical
  result += local_result;
}

double result = 0;
#pragma omp parallel
{
   double local_result;
#pragma omp for
   for (i=0; i<N; i++) {
    local_result = f(x,i);
#pragma omp critical
   result += local_result;
} // end of for loop
}

原子操作/加锁

性能是不好的，变串行了 

#pragma omp atomic
 pi += sum;

static omp_lock_t lock;
void omp_init_lock(&lock)：初始化互斥器
void omp_destroy_lock(omp_lock*)：销毁互斥器
void omp_set_lock(omp_lock*)：获得互斥器
void omp_unset_lock(omp_lock*)：释放互斥器
void omp_test_lock(omp_lock*): 试图获得互斥器，如果获得成功则返回true，否则返回false

reduction clause 子句

将其添加到一个omp并行区域有如下效果。 * OpenMP将为每个线程制作一个reduction变量的副本，初始化为reduction操作的身份，例如\(1\)用于乘法。 * 然后，每个线程将其reduce到其本地变量中。 * 在并行区域结束时，本地结果被合并，再次使用reduction操作，合并到全局变量。

多个变量的情况

reduction(+:x,y,z)
reduction(+:array[:])

对于复杂结构体

如果代码过于复杂，还是建议复制全局变量来手工实现，最后再合并。 

//错误示例
double result,local_results[3];
#pragma omp parallel
{
  int num = omp_get_thread_num();
  if (num==0)      local_results[num] = f(x)
  else if (num==1) local_results[num] = g(x)
  else if (num==2) local_results[num] = h(x)
}
result = local_results[0]+local_results[1]+local_results[2]
虽然上面这段代码是正确的，但它可能是低效的，因为有一个叫做虚假共享的现象。即使线程写到不同的变量，这些变量也可能在同一个缓存线上。这意味着核心将浪费大量的时间和带宽来更新对方的缓存线副本。

可以通过给每个线程提供自己的缓存线来防止错误的共享。 

// 不是最好
double result,local_results[3][8];
#pragma omp parallel
{
  int num = omp_get_thread_num();
  if (num==0)      local_results[num][1] = f(x)
// et cetera
}
最好的方法给每个线程一个真正的局部变量，并在最后用一个critial部分对这些变量进行求和。 
double result = 0;
#pragma omp parallel
{
  double local_result;
  local_result = .....
#pragam omp critical
  result += local_result;
}

默认的归约操作

Arithmetic reductions: \(+,*,-,\max,\min\)

Logical operator reductions in C: & && | || ^

归约变量的初始值

初始化值大多是不言而喻的，比如加法的0和乘法的1。对于min和max，它们分别是该类型的最大和最小可表示值。

用户自定义reduction的声明与使用

语法结构如下 

#pragma omp declare reduction
    ( identifier : typelist : combiner )
    [initializer(initializer-expression)]
例子1: 取int最大 
int mymax(int r,int n) {
// r is the already reduced value
// n is the new value
  int m;
  if (n>r) {
    m = n;
  } else {
    m = r;
  }
  return m;
}
#pragma omp declare reduction \
  (rwz:int:omp_out=mymax(omp_out,omp_in)) \
  initializer(omp_priv=INT_MIN)
  m = INT_MIN;
#pragma omp parallel for reduction(rwz:m)
  for (int idata=0; idata<ndata; idata++)
    m = mymax(m,data[idata]);

openmp减法归约浮点运算有精度损失

如何对vector归约

累加

#include <algorithm>
#include <vector>

#pragma omp declare reduction(vec_float_plus : std::vector<float> : \
                              std::transform(omp_out.begin(), omp_out.end(), omp_in.begin(), omp_out.begin(), std::plus<float>())) \
                    initializer(omp_priv = decltype(omp_orig)(omp_orig.size()))

std::vector<float> res(n,0);
#pragma omp parallel for reduction(vec_float_plus : res)
for(size_t i=0; i<m; i++){
    res[...] += ...;
}
编辑：原始initializer很简单：initializer（omp_priv = omp_orig）。但是，如果原始副本没有全零，结果将是错误的。因此，我建议使用更复杂的initializer，它总是创建零元素向量。

求最大值

#pragma omp declare reduction(vec_double_max : std::vector<double> : \
                          std::transform(omp_out.begin(), omp_out.end(), omp_in.begin(), omp_out.begin(), [](double a, double b) {return std::max(a,b);}))     \
                    initializer(omp_priv = decltype(omp_orig)(omp_orig.size()))

#pragma omp parallel for reduction(vec_double_max:maxlab)
for( int i = 0; i < sz; i++ )
{
   maxlab[klabels[i]] = max(maxlab[klabels[i]],distlab[i]);
}

std::transform

在指定的范围内应用于给定的操作，并将结果存储在指定的另一个范围内。

需要进一步的研究学习

  1. 对vector的归约

  2. 泥菩萨: 你这么改，开-g，在vtune里面看汇编

泥菩萨: 看有没有vmm指令

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

写IPCC发现：openmp没想象中简单，

参考文献

https://stackoverflow.com/questions/43168661/openmp-and-reduction-on-stdvector

https://pages.tacc.utexas.edu/~eijkhout/pcse/html/omp-reduction.html

http://www.cplusplus.com/forum/general/201500/

  • 分类于 Tutorials
  • 需要 1 分钟阅读时间

AOCC

https://developer.amd.com/amd-aocc/

Install

cd <compdir>\
tar -xvf aocc-compiler-<ver>.tar
cd aocc-compiler-<ver>
bash install.sh
# It will install the compiler and displaythe AOCC setup instructions.

source <compdir>/setenv_AOCC.sh
# This will setup the shell environment for using AOCC C, C++, and Fortran compiler where the command is executed.

Using AOCC

Libraries

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://developer.amd.com/wp-content/resources/AOCC_57223_Install_Guide_Rev_3.1.pdf

  • 分类于 Tutorials
  • 需要 2 分钟阅读时间

AMD Epyc Compiler Options

AMD EPYC™ 7xx2-series Processors Compiler Options Quick Reference Guide

AOCC compiler (with Flang -Fortran Front-End)

Latest release: 2.1, Nov 2019

https://developer.amd.com/amd-aocc/Advanced

GNU compiler collection (gcc, g++, gfortran)

Intel compilers (icc, icpc, ifort)

amd prace guide

需要进一步的研究学习

  1. Amd uprof
  2. PGI compiler
  3. Numactl
  4. OMP_PROC_BIND=TRUE; OMP_PLACES=sockets

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://developer.amd.com/wordpress/media/2020/04/Compiler%20Options%20Quick%20Ref%20Guide%20for%20AMD%20EPYC%207xx2%20Series%20Processors.pdf

https://prace-ri.eu/wp-content/uploads/Best-Practice-Guide_AMD.pdf#page35

Prace guide

  • 分类于 Tutorials
  • 需要 2 分钟阅读时间

Intel Compile Options

Win与Linux的区别

选项区别

对于大部分选项，Intel编译器在Win上的格式为：/Qopt，那么对应于Lin上的选项是：-opt。禁用某一个选项的方式是/Qopt-和-opt-。

Intel的编译器、链接器等

在Win上，编译器为icl.exe，链接器为xilink.exe，VS的编译器为cl.exe，链接器为link.exe。

在Linux下，C编译器为icc，C++编译器为icpc（但是也可以使用icc编译C++文件），链接器为xild，打包为xiar，其余工具类似命名。

GNU的C编译器为gcc，C++编译器为g++，链接器为ld，打包为ar

并行化

-qopenmp

-qopenmp-simd

如果选项 O2 或更高版本有效，则启用 OpenMP* SIMD 编译。

-parallel

告诉自动并行程序为可以安全地并行执行的循环生成多线程代码。

要使用此选项，您还必须指定选项 O2 或 O3。 如果还指定了选项 O3，则此选项设置选项 [q 或 Q]opt-matmul。

-qopt-matmul

启用或禁用编译器生成的矩阵乘法（matmul）库调用。

向量化(SIMD指令集)

-xHost

必须至少与-O2一起使用，在Linux系统上，如果既不指定-x也不指定-m，则默认值为-msse2。

-fast

On macOS* systems: -ipo, -mdynamic-no-pic,-O3, -no-prec-div,-fp-model fast=2, and -xHost

On Windows* systems: /O3, /Qipo, /Qprec-div-, /fp:fast=2, and /QxHost

On Linux* systems: -ipo, -O3, -no-prec-div,-static, -fp-model fast=2, and -xHost

指定选项 fast 后，您可以通过在命令行上指定不同的特定于处理器的 [Q]x 选项来覆盖 [Q]xHost 选项设置。但是，命令行上指定的最后一个选项优先。

-march

必须至少与-O2一起使用，如果同时指定 -ax 和 -march 选项，编译器将不会生成特定于 Intel 的指令。

指定 -march=pentium4 设置 -mtune=pentium4。

-x

告诉编译器它可以针对哪些处理器功能，包括它可以生成哪些指令集和优化。

AMBERLAKE
BROADWELL
CANNONLAKE
CASCADELAKE
COFFEELAKE
GOLDMONT
GOLDMONT-PLUS
HASWELL
ICELAKE-CLIENT (or ICELAKE)
ICELAKE-SERVER
IVYBRIDGE
KABYLAKE
KNL
KNM
SANDYBRIDGE
SILVERMONT
SKYLAKE
SKYLAKE-AVX512
TREMONT
WHISKEYLAKE

-m

告诉编译器它可能针对哪些功能，包括它可能生成的指令集。

-ax

生成基于多个指令集的代码。

HLO

High-level Optimizations，高级(别)优化。O1不属于

-O2

更广泛的优化。英特尔推荐通用。

在O2和更高级别启用矢量化。

在使用IA-32体系结构的系统上：执行一些基本的循环优化，例如分发、谓词Opt、交换、多版本控制和标量替换。

此选项还支持：

内部函数的内联
文件内过程间优化，包括：
   内联
   恒定传播
   正向替代
   常规属性传播
   可变地址分析
   死静态函数消除
   删除未引用变量
以下性能增益功能：
   恒定传播
   复制传播
   死码消除
   全局寄存器分配
   全局指令调度与控制推测
   循环展开
   优化代码选择
   部分冗余消除
   强度折减/诱导变量简化
   变量重命名
   异常处理优化
   尾部递归
   窥视孔优化
   结构分配降低与优化
   死区消除

-O3

O3选项对循环转换(loop transformations)进行更好的处理来优化内存访问。

比-O2更激进，编译时间更长。建议用于涉及密集浮点计算的循环代码。

既执行O2优化，并支持更积极的循环转换，如Fusion、Block Unroll和Jam以及Collasing IF语句。

此选项可以设置其他选项。这由编译器决定，具体取决于您使用的操作系统和体系结构。设置的选项可能会因版本而异。

当O3与options-ax或-x（Linux）或options/Qax或/Qx（Windows）一起使用时，编译器执行的数据依赖性分析比O2更严格，这可能会导致更长的编译时间。

O3优化可能不会导致更高的性能，除非发生循环和内存访问转换。在某些情况下，与O2优化相比，优化可能会减慢代码的速度。

O3选项建议用于循环大量使用浮点计算和处理大型数据集的应用程序。

与非英特尔微处理器相比，共享库中的许多例程针对英特尔微处理器进行了高度优化。

-Ofast

-O3 plus some extras.

IPO

Interprocedural Optimizations，过程间优化。

典型优化措施包括：过程内嵌与重新排序、消除死（执行不到的）代码以及常数传播和内联等基本优化。

过程间优化，当程序链接时检查文件间函数调用的一个步骤。在编译和链接时必须使用此标志。使用这个标志的编译时间非常长，但是根据应用程序的不同，如果与-O*标志结合使用，可能会有明显的性能改进。

内联

内联或内联展开，简单理解，就是将函数调用用函数体代替，主要优点是省去了函数调用开销和返回指令的开销，主要缺点是可能增大代码大小。

PGO

PGO优化是分三步完成的，是一个动态的优化过程。

PGO，即Profile-Guided Optimizations，档案导引优化。

具体选项详解

-mtune=processor

此标志对特定的处理器类型进行额外的调整，但是它不会生成额外的SIMD指令，因此不存在体系结构兼容性问题。调优将涉及对处理器缓存大小、指令优先顺序等的优化。

为支持指定英特尔处理器或微体系结构代码名的处理器优化代码。

-no-prec-div

不启用 提高浮点除法的精度。

-static

不用动态库

-fp-model fast=2

自动向量化时按照固定精度，与OpenMP的选项好像有兼容性的问题

-funroll-all-loops

展开所有循环，即使进入循环时迭代次数不确定。此选项可能会影响性能。

-unroll-aggressive / -no-unroll-aggressive

此选项决定编译器是否对某些循环使用更激进的展开。期权的积极形式可以提高绩效。

此选项可对具有较小恒定递增计数的回路进行积极的完全展开。

falign-loops

将循环对齐到 2 的幂次字节边界。

-falign-loops[=n]是最小对齐边界的可选字节数。它必须是 1 到 4096 之间的 2 的幂，例如 1、2、4、8、16、32、64、128 等。如果为 n 指定 1，则不执行对齐；这与指定选项的否定形式相同。如果不指定 n，则默认对齐为 16 字节。

-O0 / -Od

关闭所有优化选项，-O等于-O2 (Linux and macOS)

-O1

在保证代码量不增加的情况下编译，

  1. 实现全局优化；这包括数据流分析、代码运动、强度降低和测试替换、分割生存期分析和指令调度。
  2. 禁用某些内部函数的内联。

遇到的问题

 icpc -dM -E -x c++ SLIC.cpp

https://stackoverflow.com/questions/34310546/how-can-i-see-which-compilation-options-are-enabled-on-intel-icc-compiler

parallel 与mpicc 或者mpiicc有什么区别呢

开题缘由、总结、反思、吐槽~~

讲实话，IPO PGO我已经晕了，我先列个list,之后再研究

参考文献

https://blog.csdn.net/gengshenghong/article/details/7034748

按字母顺序排列的intel c++编译器选项列表

  • 分类于 Tutorials
  • 需要 2 分钟阅读时间

IPCC Preliminary SLIC Optimization 2

chivier advise on IPCC amd_256

技术路线 描述 时间 加速比 备注
Baseline 串行程序 21872 ms 1
核心循环openmp 未指定 8079ms
核心循环openmp 单节点64核 7690ms 2.84
换intel的ipcp 基于上一步 3071 ms 7.12
-xHOST 其余不行，基于上一步 4012ms
-O3 基于上一步 3593ms

node5

Intel(R) Xeon(R) Platinum 8153 CPU @ 2.00GHz

技术路线 描述 时间 加速比 备注
Baseline 串行程序 29240 ms 1
核心循环openmp 未指定(htop看出64核) 12244 ms
去除无用计算+两个numk的for循环 080501 11953 ms 10054 ms
计算融合(去除inv) 080502 15702 ms 14923 ms 15438 ms 11987 ms
maxlab openmp 基于第三行080503 13872 ms 11716 ms
循环展开?? 14436 ms 14232 ms 15680 ms

-xCOMMON-AVX512 not supports

Please verify that both the operating system and the processor support Intel(R) X87, CMOV, MMX, FXSAVE, SSE, SSE2, SSE3, SSSE3, SSE4_1, SSE4_2, MOVBE, POPCNT, AVX, F16C, FMA, BMI, LZCNT, AVX2, AVX512F, ADX and AVX512CD instructions.
-xCORE-AVX2 
Please verify that both the operating system and the processor support Intel(R) X87, CMOV, MMX, FXSAVE, SSE, SSE2, SSE3, SSSE3, SSE4_1, SSE4_2, MOVBE, POPCNT, AVX, F16C, FMA, BMI, LZCNT and AVX2 instructions
没有 FXSAVE,BMI,LZCNT 有BMI1，BMI2

使用-xAVX,或者-xHOST 来选择可用的最先进指令集 

Please verify that both the operating system and the processor support Intel(R) X87, CMOV, MMX, FXSAVE, SSE, SSE2, SSE3, SSSE3, SSE4_1, SSE4_2, POPCNT and AVX instructions.

-fast bugs

ld: cannot find -lstdc++
ld: cannot find -lstdc++
/public1/soft/intel/2020u4/compilers_and_libraries_2020.4.304/linux/compiler/lib/intel64_lin/libiomp5.a(ompt-general.o): In function `ompt_pre_init':
(.text+0x2281): warning: Using 'dlopen' in statically linked applications requires at runtime the shared libraries from the glibc version used for linking
/var/spool/slurm/d/job437118/slurm_script: line 23: ./SLIC_slurm_intel_o3: No such file or directory

AMD EPYC 7~~2

icpc -Ofast -march=core-avx2 -ipo -mdynamic-no-pic -unroll-aggressive -no-prec-div -fp-mode fast=2 -funroll-all-loops -falign-loops -fma -ftz -fomit-frame-pointer -std=c++11 -qopenmp SLIC_openmp.cpp -o SLIC_slurm_intel_o3

后续优化

基于核心的openmp并行

去除无用计算

delete all maxxy
if(maxxy[klabels[i]] < distxy[i]) maxxy[klabels[i]] = distxy[i];

计算融合(减少访存次数)

  1. 将inv去除(效果存疑)
  2. maxlab openmp并行(由于不是计算密集的，是不是要循环展开)

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

无