选择独特/重复数据删除的SSE / AVX [英] Select unique/deduplication in SSE/AVX

问题描述

问题
是否有使用的x86 SIMD指令的任何计算上可行的方法，是一个整数集的内部寄存器的重复数据删除？

Problem
Are there any computationally feasible approaches to intra-register deduplication of a set of integers using x86 SIMD instructions?

示例
我们有一个4元组寄存器R1 = {3,9，2,9}，并且希望获得登记R2 = {3,9，2，NULL}。

Example
We have a 4-tuple register R1 = {3, 9, 2, 9}, and wish to obtain register R2 = {3, 9, 2, NULL}.

限制
Stablility 的。输入命令preservation是没有意义的。

Restrictions
Stablility. Preservation of the input order is of no significance.

输出的。然而，任何数值除去/空值必须是在寄存器的开始和/或结束：

Output. However, any removed values/NULLs must be at the beginning and/or end of the register:

• {空，1，2，3} - 确定
• {1，2，NULL，NULL} - 确定
• {空，2，NULL，NULL} - 确定
• {空，2，空，1} - 无效订单
• {NULL，NULL，NULL，NULL} - 无效输出

有明显的奖金如果已知，以产生一种特定的输出格式。请假设NULL有效均值为0（零）。

It is obviously a bonus if it is known to produce one particular output format. Please assume NULL to effectively mean 0 (zero).

概论的。必须能够容忍不存在重复的，在这种情况下，产生等同于输入寄存器的输出。

Generality. Must be able to tolerate the absence of duplicates, and in this case produce an output equivalent to the input register.

指令集的。我正在寻找的任何或所有的解决方案：SSE2，SSSE3; SSE4.x; AVX-AVX2

Instruction sets. I'm looking for solutions for any or all of: SSE2-SSSE3; SSE4.x; AVX-AVX2

推荐答案

天真的解决方案

根据马克斯（）操作原油伪code。注释跟踪数据对于第一次迭代。

Crude pseudo-code based on the Max() operation. Comments track the data for the first iteration.

A = RIN //{3, 9, 2, 9}

For i = 0 .. 3:

  B = Rotate(A, 1) //{9, 2, 9, 3}
  C = Rotate(A, 2) //{2, 9, 3, 9}
  D = Rotate(A, 3) //{9, 3, 9, 2}

  RMAX = Max(A,B) //{9, 9, 9, 9}
  RMAX = Max(RMAX, C) //{9, 9, 9, 9}
  RMAX = Max(RMAX, D) //{9, 9, 9, 9}

  ROUT[i] = RMAX[0] //ROUT = {9, null, null, null}

  TMP  = A
  MASK = Equality(RMAX, TMP) //MASK = {0, 1, 0, 1}
  MASK = Invert(MASK) //MASK = {1, 0, 1, 0}
  Clear(A)
  A = MoveMasked(TMP, MASK) //A = {3, null, 2, null}

若干思考：

A = RIN //{3, 9, 2, 9}

B = Rotate(A, 1) //{9, 2, 9, 3}
C = Rotate(A, 2) //{2, 9, 3, 9}
D = Rotate(A, 3) //{9, 3, 9, 2}

maskA = cmpeq(A,B) //{0,  0,  0,  0}
maskB = cmpeq(A,C) //{0, -1,  0, -1}
maskC = cmpeq(A,D) //{0,  0,  0,  0}

indexA = horSum( { 1,2,4,8 } * maskA ) // 0
indexB = horSum( { 1,2,4,8 } * maskB ) // 10
indexC = horSum( { 1,2,4,8 } * maskC ) // 0

// The problem is this function here
// Of the 4096 possible indexABC only a subset will occur
// Based on an enumeration of all possible indexes a pattern
// for an lookup table could possibly be found
shuffleConst = lookupShuffle( indexA, indexB, indexC )

shuffle(A, shuffleConst)

这篇关于选择独特/重复数据删除的SSE / AVX的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！