llvm dev - May 2017 - PSA: Parallel STL algorithms available in LLVM

Even without a concrete use case, I agree that it's absolutely imperative
for the standard to require this of a conforming implementation. It's going
to be the source of so many problems otherwise
On Fri, May 12, 2017 at 9:14 AM Hal Finkel <hfinkel at anl.gov> wrote:
>
> On 05/12/2017 11:00 AM, Scott Smith wrote:
>
> On Fri, May 12, 2017 at 12:52 AM, Bryce Lelbach <balelbach at
lbl.gov> wrote:
>
>> * I am concerned that nested parallel algorithms will prove to be a
>> big implementation burden for GPU and accelerator architectures.
>>
>
> Can't they fall back on serial execution?  I thought the executor is a
> hint, not a requirement (certainly the standard doesn't say it has to
> execute on multiple threads, just that it may).
>
>
>>
>> However, I want to gently urge caution and then take this thread on a
>> bit of a tangent, because I suspect this work will start leading
>> towards whatever goes into the libc++ C++17 parallel algorithms
>> implementation. Even if the intention is to have a separate,
>> stand-alone implementation in LLVM Support, I think that
>> implementation should share some interfaces and design philosophy with
>> whatever goes into libc++. I think there is a very important step that
>> needs to be taken before substantial work is done on libc++'s
parallel
>> algorithms.
>>
>
> I fear what you're describing is another 1.5 year long standards
> committee-like process, involving multiple stakeholders, discussions, etc.
>
> The background of how this came to be in LLVM is roughly:
> 1. I wanted to parallelize more work in LLDB, which has it's own
> non-nestable task execution model.  It involved creating individual tasks,
> rather than describing the iteration requested, so I put together my own
> parallel:for_each-like implementation just for LLDB.
> 2. It was suggested that rather than have each LLVM subproject implement
> its own framework, that it should instead be put into LLVM proper.  Zachary
> volunteered to do that, taking code from LLD and pulling it into LLVM.
> 3. It was then suggested that the interface should look more like the
> C++17 standard, presumably to make it easier to transition to the standard
> library and drop LLVM's own implementation once the time was right.
> 4. Back to LLDB, I want to make more code use for_each, but that code may
> itself call for_each, so in order to avoid creating Yet Another parallelism
> model, I want to make sure LLVM's for_each supports nested calling.
>
> As it is, we have a real use case today for this behavior, but not the
> resources/time to invest in coming up with defining how a shared library
> interface should look, separate from the C++17 parallelism interface, just
> so that libc++ may (or may not) pick it up somewhere down the line.
>
> IMO it makes more sense to continue with the separate implementation of
> "kinda mostly C++17 parallelism" with minimal
changes/improvements as
> necessary inside LLVM, and then switch to libc++/libstdc++/etc standard
> implementation later once those interfaces are implemented and pervasive
> across all the architectures that LLVM needs to work on.  Otherwise, we
> hold up progress in LLVM/LLDB today.
>
>
> I agree. I've chatted a couple of times with Marshall about the design
for
> parallel algorithms in libc++. I think that we have a reasonable idea of
> what we'd like to do there, at least in some general sense. I'd not
hold up
> this work on a libc++-appropriate implementation. Having the use case,
> however, is definitely valuable.
>
>
>  -Hal
>
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170512/c58d9f79/attachment.html>

On 05/12/2017 11:19 AM, Zachary Turner wrote:
> Even without a concrete use case, I agree that it's absolutely 
> imperative for the standard to require this of a conforming 
> implementation. It's going to be the source of so many problems
otherwise
I agree that it should work in some sense, but I meant that having the 
use case against which we can evaluate different implementation 
strategies is important.

  -Hal
> On Fri, May 12, 2017 at 9:14 AM Hal Finkel <hfinkel at anl.gov 
> <mailto:hfinkel at anl.gov>> wrote:
>
>
>     On 05/12/2017 11:00 AM, Scott Smith wrote:
>>     On Fri, May 12, 2017 at 12:52 AM, Bryce Lelbach
>>     <balelbach at lbl.gov <mailto:balelbach at lbl.gov>>
wrote:
>>
>>         * I am concerned that nested parallel algorithms will prove
>>         to be a
>>         big implementation burden for GPU and accelerator
architectures.
>>
>>
>>     Can't they fall back on serial execution?  I thought the
executor
>>     is a hint, not a requirement (certainly the standard doesn't
say
>>     it has to execute on multiple threads, just that it may).
>>
>>
>>         However, I want to gently urge caution and then take this
>>         thread on a
>>         bit of a tangent, because I suspect this work will start
leading
>>         towards whatever goes into the libc++ C++17 parallel algorithms
>>         implementation. Even if the intention is to have a separate,
>>         stand-alone implementation in LLVM Support, I think that
>>         implementation should share some interfaces and design
>>         philosophy with
>>         whatever goes into libc++. I think there is a very important
>>         step that
>>         needs to be taken before substantial work is done on
libc++'s
>>         parallel
>>         algorithms.
>>
>>
>>     I fear what you're describing is another 1.5 year long
standards
>>     committee-like process, involving multiple stakeholders,
>>     discussions, etc.
>>
>>     The background of how this came to be in LLVM is roughly:
>>     1. I wanted to parallelize more work in LLDB, which has it's
own
>>     non-nestable task execution model.  It involved creating
>>     individual tasks, rather than describing the iteration requested,
>>     so I put together my own parallel:for_each-like implementation
>>     just for LLDB.
>>     2. It was suggested that rather than have each LLVM subproject
>>     implement its own framework, that it should instead be put into
>>     LLVM proper. Zachary volunteered to do that, taking code from LLD
>>     and pulling it into LLVM.
>>     3. It was then suggested that the interface should look more like
>>     the C++17 standard, presumably to make it easier to transition to
>>     the standard library and drop LLVM's own implementation once
the
>>     time was right.
>>     4. Back to LLDB, I want to make more code use for_each, but that
>>     code may itself call for_each, so in order to avoid creating Yet
>>     Another parallelism model, I want to make sure LLVM's for_each
>>     supports nested calling.
>>
>>     As it is, we have a real use case today for this behavior, but
>>     not the resources/time to invest in coming up with defining how a
>>     shared library interface should look, separate from the C++17
>>     parallelism interface, just so that libc++ may (or may not) pick
>>     it up somewhere down the line.
>>
>>     IMO it makes more sense to continue with the separate
>>     implementation of "kinda mostly C++17 parallelism" with
minimal
>>     changes/improvements as necessary inside LLVM, and then switch to
>>     libc++/libstdc++/etc standard implementation later once those
>>     interfaces are implemented and pervasive across all the
>>     architectures that LLVM needs to work on.  Otherwise, we hold up
>>     progress in LLVM/LLDB today.
>
>     I agree. I've chatted a couple of times with Marshall about the
>     design for parallel algorithms in libc++. I think that we have a
>     reasonable idea of what we'd like to do there, at least in some
>     general sense. I'd not hold up this work on a libc++-appropriate
>     implementation. Having the use case, however, is definitely valuable.
>
>
>      -Hal
>
>     -- 
>     Hal Finkel
>     Lead, Compiler Technology and Programming Languages
>     Leadership Computing Facility
>     Argonne National Laboratory
>
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170512/0f680c3e/attachment.html>

On Fri, May 12, 2017 at 9:19 AM, Zachary Turner <zturner at google.com>
wrote:
> Even without a concrete use case, I agree that it's absolutely
imperative
> for the standard to require this of a conforming implementation. It's
going
> to be the source of so many problems otherwise
To confirm - what you'd like is clarification in the standard that
recursive parallelism is supported?

I think this is feasible; I'd suggest a non-normative note. I could
write a short committee paper on this (targeting C++20) for the next
meeting.

-- 
Bryce Adelstein Lelbach aka wash
Lawrence Berkeley National Laboratory
ISO C++ Committee Member
CppCon and C++Now Program Chair

Compiler ICE Hunter
--

Yes, I would hate for some library implementer to either interpret the
standard differently or simply not consider the issue of recursive
parallelism at all and end up with an implementation that doesn't support
it (not that unlikely considering it went 1.5 years through committee as
you said and the topic never came up).


On Wed, May 17, 2017 at 7:25 AM Bryce Lelbach <balelbach at lbl.gov>
wrote:
> On Fri, May 12, 2017 at 9:19 AM, Zachary Turner <zturner at
google.com>
> wrote:
> > Even without a concrete use case, I agree that it's absolutely
imperative
> > for the standard to require this of a conforming implementation.
It's
> going
> > to be the source of so many problems otherwise
>
> To confirm - what you'd like is clarification in the standard that
> recursive parallelism is supported?
>
> I think this is feasible; I'd suggest a non-normative note. I could
> write a short committee paper on this (targeting C++20) for the next
> meeting.
>
> --
> Bryce Adelstein Lelbach aka wash
> Lawrence Berkeley National Laboratory
> ISO C++ Committee Member
> CppCon and C++Now Program Chair
>
> Compiler ICE Hunter
> --
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170517/02ac38e9/attachment-0001.html>