x86最大/最小asm指令？

Question

是否有任何可以加速Core i7架构上双/整数矢量最小/最大值计算的asm指令？

更新：

我没想到会这么丰富的解答，谢谢。 所以我看到最大/最小值可能没有分支。 我有子问题：

有没有一种有效的方法来获得最大的双数的索引？

Answer 1

对于32位有符号/无符号整数，SSE4具有PMAXSD或PMAXUD，这可能很有用。

SSE2具有MAXPD和MAXSD其中比较和跨地区对双打的，所以你按照N/2-1 MAXPDs一个MAXSD得到n的向量的最大值，与负载和操作的通常交错。

有以上MIN等值。

对于双的情况下，你可能不会做的更好汇编比SSE模式半像样的C++编译器：

peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max 
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse 
peregrino:$ time bin/min_max 
0,40 

real 0m0.874s 
user 0m0.796s 
sys 0m0.004s 
peregrino:$ time bin/min_max_sse 
0,40 

real 0m0.457s 
user 0m0.404s 
sys 0m0.000s 

其中min_max计算的500个双打阵列的最小值和最大值用天真的循环10万次：

bool min_max (double array[], size_t len, double& min, double& max) 
{ 
    double min_value = array [ 0 ]; 
    double max_value = array [ 0 ]; 

    for (size_t index = 1; index < len; ++index) { 
     if (array [ index ] < min_value) min_value = array [ index ]; 
     if (array [ index ] > max_value) max_value = array [ index ]; 
    } 

    min = min_value; 
    max = max_value; 
} 

---

针对两部分，传统的优化删除从最大操作分支是比较值，获得标志作为一个唱（比如给出0或1），减去1（给出0或0xffff_ffff），'和'与两个可能结果的异或，所以你得到相当于(a > best ? (current_index^best_index) : 0)^best_index)。我怀疑有一种简单的SSE方式来做到这一点，只是因为SSE倾向于使用压缩值而不是标记值;有一些水平索引操作，所以你可以尝试找到最大值，然后从原始向量中的所有元素中减去该值，然后收集符号位，并且签名的零将对应于最大值的索引，但这可能会除非您使用短裤或字节，否则不会有所改进。

Answer 2

来自SSE的MAXPS和MINPS都对打包的单精度浮点数进行操作。 PMAXSW，PMINSW，PMAXUB和PMINUB均可对包装的8位字进行操作，无论是有符号还是无符号。请注意，这些比较两个输入SSE寄存器或地址位置元素明智并将结果存储到一个SSE寄存器或内存位置。

MAXPS和MINPS的SSE2版本应该可以在双精度浮点上工作。

您使用哪种编译器和优化标志？如果您的目标支持它们，gcc 4.0和更高版本应自动矢量化操作，而早期版本可能需要特定的标志。

Answer 3

，如果您使用的是英特尔的IPP库，你可以使用矢量statistical functions计算矢量最小/最大（除其他事项外）

Answer 4

在回答你的第二个问题：在大多数平台上，有一些已经包含优化库这个操作的实现（以及大多数其他简单的向量操作）。 使用它们。

• 在OS X上，存在vDSP_maxviD()和cblas_idamax()的Accelerate.framework
• 英特尔编译器包括IPP和MKL库，具有高性能的实现，包括cblas_idamax()
• 大多数Linux系统将有cblas_idamax()在BLAS图书馆中，根据其出处可能调整或可能不调整;关心性能的用户通常会有很好的实现（或者可以被说服去安装一个）
• 如果一切都失败了，你可以使用ATLAS（自动调优线性代数软件）在目标平台
上获得不错的性能实现

Answer 5

对于您的第二个问题，您可能需要考虑收集和存储这些数据的方式。

您可以将数据存储在保持数据始终排序的B树中，只需要进行对数比较操作。

然后你总是知道最大值是多少。

http://en.wikipedia.org/wiki/B_tree

Answer 6

更新：我只是意识到，你说在第2部分“阵列”，而不是“矢量”我会在这里反正如果离开这非常有用。

---

重新：两部分：找到最大/最小元件的在SSE矢量的索引：

• 做一个水平最大。对于2个double元素的128b向量，这只是一个shufpd + maxpd将结果广播到这两个元素。

  对于其他情况，它当然会采取更多步骤。有关想法，请参阅Fastest way to do horizontal float vector sum on x86，将addps替换为maxps或minps。 （但请注意，16位整数是特殊的，因为你可以使用SSE4 phminposuw。对于最大，从255减去）

• 执行矢量原始载体，每一个元素是最大的载体之间的填充比较。

  （pcmpeqq整数位模式或通常cmpeqpd都将为double情况下工作）。

• int _mm_movemask_pd (__m128d a) (movmskpd)以比较结果作为整数位图。
• 位扫描（bsf）它用于（第一次）匹配：index = _bit_scan_forward(cmpmask)。如果使用整数比较，则cmpmask = 0是不可能的（因为即使它们是NaN，至少一个元素也会匹配）。

这应该编译成只有6条指令（包括一个movapd）。是的，刚刚检查the Godbolt compiler explorer，它确实与SSE。

#include <immintrin.h> 
#include <x86intrin.h> 

int maxpos(__m128d v) { 
    __m128d swapped = _mm_shuffle_pd(v,v, 1); 
    __m128d maxbcast = _mm_max_pd(swapped, v); 
    __m128d cmp = _mm_cmpeq_pd(maxbcast, v); 
    int cmpmask = _mm_movemask_pd(cmp); 
    return _bit_scan_forward(cmpmask); 
} 

请注意，_mm_max_pd is not commutative with NaN inputs。如果NaN可能，并且您不关心Intel Nehalem的性能，则可以考虑使用_mm_cmpeq_epi64来比较位模式。尽管如此，从float到vec-int的旁路延迟在Nehalem上是一个问题。

NaN！= NaN在IEEE浮点，因此_mm_cmpeq_pd结果掩码可能在全NaN情况下全部为零。

您可以在2元素的情况下始终得到0或1的另一件事是用cmpmask >> 1替换位扫描。 （bsf奇怪，输入=全零）。