フラット化変換

フラット化変換は、ネストされたデータ並列性をフラットなデータ並列性に変換するアルゴリズムです。これは、ガイ・ブレロクがNESLプログラミング言語の一部として開発しました。 ^{[1]フラット化変換は}ベクトル化 と呼ばれることもありますが、自動ベクトル化とはまったく関係ありません。元のフラット化アルゴリズムは、プリミティブ型を含む1次多次元配列のみを対象としていましたが、Data Parallel Haskellの作業で高次および再帰データ型を処理できるように拡張されました。^[2]

フラット化は、関数を持ち上げて単一の値ではなく配列を操作することで機能します。たとえば、関数 は関数 に持ち上げられます。これは、式を持ち上げた関数の適用で置き換えることができることを意味します。直感的には、フラット化は、すべての関数の適用を対応する持ち上げられた関数の適用で置き換えることで機能します。 ${\displaystyle f:A\rightarrow B}$${\displaystyle f':[A]\rightarrow [B]}$${\displaystyle map~f~x}$${\displaystyle f'~x}$

平坦化後、配列は、スカラー要素を含む 1 次元の値ベクトルVとして表され、ネストされた構造を記録する補助情報 (通常はブール フラグ ベクトルFの形式) も示されます。フラグ ベクトルは、値ベクトル内の対応する要素が、新しいセグメントの開始であるかどうかを示します。たとえば、2 次元の不規則な配列は、データ ベクトルとフラグ ベクトルとして表すことができます。 ${\displaystyle A=[[1,2,3],[4,5],[],[6]]}$${\displaystyle V=[1,2,3,4,5,6,7]}$${\displaystyle F=[1,0,0,1,0,1,1]}$

このフラグ ベクトルは、ネストされた並列処理を正しくフラット化するために必要です。たとえば、プレフィックス合計をセグメント スキャンにフラ​​ット化するときに使用されます。

フラット化により、元のプログラムの漸近的な作業量と空間の複雑さが増加し、結果的に効率が大幅に低下する可能性があります。^[3]

フラット化はもともとコネクションマシンなどのベクターマシン向けに開発されたもので、現代のマルチコアCPUには適さないコードを生成することが多い。 ^{[4]しかし、より単純なケースの根底にある原理は、} Google Jaxvmapの などの構造に見出すことができる。