\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的时钟周期频率为C1，CPI为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}