授業計画

コンピュータアーキテクチャ

第 3 週 演算アーキテクチャ（演算アルゴリズムと回路）

2013年10月9日 金岡 晃

授業計画

第 1 週 (9/25)

授業概要・２進数表現・論理回 路の復習

第 2 週 (10/2)

２進演算（数の表現）

第 3 週 (10/9)

演算アーキテクチャ（演算アル ゴリズムと回路）

第 4 週 (10/16)

ノイマン型コンピュータ・命令 とは・命令の使い方

第 5 週 (10/23)

休講 第 6 週

(10/30)

命令セットアーキテクチャ（命 令の表現・命令の実行の仕組）

第 7 週 (11/6)

ハーバードアーキテクチャ・

RISC と CISC ・制御アーキテク

第 8 週 (11/13)

中間試験 第 9 週

(11/20)

休講 第 10 週

(11/27)

メモリの仕組 第 11 週

(12/4)

キャッシュメモリと仮想メ モリ

第 12 週 (12/11)

割込みアーキテクチャ 第 13 週

(12/18)

パイプライン 第 14 週

(1/8)

入出力アーキテクチャ・ま

とめ

【復習】第 2 週

２進演算（数の表現）

コンピュータアーキテクチャ

10 進数の 2 進表現： 2 進化 10 進数（ BCD ）

10進数の1桁（0-9）を2進（0と1）で表現するためには 少なくとも4ビットが必要

2進数4ビットでは

16通りの表現が可能（0000-1111）

10通りのみを使用して10進数と対応づけた単純な手法：

2進化10進数（BCD：Binary Coded Decimal）

10 進数 BCD 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001

複数桁の10進数は？

各桁の数字を

BCD で表現

10 進数の 2 進表現： 3 増しコード

10 進数

0 0011

1 0100

2 0101

3 0110

4 0111

5 1000

6 1001

7 1010

8 1011

9 1100

BCDに3を加算したコード

• 0000のデータ割り当てが無い

• 各ビットを反転する（NOTをとる）と、10進数の9の 補数となる（自己補数化性）

0011（0） → 1100（9）

10進数の9の補数

足すと9になる数のペア 減算に都合

が良い

• 四捨五入の判断がMSBを見るだけで可能

「データがない」ことを示すのに

0000を利用可能

10 進数の 2 進表現：グレイコード

10 進数 グレイコード

0 0000

1 0001

2 0011

3 0010

4 0110

5 0111

6 0101

7 0100

8 1100

9 1101

10進数のデータが1変わるときに、対応するコードのビッ トの変更が1か所だけで済む表現

たとえばBCDで(7)10から(8)10に増えるとき, 0111が1000になるので

計4ビットのデータを変換しなければならないが

グレイコードでは1ビットのデータ変換だけで良い

負の数の表現：符号と絶対値表現

10 進数 2 進表現

-7 1111

-6 1110

-5 1101

-4 1100

-3 1011

-2 1010

-1 1001

-0 1000

10 進数 2 進表現

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

MSBを符号ビットとし、残りのビット

で数値を絶対値にしたデータを表す

負の数の表現： 2 の補数表現

10 進数 2 進表現

-8 1000

-7 1001

-6 1010

-5 1011

-4 1100

-3 1101

-2 1110

-1 1111

10 進数 2 進表現

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

負の数はその数の絶対値の2の補数で

表す

実数の表現：浮動小数点数

ビット番号：

符号ビット

（正：0、負：1） 指数部 小数点 仮数部

0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

31 30 29 28 27 2625 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

実数を 2 進数で表現する (5.625)

(101.101)

整数部を0以外の１桁（つまり2進数の場合 1）に調整（正規化、normalize）する。

1.01101 × 2

仮数部 指数部

32 ビット

（単精度）の場合

• MSB：仮数の符号

• 8ビット：指数部

• 23ビット：仮数部

バイアス表現：

-127乗から128乗まで表すため に、127を加算して2進表現する けち表現（Economized Representation）

2進数を正規化すると必ず1になるため、1を省略して1ビット省略する方法

演習：浮動小数点数

浮動総数点数で表す 32 ビット：

構成はスライド 23 と同じ バイアスは 127 けち表現

128

0.00001625

前回の演習

0.00001625 板書で下記のように書きましたが、これは間違いです。

1.625 × 10 ⁵

※最初に問題を作るときに10のべき乗で問題を作ってしまった。

1.625 × 10 ^{5 2進表現するには} ここは2のべき乗で表されなけ ればならない

問題が良く なかった

0.052734375 まず2進数で表現： 0.000011011

指数部と仮数部に分ける： 1.1011 × 2

あとは一緒

第 3 週 演算アーキテクチャ

（演算アルゴリズムと回路）

コンピュータアーキテクチャ

本日の到達目標と概要

• 到達目標

– 算術演算の基本アルゴリズムを習得する

• 概要

– 加減算アルゴリズム

– 乗算アルゴリズム：ブース法（ Booth Algorithm ）

– 除算アルゴリズム：引き戻し法（ Restoring Division ）と引き放し

法（ Nonrestoring Division ）

加減算アルゴリズム

• 加算

– 全加算器をビット数分並べる

• 減算

– 2 の補数表現にして加算にす る

• これらを合わせると加減算を両 方演算可能な回路を構成できる

𝑦 𝑥

𝑐 𝑠

𝑋

FA

𝑋 𝑌 𝐶₁

𝐶₀ 𝑆

FA

𝑋 𝑌 𝐶₁

𝐶₀ 𝑆

FA

𝑋 𝑌 𝐶₁

𝐶₀

𝑆 𝑆₃

𝐶_O

𝑆₂

𝑆₁ 𝑋₀

𝑌₁ 𝑋₁ 𝑌₂ 𝑋₂ 𝑌₃ 𝑋₃

全加算器（ FA ）

加減算器の例

𝐶_𝑆𝐺𝑁： 制御信号

𝑋 + 𝑌 𝑖𝑓 𝐶_𝑆𝐺𝑁 = 0 𝑋 − 𝑌 𝑖𝑓 𝐶_𝑆𝐺𝑁 = 1

乗算アルゴリズム

ブース法

（ Booth Altorithm ） 前提

𝑃 = 𝑋 ⋅ 𝑌 を求める。

このとき 𝑋 を被乗数、 𝑌 を乗数と呼ぶ。

また 𝑋 を2進数表現した際の各ビットを 𝑥

で表す。

𝑖 (0,1, … ) は下位から数えて何ビット目かを示す。

• 負の乗算にも対応した広く利用されている方式。

• 負の数は2の補数で表現される

• 乗数を2進展開し、各ビットについてシフトと加算を行っていく

• 各ビットとその前のビットの値の組み合わせによりシフトと加算の 動作が異なる

• 𝑖 ビット目の動作では 𝑦

と 𝑦

の組み合わせを見る

• 組合せは以下の3種類：00または11、10、01

• 動作は加算の位置が変化する方法と加算の位置を変化させない方法

で異なる

ブース法（ Booth Algorithm ）

加算位置が変化する方法 𝑃 = 0, 𝑦

= 0 とする

各ビット 𝑖 (0,1, … , 𝑛 − 1) について以下の動作を行う 𝑦

と 𝑦

が等しい場合：なにも行わない 𝑦

= 0, 𝑦

= 1 の場合： 𝑋 × 2

を 𝑃 に加算 𝑦

= 1, 𝑦

= 0 の場合： 𝑋 × 2

を 𝑃 から減算 加算位置が変化しない方法

𝑃 = 0, 𝑦

= 0 とする

各ビット 𝑖 (0,1, … , 𝑛 − 1) について以下の動作を行う

𝑦

と 𝑦

が等しい場合：なにも行わなず、 𝑃 を右にシフト

ブース法：演算例

𝑃 = 3 ⋅ 5

加算位置が変化する方法 加算位置が変化しない方法

除算アルゴリズム

引き戻し法 (Restoring Division)

引き放し法 前提

𝑋 と 𝑌 の商 𝑄 と剰余 𝑅 求める。

このとき 𝑋 を被除数、 𝑌 を除数と呼ぶ。

また 𝑋 を2進数表現した際の各ビットを 𝑥

で表す。

𝑖 (0,1, … ) は下位から数えて何ビット目かを示す。

𝑋 は 2𝑛 ビット、 𝑌 は 𝑛 ビットとする。

また 𝑋 の上位 𝑛 ビットを 𝑋1 、下位 𝑛 ビットを 𝑋2 とする

𝑋 の上位 𝑛 ビットから 𝑌 を引いていく。筆算では 𝑋 の上位 𝑛 ビットと 𝑌 の大小を

比較し、大きければその桁の商を1、小さければ0としているが、引き戻し

法ではまず減算を行い、その結果の正負を判定する。負である場合、同じ

ものを加算することで元に戻す。

除算アルゴリズム：引き戻し法

START

𝑌 ≠ 0

𝑋1 ← 𝑋1 − 𝑌

𝑋1 < 0

𝑋1 ← 𝑋1 + 𝑌

を左へ

1ビットシフト

𝑋1 ← 𝑋1 − 𝑌

𝑋1 ≥ 0 𝐶 ← 1

𝑛 ← 𝑛 − 1

𝐶 ← 0 𝑋1 ← 𝑋1 + 𝑌

𝑛 ≠ 0

END

オーバフロー

No

No Yes

Yes

𝑋1 𝑋2 𝐶

Yes

Yes

No

No

フローチャート

除算アルゴリズム：引き戻し法

START

𝑌 ≠ 0

𝑋1 ← 𝑋1 − 𝑌

𝑋1 < 0

𝑋1 ← 𝑋1 + 𝑌

を左へ

1ビットシフト

𝑋1 ← 𝑋1 − 𝑌

𝑋1 ≥ 0 𝐶 ← 1

𝑛 ← 𝑛 − 1

𝐶 ← 0 𝑋1 ← 𝑋1 + 𝑌

𝑛 ≠ 0 オーバフロー

No

No Yes

Yes

𝑋1 𝑋2 𝐶

Yes

Yes

No

一度減算を行う 減算の結果が

正か負か 判断 負であれば

商のその桁は 0 とし、

減算を元に戻す

（引き戻し）

引き戻し法：演算例

𝑋 = 22, 𝑌 = 6 𝑋 = 35, 𝑌 = 7

引き放し法のフローチャート

START

𝑌 ≠ 0

𝑋1 ← 𝑋1 − 𝑌

𝑋1 < 0

𝑋1 ← 𝑋1 + 𝑌 𝑛 ← 𝑛 − 1

𝑋1 ≥ 0

𝑛 ← 𝑛 − 1 𝐶 ← 0

を左へ

1ビットシフト 𝑋1 ← 𝑋1 + 𝑌

𝑛 ≠ 0 オーバ

フロー

No

No Yes

Yes

Yes

Yes

No

No を左へ1ビットシフト

𝑋1 𝑋2 𝐶

𝑋1 𝑋2 𝐶 𝐶 ← 1

を左へ

1ビットシフト 𝑋1 ← 𝑋1 − 𝑌

𝑋1 𝑋2 𝐶

𝑋1 ≥ 0 𝐶 ← 0 𝑋1 ← 𝑋1 + 𝑌

No Yes

𝐶 ← 1

引き放し法のフローチャート

START

𝑌 ≠ 0

𝑋1 ← 𝑋1 − 𝑌

𝑋1 < 0

𝑋1 ← 𝑋1 + 𝑌 𝑛 ← 𝑛 − 1

𝑋1 ≥ 0

𝑛 ← 𝑛 − 1 𝐶 ← 0

を左へ

1ビットシフト 𝑋1 ← 𝑋1 + 𝑌

𝑛 ≠ 0

END

オーバ フロー

No

No Yes

Yes

Yes

Yes

No

No を左へ1ビットシフト

𝑋1 𝑋2 𝐶

𝑋1 𝑋2 𝐶 𝐶 ← 1

を左へ

1ビットシフト 𝑋1 ← 𝑋1 − 𝑌

𝑋1 𝑋2 𝐶

𝑋1 ≥ 0 𝐶 ← 0 𝑋1 ← 𝑋1 + 𝑌

No Yes

𝐶 ← 1

フローチャート 引き戻し法と

比較すると ループ部分の

演算回数が 少なくなっている

（高速化）

𝐶 に入れられた値を上位より

記載すると商が求まり、最終

的な 𝑋1 が剰余を示している。

引き戻し法：演算例

𝑋 = 22, 𝑌 = 6 𝑋 = 35, 𝑌 = 7

本日の到達目標と概要

• 到達目標

– 算術演算の基本アルゴリズムを習得する

• 概要

– 加減算アルゴリズム

– 乗算アルゴリズム：ブース法（ Booth Algorithm ）

– 除算アルゴリズム：引き戻し法（ Restoring Division ）と引き放し 法（ Nonrestoring Division ）

24 ^2013/10/09