計算機工学 II 授業ノート 第 1 回 ( ) 担当 : 寺田

Transcription

1 計算機工学 II 授業ノート 第 1 回 ( ) 担当 : 寺田 担当教員 : 寺田努 ( 工学研究科電気電子工学専攻准教授 ) [email protected] ( 質問等はメールでお願いします ) TEL: 居室 : B-401 授業日程 :4/10, 4/17, 4/24, 5/1, 5/22, 5/29, 6/5, 6/12 6/19, 6/26, 7/3, 7/10, 7/17 の 13 回程度を予定教科書 : コンピュータアーキテクチャ ( 中島康彦著 ) 成績評価 : 期末試験 + 授業内小テスト & レポートの合計点数 (1 : 1) 計算機工学とは何か? ディジタル計算機の心臓部である中央処理装置 (CPU) を中心に, ハードウェとの接点である計算機アーキテクチャについて習得する ( シラバスより ) コンピュータにおけるさまざまな要素 ( どのようなデータ形式を採用するか? どのようなデータ蓄積方法を採るか? どのようにプログラムを実行するか? など ) において, 優れた実現手法や必須の項目に関して, 基本的で共通的な事項を開発の歴史や考え方も交えて, 詳しく説明する. 低コストで要求を満たすためにはどのような工夫がいるのか? その時代のコンピュータシステムに対する要求に対して, どのように仕様が決まったのか? どのようなライバルアーキテクチャが存在し, なぜそれを蹴落として今のアーキテクチャがあるのか? ハードウェアとソフトウェアの機能分担は? 開発者たちは, 少しでも性能のよいコンピュータを作るために日々新しいアイデアを考え出す努力を重ねている. 複数の CPU を使って計算を速く行うためにはどのようなプログラムの書き方が望ましいか, キャッシュメモリの内容の整合性を保つにはどのような実装がよいか, など. 多くのアイデアを出すことができるのは人間の創造的な思考能力である. 複数の選択肢があるときに, さまざまな条件を考慮して最適なものを選ぶ力 新しいものが出てきたときに, なぜそれが必要なのかを判断する力

2 計算機の誕生と発展初期のコンピュータのプログラム供給方式は, 紙テープ読み取りや配線盤に直接配線を行う形. デメリット 紙テープ : 紙テープの読み取り速度に限界がある 配線盤 : プログラムの変更に多大な労力と時間を要する ノイマン型計算機 ( プログラム内蔵方式 )1945 年 プログラム もデータと一緒に計算機の中に格納. 中央処理装置 主 記憶装置 という計算機の基本構成を確立 計算機アーキテクチャとは プログラマから見たシステムの属性および外部仕様 それを効率的に実現する内部仕様ハードウェアの物理的な違いやメーカの違いにかかわらず, 同一のプログラムが実行できるといった恩恵が受けられる.

3 授業内レポート第 1 回学籍番号名前 (1) 下記の単語のうち, 簡単に説明できるものに を, 説明はできないが聞いたことがあるものに をつけよ. 2 進数 10 進数機械語ギガバイトテラバイトスタック パイプライン再起呼出し浮動小数点 2 の補数仮想記憶排他的論理和 分岐予測コンパイラ投機実行 C# java android (2) 下記のサービスのうち, 実際に登録して利用しているものに を, 内容を知っているものに をつけよ. mixi GREE Gmail モバゲータウングルーポン食べログ facebook Twitter instagram Google Calendar Flicker LINE note はてな (3) 計算機アーキテクチャによって, ハードウェアの物理的な違いやメーカの違いにかかわらず, 同一のプロ グラムが実行できると何がうれしいかを 1 つ述べよ. なお, 新規ソフトウェアの開発 応用ソフトウェアの 開発 価格性能比 コンピュータファミリー といった言葉を 1 つ以上含めて記述すること (4) 授業に関して, 希望や質問等があれば記述してください.

4 計算機工学 II 授業ノート Vol.2( ) 担当 : 寺田 1. 基本素子と情報の表現計算機における情報の表現方法計算機内部では 1 と 0 しか用いることができないため,0 と 1 で符号化したものを文字や数字として用いる. 特に数字は 0 と 1 のみで表現可能な 2 進数を用いるのが普通. 計算機で数や文字を処理する際の 1 まとまりの処理単位をと呼ぶ. これを長くすると.. メリット : デメリット : 大多数の用途に対して効率的かつ経済的に利用できる仕様を追求することが必要. データの種類と語長表現したいもの : 整数, 有理数, 実数, 複素数, ベクトル, 行列, グラフ, 図形, 品番, 品名, 人名, 住所, 単価, 売上高, 利率 必須だと考えられるのは?: 文字,2 進整数,2 進浮動小数点数,10 進整数 それぞれの語長は? 2 進整数 :32 ビットあればだいたい OK( 理論上は 4GByte まで扱える ), 最近は 64 ビットも 文字 :1 文字,8 ビット?16 ビット? 2 進整数の表現正の整数のみを扱う場合 : 各ビットで表現される 2 値系列に対し, そのまま左端を最上位桁, 右端を最下位桁とみた 2 進数に対応付ければよい. 249(10 進 ) (2 進 ) 正負の整数を扱う場合 : いくつかの対応付けの方法がある. 考慮すべきことは [1] 正負の判定が容易なこと [2] 一意的に表されること [3] 数 M の表現から-M の表現が簡単に求まり, 加算が容易であること (1) 符号付絶対値系 最上位ビットで正負を表す.0 の表現にが生じる. 加減算が複雑になる. 1

5 数 符号付絶対値系 1の補数系 2の補数系 (2) 1 の補数系 ** 補数とは ** N 進法において, ある数 a に足して全体の桁が1つ上がるような最小の自然数を N 進法における a に対する という. N 進法において, ある数 a に足しても桁が上がらない最大の自然数を N 進法における a に対する という. ** 補数の説明終 ** 2 進数において,1 の補数とは 0 と 1 を単純に入れ替えたものである. 1 の補数系では, 正の数 M はその 2 進数で, 負の数 -M は M の 1 の補数で表す. 結果的に最上位ビットが正 負を表すことになる.0 の表現に +0 と -0 の 2 通りが生じる. 2

6 加算の手順 ( 減算は補数をとってから加算 ) [1] そのまま足す [2] [3] (3) 2 の補数系 正の数 M はその 2 進数で, 負の数 -M は M の 2 の補数で表す. 結果的に最上位ビットが正負を表すことに なる.0 の表現は一意. 加算の手順 [1] そのまま足す [2] 算術シフト 論理シフト : 算術シフト : 算術シフトにおけるシフト方式 2の補数系で数を表す 2 値系列 X=(xn-1, xn-2,, x0) において, 左シフトした数 XL と右シフトした数 XR は次のように表現できる XL= XR= 符号拡張 ビット数の異なる数を加減算したい場合には長さをそろえる処理が必要. ビット長の短い数をビット長の長い数に合わせるには, 上位桁に よい. を挿入していけば 3

7 授業内レポート第二回学籍番号名前 (1) 2 の歩数系で数を表す 2 値系列 X=(xn-1, xn-2, xn-3,, x0) において, 左算術シフトを XL, 右算術シフトし た数 XR を示せ. その際, オーバフローおよびアンダーフローの条件を示すこと. また, なぜその条件に なるのかを考えよ. (2) ( )2=154 に (1010)2C=-6 を加算せよ. 計算の途中経過も記すこと. 添え字の 2 や 2C はそれ ぞれ, 正しかない 2 進数系,2 の補数系を表す. (3) コメントや質問があれば書いてください. 4

8 計算機工学 II 授業ノート Vol. 3 担当 : 寺田 コンピュータにおいて小数の表現を行う場合,10 進数の場合と同様に固定小数点と浮動小数点がある. ここ では特に浮動小数点について説明する. 浮動小数点数 実数は, 一般には有限の桁数では表現できない. 実際の応用では何桁かの有効数字が得られれば問題ない. そこで実数のによる表現を用いる. ただし, m を仮数,e を指数,β を底,p を精度と呼ぶ. d 0 0 のとき, されているという. このとき表現は一意に定まる. 表せる数 浮動小数点で表せる数は, の間に等間隔で並んでいる. 間隔は正規化された浮動小数点数の最下位桁の 1 の値. 実際の数値は点在する表現可能な数の一番近いところに近似されるため, その最大誤差は間隔の半分となる. 値域 正の正規化浮動小数点数で表せる最大値 F max 最小値 F min F max F min = つまり, 浮動小数点数の値域は z, z -F min < z < F min のとき z < -F max および F max < z のとき IEEE 標準の浮動小数点数形式 IEEE754 と IEEE854 の 2 つが 1980 年代に検討 制定された.IEEE754 は底を 2 のみ許容. 単精度 拡張単精度 倍精度 拡張倍精度 p e max e min 指数のビット数 語長

9 指数部の割当て可能数を 2 減らし, 特殊な値の表現を用意している. 指数部 仮数部 意味 e=e min -1 f=0 ±0 e=e min -1 f 0 0. f 2 e min e min e e max f 1. f 2 e e=e max +1 f=0 ± e=e max +1 f 0 NaN 3-2

10 授業レポート第三回学籍番号名前 (1) 1 語 32 ビットで浮動小数点数 m β e を表現する.m と e の絶対値に割り当てられるビット数が 30 ビット ( つ まり m と e はそれぞれ符号付絶対値系であり, 符号に 2 ビット消費する ) であるとき,β=2,m が 24 ビット, e が 6 ビットのときを例に,β の大きさ, および m と e のビット数という 3 つの値の関係を説明せよ. (2) IEEE754 の倍精度の方式と 符号ビットが 1 ビット, 整数部分が 16 ビット, 小数部分が 47 ビット の固 定小数点形式について, 表現できる数の絶対値の最大値を比較せよ. (3) リクエストや質問等があれば書いてください. 3-3

11 計算機工学 II 授業ノート Vol.4 担当 : 寺田 算術演算回路の構成法 32 ビットで表された 2 数の加減乗除を行う演算回路は, 入力数, 出力数 の組合せ論理 回路で構成可能 現実的には無理 ( 真理値表さえ作れない ). したがって, 人間が筆算を行うのと同様の工夫が必要. 加減算回路 2 の補数系では減算は補数を加算すればよい を構成すればよい. n ビットの加算器は,3 入力の 1 ビット加算器 ( 全加算器 :full adder) を基本回路として構成. 加算する 2 数 :a i,b i, 下位桁からの桁上げ :c i とし, 和 :s i, 上位桁への桁上げ :c i+1 とすると s i = c i+1 = g i :,p i : 順次桁上げ加算器 桁上げを各段で待つ必要があるため遅い パラレルプリフィックスアダー 各桁の桁上げ信号は, を使わなくても計算可能. これを利用して桁上 げ情報を先に伝播する加算器をと呼ぶ. 4-1

12 左図のように加算器を修正すると, 右図のような桁上げ先見加算器が構成できる. c i+2 = L をという. L を多段化 (P65 図 3.3) したり,L を 4 ビットに拡張することでさらなる高速化が可能. 乗算回路 A=(a n-1, a n-2, a 0 ),B=(b n-1, b n-2, b 0 ) (2 の補数系 ) のとき A B= A が正の時と負の時に分けて考えれば証明は容易 逐次型乗算機 乗数 A と部分和 P を 1 ビットずつシフトしながら部分積 a i B を部分和 P に加算していくことで計算する. 加算が 1 クロックとすると,n ビットの乗算に n クロックかかる 4-2

13 並列乗算器 逐次型乗算器の加算を並列加算器で行う. 1 ビットずつの乗算を何ビットかまとめて行うことで高速化が可能. 2 ビットの場合, を求めて部分和に加える. カッコ内は を とるが, を作成するのはコストが高い. ブースのアルゴリズム 乗数の中に連続した 1 が含まれる場合, 計算回数を減少させられる. 一般に, ブースのアルゴリズムは下記のように表現される. a i a i-1 加数 2 ビットずつにした場合は下記のとおり a i+1 a i (a i-1 ) 加数 4-3

14 除算回路 除数 D, 被除数 X が n ビットの符号なし正小数であるとする. このとき除算は が成立する Q と R を求めること. 筆算と同様に考え, 商を (Q=0.q 1 q 2 q n ), 各段の計算結果を r i とすると 引き戻し法による除算 となる. (1) R と Q を連結して左に 1 ビットシフトする (2) とし,R が負なら (3) へ, 正ならば (4) へ進む (3) として (1) に戻る (4) として (1) に戻る 最悪の場合回の加減算が必要になる. 引き放し法による除算引き戻し法 (3) における元に戻す作業をせずに次のステップで補償する方法 (1) R と Q を連結して左に 1 ビットシフトし, 負ならば (2) へ, 正ならば (3) へ (2) として (1) に戻る (3) として (1) に戻る 加減算回数は n 回. 商の -1 は 0 で表しておき, 最後に正しい 2 進数に変換する方法がポピュラー. 浮動小数点演算回路整数演算とシフトの組合せ整数演算 : 乗除算は加減算にくらべてはるかに複雑浮動小数点演算 : 加減算では逐次的に行う処理が多いため, 乗算が加減算と同程度か高速. 4-4

15 浮動小数点の加減算手順 (1) 加数と被加数の指数の差を求める (2) 大きいほうの指数を, 答の仮の指数とする (3) 指数が小さいほうの仮数を, 指数の差だけ右にシフトする (4) 仮数の加減算を行う (5) 答の正負の符号を定める (6) 演算結果の仮数の正規化に必要なシフト桁数を求める (7) 仮数を左にシフトするとともに丸めを行う (8) シフト数だけ仮の指数を補正する 丸めの処理には, が用いられることが多い. 浮動小数点の乗除算 (1) 仮数の乗除算を行う (2) 指数の加減算を行う (3) 答の正負の符号を定める (4) 結果に応じて仮数を 1 ビットシフトするとともに丸めを行う (5) 結果に応じて指数を 1 だけ補正する 4-5

16 授業内レポート第四回学籍番号名前 (1) を, ブースのアルゴリズムを使って解く様子を記述せよ. アルゴリズム動作がわかるように書 かれていれば形式は問わない. (2) を引き戻し法と引き放し法それぞれで計算せよ (3) 授業に関するリクエストやその他質問等があれば書いてください. 4-6

17 計算機工学 II 授業ノート Vol. 5 ( 担当 : 寺田 ) 3. プログラミングコンピュータは 2 進数の並びでないと命令を理解できないが, 人間は 2 進数命令を直接理解するのが困難なので,C 言語,Java など人間に理解しやすいを用いてコンピュータに処理を実行させる. 命令語の構成命令とオペランド計算機命令の基本形 : 実行すべき と を指定すること a = b + c,a = b c など 演算を指定する部分 を, 演算の対象となるデータを と呼ぶ. a = b op c (2 つのオペランド b,c に演算 op を施し, 結果を a とする ) アドレスで書くと,A [B] op [C] (A:, B, C: ) 命令数 :EDSAC では 18 個, 最近の CISC では 200 以上, 最近の RISC では 100 程度 計算機の構成方法 (1) アキュムレータ型計算機 A [B] op [C] において,A = B = 例えば a = b + c を計算するには,load B,add C,store A の 3 命令が必要 このような形を と呼ぶ 4-1

18 n アドレス命令 :1 つの命令に n 個のアドレスをもたせる命令 n が大きい : 処理が. あらゆる命令を用意するため. n が小さい : 命令数が. 処理ステップ数が. 例えば 3 アドレス命令だと,a = b + c は add A, B, C といった形で 1 命令による表現が可能 (2) レジスタ型計算機 アキュムレータ型におけるアキュムレータを汎用にし, 複数用意したもの. A [B] op [C] における A,B,C が. そのため, 命令あたり のオペランド数は. (3) スタック型計算機 4-2

19 レジスタの代わりに オペランドが を用いたもの. スタックの上 2 つで演算を行うため, 演算命令には 命令の種類 : レジスタ 主記憶の間でデータを移動する命令. : 加減乗除の四則演算を行う命令. 演算結果の正 負 0 オーバフローの有無によりを設定するものもある.2 進整数と 10 進整数, 浮動小数点数などの変換命令も含まれる. :2 変数の論理関数 (AND,OR,EOR),1 変数関数 NOT 等の命令. : 算術シフトや論理シフトを行う命令. : 命令の実行番地を変える命令. その他 : 入出力やシステム制御に関するもの. オペランドの指定方法主記憶アドレス : アドレスを指定する ( 指定方法は後述 ). 汎用レジスタ : レジスタ番号を指定する. 特殊レジスタ ( プログラムカウンタ, プログラム状態語, 制御レジスタなど ): 専用の命令が用意されていてことが多い. 値 ( レジスタの一定値の増減や, シフトの桁数指定など ): 直接指定するため高速に処理可能. 即値形式. 4-3

20 授業内レポート第 5 回学籍番号名前 (1) アキュムレータ型計算機, レジスタ型計算機, スタック型計算機の特徴を簡単にまとめよ. また, 現在レ ジスタ型計算機が主流である理由を説明せよ. (2) 授業に関するリクエスト等があれば書いてください. 4-4

21 計算機工学 II 授業ノート Vol.6 ( 担当 : 寺田 ) 命令の実行制御演算処理部と実行制御部演算処理部 : 演算回路 ( 前回説明したもの ) や, 汎用レジスタ, プログラムカウンタ等の専用レジスタがバスに接続されたもの. S,D : バスを表し, 共有される.S1,S2 は演算回路入力用,D は演算回路出力用 ALU :Arithmetic Logic Unit. 演算回路 Rn : 汎用レジスタ PC : プログラムカウンタ MAR :Memory Address Register. オペランドの実アドレスが格納される MDR :Memory Data Register. 読み出したオペランドが格納される :. これを開閉してデータの流れを指定する. 例えば a, b, c, d が開いているとき には,R0 と R1 の内容を処理 (ALU への命令が加算の場合は加算 ) した結果が R2 に設定される. 6-1

22 実行制御部 : 制御信号の系列を加えることでする. 実行制御部の処理 (1) PC( プログラムカウンタ ) が指すメモリアドレスから命令を読み出し,PC を次命令まで進める. (2) 命令を解釈し, レジスタファイルと呼ぶレジスタの集合体から必要なデータを読み出す. また, 引き続くステージの制御信号を準備する. (3) 演算器において算術 / 論理演算 / シフトなどを行う. ロード / ストア命令の場合はアドレス計算のみを行う. 分岐命令の場合は条件コードに応じて PC に分岐先アドレスを書き込む. (4) 演算命令の場合は何もしない. ロード / ストア命令の場合はアドレス計算結果を用いてメモリを参照しデータを読み書きする. (5) 演算結果やロード結果をレジスタファイルに書き込む. パイプライン実行 命令実行における個々のステップはそれぞれの処理を行う回路ユニットが存在している. : ある命令の処理終了後に次命令を処理する. 下記のようにユニット稼動に無駄が生じる サイクル 命令 1 F D E M W 命令 2 F D E M W : それぞれのステップの独立性を応用して次々に命令を投入 実行する. 高速化の有 力手法. 分割された処理単位のそれぞれを プの多い命令のステップ数. と呼ぶ. ステージ数は, 最も実行ステッ 6-2

23 サイクル 命令 1 F D E M W 命令 2 F D E M W 命令 3 F D E M W 命令 4 F D E M W 命令 5 F D E M W 命令 6 F D E M W 命令 7 F D E M W 命令 8 F D E M W 理想的に動作した場合, パイプライン処理は最大 せず,5 ステージ存在する命令が少ないため, 実際はもう少し差は小さい ) の実行速度 ( 逐次処理では無駄なステージが存在 動作周波数 パイプラインを実現するためには, 各ステージの処理時間を均等にする必要がある. ステージの処理時間を (1 クロック ) と呼び,CPU の動作周波数は 1/ [Hz] である. MIPS:million instructions per second.1 命令あたりの平均命令実行時間 (100 万分の 1 秒 ).CPU の性能表現によ く用いられる. 測定に使用するプログラムやデータに依存する. パイプステージ 詳細な説明は教科書 p.44~52 を読んでおくこと. 6-3

24 授業内レポート第六回学籍番号名前 (1) あるプログラムをシミュレータで実行して測定したところ,4 クロックで実行できる命令が 40%,5 クロ ックで実行できる命令が 60% の頻度で起こっていた. この場合, 逐次実行した場合の 1 命令あたりの平均所 要クロック数はいくつになるか. (2) (1) のプログラムを逐次処理で実行した場合に比べて,5 ステージ (F D E M W) のパイプライン処理を実装 した場合, 何倍の速度で実行できるか. ただし, パイプラインはすべてのステージが命令を実行している定常 状態にあるとし, パイプラインが乱れるようなことはないと仮定してよい. (2) 授業に関するリクエストやその他質問等があれば書いてください. 6-4

25 計算機工学 II 授業ノート Vol.7( 担当 : 寺田 ) キャッシュメモリプロセッサの高速化 (1 サイクル 10ns など ) に対して主記憶のアクセス時間 (DRAM で 100ns 近辺 ) との落差が生じる. 高速で大容量な主記憶を用意することは現時点では困難であるため, を CPU に設ける. キャッシュメモリ : を保持しておく高速なメモリ. ヒットすれば低速な主記憶へアクセスすることなくデータの読み出しが可能. プログラムの時間的 空間的局所性を利用してヒット率 ( アクセスする命令やデータがキャッシュメモリに存在する確率 ) を高める. キャッシュアクセス時間 10ns, 主記憶装置アクセス時間 200ns, ヒット率 95% だとすると, 平均メモリアクセス時間は キャッシュメモリの仕組みを実現するにあたっての検討事項 キャッシュメモリと主記憶の対応付けと検索を行う機構 キャッシュの置き換えの機構 キャッシュへの更新を主記憶に伝播する機構 ブロックとマッピング ブロック : キャッシュメモリに主記憶の写しを作る際の写しの大きさの単位 ブロック枠 : キャッシュメモリにおける, ブロックを格納するための区画 ブロックが大きい 管理が簡単, ヒット率低い, 書き換えコストが高い ブロックが小さい 効率がよい, 主記憶との対応付けが大変 現在は, 通常 16,32,64 バイト程度がブロックの大きさとして採用されている. 8-1

26 ディレクトリ : キャッシュメモリに主記憶のどのブロックが割り当てられているかを高速に検索するための 索引. ディレクトリ内の検索には連想記憶などの高速な機構を採用する. マッピング方式 主記憶ブロックに対してどのブロック枠を割り当てるかを決める方式がいくつかある. ( 以下, ブロックサイズ :64 バイト, キャッシュ容量 :64K バイト, 主記憶容量 :4G バイト ) : 主記憶の任意のブロックをキャッシュの任意のブロック枠にマッピングでき る方式 制約がないためキャッシュメモリの利用効率が高く, ヒット率も高い ディレクトリ検索の効率が悪い. 8-2

27 : 主記憶の各ブロックに対するディレクトリのエントリが一意に決まる方式 下記の例では, 主記憶を 1024 の群に分け, 主記憶ブロックの番号 i に対してブロック枠 j=i mod 1024 を割 り当てる. ディレクトリの検索を必要としない 特定の群の主記憶ブロックにアクセスが集中する可能性が高い : 両方式の中間にあたる方式 キャッシュメモリのブロック枠を n 行 m 列に構成する. 主記憶ブロックも m 個の群にわけ, それぞれを 1 列のブロック枠に割り当てる. ある主記憶ブロックがどの群に属するかは検索しなくてもわかる ディレクトリ検索は群内に限られる 8-3

28 書き込み方式 書き込みたい主記憶アドレスのブロックがキャッシュに存在する場合ライトスルー方式 : データ更新時にキャッシュを更新すると同時に主記憶にも書き込むライトバック方式 : キャッシュのみを更新し, そのキャッシュが破棄されるときに主記憶に書き込む 書き込みたい主記憶アドレスのブロックがキャッシュに存在しない場合 Write allocate 方式 : キャッシュを作ってから書き込む No write allocate 方式 : キャッシュはつくらずに直接主記憶に書き込む 置き換えアルゴリズム キャッシュメモリに必要な写しがなく, キャッシュメモリに空いているブロック枠がない場合にはキャッシュ の置き換えが必要となる. : 写しの使われ方に関係なく古い写しが置き換えられる よく用いられている写しが置き換えられる可能性が高いが, キャッシュが一定期間残るためある程度大きなキャッシュサイズであれば悪い方式ではない. : 各ブロック枠に Usage bit を設け, そのブロック枠にアクセスがあると Usage bit を 1 にし,Usage bit が 0 のものを置き換える : もっとも最後にアクセスされた写しを置き換える 8-4

29 授業内レポート第七回学籍番号名前 (1) キャッシュメモリの容量が 256K バイト, 主記憶の最大容量が 4G バイトのメモリ系 (=アドレス指定に 32 ビット必要 ) において, ブロックの大きさが 32 バイトの 8 ウェイ群連想方式 ( 群におけるブロック枠の数が 8 つ ) を採用したとき, 群番号, および群内ブロック番号の指定に何ビット必要か. また, ディレクトリ全体で何ビット必要か. (2) メモリ系への書き込みにおけるライトスルー方式およびライトバック方式のメリット デメリットについ て簡単に議論せよ. (3) 授業に関するリクエストやその他質問等があれば書いてください. 8-5

30 計算機工学 II 授業ノート (Vol.8) 担当 : 寺田 システム アーキテクチャ ハードウェア アーキテクチャ ( これまで ): 計算機の高性能化技術 システム アーキテクチャ : 計算機の効率的な利用と使いやすさの向上のための技術 (OS の機能 ) : 物理的な資源を論理的な資源に変換することで, 抽象度を上げて物理制約から逃れる. プロセッサの仮想化 初期の計算機ではプログラムは 1 つずつ実行され, キー入力や処理結果の出力時には CPU は入出力装置の動 作終了を待っていた. 多重プログラミング : 入出力処理による待ち時間の際に, 別の実行可能なプログラムを実行する. 事象駆動方式 : 多重プログラミングのように, 入出力要求の発生などの事象に応じてプログラムを切り替える時分割システム :CPU をタイム クオンタムと呼ぶ微小時間ごとに次々とユーザプログラムの実行に割り当てていく方式. 処理中のプログラム数だけがあり, それらがそれぞれのプロセスを処理する. プロセスの基本状態 : 実プロセッサが割り当てられてプログラムが実行されている状態 : 入出力装置や補助記憶装置の動作の終了を待っている状態 : 実行可能であるが実プロセッサが割り当てられていない状態 9-1

31 割込み 入出力動作の終了やタイム クオンタムの終了などをハードウェア的に監視し,CPU に知らせる機構. オー バフローの検知機構が最初の割込み機構.IBM System 370 では下記の 7 レベルが存在する. (1) 緊急ハードウェア障害割込み : ハードウェア障害の重篤なもの (2) Supervisor call 割込み : ユーザプロセスが高レベルの処理実行を依頼するために起こす割込み (3) プログラム割込み : 桁あふれや 0 除算などプログラム実行中のトラブルにより起こる割込み (4) 抑制可能ハードウェア障害割込み : ハードウェア障害のうち, 復帰できたもの (5) 外部割込み : タイマ割込みや他の CPU からの信号受信など (6) 入出力割込み : 入出力装置の動作完了等によって生じる (7) リスタート割込み : リスタートボタンを押すことによって生じる 割込みは命令の実行と非同期に生じるため, 実行中の命令を継続できるよう方法を採る必要がある. 排他制御 複数のプロセスが共有データにアクセスする際に必要となる機能. 同じデータを複数のプロセスが好きに書き換えると問題が起こる. : 共有データにアクセスする操作 TS 命令による排他制御 : 下図のように, ロックをかけることでクリティカル リージョン処理中の共有デー タアクセスを排除する. ロックが解除されるのを待つ間, プロセスは待機状態となる. 9-2

32 主記憶の仮想化実記憶 : 主記憶, 実際の記憶装置 : 実記憶よりはるかに大きい主記憶が実現できる. その一部が実記憶に配置され, その他は補助記憶に配置される.OS が管理する. ページとセグメント ページ方式 : 機械的に一定の大きさのページを単位として主記憶と補助記憶との入れ替えを行う. セグメント方式 : プログラムやデータを意味のあるまとまり ( セグメント ) に分割して用いる. ページ方式 CPU キャッシュメモリの考え方と同様だが下記の相違点がある. サイズが増大 転送量も増大 低速 ストア スルー方式は現実的でない. 書込みの行われていないページを優先的に追い出す 効率を考え完全連想方式をとるが, ディレクトリ方式でアドレス対応付けを行うと連想記憶が大きくなりすぎるため, を用いる. 検索回数が 1 回であるため連想記憶を用いる必要がない ( 主記憶に置ける ) 仮想空間 4G バイト ( アドレス指定 32 ビット ), 実空間 64M バイト (26 ビット ), ページの大きさ 4K バイト (12 ビット ) の場合, 仮想空間は 1M ページ (20 ビット ), 実空間は 16K ページ枠 (14 ビット ) ディレクトリ方式 : ページ方式 :4 バイト 1M で が必要 が必要 9-3

33 単一仮想記憶と多重仮想記憶 単一仮想記憶方式 : 全プロセスが同じページ表を利用する方式 多重仮想記憶方式 : プロセスごとにページ表をもたせる方式 ページ表の多段構成多重仮想記憶方式で多重度を 10 にすればページ表のサイズは 10 倍にもなる. 一方, ページ表の中のほとんどの部分は利用されていない 多段構成の利用. 仮想アドレス 32 ビット, ページの大きさ 4K バイト ( ページ番号は 20 ビット ),2 段のページ表に 10 ビットずつ割り当てると, 各段のページ表のエントリ数は 1K. あるプロセスが,0 ページ目から数ページのプロセスと,2K ページ目から数ページのデータ領域からなっている場合,1 段目のページ表 1 つと 2 段目のページ表 2 つがあればよく, ページ表全体の容量は (1 エントリ 4 バイトの場合 ) でよい. 9-4

34 授業内レポート第八回学籍番号名前 (1) キャッシングと主記憶の仮想化の, 類似点および相違点をまとめよ (2) プロセスの基本状態において, 待ち の状態が存在する意味を説明せよ. (3) 授業に関するリクエストやその他質問等があれば書いてください. 9-5

35 計算機工学 II 授業ノート Vol.9( 担当 : 寺田 ) 6. プログラムとメモリ これまでの前提知識 - プログラムは, ロード / ストア命令, 演算命令, 分岐命令などを組み合わせて実行される. - プログラムや, 処理するデータは, メモリ ( 主記憶 ) に格納されている. - プログラムカウンタ (PC) と呼ばれる変数が, 現在のプログラム実行番地を格納している. サブルーチン繰り返し行われるような命令を別に切り出して関数化し, 再利用できる形にしておくこと. プログラムの化や見やすさの向上に貢献する. 関数は多段で呼び出されたり, 再帰呼び出しがあり得るので, 使用している変数値と, 飛び先関数終了時の復帰先アドレスをどこかに確保しておく必要がある. スタックの利用 9-1

36 サブルーチン呼び出し時の処理サブルーチン呼び出し時にスタックには, - サブルーチン終了時の復帰先アドレス - サブルーチン呼び出し時の引数 - サブルーチンのローカル変数が格納される. 割り込みの実現 割り込み処理はサブルーチンと同様の処理で実現可能. ただし, 優先度の処理や CPU 状態の復元などいくつ かの追加処理が含まれる. コールスタックの危険性スタックにローカル変数と復帰先アドレスを格納していく場合, 適切にプログラムを記述しておかないと不正なコードを実行される可能性がある. 例えば下図では, 適切に処理をしていない場合に, 復帰先アドレスが書き換えられる可能性を示している ( バッファオーバーフロー攻撃 ). 対策として, 例えば java 仮想マシンはメモリをヒープ領域とスタック領域に分割した上で, 入出力が可能なデータ構造はヒープ領域のみに配置し, 復帰先アドレスの破壊を困難にしている. この場合, 関数処理が終了しても, ヒープ領域のデータは解放できないため, そのための処理 ( ガベージコレクション ) を定期的に行ってメモリを解放する必要がある. 9-2

37 授業内レポート第九回学籍番号名前 (1) サブルーチンの呼び出し時に, 復帰先アドレスの格納にスタックを用いるメリットを述べよ. (2) 命令の分岐予測に関して, 静的予測と飽和カウンタの予測精度に差が出る場合を例を挙げて示せ. (3) 授業に関するリクエストやその他質問等があれば書いてください. 9-3

38 計算機工学 II 授業ノート Vol.10( 担当 : 寺田 ) 8. スーパースカラと VLIW パイプラインの高速化キャッシング技術や仮想化技術の進歩とともにメモリは高速化されつつあるので, 対応して CPU もさらなる高速化を狙うが, 動作周波数の向上は頭打ちである. ひとつの方針として,CPU における命令のパイプライン実行を高速化する. パイプラインの細分化による見た目の周波数向上 パイプラインの段数増加に対する速度向上への障害 上図 (d): 依存関係の存在 上図 (e): 分岐予測の失敗 パイプラインの同時実行と命令の依存関係 : パイプラインの 1 つのステージで複数の命令を実行するようにしたもの. 演算ユニット等が冗長化されている. 命令を同時に実行してもよいかを判断するための が重要になる. 依存関係調査 10-1

39 (a) フロー依存 : 先行命令の書き込み先を後続命令が読み出す. (b) 逆依存 : 先行命令の読み出しレジスタに後続命令を書き込む. (c) 出力依存 : 複数命令を同一レジスタに書き込む. 本質的データ依存以外は, レジスタリネーミングにより解消可能. インオーダ実行とアウトオブオーダ実行 10-2

40 インオーダ実行 : 命令の順序関係を崩さずに実行する : 命令の実行順序をを崩してもよい.Rename ステージでレジスタリネーミングを行い,Rerite ステージで順序関係を回復する. 分岐予測と投機的実行パイプラインとスーパースカラにより, 命令を次々と実行できるため, 分岐命令の実行結果を待たずに分岐がどうなるかを予測して次命令の実行を始めることになる ( 投機的実行 ). この場合, 分岐予測の精度が性能に大きく影響する. 静的予測 : 必ず分岐する ( 分岐しない ) とする. 飽和カウンタ : 予測の成否に応じて状態変更. 適応型予測 : 命令ごとの過去の分岐パターンを使う 次命令で参照する主記憶アドレスや値についても予測できれば効率がよい. Last value Stride based Context based Hybrid : 最後に利用した値をそのまま使う : 直近に使用したアドレスやロード結果の差分を使って予測 : 過去の履歴と現在の状況を比較 : 複数の機構を同時に装備して使い分ける ソフトウェアパイプライニング 実行時に命令の入れ替えを行うのではなく, プログラムをコンパイルするときにコンパイラが命令の実行順序 を変更したり, ループを展開するなどの処理を行い, 効率的に実行できるようにしておく. 10-3

41 計算機工学 II 授業ノート Vol.11( ) 担当 : 寺田 13. I/O 装置 キーボードやディスプレイ, プリンタ, センサ, アクチュエータなどの入出力装置や, 磁気ディスク, 磁気テ ープなどの補助記憶装置,CPU やメモリとの間でどのようにデータをやり取りするかを規定する. 昔 :CPU の命令セットの中に, CPU はハードウェア処理が終わるまで次の処理に移らない 命令の数の増加や接続機器の増加に対処できない を組み込む 現在 :CPU から周辺装置へのコマンドをデータとして送信する手法 : メモリアドレスの一部を, 指令レジスタ, データレジスタ, 状態レジスタ等に割り当てることで, メモリへの読み書きと同様の命令を使って周辺機器を制御する方式 : 周辺機器への I/O を行う専用命令を利用する方式 ポーリングや割り込みを利用して周辺装置の動作終了を検出する 実際のデータ送受信の際には, メモリアクセスの高速化や CPU 負荷の軽減のために,CPU を介さずに直接デ ータのやり取りを行うが採られることが多い. 小型計算機の入出力系の構成 CPU とメモリの間は高速バス ( メモリバス ), 周辺機器は入出力バスにつなぎ, アダプタを介してメモリバス に接続される. バス :1 組の伝送線に機器ごとに一組の伝送線をつなげたもの. 回路構成が単純 機器数の増減への対処が容易 伝送線を共用するために種々の制御が必要, 性能面でもネックとなる同期バス : バスにつながる機器や回路がバスから供給されるクロックに同期してデータを送受信する非同期バス : クロックはもたずに, 応答確認 (Ack) を使って通信を行う 11-1

42 非同期バスの応答確認方式 (1) 送信側はデータと共にデータ送信信号を送る (2) データ送信信号を受け取った受信側は, 確認信号を返信すると同時にデータを格納 (3) 送信側は確認信号によりデータが届いたことを知り, データ送信信号を停止する (4) 受信側はデータ送信信号の停止検出により, 確認信号が届いたことを知り, 確認信号を停止 (5) 送信側は, 確認信号停止によりデータ送信が完了したことを知り, 次のデータ伝送に移る この場合のデータ転送速度 T c = 信号線上での伝播遅延時間.RDY(s) と RDY(r), または ACC(s) と ACC(r) の時間差. T m =マスター内部の論理回路での遅延時間.ACC(r) の立上りと RDY(s) の立下り, または ACC(r) の立下りと DAT(s) の立上りの時間差 T s =スレーブ内部の論理回路での遅延時間.RDY(r) と ACC(s) の間の時間差. T d =データ線の信号伝播時間のばらつきの補償時間.DAT(s) の立上りと RDY(s) の立上りの間の時間差. この場合のデータ転送速度は, データ線を n バイトとすると, n / (4T c +2T m +2T s +T d ) [ バイト /s] となる. 改良方式 ( 高速応答方式 ) n / (2T c +T m +T s +T d ) [ バイト /s] 11-2

43 バスの使用権の制御 バスには複数の機器が接続されているため, バスの使用権を獲得する必要がある. 方式 接続順にバス使用の優先度が決まるシンプルな方式. 11-3