Spring算法-终极的内存访问优化

基于Krylov子空间的迭代方法中,存在海量的矩阵与矢量相乘的运算。而矩阵乘矢量,瓶颈并不在CPU运算速度,而在于CPU访问内存的带宽有限。

具体来说,从主存中读一个数据,要几百个时钟周期,远远高于运算本身。所以,算法优化的核心矛盾在于:访问主存的代价是昂贵的,而CPU内的运算则是廉价的。

我整个今年春季学期,可以说是不断地与优化主存访问做斗争的过程。以一个1000×1000的网格为例,从最初500多秒起跳,到后来优化到60秒以内,我觉得我是吃奶的力气都使出来了。

不过,今天,我相信我终于找到了终极的内存访问优化方法。为什么说是终极的呢?理由如下:

  1. 整个数组的读取、写入是顺序进行的,不存在随机访问;
  2. 数据只被从主存中读取一次;
  3. 这意味着,重复使用的数据,一定保证是在缓存里的;

正因为做到了这些,我才相信我这个算法是终极的内存访问优化方法了。除非是,在1、2、3条之外,还存在主存访问优化手段。不过,这已经在我目前的知识体系之外了。我当前的目标,就是做到这1、2、3条。

这个算法是我苦思冥想出来的,不过估计已经被人发表了。因为一旦想通后,整个算法是很简单的,并且是符合人的直觉的。也就是说,只要你真正地苦思冥想过这个问题,就一定会达到这个境界的。

整个的暑假工作开了个好头,继续努力吧!

1035742

Advertisements
此条目发表在未分类分类目录。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s