I can certainly create an issue for this. However, there is one bit of
subtlety which makes things a bit more interesting, so I figure I'll give
it a bit more thought and try to write something up this weekend.
One tricky bit is that the simplest motivating examples, e.g.:
typedef struct {
uint32 account;
int32 delta_cents;
} acct_delta_t;
// for compactness, bounds checking omitted
void apply_deltas(uniform int32 balances[], uniform acct_delta_t deltas[],
uniform int num_deltas)
{
foreach (i = 0 ... num_deltas) {
uint32 acct = deltas[i].account;
int32 cents = deltas[i].delta_cents;
balances[acct] += cents;
}
}
(which will obviously get the wrong answer if two instances in one gang
gather, add, and scatter, one of those scatters will win and the balance
will not come out correct. Really, this is just a class of mutual exclusion
problem that is actually *much* simpler than the traditional forms of these
problems because the gang advances in lock step so we *can* use something
like *vpconflictd* to check in advance).
The above example is the simplest case imaginable. However, you could
easily imagine a closely related form of this problem (which is much closer
to real-world) where your transactions look like this instead:
typedef struct {
uint32 from_account;
uint32 to_account;
uint32 cents;
} fancy_acct_delta_t;
where you'd need to check that no two transactions in your batch conflict
with one another in _either_ account number... This isn't hard for a human
to do with some thought or for a compiler to construct algebraically but of
course it is possible to get into a situation where the non-trivial cost of
the conflict detection may suggest a different approach altogether (e.g.
hashing all incoming items into N separate queues so you know a priori that
you can grab the head item off each queue and know it will not conflict,
though this carries the opportunity cost of needing to partition your
resources N ways and live with any uneven/adverserial hash abberations that
may leave some partitions underutilized and others full).
As for *vp2intersectd*, it seems like it ought to be useful for _something_
but just what hasn't come to mind yet. I expect once I get the opportunity
to play with it a bit more something may resolve itself.
Cheers,
-lars
On Tuesday, July 21, 2020 at 12:12:52 AM UTC-7, Dmitry Babokin wrote:
>
> Hi Lars,
>
> Thank you for a detailed motivating examples describing the need for
> conflict detection capability in the language!
>
> Currently there's no way to generate vpconflictd instruction in ISPC. I
> see two paths to generate it:
> (1) introduce a library function, which has semantic of vpconflitd/q and
> emulate it on the platforms that don't support it - as you suggested, or
> (2) introduce a generic way to call arbitrary intrinsics as proposed in
> https://github.com/ispc/ispc/issues/1803
>
> Given the importance of the instruction for many applications that you
> outlined and as you see value for emulating it, I would suggest going with
> a dedicated library function. I would say that your description of the
> problem even sounds like we are missing a special type of "foreach" loop,
> which would serialize conflicting iterations. If we get enough motivating
> examples and prove that we can implement it efficiently enough, I would
> support it as well.
>
> I can implement the library function pretty easily. Could you please file
> an issue for that?
>
> Also, if you can contribute an example (as a self sufficient program that
> we can distribute as part of our example set) of the algorithm, where this
> instruction is useful, what would be really cool. All the cases that you've
> described do make sense and sound very convincing, but I personally don't
> have experience with these kinds of algorithms. This also sounds like an
> interesting assignment for someone who is studying algorithms class.
>
> And one more question, do you see the use for VP2INTERSECTD instructions
> in these algorithms?
>
>
--
You received this message because you are subscribed to the Google Groups
"Intel SPMD Program Compiler Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/ispc-users/d0649109-30d2-46c3-aaf6-7aa1cb02af91o%40googlegroups.com.
