CSAPP cache lab – Optimizing Matrix Transpose

CSAPP cache lab part B

矩阵转置

矩阵转置是一种操作，它将矩阵的行和列互换位置，即将原始矩阵的行变为转置矩阵的列，将原始矩阵的列变为转置矩阵的行。转置操作可以通过改变矩阵的布局来方便地进行某些计算和分析。

假设有一个m×n的矩阵A，其转置矩阵为n×m的矩阵B。那么B的第i行第j列的元素就是A的第j行第i列的元素，即B[i][j] = A[j][i]。

例如，对于以下矩阵A：

A = [ 123 ][ 456 ]

其转置矩阵B为：

B = [ 14 ][ 25 ][ 36 ]

可以看到，B的第一行是A的第一列，B的第二行是A的第二列，以此类推。

矩阵转置在很多领域中都有广泛的应用，例如线性代数、图像处理、矩阵运算等。它可以用于求解线性方程组、计算矩阵的逆、矩阵相乘等操作。在编程中，可以使用循环和临时变量来实现矩阵转置，也可以使用现有的矩阵库或数学库提供的函数来完成转置操作。

part B 背景

已经实现了矩阵转置函数，需要通过提高cache hit的方式，提高性能。
int 类型通常是4bytes。

3种格式的矩阵:

预期:

cache 的参数:
s = 5, E = 1, b = 5

使用 cache blocking 优化 Matrix Transpose

执行matrix transpose 函数:

./test-trans -M 32 -N 32

test-trans 会生成 trace.f0 和trace.f1文件，

./csim-ref -v -s 5 -E 1 -b 5 -t trace.f0 | less

32 x 32 的case, 使用分块将miss从1183降低到了343。
对于32 x 32:
A[0][0] 的地址：602100 – A[0][7], set: 8
A[8][0] 的地址：602500 – A[8][7], set: 8
B[0][0] 的地址：642100 – B[0][7], set: 8
B[8][0] 的地址：642500 – B[8][7], set: 8
建议bszie 为8。

但是64 x 64的case 的miss 没有降低。
对于64 x 64:
A[0][0] 的地址：602100 – A[0][7], set: 8
A[4][0] 的地址：602500 – A[4][7], set: 8
B[0][0] 的地址：642100 – B[0][7], set: 8
B[4][0] 的地址：642500 – B[4][7], set: 8

为了减少缓存冲突，bsize建议设置为4。
当bsize == 4时，miss 下降到1891。

不同的blcok size会对cache miss 产生影响；

关于cache miss:

1. A[0][0] 和 B[0][0], A[0][1] (602104)的setIndex 都是8, 存在cahce miss
2. empty cache 会导致miss
   主要是以上两种情况导致的cache miss。
   
   A[i][j] 到 A[i][j+bsize-1] 应该都是在同一个cache block ，再一次迭代将一个block的一行数据读出，可以减少缓存冲突，提高了局部访问，从而降低miss，让miss 降低1699。
   
   同样，32 x 32的case, 也可以降低缓存冲突。
   
   降低到300以下：
   
   回到64 x 64的case, 使用4 x 4的block, 不能充分利用cache block, 会有4个block的浪费，所以存在优化空间。

由于 61 x 67, 每个cache line 不能保存完整的行，建议是使用较大的block, bsize为17时，可以满足miss 低于2000。

cache blocking

Cache blocking，也称为循环阻塞或循环平铺，是一种在高性能计算中用于优化内存的技术，特别是对涉及嵌套循环和数据结构（如矩阵）的算法。Cache blocking 的主要目标是改善数据局部性，减少缓存失效的次数，从而提高整个程序的性能。

以下是对 cache blocking 的概述：

1. 动机:

   • 缓存层次结构： 现代计算机体系结构通常具有内存层次结构，包括寄存器、L1、L2甚至L3缓存，以及主内存。从较高层次的内存中访问数据比从较低层次的内存中访问数据更快。
   • 缓存行大小： 数据在内存层次结构之间以固定大小的块（称为缓存行）传输。有效地利用这些缓存行对于优化内存访问至关重要。

2. 基本思想:

   • 循环嵌套优化： Cache blocking 通常应用于嵌套循环，这在科学计算和数值计算中很常见。其思想是将嵌套循环的迭代空间划分为适应缓存的小而连续的块。

3. 技术:

   • 划分迭代空间： 将嵌套循环划分为迭代块，然后结构化算法以一次处理这些块。这减小了工作集大小，提高了空间局部性。
   • 数据重用： 通过在适应缓存的小块上操作，算法内部可以重复使用相同的数据，减少了从内存层次结构较慢的部分重新加载数据的需求。

4. 优势:

   • 减少缓存失效： Cache blocking 通过确保算法访问的数据在需要时位于缓存中，帮助最小化了缓存失效次数。
   • 改善空间局部性： 具有空间局部性的数据访问模式提高了整体内存访问的效率，更好地利用了缓存行。

5. 实现:

   • 编译器优化： 一些编译器可以在代码编译期间自动应用 cache blocking 转换。
   • 手动优化： 程序员也可以通过手动重组他们的代码来手动应用 cache blocking 技术。

6. 应用:

   • 矩阵乘法： Cache blocking 在优化矩阵乘法算法中经常被使用。
   • 数值计算： 对涉及密集矩阵、卷积操作和其他数值计算的算法来说，cache blocking 是有益的。

Cache blocking 是一种重要的优化技术，特别是在科学计算和数值分析中，其中算法的性能往往受制于内存访问模式。通过精心管理数据局部性，cache blocking 有助于充分利用现代计算机体系结构的层次结构，从而实现更好的性能。

分块

使用分块，列也可以利用cache hit提高算法效率。

不使用分块一次迭代，可能出发多次line i的缓存冲突。

cache blocking 论文

推荐 “Cache Performance of Blocked Algorithms” by Monica S. Lam, Edward E. Rothberg, and Michael E. Wolf
这是一篇经典的论文，探讨了在矩阵乘法等计算中如何通过缓存块来优化性能。这篇论文发表在1991年的 ACM SIGPLAN 论文集上。

函数指针

指向函数的指针是一种特殊类型的指针，它可以指向函数的内存地址。通过函数指针，可以将函数作为参数传递给其他函数、在运行时动态选择要调用的函数，或者将函数作为返回值返回。

函数指针的声明方式与普通指针相似，只是在声明时需要指定函数的返回类型和参数列表。例如，以下是一个指向函数的指针的声明示例：

int (*func_ptr)(int, int);

在上述声明中，func_ptr是一个指向返回类型为int，参数列表为两个int类型的函数的指针。可以通过将函数的名称赋值给函数指针来进行初始化，如下所示：

int sum(int a, int b) {return a + b;}int main() {int (*func_ptr)(int, int) = sum;int result = func_ptr(3, 4); // 调用sum函数，将结果赋值给result变量return 0;}

在上述示例中，将函数sum的地址赋值给了函数指针func_ptr，然后可以通过函数指针来调用函数并获取结果。

通过函数指针，可以实现函数的动态调用和多态性，使得代码更加灵活和可扩展。

c语言二维数组的地址

在C或C++中，static int A[256][256]; 和 static int B[256][256]; 这样的静态多维数组的地址是固定的。静态数组在程序运行时在全局数据区分配内存，其地址在整个程序执行期间保持不变

在大多数操作系统中，程序的全局静态数据区（Global Static Data Area）通常在程序加载时被分配，并且在整个程序运行期间保持不变。这包括全局变量、静态变量以及静态数组等。因此，如果你多次执行程序，这些全局静态数据的地址通常不会改变。

当程序加载到内存时，操作系统会为全局静态数据分配内存，并将其初始化。这些数据存储在固定的内存位置，以便程序可以随时访问它们。因此，每次运行程序时，全局静态数据区的地址保持不变。

这种行为有助于确保程序能够正常访问全局静态数据，并且程序中的其他部分可以依赖这些数据的固定位置。但是请注意，这种固定性仅适用于全局静态数据，而不适用于局部变量或动态分配的内存（例如使用 malloc 或 new 分配的内存），它们的地址可能在运行时变化。

主流优化缓存命中

缓存命中对于提高计算机系统性能非常关键。以下是一些主流的优化缓存命中的方法：

1. 局部性原理（Locality Principle）：

   • 时间局部性：访问的数据很可能在不久的将来再次被访问。
   • 空间局部性：访问的数据附近的数据很可能在不久的将来被访问。

2. 缓存友好的数据结构：

   • 尽量使用数组而不是链表，因为数组的元素在内存中是连续存储的，有较好的空间局部性。
   • 对于多维数组，尽量按照主要方向顺序存储数据，以增加空间局部性。

3. 缓存对齐（Cache Alignment）：

   • 将数据结构和数组按照缓存行的大小对齐，以减少缓存行的浪费。

4. 循环展开（Loop Unrolling）：

   • 将循环中的迭代次数展开，减少循环的迭代次数，提高局部性。

5. 软件预取（Software Prefetching）：

   • 在代码中预测未来可能会使用的数据，并在需要时提前将其加载到缓存中，以减少缓存未命中。

6. 避免假共享（False Sharing）：

   • 确保不同线程使用的数据不共享同一缓存行，以避免因为一个线程修改数据而导致其他线程的缓存无效。

7. 缓存感知型算法：

   • 一些算法可以被设计为更加缓存友好，例如分块算法（Tiling）。

8. 数据压缩：

   • 在某些情况下，通过使用压缩算法可以减少数据传输的量，从而减少缓存需求。

9. 硬件级别的优化：

   • 利用硬件指令集中的一些优化指令，如SSE（Streaming SIMD Extensions）等，来提高对缓存的利用率。

10. 分级缓存（Cache Hierarchy）优化：

    • 了解和合理利用不同级别的缓存，以最大化缓存命中率。

tiling 和 blocking 的区别？

“Blocking” 和 “tiling” 都是优化算法以提高缓存利用率的技术。尽管它们的目标相似，但它们在实现上有一些细微的差别：

1. Blocking（块级优化）：

   • 概念： Blocking 通过将数据划分为小块（块），然后按块处理，以提高数据局部性。
   • 操作： 对于一个矩阵，可以将其分割为较小的子矩阵（块），然后按块进行计算。这有助于提高空间局部性，因为它使得相邻的数据在物理内存中更加接近，减少了缓存未命中的可能性。
   • 实现： 常用于优化矩阵运算，如矩阵乘法。算法会按块处理矩阵，以减少对主存的访问次数。

2. Tiling（瓦片优化）：

   • 概念： Tiling 是一种更广泛的优化方法，它涵盖了 blocking 的概念，但更一般地用于描述将计算分解为小的、独立的任务单元，这些任务单元可以并行执行，从而提高缓存利用率。
   • 操作： 与 blocking 类似，通过将数据分割成小块（瓦片）并按瓦片进行计算，以提高局部性。但在某些上下文中，瓦片也可能指的是分割问题空间，使得可以并行地处理各个瓦片。
   • 实现： Tiling 不仅适用于矩阵运算，还可用于其他类型的问题，包括图像处理、信号处理等。

总的来说，blocking 是 tiling 的一个特例。Tiling 的概念更加通用，可以适用于不同类型的问题，而 blocking 更专注于按块处理数据以提高空间局部性。在许多上下文中，这两个术语可能会被交替使用。

硬件和软件缓存

硬件实现的缓存和软件实现的缓存是两种不同的概念，它们分别指的是在计算机系统中由硬件和软件管理的缓存。

1. 硬件实现的缓存：

   • 位置： 硬件缓存是由计算机体系结构中的硬件组件实现和管理的。通常，现代计算机体系结构包括多层次的硬件缓存，如L1、L2和L3缓存。
   • 管理： 硬件缓存的管理是透明的，即它由硬件自动完成，而不需要软件的直接干预。硬件使用一些缓存替换策略和预取算法，以提高缓存的效率和性能。
   • 访问速度： 由于硬件缓存是直接嵌入到处理器芯片中的，它们通常具有非常快的访问速度。

2. 软件实现的缓存：

   • 位置： 软件缓存是在应用程序或操作系统级别由软件实现的，而不是由硬件实现的。这可能涉及到在主存储器中维护缓存结构，例如软件缓存池。
   • 管理： 软件缓存的管理需要软件程序员手动实现，包括数据的存储、检索、替换和更新。软件缓存通常需要更多的软件开发和维护工作。
   • 访问速度： 与硬件缓存相比，由于软件缓存是在主存储器中实现的，其访问速度可能相对较慢。

总的来说，硬件实现的缓存是通过处理器芯片内的硬件组件实现和管理的，而软件实现的缓存是通过软件层面的数据结构和算法来实现的。硬件缓存通常更为高效，但软件缓存允许更大的灵活性和可编程性。在实际应用中，两者可能会结合使用以最大程度地提高系统性能。

软件缓存的例子

软件实现的缓存通常涉及在应用程序或操作系统层面手动管理数据的存储、检索和更新。以下是一些软件实现的缓存的例子：

1. 文件系统缓存：

   • 操作系统通常维护一个文件系统缓存，用于存储最近读取或写入的文件块。这样，如果相同的数据被多次访问，就可以从缓存中读取，而不是重新访问磁盘。

2. 数据库查询缓存：

   • 在数据库查询中，可以手动实现一个查询结果的缓存，以避免重复执行相同的查询。如果之前已经执行过某个查询并且结果没有发生变化，就可以从缓存中获取结果，而不必再次查询数据库。

3. Web应用程序缓存：

   • Web应用程序可以使用缓存来存储页面内容、图像或其他资源，以减少对服务器的请求。浏览器缓存是其中的一种形式，它可以缓存页面元

docker 的坑

https://zhuanlan.zhihu.com/p/342594115

links

https://zhuanlan.zhihu.com/p/112040924
https://zhuanlan.zhihu.com/p/79058089
https://zhuanlan.zhihu.com/p/387662272
https://blog.csdn.net/qq_42241839/article/details/122984159