Map dot products to processing elements

Fix the computation before scheduling it

Let A have shape M×K and B have shape K×P. Their product C has shape M×P. The index i selects an output row, j selects an output column, and k is the reduction index inside the sum. Indices start at zero throughout this course.

Our output-stationary design assigns C(i,j) to PE(i,j). That processing element retains its partial sum while A moves right and B moves down. Movement provides reuse; the equation specifies which operands may be multiplied. We will define clock timing separately, so a scheduling error cannot silently change the intended mathematics.

Work a complete reference

Use A=[[1,2],[3,4]] and B=[[5,6],[7,8]]. PE(0,1) combines row [1,2] with column [6,8]. It accumulates 1×6=6 and 2×8=16 to obtain 22. Using B's second row [7,8] instead gives 23, a useful signature of a row/column mistake.

The expected matrix is [[19,22],[43,50]]. Each PE performs two valid MACs, so the array performs eight MACs. A convention counting one multiplication and one addition separately reports sixteen arithmetic operations. Always label the unit when comparing throughput.

Connect coordinates to storage

In row-major storage, A(i,k) has element offset iK+k and B(k,j) has offset kP+j. For column j=1 in this example, B uses offsets 1 and 3. A memory interface delivering contiguous rows therefore needs buffering or rearrangement to supply columns to the top of the array.

Build the arithmetic reference using wide integers, applying the chosen output conversion afterward. These small positive inputs do not test overflow. Later tests must add negative values, the most negative operand and a longer reduction. An identity B should reproduce A, while an all-zero row of A should produce an all-zero row of C. Record each PE's list of k terms as well as its final sum: a missing or repeated term is then visible even when two mistakes cancel numerically.