ループ分割とループ融合

コンピュータ科学の分野において、ループ分割（英語: loop fission, loop distribution）は、コンパイラ最適化手法の1つであり、1つのループを、同じインデックスの範囲を持つ複数のループに分解し、各ループでは元のループ本体の一部だけをもたせる、という手法である。大きなループ本体を小さなループに分割することで、参照の局所性をよりよく活用することが目的である。この最適化が最も効率よく実行できるのは、1つのタスクを複数のタスクに分割して、各タスクをそれぞれのコアで並列に実行できるマルチコアプロセッサである。

逆に、ループ融合（英語: loop fusion, loop jamming）は、複数のループを1つのループに置換するという、コンパイラ最適化およびループ変換の手法である。2つのループが同じ範囲でイテレートしており、互いにデータの参照が存在しない場合に適用可能である。ループ融合は、必ずしもランタイムの速度向上に寄与するとは限らない。実際、一部のアーキテクチャでは、たとえば、各ループ内でのデータの局所性が高まるため、2つのループの方が1つのループより性能が良いことがある。

ループ分割

C言語での例

int a[100], b[100];
for (int i = 0; i < 100; i++) {
  a[i] = 1; 
  b[i] = 2;
}

上記のコードのfor文を以下のように分解する。

int a[100], b[100];
for (int i = 0; i < 100; i++) {
  a[i] = 1;                     
}
for (int i = 0; i < 100; i++) {
  b[i] = 2;
}

ループ融合

C言語での例

int a[100], b[100];
for (int i = 0; i < 100; i++) {
  a[i] = 1;
}
for (int i = 0; i < 100; i++) {
  b[i] = 2;
}

上記のコードのfor文を以下のように融合する。

int a[100], b[100];
for (int i = 0; i < 100; i++) {
  a[i] = 1; 
  b[i] = 2;
}

関連項目

• 式テンプレート
• ループ変換
• Nuclear computation

参考文献

• Loop fission