thr3ads.net - llvm dev - [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen" [Sep 2014]

If this information is useful, please help other people find it:
Share via:

Robison, Arch

2014-Aug-28 17:32 UTC

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

It's a problem in the OpenMP specification.  The authors (including some
from Intel) intended that the OpenMP simd construct assert no lexically backward
dependences exist, but as you say, it's not obvious from the spec.  One of
our OpenMP community members is going to bring up the ambiguity with the OpenMP
committee.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Thursday, August 28, 2014 11:53 AM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Well, having not understood the connection between lexical dependence and the
openMP simd construct yesterday, I inquired in the openMP community.  If I
understand the answer I got (from someone at Intel), the openMP simd construct
is really asserting that no lexically backward dependences exist.  This is not
at all obvious to me from reading the spec.

That answer seems to be in conflict with what you are saying below.

Thanks
Jon

-----Original Message-----
From: Robison, Arch [mailto:arch.robison at intel.com] 
Sent: Thursday, August 28, 2014 10:47 AM
To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman
(alexander.musman at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
> Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
Actually, you're note is timely, because I'm planning to send out a
patch (as soon as I update LangRef and rerun tests) that supports safelen but
*not* lexical dependences.  I don't need the safelen for Julia, but having
done the work and seeing that OpenMP needs it, feel that I should finish the
work to contribute it.

Yes, safelen and lexical forward dependences are separable.  I was initially
under the impression that to implement OpenMP 4.0 simd loops correctly, support
for both safelen and lexical forward dependences were necessary.  Indeed, the
Intel compiler supports forward lexical dependences in OpenMP 4.0 simd loops. 
(Sophisticated vectorizers have to support them anyway for auto-vectorization.) 
But upon closer reading, and discussion with the experts here, it became
apparent that the OpenMP 4.0 spec talks about execution of SIMD instructions,
but does not say much about how source code is mapped onto those instructions,
so support for lexical dependences is not necessary for 4.0.

Likewise, I'm dropping my experiment with supporting lexical forward
dependences in Julia, though I'm mulling an alternative language-level
solution.
> Assuming that lexical ordering is irrelevant to this discussion, it would
be nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.
Right.
> I was thinking that you could add an additional parameter that specifies
the minimum dependence distance.  It would be optional and if absent, would be
infinite (which preserves existing semantics).
The parameter is best put on the loop instead of each access.  That way it can
have different values for different loop levels.  I.e., each loop is marked with
its relevant component of the minimum distance vector.

With respect to a more general mechanism, and perhaps more complete distance
information, that seems worthwhile if there's real benefit to be obtained. 
I'll leave that to others, though I'd be curious to see proposed
designs.  I haven't explored the limits of LLVM's metadata format.  For
instance, what's the best way to store a distance matrix as metadata?

- I agree with Hal's request that we don't use the name
'safelen'

I'm fine with the "minimum_dependence_distance" if everyone else
is.

- Arch

-----Original Message-----
From: Humphreys, Jonathan [mailto:j-humphreys at ti.com] 
Sent: Wednesday, August 27, 2014 5:37 PM
To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman (alexander.musman
at gmail.com)
Cc: LLVM Dev
Subject: RE: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Sorry for coming to the discussion so late.  I have a couple of
questions/comments:
 - I'm no openMP expert but I don't understand the relevance of
lexically forward or backward dependence with respect to the safelen() metadata.
I would be surprised if the openMP spec based safelen() upon lexical ordering
for the reasons that you are running up against.
 - I agree with Hal's request that we don't use the name
'safelen'.  I can think of many other 'safety' requirements for
SIMD (such as alignment), and the proposed metadata is specifically addressing
memory dependence.
 - what are the semantics for outer loop dependences in nested loops?  I believe
that openMP restricts the usage of this clause to nested loops that are
perfectly nested and collapsible.  We will be introducing this metadata in LLVM
without such restrictions.
 - Assuming that lexical ordering is irrelevant to this discussion, it would be
nice if we could build upon the llvm.mem.parallel_loop_access metadata rather
than inventing more metadata.  I was thinking that you could add an additional
parameter that specifies the minimum dependence distance.  It would be optional
and if absent, would be infinite (which preserves existing semantics).
 - And having said that, I'm also wondering (but haven't thought any of
it through) if instead of inventing metadata to address particular language
features, we should instead invent a more general mechanism for expressing
memory independence through metadata.  Then the expression of a language feature
could be decomposed into basic dependence metadata.  There are many advantages
to this.  It would be more precise (operation based vs loop based).  Being
basic/lowlevel, passes that invalidate it (or enhance it) can do that at a
fundamental level and not need to be aware of a specific language feature that
might be implied in the name of the metadata.  And being more precise, it would
be more robust because any pass that introduces memory operations would not have
the metadata and so wouldn't inherit assertions that might not be true for
it.

Jon

Hal Finkel

2014-Sep-28 07:58 UTC

head link

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

----- Original Message -----> From: "Arch Robison" <arch.robison at intel.com>
> To: "Jonathan Humphreys" <j-humphreys at ti.com>, "Hal
Finkel" <hfinkel at anl.gov>, "Renato Golin"
> <renato.golin at linaro.org>, "Alexander Musman
(alexander.musman at gmail.com)" <alexander.musman at gmail.com>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu>
> Sent: Thursday, August 28, 2014 12:32:25 PM
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> It's a problem in the OpenMP specification.  The authors (including
> some from Intel) intended that the OpenMP simd construct assert no
> lexically backward dependences exist, but as you say, it's not
> obvious from the spec.  One of our OpenMP community members is going
> to bring up the ambiguity with the OpenMP committee.
What was the outcome of this?

Thanks again,
Hal
> 
> - Arch
> 
> -----Original Message-----
> From: Humphreys, Jonathan [mailto:j-humphreys at ti.com]
> Sent: Thursday, August 28, 2014 11:53 AM
> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> Well, having not understood the connection between lexical dependence
> and the openMP simd construct yesterday, I inquired in the openMP
> community.  If I understand the answer I got (from someone at
> Intel), the openMP simd construct is really asserting that no
> lexically backward dependences exist.  This is not at all obvious to
> me from reading the spec.
> 
> That answer seems to be in conflict with what you are saying below.
> 
> Thanks
> Jon
> 
> -----Original Message-----
> From: Robison, Arch [mailto:arch.robison at intel.com]
> Sent: Thursday, August 28, 2014 10:47 AM
> To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> > Sorry for coming to the discussion so late.  I have a couple of
> > questions/comments:
> 
> Actually, you're note is timely, because I'm planning to send out a
> patch (as soon as I update LangRef and rerun tests) that supports
> safelen but *not* lexical dependences.  I don't need the safelen for
> Julia, but having done the work and seeing that OpenMP needs it,
> feel that I should finish the work to contribute it.
> 
> Yes, safelen and lexical forward dependences are separable.  I was
> initially under the impression that to implement OpenMP 4.0 simd
> loops correctly, support for both safelen and lexical forward
> dependences were necessary.  Indeed, the Intel compiler supports
> forward lexical dependences in OpenMP 4.0 simd loops.
>  (Sophisticated vectorizers have to support them anyway for
> auto-vectorization.)  But upon closer reading, and discussion with
> the experts here, it became apparent that the OpenMP 4.0 spec talks
> about execution of SIMD instructions, but does not say much about
> how source code is mapped onto those instructions, so support for
> lexical dependences is not necessary for 4.0.
> 
> Likewise, I'm dropping my experiment with supporting lexical forward
> dependences in Julia, though I'm mulling an alternative
> language-level solution.
> 
> > Assuming that lexical ordering is irrelevant to this discussion, it
> > would be nice if we could build upon the
> > llvm.mem.parallel_loop_access metadata rather than inventing more
> > metadata.
> 
> Right.
> 
> > I was thinking that you could add an additional parameter that
> > specifies the minimum dependence distance.  It would be optional
> > and if absent, would be infinite (which preserves existing
> > semantics).
> 
> The parameter is best put on the loop instead of each access.  That
> way it can have different values for different loop levels.  I.e.,
> each loop is marked with its relevant component of the minimum
> distance vector.
> 
> With respect to a more general mechanism, and perhaps more complete
> distance information, that seems worthwhile if there's real benefit
> to be obtained.  I'll leave that to others, though I'd be curious
to
> see proposed designs.  I haven't explored the limits of LLVM's
> metadata format.  For instance, what's the best way to store a
> distance matrix as metadata?
> 
> - I agree with Hal's request that we don't use the name
'safelen'
> 
> I'm fine with the "minimum_dependence_distance" if everyone
else is.
> 
> - Arch
> 
> -----Original Message-----
> From: Humphreys, Jonathan [mailto:j-humphreys at ti.com]
> Sent: Wednesday, August 27, 2014 5:37 PM
> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
> 
> Sorry for coming to the discussion so late.  I have a couple of
> questions/comments:
>  - I'm no openMP expert but I don't understand the relevance of
>  lexically forward or backward dependence with respect to the
>  safelen() metadata.  I would be surprised if the openMP spec based
>  safelen() upon lexical ordering for the reasons that you are
>  running up against.
>  - I agree with Hal's request that we don't use the name
'safelen'.
>   I can think of many other 'safety' requirements for SIMD (such as
>  alignment), and the proposed metadata is specifically addressing
>  memory dependence.
>  - what are the semantics for outer loop dependences in nested loops?
>   I believe that openMP restricts the usage of this clause to nested
>  loops that are perfectly nested and collapsible.  We will be
>  introducing this metadata in LLVM without such restrictions.
>  - Assuming that lexical ordering is irrelevant to this discussion,
>  it would be nice if we could build upon the
>  llvm.mem.parallel_loop_access metadata rather than inventing more
>  metadata.  I was thinking that you could add an additional
>  parameter that specifies the minimum dependence distance.  It would
>  be optional and if absent, would be infinite (which preserves
>  existing semantics).
>  - And having said that, I'm also wondering (but haven't thought
any
>  of it through) if instead of inventing metadata to address
>  particular language features, we should instead invent a more
>  general mechanism for expressing memory independence through
>  metadata.  Then the expression of a language feature could be
>  decomposed into basic dependence metadata.  There are many
>  advantages to this.  It would be more precise (operation based vs
>  loop based).  Being basic/lowlevel, passes that invalidate it (or
>  enhance it) can do that at a fundamental level and not need to be
>  aware of a specific language feature that might be implied in the
>  name of the metadata.  And being more precise, it would be more
>  robust because any pass that introduces memory operations would not
>  have the metadata and so wouldn't inherit assertions that might not
>  be true for it.
> 
> Jon
> 
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

Tian, Xinmin

2014-Sep-28 20:40 UTC

head link

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

More precisely, for a simd loop, if the safelen(VL) clause is specified,  there
should have no loop-carried lexical backward data dependency within the
specified safe vector length VL.

We will make this clear in the OpenMP 4.1 spec.



Xinmin Tian (Intel)



-----Original Message-----
From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Hal Finkel
Sent: Sunday, September 28, 2014 12:59 AM
To: Robison, Arch
Cc: Jonathan Humphreys; LLVM Dev
Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"



----- Original Message -----
> From: "Arch Robison" <arch.robison at
intel.com<mailto:arch.robison at intel.com>>
> To: "Jonathan Humphreys" <j-humphreys at
ti.com<mailto:j-humphreys at ti.com>>, "Hal Finkel"
<hfinkel at anl.gov<mailto:hfinkel at anl.gov>>, "Renato
Golin"
> <renato.golin at linaro.org<mailto:renato.golin at
linaro.org>>, "Alexander Musman
> (alexander.musman at gmail.com<mailto:alexander.musman at
gmail.com>)" <alexander.musman at
gmail.com<mailto:alexander.musman at gmail.com>>
> Cc: "LLVM Dev" <llvmdev at cs.uiuc.edu<mailto:llvmdev at
cs.uiuc.edu>>
> Sent: Thursday, August 28, 2014 12:32:25 PM
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
>
> It's a problem in the OpenMP specification.  The authors (including
> some from Intel) intended that the OpenMP simd construct assert no
> lexically backward dependences exist, but as you say, it's not obvious
> from the spec.  One of our OpenMP community members is going to bring
> up the ambiguity with the OpenMP committee.


What was the outcome of this?



Thanks again,

Hal


>
> - Arch
>
> -----Original Message-----
> From: Humphreys, Jonathan [mailto:j-humphreys at ti.com]
> Sent: Thursday, August 28, 2014 11:53 AM
> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com<mailto:alexander.musman at gmail.com>)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
>
> Well, having not understood the connection between lexical dependence
> and the openMP simd construct yesterday, I inquired in the openMP
> community.  If I understand the answer I got (from someone at Intel),
> the openMP simd construct is really asserting that no lexically
> backward dependences exist.  This is not at all obvious to me from
> reading the spec.
>
> That answer seems to be in conflict with what you are saying below.
>
> Thanks
> Jon
>
> -----Original Message-----
> From: Robison, Arch [mailto:arch.robison at intel.com]
> Sent: Thursday, August 28, 2014 10:47 AM
> To: Humphreys, Jonathan; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com<mailto:alexander.musman at gmail.com>)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
>
> > Sorry for coming to the discussion so late.  I have a couple of
> > questions/comments:
>
> Actually, you're note is timely, because I'm planning to send out a
> patch (as soon as I update LangRef and rerun tests) that supports
> safelen but *not* lexical dependences.  I don't need the safelen for
> Julia, but having done the work and seeing that OpenMP needs it, feel
> that I should finish the work to contribute it.
>
> Yes, safelen and lexical forward dependences are separable.  I was
> initially under the impression that to implement OpenMP 4.0 simd loops
> correctly, support for both safelen and lexical forward dependences
> were necessary.  Indeed, the Intel compiler supports forward lexical
> dependences in OpenMP 4.0 simd loops.
>  (Sophisticated vectorizers have to support them anyway for
> auto-vectorization.)  But upon closer reading, and discussion with the
> experts here, it became apparent that the OpenMP 4.0 spec talks about
> execution of SIMD instructions, but does not say much about how source
> code is mapped onto those instructions, so support for lexical
> dependences is not necessary for 4.0.
>
> Likewise, I'm dropping my experiment with supporting lexical forward
> dependences in Julia, though I'm mulling an alternative language-level
> solution.
>
> > Assuming that lexical ordering is irrelevant to this discussion, it
> > would be nice if we could build upon the
> > llvm.mem.parallel_loop_access metadata rather than inventing more
> > metadata.
>
> Right.
>
> > I was thinking that you could add an additional parameter that
> > specifies the minimum dependence distance.  It would be optional and
> > if absent, would be infinite (which preserves existing semantics).
>
> The parameter is best put on the loop instead of each access.  That
> way it can have different values for different loop levels.  I.e.,
> each loop is marked with its relevant component of the minimum
> distance vector.
>
> With respect to a more general mechanism, and perhaps more complete
> distance information, that seems worthwhile if there's real benefit to
> be obtained.  I'll leave that to others, though I'd be curious to
see
> proposed designs.  I haven't explored the limits of LLVM's metadata
> format.  For instance, what's the best way to store a distance matrix
> as metadata?
>
> - I agree with Hal's request that we don't use the name
'safelen'
>
> I'm fine with the "minimum_dependence_distance" if everyone
else is.
>
> - Arch
>
> -----Original Message-----
> From: Humphreys, Jonathan [mailto:j-humphreys at ti.com]
> Sent: Wednesday, August 27, 2014 5:37 PM
> To: Robison, Arch; Hal Finkel; Renato Golin; Alexander Musman
> (alexander.musman at gmail.com<mailto:alexander.musman at gmail.com>)
> Cc: LLVM Dev
> Subject: RE: [LLVMdev] Proposal for
""llvm.mem.vectorize.safelen"
>
> Sorry for coming to the discussion so late.  I have a couple of
> questions/comments:
>  - I'm no openMP expert but I don't understand the relevance of
> lexically forward or backward dependence with respect to the
>  safelen() metadata.  I would be surprised if the openMP spec based
>  safelen() upon lexical ordering for the reasons that you are  running
> up against.
>  - I agree with Hal's request that we don't use the name
'safelen'.
>   I can think of many other 'safety' requirements for SIMD (such as
> alignment), and the proposed metadata is specifically addressing
> memory dependence.
>  - what are the semantics for outer loop dependences in nested loops?
>   I believe that openMP restricts the usage of this clause to nested
> loops that are perfectly nested and collapsible.  We will be
> introducing this metadata in LLVM without such restrictions.
>  - Assuming that lexical ordering is irrelevant to this discussion,
> it would be nice if we could build upon the
> llvm.mem.parallel_loop_access metadata rather than inventing more
> metadata.  I was thinking that you could add an additional  parameter
> that specifies the minimum dependence distance.  It would  be optional
> and if absent, would be infinite (which preserves  existing
> semantics).
>  - And having said that, I'm also wondering (but haven't thought
any
> of it through) if instead of inventing metadata to address  particular
> language features, we should instead invent a more  general mechanism
> for expressing memory independence through  metadata.  Then the
> expression of a language feature could be  decomposed into basic
> dependence metadata.  There are many  advantages to this.  It would be
> more precise (operation based vs  loop based).  Being basic/lowlevel,
> passes that invalidate it (or  enhance it) can do that at a
> fundamental level and not need to be  aware of a specific language
> feature that might be implied in the  name of the metadata.  And being
> more precise, it would be more  robust because any pass that
> introduces memory operations would not  have the metadata and so
> wouldn't inherit assertions that might not  be true for it.
>
> Jon
>
>


--

Hal Finkel

Assistant Computational Scientist

Leadership Computing Facility

Argonne National Laboratory

_______________________________________________

LLVM Developers mailing list

LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>        
http://llvm.cs.uiuc.edu

http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140928/0f0833ee/attachment.html>

Reasonably Related Threads

Search for more reasonably related threads

llvm dev - Sep 2014 - [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"

Reasonably Related Threads