4

ほとんどのアルゴリズム（ソート、検索、グラフトラバーサルなど）の実装では、追加の通常の操作を犠牲にしてメモリアクセスを減らすことでトレードオフが発生することがよくあります。

Knuthには、特定のプロセッサから抽象化し、通常の操作（oops）とメモリ操作（mems）のみを区別することにより、さまざまなアルゴリズム実装の複雑さを比較するための便利な方法があります。

コンパイルされたプログラムでは、通常、コンパイラに低レベルの操作を整理させ、データがキャッシュメモリ（高速）または仮想メモリ（低速）のどちらに保持されるかという問題をオペレーティングシステムが処理することを期待します。さらに、命令の正確な数/コストはコンパイラによってカプセル化されます。

Forthを使用すると、そのようなカプセル化はなくなり、レジスタプロセッサ上で実行されるスタックマシンに近いとはいえ、マシンにはるかに近くなります。

オペレーティングシステムの影響を無視して（メモリのストールなどがないように）、今のところ単純なプロセッサを想定します。

（1）Forthの通常のスタック操作（dup、rot、over、swapなど）をForthのメモリアクセスフェッチ（@）またはストア（！）のコストと比較する方法について誰かがアドバイスできますか？

（2）メモリアクセスの節約とトレードオフする通常の操作の数を決定するために使用できる経験則はありますか？

私が探しているのは、「通常の50オペレーション、通常の500オペレーション、または通常の5オペレーションのメモリアクセスコスト」のようなものです。Ballparkは絶対に問題ありません。

フェッチとストアの相対的なコストと、腐敗、スワップ、重複、ドロップ、オーバー、桁違いの修正の相対的なコストを把握しようとしています。

4

2 に答える 2

3

この記事メモリから1つの単語をフェッチするのにどのくらい時間がかかりますか？経験則によると、メインメモリのストール時間について説明しますが、基本的には、メインメモリのストール中に多くの命令を実行できます。他の人が言っているように、数はシステム間で大きく異なります。

特にCPUにはより多くのコアがあるため、メインメモリのストールは大きな関心領域ですが、通常はそれほど高速なメモリ帯域幅ではありません。CPUが「スペア」サイクルと密集したキャッシュラインを利用できるように、メインメモリ内のデータの圧縮についてもいくつかの研究が行われていますhttp://oai.cwi.nl/oai/asset/15564/15564B.pdf

詳細に本当に興味がある人のために、ほとんどのCPUメーカーは、メモリの最適化などに関する詳細なガイドを公開しています。これは主にハイエンドおよびコンパイラの作成者を対象としていますが、2glおよび3glのすべてのプログラマーが読むことができます。

追伸 フォースに行きます。

于 2013-03-18T01:50:51.370 に答える
1

メモリフェッチとレジスタ操作の比較は、実際にはアセンブラプログラムであるcコンパイラの出力の場合と同様に、アセンブラプログラムでも問題ありません。Forthでは、この質問はほとんど意味がありません。そもそもフォースは通訳であり、フォースを使用することで究極のスピードを放棄します。もちろん、Forthの上にオプティマイザーを追加することもできますが、c-optimiserとForthオプティマイザーの出力が最適なソリューションに収束するため、この質問はさらに意味がありません。

ANDのようなForthの基本操作を見てみましょう。これは次のように実装されます

> CODE AND
>     POP AX
>     POP BX
>     AND AX, BX
>     PUSH AX
>     NEXT

したがって、基本的な計算操作のように見えるものに対して、すでに3つのメモリ操作があります。Knuthメトリックは適用できないようです。また、フォースは大きな時間を失っているようですが、それは真実ではありません。これらのメモリ操作はすべて、一般的なプロセッサのL1キャッシュにあります。これは、小さなc関数のローカル変数とほぼ同じくらい効率的です。VARIABLEとスタックを使用して、スタック操作をメモリ操作と比較できます。答えは簡単です。VARIABLEは、メモリストールのリスクがあります。スタック操作は、ほぼ確実にL1キャッシュヒットになります。これが最も重要な考慮事項です。しかし、質問はそれを考慮しないように明示的に求めています！だからそこに。

于 2020-10-18T16:29:28.573 に答える