Previous module:
Next module:
University of Washington  
Department of Applied Mathematics  
AMATH 483/583   Assigned: May 08, 2019
Mid Term Exam   Due: May 15, 2019

Contents

Introduction

This assignment is extracted as with previous assignments into a directory midterm. In that directory is a file Questions.md with short answer questions that you will be asked in different parts of this assignment. To fill in your answers, open the file in vscode and insert your answers directly into the file, using the format indicated.

The tar ball for this assignment can be downloaded with this link.

Special Instructions for Mid Term

This is a take-home midterm exam for AMATH 483/583. Its purpose is to evaluate what you have learned so far in this course. The same rules as for homework assignments apply for the mid-term – with the following two exceptions:

  1. The exam may not be discussed with anyone except course instructors\ Do not discuss it with your classmates, with your friends, with your enemies. You may refer to your previous assignments, AMATH 483/583 slides and lectures. You may contact the instructors via private messages on Piazza to clarify questions. The same policies and penalties for plagiarism apply for the mid-term as for the regular assignments.

  2. No midterms will be accepted after 11:59pm PDT on 5/14\ The submission entry on Canvas will electronically close at this time and no further midterms will be accepted. Grace days cannot be applied to the midterm.

The mid-term will be graded by hand in addition to automatic testing. We haven’t really had any requirements on commenting your code, either with or the $/^$, $\,^/$ pair. Continuing in this regard, general code comments will not be required for the midterm, but are highly suggested. Any clarifying comments may help the graders award partial credit if your code doesn’t exhibit the correct behavior.

Preliminaries

For 483 students, this midterm consists of two problems: Implementing the primary functionality needed for compressed sparse column (CSC) matrix format and implementing sparse-matrix by dense matrix product. For 583 students, you will have in addition to compressed sparse column to also implement array of structures (AOS) sparse matrix format.

These implementations are carried out in various support files (which will be specified in each problem). There are four driver programs that will be used to test and time your implementations:

  1. matvec_test.cpp
  2. matvec_time.cpp
  3. matmat_test.cpp
  4. matmat_time.cpp

Targets for the corresponding exe files are given in your Makefile.

The tests and timing functionality for CSC and AOS is conditionally compiled in these files. If you look through the files you will see sections of code bracketed with one of these four macros:

  1. TEST_CSC
  2. TIME_CSC
  3. TEST_AOS
  4. TIME_AOS

If a particular macro is not defined, the corresponding test or timing code is not run. The definitions are supplied via the command line to the compiler – commenting or uncommenting the appropriate line in the Makefile will disable or enable (respectively) the appropriate testing or timing.

As supplied, the Makefile has all these macros commented out. You can build and run all four driver programs and they will test and time COO and CSR. As you build out CSC, you should uncomment the TEST_CSC and TIME_CSC macros. Similarly, for 583 students, when you build out AOS, uncomment TEST_AOS and TIME_AOS.

Warm Up

Sparse-Matrix Vector Product

As supplied, the driver programs matvec_test and matvec_time will compile and run with CSR and COO formats.

Compile and run matvec_test.exe and matvec_time.exe 

$ make matvec_test.exe
$ ./matvec_test.exe
$ make matvec_time.exe
$ ./matvec_time.exe

The driver matvec_time.exe will run and time matrix-vector product using a discretized 2D Laplacian (as presented in lecture) for various problem sizes and plot the performance in matvec_time.png.

The driver matvec_test.exe will run a few sanity tests on COO and CSR.

Problems

Sparse-Matrix Dense-Matrix Product

So far we have considered sparse matrices with their use in linear systems – noting that sparse matrix by vector product is a fundamental operation. In this problem we want to consider the effects of sparse matrix by dense matrix product.

First, in the file amath583sparse.cpp there are two functions to complete for this problem: operator* for COO times dense matrix and operator* for CSR times dense matrix. Note that as with operator* for COO and CSR times a vector, the operator* function invokes a member function in the corresponding class that then uses the internal matrix representation to carry out the product.

Next, in the files COOMatrix.hpp and CSRMatrix.hpp are skeletons for the actual multiplication.

Complete the operator* functions in amath583sparse.cpp for dense matrix product for COO and CSR and complete the corresponding matmat member functions in COOMatrix and CSRMatrix.

Compile and run matmat_test.exe and matmat_time.exe. As with matvec_time.exe, matmat_time.exe takes an argument that specifies the maximum problem size – where problem size in this case is the size of the sparse matrix. It also takes an argument that specifies the maximum number of columns in the matrix B (the dense matrix operand in the sparse matrix by dense matrix product). The program plots performance results in matmat_time.png.

(Include your answer in Questions.md.) How does the performance (in GFLOP/s) for sparse-matrix by dense matrix product (SPMM) compare to sparse-matrix by vector product (SPMV)? The performance for SPMM should be about the same as for SPMV in the case of a 1 column dense matrix.
What is the trend with increasing numbers of columns?

(Include your answer in Questions.md.) How does the performance of SPMM (in GFLOP/s) compare to the results you got dense matrix-matrix product in previous assignments? There should be a fairly large difference in GFLOP/s between sparse and dense matrix methods. Give some reasons for such a big difference.

Compressed Sparse Column Format

In lecture we derived the compressed sparse row format from coordinate format by first sorting the data based on the row indices stored in COO. By applying run-length encoding we compressed the row indices from a size equal to the number of non-zeros in the matrix down to the number of rows in the matrix (plus one).

A similar process could have been applied had we instead sorted the coordinate data by columns rather than rows. Such a format is known as compressed sparse column (CSC).

A skeleton for CSC format has been provided in CSCMatrix.hpp. In this case there are three member functions you need to complete:

  1. push_back – adds an element to the sparse matrix
  2. stream_coordinates – sends triples of (row, column, value) to an output stream
  3. matvec – computes matrix by vector product

Uncomment the macros for TIME_CSC and TEST_CSC in the Makefile and compile and run matvec_test.exe and matvec_time.exe

Extra Credit Implement matmat for CSC and compile and run matmat_test.exe and matmat_time.exe.

(Include your answer in Questions.md.) How does the performance of SPMM (in GFLOP/s) compare to the results you got dense matrix-matrix product in previous assignments? There should be a fairly large difference in GFLOP/s between sparse and dense matrix methods. Give some reasons for such a big difference.

(Include your answer in Questions.md.) How does the performance of CSC compare to the performance of CSR and of COO?
Explain why (or why not) there are any significant differences.

Array of Structs (AMATH583 Only)

In class we discussed that there are two ways to represent a coordinate (COO) sparse matrix – struct of arrays or array of structs. Our implementation (that we call COOMatrix) thus far has been the former: the row index information, the column index information, and the values are all stored in separate arrays.

You are to write a new implementation that implements the COO sparse matrix as an array of structs (AOS). With AOS, the sparse matrix information is kept in a single array, where each entry in the array is a data structure consisting of three pieces of information: row index, column index, and value.

A skeleton for AOS format has been provided in AOSMatrix.hpp. In this case there are three member functions you need to complete:

  1. push_back – adds an element to the sparse matrix
  2. stream_coordinates – sends triples of (row, column, value) to an output stream
  3. matvec – computes matrix by vector product

Uncomment the macros for TIME_AOS and TEST_AOS in the Makefile and compile and run matvec_test.exe and matvec_time.exe

(Include your answer in Questions.md.) How does the performance of AOS compare to the performance of COO?
Explain why (or why not) there are any significant differences.

Extra Credit Implement the matmat for AOS and compile and run matmat_test.exe and matmat_time.exe.

Submitting Your Work

Do a make clean in your midterm directory and then create a tar ball midterm.tar.gz containing all of the files in that directory. From within the midterm directory:

$ cd midterm
$ make clean
$ cd ..
$ tar zcvf midterm-submit.tar.gz --exclude "./midterm/.vscode" ./midterm

If you relied on any external references, list them in a file refs.txt and include that in your tarball as well (in the midterm subdirectory).

Previous section:
Next section: