著者

石川 隼輔 山名 早人

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告計算機アーキテクチャ(ARC) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.22, pp.121-126, 2002-03-07

---

本稿では,ループに対して投機的実行を効果的に適用する手法について提案し,SPECcpu95 ベンチマークのcompress プログラムを用いて有効性を検証した.一般的に,ループはプログラムの実行時間の大部分を占めていることから,ループ並列化によるプログラム速度向上率は高い。しかし、従来の並列化手法では、データ依存が静的に解析できない場合、データ依存が存在すると仮定し解析を進める。このため、たとえば,実際には一万回に一回しかループ運搬依存(LCD)が発生しないようなループであっても並列化することができない.しかし,このようなループに対して投機的実行を適用することにより,プログラムを高速に実行することが可能となる.本稿では、従来考慮されてこなかった投機的実行失敗時の復帰処理に必要なオーバーヘッドをパラメータとして取り入れることにより,投機的実行の効果が期待できる部分のみを選択的に投機的実行する方式を提案する。提案手法は、復帰処理オーバーヘッドの他、LCD が実行時にどの程度の確立で存在するのかを表すLCD 存在率と、投機的実行開始位置とをパラメータとし,選択的な投機的実行を実現する。本手法をcompress プログラムに適用した結果,現状では3倍の速度低下がみられた。このため、速度低下の原因を解析し,その原因を解決するための新たな投機的実行適用手法も提案する.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.