SchoolWork-LaTeX/计算机系统结构/平时作业/第五章作业1.tex
423A35C7 5906ac1efc 重构目录层次
0-课程笔记
1-平时作业
2-实验报告
3-期末大作业
2024-09-02 18:32:58 +08:00

363 lines
21 KiB
TeX
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

\documentclass[全部作业]{subfiles}
\input{mysubpreamble}
\setcounter{chapter}{4}
\begin{document}
\chapter{大而快:层次化存储}
\begin{enumerate}
\questionandanswer[5.2]{
cache对于为处理器提供高性能存储器层次结构非常重要。下面是64位存储器地址访问顺序列表以字地址的形式给出。
\mint{C}|0x03, 0xb4, 0x2b, 0x02, 0xbf, 0x58, 0xbe, 0x0e, 0xb5, 0x2c, 0xba, 0xbd|
}{}
\begin{enumerate}
\questionandanswer[5.2.1]{
[ 10 ]<5.3>对于一个有16个cache块、每个块大小为1个字的cache标识这些引用的二进制字地址、标签和索引。此外假设cache最初为空列出每个地址的访问会命中还是失效。
}{
缓存块有16个也就是$2^{4}$所以索引的大小为4个位给出的地址为两个十六进制位即8位二进制所以索引实际上就是低4位地址标签实际上是就是高4位地址是否命中只需要看在某一行之前是否出现过相同的标签和索引。
\includexopp[1.5]{5.2.1.1}
}
\questionandanswer[5.2.2]{
[ 10 ]<5.3>对于一个有8个cache块、每个块大小为2个字的cache标识这些引用的二进制字地址、标签、索引和偏移。此外假设cache最初为空列出每个地址的访问会命中还是失效。
}{
每个缓存块的大小变大了,缓存块的数量变小了,所以偏移实际上就是把索引的最低位移过来了。同样是否命中只需要看在某一行之前是否出现过相同的标签和索引,并且在这之后没有索引相同但标签不同的访问(不然就被置换了),不需要考虑偏移。这里的命中一列,不命中使用$\times $表示,而命中使用〇表示(用〇比√从视觉上更好区分)。
\includexopp[1.5]{5.2.2.1}
}
\questionandanswer[5.2.3]{
[ 20 ]<5.3,5.4>请针对给定的访问顺序优化cache设计。这里有三种直接映射cache的设计方案,每种方案都可以容纳8个字的数据:
\begin{itemize}
\item C1的块大小为1个字
\item C2的块大小为2个字
\item C3的块大小为4个字
\end{itemize}
}{
\includexopp[1.5]{5.2.3.1}
可见C2的缓存命中次数最多所以这里应该选择C2方案。
}
\end{enumerate}
\questionandanswer[5.3]{
按照惯例, cache 以它包含的数据量来进行命名例如4KiB cache可以容纳4KiB的数据但是cache还需要SRAM来存储元数据如标签和有效位等。本题研究cache的配置如何影响实现它所需的SRAM总量以及cache 的性能。对所有的部分都假设cache是字节可寻址的并且地址和字都是64位的。
}{}
\begin{enumerate}
\questionandanswer[5.3.1]{
[ 10 ]<5.3>计算实现每个块大小为2个字的32KiB cache 所需的总位数。
}{
32KiB即$2^{5}\times 2^{10}=2^{15} \text{B}$每个块大小为2个字即$2\times 64 / 8=2^{4}\text{B}$由于字节寻址所以偏移为4位共有$2^{15-4}=2^{11}$个块因此索引为11位那么地址为64位所以标签就是$64-4-11=49$有效位为1位。每个块都有一个标签和一个有效位所以SRAM存储的元数据需要$2^{11}\times (49+1) = 102400$位。再加上存储数据的$2^{15+3}$位,即\boldkai{$\bm{2^{11}\times (49+1) + 2^{15+3} = 364544}$}
}
\questionandanswer[5.3.2]{
[ 10 ]<5.3>计算实现每个块大小为16个字的64KiB cache所需的总位数。这个cache 比 5.3.1中描述的32KiB cache大多少?(请注意通过更改块大小我们将数据量增加了一倍但并不是将cache的总大小加倍。)
}{
64KiB即$2^{6}\times 2^{10}=2^{16}\text{B}$每个块的大小为16个字即$16\times 64/8=2^{7}$B所以偏移为7位。
共有$2^{16-7}=2^{9}$个块索引为9位。
标签为$64-7-9 = 48$有效位为1位。
所以需要的总位数为$2^{9}\times (48+1)+2^{16+3} = \bm{549376}$比5.3.1大了$\frac{549376-364544}{364544} = 0.507022471910112$,即约大了$\bm{50.70\%}$
}
\questionandanswer[5.3.3]{
[ 5 ]<5.3>解释为什么5.3.2中的64KiB cache尽管数据量比较大但是可能会提供比5.3.1中的cache更慢的性能。
}{
5.3.2中的64KiB cache每个块的大小比5.3.1大,所以每次缓存失效时都需要把更多的数据读入缓存或写回存储,所以失效代价会更大。而且总块数更少,所以命中率会更低。
}
\questionandanswer[5.3.4]{
[ 10 ]<5.3,5.4>生成一系列读请求这些请求需要在32KiB的两路组相联cache上的失效率低于在5.3.1中描述的cache的失效率。
}{
在5.3.1中标签49位索引11位偏移4位。若改成两路组相联那么每个块就只有1个字了且索引为10位标签为50位每个块都各自有一个标签和一个有效位。所以只需要构造索引相同的地址但是标签不同即可让5.3.1的直接映射失效,而两路组相联不失效。所以构造的读请求地址如下:\boldkai{0x00000, 0x10000, 0x00000, 0x10000, 0x00000, 0x10000, ……},前两次请求都未命中缓存,但从第三次请求开始,直接映射会一直失效,而两路组相联会一直命中,所以符合要求。
}
\end{enumerate}
\questionandanswer[5.5]{
对一个64位地址的直接映射cache的设计地址的以下位用于访问cache。
\begin{center}
\begin{tabular}{ccc}
\toprule
标签 & 索引 & 偏移 \\
\midrule
$63 \sim 10$ & $9\sim 5$ & $4\sim 0$ \\
\bottomrule
\end{tabular}
\end{center}
}{}
\begin{enumerate}
\questionandanswer[5.5.1]{
[ 5 ]<5.3>cache 块大小为多少(以字为单位)?
}{
偏移是0到4也就是5位所以cache块的大小是$2^{5}=32$B一个字是4B所以cache块的大小是\boldkai{8}个字。
}
\questionandanswer[5.5.2]{
[ 5 ]<5.3 >cache块有多少个?
}{
索引从5到9也就是5位所以cache块有$2^{5}=\bm{32}$个。
}
\questionandanswer[5.5.3]{
[ 5 ]<5.3>这种cache实现所需的总位数与数据存储位之间的比率是多少?
}{
标签是10到63也就是54位还需要一位有效位所以实现所需的总位数是$2^{5}\times (54+1)+2^{5}\times 2^{5} \times 8 = 9952$,数据存储位是$2^{5}\times 2^{5}\times 8 = 8192$。所以这种cache实现所需的总位数与数据存储位之间的比率是$\frac{9952}{8192}\times 100\% = \bm{121.484375\%}$
}
\questionandanswer[5.5.4]{
下表记录了从上电开始cache访问的字节地址。
\begin{center}
\begin{tabular}{cccccccccccccc}
\toprule
十六进制 & 00 & 04 & 10 & 84 & E8 & A0 & 400 & 1E & 8C & C1C & B4 & 884 \\
\midrule
十进制 & 0 & 4 & 16 & 132 & 232 & 160 & 1024 & 30 & 140 & 3100 & 180 & 2180 \\
\bottomrule
\end{tabular}
\end{center}
[ 20 ]<5.3>对每一次访问,列出:它的标签、索引和偏移;指出命中还是失效;替换了哪个字节(如果有的话)。
}{
\includexopp[1.5]{5.5.4.1}
图中的Address表示十六进制的地址Tag为标签,Index为索引Offset为偏移Hit列中勾表示命中叉表示失效Sub表示替换的字节地址范围。
}
\questionandanswer[5.5.5]{
[ 5 ]<5.3>命中率是多少?
}{
12次访问中有4次命中所以命中率为$\frac{1}{3} \approx \bm{33.33}\%$
}
\questionandanswer[5.5.6]{
[ 5 ]<5.3>列出cache的最终状态每个有效表项表示为<索引,标签,数据>的记录。例如:
\mint{C}|<0, 3, Mem[0xC00]-Mem[0xC1F]|
}{}
{\kaishu
对于某个索引从后往前看Index首次找到这个索引的地方所在的标签即为最终状态的标签之后把偏移全填为0再把地址转成十六进制已按4位一组用蓝色线分隔即为起始地址把偏移量全填为1再把地址转成十六机制即为结束地址。
例如对于0号索引最后一次出现是在地址C1C的地方它的标签为11也就是十六进制的3。之后看这一行的地址为 11\!|\!00 000\!|\!1 1100将偏移量全填成0也就是 11\!|\!00 000\!|\!0 0000这就是0xC00将偏移量全填成1也就是 11\!|\!00 000\!|\!1 1111这就是 0xC1F所以结果为 \mintinline{C}{<0, 3, Mem[0xC00]-Mem[0xC1F]}
所以cache的最终状态如下
\begin{minted}{C}
<0, 3, Mem[0xC00]-Mem[0xC1F]>
<4, 2, Mem[0x880]-Mem[0x89F]>
<5, 0, Mem[0x0A0]-Mem[0x0BF]>
<7, 0, Mem[0x0E0]-Mem[0x0FF]>
\end{minted}
}
\end{enumerate}
\questionandanswer[5.7]{
考虑以下的程序和cache行为:
\begin{center}
\begin{tabularx}{\linewidth}{ZZZZZ}
\toprule
每1000条指令的数据读次数 & 每1000条指令的数据写次数 & 指令cache失效率 & 数据cache失效率 & 块大小(字节) \\
\midrule
250 & 100 & 0.30\% & 2\% & 64 \\
\bottomrule
\end{tabularx}
\end{center}
}{}
\begin{enumerate}
\questionandanswer[5.7.1]{
[ 10 ]<5.3,5.8>假设一个带有写直达、写分配cache的CPU实现了2的CPI那么RAM和cache之间的读写带宽用每个周期的字节数进行测量是多少?(假设每个失效都会生成一个块的请求。)
}{
CPI为2每条指令2个周期那么每个周期就是0.5条指令,那么指令的读带宽就是$0.5\times 0.30\% \times 64 = 0.096$字节/周期,而数据的读带宽就是$0.5\times \frac{250}{1000}\times 2\%\times 64 = 0.16$字节/周期。
% $$
% 0.5\times 0.30\% \times 64 + 0.5\times \frac{250}{1000}\times 2\%\times 64 = 0.256 \text{字节/周期}
% $$
由于写直达所以不管是否失效都需要将某个寄存器的数据写入到RAM中RISC-V中的寄存器为64位也就是8个字节那么写入RAM的带宽为$0.5\times \frac{100}{1000}\times 8 = 0.4$字节/周期。
由于写分配,所以当失效时,需要先(后*将RAM中的数据放回到寄存器中这时会产生读带宽$0.5\times \frac{100}{1000}\times 2\%\times 64 = 0.064$字节/周期。
*如果先取回数据那么需要同时写入cache和RAM如果后取回数据那么就只写入RAM取回时就已经是最新的数据了。
所以总的读带宽为
$
0.096+0.16+0.064 = \bm{0.32} \text{字节/周期}
$
总的写带宽为
$
\bm{0.4} \text{字节/周期}
$
}
\questionandanswer[5.7.2]{
[ 10 ]<5.3,5.8>对于一个写回、写分配 cache来说假设替换出的数据cache块中有30\%是脏块那么为了实现CPI为2读写带宽需要达到多少?
}{
指令的读带宽仍为0.096字节/周期数据的读带宽仍为0.16字节/周期。但是这里的“写分配”似乎没用写的时候如果不失效那cache中就是最新的如果失效那先替换旧的块之后再写入cache也不会出现分配的情况。
对于写回策略当写不失效时不需要在cache与RAM中传输数据。当写失效时如果被替换的cache块是“脏”块也就是被修改过那么需要将这个块写入到RAM中。当读失效时仍然会产生cache块的替换所以如果是“脏”块也需要写入RAM。并且这里没有提及缓冲的事所以认为没有写缓冲那么写带宽为$0.5\times \left( \frac{250}{1000}+\frac{100}{1000} \right) \times 2\%\times 30\%\times 64 = 0.0672$
所以总的读带宽为$\bm{0.096}$字节/周期,总的写带宽为$\bm{0.0672}$字节/周期。
}
\end{enumerate}
\questionandanswer[5.9]{
cache块大小(B)可以影响失效率和失效延迟。假设一台机器的基本CPI为1每条指令的平均访问次数包括指令和数据为1.35给定以下各种不同cache块大小的失效率找到能够最小化总失效延迟的cache块大小。
\begin{center}
\begin{tabularx}{0.8\linewidth}{ZZZZZ}
\toprule
8:4\% & 16:3\% & 32:2\% & 64:1.5\% & 128:1\% \\
\bottomrule
\end{tabularx}
\end{center}
}{}
\begin{enumerate}
\questionandanswer[5.9.1]{
[ 10 ]<5.3>失效延迟为20$\times $B周期时,最优块大小是多少?
}{
总失效延迟为$1.35\times \text{失效率}\times 20\times B$周期,所以所求问题为
$$
\mathop{\arg\min}_{i}
\quad 1.35\times \text{失效率}_{i}\times 20\times B_i
$$
$$
\left\{ \left( B_i, \text{失效率}_{i} \right) \right\} = \{ (8,0.04), (16,0.03), (32,0.02), (64,0.015), (128,0.01) \}
$$
枚举可得
\begin{center}
\begin{tabular}{ccc}
\toprule
$B_i$ & $\text{失效率}_{i}$ & 总失效延迟 \\
\midrule
8 & 0.04 & 8.64 \\
16 & 0.03 & 12.96\\
32 & 0.02 & 17.28\\
64 & 0.015 & 25.92\\
128 & 0.01 & 34.56\\
\bottomrule
\end{tabular}
\end{center}
\boldkai{所以最优块大小是8。}
}
\questionandanswer[5.9.2]{
[10]<5.3>失效延迟为24+B周期时最优块大小是多少?
}{
总失效延迟为$1.35\times \text{失效率}\times (24+B)$周期,所以所求问题为
$$
\mathop{\arg\min}_{i}
\quad 1.35\times \text{失效率}\times (24+B)
$$
$$
\left\{ \left( B_i, \text{失效率}_{i} \right) \right\} = \{ (8,0.04), (16,0.03), (32,0.02), (64,0.015), (128,0.01) \}
$$
枚举可得
\begin{center}
\begin{tabular}{ccc}
\toprule
$B_i$ & $\text{失效率}_{i}$ & 总失效延迟 \\
\midrule
8 & 0.04 & 1.728\\
16 & 0.03 & 1.62 \\
32 & 0.02 & 1.512\\
64 & 0.015 & 1.782\\
128 & 0.01 & 2.052\\
\bottomrule
\end{tabular}
\end{center}
\boldkai{所以最优块大小是32。}
}
\questionandanswer[5.9.3]{
5.9.3[ 10 ]<5.3>失效延迟为定值时,最优块大小是多少?
}{
总失效延迟为$1.35\times \text{失效率}\times \text{定值}$,所以失效率越小,总失效延迟就越小,\boldkai{所以最优块大小是128。}
}
\end{enumerate}
\questionandanswer[5.10]{
本题研究不同cache容量对整体性能的影响。通常, cache访问时间与cache容量成正比。假设主存访问需要70ns并且在所有指令中有36\%的指令访问数据内存。下表显示了两个处理器P1和P2中每个处理器各自的L1 cache 的数据。
\begin{center}
\begin{tabular}{cccc}
\toprule
& L1大小 & L1失效率 & L1命中时间 \\
\midrule
P1 & 2 KiB & 8.0\% & 0.66 ns \\
P2 & 4 KiB & 6.0\% & 0.90 ns \\
\bottomrule
\end{tabular}
\end{center}
}{}
\questionandanswer[5.10.1]{
[ 5 ]<5.4>假设L1命中时间决定Pl和P2的时钟周期时间它们各自的时钟频率是多少?
}{
% 设P1的时钟周期频率为C1CPI为CPI
% % + C_1 \times CPI \times (1+0.36)\times 0.08 \times 70
% $$
% C_1\times CPI \times 0.36\% \times 2k = 0.66
% $$
P1$\frac{1}{0.66 \times 10^{-9}} \approx 1.515 \times 10^{9} \text{Hz}=1.515 \text{GHz}$
P2$\frac{1}{0.90 \times 10^{-9}} \approx 1.111 \times 10^{9} \text{Hz}=1.111 \text{GHz}$
}
\questionandanswer[5.10.2]{
[ 10 ]<5.4>P1和P2各自的AMAT (平均内存访问时间)是多少(以周期为单位)?
}{
这里的平均内存访问时间应该是每条指令的,而且是已知产生内存访问的情况下计算的,
% 所以应该为$36\% \times (0.66 + 8\% \times 70) \times 10^{-9}\times \frac{1}{0.66\times 10^{-9}} = 3.41454545454545$
所以为
$$
\text{P1:}\quad 1+8\% \times \left\lceil \frac{70}{0.66} \right\rceil = 9.56 \text{周期}
$$
$$
\text{P2:} \quad 1+6\%\times \left\lceil \frac{70}{0.90} \right\rceil = 5.68 \text{周期}
$$
}
\questionandanswer[5.10.3]{
[ 5 ]<5.4>假设基本CPI为1.0而且没有任何内存停顿那么P1和P2的总CPI是多少?哪个处理器更快?(当我们说“基本CPI为1.0”时意思是指令在一个周期内完成除非指令访问或者数据访问导致cache失效。)
}{
这里计算的总CPI仍然是每条指令的周期数但是并没有已知产生内存访问所以
$$
\text{P1:}\quad 1+ 8\% \times \left\lceil \frac{70}{0.66} \right\rceil +36\% \times 8\% \times \left\lceil \frac{70}{0.66} \right\rceil = 12.6416 \text{周期/指令}
$$
$$
\text{P2:} \quad 1+ 6\% \times \left\lceil \frac{70}{0.90} \right\rceil + 36\% \times 6\% \times \left\lceil \frac{70}{0.90} \right\rceil = 7.3648 \text{周期/指令}
$$
\boldkai{所以P2更快。}
}
\questionandanswer[]{
对于接下来的三个问题我们将考虑向P1添加L2 cache(可能弥补其有限的Ll cache容量)。解决这些问题时请使用上一个表中的Ll cache容量和命中时间。L2失效率表示的是其局部失效率。
\begin{center}
\begin{tabular}{ccc}
\toprule
L2大小 & L2失效率 & L2命中时间 \\
\midrule
1 MiB & 95\% & 5.62 ns \\
\bottomrule
\end{tabular}
\end{center}
}{}
\questionandanswer[5.10.4]{
[ 10 ]<5.4>添加L2 cache的P1的AMAT是多少?在使用L2 cache后,AMAT变得更好还是更差?
}{
$$
1+8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times 95\% \times \left\lceil \frac{70}{0.66} \right\rceil = 9.852 \text{周期}
$$
显然使用L2 cache后AMAT变得更差。
}
\questionandanswer[5.10.5]{
[ 5 ]<5.4>假设基本CPI为1.0而且没有任何内存停顿那么添加L2 cache的P1的总CPI是多少?
}{
$$
1+ 8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times 95\% \times \left\lceil \frac{70}{0.66} \right\rceil + 36\% \times \left( 8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times 95\% \times \left\lceil \frac{70}{0.66} \right\rceil \right) = 13.03872
$$
}
\questionandanswer[5.10.6]{
[ 10 ]<5.4>为了使具有L2 cache的P1比没有L2 cache的P1更快需要L2的失效率为多少?
}{
设L2的失效率最大为$x$,则
$$
1+8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times x \times \left\lceil \frac{70}{0.66} \right\rceil = 9.56
$$
解得
$ x = \frac{98}{107} \approx 0.9159 = 91.59\%$所以L2的失效率需要小于$91.59\%$
}
\questionandanswer[5.10.7]{
[ 15 ]<5.4>为了使具有L2 cache 的P1比没有L2 cache的P2更快需要L2的失效率为多少?
}{
设L2的失效率最大为$x$由于涉及到P1和P2所以这里需要比较的是实际的执行时间即CPI $\times $ 每条指令执行的时间由于5.10.1的假设所以每条指令执行的时间就是L1命中时间。
$$
\begin{aligned}
&\left[1+ 8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times x\times \left\lceil \frac{70}{0.66} \right\rceil + 36\% \times \left( 8\% \times \left\lceil \frac{5.62}{0.66} \right\rceil + 8\% \times x\times \left\lceil \frac{70}{0.66} \right\rceil \right) \right] \times 0.66 \\
&= 7.3648 \times 0.90 \\
\end{aligned}
$$
解得
$ x = \frac{27719}{40018} \approx 0.6927 = 69.27 \%
$所以L2的失效率需要小于$69.27\%$
}
\end{enumerate}
\end{document}