二 cahce 一致性-替换算法-多级cahce-并行主存系统

2023-12-28 10:18

本文主要是介绍二 cahce 一致性-替换算法-多级cahce-并行主存系统,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.cache的一致性问题:

 

1.cache的一致性问题指的是什么?

cache中的内容是主存的副本。

情况1:cache中的内容进行更新时,而没有改变主存中的相应内容时,cache和主存之间产生了不一致性。

 

情况2:当多个设备都允许访问主存时

例:I/O设备可通过DMA 方式直接读写主存时,如果Cache中的内容被修改,则I/O设备读出的对应主存单元的内容无效;若I/O设备修改了主存单元的内容,则对应Cache行中的内容无效。

 

情况3:当多个CPU都有各自私有的Cache并且共享主存时

例:某个CPU修改了自身Cache中的内容,则对应的主存单元和其他CPU中对应的Cache行的内容都要变为无效。

 

私有Cache中的变量u被更新后,各处理器读到的是不同的u值.

处理器私有Cache引入的问题

• 同一变量拷贝可能出现在多个处理器私有Cache中

•某处理器写操作可能对其它处理器是不可见的

 

 

2.如何保持Cache一致性呢?只有写操作能修改cache和主存ddr中的内容

当CPU写存储地址命中Cache时:

Write Through (写直达、写通过、直写)

Write Back (写回、一次性写、回写 )

 

Cache的写机制:Write Through (写直达、写通过、直写)

当一个写操作产生时,新值同时写到Cache和主存的块中

写直达会带来什么影响?

Memory is too slow(>100Cycles)

10%的存数指令会使CPI增加到:1.0+100×10%=11

 

在Cache和主存之间使用写缓冲(Write Buffer)

• 当一个数据等待被写入主存时,先将其存入写缓冲;

• 在把数据写入Cache和写缓冲后,处理器继续执行命令;

• 当写主存操作结束后,写缓冲里的数据释放

 

Cache的写机制:Write Back (写回、一次性写、回写)

当一个写操作产生时,新值仅被写到Cache中,而不被写入主存

写回方式会带来什么影响?

• 大大降低主存带宽需求,提高系统性能,控制可能很复杂

• 每个Cache行都设置一个修改位 (“ dirty bit-脏位”) ,如果对应Cache行中的主存块被修改,就同时置修改位为“1“ ,如果修改位为“0“ ,则说明对应主存块没有被修改过

• 只有当修改位为“1“的块从cache中替换出去时,才把它写回主存

 

写命中(Write Hit)要写的单元已经在Cache中

Write Through(写通过、写直达、直写)

Write Back(一次性写、写回、回写)

 

写不命中(Write Miss)要写的单元不在Cache中

Allocate-on-miss (写分配)

No-allocate-on-write (写不分配)

 

写不命中时如何处理?

Allocate-on-miss (写分配)

将该主存块装入Cache,然后更新Cache行中的相应单元;试图利用空间局部性,但增加了从主存读入一个块的开销

 

No-allocate-on-write (写不分配)

直接写主存,不把被写数据放入Cache;减少了从主存读一个块的开销,但没有利用空间局部性

 

 

 

2.cache的替换算法:

 

1.什么时候需要进行Cache替换?

Cache行数<<主存块数;

• 主存块和Cache行:多对1;

• 当一个新的主存块需要复制到Cache中时,如果Cache中的对应行已经全部被占满,怎么办?选择淘汰掉一个Cache行中的块

 

直接映射(Direct Mapped)Cache

• 映射唯一,无条件用新信息替换老信息

 

N路组相联(N-way Set Associative)Cache

• 每个主存数据有N个Cache行可选择,需考虑替换哪一行

 

全相联(Fully Associative)Cache

• 每个主存数据可存放到Cache任意行中,需考虑替换哪一行

 

2.常用替换算法:

先进先出FIFO、最近最少用LRU、最不经常使用LFU、随机替换

 

先进先出(First In First Out,FIFO)算法

基本思想:总是把最先进入的那一块替换掉

 

最近最少使用(Least Recently Used,LRU)算法

基本思想:总是把最近最少用的那一块淘汰掉,利用时间局部性

LRU算法的命中率随组中行数的增大而提高

 

LRU算法具体实现:通过给每个Cache行设定一个计数器,根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位

计数器变化规则

•每组4行时,计数器设2位。计数值越小,则说明越被常用

•命中时,被访问行的计数器置0,其他行计数器加1,其余不变

•未命中且该组未满时,新行计数器置为0,其余全加1

•未命中且该组已满时,计数值最大的那一行中的主存块被淘汰,新行计数器置为0,其余加1

 

随机(Random)替换算法

基本思想:随机地从候选的槽中选取一个淘汰,与使用情况无关

模拟试验表明,随机替换算法在性能上只稍逊于LRU算法,而且代价低!

 

 

3.多级cache

 

多级Cache系统成为主流:在Cache-Memory系统中使用更多的层次结构,以掩盖CPU访存延迟,提高处理器的执行效率.

 

多Cache系统设计的主要考虑因素:

(1) 单级/多级

• 片内(On-chip)Cache:将Cache和CPU作在一个芯片上

• 外部(Off-chip)Cache:不做在CPU内而是独立设置一个Cache

• 单级Cache:只用一个片内Cache

• 多级Cache:同时使用L1 、L2 Cache,有些系统还有L3 Cache

L1 Cache更靠近CPU,其速度比L2快,其容量比L2小

 

(2) 联合/分立

分立:数据和指令分开存放在各自的数据和指令Cache中

联合:数据和指令都放在一个Cache中

一般L1 Cache都是分立Cache,为什么?

L1 Cache的命中时间比命中率更重要!减少命中时间以获得较短的时钟周期

一般L2 Cache都是联合Cache,为什么?

L2 Cache的命中率比命中时间更重要!降低缺失率以减少访问主存缺失损失

两级Cache 系统的缺失损失(Miss Penalty)分析:

(1) 单级/多级

• 若L2 Cache包含所请求信息,则缺失损失为L2 Cache的访问时间

• 否则要访问主存,并同时取到L1 Cache和L2 Cache(缺失损失更大)

 

4.并行主存系统

 

解决内存访问速度慢的措施:

•提高主存芯片本身的速度

•在主存和CPU之间加入Cache

•采用并行结构技术

主存性能一直是计算机的重要性能指标之一,决定着计算机系统的整体性能

计算机系统期望主存:速度快、容量大、可靠性高、成本低

但从计算机实现技术来看,存在两个现实:

• 主存速度的提高总是远远落后于CPU速度的增长

• 主存容量的扩大总是远远满足不了软件的日益膨胀

结论:单从存储技术本身提高主存速度和容量,已经很难满足计算机系统的实际需求

从存储系统结构上想办法?

1、层次式存储系统

Cache —— 主存层次

主存 —— 辅存层次(虚拟存储技术,扩大用户编程的逻辑空间)

2、多体(多模块)并行交叉编址的主存储器

 

多体存储器

由若干个小存储体组成,共用MAR和MDR,同一套读/写控制电路、地址缓存、地址译码,不能提高数据访问速度

 

多体存储器

一个存储器中提供两套独立工作的读/写控制 电路 地址缓存 地址译 码 两个读写端口

根据地址线和数据线能同时进行两个数据的读/写.

 

通常作为双口RAM或指令预取部件

 

多模块存储器(多体交叉)

包含多个小存储体/模块,每个体有自己的MAR、MDR和读写电路

多个存储模块可独立并行工作

能够提高数据访问速度

 

编址方式

连续编址(高位交叉访问)

交叉编址(低位交叉访问)

 

连续编址方式 —— 高位交叉访问存储器

实现方法:用主存地址码的高位区分存储体号,低位表示模块内的地址

扩大了存储器容量连续字在一个模块中;各个体并行工作

 

存储地址连续的数据落在同一存储体内,容易发生访存冲突,并行存取的可能性很小

 

访存冲突,就是同时有两个或两个以上访存地址指向同一存储体,不能同时进行访存

 

用于非共享主存(即每个处理机仅享用统一编址主存的部分连续地址空间)和专用Cache的多处理机系统中

 

交叉编址方式 —— 低位交叉访问存储器

实现方法:用主存地址码的低位区分存储体号,高位表示模块内的地址

 

连续字分布在多个体中;各个体轮流编址、并行工作提高存储器访问速度

 

存储地址在同一存储体中不连续,以存储体个数(如:m)为模交叉编址

连续的程序或数据将交叉存放在m个存储体中,可实现以m为模的交叉并行存取,访存冲突的概率很小,为充分发挥并行性,多数计算机都采用低位交叉编址方式

 

 

什么条件下,多体低位交叉编址可增加存储带宽?

CPU访问主存的存储单元地址分布在不同存储体内

 

避免存储体访问冲突

软件通过编译程序做循环变换,可避免访问相同的存储体

硬件采用质数个存储体的低位交叉并行主存系统:一种无访问冲突的并行主存结构(实际带宽接近于最大带宽)

• 余数定律证明

• YH-1巨型机采用的是31个存储体构成的无冲突并行主存结构

 

指令执行时发生Cache失效/缺失/失靶,需到主存取数据或指令在主存和Cache之间传输的单位是块(Block)

问题:何种存储器使Block传输最快(miss penalty最小)?

存储器访问过程:

•发送地址到主存储器:1个总线时钟

•访问主存的时间:15个总线时钟

•从总线上传送一个字:1个总线时钟

 

并行计算机的访存模型

1、UMA模型(Uniform Memory Access):均匀存储访问模型

特点

• 物理存储器被所有处理器均匀共享(SM:Shared Memory)

• 访问任何存储字的时间相同

• 每台处理器可带私有高速缓冲

• 外围设备可以某种形式共享

 

2、NUMA模型(Non-Uniform Memory Access):非均匀存储访

特点

• 被共享的存储器在物理上分布于各个处理器

• 处理器访问不同存储器的时间不一样

• 每台处理器带私有高速缓冲

• 外围设备可以某种形式共享

 

多处理机的Cache一致性

 

多核处理器:在单芯片上的多个处理器,可能会共享主存中的一个公共的物理地址空间

Cache提供共享数据的迁移(migration)和复制(replication)

• 迁移:数据项可以移入本地cache并以透明的方式使用。迁移减少访问

远程共享数据项的延迟和对共享存储器带宽的需求

• 复制:当共享数据被同时读取时,Cache在本地对数据项做了备份。

复制减少了访问延迟和读取共享数据时的竞争现象

 

Cache共享数据带来新的问题 —— Cache一致性问题

• 两个不同处理器所保存的存储器视图是通过各自的cache得到(采用写直达cache)

• 两个处理器可能分别得到两个不同的值

 

软件方法:借助编译程序进行分析,使共享数据只存放在主存中,不允许放入高速缓存中

硬件方法:硬件协议维护,关键在于跟踪所有共享数据块的状态

• 侦听协议(snooping)

• 目录协议

 

侦听协议

基于总线连接的多处理机系统中,每个处理器的高速缓存设置1个侦听部件,侦听总线上的事务活动

若侦听到主存中有1个单元被其它处理器修改,而在自己Cache中有该单元的副本时,则将自己Cache中的副本置为无效,或把该副本更新,保持与主存中相应单元的内容一致

 

目录协议(Directory Protocol)

在主存中设置一个目录表,表中每一项记录共享数据的所有高速缓存行(数据块)的位置和状态,包括几个指示器(指示数据块的副本放在哪些处理器的高速缓存中)和指示位(指示是否已有高速缓存更新过此数据块的内容)

当一个处理器写入自己的高速缓存时,基于目录表,只需有选择地通知存有该数据块的处理器中的高速缓存,使相应副本被废弃或被更新

这篇关于二 cahce 一致性-替换算法-多级cahce-并行主存系统的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

Linux系统之dns域名解析全过程

《Linux系统之dns域名解析全过程》:本文主要介绍Linux系统之dns域名解析全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、dns域名解析介绍1、DNS核心概念1.1 区域 zone1.2 记录 record二、DNS服务的配置1、正向解析的配置

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Linux系统之authconfig命令的使用解读

《Linux系统之authconfig命令的使用解读》authconfig是一个用于配置Linux系统身份验证和账户管理设置的命令行工具,主要用于RedHat系列的Linux发行版,它提供了一系列选项... 目录linux authconfig命令的使用基本语法常用选项示例总结Linux authconfi

Nginx配置系统服务&设置环境变量方式

《Nginx配置系统服务&设置环境变量方式》本文介绍了如何将Nginx配置为系统服务并设置环境变量,以便更方便地对Nginx进行操作,通过配置系统服务,可以使用系统命令来启动、停止或重新加载Nginx... 目录1.Nginx操作问题2.配置系统服android务3.设置环境变量总结1.Nginx操作问题

Java之并行流(Parallel Stream)使用详解

《Java之并行流(ParallelStream)使用详解》Java并行流(ParallelStream)通过多线程并行处理集合数据,利用Fork/Join框架加速计算,适用于大规模数据集和计算密集... 目录Java并行流(Parallel Stream)1. 核心概念与原理2. 创建并行流的方式3. 适

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网