パタヘネ
https://m.media-amazon.com/images/I/61vXdBJ3-6L.jpg
マック安い
1章(2020/05/11)
常識・概要・チュートリアル
2章(2020/05/12)
3つの設計原則
単純性は規則性につながる
例: フォーマットを統一する(r-format, i, j)
小さければ小さいほど高速になる
優れた設計には適度な妥協が必要である p167
例: MIPSの命令長はすべて32bitに妥協する
MIPS
32bit == 1word
レジスタ数: 32個
lw <regster>, immediatly(<regster>)
lw $s1, 20($s2)
メモリのアドレスは8bitごとに振られているので、レジスタのサイズがwordなので4アドレスごとに計算する
https://gyazo.com/7ffd8467a88ecc9ba9a1e310ae5c31b7
op：命令の基本操作．従来から命令操作コード（opcode，オペコード）
rs：第１のソース・オペランドのレジスタ．
rt：第２のソース・オペランドのレジスタ
rd：デスティネーション・オペランドのレジスタ，つまり結果を収める先．
shamt：シフト量
funct：機能．命令操作フィールドのバリエーションを表す (機能コード)
https://gyazo.com/98a8f4ba91a185d748d9bd953fda810f
https://gyazo.com/4f4ca2b45c6ea1ce2af690b7ceb77e3c
lwなどのアドレスや即値指定したい命令のためのフォーマット
2.8 コンピュータ・ハードウェア内の手続のサポート (2020/5/13)
⼿続き呼出しのために使われるレジスタ
$a0-$a3:４本の引数レジスタ．パラメータを渡すために使⽤．必要に応じて保存
$v0-$v1:２本の値レジスタ．結果の値を返すために使⽤．
$ra: １本の戻りアドレス・レジスタ．制御を元に戻すために使⽤．必要に応じて保存
$t0-$t9: 非呼び出し側でガンガン上書きして問題ない
$s0-$s7: 被呼び出し側で使う場合対比する必要がある
jal [手続きのアドレス]: 実質関数呼び出し
PC: プログラムカウンタ
$sp: スタックポインタ $fp: フレームの先頭(ベースポインタ)
2.9 人との情報交換 (2020/5/13)
文字コードの話
ascii
2.10 32ビットの即値およびアドレスに対するMIPSのアドレシング方式(2020/5/14)
pc相対アドレッシング
条件分岐命令は即値として$ 2^{16}bitを指定できるので、PCレジスタ$ \pm 2^{15}(単位はword)の範囲でjmpできる
jmp, bne で指定する即値は word単位で計算するので $ 2^{18} = \pm 32 \rm K \mathrm{word}
$ 0000 0000_{16} = SLL $0, $0, 0 = 副作用ないので慣例的に noop として扱われる
Note: The encoding for a NOOP represents the instruction SLL $0, $0, 0 which has no side effects. In fact, nearly every instruction that has $0 as its destination register will have no side effect and can thus be considered a NOOP instruction.
https://gyazo.com/5f77a42ee7ed15bfc44caada75101d90
2.11 並列処理と命令: 同期(2020/5/14
ll(load linked) と sc(store conditional) が用意されている
単一プロセッサでも割り込みがないことを保証するために使用するのは有用
2.16 AMDv7(32bit)
divがない
2.17 Intel x86
命令が時代に合わせてたくさん追加された
互換性
歴史、命令セット
MIPSとかと違って命令長がバラバラ
2.18 ARMv8（64ビット）の命令
16bitなのはお前だけ
MOSek 6502はゴミ箱行きの運命
ARMv7とARMv8の主な類似点は、名称となった
3章 コンピュータにおける算術演算
3.2 加算と減算(2020/5/14)
オーバーフロー -> 例外が発生 -> 例外PC(EPC) にアドレスを保存できる(mfc0命令)
下記の状況に対応するために、OS用に$k0と$k1 が予約されている
code:sample.asm
// in error handling
add $s0, $epc, $zero
// すべてのレジスタを戻すとs0が上書きされてしまう...
jr $s0
3.3 乗算
大量のハードウェア資源を利用し、$ \log_2{32}のオーダーで計算可能。
Hi: 上位32bit (mfhi命令)
Lo: 下位32bit (mflo命令)
で取り出すことができる。オーバフローの有無は検査されない。
3.4 除算(2020/5/15)
オーバフローは無視。
div(divu)命令はレジスタを3つ指定することができ、hi, loレジスタから自動的にmflo, mfhi命令で結果が保存される。
結果を予想することにより、高速化を図っている。
3.5 浮動小数点演算(2020/5/15)
下駄履き: float => +127
$ (-1)^S * (1 + \rm{仮数}) * 2^{\rm{指数} - 127}
4章 プロセッサ
一番単純でコアなデータパス
https://gyazo.com/53eb8d2139cd99457ba6e14d30678634
4.4 単純な実装方式(2020/5/19)
R format:のとき(機能フィールドが使用される)
主制御ユニット -> ALUop 2bit + funct 6bit -> ALU制御入力 4bit
ロード命令の場合 は，ビット20-16（rt）に保持される．Ｒ形式命令の場合はビット15-11（rd）に保持 される．したがって，書き込み先のレジスタ番号を⽰すために使⽤する命令フィー ルドの選択⽤に，マルチプレクサが必要となる．
https://gyazo.com/0c54eae2eb98db9dbeea42312effae6c
命令のデータパス制御
https://gyazo.com/ea1557ddc562a23b08b052c0389cdbbc
jump命令の追加
https://gyazo.com/e109affb2ab0a9cfe8c6aff15611e22f
4.5 パイプライン処理(2020/5/20)
nステージなら最大n倍高速化できる
1. メモリから命令をフェッチ
2. 命令のデコードとレジスタの読み出しを並列に行う。
3. 命令操作の実⾏またはアドレスの⽣成を⾏う．
4. データ・メモリ中のオペランドにアクセスする．
5. 結果をレジスタに書き込む．
- 最も遅い命令/ステージを基準
200ps / 100ps / 200ps / 200ps / 100ps
single: 800ps ( = lw)
pipeline: 200ps
理想的な条件下のパイプライン方式マシンの命令実行間隔
$ パイプライン処理における命令の実行間隔 = 非パイプライン処理における命令の実行間隔 / パイプラインのステージ数
パイプライン・ハザード
待たなければいけない時がある -> ストール
1ステージ分ストール -> バブル
構造ハザード: メモリの同時読み書きなど、物理的な制約
code:"例
<hazard>
1: if -> id -> ex -> mem -> wb
4: if -> id ->
データハザード
連続した命令で直前の計算結果を使用する場合など、直前の命令に依存しているとき: add -> sub など
→ フォワーディング: 演算結果を直接つなぐ
-> 被ロード・データ・ハザード
後続の命令が直前のロード命令で読み込まれるデータを欲する場合、データがまだ利用可能でないことが原因でハザードする。コンパイラでハザードが発生しないような命令を作ることで回避可能なものもある
制御ハザード
→ 分岐予想
-> 遅延判定(Out of Order Execution): 分岐に影響しない命令を行って時間稼ぎ
4.6 データパスのパイプライン化と制御(2020/5/21)
命令を5つのステージに分ける
https://gyazo.com/c6b0fdd38bc4ee591e6d40bd361c21f0
各パイプライン処理で制御線を操作する
https://gyazo.com/2cf2da0eb6bf51c6b908d10175c57296
4.7 データハザード: フォワーディングとストール
パイプラインレジスタとフィールドで依存関係を表す
1a. EX/MEM.RegisterRd = ID/EX.RegisterRs
1b. EX/MEM.RegisterRd = ID/EX.RegisterRt
2a. MEM/WB.RegisterRd = ID/EX.RegisterRs
2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
code:例
// <op> <rd> <rs> <rt>
sub $2, $1, $3 // if | reg:rd | ...
* ^^^ ^^^^^^
* data hazard!!
*
and $12, $2, $5 // if | reg:rs | ...
^^^ ^^^^^^
data hazard: EX/MEM.RegisterRd = ID/EX.RegisterRs = $2
4.8 制御ハザード(2020/5/22)
= 分岐ハザード
最適化手法
分岐が不成立と仮定
分岐による遅延の削減(早い段階で分岐判断する) → フラッシュする命令数を最小化
https://gyazo.com/5f06e01bc9ba106a31418b549d57024d
4.9 例外
例外と割り込みの意味は似ているが背景によって異なる
EPC(Exception Program Counter)にエラーが発生したアドレスを保存
Causeレジスタ: 例外の原因を保存
原因に基づいて制御を移すアドレスを指定する
https://gyazo.com/ee1eb8071181962fdc76e9a6ac3d09d3
4.10 命令を通じた並列処理
リオーダバッファとリザベーションステーションによるレジスタリネーミング
5 容量と速度の両立 : 記憶階層の利用
5.1 はじめに(2020/05/23)
時間的局所性: まもなく参照される確率が高い
空間的局所性: その近くにあるものが参照される確率が高い
ブロック: レベルの異なる記憶階層で取り交わすデータ量の単位
ヒット時間: 上位レベルのアクセスにかかる時間
ミス・ペナルティ: 下位レベルのブロックをプロセッサに取り込むのにかかる時間
5.2 メモリ・テクノロジ
5.3 キャッシュの基礎
ダイレクトマップ方式: ブロックのアドレス % キャッシュのブロック数
タグフィールドとキャッシュインデックスで一意にメモリアドレスが定まる
タグフィールド長
[20: tag, 10: index, 2: byte offset = 00]
- キャッシュが $ 2^n ブロック -> nビットをインデックスに
- ブロックサイズ: $ 2^m word
$ 32 - (n + m + 2)
ブロックサイズ: 16 byte(4 word), 64ブロックのキャッシュで アドレスが 1200 のwordのブロック番号は?
1200 >> 2(word) >> 2(byte offset) = 75th より 75 % 64 = 11
書き込みの取り扱い
- ライトスルー: キャッシュとメモリの両方に反映
-> ライトバッファ: メモリに書き込みするデータを貯めておく
- ライトバック: キャッシュが上書きされそうな時にメモリに反映
- ライトアロケート: ライトスルーでキャッシュミス時メモリからブロックに割当
- ノーライトアロケート: 割り当てない
https://gyazo.com/ac7b316d1b515f6020dc485c1784eda2
ブロックが大きい -> ミスが少ない
ブロックが小さい -> ミスペナルティが小さい
→ 主記憶のバンド幅を大きくしよう
5.4 キャッシュの性能の測定と改善(2020/5/24)
- ダイレクトマップ方式(=1-way) -> アドレスごとに場所固定
- n-way セットアソシエイティブ方式 -> n個ごとのブロックで管理
- フルアソシエイティブ方式(=N-way) -> 完全自由
連想度(n)を増やせばキャッシュミス率は下がるがヒット時間が増大
5.5 信頼性の高い記憶階層
5.6 仮想マシン
プロセッサの仮想化にかかるコストは負荷の性質に左右される．プロセッサば かりを使⽤するユーザー・レベルのプログラムの場合，仮想化のオーバヘッドはかからな い．理由は，OSを呼出すことはめったにないからである．したがって，すべてが本来の速 度で実⾏される．⼊出⼒が⾮常に多い負荷は頻繁にOSの介⼊が必要で，多くのシステム・ コールや特権命令が実⾏されるため，仮想化のオーバヘッドが⾼くなる．p704
5.7 仮想記憶(2020/5/28)
- ページ方式
- セグメント方式
メモリ上に仮想ページ番号と物理アドレスを対応付けた表を保存しておく。
このページ・テーブルにはすべての対応関係が登録されている。
page table レジスタはページテーブルのメモリ上の始点を指すレジスタ
ダーティ
メモリからディスク上のページを更新する必要があるページ
TLB
アドレス変換の計算をキャッシュするCPUのキャッシュ
TLB見てアドレス計算済みか？
ページテーブル見て物理かディスクか
物理ならキャッシュあるか？
ユーザープロセスとカーネルプロセス
コンテキストスイッチ
5.8 記憶階層間に共通する概念(2020/06/03)
1way -> 2way のミス率の改善が顕著
三つのC
- 初期参照ミス
- 容量性ミス
- 競合性ミス
5.9 有限状態機械を用いた単純なキャッシュの制御
5.10 並列処理と記憶階層:キャッシュ・コヒーレンス
- コヒーレンス性:
- 一貫性(consitency)
5.11 並列処理と記憶階層:RAID
6 クライアントからクラウドまでの並列 プロセッサ
6.1 はじめに 06/21
ハードウェア: (直列, 並列) X ソフトウェア(逐次, 同時並行)
6.2 並列処理プログラム作成の困難さ
- Amdahlの法則: $ 改善後 = \frac{改善の影響}{改善度} + 改善できない所
- 強いスケーリング: 問題の規模を固定したときの速度向上
- 弱いー: コア数と規模を増やして速度向上
6.3 SIMD
SSE, AVX命令にあたる
6.4 ハードウェア・マルチスレッディング(2020/06/22)
複数のスレッドが単一プロセッサを共有(ハードウェアがスレッドを切り替え)
細粒度マルチスレッディング(fine-grained multithreading)
1命令ごとにスレッドを切り替え、交互に実行する
短時間・長時間ストールの損失を隠せる
粗粒度マルチスレッディング(coarse-grained multithreading)
長時間ストールの時に切り替え
同時マルチスレッディング(simulataneous multithreading)
複数命令発行・動的スケジューリング・パイプライン方式
単一コアのなかにスーパースカラが展開されている
6.5 マルチコアをはじめとする共有記憶型マルチプロセッサ
共有記憶マルチプロセッサ: アドレス空間を共有
同期が必要 -> ロック
OpenMPとかのAPIを使用することができる
6.6 グラフィックス処理ユニットの概要(2020/06/23)
https://gyazo.com/b390a09d352722f47d8138d82f9f157b
6.7 クラスタ、ウェアハウス・スケール・コンピュータおよびその他のメッセージ交換型マルチプロセッサ
6.8 マルチプロセッサ・ネットワーク・トポロジの概要
ノードのつなぎ方
6.10 マルチプロセッサのベンチマークおよび性能モデル(2020/06/24)
付録C グラフィックスとGPUコンピューティング
C.1 はじめに(2020/06/30)
VGA(video graphics array)
初期メモリコントローラ and display generator
1997 3Dがいい感じになる
2000 強くなったのでGPUに名前変更
C.2 GPUシステムのアーキテクチャ
C.3 GPUのプログラミング
C.4 マルチスレッド型マルチプロセッサのアーキテクチャ
C.5 並列記憶システム