計算システム論第二
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
] [
リンク元
]
開始行:
[[講義日程-2008年度夏学期]]
** 計算システム論第二 [#l207d376]
- 担当：中村 宏 准教授
- 1.5単位
-- 数理：限定選択C
-- システム：限定選択B
- 10:15-11:45 工学部六号館 62講義室
-成績評価
--試験による。持ち込み不可~
出席は救済のみ
**試験関係 [#r560fa0d]
//-だれか過去問の答え作ってくれないかなぁ。
-不完全ですがversion2うp。授業を受けていない人も、一通り...
--''第二問の(1)(ア)は、講義の定義からいくと、CPI＝(必ずキ...
--''↑俺もそう思った。あと、第一問の(1)は空欄１が「PC <- P...
--↑多分それであっています。それから、残りの答えはしばしお...
--''↑最初のを書いた人間です。ですよねー。第二問の(1)(ア)...
--↑を補足すると(1)(イ)はcycle time=1.25[nsec],miss penalt...
CPI=1+0.4×0.05×80＝2.6,実行時間は(2.6×1.25)/(5×1)＝0.65（...
//あと(2)(ｳ)で実行時間長くなったんですけど・・
-自分の計算だと4.96って正解の5に近い値になったのは偶然?(s...
-第2問（ア）について。ミスペナルティ100nsだけど、実際には...
-(イ)については、ペナルティ100nsはかわらないままプロセッ...
-(ウ)では各々求めたCPI値(a,bとしよう)から以下の計算をすれ...
-みんな名乗ろうよ(by sen)
**参考文献とその他役に立ちそうなもの [#qb7c25e0]
参考書。いわゆるパタヘネ本。
--Conmputer Organization & Design: The Hardware/Software ...
--[[コンピュータの構成と設計>"http://www.amazon.co.jp/コ...
-[[MIPSシミュレータ>http://pages.cs.wisc.edu/~larus/spim....
-[[講義ページ>http://www.hal.rcast.u-tokyo.ac.jp/~nakamur...
パスワードはお友達に聞いてね。
-[[九大の講義ノート>http://ocw.kyushu-u.ac.jp/0009/0006/l...
-[[論理合成を忘れてしまった人はこちら>http://www.ssc.pe.t...
**内容 [#t7f6cf42]
物理的制約のもとで複数のシステムを有機的に組み合わせ，計...
+計算システムのモデリング
+命令セットアーキテクチャ
+データパスと制御論理
+メモリシステム：キャッシュメモリ、仮想記憶
+入出力制御
+プロセスの管理
+フォールトトレラントシステム
**授業ノート [#ra620884]
Presented by sen. tzik all blame reserved.~
誤植は見つけた人が直すものです
+計算システムとは
--目的に応じて
--ハードウェアとソフトウェアを組みあわせて構成~
目的によってさまざまな構成がありうるが、基本は同じ。
++ハードウェア構成(p2,3)
--CPU(Central Processing Unit) ,Processing Unit(PU) + 主...
--出入力装置
--補助記憶装置(HDDとか)
--プロセッサの速度はムーアの法則に従って増加するのに対し...
でも、基本的な部分は変わってないよ。
+システム設計の階層
-プログラムの構成
--高級言語(C,C++) → コンパイル → a.out(バイナリ)
--高級言語による設計の時には、下位レベル(ハードウェアのこ...
++概念レベル(仕様書、頭の中)
++高級言語レベル(C,C++) ハードウェアに非依存
++機械命令レベル(PU依存)
++レジスタトランスファレベル
++ゲートレベル
++スイッチレベル
iii.までがソフト屋さんの仕事。ここが変わるとソフト、ハー...
ivはレジスタ間の転送をハードウェアで実現する手法を規定~
VHDL,Verilogとかのハードウェア記述言語を使う。~
データパスと制御論理~
~
v.は第一でやったところ~
vi.はトランジスタの話。基本的にはこのあたりを気にする必要...
+階層設計に関する検討
1つのシステムがとても複雑になってきている。~
→設計の見通しの良さ~
設計が階層化されていれば、バグが生じたときに1つだけ上の階...
→最終的な品質(製品としての性能と設計期間)
+セマンティックギャップ(semantic gap)~
高級言語の機能と、ハードウェアで実現されている機能(アセン...
高級言語マシンというものが、今から20年くらい前にはさかん...
RISC(Reduced insttuction set computer)~
→ハードウェアで実現する機能、命令は簡単なものでも良い。~
''プログラムの実行時間=(プログラムあたりの命令数)*(1命令...
高級言語マシンでは、1↓ 2↑~
RISCでは1↑2↓~
RISCでは単純な命令だけにして命令セットの数を減らすのが目...
'(1命令あたりの実行時間) = (1命令あたりの所要サイクル数)*...
単純な命令を繰り返すもののほうが、流れ作業に向いている。...
//中村先生… とても、ノートが取りにくいです…
//番号付きリストがうまく表示されないので、あとで書きなおす
//とても、眠いです…
+ハードウェア/ソフトウェア協調設計
例えば、組み込みとか、ちょっと凝った処理をしたいときにプ...
{ハードウェア|ソフトウェア}で実現する機能の決定。
//ハニョンハニョン
2.命令セットアーキテクチャ
2.1命令(instruction)
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
0.25 * 0.5 = 1.25(%)
PUが処理すべき動作を指示
命令セットアーキテクチャ(instruction set architecture)~
→命令の体系、ハードウェアとソフトウェアのインターフェイス...
命令の種類
-算術演算命令(加算、減算etc.)
-論理演算命令(and,or)
-データ転送命令(メモリなどとの間でデータを転送)
-分岐命令(if文のようなもの)
命令語(instruction words)~
命令を表現するword(バイナリ)
//MIPSの命令一覧を探したけど、見やすいのが無かった…
MIPSの命令については、これが分かりやすいかも~
http://ocw.kyushu-u.ac.jp/0009/0006/lecture/10.pdf
2.2 主記憶のアドレシング~
PUのレジスタは数十個(MIPSの場合は32ないし64個)なので、メ...
アドレス付けの単位
-バイトアドレシング → 1つの番地で、1バイト管理
-ワードアドレシング → 1つの番地で、1ワード(4bit)管理
主記憶のサイズ~
プリント2^32=2^32バイト(32bitアドレス空間) →4GB~
最近はこれじゃ足りないので、64bitアドレス空間を使っている...
命令セットアーキテクチャ
プロセッサAからプロセッサBへ。~
今までのソフトウェアが動くか？~
そもそも同じなら、完全互換。命令を追加した場合は上位互換...
エンディアン(Endian)
-big endian
-litte endian
数値データを置く場所がどちらへ進んでいくか？ ~
数値データのMSD(most significant digit)をアドレス番号の小...
命令セットの違いはソフトウェア側でなんとかなる。でも、ア...
2.3命令セットアーキテクチャの分類
用意されているオペレーション(操作)の種類による分類ではな...
+PU内部のオペランド指定方式
+主記憶のオペランド指定方式
2.3.1 PU内部の記憶部
-スタック(stack)
-アキュムレータ(accumurator) ←レジスタが一つしかないと思...
-レジスタ(register) ←最近の汎用プロセッサはこれ
詳細はググれカス(by 中村先生)
4/28
2.3.2 汎用レジスタ方式における記憶部の指定方法~
(1)regiaster addressing~
レジスタを指定する~
add r1,r2,r3 # r1 <= r2 + r3
(2)immediate addressing(直値) ~
オペランドの値を指定する
add r1,r2,1000 # r1 <= r2 +1000
(3)direct addressing~
主記憶のアドレスを直接指定
(3-1) register~
load r1,(r2) # r1 <= mem[r2]
主記憶のアドレスを保持するレジスタを指定する
(3-2) immediate~
load r1,(1000) # r1 <= mem[1000]
主記憶のアドレスを直接指定する
(3-3)index~
load r1,24(r2) # r1 <= mem[r2+24]
レジスタとオフセットで指定
(4)indirect addressing(間接参照)
-主記憶のアドレスを間接的に指定
-主記憶のアドレスを保持する別の主記憶のアドレスを指定する
(4-1)register~
load r1,@(r2) # r1 <= mem[mem[r2]]
(4-2) immediate~
load r1,@(1000) # r1 <= mem[mem[1000]]
(4-3) index
load r1,@24(r2) # r1 <= mem[mem[r2+24]]
2.4 RISC(reduced instruction set computer)~
命令セットアーキテクチャの1カテゴリ。明確な定義はないが、...
-命令長が一定
-論理、算術命令のオペランドはレジスタのみ
-ロードストアアーキテクチャ~
主記憶のデータはロード命令、ストア命令のみで操作
lw $1,4($2)
add $1,$1,1
sw $1,4($2)
などという形で書かなければいけない。
-単純なメモリアドレシング(indirect addressingはない)
RISCの方針~
命令を単純化して、命令数は増加しても命令当りの処理時間を...
処理時間 = (命令数)*(命令あたりの処理時間)~
このあたりは、後でパイプラインやらないと分からないかも
3.データパスと制御論理~
データパス(data path)~
所望の処理を実現するためのデータが流れる経路
//http://urasoku.blog106.fc2.com/blog-entry-368.html
//てらえろす
-レジスタ等の記憶装置
-算術論理演算回路
-その間の相互接続
//たぶん、図が多くなって書けなくなるとおもうのでぐぐって...
制御論理~
所望の処理を実現するために、データパス上のデータ転送を制...
有限状態機械(Finite State Machine)で表現することが多い
実現方法:wired logic(有線論理)→FFと組合せ回路
3.1データパス~
(1)構成要素~
演算器、マルチプレクサ、レジスタ、メモリ~
(1-1)演算器:複数の入力に対し、制御信号で指定される演算を...
(1-2)マルチプレクサ~
複数の入力に対して、制御信号で指定された入力を選択して出...
(1-3)レジスタ:記憶部
機能的にはD-FFと類似だが、N-bitデータを扱う。制御信号(wri...
(1-4)レジスタファイル
M個のレジスタを扱う。入力出力をどれだけ許すか？~
最低、2入力1出力(そうじゃなきゃ演算ができないから)
3.2制御論理~
所望の動作をデータパス上で実現するための論理
(1)wired logic(布線論理)による方法。ハードウェア(FFと組み...
高速だが設計は大変~
(2)マイクロプログラムによる方法。命令より一段下のレベルの...
設計変更は容易だが、低速
3.3データパスと制御論理の設計~
「全ての命令の動作を実現するハードウェア」~
(1)各命令の実行ステージの分割~
いくつ？ 各ステージの動作は？~
ステージ：1サイクルに対応
(2)前項を満たすデータパスの構築~
該当するデータパス上で、各ステージの動作を実現する制御論...
(3)データパスはゲートレベルスイッチで対応~
制御論理は状態遷移図で与えられているので、前述の二つの方...
1,2レジスタトランスファレベル設計
6/2
4.メモリシステム~
4.1 キャッシュメモリ~
4.1.1 概念~
キャッシュ：大切なものを隠しておく場所~
方針：高速かつ大容量な記憶装置が手に入ればいいのだが、一...
根拠：局所性(locality)~
時間的局所性~
ある情報が参照されると、すぐ後にまた参照される傾向がある。
空間的局所性~
ある情報が参照されると、近くの情報も参照される傾向がある。
-用語
キャッシュヒット~
参照される情報がキャッシュにあること~
キャッシュミス~
参照される情報がキャッシュにないこと~
ヒット率~
参照時にヒットである割合~
メモリアクセス時間~
= (ヒット率) * (キャッシュアクセス時間) + (ミス率) * (主...
高速化~
キャッシュをどう構成させるか？~
-ヒット率を上げる
-キャッシュアクセス時間を短縮する
4.1.2 主記憶とキャッシュのアドレスマッピング~
メモリからキャッシュへ持ってきたデータをどう配置するか？
(1)direct mapping(ダイレクトマップ方式)~
主記憶のコピーの格納場所は、キャッシュ上で一意に定まる。~
(2)fully associative(フルアソシアティブ)
主記憶のコピーの格納場所はキャッシュ上の任意の場所~
(3)N-way set associative(n-ウェイセットアソシアティブ)
主記憶のコピーの格納場所は、キャッシュ上でN通りある。~
キャッシュ上でデータを探す時間とキャッシュの使い易さのト...
4.1.3 キャッシュの構成と制御(p21)~
(1) ダイレクトマップの例~
ブロックサイズ4B,容量4KB~
(1-1)キャッシュの構成~
ブロック数：1024~
ブロックのデータ部：4B~
index：キャッシュブロック番号
V:当該ブロックが有効かどうか？
tag：当該ブロックに格納されているデータのアドレス~
data:当該ブロックに格納されているデータの本体~
(1-2)メモリ参照時のアドレスビットの意味~
32bitのアドレス空間~
offset部：アドレスの下位2bit[1:0]
→ブロック内のオフセットを定める
index部：アドレスの次の下位10bit[11:2]
→参照すべきcache indexを定める
tag部：上位20bit[31:12]
→tag部と比較される
(1-3)読み出しと参照の動作~
(1)参照すべきアドレスのindex部からcache index を決定し、t...
(2)キャッシュ内のtag部と、参照すべきアドレスのtag部が一致...
-不一致 → キャッシュミス
-一致
--有効ビット →キャッシュヒット
--無効ビット →キャッシュミス
(3)キャッシュヒット時~
キャッシュのデータ部から所望のデータを読みだす
キャッシュミス時~
主記憶にデータを読みにいく
-参照されるデータを含む1ブロック分のデータを主記憶へ持っ...
-現在のキャッシュの当該ブロックを破棄して、新しいデータを...
//6月16日 遅刻した
4.2.仮想記憶(virtual memory)~
4.2.1 概要~
物理的には小容量しかないメモリを仮想的に大容量のメモリと...
OSの管理下で、ハードウェア機能のサポートにより限られた容...
-キャッシュと仮想記憶の対比
○ キャッシュ 仮想記憶~
制御単位 ブロック(固定、32Bから256B) ページ(固定:4KBから...
入れ替え制御 ハード ソフト~
(1)原理~
主記憶の記憶領域が不足したら不要な主記憶の一部を2次記憶へ...
swap in : 2次記憶から主記憶へ~
swap out: 主記憶から2次記憶へ~
(2)アドレス空間~
論理アドレス空間(logical address space)~
ユーザプログラムが実行されているアドレス空間(仮想アドレス...
物理アドレス空間(physical address space)~
主記憶上で実際に提供されているアドレス空間(実アドレス空間...
(3)制御の概略~
1.PU上でメモリアクセス実行~
2.論理アドレス→物理アドレスの変換(DAT:dynamic address tra...
3.変換可能→物理アドレスを用いて主記憶アクセス~
変換不可→該当論理アドレスは主記憶にない。~
→割り込み発生(ページフォールト)~
→OSに制御が渡る→OSがswap in/out を行なう。
4.2.2 アドレス変換方式~
アドレス変換の単位:ページ(固定) / セグメント(可変)
(1)ページング(paging)~
1953(英マンチェスター大)
プリント22p
-変換方式~
論理アドレス~
ページ番号とページのオプトからなる。~
論理アドレスのページ番号を物理アドレスページ番号へ変換
(2)セグメンテーション~
1961(米Burroughs社)
主記憶に置く単位をプログラムの論理的に独立した単位(セグメ...
ページングとの違いは多きさが可変であること
-長所 セグメントは属性が明確。記憶保護に最適~
-短所 外部フラグメンテーションが生じる~
→ページ化セグメント(paged segment)などがある
//前回senは休んでいました
// 6/30
5.入出力制御~
5.1 入出力制御方式~
1.特別なI/O方式~
アドレスとは別
2.address mapping I/O~
あるアドレスへの読み書きを入出力として扱う。
5.1.2 入出力装置からの通知検出方法
1.ポーリング方式~
CPUが定期的にI/Oデバイスを監視する。頻度が高ければ応答性...
2.割り込み方式(次でまたやる)
デバイス手動で、終了を割り込みで通知する。
割り込みを(ハードウェアが)検出すると、OSへ制御を渡して割...
ポーリングとは逆に、監視のオーバーヘッドは無いが、プロセ...
。
5.1.3 データ転送を行う主体による分類~
(1) プログラム制御方式~
CPUがプログラムモードの入出力命令によって、入出力装置を起...
入出力命令実行中はCPU動作が中断するため、大量のデータ転送...
(2) DMA制御方式(direct memory access)~
CPUとは独立に、主記憶と入出力装置のデータ転送を行う機構。...
(step1) CPUは入出力装置のID、実行すべき処理、転送先/元の...
(step2) DMAはバスの調停と入出力装置における処理を開始~
(step3) DMA転送が終了したら割り込みで通知~
例題. ポーリングと割り込み
一回のポーリングに400サイクル、CPU 500MHz
4words(16B毎)転送が行われ転送性能 4MB/sec のディスク
データが失われないようにポーリングで検出する場合のポーリ...
解.
(1) 必要なポーリングの頻度
4MB/16B = 250k(回/sec)
1秒あたりのオーバヘッドは
400 * 250k = 100Mサイクル
100M/500M = 20% のオーバーヘッド
(2) 割り込みの場合
一回の割り込み処理に、500サイクル要する場合
オーバーヘッドは？
割り込み頻度はポーリングと同じく250k
オーバーヘッドは (250k * 500サイクル)/500Mサイクル = 25%
(3) ディスクの入出力処理は全体の5%だけである場合
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
// 0.25 * 0.5 = 1.25(%)
25 * 0.05 = 1.25(%)
(4)DMA転送のオーバーヘッド
同じディスク
DMA転送のsetupに1000サイクル
DMA転送の終了の割り込みに5000サイクル
平均転送サイズ 8KB
このときのオーバーヘッド
ディスクは100%active
4MB/8KB = 0.5k(回/sec)
1回のDMA転送のオーバーヘッド
6000サイクル
(6000 * 0.5)/500M = 0.6%
5.2 割り込み~
不定期に起こる事象に対して、プログラムの実行を中断してし...
5.2.1 割り込みの種類
-入出力割り込み~
キーボード、マウス
-システムコール割り込み
システムコールの発行(標準出力へ表示など)
-プログラム割り込み(ページフォールト、異常実行(0割り))
-外部割り込み(リセット)
precise/imprecise
正確な割り込み(復帰再開可能)
不正確な割り込み(復帰再開不可能)
-precise~
割り込みを発生させた命令以前の命令は終了し、割り込み処理...
→ページフォールトはpreciseであるべき~
~
0除算：impreciseでも良い~
preciseの割り込みは思いの他大変
5.2.2 // 6/30
5.2.2 割り込み処理方式~
割り込みの受付は命令単位
+割り込みを受け付けるかを判断(優先度がある場合)
+CPUは実行中のプロセスを中断し、再開に必要な情報(PC、レジ...
+割り込みベクタを参照し、指定されている値をPCに設定~
=割り込み処理ルーチン 割り込みハンドラに移行 OSに制御が移行
+処理が終了したら、退避情報を復元して処理を再開
6.オペレーティングシステム(Operating system)
ユーザとハードウェアシステムのインターフェイス~
=ハードウェアの仮想化
6.1 役割~
+資源管理
--ハードウェア資源
---PU,主記憶,ディスク等の資源
--ソフトウェア資源
---プログラム,データ等の資源
---パーミッションの管理なども
+利用者インターフェイス
ハードウェア資源の特性を抽象化して、ユーザに提供~
特性に応じて最適化をすることができない
+運転管理とRAS~
RAS~
R:reliability
A:availability
S:serviceability
→高信頼性が要求されるシステム(銀行のオンラインシステム)で...
6.2 プロセス管理とスケジューリング~
6.2.1 プロセス(process)~
OSからハードウェア資源の割り当てを受けて処理を実行してい...
(Linuxだとpsコマンド、Windowsではタスクマネージャで見られ...
6.2.2 プロセスの状態と遷移~
(1)プロセスの状態
-実行状態：プロセスにCPU資源が割り当てられている
-実行可能状態：CPU資源は割り当てられていないが、割り当て...
-待ち状態：何らかのイベントを待っている状態
図が書けねー
・遷移状態~
1.初期状態：新しいプロセスが生成されると実行可能状態に~
2.実行可能状態→実行状態~
CPU資源が空いた時にスケジューリングアルゴリズムに従って、...
3.実行状態→実行可能状態~
特定のプロセスがCPU資源を占有するのを避けるために、あらか...
・プロセスの管理と切り替え~
OS内では、
-親プロセス/子プロセスへのポインタ
-プログラムのコード領域とデータ領域へのポインタ
-プログラムカウンタ、レジスタの退避領域
-メモリ管理状態(ページテーブルへのポインタ)
などを管理
プロセス切り替え時に必要な処理~
再開に必要な処理の退避~
CPU資源内にあるプロセスの情報、プログラムカウンタ、レジス...
6.2.3 スケジューリングアルゴリズム~
スケジューリング~
今回はCPUスケジューリング
スケジューラの評価基準
-CPU利用率
-ターンアラウンド時間 プロセスの実行要求から、実行までの...
-待ち時間 プロセス完了までに、実行可能状態のキュー(待ち行...
-応答時間
//senの遅刻によりぐぐれかす
7.フォールトトレラントシステム
障害に対して強いシステム
-故障(fault)
-fault avoidance と fault torerance
-fail safe ,fail stop
ユーザの期待するサービスを提供できないときシステムが機能...
-fail soft
ユーザが期待するサービスが提供できないとき、性能を落とし...
7.2 評価尺度~
応用分野によって必要となる信頼性は異なる。趣味の自宅鯖だ...
-信頼性
どれだけの時間障害を発生させずにサービスを提供できるか
-可用性
使いたいときにサービスが提供される確率
-保守性
修理のしやすさ、迅速さ
例えば、何十年も宇宙にあって簡単に修理のできない人工衛星...
7.2.1 フォールトカバレッジ(fault coverage)~
対象とするフォールト集合が現実に起こりうるフォールト全体...
計算システムにおけるフォールトの分類
-accidental fault(偶発的)
-physical fault(物理的)
--内部要因
--外部要因
-human fault(人為的：うっかり)
-malicious fault(人為的：故意)
-故障検出~
信頼度は故障検出能力に大きく依存
評価モデル~
どういう故障が起こるかの抽象モデル~ 良いモデルは、カバレ...
7.2.2 信頼度(rliability)~
障害発生を統計的分析を持つ確率事象として扱う。
f(t) 障害が生じる確率密度関数~
時刻tからt+dtの間に障害が生じる確率はf(t)dt
0からtの間のtauで障害が発生する確率F(t)
#mimetex(F(t) = \int^t_0 f(\tau)d \tau)
逆に時刻tまで障害が発生しない確率は
#mimetex(R(t) = 1 - F(t))
-障害率 lambda(t)~
時刻tまで無障害という条件の元で、tからt+dtに障害が起きる...
#mimetex(f(t) = R(t)\lambda(t))
#mimetex(R(t) = 1 - F(t))
#mimetex(\frac{dR(t)}{dt} = -\frac{dF(t)}{dt} = -f(t))
変数分離で積分すると
#mimetex(R(t) = \exp(-\int^t_0 \lambda(f)dt))
平均寿命 MTTF(mean time to failure)
#mimetex(MTTF = \int^\inf_0R(t)dt)
lambda(t)はどんな関数？~
システムのハードウェア バスタブ曲線(経験則)~
終了行:
[[講義日程-2008年度夏学期]]
** 計算システム論第二 [#l207d376]
- 担当：中村 宏 准教授
- 1.5単位
-- 数理：限定選択C
-- システム：限定選択B
- 10:15-11:45 工学部六号館 62講義室
-成績評価
--試験による。持ち込み不可~
出席は救済のみ
**試験関係 [#r560fa0d]
//-だれか過去問の答え作ってくれないかなぁ。
-不完全ですがversion2うp。授業を受けていない人も、一通り...
--''第二問の(1)(ア)は、講義の定義からいくと、CPI＝(必ずキ...
--''↑俺もそう思った。あと、第一問の(1)は空欄１が「PC <- P...
--↑多分それであっています。それから、残りの答えはしばしお...
--''↑最初のを書いた人間です。ですよねー。第二問の(1)(ア)...
--↑を補足すると(1)(イ)はcycle time=1.25[nsec],miss penalt...
CPI=1+0.4×0.05×80＝2.6,実行時間は(2.6×1.25)/(5×1)＝0.65（...
//あと(2)(ｳ)で実行時間長くなったんですけど・・
-自分の計算だと4.96って正解の5に近い値になったのは偶然?(s...
-第2問（ア）について。ミスペナルティ100nsだけど、実際には...
-(イ)については、ペナルティ100nsはかわらないままプロセッ...
-(ウ)では各々求めたCPI値(a,bとしよう)から以下の計算をすれ...
-みんな名乗ろうよ(by sen)
**参考文献とその他役に立ちそうなもの [#qb7c25e0]
参考書。いわゆるパタヘネ本。
--Conmputer Organization & Design: The Hardware/Software ...
--[[コンピュータの構成と設計>"http://www.amazon.co.jp/コ...
-[[MIPSシミュレータ>http://pages.cs.wisc.edu/~larus/spim....
-[[講義ページ>http://www.hal.rcast.u-tokyo.ac.jp/~nakamur...
パスワードはお友達に聞いてね。
-[[九大の講義ノート>http://ocw.kyushu-u.ac.jp/0009/0006/l...
-[[論理合成を忘れてしまった人はこちら>http://www.ssc.pe.t...
**内容 [#t7f6cf42]
物理的制約のもとで複数のシステムを有機的に組み合わせ，計...
+計算システムのモデリング
+命令セットアーキテクチャ
+データパスと制御論理
+メモリシステム：キャッシュメモリ、仮想記憶
+入出力制御
+プロセスの管理
+フォールトトレラントシステム
**授業ノート [#ra620884]
Presented by sen. tzik all blame reserved.~
誤植は見つけた人が直すものです
+計算システムとは
--目的に応じて
--ハードウェアとソフトウェアを組みあわせて構成~
目的によってさまざまな構成がありうるが、基本は同じ。
++ハードウェア構成(p2,3)
--CPU(Central Processing Unit) ,Processing Unit(PU) + 主...
--出入力装置
--補助記憶装置(HDDとか)
--プロセッサの速度はムーアの法則に従って増加するのに対し...
でも、基本的な部分は変わってないよ。
+システム設計の階層
-プログラムの構成
--高級言語(C,C++) → コンパイル → a.out(バイナリ)
--高級言語による設計の時には、下位レベル(ハードウェアのこ...
++概念レベル(仕様書、頭の中)
++高級言語レベル(C,C++) ハードウェアに非依存
++機械命令レベル(PU依存)
++レジスタトランスファレベル
++ゲートレベル
++スイッチレベル
iii.までがソフト屋さんの仕事。ここが変わるとソフト、ハー...
ivはレジスタ間の転送をハードウェアで実現する手法を規定~
VHDL,Verilogとかのハードウェア記述言語を使う。~
データパスと制御論理~
~
v.は第一でやったところ~
vi.はトランジスタの話。基本的にはこのあたりを気にする必要...
+階層設計に関する検討
1つのシステムがとても複雑になってきている。~
→設計の見通しの良さ~
設計が階層化されていれば、バグが生じたときに1つだけ上の階...
→最終的な品質(製品としての性能と設計期間)
+セマンティックギャップ(semantic gap)~
高級言語の機能と、ハードウェアで実現されている機能(アセン...
高級言語マシンというものが、今から20年くらい前にはさかん...
RISC(Reduced insttuction set computer)~
→ハードウェアで実現する機能、命令は簡単なものでも良い。~
''プログラムの実行時間=(プログラムあたりの命令数)*(1命令...
高級言語マシンでは、1↓ 2↑~
RISCでは1↑2↓~
RISCでは単純な命令だけにして命令セットの数を減らすのが目...
'(1命令あたりの実行時間) = (1命令あたりの所要サイクル数)*...
単純な命令を繰り返すもののほうが、流れ作業に向いている。...
//中村先生… とても、ノートが取りにくいです…
//番号付きリストがうまく表示されないので、あとで書きなおす
//とても、眠いです…
+ハードウェア/ソフトウェア協調設計
例えば、組み込みとか、ちょっと凝った処理をしたいときにプ...
{ハードウェア|ソフトウェア}で実現する機能の決定。
//ハニョンハニョン
2.命令セットアーキテクチャ
2.1命令(instruction)
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
0.25 * 0.5 = 1.25(%)
PUが処理すべき動作を指示
命令セットアーキテクチャ(instruction set architecture)~
→命令の体系、ハードウェアとソフトウェアのインターフェイス...
命令の種類
-算術演算命令(加算、減算etc.)
-論理演算命令(and,or)
-データ転送命令(メモリなどとの間でデータを転送)
-分岐命令(if文のようなもの)
命令語(instruction words)~
命令を表現するword(バイナリ)
//MIPSの命令一覧を探したけど、見やすいのが無かった…
MIPSの命令については、これが分かりやすいかも~
http://ocw.kyushu-u.ac.jp/0009/0006/lecture/10.pdf
2.2 主記憶のアドレシング~
PUのレジスタは数十個(MIPSの場合は32ないし64個)なので、メ...
アドレス付けの単位
-バイトアドレシング → 1つの番地で、1バイト管理
-ワードアドレシング → 1つの番地で、1ワード(4bit)管理
主記憶のサイズ~
プリント2^32=2^32バイト(32bitアドレス空間) →4GB~
最近はこれじゃ足りないので、64bitアドレス空間を使っている...
命令セットアーキテクチャ
プロセッサAからプロセッサBへ。~
今までのソフトウェアが動くか？~
そもそも同じなら、完全互換。命令を追加した場合は上位互換...
エンディアン(Endian)
-big endian
-litte endian
数値データを置く場所がどちらへ進んでいくか？ ~
数値データのMSD(most significant digit)をアドレス番号の小...
命令セットの違いはソフトウェア側でなんとかなる。でも、ア...
2.3命令セットアーキテクチャの分類
用意されているオペレーション(操作)の種類による分類ではな...
+PU内部のオペランド指定方式
+主記憶のオペランド指定方式
2.3.1 PU内部の記憶部
-スタック(stack)
-アキュムレータ(accumurator) ←レジスタが一つしかないと思...
-レジスタ(register) ←最近の汎用プロセッサはこれ
詳細はググれカス(by 中村先生)
4/28
2.3.2 汎用レジスタ方式における記憶部の指定方法~
(1)regiaster addressing~
レジスタを指定する~
add r1,r2,r3 # r1 <= r2 + r3
(2)immediate addressing(直値) ~
オペランドの値を指定する
add r1,r2,1000 # r1 <= r2 +1000
(3)direct addressing~
主記憶のアドレスを直接指定
(3-1) register~
load r1,(r2) # r1 <= mem[r2]
主記憶のアドレスを保持するレジスタを指定する
(3-2) immediate~
load r1,(1000) # r1 <= mem[1000]
主記憶のアドレスを直接指定する
(3-3)index~
load r1,24(r2) # r1 <= mem[r2+24]
レジスタとオフセットで指定
(4)indirect addressing(間接参照)
-主記憶のアドレスを間接的に指定
-主記憶のアドレスを保持する別の主記憶のアドレスを指定する
(4-1)register~
load r1,@(r2) # r1 <= mem[mem[r2]]
(4-2) immediate~
load r1,@(1000) # r1 <= mem[mem[1000]]
(4-3) index
load r1,@24(r2) # r1 <= mem[mem[r2+24]]
2.4 RISC(reduced instruction set computer)~
命令セットアーキテクチャの1カテゴリ。明確な定義はないが、...
-命令長が一定
-論理、算術命令のオペランドはレジスタのみ
-ロードストアアーキテクチャ~
主記憶のデータはロード命令、ストア命令のみで操作
lw $1,4($2)
add $1,$1,1
sw $1,4($2)
などという形で書かなければいけない。
-単純なメモリアドレシング(indirect addressingはない)
RISCの方針~
命令を単純化して、命令数は増加しても命令当りの処理時間を...
処理時間 = (命令数)*(命令あたりの処理時間)~
このあたりは、後でパイプラインやらないと分からないかも
3.データパスと制御論理~
データパス(data path)~
所望の処理を実現するためのデータが流れる経路
//http://urasoku.blog106.fc2.com/blog-entry-368.html
//てらえろす
-レジスタ等の記憶装置
-算術論理演算回路
-その間の相互接続
//たぶん、図が多くなって書けなくなるとおもうのでぐぐって...
制御論理~
所望の処理を実現するために、データパス上のデータ転送を制...
有限状態機械(Finite State Machine)で表現することが多い
実現方法:wired logic(有線論理)→FFと組合せ回路
3.1データパス~
(1)構成要素~
演算器、マルチプレクサ、レジスタ、メモリ~
(1-1)演算器:複数の入力に対し、制御信号で指定される演算を...
(1-2)マルチプレクサ~
複数の入力に対して、制御信号で指定された入力を選択して出...
(1-3)レジスタ:記憶部
機能的にはD-FFと類似だが、N-bitデータを扱う。制御信号(wri...
(1-4)レジスタファイル
M個のレジスタを扱う。入力出力をどれだけ許すか？~
最低、2入力1出力(そうじゃなきゃ演算ができないから)
3.2制御論理~
所望の動作をデータパス上で実現するための論理
(1)wired logic(布線論理)による方法。ハードウェア(FFと組み...
高速だが設計は大変~
(2)マイクロプログラムによる方法。命令より一段下のレベルの...
設計変更は容易だが、低速
3.3データパスと制御論理の設計~
「全ての命令の動作を実現するハードウェア」~
(1)各命令の実行ステージの分割~
いくつ？ 各ステージの動作は？~
ステージ：1サイクルに対応
(2)前項を満たすデータパスの構築~
該当するデータパス上で、各ステージの動作を実現する制御論...
(3)データパスはゲートレベルスイッチで対応~
制御論理は状態遷移図で与えられているので、前述の二つの方...
1,2レジスタトランスファレベル設計
6/2
4.メモリシステム~
4.1 キャッシュメモリ~
4.1.1 概念~
キャッシュ：大切なものを隠しておく場所~
方針：高速かつ大容量な記憶装置が手に入ればいいのだが、一...
根拠：局所性(locality)~
時間的局所性~
ある情報が参照されると、すぐ後にまた参照される傾向がある。
空間的局所性~
ある情報が参照されると、近くの情報も参照される傾向がある。
-用語
キャッシュヒット~
参照される情報がキャッシュにあること~
キャッシュミス~
参照される情報がキャッシュにないこと~
ヒット率~
参照時にヒットである割合~
メモリアクセス時間~
= (ヒット率) * (キャッシュアクセス時間) + (ミス率) * (主...
高速化~
キャッシュをどう構成させるか？~
-ヒット率を上げる
-キャッシュアクセス時間を短縮する
4.1.2 主記憶とキャッシュのアドレスマッピング~
メモリからキャッシュへ持ってきたデータをどう配置するか？
(1)direct mapping(ダイレクトマップ方式)~
主記憶のコピーの格納場所は、キャッシュ上で一意に定まる。~
(2)fully associative(フルアソシアティブ)
主記憶のコピーの格納場所はキャッシュ上の任意の場所~
(3)N-way set associative(n-ウェイセットアソシアティブ)
主記憶のコピーの格納場所は、キャッシュ上でN通りある。~
キャッシュ上でデータを探す時間とキャッシュの使い易さのト...
4.1.3 キャッシュの構成と制御(p21)~
(1) ダイレクトマップの例~
ブロックサイズ4B,容量4KB~
(1-1)キャッシュの構成~
ブロック数：1024~
ブロックのデータ部：4B~
index：キャッシュブロック番号
V:当該ブロックが有効かどうか？
tag：当該ブロックに格納されているデータのアドレス~
data:当該ブロックに格納されているデータの本体~
(1-2)メモリ参照時のアドレスビットの意味~
32bitのアドレス空間~
offset部：アドレスの下位2bit[1:0]
→ブロック内のオフセットを定める
index部：アドレスの次の下位10bit[11:2]
→参照すべきcache indexを定める
tag部：上位20bit[31:12]
→tag部と比較される
(1-3)読み出しと参照の動作~
(1)参照すべきアドレスのindex部からcache index を決定し、t...
(2)キャッシュ内のtag部と、参照すべきアドレスのtag部が一致...
-不一致 → キャッシュミス
-一致
--有効ビット →キャッシュヒット
--無効ビット →キャッシュミス
(3)キャッシュヒット時~
キャッシュのデータ部から所望のデータを読みだす
キャッシュミス時~
主記憶にデータを読みにいく
-参照されるデータを含む1ブロック分のデータを主記憶へ持っ...
-現在のキャッシュの当該ブロックを破棄して、新しいデータを...
//6月16日 遅刻した
4.2.仮想記憶(virtual memory)~
4.2.1 概要~
物理的には小容量しかないメモリを仮想的に大容量のメモリと...
OSの管理下で、ハードウェア機能のサポートにより限られた容...
-キャッシュと仮想記憶の対比
○ キャッシュ 仮想記憶~
制御単位 ブロック(固定、32Bから256B) ページ(固定:4KBから...
入れ替え制御 ハード ソフト~
(1)原理~
主記憶の記憶領域が不足したら不要な主記憶の一部を2次記憶へ...
swap in : 2次記憶から主記憶へ~
swap out: 主記憶から2次記憶へ~
(2)アドレス空間~
論理アドレス空間(logical address space)~
ユーザプログラムが実行されているアドレス空間(仮想アドレス...
物理アドレス空間(physical address space)~
主記憶上で実際に提供されているアドレス空間(実アドレス空間...
(3)制御の概略~
1.PU上でメモリアクセス実行~
2.論理アドレス→物理アドレスの変換(DAT:dynamic address tra...
3.変換可能→物理アドレスを用いて主記憶アクセス~
変換不可→該当論理アドレスは主記憶にない。~
→割り込み発生(ページフォールト)~
→OSに制御が渡る→OSがswap in/out を行なう。
4.2.2 アドレス変換方式~
アドレス変換の単位:ページ(固定) / セグメント(可変)
(1)ページング(paging)~
1953(英マンチェスター大)
プリント22p
-変換方式~
論理アドレス~
ページ番号とページのオプトからなる。~
論理アドレスのページ番号を物理アドレスページ番号へ変換
(2)セグメンテーション~
1961(米Burroughs社)
主記憶に置く単位をプログラムの論理的に独立した単位(セグメ...
ページングとの違いは多きさが可変であること
-長所 セグメントは属性が明確。記憶保護に最適~
-短所 外部フラグメンテーションが生じる~
→ページ化セグメント(paged segment)などがある
//前回senは休んでいました
// 6/30
5.入出力制御~
5.1 入出力制御方式~
1.特別なI/O方式~
アドレスとは別
2.address mapping I/O~
あるアドレスへの読み書きを入出力として扱う。
5.1.2 入出力装置からの通知検出方法
1.ポーリング方式~
CPUが定期的にI/Oデバイスを監視する。頻度が高ければ応答性...
2.割り込み方式(次でまたやる)
デバイス手動で、終了を割り込みで通知する。
割り込みを(ハードウェアが)検出すると、OSへ制御を渡して割...
ポーリングとは逆に、監視のオーバーヘッドは無いが、プロセ...
。
5.1.3 データ転送を行う主体による分類~
(1) プログラム制御方式~
CPUがプログラムモードの入出力命令によって、入出力装置を起...
入出力命令実行中はCPU動作が中断するため、大量のデータ転送...
(2) DMA制御方式(direct memory access)~
CPUとは独立に、主記憶と入出力装置のデータ転送を行う機構。...
(step1) CPUは入出力装置のID、実行すべき処理、転送先/元の...
(step2) DMAはバスの調停と入出力装置における処理を開始~
(step3) DMA転送が終了したら割り込みで通知~
例題. ポーリングと割り込み
一回のポーリングに400サイクル、CPU 500MHz
4words(16B毎)転送が行われ転送性能 4MB/sec のディスク
データが失われないようにポーリングで検出する場合のポーリ...
解.
(1) 必要なポーリングの頻度
4MB/16B = 250k(回/sec)
1秒あたりのオーバヘッドは
400 * 250k = 100Mサイクル
100M/500M = 20% のオーバーヘッド
(2) 割り込みの場合
一回の割り込み処理に、500サイクル要する場合
オーバーヘッドは？
割り込み頻度はポーリングと同じく250k
オーバーヘッドは (250k * 500サイクル)/500Mサイクル = 25%
(3) ディスクの入出力処理は全体の5%だけである場合
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
// 0.25 * 0.5 = 1.25(%)
25 * 0.05 = 1.25(%)
(4)DMA転送のオーバーヘッド
同じディスク
DMA転送のsetupに1000サイクル
DMA転送の終了の割り込みに5000サイクル
平均転送サイズ 8KB
このときのオーバーヘッド
ディスクは100%active
4MB/8KB = 0.5k(回/sec)
1回のDMA転送のオーバーヘッド
6000サイクル
(6000 * 0.5)/500M = 0.6%
5.2 割り込み~
不定期に起こる事象に対して、プログラムの実行を中断してし...
5.2.1 割り込みの種類
-入出力割り込み~
キーボード、マウス
-システムコール割り込み
システムコールの発行(標準出力へ表示など)
-プログラム割り込み(ページフォールト、異常実行(0割り))
-外部割り込み(リセット)
precise/imprecise
正確な割り込み(復帰再開可能)
不正確な割り込み(復帰再開不可能)
-precise~
割り込みを発生させた命令以前の命令は終了し、割り込み処理...
→ページフォールトはpreciseであるべき~
~
0除算：impreciseでも良い~
preciseの割り込みは思いの他大変
5.2.2 // 6/30
5.2.2 割り込み処理方式~
割り込みの受付は命令単位
+割り込みを受け付けるかを判断(優先度がある場合)
+CPUは実行中のプロセスを中断し、再開に必要な情報(PC、レジ...
+割り込みベクタを参照し、指定されている値をPCに設定~
=割り込み処理ルーチン 割り込みハンドラに移行 OSに制御が移行
+処理が終了したら、退避情報を復元して処理を再開
6.オペレーティングシステム(Operating system)
ユーザとハードウェアシステムのインターフェイス~
=ハードウェアの仮想化
6.1 役割~
+資源管理
--ハードウェア資源
---PU,主記憶,ディスク等の資源
--ソフトウェア資源
---プログラム,データ等の資源
---パーミッションの管理なども
+利用者インターフェイス
ハードウェア資源の特性を抽象化して、ユーザに提供~
特性に応じて最適化をすることができない
+運転管理とRAS~
RAS~
R:reliability
A:availability
S:serviceability
→高信頼性が要求されるシステム(銀行のオンラインシステム)で...
6.2 プロセス管理とスケジューリング~
6.2.1 プロセス(process)~
OSからハードウェア資源の割り当てを受けて処理を実行してい...
(Linuxだとpsコマンド、Windowsではタスクマネージャで見られ...
6.2.2 プロセスの状態と遷移~
(1)プロセスの状態
-実行状態：プロセスにCPU資源が割り当てられている
-実行可能状態：CPU資源は割り当てられていないが、割り当て...
-待ち状態：何らかのイベントを待っている状態
図が書けねー
・遷移状態~
1.初期状態：新しいプロセスが生成されると実行可能状態に~
2.実行可能状態→実行状態~
CPU資源が空いた時にスケジューリングアルゴリズムに従って、...
3.実行状態→実行可能状態~
特定のプロセスがCPU資源を占有するのを避けるために、あらか...
・プロセスの管理と切り替え~
OS内では、
-親プロセス/子プロセスへのポインタ
-プログラムのコード領域とデータ領域へのポインタ
-プログラムカウンタ、レジスタの退避領域
-メモリ管理状態(ページテーブルへのポインタ)
などを管理
プロセス切り替え時に必要な処理~
再開に必要な処理の退避~
CPU資源内にあるプロセスの情報、プログラムカウンタ、レジス...
6.2.3 スケジューリングアルゴリズム~
スケジューリング~
今回はCPUスケジューリング
スケジューラの評価基準
-CPU利用率
-ターンアラウンド時間 プロセスの実行要求から、実行までの...
-待ち時間 プロセス完了までに、実行可能状態のキュー(待ち行...
-応答時間
//senの遅刻によりぐぐれかす
7.フォールトトレラントシステム
障害に対して強いシステム
-故障(fault)
-fault avoidance と fault torerance
-fail safe ,fail stop
ユーザの期待するサービスを提供できないときシステムが機能...
-fail soft
ユーザが期待するサービスが提供できないとき、性能を落とし...
7.2 評価尺度~
応用分野によって必要となる信頼性は異なる。趣味の自宅鯖だ...
-信頼性
どれだけの時間障害を発生させずにサービスを提供できるか
-可用性
使いたいときにサービスが提供される確率
-保守性
修理のしやすさ、迅速さ
例えば、何十年も宇宙にあって簡単に修理のできない人工衛星...
7.2.1 フォールトカバレッジ(fault coverage)~
対象とするフォールト集合が現実に起こりうるフォールト全体...
計算システムにおけるフォールトの分類
-accidental fault(偶発的)
-physical fault(物理的)
--内部要因
--外部要因
-human fault(人為的：うっかり)
-malicious fault(人為的：故意)
-故障検出~
信頼度は故障検出能力に大きく依存
評価モデル~
どういう故障が起こるかの抽象モデル~ 良いモデルは、カバレ...
7.2.2 信頼度(rliability)~
障害発生を統計的分析を持つ確率事象として扱う。
f(t) 障害が生じる確率密度関数~
時刻tからt+dtの間に障害が生じる確率はf(t)dt
0からtの間のtauで障害が発生する確率F(t)
#mimetex(F(t) = \int^t_0 f(\tau)d \tau)
逆に時刻tまで障害が発生しない確率は
#mimetex(R(t) = 1 - F(t))
-障害率 lambda(t)~
時刻tまで無障害という条件の元で、tからt+dtに障害が起きる...
#mimetex(f(t) = R(t)\lambda(t))
#mimetex(R(t) = 1 - F(t))
#mimetex(\frac{dR(t)}{dt} = -\frac{dF(t)}{dt} = -f(t))
変数分離で積分すると
#mimetex(R(t) = \exp(-\int^t_0 \lambda(f)dt))
平均寿命 MTTF(mean time to failure)
#mimetex(MTTF = \int^\inf_0R(t)dt)
lambda(t)はどんな関数？~
システムのハードウェア バスタブ曲線(経験則)~
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
