Matrix multiplication is a common operation in many real world applications such as wireless communication, image processing, video analysis and processing, computer games and graphics, computational finance, cryptography, and simulation of many physical and chemical processes, among others. If we have two 𝑛 ×𝑛 matrices A and B, then their product C = A*B is also a square 𝑛 ×𝑛 matrix whose entry 𝑐!” in column 𝑖 and row 𝑗 is given by the equation n
cij =Xaikbkj
k=1
For example, if 𝑛 = 8, then
Matrix multiplication on a conventional computer can be slow because typically processors have only one Arithmetic Logic Unit (ALU). Each element of the 8×8 product matrix requires 15 arithmetic operations on top of any address calculations needed to access the right memory contents and thus a full matrix multiply can take many clock cycles.
Implementing matrix multiplication in hardware allows us to take advantage of parallelism and high memory bandwidth to improve the performance significantly. The core computation in matrix multiplication is multiplying two numbers and adding it to a running sum (called multiplyaccumulate or MAC). So, in this laboratory exercise we will start with the implementation of a MAC in hardware and then use that MAC to realize two implementations of matrix multiplication and evaluate their performance.
You don’t have to implement the hardware on the DE10 board in this lab but you should still make sure that your designs synthesize properly and estimate their hardware resources.
Task 1 : Implement a MAC
Figure 1: Block Diagram for a Multiply Accumulator
One of the most fundamental building blocks for digital signal processing is the Multiply Accumulator (MAC) shown in Figure 1. The operation of a MAC is as follows: Given inputs 𝑥 and 𝑦 and accumulator register 𝑠, the operation
𝑠 ← 𝑠 +𝑥𝑦
is performed every clock cycle. With this operation, one can see how each element of C can be calculated over a number of clock cycles.
Write a Verilog program to implement the MAC module. Your module should take two 8-bit signed 2’s complement inputs and use a 19-bit signed accumulator to produce the result. It is important to be able to clear the MAC when each entry in C is calculated. Therefore, you should also include an input signal macc_clear that when asserted assigns the product of the inputs directly to the output as shown in the block diagram.
You may use the operator “ * “ in Verilog to instantiate a multiplier and “ + “ to instantiate an adder.
Write a testbench using the skeleton code provided to verify your design. Your testbench does not need to automatically verify your results but should thoroughly test your design. Show the output waveforms and resource utilization on the FPGA to your TA.
Task 2 : Matrix Multiply with One MAC
Figure 2: High-level block diagram for Task 2.
You will now design a module to multiply two 8×8 matrices, implementing the function C = A * B by instantiating only one of the MAC modules you have designed. Access one element from each of the input RAMs at a time and use your MAC in such a way that one entry of the product matrix C is calculated about every 8 or 9 clock cycles. This algorithm is very similar to how you would multiply two matrices by hand. Remember that you must access matrix B by columns while matrix A needs to be accessed by rows.
The input and output signals for your module are given in the table below.
| Signal Name | Signal Type | Description |
| clk | Input | Clock |
| start | Input | Start signal. Your module should not begin
calculation until this signal is asserted high |
| reset | Input | Reset signal. Should reset your module to its default waiting state. Note, this should NOT clear the contents of any RAM. |
| done | Output | Completion signal. This signal should be ‘0’ while your module is running, and ‘1’ when it has completed the multiplication. |
| clock_count[10:0] | Output | Number of elapsed clock cycles. This signal should be set to zero when the module begins calculation and increment by 1 every clock cycle until the multiplication is complete, at which point it stops incrementing. |
In order to test your module successfully with the provided testbench, you should make sure to do following:
- Initialize the contents of the RAMs associated with the A and B matrices to the contents of “ram_a_init.txt” and “ram_b_init.txt” respectively. Use the $readmemb() instruction inside of an initial block to do this.
- You should write the output RAM as its own module and instantiate it in your top-level design. It is very important that when you instantiate the RAM, you give it the instance name “RAMOUTPUT” and that when you write module, the memory vector is named “mem”. Make “mem” a signed variable so ModelSim interprets its contents as 2’s complement numbers. These steps are important so the testbench accesses the correct signals.
Make the following assumptions:
- Matrix A and Matrix B are 8×8 matrices stored in column major order in two independent RAM modules.
- The entries of matrices A and B are 8-bit signed numbers.
- Matrix C is an 8×8 matrix stored in a RAM in column major order.
- The entries of matrix C are 19-bit signed numbers.
Verify your module with the provided testbench, making only minimal changes to the testbench if necessary so signal and module names are consistent. Demonstrate the simulation to your TA and record the number of clock cycles the computation took.
Task 3 : Matrix Multiply with Two MACs
Figure 3: Example architecture for performing matrix multiplication using two MACs.
Performing matrix multiplication the way we did in Task 2 does not exploit any parallelism and thus does not offer much speedup over what we might be able to achieve on a simple processor. Since the M9K memory blocks are dual ported, we can read memory contents from two separate addresses each clock cycle. We can take advantage of this and parallelize our matrix multiplication hardware. One way you might consider doing this is to read one column from B and two rows from A at a time. This technique means that two entries of C can be calculated in parallel.
Modify your module from Task 2 in the following ways:
- Dual port just one of the input matrix memory RAMs. You can reference for help in implementing a dual port RAM. Remember that values will only be read from this RAM, making it really a ROM.
https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/max10/ug_m10_memory.pdf
- Instantiate a total of two MAC modules designed in Task 1.
- Make any necessary changes to your control logic to facilitate calculating multiple entries in the product matrix at a time.
Assume that your output RAM cannot be dual ported. Thus, it might be necessary to buffer values computed by the MACs so they can be written to memory one at a time.
Verify your design using the same testbench used in Task 2. Show your simulation results to your TA and record the number of clock cycles that the computation took.
Task 4 [Max 150 Points]
Optimize your design in Task III to have better throughput (MAC/s) by adopting parallelism in terms of MAC usage and pipelining the datapath.
This task will be graded relatively, which means each group will get the points out of 150 based on their designs and corresponding throughput.
To receive any points for this task you should have a fully synthesized and functional design.
Extra Credit [100 Points]
Sparse matrix vector Multiplication (SpMV)
In many emerging applications the matrices are very sparse, which means most of the entries in the matrices are zero. The straightforward algorithm that we are using thus far is extremely inefficient for sparse matrices since we are wasting time and power and memory bandwidth/capacity storing and multiplying by zeros. See
https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_for mat) for examples of how sparse matrices can be stored. Implement a Sparse parallel Matrix Vector multiplier based on the CSR format – assume the matrix is 16×16 and vector is 16×1 and assuming the sparsity is 25% which means only 4 elements per row are non-zero (100 points).
Lab Requirements
- Task 1 [50 points]
- Write a synthesizable model for a MAC.
- Write a testbench to verify the operation of the circuit.
- Verify your design through functional simulation. Demonstrate your simulation to your TA and have them sign a verification sheet when simulation is successful.
- Estimate the resources usage – the number of flip-flops, logic elements, memory blocks, embedded multipliers etc.
- Task 2 [100 points]
- Design a circuit and write the Verilog to perform matrix multiplication of two 8×8 matrices by instantiating a single MAC.
- Verify your design using the provided testbench. Demonstrate your simulation to your TA and have them sign a verification sheet when successful.
- Estimate the resources usage – the number of flip-flops, logic elements, memory blocks, embedded multipliers etc.
- Estimate the performance of your design in terms of number of clock cycles using the performance counter and identify the bottleneck of your design.
- Task 3 [100 points]
- Dual port one of the input matrix RAM modules and design a circuit that performs matrix multiplication using two MAC units.
- Verify your design using the provided testbench. Demonstrate your simulation to your TA and have them sign a verification sheet when successful.
- Estimate the resources usage – the number of flip-flops, logic elements, memory blocks, embedded multipliers etc.
- Estimate the performance of your design in terms of number of clock cycles using the performance counter and identify the bottleneck of your design.
- Task 4 [Maximum 150 Points]
- Optimize your Task III design to have better throughput.
- Verify your design using the provided testbench. Demonstrate your simulation to your TA and have them sign a verification sheet when successful.
Prelab [20 Points]
Design the state diagram for the controller for Task 2.
Lab report [30 Points]
Submit all Verilog code that you wrote in .v files in a single zip file. Don’t submit any of the instructor given test benches. [15 Points]
Submit a brief report on the lab and explain the reasoning behind the area/performance optimization methods that you adopted. [15 Points]
Testbench Description
A testbench to verify your design has been provided. A brief description of its operation is provided here. Refer to tb_lab6.v to review the sections described:
PART 1: The testbench initializes the matrix multiplication module by asserting a reset for 2 clock cycles, waiting idly for 2 clock cycles, then asserting the start signal for one clock cycle.
PART 2: The testbench then waits for the “done” signal to be set by the module. To ensure termination, a fork-join construct is used and if 2000 clock cycles pass before the done signal is set, the testbench automatically finishes.
PART 3: The A and B matrices are displayed. The expected result matrix C is calculated and displayed. The contents of RAM in the matrix multiply module are extracted and displayed.
PART 4: The contents of RAM are compared to the expected result. If all entries match what is expected, a success message is displayed. Otherwise, the indices of the mismatching elements are displayed.
