Weak and Strong Scaling Study (25 points)

Overview

In this assignment, you will implement a parallel matrix multiplication program using OpenMP to explore both strong and weak scaling. Your program, matrixOMP.cc, will multiply two square matrices using a triple-nested loop. You will measure the execution time for different numbers of threads and matrix sizes, outputting this data to a CSV file for further analysis and visualization.

Objective and Expected Learning Outcomes

The primary objectives of this assignment are:

Parallel Matrix Multiplication:

  • Extend a basic matrix multiplication algorithm by adding OpenMP directives.
  • Understand how parallelism can accelerate computationally intensive tasks.

Strong and Weak Scaling Analysis:

  • Strong Scaling: Evaluate performance by increasing the number of threads while keeping the problem size fixed (e.g., a 1024×1024 matrix remains constant).
  • Weak Scaling: Evaluate performance by increasing the overall problem size so that each thread receives roughly the same workload as in the single-thread case. Note that the increase in problem size should reflect the algorithm’s complexity—for a single loop, doubling the size may suffice, but for double or triple nested loops, the problem size must be scaled appropriately to maintain an equal workload per thread

Performance Measurement:

  • Use OpenMP’s timing functions (e.g., omp_get_wtime()) to measure execution time accurately.
  • Collect data that shows the relationship between thread count, matrix size, and execution time.

Data Visualization:

  • Generate plots from the CSV data to illustrate the effects of strong and weak scaling on performance.
  • Analyze the scalability and efficiency of your parallel implementation.

Build System Proficiency:

  • Develop a Makefile to compile your C++ code into an executable named matrixOMP.
  • Ensure your Makefile includes targets for building (make all) and cleaning (make clean) the project.

Sample Code Snippet for Timing

#include <omp.h>
// Record the start time using OpenMP's wall-clock timer
double startTime = omp_get_wtime();

// Example parallel work: matrix multiplication using OpenMP
#pragma omp parallel for
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        for (int k = 0; k < N; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

// Record the end time
double endTime = omp_get_wtime();
printf("Time taken: %f seconds\n", endTime - startTime);

Instructions

Part 1: Implementing the Matrix Multiplication Program

  1. Create the Source File:
    • Name the file matrixOMP.cc, start by adapting a basic matrix multiplication code. Parse command-line arguments to accept: (1) matrix size (N) and (2) number of threads. - Dynamically allocate two N×N matrices (e.g., A and B) and initialize them (using random values or a constant for reproducibility).
  2. Parallelize the Computation:
    • Use OpenMP directives (such as #pragma omp parallel for and optionally the collapse clause) to parallelize the nested loops of the matrix multiplication.
    • Validate the correctness of your parallel implementation against a sequential version for a small matrix size.
  3. Performance Measurement and CSV Output:
    • Measure the execution time of the multiplication using omp_get_wtime().
    • Run experiments under two scenarios:
      • Strong Scaling: Use a fixed matrix size (e.g., 1024×1024) while varying the number of threads (e.g., 1, 2, 4, 8).
      • Weak Scaling: Increase the matrix size proportionally with the number of threads (e.g., for 1 thread, use 1024×1024, for 2 threads, double the amount of work, for 4 threads, four times the amount of work, etc.).
    • Output the performance data to a CSV file named matrixOMP.csv with the following format:
MatrixSize, Threads, Time, [Optional: Speedup/Efficiency]
1024, 1, <time>, <calculated speedup>
1024, 2, <time>, <calculated speedup>
...

Part 2: Makefile

  1. Create a Makefile that:
    • Compiles matrixOMP.cc into an executable named matrixOMP.
    • Uses the OpenMP flag (e.g., -fopenmp) during compilation.
    • Provides the following targets:
      • make all to build the executable.
      • make clean to remove build artifacts and the executable.
  2. Test the Makefile to ensure it correctly compiles and cleans the project on the cs455.cs.uic.edu resource.

Part 3: Experiment Analysis and Visualization

  1. Data Visualization:
    • Generate graphs (using any tool of your choice, e.g., Python’s matplotlib) to illustrate:
      • The relationship between the number of threads and execution time for a fixed matrix size (strong scaling).
      • The relationship between matrix size (workload) and execution time for an increasing number of threads (weak scaling).
    • Ensure your graphs are clear and well-labeled.
  2. Reflection: Write a brief reflection that recounts your experience with the assignment, including your approach to writing the C++ program with OpenMP for matrix multiplication to study both strong and weak scaling, and detailing your design decisions and any challenges faced, such as difficulties in measuring performance or generating expected speedup and scalability graphs. Reflect on whether the experimental outcomes met your expectations, discuss factors that may have influenced any discrepancies, and share the lessons learned that will shape your future work in parallel programming and performance optimization.

Submission Guidelines and Evaluation Criteria

  • Add and/or edit the following files in your GitHub repository:
    • matrixOMP.cc - C++ source code for the assignment.
    • Makefile - Makefile to build your project.
    • matrixOMP.csv - CSV file containing all the performance data collected.
    • matrixOMP.png - graph(s) visualizing your experiment results (or matrixOMPstrong.png and matrixOMPweak.png)
    • matrixOMP.txt - reflection text file discussing your experience, challenges, and insights.
  • Include a brief reflection (matrixOMP.txt) in your submission that recounts your experience with the assignment. In your reflection, describe how you approached writing the C++ program with OpenMP for matrix multiplication to study both strong and weak scaling. Discuss your design decisions and any challenges you encountered, including difficulties in measuring performance or generating the expected speedup and scalability graphs. Reflect on whether the experimental outcomes aligned with your expectations and, if not, explore what factors might have influenced the discrepancies. Share the lessons you learned from this process and how these insights might shape your future work in parallel programming and performance optimization.
  • When your program is ready for grading, commit and push your local repository to the remote git classroom repository following the Assignment Submission Instructions.
  • Your work will be evaluated on your adherence to instructions, code quality, file naming, completeness, and your reflection on the assignment.

Additional Resources