深入理解计算机系统 第6章 习题解析
这次更新第6章习题。
参考资料：
- https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter6
- https://zh.wikipedia.org/zh/%E6%AF%8F%E5%88%86%E9%90%98%E8%BD%89%E9%80%9F
- https://unix.stackexchange.com/questions/167038/is-there-any-way-to-know-the-size-of-l1-l2-l3-cache-and-ram-in-linux
- https://www.cnblogs.com/kekukele/p/3829369.html?wework_cfm_code=M8Cqb2ks4L%2BsND75%2FNCam4bak6vx5un7Fr%2BxzPv9xCxMh3ihzvKX75lVcSwK%2FeDS%2F18ogZKaBEskYzQ8zZEYnPGNXb37HFryLTWAaifxaJ0cJQUZLYjQXv8%3D
6.22
总容量$r$为
当且仅当$x=\frac 1 2$时取等号。
6.23
RPM含义为每分钟旋转数，更具体的见：
https://zh.wikipedia.org/zh/%E6%AF%8F%E5%88%86%E9%90%98%E8%BD%89%E9%80%9F
旋转时间（以ms为单位）：
传送时间（以ms为单位）：
总访问时间为：
6.24
应该文件的包含的扇区数量为：
旋转时间（以ms为单位）：
A
注意到转动一圈可以访问$1000$个扇区，所以最好情况为访问$4$圈即可，因此时间为
B
最坏情况为每次访问需要转一圈，因此时间为
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
练习6.12的高速缓存如下：
后续符号的含义如下：
- CO: 高速缓存块偏移
- CI: 高速缓存组索引
- CT: 高速缓存标记
对应关系：
A
| CT | CI | CO |
|---|---|---|
| 0x45 | 0x1 | 0x0~0x3 |
| 0x38 | 0x1 | 0x0~0x3 |
二进制：
0100,0101,001,00 ~ 0100,0101,001,11
0,1000,1010,0100 ~ 0,1000,1010,0111
0x08A4 ~ 0x08A7
0011,1000,001,00 ~ 0011,1000,001,11
0,0111,0000,0100 ~ 0,0111,0000,0111
0x0704 ~ 0x0707B
| CT | CI | CO |
|---|---|---|
| 0x91 | 0x6 | 0x0~0x3 |
二进制：
1001,0001,110,00 ~ 1001,0001,110,11
1,0010,0011,1000 ~ 1,0010,0011,1011
0x1238 ~ 0x123E6.28
练习6.12的高速缓存如下：
A
无法命中组2。
B
| CT | CI | CO |
|---|---|---|
| 0xC7 | 0x4 | 0x0~0x3 |
| 0x05 | 0x4 | 0x0~0x3 |
二进制：
1100,0111,100,00 ~ 1100,0111,100,11
1,1000,1111,0000 ~ 1,1000,1111,0011
0x18F0 ~ 0x18F3
0000,0101,100,00 ~ 0000,0101,100,11
0,0000,1011,0000 ~ 0,0000,1011,0011
0x00B0 ~ 0x00B3C
| CT | CI | CO |
|---|---|---|
| 0x71 | 0x5 | 0x0~0x3 |
二进制：
0111,0001,101,00 ~ 0111,0001,101,11
0,1110,0011,0100 ~ 0,1110,0011,0111
0x0E34 ~ 0x0E37D
| CT | CI | CO |
|---|---|---|
| 0xDE | 0x7 | 0x0~0x3 |
二进制：
1101,1110,111,00 ~ 1101,1110,111,11
1,1011,1101,1100 ~ 1,1011,1101,1111
0x1BDC ~ 0x1BDF6.29
A
所以CT占9位，CI占2位，CO占2位。
B
| 操作 | 地址 | 二进制 | CT | CI | CO | 命中？ | 读出的值（或者未知） |
|---|---|---|---|---|---|---|---|
| 读 | 0x834 | 0,1000,0011,0100 | 0b0,1000,0011=0x083 | 0b01=0x1 | 0b00=0x0 | 否 | 未知 |
| 写 | 0x836 | 0,1000,0011,0110 | 0b0,1000,0011=0x083 | 0b01=0x1 | 0b10=0x2 | 是 | 未知 |
| 读 | 0xFFD | 0,1111,1111,1101 | 0b0,1111,1111=0x0FF | 0b11=0x3 | 0b01=0x3 | 是 | 0xFF |
6.30
缓存：
A
B
CT占8位，CI占3位，CO占2位。
6.31
A, B
0x071A
0,0111,0001,1010
0011,1000,110,10
CT=0x38
CI=0x6
CO=0x2
命中
0xEB6.32
A, B
0x16E8
1,0110,1110,1000
1011,0111,010,00
CT=0xB7
CI=0x2
CO=0x0
未命中6.33
| CT | CI | CO |
|---|---|---|
| 0xBC | 0x2 | 0x0~0x3 |
| 0xB6 | 0x2 | 0x0~0x3 |
二进制：
1011,1100,010,00 ~ 1011,1100,010,11
1,0111,1000,1000 ~ 1,0111,1000,1011
0x1788 ~ 0x178B
1011,0110,010,00 ~ 1011,0110,010,11
1,0110,1100,1000 ~ 1,0110,1100,1011
0x16C8 ~ 0x16CB6.34
typedef int array[4][4];
void transpose2(array dst, array src)
{
int i, j;
for (i = 0; i < 4; i++){
for (j = 0; j < 4; j++){
dst[j][i] = src[i][j];
}
}
}高速缓存块共有两块，正好能存储两行数据，srt和dst的相同行映射到同一缓存块，代码运行时高速缓存的状态变化如下：
第一轮外循环：
初始状态
0:
1:
i = 0, j = 0
读取src[0][0](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1:
赋值dst[0][0](m)
0: dst[0][0], dst[0][1], dst[0][2], dst[0][3]
1:
i = 0, j = 1
读取src[0][1](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1:
赋值dst[1][0](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: dst[1][0], dst[1][1], dst[1][2], dst[1][3]
i = 0, j = 2
读取src[0][2](h)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: dst[1][0], dst[1][1], dst[1][2], dst[1][3]
赋值dst[2][0](m)
0: dst[2][0], dst[2][1], dst[2][2], dst[2][3]
1: dst[1][0], dst[1][1], dst[1][2], dst[1][3]
i = 0, j = 3
读取src[0][3](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: dst[2][0], dst[2][1], dst[2][2], dst[2][3]
赋值dst[3][0](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: dst[3][0], dst[3][1], dst[3][2], dst[3][3]第二轮外循环：
初始状态
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: dst[3][0], dst[3][1], dst[3][2], dst[3][3]
i = 1, j = 0
读取src[1][0](m)
0: src[0][0], src[0][1], src[0][2], src[0][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
赋值dst[0][1](m)
0: dst[0][0], dst[0][1], dst[0][2], dst[0][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
i = 1, j = 1
读取src[1][1](h)
0: dst[0][0], dst[0][1], dst[0][2], dst[0][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
赋值dst[1][1](m)
0: dst[0][0], dst[0][1], dst[0][2], dst[0][3]
1: dst[1][0], dst[1][1], dst[1][2], dst[1][3]
i = 1, j = 2
读取src[1][2](m)
0: dst[0][0], dst[0][1], dst[0][2], dst[0][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
赋值dst[2][1](m)
0: dst[2][0], dst[2][1], dst[2][2], dst[2][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
i = 1, j = 3
读取src[1][3](h)
0: dst[2][0], dst[2][1], dst[2][2], dst[2][3]
1: src[1][0], src[1][1], src[1][2], src[1][3]
赋值dst[3][1](m)
0: dst[2][0], dst[2][1], dst[2][2], dst[2][3]
1: dst[3][0], dst[3][1], dst[3][2], dst[3][3]其余情形类似，因此缓存命中情况如下：
src：
m m h m
m h m h
m m h m
m h m hdst：
m m m m
m m m m
m m m m
m m m m6.35
高速缓存块共有八块，正好能存储全部数据，所以所有的不命中都是冷不命中，因此缓存命中情况如下：
dst：
m h h h
m h h h
m h h h
m h h hsrc：
m h h h
m h h h
m h h h
m h h h6.36
代码：
int x[2][128];
int i;
int sum = 0;
for (i = 0; i < 128; i++) {
sum += x[0][i] * x[1][i];
}数组大小为$2 \times 128 \times 4 = 1024$字节。
A
注意
所以$\text{x[0][i], x[1][i]}$映射到同一缓存块，所以不命中率为100%。
B
缓存可以容纳全部数组，所以不命中率为冷不命中率，注意一个缓存块存储4个元素，所以不命中率为$\frac 1 4$。
C
回顾LRU定义（课本434）：
一共16组，每组2个高速缓存块，一个高速缓存块16字节，存储4个元素。
$\text{x[0][i], x[1][i]}$映射到同一组中不同块，一个缓存块存储4个元素，所以不命中率为$\frac 1 4$。
D
不会，因为当前不命中率为冷不命中率。
E
会，因为每次可以缓存更多的元素。
6.37
原始代码：
typedef int array_t[N][N];
int sumA(array_t a)
{
int i, j;
int sum = 0;
for (i = 0; i < N; i++）
for (j = 0; j < N; j++) {
sum += a[i][j];
}
return sum;
}
int sumB(array_t a)
{
int i, j;
int sum = 0;
for (j = 0; j < N; j++)
for(i = 0; i < N; i++){
sum += a[i][j];
}
return sum;
}
int sumC(array_t a)
{
int i, j;
int sum = 0;
for (j = 0; j < N; j += 2)
for (i = 0; i < N; i += 2){
sum += (a[i][j] + a[i+1][j]
+ a[i][j+1] + a[i+1][j+1]);
}
return sum;
}array_t大小为为$4\times N^2$字节，具体如下：
| array_t字节数 | $N=64$ | $N=60$ |
|---|---|---|
| $4\times N^2$ | 16384 | 14400 |
高速缓存一共$4\times 1024=4096$字节，共$4096/16=256$个高速缓存块，编号为$0\sim 255$，一个高速缓存块存储$4$个元素。
$\text{array_t[i][j]}$的相对地址$a[i][j]$（相对于$\mathrm{0x08000000}$）
$N=64$时，组索引为
0: a[0][0], a[0][1], a[0][2], a[0][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
......
15: a[0][60], a[0][61], a[0][62], a[0][63]
16: a[1][0], a[1][1], a[1][2], a[1][3]
17: a[1][4], a[1][5], a[1][6], a[1][7]
......
31: a[1][60], a[1][61], a[1][62], a[1][63]
......
240: a[15][0], a[15][1], a[15][2], a[15][3]
241: a[15][4], a[15][5], a[15][6], a[15][7]
...
255: a[15][60], a[15][61], a[15][62], a[15][63]
...$N=60$时，组索引为
0: a[0][0], a[0][1], a[0][2], a[0][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
......
14: a[0][56], a[0][57], a[0][58], a[0][59]
15: a[1][0], a[1][1], a[1][2], a[1][3]
16: a[1][4], a[1][5], a[1][6], a[1][7]
......
29: a[1][56], a[1][57], a[1][58], a[1][59]
......
235: a[15][0], a[15][1], a[15][2], a[15][3]
236: a[15][4], a[15][5], a[15][6], a[15][7]
......
239: a[15][56], a[15][57], a[15][58], a[15][59]
......sumA：
当$N=64,60$时，缓存如下：
0:a[0][0], a[0][1], a[0][2], a[0][3]
1:a[0][4], a[0][5], a[0][6], a[0][7]
......所以不命中率为$\frac 1 4$。
sumB:
当$N=64$时，缓存的过程如下：
0: a[0][0], a[0][1], a[0][2], a[0][3]
16: a[1][0], a[1][1], a[1][2], a[1][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
17: a[1][4], a[1][5], a[1][6], a[1][7]
......所以不命中率为$\frac 1 4$。
当$N=60$时，缓存的过程如下：
0: a[0][0], a[0][1], a[0][2], a[0][3]
15: a[1][0], a[1][1], a[1][2], a[1][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
16: a[1][4], a[1][5], a[1][6], a[1][7]所以不命中率为$\frac 1 4$。
sumC:
当$N=64$时，缓存的过程如下：
0: a[0][0], a[0][1], a[0][2], a[0][3]
16: a[1][0], a[1][1], a[1][2], a[1][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
17: a[1][4], a[1][5], a[1][6], a[1][7]
......所以不命中率为$\frac 1 4$。
当$N=60$时，缓存的过程如下：
0: a[0][0], a[0][1], a[0][2], a[0][3]
15: a[1][0], a[1][1], a[1][2], a[1][3]
1: a[0][4], a[0][5], a[0][6], a[0][7]
16: a[1][4], a[1][5], a[1][6], a[1][7]
......所以不命中率为$\frac 1 4$。
完整的结果如下：
| 函数 | $N=64$ | $N=60$ |
|---|---|---|
| sumA | $\frac 1 4$ | $\frac 1 4$ |
| sumB | $\frac 1 4$ | $\frac 1 4$ |
| sumC | $\frac 1 4$ | $\frac 1 4$ |
6.38
代码：
struct point_color {
int c;
int m;
int y;
int k;
};
struct point_color square[16][16];
int i, j;
for (i = 0; i < 16; i++){
for (j = 0; j < 16; j++){
square[i][j].c = 0;
square[i][j].m = 0;
square[i][j].y = 1;
square[i][j].k = 0;
}
}数组元素大小为$16\times 16\times 4 \times 4= 4096$字节，高速缓存块一共有$2048$字节，只能保存数组的$\frac 1 2$。
缓存一共有$2048/32=64$块，每块可以容纳$2$个元素。
A
写总数为$16\times 16\times 4 = 1024$。
B
缓存一共有$2048/32=64$块，每块可以容纳$2$个元素，所以每次读取$\text{square[i][0]}$会同时缓存$\text{square[i][1]}$，因此不命中的写总数为$16\times 8 =128$。
C
不命中率为
6.39
代码：
for (i = 0; i < 16; i++){
for (j = 0; j < 16; j++){
square[j][i].c = 0;
square[j][i].m = 0;
square[j][i].y = 1;
square[j][i].k = 0;
}
}A
写总数为$16\times 16\times 4 = 1024$。
B
注意缓存只能保存一半元素，所以读$\text{square[j+8][i]}$的第一个元素会覆盖$\text{square[j][i]}$的缓存，所以不命中数为$16\times 16$。
C
不命中率为
6.40
代码：
for (i = 0; i < 16; i++) {
for (j = 0; j < 16; j++) {
square[i][j]·y = 1
}
}
for (i = 0; i < 16; i++) {
for (j = 0 ; j < 16; j++) {
square[i][j].c = 0;
square[i][j].m = 0;
square[i][j].k = 0;
}
}A
写总数为$16\times 16\times 4 = 1024$。
B
缓存一共有$2048/32=64$块，每块可以容纳$2$个元素，所以第一部分的不命中数为
第二部分的不命中数为
总不命中数为
C
不命中率为
6.41
代码：
struct pixel {
char r;
char g;
char b;
char a;
};
struct pixel buffer[480][640];
int i, j;
char *cptr;
int *iptr;
for (j = 0; j < 640; j++){
for (i = 0; i < 480; i++){
buffer[i][j].r = 0;
buffer[i][j].g = 0;
buffer[i][j].b = 0;
buffer[i][j].a = 0;
}
}数组大小为$480\times 640 \times 4=1228800$字节；高速缓存大小为$64\times 1024=65536$字节，能容纳数组的比例为$\frac{4}{15\times 5}=\frac{4}{75}$；一共有$65536/4=16384$个高速缓存块，每块容纳一个像素。
该代码是按列读取，每读取$\text{buffer[i][j].r}$，会缓存相应的$\text{buffer[i][j].g,buffer[i][j].b,buffer[i][j].a}$，所以不命中率为
6.42
代码：
char *cptr = (char *) buffer;
for (; cptr < ((char *) buffer) + 640 * 480 * 4); cptr++)
*cptr = 0;该代码等价于按行读取，每读取$\text{buffer[i][j].r}$，会缓存相应的$\text{buffer[i][j].g,buffer[i][j].b,buffer[i][j].a}$，所以不命中率为
6.43
代码：
char *iptr = (int *) buffer;
for (; iptr < ((int *) buffer) + 640 * 480); iptr++)
*iptr = 0;注意int的大小为4字节，所以每次赋值
*iptr = 0均不会缓存任何内容，因此不命中率为$1$
6.44
参考资料：
实验结果：
Clock frequency is approx. 2208.0 MHz
Memory mountain (MB/sec)
s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 s11 s12 s13 s14 s15
128m 16567 9942 6557 5049 3568 2790 2386 2168 1965 1773 1602 1637 1637 1539 1505
64m 16688 10098 6832 5186 4061 3098 2719 2316 2052 2090 1864 1623 1687 1653 1601
32m 17677 10551 7453 5327 4236 3629 2976 2642 2457 2336 2169 2010 1835 1806 1663
16m 17562 10899 8431 6670 5333 2775 3029 2744 3140 3039 2835 2816 2699 2700 2667
8m 20028 13649 11431 9330 6711 5677 4985 4170 4209 4214 4107 4085 4084 4051 4062
4m 29176 20474 17000 14585 12084 10661 9446 8403 8147 7897 7547 7243 7058 6865 6773
2m 30147 23466 19179 15521 13090 11291 9932 8824 8417 7965 7686 7315 7054 6888 6767
1024k 29927 23267 19122 15650 13127 11321 9913 8785 8338 7968 7643 7301 7068 6631 6636
512k 30039 23633 19387 16018 13389 11605 10186 9020 8673 8402 8069 7835 7802 7715 7705
256k 32167 27323 24704 21675 18841 16621 14630 13069 12837 13191 13321 15283 14981 15426 16025
128k 33535 30400 30015 28174 24884 22025 19247 16748 16747 16186 16101 16013 15946 16432 16078
64k 33388 30222 29447 26718 22296 18841 16099 13766 13764 13780 14083 13956 13410 15473 24117
32k 34852 34388 33588 33250 31730 31899 31511 28803 28300 30650 31016 33120 26246 29694 29050
16k 34585 34258 32945 30147 31450 31071 30393 30973 29548 32292 31613 28980 30912 30754 30912根据课本介绍，只要看哪一行的数值变动不大即可，注意32k对应的行数值变动较小，64k对应的行数值变动较大，所以推测缓存大小为32k，使用命令验证：
lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Stepping: 10
CPU MHz: 2208.006
BogoMIPS: 4416.01
Hypervisor vendor: Microsoft
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 9216K6.45
参考资料：
首先查看缓存块的基本信息：
$S$：
cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
64$E$：
cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity
8$B$
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64实验思路：
对矩阵分块进行操作，分块大小为缓存块可以容纳的矩阵行数，一共测试了如下三个版本：
- v1: 普通转置。
- v2: 分块。
- v3: 分块 + 局部变量缓存。
实验代码：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
const int S = 64;
const int E = 8;
const int B = 64;
// 矩阵维度
const int D = 256;
// 循环次数
const int N = 1000;
// int大小
const int d = sizeof(int);
// 分块大小
int d1;
int min(int a, int b){
return (a > b) ? b : a;
}
void transposeV1(int *dst, int *src, int dim){
for (int i = 0; i < dim; i++){
for (int j = 0; j < dim; j++){
dst[j * dim + i] = src[i * dim + j];
}
}
}
void transposeV2(int *dst, int *src, int dim){
for (int i = 0; i < dim; i += d1){
for (int j = 0; j < dim; j += d1){
for (int s = 0; s < d1; s++){
for (int t = 0; t < d1; t++){
dst[(j + t) * dim + i + s] = src[(i + s) * dim + j + t];
}
}
}
}
}
void transposeV3(int *dst, int *src, int dim){
for (int i = 0; i < dim; i += d1){
for (int j = 0; j < dim; j += d1){
for (int s = 0; s < d1; s++){
// 本地变量
int a[d1];
for (int t = 0; t < d1; t++){
a[t] = src[(i + s) * dim + j + t];
}
for (int t = 0; t < d1; t++){
dst[(j + t) * dim + i + s] = a[t];
}
}
}
}
}
int* init_matrix(int dim){
int *matrix = (int*)malloc(dim * dim * d);
for (int i = 0; i < dim; i++){
for (int j = 0; j < dim; j++){
matrix[i * dim + j] = rand();
}
}
return matrix;
}
double test(void (*transpose)(int*, int*, int), int dim, int n){
int *dst = init_matrix(dim);
int *src = init_matrix(dim);
clock_t start = clock();
for (int i = 0; i < n; i++){
transpose(dst, src, dim);
}
clock_t end = clock();
double t = (double) (end - start) / CLOCKS_PER_SEC / n;
return t;
}
int main(){
d1 = min(D / (B / d), S * E);
printf("Block size is %d.\n", d1);
printf("transposeV1 time: %fs\n", test(transposeV1, D, N));
printf("transposeV2 time: %fs\n", test(transposeV2, D, N));
printf("transposeV3 time: %fs\n", test(transposeV3, D, N));
return 0;
}实验结果：
Block size is 16.
transposeV1 time: 0.000453s
transposeV2 time: 0.000199s
transposeV3 time: 0.000332s6.46
实验思路：
利用对称性减少运算量，对矩阵分块进行操作，分块大小为缓存块可以容纳的矩阵行数，一共测试了如下几个版本：
- v1: 普通。
- v2: 局部变量缓存。
- v3: 利用对称性减少运算量 + 局部变量缓存。
- v4: 分块。
- v5: 分块 + 局部变量缓存。
- v6: 分块 + 利用对称性减少运算量 + 局部变量缓存。
代码：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <math.h>
const int S = 64;
const int E = 8;
const int B = 64;
// 矩阵维度
const int D = 256;
// 循环次数
const int N = 1000;
// int大小
const int d = sizeof(int);
// 分块大小
int d1;
int min(int a, int b){
return (a > b) ? b : a;
}
void col_convert_v1(int *G, int dim){
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_v2(int *G, int dim){
for (int i = 0; i < dim; i++){
for (int j = 0; j < dim; j++){
int tmp = G[j * dim + i] || G[i * dim + j];
G[j * dim + i] = tmp;
G[i * dim + j] = tmp;
}
}
}
void col_convert_v3(int *G, int dim){
for (int i = 0; i < dim; i++){
for (int j = 0; j < i; j++){
int tmp = G[j * dim + i] || G[i * dim + j];
G[j * dim + i] = tmp;
G[i * dim + j] = tmp;
}
}
}
void col_convert_v4(int *G, int dim){
for (int i = 0; i < dim; i += d1){
for (int j = 0; j < dim; j += d1){
for (int s = 0; s < d1; s++){
for (int t = 0; t < d1; t++){
G[(j + t) * dim + i + s] = G[(j + t) * dim + i + s] || G[(i + s) * dim + j + t];
}
}
}
}
}
void col_convert_v5(int *G, int dim){
for (int i = 0; i < dim; i += d1){
for (int j = 0; j < dim; j += d1){
for (int s = 0; s < d1; s++){
for (int t = 0; t < d1; t++){
int tmp = G[(j + t) * dim + i + s] || G[(i + s) * dim + j + t];
G[(j + t) * dim + i + s] = tmp;
G[(i + s) * dim + j + t] = tmp;
}
}
}
}
}
void col_convert_v6(int *G, int dim){
for (int i = 0; i < dim; i += d1){
// 非分块对角元素
for (int j = 0; j < i; j += d1){
for (int s = 0; s < d1; s++){
for (int t = 0; t < d1; t++){
int tmp = G[(j + t) * dim + i + s] || G[(i + s) * dim + j + t];
G[(j + t) * dim + i + s] = tmp;
G[(i + s) * dim + j + t] = tmp;
}
}
}
// 分块对角元素
int j = i;
for (int s = 0; s < d1; s++){
for (int t = 0; t < s; t++){
int tmp = G[(j + t) * dim + i + s] || G[(i + s) * dim + j + t];
G[(j + t) * dim + i + s] = tmp;
G[(i + s) * dim + j + t] = tmp;
}
}
}
}
int* init_matrix(int dim){
int *matrix = (int*)malloc(dim * dim * d);
for (int i = 0; i < dim; i++){
for (int j = 0; j < dim; j++){
matrix[i * dim + j] = rand();
}
}
return matrix;
}
double test(void (*col_convert)(int*, int), int dim, int n){
int *G = init_matrix(dim);
clock_t start = clock();
for (int i = 0; i < n; i++){
col_convert(G, dim);
}
clock_t end = clock();
double t = (double) (end - start) / CLOCKS_PER_SEC / n;
return t;
}
int main(){
d1 = min(D / (B / d), S * E);
printf("Block size is %d.\n", d1);
printf("col_convert_v1 time: %fs\n", test(col_convert_v1, D, N));
printf("col_convert_v2 time: %fs\n", test(col_convert_v2, D, N));
printf("col_convert_v3 time: %fs\n", test(col_convert_v3, D, N));
printf("col_convert_v4 time: %fs\n", test(col_convert_v4, D, N));
printf("col_convert_v5 time: %fs\n", test(col_convert_v5, D, N));
printf("col_convert_v6 time: %fs\n", test(col_convert_v6, D, N));
return 0;
}实验结果：
Block size is 16.
col_convert_v1 time: 0.000263s
col_convert_v2 time: 0.000311s
col_convert_v3 time: 0.000135s
col_convert_v4 time: 0.000207s
col_convert_v5 time: 0.000273s
col_convert_v6 time: 0.000145s本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere