以太坊cache生成算法

1. 考试题目，cache有甚麼作用老师给的提示是替换算法，甚麼随机替换，最不经常替换

高速缓冲存储器是存在于主存与CPU之间的一级存储器， 由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多， 接近于CPU的速度。
就是为了提高存取速度，当出现高速存储器对应列中没有空的位置时，便淘汰该列中的某一组以腾出位置存放新调入的组，这称为替换。确定替换的规则叫替换算法，常用的替换算法有:最近最少使用法（LRU）、先进先出法（FIFO）和随机法（RAND）等。

2. 使Cache命中率最高的替换算法是什么

是替换最近最少使用的块算法。

Cache替换算法是影响代理缓存系统性能的一个重要因素，一个好的Cache替换算法内可以产生较高的命中率。已经提出的算法可以划分为以下三类：

传统替换算法及其直接演化，其代表算法有：

①LRU（LeastRecentlyUsed）算法：将最近最少使用的内容替换出Cache；

②LFU（LeaseFrequentlyUsed）算法。

(2)以太坊cache生成算法扩展阅读：

运行程序设置：

1、打开开始菜单，打开运行框。如果开始菜单中没有这个选项，请按键盘windows+r组合键来打开运行。

3. CACHE替换算法有哪几种，分别简要说明

其代表算法有：①Hybrid算法：算法对Cache中的每一个对象赋予一个效用函数，将效用最小的对象替换出Cache；②LowestRelativeValue算法：将效用值最低的对象替换出Cache；③（LCNR）算法：该算法使用一个关于文档访问频次、传输时间和大小的推理函数来确定替换文档；④Bolot等人提出了一种基于文档传输时间代价、大小、和上次访问时间的权重推理函数来确定文档替换；⑤SizeAdjustLRU（SLRU）算法：对缓存的对象按代价与大小的比率进行排序，并选取比率最小的对象进行替换

扩展知识:
Cache是一种根据程序局部性原则，通过小容量速度快的存储器缓存部分数据，以减少处理器对慢速大容量存储器的访问次数，从而提升处理器取指效率的机制。Cache替换算法是指当Cache缺失发生后，Cache按某种机制选中高速缓存中的某个地址进行数据更新。Cache替换算法对Cache的命中率有较大的影响。目前主流的Cache替换算法有伪随机、先进先出(FIFO——First In First Out)和最近最少使用(LRU——Least Recently Used)等。相较于伪随机和先进先出算法，LRU算法更符合程序局部性原则(当前执行的程序代码，在不久后会再次访问该代码段)，Cache的命中率更高，但其硬件资源消耗非常大。

传统的LRU算法对Cache的每一路进行统计，在需要替换时，将最近最少被使用的那一路替换。由于传统LRU算法的数据使用频率统计为向上计数，故其计数器计数位宽较大，且需要额外的机制来处理计数溢出的情况。

4. Cache组相联映射到底应该怎么算法

我先确认你的题目细节：
block = 1B，就是1个字节。（主存交换大小）
cache4行，因为是二路组关联，所以每行2个block。因此cache一共4*2B = 8字节。cache一共2个字，这种题目没法做的，因为你是字编址！！
所谓我认为你的题目是有问题的！
下面假设交换大小是1W来做！！！！！！（或者字节编址）

4行，索引号需要2位；表示为00,01,10,11
访问：
0： 就是00，所以存放在第00行，缺失
4：就是100，也存放在00行，和0一行，缺失，但是lru标记在0
8：就是1000，存放在00行（看最后2位），因为lru标记，所以把0地址内容冲掉，lru在4
2：就是10，存放在10行，缺失
0:存放在00行，吧4冲掉，lru标记在8，缺失
6:110 ，存放在10行，缺失
8:1000，命中，lru标记在0
6:110，命中
4：100，缺失，吧0冲掉，lru在8
8：1000，命中，lru到4

5. 简要介绍Cache替换算法，及几种不同替换算法。

Cache替换算法是影响代理缓存系统性能的一个重要因素，一个好的Cache替换算法可以产生较高的命中率。目前已经提出的算法可以划分为以下三类：
（1）传统替换算法及其直接演化，其代表算法有：①LRU（Least
Recently
Used）算法：将最近最少使用的内容替换出Cache；②LFU（Lease
Frequently
Used）算法：将访问次数最少的内容替换出Cache；③Pitkow/Recker[10]提出了一种替换算法：如果Cache中所有内容都是同一天被缓存的，则将最大的文档替换出Cache，否则按LRU算法进行替换。
（2）基于缓存内容关键特征的替换算法，其代表算法有：①Size[10]替换算法：将最大的内容替换出Cache；②LRU—
MIN[11]替换算法：该算法力图使被替换的文档个数最少。设待缓存文档的大小为S，对Cache中缓存的大小至少是S的文档，根据LRU算法进行替换；如果没有大小至少为S的对象，则从大小至少为S/2的文档中按照LRU算法进行替换；③LRU—Threshold[11]
替换算法：和LRU算法一致，只是大小超过一定阈值的文档不能被缓存
...

6. 在存储系统的Cache与主层次结构中,常会发生数据交换问题,我们较常使用的替换算法有

常用Cache 块置换算法有
LRU,最近最久未使用
FIFO,先进先出等

7. 主存256MB,cache有8行,每行64B,直接映射,求cache总容量，不考虑cache一致性维护和替换算法控制位

主存256MB,所以，主存地址线28根，cache有8行（也就是8块）表示块号要3位表示，每行64B就是块内地址为6位，所以，标记位=28-9=19位，有效位占1位，共20位。cache每块占（20+64×8）位。总容量为8×（20+64×8）÷ 8=532B

8. 在计算机存储结构中，内存外存和CACHE内存都会用到替换算法，它们之间有什么异同点

相同点：内存与外存之间替换、内存与cache之间替换都要求高命中率，都需要将存储区划分成较小的模块。
不同点：内存与外存之间的替换速度远小于cache与内存之间的替换速度，因此内存与外存之间一次替换的模块较大，其一般采用段页式的映射方法，而cache与内存之间多采用组相联映射模式!

9. Cache内容为什么要经常替换常用替换算法有几种

二级缓存

CPU缓存（Cache Memory）位于CPU与内存之间的临时存储器，它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分，但这一小部分是短时间内CPU即将访问的，当CPU调用大量数据时，就可避开内存直接从缓存中调用，从而加快读取速度。由此可见，在CPU中加入缓存是一种高效的解决方案，这样整个内存储器（缓存+内存）就变成了既有缓存的高速度，又有内存的大容量的存储系统了。缓存对CPU的性能影响很大，主要是因为CPU的数据交换顺序和CPU与缓存间的带宽引起的。

缓存的工作原理是当CPU要读取一个数据时，首先从缓存中查找，如果找到就立即读取并送给CPU处理；如果没有找到，就用相对慢的速度从内存中读取并送给CPU处理，同时把这个数据所在的数据块调入缓存中，可以使得以后对整块数据的读取都从缓存中进行，不必再调用内存。

正是这样的读取机制使CPU读取缓存的命中率非常高（大多数CPU可达90%左右），也就是说CPU下一次要读取的数据90%都在缓存中，只有大约10%需要从内存读取。这大大节省了CPU直接读取内存的时间，也使CPU读取数据时基本无需等待。总的来说，CPU读取数据的顺序是先缓存后内存。

最早先的CPU缓存是个整体的，而且容量很低，英特尔公司从Pentium时代开始把缓存进行了分类。当时集成在CPU内核中的缓存已不足以满足CPU的需求，而制造工艺上的限制又不能大幅度提高缓存的容量。因此出现了集成在与CPU同一块电路板上或主板上的缓存，此时就把 CPU内核集成的缓存称为一级缓存，而外部的称为二级缓存。一级缓存中还分数据缓存（Data Cache，D-Cache）和指令缓存（Instruction Cache，I-Cache）。二者分别用来存放数据和执行这些数据的指令，而且两者可以同时被CPU访问，减少了争用Cache所造成的冲突，提高了处理器效能。英特尔公司在推出Pentium 4处理器时，用新增的一种一级追踪缓存替代指令缓存，容量为12KμOps，表示能存储12K条微指令。

随着CPU制造工艺的发展，二级缓存也能轻易的集成在CPU内核中，容量也在逐年提升。现在再用集成在CPU内部与否来定义一、二级缓存，已不确切。而且随着二级缓存被集成入CPU内核中，以往二级缓存与CPU大差距分频的情况也被改变，此时其以相同于主频的速度工作，可以为CPU提供更高的传输速度。

二级缓存是CPU性能表现的关键之一，在CPU核心不变化的情况下，增加二级缓存容量能使性能大幅度提高。而同一核心的CPU高低端之分往往也是在二级缓存上有差异，由此可见二级缓存对于CPU的重要性。

CPU在缓存中找到有用的数据被称为命中，当缓存中没有CPU所需的数据时（这时称为未命中），CPU才访问内存。从理论上讲，在一颗拥有二级缓存的CPU中，读取一级缓存的命中率为80%。也就是说CPU一级缓存中找到的有用数据占数据总量的80%，剩下的20%从二级缓存中读取。由于不能准确预测将要执行的数据，读取二级缓存的命中率也在80%左右（从二级缓存读到有用的数据占总数据的16%）。那么还有的数据就不得不从内存调用，但这已经是一个相当小的比例了。目前的较高端的CPU中，还会带有三级缓存，它是为读取二级缓存后未命中的数据设计的—种缓存，在拥有三级缓存的CPU中，只有约 5%的数据需要从内存中调用，这进一步提高了CPU的效率。

为了保证CPU访问时有较高的命中率，缓存中的内容应该按一定的算法替换。一种较常用的算法是“最近最少使用算法”（LRU算法），它是将最近一段时间内最少被访问过的行淘汰出局。因此需要为每行设置一个计数器，LRU算法是把命中行的计数器清零，其他各行计数器加1。当需要替换时淘汰行计数器计数值最大的数据行出局。这是一种高效、科学的算法，其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出缓存，提高缓存的利用率。

CPU产品中，一级缓存的容量基本在4KB到64KB之间，二级缓存的容量则分为128KB、256KB、512KB、1MB、2MB等。一级缓存容量各产品之间相差不大，而二级缓存容量则是提高CPU性能的关键。二级缓存容量的提升是由CPU制造工艺所决定的，容量增大必然导致CPU内部晶体管数的增加，要在有限的CPU面积上集成更大的缓存，对制造工艺的要求也就越高。

双核心CPU的二级缓存比较特殊，和以前的单核心CPU相比，最重要的就是两个内核的缓存所保存的数据要保持一致，否则就会出现错误，为了解决这个问题不同的CPU使用了不同的办法：

Intel双核心处理器的二级缓存
目前Intel的双核心CPU主要有Pentium D、Pentium EE、Core Duo三种，其中Pentium D、Pentium EE的二级缓存方式完全相同。Pentium D和Pentium EE的二级缓存都是CPU内部两个内核具有互相独立的二级缓存，其中，8xx系列的Smithfield核心CPU为每核心1MB，而9xx系列的 Presler核心CPU为每核心2MB。这种CPU内部的两个内核之间的缓存数据同步是依靠位于主板北桥芯片上的仲裁单元通过前端总线在两个核心之间传输来实现的，所以其数据延迟问题比较严重，性能并不尽如人意。
Core Duo使用的核心为Yonah，它的二级缓存则是两个核心共享2MB的二级缓存，共享式的二级缓存配合Intel的“Smart cache”共享缓存技术，实现了真正意义上的缓存数据同步，大幅度降低了数据延迟，减少了对前端总线的占用，性能表现不错，是目前双核心处理器上最先进的二级缓存架构。今后Intel的双核心处理器的二级缓存都会采用这种两个内核共享二级缓存的“Smart cache”共享缓存技术。

AMD双核心处理器的二级缓存
Athlon 64 X2 CPU的核心主要有Manchester和Toledo两种，他们的二级缓存都是CPU内部两个内核具有互相独立的二级缓存，其中，Manchester 核心为每核心512KB，而Toledo核心为每核心1MB。处理器内部的两个内核之间的缓存数据同步是依靠CPU内置的System Request Interface(系统请求接口，SRI)控制，传输在CPU内部即可实现。这样一来，不但CPU资源占用很小，而且不必占用内存总线资源，数据延迟也比Intel的Smithfield核心和Presler核心大为减少，协作效率明显胜过这两种核心。不过，由于这种方式仍然是两个内核的缓存相互独立，从架构上来看也明显不如以Yonah核心为代表的Intel的共享缓存技术Smart Cache。
___________________________________

前端总线
总线是将信息以一个或多个源部件传送到一个或多个目的部件的一组传输线。通俗的说，就是多个部件间的公共连线，用于在各个部件之间传输信息。人们常常以MHz表示的速度来描述总线频率。总线的种类很多，前端总线的英文名字是Front Side Bus，通常用FSB表示，是将CPU连接到北桥芯片的总线。选购主板和CPU时，要注意两者搭配问题，一般来说，如果CPU不超频，那么前端总线是由 CPU决定的，如果主板不支持CPU所需要的前端总线，系统就无法工作。也就是说，需要主板和CPU都支持某个前端总线，系统才能工作，只不过一个CPU 默认的前端总线是唯一的，因此看一个系统的前端总线主要看CPU就可以。

北桥芯片负责联系内存、显卡等数据吞吐量最大的部件，并和南桥芯片连接。CPU就是通过前端总线（FSB）连接到北桥芯片，进而通过北桥芯片和内存、显卡交换数据。前端总线是CPU和外界交换数据的最主要通道，因此前端总线的数据传输能力对计算机整体性能作用很大，如果没足够快的前端总线，再强的CPU也不能明显提高计算机整体速度。数据传输最大带宽取决于所有同时传输的数据的宽度和传输频率，即数据带宽＝（总线频率×数据位宽）÷8。目前PC机上所能达到的前端总线频率有266MHz、333MHz、400MHz、533MHz、800MHz几种，前端总线频率越大，代表着CPU与北桥芯片之间的数据传输能力越大，更能充分发挥出CPU的功能。现在的CPU技术发展很快，运算速度提高很快，而足够大的前端总线可以保障有足够的数据供给给CPU，较低的前端总线将无法供给足够的数据给CPU，这样就限制了CPU性能得发挥，成为系统瓶颈。显然同等条件下，前端总线越快，系统性能越好。

外频与前端总线频率的区别：前端总线的速度指的是CPU和北桥芯片间总线的速度，更实质性的表示了CPU和外界数据传输的速度。而外频的概念是建立在数字脉冲信号震荡速度基础之上的，也就是说，100MHz外频特指数字脉冲信号在每秒钟震荡一万万次，它更多的影响了PCI及其他总线的频率。之所以前端总线与外频这两个概念容易混淆，主要的原因是在以前的很长一段时间里（主要是在Pentium 4出现之前和刚出现Pentium 4时），前端总线频率与外频是相同的，因此往往直接称前端总线为外频，最终造成这样的误会。随着计算机技术的发展，人们发现前端总线频率需要高于外频，因此采用了QDR（Quad Date Rate）技术，或者其他类似的技术实现这个目的。这些技术的原理类似于AGP的2X或者4X，它们使得前端总线的频率成为外频的2倍、4倍甚至更高，从此之后前端总线和外频的区别才开始被人们重视起来。此外，在前端总线中比较特殊的是AMD64的HyperTransport。

10. Cache采用全相连映像方式，使用LRU页面替换算法，依次访问如下块，1，8，1，7，8，2，7，

全相联，数据可以存放在cache的任何一个地方。
共3个块，
第一冷缺失，cache存放的是1 X X
第二冷缺失，cache存放的是1 8 X
第三次命中，cache存放的是8 1 X
第四次冷缺失，cache存放·的是8 1 7
第五次命中，cache存放的是1 7 8

第六次缺失，cache存放的是7 8 2
第七次命中，cache存放的是8 2 7
第八次命中，cache存放的是8 7 2