Ask Your Question

@parallel Parallel Pollard-Rho

asked 2018-06-13 13:47:04 +0200

Softy gravatar image

updated 2018-06-13 15:56:44 +0200

I am currently working on the implementation of a parallelized Pollard-Rho algorithm. I want to use the @parallel command to

D = {}
def dist_points(P,Q,dist_prop,r):
    ord = P.order()
    seed = randint(1,ord)
    X = [seed*P,seed, 0]
    counter = 0
    counter4 = 0
    m = [randrange(0,ord) for i in range(r)]
    n = [randrange(0,ord) for k in range(r)]
    T = [(m[j]*P + n[j]*Q) for j in range(r)]
       #step function (linear walk)
       X = step_linear(T,m,n,ord,X,r)
        counter += 1
        counter4 += 1
        (Pi, ai, bi) = X
        x_coord = Pi[0]
        global D
        if ZZ(x_coord)%dist_prop==0:
            if Pi in D:
                (a,b) = D[Pi]
                if gcd((b-bi),ord)==1:
                    log = ((ai-a)/(b-bi))%ord
                    return log, counter4
                D[Pi] = (ai,bi)
                seed = randint(1,P.order())
                X = [seed*P, seed, 0]
                counter = 0
        elif counter > 100*dist_prop:
            seed = randint(1,P.order())
            X = [seed*P,seed, 0]
            counter = 0

The result of the function works. But I have the feeling that the parallelization does not work. I want my 4 CPU's to work parallel on a same list D looking for points until they find a match. But when I change the 6th line to

X = [P,1,0]

so that all the CPU's do the same walk (since my step_linear function is deterministic), I get the same timing. So it seems that the parallization does not work...

Also this program should work faster for a dist_prop>1. Since we put otherwise all points in the list, and then there is no need for a parallelization right? But my program gets slower the bigger the 'dist_prop' is.

So I thought that might be due to a wrong use of the @parallel command.

I hope someone can help me with the parallel problem!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2018-06-14 00:48:23 +0200

nbruin gravatar image

The default parallel strategy is using "fork", so the global dictionary D isn't actually shared between the different processes. You only get to communicate in one way: the result you pass back. If you want to do more, you'll have to look into shared memory, and all the locking issues that come with it (which can create lock contention that can seriously hamper the gains to be had by parallel execution).

It might seem that using threading instead of processes would solve this problem in a nicer way, but you'd probably find that Python's GIL gives similar (or worse!) lock contention.

edit flag offensive delete link more


How do I use fork? Do I just change the @parallel to @fork(4)? And how could I use 'threading'? If you have the time it would be really helpfull if you could explain this is some more detail!! (or an example?) But in any case thank you for the answer!

Softy gravatar imageSofty ( 2018-06-14 16:27:09 +0200 )edit

the @fork does not seem to work either .. or I don't know how to implement it the right way.. Could you maybe explain a bit more about how to do this?

Softy gravatar imageSofty ( 2018-06-14 17:46:08 +0200 )edit

The default strategy that @parallel uses is by forking off several processes. So, if there is a @fork decorator (and if it's meant to fork off parallel workers) then you'd get the same behaviour as with @parallel.

nbruin gravatar imagenbruin ( 2018-06-14 18:00:16 +0200 )edit

How can I implement that? Neither works. If I comment out the @parallel, my program has the same speed as with the @parallel. Something is not working... Where would I need toput the @fork decorator? (I'm really not that good a programmer.. and I don't seem to understand the parallel logic sage uses.)

Softy gravatar imageSofty ( 2018-06-14 18:07:25 +0200 )edit

In my example, how can I realize that different CPUs are working on the same list looking for a match?

Softy gravatar imageSofty ( 2018-06-14 18:25:51 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2018-06-13 13:47:04 +0200

Seen: 640 times

Last updated: Jun 14 '18