Loading article…
コンピュータサイエンスにおいて、正規化ループ（行儀の良いループとも呼ばれる）とは、ループ変数が0（または任意の定数）から始まり、終了条件が満たされるまで反復ごとに1ずつ増加するループのことである。正規化ループは、データ依存性の分析を簡素化するため、コンパイラ理論やループ依存性の分析にとって非常に重要である。[要出典] [1]
適切に動作するループ
適切に動作するループは通常、次の形式になります。
i = 0 ; i < MAX ; i ++の場合、a [ i ] = b [ i ] + 5 ;
増分は単位かつ一定であるため、 aとb の両方が MAX より大きい 場合、このループは割り当てられた範囲外のメモリにアクセスすることはないことが簡単にわかります。
非正規化ループ
正規化されていないループは、異なるインデックスで開始され、非ユニタリ量で増分され、終了条件の定義が複雑になる場合があります。このようなループは、特にループ条件の一部で関数が実行される場合、最適化、ベクトル化、さらにはトラバースが困難です。
最初から開始せず、1 つ以上増加する簡単な例:
// 例 1
for ( i = 7 ; i < MAX ; i += 3 ) a [ i ] = b [ i ] + 5 ;
終了条件を追加した、より複雑な例:
// 例 2
for ( i = 7 ; i < MAX || i > MIN ; i += 3 ) a [ i ] = b [ i ] + 5 ;
ループはコンパイル時に予測できない動作をする可能性もあり、終了条件は変更されるデータの内容によって異なります。
// 例 3
for ( i = 7 ; i < MAX && a [ i ]; i += 3 ) a [ i ] = b [ i ] + 5 ;
あるいは関数呼び出しによる動的な計算も可能です:
// 例4
for ( i = start (); i < max (); i += increment () ) a [ i ] = b [ i ] + 5 ;
逆ループも非常に単純で、簡単に正規化できます。
// 例5
for ( i = MAX ; i > 0 ; i -- ) a [ i ] = b [ i ] + 5 ;
正規化されたループへの変換
正規化されていないものが動的な動作をしない場合は、通常、それを正規化されたものに変換するのは非常に簡単です。たとえば、上記の最初の例 (例 1) は、次のように簡単に変換できます。
// 例 1 -> 正規化
for ( i = 0 ; i < ( MAX -7 ) / 3 ; i ++ ) a [ i * 3 + 7 ] = b [ i * 3 + 7 ] + 5 ;
3 番目の例は、ある程度の並列化を可能にするために部分的に正規化できますが、ループの範囲 (反復回数) を知る能力がまだないため、マルチメディア ハードウェアを使用してベクトル化することが難しくなります。
7 から始めても、増分が規則的 (できれば 1) である限り、それほど問題にはなりません。ループ内の複数のステートメントがインデックスを使用する場合、異なる反復ペースに対応するために、いくつかのプライベート一時変数が作成されることがあります。
逆ループ（例 5）も簡単に正規化できます。
// 例 5 -> 正規化
for ( i = 0 ; i < MAX ; i ++ ) a [ MAX - i ] = b [ MAX - i ] + 5 ;
アクセスはまだ逆方向であることに注意してください。この場合、逆方向のままにしておくのは意味がありません (データ依存性がないため)。ただし、依存性が存在する場合は、割り当ての順序が乱れる可能性があるため、アクセスを元に戻すことにも注意が必要です。
不可能な変換
上記の例 4 では、ループから何かを予測することは不可能です。関数自体が単純 (定数) でない限り、ループがどこで開始され、どこで停止し、各反復でどれだけ増加するかを知る方法はありません。これらのループは並列化が難しいだけでなく、パフォーマンスもひどく悪くなります。
各反復で、ループは 2 つの関数 ( max()とincrement() ) を評価します。関数がインライン化されている場合でも、条件は複雑になりすぎて最適化する価値がなくなります。プログラマーは、絶対に必要な場合を除いて (必要な場合)、これらのループを作成しないように細心の注意を払う必要があります。
評価が変更中のデータに依存する場合、このようなループの別の危険性が現れます。たとえば、反復子を使用する際の通常のエラーは、リストを変更中にリストから項目を削除したり、もはや正しくないサイズ (終了条件) に依存したりすることです。
参照
参考文献
- ^ 「正規化されたヒステリシスループ」。