フリン分類法
コンピュータアーキテクチャの分類

フリン分類法は、マイケル・J・フリンが1966年に提唱し[1]、1972年に拡張されたコンピュータアーキテクチャの分類法である[2]。この分類法は定着し、現代のプロセッサとその機能の設計ツールとして利用されてきた。マルチプロセッシング中央処理装置（CPU）の台頭以来​​、マルチプログラミングの文脈は分類法の拡張として発展してきた。ダンカンの分類法[3]で扱われているベクトル処理は、 Cray-1が1977年にリリースされたため、フリンの研究には含まれていない。フリンの2番目の論文は1972年に発表された。

分類

フリンによって定義された4つの初期の分類は、アーキテクチャで利用可能な同時命令（または制御）ストリームとデータストリームの数に基づいています。[4]フリンは1972年にSIMDの3つの追加のサブカテゴリを定義しました。[2]

フリン分類法
単一のデータストリーム
複数のデータストリーム
SIMDサブカテゴリ[5]
  • 配列処理（SIMT）
  • パイプライン処理（パックSIMD）
  • 連想処理（述語付き/マスク付きSIMD）
参照

単一命令ストリーム、単一データストリーム (SISD)

命令ストリームとデータストリームのいずれにおいても並列性を利用しないシーケンシャルコンピュータ。単一の制御ユニット（CU）がメモリから単一の命令ストリーム（IS）をフェッチします。CUは適切な制御信号を生成し、単一の処理要素（PE）に単一のデータストリーム（DS）を処理させるよう指示します。つまり、一度に1つの処理を実行することになります。

SISD アーキテクチャの例としては、古いパーソナル コンピュータ(PC) (2010 年までに、多くの PC に複数のコアがありました) や古いメインフレーム コンピュータなどの従来のユニプロセッサマシンが挙げられます。

単一命令ストリーム、複数データストリーム（SIMD）

単一の命令が複数の異なるデータストリームに同時に適用されます。命令はパイプラインなどの方法で順次実行されることも、複数の機能ユニットによって並列実行されることもできます。フリンの1972年の論文では、SIMDはさらに3つのカテゴリに分類されています。[2]

  • 現在SIMTとして知られるアレイプロセッサ– これらは1つの（同じ）命令を受け取りますが、各並列処理ユニット（PU）はそれぞれ独立したメモリとレジスタファイルを備えています。各PUに接続されたメモリは他のPUと共有されません。初期のSIMTプロセッサはスカラーPU（SOLOMONでは1ビット、 ILLIAC IVでは64ビット）を搭載していましたが、現代のSIMTプロセッサ（ GPU）は必ずSWAR ALUを搭載しています。
  • パイプライン型プロセッサ- パイプライン型プロセッサは、1つの（同じ）命令を受け取りますが、中央のリソースからデータを読み取り、各プロセッサがそのデータの断片（通常は「要素」と呼ばれます）を処理し、結果を同じ中央のリソースに書き戻します。Flynnの1972年の論文の図5では、そのリソースはメインメモリです。現代のCPUでは、そのリソースは一般的にレジスタファイルです。
  • 連想プロセッサ– これらは1つの（同一の）命令を受け取りますが、それに加えて、制御ユニットからのレジスタ値も各PUにブロードキャストされます。各PUではユニットのローカルデータとブロードキャスト値を比較し、ブロードキャスト命令を実行するかスキップするかを独立して決定します


アレイプロセッサ

フリン 1972 分類法配列プロセッサ、フリンの 1972 年の論文[2]の図 5a

アレイプロセッサの現代的な用語は「単一命令複数スレッド」（SIMT）です。これは、1972年のFlynnの分類法において、SIMDのサブカテゴリとして明確に区別されています。並列サブ要素がそれぞれ独立したレジスタファイルとメモリ（キャッシュとデータメモリ）を備えている点が特徴的です。Flynnの初期の論文には、SIMTプロセッサの歴史的な例としてSOLOMONとILLIAC IVが挙げられています。

各処理要素には、PE を有効/無効にする独立したアクティブ/非アクティブ ビットもあります。 

for each (PE j) // 同期的に並行な配列
   if (active-maskbit j) then
      ブロードキャスト命令(PE j)

Nvidiaはマーケティング資料や技術文書でこの用語をよく使用し、そのアーキテクチャの斬新さを主張しています。[6] SOLOMONはNvidiaより60年以上前に登場しました。

パイプラインプロセッサ

フリン1972分類パイプラインプロセッサ、フリンの1972年の論文[2]の図5b

フリンの1972年の論文では、パイプラインプロセッサを「時分割多重化」された配列処理の一種と呼んでいます。これは、要素がメモリから順次読み出され、（パイプライン化された）ステージで処理され、最終ステージから再びメモリに順次書き出されるというものです。この記述（954ページ）から、フリンが言及していたのはベクトル連鎖、そして1966年から1973年にかけて設計・製造・販売されたTI ASC [7] や、フリンの論文執筆当時発表されたばかりだったCDC STAR-100などのメモリ間ベクトルプロセッサであったと考えられ ます。

フリン氏が1972年に論文を執筆した当時、多くのシステムはパイプラインの読み書きリソースとしてメインメモリを使用していました。すべての「パイプライン」の読み書きリソースがメインメモリではなくスカラーレジスタファイルである場合、SIMDの現代的な派生型が生まれます。例としては、Altivec、NEON、AVXなどが挙げられます。

このタイプのレジスタベースのSIMDの別名は「パックSIMD」[8]であり、別の名前はレジスタ内のSIMD（SWAR）である。

連想プロセッサ

フリン1972年の分類法による連想配列プロセッサ図、フリンの1972年の論文[2]の図5c

連想プロセッサの現代的な用語は、それぞれが独立したプロセッサを持つ連想メモリのセルに似ています。このようなプロセッサは非常に稀です。 

broadcast_value = control_unit.register ( n ) broadcast_instruction = control_unit.array_instruction for each ( PE j ) //連想配列のpossible_match = PE [ j ] .match_register if broadcast_value == possible_match PE [ j ] .execute ( broadcast_instruction )​

Aspex Microelectronicsの連想文字列プロセッサ（ASP）[9]は、マーケティング資料では「大規模ワイドSIMD」と分類されていたが、ビットレベルのALUとビットレベルの述語（Flynnの分類法では配列処理）を備えており、4096個のプロセッサそれぞれに、連想メモリ（Flynnの分類法では連想処理）を含む独自のレジスタとメモリが搭載されていた。2010年にリリースされたLinedancerは、それぞれにCAMを備えた2ビット述語SIMD ALUを4096個搭載し、毎秒8000億命令の処理能力を備えていた。[10] AspexのASP連想配列SIMTプロセッサは、NVIDIAより20年も前に登場した。[11] [12]このプロセッサは、プログラマが明示的に制御できる連想処理機能と配列処理の両方を備えていたため、Flynnの分類法に従って分類するのは困難である。

複数の命令ストリーム、単一のデータストリーム (MISD)

複数の命令が1つのデータストリーム上で動作します。これは珍しいアーキテクチャですが、一般的にはフォールトトレランスに使用されます。異種システムは同じデータストリーム上で動作し、結果が一致する必要があります。例としては、スペースシャトルの飛行制御コンピュータが挙げられます。[13]

複数の命令ストリーム、複数のデータストリーム（MIMD）

複数の自律プロセッサが、異なるデータに対して異なる命令を同時に実行します。MIMDアーキテクチャには、マルチコア ・スーパースカラ・プロセッサや、1つの共有メモリ空間または分散メモリ空間を使用する 分散システムが含まれます。

分類を比較した図

これら4つのアーキテクチャは、以下に視覚的に示されています。各処理ユニット（PU）は、ユニコアまたはマルチコアコンピュータごとに示されています。

さらなる分割

2006 年現在[アップデート]、トップ 10 のスーパーコンピュータのすべてと、TOP500 のスーパーコンピュータの ほとんどは、MIMD アーキテクチャに基づいています。

これらはフリンの研究の一部ではないが、MIMDカテゴリーをさらに以下の2つのカテゴリーに分類する人もいる[14] [15] [16] [17] [18]。さらに細分化が検討されることもある[19] 。

単一プログラム、複数データ ストリーム (SPMD)

複数の自律プロセッサが、異なるデータに対して同じプログラムを同時に（ただし、 SIMDのようなロックステップではなく、独立したポイントで）実行する。 [20]単一プロセス複数データとも呼ばれる[18]。SPMDは並列実行モデルであり、複数の協調プロセッサがプログラムを実行することを前提としているため、この用語をSPMDに使用することは技術的に正しくない。SPMDは明示的並列プログラミングの最も一般的なスタイルである。[21] SPMDモデルと用語は、RP3チームのフレデリカ・ダレマによって提案された。[22]

複数のプログラム、複数のデータ ストリーム (MPMD)

複数の自律プロセッサが、少なくとも2つの独立したプログラムを同時に実行します。HPCのコンテキストでは、このようなシステムでは、1つのノードを「ホスト」（明示的なホスト/ノード・プログラミング・モデル）または「マネージャ」（マネージャ/ワーカー戦略）として選択することがよくあります。ホストは1つのプログラムを実行し、そのプログラムが他のすべてのノードにデータを分散させます。他のノードはすべて別のプログラムを実行します。そして、他のノードは結果をマネージャに直接返します。この例として、SPU/PPUプロセッサを搭載したソニーのPlayStation 3ゲームコンソールが挙げられます。

MPMDはHPC以外の分野でも広く使用されています。例えば、makeビルドシステムは、make実行ファイル自体に加えてターゲット依存プログラムを使用して、複数の依存関係を並列にビルドできます。MPMDはパイプライン形式を取ることもよくあります。例えば、次のような単純なUnixシェルコマンドを実行すると、3つのプロセスが起動され、それぞれが別々のプログラムを並列に実行します。これらのプロセスの出力は、次のプロセスの入力として使用されます。 ls | grep "A" | more

これらはどちらも、HPCで使用される明示的な並列プログラミングとは異なり、個々のプログラムは特定の並列アルゴリズムの一部を実装するのではなく、汎用的な構成要素です。パイプライン方式では、利用可能な並列処理の量はデータセットのサイズに応じて増加しません。

参照

参考文献

  1. ^ Flynn, Michael J. (1966年12月). 「超高速コンピューティングシステム」(PDF) . Proceedings of the IEEE . 54 (12): 1901– 1909. doi :10.1109/PROC.1966.5273.
  2. ^ abcdef Flynn, Michael J. (1972年9月). 「いくつかのコンピュータ組織とその有効性」(PDF) . IEEE Transactions on Computers . C-21 (9): 948– 960. doi :10.1109/TC.1972.5009071. S2CID  18573685.
  3. ^ Duncan, Ralph (1990年2月). 「並列コンピュータアーキテクチャの概観」(PDF) . Computer . 23 (2): 5– 16. doi :10.1109/2.44900. S2CID 15036692. 2018年7月18日時点 のオリジナル(PDF)からアーカイブ。 2018年7月18日閲覧。
  4. ^ 「ベクター、SIMD、GPUアーキテクチャにおけるデータレベル並列性」(PDF) 2013年11月12日。
  5. ^ Flynn, Michael J. (1972年9月). 「いくつかのコンピュータ組織とその有効性」(PDF) . IEEE Transactions on Computers . C-21 (9): 948– 960. doi :10.1109/TC.1972.5009071.
  6. ^ 「NVIDIA の次世代 CUDA コンピューティング アーキテクチャ: Fermi」(PDF) . Nvidia .
  7. ^ http://www.bitsavers.org/pdf/ti/asc/ASC_History_May84.txt [裸の URL ]
  8. ^ 宮岡 雄三; 崔 俊一; 戸川 暢; 柳沢 正; 大月 毅 (2002).パックドSIMD型命令を用いたプロセッサコア合成のためのハードウェアユニット生成アルゴリズム. アジア太平洋回路・システム会議. pp.  171– 176. doi :10.1109/APCCAS.2002.1114930. hdl : 2065/10689 . ISBN 0-7803-7690-0。
  9. ^ Lea, RM (1988). 「ASP: コスト効率の高い並列マイクロコンピュータ」. IEEE Micro . 8 (5): 10– 29. doi :10.1109/40.87518. S2CID  25901856.
  10. ^ 「Linedancer HD – 概要」. Aspex Semiconductor . 2006年10月13日時点のオリジナルよりアーカイブ。
  11. ^ Krikelis, A. (1988).超並列連想アーキテクチャによる人工ニューラルネットワーク. 国際ニューラルネットワーク会議. ドルドレヒト: Springer . doi :10.1007/978-94-009-0643-3_39. ISBN 978-94-009-0643-3。
  12. ^ オドール、ゲザ;クリケリス、アージー。ヴェスターゴンビ、ジェルジュ。ロールバッハ、フランソワ。 「System-V の超並列連想文字列処理アーキテクチャにおける効果的なモンテカルロ シミュレーション」(PDF)。
  13. ^ Spector, A.; Gifford, D. (1984年9月). 「スペースシャトルのプライマリコンピュータシステム」Communications of the ACM . 27 (9): 872–900 . doi : 10.1145/358234.358246 . S2CID  39724471.
  14. ^ 「Single Program Multiple Data stream (SPMD)」Llnl.gov. 2004年6月4日時点のオリジナルよりアーカイブ。2013年12月9日閲覧。
  15. ^ 「ジョブのコンパイル、ビルド、実行に関するプログラミング要件」。Lightningユーザーガイド。2006年9月1日時点のオリジナルよりアーカイブ。
  16. ^ 「CTCバーチャルワークショップ」Web0.tc.cornell.edu . 2013年12月9日閲覧。
  17. ^ 「NIST SP2入門：分散メモリプログラミング」Math.nist.gov. 2013年12月13日時点のオリジナルよりアーカイブ。2013年12月9日閲覧。
  18. ^ ab 「IBM SPシステムにおける並列ジョブ管理とメッセージパッシングの理解」。2007年2月3日時点のオリジナルよりアーカイブ。
  19. ^ “9.2 戦略”.分散メモリプログラミング. 2006年9月10日時点のオリジナルよりアーカイブ。
  20. ^この記事は、2008 年 11 月 1 日より前の Free On-line Dictionary of Computing のFlynn's+taxonomy から取得した資料に基づいており、 GFDLバージョン 1.3 以降 の「再ライセンス」条項に基づいて組み込まれています。
  21. ^ 「単一プログラム複数データ」Nist.gov. 2004年12月17日. 2013年12月9日閲覧。
  22. ^ Darema, Frederica ; George, David A.; Norton, V. Alan; Pfister, Gregory F. (1988). 「EPEX/FORTRANのための単一プログラム複数データ計算モデル」. Parallel Computing . 7 (1): 11– 24. doi :10.1016/0167-8191(88)90094-4.
「https://en.wikipedia.org/w/index.php?title=Flynn%27s_taxonomy&oldid=1311739296#Multiple_programs,_multiple_data_streams_(MPMD)」より取得