11月2日笔记

页表放在主存DRAM中，因此每次cache缺失，都需要访问主存两次，第一次先访问获得物理地址，第二次获得数据，速度慢，如何最小化访存的代价，从而提升系统性能，1、DRAM和cache之间传输所用的基本单位为块，而不是字，这里利用了空间局部性原理；2、对常用的页表项使用缓存

块和页的区别：在cache中我们处理单独的块，在现代系统中，通常大小为64字节，而在虚拟存储器中，我们处理单独的页，通常大小为4K字节

16K字节的DRAM，对于虚拟存储器来说，页容量为4K字节，对于cache来说，块大小为128字节，对于取数、存数指令来说，字大小为4字节，首先16字节的DRAM，按照页来划分，划分成4页，其中每一页按照块来划分，划分成32块，其中每块由32个字组成

每个进程都有一个单独的页表，页表的每一项都有一个对应的有效位，有效位表示的是物理页号是否有效，另外每一项都有一个标志位，指明页是在DRAM中，还是在磁盘中

首先通过虚拟页号检索到页表中对应的项，然后检查有效位，如果有效位为1，则有效，检查页在DRAM中还是在磁盘中，如果所需要的页在DRAM中，可以通过页表得到物理地址，并且到主存中访问数据，如果所需要的页在磁盘中，需要分配新的页到DRAM中，如果主存中没有容量了，则将DRAM中原来的页替换掉，把被替换的页存回到磁盘中，从磁盘中加载需要的页到主存中，通过物理地址进行读写数据，如果有效位为0，则表明无效，分配新的页到DRAM中，后两种情况称为缺页，需要把控制权交给操作系统来处理，当没有足够的内存可以分配的时候，DRAM分配函数malloc会返回空指针，当内存不足的时候，需要将老的页替换掉，原来主存中的页如何存回磁盘？在虚拟存储器中，应该采用写直达，还是写回机制呢，DRAM像是磁盘的cache，是否能够每次都同步更新磁盘和主存的内容，还是当该页要被替换的时候，再写回到磁盘中去呢，一般来说，由于写时间太长，因此在虚拟器存储系统中，都采用写回机制

减少页表所需的存储量：1、增加页的大小，如果页的大小变成原来的2倍，则页表存储量就能减少到原来的二分之一；缺点是浪费内存；2、使用多级页表，由于大部分程序都只会使用虚拟内存空间的一小部分，因此risc-v使用多级页表来有效减少页表存储量

多级页表允许使用一种稀疏的方式来使用虚拟地址空间，而不用分配整个页表

8.3 地址变换高速缓存I——快表以及简单介绍I/O设备

首先对比一下cache和虚拟存储器，在cache中存储信息的最小单位是块或行，而在虚拟存储器中是页，在cache中找不到所需要的数据，我们称为缺失，或者脱靶，而在虚拟存储器中，我们称为缺页，cache中块大小通常在32~64字节，页大小通常为4K～8K字节，对于cache来说，可以选择直接映射，N路组相联，或者全相联，而虚拟存储器中，采用的是全相联的方案，Cache采用的替换策略一般选择LRU或者随机法，而虚拟存储器中，一般使用LRU法，cache一般采用写直达，或者写回机制，而虚拟存储器中，采用写回机制

每条指令和每个数据的访问都需要地址转换和保护检查，利用地址转换把虚拟地址转换成物理地址，根据处理器当前模式等信息，来进行保护检查，从而实现对当前指令或数据的保护，一个好的虚拟存储器设计方案，应该是快速且空间利用率高，接下来介绍一种特殊的地址转换cache，称为地址变换高速缓存，简称快表，TLB

地址转换所付出的代价非常大，对于单级页表来说，每次访问数据需要访问主存两次，而对于一个二级页表来说，每次访问数据需要访问主存三次

提高访问效率的关键在于：利用页表的访问局部性，将一些最近使用过的地址变换在TLB表中进行缓存，如果TLB表命中，则利用TLB中的物理页号，进行物理地址转换，加快速度，如果TLB缺失，则需要到页表中将地址变换的结果重新加载到TLB表中

TLB中每一项都有有效位，脏位，标记，以及物理页号PPN所组成，每次访问都需要在TLB中通过和标记比较来寻找虚拟页号VPN，一旦命中，则通过物理页号和页内偏移，得到所需要的物理地址

TLB的设计：通常由32128项组成，通常采用全相联设计方案，每一项映射到一个容量比较大的页，页与页之间的空间局部性很小，因此更有可能发生两个项之间的冲突，有时候更大的TLB，例如由256512项，可能采用4~8路组相联设计，更大的系统有时候采用多级TLB

由于在全相联的情况下，使用LRU替换策略需要的代价很大，而TLB的缺失比缺页要频繁的多，因此需要用较低的代价来处理缺失，TLB中常用的替换策略是随机法，或者先入先出法

TLB覆盖范围：TLB能够同时映射的最大虚拟地址空间的大小

TLB位于？应该首先检查cache还是TLB？当需要的数据的对应页不在物理存储器中的时候，cache无法保存所需要的数据，如果先检查TLB，cache收到的是物理地址，首先处理器产生虚拟地址，TLB根据虚拟地址的虚拟页号判断TLB是否命中，如果TLB命中，则得到物理地址，如果TLB缺失，则到页表中获取要查找页的物理地址，并且加载到TLB表项中，根据物理地址到cache中寻找所需要的数据，如果cache命中，则返回数据到处理器，如果cache缺失，则到主存中读取数据，并且加载数据到cache中，最终同样返回需要的数据到处理器

注意，TLB实现虚拟地址到物理地址的转换，而不是页表

TLB进行地址转换的过程：虚拟地址划分为页内偏移和虚拟页号，其中虚拟页号低位作为TLB索引，高位作为TLB的标记，如果TLB采用全相联，则索引位为0比特，使用TLB索引在TLB中寻找对应的组，然后对比该组内所有的标记，和TLB标记，找到对应的物理页号以后，与虚拟地址的页内偏移拼接，从而得到物理地址，物理地址有两种划分方式，在利用物理地址来查找数据的时候，物理地址被划分为标记、索引、偏移三个部分，然后根据其中的索引域，在cache中查找对应的组，值得注意的是，这里物理地址的TIO划分，与虚拟地址中的TIO划分是没有关联的

在流水线中，与虚拟存储器有关的器件，在取指令和访问存储器的时候，可能会产生TLB缺失，缺页，或者违反保护，TLB缺失需要硬件或者软件机制来重新填充TLB，通常在硬件中完成

违反保护可能会终止进程

通过硬件方式来解决TLB缺失的硬件单元，我们称为页表Walk，一旦指令TLB，或者数据TLB产生TLB缺失时，通过页表walk，到物理存储器中读取页表，来获得物理地址

地址转换过程的流程如下：虚拟地址到TLB中进行查找，如果TLB缺失，就使用硬件或软件方式来解决，如果该页不在物理存储器中，则缺页异常，如果该页在物理存储器中，就加载物理地址，更新TLB表的内容，如果TLB命中，则进行保护检查，如果禁止访问，则产生段错误，如果允许访问，则根据物理地址到cache中查找所需要的数据

现代的虚拟存储器系统，提供了一种错觉，每个进程都有很大的单独的存储空间，虚拟存储器能够在不同的用户或者进程之间提供隐私保护，每个用户或者进程都有自己的私有地址空间，不会被干扰，我们需要将内存进行分页，能够允许跑很大的应用程序，甚至比主存的容量还大，都可以运行，同时还隐藏了机器配置上的差异，所要付出的代价是在每次访存的时候，都要将虚拟地址转换成物理地址

虚拟存储器的性能如何？虚拟存储器在虚拟器存储结构中，位于主存的下一层，TLB在cache之前被访问，但会影响从磁盘到主存的数据传输，以前我们假设主存是最低的层次，现在不得不考虑还要访问磁盘，相同的CPI、AMAT公式都适用，只是现在要将主存看做是一个中间层的缓存

在处理器和主存之间采用cache，块大小为32字节，cache缺失率为1%~20%之间，cache命中时间为1个时钟周期，cache缺失代价为100个时钟周期

而采用主存作为磁盘的cache，需要进行分页，每页为4K字节，页缺失率不到0.001%，命中时间为100个时钟周期，缺失代价为500万个时钟周期，可见缺页的代价非常大

分页所需要的存储访问时间：L1cache命中时间位1个时钟周期，L2cache命中时间为10个时钟周期，DRAM和磁盘的访问时间分别为200个时钟周期和20M个时钟周期，

不采用分页的时候，所需要的平均存储器访问时间为：L1cache命中时间，加上L1cache缺失率乘上L2cache命中时间，加上L1cache缺失率乘上在1级cache缺失的基础上二级cache缺失率乘上二级cache缺失代价，得到5.5个时钟周期

采用分页以后的平均访存时间：不使用分页的访存时间基础上，增加一级cache、二级cache DRAM中都缺失的概率，乘上缺失代价，如果在cache中缺失后，在DRAM中命中率为99%，则计算所得的AMAT为4005.5个时钟周期，比不使用分页的慢了728倍，也就是说20000次访存中，有一次需要从磁盘中读取数据，本来需要10s的时间，现在需要约2个小时，如果在cache中缺失后，在DRAM中命中率为99.9%，则AMAT为405.5个时钟周期，如果在cache中缺失后，在DRAM中命中率为99.9999%，则AMAT为5.9个时钟周期

随着命中率变高，所需平均访问时间越少，性能越高

8.4 地址变换高速缓存II——上下文切换

单个处理器如何同时运行多个程序，解决方法：使用上下文切换，上下文切换通过更改处理器内部的状态，在不同进程之间进行切换，通过保存寄存器值，和PC指针，并且改变管理者页表基址寄存器中的值，来保存和切换进程的状态

TLB？当前的项要用于不同的进程，因此在上下文切换的时候，将所有项的有效位都设成无效

在计算机系统中，分成硬件和软件两个部分，在硬件上按照计算机规模，大到仓储规模计算机，如超级计算机，小到智能手机，计算机由中央处理器，存储器，输入输出组成，

输入输出系统：包括各种IO设备，比如显示器，键盘，外部存储器等

如何连接这些设备？假设一个程序在处理器上运行，如何与外界通信联系，需要具备和磁盘、网络、鼠标、显示器等设备连接的IO接口，接口的作用是连接到多种设备，控制这些设备，响应它们并传输数据，将它们呈现给用户数据，

处理器必须为IO做些什么？

输入：读取一个字节序列，

输出：写入一个字节序列

以下两种方法来寻址设备，1、特殊的输入输出指令和硬件；2、内存映射IO的方式

内存映射IO是将地址空间的一部分专门分配给IO设备，用普通的读写操作，比如lw、sw对这些地址的读写，会被设计为对IO设备的指令，在RISC-V中是很常用的方法

内存中某些地址不是常规的地址，而是对应于IO设备的寄存器，用于控制和数据传输

处理器的速度比IO设备快得多，造成两者速度的不匹配，例如1GHz微处理器的数据吞吐率为4G字节每秒，而典型的IO设备的数据吞吐率峰值与之相差也很远

因此要根据IO设备的速率选择合适的机制，常见的机制有轮询、中断、直接内存访问（DMA）

轮询需要周期性检查状态寄存器的值是否改变，中断指示处理器某个设备需要被关注，DMA是一种更加适合高性能设备的方案，DMA不需要处理器参与，能够直接在内存和IO设备之间进行数据传输

第九章 并行性

9.1单指令流多数据流SIMD

数据集并行，应用：例如在机器学习领域，输入一张图片到神经网络中，经过若干卷积层，或者全连接层，得到物体识别的效果

经过若干卷积层或全连接层，得到图像中物体识别的结果，在神经网络中，卷积层和全连接层的运算占了总运算量的绝大部分，有时达到90%以上，卷积层和全连接层的计算的实质是矩阵-向量乘法

相关问题就是矩阵乘法，矩阵乘法在很多工程数据、图像处理任务中都是基本的操作，同时在图像滤波、降噪、机器学习上也有广泛应用，在立体视觉上，也有很多和矩阵乘法非常类似的运算操作，由于矩阵乘法的应用相当广泛，因此在很多函数库中都有现成的函数可以调用，如dgemm，是双精度浮点矩阵乘法函数

矩阵乘法：