False cache line sharing

Aligning data to avoid false sharing

Because false cache line sharing is partially due to the layout of the data, one step in avoiding it is to adjust the layout. Typically, these adjustments are made by aligning data on cache line boundaries. (Aligning arrays generally improves performance; however, it can occasionally decrease performance.) The second step in avoiding false cache line sharing (which is covered in the section, “Distributing iterations on cache line boundaries”) is to adjust the distribution of loop iterations.

Aligning multidimensional arrays on cache line boundaries

Multidimensional arrays can also be aligned on cache line boundaries. Recall that in the example from the beginning of the section:

REAL*4 B(100,100) DO I = 1, 100 DO J = 1, 100 B(I,J) = ...B(I,J-1)... ENDDO ENDDO

we assumed B(1,1) starts on a cache line boundary. However, because the iteration distribution caused alignment on cache line boundaries to vary from dimension to dimension, performance suffered. Choose a value x for the leftmost dimension (rightmost in C and C++) in arrays so that x times the data size (in bytes) is an integral multiple of the CTIcache line size. (The code that follows gives an example of this idea.) Using such a value aligns data on CTIcache line boundaries at the same index points in all dimensions.

On X2000 servers, both the processor cache lines and the CTIcache lines are 32 bytes. (V2200 servers and nonscalable SMPs do not have CTIcaches.)

For general use, try to align everything on 32-byte boundaries for V2200 and X2000 servers. This alignment will help to eliminate false cache line sharing between processor caches and also between CTIcaches where the penalty for false sharing is even higher. Where possible, try to parameterize cache line size in anticipation of future systems that might have different cache line sizes.

Changing the example so that array B is aligned and padded (to 64 bytes), the leftmost dimension is now 112 instead of 100. (See the modified example below.) The number 112 is the smallest value x greater than 100 such that x times the data size (4 bytes) is an integral multiple of 64.

REAL*4 B(112,100) COMMON /ALIGNED/ B DO I = 1, 100 DO J = 1, 100 B(I,J) = ...B(I,J-1)... ENDDO ENDDO

Note that loop limits have not changed. Placing B in a COMMON block has forced B(1,1) onto a cache line boundary (64 bytes), and changing the first dimension to 112 assures that B(1,2), B(1,3), ..., B(1,100) all start on cache line boundaries. Table 8-3 “Restructured mapping of array to cache lines” shows how the restructured array maps to (processor) cache lines.

The next section, "“Distributing iterations on cache line boundaries”," explains how to make the compiler distribute iterations so that threads work on whole cache lines.

Table 8-3 Restructured mapping of array to cache lines

# 1, 1 #	# 1, 2 #	# 1, 3 #	# 1, 4 #	. . .	# 1, 99 #	# 1, 100 #
2, 1	2, 2	2, 3	2, 4	. . .	2, 99	2, 100
3, 1	3, 2	3, 3	3, 4	. . .	3, 99	3, 100
4, 1	4, 2	4, 3	4, 4	. . .	4, 99	4, 100
5, 1	5, 2	5, 3	5, 4	. . .	5, 99	5, 100
6, 1	6, 2	6, 3	6, 4	. . .	6, 99	6, 100
7, 1	7, 2	7, 3	7, 4	. . .	7, 99	7, 100
8, 1	8, 2	8, 3	8, 4	. . .	8, 99	8, 100
# 9, 1 #	# 9, 2 #	# 9, 3#	# 9, 4 #	. . .	# 9, 99#	# 9, 100 #
10, 1	10, 2	10, 3	10, 4	. . .	10, 99	10, 100
11, 1	11, 2	11, 3	11, 4	. . .	11, 99	11, 100
12, 1	12, 2	12, 3	12, 4	. . .	12, 99	12, 100
. . .	. . .	. . .	. . .	. . .	. . .	. . .
# 97, 1 #	# 97, 2 #	# 97, 3 #	# 97, 4 #	. . .	# 97, 99 #	# 97,100 #
98, 1	98, 2	98, 3	98, 4	. . .	98, 99	98,100
99, 1	99, 2	99, 3	99, 4	. . .	99, 99	99,100
100, 1	100, 2	100, 3	100, 4	. . .	100, 99	100,100
101, 1	101, 2	101, 3	101, 4	. . .	101, 99	101,101
102, 1	102, 2	102, 3	102, 4	. . .	102, 99	102,102
103, 1	103, 2	103, 3	103, 4	. . .	103, 99	103,103
104, 1	104, 2	104, 3	104, 4	. . .	104, 99	104,104
# 105, 1 #	# 105, 2 #	# 105, 3 #	# 105, 4 #	. . .	# 105, 99 #	# 105,105 #
106, 1	106, 2	106, 3	106, 4	. . .	106, 99	106,106
107, 1	107, 2	107, 3	107, 4	. . .	107, 99	107,107
108, 1	108, 2	108, 3	108, 4	. . .	108, 99	108,108
109, 1	109, 2	109, 3	109, 4	. . .	109, 99	109,109
110, 1	110, 2	110, 3	110, 4	. . .	110, 99	110,110
111, 1	111, 2	111, 3	111, 4	. . .	111, 99	111,112
112, 1	112, 2	112, 3	112, 4	. . .	112, 99	112,112

 

Array entries surrounded by hashmarks (#) are on cache line boundaries.

Distributing iterations on cache line boundaries

Recall that the default iteration distribution causes thread 0 to work on iterations 1-12 and thread 1 to work on iterations 13-25, and so on. Even though the cache lines are aligned across the columns of the array (see Table 8-3 “Restructured mapping of array to cache lines”), we still need to change the iteration distribution. Use CHUNK_SIZE to change the distribution:

      REAL*4 B(112,100) 
      COMMON /ALIGNED/ B
C$DIR PREFER_PARALLEL (CHUNK_SIZE=16) 
      DO I = 1, 100 
        DO J = 1, 100 
          B(I,J) = ...B(I,J-1)... 
        ENDDO 
      ENDDO

You must specify a constant CHUNK_SIZE. However, the ideal would be to distribute work so that all but one thread works on the same number of whole cache lines, and the remaining thread works on any partial cache line. For example, given:

the ideal CHUNK_SIZE would be:

CHUNK_SIZE = LSIZE * (1 + ( (1 + (NITS - 1) / LSIZE ) - 1 )/NTHDS)

For the code above, these numbers are:

CHUNK_SIZE = 8 * (1 + ( (1 + (100 - 1) / 8 ) - 1) / 8) 
           = 8 * (1 + ( (1 +  12           ) - 1) / 8) 
           = 8 * (1 + ( 12                      ) / 8)
           = 8 * (1 + 1                              ) 
           = 16

CHUNK_SIZE = 16 causes threads 0, 1, ..., 6 to execute iterations 1-16, 17-32, ..., 81-96, respectively. Thread 7 executes iterations 97-100. As a result there is no false cache line sharing, and parallel performance is greatly improved.

While you cannot specify the ideal CHUNK_SIZE for every loop, using

CHUNK_SIZE = x

where x times the data size (in bytes) is an integral multiple of 32 will eliminate false cache line sharing if the two conditions below are met:

The number 32 is used because the CTIcache line size is 32 bytes for X2000 servers.

Thread-specific array elements

Sometimes a parallel loop has each thread update a unique element of a shared array which is further processed by thread 0 outside the loop.

Consider the following Fortran example:

      REAL*4 S(8) 
C$DIR LOOP_PARALLEL
      DO I = 1, N 
        .
        .
        .
        S(MY_THREAD()+1) = ... ! EACH THREAD ASSIGNS ONE ELEMENT OF S
        .
        .
        .
      ENDDO 
C$DIR NO_PARALLEL 
      DO J = 1, NUM_THREADS()
        = ...S(J)              ! THREAD 0 POST-PROCESSES S
      ENDDO

The problem here is that potentially all the elements of S are in a single cache line, so the assignments cause false sharing. One approach is to change the code to force the unique elements into different cache lines, as indicated below:

      REAL*4 S(8,8)
C$DIR LOOP_PARALLEL 
      DO I = 1, N 
        .
        .
        .
        S(1,MY_THREAD()+1) = ... ! EACH THREAD ASSIGNS ONE ELEMENT OF S 
        .
        .
        .
      ENDDO 
C$DIR NO_PARALLEL 
      DO J = 1, NUM_THREADS()
        = ...S(1,J)             ! THREAD 0 POST-PROCESSES S 
      ENDDO

For multihypernode applications on X2000 servers, the dimensions should be S(8,number_of_threads) because the CTIcache line size is 32 bytes, and the data size is 4 bytes.

Scalars sharing a cache line

Sometimes parallel tasks will assign unique scalar variables that are in the same cache line, as in the following example:

      COMMON /RESULTS/ SUM, PRODUCT 
C$DIR BEGIN_TASKS 
      DO I = 1, N 
        .
        .
        .
        SUM = SUM + ... 
        .
        .
        .
      ENDDO
C$DIR NEXT_TASK 
      DO J = 1, M 
        .
        .
        .
        PRODUCT = PRODUCT * ... 
        .
        .
        .
      ENDDO 
C$DIR END_TASKS

This problem is similar to the example in the previous section ("“Thread-specific array elements”"), and can be avoided by padding enough space between the two scalar variables so that the variables are in separate CTIcache lines:

COMMON /RESULTS/ SUM, PAD(7), PRODUCT

where PAD(7) represents 28 bytes—SUM and PAD(7) together take up 32 bytes, forcing PRODUCT into the next CTIcache line on multinode X2000 applications because the CTIcache lines are 32 bytes.

Working with unaligned arrays

The most common cache-thrashing complication using arrays and loops will be that arrays assigned within a loop are unaligned (and possibly unalignable) with each other. There are several possible causes for this:

Consider the following Fortran example:

COMMON /OKAY/ X(112,100) 
        ... 
CALL UNALIGNED (X(I,J)) 
        ... 
SUBROUTINE UNALIGNED (Y) 
REAL*4 Y(*)
    ! Y(1) PROBABLY NOT ON A CACHE LINE BOUNDARY

The address of Y(1) is unknown. However, if elements of Y are heavily assigned in this routine, it may be worthwhile to compute an alignment, given by the following formula:

LREM = LSIZE - ( ( MOD ( LOC(Y(1))-4, LSIZE*x) + 4) /x)

where

For this case, assume LSIZE is CTIcache line size (32 bytes on X2000 servers) in single precision words (8 words). Note that

( ( MOD ( LOC(Y(1))-4, LSIZE*4) + 4) /4)

returns a value in the set 1, 2, 3, ..., LSIZE, so LREM is in the range 0 to 7.

Then a loop such as:

DO I = 1, N 
  Y(I) = ... 
ENDDO

can be transformed to:

C$DIR NO_PARALLEL 
      DO I = 1, MIN (LREM, N) ! 0 <= LREM < 8
        Y(I) = ... 
      ENDDO
C$DIR PREFER_PARALLEL (CHUNK_SIZE = 16) 
      DO I = LREM+1, N
         ! Y(LREM+1) IS ON A CACHE LINE BOUNDARY 
        Y(I) = ... 
      ENDDO

The first loop takes care of elements from the first (if any) partial cache line of data. The second loop begins on a cache line boundary, and can be controlled with CHUNK_SIZE to avoid false sharing among the threads.

Working with dependences

Data dependences in loops may prevent parallelization and prevent the elimination of false cache line sharing. If certain conditions are met, some performance gains can be achieved.

For example, consider the following code:

COMMON /ALIGNED / P(128,128), Q(128,128), R(128,128)
REAL*4 P, Q, R
DO J =  2, 128 
  DO I = 2, 127 
    P(I-1,J) = SQRT (P(I-1,J-1) + 1./3.) 
    Q(I  ,J) = SQRT (Q(I  ,J-1) + 1./3.) 
    R(I+1,J) = SQRT (R(I+1,J-1) + 1./3.) 
  ENDDO
ENDDO

Only the I loop can be parallelized. (Because of the loop-carried dependences in the J loop, it cannot be parallelized.) It is impossible to distribute the iterations such that there will be no false cache line sharing in the above loop. If all loops that refer to these arrays always use the same offsets (which is unlikely) then you could make dimension adjustments that would allow a better iteration distribution. For example, the following would work well for 8 threads:

      COMMON /ADJUSTED/ P(128,128), PAD1(15), Q(128,128),
     > PAD2(15), R(128,128)
 
      DO J =  2, 128
C$DIR   PREFER_PARALLEL (CHUNK_SIZE=16) 
        DO I = 2, 127 
          P(I-1,J) = SQRT (P(I-1,J-1) + 1./3.) 
          Q(I  ,J) = SQRT (Q(I  ,J-1) + 1./3.) 
          R(I+1,J) = SQRT (R(I+1,J-1) + 1./3.) 
        ENDDO 
      ENDDO

Padding 60 bytes before the declarations of both Q and R causes the P(1,J), Q(2,J), and R(3,J) to be aligned on 64-byte boundaries for all J. Combined with a CHUNK_SIZE of 16, this causes threads to assign data to unique whole cache lines.

Often in real-world code you will find a mix of all the above problems in some CPU-intensive loops. You will not be able to avoid all false cache line sharing, but by careful inspection of the problems and careful application of some of the workarounds shown here, you will usually be able to significantly enhance performance of your parallel loops.