15

私はこの質問を読んでいました。彼が示したコードについてもっと知りたかったのです。

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

質問は、

  1. 私は時間的局所性を理解しています.iとjへの参照は時間的局所性であるべきだと思います. 私は正しいですか？
  2. a[i] への参照が空間的局所性である必要があるという回答をリンクした質問として、空間的局所性も理解しています。私は正しいですか？

  3. その人は言った、

    「内側のループは a[i] に 10 回アクセスするときに同じメモリ アドレスを呼び出すので、これは時間的局所性の例だと思います。しかし、上記のループにも空間的局所性はありますか?」

    私は彼の推測に同意しない. a[i] によって生成される参照は空間的局所性である必要があるため (それらはブロック内の次の要素を参照します)。私は正しいですか？

4

4 に答える 4

28

First off, references to var can be temporally local or spatially local not temporal locality, which is improper grammar. Minor point.

Now, on to your questions.

  1. The principle of Temporal locality states that two instructions reference the same location within a relatively short timeframe. For example, in the code given, a[i] is referenced frequently, with instructions like a[i] = a[i] * 2 and a[i] = a[i] * 3 being executed very close together. If we are looking at this scope, we could say that references to j and a[i] are temporally local. References to i are also temporally local, because i is referenced every time a[i] is. However, if the last line of the given code read something like a[j] = a[j] * j, then references to i would not be temporally local, at least in the scope of the inner loop[1].

  2. The principle of Spatial locality states that two instructions reference contiguous memory locations. References to a[i] are a good example of this, as one can assume (most of the time) that a[0] and a[1] will be next to each other in memory.

  3. The first two basically cover this, but the quoted text is correct, and the code also demonstrates spatial locality.

[1] - Generally, when you are talking about locality, it will be in the context of a given level in the memory hierarchy, whether it be RAM or the L1 cache or what have you. In all but the most limited sense, references to both i and j are temporally local.

于 2011-10-18T18:33:55.943 に答える
2

外側のループは、空間的局所性の例です。内側の for ループが呼び出すアドレスを順次インクリメントします。

内部ループは、一時的な局所性を示しています。まったく同じメモリ アドレスが連続して 10 回アクセスされ、そのたびに j が乗算されます。

最初の 2 つの質問については、i と j (ループ カウンター) の両方が時間的局所性の非常に良い例です。

ローカリティは、メモリへの呼び出しを最小限に抑えるためにキャッシュによって適用される手段です。命令が、まだキャッシュにないメモリ アドレスの値を知る必要がある場合、メモリにアクセスし、周囲のすべてのメモリ位置もキャッシュに格納します。

于 2011-10-18T18:28:19.147 に答える