MIT 6.172 笔记 现代硬件算法案例分析

本文是https://en.algorithmica.org/hpc/和MIT 6.172的课后题解析
课程地址：

文章目录

    • HW2 Profiling Serial Merge Sort
      • 测试DEBUG和非DEBUG区别
      • 测试inline和非inline区别
      • Coarsening
    • HW3 向量化
      • 为什么用负偏移量
      • 测量向量化
      • 跨步向量化
    • HW4 Reducer Hyperobjects
      • 比较openmp和pthread
      • omp汇编指令分析
      • omp task实现
      • 优化fib
      • 优化transpose
      • schedule dynamic/static/runtime
    • Cilk运行时
    • HW 6 & HW7: Custom Memory Allocators
    • HW9 & HW10 lock-free和wait-free
      • x86的默认内存模型
      • 并行编程的golden和silver法则
      • 使用setarch x86_64 -R来关闭ASLR
      • 确定性的hashtable
    • 矩阵乘法分析
      • strict alias能起到对齐的作用吗

HW2 Profiling Serial Merge Sort

HW2的课程对应的是L2: Bentley’s Rules和L3:Bit Hacks
关于Bit Hacks可以看https://zhuanlan.zhihu.com/p/37014715

测试DEBUG和非DEBUG区别

HW2介绍了下perf和valgrind，不多展开。
首先课程要求我们用cachegrind分析sort在DEBUG和非DEBUG模式下的命中情况，并且解释指令计数代替时间的优点和缺点。
课程默认是用clang的，但是clang14和clang17经过我测试对cachegrnd的兼容性都不好，读镜像文件报错，需要打补丁：https://bugs.kde.org/show_bug.cgi?id=452758
太麻烦了，因此我换成了gcc
DEBUG模式：
image.png
非DEBUG模式：
image.png

测试inline和非inline区别

这里和我的直觉相违背，事实上：
编译器几乎不需要inline辅助内联，但是我们仍然可以用inline增加被内联的概率。
image.png
这里的性能差距主要是下面的跨翻译单元的alloc函数带来的：

void inline mem_alloc(data_t** space, int size) {
    *space = (data_t*) malloc(sizeof(data_t) * size);
    if (*space == NULL) {
        printf("out of memory...\n");
    }
}

void inline mem_free(data_t** space) {
    free(*space);
    *space = 0;
}

我们看这里生成的汇编代码：
image.png
指针和数组的比较比较简单，在此跳过。

Coarsening

void sort_c(data_t* A, int p, int r) {
  assert(A);
  // In practice, merge sort is slow for small array sizes. As such, using
  // faster sorting techniques (i.e. insertion sort) when the array size is
  // small (aka < 100), can make a significant improvement in the runtime.
  if (r-p < 16) {
    isort(&(A[p]), &(A[r]));
  } else {
    int q = (p + r) / 2;
    sort_c(A, p, q);
    sort_c(A, q + 1, r);
    merge_c(A, p, q, r);
  }
}

这里Coarsening的粒度主要收到cacheline的影响，因为L1的miss率是0。
用64字节的cacheline可以算出最佳参数应该是16。
16
image.png
image.png
100
image.png
image.png
剩下的就是空间重用，很简单不多介绍了。

HW3 向量化

为什么用负偏移量

第一个问题很申必：
image.png
f4f5f3b7563c766851fbceae8be56809.png
这里没有memcpy那种overlap问题，为什么用负偏移量呢？
问了下别人说是因为loop latch可以省一个cmp，而且现在clang已经不会这样做了（有指令fusion所以意义不大了），因此我们不需要太在意这个问题。

测量向量化

没有向量化的情况：
image.png
4宽向量化
image.png
perf分析乘法：
耗时最多的是索引更新操作
image.png
perf分析加法：
耗时最多的是向量化的加法
image.png

跨步向量化

跨步不会进行向量化：
image.png
强制进行向量化试试：
image.png
并没有变快
我们看看跨步向量化的汇编代码
image.png
跨步向量化会多出一个vextracti128指令进行提取，但是耗时很低

HW4 Reducer Hyperobjects

比较openmp和pthread

https://en.wikipedia.org/wiki/OpenMP#Pros_and_cons
优点：
可移植的多线程代码（在C/C++和其他语言中，通常必须调用特定于平台的原语才能获得多线程）。
简单：不需要像MPI那样处理消息传递。
数据布局和分解由指令自动处理。
可扩展性与共享内存系统上的MPI相当。[39]
增量并行：可以一次处理程序的一个部分，不需要对代码进行显著的更改。
串行和并行应用程序的统一代码：当使用顺序编译器时，OpenMP构造被视为注释。
在使用OpenMP并行化时，通常不需要修改原始（串行）代码语句。这减少了无意中引入错误的机会。
粗粒度和细粒度并行都是可能的。
在不完全遵循SPMD计算模式的不规则多物理应用中，如在紧密耦合的流体颗粒系统中遇到的那样，OpenMP的灵活性可以比MPI具有很大的性能优势。
可用于各种加速器，如GPGPU[41]和FPGA。
缺点：
引入难以调试的同步错误和竞争条件的风险。
截至2017年，仅在共享内存多处理器平台上有效运行（但请参阅Wayback Machine和其他分布式共享内存平台上的英特尔集群OpenMP存档2018-11-16）。
需要支持OpenMP的编译器。
可扩展性受到内存体系结构的限制。
不支持比较和交换。
缺少可靠的错误处理。
缺乏细粒度机制来控制线程处理器映射。
意外编写错误共享代码的几率很高。

omp汇编指令分析

见https://github.com/Chang-LeHung/openmp-tutorial/blob/master/docs/for.mdhttps://github.com/Chang-LeHung/openmp-tutorial/blob/master/docs/for.md
omp关键的几个操作用到了
lock cmpxchg、cmpxchg和__sync_fetch_and_add
如果划分的块比较小，那就不会用失败率比较高的cmpxchg，而是用__sync_fetch_and_add

omp task实现

见https://github.com/Chang-LeHung/openmp-tutorial/blob/master/docs/task.md
image.png

优化fib

#include <stdio.h>
#include <inttypes.h>
#include <stdlib.h>

#include "omp.h"

int64_t fib(int64_t n) {
    if (n < 2) return n;
    int64_t x, y;
    if (n < 19) {
        x = fib(n - 1);
        y = fib(n - 2);
    }
    else {
#pragma omp task shared(x)
        x = fib(n - 1);
#pragma omp task shared(y)
        y = fib(n - 2);
#pragma omp taskwait
    }

    return (x + y);
}

int main(int argc, char* argv[]) {
    int64_t n = atoi(argv[1]);
    int64_t result;

    omp_set_num_threads(4);
    int nthreads = omp_get_num_threads();
    printf("N = %d\n", nthreads);
    // result = fib(n);
#pragma omp parallel
    {
#pragma omp master
        {
            result = fib(n);
        }
    }
    printf("Fibonacci of %" PRId64 " is %" PRId64 ".\n", n, result);
}

优化transpose


void transpose(Matrix* arr) {
    uint16_t i, j;
    // Parallel section:
#ifdef _OPENMP
#pragma omp parallel for private(i, j) num_threads(8) schedule(dynamic)
    for (i = 1; i < arr->rows; i++) {
        for (j = 0; j < i; j++) {
            uint8_t tmp = arr->data[i][j];
            arr->data[i][j] = arr->data[j][i];
            arr->data[j][i] = tmp;
        }
    }
    goto end;
#endif

    // Serial section:
    for (i = 1; i < arr->rows; i++) {
        for (j = 0; j < i; j++) {
            uint8_t tmp = arr->data[i][j];
            arr->data[i][j] = arr->data[j][i];
            arr->data[j][i] = tmp;
        }
    }
    goto end;

end:
    return;
}

schedule dynamic/static/runtime

https://stackoverflow.com/questions/10850155/whats-the-difference-between-static-and-dynamic-schedule-in-openmp
schedule(static,2) 每个线程分配两个循环块
比如：

#pragma omp parallel for schedule(static,2) num_threads(8)
for (i = 0; i < 8; i++)
   memset(&a[i*4096], 1, 4096);

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory

|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

#pragma omp for schedule(dynamic,1)
用在每个循环块执行时间由较大差别的情况。**schedule(runtime) 是 OpenMP 中用于动态选择循环迭代分配方式的一种方式。具体含义如下：

  • runtime：表示在运行时动态选择循环迭代分配方式。这意味着循环迭代的分配方式将在程序运行时由运行时系统根据环境和系统的情况进行选择。

Cilk运行时

image.png

  1. RIP：RIP是英特尔x86处理器架构中的指令指针寄存器（Instruction Pointer Register）的缩写。该寄存器存储了当前正在执行的指令的内存地址。当处理器执行指令时，它会从RIP寄存器中获取下一条要执行的指令的地址。
  2. RBP：RBP是英特尔x86处理器架构中的基址指针寄存器（Base Pointer Register）的缩写。在函数调用过程中，RBP通常被用作栈帧的基址指针，用于定位函数的局部变量和参数。通过RBP，函数可以访问其局部变量和参数的内存位置。
  3. RSP：RSP是英特尔x86处理器架构中的栈指针寄存器（Stack Pointer Register）的缩写。栈是一种常用的数据结构，用于存储函数调用期间的局部变量、参数和返回地址等信息。RSP寄存器指向当前栈顶的内存地址，当新的数据被推入或弹出栈时，RSP的值会相应地更新。

HW 6 & HW7: Custom Memory Allocators

后面的两节都是选修课，因为有很多优秀的实现，比如mimalloc、tcmalloc，我之前也分析过，所以这节就跳过了，我们看下一节，lock free和wait free，这个还是很重要的。

HW9 & HW10 lock-free和wait-free

x86的默认内存模型

image.png

并行编程的golden和silver法则

golden rule：永远不要编写非确定性程序
silver rule：永远不要编写非确定性程序，如果必须要编写，那么使用完备的测试用例

使用setarch x86_64 -R来关闭ASLR

确定性的hashtable

e00dd9ba181b4aa04c87ba8ba2e7b1fa.png
这里的问题在于probe可能超出范围，所以我们通过控制线程数可以实现 good和bad
image.png

矩阵乘法分析

https://en.algorithmica.org/hpc/algorithms/matmul/

strict alias能起到对齐的作用吗

在https://en.algorithmica.org/hpc/algorithms/matmul/中说__restrict__能解决alias问题，获得性能提升，但实际上：
https://quick-bench.com/q/GxzfeO3Jmul8g0dw9K1oKgQ_9fw
image.png
可以看得出来，对齐比alias在矩阵乘中作用大得多。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue echarts 柱状图 堆叠柱状图

vue echarts 柱状图 堆叠柱状图

echarts堆叠柱状图&#xff08;效果图在文章末尾&#xff09; 1、默认只显示 月度的 数据&#xff0c;手动点击 legend 季度的 数据才会显示&#xff1b; 2、监听左侧菜单栏的宽度变化&#xff0c;图表宽度自适应展示 <template><div><div id"barChart&q…
阅读更多...
【MySQL】A01、性能优化-参数监控分析

【MySQL】A01、性能优化-参数监控分析

1、参数监控 1.1、MySQL command 查看 mysql>SHOW STATUS; &#xff08;服务器状态变量&#xff0c;运行服务器的统计和状态指标&#xff09; mysql> SHOW VARIABLES;&#xff08;服务器系统变量&#xff0c;实际上使用的变量的值&#xff09; mysql> SHOW STATUS …
阅读更多...
VTK----VTK数据结构详解1（几何篇）

VTK----VTK数据结构详解1（几何篇）

在讲VTK的数据结构之前&#xff0c;我们先了解可视化数据的两个特征&#xff1a;离散性、有规则或无规则。 离散性。当我们使用计算机去表示我们的数据时&#xff0c;一般都是基于有限数量的点做信息的采样&#xff08;或插值&#xff09;&#xff0c;因此可视化的数据是以一种…
阅读更多...
C++笔试强训day8

C++笔试强训day8

目录 1.求最小公倍数 2.数组中的最⻓连续⼦序列 3.字母收集 1.求最小公倍数 链接 这就是一道普通的数学题。 最大公倍数 A * B / A 与 B之间的最大公约数。 最大公约数求法&#xff1a;辗转相除法(或者可以用<numeric>头文件中的gcd) #include <iostream> us…
阅读更多...
Docker基础学习（5.Docker镜像命令）

Docker基础学习（5.Docker镜像命令）

⭐ 作者简介&#xff1a;码上言 ⭐ 代表教程&#xff1a;Spring Boot vue-element 开发个人博客项目实战教程 ⭐专栏内容&#xff1a;个人博客系统 ⭐我的文档网站&#xff1a;http://xyhwh-nav.cn/ ⭐微信公众号&#xff1a;码上言 文章目录 Docker run流程镜像是什么&a…
阅读更多...
AIGC - SD(中英文本生成图片) + PaddleHub/HuggingFace + stable-diffusion-webui

AIGC - SD(中英文本生成图片) + PaddleHub/HuggingFace + stable-diffusion-webui

功能 stable-diffusion(文本生成图片)webui-win搭建&#xff08;开启api界面汉化&#xff09;PaddleHubHuggingFace: SD2&#xff0c;中文-alibaba/EasyNLP stable-diffusion-webui 下载与安装 环境相关下载 python&#xff08;文档推荐&#xff1a;Install Python 3.10.6 …
阅读更多...
web-traffic-generator：一款功能强大的HTTP和HTTPs流量混淆工具

web-traffic-generator：一款功能强大的HTTP和HTTPs流量混淆工具

关于web-traffic-generator web-traffic-generator是一款功能强大的HTTP和HTTPs流量混淆工具&#xff0c;该工具基于纯Python开发&#xff0c;可以帮助广大研究人员在HTTP或HTTPs网络流量中提添加噪声&#xff0c;以此来实现流量混淆的目的。 本质上来说&#xff0c;web-traff…
阅读更多...
北大发现了一种特殊类型的注意力头！

北大发现了一种特殊类型的注意力头！

检索头的发现或许将有力地帮助大模型领域在提高长上下文推理能力、减少幻觉和压缩KV缓存方面的研究。 从 Claude100K 到 Gemini10M&#xff0c;我们正处于长上下文语言模型的时代。如何在长上下文中利用任何输入位置的信息&#xff1f;北大联合另外四所高校发现了一种特殊类型…
阅读更多...
【Redis 开发】Redis持久化(RDB和AOF)

【Redis 开发】Redis持久化(RDB和AOF)

Redis持久化 RDBAOFRDB和AOF的区别 RDB RDB全称Redis DataBase Backup file &#xff08;Redis数据备份文件&#xff09;&#xff0c;也被称为Redis数据快照&#xff0c;简单来说就是把内存中的所有数据都记录到磁盘中&#xff0c;当Redis实例故障重启后&#xff0c;从磁盘读取…
阅读更多...
【后端】Thymeleaf模板引擎学习笔记

【后端】Thymeleaf模板引擎学习笔记

文章目录 1. java体系模板引擎介绍2. 使用2.1 初步使用2.2. 引用静态资源模板2.3 引用静态资源模板(配置资源路径和后缀)2.4 整合springboot 视频地址 1. java体系模板引擎介绍 FreeMarkerThymeleafVelocity 2. 使用 2.1 初步使用 引入依赖 <dependency><groupId>…
阅读更多...
Qt/C++ 波形绘制双缓冲下改善PaintEvent连续绘制卡顿问题（完整代码解析）

Qt/C++ 波形绘制双缓冲下改善PaintEvent连续绘制卡顿问题（完整代码解析）

音频波形可视化&#xff1a;该控件用于将音频样本数据可视化为波形&#xff0c;常用于音频处理软件中以展示音频信号的时间域特性。 动态数据绘制&#xff1a;控件能够响应外部数据的变化并重新绘制波形&#xff0c;适用于实时或动态的音频数据流。 自定义绘制逻辑&#xff1…
阅读更多...
Git操作与异常处理

Git操作与异常处理

文章目录 常用操作1、代码拉取2、代码提交3、暂存区状态4、提交代码5、推送远程仓库 异常处理【1】报错信息&#xff1a;Cannot pull into a repository with state: MERGING【2】报错信息&#xff1a;You have not concluded your merge (MERGE_HEAD exists)【3】报错信息&…
阅读更多...
SpringCloud整合Ribbon负载均衡器

SpringCloud整合Ribbon负载均衡器

目录 一、模块一&#xff1a;提供数据 1.1 首先将第一个实例打包 1.2 使用命令行设置不同权重 1.3 打开图形化界面看看权重是否配置成功。 二、模块二&#xff1a;调用模块一 三、修改默认负载均衡策略 四、自定义规则 ​编辑 五、完整代码 5.1 目录结构 5.2 配置文件 …
阅读更多...
Stable Diffusion学习线路，提示词及资源分享

Stable Diffusion学习线路，提示词及资源分享

1. 提示词的基础概念 提示词分为正面提示词&#xff08;Prompts&#xff09;和反面提示词&#xff08;Negative Prompts&#xff09;。正面提示词代表你希望画面中出现的内容&#xff0c;而反面提示词代表你不希望画面中出现的内容。提示词通常是以英文书写&#xff0c;最小单…
阅读更多...
新版本Qt Creator安装配置

新版本Qt Creator安装配置

新版本Qt Creator安装配置 文章目录 新版本Qt Creator安装配置1、前言2、环境3、安装配置4、总结 更多精彩内容&#x1f449;个人内容分类汇总 &#x1f448;&#x1f449;Qt开发经验 &#x1f448; 1、前言 Qt是一个跨平台的C应用程序开发框架&#xff0c;而Qt Creator是专为Q…
阅读更多...
树，二叉树的基本概念介绍，二叉树的性质

树，二叉树的基本概念介绍，二叉树的性质

目录 树 树的定义 树的相关概念 树的存储结构 树在实际中的运用&#xff08;表示文件系统的目录树结构 &#xff09; 二叉树 二叉树的定义 现实中的二叉树 二叉树的特点 特殊的二叉树 1.斜树 2.满二叉树 3.完全二叉树 二叉树的性质 性质1&#xff1a;二叉树的第…
阅读更多...
数字旅游引领智慧化浪潮：科技创新重塑旅游体验，智慧服务打造旅游新高度

数字旅游引领智慧化浪潮：科技创新重塑旅游体验，智慧服务打造旅游新高度

在科技飞速发展的今天&#xff0c;数字旅游正以其独特的魅力引领着智慧化浪潮&#xff0c;深刻改变着旅游行业的面貌。数字技术的广泛应用&#xff0c;不仅为旅游行业注入了新的活力&#xff0c;也极大地提升了旅游体验的品质。科技创新与智慧服务的融合&#xff0c;正推动着旅…
阅读更多...
大厂面试题：两道来自京东的关于MyBatis执行器的面试题

大厂面试题：两道来自京东的关于MyBatis执行器的面试题

大家好&#xff0c;我是王有志。 今天给大家带来两道来自于京东关于的 MyBatis 面试题&#xff1a; MyBatis 提供了哪些执行器&#xff08;Executor&#xff09;&#xff1f;它们有什么区别&#xff1f;Mybatis 中如何指定 Executor 的类型&#xff1f; MyBatis 提供了哪些执…
阅读更多...
【VBA】获取指定目录下的Excel文件，并合并所有excel中的内容。

【VBA】获取指定目录下的Excel文件，并合并所有excel中的内容。

1.新建一个excel表格。并创建两个Sheet&#xff0c;名字分别命名为FileList 和 All information。 2.按ALTF11进入 VBA编程模块&#xff0c;插入模块。 3.将如下 第五部分代码复制到模块中。 点击运行即可&#xff0c;然后就能提取指定目录下的所有excel文件信息并合并到一起…
阅读更多...
plsql 新建sql窗口 初始化慢的问题

plsql 新建sql窗口 初始化慢的问题

问题描述&#xff1a; 新建sql窗口当sql语句多的情况下初始化很慢。 解决方法&#xff1a; 采用导入表的方式。 具体方式 工具->导入表->sql插入。 使用命令窗口 导入文件&#xff0c;然后点击导入按钮。
阅读更多...
最新文章

Copyright @ 2022~2023