首页计软杂谈

个人实验，参考和借鉴了知乎大佬和 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 结构体

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

# 建立全局变量

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 参数

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 文件的地址便于之后文件的读入

# 初始化数组

// 初始化
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 组最后的有效块所在行数）

# 文件读入

// 文件读入
FILE *pFile = fopen(trace_name, "r");    // 打开文件
char identifier;
unsigned address;
int size;
  • 使用 fopen 函数和之前读入的 trace_name 文件的地址读入 * pFile 中，并创建 identifier，address，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);
}
  • 使用 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 模式都只执行一次

# 结束阶段

// 结束
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 [组数] 下标的范围内（该组所有有效块）寻找，如果找到则命中，并更新最后访问时间
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 []
    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），驱逐替换该块，并更新该块最后访问时间
    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 时间刻，以便于下次使用更新访问时间
++count;    // 更新时间刻

# 完整代码

#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

# 完整代码

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];
        */
    }
}