Cache Memory for Matrix multiplication
Summary
This lecture and exercise come from CS:APP, the classic textbook from CMU. They let students explore how cache memory can be exploited to optimize the performance of matrix multiplication. The first step is to reorder the loops; the second is to divide the matrices into sub-blocks. As a further step, MATLAB can be used to show how commercial software performs on the same task. Running the multiplication on large matrices makes the performance gap clear.
CollapseLearning Goals
The students will learn the resources of hardware are limited on the computer (memory). The divide and conquer algorithm can be applied in a broad field.
MATLAB as a commercial software will be a good example to let the students know the computing efficiency is significant.
The divide and conquer algorithm that they learned from Data Structure and Algorithm course are useful.
MATLAB as a commercial software will be a good example to let the students know the computing efficiency is significant.
The divide and conquer algorithm that they learned from Data Structure and Algorithm course are useful.
Context for Use
The activity is for computer science students in the lower-core course, computer organization. It generally requires 2 hours for the lecture and a week for the lab part. The students need linear algebra basics and no experience with MATLAB. This is a natural extension of this course. We also talk about compiling, source code vs binary code, reverse engineering, etc.
This activity requires no experience with MATLAB. But after the activity, they will learn the power of MATLAB.
This activity requires no experience with MATLAB. But after the activity, they will learn the power of MATLAB.
Description and Teaching Materials
The MATLAB matrix multiplication is a natural extension of the cache memory lecture. The for-loop reordering and sub-blocking can make the multiplication faster. But MATLAB can still do the same operation even faster.
Cache Lab: Understanding Cache Memories (Acrobat (PDF) 46kB Sep8 26)
lecture: cache memories (Acrobat (PDF) 1.5MB Sep8 26)
Teaching Notes and Tips
Students have difference experience on linear algebra and MATLAB use. It should be ok to allow some students to use AI to write the MATLAB code for simulation.
Share your modifications and improvements to this activity through the Community Contribution Tool »
Assessment
The lab requires the students to write a report. They will use the template to write the review, results, struggles, and conclusions.
If any student mentions MATLAB in their report, this will be regarded as meeting the goal.
If any student mentions MATLAB in their report, this will be regarded as meeting the goal.
References and Resources
csapp webpage: https://csapp.cs.cmu.edu/