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{}
?
The
private(stop)
tells omp to give each thread a unique instance ofstop
, rather than sharing a communal value.See https://msdn.microsoft.com/en-us/library/c3dabskb.aspx
Remove that or explicitly specify it as shared.