-
主存到Cache直接映射、全相联映射和组相联映射
2016-11-29 14:30:46为了把信息放到Cache中,必须应用某种函数把主存地址定位到Cache中,这称为地址映射。---- 在信息按这种映射关系装入Cache后,CPU执行程序时,会将程序中的主存地址变换成Cache地址,这个变换过程叫做地址变换。...---- Cache的容量很小,它保存的内容只是主存内容的一个子集,且Cache与主存的数据交换是以块(cache line)为单位的。为了把信息放到Cache中,必须应用某种函数把主存地址定位到Cache中,这称为地址映射。
---- 在信息按这种映射关系装入Cache后,CPU执行程序时,会将程序中的主存地址变换成Cache地址,这个变换过程叫做地址变换。
Cache的地址映射方式有直接映射、全相联映射和组相联映射。
假设某台计算机主存容量为1MB,被分为2048块,每个Block为512B;Cache容量为8KB,被分为16块,每块也是512B。
下面以此为例介绍三种基本的地址映射方法。
1. 直接映射
---- 一个内存地址能被映射到的Cache line是固定的。就如每个人的停车位是固定分配好的,可以直接找到。缺点是:因为人多车位少,很可能几个人争用同一个车位,导致Cache淘汰换出频繁,需要频繁的从主存读取数据到Cache,这个代价也较高。
直接映射的Cache组织如图(1)所示。主存中的一个块只能映射到Cache的某一特定块中去。例如,
主存的第0块、第16块、第32块、第48块、……、第2032块等128块,只能映射到Cache的第0块;
主存的第1块、第17块、第33块、第49块、……、第2033块等128块,只能映射到Cache的第1块;
以此类推,主存的第15块、第31块、第47块、……、第2047块等128块,只能映射到Cache的第15块中。
映射完毕,Cache总共有0~15即16块,主存中的每128(2048/16)块,只能映射到Cache中的某一个块中。
即映射规则为cache line index = (主存(Page)的line数)%(cache中 cache line的总数)
主存的line数是0~2047,cache中cache line的总数是16.
图(1)
直接映射是最简单的地址映射方式,它的硬件简单,成本低,地址变换速度快,而且不涉及替换算法问题。但是这种方式不够灵活,Cache的存储空间得不到充分利用,每个主存块只有一个固定位置可存放,容易产生冲突,使Cache效率下降,因此只适合大容量Cache采用。例如,如果一个程序需要重复引用主存中第0块与第16块,最好将主存第0块与第16块同时复制到Cache中,但由于它们都只能复制到Cache的第0块中去,即使Cache中别的存储空间空着也不能占用,因此这两个块会不断地交替装入Cache中,导致命中率降低。
2. 全相联映射
---- 主存中的一个地址可被映射进任意cache line,问题是:当寻找一个地址是否已经被cache时,需要遍历每一个cache line来寻找,这个代价很高。就像停车位可以大家随便停一样,停的时候简单,找车的时候需要一个一个停车位的找了。
图(2)是全相联映射的Cache组织,主存中任何一块都可以映射到Cache中的任何一块位置上。
图(2)
全相联映射方式比较灵活,主存的各块可以映射到Cache的任一块中,Cache的利用率高,块冲突概率低,只要淘汰Cache中的某一块,即可调入主存的任一块。但是,由于Cache比较电路的设计和实现比较困难,这种方式只适合于小容量Cache采用。
3. 组相联映射
---- 组相联映射实际上是直接映射和全相联映射的折中方案,其组织结构如图(3)所示。
主存和Cache都分组,主存中一个组内的块数与Cache中的分组数相同,组间采用直接映射,组内采用全相联映射。也就是说,将Cache分成2^u组,每组包含2^v块,主存块存放到哪个组是固定的,至于存到该组哪一块则是灵活的。即主存的某块只能映射到Cache的特定组中的任意一块。主存的某块b与Cache的组k之间满足以下关系:k=b%(2^u).
例如,Cache分为8组(u=3),每组2块(v=1),主存分为128个区,每个区16块。
图(3)
主存中的各块与Cache的组号之间有固定的映射关系,但可自由映射到对应Cache组中的任何一块。例如:
--主存的第0块、第2^u块、第2×(2^u)块、…第255x(2^u)即255x8=2040块等256块均映射于Cache的第0组,但可映射到其中的第0块或第1块;
--主存的第1块、第2^u+1块、第3^(2^u)+1块、…第255x(2^u+1)即2041块等均映射于Cache的第2组,但可映射到Cache第2组中的任意一块;
--主存的第2块、第2^u+2块、第(2^u)x2+2块、…第2042块等均映射于Cache的第3组,但可映射到Cache第3组中的任意一块;
--主存的第7块、第2^u+7块、第2^(u+1)+7块、…第2047块等均映射于Cache的第8组,但可映射到Cache第8组中的第14块或第15块。
常采用的组相联结构Cache,每组内有2、4、8、16块,称为2路、4路、8路、16路组相联Cache。以上为2路组相联Cache。组相联结构Cache是前两种方法的折中方案,适度兼顾二者的优点,尽量避免二者的缺点,因而得到普遍采用。
实例分析:
1.容量为64块的Cache采用组相联方式映像,字块大小为128字节,每4块为一组,若主容量为4096块,且以字编址,那么主存地址为(19)位,主存区号为(6)位。
解:组相联的地址构成为:区号+组号+块号+块内地址。
主存的每个分区/组大小与整个Cache大小相等,故此主存需要分的区数为:4096/64=64,因为26=64,因此需要6位来表示区号。每4块为一组,故共有组数 64/4 = 16 ,因为24=16,因此需要4位表示组号。每组4块,故表示块号需要2位。
块内地址共128字节,27=128,所以块内地需要7位表示。所以:主存地址的位数=6+4+2+7 = 19
主存区号的位数=6
个人见解:Cache有u组,每组有v块,即u = 16,v = 4,Cache大小:64块×128B = 8KB。
主存大小:4096×128B = 2^12*2^7 = 2^19,即主存地址有19位。4096/64= 2^6主存区号为6位。
2.某 32 位计算机的 cache 容量为 16KB,cache 块的大小为 16B,若主存与 cache 的地址映射采用直接映射方式,则主存地址为 1234E8F8(十六进制)的单元装入的 cache 地址为__C__。
A. 00 0100 0100 1101 (二进制)
B. 01 0010 0011 0100 (二进制)
C. 10 1000 1111 1000 (二进制)
D. 11 0100 1110 1000 (二进制)解:Cache大小为16KB,块大小为16B,所以Cache被分成16KB/16B=1024块,因210=1024故需要10位来表示块数。
24=16故块内地址需要4位来表示。所以Cache的地址线位置为14位。
由于采用直接映像的方式,所以主存的后14位就是要装入的到Cache中的位置。故选 C.
个人见解:Cache的容量是16KB = 16×1024B = 16384B,主存的地址为0x1234E8F8/(16×1024B)= 18643. 该地址对应的是主存的第18643块。
根据公式:cache的块地址i = 主存的块地址 % 16384 = 1234E8F8 - 1234C000 = 0x28F8 选C
-
Go 映射
2019-09-20 18:58:11映射的内部实现和基础功能 映射是一种数据结构,用于存储一系列无序的键值对,实现基于键的快速检索数据 文章目录映射的内部实现和基础功能1.内部实现2. 创建和初始化a. make函数声明映射b. 字面量声明映射参考: ...映射的内部实现和基础功能
映射是一种数据结构,用于存储一系列无序的键值对,实现基于键的快速检索数据
文章目录
1.内部实现
映射是一个存储键值对的无序集合
a. 可以使用类是处理数组和切片的方式迭代映射中的元素
b. 映射是无序的,每次迭代映射的顺序都有可能不一致
注:无序的原因是映射的实现使用了散列表散列表
映射的散列表包含一组桶:
a. 在存储删除或者查找键值对的时候,所有的操作都要选择一个桶。操作时将指定的键传递给映射的散列函数,就能选中对应的桶
散列函数的作用是生成一个索引,并将键值对分布到所有的可用的桶里
随着映射存储的增加,索引分布越均匀,访问键值对的速度就越快2. 创建和初始化
a. make函数声明映射
// 创建一个键为string值为int的映射 rain_dict := make(map[string]int) // 输出结果: // == rain_dict: map[]
b. 字面量声明映射
映射的初始长度很根据初始化时的键值对的数量来确定
1) 映射的键可以使任意值
切片、函数以及包含切片的结构类型,由于具有“引用语义”,不能作为键
2) 值的类型可以是内置的类型,也可以是可以用 == 运算符作比较的 结构类型// 创建一个映射,并初始化数值 rain_dict_1 :=map[string]string{"china": "BeiJing", "america":"NewYork"} // 输出结果: // == rain_dict_1: map[america:NewYork china:BeiJing]
3. 使用映射
a. 映射赋值
// 创建一个空映射 rain_dict_2 := map[string]int{} // 映射赋值 rain_dict_2["top"] = 5 rain_dict_2["right"] = 6 // 输出结果: // == rain_dict_2: map[right:6 top:5]
b. nil映射
nil 映射不能存储键值对,否则会发生一个语法错误
// 声明式创建nil映射 var rain_dict_3 map[string]int // nil 映射赋值 rain_dict_3["msit"] = 2 // 输出结果: // panic: assignment to entry in nil map
c. 判断键值是否相互匹配
i. 同时获取值与这个值是否存在的标志
// 创建一个映射 rain_dict_4 := map[string]int{"Chinese": 98, "English": 86} // 同时获取值和是否存在的标志 // value 零值(不存在),key bool value, key := rain_dict_4["math"] if key{ fmt.Printf("Both Value: %d", value) }
d. 迭代映射
使用关键字range迭代映射
// 创建一个映射 rain_ditc_5 := map[string]int{"hight": 120, "width": 45, "kg": 48} // 迭代打印键值对 for key, value := range rain_dict_5{ fmt.Printf("Key: %s, Value: %d, Key_addr: %X, Value_addr: %X", key, value, &key, &value) } // 输出结果: // Key: hight, Value: 120, Key_addr: C0000521C0, Value_addr: C000066080 // Key: width, Value: 45, Key_addr: C0000521C0, Value_addr: C000066080 // Key: kg, Value: 48, Key_addr: C0000521C0, Value_addr: C000066080
删除一项元素
// 创建一个映射 rain_dict_6 := map[int]int{1:1, 2:2, 3:3} // 删除key=2的元素 delete(rain_dict_5, 2) // 输出结果: // == Rain_dict_6: map[1:1 3:3]
4. 函数间传递映射
在函数间传递映射,并不会 复制映射作为副本
当对这个映射修改时,所有对这个映射的映射都会察觉到这个修改package main import "fmt" func main() { rain_dict_7 := map[string]int{"Chinese": 98, "English": 86, "Math": 90} Rain_map_1(rain_dict_7) Rain_map_2(rain_dict_7) Rain_map_delete(rain_dict_7, "English") fmt.Println("== rain_dict_7: ", rain_dict_7) } func Rain_map_1(rain map[string]int) { rain["Physical"] = 71 fmt.Println("== Rain_map_1: ", rain) } func Rain_map_2(rain map[string]int) { rain["Naturl"] = 82 fmt.Println("== Rain_map_2: ", rain) } func Rain_map_delete(rain map[string]int, key string){ fmt.Println("== Pre_delete_map: ", rain) delete(rain, key) } // 输出结果: // == Rain_map_1: map[Chinese:98 English:86 Math:90 Physical:71] // == Rain_map_2: map[Chinese:98 English:86 Math:90 Naturl:82 Physical:71] // == Pre_delete_map: map[Chinese:98 English:86 Math:90 Naturl:82 Physical:71] // == rain_dict_7: map[Chinese:98 Math:90 Naturl:82 Physical:71]
参考:
-
同态映射 同构映射
2020-04-27 11:50:081. 通俗来说,同构是指具有相同...2. 两个代数结构相同是指它们之间至少存在一个同构映射。同构映射要满足两个条件:它是集合之间的双射或一一对应;它保持代数结构的所有运算及一些特殊元素,比如,单位元、零元素...1. 通俗来说,同构是指具有相同的代数结构。代数结构由一个或多个集合、若干运算及一些运算规则所唯一确定。代数结构相同的含义是指:除了表示集合元素的符号有可能不同外,对应集合的元素个数相同,集合上的运算一致,运算规则也完全一样。
2. 两个代数结构相同是指它们之间至少存在一个同构映射。同构映射要满足两个条件:它是集合之间的双射或一一对应;它保持代数结构的所有运算及一些特殊元素,比如,单位元、零元素等等,尽管有些要求可以由其它主要条件推出。
3. 举个例子,两个群之间的同构映射为集合之间的双射,且该映射保持群的乘法运算。即,先乘积后映射与先映射后乘积的结果一致。
4. 研究代数结构的主要目的是对其进行分类,或者说找出所有的这种代数结构。同构的代数结构可以不加区分,把它们可以看成一样的。因此,代数结构的分类就是找出该代数结构的所有同构类。
5. 如果两个代数结构不同构,为了研究它们之间的关系,可考虑它们之间保持运算的映射,这就是同态的概念。同态比同构更一般、广泛;同构只是同态的特例。
6. 同态不是同构的原因主要体现在:相应的映射不是双射,即,不是单射或不是满射。当然也可能既不是单射也不是满射。当映射不是满射时,我们只需考虑映射的像集,这个像集是原来代数结构的子结构。比如,对群的情形,同态的像集是一个子群。用子结构替换原来的代数结构,原来的映射变成了满射!
7. 当映射不是单射时,不同的元素被映到相同的元素。这时,可以把映到同一个元素的元素看成是一样的,或者说它们是等价的。这样我们将得到一个等价关系,做商集。在这个商集上诱导的映射就是一个单射了。这就是同态基本定理的主要想法。
8. 在这个商集上可以定义类似的代数结构,使得前面提到的映射是同态。从这个商代数到上述提到的子代数诱导的映射就是一个同构映射了。
-
mybatis 映射器的自动映射和驼峰映射
2017-09-19 21:59:56映射器的自动映射和驼峰映射mybatis提供了自动映射功能,在默认情况下是开启的。在setting中有两个可以配置的选项 autoMappingBehavior和mapUnderscoreToCamelCase。它们分别控制自动映射和驼峰式映射。 配置自动...##映射器的自动映射和驼峰映射
mybatis提供了自动映射功能,在默认情况下是开启的。在setting中有两个可以配置的选项 autoMappingBehavior和mapUnderscoreToCamelCase。它们分别控制自动映射和驼峰式映射。
配置自动映射的取值范围是:- NONE 不自动进行映射
- PARTIAL 默认值,只对没有嵌套的结果集进行自动映射
- FULL 对于所有的结果集进行映射,包括嵌套结果集。
<select id="getRole" parameterType="role" resultType="role"> SELECT id,roleName , note FROM role WHERE id = #{id} </select>
当我们数据库中字段名为roleName且对应的pojo中的属性名称也为roleName时,可以完成自动映射。但是当数据库字段名为role_name样式时,可以通过开启驼峰映射方式,完成任务。
配置mapUnderscoreToCamelCase:<settings> <setting name="mapUnderscoreToCamelCase" value="true"/> </settings>
映射文件中的sql语句:
<select id="getRole" parameterType="role" resultType="role"> SELECT id,role_name , note FROM role WHERE id = #{id} </select>
此时pojo中对应role_name字段的属性名仍为roleName。
但是mybatis会严格按照驼峰式映射规则完成映射,这样pojo和数据字段严格对应,降低了灵活性。在实际开发中有些映射更加复杂,所以一般采用resultMap方式,建立结果集映射。 -
docker文件夹映射的两种方式---主机卷映射和共享文件夹映射
2018-08-21 16:20:26主机卷的映射 使用共享存储的映射 docker容器不保持任何数据 重要数据请使用外部卷存储(数据持久化) 容器可以挂载真实机目录或共享存储为卷 主机卷的映射 [root@docker1 ~]# mkdir /var/data [root@docker1 ~... -
resultMap的用法以及关联结果集映射
2018-08-05 11:05:48resultType resultType可以把查询结果封装到pojo类型中,但必须pojo类的属性名和查询到的数据库表的字段名一致。...resultMap可以实现将查询结果映射为复杂类型的pojo,比如在查询结果映射对象中包... -
直接映射,组相连映射以及全相连映射
2018-05-23 21:52:16Cache的容量很小,它保存的内容只是主存内容的一个子集,且Cache与主存的数据交换是以块为单位的。为了把信息放到Cache中,...Cache的地址映射方式有直接映射、全相联映射和组相联映射。假设某台计算机主存容量为... -
网站开发进阶(三)Windows NAT端口映射
2015-10-22 16:25:02Windows NAT端口映射 由于有需求进行端口映射,又不想装乱七八糟的软件,Windows本身自带的路由远程访问配置太麻烦,还要两块网卡,坑爹啊。 其实Windows本身命令行支持配置端口映射,条件是已经安装了IPV6,启不... -
Java之映射(map)
2018-06-06 21:23:48集是一个集合,它可以快速地...映射(map)数据结构就是为此而设计的。映射用来存放键/值对。如果提供了键,就能够查找到值。它们之间是一一对应关系。 1.基本映射操作: Java类库为映射提供了两个通用的实现:Has... -
静态映射和动态映射
2018-02-18 21:46:17无论静态映射还是动态映射目的都是将外设地址映射到虚拟地址的空间(3G-4G)中分配给用作外设映射的虚拟地址空间(开启mmu后cpu看到的都是虚拟地址,访问外设时同样需要映射到虚拟地址空间) 一般写寄存器读寄存器... -
hibernate + spring.xml 实体类映射几种方法的介绍
2017-05-23 14:40:58由于spring对hibernate配置文件hibernate.cfg.xml的集成相当好, 所以,在项目中我一直使用spring的org.springframework.orm.hibernate....LocalSessionFactoryBean有好几个属性用来查找hibernate映射文件: ma -
映射参数
2017-08-05 10:51:27映射参数 -
mybatis 自动映射与驼峰映射(xml映射配置四)
2018-10-26 10:13:03自动映射 autoMappingBehavior 指定 MyBatis 应如何自动映射列到字段或属性。 配置属性 含义 NONE 表示取消自动映射; PARTIAL 只会自动映射没有定义嵌套结果集映射的结果集。 FULL 会自动映射任意复杂... -
什么是映射?如何清晰的理解映射?
2018-06-29 11:32:53我们在计算机科学和数学里经常用到映射概念,这里打个比方就容易理解了 不废话 直接作出最直白的解释 : 生活里存在大量的对应 : 比如一个人的身份证号对应一个人 一张电影票对应一个人 一个丈夫配一个妻子 或者一... -
URL映射
2018-07-31 22:04:48[CCF]URL映射 Question URL 映射是诸如 Django、Ruby on Rails 等网页框架 (web frameworks) 的一个重要组件。对于从浏览器发来的 HTTP 请求,URL 映射模块会解析请求中的 URL 地址,并将其分派给相应的处理代码... -
Arnold映射(猫映射)原理及 matlab源码
2020-02-19 12:45:37猫映射(Cat映射),也称为Arnold映射,由俄国数学家弗拉基米尔·阿诺德(Vladimir Igorevich Arnold)提出,在Arnold授课的时候经常使用猫的图像作为例子,故称为“猫映射”。这是一种在有限区域内进行反复折叠、... -
浅谈cache的直接映射、全相联映射和组相联映射
2019-06-24 11:27:34对于cache的几种映射方式进行一个小总结,方便以后自己不会了来看看 以下用图书馆坐座位的例子来说一说直接映射、全相联映射和组相联映射。 对于直接映射,每个块在cache中只能有一个位置,非常局限,就好像图书馆里... -
容易理解的计算机组成原理中主存与Cache的3种映射方式(直接映射,全相联映射,组相联映射)
2020-07-28 22:41:39容易理解的计算机组成原理中主存与Cache的3种映射方式(直接映射,全相联映射,组相联映射) 一.为了让大家更加方便的理解,我首先设置了两个问题,同时也写了相应的个人所理解的答案 1.为什么引入Cache? 答: ... -
【MyBatis学习06】输入映射和输出映射
2016-06-12 21:49:42在前面几篇博文的例子中也可以看到mybatis中输入映射和输出映射的身影,但是没有系统的总结一下,这篇博客主要对这两个东东做一个总结。我们知道mybatis中输入映射和输出映射可以是基本数据类型、hashmap或者pojo的... -
Docker运维笔记-Docker端口映射
2016-06-21 23:33:29为什么要端口映射? 端口映射的指令是什么? 如何查看端口映射是否成功? -
【Mybatis高级映射】一对一映射、一对多映射、多对多映射
2016-12-16 21:33:52当我们学习heribnate的时候,也就是SSH框架的网上商城的时候,我们就学习过它对应的高级映射,一对一映射,一对多映射,多对多映射。对于SSM的Mybatis来说,肯定也是差不多的。既然开了头了,我们就也来简单说一些... -
ES6:map映射数组映射
2019-01-11 14:52:121、将一个普通数组映射为对象数组 将[1,2,3] 映射为 [{id: 1}, {id: 2}, {id: 3}] var arr=[1,2,3]; arr=arr.map(item=> { // item是数组中的每一个值 return {id:item} }) console.log(arr); //[{id: ... -
upnp 端口映射
2018-07-10 15:34:25简介 处于内网的机器,因为没有一个公有的Ip,外面是无法主动连接到内网的设备。...UPNP端口映射将一个外部端口映射到一个【内网Ip:端口】,当然也指明了使用的协议是UDP,TCP,还是此映射同时适应UDP和TCP。 UPN... -
Cache地址映射
2018-09-01 15:17:35理解Cache地址映射之前补充一些基础知识,Cache的地址映射和MMU(内存管理单元)和TLB Cache(转译查找缓存)中的映射是有区别的。Cache、TLB Cache、MMU在CPU中结构如图1所示,图1展现的是Cortex A9 Processor内部... -
数据结构之映射
2020-09-08 22:58:18数据结构之映射 -
扩散映射
2018-03-27 19:25:33扩散映射(diffusion map)本文出发点: 在论文<constraints as features>中,将 不连约束 的添加 转为 特征空间的增广,用到了样本在扩散空间的分布,而扩散空间的分布是由扩散映射得到的。注:蓝色... -
集合和映射
2019-10-05 21:25:41集合和映射 -
高等数学 —— 映射与函数 —— 映射
2019-02-26 19:09:19映射是现代数学中的一个基本概念,而函数是微积分的研究对象,也是映射的一种 1.映射概念 设X、YX、YX、Y是两个非空集合,如果存在一个法则fff,使得对XXX中每个元素xxx,按法则fff,在YYY中有唯一确定的元素yyy与之...
-
axure 8元件库.zip
-
Azure公有云测试计划.xlsx
-
【数据分析-随到随学】Hive详解
-
SIFT特征提取
-
23种JAVA设计模式
-
clickhouse bitmap入门
-
搞机助手_V4.8.1.zip
-
机器学习基础补习08---决策树和随机森林
-
微服务系列第七十一季-Introducing Spring Boot
-
Going Deeper with Convolutions中Inception概要
-
92. 进程间通信 - 信号接收 pause
-
图像的余弦加窗边界条件
-
thinkphp5.1博客后台实战视频
-
【数据分析-随到随学】Mysql数据库
-
python 爬取某网火锅信息,写入文本
-
浏览器端模块化的难题
-
26、MySQL存储过程
-
python 读取 txt文本写入mysql
-
【数据分析-随到随学】Spark理论及实战
-
(新)备战2021软考网络工程师顺利通关培训套餐