CS:APP 第6章存储器层次结构作业

6.22

相当于求函数 $x*r*(r-x*r)$ 的最值，通过初中知识可以得到当 $x=\frac{1}{2}$ 时取到最值。

6.23

$\begin{aligned} T_{access}&=T_{avg\ seek}+T_{avg\ rotation}+T_{avg\ transfer}\\ &=4+\frac{60}{15000}*1000*\frac{1}{2}+\frac{60}{15000}*1000*\frac{1}{800}\\ &=4+2+0.005\\ &=6.005ms \end{aligned}$

6.24

A

最好情况就是全部连续。
$\begin{aligned} T_{access}&=T_{avg\ seek}+T_{avg\ rotation}+T_{avg\ transfer}\\ &=4+\frac{60}{15000}*1000*\frac{1}{2}+\frac{60}{15000}*1000*\frac{4000}{1000}\\ &=4+2+16\\ &=22ms \end{aligned}$

B

$\begin{aligned} T_{access}&=(T_{avg\ seek}+T_{avg\ rotation}+T_{avg\ transfer})*times\\ &=(4+\frac{60}{15000}*1000*\frac{1}{2}+\frac{60}{15000}*1000*\frac{1}{1000})*4000\\ &=(4+2+0.004)*4000\\ &=24016ms \end{aligned}$

6.25

$高速缓存$	$m$	$C$	$B$	$E$	$S$	$t$	$s$	$b$
$1.$	$32$	$1024$	$4$	$4$	$64$	$24$	$6$	$2$
$2.$	$32$	$1024$	$4$	$256$	$1$	$30$	$0$	$2$
$3.$	$32$	$1024$	$8$	$1$	$128$	$22$	$7$	$3$
$4.$	$32$	$1024$	$8$	$128$	$1$	$29$	$0$	$3$
$5.$	$32$	$1024$	$32$	$1$	$32$	$22$	$5$	$5$
$6.$	$32$	$1024$	$32$	$4$	$8$	$24$	$3$	$5$

6.26

$高速缓存$	$m$	$C$	$B$	$E$	$S$	$t$	$s$	$b$
$1.$	$32$	$2048$	$8$	$1$	$256$	$21$	$8$	$3$
$2.$	$32$	$2048$	$4$	$4$	$128$	$23$	$7$	$2$
$3.$	$32$	$1024$	$2$	$8$	$64$	$25$	$6$	$1$
$4.$	$32$	$1024$	$32$	$2$	$16$	$23$	$4$	$5$

6.27

A

0x8a4~0x8a7,0x704~0x707

B

0x1238~0x123b

6.28

A

无

B

0x18f0~0x18f3,0xb0~0xb3

C

0xe34~0xe37

D

0x1bdc~0x1bdf

6.29

A

CO:0~1
CI:2~3
CT:4~11

B

$操作$	$地址$	$命中?$	$读出的值(或者未知)$
$读$	$0x834$	$否$	$未知$
$写$	$0x836$	$是$	$-$
$读$	$0xffd$	$是$	$0x3$

6.30

A

$C=S*E*B=8*4*4=128Byte$

B

CO:0~1
CI:2~4
CT:5~12

6.31

A

00111000 110 10

B

CO:0x2
CI:0x6
CT:0x38
命中:是
返回:0xeb

6.32

A

10110111 010 00

B

CO:0x0
CI:0x2
CT:0xb7
命中:否
返回:—

6.33

0x1788~0x178b,0x16c8~0x16cb

6.34

dst数组：

	$列0$	$列1$	$列2$	$列3$
$行0$	$m$	$h$	$m$	$m$
$行1$	$m$	$h$	$m$	$m$
$行2$	$m$	$h$	$m$	$m$
$行3$	$m$	$h$	$m$	$m$

src数组：

	$列0$	$列1$	$列2$	$列3$
$行0$	$m$	$m$	$h$	$m$
$行1$	$m$	$h$	$m$	$h$
$行2$	$m$	$m$	$h$	$m$
$行3$	$m$	$h$	$m$	$h$

本来手算的，脑子不清楚算麻了，干脆写了个程序跑，省事多了。

#include <iostream>
#include <vector>
using namespace std;

int cache[2] = {-1, -1};

vector<string> src, dst;

void print(vector<string> &vs)
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
            cout << vs[i * 4 + j] << ' ';
        cout << endl;
    }
}

int main()
{
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
        {
            int bsrc = i, bdst = j + 4;
            if (cache[bsrc & 1] != bsrc)
                src.push_back("m"), cache[bsrc & 1] = bsrc;
            else
                src.push_back("h");
            if (cache[bdst & 1] != bdst)
                dst.push_back("m"), cache[bdst & 1] = bdst;
            else
                dst.push_back("h");
        }

    cout << "src:\n";
    print(src);
    cout << "dst:\n";
    print(dst);
}

dst的答案没转置，脑补一下就行了。

6.35

显然 $128Byte$ 足够大，放得下所有元素，那么只有初始的未命中，剩下的全是命中了。

dst数组：

	$列0$	$列1$	$列2$	$列3$
$行0$	$m$	$h$	$h$	$h$
$行1$	$m$	$h$	$h$	$h$
$行2$	$m$	$h$	$h$	$h$
$行3$	$m$	$h$	$h$	$h$

src数组：

	$列0$	$列1$	$列2$	$列3$
$行0$	$m$	$h$	$h$	$h$
$行1$	$m$	$h$	$h$	$h$
$行2$	$m$	$h$	$h$	$h$
$行3$	$m$	$h$	$h$	$h$

6.36

A

$100\%$

B

$25\%$

C

$25\%$

D

不会，块与块之间已经不会互相冲突，不会出现抖动现象。

E

会，只有对块的第一次访问会不命中，当块增大，访问块的次数增多，会导致命中率上升。

6.37

$函数$	$N=64$	$N=60$
$sumA$	$25\%$	$25\%$
$sumB$	$100\%$	$25\%$
$sumC$	$50\%$	$25\%$

我对答案的那哥们好像做错了，主要不一样的地方在于第一列的第二和第三行。
对于 $N=64,sumB$ 的情况来说，每次步长为 $64*4=256Byte$ ，缓存为 $4KB$ ，能够放下 $4KB/256B=16$ 次循环，而每次循环次数为 $64$ 次，后面的会覆盖之前缓存中的内容，因为是在一次内层循环中，缓存被全部换了一遍，外层循环只不过是在重复这个过程，所以不命中率为 $100\%$ ，和之前抖动的现象类似。
对于 $N=64,sumC$ 的情况，和上面一种类似，也是抖动，只不过有一个改进是每次取 $2*2$ 的一个矩阵，这样右边的两个元素会命中，所以不命中率下降到了 $50\%$ 。

对于右边 $N=60,sumB$ 的情况，我们可以看到没有做任何事情，单单改变了元素数量命中率就会上升。思考了一下出现这种现象的原因。每次步长为 $60*4=240Byte$ ，块大小为 $16Byte$ ，所以步长为 $15$ 块，需要访问 $60$ 次，而缓存一共有 $256$ 块，发现这两个数字互素，只有塞满缓存后才开始替换，只有第一个元素会不命中，所以不命中率大约为 $25\%$ ，感觉和哈希用素数取模是同一个道理，倒不如说直接映射缓存其实就是一个哈希表。

这位老哥把缓存的图画出来了，可以帮助理解。

6.38

A

$1024$

B

$128$

C

$12.5\%$

6.39

A

$1024$

B

$256$

C

$25\%$

连续访问 $4$ 个元素，只有第一个不命中。

6.40

A

$1024$

B

$16*16*\frac{1}{2}+16*16*3*\frac{1}{6}=256$

C

$25\%$

6.41

$25\%$

6.42

$25\%$

6.43

$100\%$

6.44

运行结果：

Clock frequency is approx. 2496.0 MHz
Memory mountain (MB/sec)
        s1      s2      s3      s4      s5      s6      s7      s8      s9      s10     s11     s12     s13     s14    s15
128m    16431   9272    6687    4910    3933    3396    2824    2481    2251    2114    1980    1854    1723    1652    1605
64m     16924   9866    6896    4929    4066    3407    2899    2643    2390    2185    2037    1872    1767    1695    1655
32m     17100   10608   7226    5359    4410    3682    3178    2835    2614    2248    2245    2092    2011    1896    1852
16m     18372   11009   8467    6270    5125    4269    3758    3344    3115    2902    2488    2631    2523    2375    2465
8m      20366   13656   10551   7949    5321    4516    4272    3454    3772    3593    3684    3844    3848    3951    4227
4m      28843   20763   16701   13705   11511   9892    8512    7540    7754    7437    7167    6920    6751    6211    6108
2m      27698   21271   17533   13978   11617   10004   8760    7758    7421    7178    6906    6676    6496    6346    6241
1024k   27726   20927   17356   13963   11671   10034   8810    7794    7461    7179    6895    6662    6491    6332    6243
512k    27800   21148   17539   14195   11940   10234   8978    7929    7544    7264    7074    6919    6844    6824    6827
256k    27900   23239   21056   18338   16104   14107   12500   11044   10965   11262   11206   11973   11848   12114   13013
128k    28870   23503   23341   21706   19779   16891   15620   13797   13810   13827   12269   12598   11995   12456   12725
64k     29284   24951   24255   22923   20046   16704   15037   12991   12246   12505   12370   11771   12240   13217   23401
32k     32900   31361   30494   28638   28200   28279   27819   27631   27869   28591   32039   30973   27587   26792   29952
16k     31313   30337   29761   29894   28196   30973   27813   31170   26722   30973   28589   25426   26652   26548   27256

观察s15列，从下往上，寻找梯度下降最快的几个点，数据趋势大约是30000->13000->6200->1700，比较明显地下降了三次，分别对应三级缓存，分别大约是128KB，1.0MB，32MB。实际上查看任务管理器中三级缓存的数据，分别为：256KB，1.0MB和6.0MB，和预估的有差距。说明这种方式只能大概地估计缓存大小，并不准确。

6.45

一开始觉得没什么好提升的，后来看了提示，仔细分析缓存的访问，发现对于src的访问已经没有提升了，而对于dst的访问还有提升的空间。
因为dst是按照列访问的，原来的访问模式每次将一块加载到缓存中，然后只使用一次就离开去别的块了，所以我们可以将原矩阵分块，使得每次加载一块进入缓存后，多使用几次再去下一个循环，而这个分块的大小，是根据缓存中一行的大小来决定的，在不清楚数据的情况下只能多次尝试。
代码如下：

#include <ctime>
#include <iostream>
#include <random>
using namespace std;

const int N = 8192;
int dst[N][N], src[N][N];

void gen()
{
    mt19937 rng(time(0));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            src[i][j] = rng();
}
void test(void (*fun)(int *, int *, int, int), int block = -1)
{
    clock_t st = clock();
    fun(&dst[0][0], &src[0][0], N, block);
    cout << clock() - st << '\n';
}

void transpose(int *dst, int *src, int dim, int block)
{
    for (int i = 0; i < dim; i++)
        for (int j = 0; j < dim; j++)
            dst[j * dim + i] = src[i * dim + j];
}

void transpose_optimized(int *dst, int *src, int dim, int block)
{
    for (int i = 0; i < dim - block + 1; i += block)
        for (int j = 0; j < dim - block + 1; j += block)
            for (int m = 0; m < block; m++)
                for (int n = 0; n < block; n++)
                    dst[(j + n) * dim + i + m] = src[(i + m) * dim + j + n];
    for (int ii = i; ii < dim; ii++)
        for (int jj = 0; jj < dim; jj++)
            dst[jj * dim + ii] = src[ii * dim + jj];
    for (int ii = 0; ii < i; ii++)
        for (int jj = j; jj < dim; jj++)
            dst[jj * dim + ii] = src[ii * dim + jj];
}

int main()
{
    gen();
    cout << "origin: ";
    test(transpose);

    for (int block = 2; block <= 16; block++)
    {
        cout << "block size= " << block << ": ";
        test(transpose_optimized, block);
    }
}

用c++写了个测试程序，先用随机数填充了一个8192*8192的矩阵，然后对原代码和优化后的代码分别进行时间的测量得到结果：

origin: 984
block size= 2: 454
block size= 3: 326
block size= 4: 270
block size= 5: 275
block size= 6: 250
block size= 7: 246
block size= 8: 219
block size= 9: 220
block size= 10: 229
block size= 11: 260
block size= 12: 288
block size= 13: 327
block size= 14: 326
block size= 15: 336
block size= 16: 356

发现运行时间先减少再增大，这样的结果是意料之中的，首先随着分块的变大运行速度提高，因为缓存的利用率得到了提高，到达一定程度后，每次分块都超出了缓存一行的大小，在内循环中都需要多次访问内存，缓存的利用率反而下降，运行速度下降。
经过多次实验，得到当block size=8时取得最小值，运行速度提高了 $4$ 倍左右。

6.46

和上一题几乎一模一样，改改代码就完事了。
注意细节，利用对称性能够减少一些计算量。

#include <ctime>
#include <iostream>
#include <random>
using namespace std;

const int N = 8192;
int G[N][N];

void gen()
{
    mt19937 rng(time(0));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            G[i][j] = rng() % 2;
}
void test(void (*fun)(int *, int, int), int block = -1)
{
    clock_t st = clock();
    fun(&G[0][0], N, block);
    cout << clock() - st << '\n';
}

void col_convert(int *G, int dim, int block)
{
    for (int i = 0; i < dim; i++)
        for (int j = 0; j < dim; j++)
            G[j * dim + i] = G[j * dim + i] | G[i * dim + j];
}

void col_convert_optimized(int *G, int dim, int block)
{
    for (int i = 0; i < dim - block + 1; i += block)
        for (int j = i; j < dim - block + 1; j += block)
            for (int m = 0; m < block; m++)
                for (int n = 0; n < block; n++)
                    G[(i + m) * dim + j + n] = G[(j + n) * dim + i + m] = G[(j + n) * dim + i + m] | G[(i + m) * dim + j + n];
    for (; i < dim; i++)
        for (j = 0; j <= i; j++)
            G[i * dim + j] = G[j * dim + i] = G[i * dim + j] | G[j * dim + i];
}

int main()
{
    gen();
    cout << "origin: ";
    test(col_convert);

    for (int block = 2; block <= 16; block++)
    {
        cout << "block size= " << block << ": ";
        test(col_convert_optimized, block);
    }

}

运行结果：

origin: 838
block size= 2: 440
block size= 3: 352
block size= 4: 316
block size= 5: 271
block size= 6: 235
block size= 7: 210
block size= 8: 177
block size= 9: 211
block size= 10: 255
block size= 11: 293
block size= 12: 339
block size= 13: 455
block size= 14: 532
block size= 15: 532
block size= 16: 527

番外

查看缓存架构。
输入命令：

cd /sys/devices/system/cpu/cpu0/cache/index0

这是cpu0的第一个缓存数据。

dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ ls
coherency_line_size  level           physical_line_partition  shared_cpu_map  type    ways_of_associativity
id                   number_of_sets  shared_cpu_list          size            uevent

下面解释一下部分文件中的数据。

文件	注释
`coherency_line_size`	行/块大小
`level`	在第几层(Ln中的n)
`number_of_sets`	组数
`size`	缓存总大小
`type`	类型(Data/Instruction/Unified)
`ways_of_associativity`	相联数(每组行数)
`shared_cpu_map`	十六进制数字，代表哪几个cpu共享
`shared_cpu_list`	共享的cpu的列表

我的机器cpu是Intel Core i5，经过查看数据，与下图层次结构一致。

缓存层次结构

接下来举个例子进行验证：

dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cd /sys/devices/system/cpu/cpu1/cache/index3
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat level
3
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat size
6144K
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat type
Unified
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat number_of_sets
8192
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat ways_of_associativity
12
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat coherency_line_size
64
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu1/cache/index3$ cat shared_cpu_list
0-3

这是cpu1中的第四个缓存，对应图中的L3统一的高速缓存(所有的核共享)，我们可以看到打印出的数据表明：

在第三层
总大小为6.0MB
统一的
组数为8192
相联数为12
每一行大小位64B
被所有的cpu共享

其他的缓存都能在这些地方中查看到数据。

再举个例子：

dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cd /sys/devices/system/cpu/cpu0/cache/index0
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat level
1
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat size
32K
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat type
Data
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat number_of_sets
64
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat ways_of_associativity
8
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat coherency_line_size
64
dyume@LAPTOP-LLU88NPC:/sys/devices/system/cpu/cpu0/cache/index0$ cat shared_cpu_list
0

这是cpu0中的第一个缓存，对应图中的L1d-cache，我们可以看到打印出的数据表明：

在第一层
总大小为32KB
数据缓存
组数为64
相联数为8
每一行大小位64B
只被第一个处理器独享

最后编辑于：2021.03.24 15:22:33

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 215,384评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,845评论 3赞 391
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 161,148评论 0赞 351
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,640评论 1赞 290
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,731评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,712评论 1赞 294
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,703评论 3赞 415
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,473评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,915评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,227评论 2赞 331
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,384评论 1赞 345
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,063评论 5赞 340
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,706评论 3赞 324
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,302评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,531评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,321评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,248评论 2赞 352

CS:APP 第6章 存储器层次结构 作业

6.22

6.23

6.24

A

B

6.25

6.26

6.27

A

B

6.28

A

B

C

D

6.29

A

B

6.30

A

B

6.31

A

B

6.32

A

B

6.33

6.34

dst数组：

src数组：

6.35

dst数组：

src数组：

6.36

A

B

C

D

E

6.37

6.38

A

B

C

6.39

A

B

C

6.40

A

B

C

6.41

6.42

6.43

6.44

6.45

6.46

番外

推荐阅读更多精彩内容

CS:APP 第6章存储器层次结构作业