レジスタ生存グラフを用いたレジスタ割付けへのプロセッサ並列度の考慮

情報処理学会 Web Site 参考文献11件

書誌事項

タイトル別名
  • レジスタ セイゾン グラフ オ モチイタ レジスタ ワリツケ エ ノ プロセッサ ヘイレツド ノ コウリョ
  • Considering Parallelism of Processor to Register Allocation Based on Register Existence Graph

この論文をさがす

抄録

本稿では，命令レベル並列プロセッサを対象としたレジスタ割付けとコードスケジューリング技法を提案する．我々は，命令レベル並列性（ILP: Instruction Level Parallelism）を抽出する手法として，ガード付きプログラム依存グラフ（Guarded Program Dependence Graph）から生成されるレジスタ生存グラフを用いた手法を提案してきた．この手法は，レジスタアロケータとコードスケジューラの協調動作を考慮した手法の1 つであり，これまでの手法では抽出するのが困難な，高いILP を抽出できるという特徴を持っている．しかし，この手法は，プログラム中の変数の値を表す仮想レジスタどうしの生存区間の干渉を，プロセッサの並列度を考慮せずにレジスタ数以下に低減しているため，資源割付け時にレジスタ不足が起きる可能性があるという問題があった．このため，不必要なnop 命令や，レジスタの値をメモリに退避するスピルコードが挿入されてしまい，性能が低下してしまうことがあった．そこで，本手法ではプレスケジューリングを導入することにより，さらなるILP の抽出を図るとともに，コード割付け時のレジスタ不足問題を解決する．SPECint2000 の中から，特徴的なループを持つプログラムの最内ループに対して本手法を適用したところ，実行サイクル数において従来手法より平均8%の性能向上が見られた．

We propose a register allocation and a code scheduling technique for instruction level parallel processors. We have suggested a method using Register Existence Graph generated from Guarded Program Dependence Graph in order to extract instruction level parallelism (ILP) in a program. This method is one of the methods considering both of the register allocation and the code scheduling, and can extract higher ILP compared to the previous methods. However, this method has a possibility of register shortage at the resource allocation phase because it reduces the interference among values in the live variables as if the processor has an infinite number of execution units, and therefore, unnecessary NOP instructions or spill instructions that move register values to and from memory are inserted at the resource allocation phase. In this paper, we introduce a method using pre-scheduling in order to extract higher ILP and avoid the above mentioned register shortage. The performance of this method is about 8% better than that of a previous method when applying it to some loop-intensive programs in the SPECint2000 benchmarks.

収録刊行物

参考文献 (11)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ