9

本Computer Systems: A Programmer's Perspectiveの演習 5.5 は、多項式の値を計算するためのコードを示しています。

double poly(double a[], double x, int degree)
{
    long int i;
    double result = a[0];
    double xpwr = x;
    for (i = 1; i <= degree; i++) {
        result += a[i] * xpwr;
        xpwr = x * xpwr;
    }
    return result;
}

この演習では、倍精度浮動小数点の加算と乗算に必要なクロック サイクルがそれぞれ 3 と 5 であると想定しています。読者は、測定された CPE (Cycles Per Element) 値が 5 である理由を説明するよう求められます。

演習の答えによると、反復ごとに変数xpwrとを更新するresult必要があり、必要な操作は浮動小数点加算 ( の場合result) と浮動小数点乗算 ( の場合xpwr) であるため、後者がレイテンシを支配し、最終的な CPE は 5 です。

しかし、データフローは次のようにする必要があると思います。

xpwr               result
  |                  |
  +-----+ +--[load]  |
  |     | |          |
[mul]  [mul]         |
  |      |           |
  |      +---+ +-----+
  |          | |
  |         [add]
  |           |
  |           +------+
  |                  |
xpwr               result

したがって、最長パスは の前の値xpwrから の新しい値までであり、実行ユニットおよびresultを通過します。したがって、最長時間は 8 サイクルです。[mul][add]

聞きたい

  1. クリティカル パスの正確な意味は何ですか? そして、それをどのように決定するのですか？
  2. どちらの答え（私のものと本）がより合理的ですか?

CPU、アーキテクチャ、実行ユニット、パイプライン、浮動小数点ユニットに関する説明をいただければ幸いです。

4

4 に答える 4

6

私はパーティーに少し遅れていることを知っていますが、本は完全に正しい. コードのタイミングを自分で確認できるように、CPE は確かに 5 であるため、2 番目の答えは間違っています。

しかし、最初のものも間違っています。MUL を同時に実行する必要があると書かれていますが、これは Nehalem アーキテクチャではまったく不可能です (そして、ほとんどの最新のプロセッサと思われます)。1 つの FP MUL ユニットと別の FP ADD ユニットしかないことに注意してください (本、ed. 2011 以降に示されているように)。

代わりにこれが起こります：

(LOAD は常に存在すると想定され、キャッシュ内にある場合は 1 サイクルのみ)

まずxpwr *= x、MUL をフィードします。その直後にフィードしますxpwr*a[i](パイプラインを思い出してください!)

... 5 サイクル後に の新しい値が得られ、xpwr6 サイクル後に の結果が得られxpwr*a[i]ます。その時点で、 の新しい計算xpwr *= xが MUL のステージ 1 になります。したがって、制限されたくない場合、残りの操作を実行するサイクルはあと 4 サイクルしかありません。

もちろん、FP ADD が新しいresult.

したがって、制限要因が の計算であることが明らかになりxpwrます。つまり、クリティカル パス (それが何であれ) を探す際には、特に古い値から新しい値へのパスに注目する必要があります。この場合、パスresultは 1 つの FP ADD! だけで構成されます。（それも最初は私を失望させたものです）

于 2014-10-19T04:10:57.720 に答える
2

クリティカル パスは確かに 8 サイクルですが、質問は CPE を求めます。これは、ループのもう 1 つのサイクルを出力するための時間平均時間のようなものです。

最初と最後のサイクル以外では、オペランドが相互に依存していないため、プロセッサはループの前の反復からの加算と現在の乗算を同時に実行できます。ループの最初の反復では完全に 8 サイクルかかりますが、その後のすべての反復では、ループの実行に 5 サイクルしかかからないため、実際の CPE は 5 サイクルになります。

PS 本書のクリティカル パスの提示方法が紛らわしいことに同意します。クリティカル パスの定義は、単に最長のパスをたどるパスではなく、パスには、以前の操作に依存するオペランドを持つ操作が含まれている必要があるため、順序どおりにする必要があります。この定義により、クリティカル パスを見つけることはむしろ直感的ではなくなります。

于 2014-02-22T09:09:59.507 に答える
1

A1: 本によると、クリティカル パスはデータ フロー グラフの中で最も長いものであり、直線上にある必要があり、「mul」と「add」を加算するのではなく、単一のレジスタに影響を与えます。次の操作の中間オペランドのみ。

この質問については、残りを読み続ければすべて完了します。特に、combine7 のデータ フロー グラフと、combine5 のデータ フロー グラフを比較すると役立ちます。

A2: A1 が理解され、質問 2 がクリアされ、本の回答が合理的である場合。

于 2014-11-23T00:01:29.563 に答える
0

クリティカル パスはグラフを通過する最長パスで、この場合は 8 クロックです。これは、Dragon Bookがクリティカル パスについて述べていることです (10.3.3 優先順位付けされたトポロジー順序)。

リソースの制約がなければ、最短のスケジュールはクリティカル パス (データ依存グラフを通る最長のパス) によって与えられます。優先度関数として役立つメトリックは、ノードの高さです。これは、ノードから始まるグラフ内の最長パスの長さです。

あなたは本の間違いを見つけたと思います。将来の印刷物で修正できるように、著者に連絡することを検討してください。

于 2013-02-10T23:13:26.260 に答える