多面体モデル

多面体モデル(多面体法とも呼ばれる) は、大量の操作 (明示的に列挙するには大きすぎる) を実行するプログラムのための数学的フレームワークであり、コンパクトな表現が求められます。入れ子になったループ プログラムは典型的な例ですが、唯一の例ではありません。このモデルは、プログラム最適化におけるループネストの最適化に最もよく使用されます。多面体法では、入れ子になったループ内の各ループ反復を、多面体と呼ばれる数学的オブジェクト内の格子点として扱い、多面体に対してアフィン変換またはより一般的な非アフィン変換 (タイリングなど) を実行してから、多面体スキャンによって、変換された多面体を同等で最適化された (対象となる最適化の目標によって異なります) ループ ネストに変換します。

Cで書かれた次の例を考えてみましょう。

定数int n = 100 ; int i , j , a [ n ][ n ];    
   

i = 1 ; i < n ; i ++の場合{ j = 1 ; j < ( i + 2 ) && j < n ; j ++ の場合{ a [ i ] [ j ] = a [ i - 1 ] [ j ] + a [ i ] [ j - 1 ]; } }        
                
            
  

このコードの本質的な問題は、 上の内部ループの各反復ではa[i][j]、前の反復の結果 が既に利用可能になっている必要があることです。したがって、このコードは、現在の記述のままでは a[i][j - 1]並列化またはパイプライン化できません。

アフィン変換と境界の適切な変更を 伴う多面体モデルを適用すると、上記のネストされたループは次のように変換されます。${\displaystyle (i',\,j')=(i+j,\,j)}$

a [ i - j ][ j ] = a [ i - j - 1 ][ j ] + a [ i - j ][ j - 1 ];              

この場合、内側のループのどの反復も前の反復の結果に依存しません。内側のループ全体を並列に実行できます。実際、 が与えられたa(i, j) = a[i-j][j]場合、a(i, j)は のみに依存しa(i - 1, x)、 となります。(ただし、外側のループの各反復は前の反復に依存します。) ${\displaystyle x\in \{j-1,\,j\}}$

次のCコードは、 Floyd–Steinberg ディザリングに類似したエラー分散ディザリングの形式を実装していますが、教育上の理由で変更されています。2 次元配列にはピクセルの行が含まれており、各ピクセルのグレースケール値は 0 から 255 までです。ルーチンが終了すると、出力配列には値 0 または値 255 のピクセルのみが含まれます。計算中、各ピクセルのディザリング エラーは、配列に追加することによって収集されます。(計算中、と は読み取りと書き込みの両方が行われ、は読み取り専用ではなく、 は書き込み専用ではない ことに注意してください。)srchwdstsrcsrcdstsrcdst

内側のループの各反復では、、、およびsrc[i][j]の値に基づいての値が変更されます。( にも同じ依存関係が適用されます。ループをスケーリングする目的で、と を同じ要素として考えることができます。) の依存関係は、右の図のようにグラフィカルに表すことができます。 src[i-1][j]src[i][j-1]src[i+1][j-1]dst[i][j]src[i][j]dst[i][j]src[i][j]

元の依存関係図にアフィン変換を実行すると、次の画像に示すような新しい図が作成されます。次に、 と の代わりにと をループするようにコードを書き直すと、次の「歪んだ」ルーチンが得られます。 ${\displaystyle (p,\,t)=(i,\,2j+i)}$ptij

• 多面体モデルをサポートするフレームワーク
• ループネストの最適化
• ループ最適化
• ループ展開
• ループタイリング

• 「基本的な多面体法」、Martin Griebl によるチュートリアル。上記の擬似コード例の図が含まれています。
• 「ポリトープ モデルにおけるコード生成」(1998)。Martin Griebl、Christian Lengauer、Sabine Wetzel
• 「CLooG 多面体コード ジェネレーター」
• 「CodeGen+: Z-多面体スキャン」^{[永久リンク切れ‍ ]}
• PoCC: 多面体コンパイラコレクション
• PLUTO - アフィンループネストの自動並列化および局所最適化ツール
  • Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (2008-01-01)。「実用的な自動多面体並列化装置および局所性最適化装置」。プログラミング言語の設計と実装に関する第 29 回 ACM SIGPLAN 会議の議事録。PLDI '08 。ニューヨーク、ニューヨーク、米国: ACM。pp. 101–113。doi :10.1145/1375581.1375595。ISBN 9781595938602. S2CID  7086982。
• polyhedral.info - 多面体コンパイルに関する情報を集めるウェブサイト
• Polly - 高レベルループとデータ局所性最適化のための LLVM フレームワーク
• MIT ティラミス多面体フレームワーク。