ループのパイプライン処理とループ展開

ループのパイプライン処理とループ展開は、どちらもループの繰り返し間の並列処理を可能にすることで、ハードウェア関数のパフォーマンスを改善する手法です。ここでは、ループのパイプライン処理とループ展開の基本的な概念とこれらの手法を使用するコード例を示し、これらの手法を使用して最適なパフォーマンスを達成する際に制限となる要因について説明します。

ループのパイプライン処理

C/C++ のような逐次言語の場合、ループの演算は順番に実行され、ループの次の繰り返しは、現在の繰り返しの最後の演算が終了してから開始されます。ループのパイプライン処理を使用すると、次の図に示すようにループ内の演算が並列方式でインプリメントできるようになります。

図: ループのパイプライン処理

上図に示すように、パイプライン処理しない場合、2 つの RD 演算間に 3 クロックサイクルあるので、ループ全体が終了するのに 6 クロックサイクル必要となります。パイプライン処理を使用すると、2 つの RD 演算間は 1 クロックサイクルなので、ループ全体が終了するのに 4 クロックサイクルしか必要となりません。ループの次の繰り返しは現在の繰り返しが終了する前に開始できます。

開始間隔 (II) はループのパイプライン処理における重要な用語で、ループの連続する繰り返しの開始時間の差をクロックサイクル数で示します。上記の図では、連続するループの繰り返しの開始時間の差は 1 クロックサイクルしかないので、開始間隔 (II) は 1 です。

ループをパイプライン処理するには、次に示すように、ループ本体の開始部分に #pragma HLS pipeline と記述します。Vivado HLS で、最小限の開始間隔でループのパイプライン処理が試みられます。

for (index_a = 0; index_a < A_NROWS; index_a++) {
     for (index_b = 0; index_b < B_NCOLS; index_b++) {
#pragma HLS PIPELINE II=1
         float result = 0;
         for (index_d = 0; index_d < A_NCOLS; index_d++) {
             float product_term = in_A[index_a][index_d] * in_B[index_d][index_b];
             result += product_term;
         }
         out_C[index_a * B_NCOLS + index_b] = result;
     }
}

ループ展開

ループ展開は、ループの繰り返し間を並列処理するための別の手法で、ループ本体の複数コピーを作成して、ループの繰り返しカウンターをそれに合わせて調整します。次のコードは、展開されていないループを示しています。

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

ループを係数 2 で展開すると、次のようになります。

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

係数 N でループを展開すると、ループ本体の N 個のコピーが作成され、各コピーで参照されるループ変数 (前述の例の場合は a[i+1]) がそれに合わせてアップデートされ、ループの繰り返しカウンター (前述の例の場合は i+=2) もそれに合わせてアップデートされます。

ループ展開では、ループの各繰り返しにより多くの演算が作成されるので、Vivado HLS でこれらの演算を並列処理できるようになります。並列処理が増えると、スループットが増加し、システムパフォーマンスも向上します。係数 N がループの繰り返しの合計 (前述の例の場合は 10) よりも少ない場合、「部分展開」と呼ばれます。係数 N がループの繰り返し数と同じ場合は、「全展開」と呼ばれます。全展開の場合、コンパイル時にループ範囲がわかっている必要がありますが、並列処理は最大限に実行されます。

ループを展開するには、そのループの開始部分に #pragma HLS unroll [factor=N] を挿入します。オプションの factor=N を指定しない場合、ループは全展開されます。

int sum = 0;
for(int i = 0; i < 10; i++) {
#pragma HLS unroll factor=2
    sum += a[i];
}

ループのパイプライン処理とループ展開で達成される並列処理を制限する要因

ループのパイプライン処理とループ展開は、どちらもループの繰り返し間の並列処理を可能にしますが、ループ繰り返し間の並列処理は、ループ繰り返し間のデータ依存性と、使用可能なハードウェアリソース数の２つの主な要因により制限されます。

連続する繰り返しにおける 1 つの繰り返しの演算から次の繰り返しの演算へのデータ依存性は「ループキャリー依存性」と呼ばれ、現在の繰り返しの演算が終了して次の繰り返しの演算用のデータ入力が計算されるまで、次の繰り返しの演算を開始できないことを意味します。ループキャリー依存性があると、ループのパイプライン処理を使用して達成可能な開始間隔とループ展開を使用して実行可能な並列処理が制限されます。

次の例は、変数 a と b を出力する演算と入力として使用する演算間でのループキャリー依存性を示しています。

while (a != b) {
    if (a > b) 
        a –= b;
    else 
        b –= a;
}

このループの次の繰り返しの演算は、現在の繰り返しが計算されて、a と b の値がアップデートされるまで開始できません。次の例に示すような配列アクセスは、ループキャリー依存性のよくある原因です。

for (i = 1; i < N; i++)
    mem[i] = mem[i-1] + i;

この例の場合、現在の繰り返しが配列の内容をアップデートするまでループの次の繰り返しを開始できません。ループのパイプライン処理の場合、最小の開始間隔はメモリ読み出し、加算、メモリ書き込みに必要な合計クロックサイクル数です。

使用可能なハードウェアリソース数もループのパイプライン処理およびループ展開のパフォーマンスを制限する要因です。次の図は、リソースの制限により発生する問題の例を示しています。この場合、ループを開始間隔 1 でパイプライン処理することはできません。

図: リソースの競合

この例の場合、ループが開始間隔 1 でパイプライン処理されると、2 つの読み出しが実行されることになります。メモリにシングルポートしかない場合、この 2 つの読み出しは同時に実行できず、2 サイクルで実行する必要があります。このため、最小の開始間隔は図の (B) に示すように 2 になります。同じことは、その他のハードウェアリソースでも発生します。たとえば、op_compute が DSP コアを使用してインプリメントされ、それが各サイクルごとに新しい入力を受信できず、このような DSP コアが 1 つしかない場合、op_compute はサイクルごとに DSP に出力できないので、開始間隔 1 は使用できません。