高性能计算（HPC）系列之二：深入基础软件开发第二篇

书接前文。

先放公众号震楼。如果你是从其他APP跳过来的，点击右上角三个点，选择浏览器打开，长按此图片，选择分享图片。可以分享给文件传输助手。

然后进入微信，在文件传输助手中，点击图片，长按，就可以加公众号了。

本公众号精彩内容多多。不只有深度的技术，还有视角独特的故事。

预告下，我们的《数据库传奇》故事系列，就要上线了。简单易读，边讲故事，边扩展知识边界。

正文开始：

上一篇我们用土方法测量了CPU的频率。同时介绍了基本知识。

测量频率当然不是我们的最终目的，最终目的是如何能榨干CPU每一个周期的、写出能效最高的程序。做到了这一点，才是真正的HPC编程，才是基础软件开发应有的样子。（要不然开发的可以叫平台软件，称不上基础软件）

为了最高的能效，我再提个问题：如果我真的要进行1亿次加法，如何才能更快的完成？

比如，我把程序改一改，要在循环中完成“阶加”，1+2+3+4……

 gettimeofday(&tv1, 0); begin = rdtscp(); k = 0; for (i=0; i<=num; i++) {     k+=i; } end = rdtscp(); gettimeofday(&tv2, 0);

（如果你是高端CPU，可以把多条i++宏融合，可以试试这个版本的“阶加“）

它的执行时间和k=k+1一样。循环产生的多条k+=i，是前后依赖的，无法并行执行。

如果想并行执行，要把1+2+3+……拆开，比如，拆为如下两条线：

1+3+5+7+……2+4+6+8+……

第一条线对应所有奇数之和。

第二条线计算所有偶数之和。

两条线互不依赖。

程序代码如下：

 gettimeofday(&tv1, 0); begin = rdtscp(); k1 = 0; k2 = 0; for (i=0, j=1; i<=num; i+=2, j+=2) {     k1+=i;     k2+=j; } k1+=k2; end = rdtscp(); gettimeofday(&tv2, 0);

i的值依次是0, 2, 4, 6, ……，1亿以内所有偶数。

j的值依次为1, 3, 5, 7, ……，1亿以内所有奇数。

i的值合并累加到k1。

j的值合并累加到k2。

最后再把k1, k2加起来。

在程序内部，形成两条并不依赖的线。编译：

[root@oracledb ff]# gcc -g measure2.c -o m2_2[root@oracledb ff]#

看结果：

[root@oracledb ff]# ./m2_2 0 100000000TSC: 100013689 10874597131704447447.813657 - 1704447447.765921 = 47736

47000多微秒。略有一点点提升，优化前的程序，通常是48000、49000多微秒。

优化后的m2_2，循环次数是少了一半的，从1亿次循环，减到5千万次循环。但为什么提升不明显？

还记得刚才的反汇编吗，k = k + 1时的那段，我再粘贴过来：

A: 0x000000000040087a <+110>:   add   $0x1,%ebx          // k = k + 1B: 0x000000000040087d <+113>:   add   $0x1,%r12d          // i++，为了控制循环次数C: 0x0000000000400881 <+117>:   movslq %r12d,%rax          // 为了控制循环次数D: 0x0000000000400884 <+120>:   cmp   -0x28(%rbp),%rax     // 为了控制循环次数E: 0x0000000000400888 <+124>:   jb    0x40087a <work+110>  // 循环，向上跳转

循环中已经有5条指令了。一次循环，已经达到最大IPC：5。

这次的“阶加“，把k = k + 1，换成了k = k + i。最终编译完的汇编代码，应该相差无几。循环中的指令数，应该也是5。

也就是说，就算只有一条线时，一次循环指令数已经超过4，已经达到了指令级并行的上限。

简单点说：

一条线已经达到IPC上限，再增加一条线，也没有意义了。

[root@oracledb ff]# gcc -g measure2.c -o m2_2 -O2[root@oracledb ff]#[root@oracledb ff]# ./m2_2 0 100000000TSC: 150711850 10874597131704448468.465430 - 1704448468.393496 = 71934

A: 0x00000000004008a0 <+64>: add %ecx,%esi             // k1+=iB: 0x00000000004008a2 <+66>: lea 0x1(%rax,%rcx,1),%eax // k2+=(i+1)C: 0x00000000004008a6 <+70>: add $0x2,%rcx             // i+=2D: 0x00000000004008aa <+74>: cmp %rcx,%rbx             // 循环控制E: 0x00000000004008ad <+77>: jae 0x4008a0              // 循环控制

他的工作就是HPC编程。

其实就像SQL优化，一条SQL，只是不是太过复杂，对于有经验的人来说，看看执行计划，再实际看看数据量，SQL大概所用时间，也可以评估出来。如果实际执行时间和预估时间相差太多，那不就是可以调优的SQL吗！

道理是一样的。只不过，掌握数据库原理的人更多，了解处理器原理的开发，则几乎没有。但也正是因为没有，才有巨大的潜力啊。这不正是你渡过35岁危机、甚至45岁危机，最好的机会吗。

我们继续，通过前面的分析，结合测试结果，我这款至强E5-2620，很可能存在BUG，LEA和ADD混合时，LEA执行完成后，会STALL一个周期。

我把程序改成嵌入汇编验证下：

 gettimeofday(&tv1, 0); begin = rdtscp(); k1 = 0; k2 = 0; //for (i=0, j=1; i<=num; i+=2, j+=2) // 这是程序原本的样子 //{ //   k1+=i; //   k2+=j; //} __asm__ __volatile__     // 改为如下嵌入汇编 (     "movq   $0, %%rcx\n\t"     "movl   %4, %%eax\n\t"     "movq   $1, %%rbx\n\t"     "LOOP:\n\t"         "addl    %%ecx, %0\n\t"         "addq    $0x2, %%rcx\n\t"         //   "leaq    0x1(%%rax, %%rcx, 1), %%rax\n\t"         "addq    %%rbx, %%rax\n\t"         "addq    $0x2, %%rbx\n\t"         "cmpq    %%rcx, %2\n\t"         "jae     LOOP\n\t"     "movl %%eax, %1\n\t"     :"=r"(k1), "=r"(k2)     :"r"(num), "0"(k1),"1"(k2)     :"rbx","rcx" ); k1+=k2; end = rdtscp(); gettimeofday(&tv2, 0);

"leaq0x1(%%rax, %%rcx, 1), %%rax\n\t" 我注释掉了。因为先是用leaq验证了下，我手写的嵌入汇编，的确需要1亿5千万周期多，和GCC编译的结果一样。

然后，我注释掉了leaq指令，换成ADD。因为add无法实现k2+(i+1)，所以指令数多了一些。

好，编译：

[root@oracledb ff]# gcc -g measure2.c -o m2_3[root@oracledb ff]#

运行：

[root@oracledb ff]# ./m2_3 0 100000000TSC: 74457414 10874597131704680261.803066 - 1704680261.767528 = 35538

35538微秒，总时间上，的确少了。原来一条线时，是48000、49000微秒。

使用LEA时，是71000多微秒。

我有使用rdtscp编译程序所用TSC，也就是程序所用周期数，为7400多万个周期（74457414）。比使用LEA的时候好多了，使用LEA时，一共需要1.5亿多个周期。

通过这个测试，我有理由认为，这款CPU的微架构（至强 E5-2620），存在问题。

我又换了台机器，分别在icelake、tigerlake微架构上，做了测试，不存在这样的问题。

当然，找出CPU的潜在性能BUG，并不是我的目的。我的目的是提高程序能效，是HPC高性能编程。

Intel估计也从未注意过这个问题，毕竟能发现这样问题的人太少。而且，这个问题解决起来又十分简单，把LEA换成ADD，就可以了。

继续我们的讨论，7400万周期，3.5万多微秒，是否就是这个程序的能效极限了？我们做1亿次加法，是否最快就是3.5万微秒了呢？

按照前面讲的方法：“先预估分析，再对照实际运行数据”。

下面是1亿次加法的汇编：

  "LOOP:\n\t"A     "addl    %%ecx, %0\n\t"     //B     "addq    $0x2, %%rcx\n\t"   // A与B，对应0+2+4+6+……C     "addq    %%rbx, %%rax\n\t"   //D     "addq    $0x2, %%rbx\n\t"   // C与D，对应1+3+5+7+……E     "cmpq    %%rcx, %2\n\t"F     "jae     LOOP\n\t"

E、F将宏融合为EF。

EF依赖B的结果。

其他指令无依赖。

这样的程序，一周执行4条指令，也就是IPC达到4，是没问题的。

循环共5000万次，每次循环5条指令（E、F按宏融合后算一条指令），IPC为4，5 * 50000000 / 4，得6250万周期。

预估，它应该需要6250万周期。但实际上它使用了7400万周期多，实际的IPC为3.35。

根据我们的分析，IPC应该可以达到4，但实际只达到3.35，因此，还有提升空间。

这里之所以IPC没有达到4，主要是因为前端译码模块，没有能足量的把指令传递到后端。

这里有几个名词我简单解释下。

复杂指令集的CPU，其内部执行的，不是指令，而是微码，uOP。关于这个，我不详细解释了，有好多资料可以进一步了解下。

指令先读入内存，再进入专用于指令的L1 Cache，称为iCache，然后CPU将对iCache中的指令进行译码，将指令转为uOP。这个译码部分的集成电路，称为前端。还有分枝预测什么的，就都属于前端部分。

译码后，指令就被“翻译”为uOP了，然后会由执行模块执行uOP。这个执行模块对应的集成电路，称为后端。

可以简单的理解为：前端译码，后端执行。

有这个基础，对于HPC高性能开发，也就够了。

我们这里IPC没有达到预想的值，问题不在后端执行，而在前端译码。

对于前端译码，遇到分枝指令，是要停止的。前面的A、B、C、D、EF，5条指令，EF是分枝指令，前端部分是这样工作的：

第一周期，完成如下指令的译码：A1 B1 C1 D1

第二周期，完成如下指令的译码：EF1

第三周期，完成如下指令的译码：A2 B2 C2 D2

第四周期，完成如下指令的译码：EF2

……

分枝指令，只能是这一周期中，最后一条进入前端译码部分的指令。像上面这样，如果EF1是这一周期第一条译码的指令，这一周期就只能译码这一条指令。（为什么会有这样的限制，第三篇会有简单的分析）

前端部分如果不能足量的把指令译码为uOP，交给后端，后端的IPC当然也就上不去。

这里的主要问题是，前端部分也是有个吞吐量的概念的，可以也叫IPC。

前端吞吐量不足，是会影响后端的。

CPU厂商当然早就注意到了这个问题，为了解决这个问题，他们八仙过海，各显神通。

比如，再增加一块缓存，保存译码结果，下次遇到相同指令，就不译码了，直接取出缓存中译好的uOP。这是最通用的做法，Intel/AMD都这样做了。

就像我们这里的循环，循环1亿次，产生了1亿条指令，没必要让前端部分做1亿次翻译。把第一次翻译好的uOP，写入这块缓存，后面直接从缓存中得到uOP就可以了。

这块缓存并不是L1 指令Cache，是额外的一块缓存。现在的CPU，基本都可以在这块缓存中存储两千条左右指令的译码结果。

（除了这种方法，还有其他的啊，比如LCD之类的，这里举个例子说明下而已）

但是，由于处理器内部复杂度的增加，各种限制也随之增加，有时候这块缓存并不能被有效的使用。

这个时候，对于我们软件的开发者，我们能做的，就只有一件事，尽量不要让分枝指令，成为这个周期第一条进入前端译码的指令。

分枝跳转类指令是复杂度高的罪魁祸首。它不仅影响前端，还影响前、后端的交互。

理论上讲，分枝跳转类指令，要等到后端执行过程结束后，才知道要跳转去哪里，前端才可以继续从跳转目标处译码。如果CPU真这样设计，那就太慢了，因此前端并不等待后端告诉它，要跳到哪里，前端自己根据概率，估算要跳到哪里，这就是分枝预测了。

这一块我们不详细说了，但我们要知道，分枝跳转类指令，是需要前、后端交互的。它可能会导致，在没有依赖的情况下，前、后端的吞吐量，都达不到预期。

（注意我所说的不是分枝预测失败）

解决的方式，就是前面所说，不要让分枝指令，成为这个周期第一条进入前端译码的指令。

如果很不幸，像上面的例子一样，EF1、EF2……，分枝指令有可能成为这个周期中第一条进入前端的指令，那么，我们可以继续在循环中增加指令，这样可以让前端、后端的吞吐更高。

我把程序改造成这样：

__asm__ __volatile__(    "movq   $0, %%rcx\n\t"    "movl   %4, %%eax\n\t"    "movq   $1, %%rbx\n\t"    "movq   $2, %%rdx\n\t"    "movq   $0, %%r8\n\t"    "LOOP:\n\t"A       "addl    %%ecx, %0\n\t"B       "addq    $0x3, %%rcx\n\t"       // A与B，对应0+3+6+9+……C       "addq    %%rbx, %%rax\n\t"D       "addq    $0x3, %%rbx\n\t"       // C与D，对应1+4+7+10+……E       "addq    %%rdx, %%r8\n\t"F       "addq    $0x3, %%rdx\n\t"       // E与F，对应2+5+8+11+……G       "cmpq    %%rcx, %2\n\t"H       "jae     LOOP\n\t"    "addl %%r8d, %%eax\n\t"    "movl %%eax, %1\n\t"    :"=r"(k1), "=r"(k2)    :"r"(num), "0"(k1), "1"(k2)    :"rbx","rcx","rdx","r8");

我把两条线，改造为了三条线。注释中已经写的很清楚了，这里不再过多解释。

直接看它的效果吧：

[root@oracledb ff]# ./m2_4 0 100000000TSC: 61260982 10874597131704691378.679653 - 1704691378.650413 = 29240

1亿次加法，总时间已经下降到29240微秒。一开始是48000、49000微秒。

看，在我们的优化下，时间已经下降了快一半了。

周期数是6126万。

现在的IPC为3.8，比刚才的3.35，略有提升。离4也已经很近了。

我不再详细分析这一次的指令流了，分枝跳转指令，是宏融合后的GH，在它之前，有足够多的无依赖指令，可以让吞吐量（IPC）达到4。

但是，由于分枝跳转指令的复杂性，IPC仍没有达到4，3.8的IPC，已经是上限了。

再增加到4条线后：

[root@oracledb ff]# ./m2_5 0 100000000TSC: 58716264 12874597181704692404.571038 - 1704692404.543013 = 28025

仍有一点点提升。

5条线：

[root@oracledb ff]# ./m2_6 0 100000000TSC: 61027192 13874597221704693125.881744 - 1704693125.852616 = 29128

性能又下降了。

我们得到了最快速的版本，就是将1+2+3+4……，分割为4条线。时间从48000、49000微秒，下降到28025微秒。

所用时间，只有原来的58%。

真能读到这里的朋友，我相信应该寥寥无几。中国基础软件的振兴，真的只能靠你们了。

到这里，可能不禁有人要问，这不就是循环展开吗。

对，这就是循环展开。

我们其实详细描述了循环展开为什么可以提升性能。

如果你不知道这些细节，循环展开，这四个字，对你将只是一种实际使用不上的奇技淫巧，只能在测试环境玩玩。

你看到了，这里面有非常多的注意事项，远不是循环只要一展开，性能就能提升那么简单。

1亿次“阶加“，所用时间已经下降到原来的58%，还有提升空间吗？

那必须有。

等下期吧。

应该没多少人期待，多数人读不到这里 :)

再预告下，我们的《数据库传奇》故事系列，就要上线了。

我可不是什么难写什么的，讲故事也是我的专长。

这里有个《卡脖子的数据库：从一项功能说起》系列：

https://mp.weixin.qq.com/s/OsgRuKs-1HtEpxbjOPx2aw

这是第一篇。一共5篇，都在公众号的开始处，特别适合带薪拉屎的时候读。不要错过，关注 @IT知识刺客，不错过精彩内容。