【 我所認知的BIOS】-->Cache（3）
LightSeed
12/14/2009
Go on。。。这章详细讲cache的操作过程。
9、详细剖析memory的读操作
下面的一系列的演示是在486的基础上，并且L1 read miss的情况下。好，我们来开始：
Processor在执行
|
MOV AL,[4025] |
加上processor正处于保护模式或者实模式，并且segment是从0开始的，页管理方式已经关掉。那么我们可以这样理解上面这个指令，就是processor要准备从内存地址为00004025处的数据读一个byte出来，并存到AL当中去。
9.1 从L1 cache的角度来看main memory
Cache controller在486上的话必须要去考虑4G大小的内存空间。486的L1 cache controller把内存空间分成了2，097，152个页（这个页和讲虚拟存储机制中的页两回事哦。）而且每个页大小是5KB。Cache controller还把这每个page都均分成了128个line，每个line的大小一下就算出来了是16个bytes（这就是前文提到的“不太大的一块数据”），line的序号是从0~127。
举个例子，内存地址从00000000~00000000FH的内存数据应该属于是page 0，line 0的地方。00000010~00000001FH的内存数据应该属于是page 0，line 0的地方，以此类推。当processor产生一个内存地址的时候，高21位（A31:A11）是用来确定2KB page的，接着的7位（A10:A4）是用来确定这个page中Line的。剩下的最低4位是用来确定这里line中的具体位置。
那么来看看我们例子中的内存地址，00004025H，用这种方法来计算的话，mov指令应该尝试着去读取第8 page的第2 line的第5位置处的数据。
9.2 L1响应memory read的请求
物理内存的地址00004025H传递到L1 cache controller后，L1 cache controller去check自己的目录里面是不是有这个内存中的数据。如果数据在L1 cache里面的话，那么L1就迅速地放回数据给processor。如果数据不在L1 cache中的话，那么L1 cache controller就会产生一个read周期的请求到总线上。
9.3 L1 cache controller的结构
L1 cache controller的结构如图3，
图3 L1 cache controller的结构
从图3中可以看出，在cache的存储器中有4个bank，一般命名为way0~way3。每个bank（way）是由2KB的高速静态RAM组成。这2KB的SRAM被分成了128个Line（0~127）。每个line能够存储16个bytes的数据。当一个16 byte的数据从外部存储器中读到cache controller中的时候，会被存到4个bank中某个bank的某个Entry里面去。不过，这里对应的Entry是专属的。举个例子，任何一个memory page中的 line 12的数据都会被放到bank中的Entry 12处。
让我们来看看图3，一个一个来说其中的作用吧：
①LRU，这个就是least recently used，它是供LRU算法计算用的标记。（后面我会详细说明。）
②Tag valid bits，它是标记后面的tag field是否有效的。在cache controller check的过程中，会首先看这个bit。如果无效的话，那么根本不用看了。如果有效的话，那么通过比对知道，line中的数据是从哪个内存地址copy过来的数据。
③Tag fields，它本身在entry（条目）中所处的位置和自己这个区段存储的数据结合起来就表示了他对应的实际的物理内存地址（physical memory address）。见图3的最下方，[A31:A11]代表了是从page 8中来的数据，[A10:A4]表明了是从line 2中来的数据。而存储的数据就在bank中的line 2里面。（那么你现在知道图3中，tag fields 0~3中所对应的数据，对应的物理地址是多少么？）
如果在cache controller在check page address的时候，没有tag fields与之匹配，那么cache miss就发生了。Controller就会触发一个read的请求到bus上，以此希望能从外部的存储器得到数据。当数据从外部的存储器读回来的时候，controller必须要把数据保存起来，并且更新目录条目。如果当前的4个line都是被使用的，那么controller就必须要去裁定哪个是最旧的数据，然后用新的数据覆盖它。与此同时目录条目（directory entry）和LRU标记都要更新。这种情下，controller就是用LRU的标记来做判断的。
9.4 L1 cache的check
图4是L1 cache解析内存地址的一个示意图，见图4再回味一下上节Tag field的说明就可以更清楚了。
图4
9.5 The bus cycle request
当read miss发生的时候，L1 cache controller触发一个memory read 的系统周期请求到处理器的总线单元上去。作为回应，总线单元（bus unit）会触发一个memory read的总线周期（bus cycle）。486 processor会屏蔽掉地址的最低两位，因为processor没有A0和A1这两个输出。这是因为内存地址会被转换成双字（double word）来读取。比如说，在操作00004025H的时候，会把地址转换成00004024H处的地址，但是会bus unit会把BE1#使能，这样就可以确定从00004024H开始的双字的第二个位置作为目标位置。图5是当前的内存地址输出的信号。
图5 00004025H的内存地址信号输出
图6是总线周期的时序图。看看图6中的第二周期，当00004025H地址被放到地址总线上时，双字地址当然应该是00004024H，从00004024H开始处的4个byte是00004024~00004027H这四个内存地址处的数据。因为执行单元只需要00004025H中的数据，（仅仅需要第二个byte），这就体现在BE1#被使能上。Processor同时会把PCD(page cache disable)输出拉低，（表明，现在是有cache的）。那么L2的存储系统就必须要考虑内存地址是cacheable的情况，应该要接收整个line里的信息。（16 bytes哦，所以才会有4020~402C这么多地址的信息，不过可能有人会问，为什么是先传00004024H开始的double word呀？这是和line fill的机制有关的，后面稍微讲讲。）假如说，processor的PWT（page write through）代表着更新cache的方式。（也就是前面我们所说的WB和WT两者的区别。）当PWT为低的时候，表示write back controller在更新cache的同时，不需要同时更新主存。当write miss的时候processor就得把数据写入到主存中去。反之（PWT为高）就是write-back controller在更新它的cahce的时候同时也更新主存。如果write miss的话，那么就只更新主存。
图6 总线周期的时序图
其实在第一次或者说第N次读这个图的时候，对于图中的两个wait state总是感觉理解的不够深入。这里也详细说明一下，为什么会有这两个状态，并且他们的作用是什么。
先说说第一个wait state（CLK 4其实后面的一个wait 也是一样的。至于为什么要间隔开，到目前为止，我的理解是因为486能够锁存的数据是64bit，如果是128bit的话，就应该能一次（不用再插入wait的状态）全部传输完了。），processor采样RDY#和BRDY#来check需要读取的data是否再数据总线上。当BRDY#（笔者：从某种程度上说，BRDY#的信息对于CPU更有效。）采样有效后，这就告诉了processor两件事：
①第一个doubleword（16个bytes分成4个double word来传送。）已经在数据总线上了。
②memory的地址传送支持bursting这种机制。
Processor作为回应应该是这样：
①读取总线上的第一个doubleword下来，并存到L1 cache的存储器中去。当然这个信息是不会被L1记录下来的。只有等到整个line都被填满了后才会把这个信息记录下来。
②确定本来processor想要的数据。（比如说00004025H处的数据。）执行单元会把这个byte的数据放到AL寄存器中去，这才是真正的MOV指令哦。呵呵。。。
③突发传输（burst）第二个doubleword，（地址是00004020H）。
9.6 怎么去填cache的Line
正如前面所说，当L1 cache miss发生了以后，processor把内存地址放到地址总线上去，并且把PCD拉低来表明马上要执行填L2 cache的line。NCA逻辑部件也是内存地址解析的一个重要部分，每次机器上电后，NCA逻辑部件都会自动地被设置成non-cacheable的属性。当NCA逻辑部件检测到总线上的内存地址是cacheable的时候，它就得在地址周期（address time（T1））结束前把KEN#（Cache enable）信号拉低。只有这样做了，才能表明memory已经同意填line的信息。Processor必须在CLK的上升沿的时候采样KEN#信号，接着在下一个CLK上升沿采样RDY#或者BRDY#信号。
在我们的例子中，从图6中可以看出，当从00004024H的内存地址读取一个双字的的时候，在第一个总线周期（bus cycle）中插入了一个wait的状态。我们假设00004025H的内存地址是cacheable的情况下，processor会在地址周期的最末，采样KEN#信号（low）。当在下一个CLK周期的上升沿采样到BRDY#的时候，说明processor的地址系统已经同意执行cache line fill的操作了。
9.7 cache line fill defined
刚刚一直在说line fill，可是它究竟是个啥呢？是怎么定义的呢？
每当cache controller发生read miss的时候，processor就必须要经过L2 cache controller到速度比较慢的主存中去read，请求data。然而在L2 读取数据的时候，却不是单独地读取某一字节或者字。由于L1的cache是由Line这种东西来存储数据的，而且在486上一个line的大小为16 bytes，那么当cache从主存读取数据到line的时候，就需要操作16个bytes了。
然而16个bytes组成的一个block的位置都是在可以被16整除的地址界限上开始的。（比如说0H,10H,20H etc.）
当L2 read miss的时候，processor触发了一个memory read的bus cycle。经过NCA逻辑解析后，假如这个memory address是cacheable的，那么processor就希望能够获取4个double word的信息。然而这4个double word却不需要送回来的顺序是已经规定好的。而这个送回来的顺序就叫做“cache line fill sequence”。这个顺序可以有以下四种，见图7（笔者：这里PCI的设备读取data的时候也有这个顺序，在操作cacheline上，pci spec的规定和CPU是一致的。）
图7 cache line fill sequence
9.8 L2 cache对memory address的解析
在前面的小节我们有说，processor发出的地址中是没有A1和A0的，而且要读取的字节就在BE1#这个信号上。但是L2 cache controller和processor都同意执行line fill的动作了。Cache controller就会忽略实际的BE1#的信号。换句话说，整个double word的数据将会全部送回给processor。原因就在于bus cycle已经转换成了cache line fill的动作了，processor期望的是能够得到整个doubleword的数据，（就算是他对BE1#也有了操作。）。
9.9 L2 cache read miss给processor带来的影响
我们可以从cache line fill的顺序中看出，在数据送回来的时候有可能第一个从慢速的main memory读回来的doubleword数据不是processor需要的数据，所以在bus cycle中就可能会插入一个或者多个的wait state。所以整个系统的性能也就有所下降了。（看来cache的命中率的高低，直接影响着系统的性能。）
9.10 Dram主存的组织
要想达到最优化的内存配置，应该具备以下三个条件。参见图8
①用交叉内存的架构。所有地址线A2=0的数据都放在memory的bank A中，而地址线A2 = 1的数据都放在bank B中。
②锁存64个bit，如果能锁存64个bit的话，那么在执行读的时候就可以同时读取2个doubleword了。（参见后续章节，那么在读取第二个doubleword的时候就会省下一个周期。）
③主存的控制逻辑部件也应该设计出侦测cache line fill的动作。换句话说，当L2 cache controller在执行cache line fill的过程中，主存最好能够自动地从main memory中读取4个doubleword。
图8 主存的组织形式
9.11 第一个doubleword是怎么被送到L2 cache的
见9.5节的最末的特别说明。
9.12 Memory 子系统处理剩下的三个doubleword
当processor收到第一个doubleword后，它就会把第二个doubleword的地址放到A31:A2上，并且把4个byte都设为有效（在图6中的CLK 5时做的）。举个实际的例子来说，第二个doubleword是00004020H。因为processor已经从memory读到了64个bit的数据并被L2 cache锁存了起来，那么这第二个doubleword就可以马上有效地放到数据总线上了。在CLK 5的最末processor会去采样RDY#和BRDD#信息来check第二个doubleword是不是在数据总线上了。等到BRDY#有效，L1就会把这个doubleword存储到way3 line 2的存储器里去。至此4个doubleword中的两个doubleword已经被读取了。
因为BRDY#有效，（不是RDY#）processor会在下一个周期中burst out第三个doubleword。（由于此时就没锁存了，所以要插入一个等待的周期。）从第三个doubleword开始，就相当于是重复了读取第一个doubleword的过程。在此不再赘述。
9.13 结束的标志
当第三个doubleword的数据被放在数据总线上的时候，Look-through cache controller会使能KEN#（cache enable）。这个信号是去使能L1 cache controller去储存这个line的数据到L1 cache中去。当cache controller已经侦测到了snoop hit的时候，（其他的bus master要更新主存中的数据的，而这个数据恰好正是目前正在传输的数据，正在做line fill的动作。 ）假如processor允许在这种情况下继续把line fill填完，那么这L1 cache中的数据就是“过时”的数据了。
Processor采样KEN#，如果它在这个数据的周期的末尾还是有效的（CLK 7），那么说明这个数据是有效的。否则就不是有效的。
9.14 L1 cache的更新
在前面的那么多的篇幅中，详细讲了怎么将信息从DRAM传输到cache中来，那么cache又是怎么更新自己的line的呢？这节就是来探讨这个问题。
让我们再来看看图3，为了方便我就copy到这里来了。
图3 L1 cache controller的结构
从图中我们可以看出，cache里line 2的当前数据是这样组成的。分别从page 200H，A300H，1000H，2314H copy过来的数据，并且4个entry都是有效的。不幸的是，这个时候一个新的page的数据必须要存入到line 2中来，cache controller就必须要决定哪一个field应该用新的数据去覆盖。那么这个时候，之前提到的LRU（Least-recently used）算法就派上用场了。让我们来先看看图9，整个LRU算法的精髓都体现在其中了。
图9 LRU 算法示意图
我们来看看当前的LRU bit的设置是101B。因为bit0和bit2是“1”，所以way 3中的line会被更新。图中的路线写的比较清楚，所以也不必赘述。在更新line的同时，也会把LRU的bit更新，供下次裁决用。（笔者：至于LRU标记是怎么更新的，还没找到相应的资料。）
9.15 关于memory read的时间问题
如果说用386的传统传输数据的模式，那么copy这4个doubleword最少都需要12个PCLK的。（每传输一个doubleword都需要3个PCLK。）如果用burst-mode来传输的话，将会需要7个PCLK。（第一个doubleword需要3个PCLK，第三个需要2PCLK，其他两个分别需要1个PCLK。）如果请求的数据本来就在L2 cache里面的话，只需要用5个PCLK。因为不需要等待周期的插入了。
9.16 印证我的猜想
我们假设一下，当L2 cache能够锁存128个bit的时候，processor的timing会不会在传输第三个doubleword的时候就直接传输数据了呢？（不插入等待周期了。）事实证明确实如此。见图10，是有4个bank的内存存储数据示意图（交叉存是为了提高效率。）
图10 4 bank下为了支持burst而交叉存储数据
图11是在这种情况下，processor传输4个doubleword的时序图。从图10中我们可以清楚地看到，第三个doubleword之前的wait state已经没了。这也印证了前面我的猜想。
图11 L2 cache可以锁存128 bit时总线上的时序
9.17 用burst从L2 cache传输数据
在9.16中就有说，从L2 cache直接读取数据的话会比较快，因为中间不用插入wait的周期。参见图12，从图中的时序可以看出，仅仅需要5个PCLK就可以把4个doubleword的数据传输完成了。
图12 从L2 cache用burst读取数据时序
9.18 Burst的中断
在某些情况下，memory子系统在执行burst cache line fill的时候不能响应4个doubleword的传输。图13就是这种类型的时序图。
图13
在我们说的这个例子中，当前面两个doubleword（00004024H和00004020H）已经从memory中用burst读出来后。然而在正要传输第三个doubleword的时候，memory logic部件用RDY#信号来代替了BRDY#。这就导致了486上burst的“interrupt”。
但是486仍然希望cache line继续被填完，由于终止了burst的传输，那么processor就马上出发正常的bus cycle来读取下一个doubleword（0000402CH）。然而这个时候却有恰好满足了一个burst的条件(见图12)，因为：
①486一直保持着BLAST#信号off，这就说明下一个doubleword不是最后一个doubleword。
②然而BRDY#却又有效了，那么又说明现在又可以进行burst传输了。
当在之后burst传输中，到第二个doubleword（0000402CH）的末尾时候，NCA logic部件使能KEN#信号来表明下一个doubleword就是最后一个数据了。（line被完全写进去了。）（笔者：同时我们也可用猜想一下，假如第三个doubleword传好后，RDY#信号又代替了BRDY#信号，会发生什么事情呢？）
486作为响应，会控制BLAST#（拉低），当486在时钟的最末，会采样BRDY#完成全部的传输。最终完成line的fill。
9.19 没有burst的line fill
其实过程大多都不用说，用一个时序图能够清楚地把话说出来。每传输一个doubleword都会插入wait 状态。
见图14
图14 没有burst下的line fill时序图
10、L1 cache处理memory的write
其实理解了read的操作后，来理解write也就不难了。当processor触发了write的动作后，cache controller用address来check cache中的目录条目，当有相互匹配的entry找到的时候，我们就称这为write hit了。如果cache controller是WT的，那么controller会先把数据更新到cache存储器当中去，然后马上下命令让bus单元执行memory的write操作。这样L1中的数据和外部存储器的数据就达到一致了。
11、486的cache snooping
当486执行写的操作，准备把数据写到main memory的时候，486的L1 cache必须要注意数据的变更。如果不这样做的话，后果可想而知。为了保持486的cache中的数据一致性，486有“snooping”的机制来侦测地址总线上的操作。在486上主要由下面两个pin来完成：
①AHOLD（Address Hold），如果其他的bus master有写数据到主存的动作，外部的逻辑器件就会使能AHOLD。486会响应AHOLD，它马上就放弃它对的地址总线的控制权。
②EADS#（External Address Status），紧接第一步，外部逻辑器件会使EADS#有效，以此来表明外部的bus master已经把有效的数据的内存地址放到了地址总线上了。A31:A4这会就用来做486的输入，L1 cache controller就可以用此来check将要被写的数据的地址。这个地址被用来在L1 cache 中check自己的line。如果恰好L1 cache中恰好也被扫描到有这个地址的数据，那么相应的Valid标志位就会被marked。（因为它的数据已经不能实时反映最新的数据了。）
L1的snoop也叫做cache invalidation cycle。因为他的作用就是当snoop命中的时候，直接把它自己copy好的line invalid（说明它的数据是不会被更新的哦，在MESI的协议中就反应为I（invalid）的动作，见图16）。时序可参见图15
图15 cache invalidation cycle
12、对L1和L2 cache的控制
这节主要探讨一下FLUSH#，INVD，WBINVD。
①FLUSH# pin的效果在L1和L2 cache上的效果是一样的。当FLUSH#有效的时候，会导致L1，L2 cache controller的Tag valid bits都被清掉。而在L2上。
②INVD指令的执行，会代指L1 cache被全部无效。并且在486上会执行一个特殊的bus cycle来给外部的cache下命令，flush他的内容。
③WBINVD指令的执行，会有两个事情发生。
A，L1 cache被刷掉。
B，486上会执行一个特殊的bus cycle来给外部的cache下命令，把全部的无用的数据都写回到主存中去，并刷掉它的数据。
MESI我自己画的图（486的）
图16 MESI