文献

J-GLOBAL ID：201502203453301344   整理番号：15A1005887

依存関係に基づく括出し法

Dependency Based Factoring

著者 (2件)： 那須孝志 (東京理大) ,  滝本宗宏 (東京理大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 115  号： 154(KBSE2015 9-27)  ページ： 57-62  発行年： 2015年07月15日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： SIMD実行によって引き起こされる分岐発散は,GPUの効率低下を引き起こす主要な問題である。この分岐発散を改善する手法として,括出しと呼ばれる最適化が有効であることが知られている。しかし,従来の括出し法では,依存関係をもつ複数の計算を括り出す際,新たな分岐の挿入を複数回必要とする場合があった。本稿では,演算子の一致性だけに基づいた従来の括出し法を拡張し,括り出す計算の依存関係も考慮した括出し法を提案する。その上で,より大きな依存構造をもつ計算を優先して括り出すことによって,従来法よりも多くの括出しを,一度の分岐挿入で実現する。また,各分岐の訪問順序を考慮して括り出すことで,入れ子になった分岐からの括出しも可能にする。提案手法の有用性を示すため,SPEC CPU2000とGPUの各ベンチマークを用いて実験を行ったところ,従来法と比較し最大で77%多くの括出しを実現し,最大で約12%の実行速度向上が得られることを確認した。(著者抄録)

シソーラス用語： *依存性 ,  *SIMD ,  マイクロプロセッサ ,  専用プロセッサ ,  データ表現 ,  計算機コード ,  枝分れ ,  発散 ,  プログラムメンテナンス ,  GPU【プロセッサ】 ,  コードクローン ,  リファクタリング
準シソーラス用語： SSA形式 ,  *依存関係 ,  分岐

分類 (1件)： 計算機システム開発  (JD02010R)

引用文献 (8件)：

• Bowen Alpern, Mark N Wegman, and F Kenneth Zadeck. Detecting equality of variables in programs. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 1-11. ACM, 1988.
• Daniel Cederman and Philippas Tsigas. A practical quicksort algorithm for graphics processors. In Algorithms-ESA 2008, pages 246-258. Springer, 2008.
• Shuai Che, Jeremy W Sheaffer, Michael Boyer, Lukasz G Szafaryn, Liang Wang, and Kevin Skadron. A characterization of the rodinia benchmark suite with comparison to contemporary cmp workloads. In Workload Characterization (IISWC), 2010 IEEE International Symposium on, pages 1-11. IEEE, 2010.
• Bruno Coutinho, Diogo Sampaio, Fernando Magno Quintao Pereira, and Wagner Meira Jr. Divergence analysis and optimizations. In Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques, PACT '11, pages 320-329, Washington, DC, USA, 2011. IEEE Computer Society.
• Tianyi David Han and Tarek S. Abdelrahman. Reducing branch divergence in gpu programs. In Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units, GPGPU-4, pages 3:1-3:8, New York, NY, USA, 2011. ACM.

タイトルに関連する用語 (2件)： 依存関係 ,  法