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

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170512/18f7b255/attachment.html>

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

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

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>

Apologies for my delayed reply - I've been on travel the past few days.

On Fri, May 12, 2017 at 9:00 AM, Scott Smith
<scott.smith at purestorage.com> wrote:
> 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).
Yes. However, it is a quality-of-implementation issue.
> I fear what you're describing is another 1.5 year long standards
> committee-like process, involving multiple stakeholders, discussions, etc.
Yep. I don't think it will take quite that long, but it's not a trivial
task.
> 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.
Ah, alright. I think I understand your requirements a bit better now.
> 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, this sounds quite sensible to me.

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

Compiler ICE Hunter
--

On Fri, May 12, 2017 at 9:14 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
> 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.

Sounds good to me. This might be a good time to start on this sort of
thing, given that there's interest and internal use cases in the LLVM
ecosystem.



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

Compiler ICE Hunter
--