述語付きソフトウェア・パイプラインへのSpiral Graphによるレジスタ割付け

• Item type: Trans(1)
• 公開日: 2002-09-15
• タイトル: 述語付きソフトウェア・パイプラインへのSpiral Graphによるレジスタ割付け
• タイトル / 言語: en
• タイトル: Register Allocation for Predicated Software Pipelining Using Spiral Graph
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 通常論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 筑波大学工学研究科／現在，茨城県工業技術センター
• 著者所属: 佐賀大学理工学部
• 著者所属: 筑波大学電子・情報工学系
• 著者所属(英): en
• 著者所属(英): Doctoral Program in Engineering, University of Tsukuba/Presently with Industrial Technology Institute of Ibaraki Prefecture
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Saga University
• 著者所属(英): en
• 著者所属(英): Institute of Information Sciences and Electronics, University of Tsukuba
• 著者名: 糸賀, 裕弥; 山下, 義行; 田中, 二郎
• 著者名(英): Hiroya, Itoga; Yoshiyuki, Yamashita; Jiro, Tanaka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ソフトウェア・パイプラインによる最適化をハードウェアで補助する仕組みとして，レジスタ改名機構と述語付き命令実行機構がある．レジスタ改名機構向けのレジスタ割付け手法としてSpiralGraph を用いた方法が提案されているが，述語付き命令実行機構を備えた場合の割付け方法について詳しい解析がなされていなかった．本論文では，それら2 つの補助機能を備えたIA-64 のようなアーキテクチャに対するレジスタ割付け手法として，述語付きSpiral Graph を提案する．述語付きSpiral Graph は，従来のトラックを述語の値に応じた副トラックの集合と見なすことで，述語が異なる命令で別に定義される生存区間を適切に表現することができる．述語付きSpiral Graph を用いることで，必要レジスタ数を最小とするレジスタ割付けが多項式時間で行える．提案するアルゴリズムでは，必要レジスタ数の下界であるWmax 本のレジスタで割付けが行えるか判定を行い，必要レジスタ数がWmax 本の場合の割付け結果が得られ．そうでない場合には，Wmax +1 本での割付け結果が得られる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Register renaming and predicated execution are the hardware facilities to support software pipelining. Spiral Graph has been proposed to allocate registers for the architectures with register renaming. However, the original Spiral Graph cannot naturally express the predi-cated execution. In this paper, authors propose Predicated Spiral Graph for the architectures that support software pipelining, such as Intel IA-64 architecture. Predicated Spiral Graph extends a track on the original Spiral Graph to multiple sub-tracks, each of which represents each value of the predicates. The live ranges, which are defined and used in the predicated execution, are allocated to the sub-tracks. Authors propose the algorithm on Predicated Spiral Graph, which yields the optimal number of the required registers in polynomial time. This algorithm judges whether the number of the required registers equals to Wmax, a lower boundary of them, and yields a result of allocation. Even if the check fails, the algorithm yields a result which requires Wmax +1.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 43, 号 SIG08(PRO15), p. 62-71, 発行日 2002-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会