ループ分割とループ融合

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

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

loop fission

C言語での例

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

上記のコードは、以下のコードと等価である。

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

loop fusion

C言語での例

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

上記のコードは、以下のコードと等価である。

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

関連項目

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

参考文献

• Loop fission