#13580: Parallel map reduce on SearchForest
-------------------------------------+-------------------------------------
Reporter: hivert | Owner: hivert
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-7.2
Component: combinatorics | Resolution:
Keywords: map-reduce, | Merged in:
days57, days77 | Reviewers: Sébastien Labbé,
Authors: Florent Hivert, | Jean-Baptiste Priez
Jean-Baptiste Priez, Nathann | Work issues:
Cohen | Commit:
Report Upstream: N/A | 134c1fad85dd50fa28528adc343bad759b174cc6
Branch: | Stopgaps:
u/hivert/ticket/13580 |
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by tscrim):
* milestone: sage-6.4 => sage-7.2
Comment:
Replying to [comment:98 hivert]:
> Replying to [comment:96 tscrim]:
> > Also, what are the current plans to cythonize `SearchForest` and the
parallel reduce map?
>
> Concerning Cythonization of map-reduce, my current opinion is that, the
code
> is designed for case where the computation of the children is costly. In
this
> case the cost of the current code should be negligible. There are a lot
of
> function calls, I'm using Python synchronization primitive, but most
> importantly, communication is are by pickling/unpickling which is very
> slow. So the idea is to reduce at most at possible the communication,
but
> without drastically changing the technology, I don't think you get a
large
> improvement without great effort. You'll need to rewrite all the
communication
> primitive and to inline the function call to the client code.
>
> On the other hand, If you are allowed to write the code directly in
C/C++
> (which is the case for small basic objects), then the Cilk extension of
C is
> wonderful. It's a small extension which is supported by GCC since
version 5,
> ICC and in recent CLANG (https://cilkplus.github.io/). I've several code
where
> I've been able to have very large speedup. See
> e.g. https://hal.archives-ouvertes.fr/hal-00823339/file/article.pdf if
you are
> curious.
>
> Now if you have a specific use case, I'll be happy to experiment.
Christian, Vivien, and I are working on trying to speed up the iteration
of finite Coxeter groups by using (subgroups of) permutation groups and
the iterator method of generic Coxeter groups, which uses a `SearchForest`
(see #11187 and the `CoxeterGroups` category). Our goal is to try and
match or beat GAP3 iteration time (which we are about ~30x slower).
We are in the process pushing our successor computation code to Cython and
some of our other methods, but we would appreciate any insights you have.
Yet the code on this ticket will definitely help with that. Thank you for
finishing it.
--
Ticket URL: <http://trac.sagemath.org/ticket/13580#comment:101>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
