最適化手法の適用

コンパイラーはループに対して、交換、アンロール、キャッシュ・ブロッキング、およびロードペアなどの最適化を適用します (適用されないこともあります)。以下のセクションでは、ループを手動で変換する方法および宣言子または内部オプションを使用してループを制御する方法を含めて、これらの変換について説明します。

ループ交換

ループ交換は、2 つの入れ子しているループの実行順を単純に交換する、高レベルな最適化 (HLO) によって適用される入れ子ループの交換です。通常は、キャッシュの局所性を向上するために、ループ内部で使用される配列要素に、連続するユニット・ストライド・アクセスを提供することで行われます。-O3 (Linux* および Mac OS* X) または /O3 (Windows*) オプションを指定すると、コンパイラーはループ交換を適用できる可能性があるかどうかを調べます。

次に、ループ交換の例を示します。

subroutine loop_interchange(a,b,c, NUM)

implicit none

integer :: i,j,k,NUM

real :: a(NUM,NUM), b(NUM,NUM), c(NUM,NUM)

! loop before loop interchange

do i=1,NUM

  do j=1,NUM

    do k=1,NUM

        c(j,i) = c(j,i) + a(j,k) * b(k,i)

    end do

  end do

end do

! loop after interchange

do i=1,NUM

  do k=1,NUM

    do j=1,NUM

        c(j,i) = c(j,i) + a(j,k) * b(k,i)

    end do

  end do

end do

end subroutine loop_interchange

アンロール

ループアンロールは、単一のループ反復中にできるだけ多くの関数ユニットで有用な作業を行いながら、命令レベルの並列処理 (ILP) の利点を活用できる、HLO によって一般的に使用されるループ変換です。ループアンロールでは、より少ないループの反復で、ループの内部により多くの作業を追加します。

subroutine loop_unroll_before(a,b,c,N,M)

implicit none

integer :: i,j,N,M

real :: a(N,M), b(N,M), c(N,M)

N=1025

M=5

do i=1,N

  do j=1,M

    a(j,i) = b(j,i) + c(j,i)

  end do

end do

end subroutine loop_unroll_before

 

subroutine loop_unroll_after(a,b,c,N,M)

implicit none

integer :: i,j,K,N,M

real :: a(N,M), b(N,M), c(N,M)

N=1025

M=5

K=MOD(N,4)  !K= N MOD 4

! main part of loop

do i=1,N-K,4

  do j=1,M

    a(j,i) = b(j,i) + c(j,i)

    a(j,i+1) = b(j,i+1) + c(j,i+1)

    a(j,i+2) = b(j,i+2) + c(j,i+2)

    a(j,i+3) = b(j,i+3) + c(j,i+3)

  end do

end do

! post conditioning part of loop

do i= N-K+2, N, 4

  do j=1,M

    a(j,i) = b(j,i) + c(j,i)

  end do

end do

end subroutine loop_unroll_after

ポスト・コンディショニングは、データのアライメントを保存してメモリー・アライメント・アクセスのペナルティーを回避できるので、プリ・コンディショニングよりもポスト・コンディショニングを推奨します。

キャッシュ・ブロッキング

キャッシュ・ブロッキングは、L1 キャッシュまたは L2 キャッシュの一部にフィットしやすいように、構造データブロックを含みます。データキャッシュの局所性を制御することで、アプリケーションはメモリー・バス・アクセスによるパフォーマンスの遅延を最小限にすることができます。アプリケーションは、データがキャッシュにある間にスレッドがデータに繰り返してアクセスできるように、大きな配列をメモリーの小さなブロックに分割してこの動作を制御します。

例えば、イメージはイメージ全体のより小さな部分またはビデオフレームを使用して処理できるので、キャッシュ・ブロッキング・テクニックは、イメージ処理アプリケーションおよびビデオ・アプリケーションに適しています。コンパイラーは、L2 キャッシュから実行するように命令の関連ブロックをグループ化して、同じテクニックをよく使用します。

キャッシュ・ブロッキング・テクニックの有効性は、データブロックのサイズ、プロセッサーのキャッシュサイズ、およびデータが再利用される回数に依存します。キャッシュサイズはプロセッサーによって異なります。アプリケーションは、CPUID 命令を使用してデータキャッシュのサイズを検出し、パフォーマンスが最大限になるようにキャッシュ・ブロッキングのタイルサイズを動的に調整できます。一般的に、キャッシュブロックのサイズは、物理的なキャッシュサイズの 1/2 から 3/4 にするべきです。ハイパースレッディング・テクノロジー (HT テクノロジー) が有効なシステムでは、物理的なキャッシュサイズの 1/4 から 1/2 にしてください 「ハイパースレッディング・テクノロジーの設計」

キャッシュ・ブロッキングは HLO に適用され、同時にすべての配列をキャッシュに入れることができない大きな配列で使用されます。この手法は、(小さな領域の) キャッシュにデータのサブセットを入れて、データがメモリーからの新しいデータに置換される前に、このキャッシュされたデータをできるだけ有効に使用する 1 つの方法です。

subroutine cache_blocking_before(a,b,N)

  implicit none

  integer :: i,j,k,N

  real :: a(N,N,N), b(N,N,N), c(N,N,N)

  N=1000

  do i = 1, N

    do j = 1, N

      do k = 1, N

        a(i,j,k) = a(i,j,k) + b(i,j,k)

      end do

    end do

  end do

end subroutine cache_blocking_before

subroutine cache_blocking_after(a,b,N)

  implicit none

  integer :: i,j,k,u,v,N

  real :: a(N,N,N), b(N,N,N), c(N,N,N)

  N=1000

  do v = 1, N, 20

    do u = 1, N, 20

      do k = v, v+19

        do j = u, u+19

          do i = 1, N

            a(i,j,k) = a(i,j,k) + b(i,j,k)

          end do

        end do

      end do

    end do

  end do

end subroutine cache_blocking_after

キャッシュブロックのサイズは 20 に設定されます。目的は、キャッシュにあるデータのブロックを読み取って、可能なすべてのビットの計算を行った後、新しいデータのブロックをキャッシュにロードすることです。同時にキャッシュに A の 20 の要素と B の 20 の要素があり、次のキャッシュブロックに進む前に、このデータで可能な限りの作業を行います。

アーキテクチャーが異なると、ブロッキング系数も異なります。ブロッキング系数は経験的に判断します。例えば、単精度と倍精度では異なるブロッキング系数が必要です。通常、パフォーマンスに与える影響は非常に大きくなります。

ループ分配

ループ分配は、1 つの大きなループを 2 つの小さなループに分割する高レベルループ変換です。レジスターの使用率が高いためにソフトウェアのパイプライン化 (SWP) やベクトル化のような最適化を実行できない場合に役立ちます。ループをより小さなセグメントに分割することによって、より小さな各ループ、またはその少なくとも 1 つをソフトウェアのパイプライン化またはベクトル化できる可能性があります。次に例を示します。

subroutine loop_distribution_before(a,b,c,x,y,z,N)

  implicit none

  integer :: i,N

  real :: a(N), b(N), c(N), x(N), y(N), z(N)

  N=1024

  do i = 1, N

    a(i) = a(i) + i

    b(i) = b(i) + i

    c(i) = c(i) + i

    x(i) = x(i) + i

    y(i) = y(i) + i

    z(i) = z(i) + i

  end do

end subroutine loop_distribution_before

subroutine loop_distribution_after(a,b,c,x,y,z,N)

  implicit none

  integer :: i,N

  real :: a(N), b(N), c(N), x(N), y(N), z(N)

  N=1024

  do i = 1, N

    a(i) = a(i) + i

    b(i) = b(i) + i

    c(i) = c(i) + i

  end do

  do i = 1, N

    x(i) = x(i) + i

    y(i) = y(i) + i

    z(i) = z(i) + i

  end do

end subroutine loop_distribution_after

次のように、コンパイラーにループの分配を推奨する宣言子があります。

!DEC$ distribute point

プラグマがループの外部に配置されると、コンパイラーはその内部ヒューリスティックに基づいてループを分配しようとします。次に、ループの外部でプラグマを使用する例を示します。

subroutine loop_distribution_pragma1(a,b,c,x,y,z,N)

  implicit none

  integer :: i,N

  real :: a(N), b(N), c(N), x(N), y(N), z(N)

  N=1024

!DEC$ distribute point

  do i = 1, N

    a(i) = a(i) + i

    b(i) = b(i) + i

    c(i) = c(i) + i

    x(i) = x(i) + i

    y(i) = y(i) + i

    z(i) = z(i) + i

  end do

end subroutine loop_distribution_pragma1

ループの内部に配置されると、コンパイラーはそのポイントでループを分配しようとします。ループ伝播の依存はすべて無視されます。次の例は、分割すべき場所を正確に示すためにループの内部で宣言子を使用しています。

subroutine loop_distribution_pragma2(a,b,c,x,y,z,N)

  implicit none

  integer :: i,N

  real :: a(N), b(N), c(N), x(N), y(N), z(N)

  N=1024

  do i = 1, N

    a(i) = a(i) + i

    b(i) = b(i) + i

    c(i) = c(i) + i

!DEC$  distribute point

    x(i) = x(i) + i

    y(i) = y(i) + i

    z(i) = z(i) + i

  end do

end subroutine loop_distribution_pragma2

ロードペア (IA-64 対応コンパイラー)

ロードペア (ldfp) は、1 回の転送でメモリーから 2 つの連続した単精度または倍精度値をロードする命令です。ロードペアは、パフォーマンスを大幅に向上させることができます。

手動ループ変換

手動ループ変換が使用可能な場合や、推奨される場合もあります。ただし、通常は、手動ではなく、コンパイラーでループ変換を行うようにすべきです。手動変換は最後の手段です。パフォーマンスの向上を試みている場合にのみ、この手法を使用してください。

手動ループ変換には、次のような多くの短所があります。

HLO レポートは、コンパイラーによって適用されたループ変換についての情報を知らせます。

手動でループを変換する場合に重要なのは経験です。コンパイラーが無視したループ変換を適用する場合もあります。また、コンパイラーが -O3 (Linux) または /O3 (Windows) を適用した後に手動ループ変換を適用すると良い場合もあります。