11. loop指示文

loop指示文は対象のループを並列化する指示文です. そのループ中に現れる分散配列は,下記の条件を満たす必要があります.

1. 繰り返しを跨ぐデータ依存や制御依存がないこと. つまり,ループの繰り返しは,どのような順番で実行しても同じ結果となるようなループであること

  1. 分散配列の要素を持っているノードが,その要素をアクセスすること

11.1. 分散配列へのアクセス

下記のプログラムは,正しいloop指示文とループ文の例です. ループ内でアクセスされる分散配列aのインデックスはiだけなので,条件1をクリアします. また,loop指示文のon節で指定されたテンプレートが持つ各ノードのインデックス情報はループ内の分散配列と同じなので, 条件2もクリアします.

  • XMP/Cプログラム
#pragma xmp nodes p[2]
#pragma xmp template t[10]
#pragma xmp distribute t[block] onto p

int main(){
  int a[10];
#pragma xmp align a[i] with t[i]

#pragma xmp loop on t[i]
  for(int i=0;i<10;i++)
    a[i] = i;

  return 0;
}
  • XMP/Fortranプログラム
program main
!$xmp nodes p(2)
!$xmp template t(10)
!$xmp distribute t(block) onto p
  integer a(10)
!$xmp align a(i) with t(i)

!$xmp loop on t(i)
  do i=1, 10
    a(i) = i
  enddo

end program main
_images/loop1.png

同じプログラムでループの範囲が下記のように小さくなっていたら,並列化できるでしょうか?

  • XMP/Cプログラム(一部分)
#pragma xmp loop on t[i]
  for(int i=1;i<9;i++)
    a[i] = i;
  • XMP/Fortranプログラム(一部分)
!$xmp loop on t(i)
  do i=2, 9
    a(i) = i
  enddo

この場合も,条件1と2をともに満たすため,並列化可能です. XMP/Cでは, p[0]はインデックス1から4を処理し,p[1]は5から8を処理します. 同様に,XMP/Fortranでは,p(1)はインデックス2から5を処理し,p(2)は6から9を処理します.

_images/loop2.png

次に,同じプログラムで分散配列のインデックスがずれていたら,並列化できるでしょうか?

  • XMP/Cプログラム(一部分)
#pragma xmp loop on t[i]
  for(int i=1;i<9;i++)
    a[i+1] = i;
  • XMP/Fortranプログラム(一部分)
!$xmp loop on t(i)
  do i=2, 9
    a(i+1) = i
  enddo

この場合は,条件1は満たしますが,条件2は満たさないため,並列化を行うことができません. XMP/Cでは,p[0]はa[5]をアクセスしようとしますが,p[0]はa[5]を持っていないためです. 同様に,XMP/Fortranでは,p(1)はa(6)をアクセスしようとしますが,p(1)はa(6)を持っていません.

_images/loop3.png

11.2. 集約計算

次の逐次プログラムを使って集約計算について説明します.

  • Cプログラム
#include <stdio.h>

int main(){
  int a[10], sum = 0;

  for(int i=0;i<10;i++){
    a[i] = i+1;
    sum += a[i];
  }

  printf("%d\n", sum);

  return 0;
}
  • Fortranプログラム
program main
  integer :: a(10), sum = 0

  do i=1, 10
    a(i) = i
    sum = sum + a(i)
  enddo

  write(*,*) sum

end program main

上のループをloop指示文だけを使って並列化しようとした場合, ノード毎に変数sumの値が計算されるため, 変数sumの値はノード毎に異なる結果になります.

  • XMP/Cプログラム(未完成.一部)
#pragma xmp loop on t[i]
   for(int i=0;i<10;i++){
     a[i] = i+1;
     sum += a[i];
   }
  • XMP/Fortranプログラム(未完成.一部)
!$xmp loop on t(i)
  do i=1, 10
    a(i) = i
    sum = sum + a(i)
  enddo
_images/reduction1.png

そこで,loop指示文にreduction節を加えます.

  • XMP/Cプログラム
#include <stdio.h>
#pragma xmp nodes p[2]
#pragma xmp template t[10]
#pragma xmp distribute t[block] onto p

int main(){
  int a[10], sum = 0;
#pragma xmp align a[i] with t[i]

#pragma xmp loop on t[i] reduction(+:sum)
  for(int i=0;i<10;i++){
    a[i] = i+1;
    sum += a[i];
  }

  printf("%d\n", sum);

  return 0;
}
  • XMP/Fortranプログラム
program main
!$xmp nodes p(2)
!$xmp template t(10)
!$xmp distribute t(block) onto p
  integer :: a(10), sum = 0
!$xmp align a(i) with t(i)

!$xmp loop on t(i) reduction(+:sum)
  do i=1, 10
    a(i) = i
    sum = sum + a(i)
  enddo

  write(*,*) sum

end program main

reduction節には集約のための演算子と集約変数を指定します. 上例では加算の演算子を指定しており, この集約計算がノードを跨ぐ総和を求めていることを表現しています.

_images/reduction2.png

集約計算に対する演算は,下記の結合則が成り立つ演算に限られます.

  • XMP/Cプログラム
+
*
-
&
|
^
&&
||
max
min
firstmax
firstmin
lastmax
lastmin
  • XMP/Fortranプログラム
+
*
-
.and.
.or.
.eqv.
.neqv.
max
min
iand
ior
ieor
firstmax
firstmin
lastmax
lastmin

注釈

集約変数が浮動小数点型の場合は,計算順序の違いにより,逐次実行と並列実行で結果がわずかに異なる場合があります.

11.3. ネストされたループの並列実行

ネストされたループに対するワークマッピングも,1次元配列と同じように行うことができます.

  • XMP/Cプログラム
#pragma xmp nodes p[2][2]
#pragma xmp template t[10][10]
#pragma xmp distribute t[block][block] onto p

int main(){
  int a[10][10];
#pragma xmp align a[i][j] with t[i][j]

#pragma xmp loop on t[i][j]
  for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
      a[i][j] = i*10+j;

  return 0;
}
  • XMP/Fortranプログラム
program main
!$xmp nodes p(2,2)
!$xmp template t(10,10)
!$xmp distribute t(block,block) onto p
  integer :: a(10,10)
!$xmp align a(j,i) with t(j,i)

!$xmp loop on t(j,i)
  do i=1, 10
    do j=1, 10
      a(j,i) = i*10+j
    enddo
  enddo

end program main