CPU Cache简介

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

为什么需要CPUCache

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

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

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

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

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

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

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

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

如何设计Cache

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

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

N-way associative

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

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

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

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冲突之间的互相平衡。

如上的公式,我们可以通过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来管理三个缓存以及内存之间的关系。

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

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

Locality

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

Access data sequentially

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的角度而言则非常糟糕,数据角度上,内存是跳跃的。

假如我们改造一下代码,将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倍。

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冲突,引起了内存和缓存之间的频繁交替,因此性能会下降。

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

总结

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

下一篇分享一下CPU系列的最后一部分内容:SIMD以及面向数据DOD

原文发布于微信公众号 - LET(LET0-0)

原文发表时间:2018-08-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏熊二哥

企业模式和设计模式快速入门

相信大家对GOF的23个设计模式和Martin Fowler的企业应用架构模式都有过了解,这部分的内容和知识非常驳杂,不过真正常用的模式并不多,比如单例模式、策...

1997
来自专栏极客生活

从计算机体系结构到高性能编程实践(一)

上来先推荐一本书,《计算机体系结构:量化研究方法(第五版)》,英文能力比较好的建议阅读原版。

1102
来自专栏小文博客

谷歌浏览器这样设置后看小说无广告

谷歌浏览器是目前为止口碑比较好的一款浏览器吧,虽然有些地方操作确实不如其他浏览器方便,但是大体上还是比其他浏览器好太多。

2804
来自专栏程序员互动联盟

程序语言变形记

随着科技的发展我们生活中接触到的应用程序越来越多,它给我们的生活带来了很大的便利。移动端安卓,苹果大肆横行;pc上QQ,浏览器大行天下。我们在享受这些软件给我们...

3305
来自专栏Python数据科学

Python定期爬取GitHub上每日流行项目

介绍一个在GitHub上看到的通用的python爬虫,难度不大,是一个蛮好玩的点,顺便总结一下python爬虫的一些需要注意的点。

2132
来自专栏北京马哥教育

Linux 的 OOM 终结者

现在是早晨6点钟。已经醒来的我正在总结到底是什么事情使得我的起床闹铃提前了这么多。故事刚开始的时候,手机铃声恰好停止。又困又烦躁的我看了下手机,看看是不是我自己...

4156
来自专栏WeTest质量开放平台团队的专栏

[分享干货晒技术]Unity 手游内存优化分享

Mono下的foreach使用需谨慎。频繁调用容易触及堆上限,导致GC过早触发,出现卡顿现象。

2812
来自专栏机器学习和数学

[编程经验] 我是如何半自动抓取素材公社图片的

网络爬虫是一件比较繁琐的事情,特别考验人的耐心。但又是非常令人着迷的一件事,因为当你从网络上爬到了自己的想要的数据,满满的成就感油然而生。但是我对爬虫掌握的并不...

3525
来自专栏FreeBuf

逆向华为路由器第三部分

引文 在前面两个部分(1,2)已经介绍了UART,BusyBox等部分的逆向调试,而这篇将会开始在流量分析方面下手,来逆向出更多的信息。 正文 请看下图,数据存...

2048
来自专栏码字搬砖

JVM内存模型

先磨磨肩擦擦掌,小二很早就听说jvm的内存很是奇特,今日一看果然不同凡响。下面且听小二一一道来。

2395

扫码关注云+社区

领取腾讯云代金券