Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

4年間+2年間の工業大学・大学院で学んだ知識やためになることを投稿していきます

コンピュータアーキテクチャ 本番レベル模試(最終復習チェック)

こんにちは、ももやまです。

久しぶりにコンピュータアーキテクチャのお勉強をしたので、行基本変形サークルの皆さん [ @kit_matrix ] と一緒にアーキテクチャ分野の確認チェックとして本番レベル模試模試を作成しました。

記号問題は解答フォームから自動採点できるのでぜひチャレンジお待ちしております!

 

 

本番レベル模試に加えて60問1問1答も作成しましています。
復習の材料としてこちらもご覧ください。

www.momoyama-usagi.com

問題1.

以下の記述のうち、正しい文に〇を、誤った文に×を解答欄に記入しなさい。(配点 10)

(1) RISCプロセッサは、メインメモリにアクセスできるアクセスをロード命令のみに限定している。

(2) マイクロプログラム方式では処理が逐次的であるため、パイプライン処理のような制御には不向きである。

(3) スーパースカラ方式では、コンパイラの生成するコードに互換性があるため、アウトオブオーダー実行が可能である。

(4) CDやDVDは不揮発性である。

(5) デマンドページングとは、ページの参照要求が発生した際にのみメインメモリから補助記憶装置にページを読み込む方式であり、ページ転送に無駄がない。

(6) キャッシュコヒーレンシとは、キャッシュメモリとメインメモリ内のデータの一貫性のことを指す。

(7) ハードディスクのシーク時間はブロックの大きさに依存しない。

(8) Direct Memory Access (DMA) とは、バスを介さずに直接入出力装置とメインメモリの間でデータを転送することである。

(9) 2項演算において、アキュームレータマシンは1オペランド形式の例である。

(10) CPUからキャッシュメモリへのアクセス時に、命令やデータのコピーがキャッシュに存在しないために発生するブロックの置き換え時間をミスヒット時間と呼ぶ。 

 ★解説★

[10点満点:1ミス-2点]

(1) 解答:×

ロード命令、ストア命令の2つに限定しています。

(2) 解答:〇

パイプライン処理が向いているのはRISCプロセッサでよく使われるワイヤードロジック方式である(RISCはパイプライン処理に向いているため)。

(3) 解答:〇

設問通り。

(4) 解答:〇

CDやDVDが揮発性だったらどこから電源取ってくるんですか()

(揮発性=電力供給が途絶えたらデータ吹っ飛ぶもの)

(5) 解答:×

補助記憶→主記憶

(6) 解答:〇

設問通り。

(7) 解答:〇

「シーク時間→磁気ヘッドを磁気ディスクの目的の場所に動かす時間」なので、ブロック(データ量)には全く依存しない

(8) 解答:×

バス→CPU

(9) 解答:〇

設問通り。

(10) 解答:×

ミスヒット→ミスペナルティ時間

 

問題2.

以下の各問の解答として最適なものを選択肢の中から選択し、記号を解答欄に記入しなさい。(配点 16)

1.つぎのうち、2項演算において2オペランド形式よりも3オペランド形式の方が優れているといえる点はどれか。

    (a) レジスタ値の再利用
    (b) オペランド長
    (c) オペランドの数
    (d) CPU内のレジスタ数

2.つぎのうち、RISCの例であるものはどれか。

    (a) System/360
    (b) x86
    (c) R8C/Tiny
    (d) SPARC

3.記憶装置において、入出力要求から入出力が完了するまでの時間をなんというか。

    (a) シーク時間
    (b) 転送時間
    (c) アクセス時間
    (d) サイクル時間

4.VAX-11のアドレシングモードである「自動デクリメント」、「自動インクリメント」はつぎのうちどれに有効か。

    (a) stackの実現
    (b) queueの実現
    (c) 再帰関数の実現
    (d) プログラムの高速実行

5.各プロセスのページテーブルはどこに置かれるか。

    (a) CPUのMMU(Memory Management Unit)内
    (b) 各プロセスのプログラムの中
    (c) 補助記憶装置内
    (d) メインメモリの核の領域内

6.MIPSにおいて、NOP命令を代用する命令はつぎのうちどれか。

    (a) add $zero, $zero
    (b) addi $zero, $zero, 0
    (c) sll $zero, $zero, $zero
    (d) sll $zero, $zero, 0

7.つぎのうち、記憶階層においてアクセス速度が最も早いのはどれか。

    (a) メインメモリ
    (b) キャッシュメモリ
    (c) CPU内のレジスタ
    (d) 補助記憶装置

8.TLBがアドレス変換を高速化させることが可能な理由として正しい記述はどれか。

    (a) 優先度の観点から、メモリアクセスをより高速に行うことができるから。
    (b) TLB内の機構によりページフォルト率を大幅に下げることができるから。
    (c) これからの将来に最も長い時間参照されないページを予測することができるから。
    (d) 仮想ページ番号とページ枠番号の対を高速にアクセスできるレジスタに保存しているから。

 ★解説★

1.

解答:(a)

レジスタ値の再利用する場合、2オペランドだとレジスタ値が破壊されてしまう可能性があるため、2オペランドよりも3オペランドのほうが優れています。
(3オペランドだと破壊されない)

2.

解答:(d)

3.

解答:(c)

入出力要求から入出力が完了するまでの時間=アクセス時間

 

「アクセス時間=シーク時間+回転待ち時間+データ転送時間」

こちらも頭に入れておきましょう。

4.

 解答:(a)

5. 

解答:(d)

6.

解答:(d)

7.

解答:(c)

レジスタは記憶できる情報量こそ少ないですが、最速でアクセスすることができます。

8.

解答:(d)

TLBは「 仮想ページ番号とページ枠番号の対応づけ」をキャッシュすることで早くアクセスすることができます。

問題3.

MIPSのパイプライン処理について以下の問いに答えなさい。
(配点 11)

(1) MIPSではパイプライン処理として、実行命令を5つのステージに分類する。それぞれの名称をステージ順に記しなさい。

(2) パイプラインハザードが発生すると何が問題か。簡潔に説明しなさい。

(3) パイプラインハザードのうち、構造ハザードとは何か。また、それを回避するためにどのような措置が取られているか。簡潔に説明しなさい。

(4) つぎのアセンブリ言語のプログラムを実行することを考える。  

addi $s0, $s0, 1    # $s0 ← $s0 + 1
lw   $s1, 0($fp)    # $s1 ← メモリ
add  $t0, $s0, $s1  # $t0 ← $s0 + $s1
sw   $t0, -4($fp)   # $t0 → メモリ
sll  $s2, $t0, 2    # $s2 ← $s0 << 2

フォワーディングを行わず、データハザードに対してストールするパイプライン処理でプログラムを実行するとき、NOP命令は何回挿入されますか。

 
 ★解説★
1.[2点完答]
解答
1st:命令フェッチ(IF)
2nd:命令解読(ID)
3rd:命令実行(EX)
4th:メモリアクセス(MEM)
5th:書き込み(WB) 
 
2.[3点]
解答
つぎのサイクルで実行する予定の命令ができなくなり、遅延が発生し、処理速度が低下してしまう。
(赤色1点、青色2点の合計3点)
 
3.[3点]
解答
構造ハザードは、2つの命令が同じハードウェア資源にアクセスすることで競合が生じるハザードである。ハザードを回避するために、2つの命令に対し、それぞれ別々のメモリに格納している
(構造ハザードの説明2点、回避方法1点、回避方法は別解あるかも。)
 
4.[3点]
解答:4回 
つぎのようにパイプライン処理の様子を実際に書いてみるのがおすすめ。

f:id:momoyama1192:20190801113756g:plain

問題の2行目、4行目のプログラムでは、デコードに必要な変数(2行目は$s0、4行目は$t0)の結果が返されるまではデコードを行うことができないので、その分のnopを図に挿入する必要がある。

よって答えは4回。

問題4.

CISCとRISCのアドレシングモードの数について、それぞれの設計思想に基づいて説明しなさい。(配点  5)

 ★解説★

解答(参考までに)
CISCプロセッサは、アドレシングモードを多数用意することで1つの命令で様々なことをできるようにし、アセンブリ言語で書くプログラマの負担を軽くすることができるように設計された。
一方RISCプロセッサはアドレシングモードを少数にすることで、制御回路を設計の段階で簡単にし、命令の実行速度を向上させるように設計された。
(青色部分1.5点、赤色部分1点 [小数点切り上げ] 合計5点)
 

問題5.

ページングを用いた仮想記憶について、以下の問いに答えなさい。

1.仮想記憶はどのようにして実現されるか。

2.仮想アドレスが32bit、ページサイズが4KBの仮想記憶空間において、ページテーブルのエントリの大きさを8[Bytes]とする。このとき、つぎの(a)~(d)を求めなさい。なお、解答の際には bit(s)やKBなどの適切な単位を用いなさい。

(a) 仮想空間の大きさ
(b) ページ内変異のビット数
(c) 仮想ページ番号のビット数
(d) ページテーブルの大きさ

3.仮想記憶空間は2と同じものとする。このシステムにおいて、プログラムカウンタの値が16進数で0x005f4c88であったとする。このときのアドレス変換に関して、つぎの値を求め、それぞれ16進数で答えなさい。

(a) 仮想ページ番号
(b) ページ内変異

4.ページテーブル内の存在ビットの役割を述べなさい。

5.あるユーザープログラム実行時のメモリのアクセスの99.6%がTLBを介して行われ、ページテーブルを介したアクセスには0.5μ秒(500m秒)、ページフォルト時には10m秒のオーバーヘッドを伴うものとする。1回のメモリアクセスの遅れを平均0.0004μ秒(4n秒)以下に抑えるためには、ページフォルト率はいくら以下でなければならないか。

6.参照されるページ数が9、ページ枠の数を3とする。つぎに示す系列でページを参照するとき、ページ取り出しにデマンドページング、ページ置き換えにLRU(Least Resently Used)アルゴリズムを用いたときのページフォルト回数を解答欄の表を完成させることにより求めなさい。

ページ参照の系列:1,1,4,5,1,4,3,6,4,7,2,3,3,4,1,1,2,9

7.ページ置き換えアルゴリズムの最適解について、そのアルゴリズムの内容を説明しなさい。また、そのアルゴリズムが抱える課題を指摘しなさい。

 ★解説★

1.[3点]

解答:主記憶(メインメモリ)と補助記憶装置の2つを組み合わせること実現される。

(赤色要素に1点×3)

2.[2点 × 4 = 8点]

解答

(a) 4GB,  (b) 12bit  (c) 20bit  (d) 8MB

(a)

仮想アドレスの大きさがそのまま仮想空間の大きさになる。

なので、 2^{32} \mathrm{[byte]} =  4 \mathrm{[GB]} となる。

(b)

ページ内変異は、ページサイズのことである。
今回のページサイズは4KBなので、 2^{2} \cdot 2^{10} = 2^{12} より12ビットとなる。

(c)

仮想ページ番号のビット数=仮想アドレスのビット数(32)-ページ内変異(12)で求められる。よって20ビット。

(d)

仮想空間の大きさは 4GB、1つあたりのページテーブルの大きさは4KBなので、ページテーブルの数\[ 4 \times 2^{30} \div \left(4 \times 2^{10} \right) = 2^{20} \mathrm{[bytes]} = 1 \mathrm{[M]}\]また、今回のページテーブルのエントリの大きさは 8[bytes] なので、\[ 1 \mathrm{[M]} \times 8 \mathrm{[bytes]} = 8 \mathrm{[MB]} \]となる。

  

一応確認

 1 \mathrm{[byte]} 2^{3} \mathrm{[bit]}
 1 \mathrm{[KB]} 2^{10} \mathrm{[bytes]}
 1 \mathrm{[MB]} 2^{10} \mathrm{[KB]}
 1 \mathrm{[GB]} 2^{10} \mathrm{[MB]}
 1 \mathrm{[TB]} 2^{10} \mathrm{[GB]}

です。

3.[3点 × 2 = 6点]

2より仮想ページ番号が20ビット(16進数5桁分)、ページ内変異が12ビット(16進数3桁分)である。さらにPCの値の上位部分(5桁)が仮想ページ番号、下位部分(3桁)がページ内変異となるので、

仮想ページ番号:0x005f4
ページ内変異:0xc88

となる。

 

4.[4点]

存在ビットは、ページが主記憶(メインメモリ)の中に存在するかどうかを示すビットである。さらに、MMUが主記憶内にページが存在しないことを検知し、ページフォルト割り込みをすることで必要なページを読み込めるようにするため。

緑色要素に3点赤色要素に1点

 

(ちなみにOSは、MMUからのページフォルト割り込みによってページフォルトの発生を確認することができる。)

 

5.[4点]

TLBを介したアクセスは高速なので時間を無視できる。

ページフォルト率を  x %とすると、\[
99.6 \times 0 + 0.4 \times 5.0 \times 10^{-7} + x \times 1.0 \times 10^{-2} \leqq 100 \times  4.0 \times 10^{-9} \]となる  x を求めればよい。\[
2.0 \times 10^{-7} + 1.0 \times 10^{-2} x \leqq 4.0 \times 10^{-7} \\
1.0 \times 10^{-2} x \leqq 2.0 \times 10^{-7} \\
x \leqq 2.0 \times 10^{-5} 
\]より、ページフォルト率が  2.0 \times 10^{-5} \mathrm{[\%]} 以下になればよい。

(※  2.0 \times 10^{-5} \mathrm{[\%]} と  2.0 \times 10^{-7} は同じ)

採点基準:立式に2点、答えに2点

 

6.[3点]

つぎのようなページテーブルを書くとよい。
LRUアルゴリズムなので、一番長く参照されていないページを捨て、捨てた部分に参照するページを読み込めばよい。

f:id:momoyama1192:20190801113446g:plain

合計12回が答え。

採点基準:ページテーブルが書けて2点、答えに1点

 

7.[2点×2=4点]

最適解:将来最も参照されないページを置き換えるアルゴリズム(OPTアルゴリズム)
課題 :将来の予測をするのは非常に困難である。

各2点。

 

ページテーブル、ページフォルトなどについてはこちらの記事にて説明しているので苦手だなと思った方はこちらの記事を御覧ください。

www.momoyama-usagi.com

問題6.

キャッシュメモリに関して、つぎの文章を読んで以下の問いに答えなさい。
(配点 25)

 

 キャッシュメモリとは、 (    A    ) が (    B    ) を参照する前に、まずキャッシュメモリを参照することで読み書き速度の遅い (    B    ) 装置の参照回数を削減し、システム全体の処理速度が低下する問題を解消する装置である。

1.上の文章の空欄 (    A    ), (    B    ) に当てはまる語句を答えなさい。

2.キャッシュメモリを命令キャッシュとデータキャッシュに分離し、それぞれの制御機構やアドレスバス、データバスを別々に実装したメモリアーキテクチャをなんというか。

3.2のアーキテクチャの利点を3つ述べなさい。

4.キャッシュメモリのマッピング法として、セット連想マッピング(セット・アソシアティブ方式)がある。この方式について他のマッピング方式の長所について言及しながら説明しなさい。

5.キャッシュが有効に働く理由を命令やデータの参照の局所性の観点から説明しなさい。

6.キャッシュメモリのブロック置き換えアルゴリズムとしてLRUが有効に働く理由を参照の時間的局所性から説明しなさい。

7.DRAMとSRAMのうち、一般的にキャッシュメモリに利用されているのはどちらか。理由と合わせて答えなさい。

 ★解説★

1.[2点×2]

解答

A:プロセッサ
B:主記憶

 

2.[2点]

解答:ハーバードアーキテクチャ

 

3.[2点×3=6点]

  • キャッシュメモリへの 命令アクセスとデータアクセスが競合しないので、キャッシュとCPUの間の転送容量が大きくなる
  • 命令の参照の局所性が安定して高くなるため、ミスペナルティ時間を減らすことができる
  • 読み出し専用の命令なので、メインメモリへの更新だけの機構が不要である

4.[5点]

解答

セット連想マッピング(セット・アソシアティブ方式)は、セットの選択にキャッシュ検索時間が早く実装が容易な直接マッピング(ダイレクトマップ方式)セット内のブロックの割り当ての自由度が高い完全連想マッピング(フルアソシアティブ方式)両者の長所を取り入れた中間的なマッピングである。

採点基準:青色要素に2点×2、赤色要素は1点

 

セット連想マッピング(セット・アソシアティブ方式)は、直接マッピング(ダイレクトマップ方式)と完全連想マッピング(フルアソシアティブ方式)の中間的な存在であることを頭に入れておきましょう。

 

5.[3点]

参照の局所性(時間的局所性、空間的局所性)から、アクセスした近くの命令およびデータは、近い間に再び利用される可能性が高く、ミスヒットを少なくできるから。

(緑色要素が重要)

 

6.[3点]

ページの参照には、最近参照されたページは将来再び参照される可能性が高いという時間的局所性があるため、「過去最も長い間参照されなかったページを追い出す」LRUアルゴリズムは、「将来最も長い期間参照されないページを追い出す」理想的なアルゴリズムの近似となるため。

採点基準:青色に2点、赤色に1点

 

7.[3点]

システム全体の処理速度が低下する問題を解消させるために高速な読み書きが必要なため、高速に読み書きができるSRAMが一般的に利用される。

採点基準:青色に2点、赤色に1点

 

さいごに.

今回はコンピュータアーキテクチャ分野の確認チェック用に本番レベル模試を行基本変形サークルの皆さんと作成をしました。

 60問1問1答とセットでコンピュータアーキテクチャの良い復習材料になれば幸いです。