25) HW3 Review

25) HW3 Review#

Today#

    1. Review of HW3

    1. Submission expectations and reminders

1. Review of HW3#

Solution to HW3. Here is my C code:

  1
  2#include <argp.h>
  3#include <math.h>
  4#include <omp.h>
  5#include <stdbool.h>
  6#include <stdio.h>
  7#include <stdlib.h>
  8#include <string.h>
  9
 10struct Args {
 11  size_t length;
 12  size_t nreps;
 13  bool block;
 14  size_t unroll_factor;
 15};
 16
 17// static memory variable declared here
 18static struct argp_option options[] = {
 19  {"length", 'S', "size_t", 0, "Length of each vector"},
 20  {"nreps", 'r', "size_t", 0, "Number of repetitions"},
 21  {"block", 'b', NULL, 0, "Compute block dot products (versus a single dot product)"}
 22};
 23
 24static error_t parse_opt (int key, char *arg, struct argp_state *state)
 25{
 26  struct Args *args = state->input;
 27  switch (key) {
 28  case ARGP_KEY_INIT:
 29    args->length = 24;
 30    args->nreps = 10;
 31    args->block = false;
 32    break;
 33  case 'S':
 34    args->length = strtol(arg, NULL, 10);
 35    break;
 36  case 'r':
 37    args->nreps = strtol(arg, NULL, 10);
 38    break;
 39  case 'b':
 40    args->block = true;
 41    break;
 42  default:
 43    return ARGP_ERR_UNKNOWN;
 44  }
 45  return 0;
 46}
 47
 48int I = 8;
 49int J = 4;
 50double tol = 1e-6;
 51
 52int c_length[] = {3, 4};
 53
 54
 55// Function declarations here
 56double dot_product(int S, const double *a, const double *b);
 57double vector_norm(const double *a, int S);
 58int is_orthogonal(int S, const double *a, const double *b, double tol);
 59void bdot(int I, int S, int J, const double *m, const double *n, double *p);
 60
 61double dot_product(int S, const double *a, const double *b){
 62
 63    double sum = 0;
 64    for (int i = 0; i<S; i++)
 65        sum += a[i] * b[i];
 66
 67    return sum;
 68}
 69
 70double vector_norm(const double *a, int S){
 71
 72    double sum = 0;
 73    for (int i = 0; i<S; i++)
 74        sum += pow(a[i],2);
 75
 76    return sqrt(sum);
 77}
 78
 79int is_orthogonal(int S, const double *a, const double *b, double tol){
 80    
 81    return (fabs(dot_product(S, a, b) <= tol));
 82 }
 83
 84// Performs the operation
 85//   P = M * N
 86// where M and N have shape (I,S) and (S,J) respectively.
 87// This version stores M as row-major and N as column-major.
 88void bdot(int I, int S, int J, const double *m, const double *n, double *p){
 89
 90    for (int i=0; i<I; i++) {
 91        for (int j=0; j<J; j++) {
 92            p[i*J+j] = dot_product(S, &m[i*S], &n[j*S]);
 93        }
 94    }
 95}
 96
 97static void init_bdot(int I, int S, int J, double *m, double *n) {
 98    for (int s=0; s<S; s++) {
 99        for (int i=0; i<I; i++)
100            m[i*S + s] = 1000*(i+1) + s+1;
101        for (int j=0; j<J; j++)
102            n[j*S + s] = 1./(1000*(j+1) + s+1);
103    }
104}
105
106
107// Reference matrix-matrix multiply product implementation
108void matrix_ref(int I, int S, int J, const double *m, const double *n, double *p){
109    for (int i=0; i<I; i++) {
110        for (int j=0; j<J; j++) {
111            p[i*J+j] = 0.0;
112            for (int s=0; s<S; s++) {
113                p[i*J+j] += m[i*S + s] * n[j*S + s];
114            }
115        }
116    }
117}
118
119static void report_dot(const char *name, const double result, const double ref_result) {
120
121  if (fabs(result - ref_result) > 1e-10) {
122    printf("Result = %f failed to validate with expected value %f\n", result, ref_result);
123    return;
124  }
125  printf("%s matches the reference result.\n", name);
126}
127
128static void report_is_orthogonal(const char *name, const int result, const int ref_result) {
129  if (result != ref_result) {
130    printf("Result = %d failed to validate with expected value %d \n", result, ref_result);
131    return;
132  }
133  printf("%s matches the reference result. The two vectors are %s \n", name, ref_result ? "orthogonal.": "not orthogonal.");
134}
135
136static void report_vector_norm(const char *name, const double result, const double ref_result) {
137
138  if (fabs(result - ref_result) > 1e-10) {
139    printf("Result = %f failed to validate with expected value %f\n", result, ref_result);
140    return;
141  }
142  printf("%s matches the reference result.\n", name);
143}
144
145static void report_bdot(const char *name, int I, int J, const double *result, const double *ref_result) {
146  if (result && ref_result && result != ref_result) {
147    for (int i=0; i<I; i++) {
148      for (int j=0; j<J; j++) {
149        if (fabs(result[i*J + j] - ref_result[i*J + j]) > 1e-10) {
150          printf("Result[%d,%d] = %f failed to validate with expected value %f\n", i, j, result[i*J + j], ref_result[i*J + j]);
151          return;
152        }
153      }
154    }
155  }
156  printf("%s matches the reference result.\n", name);
157}
158
159
160#define REPORT_BDOT(f, I, S, J, m, n, p, p_ref) do { \
161        f(I, S, J, m, n, p);                         \
162        report_bdot(#f, I, J, p, p_ref);             \
163} while (0)
164
165int main(int argc, char **argv){
166
167    struct Args args;
168    struct argp argp = {options, parse_opt, NULL, NULL};
169    argp_parse(&argp, argc, argv, 0, 0, &args);
170    size_t S = args.length;
171
172    switch (args.block) {
173    case false: { // single dot product case
174        // stack memory variable declarations here
175        double a1[] = {1, 0, 0};
176        double b1[] = {0, 1, 0};
177        double a2[] = {1, 2, 3, 4};
178        double b2[] = {1, 1, 1, 1};
179
180        // result of (a1,b1) and (a2,b2) dot products and reference values
181        double c1, c2;
182        double c1_ref = 0;
183        double c2_ref = 10;
184
185        // result of is_orthogonal 
186        int flag1, flag2;
187        int flag1_ref = 1; // a1 and b1 are orthogonal
188        int flag2_ref = 0; // a2 and b2 are not orthogonal
189
190        // result for vector_norm
191        double na1, na2, nb1, nb2;
192        double na1_ref = 1.0;
193        double na2_ref = 5.477225575051661;
194        double nb1_ref = 1.0;
195        double nb2_ref = 2.0;
196
197        // calls to your functions by reference here
198        // print statements to show results
199        c1 = dot_product(c_length[0], a1, b1);                               
200        report_dot("dot_product of a1 and b1", c1, c1_ref); 
201        c2 = dot_product(c_length[1], a2, b2);                               
202        report_dot("dot_product of a2 and b2", c2, c2_ref); 
203
204        flag1 = is_orthogonal(c_length[0], a1, b1, tol);
205        report_is_orthogonal("is_orthogonal between a1 and b1", flag1, flag1_ref); 
206        flag2 = is_orthogonal(c_length[1], a2, b2, tol);
207        report_is_orthogonal("is_orthogonal between a2 and b2", flag2, flag2_ref); 
208
209        na1 = vector_norm(a1, c_length[0]);
210        nb1 = vector_norm(b1, c_length[0]);
211        na2 = vector_norm(a2, c_length[1]);
212        nb2 = vector_norm(b2, c_length[1]);
213        report_vector_norm("vector_norm of a1", na1, na1_ref);
214        report_vector_norm("vector_norm of a2", na2, na2_ref);
215        report_vector_norm("vector_norm of b1", nb1, nb1_ref);
216        report_vector_norm("vector_norm of b2", nb2, nb2_ref);
217
218        } break;
219        case true: { // blocked dot product case
220            // Initialize the matrices (as flattened vectors)
221            // heap memory allocations here
222            double *m = malloc(I * S * sizeof(double));
223            double *n = malloc(J * S * sizeof(double));
224            double *p = malloc(I * J * sizeof(double));
225            double *p_ref = malloc(I * J * sizeof(double));
226
227            init_bdot(I, args.length, J, m, n);
228            matrix_ref(I, S, J, m, n, p_ref);
229            REPORT_BDOT(bdot, I, S, J, m, n, p, p_ref);
230
231            // free allocated heap memory here
232            free(m); free(n); free(p); free(p_ref);
233    } break;
234    }
235
236    return 0;
237}
238

This program can be compiled with the GNU C compiler with:

gcc dot.c -lm -o dot

and executed with

./dot

or

./dot -b

to test the blocked version.

Common mistakes#

Here is a list of common mistakes that a few people made:

  • Part 4: Not really implementing a blocked dot product between the rows of \(M\) and the columns of \(N\). The best way would have been reusing the dot_product function that was implemented for Part 1. This allows for code re-use, which is a good practice.

  • E.C.: not safely initializing to zero the output variable for the triple nested loop matrix-matrix multiplication. You could have achieved this by either invoking calloc instead of malloc or by manually initializing to zero all entries of the output variable (typically this is done right before the inner-most loop).

2. Submission expectations and reminders#

  • In general, when you receive an Assignment via a GitHub Classroom link, you want to clone your assignment repository, by doing

git clone your_assignment_repository_url

  • You can also work on a back-up repository or directory of your choice if you want to, for your scrap work, but you have to clone the assignment repository and submit your work there to be considered for submission and grading.

  • As soon as you clone your Assignment repository, move to that repository

cd your_assignment_repository

  • Create a new feature branch and switch to that. You can do this in two ways:

    • git checkout -b name_of_your_branch

    • git branch name_of_your_branch and then git checkout name_of_your_branch

  • Do NOT work directly off main

  • You can work on your feature branch as much as you like and create repeated incremental snapshots of your work via git commit. Always remember to use meaningful commit messages to remind yourself (and others) about your work in that moment in time. In a terminal you can simply do this by

git commit -m "Your commit message"

You can also write multi-line more detailed commit messages if you want. Just simply separate them with a space, and repeat the -m option, as in:

git commit -m "Your commit message" -m "Your more detailed message on a new line"

  • When you are satisfied with your committed work, you can push it to your working branch via:

git push origin your_branch_name

If it is the first time you are doing this, git will automatically tell you that you can open a Pull Request with your changes. Just CTRL-click on the URL that git shows you in the terminal and you will be sent to your Pull Request web interface.

Any successive changes that you want to push to your branch, they will be automatically reflected on the open PR.

  • Only changes made within the deadline (including the lateness window) will be graded.

  • Remember not to attempt to close or merge your PR without any Reviewer (in this case your instructor) approval.

  • Always remember to double check the File changed tab in your PR. If you see files that should not belong there (e.g., files automatically created by your IDE or virtual environment files) remove them.

  • If you are using an IDE that automatically creates hidden project files that you might inadvertently push to your branch, it is always a good practice to use a .gitignore file that specify which files you do not want to be tracked by git, and therefore, pushed to your branch. Recall that we covered this in our first lecture.

Reminder about the AI policy in this course#

A friendly reminder that in this course, we follow the University Senate’s extended definition of plagiarism that includes the un-cited use of generative AI applications, specifically: “representing work produced by generative Artificial Intelligence as one’s own.”

I provided in the Syllabus examples of how to properly cite the use of any genAI or LLM tool.

Contents