logo标签列表

如何改进大型uint64数组的XOR运算？

c++c++11xoravx2
3
我想要对大型的位移数组进行异或操作，以下是便于解释的可移植版本的函数。我该如何改进这个计算过程？我尝试过使用AVX2，但没有看到太多改进。目前对于下面示例中显示的DB，处理所有内容需要50毫秒，即12 GB/s。我将非常感谢任何改进计算过程的建议。
#include <iostream>

uint64_t partition_size = 4096;
uint64_t entry_size = 32; // bytes
uint64_t DB_size = 16777216;
uint64_t *DB = new uint64_t[DB_size * entry_size/64];


//partition_index will be a random multiple of partition_size, e.g. 0, 8192, 4096 etc
//random_offset will be a random number in [0, partition_size]
void xor_shifted_arrays(uint32_t partition_index, uint32_t random_offset, uint64_t *result)
{
    auto uint64_per_entry = entry_size / sizeof(uint64_t);

    int shift_offset;
    uint32_t shift;
    
    for (int i = 0; i < partition_size  ; i = i + 1)
    {
        shift = (i + random_offset) & (partition_size - 1);
        shift_offset = shift * uint64_per_entry;
        
        for (int j = 0; j < uint64_per_entry; j=j+1){
            result[shift_offset + j] = result[shift_offset + j] ^ DB[partition_index + j];  
        }
        partition_index = partition_index + uint64_per_entry;
    }
}

更新： 这是godbolt链接：https://godbolt.org/z/j14av3fGq 我还在两个实例上运行了这段代码。
Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz 运行在 MacOS 13.6 上，16 GB DDR4 RAM，编译器为 Apple clang version 15.0.0 (clang-1500.0.40.1)
AWS r7i.2xlarge Intel(R) Xeon(R) Platinum 8488C 运行在 Ubuntu 上，64 GB DDR5 RAM，编译器为 g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
令人惊讶的是，Xeon 上的速度是其两倍慢！！
我正在使用编译器标志 O3
更新2：我觉得这可能会有用，上述代码是从外部函数中调用的，类似于以下示例（非运行代码）
void outer_function(){
  uint64_t *result1 = new uint64_t[partition_size];
  uint64_t *result2 = new uint64_t[partition_size];
  uint64_t number_partitions = 4096;
  for (int i=0; i< number_partitions; i++){
      xor_shifted_arrays(i*partition_size,           some_rnd_gen(), result1)
  }
  for (int i=0; i< number_partitions; i++){
     xor_shifted_arrays(i*partition_size,                some_rnd_gen(), result2)
  }
}
4
任何关于C++代码速度或性能的问题都必须附带编译器选项，这些选项用于构建程序。其中最重要的选项是优化设置。如果您正在运行未优化或“调试”构建，则您报告的计时是没有意义的。 - undefined
3
Xeon 8488C与您的i7-7700K Kaby Lake在内存带宽随线程数量扩展方面有着显著的差异。KBL系统可以通过单个核心更多或更少地饱和DRAM，但Sapphire Rapids Xeon需要大部分核心处于活动状态才能使其DRAM控制器达到最大化，每个核心的带宽低于较旧的台式机芯片（为什么Skylake在单线程内存吞吐量方面比Broadwell-E好得多？）。请参阅https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/以获取一些SPR图表。 - undefined
2
与如何使用SIMD加速XOR两个内存块？几乎相同 - 编译器已经自动向量化（至少在GCC的-O3级别）。如今，我们不再受限于2013年的SSE2问题，内存对齐对于良好的SIMD性能通常不再那么重要（或者如果内存对齐，向编译器保证对其对于AVX来说有时是完全无关紧要的）。但是，重要的是编译器已经做得很好，您不需要使用内嵌函数来实现这一点。 - undefined
1
如果你想在多核心的CPU上获得良好的单核心内存带宽，可以考虑使用AMD的Threadripper或EPYC处理器。在https://chipsandcheese.com/2023/03/12/a-peek-at-sapphire-rapids/中，有一张关于单核心内存带宽与工作集大小的图表，其中包括了基于Zen3架构的EPYC处理器。它的性能大约是Sapphire Rapids（SPR）的两倍，与i9-12900K桌面处理器相当。 - undefined
1
@CryptoKitty：是的，为了获取L3命中，进行缓存阻塞是值得的，也许L2也是。DB仍然可以是一个连续的数组，你只需要在结果/DB的每个块的前0.5 MiB上进行循环，然后是第二个，第三个，以此类推，并在你当前代码的外部循环中执行。在大型Xeon处理器上，每个核心私有的L2缓存比L3缓存要快得多，每个核心都有1到2 MiB的L2缓存。（SPR上是2 MiB。） - undefined
显示剩余35条评论
2个回答
3
这些大多是通用的建议，它们将帮助你的编译器优化代码（其中许多已经在评论中提到了）。
  • 对于数组的索引/大小，始终使用size_t（或ptrdiff_t，如果您想允许负索引）。这将使编译器避免处理潜在的环绕或溢出行为。
  • 在初始化变量的位置/使用它们的范围内声明变量。
  • 将所有在初始化后永远不会更改的变量声明为const。如果编译器知道它们的值，它可以优化与它们的乘法或除法，尤其是如果它们是2的幂。
  • 将您修改的数组的指针作为函数参数传递，并使用__restrict关键字（只有在确定该数组不与其他数组别名/重叠时才这样做）。这通常有助于编译器进行展开和SIMD优化。
  • 使用-march=native（或-march=target_architecture）编译您的代码，以针对本地或某个特定的CPU架构进行优化（当然还要加上-O3）。
  • 仅为了可读性：不要写A = A + B，而是写A += B（与^/^=等类似）。这通常对编译器没有影响。
假设您在您的godbolt链接中的`j=j+4`是一个打字错误，您的意思是`j+=1`（或者`++j`），这将导致非常干净的AVX2代码。
// assuming these are known at compile-time:
const size_t partition_size = 4096; 
const size_t entry_size = 256; // bits
const size_t DB_size = 16777216;

uint64_t *DB = new uint64_t[DB_size * entry_size/64];
const size_t uint64_per_entry = entry_size / sizeof(uint64_t);
//uint64_t *result = new uint64_t[partition_size]; // pass this as parameter

//partition_index will be a random multiple of partition_size, e.g. 0, 8192, 4096 etc
//random_offset will be a random number in [0, partition_size]
void xor_shifted_arrays(size_t partition_index, size_t random_offset, uint64_t *__restrict result)
{

    for (size_t i = 0; i < partition_size  ; i++)
    {
        const size_t shift = (i + random_offset) & (partition_size - 1);
        const size_t shift_offset = shift * uint64_per_entry;
        
        for (size_t j = 0; j < uint64_per_entry; j++){
            result[shift_offset + j] ^= DB[partition_index + j];    
        }
        partition_index += uint64_per_entry;
    }
}

Godbolt-Link: https://godbolt.org/z/Khs5aTPaK 我对这段代码没有看到更多可能的改进。你需要一次性读取和写入每个result条目以及相应的DB条目。 如果你对内存管理有控制权，你可以确保指针对齐到页面大小（或至少与你的SIMD宽度对齐）。
另外，如果（针对不同的问题）某些条目需要多次读取或修改，你可以尝试重新安排循环，以减少变量从/写入内存的频率。
添加外部函数草图，以防有什么可以在那里做的。 - undefined
1
@CryptoKitty，对于你所遇到的扩展问题，你可以大大减少对结果向量的访问次数。顺便说一句：你确定 uint64_per_entry = entry_size / sizeof(uint64_t); 这个表达式是正确的吗？请注意，sizeof 给出的是字节数而不是位数。 - undefined
如何减少访问次数？ - undefined
我不小心把entry_size设为了bits，实际上应该是bytes。是的，uint64_per_entry = entry_size / sizeof(uint64_t); 是正确的，应该是4。 - undefined
假设 some_rnd_gen() 没有奇怪的副作用，你可以展开外层循环的2或4次迭代，而不是对 result 进行移位，将所有对 DB 的访问都通过 -random_offset 进行移位。然后，在将它们异或到 result 条目之前，可以对多个 DB 条目进行异或操作。（如果你需要一个可工作的实现，请提供一个可工作的 [mre]） - undefined
1
OpenCL可以轻松地将简单代码向量化，并将工作分配给所有核心。例如，以下代码在3毫秒内使用Ryzen 7900（12个核心）计算了1600万个64位整数的XOR，在双通道4800MHz DDR5内存上实现了约44GB/s的带宽（这只是所有元素的简单XOR，不是完全按照您的算法，因此它没有有效地使用缓存，而是简单地流式传输数据）。
int main()
{
    constexpr int N = 4096 * 4096;
    constexpr int numWorkers = 4096*32;
    GPGPU::Computer computer(GPGPU::Computer::DEVICE_CPUS);
    std::string nStr = std::string("constant int N = ") + std::to_string(N) + R"(;
    )";
    std::string nwStr = std::string("constant int stride = ") + std::to_string(numWorkers) + R"(;
    )";
    computer.compile(nStr+nwStr+R"(
    
        kernel void Xor(global unsigned long * dataIn, global unsigned long * dataOut)
        { 
            int id = get_global_id(0);
            unsigned long xorData = dataIn[id];
            for(int i=1;i<N/stride;i++)
            {
                xorData = xorData ^ dataIn[id + i*stride];
            }

            // reduced result
            dataOut[id]=xorData;
        })", "Xor");

    GPGPU::HostParameter dataIn = computer.createArrayInput<uint64_t>("dataIn",N);
    GPGPU::HostParameter dataOut = computer.createArrayOutput<uint64_t>("dataOut", numWorkers);
    auto parameters = dataIn.next(dataOut);

    uint64_t result = 0;
    size_t t;
    for (int rep = 0; rep < 20; rep++)
    {
        for (int init = 0; init < N; init++)
            dataIn.access<uint64_t>(init) = init;
        {
            GPGPU::Bench bench(&t);
            computer.compute(parameters, "Xor", 0, numWorkers, 256);

            // final pass on host-side with just numWorkers elements
            uint64_txorData = dataOut.access<uint64_t>(0);
            for (int i = 1; i < numWorkers; i++)
            {
                xorData ^= dataOut.access<uint64_t>(i);
            }
            result = xorData;
        }
        std::cout << "computation took " << t / 1000000000.0 << "s" << std::endl;
        std::cout << "xor: " << result << std::endl;
        std::cout << "------------" << std::endl;
    }
    return 0;
}

输出：

computation took 0.0079244s
xor: 0
------------
computation took 0.0030533s
xor: 0
------------
computation took 0.0030468s
xor: 0
------------
computation took 0.0031714s
xor: 0
------------
computation took 0.0030102s
xor: 0
------------
computation took 0.0030884s
xor: 0
------------
computation took 0.0029352s
xor: 0
------------
computation took 0.0029854s
xor: 0
------------
computation took 0.0029936s
xor: 0
------------
computation took 0.0029326s
xor: 0
------------
computation took 0.0030838s
xor: 0
------------
computation took 0.0031311s
xor: 0
------------
computation took 0.0030022s
xor: 0
------------
computation took 0.0031073s
xor: 0
------------
computation took 0.0029577s
xor: 0
------------
computation took 0.0030004s
xor: 0
------------
computation took 0.0031038s
xor: 0
------------
computation took 0.0029255s
xor: 0
------------
computation took 0.002938s
xor: 0
------------
computation took 0.0029927s
xor: 0
------------

我必须安装Intel的运行时才能使用CPU。我也尝试了GPU，但是pcie v4.0有一些瓶颈（只有大约32GB/s，超出了CPU缓存之外）。
要控制L2和L3的缓存或显式选择核心，您可以使用OpenCL的device-fission功能。如果您不需要OpenCL，您仍然可以观察程序二进制的汇编输出，以了解它如何对代码进行向量化，并将其用于您自己的C++手动优化的AVX库。
OpenMP的#pragma omp parallel可能更容易使用，并且基本上可以得到相同的结果。挑战在于以足够粗的块并行化，以最小化开销，所以可能不适用于内部循环。特别是如果对L2大小的内部循环进行缓存阻塞，您会希望确保同一物理核心每次重新读取相同的DB或result块。 - undefined
1
OpenCL具有设备分割功能，可以让物理核心独立且明确地作为设备使用。甚至可以通过缓存拓扑查询来选择它们。但在计算上可能不如手动调优的AVX代码好，但仍然能够充分利用缓存。也许通过将块ID映射到核心ID可以解决这个缓存问题。当然，启用OpenMP要简单得多。但一旦在OpenCL中完成，甚至可以自动过渡到GPU甚至FPGA，以备不时之需。 - undefined
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接