<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.hoenzb
{mso-style-name:hoenzb;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
@page WordSection1
{size:8.5in 11.0in;
margin:56.7pt 42.5pt 56.7pt 85.05pt;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="RU" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">> having a thread run at 100% is detrimental to other unrelated processes in the same machine.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">You could limit the HW resources for your application (e.g. using KMP_HW_SUBSET environment variable), leaving the rest
of machine for other processes. The OpenMP runtime library has default settings those give as much performance as possible, and these settings are in contrary with composability with other applications running in parallel on the same HW. You may need to manually
adjust settings so that your application behave in composable way.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">></span><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Is this intended? Are there any
other parameters to tweak?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Yes, it is intended. If there are no tasks being executed and no tasks to execute, then the blocktime works for idle threads.
If there are tasks then threads never go to sleep waiting for more tasks to be scheduled. That is usual tasking scenario – when one task can generate many more tasks. If we would let idle threads to go to sleep when some thread generates new tasks, that
will slow down a lot of existing codes. So I don’t see how your highly unbalanced case can be improved by the library without hurting real applications with better work balance.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Regarding the wait policy, it is currently implemented so that threads call sched_yield for passive policy and spin more
actively otherwise. Unfortunately modern kernels behave so that yielding threads are scheduled for execution more frequently in order to let all threads consume equal CPU time, regardless of possible work imbalance in the application. We may think of re-implementing
the passive wait policy, or introducing new “very passive” policy, but this would need careful design and time for implementation.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">Your current suggested change breaks the task stealing algorithm, because threads do multiple attempts to steal tasks
from randomly chosen victim thread until success, and the change breaks this letting a thread go to sleep after the first stealing attempt. It would be possible to count number of tasks globally and let threads go to sleep if there are no tasks to execute.
But I suspect this can cause significant slowdown of existing codes, so a lot of performance testing should be done first before applying something like this.</span><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">-- Andrey<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Openmp-dev [mailto:openmp-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Adhityaa Chandrasekar via Openmp-dev<br>
<b>Sent:</b> Friday, September 22, 2017 9:22 AM<br>
<b>To:</b> Jeff Hammond <jeff.science@gmail.com><br>
<b>Cc:</b> openmp-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [Openmp-dev] 100% CPU usage when threads can't steal tasks<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">On Fri, Sep 22, 2017 at 2:21 AM, Jeff Hammond <<a href="mailto:jeff.science@gmail.com" target="_blank">jeff.science@gmail.com</a>> wrote:<o:p></o:p></p>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<p class="MsoNormal">You might find <a href="https://software.intel.com/en-us/forums/intel-many-integrated-core/topic/556869" target="_blank">https://software.intel.com/en-us/forums/intel-many-integrated-core/topic/556869</a> relevant.<o:p></o:p></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks for that link. I agree with the statement that time to solution is a more important metric in comparison to CPU time. However, having a thread run at 100% is detrimental to other unrelated processes in the same machine.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Is there anything else you want me to notice in that thread?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I consider idling in the OpenMP runtime to be a sign of a badly behaved application, not a runtime bug in need of fixing. But in any case, OMP_WAIT_POLICY/KMP_BLOCKTIME exist to address that.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">OMP_WAIT_POLICY and KMP_BLOCKTIME indeed are designed to solve that - however, I don't think the clang OpenMP runtime is respecting the OMP_WAIT_POLICY value -- I set `export OMP_WAIT_POLICY=passive` and compiled the example program with
g++ and clang++. The g++ binary used virtually no CPU while the clang++ binary had three processes at 100% (three because OMP_NUM_THREADS=4 and only 1 is executing a task; the other three are idle).<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Is this intended? Are there any other parameters to tweak?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">In any case, I think a default of "temporarily active for a while before switching to passive" instead of "always active unless the user manually overrides" is saner, no?<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"> <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Best,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Jeff<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<div>
<p class="MsoNormal">On Thu, Sep 21, 2017 at 1:11 PM, Adhityaa Chandrasekar via Openmp-dev <<a href="mailto:openmp-dev@lists.llvm.org" target="_blank">openmp-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p>
</div>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Hi,</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">My name is Adhityaa and I'm an undergrad student. This is my first time getting involved in OpenMP development at LLVM. I have used the library a bunch of times before, but I haven't been involved in the behind-the-scenes
work before.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">So I was just taking a look at <a href="https://bugs.llvm.org/show_bug.cgi?id=33543" target="_blank">https://bugs.llvm.org/show_bug.cgi?id=33543</a> and I tried solving it (it looked like a simple, reproducible
bug that looked quite important). First I ran strace on the program to see exactly what was happening - I found that the threads without any tasks were issuing a whole bunch of `sched_yield()`, making the CPU go to 100%.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Then I tried going into the code. I came up with a fairly simple patch that almost solved the issue:<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">--- kmp_wait_release.h (revision 313888)</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+++ kmp_wait_release.h (working copy)</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">@@ -188,6 +188,7 @@</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> // Main wait spin loop</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> while (flag->notdone_check()) {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> int in_pool;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+ int executed_tasks = 1;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> kmp_task_team_t *task_team = NULL;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> if (__kmp_tasking_mode != tskm_immediate_exec) {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> task_team = this_thr->th.th_task_team;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">@@ -200,10 +201,11 @@</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> disabled (KMP_TASKING=0). */</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> if (task_team != NULL) {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> if (TCR_SYNC_4(task_team->tt.tt_active)) {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">- if (KMP_TASKING_ENABLED(task_team))</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">- flag->execute_tasks(</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+ if (KMP_TASKING_ENABLED(task_team)) {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+ executed_tasks = flag->execute_tasks(</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> this_thr, th_gtid, final_spin,</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> &tasks_completed USE_ITT_BUILD_ARG(itt_sync_obj), 0);</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+ }</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> else</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> this_thr->th.th_reap_state = KMP_SAFE_TO_REAP;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> } else {</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">@@ -269,7 +271,7 @@</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> continue;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> </span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> // Don't suspend if there is a likelihood of new tasks being spawned.</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">- if ((task_team != NULL) && TCR_4(task_team->tt.tt_found_tasks))</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New"">+ if ((task_team != NULL) && TCR_4(task_team->tt.tt_found_tasks) && executed_tasks)</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> continue;</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> </span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt;font-family:"Courier New""> #if KMP_USE_MONITOR</span><span style="font-size:9.5pt"><o:p></o:p></span></p>
</div>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Alas, this led to a deadlock - the thread went into a futex wait and was never woke again. So I looked at how GCC did things and they issue a FUTEX_WAKE_PRIVATE for INT_MAX threads at the end of things. This
should solve the problem, I think?<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Anyway, it's pretty late here and I've been at this for over 6-7 hours at a stretch, so I'm really tired. I was just wondering if I could get some help on how to proceed from here (and whether I'm even on the
right track).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Thanks,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.5pt">Adhityaa<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt">_______________________________________________<br>
Openmp-dev mailing list<br>
<a href="mailto:Openmp-dev@lists.llvm.org" target="_blank">Openmp-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/openmp-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/openmp-dev</a><o:p></o:p></p>
</blockquote>
</div>
<p class="MsoNormal"><span style="color:#888888"><br>
<br clear="all">
<span class="hoenzb"><o:p></o:p></span></span></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal"><span class="hoenzb"><span style="color:#888888">-- </span><o:p></o:p></span></p>
<div>
<p class="MsoNormal"><span style="color:#888888">Jeff Hammond<br>
<a href="mailto:jeff.science@gmail.com" target="_blank">jeff.science@gmail.com</a><br>
<a href="http://jeffhammond.github.io/" target="_blank">http://jeffhammond.github.io/</a></span><o:p></o:p></p>
</div>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</div>
</div>
<p><br>--------------------------------------------------------------------<br>Joint Stock Company Intel A/O<br>Registered legal address: Krylatsky Hills Business Park, <br>17 Krylatskaya Str., Bldg 4, Moscow 121614, <br>Russian Federation</p><p>This e-mail and any attachments may contain confidential material for<br>the sole use of the intended recipient(s). Any review or distribution<br>by others is strictly prohibited. If you are not the intended<br>recipient, please contact the sender and delete all copies.</p>
</body>
</html>