Load Value Approximation(cache层的load近似化)

Introduction

近似计算已经成为了一个研究的热门。而且他跨越了多个层面,从电路层到体系结构层,到算法层。

谷歌学术搜索结果:

物理世界的本质

依照经验来看,物理世界的本质是连续的。但是我们没有足够的能力来处理这样连续的数据,至于还有什么原因,想出了模数转换这个方法,我也不清楚。

模数转换,必然性的导致了信息的缺失。

但是,最后应用基本都是面向人的,而人实际上是有很大限制的:

  • 人眼分辨率600万左右
  • 电影30FPS就不会觉得卡
  • 人耳20Hz – 20kHz的声音

对于视频或者图像来说,可能几行,几十行像素有错误,我们也分辨不出很大的差别来。

很多情况下,我们不需要那么精确的数据

对于一些inherent error-tolerant(天生具有错误承受能力)的应用来说,数据精确,对于计算能力、存储能力和能耗产生了指数倍数的需求。

因此,近似计算的提出,是对传统架构的新挑战和大趋势。

发展方向

现在学术界对于近似计算的分类,主要有以下三种类型:

  • 电路级别
  • 体系结构
  • 算法级别

本文主要说明了《Load Value Approximation》的思路。

我的研究方向主要是体系结构,看过一些有趣的idea,比如在memory级别,SRAM的电压越低,出错的可能性越大,但是在保持一定的错误率的情况下,我们可以降低电压来节能。将数据按照某种标准进行优先级排序,把不重要的数据放到寿命将要到限的cell上。即便出错误,也可以接受。

Load Value Predictor

传统的预测器,前提条件还是“在系统中流动的数据是精确的数据”:

  1. 在L1 Private Cache中Miss了数据X
  2. 预测器生成一个预测值X_Pre,
  3. X_Pre被送到cpu进行处理,同时向下一层cache or memory取真实的数据X_Actual。
  4. 数据被取上来以后,X_Pre和X_Actual进行比对,如果不相同,认为预测失败了,RollBack产生X_Pre以后的进行的操作,降低产生的这个X_Pre值的可信度。如果相同,说明预测成功了,增加X_Pre的可信度。

存在的问题

RollBack

撤销自从把X_Pre作为真实数据以后进行的操作,恢复寄存器甚至cache的数据。如果要恢复,意味着需要保存原来的状态,需要额外的存储空间和控制流。

Value Delay


Load Miss A --> Prediction
			--> Fetch A
			--> Load Miss B --> Prediction
							--> Fetch B

A和B有数据相关性,在B的prediction时,由于预测器还没有经过数据A的训练,预测出来的数据,很可能是错误的,那么B后面的操作,全部需要RollBack。

Load Value Approximator

近似器和预测器类似,但是他是允许数据有错误出现,在approximator的④上,只是单纯的训练数据,而没有rollback。近似器完全消除了rollback

  • GHB: FIFO队列,存储最近的load指令,buffer里每条数据存储的真实数据。前图中所有的X_Actual都在GHB中。
  • LHB:只存储匹配当前tag的最近的load value
  • h: hash函数(xor等),展示了load pattern
  • conf:决定了当前是否可信,<0 则不做预测 (预测在可信窗口大小内则++)
  • degree:决定了这个数据可以用多少次
  • f: average等

上图是他的设计。在Load miss之后,用一个h函数哈希出值,然后到表里去匹配,如果匹配不到,那么传递miss,同时更新表。

可以近似化的数据

语句块类型 解释 是否可以近似化
控制流 if a == 49 ,那么如果对a近似化,程序将走向错误的方向
除数 如果除数为0.001,那么很可能会被近似化为0,出现除数为0的错误,导致程序崩溃
内存地址或指针 如果内存地址出现了错误,那么程序可能溢出或者访问不该访问的地址
循环 应该是耗费最多最重要的循环才可以被近似化

使用的Benchmark

PARSEC 3.0

Canneal blackscholes swaptions Bodytrack
CAD应用,使用模拟退火算法生成二维数据 金融分析软件,使用偏微分方程计算 金融分析软件,使用偏微分方程计算 根据四个摄像头的数据,追踪人的运动
x264 Ferret Fluidanimate
H264的视频编码解码软件 相似图像搜索引擎 水流模拟软件

使用的实验平台

总结

up to 28.6% speedup (8.5% on average) and 44.1% energy savings (12.6% on average) in the memory hierarchy。

尽管idea看起来很棒,但是最终的summary实验结果感觉没有那么理想,提升的效果比较小,尤其是x264的实验结果,甚为奇怪,提升很不明显。

文章版权归 FindHao 所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权|
转载必须包含本声明,并以超链接形式注明作者 FindHao 和本文原始地址:
https://www.findhao.net/easycoding/1989

你可能喜欢:(相似内容推荐和广告都使用了谷歌的推荐系统,需要对本站取消广告屏蔽才能显示。感谢点击↓广告支持博主~)

Find

新浪微博(FindSpace博客)QQ群:不安分的Coder(375670127) 不安分的Coder

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*