gpt4 book ai didi

assembly - 如何实现浮点值的totalOrder谓词?

转载 作者:行者123 更新时间:2023-12-04 17:19:33 26 4
gpt4 key购买 nike

IEEE 754规范在第5.10节中定义了一个总订单,我想在组装中实现该总订单。

the Wikipedia description中,这听起来很像可以实现无分支或几乎无分支的实现,但是我一直无法提出一种不错的方法。而且我在主要的编程语言中找不到任何符合规范的实现


比较两个浮点数时,它充当≤操作,除了totalOrder(−0,+0)¬¬totalOrder(+0,−0)以及相同浮点数的不同表示按其顺序排序指数乘以符号位。然后,通过对-qNaN <-sNaN <数字<+ sNaN <+ qNaN进行排序,将排序扩展到NaN,同一类中的两个NaN之间的排序基于这些数据的整数有效负载乘以符号位。


先检查NaN然后跳转到浮点比较或处理NaN情况是否有意义,还是将浮点值移到整数寄存器并在那里进行所有操作更有意义?

(至少通过阅读说明,可以感觉到规范作者努力允许使用整数指令直接实现。)

在x86-64处理器上实现浮点总数的“最佳”方法是什么?

最佳答案

如果将FP位模式作为符号/幅度整数(包括-0 < +0和NaN位模式1)进行比较,则所有这些工作就可以了。这就是为什么像binary64 (double)这样的IEEE格式使用偏差指数并将字段按该顺序排列的原因之一。 (另一个是通过nextafter++在位模式上方便地实现--的方法。)

可以用2的补码整数比较有效地实现:


如果两个符号均已清除:非负数Just Work
如果只设置了一个符号位:任何负数都小于任何非负数,包括-0.0 < +0.0作为0x80000000 < 0x00000000,因此2的补码x <= y起作用。
如果两个都设置了符号位((x&y)>>63):2的补码x<y是符号/幅度FP x>y。在x86 asm中,您可以避免移动,而只需看一下SF,或者使用SIMD元素的高位。

在不弄乱==情况的情况下处理这个问题很棘手:您不能仅对x&y结果进行XOR <签名;当他们比较相等时,它将翻转它。如果两个输入均为负,则为<=,其他情况为<。我不确定这是否可用于排序。




使用SSE4.2 pcmpgtq,您可以在其普通XMM寄存器中使用双FP值,或者对于32位浮点型,在pcmpgtd中使用SSE2(为x86-64保证)。 (请注意,与pcmpgtq相比,pcmpgtd相对较慢:端口更少,延迟更长。https://agner.org/optimize/。例如,在Skylake上,1 p5 uop的延迟为3c,而pcmpgtd和pcmpeqq为1 uop的p0 / p1的延迟为1。周期延迟。)

我们不能仅使用一个pcmpgtq +符号修复来处理按位相等的情况。
不管输入是正还是负,x1 bitwise_eq x0给出的pcmpgtq结果均为0。根据总顺序,如果您希望0或1表示sign(x0&x1)>>=<,则基于<=翻转它会产生不一致的行为。但是不幸的是,FP比较的-0.0 == +0.0行为意味着我们必须对等于FP的情况进行特殊处理,而不仅仅是FP无序的情况。

您不需要汇编,只需在C语言中将pun键入uint64_t即可,使编译器可能使用movq rax, xmm0或对向量reg使用内在函数。

但是,如果您正在使用asm,则可以考虑进行FP比较并在ZF = 1上分支(将其设置为无序或相等),然后再执行整数。如果您期望NaN和完全相等(包括+-0.0 == -+0.0)很少见,那么这可能会很好。请注意,对于the ucomisd docs中的无序ZF,CF,PF = 1,1,1。所有x86 FP都直接或通过fcom / fnstsw ax / lahf以相同的方式比较设置标志。

例如,独立版本可能看起来像这样。 (在内联时简化,例如如果调用者分支,则直接使用jb而不是setb分支):

totalOrder:   ; 0/1 integer in EAX = (xmm0 <= xmm1 totalOrder)
xor eax, eax
ucomisd xmm0, xmm1 ; ZF=0 implies PF=0 (ordered) so just check ZF
jz .compare_as_integer ; unordered or FP-equal
; else CF accurately reflects the < or > (total) order of xmm0 vs. xmm1
setb al ; or branch with jb
ret

;; SSE4.2, using AVX 3-operand versions. Use movaps as needed for non-AVX
### Untested
; Used for unordered or FP-equal, including -0.0 == +0.0
; but also including -1.0 == -1.0 for example
.compare_as_integer: ; should work in general for any sign/magnitude integer
vpcmpgtq xmm2, xmm1, xmm0 ; reversed order of comparison: x1>x0 == x0<x1
vpand xmm3, xmm1, xmm0 ; we only care about the MSB of the 64-bit integer
vpxor xmm2, xmm3 ; flip if x0 & x1 are negative

vpcmpeqq xmm1, xmm0
vpor xmm2, xmm1
; top bits of XMM2 hold the boolean result for each SIMD element
; suitable for use with blendvpd

vmovmskpd eax, xmm2 ; low bit of EAX = valid, high bit might be garbage
and eax, 1 ; optional depending on use-case
; EAX=1 if x0 bitwise_eq x1 or sign/magnitude x1 > x0
ret


使用AVX512VL, vpternlogq可以替换所有3个AND / XOR / OR操作;它可以实现3个输入的任意布尔函数。 (y_gt_x) ^ (x&y) | y_eq_x

如果没有SSE4.2,或者没有标量无分支策略,我就想到了这一点。 (例如,如果值实际上在内存中,那么您可以执行 mov加载,而不是XMM规则中的 movq)。

;; works on its own, or as the fallback after ucomisd/jz
compare_as_integer:
movq rcx, xmm0
movq rsi, xmm1

xor eax, eax
cmp rcx, rsi
; je bitwise equal special case would simplify the rest
setl al ; 2's complement x < y
sete dl
and rcx, rsi ; maybe something with TEST / CMOVS?
shr rcx, 63
xor al, cl ; flip the SETL result if both inputs were negative
or al, dl ; always true on bitwise equal
ret


setl和8位 xoror写入AL后,即使在P6-系列上,EAX should make it safe to read EAX without a partial-reg stall的异或归零。 ( Why doesn't GCC use partial registers?)。在大多数其他CPU上,唯一的缺点是对RDX的旧值有错误的依赖关系,而我在 sete dl之前并没有破坏它的旧值。如果我先对EDX进行了Xor归零,则可以 xoror进入EAX。

分支策略可以像这样工作:

;; probably slower unless data is predictable, e.g. mostly non-negative
compare_as_integer_branchy:
movq rcx, xmm0
movq rsi, xmm1

xor eax, eax ; mov eax,1 with je to a ret wouldn't avoid partial-register stalls for setl al
cmp rcx, rsi
je .flip_result ; return 1
setl al ; 2's complement x < y

test rcx, rsi
js .flip_result ; if (x&y both negative)
ret

.flip_result: ; not bitwise EQ, and both inputs negative
xor al, 1
ret


如果需要,可以混合并匹配部分内容;可以沿非等距路径使用AND / SHR / XOR代替 test+js



如果在分支结果的情况下进行内联,则可以在特殊情况处理之前放置common(?)-case(有限且不相等)分支。但是,特殊情况包括有序 <,因此ZF = 1上的一个希望可预测的分支(包括PF = 1无序情况)可能仍然是一个好主意。

    ucomisd  xmm1, xmm0
ja x1_gt_x0 ; CF==0 && ZF==0
; maybe unordered, maybe -0 vs +0, maybe just x1 < x0




脚注1:NaN编码是总订单的一部分

FP值(及其符号/幅度编码)在零附近对称。即使对于NaN,符号位始终是符号位,因此可以用相同的方式处理。


最小的幅度当然是+ -0.0:所有指数和尾数位均为零。
次法线具有零指数字段(最小值),表示尾数的前导零。显式部分不为零。大小与尾数呈线性关系。 (实际上,零只是次常态的一种特殊情况。)
归一化的数字范围为指数= 1到指数 +-无穷大有指数=全1,尾数= 0
+-NaN具有指数=全1,尾数=非零


在x86上,sNaN清除了尾数的最高位。其余部分是至少有1个置位的有效载荷(否则为Inf)。
在x86上,qNaN具有尾数集的最高位。其余就是有效载荷



https://cwiki.apache.org/confluence/display/stdcxx/FloatingPoint(从 Are the bit patterns of NaNs really hardware-dependent?链接)显示了一些其他ISA上的一些sNaN和qNaN编码。有些与x86不同,但是POWER和Alpha的尾数MSB设置为qNaN,因此它们的整数幅度大于任何sNaN。

PA-RISC选择了另一种方法,因此针对(过时的)ISA实施总订单谓词将需要针对FP比较无序情况进行额外的工作。在进行整数比较之前,如果两个值中的任何一个都是任何一种NaN,则将这两个值中的该位翻转可能会起作用。

(我之所以这样说是因为相同的算法可能会用在x86上可能不会专用的高级语言中。但是您可能只想保留它,并始终以相同的方式处理相同的二进制位模式,即使那意味着qNaN


PS:我知道“ significand”在技术上更正确,但是“ mantissa”的音节较少,我更喜欢它,并且在这种情况下很好理解。

关于assembly - 如何实现浮点值的totalOrder谓词?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59348310/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com