Due : 1 1 :59pm Mon 0 1-May-2023

Approximately 3.0-4.0% of total grade

Submit to Gradescope

Projects are ind iv idual work : no collaboration with other students is allowed. Seek help from course staff if you get stuck for too long.

CODE/TEST DISTRIBUTION : p4-code.z ip

V ideo Overv iew : Not yet ava ilable

CHANGELOG :

Wed Apr 26 02 :39 : 17 PM CDT 2023

Some errors in the autograder for P4 have been corrected on Gradescope. If you see problems that indicate compilation failed on your submission, resubmit or ask a staff member to re-run the autograder to get new result.

Tue Apr 25 09 :22 :29 AM CDT 2023

As noted in Post 604, Problem 1 Test #5 would often time out for correct code due to Valgrind slowing down the computationally intense loops to check memory references. The tests have been adjusted to account for this and can be updated using the following commands in a terminal

Fr i Apr 2 1 03 : 1 1 :0 1 PM CDT 2023

Fixed several typos such as incorrect totals for problem points and mention of a writing answers in a writeup file which should instead be done in the comments in matsquare_optm.c

Fr i Apr 2 1 0 1 :05 : 17 PM CDT 2023

The missing test-input/ directory has been added to the codepack which should fix problems for those attempting to run make test-prob2. Download a fresh copy of the code pack and copy this directory into your project directory.

Table of Contents

1. Introduction

2. Download Code and Setup

3. Problem 1 : Squaring a Matrix

3.1. Overview

3.2. Optimize Matrix Squaring

3.3. Evaluation on loginNN

3.4. matsquare_print.c Testing Program

3.5. Optimization Suggestions and Documentation

3.6. Grading Criteria for Problem 1 (55%)

4. Problem 2 : showsym

4.1. Overview

4.2. ELF File References

4.3. Overall Approach

4.4. ELF Header and Section Header Array

4.5. String Tables, Names, Section Headers

4.6. Symbol Table and .strtab

4.7. Behavior in Error Cases

4.8. showsym Template

4.9. Grading Criteria for showsym (45%)

5. Project Submission

5.1. Submit to Gradescope

5.2. Late Policies

1 Introduction

This assignment focuses on two aspects discussed in lecture over the last month.

1. Program Optimization : The project pack provides a baseline implementation for a function and asks for a more performant version which runs faster. To do so, one must exploit knowledge of the memory hierarchy and processor architecture to complete the computations more quickly.

2. Memory Mapping a Binary file in the ELF format and locating a specific section to access its contents.

2 Download Code and Setup

Download the code pack linked at the top of the page. Unzip this which will create a project folder. Create new files in this folder. Ultimately you will re-zip this folder to submit it.

3 Problem 1 : Squaring a Matrix

3.1 Overview

A problem that occasionally arises in numerical computing when working with Matrices (2D Arrays) is to compute the Square of a matrix. This is a special case of general matrix multiplication and

students unfamiliar with this operation should study it to get some context for the present work. Terminology can get a little confusing so keep the following in mind.

A Square Matr ix has equal numbers of rows and columns and can be multiplied by itself.

Squar ing a matrix, sometimes notated M*M = M^2 is multiplying a matrix by itself which can only be done if it is a square matrix (equal rows/columns).

The diagram below illustrates the result of squaring a matrix by multiplying it by itself.

Figure 1 : 3 by 3 matrix M with colored elements along with result of squaring the matrix as M*M.

Note that that for each of the elements of the squared matrix, the elements are the result of a row multiplied by a column from the original matrix :

The file matsquare_base.c provides a baseline function that performs this computation in a direct fashion as the above definition  indicates The algorithm uses the most "natural" approach of multiplying each row by each column to produce the result in the for each part of the squared result. As you survey the code, note the use of various convenience macros such as MGET(mat,i,j) interact with the matrix type used.

Note that the original matrix comes in as the parameter mat and the result of squaring the matrix is stored in the parameter matsq.

While this algorithm is a direct translation of how humans would visually calculate the square of small matrices, it is unfortunately fairly slow when executing on most modern computing systems.

3.2 Optimize Matrix Squaring

The purpose of this problem is to write matsquare_OPTM() which is a faster version of the provided matsquare_BASE() to calculate the results.

Write your code in the file matsquare_optm.c.

Keep the following things in mind.

1. You will need to acquaint yourself with the functions and types related to matrices and vectors provided in the matvec.h and demonstrated in the baseline function. Understanding the layout of the matrix in memory is essential to unlocking performance.

2. The goal of matsquare_OPTM() is to exceed the performance of matsquare_BASE() by as much as possible.

3. To achieve this goal, several optimizations must be implemented and suggestions are given in a later section.

4. You will need to document your optimizations in comments included in the matsquare_optm.c file and provide timing results of running the optimized version.

5. Part  of  your  grade will be based  on  the  speed  of  the  optimized  code  on  the machine loginNN.cselabs.umn.edu. The main routine matsquare_benchmark.c will be used for this.

Some details are provided in subsequent sections.