ループへの効果的な投機的実行適用手法

• Item type: SIG Technical Reports(1)
• 公開日: 2002-03-07
• タイトル: ループへの効果的な投機的実行適用手法
• タイトル / 言語: en
• タイトル: An Efficient Speculative Execution Scheme for Loops
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 早稲田大学理工学部
• 著者所属: アドバンスト並列化コンパイラ研究会
• 著者所属(英): en
• 著者所属(英): School of Science and Engineering, Waseda Univ.
• 著者所属(英): en
• 著者所属(英): Advanced Parallelizing Compiler Project
• 著者名: 石川, 隼輔; 山名, 早人
• 著者名(英): Shunsuke, Ishikawa; Hayato, Yamana
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，ループに対して投機的実行を効果的に適用する手法について提案し，SPECcpu95 ベンチマークのcompress プログラムを用いて有効性を検証した．一般的に，ループはプログラムの実行時間の大部分を占めていることから，ループ並列化によるプログラム速度向上率は高い。しかし、従来の並列化手法では、データ依存が静的に解析できない場合、データ依存が存在すると仮定し解析を進める。このため、たとえば，実際には一万回に一回しかループ運搬依存（LCD)が発生しないようなループであっても並列化することができない．しかし，このようなループに対して投機的実行を適用することにより，プログラムを高速に実行することが可能となる．本稿では、従来考慮されてこなかった投機的実行失敗時の復帰処理に必要なオーバーヘッドをパラメータとして取り入れることにより，投機的実行の効果が期待できる部分のみを選択的に投機的実行する方式を提案する。提案手法は、復帰処理オーバーヘッドの他、LCD が実行時にどの程度の確立で存在するのかを表すLCD 存在率と、投機的実行開始位置とをパラメータとし，選択的な投機的実行を実現する。本手法をcompress プログラムに適用した結果，現状では3倍の速度低下がみられた。このため、速度低下の原因を解析し，その原因を解決するための新たな投機的実行適用手法も提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an efficient speculative execution scheme for loops, and have confirmed the usefullness of the scheme using the compress program from SPECcup95 benchmark. Generally, since the execution time of loops holds the large portion of the total execution time, the loop parallelization scheme improves the program performance, dramatically. However, when the data dependence cannnot be analyzed statically, the conventional parallelization scheme assumes that the data dependence exists. For this reason, such a loop cannot be parallelized even if the loop carried dependence(LCD) occurs only in 10,000 times, dynamically. However, the speculative execution scheme has been known to speedup such a loop. In this paper, we propose the scheme to apply the speculative execution alternatively only to the portion expected to be speeduped effectively, using the overhead parameter required for the book-keeping process when the speculation fails. Such overhead has not been considered on conventional speculative execution schemes. The proposed scheme enables the alternative speculative exection using the overhead parameter for book-keeping, the LCD existence probability, and the timing of the speculative execution initiation. As a results, in the present stage, the execution speed is fell down to one third. To solve this problem, we also propose a new speculative execution.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2002, 号 22(2001-HPC-089), p. 121-126, 発行日 2002-03-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会