Question
You are given a correct but slow numerical kernel, representative inputs, a correctness checker, and a benchmark. Improve its measured throughput without changing its output contract. **Assumption:** the precise production kernel and hardware contract are unavailable in this preparation version. Begin by implementing and optimizing compatible rectangular matrix multiplication over numeric arrays: ```python def matmul(a: list[list[float]], b: list[list[float]]) -> list[list[float]]: ... ``` Reject incompatible or ragged inputs. Preserve numerical correctness within the stated tolerance and do not special-case benchmark inputs. For this preparation interface, matrices are nonempty rectangular lists with nonempty rows and finite real entries (booleans are not numbers). Raise `ValueError` for invalid shape, nonfinite values or incompatible dimensions. Do not modify either input. Integer fixtures require exact results; floating-point implementations should agree with mathematical multiplication within `1e-9` relative/absolute error. The supplied `run_case` only dispatches fixtures. Public checks assess correctness, not benchmark speed, GPU behavior or a reported employer performance threshold. ## Required workflow - Establish a reproducible baseline and profile before changing code. - Form a bottleneck hypothesis: computation, memory access, allocation, dispatch, or data movement. - Make one measurable change at a time and retain correctness checks. - Explain why each transformation should help the target hardware. - Report regressions and limits honestly. ## Design discussion (not graded) 1. Improve cache locality through loop order and blocking. 2. Remove redundant work and temporary allocations; evaluate vectorization. 3. Discuss unrolling, fusion, parallelism, and memory coalescing for an accelerator kernel. 4. Use arithmetic intensity and a roofline model to predict whether matrix shapes are compute- or bandwidth-bound. 5. Compare pipeline and tensor parallelism for a multi-layer model across two devices.