Datasharing Problem

General OpenMP discussion

Datasharing Problem

Postby yazan » Mon Jan 06, 2014 12:18 pm

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

Postby MarkB » Tue Jan 07, 2014 6:47 am

Could you post the sequential code and include the initialisation and adjustment of the result array please? Is result used in HW()?
MarkB
 
Posts: 481
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Datasharing Problem

Postby yazan » Tue Jan 07, 2014 8:06 am

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

Postby MarkB » Tue Jan 07, 2014 8:37 am

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: 481
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Datasharing Problem

Postby yazan » Tue Jan 07, 2014 10:03 am

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
threads.png (8.5 KiB) Viewed 3080 times
yazan
 
Posts: 7
Joined: Mon Jan 06, 2014 11:57 am

Re: Datasharing Problem

Postby MarkB » Tue Jan 07, 2014 10:31 am

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: 481
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Datasharing Problem

Postby yazan » Thu Jan 09, 2014 5:59 am

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 givenResult

myResult = 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 myResult
for(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 = 1
for(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
enumerate indizies.png (10.31 KiB) Viewed 3071 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

Postby MarkB » Thu Jan 09, 2014 9:30 am

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 givenResult

Result = 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 Result
for(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 column
myResult[x] = Result[x] ^ matrix[i][x];
if(myResult) == givenResult){
exit(EXIT_SUCCESS);
}
}


y = 1
for(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: 481
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Re: Datasharing Problem

Postby yazan » Tue Jan 21, 2014 2:08 pm

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

Postby MarkB » Wed Jan 22, 2014 3:19 am

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: 481
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: Yahoo [Bot] and 12 guests