Re: [RFC] Proposal to contribute Intel’s implementation of C++17 parallel algorithms

[Pekka Jääskeläinen]

Hi,

I'm glad to see your PSTL implementation getting upstreamed, thanks! I only very
briefly browsed the code so far though.

On Wed, Nov 29, 2017 at 5:47 PM, Kukanov, Alexey
<Alexey.Kukanov@intel.com> wrote:
> I think it would be ideal if GCC offloading could be used as a backend for the implementation.
> We can adjust the backend API if that's needed to support different "executors".
> For start, I will study Pekka's presentation.

That presentation was given to get preliminary suggestions and
comments from the Cauldron
attendants before we even started the implementation work, so it might
not be very useful outside
the general background description / "problem statement".

After the Prague meeting, we've proceeded with our experiments on top
of Martin Jambor's direct HSA
offloading builtins and the path towards transparent heterogeneous
offloading of Parallel STL algorithms
seems clear now. We've some common std::transform offloading cases
running now through the
stack. This is experimental / POC code, and now it's time to start
thinking how to cleanly integrate
the heterogeneous offloading version of PSTL to libstdc++ and gcc code
base.  So your posting came
at a good time!

Some additional considerations in the heterogeneous offloading
scenario (where we assume shared
system memory across devices, but differing ISAs and disjoint
instruction address spaces), which
might affect the sharing of code with your implementation:

1) Offload granularity.

We want to offload larger entities, if possible, to reduce sync/kernel
launch overheads between
the co-processors and the host. Thus, not only offload individual
parallel loops inside an algorithm
implementation, but the whole algorithm.

2) Try to avoid indirect calls.

We want to avoid indirect calls to the user defined functions called
by the algorithms.

Function pointers are problematic in heterogeneous multi-ISA disjoint
imem address
space scenarios. Even if there was efficient support for "universal
function pointers",
the fact that we "online compile" kernels presents an optimization
opportunity: At
the kernel launch time we should know the underlying function's
address of the functor, so it's
useful to utilize the information when finalizing (compiling) the
kernel and convert to direct calls.
The resulting kernel's code can be more easily inlined and vectorized
across work-items for
SIMD ISAs, or just more efficiently "SPMD executed" on GPGPUs.

3) We cannot offload arbitrary functions.

There are restrictions on what we can compile to offloaded kernels.
E.g. the above function
pointer restriction; kernels calling user functions that do function
pointer calls (e.g. calls via
vtable) are not supported at this point. We can avoid the first level
indirect call to the functor
itself via kernel specialization, but the next level (if the user
function itself calls functions indirectly) is not
supported currently. Also kernels calling system (host) functions
(e.g. syscalls) are similarly
not supported. Nor are ones throwing exceptions, etc.

As it's likely to be the case for the foreseeable future that not all
host-supported functions
can be offloaded, a nice way to handle situations where offloading
does not work for a reason
or another, will be a silent fallback to a "homogeneous" version, e.g.
to your TBB-based host
execution. This way we can gradually increase the types of user functions we can
heterogeneous-offload over time and meanwhile enable offloading of the
currently supported
cases.


BTW regarding the C++ standard, I think it's currently not allowed to
just do heterogeneous
offloading even in case of unseq or par_unseq policies.  This is
because the user function implementations
might be target-specific and can assume these target specifics are
uniform across all the functions in
the program. I think the standard could use an additional Execution
Policy using which the programmer
can state that it's safe to also offload the algorithm call to other
ISAs than the one of the host CPU
(meaning it doesn't rely on sizeof, compile time detected endianness,
or other target specific info).


BR,
Pekka