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