Katkat
Back

Design Ordered CUDA Reduction

Applied IntuitionMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question evaluates understanding of parallel GPU programming, deterministic reduction ordering, and numerical stability in floating-point arithmetic, within the domain of parallel algorithms, GPU/CUDA programming, and numerical computing for a Software Engineering Fundamentals / Machine Learning Engineer role.

In CUDA, a parallel reduction can produce different results if the combination order is not fixed, especially for floating-point arithmetic where addition is not perfectly associative.

Design an algorithm for a deterministic reduction that guarantees a well-defined reduction order. The interviewer suggests that the idea is similar to prefix sum.

Address the following:

  1. How would you organize the reduction within a CUDA block?
  2. How would you combine results across blocks without relying on nondeterministic atomics?
  3. How does the approach relate to prefix-scan algorithms?
  4. What guarantees can and cannot be provided for floating-point reductions?
  5. What are the time and memory tradeoffs?