東京大学 情報理工学系研究科 電子情報学専攻 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$ と同程度。

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) と考えられる。