| Presentation | 2015-07-23 Dependency Based Factoring Takashi Nasu, Munehiro Takimoto, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Branch divergence caused by Single Instruction Multiple Data (SIMD) execution extremely decreases the performance of GPU. One of effective optimizations for suppressing the branch divergence is code factoring, which is a program transformation factoring out instructions with identical operators on branch paths as a common instruction. In general, the factorization of several instructions may require introduction of some new branches to hold dependencies of the instructions at the sacrifice of the optimization effect. In other words, the naive factorization of instructions may prevent subsequent instructions from being factored out through a single branch insertion. In this paper, we propose a new code factoring approach that not only detects instructions with identical operators, but also considers their dependencies. Our approach preferentially factors out the larger sequence of instructions with the same dependence structure, so that more instructions can be factored out through a single branch insertion. Furthermore, the factorization manner enables factoring instructions across nested branches. In order to prove the effectiveness of our approach, we have conducted experiments for the number of instructions factored out and the improvement of execution efficiency on SPEC CPU2000 and GPU benchmarks respectively. Their results show that our approach increases instructions factored out as much as 77% compared with the naive approach, and show that it maximally achieves speed-up by almost 12% on GPU. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | GPU / Branch divergence / Code factoring / Code clone / Congruence detection |
| Paper # | SS2015-20,KBSE2015-13 |
| Date of Issue | 2015-07-15 (SS, KBSE) |
| Conference Information | |
| Committee | KBSE / SS / IPSJ-SE |
|---|---|
| Conference Date | 2015/7/22(3days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Tadashi Iijima(Keio Univ.) / Shoji Yuen(Nagoya Univ.) |
| Vice Chair | Shigeo Kaneda(Doshisha Univ.) / Kazuhiro Ogata(JAIST) |
| Secretary | Shigeo Kaneda(Nihon Univ.) / Kazuhiro Ogata(Osaka Univ.) / (Tokyo Inst. of Tech.) |
| Assistant | Shinpei Ogata(Shinshu Univ.) / Hiroaki Hashiura(Nippon Inst. of Tech.) / Yoshiki Higo(Osaka Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Knowledge-Based Software Engineering / Technical Committee on Software Science / Special Interest Group on Software Engineering |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Dependency Based Factoring |
| Sub Title (in English) | |
| Keyword(1) | GPU |
| Keyword(2) | Branch divergence |
| Keyword(3) | Code factoring |
| Keyword(4) | Code clone |
| Keyword(5) | Congruence detection |
| 1st Author's Name | Takashi Nasu |
| 1st Author's Affiliation | Tokyo University of Science(TUS) |
| 2nd Author's Name | Munehiro Takimoto |
| 2nd Author's Affiliation | Tokyo University of Science(TUS) |
| Date | 2015-07-23 |
| Paper # | SS2015-20,KBSE2015-13 |
| Volume (vol) | vol.115 |
| Number (no) | SS-153,KBSE-154 |
| Page | pp.pp.57-62(SS), pp.57-62(KBSE), |
| #Pages | 6 |
| Date of Issue | 2015-07-15 (SS, KBSE) |