课程主页：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/index.htm

课程视频：

https://www.bilibili.com/video/BV1wA411h7N7

最近入坑一门MIT讲软件性能的课程，看了下目录感觉挺实用的，后续会将其学完，这次回顾第一讲，主要是通过矩阵乘法的案例介绍课程主旨。

Lecture 1 介绍 & 矩阵乘法

为什么学习软件性能

哪些软件属性比性能更重要？

  • 兼容性
  • 功能
  • 可靠性
  • 正确性
  • 可维护性
  • 鲁棒性
  • 清晰性
  • 可调试性
  • 模块化
  • 便携性
  • 可测试性
  • 可用性

尽管如此，性能是计算的货币，通常可以用性能“购买”所需的属性。

来看下晶体管数和时钟频率随时间的变化：

从上图中可以看出，晶体管是线性增加的，但是时钟频率却不是，2004年之后时钟频率陷入瓶颈，这是因为如果时钟频率的缩放比例继续保持每年25％-30％的增长趋势，则功率密度的增长如下：

为了继续扩展性能，处理器制造商在微处理器芯片上放置了许多处理器核：

来看下晶体管数，时钟频率以及处理器核数随时间的变换：

尽管摩尔定律继续提高计算机性能，现在的计算机结构非常复杂；通常，必须对软件进行修改以有效利用硬件。

案例学习：矩阵乘法

考虑平方矩阵乘法问题：

即

为了方便讨论，这里假设

假设我们的处理器性能如下：

那么

其中$16$对应了8 double-precision operations。

老师对比了Python，Java，C计算$n=4096$时的效率，分析了Python，Java的缺点，最后提出本课程会基于C讨论，效率对比如下：

尽管C比较快，但是也只是达到了峰值的0.014而已，后续介绍几种优化方法。

C程序

代码核心部分如下：

for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j){
		for (int k = ; k < n; ++k){	
			C[i][j] += A[i][k]* B[k][j];
		}
	}
}

利用Clang/LLVM 5.0编译，程序的运行时间为：

下面分别运用多种方法进行优化。

交换循环次序

之所以产生上述现象，是由于缓存的原因：

  • 每个处理器在称为高速缓存行的连续块中读写主存储器。
  • 先前访问的缓存行存储在位于处理器附近的较小的内存中，称为“缓存”。
  • 高速缓存命中——快速访问高速缓存中的数据。
  • 高速缓存未命中——访问不在高速缓存中的数据的速度很慢。

缓存图示如下：

矩阵在内存中的布局如下：

不同顺序对应的访问方式：

可以通过valgrind工具评估缓存未命中率：

valgrind --tool=cachegrind ./mm

得到如下结果：

编译器优化
  • Clang提供了一组优化开关。
  • 可以指定一个开关，要求它进行优化。
  • Clang还支持用于特殊目的的优化级别，例如-0s旨在限制代码大小，而-0g用于调试目的。

性能对比：

目前整体性能对比：

多核并行

利用多核并行的方式如下：

cilk_for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j){
		cilk_for (int k = ; k < n; ++k){	
			C[i][j] += A[i][k]* B[k][j];
		}
	}
}

几种并行方式对比：

实际上我们有如下经验法则：并行化外循环而不是内循环。

目前整体性能对比：

数据复用：分块

首先回顾缓存的概念：

想法：重组计算以尽可能重用高速缓存中的数据。

  • 高速缓存未命中的速度很慢，而高速缓存命中的速度很快。
  • 通过重用已经存在的数据，尝试充分利用缓存。

考虑计算$C(4096\times 4096)$中一行需要的内存读写数量：

  • $4096\times 1= 4096$次写入$C$
  • $4096\times 1= 4096$次读取$A$
  • $4096\times 4096=16777216$次读取$B$
  • 总共的内存读写数量为$16785408$

如果将$C$分成$64\times 64$的分块，那么计算一个分块的读写数量为：

  • $64\times 64= 4096$次写入$C$
  • $64\times 4096= 262144$次读取$A$
  • $4096\times 64=262144$次读取$B$
  • 总共的内存读写数量为$528384$

现在对不同的分块大小做实验得到如下结果：

目前整体性能对比：

缓存未命中情况：

课件中还提到2级缓存，这里从略。

递归并行矩阵乘法

所以$n\times n$矩阵乘法拆成$8$个$n/2\times n/2$个矩阵乘法加上$1$个$n\times n$矩阵加法：

其中THRESHOLD是阈值，需要人为调试。

目前整体性能对比：

缓存未命中情况：

编译矢量化

矢量硬件

现代微处理器结合了矢量硬件，以单指令流，多数据流（SIMD）的方式处理数据。

可以使用如下方式进行编译向量化：

$clang -O3 -std=c99 mm.c -o mm -Rpass=vector
mm.c:42:7: remark: vectorized loop (vectorization width:2, interleaved count: 2)[-Rpass=loop-vectorize]
	for (int j = 0; j < n; ++j){
	^

程序员可以使用如下编译器标志来指示编译器使用现代矢量指令：

  • -mavx：使用Intel AVX矢量指令。
  • -mavx2：使用Intel AVX2矢量指令。
  • -mfma：使用融合乘法加法矢量指令。
  • -march = < string >：使用指定体系结构上可用的任何指令。
  • -march = native：使用进行编译的计算机体系结构上可用的任何指令。
  • 由于浮点运算的限制，可能需要附加标志，例如-ffast-math，这些矢量化标志才能生效。

目前整体性能对比：

编译器标志为

–march=native –ffast-math
其他优化

我们可以应用更多的想法和性能工程技巧来使此代码运行更快，包括：

  • 预处理
  • 矩阵转置
  • 数据对齐
  • 内存管理优化
  • 针对基本情况的巧妙算法，明确使用AVX内部指令

整体性能对比：

版本10和Intel的Math Kernel Library性能相当，所以优化到此为止。