NEON SIMD 中设置位的总和
Aggregate sum for set bits in NEON SIMD
我有一个对大量字节数组进行运算的算法。作为预处理步骤,我需要为给定的索引创建一个计数,其中的位是到目前为止在数组中设置的频率。
我可以使用以下(伪)代码在 C 中执行此操作:
input: uint8_t values[COUNT];
output: uint32_t bitsum[COUNT+1][8];
(bitsum[i][x] is the counter for the x-th bit being set in
the PRECEEDING i bytes -- this makes bitsum[0][x] == 0)
// we skip first row
for (int i=1; i < COUNT+1; i++) {
for (int bit=0; bit < 8; bit++) {
bitsum[i][bit] = bitsum[i-1][bit];
if (values[i-1] & (1 << bit) != 0) {
bitsum[i][bit]++;
}
}
}
不过,我希望使用 NEON SIMD 可以更快地实现这一点。不幸的是,我对此很陌生,所以我无法解决这个问题(还?)并寻求帮助。甚至可以在 NEON 中执行此操作吗?
更新:
试图在 C 中加速此代码,我相信以下方法是最快的(当然没有展开内部 for 循环):
// pre-calculate lookup-table
uint16_t lookup[256][8];
for (int value=0; value < 256; value++) {
for (int bit=0; bit < 8; bit++) {
if (value & (1 << bit) != 0) {
lookup[value][bit]++;
}
}
}
// create sum
for (int i=1; i < COUNT+1; i++) {
for (int bit=0; bit < 8; bit++) {
bitsum[i][bit] = bitsum[i-1][bit] + lookup[values[i-1]][bit];
}
}
这看起来对于 SIMD 来说是理想的,除了查找-table 访问 - 至少我找不到在 NEON 中执行此操作的方法。
您可以使用 VTBL
和 VTBX
指令在 NEON 中执行 table 查找,但它们仅适用于查找条目很少的 table。在针对 NEON 进行优化时,通常最好寻找一种在 运行 时间计算值的方法,而不是使用 table.
在此示例中,计算 运行 时间的查找非常简单。功能本质上是
int lookup(int val, int bit) { return (val & (1<<bit) >> bit); }
可以轻松转换为 NEON SIMD。
因此,您的函数可以像这样使用 NEON 内在函数来实现:
#include <arm_neon.h>
void f(uint32_t *output, const uint8_t *input, int length)
{
static const uint8_t mask_vals[] = { 0x1, 0x2, 0x4, 0x8,
0x10, 0x20, 0x40, 0x80 };
/* NEON shifts are left shifts, and we want a right shift,
so use negative numbers here */
static const int8_t shift_vals[] = { 0, -1, -2, -3, -4, -5, -6, -7 };
/* constants we need in the main loop */
uint8x8_t mask = vld1_u8(mask_vals);
int8x8_t shift = vld1_s8(shift_vals);
/* accumulators for results, bits 0-3 in cumul1, bits 4-7 in cumul2 */
uint32x4_t cumul1 = vdupq_n_u32(0);
uint32x4_t cumul2 = vdupq_n_u32(0);
for (int i = 0; i < length; i++)
{
uint8x8_t v = vld1_dup_u8(input+i);
/* this gives 0 or 1 in each lane, depending on whether the
appropriate bit is set */
uint8x8_t incr = vshl_u8(vand_u8(v, mask), shift);
/* widen to 16 bits */
uint16x8_t incr_w = vmovl_u8(incr);
/* increment the accumulators */
cumul1 = vaddw_u16(cumul1, vget_low_u16(incr_w));
cumul2 = vaddw_u16(cumul2, vget_high_u16(incr_w));
/* store the accumulator values */
vst1q_u32(output + i*8, cumul1);
vst1q_u32(output + i*8 + 4, cumul2);
}
}
免责声明:此代码可以编译,但我尚未对其进行测试。
我有一个对大量字节数组进行运算的算法。作为预处理步骤,我需要为给定的索引创建一个计数,其中的位是到目前为止在数组中设置的频率。
我可以使用以下(伪)代码在 C 中执行此操作:
input: uint8_t values[COUNT];
output: uint32_t bitsum[COUNT+1][8];
(bitsum[i][x] is the counter for the x-th bit being set in
the PRECEEDING i bytes -- this makes bitsum[0][x] == 0)
// we skip first row
for (int i=1; i < COUNT+1; i++) {
for (int bit=0; bit < 8; bit++) {
bitsum[i][bit] = bitsum[i-1][bit];
if (values[i-1] & (1 << bit) != 0) {
bitsum[i][bit]++;
}
}
}
不过,我希望使用 NEON SIMD 可以更快地实现这一点。不幸的是,我对此很陌生,所以我无法解决这个问题(还?)并寻求帮助。甚至可以在 NEON 中执行此操作吗?
更新:
试图在 C 中加速此代码,我相信以下方法是最快的(当然没有展开内部 for 循环):
// pre-calculate lookup-table
uint16_t lookup[256][8];
for (int value=0; value < 256; value++) {
for (int bit=0; bit < 8; bit++) {
if (value & (1 << bit) != 0) {
lookup[value][bit]++;
}
}
}
// create sum
for (int i=1; i < COUNT+1; i++) {
for (int bit=0; bit < 8; bit++) {
bitsum[i][bit] = bitsum[i-1][bit] + lookup[values[i-1]][bit];
}
}
这看起来对于 SIMD 来说是理想的,除了查找-table 访问 - 至少我找不到在 NEON 中执行此操作的方法。
您可以使用 VTBL
和 VTBX
指令在 NEON 中执行 table 查找,但它们仅适用于查找条目很少的 table。在针对 NEON 进行优化时,通常最好寻找一种在 运行 时间计算值的方法,而不是使用 table.
在此示例中,计算 运行 时间的查找非常简单。功能本质上是
int lookup(int val, int bit) { return (val & (1<<bit) >> bit); }
可以轻松转换为 NEON SIMD。
因此,您的函数可以像这样使用 NEON 内在函数来实现:
#include <arm_neon.h>
void f(uint32_t *output, const uint8_t *input, int length)
{
static const uint8_t mask_vals[] = { 0x1, 0x2, 0x4, 0x8,
0x10, 0x20, 0x40, 0x80 };
/* NEON shifts are left shifts, and we want a right shift,
so use negative numbers here */
static const int8_t shift_vals[] = { 0, -1, -2, -3, -4, -5, -6, -7 };
/* constants we need in the main loop */
uint8x8_t mask = vld1_u8(mask_vals);
int8x8_t shift = vld1_s8(shift_vals);
/* accumulators for results, bits 0-3 in cumul1, bits 4-7 in cumul2 */
uint32x4_t cumul1 = vdupq_n_u32(0);
uint32x4_t cumul2 = vdupq_n_u32(0);
for (int i = 0; i < length; i++)
{
uint8x8_t v = vld1_dup_u8(input+i);
/* this gives 0 or 1 in each lane, depending on whether the
appropriate bit is set */
uint8x8_t incr = vshl_u8(vand_u8(v, mask), shift);
/* widen to 16 bits */
uint16x8_t incr_w = vmovl_u8(incr);
/* increment the accumulators */
cumul1 = vaddw_u16(cumul1, vget_low_u16(incr_w));
cumul2 = vaddw_u16(cumul2, vget_high_u16(incr_w));
/* store the accumulator values */
vst1q_u32(output + i*8, cumul1);
vst1q_u32(output + i*8 + 4, cumul2);
}
}
免责声明:此代码可以编译,但我尚未对其进行测试。