WEKO3
アイテム
Scalar Replacement Considering Branch Divergence
https://ipsj.ixsq.nii.ac.jp/records/214569
https://ipsj.ixsq.nii.ac.jp/records/214569d0d52cb5-03e1-4555-8307-defd4118726f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TPRO1501004.pdf (937.4 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-01-05 | |||||||||
| タイトル | ||||||||||
| タイトル | Scalar Replacement Considering Branch Divergence | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Scalar Replacement Considering Branch Divergence | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| キーワード | ||||||||||
| 主題Scheme | Other | |||||||||
| 主題 | [通常論文] GPU, branch divergence, code optimization, scalar replacement, speculative code motion | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||
| 資源タイプ | journal article | |||||||||
| 著者所属 | ||||||||||
| Department of Information Sciences, Tokyo University of Science | ||||||||||
| 著者所属 | ||||||||||
| Department of Information Sciences, Tokyo University of Science | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Information Sciences, Tokyo University of Science | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Department of Information Sciences, Tokyo University of Science | ||||||||||
| 著者名 |
Junji, Fukuhara
× Junji, Fukuhara
× Munehiro, Takimoto
|
|||||||||
| 著者名(英) |
Junji, Fukuhara
× Junji, Fukuhara
× Munehiro, Takimoto
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.30(2022) (online) ------------------------------ |
|||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 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. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.30(2022) (online) ------------------------------ |
|||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA11464814 | |||||||||
| 書誌情報 |
情報処理学会論文誌プログラミング（PRO） 巻 15, 号 1, 発行日 2022-01-05 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 1882-7802 | |||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
