بناء Matmul خطوة بخطوة

Matrix multiply, or matmul, combines an M by K matrix with a K by N matrix to produce an M by N result. It is the heart of AI math.

Each output cell is a dot product: walk across one row of A and down one column of B, multiplying and summing as you go.

The naive version uses three loops over i, j, and k. The outer two pick the output cell, the inner one sums the products.

Before accumulating, set each result cell to zero. Otherwise old or garbage values pollute your sum.

The inner k loop keeps a running accumulator. Summing into a local variable is often faster than touching C every step.

Write the kernel with fn and typed arguments. Strict types let Mojo compile tight machine code with no dynamic overhead.

The basic triple loop does the right math but reads B by column, jumping through memory. Poor locality wastes cache and time.

Reordering to i, k, j keeps the inner loop walking memory in straight lines. Better access patterns can speed matmul a lot.

Nearly all the time lives in the innermost loop. That hot inner loop is exactly where vectorizing and tuning pay off.

Get the simple version right and save its output. It becomes the reference you compare every faster kernel against.

From here you add SIMD, tiling, and parallelism. Each step keeps the same result but raises throughput toward peak hardware speed.

Why is the textbook triple-loop matmul often slow in practice?

Matmul sums a dot product per output cell with three loops; start cells at zero, accumulate locally, and mind loop order for cache. 🔢