Here is this weeks lab, but its a bit unique, so you need to pay extra careful attention to my instructions. You need to follow the instructions in the document as well as adhere to the rubric in the marking guide decument to a very high standard. Here are some extra information you shoul make use of:

Dear FIT3143 Students,

Good day to you. This is a lengthy post, but it contains important information to help you in Week 11, Lab #6.

Please refer to the following points.

I. Task 1 (No marks, but needs to be completed).

Technically, the code below completes most of Task 1. You need to modify the serial code using the sample code below, run the experiments, and record the results in Table 1 as per the lab specifications. You can also refer to this separate post by Mason Hodge, which contains an amended serial code that feeds in the matrix size as a command line argument (Thank you, Mason).

You choose either one of the following partitioning methods for Task 1.

a) Straightforward row partitioning method

Figure 1 - Example of row-only partitioning method using 4 threads.

Sample algorithm and code for row-only partitioning. This code is based on Figure 1 as an example and should work with any number of threads.

void *ThreadFuncRowPartition(void *pArg)
{
// Assume the matrix arrays, row, column and commonPoint variables are global variables and initialised in main function.
int i, j, k;
int my_rank = ((int)pArg);
int NUM_THREADS = sysconf(_SC_NPROCESSORS_ONLN); // Get number of threads from system

int rpt = rowC / NUM_THREADS; 
int rptr = rowC % NUM_THREADS; 

int sp = my_rank * rpt; 
int ep = sp + rpt; 
if(my_rank == NUM_THREADS-1)
    ep += rptr;

for(i = sp; i < ep; i++){
    for(j = 0; j < colC; j++){
        for(k = 0; k < commonPoint; k++){
            pMatrixC[(i*colC)+j] += (pMatrixA[(i*colA)+k] * pMatrixB[(k*colB)+j]);
        }
    }
}
return NULL;
content_copy
Use code with caution.

}

b) Tile partitioning/submatrix method, with a fixed column divisor

We fix either the maximum number of column divisors or the maximum number of row divisors in the submatrix design. We fix the maximum number of column divisors in Figure 2 below and the code example.

Figure 2 - Example of tile partitioning method using 6 threads, with a fixed column divisor (red vertical line) that splits the tiles into left and right regions. The total number of threads should always be an even number when implementing this method.

Sample algorithm and code for tile partitioning (note that this code is not neat, but the logic should work). This code is based on Figure 2 as an example and should work as long as the number of threads is divisible by 2 without a remainder.

void *ThreadFunc2(void *pArg){
// Assume the matrix arrays, row, column and commonPoint variables are global variables and initialised in main function.
int i, j, k;
int my_rank = ((int)pArg);
int NUM_THREADS = sysconf(_SC_NPROCESSORS_ONLN); // Get number of threads from system

int row_start_point, row_end_point;
int col_start_point, col_end_point;
int threadColDiv = 1;
int threadColDivRemain = 0;
int threadRowDiv = 1;
int threadRowDivRemain = 0;

threadColDiv = colC / 2;
threadColDivRemain = colC % 2;
threadRowDiv = rowC / (NUM_THREADS / 2);
threadRowDivRemain = rowC % (NUM_THREADS / 2);

if(my_rank % 2 == 0){
    // Even thread
    if(my_rank == (NUM_THREADS - 2)){
        // Last even thread
        row_start_point = (my_rank / 2) * threadRowDiv;
        row_end_point = row_start_point + threadRowDiv + threadRowDivRemain;
    }else{
        // Not last even thread
        row_start_point = (my_rank / 2) * threadRowDiv;
        row_end_point = row_start_point + threadRowDiv;
    }
    col_start_point = 0;
    col_end_point = threadColDiv;
}else{
    // Odd thread
    if(my_rank == (NUM_THREADS - 1)){
        // Last odd thread
        row_start_point = (my_rank / 2) * threadRowDiv;
        row_end_point = row_start_point + threadRowDiv + threadRowDivRemain;
    }else{
        // Not last odd thread
        row_start_point = (my_rank / 2) * threadRowDiv;
        row_end_point = row_start_point + threadRowDiv;
    }
    col_start_point = threadColDiv;
    col_end_point = col_start_point + threadColDiv + threadColDivRemain;
}

// Matrix multiplication
for(i = row_start_point; i < row_end_point; i++){
    for(j = col_start_point; j < col_end_point; j++){
        for(k = 0; k < commonPoint; k++){
            pMatrixC[(i*colC)+j] += (pMatrixA[(i*colA)+k] * pMatrixB[(k*colB)+j]);
        }
    }
}
return NULL;
content_copy
Use code with caution.

}

c) A dynamic tile partitioning/submatrix method

Figure 3 - Example of dynamic tile partitioning method using 9 threads. The submatrix consists of a two-dimension tile structure. The total number of threads should be a perfect square value when implementing this method. You can specify this in the code and report, and there is no penalty for it.

Sample algorithm and code for tile partitioning. This code is based on Figure 3 as an example and should work as long the number of threads is a perfect square.

void *ThreadFunc3(void *pArg){
// Assume the matrix arrays, row, column and commonPoint variables are global variables and initialised in main function.
int i, j, k;
int my_rank = ((int)pArg);
int NUM_THREADS = sysconf(_SC_NPROCESSORS_ONLN); // Get number of threads from system

int row_start_point, row_end_point;
int col_start_point, col_end_point;

// for sqrt(), ensure math.h is included and -lm is used when compiling the code
int tileRows = (int)sqrt(NUM_THREADS); 
int tileCols = (int)sqrt(NUM_THREADS);
int tileRowPos = my_rank / tileCols;
int tileColPos = my_rank % tileCols;

row_start_point = tileRowPos * (rowC / tileRows);
row_end_point = row_start_point + (rowC / tileRows);
if(tileRowPos == tileRows - 1)  
    row_end_point += (rowC % tileRows); // Remainder tile rows

col_start_point = tileColPos * (colC / tileCols); 
col_end_point = col_start_point + (colC / tileCols);  
if(tileColPos == tileCols - 1) 
    col_end_point += (colC % tileCols); // Remainder tile columns
    
// Matrix multiplication
for(i = row_start_point; i < row_end_point; i++){
    for(j = col_start_point; j < col_end_point; j++){
        for(k = 0; k < commonPoint; k++){
            pMatrixC[(i*colC)+j] += (pMatrixA[(i*colA)+k] * pMatrixB[(k*colB)+j]);
        }
    }
}
return NULL;
content_copy
Use code with caution.

}

d) Other parallel partitioning methods (Fox/Canon, etc)

You are not required to consider advanced partitioning techniques such as Fox/Canon, but you may consider doing so.

II. Task 2

a) The lab specifications mention that only the root process can access the input matrix binary files. Therefore, the challenging part of Task 2 is distributing the input matrices from the root MPI process to other processes in the communication group. This is especially true when implementing a tile-based parallel partitioning method in MPI. In Task 1 above, the POSIX threads can directly access different regions of the input matrices as these matrices were created as heap arrays (shared memory). However, you are required to distribute only the required rows and columns of the input matrix data to the other MPI processes to perform the tile-based matrix multiplication computation. If you broadcast all input matrices A and B to all processes, the communication time will be very high, especially for large matrix multiplication, and this will reduce the overall speed (hence, the mark deduction).

b) Therefore, as a start, you can consider implementing a row-based partitioning method in Task 2 for MPI. It is still tricky to figure out how to distribute the different rows of the input matrices to the other processes. Nevertheless, this method is easier to implement than the tile-based approach. To clarify, this method will not give you the maximum marks for Task 2. If you implement a correct row-only partitioning method for Task 2 and assume you get everything else correct in Task 2 (code, report, Q&A, etc.), you can score up to 50 out of 60 marks.

c) Once you have implemented a correct version of a row partitioning method for Task 2, you have more flexibility to try out the more complex tile-based partitioning method in Task 2. Even if you can't get the tile-based method to work, you can fall back to your row-based partitioning, albeit you would not be eligible to score the maximum marks for this task.

III. Task 3

a) The main purpose of Task 3 is to investigate if a hybrid MPI-POSIX/OMP method would perform better than an MPI-only method. The hypothesis here is that if we have a cluster platform, we use MPI to distribute data from one compute node to another compute node in the cluster, and within each compute node, we use threads to parallelise the computation. This method reduces the number of MPI sends and receives and should improve overall speed-up. That said, using CAAS in Task 3 is not mandatory. You can still run the experiments for Task 3 on your local machine, albeit it could be difficult to obtain a clear picture of the performance of a Hybrid MPI-POSIX/OMP versus that of an MPI-only method on a local computer (unless you have a local computer with a large number of CPU cores). Hence, we encourage you to use CAAS where possible.

b) Task 3 also investigates parallelising the file read and write operations. This is the main reason why the sample input files are binary files. As far as I know, we cannot parallelise a file read and write if accessed as a text file. However, if the file is binary, we can open it in binary mode and use threads to read from or write into different sections of the file.

c) The important point about Task 3 is the partitioning method. As illustrated in Figure 4 below, the workload is partitioned into three MPI processes. Each MPI process creates three threads to sub-partition the workload. You can specify a fixed number of threads per MPI process. However, you should not fix the number of MPI processes in your design. The question here is whether we should use a row or tile approach for the threads within each MPI process. The lab specification did not include a requirement about the partitioning method for the threads within an MPI process. Hence, you can opt for either a row or tile-based partitioning when distributing the workload among the threads in each MPI process. But please remember to factor in the remaining cells in your workload distribution.

Figure 3: Sample Hybrid MPI-Threads partitioning method.

IV Concluding points

a) The lab 6 requirements are more complex than those of previous labs. Nevertheless, by completing this lab, students will better understand how different parallel computing designs and implementations can be used to solve a complex task.

b) The aforementioned explanation and sample code provided should help you complete Tasks 1, 2 and 3 of this lab. Please consider a strategic approach when completing the lab tasks. As aforementioned, you can start with a row-partitioning method for Task 2 to ensure that you have a working solution for this task. Although you would not score the maximum marks for Task 2 using the row-only partitioning method, you will still score good marks. Once you have implemented the row method, you can then try implementing a tile-based or advanced partitioning method. You are not required to use Fox/Canon in this lab. Nevertheless, you can consider implementing it based on the Week 11b lecture materials and recording if you are keen to explore more advanced partitioning methods for parallel matrix multiplication.

c) In Task 3, you can apply a row or tile-based workload distribution between the threads for each MPI process.

d) Please be honest when designing and implementing your code for Tasks 1 to 3. Do not falsify the results in your Tables. If you cannot obtain all of the results on time, you can submit what you have and still obtain marks. It is unethical to falsify your results and risks academic misconduct if the teaching team detects it.

The teaching team hopes that the aforementioned information is helpful and that you will complete the final lab activity of this unit with a positive experience.

Thank you.

Dear FIT3143 Students,

Students have been asking the teaching team what is the correct method to measure communication time in MPI. In fact, there has been some queries as to what is defined as communication time. Well, communication time is generally understood as the time taken to send and/or receive messages between MPI processes.

Some students may have a slightly different interpretation of communication time and that should be okay so long it is logical. If you are not sure if your communication measurement is logical, please do clarify with your lab instructor (or lecturer) before implementing it in Tasks 2 and 3 of Week 11 - Lab #6.

To measure the communication time, the common approach would be to put a timestamp (using clock_gettime()) right before and after the MPI_Send() function. This approach is acceptable but it may not be accurate as MPI_Send() does not block until all of the data have been received by the receiver.

The teaching team understands that a portion of students have labs on Monday and we do not intent to perturb you with this post on the eve day of a Monday lab session. If you are using the aforementioned technique or any other logical approach in measuring communication time, this should be okay.

Nevertheless, if you are you seeking an accurate way to measure communication time, please consider the following information.

The figure above illustrates a sequence diagram describing a method to measure the time taken for a message to be sent from the sender to the receiver (i.e., communication time). The root process gets the current timestamp (e.g., using clock_gettime()) and packs this timestamp along with the message that is intended to be sent to the other processes. The packed message is sent to all other processes. The other processes receives the packed message and gets a current timestamp immediately after receiving the message. Then, these processes unpacks the messages to extract the root's timestamp. By subtracting the current timestamp from the root's timestamp, we have the time taken for the message to travel from the root to the recipient process.

Implementing the above sequence diagram design into a code can be rather tricky, especially when packing messages. Therefore, the following code includes a sample implementation based on the aforementioned sequence diagram.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <time.h>
#include <mpi.h>
#include<unistd.h>

int main(int argc, char *argv[])
{
// Variables
char *dim;
int i = 0, j = 0, k = 0, p = 0, my_rank = 0;
int row = 0, col = 0;
int *pMatrix = NULL;
char matrixFileName[50];
FILE *pFile;

char *pPackedBuffer = NULL;
int packedBufferSize = 0;
int position = 0;

/* Clock information */
struct timespec startComm, endComm;
double time_taken;

MPI_Status status;
MPI_Init(NULL, NULL);
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &p);

if (argc < 2 || argc > 2) {
    printf("Invalid input argument\n");
    return 0;
}
if (argc == 2) {
    dim = argv[1];
}
// 1. Read Input matrix to heap array
if(my_rank == 0){    
    printf("Root process - Reading Matrix A - Start\n");
    sprintf(matrixFileName, "MA_%sx%s.bin", dim, dim);
    pFile = fopen(matrixFileName, "rb");
    if (pFile == NULL) {
        printf("Error: File %s doesn't exist.\n", matrixFileName);
        return 0;
    }
    fread(&row, sizeof(int), 1, pFile); 
    fread(&col, sizeof(int), 1, pFile); 

    pMatrix = (int*)malloc((row*col) * sizeof(int));
    for(i = 0; i < row; i++){
        fread(&pMatrix[i*col], sizeof(int), col, pFile);
    }
    fclose(pFile);

    printf("Root process - Reading Matrix A - Done\n");
}
// 2. Broadcast row and col to all processes
MPI_Bcast(&row, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&col, 1, MPI_INT, 0, MPI_COMM_WORLD);

// 3. Prepare pack buffer data
packedBufferSize = (sizeof(unsigned long long) * 2) + (row * col * sizeof(int)); // tv_sec + tv_nsec + matrix (int array)
pPackedBuffer = (char*)malloc(packedBufferSize);

// 4. Root packs the data (i.e., time and matrix)
if(my_rank == 0){
    // timestamp right before broadcast (or send).
    clock_gettime(CLOCK_MONOTONIC, &startComm);
    
    // Pack timestamp and matrix into a single packed buffer
    MPI_Pack(&startComm.tv_sec, 1, MPI_UINT64_T, pPackedBuffer, packedBufferSize, &position, MPI_COMM_WORLD);
    MPI_Pack(&startComm.tv_nsec, 1, MPI_UINT64_T, pPackedBuffer, packedBufferSize, &position, MPI_COMM_WORLD);
    MPI_Pack(pMatrix, (row*col), MPI_INT, pPackedBuffer, packedBufferSize, &position, MPI_COMM_WORLD);
}
// 5. Root sends the packed buffer which includes the startComm time and pMatrix to all other processes.

// Use either MPI Bcast or MPI Send & Receive
// If you use MPI Bcast, comment out the send and receive functions, and vice-versa.

//MPI_Bcast(pPackedBuffer, packedBufferSize, MPI_PACKED, 0, MPI_COMM_WORLD);

if(my_rank == 0){
    for(i = 1; i < p; i++){
        MPI_Send(pPackedBuffer, packedBufferSize, MPI_PACKED, i, 0, MPI_COMM_WORLD);
    }
}else{
    MPI_Recv(pPackedBuffer, packedBufferSize, MPI_PACKED, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}

// 6. Non root processes unpacks the buffer into startComm variable and pMatrix array.
if(my_rank != 0){
    // timestamp right after broadcast (or receive).
    clock_gettime(CLOCK_MONOTONIC, &endComm); 
    // Create heap memory for matrix.
    pMatrix = (int*)malloc((row*col) * sizeof(int));
    position = 0;
    // Unpack timestamp and matrix into startComm variable and array.
    MPI_Unpack(pPackedBuffer, packedBufferSize, &position, &startComm.tv_sec, 1, MPI_UINT64_T, MPI_COMM_WORLD);
    MPI_Unpack(pPackedBuffer, packedBufferSize, &position, &startComm.tv_nsec, 1, MPI_UINT64_T, MPI_COMM_WORLD);
    MPI_Unpack(pPackedBuffer, packedBufferSize, &position, pMatrix, (row*col), MPI_INT, MPI_COMM_WORLD);
    
    // Measure communication time, endComm (after broadcast) - startComm (before broacast)
    time_taken = (endComm.tv_sec - startComm.tv_sec) * 1e9; 
    time_taken = (time_taken + (endComm.tv_nsec - startComm.tv_nsec)) * 1e-9; 
    printf("Rank %d took %lf (s) to receive matrix from Root process\n", my_rank, time_taken);
    
    // Non root processes writes the received pMatrix A into a separate binary file.
    sprintf(matrixFileName, "Rank_%d_MA_%dx%d.bin", my_rank, row, col);
    pFile = fopen(matrixFileName, "wb"); 
    fwrite(&row, sizeof(int), 1, pFile); 
    fwrite(&col, sizeof(int), 1, pFile); 
    for(i = 0; i < row; i++){
        fwrite(&pMatrix[i*col], sizeof(int), col, pFile);
    }
    fclose(pFile);
}
// Clean up
MPI_Finalize();
free(pMatrix);
return 0;
content_copy
Use code with caution.

}

The code above can also be accessed here:

File
MPI_CommunicationTime.c
In the code above, the root process opens an input binary file, reads its content into a heap array and sends the array to all other MPI processes. The aim here is to measure the time by the root to send the array to each other MPI process. Hence, the code above follows the sequence diagram above, whereby the root's timestamp is packed together with the binary content and sent to other MPI processes. The receiving processes unpacks the message and subtracts the timestamp to obtain the communication time. We are using the clock_gettime() function to obtain the timestamp at point of usage.

The following screen shot depicts execution of the aforementioned code reading from a 2000x2000 binary file. Please make sure the binary file is in the same directory of your compiled program. Sample binary files can be accessed here.

In the screenshot above, the compiled program is executed using mpirun with 4 processes. As seen above, rank 1 took 0.0138 seconds to receive a 2000x2000 array from the root process. The communication time increases for ranks 2 and 3 given that the root process sequentially sends each array to the other processes. The overall communication time is sum of the aforementioned time, that is it took the the whole program about 0.065 seconds to send the binary content from the root to all other processes. You may be wandering if there is a way to automatically sum up the time rather than manually adding them. Well, you can modify the code above for the the non-root processes to send the communication time back to the root process to be summed and printed on screen (or logged into a file).

One important point to note here. The aforementioned code was compiled and executed on a local computer (using docker). If you apply the aforementioned approach on the CAAS cluster, you might observe a negative time result. This is because the when running the program across multiple nodes in a cluster, the system clocks in each node must be synchronized. The clock times in the CAAS nodes might not be synchronized. Nevertheless, it is worth a try if you are keen to explore further.

In addition, if you are using MPI Scatter or Gather, it's difficult to pack a message that is to be scattered and gathered. For MPI scatter and gather, you could probably try placing the timestamps directly before and after these functions.

The teaching hopes that the aforementioned explanation provides some helpful insights to accurately measure communication time between a send and receive function (or broadcast).

Thank you.

Here is the excersises:

Preamble
 In matrix multiplication, the product of an m × p matrix A with a p × n matrix B results in an m
 × nmatrix denoted as C is mathematically represented as:
 (Eq. 1)
 Figure 1- Illustration of matrix multiplication. Note that Eq. 1 and this figure iterate i and j
 from 1. When implementing the equation into the code, you can iterate i and j from 0.
 Mathematically, matrix multiplication is a binary operation that yields a resultant matrix based
 on two input matrices. The general definition of matrix multiplication is illustrated in Figure 1.
 Basically, given an n×m matrix A and an m×p matrix B, the product of the two matrices
 would produce an n×p matrix C. Each individual element in the resultant matrix C, denoted
 as C(i, j), is the dot product of the ith row of matrix A and the jth column of matrix B. This dot
 product operation is expressed mathematically, as in equation (1). Therefore, to define the
 product of matrix A and B, the number of columns in matrix A must be equivalent to the
 number of rows in matrix B.
 Code listing 1 describes a simple code to generate matrices. When executing this compiled
 code, the user will be prompted to enter a file name followed by the size of the matrix. The
 program will then generate the required matrix and populate its cells with random values
 before writing the matrix into the binary file. To view the content of the binary file, you can
 load the binary file into https://hexed.it/
 Code listing 1- C code that generates matrices and writes to a binary file. You can also
 access the code here.
 /////////////////////////////////////////////////////////////
 /////////////////////////
 // MatrixGenerator_bin.c
 //---------------------------------------------------------------------------------
//
 // Generates a N x M matrix with random cell values and
 writes into a binary file
 //
 //
 /////////////////////////////////////////////////////////////
 2
/////////////////////////
 #include <stdio.h>
 #include <stdlib.h>
 #include <memory.h>
 #include <time.h>
 #define MATRIX_CELL_MAXVAL 1000
 int main()
 {
 int row, col;
 int i,j;
 char matrixName[256] = {0};
 unsigned int randNum = 0;
 printf("Welcome to the random matrix file
 generator!\n\n");
 printf("Specify the matrix file name (e.g. MA.bin): ");
 scanf("%s", matrixName);
 printf("Specify the matrix row and col values (e.g. 10
 10): ");
 scanf("%d%d", &row, &col);
 srand((unsigned int)time(NULL));
 FILE *pFile = fopen(matrixName, "wb");
 fwrite(&row, sizeof(int), 1, pFile);
 fwrite(&col, sizeof(int), 1, pFile);
 for(i = 0; i < row; i++){
 for(j = 0; j < col; j++){
 randNum = 100 + ((unsigned int)rand() %
 MATRIX_CELL_MAXVAL);
 fwrite(&randNum, sizeof(unsigned int), 1,
 pFile);
 }
 }
 fclose(pFile);
 printf("Done!\n");
 return 0;
 }
 Code listing 2 describes a serial matrix multiplication algorithm. The code reads the
 content of the input binary files (e.g. MA.bin and MB.bin) into heap memory and
 computes the matrix multiplication. The resultant matrix is then written into a new
 binary file (e.g., MC.bin).
 3
Code listing 2- Serial C code for matrix multiplication. You can also access the code here.
 /////////////////////////////////////////////////////////////
 /////////////////////////
 // MatrixMul_1D_bin.c
 //---------------------------------------------------------------------------------
//
 // Multiplies two matrices and writes the resultant
 multiplication into a binary file.
 //
 //
 /////////////////////////////////////////////////////////////
 /////////////////////////
 #include <stdio.h>
 #include <stdlib.h>
 #include <memory.h>
 #include <time.h>
 int main()
 {
 // Variables
 int i = 0, j = 0, k = 0;
 /* Clock information */
 struct timespec start, end;
 double time_taken;
 clock_gettime(CLOCK_MONOTONIC, &start);
 // 1. Read Matrix A
 int rowA = 0, colA = 0;
 printf("Matrix Multiplication using 1-Dimension Arrays
Start\n\n");
 printf("Reading Matrix A- Start\n");
 FILE *pFileA = fopen("MA_1000x1000.bin", "rb");
 fread(&rowA, sizeof(int), 1, pFileA);
 fread(&colA, sizeof(int), 1, pFileA);
 int *pMatrixA = (int*)malloc((rowA*colA) * sizeof(int));
 for(i = 0; i < rowA; i++){
 fread(&pMatrixA[i*colA], sizeof(int), colA, pFileA);
 }
 fclose(pFileA);
 printf("Reading Matrix A- Done\n");
 // 2. Read Matrix B
 int rowB = 0, colB = 0;
 4
printf("Reading Matrix B- Start\n");
 FILE *pFileB = fopen("MB_1000x1000.bin", "rb");
 fread(&rowB, sizeof(int), 1, pFileB);
 fread(&colB, sizeof(int), 1, pFileB);
 int *pMatrixB = (int*)malloc((rowB*colB) * sizeof(int));
 for(i = 0; i < rowB; i++){
 fread(&pMatrixB[i*colB], sizeof(int), colB, pFileB);
 }
 fclose(pFileB);
 printf("Reading Matrix B- Done\n");
 // 3. Perform matrix multiplication
 printf("Matrix Multiplication- Start\n");
 int rowC = rowA, colC = colB;
 unsigned long long *pMatrixC = (unsigned long
 long*)calloc((rowC*colC), sizeof(unsigned long long));
 int commonPoint = colA;
 for(i = 0; i < rowC; i++){
 for(j = 0; j < colC; j++){
 for(k = 0; k < commonPoint; k++){
 pMatrixC[(i*colC)+j] +=
 (pMatrixA[(i*colA)+k] * pMatrixB[(k*colB)+j]);
 }
 }
 }
 printf("Matrix Multiplication- Done\n");
 // 4. Write resuls to a new file
 printf("Write Resultant Matrix C to File- Start\n");
 FILE *pFileC = fopen("MC.bin", "wb");
 fwrite(&rowC, sizeof(int), 1, pFileC);
 fwrite(&colC, sizeof(int), 1, pFileC);
 for(i = 0; i < rowC; i++){
 fwrite(&pMatrixC[i*colC], sizeof(unsigned long long),
 colC, pFileC); // use fwrite to write one row of columns to the
 file
 }
 fclose(pFileC);
 printf("Write Resultant Matrix C to File- Done\n");
 clock_gettime(CLOCK_MONOTONIC, &end);
 time_taken = (end.tv_sec- start.tv_sec) * 1e9;
 time_taken = (time_taken + (end.tv_nsec- start.tv_nsec)) *
 1e-9;
 printf("Overall time (Including read, multiplication and
 write)(s): %lf\n", time_taken); // ts
 5
 // Clean up
free(pMatrixA);
 free(pMatrixB);
 free(pMatrixC);
 printf("Matrix Multiplication using 1-Dimension Arrays
Done\n");
 return 0;
 }
 Task 1- Matrix Multiplication (Serial and Parallel with
 POSIX/OMP)
 Marks- 0
 Hurdles- Yes.
 Although this task carries no marks, you are required to complete it. If you skip this
 task, you will not receive any marks in this lab, even if you complete the other tasks.
 In this task, you will analyse the performance of serial matrix multiplication and implement a
 parallel partitioning algorithm using shared memory parallelism (i.e., POSIX or OMP).
 a) Compile and execute Code Listing 1. Generate a set of binary files containing
 matrices. Alternatively, please refer to the sample binary files here.
 b) Compile and execute Code Listing 2. Observe the time taken to complete the matrix
 multiplication for large matrices. You can use Table 1 as a template to populate your
 results. You may modify the size of the matrices in Table 1 to suit your local
 computing resources. You are encouraged to use the CAAS platform when testing for
 large matrix multiplications.
 c) Optional: Apply Bernstein’s condition to objectively verify that each cell has no
 dependencies for matrix multiplication.
 d) Calculate the theoretical speed up. You could use Amdahl’s law by assuming that the
 size of the problem is fixed (i.e., the size of the matrices used for the multiplication).
 Alternatively, you can use Gustafson's law, assuming the problem size scales with
 the number of processors. Hint: Refer to the lecture materials in Week 11.
 e) Parallelise the serial matrix multiplication C code using data parallelism with either
 POSIX or OMP threads.
 i)
 Implement a parallel partitioning algorithm to distribute the workload among
 the threads equally.
 ii)
 f)
 You could consider a straightforward row partitioning method [or a more
 complex tile partitioning (or submatrix) approach].
 Compile and execute the parallel code. Update the parallel time using POSIX/OMP in
 Table 1 and compute the actual speed up.
 g) Optional: Compare and analyse the actual speed up versus the theoretical speed
 up. Include any observations on the differences between the theoretical and actual
 speed-ups. You can replicate Table 1 to include results for increasing the number of
 threads and CPU cores. This would provide additional analysis on the performance
 of matrix multiplication for increasing numbers of threads/cores and matrix sizes.
 h) Write your observations above in your report.
 6
Table 1- Matrix multiplication compute time time for increasing matrix size
 (Serial & Parallel with POSIX/OMP). Note: You may reduce the size of the matrices to
 suit your local computing resources
 Number of CPU cores or logical processes: ___
 Number of threads used for POSIX/OMP: ___
 Matrix size
 Serial time, Ts (s)
 Parallel time, Tp
POSIX/OMP (s)
 500x500 1000x1000 2000x2000 3000x3000 4000x4000
 Speed Up (Ts/Tp)
 Task 2- Parallel Matrix Multiplication (MPI)
 Maximum marks- 60 marks.
 Hurdles- No.
 In this task, you will design and implement a parallel partitioning algorithm for matrix
 multiplication using Message Passing Interface (MPI).
 a) Parallelise the serial matrix multiplication C code using data parallelism with MPI. You
 should implement a tile-based or submatrix approach in the parallel partitioning
 design. Please refer to Figure 2 for a sample depiction of this method. If you opt for a
 simpler row-based partitioning approach, you will not obtain the maximum marks for
 this task. Please refer to Week 11’s lecture materials for row and tile-based
 partitioning methods.
 b) Only the root process can access the input matrix binary files (e.g.,
 MA_1000x1000.bin & MB_1000x1000.bin). The root process reads the content of the
 input binary files into its memory.
 c) Implement a parallel partitioning algorithm to distribute the workload among the MPI
 processes equally.
 i)
 ii)
 iii)
 The root process will distribute the input matrices to the other processes in
 the MPI communicator. Note that you should apply an efficient approach in
 distributing the input matrices among the MPI processes, i.e., the root
 process should only send the required rows and columns of the input
 matrices to the other MPI processes. If the root process broadcasts
 unnecessary input data (matrices/sub-matrices) to any other MPI processes,
 the method will be inefficient, and marks will be deducted.
 All processes (including the root process) perform the matrix multiplication
 based on the partitioning algorithm.
 The root process gathers the computed matrices from other processes and
 writes the results into a binary file (e.g., MC.bin). Only the root process writes
 the results to a binary file.
 d) Compile and execute the parallel code.
 i)
 Update the parallel time using MPI in Table 2 and compute the actual speed
 up.
 ii)
 Measure the time required to send and receive the messages between the
 root process and other processes and include it in Table 2 (i.e., MPI
 communication time).
 7
e) Compare and analyse the actual speed up versus the theoretical speed up. Include
 any observations on the differences between the theoretical and actual speed-ups
 and the impact of communication time on the speed-up.
 Optional: You can replicate Table 2 to include results for increasing the number of
 MPI processes. This would provide additional analysis on the performance of matrix
 multiplication for increasing numbers of processes and matrix sizes.
 f)
 Write your observations above in your report.
 g) Task 2 marks distribution
 i)
 Parts (a) to (c): Row-based partitioning method, maximum 20 marks.
 Tile-based partitioning method, maximum 30 marks.
 ii)
 iii)
 Parts (d) & (e): 10 marks
 Q&A(interview): 20 marks
 a) Simpler tile-based (or submatrix) partitioning for parallel matrix multiplication (i.e., one vertical
 line to split the processes into its submatrices)
 b) Amorecomplex tile-based (or submatrix) partitioning for parallel matrix multiplication (i.e.,
 multiple vertical lines to split the processes into its submatrices)
 Figure 2- Sample tile-based (or submatrix) partitioning for parallel matrix multiplication. You may implement
 either (a) or (b) in Task 2.
 Table 2- Matrix multiplication compute time time for increasing matrix size
 (Serial & Parallel with MPI). Note: You may reduce the size of the matrices to suit your local
 computing resources
 Number of nodes (Specify 1 if only using your local computer): ___
 Number of CPU cores or logical processes per node: ___
 Number of MPI processes: ___
 Matrix size
 500x500 1000x1000 2000x2000 3000x3000 4000x4000
 Serial time, Ts (s)
 Parallel time, Tp
MPI (s)
 8
MPI
 communication
 time (s)
 Speed Up (Ts/Tp)
 Task 3- Parallel Matrix Multiplication (Hybrid MPI
POSIX/OMP)
 Maximum marks- 40 marks.
 Hurdles- No.
 In this task, you will design and implement a parallel partitioning algorithm for matrix
 multiplication using a hybrid MPI and POSIX/OMP approach.
 a) Modify the parallel code from Task 2 such that:
 i)
 The root process uses POSIX/OMP threads to read each input matrix binary
 file into memory. You are required to investigate/research parallel file reading
 with binary files in C.
 ii)
 iii)
 Each MPI process will use POSIX/OMP threads to compute the matrix
 multiplication based on the partitioned method. In this context, you will use
 fewer MPI processes with one MPI process running threads to compute the
 parallel matrix multiplication. For instance, in task 2 above, if you have 4 CPU
 cores (or logical processes), you will execute mpirun with 4 processes. In task
 3, if you have the same 4 CPU cores, you can execute mpirun with 2
 processes, with each MPI process executing two POSIX/OMP threads to
 compute the parallel matrix multiplication. You can specify a fixed number of
 threads per MPI process. However, you should not fix the number of MPI
 processes in your design. Please refer to Figure 3 for a sample depiction of
 this method.
 The root process uses POSIX/OMP threads to write the matrix multiplication
 result into the binary file (i.e., parallel file write).
 b) Compile and execute the parallel code.
 i)
 Update the parallel time using Hybrid MPI-POSIX/OMP in Table 3 and
 compute the actual speed up.
 ii)
 Measure the time required to send and receive the messages between the
 root process and other processes and include it in Table 3 (i.e., MPI
 communication time).
 c) Compare and analyse the actual speed up versus the theoretical speed up. Include
 any observations on the differences between the theoretical and actual speed-ups
 and the impact of communication time on the speed-up. Analyse if the
 communication time in Table 3 is any better than the communication time in Table 2.
 Provide some reasoning here.
 Optional: You can replicate Table 3 to include results for increasing the number of
 MPI processes and threads. This would provide additional analysis of the
 performance of matrix multiplication for increasing numbers of processes, threads
 and matrix sizes. You may need to use the CAAS platform when running with large
 numbers of MPI processes and/or threads.
 d) Write your observations in (a) to (c) in your report.
 e) Task 3 marks distribution
 9
i)
 ii)
 iii)
 Part (a): 10 marks
 Parts (b) and (c): 10 marks
 Q&A(interview): 20 marks
 Figure 3- Sample Hybrid MPI-Threads partitioning method. In this illustration, the workload is partitioned into
 two MPI processes. Each MPI process creates two threads to sub-partition the workload. To reiterate,
 you can specify a fixed number of threads per MPI process. However, you should not fix the number
 of MPI processes in your design.
 Table 3- Matrix multiplication compute time time for increasing matrix size
 (Serial & Hybrid MPI-POSIX/OMP). Note: You may reduce the size of the matrices to suit your
 local computing resources
 Number of nodes (Specify 1 if only using your local computer): ___
 Number of CPU cores or logical processes per node: ___
 Number of MPI processes: ___
 Number of threads per MPI process: ___
 Matrix size
 500x500
 1000x1000 2000x2000 3000x3000 4000x4000
 Serial time, Ts (s)
 Parallel time, Tp
Hybrid (s)
 MPI
 communication
 time (s)
 Speed Up (Ts/Tp)
 What to submit
 a) Task 1 (0%, Hurdles requirement)
 i)
 Parallel POSIX/OMP matrix multiplication code (task1.c).
 ii)
 A report containing Table 1.
 b) Task 2 (60%, No hurdles)
 i)
 Parallel MPI matrix multiplication code (task2.c).
 ii)
 iii)
 A report containing Table 2 and an analysis of the results.
 A zipped file containing one sample of the input and output binary files
 (task2.zip).
 c) Task 3 (40%, No hurdles)
 i)
 Hybrid MPI-POSIX/OMP matrix multiplication code (task3.c).
 ii)
 A report containing Table 3 and an analysis of the results.
 10
iii)
 A zipped file containing one sample of the input and output binary files
 (task3.zip).
 Note: You can have one report containing the tabulated results and analysis for Tasks 1 to 3
 (Report.docx or Report.pdf).
 Important points
 a) You can modify the serial C code to optimise it before parallelising it. This includes
 transposing matrix B before multiplying it with matrix A.
 b) You can modify Tables 1 to 3 above to include additional columns or rows to aid your
 analysis and explanation. As mentioned above, you can also reduce the size of the
 input matrices to suit your local computing resources. You can compile the
 MatrixGenerator_bin.c file and execute it to generate smaller input
 matrices. Please ensure that the input matrices' correct dimensions (i.e., rows and
 columns) are used when performing the matrix multiplication.
 c) Usage of the CAAS platform is not mandatory for this lab. Nevertheless, running the
 experiments on the CAAS platform would be beneficial when testing with large
 matrices.
 d) You should use the same computer settings for serial and parallel versions of your
 experiments. Please refrain from running the serial code on one platform and the
 parallel code on another platform. It could lead to inconsistent results.
 e) If you refer to generative AI to aid in this lab, please ensure that you declare it in your
 report

Marking Rubric for Week 11 (Lab #6)
 FIT3143 Parallel Computing © Monash University 2024
 Task 1- Criteria to meet the hurdles
 a) Parallel POSIX/OMP matrix multiplication code.
 b) Areport containing Table 1 from the Lab specifications.
 Task 2 (60%)
 a) Coding tasks (including correctness and program execution) (30%)
 i)
 Partitioning & computational method (Max: 10%)
 1) Incorrect partitioning method, limited or no parallelism observed
 (0%).
 2) Rowor Column only partitioning or an equivalent straightforward
 / less efficient method (5%).
 3) Correct Tile-based (submatrix) partitioning (10%).
 ii)
 iii)
 Communication method- Distribution of data (Max: 10%)
 1) Incorrect communication method between root process and
 other processes or no communication between processes. All
 processes have default access to the input binary files, which
 does not comply with the lab specifications (0%).
 2) Root process broadcasts input matrices to all processes, which
 includes unnecessary data (3%).
 3) Root process sends required data to all processes, but based on
 a Rowor Column only partitioning or an equivalent trivial / less
 efficient method (5%).
 4) The root process sends the required data to all processes based
 on the Tile-based (submatrix) partitioning (10%).
 Communication method- Gathering of results & writing to file
 (Max: 10%)
 1) Incorrect communication between processes or no
 communication between processes. Results are written by each
 MPI process to local files, which does not comply with the lab
 specifications (0%)
 2) The root process gathers resultant blocks of multiplication
 results from other processes and writes them to a file. However,
 the gathered results included unnecessary/wrong information
 (5%)
 1
3) The root process correctly gathers relevant resultant blocks of
 multiplication results from other processes and writes them to a
 file (10%).
 b) Report (10%)
 i)
 ii)
 Tabulation of results (Max: 5%)
 1) No results or incorrect results (0%)
 2) Incomplete or insufficient results tabulated (2%)
 3) Complete results tabulated (5%)
 Analysis and observations (Max: 5%):
 1) No analysis or observations includes, or information provided is
 not correct (0%)
 2) Limited/poor analysis and observation in comparing the
 performance of the parallel MPI method against the serial or
 POSIX/OMP version from Task 1 (2%).
 3) Complete analysis and observation based on the tabulated
 results. Sufficient comparisons are made between the parallel
 MPI method and the serial or POSIX/OMP version from Task 1
 (5%).
 c) Q&Asession (20%)
 i)
 ii)
 iii)
 iv)
 v)
 Minimal to no relevance or correctness (0-6%)
 Limited relevance or correctness (7-9%)
 Partial correctness with significant gaps or errors (10-14%)
 Deep understanding with practical application on both the topics and
 the required tasks, but with minor omissions or errors (15-17%)
 Deep understanding with practical application of both the topics and
 the required tasks (18-20%)
 Task 3 (40%)
 a) Coding tasks (including correctness and program execution) (10%)
 i)
 Parallel read & write (Max: 5%)
 1) Incorrect code or limited parallelism observed (0%).
 2) Less than ideal/suboptimal parallel performance or using one
 thread to read one single input file (2%).
 3) Parallelism has successfully applied in both file reading (multiple
 threads reading from a file) and writing (multiple threads writing
 to a file) operations with good/optimal performance (5%).
 ii)
 Hybrid MPI-thread (Max: 5%)
 1) Incorrect partitioning method, limited or no parallelism observed
 (0%).
 2) Hardcoding or fixing both the number of MPI processes and the
 number of threads per process (2%).
 2
3) Correct hybrid partitioning method with a dynamic number of
 MPI processes and fixed / dynamic number of threads per
 process (5%)
 b) Report (10%)
 i)
 ii)
 Tabulation of results (Max: 5%)
 1) No results or incorrect results (0%)
 2) Incomplete or insufficient results tabulated (2%)
 3) Complete results tabulated (5%)
 Analysis and observations (Max: 5%):
 1) No analysis or observations includes, or information provided is
 not correct (0%)
 2) Limited/poor analysis and observation were made when
 comparing the performance of the hybrid MPI-Thread method
 against the MPI-only parallel method from Task 2, or against the
 thread/OpenMP parallel method from Task 1 (2%).
 3) Complete analysis and observation based on the tabulated
 results. Sufficient comparisons are made between the hybrid
 MPI-Thread method and the MPI-only & thread-only parallel
 method from Task 2 & Task 1 (5%).
 c) Q&Asession (20%)
 i)
 ii)
 iii)
 iv)
 v)
 Minimal to no relevance or correctness (0-6%)
 Limited relevance or correctness (7-9%)
 Partial correctness with significant gaps or errors (10-14%)
 Deep understanding with practical application on both the topics and
 the required tasks, but with minor omissions or errors (15-17%)
 Deep understanding with practical application of both the topics and
 the required tasks (18-20%