投機的マルチスレッド

スレッド レベル スペキュレーション( TLS ) は、投機的マルチスレッド、または投機的並列化とも呼ばれ、^{[1] は、別の独立した}スレッドでの通常の実行と並行して後で実行されることが予想されるコンピュータ コードの一部を投機的に実行する手法です。このような投機的スレッドでは、入力変数の値について仮定を行う必要があります。これらが無効であることが判明した場合、これらの入力変数に依存する投機的スレッドの部分は破棄して圧縮する必要があります。仮定が正しければ、スレッドを効率的にスケジュールすることができれば、プログラムはより短い時間で完了できます。

TLS はシリアルコードからスレッドを抽出し、安全なスレッドと並行して投機的に実行します。投機的なスレッドは、入力状態に関する推定が無効であることが判明した場合、破棄するか再実行する必要があります。これは、コンパイル時にスレッドの独立性が保証されないため、静的 (コンパイル時) 並列化技術では利用できない並列性を発見できる動的 (実行時)並列化技術です。この技術で全体の実行時間を短縮するという目標を達成するには、メインの安全なスレッドと並行して効率的に実行できる CPU リソースが必要です。^[2]

TLS は、楽観的に、コードの特定の部分 (通常はループ) が安全に並列実行できることを前提としています。そのために、反復空間を複数の異なるスレッドによって並列実行されるチャンクに分割します。ハードウェアまたはソフトウェア モニターは、シーケンシャルなセマンティクスが維持されるようにします (言い換えると、ループがシーケンシャルに実行されているかのように実行が進行します)。依存関係違反が発生した場合、投機的フレームワークは、並列実行全体を停止して再起動するか、問題のあるスレッドとその後続スレッドをすべて停止して再起動し、正しいデータを入力できるようにするか、問題のあるスレッドとその後続スレッドのみを停止して、そこから不正なデータを消費したスレッドのみを停止するかを選択できます。^[3]

• Yiapanis , Paraskevas; Brown, Gavin; Lujan , Mikel (2016). 「スレッドレベル並列処理のためのコンパイラ駆動型ソフトウェア投機」。ACM Transactions on Programming Languages and Systems。38 ( 2): 1–45。doi : 10.1145/2821505。

• Yiapanis, Paraskevas; Rosas-Ham, Demian; Brown, Gavin; Lujan, Mikel (2013). 「投機的並列化のためのソフトウェアランタイムシステムの最適化」ACM Transactions on Architecture and Code Optimization . 9 (4): 1–27. doi : 10.1145/2400682.2400698 .
• Llanos, Diego R. (2007). 「投機的並列化のコンテキストにおけるランダム増分アルゴリズムの新しいスケジューリング戦略」. IEEE Transactions on Computers . 56 (6): 839–852. CiteSeerX  10.1.1.77.5496 . doi :10.1109/TC.2007.1030. S2CID  3181243.
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012)。「民営化と削減のための投機的分離」(PDF)。第 33 回 ACM SIGPLAN プログラミング言語の設計と実装に関する会議の議事録。PLDI '12。pp. 359–370。doi :10.1145/2254064.2254107。
• Bhowmik, Anasua; Franklin, Manoj (2002)。「投機的マルチスレッド用の汎用コンパイラ フレームワーク」。並列アルゴリズムとアーキテクチャに関する第 14 回 ACM シンポジウムの議事録。SPAA '02。pp. 99–108。doi : 10.1145 /564870.564885。
• ブルーニング、デレク。デヴァバクトゥニ、シュリクリシュナ。アマラシンハ、サマン (2000)。 Softspec: ソフトウェアベースの投機的並列処理(PDF)。 FDDO-3。 1 ～ 10 ページ。
• Chen, Michael K.; Olukotun, Kunle (1998)。「シングルスレッド Java プログラムにおけるメソッド レベルの並列処理の活用」。並列アーキテクチャとコンパイル技術に関する国際会議。PACT 1998。pp. 176–184。doi : 10.1109 /PACT.1998.727190。
• Chen, Michael K.; Olukotun, Kunle (2003)。「Java プログラムを動的に並列化する Jrpm システム」。第 30 回コンピュータ アーキテクチャ国際シンポジウムの議事録。ISCA '03。pp. 434–446。doi : 10.1145 /859618.859668。
• Cintra, Marcelo; Llanos, Diego R. ( 2003)。「マルチプロセッサ上での効率的で堅牢なソフトウェア投機的並列化に向けて」。並列プログラミングの原理と実践に関する第 9 回 ACM SIGPLAN シンポジウムの議事録。PPoPP '03。pp. 13–24。doi :10.1145/781498.781501。
• Cook, Jonathan J. (2002). 「Java バイトコードの逆実行」.コンピュータジャーナル. 45 (6): 608–619. CiteSeerX  10.1.1.20.4765 . doi :10.1093/comjnl/45.6.608.
• Quinones, Carlos Garcia; Madriles, Carlos; Sanchez, Jesus; Marcuello, Pedro; Gonzalez, Antonio; Tullsen, Dean M. (2005)。「Mitosis Compiler: 事前計算スライスに基づく投機的スレッドのインフラストラクチャ」。プログラミング言語の設計と実装に関する 2005 ACM SIGPLAN 会議の議事録。PLDI '05。pp. 269–279。doi : 10.1145 /1065010.1065043。
• Hu, Shiwen; Bhargava, Ravi; John, Lizy Kurian (2003). 「投機的メソッドレベル並列処理の活用における戻り値予測の役割」(PDF) . JILP . 5 : 1–21.
• Kazi, Iffat H. (2000)。投機的マルチスレッドに基づく動的適応型並列化モデル (博士論文)。ミネソタ大学。pp. 1–188。
• Pickett, Christopher JF; Verbrugge, Clark (2005)。「SableSpMT: Java で投機的マルチスレッドを分析するためのソフトウェア フレームワーク」。ソフトウェア ツールとエンジニアリングのためのプログラム分析に関する第 6 回 ACM SIGPLAN-SIGSOFT ワークショップの議事録。PASTE '05。pp. 59–66。doi :10.1145/1108792.1108809。
• Pickett, Christopher JF; Verbrugge, Clark (2005)。「Java 言語および仮想マシン環境のソフトウェア スレッド レベルの推測」(PDF)。並列コンピューティングのための言語とコンパイラに関する第 18 回国際会議の議事録。LCPC '05。LNCS。第 4339 巻。pp. 304–318。doi : 10.1007/978-3-540-69330-7_21。
• Porter, Leo; Choi, Bumyong; Tullsen, Dean M. ( 2009)。「ハードウェア トランザクション メモリから投機的マルチスレッドへのパスのマッピング」。第 18 回並列アーキテクチャおよびコンパイル技術に関する国際会議。PACT '09。pp. 313–324。CiteSeerX 10.1.1.153.2503。doi :10.1109/  PACT.2009.37。
• Rundberg, Peter; Stenstrom, Per (2001). 「マルチプロセッサ向けの全ソフトウェア スレッド レベルのデータ依存性推測システム」(PDF) . JILP . 3 : 1–28.
• Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). 「スレッドレベルの推測に対する STAMPede アプローチ」. ACM Transactions on Computer Systems . 23 (3): 253–300. CiteSeerX  10.1.1.79.4317 . doi :10.1145/1082469.1082471. S2CID  10499545.
• Whaley, John; Kozyrakis, Christos (2005). 「プロファイル駆動型メソッドレベル投機的並列化のヒューリスティック」.国際並列処理会議. ICPP 2005. pp. 147–156. CiteSeerX  10.1.1.77.3989 . doi :10.1109/ICPP.2005.44.
• Renau, Jose; Strauss, Karin ; Ceze, Luis; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). 「エネルギー効率の高いスレッド レベルの投機」(PDF) . IEEE Micro . 26 (1): 80–91. doi :10.1109/MM.2006.11. S2CID  206472480.
• 吉添 一樹、松本 隆、平木 啓 (1998)。「JVM 上の投機的並列実行」。HPNCに関する英国ワークショップ。pp. 1–20。
• Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009)。「ソフトウェア スレッド レベルの推測のための軽量インプレース実装」( PDF)。アルゴリズムとアーキテクチャにおける並列処理に関する第 21 回年次シンポジウムの議事録。SPAA '09。pp. 1–10。doi :10.1145/1583991.1584050。