{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00142293","sets":["934:935:8226:8227"]},"path":["8227"],"owner":"11","recid":"142293","title":["グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用"],"pubdate":{"attribute_name":"公開日","attribute_value":"2015-06-02"},"_buckets":{"deposit":"4f84fe73-6af0-4977-81fa-2dd25ced0982"},"_deposit":{"id":"142293","pid":{"type":"depid","value":"142293","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用","author_link":["210639","210640","210638","210642","210643","210641"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"グラフ問題を効率的に解くためのハードウェアトランザクショナルメモリの利用"},{"subitem_title":"Using Hardware Transactional Memory for Efficiently Solving Graph Problems","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[発表概要]","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2015-06-02","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"電気通信大学大学院情報理工学研究科"},{"subitem_text_value":"電気通信大学大学院情報理工学研究科"},{"subitem_text_value":"電気通信大学大学院情報理工学研究科"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Informatics and Engineering, The University of Electro-Communications","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics and Engineering, The University of Electro-Communications","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics and Engineering, The University of Electro-Communications","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/142293/files/IPSJ-TPRO0801009.pdf"},"date":[{"dateType":"Available","dateValue":"2017-06-02"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO0801009.pdf","filesize":[{"value":"96.8 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"15"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"118e23c8-6a98-4f0b-8105-e53032409dc9","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2015 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小林, 哲"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"佐藤, 重幸"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"岩崎, 英哉"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tetsu, Kobayashi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Shigeyuki, Sato","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hideya, Iwasaki","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464814","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7802","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"近年，ハードウェアトランザクショナルメモリ（HTM）を搭載したCPUが市場にリリースされてきている．HTMのような投機的並列実行は，グラフアルゴリズムの並列処理に有効であることが知られている．そのため，HTMをグラフ問題の並列処理に利用することは有用と考えられる．しかし，現実的なグラフ問題の並列処理におけるトランザクションは，グラフの探索と更新をアトミックに行う必要があるため長くなりやすい．HTMではハードウェアの制限によって，このようなトランザクションを効率的に実行することは難しい．この問題を解決するため，本発表では，HTMのトランザクションを短縮する方法を提案する．提案方法では，計算処理とグラフの探索部分をトランザクションの外に出し，グラフの更新だけをトランザクション内で実行する．本発表では，HTMとしてIntel HaswellのRestricted Transactional Memoryを，グラフ問題としてDelaunay Mesh Refinementを取り上げ，提案する方法をpthreadsのmutexによる実装と比較して評価を行った．","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"16","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicPageStart":"16","bibliographicIssueDates":{"bibliographicIssueDate":"2015-06-02","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"8"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":142293,"updated":"2025-01-20T19:03:10.845072+00:00","links":{},"created":"2025-01-19T00:19:45.779698+00:00"}