Parallel programming

These function are only available if PARI was configured using Configure --mt = .... Two multithread interfaces are supported:

* POSIX threads

* Message passing interface (MPI)

As a rule, POSIX threads are well-suited for single systems, while MPI is used by most clusters. However the parallel GP interface does not depend on the chosen multithread interface: a properly written GP program will work identically with both.


parapply(f, x)

Parallel evaluation of f on the elements of x. The function f must not access global variables or variables declared with local(), and must be free of side effects.

  parapply(factor,[2^256 + 1, 2^193 - 1])

factors 2256 + 1 and 2193 - 1 in parallel.

  {
    my(E = ellinit([1,3]), V = vector(12,i,randomprime(2^200)));
    parapply(p->ellcard(E,p), V)
  }

computes the order of E(𝔽p) for 12 random primes of 200 bits.

The library syntax is GEN parapply(GEN f, GEN x).


pareval(x)

Parallel evaluation of the elements of x, where x is a vector of closures. The closures must be of arity 0, must not access global variables or variables declared with local and must be free of side effects.

Here is an artificial example explaining the MOV attack on the elliptic discrete log problem (by reducing it to a standard discrete log over a finite field):

  {
    my(q = 2^30 + 3, m = 40 * q; p = 1 + m^2); \\ p, q are primes
    my(E = ellinit([0,0,0,1,0] * Mod(1,p)));
    my([P, Q] = ellgenerators(E));
    \\ E(Fp) ~ Z/m P + Z/m Q and the order of the
    \\ Weil pairing <P,Q> in (Z/p)* is m
    my(F = [m,factor(m)], e = random(m), R, wR, wQ);
    R = ellpow(E, Q, e);
    wR = ellweilpairing(E,P,R,m);
    wQ = ellweilpairing(E,P,Q,m); \\ wR = wQ^e
    pareval([()->znlog(wR,wQ,F), ()->elllog(E,R,Q), ()->e])
  }

Note the use of my to pass "arguments" to the functions we need to evaluate while satisfying the listed requirements: closures of arity 0 and no global variables (another possibility would be to use export). As a result, the final three statements satisfy all the listed requirements and are run in parallel. (Which is silly for this computation but illustrates the use of pareval.) The function parfor is more powerful but harder to use.

The library syntax is GEN pareval(GEN x).


parfor(i = a, {b}, expr1, {r}, {expr2})

Evaluates in parallel the expression expr1 in the formal argument i running from a to b. If b is set to +oo, the loop runs indefinitely. If r and expr2 are present, the expression expr2 in the formal variables r and i is evaluated with r running through all the different results obtained for expr1 and i takes the corresponding argument.

The computations of expr1 are started in increasing order of i; otherwise said, the computation for i = c is started after those for i = 1,..., c-1 have been started, but before the computation for i = c+1 is started. Notice that the order of completion, that is, the order in which the different r become available, may be different; expr2 is evaluated sequentially on each r as it appears.

The following example computes the sum of the squares of the integers from 1 to 10 by computing the squares in parallel and is equivalent to parsum (i = 1, 10, i^2):

  ? s=0;
  ? parfor (i=1, 10, i^2, r, s=s+r)
  ? s
  %3 = 385

More precisely, apart from a potentially different order of evaluation due to the parallelism, the line containing parfor is equivalent to

  ? my (r); for (i=1, 10, r=i^2; s=s+r)

The sequentiality of the evaluation of expr2 ensures that the variable s is not modified concurrently by two different additions, although the order in which the terms are added is nondeterministic.

It is allowed for expr2 to exit the loop using break/next/return. If that happens for i = c, then the evaluation of expr1 and expr2 is continued for all values i < c, and the return value is the one obtained for the smallest i causing an interruption in expr2 (it may be undefined if this is a break/next). In that case, using side-effects in expr2 may lead to undefined behavior, as the exact number of values of i for which it is executed is nondeterministic. The following example computes nextprime(1000) in parallel:

  ? parfor (i=1000, , isprime (i), r, if (r, return (i)))
  %1 = 1009


parforeach(V, x, expr1, {r}, {expr2})

Evaluates in parallel the expression expr1 in the formal argument x, where x runs through all components of V. If r and expr2 are present, evaluate sequentially the expression expr2, in which the formal variables x and r are replaced by the successive arguments and corresponding values. The sequential evaluation ordering is not specified:

  ? parforeach([50..100], x,isprime(x), r, if(r,print(x)))
  53
  67
  71
  79
  83
  89
  97
  73
  59
  61


parforprime(p = a, {b}, expr1, {r}, {expr2})

Behaves exactly as parfor, but loops only over prime values p. Precisely, the functions evaluates in parallel the expression expr1 in the formal argument p running through the primes from a to b. If b is set to +oo, the loop runs indefinitely. If r and expr2 are present, the expression expr2 in the formal variables r and p is evaluated with r running through all the different results obtained for expr1 and p takes the corresponding argument.

It is allowed fo expr2 to exit the loop using break/next/return; see the remarks in the documentation of parfor for details.


parforprimestep(p = a, {b}, q, expr1, {r}, {expr2})

Behaves exactly as parfor, but loops only over prime values p in an arithmetic progression Precisely, the functions evaluates in parallel the expression expr1 in the formal argument p running through the primes from a to b in an arithmetic progression of the form a + k q. (p = a (mod q)) or an intmod Mod(c,N). If b is set to +oo, the loop runs indefinitely. If r and expr2 are present, the expression expr2 in the formal variables r and p is evaluated with r running through all the different results obtained for expr1 and p takes the corresponding argument.

It is allowed fo expr2 to exit the loop using break/next/return; see the remarks in the documentation of parfor for details.


parforvec(X = v, expr1, {j}, {expr2}, {flag})

Evaluates the sequence expr2 (dependent on X and j) for X as generated by forvec, in random order, computed in parallel. Substitute for j the value of expr1 (dependent on X).

It is allowed fo expr2 to exit the loop using break/next/return, however in that case, expr2 will still be evaluated for all remaining value of p less than the current one, unless a subsequent break/next/return happens.


parselect(f, A, {flag = 0})

Selects elements of A according to the selection function f, done in parallel. If flag is 1, return the indices of those elements (indirect selection) The function f must not access global variables or variables declared with local(), and must be free of side effects.

The library syntax is GEN parselect(GEN f, GEN A, long flag).


parsum(i = a, b, expr)

Sum of expression expr, the formal parameter going from a to b, evaluated in parallel in random order. The expression expr must not access global variables or variables declared with local(), and must be free of side effects.

  ? parsum(i=1,1000,ispseudoprime(2^prime(i)-1))
  cpu time = 1min, 26,776 ms, real time = 5,854 ms.
  %1 = 20

returns the number of prime numbers among the first 1000 Mersenne numbers.


parvector(N, i, expr)

As vector(N,i,expr) but the evaluations of expr are done in parallel. The expression expr must not access global variables or variables declared with local(), and must be free of side effects.

  parvector(10,i,quadclassunit(2^(100+i)+1).no)

computes the class numbers in parallel.