{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00214569","sets":["934:935:10774:10775"]},"path":["10775"],"owner":"44499","recid":"214569","title":["Scalar Replacement Considering Branch Divergence"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-01-05"},"_buckets":{"deposit":"721da6ec-3288-443a-b774-71df3fe9807e"},"_deposit":{"id":"214569","pid":{"type":"depid","value":"214569","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Scalar Replacement Considering Branch Divergence","author_link":["551523","551522","551521","551520"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Scalar Replacement Considering Branch Divergence"},{"subitem_title":"Scalar Replacement Considering Branch Divergence","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[通常論文] GPU, branch divergence, code optimization, scalar replacement, speculative code motion","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2022-01-05","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Information Sciences, Tokyo University of Science"},{"subitem_text_value":"Department of Information Sciences, Tokyo University of Science"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Information Sciences, Tokyo University of Science","subitem_text_language":"en"},{"subitem_text_value":"Department of Information Sciences, Tokyo University of Science","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"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/214569/files/IPSJ-TPRO1501004.pdf","label":"IPSJ-TPRO1501004.pdf"},"date":[{"dateType":"Available","dateValue":"2024-01-05"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TPRO1501004.pdf","filesize":[{"value":"937.4 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":"6e7e4a94-ec1e-4471-8b81-0d4a3dbb272d","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Junji, Fukuhara"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Munehiro, Takimoto"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Junji, Fukuhara","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Munehiro, Takimoto","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":"GPU with the Single Instruction Multiple Data (SIMD) execution model enables a program to work efficiently. However, the efficiency may decrease because of branch divergence that occurs when SIMD threads follow different paths in some branches. Once the divergence occurs, some threads must wait until completion of the execution of the others. Thus, it is important to reduce branch divergence to improve the efficiency of GPU programs. On the other hand, branch divergence may be increased by some traditional code optimizations based on code motion such as partial redundancy elimination (PRE) and scalar replacement (SR). These methods insert some expressions into some paths, on which insertion points may be included in divergent branches. That is, the insertion may increase branch divergence, which may result in the decrease of execution efficiency of GPU programs. In this paper, we propose a new SR approach, called Speculative SR based on Question Propagation (SSRQP), which not only removes redundant memory accesses but also reduces branch divergence. SSRQP achieves SR based on speculative code motion, which not only eliminates inter-iteration redundant memory accesses without increasing branch divergence but also decreases branch divergence that originally exists through hoisting memory accesses in true and false sides of a divergent branch out of it. To prove the effectiveness of our method, we have conducted experiments through applying it to some benchmarks with divergent branches. The experimental results show that it can improve the efficiency about 40% in the best case in comparison with traditional techniques.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"GPU with the Single Instruction Multiple Data (SIMD) execution model enables a program to work efficiently. However, the efficiency may decrease because of branch divergence that occurs when SIMD threads follow different paths in some branches. Once the divergence occurs, some threads must wait until completion of the execution of the others. Thus, it is important to reduce branch divergence to improve the efficiency of GPU programs. On the other hand, branch divergence may be increased by some traditional code optimizations based on code motion such as partial redundancy elimination (PRE) and scalar replacement (SR). These methods insert some expressions into some paths, on which insertion points may be included in divergent branches. That is, the insertion may increase branch divergence, which may result in the decrease of execution efficiency of GPU programs. In this paper, we propose a new SR approach, called Speculative SR based on Question Propagation (SSRQP), which not only removes redundant memory accesses but also reduces branch divergence. SSRQP achieves SR based on speculative code motion, which not only eliminates inter-iteration redundant memory accesses without increasing branch divergence but also decreases branch divergence that originally exists through hoisting memory accesses in true and false sides of a divergent branch out of it. To prove the effectiveness of our method, we have conducted experiments through applying it to some benchmarks with divergent branches. The experimental results show that it can improve the efficiency about 40% in the best case in comparison with traditional techniques.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌プログラミング（PRO）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2022-01-05","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicVolumeNumber":"15"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":214569,"updated":"2025-01-19T16:33:47.182430+00:00","links":{},"created":"2025-01-19T01:15:22.815289+00:00"}