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 = [ 1  2  3 ][ 4  5  6 ]

其转置矩阵B为:

B = [ 1  4 ][ 2  5 ][ 3  6 ]

可以看到,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)通常在程序加载时被分配,并且在整个程序运行期间保持不变。这包括全局变量、静态变量以及静态数组等。因此,如果你多次执行程序,这些全局静态数据的地址通常不会改变。

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

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

主流优化缓存命中

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

  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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/233833.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【uniapp】调用阿里云OCR图片识别文字:

文章目录 一、效果&#xff1a;二、实现&#xff1a; 一、效果&#xff1a; 二、实现&#xff1a; 【阿里官方】高精版OCR文字识别【最新版】-云市场-阿里云 <template><view class"container"><!-- 选择图片 --><button click"imageO…

在win10和Linux上配置SSH 无密码登录

文章目录 一、用途二、在本地机器上使用ssh-keygen产生公钥私钥对1&#xff09;在Linux (或macOS) 上产生SSH公私钥的方法2&#xff09;在win10上产生SSH公私钥的方法a&#xff09;检查windows 本地是否安装有sshb&#xff09;在本地生成SSH密钥对&#xff08;公钥和私钥&#…

2024 年 API 安全:预测和趋势

随着技术以前所未有的速度不断进步&#xff0c;API&#xff08;应用程序编程接口&#xff09;安全性的复杂性也随之增加。随着 API 在现代应用程序和服务中的激增&#xff0c;组织将需要更好地了解其 API 环境以及 API 给运营带来的风险。 到 2024 年&#xff0c;预计几个关键…

基于R语言(SEM)结构方程模型教程

详情点击链接&#xff1a;基于R语言&#xff08;SEM&#xff09;结构方程模型教程 01、R/Rstudio (2)R语言基本操作&#xff0c;包括向量、矩阵、数据框及数据列表等生成和数据提取等 (3)R语言数据文件读取、整理&#xff08;清洗&#xff09;、结果存储等&#xff08;含tidve…

安防视频云平台/可视化监控云平台ARM版EasyCVR无法下载录像文件,如何解决?

视频集中存储/云存储/视频监控管理平台EasyCVR能在复杂的网络环境中&#xff0c;将分散的各类视频资源进行统一汇聚、整合、集中管理&#xff0c;实现视频资源的鉴权管理、按需调阅、全网分发、智能分析等。GB28181视频监控/AI智能大数据视频分析EasyCVR平台已经广泛应用在工地…

【gRPC学习】使用go学习gRPC

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 RPC是远程调用,而google实现了grpc比较方便地实现了远程调用,gRPC是一个现代的开源远程过程调用(RPC)框架 概念介绍 在gRPC中&#xff0c;客户端应用程序可以直接调用另一台计算机上的服务器应用程序上的方法&#…

Docker 部署后端项目自动化脚本

文章目录 开机自启动docker打包后端项目Dockerfile文件脚本文件使用 开机自启动docker systemctl enable docker打包后端项目 这里的项目位置是target同级目录 1.在项目下面新建一个bin目录 新建一个package.txt 写入下方代码后 后缀改为.bat echo off echo. echo [信息] 打…

迎接人工智能的下一个时代:ChatGPT的技术实现原理、行业实践以及商业变现途径

课程背景 2023年&#xff0c;以ChatGPT为代表的接近人类水平的对话机器人&#xff0c;AIGC不断刷爆网络&#xff0c;其强大的内容生成能力给人们带来了巨大的震撼。学术界和产业界也都形成共识&#xff1a;AIGC绝非昙花一现&#xff0c;其底层技术和产业生态已经形成了新的格局…

CloudCompare——点云空间圆拟合

目录 1.概述2.软件实现3.完整操作4.相关代码 本文由CSDN点云侠原创&#xff0c;CloudCompare——点云空间圆拟合&#xff0c;爬虫自重。如果你不是在点云侠的博客中看到该文章&#xff0c;那么此处便是不要脸的爬虫与GPT生成的文章。 1.概述 CloudCompare软件中的Tools——>…

洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes 刷题笔记

P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 直接枚举 减枝优化判断 优化1 只有偶数才会是质数 优化2 回文数的判断次数要优于检查素数 先判断是否为回文数再检查是否为质数 if( hw(i)&&isprime(i)) 这里…

物理机与vm文件共享与传输的设置方法

今天跟各位小伙伴&#xff0c;分享一下物理机与vm虚拟机文件共享与传输的设置方法&#xff0c;以供大家参考&#xff01; 一、物理机与虚拟机文件共享设置方法 第一步&#xff1a;先关闭虚拟机&#xff08;客户机&#xff09; 第二步&#xff1a;选择编辑虚拟机设置 第三步&am…

大数据机器学习深度解读决策树算法:技术全解与案例实战

大数据机器学习深度解读决策树算法&#xff1a;技术全解与案例实战 本文深入探讨了机器学习中的决策树算法&#xff0c;从基础概念到高级研究进展&#xff0c;再到实战案例应用&#xff0c;全面解析了决策树的理论及其在现实世界问题中的实际效能。通过技术细节和案例实践&…

stable diffusion 人物高级提示词(四)朝向、画面范围、远近、焦距、机位、拍摄角度

一、朝向 英文中文front view正面Profile view / from side侧面half-front view半正面Back view背面(quarter front view:1.5)四分之一正面 prompt/英文中文翻译looking at the camera看向镜头facing the camera面对镜头turned towards the camera转向镜头looking away from …

计算一个时间序列中每一个元素对应着星期几Series.dt.dayofweek

【小白从小学Python、C、Java】 【计算机等考500强证书考研】 【Python-数据分析】 计算一个时间序列中 各元素是星期几(之后-1) 例:1月9日是周二则返回1 Series.dt.dayofweek [太阳]选择题 以下关于代码输出结果的说法中正确的是? import pandas as pd ts pd.Series(pd.date…

Spring学习 基于注解的AOP配置

5.1.创建工程 5.1.1.pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.ap…

苹果电脑交互式原型设计软件Axure RP 9 mac特色介绍

Axure RP 9 for Mac是一款交互式原型设计软件&#xff0c;使用axure rp9以最佳的方式展示您的作品&#xff0c;优化现代浏览器并为现代工作流程设计。同时确保您的解决方案正确完整地构建。Axure RP 9 for Mac为您整理笔记&#xff0c;将其分配给UI元素&#xff0c;并合并屏幕注…

Visual Studio 2022 AI Code 支持

1.先在 Log In | Codeium Free AI Code Completion & Chat 上注册一个用户 在Visual Stuido 中扩展中搜索 codeium 并安装 安装完成后登录即可。 注意国内可能存在网络问题无法使用这时建议使用代理进行登录。 地址如下&#xff1a; Sign Up | Codeium Free AI Code Co…

小巧且兼具高性能的小模型 TinyLlama 等

TinyLlama-1.1B 小模型在边缘设备上有着广泛的应用&#xff0c;如智能手机、物联网设备和嵌入式系统&#xff0c;这些边缘设备通常具有有限的计算能力和存储空间&#xff0c;它们无法有效地运行大型语言模型。因此&#xff0c;深入探究小型模型显得尤为重要。 来自新加坡科技…

详解Java中的serialVersionUID概念以及作用(附上Demo)

目录 前言1. 概念2. Demo 前言 原本实现Serializable接口的时候一直都没有serialVersionUID属性&#xff0c;直到看到涉及MybatisPlus新项目中都有该属性&#xff0c;于是做了一期学习了解&#xff0c;最后发现该属性类似深度学习训练中的种子seed&#xff0c;类似版本控制&am…

Java课程设计个人博客

目录 引言&#xff1a;在此说明在本次课设过程中所遇到的困难&#xff01; 一、项目搭建的问题 Q1:Web项目应用啥么编译器编写&#xff1f; Q2:如何创建Web项目(MAVEN)&#xff1f; Q3:Tomcat服务器开头控制台显示乱码如何解决&#xff1f; Q4:Tomcat服务器怎么设置项目的…