Computer Architecture

CS专业课学习笔记

計算機の基本構造

• 入力装置：外部からコンピュータにデータを読み込ませる装置
• 記憶装置：データやプログラムを記憶しておく装置
• 演算装置：四則演算や論理演算を行う装置
• 制御装置：記憶装置から取り出した命令を読解し実行を支持する装置
• 出力装置：処理されたデータをコンピュータの外部に出す装置

中央処理装置(Central Processing Unit, CPU): 演算装置 + 制御装置

CPUの構成

演算装置

• 算術論理演算装置(Arithmetic Logic Unit, ALU): 算術演算や論理演算を行う演算回路
• レジスタ(Register): 演算などに必要なデータを一時格納する
  • 汎用レジスタ(General Register, GR): 高速に動作するCPU内の記憶装置、特定の目的を持たず、様々な役割を果たすレジスタ
  • フラグレジスタ(Flag Register, FR): ALUの処理結果に基づいた動作を行うレジスタ

フラグレジスタの例:

• オーバフローフラグ(OF): 演算結果がある範囲を超えると1、範囲内だと0
• サインフラグ(SF): 演算結果が負の時1、それ以外の時0
• ゼロフラグ(ZF): 演算結果がゼロの時1、それ以外の時0

制御装置

• プログラムカウンタ(Program Counter, PC): 命令が格納されているアドレスを示す
• 命令レジスタ(Instruction Register, IR): 読み出された命令を一時格納する
• デコーダ(Decoder, DEC): 命令を解読し、制御信号やアドレスを発生する

命令実行の流れ: メモリに格納されているめいれいを1つ取り出して解読したあと実行する、という動作を繰り返して処理を進める

基本動作

プログラム内蔵方式

プログラム内蔵方式はプログラムをメモリに格納するのでプログラムの入力 / 変更が容易

• 単一メモリ方式
  • プログラムとデータは同じメモリに数値として格納
  • メモリにはアドレスが割り振られている
• 逐次処理方式
  • 命令は原則実行順にメモリに格納
  • 順序取り出しながら処理

プログラム内蔵方式のボトルネック(bottleneck): 同じメモリにプログラムとデータが共存しているため、メモリへのアクセス速度が遅い場合、全体のパフォーマンスに影響が出る

まとめ

• ライプニッツやパスカルによって作られた機械要素によって計算を行う計算機を機械式計算機という
• 1946年にモークリーとエーカットによって弾道計算用として実用化された電子計算機をENIACという．プログラムは内蔵だが書き換えはできなかった
• System/360はアーキテクチャを抽象化した製品群を形成した初の商用コンピュータである
• 1981年にIBMが発表したIBM Personal ComputerはIBM PC互換機の元であり，回答オープンアーキテクチャを採用したことが特徴である．ソフト・ハード両面での膨大な市場形成に寄与した
• 現在の計算機はすべてプログラム内蔵方式(またはノイマン型)の計算機である
• ALUはCPUの構成要素の一つで，算術演算や論理演算を行う装置
• 汎用レジスタはCPUの構成要素の一つで，特定の目的を持たず様々な役割を果たすレジスタ
• プログラムカウンタはCPUの構成要素の一つで，次に実行するプログラムが格納されているメモリのアドレスを記憶しているレジスタ
• デコーダはCPUの構成要素の一つで，命令を複合して実行に必要な制御信号を出力する装置

計算機の性能評価

計算機性能の定義

速度を基準に考える

• 応答時間(response time): 1つのプログラムを実行し終える時間
  • 実行を開始してから終了までの時間「実行時間(execution time)」ともいう
• スループット(throughput): 全てのプログラムを実行し終える時間
  • 単位時間当たりに終了した作業の量「バンド幅(bandwidth)」ともいう

相対性能

計算機Aは計算機Bよりもn倍速い

$$\begin{aligned} \frac{\text{性能}_A}{\text{性能}_B} = \frac{\text{実行時間}_B}{\text{実行時間}_A} = n \end{aligned}$$

実行時間による性能測定

システム性能

• ディスク/メモリアクセス、入出力動作、OSのオーバーヘッド全てを含む応答時間(経過時間)
• CPU(実行)時間 (CPU (execution)time)
  • プロセッサが実際に処理に費やした時間
  • 他のプログラムを実行するための待ち時間は含まない

CPU時間はさらに2種類に分けられる

• ユーザーCPU時間(user CPU time) $\Rightarrow$ CPU性能
  • プログラム中で費やされた時間
• システムCPU時間(system CPU time)
  • プログラムに代わってOSが処理に費やした時間

CPU性能

クロック・サイクル時間

• 1クロック周期の占める時間
• ハードウェア内で事象を起こすタイミングの最小単位

$$\begin{aligned} CPU\text{実行時間} &= CPU\text{クロック・サイクル数} \times \text{クロック・サイクル時間} \\ \\ &= \frac{\text{クロック・サイクル数}}{\text{クロック周波数}} \end{aligned}$$

CPU性能を向上させるためには

• プログラム実行に必要なクロック・サイクル数を減らす
• プロセッサのクロック周波数を上げる

CPI一定程度上更加准确的反映了计算机的运算速度。

命令に基づく性能

CPI(clock cycle per instruction): 各命令を実行するのに必要なクロック・サイクル数の平均

$$CPU \text{クロック・サイクル数} = \text{プログラムの実行命令数} \times CPI$$

$$CPU \text{実行時間} = \text{命令数} \times CPI \times \text{クロック・サイクル時間}$$

古典的なCPU性能方程式

$$\begin{aligned} CPU\text{実行時間} &= \text{命令数} \times CPI \times \text{クロック・サイクル時間} \\ \\ &= \frac{\text{プログラムの実行命令数} \times CPI}{\text{クロック周波数}} \end{aligned}$$

CPUのエネルギーと電力

現代の集積回路の支配的なテクノロジーはCMOS論理回路

• 消費電力が極めて少ない
• 論理値が変化するときだけ電流を消費する

$$\text{消費エネルギー}:E \propto \int_0^t P = Pt = P \times \frac{\text{プログラムの実行命令数} \times CPI}{\text{クロック周波数}}$$

ムーアの法則

集積回路上のトランジスタ数は「18か月(=1.5年)ごとに倍になる」

• n年後の倍率pは $p = 2^{n/1.5}$

アムダールの法則

処理効率はそれを構成する個々の要素の平均効率で決まるのではなく、一部の非効率部分によって律速される

あるコンピュータ上で実行にTかかるプログラムがある。プログラムは効率化可能部分TPと効率化不可能部分TSからなるとする

$$T = TP + TS$$

TPの部分について、n倍の理想的な効率化ができるとするとその時の実行時間T(n)は

$$T(n) = \frac{TP}{n} + TS$$

nを無限大にすると

$$\lim_{n \rightarrow \infty} T(n) = TS$$

課題2.1

あるプログラムPをあるプロセッサM上で実行すると90億個の命令が実行され，この場合のCPIが0.8であることがわかっている．また，クロック周波数は3.0GHzとする．Pの実行を開始してから終了するまでの実行時間を求めよ．ただし，ここでの実行時間とは，OSがPに割り当てる正味の実行時間，いわゆるユーザCPU時間とする．

• 命令数: $CI = 90 \times 10^8$
• CPI = 0.8
• クロック周波数: $f = 3 \times 10^9 Hz$

$$\frac{CI \times CPI}{f} = 2.4(s)$$

課題2.2

同じ命令セットを別々に実装したプロセッサX1とX2がある．X1のクロック周波数は4.0GHzであり，X2のクロック周波数は2.0GHzである．表はこの命令セットを3つの命令タイプ（A,B,C）に分類し，X1とX2における各命令タイプごとに求めた平均CPIを示している．この表にはあるプログラムPXに関して3種類のコンパイラ(C1,C2,C3)によって生成される命令の実行回数の割合（命令出現頻度）も示されている．PXに関して，命令の総実行回数は3つのコンパイラとも同じであるが，命令タイプごとの命令実行回数割合は表に示されているとおりであるとする．この条件の下でPXを実行するとき、以下の問いに答えよ。明示してある情報以外の条件は，プロセッサ間およびコンパイラ間で同一とする．

(1) X1とX2の両方でC1を使用した場合、X1とX2のどちらがどのくらい速いかを示せ

X1でC1を使う場合、平均CPUクロックサイクル時間は

$$0.5 \times 1 + 0.4 \times 2 + 0.1 \times 4 = 1.7$$

この時のCPU実行時間は，PXの命令総実行回数をNとすると

$$\frac{1.7}{4 \times 10^9} \times N = 0.425N(ns)$$

同様に、X2でC1を使った場合，0.775N(ns)となる．よって0.775N / 0.425N = 1.82倍

(2) X1で最も高速にPXを実行するには、どのコンパイラを使用するべきか

X1で各コンパイラのCPU実行時間は、

よって、C2

(3) X2で最も高速にPXを実行するには、どのコンパイラを使用するべきか

X2で各コンパイラのCPU実行時間は、

よって、C3

(4) PXを最も高速に実行するプロセッサとコンパイラの組み合わせを共に示せ

上の表より、X1、C2が最も速い

課題2.3

Mooreの法則に基づくと、2020年における1チップ上のトランジスタ数は2010年の何倍になるか？(小数点第2位を四捨五入して答えよ)

$$2^{\frac{10}{1.5}} = 101.59$$

よって101.6倍

課題2.4

あるアプリケーションを実行しているシングルコアシステムAを同じアーキテクチャの2つのコアを持つシステム（デュアルコアシステム）Bに変更し、電力が節約できないかを検討する．ここでは、電圧は周波数とともに直線的に下げることが可能であるとする

(1) 実行予定のアプリケーションが80％並列化可能であるとする．同じ性能（応答時間）を得るために，どの程度周波数を下げることができるか？

サイクル数をCI，サイクルクロック数をCPIとする．

$$\begin{aligned} &T_A = \frac{CI \times CPI}{f_A} \\ &T_B = \frac{CI \times CPI}{f_B} \\ &T_B^{'} = (\frac{0.8}{2} + 1 - 0.8)T_B \\ &T_A = T_B^{'} \end{aligned}$$

システムAとBでCIとCPIは変化しないことから、

$$\frac{f_B}{f_A} = \frac{0.8}{2} + 1 - 0.8 = 0.6$$

(2) デュアルコアシステムBを(1)の周波数で実行するとき、シングルコアシステムAに比べて動的電力をどの程度要求するか？

• $V \propto f$

$$\frac{P_B}{P_A} = \frac{V_B^2 f_B}{V_A^2 f_A} = \frac{(0.6V_A)^2 (0.6f_A)}{V_A^2 f_A} = 0.6^3 = 0.216$$

(3) 電圧が元の電圧の75%以下には設定することができないとする．この電圧のことを「下限電圧」と呼び，この電圧より低くするとシステムが動作しなくなる．下限電圧に達してしまう並列化の割合（％）はいくらか？

並列度をxとする. $T_A = T_B^{'}$より

$$\frac{f_B}{f_A} = \frac{x}{2} + 1 - x$$

ここで、

$$V_B \geq 0.75V_A \Rightarrow f_B \geq 0.75f_A$$

より、

$$\frac{f_B}{f_A} = \frac{x}{2} + (1 - x) \geq 0.75 \Leftrightarrow x \leq 0.5$$

(4) 下限電圧を考慮した場合，デュアルコアシステムBはシングルコアシステムAに比べてどの程度，動的電力を必要とするか？

$$\frac{P_B}{P_A} = \frac{V_B^2 f_B}{V_A^2 f_A} = \frac{(0.75V_A)^2 (0.6f_A)}{V_A^2 f_A} = 0.75^2 \times 0.6 = 0.3375$$

CPU性能相关题目-1

• ピーク性能[命令数 / 秒] = クロック周波数[クロック数 / 秒] / CPI[クロック数 / 命令数]

CPU性能相关题目-2

• $\frac{1}{3} * 0.74 + (1 - 0.74) = 0.50666$

总结-CPU性能公式

基础知识：

• CPU时间：一个程序在CPU上运行的时间（不包括I/O时间）
• 主频，时钟频率：CPU内部主时钟的频率，表示1秒可以完成多少个周期
  • 例如：主频为4.1GHz，表示每秒可以完成 $4.1 * 10^9$ 个时钟周期
• 时钟周期：时钟周期也成为振荡周期，定义为时钟频率的倒数。时钟周期是计算机中最基本，最小的时间单位。在一个时钟周期内，CPU仅完成一个最基本的动作
  • 例如：时钟周期 = 1 / 频率，$clock \ cycle = 1 / 4.1 * 10^9$
  • CPU的时钟周期越短，CPU性能越好
• 指令周期：取出并执行一条指令的时间
• 指令周期数CPI：平均每条指令耗费的时钟周期数

由上式变换得

1
2
3

执行程序所需要的时钟周期数 = CPI * 所执行的指令条数
CPU时间 / 时钟周期时间    = CPI * 所执行的指令条数
CPU时间                  = CPI * 所执行的指令条数 * 时钟周期时间

我们约定IC：所执行得指令条数，因此

命令セットアーキテクチャ(ISA)

命令セットアーキテクチャ(Instruction Set Architecture, ISA)とは、コンピュータの備えるべき機能とそれを動作させるための命令セットを定めるもの

• アーキテクチャの実装(ハードウェア)によらない

抽象化に関するその他のアイデア:

• OS
  • 低水準システム機能(I/O, メモリ割当)の抽象化 $\Rightarrow$ ユーザは機能の詳細を気にする必要がない
• ABI(application binary interface)
  • 命令セットだけでなくOSまで含んだ定義 $\Rightarrow$ 互換ABIのシステムでは同じバイナリファイルが実行可能

代表的なISA

• CISC(Complex Instruction Set Architecture)
  • 複雑な一連の処理を少ない命令数で行うことでパフォーマンス向上を目指した命令セットアーキテクチャ
  • eg. Intel x86, System/360
• RISC(Reduced Instruction Set Architecture)
  • 各命令を単純にして高速に実行することでパフォーマンス向上を目指した命令セットアーキテクチャ
  • eg. MIPS, ARM, PowerPC, SPARC
• VLIW(Very Long Instruction Word)
  • 複雑な機能が詰め込まれたかなり長い語によって一単位の命令が構成されている命令セットアーキテクチャ
  • eg. Itanium, Crusoe

MIPSアーキテクチャ

MIPS Computer System(現MIPS Technologies)が1980年代初頭から設計・開発が行われているRICSマイクロプロセッサ

MIPS I

• レジスタ長は32bit(= 4byte)、32本
  • CPU内の記憶装置、容量は少ないが高速
• 命令は32bit(= 4byte)の固定長
• 命令形式は3種類で各命令で行える演算は一つだけ
• メモリアクセスはロード(lw)/ストア(sw)命令のみ
• 3オペランド命令
  • eg. add C, A, B
  • オペランド = 命令
• 遅延分岐

MIPSの代表的な命令セット

MIPSのオペランド

メモリアドレス

• バイトアドレス方式(Byte Addressing)
  • 1バイト単位でアドレスを割り振られる
• MIPSの1命令は4バイト固定長(4バイト=1語(word))
  • 整列化制約: 各命令のアドレスは4の倍数になる
    • PCは4刻みで増える
  • 配列のインデックスに4を掛けてバイトに直す必要がある

レジスタ使用した演算

例: 次のCステートメントに対応するMIPSアセンブリ・コードを示せ. 変数a, b, c, d, eの値はそれぞれレジスタ$s0, $s1, $s2, $s3, $s4に格納されているとする.

(1) a = b + c; // C code

1

add $s0, &s1, $s2

(2) a = b + c + d + e; // C code

1
2
3

add $s0, &s1, $s2
add $s0, &s0, $s3
add $s0, &s0, $s4

ロードとストア(load/store)

演算命令(add)はレジスタの内容を読んで演算結果をレジスタに書き込む $\Rightarrow$ メモリ上のデータはレジスタに予めロードする必要がある

例題1: 次のCステートメントに対応するMIPSアセンブリ・コードを示せ. 変数hは$s2, 配列Aの先頭アドレス(&A[0])は$s3に格納されているとする.

(1) A[12] = h + A[8]; // C code

• A[8]をレジスタにロードする
  • A[8]のアドレスを求める
  • A[8]のデータをレジスタにロードする

• h + A[8]を計算する
• 計算計算をA[12]にストアする

1
2
3
4
5

lw $t0, 32($s3)     // A[8]をレジスタにロードする

add $t0, $s2, $t0   // h + A[8]を計算する

sw $t0, 48($s3)     // 計算計算をA[12]にストアする

例題2:

定数の加算

• 定数を用いて演算はプログラム中に頻出する

例: a = a + 4; // C code

• a, 4 $\Rightarrow$ $s1, AddrConstrant4($s2)

1
2
3

lw $t0, AddrConstrant4($s2) // メモリからロード

add $s1, $s1, $t0

メモリから定数をロードするよりも遥かに効率がよい $\Rightarrow$ 基本命令形式に変型版を用意する

1

addi $s1, $s1, 4

MIPSの命令形式

命令形式: 命令語のフィールド構成

• MIPS は命令語を32bit 幅で統一している
• MIPS の命令形式は，R形式，I形式，J形式の3種類がある
• どの命令形式かは，op フィールド（命令操作コード）で判別できる

R形式

• op: 命令操作コード
• rs: 第1のソースオペランドのレジスタ
• rt: 第2のソースオペランドのレジスタ
• rd: デスティネーション・オペランド (結果出力) のレジスタ
• shamt: シフト量
• funct: 機能コード. オペランドのバリエーション

I形式

J形式

比較命令

論理演算命令

シフト命令

• 左移1位即乘2

課題3.1

(1) 以下の空欄に当てはまる語句を埋めよ．

1. コンピュータを動作させる（機械語の）命令の集まりを命令セットという．
2. ハードウェアと最低水準のソフトウェアとの間のインターフェースのことを命令セットアーキテクチャという．
3. 機械語の命令を記号で置き換えた言語をアセンブリ言語という．
4. CPU内にあり容量は少ないが非常に高速に動作するメモリのことをレジスタという．
5. MIPSのレジスタは32本あり，レジスタ長は32bitである．
6. MIPSの命令長は32bitの固定長である．
7. MIPSの命令フォーマットは3種類あり，Rフォーマット, Iフォーマット, Jフォーマットである．
8. 各命令で演算の対象となる変数のことをオペランドという．
9. MIPSのメモリアドレスはバイトアドレス方式である.
10. MIPSのプログラムカウンタは4刻みで増える．

(2) 以下のC ステートメントに対応するMIPS アセンブリ・コードの空欄を埋めよ．変数f, g, h, i, j はレジスタ$s0, $s1, $s2, $s3, $s4 にそれぞれ割り当てられている．配列A, B の先頭アドレスはレジスタ$s6, $s7 にそれぞれ割り当てられている．一時変数としてレジスタ$t0, $t1 を使用することができる．$zeroは常にゼロとなるレジスタである．

1. f = g + (h –10); // C言語

MIPSアセンブリ・コード

1
2

addi $s0, $s2, -10  // f = h - 10
add $s0, $s0, $s1   // f = f + g

2. B[8] = A[i – j]; // C言語

MIPSアセンブリ・コード

1
2
3
4
5

sub $t0, $s3, $s4   // Calc i-j                         计算偏移量
sll $t0, $t0, 2     // (i-j)*4 [index -> Address[Byte]] 左移1就乘2， 移2就乘4
add $t0, $s6, $t0   // Calc address of A[i-j]           用A[]的首地址计算A[i-j]地址
lw $t0, 0($t0)      // Load A[i-j] into $t0             读取A[i-j]的值
sw $t0, 32($s7)     // Store $t0 into B[8] (32 = 8*4)   将A[i-j]的值保存在B[8]上

3. f = -g - A[5]; // C言語

MIPSアセンブリ・コード

1
2
3

lw $s0, 20($s6)       // Load A[5] into f
sub $s0, $zero, $s0   // f = 0 - f
sub $s0, $s0, $s1     // f = f - g

4. B[6] = h + A[i - j]; // C言語

MIPSアセンブリ・コード

1
2
3
4
5
6

sub $t0, $s3, $s4     // Calc i-j
sll $t0, $t0, 2       // (i-j)*4 [index -> Address[Byte]]
add $t0, $t0, $s6     // Calc address of A[i-j]
lw $t0, 0($t0)        // Load A[i-j] into $t0
add $t0, $t0, $s2     // $t0 = $t0 + h
sw $t0, 24($s7)       // Store $t0 into B[6] (24 = 8*3)

• 计算偏移量(i - j)
• 偏移地址(i - j)*4
• 计算地址（用首地址）
• load数值
• store数值

ループの処理

ループで使う命令:

• beq(branch if equal): beq register1, register2, L1
  • レジスタ1とレジスタ2の値が等しい時、L1というラベルの付いたステートメントにプログラムの流れを分岐される
• bne(branch if not equal): bne register1, register2, L1
  • レジスタ1とレジスタ2の値が等しくない時、L1というラベルの付いたステートメントにプログラムの流れを分岐される
• j(無条件分岐): j Exit
  • プロセッサに必ず分岐を行わせる
• slt(set on less than):
  • slt register3, register1, register2 # 符号付き
  • sltu register3, register1, register2 # 符号なし
  • レジスタ1 < レジスタ2の場合にレジスタ3に1をセットし、そうでない場合に0をセットする

分岐命令

forループ

whileループ

手続き処理

MIPSでの手続き呼び出し

専用レジスタ

• $a0 - $a3: 引数レジスタ(パラメータを渡すために使用)
• $v0 - $v1: 値レジスタ(結果の値を返すために使用)
• $ra: 戻りアドレス・レジスタ(制御を元に戻すために使用)

手続き専用の命令

• jal[手続きのアドレス]
  • jump-and-link命令
  • 手続きのアドレスにジャンプすると同時に、次の命令のアドレスをレジスタ$raに退避する
• jr[レジスタ]
  • jump-register命令
  • レジスタ中に指定されているアドレスに無条件にジャンプする

スタックを用いたレジスタのスピル・アウト

汇编里把一段内存空间定义为一个栈，栈总是先进后出，栈的最大空间为 64K。由于 “栈” 是由高到低使用的，所以新压入的数据的位置更低，ESP 中的指针将一直指向这个新位置，所以 ESP 中的地址数据是动态的。

赤字の三つのレジスタを一時的に退避させておかないと手続き呼び出し前後で状態が変わってしまうことになる

レジスタの内容をメモリに退避させることをスピル・アウトという

例: 再帰(recursion)

この例ではローカル変数がスタックに退避させる必要がない

• 手続きフレーム（アクティベーション・レコード）: スタックのうちで、手続きによって退避されたレジスタおよびローカル変数が収められている領域
• フレームポインタ: 手続きフレームの先頭の語を指す$spは手続き中変化するが$fpは変化しない

手続き呼び出し中に保持される/されないレジスタ:

アドレシング

アドレシング(Addressing): データの場所を指し示す方法

MIPSのアドレシング・モード

• 即値アドレシング: 命令中に指定した定数をオペランドとする
• レジスタ・アドレシング: オペランドにレジスタを取る
• ベース相対アドレシング（ディスプレースメント・アドレシング）: 命令中に指定した定数とレジスタの和によって、オペランドが記憶されているメモリの位置を示す
• PC相対アドレシング: PCと命令中に指定した定数との和によってアドレスを示す
• 疑似直接アドレシング: 命令中の26ビットとPCの上位ビットを連結したものがジャンプ・アドレスとなる

即値アドレシング

符号拡張(sign extension): レジスタ上位の空きビットに符号ビットを繰り返しコピーして埋める操作

• $\color{blue}{0}$が16bitにおける符号ビットで、これは赤字の上位ビットにコピー

レジスタ・アドレシング

• rs, rt, rd: レジスタ(32bit)

ベース相対アドレシング

• 例: lw, lh, lb
• ロードとストアには語、半語、バイト

PC相対アドレシング

• 例: beq, bne

疑似直接アドレシング

アドレシング例

• beq命令では次の命令アドレス（PC＋4）をベースに相対アドレス（2語=2*4バイト）を指定している（PC相対アドレシング）
• j命令ではラベルLoopに対する完全なアドレス(語単位)を指定している

MIPSの設計規則

• 単純性は規則性につながる
  • 命令が固定長
• 小さければ小さいほど高速になる
  • レジスタ数が32本
• 優れた設計には適度な妥協が必要である
  • 命令長を固定する代わりに複数の命令形式を用いる
• 一般的な場合を高速化する
  • PC相対アドレシング
  • 即値アドレシング

課題3.2

(1) 在MIPS中条件分支的地址范围（K=1024）是多大？

上位4ビットがPCから得られる256Mのアドレスの範囲内

(2) 在MIPS中跳转和跳转链接指令的地址范围（M=1024K）是多大？

分岐点の前後それぞれ約128Kの範囲のアドレス

(3) 以下のMIPS アセンブリ・コードに対応するC ステートメントを簡潔に示せ．

変数a, b, h, i, j はレジスタ$s0, $s1, $s2, $s3, $s4 にそれぞれ割り当てられている．

配列A, B の先頭アドレスはレジスタ$6, $s7 に それぞれ割り当てられている．

一時変数としてレジスタ$t0, $t1 を使用することができる．$zero は常にゼロとなるレジスタである．

MIPSアセンブリ・コード

1
2
3
4
5
6

       addi  $s3,    $zero,  $s0   
       beq   $zero,  $zero,  TEST  
LOOP:  addi  $s4     $s4     2     
       addi  $s3,    $s3     1     
TEST:  slt   $t1,    $s3,    $s1   
       bne   $t1,    $zero,  LOOP  

1
2
3

for (i = a; i < b; i++){
  j = j + 2;
}

• beq(branch if equal): beq register1, register2, L1
  • レジスタ1とレジスタ2の値が等しい時、L1というラベルの付いたステートメントにプログラムの流れを分岐される
• bne(branch if not equal): bne register1, register2, L1
  • レジスタ1とレジスタ2の値が等しくない時、L1というラベルの付いたステートメントにプログラムの流れを分岐される
• j(無条件分岐): j Exit
  • プロセッサに必ず分岐を行わせる
• slt(set on less than):
  • slt register3, register1, register2 # 符号付き
  • sltu register3, register1, register2 # 符号なし
  • レジスタ1 < レジスタ2の場合にレジスタ3に1をセットし、そうでない場合に0をセットする

(4) 以下のMIPSアセンブリ・コードを実行する．次の問いに答えよ．

1
2
3
4
5

       slt   $t2,  $zero,  $t0   
       bne   $t2,  $zero,  ELSE  
       j     DONE                
ELSE:  addi  $t2,  $t2,    2     
DONE:

• $t0に0x00101000が保持されているとき、$t2の値はどうなるか
  • $$t_2 = 1 \Rightarrow 1 + 2 = 3$
• $t0に0x80001000が保持されているとき、$t2の値はどうなるか
  • $$t_0 < 0$
  • $$t_2 = 0$

(5) 16ビット固定長の命令セットをもつコンピュータがある。このコンピュータには、30種の命令が規定されており、汎用レジスタの数は4である。また、命令フォーマットでは、命令種別、レジスタ番号、即値を指定するフィールドが規定されており、レジスターレジスタ間の演算命令は3個（ソース2個、デスティネーション1個）、レジスター即値間の演算命令は2個（ソース1個、デスティネーション1個）のレジスタオペランドを取るとする。

レジスター即値間の演算命令において、命令種別及びレジスタオペランドの指定に用いるフィールド以外のビットをすべて即値の表現に使用できるとしたとき、この命令で扱うことができる即値の最大値として最も妥当なのはどれか。

ただし、命令種別を表すフィールドは固定幅とし、そのフィールド以外で命令種別を区別することはできないものとする。また、即値フィールドは符号なし整数として解釈されるものとする。

解答: 127

• 命令数30種であるから0～29で表現できればよい。この時、5bitが必要。
• 汎用レジスタの数4であるから0から3で表現できればよい。このとき、2bitが必要。
• レジスター即値の演算命令で命令とオペランド2つで必要なビット幅は5+2*2=9bitであることから残り7bit。
  • rs: ソース, rt: デスティネーション
• 7bitで表現できる数は $2^7 = 128$(通り）であるから、符号なし整数の場合、0から127まで表現することが出来る

(6) 次のプログラムにおいて，命令Aから命令Bまで実行されるとき，次の問いに答えよ．ただし，$zeroは常にゼロとなるレジスタであり，アドレス100からデータメモリに格納されているワード値は，順番に2,4,6,8,10,⋯とする． また，命令Aは命令アドレス0000A000に置かれているとする．

1
2
3
4
5
6
7
8
9
10
11

プログラム：                               
  アドレス   命令                          
  0000A000  addi $s5, $zero, 100 (命令A)  
            addi $s1, $zero, 104        
            addi $s2, $zero, 0          
    loop    lw $s3, 0($s5)              
            add $s2, $s2, $s3           
            addi $s5, $s5, 4            
            slt $s4, $s1, $s5           
            beq $s4, $zero, loop        
            sw $s2, 0($s5) (命令B)

• 命令B実行後のレジスタ$s2の値を示せ．
  • $2 + 4 = 6$
• プログラムのbeq命令を実行するときの符号拡張の出力の値を8桁の16進数で示せ．

PC相対アドレッシング

ジャンプ先アドレス = PC + 4 + (符号拡張, 2ビットシフト）

swから5命令前まで戻ればよい.

1
2
3
4

0000 0101 ← 5
1111 1010 ← 符号反転
1111 1011 ← +1 (2の補数) = -5
FB

よって符号拡張した結果はFFFF FFFB

这里要求beq命令执行时候这个loop的值，即符号扩张。所以找到上面loop这一行后再往上一行，即往上5行，这个值位5。

所以求5的符号扩张的值即可。最后转化成16进制

算数演算

整数の加算と減算

加算

• 最下位ビットから順にビットごとに加算し桁上げがあれば次の桁のビットに加える
• 加算によって最上位ビットからの繰り上がりが発生（オーバーフロー）した場合
  • 符号あり演算(add,addi,subなど)の場合：例外(割り込み)が発生
  • 符号なし演算(addu,addiu,subuなど)の場合：無視する

$$(0110)_2 + (0001)_2 = (0111)_2$$

減算

• 引く数を正負反転（2の補数）して加算

$$(0111)_2 - (0110)_2 = (0111)_2 + (1010)_2 = (0001)_2$$

オーバーフロー

結果が用意されたハードウェアに収まりきらない場合、オーバーフローが発生する

$$(6)_{10} + (2)_{10} = (0110)_2 + (0010)_2 = (1000)_2 = \color{red}{-8}$$

• 正の数同士、若しくは負の数同士の加算では、このようなことが起こる
• この例では4ビットなので、計算結果が-8から7に収まらないといけない

オーバーフローが起きないケース:

• 符号が異なる数の加算（正の数 + 負の数）
• 符号が同じ数の減算 = 符号が異なる数の加算
  • 正の数 - 正の数 = 正の数 + 負の数

オーバーフローの検出と例外処理

最上位ビット（符号ビット）が値として設定される

• 以下はオーバフロー起きている場合

例外（割り込み）:

• 例外を起こした命令のアドレスをレジスタに退避
  • MIPSでは例外プログラムカウンタEPCが用意されている
• 例外処理ルーチンにジャンプ
  • mfc0（movefromsystemcontrol）命令でEPCをレジスタにコピーできる（例外処理後、jrで復帰することも可能）

MIPSの加算と減算（まとめ）

• 符号あり整数の加算(add,addi)と減算(sub)

1
2
3

add  $s1, $s2, $s3 : $s1 = $s2 + $s3
addi $s1, $s2, 20  : $s1 = $s2 + 20
sub  $s1, $s2, $s3 : $s1 = $s2 ‐ $s3

• 符号なし整数の加算(addu,addiu)と減算(subu)

1
2
3

addu  $s1, $s2, $s3 : $s1 = $s2 + $s3
addiu $s1, $s2, 20  : $s1 = $s2 + 20
subu  $s1, $s2, $s3 : $s1 = $s2 ‐ $s3

整数の乗算、除算

乗算

$$(1000)_{10} \times (1101)_{10} = (1101000)_{10}$$

乗算ハードウェア

1. 乗数の最下位ビットの値に応じて被乗数を積レジスタに加える
2. 被乗数レジスタを左シフト
3. 乗数レジスタを右シフト

このステップを32回繰り返すことで結果が得られる

乗算ハードウェアの改良

1. 乗数の最下位ビットが１の場合、被乗数を積に加算
2. 積レジスタ（乗数含む）を右シフトする

このステップを32回繰り返すことで結果が得られる

MIPSにおける乗算命令

除算

除算ハードウェア

除算ハードウェアの改良

符号付き除算

被除数 = 商 $\times$ 除数 + 剰余

• 商の符号 = 被除数と除数が同符号なら正, 異符号なら負
• 剰余の符号 = 被除数の符号

例:

• $7 \div 2 = +3 \cdots +1$
• $7 \div (-2) = -3 \cdots +1$
• $-7 \div 2 = -3 \cdots -1$
• $-7 \div (-2) = +3 \cdots -1$

MIPSによる除算

浮動小数点の表現法(IEEE 754)

実数を表す科学記数法

$$(-1)^S \times (\text{仮数部}) \times 2^{\text{指数部}}$$

• eg. $1.0101 \times 2^{-1}$
• 小数点の左側が一桁でかつ0でないものを正規化数という

IEEE 754のエンコード規則

• オーバーフロー：正の指数が大きすぎて指数部に収まりきらない場合
• アンダーフロー：負の指数が大きすぎて指数部に収まりきらない場合
  • いずれも正規化数にすることができない
• ゼロ除算: 非ゼロの数をゼロで割った場合
  • 例外処理 or $\pm \infty$のビットパターンを設定
• 無効演算: $\infty \times 0, \infty - \infty, \infty \div \infty, 0 \div 0$, 負の平方根
  • 例外処理or NaNのビットパターンを設定

浮動小数点の加算、乗算

浮動小数点の加算

浮動小数点の乗算

MIPSにおける浮動小数点命令

課題3.3

(1) 以下の空欄に当てはまる語句を埋めよ．

1. 整数の演算で結果が用意されたハードウェアに収まりきらない場合、オーバーフローが発生する．
2. 符号が同じ数の減算ではオーバーフローの事象は起こりえない．
3. MIPSでは符号なし整数の加算、減算命令はオーバーフローが起きても無視する．無視しないときは例外または割込みが発生する．
4. MIPSの符号付き乗算命令はmultであり，HiとLoの2つのレジスタに結果が格納される．
5. IEEE 754は浮動小数点演算の標準規格であり，32bitの浮動小数点形式を単精度浮動小数点，64bitの浮動小数点形式を倍精度浮動小数点という．
6. 単精度浮動小数点、倍精度浮動小数点のゲタはそれぞれ127, 1023である．
7. IEEE 754で小数点の左側が一桁でかつ0でないものを正規化数という．
8. IEEE 754で仮数部も指数部も0であるときの値は0である．

(2) IEEE 754標準規格を使用して，10進数の-12.75を単精度浮動小数点フォーマットで表現し，これを16進数で表せ．

• $s = 1$

$$(12.75)_{10} = (1100.11)_2 = (1.10011 \times 2^3)_2$$

であるから、仮数部は1．指数部をEとすると

• $E - 127 = 3 \Leftrightarrow E = 130$

$$(130)_{10} = (128+2)_{10} = (2^7+2^1)_{10} = (1000 0000+0000 0010)_2 = (1000 0010)_2$$

であるから

• $s = 1$
• 指数部 = 1000 0010
• 仮数部 = 1001 1000 … 000

となる。

$$(1100)_2 = (C)_{16}, \quad (0001)_2 = (1)_{16}, \quad (0100)_2 = (4)_{16}, \quad (1100)_2 = (C)_{16}$$

よって、C14C0000

1
2
3
4

import bitstring

bitstring.BitArray(float=-12.75, length=32) 
BitArray('0xc14c0000')

(3)

IEEE 754形式を使用して，−1/4を表すビットパターンを16進数で示せ．−1/4を正確に表すことができるか．

• ビットパターン: BE800000
• 正確に表すことができる

IEEE 754形式を使用して，1/10を表すビットパターンを16進数で示せ．1/10を正確に表すことができるか．

• ビットパターン: 3DCCCCCC
• 正確に表すことができない

プログラムの翻訳

コンパイラ

• プログラムをアセンブリ言語に翻訳する
• オブジェクトファイルを直接生成するものもある

1
2

# gccの場合
gcc ‐c ‐o hello.o hello.c

アセンブラ

アセンブリ言語プログラムをオブジェクトに翻訳する

1
2

# gccの場合
gcc ‐S ‐o hello.s hello.c

オブジェクト・ファイル

機械語命令、データ、命令をメモリ中に配置するための情報からなるファイル

オブジェクトファイルの構成（UNIXの場合）

• オブジェクト・ファイル・ヘッダー: 残りの部分のサイズと位置
• テキスト・セグメン: プログラム（機械語）
• 静的データ・セグメ: 静的変数など
• リロケーション情報: プログラムをメモリにロードした時の絶対アドレスに依存する命令語およびデータ語
• シンボル・テーブ: 外部参照などの未定義の残りのラベル
• デバッグ情報: どのようにコンパイルしたかの記録

リンカ（リンク・エディタ）

個別に作られたオブジェクトファイルをつなぎあわせて実行ファイルを作成するシステム・プログラム

MIPSプログラムのメモリ構造

例: 手続きA, Bのリンク

• テキスト・セグメントの開始アドレス: $(40 \ 000)_{16}$
• データ・セグメントの開始アドレス: $(1000 \ 0000)_{16}$
• グローバル・ポインタ($gp): $(1000 \ 8000)_{16}$

1. 手続A, Bをメモリに配置する
   1. 変数X、Y手続きA、Bのアドレスが決まる
2. 各命令のアドレス・フィールドを更新する
   1. リンカは命令タイプ・フィールドを参照して更新対象のアドレスのフォーマットを判別する
   2. load/store命令：$gpに対する相対アドレス
   3. jal命令：疑似直接アドレッシング, ジャンプ先アドレスが直接書き込めばよい

• 手続きAのテキストサイズは100, データサイズは20なので, 手続きBのテキスト解釈アドレス, データ解釈アドレスはそれぞれ赤字に示した.

• 続いて, リンカは命令のアドレスフィールドを更新していく.
• まず, jump and link命令jal $100040_{16}$のjump先アドレスは手続きBの解釈アドレスになるので$0040 \ 0100_{16}$
• 一方, アドレス$0040 \ 0104_{16}$ jump and link命令jal $100000_{16}$のjump先アドレスは手続きAの解釈アドレスになるので$0040 \ 0000_{16}$になる
• jump and link命令で指定するアドレスが擬似直接アドレシングなので, アドレスフィールド26bitを2bit左shiftして, それがアドレスになる. よって, 実際のアドレスは逆に2bit右shiftしたものになるので, 赤字のように, $0010 \ 0000_{16}$, $0010 \ 0040_{16}$になる

• 次にload命令とstore命令のアドレスフィールドの更新. これらの命令はグローバルポインタに対する相対アドレスが指定される
• グローバルポインタは$1000 \ 8000_{16}$で初期化されている. 変数Xのアドレスを得るためには, グローバルポインタから$8000_{16}$を引いてあげると良い. これをload命令のoff setに設定してあげるとXを指定することができる.
• 同様に, 変数Yのアドレスを得るためには, グローバルポインタから$8020_{16}$を引いてあげると良い. これをload命令のoff setに設定してあげるとYを指定することができる.
• このようにして, データ・セグメントの相対アドレスを解決する

ローダ

プログラムを主記憶に読み込んで実行できるようにするシステム・プログラム

1. 実行ファイルのヘッダーを読んで、テキストセグメントとデータセグメントの大きさを判定
2. テキストセグメントとデータセグメントを保持するのに十分な大きさのアドレス空間を作成
3. 実行ファイルから命令とデータをメモリにコピー
4. メインプログラムに渡されるパラメータが存在すれば、スタック上にコピー
5. マシンのレジスタを初期化し、スタックポインタに最初の空きロケーションを設定
6. 開始ルーチンにジャンプ
   1. 開始ルーチンはスタックからプログラムの内容をレジスタにコピーしてプログラムのメイン・ルーチンを呼び出す。メインルーチンから処理が戻ると開始ルーチンは終了システムコールを用いてプログラムを終了させる

静的ライブラリ(Static Library)

ライブラリ = 複数のプログラムで使われる共通の機能をまとめたもの

静的ライブラリは、リンク時に実行ファイルの一部に組み込まれる. 拡張子は.a/.lib

1
2
3
4

# gccの場合
ar r lib AB.a A.o B.o
gcc main.c‐l AB‐L.
gcc main.c A.o B.o

動的ライブラリ(DLL,Dynamic Link Library)

静的ライブラリの欠点:

• 実行ファイルの一部に組み込まれるため、新バージョンのライブラリに自動的に更新されない
• 実際に使用されないものも含むため実行ファイルのサイズが大きくなってしまう

動的ライブラリは、プログラムが実行されるときにリンク・ロードされる

• 実行ファイルのサイズを小さくできる
• 初回呼び出しのときのみ負荷がかかるが、2回目以降はかからない

ARMv7(32bit)

組み込み機器や低消費電力機器向けに広く用いられている

課題4.1

(1) 次の説明が示す語句を答えなさい．

1. 機械語の命令を人間にとってわかりやすい記号に一対一で置き換えた言語: アセンブリ言語
2. アセンブラによって生成されるプログラム単位: オブジェクトファイル
3. オブジェクトをつなぎ合わせて実行ファイルを作成するシステム・プログラム: リンカ
4. デバッグ情報を含まない実行ファイル: ストリップ済み実行ファイル
5. 複数のプログラムで使われる共通の機能をまとめたもの: ライブラリ

(2) 次のMIPSアセンブリ・コードについて以下の問に答えよ．

1

lw  $s2  -12($s0)

• lw命令の第1オペランド、第2オペランドのアドレッシング・モードをそれぞれ答えよ．

第一オペランド：レジスタアドレッシング
第二オペランド：ベース相対アドレッシング

• $s0の値が0x00000100であった．lw命令の第2オペランドの実効アドレスを求めよ．

ベースアドレスにオフセットを足し合わせればよい。

ベースアドレス：0x00000100
オフセット：-12 = 0xFFFFFFF4

より 0x0000 0100 + 0xFFFF FFF4 = 0x0000 00F4

(3) 次の疑似命令を実現するMIPSアセンブリ・コードを1行で示せ．

clear $t0($t0をzeroでクリアする)

• add $t0, $zero, $zero

データパス(Datapath)

コンピュータの速度を決める要因:

• 実行命令数
  • 命令セット・アーキテクチャ
  • コンパイラ
• クロック・サイクル時間
  • プロセッサの実装
• 命令当たりのクロック・サイクル数（CPI）
  • プロセッサの実装

プロセッサの構成

プロセッサは大別してデータパスと制御で構成される

• データパス：演算処理を行う
• 制御：データパスとメモリに指示を出す

データパス要素：プロセッサ内でデータを処理または保持するために使用する機能ユニット

• eg. 命令メモリ、データメモリ、レジスタ、ALU、加算器

MIPSにおけるデータパスの論理要素

クロック方式(clocking methodology)

データが読み出し可能なタイミング、書き込み可能なタイミングの定義

エッジ・トリガ・クロック方式(edge-triggered clocking): クロック波形のエッジでのみ状態論理要素に記憶されている値を更新する方式

この方式を使うと、レジスタから値を読み出し、何らかの演算を行って、結果はレジスタに書き込むという動作を1クロック・サイクルで実行することができる
The inputs are values that were written in a previous clock cycle, while the outputs are values that can be used in a following clock cycle

MIPS命令のサブセットの実装

実装する命令セット:

• メモリ参照命令：lw、sw
• 算術論理演算命令：add、sub、and、or、slt
• 分岐命令：beq、j

左から: PC(レジスタ)、命令メモリ、レジスタファイル、ALU、データ・メモリ

データパス要素->命令メモリ

実行対象となる命令を格納する

• 命令メモリは読み出し専用でアクセス（データパスが命令メモリに書き込むことはない）
• 常に入力アドレスによって指定された場所の内容を出力する

データパス要素->データメモリ

プログラムの実行で必要となるデータを格納する

2本の制御信号を持つ:

• MemWrite：書き込み要求（1のとき書き込み）
• MemRead ：読み込み要求（1のとき読み込み）

データパス要素->レジスタファイル

複数のレジスタの集合

書き込むを行う場合は、制御信号RegWriteがアサートされる必要がある

• レジスタ番号を指定することによって任意のレジスタを読み書きできる
• レジスタの値も保持している
• レジスタファイルは4入力, 2出力になる
• レジスタ番号指定する入力の幅は5bit
• 一方、書き込みデータと読み出しデータのデータの幅は32bit

データパス要素->ALU

指定した算術論理演算を実行する

ALU制御入力:

• 0000（AND）, 0001（OR）, 0010（加算）, 0110（減算）, 0111（Set on less than）, 1100（NOR）

Control logic is used to decide whether the incremented PC or branch target should replace the PC, based on the Zero output of the ALU.

マルチプレクサ(multiplexor)

いくつかの入力の中から⼀つを制御で選択したもの

命令の取り出し

PC、命令メモリ、ALUで実装

• プログラムカウンタ（PC）は次に実行する命令のアドレスを保持する
• 加算器は加算専用のALUであり、次の命令を指すために４バイト加算する
• 命令の読み出し（フェッチ）と同時にPC繰り上げを行う

命令の実行(Rフォーマット)

レジスタファイルとALUで実装

ロード／ストア命令(Iフォーマット)

レジスタファイルとALUで実装

分岐命令(beq)

課題5.1

• MemtoRegはデータをメモリからレジスタファイルに送るように設定しなければならない
• MemtoRegの設定は考慮する必要がある

ALU制御ユニットの設計

ALU制御入力:

• 0000（AND）
• 0001（OR）
• 0010（加算）
• 0110（減算）
• 0111（Set on less than）
• …

load/store命令ではメモリアドレスのに計算にALUが使われるように、各命令でALUはこの五つの機能をどれか一つが実行される

命令が決まるとALUのどの機能を使われるかを分かるので、制御信号も決まる

具体的には、ALUの制御信号は命令の機能コード(funct)制御フィールドから作られる

• 機能コード：Rフォーマット下位6bit
  • 各命令の5‐0ビット(6bit)
• ALUOp
  • 主制御ユニットで生成される2bitの制御コード

• LW, SWはIフォーマットなので、機能コードがないが、ALUOpのみからALU制御コードから作られる
• ALUOpコードが00：加算
• ALUOpコードが01：減算
• ALUOpコードが10：機能フィールドに応じた演算に対応するALU制御入力が生成される

• 何故ALU制御ユニットを主制御ユニットと別に用意するか？
  • 小さな制御ユニットを複数に用意するとはよく行われている。速度の向上を繋がるために、行われることが多い

主制御ユニットの設計

• 命令操作コードは常にopで指定される(opcode is always contained in bits 31:26)

• ２つの読み出しレジスタは常にrs，rtで指定される

• ロード／ストア命令のベース・レジスタはrsで指定される

• branch equal(beq)、ロード／ストアのオフセットはビット15‐0で指定される(The 16-bit off set for branch equal, load, and store is always in positions 15:0)

• 書き込みレジスタは、次の二か所で指定される

  • Rフォーマット：rd(ビット15‐11)
  • ロード命令：rt(ビット20‐16)
  • マルチプレクサによる切り替えが必要

制御信号の役割

RegDst

RegWrite

• 書き込むタイミングはクロックで決まる

ALUSrc

• ALUSrcは、Iフォーマットのアドレス計算や即値を用いた演算で使われる(lw)

PCSrc

• PCSrcは条件分岐命令で使われる(beq)

MemWrite/MemRead

MemtoReg

• MemtoRegはメモリから読みだしたデータをレジスタに書き込むときに使われる(lw)

制御信号の設定

上は8本の制御線について説明したが、この制御線の値は何を見て決めれば良いでしょうか？

制御線の値は命令操作コードを用いることで決定できる

• R形式（add、sub、and、or、slt）
  • functからALU制御信号が生成される
  • rdが書き込みレジスタに設定され、演算結果が書き込まれる
• lw/sw
  • アドレス計算を行うようにALUが設定される
• beq
  • Branch、ゼロ判定出力がアサートされていれば分岐先アドレスをPCに設定する

Rフォーマットのデータパス

ロード命令のデータパス

ストア命令のデータパス

beq命令のデータパス

ジャンプ命令(j)の実装

• 疑似直接アドレシング

単⼀サイクル・データパスの問題点

• 命令によってデータパスの長さが異なる
  • クロック・サイクルは最長パスに合わせなければなければならないため、効率が悪い

パイプライン(Pipeline)

パイプライン処理: 複数の命令を少しずつずらして同時並行的に実行する実装方式

MIPSの場合, 命令の実行は最大5ステップ（=ステージ）を要する

1. メモリから命令をフェッチする
2. 命令をデコードしながらレジスタを読み出す
3. 命令操作の実行またはアドレスを生成する
4. メモリ中のデータにアクセスする
5. 結果をレジスタに書き込む

それぞれのステージが単⼀サイクル・データパス上でどこに対応するかを見てくる

データパスの模式図

５つのステージからなる

単⼀サイクル方式での実行

単⼀サイクル方式は全ての命令が１クロック・サイクルで実行されるため、最も遅い命令にクロック・サイクルをあわせなければならない

• ここではマルチプレクサ、制御ユニット、PCアクセス、符号拡張ユニットには遅延がない
• １つの命令が終わったら次の命令を実行
• ある時刻に動作する機能ユニットは⼀つだけ

パイプライン方式での実行

複数の命令を少しずつずらして同時並行的に実行

パイプライン方式は各ステージが１クロック・サイクルで実行されるため、最も遅いステージにクロック・サイクルをあわせなければならない

ステージ数は各機能ユニットの使用の有無にかかわらず同じ

$$\text{パイプライン処理における命令の実行時間} = \frac{\text{非パイプライン処理における命令の実行時間}}{\text{パイプラインのステージ数}}$$

単⼀サイクル方式では800psだったので、理想的には5倍速くなる($800 / 5 = 160$clock cycle)が期待される。しかし、この例から、実際に200ps、即ち、4倍速くなった。これは完全にステージ時間のバランスが取れていないと示した。
また、3命令実行する場合は、確かに速くなっているが、4倍は速くなっていない。これは、命令数を増やすことで、段々4倍に近づけることができる。

• ここではレジスタの読みだしはクロックサイクルの後半で、レジスタへの書き込みは前半で行われるとする
• レイテンシ(latency)：個々の命令を完了させるのにかかる時間
• スループット(throughput)：すべての命令を完了させるのにかかる時間

パイプライン処理はレイテンシではなくスループットを向上させる

MIPSにおけるパイプライン処理

• 命令長がすべて同じ
  • 命令フェッチおよびデコードが容易
• どの命令形式でもソース・レジスタ（rs）のフィールド位置が同じ
  • フェッチされた命令の種別判定と同時に、レジスタ・ファイルの読み出しが可能
• メモリの操作はロード・ストアのみ
  • メモリ中のデータを直接演算対象にしないためステージがシンプル
• メモリに整列化制約がある（語アドレス=4の倍数）
  • データ転送が効率的

パイプライン・レジスタ：各ステージのデータを記憶しておくレジスタ

ロード命令のデータパス

1. プログラムカウントPCアドレスは4繰り上げられて、プログラムカウントにはき戻される。そして、次のクロック・サイクルに備えられる
2. IF/IDパイプライン・レジスタには命令メモリからのデータと繰り上げられたプログラムカウントの値が保存される。このプログラムカウントの値はロード命令で使わないが、beq命令などで使用するなので保存される
3. IF/IDパイプライン・レジスタからレジスタ番号と16ビットの即値フィールドが取り出される。16ビットの即値フィールドが符号拡張が行われて、読み出されたデータと共にID/EXパイプライン・レジスタに保存される
4. 次に、読み出されたデータと符号拡張された即値をALUで加算して、結果をEX/MEMパイプライン・レジスタに保存される。beq命令の分岐先アドレスもこのステージで加算され、EX/MEMパイプライン・レジスタに保存される
5. そして、加算結果を使って、データ読み出し、MEM/WBパイプライン・レジスタに書き込む
6. 最後に、MEM/WBパイプライン・レジスタからデータを読み出して、レジスタに書き込む

実際に、この設計が上手く動かない！ロード命令には最後にレジスタへの書き込みが必要。しかし、ロード命令で実行する時に取り出した書き込みレジスタ番号は最後の書き込む時に失われてしまう。従って、最後の(6)書き込むは実行できない。

以下のように修正する

書き込みレジスタ番号をパイプライン・レジスタに次々と渡していく。WBステージで使えるようにする。

パイプライン化したデータパスを共有するためには，以降のステージで使用される命令要素を各パイプライン・レジスタに保存する必要がある

ストア命令のデータパス

1. プログラムカウントPCアドレスは4繰り上げられて、プログラムカウントにはき戻される。そして、次のクロック・サイクルに備えられる
2. IF/IDパイプライン・レジスタには命令メモリからのデータと繰り上げられたプログラムカウントの値が保存される。このプログラムカウントの値はロード命令で使わないが、beq命令などで使用するなので保存される
3. IF/IDパイプライン・レジスタからレジスタ番号二つと16ビットの即値フィールドが取り出される。16ビットの即値フィールドが符号拡張が行われて、読み出されたデータと共にID/EXパイプライン・レジスタに保存される
4. 次に、読み出されたデータと符号拡張された即値をALUで加算して、結果をEX/MEMパイプライン・レジスタに保存される。保存するデータもEX/MEMパイプライン・レジスタに保存される
5. そして、メモリにデータが書き込まれる
6. ストア命令ではWBステージが既に終わっているので、何も行われない

課題6.1

課題6.2

パイプラインの制御

単一サイクル方式と同様にパイプラインのデータパスに制御を追加するとどうなるでしょうか？

データパスに制御信号を追加するとこのようになる

各パイプライン・ステージで制御信号を設定する

• PCへの書き込み、およびパイプライン・レジスタへの書き込みは各クロック・サイクルで行われるとする
  • 制御信号なし

次に、今まで無視したパイプラインの問題点について見ていく

パイプライン・ハザード(Pipeline Hazards)

ハザード: パイプライン処理において次のクロック・サイクルで次の命令を実行できない事態

パイプライン・ハザードの分類

• 構造ハザード: ハードの制約で生じる
  • 同じハードに複数の命令から同時にアクセスできない
• データ・ハザード: 先行命令に後続の命令が依存している場合に生じる
  • 被ロード・データ・ハザード: 後続命令のデータが先行命令によってロードされるデータである場合
  • パイプライン・ストール（バブルともいわれる、命令処理の⼀時停止）させなければならない
• 制御ハザード（または分岐ハザード）: 後続命令の実行判断を先行命令に基づいて行う場合に生じる
  • 分岐命令
  • ストール、予測を行う

構造ハザードの例

データ・ハザード対策

フォワーディング(forwarding)又はバイパシング(bypassing)

• データ・ハザードを解消する方法の⼀つ
• レジスタ、メモリに書き込まれる前のデータを使う

フォワーディング/バイパシング: add命令の計算結果は3サイクル目で求められているため、パイプラインレジスタの値をsub命令が必要とするALUのバイパスすることで、sub命令をストールさせずに実行することができる。

フォワーディング・ユニットを追加したデータパスはこのようになる

EX/MEMパイプラインレジスタの値をALUの入力としてforwardするパスとMEM/WBパイプラインレジスタの値をALUの入力としてforwardするパスを追加されている

• フォワーディング・ユニットはforwardされた値を使うかどうかを切り替えるマルチプレクサを制御する

EXハザードの検出条件

MEMハザードの検出条件

forwardingできない場合

ストールの実装

IDステージ上の命令をストールさせる場合、PCレジスタとIF/IDパイプライン・レジスタを変更しないようにすればよい。

EXステージ以降で、何もしない命令nopを実行すればよい。

• ID/EXパイプライン・レジスタ中のEX, MEM, WB制御フィールドを全て0に変更する。このようにして、レジスタにもメモリにも何も書き込まない

制御ハザード対策

遅延分岐: 分岐直後の命令が常に実行され，分岐は1命令分遅れて実行する

もう一つの対策は静的分岐予測: 分岐が不成立と仮定して後続命令を実行

• 分岐が成立した場合、途中まで進めた命令を破棄
  • 分岐不成立の確率と進めた命令の破棄コスト次第

命令破棄の方法(フラッシュ): IF, ID,EXステージ上の制御値を0に変更

別の対策としては分岐判定を早める

分岐先アドレス計算と分岐判定の評価をIDステージに移すことができれば，分岐成立時のペナルティが現在フェッチ中の命令⼀つに減る。ただしIDステージにハードウェアの追加が必要。

• フォワーディング
• ハザード検出

最後の対策は動的分岐予測である

動的分岐予測: ハードウェアを追加して、実行時の情報を使用して分岐予測を行う。追加したハードウェアは分岐予測バッファと呼ばれている小さなメモリである

• 1ビット予測方式
  • 直近の結果を使って予測
  • 予測が1回ではなく2回誤ってしまう場合がある
• 2ビット予測方式
  • 予測が2回続けて外れたら予測を変更
  • 予測が外れるのは1回だけ

例外と割込み

例外: 制御の流れにおける予期せぬ変更、「割込み」とも言う

割込み: プロセッサの外部から発生した例外

例外が起きた時の対処方法

• 問題を起こしている例外のアドレスを例外プログラムカウンタ（Exception Program Counter: EPC）に退避させ、OSに制御を渡す
• 例外の原因をOSに伝える方法
  • ベクタ割込みを使う
  • 特定の状態レジスタ（Causeレジスタ、32bit）に例外の原因を記録(MIPSはこっち)
• 例外処理後
  • プログラムの実行中止（強制終了）
  • プログラムの実行継続

パイプライン方法における例外

例外を制御ハザードの⼀種として扱う

例外が発生すると、

• 続く命令をフラッシュ
• 新しいアドレスの命令をフェッチ

分岐と同じ仕組みが利用可能

例外の原因を常に正しく把握することは難しい

• どの命令で例外が発生したのか
• 複数の例外が発生した場合の対応

命令を通じた並列処理

命令レベル並列性(Instruction‐level parallelism : ILP): パイプライン処理は、命令間の潜在的な並列性を利用している

ILPを高める方法：

• パイプラインの段数を増やす
  • スーパーパイプライン
• ハードウェアの構成要素を多重化して各パイプライン・ステージのそれぞれで複数命令が実行できるようにする
  • スーパースカラ
  • VLIW（Very Long Instruction Word）

スーパーパイプライン

スーパーパイプライン: パイプラインの処理の分割単位をさらに細分化してILPを上げる

• メリット
  • より高い周波数で動作させることができる
• デメリット
  • パイプラインレジスタの数が増加するため、予測分岐が外れると多くの命令を破棄しなければならない

スーパースカラ

スーパースカラ(superscalar): ハードウェアを追加し、依存関係のない命令を同時に複数命令を実行することでILPを上げる

動的パイプライン・スケジューリングが取り入れられている（実行順序を再構成してできるだけストールを避ける技術）

• メリット
  • 1クロック・サイクルで複数命令を同時に実行できる
• デメリット
  • 実行可能な命令数が増えると依存関係の計算コストが増大する

課題6.3

以20条命令为例：

課題6.4

$1\mu s = 1000ns$ 假设不发生flush，即不会有被无效化的指令，分别计算不同pipeline段数在1000ns内执行的指令数：

$$\begin{aligned} n_1 &= \frac{1000}{12} \simeq 83 \\\\ n_2 &= \frac{1000}{8} = 125 \end{aligned}$$

即不发生flush情况下，3段的pipeline比5段的pipeline多执行了 $125 - 83 = 42$ 条指令。再考虑有无效化的情况，3段的pipeline会一次无效3个指令，而5段的pipeline会一次无效5个指令。1000ns内发生 $\frac{42}{(5 - 3)} = 21$ 回flush时，两个处理器所执行的时间几乎相等

メモリテクノロジ(Memory Hierarchy)

理想を言えば，無限の容量を備え，いかなる語にも瞬時にアクセスできるような記憶装置が欲しい．

しかし，現実には記憶装置をいくつかの階層に分けて構成せざるを得ない．

記憶階層

記憶階層とは，下の階層に行くほど容量が大きくなるが，アクセスにはより時間がかかるような仕組みである．

記憶階層の利用

記憶階層は「局所性の法則」に基づき構成される

局所性の法則：

• 時間的局所性: ある項目が参照された場合、その項目がまもなく再び参照される確率が高い
• 空間的局所性: ある項目が参照された場合、その近くにある項目がまもなく再び参照される確率が高い

記憶階層の構造

SRAMとDRAM

SSDとHDD

キャッシュ(Cache)

キャッシュ(Cache): プロセッサと主記憶の間に挿入された記憶階層

ダイレクト・マップ方式

ブロック数 = 8の場合におけるキャッシュの推移

アドレスとキャッシュインデックスの対応は以下の図に示す

キャッシュに必要な総ビット数

• $32 \text{bit}$ のバイト・アドレス
• ダイレクト・マップ方式のキャッシュ
• キャッシュ容量 = $2^n$ ブロック ($n \text{bit}$ をインデックスに使用)
• ブロック・サイズ = $2^m$語 (= $2^{m+2} \text{Byte} = 2^{m+5} \text{bit} = 2^m \times 32 \text{bit}$)
• タグ・フィールド長 = $32 - (n + m + 2)$
• 有効フィールドに $1 \text{bit}$ が必要

キャッシュの総ビット数は

$$2^n \times (\text{ブロック・サイズ} + \text{タグ長} + \text{有効フィールド長})$$

となり

$$2^n \times (2^m \times 32 + (32 - n - m - 2) + 1)$$

キャッシュ・ミスの取り扱い

制御ユニットはキャッシュ・ミスを検出した場合、パイプラインをストールさせ、別の制御ユニットを用いて下位のキャッシュからデータを持ってこなければならない

命令呼び出し時のキャッシュ・ミスの対応:

1. 元のPC値をメモリに送る
2. 主記憶から読み出しを行うよう指示し、その完了を待つ
3. キャッシュに該当するブロックに書き込みを行う
   1. 主記憶から読み出したデータ $\rightarrow$ キャッシュのデータ部分
   2. アドレスの上位ビット $\rightarrow$ タグ・フィールド
   3. 有効ビット $\rightarrow$ 1(ON)を設定
4. 命令実行を最初のステップから再開する

書き込みの取り扱い

キャッシュと主記憶の「⼀貫性（consistency)」が必要

• ライト・スルー方式: データを書き込む際、キャッシュと主記憶の両方に書き込むようにする方式
  • ライト・バッファ: 主記憶に対する書き込み待ちのデータを蓄えておく場所
• ライト・バック方式: データを書き込む際、キャッシュの対応するブロックのみに書きこみ、修正されたブロックが置き換え対象になった時に主記憶に書き込む

課題7.1

キャッシュ性能の測定

平均メモリ・アクセス時間(AMAT)

• AMAT = Time for a hit + Miss rate $\times$ Miss penalty = $1 + 0.05 \times 20$

キャッシュサイズを増やすとミス率が下がる(ヒット率を上がる)及びヒット時間が増える(検索に時間がかかる)のため, ヒット時間増大の影響がヒット率を上回るとプロセッサの性能低下につながる

ブロック配置の方法

ヒット率を下げるためには, キャッシュサイズを大きくしたい, でもヒット時間大きくしたくない. ヒット時間を抑えつつキャッシュサイズを増やすにはどのようなキャッシュを配置すれば良いでしょうか?

• ダイレクト・マップ方式: 主記憶のブロックが配置されるキャッシュ内のロケーションは一意に決まる
• セット・アソシアティブ方式: 主記憶のブロックが配置されるセット番号は一意に決まるが, セット中の任意のロケーションに配置される
• フル・アソシアティブ方式: 主記憶のブロックが配置されるキャッシュ中の任意のロケーションに配置される

セット・アソシアティブ方式

主記憶のブロックを配置可能なセットが $n$ 個あり、各セット $m$ 個のブロックからなるセット・アソシアティブ方式をmウェイ・セット・アソシアティブ方式という

• 2ウェイ・セット・アソシアティブ方式: 連想度2, セット数4
• 4ウェイ・セット・アソシアティブ方式: 連想度4, セット数2

以下は4セット・アソシアティブ方式実装例。連想度4, セット数256からなるキャッシュになっている。セット番号は0-255なので、8bitで表現可能。

メモリアドレスの2-9bit目までの8bitをインデックスとして、10-31bit目までの22bitはタグになる。

• アドレス構成
  • タグ
  • インデックス （セットの選択）
  • ブロック内オフセット
• ハードウェアのコスト
  • 比較器とマルチプレクサ
  • 各ブロックにタグ
• 検索コスト
  • 該当するセットを選択
  • 選択したセットの中から該当タグの検索
• 置き換えブロックの選択
  • LRU(Least recently used)法: 使用されずにいた時間が最も長いブロックを置き換える

マルチ・レベル・キャッシュ

性能向上のためにプロセッサと主記憶の間に複数レベルのキャッシュを追加

設計指針:

• １次(L1)キャッシュ
  • ヒット時間を最小化
    • クロック・サイクルを短縮
      • キャッシュ容量、ブロックサイズを小さくする
• ２次(L2)キャッシュ
  • ミス率を削減
    • 主記憶アクセス時の長いミスペナルティを削減
      • キャッシュ容量・ブロックサイズ大きくする
      • 連想度も高める

仮想記憶(Virtual memory)

仮想記憶: 2次記憶（SSD、磁気ディスク）に対して，主記憶にキャッシュの役割を持たせる仕組み

仮想記憶の目的

1. 複数プログラム間でメモリを効率よく共有する
2. 主記憶容量の限界に対処するプログラム上の負荷を軽減する

仮想記憶の機能

1. 各プログラム独⾃のアドレス空間と物理アドレス空間の変換, プログラム間のアドレス空間の保護
2. 主記憶（物理メモリ）と２次記憶とのやり取りの⾃動化

必要なデータを(高速な)主記憶に置き、当面必要ないデータを(低速な)2次記憶に置く

仮想記憶の仕組み

• 各プロセスに対して連続な仮想アドレスが与えられ，アドレス変換(アドレス・マッピング)によって物理アドレスに変換される
• アドレス変換はページ単位で行われる（キャッシュのブロックに相当）
• アクセスするデータが主記憶中にない場合、ページ・フォールトが発生する（キャッシュのミスに相当）

仮想アドレスと物理アドレスの対応

• ページサイズ：ページ内オフセットで決まる$(2^{12} = 4\text{KiB})$
• 物理ページ数：物理ページ番号からきまる$(2^{18})$
  • 物理アドレスの最大容量は $2^{18+12} = 1\text{GiB}$ （仮想アドレス空間 $2^2\text{GiB} = 4\text{GiB}$）

仮想記憶システムの設計

• ページフォールトの発生低減
  • ページ配置はフル・アソシアティブ方式
  • ページ・テーブルを用いた検索
• ページ・フォールト
  • ソフトウェア(OS)で例外処理する
    • あらかじめディスク上にプロセスの全仮想記憶空間を予約（スワップ領域）
    • あらかじめ各仮想ページがどの物理ページに割り当てられているかを記録するデータ構造を作成
      • 割り当てる物理メモリがない時は置き換えるページの選択を行う
        • 参照ビット（使用ビット）に基づくLRU
• ディスクへの書き込み回数削減
  • ライト・バック方式
  • ページ・テーブルにダーティ・ビットと付加
    • ダーティ・ビットが付加されたページだけ書き戻す

アドレス変換バッファ(TLB)

• ページ・テーブル（フル・アソシアティブ方式）に対するキャッシュ
• 最近使用されたアドレスの対応関係を記録する

記憶階層の全体的な動作

記憶階層の3要素(TLB，ページテーブル，キャッシュ)の相互作用は次のようになる

課題7.2

• address长32bit
• data容量：512B
• block size：32B

1. block size = 32B = $2^{m+2} = 2^5$ B, $\log_2 32 = 5$ offset(2bit-offset + 3block offset)
2. block数 = data容量（缓存大小） / block size = $512 / 32 = 2^4 = 16$ 个block
3. 因为是2-way set associaltive方式，平均1-way有 $16 / 2 = 8 = 2^3$ 个block，即3 bits来表示该缓存的index
4. address = tag + index + offset = tag + index + (bit-offset + block offset)可知等下的24bits作为tag

課題7.3

• data容量：32KB = $32 * 2^{10}$B
• block size：32B

1. 由 block size = 32B = $2^{m+2} = 2^5$ B, 计算 $\log_2 32 = 5$ offset(2bit-offset + 3block offset)
2. 计算block数：data容量（缓存大小） / block size = $32KB / 32 = 2^{10}$ 个block
3. 因为是2-way set associaltive方式，平均1-way有 $2^{10} / 2 = 2^9$ 个block，即9 bits来表示该缓存的index
4. address = tag + index + offset = tag + index + (bit-offset + block offset)可知等下的18bits作为tag

課題7.4

• Total CPI = 1 Primary stalls per instruction + Secondary stalls per instruction

まとめ

• 計算機の基本構造
• コンピュータの言葉
  • 命令セットアーキテクチャ
  • ハードウェアを動作させるための命令、命令セットおよびコンピュータにおける算術演算について学ぶ
• ソフトウェア
  • プログラムの翻訳
  • 高水準プログラム言語がどのようにして実行プログラムへ変換されるかを学ぶ
• プロセッサ
  • データパス
  • 例外と割り込み
  • パイプライン
  • 並列処理
  • プロセッサの実装で使われる基本的な原理と技法について学ぶ
• メモリ
  • メモリ・テクノロジ
  • キャッシュと仮想記憶
  • メモリの階層構造、高速化技法について学ぶ
• 性能
  • コンピュータの性能評価
  • コンピュータの性能を判定する各種の方法について学ぶ
• 仮想化
  • 仮想化技術
  • 仮想化の実現で用いられる原理と技法について学ぶ

参考文献

• Computer Organization and Design: The Hardware/Software Interface