Ask Your Question
1

How to implement a parallelization?

asked 2019-05-27 00:14:24 -0500

updated 2019-05-27 05:01:41 -0500

Consider a code of the kind tree exploration amassing fruits: when the procedure arrives to a new node of the tree, if it is a leaf a possible fruit is collected, else a computation is done to determine the children of the node. I would like to parallelize as follows: the children are allocated to all the available CPUs, each CPU has a queue and a given child is allocated to the CPU with the smallest queue.

It seems to be a generic way to parallelize such a tree exploration.

Question: How to implement such a parallelization?
In addition, how to use GPU (for HPC)?

The code has the following form:

cpdef function(list L1, list L2):
    cdef int i,n #...
    cdef list LL1,LL2 #...
    #...
    # core of the code
    #...
    n= #...
    for i in range(n):
        LL1= #...
        LL2= #...
        function(LL1,LL2)
edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
2

answered 2019-05-27 05:23:56 -0500

slelievre gravatar image

Have you looked at map-reduce?

If I understand correctly, it is exactly designed to parallelize such tree operations, using a "work-stealing" algorithm, whose goal is to minimize the communication overhead when parallelizing operations on highly unbalanced objects such as trees.

See also

edit flag offensive delete link more

Comments

It seems to be incompatible with Cython, I got the following error: Error compiling Cython file, AttributeError: 'ClosureScope' object has no attribute 'scope_class'. Do you know how to solve that?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2019-05-29 11:24:22 -0500 )edit

And do you know how to use GPU?

Sébastien Palcoux gravatar imageSébastien Palcoux ( 2019-05-29 16:38:29 -0500 )edit

Regarding Cython or GPU, hopefully someone else can chime in.

slelievre gravatar imageslelievre ( 2019-05-31 08:47:39 -0500 )edit
slelievre gravatar imageslelievre ( 2019-06-01 09:53:21 -0500 )edit

Without looking at the code I can't debug the Cython problem. I've used map-reduce and Cython in the past and it worked. Please post another question with some minimal code to reproduce the problem.

Hivert gravatar imageHivert ( 2019-06-06 14:40:34 -0500 )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

1 follower

Stats

Asked: 2019-05-27 00:14:24 -0500

Seen: 127 times

Last updated: May 27