Open-Ended Portion: Optimizing Multi-Threaded Matrix Multiply (75%)

In this portion of the lab, you will implement and optimize a multithreaded kernel for the dual-core system.

\[C_{ij} = \sum_{k} A_{ik} \mathbin{\&} B_{kj}\]

The loop structure, data access patterns, and memory traffic are identical to those of conventional matrix multiplication. The only difference is the kernel performs a bitwise AND operation instead of multiplication. Since Sodor does not have a hardware multiplier, software multiplication would require tens of instructions per operation, obscuring the memory-system effects we want to study. Replacing multiplication with bitwise AND keeps the computation lightweight, allowing you to focus on cache behavior, memory traffic, and coherence overhead.

A naive implementation is provided in ${TESTDIR}/mt-matmul-naive/mt-matmul_naive.c. Begin by building and running the mt-matmul-naive benchmark to establish a performance baseline:

cd ${SIMDIR}
make CONFIG=CS152Lab4MIConfig  run-binary-fast BINARY=${TESTDIR}/mt-matmul-naive.riscv
make CONFIG=CS152Lab4MSIConfig run-binary-fast BINARY=${TESTDIR}/mt-matmul-naive.riscv

Write your code in the matmul_opt() function found in ${TESTDIR}/mt-matmul-opt/mt-matmul_opt.c. Its lda parameter is the size of each square matrix. For example, if lda = 32, each matrix has 32 rows and 32 columns. Since the matrices are stored as 1D arrays, we use i * lda + j to access the element at row i, column j.

After writing your code, rebuild the benchmarks:

cd ${TESTDIR}
make

Then, run the mt-matmul-opt benchmark on the simulator as follows:

cd ${SIMDIR}
make CONFIG=CS152Lab4MIConfig  run-binary-fast BINARY=${TESTDIR}/mt-matmul-opt.riscv
make CONFIG=CS152Lab4MSIConfig run-binary-fast BINARY=${TESTDIR}/mt-matmul-opt.riscv

Once your code passes the correctness test, do your best to optimize its performance. Your results from the MI and MSI runs will both be compared against a threshold to determine the final grade for this section.

Submission

Use the following command to prepare your code for submission, and upload the resulting file to the Gradescope autograder.

cd ${TESTDIR}
make zip-matmul

Note that code outside mt-matmul_opt.c will be ignored. Your submitted function must only compute the result and, if needed, call barrier(nc). Before submitting, remove all debugging and performance measurement code. The autograder will assign no credit if your implementation:

  • Calls printf(), setStats(), printStats(), or exit().
  • Accesses performance counters.
  • Reads verify_data.

Only submit once per group. Make sure to add your group members to your autograder submission.