数据复用

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

自复用#xff1a;如果多个迭代访问同一个内存位置#xff0c;那…前言

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

数据复用

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

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

举个例子

这个内存位置的数据这样的访问经常被使用因为这块内存的数据可能被改变。

组复用Z[1][2],

Z[1][2]

Z[1][3]每次通过不同的指令进行访问但这些位置的数据之间有相关性。

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

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

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

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

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

找出重复迭代

0的两次迭代等价其中一个对矩阵的秩没有影响它是多余的现在我们的问题是这个等式的求解。

向量与空间体

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

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

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

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

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

向量解与迭代

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

[i1

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

将数据复用问题转化为重复迭代问题再引入矩阵转化为代数问题最后求解出访问相同数据的重复迭代。

以上都属于自复用内容先更这些。