グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用

• Item type: Trans(1)
• 公開日: 2015-06-02
• タイトル: グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用
• タイトル / 言語: en
• タイトル: Using Hardware Transactional Memory for Efficiently Solving Graph Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 電気通信大学大学院情報理工学研究科
• 著者所属: 電気通信大学大学院情報理工学研究科
• 著者所属: 電気通信大学大学院情報理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者名: 小林, 哲; 佐藤, 重幸; 岩崎, 英哉
• 著者名(英): Tetsu, Kobayashi; Shigeyuki, Sato; Hideya, Iwasaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年，ハードウェアトランザクショナルメモリ（HTM）を搭載したCPUが市場にリリースされてきている．HTMのような投機的並列実行は，グラフアルゴリズムの並列処理に有効であることが知られている．そのため，HTMをグラフ問題の並列処理に利用することは有用と考えられる．しかし，現実的なグラフ問題の並列処理におけるトランザクションは，グラフの探索と更新をアトミックに行う必要があるため長くなりやすい．HTMではハードウェアの制限によって，このようなトランザクションを効率的に実行することは難しい．この問題を解決するため，本発表では，HTMのトランザクションを短縮する方法を提案する．提案方法では，計算処理とグラフの探索部分をトランザクションの外に出し，グラフの更新だけをトランザクション内で実行する．本発表では，HTMとしてIntel HaswellのRestricted Transactional Memoryを，グラフ問題としてDelaunay Mesh Refinementを取り上げ，提案する方法をpthreadsのmutexによる実装と比較して評価を行った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Nowadays, commodity processors are equipped with hardware transactional memory (HTM). Speculative parallel execution, which HTM adopts, is known to bring a performance gain in a wide range of graph algorithms. Therefore, the application of HTM to parallel graph processing seems promising. However, transactions in parallel graph processing for practical graph problems tend to be long because both graph traversal and updating have generally to be atomic. Executing such transactions efficiently is difficult because of hardware restrictions of HTM. To resolve this problem, we propose a method for shortening transactions of HTM. It makes calculation and graph traversal migrate from transactions and performs only graph updating within transactions. In this study, we use the Restricted Transactional Memory, which is a HTM functionality of the Intel Haswell architecture, and deal with Delaunay Mesh Refinement as an example graph problem. We evaluate the proposed method by comparing it with mutex locks in Phreads.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 8, 号 1, p. 16-16, 発行日 2015-06-02
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会