ログエントリ数を考慮したLogTMの アボート対象選択手法とその評価 浅井宏樹† 津邑公暁† 松尾啓志† ○ 　†名古屋工業大学

研究背景 マルチコアを用いた並列プログラミングの需要が高まる 消費電力や配線遅延の相対的な増大 単一コアの性能向上が困難 マルチスレッドによる並列実行 プロセッサ全体のスループットの向上 共有メモリ型並列プログラミングでは共有リソースの同期が必要 ロックが一般的 ロックの問題点 並列性が低下 デッドロックが発生する危険性 プログラム設計が困難 2 　Transactional Memory：ロックを使わない同期機構

発表の流れ 既存手法 LogTM 提案手法 ログエントリ数を考慮したアボート対象の選択 競合度を考慮したアボート対象の選択 評価 3

Transactional Memoryをハードウェア上に実現 トランザクションを投機的に実行する 投機的実行に失敗したときは処理をやり直す ログ領域に上書きされる前の値を退避 LogTM: Log-based Transactional Memory 4 cache ログ 投機実行成功 ログを破棄 上書き Shared Memory コミット

Transactional Memoryをハードウェア上に実現 トランザクションを投機的に実行する 投機的実行に失敗したときは処理をやり直す ログ領域に上書きされる前の値を退避 Log-based Transactional Memory 5 cache ログ 投機実行成功 Shared Memory cache ログ 再実行 アボート

trans2 LogTM: 競合の検出と解決 6 thread1 thread1 thread2 cache cache Directory 130 x=8 y=32 y=16 x=64 Shared Memory trans1 0 1 x 8 thread2 y 0 1 y 32 0 1 y 32 再実行 y 0 1 y 16 片方を アボート ストール から復帰 … 0 1 y 4 アボート trans2 129

発表の流れ 既存手法 LogTM 提案手法 ログエントリ数を考慮したアボート対象の選択 競合度を考慮したアボート対象の選択 評価 7

提案: ログエントリ数を考慮したアボート対象選択 トランザクションのコミット優先度 両者を考慮してアボート対象を選択する C(tr) = k ・ L(tr) + T(tr) k ： 1つのログエントリを書き戻すときにかかるOvh L(tr) ： ログエントリ数 T(tr) ： 開始してからアボートした時点までの経過時間 8

提案: ログエントリ数を考慮したアボート対象選択 トランザクションの優先度 9 競合

ログエントリ数の通信 デッドロック検出時にC(tr)を計算 nack受信時にデッドロック検出 nackにログエントリ数付加 10

デッドロック検出時にC(tr)を計算 nack受信時にデッドロック検出 nackにログエントリ数付加 C(tr)を計算して比較 nack受信者をアボートさせる nack送信者をアボートさせる アボートリクエストにより通知 アボート対象の選択 11 129 x=8 y=x trans1 アボート

デッドロック検出時にC(tr)を計算 nack受信時にデッドロック検出 nackにログエントリ数付加 C(tr)を計算して比較 nack受信者をアボートさせる nack送信者をアボートさせる アボートリクエストにより通知 アボート対象の選択 12 y=16 x=y trans2 130 アボート

発表の流れ 既存手法 LogTM 提案手法 ログエントリ数を考慮したアボート対象の選択 競合度を考慮したアボート対象の選択 評価 13

提案: 競合度を考慮したアボート対象選択 トランザクションごとに待たせている数が異なる より多く待たせているものを優先してコミット 待たせているトランザクションの数を考慮して選択 競合度 D(tr) 14 D(1)=3 D(2)=5 アボート

競合ビットによる競合度の算出 nack thread1 thread2 thread3 1 1 1 trans1 trans2 trans3 15 待たせている情報を保持 各スレッドIDに対応 セットされた1の数を競合度とする requestに付加 現在の競合状況を通知 競合情報の引き継ぎ 受信した競合ビットと論理和をとる ストール関係の連鎖に対応

デッドロック検出時に比較 同じ値を持ってしまう 更新前の競合ビットを保持 nackに付加して通知 競合度を算出して比較 競合度の比較 誰を待たせているかを 明確にする nack 1 1 1 trans1 trans2 trans3 1 16

提案: 競合度を考慮したアボート対象選択 生存優先度 P(tr) 低いトランザクションをアボート対象として選択 P(tr) = ｗC・ C(tr) + ｗD・ D(tr) ｗC，ｗD　: 重み 17

発表の流れ 既存手法 LogTM 提案手法 ログエントリ数を考慮したアボート対象の選択 競合度を考慮したアボート対象の選択 評価 18

評価環境 シミュレーション環境 シミュレータ Virtutech Simics*： フルシステムシミュレータ(SPARC-V9，Solaris10を選択) GEMS**： メモリシステムシミュレータ シミュレーションパラメタ 並列度：31 標本数：10，信頼区間：95% ベンチマークプログラム SPLASH-2 (Barnes, Raytrace, Cholesky) 19 * Magnusson, P. S. and et al: Simics: A Full System Simulation Platform, Computer,Vol. 35, pp. 50–58 (2002). ** Martin, M.M., Sorin, D.J., Beckmann, B.M., Marty, M.R., Xu, M., Alameldeen,A.R., E.Moore, K., Hill, M.D.and Wood., D.A.: Multifacet’s General Executiondriven Multiprocessor Simulator (GEMS) Toolset, Computer Architecture News, ACM, pp.254–265 (2005).

評価結果 20 Barnes Raytrace Cholesky Ratio of cycles

考察 ログエントリ数の差分 デッドロックしたトランザクション から計測した差分 アボート当りの書き戻し数 1回のアボート当りに書き戻された ログエントリ数の平均値 ストール回数 全てのトランザクションで発生した ストールの回数の和 21

まとめと今後の課題 アボート対象を選択する手法の提案 ログエントリ数を考慮した選択 競合度を考慮した選択 今後の課題 プログラムによって適切な重みが異なっている 原因を調査する 重みを動的に決定する手法を検討する 他のプログラムにおいて提案手法を適用した場合の 影響について詳しく調査する 22