优化程序中的数据：从代数到向量解

前言

在前文笔者简单介绍了把数据迭代抽象为线性代数，并介绍了空间体、维度等概念。

数据复用

数据复用是一种提高程序执行效率与数据局部性的方法，分为自复用与组复用，

自复用：如果多个迭代访问同一个内存位置，那么称为自复用。

组复用：如果多个迭代访问不同的内存位置，但这些位置存储的是相关的数据，那么称为组复用。

举个例子：

自复用：Z[1][1]，每次迭代都访问 Z[1][1] 这个内存位置的数据，这样的访问经常被使用，因为这块内存的数据可能被改变。

组复用：Z[1][2], Z[1][3]，每次迭代访问不同的内存位置（如 Z[1][2] 和 Z[1][3]），每次通过不同的指令进行访问，但这些位置的数据之间有相关性。

循环中的重复访问

数据复用，就是循环中的重复访问数据，对于数组的遍历，假设每个元素之间都没有依赖关系，那么我们可以直接全部并行执行，在并行的基础上，我们会优先执行具有局部性的数据，因为cache中的数据往往都具有局部性，如果去执行与前面的数据局部性差的数据，很可能这些数据在下一级内存中，这样会浪费CPU时间。

为了优化局部性，我们希望识别访问相同数据或相同cache线的遍历（迭代）。

矩阵的秩与重复迭代

矩阵的秩是线性无关行（或列）的数目，在上文笔者简单介绍了如何将迭代与矩阵等价。

那么在数组的迭代过程中，如果进行了重复的迭代，那么转化为矩阵，也就是多了线性相关行（或列）的数目，而矩阵的秩其实并没有改变。

那么，我们需要找出重复的迭代，并将这些迭代进行密集处理，这样能获得更好的局部性。

找出重复迭代

在前文笔者写过不等式表示出来的矩阵：

|  1  0 |   | i |   >=   | 0 |
| -1  0 | * | j |   >=   | -5 |
| -1  1 |           >=   | 0 |
|  0 -1 |           >=   | -7 |

我们可以把矩阵写成这样：

Fi + f >= 0

这样写，就是一次迭代的访问，同理，再写一次迭代：

Fl + f >= 0

那么，我们可以知道，重复的迭代，就是：

Fi + f = Fl + f
也就是：F(i - l) = 0

这样做，我们就成功把迭代等价问题转为了数学问题。

F(i - l) = 0求解

现在我们已经知道了，满足F(i - l) = 0的两次迭代等价，其中一个对矩阵的秩没有影响，它是多余的，现在，我们的问题是这个等式的求解。

向量与空间体

我们先思考一下，i和l都是向量，那么假设它们的差值为向量v，那么问题就是：

Fv = 0

F是一个矩阵，而且是确定值，它由不等式给出，那么抽象到空间中，它可以表示为一个空间体，

假设这个空间体是平面，那么V，一定就是垂直于这个平面的向量，根据向量的性质我们可以知道它们的相乘结果是0。

现在我们对空间抽象有一些理解了，那么拓展到更高维度，不管F是一个怎样的空间体，v向量空间都会使它们的结果为0，那么把V称之为零空间，我们的目的就是求解出这个零空间，这样我们就会知道那些迭代是等价的。

到这一步就不用再细究了，直接使用matlab或者python进行求解是一个非常不错的选择。

向量解与迭代

假设我们使用matlab等工具求解出v的值为：(这个值是笔者随便乱敲的)

[1
 1]

我们迭代使用的遍历有i和j，那么也就是说：

[i1   - [i2
 j1]  -  j2]  = [1
 				 1]

也就是说，在我们迭代遍历数组并使用i和j作为迭代量时，如果这一次的迭代与之后的一次迭代，它们的差值刚好满足向量v的结果，那么它们就是重复迭代。

总结

将数据复用问题转化为重复迭代问题，再引入矩阵转化为代数问题，最后求解出访问相同数据的重复迭代。以上都属于自复用内容，先更这些。