Q: Where to handle continuous global address space?

[devreal]

After looking at the implementations of dash::copy today, I noticed a major flaw in the current implementation. In a nutshell, this is what dash::copy(T*, T*, GlobOutputIter) does:

1. memcpy the local portion of the transfer
2. put the preceeding elements
3. put the succeeding elements

Now, this will work fine for up to 3 units. However, experience from the last couple of years dictates that there well might be more than 3 units in the future so whenever a user tries to copy a local vector into parts of a dash::Array spanning >=4 units a unicorn will die a gruel death.

My guess is that DASH assumes that DART is aware of the continuous address space, i.e., a gptr is just the start of an arbitrary region that can potentially span over multiple units. The bad news is that DART communication operations are totally agnostic of this atm so the higher levels have to make sure not to write out-of-bounds of a single unit referenced in a gptr. In essence, #398 addresses this problem for dash::transform.

We could, however, give DART the notion of a continuous address space and let it handle multi-unit puts and gets rather easily. DART has the information on the size of each allocation on the individual units available and could thus nicely overlap remote transfers and (node-)local memcpys. It would also be a little more efficient since the meta-data queries would have to be done once instead of once for every individual target unit.

While I think this would be a worthwhile addition to DART, it also alters the semantics of it, shifting away from being a slim wrapper around MPI. But maybe this is how DASH already expects it to behave? The alternative would be to adapt dash::copy to handle these cases (not sure what other DASH features are affected).

Please comment.

[fuchsto]

Yes, local-to-global copy is an incomplete implementation, there are "known limitations" I didn't address so far because some secondary considerations are not resolved, yet.

On DART and iteration space:
We had a talk (and quick agreement) in Munich about this.
In brief: No, DART should not define / understand concepts of iteration- and index space.
Trivial cases like bucket traversal are an evil trap ("hey, it's easy, actually!") that distract from fundamental conceptional deal-breakers.

I try to keep it non-formalese and readable: DART has no concept of index sets, ranges, or iteration space. You could add it, but that is re-implementing C++ then (an entertaining, yet fruitless endeavour), and some parts of DASH (Patterns, mostly).

So why not just implement contiguous ("continuous" refers to the time domain) address ranges?
Because these are just a special case of the iterator concept that will differ from semantics expected by many Containers. If DART pre-defines iteration, it also has to respect the index set and partitioning traits used by the owning DASH-Container. If these differ, you will get lots of nasty calls, at 4 am, in foreign, aggressive tongues (think Bavarian).

[devreal]

Yes, local-to-global copy is an incomplete implementation, there are "known limitations" I didn't address so far because some secondary considerations are not resolved, yet.

I guess they are known to you but they are not documented. Not the first time something is supposed to work except for this and that corner case surprise...

In brief: No, DART should not define / understand concepts of iteration- and index space.

Well, this is not about the iteration space of containers or patterns. This is about the underlying global address space, just like a memcpy has no concept of iteration spaces in C/C++. Still, a memcpy can be used to cover the full range of an allocation, given a unit-stride and contiguous ranges. Whenever possible, std::copy will fall-back to such a low-level implementation (in that case memmove since overlapping ranges have to be supported, which I don't see us doing). DASH may do whatever it wants to with it. Right now, only unit-stride contiguous ranges are (claimed to be) supported by dash::copy anyway, afaics.

In any case, I would really like to see this fixed. I don't know what the current state is since I am not in the Munich-loop. However, we should not even dare to release such a partial implementation.

[rkowalewski]

Well, this is not about the iteration space of containers or patterns. This is about the underlying global address space, just like a memcpy has no concept of iteration spaces in C/C++. Still, a memcpy can be used to cover the full range of an allocation, given a unit-stride and contiguous ranges.

As pointed out by @fuchsto we had a talk in Munich couple of weeks ago. And we made some progress regarding global address spaces in #345 with a more detail discussion in #333. The memory concept is still in work. However, I think this covers the concept of the global memory range and copy from/into contiguous global adress ranges should work here. If not, what aspects are missing?

Whenever possible, std::copy will fall-back to such a low-level implementation (in that case memmove since overlapping ranges have to be supported, which I don't see us doing).

No, std::copy does not support overlapping ranges. The standard states:
"The behavior is undefined if d_first is within the range [first, last). Use std::copy_backward instead." --> So it is another algorithm and I see no reason why we cannot support it.

DASH may do whatever it wants to with it. Right now, only unit-stride contiguous ranges are (claimed to be) supported by dash::copy anyway, afaics.

I agree we have to make progress here. Rangse should help us to escape from this dilemma.

[devreal]

No, std::copy does not support overlapping ranges. The standard states:

"The behavior is undefined if d_first is within the range [first, last). Use std::copy_backward instead."

--> So it is another algorithm and I see no reason why we cannot support it.

Read carefully here! The quote already states that std::copy supports overlapping ranges: only d_first (the first output element) may not be in [first, last) but otherwise the range may overlap. And if you look at implementations of std::copy you will see memmove being used where possible.

I agree we have to make progress here. Rangse should help us to escape from this dilemma.

Well, let's see what comes out of that. It's severely frustrating to see things crumble in so many places whenever I touch them, not knowing whether this is a bug, a known limitation or work in progress. I guess I should spend less time on trying to fix other people's codes...

[rkowalewski]

Read carefully here! The quote already states that std::copy supports overlapping ranges: only d_first (the first output element) may not be in [first, last) but otherwise the range may overlap. And if you look at implementations of std::copy you will see memmove being used where possible.

You are right. We may overlap coming from the left-hand side but not the right-hand side. The conditions are reversed in copy_backward which is obvious. And this is certainly a bug in the DASH counterpart. So let us document this restriction and fix it in a separate issue. Applying the memmove approach in global address ranges even if the source and target ranges do not overlap will significantly impact the performance. So we should not simply follow the libstdc++ approach.

Appart from that, is this a blocker right now? I agree, it is a correctness problem and we are not compliant to the C++ standard but I see it as a special case which we can document.

Moreover, we should focus on the essential question of this issue. Is there still something which is conceptually not covered in the memory space concept?