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

IT知识刺客 2024-01-12

114

书接前文。

先放公众号震楼。如果你是从其他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 100000000
TSC: 100013689 1087459713
1704447447.813657 - 1704447447.765921 = 47736

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

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

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

A: 0x000000000040087a <+110>:   add   $0x1,%ebx           k = k + 1
B: 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上限，再增加一条线，也没有意义了。

怎么办？

使用O2编译，减少指令数，试试看：

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

更慢了。还慢了快一倍。从47000微秒，到接近72000微秒。

看来编译器也不是永远的神。

先别急下结论。

我非常好奇-O2把代码变成什么样子了，反汇编看看：

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

-O2模式其实真聪明，比我自己手撸汇编要强。

它发现i与j的值永远只差1，那为啥还要两个变量，一个就够了。

看B这条指令，说实话，我想不到这样的写法。用lea，实现k2+=(i+1)，省去了j这个变量。

而且，有个古老的传说，用lea实现加法，比ADD更快。

其实LEA和ADD的响应时间都一样，都是1个周期。但早期的CPU，只有一个计算ADD的模块，两条ADD，就算没有依赖，也无法同一周期同时执行。但LEA是另一个专门的模块电路完成计算的，和ADD不一起，一条LEA和一条ADD，可以同时计算。所以，你有两个加法，编译器很可能编译为一条ADD、一条LEA。

现在的CPU，完成ADD的模块最少两套，多的可能4、5套。将加法编译为LEA，很多时候已经没有必要。

当然，这里使用LEA，主要是LEA可以完成k2+(i+1)，这是ADD做不到的。

gcc很聪明的选择了合适的指令。

但gcc并不是万能的。做为基础软件开发，如果完全依赖gcc、依赖编译器，是不可想象的。虽然现状的确是如此。

人工分析下，上面的汇编，D和E仍然要宏融合为一条大指令，仍记为DE。从A到E，实际执行的指令数为4。

4条指令中，DE依赖C，其他无依赖。

第一周期，有三条指令可以运行：A1 B1 C1

第二周期有4条，上一轮循环的DE1，和第二轮循环的A2、B2、C2，即：DE1 A2 B2 C2

第三周期4条：DE2 A3 B3 C3

……

按我们的分析，宏观上可以认为，CPU应该能在一个周期内执行完循环的4条指令（DE算一条指令）。

循环次数为5千万，一次循环也就一个周期，总共需要5千万周期。这是我们根据处理器的原理，得出的结论。

但实际CPU所用周期数是150711850，1亿5千万多。

实际和预估不一样，这就存在优化的空间。

gcc不会为你做这个分析，chatGPT估计也搞不定。我估计，其他的数据库内核开发团队也做不到，但我们可以。做为真正的基础软件，我们可以为您压榨出CPU的每一个周期。

看到没，什么是高性能编程（HPC），什么是基础软件编程，这就是。

你要基于原理，先对程序的运行时间有一个预估，再看实际的运行时间。如果差异过大，那性能上就有提升空间（当然，也可能你了解的原理是错的，预估错误）。

（当然，不是每一行代码都要这样做）

一个软件，所有关键的、高频的部分，都这样优化过，那能效绝对就是扛扛的了。这就是HPC编程。

HPC并不是简单的堆硬件，也不是高深莫测的超算。当然，超算当然属于HPC。但我们所理解的超算，多是指硬件层面，银河大型机、太湖之光等。

HPC是高性能计算，并不只有传统意义上的超算。

现在的企业服务器，其实已经非常强悍了，只要合理编程，发挥硬件潜力，90%的商业需求都可满足（90%还是保守的说法），需要超算的场景并不多。

而且云计算的发展，服务器数量越来越多，如果服务器上的程序可以使用HPC方式开发，每年可以节省大量电能。

在美帝，研究HPC编程的有很多，stackoverflow.com中有很多相关的讨论，给我的学习过程提供了很大帮助。

我在《HPC(高性能计算第一篇):一文彻底搞懂并发编程与内存屏障(完结篇)》中，提到过的一个大佬：

他的工作就是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);

"leaq 0x1(%%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 100000000
TSC: 74457414 1087459713
1704680261.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 100000000
TSC: 61260982 1087459713
1704691378.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 100000000
TSC: 58716264 1287459718
1704692404.571038 - 1704692404.543013 = 28025

仍有一点点提升。

5条线：

[root@oracledb ff]# ./m2_6 0 100000000
TSC: 61027192 1387459722
1704693125.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知识刺客，不错过精彩内容。

高性能计算前端架构指令周期汇编指令后端技术

文章转载自IT知识刺客，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

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

评论