10

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

更新：

没想到这么丰富的答案，谢谢。所以我看到 max/min 可以在没有分支的情况下完成。我有子问题：

有没有一种有效的方法来获取数组中最大双精度数的索引？

4

6 回答 6

13

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

SSE2 具有MAXPD并且MAXSD在成对的双精度之间和之间进行比较，因此您遵循 n/2-1 MAXPD 和一个 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 个数组的 min 和 max 100,000 次：

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），减去一个（给出 0 或 0xffff_ffff）并使用两个可能结果的异或，所以你得到( a > best ? ( current_index ^ best_index ) : 0 ) ^ best_index ). 我怀疑是否有一种简单的 SSE 方法可以做到这一点，仅仅是因为 SSE 倾向于对打包值而不是标记值进行操作；有一些水平索引操作，所以你可以尝试找到最大值，然后从原始向量中的所有元素中减去它，然后收集符号位，零符号位将对应于最大值的索引，但这可能除非您使用短裤或字节，否则不会有任何改进。

于 2009-12-28T15:01:23.907 回答
4

SSE 的 MAXPS 和 MINPS 都对压缩的单精度浮点数进行运算。PMAXSW、PMINSW、PMAXUB 和 PMINUB 都对压缩的 8 位字（有符号或无符号）进行操作。请注意，它们按元素比较两个输入 SSE 寄存器或地址位置，并将结果存储到 SSE 寄存器或内存位置。

SSE2 版本的 MAXPS 和 MINPS 应该适用于双精度浮点数。

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

于 2009-12-28T15:00:35.047 回答
2

如果您使用英特尔的IPP库，您可以使用矢量统计函数 来计算矢量最小值/最大值（除其他外）

于 2009-12-28T15:03:05.323 回答
2

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

  • 在 OS X 上，Accelerate.framework 中有vDSP_maxviD( )和cblas_idamax( )
  • 英特尔编译器包括 IPP 和 MKL 库，它们具有高性能实现，包括cblas_idamax( )
  • 大多数 Linux 系统都包含cblas_idamax( )BLAS 库，根据其出处可能会或可能不会进行良好调整；关心性能的用户通常会有一个很好的实现（或者可以被说服安装一个）
  • 如果一切都失败了，您可以使用 ATLAS（自动调谐线性代数软件）在目标平台上获得不错的性能实现
于 2009-12-29T22:31:43.513 回答
1

更新：我刚刚意识到你在第 2 部分中说的是“数组”，而不是“向量”。无论如何我都会把它留在这里，以防它有用。

回复：第二部分：在 SSE 向量中找到最大/最小元素的索引：

  • 做一个水平最大值。对于 2 个double元素的 128b 向量，只需一个shufpd+maxpd即可将结果广播留给两个元素。

    对于其他情况，当然会采取更多的步骤。有关想法，请参阅在 x86 上进行水平浮点向量求和的最快方法，替换addps为maxpsor 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 条指令（包括 a movapd）。是的，刚刚检查了 Godbolt 编译器资源管理器，它确实使用了 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它与 NaN 输入不可交换。如果 NaN 是可能的，并且您不关心 Intel Nehalem 的性能，您可以考虑使用_mm_cmpeq_epi64来比较位模式。不过，从 float 到 vec-int 的旁路延迟是 Nehalem 的一个问题。

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

在 2 元素的情况下，您可以做的另一件事总是得到 0 或 1 是用cmpmask >> 1. （bsf输入=全零很奇怪）。

于 2017-08-07T07:58:33.617 回答
-1

在回答您的第二个问题时，您可能值得考虑一下您收集和存储这些数据的方式。

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

然后，您始终知道最大值在哪里。

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

于 2012-02-16T03:26:58.863 回答