【旧文重发 | 03】IC基础知识

[41] 什么是时间局域性和空间局域性？

局域性原理：程序常常重复使用它们最近用过的数据和指令。一条广泛适用的经验规律是：一个程序90%的执行时间花费在仅10%的代码中。局域性意味着我们可以根据一个程序最近访问的指令和数据，比较准确地预测它近期会使用哪些内容。局域性的原理也适应于数据访问，不过不像代码访问那样明显。

• 时间局域性是指最近访问过的内容很可能会在短期内被再次访问。
• 空间局域性是指地址相互临近的项目很可能会在短时间内都被用到。

[42] 计算机系统中有哪些存储？

1. Register
2. Cache
3. Main Memory/Primary Memory
4. Secondary Memory (Magnetic/Optical)

[43] 什么是cache？

cache是小型的快速存储。通常在Main Memory和CPU之间，有时放置于CPU内。

[44] 概述cache操作，cache功能的原理是？

每当CPU请求存储位置的内容时，都会首先检查cache中是否有此数据。如果cache中存在数据，则CPU直接从cache中获取数据。由于不需要CPU进入该数据的Main Memory，因此速度更快。如果缓存中不存在数据，则将一块数据从Main Memory读取到cache中，然后以字块的形式从cache中传输到CPU。

[45] 什么是cache的miss和hit？

在cache中查找地址时，若缓存中包含该内存位置，称之为cache hit。如果在cache找不到，则称之为cache miss。

[46] 如果一台机器存在cache，那么在链表和向量中搜索一个值的性能表现有什么差异？

链表是一种将其元素存储在非连续存储位置中的数据结构，而向量是一种将元素存储在连续位置中的数据结构。对于具有cache的设计：如果cache中存在一块数据，则很可能在cache中也存在后续的连续数据，因为通常是从主存储器到高速缓冲存储器的任何取指令 根据缓存行（通常为64或128字节）获取。因此，在拥有cache的机器上，通过向量进行搜索将比链表进行搜索更快。

[47] 将内存映射到cache有哪些机制？请比较他们的优缺点

一共有三种主要的映射方法。这三种映射中，主存储器和cache都被划分为存储块（blocks of memory，也称cache line，每个64bytes），这是映射时的最小单位。

• 直接映射(Direct Mapping):直接映射中，主内存和cache中始终存在一对一的映射，一组只有一个数据块。例如：在下图中，cache大小为128个块，而主内存中有4096个块。设计实现是基于模数计算得到的，i为cache的块序号，j是主内存的块编号，m是cache的行数，i = j mod m。如果块的大小为64B而地址为32为，则地址[5：0]称为字节偏移量，它说明字节在块中的位置，地址[12：6]称为组位，说明地址地址映射到哪一组，剩下的地址位作为标志位，标志说明cache映射了哪些内存中的地址。这是最简单的映射，并且可以通过内存地址可以轻松计算cache中的数据在内存中的位置，并且只需要一个标记为进行比较就能知道是否命中。这种映射的缺点是命中率低， Cache的存储空间利用率低。

• 全局关联映射(Fully Associate Mapping):任何的内存块都能映射到cache的任何块中，使用和上面的图一样的例子，地址[5:0]，作为块内部的索引，剩下的所有位都用于和cache中的所有标记为进行比较，这需要很大的比较器。虽然这种方式命中率较高，Cache的存储空间利用率高，但是线路复杂，成本高，速度低
• 组关联映射(Set Associate Mapping):将cache分成u组，每组v行，主存块存放到哪个组是固定的，至于存到该组哪一行是灵活的，即有如下函数关系：cache总行数m＝u×v，组号q＝j mod u组间采用直接映射，组内为全相联。例如，下图显示了128个块的相同高速缓存，这些高速缓存组织为64个集合，每个集合具有2个块。硬件较简单，速度较快，命中率较高，但是与分组有关系。

[48] 更高关联性的缓存有什么缺点？

更高关联性的cache意味着需要更加大的比较器，用于将传入的地址和标签进行对比，会导致更加大的硬件需求和功耗。

[49] 一个按字节寻址的CPU的cache具有以下特征：a)与大小为1byte的块直接映射 b)块的cache索引位4位。那么cache中包含多少个块，作为cache的一部分，需要存储多少个标记为？

cache的索引位有4位，因此cache包含2^4=16个块，每个块只有1byte所以不需要块内索引，剩下的16-4=12位全部作为标记位

[50] 一个四路组关联的cache总大小为256KB，如果每个cache line的大小为64byte，那么cache中有多少组？标记位需要多少位？假设地址位宽位32位。

cache的块的数量为256K/64=4096，而cache为四路关联，则组数量为4096/4=1024。64byte的cache line 需要6位进行块内索引，10位进行集合索引，剩下的32-6-10=16位作为标记为

[51] 直写式缓存和回写式缓存有什么区别？优缺点是什么？

• 直写式缓存方式: 当CPU要将数据写入内存时,除了更新缓冲内存上的数据外,也将数据写在SDRAM中以维持主存与缓冲内存的一致性,当要写入内存的数据多起来的话,速度自然就慢了下来.
• 回写式缓存方式: 当CPU要将数据写入内存时,只会先更新缓冲内存上的数据,随后再让缓冲内存在总线不塞车的时候才把数据写回SDRAM,所以速度自然快得多

回写缓存在内存带宽利用方面更好，因为仅在需要时才回写数据。如果系统中存在多个可以缓存同一地址的cache，则维护数据一致性非常复杂，因为内存可能并不总是具有最新数据。

[52] inclusive 和 exclusive cache之间有什么区别？

cache的inclusive和exclusive属性适用于具备多级缓存的设计。

• 当CPU试图从某地址load数据时，首先从L1 cache中查询是否命中，如果命中则把数据返回给CPU。如果L1 cache缺失，则继续从L2 cache中查找。当L2 cache命中时，数据会返回给L1 cache以及CPU。如果L2 cache也缺失，很不幸，我们需要从主存中load数据，将数据返回给L2 cache、L1 cache及CPU。这种多级cache的工作方式称之为inclusive cache。某一地址的数据可能存在多级缓存中。
• 与inclusive cache对应的是exclusive cache，这种cache保证某一地址的数据缓存只会存在于多级cache其中一级。也就是说，任意地址的数据不可能同时在L1和L2 cache中缓存。

exclusive cache的优点之一是多级cache可以一起存储更多的数据。一般使用inclusive cache类型，每次cache miss，可以从下一级的cache中寻找，load。而exclusive cache，每次cache miss，只能去main memory中load。但是exclusive cache比较节省cache size。

[53] 组关联映射中用于替换cache line的算法有什么不同？

以下是一些可用于替换cache line的算法

• LRU(Least Recently Used):将最近最少使用的内容替换出cache
• MRU (Most Recently Used):与MRU，将最近经常的内容提出cache
• PLRU (Pseudo LRU):关联性很大的时候，LRU的实现成本很高。如果实际情况在丢弃任一个最近最少使用的数据就能满足，那么伪LRU算法就派上用场了，它为每一个缓存数据设立一个标志位就可以工作。
• LFU (Least Frequently Used):这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。
• Random replacement:在该算法中，不存储任何信息，并且在需要替换时选择一条随机行。

[54] 缓存一致性的问题是什么？

在多个处理器拥有自己的cache的共享多处理器系统中，相同数据（相同地址）的多个副本可能会同时存在于不同的cache中。如果允许每个处理器自由更新cache，则可能导致内存视图不一致。这称为高速缓存一致性问题。例如：如果允许两个处理器将值写入同一地址，则在不同处理器上读取同一地址可能会看到不同的值。

[55] 基于监听和基于目录的缓存一致性协议之间有什么区别？

• Snoop based Coherence Protocol:来自处理器的数据请求将发送到共享系统一部分的所有其他处理器。其他所有处理器都监听此请求，并查看它们是否具有数据副本并做出相应响应。因此，每个处理器都需要维护存储器的一致性视图。
• Directory based Coherence Protocol:目录用于跟踪哪些处理器正在访问和缓存哪些地址。发出新请求的任何处理器都将检查此目录，以了解其他代理是否有副本，然后可以向该代理发送点对点请求以获取最新的数据副本。

[56] 什么是MESI协议？

MESI协议时多处理器系统中最常用的cache一致性协议。MESI 是指4中状态的首字母。每个Cache line有4个状态，可用2个bit表示，它们分别是：

[57] 什么是MESIF和MOESIF协议？

是对于MESI协议的扩展，引入了两个新状态“F”“O”：

• F (Forward): 在MOESI协议中，S状态的定义发生了细微的变化。当一个Cache行状态为S时，其包含的数据并不一定与存储器一致。如果在其他CPU的Cache中不存在状态为O的副本时，该Cache行中的数据与存储器一致；如果在其他CPU的Cache中存在状态为O的副本时，Cache行中的数据与存储器不一致。
• O (Owned): O位为1表示在当前Cache 行中包含的数据是当前处理器系统最新的数据拷贝，而且在其他CPU中一定具有该Cache行的副本，其他CPU的Cache行状态为S。如果主存储器的数据在多个CPU的Cache中都具有副本时，有且仅有一个CPU的Cache行状态为O，其他CPU的Cache行状态只能为S。与MESI协议中的S状态不同，状态为O的Cache行中的数据与存储器中的数据并不一致。

[57] 什么是虚拟内存？

虚拟内存是一致内存管理技术，及时实际的物理内存很小，虚拟处理器也允许处理器查看地址的虚拟连续空间。操作系统管理虚拟地址空间以及从辅助设备（如磁盘）到物理主内存的内存分配。CPU中的地址转换硬件（memory management unit，MMU）将虚拟地址转换为物理地址。此地址转换使用分页的概念，其中将连续的内存地址块（称为页）用于虚拟内存和实际物理内存之间的映射。

[58] 虚拟内存地址和物理内存地址的区别是什么？

软件程序或进程用来访问其地址空间中存储位置的地址称为虚拟地址。然后，操作系统连同硬件将其转换为另一个地址，该地址可用于实际访问DRAM上的主内存位置，该地址称为物理地址。地址转换是使用分页的概念完成的，如果主内存或DRAM没有此位置，则在OS的协助下，数据将从辅助内存（如磁盘）移至主内存。

[59] 什么是页的概念？

所有虚拟内存都将虚拟地址空间划分为页，页内的虚拟内存地址是连续的。页是内存从辅助存储移动到物理内存以管理虚拟内存的最小单位。大多数计算机系统的页至少为4KB.当需要更大的实际内存是，某些结构还支持更大的页。页表用于将应用程序看到的虚拟地址转换为物理地址，是一种数据结构，用于多页情况下，在内存中虚拟地址到物理地址的映射。

[60] 什么是TLB？

TLB: Translation Lookaside Buffer。根据功能可以译为快表，直译可以翻译为旁路转换缓冲，也可以把它理解成页表缓冲。里面存放的是一些页表文件（虚拟地址到物理地址的转换表）。当处理器要在主内存寻址时，不是直接在内存的物理地址里查找的，而是通过一组虚拟地址转换到主内存的物理地址，TLB就是负责将虚拟内存地址翻译成实际的物理内存地址，而CPU寻址时会优先在TLB中进行寻址。处理器的性能就和寻址的命中率有很大的关系。