<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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle17
{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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">1. Not sure I got the question right, but if you want to get real chunk bounds inside the OpenMP runtime library, I am
afraid it is impossible. Because clang goes to the runtime with normalized loop bounds, thus the runtime does not know actual values, it only knows normalized iteration space.
<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">2. You are right, the dynamic scheduling uses single atomic operation per chunk. To access if it is expensive or not,
try to distribute 1B of chunks, and you will find that the scheduling is pretty expensive comparing to static schedule for example. Working with a dozen of chunks the overhead will always be small (relatively).<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">Regards,<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"><a name="_____replyseparator"></a><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>yongkee kwon via Openmp-dev<br>
<b>Sent:</b> Sunday, January 13, 2019 5:51 AM<br>
<b>To:</b> openmp-dev@lists.llvm.org<br>
<b>Subject:</b> [Openmp-dev] questions about loop scheduling<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">Hi everyone, <o:p></o:p></p>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I'd like to ask and clarify questions that I came up with while I am working on performance tracing with various loop schedules.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">1. For static/chunked schedule with decreasing loop, I've observed something strange with kmp(c)_for_static_init(). I checked loop iteration lower and upper bound, a size of chunk, and a size of loop increment at the beginning and end of
kmp_static_init by enabling debug (KMP_D_DEBUG) and they looked like as if I set up increasing loop while it was working well as I expected. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">To be more specific, let me give you a very simple example as follows:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">omp_set_num_threads(4);</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">#pragma omp parallel for schedule(static, 4)</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><span style="font-family:"Courier New"">for( int i = 31; i >=0; i--) { LOOP_BODY };</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">In this case, thread0 would get the chunk of iteration between 31 and 28 and between 15 and 12, thread1 between 27 and 24 and between 11 and 8, and so forth. However I saw kmp(c)_for_static_init for thread0 had (LB:0, UB:3, ST:16) as if
it were an increasing loop starting at 0 or there should be a way for runtime to interpret a task of LB 0 as a loop iteration with the index of 31. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The reason why I care about this is because I'd like to track each work chunk by scheduling it arbitrarily and I was considering LB (lower bound) as a unique ID for each work chunk. However in this case, I don't know how I extract the correct
bound associate with loop iteration number of scheduled chunk. I am also looking into an implementation of Clang codegen library for OpenMP to see if what's going on there but I feel I am a bit lost. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Please help me find what I missed and correct me if I went anything wrong. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">2. To measure an overhead of dynamic/chunked scheduling, I've added callbacks at the beginning and end of __kmp_dispatch_next_algorithm() in kmp_dispatch.cpp and monitored an elapsed time in between. I was told dynamic scheduling could
be pretty expensive and thus I would expect a contention around (a sort of conceptually) centralized work queue would be expensive as we have more chunks and threads as discussed in the paper [REF1]. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">However it seems it's pretty acceptable with moderate number of threads (16-64) and a number of chunks per thread (16-64) unless I try too extreme case such as chunk of 1. I took a quick look at the implementation and it seemed to make
sense since what we paid for dynamic scheduling as compared to static scheduling is an atomic operation (test_then_inc_acq) and there was not such a centralized queue substantiated. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">I'd like to just double check what I've observed make sense to those who contributed performance tune for the runtime implementation. Any comment on your experience would be greatly appreciated!<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">FYI, I am working on Clang 7 and LLVM OpenMP 7.0. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">[REF1] OpenMP task scheduling strategies for multicore NUMA systems<o:p></o:p></p>
</div>
</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>