Tiny-GPU开源项目

项目地址

Tiny-GPU架构图

GPU

Tiny-GPU工作方式

Tiny GPU以单核的方式工作，启动内核需要以下步骤：

在全局程序内存中加载内核程序
在数据内存中加载必要的数据
在设备控制寄存器中设置启动的线程数量
通过将启动信号拉高，启动内核
Tiny-GPU组成部分
GPU本身包括以下几个部分：
设备控制寄存器：保存内核在GPU中的执行方式（例如需要启动的线程数量thread_count）；
调度器：内核被启动后，调度器管理线程在不同计算核心上的执行。调度器将可以在单个核心上并行执行的线程编排成组（blocks）,并将组发送给活跃的核心处理，等待所有block处理完成；
多个计算核心：
数据内存/程序内存的内存控制器：GPU需要和外部内存交互。
- Global memory：项目的外村标准为：
  - 数据内存：8bits寻址，每行8bits数据；
  - 程序内存：8bits寻址，每行保存16bits的指令（ISA）
- 内存控制器：全局内存具有固定的读写带宽，实际上多个核心可能同时要求访问内存数据，超过外存的最大读写带宽。内存控制器监控所有来自计算核心的内存访问，根据外存带宽限制请求，并返回外部存储器的相应。每一个内存控制器都有固定大小的通道。
缓存：将核心频繁访问的数据存放到设备SRAM中可加快后续对相同数据的访问速度。
计算单元—核心（Core）：每个内核有许多计算资源，资源围绕可以支持的线程数量构建，为了最大化并行度，需要对这些计算资源进行优化管理，提高计算资源利用率。在本项目中，每个内核一次处理一个block，对于block中的每个线程，内核都有专用的ALU、LSU、PC以及寄存器。管理内核上的线程指令执行是GPU中最具有挑战的问题之一。
- 核心调度器（Core Scheduler）：每个核心都有一个管理线程执行的调度器。Tiny-GPU的调度器按顺序执行到来的Block，以同步、顺序的方式执行block内所有线程的指令。==在更高级的调度程序中，流水线Pipline被用于流式执行指令。此外，wrap技术可用于并行执行block内的多个线程。==调度器必须考虑外存数据的读写延迟，优化指令执行。
- 取指器Fetcher：异步的根据程序计数器从程序外存/缓存中获取指令。
- 解码器Decoder：解码读取的指令，获得线程执行的控制信号。
- 寄存器Register：每个线程都有独立的寄存器，保存线程当前的计算数据，使SIMD单指令多数据模式得以实现。此外，每个寄存器文件包含一些只读寄存器，保存当前线程的ID以及所属的Block块号，线程根据这些信息可以执行不同的数据。
- ALUs：算数逻辑单元用来处理 ADD、SUB、MUL、DIV、CMP指令。
- LSUs：专用load-store单元访问全局内存，用于处理LDR&STR指令并相应内存控制器等待。
- PCs：专用程序计数器，决定每个线程下一步执行的指令，每次执行完当前指令+1。通过BRnzp指令，比肩NZP计算器的值，如果满足特定条件跳转到指定程序行，实现程序的循环执行和条件分支。Tiny-GPU并行执行所有线程，简单假设所有线程每条指令执行完成后PC计数器值相同。==实际GPU中，线程可以分支到不同的PCs值，使得初始化的多个线程可以独立分散执行。==

ISA

ISA：Tiny-GPU实现了11指令ISA，可以简单验证矩阵加法和乘法等简单内核执行。
- BRnzp：如果nzp寄存器满足nzp条件，跳转到程序内存中的指定行。
- CMP：比较两个寄存器的值，并将结果存储在NZP寄存器中，用于后续的BRnzp指令。
- ADD、SUB、MUL、DIV：实现tensor math的基础算数操作。
- LDR：从全局内存中加载数据。
- STR：将数据存储到全局内存中。
- CONST：将常量加载到寄存器中。
- RET：完成信号，表明当前线程执行结束。
  寄存器通过4bits寻址，即一共有16个寄存器。R0-R12支持自由读写，R13-R15是只读寄存器，用来保存%blockIdx、%blockDim、以及%threadIdx，这三个参数对于SIMD至关重要。

Tiny-GPU 执行

Core核心

每个核心通过一系列控制流程执行指令：

FETCH：根据PC从程序内存中读取下一条指令；
DECODE：解码指令获得控制信号；
REQUEST：对于LDR和STR，向全局内存发起读写请求；
WAIT：等待全局存储器返回数据；
EXECUTE：对数据执行任意计算操作；
UPDATE：更新寄存器（包括NZP寄存器）；
==实际上，上述的一些步骤可以被压缩执行以节约操作时间，此外也可以通过Pipeline流式处理相邻指令，即当前指令无需等待先前指令完成即可开始执行。==
Thread线程执行框图

内核设计举例

项目根据提供的指令集，设计了两个1x8的矩阵加法和2x2的矩阵乘法内核，内核通过使用 %blockIdx, %blockDim, and %threadIdx 寄存器展示了GPU的SIMD编程方式。

矩阵加法：

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

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

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

ADD R4, R1, R0                 ; addr(A[i]) = baseA + i
LDR R4, R4                     ; load A[i] from global memory

ADD R5, R2, R0                 ; addr(B[i]) = baseB + i
LDR R5, R5                     ; load B[i] from global memory

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

RET                            ; end of kernel

矩阵乘法：

实现2x2的矩阵乘法，对于对应行、列的点乘使用SIMD并且使用CMP和BRznp控制循环跳出。

.threads 4
.data 1 2 3 4                  ; matrix A (2 x 2)
.data 1 2 3 4                  ; matrix 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)
CONST R3, #0                   ; baseA (matrix A base address)
CONST R4, #4                   ; baseB (matrix B base address)
CONST R5, #8                   ; baseC (matrix C base address)

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

  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

  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

ADD R9, R5, R0                 ; addr(C[i]) = baseC + i
STR R9, R8                     ; store C[i] in global memory

RET                            ; end of kernel

Tiny-GPU模拟执行

本地安装iverilog and cocotb进行仿真。

其余扩展模块

为了简化实现流程，Tiny-GPU省略了现代GPU中的许多优化技术。

Multi-layered Cache & Shared Memory

现代GPU使用多级缓存减少从外部存储器中读取的数据量。Tiny-GPU目前只实现了访存计算单元与存储控制器之间的一级缓存。

实现多级缓存使得频繁访问的数据被缓存在核心内部；
实现不同缓存算法，提高缓存命中率；
同一block内部的多个thread可以访问一段共享内存，用于共享计算结果；
Memory Coalescing
内存访问合并。并行执行的多个线程通常会访问连续内存地址（多个线程访问矩阵的连续元素），但是每一个内存访问都被单独执行。
通过分析内存请求队列，并且将相邻的访存请求合并成单个事务，降低总的内存请求开销。
PIpelining
目前Tiny-GPU执行下一条指令需要等待当前指令完成。
实现多个顺序指令之间的流水执行并保证正确性，帮助提升计算资源利用率。
Warp Scheduling
在GPU中，Warp Scheduler（线程束调度器）模块是一个关键组件，用于协调和调度线程束（warp）的执行。线程束是一组连续的线程，通常有32个线程组成。这些线程在GPU中以并行方式执行相同的指令，称为SIMD（Single Instruction, Multiple Data）执行模型。Warp Scheduler的主要功能是决定哪个线程束将被调度器选择执行，并将它们分配给可用的执行单元（如流处理器）进行计算。Warp Scheduler可以根据多种策略来选择线程束，如轮转（Round-robin）调度、优先级调度或动态调度等。
Branch Divergence
Tiny-GPU假设所有的线程执行完成后PC值相同，因此在线程整个生命周期内都可以并行执行。实际上线程根据自身数据可能跳转到不同代码行。不同PC值的线程引入管理线程分叉和再次合并机制。
Synchronization & Barriers
现代GPU允许设置barrier使得block内部线程同步执行，即允许所有线程到达指定阶段后继续执行。这对于线程需要相互交换共享数据的情况非常有用，以便确保所有数据得到完全处理。

Tiny-GPU开源项目

Tiny-GPU架构图

Tiny-GPU工作方式

Tiny-GPU组成部分

Tiny-GPU 执行

Core核心

Thread线程执行框图

内核设计举例

矩阵加法：

矩阵乘法：

Tiny-GPU模拟执行

其余扩展模块

Multi-layered Cache & Shared Memory

Memory Coalescing

PIpelining

Warp Scheduling

Branch Divergence

Synchronization & Barriers