最適なロールバック・ポイントを選択するトランザクショナル・メモリ

元データ 2010-07-27

概要

並列プログラミングにおいて,ロックを用いた同期機構が広く用いられている.しかし,ロックを用いると,デッドロックや不要なロックによる並列性の低下が生じることがある.一方で,ロックを用いるよりも容易に速いプログラムを書ける,トランザクショナル・メモリを用いた同期機構が提案されている.トランザクショナル・メモリを用いた並列プログラミングでは,プログラマが排他制御したい一連の処理をトランザクションとして指定する.多くのトランザクショナル・メモリの手法では,トランザクションは一つのスレッドで投機実行され,不可分に実行されているかのように実行される.もし並列に実行されている他スレッドの処理とトランザクションの処理が競合した場合,トランザクションをロールバックし,初めから再実行する.トランザクションのロールバックでは,再実行される命令数が多いと,大きなペナルティとなることがある.そこで,トランザクションの開始点に戻るのではなく,その途中に戻る部分ロールバックを行うことでペナルティを削減する手法が提案されている.しかし,これらの手法では,常に最適なチェックポイントへロールバックするわけではない.本稿では,過去の競合アドレスへのアクセスをチェックポイントとし,最適なチェックポイントを選択する手法を提案する.数の制限なしにチェックポイントを取り,最適なチェックポイントを選択することで,投機失敗時のペナルティを削減する.開始点のみをチェックポイントとした最適なチェックポイントを選択する手法の評価では,最大 9:2 倍の性能向上を達成できた.

著者

五島 正裕 東京大学情報理工学系研究科
坂井 修一 東京大学大学院工学系研究科
塩谷 亮太 東京大学大学院情報理工学系研究科
五島 正裕 東京大学大学院情報理工学系研究科
坂井 修一 東京大学
塩谷 亮太 東京大学情報理工学系研究科:日本学術振興会
伊藤 悠二 東京大学大学院情報理工学系研究科
五島 正裕 東京大学 情報理工学系研究科
坂井 修一 東京大学 情報理工学系研究科
ハイハー グェン 京都大学情報学研究科
坂井 修一 東京大学大学院 情報理工学系研究科

関連論文

▼もっと見る