How can I convert a C code program into OpenMP using tasks and dependencies

Question

I have code written in C and I need to convert it into openMP using tasks and dependencies.

Below is my code:

#include <omp.h>
#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[])
{
    //declare two dimensional array A and define its values
    int arrA[3][3] = { { 1, 1,0 }, { 1, 1,0 },{ 1, 1,0 } }; 
    //declare two dimensional array B and give properties of its dimensions
    int arrB[3][3];
    //declare variables to be used
    int diag, i, j,top,left;

    printf("Array A:\n");
    //use for loop to make two dimensional array
    for ( i = 0; i < 3; i++) { 
        for ( j = 0; j < 3; j++) { 
            //display values in two dimensional array A
            printf("%d\t",arrA[i][j]); 
        } 

        printf("\n");  
    } 

    printf("Array B:\n");
    for( i=0;i<3;i++){
        for( j=0;j<3;j++) {
            diag = 0; top=0; left=0;
            if(i-1>=0 && j-1>=0) {
                diag = arrB[i-1][j-1];
            }
            if(i-1>=0) {
                top = arrB[i-1][j];
            }
            if(j-1>=0) {
                left = arrB[i][j-1];
            }
            #pragma omp task private(i, j, top,left) shared(arrA,arrB)\
            depend ( inout: arrA[i][j], arrA[top][left] ) \
           depend ( inout: arrB[i][j] )
            arrB[i][j] = diag + arrA[i][j] + (top-diag) + (left-diag);
        }
    }
    //use for loop to make two dimensional array
    for(i=0;i<3;i++) {
        for(j=0;j<3;j++) {
            //display values in two dimensional array A
            printf("%d\t",arrB[i][j]);
        }
        printf("\n");
    }
}

I am new to parallel programming and C language, so I am not sure how to do this. The problem I am having is to code this having one task to compute each entry of array B with appropriate dependencies to ensure they execute in the correct order.

What I am trying to accomplish is having a two dimensional array (Array A) which has the following values :

1 1 0
1 1 0
1 1 0

Create another two dimensional array B to look like this:

1 2 2
2 4 4
3 6 6

with openMP tasks and dependencies.

Answer 1

You should first use the depend(in: ...) and depend(out: ...) to specify the input and output dependencies of the task. Additionally, you must include the 3 conditionals into the task body as they read the cells of arrB written by the tasks. Finally, you should add a #pragma omp parallel section and let only one thread create the tasks with either #pragma omp master of #pragma omp single.

Here is a solution:

    printf("Array B:\n");
    #pragma omp parallel
    #pragma omp master
    for( i=0;i<3;i++){
        for( j=0;j<3;j++) {
            #pragma omp task \
                    firstprivate(i, j) \
                    private(diag, top, left) \
                    shared(arrA, arrB) \
                    depend(in: arrB[i-1][j], arrB[i][j-1]) \
                    depend(out: arrB[i][j])
            {
                diag = 0; top=0; left=0;
                if(i-1>=0 && j-1>=0) {
                    diag = arrB[i-1][j-1];
                }
                if(i-1>=0) {
                    top = arrB[i-1][j];
                }
                if(j-1>=0) {
                    left = arrB[i][j-1];
                }
                arrB[i][j] = diag + arrA[i][j] + (top-diag) + (left-diag);
            }
        }
    }
    #pragma omp taskwait

Please note that the dependency arrB[i-1][j-1] is not specified as it is already included in the other indirectly. arrA[i][j] is not needed either since there are no other task writing into it. Both are optimizations.

While this solution is correct, it will probably be run the code in sequential. The problem comes from the dependencies: OpenMP does not provide a simple way to add conditions for the first line and the first column. One way to overcome that is to split the code in 3 parts computing each possible case (cumbersome as it duplicate the code). Another way is to create the task in a different order so that false dependencies does not occur (eg. diagonal walk). Yet another way is to build yourself the dependencies with pointers (requires a good understanding of OpenMP). None of the solution is really good.

PS: I guess that you want to play with OpenMP tasks and you do not expect any speed-up related to parallelizing this code as the computation is not enough intensive so that can be useful).