X86アーキテクチャのメモリ階層を考慮した最適なRegister Allocation

• Item type: Trans(1)
• 公開日: 2004-07-15
• タイトル: X86アーキテクチャのメモリ階層を考慮した最適なRegister Allocation
• タイトル / 言語: en
• タイトル: An Optimal Register Allocation for X86 Architecture with Consideration of Memory Hierarchy
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学基盤情報学専攻
• 著者所属: 東京大学情報基盤センター
• 著者所属(英): en
• 著者所属(英): Department of Frontier Informatics, The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Information Technology Center, The University of Tokyo
• 著者名: 堀本, 和秀; 佐藤周行
• 著者名(英): Kazuhide, Horimoto; Hiroyuki, Sato
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: コンピュータでは，高い性能を実現するためにキャッシュを上手く利用することが有効である．そのため近年のプロセッサは一般的にある程度のメモリ階層を持っており，コンパイラは高い性能を実現するためにこのメモリ階層を考慮する必要がある．X86のようなアーキテクチャでは，レジスタの数が少ないことや，命令のオペランドをメモリにできることからRegister Allocationは難しくなる．Graph Coloringのような従来のヒューリスティックな方法ではその難しくなったRegister Allocationで良い性能を出せる解を求められるかは自明ではない．本研究の目的は，0-1 Integer Programmingを用いてキャッシュを有効利用できるRegister Allocationの最適解を求めるためのモデル化を行い，既存のコンパイラとの比較と評価を行うことである．本発表では，Pentium 4のアーキテクチャのRegister/Cache/Memoryの階層を考慮したRegister Allocationを行うための性能モデルの0-1 Integer Programmingによる定式化を行い，その実装と性能の測定を行った．さらに既存のコンパイラとの比較と評価を試み，従来のヒューリスティックスの改善点などについて考察を行った．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In modern proceccors, memory hierarchy must be utilized effectively for achieving high performance. Compilers must be designed to exploit the memory hierarchy. For the X86 architecture that has few registers, and furthermore has possible memory operands, register allocation is never trivial. In other words, it is not clear if conventional heuristics such as graph coloring can give the best register allocation. Our goal is to formulate register allocation for Pentium 4 with 0-1 Integer Programming. This scheme is proved to be optimum for the performance model which considers the register/cache/memory hierarchy. In this presentation, we show the scheme of generaing 0-1 Integer Programming for a given code, and apply the solutions for register allocation. Furthermore, we evaluate the solutions on realistic platform.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 45, 号 SIG09(PRO22), p. 84-84, 発行日 2004-07-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会