OpenMP parallelisation of strided assigner

[starboerg]

Using multidimensional arrays xtensor libary performs parallelization of the inner-most loop in assignments (xasssign.h:). This creates a massive overhead compared to parallelization of the outer loop (just imagine a 100x100x100 array) .
In addition, OpenMP could be combined with TBB.
Currently users are forced to implement these loops manually and turn off xtensors OpenMP usage.

[JohanMabille]

Not sure to understand, the only case of assign with nested loops is the strided_assign, which does not support OpenMP.

All other assign mechanisms have a single loop.

[starboerg]

Thanks for the quick reply!!
Yes, I had a closer look to the code now and also realized the strided_loop_assigner to be not parallelized at all.
The use case I have in mind is to apply a diffusion kernel on an array using views shifted by the offsets of the kernel elements. Since you have to use shadow regions in that case, you will likely end up in the strided assign.

[JohanMabille]

Is that something you would like to implement?

[starboerg]

I would give it a try. I will have a look at your iterator implementation if everything required is there in order to chunk the outer loop.
Nice documentation, btw. https://xtensor.readthedocs.io/en/latest/developer/iterating_expression.html

[JohanMabille]

Thanks!

I think the stepper have all the basic methods required to parallelize the loop, but maybe we could add convenient functions to implement that feature more easily.

[starboerg]

H Johan,
it took me a while to get back on this.
I implemented the parallelization of strided_loop_assigner() and i will continue to work on it and test it.

However, I touched another issue when trying to test it: although strided_loop_assigner() can deal with all assignments that are contiguous in the innermost loop, the fallback_assigner is triggered for all containers/views that are non-contiguous in any dimension, since their layout is reported to be layout_type::dynamic.
In particular, this triggers the fallback assigner for subvolume assignments of an xtensor via an xview, which may imply a performance hit of factor 4-8. How can I solve that, since I want to apply a kernel on a subvolume of an xtensor like this here :

const std::array<size_t,3> shape = {500,500,500};
xt::xtensor<double,3> a(shape), b(shape);
auto core = xt::range(1,499);
xt::noalias(xt::view(b, core, core, core)) 
			= 1.0/7.0 * (  xt::view(a, core, core, core)
			  +  xt::view(a, core, core, xt::range(2,500))
			  + xt::view(a, core, core, xt::range(0,498))
			  + xt::view(a, core, xt::range(2,500), core)
			  + xt::view(a, core, xt::range(0,498), core) 
			  + xt::view(a, xt::range(2,500), core, core) 
			  + xt::view(a, xt::range(0,498), core, core) ); 

Is that a more general issue or should that be worked around in the assigner ?

[starboerg]

This issue relates to #1603 .

Performance test of the example above using

• xview : 3070ms (fallback assigner)
• xstrided_view : 1353ms
• xview 'fixed' strided_assign 333 ms (186 ms w. 4 threads)

I would really like to help fixing the xview + strided_assigner for non-contiguous views, which are contiguous on first dimension. Any suggestion would be appreciated.