No | 216620 | |
著者(漢字) | 大津,金光 | |
著者(英字) | ||
著者(カナ) | オオツ,カネミツ | |
標題(和) | バイナリ変換処理によるマルチスレッド化に関する研究 | |
標題(洋) | A Study on Multithreading with Binary Translation Technology | |
報告番号 | 216620 | |
報告番号 | 乙16620 | |
学位授与日 | 2006.09.20 | |
学位種別 | 論文博士 | |
学位種類 | 博士(情報理工学) | |
学位記番号 | 第16620号 | |
研究科 | ||
専攻 | ||
論文審査委員 | ||
内容要旨 | めまぐるしく変化するこの現代社会において,コンピュータシステムに対する性能化の要求は益々大きくなってきている.この要請に応えるため,従来からプロセッサの性能を向上するための研究が種々に成されてきた. プロセッサの性能は,回路の動作クロック速度の向上と命令レベル並列性の活用との主に二つの要因により引き上げられてきた.しかしながら,回路の動作クロック速度の向上は消費電力の増大やトランジスタ素子の縮小限界などの物理的な制限により伸び悩んでいる状態であり,またシングルスレッド実行での命令レベル並列性の抽出をこれまで以上に高めるために必要となるハードウェア資源は急激に増大している.そのため現実的な意味でのシングルスレッド実行での性能向上は限界に近づいている. この状況を反映して,近年はシングルスレッドの性能を上げることにハードウェア資源を使うよりも1チップ上に複数のプロセッサを載せるマルチコアマルチスレッドアーキテクチャとした方がシステム全体としての性能を上げることが容易であると考えられ,主要なプロセッサメーカはマルチコアマルチスレッドアーキテクチャを採用している. しかしながら,これらのマルチコアマルチスレッドプロセッサの性能を十分に引き出すためには,プログラムコードのマルチスレッド化が必要不可欠であるが,そのためにはプログラムのソースコードを参照する必要であるという問題があった.そのため,ソースコードを参照できないプログラムのマルチスレッド化による高速化は達成困難であった. 本研究の目的は,逐次プログラムをマルチコアマルチスレッドプロセッサ上で高速化することである.そのために本研究では逐次のバイナリコードからマルチスレッド化されたバイナリコードへの自動変換処理を行なう手法を提案し,ソフトウェアのみで自動マルチスレッド化を行なうシステムを開発した.自動マルチスレッド化に向いたマルチスレッド実行モデルとしてスレッドパイプライニングモデルを採用し,forループのイテレーションを単位としたマルチスレッド化を行なう.また,スレッドパイプライニングモデルに基づいてforループをマルチスレッド化するために必要となるイテレーション間依存変数やループ誘導変数の検出をバイナリコードレベルで行なうための解析手法を開発した. 本研究で開発したバイナリ変換システムは,マルチスレッド化の対象であるプログラムのバイナリコードを内部中間表現に変換し,制御フロー解析によりプログラムのループ構造を検出する.検出したループ構造に対して,データフロー解析を行なうことでイテレーション間依存となる変数の検出とループ誘導変数を検出し,スレッドパイプライニングモデルに基づいたマルチスレッド化を行なう. SPEC95ベンチマークを用いたシミュレーションにより提案手法の性能を評価した結果,逐次実行に対して性能向上が達成できることを示した.ループに着目したマルチスレッド化手法においては,マルチスレッド化の対象ループが,(1)ループのコードサイズが大きい,(2)各ループの実行回数が多い,(3)ループイテレーション間のデータ依存によりスレッド間の並列実行が阻害されいくい,といった条件を満たす場合には,十分に性能向上が可能であることが示された.また,評価により既存のスレッドパイプライニングモデルに基づいたソースコードレベルでの手動マルチスレッド化手法と同等の性能をバイナリコードレベルでの変換により達成可能であることを示した.さらに,変換対象であるバイナリコードを生成する際にコンパイラにより施された最適化の性能に与える影響を評価した.バイナリコードにループアンローリングの最適化が施されている場合は,提案手法により大きく高速化することを明らかとした.またコンパイラの最適化レベルにより提案手法で達成される性能が影響され,最適化レベルが低いほど提案手法により大きく高速化することを示した. 本研究により,コード変換のための専用ハードウェアを持たないマルチコアマルチスレッドプロセッサ上で,スレッドパイプライニングモデルに基づいたバイナリコードレベルでのプログラムループの自動マルチスレッド化が実現され,提案手法が幅広い領域で有望であることが示された. | |
審査要旨 | ムーアの法則(半導体技術の集積度は16ヶ月で2倍になるという法則)に従って、半導体の集積度および動作周波数の向上によりプロセッサの性能も向上してきた。しかし、リーク電流、発熱等の問題により、プロセッサの周波数は頭打ちとなった。さらなるプロセッサ性能の向上は、動作周波数の向上から複数のプロセッサを一つのチップに搭載することによる性能向上に移った。多くのレガシーアプリケーションは逐次プログラムであり、これらアプリケーションの実行速度向上には、アプリケーションプログラムの並列化が必須となる。しかし、アプリケーションよってはソースプログラムではなく、バイナリプログラムしか存在しない場合もある。これらアプリケーションの実行を高速化する手法が求められている。 本論文は逐次バイナリプログラムの高速化をマルチコア・マルチスレッドプロセッサアーキテクチャ上での非投機的なマルチスレッド化により達成するために、バイナリ変換技術を用いることを提案した初めての研究である。本論文では実用的な方式実現のための基礎検討として、プログラムの基本的なループ構造であるforループを対象とし、スレッドパイプライニングモデルに基づいたマルチスレッド化をバイナリ変換処理によりバイナリコードレベルで行なう方式について研究を行なっている。 本論文のこの分野に対する貢献として、まずスレッドパイプライニングモデルに基づいたマルチスレッド化においてソースコードからの手動によるマルチスレッド化に匹敵するバイナリ変換によるマルチスレッド化の方法を示したことが挙げられる。これによってソースコードの参照を必要とする従来のマルチスレッド化手法や既存の専用ハードウェアによる実行時マルチスレッド化とは異なるアプローチとして、逐次処理プログラムのバイナリコードをバイナリ変換処理により直接改変することによって従来方式と同程度の性能を達成するマルチスレッド化が可能であることが示された。 また、本研究ではforループの誘導変数とイテレーション間依存変数をバイナリコードから検出するバイナリコード解析方法を新たに開発している。これは本来forループを対象としてスレッドパイプライニングモデルに基づいたマルチスレッド化処理を行なう上で必要不可欠である変数情報をバイナリコードから抽出するために開発されたものであるが、スレッドパイプライニングモデル以外の並列実行モデルに基づいてのバイナリ変換によるマルチスレッド化を行なう際においても有用な情報と言える。このバイナリコード解析方法の開発も本論文の貢献するところである。 さらに、本研究での提案手法を実現したバイナリ変換プログラムを用いての実験的評価により、バイナリコードを直接マルチスレッド化することによってもソースコードをマルチスレッド化する場合と同程度の性能を達成できることを示し、マルチコア・マルチスレッドプロセッサ上での逐次処理プログラムの高速化手法としてバイナリ変換技術が有望であることを示した。バイナリ変換処理による逐次プログラムのマルチスレッド化という新しい手法の可能性を開いたことは極めて大きな貢献と言える。 よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。 | |
UTokyo Repositoryリンク |