誤ったキャッシュラインの共有

誤った共有を避けるためにデータを整列する

誤ったキャッシュラインの共有の原因の一部はデータのレイアウトにあるので、誤った共有を避けるための第 1 の方法はこのレイアウトを調整することになります。典型的な調整方法はデータをキャッシュラインの境界に整列することです。一般に、配列を整列するとパフォーマンスが向上します。しかし、場合によってはパフォーマンスが低下することもあります。

誤った共有を避けるための第 2 の方法はループ繰り返しの分散を調整することです。この方法の説明は「キャッシュラインの境界に繰り返しを分散する」にあります。

キャッシュラインの境界に繰り返しを分散する

デフォルトの繰り返しの分散によってスレッド 0 が繰り返し範囲 1〜12 で作動し、スレッド 1 が繰り返し範囲 13〜25 で作動する (スレッド 2、スレッド 3...) ということを思い出してください。キャッシュラインが配列の列に対して整列していても (表 14-2 「I ループのデフォルト分散」を参照してください)、依然として繰り返しの分散を変更する必要があります。 CHUNK_SIZE 属性を使用して、この分散を変更してください。

      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

定数のCHUNK_SIZE 属性を指定しなければなりません。しかし、作動を分散して、1 つ以外のすべてのスレッドが同じ数の全キャッシュラインで作動し、残りのスレッドがキャッシュラインのどの部分でも作動するように、作動を分散することが理想的です。たとえば、次のことを仮定します。

NITS = 繰り返し回数

NTHDS = スレッドの数

LSIZE = ワードで表した行サイズ (8 は 4 バイトデータ、4 は 8 バイトデータ、2 は 16 バイトデータをそれぞれ表します)

理想的なCHUNK_SIZE は次のとおりです。

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

前述のコードでは、これらの数値は次のようになります。

NITS = 100

LSIZE = 8 ( 4 バイトデータ用の V2250 の境界での整列)

NTHDS =8

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 によって、スレッド 0, 1, ..., 6 はそれぞれ繰り返し 1〜16, 17〜32, ..., 81〜96 を実行します。スレッド 7 は繰り返し 97〜100 を実行します。この結果、誤ったキャッシュラインの共有はなくなり、パラレルパフォーマンスが大幅に向上します。

すべてのループに理想的なCHUNK_SIZE を指定することはできません。式

CHUNK_SIZE = x

(データサイズ (バイト) のx 倍が 32 の整数倍) を使用して、誤ったキャッシュラインの共有を削除してください。これは次の 2 つの条件を満たしている場合のみ可能です。

数字 32 を使用する理由は、V2250 サーバー用のキャッシュラインのサイズが 32 バイトだからです。

スレッド固有の配列要素

パラレルループで各スレッドが共有配列の 1 つの要素を更新することがあります。この配列はループ外でスレッド 0 によって次の処理を受けます。

次の Fortran のコードを考えてみましょう。このコードでは誤った共有が起ります。

      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

このコードの問題は、S のすべての要素が単一のキャッシュラインに存在する可能性があるので、代入を行うと誤った共有が生じるということです。解決法の 1 つは、次のコードで示すように、このコードを変更して異なるキャッシュラインにそれぞれ 1 つの要素を強制的に入れることです。

      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

キャッシュラインを共有するスカラー

次のコードのように、パラレルタスクが、同一のキャッシュラインにある 1 つのスカラー変数に代入することがあります。

      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

不整列の配列を処理する

配列とループを使用する場合のキャッシュスラッシングの問題で一番多いのは、ループ内で代入される配列が互いに整列していないときに起こるものです。この原因としては、次のものが考えられます。

次の Fortran のコードを考えてみましょう。

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

Y(1) のアドレスはわかりません。しかし、Y の要素をこのルーチンで何度も代入している場合は、次の公式でデータの割り付け境界を計算してみる価値があります。

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

ここで

この場合、V2250 サーバー上のLSIZE は単精度ワード (8 ワード) で 32 バイトです。次のことに注意してください。

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

は 1, 2, 3, ..., LSIZE の集合の値を返すので、LREM の範囲は 0 から 7 までであるということです。

次に、

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

のようなループを次のように変換します。

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

最初のループでは、データの最初の (もしあれば) 部分のキャッシュラインからの要素を考慮しています。次のループはキャッシュラインの境界で始まり、CHUNK_SIZE で制御されているので、スレッド間の誤った 共有を避けることができます。

依存を処理する

ループでのデータ依存は、パラレル化を妨害し、誤ったキャッシュラインの共有の削除を妨害することがあります。このような場合、一定の条件を満たせばパフォーマンスが向上します。

例として、次のコードを考えてみましょう。

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

J ループ内のループ搬送依存が原因で、I ループしかパラレル化されていません。このループで誤ったキャッシュラインの共有が生じないように、繰り返しを分散することは不可能です。これらの配列に関係するすべてのループで同一のオフセットを常に使用すれば (できそうもありませんが)、次元を調整して、より良い繰り返しの分散が可能でしょう。

たとえば、次のコードは 8 つのスレッドで正しく作動する可能性があります。

      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

Q とR の両方の宣言の前に 60 バイトをパディングすれば、すべてのJ に対してP(1,J)、Q(2,J)、およびR(3,J) が 64 バイト境界に整列します。CHUNK_SIZE を 16 にしてこれを行えば、スレッドが、重複しない全キャッシュラインにデータを割り当てます。

CPU を多用するループでは、前述の問題すべてが組み合わさった問題に出会うことがよくあります。誤ったキャッシュラインの共有すべてを避けることは不可能です。しかし、問題を注意深く調べ、ここで説明した対処法を慎重に行えば、パラレルループのパフォーマンスを大幅に強化できます。