ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 06 Jun 2019 15:54:32 -0500How to implement a parallelization?http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/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)Mon, 27 May 2019 00:14:24 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/Answer by slelievre for <p>Consider a code of the kind <em>tree exploration amassing fruits</em>: 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.</p>
<p>It seems to be a generic way to parallelize such a tree exploration.</p>
<p><strong>Question</strong>: How to implement such a parallelization? <br>
In addition, how to use GPU (for HPC)?</p>
<p>The code has the following form: </p>
<pre><code>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)
</code></pre>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?answer=46685#post-id-46685Have you looked at [**map-reduce**](http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html)?
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
- [OpenDreamKit deliverable 5.1](https://github.com/OpenDreamKit/OpenDreamKit/issues/107)
(see links to final report and slides on the issue page)Mon, 27 May 2019 05:23:56 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?answer=46685#post-id-46685Comment by Sébastien Palcoux for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46840#post-id-46840@Hivert: Done! https://ask.sagemath.org/question/46839/cython-problem-with-map-reduce/Thu, 06 Jun 2019 15:54:32 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46840#post-id-46840Comment by Hivert for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46836#post-id-46836Without 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.Thu, 06 Jun 2019 14:40:34 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46836#post-id-46836Comment by slelievre for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46765#post-id-46765I see you posted two follow-up questions, I'm adding links here for reference.
- [Ask Sage question 46711: Is map_reduce working for parallel computing? How?](https://ask.sagemath.org/question/46711)
- [Ask Sage question 46754: How to use a GPU for HPC?](https://ask.sagemath.org/question/46754)Sat, 01 Jun 2019 09:53:21 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46765#post-id-46765Comment by slelievre for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46741#post-id-46741Regarding Cython or GPU, hopefully someone else can chime in.Fri, 31 May 2019 08:47:39 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46741#post-id-46741Comment by Sébastien Palcoux for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46703#post-id-46703And do you know how to use GPU?Wed, 29 May 2019 16:38:29 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46703#post-id-46703Comment by Sébastien Palcoux for <p>Have you looked at <a href="http://doc.sagemath.org/html/en/reference/parallel/sage/parallel/map_reduce.html"><strong>map-reduce</strong></a>?</p>
<p>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.</p>
<p>See also</p>
<ul>
<li><a href="https://github.com/OpenDreamKit/OpenDreamKit/issues/107">OpenDreamKit deliverable 5.1</a>
(see links to final report and slides on the issue page)</li>
</ul>
http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46699#post-id-46699It 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?Wed, 29 May 2019 11:24:22 -0500http://ask.sagemath.org/question/46682/how-to-implement-a-parallelization/?comment=46699#post-id-46699