東京大学 情報理工学系研究科 電子情報学専攻 2014年8月実施 専門 第2問
Author
Description
以下の問いに答えよ。
(1) 現代的なスーパースカラプロセッサは、プログラムのメモリアクセス性能をあげるために以下を含むいくつもの機構を備えている。
- (a) キャッシュ
- (b) ハードウェアによる先読み
- (
) ノンブロッキングキャッシュ
それぞれの機構が何をするか、およびそれぞれがメモリアクセス性能をあげるためにどう貢献するのかを簡潔に説明せよ。
(2) ある構造体の配列および、その全要素にアクセスするプログラムを考え、アクセスの方法や配列の大きさが性能に与える影響について考察する。具体的には、以下の方法
方法 1: 全要素を逐次的に、配列の先頭から終わりまでアクセスする。
方法 2: 配列の添字を乱数で生成し、その添字の要素に、それらが生成された順でアクセスする。配列の全ての添字がちょうど一度ずつ生成されるとする。なお、乱数ひとつを生成するのにかかる時間は
方法 3: 各要素に後続の要素を指すポインタを持たせ、全要素をひとつの線型リストにする。そして、そのポインタをたどりながらアクセスする。ただし、ある要素は、配列の直後の要素を指すようにする。結果として要素は方法
方法 4: 方法
一要素は
それぞれの方法で、同じ配列を繰り返し続けざまに何度もアクセスし、一アクセスあたりの平均時間を測定した。その時間は方法および、配列の要素数（
| 方法 | ||
| 方法 | ||
| 方法 | ||
| 方法 |
以下のそれぞれの場合に、
- (2-1) ( 方法
, ) と ( 方法 , ) - (2-2) ( 方法
, ) と ( 方法 , ) - (2-3) ( 方法
, ) と ( 方法 , ) - (2-4) ( 方法
, ) と ( 方法 , )
(3) 表中の
- (a)
付近。つまり，方法 と同程度。 - (b)
付近。つまり，方法 と同程度。 - (
) 付近。つまり，方法 と同程度。
Kai
(1)
(a)
キャッシュ
(b)
ハードウェアによる先読み
( プリフェッチとも言う。) CPU が今後のデータアクセスを予測して自動的にメインメモリからキャッシュにデータをおく。メインメモリよりも高速にアクセスできるキャッシュからデータを利用できる。
(
ノンブロッキングキャッシュ
ある処理に必要なデータをメインメモリにまで取りに行く間に、他の処理に必要なデータをキャッシュから取る仕組み。これにより、処理全体でデータを取りに行く時間が短縮できる。
(2)
(2-1)
- 最も関係の深いプロセッサ機構： (b)
- 根拠： 方法
で使うデータが周期的であり先読みが非常に効果的だから。一方、ランダムに添え字が選ばれる方法 に対して有効ではないから。
(2-2)
- 最も関係の深いプロセッサ機構： (a)
- 根拠：
のとき、構造体は バイトだから全て合わせて約 バイト。 キャッシュは KB バイトだからすべて の構造体は キャッシュに載る。一方、 のときは キャッシュにすべての構造体が載らないから。
(2-3)
- 最も関係の深いプロセッサ機構： (b)
- 根拠： (2-1) と同様の理由
(2-4)
- 最も関係の深いプロセッサ機構： なし
- 根拠： 配列にアクセスする時間計算量は
だが、線形リストにアクセスする場合は だから差がついている。どちらも要素がキャッシュに載らないほど大きいのでプロセッサレベルの問題ではない。
(3)
最もありそうな値 ： (b)
根拠
キャッシュにはすべての要素が載らないが、規則的に要素にアクセスするのでハードウェアの先読みから方法