MIT 6.172 L2 Bentley Rules for Optimizing Work

课程主页：

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

这次回顾第二讲，这一讲介绍了减少工作量(work)的一些方法。

Lecture 2 Bentley优化工作规则

工作量(work)

程序的工作量（在给定的输入上）是程序执行的所有操作的总和。

后续将介绍优化工作的”Bentley”规则，整体的规划如下：

数据结构

打包和编码

打包的思想是在一个机器字中存储多个数据值。编码的相关思想是将数据值转换成较少比特的表示。

例子：考虑日期数据“September 11, 2018”，该日期需要18比特表示。

编码日期：

如果我们只存储公元前4096年到公元4096年的日期，如果用数字表示日期，那么需要的位数为：

$\left\lceil \lg \left(365.25 × 8192\right)\right \rceil\approx \left\lceil \lg \left(3 \times 10^{6}\right)\right \rceil=22$

打包日期：

typedef struct {
	int year: 13;
	int month: 4;
	int day: 5;
} date_t;

该打包表示需要22位。

增强

数据结构扩充的思想是向数据结构中添加信息，使常用操作减少工作量。

例子：单向链表拼接操作，可以通过增加尾指针减少运算时间：

预计算

预计算的思想是预先进行计算，以避免在“任务关键”时进行计算。

例子：二项式系数的计算。

方法1：

int choose(int n, int k) {
    if (n < k) return 0;
    if (n == 0) return 1;
    if (k == 0) return 1;
	return choose(n-1, k-1) + choose(n-1, k);
}

该方法会有很多重复计算，可以通过预计算的方式避免这点。

方法2：

#define CHOOSE_SIZE 100
int choose[CHOOSE_SIZE][CHOOSE_SIZE];

void init_choose() {
	for (int n = 0; n < CHOOSE_SIZE; ++n) {
        choose[n][0] = 1;
        choose[n][n] = 1;
    }
	for (int n = 1; n < CHOOSE_SIZE; ++n){
		choose[0][n] = 0;
		for (int k = 1; k < n; ++k){
			choose[n][k] = choose[n-1][k-1] + choose[n-1][k];
             choose[k][n] = 0;
		}
	}
}

编译时初始化

编译时初始化的思想是在编译期间存储常量的值，从而节省执行时的工作。

如果表很大怎么办？可以通过程序来编写该表：

int main(int argc, const char *argv[]){
    init_choose();
    printf("int choose[10][10] = {\n");
    for (int a = 0; a < 10; ++a) {
		printf(" {");
		for (int b = 0; b < 10; ++b) {
            printf("%3d, ", choose[a][b]);
        }
		printf("}, \n" );
    }
	printf("}; \n");
}

缓存

缓存的思想是存储最近访问过的结果，这样程序就不需要再计算它们了。

例子：

double cached_A = 0.0;
double cached_B = 0.0;
double cached_h = 0.0;

inline double hypotenuse(double A, double B){
    if (A == cached_A && B == cached_B){
		return cached_h;
	}
    cached_A = A;
    cached_B = B;
    cached_h = sqrt(A*A + B*B);
    return cached_h;
}

稀疏性

利用稀疏性的思想是为了避免在零上存储和计算。因为最快的计算方法是根本不计算。

例子：矩阵乘法。

$y=\left(\begin{array}{llllll} 3 & 0 & 0 & 0 & 1 & 0 \\ 0 & 4 & 1 & 0 & 5 & 9 \\ 0 & 0 & 0 & 2 & 0 & 6 \\ 5 & 0 & 0 & 3 & 0 & 0 \\ 5 & 0 & 0 & 0 & 8 & 0 \\ 0 & 0 & 0 & 9 & 7 & 0 \end{array}\right)\left(\begin{array}{l} 1 \\ 4 \\ 2 \\ 8 \\ 5 \\ 7 \end{array}\right)$

该矩阵只有14项非零，只需考虑这些项即可：

$\mathrm{y}=\left(\begin{array}{cccccc} 3 & & & & 1 & \\ & 4 & 1 & & 5 & 9 \\ & & & 2 & & 6 \\ 5 & & & 3 & & \\ 5 & & & & 8 \\ & & & 9 & 7 & \end{array}\right)\left(\begin{array}{l} 1 \\ 4 \\ 2 \\ 8 \\ 5 \\ 7 \end{array}\right)$

压缩稀疏行（CSR）：

rows表示每行开始部分的索引，cols表示对应列，vals为对应值，代码实现如下：

typedef struct {
	int n, nnz;
	int *rows;		//length n
	int *cols;		//length nnz
    double *vals;	 //length nnz
}sparse_matrix_t;

void spmv(sparse_matrix_t *A, double *x, double *y) {
    for (int i = 0; i < A->n; i++){
		y[i] = 0;
		for (int k = A->rows[i]; k < A->rows[i+1]; k++){
            int j = A->cols[k];
		   y[i] += A->vals[k] * x[j];
        }
	}
}

存储静态稀疏图（和之前类似）：

逻辑

常量折叠和传播

常量折叠和传播的思想是在编译过程中计算常量表达式并将结果替换为其他表达式：

#include <math.h>

void orrery() {
	const double radius = 6371000.0;
	const double diameter = 2 * radius;
	const double circumference = M_PI * diameter;
	const double cross_area = M_PI * radius * radius;
	const double surface_area = circumference * diameter;
	const double volume = 4 * M_PI * radius * radius * radius / 3;
    // ...
}