<div dir="ltr">It is attached. Thank you!</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Nov 2, 2020 at 3:34 AM Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com">mikhail.dvorskiy@intel.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-US">
<div class="gmail-m_3237610087794401547WordSection1">
<p class="MsoNormal">Hi Christopher,<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">I will try to investigate what is wrong…<u></u><u></u></p>
<p class="MsoNormal">Could you please send me a your merged version of algorithm_impl.h? I’ll check it as well.<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Best regards,<u></u><u></u></p>
<p class="MsoNormal">Mikhail Dvorskiy<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><b>From:</b> Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>> <br>
<b>Sent:</b> Saturday, October 31, 2020 5:33 PM<br>
<b>To:</b> Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>><br>
<b>Cc:</b> Kukanov, Alexey <<a href="mailto:Alexey.Kukanov@intel.com" target="_blank">Alexey.Kukanov@intel.com</a>>; Pavlov, Evgeniy <<a href="mailto:evgeniy.pavlov@intel.com" target="_blank">evgeniy.pavlov@intel.com</a>>; Louis Dionne <<a href="mailto:ldionne@apple.com" target="_blank">ldionne@apple.com</a>>; Thomas Rodgers <<a href="mailto:trodgers@redhat.com" target="_blank">trodgers@redhat.com</a>>; Libc++ Dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [libcxx-dev] OpenMP parallel reduce bugs<u></u><u></u></p>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">Hi Mikhail,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I used the patch, but the unit tests are failing. Maybe I applied the patch badly, or perhaps I did something wrong in the reducer. I rewrote the parallel reduce function as:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<pre><span style="font-size:11.5pt;color:rgb(0,51,179)">template </span><span style="font-size:11.5pt;color:rgb(8,8,8)"><</span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction</span><span style="font-size:11.5pt;color:rgb(8,8,8)">><br></span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value<br></span><span style="font-size:11.5pt;color:rgb(0,98,122)">__parallel_reduce_body</span><span style="font-size:11.5pt;color:rgb(8,8,8)">(</span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__first, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__last, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__identity,<br> </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__real_body, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__reduction)<br>{<br> std::size_t </span><span style="font-size:11.5pt;color:black">__n_chunks</span><span style="font-size:11.5pt;color:rgb(8,8,8)">{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">}, __chunk_size{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">}, __first_chunk_size{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">};<br> __omp_backend::__chunk_partitioner(__first, __last, __n_chunks, __chunk_size, __first_chunk_size);<br><br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">using </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_CombinerType </span><span style="font-size:11.5pt;color:rgb(8,8,8)">= </span><span style="font-size:11.5pt;color:teal">__pstl</span><span style="font-size:11.5pt;color:rgb(8,8,8)">::</span><span style="font-size:11.5pt;color:teal">__internal</span><span style="font-size:11.5pt;color:rgb(8,8,8)">::</span><span style="font-size:11.5pt;color:teal">_Combiner</span><span style="font-size:11.5pt;color:rgb(8,8,8)"><</span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction</span><span style="font-size:11.5pt;color:rgb(8,8,8)">>;<br> </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_CombinerType </span><span style="font-size:11.5pt;color:black">__result</span><span style="font-size:11.5pt;color:rgb(8,8,8)">{__identity, &__reduction};<br> _PSTL_PRAGMA_DECLARE_REDUCTION(__combiner, _CombinerType)<br><br> </span><i><span style="font-size:11.5pt;color:rgb(140,140,140)">// To avoid over-subscription we use taskloop for the nested parallelism<br> </span></i><span style="font-size:11.5pt;color:rgb(8,8,8)">_PSTL_PRAGMA(omp taskloop reduction(__combiner : __result))<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">for </span><span style="font-size:11.5pt;color:rgb(8,8,8)">(std::size_t __chunk = </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">; __chunk < __n_chunks; ++__chunk)<br> {<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__this_chunk_size = __chunk == </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">? __first_chunk_size : __chunk_size;<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__index = __chunk == </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">? </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">: (__chunk * __chunk_size) + (__first_chunk_size - __chunk_size);<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__begin = __first + __index;<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__end = __begin + __this_chunk_size;<br> __result.__value = __real_body(__begin, __end, __identity);<br> }<br><br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">return </span><span style="font-size:11.5pt;color:black">__result</span><span style="font-size:11.5pt;color:rgb(8,8,8)">.</span><span style="font-size:11.5pt;color:black">__value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">;<br>}<u></u><u></u></span></pre>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Sat, Oct 31, 2020 at 9:35 AM Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal">I was able to puzzle out the patch, and it seems to compile now. I'll rewrite the reducer and see how it goes. Thanks!<u></u><u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Oct 30, 2020 at 4:29 PM Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal">Hi Mikhail,<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I tried to apply the patch today, but it doesn't apply cleanly. May I ask what version of the repo I should use? After I apply it (skipping a hunk that doesn't apply) I get some compile errors:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal"><br>
/home/christopher/projects/llvm-project/pstl/include/pstl/internal/algorithm_impl.h:1780:13: error: unknown type name '_ReduceRes'<br>
_ReduceRes __table[] = {__broken, __broken, __broken, __broken, __broken, __all_true,<br>
^<br>
/home/christopher/projects/llvm-project/pstl/include/pstl/internal/algorithm_impl.h:1783:13: error: use of '_ReduceType' with tag type that does not match previous declaration<br>
struct _ReduceType<br>
^<br>
/home/christopher/projects/llvm-project/pstl/include/pstl/internal/algorithm_impl.h:1770:18: note: previous use is here<br>
enum _ReduceType<br>
^<br>
/home/christopher/projects/llvm-project/pstl/include/pstl/internal/algorithm_impl.h:1802:54: error: use of undeclared identifier '__val1'; did you mean '__value'?<br>
return _ReduceType{__broken, __val1.__pos};<br>
^~~~~~<br>
__value<br>
/home/christopher/projects/llvm-project/pstl/include/pstl/internal/algorithm_impl.h:1799:73: note: '__value' declared here<br>
_ReduceType __value) -> _ReduceType {<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<p class="MsoNormal">On Wed, Oct 21, 2020 at 9:36 AM Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal">Hi Christopher,<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Please find the attachment - a patch which fixes the mentioned problem with is partitioned algo. I’ve not yet promoted it into LLVM repo, but you can check it now with OpenMP backend.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Best regards,<u></u><u></u></p>
<p class="MsoNormal">Mikhail Dvorskiy<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal"><b>From:</b> Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>>
<br>
<b>Sent:</b> Monday, October 5, 2020 3:01 PM<br>
<b>To:</b> Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>><br>
<b>Cc:</b> Kukanov, Alexey <<a href="mailto:Alexey.Kukanov@intel.com" target="_blank">Alexey.Kukanov@intel.com</a>>; Pavlov, Evgeniy <<a href="mailto:evgeniy.pavlov@intel.com" target="_blank">evgeniy.pavlov@intel.com</a>>; Louis Dionne <<a href="mailto:ldionne@apple.com" target="_blank">ldionne@apple.com</a>>;
Thomas Rodgers <<a href="mailto:trodgers@redhat.com" target="_blank">trodgers@redhat.com</a>>; Libc++ Dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [libcxx-dev] OpenMP parallel reduce bugs<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<p class="MsoNormal">Great, thanks! <u></u><u></u></p>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I appreciate it!<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Mon, Oct 5, 2020, 04:22 Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin:5pt 0in 5pt 4.8pt">
<div>
<div>
<p class="MsoNormal">Hi Christopher,<u></u><u></u></p>
<p class="MsoNormal">I’ve double check the code of __pattern_is_partitioned (which is based on the reduction parallel pattern). Yes, a binary operation is not commutative. So, my hypo was right.<u></u><u></u></p>
<p class="MsoNormal">Generally speaking the writing “manually” reduction pattern w/o OpenMP s reducer is not good approach due to it may be not effective. Indeed, if we consider your example – the
second loop (for) combines the results in serial mode, and std::vector brings additional overheads…<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Once more, OpenMP reduction requires commutative binary operation and it is right. With PSTL design perspective an algorithm pattern should not rely on a fact that a parallel reduction
pattern (which is provided by a parallel backend) support a non-commutative binary operation. So, it is an issue of __pattern_is_partitioned and we will fix it. So while I would suggest don’t worry about that.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Best regards,<u></u><u></u></p>
<p class="MsoNormal">Mikhail Dvorskiy<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal"><b>From:</b> Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>>
<br>
<b>Sent:</b> Saturday, October 3, 2020 6:19 PM<br>
<b>To:</b> Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>><br>
<b>Cc:</b> Kukanov, Alexey <<a href="mailto:Alexey.Kukanov@intel.com" target="_blank">Alexey.Kukanov@intel.com</a>>; Pavlov, Evgeniy <<a href="mailto:evgeniy.pavlov@intel.com" target="_blank">evgeniy.pavlov@intel.com</a>>; Louis Dionne <<a href="mailto:ldionne@apple.com" target="_blank">ldionne@apple.com</a>>;
Thomas Rodgers <<a href="mailto:trodgers@redhat.com" target="_blank">trodgers@redhat.com</a>>; Libc++ Dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [libcxx-dev] OpenMP parallel reduce bugs<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<p class="MsoNormal">Hello again,<u></u><u></u></p>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I was able to rewrite the parallel_reduce function in a way that works without using OpenMP's reducer. I have a couple of questions:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">1. I use a vector to gather the intervening results for later reduction. Is there any problem depending on vector here?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">2. I can see that it might make sense to build a taskloop for the actual reduction if the number of chunks is quite large. Is that something that I should look into more?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">The code is below. Please let me know if you have any questions or concerns.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<pre><i><span style="font-size:11.5pt;color:rgb(140,140,140)">//------------------------------------------------------------------------<br>// parallel_reduce<br>//------------------------------------------------------------------------<br><br></span></i><span style="font-size:11.5pt;color:rgb(0,51,179)">template </span><span style="font-size:11.5pt;color:rgb(8,8,8)"><</span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction</span><span style="font-size:11.5pt;color:rgb(8,8,8)">><br></span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value<br></span><span style="font-size:11.5pt;color:rgb(0,98,122)">__parallel_reduce_body</span><span style="font-size:11.5pt;color:rgb(8,8,8)">(</span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__first, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__last, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__identity,<br> </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__real_body, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__reduction)<br>{<br> std::size_t </span><span style="font-size:11.5pt;color:black">__n_chunks</span><span style="font-size:11.5pt;color:rgb(8,8,8)">{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">}, __chunk_size{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">}, __first_chunk_size{</span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">};<br> __chunk_partitioner(__first, __last, __n_chunks, __chunk_size, __first_chunk_size);<br><br> std::vector<_Value> __values(__n_chunks);<br><br> </span><i><span style="font-size:11.5pt;color:rgb(140,140,140)">// To avoid over-subscription we use taskloop for the nested parallelism<br> </span></i><span style="font-size:11.5pt;color:rgb(8,8,8)">_PSTL_PRAGMA(omp taskloop shared(__values))<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">for </span><span style="font-size:11.5pt;color:rgb(8,8,8)">(std::size_t __chunk = </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">; __chunk < __n_chunks; ++__chunk)<br> {<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__this_chunk_size = __chunk == </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">? __first_chunk_size : __chunk_size;<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__index = __chunk == </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">? </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0 </span><span style="font-size:11.5pt;color:rgb(8,8,8)">: (__chunk * __chunk_size) + (__first_chunk_size - __chunk_size);<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__begin = __first + __index;<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__end = __begin + __this_chunk_size;<br> __values[__chunk] = __real_body(__begin, __end, __identity);<br> }<br><br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:black">__result </span><span style="font-size:11.5pt;color:rgb(8,8,8)">= __values.front();<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">for </span><span style="font-size:11.5pt;color:rgb(8,8,8)">(</span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">p = __values.begin() + </span><span style="font-size:11.5pt;color:rgb(23,80,235)">1</span><span style="font-size:11.5pt;color:rgb(8,8,8)">; p != __values.end(); ++p)<br> {<br> __result = __reduction(__result, *p);<br> }<br><br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">return </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__result;<br>}</span><u></u><u></u></pre>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Fri, Oct 2, 2020 at 1:33 PM Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin:5pt 0in 5pt 4.8pt">
<div>
<p class="MsoNormal">Thank you. I wondered if you had an update on this. I've done some further looking, and I think that is correct. I've tried to find example implementations of performing reductions
with openmp that don't require a commutative operator. It seems like rewriting the is_partioned algorithm to provide a commutative operator might be a larger / undesirable change.<u></u><u></u></p>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Do you have any guidance on manually writing a task loop in openmp that performs the reduction without requiring commutativity?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Thanks!<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">-={C}=-<u></u><u></u></p>
</div>
</div>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">On Thu, Oct 1, 2020 at 9:11 AM Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>> wrote:<u></u><u></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin:5pt 0in 5pt 4.8pt">
<div>
<div>
<p class="MsoNormal">Hi Christopher,<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Yes, <span style="font-size:10pt;font-family:"Segoe UI",sans-serif;color:black">“is_partitioned” algo implementation is based on a reduction parallel pattern. </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Segoe UI",sans-serif;color:black">And it looks that a binary operation (combiner) is not commutative.</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Segoe UI",sans-serif;color:black"> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Segoe UI",sans-serif;color:black">In general, “reduction” algorithm requires a commutative binary operation. And OpenMP reduction requires
that.</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-size:10pt;font-family:"Segoe UI",sans-serif;color:black">For TBB backend it works because TBB parallel reduction algorithm doesn’t require a commutative binary
operation. </span><u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">We (me or Evgeniy) will check that hypo and inform you.<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal">Best regards,<u></u><u></u></p>
<p class="MsoNormal">Mikhail Dvorskiy<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<p class="MsoNormal"><b>From:</b> Christopher Nelson <<a href="mailto:nadiasvertex@gmail.com" target="_blank">nadiasvertex@gmail.com</a>>
<br>
<b>Sent:</b> Thursday, October 1, 2020 2:46 AM<br>
<b>To:</b> Kukanov, Alexey <<a href="mailto:Alexey.Kukanov@intel.com" target="_blank">Alexey.Kukanov@intel.com</a>><br>
<b>Cc:</b> Dvorskiy, Mikhail <<a href="mailto:mikhail.dvorskiy@intel.com" target="_blank">mikhail.dvorskiy@intel.com</a>>; Pavlov, Evgeniy <<a href="mailto:evgeniy.pavlov@intel.com" target="_blank">evgeniy.pavlov@intel.com</a>>; Louis Dionne <<a href="mailto:ldionne@apple.com" target="_blank">ldionne@apple.com</a>>;
Thomas Rodgers <<a href="mailto:trodgers@redhat.com" target="_blank">trodgers@redhat.com</a>>; Libc++ Dev <<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a>><br>
<b>Subject:</b> [libcxx-dev] OpenMP parallel reduce bugs<u></u><u></u></p>
<p class="MsoNormal"> <u></u><u></u></p>
<div>
<div>
<p class="MsoNormal">Hello friends,<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I have been working on the OpenMP backend for the parallel STL, and most of the tests are passing. However, among the failures is the "is_partitioned" test. I have rewritten the
__parallel_reduce backend function to be simpler to understand in an attempt to understand what is failing (code is below.)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I also rewrote it as a serial function that splits the iteration range in two and then calls __reduction() on each half of the range being passed in. The result I get from the serial
execution as compared to the result I get from the parallel execution is different.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I have verified that the parallel execution tasks are run, and that their results match what each serial execution would be if I ran them that way.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">I am wondering if there is something wrong with the way OpenMP is running the reducer here? Perhaps it is injecting a value into the computation that is unexpected for this algorithm?
Does anything jump out at anyone as being suspicious?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">Thank you again for your time and assistance!<u></u><u></u></p>
</div>
<div>
<pre><span style="font-size:11.5pt;color:rgb(0,51,179)">template </span><span style="font-size:11.5pt;color:rgb(8,8,8)"><</span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">class </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(0,51,179)">typename </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction</span><span style="font-size:11.5pt;color:rgb(8,8,8)">><br></span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value<br></span><span style="font-size:11.5pt;color:rgb(0,98,122)">__parallel_reduce_body</span><span style="font-size:11.5pt;color:rgb(8,8,8)">(</span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__first, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RandomAccessIterator </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__last, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__identity,<br> </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_RealBody </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__real_body, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__reduction)<br>{<br> std::size_t </span><span style="font-size:11.5pt;color:black">__item_count </span><span style="font-size:11.5pt;color:rgb(8,8,8)">= __last - __first;<br> std::size_t </span><span style="font-size:11.5pt;color:black">__head_items </span><span style="font-size:11.5pt;color:rgb(8,8,8)">= (__item_count / __default_chunk_size) * __default_chunk_size;<br><br> </span><i><span style="font-size:11.5pt;color:rgb(140,140,140)">// We should encapsulate a result value and a reduction operator since we<br> // cannot use a lambda in OpenMP UDR.<br> </span></i><span style="font-size:11.5pt;color:rgb(0,51,179)">using </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_CombinerType </span><span style="font-size:11.5pt;color:rgb(8,8,8)">= </span><span style="font-size:11.5pt;color:teal">__pstl</span><span style="font-size:11.5pt;color:rgb(8,8,8)">::</span><span style="font-size:11.5pt;color:teal">__internal</span><span style="font-size:11.5pt;color:rgb(8,8,8)">::</span><span style="font-size:11.5pt;color:teal">_Combiner</span><span style="font-size:11.5pt;color:rgb(8,8,8)"><</span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">, </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_Reduction</span><span style="font-size:11.5pt;color:rgb(8,8,8)">>;<br> </span><span style="font-size:11.5pt;color:rgb(55,31,128)">_CombinerType </span><span style="font-size:11.5pt;color:black">__result</span><span style="font-size:11.5pt;color:rgb(8,8,8)">{__identity, &__reduction};<br> _PSTL_PRAGMA_DECLARE_REDUCTION(__combiner, _CombinerType)<br><br> </span><i><span style="font-size:11.5pt;color:rgb(140,140,140)">// To avoid over-subscription we use taskloop for the nested parallelism<br> //_PSTL_PRAGMA(omp taskloop reduction(__combiner : __result))<br> </span></i><span style="font-size:11.5pt;color:rgb(0,51,179)">for </span><span style="font-size:11.5pt;color:rgb(8,8,8)">(std::size_t __i = </span><span style="font-size:11.5pt;color:rgb(23,80,235)">0</span><span style="font-size:11.5pt;color:rgb(8,8,8)">; __i < __item_count; __i += __default_chunk_size)<br> {<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__begin = __first + __i;<br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">auto </span><span style="font-size:11.5pt;color:rgb(8,8,8)">__end = __i < __head_items ? __begin + __default_chunk_size : __last;<br> __result.__value = __real_body(__begin, __end, __identity);<br> }<br><br> </span><span style="font-size:11.5pt;color:rgb(0,51,179)">return </span><span style="font-size:11.5pt;color:black">__result</span><span style="font-size:11.5pt;color:rgb(8,8,8)">.</span><span style="font-size:11.5pt;color:black">__value</span><span style="font-size:11.5pt;color:rgb(8,8,8)">;<br>} </span><u></u><u></u></pre>
</div>
</div>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote></div>