CPU,内存和cache之间的关系  和 cache的操作

https://blog.csdn.net/vanbreaker/article/details/7470830

cache和内存的关联方式(associativity)

https://blog.csdn.net/vanbreaker/article/details/7475093

cache的写策略和多处理器支持

https://blog.csdn.net/vanbreaker/article/details/7477853#comments

cache读写机制

https://blog.csdn.net/tc_xjyxhd/article/details/50603007

首先是Write-through和Write-back的区别：（这部分参考：http://witmax.cn/cache-writing-policies.html）

Write-through（直写模式、写透模式）：数据更新时，同时写入Cache和下一级存储。不存在dirty问题。

优点：简单可靠，不涉及cahce一致性问题；缺点：速度慢（因为同时写下一级存储（比如DDR））。

Write-back（回写模式）：数据更新时，只写Cache；当数据被替换出来时，才将该被修改的Cache数据写到下一级存储。涉及dirty这个概念。

优点：速度快；下一级存储没有副本，若出现意外情况数据将丢失。

顺便，dirty：是指cache某个位置数据被更新了，但是还没更新其对应的下一级存储位置（即cache不一致）；相反

   clean：cache数据与下一级存储位置数据一致

而allocate是针对cache miss时的处理方式，下面是我的理解：

No-allocate：不论读、写操作，cache miss时，直接写下一级存储（如DDR）

Read-allocate：读操作，cache miss时，在cache中分配一个空间，从下一级存储读取该数据到cache分配的这个空间，最后读取该值。注意：对于Write-back模式，如果分配的这个位置原数据是dirty的，需要将该数据先写回下一级存储。

Write-allocate：写操作，cache miss时，在cache中分配一个空间，将数据先写入该位置，根据Write-back还是Write-through决定是否再写入下一级存储。注意：对于Write-back模式，如果分配的这个位置原数据是dirty的，需要将该数据先写回下一级存储。



下面为参考网址给出的2个示例图，第一个是Write-through Read-allocate，第二个是Write-back Read and Write-allocate





简单总结一下该部分：Write-through和Write-back为写入cache的模式，区别是在写cache时是否还同时写下一级memory；allocate那堆只在cache miss时生效，负责分配cache空间给读和写中转用；另外，dirty只发生在Write-back模式，需要额外进行一步回写。

 

Cache基础知识归纳总结

https://blog.csdn.net/u010959074/article/details/52051606

1、缓存行

a) 缓存行：CPU不再是按字节访问内存，而是以64字节为单位的块(chunk)拿取，称为一个缓存行(cache line)。

b) 当程序运行的时间主要与内存访问的次数相关时，Cache的影响很重要。

c) 内存被分割成主存块(chunk)

d) 数据对齐。

2、L1和L2缓存

a) L1数据缓存，一个32KB的L1指令缓存，还有一个4MB大小L2数据缓存。L1缓存是处理器独享的，L2缓存是成对处理器共享的。

b) L1 速度 > L2 速度

c) 计算机的计算数据需要从磁盘调度到内存，然后再调度到L2 Cache，再到L1 Cache，最后进CPU寄存器进行计算。

3、指令级别的并发

a) 指令级别的并发性：部分指令具有并发性，U/V两条流水线。

4、缓存的关联性

 

a) 缓存关联性

b) 直接映射：每个内存块只能映射到一个特定的缓存槽

c) N路组关联(N-way set associative cache)：每个内存块能够被映射到N路特定缓存槽中的任意一路。

d) 完全关联(Fully associative cache)：每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。

5、缓存行的为共享

a) 缓存行的为共享：当一个处理器改变了属于它自己缓存中的一个值，其它处理器就再也无法使用它自己原来的值，因为其对应的内存位置将被刷新(invalidate)到所有缓存。而且由于缓存操作是以缓存行而不是字节为粒度，所有缓存中整个缓存行将被刷新！

b) volatile关键字

当变量被某个线程A修改值之后，其它线程比如B若读取此变量的话，立刻可以看到原来线程A修改后的值

注：普通变量与volatile变量的区别是volatile的特殊规则保证了新值能立即同步到主内存，以及每次使用前可以立即从内存刷新，即一个线程修改了某个变量的值，其它线程读取的话肯定能看到新的值；

6、硬件复杂性

a) 有些处理器上，L1缓存能够并发处理两路访问，如果访问是来自不同的存储体（？），而对同一存储体的访问只能串行处理。而且处理器聪明的优化策略也会使你感到惊讶，比如在伪共享的例子中，以前在一些没有微调的机器上运行表现并不良好，但我家里的机器能够对最简单的例子进行优化来减少缓存刷新。



a) 程序的运行存在时间和空间上的局部性

前者是指只要内存中的值被换入缓存，今后一段时间内会被多次引用，后者是指该内存附近的值也被换入缓存。如果在编程中特别注意运用局部性原理，就会获得性能上的回报。
比如C语言中应该尽量减少静态变量的引用，这是因为静态变量存储在全局数据段，在一个被反复调用的函数体内，引用该变量需要对缓存多次换入换出，而如果是分配在堆栈上的局部变量，函数每次调用CPU只要从缓存中就能找到它了，因为堆栈的重复利用率高。

再比如循环体内的代码要尽量精简，因为代码（就是指令？）是放在指令缓存里的，而指令缓存都是一级缓存，只有几K字节大小，如果对某段代码需要多次读取，而这段代码又跨越一个L1缓存大小，那么缓存优势将荡然无存。

b）关于CPU的流水线(pipeline)并发性简单说说，

Intel Pentium处理器有两条流水线U和V，每条流水线可各自独立地读写缓存，所以可以在一个时钟周期内同时执行两条指令。但这两条流水线不是对等的，U流水线可以处理所有指令集，V流水线只能处理简单指令。

CPU指令通常被分为四类，第一类是常用的简单指令，像mov, nop, push, pop, add, sub, and, or, xor, inc, dec, cmp, lea，可以在任意一条流水线执行，只要相互之间不存在依赖性，完全可以做到指令并发。

第二类指令需要同别的流水线配合，像一些进位和移位操作，这类指令如果在U流水线中，那么别的指令可以在V流水线并发运行，如果在V流水线中，那么U流水线是暂停的。

第三类指令是一些跳转指令，如cmp,call以及条件分支，它们同第二类相反，当工作在V流水线时才能通U流水线协作，否则只能独占CPU。

第四类指令是其它复杂的指令，一般不常用，因为它们都只能独占CPU。

如果是汇编级别编程，要达到指令级别并发，必须要注重指令之间的配对。尽量使用第一类指令，避免第四类，还要在顺序上减少上下文依赖。

a) 缓存行的开始点？数据对齐？

主存块（chunk），如果是8字节对齐则，起始地址为8的倍数。

http://www.cnblogs.com/bakari/archive/2012/08/27/2658956.html

Cache line alignment （cache对齐）

数据跨越两个cache line，就意味着两次load或者两次store。如果数据结构是cache line对齐的，  就有可能减少一次读写。数据结构的首地址cache line对齐，意味着可能有内存浪费（特别是  数组这样连续分配的数据结构），所以需要在空间和时间两方面权衡。

对于普通代码，内存边界对齐也是有好处的，可以降低高速缓存(Cache)和内存交换数据的次数。主要问题是在于Cache本身是分成很多Cache-Line,每条Cache-Line具有一定的长度，比如一般来说L1 Cache每条Cache Line长度在32个字节或64个字节；而L2的会更大，比如64个字节或128个字节。用户每次访问地址空间中一个变量，如果不在Cache当中，那么就需要从内存中先将数据调入Cache中.

比如现在有个变量 int x;占用4个字节,它的起始地址是0x1234567F;那么它占用的内存范围就在0x1234567F-0x12345682之间。如果现在Cache Line长度为32个字节，那么每次内存同Cache进行数据交换时，都必须取起始地址时32(0x20)倍数的内存位置开始的一段长度为32的内存同Cache Line进行交换.   比如0x1234567F落在范围0x12345660~0x1234567F上，但是0x12345680~0x12345682落在范围 0x12345680~0x1234569F上，也就是说，为了将4个字节的整数变量0x1234567F~0x12345682装入Cache,我们必 须调入两条Cache Line的数据。但是如果int x的起始地址按4的倍数对齐，比如是 0x1234567C~0x1234567F,那么必然会落在一条Cache Line上，所以每次访问变量x就最多只需要装入一条Cache Line的数据了。比如现在一般的malloc()函数，返回的内存地址会已经是8字节对齐的，这个就是为了能够让大部分程序有更好的性能。

b）多级缓存，级数设置？

1级速度要求最高的速度，2级次之，3级最次，3个级数就够了，95%调用缓存，再多成本高。



c）L1与L2的合作？

http://coolshell.cn/articles/3236.html

计算机的计算数据需要从磁盘调度到内存，然后再调度到L2 Cache，再到L1 Cache，最后进CPU寄存器进行计算。

d) CPU的流水线?

http://blog.jobbole.com/40844/

I486拥有五级流水线。分别是：取指(Fetch)，译码(D1, main decode)，转址(D2, translate)，执行(EX, execute)，写回(WB)。某个指令可以在流水线的任何一级。

 

但是这样的流水线有一个明显的缺陷。对于下面的指令代码，它们的功能是将两个变量的内

容进行交换。

1

2

3

XOR a, b

XOR b, a

XOR a, b

从8086直到386处理器都没有流水线。处理器一次只能执行一条指令。再这样的架构下，上面的代码执行并不会存在问题。

但是i486处理器是首个拥有流水线的x86处理器，它执行上面的代码会发生什么呢？当你一下去观察很多指令在流水线中运行，你会觉得混乱，所以你需要回头参考上面的图。

第一步是第一条指令进入取指阶段；然后在第二步第一条指令进入译码阶段，同时第二条指令进入取指阶段；第三步第一条指令进入转址阶段，第二条指令进入译码阶段，第三条指令进入取指阶段。但是在第四步会出现问题，第一条指令会进入执行阶段，而其他指令却不能继续向前移动。第二条xor指令需要第一条xor指令计算的结果a，但是直到第一条指令执行完成才会写回。所以流水线的其他指令就会在当前流水级等待直到第一条指令的执行和写回阶段完成。第二条指令会等待第一条指令完成才能进入流水线下一级，同样第三条指令也要等待第二条指令完成。

这个现象被称为流水线阻塞或者流水线气泡。



e) 本机中的缓存大小

L1d cache:             12*32K  独享

L1i cache:              12*32K独享

L2 cache:              12*256K独享

L3 cache:              30720K  一个物理cpu中所有内核共享

NUMA node0 CPU(s):     0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46

NUMA node1 CPU(s):     1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47

f )  L1、L2缓存行大小。

英特尔酷睿i7，酷睿， Atom和NetBurst， Core Solo和Pentium M处理器的L1，L2或L3缓存的高速缓存行是64个字节宽。



g）写命中：

http://blog.csdn.net/opensure/article/details/46669337

当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果不存在一个有效的缓存行，则处理器将这个操作数写回到缓存，而不是写回到内存，这个操作被称为写命中。

----------------------------------------------------------------------------

术语 英文单词 描述

共享变量 在多个线程之间能够被共享的变量被称为共享变量。共享变量包括所有的实例变量，静态变量和数组元素。他们都被存放在堆内存中，Volatile只作用于共享 变量。

内存屏障 Memory Barriers 是一组处理器指令，用于实现对内存操作的顺序限制。

备注： In the Java Memory Model a volatile field has a store barrier inserted after a write to it and a load barrier inserted before a read of it.

缓冲行 Cache line 缓存中可以分配的最小存储单位。处理器填写缓存线时会加载整个缓存线，需要使用多个主内存读周期。

原子操作 Atomic operations 不可中断的一个或一系列操作。

缓存行填充 cache line fill 当处理器识别到从内存中读取操作数是可缓存的，处理器读取整个缓存行到适当的缓存（L1，L2，L3的或所有）

缓存命中 cache hit 如果进行高速缓存行填充操作的内存位置仍然是下次处理器访问的地址时，处理器从缓存中读取操作数，而不是从内存。

写命中 write hit 当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果不存在一个有效的缓存行，则处理器将这个操 作数写回到缓存，而不是写回到内存，这个操作被称为写命中。

写缺失 write misses the cache 一个有效的缓存行被写入到不存在的内存区域。

 

Cache失效的原因 
强制性失效 (Compulsory miss): 当第一次访问一个块时，该块不在 Cache中, 需从下一级存储中调入 Cache, 这就是强制性失效。这种失效也称为冷启动失效，或首次访问失效。(增加块大小，预取)
容量失效 (Capacity miss): 如果程序执行时所需的块不能全部调入 Cache 中, 则当某些块被替换后, 若又重新被访问, 就会发生失效。这种失效称为容量失效。(增加容量) 抖动现象。
冲突失效 (Conflict miss): 在组相联或直接映像 Cache 中, 若太多的块映像到同一组(块)中，则会出现该组中某个块被别的块替换、然后又被重新访问的情况。这就是发生了冲突失效。这种失效也称为碰撞失效 (collision) 或干扰失效 (interference)。(提高相联度)
Cache性能的衡量标准 
缺失率：访问Cache失效次数/访问内存总次数 

Miss Rate = Misses / Memory accesses
每条指令缺失次数： 

Misses/Instruction = Miss Rate * Memory accesses / Instruction
平均内存访问时间： 

Average memory access time = Hit time + Miss rate × Miss penalty 
hit time：cache 命中所需要的访问时间 
Miss penalty：失效开销，cache未命中，从内存取出相应块并替换cache中某块的时间之和 
注：平均内存访问时间虽然叫缺失率性能更好，但是它仍然是一种间接的方法，不能够直接代替执行时间。推测处理及可能执行其他指令在cache失效期间，能够弥补一部分损失。多线程的使用也能够容忍失效，避免处理机闲置。
cache的基本优化方案 
采用更大的块将低缺失率。
采用更大的cache降低缺失率。
搞关联性降低缺失率。
多级缓存降低缺失损失。 

average memory access time: 

Hit timeL1 + Miss rateL1 × (Hit timeL2 + Miss rateL2 × Miss penaltyL2)
给读缺失更高的优先级来降低缺失损失。 

在带有写缓冲的环境下适合使用这种优化方式。写缓冲有它的危害，写缓冲会保存更新的值，当一个读操作发送缺失时，由于缓冲和内存出现不一致情况下，读-写会产生危害。一种解决方案是在发生读缺失的情况下检查缓冲内容，如果没有和内存内容冲突，并且内存系统时可用的，那么先发送读操作，然后在写，降低缺失损失。这种方案没有额外的功率消耗。
在索引cache期间避免地址转换降低命中时间。

Integer Cache
IntegerCache源码
Integer 使用Cache源码
瞎搞

IntegerCache源码

java.lang.Integer.IntegerCache {
        static final int low = -128;
        static final int high;
        static final Integer cache[];
        ...
}


Cache会缓存 [low, high-low] 范围内的整数
high默认127 范围 [127, Integer.MAX_VALUE - (-low) -1] , 可由 java.lang.Integer.IntegerCache.high 设置

Integer 使用Cache源码

public final class Integer extends Number implements Comparable<Integer> {
	...
	private final int value;
	...
	public static Integer valueOf(int i) {
		if (i >= IntegerCache.low && i <= IntegerCache.high)
			return IntegerCache.cache[i + (-IntegerCache.low)];
		return new Integer(i);
	}
	...
}


可以看出非new的Integer如果值在[low, high]内, 则复用同一个对象
注意java.lang.Integer#value为final

瞎搞

实现一段任何数字与Integer a = 2相乘为0的功能
/**
 * Integer常量池
 */
@Log4j2
public class ModifyInteger {

    static {
        try {
            modify();
        } catch (NoSuchFieldException | IllegalAccessException e) {
            e.printStackTrace();
        }
    }

    private static void modify() throws NoSuchFieldException, IllegalAccessException {
        // 1. 获取 IntegerCache 类
        Class<?> IntegerCache = Integer.class.getDeclaredClasses()[0];

        // 2. 获取 value 字段
        Field integerCacheValue = IntegerCache.getDeclaredField("cache");
        Field integerCacheLow = IntegerCache.getDeclaredField("low");

        // 3. 获取缓存数组
        integerCacheValue.setAccessible(true);
        Integer[] sourceCache = (Integer[]) integerCacheValue.get(Integer.class);

        // 4. 获取缓存最小值
        integerCacheLow.setAccessible(true);
        int low = integerCacheLow.getInt(Integer.class);

        // 5. 将缓存中的 2 修改为 0 (偷梁换柱)
        sourceCache[(low < 0 ? -low : low) + 2] = 0;
    }

    public static void check(Integer n) {
        Random random = new Random(System.currentTimeMillis());
        for (int idx = 0; idx < 10; idx++) {
        	// 14:48:53.775 [main] INFO org.example.codeTest.ModifyInteger - random * 2 = 0
            log.info("random * 2 = {}", random.nextInt(100) * n);
        }
    }
    
    public static void main(String[] args) {
        check(2);
    }
}

---- 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采用。

需要存储tag来区分，tag可以理解为主存块的index，方便查找。

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块。

下面这个图中间部分总共16块，0~15，是从主存中取了和Cache同样大小的，16块分为2组，0~7块是第1组，8~15块是第2组。

即将一个区分为了2组；块0映射到Cache中的组1，块1映射组1，以此类推，块7映射组7；但是可以是组中的任一块。

 

                                                                          图（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是前两种方法的折中方案，适度兼顾二者的优点，尽量避免二者的缺点，因而得到普遍采用。

更正一下：有人说这个Cache的组画的不对，是Cache分了2组，应该是组1和组2，组1里有0-7，组2是8-15，和中间的那个一样。

这么画是为了便于理解，把2路体现在了中间部分，而把可以放同一个块的放到了一组，看个人理解，但是映射的关系都是一样的。

至于块0和块1在一组不太合逻辑，更正为下面的图，有问题请指正。



实例分析：

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