計算機構成論II第4回-7回

計算機構成論II

第4回第5回第6回第7回

(全15回）

電気情報系学科

10/3 10/10 10/24 10/31 11/7 11/14 11/21 11/28 12/5 12/12 12/19 12/26 1/9 1/23 1/30

授業計画

休講 補講 12/4

テキストの5章

基本的演算とその拡張

命令語＝ 命令オペレータ部 ＋ オペランド

論理演算 加算、減算

データの流れ 制御の流れ 命令レジスタ プログラム カウンタ 命令デコーダ ＡＬＵ 算術論理 演算 ユニット レ ジ ス タ 群 メモリ部 入出力部 制御部 演算部

CPU

基本的演算とその拡張

論理演算

ブール代数則

恒等則: A+0=A,

恒等則： 𝐴 + 0 = 𝐴,

𝐴 ∙ 1 = 𝐴

0と1の代数則： 𝐴 + 1 = 𝐴,

𝐴 ∙ 0 = 0

逆元則： 𝐴 + 𝐴 = 1, 𝐴 ∙ 𝐴 = 0

交換則： 𝐴 + 𝐵 = 𝐵 + 𝐴, 𝐴 ∙ 𝐵 = 𝐵 ∙ 𝐴

結合則： 𝐴 + 𝐵 + 𝐶 = 𝐴 + 𝐵 + 𝐶, 𝐴 ∙ (𝐵 ∙ 𝐶) = 𝐴 ∙ 𝐵 ∙ 𝐶

論理演算

ブール代数則

ドモルガンの定理

𝐴 + 𝐵 = 𝐴 ∙ 𝐵 ,

𝐴 ∙ 𝐵 = 𝐴 + 𝐵

論理和 論理積 MIL記号 A B C ORゲート A B C ANDゲート

排他的 論理和 A B C XORゲート + 論理否定 NOTゲート

A C

𝐴 ⊕ 𝐵 = 𝐴 + 𝐵 ⋅ 𝐴 ∙ 𝐵 = 𝐴 ⋅ 𝐵 + 𝐴 ⋅ 𝐵

A B C 排他的 論理和 XORゲート + Exclusive OR

論理回路は汎用ＩＣとしても実現されている。

加算と減算

1ビット半加算器

A B C ANDゲート XORゲート + Exclusive OR A B C 桁上げはANDゲート、 和はXORゲートで表現できる。

加算と減算

1ビット全加算器

下の桁からの桁上げと上の桁への桁上げを持つ加算器を全加算器と呼ぶ 𝐴_𝑖 𝐵_𝑖 𝐶_𝑖−1 𝑆

HA

HA

𝑆𝑖 𝐶 𝐶_𝑖 = HA

加算と減算

1ビット全加算器

𝐴_𝑖 𝐵_𝑖 𝐶_𝑖−1 𝑆 HA HA 𝑆𝑖 𝐶 𝐶_𝑖 𝐶_𝑖 = 𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1 + 𝐴_𝑖 ⋅ 𝐵 ∙ 𝐶_{𝑖 𝑖−1} +𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1 + 𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1 = 𝐴_𝑖 ⋅ 𝐵_𝑖 + 𝐴_𝑖 ⋅ 𝐶_𝑖−1 + 𝐵_𝑖 ⋅ 𝐶_𝑖−1 = (𝐴_𝑖 ⋅ 𝐵 + 𝐴_{𝑖 𝑖} ⋅ 𝐵_𝑖) ⋅ 𝐶𝑖−1+ 𝐴𝑖 ⋅ 𝐵𝑖 + 𝐴𝑖 ⋅ 𝐵 ⋅ 𝐶𝑖 𝑖−1 = 𝐴_𝑖 ⋅ 𝐵_𝑖 + 𝐴_𝑖 ⋅ 𝐵 ⋅ 𝐶_{𝑖 𝑖−1}++ 𝐴𝑖 ⋅ 𝐵𝑖 + 𝐴𝑖 ⋅ 𝐵 ⋅ 𝐶𝑖 𝑖−1 𝑆_𝑖 = 𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1 + 𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1 +𝐴_𝑖 ⋅ 𝐵 ⋅ 𝐶_{𝑖 𝑖−1} + 𝐴_𝑖 ⋅ 𝐵_𝑖 ⋅ 𝐶_𝑖−1

14

加算と減算

1bit 全加算器(Full Adder)は結局1bit 半加算器を2個組みあわせて構成される。 𝐴_𝑖 𝐵_𝑖 𝐶_𝑖−1 𝑆_𝑖 𝐶_𝑖 ＦＡ C_i-1 A_i B_i S C_i

32bit 順次桁上げ加算器

C_-1 ＦＡ A₀ B₀ S_i C₀ ＦＡ A₁ B₁ S_i C₁ ＦＡ A₂₉ B₂₉ S₂₉ C₂₉ ＦＡ A₃₀ B₃₀ S₃₀ C₃₀ ＦＡ A₃₁ B₃₁ S₃₁ C₃₁

32bit 順次桁上げ加算器

C_-1 ＦＡ A₀ B₀ S_i C₀ ＦＡ A₁ B₁ S_i C₁ ＦＡ A₂₉ B₂₉ S₂₉ C₂₉ ＦＡ A₃₀ B₃₀ S₃₀ C₃₀ ＦＡ A₃₁ B₃₁ S₃₁ C₃₁ 減算への対応 + + + + + 補 数 用 制 御 信 号 線 + Exclusive OR 27-14=13 11011 11110 00001 10001 1 101101

順次桁上げ方式：キャリーの伝搬を待たないと上位の桁の結果が 確定しないので演算時間がかかる。

キャリー先読み方式などではこの問題を解決している。

C_-1 ＦＡ A₀ B₀ S_i C₀ ＦＡ A₁ B₁ S_i C₁ ＦＡ A₂₉ B₂₉ S₂₉ C₂₉ ＦＡ A₃₀ B₃₀ S₃₀ C₃₀ ＦＡ A₃₁ B₃₁ S₃₁ C₃₁

キャリー先読み論理回路 Carry Look Ahead

Carry Look ahead 方式

すべてのcarryはA,B各bitのand or の２段論理で実現できる。

C₁ ← (A₁ AND B₁) OR (A₀ AND B₀ AND A₁) OR (A₀ AND B₀ AND B₁) C₀ ← A₀ AND B₀

C₂ ← (A₂ AND B₂) OR (A₁ AND B₁ AND A₂) OR (A₁ AND B₁ AND B₂) OR (A₀ AND B₀ AND A₁ AND A₂) OR (A₀ AND B₀ AND A₁ AND B₂) OR (A₀ AND B₀ AND B₁ AND A₂) OR (A₀ AND B₀ AND B₁ AND B₂)

乗算

10011 x 10101=? 19x 21=399

10011

x 10101

10011

00000

10011

00000

10011

110001111

乗算は左シフトと加算の繰り返し

乗算

被乗数 _乗数 32bit 符号なし2進整数 32bit 符号なし2進整数 I レジスタ(64bit) J レジスタ(32bit) Pレジスタ(64bit) 積

乗算

Pレジ(64bit) 被乗数 積 I レジ(64bit) ALU（加算） 乗数 Jレジ(32bit) LSBが１なら加算実行を指令 右シフト 左シフト

除算

110011

101

1

-101

10

1

0

-000

101

1

-101

01

1

-000

1

0

被除数 除数 商 剰余 テキストに習って 手順を確認しよう。

除算

D1レジ(64bit) 除数 被除数（剰余） D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 非負ならQレジのLSBに１を設定 負ならQレジのLSBに０を設定 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 非負ならQレジのLSBに１を設定 負ならQレジのLSBに０を設定 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0 非負ならQレジのLSBに１を設定 負ならQレジのLSBに０を設定

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 マイナス 0

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 非負ならQレジのLSBに１を設定 負ならQレジのLSBに０を設定 00001

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 0 0 0 0 0 1 1 00001 0 0 1 0 0 1 0 1

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 非負ならQレジのLSBに１を設定 負ならQレジのLSBに０を設定 マイナス

除算

D1レジ(64bit) 被除数（剰余） 除数 D2 レジ(64bit) ALU（減算と加算） 商 Qレジ(32bit) 左シフト 右シフト 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 マイナス

除算

シフト演算

指定されたビット数だけレジスタの内容を左、あるいは右に移動（シフト）する演算 論理左シフト 論理右シフト 算術シフトの場合は MSB（符号を表す）は 最初の値が保存される

サブルーチン

全体が一つのプログラム M1 M2 M3 M4 S S M1 M2 M3 M4 S L L メインルーチン サブルーチン 同じプログラムを何度も書かなくてよい 開発済のプログラムの再利用（ライブラリ） 利点 開発効率の向上

サブルーチン

M1 M2 M3 M4 S L メインルーチン サブルーチン 呼び出し call 戻る return サブルーチン メインルーチン

スタック

呼び出し call 戻る return サブルーチン メインルーチン サブルーチンに飛ぶ際には サブルーチンからの戻り先のアドレスやレジスタの 値をメモリに退避しておく必要がある。 スタックというデータ格納法を用いる。

上に積んでいき、上からとってゆく

スタック

PUSH POP

スタック

データのPUSH データのPOP スタックトップ スタックボトム スタックポインタ スタックが伸びる スタックが縮む

メモリ

スタック領域 N番地 N-4番地 N-8番地 N-12番地 N-16番地

6. MIPSアセンブリ言語と機械語

アセンブリ言語構文 (1)ラベル 英文字、アンダーバー ＿ ピリオド . ドル $ 数字 ニーモニックをラベルには出来ない ラベルの後はコロン ： ラベルは分岐先の命令やサブルーチンの先頭につける。 (2)アセンブリ言語命令 機械語命令に対応した命令、 アセンブラにより機械語命令列に翻訳される合成命令（疑似命令） アセンブラに対する指令（アセンブラ指令） ピリオドで始まる。 命令オペレータ＋オペランド をアセンブリコードあるいは ニーモニックコードという。

6. MIPSアセンブリ言語と機械語

アセンブリ言語構文

(3)数値 10進数として扱う。 0xが付いたときは16進数

(4)レジスタ

32個の汎用レジスタ 0番から31番

$をつける。

(5)注釈 #で始まる

機械語命令の形式

MIPSの機械語命令は 32bit（1語）固定長

命令形式は3種類

R形式

I形式

J形式

R形式

機械語命令の形式

I形式

R形式

機械語命令の形式

オペコード 第1ソース レジスタ 第2ソース レジスタ デスティネーション レジスタ シフトビット数 （シフト命令の場合） シフト命令以外では 00000 算術、 論理演算の種別 レジスタ形式

機械語命令の形式

I形式

オペコード ソース レジスタ デスティネーション レジスタ 分岐変位、アドレス変位 即値（immediate）形式

機械語命令の形式

J形式

オペコード 飛び先アドレス

組込みシステムにおいてプログラムの速度と

メモリサイズが重要である場合。

例：

実時間制御システム、カーナビ、スマホなど

制約の厳しい実時間処理

リアルタイムOSなどを利用する必要

高級言語で記述できない箇所

割込み処理，クリティカルな処理

リアルタイムOSの記述

アセンブリ言語の必要性

.data

msg: .asciiz "Hello World" .text .globl main main: li $v0, 4 # v0レジスタに４をセット syscall(print_str) la $a0, msg # a0レジスタにメッセージのアドレスを格納 syscall # 文字列を出力 jr $ra # リターン

Hello World のソースプログラム

疑似命令 .data データ領域の開始 疑似命令 .asciiz "Strings": 文字列を配置 ラベル 疑似命令 globl L ラベル L を大局的に参照可能な記号と宣言する 疑似命令 .text テキスト領域の開始

MIPSの練習

アセンブラのソース

Text領域 （命令コード） データ領域 （命令コード） 実行結果 QtSpimの出力 .data

msg: .asciiz "Hello World" .text

.globl main

main: li $v0, 4 # syscall 4 (print_str) la $a0, msg # argument: string syscall # print the string jr $ra # retrun to caller

アセンブラ言語の形

mainの処理 #Text領域 #Data領域 .text .globl main main: jr $ra .data _start: jal main スタートアップルーチン、自動的に生成される テキスト領域（プログラム領域） データ領域 グローバル変数

疑似命令

セグメント、ラベル、データの宣言

.text: テキスト領域の開始

例 .text[addr]

.data: データ領域の開始

例

.globl L: ラベル L を大局的に参照可能な記号と宣言する。

例 .globl main

.word n: 1 語のデータ n を配置。

.space n: n バイトの領域を確保

足し算の例

add.asm

# Text Segment

.text

.globl

main

main:

addi $a0,$zero,5

# a0=5

addi $a1,$zero,10

# a1=10

add $v0,$a0,$a1

# v0=a0+a1

jr $ra

#mainの終了

#Data Segment

マクロ命令

レジスタの初期化

Li (Load Immediate) 命令

La (Load Address) 命令

la rs, addr 意味 rs <=addr (32bit)

move(Move) 命令

move rd, rs 意味 rd <=rs

実際の命令

li Rd, value

lui $at, Upper 16-bits of value ori Rd, $at, Lower 16-bits of value

la Rd, Label

lui $at, Upper 16-bits of Label ori Rd, $at, Lower 16-bits of Label

move Rd, Rs addu Rd, $0, Rs 実際の機械語では 16bitの即値しか扱えないので 2回に分ける 実際の機械語では 16bitの即値しか扱えないので 2回に分ける

MIPSのプログラミングについては下記ＵＲＬが 参考になる。 その他日本語サイトも

アセンブラプログラムの開始

スタートアップ lw $a0 0($sp) addiu $a1 $sp 4 addiu $a2 $a1 4 sll $v0 $a0 2

addu $a2 #a2 $vo jal main

アセンブラプログラムの開始

lw $a0 0($sp)

addiu $a1 $sp 4

addiu $a2 $a1 4

sll $v0 $a0 2

addu $a2 #a2 $vo

jal main

C 言語のmain関数の引数

main(argc, argv)

$4 arggc

$5 argv

$6 環境変数のポインタ

# シャープはコメントを表す． # このプログラムはa=b+cを実行する．

# a=$s0, b=$s1, c=$s2とする

# addi命令は第2オペランドに定数が書ける

# $zeroは常に値が0のレジスタ

# 最初に実行する関数はmainと決まっているのでmainを宣言する必要がある．

# .globl main

# main関数の宣言. main: addi $s1, $zero, 1

# b=$s1=1 addi $s2, $zero, 2

# c=$s2=2 add $s0, $s1, $s2

# a=$s0=b+c=3 jr $ra

# プログラムの終了

# a=$s0=3になっていることをSPIMシミュレータで確認すること

Cのプログラムとアセンブラの比較 例題１

.globl main # main関数の宣言 main: addi $s1, $zero, 1 # b=$s1=1 addi $s2, $zero, 2 # c=$s2=2 add $s0, $s1, $s2 # a=$s0=b+c=3 jr $ra # end

Cのプログラムとアセンブラの比較 例題2

main()

{int a, b, c;

b=-1;

c=2;

a=b+c;

}

.globl main # a=$s0, b=$s1, c=$s2

main: sub $s1, $zero, 1 # b=$s1=-1

add $s2, $zero, 2 # c=$s2=2

add $s0,$s1,$s2 # a=$s0=b+c=1

jr $ra #

.globl main # a=$s0, b=$s1, c=$s2 main: sub $s1, $zero, 1 # b=$s1=-1 add $s2, $zero, 2 # c=$s2=2 add $s0,$s1,$s2 # a=$s0=b+c=1 jr $ra #

アセンブラプログラムの開始

lw $a0 0($sp)

addiu $a1 $sp 4

addiu $a2 $a1 4

sll $v0 $a0 2

addu $a2 #a2 $vo

jal main

C 言語のmain関数の引数

main(argc, argv)

$4 arggc

$5 argv

$6 環境変数のポインタ

main(){ int a, b, c; b=1; c=2; a=b+c; printf("a=%d¥n) }

Cのプログラムとアセンブラの比較 例題4

# b=1, c=2 とし，a=b+cを計算する． # その答えを a = 3 とプリントする． # Data記述部でプリントする文字列を定義しておく． # Data記述部 .data str: .asciiz "a = " .text # mainプログラムをテキストセグメントに置く． .globl main # mainの宣言. a=$s0, b=$s1, c=$s2とする main: addi $s1, $zero, 1 # b=$s1=1

addi $s2, $zero, 2 # c=$s2=2 add $s0, $s1, $s2 # a=$s0=b+c # プリントするためのプログラム

addi $v0, $zero, 4 # syscallに文字のprintを指示

la $a0, str # $a0に文字列str:のアドレスを入れる syscall # 文字列"a = "をプリント

add $a0, $s0, $zero # $a0=$s0

addi $v0, $zero, 1 # syscallに整数のprintを指示 syscall # aの値をプリント

Cのプログラムとアセンブラの比較 例題4

.data

str: .asciiz "a = "

.text

.globl main main: addi $s1, $zero, 1 addi $s2, $zero, 2 add $s0, $s1, $s2 # プリントするためのプログラム addi $v0, $zero, 4 la $a0, str syscall add $a0, $s0, $zero addi $v0, $zero, 1 syscall jr $ra

Cのプログラムとアセンブラの比較 例題4

Data segment の先頭アドレスが0x10010000, 0x1001=4097

la $a0, str

lui $4,

4097

[str]

1 0 0 1 $4レジスタ すなわち a0レジスタ 10進の4097は16進で1001 0 0 0 0 上位16bitに 16進の1001を格納 下位16bitは ０を入れる

マクロ命令の使われ方

Cのプログラムとアセンブラの比較 例題5

int x[2]; main() { Int c; x[0]=0; x[1]=6; c=5; x[0]=x[1]+c} .data X: .word 0,6 # テキストセグメントを定義する． .text

.globl main # main関数の宣言. main: la $s1, X # $s1に配列x[0]のアドレス addi $s3, 5 # c=$s3=5 lw $s6, 4($s1) # $s6=x[1] $6にx[1]をロード # PCSpimでメニューのsimulator→settingsでdelayed loadにチェックを入れると， # lw命令は値をレジスタにロードするのに2サイクルかかるようになる． # チェックをはずすとlw命令を1サイクルで実行する． # ここではメモリが遅いためロードは2サイクルかかるとする． # lwの1サイクル後はレジスタにまだloadする値が入っていない．そこで意味のない # 命令を実行してもう1サイクル時間を遅らせる．

add $t1, $t1, $zero # load delayのため1サイクル遅らせる 意味のない命令

Cのプログラムとアセンブラの比較 例題5

.data

X: .word 0,6

.text .globl main main:

la $s1, X # $s1に配列x[0]のアドレス addi $s3, 5 # c=$s3=5 lw $s6, 4($s1) add $t1, $t1, $zero add $t2, $s3, $s6 sw $t2, 0($s1) jr $ra