陆国伟- · 2021年08月19日

CPU Cache简介

备注:需对CPU有一定理解,建议阅读CPU简介

为什么需要CPUCache

真空中光速为299,792,458米/秒,目前,Intel的i7频率可以达到4GHz,简单换算一下,可以得出结论:光(电流)在一个Cycle内移动的距离约为0.075米。显然,目前的内存条的芯片(反正两面。约为3.75cm)大大超过了这个长度,换句话说,理论上,在一个Cycle内内存条上总有一个位置是我们无法触摸。

实际上,早期的计算机结构相对简单,就是不同组件构成的一个体系,包括CPU,内存条,硬盘和网卡等,各组件之间的性能相对平衡。后来,随着各个组件的不断发展,各自形成了一个相对独立的子体系,众所周知的摩尔定律,就是描述CPU性能的迅猛发展。不同组件之间的性能差异日益显著。

aijishu_cpu1.jpg

巧妇难为无米之炊,内存不给力,再快的CPU也无用武之地。难道真的没有办法提高内存的性能吗?答案是有。

内存可以分为两大类:SRAM(静态)和DRAM(动态),因为如下是两者的电路对比:

aijishu_cpu2.jpg

前者性能高,状态稳定,直接访问M1~M4晶体管,获取当前的内存状态(0或1),而后者将内存状态保存在C(电容器),这个设计有三个问题,第一是访问容器C会导致放电,因此,需要不停的刷新充电,这个过程中无法访问该内存存放的数据,同时需要使用放大器才能区分状态(0或1),每次读操作后需要重新充电,总之,这导致了动态内存的设计下,无法直接获取内存状态。

原则上,我也是看不懂上图的,但直觉告诉我,前者比后者复杂的多。俗话说“人至贱则无敌”,最终,出于成本的考虑,更便宜的动态内存成为主流。

假设你是一个图书馆的管理员,配有一张迷你办公桌。每次有人借书,你会检查办公桌上是否有这本书,如果有就直接给借书人;如果没有,你就需要去书库中找到这本书,再给借书人。很明显,前者几乎不会花费时间,相当于读取寄存器数据,后者就要花不少时间,相对于读取内存数据。

如果是三十年前,那这个场景不会有什么变化,但后来,我们可以做一个小书架,放在书桌旁,能装几本书。缺点是这个书架得用黄花梨做。随着工艺的提高,我们可以做一个三层小书架。这样,我们可以“预测”那些最受欢迎的书,放到书架上,减少(耗时的)书库取书的次数。这就是用静态内存来做CPU Cache的思路。

aijishu_cpu3.jpg

如何设计Cache

缓存机制,理论上缓解了CPU和内存之间性能差距日益增大这个难题。但实际中,缓存数据是否是当前CPU所需要的数据,这就是一个很严肃的问题了。

首先,一级缓存只有32K,而通常内存条则是8G,这就是一个抽屉问题:8*1024个球放到32个抽屉里,如何提高抽屉的利用率,避免过劳或过闲;如何设置球的优先级,是上一次访问的数据优先级高,还是访问次数最多的数据优先级高,或者随机给一个优先级,这是一个Replace policy的设计。

N-way associative

N-way associative具体算法在之前的《CPU简介》中已经谈到,这里默认大家都了解,不讨论具体该细节。

aijishu_cpu4.jpg

如上图,吃饭时间到了,狗狗会遍历所有饭盒,看是否有空位,如果有,则占有该饭盒;如果没有,则挑一个好欺负的狗狗,霸占它的饭盒。这和数据存储是一个思路:假设有8个抽屉,现在需要放一个球,会依次打开抽屉看是否有空抽屉,这称为full associative。好处是能找到一个抽屉来存放球(数据),缺点是需要遍历所有抽屉,当抽屉数目过长时,复杂度是O(n),线性增长。

aijishu_cpu5.jpg

为了优化遍历时间,自然想到用Hash Table。基于上面抽屉的场景,我们现在对8个抽屉编号,所有的球也都有一个唯一的编号(内存地址),然后用编号除以8,根据余数找到对应的抽屉,如果抽屉里面有球,则替换。这样,找到抽屉的时间为O(1),但缺点是容易出现Hash冲突,导致效率下降。这称为direct mapping。     

aijishu_cpu6.jpg

full associative和direct mapping各有利弊,于是两者结合,也就是目前采用的N-way associative的设计方案。如上图,6195 的二进制是 00...0110000 011 0011。这样,在8(2^3)sets中,取绿色的三位,存放在索引3;在4(2^2)sets中,取绿色的二位,存放在索引3中,里面有两个“抽屉”(2-way)可供选择;在2(2^1)sets中,取绿色的后一位,存放在索引1中,里面有四个“抽屉”(4-way)可供选择。

不难发现,full associative和direct mapping是一维的行或列的设计方式,1-way就相当于direct mapping,8-way就是full associative。N-way则是一种行和列的二维设计,提高了灵活性,在遍历和减少Hash冲突之间的互相平衡。

aijishu_cpu7.jpg

如上的公式,我们可以通过C++ template设计一个N-way associative,实现一个缓存策略的模拟。

template <intnCacheSize, intnWayNum, intnBlockSize>
class associativity
{}

Replace policy

有了数据存储方案,如果没有空的区块时,应该替换哪一个区块呢?这里面也涉及到一个算法:每次有新的数据增加到Cache区块时,需要更新每一个区块的优先级,确定一个当前最不重要的数据,以便下次需要时替换。

  • Belady
    最常见的替换算法,FIFO先进先出的策略。每次数据加入队列时,如果该数据已经存在,仍然认为是旧数据
  • Random
    顾名思义,抽死签,随机找一个block替换
  • LRU:Least recently used
    类似FIFO,每次数据加入队列时,如果该数据已经存在,认为是新数据
  • LFU:Least-frequently used
    引用计数,引用次数最少的将被替换掉

当然还有很多替换策略,如上是我自己写的Cache中加入的替换策略,发现并没有明显的好坏之分。

三级缓存

我们的设计中,有三级缓存C1~C3的层级关系,对应到代码中,三者的实现原理都一样,都可以通过templateclass实现,无非是N-way和CacheSize的不同而已。但我们还需要一个CacheManager来管理三个缓存以及内存之间的关系。

首先,写数据时,是否需要写入到内存,还是暂时保存在缓存中,离开缓存时再写入内存;三级缓存中,是否允许存在重复数据;当数据从高一级的缓存中替换出来时,如何加入到下一级缓存中。

最后,需要增加一个计数能力,统计一下缓存命中率。下图是我设计的一个三级缓存模拟器,绿色是一级缓存命中,蓝色是二级,橙色是三级,红色是未命中。

aijishu_cpu8.jpg

Locality

通过上面两部分,我们能了解为何设计CPU Cache以及实现思路,在程序设计时,这些知识有什么用处呢?如何能让我们的编码具备较高的缓存命中率呢?毕竟,有了先进的武器,如果不能熟练掌握,也是无济于事。

Access data sequentially

aijishu_cpu9.jpg

for (int i = 0; i <arr.Length; i += K) arr[i] *= 3;

如上,随着K增加,K=16是一个临界点,说明该CPUCache中,一个Block(Cache Line)存储了16 * sizeof(int) = 64字节,基于缓存的考虑,不难理解,因为CacheLine中的数据连续,因此缓存命中率较高,读写速度很快,因此,在这个临界点内,K的变化,尽管会减少操作指令,但不会带来性能的提升。

记得当年刚毕业时做的面试题,其中一个是遍历二维数组A[M][N],for(M) { for(N)}和for(N){ for(M)}之间有什么区别。前者行优先,访问的内存依次连续,而后者是列优先,内存不连续。

通常一个class会封装多个组件,比如一个Entity,里面包含AI模块,Physics物理模拟模块以及Render模块,通常,我们习惯这样写代码来遍历多个Entity Array:

while (!gameOver)

{

    // Process AI.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->ai()->update();

    }

    // Updatephysics.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->physics()->update();

    }

    // Draw toscreen.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->render()->render();

    }

    // Other gameloop machinery for timing...
}

看上去逻辑优雅,这也是OOP的设计核心:状态的管理。但从Cache的角度而言则非常糟糕,数据角度上,内存是跳跃的。

aijishu_cpu10.jpg

假如我们改造一下代码,将Entity类拆分成三个组件对应的类,然后依次遍历具体的方法:

AIComponent* aiComponents =

new AIComponent[MAX_ENTITIES];

PhysicsComponent* physicsComponents =

new PhysicsComponent[MAX_ENTITIES];

RenderComponent* renderComponents =

new RenderComponent[MAX_ENTITIES];

while (!gameOver)

{

    // Process AI.

    for (int i = 0;i < numEntities; i++)

    {

        aiComponents[i].update();

    }

    // Updatephysics.

    for (int i = 0;i < numEntities; i++)

    {

        physicsComponents[i].update();

    }

    // Draw toscreen.

    for (int i = 0;i < numEntities; i++)

    {

        renderComponents[i].render();

    }

    // Other gameloop machinery for timing...

}

此时,数据访问上,内存是连续的,性能就会有明显的提升,测试中性能提升了50倍。

aijishu_cpu11.jpg

large data structures

我们在看这段有意思的代码:

public longUpdate(byte[] arr, int K)

{

    // Number of iterations – arbitrary

    const int rep =1024*1024; 

    int p = 0;

    for (int i = 0;i < rep; i++)

    {

        arr[p]++;

        p += K;

        if (p >=arr.Length) p = 0;

    }

}

如下图,依次增大array length和K-Step,白色表示时间较短,蓝色表示时间久,会发现,当K为2的N次方时,会有一根突出的蓝线。原因是K间隔下的内存地址,正好导致了Hash冲突,引起了内存和缓存之间的频繁交替,因此性能会下降。

aijishu_cpu12.jpg

在Agner Fog的optimizing\_cpp的9.10中,针对矩阵转置的例子,有更为详细的介绍,这种情况下,我们不妨大块拆成小块的思路,来得到效率的提升。

总结

CPU Cache的介绍就到此结束,希望大家在编码时,能留意让自己的代码更好的发挥缓存的优势。能够认识到OOP编程下,看似整洁的代码下,也夹杂着看不见的性能的牺牲。

作者:Peter6
原文链接:https://mp.weixin.qq.com/s/2fXaJwJHeoIvA_mN1Vj3YA
微信公众号:
LET.jpg

推荐阅读

更多GPU及渲染技术干货请关注Arm Mali GPU技术专栏。
4 阅读 862
推荐阅读
0 条评论
关注数
26
内容数
10
Arm Mali GPU系列相关技术干货
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息