## Datasharing Problem

General OpenMP discussion

### Datasharing Problem

hi all

the Problem is: in the master Block the Arrays index and result will be adjusted. we want that the Threads work with the new Values in the next iteration.
we have tried the directives Threadpriavte and firstprivate but no one have worked for us.
Any suggestions please.
Last edited by yazan on Mon Apr 07, 2014 7:06 am, edited 1 time in total.
yazan

Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

### Re: Datasharing Problem

Could you post the sequential code and include the initialisation and adjustment of the result array please? Is result used in HW()?
MarkB

Posts: 543
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Datasharing Problem

here is the Code:
you will see some changes, they ware made to make it clearer to understand, the functionality is the same as before.

Code: Select all
`    n = 100;   s = 7;   t = 4      int *index,y;    uint64 **matrix,*result;    matrix = new WORD *[n+1];    for(int i = 0; i < n+1; i++)        matrix[i] = new uint64 [1];   result = new uint64 [1];    index = new int [s-t];    for(int j=0; j<s-t; j++)        index[j] = n-k+j;      #pragma omp prallel firstprivate(result) shared(matrix, index){   while(index[0] <= n-(s-t)){        #pragma omp for         for(int i=index[s-t-1]; i<n; i++){            result[x] ^= matrix[i][x];            if(HammingWeight(result) == t){                exit(EXIT_SUCCESS);            }            result[x] ^= matrix[i][x];        }      #pragma omp barrier      #pragma omp master      {         y = 1         for(int i=s-t-2; i>=0; i--){            result[x] ^= matrix[index[i]][x];            y++;            if(index[i] != n-y)            break;         }         index[s-t-y]++;         result[x] ^= matrix[index[s-t-y]][x];         for(int i=s-t-y+1,offset=1; i<s-t; i++,offset++){            index[i]=index[s-t-y]+offset;            if(i!= s-t-1)               result[x] ^= matrix[index[i]][x];    }}   `

yes it used.
Note: localresult and result can be seen as the same. in the first post i have forgotten to modify the code. so it should be result where localresult is used.
yazan

Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

### Re: Datasharing Problem

I don't see how you can parallelise the i loop as the contents of result depend on the values from the previous iteration. Am I missing something?
MarkB

Posts: 543
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Datasharing Problem

as Diagram better than words i have made this Diagram:

we have this situation:
is in the attached file
my question is do we have a possibility to make the changes in master available to the threads in the next Iteration?

Note: result ist Firstprivate, index is Shared.
Attachments
threads.png (8.5 KiB) Viewed 3957 times
yazan

Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

### Re: Datasharing Problem

For index[], making it shared is fine. However, I think you have a synchronisation bug: the barrier should be after the master region, not before it, to prevent the non-master threads from entering the next i loop before the master region is complete. (There is an implicit barrier at the end of the for construct, so you don't need one there).

I still don't quite understand the dependencies on result[]. If you want each thread to have a private copy, initialised with the value just written by the master region, then you should declare it shared on the parallel construct and firstprivate on the for construct. Also, if you expect the master region to see the values written in the logically last iteration of the i loop, then you should declare it lastprivate (as well as firstprivate) on the for construct.
MarkB

Posts: 543
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Datasharing Problem

Thank you for your response, which has helped us a loot, but we still have synchronization problem. randomly the Algorithm don't find the solution.
so I'll explain the function that we would like to run in parallel, maybe could you or anyone else help us:

1- We have a (32xn) or (64xn) matrix, depends on the system the program run on, consists only of binary numbers (0/1). We have stored each column in an integer, this means we treat the bits in the Integer as columns.
2- somebody has added (==did xor) together s columns. We don't know which? But we get the result.
3- we should search and find this S-columns with the function, which we have posted.
4- we have the variable matrix, contents the Matrix. And givenResult, contents the s-Columns result.

<important>
- we need to map all possible combinations and compare each combination with the given result.
our algorithm runs sequential 100% correctly

******* explain the idee here*******
our algorithm is as follows
(e.g. n = 50 and s = 7)
first we calculate the first s-1 columns (this part is used by all threads)
• 1- we add the next column to the result and check if the result is what we need
if yes then we finished. if no we remove it and try the next column.
as shown in the figure we xor the first 6 cols (the black ones) in the parallel region (the blue one) we try one after another the cols
• 2. if we tried all the n columns we try another set of columns.
this set is calculated in the master Block.
in the master block we du two things:
• 1. calculate the new set of columns i.e adjust the index[].
the next iteration should be (1-5 black and 7 blue)
• 2. calculate the new result according the new index[].
the new result is the xor from 1-5 and 7 cols
with the next iteration the threads should work with the new index and result arrays.
here is again:

Code: Select all
`int *index,y;    uint64 *myResult;//another function read and stored the matrix and given result in the Varibles matrix and givenResultmyResult = new uint64 [1];myResult = 0;    index = new int [s];    for(int j=0; j<s; j++)        index[j] = 0;//do XOR the first s-1 columns and stor it in myResultfor(int i=0; i<s-1; i++)for(int x=0; x<1; x++) myResult[i] ^= matrix[i][x]#pragma omp prallel shared(matrix, index, myResult){while(index[0] <= n-s){        #pragma omp for firstprivate(myResult,index)         for(int i=index[s-1]; i<n; i++){//add the next column            myResult[x] ^= matrix[i][x];            if(myResult) == givenResult){                exit(EXIT_SUCCESS);            }//delete the last added column            myResult[x] ^= matrix[i][x];        }#pragma omp master{y = 1for(int i=s-2; i>=0; i--){myResult[x] ^= matrix[index[i]][x];y++;if(index[i] != n-y)break;}index[s-y]++;myResult[x] ^= matrix[index[s-y]][x];for(int i=s-y+1,offset=1; i<s; i++,offset++){index[i]=index[s-y]+offset;if(i!= s-1)myResult[x] ^= matrix[index[i]][x];}//end master#pragma omp barrier}//end while}//end parallel region`
Attachments
enumerate indizies.png (10.31 KiB) Viewed 3948 times
Last edited by yazan on Wed Jan 22, 2014 6:12 pm, edited 1 time in total.
yazan

Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

### Re: Datasharing Problem

I don't see anything obviously wrong with your code, though it's a bit hard to tell with all the syntax errors!
Does the code run correctly if you compile without OpenMP? Does it run correctly if you compile with OpenMP and use 1 thread?

You could try a simpler approach first, like this, which may be easier to get working:

Code: Select all
`int *index,y;uint64 *myResult, Result;//another function read and stored the matrix and given result in the Varibles matrix and givenResultResult = new uint64 [1];Result = 0;myResult = new uint64 [1];index = new int [s];for(int j=0; j<s; j++)index[j] = 0;//do XOR the first s-1 columns and stor it in Resultfor(int i=0; i<s-1; i++)for(int x=0; x<1; x++)Result[i] ^= matrix[i][x];while(index[0] <= n-s){#pragma omp parallel for private(myResult)for(int i=index[s-1]; i<n; i++){//add the next columnmyResult[x] = Result[x] ^ matrix[i][x];if(myResult) == givenResult){exit(EXIT_SUCCESS);}}y = 1for(int i=s-2; i>=0; i--){myResult[x] ^= matrix[index[i]][x];y++;if(index[i] != n-y)break;}index[s-y]++;myResult[x] ^= matrix[index[s-y]][x];for(int i=s-y+1,offset=1; i<s; i++,offset++){index[i]=index[s-y]+offset;if(i!= s-1)myResult[x] ^= matrix[index[i]][x];}//end while`
MarkB

Posts: 543
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: Datasharing Problem

Hi MarkB,

we still trying to run our Function with openMP, but unsuccessfully
To your question
Does the code run correctly if you compile without OpenMP?
yes, our Code run correctly without openMP and with single threaded openMP.

in multi threaded openMP it delivers the solution in some cases.

we tried your Idee only with "#pragma omp parallel for private(myresult)" but unfortunately unsuccessfully
thiswhy we think, it is a synchronization problem. do you have any suggestions, how to improve the synchronization

with best regards
yazan
yazan

Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

### Re: Datasharing Problem

Hi Yazan,

Can you post the latest version of your code, please? (The real code, not just a sketch!)

One possible source of error is unintentional sharing of variables inside any routines called from the parallel region (e.g. statics, globals).

Mark.
MarkB

Posts: 543
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Next

Return to Using OpenMP

### Who is online

Users browsing this forum: Google [Bot] and 5 guests