课程主页:

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性能相当,所以优化到此为止。