大規模集積回路の自動設計における上位論理合成に関しては様々なアプローチが提案されてきたが、高速化を可能とするパイプライン回路の自動合成は考慮すべき制約が多いことから効率的でかつ性能のよい手法は確立しておらず、研究が必要な段階にある。

　回路の自動設計の仕様には回路の速度性能とコスト(回路の面積)という2つの大きな性能を規定する項目がある。一般的にコストが低くかつパフォーマンスの高いものが良い設計であるが、回路の速度性能とコストの間にはトレードオフ問題が存在する。高速な回路を目指して設計を行う場合は、一般的により多くの部品が使用されるので、回路の面積が大になる。従って、速度とコストを評価基準とする回路の自動合成は使用面積により重み付けされた部品数と速度の2次元空間上の探索問題となる。高速なパイプライン処理を用いる回路の自動設計を行う場合には、回路の処理速度は部品数の他に、パイプラインのステージ(パイプラインの段数)にも依存する。従って、良いパイプライン回路の設計は、パイプラインのステージ数、部品数、速度の3次元空間上の探索問題となり、より難しくなる。

　パイプライン回路の自動設計は、ステージ数の決定、演算のスケージュリング、ハードウェア資源の割当という3つのサブ・タスクに分けることができる。それぞれは相互的に依存するため、この3つのタスクを同時に行わなければ、最適な設計を見い出すことは非常に困難である。

　今まで提案された各種のアプローチは、基本的にヒューリスティックな方法であり、この3要素を同時に考慮していない。この3つのタスクを独立に実行して設計を行うか、或いは3つのタスクの独立な実行を何度も繰り返すことによって設計を行うアプローチが主流であった。これらのアプローチは単純な方法で、プログラムの実行は高速であるという利点を持つが、但し、得られる設計は局所的最適解に陥りやすいのが大きな欠点となっている。より良い結果を見い出すためには、この3つのタスクを同時に行うことが必要であると考えて、シミュレーテットアニーリング(simulated annealing以下はSAと略称する)方法に基づいて、本研究を行った。このSAは、コストが増加した状態も確率的に採用することにより局所的最適解からの脱出が図れるという大きな長所を持っているが、長い処理時間を要する欠点もある。

　本論文で対象とするのは、目的とする処理のプログラム記述を既存の方法により変換して得られたデータフロー・グラフ表現である。この場合、同一の処理手順の多数の反復(ループ)を含むときに、パイプライン処理による高速化が効果的になる。本研究ではこのようなデータフロー・グラフから速度性能と面積コストに関して最適なパイプライン回路を設計するSAに基づく手法を示している。高速でかつ局所的最適値に陥りにくいアプローチを開発するために、本研究では従来のSA法にパイプライン回路設計に有用ないくつかのルールベース知識を付き加えた。そして、高速化したSA法をパイプ

　高速化したSA法を用いたパイプライン回路の設計問題は図1に示すような3次元空間上での配置問題になる。図1で示した空間の3つの軸は、それぞれ以下の意味をする :

　t: 1つのステージに含まれるサイクル数(パイプラインのラテンシィ)

　s: パイプラインのステージ数

　p: 演算器の数

　動作記述中の各演算は図1中のキュープで表すことができる。全てのキューブに対する1つの配置(SAでは状態、あるいは構成と呼ぶ)は1つのパイプライン回路設計になる。ここで、パイプラインのステージ数とラテンシィは最大のt,sの座標値よって決められ、各演算の配置は1つのスケージュル結果にもなっている。この結果に関する評価は式(1)の関数で表される:

　式(1)の右辺の最初の3項目はハードウェア・コストで、第4項目は速度コストである。係数kの指定によって、高速性か、低コスト性のどちらを重視した回路設計かを選択することができる。SAは与えられた初期状態から出発して、次々と状態を推移させ、最終的には評価関数に対する最適状態に行き着くことが期待できる。

図1 高速化したSA法を用いたパイプライン回路の設計

　本手法の性能は複数のパイプライン回路設計を通じて具体的に示しており、従来の手法では見い出せなかった設計も見い出している。

　パイプライン回路の自動設計においては他の色々な研究課題も存在する。例えば、データ・パスの合成に置ける様々なパイプライン・ハザード問題の解決や、パイプライン・ネットワークの同期化や、或いはより効率的な設計ができるよう記述言語からデータフローグラフを生成する時の工夫などの問題である。本論文では上記の問題に対する研究成果、方法論、或いは著者の見解も記述している。

　本論文は"A Pipelined VLSI Circuit Synthesis Method Based on Behavioral Specification(動作記述に基づくパイプラインVLSI回路の自動合成法)"と題し、高速演算の重要な回路形式であるパイプライン回路を動作仕様記述から自動合成する手法について記しており、英文で記されている。

　VLSIの自動設計においては、動作仕様記述から回路を合成する上位レベルの論理回路合成の重要性が増してきており、種々のアプローチがとられているが、パイプライン回路の自動合成については考慮すべき制約が多いことから、効率的でかつ性能の良い手法はまだ確立していない段階にある。本論文は回路の速度性能とハードウェア・コストを考慮して、効率的に所望のパイプライン回路を設計する一手法を提示している。

　第1章は序論であり、VLSIの上位レベル自動設計、パイプライン回路設計の概要と、これまでの研究を要約している。

　第2章"Pipeline Processing in High Level Synthesis of VLSI(VLSI上位レベル合成におけるパイプライン処理)"では、本論文で対象とするディジタル信号処理回路(DSP)等のパイプライン回路設計の基礎的事項について述べている。出発点は動作仕様のプログラム表現を変換して得られるデータフローグラフ表現であり、同一手順の処理の多数の反復(ループ)を含む場合にパイプラインによる高速化が効果的となる。パイプライン設計で用いるステージ、実行ウインドウ、レイテンシィ等について記し、パイプラインによって達成される演算速度の向上率とハードウェア量を少なくするための考慮事項について述べている。

　第3章"Pipeline Hazards and Control"では、パイプライン回路設計時に考慮しなければならないハザードの課題に関する検討を示している。即ち、先行演算の結果のデータを使用するという時間的依存関係に起因するデータハザード、演算ループの継続(停止)条件の判定が事前には行なえないことに起因する制御ハザード、同一ハードウェア使用の競合による構造ハザードについて、これらがパイプライン化によって問題を生じる場合に関する詳細な検討を行ない、自動設計において回避する方法を示している。

　第4章"Hardware Allocation and Operation Scheduling Based on Simulated Annealing(シミュレーティッドアニーリングに基づくハードウェア割付けと演算スケジューリング)"は本論文の中心であり、上記の検討を基にして、シミュレーティッドアニーリング法を用いた探索に基づくパイプライン回路の自動合成法を示している。

　パイプライン回路の自動設計は、ステージ数の決定、演算のスケジューリング、各演算へのハードウェアの割付という3種のサブタスクに分けることができるがこれらは相互に依存する。このため、従来の方法はこの3種のサブタスクを独立に実行する、あるいは独立な実行を何度も繰り返すものであり、高速ではあるが最適解を見い出すことは困難な場合が多かった。本論文では、この3種のサブタスクの同時実行を可能とするため、各演算を3次元空間(3軸はパイプラインのステージ数、1ステージに含まれるサイクル数(レイテンシィ)、演算器の数)へハザード等を回避して整合的に配置する探索問題とする枠組みを与えている。そして、この最適配置を局所最適解からの脱出能力を有するシミュレーティッドアニーリング法によって求める手法を与えている。最適化を図る目的関数は、所要のハードウェア・コストと達成できる演算処理時間の重み付け和で定義される。多くのハードウェアを使用するが最小演算処理時間が得られる回路構成を初期値として、可能な確率的遷移を行なって探索を行なう訳であるが、通常であると長時間を要するシミュレーティッドアニーリング法の効率を向上させるため、パイプライン回路設計に有用な複数のルールに基づく遷移を導入している。

　このパイプライン回路設計を行なうプログラムを作成し、いくつかの例についてこれまでに公表された設計例よりも優れた設計を実用的な時間内(数分以内)で見い出すなど、具体例を通して手法の有効性を実証している。

　第5章は結論である。

　付録"Minimization of Delay Buffers in Pipelined Network"では、複数データ流を有するパイプライン回路網において、多重入力演算器の各入力を時間的に同期させるために挿入する遅延バッファの最小化を図る考案した手法を記している。

　以上これを要するに、動作仕様記述からパイプライン回路の自動設計を行なう問題に対して、パイプラインステージ数の決定、演算のスケジューリング、各演算へのハードウェアの割付けの3種のサブタスクを同時に実行可能な探索問題として扱えることを明かにし、シミュレーティッドアニーリング法に基づく方法で、回路の速度とハードウェア・コストの両者を考慮した最適構成を見い出す手法を提示し、具体例を通してその有効性を示したものであり、電子工学上貢献するところが少なくない。

　よって、著者は東京大学大学院工学系研究科電子工学専攻における博士の学位論文審査に合格したものと認める。