Hi all,
Correlation functions are another example where such capability in ispc
would be fantastic. Correlation functions require computing pairwise
separations (up to some Rmax) and then computing a histogram of these
separations. Correlation functions are widely used in Astronomy (100k+
references in papers). A trivial code for a correlation function is:
for(int64_t i=0;i<Npart;i++) {
for(int64_t j=0;j<Npart;j++) {
const double dx = xpos[i] - xpos[j];
const double dy = ypos[i] - ypos[j];
const double dz = zpos[i] - zpos[j];
const double r2 = dx*dx + dy*dy + dz*dz;
if(r2 < sqr_rmin || r2 >= sqr_rmax) continue;
const double r = sqrt(r2);
const int index = convert_sep_to_histogram_index(r);
histogram[index]++;
}
}
where, the convert_sep_to_histogram function scales "r" into [0, nbins-1].
The pairwise computation can be done with SIMD but the histogram update
needs to be serialised in general. If ispc adds the equivalent of the
vpconflict instruction that would be great!
Here is a self-contained simple correlation function repo (with tests):
https://github.com/manodeep/simple-corr
Cheers,
Manodeep
On Thursday, July 23, 2020 at 1:03:49 AM UTC+10 [email protected] wrote:
> Yes, that's essentially it. I suspect that most people will just use the
> general conflict mechanism any time they have a pattern where a
> received/computed/derived field selects which data are in play for any
> given lane dynamically at runtime. People who have some other oddball use
> for that function could still use the intrinsic (which would emit the
> special instruction on platforms that had it, or an equivalent sequence
> otherwise).
>
> -lars
>
> -lars
>
> On Tue, Jul 21, 2020, 22:02 Dmitry Babokin <[email protected]> wrote:
>
>> Ok, so I read it as:
>> (1) we may want have more general mechanism to deal with conflicts.
>> (2) for *vpconflictd* instruction the question if it needs to be exposed
>> as a library function (available on all platforms with fall-back
>> implementation) or as an intrinsic, which is available only for AVX512
>> instruction set.
>>
>> Dmitry.
>>
>> On Tue, Jul 21, 2020 at 8:58 PM Lars Friend <[email protected]> wrote:
>>
>>> 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
>>>
>>> <https://groups.google.com/d/msgid/ispc-users/d0649109-30d2-46c3-aaf6-7aa1cb02af91o%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>> --
>> 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/CACRFwuhCewxpsoaeq59ArNxQvwauKb-%3D9USNc0jZu_hgSYD0ww%40mail.gmail.com
>>
>> <https://groups.google.com/d/msgid/ispc-users/CACRFwuhCewxpsoaeq59ArNxQvwauKb-%3D9USNc0jZu_hgSYD0ww%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
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/da717b93-c674-4e02-bcd7-2b2693115773n%40googlegroups.com.
