東京大学 情報理工学系研究科 電子情報学専攻 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)

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

( プリフェッチとも言う。) CPU が今後のデータアクセスを予測して自動的にメインメモリからキャッシュにデータをおく。メインメモリよりも高速にアクセスできるキャッシュからデータを利用できる。

($c$)

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

ある処理に必要なデータをメインメモリにまで取りに行く間に、他の処理に必要なデータをキャッシュから取る仕組み。これにより、処理全体でデータを取りに行く時間が短縮できる。

(2)

(2-1)

• 最も関係の深いプロセッサ機構： (b)
• 根拠： 方法 $1$ で使うデータが周期的であり先読みが非常に効果的だから。一方、ランダムに添え字が選ばれる方法 $2$ に対して有効ではないから。

(2-2)

• 最も関係の深いプロセッサ機構： (a)
• 根拠： $N \approx 2^{10}$ のとき、構造体は $16 = 2^4$ バイトだから全て合わせて約 $2^{14}$ バイト。$L1$ キャッシュは $32$KB $\approx 2^5 \times 2^{10} = 2^{15}$ バイトだからすべて $L1$ の構造体は $L1$ キャッシュに載る。一方、$N \approx 2^{22}$ のときは $L1$ キャッシュにすべての構造体が載らないから。

(2-3)

• 最も関係の深いプロセッサ機構： (b)
• 根拠： (2-1) と同様の理由

(2-4)

• 最も関係の深いプロセッサ機構： なし
• 根拠： 配列にアクセスする時間計算量は $O(1)$ だが、線形リストにアクセスする場合は $O(N)$ だから差がついている。どちらも要素がキャッシュに載らないほど大きいのでプロセッサレベルの問題ではない。

(3)

最もありそうな値 ： (b)

根拠

キャッシュにはすべての要素が載らないが、規則的に要素にアクセスするのでハードウェアの先読みから方法 $4$ よりは高速にアクセスできる。一方同じ規則的なアクセスである方法 $1$ は配列の添字でアクセスしているのに対して、方法 $3$ はより低速な線形リストでアクセスしている。そのため方法 $1$ ほど早くはなく (b) と考えられる。