学习笔记

CUDA学习之GEMM(一)

53 分钟阅读
学习笔记CUDA

这一节按照ppt完成以下任务,分别是矩阵乘法GEMM的Naive版本,内存合并版本,SMEM分块版本,1D Blocktiling版本,2DBlocktiling版本等等。我感觉还挺恶心的,这个做完我就拿去当我简历上的东西了,直到后面我们完成了FlashAttention的优化。

认真做做吧!

前置芝士

GEMM是计算密集型算子,那么我们怎么论证的呢。

对于计算复杂度,结果矩阵的每个数都会进行一个点积操作O(N),一共有N * N个数,所以计算的总复杂度是$O(N^3)$

对于访存,一共三个矩阵,每个矩阵是O(N^2),所以访存复杂度是$O(N^2)$

GEMM: $C = \alpha A * B + \beta D$

Naive 版本

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cuda_runtime.h>
#include <cstdint> 
#include <type_traits>


#define CUDA_CHECK(call) { \
    cudaError_t err = call ;   \
    if (err != cudaSuccess){ \
        std::cerr << "CUDA error at " << __FILE__ << ":" << __LINE__ << ": " \
                  << cudaGetErrorString(err) << '\n'; \
        exit(1); \
    }    \
} \

template <typename T> 
__global__ void gemm_naive(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    int row = blockIdx.y * blockDim.y + threadIdx.y;
    int col = blockIdx.x * blockDim.x + threadIdx.x;

    if (row < M && col < N) {
        float sum = 0.0f;
        for (int k = 0; k < K; k ++){
            sum += A[row * K + k] * B[k * N + col];
        }
        C[row * N + col] = alpha * sum + beta * C[row * N + col];
    }
}

int main () {
    const int N = 1024;
    const int M = 1024;
    const int K = 512;
    float alpha = 1.3f;
    float beta = 2.1f;
    std::vector<float> h_A_matrix(M*K);
    std::vector<float> h_B_matrix(K*N);

    std::vector<float> ref_C(M*N, 1.0f);
    std::vector<float> ans_C(M*N, 1.0f);

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < K; j ++) {
            h_A_matrix[i * K + j] = static_cast<float>(i % 97) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < K; i ++) {
        for (size_t j = 0; j < N; j ++) {
            h_B_matrix[i * N + j] = static_cast<float>(i % 53) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++){
            float sum = 0.0f;
            for (size_t k = 0; k < K; k++)
            {
                sum += h_A_matrix[i*K+k] * h_B_matrix[k*N+j];
            }
            ref_C[i*N+j] = alpha * sum + beta * ref_C[i*N+j];
        }
    }

    float *d_A_matrix = nullptr;
    float *d_B_matrix = nullptr;
    float *d_C = nullptr;
    CUDA_CHECK(cudaMalloc(&d_A_matrix, static_cast<size_t>(M * K * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_B_matrix, static_cast<size_t>(K * N * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_C, static_cast<size_t>(M * N * sizeof(float))));

    CUDA_CHECK(cudaMemcpy(d_A_matrix, h_A_matrix.data(), static_cast<size_t>(M * K * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_B_matrix, h_B_matrix.data(), static_cast<size_t>(K * N * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_C, ans_C.data(), static_cast<size_t>(M * N * sizeof(float)), cudaMemcpyHostToDevice));

    unsigned int block_size = 32;
    dim3 block(block_size, block_size);
    unsigned grid_size_x = (N + block.x - 1) / block.x;
    unsigned grid_size_y = (M + block.y - 1) / block.y;
    dim3 grid(grid_size_x, grid_size_y);
    
    gemm_naive<float><<<grid, block>>> (M, N, K, alpha, d_A_matrix, d_B_matrix, beta, d_C);
    CUDA_CHECK(cudaGetLastError());
    CUDA_CHECK(cudaDeviceSynchronize());

    CUDA_CHECK(cudaMemcpy(ans_C.data(), d_C, M * N * sizeof(float), cudaMemcpyDeviceToHost));

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++) {
            if (fabs(ref_C[i * N + j] - ans_C[i * N + j]) > 1e-3f * std::max(1.0f, fabs(ref_C[i * N + j]))) {
                std::cerr << "wrong" ;
                exit(1);
            }
        }
    }

    CUDA_CHECK(cudaFree(d_A_matrix));
    CUDA_CHECK(cudaFree(d_B_matrix));
    CUDA_CHECK(cudaFree(d_C));

    std::cout << "passed!\n\n";

    return 0;
}

没什么好讲的,很写到现在已经很简单了

分析:

我们发现sum那一行占据89.55%的动态指令,每次循环需要两次全局内存加载,一次浮点FMA,以及地址计算

当前M * N = 1024^2 = 1048576个元素,每个元素循环512次,所以这行会被执行1024^2 * 512次

注意到左下角的Instruction Mix ,这个表示该源代码生成了哪些类型的SASS指令

我们能够发现对于A,我们同一个warp的32个线程访问同一个元素,可以利用广播和缓存。

Live Registers=37, 这个意思是执行到这个位置时,一个线程大约有37个仍然需要保留其值的寄存器


L2 Theoretical Sectors Global Excessive
表示全局内存访问产生的 L2 sector 数量,相对于理论最少 sector 数量多了多少。

这里接近100%,说明产生了大量额外 sector,通常意味着:

  • warp 内地址不连续;
  • stride 很大;
  • 全局内存访问没有合并。

Warp Stall Sampling
表示采样到的 warp stall 中,有多少可以归因于当前源代码行。

这里我们的结果意味着几乎所有采样到的stall都集中在这一行,常见原因包括:

  • 等待全局内存加载;
  • scoreboard dependency;
  • sum 连续依赖;
  • 地址计算依赖。


计算密集型


这里需要注意我们代码的书写逻辑:

template <typename T> 
__global__ void gemm_naive(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    int row = blockIdx.y * blockDim.y + threadIdx.y;
    int col = blockIdx.x * blockDim.x + threadIdx.x;

    if (row < M && col < N) {
        float sum = 0.0f;
        for (int k = 0; k < K; k ++){
            sum += A[row * K + k] * B[k * N + col];
        }
        C[row * N + col] = alpha * sum + beta * C[row * N + col];
    }
}

为什么我们要这样写?threadIdx.x变化的是要比threadIdx.y快的,blockIdx和gridIdx在这方面也是。这样写的好处是我们在读写A和C时每一行加载数值会变得连续,可以合并。

SMEM缓存版本

通过观察我们可以发现,矩阵中的数据是被复用的,例如计算C里的第一行都用到了A的第一行内容。之前是直接从GMEM里反复读取,这样造成延迟大且浪费资源,于是我们可以通过SMEM来优化,通过SMEM缓存来减少数据复用开销从而提高性能。

const size_t BLOCK_DIM = static_cast<size_t>(1024);

template <typename T> 
__global__ void gemm_smem_caching(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    __shared__ T As[BLOCK_DIM][BLOCK_DIM] ;
    __shared__ T Bs[BLOCK_DIM][BLOCK_DIM] ; 
    
    int row = blockIdx.y * BLOCK_DIM + threadIdx.y;
    int col = blockIdx.x * BLOCK_DIM + threadIdx.x;

    T tmp = T(0) ; 

    int a_row = row;
    int a_col = threadIdx.x;
    As[a_row][a_col] = (a_row < M && a_col < K) ? A[a_row*K+a_col] : T(0);

    int b_row = threadIdx.y;
    int b_col = col;
    Bs[b_row][b_col] = (b_row < K && b_col < N) ? B[b_row*N+b_col] : T(0);

    __syncthreads();

    for (size_t k = 0; k < K; k ++) {
        tmp += As[threadIdx.y][k] * Bs[k][threadIdx.x];
    }
    __syncthreads();

    C[row*N+col] = alpha * tmp + beta * C[row * N + col];
}

发现报错:

发现这里我们需要的空间太大了,超出了SMEM的可分配上限。

很自然的我们想到了分块(tiling)的思想,每次仅从GMEM加载一块(Tile)到SMEM,然后计算这部分的数据。

const size_t BLOCK_DIM = static_cast<size_t>(32);

template <typename T> 
__global__ void gemm_smem_caching(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    __shared__ T As[BLOCK_DIM][BLOCK_DIM] ;
    __shared__ T Bs[BLOCK_DIM][BLOCK_DIM] ; 
    
    int row = blockIdx.y * BLOCK_DIM + threadIdx.y;
    int col = blockIdx.x * BLOCK_DIM + threadIdx.x;

    T tmp = T(0) ; 

    for (size_t bk = 0; bk < K; bk += BLOCK_DIM){
        int a_row = row;
        int a_col = bk + threadIdx.x;
        As[threadIdx.y][threadIdx.x] = (a_row < M && a_col < K) ? A[a_row*K+a_col] : T(0);

        int b_row = bk + threadIdx.y;
        int b_col = col;
        Bs[threadIdx.y][threadIdx.x] = (b_row < K && b_col < N) ? B[b_row*N+b_col] : T(0);

        __syncthreads();

        for (size_t k = 0; k < BLOCK_DIM; k ++) {
            tmp += As[threadIdx.y][k] * Bs[k][threadIdx.x];
        }
        __syncthreads();
    }

    
    if (row < M && col < N) {
        C[row*N+col] = alpha * tmp + beta * C[row * N + col];
    }
}


Warp很多都在等待SMEM(使用过于频繁)

1D Blocktiling


回顾一下我之前的GEMM代码,它一个线程负责计算C矩阵中的1个元素,每个线程只有一个累加器tmp,每个线程不断从Shared Memory中加载A、B的数据。

而现在我们这样操作,让一个线程同时计算C矩阵同一列中的’THREAD_M’个元素,从而复用从Shared Memory中读取的B元素。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cuda_runtime.h>
#include <cstdint> 
#include <type_traits>


#define CUDA_CHECK(call) { \
    cudaError_t err = call ;   \
    if (err != cudaSuccess){ \
        std::cerr << "CUDA error at " << __FILE__ << ":" << __LINE__ << ": " \
                  << cudaGetErrorString(err) << '\n'; \
        exit(1); \
    }    \
} \

const size_t BLOCK_DIM = static_cast<size_t>(32);
constexpr int THREAD_M = 4;

template <typename T> 
__global__ void gemm_smem_caching(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    __shared__ T As[BLOCK_DIM][BLOCK_DIM] ;
    __shared__ T Bs[BLOCK_DIM][BLOCK_DIM] ; 

    int tx = threadIdx.x;
    int ty = threadIdx.y;
    
    int rowStart = blockIdx.y * BLOCK_DIM + threadIdx.y * THREAD_M;
    int col = blockIdx.x * BLOCK_DIM + threadIdx.x;

    T accum[THREAD_M] = {T(0)};

    for (int bk = 0; bk < K; bk += BLOCK_DIM){
        for (int i = 0; i < THREAD_M; i ++) {
            int localRow = ty * THREAD_M + i;
            int aRow = blockIdx.y * BLOCK_DIM + localRow;
            int aCol = bk + tx;
            As[localRow][tx] = (aRow < M && aCol < K) ? A[aRow*K+aCol] : T(0);

            int bRow = bk + localRow;
            int bCol = col;
            Bs[localRow][tx] = (bRow < K && bCol < N) ? B[bRow*N+bCol] : T(0);
        }

        __syncthreads();

        for (int k = 0; k < BLOCK_DIM; k ++) {
            T bVal = Bs[k][tx];

            #pragma unroll
            for (int i = 0; i < THREAD_M; i ++) {
                int aRow = ty * THREAD_M + i;
                T aVal = As[aRow][k];

                accum[i] += aVal * bVal;
            }
        }

        __syncthreads();
    }

    for (int i = 0; i < THREAD_M; i++) {
        int row = rowStart + i;

        if (row < M && col < N) {
            int idx = row * N + col;

            C[idx] = static_cast<T>(
                alpha * accum[i] + beta * C[idx]
            );
        }
    }
}


int main () {
    const int N = 1024;
    const int M = 1024;
    const int K = 512;
    float alpha = 1.3f;
    float beta = 2.1f;
    std::vector<float> h_A_matrix(M*K);
    std::vector<float> h_B_matrix(K*N);

    std::vector<float> ref_C(M*N, 1.0f);
    std::vector<float> ans_C(M*N, 1.0f);

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < K; j ++) {
            h_A_matrix[i * K + j] = static_cast<float>(i % 97) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < K; i ++) {
        for (size_t j = 0; j < N; j ++) {
            h_B_matrix[i * N + j] = static_cast<float>(i % 53) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++){
            float sum = 0.0f;
            for (size_t k = 0; k < K; k++)
            {
                sum += h_A_matrix[i*K+k] * h_B_matrix[k*N+j];
            }
            ref_C[i*N+j] = alpha * sum + beta * ref_C[i*N+j];
        }
    }

    float *d_A_matrix = nullptr;
    float *d_B_matrix = nullptr;
    float *d_C = nullptr;
    CUDA_CHECK(cudaMalloc(&d_A_matrix, static_cast<size_t>(M * K * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_B_matrix, static_cast<size_t>(K * N * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_C, static_cast<size_t>(M * N * sizeof(float))));

    CUDA_CHECK(cudaMemcpy(d_A_matrix, h_A_matrix.data(), static_cast<size_t>(M * K * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_B_matrix, h_B_matrix.data(), static_cast<size_t>(K * N * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_C, ans_C.data(), static_cast<size_t>(M * N * sizeof(float)), cudaMemcpyHostToDevice));

    unsigned int block_size = 32;
    dim3 block(block_size, block_size/static_cast<unsigned int>(THREAD_M));
    unsigned grid_size_x = (N + block.x - 1) / block_size;
    unsigned grid_size_y = (M + block.y - 1) / block_size;
    dim3 grid(grid_size_x, grid_size_y);
    
    gemm_smem_caching<float><<<grid, block>>> (M, N, K, alpha, d_A_matrix, d_B_matrix, beta, d_C);
    CUDA_CHECK(cudaGetLastError());
    CUDA_CHECK(cudaDeviceSynchronize());

    CUDA_CHECK(cudaMemcpy(ans_C.data(), d_C, M * N * sizeof(float), cudaMemcpyDeviceToHost));

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++) {
            if (fabs(ref_C[i * N + j] - ans_C[i * N + j]) > 1e-3f * std::max(1.0f, fabs(ref_C[i * N + j]))) {
                std::cerr << "wrong" ;
                exit(1);
            }
        }
    }

    CUDA_CHECK(cudaFree(d_A_matrix));
    CUDA_CHECK(cudaFree(d_B_matrix));
    CUDA_CHECK(cudaFree(d_C));

    std::cout << "passed!\n\n";

    return 0;
}

我来梳理一下这里面的逻辑:

理论

我们规定一个CUDA Block负责计算C中的一个32*32 的区域

现在我们希望一个线程同时计算同一列的4个连续元素

例如对于线程(tx = 3, ty = 2)不再只计算C[2][3],而是计算当前Tile内的:C[8][3],C[9][3],C[10][3],C[11][3],这也能解释代码中的:

int localRow = ty * THREAD_M + i;

既然一个线程计算4个元素,那每个线程就需要4个累加器accum[THREAD_M],这四个累加器分别对应上面的C.

由于每个线程现在计算4个输出,那么总共只需要32 * 32 / 4 = 256个线程 。

这里需要注意,在x方向我们希望一个线程负责一列,在y方向,一个线程负责四行。

这里需要详细说一下Shared Memory部分。首先我们思考,我需要加载什么数据,才能计算当前的32*32 C tile。很自然的A,B,C都是32*32,所以我们需要填充:

__shared__ T As[32][32];
__shared__ T Bs[32][32];

一个Block只有256个线程,而As,Bs分别有1024个元素,所以一个线程必须承担4个As和4个Bs元素的加载任务。

对于固定的tx,8个不同的ty分别负责行0-31。

代码中aRow,aCol分别代表A中的全局行和列。这里都很好理解。但可以更抽象的去理解这个全局坐标是怎么看的:
$$\begin{equation} \boxed{ \begin{aligned} A &: \quad (blockRow+r,\ bk+c)\\ B &: \quad (bk+r,\ blockCol+c) \end{aligned} } \end{equation}$$

这里我理解不清楚的地方在于为什么我只算了k的0~31就能够说明C的值,这里需要注意我们的for循环嵌套,我们实际上就是取了A的THREAD_M整行和B的THREAD_M整列,请注意这个。

2D Blocktiling

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cuda_runtime.h>
#include <cstdint> 
#include <type_traits>


#define CUDA_CHECK(call) { \
    cudaError_t err = call ;   \
    if (err != cudaSuccess){ \
        std::cerr << "CUDA error at " << __FILE__ << ":" << __LINE__ << ": " \
                  << cudaGetErrorString(err) << '\n'; \
        exit(1); \
    }    \
} \

const size_t BLOCK_DIM = static_cast<size_t>(32);
constexpr int THREAD_M = 4;
constexpr int THREAD_N = 4;

template <typename T> 
__global__ void gemm_smem_caching(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    __shared__ T As[BLOCK_DIM][BLOCK_DIM] ;
    __shared__ T Bs[BLOCK_DIM][BLOCK_DIM] ; 

    int tx = threadIdx.x;
    int ty = threadIdx.y;
    
    int rowStart = blockIdx.y * BLOCK_DIM + threadIdx.y * THREAD_M;
    int colStart = blockIdx.x * BLOCK_DIM + threadIdx.x * THREAD_N;

    T accum[THREAD_M][THREAD_N] = {T(0)};

    int tid = ty * blockDim.x + tx;
    int numThreads = blockDim.x * blockDim.y;

    for (int bk = 0; bk < K; bk += BLOCK_DIM){
        for (int idx = tid; idx < BLOCK_DIM * BLOCK_DIM; idx += numThreads) {

            int r = idx / BLOCK_DIM;
            int c = idx % BLOCK_DIM;

            int aRow = blockIdx.y * BLOCK_DIM + r;
            int aCol = bk + c;
            As[r][c] = (aRow < M && aCol < K) ? A[aRow*K+aCol] : T(0);

            int bRow = bk + r;
            int bCol = blockIdx.x * BLOCK_DIM + c;
            Bs[r][c] = (bRow < K && bCol < N) ? B[bRow*N+bCol] : T(0);
        }

        __syncthreads();

        for (int k = 0; k < BLOCK_DIM; k ++) {
            T A_reg[THREAD_M];
            T B_reg[THREAD_N];

            #pragma unroll
            for (int i = 0; i < THREAD_M; i ++) {
                int aRow = ty * THREAD_M + i;
                A_reg[i] = As[aRow][k];
            }
            
            #pragma unroll
            for (int j = 0; j < THREAD_N; j ++) {
                int bCol = tx * THREAD_N + j;
                B_reg[j] = Bs[k][bCol];
            }

            #pragma unroll
            for (int i = 0; i < THREAD_M; i ++) {
                for ( int j = 0; j < THREAD_N; j ++) {
                    accum[i][j] += A_reg[i] * B_reg[j];
                }
            }
        }

        __syncthreads();
    }

    for (int i = 0; i < THREAD_M; i ++) {
        for ( int j = 0; j < THREAD_N; j ++) {
            int row = rowStart + i;
            int col = colStart + j;

            if (row < M && col < N) {
                int index = row * N + col;

                C[index] = static_cast<T>(alpha * accum[i][j] + beta * C[index]);
            }
        }
    }
}


int main () {
    const int N = 1024;
    const int M = 1024;
    const int K = 512;
    float alpha = 1.3f;
    float beta = 2.1f;
    std::vector<float> h_A_matrix(M*K);
    std::vector<float> h_B_matrix(K*N);

    std::vector<float> ref_C(M*N, 1.0f);
    std::vector<float> ans_C(M*N, 1.0f);

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < K; j ++) {
            h_A_matrix[i * K + j] = static_cast<float>(i % 97) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < K; i ++) {
        for (size_t j = 0; j < N; j ++) {
            h_B_matrix[i * N + j] = static_cast<float>(i % 53) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++){
            float sum = 0.0f;
            for (size_t k = 0; k < K; k++)
            {
                sum += h_A_matrix[i*K+k] * h_B_matrix[k*N+j];
            }
            ref_C[i*N+j] = alpha * sum + beta * ref_C[i*N+j];
        }
    }

    float *d_A_matrix = nullptr;
    float *d_B_matrix = nullptr;
    float *d_C = nullptr;
    CUDA_CHECK(cudaMalloc(&d_A_matrix, static_cast<size_t>(M * K * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_B_matrix, static_cast<size_t>(K * N * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_C, static_cast<size_t>(M * N * sizeof(float))));

    CUDA_CHECK(cudaMemcpy(d_A_matrix, h_A_matrix.data(), static_cast<size_t>(M * K * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_B_matrix, h_B_matrix.data(), static_cast<size_t>(K * N * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_C, ans_C.data(), static_cast<size_t>(M * N * sizeof(float)), cudaMemcpyHostToDevice));

    unsigned int block_size = 32;
    dim3 block(block_size/static_cast<unsigned int>(THREAD_N), block_size/static_cast<unsigned int>(THREAD_M));
    unsigned grid_size_x = (N + block.x - 1) / block_size;
    unsigned grid_size_y = (M + block.y - 1) / block_size;
    dim3 grid(grid_size_x, grid_size_y);
    
    gemm_smem_caching<float><<<grid, block>>> (M, N, K, alpha, d_A_matrix, d_B_matrix, beta, d_C);
    CUDA_CHECK(cudaGetLastError());
    CUDA_CHECK(cudaDeviceSynchronize());

    CUDA_CHECK(cudaMemcpy(ans_C.data(), d_C, M * N * sizeof(float), cudaMemcpyDeviceToHost));

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++) {
            if (fabs(ref_C[i * N + j] - ans_C[i * N + j]) > 1e-3f * std::max(1.0f, fabs(ref_C[i * N + j]))) {
                std::cerr << "wrong" ;
                exit(1);
            }
        }
    }

    CUDA_CHECK(cudaFree(d_A_matrix));
    CUDA_CHECK(cudaFree(d_B_matrix));
    CUDA_CHECK(cudaFree(d_C));

    std::cout << "passed!\n\n";

    return 0;
}

昨天匆匆忙忙的写完了代码,但是代码里面很多细节我其实没有那么清楚,今天仔细研究一下。

现在我开始对于1d和2d的优化逻辑进行总结

小结

1D 和 2Dblock tiling本质是让一个线程计算多个C元素,从而把shared memory中读出的数据继续放进寄存器并重复使用。

优点是:1.能够减少shared-memory读取次数,2.降低地址计算,循环控制等指令占比,3.增加相互独立的FMA,隐藏指令延迟,4.减少线程数量和调度开销。

我们一个个的看:

Naive

对于naive GEMM,我们每次循环读取一个A和一个B,执行一次FMA,一次FMA计算A * B + sum,这算作2个FLOP,读取2个float,所以:

2 FLOP / 8 byte = 0.25 FLOP/byte

Shared Memory

对于shared memory tiling,每轮加载A tile:32 * 32, B tile: 32 * 32, 然后计算 C tile: 32 * 32,总的流量为:(32 * 32 + 32 * 32) * 4 byte = 8192byte, 计算的次数为:32 * 32 * 32 * 2 = 65536 FLOP, 所以$AI = \frac{65536}{8192} = 8 FLOP/byte$。但是可以主义党,这个方案每个线程只计算一个输出元素,shared memory中的数据还没有充分利用寄存器复用。

1D block tiling

对于1D block tiling,我们每个线程计算纵向的4个输出,例如一个线程计算:

C[row + 0][col]
C[row + 1][col]
C[row + 2][col]
C[row + 3][col]

代码里面我们可以看到,bVal只从shared memory读取一次,却参与4次FMA,可以得知,1d tiling主要复用的是B。

对于这个方案的每次k,我们每个线程读取4个A,1个B,执行4个FMA。这样说还是很抽象,回过头来,为什么我们要设计1D block tiling,我们的目的是解决warp等待SMEM的问题,我们实际上并没有减少计算量,也没有减少每个Block从Global Memory加载的数据量,但是它减少了Shared Memory的重复读取,提高了寄存器的复用,增加了指令级并行。

指令级并行是什么意思,原版的代码:

tmp += As[ty][0] * Bs[0][tx];
tmp += As[ty][1] * Bs[1][tx];
tmp += As[ty][2] * Bs[2][tx];

后一次累加前一次的tmp。

而我们的1D拥有4个累加器。

2D block tiling

FMA:读取4个A,4个B,执行16个FMA。其它逻辑差不多。

Warp Tiling

理论

我们假设:

  1. 一个 thread block 负责一个 BM×BN 的 C tile;
  2. block 中的每个 warp 负责一个 WM×WN 的 C tile;
  3. warp 中的每个 lane 负责一个 TM×TN 的 thread tile;
  4. thread tile 的结果保存在该线程的寄存器中。

那么一个warp tile中thread tile的数量必须恰好等于32

(WM / TM) × (WN / TN) == 32

一个block中warp数量为:

NUM_WARPS = (BM / WM) × (BN / WN) 

block中线程数量为:

NUM_THREADS = NUM_WARPS × 32

它的作用是建立更清晰的层级,使得可以系统控制,比如:

  • 每个 block 从 global memory 加载哪些 A、B 元素;
  • 每个 warp 从 shared memory 消费哪些 A、B 数据;
  • 每个线程在寄存器中保存多少个 C 元素;
  • shared memory 到寄存器的数据复用次数;
  • 一个 warp 内的访问是否连续、广播或产生 Bank Conflict;
  • 后续如何加入 float4、双缓冲和 cp.async。

代码

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cuda_runtime.h>
#include <cstdint> 
#include <type_traits>


#define CUDA_CHECK(call) { \
    cudaError_t err = call ;   \
    if (err != cudaSuccess){ \
        std::cerr << "CUDA error at " << __FILE__ << ":" << __LINE__ << ": " \
                  << cudaGetErrorString(err) << '\n'; \
        exit(1); \
    }    \
} \

constexpr int BM = 64;
constexpr int BN = 64;
constexpr int BK = 8;

constexpr int WM = 32;
constexpr int WN = 32;

constexpr int TM = 8;
constexpr int TN = 4;

constexpr int NUM_WARPS_M = BM / WM;
constexpr int NUM_WARPS_N = BN / WN;
constexpr int NUM_WARPS = NUM_WARPS_M * NUM_WARPS_N;
constexpr int NUM_THREADS = NUM_WARPS * 32;

static_assert(BM % WM == 0);
static_assert(BN % WN == 0);
static_assert(WM % TM == 0);
static_assert(WN % TN == 0);
static_assert((WM / TM) * (WN / TN) == 32);

template <typename T> 
__global__ void gemm_warptiling(int M, int N, int K, float alpha, const T *A, const T *B, float beta, T *C){
    __shared__ T As[BM][BK];
    __shared__ T Bs[BK][BN];

    int tid = threadIdx.x;
    int warpId = tid / 32;
    int laneId = tid % 32;

    int warpRow = warpId / NUM_WARPS_N;
    int warpCol = warpId % NUM_WARPS_N;

    constexpr int THREAD_TILES_N = WN / TN;
    int laneRow = laneId / THREAD_TILES_N;
    int laneCol = laneId % THREAD_TILES_N;

    int threadRowBase = warpRow * WM + laneRow * TM;
    int threadColBase = warpCol * WN + laneCol * TN;

    T accum[TM][TN] = {T(0)};

    for (int bk = 0; bk < K; bk += BK) {
        for (int idx = tid; idx < BM * BK; idx += NUM_THREADS) {
            int localRow = idx / BK;
            int localK = idx % BK;

            int globalRow = blockIdx.y * BM + localRow;
            int globalK = bk + localK;

            As[localRow][localK] = (globalRow < M && globalK < K) ? A[globalRow * K + globalK] : T(0);
        }

        for (int idx = tid; idx < BK * BN; idx += NUM_THREADS) {
            int localK = idx / BN;
            int localCol = idx % BN;

            int globalK = bk + localK;
            int globalCol = blockIdx.x * BN + localCol;

            Bs[localK][localCol] = (globalK < K && globalCol < N) ? B[globalK * N + globalCol] : T(0);
        }

        __syncthreads();

        #pragma unroll
        for (int localK = 0; localK < BK; localK ++) {
            T A_reg[TM];
            T B_reg[TN];

            #pragma unroll
            for (int i = 0; i < TM; i ++) {
                A_reg[i] = As[threadRowBase + i][localK];
            }

            #pragma unroll
            for (int j = 0; j < TN; j ++) {
                B_reg[j] = Bs[localK][threadColBase + j];
            }

            #pragma unroll
            for (int i = 0; i < TM; i ++) {
                #pragma unroll
                for (int j = 0; j < TN; j ++) {
                    accum[i][j] += A_reg[i] * B_reg[j];
                }
            }
        }

        __syncthreads();
    }

    #pragma unroll
    for (int i = 0; i < TM; i ++) {
        #pragma unroll
        for (int j = 0; j < TN; j ++) {
            int row = blockIdx.y * BM + threadRowBase + i;
            int col = blockIdx.x * BN + threadColBase + j;

            if (row < M && col < N) {
                int index = row * N + col;

                C[index] = static_cast<T>(
                    alpha * accum[i][j] + beta * C[index]
                );
            }
        }
    }
}


int main () {
    const int N = 1024;
    const int M = 1024;
    const int K = 512;
    float alpha = 1.3f;
    float beta = 2.1f;
    std::vector<float> h_A_matrix(M*K);
    std::vector<float> h_B_matrix(K*N);

    std::vector<float> ref_C(M*N, 1.0f);
    std::vector<float> ans_C(M*N, 1.0f);

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < K; j ++) {
            h_A_matrix[i * K + j] = static_cast<float>(i % 97) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < K; i ++) {
        for (size_t j = 0; j < N; j ++) {
            h_B_matrix[i * N + j] = static_cast<float>(i % 53) - static_cast<float>(j);
        }
    }

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++){
            float sum = 0.0f;
            for (size_t k = 0; k < K; k++)
            {
                sum += h_A_matrix[i*K+k] * h_B_matrix[k*N+j];
            }
            ref_C[i*N+j] = alpha * sum + beta * ref_C[i*N+j];
        }
    }

    float *d_A_matrix = nullptr;
    float *d_B_matrix = nullptr;
    float *d_C = nullptr;
    CUDA_CHECK(cudaMalloc(&d_A_matrix, static_cast<size_t>(M * K * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_B_matrix, static_cast<size_t>(K * N * sizeof(float))));
    CUDA_CHECK(cudaMalloc(&d_C, static_cast<size_t>(M * N * sizeof(float))));

    CUDA_CHECK(cudaMemcpy(d_A_matrix, h_A_matrix.data(), static_cast<size_t>(M * K * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_B_matrix, h_B_matrix.data(), static_cast<size_t>(K * N * sizeof(float)), cudaMemcpyHostToDevice));
    CUDA_CHECK(cudaMemcpy(d_C, ans_C.data(), static_cast<size_t>(M * N * sizeof(float)), cudaMemcpyHostToDevice));

    dim3 block(NUM_THREADS);
    unsigned grid_size_x = (N + BN - 1) / BN;
    unsigned grid_size_y = (M + BM - 1) / BM;
    dim3 grid(grid_size_x, grid_size_y);

    gemm_warptiling<float><<<grid, block>>> (M, N, K, alpha, d_A_matrix, d_B_matrix, beta, d_C);
    CUDA_CHECK(cudaGetLastError());
    CUDA_CHECK(cudaDeviceSynchronize());

    CUDA_CHECK(cudaMemcpy(ans_C.data(), d_C, M * N * sizeof(float), cudaMemcpyDeviceToHost));

    for (size_t i = 0; i < M; i ++) {
        for (size_t j = 0; j < N; j ++) {
            if (fabs(ref_C[i * N + j] - ans_C[i * N + j]) > 1e-3f * std::max(1.0f, fabs(ref_C[i * N + j]))) {
                std::cerr << "wrong" ;
                exit(1);
            }
        }
    }

    CUDA_CHECK(cudaFree(d_A_matrix));
    CUDA_CHECK(cudaFree(d_B_matrix));
    CUDA_CHECK(cudaFree(d_C));

    std::cout << "passed!\n\n";

    return 0;
}

这里我先将block设为一维(方便逐步理解)

int tid = threadIdx.x;      // 0..127
int warpId = tid / 32;      // 0..3
int laneId = tid % 32;      // 0..31

block tile中有2*2个warp tile, N方向的warp数量为2,映射公式:

int warpRow = warpId / WARPS_N;
int warpCol = warpId % WARPS_N;

该warp在block tile中负责的起点:

int warpRowBase = warpRow * WM;
int warpColBase = warpCol * WN;

一个warp tile中:

M 方向有 WM/TM = 4 个 thread tile
N 方向有 WN/TN = 8 个 thread tile

因此把32个lane看成4*8,我们定义:

constexpr int THREAD_TILES_N = WN / TN;  // 8

int laneRow = laneId / THREAD_TILES_N;   // 0..3
int laneCol = laneId % THREAD_TILES_N;   // 0..7


大概看图理解会更简单一点。

这一节的GEMM先告一段落,我也有点做力竭了。

下一节去从系统上对它进行优化