C++ Logo

sg14

Advanced search

Re: [SG14] SG14 Features

From: Jeremy Ong <jeremycong_at_[hidden]>
Date: Wed, 11 Dec 2019 14:13:25 -0700
This is a bit out of left field, but I'd be interested in a data structure
adapter which packs its elements based on Morton codes (or some other
space-filling Hilbert curve, see https://en.wikipedia.org/wiki/Z-order_curve
).

The idea is that there are a good chunk of algorithms that operate on
densely packed structures where the likelihood of accessing neighboring
elements is high. Examples I can think of off the top of my head:
1. Simulating a fluid or crowd motion
2. Any finite element model (e.g. simulating cloth)
3. Lattice computation (e.g. Lattice quantum chromodynamics)
4. Sampling neighboring points in an image, possibly for the purposes of
compression or filtering
5. A painting application (e.g. flood fill, drawing a continuous
stroke/curve to a raster).
6. Accelerating a matrix multiplication by parallelizing the computation on
minors.

The last application perhaps best captures the "gist" of why this is
useful. If I want to parallelize my computation, I need to partition the
data in contiguous chunks. Otherwise, each thread or worker will ultimately
be accessing essentially random addresses within the data range. Aside from
memory coherency issues, this would cause issues with false sharing if my
data is not padded to the size of a cache line.

This technique is widely used already in GPUs. For example, when uploading
a texture for sampling later on, if the texture isn't already
block-compressed, the GPU will swizzle the texture such that sampling is
efficient. For the purposes of bilinear filtering, neighboring pixels will
fetch 4 texels in the texture that will all likely reside in the texture
cache. If not, they generally can be populated in the cache with a single
cache-line load (as opposed to four).

This could be implemented in user-land (e.g. `std::nd_array<typename T,
size_t...>` ignore the bad name for the time-being) in an arbitrary number
of dimensions. The tradeoff is that single element access will require
several cycles to compute the address (a few bit operations).

Does this warrant inclusion in the standard? This is actually something not
100% clear to me but I'd be interested in other people's thoughts.

On Wed, Dec 11, 2019 at 1:45 PM Matthew Butler via SG14 <
sg14_at_[hidden]> wrote:

> I would be interested in hearing everyone's thoughts on Herbceptions.
>
> Also Colony and Ring Buffer would be useful adds.
>
> On Wed, Dec 11, 2019 at 1:41 PM Tjernstrom, Staffan via SG14 <
> sg14_at_[hidden]> wrote:
>
>> Today's call discussed informally which features we would like to pursue
>> as a group for '23 and beyond. Many suggestions appeared both in the chat
>> as well as in the call itself.
>>
>>
>>
>> Feel free to use this thread as a collection point that we can circle
>> back around to and gather inspiration from.
>>
>>
>>
>> Kind Rgds
>>
>> Staffan Tj.
>>
>>
>>
>> ------------------------------
>>
>> IMPORTANT: The information contained in this email and/or its attachments
>> is confidential. If you are not the intended recipient, please notify the
>> sender immediately by reply and immediately delete this message and all its
>> attachments. Any review, use, reproduction, disclosure or dissemination of
>> this message or any attachment by an unintended recipient is strictly
>> prohibited. Neither this message nor any attachment is intended as or
>> should be construed as an offer, solicitation or recommendation to buy or
>> sell any security or other financial instrument. Neither the sender, his or
>> her employer nor any of their respective affiliates makes any warranties as
>> to the completeness or accuracy of any of the information contained herein
>> or that this message or any of its attachments is free of viruses.
>> _______________________________________________
>> SG14 mailing list
>> SG14_at_[hidden]
>> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>>
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>

Received on 2019-12-11 15:16:40