Name: _____________________________ 6 Digit StudentID: ___ ___ ___ ___ ___ ___

Worksheet 04: Matrix Multiplication and Nested Join Fork Loops

Matrix Multiply

Imagine square matrices a, b, and result each of size 1000 by 1000. It follows that n, m, and p below will each be 1000.

int n = a.length;
int m = b[0].length;
int p = a[0].length;

Imagine further that you are targetting creating ~10 times as many tasks as available processors.

Note: the code below uses a single (1) join_void_fork_loop.

• Is this reasonably appropriate if you had 8 available processors? Yes / No
• What if you had 100 available processors? Yes / No

join_void_fork_loop(0, n, (i) -> {
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < p; k++) {
            result[i][j] += a[i][k] * b[k][j];
        }
    }
});

Note: the code below uses two (2) nested join_void_fork_loops.

• Is this reasonably appropriate if you had 8 available processors? Yes / No
• What if you had 100,000 available processors? Yes / No

join_void_fork_loop(0, n, (i) -> {
    join_void_fork_loop(0, m, (j) -> {
        for (int k = 0; k < p; k++) {
            result[i][j] += a[i][k] * b[k][j];
        }
    });
});

Note: the code below uses three (3) nested join_void_fork_loops.

• Is this reasonably appropriate if you had 8 available processors? Yes / No
• What if you had 100,000,000 available processors? Yes / No

join_void_fork_loop(0, n, (i) -> {
    join_void_fork_loop(0, m, (j) -> {
        join_void_fork_loop(0, p, (k) -> {
            result[i][j] += a[i][k] * b[k][j];
        });
    });
});

Single Join Fork Loops

For the code below:

• How many times will doSomething1d be executed? _______________
  
  
• How many times will fork be executed? _______________
  
  
• How many times will join be executed? _______________

join_void_fork_loop(0, n, (i) -> {
    doSomething1d(i);
});

Nested Join Fork Loops

For the code below:

• How many times will doSomething2d be executed? _______________
  
  
• How many times will fork be executed? _______________
  
  
• How many times will join be executed? _______________

    join_void_fork_loop(0, n, (i) -> {
        join_void_fork_loop(0, m, (j) -> {
            doSomething2d(i, j);
        });
    });

Post Lecture

Synthesize today's class session

What is unclear?