Katkat
Back

Explain Amdahl’s law and GPU matmul optimization

NVIDIASoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question tests the ability to apply Amdahl's Law to real-world hardware acceleration and understand the architectural constraints involved in GPU matrix multiplication.

The Theoretical Limit of Acceleration

You are working on a C++ library that accelerates a large-scale simulation. Currently, the simulation spends 80% of its time on a CPU-bound matrix-matrix multiplication (GEMM) operation and 20% on serial data orchestration tasks that cannot be parallelized.

  1. Amdahl's Law Application: If you port the GEMM operation to a GPU and achieve a 50x speedup for that portion, what is the theoretical maximum speedup of the entire simulation? What happens to the overall speedup if you improve the GPU kernel to be 500x faster?

  2. Architectural Optimization: Explain why a naive implementation of matrix multiplication is inefficient on a GPU. Describe how you would implement 'tiled' matrix multiplication to optimize memory access patterns. Specifically, discuss the roles of GPU Shared Memory versus Global Memory and why minimizing global memory traffic is critical for performance.

  3. C++ Runtime Considerations: In your high-performance library, you often define interface classes for different compute kernels. If you use a virtual function to dispatch between a CPU-based kernel and a GPU-based kernel, explain the performance implications of this choice in terms of instruction pipelining and the compiler's ability to inline code.

Hints

Hint 1

Recall that Amdahl's Law states Speedup = 1 / ((1 - P) + (P / S)), where P is the parallelizable fraction and S is the speedup factor.

Hint 2

Tiled multiplication works by loading small sub-matrices into high-speed shared memory to reduce redundant loads from global memory.

Hint 3

Virtual functions introduce an indirect branch (vtable lookup) which prevents the compiler from inlining the function call, potentially leading to increased latency in performance-critical loops.

Follow-up questions

  • How does 'occupancy' relate to the number of active warps on an NVIDIA GPU, and how might you trade off shared memory usage against occupancy?
  • If the simulation involves matrices that do not fit into shared memory, how does the tiling strategy change?
  • Can you describe a scenario where using templates (CRTP) would be preferred over virtual functions for kernel dispatching in high-performance C++?