計算機アーキテクチャ

計算機アーキテクチャ
第7回 計算アーキテクチャ(ARU)
計算機のハードウェア実装
2014年 5月26日
電気情報工学科
田島 孝治
第7回 計算機アーキテクチャ
1
授業スケジュール(前期)
回
日付
タイトル
回
日付
タイトル
1
4/7
コンピュータ技術の歴史と
コンピュータアーキテクチャ
10
6/16
主記憶装置とレジスタ
11
6/23
命令実行の流れ
12
6/30
命令形式とアセンブリ言語
13
7/7
命令セット
14
7/14
サブルーチンの実現
15
7/28
PCSpimによるアセンブリ言語
プログラム
8/4?
期末試験(日程は仮)
9/29?
フォローアップ(日程は仮)
2
4/14
ノイマン型コンピュータ
3
4/21
コンピュータのハードウェア
4
4/28
数と文字の表現
5
5/12
固定小数点数と浮動小数点表現
6
5/19
計算アーキテクチャ(ARU)
7
5/26
計算装置のハードウェア実装
8
6/2
文字コード
9
6/11?
中間試験(日程は仮)
16
※5/5はこどもの日、7/21は海の日のため休講
※急なスケジュール変更があった場合,掲示およびメールで連絡します
第7回 計算機アーキテクチャ
2
今日の授業の目的
加減算の計算アーキテクチャを理解する
シフトと乗除算のアーキテクチャを理解する



加減算のアルゴリズムを復習し、計算をでき
るようにする
シフト演算のハードウェア実装について知る
シフトと加減算を組み合わせた乗除算の実装
について知る
第7回 計算機アーキテクチャ
3
4
全加算器の設計と実装

全加算器の真理値表
A
0
0
0
0

B 𝐶𝑖𝑛 𝐶𝑜𝑢𝑡
0 0
0
0 1
0
1 0
0
1 1
1
S
0
1
1
0
A
1
1
1
1
B 𝐶𝑖𝑛 𝐶𝑜𝑢𝑡
0 0
0
0 1
1
1 0
1
1 1
1
回路の論理式
S=A⊕B⊕C
Cout = AB + ACin + BCin
第7回 計算機アーキテクチャ
S
1
0
0
1
5
1ビット全加算器の回路図
A
B
𝐶𝑖𝑛
S
𝐶𝑜𝑢𝑡

𝐴
𝐵
FA
𝐶𝑖𝑛
𝑆
𝐶𝑜𝑢𝑡
以後簡単のためにボックス化して書く
第7回 計算機アーキテクチャ
Nビット全加算器を作るには

1ビット全加算器を複数つなげれば良い
𝐴0
𝐵0
𝐴
𝐵
0
𝐶𝑖𝑛
𝐴1
𝐵1
𝐴
𝐵
FA
𝑆0
𝐴2
𝐵2
𝐶𝑜𝑢𝑡
FA
𝐶𝑖𝑛

𝑆
𝑆
𝐶𝑜𝑢𝑡
𝐴
𝐵
FA
𝐶𝑖𝑛
𝑆1
𝐴3
𝐵3
𝐴
𝐵
𝑆2
𝐶𝑜𝑢𝑡
FA
𝐶𝑖𝑛
𝑆
𝐶𝑜𝑢𝑡
リプルキャリー型加算器と呼ぶ
第7回 計算機アーキテクチャ
𝑆
𝑆3
6
減算器を作るには

減算用の論理式を作る?


2の補数を使う



加算器と同じようにカルノー図を作れば作れる
加算器と同じ回路で実現できる
2の補数を計算する回路が必要
2の補数の計算方法



反転して、1を加える
反転:NOT回路を通す
1を加える:最下位ビットの𝐶𝑖𝑛 を常に1する
第7回 計算機アーキテクチャ
7
8
4ビット減算器
𝐴0
𝐵0
𝐴
𝐵
1
𝐶𝑖𝑛
𝐴1
𝐵1
𝐴
𝐵
FA
𝑆
𝑆0
𝐴2
𝐵2
𝐶𝑜𝑢𝑡
FA
𝐶𝑖𝑛
𝑆
𝐶𝑜𝑢𝑡
𝐴
𝐵
FA
𝐶𝑖𝑛
𝑆1
𝐴3
𝐵3
𝐴
𝐵
𝑆2
𝐶𝑜𝑢𝑡
FA
𝐶𝑖𝑛
第7回 計算機アーキテクチャ
𝑆
𝑆
𝐶𝑜𝑢𝑡
𝑆3
9
実際に演算してみよう

符号付きの場合の解釈
問題(10進数)
2進数
結果
10進数
(1) 3 + (-5)
(2) (-6) – (-3)
(3) (-3) + (-7)
(4) (-6) – 4
第7回 計算機アーキテクチャ
正しい?
10
計算スペース
𝐶
𝐴0
𝐵0
𝐴1
𝐵1
𝐴2
𝐵2
𝐴3
𝐵3
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐶𝑖𝑛
𝐶𝑖𝑛
𝑆0
𝐶
𝐶𝑖𝑛
𝐶𝑖𝑛
𝑆2
𝑆1
𝑆3
𝐴0
𝐵0
𝐴1
𝐵1
𝐴2
𝐵2
𝐴3
𝐵3
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐶𝑖𝑛
𝑆0
𝐶𝑖𝑛
𝑆1
𝐶𝑖𝑛
𝐶0
𝑆2
第7回 計算機アーキテクチャ
𝐶𝑖𝑛
𝑆3
𝐶0
11
計算スペース
𝐶
𝐴0
𝐵0
𝐴1
𝐵1
𝐴2
𝐵2
𝐴3
𝐵3
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐶𝑖𝑛
𝐶𝑖𝑛
𝑆0
𝐶
𝐶𝑖𝑛
𝐶𝑖𝑛
𝑆2
𝑆1
𝑆3
𝐴0
𝐵0
𝐴1
𝐵1
𝐴2
𝐵2
𝐴3
𝐵3
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐴
𝐵
FA 𝐶𝑜𝑢𝑡
𝑆
𝐶𝑖𝑛
𝑆0
𝐶𝑖𝑛
𝑆1
𝐶𝑖𝑛
𝐶0
𝑆2
第7回 計算機アーキテクチャ
𝐶𝑖𝑛
𝑆3
𝐶0
12
レジスタと順序回路

加減算の回路


値の保持はどうするのか

レジスタの実装
FFによるものが一般的
D-FFの真理値表
入力
出力
D
CK Qn+1 Qn+1
この講義で用いるFF
0
↑
0
1
D-FFのみで考える
1
↑
1
0
0/1
0
Qn
Qn
0/1
1
Qn
Qn
0
↓
Qn
Qn
1
↓
Qn
Qn


組み合わせ回路だけですべてが実現された

D
Q
CK
D-FF
Q
立ち上がり
立ち下り
第7回 計算機アーキテクチャ
D-FFの動作確認(タイムチャート)
D
CLK
Q
Q
第7回 計算機アーキテクチャ
13
D-FFによるシフト回路の実装

4ビットの右シフト回路を考える


パッディングはMSBの値とする
まずは状態遷移図を作る

クロックでシフト
0111
0110
0101
0011
0100
0010
0001
0000
1000
1100
1110
1111
1001
1101
1010
1011
14
15
真理値表の作成
現在の状態
次の状態
現在の状態
次の状態
S3
S2
S1
S0
S3
S2
S1’
S0’
S3
S2
S1
S0
S3
S2
S1’
S0’
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
0
0
1
0
1
1
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
0
0
1
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
第7回 計算機アーキテクチャ
16
カルノー図の作成1

S0’について
\S3S2
S1S0\
00
00
01
11
10
0
0
0
0
01
0
0
0
0
11
1
1
1
1
10
1
1
1
1
𝑆0′ = 𝑆1
第7回 計算機アーキテクチャ
17
カルノー図の作成2

S1’について
\S3S2
S1S0\
00
00
01
11
10
0
1
1
0
01
0
1
1
0
11
0
1
1
0
10
0
1
1
0
𝑆1′ = 𝑆2
第7回 計算機アーキテクチャ
18
カルノー図の作成3

S2’について
\S3S2
S1S0\
00
00
01
11
10
0
0
1
1
01
0
0
1
1
11
0
0
1
1
10
0
0
1
1
𝑆2′ = 𝑆3
第7回 計算機アーキテクチャ
19
カルノー図の作成4

S3’について
\S3S2
S1S0\
00
00
01
11
10
0
0
1
1
01
0
0
1
1
11
0
0
1
1
10
0
0
1
1
𝑆3′ = 𝑆3
第7回 計算機アーキテクチャ
20
D-FFによるシフト演算器
S3
S2
S1
S0
D
Q
D
Q
D
Q
D
Q
CK
Q
CK
Q
CK
Q
CK
Q
CLK


この演算器をシフトレジスタということもある
シフトを使うと何ができるのか?

乗除算ができます
第7回 計算機アーキテクチャ
乗除算のルール(直接乗算法)

乗数(除数)の2進数の意味

何ビットずらす(シフトする)か示している


掛け算は左シフト、割り算は右シフト
乗除算に掛け算九九は要らない
例) 116 × 28
116 = (0111 0100)2
28 = (0001 1100)2
01 1101 00
011 1010 0
0111 0100
1011 0000 = -80


21
ビットがずれて計算しにくい
左シフトは符号が維持できない
0ビットシフト
1ビットシフト
2ビットシフト
3ビットシフト
4ビットシフト
ブース法による乗算


2の補数で負の数も扱える乗算アルゴリズム
乗数の隣り合うビットを用いて演算方法を決定



1ビットづつ演算が決まる
部分積の計算式を利用
 nビットの数値、XとYの部分積を𝑃𝑖 とする
−1
 𝑃𝑖+1 = 2
(𝑃𝑖 + 𝑦𝑖 𝑋2𝑛 )
具体的には次の表に従い数値を操作する
𝑦𝑖
𝑦𝑖−1
0
0
そのまま右へ1ビット算術シフト
0
1
被乗数を加算した後、右へ1ビット算術シフト
1
0
被乗数を減算した後、右へ1ビット算術シフト
1
1
そのまま右へ1ビット算術シフト
操作
22
23
ブース法による乗算

4 = (0100)2
6 = (0110)2
例:4×6(4ビット)の場合
0000 0110 0
右シフト 0000 0011 0
-)0100
減算
1100 0011
右シフト 1110 0001 1
右シフト 1111 0000 1
加算 +)0100
0011 0000
右シフト 0001 1000 0
𝑃0
𝑃1
𝑃2
𝑃3
0001 1000
24
ブース法の実装と他のアルゴリズム

ハードウェア


アルゴリズムの強み



1の連続に対し加算処理が不要
1と0が交互に繰り返されると不向き
処理アルゴリズムには亜種が存在する


シフトと加算の組み合わせだけで実現可能
今回は多ビットの加算を行わない基本的な方法を説明
乗算のアルゴリズムにはより高速なものがある

ウォリスの木(Wallace tree)を用いる方法
第7回 計算機アーキテクチャ
除算の実現方法


引き戻し法(restoring division)、引き放し法
(nonrestoring division)が広く知られる
引き放し法




演算回数を少なくできる
負の符号も扱えるが、補正が必要になる
符号計算と数値計算を独立させたほうが良い
引き放し法の演算手順




被除数の符号と除数の符号から商の符号を決定
2の補数表現により負の数を正の数に変換
アルゴリズムにより商と剰余を計算
商の符号が負の場合、2の補数に変換
第7回 計算機アーキテクチャ
25
引き放し法のアルゴリズム

例)26÷5 (商は5、剰余は1)
0101
0001 1010
-)0101
0101
1100 1010
1001 010
+)0101
0101
1110 010
÷
第7回 計算機アーキテクチャ
0
0
26
引き放し法のアルゴリズム
0101
1110 010
1100 10
+)0101
0101
0001 10
0011 0
-)0101
1110 0
0101
1100
+)0101
剰余 0001
0
0
1
0
0 商
シフトできなくなったら演算修了
27
28
演習問題

次の計算を2進数で行え


全ての数値は8bitで表し、MSBは符号ビットとする
乗算はブース法により行い過程を示すこと
①
②
③
④
⑤
41 + 60
52 - 41
98 + 125
6 - 55
15 - 173
⑥
⑦
⑧
⑨
⑩
58 × 6
60 ÷ 4
-8 × 22
-56 ÷ 58
-16 × 98
第7回 計算機アーキテクチャ
浮動小数点の加減算

29
指数部と仮数部は別に考える


先に指数部をシフト(桁合わせ)してから演算する
数値A
S 指数A

数値B
S 指数B

仮数A
仮数B
計算のイメージ(指数A>指数B、共にS=0の時)
仮数A
仮数B
指数A - 指数B
S 指数A

仮数C
加減算の結果、正規化が必要な場合は調整する
(例:仮数部が桁上がりした場合、1ビットシフトし、指数を1増やす)
浮動小数点の乗除算

加減算と同様に指数部と仮数部は分ける




指数部は加減算
仮数部は乗除算
必要に応じて結果を正規化
計算の流れ
指数演算
仮数演算
正規化
30