半導体技術の進歩によって、より複雑な機能をハードウェアおよびソフトウェアとしてシステムLSI上に実装することが年々可能となってきている。このようなシステムLSIを短い納期内に、できるだけ少数のエンジニアで実現するには、設計生産性の向上が必要である。設計生産性の向上には、C言語をはじめとする高位記述からトップダウンでハードウェアおよびソフトウェアを合成することや、プログラム可能で変更容易なアーキテクチャを利用することが有効であると考えられている。本論文では、プロセッサをベースとしたプログラム可能なアーキテクチャに対して、与えられたアプリケーションプログラムの実行性能を向上するような命令セットを自動的に追加し、それらを使用した最適コードを生成する手法を提案する。

提案手法の流れを説明する。与えられたアプリケーションからプロファイリングを利用して性能ボトルネック部分を抽出する。ボトルネック部分をデーターフローグラフ（DFG）として表現し、その部分グラフを拡張命令候補として列挙する。各拡張命令候補に対して、ハードウェアで実現した際の面積など最適化に必要な情報も求めておく。拡張命令候補とプロセッサがもともと持っている命令を使用して、最短サイクルでDFGを計算するようなコードが生成される。なお、拡張命令の個数、拡張命令セットを実現するハードウェアの面積、コード量などに関する制約を課すことも可能である。

本論文では命令セット拡張およびコード生成問題を有限状態機械（FSM）を利用して定式化した。定式化ではマッチとよばれる概念を使用する。DFGの部分グラフgが、命令（あるいは拡張命令候補、以後これらを区別しない）iによって計算可能なとき、その対応関係（g, i）をマッチと呼ぶ。簡単のため命令iは1サイクルで実行されるものと仮定する。部分グラフgを計算するために命令iを実行することを、マッチ（g, i）を実行すると呼ぶ。提案手法では、与えられたDFGと命令セット、拡張命令候補からマッチをすべて列挙し、DFGを最後まで計算するようなマッチの最短実行系列を求める。そのような系列から最短サイクルのコードを抽出可能である。

定式化したFSMの主要部分を説明する。FSMの入力変数として、各マッチmごとに二値変数emを用意する。二値変数emは、あるサイクルでマッチmを実行するときに1、実行しない場合に0となる変数である。FSMの状態変数として、DFGの各ノードnおよび各レジスタlに対して、二値変数an,lを用意する。二値変数an,lはノードｎの計算結果がレジスタlに格納されているときに1、格納されていないときに0となる変数である。もう一つの状態変数として、各拡張命令候補cに対して二値変数ucを用意する。二値変数ucはあるサイクルまでに拡張命令候補cが実行されたときに1、一度も実行されなかった場合に0となる変数である。他にも入力変数および状態変数が定義されるが、ここでは説明を省略する。FSMの初期状態としてDFGの計算前の状態、最終状態としてDFGの計算後の状態を設定する。このとき、初期状態から最終状態へ到達するような最短サイクルの入力系列（マッチの実行系列）が最短サイクルのコードを表す。FSMの状態遷移の際には、リソース、データ依存関係、拡張命令の面積やコード量に関する制約を課し、制約を違反するような状態遷移を抑えることができる。

以上のような考え方でコード生成の3つの基本ステップ、すなわち、コード選択、レジスタアロケーション、スケジューリングだけでなく、ソフトウェアパイプライン、SIMD命令の利用などをすべて同時に考慮したFSMを生成する手法を提案した。FSMを網羅的に解析することで、これらを同時に考慮したうえでの最適解を求めることが可能である。

形式的検証の分野では最近FSMの解析に充足可能性判定（SAT）がよく利用されている。充足可能性判定（SAT）問題とは、与えられた論理式の値を1にするような変数値の組み合わせを求める問題であり、最近SAT問題を高速に解く技術が急速に発達した。FSMの状態遷移関数を一定サイクル分だけ展開し、生成された組み合わせ回路をSAT問題に変換して解析することで、そのサイクル内でFSMがある初期状態からある最終状態に到達可能か網羅的に調べることができる。本論文ではその技術と、FSMによるコード生成の定式化を組み合わせ、DSP（Digital signal processor）向けのコード生成を行った。数十ノード以内のDFGに対して提案手法を適用したところ、人手で最適化されたコードと同等かそれより良いコードが生成された。

命令セット拡張をASIC（特定用途向け集積回路）のような専用回路として実現する場合、高い性能や小面積、低費電力といった利点が得られるが、柔軟性に乏しいという欠点がある。本論文では柔軟性が高い命令セット拡張を実現するため、命令セット拡張をリコンフィギュラブルデータパスにマッピングする手法を提案した。リコンフィギュラブルデータパスとは、ALUや乗算器、レジスタなどの機能ユニットが配列状に並んだ構造をとり、機能ユニットの機能や、それらの間の接続をコンフィギュレーションによって変更可能である。提案手法の入力は、DFGおよびリコンフィギュラブルデータパスのアーキテクチャであり、与えられたDFGをリコンフィギュラブルデータパスで実行するようなコンフィギュレーションを自動生成する。DFGの配置、概略配線、詳細配線をすべて同時に考慮した充足可能性判定問題の定式化を示し、実験を行った。その結果20ノード程度までの問題であれば最適にマッピングできることが判明した。

本論文は「Instruction-set Extension and Code Generation for Application-specific Processors」（特定用途向けプロセッサのための命令セット拡張およびコード生成に関する研究）と題し、特定用途向け特化したプロセッサーアーキテクチャを対象として処理の効率化のための演算命令の追加と、に特有の混成アーキテクチャを対象としたコード生成の最適化について研究したもので6章より構成され英文で記述されている．

第1章はIntroduction(序論)であり研究の背景と目的を述べている。本研究ではムーア則により1チップ上に実装可能なトランジスタ数が伸び続けている半面、設計者の設計能力向上がそれに追いついていない製造技術と設計力との間のギャップをテーマとして取り上げている。設計生産性を向上するために高位記述の利用、設計資産（IP: Intellectual Property）の再利用等を検討しており、再利用を容易化するプログラム可能なIPの重要性について述べている。本研究ではこれらの中でプログラム可能なIPとして特定用途向けプロセッサ（ASIP: Application-Specific Instruction-set Processor）に注目し、その高位記述（C言語）からの効率的な設計およびプログラム手法を主な研究対象としていることを述べている。

第2章はBackground(背景)と題し、プログラム可能なIPおよび、高位記述からの設計ツールについて現状を説明している。前者として組み込み向けマイクロプロセッサ、FPGA（Field Programmable Gate Array）、リコンフィギュラブルプロセッサ、特定用途向けプロセッサ、DSP（Digital Signal Processor）/VLIW（ Very Long Instruction Word）、FMA（Field Modifiable Architecture）などをあげ、設計ツールについては、プロファイラ、コンパイラ、コード生成、高位合成など、本研究の背景として用いられる技術体系を述べている。

第3章はFormulation(定式化)と題し、有限状態機械（FSM: Finite State Machine）を利用して、命令セット拡張およびコード生成（コード選択、レジスタ割り当て、コードスケジューリング）を同時に行う定式化を示している。定式化では、データフローグラフ（DFG: Data-Flow Graph）、プロセッサの持つ命令関連情報、拡張命令候補に関する情報、面積等の設計制約を考慮している。定式化したFSMでは入力は各サイクルで実行する命令を表し、FSMの状態は各サイクルでデータパスの記憶要素が保持している中間結果を表している。初期状態はDFGの計算前の状態であり最終状態はDFGの計算終了状態をあらわし、初期状態から最終状態までの経路を網羅的に探索することで制約条件を満足する命令セット拡張およびコード生成が可能となる手法を定式化している。さらにソフトウェアパイプラインおよびSIMD(Single-instruction multiple data)命令を扱えるように拡張している。

第4章はOptimum retargetable code generation(再ターゲット最適コード生成)と題し、第3章で提案したFSMを応用し、充足可能性判定（SAT: Boolean Satisfiability）問題としてFSMの解析を行い最小サイクル数のコード生成を行う方法を提案している。これによりコード選択、レジスタ割り当て、コードスケジューリング、ソフトウェアパイプラインを同時に行いつつ最小サイクルのコードを生成することを可能としている。DSP Stoneと呼ばれるDSP向けベンチマークプログラムと、アナログデバイス社のDSP（ADSP-2100）アーキテクチャに対して実験を行い、提案手法はアーヘン工科大学の大学院学生による人手で最適化したコードと同等以上の良好な品質のコードを1分以内で生成することができたことを述べている。

第5章はFlexible instruction extension(柔軟な命令拡張)と題し、拡張命令を柔軟に実現するためにリコンフィギュラブルデータパスにマッピングする方式を提案している。拡張命令を表すDFGの配置と配線を同時に定式化し、高品質なマッピング結果を得るため定式化をSAT問題として解析し、配置と配線を同時に実現する厳密解を求められることを示している。実験結果より最大でおよそ20個程度のノードをもつDFGに対して本提案手法が適用できることを示している。また、焼きなまし法などの発見的最適化手法を利用したトロント大学のVPR（Versatile Place and Route）ツールと結果を比較して、VPRで配置配線に失敗する場合にも本提案手法を利用すれば成功する場合のあることを述べている。

第6章は「結論」であり本論文の研究成果をまとめている．

以上、本論文は、用途に特化したプロセッサ・アーキテクチャを対象として、効率的演算命令の追加とコード生成を同時に最適化のために、問題を有限状態機械として定式化し充足可能性判定問題として解析する手法を提案するとともに、ベンチマーク結果によりその有効性を示したもので電子工学の発展に寄与する点が少なくない．

よって本論文は博士（工学）の学位請求論文として合格したものと認められる．