レジスタ割り当てにおける循環区間グラフの彩色アルゴリズムについて

• Item type: SIG Technical Reports(1)
• 公開日: 1995-01-23
• タイトル: レジスタ割り当てにおける循環区間グラフの彩色アルゴリズムについて
• タイトル / 言語: en
• タイトル: A Coloring Algorithm of Cyclic Interval Graphs for Register Allocation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 三重大学工学部
• 著者所属: 三重大学工学部
• 著者所属: 三重大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Mie University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Mie University
• 著者名: 紀伊, 康之; 大山口, 通夫; 太田, 義勝
• 著者名(英): Yasuyuki, Kii; Michio, Oyamaguchi; Yoshikatsu, Ohta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: レジスタ割り当ては、効率の良いコードを生成するため、コンパイラにおいて重要な最適化技術のひとつである。構造化されたプログラムのレジスタ割り当て問題は、循環区間グラフの彩色問題に還元できる。この問題は一般にNP完全であるが、最近ファットカバー・アルゴリズムと呼ばれる効率の良い発見的アルゴリズムがHe11drenら()によって提案された。このファット4カバー・アルゴリズムはグラフの最大幅のみの解析に基づいていたが、本稿では最大幅と最小幅の両方の解析に基づくように改善した新しい発見的アルゴリズムを提案する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Register allocation is an important optimization technique in compilers to generate efficient codes. The register allocation of well-structured programs is reducible to coloring problem of cyclic interval graphs. Although the problem is NP-complete, an efficient heuristic algorithm called fatcover algorithm was proposed by Hendren et al. (1992). In this paper, we improve this fatcover algorithm based on the analysis of the maximum width of cyclic interval graphs alone, and propose a new heuristic algorithm based on the analysis of both maximum and minimum widths.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 10(1994-AL-043), p. 39-46, 発行日 1995-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会