最专业的网站设计平台,网站后台构建,广州注册公司地址,微信第三方网站怎么做文章目录1 局部性原理性能分析2 Cache工作原理#xff08;简易版#xff09;3 地址映射4 替换算法4.1 替换算法#xff08;十进制#xff09;举例4.2 Cache工作原理#xff08;加强版#xff09;4.2.1写策略-命中4.2.2 写策略-未命中4.3 替换算法#xff08;二进制…
文章目录1 局部性原理性能分析2 Cache工作原理简易版3 地址映射4 替换算法4.1 替换算法十进制举例4.2 Cache工作原理加强版4.2.1写策略-命中4.2.2 写策略-未命中4.3 替换算法二进制例题4.4 Cache工作原理高配版4.5 Cache例题小结5 虚拟存储器5.1 页式虚拟存储器5.2 段式虚拟存储器5.3 段页式虚拟存储器5.4 快表TLB5.5 页式虚拟存储器-例题1 局部性原理性能分析 空间局部性在最近的未来要用到的信息指令和数据很可能与现在正在使用的信息在存储空间上是邻近的时间局部性在最近的未来要用到的信息很可能是现在正在使用的信息 高速缓冲技术就是利用程序访问的局部性原理把程序中正在使用的部分存放在一个高速的容量较小的Cache中使CPU访存操作大多数针对Cache进行从而大大提高程序的执行速度
2 Cache工作原理简易版
Cache工作原理类似操作系统分页存储快表机制 CPU与Cache之间的数据交换以字为单位而Cache与主存之间的数据交换则以Cache块为单位 命中率H:CPU欲访问的信息已在Cache中的比率 设一个程序执行期间Cache的总命中次数为Nc访问主存的总次Nm 则HNc/NcNm缺失率M1-H设tc为命中时的Cache访问时间tm为未命中时的访问时间 Cache—主存系统的平均访问时间Ta为TaHtc1-Htm 假设Cache的速度是主存的5倍且Cache的命中率为95%则采用Cache后存储器性能提高多少设Cache和主存同时被访问若Cache命中则中断访问主存 若采用先访问Cache再访问主存的方式 不命中时访问cache耗时为t发现不命中后再访问主存耗时为5t总耗时为6t 故系统的平均访问时间为 T2 0.95×t0.05×6t 1.25t 故性能为原来的 5t / 1.25t 4倍即提高了3倍。 Cache三大核心问题 主存中的块放到Cache中哪个位置 1空位随意放全相联映射 2对号入座直接映射 3按号分组组内随意放组相联映射 对于1Cache满了如何处理对于23对应位置被占用如何处理 随机RAND算法、先进先出FIFO算法、近期最少使用LRU算法、最不经常使用LFU算法。 修改Cache中的内容后如何保持主存中相应内容的一致性 命中 全写法write-through 写回法write-back 不命中 写分配法write-allocate 非写分配法not-write-allocate 3 地址映射 Cache高三位确定行号低6位确定行内地址对应这行中的哪个单元 主存 低的6位表示每一行中的具体哪个位置对应这行的哪个单元 中的3位对应Cache的行号 高的19位就是主存比Cache多出来的地址位数 全相联映射 主存中内容可以往Cache中随意放但需要设置一个有效位如果是0表示空闲如果是1表示已经占满 根据有效位可以判断是否放了东西根据有效位后的标号对应主存的地址主存的地址高位作为一个标记存放在Cache相应的单元 Cache需要保存地址高位绿蓝都要存 直接映射 由于主存中多块可以放在Cache中同一位置为了区分具体来自主存中哪一位置把主存中的块存过去后立刻把主存地址高位存到对应的Cache行作为标记项 Cache需要保存地址高位一一对应的无需保存存绿 组相联映射按号分组组内任意放综合了上面两者优势 高的两位做组号0 1对应0组高两位00 2 3对应1组高两位01… 三种方式地址映射 有效位告诉机器此块数据要使用不能被其他数据覆盖Cache中只要放了数据就置有效位1 标记位告诉机器Cache中数据来自主存具体哪一位置 4 替换算法 随机算法RAND随机地确定替换的Cache块。它的实现比较简单但没有依据程序访问的局部性原理故可能命中率较低。先进先出算法FIFO选择最早调入的行进行替换。它比较容易实现但也没有依据程序访问的局部性原理可能会把一些需要经常使用的程序块如循环程序也作为最早进入Cache的块替换掉。近期最少使用算法LRU依据程序访问的局部性原理选择近期内长久未访问过的存储行作为替换的行平均命中率要比FIFO要高是堆栈类算法。 LRU算法对每行设置一个计数器Cache每命中一次命中行计数器清o而其他各行计数器均加1需要替换时比较各特定行的计数值将计数值最大的行换出。最不经常使用算法LFU将一段时间内被访问次数最少的存储行换出。每行也设置一个计数器新行建立后从0开始计数每访问一次被访问的行计数器加1需要替换时比较各特定行的计数值将计数值最小的行换出。 4.1 替换算法十进制举例 说明 直接映射 1主存块号/总块数 余数→Cache块号 2商→对应的标记位 访问4,6号由于Cache为空未命中标记置为0再访问12对应Cache中4号单元虽然有效位1但是标记位0与12除8商1不一样则发生替换12替换4并把标记位改1未命中访问4未命中4号单元标记位改0访问8… 每次访问一个单元用商更新一下被访问的标记位 FIFO 每新进来一个元素先往下放如果之前有元素就把之前有的元素往上抬则下面的元素始终是新放入的往上抬时自然而然替换了 访问第四个4时因为里面有4和12命中访问接下来的8把最上面12替换出去… LRU: 把即将要替换的放上面把最近使用过的放下面 访问12时12根4相比是刚刚使用的把12放下面接下来访问412是最近不太用的往上抬且4命中访问8时8往下放替换12… 4.2 Cache工作原理加强版 4.2.1写策略-命中 全写法写直通法write-through当CPU对Cache写命中时必须把数据同时写入Cache和主存一般使用写缓冲write buffer写回法write-back当CPU对Cache写命中时只修改Cache的内容而不立即写入主存只有当此块被换出时才写回主存 4.2.2 写策略-未命中 写分配法write-allocate把主存中的块调入Cache在Cache中修改。 搭配写回法使用。非写分配法not-write-allocate只写入主存不调入Cache。 搭配全写法使用。 4.3 替换算法二进制例题
设主存地址空间大小为1KB按字节编址Cache由8个块构成每个Cache块大小为16BCPU依次访问以下地址0001001110、1001110010、0001001111、0011000010、0101001000、1011110010、1111010000、0011001001十进制为78、626、79、194、328、754、976、201求
1假设地址映射方式为全相联映射在采用FIF0、LRU、LFU替换算法时分别求Cache命中次数。 首先分析地址结构 访问0001001110时有效位由0改为1标记位就是地址前六位000100 访问1001110010时有效位由0改为1标记位就是地址前六位100111 访问0001001111时标记位地址前六位000100已在Cache中命中或者用十进制角度64~79为一块访问78再访问79命中调入的一块同标记位的地址而不是一个地址 全相联模式下可能不会发生替换Cache是一点一点用完 2假设地址映射方式为直接映射求Cache命中次数。 首先分析地址结构 访问0001001110时由100可知放在Cache中4号块把标记置为000有效位1 访问1001110010时由111可知放在Cache中7号块把标记置为100有效位1 访问0001001111时由100可知放在Cache中4号块此时有效位1Cache标记位000与当前地址标记位000同命中 访问0011000010时由100可知放在Cache中4号块此时有效位1Cache标记位001与当前地址标记位000不同未命中替换把001替换000 直接映射对号入座→有冲突直接替换不涉及替换策略 首先分析地址结构 访问0001001110时由组号00可知放在Cache中0号块把标记置为0001有效位1在组内采用全相联映射放0号组的1号块和2号块都可以假设放在1号块访问1001110010时由11可知放在Cache中3号组把标记置为1001有效位1,访问0001001111时由00可知放在Cache中0号组此时有效位1Cache标记位0001与当前地址标记位0001同命中访问0011000010时由00可知放在Cache中0号组此时有效位1Cache标记位0011与当前地址标记位0001不同未命中把它放在0组中的2号块1号块已放了访问0101001000时由00可知放在Cache中0号组第0组已满但当前标记与Cache两个标记都不同需要替换 若采用FIFO替换最早调入的最早调入的块标记是0001故替换之。 若采用LRU替换最近未使用的刚用过0011故替换0001 LFU比较次数替换使用次数最少的 4假设其它配置同3采用写回法和直写法时Cache的总容量分别为多少 标记项有效位1位固定标记位由地址映射方式决定维护位由替换算法决定替换位由替换策略决定 4.4 Cache工作原理高配版 4.5 Cache例题小结 5 虚拟存储器 虚拟存储器是一个逻辑模型关注功能不关注实现功能用户给出一个地址叫做虚地址或逻辑地址虚拟存储器要给出该地址对应的数据。实现由辅助硬件将虚地址映射到主存当中的某个单元主存单元地址称为实地址或物理地址。 5.1 页式虚拟存储器
虚拟空间与主存空间都被划分成同样大小的页主存的页称为实页虚存的页称为虚页。 虚地址到物理地址映射过程 5.2 段式虚拟存储器 段式虚拟存储器中的段是按程序的逻辑结构划分的各个段的长度因程序而异。虚拟地址分为两部分段号和段内地址。段表每一行记录了与某个段对应的段号、装入位、段起点和段长等信息。 由于段的长度可变所以段表中要给出各段的起始地址与段的长度。 地址映射过程 5.3 段页式虚拟存储器 把程序按逻辑结构分段每段再划分为固定大小的页主存空间也划分为大小相等的页程序对主存的调入、调出仍以页为基本传送单位。每个程序对应一个段表每段对应一个页表。虚拟地址段号段内页号页内地址 5.4 快表TLB 页表、段表存放在主存中收到虚拟地址后要先访问主存查询页表、段表进行虚实地址转换。放在主存中的页表称为慢表Page。提高变换速度→用高速缓冲存储器存放常用的页表项→快表TLB 5.5 页式虚拟存储器-例题 地址变换第一步在于分析地址结构 标记对应虚页号页框对应实页号 有效位0快表未命中接下来查询页表若命中页表完成虚实转换若未命中主存中调出来 实页号与虚页号相互替换页内地址保持不变
