什么是在x86上提供无分支FP min和max的指令?
引用(感谢作者开发和共享算法!):
由于现代浮点指令集可以在没有分支的情况下计算最小值和最大值
作者的相应代码就是
dmnsn_min(double a, double b) { return a < b ? a : b; }
我熟悉例如_mm_max_ps
,但这是一个向量指令。 上面的代码显然是用于标量forms。
题:
- 什么是x86上的标量无分支minmax指令? 这是一系列指令吗?
- 假设它将被应用,或者如何调用它是否安全?
- 关于min / max的无分支问题是否有意义? 根据我的理解,对于光线跟踪器和/或其他视觉软件,给定光线盒交叉例程,分支预测器没有可靠的模式来拾取,因此消除分支确实有意义。 我是对的吗?
- 最重要的是,所讨论的算法是围绕(+/-)INFINITY进行比较而建立的。 这是可靠的,我们正在讨论的(未知)指令和浮点标准吗?
以防万一:我熟悉在C ++中使用min和max函数 ,相信它是相关的,但不是我的问题。
大多数向量FP指令具有标量等价物。 MINSS / MAXSS / MINSD / MAXSD是你想要的。 它们按照您的预期方式处理+/- Infinity。
MINSS a,b
完全实现(a
(a根据IEEE规则
,包含有关零符号,NaN和无穷大的所有内容。 (即它保持源操作数b
,无序。)这意味着编译器可以将它们用于std::min(b,a)
和std::max(b,a)
,因为这些函数基于相同的表达式。
MAXSS a,b
完全实现(b
(b ,再次保持源操作数无序。 使用
maxss xmm0, [rsi]
循环数组时maxss xmm0, [rsi]
如果数组包含任何NaN maxss xmm0, [rsi]
将导致NaN,通过计算传播NaN,这与其他FP操作一样正常。 它还意味着您可以使用NaN(使用pcmpeqd xmm0,xmm0
)而不是-Inf或第一个数组元素初始化xmm0
; 这可能会简化处理可能空的列表。
不要试图在标量浮点数上使用_mm_min_ss
; 内在函数仅适用于__m128
操作数 ,并且英特尔的内在函数不提供任何方法来使标量浮点数进入__m128
的低元素而不会使高元素归零或以某种方式执行额外的工作。 即使最终结果不依赖于上层元素中的任何内容,大多数编译器实际上也会发出无用的指令来执行此操作。 没有像__m256 _mm256_castps128_ps256 (__m128 a)
这样只是将一个浮点数转换为__m128
,而上层元素中有垃圾。 我认为这是一个设计缺陷。 :/
但幸运的是,您不需要手动执行此操作,编译器知道如何使用SSE / SSE2 min / max。 只要写你的C就可以了。 您的问题中的function是理想的:如下所示(Godbolt链接):
// can and does inline to a single MINSD instruction, and can auto-vectorize easily static inline double dmnsn_min(double a, double b) { return a < b ? a : b; }
注意它们与NaN的不对称行为 :如果操作数是无序的,则dest = src(即,如果任一操作数是NaN,则它采用第二个操作数)。 这对于SIMD条件更新非常有用,请参见下文。
(如果它们中的任何一个是NaN,则a
和b
是无序的。这意味着a ,
a==b
, a>b
都是假的。请参阅Bruce Dawson关于许多FP陷阱的浮点系列文章 。)
相应的_mm_min_ss
/ _mm_min_ps
内在函数可能有也可能没有此行为,具体取决于编译器。
我认为内在函数应该具有与asm指令相同的操作数顺序语义,但gcc已经将操作数视为_mm_min_ps
,即使没有-ffast-math
很长一段时间,gcc4.4或者更早。 GCC 7最终改变它以匹配ICC和clang。
英特尔的在线内在函数查找器没有记录该函数的行为,但它可能不应该是详尽无遗的。 asm insn ref手册并没有说内在没有那个属性; 它只是将_mm_min_ss
列为_mm_min_ss
的内在函数。
当我搜索"_mm_min_ps" NaN
,我发现了这个真实的代码以及使用内在函数来处理NaN的其他一些讨论,所以很明显很多人都希望内在函数像asm指令一样。 (这是我昨天写的一些代码,我已经考虑过把它写成一个自我回答的问答。)
鉴于存在这种长期存在的gcc错误,想要利用MINPS的NaN处理的可移植代码需要采取预防措施。 许多现有Linux发行版上的标准gcc版本将错误编译您的代码,如果它取决于_mm_min_ps
的操作数_mm_min_ps
。 所以你可能需要一个#ifdef
来检测实际的gcc(不是clang等),还有另一种选择。 或者首先采用不同的方式:/或者使用_mm_cmplt_ps
和布尔AND / ANDNOT / OR。
启用-ffast-math
也会使_mm_min_ps
在所有编译器上_mm_min_ps
交换。
像往常一样,编译器知道如何使用指令集正确实现C语义 。 无论如何,MINSS和MAXSS 都比你用分支做的任何东西都快 ,所以只需编写可以编译成其中一个的代码。
可交换_mm_min_ps
问题仅适用于内在:gcc确切地知道MINSS / MINPS如何工作,并使用它们来正确实现严格的FP语义(当你不使用-ffast-math时)。
您通常不需要做任何特殊的事情来从编译器中获取合适的标量代码。 如果您打算花时间关注编译器使用的指令,那么如果编译器没有这样做,您应该首先手动向量化代码。
(在极少数情况下,分支是最好的,如果条件几乎总是单程并且延迟比吞吐量更重要.MINPS延迟是~3个周期,但完美预测的分支为关键的依赖链增加0个周期路径。)
在C ++中,使用std::min
和std::max
,它们是根据>
或<
定义的,并且对fmin
和fmax
所做的NaN行为没有相同的要求。 除非你需要他们的NaN行为,否则避免使用fmin
和fmax
。
在C中,我认为只需编写自己的min
和max
函数(如果你安全地执行它,就可以编写宏)。
关于Godbolt编译器资源管理器的C&asm
float minfloat(float a, float b) { return (a
如果你想自己使用_mm_min_ss
/ _mm_min_ps
,编写代码,即使没有-ffast-math,编译器也能使编译好。
如果您不想要NaN,或者想要特别处理它们,请写下类似的东西
lowest = _mm_min_ps(lowest, some_loop_variable);
所以保持lowest
的寄存器可以就地更新(即使没有AVX)。
利用MINPS的NaN行为:
说你的标量代码是这样的
if(some condition) lowest = min(lowest, x);
假设条件可以使用CMPPS进行矢量化,因此您有一个元素向量,其中所有位都设置或全部清除。 (或者你可以直接使用ANDPS / ORPS / XORPS浮点数,如果你只关心它们的符号并且不关心负零。这会在符号位中创建一个真值,其他地方都有垃圾.BLENDVPS只看起来在符号位,所以这可能非常有用。或者你可以用PSRAD xmm, 31
广播符号位。)
实现这一点的直接方法是根据条件掩码将x
与+Inf
混合。 或者newval = min(lowest, x);
并将newval融入lowest
。 (BLENDVPS或AND / ANDNOT / OR)。
但诀窍是所有一位都是NaN,而按位OR会传播它 。 所以:
__m128 inverse_condition = _mm_cmplt_ps(foo, bar); __m128 x = whatever; x = _mm_or_ps(x, condition); // turn elements into NaN where the mask is all-ones lowest = _mm_min_ps(x, lowest); // NaN elements in x mean no change in lowest // REQUIRES NON-COMMUTATIVE _mm_min_ps: no -ffast-math // AND DOESN'T WORK AT ALL WITH MOST GCC VERSIONS.
所以只有SSE2,我们用两个额外的指令(ORPS和MOVAPS)完成了条件MINPS,除非循环展开允许MOVAPS消失。
没有SSE4.1 BLENDVPS的替代方案是ANDPS / ANDNPS / ORPS混合,加上额外的MOVAPS。 无论如何,ORPS比BLENDVPS更有效(在大多数CPU上它都是2 uops)。
彼得·科德斯的答案很棒,我只是觉得我会加入一些较短的逐点答案:
- 什么是x86上的标量无分支minmax指令? 这是一系列指令吗?
我指的是minss
/ minsd
。 甚至其他没有这些指令的架构也应该能够通过条件移动无分支地完成。
- 假设它将被应用,或者如何调用它是否安全?
gcc
和clang
都会优化(a < b) ? a : b
(a < b) ? a : b
到minss
/ minsd
,所以我不打扰使用内在函数。 但是不能和其他编译器说话。
- 关于min / max的无分支问题是否有意义? 根据我的理解,对于光线跟踪器和/或其他视觉软件,给定光线盒交叉例程,分支预测器没有可靠的模式来拾取,因此消除分支确实有意义。 我是对的吗?
个人a < b
测试几乎完全不可预测,因此避免分支是非常重要的。 if (ray.dir.x != 0.0)
是非常可预测的,因此避免使用这些分支并不重要,但它确实缩小了代码大小并使其更易于矢量化。 最重要的部分可能是删除分歧。
- 最重要的是,所讨论的算法是围绕(+/-)INFINITY进行比较而建立的。 这是可靠的,我们正在讨论的(未知)指令和浮点标准吗?
是的, minss
/ minsd
行为与(a < b) ? a : b
完全相同(a < b) ? a : b
(a < b) ? a : b
,包括他们对无穷大和NaNs的治疗。
另外,我在你引用的那篇文章中写了一篇后续文章 ,详细介绍了NaNs和min / max。