東京大学 情報理工学系研究科 電子情報学専攻 2014年8月実施 専門 第2問

标签：

• Tokyo-University
• Hardware-Prefetching
• Non-Blocking-Cache
• Sequential-Random-and-Pointer-Chasing-Access
• Multi-Level-Cache
• Memory-Level-Parallelism

Author

diohabara

Description

以下の問いに答えよ。

(1) 現代的なスーパースカラプロセッサは、プログラムのメモリアクセス性能をあげるために以下を含むいくつもの機構を備えている。

• (a) キャッシュ
• (b) ハードウェアによる先読み
• ($c$) ノンブロッキングキャッシュ

それぞれの機構が何をするか、およびそれぞれがメモリアクセス性能をあげるためにどう貢献するのかを簡潔に説明せよ。

(2) ある構造体の配列および、その全要素にアクセスするプログラムを考え、アクセスの方法や配列の大きさが性能に与える影響について考察する。具体的には、以下の方法 $1〜4$ を考える。

方法 1: 全要素を逐次的に、配列の先頭から終わりまでアクセスする。

方法 2: 配列の添字を乱数で生成し、その添字の要素に、それらが生成された順でアクセスする。配列の全ての添字がちょうど一度ずつ生成されるとする。なお、乱数ひとつを生成するのにかかる時間は $7〜8$ サイクル程度で、メモリアクセス命令は必要ない。

方法 3: 各要素に後続の要素を指すポインタを持たせ、全要素をひとつの線型リストにする。そして、そのポインタをたどりながらアクセスする。ただし、ある要素は、配列の直後の要素を指すようにする。結果として要素は方法 $1$ と同じ順序でアクセスされる。

方法 4: 方法 $3$ と同様だが、ポインタは方法 $2$ と同じく乱数で生成される。つまり各要素のポインタは、方法 $2$ においてその要素の次にアクセスされる要素を指す。結果として要素は方法 $2$ と同じ順序でアクセスされる。

一要素は $16$ バイトとする。プロセッサはレベル $1$ から $3$ までのキャッシュを持ち、キャッシュの大きさはそれぞれ、$32$KB, $256$KB, $4$MB であるとする（$1$KB = $2^{10}$ バイト、1MB = $2^{20}$ バイト）。

それぞれの方法で、同じ配列を繰り返し続けざまに何度もアクセスし、一アクセスあたりの平均時間を測定した。その時間は方法および、配列の要素数（$N$）に応じて変化し、以下の表のようになった。数字はアクセス回あたりの平均時間（プロセッササイクル数）を示す。

	$N \approx 2^{10}$	$N \approx 2^{22}$
方法$1$	$1.1$	$8.0$
方法$2$	$8.4$	$47.5$
方法$3$	$7.0$	$(x)$
方法$4$	$7.0$	$199.2$

以下のそれぞれの場合に、$2$ つの性能の違いに最も関係の深いプロセッサの機構は何か？上記の $(a)$ から $(c)$ の中から選んで答えよ。どれも関係しない場合は、なしと答えよ。根拠も示せ。

• (2-1) ( 方法 $1$, $N \approx 2^{10}$ ) と　( 方法 $2$, $N \approx 2^{10}$ )
• (2-2) ( 方法 $4$, $N \approx 2^{10}$ ) と　( 方法 $4$, $N \approx 2^{22}$ )
• (2-3) ( 方法 $1$, $N \approx 2^{22}$ ) と　( 方法 $2$, $N \approx 2^{22}$ )
• (2-4) ( 方法 $2$, $N \approx 2^{22}$ ) と　( 方法 $4$, $N \approx 2^{22}$ )

(3) 表中の $(x)$ の値はどの程度か？以下のうちから最もありそうな値を選び、理由を述べよ。

• (a) $8.0$ 付近。つまり，方法 $1$ と同程度。
• (b) $47.5$ 付近。つまり，方法 $2$ と同程度。
• ($c$) $199.2$ 付近。つまり，方法 $4$ と同程度。

题目描述

回答下列问题。

(1) 现代超标量处理器为提高程序的内存访问性能，通常具有以下机制：

• (a) 缓存；
• (b) 硬件预取；
• (c) 非阻塞缓存。

简要说明每种机制做什么，以及它如何改善内存访问性能。

(2) 考察访问某结构体数组全部元素的四种方法，以及访问顺序和数组大小对性能的影响。

• 方法 1：从数组开头到末尾顺序访问所有元素。
• 方法 2：随机生成数组下标，并按生成顺序访问；每个下标恰好生成一次。生成一个随机数约需 $7$～$8$ 个周期，且不需要内存访问指令。
• 方法 3：每个元素保存指向后继元素的指针，把全部元素组成一条线性链表；每个元素指向数组中紧随其后的元素，故访问顺序与方法 1 相同。
• 方法 4：与方法 3 相同，但指针按方法 2 的随机顺序设置，即每个元素指向方法 2 中下一次访问的元素，故访问顺序与方法 2 相同。

每个元素占 $16$ 字节。处理器有三级缓存，L1、L2、L3 容量分别为 $32\text{ KB}$、$256\text{ KB}$、$4\text{ MB}$，其中 $1\text{ KB}=2^{10}$ 字节，$1\text{ MB}=2^{20}$ 字节。对同一数组连续重复访问多次后，测得每次访问的平均处理器周期数如下：

	$N\approx2^{10}$	$N\approx2^{22}$
方法 1	$1.1$	$8.0$
方法 2	$8.4$	$47.5$
方法 3	$7.0$	$(x)$
方法 4	$7.0$	$199.2$

对下列每一组性能差异，从 (a)～(c) 中选择关系最密切的处理器机制；若均无关则答“无”，并说明理由。

• (2-1) 方法 1、$N\approx2^{10}$ 与方法 2、$N\approx2^{10}$；
• (2-2) 方法 4、$N\approx2^{10}$ 与方法 4、$N\approx2^{22}$；
• (2-3) 方法 1、$N\approx2^{22}$ 与方法 2、$N\approx2^{22}$；
• (2-4) 方法 2、$N\approx2^{22}$ 与方法 4、$N\approx2^{22}$。

(3) 从以下候选中选出表中 $(x)$ 最可能接近的值，并说明理由：

• (a) $8.0$，即与方法 1 大致相同；
• (b) $47.5$，即与方法 2 大致相同；
• (c) $199.2$，即与方法 4 大致相同。

Kai

(1)

(a)

キャッシュ

主記憶より小容量で高速な記憶にデータのコピーを保持し、時間的・空間的局所性を利用して平均アクセス時間を短縮する。アクセス遅延は階層や実装に依存し、必ずしも1サイクルではない。

(b)

ハードウェアによる先読み

過去のアクセス列から今後必要になるキャッシュラインを予測し、要求される前に下位階層から取り込む。連続・一定ストライドのアクセスでは、主記憶の遅延を先行転送で隠せる。

(c)

ノンブロッキングキャッシュ

ミスの処理中にも独立したアクセスを受け付ける。ヒットを処理するだけでなく、複数のミスを同時に処理できる構成では、独立したメモリアクセスの待ち時間を重ね合わせられる。

(2)

(2-1)

• 最も関係の深いプロセッサ機構：なし。
• 根拠：配列は $16\cdot2^{10}=16\mathrm{KiB}$ で L1 に収まり、繰り返し測定では両方法ともほぼヒットする。方法2では各アクセスのための乱数生成に7～8サイクルかかり、これが8.4サイクルの主因となる。

(2-2)

• 最も関係の深いプロセッサ機構：(a)。
• 根拠：小さい配列はL1に収まるが、大きい配列は $16\cdot2^{22}=64\mathrm{MiB}$ で、4 MiB のL3にも収まらない。ランダムなポインタ追跡では主記憶へのアクセスが多く、次のアドレスの計算も現在の読出し完了を待つ。

(2-3)

• 最も関係の深いプロセッサ機構：(b)。
• 根拠：方法1は連続アクセスなのでハードウェアが先のラインを予測して取り込める。方法2のランダムアクセスは予測しにくい。

(2-4)

• 最も関係の深いプロセッサ機構：(c)。
• 根拠：方法2では、先の読出しの結果を待たずに後続の添字を生成でき、複数のキャッシュミスを並行処理できる。方法4では各読出しの結果が次のアドレスを決めるので、ミスの待ち時間が直列に加算される。どちらも全要素を一巡する処理量は $O(N)$ であり、差の原因はこの依存関係にある。

(3)

最もありそうな値は (a)、8.0付近 である。

方法3もアドレス列は方法1と同じ連続列なので、ハードウェアによる先読みが働く。ポインタ依存は残るが、先読みが十分先行すれば各読出しは高速なキャッシュで処理される。小さい配列で測定された依存読出しの約7サイクルと、方法1の大きい配列の約8サイクルを考えると、選択肢の中では8.0が最も妥当である。厳密な値は先読みの距離や帯域などに依存する。