第5回講義

計算機アーキテクチャー Computer Architecture
1
算術論理演算Ｉ
～符号付き数とALU～
(株)日立製作所 マイクロデバイス事業部
Micro Device Division, Hitachi Ltd.
川下
達也
Tatsuya Kawashimo
計算機アーキテクチャー Computer Architecture
2
計算機アーキテクチャー
１章：ｺﾝﾋﾟｭｰﾀの構成とﾃｸﾉﾛｼﾞ（５つの構成要素、半導体、ｺｽﾄ）
コンパイラ
２章：性能の評価
（CPU時間、CPI）
３章：命令
（MIPS命令ｾｯﾄ）
インターフェース
コンピュータ
制御
記憶
４章：算術論理演算
（符号付整数、ALU）
入力
５章：データパスと制御
６章：パイプライン
プ
（ｽﾄｰﾙ、ﾌｫﾜｰﾃﾞｨﾝｸ)
９章：並列プロセッサ
９章
並列プロセッサ
（SMP）
ﾃﾞｰﾀﾊﾟｽ
プロセッサ
７章：
記憶階層
（ｷｬｯｼｭ、
仮想記憶）
８章：
（ﾊﾞｽ)
（ﾊ
ｽ)
出力
計算機アーキテクチャー Computer Architecture
3
本日の授業の内容
コンパイラ
① 符号付き整数
インタフェース
コンピュータ
② 整数
整数の加算と減算
加算 減算
③ 論理演算
④ 算術論理演算ユニット
制 御
入 力
記 憶
データ
パ ス
プ セ サ
プロセッサ
出 力
計算機アーキテクチャー Computer Architecture
符号なし数 (Unsigned Numbers)
2進数 ： 10112
10進数 ： 1110
10112 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20
最上位ビット
= 1 x 8 + 0 x 4 + 1 x 2 +1 x 1
最下位ビット
= 1110
MIPSでの表現 (32bitで
(32bitで一つの数を表現)
の数を表現)
0000 0000 0000 0000 0000 0000 0000 1011
命令のアドレスは符号なし数
4
計算機アーキテクチャー Computer Architecture
符号なし数以外の数
もちろん、話はこんなに簡単ではなくて．．．
、話
簡単
① 符号なし数で表現できる数には上限下限がある
② 分数や実数の表現は？
③ 負の数は？
（MIPSには bi命令は無い addi命令で負の数を加
（MIPSにはsubi命令は無い;
ddi命令で負の数を加
算することで表現）
どうやって負の数を表現するか？
幾つかの選択肢がある
5
計算機アーキテクチャー Computer Architecture
6
符号付き数の表現方法例
符号付き絶対値:
000 = +0
001 = +1
010 = +22
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
１の補数
000 = +0
001 = +1
010 = +22
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
0の表現方法が何通り？（正の0、負の0）
ハードウエアで演算器を実現しやすいのはどれ？
1ビットを見て正負がわかる？
２の補数
000 = +0
001 = +1
010 = +22
011 = +3
100 = -4
101 = -3
110 = -2
111 = -1
計算機アーキテクチャー Computer Architecture
7
符号付き数 (Signed Numbers)
正負の整数（integer） 2の補数表現 ：x＋（－x）＝0
x31×（－231）＋{{ x30×230＋x29×229＋・・・＋x2×22＋x1×21＋x0×20 }
31
27
23
19
15
11
7
4　0
最大値 0111 1111 1111 1111 1111 1111 1111 1111
:
0
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0010
0001
0000
1111
1110
:
1000 0000 0000 0000 0000 0000 0000 0001
最小値 1000 0000 0000 0000 0000 0000 0000 0000
2
2
2
2
2
2
2
2
2 147 483 647 10
＝ 2,147,483,647
＝
＝
＝
＝
＝
2 10
1 10
0 10
-1 10
-2 10
＝ -2,147,483,647 10
＝ -2,147,483,648 10
符号ビット
オーバフロー：x＜最小値 or x＞最大値 （｜x｜が大きすぎて表現不可）
計算機アーキテクチャー Computer Architecture
8
負の数の求め方
負の数の求め方
2進数のすべての0を1 すべての1を0に置き換え（正負反転）
2進数のすべての0を1、すべての1を0に置き換え（正負反転）
1を足す
例題： 210を正負反転して、- 210を求めよ
210 = 0000 0000 0000 0000 0000 0000 0000 00102
正負反転して１を足す
1111 1111 1111 1111 1111 1111 1111 11012
+)
12
-2210= 1111 1111 1111 1111 1111 1111 1111 11102
計算機アーキテクチャー Computer Architecture
9
符号拡張 (Sign Extension)
• 符号拡張の例：
8ビットの符号付き整数を32ビットの符号付き整数に変換する
（メモリを節約する為、1つの整数を8ビットに割り当てた。
レジスタは32ビットなので、メモリからレジスタ のロ ド時に何
レジスタは32ビットなので、メモリからレジスタへのロード時に何
かの変換が必要）
• lbu (load unsigned byte) vs. lb (load byte)
16ビットの符号付き整数を32ビットの符号付き整数に変換
符号ビットを長くなったビット部分を0にすると……
31
23
19
15
11
7
4 0
1010 1010 1010 1011
2
43 691 10 ＝ 0000 0000 0000 0000 1010 1010 1010 1011
43,691
2
-21,845 10 ＝
×
27
計算機アーキテクチャー Computer Architecture
10
符号拡張 (Sign Extension)
• 符号拡張の例：
8ビットの符号付き整数を32ビットの符号付き整数に変換する
（メモリを節約する為、1つの整数を8ビットに割り当てた。
レジスタは32ビットなので、メモリからレジスタ のロ ド時に何
レジスタは32ビットなので、メモリからレジスタへのロード時に何
かの変換が必要）
• lbu (load unsigned byte) vs. lb (load byte)
16ビットの符号付き整数を32ビットの符号付き整数に変換
①元の値を元のビット位置にコピー
②符号拡張：符号ビットを長くなったビット部分にコピー
31
27
23
19
15
11
4
0
1010 1010 1010 1011
②
↓①
21 845 10 ＝ 1111 1111 1111 1111 1010 1010 1010 1011
-21,845
-21,845 10 ＝
○
7
2
2
計算機アーキテクチャー Computer Architecture
11
16進数
プログラムでの数値の表示
スペース（文字数）の節約
→ 2進数に容易に変換できる16進数で表示
0010 0110 1010 1111 2
↓ ↓ ↓ ↓
2
6
A
F 16
016 = 00002
616 = 01102 b16 = 10112
116 = 00012
716 = 01112 c16 = 11002
216 = 00102
816 = 10002 d16 = 11012
316 = 00112
916 = 10012 e16 = 11102
416 = 01002
a16 = 10102 f16 = 11112
516 = 01012
計算機アーキテクチャー Computer Architecture
整数の加算・減算
12
下位ビットから順に最上位ビットまでビットごとに加算
し、桁上げがあればすぐ上のビットに加える。
加算
0111 (7)
+ 0110 (6)
1101 (13)
減算 ： 引く数を正負反転して加算
0101 (5)
0101
- 0110 (6)
+ 1010
1111 (-1)
オーバーフロー
バ
(nビット
ビ
+ nビットの結果がn+1ビットになる)
ビ
結 が
ビ
な
0111 (7)
+ 0001 (1)
1000 (-8?)
計算機アーキテクチャー Computer Architecture
オーバーフロー
z正の数と負の数を加える場合は、発生しない
z同じ符号の数の減算では、発生しない
z符号ビットが影響受ける場合にオーバーフロー
正の数どうしを足して、負の数になった場合
負の数どうしを足して、正の数になった場合
正の数から負の数を引いて、結果が負になった場合
負の数から正の数を引いて、結果が正になった場合
zオーバーフローが起きると例外 (Exception)が発生
特別な処 をす
特別な処理をするサブルーチン（手続き）の先頭にJump
（手続 ） 先頭
p
13
計算機アーキテクチャー Computer Architecture
論理シフト (Logical Shift)
論理シフト ： 語中の全てのbitを左又は右に指定bit数ずらし、空いた部分に
0を詰める。
shamt (shift amount)にシフト量を指定
左シフト (sll), 右シフト (srl)
算術右シフト (sra)
8ビット左へシフト
8ビ
ト左 シフト
0000 0000 0000 0000 0000 0000 0000 00102
0000 0000 0000 0000 0000 0010 0000 00002
31
R形式
25
op
20
rs
15
rt
rd
10
5
0
shamt funct
(1) sll rd, rt, Sa(shamt)
0
0
rt
rd
Sa
0
(2) srl rd, rt, Sa(shamt)
0
0
rt
rd
Sa
2
論理演算命令
14
計算機アーキテクチャー Computer Architecture
論理積 (and)、論理和 (or)
15
AND（論理積）： 2つの語中の全てのbitについて、
ともに1である場合は1と、そうでない場合は0とする。
OR （論理和）： 2つの語中の全てのbitについて、
いずれかが1である場合は1と、そうでない場合は0とする。
31
25
20
15
10
5
0
instruction
op
rs
rt
rd
shamt funct
意 味
意　味
6bit
5bit
5bit
5bit
5bit
6bit ※16ビットを0拡張する
フィールド長
（63） （31） （31） （31） （31） （63）
（最大値）
and
0 $入力1 $入力2 $出力
0
36 $出力＝AND（$入力1,$
1 $入力2）
or
0
$入力1 $入力2 $出力
andi
12
$入力 $出力 ※定数 16bit（65,535） $出力＝AND（$入力,定数）
ori
13
$入力 $出力 ※定数 16bit（65,535） $出力＝OR（$入力,定数）
0
37
$出力＝OR（$入力1,$入力2）
計算機アーキテクチャー Computer Architecture
16
ALUの基本要素
算術論理演算ユニットALU（Arithmetic Logic Unit）
算術演算（加算 減算な ）や論理演算（
算術演算（加算･減算など）や論理演算（AND･ORなど）を行う
な ）を行う
ANDゲート
ORゲート
インバータ
マルチプレクサ
b）
（ c=a･b
b）
（ c=a+b
（ c=a ）
d 0 → c=a ）
（ d=0
（ d=1 → c=b ）
d
a
b
c
a
0
0
1
1
b c=a･b
0
0
1
0
0
0
1
1
a
b
c
c a
a
0
0
1
1
b c=a+b
0
0
1
1
0
1
1
1
a c=a
0 1
1 0
a
b
0
1
d c
0 a
1 b
c
計算機アーキテクチャー Computer Architecture
and及びor用の1ビット演算ユニット
O
Operation
ti
a
0
Result
b
1
マルチプレクサがandとorの結果のどちらかを選
マルチプレクサが
dと の結果のどちらかを選
択してResultへ出力
17
計算機アーキテクチャー Computer Architecture
18
1ビット加算器
CarryIn
a
Sum
b
cout = a b + a cin + b cin
sum = a xor b xor cin
0111 (7)
+ 0110 (6)
1101 (13)
C
CarryOut
O
Cout = aとbが両方1の時、 または aとCinが両方1の時、
a,b,cが全て1の時、
または bとCinが両方1の時
sum = aは1,bとCinが0の時、
Cinは1,aとbが0の時、
は1 とbが0の時
または
または
bは1,aとCinが0の時、
a,b,C
b Cinが全て1の時
計算機アーキテクチャー Computer Architecture
19
1ビットALU
ビット反転
a
減算：ビット反転で可能
2の補数表現だから
－b＝b＋1
b＝b＋1
↓
キャリーインを1にすれば
a＋b＋1＝a＋（－b）
＋b＋1 ＋（ b）
b
キャリーイン
a
AND
OR
b
b
b
a・b
a+b
操作
1bit
論 演算
論理演算
ユニット
0
1
a
0
b
1
b
b
2の補数表現に基づいて加算器を構成
補数表現 基づ
加算器を構成
すると、ハードウエアが単純化される
＋
2
1bit
加算器
キ リ
キャリーアウト
ウト
結果
計算機アーキテクチャー Computer Architecture
20
順次桁上げ加算器 (ripple carry adder)
CarryIn
a0
b0
ripple:
Operation
CarryIn
ALU0
Result0
【変化】《動》ripples |
rippling | rippled,
CarryOut
a1
b1
CarryIn
ALU1
Result1
CarryOut
a2
b2
【@】《名》リップル,リプル
CarryIn
Ca
y
ALU2
Result2
さざ波,波状,波紋,《自動》
さざ波
波状 波紋 《自動》
～に波紋を起こす,さざ波
が立つ,波紋ができる,連続
的に発射する
CarryOut
a31
b31
CarryIn
ALU31
Result31
(0 )
(0 )
(1 )
(1 )
(0 )
(C a r rie s )
0
0
0
1
1
1
0
0
0
1
1
0
(0) 0
(0) 0
(0) 1
(1) 1
(1) 0
(0) 1
計算機アーキテクチャー Computer Architecture
桁上げ先見 (carry-lookahead)
21
ALU i+1 は、ALU i のCoutが出力されるまで計算開始できない！
c0
g0
桁上げ先見加算器：キャリーインc i +1 を先見
p0
c0
c1
キャリーが発生 (generate)する条件
gi = a i bi
キャリーが伝播(propagate)する条件
pi = a i + b i
p0
g0
c0
g0
g1
p0
p1
g1
c2
p1
g2
p2
g3
p3
c4
水が得られるのは、①直近の生成バ
ルブ(g
ブ i)が開く場合 ② 伝播バルブ
ブ
(pi)が開いて上位に水のある場合
c1
c2
c3
c4
=
=
=
=
g0
g1
g2
g3
+
+
+
+
p0c0
p1c1
p2c2
p3c3
c2 = g1 + p1g0 + p1p0c0
c3 = g2 + p2g1 + p2p1g0
+ p2p1p0c0
c4 = g3 + p3g2 + p3p2g1
+ p3p2p1g0 + p3p2p1p0c0
計算機アーキテクチャー Computer Architecture
桁上げ先見加算器
C a rry In
a0
b0
a1
b1
a2
b2
a3
b3
C a rry In
R e s ult0--3
ALU0
P0
G0
pi
gi
C arry-loo k ah ea d u n it
C1
a4
b4
a5
b5
a6
b6
a7
b7
a8
b8
a9
b9
a1 0
b1 0
a1 1
b1 1
a1 2
b1 2
a1 3
b1 3
a1 4
b1 4
a1 5
b1 5
32ビットの加算器にこれをそのまま
適用するとハードウエアが大きくな
り過ぎる
↓
桁上げ先見4ビット加算器を4つ使う
これらを、桁上げ先見方式で接続
ci + 1
C a rry In
R e s ult4--7
ALU1
P1
G1
pi + 1
gi + 1
C2
ci + 2
C a rry In
R e s ult8--1 1
ALU2
P2
G2
pi + 2
gi + 2
C3
ci + 3
C a rry In
R e s ult12 --1 5
ALU3
P3
G3
pi + 3
gi + 3
C4
C a rryO u t
ci + 4
C1 = G0 + P0C0
C2 = G1 + P1G0 + P1P0C0
C3 = G2 + P2G1 + P2P1G0
+ P2P1P0C0
C4 = G3 + P3G2 + P3P2G1 + P3P2P1G0
+ P3P2P1P0C0
22
計算機アーキテクチャー Computer Architecture
23
32ビットALU
ビット･ネゲート
=
減算結果を利用してALUに組込める命令
ビット反転
a0
b0
＋
キャリーイン
×
キャリーイン
ALU0
操作
（ ）より小 ： set on less than
（1）より小
a＜b？ ⇒ a－b＜0？
→ 減算結果の符号ビットを第0ビットにセット
（2）ゼロ判定 ： branch on （not） equal
a＝b？ ⇒ a－b＝0？
→ ゼロ判定＝NOT（OR（減算結果の全ビット））
結果0
より小
キャリーアウト
a11
b1
0
キャリ イン
キャリーイン
ALU1
結果1
より小
キャリーアウト
ゼロ判定
ALUの制御の単純化 ： ビット･ネゲート
a31
b31
0
キャリーイン
ALU31
より小
オーバフロー
バ
結果31
セット
「第0ビットALUのキャリーイン」と
「各ビットALUのビット反転」を一本化した制御線
加算・論理演算 ： 常に両方が0
減算・より小・ゼロ判定 ： 常に両方が1
オーバフロー