GPU-Accelerated Matrix Multiplication in CUDA vs Standard C++: Theory to Implementation (from Scratch - 1783× Speedup)¶
A Technical Deep-Dive into low level CUDA Programming fundamentals for Machine Learning
Abstract¶
Matrix multiplication is the computational backbone of modern machine learning. From dense neural network layers to attention mechanisms in transformers, nearly every operation in deep learning reduces to matrix operations. This technical notebook presents a systematic comparison of CPU and GPU implementations of matrix multiplication, demonstrating speedups of up to 1783× with optimized GPU code.
Implementation Approach¶
We implement matrix multiplication from scratch in C++ using:
- C++17 for all CPU and host code
- NVIDIA CUDA Toolkit (raw CUDA C++ implimentation) for GPU kernels
- No external libraries — no cuBLAS, no cuDNN, no Eigen
- Create files, build and and run C++ from this python notebook - Easily stores result for others to view and follow logic. Convert to web display .html afterwards with pip nbconvert.
This approach provides deep understanding of how GPU acceleration works at the fundamental level, before abstracting to optimized libraries.
Part 1: Theory¶
1.1 Why Matrix Multiplication Matters in Machine Learning¶
Matrix multiplication underpins virtually all modern deep learning computations:
| Layer Type | Core Operation |
|---|---|
| Dense/Fully Connected | $Y = XW + b$ (direct matrix multiply) |
| Attention (Transformers) | $\text{Attention}(Q,K,V) = \text{softmax}(\frac{QK^T}{\sqrt{d_k}})V$ |
| Recurrent (LSTM/GRU) | Multiple matrix multiplies per timestep |
A single forward pass through GPT-3 (175B parameters) requires approximately 350 petaFLOPs of matrix operations. The efficiency of matrix multiplication directly determines training time and inference latency.
1.2 Mathematical Definition¶
For matrices $A \in \mathbb{R}^{M \times K}$ and $B \in \mathbb{R}^{K \times N}$, the product $C \in \mathbb{R}^{M \times N}$ is defined as:
$$C_{ij} = \sum_{k=0}^{K-1} A_{ik} \cdot B_{kj}$$
Computational Complexity: $O(M \cdot N \cdot K)$ — or $O(n^3)$ for square matrices.
For a 4096×4096 matrix multiply: 137 billion FLOPs (floating-point operations).
1.3 The Case for GPU Acceleration¶
| Characteristic | CPU | GPU |
|---|---|---|
| Core count | 4-64 complex cores | 1000s of simple cores |
| Design philosophy | Latency-optimized | Throughput-optimized |
| Memory bandwidth | ~50 GB/s | ~900 GB/s (HBM2) |
| Peak FP32 TFLOPS | ~1-2 TFLOPS | ~30-80 TFLOPS |
Key insight: Matrix multiplication is embarrassingly parallel — each output element $C_{ij}$ can be computed independently. This maps perfectly to GPU architectures.
1.4 The CUDA Programming Model¶
CUDA (Compute Unified Device Architecture) enables heterogeneous computing:
- Execution Model: Kernels launch thousands of threads organized in a hierarchy:
- Thread → Single execution unit
- Block → Group of threads (can share memory, synchronize)
- Grid → Collection of blocks (entire kernel launch)
Part 2: Naive GPU and CPU Implementations¶
We begin with straightforward implementations that prioritize correctness over performance. These serve as baselines for measuring optimization gains.
2.1 CPU Implementation¶
Algorithm: Triple-nested loop computing each $C_{ij}$ sequentially.
Time Complexity: $O(n^3)$ with poor cache utilization due to strided memory access.
The naive implementation follows the mathematical definition directly. Note the memory access pattern: while row traversal is contiguous for matrix $A$, column traversal of matrix $B$ exhibits poor spatial locality.
Creating the C++ header file declaration:
%%writefile naive_cpu.h
#pragma once
#include <chrono>
// Naive CPU matrix multiplication - O(n³)
void cpu_matmul_naive(const float* A, const float* B, float* C, int M, int K, int N);
// Benchmark function
double benchmark_cpu(const float* A, const float* B, float* C, int M, int K, int N, int runs = 3);
Overwriting naive_cpu.h
Creating the C++ main implimentation run file:
%%writefile naive_cpu.cpp
#include "naive_cpu.h"
#include <cstring>
// Naive CPU: Simple triple-nested loop
void cpu_matmul_naive(const float* A, const float* B, float* C, int M, int K, int N) {
std::memset(C, 0, M * N * sizeof(float));
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
float sum = 0.0f;
for (int k = 0; k < K; ++k) {
sum += A[i * K + k] * B[k * N + j];
}
C[i * N + j] = sum;
}
}
}
double benchmark_cpu(const float* A, const float* B, float* C, int M, int K, int N, int runs) {
cpu_matmul_naive(A, B, C, M, K, N); // Warmup
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < runs; ++i) cpu_matmul_naive(A, B, C, M, K, N);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> elapsed = end - start;
return elapsed.count() / runs;
}
Overwriting naive_cpu.cpp
2.1.2 GPU (CUDA) Implementation¶
Parallelization Strategy: Each GPU thread computes exactly one output element $C_{ij}$.
For an $N \times N$ output matrix, we launch $N^2$ threads. The GPU schedules these across thousands of CUDA cores, achieving massive parallelism.
Thread-to-Element Mapping (1024 × 1024 matrix):
┌─────────┬─────────┬─────────┬─────────┐
│ T(0,0) │ T(0,1) │ T(0,2) │ ... │
├─────────┼─────────┼─────────┼─────────┤ 1,048,576 threads
│ T(1,0) │ T(1,1) │ T(1,2) │ ... │ execute in parallel
├─────────┼─────────┼─────────┼─────────┤
│ ... │ ... │ ... │ ... │
└─────────┴─────────┴─────────┴─────────┘
Thread Indexing: Each thread computes its global position:
int row = blockIdx.y * blockDim.y + threadIdx.y;
int col = blockIdx.x * blockDim.x + threadIdx.x;
Cuda C++ header file:
%%writefile naive_cuda.cuh
#pragma once
#include <cuda_runtime.h>
#include <stdio.h>
#define CUDA_CHECK(call) do { \
cudaError_t err = call; \
if (err != cudaSuccess) { \
printf("CUDA error: %s\n", cudaGetErrorString(err)); \
exit(1); \
} \
} while(0)
// Naive GPU matrix multiplication
void gpu_matmul_naive(const float* h_A, const float* h_B, float* h_C, int M, int K, int N);
double benchmark_gpu(const float* h_A, const float* h_B, float* h_C, int M, int K, int N, int runs = 5);
void print_device_info();
Overwriting naive_cuda.cuh
C++ CUDA Kernel main Implementation file:
The naive kernel demonstrates the fundamental CUDA programming pattern:
- Calculate thread's unique position in the output matrix
- Perform the dot product computation
- Write result to global memory
%%writefile naive_cuda.cu
#include "naive_cuda.cuh"
// Naive CUDA Kernel: Each thread computes one output element
__global__ void naive_kernel(const float* A, const float* B, float* C, int M, int K, int N) {
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] = sum;
}
}
void gpu_matmul_naive(const float* h_A, const float* h_B, float* h_C, int M, int K, int N) {
float *d_A, *d_B, *d_C;
CUDA_CHECK(cudaMalloc(&d_A, M*K*sizeof(float)));
CUDA_CHECK(cudaMalloc(&d_B, K*N*sizeof(float)));
CUDA_CHECK(cudaMalloc(&d_C, M*N*sizeof(float)));
CUDA_CHECK(cudaMemcpy(d_A, h_A, M*K*sizeof(float), cudaMemcpyHostToDevice));
CUDA_CHECK(cudaMemcpy(d_B, h_B, K*N*sizeof(float), cudaMemcpyHostToDevice));
dim3 block(16, 16), grid((N+15)/16, (M+15)/16);
naive_kernel<<<grid, block>>>(d_A, d_B, d_C, M, K, N);
CUDA_CHECK(cudaDeviceSynchronize());
CUDA_CHECK(cudaMemcpy(h_C, d_C, M*N*sizeof(float), cudaMemcpyDeviceToHost));
cudaFree(d_A); cudaFree(d_B); cudaFree(d_C);
}
double benchmark_gpu(const float* h_A, const float* h_B, float* h_C, int M, int K, int N, int runs) {
gpu_matmul_naive(h_A, h_B, h_C, M, K, N); // Warmup
cudaEvent_t start, stop;
CUDA_CHECK(cudaEventCreate(&start)); CUDA_CHECK(cudaEventCreate(&stop));
CUDA_CHECK(cudaEventRecord(start));
for (int i = 0; i < runs; ++i) gpu_matmul_naive(h_A, h_B, h_C, M, K, N);
CUDA_CHECK(cudaEventRecord(stop)); CUDA_CHECK(cudaEventSynchronize(stop));
float ms; CUDA_CHECK(cudaEventElapsedTime(&ms, start, stop));
cudaEventDestroy(start); cudaEventDestroy(stop);
return ms / runs;
}
void print_device_info() {
cudaDeviceProp prop; cudaGetDeviceProperties(&prop, 0);
printf("\n=== GPU: %s ===\n", prop.name);
printf("Compute: %d.%d | SMs: %d | Memory: %.1f GB\n\n",
prop.major, prop.minor, prop.multiProcessorCount, prop.totalGlobalMem/1e9);
}
Overwriting naive_cuda.cu
2.3 Benchmark Program¶
The benchmark compares CPU Naive vs GPU Naive, measuring wall-clock time and GFLOPS.
%%writefile naive_main.cpp
#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include "naive_cpu.h"
#include "naive_cuda.cuh"
void init_random(float* m, int size) {
std::mt19937 gen(42);
std::uniform_real_distribution<float> dist(0, 1);
for (int i = 0; i < size; ++i) m[i] = dist(gen);
}
double gflops(int N, double ms) { return (2.0 * N * N * N) / (ms / 1000.0) / 1e9; }
void benchmark(int N) {
std::cout << "\n" << std::string(60, '=') << std::endl;
std::cout << "Matrix Size: " << N << " x " << N << std::endl;
std::cout << std::string(60, '=') << std::endl;
std::vector<float> A(N*N), B(N*N), C(N*N);
init_random(A.data(), N*N);
init_random(B.data(), N*N);
std::cout << std::left << std::setw(20) << "Method" << std::right
<< std::setw(15) << "Time (ms)" << std::setw(12) << "GFLOPS" << std::setw(12) << "Speedup" << std::endl;
std::cout << std::string(60, '-') << std::endl;
// CPU Naive
double t_cpu = benchmark_cpu(A.data(), B.data(), C.data(), N, N, N, 2);
std::cout << std::left << std::setw(20) << "CPU Naive" << std::right
<< std::setw(15) << std::fixed << std::setprecision(2) << t_cpu
<< std::setw(12) << gflops(N, t_cpu) << std::setw(12) << "1.00x" << std::endl;
// GPU Naive
double t_gpu = benchmark_gpu(A.data(), B.data(), C.data(), N, N, N, 5);
std::cout << std::left << std::setw(20) << "GPU Naive" << std::right
<< std::setw(15) << t_gpu << std::setw(12) << gflops(N, t_gpu)
<< std::setw(11) << std::setprecision(1) << (t_cpu/t_gpu) << "x" << std::endl;
}
int main() {
std::cout << "\n";
std::cout << "============================================================" << std::endl;
std::cout << " PART 2: NAIVE IMPLEMENTATIONS - CPU vs GPU" << std::endl;
std::cout << "============================================================" << std::endl;
print_device_info();
benchmark(256);
benchmark(512);
benchmark(1024);
std::cout << "\n" << std::string(60, '=') << std::endl;
std::cout << "Naive benchmark complete!" << std::endl;
std::cout << "GPU achieves significant speedup through parallelization alone." << std::endl;
std::cout << std::string(60, '=') << std::endl;
return 0;
}
Overwriting naive_main.cpp
2.4 Compile C++ Naive Version¶
Compile the naive CPU and GPU implementations:
import subprocess
import os
# Find Visual Studio vcvars64.bat
vs_paths = [
r"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Auxiliary\Build\vcvars64.bat",
]
vcvars = None
for path in vs_paths:
if os.path.exists(path):
vcvars = path
print(f"Found VS: {path.split(chr(92))[-4]}")
break
if vcvars:
print("Compiling NaiveMatMul.exe...")
cmd = f'"{vcvars}" && nvcc -O3 -std=c++17 -o NaiveMatMul.exe naive_main.cpp naive_cpu.cpp naive_cuda.cu'
result = subprocess.run(cmd, shell=True, capture_output=True, text=True)
if result.returncode == 0:
print("✓ Build successful: NaiveMatMul.exe")
else:
print(f"✗ Build failed!\n{result.stderr}")
else:
print("ERROR: Visual Studio not found!")
Found VS: VC Compiling NaiveMatMul.exe... ✓ Build successful: NaiveMatMul.exe
2.5 Run Naive Benchmark¶
import subprocess
result = subprocess.run("NaiveMatMul.exe", shell=True, capture_output=True, text=True)
print(result.stdout)
if result.stderr:
print(result.stderr)
============================================================ PART 2: NAIVE IMPLEMENTATIONS - CPU vs GPU ============================================================ === GPU: NVIDIA GeForce RTX 3090 === Compute: 8.6 | SMs: 82 | Memory: 25.8 GB ============================================================ Matrix Size: 256 x 256 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Naive 15.34 2.19 1.00x GPU Naive 0.64 52.84 24.2x ============================================================ Matrix Size: 512 x 512 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Naive 349.01 0.77 1.00x GPU Naive 1.35 198.13 257.6x ============================================================ Matrix Size: 1024 x 1024 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Naive 6097.68 0.35 1.00x GPU Naive 12.18 176.30 500.6x ============================================================ Naive benchmark complete! GPU achieves significant speedup through parallelization alone. ============================================================
Part 3: Memory-Optimized Implementations¶
The naive implementations suffer from poor memory access patterns. We now introduce optimizations that exploit the memory hierarchy for additional 2-10× speedup.
3.1 Optimization Strategies¶
CPU: Loop Tiling (Cache Blocking)¶
Problem: Poor cache utilization — column access in matrix $B$ causes cache misses.
Solution: Process matrices in small tiles that fit in L1/L2 cache (~32KB).
Memory Access Pattern:
Before: Strided access → Cache misses → Slow
After: Tiled access → Cache hits → Fast
GPU: Shared Memory Tiling¶
Problem: Global memory (VRAM) has ~500 cycle latency.
Solution: Threads cooperatively load tiles into shared memory (~5 cycle latency).
Memory Hierarchy Latency:
┌──────────────┬────────────┬──────────────┐
│ Registers │ Shared │ Global │
│ ~1 cycle │ ~5 cycles │ ~500 cycles │
└──────────────┴────────────┴──────────────┘
The tiled kernel reduces global memory accesses by TILE_SIZE (32×).
3.2 Optimized CPU Implementation (Tiled)¶
%%writefile optimized_cpu.h
#pragma once
#include <chrono>
void cpu_matmul_tiled(const float* A, const float* B, float* C, int M, int K, int N, int tile = 32);
double benchmark_cpu_opt(const float* A, const float* B, float* C, int M, int K, int N, int runs = 3);
Overwriting optimized_cpu.h
%%writefile optimized_cpu.cpp
#include "optimized_cpu.h"
#include <cstring>
#include <algorithm>
// Tiled CPU: Better cache utilization through loop blocking
void cpu_matmul_tiled(const float* A, const float* B, float* C, int M, int K, int N, int tile) {
std::memset(C, 0, M * N * sizeof(float));
for (int i0 = 0; i0 < M; i0 += tile) {
for (int j0 = 0; j0 < N; j0 += tile) {
for (int k0 = 0; k0 < K; k0 += tile) {
int i_end = std::min(i0 + tile, M);
int j_end = std::min(j0 + tile, N);
int k_end = std::min(k0 + tile, K);
for (int i = i0; i < i_end; ++i) {
for (int k = k0; k < k_end; ++k) {
float a_ik = A[i * K + k];
for (int j = j0; j < j_end; ++j) {
C[i * N + j] += a_ik * B[k * N + j];
}
}
}
}
}
}
}
double benchmark_cpu_opt(const float* A, const float* B, float* C, int M, int K, int N, int runs) {
cpu_matmul_tiled(A, B, C, M, K, N); // Warmup
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < runs; ++i) cpu_matmul_tiled(A, B, C, M, K, N);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::milli> elapsed = end - start;
return elapsed.count() / runs;
}
Overwriting optimized_cpu.cpp
3.3 Optimized GPU Implementation (Shared Memory)¶
%%writefile optimized_cuda.cuh
#pragma once
#include <cuda_runtime.h>
#include <stdio.h>
#define CUDA_CHECK(call) do { \
cudaError_t err = call; \
if (err != cudaSuccess) { \
printf("CUDA error: %s\n", cudaGetErrorString(err)); \
exit(1); \
} \
} while(0)
#define TILE_SIZE 32
void gpu_matmul_tiled(const float* h_A, const float* h_B, float* h_C, int M, int K, int N);
double benchmark_gpu_opt(const float* h_A, const float* h_B, float* h_C, int M, int K, int N, int runs = 5);
void print_device_info();
Overwriting optimized_cuda.cuh
%%writefile optimized_cuda.cu
#include "optimized_cuda.cuh"
// Tiled CUDA Kernel: Uses shared memory for faster access
__global__ void tiled_kernel(const float* A, const float* B, float* C, int M, int K, int N) {
__shared__ float As[TILE_SIZE][TILE_SIZE];
__shared__ float Bs[TILE_SIZE][TILE_SIZE];
int bx = blockIdx.x, by = blockIdx.y;
int tx = threadIdx.x, ty = threadIdx.y;
int row = by * TILE_SIZE + ty;
int col = bx * TILE_SIZE + tx;
float sum = 0.0f;
for (int t = 0; t < (K + TILE_SIZE - 1) / TILE_SIZE; ++t) {
// Cooperative loading into shared memory
As[ty][tx] = (row < M && t*TILE_SIZE+tx < K) ? A[row*K + t*TILE_SIZE+tx] : 0;
Bs[ty][tx] = (t*TILE_SIZE+ty < K && col < N) ? B[(t*TILE_SIZE+ty)*N + col] : 0;
__syncthreads();
// Compute using shared memory (fast!)
#pragma unroll
for (int k = 0; k < TILE_SIZE; ++k)
sum += As[ty][k] * Bs[k][tx];
__syncthreads();
}
if (row < M && col < N) C[row * N + col] = sum;
}
void gpu_matmul_tiled(const float* h_A, const float* h_B, float* h_C, int M, int K, int N) {
float *d_A, *d_B, *d_C;
CUDA_CHECK(cudaMalloc(&d_A, M*K*sizeof(float)));
CUDA_CHECK(cudaMalloc(&d_B, K*N*sizeof(float)));
CUDA_CHECK(cudaMalloc(&d_C, M*N*sizeof(float)));
CUDA_CHECK(cudaMemcpy(d_A, h_A, M*K*sizeof(float), cudaMemcpyHostToDevice));
CUDA_CHECK(cudaMemcpy(d_B, h_B, K*N*sizeof(float), cudaMemcpyHostToDevice));
dim3 block(TILE_SIZE, TILE_SIZE);
dim3 grid((N+TILE_SIZE-1)/TILE_SIZE, (M+TILE_SIZE-1)/TILE_SIZE);
tiled_kernel<<<grid, block>>>(d_A, d_B, d_C, M, K, N);
CUDA_CHECK(cudaDeviceSynchronize());
CUDA_CHECK(cudaMemcpy(h_C, d_C, M*N*sizeof(float), cudaMemcpyDeviceToHost));
cudaFree(d_A); cudaFree(d_B); cudaFree(d_C);
}
double benchmark_gpu_opt(const float* h_A, const float* h_B, float* h_C, int M, int K, int N, int runs) {
gpu_matmul_tiled(h_A, h_B, h_C, M, K, N); // Warmup
cudaEvent_t start, stop;
CUDA_CHECK(cudaEventCreate(&start)); CUDA_CHECK(cudaEventCreate(&stop));
CUDA_CHECK(cudaEventRecord(start));
for (int i = 0; i < runs; ++i) gpu_matmul_tiled(h_A, h_B, h_C, M, K, N);
CUDA_CHECK(cudaEventRecord(stop)); CUDA_CHECK(cudaEventSynchronize(stop));
float ms; CUDA_CHECK(cudaEventElapsedTime(&ms, start, stop));
cudaEventDestroy(start); cudaEventDestroy(stop);
return ms / runs;
}
void print_device_info() {
cudaDeviceProp prop; cudaGetDeviceProperties(&prop, 0);
printf("\n=== GPU: %s ===\n", prop.name);
printf("Compute: %d.%d | SMs: %d | Memory: %.1f GB\n\n",
prop.major, prop.minor, prop.multiProcessorCount, prop.totalGlobalMem/1e9);
}
Overwriting optimized_cuda.cu
3.4 Optimized Benchmark Program¶
%%writefile optimized_main.cpp
#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include "optimized_cpu.h"
#include "optimized_cuda.cuh"
void init_random(float* m, int size) {
std::mt19937 gen(42);
std::uniform_real_distribution<float> dist(0, 1);
for (int i = 0; i < size; ++i) m[i] = dist(gen);
}
double gflops(int N, double ms) { return (2.0 * N * N * N) / (ms / 1000.0) / 1e9; }
void benchmark(int N) {
std::cout << "\n" << std::string(60, '=') << std::endl;
std::cout << "Matrix Size: " << N << " x " << N << std::endl;
std::cout << std::string(60, '=') << std::endl;
std::vector<float> A(N*N), B(N*N), C(N*N);
init_random(A.data(), N*N);
init_random(B.data(), N*N);
std::cout << std::left << std::setw(25) << "Method" << std::right
<< std::setw(12) << "Time (ms)" << std::setw(12) << "GFLOPS" << std::setw(12) << "Speedup" << std::endl;
std::cout << std::string(60, '-') << std::endl;
// CPU Tiled (optimized)
double t_cpu = benchmark_cpu_opt(A.data(), B.data(), C.data(), N, N, N, 2);
std::cout << std::left << std::setw(25) << "CPU Tiled (cache opt)" << std::right
<< std::setw(12) << std::fixed << std::setprecision(2) << t_cpu
<< std::setw(12) << gflops(N, t_cpu) << std::setw(12) << "1.00x" << std::endl;
// GPU Tiled (shared memory)
double t_gpu = benchmark_gpu_opt(A.data(), B.data(), C.data(), N, N, N, 5);
std::cout << std::left << std::setw(25) << "GPU Tiled (shared mem)" << std::right
<< std::setw(12) << t_gpu << std::setw(12) << gflops(N, t_gpu)
<< std::setw(11) << std::setprecision(1) << (t_cpu/t_gpu) << "x" << std::endl;
}
int main() {
std::cout << "\n";
std::cout << "============================================================" << std::endl;
std::cout << " PART 3: OPTIMIZED IMPLEMENTATIONS - CPU vs GPU" << std::endl;
std::cout << "============================================================" << std::endl;
print_device_info();
benchmark(256);
benchmark(512);
benchmark(1024);
std::cout << "\n" << std::string(60, '=') << std::endl;
std::cout << "Optimized benchmark complete!" << std::endl;
std::cout << "Memory optimization provides additional speedup over naive." << std::endl;
std::cout << std::string(60, '=') << std::endl;
return 0;
}
Overwriting optimized_main.cpp
3.5 Compile Optimized Version¶
import subprocess
import os
vs_paths = [
r"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Auxiliary\Build\vcvars64.bat",
r"C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Auxiliary\Build\vcvars64.bat",
]
vcvars = None
for path in vs_paths:
if os.path.exists(path):
vcvars = path
print(f"Found VS: {path.split(chr(92))[-4]}")
break
if vcvars:
print("Compiling OptimizedMatMul.exe...")
cmd = f'"{vcvars}" && nvcc -O3 -std=c++17 -o OptimizedMatMul.exe optimized_main.cpp optimized_cpu.cpp optimized_cuda.cu'
result = subprocess.run(cmd, shell=True, capture_output=True, text=True)
if result.returncode == 0:
print("✓ Build successful: OptimizedMatMul.exe")
else:
print(f"✗ Build failed!\n{result.stderr}")
else:
print("ERROR: Visual Studio not found!")
Found VS: VC Compiling OptimizedMatMul.exe... ✓ Build successful: OptimizedMatMul.exe
3.6 Run Optimized Benchmark¶
import subprocess
result = subprocess.run("OptimizedMatMul.exe", shell=True, capture_output=True, text=True)
print(result.stdout)
if result.stderr:
print(result.stderr)
============================================================ PART 3: OPTIMIZED IMPLEMENTATIONS - CPU vs GPU ============================================================ === GPU: NVIDIA GeForce RTX 3090 === Compute: 8.6 | SMs: 82 | Memory: 25.8 GB ============================================================ Matrix Size: 256 x 256 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Tiled (cache opt) 5.09 6.59 1.00x GPU Tiled (shared mem) 0.58 57.93 8.8x ============================================================ Matrix Size: 512 x 512 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Tiled (cache opt) 40.44 6.64 1.00x GPU Tiled (shared mem) 1.16 231.00 34.8x ============================================================ Matrix Size: 1024 x 1024 ============================================================ Method Time (ms) GFLOPS Speedup ------------------------------------------------------------ CPU Tiled (cache opt) 325.23 6.60 1.00x GPU Tiled (shared mem) 3.42 627.02 95.0x ============================================================ Optimized benchmark complete! Memory optimization provides additional speedup over naive. ============================================================
Part 4: Conclusions¶
4.1 Naive Implementations (GPU Speedup vs CPU Naive)¶
| Matrix Size | CPU Naive (ms) | GFLOPS | GPU Naive (ms) | GFLOPS | Speedup |
|---|---|---|---|---|---|
| 256×256 | 15.34 | 2.19 | 0.64 | 52.84 | 24× |
| 512×512 | 349.01 | 0.77 | 1.35 | 198.13 | 259× |
| 1024×1024 | 6097.68 | 0.35 | 12.18 | 176.30 | 501× |
4.2 Memory-Optimized Implementations (Tiled GPU and Tiled CPU Speedup vs CPU Naive)¶
| Matrix Size | CPU Tiled (ms) | Speedup | GPU Tiled (ms) | GFLOPS | Speedup |
|---|---|---|---|---|---|
| 256×256 | 5.09 | 3.0× | 0.58 | 57.93 | 26× |
| 512×512 | 40.44 | 8.6× | 1.16 | 231.00 | 301× |
| 1024×1024 | 325.23 | 18.7× | 3.42 | 627.02 | 1783× |
4.3 Key Insights¶
-
GPU Tiled achieves up to 1783× speedup over CPU Naive at 1024×1024.
-
Speedup increases with matrix size — GPU benefits more from larger workloads.
-
CPU Tiling provides 3-19× improvement through better cache utilization.
-
GPU Tiling adds 1.2-3.6× over GPU Naive through shared memory optimization.
-
Peak performance: 627 GFLOPS 0.627 TFLOPS on GPU Tiled (1024×1024). A Nvidea 3090 theoretical has 34 TFLOPS so we far from pusing it to the limit. Larger arrays or parralell multiplications can push this higher.
-
All Compiler optimised code: Note - All code here CPU and GPU versions is optimised C++ compiled code, which already has more 1000X speedup over raw interpreted pure python code.
4.4 Production Recommendations¶
For production ML workloads, use optimized libraries (even faster than hand-written kernels):
| Library | Use Case |
|---|---|
| cuBLAS | Matrix operations (GEMM) — 2-3× faster than our tiled kernel |
| cuDNN | Neural network layers |
| Eigen | For CPU optimised matrix multiplication |
| Tensor Cores | FP16/INT8 for additional 2-4× speedup |
#include <cublas_v2.h>
cublasSgemm(handle, ...); // Highly optimized, uses Tensor Cores