あらいげた

計算機構成論ノート

中途半端なんだけど他の人もうpして補完してくれることを期待。

たぶん第3週の途中辺りから書いてます。それまでは紙に書いてました。寝てたりボーっとしたりしてて穴だらけなので、授業で扱った項目の半分程度しか入ってないものと思ってください。

途中の「→動画」っていうのはUstで録画した動画のことです。

【ハードワイヤード制御】

CPUのデータパスを組み合わせ論理回路とステートマシンの組み合わせで操作(これは意味なしの定義)

例
        - 30入力 40出力回路
        - ステート → 命令実行のフェーズ、命令のOPCODEなど

        - 論理合成の進歩により実現が容易になりつつある

        →図

【マイクロプログラム方式の変形(1)】

水平マイクロプログラム方式の命令幅圧縮
        マイクロ命令のフィールド分割
                - 排他的動作を用い圧縮(Output Enable, Write Enableなど)
                - 可変フィールド分割方式
                - 実際に使用されるマイクロ語の組み合わせの最適化コーディング
                - マイクロ命令ステップ数を最小にする最適化
                       *これらは共にNP困難問題*
                
                - 垂直マイクロプログラムとの差は曖昧

        →図

【IBM360マイクロアーキテクチャ】

ファミリーアーキテクチャのマイクロプログラムによる実現
メインフレーム(CISC)の典型的設計手法

        マイクロプログラムのビットごとの仕様などの図

【マイクロプログラム方式の変形(2)】

垂直マイクロプログラム方式
        - マイクロ命令幅の更なる縮小(横のものを縦に)
                最適化のための評価関数には疑問
        - HP2100に見る垂直マイクロプログラム
        - HP2100 → 16bitミニコンピュータ
        - 垂直マイクロプログラムが廃れた理由
                ↓
         IPCの著しい低下

        垂直マイクロプログラム(メモリが縦長)のほうが消費電力が少ない
        超低消費電力を狙う場合には有効

【マイクロプログラム方式の変形(3)】

並列マイクロプログラム(垂直、水平とも)
        京都大学
        
        とばされたー

【ユニバーサルインタプリター】

プログラミング言語に適応したマイクロプログラミング
B1700の実例
        - ビットアドレッシング能力を持つ万能マイクロエンジン
        - 残念ながら、普及せず
        - 最近、万能インタープリタが再び脚光
        
        (- Huffmanコーディングで可変長命令を使用)

【ユニバーサルインタプリタの最近の話題】

マイクロプログラムによる適応型中間言語方式
バイトコードのRISC命令による適応型中間言語方式
遠隔実行、協調動作
機種独立性の確保と、セキュリティの確保
        「ユーザにこの操作は許すがこれは許さない」ということができない
        すべての実行を許してしまう

【割り込み機構の目的】

3個の異なる目的
        1. アーキテクチャの拡張
                - 機能のソフトウェア・ハードウェア協調による実現
                - 割り込み処理時間による速度低下 → 割り込み処理の高速化機構
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                - 例: システムコール、浮動小数点例外、ページフォルト、ブレークポイント、トレース
        2. 保護機構の実現
                - 特権レベルの乱用に対する保護
                - 命令実行と平行したハードウェアによる違反検出
                - 精密な設計によるセキュリティ・ホールの回避 → メモリ保護機構
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                - 例: MMUトラップ、特権命令実行例外、システムコール
        3. 非同期事象との同期
                - ハードウェアによるサブルーチン呼び出し
                - 実時間制約を満たすための優先度処理の実現 → 優先度機構
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                - 例: 外部割込み、タイマー、リセット、マシンチェック

【割り込みの実現】

割り込みの要因
        - マシンチェック
                電源異常、メモリエラー、演算エラー
        - リセット(ハードウェアリセット)
        - 外部(I/O)割り込み → 1からN要因まで
        - タイマー(2本程度:ユーザ使用用と時間課金用など)
        - バスエラー(バスのタイムアウト)
        
        - ページ・フォルト(TLBミス)
        - MMU割り込み
                メモリ保護エラー、ページ変換エラー、page aliasing検出、ミスアラインメント
        - 未定義命令の実行(実装されてない命令をソフトウェアエミュレーションする上で重要)
        - 命令特権レベルエラー(ユーザーモードでの特権命令実行)

        - 浮動小数点演算トラップ
                オーバーフロー、アンダーフロー、0 div、NaN等
        - 整数演算トラップ
                オーバーフロー、0 div、アドレス計算エラー等
        
        - ブレークポイント
        - トレース命令の実行
        - システムコール(OSの呼び出し)

【命令実行と割り込みタイミング】

1. 完了
        割り込み要因発生時に実行している命令の実行が完了(メモリ、レジスタなどの書き込みが完了)した後、
        次命令実行が開始される前に割り込みが発生する。割り込みからの復帰後は、次命令から実行を再開する
        - 外部割込み、システムコール等
2. 中止
        割り込み要因発生時に実行している命令の実行を中止し、当該命令実行が開始される直前の状態で
        割り込みが発生する。割り込みからの復帰後は、当該命令から実行を再開する
        - ページフォルト、MMUトラップ、浮動小数点例外、整数演算例外、ブレークポイント、トレース等
3. 中断
        割り込み要因が発生すると、直ちに命令実行を中断し、割り込み動作を開始する。
        割り込みから、当該命令部分に復帰しないが、する場合には当該命令または次命令から命令実行を再開する
        - マシンチェック

【同期/非同期】

同期割り込み
      *1セット完了してから
[FDREW][FDREW]
         ↑  → [割り込みシーケンス][割り込みハンドラ]
   外部割込み                                         → [FDREW][FDREW][FDREW]
                                                          復帰

非同期割り込み
      *中止
[FDREW][F]
        ↓ → [割り込みシーケンス][割り込みハンドラ]
    命令                                           → [FDREW][FDREW][FDREW]
  ページフォールト                                      再実行

可変長命令を使っているとどこまで巻き戻せばいいのか分からなかったりする

【割り込み優先度】

優先度/割り込みマスクの必然性
        - 割り込み処理の相互排他
        - 不必要な割り込みの抑制(特に算術以外)
        - リアルタイム性の確保
        - デッドロックの抑止
        - Unmaskable Interrupt は最低限必要(リセット等)

(参考)リアルタイムスケジューリング
        - 静的スケジューリング(Rate Monotonic Scheduling)
                処理の周期の短いものに高い優先度)
        - 動的? スライドすなー!!

【割り込みシーケンス】

割り込みシーケンス → 割り込み要因発生から、ハンドラまで
        1. 割り込み要因の検出 → Σ INT_i & MASK_i
        2. 実行中命令の完了、中断または中止を待つ
        3. 割り込み要因などに基づき割り込みベクトルを作成
                - 割り込みベクトル → 割り込みハンドラの実行開始番地
        4. 実行中命令の情報(PC, PSW等)を退避・格納
        5. (必要ならば)割り込み要因情報を退避・格納
        6. プロセッサモードを特権モードに変える、新しいPSWのセット
        7. 優先度の低い割り込みの禁止(すべてを禁止して、ソフトウェアでマスクを設定する場合もある)
        8. 割り込みベクトルへ分岐し、ハンドラを起動

        上記処理を、ハードウェアまたはマイクロプログラムで実現

【割り込みハンドラと割り込みからの復帰】

割り込みハンドラ
        - 割り込みマスクの設定
        - プロセッサ状態のソフトウェアによる退避(レジスタ、システムレジスタ)
        - 割り込み要因の詳細な解析(ひとつの要因を複数原因で共有)
        - デバイスなど動作の起動
        - OSへの要求キュー操作など必要なソフトウェア実行
        - 割り込み復帰の準備(PCの操作、退避されたPWSの変更)、プロセッサ状態の回復
        - 割り込みから復帰命令実行

復帰命令
        - 元の命令実行のための状態(PC、PWS)復帰
        - 特権モードを元に戻す
        - 実行再開

【割り込み実現の困難さ】

可変長命令
        - 命令境界のソフトウェアによる検出(特に巻き戻し)
        - 実行途中での割り込み(メモリへの変更途中など)
        - 非常に長い命令中でのページフォルト(リアルタイム性の確保)

状態の退避・格納と復帰の命令オーバーヘッド
        - レジスタ、PSW
        - 仮想記憶実現に必要な情報
        - システムレジスタ
        (映像や音を扱うときは割り込みで止まったりするのは深刻な問題らしい)

セキュリティの確保
        - 保護システム設計との関連
                - Capability方式、キー方式、リング、ドメイン…
                - メモリアクセス保護、通信保護、プロセス保護(Call/Ret)
        - 特権命令設計
        - 現在のCPUセキュリティは設計の完全性に依存している
                例→CPUを止めるユーザプログラム

【割り込みへのアーキテクチャ支援】

命令長
        - 固定長命令、固定数オペランドとしてすべてを簡略化
        - ロード・ストア命令の分離による要因の簡略化

状態の退避・格納と復帰の命令オーバーヘッド
        - CPUの複数コンテクスト(レジスタセット、PSW)
        - 複数プロセス混在を許す仮想記憶方式(プロセスID)
        - SMT(Simulataneous Multi-Threading)

セキュリティの確保
        - メモリ保護に帰着させる保護方式
        - 仮想計算機システム

        キャッシュメモリ、パイプライン方式はより大きな負のインパクト
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

【第6週】

・計算機の高速化
・パイプラインアーキテクチャ
        ・基本構成
        ・パイプラインハザード(基礎編)

【計算の高速化】
積極的な高速化
        - 本質的な計算家庭を高速化
                - 浮動小数点演算実行数の増加
                - 比較、移動操作実行数の増加
                - 演算操作実行数 = クロック周波数×同時実行の演算数

消極的な高速化
        - 計算に伴うオーバーヘッドの削減
                - プロセッサの遊び時間の減少
                        - パイプラインのバブル
                        - メモリアクセスの待ち時間
                - 非本質的命令実行数の減少
                - OSの実行命令数の減少
                - ライブラリの実効命令数の減少
                - I/O待ち時間の減少

【CPUの高速化のスペクトル(1)】

計算原理の高速化
        フォンノイマン計算機、量子計算、DNAコンピューティング、生物コンピューティング
        ニューラルネットワーク
物理原理の高速化
        Si, GaAs, HEMT, JJ, 単電子素子,磁束量子素子
素子の高速化(クロックの高速化)
        - 素子の縮小(電子走行距離の短縮、容量の減少)→0.005μ?
        - SOI, 銅配線、Low-k

【CPUの高速化のスペクトル(2)】

多量の素子の利用 → 局所並列性の利用、投機的実行
        - パイプライン・アーキテクチャ、ベクトルアーキテクチャ
        - スーパースカラ・アーキテクチャ、VLIW
        - 分岐予測、データ値予測、スレッドレベル予測

メモリアクセスの高速化
        - キャッシュメモリ
        - 高速メインメモリ

並列性の利用
        - SMP(真の共有メモリ並列アーキテクチャ)
        - ~~~~
        - ~~~~あー

【パイプラインアーキテクチャ】

CPU基本アーキテクチャの問題点
        - 実行の5フェーズが逐次的に解釈実行される
        - CPU上の資源の一部だけが、一時店で動作
        - CPI(1命令あたりのクロック数の増大)なんちゃらかんりゃら

【CPUのパイプライン設計】






-------------------------


6/26

【動的スケジューリング】

- In order issue / In order completion         +
- In order issue / Out of order completion     +- Static Scheduling
- Out of order issue / Out of order completion -- Dynamic Scheduling

動的スケジューリング
- 逐次実行列に、広がりを持つ命令ウィンドウを設定
- 命令ウィンドウ内の実行順序を動的に決定し性能を最大化する


【動的命令と静的命令】
静的命令
- プログラムのテキスト上での命令、命令実行順
- プログラマ、コンパイラからは静的命令だけが見える。

動的命令
- CPU上で実行される命令、命令実行順
- CPUの高速化は動的命令の高速化によってなされる

【動的スケジューリングの理想形態】

ここでの命令は実行された命令→動的命令をさす

命令ウィンドウ投入時点において
- 命令実行が完了している命令からの
 レジスタ、メモリデータは、レジスタ、メモリから読み出す
- 未実効命令へのレジスタ、メモリデータはメモリ、レジスタ経由で引き渡す
- それ以外については、可能な限り命令ウィンドウ内で直接命令間で渡す

命令ウィンドウ内では
- 各命令はデータ依存関係にもとづき実行制御される
 (各入力オペランドがそろった時点で命令実行)
- CPU内資源が無限にある場合に最短の実行時間を得る
- 未実行命令に渡すメモリデータは命令ウィンドウに最も近いものをうぽおおおお


【命令ウィンドウ内の条件分岐】

【ILP利用に対する制御ハザード】
ILP利用→データ依存関係に基づく並列性による高速化
制御ハザード→制御依存関係では、分岐命令の前後が逐次化
        ↓
   逐次計算機では、実効命令列は逐次

制御ハザードによる逐次化の解消
- 遅延分岐命令 → 遅延スロット数が限定されっるため、効果が少ない
- 分岐予測 → 投機的に逐次実行列を作成。失敗したら巻き戻し
- 深い分岐予測 → 分岐予測の先の分岐予測
- Dual Rail 実行 → 分岐の両側を並列実行(分岐方向が確定するまで)
- 条件分岐から条件代入への変換 → 演算量が急増、並列性は増加

【分岐予測】

条件分岐命令に制御依存している命令列を投機的に実行
- 静的分岐予測
        - コンパイラ等が、分岐命令毎に投機的実行を行う方向を設定
                - Alpha 21064では、分岐の方向で設定(正→非分岐、負→分岐を予測)
                - SPARC等では命令により投機する分岐方向を指示
                - 分岐命令の次に、投機する分岐方向の命令を詰める
                - 投機が成功した場合には、処理を続行
                - 投機が失敗した場合には、分岐以降の処理を全て取り消し正しい場所から再開
                - 投機中の副作用は、巻き戻し可能・仮の副作用とする

【静的分岐予測の限界】

分岐命令の投機的実行
- 分岐側を投機する場合、ペナルティなしの設計は困難
- 投機に失敗して時のペナルティ大 ←ここだけ覚えておけばいいヨ
        - 仮状態の取り消し
        - 既に加えた副作用の巻き戻し
        - 並列計算との関連(メモリの一貫性問題)

- 投機の成功率(ヒット率)が低い
        - ループを作る分岐命令
                - ループ毎に一回不成功    p = 1/n
        - ループ内の条件判断
                - 静的予測困難 → プロファイルに基づく分岐予測
                        → 実行時のプログラム切り替え
        - 例外処理ルーチンへの分岐
                - 高い制的予測制度
        - トータルでは80%位のヒット率

【動的分岐予測方式】

実行時の過去の履歴から、分岐方向を予測し投機実行する
- 局所情報  当該分岐命令の過去の分岐履歴など
- 大局情報  当該分岐命令以外の過去の実行状況など

- 例:ループを作る分岐を、過去の分岐方向から予測
- 例:過去の分岐パターンで、最出のものから予測
- 例:他の分岐命令から分岐方向を類推

【動的分岐予測方式の歴史】

分岐予測表による方法
- 英国マンチェスタ大、MU-5の命令ユニット
- Branch Target Buffer (マンチェスタ大)
- 2-level分岐予測
- GShare方式の分岐予測

【分岐予測表(BPT or BPB)】

- 条件分岐命令のアドレスと、過去の分岐履歴を表(またはカウンタ)
      | 条件分岐命令(下位アドレス)| Valid | 履歴カウンタ |
      |                             |       |              |
      |                             |       |              |
      |                             |       |              |

- 1ビット予測 → 偏った分岐でミス回数が倍増
- 2ビット予測 → 飽和カウンタが通常用いられる
        →図は動画

【Branch Target Buffer】
分岐予測表は、分岐命令の成立/不成立を予測
        → 分岐命令による分岐先アドレス生成が必要
                → 最低1クロックのペナルティ

Branch Target Buffer(BTB)
あとはどうがみろ

【BTBの処理】
           [PCをメモリとBTBに送付]
                                ↓
            ← No    <BTBに対応するエントリ?>   Yes →
    ↓                                              ↓
 <命令は分岐命令?>                            [BTBの予測PCを送付]
  No    Yes                         ↓
  ↓    ↓              <分岐結果が予測と一致?>
通常実行  命令をBTBに登録              ~~~~~~動画~~~~~~~~~~~

【更なる分岐予測精度の向上】

命令レベル並列性の利用 → 1クロックに基本位置ブロック
分岐に夜性能低下(クロック)
        分岐命令のBTBヒット率 * 予測ミス率 * ミスペナルティ
    + (1 - BTBヒット率) * 分岐成立率 * 分岐ペナルティ
~~~~~~~~~~~~~~~

【2レベル分岐予測】
分岐予測を、分岐のパターンと分岐履歴から予測
例:PAs方式 Intel Pentium iii

図は動画で


【Gshare方式】

【ハイブリッド分岐予測】
- ローカル履歴予測方式とグローバル予測方式の組み合わせ
- どちらで予測するのが良いかの選択に関する予測器
- DEC Alpha 21264で使用
     ↓
  予測期の方式は、分岐だけでなく
    - メモリアドレス予測
        - 値予測
  でも使用される

【ちこくすた】
【動画で見よう】

【スコアボード方式】

【リザベーションステーション】

【トマスロのアルゴリズムの実行】

【パイプライン方式と割り込み】

H21 7/10

【アスセスギャップの克服】

【時間的局所性と空間的局所性】

【局所性の利用方式】

【キャッシュメモリ(バッファ・ストレージ)】
ハードウェアによる Large/Smallメモリの使用
- Wilks ; 1965, IBBM 360/85:1968
- メモリ間データ移動を実現する命令オーバーヘッドなし
- メモリ間転送量はプログラムのアクセスパターンに依存
- 小規模メモリを検索するハードウェアが必要(付加ハードウェア)
- メモリ間転送の単位は固定(ブロック/ライン)

基本方式
- メモリ空間を、固定サイズのブロックに分割
- ブロック単位で、小規模メモリにコピー作成
- 読み出しは小規模メモリから

【基本方式】
→動画
- ダイレクトマップ方式
- フルアソシアティブ方式
- セットアソシアティブ方式

【基本方式(2)】

【基本方式(3)】
キャッシュミス時に、どのブロックを置き換えるか
- キャッシュミス 当該ブロックがキャッシュメモリ上にない

- ダイレクトマップ方式
        置き換えるブロックは一意的に決定

- セットアソシアティブ方式
        N個の候補から選択
                - Random方式
                - LRU(Least Recently Used)方式 キャッシュメモリでは、正確なLRUが可能

- フルアソシアティブ方式
        Random方式が中心(正確なLRUは無理)

(脱線) FIFO異常とは
        Stackアルゴリズムではcacheを大きくすると性能低下

【LRU方式の実現】

キャッシュメモリでは、1メモリアクセスしか許されない→Write Only
→動画

【基本方式(4)】

書き込み時の動作
- メインメモリに書き込みを反映させるか?
        Write Through   キャッシュメモリへの書き込みは、同時にメインメモリへ
        Write Back      書き込みはキャッシュメモリだけに反映
- キャッシュ上にないブロックへの書き込み
        Write Allocate  当該ブロックをキャッシュメモリにコピーして、キャッシュに書く
        No Write Allocate       メインメモリだけに書き込み、キャッシュは不変

        通常      Write Through : No Write Allocate
                Write Back :    Write Allocate の組み合わせ
                銀行ではECC付メインメモリでWrite Throughを使う(キャッシュにはECCがない)

これらは、メモリアクセスの(Read,Write)のパタンで優劣
        - 信頼性の問題
        - メモリバス転送量の問題

【キャッシュメモリの性能】
- ミス率   キャッシュメモリ上にアクセスするブロックがない
- 平均アクセス時間
        = (1 - ミス率) * キャッシュアクセス時間
          + ミス率 * (メインメモリアクセス時間 + 転送時間)

キャッシュミスの原因
        1. 初期ミス クリアなキャッシュにデータを埋めていく
        2. 容量ミス ワーキングセットがキャッシュに入らない
        3. 競合ミス 連想性が原因で、キャッシュからはみ出す

【キャッシュのブロック図】
→動画
よく覚えておきなさいとかチラッと言ったような

【ID分離キャッシュと統合キャッシュ】
→動画

【キャッシュサイズとミス率】
→動画
暗記してもしょうがない
容量を増やすと順調にミス率は低下していくが、だんだん容量に対し低下幅は小さくなっていく

【キャッシュミスの原因】
→動画

【キャッシュメモリの高速化】

【ミス率の減少方式(1)】

ミスの原因が時間的局所性/空間的局所性のいずれに関連か?

大きいブロックサイズ
        1. 空間的局所性の利用
        2. ミスペナルティの増大(転送時間の増大)
        3. ブロック数の減少(時間的局所性が利用困難)
        4. 通常、32から64バイト。容量が小さい場合には最適値が減少

【ブロックサイズの選択】

【ミス率の減少方式(2)】

高い連想性の使用
        - ダイレクト・マップキャッシュ → セットアソシアティブ
        - 2way → 4way
        - 競合ミスの減少とキャッシュアクセス時間のトレードオフ
                - (特にダイレクトマップキャッシュの高速性)
        →動画

【ミス率の減少方式(3)】

Victim Cache
        - ダイレクトマップキャッシュでの競合ミスを、最近追い出されたブロックを
          保持する小さなFull Associativeキャッシュで回避
        - 4エントリから7エントリで十分有効

【ミス率の減少方式(4)】

擬似セットアソシアティブ方式
        - 各Wayは、独立したメモリではなく、同一メモリの異なる領域としておく
        - どのWayをアクセスするか→アクセス順でブロック内容を交換
        - ヒット時間が、直接ヒットする場合と擬似的にヒットする場合に分かれる
        - この方式は絶滅した?

【ミス率の減少方式(5)】

ハードウェアによるプリフェッチ
        - プリフェッチ        CPUからの実際のアクセス時間に先立って、block in
        - 命令            シーケンシャル実行時に、次のブロックをプリフェッチ
        - データ   連続アドレスアクセスで、次のブロックをプリフェッチ
        
        書ききらないよ→動画

【ミス率の減少方式(6)】

ソフトウェアによるプリフェッチ
        - コンパイラがプリフェッチ命令を挿入
        - プリフェッチ命令 non-blockingなキャッシュアクセス命令
        - コンパイラが、命令/データのアクセスパタンを解析
        - 連続アクセス、一定ストライドアクセスなど
        - 問題点
                - プリフェッチ命令のオーバーロード
                - 競合ミスによる無駄なプリフェッチ

【ミス率の減少方式(7)】

最適化コンパイラによるキャッシュを意識した変換/スケジューリング
        - ブロッキング(データの分割を変え、キャッシュ内にワーキングセットが
                        入るように変更)
        - 配列の併合(空間的局所性を活用)
        - ループ順序の変更
        - ループ分裂
        - ループ融合

全て、プログラムから依存グラフを作成しそこから作成

【最適化コンパイラによる性能向上】
→動画


CategoryHomepage

Araigeta (last edited 2009-09-05 03:36:46 by Araigeta)