计算机组成原理第三次作业

3.1 解释下列名词

存储单元

存储单元是计算机内存的最小可寻址单位。它通常包含一个固定数量的位，这个数量取决于计算机的体系结构。

存取时间

又称为存储器的访问时间，是指启动一次存储器操作(读或写分别对应取与存)到该操作完成所经历的时间，注意读写时间可能不同，DRAM 读慢写快、闪存读快写慢。

存取周期

连续启动两次访问操作之间的最短时间间隔;对主存而言，存储周期除包括存取时间外，还包括存储器状态的稳定恢复时间，所以存储周期略大于存取时间。

存储器带宽

单位时间内存储器所能传输的信息量，常用的单位包括位/秒或字节秒;带宽是衡量数据传输速率的重要指标，与存取时间的长短和一次传输的数据位的多少有关;一般而言存取时间越短、数据位宽越大，存储带宽越高。

刷新

对于某些类型的内存（如动态随机存取内存，DRAM），数据在存储单元中的存储是暂时的，如果不定期地进行刷新，数据就会消失。刷新过程就是重新充电到内存单元，以保持数据的存在。这个过程通常由硬件自动完成，对于程序员来说是透明的。

大端存储

采用多字节方式访问主存时，主存中的字节顺序非常重要，不同的顺序访问得到的数据完全不一样。当存储器的低字节地址单元中存放的是数据的最高字节时称这种数据存放方式为大端(Big-Endian)方式。

小端存储

当存储器的低字节地址单元中存放的是数据的最低字节时，称这种数据存放方式为小端(Litte-Endian)方式;

字扩展

"字扩展"通常指的是将一个较小的数据类型（如字节或半字）扩展到一个较大的数据类型（如字或双字）的过程。

字扩展可以是有符号的或无符号的。有符号扩展会保留原始数据的符号（正或负），而无符号扩展则总是产生一个非负结果。

位扩展

"位扩展"是指将一个较小位数的二进制数扩展到一个较大位数的过程。

多体交叉存储器

多体交叉存储器也由多个存储模块构成，这些模块的容量和存取速度相同。根据对多个模块编址方式的不同，其组织方式又可分为高位多体交叉和低位多体交叉两种。

TLB（快表）

cache 虽然可以缓存部分经常访问的页表块，但这种数据块的粒度较大，并不能充分利用虚拟存储器访问的局部性。为了进一步降低虚拟存储器地址转换的硬件开销，现代处理器都维护着一个转换旁路缓冲区(TranslationLook-aside Bufer，TLB)，用于缓冲经常访问的页表项 PTE。TLB 本质上就是一个容量较小的 cache，为提高查找速度，大多采用全相联或组相联方式，且采用随机替换算法。
当采用组相联方式时,按照组相联cache的地址划分方法,将虚页号划分成TLB标记(TLBT)和TLB 索引(TLBI)两部分，以便于快速判断所要访问的页面是否在主存中，当 TLB命中时还可利用 TLB返回的 PTE 完成虚拟地址到物理地址的转换。组相联时虚拟地址划分如下图

TLB离CPU更近，访问速度更快，所以通常将TLB表称为快表，而将主存中的页表称为慢表。

LRU算法

近期最少使用(Least Recently Used，LRU)算法是将近期内最久未被访问过的行淘汰。为此，每行也需要设置一个计数器，cache 每命中一次，对应的命中行计数器清零，其他各行计数器加1,因此它是未访问次数计数器。当需要替换时,比较各特定行的计数值,将计数值最大的行换出。这种算法显然保护了刚载入 cache的新数据，符合 cache 工作原理，因此使 cache 有较高的命中率。LRU算法硬件实现的难点主要是快速比较多行计数器。要找出计数值最大的cache行，具体实现时需要较多的比较器进行归并比较。但如果是二路组相联的cache，情况则会大为简化。因为一个主存块只能在一个特定组的两行中存放，二选一完全不需要计数器，只需要一个二进制位即可。如果规定一组中当A 行调入新数据时将此位置1，另一行(B行)调入新数据时将此位置 0，那么当需要替换时只需检查此位的状态即可，若此位为0，说明B行的数据比 A 行的后调入，故将A行换出，反之则换出 B行。Pentium 机芯片内的数据 cache 是一个二路组相联结构,采用的就是这种 LRU 替换算法。

Cache一致性

缓存一致性（Cache Coherence）是多处理器系统中的一个重要概念。在多处理器系统中，每个处理器都有自己的私有缓存，用于存储最近访问的数据。当多个处理器同时访问和修改同一块内存区域时，就可能出现缓存不一致的问题。

缓存一致性协议是为了解决这个问题而设计的。它们的目标是确保在任何时刻，任何处理器读取的同一内存位置的值都是一致的。常见的缓存一致性协议包括MESI（Modified, Exclusive, Shared, Invalid）协议、MOESI（Modified, Owner, Exclusive, Shared, Invalid）协议和MSI（Modified, Shared, Invalid）协议。

3.2 选择题

I. RAM是易失性存储器，ROM是非易失性存储器。这个叙述是正确的。RAM（随机存取存储器）中的数据在断电后会丢失，所以它是易失性的。而ROM（只读存储器）中的数据在断电后仍然保留，所以它是非易失性的。

Ⅱ. RAM 和 ROM 都采用随机存取方式进行信息访问。这个叙述也是正确的。RAM和ROM都是随机存取存储器，可以直接访问存储器中的任何位置。

Ⅲ. RAM和ROM 都可用作cache。这个叙述是错误的。通常情况下，缓存（cache）是使用SRAM（静态随机存取存储器）而不是RAM或ROM实现的。SRAM比RAM更快，但成本更高。ROM由于是只读的，所以不能用作缓存。

Ⅳ. RAM 和 ROM 都需要进行刷新。这个叙述也是错误的。只有DRAM（动态随机存取存储器）需要刷新。SRAM（静态随机存取存储器）和ROM都不需要刷新。

选A
ROM芯片：每个ROM芯片的容量是2KB，需要的ROM总容量是4KB，所以需要2个ROM芯片。

RAM芯片：每个RAM芯片的容量是4KBx4位=2KB，需要的RAM总容量是64KB-4KB=60KB，所以需要30个RAM芯片。

所以，需要的ROM芯片数和RAM芯片数分别是2和30。

选D
根据 DRAM的结构和原理可知，在分时复用的情况下，芯片引脚个数取决于行地址线和列地址线中的较大值，对于一个2K×1位的DRAM芯片，总共需要11条地址线，只有当一个取5，一个取6时可使管脚数最小，而DRAM的刷新开销取决于行数，因此行地址线应该为5、列地址线为6，即行数2⁵=32，列数为2⁶=64。

选C
每个访存地址对应的存储模块序号（ 0,1,2,3 ）如下所示：

访存地址 8005 8006 8007 8008 8001 8002 8003 8004 8000

模块序号 1 2 3 0 1 2 3 0 0

其中，模块序号 = 访存地址 % 存储器交叉模块数。

判断可能发生访存冲突的规则是：给定的访存地址在相邻的四次访问中出现在同一个存储模块内。据此，根据上表可知 8004 和 8000 对应的模块号都为 0 ，即表明这两次的访问出现在同一模块内且在相邻的访问请求中，满足发生冲突的条件。

选D
A. EPROM（可擦除可编程只读存储器）：它是一种随机存取的存储器，可以直接访问存储器中的任何位置。

B. CDROM（只读光盘存储器）：它是一种顺序存取的存储器，数据的读取需要按照物理位置的顺序进行。

C. DRAM（动态随机存取存储器）：它是一种随机存取的存储器，可以直接访问存储器中的任何位置。

D. SRAM（静态随机存取存储器）：它也是一种随机存取的存储器，可以直接访问存储器中的任何位置。

所以，不采用随机存取方式的存储器是CDROM。

选B
这里的循环指令本身具有时间局部性，它对数组a的访问具有空间局部性，选A。
在这个问题中，Cache有4个行，采用2路组相联映射方式，所以有2个组，每个组有2个行。主存地址依次为0，4，8，2，0，6，8，6，4，8。
- 首先，主存地址0，4，8，2依次访问，由于Cache初始为空，所以这4次访问都是缺失，Cache的内容变为：
  
  组0：2，0 组1：4，8
- 然后，主存地址0被访问，命中Cache，Cache的内容不变。
- 接着，主存地址6被访问，缺失，由于组0已满，需要替换，采用LRU替换算法，替换最久未使用的行，也就是行0，Cache的内容变为：
  
  组0：6，2 组1：4，8
- 然后，主存地址8被访问，命中Cache，Cache的内容不变。
- 接着，主存地址6被访问，命中Cache，Cache的内容不变。
- 然后，主存地址4被访问，缺失，由于组1已满，需要替换，采用LRU替换算法，替换最久未使用的行，也就是行8，Cache的内容变为：
  
  组0：6，2 组1：4，0
- 最后，主存地址8被访问，缺失，由于组1已满，需要替换，采用LRU替换算法，替换最久未使用的行，也就是行0，Cache的内容变为：
  
  组0：6，2 组1：8，4
选C
通过将指令Cache和数据Cache分离，可以在同一时钟周期内同时从指令Cache获取指令和从数据Cache获取数据，从而减少资源冲突，提高处理器的执行效率。

选D
如果TLB命中，说明找到了虚拟地址对应的物理地址。如果Cache命中，说明在Cache中找到了需要的数据。这两者都说明数据已经在内存中，所以Page不可能未命中。如果Page未命中，说明数据不在内存中，这与TLB和Cache的命中矛盾。

D
缺页中断和普通中断的区别之一就是缺页中断是在指令执行过程中，而普通中断是在指令执行结束完成的一小段中断检测间隔内，所以处理完缺页中断应该是回到发生缺页的指令。

D

访存地址	8005	8006	8007	8008	8001	8002	8003	8004	8000
模块序号	1	2	3	0	1	2	3	0	0

3.3 简答题

层次化存储体系的设计旨在实现两大目标：首先，它旨在弥补高速CPU与相对慢速的主存之间的性能差距；其次，它旨在解决主存容量有限的问题。

存储系统的分级结构主要由三级构成，即Cache、主存以及辅助存储器。这一结构建立在时间局部性原理与空间局部性原理的基础之上。Cache与主存之间的存储层次主要解决了主存速度不足的问题，使得CPU能够更高效地访问数据；而主存与辅助存储器之间的存储层次则解决了主存容量受限的问题，实现了更大容量的数据存储与访问。
电容C上的电荷会逐渐泄漏，数据只能保存较短的时间。为避免数据丢失，必须定期采用类似读操作的方式对存储单元补充电荷，这个过程称为刷新，这也是动态 RAM 得名的原因。

刷新方式：集中刷新、分散刷新和异步刷新。前者存在CPU死时间；分散刷新由于刷新次数过多，降低了存储器的速度；异步刷新是前两者的折中。
多体交叉存储器由多个存储模块构成，这些模块的容量和存取速度相同，具有各自独立的地址寄存器、地址译码器、驱动电路和读写控制电路。根据对多各模块编址方式的不同，又可分为高位多体交叉和低位多体交叉两种方式。
1. 高位交叉：按存储器地址的高位地址划分模块，同一存储体内的地址是连续的。当多个目标同时访问存储器时(如CPU和DMA设备同时访问存储器)，如果访问的地方范围处于不同的存储芯片，则提供并行访问。
2. 低位交叉：按存储器地址的低位地址划分模块，同一存储体内的地址不相邻，相邻地址处在不同存储体中。CPU可同时启动多个存储体，并进行并行访问。
1. 先进先出算法(FIFO)
基本思想：按照数据块进入Cache的先后决定替换的顺序，即在需要进行替换时，选择最先被调入Cache中的块作为替换块。这种方法要求为每块记录它们进入Cache的先后次序。
优点：FIFO算法系统开销较小。
缺点：是不考虑程序访问的局部性，可能会把一些需要经常使用的块（如循环程序块）也作为最早进入Cache的块而替换掉，因此，可能导致Cache的命中率不高。
1. 近期最少使用(LRU)算法
基本思想：将近期内长久未被访问过的行换出。为此，每行设置一个计数器，cache每命中一次，命中行计数器清零，其它各行计数器增1，因此它是未访问次数计数器。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。
优点：这种算法显然保护了刚调入Cache的新数据，符合cache工作原理，因而使cache有较高的命中率。LRU算法硬件实现简单
1. 最不经常使用(LFU)算法
基本思想：将一段时间内被访次数最少的那行数据换出。为此，每行设置一个计数器，新调入行的数据从0开始计数，每访问一次被访行的计数器增1。当需要替换时，对这些特定行的计数值进行比较，将计数值最小的行换出。
缺点：一段期间访问情况不能严格反映近期访问情况。例如特定行中的A、B两行，A行在期间的前期多次被访问而后期未被访问，但累积计数值很大，B行是前期不常用而后期却正被频繁访问，但可能由于累积计数小于A行而被LFU算法换出了。
1. 随机替换算法
基本思想：需要进行替换时，从特定的行位置中随机地选取一行进行替换。

优点：硬件实现最容易，而且速度也比前几种策略快。
缺点：随意换出的数据很可能马上又要用，从而降低命中率和cache工作效率。但这个负面效应随着cache容量增大会减少，模拟研究表明随机替换策略的功效只是稍逊于LFU和LRU。

3.4 画图题

用4片32Kx8位SRAM存储芯片可设计哪几种不同容量和字长的存储器?画出相应设计图并完成与CPU连接

可分别设计

128K×8位

64K×16位

32K×32位

3.5 画图题

用32Kx8位RAM芯片和64Kx4位ROM芯片，设计256Kx8位存储器。其中，从30000H到3FFFFH地址空间为只读存储区，其他为可读、可写存储区。完成存储器与CPU连接。

3.6 画图题

某计算机字长16位，主存容量128KB，请用16Kx8位的静态RAM芯片和32Kx16位的ROM芯片，为该机设计一个主存储器。要求18000H~1FFFFH为ROM区，其余为RAM区，画出存储器结构及其与CPU连接的框图

3.7 分析空间局部性和时间局部性

(1) 对于数组访问的时间局部性和空间局部性：

代码A：在代码A中，数组是按行优先顺序访问的，这与数组在内存中的存储方式相匹配。因此，代码A具有很好的空间局部性，因为它连续访问内存地址。每个元素被访问后立即使用，不存在时间局部性。
代码B：在代码B中，数组是按列优先顺序访问的，这与数组在内存中的存储方式不匹配。因此，代码B的空间局部性较差。每个元素被访问后立即使用，不存在时间局部性。

(2) 对于变量sum的时间局部性和空间局部性：

在两段代码中，变量sum都被频繁地读取和写入，因此它具有很好的时间局部性。由于sum是一个单一的变量，因此它的空间局部性并不重要。

(3) 对于for循环体对指令访问的时间局部性和空间局部性：

在两段代码中，for循环体都被反复执行，因此它们具有很好的时间局部性。由于for循环体中的指令集较小，并且被连续执行，因此它们也具有很好的空间局部性。