10. マルチスレッド・プロセッサ 五島 正裕.

Presentation on theme: "10. マルチスレッド・プロセッサ 五島 正裕."— Presentation transcript:

1 10. マルチスレッド・プロセッサ 五島 正裕

2 内容 スレッド と マルチスレッド・プロセッサ スループット指向 MTP Thread-Level-Parallelism 指向 MTP
Advanced Computer Architecture 内容 スレッド と マルチスレッド・プロセッサ スループット指向 MTP Thread-Level-Parallelism 指向 MTP

3 スレッド と マルチスレッド・プロセッサ

4 スレッド (thread) とは いろいろなレベルのスレッド 言語のスレッド Java thread
Advanced Computer Architecture スレッド (thread) とは いろいろなレベルのスレッド 言語のスレッド Java thread スレッド・ライブラリ の ユーザ・レベル・スレッド： スレッド・ライブラリ の システム・レベル・スレッド＝OS のスレッド： Pthreads，NT thread HW のスレッド： プロセッサ・コンテクスト： 「プロセッサの実行状態」 「1つの PC で指定される命令流」

5 OS のスレッド タスク ― スレッド・モデル 1つのプロセス ＝ 1つのタスク ＋ 1つ以上のスレッド スレッド タスク タスク
Advanced Computer Architecture OS のスレッド タスク ― スレッド・モデル 1つのプロセス ＝ 1つのタスク ＋ 1つ以上のスレッド スレッド タスク タスク シングル・スレッド・プロセス マルチスレッド・プロセス

6 OS のスレッド プロセス，スレッドの実体： プロセスの実体： ページ・テーブル（大きい）
Advanced Computer Architecture OS のスレッド プロセス，スレッドの実体： プロセスの実体： ページ・テーブル（大きい） スレッドの実体： プロセッサ・コンテクスト（小さい） マルチ・プロセス のサイズ ＞マルチスレッドのシングル・プロセス のサイズ スレッド タスク タスク シングル・スレッド・プロセス マルチスレッド・プロセス

7 マルチスレッド・プロセッサ (MTP) プロセッサ・コンテクスト (processor context)
Advanced Computer Architecture マルチスレッド・プロセッサ (MTP) プロセッサ・コンテクスト (processor context) プロセッサの動作状態を一意に定義するデータの集合 「コンテクスト・スイッチのとき，退避/復帰されるもの」 PC，レジスタ，ステータス・レジスタ，etc． マルチスレッド・プロセッサ (MTP)： 複数のプロセッサ・コンテクストを保持する それらのスイッチを HW が行う 1個のプロセッサであって，複数のスレッドを「同時に」実行できるもの

8 余談：マルチスレッド・プロセッサの英訳？
Advanced Computer Architecture 余談：マルチスレッド・プロセッサの英訳？ Google (2009/06/23 → 2011/06/14) "multithreaded processor" (18,100件 → 61,800件) "multi-threaded processor" (12,800件 → 270,000件) "multithreading processor" ( 6,980件 → 15,400件) "multi-ｔhreading processor" ( 1,720件 → 82,800件) "multithread processor" ( 1,710件 → 10,100件) "multi-thread processor" ( 1,840件 → 52,200件)

9 マルチスレッド・プロセッサ （和訳） Google (2009/06/23 → 2011/06/14)
Advanced Computer Architecture マルチスレッド・プロセッサ （和訳） Google (2009/06/23 → 2011/06/14) "マルチ スレッド プロセッサ" (226件 → 5,940件) "マルチ スレッディング プロセッサ" (18件 → 4件 うち2件がこのスライドｗ) "スレディッド" （数件 → 210件） "スレディド" （数件 → 7件 うちｒｙ） "スレッディッド" （数件 → 119件）

10 余談：マルチスレッド・プロセッサ マルチスレッド・プロセッサ 複数スレッドを「同時に」実行できる 1つのプロセッサ
Advanced Computer Architecture 余談：マルチスレッド・プロセッサ マルチスレッド・プロセッサ 複数スレッドを「同時に」実行できる 1つのプロセッサ マルチコア (multicore)，チップ・マルチプロセッサ (CMP) 複数のプロセッサ（コア）が1つのチップ（パッケージ）に集積されているもの マルチプロセッサ (multiprocessor) 複数のプロセッサ・チップを持つ 1つのシステム マルチスレッドのマルチコア，マルチプロセッサもある

11 余談：CPU，プロセッサ と コア 「CPU」 obsolete? 「マルチコア・プロセッサ」，「Intel Core i7 プロセッサ」
Advanced Computer Architecture 余談：CPU，プロセッサ と コア 「CPU」 obsolete? 「マルチコア・プロセッサ」，「Intel Core i7 プロセッサ」 「プロセッサ」は，パッケージ． 「コア」は，プログラムを実体する実体の一揃い 「プロセッサ・コンテクスト」，「マルチスレッド・プロセッサ」 「プロセッサ」は，プログラムを実体する実体の一揃い 「マルチコア・プロセッサ」の「コア」に相当 ならば，「コア・コンテクスト」，「マルチスレッド・コア」と言うか？

12 複数のスレッドの元 複数のスレッドの元 (source)： 複数のプログラムから 1本ずつ 1本のプログラムから複数のスレッド
Advanced Computer Architecture 複数のスレッドの元 複数のスレッドの元 (source)： 複数のプログラムから 1本ずつ 1本のプログラムから複数のスレッド それらの組み合わせ 抽出の方法： スレッド・ライブラリや言語機能を用いてプログラマが 自動マルチスレッド化コンパイラが HW が自動的に

13 MTP の分類 スループット指向 複数のプログラム 「単一のプログラムは速くならないが， 複数のプログラムを実行しても遅くならない」
Advanced Computer Architecture MTP の分類 スループット指向 複数のプログラム 「単一のプログラムは速くならないが， 　複数のプログラムを実行しても遅くならない」 粗粒度の並列性がある単一のプログラム（⇒ 複数のプログラム） データ並列性 「粗粒度のスレッド」 スレッド・ライブラリ 言語のスレッド機能 TLP (Thread-Level Parallelism) 指向 粗粒度の並列性がない単一のプログラム ⇒ TLP の抽出

14 (Thread-Level Parallelism)
Advanced Computer Architecture MT プロセッサの分類 プログラム 粗粒度の並列性 マイクロアーキテクチャ 複数 あり スループット指向 単一 粗粒度のスレッド データ並列性 TLP 指向 (Thread-Level Parallelism) なし

15 スループット指向 MTP

16 スループット指向 MTP の対象 スループット指向 MTP の対象： 粗粒度の並列性がある単一のプログラム データ並列性
Advanced Computer Architecture スループット指向 MTP の対象 スループット指向 MTP の対象： 粗粒度の並列性がある単一のプログラム データ並列性 「粗粒度のスレッド」 スレッド・ライブラリ 言語のスレッド機能 複数のプログラム： 「単一のプログラムは速くならないが， 　複数のプログラムを実行しても遅くならない」

17 スループット指向 MTP の戦略 スループット指向 MTP の戦略： 計算資源の利用効率の向上
Advanced Computer Architecture スループット指向 MTP の戦略 スループット指向 MTP の戦略： 計算資源の利用効率の向上 シングル・スレッドでは使いきれない計算資源の活用 使い切れない原因：レイテンシ 依存関係：レイテンシ分の空きスロット，バブル 予測ミス：ペナルティ分の空きスロット，バブル 実際的な主要因： データ依存 分岐予測ミス キャッシュ・ミス

18 スループット指向 MTP の分類 細粒度 (fine-grain) MTP クロック単位で切り替え
Advanced Computer Architecture スループット指向 MTP の分類 細粒度 (fine-grain) MTP クロック単位で切り替え SONY Cell PPE (2threads) Microsoft Xbox 360 (2threads) ？ 粗粒度 (coarse-grain) MTP，SoE (Switch-on-Event) MTP 長レイテンシ（キャッシュ・ミス）イベント発生時に切り替え Intel Itanium 2 SMT (Simultaneous Multi-Threading) プロセッサ 命令単位で切り替え Intel Hyper-Threading (HT) Technology (2threads)

19 細粒度 MT の効果 毎サイクル，スレッドを切り替える たとえば，スレッド数 ２ なら，
Advanced Computer Architecture 細粒度 MT の効果 毎サイクル，スレッドを切り替える たとえば，スレッド数 ２ なら， クロックを倍，パイプライン段数を倍にしても，レイテンシの影響が出ない cycle cycle

20 細粒度 MT の効果 IF ID EX L1 WB 昔 IF ID EX L1 WB IF ID EX L1 WB 微細化 IF ID EX
Advanced Computer Architecture 細粒度 MT の効果 IF ID EX L1 WB 昔 IF ID EX L1 WB IF ID EX L1 WB 微細化 IF ID EX L1 WB IF IF ID ID EX L1 L1 WB WB パイプライン化 IF IF ID ID EX L1 L1 WB WB IF IF ID ID EX L1 L1 WB WB IF IF ID ID EX L1 L1 WB WB 細粒度 MT IF IF ID ID EX L1 L1 WB WB IF IF ID ID EX L1 L1 WB WB

21 粗粒度 （Switch-on-Event） MT の効果
Advanced Computer Architecture 粗粒度 （Switch-on-Event） MT の効果 キャッシュ・ミス（など）で切り替え 分岐予測ミスには効果なし cycle キャッシュ・ミス キャッシュ ミス キャッシュ ヒット

22 Switch-on-Future-Event MT の効果
Advanced Computer Architecture Switch-on-Future-Event MT の効果 キャッシュ・ミス（など）を起こすと予測したら切り替え 分岐予測ミスにも効果あり cycle キャッシュ・ミス キャッシュ ヒット

23 SMT の構成 Out-of-Order スーパスカラがベース 拡張： 命令フェッチ： 細粒度で（クロックごとに）スレッド切り替え
Advanced Computer Architecture SMT の構成 Out-of-Order スーパスカラがベース 拡張： 命令フェッチ： 細粒度で（クロックごとに）スレッド切り替え それ以外： 論理レジスタ番号をスレッドの ID で拡張 「スレッド 0 は r0-0～r0-31，スレッド 1 は r1-0～r1-31」

24 スーパスカラ･プロセッサの基本構造 PC PC レジスタ・ファイル 命令 ウィンドウ 演算器 フロントエンド Front-end
Advanced Computer Architecture スーパスカラ･プロセッサの基本構造 PC PC レジスタ・ファイル 命令 キャッシュ 命令 ウィンドウ リネーム ロジック 演算器 フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB フロントエンド Front-end バックエンド Back-end

25 SMT の効果 cycle cycle 演算器 演算器 演算器 #０ #1 #０ #1 #０ #1
Advanced Computer Architecture SMT の効果 演算器 演算器 演算器 #０ #1 #０ #1 #０ #1 cycle cycle

26 SMT の利点/欠点 利点： OoO スーパスカラから，わずかな追加 HW で，MT化できる 他の MTP に比べ，
Advanced Computer Architecture SMT の利点/欠点 利点： OoO スーパスカラから，わずかな追加 HW で，MT化できる 他の MTP に比べ， 分岐予測ミス・ペナルティを含む，すべてのレイテンシを隠蔽可能 欠点（？）： （マルチコアに比べると）性能向上幅が小さい 「貧乏人のマルチコア」 スケーラブルでない 大容量のリネーム・テーブル，レジスタ・ファイルが必要になる

27 SMT のスレッド数 SMT の効果：空いている演算器の有効利用 スレッド数のみ ２ 以上に増やしても，性能向上はわずか
Advanced Computer Architecture SMT のスレッド数 SMT の効果：空いている演算器の有効利用 スレッド数のみ ２ 以上に増やしても，性能向上はわずか スレッド数を（２より）増やす ⇒ 演算器を 1揃い より増やす シングル・コア 4-way SMT vs. non-SMT デュアルコア デュアルコアの方が分散していてコンパクト 実際上，スレッド数は 2 まで

28 TLP 指向 MTP

29 TLP と ILP ILP : Instruction-Level Parallelism （1本のスレッドの中の）命令レベルの並列性
Advanced Computer Architecture TLP と ILP ILP : Instruction-Level Parallelism （1本のスレッドの中の）命令レベルの並列性 1個の PC が指す周辺にある，同時に実行可能な命令の数 TLP : Thread-Level Parallelism 複数のスレッドの中の 命令レベルの並列性 複数の PC が指す周辺にある，同時に実行可能な命令の数 ただし… データ並列性 や「粗粒度のスレッド」によるスレッドの並列性は， TLP とは言わない（たぶん） ILPは 1～2，TLPは 10～100（理想）

30 スレッドの抽出法 スレッドの抽出法： 静的： コンパイラ バイナリ互換性なし 動的： プロセッサ バイナリ互換性維持（可能）
Advanced Computer Architecture スレッドの抽出法 スレッドの抽出法： 静的： コンパイラ バイナリ互換性なし 動的： プロセッサ バイナリ互換性維持（可能）

31 SpMT SpMT （Speculative Multi-Threading，投機的 MT） 逐次プログラムを TLP 指向で PC を複数
Advanced Computer Architecture SpMT SpMT （Speculative Multi-Threading，投機的 MT） 逐次プログラムを TLP 指向で PC を複数 必然的に投機的になる 子スレッドを投機的に fork． プログラマ（やコンパイラ）が指定可能な粒度では敵わない ⇒ 細粒度 １スレッド：数～数十命令

32 複数パス実行 複数パス実行 (multi-path execution) 分岐予測があたりにくい分岐の先を子スレッドに
Advanced Computer Architecture 複数パス実行 複数パス実行 (multi-path execution) 分岐予測があたりにくい分岐の先を子スレッドに あたったスレッドが生き残る 分岐予測 複数パス実行 PC PC PC PC PC

33 ヘルパ・スレッディング (helper threading)
Advanced Computer Architecture ヘルパ・スレッディング (helper threading) ヘルパ・スレッド 簡約化されたコードを実行し，キャッシュ・プリフェッチ（など）を行う メイン・スレッド キャッシュ・アクセスがヒットする Pseudo Multi-Threading (using Intel Hyper-Threading) メイン・スレッド × 1 ＋ ヘルパ・スレッド × 1 を SMT で．

34 Slipstream Processors
Advanced Computer Architecture Slipstream Processors 先行スレッド 静的予測に基づいて簡約化されたコードを実行 簡約化されているので速い キャッシュや予測器を暖める 検証スレッド 先行スレッドの後を追って， 簡約化されていないコードを実行し，予測を検証 キャッシュや予測器が暖まっているので速い

35 今日のまとめ

36 (Thread-Level Parallelism)
MTP の分類 プログラム 粗粒度の並列性 マイクロアーキテクチャ 単一 なし TLP 指向 (Thread-Level Parallelism) データ並列性 粗粒度のスレッド スループット指向 複数 あり Advanced Computer Architecture

37 スループット指向 MTP ： 実用段階 細粒度 (fine-grain) MTP クロック単位で切り替え
Advanced Computer Architecture スループット指向 MTP ： 実用段階 細粒度 (fine-grain) MTP クロック単位で切り替え SONY Cell PPE (2threads) Microsoft Xbox 360 (2threads) ？ 粗粒度 (coarse-grain) MTP，SoE (Switch on Event) MTP 長レイテンシ（キャッシュ・ミス）イベント発生時に切り替え Intel Itanium 2 SMT (Simultaneous Multi-Threading) プロセッサ 命令単位で切り替え Intel Hyper-Threading (HT) Technology (2threads)

38 TLP 指向 MTP ： 研究段階 シングル・プログラムの無制限の性能向上を目指す SpMT → 死語？
Advanced Computer Architecture TLP 指向 MTP ： 研究段階 シングル・プログラムの無制限の性能向上を目指す SpMT → 死語？ 目的を限定する ＝ レイテンシの隠蔽による資源の利用効率の向上 ヘルパー・スレッディング Switch-on-Future-Event MT