Design a multithreaded CPU 1D convolution
Company: IBM
Role: Software Engineer
Category: System Design
Difficulty: hard
Interview Round: Take-home Project
##### Question
Design and implement a multithreaded CPU version of the **valid 1‑D convolution**. Valid convolution produces an output of length `M = N − K + 1`, where each output is an independent dot product over `K` kernel taps:
`y[i] = Σ_{j=0}^{K−1} x[i+j] · h[j]`
For each of the following cases, describe (and provide code or pseudocode for) how to partition work, assign and schedule threads, and combine results. Address load balancing, scheduling, cache locality, avoiding false sharing, synchronization/merging of partial outputs, vectorization (SIMD), and how to choose chunk/tile sizes and the number of threads:
1. Input length = 1,000,000; kernel length = 3.
2. Input length = 1,000,000; kernel length = 1,000,000.
3. Maximum available worker threads = 100 — give a general, configurable policy (usable for cases 1 and 2) that caps the worker count and chooses chunk sizes accordingly.
Provide pseudocode or an API-level design for the unified routine.
Quick Answer: An IBM software-engineer take-home that asks you to design and implement a multithreaded CPU version of valid 1D convolution across three regimes: a tiny kernel (K=3), a kernel as long as the input (K=N, a single dot product), and a 100-thread cap. It evaluates parallel decomposition, scheduling, cache locality, false-sharing avoidance, SIMD vectorization, and reduction/synchronization choices.