並列処理

ここから少し内容が高度になる。 Article Category

• キャッシュコヒーレンシ

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

• SIMDコンピュータ

• 背景：

  • Race conditions , mutual exclusion (lock, deadlock) , synchronization, and parallel slowdown

  • Fine-grained, coarse-grained, and embarrassing parallelism

• 種類：ビットレベル、命令レベル (パイプライン/ スーパースケーラ)、データ、 タスク

• ハードウェア：

  • メモリと通信：共有メモリ/ 分散メモリ、 UMA/ NUMA、 キャッシュコヒーレンシ、 バススヌープ、 バス

  • 並列コンピュータの分類：マルチコア、 SMP、 分散コンピュータ(クラスタ)、特別(reconfig, GPGPU、ASIC、ベクタープロセッサ）

• ソフトウェア：並列処理言語 (message passing(POSIX threads, OpenMP, MPI))、自動並列化、application checkpointing

• アルゴリズム：

• パイプライン

  • ステージ

  • ハザード

    • 構造ハザード

    • データハザード (依存関係の分類(RAW依存/WAR依存/WAW依存)/RAWの解消法(バイパス/パイプラインスケジューリング))

    • 制御ハザード (動的解消方法(分岐予測/分岐ターゲットキャッシュ)/静的解消方法(遅延分岐))

  • スーパーパイプライン

• 命令レベル並列コンピュータ (スーパースケーラ/VLIW/アウトオブオーダー)

• マルチプロセッサ (共有メモリ/MIMD)

• 相互結合網 (静的網/動的網/複合網)

• データフロー・アーキテクチャ

• 論理記憶

• 並列処理の形態による分類

  • 時空による分類

    • 時間並列性を利用したのがパイプライン

    • 空間並列性を利用したのがいわゆる並列処理

    • 両方合わせた並列パイプライン処理もある。

  • 命令とデータによる分類

  • 非ノイマン型 実行制御の基本となるのが命令以外のものを非ノイマン型で、データ駆動型などがある。

    • ノイマン型

      • SISD細粒度

        • 時間並列 パイプライン スーパーパイプライン

        • 空間並列 スーパースケーラ VLIW

      • SIMD

        • 時間並列 ベクタコンピュータ

        • 空間並列 SIMDパラレル 連想プロセッサ

      • MIMD

        • 時間並列 シストリックアレイ

        • 空間並列 マルチプロセッサ マルチコンピュータ PC/WSクラスタ

    • 非ノイマン型

      • データ駆動

      • 要求駆動

• 命令とデータによる分類

  • SISD。逐次型の普通のコンピュータ。

  • SIMD。同一の命令で複数のデータを処理する。同じ処理を一度にたくさん実行する。

  • MIMD。複数の命令が複数のデータに対して異なる処理を同時に実行する。

  • Flynn's taxnomoy：SIMD, MIMD

• 粒度 並列処理の単位となる処理の大きさを粒度という。

  • 細粒度 命令、文

  • 中粒度 ループ

  • 粗粒度 ブロック、サブルーチン

• マルチプロセッサ\MIMDマルチプロセッサ

  • 構成による分類

    • 集中共有メモリ … UMA

    • 分散共有メモリ

    • 部分共有メモリ

  • キャッシュコヒーレンス

    • コヒーレントにする方法 更新方式 無効化方式

    • 静的な方法 共有キャッシュ

    • 動的な方法 共有バス法 … スヌープキャッシュ ディレクトリ法

  • キャッシュコヒーレンスプロトコル

  • 同期

    • 条件同期

    • 相互排除

    • プロセスの待ち方 スピンロック サスペンドロック

  • コンパイル技術

    • タスク分割

    • タスクスケジューリング

• マルチプロセッサ\MIMDマルチコンピュータ

  • メッセージパッシング

    • 同期 非同期 待ち合わせ

    • MPI

  • 並列プログラミング メモリモデルによる分類

    • 分散メモリモデル

    • 共有メモリモデル

• マルチプロセッサ\命令レベル並列コンピュータ

  • スーパーパイプライン

  • スーパースケーラ

  • VLIW

  • 命令レベル並列性の抽出方法（アウトオブオーダー実行）

    • 静的な方法 … 命令スケジューリング

      • リストスケジューリング

      • トレーススケジューリング

      • ソフトウェアパイプライニング

      • プレディケーション

    • 動的な方法

      • スコアボーディング

      • トマスロアルゴリズム

        • リザベーションステーション

• マルチプロセッサ\共有メモリ

  • 同期

    • 条件同期

    • 相互排除

    • 待ち方

      • スピンロック

      • サスペンドロック

    • ハードウェア機構

      • テスト・アンド・セット

      • フェッチ・アンド・アッド

      • ロードリンクト、ストアコンディショナル

    • ソフトウェア機構

      • セマフォ

      • モニタ

      • バリア

  • メモリコンシステンシモデル

    • シーケンシャルコンシステンシ