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.