我正在尝试用CUDA构造一个并行算法,它采用一个整数数组,并删除所有0的有或没有保持顺序.
例:
全局内存:{0,0,0,0,14,0,0,17,0,0,0,0,13}
主机内存结果:{17,13,14,0,0,...}
最简单的方法是使用主机删除0中的O(n)时间.但考虑到我有各种各样的1000元素,在发送之前将GPU上的所有内容保留并首先压缩它可能会更快.
优选的方法是创建设备上堆栈,使得每个线程可以(以任何顺序)弹出和推送到堆栈上或从堆栈中推出.但是,我不认为CUDA有这个实现.
等效(但速度要慢得多)的方法是继续尝试写入,直到所有线程都写完为止:
kernalRemoveSpacing(int * array, int * outArray, int arraySize) {
if (array[threadId.x] == 0)
return;
for (int i = 0; i < arraySize; i++) {
array = arr[threadId.x];
__threadfence();
// If we were the lucky thread we won!
// kill the thread and continue re-reincarnated in a different thread
if (array[i] == arr[threadId.x])
return;
}
}
这种方法的好处在于我们会O(f(x))及时执行,其中f(x)是数组中非零值的平均数(f(x) ~= ln(n)对于我的实现,因此是O(ln(n)) …
我观看了有关十大最疯狂汇编语言指令的 YouTube 视频，其中一些指令对我来说没有明显的应用。像这样的东西有什么意义PEXT，它只取第二个参数中与第一个参数中的 1 索引相匹配的位？编译器如何知道何时使用该指令？关于无进位乘法的相同/相似问题。
免责声明：我对汇编语言知之甚少甚至一无所知。也许我应该读一下它！
我希望这个问题适合 stackoverflow。
Matt Scarpino给出了一个很好的解释(虽然他承认他不确定这是最佳算法,但我感谢他),感谢他如何将两个复杂的双倍乘以英特尔的AVX内在函数.这是他的方法,我已经验证了:
__m256d vec1 = _mm256_setr_pd(4.0, 5.0, 13.0, 6.0);
__m256d vec2 = _mm256_setr_pd(9.0, 3.0, 6.0, 7.0);
__m256d neg = _mm256_setr_pd(1.0, -1.0, 1.0, -1.0);
/* Step 1: Multiply vec1 and vec2 */
__m256d vec3 = _mm256_mul_pd(vec1, vec2);
/* Step 2: Switch the real and imaginary elements of vec2 */
vec2 = _mm256_permute_pd(vec2, 0x5);
/* Step 3: Negate the imaginary elements of vec2 */
vec2 = _mm256_mul_pd(vec2, neg);
/* Step 4: Multiply vec1 and the modified vec2 */
__m256d vec4 = …使用 sse 优化以下代码的有效方法是什么？
uint16_t change1= ... ;
uint8_t* pSrc = ... ;
uint8_t* pDest = ... ;
if(change1 & 0x0001) *pDest++ = pSrc[0];
if(change1 & 0x0002) *pDest++ = pSrc[1];
if(change1 & 0x0004) *pDest++ = pSrc[2];
if(change1 & 0x0008) *pDest++ = pSrc[3];
if(change1 & 0x0010) *pDest++ = pSrc[4];
if(change1 & 0x0020) *pDest++ = pSrc[5];
if(change1 & 0x0040) *pDest++ = pSrc[6];
if(change1 & 0x0080) *pDest++ = pSrc[7];
if(change1 & 0x0100) *pDest++ = pSrc[8];
if(change1 & 0x0200) *pDest++ = pSrc[9];
if(change1 & 0x0400) …假设我有一个掩码mask和一个输入n,例如
mask = 0x10f3 (0001 0000 1111 0011)
n = 0xda4d (1101 1010 0100 1101)
我想1)隔离掩码位(n从不在中删除位mask)
masked_n = 0x10f3 & 0xda4d = 0x1041 (0001 0000 0100 0001)
和2) "扁平化"他们(摆脱零位mask,并将这些同样转移到masked_n)？
flattened_mask = 0x007f (0000 0000 0111 1111)
bits to discard (___1 ____ 0100 __01)
first shift ( __ _1__ __01 0001)
second shift ( __ _101 0001)
result = 0x0051 (0000 0000 0101 0001)
我编写了一个算法,使用Intel内部函数并行执行多个单精度操作.我的算法的每次迭代的结果是单个256位向量(__m256)中的非零项的数量.
例如:
00000000 FFFFFFFF 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF
其中迭代的结果是4.
计算向量中非零项数的最快方法是什么？
目前我正在做这样的事情:
float results[8];
_mm256_storeu_ps(results, result_vector);
int count = 0;
for (uint32_t idx = 0; idx < 8; ++idx)
{
if (results[idx] != 0)
{
++count;
}
}
这种方法运行得很好,但我想知道是否有更有效的方法来做,也许是一个不涉及商店的方法.
我在内存中有大量 64 位值。不幸的是，它们可能不会与 64 位地址对齐。我的目标是改变所有这些值的字节序，即交换/反转它们的字节。
我知道bswap交换 32 位或 64 位寄存器字节的指令。但是因为它需要一个寄存器参数，所以我不能将它传递给我的内存地址。当然我可以先将内存加载到寄存器中，然后交换，然后写回：
mov rax, qword [rsi]
bswap rax
mov qword [rsi], rax
但这是否正确，因为地址可能未对齐？
另一种可能性是手动进行交换：
mov al, byte [rsi + 0]
mov bl, byte [rsi + 7]
mov byte [rsi + 0], bl
mov byte [rsi + 7], al
mov al, byte [rsi + 1]
mov bl, byte [rsi + 6]
mov byte [rsi + 1], bl
mov byte [rsi + 6], al
mov al, byte [rsi + 2]
mov bl, …请告诉我，我自己也搞不懂：
这里我有__m128iSIMD 向量 - 每个 16 个字节都包含以下值：
1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1
是否可以以某种方式变换该向量，以便删除所有 1，并且零的位置是该零向量中元素的编号。也就是说，像这样：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1
1 4 6 10 12 14
最后得到一个只有这些值的向量：
1 4 6 10 12 14
什么样的逻辑才能得到这样的结果呢？应使用哪些 SIMD 指令？
PS：我刚刚开始学习SIMD - 所以我知道的不多。我不明白。
我仍在与在密集、单精度、Fortran 排序的二维数组中查找非零条目的索引（和相应值）i的问题作斗争。我通过 Python 使用 Cython，中间有一些 C。j
我提前道歉，因为这篇文章将会非常长。
我必须处理数千个（有时数百万个）中型 2D 数组（有时 700 x 1,000，有时 6,000 x 7,000 等等），这些数组非常稀疏，但它们提供为密集的（密度可以低至 0.02% 和高达 1-2%）。这些矩阵有时具有某种结构，但通常这是不可预测的。
我尝试过 numpy.nonzero 和 Scipy稀疏的东西，但不幸的是它们比我的慢。
我问这个问题是为了看看我的（可能不正确的）代码的性能是否有可能改进- 即，使其更快 - 而且也可以从更有经验的人那里学习新东西。
我对 Cython 的熟练程度非常有限。我对 C 的了解很糟糕（实际上几乎为零）。我所知道的关于 SIMD 指令的一切都可以用大字写在邮票上。
我在 StackOverflow 上来回搜索并找到了类似问题的答案，其中许多问题都使用了非常先进的 SIMD 解决方案。但由于我对 SIMD 一无所知，因此我无法修改它们以满足我的需要。
我使用这些标志编译下面发布的 Cython 脚本：
-O3 -ffast-math -funroll-loops -ftree-vectorize …旨在提供高性能数字运算的 CPU 最终会采用某种向量指令集。基本上有两种：
SIMD。这在概念上很简单，例如，您不仅拥有一组 64 位寄存器及其上的操作，还拥有第二组 128 位寄存器，并且可以同时对两个 64 位值的短向量进行操作。它在实现中变得复杂，因为您还希望可以选择对四个 32 位值进行操作，然后新一代 CPU 提供 256 位向量，这需要一套全新的指令等。
较旧的 Cray 风格向量指令，其中向量一开始很大，例如 4096 位，但同时操作的元素数量是透明的，并且要在给定操作中使用的元素数量是指令参数。这个想法是，你预先减少一点复杂性，以避免以后出现复杂性。
有人认为选项 2 更好，并且这些论点似乎有道理，例如https://www.sigarch.org/simd-instructions-considered-harmful/
至少乍一看，选项 2 似乎可以完成选项 1 可以做的所有事情，而且更容易，而且总体上更好。
是否存在相反情况的工作负载？SIMD 指令在哪里可以完成 Cray 式向量无法完成的任务，或者可以更快或使用更少的代码完成任务？