2
$\begingroup$

This is a homework problem that I have

In a multicore system, you are running the code on the right on each core, and it suffers from false sharing. You can assume t_id is set to a unique thread identifier (e.g. 0-15). How could you change the code to reduce false sharing?

for (int i=0; i<N; i++)
    totals[t_id] += a[i];

What I'm having trouble with is seeing where the false sharing is occurring. It says state t_id is set to a unique thread identifier, so doesn't that mean there's only 1 thread that's accessing the data here?

We only briefly went over false sharing, but from what I've learned false sharing occurs when a cache miss occurs because the data was invalidated previously due to an "irrelevant" data being written/read from a different cache. But if the thread is the same, then doesn't that mean it's the same cache being used to write/read? How would false sharing occur here?

$\endgroup$

2 Answers 2

4
$\begingroup$

The false sharing is happening in the totals memory block.

The smallest unit of cache is a cache line. On standard x86 and ARM systems, a cache line is 64 bytes. On some PowerPC archs, the cache line is 128 or even 256 bytes. Reading from main memory into the cache is done one cache line at a time, and cache invalidation is done one cache line at a time.

Imagine each element of totals is a uint8. 64 elements of totals fit in one cache line. Every time += is called, the 64 byte cache line containing totals[tid] is read from and written to. That means every core is constantly invalidating that cache line, and the ensuing coordination, “false sharing”, is costly and unnecessary.

You could fix this while maintaining similar code structure by

  • Padding each element of totals so that it takes up a whole cache line

  • If totals has enough elements, offsetting your access so that multiple threads tend not to manipulate the same cache line. Ex: index by (tid * 64) % n_elements

$\endgroup$
4
$\begingroup$

I upvoted the post explaining why the false sharing happens. But in this specific case there is also a trivial change to avoid 99.9% of the false sharing: Instead of

for (int i=0; i<N; i++)
    totals[t_id] += a[i];

you write

sum = totals[t_id];
for (int i=0; i<N; i++)
    sum += a[i];
totals[t_id] = sum;

So instead of N times false sharing it only happens once. N times improvement. This will also be a huge improvement if there is only one thread running.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.