tiny-gpu

一个使用 Verilog 实现的极简 GPU，为了从零开始学习 GPU 的工作原理而优化设计。

使用少于 15 个完全注释的 Verilog 文件构建，包含完整的架构和 ISA 文档，可工作的矩阵加法/乘法内核，以及对内核仿真和执行跟踪的完整支持。

概述

如果你想从架构到控制信号完整地学习 CPU 的工作原理，网上有很多资源可以帮助你。

GPU 则不然。

由于 GPU 市场的竞争非常激烈，所有现代架构的底层技术细节仍然是专有的。

虽然有很多资源可以学习 GPU 编程，但几乎没有资源可以学习 GPU 在硬件层面的工作原理。

最好的选择是研究像 Miaow 和 VeriGPU 这样的开源 GPU 实现，并尝试弄清楚发生了什么。这很有挑战性，因为这些项目的目标是功能完整和实用，因此它们相当复杂。

这就是我构建 tiny-gpu 的原因!

什么是 tiny-gpu?

重要提示

tiny-gpu 是一个极简的 GPU 实现，为了从零开始学习 GPU 的工作原理而优化设计。

特别是，随着通用 GPU (GPGPU) 和像 Google 的 TPU 这样的 ML 加速器的趋势，tiny-gpu 专注于突出所有这些架构的通用原则，而不是特定于图形硬件的细节。

考虑到这个动机，我们可以通过去除构建生产级显卡的大部分复杂性来简化 GPU，并专注于对所有这些现代硬件加速器至关重要的核心要素。

这个项目主要专注于探索：

  1. 架构 (Architecture) - GPU 的架构是什么样的？最重要的元素是什么？
  2. 并行化 (Parallelization) - SIMD 编程模型如何在硬件中实现？
  3. 内存 (Memory) - GPU 如何解决有限内存带宽的约束？

在理解本项目中阐述的基础知识之后，你可以查看[高级功能部分]，以了解生产级 GPU 中所做的一些最重要的优化（这些优化更具挑战性），这些优化可以提高性能。

架构

Image 15: GPU Image 16: 核心 (Core)

GPU

tiny-gpu 被构建为一次执行一个内核 (kernel)。

为了启动一个内核 (kernel)，我们需要做以下事情：

  1. 将全局程序内存 (global program memory) 加载内核代码
  2. 将数据内存 (data memory) 加载必要的数据
  3. 在设备控制寄存器 (device control register) 中指定要启动的线程 (thread) 数量
  4. 通过将启动信号设置为高电平来启动内核 (kernel)。

GPU 本身由以下单元组成：

  1. 设备控制寄存器 (Device control register)
  2. 调度器 (Dispatcher)
  3. 可变数量的计算核心 (compute cores)
  4. 用于数据内存 (data memory) 和程序内存 (program memory) 的内存控制器 (memory controllers)
  5. 缓存 (Cache)

设备控制寄存器 (Device Control Register)

设备控制寄存器 (device control register) 通常存储元数据 (metadata)，指定内核 (kernels) 应如何在 GPU 上执行。

在本例中，设备控制寄存器 (device control register) 仅存储 thread_count - 为活动内核 (kernel) 启动的线程 (thread) 总数。

调度器 (Dispatcher)

一旦内核 (kernel) 启动，调度器 (dispatcher) 就是实际管理线程 (threads) 分配到不同计算核心 (compute cores) 的单元。

调度器 (dispatcher) 将线程 (threads) 组织成可以在单个核心 (core) 上并行执行的组，称为 块 (blocks)，并将这些块 (blocks) 发送出去，由可用的核心 (cores) 处理。

一旦所有块 (blocks) 都被处理完毕，调度器 (dispatcher) 会报告内核 (kernel) 执行完成。

内存 (Memory)

GPU 被构建为与外部全局内存 (external global memory) 接口。为了简单起见，这里将数据内存 (data memory) 和程序内存 (program memory) 分开。

全局内存 (Global Memory)

tiny-gpu 数据内存 (data memory) 具有以下规格：

  • 8 位寻址能力（数据内存 (data memory) 总共有 256 行）
  • 8 位数据（每行存储的值 < 256）

tiny-gpu 程序内存 (program memory) 具有以下规格：

  • 8 位寻址能力（程序内存 (program memory) 总共有 256 行）
  • 16 位数据（每个指令 (instruction) 都是 16 位，由 ISA 指定）

内存控制器 (Memory Controllers)

全局内存 (global memory) 具有固定的读/写带宽，但所有核心 (cores) 发出的访问内存 (memory) 的请求可能远远超过外部内存 (external memory) 实际能够处理的请求数量。

内存控制器 (memory controllers) 跟踪所有从计算核心 (compute cores) 发送到内存 (memory) 的请求，根据实际的外部内存 (external memory) 带宽限制请求，并将来自外部内存 (external memory) 的响应中继回正确的资源。

每个内存控制器 (memory controller) 都有固定数量的通道，具体数量取决于全局内存 (global memory) 的带宽。

缓存 (Cache) (WIP)

多个核心 (cores) 经常从全局内存 (global memory) 请求相同的数据。不断重复访问全局内存 (global memory) 是昂贵的，而且由于数据已经被获取过一次，因此将其存储在设备上的 SRAM 中，以便在后续请求中更快地检索会更有效率。

这正是缓存 (cache) 的用途。从外部内存 (external memory) 检索的数据存储在缓存 (cache) 中，可以在后续请求中从那里检索，从而释放内存带宽以用于新数据。

核心 (Core)

每个核心 (core) 都有许多计算资源，通常围绕其可以支持的特定数量的线程 (threads) 构建。为了最大限度地提高并行化 (parallelization)，需要优化管理这些资源，以最大限度地提高资源利用率。

在这个简化的 GPU 中，每个核心 (core) 一次处理一个 块 (block)，并且对于块 (block) 中的每个线程 (thread)，核心 (core) 都有专用的 ALU、LSU、PC 和寄存器文件 (register file)。在这些资源上管理线程 (thread) 指令 (instructions) 的执行是 GPU 中最具挑战性的问题之一。

调度器 (Scheduler)

每个核心 (core) 都有一个调度器 (scheduler)，用于管理线程 (threads) 的执行。

tiny-gpu 调度器 (scheduler) 在获取新块 (block) 之前，会执行完单个块 (block) 的所有指令 (instructions)，并且同步且顺序地执行块 (block) 中所有线程 (threads) 的指令 (instructions)。

在更高级的调度器 (schedulers) 中，像 流水线 (pipelining) 这样的技术被用来流式传输多个后续指令 (instructions) 的执行，以在之前的指令 (instructions) 完全完成之前最大限度地利用资源。此外，warp 调度 (warp scheduling) 可以用来并行执行块 (block) 内多个批次的线程 (threads)。

调度器 (scheduler) 必须解决的主要约束是与从全局内存 (global memory) 加载和存储数据相关的延迟。虽然大多数指令 (instructions) 可以同步执行，但这些加载-存储操作是异步的，这意味着其余的指令 (instruction) 执行必须围绕这些长时间的等待时间构建。

取指器 (Fetcher)

从程序内存 (program memory) 异步获取当前程序计数器 (program counter) 处的指令 (instruction)（在执行单个块 (block) 后，大多数实际上应该从缓存 (cache) 中获取）。

解码器 (Decoder)

将获取的指令 (instruction) 解码为用于线程 (thread) 执行的控制信号。

寄存器文件 (Register Files)

每个线程 (thread) 都有自己专用的寄存器文件 (register files) 组。寄存器文件 (register files) 保存每个线程 (thread) 正在执行计算的数据，这实现了单指令多数据 (SIMD) 模式。

重要的是，每个寄存器文件 (register file) 都包含一些只读寄存器 (read-only registers)，用于保存关于当前正在本地执行的块 (block) 和线程 (thread) 的数据，从而使内核 (kernels) 能够根据本地线程 (thread) ID 使用不同的数据执行。

算术逻辑单元 (ALUs)

每个线程 (thread) 都有专用的算术逻辑单元 (arithmetic-logic unit, ALU) 来执行计算。处理 ADD、SUB、MUL、DIV 算术指令 (arithmetic instructions)。

还处理 CMP 比较指令 (comparison instruction)，该指令 (instruction) 实际上输出两个寄存器 (registers) 之间的差值结果是负数、零还是正数 - 并将结果存储在 PC 单元中的 NZP 寄存器 (register) 中。

加载存储单元 (LSUs)

每个线程 (thread) 都有专用的加载存储单元 (load-store unit, LSU)，用于访问全局数据内存 (global data memory)。

处理 LDR 和 STR 指令 (instructions) - 并处理内存控制器 (memory controller) 处理和中继内存 (memory) 请求的异步等待时间。

程序计数器 (PCs)

每个单元都有专用的程序计数器 (program-counter, PC)，用于确定每个线程 (thread) 要执行的下一个指令 (instructions)。

默认情况下，PC 在每条指令 (instruction) 后递增 1。

使用 BRnzp 指令 (instruction)，NZP 寄存器 (register) 检查 NZP 寄存器 (register)（由之前的 CMP 指令 (instruction) 设置）是否与某些情况匹配 - 如果匹配，它将分支到程序内存 (program memory) 的特定行。这就是循环和条件语句的实现方式。

由于线程 (threads) 是并行处理的，tiny-gpu 假设所有线程 (threads) 在每条指令 (instruction) 后“收敛”到相同的程序计数器 (program counter) - 为了简单起见，这是一个幼稚的假设。

在真正的 GPU 中，单个线程 (threads) 可以分支到不同的 PC，导致 分支发散 (branch divergence)，最初一起处理的一组线程 (threads) 必须分裂成单独的执行。

ISA

Image 17: ISA

tiny-gpu 实现了一个简单的 11 条指令 (instructions) 的 ISA，旨在为像矩阵加法和矩阵乘法这样的概念验证 (proof-of-concept) 实现简单的内核 (kernels)（实现方式在本页下方）。

为此，它支持以下指令 (instructions)：

  • BRnzp - 分支指令 (Branch instruction)，如果 NZP 寄存器 (register) 与指令 (instruction) 中的 nzp 条件匹配，则跳转到程序内存 (program memory) 的另一行。
  • CMP - 比较两个寄存器 (registers) 的值，并将结果存储在 NZP 寄存器 (register) 中，以供稍后的 BRnzp 指令 (instruction) 使用。
  • ADD、SUB、MUL、DIV - 基本算术运算，用于实现张量 (tensor) 数学。
  • LDR - 从全局内存 (global memory) 加载数据。
  • STR - 将数据存储到全局内存 (global memory) 中。
  • CONST - 将常量 (constant) 值加载到寄存器 (register) 中。
  • RET - 发出当前线程 (thread) 已到达执行结束的信号。

每个寄存器 (register) 由 4 位指定，这意味着总共有 16 个寄存器 (registers)。前 13 个寄存器 R0 - R12 是支持读/写的自由寄存器 (free registers)。最后 3 个寄存器 (registers) 是特殊的只读寄存器 (read-only registers)，用于提供对 SIMD 至关重要的 %blockIdx、%blockDim 和 %threadIdx。

执行 (Execution)

核心 (Core)

每个核心 (core) 都遵循以下控制流 (control flow)，经历不同的阶段来执行每条指令 (instruction)：

  1. FETCH - 从程序内存 (program memory) 中获取当前程序计数器 (program counter) 处的下一条指令 (instruction)。
  2. DECODE - 将指令 (instruction) 解码为控制信号。
  3. REQUEST - 如果需要，从全局内存 (global memory) 请求数据（如果是 LDR 或 STR 指令 (instruction)）。
  4. WAIT - 如果适用，等待来自全局内存 (global memory) 的数据。
  5. EXECUTE - 对数据执行任何计算。
  6. UPDATE - 更新寄存器文件 (register files) 和 NZP 寄存器 (register)。

控制流 (control flow) 这样布局是为了简单易懂。

实际上，可以压缩其中的几个步骤以优化处理时间，GPU 还可以使用 流水线 (pipelining) 来流式传输和协调核心 (core) 资源上多个指令 (instructions) 的执行，而无需等待之前的指令 (instructions) 完成。

线程 (Thread)

Image 18: 线程 (Thread)

每个核心 (core) 中的每个线程 (thread) 都遵循上述执行路径，对其专用寄存器文件 (register file) 中的数据执行计算。

这类似于标准的 CPU 图，并且在功能上也非常相似。主要区别在于 %blockIdx、%blockDim 和 %threadIdx 值位于每个线程 (thread) 的只读寄存器 (read-only registers) 中，从而实现 SIMD 功能。

内核 (Kernels)

我使用我的 ISA 编写了一个矩阵加法和矩阵乘法内核 (kernels) 作为概念验证 (proof of concept)，以演示使用我的 GPU 进行 SIMD 编程和执行。本仓库中的测试文件能够完全模拟这些内核 (kernels) 在 GPU 上的执行，生成数据内存 (data memory) 状态和完整的执行跟踪。

矩阵加法

这个矩阵加法内核 (kernel) 通过在单独的线程 (threads) 中执行 8 个元素级加法来添加两个 1 x 8 矩阵。

此演示利用 %blockIdx、%blockDim 和 %threadIdx 寄存器 (registers) 来展示此 GPU 上的 SIMD 编程。它还使用了需要异步内存管理 (async memory management) 的 LDR 和 STR 指令 (instructions)。

matadd.asm

.threads 8
.data 0 1 2 3 4 5 6 7          ; matrix A (1 x 8) 矩阵 A (1 x 8)
.data 0 1 2 3 4 5 6 7          ; matrix B (1 x 8) 矩阵 B (1 x 8)

MUL R0, %blockIdx, %blockDim
ADD R0, R0, %threadIdx         ; i = blockIdx * blockDim + threadIdx

CONST R1, #0                   ; baseA (matrix A base address) 矩阵 A 基地址
CONST R2, #8                   ; baseB (matrix B base address) 矩阵 B 基地址
CONST R3, #16                  ; baseC (matrix C base address) 矩阵 C 基地址

ADD R4, R1, R0                 ; addr(A[i]) = baseA + i
LDR R4, R4                     ; load A[i] from global memory 从全局内存加载 A[i]

ADD R5, R2, R0                 ; addr(B[i]) = baseB + i
LDR R5, R5                     ; load B[i] from global memory 从全局内存加载 B[i]

ADD R6, R4, R5                 ; C[i] = A[i] + B[i]

ADD R7, R3, R0                 ; addr(C[i]) = baseC + i
STR R7, R6                     ; store C[i] in global memory 将 C[i] 存储到全局内存

RET                            ; end of kernel 内核结束

矩阵乘法

矩阵乘法内核 (kernel) 乘以两个 2x2 矩阵。它执行相关行和列的点积的元素级计算，并使用 CMP 和 BRnzp 指令 (instructions) 来演示线程 (threads) 内的分支（值得注意的是，所有分支都收敛，因此此内核 (kernel) 在当前的 tiny-gpu 实现上有效）。

matmul.asm

.threads 4
.data 1 2 3 4                  ; matrix A (2 x 2) 矩阵 A (2 x 2)
.data 1 2 3 4                  ; matrix B (2 x 2) 矩阵 B (2 x 2)

MUL R0, %blockIdx, %blockDim
ADD R0, R0, %threadIdx         ; i = blockIdx * blockDim + threadIdx

CONST R1, #1                   ; increment 增量
CONST R2, #2                   ; N (matrix inner dimension) 矩阵内维度 N
CONST R3, #0                   ; baseA (matrix A base address) 矩阵 A 基地址
CONST R4, #4                   ; baseB (matrix B base address) 矩阵 B 基地址
CONST R5, #8                   ; baseC (matrix C base address) 矩阵 C 基地址

DIV R6, R0, R2                 ; row = i // N
MUL R7, R6, R2
SUB R7, R0, R7                 ; col = i % N

CONST R8, #0                   ; acc = 0
CONST R9, #0                   ; k = 0

LOOP:
  MUL R10, R6, R2
  ADD R10, R10, R9
  ADD R10, R10, R3             ; addr(A[i]) = row * N + k + baseA
  LDR R10, R10                 ; load A[i] from global memory 从全局内存加载 A[i]

  MUL R11, R9, R2
  ADD R11, R11, R7
  ADD R11, R11, R4             ; addr(B[i]) = k * N + col + baseB
  LDR R11, R11                 ; load B[i] from global memory 从全局内存加载 B[i]

  MUL R12, R10, R11
  ADD R8, R8, R12              ; acc = acc + A[i] * B[i]

  ADD R9, R9, R1               ; increment k

  CMP R9, R2
  BRn LOOP                    ; loop while k < N 当 k < N 时循环

ADD R9, R5, R0                 ; addr(C[i]) = baseC + i
STR R9, R8                     ; store C[i] in global memory 将 C[i] 存储到全局内存

RET                            ; end of kernel 内核结束

仿真 (Simulation)

tiny-gpu 被设置为仿真 (simulate) 上述两个内核 (kernels) 的执行。在仿真 (simulating) 之前，你需要安装 iverilog 和 cocotb：

  • 使用 brew install icarus-verilog 和 pip3 install cocotb 安装 Verilog 编译器
  • 从 https://github.com/zachjs/sv2v/releases 下载最新版本的 sv2v，解压并将二进制文件放入 $PATH 中。
  • 在本仓库的根目录中运行 mkdir build。

安装完先决条件后，你可以使用 make test_matadd 和 make test_matmul 运行内核 (kernel) 仿真 (simulations)。

执行仿真 (simulations) 将在 test/logs 中输出一个日志文件，其中包含初始数据内存 (data memory) 状态、内核 (kernel) 的完整执行跟踪和最终数据内存 (data memory) 状态。

如果你查看每个日志文件开头记录的初始数据内存 (data memory) 状态，你应该会看到用于计算的两个起始矩阵，在文件末尾的最终数据内存 (data memory) 中，你也应该看到结果矩阵。

下面是执行跟踪的示例，显示了每个周期中每个核心 (core) 内每个线程 (thread) 的执行情况，包括当前指令 (instruction)、PC、寄存器 (register) 值、状态等。

Image 19: 执行跟踪 (execution trace)

对于任何尝试运行仿真 (simulation) 或使用此仓库的人，如果你遇到任何问题，请随时在 Twitter 上私信我 - 我希望你能让它运行起来！

高级功能 (Advanced Functionality)

为了简单起见，现代 GPU 中实现的许多额外功能都大大提高了性能和功能，但 tiny-gpu 省略了这些功能。我们将在本节中讨论其中一些最关键的功能。

多层缓存和共享内存 (Multi-layered Cache & Shared Memory)

在现代 GPU 中，使用多层不同级别的缓存 (caches) 来最大限度地减少需要从全局内存 (global memory) 访问的数据量。tiny-gpu 仅在请求内存 (memory) 的各个计算单元 (compute units) 和存储最近缓存 (cached) 数据的内存控制器 (memory controllers) 之间实现了一个缓存层。

实现多层缓存 (multi-layered caches) 允许频繁访问的数据更本地化地缓存到正在使用它的位置（某些缓存 (caches) 在各个计算核心 (compute cores) 内），从而最大限度地缩短此数据的加载时间。

使用不同的缓存 (caching) 算法来最大限度地提高缓存命中率 (cache-hits) - 这是一个可以改进以优化内存 (memory) 访问的关键维度。

此外，GPU 通常对同一块 (block) 内的线程 (threads) 使用 共享内存 (shared memory)，以访问可用于与其他线程 (threads) 共享结果的单个内存空间。

内存合并 (Memory Coalescing)

GPU 使用的另一个关键内存 (memory) 优化是 内存合并 (memory coalescing)。并行运行的多个线程 (threads) 通常需要访问内存 (memory) 中的顺序地址（例如，一组线程 (threads) 访问矩阵 (matrix) 中的相邻元素） - 但每个内存 (memory) 请求都是单独放置的。

内存合并 (memory coalescing) 用于分析排队的内存 (memory) 请求，并将相邻的请求合并为一个事务，从而最大限度地减少花费在寻址上的时间，并将所有请求一起发出。

流水线 (Pipelining)

在 tiny-gpu 的控制流 (control flow) 中，核心 (cores) 在开始执行下一条指令 (instruction) 之前，会等待在一组线程 (threads) 上执行完一条指令 (instruction)。

现代 GPU 使用 流水线 (pipelining) 来流式传输多个顺序指令 (instructions) 的执行，同时确保彼此之间具有依赖关系的指令 (instructions) 仍然按顺序执行。

这有助于最大限度地提高核心 (cores) 内的资源利用率，因为资源不会在等待时（例如：在异步内存 (memory) 请求期间）处于空闲状态。

Warp 调度 (Warp Scheduling)

另一种用于最大限度地提高核心 (cores) 资源利用率的策略是 warp 调度 (warp scheduling)。这种方法涉及将块 (blocks) 分解为可以一起执行的线程 (threads) 的各个批次。

通过在一个 warp 等待时执行来自另一个 warp 的指令 (instructions)，可以在单个核心 (core) 上同时执行多个 warps。这类似于流水线 (pipelining)，但处理的是来自不同线程 (threads) 的指令 (instructions)。

分支发散 (Branch Divergence)

tiny-gpu 假设单个批次中的所有线程 (threads) 在每条指令 (instruction) 后都最终到达相同的 PC，这意味着线程 (threads) 可以在其整个生命周期内并行执行。

实际上，单个线程 (threads) 可能会彼此发散，并根据其数据分支到不同的行。对于不同的 PC，这些线程 (threads) 将需要分裂成单独的执行行，这需要管理发散的线程 (threads) 并注意线程 (threads) 何时再次收敛。

同步和屏障 (Synchronization & Barriers)

现代 GPU 的另一个核心功能是设置 屏障 (barriers) 的能力，以便块 (block) 中的线程 (threads) 组可以同步并等待同一块 (block) 中的所有其他线程 (threads) 都到达某个点，然后再继续执行。

这对于线程 (threads) 需要相互交换共享数据的情况很有用，因此它们可以确保数据已得到充分处理。