该篇介绍主要以 AMDGPU 7900XTX (Navi31) 为例。 GPGPU 模型简介 SIMT 模型现代 GPU 上基本使用 SIMT (单指令多线程, Single Instruction Multiple Threads) 模型，即一条指令执行在多个线程 (thread / lane / invocation) 上，每个线程上可能存储、运算不同地数据，也就是说具有大规模并行计算的能力。 在 SIMT 模型上，由于指令是一次性发送到多个线程上，因此需要一个管理线程的单元。在 Vulkan 中将其称其为 subgroup，在 DirectX 或 AMDGPU 上被称为 wavefront，Nvidia 将其称之为 wrap。Subgroup 是 GPU 上的最小控制单元，即使我们需要一个线程，我们也只能向 GPU 申请使用一个 subgroup。 AMDGPU 上 subgroup 的最小是 32 个线程 (wave32)，但是可以使用 2 个 wave32 组成一个 wave64 使用。以下无特殊说明，subgroup 以基础的 wave32 介绍。 SIMD 执行单元是一个更大层级的单元，根据 AMDGPU 公开的 RDNA 资料，一个 SIMD 上有 16 个 ALU (算术逻辑单元，Arithmetic logic unit)，也就是 16 个 subgroup。另外一些更上层的控制单元简单地列举：

deqp-runner is a series of tools written by mesa developers for running vulkan and opengl quality test case programs. It can run in parallel and robustly dEQP (draw-element quality program), piglit, SkQP (Skia Quality Program), and so on. In my experience, when running large dEQP test cases, your own changes may cause umd (user mode driver) to fail, crash, timeout, or hang. If you simply use deqp-vk, the khronos testcases program for vulkan, the test will stop when umd throws unrecoverable error.

Whatcopy from Wikipidia: Mesa is an open source implementation of OpenGL, Vulkan, and other graphics API specifications. Mesa translates these specifications to vendor-specific graphics hardware drivers. Vendor DriversMesa is UMD (User mode driver), provides implementation of graphics API and shader compiler. Mesa is like a mono repository, different vendor drivers and graphics APIs are in different directories. Gallium is a driver project in mesa, includes many backends for hardwares:

容器 Lists在 scheme 中一类最基础的异构数据结构即 list 1 2 (list 1 2 3 "str") '(1 2 3 "str") 当然 list 可以看作是个二元组 pair，也有称作 dotlist 1 2 3 4 5 6 7 8 (cons 1 2) ;; '(1 . 2) (cons 1 '(2)) ;; '(1 2) (cons* 1 2 3 4) ;; '(1 2 3 . 4) '(1 . (2 . (3 . 4))) (cons* 1 2 '(3 4)) ;; '(1 2 3 4) '(1 .

libarchive 是一个可以创建和读取多种不同流式归档格式的程序库，包含了最流行的 tar 格式变体、一些 cpio 格式，以及所有的 BSD 和 GNU ar 变体。bsdtar 是一个使用 libarchive 的 tar 实现。 简介 为什么实现大约在 2001 年的某个时间，邮件列表中出现了一些关于 FreeBSD 打包工具的辩论，辩论主要涉及两个相关的问题： 对打包工具来说什么是 正确 (right) 的格式？ 为什么 FreeBSD 的打包工具比其他发行版的打包工具慢？ 在仔细研究之后，Kientzle 认为 tar/gzip 和 tar/bzip2 依然是很好的格式，性能问题纯粹是实现的原因。 因此，Kientzle 开启了一个从 pkg_add 开始重写打包工具的项目，关键是这个项目是一个了解 tar/gzip 和 tar/bzip2 的库。他最终在 2003 年时完成了 libtarfile，并意识到许多核心的基础设施都要简单通用地处理其他格式，因此这个库被重命名为 libarchive。一次在 Kientzle 构建 libarchive 时，他意识到他早期测试套件更接近于一个 GNU tar 的完全 BSD 许可的替代品，即 bsdtar。FreeBSD 项目采用了 bsdtar 和 libarchive，并允许他继续在 FreeBSD 源码树中开发。大约在 2007 年，libarchive 被移植到其他平台，并将主要开发工作转移到了独立的仓库，刚开始在 GoogleCode，之后转到了 GitHub 直到今天。 谁在用 操作系统

Graphs stand or fall by their choice of nodes and edges. — Watts & Strogatz 信息 对于图的学习推荐使用 Rocs。什么？你说你是 Windows？那也不知道用什么啊，欢迎推荐其他工具。另外，KDE 天下第一！ 图的定义与表示图 (graph) 是有序对 \(G = (V, E)\)，其中 V 是点集 (Vertex)，点的个数用 \(\lvert{V}\rvert\) 表示；\(E \subseteq \{ \{ x, y \}: (x, y) \in V^{2}, x \ne y \}\) 是边集 (Edge)，边的个数用 \(\lvert{E}\rvert\) 表示。如果点对是有序的，那么这个图称为有向图 (directed graph / digraph)。当然有向图的边，如果去掉方向限制所对应的无向图，称为该有向图的基础图 (underlying graph)。有时边还有一个属性称为权重 (weight)，表示使用这条边的代价 (cost)。如果任意两个顶点之间都有一条边的话，那么这个图被称作完全图 (complete graph)。 图中的一条路径 (path) 是一个顶点序列 \(v_{1}, v_{2}, \cdots, v_{n}\) (其中 \(v_{i}, v_{i+1} \in E, i \le i < n\))，一条路径的长 (length) 是这条路径上的边的数量。如果图中含有一个顶点到它自身的路径，则这个路径称为环 (loop)，另外环上所有顶点是互异的。有向图中的环通常被称为回路 (cycle)，没有回路的有向图是无环的 (acyclic)，也被称为有向无环图 (DAG, Directed Acyclic Graph)。

控制流解释器所执行语句来执行某些操作。 比如这整个复合语句 (compound statement)，在 Python 中由 def 声明；标头 header 确定了一个简易语句 (clause) 的类型，这个语句中跟随了一个语句序列 (suite)。解释器会按一定顺序执行这个语句序列。 条件语句条件语句在大部分语言中以 if 关键字呈现。 在 Python 中 True 和 False 分别表示真或假，if 引导条件语句及其真分支，零或一个 else 引导假分支，其中还可能会有零或多个 elif 进行嵌套。 1 2 3 4 5 6 7 def absolute_value(n): if n < 0: return -n elif n == 0: return 0 else: return n 在 scheme 中 #t 和 #f 分别表示真或假，语法的话就不能 elif 进行嵌套了 (if test consequent alternative) 1 2 (define (absolute-value n) (if (positive?

优化背景上世纪 80 年代早期优化在编译器开发中还是一个可选特性，一般在其他部分都完成后才会添加到编译器中。因此出现了调试编译器和优化编译器的区别，即前者强调编译速度，因此可执行代码与源码之间存在较强的对应关系；后者强调最小化或最大化可执行程序的某些属性。因此优化编译器会花费更多时间来编译，生成质量更好的代码，通常这个过程伴随着大量移动操作，使调试变得困难。 从 RISC 开始流行，运行时性能开始需要编译器的优化。分支指令的延迟槽、非阻塞内存操作、流水线使用的增多以及功能单元数目的增加等，这些特性使得处理器性能不仅收程序布局和结构方面的制约，还受到指令调度和资源分配等底层细节的限制。 优化编译器现在变得司空见惯 (反而 go 是异类)，进而使编译器改变成了前端、后端的架构，优化将前端与性能问题分割开来。优化假定后端会处理资源分配的问题，因而假定针对具有无限寄存器、内存和功能单元的理想机器进行优化。这也对编译器后端产生了更大压力。 示例：改进数组的地址计算如果编译器前端对数组的引用 m[i, j] 生成的 IR 没有关于 m、i、j 的信息或不了解外围的上下文，编译器如果按照默认的行主序处理地址。生成的表达式类似 \[m + (i - low_{1}(m)) \times (high_{2}(m) - low_{2}(m) + 1) \times w + (j - low_{2}(m)) \times w.\] m 是数组的首地址，\(low_{i}(m)\) 和 \(high_{i}(m)\) 分别表示 m 的第 i 维的下界和上界，w 是 m 中一个元素的字节长度。如何降低该计算的代价，直接取决于对该数组变量极其上下文的分析。如果数组 m 是局部变量并各维度下界均从 1 开始，且上界已知，那么就可以将计算简化为 \[m + (i - 1) \times high_{2}(m) \times w + (j - 1) \times w.\] 如果引用出现在循环内部，且循环中 i 从 1 变动到 I，那么编译器可以使用运算符强度折减 (OSR, Operator Strength Reduction) 将 \((i - 1) \times high_{2}(m) \times w\) 替换为 \(i^{’}_{x} = i^{’}_{x - 1} + high_{2}(m) \times w\) (其中 \(i^{’}_{1} = 0\))。同样地，如果 j 也是个循环的归纳变量 (IV, Induction Variable)，且 j 从 1 变动到 J，那么经过 OSR 后就有了 \(j^{’}_{y} = j^{’}_{y - 1} + w\) (其中 \(j^{’}_{1} = 0\))。经过两次 OSR 后，只需要计算此式 \[m + i^{’} + j^{’}.

编译器通常组织为一连串的处理 pass，在每两个 pass 之间需要将已知的所有信息进行传递，因此编译器需要中间表示 (IR, Intermediate Representation) 表达信息。IR 在编译器中可能是唯一的，也可能有多种。在转换期间，编译器不会回头查看源代码，而是只观察 IR，因此 IR 的性质对编译器对代码的处理由决定性影响。 除了词法分析器，大多数 pass 的输入都是 IR；除了代码生成器，大多数 pass 的输出都是 IR。大多数源代码并不足以支持编译器必须的信息，比如变量与常量的地址，或参数使用的寄存器等，为了记录所有信息，大多数编译器还会添加表和集合来记录额外信息，通常认为这也是 IR 的一部分。 IR 的实现会迫使编译器的开发人员专注于实际问题，用廉价的方式来执行需要频繁进行的操作，并且简洁的表示编译器间可能出现的所有结构。除了这些，还需要可读的 IR 表示。当然，对于使用 IR 的编译器来说，总会在 IR 上进行多次处理，一个 pass 处理中收集信息，另一个 pass 处理中优化代码。 IR 的分类编译器使用过许多种 IR，主要是三个方面：结构性的组织、抽象层次和命名方案。一般来说，这三个属性是独立的。对于 IR 从结构上可以分为： 图 IR 将编译器信息编码在图中。算法通过途中的对象来表述：结点、边、列表、树。 线性 IR 类似某些抽象机上的伪代码，相应算法将迭代遍历简单的线性操作序列。 混合 IR 混合前两种以获取优势，比如现代编译器中常见的 BasicBlock (BB) 内线性表示，而使用控制流图来表示 bb 之间的关系。 IR 的结构性组织对编译器的分析、优化、代码生成等有极大影响，比如树形 IR 得出的处理 pass 在结构上很自然的设计为某种形式的树遍历，而线性 IR 得出的处理 pass 一般顺序迭代遍历各个操作。 IR 所处的抽象层次，如果接近源代码，可能只需要一个结点就可以表示数组访问或过程调用，而较底层的表示中，可能需要合并几个 IR 操作。 1 2 uint[100][100] arr; arr[50][50] = 32; 1 2 3 4 ;; Spir-V %_var_arr = OpVariable %_ptr_arr_100_100 Function %elem = OpAccessChain %_ptr_int %_var_arr %uint_50 %uint_50 OpStore %elem %uint_32 1 2 3 4 5 ;; LLVM IR %1 = alloca [100 x [100 x i32]], align 4 %2 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* %1, i64 0, i64 50 %3 = getelementptr inbounds [100 x i32], [100 x i32]* %2, i64 0, i64 50 store i32 32, i32* %3, align 4 很明显，上面这三个不同层次的代码，对于简单的构造数组，并进行访问元素赋值，它们是不一样的。低层次的 IR 可以展现出更多源代码中所隐藏的细节，从而为编译器优化提供更多可能。

虽然 CS61A 使用 Python 进行教学，但我希望好好学一下 Erlang 和 Scheme。如果想查看更多关于 CS61A 的信息，请访问 课程主页，当然我也会将一部分内容和实现放在自己的 repo 中。 scheme 有很多不同的实现，而大多实现不兼容。因此我使用的是 MIT/GNU Scheme。 Lab00: Getting Startted (入门)首先搭建一个环境，CS61A 中指 Python3 环境。 Setup: 以下是本课程所用到的基础软件，也是重要的组件。 终端 (Terminal)：安装一个终端可以让你运行本课程的 OK 命令 编程环境 (Environment)：编程环境是必须的，当然课程需要的是 Python3.7，这样你才可以运行 OK 命令 文本编辑器 (Text Editor)：VSCode、Atom 什么都行，只要能用来写代码 练习使用终端，并组织你的项目文件 学习 Python 基础 做一个练习 安装 安装终端在 MacOS 和 Linux 中本身就自带了终端软件 (Terminal)，如果是 KDE，终端软件被称作 Konsole。而 Windows 中，直接在 Store 中下载 Windows Terminal 即可。当然 Windows 下推荐使用 WSL，但是系统不是关注的重点。 安装语言环境最低要求 Python3.7，因为这是运行 OK 命令的必要条件。当然你也可以使用别的编程语言。 Windows 下，你可以在这里下载 Python3 或 erlang。安装之后将路径添加到 PATH 系统环境变量中。如果你用 WSL 那和 Linux 下没什么区别。

众所周知，运行的程序是需要内存占用的，在编码时假定栈上的空间是连续的，且定义的所有变量都连续分布在栈上。 实际上，虽然变量是连续分布在栈上的，但编译器会根据不同类型与对齐方式，将变量重新排列，达到最优情况。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <stdio.h> #include <stdlib.h> #define __print_position(type, CNT) \ type VAR##CNT; \ printf("VAR"#CNT " (" #type ")\t: %p\n", &VAR##CNT); #define _print_position(type, CNT) __print_position(type, CNT) #define print_position(type) _print_position(type, __COUNTER__) int main(void) { print_position(int); // VAR0 (int) : 0x7ffe84765470 print_position(double); // VAR1 (double): 0x7ffe84765478 print_position(char); // VAR2 (char) : 0x7ffe8476546f print_position(float); // VAR3 (float) : 0x7ffe84765474 print_position(div_t); // VAR4 (div_t) : 0x7ffe84765480 } 本文主要集中在结构体的对齐。

Windows 中，在安装 Git Bash 时，会安装一个最小化的 Msys 环境，用于提供 Uinx 兼容层。单独安装一个 msys 不如直接使用 Git 引入的来的爽。 另外还有些好处，比如安装依赖只需要从包管理器安装，而无需到处找官网安装配环境。 安装 GitGit 的安装应该是都会的，但还是应该说以下，在 Windows 上安装 git 时，实际上是有很多细节需要注意的。 选择 git 使用的默认的编辑器 实际上，git 已经在这里说的很明白了，默认 vim 是一个历史原因，推建我们使用更现代的 GUI 编辑器。实际上，你可以使用 core.editor 来修改你想使用的编辑器。当然，如果你不设置这个值，git 会用环境变量中的 EDITOR 作为默认编辑器使用，而 Unix 世界中，EDITOR 往往是 Vi 或 Vim。 最后说一下我的习惯，我并不喜欢 Vim，但是配置了的 Emacs 打开太慢了，由其是简单的写一个 message (VSCode 人称小 emacs)，所以我更偏向于终端编辑器 GNU Nano，图形编辑器则更喜欢用 Kate。 初始化新仓库时的默认分值名称 你可以使用 init.defaultbranch 来更改默认的分支名称。 环境变量的作用域 我更推建第一种使用方式，我们只会在 Git-Bash 中使用 Unix tools。这样现得我们的环境变量更为干净。其实在 Powershell 中还好，在 CMD Prompt 中使用 [ 也太精分了。 换行符转换