計算システム論第二のバックアップ(No.9)

講義日程-2008年度夏学期

計算システム論第二 †

担当：中村宏准教授
1.5単位
- 数理：限定選択C
- システム：限定選択B
10:15-11:45 工学部六号館 62講義室
参考文献
いわゆるパタヘネ本。
- Conmputer Organization & Design: The Hardware/Software Interface 3rd Edition
- コンピュータの構成と設計

MIPSシミュレータ

講義ページ
パスワードはお友達に聞いてね。

九大の講義ノート

成績評価
- 試験による。持ち込み不可
  出席は救済のみ

↑

内容 †

物理的制約のもとで複数のシステムを有機的に組み合わせ，計測，認識，制御，知能などを実現する最適化されたインタラクティブな計算システムの構成理論と手法を学ぶ。

計算システムのモデリング
命令セットアーキテクチャ
データパスと制御論理
メモリシステム：キャッシュメモリ、仮想記憶
入出力制御
プロセスの管理
フォールトトレラントシステム

↑

授業ノート †

Presented by sen. tzik all blame reserved.
誤植は見つけた人が直すものです

計算システムとは
- 目的に応じて
- ハードウェアとソフトウェアを組みあわせて構成
  目的によってさまざまな構成がありうるが、基本は同じ。

ハードウェア構成(p2,3)

CPU(Central Processing Unit) ,Processing Unit(PU) + 主記憶
出入力装置
補助記憶装置(HDDとか)

プロセッサの速度はムーアの法則に従って増加するのに対し、記憶装置や入出力の速度は相対的に遅く、そこがボトルネックになっている。それを解決するための手法が最近のプロセッサには取りいれられている。(キャッシュとか)。たとえば、HDDの読み込み速度はCPUの100万倍くらい遅い。
でも、基本的な部分は変わってないよ。

システム設計の階層

プログラムの構成
- 高級言語(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↑
'(1命令あたりの実行時間) = (1命令あたりの所要サイクル数)*(サイクル時間)'

単純な命令を繰り返すもののほうが、流れ作業に向いている。面倒なのでウィキペとか参考書とかを参照(パイプライン処理:http://ja.wikipedia.org/wiki/パイプライン処理/)

ハードウェア/ソフトウェア協調設計例えば、組み込みとか、ちょっと凝った処理をしたいときにプロセッサを設計することはよくある。(携帯電話であればコストダウン、数値計算だけに特化したスパコンを作るetc.)一般的に、ハードウェアでやることを増やすと性能はあがるが、コストも増える。ハード/ソフトの協調設計ではこのトレードオフになる。どうするのがいいかはお金と時間による
{ハードウェア|ソフトウェア}で実現する機能の決定。

2.命令セットアーキテクチャ 2.1命令(instruction) PUが処理すべき動作を指示

命令セットアーキテクチャ(instruction set architecture)
→命令の体系、ハードウェアとソフトウェアのインターフェイス、計算機構成の重要な抽象化レベル

命令の種類

算術演算命令(加算、減算etc.)
論理演算命令(and,or)
データ転送命令(メモリなどとの間でデータを転送)
分岐命令(if文のようなもの)

命令語(instruction words)
命令を表現するword(バイナリ)

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へ。
今までのソフトウェアが動くか？
そもそも同じなら、完全互換。命令を追加した場合は上位互換。Intelのx86は、上位互換を維持するために、複雑怪奇な命令セットになっているのだとか…

エンディアン(Endian)

big endian
litte endian 数値データを置く場所がどちらへ進んでいくか？
数値データのMSD(most significant digit)をアドレス番号の小さい方に対応させるのがbig endianで、LSD(least significant digit)をアドレス番号の小さい方に対応させるのがlitte endian。互いにデータのやりとりをしなければ何も問題はない。 mipsはどちらにも対応していた(はず)

命令セットの違いはソフトウェア側でなんとかなる。でも、アドレスづけの単位やらエンディアンの違いは、どうにもならないこともある。

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[1000]

(4-3) index

load r1,@24(r2) # r1 <= mem[mem[r2+24]]

2.4 RISC(reduced instruction set computer)
命令セットアーキテクチャの1カテゴリ。明確な定義はないが、一般的に次のような特徴を有するものがRISCと呼ばれる。

命令長が一定
論理、算術命令のオペランドはレジスタのみ
ロードストアアーキテクチャ
主記憶のデータはロード命令、ストア命令のみで操作
```
lw $1,4($2)
add $1,$1,1
sw $1,4($2)
```
などという形で書かなければいけない。
単純なメモリアドレシング(indirect addressingはない)

RISCの方針
命令を単純化して、命令数は増加しても命令当りの処理時間を短くすることで、全体jの処理を高速化する。(また、命令形式が単純であることはパイプライン処理のし易さにも影響する)

処理時間 = (命令数)*(命令あたりの処理時間)
このあたりは、後でパイプラインやらないと分からないかも

3.データパスと制御論理
データパス(data path)
所望の処理を実現するためのデータが流れる経路

レジスタ等の記憶装置
算術論理演算回路
その間の相互接続

制御論理
所望の処理を実現するために、データパス上のデータ転送を制御する論理。データパス上のタイミング制御も含む
有限状態機械(Finite State Machine)で表現することが多い実現方法:wired logic(有線論理)→FFと組合せ回路

3.1データパス
(1)構成要素
演算器、マルチプレクサ、レジスタ、メモリ
(1-1)演算器:複数の入力に対し、制御信号で指定される演算を行う。

(1-2)マルチプレクサ
複数の入力に対して、制御信号で指定された入力を選択して出力(selecter)

(1-3)レジスタ:記憶部機能的にはD-FFと類似だが、N-bitデータを扱う。制御信号(write enable)がある。MIPSの場合は32bit

(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 を決定し、tagを参照
(2)キャッシュ内のtag部と、参照すべきアドレスのtag部が一致するかを比較

不一致 → キャッシュミス
一致
- 有効ビット →キャッシュヒット
- 無効ビット →キャッシュミス

(3)キャッシュヒット時
キャッシュのデータ部から所望のデータを読みだす

キャッシュミス時
主記憶にデータを読みにいく

参照されるデータを含む1ブロック分のデータを主記憶へ持ってくる
現在のキャッシュの当該ブロックを破棄して、新しいデータをキャッシュのデータ部へ格納、キャッシュのタグを更新

計算システム論第二 のバックアップ(No.9)