計算機工学II 授業ノート 第1 回（2014.4.11）担当：寺田 --- 担当教員：寺田 努（工学研究科電気電子工学専攻 准教授） Email: [email protected] （質問等はメールでお願いします） TEL: 078-803-6117 居室: 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 を使って計算を速く行うためにはどのようなプログラムの書き方が望ましいか，キャッシュ メモリの内容の整合性を保つにはどのような実装がよいか，など．多くのアイデアを出すことができるのは人 間の創造的な思考能力である．
計算機の誕生と発展 初期のコンピュータのプログラム供給方式は，紙テープ読み取りや配線盤に直接配線を行う形． ・ デメリット 紙テープ：紙テープの読み取り速度に限界がある 配線盤：プログラムの変更に多大な労力と時間を要する ノイマン型計算機 （プログラム内蔵方式）1945 年 プログラム もデータと一緒に計算機の中に格納． 中央処理装置 – 主 ― 記憶装置 という計算機の基本構成を確立 計算機アーキテクチャとは ・ プログラマから見たシステムの属性および外部仕様 ・ それを効率的に実現する内部仕様 ハードウェアの物理的な違いやメーカの違いにかかわらず，同一のプログラムが実行できるといった恩恵が受 けられる．
授業内レポート第1 回 学籍番号 名前 (1) 下記の単語のうち，簡単に説明できるものに○を，説明はできないが聞いたことがあるものに△をつけよ． 2 進数 10 進数 機械語 ギガバイト テラバイト スタック パイプライン 再起呼出し 浮動小数点 2 の補数 仮想記憶 排他的論理和 分岐予測 コンパイラ 投機実行 C# java android (2) 下記のサービスのうち，実際に登録して利用しているものに○を，内容を知っているものに△をつけよ．
mixi GREE Gmail モバゲータウン グルーポン 食べログ facebook Twitter instagram Google Calendar Flicker LINE note はてな
(3) 計算機アーキテクチャによって，ハードウェアの物理的な違いやメーカの違いにかかわらず，同一のプロ グラムが実行できると何がうれしいかを1 つ述べよ．なお，「新規ソフトウェアの開発」「応用ソフトウェアの 開発」「価格性能比」「コンピュータファミリー」といった言葉を1 つ以上含めて記述すること
計算機工学II 授業ノート Vol.2（2015.4.24）担当：寺田 １．基本素子と情報の表現 計算機における情報の表現方法 計算機内部では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 の補数系 2 の補数系 7 6 5 4 3 2 1 0 －0 －1 －2 －3 －4 －5 －6 －7 －8 (2) 1 の補数系 ** 補数とは ** ・N 進法において，ある数 a に足して全体の桁が１つ上がるような最小の自然数を「N 進法における a に対 する 」という． ・N 進法において，ある数 a に足しても桁が上がらない最大の自然数を「N 進法における a に対する 」という． ** 補数の説明終 ** 2 進数において，1 の補数とは 0 と 1 を単純に入れ替えたものである． 1 の補数系では，正の数 M はその 2 進数で，負の数－M は M の 1 の補数で表す．結果的に最上位ビットが正
加算の手順（減算は補数をとってから加算） [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= 符号拡張 ビット数の異なる数を加減算したい場合には長さをそろえる処理が必要． ビット長の短い数をビット長の長い数に合わせるには，上位桁に を挿入していけば よい．
授業内レポート第二回 学籍番号 名前 (1) 2 の歩数系で数を表す 2 値系列 X＝(xn-1, xn-2, xn-3, …, x0)において，左算術シフトを XL，右算術シフトし た数XR を示せ．その際，オーバフローおよびアンダーフローの条件を示すこと．また，なぜその条件に なるのかを考えよ． (2) (10011010)2＝154 に (1010)2C=－6 を加算せよ．計算の途中経過も記すこと．添え字の 2 や 2C はそれ ぞれ，正しかない2 進数系，2 の補数系を表す． (3) コメントや質問があれば書いてください．
計算機工学II 授業ノート Vol. 3 担当：寺田 コンピュータにおいて小数の表現を行う場合，10 進数の場合と同様に固定小数点と浮動小数点がある．ここ では特に浮動小数点について説明する． 浮動小数点数 実数は，一般には有限の桁数では表現できない．実際の応用では何桁かの有効数字が得られれば問題ない． そこで実数の による表現を用いる． ただし， m を仮数，e を指数，β を底，p を精度と呼ぶ． d0≠0 のとき， されているという．このとき表現は一意に定まる． 表せる数 浮動小数点で表せる数は，の間に等間隔で並んでいる．間隔は正規化された浮動小数点数の最下位桁の1 の値． 実際の数値は点在する表現可能な数の一番近いところに近似されるため，その最大誤差は間隔の半分となる． 値域 正の正規化浮動小数点数で表せる最大値Fmax・最小値Fmin Fmax≒ Fmin＝ つまり，浮動小数点数の値域は ≦ z ≦ ， ≦ z ≦ －Fmin ＜ z ＜ Fmin のとき z ＜ －Fmax および Fmax ＜ z のとき IEEE 標準の浮動小数点数形式
IEEE754 と IEEE854 の 2 つが 1980 年代に検討・制定された．IEEE754 は底を 2 のみ許容．
単精度 拡張単精度 倍精度 拡張倍精度 p 24 ≧32 53 ≧64 emax ＋127 ≧＋1023 ＋1023 ≧＋16383 emin －126 ≦－1022 －1022 ≦－16382 指数のビット数 8 ≧11 11 ≧15 語長 32 ≧43 64 ≧79
指数部の割当て可能数を2 減らし，特殊な値の表現を用意している．
指数部 仮数部 意味
e＝emin－1 f＝0 ±0
e＝emin－1 f≠0 0. f×2emin
emin≦e≦emax f 1. f×2e
e＝emax＋1 f＝0 ±∞
授業レポート第三回 学籍番号 名前 (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) リクエストや質問等があれば書いてください．
計算機工学 II 授業ノート Vol.4 担当：寺田 算術演算回路の構成法 32 ビットで表された 2 数の加減乗除を行う演算回路は，入力数 ，出力数 の組合せ論理 回路で構成可能 → 現実的には無理（真理値表さえ作れない）．したがって，人間が筆算を行うのと同様の工夫が必要． 加減算回路 2 の補数系では減算は補数を加算すればよい → を構成すればよい． n ビットの加算器は，3 入力の 1 ビット加算器（全加算器：full adder）を基本回路として構成． 加算する 2 数：ai，bi，下位桁からの桁上げ：ciとし，和：si，上位桁への桁上げ：ci+1 とすると si＝ ci+1= gi： ，pi： 順次桁上げ加算器 ・桁上げを各段で待つ必要があるため遅い パラレルプリフィックスアダー 各桁の桁上げ信号は， を使わなくても計算可能．これを利用して桁上 げ情報を先に伝播する加算器を と呼ぶ．
左図のように加算器を修正すると，右図のような桁上げ先見加算器が構成できる．
ci+2=
L を という．
L を多段化（P65 図 3.3）したり，L を 4 ビットに拡張することでさらなる高速化が可能．
乗算回路
A=(an-1, an-2, … a0)，B=(bn-1, bn-2, … b0) (2 の補数系)のとき
A×B=
※ A が正の時と負の時に分けて考えれば証明は容易
逐次型乗算機
乗数 A と部分和 P を 1 ビットずつシフトしながら部分積 aiB を部分和 P に加算していくことで計算する．
並列乗算器 逐次型乗算器の加算を並列加算器で行う． 1 ビットずつの乗算を何ビットかまとめて行うことで高速化が可能． ※2 ビットの場合， を求めて部分和に加える．カッコ内は を とるが， を作成するのはコストが高い． ブースのアルゴリズム 乗数の中に連続した 1 が含まれる場合，計算回数を減少させられる． → 一般に，ブースのアルゴリズムは下記のように表現される． ai ai-1 加数 2 ビットずつにした場合は下記のとおり ai+1 ai (ai-1) 加数
除算回路 除数 D，被除数 X が n ビットの符号なし正小数であるとする．このとき除算は が成立する Q と R を求めること．筆算と同様に考え，商を（Q=0.q1q2･･･qn），各段の計算結果を riとすると となる． 引き戻し法による除算 (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 進数に変換する方法がポピュラー． 浮動小数点演算回路 整数演算とシフトの組合せ 整数演算：乗除算は加減算にくらべてはるかに複雑 浮動小数点演算：加減算では逐次的に行う処理が多いため，乗算が加減算と同程度か高速．
浮動小数点の加減算手順 (1) 加数と被加数の指数の差を求める (2) 大きいほうの指数を，答の仮の指数とする (3) 指数が小さいほうの仮数を，指数の差だけ右にシフトする (4) 仮数の加減算を行う (5) 答の正負の符号を定める (6) 演算結果の仮数の正規化に必要なシフト桁数を求める (7) 仮数を左にシフトするとともに丸めを行う (8) シフト数だけ仮の指数を補正する 丸めの処理には， が用いられることが多い． 浮動小数点の乗除算 (1) 仮数の乗除算を行う (2) 指数の加減算を行う (3) 答の正負の符号を定める (4) 結果に応じて仮数を 1 ビットシフトするとともに丸めを行う (5) 結果に応じて指数を 1 だけ補正する
授業内レポート第四回 学籍番号 名前
(1) －310×510 を，ブースのアルゴリズムを使って解く様子を記述せよ．アルゴリズム動作がわかるように書 かれていれば形式は問わない．
(2) .10012 ÷ .11012 を引き戻し法と引き放し法それぞれで計算せよ
計算機工学 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 程度
計算機の構成方法
n アドレス命令：1 つの命令に n 個のアドレスをもたせる命令 n が大きい：処理が ．あらゆる命令を用意するため ． n が小さい：命令数が ．処理ステップ数が ． 例えば 3 アドレス命令だと，a = b + c は add A, B, C といった形で 1 命令による表現が可能 (2) レジスタ型計算機 アキュムレータ型におけるアキュムレータを汎用にし，複数用意したもの． A ← [B] op [C] における A，B，C が ．そのため，命令あたり のオペランド数は ． (3) スタック型計算機
レジスタの代わりに を用いたもの．スタックの上 2 つで演算を行うため，演算命令には オペランドが 命令の種類 ： レジスタ・主記憶の間でデータを移動する命令． ：加減乗除の四則演算を行う命令．演算結果の正・負・0・オーバフローの有無により を設定するものもある．2 進整数と 10 進整数，浮動小数点数などの 変換命令も含まれる． ：2 変数の論理関数（AND，OR，EOR），1 変数関数 NOT 等の命令． ：算術シフトや論理シフトを行う命令． ：命令の実行番地を変える命令． その他：入出力やシステム制御に関するもの． オペランドの指定方法 主記憶アドレス：アドレスを指定する（指定方法は後述）． 汎用レジスタ：レジスタ番号を指定する． 特殊レジスタ（プログラムカウンタ，プログラム状態語，制御レジスタなど）：専用の命令が用意されていて ことが多い． 値（レジスタの一定値の増減や，シフトの桁数指定など）：直接指定するため高速に処理可能．即値形式．
授業内レポート第 5 回 学籍番号 名前
(1) アキュムレータ型計算機，レジスタ型計算機，スタック型計算機の特徴を簡単にまとめよ．また，現在レ ジスタ型計算機が主流である理由を説明せよ．
計算機工学 II 授業ノート Vol.6 (担当：寺田) 命令の実行制御 演算処理部と実行制御部 演算処理部：演算回路（前回説明したもの）や，汎用レジスタ，プログラムカウンタ等の専用レジスタがバス に接続されたもの． S，D ：バスを表し，共有される．S1，S2 は演算回路入力用，D は演算回路出力用 ALU ：Arithmetic Logic Unit．演算回路
実行制御部：制御信号の系列を加えることで する． 実行制御部の処理 (1) PC(プログラムカウンタ)が指すメモリアドレスから命令を読み出し，PC を次命令まで進める． (2) 命令を解釈し，レジスタファイルと呼ぶレジスタの集合体から必要なデータを読み出す．また，引き続くス テージの制御信号を準備する． (3) 演算器において算術/論理演算/シフトなどを行う．ロード/ストア命令の場合はアドレス計算のみを行う．分 岐命令の場合は条件コードに応じて PC に分岐先アドレスを書き込む． (4) 演算命令の場合は何もしない．ロード/ストア命令の場合はアドレス計算結果を用いてメモリを参照しデー タを読み書きする． (5) 演算結果やロード結果をレジスタファイルに書き込む． パイプライン実行 命令実行における個々のステップはそれぞれの処理を行う回路ユニットが存在している． ：ある命令の処理終了後に次命令を処理する．下記のようにユニット稼動に無駄が生じる サイクル 1 2 3 4 5 6 7 8 9 10 11 12 13 14 命令 1 F D E M W 命令 2 F D E M W ：それぞれのステップの独立性を応用して次々に命令を投入・実行する．高速化の有 力手法．分割された処理単位のそれぞれを と呼ぶ．ステージ数は，最も実行ステッ プの多い命令のステップ数．
サイクル 1 2 3 4 5 6 7 8 9 10 11 12 13 14 命令 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 万分の１秒)．CPU の性能表現によ く用いられる．測定に使用するプログラムやデータに依存する．
パイプステージ
授業内レポート第六回 学籍番号 名前 (1) あるプログラムをシミュレータで実行して測定したところ，4 クロックで実行できる命令が 40％，5 クロ ックで実行できる命令が 60％の頻度で起こっていた．この場合，逐次実行した場合の 1 命令あたりの平均所 要クロック数はいくつになるか． (2) (1)のプログラムを逐次処理で実行した場合に比べて，5 ステージ（F D E M W）のパイプライン処理を実装 した場合，何倍の速度で実行できるか．ただし，パイプラインはすべてのステージが命令を実行している定常 状態にあるとし，パイプラインが乱れるようなことはないと仮定してよい． (2) 授業に関するリクエストやその他質問等があれば書いてください．
計算機工学 II 授業ノート Vol.7（担当：寺田） キャッシュメモリ プロセッサの高速化(1 サイクル 10ns など)に対して主記憶のアクセス時間(DRAM で 100ns 近辺)との落差が生 じる．高速で大容量な主記憶を用意することは現時点では困難であるため， を CPU に設ける． キャッシュメモリ： を保持しておく高速なメモリ．ヒットすれ ば低速な主記憶へアクセスすることなくデータの読み出しが可能．プログラムの時間的・空間的局所性を利用 してヒット率（アクセスする命令やデータがキャッシュメモリに存在する確率）を高める． キャッシュアクセス時間 10ns，主記憶装置アクセス時間 200ns，ヒット率 95％だとすると， 平均メモリアクセス時間は キャッシュメモリの仕組みを実現するにあたっての検討事項 ・キャッシュメモリと主記憶の対応付けと検索を行う機構 ・キャッシュの置き換えの機構 ・キャッシュへの更新を主記憶に伝播する機構 ブロックとマッピング ブロック：キャッシュメモリに主記憶の写しを作る際の写しの大きさの単位 ブロック枠：キャッシュメモリにおける，ブロックを格納するための区画 ブロックが大きい → 管理が簡単，ヒット率低い，書き換えコストが高い ブロックが小さい → 効率がよい，主記憶との対応付けが大変 ※ 現在は，通常 16，32，64 バイト程度がブロックの大きさとして採用されている．
ディレクトリ： キャッシュメモリに主記憶のどのブロックが割り当てられているかを高速に検索するための 索引．ディレクトリ内の検索には連想記憶などの高速な機構を採用する． マッピング方式 主記憶ブロックに対してどのブロック枠を割り当てるかを決める方式がいくつかある． (以下，ブロックサイズ：64 バイト，キャッシュ容量：64K バイト，主記憶容量：4G バイト) ：主記憶の任意のブロックをキャッシュの任意のブロック枠にマッピングでき る方式 ・制約がないためキャッシュメモリの利用効率が高く，ヒット率も高い ・ディレクトリ検索の効率が悪い．
：主記憶の各ブロックに対するディレクトリのエントリが一意に決まる方式 ※下記の例では，主記憶を 1024 の群に分け，主記憶ブロックの番号 i に対してブロック枠 j＝i mod 1024 を割 り当てる． ・ディレクトリの検索を必要としない ・特定の群の主記憶ブロックにアクセスが集中する可能性が高い ：両方式の中間にあたる方式 キャッシュメモリのブロック枠を n 行×m 列に構成する．主記憶ブロックも m 個の群にわけ，それぞれを 1 列のブロック枠に割り当てる．
書き込み方式 ・書き込みたい主記憶アドレスのブロックがキャッシュに存在する場合 ライトスルー方式：データ更新時にキャッシュを更新すると同時に主記憶にも書き込む ライトバック方式：キャッシュのみを更新し，そのキャッシュが破棄されるときに主記憶に書き込む ・書き込みたい主記憶アドレスのブロックがキャッシュに存在しない場合 Write allocate 方式：キャッシュを作ってから書き込む No write allocate 方式：キャッシュはつくらずに直接主記憶に書き込む 置き換えアルゴリズム キャッシュメモリに必要な写しがなく，キャッシュメモリに空いているブロック枠がない場合にはキャッシュ の置き換えが必要となる． ：写しの使われ方に関係なく古い写しが置き換えられる →よく用いられている写しが置き換えられる可能性が高いが，キャッシュが一定期間残るためある程度大きな キャッシュサイズであれば悪い方式ではない． ：各ブロック枠に Usage bit を設け，そのブロック枠にアクセス があると Usage bit を 1 にし，Usage bit が 0 のものを置き換える
授業内レポート第七回 学籍番号 名前 (1) キャッシュメモリの容量が 256K バイト，主記憶の最大容量が 4G バイトのメモリ系(＝アドレス指定に 32 ビット必要)において，ブロックの大きさが 32 バイトの 8 ウェイ群連想方式(群におけるブロック枠の数が 8 つ)を採用したとき，群番号，および群内ブロック番号の指定に何ビット必要か．また，ディレクトリ全体で 何ビット必要か． (2)メモリ系への書き込みにおけるライトスルー方式およびライトバック方式のメリット・デメリットについ て簡単に議論せよ．
計算機工学 II 授業ノート （Vol.8）担当：寺田 システム・アーキテクチャ ハードウェア・アーキテクチャ(これまで)：計算機の高性能化技術 システム・アーキテクチャ：計算機の効率的な利用と使いやすさの向上のための技術（OS の機能） ：物理的な資源を論理的な資源に変換することで，抽象度を上げて物理制約から逃れる． プロセッサの仮想化 初期の計算機ではプログラムは 1 つずつ実行され，キー入力や処理結果の出力時には CPU は入出力装置の動 作終了を待っていた． 多重プログラミング：入出力処理による待ち時間の際に，別の実行可能なプログラムを実行する． 事象駆動方式：多重プログラミングのように，入出力要求の発生などの事象に応じてプログラムを切り替える 時分割システム：CPU をタイム・クオンタムと呼ぶ微小時間ごとに次々とユーザプログラムの実行に割り当 てていく方式． →処理中のプログラム数だけ があり，それらがそれぞれのプロセスを処理する． プロセスの基本状態 ：実プロセッサが割り当てられてプログラムが実行されている状態 ：入出力装置や補助記憶装置の動作の終了を待っている状態 ：実行可能であるが実プロセッサが割り当てられていない状態
割込み 入出力動作の終了やタイム・クオンタムの終了などをハードウェア的に監視し，CPU に知らせる機構．オー バフローの検知機構が最初の割込み機構．IBM System 370 では下記の 7 レベルが存在する． (1) 緊急ハードウェア障害割込み：ハードウェア障害の重篤なもの (2) Supervisor call 割込み：ユーザプロセスが高レベルの処理実行を依頼するために起こす割込み (3) プログラム割込み：桁あふれや 0 除算などプログラム実行中のトラブルにより起こる割込み (4) 抑制可能ハードウェア障害割込み：ハードウェア障害のうち，復帰できたもの (5) 外部割込み：タイマ割込みや他の CPU からの信号受信など (6) 入出力割込み：入出力装置の動作完了等によって生じる (7) リスタート割込み：リスタートボタンを押すことによって生じる 割込みは命令の実行と非同期に生じるため，実行中の命令を継続できるよう方法を採る必要がある． 排他制御 複数のプロセスが共有データにアクセスする際に必要となる機能． → 同じデータを複数のプロセスが好きに書き換えると問題が起こる． ：共有データにアクセスする操作 TS 命令による排他制御：下図のように，ロックをかけることでクリティカル・リージョン処理中の共有デー タアクセスを排除する．ロックが解除されるのを待つ間，プロセスは待機状態となる．
主記憶の仮想化 実記憶：主記憶，実際の記憶装置 ：実記憶よりはるかに大きい主記憶が実現できる．その一部が実記憶に配置され，その他は補 助記憶に配置される．OS が管理する． ページとセグメント ページ方式：機械的に一定の大きさのページを単位として主記憶と補助記憶との入れ替えを行う． セグメント方式：プログラムやデータを意味のあるまとまり(セグメント)に分割して用いる． ページ方式 CPU キャッシュメモリの考え方と同様だが下記の相違点がある． ・サイズが増大 ・転送量も増大 ・低速 → ストア・スルー方式は現実的でない．書込みの行われていないページを優先的に追い出す → 効率を考え完全連想方式をとるが，ディレクトリ方式でアドレス対応付けを行うと連想記憶が大きくなり すぎるため， を用いる． ・検索回数が 1 回であるため連想記憶を用いる必要がない（主記憶に置ける） 仮想空間 4G バイト(アドレス指定 32 ビット)，実空間 64M バイト(26 ビット)，ページの大きさ 4K バイト(12 ビット)の場合，仮想空間は 1M ページ(20 ビット)，実空間は 16K ページ枠(14 ビット) ディレクトリ方式： が必要 ページ方式：4 バイト×1M で が必要
単一仮想記憶と多重仮想記憶 単一仮想記憶方式：全プロセスが同じページ表を利用する方式 多重仮想記憶方式：プロセスごとにページ表をもたせる方式 ページ表の多段構成 多重仮想記憶方式で多重度を 10 にすればページ表のサイズは 10 倍にもなる．一方，ページ表の中のほとんど の部分は利用されていない → 多段構成の利用．
授業内レポート第八回 学籍番号 名前
(1) キャッシングと主記憶の仮想化の，類似点および相違点をまとめよ
(2)プロセスの基本状態において，「待ち」の状態が存在する意味を説明せよ．
計算機工学 II 授業ノート Vol.9（担当：寺田） 6. プログラムとメモリ ・これまでの前提知識 - プログラムは，ロード/ストア命令，演算命令，分岐命令などを組み合わせて実行される． - プログラムや，処理するデータは，メモリ(主記憶)に格納されている． - プログラムカウンタ(PC)と呼ばれる変数が，現在のプログラム実行番地を格納している． サブルーチン 繰り返し行われるような命令を別に切り出して関数化し，再利用できる形にしておくこと．プログラムの 化や見やすさの向上 に貢献する．関数は多段で呼び出されたり，再帰呼び出しがあり得るので，使 用している変数値と，飛び先関数終了時の 復帰先アドレス をどこかに確保しておく必要がある． → スタック の利用
サブルーチン呼び出し時の処理 サブルーチン呼び出し時にスタックには， - サブルーチン終了時の復帰先アドレス - サブルーチン呼び出し時の引数 - サブルーチンのローカル変数 が格納される． 割り込みの実現 割り込み処理はサブルーチンと同様の処理で実現可能．ただし，優先度の処理や CPU 状態の復元などいくつ かの追加処理が含まれる． コールスタックの危険性 スタックにローカル変数と復帰先アドレスを格納していく場合，適切にプログラムを記述しておかないと不正 なコードを実行される可能性がある．例えば下図では，適切に処理をしていない場合に，復帰先アドレス が書き換えられる可能性を示している(バッファオーバーフロー攻撃)． 対策として，例えば java 仮想マシンはメモリをヒープ領域とスタック領域に分割した上で，入出力が可能な データ構造はヒープ領域のみに配置し，復帰先アドレスの破壊を困難にしている．この場合，関数処理が終了 しても，ヒープ領域のデータは解放できないため，そのための処理(ガベージコレクション)を定期的に行って メモリを解放する必要がある．
授業内レポート第九回 学籍番号 名前
(1) サブルーチンの呼び出し時に，復帰先アドレスの格納にスタックを用いるメリットを述べよ．
(2) 命令の分岐予測に関して，静的予測と飽和カウンタの予測精度に差が出る場合を例を挙げて示せ．
計算機工学 II 授業ノート Vol.10（担当：寺田） 8. スーパースカラと VLIW パイプラインの高速化 キャッシング技術や仮想化技術の進歩とともにメモリは高速化されつつあるので，対応して CPU もさらなる 高速化を狙うが，動作周波数の向上は頭打ちである．ひとつの方針として，CPU における命令のパイプライ ン実行を高速化する． パイプラインの 細分化 による見た目の周波数向上 パイプラインの段数増加に対する速度向上への障害 上図(d): 依存関係の存在 上図(e): 分岐予測の失敗 パイプラインの同時実行と命令の依存関係 : パイプラインの 1 つのステージで複数の命令を実行するようにしたもの． 演算ユニット等が冗長化されている．命令を同時に実行してもよいかを判断するための 依存関係調査 が重要になる．
(a) フロー依存 : 先行命令の書き込み先を後続命令が読み出す． (b) 逆依存 : 先行命令の読み出しレジスタに後続命令を書き込む． (c) 出力依存 : 複数命令を同一レジスタに書き込む．
本質的データ依存以外は， レジスタリネーミング により解消可能．
インオーダ実行 : 命令の順序関係を崩さずに実行する : 命令の実行順序をを崩してもよい．Rename ステージでレジスタリネー ミングを行い，Rerite ステージで順序関係を回復する． 分岐予測と投機的実行 パイプラインとスーパースカラにより，命令を次々と実行できるため，分岐命令の実行結果を待たずに分岐が どうなるかを予測して次命令の実行を始めることになる(投機的実行)．この場合，分岐予測の精度が性能に大 きく影響する． 静的予測 : 必ず分岐する(分岐しない)とする． 飽和カウンタ : 予測の成否に応じて状態変更． 適応型予測 : 命令ごとの過去の分岐パターンを使う 次命令で参照する主記憶アドレスや値についても予測できれば効率がよい． Last value : 最後に利用した値をそのまま使う Stride based : 直近に使用したアドレスやロード結果の差分を使って予測 Context based : 過去の履歴と現在の状況を比較 Hybrid : 複数の機構を同時に装備して使い分ける ソフトウェアパイプライニング 実行時に命令の入れ替えを行うのではなく，プログラムをコンパイルするときにコンパイラが命令の実行順序 を変更したり，ループを展開するなどの処理を行い，効率的に実行できるようにしておく．
計算機工学 II 授業ノート Vol.11（2014.7.4）担当：寺田 13. I/O 装置 キーボードやディスプレイ，プリンタ，センサ，アクチュエータなどの入出力装置や，磁気ディスク，磁気テ ープなどの補助記憶装置，CPU やメモリとの間でどのようにデータをやり取りするかを規定する． 昔：CPU の命令セットの中に， を組み込む ・CPU はハードウェア処理が終わるまで次の処理に移らない ・命令の数の増加や接続機器の増加に対処できない 現在：CPU から周辺装置へのコマンドをデータとして送信する手法 ・ ：メモリアドレスの一部を，指令レジスタ，データレジスタ， 状態レジスタ等に割り当てることで，メモリへの読み書きと同様の命令を使って周辺機器を制御する方式 ・ ：周辺機器への I/O を行う専用命令を利用する方式 ・ポーリングや割り込みを利用して周辺装置の動作終了を検出する 実際のデータ送受信の際には，メモリアクセスの高速化や CPU 負荷の軽減のために，CPU を介さずに直接デ ータのやり取りを行う が採られることが多い． 小型計算機の入出力系の構成 CPU とメモリの間は高速バス（メモリバス），周辺機器は入出力バスにつなぎ，アダプタを介してメモリバス に接続される． バス：1 組の伝送線に機器ごとに一組の伝送線をつなげたもの． ・回路構成が単純
非同期バスの応答確認方式 (1) 送信側はデータと共にデータ送信信号を送る (2) データ送信信号を受け取った受信側は，確認信号を返信すると同時にデータを格納 (3) 送信側は確認信号によりデータが届いたことを知り，データ送信信号を停止する (4) 受信側はデータ送信信号の停止検出により，確認信号が届いたことを知り，確認信号を停止 (5) 送信側は，確認信号停止によりデータ送信が完了したことを知り，次のデータ伝送に移る この場合のデータ転送速度
Tc＝信号線上での伝播遅延時間．RDY(s)と RDY(r)，または ACC(s)と ACC(r)の時間差．
Tm＝マスター内部の論理回路での遅延時間．ACC(r)の立上りと RDY(s)の立下り，または ACC(r)の立下りと
DAT(s)の立上りの時間差 Ts＝スレーブ内部の論理回路での遅延時間．RDY(r)と ACC(s)の間の時間差． Td＝データ線の信号伝播時間のばらつきの補償時間．DAT(s)の立上りと RDY(s)の立上りの間の時間差． この場合のデータ転送速度は，データ線を n バイトとすると， n / (4Tc＋2Tm＋2Ts＋Td ) [バイト/s]となる． 改良方式（高速応答方式） n / (2Tc＋Tm＋Ts＋Td ) [バイト/s]
バスの使用権の制御
バスには複数の機器が接続されているため，バスの使用権を獲得する必要がある．
・ 方式
