cache 订阅
Caché,是 一种后关系型数据库。能并发访问同一数据的数据库技术。 展开全文
Caché,是 一种后关系型数据库。能并发访问同一数据的数据库技术。
信息
定    义
一种后关系型数据库
作    用
对事务数据的实时查询
针对对象
为专业开发者而设计
中文名
Caché
Caché简介
什么是 Caché?。它独一无二地提供了三种整合的、能并发访问同一数据的数据库技术:成熟的对象访问方式,高性能的 SQL 访问方式以及丰富的多维访问。在对象数据、关系型数据以及多维数据视图之间不需要映射,这样就大大节省了开发和运行时间。
收起全文
精华内容
参与话题
问答
  • cache

    千次阅读 2018-11-01 17:39:40
    CPU,内存和cache之间的关系 和 cache的操作 https://blog.csdn.net/vanbreaker/article/details/7470830 cache和内存的关联方式(associativity) https://blog.csdn.net/vanbreaker/article/details/7475093 ...

    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

    A Write-Through cache with No-Write Allocation

    简单总结一下该部分: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结构与工作原理

    万次阅读 多人点赞 2017-11-23 14:44:55
    在经历N次的阅读之后,终于明白了cache结构和工作原理。  首先,要想理解cache,先理解内存。内存的简单表示如下图,内存里面的内容的查找是根据地址来进行的,也就是说内存包含两点①地址②内存的内容(存的...

    在经历N次的阅读之后,终于明白了cache的结构和工作原理。

        首先,要想理解cache,先理解内存。内存的简单表示如下图,内存里面的内容的查找是根据地址来进行的,也就是说内存包含两点①地址②内存的内容(存的数据),根据地址来找数据。

                                                                                     图1   内存的结构

        上图的0000~0008是地址,A~I是存的数据,cpu根据地址去寻找数据。图中的一个字母代表一个字节的数据。

        我们都清楚,cache中的数据就是物理内存中的数据的子集,那么对于物理内存的一个数据,根据cache中可以放置这个数据位置的多少,可以分为三种:①如果cache中只有一个位置可以容纳这个数据,则为直接映射的cache;②如果cache中有多个地方可以放置这个数据,它就是组相联的cache;③如果cache中的任何地方都可以放置这个数据,那么它就是全相连的cache;如下图2所示:

                                                                            图2  cache的三种组成方式

        更详细的讲,cache的结构其实和内存的结构类似,也包含地址和内容,只是cache的内容除了存的数据(data)之外,还包含存的数据的物理内存的地址信息(tag),因为CPU发出的寻址信息都是针对物理内存发出的,所以cache中除了要保存数据信息之外,还要保存数据对应的地址,这样才能在cache中根据物理内存的地址信息查找物理内存中对应的数据。(当然为了加快寻找速度,cache中一般还包含一个有效位(valid),用来标记这个cache line是否保存着有效的数据)。一个tag和它对应的数据组成的一行称为一个cache line。如下图所示,下表中的一行就是一个cache line。

                                                                      图3   cache的基本结构

    具体的Data、Valid、Tag各有多大,在介绍了内存的地址划分之后再在下文中讲。

    知道了cache的结构之后,如何在cache中去寻找对应的数据呢?简单起见,我们先选择 直接映射的cache组成方式进行下文的分析

    首先对于一段物理内存(block),该物理内存上的每个字节的地址划分为以下几段:[3]

                                                                               图4   处理器物理内存地址的划分

    这样的话物理内存中的数据到cache的映射关系如下图5所示:

                                                                                    图5   cache的查找过程

        上图的映射原则就是:根据物理地址的中间三位(index字段)来定位当前数据应该在cache的哪一行,把物理地址的tag字段和该地址对应的内容放入对应的cache line的tag字段和data字段,并把相应的valid位置1。那么在之后进行cache寻找的时候就可以根据cache line的tag字段来辨认当前line中的数据是数据哪个block的。

        上图5中的地址00 000 00~11 111 11按照图4的原则进行地址划分:地址的最高两位为Tag字段;中间三位为index字段;最低两位为Block Offset 字段;由于Block Offset是两位,也就是一个block的大小是2²=4个字节的数据,也就是一个cache line的data字段包含4个字节的数据;index为3位,说明cache共包含2³=8个组(对于直接映射的cache,也称为8个行);很明显,cache的一个行中只能存储1 块(Block )=4字节的数据,但是按照图5的映射方式,会有2^(tag位数) = 2^2 = 4块的数映射到同一个行,此时通过Tag字段的比较来辨别是不是我们要取数据的地址,如果不是的话,也就是发生了cache的缺失。如图5的Block 0和Block 1的index字段都是000,按照上面的理论它们都应该映射到第 000=0行(这儿的行也就是组,因为图5是直接映射的cache),但是现在第0行的内容是K、L、M、N,也就是Block 1的内容,为什么呢?仔细看该cache line的tag=01,映射到第0行的块只有Block 1的tag字段=01,所以可以得知此时该cache line中存储的数据是Block 1的数据,此时如果CPU发出的访存请求是访问Block 0 的话,也就是发生了缺失。此时进一步定量分析的话,共有4个数据块竞争使用cache 第0行的位置,也就是说cache的命中率为25%。

        上面的过程总结起来就是:物理内存的索引字段(Index)选择cache 的行,通过对比物理内存和cache line的Tag来判断是否命中。块偏移字段(Block Offset)可以从cache line的数据块中选择期望数据。注意在这个过程中cache的index是不占空间的,它就类似于物理内存的地址,对于物理内存来说是通过地址去寻找数据,对于cache来说,是通过index来找到对应的cache line,或者更通俗的讲就是:cache line的地址对应的就是物理内存的index字段。

        此时该cache的容量计算如下:每一个cache line的数据字段占4个字节,共2³=8行,所以数据占据4×8=32个字节,一个cache line中tag字段和valid位占2+1=3bit,整个cache的tag+valid=3bit×8行=24bit=3Byte,通常情况下我们都是一cache中数据部分占的空间表示cache的容量,也就是32字节,但是实际上,它还额外多占用了3字节的存储空间[4]。

     

        图5的分析是针对直接映射的cache进行的,对于组相联或者全相连的cache的分析与之类似。如果是组相连的cache,每个组(set)里面包含多个行(line),通过内存地址的index字段来寻址组,确定组之后再根据tag来确定是否命中;对于全相连的cache,就不需要index字段了,因为全相连的cache相当于只有一个组的组相连cache。这是只需要根据要寻址的地址的tag来逐一与cache中的tag字段比较,如果有与之匹配的cache line,也就是cache hit了,如果遍历整个cache,也没有找到匹配的cache line,那就是cache miss了。

     

    注:为了叙述的简单性,省略了内存地址通过TLB的的虚实转换部分,由[1]可知,内存地址的Tag部分其实是需要先经过TLB的转化才能够去和cache line的tag部分去进行匹配的。

     

    参考:

    [1]Cache的工作原理

    [2]每个程序员都应该了解的 CPU 高速缓存

    [3]计算机体系结构:量化研究方法 Hennessy   P411

    [4]超标量处理器设计 姚永斌  P21

     

    展开全文
  • Cache基本结构

    千次阅读 2011-06-14 15:43:00
    Cache的基本结构 Cache通常由相联存储器实现。相联存储器的每一个存储块都具有额外的存储信息,称为标签(Tag)。当访问相联存储器时,将地址和每一个标签同时进行比较,从而对标签相同的存储块进行访问。Cache的3种...

    Cache的基本结构

    Cache通常由相联存储器实现。相联存储器的每一个存储块都具有额外的存储信息,称为标签(Tag)。当访问相联存储器时,将地址和每一个标签同时进行比较,从而对标签相同的存储块进行访问。Cache的3种基本结构如下:

    全相联Cache

    在全相联Cache中,存储的块与块之间,以及存储顺序或保存的存储器地址之间没有直接的关系。程序可以访问很多的子程序、堆栈和段,而它们是位于主存储器的不同部位上。

    因此,Cache保存着很多互不相关的数据块,Cache必须对每个块和块自身的地址加以存储。当请求数据时,Cache控制器要把请求地址同所有地址加以比较,进行确认。

    这种Cache结构的主要优点是,它能够在给定的时间内去存储主存器中的不同的块,命中率高;缺点是每一次请求数据同Cache中的地址进行比较需要相当的时间,速度较慢。


    直接映像Cache

    直接映像Cache不同于全相联Cache,地址仅需比较一次。

    在直接映像Cache中,由于每个主存储器的块在Cache中仅存在一个位置,因而把地址的比较次数减少为一次。其做法是,为Cache中的每个块位置分配一个索引字段,用Tag字段区分存放在Cache位置上的不同的块。

    单路直接映像把主存储器分成若干页,主存储器的每一页与Cache存储器的大小相同,匹配的主存储器的偏移量可以直接映像为Cache偏移量。Cache的Tag存储器(偏移量)保存着主存储器的页地址(页号)。

    以上可以看出,直接映像Cache优于全相联Cache,能进行快速查找,其缺点是当主存储器的组之间做频繁调用时,Cache控制器必须做多次转换。

    组相联Cache

    组相联Cache是介于全相联Cache和直接映像Cache之间的一种结构。这种类型的Cache使用了几组直接映像的块,对于某一个给定的索引号,可以允许有几个块位置,因而可以增加命中率和系统效率。



    Cache与DRAM存取的一致性

    在CPU与主存之间增加了Cache之后,便存在数据在CPU和Cache及主存之间如何存取的问题。读写各有2种方式。

    贯穿读出式(Look Through)

    该方式将Cache隔在CPU与主存之间,CPU对主存的所有数据请求都首先送到Cache,由Cache自行在自身查找。如果命中,则切断CPU对主存的请求,并将数据送出;不命中,则将数据请求传给主存。

    该方法的优点是降低了CPU对主存的请求次数,缺点是延迟了CPU对主存的访问时间。

    旁路读出式(Look Aside)

    在这种方式中,CPU发出数据请求时,并不是单通道地穿过Cache,而是向Cache和主存同时发出请求。由于Cache速度更快,如果命中,则Cache在将数据回送给CPU的同时,还来得及中断CPU对主存的请求;不命中,则Cache不做任何动作,由CPU直接访问主存。

    它的优点是没有时间延迟,缺点是每次CPU对主存的访问都存在,这样,就占用了一部分总线时间。

    写穿式(Write Through)

    任一从CPU发出的写信号送到Cache的同时,也写入主存,以保证主存的数据能同步地更新。

    它的优点是操作简单,但由于主存的慢速,降低了系统的写速度并占用了总线的时间。

    回写式(Copy Back)

    为了克服贯穿式中每次数据写入时都要访问主存,从而导致系统写速度降低并占用总线时间的弊病,尽量减少对主存的访问次数,又有了回写式。

    它是这样工作的:数据一般只写到Cache,这样有可能出现Cache中的数据得到更新而主存中的数据不变(数据陈旧)的情况。但此时可在Cache 中设一标志地址及数据陈旧的信息,只有当Cache中的数据被再次更改时,才将原更新的数据写入主存相应的单元中,然后再接受再次更新的数据。这样保证了Cache和主存中的数据不致产生冲突。

    s

    展开全文
  • Cache的组成结构

    千次阅读 2014-03-09 14:50:26
    在一个Cache中包含多行多列,存在若干类组成方式。在处理器体系结构的历史...在介绍Set-Associative组成结构之前,我们简单回顾另外一种Cache组成结构,Sector Buffer方式[23]。假定在一个微架构中,Cache大小为16KB,
    在一个Cache中包含多行多列,存在若干类组成方式。在处理器体系结构的历史上,曾出现过更多的的组成结构,最后剩余下来的是我们耳熟能详的Set-Associative组成结构。这种结构在现代处理器微架构中得到了大规模普及。
    

    在介绍Set-Associative组成结构之前,我们简单回顾另外一种Cache组成结构,Sector Buffer方式[23]。假定在一个微架构中,Cache大小为16KB,使用Sector Buffer方式时,这个16KB被分解为16个1KB大小的Sector,CPU可以同时查找这16个Sector。

    当CPU访问的数据不在这16个Sector中命中时,将首先进行Sector淘汰操作,在获得一个新的Sector后,将即将需要访问的64B数据填入这个Sector。如果CPU访问的数据命中了某个Sector,但是数据并不包含在Sector时,将相应的数据继续读到这个Sector中。采用这种方法时,Cache的划分粒度较为粗略,对程序的局部性的要求过高。Cache的整体命中率不如采用Set-Associative的组成方式[23]。

    在狭义Cache的设计中,这种方法已经不在使用。但是这种方法依然没有完全失效。处理器体系结构是尺有所短,寸有所长。在一些广义Cache的设计中,Sector Buffer方式依然是一种行之有效的Buffer管理策略。有很多程序员仍在不自觉地使用这种方式。这种不自觉的行为有时是危险的,太多不自觉的存在有时会使人忘记了最基础的知识。

    我曾经逐行阅读过一些工作了很多年的工程师的Verilog代码,在这些代码中使用了一些算法,这些算法我总感觉似曾相识,却已物是人非。他们采用的算法实际上有许多经典的实现方式,已经没有太多争论,甚至被列入了教科书中。有些工程师却忘记了这些如教科书般的经典,可能甚至没有仔细阅读过这些书籍,在原本较为完美的实现中填入蛇足。更为糟糕的是,一些应该存在的部件被他们轻易的忽略了。

    有时间温故这些经典书籍是一件很幸运的事情。我手边常备着A Quantitative Approach和The Art of Computer Programming这些书籍,茶余饭后翻着,总能在这些书籍中得到一些新的体会。时间总是有的。很多人一直在抱怨着工作的忙碌,没有空余,虽然他们从未试图去挤时间的海绵,总是反复做着相同的事情。多次反复最有可能的结果是熟能生巧而为匠,却很难在这样近乎机械的重复中出现灵光一现的机枢。这些机枢可能发生在你多读了几行经文,或受其他领域的间接影响,也许并不是能够出现在日常工作的简单重复之上。

    写作时回忆SectorBuffer机制时写下了这些文字。在现代处理器中,Cache Block的组成方式大多都采用了Set-Associative方式。与Set-Associative方式相关的Cache Block组成方式还有Direct Mapped和Fully-Associative两种机制。Direct Mapped和Fully-Associative也可以被认为是Set-Associative方式的两种特例。

    在上世纪90年代,Direct Mapped机制大行其道,在Alpha 21064,21064A和21164处理器中,L1 I Cache和D Cache都使用了Direct Mapped方式和Write Through策略。直到Alpha 21264,在L1 Cache层面才开始使用2-Way Associative方式和Write Back策略[16][17][18]。即便如此Alpha 21264在L1 I Cache仍然做出了一些独特设计,采用了2-Way Set-Predict结构,在某种程度上看使用这种方式,L1 I Cache相当于工作在Direct Mapped方式中。

    在90年代,世界上没有任何一个微架构能够与Alpha相提并论,没有任何一个公司有DEC在处理器微架构中的地位,来自DEC的结论几乎即为真理,而且这些结论都有非常深入的理论作为基础。与Fully-Associative和Set-Associative相比,Direct Mapped方式所需硬件资源非常有限,每一次存储器访问都固定到了一个指定的Cache Block。这种简单明了带来了一系列优点,最大的优点是在200~300MHz CPU主频的情况下,Load-Use Latency可以是1个Cycle。天下武功无坚不破,唯快不破。

    至今很少有微架构在L1层面继续使用Direct Mapped方式,但是这种实现方式并没有如大家想象中糟糕。围绕着Direct Mapped方式,学术界做出了许多努力,其中带来最大影响的是Normal P. Jouppi书写的“Improving Direct-Mapped Cache Performance by Additionof a Small Fully-Associative Cache and PrefetchBuffers”,其中提到的Victim Cache,Stream Buffer[20]至今依然在活跃。

    使DirectMapped方式逐步退出历史舞台的部分原因是CPU Core主频的增加使得Direct Mapped方式所带来的Load-Use Latency在相对缩小,更为重要的是呈平方级别增加的主存储器容量使得Cache容量相对在缩小。

    从Cache MissRate的层面考虑,一个采用Direct Mapped方式容量为N的Cache其Miss Rate与采用2-Way Set-Associative方式容量为N/2的Cache几乎相同。这个Observation被John和David称为2:1 Cache Rule of Thumb[7]。这意味着采用Direct Mapped方式的Cache,所需要的Cache容量相对较大。

    近些年L1Cache与主存储器容量间的比值不但没有缩小而是越来越大。L1 Cache的大小已经很少发生质的变化了,从Pentium的16/32KB L1 Cache到Sandy Bridge的64KB L1 Cache,Intel用了足足二十多年的时间。在这二十多年中,主存储器容量何止扩大了两千倍。相同的故事也发生在L2与L3 Cache中。这使得在采用Direct Mapped方式时,Cache的Miss Ratio逐步提高,也使得N-Way Set-Associative方式闪亮登场。

    采用Set-Associative方式时,Cache被分解为S个Sets,其中每一个Set中有N个Ways。根据N的不同,Cache可以分为Fully-Associative, N-WaysSet-Associative或者是Direct Mapped。在Cache的总容量不变的情况下,即S×N的值为一个常数M时,N越大,则S越小,反之亦然。8-Way Set-Associative Cache的组成结构如图2‑4所示。

    2.2 <wbr>Cache的组成结构

    如图2‑4所示,在Cache Block中Real Address Tag字段与数据字段分离,因为这两类字段分别存在不同类型的存储器中。在同一个Set中,Real Address Tag阵列多使用CAM(Content Addressable Memory)存放,以利于并行查找PS(Parallel Search)方式的实现,在设计中也可以根据需要使用串行查找方式SS(Sequential Search)。与PS方式相比,SS方式使用的物理资源较少,但是当使用的Ways数较大时,采用这个方式的查找速度较慢。在现代微架构中,数据字段组成的阵列一般使用多端口,多Bank的SRAM。下文主要讨论PS的实现方式。

    对于一个Cache,其总大小由存放Tag阵列和SRAM阵列组成,在参数N较低时也可以采用RAM Tag,本篇仅讨论CAM Tag,在功耗日益敏感的今天,Highly Associative Cache倾向于使用CAM Tag。在许多微架构中,如Nehalem微架构的L1 Cache为32KB[12],这是的大小是指SRAM阵列,没有包括Tag阵列。Tag阵列占用的Die Size不容忽略。

    在说明Set-Associative方式和Tag阵列之前,我们进一步讨论NS这个参数。不同的处理器采用了不同的Cache映射方式,如Fully-Associative, N-WaysSet-Associative或者是Direct Mapped。如果使用NS参数进行描述,这三类方式本质上都是N-Ways Set-Associative方式,只是选用了不同的NS参数而已。

    在使用N-WaysSet-Associative方式时,Cache首先被分解为多个Set。当S参数等于1时,即所有Cache Block使用一个Set进行管理时,这种方式即为Fully-Associative;N参数为1时的管理方式为Direct Mapped;当NS参数不为1时,使用的方式为N-Ways Set-Associative方式。在图2‑4中,N为8,这种方式被称为8-Way Set-Associative。

    诸多研究结果表明,随着N的不断增大,Cache的Miss Ratio在逐步降低[7][23]。这并不意味着设计者可以使用更大的参数N。在很多情况下,使用更大的参数N并不会显著降低Miss Ratio,就单级Cache而言,8-Way Set-Associative与Fully-Associative方式从Miss Ratio层面上看效果相当[7]。许多微架构使用的16-Way或者更高的32-Way Set-Associative,并不是单纯为了降低Miss Ratio。

    随着Way数的增加,即便Cache所使用的Data阵列保持不变,Cache使用的总资源以及Tag比较所需要的时间也在逐步增加。在一个实际的微架构中,貌似巨大无比的CPU Die放不下几片Cache,在实际设计中一个Die所提供的容量已经被利用的无以复加,很多貌似优秀的设计被不得已割舍。这也使得在诸多条件制约之下,参数N并不是越大越好。这个参数的选择是资源权衡的结果。

    当S参数为1时,N等于M,此时Tag阵列的总Entry数目依然为M,但是对于CAM这样的存储器,单独的一个M大小的数据单元所耗费的Die资源,略微超过S个N大小的数据单元。随着N的提高,Tag阵列所消耗的比较时间将逐步增加,所需要的功耗也在逐级增大。在进一步讨论这些细节知识前,我们需要了解CAM的基本组成结构,如图2‑5所示。

    2.2 <wbr>Cache的组成结构

    图2‑5中所示的CAM中有3个Word,每一个Word由4个Bits组成,其中每一个Bit对应一个CAM Cell。其中每一个Word对应一条横向的ML(Match Line),由ML0~2组成。在一个CAM内,所有Word的所有Bits将同时进行查找。在一列中,Bits分别与两个SL(Serach Line)对应,包括SL0~3和~SL0~3#。其中一个Bit对应一个CAM Cell。

    使用CAM进行查找时,需要首先将Search Word放入Search Data Register/Drivers中,之后这个Search Word分解为若干个Bits,通过SL或者~SL发送到所有CAM Cell中。其中每一个CAM Cell将Hit/Miss信息传递给各自的ML。所有ML信息将最后统一在一起,得出最后的Hit/Miss结论,同时也将给出在CAM的哪个地址命中的信息[1]。由此可以发现,由于CAM使用并行查找方式,其查找效率明显操作SRAM。

    这也使得CAM得到了广泛应用。但是我们依然无法从这些描述中,获得随着CAM包含的Word数目增加,比较时间将逐步增加,所需要的功耗也在逐级增大这个结论,也因此无法解释Cache设计中为什么不能使用过多的Way。为此我们需要进一步去微观地了解CAM Cell的结构和Hit/Miss识别机制。在门级电路的实现中,一个CAM Cell的设计可以使用两种方式,一个是基于NOR,另一个是基于NAND,如图2‑6所示。

    2.2 <wbr>Cache的组成结构

    在上图中可以发现NOR-Type CAMCell和NAND-Type CACM Cell分别由4和3个MOSGET加上一个SRAM Cell组成,一个SRAM Cell通常由6个Transistor组成[2]。由此可以发现一个基本的NOR-Type CAM Cell由10个,NAND-Type CACM Cell由9个Transistor组成。

    这不是NOR/NAND CAMCell的细节,NOR CAM Cell有9个Transistor的实现方式,NAND CAM Cell有10个Transistor的实现方式,这些由实现过程中的取舍决定。NOR和NAND CAM的主要区别是Word的查找策略,NOR CAM Cell采用并行查找方式,NAND CAM Cell使用级联方式进行查找,如图2‑7所示。

    2.2 <wbr>Cache的组成结构

    为节约篇幅,我省略如何对这些晶体管进行Precharge,Discharge,如何Evaluate,并最终确定一个Word是Hit还是Miss,读者可以进一步阅读[25]获得详细信息。较为重要的内容是从图2‑7中可以发现,当使用NAND CAM时,Word的匹配使用级联方式,MLn需要得到MLn-1的信息后才能继续进行,采用NOR CAM是全并行查找。仅从这些描述上似乎可以发现,NOR CAM在没有明显提高Transistor数目的前提之下,从本质上提高了匹配效率,貌似NAND CAM并没有太多优点。

    事实并非如此。在使用NORCAM时,随着Word包含Bit数目的增加,ML上的负载数也随之增加。这些过多输入的与操作将带来延时和功耗。在图2‑7所示的N-Input与操作采用了One-Stage实现方式,需要使用Sense Amplifier降低延时,但是这个Sense Amplifier无论在工作或者处于Idle状态时的功耗都较大。当然在n较大时,Multi-Stage n-input AND Gate所产生的延时更不能接受。

    即便使用了SenseAmplifier,也并不能解决全部问题。当时钟频率较高时,这种并联方式所产生的延时很难满足系统需求。使用NAND CAM方式是一推一关系,没有这种负载要求。在Cache的Tag中除了需要保存Real Address之外还有许多状态信息,这也加大了AND Gate的负担。

    CAM除了横向判断一个Word是Hit还是Miss之外,还有另外一个重要问题,就是Search Data Register/Driver的驱动能力问题,这个问题进一步引申就是N-Way Set-Associative中N究竟多大才合理的问题。一个门能够驱动多少个负载和许多因素相关,频率,电流强度和连接介质等。对于一个运行在3.3GHz的L1 Cache而言,一个Cycle仅有300ps,在这么短的延时内,门级电路做不了太多事情。

    我们可能有很多方法提高驱动能力,Buffering the fan-out,使用金属线介质或者更多级的驱动器,缩短走线距离等等。在所有追求极限的设计中,这些方法不是带来了过高的延时,就是提高了功耗。一个简单的方式是采用流水方式,使用更多的节拍,但是你可知我为了节省这一拍延时经历了多少努力。这一切使得在N-Ways Set-Associative方式中N的选择是一个痛苦的折中,也使得在现代微架构的L1 Cache中N不会太大。

    尽管有这些困难,绝大多数现代微架构还是选择了N-Ways Set-Associative方式,只是对参数N进行了折中。在这种方式下,当CPU使用地址r(i)进行存储器访问时,首先使用函数f寻找合适的Set,即s(i) = f(r(i)),然后在将访问的地址的高字段与选中Set的Real Address Tag阵列进行联合比较,如果在Tag阵列中没有命中,表示Cache Miss;如果命中则进一步检查Cache Block状态信息,并将数据最终读出或者写入。

    现代微架构多使用2-Ways,4-Ways,8-Ways或者16-Ways Set-Associative方式组成Cache的基本结构。Ways的数目多为2的幂,采用这种组成方式便于硬件实现。然而依然有例外存在,在有些处理器中可能出现10-Ways或者其他非2幂的Ways。

    出现这种现象的主要原因是这个Way并非对等。在一个处理器系统中,微架构和外部设备,如显卡和各类PCIe设备,都可以进行存储器访问。这些存储器访问并不类同。在多数情况下,微架构经由LSQ,FLC,MLCs,之后通过LLC,最终与主存储器进行数据交换。外部设备进行DMA访问时,直接面对的是LLC和主存储器,并对L1 Cache和MLC产生简介影响。微架构与外部设备访问主存储器存在的差异,决定了在有些处理器中,LLC Way的构成并不一定是2的幂,而是由若干2的幂之和组成,如10-Ways Set-Associative可能是由一个8-Ways和一个2-Ways组成。

    无论是软件还是硬件设计师都欣赏同构的规整,和由此带来的便利与精彩。但是在更多情况下,事物存在的差异性,使得严格的同构并不能发挥最大的功效,更多时候需要使用异构使同构最终成为可能。

    在Cache中,不对等Way的产生除了因为访问路线并不一致之外,还有一个原因是为了降低Cache Miss Rate,有些微架构进行Way选择使用了不同的算法。如Skewed-Associative Cache[26]可以使用不用的Hash算法,f0和f1分别映射一个Set内的两个Way,采用这种方法在没有增加Set的Ways数目的情况下,有效降低了Cache Miss Rate。[26]的结论是在Cache总大小相同时,2-Way Skewed- Associative Cache的Hit Ratio与4-Way Associative Cache相当,其Hit Time与Direct Mapped方式接近。但是在Cache容量较大时,f0和f1的映射成本也随之加大,从而在一定程度上增加了Cache的访问时间。

    在历史上还出现过其他的Cache组成结构,如Hash-rehash Cache,Column-Associative Cache等,本篇对此不再一一介绍。值得留意的是Parallel Multicolumn Cache[27],这种Cache的实现要点是综合了Direct Mapped Cache和N-Ways Set-Associative方式,在访问Cache时首先使用Direct Mapped策略以获得最短的检索时间,在DM方式没有命中后,再访问N-Ways方式组成的模块。

    上述这些方式基本是围绕着DirectMapped进行优化,目前鲜有现代微架构继续使用这些方法,但是在一个广义Cache的设计中,如果仅存在一级Cache,这些方法依然有广泛活跃着。这也是本节在此提及这些算法的主要原因。

    在体系结构领域,针对Cache的Way的处理上,还有很多算法,但是在结合整个Cache层次结构的复杂性之后,具有实用价值的算法并不多。在目前已实现的微架构中,使用的最多的方式依然是N-Ways Set-Associative。

    在某些场景下,MissPenalty无法忍受,比如TLB Miss,无论是采用纯软件还是Hardware Assistance的方法,Miss Penalty的代价都过于昂贵。这使得架构师最终选择了Fully Associative实现方式。在现代微架构中,TLB的设计需要对Hit Time和Miss Rate的设计进行折中,TLB因此分为两级,L1和L2。L1-TLB的实现侧重于Hit Time参数,较小一些,多使用Fully Associative方式,对其的要求是Extremely Fast;L2 TLB的实现需要进一步考虑Miss Rate,通常较大一些,多使用N-Way Associative方式。



    [1] 在Cache的设计中,地址信息并不是必要的。在Routing Table的查找中多使用了地址信息。

    [2] SRAM Cell还可以使用8个Transistors的实现方式。

    展开全文
  • 计算机体系结构cache

    千次阅读 2018-10-07 01:39:51
    cache电路 cache模型 cache算法 与cache相关的系统调用 0x00 cache简介 高速缓存(cache)是CPU内部用来加快数据访问的缓存技术。高速缓存属于SRAM,主存储器属于DRAM,一般而言主存储器一般称内存,后续我们...
  • 理解cache结构 bank

    千次阅读 2015-05-25 14:08:08
    讲解cache在intel和AMD之间的区别,并绘有结构图。http://blog.sina.com.cn/s/blog_6472c4cc0102duzr.html 本博客系统的介绍了cache的工作原理。 参考:http://blog.sina.com.cn/s/blog_6472c4cc0102dw61.html
  • Cache层次结构的引入

    千次阅读 2015-05-10 10:29:25
    我经常尝试一些方法,试图去解决在存储器子系统存在的瓶颈问题,总会陷入长考。在我们所处的这个领域,这个时代,在不断涌现出一些新的变化。这些变化会我们之前历千辛万苦学得一些知识和理念荡然无存。...
  • LRU Cache数据结构简介

    千次阅读 2014-03-26 18:21:48
    什么是LRU Cache  LRU是Least Recently Used的缩写,意思是最近最少使用,它是一种Cache替换算法。... 广义上的Cache指的是位于速度相差较大的两种硬件之间, 用于协调两者数据传输速度差异的结构。除了CPU与主存之间
  • http://www.tektalk.org/2011/04/14/%e7%8e%b0%e4%bb%a3-cpu-%e4%b8%ad%e7%9a%84-cache-%e7%bb%93%e6%9e%84/ 0.缘起 受首席启发,补充点 cache 背景。再乱弹一下 Page Coloring   1. 概述 ...
  • CPU体系结构cache小结

    万次阅读 多人点赞 2018-03-25 13:51:11
    1.What is cache? CPU缓存(Cache Memory)位于CPU与内存之间的临时存储器,它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分,但这一小部分是短时间内CPU即将访问的,当CPU调用大量数据时,就可...
  • Cache——缓存数据结构实现

    千次阅读 2015-09-16 18:13:49
    Cache——缓存缓存是临时存放数据的区域,缓存的运行速度比内存快得多,设计好一个缓存结构能够帮助我们更快地运行程序。 进来在阿里面试的时候也遇到设计一个缓存的问题,同时leetcode和Hihocoder上都出现了设计...
  • 存储器层次结构 - cache基本原理

    千次阅读 2013-05-27 15:43:48
    例如大多数程序都包好了循环结构,因此这部分指令和数据将被重复的访问,呈现出了很高的时间局部性。 空间局部性 如果某个数据项被访问,与他地址相邻的数据项可能很快被访问。由于程序通常是顺序执行的,因此程序...
  • IntegerCache

    万次阅读 2020-09-11 12:09:32
    Integer CacheIntegerCache源码Integer 使用Cache源码瞎搞 IntegerCache源码 java.lang.Integer.IntegerCache { static final int low = -128; static final int high; static final Integer cache[]; ... } ...
  • [计算机体系结构] Cache 基本概念

    千次阅读 2019-05-05 15:32:27
    CACHE中发现一个位置,并把新的cache数据存到这个位置的过程。这个处理过程可能包括evicting(驱逐)cache中已存在的数据,从而为新的数据腾出空间。 Associativity 指每个Set(集)里包含的line frames(行帧)...
  • 【并发编程】CPU cache结构和缓存一致性(MESI协议)

    万次阅读 多人点赞 2016-01-03 06:29:21
    cpu cache已经发展到了三级缓存结构,基本上现在买的个人电脑都是L3结构。 1. cache的意义 为什么需要CPU cache?因为CPU的频率太快了,快到主存跟不上,这样在处理器时钟周期内,CPU常常需要等待主存,浪费资源...
  • 浅析x86架构中cache的组织结构

    千次阅读 2016-03-31 15:51:59
    这篇文章诞生的源头是我之前在stackoverflow看到的一个问题: Why is transposing a matrix of 512×512 much slower than transposing a matrix ...想必对x86架构上的cache没有较深入了解过的童鞋看过之后也是一样
  • ArcGIS Server cache server directory的目录结构/L+/R+/C+,row和col是十六进制的行列号;而REST访问缓存目录的结构是///,是比例尺级别,、是十进制的行列号。可以通过Python将Server的 cache目录结构转换成REST的...
  • cache数据库之表的存储结构

    千次阅读 2015-08-10 16:14:50
    1.我们已经建了一个person类,接下来就是表的存储结构 2.打开Inspector,先输入rowid名字为p_RowID,选class->Storage 3.新建一个Storage,选择CacheSQLStorage,在SqlIdExpression中输入$i(^mdata(“Person”)) ...
  • kmem_cache是slab的核心结构体,主要描述slab的各种信息和链接空闲slab,还保存高速缓存的指针数组。所以要想使用slab分配得先创建kmem_cache结构体。 struct kmem_cache * kmem_cache_create (const char *name, ...
  • Cache的功能、结构与工作原理

    千次阅读 2010-05-15 11:41:00
    高速缓冲存储器是存在于主存与CPU之间的一级存储器, 由静态存储芯片(SRAM)组成,容量比较小但速度比主存高得多, 接近于CPU的速度。 Cache的功能是用来存放那些近期需要... Cache结构和工作原理如图2.3.1所示。
  • buffer cache实验1-内存结构图解

    千次阅读 2014-02-17 21:19:19
    1.为什么要使用buffer cache??? buffer cache就是一块含有许多数据块的内存区域,这些数据块主要都是数据文件里的数据块内容的拷贝。 从buffer cache中读取一个数据块一般需要100ns左右,从一般的存储硬盘中读取...
  • 首先给出一个存储器的金字塔形结构图:  L0 寄存器 Regs. (CPU在一个时钟周期内可以访问到)  L1 高速缓存 SRAM 几个时钟cycles  
  • Cache Pattern

    千次阅读 2013-03-04 13:12:46
    Oracle EBS中,如果获取Item,Organization等基础数据的信息。你可以写SQL来查,这种做法的不好处就是,在不同Procedure或者Function中,...以获取Organization为例,系统中标准的做法是: l_return_value := INV_CACHE.
  • Cache总义Cache用法之页面声明

    千次阅读 2007-03-20 22:05:00
    Cache总义Cache用法之页面声明Duration="#ofseconds"Location="Any|Client|Downstream|Server|None"VaryByControl="ControlName"VaryByCustom="browser|customstring"VaryByHeader="headers"VaryByParam="Parameter...
  • Cache lines & Cache coherence & False sharing

    千次阅读 2012-04-12 15:51:36
    Cache lines The data in a cache is grouped into blocks called cache-lines, which are typically 64 or 128 bytes wide. These are the smallest units of memory that can be read from, or written ...
  • Cache

    千次阅读 2016-09-01 23:14:04
    Cache失效的原因 强制性失效 (Compulsory miss): 当第一次访问一个块时,该块不在 Cache中, 需从下一级存储中调入 Cache, 这就是强制性失效。这种失效也称为冷启动失效,或首次访问失效。(增加块大小,预取) 容量...
  • namespace Coldairarrow.Util { /// <summary>... public enum CacheType { /// <summary> /// 使用内存缓存(不支持分布式) /// </summary> Memory, /// <summary>

空空如也

1 2 3 4 5 ... 20
收藏数 143,273
精华内容 57,309
关键字:

cache