<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=koi8-r">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><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;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 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;
color:black;}
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;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;
color:black;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:Consolas;}
span.EmailStyle21
{mso-style-type:personal;
font-family:"Calibri",sans-serif;}
span.EmailStyle22
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
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 bgcolor="white" lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Hi Alexey and Johannes,<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">I believe that deferring to use of the state machine can help to make a better decision. I agree with that. However, I am not sure how feasible is that. I look forward to hearing
more details once the RFC is ready.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">In flang, currently we have implemented the SPMD mode, but not non-SPMD mode.
<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Alexey Bataev <a.bataev@outlook.com>
<br>
<b>Sent:</b> Wednesday, January 23, 2019 3:27 PM<br>
<b>To:</b> Guray Ozen <gozen@nvidia.com>; Doerfert, Johannes Rudolf <jdoerfert@anl.gov><br>
<b>Cc:</b> Gheorghe-Teod Bercea <gheorghe-teod.bercea@ibm.com>; openmp-dev@lists.llvm.org<br>
<b>Subject:</b> Re: [RFC] Late (OpenMP) GPU code "SPMD-zation"<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p>Hi Guray, I think Johannes is a little bit optimistic in his conclusion. We agreed, that this optimization can give some additional performance. But I would not say, that the RFC is accepted completely. Johannes need to prepare and post RFC for the required
transformation pass in LLVM. After that we can further investigate this idea from point of view of the frontend and the runtime library. We need the design for the new library functions and the protocol between the compiler and the library.<o:p></o:p></p>
<pre>-------------<o:p></o:p></pre>
<pre>Best regards,<o:p></o:p></pre>
<pre>Alexey Bataev<o:p></o:p></pre>
<div>
<p class="MsoNormal">23.01.2019 4:14, Guray Ozen пишет:<o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">We are working on OpenMP target offloading for GPUs in Flang, and adopting the same code generation strategy. The proposal is affecting us. It would be nice to know more details
about the proposal. So we can prepare ourselves to adapt flang (if everything goes on the way).
</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">Have you find and a solution for data sharing? How are you going to manage data sharing for SPMD and non-SPMD?</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> cfe-dev
<a href="mailto:cfe-dev-bounces@lists.llvm.org"><cfe-dev-bounces@lists.llvm.org></a>
<b>On Behalf Of </b>Doerfert, Johannes Rudolf via cfe-dev<br>
<b>Sent:</b> Wednesday, January 23, 2019 12:50 AM<br>
<b>To:</b> Alexey Bataev <a href="mailto:a.bataev@outlook.com"><a.bataev@outlook.com></a><br>
<b>Cc:</b> llvm-dev <a href="mailto:llvm-dev@lists.llvm.org"><llvm-dev@lists.llvm.org></a>;
<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>; <a href="mailto:openmp-dev@lists.llvm.org">
openmp-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [cfe-dev] [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"> <o:p></o:p></p>
<div id="divtagdefaultwrapper">
<p><span style="font-family:"Calibri",sans-serif">After an IRC discussion, I think Alexey and I are pretty much in agreement (on the general feasibility at least).</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">I try to sketch the proposed idea again below, as the initial RFC was simply not descriptive enough.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">After that, I shortly summarize how I see these changes being developed and committed so that we</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> - never have any regressions,</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> - can make an educated decision before removing any existing code.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">What we want to do:</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">The intermediate goal is that the code generated by clang for the SPMD and non-SPMD (earlier denoted as "guarded") case</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">is conceptually/structurally very similar. The current non-SPMD code is, however, a state machine generated into the user code
</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">module. This state machine is very hard to analyze and optimize. If the code would look as the SPMD code but *behave the same</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">way it does now*, we could "easily" switch from non-SPMD to SPMD version after a (late) analysis determined legality. To make</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">the code look the same but behave differently, we propose to hide the semantic difference in the runtime library calls. That is,
</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">the runtime calls emitted in the two modes are (slightly) different, or there is a flag which indicates the (initial) mode. If that mode</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif">is SPMD, the runtime behavior does not change compared to the way it is now. If that mode is non-SPMD, the runtime would
</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">separate the master and worker threads, as we do it now in the user code module, and keep the workers in an internal state machine</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">waiting for the master to provide them with work. Only the master would return from the runtime call and the mechanism</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">to distribute work to the worker threads would (for now) stay the same.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">Preliminary implementation (and integration) steps:</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">1) Design and implement the necessary runtime extensions and determine feasibility.
</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">2) Allow to Clang codegen to use the new runtime extensions if explicitly chosen by the user.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">2b) Performance comparison unoptimized new code path vs. original code path on test cases and real use cases.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">3) Implement the middle-end pass to analyze and optimize the code using the runtime extensions.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">3b) Performance comparison optimized new code path vs. original code path on real use cases.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">4) If no conceptual problem was found and 2b)/3b) determined that the new code path is superior, switch to the</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> new code path by default.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">5) If no regressions/complaints are reported after a grace period, remove the old code path from the clang front-end.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">Again, this is an early design RFC for which I welcome any feedback!</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">Thanks,</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> Johannes</span><o:p></o:p></p>
<div id="divtagdefaultwrapper">
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-family:"Calibri",sans-serif">
<hr size="2" width="98%" align="center">
</span></div>
<div id="divRplyFwdMsg">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Doerfert, Johannes Rudolf<br>
<b>Sent:</b> Tuesday, January 22, 2019 1:50:51 PM<br>
<b>To:</b> Alexey Bataev<br>
<b>Cc:</b> <a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>; <a href="mailto:openmp-dev@lists.llvm.org">
openmp-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><span style="font-family:"Calibri",sans-serif">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div id="x_divtagdefaultwrapper">
<p><span style="font-family:"Calibri",sans-serif">What do you refer to with: "No, we don't". </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">Again, I do not propose to remove the SPMD "detection" in Clang. We will still identify SPMD mode based on the syntactic criteria we have now.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif">The Clang analysis is also not affected. Thus, we will globalize/localize the same variables as we do now. I don't see why this should be any different.</span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center"><span style="font-family:"Calibri",sans-serif">
<hr size="2" width="98%" align="center">
</span></div>
<div id="x_divRplyFwdMsg">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>>
on behalf of Alexey Bataev via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Sent:</b> Tuesday, January 22, 2019 1:46:39 PM<br>
<b>To:</b> Doerfert, Johannes Rudolf<br>
<b>Cc:</b> llvm-dev; <a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>;
<a href="mailto:openmp-dev@lists.llvm.org">openmp-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><span style="font-family:"Calibri",sans-serif">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<div>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">No, we don't. We need to perform the different kind of the analysis for SPMD mode constructs and Non-SPMD.</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">For SPMD mode we need to globalize only reduction/lastprivate variables. For Non-SPMD mode, we need to globalize all the private/local variables, that may escape their declaration context
in the construct.</span><o:p></o:p></p>
<pre style="background:white">-------------<o:p></o:p></pre>
<pre style="background:white">Best regards,<o:p></o:p></pre>
<pre style="background:white">Alexey Bataev<o:p></o:p></pre>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif">22.01.2019 14:29, Doerfert, Johannes Rudolf пишет:</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div id="x_x_divtagdefaultwrapper">
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif">We would still know that. We can do exactly the same reasoning as we do now.
</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">I think the important question is, how different is the code generated for either mode and can we hide (most of) the differences in the runtime.</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">If I understand you correctly, you say the data sharing code looks very different and the differences cannot be hidden, correct?</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">It would be helpful for me to understand your point if you could give me a piece of OpenMP for which the data sharing in SPMD mode and "guarded"</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">mode are as different as possible. I can compile it in both modes myself so high-level OpenMP is fine (I will disable SPMD mode manually in the source if necessary).</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">Thanks,</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> Johannes</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<div>
<div class="MsoNormal" align="center" style="text-align:center;background:white">
<span style="font-family:"Calibri",sans-serif">
<hr size="2" width="98%" align="center">
</span></div>
<div id="x_x_divRplyFwdMsg">
<p class="MsoNormal" style="background:white"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev
<a href="mailto:llvm-dev-bounces@lists.llvm.org"><llvm-dev-bounces@lists.llvm.org></a> on behalf of Alexey Bataev via llvm-dev
<a href="mailto:llvm-dev@lists.llvm.org"><llvm-dev@lists.llvm.org></a><br>
<b>Sent:</b> Tuesday, January 22, 2019 13:10<br>
<b>To:</b> Doerfert, Johannes Rudolf<br>
<b>Cc:</b> Alexey Bataev; LLVM-Dev; Arpith Chacko Jacob; <a href="mailto:openmp-dev@lists.llvm.org">
openmp-dev@lists.llvm.org</a>; <a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><span style="font-family:"Calibri",sans-serif">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-family:"Calibri",sans-serif">But we need to know the execution mode, SPMD or "guarded"</span><o:p></o:p></p>
</div>
<pre style="background:white">-------------<o:p></o:p></pre>
<pre style="background:white">Best regards,<o:p></o:p></pre>
<pre style="background:white">Alexey Bataev<o:p></o:p></pre>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif">22.01.2019 13:54, Doerfert, Johannes Rudolf пишет:</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">We could still do that in clang, couldn't we?</span><o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Get
<a href="https://aka.ms/ghei36">Outlook for Android</a></span><o:p></o:p></p>
</div>
<p class="MsoNormal" style="background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center;background:white">
<span style="font-family:"Calibri",sans-serif">
<hr size="2" width="98%" align="center">
</span></div>
<div id="x_x_x_divRplyFwdMsg">
<p class="MsoNormal" style="background:white"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Alexey Bataev
<a href="mailto:a.bataev@outlook.com"><a.bataev@outlook.com></a><br>
<b>Sent:</b> Tuesday, January 22, 2019 12:52:42 PM<br>
<b>To:</b> Doerfert, Johannes Rudolf; <a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<b>Cc:</b> <a href="mailto:openmp-dev@lists.llvm.org">openmp-dev@lists.llvm.org</a>; LLVM-Dev; Finkel, Hal J.; Alexey Bataev; Arpith Chacko Jacob<br>
<b>Subject:</b> Re: [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><span style="font-family:"Calibri",sans-serif">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<div>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">The globalization for the local variables, for example. It must be implemented in the compiler to get the good performance, not in the runtime.</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<pre style="background:white">-------------<o:p></o:p></pre>
<pre style="background:white">Best regards,<o:p></o:p></pre>
<pre style="background:white">Alexey Bataev<o:p></o:p></pre>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif">22.01.2019 13:43, Doerfert, Johannes Rudolf пишет:</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Could you elaborate on what you refer to wrt data sharing. What do we currently do in the clang code generation that we could not
effectively implement in the runtime, potentially with support of an llvm pass.</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Thanks,</span><o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-bottom:12.0pt;background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> James</span><o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Get
<a href="https://aka.ms/ghei36">Outlook for Android</a></span><o:p></o:p></p>
</div>
<p class="MsoNormal" style="background:white"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
<div class="MsoNormal" align="center" style="text-align:center;background:white">
<span style="font-family:"Calibri",sans-serif">
<hr size="2" width="98%" align="center">
</span></div>
<div id="x_x_x_divRplyFwdMsg">
<p class="MsoNormal" style="background:white"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> Alexey Bataev
<a href="mailto:a.bataev@outlook.com"><a.bataev@outlook.com></a><br>
<b>Sent:</b> Tuesday, January 22, 2019 12:34:01 PM<br>
<b>To:</b> Doerfert, Johannes Rudolf; <a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a><br>
<b>Cc:</b> <a href="mailto:openmp-dev@lists.llvm.org">openmp-dev@lists.llvm.org</a>; LLVM-Dev; Finkel, Hal J.; Alexey Bataev; Arpith Chacko Jacob<br>
<b>Subject:</b> Re: [RFC] Late (OpenMP) GPU code "SPMD-zation"</span><span style="font-family:"Calibri",sans-serif">
</span><o:p></o:p></p>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<div>
<p style="background:white"><span style="font-family:"Calibri",sans-serif"> </span><o:p></o:p></p>
<pre style="background:white">-------------<o:p></o:p></pre>
<pre style="background:white">Best regards,<o:p></o:p></pre>
<pre style="background:white">Alexey Bataev<o:p></o:p></pre>
<div>
<p class="MsoNormal" style="background:white"><span style="font-family:"Calibri",sans-serif">22.01.2019 13:17, Doerfert, Johannes Rudolf пишет:</span><o:p></o:p></p>
</div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre style="background:white">Where we are<o:p></o:p></pre>
<pre style="background:white">------------<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">Currently, when we generate OpenMP target offloading code for GPUs, we<o:p></o:p></pre>
<pre style="background:white">use sufficient syntactic criteria to decide between two execution modes:<o:p></o:p></pre>
<pre style="background:white"> 1) SPMD -- All target threads (in an OpenMP team) run all the code.<o:p></o:p></pre>
<pre style="background:white"> 2) "Guarded" -- The master thread (of an OpenMP team) runs the user<o:p></o:p></pre>
<pre style="background:white"> code. If an OpenMP distribute region is encountered, thus<o:p></o:p></pre>
<pre style="background:white"> if all threads (in the OpenMP team) are supposed to<o:p></o:p></pre>
<pre style="background:white"> execute the region, the master wakes up the idling<o:p></o:p></pre>
<pre style="background:white"> worker threads and points them to the correct piece of<o:p></o:p></pre>
<pre style="background:white"> code for distributed execution.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">For a variety of reasons we (generally) prefer the first execution mode.<o:p></o:p></pre>
<pre style="background:white">However, depending on the code, that might not be valid, or we might<o:p></o:p></pre>
<pre style="background:white">just not know if it is in the Clang code generation phase.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">The implementation of the "guarded" execution mode follows roughly the<o:p></o:p></pre>
<pre style="background:white">state machine description in [1], though the implementation is different<o:p></o:p></pre>
<pre style="background:white">(more general) nowadays.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">What we want<o:p></o:p></pre>
<pre style="background:white">------------<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">Increase the amount of code executed in SPMD mode and the use of<o:p></o:p></pre>
<pre style="background:white">lightweight "guarding" schemes where appropriate.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">How we get (could) there<o:p></o:p></pre>
<pre style="background:white">------------------------<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">We propose the following two modifications in order:<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> 1) Move the state machine logic into the OpenMP runtime library. That<o:p></o:p></pre>
<pre style="background:white"> means in SPMD mode all device threads will start the execution of<o:p></o:p></pre>
<pre style="background:white"> the user code, thus emerge from the runtime, while in guarded mode<o:p></o:p></pre>
<pre style="background:white"> only the master will escape the runtime and the other threads will<o:p></o:p></pre>
<pre style="background:white"> idle in their state machine code that is now just "hidden".<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> Why:<o:p></o:p></pre>
<pre style="background:white"> - The state machine code cannot be (reasonably) optimized anyway,<o:p></o:p></pre>
<pre style="background:white"> moving it into the library shouldn't hurt runtime but might even<o:p></o:p></pre>
<pre style="background:white"> improve compile time a little bit.<o:p></o:p></pre>
<pre style="background:white"> - The change should also simplify the Clang code generation as we<o:p></o:p></pre>
<pre style="background:white"> would generate structurally the same code for both execution modes<o:p></o:p></pre>
<pre style="background:white"> but only the runtime library calls, or their arguments, would<o:p></o:p></pre>
<pre style="background:white"> differ between them.<o:p></o:p></pre>
<pre style="background:white"> - The reason we should not "just start in SPMD mode" and "repair"<o:p></o:p></pre>
<pre style="background:white"> it later is simple, this way we always have semantically correct<o:p></o:p></pre>
<pre style="background:white"> and executable code.<o:p></o:p></pre>
<pre style="background:white"> - Finally, and most importantly, there is now only little<o:p></o:p></pre>
<pre style="background:white"> difference (see above) between the two modes in the code<o:p></o:p></pre>
<pre style="background:white"> generated by clang. If we later analyze the code trying to decide<o:p></o:p></pre>
<pre style="background:white"> if we can use SPMD mode instead of guarded mode the analysis and<o:p></o:p></pre>
<pre style="background:white"> transformation becomes much simpler.<o:p></o:p></pre>
</blockquote>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">The last item is wrong, unfortunately. A lot of things in the codegen depend on the execution mode, e.g. correct support of the data-sharing. Of course, we can try to generalize the
codegen and rely completely on the runtime, but the performance is going to be very poor.</span><o:p></o:p></p>
<p style="background:white"><span style="font-family:"Calibri",sans-serif">We still need static analysis in the compiler. I agree, that it is better to move this analysis to the backend, at least after the inlining, but at the moment it is not possible. We
need the support for the late outlining, which will allow to implement better detection of the SPMD constructs + improve performance.</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<pre style="background:white"> 2) Implement a middle-end LLVM-IR pass that detects the guarded mode,<o:p></o:p></pre>
<pre style="background:white"> e.g., through the runtime library calls used, and that tries to<o:p></o:p></pre>
<pre style="background:white"> convert it into the SPMD mode potentially by introducing lightweight<o:p></o:p></pre>
<pre style="background:white"> guards in the process.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> Why:<o:p></o:p></pre>
<pre style="background:white"> - After the inliner, and the canonicalizations, we have a clearer<o:p></o:p></pre>
<pre style="background:white"> picture of the code that is actually executed in the target<o:p></o:p></pre>
<pre style="background:white"> region and all the side effects it contains. Thus, we can make an<o:p></o:p></pre>
<pre style="background:white"> educated decision on the required amount of guards that prevent<o:p></o:p></pre>
<pre style="background:white"> unwanted side effects from happening after a move to SPMD mode.<o:p></o:p></pre>
<pre style="background:white"> - At this point we can more easily introduce different schemes to<o:p></o:p></pre>
<pre style="background:white"> avoid side effects by threads that were not supposed to run. We<o:p></o:p></pre>
<pre style="background:white"> can decide if a state machine is needed, conditionals should be<o:p></o:p></pre>
<pre style="background:white"> employed, masked instructions are appropriate, or "dummy" local<o:p></o:p></pre>
<pre style="background:white"> storage can be used to hide the side effect from the outside<o:p></o:p></pre>
<pre style="background:white"> world.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">None of this was implemented yet but we plan to start in the immediate<o:p></o:p></pre>
<pre style="background:white">future. Any comments, ideas, criticism is welcome!<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">Cheers,<o:p></o:p></pre>
<pre style="background:white"> Johannes<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">P.S. [2-4] Provide further information on implementation and features.<o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white">[1] <a href="https://ieeexplore.ieee.org/document/7069297">https://ieeexplore.ieee.org/document/7069297</a><o:p></o:p></pre>
<pre style="background:white">[2] <a href="https://dl.acm.org/citation.cfm?id=2833161">https://dl.acm.org/citation.cfm?id=2833161</a><o:p></o:p></pre>
<pre style="background:white">[3] <a href="https://dl.acm.org/citation.cfm?id=3018870">https://dl.acm.org/citation.cfm?id=3018870</a><o:p></o:p></pre>
<pre style="background:white">[4] <a href="https://dl.acm.org/citation.cfm?id=3148189">https://dl.acm.org/citation.cfm?id=3148189</a><o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
<pre style="background:white"> <o:p></o:p></pre>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
<div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="100%" align="center">
</div>
</div>
<div>
<p class="MsoNormal">This email message is for the sole use of the intended recipient(s) and may contain confidential information. Any unauthorized review, use, disclosure or distribution is prohibited. If you are not the intended recipient, please contact
the sender by reply email and destroy all copies of the original message. <o:p></o:p></p>
</div>
<div>
<div class="MsoNormal" align="center" style="text-align:center">
<hr size="2" width="100%" align="center">
</div>
</div>
</blockquote>
</div>
</body>
</html>