论如何用不正确的方式刷Lab

问题

在ICS Lab7的最后一个Part中，我们需要做这样两件事：

优化一个Y86指令集流水线模拟器，这部分不是本文的主角；
优化一段Y86汇编程序ncopy.ys，程序需要将一段内存（32位整数数组）复制到另一个位置，并且统计其中有多少个正数。

这个Part的最终目的是，使ncopy.ys处理一个整数所需的平均时钟周期数最少。

常规策略

首先，我们可以在指令集模拟器中实现iaddl和leave这两条指令。实现思路不复杂，iaddl相当于irmovl的读取过程搭配addl的运算过程，而leave相当于将%ebp指向的地址作为栈顶执行pop %ebp。仿照相关指令的实现方式，稍加修改后填上就可以了。

我们可以在指令集模拟器中做更多的优化，比如细化判断条件，做数据转发，改进分支预测，以去除一些不必要的bubble（流水线暂停）。这里不展开讲了。

下面来说说Y86汇编程序。

ncopy的原版长这样：

 1 ncopy:
 2     pushl %ebp
 3     rrmovl %esp, %ebp
 4     pushl %esi
 5     pushl %ebx
 6     pushl %edi
 7 
 8     mrmovl 8(%ebp), %ebx    # src
 9     mrmovl 16(%ebp), %edx   # len
10     mrmovl 12(%ebp), %ecx   # dst
11 
12     xorl %eax, %eax     # count = 0;
13     andl %edx, %edx     # len <= 0?
14     jle Done            # if so, goto Done:
15 
16 Loop:
17     mrmovl (%ebx), %esi # read val from src
18     rmmovl %esi, (%ecx) # store val to dst
19     andl %esi, %esi     # val <= 0?
20     jle After           # if so, goto After:
21     irmovl $1, %edi
22     addl %edi, %eax     # count++
23 
24 After:
25     irmovl $1, %edi
26     subl %edi, %edx     # len--
27     irmovl $4, %edi
28     addl %edi, %ebx     # src++
29     addl %edi, %ecx     # dst++
30     andl %edx, %edx     # len > 0?
31     jg Loop             # if so, goto Loop:
32 
33 Done:
34     popl %edi
35     popl %ebx
36     popl %esi
37     rrmovl %ebp, %esp
38     popl %ebp
39     ret

头和尾暂时不看，程序中有两个关键的部分。其一，是Loop节，这一节直接关系到整个程序的性能；其二，是After节，也有一定的优化空间。

我们先从最简单的开始，把iaddl指令用上：

 1 Loop:
 2     mrmovl (%ebx), %esi # read
 3     rmmovl %esi, (%ecx) # store
 4     andl %esi, %esi     # val <= 0?
 5     jle After           # if so, goto After:
 6     iaddl $1, %eax      # count++
 7 
 8 After:
 9     iaddl $-1, %edx     # len--
10     iaddl $4, %ebx      # src++
11     iaddl $4, %ecx      # dst++
12     andl %edx, %edx     # len > 0?
13     jg Loop             # if so, goto Loop:

循环展开：

 1 Loop(n-1):
 2 
 3 ...
 4 
 5 Loop2:
 6     mrmovl 8(%ebx), %esi
 7     rmmovl %esi, 8(%ecx)
 8     andl %esi, %esi
 9     jle Loop1
10     iaddl $1, %eax
11 
12 Loop1:
13     mrmovl 4(%ebx), %esi
14     rmmovl %esi, 4(%ecx)
15     andl %esi, %esi
16     jle Loop
17     iaddl $1, %eax
18 
19 Loop0:
20     mrmovl (%ebx), %esi
21     rmmovl %esi, (%ecx)
22     andl %esi, %esi
23     jle After
24     iaddl $1, %eax

对于循环展开，需要考虑到余项问题。例如，如果展开规模为每个大循环16小节，那么当输入长度为21时，就会有5个“余项”。

我们可以手写一个类似Duff设备的结构，也可以把余项放在单独的switch结构里。由于Y86指令集里没有乘除、余数指令，我们一般把展开规模定为2的阶乘，然后对数组长度len做mask，用加法将结果乘以4（Y86的整数是32位的，它的字长相当于四个字节）得到偏移，查找跳转表来实现跳转。

index = len & mask

addr = *(jump_table + index + index + index + index)

顺带一提，Duff设备除了循环展开之外，还有一个非常有（毁）意（三）思（观）的用途是实现coroutine。

然后，观察每个Loop小节，我们发现时间的浪费主要在两个地方，其一是mrmovl与rmmovl之间的bubble，其二是jle分支预测错误产生的回退负担。

可以用条件数据移动代替jump：

1 Loop0:
2     mrmovl (%ebx), %esi
3     rrmovl %eax, %edi       # edi = count
4     rmmovl %esi, (%ecx)
5     iaddl $1, %edi          # edi = count + 1
6     andl %esi, %esi         # val <= 0?
7     cmovg %edi, %eax        # if so, apply the new value

还有一种办法，把两个Loop小节合并到一块。这样更快，但是对于循环余项，需要做另外的处理。

 1 Loop1:
 2     mrmovl 4(%ebx), %esi    # second
 3     mrmovl 0(%ebx), %edi    # first
 4     rmmovl %esi, 4(%ecx)    # second
 5     rmmovl %edi, 0(%ecx)    # first
 6 
 7     andl %esi, %esi         # second
 8     jle Loop
 9     iaddl $1, %eax
10 
11 Loop0:
12     andl %edi, %edi         # first
13     jle After
14     iaddl $1, %eax

除了循环之外，程序的其它部分也有一定的优化空间，但本文中不进一步展开了。~~不是这篇文章的重点嘿嘿，你来打我呀～~~

来点黑科技

考虑到每多处理一个整数平均只需要5.x个时钟周期（注：Y86的世界观里，内存访问是极快的），循环中可优化的空间似乎已经所剩不多。但是，有些事情就是那样万万没想到。

现在提供一条秘密情报（误），输入的数据尽管有正有负，它们的绝对值都不大，而且都不是0。测试数据的格式其实是1, 2, -3, -4, 5...，当然，如果更彻底地黑数据，就不那么有趣了。

你猜，我们可以如何利用这条信息？

给点提示，如果Y86支持二进制移位shr，我们可以利用符号扩展将整数变成0或-1，这样能省去了判断符号的步骤——先把数组长度赋值给结果，然后在遇到负数时利用符号扩展得到的-1不断将结果减小，最终得到正数个数。但是Y86并不包含这样的指令。等等……虽然不能做移位，但是可以移字节不是嘛！

举个例子，整数-3的二进制表示是11111101 11111111 11111111 11111111，只要数的绝对值够小，高16位就会是全0或全1。那么向后看两个字节，就能得到11111111 11111111 ???????? ????????。尽管这个数的高16位我们并不知道，这并不妨碍我们利用低16位，只要在最后将运算结果mask一下，轻松搞定。

 1 ncopy:
 2     ...
 3     rrmovl %edx, %eax       # count = len;
 4     ...
 5 
 6 ...
 7 
 8 Loop0:
 9     mrmovl 0(%ebx), %esi    # read val
10     mrmovl 2(%ebx), %edi    # read sign
11     rmmovl %esi, 0(%ecx)    # store val
12     addl %edi, %eax         # count += (val > 0) ? 0 : -1
13 
14 ...
15 
16 Fin:
17     ...
18     irmovl $0xffff, %ecx    # load mask 
19     andl %ecx, %eax         # apply the mask
20     ...

现在，每多处理一个整数会消耗4个时钟周期。而比较显然的是，整数需要一读一写这两项内存操作，无法回避，正数也需要用指令来统计，3个时钟周期几乎是理论极限了。现在问题来了，这能做到吗？

答案是可以，至少近似地可以。

熟悉Y86流水线的你可能你会想，Y86的内存读取在计算之后呀，单个时钟周期怎么做到又取出符号又把它加到结果中呢？

不，要换个思路，我们可以把取数据和取符号合并到一起。只需要不对齐地读写内存就可以了。例如复制三个整数，正常的做法是：[0-3] [4-7] [8-11]，而[0-3] [2-5] [6-9] [8-11]就是接下来要用的做法。尽管麻烦一些，但是我们可以直接读出原先整数的高位了。

而不对齐读写内存的耗时还是和原来一样——没有bubble时每个时钟周期都能执行一次。这再次印证了，Y86的内存访问能力有多么不科学。

下面上代码，为了避免bubble，还需要将读写过程交错一下：

 1 ...
 2 
 3 Loop3:
 4     addl %edi, %eax
 5     mrmovl 10(%ebx), %edi   # read between src[2] and src[3]
 6     rmmovl %esi, 14(%ecx)
 7 
 8 Loop2:
 9     addl %esi, %eax
10     mrmovl 6(%ebx), %esi
11     rmmovl %edi, 10(%ecx)   # store data
12 
13 Loop1:
14     addl %edi, %eax         # count the sign
15     mrmovl 2(%ebx), %edi
16     rmmovl %esi, 6(%ecx)
17 
18 ...

对于头部和尾部，我们需要这样处理：

 1 Loop15:
 2     mrmovl 60(%ebx), %edi   # read the tail
 3     mrmovl 62(%ebx), %esi   # read sign of src[15]
 4     rmmovl %edi, 60(%ecx)   # store the tail
 5     mrmovl 58(%ebx), %edi   # read between src[14] and src[15]
 6 
 7 ...
 8 
 9 Loop0:
10     addl %esi, %eax
11     mrmovl 0(%ebx), %esi    # read the head
12     rmmovl %edi, 2(%ecx)
13 
14     rmmovl %esi, 0(%ecx)    # store the head
15     addl %edi, %eax         # count the sign

我们还需要为余项写一些额外的入口，它们和Loop15小节类似。

另外，处理数据的头尾两端时，需要使用额外的指令，效率还是低了些，对于余项较少的情形，我们可以做专门的优化。

完整的Y86代码可以在这里找到。

> C++11 Lambda函数闭包的类型与存储形式

>> 关于健康

>>> 论如何用不正确的方式刷Lab

>>>> 求值过程中的副作用与顺序点

>>>>> gcc和clang之间的一个细节差异

<<<<<<