<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=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@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:"\@SimSun";
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-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.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{mso-style-priority:99;
mso-style-link:"Plain Text Char";
margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.PlainTextChar
{mso-style-name:"Plain Text Char";
mso-style-priority:99;
mso-style-link:"Plain Text";
font-family:"Calibri","sans-serif";}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@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 lang="EN-US" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoPlainText">More precisely, for a simd loop, if the safelen(VL) clause is specified, there should have no loop-carried lexical backward data dependency
<b><span style="color:#4472C4">within the specified safe vector length VL</span></b>.
<o:p></o:p></p>
<p class="MsoPlainText"><a name="_MailEndCompose">We will make this clear in the OpenMP 4.1 spec.
<o:p></o:p></a></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Xinmin Tian (Intel)<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">-----Original Message-----<br>
From: llvmdev-bounces@cs.uiuc.edu [mailto:llvmdev-bounces@cs.uiuc.edu] On Behalf Of Hal Finkel<br>
Sent: Sunday, September 28, 2014 12:59 AM<br>
To: Robison, Arch<br>
Cc: Jonathan Humphreys; LLVM Dev<br>
Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"</p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">----- Original Message -----<o:p></o:p></p>
<p class="MsoPlainText">> From: "Arch Robison" <<a href="mailto:arch.robison@intel.com"><span style="color:windowtext;text-decoration:none">arch.robison@intel.com</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> To: "Jonathan Humphreys" <<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">j-humphreys@ti.com</span></a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov"><span style="color:windowtext;text-decoration:none">hfinkel@anl.gov</span></a>>,
"Renato Golin"<o:p></o:p></p>
<p class="MsoPlainText">> <<a href="mailto:renato.golin@linaro.org"><span style="color:windowtext;text-decoration:none">renato.golin@linaro.org</span></a>>, "Alexander Musman
<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)" <<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> Cc: "LLVM Dev" <<a href="mailto:llvmdev@cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">llvmdev@cs.uiuc.edu</span></a>><o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 12:32:25 PM<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> It's a problem in the OpenMP specification. The authors (including
<o:p></o:p></p>
<p class="MsoPlainText">> some from Intel) intended that the OpenMP simd construct assert no
<o:p></o:p></p>
<p class="MsoPlainText">> lexically backward dependences exist, but as you say, it's not obvious
<o:p></o:p></p>
<p class="MsoPlainText">> from the spec. One of our OpenMP community members is going to bring
<o:p></o:p></p>
<p class="MsoPlainText">> up the ambiguity with the OpenMP committee.<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">What was the outcome of this?<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">Thanks again,<o:p></o:p></p>
<p class="MsoPlainText">Hal<o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - Arch<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Humphreys, Jonathan [<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">mailto:j-humphreys@ti.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 11:53 AM<o:p></o:p></p>
<p class="MsoPlainText">> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Well, having not understood the connection between lexical dependence
<o:p></o:p></p>
<p class="MsoPlainText">> and the openMP simd construct yesterday, I inquired in the openMP
<o:p></o:p></p>
<p class="MsoPlainText">> community. If I understand the answer I got (from someone at Intel),
<o:p></o:p></p>
<p class="MsoPlainText">> the openMP simd construct is really asserting that no lexically
<o:p></o:p></p>
<p class="MsoPlainText">> backward dependences exist. This is not at all obvious to me from
<o:p></o:p></p>
<p class="MsoPlainText">> reading the spec.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> That answer seems to be in conflict with what you are saying below.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Thanks<o:p></o:p></p>
<p class="MsoPlainText">> Jon<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Robison, Arch [<a href="mailto:arch.robison@intel.com"><span style="color:windowtext;text-decoration:none">mailto:arch.robison@intel.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Thursday, August 28, 2014 10:47 AM<o:p></o:p></p>
<p class="MsoPlainText">> To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > Sorry for coming to the discussion so late. I have a couple of<o:p></o:p></p>
<p class="MsoPlainText">> > questions/comments:<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Actually, you're note is timely, because I'm planning to send out a
<o:p></o:p></p>
<p class="MsoPlainText">> patch (as soon as I update LangRef and rerun tests) that supports
<o:p></o:p></p>
<p class="MsoPlainText">> safelen but *not* lexical dependences. I don't need the safelen for
<o:p></o:p></p>
<p class="MsoPlainText">> Julia, but having done the work and seeing that OpenMP needs it, feel
<o:p></o:p></p>
<p class="MsoPlainText">> that I should finish the work to contribute it.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Yes, safelen and lexical forward dependences are separable. I was
<o:p></o:p></p>
<p class="MsoPlainText">> initially under the impression that to implement OpenMP 4.0 simd loops
<o:p></o:p></p>
<p class="MsoPlainText">> correctly, support for both safelen and lexical forward dependences
<o:p></o:p></p>
<p class="MsoPlainText">> were necessary. Indeed, the Intel compiler supports forward lexical
<o:p></o:p></p>
<p class="MsoPlainText">> dependences in OpenMP 4.0 simd loops.<o:p></o:p></p>
<p class="MsoPlainText">> (Sophisticated vectorizers have to support them anyway for<o:p></o:p></p>
<p class="MsoPlainText">> auto-vectorization.) But upon closer reading, and discussion with the
<o:p></o:p></p>
<p class="MsoPlainText">> experts here, it became apparent that the OpenMP 4.0 spec talks about
<o:p></o:p></p>
<p class="MsoPlainText">> execution of SIMD instructions, but does not say much about how source
<o:p></o:p></p>
<p class="MsoPlainText">> code is mapped onto those instructions, so support for lexical
<o:p></o:p></p>
<p class="MsoPlainText">> dependences is not necessary for 4.0.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Likewise, I'm dropping my experiment with supporting lexical forward
<o:p></o:p></p>
<p class="MsoPlainText">> dependences in Julia, though I'm mulling an alternative language-level
<o:p></o:p></p>
<p class="MsoPlainText">> solution.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > Assuming that lexical ordering is irrelevant to this discussion, it
<o:p></o:p></p>
<p class="MsoPlainText">> > would be nice if we could build upon the <o:p></o:p></p>
<p class="MsoPlainText">> > llvm.mem.parallel_loop_access metadata rather than inventing more
<o:p></o:p></p>
<p class="MsoPlainText">> > metadata.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Right.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> > I was thinking that you could add an additional parameter that
<o:p></o:p></p>
<p class="MsoPlainText">> > specifies the minimum dependence distance. It would be optional and
<o:p></o:p></p>
<p class="MsoPlainText">> > if absent, would be infinite (which preserves existing semantics).<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> The parameter is best put on the loop instead of each access. That
<o:p></o:p></p>
<p class="MsoPlainText">> way it can have different values for different loop levels. I.e.,
<o:p></o:p></p>
<p class="MsoPlainText">> each loop is marked with its relevant component of the minimum
<o:p></o:p></p>
<p class="MsoPlainText">> distance vector.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> With respect to a more general mechanism, and perhaps more complete
<o:p></o:p></p>
<p class="MsoPlainText">> distance information, that seems worthwhile if there's real benefit to
<o:p></o:p></p>
<p class="MsoPlainText">> be obtained. I'll leave that to others, though I'd be curious to see
<o:p></o:p></p>
<p class="MsoPlainText">> proposed designs. I haven't explored the limits of LLVM's metadata
<o:p></o:p></p>
<p class="MsoPlainText">> format. For instance, what's the best way to store a distance matrix
<o:p></o:p></p>
<p class="MsoPlainText">> as metadata?<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - I agree with Hal's request that we don't use the name 'safelen'<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> I'm fine with the "minimum_dependence_distance" if everyone else is.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> - Arch<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> -----Original Message-----<o:p></o:p></p>
<p class="MsoPlainText">> From: Humphreys, Jonathan [<a href="mailto:j-humphreys@ti.com"><span style="color:windowtext;text-decoration:none">mailto:j-humphreys@ti.com</span></a>]<o:p></o:p></p>
<p class="MsoPlainText">> Sent: Wednesday, August 27, 2014 5:37 PM<o:p></o:p></p>
<p class="MsoPlainText">> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman<o:p></o:p></p>
<p class="MsoPlainText">> (<a href="mailto:alexander.musman@gmail.com"><span style="color:windowtext;text-decoration:none">alexander.musman@gmail.com</span></a>)<o:p></o:p></p>
<p class="MsoPlainText">> Cc: LLVM Dev<o:p></o:p></p>
<p class="MsoPlainText">> Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Sorry for coming to the discussion so late. I have a couple of<o:p></o:p></p>
<p class="MsoPlainText">> questions/comments:<o:p></o:p></p>
<p class="MsoPlainText">> - I'm no openMP expert but I don't understand the relevance of
<o:p></o:p></p>
<p class="MsoPlainText">> lexically forward or backward dependence with respect to the<o:p></o:p></p>
<p class="MsoPlainText">> safelen() metadata. I would be surprised if the openMP spec based<o:p></o:p></p>
<p class="MsoPlainText">> safelen() upon lexical ordering for the reasons that you are running
<o:p></o:p></p>
<p class="MsoPlainText">> up against.<o:p></o:p></p>
<p class="MsoPlainText">> - I agree with Hal's request that we don't use the name 'safelen'.<o:p></o:p></p>
<p class="MsoPlainText">> I can think of many other 'safety' requirements for SIMD (such as
<o:p></o:p></p>
<p class="MsoPlainText">> alignment), and the proposed metadata is specifically addressing
<o:p></o:p></p>
<p class="MsoPlainText">> memory dependence.<o:p></o:p></p>
<p class="MsoPlainText">> - what are the semantics for outer loop dependences in nested loops?<o:p></o:p></p>
<p class="MsoPlainText">> I believe that openMP restricts the usage of this clause to nested
<o:p></o:p></p>
<p class="MsoPlainText">> loops that are perfectly nested and collapsible. We will be
<o:p></o:p></p>
<p class="MsoPlainText">> introducing this metadata in LLVM without such restrictions.<o:p></o:p></p>
<p class="MsoPlainText">> - Assuming that lexical ordering is irrelevant to this discussion,
<o:p></o:p></p>
<p class="MsoPlainText">> it would be nice if we could build upon the <o:p></o:p></p>
<p class="MsoPlainText">> llvm.mem.parallel_loop_access metadata rather than inventing more
<o:p></o:p></p>
<p class="MsoPlainText">> metadata. I was thinking that you could add an additional parameter
<o:p></o:p></p>
<p class="MsoPlainText">> that specifies the minimum dependence distance. It would be optional
<o:p></o:p></p>
<p class="MsoPlainText">> and if absent, would be infinite (which preserves existing
<o:p></o:p></p>
<p class="MsoPlainText">> semantics).<o:p></o:p></p>
<p class="MsoPlainText">> - And having said that, I'm also wondering (but haven't thought any
<o:p></o:p></p>
<p class="MsoPlainText">> of it through) if instead of inventing metadata to address particular
<o:p></o:p></p>
<p class="MsoPlainText">> language features, we should instead invent a more general mechanism
<o:p></o:p></p>
<p class="MsoPlainText">> for expressing memory independence through metadata. Then the
<o:p></o:p></p>
<p class="MsoPlainText">> expression of a language feature could be decomposed into basic
<o:p></o:p></p>
<p class="MsoPlainText">> dependence metadata. There are many advantages to this. It would be
<o:p></o:p></p>
<p class="MsoPlainText">> more precise (operation based vs loop based). Being basic/lowlevel,
<o:p></o:p></p>
<p class="MsoPlainText">> passes that invalidate it (or enhance it) can do that at a
<o:p></o:p></p>
<p class="MsoPlainText">> fundamental level and not need to be aware of a specific language
<o:p></o:p></p>
<p class="MsoPlainText">> feature that might be implied in the name of the metadata. And being
<o:p></o:p></p>
<p class="MsoPlainText">> more precise, it would be more robust because any pass that
<o:p></o:p></p>
<p class="MsoPlainText">> introduces memory operations would not have the metadata and so
<o:p></o:p></p>
<p class="MsoPlainText">> wouldn't inherit assertions that might not be true for it.<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> Jon<o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText">> <o:p></o:p></p>
<p class="MsoPlainText"><o:p> </o:p></p>
<p class="MsoPlainText">--<o:p></o:p></p>
<p class="MsoPlainText">Hal Finkel<o:p></o:p></p>
<p class="MsoPlainText">Assistant Computational Scientist<o:p></o:p></p>
<p class="MsoPlainText">Leadership Computing Facility<o:p></o:p></p>
<p class="MsoPlainText">Argonne National Laboratory<o:p></o:p></p>
<p class="MsoPlainText">_______________________________________________<o:p></o:p></p>
<p class="MsoPlainText">LLVM Developers mailing list<o:p></o:p></p>
<p class="MsoPlainText"><a href="mailto:LLVMdev@cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">LLVMdev@cs.uiuc.edu</span></a> <a href="http://llvm.cs.uiuc.edu"><span style="color:windowtext;text-decoration:none">http://llvm.cs.uiuc.edu</span></a><o:p></o:p></p>
<p class="MsoPlainText"><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"><span style="color:windowtext;text-decoration:none">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</span></a><o:p></o:p></p>
</div>
</body>
</html>