#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: |
-------------------------------------+-------------------------------------
Comment (by hivert):
Replying to [comment:101 tscrim]:
> 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).
I'll be both very happy and interested to have usecase for this code.
> 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.
Do you have a typical example relying on {{{SearchForest}}} of code on top
of
#11187 that I can profile ? Note that I included in the documentation of
map_reduce.py a guide on how to profile the parallel code. I'd like to
measure
the proportion of time that is spend on Coxeter code one one hand and on
the
parallel infrastructure on the other.
Now, concerning coxeter group, I'm quite sure that rewriting part of the
code
in C/C++ and using advanced parallel stuff (AVX instruction set + SIMD)
you
can get speedup a large as several hundreds and even thousand ! As a
witness
on https://github.com/hivert/IVMPG I wrote a code whose goal is to
enumerate
integer vector modulo permutation group. Compared to the code we have in
Sage
which has been Cythonized and optimized by Simon King I manage to get
speedup
a large as x2000 ! I need help on the build system to be able to
distribute
it. I'm pretty sure the code there is very similar to what you need in
Coxeter
groups.
By the way, should we transfer this discussion on #11187 ?
--
Ticket URL: <http://trac.sagemath.org/ticket/13580#comment:102>
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.
