1
$\begingroup$

Intro

I am trying to do various calculations (call some Analyze[point, neighbourhood] function) over the large datasets of points in 2D space. The nature of the calculations is irrelevant, but basic scenario is this:

  • for each point we get all the neighbours within a certain window around it;
  • apply the Analyze[...] function to the list of the neighbours.

I use Nearest[...] to generate NearestFunction, which I then apply to each point as needed to obtain list of neighbours.

The problem

The issue is that I cannot parallelise it automatically. An example is below, with Analyze[...] reproducing the work of native MeanShift[...]:

data = RandomReal[{0, 1}, {10000, 2}];

AbsoluteTiming[
 nf = Nearest[data]
 ]

Print["Native MeanShift[...]:"]
AbsoluteTiming[a = MeanShift[data, 0.1]; Short[a]]
Print["Serial Map of custom meanshift:"]
AbsoluteTiming[b = Map[Mean[nf[#, {All, 0.1}]] &, data]; Short[b]]
Print["ParallelMap of custom meanshift:"]
AbsoluteTiming[c = ParallelMap[Mean[nf[#, {All, 0.1}]] &, data];Short[c]]

Chop[a - b] // Norm
Chop[a - c] // Norm



"Native MeanShift[...]:"
Out[1853]= {0.196895,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

"Serial Map of custom meanshift:"
Out[1855]= {0.316036,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

"ParallelMap of custom meanshift:"
Out[1857]= {2.45064,{{0.952903,0.197091},{0.401769,0.566927},<<9997>>,{0.0726459,0.558314}}}

Out[1858]= 0
Out[1859]= 0

Question

As you can see, the ParallelMap is slower than serial execution. Why? What are the actual guts of the NearestFunction[...] that in ParallelMap version it experiences a slowdown?

I'm guessing there might be some access conflicts, with different parallel kernels using their own automatically distributed copies of index function (if that what NearestFunction[...] is) but trying to access the global data list simultaneously.

If that's the case, what is the workaround – distribute the data itself and create nearest function within each parallel kernel?

Thanks in advance for any advice!

$\endgroup$
  • $\begingroup$ It might be faster if you use DistributeDefinitions on the NerestFunction. Also granularity matters here. If you divvy the data into chunks you might get improvment. But best is probably to take advantage of listability and do Mean[nf[data, {All, 0.1}]] . Under the hood the NearstFunction will use parallel mapping I believe. $\endgroup$ – Daniel Lichtblau Jul 9 '17 at 14:48
  • $\begingroup$ Note that MeanShift is already parallelized (via the Math Kernel Library, probably). $\endgroup$ – Michael E2 Jul 9 '17 at 20:41
  • $\begingroup$ Thank you! Appreciate the tip about the listability in NearestFunction[] – it does perform better than mapping over the list of points. Unfortunately such listable call seems to be a recent addition: supported in v11, but not in v10 (at least not in Linux version I have access to). Probably the issue in the question is the implicit parallelisation of NearestFunction[], just like the MeanShift. Then the attempt to use second layer of parallelisation via ParallelMap degrades the performance. I wonder if one can restrict this "implicit" Math Kernel parallelisation? $\endgroup$ – Yury Jul 12 '17 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.