assembly 尝试理解AlphaDev的新排序算法：为什么我的汇编代码不能按预期工作？

cgh8pdjw 于 2023-06-30 发布在其他

关注(0)|答案(3)|浏览(79)

最近在www.example.com上发表了一篇文章nature.com，Faster sorting algorithms discovered using deep reinforcement learning，其中谈到AlphaDev发现了一种更快的排序算法。这引起了我的兴趣，我一直试图理解这个发现。
关于这个主题的其他文章是：

下面是原始sort3算法的伪代码，与AlphaDev发现的改进算法相比。

原始伪码

Memory [0] = A
Memory [1] = B
Memory [2] = C

mov Memory[0] P  // P = A
mov Memory[1] Q  // Q = B
mov Memory[2] R  // R = C

mov R S
cmp P R
cmovg P R  // R = max(A, C)
cmovl P S  // S = min(A, C)
mov S P    // P = min(A, C)
cmp S Q
cmovg Q P  // P = min(A, B, C)
cmovg S Q  // Q = max(min(A, C), B)

mov P Memory[0]  // = min(A, B, C)
mov Q Memory[1]  // = max(min(A, C), B)
mov R Memory[2]  // = max(A, C)

AlphaDev伪码

Memory [0] = A
Memory [1] = B
Memory [2] = C

mov Memory[0] P  // P = A
mov Memory[1] Q  // Q = B
mov Memory[2] R  // R = C

mov R S
cmp P R
cmovg P R  // R = max(A, C)
cmovl P S  // S = min(A, C)

cmp S Q
cmovg Q P  // P = min(A, B)
cmovg S Q  // Q = max(min(A, C), B)

mov P Memory[0]  // = min(A, B)
mov Q Memory[1]  // = max(min(A, C), B)
mov R Memory[2]  // = max(A, C)

改进集中在省略了单个移动命令mov S P。为了帮助理解，我编写了以下汇编代码。然而，我的测试表明，排序算法在 A=3，B=2和C=1时不工作，但在 A=3，B=1和C=2 时工作。
这是在Ubuntu 20.04 Desktop上编写、编译和运行的。

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 20.04.6 LTS
Release:    20.04
Codename:   focal

$ nasm -v
NASM version 2.14.02

$ ld -v
GNU ld (GNU Binutils for Ubuntu) 2.34

我的汇编代码测试...

; -----------------------------------------------------------------
;
; sort_test.asm
;
; Test for AlphaDev sorting algorithm
;
; My findings are that AlphaDev's removal of 'mov S P' doesn't work when:
;   a = 3, b = 2, c = 1
; But it does work with:
;   a = 3, b = 1, c = 2
;
; Output: The sorted values of a, b & c printed to stdout with spaces
;
; Compile & run with:
;
; nasm -f elf32 sort_test.asm && ld -m elf_i386 sort_test.o -o sort_test && ./sort_test
;
; -----------------------------------------------------------------

global _start

section .data
  a equ 3
  b equ 2
  c equ 1

section .bss
  buffer resb 5

section .text
_start:
; ------------------- ; AlphaDev pseudo-code

  mov eax, a          ; P = A
  mov ecx, b          ; Q = B
  mov edx, c          ; R = C
  mov ebx, edx        ; mov R S

  cmp eax, edx        ; cmp P R
  cmovg edx, eax      ; cmovg P R  // R = max(A, C)
  cmovl ebx, eax      ; cmovl P S  // S = min(A, C)

; The following line was in original sorting algorithm,
; but AlphaDev determined it wasn't necessary
;  mov eax, ebx       ; mov S P   // p = min(A, C)

  cmp ebx, ecx        ; cmp S Q
  cmovg eax, ecx      ; cmovg Q P  // P = min(A, B)
  cmovg ecx, ebx      ; cmovg S Q  // Q = max(min(A, C), B)

; add values to buffer with spaces
  add eax, 30h
  mov [buffer], eax
  mov [buffer+1], byte 0x20

  add ecx, 30h
  mov [buffer+2], ecx
  mov [buffer+3], byte 0x20

  add edx, 30h
  mov [buffer+4], edx

; write buffer to stdout
  mov eax, 4      ; sys_write system call
  mov ebx, 1      ; stdout file descriptor
  mov ecx, buffer ; buffer to write
  mov edx, 5      ; number of bytes to write
  int 0x80

  mov eax, 1      ; sys_exit system call
  mov ebx, 0      ; exit status 0
  int 0x80

我已经在命令行上运行了这个测试，以打印排序的结果，但是我也使用了gdb逐行遍历这个可执行文件。在调试过程中，我清楚地看到，“A”（又名 “P”，又名 “eax”）的寄存器在 A=3、B=2和C=1 时从未更新，但在 A=3、B=1和C=2 时更新。

*******************************我也不精通任何其他特定的语言，但我尝试过C，C++，JavaScript，PHP和HTML来完成小项目。基本上，我自学了我所知道的。为了达到编写这个测试的目的，我必须学习相当多的东西。因此，我肯定会犯错误或不理解问题。

无论如何，请帮助我理解为什么我在观察我是什么。

我误解了问题吗？
我是不是误解了伪代码？
将伪代码转换为汇编是不是犯了一个错误？
我的汇编代码有错误吗？
伪代码是错的吗？

assembly

来源：https://stackoverflow.com/questions/76528409/trying-to-understand-the-new-sorting-algorithm-from-alphadev-why-does-my-assemb

3条答案

按热度按时间

pgky5nke1#

TL：DR：令人困惑的是，它们只显示了3个元素排序网络中3个比较器中的最后2个，而不是完整的3个元素排序。这是非常误导性的，包括在他们的论文中的图表中。

我会使用AT&T语法（就像用GCC组装的.s文件中的cmovg %ecx, %eax），这样操作数顺序就可以匹配伪代码，目标在右边。
你是对的，我看了这篇文章，当C是最小的元素时，3元素伪代码不能正确排序。我知道x86-64 asm向后可以向前，我不只是指英特尔与。AT&T语法：P即使查看真实的代码，而不仅仅是注解，如果最小的元素以R = memory[2] = C开头，那么它也不可能以memory[0] = P结尾。
我在真正阅读你的问题之前打开了这篇文章，在浏览了这篇文章之后，我自己也注意到了这个问题，直到看到关于实际改进的部分，所以我没有看你试图复制它。但我没有任何偏见，看到一个问题，我只是想了解它自己。没有任何写P的指令可以从可能包含起始R值的值中读取，因此它无法获得该值。
这篇文章间接链接了他们发表在《自然》杂志上的论文（Faster sorting algorithms discovered using deep reinforcement learning by丹尼尔J. Mankowitz等人全文在Nature链接中。
他们在实际的论文中使用了相同的代码图像，但有一些解释性的文字和图表，根据3元素排序网络。

图3a示出了用于三个元件的最佳分选网络（参见分选网络概述的方法）。我们将解释AlphaDev如何改进圈出的网段。在各种规模的排序网络中，可以找到这种结构的许多变体，并且在每种情况下都适用相同的论点。
网络的圆圈部分（最后两个比较器）可以看作是一个指令序列，它接受一个输入序列> A，B，C>，并转换每个输入，如表2a所示（左）。**然而，线路B和C上的比较器在此运算符之前，因此保证了B ≤ C的输入序列。**这意味着计算min（A，B）而不是min（A，B，C）作为第一个输出就足够了，如表2a所示（右）。图1和图2之间的伪代码差异。图3b、c演示了AlphaDev交换移动如何在每次应用时保存一条指令。

**所以这个伪代码只用于排序网络的圈出部分，即3个比较和交换步骤中的最后2个。**在他们的博客文章中，甚至在论文的其他部分，如表2，他们使它听起来像是整个排序，而不仅仅是最后2个步骤。伪代码甚至以内存中的值开始，这是令人困惑的，在有条件地交换B和C以确保B <= C之后，情况就不是这样了。

此外，在3元素排序中，仅仅一条mov指令不太可能带来巨大的加速。Can x86's MOV really be "free"? Why can't I reproduce this at all?-它从来不是免费的（它会消耗前端带宽），但它在除Ice Lake以外的大多数最新微架构上都具有零延迟。我猜这不是他们得到了70%的加速！
使用像vpminsd dst, src1, src2（https://www.felixcloutier.com/x86/pminsd:pminsq）/vpmaxsd这样的AVX SIMD指令，使用非破坏性的单独目的地执行最小和最大的有符号双字（32位）元素，除了关键路径延迟外，没有任何节省。min(B, prev_result)仍然只是一条指令，不需要单独的寄存器拷贝（vmovdqa xmm0, xmm1），就像SSE4.1中那样，如果你正在做一个排序网络。但是当用shuffle和SIMD最小/最大比较器构建排序网络时，延迟可能会很大，我最后一次听说的是在x86-64上对大整数或FP数组进行整数排序的最新技术，而不仅仅是在标量cmov代码中保存mov！
但是，许多程序的编译并没有假设AVX可用，因为不幸的是，它并没有得到普遍支持，在过去几年中，一些低功耗的x86 CPU以及Ice Lake之前的Pentium / Celeron CPU上都缺少AVX（因此，对于低预算的桌面CPU来说，可能是2018年左右）。
他们在Nature上的论文提到了SIMD排序网络，但指出libc++ std::sort没有利用它，即使输入是float或int的数组，而不是class es和重载的operator <。

这个3元素调整是一个微优化，而不是“新的排序算法”。在AArch 64上，它可能仍然可以保存延迟，但只能节省x86上的指令

人工智能可以找到这些微优化是很好的，但是如果在min(A,C)或min(B,C)之间进行选择，它们就不会那么令人惊讶了，因为后者是B在这一点上的实际情况。
通过仔细选择更高级别的源代码来避免寄存器复制指令是人类可以做的事情，例如。_mm_movehl_ps合并目的地（第一个源操作数）的选择在我2016年关于 * Fastest way to do horizontal SSE vector sum (or other reduction) * 的回答中-请参阅编译器生成的asm # note the reuse of shuf, avoiding a movaps的评论。

以前在自动微优化方面的工作包括STOKE，这是一个随机超级优化器，它随机尝试指令序列，希望找到与测试函数输出匹配的廉价序列。搜索空间是如此之大，以至于当它需要超过3或4个指令时，它往往会错过可能的序列（斯托克自己的页面说它还没有生产就绪，只是一个研究原型）。AI是有帮助的。手工查看asm可能遗漏的优化是一项很大的工作，可以通过调整源代码来修复。
但至少对于这个3元素子问题，它只是一个微优化，而不是真正的 * 算法 * 新。它仍然只是一个3比较器排序网络。一个编译更便宜的x86-64，这是很好的。但是在一些3操作数ISA上，它们的等价物cmov（如AArch64's csel dst, src1, src2, flag_condition conditional-select）具有单独的目的地，没有mov需要保存。不过，它仍然可以保存关键路径上的延迟。
他们在《自然》杂志上的论文还展示了对可变数量的元素进行排序的算法差异，其中>= 3的情况都是从前3个元素开始排序的。也许这有助于分支预测，因为当len > 3上的最后一个分支正在解析时，这项工作可能正在进行中，以确定是否需要进行简化的4元素排序，该排序可以假设前3个元素已排序。他们说：“正是这部分程序大大节省了延迟时间。”（他们还称之为“全新”算法，我认为这对于在短的未知长度输入上使用排序网络的问题是正确的。）

赞(0）回复(0）举报 2023-06-30

hjzp0vay2#

我在AlphaDev wikipedia article上写了这篇博客文章：
Understanding DeepMind's Sorting Algorithm
它将伪组件转换为实际组件：

/   move37.S
        .equ    P,%rax
        .equ    Q,%rcx
        .equ    R,%rdx
        .equ    S,%rsi
move37: mov (%rdi),P
        mov 8(%rdi),Q
        mov 16(%rdi),R
        mov R,S
        cmp P,R
        cmovg   P,R
        cmovl   P,S
        cmp S,Q
        cmovg   Q,P
        cmovg   S,Q
        mov R,(%rdi)
        mov Q,8(%rdi)
        mov P,16(%rdi)
        ret
        .type   move37,@function
        .size   move37,.-move37
        .globl  move37

赞(0）回复(0）举报 2023-06-30

qpgpyjmq3#

Deepmind的Nature文章中AlphaDev Sort 3算法的伪代码有一个bug，当第一个数字大于其他两个相等的数字时，它会影响三个数字的排序。也就是说，A>B=C（其满足前提条件B<=C）。例如，如果输入是（2，1，1），则输出是（2，1，2）;没有分类，实际上已经损坏。
bug在第12行：cmovg Q P，其应该是cmovge Q P，以确保在这种情况下P被覆盖。重新引入原始的mov S P指令也将修复该问题，但是将使改变的目的失败。类似的错误和修复适用于本文的图3d、e、f中的Sort 8片段的伪代码（cmovl R T应该是cmovle R T）。
AlphaDev的Github上的Sort 3代码和Nature文章的Supplement G中没有这个问题，大概LLVM libc++库中的代码也没有。
一步一步：

# before first shown step  (after the B,C comparator)
P = 2
Q = 1
R = 1

# after first step
  # P=2 still  unmodified by this step, still just A
  # Q=1 still  still just B
R = 2   # max(A,C) = max(A, max(B, C)) since B<=C
S = 1   # min(A,C) = min(A, max(B, C))

 cmp S, Q(B)  is  cmp 1, 1  # the Greater condition is false
# after final step
P = 2 unchanged by cmovg Q(1), P(2)   !!!! Bug here
Q = 1 unchanged by cmovg S(1), Q(1)
# R = 2 still

cmovge Q, P将复制1，而不是保留2。对于升序排序，我们希望PQR = 1，1，2

赞(0）回复(0）举报 2023-06-30

我来回答

assembly 尝试理解AlphaDev的新排序算法：为什么我的汇编代码不能按预期工作？

3条答案

这个3元素调整是一个微优化，而不是“新的排序算法”。在AArch 64上，它可能仍然可以保存延迟，但只能节省x86上的指令

相关问题

热门标签

最新问答