3

記事はこちら

http://en.wikipedia.org/wiki/Reconfigurable_computing#Example_of_a_streaming_model_of_computation

計算のストリーミング モデルの例
問題: 長さ 256 の 2 つの文字配列が与えられます:A[]とB[]. C[]のように配列を計算する必要がありC[i]=B[B[B[B[B[B[B[B[A[i]]]]]]]]]ます。この問題は仮想的なものですが、いくつかのアプリケーションを持つ同様の問題が存在します。

上記の問題に対するソフトウェア ソリューション (C コード) を考えてみましょう。 

for(int i=0;i<256;i++){
        char a=A[i];
        for(int j=0;j<8;j++)
                a=B[a];
        C[i]=a;
}

このプログラムは、CPU に対して約 256*10*CPI サイクルかかります。ここで、CPI は命令ごとのサイクル数です。

Haskell GHC のような高度なコンパイラでこの問題を最適化できますか?

4

1 に答える 1

2

この wiki ページはあまり意味がありません (そこのトーク ページにも記載されていると思います)。

サンプル マシンは、アクセスをパイプライン処理するには、(異なるパイプライン処理されたステージからの) 8 つの同時要求を維持できるだけでなく、それらを 1 サイクルで完了することができるメモリが必要であるという事実を無視しているため、まったく意味がありません。メモリのバンキングまたは分割は、すべてが B の同じアドレスにアクセスするため、実際には機能しません。

少し拡張して、B を 8 つの異なるメモリ ユニットに複製したと言うことができますが、その場合、コヒーレンシを維持するために、より複雑なコントローラーを見つける必要があります。そうしないと、それらを読み取りにしか使用できなくなります。一方、この種のメモリがあれば、競合している「CPU」はそれを使用できるようにする必要があります。このバンクされたメモリがあれば、アウトオブオーダー実行の最新の CPU は、たとえば、ロードごとに 1 サイクルという同じ仮定の下で、次の命令を発行できます。最初のサイクル: a[i] をロードし、i+ を計算1 2 番目のサイクル: a[i+1] をロード、b[a[i]] をロード、(i+1)+1 を計算 3 番目のサイクル: a[i+2] をロード、b[a[i+1]] をロード、ロード b[b[a[i]]]、計算 i+1+1+1 ... したがって、基本的なコンパイラを使用しても、基本的に、それらが示す特別なパイプラインと同じように機能します。

コンパイラに関する質問については、これを解決できると思う機能を正確に指定していません。一般的に言えば、メモリ依存のレイテンシを軽減できないため、これらの問題をコンパイラで最適化するのは非常に困難です。つまり、最初に a[i] にアクセスする必要があります。その後、CPU は b[a[i]] にアクセスするためのアドレスを取得し、次に b[b[a[i]] のアドレスを取得します。 ]]、 等々。まだアクセスされていないメモリの内容を推測するためにコンパイラができることはあまりありません (推測したとしても、実際のロードが到着するまでに変更される可能性があるため、実用的な目的で使用するのは賢明ではありません)。番組順）。

これは、リンクされたリストをトラバースする「ポインター追跡」の問題に似ています。必要なアドレスは、コンパイル時に不明であるだけでなく、実行時に予測するのも難しく、変更される可能性があります。

これが最適化できないと言っているわけではありませんが、通常は、専用のハードウェア ソリューション (メモリ バンキングなど) や、使用がかなり制限された高度な投機的アルゴリズムが必要になります。このトピックに関する論文 (主に HW プリフェッチ) があります。

于 2013-09-23T08:29:52.780 に答える