待機アルゴリズムの改良によるトランザクショナルメモリの高速化

Info

山田 遼平, 橋本 高志良, 津邑 公暁 : "待機アルゴリズムの改良によるトランザクショナルメモリの高速化", 情処研報 (SWoPP2014) ,pp1--8 (Jul. 2014) 予稿

Abstract

マルチコア環境では，共有変数へのアクセス調停のためにロックを用いることが一般的である．しかし，ロックには並列性の低下やデッドロックの発生などの問題があるため，これに代わる並行性制御機構としてトランザクショナルメモリ（TM）が提案されている．この機構のハードウェア実装であるハードウェア・トランザクショナルメモリ（HTM）では，アクセス競合が発生しない限りトランザクションが投機実行される．HTM では投機実行が失敗した場合，再び競合が発生することをを防ぐため，トランザクションの再実行までに待機時間を設定するアルゴリズムが採用されている．しかし，既存の待機アルゴリズムでは適切な待機時間を設定できていないため，再び競合が発生して投機実行の失敗が繰り返されることで，HTM の性能が著しく低下してしまう場合がある．本稿では，この待機アルゴリズムを改良し，トランザクションの実行状況に応じた待機処理を行うことでHTM を高速化する手法を提案する．シミュレーションによる評価の結果，提案手法により最大59.9%，16 スレッドで平均11.2%の高速化を確認した．