计软杂谈

个人实验，参考和借鉴了知乎大佬和 CSDN

  • 本实验上学期花了一周的时间才做完，也算是 CSAPP 中做的最认真的一个了
  • 相比于 PhaseA，PhaseB 更加的阴间和耗时
  • 在做实验的过程中参考了知乎大佬和 CSDN 上的代码，并融入了自己的 idea，希望能帮助到计软的同学（笑）

PhaseA

实验要求

  • 实现一个 cache 模拟器，运行时输入 s,b,E，要求统计命中，未命中和驱逐的次数，cache 忽略块偏移量，且采用 LRU 策略进行驱逐

实验过程

  • traces 文件中包含 I，L，S，M 四种模式：I 需要忽略，而经过分析可知 S（Store）和 L（Load）模式本质上相同（缓存中已存在直接命中，缓存中未存在则未命中，如果缓存已满则需要驱逐），而 M 模式则是先进行 L 再进行 S 模式

声明 cache_line 结构体

1
2
3
4
5
struct cache_line
{
    int tag;    //标记位
    int LRU_counter;    //最后访问时间
};
  • cache_line 中包含 tag 标记位和 LRU_counter 用于记录最后访问时间便于驱逐（Valid_bit 有效位省略而采用另一种方法）

建立全局变量

1
2
3
4
5
struct cache_line **cache;
int hit_count, miss_count, eviction_count;
int *cache_index;
int s, E, b, S;
int count = 0;    //时间刻
  • cache 结构体二级指针用于建立二维数组
  • hit_count，miss_count，eviction_count 用于记录命中，未命中和驱逐的次数
  • cache_index 以及指针用于建立一维数组来维护组有效行的个数
  • s，E，b 接收传入参数，S 便于开辟内存
  • count 作为时间刻

接收传入 s，E，b 参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int opt;
char *trace_name;    //trace文件地址
//命令行读入
while ((opt = getopt(argc, argv, "s:E:b:t:")) != -1)
{
    switch (opt)
    {
    case 's':
        s = atoi(optarg);    //读入s
        break;
    case 'E':
        E = atoi(optarg);    //读入E
        break;
    case 'b':
        b = atoi(optarg);    //读入b
        break;
    case 't':
        trace_name = optarg;    //读入地址
    default:
        break;
    }
}
  • 使用 getopt 函数将参数传入 s，E，b 中，同时创建 trace_name 字符串用于记录 trace 文件的地址便于之后文件的读入

初始化数组

1
2
3
4
5
6
7
8
9
10
 //初始化
S = pow(2, s);    //计算S=2^s
cache = (struct cache_line **)malloc(sizeof(struct cache_line *) * S);
for (int i = 0; i < S; i++)
    cache[i] = (struct cache_line *)malloc(sizeof(struct cache_line *) * E);    //cache开辟内存
for (int i = 0; i < S; i++)
    for (int j = 0; j < E; j++)
        cache[i][j].tag = cache[i][j].LRU_counter = 0;    //cache初始化
cache_index = (int *)malloc(sizeof(int) * S);    //cache_index开辟内存
memset(cache_index, 0, sizeof(int) * S);    //cache_index初始化
  • 使用 malloc 函数对 cache_line 和 cache_index 开辟内存，建立 cache_line[S][E]和 cache[S]，同时初始化为 0
    （cache_line[x][y]表示第 x 组第 y 行所存内容，cache[x]表示第 x 组最后的有效块所在行数）

文件读入

1
2
3
4
5
//文件读入
FILE *pFile = fopen(trace_name, "r");    //打开文件
char identifier;
unsigned address;
int size;
  • 使用 fopen 函数和之前读入的 trace_name 文件的地址读入*pFile 中，并创建 identifier，address，size 用于存储文件中读入的内容

读入后数据处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (fscanf(pFile, " %c %x,%d", &identifier, &address, &size) > 0)    //按行读入
{
    if (identifier == 'I')    //忽略I模式
        continue;
    int t_address = address / ((int)pow(2, s + b));    //计算标记位
    int s_address = address / ((int)pow(2, b)) % (int)(pow(2, s));    //计算索引位
    if (identifier == 'M')    //M模式两次solve
    {
        Solve(t_address, s_address);
        Solve(t_address, s_address);
    }
    else    //S模式或L模式
        Solve(t_address, s_address);
}
  • 使用 fscanf 函数按行读取 trace 文件的内容，模式读入 identifier 中，地址读入 address 中，操作范围读入 size 中
  • 由于忽略 I 模式，所以 identifier==’I’后直接 continue
  • 由于忽略块偏移量，所以无需记录地址中的块偏移部分而只需统计索引部分（s_address）和标记部分（t_address）
  • 根据读入的 s 和计算并分割出这两部分（t_address=⌊address / 2^(s+b) ⌋，
    s_address=⌊address/ 2^b ⌋mod 2^s）
  • 由于 L 模式和 S 模式操作方式相同，而 M 模式是 L 模式+S 模式，所以可以只写一个 solve 函数，对于 M 模式执行两次，而对于 L 和 S 模式都只执行一次

结束阶段

1
2
3
4
5
//结束
free(cache);
free(cache_index);    //释放内存
fclose(pFile);    //关闭文件
printSummary(hit_count, miss_count, eviction_count);    //输出
  • 释放开辟的内存并关闭文件
  • 调用 printSummary 输出命中，未命中和驱逐的个数

solve 函数

前提：同一个组内，有效块按访问时间顺序依次顺序存储（组未满状态下），且使用 cache_index 来记录该组最后的有效块所在行数

  • 不论 Store 还是 Load 都存在两种状态：缓存中已存在——命中，缓存中不存在——未命中
  • 1.命中状态（find_flag=1）
  • 基本思想：在 cache_index[组数]下标的范围内（该组所有有效块）寻找，如果找到则命中，并更新最后访问时间
1
2
3
4
5
6
7
8
9
10
11
int find_flag = 0;    //寻找哨兵
for (int i = 0; i < cache_index[s_address]; i++)
{
    if (cache[s_address][i].tag == t_address)   //找到
    {
        ++hit_count;
        cache[s_address][i].LRU_counter = count;
        find_flag = 1;
        break;
    }
}
    1. 不命中状态（find_flag=0）
  • 基本思想：在该组所有有效行中都寻找不到，则未命中。此时分两种情况：
    • 2.1. 组未满：
    • 无需驱逐，仅需在 cache[组数][]中向后插入该有效块，并更新最后访问时间和该组 cache_line[]
    1
    2
    3
    4
    5
    6
    if (cache_index[s_address] != E) //组未满
    {
        ++miss_count;    //未命中
        cache[s_address][cache_index[s_address]].tag = t_address;    //更新缓存
        cache[s_address][cache_index[s_address]++].LRU_counter = count;    //更新最后访问时间
    }
    • 2.2. 组已满：
    • 需要驱逐，此时在该组中寻找访问时间最小的有效块（LRU），驱逐替换该块，并更新该块最后访问时间
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    else //组已满，需要LRU
    {
        ++eviction_count;    //驱逐
        ++miss_count;    //未命中
        int min_count = cache[s_address][0].LRU_counter;    //最后访问时间最远块访问时间
        int min_count_index = 0;    //最后访问时间最远块下标
        for (int i = 1; i < E; i++)
            if (cache[s_address][i].LRU_counter < min_count)
            {
                min_count = cache[s_address][i].LRU_counter;    //更新最后访问时间最远块访问时间
                min_count_index = i;    //更新最后访问时间最远块下标
            }
        cache[s_address][min_count_index].tag = t_address;    //更新缓存
        cache[s_address][min_count_index].LRU_counter = count;    //更新最后访问时间
    }
  • 在 solve 函数结束后更新 count 时间刻，以便于下次使用更新访问时间
1
++count;    //更新时间刻

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "cachelab.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>
#include <math.h>
#include <string.h>
struct cache_line
{
    int tag;    //标记位
    int LRU_counter;    //最后访问时间
};
struct cache_line **cache;
int hit_count, miss_count, eviction_count;
int *cache_index;
int s, E, b, S;
int count = 0;    //时间刻
void Solve(int t_address, int s_address)
{
    int find_flag = 0;    //寻找哨兵
    for (int i = 0; i < cache_index[s_address]; i++)
    {
        if (cache[s_address][i].tag == t_address)   //找到
        {
            ++hit_count;
            cache[s_address][i].LRU_counter = count;
            find_flag = 1;
            break;
        }
    }
    if (!find_flag) //未找到
    {
        if (cache_index[s_address] != E) //组未满
        {
            ++miss_count;    //未命中
            cache[s_address][cache_index[s_address]].tag = t_address;    //更新缓存
            cache[s_address][cache_index[s_address]++].LRU_counter = count;    //更新最后访问时间
        }
        else //组已满，需要LRU
        {
            ++eviction_count;    //驱逐
            ++miss_count;    //未命中
            int min_count = cache[s_address][0].LRU_counter;    //最后访问时间最远块访问时间
            int min_count_index = 0;    //最后访问时间最远块下标
            for (int i = 1; i < E; i++)
                if (cache[s_address][i].LRU_counter < min_count)
                {
                    min_count = cache[s_address][i].LRU_counter;    //更新最后访问时间最远块访问时间
                    min_count_index = i;    //更新最后访问时间最远块下标
                }
            cache[s_address][min_count_index].tag = t_address;    //更新缓存
            cache[s_address][min_count_index].LRU_counter = count;    //更新最后访问时间
        }
    }
    ++count;    //更新时间刻
}
int main(int argc, char *argv[])
{
    int opt;
    char *trace_name;    //trace文件地址
    //命令行读入
    while ((opt = getopt(argc, argv, "s:E:b:t:")) != -1)
    {
        switch (opt)
        {
        case 's':
            s = atoi(optarg);    //读入s
            break;
        case 'E':
            E = atoi(optarg);    //读入E
            break;
        case 'b':
            b = atoi(optarg);    //读入b
            break;
        case 't':
            trace_name = optarg;    //读入地址
        default:
            break;
        }
    }
    //初始化
    S = pow(2, s);    //计算S=2^s
    cache = (struct cache_line **)malloc(sizeof(struct cache_line *) * S);
    for (int i = 0; i < S; i++)
        cache[i] = (struct cache_line *)malloc(sizeof(struct cache_line *) * E);    //cache开辟内存
    for (int i = 0; i < S; i++)
        for (int j = 0; j < E; j++)
            cache[i][j].tag = cache[i][j].LRU_counter = 0;    //cache初始化
    cache_index = (int *)malloc(sizeof(int) * S);    //cache_index开辟内存
    memset(cache_index, 0, sizeof(int) * S);    //cache_index初始化
    //文件读入
    FILE *pFile = fopen(trace_name, "r");    //打开文件
    char identifier;
    unsigned address;
    int size;
    //处理
    while (fscanf(pFile, " %c %x,%d", &identifier, &address, &size) > 0)    //按行读入
    {
        if (identifier == 'I')    //忽略I模式
            continue;
        int t_address = address / ((int)pow(2, s + b));    //计算标记位
        int s_address = address / ((int)pow(2, b)) % (int)(pow(2, s));    //计算索引位
        if (identifier == 'M')    //M模式两次solve
        {
            Solve(t_address, s_address);
            Solve(t_address, s_address);
        }
        else    //S模式或L模式
            Solve(t_address, s_address);
    }
    //结束
    free(cache);
    free(cache_index);    //释放内存
    fclose(pFile);    //关闭文件
    printSummary(hit_count, miss_count, eviction_count);    //输出
    return 0;
}

PhaseB

实验要求

  • 优化转置矩阵的代码，使其未命中率尽可能低
  • 矩阵大小分别为 32*32,64*64 和 61*67，由于不同矩阵大小的代码可能不同，所以所写代码只对测试的三组数据进行优化
  • 从老师所给的 PPT 和 pdf 中可以知道对矩阵分组（blocking）可以有效地提升缓存命中率

前提：从导出的 trans.f0 文件中可以得知，使用./test-trans 命令测试得出的未命中数量比实际的多 3（valgrind 模拟额外开销）
以下提及的所有未命中均为实际未命中数量，如需转换到命令输出需加 3

32*32（理论最优 256）

基准测试

  • 经过测试，文件自带转置函数对于 32*32 矩阵转置未命中为 1180
命中率分析
  • A：（156 未命中，15.23%未命中率）
    1
  • B：（1024 未命中，100%未命中率）
    2
  • 在 A 矩阵遍历每一行时，B 中每一列的每个元素每隔 8 行都会发生冲突不命中，如此造成低命中率

第一次优化

  • 由于是每隔 8 行发生不命中，所以首先考虑 8*8 矩阵分块。注意到每个缓存块中正好能存放 8 个整型，且每个分块除对角线互不干扰（不会发生驱逐），如此一来按块进行转置，每个块中不会发生大量的冲突不命中，且块与块之间绝对不会发生冲突。所以 8*8 分块是可行的
  • 代码
    4
  • 经过测试，8*8 对于 32*32 矩阵转置未命中为 340
    3
命中率分析
  • A：（156 未命中，15.23%未命中率）
    5
  • B：（184 未命中 17.97%未命中率）
    6
  • A 没有发生变化而 B 命中率大大提高，但总未命中数仍然超过 300

第二次优化

  • 注意到 A 矩阵中元素仍然会和 B 矩阵中元素互相冲突，导致 A 矩阵的对角线和 B 矩阵对角线上一格元素发生冲突不命中，具体解释如图所示：
    7
  • 大部分冲突命中均发生在 A 和 B 的相邻操作中（红色画圈部分），所以可以考虑先同时对 A 块中的同一行进行读取操作，再同时对 B 块对应列进行写入操作，这样便可以消除相邻操作带来的冲突不命中
  • 替换内部循环代码为：
    8
  • 经过测试，8*8 对于 32*32 矩阵转置未命中为 284，已达到满分标准
    9
命中率分析
  • A：（128 未命中，12.5%未命中率）
    10
  • B：（156 未命中，15.23%未命中率）
    11

64*64（理论最优 1024）

基准测试

  • 相比于 32*32 矩阵缓存能存放 8 行元素，64*64 矩阵缓存只能存放 4 行元素
  • 首先尝试和上题一样 8*8 分块并一次性读取一行（代码省略）
  • 经过测试，8*8 并一次性读取对于 64*64 矩阵转置未命中为 4608，几乎没有提升
    12
  • 文件自带转置函数未命中为 4720
    13
命中率分析
  • A：（512 未命中，12.5%未命中率）
    14
  • B：（4096 未命中，100%未命中率）
    15
  • 由于每次对 A 一次性读取一行，所以 A 矩阵的命中率得到了提升（12.5%未命中率）
  • 但由于缓存只能存下矩阵前 4 行元素，B 矩阵在读取后 4 列时会覆盖前 4 列，同时读取前 4 列时会覆盖后 4 列，导致每个元素都发生了冲突不命中（初始为冷不命中）
    16
    （红色箭头表示冲突不命中）

第一次优化

  • 由于前后 4 列会互相覆盖，所以考虑将 8*8 分块改为 4*4 分块，每次一次性读取一行，这样便能降低 B 矩阵的未命中率
  • 代码：
    17
  • 经过测试，4*4 并一次性读取对于 64*64 矩阵转置未命中为 1696，有了较大的提升，但依然没有小于 1300
    18
命中率分析
  • A：（576，14.06%未命中率）
    19
  • B：（1120，27.34%未命中率）
    20
  • B 矩阵由于降低分块大小且仍然一次性读取一行，不再 100%未命中率，但由于采用了 4*4 分块，在非对角线块内部仍然会发生大量冲突不命中，未命中率为 25%，而在对角线块上由于 A 矩阵和 B 矩阵所映射到相同的缓存块，导致 A 矩阵和 B 矩阵发生冲突不命中，未命中率更高
    21
    （非对角线块）
  • 由此可见单纯的 4*4 分块已经达到了极限，需要更进一步的优化

第二次优化

  • 由于缓存中能存放 8 个整型，所以考虑先进行 8*8 分块，而在大块内部再进行 4*4 分块操作
    为了最大化的利用缓存，尽可能低减少冲突，考虑在 8*8 大块内部进行三步操作：

这里的思想参考了某位大神，这里着重分析
每个 8*8 块中的 4*4 块按行顺序将块被标记为 1,2,3,4 块

  • 1.首先对 A 矩阵的 1,2 块一次性读取一行 8 个元素，并按列分别移入 B 矩阵的 1 块和 2 块中
    22
  • 2.对 A 矩阵的 3 块按列读取，对 B 矩阵的 2 块按行读取，将读取到的 A 矩阵按行移入 B 矩阵的 2 块，将读取到的 B 矩阵按行移入 B 矩阵的 3 块（两次读取后直接进行移入）
    23
  • 3.对 A 矩阵的 4 块一次性读取两行，并按列移入 B 矩阵的 4 块中
    24
  • 代码：
    25
  • 经过测试，该方法对于 64*64 矩阵转置未命中为 1160，已达到满分标准
    26
命中率分析
  • A：（552，13.48%未命中率）
    34
  • B：（608，14.84%未命中率）
    35
  • 对于对角块：
    • 第一步对 A 矩阵的 1,2 块一次性读取一行 8 个元素，A 矩阵的 1,2 块的未命中率降低为 12.5%（本来为 25%），由于充分使用了缓存块，提升了 A 矩阵命中率
    • 对于 B 矩阵按列移入 1,2 块，在首次写入 1 块的第一列时冷不命中，同时缓存被写入相对应行中元素，所以 2 块所有元素在这一步中会全部命中，而仅仅会在 1 块的对角线上发生冲突不命中
    • 第二步先对 A 矩阵的 3 块按列读取，对 B 矩阵的 2 块按行读取
    • A 矩阵首次读取 3 块第一列发生冲突不命中，而在之后的的读取中对角线上元素会和 B 矩阵发生冲突不命中，而对于 B 矩阵，由于按行进行读取，所以冲突不命中仅仅发生在 2 块的第一列上
    • 将读取到的 A 矩阵按行移入 B 矩阵的 2 块，将读取到的 B 矩阵按行移入 B 矩阵的 3 块（注意行列顺序）
    • 由于之前在读取时已按行将 B 矩阵存入缓存中，所以 B 矩阵 2 块上会全部命中，而仅仅在移入 3 块时在每一列上发生冲突不命中
    • 第三步对 A 矩阵的 4 块一次性读取两行，并按列移入 B 矩阵的 4 块中
    • 和之前 4*4 分块类似，但选择一次性读入两行相比于一次性读取一行能小幅提升命中率
  • 对于非对角块：
    • 三步操作都仅仅会在 4 个小块的第一列上发生冲突不命中，未命中率均为 12.5%，对于 B 矩阵来说命中率大大提升

61*67

  • 由于 61 和 67 都是素数，无法被 8 整除，所以在缓存中会发生错位现象，如图所示
    27
    （A 矩阵 67*61 部分缓存映射关系）
  • 矩阵不是正方形，A 矩阵和 B 矩阵的行数和列数并不相等，所以直接分析相比于之前会非常困难，且效率也不高，所以本情况不再详细分析
  • 由于冲突不命中的概率相比于 64*64 会下降，所以块的大小可以适当加大，此外对于不能分块的区域需要分开处理

第一次优化

  • 首先考虑和 64*64 矩阵一样的转置方法：
    将 61*67 的 56*64 部分采用和之前一样的方法，而对于剩下的部分采用最原始的直接转置法：
    28
  • 经测试，未命中为 2058，已经非常接近 2000：
    29
  • 剩下的矩阵考虑分成 3 大部分：
  • 第一部分（A[64][0]~A[67][59]）
  • 分成 3*6 的块，每次一次性读取一行进行转置
  • 第二部分（A[0][56]~A[63][59]）
  • 一次性读取一行进行转置
  • 第三部分（A[64][60]~A[66][60]）
  • 直接转置
  • 剩下部分的代码：（不完整）
    30
  • 经测试，未命中为 1971，已达到了满分标准，但还有优化空间
    31

第二次优化

  • 经过测试，发现存在更优解：
  • 将 61*67 的 60*60 部分分成 20*4 的块，每次一次性读取两行
  • 剩下的矩阵考虑分成 2 大部分：
  • 第一部分（A[0][60]~A[66][60]）
  • 直接转置
  • 第二部分（A[60][0]~A[66][59]）
  • 一次性读取一列进行转置（非按行读取）
  • 代码：
    32
  • 经测试，未命中为 1750，有了较大幅度的优化，同时代码复杂度也大大下降
    33

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, ii;
    int x0, x1, x2, x3, x4, x5, x6, x7;
    if (M == 32) //32x32矩阵
    {
        for (i = 0; i < 32; i += 8)
            for (j = 0; j < 32; j += 8)     //8x8分块
                for (ii = i; ii < i + 8; ii++)
                {
                    x0 = A[ii][j];      x1 = A[ii][j + 1];
                    x2 = A[ii][j + 2];  x3 = A[ii][j + 3];
                    x4 = A[ii][j + 4];  x5 = A[ii][j + 5];
                    x6 = A[ii][j + 6];  x7 = A[ii][j + 7];  //每次一次性读取一行，存入x0~x7
                    B[j][ii] = x0;      B[j + 1][ii] = x1;
                    B[j + 2][ii] = x2;  B[j + 3][ii] = x3;
                    B[j + 4][ii] = x4;  B[j + 5][ii] = x5;
                    B[j + 6][ii] = x6;  B[j + 7][ii] = x7;  //移入B矩阵
                }
    }
    else if (M == 64) //64x64矩阵
    {
        for (i = 0; i < 64; i += 8)
            for (j = 0; j < 64; j += 8) //先8x8分块
            {
                //8x8大块中进行3步操作
                for (ii = i; ii < i + 4; ii++)  //A矩阵的1,2块
                {
                    x0 = A[ii][j];      x1 = A[ii][j + 1];
                    x2 = A[ii][j + 2];  x3 = A[ii][j + 3];
                    x4 = A[ii][j + 4];  x5 = A[ii][j + 5];
                    x6 = A[ii][j + 6];  x7 = A[ii][j + 7];  //一次性读取一行，存入x0~x7
                    B[j][ii] = x0;      B[j + 1][ii] = x1;
                    B[j + 2][ii] = x2;  B[j + 3][ii] = x3;  //按列移入B矩阵1块
                    B[j][ii + 4] = x4;  B[j + 1][ii + 4] = x5;
                    B[j + 2][ii + 4] = x6;  B[j + 3][ii + 4] = x7;  //按列移入B矩阵2块
                }
                for (ii = j; ii < j + 4; ii++)  //A矩阵的3块和B矩阵的2块
                {
                    x0 = A[i + 4][ii];  x1 = A[i + 5][ii];
                    x2 = A[i + 6][ii];  x3 = A[i + 7][ii];  //按列读取A矩阵3块
                    x4 = B[ii][i + 4];  x5 = B[ii][i + 5];
                    x6 = B[ii][i + 6];  x7 = B[ii][i + 7];  //按行读取B矩阵2块
                    B[ii][i + 4] = x0;  B[ii][i + 5] = x1;
                    B[ii][i + 6] = x2;  B[ii][i + 7] = x3;  //按行移入B矩阵2块
                    B[ii + 4][i] = x4;  B[ii + 4][i + 1] = x5;
                    B[ii + 4][i + 2] = x6;  B[ii + 4][i + 3] = x7;  //按行移入B矩阵3块
                }
                for (ii = i + 4; ii < i + 8; ii += 2)   //A矩阵的4块
                {
                    x0 = A[ii][j + 4];      x1 = A[ii][j + 5];
                    x2 = A[ii][j + 6];      x3 = A[ii][j + 7];
                    x4 = A[ii + 1][j + 4];  x5 = A[ii + 1][j + 5];
                    x6 = A[ii + 1][j + 6];  x7 = A[ii + 1][j + 7];  //一次性读取两行，存入x0~x7
                    B[j + 4][ii] = x0;      B[j + 5][ii] = x1;
                    B[j + 6][ii] = x2;      B[j + 7][ii] = x3;
                    B[j + 4][ii + 1] = x4;  B[j + 5][ii + 1] = x5;
                    B[j + 6][ii + 1] = x6;  B[j + 7][ii + 1] = x7;  //移入B矩阵
                }
            }
    }
    else //61x67矩阵
    {
        //以下为1750miss方法
        for (i = 0; i < 60; i += 20)
            for (j = 0; j < 60; j += 4) //60x60部分进行20x4分块
                for (ii = i; ii < i + 20; ii += 2)
                {
                    x0 = A[ii][j];          x1 = A[ii][j + 1];
                    x2 = A[ii][j + 2];      x3 = A[ii][j + 3];
                    x4 = A[ii + 1][j];      x5 = A[ii + 1][j + 1];
                    x6 = A[ii + 1][j + 2];  x7 = A[ii + 1][j + 3];  //一次性读取两行，存入x0~x7
                    B[j][ii] = x0;          B[j + 1][ii] = x1;
                    B[j + 2][ii] = x2;      B[j + 3][ii] = x3;
                    B[j][ii + 1] = x4;      B[j + 1][ii + 1] = x5;
                    B[j + 2][ii + 1] = x6;  B[j + 3][ii + 1] = x7;  //移入B矩阵
                }
        for (i = 0; i < 67; i++)    //A[0][60]~A[66][60]部分直接转置
            B[60][i] = A[i][60];
        for (i = 0; i < 60; i++)    //A[60][0]~A[66][59]部分
        {
            x0=A[60][i];    x1=A[61][i];
            x2=A[62][i];    x3=A[63][i];
            x4=A[64][i];    x5=A[65][i];
            x6=A[66][i];    //一次性读取一列，存入x0~x6
            B[i][60]=x0;    B[i][61]=x1;
            B[i][62]=x2;    B[i][63]=x3;
            B[i][64]=x4;    B[i][65]=x5;
            B[i][66]=x6;    //移入B矩阵
        }
        /*
        //以下为1971miss方法
        for (i = 0; i < 64; i += 8)
            for (j = 0; j < 56; j += 8) //64x56部分进行8x8分块
            {
                for (ii = i; ii < i + 4; ii++)  //以下方法同64x64
                {
                    x0 = A[ii][j];      x1 = A[ii][j + 1];
                    x2 = A[ii][j + 2];  x3 = A[ii][j + 3];
                    x4 = A[ii][j + 4];  x5 = A[ii][j + 5];
                    x6 = A[ii][j + 6];  x7 = A[ii][j + 7];
                    B[j][ii] = x0;      B[j + 1][ii] = x1;
                    B[j + 2][ii] = x2;  B[j + 3][ii] = x3;
                    B[j][ii + 4] = x4;  B[j + 1][ii + 4] = x5;
                    B[j + 2][ii + 4] = x6;  B[j + 3][ii + 4] = x7;
                }
                for (ii = j; ii < j + 4; ii++)
                {
                    x0 = A[i + 4][ii];  x1 = A[i + 5][ii];
                    x2 = A[i + 6][ii];  x3 = A[i + 7][ii];
                    x4 = B[ii][i + 4];  x5 = B[ii][i + 5];
                    x6 = B[ii][i + 6];  x7 = B[ii][i + 7];
                    B[ii][i + 4] = x0;  B[ii][i + 5] = x1;
                    B[ii][i + 6] = x2;  B[ii][i + 7] = x3;
                    B[ii + 4][i] = x4;  B[ii + 4][i + 1] = x5;
                    B[ii + 4][i + 2] = x6;  B[ii + 4][i + 3] = x7;
                }
                for (ii = i + 4; ii < i + 8; ii += 2)
                {
                    x0 = A[ii][j + 4];      x1 = A[ii][j + 5];
                    x2 = A[ii][j + 6];      x3 = A[ii][j + 7];
                    x4 = A[ii + 1][j + 4];  x5 = A[ii + 1][j + 5];
                    x6 = A[ii + 1][j + 6];  x7 = A[ii + 1][j + 7];
                    B[j + 4][ii] = x0;      B[j + 5][ii] = x1;
                    B[j + 6][ii] = x2;      B[j + 7][ii] = x3;
                    B[j + 4][ii + 1] = x4;  B[j + 5][ii + 1] = x5;
                    B[j + 6][ii + 1] = x6;  B[j + 7][ii + 1] = x7;
                }
            }
        for (j = 0; j < 60; j += 6)
            for (ii = 64; ii < 67; ii++)    //A[64][0]~A[67][59]部分进行3x6分块
            {
                x0 = A[ii][j];      x1 = A[ii][j + 1];
                x2 = A[ii][j + 2];  x3 = A[ii][j + 3];
                x4 = A[ii][j + 4];  x5 = A[ii][j + 5];  //一次性读取一行
                B[j][ii] = x0;      B[j + 1][ii] = x1;
                B[j + 2][ii] = x2;  B[j + 3][ii] = x3;
                B[j + 4][ii] = x4;  B[j + 5][ii] = x5;
            }
        for (i = 0; i < 64; i ++)   //A[0][56]~A[63][59]部分
        {
            x0 = A[i][56]; x1 = A[i][57];
            x2 = A[i][58]; x3 = A[i][59];   //一次性读取一行
            x4 = A[i][60]; B[56][i] = x0;
            B[57][i] = x1; B[58][i] = x2;
            B[59][i] = x3; B[60][i] = x4;
        }
        B[60][64] = A[64][60];  //剩余直接转置
        B[60][65] = A[65][60];
        B[60][66] = A[66][60];
        */
    }
}

Leave a comment

waline