[SOLVED] CPSC 3300 - Project 3 -- Speed up Matrix Multiplication

Description

 In this project you are going to optimize an implementation of sequential Matrix Multiply provided in matmul_naive.c. The goal is to obtain a maximum overall speedup as you can with multiple optimization techniques. Note that you can’t use parallel computing for this project.

Start with the provided naïve implementation, and add optimization techniques one by one to hand tune the program and make it run faster. Common optimization techniques include register variable, loop interchanging, loop unrolling, blocking, prefetching. These techniques are commonly used by programmers and compilers.

Name the optimized code matmul_opt.c, compare the optimized code against the naïve implementation.

Submit matmul_opt.c and a report named “Matrix Multiplication Optimization.pdf” both to Canvas. The required sections and contents for the report is provided at the end of this document.

Matmul: C = A x B where A is a general m x k matrix, B is a general k x n matrix, and C is the product m x n matrix. For simplicity we assume m = k = n or square matrices in this project.

Compare hand-tuned program against naïve program. Always use -O0 (-[Big O][zero]) to turn off optimization in compilers when compiling the hand-tuned program and the naïve program. Compare the execution times of these two programs for various matrix sizes and calculate speedups, which is defined as Time_naive/Time_opt.

Timing: Use timing functions in the code to measure the performance. Example timing functions include gettimeofday and getrusage in Unix/Linux environments. Report the performances, speedups, and comparisons in figures or/and tables. Multiple matrix sizes should be examined in the experiments.

The timing and comparisons can be reported in a table as follows or in figures. In the table, T1 and T2 represent two different optimization techniques. Your method should include as many effective techniques as possible, so that the achieved speedup is the highest. Particularly, your method should include the blocking technique and use different block sizes. Assume that blocking is denoted as T4, the following table includes the timing info for two block sizes.

The report should be at least 4 pages (2 ½ pages single spaced) or if working as a team of two, 8 pages (5 pages single spaced).