Channels ▼
RSS

Parallel

Eliminate False Sharing


From Zero to Hero: The Little Parallel Counter That Could

The simplest way to fix the problem is simply to have each p-th worker increment its own local variable, and only at the end write its final tally to result[p]. It's an amazingly small change to the code:


// Example 2: Simple parallel version
// (de-flawed using a local variable)
//
int result[P];

// Each of P parallel workers processes 1/P-th
// of the data; the p-th worker records its
// partial count in result[p]
for( int p = 0; p < P; ++p )
   pool.run( [&,p] {
   <font color="#FF0000">int count = 0;</font>
   int chunkSize = DIM/P + 1;
   int myStart = p * chunkSize;
   int myEnd = min( myStart+chunkSize, DIM );
   for( int i = myStart; i < myEnd; ++i )
      for( int j = 0; j < DIM; ++j )
        if( matrix[i*DIM + j] % 2 != 0 )
          <font color="#FF0000">++count;
   result[p] = count;</font>
} );
// … etc. as before …

Could such a small change really make a big difference in scalability? Let's measure and find out. When I ran the code in Example 2 with values of P from 1 to 24 (on a 24-core machine), I got the results shown in Figure 4.

Figure 4: Removing cache line contention on the result array takes us from zero scaling to linear scaling, up to the available hardware parallelism (test run on a 24-core machine).

The amended code's scalability isn't just better -- it's perfect scaling, linear in the number of processors. Figure 5 shows the work per CPU core with P = 24; each core's work was complete so fast that it didn't manage to peg the core long enough to fill a whole CPU monitor polling interval.

Figure 5: Running Example 2 with P = 24 — now that's more like it, the kind of workload distribution we want to see.

Now that we've confirmed the culprit in Example 1 was memory contention due to false sharing on the result array, this helps clear up the mystery of why the cores appeared pegged in the CPU monitor (Figure 3) when they were actually not doing as much work: Many CPU monitors, like this one, count the time a core is waiting for cache and memory as part of its "busy" time. After all, the core is executing an instruction; it just happens to be an expensive memory fetch instruction. That explains why a core can appear to be fully utilized when it's actually only doing useful computation work a fraction of the time; it's spending the rest of its time just waiting for memory.

We've also cleared up the mystery of why some workers finished faster than others in Figure 3: The ones that took longer were the ones that were experiencing more contention because their counters happened to be on cache lines containing a greater number of other workers' counters. Workers whose counters happened to be on less-popular cache lines had to wait less and so ran faster.

Our small code change has taken us from zero scaling to perfect scaling: Now that's a zero-to-hero technique worth knowing about.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video