明示的なマルチスレッド

明示的マルチスレッド( XMT ) は、並列ランダムアクセスマシン(PRAM) 並列計算モデルに基づいて設計された並列コンピュータを構築およびプログラミングするためのコンピュータサイエンスのパラダイムです。XMT をより直接的に説明すると、シリアルコンピューティングをシンプルにした基本的な抽象化、つまりシリアルプログラムで実行可能な任意の単一の命令が即座に実行されることから始まります。この抽象化の結果、次に実行可能な命令が段階的に (帰納的に) 示されます。Vishkin (2011) で即時同時実行 (ICE) と呼ばれた XMT の背後にある基本的な並列抽象化は、同時実行可能な無数の命令が即座に実行されることです。ICE の結果、同時実行可能な次の命令が段階的に (帰納的に) 示されます。シリアルフォンノイマン型コンピュータ(現在までに成功した唯一の汎用プラットフォーム) を超えて、XMT の目標は、コンピュータサイエンスが再び数学的帰納法を単純な 1 行のコンピューティング抽象化で強化できるようにすることです。

ランダム アクセス マシン( RAM ) は、標準的なシリアル コンピューティングのアルゴリズムと複雑さを研究するためにコンピューター サイエンスで使用される抽象マシンモデルです。PRAM 計算モデルは、並列コンピューティングの並列アルゴリズムと複雑さを同様に研究するために、それらがまだ構築されていなかったときに導入された抽象並列マシン モデルです。研究者は、PRAM モデルの並列アルゴリズムに関する膨大な知識を開発しました。これらの並列アルゴリズムは、並列アルゴリズムの他のアプローチの基準から見ても単純であることでも知られています。

PRAM モデルに関するこの膨大な並列アルゴリズムの知識とそれらの相対的な単純さが、これらの並列アルゴリズムによってプログラミングできるコンピュータを構築する動機となりました。並列プログラマの生産性は、並列コンピュータの成功にとって非常に重要であると長い間考えられてきたため、アルゴリズムの単純さは重要です。

マルチコアコンピュータは、単一の集積回路ダイに統合された 2 つ以上のプロセッサ コアを中心に構築されています。これらは、汎用コンピューティングを含む多くのアプリケーション ドメインで広く使用されています。明示的マルチスレッド (XMT) は、数十、数百、数千のプロセッサ コアを備えたマルチコア コンピュータを構築およびプログラミングするためのコンピューティング パラダイムです。

2011 年と 2012 年に公開された実験作業では、最先端のマルチコア コンピューターで同じ問題を解く場合よりも、XMT プロトタイプで高度な PRAM アルゴリズムを実行する場合の方が大幅に高速化されることが実証されています。

2018 年に発表された研究によると、ロックステップ並列プログラミング (ICE を使用) は、XMT システム上で最速の手動調整されたマルチスレッド コードと同じパフォーマンスを実現できます。このような帰納的ロックステップ アプローチは、プログラマーにとって難しいことで知られる他の多くのコア システムのマルチスレッド プログラミング アプローチとは対照的です。

XMT パラダイムはUzi Vishkinによって導入されました。

明示的マルチスレッド (XMT) コンピューティング パラダイムは、複数のレベルの抽象化を統合します。

Shiloach & Vishkin (1982) によって導入された作業時間 (WT) (作業深度と呼ばれることもある) フレームワークは、並列アルゴリズムを概念化して記述するための簡単な方法を提供します。WT フレームワークでは、並列アルゴリズムは最初に並列ラウンドの観点から記述されます。各ラウンドでは、実行される操作が特徴付けられますが、いくつかの問題は抑制できます。たとえば、各ラウンドの操作数は明確である必要はなく、プロセッサについて言及する必要はなく、ジョブへのプロセッサの割り当てに役立つ可能性のある情報は考慮する必要はありません。次に、抑制された情報が提供されます。抑制された情報を含めることは、実際には、Brent (1974) によるスケジューリング定理の証明によって導かれます。WT フレームワークが便利なのは、並列アルゴリズムの初期記述を大幅に簡素化できる一方で、その初期記述で抑制された詳細を挿入することはそれほど難しくないことが多いためです。たとえば、WT フレームワークは、並列アルゴリズムの本 (PRAM モデル用) JaJa (1992) および Keller、Kessler、Traeff (2001)、およびクラス ノート Vishkin (2009) で基本的なプレゼンテーション フレームワークとして採用されました。Vishkin (2011) では、WT フレームワークと上記のより基本的な ICE 抽象化との単純な関係について説明しています。

XMT パラダイムは、プログラミング言語 C の小さな拡張である並列マルチスレッド プログラミング言語であるXMTCを使用してプログラミングできます。XMTパラダイムには、WT フレームワークでアルゴリズムをキャストすることから始まり、XMTC でプログラミングに進むプログラマーのワークフローが含まれています。

XMTマルチコアコンピュータシステムは、いくつかの特許を組み込んだマルチスレッドプログラムの実行時負荷分散機能を提供します。その1つ^[1]は、フォンノイマンアーキテクチャの中心となるプログラムカウンタの概念をマルチコアハードウェアに 一般化しています。

2007 年 1 月、全体のコンセプトを実証する 64 プロセッサ コンピュータ^[2] Paraleap ^[3]が完成しました。XMT のコンセプトは Vishkin ら (1998) と Naishlos ら (2003) で発表され、XMT 64 プロセッサ コンピュータは Wen と Vishkin (2008) で発表されました。並列プログラミングを容易にすることは、今日のコンピュータ サイエンスが直面している最大の課題の 1 つであるため、デモンストレーションでは、高校生から大学院生までの学生を対象に、PRAM アルゴリズムと XMTC プログラミングの基礎を教えることも目指しました。

Caragea & Vishkin (2011) が最大フロー問題について報告した実験作業、および Edwards と Vishkin (2012a、2012b) がグラフ接続性 (接続性 (グラフ理論) )、グラフ二重接続性 (二重接続グラフ)、およびグラフ三重接続性 (三重接続コンポーネント) の問題に関して発表した 2 つの論文では、並列アルゴリズムの文献にある最も高度なアルゴリズムのいくつかについて、XMT パラダイムは最先端のマルチコア コンピューターで同じ問題を実行する場合よりも 8 倍から 100 倍以上の高速化を実現できることが実証されました。報告された各高速化は、XMT プロトタイプのクロック サイクルを、最速のシリアル マシンで実行される最速のシリアル アルゴリズムと比較することによって得られました。

XMT のプロトタイピングは、Ghanim、Vishkin、Barua (2018) で最高潮に達し、ロックステップ並列プログラミング (ICE を使用) は、XMT システムで最速の手動調整されたマルチスレッド コードと同じパフォーマンスを実現できることが証明されました。この 2018 年の成果は、XMT プログラミングと、競合状態やその他の要求がプログラマーを困難にし、時には失敗させる傾向がある、ほぼすべての他のコア システムで採用されているマルチスレッド プログラミング アプローチとの違いを鮮明にしています (Vishkin (2014))。

• ブレント、リチャード P. (1974)、「一般的な算術式の並列評価」、Journal of the ACM、21 (2): 201–208、CiteSeerX  10.1.1.100.9361、doi :10.1145/321812.321815、S2CID  16416106。
• シロアチ、ヨッシ、ヴィシュキン、ウジ（1982）、「O（n ²  log  n）並列最大フローアルゴリズム」、アルゴリズムジャーナル、3（2）：128–146、doi：10.1016/0196-6774（82）90013-X。
• JaJa, Joseph (1992)、『並列アルゴリズム入門』、Addison-Wesley、ISBN 978-0-201-54856-3
• ケラー、ヨルグ。ケスラー、クリストフ・W. Traeff、Jesper L. (2001)、実践的な PRAM プログラミング、Wiley-Interscience、ISBN 978-0-471-35351-5
• Naishlos, Dorit; Nuzman, Joseph; Tseng, Chau-Wen; Vishkin, Uzi (2003)、「極細粒度並列プログラミング アプローチの最初の垂直プロトタイピングに向けて」(PDF)、Theory of Computing Systems、36 (5): 551–552、doi :10.1007/s00224-003-1086-6、S2CID  1929495。

• Torbert, Shane; Vishkin, Uzi; Tzur, Ron; Ellison, David (2010)、「高校生に並列アルゴリズム思考を教えることは可能か?」、第 41 回 ACM 技術シンポジウム コンピュータ サイエンス教育に関する議事録 - SIGCSE '10、p. 290、doi : 10.1145/1734263.1734363、ISBN 9781450300063。
• Vishkin, Uzi; Dascal, Shlomit; Berkovich, Efraim; Nuzman, Joseph (1998)、「命令並列処理のための明示的マルチスレッド (XMT) ブリッジング モデル」、Proc. 1998 ACM Symposium on Parallel Algorithms and Architectures (SPAA)、pp. 140–151。
• Vishkin, Uzi (2009)、「並列思考：基本的なデータ並列アルゴリズムとテクニック」、104ページ（PDF）、1992年以来メリーランド大学カレッジパーク校、テルアビブ大学、テクニオンで教えられている並列アルゴリズムのコースの講義ノート
• Wen, Xingzhi、Vishkin, Uzi (2008)、「FPGA ベースの PRAM オンチップ プロセッサのプロトタイプ」、Proc. 2008 ACM Conference on Computing Frontiers (Ischia、イタリア) (PDF)、pp. 55–66、doi :10.1145/1366230.1366240、ISBN 9781605580777、S2CID  11557669。
• Vishkin, Uzi (2011)、「単純な抽象化を使用して並列処理コンピューティングを再発明する」、Communications of the ACM、54 : 75–85、doi :10.1145/1866739.1866757。
• Caragea, George; Vishkin, Uzi (2011)、「簡単な発表: 並列最大フローの高速化」、Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)、pp. 131–134、doi :10.1145/1989493.1989511、ISBN 9781450307437、S2CID  5511743。
• Edwards, James A.; Vishkin, Uzi (2012a)、「グラフの連結性と双連結性に対するよりシンプルな並列プログラミングによる高速化」、2012 マルチコアおよびメニーコア向けプログラミング モデルとアプリケーションに関する国際ワークショップの議事録、pp. 103–114、doi :10.1145/2141702.2141714、ISBN 9781450312110、S2CID  15095569。
• Edwards, James A.; Vishkin, Uzi (2012b)、「簡単な発表: 並列グラフ三連結性の高速化」、Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)、pp. 190–192、doi :10.1145/2312005.2312042、ISBN 9781450312134、S2CID  16908459。
• Vishkin, Uzi (2014)、「汎用並列処理用のマルチコアハードウェアは壊れているか? 視点記事」、Communications of the ACM、57 (4): 35–39、doi :10.1145/2580945、S2CID  30098719。
• Ghanim, Fady; Vishkin, Uzi; Barua, Rajeev (2018 年 2 月)、「ICE を使用した簡単な PRAM ベースの高性能並列プログラミング」、IEEE Transactions on Parallel and Distributed Systems、29 (2): 377–390、doi : 10.1109/TPDS.2017.2754376、hdl : 1903/18521。

• XMT プロジェクトのホームページ。ソフトウェア リリース、オンライン チュートリアル、並列処理を教える資料へのリンクがあります。