局部性

空间局部性:最近使用到的数据可能也是不远的未来要使用的数据，通常都是相邻的向

for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        cout<<a[i][j];
    } //这就是一个具有空间局部性的程序

时间局部性:在最近和未来要用到的信息，很可能是现在就在使用的信息(多次访问同一个信息)

for(int i=0;i<=n;i++)
{
    temp=1;
    for(int j=0;j<=m;j++){
        temp*=a[j];
        sum+=temp;
    } 
}//这是一个既具有空间局部性和时间局部性的程序

Cache和主存的映射方式★

直接映射(cache 的行和块是一个意思)

直接映射的冲突概率最高，空间利用率最低，但是实现简单

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

地址结构

例：有一主存Cache层次的存储器，主存容量为1MB，Cache容量为16KB，每块32B,
采用直接地址映射方式，Cache起始字块为0，若主存地址为35301H，
且CPU访问Cache命中，则在Cache的____号字块

全相联映射

标记用于指出该行取自主存哪一列，Cache块的冲突概率低，空间利用率高，命中率高；缺点速度慢，实现成本高

地址结构(全相联映射只有两个字段)

例：假设主存地址位数为32位，按字节编址，主存和Cache之间采用全相联映射方式，
主存块大小为1个字，每字32位，
采用回写法方式和随机替换策略，则能存放32K字数据的Cache的总容量至少有____位

组相联映射

组外采用直接映射，组间采用全相联映射的方式。选定适量的数量，可使组相联映射的成本接近直接映射，而性能接近全相联映射

Cache组号=主存块号 % Cache组数

地址结构

例:假设主存按字节编址，Cache共有64行，采用四路组相联映射方式，主存块大小为32字节，
所有编号都从0开始，则第2593号存储单元所在主存块的Cache组号是____

Cache总容量

地址结构(回写法加1个脏位)

例：假设主存地址位数为32位，按字节编址，主存和Cache之间采用全相联映射方式
，主存块大小为1个字，每字32位，采用回写法方式和随机替换策略，
则能存放32K字数据的Cache的总容量至少有____位

Cache中主存块的替换算法

RAND随机算法

随机确定替换的Cache行,实现简单，命中率较低

FIFO先进先出算法

实现简单

LRU近期最少使用算法：

命中率比FIFO高，是堆栈类算法

例:假设某计算机按字编码，Cache有4行，Cache和主存之间交换的块大小为1个字
，若Cache的内容初始为空，采用二路相联映射方法和LRU替换策略，
则访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是____

Cache的命中率

例:for(int k=0;k<1000;k++)
    a[k]=a[k]+32;
若数组a和变量k均为int型，数据Cache采用直接映射方式，数据区间大小为1KB,
块大小16B，该程序段执行前Cache为空，该程序段执行过程中访问数组a的Cache命中率为___