#18987: Parallel computation for TilingSolver.number_of_solutions
-------------------------+-------------------------------------------------
Reporter: | Owner:
slabbe | Status: needs_work
Type: | Milestone: sage-6.9
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers: Vincent Delecroix
combinatorics | Work issues:
Keywords: | Commit:
Authors: | b370fd04a3efb7393d5516936958c552934faa7f
Sébastien Labbé | Stopgaps:
Report Upstream: N/A |
Branch: |
u/slabbe/18987 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by vdelecroix):
Replying to [comment:10 slabbe]:
> Replying to [comment:9 vdelecroix]:
> > Salut Sebastien,
> >
> > Do you mind if I rebase over 6.9.beta1?
>
> Merge or rebase? I prefer if you merge. Or I can rebase on 6.9.beta1 to
keep the authorship (right?).
The autorship of what? If I do a rebase, you keep the autorship of
commits. But of course it will be my branch (or a public one).
I do prefer rebase over merge because:
- history is much cleaner afterwards (fewer commits that follow each
other)
- you can hide whatever you want in a merge commit
> > Note that I also have a waiting commit that does some tiny
optimization to `dancing_links.pyx`.
>
> Where?
On my computer ;-) It is waiting for the rebase or merge.
> > I am not sure the overall strategy is the good one. If parallelization
is needed I guess that it should better be implemented at the level of
dancing links. Googling "parallelization dancing links" already gives a
lot of things.
>
> Indeed, I am using a parallelization strategy that applies to a tiling
problem where each piece is used only once. This strategy obviously does
not apply to the general problem that is the Exact cover problem.
In the exact cover problem, each subset is used at most once. In your
tiling formulation a piece count for several subsets. You can naively
apply the same thing for dancing links: look at one position `i0` and
consider the set `S0` of subsets that cover it. For each subset in `S0`,
launch a thread where you only run through the subproblem that consists of
having fixed this subset.
But I guess that there exists less naive parallelization.
> Also, I prefered to cut the (tiling) problem into subproblems that takes
at most 2-3 hours each so that I can more easily follow the process of the
computation and stop and restart the computation more easily. Even with a
parallel implementation of dancing links, the computation would take days
to finish.
Why? If your parallization ends with a time better than `total_time /
nb_cpus` then you should parallelize more often ;-)
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/18987#comment:11>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
