様式８の１の１ 別紙１
論文の内容の要旨
専攻名 システム創成工学専攻 氏 名 十鳥 弘泰
近年，複数のプロセッサコアを単一のチップ上に搭載したマルチコアプロセッサが普及して おり，複数のプロセッサコアを活かした並列実行が注目されている。マルチコアプロセッサ上に おいてプログラムを並列実行する場合，プログラム中に存在する制御やデータの依存関係が問題 となる。特に，記号処理等を行う非数値処理系プログラムでは，この依存関係の有無が曖昧な場 合が多い。少しでも依存する可能性がある場合，プログラムの整合性を保つため，同期通信を頻 繁に行う必要がある。このため，同時並列に実行される処理が少なくなり速度向上を達成するこ とが困難になるといった課題がある。
本論文は，非数値処理系プログラムにおける並列化に関する課題を解決するため，依存関係 が複雑なプログラムに対して有効な投機的並列実行方式について検討し，静的なプログラム解析 だけでなく，プログラム実行時の実行挙動の情報を活用した新たな並列実行技術に関する知見を 得ることを目的とする。
本論文は全6章で構成され，各章の概要は以下のとおりである。
第１章は序論であり，研究の背景と研究目的を提示している。
第２章では，非数値処理系プログラムを並列化によって高速化するための有力な方法として，
将来実行される可能性のある処理を予測し，先行して並列実行する投機的並列実行方式について 説明している。そして，従来の投機的並列実行方式に関する研究について述べている。
第３章では，プログラムの実行挙動の性質を活用した投機的並列実行方式を実現するプロセ ッサの開発について述べている。プログラムの並列化において高速化の期待できる処理は，実行 頻度の高い繰り返し処理 (ループ) である。高精度である予測を実現するためには，静的なプ ログラム構造の解析だけでなく，プログラムの実行挙動を解析し，プログラムの振る舞いに対応 することが重要である。まず，ループ１回分の繰り返しにおけるプログラム上の命令の実行経路 (パス) について，プログラム実行の全体をとおした実行の偏りについて述べる。そして，こ の偏りを利用し，予測が成功する確率の高い実行割合上位２本のパスのみを選び，投機的に並列 実行する２パス限定投機方式について説明している。本研究では，同方式の性能を最大限に引き 出すマルチコアプロセッサ・アーキテクチャについて検討を行い，独自のアーキテクチャとして ２パス限定投機システムを提案している。また，同システム上で実行するプログラムの最適化に ついて検討し，最適化を施したプログラムをシミュレータ上で実行することにより，システムの 性能評価を行っている。性能評価の結果，プロセッサコア４台の場合に，逐次実行に対して最大 で1.55倍の性能向上を達成できることを明らかにしている。
第４章では，複数のパスを持つループに対して予測性能の向上を図るため，プログラム全体
をとおした実行割合のうち，上位３位以下のパスを予測の対象とした手法について検討している。
従来，１ビットで表されていたパスの実行履歴情報を，２ビット，３ビットと拡張して扱うこと により，投機対象となるパスの種類数を増大させる手法を検討し，多くの追加ハードウェアを必 要としない，新たなパスの予測メカニズムを提案する。そして，シミュレータによる予測性能の 評価により，従来の１ビットの実行履歴情報を利用したパス予測機構に対し，同程度の記憶資源 で予測性能を最大で7.6％向上できることを明らかにしている。
第５章では，複数のパスを持ち，複雑な実行挙動を示すプログラムに対して高い予測精度を 実現するため，プログラム実行中に動的に予測対象とするパスを変更する手法について提案して いる。あるループの実行を開始してからループを終了するまでの区間におけるパス実行割合の遷 移の様子から，直前のループ区間の実行割合上位２本のパスを，次のループ区間における予測対 象として動的に選択する方式を提案している。そして，動的な選択を行った場合の予測成功率に ついてシミュレータを用いた性能評価を行い，従来の静的な予測手法に比べ，予測性能を最大で 33%向上できることを明らかにしている。
最後に，第６章では，結論として本研究で得られた知見をまとめ，結果を総括している。
