计算机体系结构存储系统

存储系统原理

两种典型的存储系统：Cache存储系统和虚拟存储系统。前者主要目的是提高存储器速度，后者有主存储器和硬盘构成，主要用于扩大存储器容量。
在这里插入图片描述

存储系统的访问效率

$e=\frac{T_1}{T}=\frac{1}{H+(1-H)\times\frac{T_2}{T_1}}=f(H,\frac{T_2}{T_1})$
可见访问效率主要与命中率和两级存储器的速度之比有关，访问效率实际上是表示存储系统访问速度能到达系统中访问较快组件的百分之多少。

交叉访问存储器

高位交叉访问存储器

在这里插入图片描述

低位交叉访问存储器

用概率刻画访问冲突问题

共有 $n$ 个存储体，每个存储周期只能取到 $k$ 个有效字，其余 $n - k$ 个存储体有冲突。假设 $p (k)$ 是 $k$ 的概率密度函数PDF， $k$ 的平均值为：
$N=\sum_{k=1}^{n}k\times p(k)$
$N$ 是每个存储周期内能够访问到的平均有效字个数，通常称为并行存储器的加速比。

定义转移成功的概率为 $g$ ，即读出的是转移指令且转移成功的概率。我们有 $p(k)=(1-g)^{k-1}g, k=1,2,···,n-1$ ，前 $(k - 1)$ 个字不是转移指令或者是不成功的转移指令，第 $k$ 个字是转移指令且成功转移。

加速比可以通过以下方式计算：
$N=g+2(1-g)g+3(1-g)^2g+...+(n-1)(1-g)^{n-2}g+n(1-g)^{n-1}$

这是一个等差 $\times$ 等比数列求和问题（梦回高中）。

首先乘上等比数列的比 $(1 - q)$ ，得
$1-g)N=(1-g)g+2(1-g)^2g+3(1-g)^3g+...+(n-1)(1-g)^{n-1}g+n(1-g)^{n}$

和原式作差（注意最后一项形式是不同的（少了 $g$ ）不能相减）得
$N-(1-g)N=[g+(1-g)g+(1-g)^2g+...+(1-g)^{n-2}g]+n(1-g)^{n-1}-n(1-g)^{n}-(n-1)(1-g)^{n-1}g$

前面一部分利用等比数列求和公式 $S_n=\frac{a_1-a_nq}{1-q}$ ，进行求和得到
$gN=[\frac{g-(1-g)^{n-1}g}{1-(1-g)}]+n(1-g)^{n-1}-n(1-g)^{n}-(n-1)(1-g)^{n-1}g$
$gN=1-(1-g)^{n-1}+n(1-g)^{n-1}-n(1-g)^{n}-(n-1)(1-g)^{n-1}g$

进行合并同类项可得
$gN=1+(n-1)(1-g)^{n-1}-n(1-g)^{n}-(n-1)(1-g)^{n-1}g$
$gN=1+(n-1)(1-g)^{n}-n(1-g)^{n}$
$gN=1-(1-g)^{n}$

最终得到
$N=\frac{1-(1-g)^{n}}{g}$

通过打表查看，加速比和存储体个数以及程序转移概率之间的关系，由于转移指令的存在，实际的加速比大受限制。
在这里插入图片描述

虚拟存储器

多级页表

在这里插入图片描述
保证最后一级页表可以容纳所有虚实页号之间的映射：
$2^g\times\frac{N_p}{N_d}\geq\frac{N_v}{N_p}$
取对数得
$g(log_2N_p-log_2N_d)\geq(log_2N_v-log_2N_p)$
最小满足以上条件的 $g$ 为 $\lceil\frac{log_2N_v-log_2N_p}{log_2N_p-log_2N_d}\rceil$ 。