Convert do/while into parallel do/while loop

351 views Asked by At

I'm having trouble converting a do/while{} into OpenMP. I'm following Example: While Loop from Cornell's Virtual Workshop.

Here is the original do/while{}. The variables r, re and modn are just Crypto++ classes. r and re are Integers, while modn is a ModularArithmetic. Randomize creates an integer in the specified range.

do {
    r.Randomize(rng, Integer::One(), m_n - Integer::One(), Integer::ANY);
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));

The parallelizable part is the two Jacobi tests after the random number is generated. Jacobi is cheaper (O(m·log(n))) than modular inversion (O(n^2)). Also, Jacobi fails 75% of the time, so I should perform the Jacobi tests before spending cycles on the modular inversion.

Here is what I have translated it to. EDIT: The outer #pragma omp parallel private(stop) { ... } was removed. Please check history if kfsone's answer does not make sense.

bool stop = false;
while(!stop)
{
    r.Randomize(rng, Integer::One(), m_n - Integer::One());        

    int jp, jq;
    #pragma omp parallel sections
    {
        #pragma omp section
            jp = Jacobi(r % m_p, m_p);
        #pragma omp section
            jq = Jacobi(r % m_q, m_q);
    }

    if ((jp != -1) && (jq != -1))
    {
        rInv = modn.MultiplicativeInverse(r);

        if(rInv.NotZero()) {
            stop = true;
        }
    }
}

The self tests succeed with the non-OMP version, but fail with the OMP version, so I know something is wrong.

What am I doing wrong in the OMP version of the do/while{}?

1

There are 1 answers

3
kfsone On BEST ANSWER

The private(stop) tells omp to give each thread a unique instance of stop, rather than sharing a communal value.

See https://msdn.microsoft.com/en-us/library/c3dabskb.aspx

Remove that or explicitly specify it as shared.