You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Hello guys!
I'm trying to parallelize the generation of all of the partitions of a set S over MPI (using mpi4py).
I know the number of possible partiotions of a set containing N elements is the Bell number evaluated in N.
In my case N=19, so Bell(19)=5832742205057 (huge!).
The first way I tried was to parallelize on the number of subset composing each partition, so that I can start 19 threads each running set_partitions(S,k=threadID)
with threadID spanning from 1 to 19.
Such a way each thread generates S(19,threadID) partitions, where S(N,k) is the Stirling number.
The problem is that in this way resources are not well allocated, because the number of partitions are not equally distributed along threads, as you can see below.
As you can see the maximum Stirling number in this list (1709751003480) is about 1/3 of Bell(19), so the improvement would not be useful in practice.
There is a way to better parallize set_partitions in order to obtain better resource balancing?
I've been thinking about to start from the partitions of a subset of the entire set in order to evaluate a subset of the partitions parallely on each thread.
Have you any idea?
Thanks for help.
Ivan
[EDIT]
It seems the problem could be approached using a rooted tree discovering algoritm. How set_partitions could be modified in order to use that approach?
The text was updated successfully, but these errors were encountered:
I'm using threads beacause I can allocate them on different machines using the MPI protocol.
But it's a conceptual probelm; it does not matter if they are threads, CPUs or nodes.
Hello guys!
I'm trying to parallelize the generation of all of the partitions of a set
S
over MPI (using mpi4py).I know the number of possible partiotions of a set containing
N
elements is the Bell number evaluated inN
.In my case
N=19
, soBell(19)=5832742205057
(huge!).The first way I tried was to parallelize on the number of subset composing each partition, so that I can start 19 threads each running
set_partitions(S,k=threadID)
with
threadID
spanning from1
to19
.Such a way each thread generates S(19,threadID) partitions, where S(N,k) is the Stirling number.
The problem is that in this way resources are not well allocated, because the number of partitions are not equally distributed along threads, as you can see below.
As you can see the maximum Stirling number in this list (
1709751003480
) is about1/3
ofBell(19)
, so the improvement would not be useful in practice.There is a way to better parallize
set_partitions
in order to obtain better resource balancing?I've been thinking about to start from the partitions of a subset of the entire set in order to evaluate a subset of the partitions parallely on each thread.
Have you any idea?
Thanks for help.
Ivan
[EDIT]
It seems the problem could be approached using a rooted tree discovering algoritm. How
set_partitions
could be modified in order to use that approach?The text was updated successfully, but these errors were encountered: