C语言 为什么对64位元素的循环进行向量化并不能提高大型缓冲区的性能？

gstyhher  于 2023-05-16  发布在  其他
关注(0)|答案(4)|浏览(116)

我正在研究向量化对程序性能的影响。在这方面，我写了以下代码：

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

#define LEN 10000000

int main(){

    struct timeval stTime, endTime;

    double* a = (double*)malloc(LEN*sizeof(*a));
    double* b = (double*)malloc(LEN*sizeof(*b));
    double* c = (double*)malloc(LEN*sizeof(*c));

    int k;
    for(k = 0; k < LEN; k++){
        a[k] = rand();
        b[k] = rand();
    }

    gettimeofday(&stTime, NULL);

    for(k = 0; k < LEN; k++)
        c[k] = a[k] * b[k];

    gettimeofday(&endTime, NULL);

    FILE* fh = fopen("dump", "w");
    for(k = 0; k < LEN; k++)
        fprintf(fh, "c[%d] = %f\t", k, c[k]);
    fclose(fh);

    double timeE = (double)(endTime.tv_usec + endTime.tv_sec*1000000 - stTime.tv_usec - stTime.tv_sec*1000000);

    printf("Time elapsed: %f\n", timeE);

    return 0;
}

在这段代码中，我只是简单地初始化和乘以两个向量。结果保存在矢量c中。我主要感兴趣的是向量化以下循环的效果：

for(k = 0; k < LEN; k++)
    c[k] = a[k] * b[k];

我使用以下两个命令编译代码：

1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2

我希望看到性能的提高，因为第二个命令成功地向量化了循环。然而，我的研究表明，当循环被向量化时，没有性能提高。
我可能错过了一些东西，因为我对这个主题不太熟悉。所以，请让我知道，如果我的代码有什么问题。
先谢谢你的帮助。
PS：我使用的是Mac OSX，所以不需要对齐数据，因为所有分配的内存都是16字节对齐的。
编辑：首先感谢大家的评论和回答。我想了想@Mysticial提出的答案，还有一些问题应该在这里提到。首先，正如@Vinska所提到的，c[k]=a[k]*b[k]不会只占用一个周期。除了循环索引递增和比较以确保k小于LEN之外，还需要执行其他操作来执行操作。看看编译器生成的汇编代码，可以看出一个简单的乘法需要的周期远远不止一个。矢量化的版本看起来像：

L_B1.9:                         # Preds L_B1.8
        movq      %r13, %rax                                    #25.5
        andq      $15, %rax                                     #25.5
        testl     %eax, %eax                                    #25.5
        je        L_B1.12       # Prob 50%                      #25.5
                                # LOE rbx r12 r13 r14 r15 eax
L_B1.10:                        # Preds L_B1.9
        testb     $7, %al                                       #25.5
        jne       L_B1.32       # Prob 10%                      #25.5
                                # LOE rbx r12 r13 r14 r15
L_B1.11:                        # Preds L_B1.10
        movsd     (%r14), %xmm0                                 #26.16
        movl      $1, %eax                                      #25.5
        mulsd     (%r15), %xmm0                                 #26.23
        movsd     %xmm0, (%r13)                                 #26.9
                                # LOE rbx r12 r13 r14 r15 eax
L_B1.12:                        # Preds L_B1.11 L_B1.9
        movl      %eax, %edx                                    #25.5
        movl      %eax, %eax                                    #26.23
        negl      %edx                                          #25.5
        andl      $1, %edx                                      #25.5
        negl      %edx                                          #25.5
        addl      $10000000, %edx                               #25.5
        lea       (%r15,%rax,8), %rcx                           #26.23
        testq     $15, %rcx                                     #25.5
        je        L_B1.16       # Prob 60%                      #25.5
                                # LOE rdx rbx r12 r13 r14 r15 eax
L_B1.13:                        # Preds L_B1.12
        movl      %eax, %eax                                    #25.5
                                # LOE rax rdx rbx r12 r13 r14 r15
L_B1.14:                        # Preds L_B1.14 L_B1.13
        movups    (%r15,%rax,8), %xmm0                          #26.23
        movsd     (%r14,%rax,8), %xmm1                          #26.16
        movhpd    8(%r14,%rax,8), %xmm1                         #26.16
        mulpd     %xmm0, %xmm1                                  #26.23
        movntpd   %xmm1, (%r13,%rax,8)                          #26.9
        addq      $2, %rax                                      #25.5
        cmpq      %rdx, %rax                                    #25.5
        jb        L_B1.14       # Prob 99%                      #25.5
        jmp       L_B1.20       # Prob 100%                     #25.5
                                # LOE rax rdx rbx r12 r13 r14 r15
L_B1.16:                        # Preds L_B1.12
        movl      %eax, %eax                                    #25.5
                                # LOE rax rdx rbx r12 r13 r14 r15
L_B1.17:                        # Preds L_B1.17 L_B1.16
        movsd     (%r14,%rax,8), %xmm0                          #26.16
        movhpd    8(%r14,%rax,8), %xmm0                         #26.16
        mulpd     (%r15,%rax,8), %xmm0                          #26.23
        movntpd   %xmm0, (%r13,%rax,8)                          #26.9
        addq      $2, %rax                                      #25.5
        cmpq      %rdx, %rax                                    #25.5
        jb        L_B1.17       # Prob 99%                      #25.5
                                # LOE rax rdx rbx r12 r13 r14 r15
L_B1.18:                        # Preds L_B1.17
        mfence                                                  #25.5
                                # LOE rdx rbx r12 r13 r14 r15
L_B1.19:                        # Preds L_B1.18
        mfence                                                  #25.5
                                # LOE rdx rbx r12 r13 r14 r15
L_B1.20:                        # Preds L_B1.14 L_B1.19 L_B1.32
        cmpq      $10000000, %rdx                               #25.5
        jae       L_B1.24       # Prob 0%                       #25.5
                                # LOE rdx rbx r12 r13 r14 r15
L_B1.22:                        # Preds L_B1.20 L_B1.22
        movsd     (%r14,%rdx,8), %xmm0                          #26.16
        mulsd     (%r15,%rdx,8), %xmm0                          #26.23
        movsd     %xmm0, (%r13,%rdx,8)                          #26.9
        incq      %rdx                                          #25.5
        cmpq      $10000000, %rdx                               #25.5
        jb        L_B1.22       # Prob 99%                      #25.5
                                # LOE rdx rbx r12 r13 r14 r15
L_B1.24:                        # Preds L_B1.22 L_B1.20

而非矢量化版本为：

L_B1.9:                         # Preds L_B1.8
        xorl      %eax, %eax                                    #25.5
                                # LOE rbx r12 r13 r14 r15 eax
L_B1.10:                        # Preds L_B1.10 L_B1.9
        lea       (%rax,%rax), %edx                             #26.9
        incl      %eax                                          #25.5
        cmpl      $5000000, %eax                                #25.5
        movsd     (%r15,%rdx,8), %xmm0                          #26.16
        movsd     8(%r15,%rdx,8), %xmm1                         #26.16
        mulsd     (%r13,%rdx,8), %xmm0                          #26.23
        mulsd     8(%r13,%rdx,8), %xmm1                         #26.23
        movsd     %xmm0, (%rbx,%rdx,8)                          #26.9
        movsd     %xmm1, 8(%rbx,%rdx,8)                         #26.9
        jb        L_B1.10       # Prob 99%                      #25.5
                                # LOE rbx r12 r13 r14 r15 eax

除此之外，处理器不加载仅24字节。在每次访问存储器时，加载一整行（64字节）。更重要的是，由于a、b和c所需的内存是连续的，所以预取器肯定会有很大帮助，并提前加载下一个块。话虽如此，我认为@Mysticial计算的内存带宽过于悲观。
此外，Intel Vectorization Guide中提到了使用SIMD来提高程序的性能，以实现一个非常简单的加法。因此，看起来我们应该能够为这个非常简单的循环获得一些性能改进。
编辑2：再次感谢您的评论。另外，感谢@Mysticial示例代码，我终于看到了SIMD对性能改进的影响。正如Mysticial提到的，问题在于内存带宽。通过为a、b和c选择适合L1缓存的小尺寸，可以看出SIMD可以帮助显着提高性能。以下是我得到的结果：

icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec

icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec

展开循环可以进一步提高性能：

icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec

另外，我应该提到，当使用-O2编译时，我的处理器只需要一个周期就可以完成一次迭代。
PS：我的电脑是Macbook Pro酷睿i5@2.5GHz（双核）

c

4条答案

按热度按时间
afdcj2ne

afdcj2ne1#

这个原始答案在2013年是有效的。截至2017年硬件，事情已经发生了足够的变化，问题和答案都过时了。
请参阅2017年更新的答案结尾。

原始答案（2013）：

因为内存带宽会成为瓶颈。
虽然向量化和其他微优化可以提高计算速度，但它们不能提高内存的速度。
在您的示例中：

for(k = 0; k < LEN; k++)
    c[k] = a[k] * b[k];

您只对所有内存进行了一次遍历，只做了很少的工作。这是最大限度地利用你的内存带宽。
因此，无论如何优化（矢量化，展开等），它都不会变得更快。
2013年的典型台式机具有10 GB/s的内存带宽 *。
您的循环触及24字节/迭代。
如果没有矢量化，现代x64处理器可能一个周期只能进行1次迭代 *。
假设你运行在4 GHz：

  • (4 * 10^9) * 24 bytes/iteration = 96 GB/s

这几乎是您的内存带宽的10倍-没有矢量化。
[2]毫不奇怪，一些人怀疑我上面给出的数字，因为我没有引用。这些都是我的经验之谈。这里有一些基准来证明这一点。

循环迭代最快1个循环/迭代：

如果我们减少LEN，使其适合缓存，就可以摆脱内存瓶颈。
（我用C++测试了这个，因为它更容易。但这并没有什么区别）。

#include <iostream>
#include <time.h>
using std::cout;
using std::endl;

int main(){
    const int LEN = 256;

    double *a = (double*)malloc(LEN*sizeof(*a));
    double *b = (double*)malloc(LEN*sizeof(*a));
    double *c = (double*)malloc(LEN*sizeof(*a));

    int k;
    for(k = 0; k < LEN; k++){
        a[k] = rand();
        b[k] = rand();
    }

    clock_t time0 = clock();

    for (int i = 0; i < 100000000; i++){
        for(k = 0; k < LEN; k++)
            c[k] = a[k] * b[k];
    }

    clock_t time1 = clock();
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
}
  • 处理器：Intel Core i7 2600K@4.2 GHz
  • 编译器：Visual Studio 2012
  • 时间：6.55秒

在这个测试中，我在6.55秒内运行了25，600，000，000次迭代。

  • 6.55 * 4.2 GHz =27，510，000，000次循环
  • 27,510,000,000 / 25,600,000,000 =1.074次循环/迭代

现在，如果你想知道如何做到这一点：

  • 2个负载
  • 1家门店
  • 1乘
  • 增量计数器
  • 比较+分支

都在一个循环里
这是因为现代的处理器和编译器都很棒。
虽然这些操作中的每一个都有延迟（特别是乘法），但处理器能够同时执行多个迭代。我的测试机器是一个桑迪Bridge处理器，它能够在每个周期支持2x 128 b加载、1x 128 b存储和1x 256 b向量FP乘法。并且如果加载是用于微融合uop的存储器源操作数，则可能是另一个或两个向量或整数op。（仅当使用256 b AVX加载/存储时2个加载+1个存储吞吐量，否则每个周期仅两个总存储器操作（至多一个存储））。
看一下程序集（为了简洁起见，我将省略它），似乎编译器展开了循环，从而减少了循环开销。但它没能把它矢量化。

内存带宽为10 GB/s量级：

最简单的测试方法是通过memset()：

#include <iostream>
#include <time.h>
using std::cout;
using std::endl;

int main(){
    const int LEN = 1 << 30;    //  1GB

    char *a = (char*)calloc(LEN,1);

    clock_t time0 = clock();

    for (int i = 0; i < 100; i++){
        memset(a,0xff,LEN);
    }

    clock_t time1 = clock();
    cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
}
  • 处理器：Intel Core i7 2600K@4.2 GHz
  • 编译器：Visual Studio 2012
  • 时间：5.811秒

因此，我的机器需要5.811秒才能写入100 GB的内存。这大约是17.2 GB/s。
而且我的处理器是高端的。Nehalem和Core 2代处理器的内存带宽较少。

2017年3月更新：

到了2017年，事情变得更加复杂。
得益于DDR4和四通道内存，单线程不再可能使内存带宽饱和。但是带宽问题并不一定会消失。尽管带宽增加了，但处理器内核也得到了改善-而且数量更多。
从数学上来说：

  • 每个内核的带宽限制为X。
  • 主内存的带宽限制为Y。
  • 在较旧的系统上，X > Y。
  • 在当前的高端系统上，X < Y。但是X * (# of cores) > Y。

回到2013年：4 GHz桑迪Bridge +1333 MHz双通道DDR3

  • 无矢量化（8字节加载/存储）：X = 32 GB/s和Y = ~17 GB/s
  • 矢量化SSE*（16字节加载/存储）：X = 64 GB/s和Y = ~17 GB/s

2017年：Haswell-E @ 4 GHz +四通道DDR4@2400 MHz

  • 无矢量化（8字节加载/存储）：X = 32 GB/s和Y = ~70 GB/s
  • 矢量化AVX*（32字节加载/存储）：X = 64 GB/s和Y = ~70 GB/s

(For无论桑迪Bridge还是Haswell，该高速缓存中的体系结构限制都将带宽限制为约16字节/周期，而不管SIMD宽度如何。）
所以现在，单个线程并不总是能够使内存带宽饱和。您需要进行矢量化以达到X的限制。但是，如果使用2个或更多线程，您仍然会达到Y的主内存带宽限制。
但有一件事没有改变，而且很可能在很长一段时间内都不会改变：您将无法在所有内核上运行占用带宽的循环，而不会使总内存带宽饱和。

赞(0）分享  回复(0）举报  2023-05-16
izkcnapc

izkcnapc2#

正如Mysticial已经描述的，主存带宽限制是这里大缓冲区的瓶颈。解决这个问题的方法是重新设计您的处理，以便在该高速缓存的块中工作。（而不是乘以整个200MiB的双精度，只乘以128kiB，然后用它做一些事情。因此，使用乘法输出的代码将发现它仍然在L2缓存中。L2通常为256kiB，在最近的英特尔设计中，每个CPU内核都有专用的L2。）

**这种技术被称为cache blocking或loop tiling。**对于某些算法来说，这可能很棘手，但回报是L2缓存带宽与主存带宽

如果您这样做，请确保编译器不再生成流存储（movnt...）。这些写入绕过缓存，以避免用不适合的数据污染它。下一次读取该数据将需要触及主存储器。

赞(0）分享  回复(0）举报  2023-05-16
ruyhziif

ruyhziif3#

编辑：修改了答案很多。此外，请忽略我之前写的关于神秘的答案不完全正确的大部分内容。尽管如此，我仍然不同意它被内存瓶颈，因为尽管做了各种各样的测试，我看不到原始代码被内存速度限制的任何迹象。与此同时，它一直显示出明显的CPU受限迹象。
可能有很多原因。由于原因可能非常依赖于硬件，我决定我不应该根据猜测进行推测。我只是想概述一下我在后来的测试中遇到的这些事情，在那里我使用了一种更准确和可靠的CPU时间测量方法，并循环了1000次。我相信这些信息会有帮助。但请持保留态度，因为它依赖于硬件。

  • 当使用来自SSE系列的指令时，我得到的矢量化代码比非矢量化代码。
  • 使用SSE系列的矢量化代码和使用AVX的矢量化代码或多或少地以相同的性能运行。
  • 当使用AVX指令时，* 非矢量化 * 代码运行得最快-比我尝试的其他任何东西都快25%或更多。
  • 在所有情况下，结果与CPU时钟线性缩放。
  • 结果几乎不受记忆时钟的影响。
  • 结果受内存延迟的影响很大-比内存时钟大得多，但没有CPU时钟对结果的影响那么大。

WRT Mystical的每个时钟运行近1次迭代的示例-我没有想到CPU调度程序会如此高效，并假设每1.5-2个时钟周期运行1次迭代。但令我惊讶的是，事实并非如此;我肯定错了，对不起。我自己的CPU运行效率更高-1.048周期/迭代。所以我可以证明神秘的答案的这一部分是绝对正确的。

赞(0）分享  回复(0）举报  2023-05-16
bnlyeluc

bnlyeluc4#

如果a[] B[]和c[]正在争夺L2缓存：

#include <string.h> /* for memcpy */

 ...

 gettimeofday(&stTime, NULL);

    for(k = 0; k < LEN; k += 4) {
        double a4[4], b4[4], c4[4];
        memcpy(a4,a+k, sizeof a4);
        memcpy(b4,b+k, sizeof b4);
        c4[0] = a4[0] * b4[0];
        c4[1] = a4[1] * b4[1];
        c4[2] = a4[2] * b4[2];
        c4[3] = a4[3] * b4[3];
        memcpy(c+k,c4, sizeof c4);
        }

    gettimeofday(&endTime, NULL);

将运行时间从98429.000000减少到67213.000000;在这里，将环展开8倍将其减少到57157.000000。

赞(0）分享  回复(0）举报  2023-05-16
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com