I'm trying to parallelize a few constructions of chain complexes (given as a list of sparse matrices). I have a function that for any column (or row) computes the list of nonzero entries in that column (row), but several entries can appear at the same place $(i,j)$ in the matrix (their values should be summed).
For example, given a simplicial complex as a list bases
(simplices of given dimension), I write:
chCx[bases_] := Module[
{dim=Length@bases, dims=Length/@bases, basesk, baseskk, bdrs={}, bdr, x},
basesk =Association@Table[bases[[1,i]]->i,{i,dims[[1]]}];
Do[baseskk=Association@Table[bases[[k,i]]->i,{i,dims[[k]]}];
...
AppendTo[bdrs,bdr]; basesk=baseskk;, {k,2,dim}]; bdrs];
Then I replace ...
with 4 different commands, to get functions chCx
, chCx0
, chCx1
, chCx2
:
bdr = SparseArray[{},Length/@{basesk,baseskk}];
Do[bdr[[basesk[Delete[s,{{r}}]],baseskk[s]]]+=(-1)^(r+1),{r,1,k},{s,Keys@baseskk}];
and
bdr=SparseArray[{},Length/@{basesk,baseskk}]; SetSharedVariable[bdr]; DistributeDefinitions[basesk,baseskk];
ParallelDo[bdr[[basesk[Delete[s,{{r}}]],baseskk[s]]]+=(-1)^(r+1), {r,1,k},{s,Keys@baseskk}];
and
bdr = ParallelCombine[ Module[{bdri=SparseArray[{},Length/@{basesk,baseskk}]},
Do[bdri[[basesk[Delete[s,{{r}}]],baseskk[s]]]+=(-1)^(r+1), {r,1,k},{s,#}]; bdri]&, Keys@baseskk, Plus];
and
bdr = SparseArray[Flatten[ParallelTable[{basesk[Delete[s,{{r}}]],baseskk[s]}->(-1)^(r+1),
{r,1,k},{s,Keys@baseskk}],1],Length/@{basesk,baseskk}];
When I use these commands with
n=12; bases=Table[Subsets[Range@n,{k}],{k,1,n-1}]; (*sphere*)
AbsoluteTiming[chCx[bases]][[1]]
AbsoluteTiming[chCx0[bases]][[1]]
AbsoluteTiming[chCx1[bases]][[1]]
AbsoluteTiming[chCx2[bases]][[1]]
on a 2-core i3-560 CPU, I get:
0.774023
338.296
32.9942
17.921
Why is the nonparallelized code still the fastest? How can I efficiently parallelize this construction?
chCx0
is incredibly slow because you're using a shared variable that gets updated very frequently. This makes it necessary for the parallel kernels to constantly communicate with each other, which has a lot of overhead. Shared variables should be used with caution. $\endgroup$