【计组 | Cache原理】讲透Cache的所有概念与题型方法

2024-09-01 03:44

本文主要是介绍【计组 | Cache原理】讲透Cache的所有概念与题型方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Cache

写在前面:高速缓存Cache一直408中的重点以及绝对的难点,前几天我在复习计组第三章的知识,Cache这一节把我困住了,我发现很多概念我都不记得了,一些综合性强的计算题根本无从下手,我深知Cache对于每个408的初学者来说,都是痛点、难点所在,因此花了一晚上狠狠学习Cache总结做了这个Cache“大观”,尝试用最精简且具有逻辑性的方式,只讲重难点和考点,给大家讲透Cache(我发现市面上很多课程讲解的都是比较零散且不好消化的,没有抓住主要矛盾),用最短的时间达到做出考研408题目的要求。

为什么要使用Cache?

为了引出Cache这个高速缓存的妙用,我们先来认识一个概念—时间局部性

所谓的时间局部性就是同一条指令在短时间内多次运行,比如循环结构,那么我们在循环体内重复更新的变量就是具有时间局部性的,而学过操作系统我们就知道程序是放在内存里运行的,由于时间局部性,程序运行时频繁访问的数据就集中在主存中的某几块区域内,于是我们只要把这几块区域的指令、数据全都复制到CPU的Cache里,这样CPU就可以先去Cache里看看有没有数据如果有直接取出,如果没有再取访存,提高了取数据的效率。由于命中率很高,平均访问是接近于Cache的访问时间的!!(小考点)

那么主存究竟是将数据复制到Cache内的呢?我们继续来看!

关于Cache的所有概念(重点)⭐

我们现在需要把主存中的部分高频访问内容复制到Cache中,最简单的思路就是把主存和Cache都划分出一个个的相同大小的区域,然后就可以直接把数据复制过去了对吧。实际上计算机也是这么做的。

  1. **“块”**的概念:我刚刚说的大小相同的区域,在主存中叫作主存块,在Cache中叫作Cache块或Cache行(注意这两是一个东西,题目中给出块或者行都是OK的)。主存块的大小就等于Cache块的大小!!这是第一点需要我们铭记于心的,原理我刚刚已经说过了,就是方便交换数据。

  2. Cache的数据结构模型(重点看,有个记忆能画出来是最好的)

    在这里插入图片描述

    从王道教材书这张图,我们可以看到Cache主要分为了tag标记位和存储数据两部分,数据部分是以“块”为单位与内存交换数据的,如果不够清晰,我们来看小林coding给出这张结构图:

    在这里插入图片描述

    我们可以清楚地看到每一个Cache行都分为了tag位和数据块,对应的主存也要划分成一个个一样大小的数据块,那么主存是怎么进行划分操作的呢?我们需要引出一个概念“主存地址”。

  3. 主存地址:将主存划分为多个主存块后,我们就需要一些数据位来标识块号,因此主存地址可以划分为两部分:高位地址(标识块号)+低位地址(块内地址)。请一定要记住这个划分它是我们后面做题的逻辑基点,同样的Cache以同样的划分方式:高位地址(标识块号)+低位地址(块内地址)

  4. 有效位:Cache中除了拥有上述的主要部分tag+数据块,还有一些特别的东西,我们先从有效位开始介绍。

    1. 工作原理:有效位用来标记对应的 Cache行中的数据是否是有效的,如果有效位是 0,无论Cache 中是否有数据,CPU 都会直接访问内存,重新加载数据。
    2. 作用:有了这个有效位,我们想要淘汰一个主存块数据就很容易了,只需要把有效位置0,装入一个新的主存块的时候,再把有效位置为1即可。
  5. CPU访问过程:我一开始的时候就说了,如果Cache中已经有了数据,我们就不要去访存了,但是如果在Cache中没有找到数据,我们就要去内存中读取并把数据块复制到Cache块中,这个过程也就是Cache的缺失处理。重点来了,到底是谁去完成这些判断、替换数据块工作的呢?为了保证速度当然只能由硬件来实现了,因此Cache对于程序员来说是透明的,所有过程都由硬件自动实现。硬件自动实现,硬件自动实现!!!重要的事情说三遍。

Cache和主存的映射方式(超级重点⭐⭐)

这一块请跟着我一起理解并记忆!!考察计算题!

我们一直再说交换数据,那么我们怎么把主存的数据块通过地址映射的方式,复制到Cache行中呢?先来了解一下三种映射方式:

1)三种映射方式

  1. 直接映射:每个主存块映射到Cache的特定行中,CPU访问某个特定行即可
  2. 全相联映射:主存块可以映射到Cache的任意行中,需要把Cache所有行都扫一遍
  3. 组相联映射:把Cache分成多个组,每个组又有多个行,主存块可以放到特定组的任意行中,访问的时候只需要看看那特定组的所有行

2)直接映射的理解

  1. 我们先来看这张图:

    在这里插入图片描述

  2. 我们需要把主存块映射到特定的Cache行中,因此就需要一个转化的方式,我们把它提炼成一个公式:

    cache 行号 = 主存块号 % Cache行数

    我们来解释一下:假设我们一个主存块的大小为4B,给出一个主存地址x(还记得主存地址是什么吗,上面已经讲过高位标识块号低位为快内地址),我们就可以通过x/4去找到我们的主存块号(假设是从0标号的),我们也可以通过转成二进制然后通过右移操作(比如/4就是右移两位)来得到块号,再用块号去%Cache行数(同样的模运算也可以用二进制取后n位得到,等会会演示)。

    Cache行数如果题目中没有给出,就是用Cache的总容量去 / cache块的大小(和主存块是一样大的)来得到。

    好好理解一下这个公式,后面我会用综合性很强的计算题带着大家来做练习加深理解。

  3. 主存地址划分:

    三部分组成:标记Tag+Cache行号(也有叫索引的)+块内地址(也有叫块内偏移的)

    其中主存块号就是去除块内地址的部分,即标记+Cache行号。我们刚刚一直没有介绍tag位是用来干嘛的,只是引出了这个概念,实际上它是作为主存块和Cache块是否匹配的验证信息,如上图用一个比较器进行匹配的操作,同时还要去看有效位是否为1,不过这一块内容不是考察的重点,我们就算不太能理解也没有关系,能把各部分的位数计算出来就行了。

  4. 内存映射表:很多教材上都不讲这一点,所以对同学们造成了概念上的迷惑,到底什么是地址映射表?一句话,地址映射表就是Cache中除了装数据部分的大小,要用标记位+特殊位得到,等会看一道题。

3)全相联和组相联

理解了上面的直接映射后,这两种就好理解多了。

  1. 全相联映射:给每一个行都设置一个比较器 ,根据tag字段按内容访问Cache中的主存块,对于硬件开销比较大,但是能解决直接映射的冲突问题。

    在这里插入图片描述

    我们需要记住的是主存地址结构:标记+块内地址 (最简单的一种,只有两部分)

  2. 组相联映射:组间采用直接映射,组内采用全相联映射。

    在这里插入图片描述

    1. Cache行数 = 组数 * 路数(每一组的大小是相等的,路数是指每一组有多少个Cache行,题目一般给出的也是k路组相联的信息,不要搞混了)
    2. 地址结构:标记+组号+块内
    3. 组号的计算方法和直接映射中Cache行号的计算思想是一样的,先求出主存块号,再对组数取模,后面直接来看例题就更清晰了。
    4. 当路数为1时,就变成一块一组,也就退化成直接映射方式,当路数为Cache行数时,所有块都变成了一组,也就变成了全相联映射。

以上内容,请好好理解吃透,特别是对于主存地址的三种划分映射结构,Cache的模型与概念,及计算公式,下面我们进入好题精析部分。

好题赏析

题目

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

讲解笔记

在这里插入图片描述
在这里插入图片描述
讲解视频跳转:30min带你狠狠拿捏Cache所有知识与题型方法

这篇关于【计组 | Cache原理】讲透Cache的所有概念与题型方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1125847

相关文章

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

计组基础知识

操作系统的特征 并发共享虚拟异步 操作系统的功能 1、资源分配,资源回收硬件资源 CPU、内存、硬盘、I/O设备。2、为应⽤程序提供服务操作系统将硬件资源的操作封装起来,提供相对统⼀的接⼝(系统调⽤)供开发者调⽤。3、管理应⽤程序即控制进程的⽣命周期:进程开始时的环境配置和资源分配、进程结束后的资源回收、进程调度等。4、操作系统内核的功能(1)进程调度能⼒: 管理进程、线

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

【北交大信息所AI-Max2】使用方法

BJTU信息所集群AI_MAX2使用方法 使用的前提是预约到相应的算力卡,拥有登录权限的账号密码,一般为导师组共用一个。 有浏览器、ssh工具就可以。 1.新建集群Terminal 浏览器登陆10.126.62.75 (如果是1集群把75改成66) 交互式开发 执行器选Terminal 密码随便设一个(需记住) 工作空间:私有数据、全部文件 加速器选GeForce_RTX_2080_Ti

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit