スライドレジスタ割付問題の厳密解法

• Item type: Journal(1)
• 公開日: 1999-09-15
• タイトル: スライドレジスタ割付問題の厳密解法
• タイトル / 言語: en
• タイトル: An Exact Algorithm of Slide - Register Allocation Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 言語処理系
• 著者所属: 筑波大学工学研究科
• 著者所属: 筑波大学電子・情報工学系
• 著者所属: 図書館情報大学図書館情報学部
• 著者所属(英): en
• 著者所属(英): Doctoral Program in Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Institute of Information Sciences and Electronics, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): University of Library and Information Science
• 著者名: 秡川友宏; 山下, 義行; 中田, 育男
• 著者名(英): Tomohlro, Haraikawa; Yoshiyuki, Yamashita; Ikuo, Nakata
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: レジスタ#0 #1 ...を#(K+0) #(K+1) ...にいっせいに改名する命令を持つプロセッサを仮定し いっせいに改名されるレジスタをスライドレジスタとよぶことにする. このようなプロセッサを採用した計算機の1つとしては 筑波大学のCP-PACSがあげられる. 従来のレジスタにおいては ループプログラムのレジスタ割付問題はCyclic Arc Graphの彩色問題として定式化できることが知られているが スライドレジスタに関してはその割付問題の性質が詳しくは分かっていなかった. 本論文では この問題を巡回セールスマン問題の変形として定式化し この問題に厳密解決を与える. また 厳密解決で実際に最適解を求め その求解時間をもとに本厳密解法の実用化の方法を提案する. さらに 本厳密解法を近似解法の評価に応用する. 筆者らは先に近似解法を提案・評価しているが 提案時の評価は55%程度の最適性しか保証できていなかった. 最適解を利用した新たな評価により 同解法が85%以上の例題に対して最適解を与えていたことが確認できた.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Assume a processor with an instruction which renames registers #O, #1,...respectively to #(K+0), #(K+1),...all at once is given, and call these registers slide-registers. CP-PACS in the University of Tsukuba is one of the computers that utilize such a processor. For conventional registers, it is known that the register allocation problem of a loop program can be formulated as the coloring problem of Cyclic Arc Graph. However, for the slide-registers, this allocation problem has not been studied in detail. This paper shows an exact algorithm of this problem by formulating it as a variation of Traveling Salesman Problem. Moreover, based on the solution time obtained by solving problems with this exact algorithm, this paper presents a practical application method of this formulation. Furthermore, this exact algorithm is applied to the evaluation of approximation algorithms. In our recent work, an approximation algorithm was proposed, but our evaluation method there could only assure its optimality as 55%. The new evaluation using the optimal solutions revealed that the approximation algorithm proposed formerly was giving the optimal solution to more than 85% of examples.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 40, 号 9, p. 3524-3536, 発行日 1999-09-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764