JP5516596B2 - 高レベル合成での設計空間探索の方法及び装置 - Google Patents

Description

本発明は、電子設計自動化（ＥＤＡ；electronic design automation）に関連した方法、システム、及びプログラム・プロダクトに関し、特に、時に動作合成(behavioral synthesis)と呼ばれる、高レベル合成での高レベル言語の設計空間の自動化されたマイクロアーキテクチャ探索を目的とする回路設計に関する。

システム設計者は、一般に、例えばＣやＣ＋＋などの高レベル言語により、計画したハードウェア設計の仕様を与える。これは、システム性能を評価し、設計の機能上の正しさを検証するための簡単かつ速いやり方を可能にする。高レベル言語でハードウェア設計を記述することは、より上位レベルでの抽象化を与え、これはまた、コードの再利用可能性を高めることに役立つ。そのことはまた、より高速でのシュミレーションを提供し、その高レベル言語に対して現存する旧来からのコードやライブラリの全てを使用できる可能性を与える。ハードウェア設計者は、次に、手作業でコードを解析し、そのコードに適したハードウェア・アーキテクチャを見つけ出し、いずれかのハードウェア記述言語（ＨＤＬ；hardware Description Language）を用いてそのコードを書き直す必要がある。

高レベル言語は、通常はソフトウェア・アプリケーションに対して使用されるプログラミング言語であり、そこでは、このプログラムがどのように実行されるかについてはコンパイラが処理するので、このことについて設計者自身が心配する必要はない。一方、ＶＨＤＬやＶｅｒｉｌｏｇを含むＨＤＬは低レベル言語であり、そこでは、設計者は、ハードウェア・アーキテクチャを作成するために、モジュール間の接続関係のために使用されるレジスタから始まって詳細事項の各々を指定する必要がある。

より速い商品化サイクルを取り扱うために、高レベル言語はハードウェアを記述する能力を備えることが好ましい。しかしながら、高レベル言語自体はソフトウェア・プログラムに使用されるものであり、ハードウェア設計に必要な構文(construct)を備えていない。したがって、ハードウェアを取り扱えるように高レベル言語は拡張されてきており、ハードウェアを記述できるように、元の高レベル言語から派生した高レベル言語の拡張版のサブセットが作り出されてきている。サブセットは、ハードウェアにおいて必要であるが一般の高レベル言語では用意されていない特徴(feature)をユーザが指定できるようにする新たなステートメントを組み入れている。サブセットに導入された新たなステートメントは、例えば、ビット幅をカスタマイズするためのステートメントや、並列処理宣言のための別のステートメントを含んでいる。

高レベル言語の拡張版のサブセットはまた、ハードウェアにおいて直接変換されるものを持たなかったり、Ｃのサブセットの場合であれば例えばポインタや動的メモリ割り当てなどの、コンパイル時に決定できないものであったり、あるいは、例えばファンクション・コール、再帰、ｇｏｔｏ文、型キャストなどの、変換することが特に難しかったりする、いくつかの構文の使用を制限する。Ｃ／Ｃ＋＋のサブセットのいくつかの例として、ＳｙｓｔｅｍＣ、ＢＤＬ（動作記述言語；Behavioral Description Language）、ＨａｎｄｌｅＣまたはＳＡ−Ｃ、ＪＡＶＡ（登録商標）用のＪＨＤＬ(Just-Another Hardware Description Language)がある。

高レベル言語の拡張版のサブセットを用いることは、設計者がＶＨＤＬやＶｅｒｌｏｇなどの低レベル・ハードウェア記述言語（ＨＤＬ）を取り扱う必要がないので、設計プロセスを単純なものにする。しかしながら、設計者らが任意の高レベル言語のサブセットを用いてアーキテクチャの記述を開始できるようにする前に、設計者らは、適切なハードウェア・アーキテクチャを生成できるようにするために、依然として、システムの解析を手作業で行う必要がある。設計者らは、例えば、それぞれの信号のビット幅や並列処理を指定し、演算操作を特定のコンポーネントに結び付け、いずれかのリソースが共有される必要があるかどうかを定義するために、システムを解析する必要がある。

関連技術において、McConaghyに対して付与された米国特許第６，９６８，５１７号明細書（特許文献１）は、生成アルゴリズムと目的関数とを有する最適化器を用いて、最適化された設計の候補の少なくとも１つをインタラクティブ（相互対話的）に決定する方法を開示している。

設計された回路を最適化するために、設計空間を探索する必要がある。そのような設計空間探索は、データ・フロー図を使用してもよい。設計空間探索の典型的なパラメータは、タイミング、電力、面積である。

Ahmadらは、遺伝アルゴリズムを用いて、データ・フロー図中での制御ステップと面積との間のトレードオフ関係を研究した（非特許文献１）。Holzerらは、進化的多目的最適化アプローチを用いるのと同様のアプローチを用いて、パレート(Pareto)最適解を生成した（非特許文献２）。Habueltらは、パレート−フロント計算（ＰＦＡ；Pareto-Front Arithmetics）を用い、階層的検索空間を分解することによって、組み込みシステムでの探索空間を縮小した（非特許文献３）。

上述したように、高レベル合成に対する設計空間探索は、最初の高レベル言語でのアルゴリズム記述と最終的なハードウェア設計とを橋渡しして、ハードウェアの設計を迅速化するのに重要である。高レベル合成に対する設計空間探索はまた、設計におけるできるだけ早期の段階での、異なる設計パラメータ（すなわち、面積、レイテンシ、スループット、電力）間のトレードオフの探索も可能にする。ここに示す例では、シングルプロセスでの設計探索について言及するが、本明細書によって提案する方法は、システムレベルの設計にも、シングルプロセスあるいはマルチプロセス探索にも適用することができる。

米国特許第６，９６８，５１７号明細書

I. Ahmad, M. Dhodhi and F. Hielscher, "Design-Space Exploration for High-Level Synthesis," Computers and Communications, pp. 491-496, 1994 M. Holzer, B. Knerr and M. Rupp, "Design Space Exploration with Evolutionary Multi-Objective Optimisation," Proc. Industrial Embedded Systems, pp. 125-133, 2007 C. Haubelt and J. Teich, "Accelerating Design Space Exploration," International Conference on ASIC, pp. 79-84, 2003

本発明の目的は、高レベル合成のためのロバスト（頑強）な設計空間探索の方法であって、設計制約の組が与えられた（あるいは与えられなかった）として、高レベル言語でのアルゴリズム記述と最終的な最適化されたハードウェア設計とを橋渡しするように開発されてきた方法を提供することにある。

本発明の別の目的は、高レベル合成のためのロバストな設計空間探索ツールのシステムであって、設計制約の組が与えられた（あるいは与えられなかった）として、高レベル言語でのアルゴリズム記述と最終的な最適化されたハードウェア設計とを橋渡しするように開発されてきたシステムを提供することにある。

本発明の例示的態様による方法は、時刻概念を含まない(untimed)高レベル言語の設計空間を自動的に探索する方法であって、（ａ）入力ソースを解析（パース）するローカル操作の組を自動的に探索し、ローカル操作の各々に属性の組を割り当てることと、（ｂ）対象とする回路の全体の設計に影響を与えるグローバル合成オプションの組を探索することと、（ｃ）設計に割り当てられた機能ユニットの数と種類とを探索することと、の少なくとも１つを有する方法である。

本発明の別の例示的態様による装置は、時刻概念を含まない高レベル言語の設計空間を自動的に探索する装置であって、自動化された探索に対する入力を受け付ける入力装置と、ソース・コードに基づいて依存関係解析木(dependency parse tree)を生成する解析木生成器と、（ａ）入力ソースを解析（パース）するローカル操作の組を自動的に探索し、ローカル操作の各々に属性の組を割り当てること、（ｂ）対象とする回路の全体の設計に影響を与えるグローバル合成オプションの組を探索すること、及び（ｃ）設計に割り当てられた機能ユニットの数と種類とを探索することの少なくとも１つを行う探索装置と、探索結果を出力する出力装置と、を有する装置である。

本発明の実施の一形態の設計空間探索によって生成された解析木を示す、プロセス解析木の図である。 実施の一形態の設計空間探索の全体的な処理を示す、一般的フローチャートである。 探索入力とデータ変換の例を示す図である。 詳細な探索操作を示すフローチャートである。 実施の一形態の設計空間探索装置を示すブロック図である。 探索の入力と出力の概観の一例を示す。 探索の実行時間（ランタイム）を削減するクラスタリングの例を示す図である。 探索の実行時間を削減するクラスタリングの例を示す図である。 全設計空間探索の各段階の例を示す図である。 全設計空間探索の各段階の例を示す図である。 全設計空間探索の各段階の例を示す図である。 全設計空間探索の各段階の例を示す図である。 自動的に生成された設計に対する、グローバル・コスト関数の重みの効果を示す図である。 実施の一形態の方法によって生成された自動生成設計を表示し変更するために用いられる、インタラクティブ型設計空間探索ウィンドウの一例を示す図である。 実施の一形態に基づき、より小さな探索実行時間をもたらす、可能な最小操作クラスタの生成を示す図である。 実施の一形態に基づき、最速の探索実行時間をもたらす、可能な最大操作クラスタの生成を示す図である。

次に、複数の図面にわたって同様の参照符号が同様の構成要素を示している添付の図面を参照して、本発明の実施の一形態に基づく、新規ハードウェア設計の自動生成について説明する。

新規設計の自動生成は、高レベル合成すなわち動作合成に関する高レベル言語記述に対する自動化された設計空間探索に基づいている。動作合成は、グローバル合成オプションを適用し、許容される機能ユニット(functional unit)の最大数と種類とを指定し、特定の操作（オペレーション）（例えば、ループ(loop)、関数(function)、配列(array)）においてプラグマ(pragma)として指定されるローカル属性を指定することによって、オリジナルのソース・コードに手を加えないかわずかに修正するだけで、高速に、時刻概念を含まない(untimed)高レベル言語によるユニークな記述に対する多数のハードウェア・アーキテクチャの生成を可能にする。

以下の説明において、例示的な自動生成は、時刻概念を含まない高レベル言語の同一のソース・コードから開始する。

時刻概念を含まない高レベル言語の所与のコードは、手動で、例えば、インライン(inline)展開としての実装関数(implement function)や“ｇｏｔｏ”（すなわち、指定されたブロックへのジャンプ）、（例えば、アンロール(unroll)しない、ｘ回アンロールする、完全にアンロールする、または、折り返し(fold)の）ループ(loop)、布線論理としての配列へのマッピング、レジスタまたメモリなどのプラグマ(pragma)を備えることができる。これらのプラグマは、しばしば、以下の書式を有する。

/* pragma unroll=all */
for(x=0; x < 10; x++) ....
この例は、高レベル言語に対し、ｆｏｒ ｌｏｏｐ（フォー・ループ）を完全にアンロールすることを指示する。

プラグマは、所与のソース・コードの合成において、高レベル合成ツールの動作を案内する。本実施形態の方法は、外部ライブラリ・ファイル上でユーザによって指定されているか、あるいは、操作（例えば、ｆｏｒ ｌｏｏｐ、関数、配列）の規定された組に対して内部的に宣言されているプラグマ（すなわち属性）の組を読み出す。それらの操作の各々は、例えば面積、レイテンシ及び電力を減少／増加させることへのそのバイアスされた寄与に基づいて、所与の初期重み値を有している。ユーザはまた、高レベル合成ツールによってサポートされている限り、特定の操作やそれに対応する属性を定義することもできる。探索されるべき各操作は、ユーザによって手作業で特徴づけられることもできるし、あるいは、本実施形態の方法によって自動的に特徴づけられることもできる。以下の場合では、たった２つの割り当てられたプラグマが、以下に与えられた操作に関して探索されるであろう。

/* Pragma explore1="unroll=all, weight[A2:L8]", explore2="unroll=0,
weight[A10:L2]", explore3="unroll=(2-6), weight[A5:L5]" */
for(x=0; x < 10; x++) ....
ローカルなプラグマが定義されていない場合、外部ライブラリで指定されたプラグマが使用されるであろう。初期の重み値は、これらの属性の「通常の、直観的に理解できる」動作に基づいて特徴づけられる。直観的に、“ｇｏｔｏ”として関数が合成される場合には、関数が呼び出されるたびに新しいハードウェア・ブロックが生成されるインラインの場合と比べ、全体の面積を小さくすることができるだろう。しかしながら、これは全ての場合にあてはまるわけではない。いくつかの場合には、この関数を共有するために挿入される多重化回路の数が、“ｇｏｔｏ”として関数を実装する場合に得られる節約分を超過する。小さな関数の本体部（ボディ）をインライン組み込みする場合に、よりよい面積／性能の結果をもたらすことができるだろう。

インライン展開は、関数が起動される場所の全てにおいて関数の内容を展開する方法である。起動(invocation)が行われる場所に関数の内容を配置して展開すると、記述の全体としての大きさが増加する。記述におけるこの増加は、結果として得られるハードウェアの面積の増加の可能性をもたらす。しかしながら、“ｇｏｔｏ”に変換したときと比べ、合成された回路における実行サイクル数は、一般に減少する。一方、“ｇｏｔｏ”への変換は、関数の処理が単一の位置に統合される合成方法である。この統合は、全ての関数処理の起動が、この単一の位置のみから実行されるというものである。もし、同じ関数が、多数の位置から起動されることになっているとすると、処理の単一の位置への統合は、インライン展開に比べて、より小さな回路面積をもたらす。しかしながら、関数の起動は、ファンクション・コール（関数呼び出し）ごとに１サイクルを必要とするので、この方法は、インライン展開に比べ、結果として、実行サイクル数の増加をもたらしがちである。

以下の説明において、上述した、各探索操作に関する属性のユニークな組の生成のステップを第１の探索ステップと規定する。

重みは、外部から指定されたグローバル・コスト関数を最大化するために、この属性を選択する実際の確率である。したがって、少ない面積の設計が生成することが望まれる場合には、設計でのより小さな面積をもたらすであろう、より高い面積重みを有する属性に対し、選択されることに対するより高い確率が与えられる。

本実施形態に基づく方法は、グローバル合成オプションのどれかかが適用されるとして、全体設計に適用するグローバル合成オプションの組も使用する。グローバル合成オプションは、例えば、投機的スケジューリング、ＡＳＡＰ、入力及び出力ＡＬＡＰスケジューリングなどのどの種類のスケジューリング・ポリシが実行されるか、動作合成中に（例えば面積、レイテンシ、遅延指向などの）どの最適化ヒューリスティックが使用されるべきか、及び、どの種類のリソース共有ポリシが実行されるか、である。グローバル合成オプションは、設計探索に対する、より粗いレベルでの制御を提供する。グローバル合成オプションは、解析木生成で同定された全てのオペレータ（演算子）を特定の属性にマッピングすることもできる。この場合、全ての操作は同じ属性を有するであろう。第１の探索ステップで生成された属性の組に対してグローバル合成オプションの組を生成するこのステップを、第２の探索ステップと規定する。

第３の探索ステップは、所与の属性及び合成オプションに対するＦＵ（機能ユニット；functional unit）（例えば、加算器または乗算器）の最大数と種類との探索を含んでいる。これは、スケジューラに顕著な影響を及ぼし、したがって最終的な設計にも顕著な影響を及ぼす。ＦＵの最大数は、探索中に動的に変更されるであろう。

第４の探索ステップは、クロック・ステップ探索であり、クロック周期の探索を含んでいる。このステップは、同一の制御ステップに対してより多くのあるいはより少ない操作がスケジュールされることを可能にすることによって、スケジューリングに影響を及ぼし、かくして、全体としての状態の数に影響を及ぼす。

これら４種類の探索ステップは、一緒に実行されることもできるし、あるいは、任意の種類の組み合わせ（例えば、ローカル属性のみを探索する；属性とグローバル合成を探索する；または、４種類のうちの３つを一緒に探索する）で実行されることもできる。なお、第４のステップは、他のステップには非依存であり、独立して扱うことができる。

本実施形態に基づく方法は、また、グローバル・コスト関数（ＧＣＦ；global cost function）の重みを、より小さな面積の設計から始めて、よりレイテンシの低い設計が生成されるまで徐々に大きくするように（またはその逆で）自動的に変化させることによって、完全な設計空間探索を可能にする。属性とグローバル合成オプションとＦＵの数及び種類とのユニークな組が、各新しい設計ごとに生成される。各新しい設計は、所与のグローバル・コスト関数（ＧＣＦ）に基づいて、以前の設計からの増分として生成される。ＧＣＦは、
ＧＣＦ ＝ ｘ Ａ ＋ ｙ Ｌ ＋ ｘ Ｐ，
によって与えられる。ここで重み因子ｘ，ｙ，ｚは、それぞれ、全面積（Ａ）、全レイテンシ（Ｌ）及び電力（Ｐ）を最小化することの重要度を示している。重みは、設計空間の全体を探索するために、探索中に、適応的に変更される。ｘ＞＞ｙ，ｚであれば、面積の重みを最高に最小化する属性について、その属性が使用される確率がより高くなる。設計空間の一部分のみの探索が望まれる場合には、コスト関数は固定したままとして、所与のコスト関数の周囲の設計だけを探索する。この方法のランダムさは、局所的極小（ローカル・ミニマム）の問題を回避することを可能にする。

属性のユニークな組が、各設計のローカル属性とグローバル合成オプションと使用されたＦＵの数及び種類とに対するユニークなハッシュ・インデックスを生成することによって、各新しい設計に対して生成される。

図１は、本実施形態の方法により生成された解析木の一例を示している。図１から、探索することができる全ての操作を抽出することができる。抽出された操作から、依存関係木を構築することができる。木の起点により近い操作は、この操作にマッピングされた属性に依存して、全ての従属する操作が例えば反復(replicate)されたりアンロールされたりすることになるので、最終的な設計により大きな影響を及ぼす。各属性の重みは、その操作の位置に基づいて、動的に調整される。

図２は、高レベル言語のソース・コードを解析（パース）することから始まって解析木を構築する探索フローの全体を示している。自動探索（ブロック１０１）が解析木を構築する。自動探索は、高レベル合成ツールに対する、ローカル属性とグローバル合成オプションと機能ユニット制約条件ファイルとの新しい組を生成する。自動探索１０１に対する入力１１０は、探索対象の高レベル言語コード１１１と、入力オプション１１２と、グローバル・コスト関数（ＧＣＦ）１１４と、を含んでいる。自動探索１０１はまた、任意項目である入力制約条件（例えば、面積、レイテンシ及び電力）の組を含む制約条件ファイル１１２と、（バイアスされ、またはバイアスされていない）属性及びグローバル合成オプションを有する入力ライブラリ１１５とを参照し、出力ファイルに探索結果を格納する。ユーザは、コード、オプション、ＧＣＦ、入力制約条件及び入力ライブラリを指定することができる。自動探索からの出力ファイルは、ソース・コード・ファイル１３１（すなわちＩＦＦファイル）と、機能ユニット制約条件ファイル１３２と、グローバル合成オプション用のファイル１３３と、ローカル属性（プラグマ）用のファイル１３４とを含んでいる。

次に高レベル合成ツール１４１は、制約条件ファイル１１２と自動探索１０１の出力ファイルとを参照して、出力１５１として、いくつかの新しい設計と、探索結果を表すグラフィック表示とを出力する。図２において、新しい設計は、「設計１」、「設計２」、…によって示されている。本実施形態において、高レベル合成の結果は、新しい設計についての情報を抽出するために、確認用に読み出され（リードバックされ）、制約条件に適合しているかどうか、オプションの新しい組が合成におけるエラーの原因となっていないかどうかがチェックされる。

図３は、「自動探索」ブロック１０１への詳細な入力の一例を示している。ハードウェア設計のための高レベル言語（例えば、この場合はＢＤＬ）の例が、グローバル・コスト関数、入力オプション、属性の重み付けされたリスト、及び合成オプションとともに示されている。ソース・コードはまた、ソース・コードにおいて特定の操作の探索を直接制限するために、ローカル属性プラグマの使用をも示している。全ての入力を読み出した後の探索の本当の最初のステップは、同じ図面に示されているように、探索可能な操作に対してのみ、依存関係木を生成することである。

図４は、探索方法の詳細なフローチャートを示しており、必要とされる全ての入力から開始して、探索手順の主要なステップの全てを経る、主要な探索ステップを説明している。図４は、生成された出力も示している。

最初に、自動化された探索への入力１００がボックス２０１において読み出され、探索のためのシーケンス２０２が開始する。依存関係解析木が、ボックス２０３において、探索可能な操作に対して生成され、属性の重みが、ボックス２０４において、解析木における各操作の位置に基づいて調整される。調整の後、ボックス２０５において、設計探索の実行時間がクリティカルであれば、クラスタが構築される。全検索が有効にされている場合には、ＧＣＦが、ＧＣＦ＝Ａ１０，Ｌ０にリセットされるであろう。

次に、グローバル検索が選択されていれば、ボックス２０６において、グローバル制約条件関数が、漸減（デクリメント）Ｌ及び漸増（インクリメント）Ｌによって適応させられる。同時に、ＦＵの最大数が、初期値としてその最大に設定される。ボックス２０７において、属性のユニークな組が生成され、ボックス２０８において、グローバル合成オプションのユニークな組が生成される。次に、ボックス２０９において、ＦＵの最大数をデクリメントしながら、所与の属性と合成オプションに対する機能ユニットの数が探索される。この探索の結果２１０は、次に、高レベル合成ツール１４１に与えられる。

本実施形態に基づき、終了条件が満たされるまで、探索のための上記のステップが繰り返され、全ての合成オプションが探索され反復される。探索のステップが継続しているとき、ＧＣＦは、各反復ごとに適応される。したがって、本実施形態は、ボックス２１１〜２１４内に示された以下のステップを有する。

高レベル合成ののち、ステップ２１１において、探索が終了したかどうかが判断される。探索が終了していれば、高レベル合成ツール１４１がいくつかの候補となる新しい設計とそのグラフィック表示とを出力する。そうでなければ、ボックス２１２において、ＦＵの組み合わせの新しい組が可能かどうかが判断される。新しい組が可能であれば、プロセスはボックス２０９に移行する。新しい組が可能でなければ、ボックス２１３において、グローバル合成オプションの新しい組が生成されるべきかどうかが判断される。生成されるべきであれば、プロセスはボックス２０８に移行し、そうでなければ、プロセスはボックス２１４に移行する。ボックス２１４において、ＧＣＦステージあたりの属性の最大数に到達したかどうかが判断される。最大数に到達していれば、プロセスはボックス２０６に移行し、ＧＣＦを適応させて探索を続ける。そうでなければ、プロセスはボックス２０７に移行する。

ボックス２１１において全ての探索が終了した後、その結果が詳細に調べられる。

図５は、図４に示した処理のシーケンスを実行する設計空間探索装置の構成を示している。

設計空間探索装置は、自動化された探索への入力１１０を受け取る入力部３０１と、ソース・コードに基づいて依存関係解析木を生成する解析木生成器３０２と、解析木における各操作の位置に基づいて属性の重みを調整する重み調整部３０３と、クラスタを構築するクラスタ構築器３０４と、グローバル・コスト関数を適応させるＧＣＦ制御器３０５と、属性のユニークな組を生成する第１の生成器３０６と、グローバル合成オプションのユニークな組を生成する第２の生成器３０７と、所与の属性と合成オプションに関して機能ユニットの数を探索する探索部３０８と、機能ユニットの最大数を設定してデクリメントさせ、図４中のボックス２１１〜２１４のループ操作を制御するループ制御器３０９と、上記の高レベル合成ツール１４１として機能する高レベル合成部３１０と、新しい設計と探索結果を表すグラフィック表示とを出力する出力部３１１と、を含んでいる。

ここで説明する設計空間探索装置は、パーソナルコンピュータやワークステーションなどのコンピュータにこのシステムを実現するプログラムを読み込ませそのプログラムを実行させることによっても、実現することができる。コンピュータを設計空間探索装置として機能させるプログラムは、ＣＤ−ＲＯＭのようなコンピュータ可読記録媒体によって、あるいはネットワークを介して、コンピュータに読み込まれる。本発明の範囲には、設計空間探索装置として機能するようにコンピュータに指示するために用いられるプログラムと、そのプログラムを格納したプログラム・プロダクトまたはコンピュータ可読記録媒体も含まれる。

図６は、探索の入力及び出力の概観の一例を示している。この図は、設計空間探索装置の表示装置上の例示的な表示画面を表している。入力は、任意の高レベル合成ツールを使用して合成されることとなる高レベル言語記述であり、自動探索の出力は、ローカル属性とグローバル合成オプションと機能ユニットの数及び種類との新しい組である。図６に示されるグラフは、生成された設計の全てについてのトレードオフ曲線である。各点は新規の設計であり、ｘ及びｙ軸は、ユーザ選択に基づいた異なるパラメータを表すことができる。右側ペイン(pane)上のチェック・ボックスをクリックすることによって、例えば、面積、レイテンシ、状態の数、メモリ、レジスタなどの、異なる設計メトリックを表示させることができる。

実行時間（ランタイム）を削減するために、上述したクラスタリングを適用することができる。探索可能な操作の組はクラスタにすることができ、属性の固定した組をそれらに適用することができる。図７Ａ及び図７Ｂは、ここでの例のクラスタリングを示している。代替可能な２つのやり方がある。図７Ａは、可能な最小クラスタを目的とすることにより、設計空間を縮小するが、より高い探索可能性を可能にするクラスタリングを示している。図７Ｂは、可能な限り大きなクラスタを構築して、可能な限り実行時間を削減し、ＧＣＦに基づいてそれらに固定した属性を割り当てることを示している。これらの固定されたクラスタは、ＧＣＦが変化した場合には、変化することができる。

図７Ａ及び図７Ｂに示した例において、属性についての固定した組が、ＧＣＦに基づいて、異なるクラスタ化された操作に適用される。もし目標が面積を最小化することであれば、面積を最小化する属性が使用される。レイテンシを最小化することが目的である場合、属性についての異なる組がこれらの操作に割り当てられるであろう。より大きなクラスタは、探索可能な組み合わせがより少ないことを意味するので、クラスタリングのサイズは、設計検索空間に影響を与えるだろう。このことの問題点は、最適設計（すなわち最小の面積及びレイテンシ）が見つからないかもしれないことである。探索ＧＣＦが、ＧＣＦ重みの適応的な変化の間に、例えば、面積の最小化からレイテンシの最小化に変化したときは、属性についての固定された組が各クラスタに再割り当てされる。

図８Ａ〜図８Ｄは、全設計空間探索のステップを示し、連続的に空間探索の結果を示している。図８Ａに示すように、全設計空間探索は、小さなレイテンシの設計を目標とするグローバルコスト関数を用いて開始する。次に、図８Ｂ〜図８Ｄに示されるように、コスト関数重みが面積最小化に関して最大でありレイテンシ最小化に関して最小であるときに最小化された面積の設計が生成するまで設計空間の全体を探索するために、コスト関数重みが適応的に変更される。

図９は、自動的に生成された設計に対する、グローバル・コスト関数重みの効果を示している。面積に関する高い重みは、より面積の小さな設計を生成し、一方、レイテンシに関する高い重みは、レイテンシの小さな設計を生成する。ここで比Ａｘ：Ｌｙは、重みを示す。例えば、Ａ３：Ｌ７は、面積に対する重みが３で、レイテンシに対する重みが７であることを示す。

図１０は、本実施形態に基づく、自動生成される設計についてのインタラクティブ（会話的）な表示の例を示している。ひとたび探索が終了すれば、異なる設計の間のトレードオフを容易に分析できる折れ線グラフ(sequence graph)または棒グラフ(bar chart)内に各設計がプロットされる。異なるオプション（例えば、面積、レイテンシ、スループット、電力、状態の数、メモリ）を示すために、コンボ・ボックス内に与えられた異なる値を選択することによって、Ｘ軸及びＹ軸の値を変更することができる。これは、設計者が、異なるトレードオフ関係を効率的に探索することを支援する。複数の設計のうちの１つをクリックすることによって、本実施形態によって、ＲＴＬコードが自動的に生成される。

次に、クラスタの生成または創出について説明する。ここでは、探索に関し、急速探索モードと超急速探索モードの２つのモードが規定されている。

図１１は、クラスタの生成を示しており、急速探索モードに対応する。これらのクラスタは、クラスタ・ライブラリから、可能な限り最も小さくなるように取り出されたものである。このことは、グローバル・コスト関数を最大化する目標に依存して、特定の属性にクラスタを固定することによって、設計空間を著しく減縮するだろう。グローバル設計探索検索の場合、クラスタに割り当てられる属性は、グローバル・コスト関数を最大化する目標に依存して変化するであろう。

図１２は、できる限り最大のクラスタの生成を示しており、超急速探索モードに対応する。最大のクラスタを生成することは、さらにもっと設計空間を減縮するが、いくつかの最適設計を見逃すことになろう。

《実施例》
次に、実施例に照らして、本実施形態をさらにより詳細に説明する。図３に示される入力が自動化された探索に与えられらるものと仮定する。この実施例では、問題定義は、２つのゴールからなる。すなわち、（１）コスト関数を最小化する設計（例えば、最小の設計、最小のレイテンシを有する設計）を生成すること、及び（２）異なるトレードオフ関係をユーザが分析することができるようにするために、属性とグローバル合成オプションと機能ユニットの数との組み合わせを探索すること、である。これら２つの結果は、前者ができるだけ最小の数の設計を生成することを意味するのに対し、後者はできるだけ多くの異なる組み合わせを生成することを意味しているので、相互に矛盾しているように見えるかもしれない。それにも関わらず、本実施形態は、これら２つのゴールを目的とすることができる。前者は、固定されたＧＣＦを指定してその周りの設計を探索することによって達成される。後者は、全検索を指定することによって達成される。この場合、検索は、適応的にＧＣＦ重みを変更し、検索空間の全体を探索するであろう。

この方法はまた、異なる目的関数に対する最適点を見つけることによって、相反する目的最小化を解決する各探索された設計を分析する。これらの最適点は、パレート(Pareto)点と呼ばれる。ここに示す方法は、有効フロンティア（パレート・フロンティアあるいはパレート・フロントとも呼ばれる）にある全ての設計を見つけることを目標とすることもできる。

図３は、ユーザによって指定される入力の例を詳細に示している。入力は、（１）ここではＢＤＬである、ハードウェア設計用の高レベル言語ソース・コード、（２）グローバル・コスト関数重み、（３）属性とそれらの初期重み、及び、（４）グローバル合成オプションとそれらの重み、である。ユーザは、（ａ）例えば、これらに限られるものではないが、時間または設計の数などの複数の形態で、どれだけ長く探索を実行させるか、（ｂ）探索空間の全体が探索されることを望むのか、あるいは所与のＧＣＦで指定された設計空間だけか、及び（ｃ）探索中にいずれの属性または合成オプションも無視されるべきか、を指定するために、オプション・ファイル中のいくつかのオプションを指定することができる。こららは、可制御性オプションのいくつかの例に過ぎず、探索を制御することができる任意の他のオプションを含むことができる。

ソース・コードが解析され（パースされ）、依存関係木が生成される。例えば、ネストされたループの場合には最内側ループをアンロールすることに比べて外側ループをアンロールすることが面積及びレイテンシに影響を及ぼすなど、同じ種類の操作に適用される属性の影響は、解析木における操作の位置に基づいて異なるであろうから、依存関係木を生成することは重要である。この場合、ファンクション・コールを有するループをアンロールすることは、第２のループに比べ、面積に対する影響が大きいであろう。属性オプションの重みは、したがって、操作の位置に基づいて調整される。この自動的な重みの適応化は、入力オプション・ファイル中で有効にされたり無効にされたりすることができる。

ひとたびこのデータ構造が生成されると、メインの探索ループが開始する。ここには２つのオプションがある。第１のオプションは、「所与の固定されたＧＣＦに関して探索を実行」である。終了条件は、タイムリミット、設計の数、新しい設計が生成されなくなるまで実行、及び、既に生成された設計を改善しない指定された数の設計が生成された、のいずれか１つとすることができる。この場合、所与のＧＣＦを最大化する設計が生成される。第２の場合は、完全設計空間探索を実行する。この場合、ＧＣＦ重みは、最初の設計が面積を最小化するように、初期化される。各反復の間、レイテンシを最小化する設計を最終結果が生成するまで、ＧＣＦ重みは更新される。

４種類の探索を実行することができる。すなわち、（ａ）属性の探索、（ｂ）グローバル合成オプション、（ｃ）機能ユニットの数と種類、及び（ｄ）クロック周期である。これら４種類のうちいずれか１つを探索することができる。あるいは、２種類、３種類または４種類の任意の組み合わせを探索することもできる。

３つのオプションが探索されることが望まれる場合、フローは、図４に示したようになる。属性の新しいユニークな組が生成される。次に、グローバル合成オプションの新しい組が生成され、最後に、機能ユニットの数が生成される。ＦＵの数は、これに限定されるものではないが、バイナリ・サーチのようなさまざまなアルゴリズムによって探索される。最後のＦＵの探索は、ＦＵについての可能な最小個数を伴って終了する。ひとたびＦＵ探索が終了してしまえば、グローバル合成オプションが再生成されて、属性の固定された組についてのこれらに関する効果が調べられ、ＦＵの数が再探索される。グローバル合成オプションが完全に探索され終えるまで、反復の全体が繰り返される。ひとたび探索が終了したら、属性の新しい組が、再度、生成され、反復の全体が繰り返される。指定された終了基準に達した後、グローバル・コスト関数が適応化されるか、あるいは探索が終了する。

上記の説明では、探索には３つの主要なステップ（すなわち、属性の生成、グローバル合成オプション、及びＦＵの探索）がある。これらに加え、上記のクラスタ形成を実行することができる。クラスタ生成は、いくつかの最適設計を見逃すという犠牲を払って、探索をスピードアップさせるオプションである。クラスタリングは、属性探索とともにのみ機能する。言い換えれば、クラスタリングは、基本的に、属性探索のオプションである。さらに、上述した第４のステップすなわちクロック・ステップ探索を実行することもできる。

探索は、生成された設計ごとに、属性と合成オプションと使用されたＦＵの数からなるユニークな組を生成する。探索の結果の書式（フォーマット）は、高レベル合成ツールに依存して変化するであろう。結果は、例えば図１０に示したように、視覚的に表示されることができる。図１０に示したものでは、設計者は、異なる設計のトレードオフ関係を容易に探索できる。

図３は、第１のループがそれに関連したマニュアル属性を有する、高レベル言語のソース・コードの例を示している。これは、そのループに関してそれらの属性のみが探索されることを示している。２番目のループの場合、属性ライブラリ中で指定された全ての属性が、探索中に考慮されるであろう。

上述したように、本実施形態は、ハードウェア設計を目的とした動作記述に対するマイクロアーキテクチャ設計空間探索技術を提供する。時刻概念を含まないユニークな高レベル言語記述からの制約条件（例えば、面積、レイテンシ、クリティカル・パス、電力）の組を仮定して（または仮定しないで）、一連のユニークなハードウェア・アーキテクチャが自動的に生成される。設計空間は検索されて、各制約条件を最大化する異なる設計を自動的に生成する。異なる設計の間でのトレードオフを解析する容易なやり方のために、結果が設計者に対して複数のやり方で提示される。

本発明の上述した実施形態は、例示のみを目的としたものである。高レベル合成との関連で本発明を説明してきたが、本発明は、レジスタ転送レベル（ＲＴＬ；register transfer level）やデジタル・システムなどのＥＤＡでの他の領域にも適用することができるだろう。さらに、本発明が、これらの例からは外れる、より広い応用も持つことを十分に予想される。例えば、設計者は、初期探索を実行させることができるであろう。ひとたび探索が終了すると、設計者は、結果を視覚化し、入力オプション、属性またはグローバル合成オプション重みを変更し、探索の実行を継続することができる。各設計が、属性とグローバル合成オプションとＦＵとのユニークな組をログ・ファイルに登録するので、設計を再実行したときに、これらの新しい組み合わせが保証される。

探索は実行に長い時間を要するので、単一のプロセッサ上で実行する準備がなされており、あるいは、探索を加速するためにマルチプロセッサ上で実行する準備がなされる。設計者は、いつでも、探索を中断し再開させることができ、探索を中断して後で続行させることができ、複数の日にわたって探索を実行させたままとすることもできる。設計者は、探索の結果をいつでも見ることができ、探索の結果に満足すれば、探索を停止することができる。

例えば回路設計に関連して本発明を示したが、本発明の方法は、例えば、デジタル回路に関連する設計問題、スケジューリング、化学プロセス、制御システム、ニューラル・ネットワーク、検証及び認証方法、リグレッション・モデル、未知システム、通信ネットワーク、光学回路、センサを含む、他の多くの種類の設計問題に適用することができる。本発明の方法は、道路システムや、水路網、その他の大規模物理ネットワーク；光学；機械部品；及び光−電気部品などのフロー・ネットワーク設計問題にも適用可能である。

理解の明りょうさを目的として、本発明の上述の実施形態は詳細に記述されているが、添付の特許請求の範囲内で、ある変更や改良を実施できることは、明らかであろう。したがって、本実施形態は、説明に役立つものではあるが、発明を限定するものではないと考えるべきである。本発明は、ここに説明した詳細に限定されるべきではなく、添付の特許請求の範囲とその等価物の範囲内で変更されることができる。特許請求の範囲において、要素及び／またはステップは、特許請求の範囲中で明示されていない限り、特定の操作の順番を意味しているわけではない。

したがって、上記は、本発明の原理を説明するためだけのものであるとみなされる。また、多数の改良や変更を当業者は容易にすることができるであろうから、ここに示され描かれた実際の構造や操作に本発明を限定することは求められない。全ての適切な変更物及び等価物は、本発明の範囲内に含まれるものとなるであろう。

Claims (15)

1. 時刻概念を含まない高レベル言語の設計空間を自動的に探索する方法であって、
   制約条件、高レベル言語ソース・コード、入力オプション、及びライブラリ情報をコンピュータに入力するステップと、
   前記コンピュータが、探索可能な属性を有する全ての操作についての、時刻概念を有しないオリジナルのソース・コードの依存関係解析木を生成するステップと、
   前記コンピュータが、前記依存関係解析木における前記操作の位置に基づいて、属性の重みを自動的に調整するステップと、
   面積、レイテンシ及び電力を削減するために、各操作の自然な傾向に応じ、前記コンピュータが、ユーザから外部入力によって指定されたまたは内部で宣言された属性に自動的に偏りを与えるステップと、
   前記属性を選択する実際の確率に対し、前記コンピュータが、当該属性の重みをマッピングして、前記ユーザによって指定されたグローバル・コスト関数の最小化を導くステップと、
   下記（ａ）〜（ｃ）：
   （ａ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対する前記属性のユニークな組を生成することと、
   （ｂ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対するグローバル合成オプションのユニークな組を生成することと、
   （ｃ）前記高レベル言語ソース・コードに含まれる演算に対する機能ユニットの数及び種類の組を生成することと、
   の少なくとも１つを実行することにより、前記コンピュータが設計空間を探索する探索ステップと、
   前記探索ステップで得られた結果に基づいて、前記コンピュータが高レベル合成を行う高レベル合成ステップと、
   所定の終了条件を満たしているときに、前記コンピュータが、前記属性と前記グローバル合成オプションと前記機能ユニットの数及び種類とに関する情報の組を含む新しい設計を出力し、前記所定の終了条件を満たしていないときには前記探索ステップと前記高レベル合成ステップとを繰り返すステップと、
   を有し、
   前記属性は、所与のソース・コードの合成において高レベル合成ツールの動作を案内するものである、方法。
2. 前記依存関係解析木での前記操作の位置に基づいて、前記属性の重みを動的に調節することをさらに有する、請求項１に記載の方法。
3. 出力される各設計が一意のものとなるように、使用されたローカル属性とグローバル合成オプションと機能ユニットの数及び種類とに応じて、出力された各新しい設計に対する一意のハッシュ・インデックスを生成することをさらに有する、請求項１に記載の方法。
4. 所与の探索中であるいは前記探索を再実行する際にエラーが再度起こることを防ぐために、不正な属性の割り当て、不正な合成オプションの割り当てまたはそれらの組み合わせによるいかなる合成エラーも記録することをさらに有する、請求項１に記載の方法。
5. 同じ設計が再出力されないことを保証する一意のキーを読み出すことによって探索を停止したり続行したりできるように、出力された全ての前記設計を各設計の一意のハッシュ・インデックスとともに登録することを有する、請求項１に記載の方法。
6. 全設計空間探索を実行するために、前記グローバル・コスト関数の重みを適応的に変更することを有する、請求項１に記載の方法。
7. 前記適応的な変更は、小面積の設計をもたらす属性を使用する確率がより高くなるように、より高い面積重みを有する小面積設計から始まり、より小さなレイテンシの設計をもたらす属性とグローバル合成オプションとを選択することについてのより大きな確率を有する高レイテンシ重みを有して終わる、請求項６に記載の方法。
8. 前記オプションは、単一の設計探索か全体探索かのいずれかが打ち切られることになるまでのタイムアウトを指定する、請求項１に記載の方法。
9. 前記オプションは、時刻概念を含まない高レベル言語のソース・コードにおいて、プラグマとして、探索されるべき属性の組を直接指定し、
   所与の属性のみが所与の操作に対して使用され、前記重みは、オプションとして指定可能な、各属性の面積／レイテンシを削減する確率である、請求項１に記載の方法。
10. グローバル・コスト関数に基づいて属性の固定した組が割り当てられる、異なる粒度のクラスタを生成することをさらに有し、
    異なる粒度は、前記設計空間を削減する属性の組み合わせの数を制御し、ここでより大きなクラスタは、より高速の設計空間をもたらすが、最適設計の検出に失敗する可能性があり、
    クラスタ属性は、前記グローバル・コスト関数が最大化する目標が変化したときに、変化することができる、請求項１に記載の方法。
11. 前記オプションは、いつ前記探索を終了するかを指定し、
    所与の数の設計の後で、以前の設計を改善する新規の設計を出力できないときは、前記探索が終了する、請求項１に記載の方法。
12. 前記探索を再実行させて、重複した設計を有しない設計の新たなユニークな組を出力できる、請求項１１に記載の方法。
13. 時刻概念を含まない高レベル言語の設計空間を自動的に探索する装置であって、
    自動化された探索に対する、制約条件、高レベル言語ソース・コード、入力オプション、及びライブラリ情報を含む入力を受け付ける入力装置と、
    前記高レベル言語ソース・コードに基づき、探索可能な属性を有する全ての操作についての、時刻概念を有しないオリジナルのソース・コードの依存関係解析木を生成する解析木生成器と、
    前記依存関係解析木における前記操作の位置に基づいて、属性の重みを自動的に調整する重み調整部と、
    （ａ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対する前記属性のユニークな組を生成することと、（ｂ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対するグローバル合成オプションのユニークな組を生成することと、（ｃ）前記高レベル言語ソース・コードに含まれる演算に対する機能ユニットの数及び種類の組を生成することと、の少なくとも１つを行うことによって設計空間を探索する探索装置と、
    前記探索装置による探索の結果に基づいて高レベル合成を実行する高レベル合成部と、
    探索結果を出力する出力装置と、
    を有し、
    前記属性は、所与のソース・コードの合成において高レベル合成ツールの動作を案内するものであり、
    面積、レイテンシ及び電力を削減するために、各操作の自然な傾向に応じ、ユーザから外部入力によって指定されたまたは内部で宣言された属性に自動的に偏りが与えられ、
    前記属性を選択する実際の確率に対し、当該属性の重みがマッピングされて、前記ユーザによって指定されたグローバル・コスト関数の最小化が導かれ、
    前記出力装置は、所定の終了条件を満たしているときに、前記高レベル合成部から出力された新規の設計を出力する、装置。
14. グローバル・コスト関数に基づいて属性の固定した組が割り当てられる、異なる粒度のクラスタを生成するクラスタ生成器を有する、請求項１３に記載の装置。
15. コンピュータに、
    制約条件、高レベル言語ソース・コード、入力オプション、及びライブラリ情報を受け取る処理と、
    探索可能な属性を有する全ての操作についての、時刻概念を有しないオリジナルのソース・コードの依存関係解析木を生成する処理と、
    前記依存関係解析木における前記操作の位置に基づいて、前記属性の重みを自動的に調整する処理と、
    面積、レイテンシ及び電力を削減するために、各操作の自然な傾向に応じ、ユーザから外部入力によって指定されたまたは内部で宣言された属性に自動的に偏りを与える処理と、
    前記属性を選択する実際の確率に対し、当該属性の重みをマッピングして、前記ユーザによって指定されたグローバル・コスト関数の最小化を導く処理と、
    下記（ａ）〜（ｃ）：
    （ａ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対する前記属性のユニークな組を生成することと、
    （ｂ）前記高レベル言語ソース・コードに含まれる、少なくとも演算、ループ、メモリ及び関数に対するグローバル合成オプションのユニークな組を生成することと、
    （ｃ）前記高レベル言語ソース・コードに含まれる演算に対する機能ユニットの数及び種類の組を生成することと、
    の少なくとも１つを実行することにより設計空間を探索する探索処理と、
    前記探索処理で得られた結果に基づいて高レベル合成を行う高レベル合成処理と、
    所定の終了条件を満たしているときに、前記属性と前記グローバル合成オプションと前記機能ユニットの数及び種類に関する情報の組を含む新しい設計を出力し、前記所定の終了条件を満たしていないときには前記探索処理と前記高レベル合成処理とを繰り返す処理と、
    を実行させ、
    前記属性は、所与のソース・コードの合成において高レベル合成ツールの動作を案内するものである、コンピュータ・プログラム。
    

Images