Parallel Reduction: Dot Product Implementation

Configuration:
TPB = 8 (Threads Per Block)
SIZE = 8 (Vector Size)
dtype = DType.float32
Step 0: Initial Data Setup
Vector A
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
T0
T1
T2
T3
T4
T5
T6
T7
Vector B
2.0
1.0
2.0
1.0
2.0
1.0
2.0
1.0
T0
T1
T2
T3
T4
T5
T6
T7
shared = tb[dtype]().row_major[TPB]().shared().alloc();
Allocates shared memory array of size 8 for inter-thread communication
Step 1: Element-wise Multiplication
global_i = block_dim.x * block_idx.x + thread_idx.x;
local_i = thread_idx.x;
if global_i < size:
  shared[local_i] = a[global_i] * b[global_i];
Shared Memory After Multiplication
2.0
2.0
6.0
4.0
10.0
6.0
14.0
8.0
T0
T1
T2
T3
T4
T5
T6
T7

Each thread computes: A[i] × B[i] and stores in shared[thread_id]

Step 2: Tree-based Parallel Reduction
stride = TPB // 2; // stride = 4
while stride > 0:
  if local_i < stride:
    shared[local_i] += shared[local_i + stride];
  barrier();
  stride //= 2;
Reduction Level 1: stride = 4
Active threads: T0, T1, T2, T3
4.0
6.0
16.0
12.0
10.0
6.0
14.0
8.0
T0: 2.0 + 10.0 = 12.0 | T1: 2.0 + 6.0 = 8.0 | T2: 6.0 + 14.0 = 20.0 | T3: 4.0 + 8.0 = 12.0
Reduction Level 2: stride = 2
Active threads: T0, T1
20.0
20.0
16.0
12.0
10.0
6.0
14.0
8.0
T0: 12.0 + 20.0 = 32.0 | T1: 8.0 + 12.0 = 20.0
Reduction Level 3: stride = 1
Active threads: T0
52.0
20.0
16.0
12.0
10.0
6.0
14.0
8.0
T0: 32.0 + 20.0 = 52.0 (Final Result!)
Step 3: Write Final Result
if local_i == 0:
  output[0] = shared[0];
Final Output
52.0

Only thread 0 writes the final result to global memory

Algorithm Summary

Key Concepts:

  • Shared Memory: Fast on-chip memory shared within a block
  • Barrier Synchronization: Ensures all threads complete before proceeding
  • Tree Reduction: Logarithmic complexity O(log n)
  • Thread Divergence: Some threads become inactive each iteration

Performance Benefits:

  • Parallel Execution: Multiple threads work simultaneously
  • Memory Locality: Shared memory is much faster than global memory
  • Efficient Reduction: O(log n) steps instead of O(n)
  • GPU Optimized: Leverages SIMT architecture
Verification:
Dot Product = (1×2) + (2×1) + (3×2) + (4×1) + (5×2) + (6×1) + (7×2) + (8×1)
= 2 + 2 + 6 + 4 + 10 + 6 + 14 + 8 = 52.0 ✓