4

代码看起来像这样,内部循环需要大量时间:

#define _table_derive                  ((double*)(Buffer_temp + offset))
#define Table_derive(m,nbol,pos)        _table_derive[(m) + 5*((pos) + _interval_derive_dIdQ * (nbol))]
char *Buffer_temp=malloc(...);

for (n_bol=0; n_bol<1400; n_bol++)  // long loop here
    [lots of code here, hundreds of lines with computations on doubles, other loops, etc]

    double ddI=0, ddQ=0;

    // This is the original code
    for(k=0; k< 100; k++ ) {
            ddI += Table_derive(2,n_bol,k);
            ddQ += Table_derive(3,n_bol,k);
    }
    ddI /= _interval_derive_dIdQ;
    ddQ /= _interval_derive_dIdQ;
    [more code here]
}

oprofile 告诉我大部分运行时间都花在这里(第二列是时间百分比):

129304  7.6913 :for(k=0; k< 100; k++) {
275831 16.4070 :ddI += Table_derive(2,n_bol,k);
764965 45.5018 :ddQ += Table_derive(3,n_bol,k);

我的第一个问题是:我是否可以依靠 oprofile 来指示代码运行缓慢的正确位置(我在 -Og 和 -Ofast 中尝试过,它基本相同)。

我的第二个问题是:为什么这个非常简单的循环比 sqrt、atan2 和之前的数百行计算慢?我知道我没有显示所有代码,但是有很多代码,对我来说没有意义。

我尝试了各种优化器技巧来矢量化(不起作用)或展开(起作用)但收效甚微,例如:

    typedef double aligned_double __attribute__((aligned(8)));
    typedef const aligned_double* SSE_PTR;
    SSE_PTR TD=(SSE_PTR)&Table_derive(2,n_bol,0);   // We KNOW the alignement is correct because offset is multiple of 8

    for(k=0; k< 100; k++, TD+=5) {
        #pragma Loop_Optimize Unroll No_Vector
        ddI += TD[0];
        ddQ += TD[1];
    }

我检查了优化器的输出:“-Ofast -g -march=native -fopt-info-all=missed.info -funroll-loops”,在这种情况下,我得到“循环展开 9 次”,但如果我尝试矢量化,我得到(简而言之):“无法强制对齐参考”,“矢量对齐可能无法到达”,“矢量化未对齐的访问”,“访问的未知对齐:*(prephitmp_3784 +((sizetype ) _1328 + (long unsigned int) (n_bol_1173 * 500) * 2) * 4)"

有什么办法可以加快速度吗?

附录:谢谢大家的意见,我会在这里回答:

  • 是的,我知道代码很丑(不是我的),而且你还没有看到真正的原始代码(这是一个巨大的简化)
  • 我坚持使用这个数组,因为 C 代码位于库中,而大型数组一旦被 C 处理和修改,就会传递给调用者(IDL、Python 或 C)。
  • 我知道使用一些结构而不是将 char* 转换为复杂的多维 double* 会更好,但请参见上文。当第一次编写这个程序时,结构可能不是 C 规范的一部分(开个玩笑......也许)
  • 我知道对于矢量化器来说,数组结构比结构数组更好,但是,叹息......见上文。
  • 有一个实际的外循环(在调用程序中),所以这个整体数组的总大小约为 2Gb
  • 照原样,在没有优化的情况下运行大约需要 15 分钟,并且在我重写了一些代码(更快的 atan2,数组内的一些手动对齐......)之后一分钟,我使用了 -Ofast 和 -march=native
  • 由于硬件的限制变化,我试图更快地跟上数据流。
  • 我尝试使用 Clang 并且收益很小(几秒钟),但我没有看到获得优化报告的选项,例如 -fopt-info。我是否必须将程序集视为了解发生了什么的唯一选择?
  • 该系统是一个拥有 500Gb RAM 的 64 核,但我无法插入任何 OpenMP pragma 来并行化上述代码(我已经尝试过):它读取一个文件,将其完全解压缩到内存中(2Gb) ,按顺序分析它(诸如'+='之类的东西)并将一些结果吐出给调用IDL/Python。全部在一个内核上(但其他内核非常忙于实际采集和后期处理)。:(
  • 没用,感谢您的出色建议:删除 ddQ += ... 似乎将时间百分比转移到上一行:376280 39.4835:ddI+=...
  • 这让我们变得更好:删除两者(因此整个循环)保存......什么都没有!所以我想正如彼得所说,我不能相信探查器。如果我分析无环编,我会得到更均匀的时间分布(以前只有 1 秒以上的 3 行,现在大约 10 行,所有这些都像简单的变量分配一样荒谬)。

我猜这个内部循环从一开始就是一个红鲱鱼。我将使用手动计时重新开始优化。谢谢。

4

1 回答 1

3

我的第一个问题是:我可以依靠 oprofile 来指示代码慢的正确位置吗

不准确。据我了解,周期通常由等待输入(或其他一些执行资源)的指令负责,而不是产生输入或释放任何其他执行资源的指令缓慢。

但是,在您的 oprofile 输出中,它很可能实际上是最后一个循环。这个外循环里面还有其他内循环吗?

您是否配置过缓存未命中?除了循环之外,还有许多有趣的东西的计数器。

另请注意,要真正了解性能,您需要查看 asm 上的配置文件注释,而不是 C。例如,一个添加帐户的时间比另一个多,这很奇怪,但这可能只是将 insns 映射到的问题源代码行。


回复:注释掉循环的性能结果:

那么如果没有那个内部循环,程序就不会运行得更快吗?如果外部循环已经触及该内存,也许您只是缓存未命中的瓶颈,而内部循环只是再次触及该内存?perf record -e L1-dcache-load-misses ./a.out那就试试吧perf report。或oprofile等价物。

也许内循环 uops 一直在等待发布,直到外循环中的慢东西退休。现代 Intel CPU 中的 ReOrder Buffer (ROB) 大小约为 200 uop,大多数 insn 解码为单个 uop,因此乱序窗口约为 200 条指令。

注释掉内循环也意味着外循环中的任何循环携带的依赖链在内循环运行时都没有时间完成。移除该内循环可能会在外循环的瓶颈中产生质的变化,从吞吐量到延迟。


回复:使用 . 时快 15 倍-Ofast -march=native。好的,这很好。未优化的代码是可怕的,不应被视为任何类型的“基线”或任何性能。如果您想与某物进行比较,请与-O2(不包括自动矢量化-ffast-math、 或-march=native)进行比较。

尝试使用-fprofile-generate/ -fprofile-use。profile-use includes -funroll-loops,所以我认为当有可用的分析数据时,该选项效果最好。

回复:自动并行化:

您必须使用 OpenMP 编译指示或gcc 选项(如-floop-parallelize-all -ftree-parallelize-loops=4. 如果存在非平凡的循环携带依赖项,则可能无法实现自动并行化。该 wiki 页面也很旧,可能无法反映自动并行化的最新技术。我认为 OpenMP 提示要并行化哪些循环是比让编译器猜测更明智的方法,尤其是。没有-fprofile-use


我尝试使用 Clang 并且收益很小(几秒钟),但我没有看到获得优化报告的选项,例如 -fopt-info。我是否必须将程序集视为了解发生了什么的唯一选择?

clang 手册说您可以用于内联clang -Rpass=inline报告。 llvm 文档说矢量化过程的名称是loop-vectorize, 所以你可以使用-Rpass-missed=loop-vectorize, 或者-Rpass-analysis=loop-vectorize告诉你哪个语句导致矢量化失败。

查看 asm 是了解它是否自动矢量化的唯一方法但要真正判断编译器的工作,您必须知道如何自己编写高效的 asm(这样您就可以大致了解它可以做什么。)参见http ://agner.org/optimize/以及标签 wiki中的其他链接。

我没有尝试将您的代码放在http://gcc.godbolt.org/上以尝试使用不同的编译器,但如果您的示例使 asm 代表您从完整源代码中看到的内容,您可以发布一个链接。


自动矢量化

for(k=0; k< 100; k++ ) {
        ddI += Table_derive(2,n_bol,k);
        ddQ += Table_derive(3,n_bol,k);
}

这应该自动矢量化,因为 2 和 3 是连续的元素。如果将表拆分为多个表,您将获得更好的缓存局部性(对于这部分)。例如,将每组 5 的元素 2 和 3 保留在一个数组中。将一起使用的其他元素分组到表格中。(如果有重叠,例如另一个循环需要元素 1 和 3,那么可能会拆分那个无论如何都不能自动矢量化的循环?)

回复:问题更新:您不需要数组结构来使用 SSE 自动矢量化。一个 16B 的向量正好包含两个doubles,因此编译器可以累积一个[ ddI ddQ ]with的向量addsd。但是,对于 AVX 256b 向量,它必须执行vmovupd/vinsertf128才能从相邻结构中获取那对doubles,而不是单个 256b 加载,但这没什么大不了的。但是,内存局部性是一个问题。你在double你接触的缓存行中每 5 秒只使用 2 秒。


-ffast-math只要您的目标是具有双精度向量的 CPU,即使没有 ,它也可能会自动向量化。(例如 x86-64 或 32 位-msse2)。

gcc 喜欢为可能未对齐的数据做大的序言,使用标量直到它到达对齐的地址。这会导致臃肿的代码,尤其是。带有 256b 个向量和小元素。不过,它不应该太糟糕double。不过,试试 clang 3.7 或 clang 3.8。clang 使用未对齐的负载自动矢量化可能未对齐的访问,当数据在运行时对齐时,这没有额外的成本。(gcc 优化了数据未对齐的极少数情况,因为未对齐的加载/存储指令在旧 CPU(例如 Intel pre-Nehalem)上速度较慢,即使用于对齐的数据也是如此。)


如果您的char数组不能证明每个数组double甚至是 8B 对齐的,那么它可能会击败自动矢量化器。就像@JohnBollinger 评论的那样,这真的很难看。如果你有一个包含 5 个双精度的结构数组,那么就这样声明吧!

如何将其编写为结构数组:

保留“手动”多维索引,但将基本一维数组设为double或更好的struct类型的数组,因此编译器将假定每个double都是 8B 对齐的。

Buffer_temp您的原始版本还为对数组的每次访问引用了全局。(或者它是本地的?)任何可能为其别名的存储都需要重新加载基指针。(C 的别名规则允许char*对任何东西进行别名,但我认为您double*在取消引用之前强制转换为 a 可以避免这种情况。无论如何您都不会存储到内部循环内的数组中,但我假设您在外部数组中。)

typedef struct table_derive_entry {
    double a,b,c,d,e;
} derive_t;

void foo(void)
{
    // I wasn't clear on whether table is static/global, or per-call scratch space.
    derive_t *table = aligned_alloc(foo*bar*sizeof(derive_t), 64);            // or just malloc, or C99 variable size array.

    // table += offset/sizeof(table[0]);   // if table is global and offset is fixed within one call...

// maybe make offset a macro arg, too?
#define Table_derive(nbol, pos)     table[offset/sizeof(derive_t) + (pos) + _interval_derive_dIdQ / sizeof(derive_t) * (nbol))]


    // ...        
    for(k=0; k< 100; k++ ) {
         ddI += Table_derive(n_bol, k).b;
         ddQ += Table_derive(n_bol, k).c;
    }
    // ...
}
#undef Table_derive

如果_interval_derive_dIdQ并且offset不总是 5 * 8B 的倍数,那么您可能需要将double *table = ...;Table_derive 声明并修改为类似

#define Table_derive(nbol, pos)   ( ((derive_t *)(double_table + offset/sizeof(double) + _interval_derive_dIdQ / sizeof(double) * (nbol)))[pos] )

FP部门:

ddI /= _interval_derive_dIdQ;
ddQ /= _interval_derive_dIdQ;

你能double inv_interval_derive_dIdQ = 1.0 / _interval_derive_dIdQ;跳出循环吗?乘法比除法便宜得多,尤其是。如果延迟很重要,或者 sqrt 也需要 div 单元。

于 2016-04-28T01:10:48.547 回答