1

我有以下代码段，它是应用程序中的热点。由于for矢量相关性，循环未矢量化。有没有办法重写这个循环以使其运行得更快。

#define  NUM_KEYS  (1L << 20)
#define  NUM_BUCKETS (1L << 10)    
int i,k;
int shift = (1L << 11);
int key_array[NUM_KEYS],key_buff[NUM_KEYS];
int bucket_ptrs[NUM_BUCKETS];

for( i=0; i<NUM_KEYS; i++ )  
{
    k = key_array[i];
    key_buff[bucket_ptrs[k >> shift]++] = k;
}

我尝试的一种方法是创建一个临时数组来保存key_array.

for( i=0; i<NUM_KEYS; i++ )  
{
        key_arrays[i] = key_array[i] >> shift;
}
for( i=0; i<NUM_KEYS; i++ )  
{
    k = key_array[i];
    j = key_arrays[i];
    key_buff[bucket_ptrs[j]++] = k;
}

在这里，第一个循环被矢量化。但总体来说性能并没有什么提升。

4

2 回答 2

3

为什么循环不可矢量化？

这是因为您在这里有非顺序的内存访问：

key_buff[bucket_ptrs[k >> shift]++] = k;

bucket_ptrs确定访问的索引key_buff。由于这些索引无处不在，因此内存访问是非顺序的。

目前，x86 处理器仅支持 SIMD 加载/存储到连续的内存块。（理想情况下也对齐）

如果您希望它矢量化，您将需要 AVX2 的收集/分散指令。那些不存在，但应该在下一代英特尔处理器中出现。

在这里，第一个循环被矢量化。但总体来说性能并没有什么提升。

这是因为您要添加额外的循环开销。所以你现在做了两次传球key_array。如果有的话，我很惊讶它没有变慢。

有没有办法重写这个循环以使其运行得更快。

我对此表示怀疑——至少在不改变算法的情况下是这样。至少，您将希望key_buff舒适地适应您的 L1 缓存。

AVX2 会让它矢量化，但问题key_buff是 4MB。这不适合较低级别的缓存。所以即使是 AVX2 也可能没有多大帮助。您将完全受内存访问的约束。

于 2012-12-06T20:29:36.793 回答
2

可能让您感到困扰的是，虽然您对 key_array 的访问是顺序的，并且 bucket_ptrs 足够小以适合 L1，但您对 key_buff 的访问却无处不在。

不过，您正在做的事情看起来像是基数排序中的一个步骤。如果这实际上是您正在做的事情，您可能会通过首先将存储桶的数量减少到 32 或 64 个左右，然后对最重要的 5 或 6 位进行排序来提高性能。然后你有一大堆小数组，其中大部分可能适合缓存，你可以使用另一遍基数排序对它们中的每一个进行排序。

于 2012-12-06T20:24:33.200 回答