Guarantee parallel_scan to use two passes

[masterleinad]

Currently, we only guarantee that parallel_scan calls the functor with is_final==true but not if it's called with is_final==false.
Note that all backends apart from Serial use a two-pass implementation. If the user can't know/rely on two passes, it's not possible to avoid repeating expensive calculations, i.e.

void (int i, int& chunk_start, bool is_final) {
  if (is_final) {
    if (is_relevant(i)) {
      result(chunk_start) = i;
      ++chunk_start;
    }
  } else {
    if (expensive_conditon(i)) {
      is_relevant(i) = true;
      ++chunk_start;
    }
  }
} 

doesn't work if there is only one pass. Instead, we would need to launch another kernel to evaluate expensive_condition beforehand so that we need to launch three kernels for most backends (one "expensive" one for parallel_for, and two "cheap" ones for parallel_scan). It appears that the benefit of avoiding one pass in the Serial backend might not be sufficient to justify not allowing caching results in the first parallel_scan pass.

[dalg24]

Does the documentation say anything about this? If the answer is "no we don't", does the doc include anything regarding guarantees with parallel_reduce or parallel_for (I understand parallel_scan is different).

It appears that the benefit of avoiding one pass in the Serial backend might not be sufficient to justify not allowing caching results in the first parallel_scan pass.

We will see about that. Some might not be really happy about the serial parallel scan taking a 2x slow down.

[masterleinad]

We will see about that. Some might not be really happy about the serial parallel scan taking a 2x slow down.

I'd be curious to hear under which circumstances users care about performance for the Serial backend that much.

[dalg24]

Arborx for instance…

…

On Tue, Mar 26, 2024 at 9:50 PM Daniel Arndt ***@***.***> wrote: We will see about that. Some might not be really happy about the serial parallel scan taking a 2x slow down. I'd be curious to hear under which circumstances users care about performance for the Serial backend that much. — Reply to this email directly, view it on GitHub <#6897 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AACIQERVS3ESJIQYNND2ANTY2FVKRAVCNFSM6AAAAABFHXGDHGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDAMRQGM2DGOBZGU> . You are receiving this because you commented.Message ID: ***@***.***>

[stanmoore1]

In general we want Kokkos Serial to have as low overhead as possible, isn't this why a serial backend exists? Otherwise why not just run OpenMP with 1 thread?

[masterleinad]

Otherwise why not just run OpenMP with 1 thread?

The Serial backend doesn't require any dependencies whereas all other backends do so it's a good fallback and starting point.

[stanmoore1]

Most systems have OpenMP support so I think the bar is pretty low. But my point is really that we want the Serial backend to be as close to zero overhead as possible. No atomic overhead, and no multiple loops in the parallel_scan is my desire.

[ajpowelsnl]

@stanmoore1 , @masterleinad , regarding "no atomic overhead"; as of Kokkos-4.3 , there's a new CMake keyword that might be useful for serial / host-only builds: Kokkos_ENABLE_ATOMICS_BYPASS