In this workshop, you are to analyze a serial application. 

Learning Outcomes

Upon successful completion of this workshop, you will have demonstrated the abilities to

• profile a serial application
• present the results of your analysis in an interesting graphical way
• itemize and explain what you have learned in completing this workshop

Specifications

Consider the following application that adds and multiplies matrices.  The user defines the size of the matrices (n) on the command line:

 // Profile a Serial Application - Workshop 1
 // w1.cpp

 #include <iostream>
 #include <iomanip>
 #include <cstdlib>
 #include <ctime>

 void init(float** a, int n) {
     float f = 1.0f / RAND_MAX;
     for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             a[i][j] = std::rand() * f;
 }

 void add(float** a, float** b, float** c, int n) {
     for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
             c[i][j] = a[i][j] + 3.0f * b[i][j];
 }

 void multiply(float** a, float** b, float** c, int n) {
     for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++) {
             float sum = 0.0f;
             for (int k = 0; k < n; k++)
                 sum += a[i][k] * b[k][j];
             c[i][j] = sum;
         }
 }

 int main(int argc, char* argv[]) {

     // interpret command-line argument
     if (argc != 2) {
         std::cerr << argv[0] << ": invalid number of arguments\n"; 
         std::cerr << "Usage: " << argv[0] << "  size_of_matrices\n"; 
         return 1;
     }
     int n  = std::atoi(argv[1]);   // size of matrices

     float** a = new float*[n];
     for (int i = 0; i < n; i++)
        a[i] = new float[n];
     float** b = new float*[n];
     for (int i = 0; i < n; i++)
        b[i] = new float[n];
     float** c = new float*[n];
     for (int i = 0; i < n; i++)
        c[i] = new float[n];
     std::srand(std::time(nullptr));
     init(a, n);
     init(b, n);

     add(a, b, c, n);
     multiply(a, b, c, n);

     for (int i = 0; i < n; i++)
        delete [] a[i];
     delete [] a;
     for (int i = 0; i < n; i++)
        delete [] b[i];
     delete [] b;
     for (int i = 0; i < n; i++)
        delete [] c[i];
     delete [] c;
 }

Profiles

g++ Version 8.2.0

Version 8.2.0 of the GNU g++ compiler is available in matrix's local system directory.  Compile your source code using the following Makefile, which accesses this version of the compiler.

# Makefile for w1
#
GCC_VERSION = 8.2.0
PREFIX = /usr/local/gcc/${GCC_VERSION}/bin/
CC = ${PREFIX}gcc
CPP = ${PREFIX}g++

w1: w1.o
        $(CPP) -pg -ow1 w1.o

w1.o: w1.cpp
        $(CPP) -c -O2 -g -pg -std=c++17 w1.cpp 

clean:
        rm *.o
 

-O2 directs the compiler (g++) to optimize the code to level 2. 
-pg directs the compiler/linker to write the extra code needed for profiling to gmon.out. 
-g directs the compiler to produce debugging information for use with gdb. 
-o directs the linker to name the executable with the string immediately following -o. 
-std invokes the C++17 version of the compiler, which accepts the nullptr keyword. 
The highlighted statements are the rules applied by the Makefile.

A single tab (not blank spaces) identifies a Makefile rule.  Make sure that after copying this file, a single tab and not a blank spaces precedes each rule. 

To execute this Makefile, enter the command

 > make

Test Runs

Run and profile w1 for 100 by 100 matrices using the following commands

 > time w1 100
 > gprof -p -b w1 > w1.100.flt

The -p option directs the profiler (gprof) to produce a flat profile.  The -b option directs the profiler to omit detailed explanations of the column headings from the output. 

Repeat these steps for the matrix sizes listed below.  The larger sizes take a bit of time, so be patient.  Record the elapsed time for each case. 

Save your results in a spreadsheet file named w1.ods or w1.xls.

Prepare a 3D look realistic column chart showing the process times for add() and multiply() and the elapsed time with n along the horizontal axis as shown below. 

You can create the chart in Open Office using the following steps:

• Highlight data and labels, excluding multiply()/total column
• Select Chart in the Toolbar
• Chart Type - check 3D Look Realistic Column
• Data Range - 1st row as label, 1st column as label
• Chart Elements - add title, subtitle, axes labels

You can create the chart in Excel using the following steps:

• Select Insert Tab -> Charts -> Column -> 3D Clustered Column
• Switch Row and Column
• Select Data -> Filter Symbol -> uncheck n -> Apply
• Select Data -> Select edit on horizontal axis labels -> enter 500,1000,1500,2000 -> OK
• Select Data -> Plus Symbol -> Check Axis Titles
• Select Data -> Plus Symbol -> Chart Title - enter title and subtitle

Save your chart as part of your spreadsheet file.

SUBMISSION

Upload your submission files as separate files.  DO NOT ZIP your files for the submission.  If you submit a zipped file, you will be asked to resubmit your files separately and your submission will attract a 20% penalty.

Upload your submission to Blackboard: 

• Login to
• Select your course code
• Select Workshop 1 under Assignments
• Upload your spreadsheet file (click Browse My Computer, select your file, click Open)
• Under "Add Comments" write a short note to your instructor containing the following: 
  • Compare the values for the add() and multiply() functions from your table
  • include a conclusion about the trends as the problem size grows
  • identify the Big-O class of the add() and multiply() algorithms
  • describe in your own words what you have learned in completing this workshop.
• When ready to submit, press "Submit"