使用 SIMD 指令快速搜索 uint8_t 向量中的特定位置

Question

我有一个由 uint8_t 符号组成的向量 V，我需要将其划分为一系列不重叠的短语。划分算法很简单：如果 V[i-1]>V[i] 且 V[i]i 是 V[i]!=V[j] 的最小位置，则位置 V[i] 是中断。这些短语被定义为跨越两个连续断点 i 和 i' 的每个子串 V[i..i'-1]。例如，给定输入 V=ataagattggc，我们获得分区 V = at aag attggc。请注意，V[i=9]=g 不是中断，因为 V[j=11]=c 较小。相反，V[i=3]=a 是一个中断，因为 V[i-1=2]>V[3]

可以通过一种简单的方式在一次扫描中对 V 进行分区。但是，我在数百 GB 的输入上运行此算法，因此实现将受益于一些矢量化。我不是 SIMD 指令方面的专家，但我认为它们可以帮助找到突破点。

我知道如何计算 V[i-1]

下面，我写了我的实现的粗略想法（为了简单起见，我省略了一些细节）。它也可能是错误的，因为我还没有彻底测试它。我认为瓶颈在最后两个循环，因为它们无法展开。

我认为关键是直接使用SIMD指令比较V[i]和V[j]，从而绕过V'的构造。但是，我不知道如何实现这一目标。

关于如何改进这个问题有什么想法吗？

size_t vec_par_neon(const uint8_t *text, off_t txt_size){

    off_t n_chuks = txt_size/16;

    for(off_t c=0, i=1;c<n_chunks;c++,i+=16){

        //check if text[i>=1] (i.e., V) differs from text[i-1]
        chunk_prev = vld1q_u8(reinterpret_cast<const uint8_t*>(&text[i - 1]));
        chunk_curr = vld1q_u8(reinterpret_cast<const uint8_t*>(&text[i]));
        uint8x16_t cmp_result = vceqq_u8(chunk_prev, chunk_curr);
        vst1q_u8(eq_res, cmp_result);


        //gather every pair (i,text[i]) such that text[i-1]!=text[i]
        int u=1;
        for(auto j=0;j<16;j++){
            diff_pos[u] = j;
            diff_sym[u] = text[i+j];
            u+=eq_res[j]==0;
        }

        if(u>1){
            //diff_sym=V' stores the equal-symbol runs 
            chunk_prev = vld1q_u8(reinterpret_cast<const uint8_t*>(&diff_sym[0]));
            chunk_curr = vld1q_u8(reinterpret_cast<const uint8_t*>(&diff_sym[1]));
            chunk_next = vld1q_u8(reinterpret_cast<const uint8_t*>(&diff_sym[2]));

            //compute every break V'[i>1] with V'[i-1]>V'[i]<V'[i+1]
            cmp_l_res = vcgtq_u8(chunk_curr, chunk_prev);
            cmp_r_res = vcgtq_u8(chunk_curr, chunk_next);
            uint8x16_t lm = vorrq_u8(cmp_l_res, cmp_r_res);
            vst1q_u8(&lm_res[1], lm);

            int o=0;//number of breaks in V'
            for(auto j=1;j<u;j++){
                lm_res[o] = j;
                o+=lm_res[j]==0;//move to the next break
            }

            //map the breaks from V' to V        
            for(auto j=0;j<o;j++){
                //the break is i+diff_pos[lm_res[j]]
            }
            
            diff_sym[0] = diff_sym[u-1];//set data for the next chunk
        }
    }
}

Answer 1

改进：

-- 无需每次都加载

chunk_prev

，只需在循环结束时保存

chunk_prev = chunk_next

即可。目前，每次迭代都会加载两个 128 位向量，因此最终会受到内存限制。

-- 不知道为什么要存储到

eq_res

，看起来这是一个本地数组，可以方便地将元素作为数组元素访问。您不应该这样做，如果需要，请使用

vget_lane

来获取向量的元素。但我们可以完全避免它。

-- 收集

u

的数量和位置，您可以使用具有 4 个移位位置的

vshrn_n_u16

将位压缩为同时提供位置和位置的形式（请参阅 https://community.arm.com /arm-community-blogs/b/infrastruction-solutions-blog/posts/porting-x86-vector-bitmask-optimizations-to-arm-neon )

支票

u > 1

将变为

val != 0

。使用

popcount

可以获得的点击次数，完成前两项更改后，您应该能够了解如何更改其余部分。