平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算システム工学分野実行並列度の自動調整によるハードウェアトランザクショナルメモリの高速化学籍番号 24413571 氏名堀場匠一朗指導教員名津邑公暁 1 はじめにマルチコアを用いた並列プログラミングでは，一般的に共有リソースへのアクセス制御にロックが用いられてきたが，この場合デッドロックの発生や並列性の低下等の問題がある．そこで，ロックを用いない並行性制御機構としてトランザクショナルメモリ[1]（以下，TM）が提案されている．このTMをハードウェア上に実現したものはHTMと呼ばれ，一般にロックと比較して並列性が向上する．しかし，実行されるアプリケーション等によって適切な並列度は異なるため，効率的なスケジューリングが行われない場合にはTx（以下，Tx）のアボートやストールが頻発する可能性がある．そこで本研究では，この問題を効果的に解決する手法を提案する． 2 ハードウェアトランザクショナルメモリ HTMでは，Txとして定義された命令列のSerializability 図 1: 競合および無駄なストールの発生とAtomicityを保証するため，Tx内でアクセスされるメモその後実行されるwriteアクセスにより結局競合やリアドレスを監視する．そして複数のTx間で同一アドレアボートが発生してしまう．また，これにより無駄スへのアクセスが発生した場合Read afterWrite（RaW），なストールが発生する．そこで，アボートが引き起 Write after Read（WaR），Write after Write（WaW）の3 こされたアドレスへのそれ以降のアクセスを動的にパターンのアクセスが発生した場合に競合として検出さ逐次実行し，並列度を低減させることで競合やそれれる．競合が発生した場合，片方のTxの実行を中断するにともなうアボートを抑制する手法を提案する．（ストール）．さらに複数のTxがストールしている状態 4 実行並列度の向上によるストールの削減でデッドロックの可能性があると判断された場合，それに競合が発生する場合，これを検出したスレッドは，関わるどれか1つのTxの実行結果を破棄する（アボート）．実行中のTxをストールさせる必要がある．しかしなそしてアボートされたTxの開始時点の状態を復元し，Tx がら，図2の例のように，あるスレッドが特定のアを再実行する．このように，TMはロックによる排他制御ドレスにアクセスした後，同一アドレスに対して再と同等のセマンティクスを維持しつつ，競合が発生しない度アクセスすることなくコミットに至るのであれば，限りTxを並列に実行することができる．他スレッドがそのコミットに先行して当該アドレス 3 実行並列度の低減による競合の抑制上の値を書き換えたとしても，一貫性は保たれる．一般に，共有変数へのreadアクセスは，その後にそこで，競合が発生したとしても，競合相手がコミ writeアクセスをともなう場合が多く見られる．このットまで到達すると仮定して投機的に実行を継続すような操作を含むTxが複数のスレッドによって並ることで並列度を増大させる手法を提案する．行実行される場合，図1に示すように，両スレッドの readアクセスが競合とならず許可されたとしても， 5 評価 2つの提案手法をHTMの研究で広く用いられてい平成 25 年度創成シミュレーション工学専攻修士論文梗概集計算システム工学分野る３つのフェーズのうち，１つめのフェーズの実行終了後，その内部で変更された共有データはこれ以降参照されておらず，そのコミットに先立って他の図 2: 競合の発生による並列度の低下スレッドによるアクセスが投機的に実行可能となったためであると考えられる．最後に，(H) では (P1) るLogTM[2]に実装し，評価を行った．評価にはに対して総実行サイクル数の削減されたプログラム GEMS付属のmicrobench，SPLASH-2，STAMPから6 が多く見られた．種類のプログラムを用いた．実行サイクル数比を図3 6 おわりにに示す．図中の凡例はサイクル数の内訳を示してお本論文では，HTM におけるTx の実行時に悪影響り，Non-transはTx外の実行サイクル数，Good-trans を及ぼす競合パターンを解決するための手法を2 つはコミットされたTxの実行サイクル数，Bad-transは提案した．まず，アボートが引き起こされる原因とアボートされたTxの実行サイクル数，Abortingはアなったアドレスへのそれ以降のアクセスを逐次実行ボート処理に要したサイクル数，Backoffはバックオすることで，実行並列度をあえて低減させる手法をフ処理に要したサイクル数，Barrierはバリア同期に提案した．また，競合が発生したとしても投機的に要したサイクル数，Stallはストールに要したサイク実行を継続させることでTx の実行並列度を向上さル数，Waitは各提案手法で追加した待機処理に要しせる手法を提案した．これら2 つの手法を組み合わたサイクル数をそれぞれ示している．また，4 本のせたモデルは既存モデルに対して最大33．0%，16 グラフは左から順に(B)既存のLogTM，(P1)実行並列スレッドで平均3．2%の実行サイクル数を削減した．度の低減により競合を抑制する提案手法，(P2)実行今後の課題として，逐次実行の対象となるアクセス並列度の向上によりストールを削減する提案モデル，をより適切に決定する手法の考案および，投機的実 (H)2つの提案手法を組み合わせたモデルの結果を示行を適用するか否かを動的に判定できる機構を実現しており，(B)のサイクル数を1として正規化した．することが挙げられる．まず，(P1) ではPrioque において実行サイクル数 6 参考文献の大幅な減少率が目立つ．この原因を調査したとこ [1] Herlihy, M. and Moss, J. E. B.: Transactional ろ，プログラム中には共有変数に対する複合操作を Memory: Architectural Support for Lock-Free Data 行うTx が含まれており，提案手法の適用により同 Structures, Proc. 20th Annual Int’l Symp. On 一アドレスへの複合操作を並列実行することで発生 Computer Architecture, pp. 289–300 (1993). していたストールや，それに起因するアボートを十 [2] Moore, K. E., Bobba, J., Moravan, M. J., Hill, M. D. 分抑制できたことを確認した．また，(P2) におい and Wood, D. A.: LogTM: Log-based Transactional てContention に注目すると， Stall サイクルが大幅 Memory, Proc. 12th Int’l Symp. on High-Performance に削減された．これは，定義されたTx 中に存在す Computer Architecture, pp. 254–265(2006).