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

堀本, 和秀, 佐藤周行

コンピュータでは，高い性能を実現するためにキャッシュを上手く利用することが有効である．そのため近年のプロセッサは一般的にある程度のメモリ階層を持っており，コンパイラは高い性能を実現するためにこのメモリ階層を考慮する必要がある．X86のようなアーキテクチャでは，レジスタの数が少ないことや，命令のオペランドをメモリにできることからRegister Allocationは難しくなる．Graph Coloringのような従来のヒューリスティックな方法ではその難しくなったRegister Allocationで良い性能を出せる解を求められるかは自明ではない．本研究の目的は，0-1 Integer Programmingを用いてキャッシュを有効利用できるRegister Allocationの最適解を求めるためのモデル化を行い，既存のコンパイラとの比較と評価を行うことである．本発表では，Pentium 4のアーキテクチャのRegister/Cache/Memoryの階層を考慮したRegister Allocationを行うための性能モデルの0-1 Integer Programmingによる定式化を行い，その実装と性能の測定を行った．さらに既存のコンパイラとの比較と評価を試み，従来のヒューリスティックスの改善点などについて考察を行った．

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.

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

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

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

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

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

書き出し

問題の指摘

参加プロジェクトリスト

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