当前位置: 首页 > news >正文

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

前言

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

数据复用

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

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

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

举个例子:

自复用: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的值为:(这个值是笔者随便乱敲的)

[11]

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

[i1   - [i2j1]  -  j2]  = [11]

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

总结

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

http://www.lryc.cn/news/509169.html

相关文章:

  • 【Web】2024“国城杯”网络安全挑战大赛决赛题解(全)
  • 基于ceres优化的3d激光雷达开源算法
  • 【FAQ】HarmonyOS SDK 闭源开放能力 — Vision Kit(2)
  • 【LeetCode】726、原子的数量
  • VMware虚拟机三种网络工作模式
  • 14-zookeeper环境搭建
  • [搜广推]王树森推荐系统笔记——矩阵补充最近邻查找
  • Unity3D * 粒子特效 * Particle System
  • 【基础篇】1. JasperSoft Studio编辑器与报表属性介绍
  • 数据结构:算法篇:快速排序;直接插入排序
  • WebAPI编程(第一天,第二天)
  • 查看MySQL存储引擎方法,表操作
  • 【Python教程】Python3基础篇之Number(数字)
  • 基于openEuler22.09部署OpenStack Yoga云平台(一)
  • I.MX6U 启动方式详解
  • 施耐德变频器ATV320系列技术优势:创新与安全并重
  • 系统思考—全局思维
  • Windows如何切换用户访问局域网共享文件夹,如何切换网上邻居的账户
  • 如何在谷歌浏览器中启用语音搜索
  • HarmonyOS NEXT 技术实践-基于基础视觉服务实现骨骼点识别
  • Debian系统宝塔面板安装LiteSpeed Memcached(LSMCD)
  • tcp 的三次握手与四次挥手
  • QT--信号与槽机制
  • vue3项目history路由模式部署上线405、刷新404问题(包括部分页面刷新404问题)
  • 电阻容差是啥意思
  • Rust: offset祼指针操作
  • SD本地部署和云端部署的区别以及优劣
  • 4、数据结构与算法解析(C语言版)--栈
  • c# 后台任务自动执行
  • 被裁20240927 --- 嵌入式硬件开发 前篇