Document

Report
先端ソフトウェア工学II
組込みシステムとは?

組込みシステムの例







携帯電話
ゲーム機
ディジタル家電
車載機器
各種制御機器
etc
定義

厳密な定義があるわけではなく、製品に組込
まれている汎用ではないディジタルシステム
組込みシステムの歴史

従来



近年



電子回路で実現(もっと古くは機械式制御)
プログラマビリティはあまりない
マイクロコントローラ(マイコン)を用いたシステ
ム構築
PIC,AVR,H8,78K
プログラマブルだが高度な処理は不可能
最近


SH,ARM,MIPS,PPC,Atom,Core2
高性能プロセッサを用いたシステム構築
高度な信号処理を用いた複雑な処理の実現
アナログ制御
外乱
動作信号
目標値
ガバナ
基準入 +
力要素 基準入力
制御信号
制御器
調節部
操作量
アクチュ
エータ
操作部
フィードバック
主フィードバック量 要素
検出部
制御装置
オペアンプ(積分回路,NECEL)
従来
フィードバック制御系
制御対象
出力
ディジタル制御
外乱
目標値
ディジタル
演算器
D/A
アクチュ
エータ
A/D
検出器
ディジタル
制御器
ディジタル制御系
マイクロコントローラ・マイクロプロセッサの利用
制御対象
出力
マイコン・プロセッサの発達
高性能組込みプロセッサ(AM3517,TI)
マイコン(H8/3052B,ルネサス)
近年
最近
組込みマルチコアプロセッサ
MP211,NEC
ARM11MPCore,ARM
ION,NVIDIA
コンフィギュラブルプロセッサ


FPGA (Field Programmable Gate Array):
プログラマブルなロジックデバイス
PSoC (Programmable System-on-Chip):
プロセッサ+プログラマブルアナログ回路
Xilinx FPGA
Cypress PSoC
組込みシステムの一般的な構成





プロセッサ:ソフトウェアを実行。制御の中
心。
メインメモリ:ソフトウェア実行時の主記憶。
DRAMあるいはSRAMで構成。
2次記憶装置:主としてプログラムの保存
に利用。電源を切っても記憶を保持。フ
ラッシュやディスク。
周辺機器:画像処理HW、音声処理HW、
ネットワークIF等の様々な演算・処理デバ
イス。
各種I/O:ディスプレイ、タッチパネル、キー
ボード等の入出力。
プロセッサ
メインメモリ
2次記憶装置
周辺機器
各種I/O
バス
組込み用システムボードの例

Armadillo-500 FX(Atmark Techno, Inc.)


CPU: ARM1136JF-S
OS: Linux2.6
組込みシステムの動作





電源投入(パワーオンリセット)
自己診断
ブートローダ起動
OS 起動
アプリケーション起動
プロセッサ
メインメモリ
2次記憶装置
周辺機器
各種I/O
バス
自己診断


POST (Power On Self Test): 電源投入時
に実行されるシステムのテスト。プロセッサ、
メモリ、周辺機器等の故障の有無を調べる。
BIST (Built in Self Test): プロセッサ、周
辺機器等にあらかじめ組み込まれている
テスト。システムによっては、POSTの際に
BISTの機能を利用して故障の有無を調べ
る。
ブートローダ(boot loader)


オペレーティングシステムを起動する準備
をするソフトウェアプログラム。IPL(Initial
Program Loader)、ブートストラップローダ
(bootstrap loader)とも呼ばれる。
主な機能




プロセッサの初期化
メモリ設定
周辺デバイス初期化
プログラムのロードおよび実行
様々なブートローダ



Redboot:eCos(Embedded Configurable
Operating System)ベースのブートローダ。
http://sources.redhat.com/redboot
LILO:LInux LOder。x86 Linuxで良く使わ
れていたブートローダ。
GRUB:GRand Unified Bootloader。GNU
の開発した高機能なブートローダ。最近、
x86 Linux で良く利用されている。
Redboot

eCos の HAL (Hardware Abstraction
Layer) に基づく、信頼性が高く、コンパクト
で、設定しやすく、移植性の高い組み込み
向けブートローダ
オペレーティングシステム


オペレーティングシステム(OS:Operating
System)とは?:ハードウェア、メモリ等の
計算機資源を管理し、アプリケーションプ
ログラムに対するインターフェースを提供
するソフトウェア。
組込み向けOS




eCos
ITRON
VxWorks
WindowsCE
PC におけるLinuxの起動手順
BIOS (ROM
ブートローダ)
CPUをリアルモードに
設定し初期化開始
初期化部
POSTによるデバイス
等の初期化
BIOS部
ブートメディアを選択し
ブートローダに飛ぶ
ブートローダ部
Linuxカーネル
ディスクブー
トローダ
ディスク、デバイス等の初
(GRUB)
Stage1.5を見つけ制御
期化およびプロテクトモー
を渡す
圧縮カーネルイメージ
ドへの移行
Stage1
setup.S
ファイルシステムを読の展開、ページテーブ
む準備をしStage2に移
ル初期化head.S
Stage1.5
行rubの本体を起動
G
Stage2
main.c
割り込みテーブル初期化
システム時間初期化
コンソール初期化
仮想ファイルシステム初
期化etc
BIOS とは



Basic Input Output
System
ハードウェアデバイス
との抽象度の高いソ
フトウェアインター
フェース
代表例



VGA BIOS
SCSI BIOS
ACPI BIOS
x86プロセッサの動作モード

リアルモード




8086互換モード
実アドレス
20ビットのアドレス空間にアクセス可能(1Mバ
イト)
プロテクトモード



32ビットリニアアクセス空間
仮想記憶の提供
アクセス制御の実現


セグメント毎の読み取り・書き込み・実行の設定
ユーザ・システム・カーネルの区別
ソフトウェアの階層構造

演算を実行するハードウェアをソフトウェア
で階層的に抽象化
ユーザが利用するソフトウェア
オペレーティングシステム、コンパイラ等
アプリケーションソフトウェア
システムソフトウェア
ハードウェア
具体例(Android)
ハードウェアへのアクセス

OS がない場合

仕様:0100が0ならLED消灯、1なら点灯。リ
セット値は0。
プロセッサ
0000
メインメモリ
メインメモリ
LED
00ff
0100
0
LED
ハードウェアへのアクセス

OS がない場合

直接0100番地を読み書き
int * led;
led=(int *) LED_ADDR;
*led=1;
プロセッサ
0000
メインメモリ
メインメモリ
LED
点灯
00ff
0100
1
LED
ハードウェアへのアクセス

OS がない場合

直接0100番地を読み書き
int * led;
led=(int *) LED_ADDR;
*led=0;
プロセッサ
0000
メインメモリ
メインメモリ
LED
消灯
00ff
0100
0
LED
ハードウェアへのアクセス

OS がある場合

デバイスの存在するアドレス空間がカーネル
int * led;
によって管理される
led=(int *) LED_ADDR;
*led=1;
プロセッサ
0000
ユーザ空間
メインメモリ
LED
OSがこのアクセスを
許可しない
メインメモリ
カーネル空間
00ff
0100
0
LED
ハードウェアへのアクセス

OS がある場合

解1:root 権限で動かす。
プロセッサ
0000
ユーザ空間
メインメモリ
メインメモリ
LED
カーネル空間
00ff
0100
0
LED
ハードウェアへのアクセス

OS がある場合

解1:root 権限で動かす。
int * led;
led=(int *) LED_ADDR;
*led=1;
プロセッサ
0000
ユーザ空間
メインメモリ
メインメモリ
LED
点灯
root権限だとアクセス可
カーネル空間
00ff
0100
1
LED
ハードウェアへのアクセス

OS がある場合

OS が無い場合と同様にアクセス可能だが、
デバイスへのアクセスを要求するすべてのプ
ロセスにroot権限が必要となり問題。
プロセッサ
0000
ユーザ空間
メインメモリ
メインメモリ
LED
点灯
カーネル空間
00ff
0100
1
LED
ハードウェアへのアクセス

OS がある場合

解2:デバイスドライバによってカーネル管理下
int fd;
のデバイスにアクセス
fd=open(“led”,O_RDWR);
write(fd,1);
プロセッサ
0000
ユーザ空間
write() read()
メインメモリ
メインメモリ
ドライバ
LED
カーネル空間
00ff
0100
0
LED
ハードウェアへのアクセス

OS がある場合

解2:デバイスドライバによってカーネル管理下
int fd;
のデバイスにアクセス
fd=open(“led”,O_RDWR);
write(fd,1);
プロセッサ
0000
ユーザ空間
メインメモリ
メインメモリ
ドライバ
LED
点灯
カーネル空間
00ff
0100
1
LED
注1:実際には、アドレス変換を伴う場合が殆どであり、こんなに単純ではない。
注2:write の正しい使い方は man を参照。
まとめ

組込みシステムの歴史


組込みシステムの構成と動作



プロセッサの発達
ブートローダ
起動手順の概要
ソフトウェアの階層構造

ハードウェアへのアクセス例
プロセッサの仕組み
参考書

コンピュータの構成と設計~ハードウエア
とソフトウエアのインタフェース 第3版 (上)
(単行本) デイビッド・A. パターソン (著),
ジョン・L. ヘネシー (著), David A.
Patterson (原著), John L. Hennessy (原
著), 成田 光彰 (翻訳)
プロセッサとは?

演算処理装置のこと。一般には、メモリ上
に保持された命令を実行する。CPUやMPU
とほぼ同義。


CPU:Central Processing Unit の略。 中央処
理装置。
MPU:Micro Processing Unit の略。半導体製
品として1チップであるかその流れをくんでい
る処理装置に対して使う。CPU より広義。
計算機の歴史


ENIAC:Presper Eckert、
John Mauchly らによって開
発。配線を入れ替えることに
よってプログラムを行う。内
部は10進表現。
EDVAC: Presper Eckert、
John Mauchly らによって開
発。ENIACと異なり、内部2
進表現。データだけでなく命
令もメモリに保存。
Stored program
First Draft of a Report on the EDVAC. JOHN VON NEUMANN
http://cva.stanford.edu/classes/cs99s/papers/vonneumann-firstdraftedvac.pdf
Von Neumann Machine

広く使われているプロセッサのモデル。
Memory
Control
Arithmetic
Unit
Logic Unit
Input
Accumulator
計算能力は Turing Machine と等価
Output
そもそも計算って何?
(補足あるいは復習)
コンピュータとその抽象化

ディジタルコンピュータ





パーソナルコンピュータ
携帯電話
コンピュータでできることは?
コンピュータの本質って何?
ゲーム
種類による違いは?
メインフレーム
スーパーコンピュータ
抽象的な計算機(コンピュータと同じ
意味)を定義することによって、計算
機の本質を明らかにする
計算の例

以下の計算を例として考える

3と4の和を求める


与えられた0と1からなる文字列が01の繰り返
しか否かを判定する



3+4=7
01101100011 → ×
0101010101 → ○
任意の0以上の整数nに対し、与えられた0と1
n n
0
からなる文字列が 1 という形式であるか
否かを判定する
計算機による解法

組み合わせ回路:3+4のような加算は組
み合わせ回路*である加算器で実現可能
3→011
4→100
2進数表現
011
+ 100
111
2進数による加算
011
111
100
加算器による計算
*組み合わせ回路:現在の入力のみによって出力が定まる回路。
詳細は論理回路の項目にて
計算機による解法

有限オートマトン:有限状態機械とも呼ば
れ、有限個の状態を持つ数学的なモデル。
0
終了状態
q1
q2
1
0,1
1
q3
0
状態
01の連続を受理する
有限オートマトン
計算機による解法

任意の自然数nに対し、与えられた0と1からなる
文字列が 0n1n という形式で表現できるか否か
を判定する
 有限オートマトンを使ってみる

入力 n の数に合わせて状態の数を増やしたい
有限オートマトンでは実現で
きない。計算の途中結果を
保持する機構が必要
プッシュダウンオートマトン

有限オートマトンにプッシュ/ポップによるア
クセスが可能なスタックを付加。
制御部
(有限オートマトン)
入力
プッシュ/ポップ
スタック
プッシュダウンオートマトン

n n
0 1 の受理
q1
 ,  $
0,   0
q2
1,0  
q4
 ,$  
q3
1,0  
a, b  c :入力からaを読む時、スタックの先頭にある
bをcに置き換える。bがε(空列)の場合、cを
スタックに積むのみであり、cがεの場合ス
タックからbを読みだすのみである。
Turing機械

有限オートマトンやプッシュダウンオートマ
トンよりも能力の高い計算モデル




Turing機械はテープに対し書き込みと読み出
しのどちらも可能
読み書きヘッドは左右のどちらにも動く
テープは無限長
Turing機械は拒否や受理に対応する特別な
状態に入るとすぐに停止する
制御部
Turing機械
・・・
計算能力の関係
有限オートマトン
プッシュ
ダウン Turing
オート 機械
マトン
有限オートマトンの形式的定義

定義:有限オートマトン(finite automaton)
は5個組 (Q, ,  , q0 , F ) である。





Q は状態と呼ばれる有限集合
 はアルファベットと呼ばれる有限集合
 : Q    Q は遷移関数
q0  Q は開始状態
F  Q は受理状態の集合
プッシュダウンオートマトンの形
式的な定義

プッシュダウンオートマトンは6個組
(Q, , ,  , q0 , F ) である。ここで、 Q, , , F
は全て有限集合であり、

Q は状態の集合
 は入力アルファベット
  はスタックアルファベット

 : Q      P (Q   ) は遷移関数
 q0 は開始状態
 F  Q は受理状態の集合
とする。

Turing機械の形式的な定義

Turing機械は7個組 (Q, , ,  , q0 , qaccept, qreject)
である。ただし、Q, ,  は全て有限集合であり、
以下の通りである。
 Q は状態の集合
 は特別な空白文字⊔を含まない入力アルファベット
  は⊔ かつ   であるようなテープアルファベット
  : Q    Q    {L, R}は遷移関数
 q  Q は開始状態
0
 qaccept  Q は受理状態
q
 qreject であるような拒否状態
q
reject  Q は accept

計算理論の参考文献


計算理論の基礎,Michael Sipser 著,
ISBN:4-320-02948-8
計算モデル論入門-チューリング機械から
ラムダ計算へ-,井田哲雄・浜名誠著,
ISBN:4-7819-1135-8
Von Neumann Machine

広く使われているプロセッサのモデル。
Memory
Control
Arithmetic
Unit
Logic Unit
Input
Accumulator
Output
Memory


ビット列を保存する記憶装置。
アドレスでビット列の場所を
指定し、その値がビット列。
ロード、ストアと呼ばれる操
作によってメモリアクセスを
行う。


ロード:メモリから値を読む
ストア:メモリに値を書き込む
0
1
2
3
4
5
6
7
8
9
00001001
00001000
00000111
00000110
00000101
00000100
00000011
00000010
00000001
00000000
メモリの例(8ビット)
ALU および Control Unit

ALU (Arithmetic Logic Unit)


算術論理演算装置。演算結果を一時的に保
存する累算器を含んでいる。
Control Unit

命令の解釈および実行を行う。
命令の実行

右図の例を考える。

0番地の命令から実行
Control
Unit
ALU
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

9番地をロード
Control
Unit
ALU
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

9番地をロード
Control
Unit
ALU
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

9番地をロード
Control
Unit
ALU
00000001
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

1番地の命令をロード
(正しくはフェッチ)
Control
Unit
ALU
00000001
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

8番地を加算
Control
Unit
ALU
00000001
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

8番地を加算
Control
Unit
00000001+00000010=00000011
ALU
00000011
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

3番地の命令を実行
Control
Unit
ALU
00000011
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

3番地の命令を実行
Control
Unit
ALU
00000011
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000000
00000010
00000001
Memory
命令の実行

右図の例を考える。

3番地の命令を実行
Control
Unit
ALU
00000011
accumulator
0
1
2
3
4
5
6
7
8
9
9番地をロード
8番地を加算
7番地にストア
00000000
00000000
00000000
00000000
00000011
00000010
00000001
Memory
近代的なプロセッサの基本構造
0
メモリバス
PC
r0
r4
命令
デコーダ
r1
r5
制御処理
r2
r6
r3
r7
7
ALU
汎用レジスタが増えた程
度で基本は同じ
演算処理
15
メモリ
命令の種類

ロード/ストア命令


算術演算命令


+、ー、*、÷等の演算
論理演算命令


メモリとレジスタのアクセス
and、or、xor 等の演算
分岐命令

プログラムカウンタの書き換えによる制御の
変更
プロセッサの基本的な動作
リセット
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
0
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
0番地の命令のフェッチ
0
メモリバス
PC
命令
デコーダ
制御処理
0
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
注:一般にはリセット時に飛ぶアドレスが0番地とは限らない
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
1
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
2
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
分岐命令
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
3
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
4
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
分岐命令
メモリ
0
メモリバス
PC
4
命令
デコーダ
制御処理
命令:PCに0を代入
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
分岐命令
メモリ
0
メモリバス
PC
0
命令
デコーダ
制御処理
PCに0を代入
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
0番地の命令のフェッチ
0
メモリバス
PC
命令
デコーダ
制御処理
0
メモリ
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
ロード命令
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
1
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
1
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
命令:r0に16番地のデータをロード
演算処理
15
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
1
r0
0
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
命令:r0に16番地のデータをロード
演算処理
15
1
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
1
r0
1
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
2
メモリ
r0
1
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
3
メモリ
r0
1
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
3
r0
1
r4
0
r1
0
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
命令:r1に17番地のデータをロード
演算処理
15
2
ロード命令
メモリ
0
メモリバス
PC
命令
デコーダ
制御処理
1
r0
1
r4
0
r1
2
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
算術演算命令
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
4
メモリ
r0
1
r4
0
r1
2
r5
0
r2
0
r6
0
r3
0
r7
0
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
4
r0
1
r4
0
r1
2
r5
0
r2
0
r6
0
r3
0
r7
0
命令:r2にr0とr1を加えて代入
メモリ
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
4
r0
1
r4
0
r1
2
r5
0
r2
0
r6
0
r3
0
r7
0
命令:r2にr0とr1を加えて代入
メモリ
7
ALU
演算処理
15
命令実行&PCインクリメント
0
メモリバス
PC
命令
デコーダ
制御処理
4
メモリ
r0
1
r4
0
r1
2
r5
0
r2
3
r6
0
r3
0
r7
0
7
ALU
演算処理
15
プロセッサ内での命令の表現
MIPS(Microprocessor without
Interlocked Pipeline Stages)の場合

マシンコード
000000

10001
10010
01000
000000 100000
MIPSの命令形式

R形式: レジスタ用
op

rt
rd
shamt
funct
I形式: 即値およびデータ転送用
op

rs
rs
rt
constant or address
J形式: 無条件分岐命令
op
address
R形式命令
op






rs
rt
rd
shamt
funct
op:命令の種類を表現。オペコード
(opcode)と呼ばれる。
rs:第一ソースオペランドレジスタ。$s0、
$s1、…、$s7
rt:第二ソースオペランドレジスタ。$t0、$t1、
…$t7
rd:ディスティネーションレジスタ。
shamt:シフト量。
funct:あるopで表現される命令の機能の
区別をする表現。機能コードと呼ばれる。
I形式命令



op:命令の種類を表現。オペコード
(opcode)と呼ばれる。
rs:ソースオペランドレジスタ。$s0、$s1、…、
$s7
rt:オペランドレジスタ。$t0、$t1、…$t7
(ロード命令の場合はディスティネーショ
ン)
op
rs
rt
constant or address
命令の例
add
$d=$s+$t R 形式
000000ssssstttttddddd-----100000
 sub
$d=$s-$t R 形式
000000ssssstttttddddd-----100010
 addi
$d=$s+c (signed) I 形式
001000ssssstttttcccccccccccccccc
 lw
$t=memory[$s+a]
I 形式
100011ssssstttttaaaaaaaaaaaaaaaa
 sw
memory[$s+a]=$t I 形式
101011ssssstttttaaaaaaaaaaaaaaaa

命令の例
j PC=(((PC+4)&f0000000)|(a<<2)) J 形式
000010aaaaaaaaaaaaaaaaaaaaaaaaaa
 jal PC=(((PC+4)&f0000000)|(a<<2)),
$ra=PC+8 J 形式
000011aaaaaaaaaaaaaaaaaaaaaaaaaa

命令セットの種類

CISC (Complex Instruction Set
Computer): 複雑な命令セット。一般に命
令長は可変で、多くの形式がある。


IA-32(x86)
RISC (Reduced Instruction Set
Computer): 2-3の形式をもった固定長命
令セット。



SPARC(Scalable Processor ARChitecture)
MIPS
ARM(Advanced Risc Machine)
プロセッサ内での数値の表現

2進数で表現




1 -> 1
3 -> 11
11 -> 1011
一般に n bit の場合
符号なし(unsigned)
xn  xi  x3 x2 x1
n
 x 2
i 1
i
i 1
負の数をどう表現するのか?
負の数の表現

2の補数: n ビットの数 a があるとすると、
以下で定義されるのが2の補数。
2
n 1
a
2の補数
具体例
0011 -> 10000 – 00011 = 01101
最上位ビット
簡単な求め方
は無視
0011
1100
1101
全ビット反転
1を加える
2の補数を用いた加減算

4+3=7
0100
+ 0011
0111

4-3=1
0100
- 0011
0001
4+(-3)=1
0100
+ 1101
10001

3-4=-1
0011
- 0100
1111
3+(-4)=-1
0011
+ 1100
1111
加算器の実現例

4ビットの整数 A (A3A2A1A0) と B
(B3B2B1B0)の加算を考える。和は
S(S3S2S1S0) とする。
C3 S3
C2 S2
C1 S1
C0 S 0
全加算器
全加算器
全加算器
全加算器
A3 B3
A2 B2
A1 B1
A0 B0 0
全加算器:入力A,Bおよび桁上げ入力CからA+B+Cを計算し、加算結果および
桁上げ出力を出力する加算器
全加算器の動作
全加算器の真理値表
A
B
C
S
Cout
0
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
0
全加算器の構成例
A
B
C
S
Cout
加算器の構成例
A
B
C
S
A
B
C
Cout
A
B
C
S
Cout
S
Cout
A
B
C
S
Cout
加算器の実現例

4ビットの整数 A (A3A2A1A0) と B
(B3B2B1B0)の加算を考える。和は
S(S3S2S1S0) とする。
C3 S3
C2 S2
C1 S1
C0 S 0
全加算器
全加算器
全加算器
全加算器
A3 B3
A2 B2
A1 B1
A0 B0 0
全加算器:入力A,Bおよび桁上げ入力CからA+B+Cを計算し、加算結果および
桁上げ出力を出力する加算器
加算器の実現例

4ビットの整数 A (A3A2A1A0) と B
(B3B2B1B0)の加算を考える。和は
S(S3S2S1S0) とする。
C3 S3
全加算器
C2 S2
C1 S1
全加算器
全加算器
加算器と減算器が同じ構成で
C0 S 0
全加算器
実現可能
A3 B3
A2 B2
A1 B1
A0 B0 1
S=A-B
全加算器:入力A,Bおよび桁上げ入力CからA+B+Cを計算し、加算結果および
桁上げ出力を出力する加算器
その他の演算



乗算
除算
論理演算
参考書参照
実数の表現ー浮動小数点表現

小数の例



アボガドロ数 6.02214179 x 1023
プランク定数 6.62606896 x 10-34
2進小数


0.12=1.02 x 2-1
0.012=1.02 x 2-2
一般的な浮動小数点表現:(仮数) x (基数)
(指数)
IEEE754浮動小数点規格

IEEE754浮動小数点表現
(-1)S x (1+仮数) x 2
(指数-127)
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
S
指数

仮数
例:1.0 x 2-1
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
0
01111110
00000000000000000000000
浮動小数点数の演算は参考書参照
プロセッサでの命令実行手順

命令フェッチ(IF)


命令デコード(ID)


命令の実行
メモリアクセス(MA)


命令の解釈
命令実行(EX)


主記憶からの命令の取得
主記憶へのアクセス
ライトバック(WB)

レジスタへのアクセス
プロセッサの処理サイクル

シングルサイクル方式



1サイクルでIFからWBまでのすべてを実行
最も処理時間を要する命令の速度以上に高
速に動作させることはできない(全ての命令が
1サイクルで動作する必要があるから)
マルチサイクル方式

1つの命令を複数のサイクルで実行
IF
ID
EX MA WB
パイプライン処理

スループットを向上させる。
IF
ID
EX MA WB
IF
IF
ID
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
EX MA WB
実現するには様々な工夫が必要
IF
ID
EX MA WB
IF
ID
EX MA WB
パイプライン処理の障害

パイプライン・ハザード



構造ハザード:実行される命令の組み合わせ
にハードウェアが対応できないために発生す
るハザード
データ・ハザード:他の命令が終了するのを待
つ必要がある場合に発生するハザード
制御ハザード:ある命令の実行に関する判断
に実行中の他の命令の結果が必要な場合に
発生するハザード
Memory
構造ハザード
CPU
PC
IF
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
Memory
構造ハザード
CPU
PC
IF
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
Memory
構造ハザード
CPU
PC
IF
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
Memory
構造ハザード
CPU
PC
IF
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
MemoryMA
構造ハザード
競合
CPU
PC
IF
IF
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
Memory
構造ハザード

CPU
回避策1:ストールさせる
IF
PC
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
IF
ID
EX MA WB
Memory
構造ハザード

CPU
回避策1:ストールさせる
IF
PC
Instruction
register
Instruction
decoder
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
ALU Registers
EX MA WB
IF
ID
EX MA WB
MemoryMA
構造ハザード
競合
回避策2:命令メモリとデータ
メモリを分ける

IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
CPU
PC
IF
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
命令メモリ
構造ハザード
回避策2:命令メモリとデータ
メモリを分ける

IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
データメモリ
CPU
PC
Instruction
decoder
ALU Registers
EX MA WB
ハーバードアーキテクチャ
Instruction
register
Memory
データ・ハザード
CPU
PC
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード
CPU
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード
CPU
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
$t2=$s0-$t3
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード
CPU
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
$t2=$s0-$t3
-2=0-2
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード

ストールで待つ:3サイクル無駄
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
PC
Instruction
register
Instruction
decoder
EX MA WB
IF
CPU
ID
ALU Registers
EX MA WB
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード

CPU
回避策:フォワーディング
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード

CPU
回避策:フォワーディング
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
結果をALUに送る
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
Memory
データ・ハザード

CPU
回避策:フォワーディング
PC
$s0=$t0+$t1
add $s0,$t0,$t1
($s0=$t0+$t1)
sub $t2,$s0,$t3
($t2=$s0-$t3)
IF
ID
EX MA WB
IF
ID
結果をALUに送る
Instruction
register
Instruction
decoder
ALU Registers
EX MA WB
$t2=9-$t3
7=9-2
Registers
5
t0
0
s0
4
t1
0
s1
3
t2
0
s2
2
t3
0
s3
1
t4
0
s4
制御ハザード
分岐命令を含
む命令列
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
CPU
PC:10
Instruction
decoder
Instruction
register
ALU Registers
EX MA WB
制御ハザード
分岐命令を含
む命令列
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
CPU
PC:
Instruction
decoder
Instruction
register
ALU Registers
EX MA WB
制御ハザード
分岐命令を含
む命令列
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
CPU
PC:11
Instruction
decoder
Instruction
register
ALU Registers
EX MA WB
制御ハザード
分岐命令を含
む命令列
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:12
Instruction
decoder
Instruction
register
ALU Registers
後続命令のアドレス
は分岐条件に依存
成立:PC=40
不成立:PC=12
制御ハザード

制御ハザードの回避法その1:ストール
add $s0,$t0,$t1
IF
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
ストール
ストールのサイクル数はアーキテクチャ依存
制御ハザード

制御ハザードの回避法その1:ストール
add $s0,$t0,$t1
IF
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
ストール
IDにおいて分岐先アドレスを計算できるアーキテクチャの場合
制御ハザード

制御ハザードの回避法その2:分岐予測
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:10
Instruction
decoder
常に分岐が不成立と予測
Instruction
register
ALU Registers
制御ハザード

制御ハザードの回避法その2:分岐予測
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:11
Instruction
decoder
常に分岐が不成立と予測
Instruction
register
ALU Registers
制御ハザード

制御ハザードの回避法その2:分岐予測
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:12
Instruction
decoder
常に分岐が不成立と予測
Instruction
register
ALU Registers
制御ハザード

制御ハザードの回避法その2:分岐予測
add $s0,$t0,$t1
IF
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
or $s3,$s4,$t2
($s3=$s4|$t2)
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
ストール
CPU
PC:40
分岐が成立、つまり予測
実際には過去の履歴に基づく分
が外れた場合
Instruction Instruction
岐予測が行われる。分岐予測に
decoder
register
用 い る 分 岐 先 バ ッ フ ァ を Branch
ALU Registers
Target Buffer という。
制御ハザード

制御ハザードの回避法その3:遅延分岐
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
挿入された命令
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:11
Instruction
decoder
Instruction
register
ALU Registers
依存関係のない命令を挿入
制御ハザード

制御ハザードの回避法その3:遅延分岐
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
挿入された命令
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:12
Instruction
decoder
Instruction
register
ALU Registers
依存関係のない命令を挿入
制御ハザード

制御ハザードの回避法その3:遅延分岐
add $s0,$t0,$t1
($s0=$t0+$t1)
beq $s1,$s2, 40
(if($s1==$s2){goto 40})
挿入された命令
or $s3,$s4,$t2
($s3=$s4|$t2)
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
IF
ID
EX MA WB
CPU
PC:13or40
Instruction
decoder
Instruction
register
ALU Registers
依存関係のない命令を挿入
確定したアドレスの命令を実行
割込みと例外

MIPS



PowerPC



割込み:プロセッサ外部で発生する予期せぬ
事象
例外:プロセッサ内で発生する予期せぬ事象
割込み:異常な事象の発生
例外:制御の流れの変化
IA-32:すべて割込み
例外への対処法(MIPS)

例外の例



未定義命令の実行
算術オーバーフロー
対処法

OS への制御の移行


EPC(Exception Program Counter)に問題命令の
アドレスを退避
例外理由の通知


Causeレジスタに原因を記録
ベクタ割り込みの利用
おわり

similar documents