// examples/cuda-checklist/coarsening.cu // A tiled and a coarsened matrix multiply, checked element by element // against a CPU triple loop. Checks correct output only. Nothing here is timed. #include #include #include #include #define CHECK(call) \ do { \ cudaError_t err_ = (call); \ if (err_ != cudaSuccess) { \ fprintf(stderr, "%s:%d: %s\n", __FILE__, __LINE__, \ cudaGetErrorString(err_)); \ exit(2); \ } \ } while (0) constexpr int TILE = 32; // region: tiled-matmul // C = A * B for square width x width row-major matrices. TILE is 32. // Launch with dim3(TILE, TILE) threads per block and a // dim3(width / TILE, width / TILE) grid. width must be a multiple of TILE. // Each block computes one TILE x TILE tile of C. __global__ void matmul_tiled(const float *A, const float *B, float *C, int width) { __shared__ float a_tile[TILE][TILE]; __shared__ float b_tile[TILE][TILE]; int row = blockIdx.y * TILE + threadIdx.y; int col = blockIdx.x * TILE + threadIdx.x; float sum = 0.0f; // Walk along the shared dimension one tile at a time. for (int phase = 0; phase < width / TILE; ++phase) { a_tile[threadIdx.y][threadIdx.x] = A[row * width + phase * TILE + threadIdx.x]; b_tile[threadIdx.y][threadIdx.x] = B[(phase * TILE + threadIdx.y) * width + col]; __syncthreads(); for (int k = 0; k < TILE; ++k) { sum += a_tile[threadIdx.y][k] * b_tile[k][threadIdx.x]; } __syncthreads(); } C[row * width + col] = sum; } // endregion: tiled-matmul // region: coarsened-matmul // C = A * B for square width x width row-major matrices. TILE is 32. // Launch with dim3(TILE, TILE) threads per block and a // dim3(width / (TILE * COARSE), width / TILE) grid. width must be a multiple // of TILE * COARSE. Each block computes COARSE neighboring TILE x TILE tiles // of C in one row, so it loads each A tile once and reuses it COARSE times. // Shared memory is two TILE x TILE tiles (8 KB) for every COARSE, because // only one B tile is held at a time. template __global__ void matmul_coarsened(const float *A, const float *B, float *C, int width) { __shared__ float a_tile[TILE][TILE]; __shared__ float b_tile[TILE][TILE]; int row = blockIdx.y * TILE + threadIdx.y; int first_col = blockIdx.x * COARSE * TILE + threadIdx.x; float sum[COARSE]; for (int c = 0; c < COARSE; ++c) { sum[c] = 0.0f; } for (int phase = 0; phase < width / TILE; ++phase) { // The A tile is loaded once per phase and used for all COARSE tiles. a_tile[threadIdx.y][threadIdx.x] = A[row * width + phase * TILE + threadIdx.x]; for (int c = 0; c < COARSE; ++c) { // One B tile at a time. The first barrier also publishes the A tile. b_tile[threadIdx.y][threadIdx.x] = B[(phase * TILE + threadIdx.y) * width + first_col + c * TILE]; __syncthreads(); for (int k = 0; k < TILE; ++k) { sum[c] += a_tile[threadIdx.y][k] * b_tile[k][threadIdx.x]; } // No thread may overwrite b_tile, or a_tile after the last c, until // every thread has read it. __syncthreads(); } } for (int c = 0; c < COARSE; ++c) { C[row * width + first_col + c * TILE] = sum[c]; } } // endregion: coarsened-matmul // Runs matmul_coarsened on a width x width problem and returns true // when every element of C equals the CPU result. template static bool check_coarsened(const float *d_a, const float *d_b, float *d_c, int width, const std::vector &expected) { if (width % (TILE * COARSE) != 0) { fprintf(stderr, "width=%d is not a multiple of TILE * COARSE = %d\n", width, TILE * COARSE); exit(1); } size_t count = (size_t)width * width; std::vector got(count); CHECK(cudaMemset(d_c, 0xFF, count * sizeof(float))); matmul_coarsened<<>>(d_a, d_b, d_c, width); CHECK(cudaGetLastError()); CHECK(cudaDeviceSynchronize()); CHECK(cudaMemcpy(got.data(), d_c, count * sizeof(float), cudaMemcpyDeviceToHost)); bool ok = (got == expected); printf("width=%d kernel=coarsened factor=%d %s\n", width, COARSE, ok ? "ok" : "FAIL"); return ok; } int main() { const int widths[] = {512, 1024}; int max_width = 0; for (int w : widths) max_width = w > max_width ? w : max_width; const size_t max_count = (size_t)max_width * max_width; int failures = 0; for (int width : widths) { if (width % TILE != 0) { fprintf(stderr, "width=%d is not a multiple of TILE=%d\n", width, TILE); return 1; } } float *d_a = nullptr, *d_b = nullptr, *d_c = nullptr; CHECK(cudaMalloc(&d_a, max_count * sizeof(float))); CHECK(cudaMalloc(&d_b, max_count * sizeof(float))); CHECK(cudaMalloc(&d_c, max_count * sizeof(float))); // Small integers in {-2..2} keep every product and partial sum an exact // float (a sum is at most 4 * 1024 = 4096), so the comparison uses ==. unsigned int state = 12345u; for (int width : widths) { size_t count = (size_t)width * width; std::vector a(count), b(count), expected(count), got(count); for (size_t i = 0; i < count; ++i) { state = state * 1664525u + 1013904223u; a[i] = (float)((int)((state >> 16) % 5) - 2); state = state * 1664525u + 1013904223u; b[i] = (float)((int)((state >> 16) % 5) - 2); } for (int i = 0; i < width; ++i) { for (int j = 0; j < width; ++j) { float sum = 0.0f; for (int k = 0; k < width; ++k) { sum += a[(size_t)i * width + k] * b[(size_t)k * width + j]; } expected[(size_t)i * width + j] = sum; } } CHECK(cudaMemcpy(d_a, a.data(), count * sizeof(float), cudaMemcpyHostToDevice)); CHECK(cudaMemcpy(d_b, b.data(), count * sizeof(float), cudaMemcpyHostToDevice)); CHECK(cudaMemset(d_c, 0xFF, count * sizeof(float))); matmul_tiled<<>>( d_a, d_b, d_c, width); CHECK(cudaGetLastError()); CHECK(cudaDeviceSynchronize()); CHECK(cudaMemcpy(got.data(), d_c, count * sizeof(float), cudaMemcpyDeviceToHost)); bool tiled_ok = (got == expected); printf("width=%d kernel=tiled %s\n", width, tiled_ok ? "ok" : "FAIL"); if (!tiled_ok) ++failures; failures += !check_coarsened<1>(d_a, d_b, d_c, width, expected); failures += !check_coarsened<2>(d_a, d_b, d_c, width, expected); failures += !check_coarsened<4>(d_a, d_b, d_c, width, expected); failures += !check_coarsened<8>(d_a, d_b, d_c, width, expected); failures += !check_coarsened<16>(d_a, d_b, d_c, width, expected); } CHECK(cudaFree(d_a)); CHECK(cudaFree(d_b)); CHECK(cudaFree(d_c)); return failures ? 1 : 0; }