Day-10 近水楼台先得月

近水楼台先得月

tags: IT铁人

区域性原则

有在组装电脑的人就会知道,电脑的储存装置包括记忆体跟硬碟,硬碟又有分成SSD跟HDD,记忆体的空间比较小,存取速度比较快;硬碟的空间通常比较大,存取速度较慢。另外还有很靠近CPU的快取记忆体,存取速度又更快了,我们的指令跟程序都是从这些地方拿来处理的。

在执行程序的时候,如果指令或是资料在需要的时候才抓进来,时间会拉很长,所以我们会期望当我们需要资料时,资料能正好在靠近的地方,就能更快的处理。

不过由於越快的装置储存的空间就越小,这个现象称为区域性。

区域性(Locality):程序在任何一个时间点只会存取一小部份的位址空间。

时间区域性(temporal locality) 空间区域性(spatial locality)
如果一个项目被存许到,那麽它很快就会再次被存取。 如果一个项目被存取到,那麽它位址附近的项目也会很快被存取。

不同的记忆体技术

刚刚提到的三种记忆体(快取记忆体、记忆体、硬碟),他们的技术大概分为以下四种。

资料大概是2015~2018

类型 技术 存取时间 价位(per GB)
快取记忆体 SRAM 1~10ns $1000
主记忆体 DRAM 80ns $10
SSD Flash Memory 100,000ns $1
HDD Magnetic Disk 10,000,000 $0.1

可以看到速度差距很大,但速度快的又很贵,所以才需要我们这个章节讨论的内容。

快取系统与虚拟记忆体

刚刚介绍的记忆体中,我们将快取记忆体(Cache)跟主记忆体(Memory)称为快取系统;主记忆体(Memory)跟硬碟(Hard Disk)称为虚拟记忆体。

简单来说我们会偏向将最需要的部份放在快的那一层,对於快取系统来说放在快取记忆体,对於虚拟记忆体来说放在主记忆体。

每次我们需要东西时,如果它正好在比较快的那层,我们就称为hit,反之称为miss。所以我们要尽可能提昇hit rate,减少miss rate。

当东西不在快的那层时,我们就需要比较多的时间去下面一层寻找,这时要花比较多的时间,称之为miss penalty,就是出错得到的惩罚。

Direct Mapped

记忆体中我们将最小的单位称为block或line,杰哥习惯用block称呼。也就是说Cache从Memory抓资料都是以一个block为单位。不过因为Cache的容量比较小,所以要抓储存资料的方式就很重要。

这边介绍最简单的方式,Direct Mapped。基本上就是用取余数的方式决定要将Memory资料放在Cache的哪个位置,因为解释有点麻烦,直接用例子来说明:

在这边我们假设一个block是4bytes,并且这时CPU要求byte address为38的资料,这时候我们要先算出他在哪个block,透过floor function和除法可以得到是第九个block,那麽第九个block应该要放在Cache的哪个位置?

这边就是direct mapped的重点了,我们只要直接的取9 mod 4的结果即可,结果的1就代表我们应该放在Cache的第一个block。

另一件要注意的事情是,不只有第九个block会对应到Cache的第一个block,还有1,5,13等等,所以我们还要另外标记这是哪个个Memory block,只要取9除以4的商即可,也就是放在tag栏位的2,如此一来我们就可以保证这格不会被误会成是第五个Memory block之类的。

Cache Memory图解

因为Cache不可能只有4个block,这边用1024(1K)大小的Cache Memory简略说明刚刚的对照关系:

我们假设byte address有32bits。以下慢慢说明每个分区代表的意思。

  • 对於一个block有4bytes来说,我们需要2bits指名要哪个byte。
  • 对於1024的Cache Index,我们取後面10bits指名,也就是余数的部份。
  • Tag的话就是剩下的20bits。
  • 另外我们需要一个Valid bit表示这格的内容是不是有效的,有时候资料可能被人取走,我们没办法保证资料正确,或是在程序第一次载入时,其中的资料可能是上次残留的,所以也要将Valid bit设定为0表示无效资料。
  • Cache中的Data就是我们要的资料,取出来的32bits会跟byte offset比对,确认要取哪段byte。

利用空间区域性

不过刚刚一个block只放4bytes的资料,也就是一个word的大小。这样没有用到空间区域性的特性,所以我们要试着增加一个block的大小,这样子一次拿出来的空间就更大,就越有机会抓到等等可能用到的资料,通常对於阵列最有效果。

增加block大小就需要多几个bit指名要哪个word,以下展示一个block有四个word的Cache Memory:

这时候除了原本有的东西以外,还要多一个Block offset,指名要block中的哪个word,其余的部份都一样,只有tag的部份被压缩空间。

可以想成因为Block数目变少了,每个Index可能分配到的Memory Block变少了,所以tag的数量就便少了。

What's Next?

除了提昇Block数量以减少我们还有其他技巧可以减少miss rate,这部份留到下个单元再来解释。

就酱~ㄅㄅ。

上一篇 下一篇
在Hazard寻求解法是否搞错了什麽 Set Associative Cache

<<:  D-8. Rails 用Postman测试自己的WEB API && Valid Parentheses

>>:  从零开始的8-bit迷宫探险【Level 14】让主角奔跑吧!Running Sam

ETA Screen (2)

SavedStateHandle 不知道大家有没有发现在「ETA Screen (1)」贴出来的 E...

【day12】InvitationDetailFragment

今天我们要做的是邀约详细资讯! 继昨天我们完成Recyclerview之後,我们今天要让我们使用者...

[day-5] 我与我的第一个程序,HelloWorld和背後的历史!

Hello World 的起源 通常我们在测试一个程序或是一个环境是否正常 会习惯使用 Hello ...

Day 22 - Memorized Hook: useMemo

...> 如果有错误,欢迎留言指教~ Q_Q 没写完啦 useMemo 回传一个 memoi...

test

...