マルチチャネル回路の自動合成の方法および装置
シングルチャネル回路から時間多重化マルチチャネル回路を自動的に生成する方法および装置である。本発明の少なくとも１つの実施形態は、シングルチャネル回路の設計からマルチチャネル回路の時間多重化設計を自動的に生成することによって時間多重化リソース共有のためのマルチチャネルハードウェアを自動的かつ効率的に合成する。シングルチャネル設計のチャネル固有の要素（例えば、レジスタやメモリ）は、複数のチャネルの信号処理をパイプライン化するための、Ｎ倍の容量を有する、対応する要素に置き換えられる。
【発明の詳細な説明】
【発明の分野】
【０００１】
[0001]本発明はデジタル回路に関し、より詳細には、マルチチャネルハードウェアの自動合成に関する。
【関連技術の説明】
【０００２】
[0002]（例えば、超ＬＳＩ（ＶＬＳＩ）技術の規模の）デジタル回路の設計では、設計者は、コンピュータ支援手法を用いることが多い。複雑なデジタル回路の設計およびシミュレーションを支援する目的でデジタル回路を記述するために、ＨＤＬ（ハードウェア記述言語）などの標準言語が開発されてきた。いくつかのハードウェア記述言語（ＶＨＤＬやＶｅｒｉｌｏｇなど）は、業界標準として進化している。ＶＨＤＬおよびＶｅｒｉｌｏｇは、ゲートレベル、レジスタ転送レベル（ＲＴＬ）、または抽象データ型を用いた動作レベルでのハードウェアモデルの記述を可能にする汎用ハードウェア記述言語である。デバイス技術が進歩し続けるとともに、ＨＤＬをより新しいデバイスや設計スタイルに使えるように適応させるべく、様々な製品設計ツールが開発されている。
【０００３】
[0003]ＨＤＬコードによる集積回路の設計では、最初にコードが作成され、そのコードがＨＤＬコンパイラによってコンパイルされる。ＨＤＬソースコードは、特定のレベルで回路要素を記述したものであり、コンパイラは、コンパイル結果としてＲＴＬネットリストを生成する。ＲＴＬネットリストは、特定ベンダの集積回路（ＦＰＧＡ（フィールドプログラマブルゲートアレイ）やＡＳＩＣ（特定用途向け集積回路）など）のテクノロジ／アーキテクチャに依存しないという意味で、一般にテクノロジ非依存のネットリストである。ＲＴＬネットリストは、（動作表現と異なり）回路要素の回路図表現に対応する。この、テクノロジ非依存のＲＴＬネットリストをテクノロジ固有のネットリストに変換するために、あるマッピング操作が行われる。この操作により、そのベンダのテクノロジ／アーキテクチャで回路を作成することが可能である。ＦＰＧＡベンダらがそれぞれの集積回路内に論理回路を実装するために様々なテクノロジ／アーキテクチャを利用していることはよく知られている。したがって、テクノロジ非依存のＲＴＬネットリストにマッピングが施されて作成されるネットリストは、個々のベンダのテクノロジ／アーキテクチャに固有のものである。
【０００４】
[0004]回路の設計では、特定の設計目標を最適化するために、よく変形を行う。例えば、ある回路で使用される面積を減らすために変形が行われる場合がある。集積回路で使用されるシリコン面積を減らすための体系化されたアプローチの１つが、折り畳み変形（Ｆｏｌｄｉｎｇ Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）である。単一の機能単位に対して複数のアルゴリズム操作を実行することにより、実装時の機能単位数を減らすことが可能である。折り畳み変形の詳細については、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年）に説明がある。
【０００５】
[0005]デジタル回路の配線では、時間多重化リソース共有が行われてきた。例えば、「Ｐａｒａｌｌｅｌ Ｏｐｅｒａｔｉｏｎｓ ｉｎ ｔｈｅ Ｃｏｎｔｒｏｌ Ｄａｔａ ６６００」（ＡＦＩＰＳ Ｐｒｏｃｅｅｄｉｎｇｓ ＦＪＣＣ、Ｐａｒｔ ２、Ｖｏｌ．２６、１９６４年、３３〜４０頁）でＪ． Ｅ． Ｔｈｏｒｎｔｏｎによって説明されている、ＣＤＣ ６６００コンピュータのＰｅｒｉｐｈｅｒａｌ ａｎｄ Ｃｏｎｔｒｏｌ Ｐｒｏｃｅｓｓｏｒｓ（ＰＡＣＰｓ）では、ラウンドロビン様式で共通リソースにアクセスすることによって実行ハードウェアを共有する。また、マルチチャネルフィルタ用リソース共有に関する別の例を、「ＦＰＧＡ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ａ Ｓｅｒｉａｌ Ｏｒｇａｎｉｚｅｄ ＤＡ Ｍｕｌｔｉｃｈａｎｎｅｌ ＦＩＲ Ｆｉｌｔｅｒ」（Ｊｈｏｎ Ｊ．Ｌｅｏｎ Ｆｒａｎｃｏ、Ｍｉｇｕｅｌ Ａ．Ｍｅｌｇａｒｅｊｏ、Ｔｅｎｔｈ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙｓ、Ｍｏｎｔｅｒｅｙ、Ｃａｌｉｆｏｒｎｉａ、２００２年２月２４〜２６日）に見ることができる。
【０００６】
[0006]従来の折り畳みアルゴリズムは、所与の設計から、時間多重化リソース共有を伴う設計を自動的に生成することが可能である。従来の折り畳みアルゴリズムは、単一機能単位への時間多重化が可能な複数のアルゴリズム操作を識別して、機能単位（例えば、加算器、マルチプレクサ）の数を減らすことが可能である。ただし、デジタル信号処理（ＤＳＰ）設計の場合、従来の折り畳みアルゴリズムは、並列処理および依存性の抽出と、計算スケジュールの最適化とに多大な時間がかかる。ハードウェア合成の複雑さは、計算に関与する論理単位の数に対して比例を超える変化で大きくなる。したがって、設計規模が大きくなるほど、回路の最適化および変形が困難になる。
【発明の概要】
【０００７】
[0007]本明細書では、シングルチャネル回路から時間多重化マルチチャネル回路を自動的に生成する方法および装置について記載する。
【０００８】
[0008]本発明の少なくとも１つの実施形態は、シングルチャネル回路の設計からマルチチャネル回路の時間多重化設計を自動的に生成することによって時間多重化リソース共有のためのマルチチャネルハードウェアを自動的かつ効率的に合成する。シングルチャネル設計のチャネル固有の要素（例えば、レジスタやメモリ）は、複数のチャネルの信号処理をパイプライン化するための、Ｎ倍の容量を有する、対応する要素に置き換えられる。
【０００９】
[0009]本発明の一態様では、デジタル回路を設計する方法は、シングルチャネル回路である第１の設計を受け取ることと、その、シングルチャネル回路である第１の設計を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成することとを含む。一例では、マルチチャネル回路の自動生成後に、（例えば、クロック周波数を高めるために）時間多重化マルチチャネル回路に対してリタイミングが実施される。一例では、（例えば、マルチチャネル回路の遅延を調整するために）時間多重化マルチチャネル回路のパイプラインレジスタの組が識別され、除去される。一例では、時間多重化マルチチャネル回路にパイプラインレジスタの組が挿入される。一例では、複数のチャネルによる第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）が生成され、複数のチャネル用の複数の入力を第１の設計の入力ラインに時間多重化するために多重化回路が生成され、第１の設計の出力ラインからの信号を複数のチャネル用の複数の出力に時間多重分離するための多重分離回路が生成される。一例では、第１の設計における要素（例えば、定数、ランダムアクセスメモリ（ＲＡＭ）要素、読み出し専用メモリ（ＲＯＭ）要素、レジスタ、フリップフロップ、または負遅延レジスタ）が、対応する複数の、またはより大きな要素に置き換えられ、その要素のそれぞれは、ＦＳＭの状態に応じて複数のチャネルのうちの１つのチャネルに対してアクセスされる。一例では、チャネル固有でない順次要素が識別された後、第１の設計における他の順次要素がチャネル固有と識別され、チャネル固有の要素だけが、対応する複数の要素に置き換えられる。チャネル固有でない順次要素には、（例えば、順次要素のフィードフォワード切断集合の数を調べることによって、チャネル固有でない順次要素として識別された）パイプラインレジスタの組が含まれる。一例では、チャネル固有の順次要素が、複数の移動順次要素のカスケード接続に置き換えられ、別の例では、チャネル固有の順次要素が、ＦＳＭの状態に応じてアドレス指定される、複数のメモリ要素（または、容量がより大きなメモリ要素）に置き換えられる。
【００１０】
[0010]一例では、第１の設計における順次要素（例えば、フリップフロップ、レジスタ、メモリ要素、定数、および負遅延レジスタ）が、第２の設計を生成するために、対応する要素（例えば、レジスタのカスケード接続、デュアルポートＲＡＭ、またはＲＡＭとシフトレジスタの組み合わせ）に置き換えられる。対応する要素は、複数のチャネルからの信号を処理するタイミングに応じて、第２の設計において順次アクセスされる。一例では、対応する要素が、移動要素のカスケード接続であり、別の例では、対応する要素が、順次アドレス指定される（例えば、Ｎ個のメモリ要素からなるメモリが、Ｍチャネル回路に対応するようにＮ×Ｍ個のメモリ要素を有するメモリに置き換えられる）。
【００１１】
[0011]本発明の一態様では、デジタル回路を設計する方法が、シングルチャネル回路である第１の設計を受け取ることと、第１の設計のシングルチャネル回路の集合体と、そのシングルチャネル回路の集合体における並列処理を指示する情報とを生成することと、その情報を用いて、そのシングルチャネル回路の集合体に折り畳み変形を適用して、時間多重化マルチチャネル回路である第２の設計を生成することとを含む。例えば、この情報は、折り畳みの集合の情報を含み、この、折り畳みセットの情報は、折り畳みアルゴリズムを誘導して折り畳み変形を実施するために用いられる。シングルチャネル回路である第１の設計に負遅延レジスタを含めることが可能であり、変形後にリタイミング操作を実施することが可能である。
【００１２】
[0012]本発明は、方法と方法を実施する装置とを含み、装置は、方法を実施するデータ処理システムと、データ処理システムで実行されたときに方法をデータ処理システムに実施させるコンピュータ可読媒体とを含む。
【００１３】
[0013]本発明の他の特徴は、添付図面と、この後の詳細説明から明らかになるであろう。
【００１４】
[0014]添付図面の図中では、本発明が限定ではなく例として示されており、添付図面において類似した参照符号は同様の要素を指す。
【詳細な説明】
【００１５】
[0033]以下の説明および図面は、本発明の例示であって、本発明を限定するものと解釈されてはならない。本発明が完全に理解されるように、数多くの具体的な詳細について説明する。ただし、場合によっては、本発明の説明が不明瞭にならないように、よく知られている事柄や一般的な事柄については詳しく説明しない。本開示におけるある実施形態または一実施形態への参照は、必ずしも同じ実施形態への参照とは限らず、そのような参照は、少なくとも１つの実施形態への参照を意味する。
【００１６】
[0034]本発明の少なくとも１つの実施形態は、シングルチャネル回路の設計からマルチチャネル回路の時間多重化設計を自動的に生成することによって時間多重化リソース共有のためのマルチチャネルハードウェアを自動的かつ効率的に合成しようとするものである。
【００１７】
[0035]ハードウェア合成の複雑さは、設計に関与する論理単位の数に対して比例を超える変化で大きくなる。マルチチャネル回路は、一般に、独立した同一のシングルチャネルを複数有する。Ｎチャネル回路は、一般に、ハードウェア合成時に回路を最適化する際に、対応するシングルチャネル回路のＮ倍を超える数の論理（計算）単位を必要とする。使用される機能単位の数を減らすために、従来の折り畳み変形をマルチチャネル回路に適用して時間多重化回路を生成する場合、従来の折り畳みアルゴリズムでは、並列処理および依存性の抽出と、計算スケジュールの最適化とに多大な時間がかかる。したがって、時間多重化リソース共有のためのハードウェア合成の最適化は、一般に計算量が非常に多い（特に設計規模が大きい場合）。
【００１８】
[0036]本発明の一実施形態によれば、複数のチャネルの時間多重化リソース共有のための合成の最適化は、シングルチャネルの設計に基づく。並列処理および依存性を抽出する計算は不要であり、従来の折り畳み変形の大量の計算を行うことなく、シングルチャネルの設計から、時間多重化リソース共有を伴う設計を生成することが可能である。一例では、シングルチャネル設計のチャネル固有の要素（例えば、レジスタやメモリ）を、複数のチャネルの信号処理をパイプライン化するためにＮ倍を超える容量の、それらに対応する要素に置き換えることによって、シングルチャネル設計が時間多重化Ｎチャネル設計に変形される。後でさらに例を挙げて詳しく説明する。
【００１９】
[0037]本発明の方法の多くは、従来の汎用コンピュータシステムなどのデジタル処理システムで実施可能である。１つの機能だけを実行するために設計またはプログラムされた特殊用途コンピュータも使用可能である。
【００２０】
[0038]図１は、本発明に使用可能な、一般的なコンピュータシステムの一例である。図１は、コンピュータシステムの各種コンポーネントを示しているが、それらのコンポーネントの相互接続の特定のアーキテクチャまたは様式を表すことを意図したものではないことに注意されたい。そのような細部は、本発明と特に関係するものではないからである。また、これよりコンポーネントが少ないか、あるいは多いネットワークコンピュータや他のデータ処理システムも本発明に使用可能であることも理解されよう。図１のコンピュータシステムは、例えば、Ｓｕｎワークステーション、またはＷｉｎｄｏｗｓオペレーティングシステムが動作するパーソナルコンピュータ（ＰＣ）、またはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータであってよい。
【００２１】
[0039]図１に示すように、データ処理システムの形をとるコンピュータシステム１０１は、マイクロプロセッサ１０３、ＲＯＭ １０７、揮発性ＲＡＭ １０５、および不揮発性メモリ１０６に結合されたバス１０２を含む。マイクロプロセッサ１０３は、Ｍｏｔｏｒｏｌａ，Ｉｎｃ．製またはＩＢＭ製のＧ３またはＧ４マイクロプロセッサであってよく、図１の例に示すように、キャッシュメモリ１０４に結合される。バス１０２は、これらの様々なコンポーネントを相互接続し、さらに、コンポーネント１０３、１０７、１０５、および１０６を、ディスプレイコントローラおよびディスプレイ機器１０８、ならびにマウス、キーボード、モデム、ネットワークインターフェース、プリンタ、スキャナ、ビデオカメラ、および他の、当業者にはよく知られている機器などが挙げられる入出力（Ｉ／Ｏ）機器などの周辺機器と相互接続する。通常、入出力機器１１０は、入出力コントローラ１０９を介してシステムに結合される。揮発性ＲＡＭ １０５は、一般に、メモリ内のデータをリフレッシュまたは保持するために継続的な給電が必要なダイナミックＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、一般に、システムへの給電がなくなってもデータを保持する磁気ハードドライブ、光磁気ドライブ、光ドライブ、ＤＶＤ ＲＡＭ、または他のタイプ、のメモリシステムである。一般には不揮発性メモリもランダムアクセスメモリであるが、ランダムアクセスメモリでなくてもかまわない。図１では、不揮発性メモリは、データ処理システムのそれ以外のコンポーネントと直接結合されているローカルデバイスであるが、本発明は、モデムやイーサネットインターフェースなどのネットワークインターフェースでデータ処理システムと結合されているネットワークストレージ機器のような、システムから離れている不揮発性メモリも利用可能であることが理解されよう。バス１０２は、当業者にはよく知られている様々なブリッジ、コントローラ、および／またはアダプタで相互接続された１つまたは複数のバスを含むことが可能である。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ（ユニバーサルシリアルバス）周辺機器を制御するＵＳＢアダプタ、および／またはＩＥＥＥ−１３９４周辺機器を制御するＩＥＥＥ−１３９４バスアダプタを含む。
【００２２】
[0040]本発明の態様が少なくとも部分的にソフトウェアで実施可能であることは、以下の記述から明らかであろう。すなわち、本手法は、コンピュータシステムまたは他のデータ処理システムにおいて、そのプロセッサ（マイクロプロセッサなど）が、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモートストレージ機器に格納されている命令のシーケンスを実行するのに応答する形で実施されることが可能である。様々な実施形態において、本発明を実装するために、ハードワイヤード回路をソフトウェア命令を組み合わせて用いることが可能である。したがって、本手法は、ハードウェア回路とソフトウェアの特定の組み合わせに限定されるものではなく、また、データ処理システムで実行される命令の特定のソースに限定されるものでもない。さらに、以下の記述では、説明を単純にするために、様々な機能や操作を、ソフトウェアコードによって実行または起動されるものとして説明する。しかしながら、当業者であれば、そのような表現が、プロセッサ（マイクロプロセッサ１０３など）によるコードの実行の結果として機能が実施されることを意味することを理解されよう。
【００２３】
[0041]データ処理システムによって実行されたときに本発明の各種方法をシステムに実行させるソフトウェアおよびデータを格納するために、マシン可読媒体を用いることが可能である。この実行可能ソフトウェアおよびデータは、例えば、図１に示したＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、および／またはキャッシュ１０４など、様々な場所に格納することが可能である。このソフトウェアおよび／またはデータの一部を、これらのストレージ機器の任意のいずれかに格納することが可能である。
【００２４】
[0042]したがって、マシン可読媒体には、マシン（例えば、コンピュータ、ネットワーク機器、携帯情報端末、製造ツール、１つまたは複数のプロセッサの集合を有する任意の機器など）からのアクセスが可能な形で情報を提供する（すなわち、格納および／または送信する）任意のメカニズムが含まれる。例えば、マシン可読媒体として、記録可能または記録不可能媒体（例えば、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイスなど）、ならびに電気、光、音、または他の形で伝搬する信号（例えば、搬送波、赤外線信号、デジタル信号など）などがある。
【００２５】
[0043]図２は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能なシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。シングルチャネル回路２００は、ライン２０１で入力を受け取り、ライン２０３で出力を生成する。このシングルチャネル設計は、定数２１１、２１３、および２１５と、乗算器２２１、２２３、および２２５と、加算器２３５および２３７と、レジスタ（フリップフロップ）２３１および２３３とを含む。乗算器２２１、２２３、および２２５がライン２０１の入力に定数２１１、２１３、および２１５を乗じ、それらの結果を加算器２３５および２３７が合計して、ライン２０３に出力を生成する。ライン２０５のクロック信号Ｃｓが、シングルチャネル回路内の処理のパイプライン化と同期とを制御する。
【００２６】
[0044]図３は、図２の例の様々な場所での信号波形を示す図である。時刻ｔ０（３０１）に、入力信号Ｉ１がライン２０１に到着する。時刻ｔ１（３０３）に、レジスタ２３１が乗算器２２１の結果を出力してラインＡ ２０７に信号ＳＡ ３１３を生成する。時刻ｔ２（３０５）に、レジスタ２３３が加算器２３５の結果を出力してラインＢ ２０９に信号ＳＢ ３１５を生成する。これは、信号ＳＡ ３１３と乗算器２２３の出力との和である。時刻ｔ３に、加算器２３７が信号ＳＢ ３１５と乗算器２２５の出力とを合計して出力ライン２０３に信号Ｏ１ ３１７を生成する。
【００２７】
[0045]図４は、図２のシングルチャネルフィルタの集合体に対応する２チャネルフィルタの例を示す図である。例えば、回路４０１および４０３は、図２の回路２００と同じ要素および構成を有する。ハードウェアシステムの自動合成についての従来のソリューションでは、マルチチャネルシステムを特別に扱うことはしない。従来の方法では、マルチチャネル設計を、シングルチャネルシステムの大きな集合体として扱う。一般に、従来の方法は、設計に内在する高レベル並列処理を何ら示すことなく、図４に示すような２チャネルフィルタを提示する。したがって、ハードウェア合成ソフトウェアプログラムは、大量の計算を要する、並列処理および依存性を抽出するタスクを実行する。時間多重化リソース共有を伴う設計を生成するためには、折り畳み変形を適用することが可能である。したがって、従来の方法は、大量の計算を必要とする。さらに、マルチチャネルシステムがシングルチャネルシステムの集合体として解釈される場合は、内在する高レベル並列処理が見逃される可能性があり、結果として、折り畳み変形が適用される際にさらに多くの計算リソースが費やされること、および／または所与の設計が十分に最適化されないことが起こる。
【００２８】
[0046]本発明の一実施形態では、シングルチャネルシステムの集合体の中の並列処理に関連する情報は、そのシングルチャネル設計から自動的に生成されるが、この情報が生成されるのは、シングルチャネルシステムの集合体が時間多重化回路に自動的に変形される際に折り畳み変形が適用されるように汎用折り畳みアルゴリズムを誘導するためでもある。例えば、一般的な折り畳みアルゴリズム（例えば、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、１４９〜１８７頁）で説明されている折り畳みアルゴリズムなど）では、折り畳みの集合を識別することは、時間のかかる操作である。折り畳みの集合は、時間多重化によって同一機能単位で実行されることになる操作の集合である。シングルチャネル設計からシングルチャネルシステムの集合体が自動的に生成される場合は、大量の計算を行うことなく、折り畳みの集合を生成することが可能である。そのように識別された折り畳みの集合は、一般的な折り畳みアルゴリズムを、シングルチャネルシステムの集合体を変形することに誘導するために用いられることが可能である（例えば、そのような情報を用いて操作を効率化するように従来の折り畳みアルゴリズムを修正することが可能である）。
【００２９】
[0047]本発明の少なくとも１つの実施形態では、シングルチャネルシステムの大きな集合体に折り畳み変形を適用する代わりに、シングルチャネル設計に自動変形を適用して、時間多重化リソース共有を可能にする設計を生成することによって、マルチチャネル回路内の並列処理を漏れなく探り出す。
【００３０】
[0048]本発明の一実施形態は、並列処理および依存性の抽出、計算スケジュールの最適化、その他に時間を費やすことを避けるために、最初からマルチチャネル動作を想定する。この実施形態は、システムのシングルチャネルバージョンを入力と見なし、シンプルなマッピングを適用して、マルチチャネルシステムに内在する高レベル並列処理を非常に効率的に利用する。結果として得られるマルチチャネル設計の、独立した各スレッド内のデータフローが同一であるので、結果として回路の制御は最小限である。
【００３１】
[0049]図５は、本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成される２チャネルフィルタの例である。機能単位（例えば、乗算器や加算器）は、チャネル固有ではない。定数Ｃ１、Ｃ２、およびＣ３（２１１、２１３、および２１５）はチャネル固有ではないので、これらも修正なしで共有されることが可能である。レジスタは、このケースではチャネル固有である。したがって、シングルチャネル設計２００のレジスタ２３１と２３３とは、２個のシフトレジスタのカスケード接続５３１、５３３と５３５、５３７とに置き換えられる。（例えば、図４のチャネル４０１および４０３の入力４１１および４１３に対応する）入力５０１および５０３が、信号ＳＭ（５０７）に応じて、マルチプレクサ５４１によって入力ライン５０５に時間多重化され、（例えば、図４のチャネル４０１および４０３の出力４２１および４２３に対応する）出力５０９が、デマルチプレクサ５４３によってライン５１３および５１５に多重分離される。マルチプレクサ５４１（またはデマルチプレクサ５４３）の生成は、複数のチャネルが複数のポートで信号を受信（または生成）するかどうかに応じて省略可能であることが理解されよう。
【００３２】
[0050]図６は、図５の例の様々な場所での信号波形を示す図である。入力信号Ｉ１（６１５）およびＩ２（６１７）は、制御信号ＳＭ（６１３）の状態に応じて、信号ＳＩとして時間多重化される。シングルチャネル回路の一般的なクロックサイクル（例えば、図３の時刻ｔ０ ３１０からｔ１ ３０３。これは図６の時刻ｔ０ ６０１からｔ２ ６０３に対応する）では、各入力信号が１つのタイムスロットに割り当てられる（例えば、信号Ｉ１ ６１５がスロット６２１に、信号Ｉ２ ６１７がスロット６２２に割り当てられる）。所与のスロットに割り当てられた入力信号は、論理単位によって処理され、さらなる処理のために、レジスタのカスケード接続によってパイプライン移送される。例えば、ＳＩのスロット６２１に割り当てられた信号Ｉ１ ６１５に定数２１１が乗ぜられて、時刻ｔ1に、レジスタ５３１からのラインＡ１（５２１）に、ＳＡ１の中間結果６３１が生成される。中間結果６３１が、レジスタ５３３によって遅延され、時刻ｔ２ ６０３に、ラインＡ２（５２３）でＳＡ２の出力信号６４１となり、その後に、信号Ｉ１ ６１５が乗算器２２３の入力として、再度ＳＩのスロット６２３に割り当てられる。時刻ｔ３ ６０４に、加算器２３５の結果がレジスタ５３５から出力されて、ラインＢ１（５２５）にＳＢ１の信号６５１が生成され、これが同様にレジスタ５３７によって遅延されて、時刻ｔ４ ６０５に、ラインＢ２（５２７）にＳＢ２の信号６６１が出力される。その後に、信号Ｉ１ ６１５が乗算器２２５の入力として、再度ＳＩのスロット６２５に割り当てられる。時刻ｔ５ ６０６に、ラインＯ（図５の５０９）でＳＯの信号６７１（入力信号Ｉ１ ６１５に対する加算器２３７の結果）が、デマルチプレクサ５１３による出力のために待機している。同様に、信号６７２は、入力信号Ｉ２ ６１７がスロット６２２、６２４、および６２６に割り当てられて計算された結果である。この後も、前の入力に基づく結果が中間的な次のクロックサイクルで利用可能になるように、前の入力からの中間結果がシステム内をパイプライン移送される（例えば、入力Ｉ１のサンプル６２３、６２５、および６２７に基づく結果がタイムスロット６７３で利用可能になる）。
【００３３】
[0051]したがって、図５および６に示すように、シングルチャネル設計におけるレジスタがレジスタのカスケード接続に置き換えられた場合は、レジスタのカスケード接続の出力がマルチチャネル回路における信号処理のためのタイムスロット割り当てに同期するように、シングルチャネル設計のレジスタに格納された中間結果が、マルチチャネル設計におけるレジスタのカスケード接続をパイプライン移送される。本発明の一実施形態では、シングルチャネル設計におけるチャネル固有の各順次要素（例えば、レジスタ、フリップフロップ、メモリ要素）が、Ｎ倍を超える容量の、対応する要素（例えば、レジスタまたはフリップフロップのカスケード接続、タイムスロット割り当てに応じてアドレス指定されるデュアルポートＲＡＭ、ＲＡＭとシフトレジスタの組み合わせ、その他）に置き換えられる。
【００３４】
[0052]図７は、本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。図２のシングルチャネル設計２００を図７の時間多重化Ｎチャネル設計７００に自動的に変換するために、図２のレジスタ２３１がＮ個のシフトレジスタのカスケード接続７１１〜７１９に置き換えられ、図２のレジスタ２３３がＮ個のシフトレジスタのカスケード接続７２１〜７２９に置き換えられる。入力信号に対するタイムスロット割り当てを制御する信号を生成するために、モジュロ−Ｎカウンタ７０５が用いられる。ライン７０７でのモジュロ−Ｎカウンタ７０５の出力がｉ（ｉ＝０，１，．．．，Ｎ−１）の場合、マルチプレクサ７０１は、ライン７０９への入力信号として信号Ｉｉ＋１を選択する。同様に、図７の加算器２３７の出力信号がデマルチプレクサ７０３によってデコードされて、モジュロ−Ｎカウンタ７０５の出力に対応するチャネルの出力信号が生成される。
【００３５】
[0053]図８は、本発明の一実施形態による、マルチチャネルフィルタの出力を多重分離する出力デコーダおよびラッチ回路の例を示す図である。テスタ８１１、８１３、・・・、８１９は、（例えば、図７のモジュロ−Ｎカウンタ７０５からの）選択信号８４１の状態に応じてラッチ８０１、８０３、・・・、８０９を制御する。ライン８４３の信号（例えば、図７の加算器２３７の出力）は、選択信号の状態がテスタ（８１１〜８１９）の定数（８２１〜８２９）のうちの１つと一致したときに、それと対応する、出力ライン８３１、８３３、・・・、８３９のうちの１つでラッチされる。
【００３６】
[0054]図９は、本発明の代替実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの別の例である。図９では、各入力信号を処理するために、回路２００がラウンドロビン様式でアクセスされる。モジュロ−３カウンタ９０７により、各チャネルが次のチャネルの信号の処理に使用されるまでに、各チャネルの入力信号を完全に処理して出力信号を生成することが可能である。モジュロ−Ｎカウンタ９０５は、回路２００で処理されるチャネルの信号を選択する。図９の方法は、マルチチャネル設計の生成時のシングルチャネル回路の修正がより少なくなるが、図９の回路は図７の回路よりスループットが小さい。シングルチャネル設計での信号のパイプライン移送が、図９では、ラウンドロビン方式であるために、十分に利用されていない。入力信号および出力信号の構成によっては、図９のマルチチャネル設計を用いた場合に、各チャネルの信号の処理遅延を最小化できる可能性がある。しかしながら、一般には、異なるチャネルの入力信号はラウンドロビン様式では到着せず、むしろ、異なるチャネルの入力信号は同じタイミングで到着することが理解されよう。入力信号がラウンドロビン様式で到着するように入力信号をリタイミングするために、入力信号とマルチプレクサ９０１との間にバッファを用いることが可能である。そのようなバッファは、入力信号を同じタイミングでサンプルし、チャネルごとに異なる時間量だけ遅延させて、サンプルされた信号がラウンドロビン様式でマルチプレクサ９０１に到着するようにする。
【００３７】
[0055]図７の時間多重化マルチチャネルは、クロック信号ＣＮ（７４１）の周波数がシングルチャネルシステムのクロック信号（例えば、図４のクロック信号ＣＳ）の周波数のＮ倍である場合は、（例えば、図４の）シングルチャネルシステムの集合体を直接置き換えることが可能であることに注意されたい。図９の設計を用いる場合は、入力をリタイミングするために追加回路（例えば、入力信号のタイミングと処理のためのタイムスロット割り当てとに応じてアドレス指定されるＲＡＭのブロック）を用いることが可能である。
【００３８】
[0056]本発明の一実施形態では、シングルチャネル設計の各チャネル固有要素（例えば、レジスタ、定数、ＲＯＭ、またはＲＡＭ）が、マルチチャネル入力の処理をパイプライン化する、対応する要素に置き換えられる。各レジスタ（またはフリップフロップ）は、シフトレジスタのカスケード接続に置き換えられるチャネル固有レジスタと見なすことが可能であるが、パイプラインレジスタは、非チャネル固有レジスタとして識別されることが可能である。パイプラインレジスタがシフトレジスタのカスケード接続に置き換えられない場合でも、時間多重化共有チャネル内のタイミングは、チャネルの入力に対して同期することが可能である。
【００３９】
[0057]パイプラインレジスタの組は、システムグラフのフィードフォワード切断集合である。システムのフィードフォワード切断集合がそうであるように、パイプラインレジスタの組を除去すると、システムが、切断された２つのサブシステムに分割され、その２つのサブシステムの間に単一方向のデータフローがある。ただし、システム内に複数の入力および／または複数の出力がある場合、入力または出力を異なるサブシステムに分割する切断集合は、パイプラインレジスタの組として適格ではない。これは、そのような切断集合がマルチチャネル設計の生成時にパイプライン化されないと、同期が乱れる可能性があるからである。
【００４０】
[0058]フィードフォワード切断集合は、当業者に知られている様々なアルゴリズムによって自動的に識別されることが可能である。例えば、Ｆｒａｎ ＨａｌｐｅｒｉｎとＵｒｉ Ｚｗｉｃｋが「Ｃｏｍｂｉｎａｔｏｒｉａｌ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｍａｘｉｍｕｍ ｄｉｒｅｃｔｅｄ ｃｕｔ ｐｒｏｂｌｅｍ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １２ｔｈ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｄｉｓｃｒｅｔｅ Ａｌｇｏｒｉｔｈｍｓ、１〜７頁、２００１年）で説明した方法を用いて、フィードフォワード切断集合を決定することが可能である。グラフ理論の文献では、フィードフォワード切断集合は、しばしば、「有向カット（ｄｉｒｅｃｔｅｄ ｃｕｔｓまたはｄｉｃｕｔｓ）」と呼ばれていることに注意されたい。最大数のレジスタを含むフィードフォワード切断集合を見つける場合は、Ｅｒａｎ ＨａｌｐｅｒｉｎとＵｒｉ Ｚｗｉｃｋによる、「最大有向カット」を見つける方法を用いることが可能である。
【００４１】
[0059]図１０は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。図１０の設計は、パイプラインレジスタ１００１〜１００５を含む。フィードフォワード切断集合１０１１は、図１０のシステムを、その間に単一方向のデータフローがある２つのサブシステムに分割する。したがって、レジスタ１００１〜１００５は、非チャネル固有として識別され、したがって、図１０の設計におけるチャネル固有要素は、レジスタ２３１および２３３である。図１０のチャネル固有レジスタ２３１および２３３がレジスタのカスケード接続に置き換えられて、図１１の時間多重化リソース共有設計が生成される。
【００４２】
[0060]図１１は、本発明の一実施形態による、図１０のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。図１１では、パイプラインレジスタ１０１１は不変である。デマルチプレクサ７０３の動作をモジュロ−Ｎカウンタ７０５の状態と同期させるために、レジスタ１２０１が挿入され、これによるカウンタ７０５の出力の１サイクルの遅延が、切断集合１０１１による遅延の影響を相殺する。一般に、Ｍ組のパイプラインレジスタが非チャネル固有要素と識別された場合は、マルチプレクサとデマルチプレクサ（例えば、図１１の７０１と７０３）の動作を同期させるために、モジュロ−Ｎカウンタの集合がｍｏｄ（Ｍ，Ｎ）サイクル遅延される。また、図１０のレジスタ２３１、１００３、および１００５が１組のパイプラインレジスタとして識別される可能性がある点にも注意されたい。この場合は、レジスタ１００１および２３３がシフトレジスタのカスケード接続に置き換えられる。あるいは、パイプラインレジスタとして識別されるレジスタが図１０にない場合は、図１０のすべてのレジスタがレジスタのカスケード接続に置き換えられる。この場合、結果として得られる設計はＮ組のパイプラインレジスタを有し、ｍｏｄ（Ｎ，Ｎ）＝０なので、モジュロ−Ｎカウンタ７０５の出力を遅延させるレジスタは不要である。
【００４３】
[0061]シングルチャネルシステムのチャネル固有レジスタは、マルチチャネルシステムの生成時にＮ個のシフトレジスタのカスケード接続に置き換えられることが可能である。いくつかのＦＰＧＡアーキテクチャ（Ｘｉｌｉｎｘ Ｖｉｒｔｅｘなど）では、シフトレジスタはナチュラルプリミティブである。これにより、ターゲットアーキテクチャがこれらのＦＰＧＡアーキテクチャのいずれかであれば、非常に効率的なメモリの使い方が可能になる。各チャネル固有レジスタは、モジュロ−Ｎカウンタの状態に応じて中間結果をパイプライン移送することが可能な他のメモリ構成（例えば、ＮアイテムのデュアルポートＲＡＭ、ＲＡＭとシフトレジスタの組み合わせ、その他）に置き換えられることも可能であることを理解されたい。
【００４４】
[0062]図１２は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル回路の別の例を示す図である。図１２の設計は、レジスタ１２０１、１２０３、２３１とレジスタ１２０５、２３３とを含むフィードフォワード切断集合１２１１および１２１３を含む。したがって、図１２のすべてのレジスタは非チャネル固有として識別されることが可能であり、図１３の設計の生成時にレジスタのカスケード接続に置き換えられるレジスタはない。
【００４５】
[0063]図１３は、本発明の一実施形態による、図１２のシングルチャネル設計から自動的に生成されるマルチチャネルフィルタの例である。マルチプレクサ１３０１とデマルチプレクサ１３０３との間に２組のパイプラインレジスタがあるので、２サイクルの遅延を用いて、マルチチャネルフィルタの動作を同期させることが可能である。図１３の設計では、２組のパイプラインレジスタによる遅延を補償するために、デマルチプレクサ１３０３の定数を２シフトだけ循環させている。したがって、モジュロ−Ｎカウンタがｉ（ｉ＝０，１，．．．，Ｎ−１）を出力すると、マルチプレクサ１３０１が信号Ｉｉ＋１を入力として選択し、デマルチプレクサ１３０３がＯｍｏｄ（ｉ−１，Ｎ）を出力する。
【００４６】
[0064]上述の例から、時間共有設計において不変のままのパイプラインレジスタの組による遅延を補償するために、別の方法（例えば、遅延要素を挿入する、デマルチプレクサに用いる定数をシフトする、別の選択信号を生成する、またはこれらの組み合わせ）を用いることが可能であることが、当業者には明らかであろう。さらに、一般には、有限ステートマシン（ＦＳＭ）（例えば、モジュロ−Ｎカウンタ）を用いて入力信号の時間多重化ならびに設計におけるリソース共有を制御することも可能である。
【００４７】
[0065]上述の例は、単一入力と単一出力とを有するシングルチャネル設計を用いて示されているが、この説明から、複数入力と複数出力とを有するシングルチャネル設計にも、本発明の様々な実施形態の方法が適用可能であることが当業者には明らかであろう。さらに、Ｍチャネル設計（Ｍ＞１）をシングルチャネル設計として扱うことにより、リソース共有を伴うＮ×Ｍチャネル設計を自動的に生成することが可能である。
【００４８】
[0066]本発明の一実施形態では、複数のチャネルのリソース共有設計の生成時の、従来の方法（例えば、折り畳み変形、その他）による自動変形の前および／または後に、シングルチャネル設計が最適化される。
【００４９】
[0067]図１４は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法のフローチャートである。操作１４０１でシングルチャネル設計を受け取り、操作１４０３で、シングルチャネル設計を自動的に変形して時間多重化マルチチャネル設計を生成する。この変形はシングルチャネル設計に基づいており、シングルチャネルシステムの集合体より論理要素が少ないので、大量の計算を要する、高レベル並列処理の抽出操作が不要である。
【００５０】
[0068]図１５は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の詳細なフローチャートである。操作１５０１で、シングルチャネル回路の設計を受け取る。操作１５０３で、シングルチャネル回路の論理要素へのアクセスを時間多重化するために、Ｎステートの有限ステートマシン（ＦＳＭ）（例えば、モジュロ−Ｎカウンタ）を生成する。操作１５０５で、Ｎチャネル入力を、ＦＳＭの状態に応じて、シングルチャネル回路への入力として多重化する多重化回路を生成する。操作１５０７で、シングルチャネル回路の各チャネル固有要素（例えば、ＲＡＭ、ＲＯＭ、定数、レジスタ、フリップフロップ）を、ＦＳＭの状態に応じて複数のチャネルについてアクセスされる、対応する要素に置き換える。操作１５０９で、ＦＳＭの状態に応じて、シングルチャネル回路の対応する出力からＮチャネル出力を多重分離する多重分離回路を生成する。上述の変形の後に、シングルチャネル設計からマルチチャネル設計が生成される。
【００５１】
[0069]図１６は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の例である。操作１６０１で、シングルチャネル回路の設計を受け取る。操作１６０３で、モジュロ−Ｎカウンタの値がｉであるときにチャネルｉ（ｉ＝０，１，．．．，Ｎ−ｌ）の信号に対する操作が実施されるようにシングルチャネルの論理要素を制御する、そのモジュロ−Ｎカウンタを生成する。操作１６０５で、カウンタの値がｉのときに、チャネルｉの入力をシングルチャネル回路の入力として受け取るＮアイテムのマルチプレクサを生成する。操作１６０７（オプション）で、シングルチャネル回路内の非チャネル固有の順次要素（例えば、フリップフロップ、レジスタ、ＲＯＭ、定数、ＲＡＭ）を識別する。操作１６０９で、シングルチャネル設計の各チャネル固有レジスタ（例えば、フリップフロップ）を、Ｎ個の順次要素（例えば、Ｎ個のシフトレジスタのカスケード接続、ＮアイテムのデュアルポートＲＡＭ、またはＲＡＭとシフトレジスタの組み合わせ）に置き換える。操作１６１１で、サイズＭの各チャネル固有メモリ（例えば、ＲＡＭまたはＲＯＭ）を、サイズＮ×Ｍの新しいメモリに置き換える（新しいメモリのメモリアイテムＮ×ｊ＋ｉは、シングルチャネル回路においてメモリのアイテムｊがアドレス指定されたときに、チャネルｉに対してアドレス指定される）。操作１６１３で、各チャネル固有定数をＮアイテムのＲＯＭメモリに置き換える（メモリアイテムｉは、チャネルｉの定数に対してアドレス指定される）。操作１６１５で、各チャネルに対して、シングルチャネル回路の対応する出力から出力を生成する、Ｎアイテムのデマルチプレクサを生成する。
【００５２】
[0070]本発明の一実施形態では、マルチチャネル回路の自動生成時に導入されたレジスタを用いて回路のクロックレートを高めるために、リタイミングアルゴリズム（例えば、切断集合のリタイミングおよびパイプライン化、クロック周期の最小化のためのリタイミング（「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、９１〜１１８頁）で説明されている方法や、当業者に知られている他の方法など）をさらに用いる。
【００５３】
[0071]回路設計の過程の中間段階（例えば、周辺機器のリタイミング時やアーキテクチャのリタイミング時）に、負遅延を有する負遅延レジスタを用いることが可能である。物理的な負遅延レジスタは存在しないが、負遅延レジスタは、設計の中間的状態におけるタイミング制約を表すものであることを理解されたい。負遅延レジスタは、設計プロセスの早い段階で用いることが可能であり、一般には、最終的なソリューションを達成するための回路設計の過程で除去される。
【００５４】
[0072]本発明の一実施形態では、シングルチャネルシステムは、１つまたは複数の負遅延レジスタで特徴づけられ、負遅延レジスタは、普通のレジスタと同様の様式で変形されることが可能である。
【００５５】
[0073]図１７は、シングルチャネルシステムの例である。説明のために、レジスタ以外の要素の遅延は無視されている。各レジスタ（例えば、１７３１、１７３３、および１７４１）は、１単位の遅延を有する。要素１７１１、１７１３、および１７１５は定数であって、これらは時間的に変化しない。したがって、ライン１７０１の入力をＩ１（ｔ）とすると、ライン１７０３の信号は、Ｉ１（ｔ）×Ｃ３＋Ｉ１（ｔ−２）×Ｃ２＋Ｉ１（ｔ−２）×Ｃ１である。図１７では、レジスタ１７３１が乗算器１７２１の中間結果を格納してＩ１（ｔ−１）×Ｃ１を生成し、レジスタ１７３３が、乗算器１７２３の中間結果を格納してＩ１（ｔ−１）×Ｃ１を生成する。レジスタ１７４１は、加算器１７５１の中間結果を格納してＩ１（ｔ−２）×Ｃ２＋Ｉ１（ｔ−２）×Ｃ１を生成する。
【００５６】
[0074]乗算器１７２５と加算器１７５３との間の経路に正遅延レジスタと負遅延レジスタのペアを挿入することが可能である。挿入すると、図１７の回路が図１８の回路に変形される。図１８では、レジスタ１７４３が負遅延レジスタであり、レジスタ１７３５が普通のレジスタ（正遅延レジスタ）である。図１８では、レジスタ１７３１、１７３３、および１７３５が、１組のパイプラインレジスタである。このパイプラインレジスタの組（１７３１、１７３３、および１７３５）を除去するとシングルチャネル回路の遅延が変わることに注意されたい（この変化が許容されるか望ましい場合もある）。あるいは、図１９の点１７０１の前にレジスタ（図１９には示されず）を挿入して、図１８の回路と同じ遅延を有するシングルチャネル回路にすることが可能であることにも注意されたい。したがって、図１８のシングルチャネル回路を、図１９のシングルチャネル回路として指定することが可能である。図１９で、ライン１７０１の入力がＩ１（ｔ）であるとすると、ライン１７０３の出力は、Ｉ１（ｔ＋１）×Ｃ３＋Ｉ１（ｔ−１）×Ｃ２＋Ｉ１（ｔ−１）×Ｃ１である。したがって、１単位のタイミングシフトを別にすれば、図１９の回路は、本質的に図１７（または図１８）の回路としての機能を実施する。図１９の回路が入力として指定された場合は、マルチチャネル回路を自動的に生成することが可能である。レジスタ１７４１および１７４３はパイプラインレジスタではなく、これらはカスケード接続された複数のレジスタに置き換えられることが可能である。図２０は、図１９を入力して自動的に生成された２チャネル回路の例である。図１９の負遅延レジスタ１７４３は、カスケード接続された負遅延レジスタ１７７１および１７７３に置き換えられ、図１９のレジスタ１７４１は、カスケード接続されたレジスタ１７６１および１７６３に置き換えられる。入力信号を一度に１つずつ共有チャネルに供給するためにマルチプレクサ１７０５が追加され、共有チャネルから出力を一度に１つずつ復元するためにデマルチプレクサ１７０７が追加される。マルチチャネル回路が生成された後、リタイミングアルゴリズム（例えば、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、９１〜１１８頁）で説明されている方法や、当業者に知られている他の方法など）を用いてシステムを最適化することが可能である。例えば、負遅延レジスタを除去するためにパイプラインレジスタの出力を挿入することが可能である。例えば、乗算器１７２１、１７２３、および１７２５の後に２組のパイプラインレジスタを挿入して、図２１の回路を生成することが可能である。前述のとおり、一般に、パイプラインレジスタの組を挿入したり削除したりすると、ライン１７０３の出力の生成のタイミングが変わるので、適切な数のレジスタ（または遅延要素）をライン１７０９に用いて（図１１に示されるように）デマルチプレクサ１７０７の制御信号のタイミングを調整することが可能であり、（図１３に示されるように）制御信号と出力ラインとの間の対応関係を調整することが可能であることに注意されたい。本発明の実施形態によれば、図２１の回路は、図１７の回路から直接生成されることが可能である。図２０の乗算器１７２５と加算器１７５１の後にも２組のパイプラインレジスタを挿入して負遅延レジスタを除去できることに注意されたい。
【００５７】
[0075]さらに、本発明の一実施形態では、パイプラインレジスタを識別する過程で、正遅延レジスタおよび負遅延レジスタの１つまたは複数のペアがシングルチャネルシステムに導入される。例えば、マルチチャネル回路の生成のために図１７のシングルチャネル回路を受け取った後、パイプラインレジスタの識別のために正遅延レジスタと負遅延レジスタのペア（例えば、図１８の１７３５および１７４３）を挿入することが可能である。図１８に示されるように、普通のレジスタ１７３５と負遅延レジスタ１７４３とが挿入されると、パイプラインレジスタの組（１７３１、１７３３、および１７３５）の識別が可能になる。したがって、図１８のレジスタ１７４１および１７４３だけが、対応する、カスケード接続されたレジスタに置き換えられる。同様に、マルチチャネル回路の自動生成の回路を、リタイミングアルゴリズムを用いてさらに最適化することが可能である。
【００５８】
[0076]図２２〜２５は、本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。図２２のシングルチャネルフィルタは、パイプライン化された加算器１８４７（Ａ２）と、パイプライン化された乗算器１８４１〜１８４３（Ｍ１〜Ｍ３）とを有する。パイプライン化された加算器にはレジスタが組み込まれている。例えば、パイプライン化された加算器１８４７はレジスタ１８６５を有し、レジスタ１８６５はパイプライン化された加算器の物理的な一部であって、分離不可能である。同様に、パイプライン化された乗算器にもレジスタが組み込まれている（例えば、パイプライン化された乗算器１８４１、１８４２、および１８４３には、レジスタ１８３１、１８３３、および１８３５がそれぞれ組み込まれている）。
【００５９】
[0077]加算器１８５１を実装するために、パイプライン化された加算器が用いられるとする。加算器１８５１にレジスタを与えるために、負遅延レジスタを用いないのであれば、（例えば、加算器１８５３の両方の入力ラインに）普通のレジスタの組を追加することが可能である。そのような方法では、シングルチャネルシステムの遅延が増える可能性がある。別の方法として、図２３は、加算器１８５１と１８５３との間に正遅延レジスタおよび負遅延レジスタ（１８６１および１８６３）を追加する例を示している。したがって、加算器１８５１とレジスタ１８６１とを、パイプライン化された加算器１８４５（Ａ１）として実装することが可能である。リタイミングを実行してもシングルチャネルシステムの負遅延レジスタを除去することができないことに注意されたい。
【００６０】
[0078]本発明の実施形態によれば、マルチチャネル回路を自動的に生成することが可能である。例えば、図２３は、２チャネル回路について、本発明の一実施形態に従って生成されたマルチチャネル回路の時間共有部分を示している。２チャネル回路の、入力を多重化する部分と、出力を多重分離する部分とは、図２４に示されていないので注意されたい。レジスタ１８３１、１８３３、および１８３５は、図２３においてチャネル固有であり、レジスタ１８３２、１８３４、および１８３６は、図２４においてマルチチャネル回路のために挿入される。同様に、図２３のレジスタ１８６１および１８６３は、図２４の、カスケード接続されたレジスタの組（１８６１、１８６２、および１８６３と１８６４）に置き換えられる。
【００６１】
[0079]本発明の一実施形態に従って生成される２チャネル回路では、パイプライン化された演算器のそれぞれに対して追加レジスタが生成される。そして、負遅延レジスタを除去するためにリタイミング操作が行われる。例えば、リタイミング操作では、図２４のレジスタ１８３２および１８３４を加算器１８５１と１８５３との間の経路に移動して、加算器１８５１と１８５３との間の経路に、負レジスタ（１８６３および１８６４）を相殺するのに十分な、普通のレジスタがあるようにすることが可能である。そのようにして２チャネル回路が得られる例を図２５に示す。図２５では、乗算器２８２１、１８２３、および１８２５と、加算器１８５１および１８５３とを、対応する、パイプライン化された演算器（パイプライン化された乗算器１８４１、１８４２、および１８４３と、パイプライン化された加算器１８４５および１８４７）として実装することが可能である。ただし、負遅延レジスタはすべて、リタイミング後に除去される。
【００６２】
[0080]上述の例では、パイプライン化された加算器と、パイプライン化された乗算器とを示した。しかしながら、次の説明から、他のパイプライン化された論理要素やパイプライン化されたＩＰブロックも同様に扱うことが可能であることを理解されよう。
【００６３】
[0081]本発明の一実施形態では、パイプラインレジスタの組が識別されず、すべてのレジスタがチャネル固有であると見なされる。例えば、シングルチャネルシステムをＮチャネルシステムに自動的に変形する方法は、以下の操作を含む。
【００６４】
[0082]１．モジュロ−ＮカウンタをＮステートの有限ステートマシン（ＦＳＭ）として生成する。ＦＳＭのステート変数はｃｎｔで表される。システムのｍ番目のチャネル（（０≦ｍ≦Ｎ−１）は、ＦＳＭがｍ番目の状態のとき（例えば、ｃｎｔ＝ｍであるとき）に有効にアクティブ化される。
【００６５】
[0083]２．各レジスタを、Ｎ個のシフトレジスタのカスケード接続に置き換える（あるいは、Ｎが大きい場合は、各レジスタを、ＮアイテムのデュアルポートＲＡＭか、ＲＡＭとシフトレジスタの組み合わせに置き換えることが可能である）。
【００６６】
[0084]３．サイズＭの各ＲＡＭメモリを、サイズＮ×ＭのＲＡＭメモリに置き換える。アドレス生成回路は、シングルチャネル設計のメモリアイテムＡがアドレスＮ×Ａ＋ｃｎｔのアイテムに置き換えられるように、メモリアイテムをアドレス指定するよう修正または追加される。新しいメモリからの出力がＦＳＭの状態と同期するようにメモリアイテムを論理的にパイプライン化するために、他のアドレス変換方式を用いることも可能であることを理解されたい。一般に、変換されたアドレスは、元のアドレス、ＦＳＭの状態、およびアクティブなチャネルの番号の関数である。
【００６７】
[0085]４．チャネル固有のＲＯＭがある場合（例えば、ＲＯＭの内容がチャネルごとに異なる場合）は、ＲＯＭアイテムＮ×Ａ＋ｍがｍ番目のチャネルのＲＯＭアイテムＡの内容を保持するように、ＲＡＭの場合と同様の変形を適用する。ＲＯＭがチャネル固有でない場合、変形は不要である。
【００６８】
[0086]５．チャネル固有の定数がある場合（例えば、チャネルごとに定数の値が異なる場合）は、その定数を、ＮアイテムのＲＯＭに置き換える。ＲＯＭのアドレスラインはｃｎｔで駆動される（ＲＯＭアクセスに１クロックの遅延がある場合はｃｎｔ−１で駆動される）。定数がチャネル固有でない場合、変形は不要である。
【００６９】
[0087]異なるチャネルの入力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の入力ポートを有する場合は、これらの入力を、ｃｎｔで駆動される選択ラインを有する、Ｎアイテムのマルチプレクサで多重化する。ｃｎｔは、入力を駆動するクロックよりＮ倍高速である。同様に、異なるチャネルの出力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の出力ポートを有する場合は、これらの出力を、ｃｎｔで駆動される選択ラインを有する、Ｎアイテムのデコーダで多重分離する。この出力は、Ｎ倍低速なクロックでラッチされることが可能である。シングルチャネル設計の他のコンポーネントは、時間多重化されている間中、現状のまま、共有リソースとして保持される。
【００７０】
[0088]本発明の別の実施形態では、レジスタの生成を避けるためにパイプラインレジスタの組が識別される。例えば、シングルチャネルシステムをＮチャネルシステムに自動的に変形する方法は、以下の操作を含む。
【００７１】
[0089]１．可能な限り多くの、かつ幅広のレジスタをカバーするために、システム内のパイプラインレジスタを識別する。パイプラインレジスタの組が複数存在してもよいが、それらの組は相互に排他的でなければならない。どのパイプラインレジスタの組にも分類されないレジスタはすべて状態レジスタである。パイプラインレジスタは非チャネル固有であり、状態レジスタはチャネル固有である。Ｐ個の個別のパイプラインレジスタの組が存在する場合、システムは、まとまりのないＰ＋１個のサブシステムに分割されており、サブシステムが単体でリンクされたリストが形成されている。このリストでは、各フィードフォワード切断集合が、リンクを、データフローの方向を示すリンク方向とともに定義している。リンクされたリストでの順番がｉ（０≦ｉ≦Ｐ）であるサブシステムをＳｉで表す。
【００７２】
[0090]２．少なくとも１つのモジュロ−ＮカウンタからＰ＋１個のＮステートの有限ステートマシン（ＦＳＭ）を生成する。ｉ番目のＦＳＭ（０≦ｉ≦Ｐ）の状態変数をｃｎｔｉで表す。ｉ番目のＦＳＭがｍ番目の状態にある場合（例えば、ｃｎｔｉ＝ｍの場合）、サブシステムＳｉのハードウェアは、ｍ番目のチャネル（０≦ｍ≦Ｎ−１）のデータを処理する。［０，Ｐ］における∀ｉ，ｊに対してｍｏｄ（（ｃｎｔｉ−ｃｎｔｊ），Ｎ）＝ｍｏｄ（（ｊ−ｉ），Ｎ）であれば、サブシステム間で適正な同期が維持される。この関係は、ｃｎｔｉがｃｎｔｉ−１を１クロック遅延させたものである場合に成り立つ（ｉ＝１，２，．．．，Ｎ−１）。したがって、ｃｎｔｉは、レジスタを用いてｃｎｔｉ−１から導出されることが可能であり、ＦＳＭは、１つのモジュロ−Ｎカウンタとレジスタのカスケード接続とを用いて実装されることが可能である。
【００７３】
[0091]３．各状態レジスタを、Ｎ個のシフトレジスタのカスケード接続に置き換える（あるいは、Ｎが大きい場合は、各状態レジスタを、ＮアイテムのデュアルポートＲＡＭか、ＲＡＭとシフトレジスタの組み合わせに置き換えることが可能である）。
【００７４】
[0092]４．サイズＭの各ＲＡＭメモリを、サイズＮ＿ＭのＲＡＭメモリに置き換える。サブシステムＳｉ内のＲＡＭに関しては、シングルチャネル設計のメモリアイテムＡが、アドレスＮ＿Ａ＋ｃｎｔｉにあるアイテムに置き換えられるようにメモリアイテムをアドレス指定するよう、アドレス生成回路が修正または追加される。新しいメモリからの出力がｉ番目のＦＳＭの状態と同期するようにメモリアイテムを論理的にパイプライン化するために、他のアドレス変換方式を用いることも可能であることを理解されたい。一般に、変換されたアドレスは、元のアドレス、ｉ番目のＦＳＭの状態、およびアクティブなチャネルの番号の関数である。
【００７５】
[0093]５．チャネル固有のＲＯＭがある場合（例えば、ＲＯＭの内容がチャネルごとに異なる場合）は、ＲＯＭアイテムＮ＿Ａ＋ｍがｍ番目のチャネルのＲＯＭアイテムＡの内容を保持するように、ＲＡＭの場合と同様の変形を適用する。ＲＯＭがチャネル固有でない場合、変形は不要である。
【００７６】
[0094]６．サブシステムＳｉ内にチャネル固有の定数がある場合（例えば、チャネルごとに定数の値が異なる場合）は、その定数を、ＮアイテムのＲＯＭに置き換える。ＲＯＭのアドレスラインはｃｎｔｉで駆動される（ＲＯＭアクセスに１クロックの遅延がある場合はｃｎｔｉ−１で駆動される）。定数がチャネル固有でない場合、変形は不要である。
【００７７】
[0095]異なるチャネルの入力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の入力ポートを有する場合は、これらの入力を、ｃｎｔ０で駆動される選択ラインを有する、Ｎアイテムのマルチプレクサで多重化する。ｃｎｔ０は、入力を駆動するクロックよりＮ倍高速である。同様に、異なるチャネルの出力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の出力ポートを有する場合は、これらの出力を、ｃｎｔｐで駆動される選択ラインを有する、Ｎアイテムのデコーダで多重分離する。この出力は、Ｎ倍低速なクロックでラッチされることが可能である。シングルチャネル設計の他のコンポーネントは、時間多重化されている間中、現状のまま、共有リソースとして保持される。
【００７８】
[0096]Ｐ＋１個のＮステートの有限ステートマシンを用いればＰ＋１個のサブシステムのタイミングを個別に制御することが可能であるが、別の方法として、単一のＮステートのＦＳＭを用いてすべてのサブシステムの動作を制御することが可能である。この場合、所与のチャネルに対して、ＦＳＭの状態が別の値に達すると、別のサブシステムが処理を行う。例えば、ＦＳＭが状態ｃｎｔ＝ｍｏｄ（ｍ−１，Ｎ）の場合には、サブシステムＳｉのハードウェアがｍ番目のチャネル（０≦ｍ≦Ｎ−１）のデータを処理する。
【００７９】
[0097]パイプラインレジスタの組は、タイミング制限が許せば、識別および除去されることが可能である。例えば、図１０のパイプラインレジスタの組１０１１は、図２の設計を生成するために除去されることが可能であり、図１１のパイプラインレジスタの組１０１１は、図７の設計を生成するために自動的に除去されることが可能である。同様に、パイプラインレジスタが自動的に設計に追加されることも可能である。一般には、パイプラインレジスタを追加したり削除したりすると、回路の入力から出力までの遅延が変わることに注意されたい。ただし、そのような変化は許容されることが多い。
【００８０】
[0098]本発明の一実施形態では、実行時に構成可能な深さを有するシフトレジスタを用い、実行時に構成可能な法を有するモジュロ−Ｎカウンタを用いると、動作を中断させることなく、折り畳みレートＮを実行時に変更することが可能である。アクティブチャネルの数が動的なパラメータである用途では、折り畳みレートをアクティブチャネルの数に適応させて、状況が許すときに、電力消費を抑えるためにクロックレートを下げることが可能である。
【００８１】
[0099]したがって、本発明の少なくとも１つの実施形態は、入力されたシングルチャネルシステムの設計からマルチチャネルシステムの設計を自動的に生成する。シングルチャネルシステムの設計は、論理（計算）ユニットの時間多重化リソース共有を伴うＮチャネルシステムに自動的に変形される。この変形はシンプルで非常に高速であり、得られる設計のハードウェアは非常に効率的である。
【００８２】
[00100]本発明の様々な実施形態の方法によりシングルチャネル設計から時間多重化マルチチャネル設計が生成されるので、より少ない数の論理要素に対して最適化および合成の操作を高速で実施することが可能である。制御論理の使い方については、最小限にすることが可能である。一部のＦＰＧＡアーキテクチャでは、合成されたシステムのメモリの使い方を非常に効率的にすることが可能である。さらに、本発明の様々な方法が、高次のパイプラインと大幅な高速化を想定している。
【００８３】
[00101]本明細書ではここまで、本発明の特定の例示的実施形態を参照しながら本発明について説明してきた。添付の特許請求項で示されている、本発明の広い趣旨および範囲を逸脱することなく、様々な修正を本発明に施しうることは明らかであろう。したがって、本明細書および添付図面は、制限の意味ではなく例示の意味で解釈されるべきである。
【図面の簡単な説明】
【００８４】
【図１】本発明に使用可能なデータ処理システムのブロック図の例である。
【図２】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能なシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。
【図３】図２の例の様々な場所での信号波形を示す図である。
【図４】図２のシングルチャネルフィルタの集合体に対応する２チャネルフィルタの例を示す図である。
【図５】本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成される２チャネルフィルタの例である。
【図６】図５の例の様々な場所での信号波形を示す図である。
【図７】本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図８】本発明の一実施形態による、マルチチャネルフィルタの出力を多重分離する出力デコーダおよびラッチ回路の例を示す図である。
【図９】本発明の代替実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの別の例である。
【図１０】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。
【図１１】本発明の一実施形態による、図１０のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図１２】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル回路の別の例を示す図である。
【図１３】本発明の一実施形態による、図１２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図１４】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法のフローチャートである。
【図１５】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の詳細なフローチャートである。
【図１６】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の例である。
【図１７】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図１８】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図１９】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２０】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２１】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２２】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２３】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２４】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２５】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【発明の分野】
【０００１】
[0001]本発明はデジタル回路に関し、より詳細には、マルチチャネルハードウェアの自動合成に関する。
【関連技術の説明】
【０００２】
[0002]（例えば、超ＬＳＩ（ＶＬＳＩ）技術の規模の）デジタル回路の設計では、設計者は、コンピュータ支援手法を用いることが多い。複雑なデジタル回路の設計およびシミュレーションを支援する目的でデジタル回路を記述するために、ＨＤＬ（ハードウェア記述言語）などの標準言語が開発されてきた。いくつかのハードウェア記述言語（ＶＨＤＬやＶｅｒｉｌｏｇなど）は、業界標準として進化している。ＶＨＤＬおよびＶｅｒｉｌｏｇは、ゲートレベル、レジスタ転送レベル（ＲＴＬ）、または抽象データ型を用いた動作レベルでのハードウェアモデルの記述を可能にする汎用ハードウェア記述言語である。デバイス技術が進歩し続けるとともに、ＨＤＬをより新しいデバイスや設計スタイルに使えるように適応させるべく、様々な製品設計ツールが開発されている。
【０００３】
[0003]ＨＤＬコードによる集積回路の設計では、最初にコードが作成され、そのコードがＨＤＬコンパイラによってコンパイルされる。ＨＤＬソースコードは、特定のレベルで回路要素を記述したものであり、コンパイラは、コンパイル結果としてＲＴＬネットリストを生成する。ＲＴＬネットリストは、特定ベンダの集積回路（ＦＰＧＡ（フィールドプログラマブルゲートアレイ）やＡＳＩＣ（特定用途向け集積回路）など）のテクノロジ／アーキテクチャに依存しないという意味で、一般にテクノロジ非依存のネットリストである。ＲＴＬネットリストは、（動作表現と異なり）回路要素の回路図表現に対応する。この、テクノロジ非依存のＲＴＬネットリストをテクノロジ固有のネットリストに変換するために、あるマッピング操作が行われる。この操作により、そのベンダのテクノロジ／アーキテクチャで回路を作成することが可能である。ＦＰＧＡベンダらがそれぞれの集積回路内に論理回路を実装するために様々なテクノロジ／アーキテクチャを利用していることはよく知られている。したがって、テクノロジ非依存のＲＴＬネットリストにマッピングが施されて作成されるネットリストは、個々のベンダのテクノロジ／アーキテクチャに固有のものである。
【０００４】
[0004]回路の設計では、特定の設計目標を最適化するために、よく変形を行う。例えば、ある回路で使用される面積を減らすために変形が行われる場合がある。集積回路で使用されるシリコン面積を減らすための体系化されたアプローチの１つが、折り畳み変形（Ｆｏｌｄｉｎｇ Ｔｒａｎｓｆｏｒｍａｔｉｏｎ）である。単一の機能単位に対して複数のアルゴリズム操作を実行することにより、実装時の機能単位数を減らすことが可能である。折り畳み変形の詳細については、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年）に説明がある。
【０００５】
[0005]デジタル回路の配線では、時間多重化リソース共有が行われてきた。例えば、「Ｐａｒａｌｌｅｌ Ｏｐｅｒａｔｉｏｎｓ ｉｎ ｔｈｅ Ｃｏｎｔｒｏｌ Ｄａｔａ ６６００」（ＡＦＩＰＳ Ｐｒｏｃｅｅｄｉｎｇｓ ＦＪＣＣ、Ｐａｒｔ ２、Ｖｏｌ．２６、１９６４年、３３〜４０頁）でＪ． Ｅ． Ｔｈｏｒｎｔｏｎによって説明されている、ＣＤＣ ６６００コンピュータのＰｅｒｉｐｈｅｒａｌ ａｎｄ Ｃｏｎｔｒｏｌ Ｐｒｏｃｅｓｓｏｒｓ（ＰＡＣＰｓ）では、ラウンドロビン様式で共通リソースにアクセスすることによって実行ハードウェアを共有する。また、マルチチャネルフィルタ用リソース共有に関する別の例を、「ＦＰＧＡ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ａ Ｓｅｒｉａｌ Ｏｒｇａｎｉｚｅｄ ＤＡ Ｍｕｌｔｉｃｈａｎｎｅｌ ＦＩＲ Ｆｉｌｔｅｒ」（Ｊｈｏｎ Ｊ．Ｌｅｏｎ Ｆｒａｎｃｏ、Ｍｉｇｕｅｌ Ａ．Ｍｅｌｇａｒｅｊｏ、Ｔｅｎｔｈ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙｓ、Ｍｏｎｔｅｒｅｙ、Ｃａｌｉｆｏｒｎｉａ、２００２年２月２４〜２６日）に見ることができる。
【０００６】
[0006]従来の折り畳みアルゴリズムは、所与の設計から、時間多重化リソース共有を伴う設計を自動的に生成することが可能である。従来の折り畳みアルゴリズムは、単一機能単位への時間多重化が可能な複数のアルゴリズム操作を識別して、機能単位（例えば、加算器、マルチプレクサ）の数を減らすことが可能である。ただし、デジタル信号処理（ＤＳＰ）設計の場合、従来の折り畳みアルゴリズムは、並列処理および依存性の抽出と、計算スケジュールの最適化とに多大な時間がかかる。ハードウェア合成の複雑さは、計算に関与する論理単位の数に対して比例を超える変化で大きくなる。したがって、設計規模が大きくなるほど、回路の最適化および変形が困難になる。
【発明の概要】
【０００７】
[0007]本明細書では、シングルチャネル回路から時間多重化マルチチャネル回路を自動的に生成する方法および装置について記載する。
【０００８】
[0008]本発明の少なくとも１つの実施形態は、シングルチャネル回路の設計からマルチチャネル回路の時間多重化設計を自動的に生成することによって時間多重化リソース共有のためのマルチチャネルハードウェアを自動的かつ効率的に合成する。シングルチャネル設計のチャネル固有の要素（例えば、レジスタやメモリ）は、複数のチャネルの信号処理をパイプライン化するための、Ｎ倍の容量を有する、対応する要素に置き換えられる。
【０００９】
[0009]本発明の一態様では、デジタル回路を設計する方法は、シングルチャネル回路である第１の設計を受け取ることと、その、シングルチャネル回路である第１の設計を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成することとを含む。一例では、マルチチャネル回路の自動生成後に、（例えば、クロック周波数を高めるために）時間多重化マルチチャネル回路に対してリタイミングが実施される。一例では、（例えば、マルチチャネル回路の遅延を調整するために）時間多重化マルチチャネル回路のパイプラインレジスタの組が識別され、除去される。一例では、時間多重化マルチチャネル回路にパイプラインレジスタの組が挿入される。一例では、複数のチャネルによる第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）が生成され、複数のチャネル用の複数の入力を第１の設計の入力ラインに時間多重化するために多重化回路が生成され、第１の設計の出力ラインからの信号を複数のチャネル用の複数の出力に時間多重分離するための多重分離回路が生成される。一例では、第１の設計における要素（例えば、定数、ランダムアクセスメモリ（ＲＡＭ）要素、読み出し専用メモリ（ＲＯＭ）要素、レジスタ、フリップフロップ、または負遅延レジスタ）が、対応する複数の、またはより大きな要素に置き換えられ、その要素のそれぞれは、ＦＳＭの状態に応じて複数のチャネルのうちの１つのチャネルに対してアクセスされる。一例では、チャネル固有でない順次要素が識別された後、第１の設計における他の順次要素がチャネル固有と識別され、チャネル固有の要素だけが、対応する複数の要素に置き換えられる。チャネル固有でない順次要素には、（例えば、順次要素のフィードフォワード切断集合の数を調べることによって、チャネル固有でない順次要素として識別された）パイプラインレジスタの組が含まれる。一例では、チャネル固有の順次要素が、複数の移動順次要素のカスケード接続に置き換えられ、別の例では、チャネル固有の順次要素が、ＦＳＭの状態に応じてアドレス指定される、複数のメモリ要素（または、容量がより大きなメモリ要素）に置き換えられる。
【００１０】
[0010]一例では、第１の設計における順次要素（例えば、フリップフロップ、レジスタ、メモリ要素、定数、および負遅延レジスタ）が、第２の設計を生成するために、対応する要素（例えば、レジスタのカスケード接続、デュアルポートＲＡＭ、またはＲＡＭとシフトレジスタの組み合わせ）に置き換えられる。対応する要素は、複数のチャネルからの信号を処理するタイミングに応じて、第２の設計において順次アクセスされる。一例では、対応する要素が、移動要素のカスケード接続であり、別の例では、対応する要素が、順次アドレス指定される（例えば、Ｎ個のメモリ要素からなるメモリが、Ｍチャネル回路に対応するようにＮ×Ｍ個のメモリ要素を有するメモリに置き換えられる）。
【００１１】
[0011]本発明の一態様では、デジタル回路を設計する方法が、シングルチャネル回路である第１の設計を受け取ることと、第１の設計のシングルチャネル回路の集合体と、そのシングルチャネル回路の集合体における並列処理を指示する情報とを生成することと、その情報を用いて、そのシングルチャネル回路の集合体に折り畳み変形を適用して、時間多重化マルチチャネル回路である第２の設計を生成することとを含む。例えば、この情報は、折り畳みの集合の情報を含み、この、折り畳みセットの情報は、折り畳みアルゴリズムを誘導して折り畳み変形を実施するために用いられる。シングルチャネル回路である第１の設計に負遅延レジスタを含めることが可能であり、変形後にリタイミング操作を実施することが可能である。
【００１２】
[0012]本発明は、方法と方法を実施する装置とを含み、装置は、方法を実施するデータ処理システムと、データ処理システムで実行されたときに方法をデータ処理システムに実施させるコンピュータ可読媒体とを含む。
【００１３】
[0013]本発明の他の特徴は、添付図面と、この後の詳細説明から明らかになるであろう。
【００１４】
[0014]添付図面の図中では、本発明が限定ではなく例として示されており、添付図面において類似した参照符号は同様の要素を指す。
【詳細な説明】
【００１５】
[0033]以下の説明および図面は、本発明の例示であって、本発明を限定するものと解釈されてはならない。本発明が完全に理解されるように、数多くの具体的な詳細について説明する。ただし、場合によっては、本発明の説明が不明瞭にならないように、よく知られている事柄や一般的な事柄については詳しく説明しない。本開示におけるある実施形態または一実施形態への参照は、必ずしも同じ実施形態への参照とは限らず、そのような参照は、少なくとも１つの実施形態への参照を意味する。
【００１６】
[0034]本発明の少なくとも１つの実施形態は、シングルチャネル回路の設計からマルチチャネル回路の時間多重化設計を自動的に生成することによって時間多重化リソース共有のためのマルチチャネルハードウェアを自動的かつ効率的に合成しようとするものである。
【００１７】
[0035]ハードウェア合成の複雑さは、設計に関与する論理単位の数に対して比例を超える変化で大きくなる。マルチチャネル回路は、一般に、独立した同一のシングルチャネルを複数有する。Ｎチャネル回路は、一般に、ハードウェア合成時に回路を最適化する際に、対応するシングルチャネル回路のＮ倍を超える数の論理（計算）単位を必要とする。使用される機能単位の数を減らすために、従来の折り畳み変形をマルチチャネル回路に適用して時間多重化回路を生成する場合、従来の折り畳みアルゴリズムでは、並列処理および依存性の抽出と、計算スケジュールの最適化とに多大な時間がかかる。したがって、時間多重化リソース共有のためのハードウェア合成の最適化は、一般に計算量が非常に多い（特に設計規模が大きい場合）。
【００１８】
[0036]本発明の一実施形態によれば、複数のチャネルの時間多重化リソース共有のための合成の最適化は、シングルチャネルの設計に基づく。並列処理および依存性を抽出する計算は不要であり、従来の折り畳み変形の大量の計算を行うことなく、シングルチャネルの設計から、時間多重化リソース共有を伴う設計を生成することが可能である。一例では、シングルチャネル設計のチャネル固有の要素（例えば、レジスタやメモリ）を、複数のチャネルの信号処理をパイプライン化するためにＮ倍を超える容量の、それらに対応する要素に置き換えることによって、シングルチャネル設計が時間多重化Ｎチャネル設計に変形される。後でさらに例を挙げて詳しく説明する。
【００１９】
[0037]本発明の方法の多くは、従来の汎用コンピュータシステムなどのデジタル処理システムで実施可能である。１つの機能だけを実行するために設計またはプログラムされた特殊用途コンピュータも使用可能である。
【００２０】
[0038]図１は、本発明に使用可能な、一般的なコンピュータシステムの一例である。図１は、コンピュータシステムの各種コンポーネントを示しているが、それらのコンポーネントの相互接続の特定のアーキテクチャまたは様式を表すことを意図したものではないことに注意されたい。そのような細部は、本発明と特に関係するものではないからである。また、これよりコンポーネントが少ないか、あるいは多いネットワークコンピュータや他のデータ処理システムも本発明に使用可能であることも理解されよう。図１のコンピュータシステムは、例えば、Ｓｕｎワークステーション、またはＷｉｎｄｏｗｓオペレーティングシステムが動作するパーソナルコンピュータ（ＰＣ）、またはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータであってよい。
【００２１】
[0039]図１に示すように、データ処理システムの形をとるコンピュータシステム１０１は、マイクロプロセッサ１０３、ＲＯＭ １０７、揮発性ＲＡＭ １０５、および不揮発性メモリ１０６に結合されたバス１０２を含む。マイクロプロセッサ１０３は、Ｍｏｔｏｒｏｌａ，Ｉｎｃ．製またはＩＢＭ製のＧ３またはＧ４マイクロプロセッサであってよく、図１の例に示すように、キャッシュメモリ１０４に結合される。バス１０２は、これらの様々なコンポーネントを相互接続し、さらに、コンポーネント１０３、１０７、１０５、および１０６を、ディスプレイコントローラおよびディスプレイ機器１０８、ならびにマウス、キーボード、モデム、ネットワークインターフェース、プリンタ、スキャナ、ビデオカメラ、および他の、当業者にはよく知られている機器などが挙げられる入出力（Ｉ／Ｏ）機器などの周辺機器と相互接続する。通常、入出力機器１１０は、入出力コントローラ１０９を介してシステムに結合される。揮発性ＲＡＭ １０５は、一般に、メモリ内のデータをリフレッシュまたは保持するために継続的な給電が必要なダイナミックＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、一般に、システムへの給電がなくなってもデータを保持する磁気ハードドライブ、光磁気ドライブ、光ドライブ、ＤＶＤ ＲＡＭ、または他のタイプ、のメモリシステムである。一般には不揮発性メモリもランダムアクセスメモリであるが、ランダムアクセスメモリでなくてもかまわない。図１では、不揮発性メモリは、データ処理システムのそれ以外のコンポーネントと直接結合されているローカルデバイスであるが、本発明は、モデムやイーサネットインターフェースなどのネットワークインターフェースでデータ処理システムと結合されているネットワークストレージ機器のような、システムから離れている不揮発性メモリも利用可能であることが理解されよう。バス１０２は、当業者にはよく知られている様々なブリッジ、コントローラ、および／またはアダプタで相互接続された１つまたは複数のバスを含むことが可能である。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ（ユニバーサルシリアルバス）周辺機器を制御するＵＳＢアダプタ、および／またはＩＥＥＥ−１３９４周辺機器を制御するＩＥＥＥ−１３９４バスアダプタを含む。
【００２２】
[0040]本発明の態様が少なくとも部分的にソフトウェアで実施可能であることは、以下の記述から明らかであろう。すなわち、本手法は、コンピュータシステムまたは他のデータ処理システムにおいて、そのプロセッサ（マイクロプロセッサなど）が、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモートストレージ機器に格納されている命令のシーケンスを実行するのに応答する形で実施されることが可能である。様々な実施形態において、本発明を実装するために、ハードワイヤード回路をソフトウェア命令を組み合わせて用いることが可能である。したがって、本手法は、ハードウェア回路とソフトウェアの特定の組み合わせに限定されるものではなく、また、データ処理システムで実行される命令の特定のソースに限定されるものでもない。さらに、以下の記述では、説明を単純にするために、様々な機能や操作を、ソフトウェアコードによって実行または起動されるものとして説明する。しかしながら、当業者であれば、そのような表現が、プロセッサ（マイクロプロセッサ１０３など）によるコードの実行の結果として機能が実施されることを意味することを理解されよう。
【００２３】
[0041]データ処理システムによって実行されたときに本発明の各種方法をシステムに実行させるソフトウェアおよびデータを格納するために、マシン可読媒体を用いることが可能である。この実行可能ソフトウェアおよびデータは、例えば、図１に示したＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、および／またはキャッシュ１０４など、様々な場所に格納することが可能である。このソフトウェアおよび／またはデータの一部を、これらのストレージ機器の任意のいずれかに格納することが可能である。
【００２４】
[0042]したがって、マシン可読媒体には、マシン（例えば、コンピュータ、ネットワーク機器、携帯情報端末、製造ツール、１つまたは複数のプロセッサの集合を有する任意の機器など）からのアクセスが可能な形で情報を提供する（すなわち、格納および／または送信する）任意のメカニズムが含まれる。例えば、マシン可読媒体として、記録可能または記録不可能媒体（例えば、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイスなど）、ならびに電気、光、音、または他の形で伝搬する信号（例えば、搬送波、赤外線信号、デジタル信号など）などがある。
【００２５】
[0043]図２は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能なシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。シングルチャネル回路２００は、ライン２０１で入力を受け取り、ライン２０３で出力を生成する。このシングルチャネル設計は、定数２１１、２１３、および２１５と、乗算器２２１、２２３、および２２５と、加算器２３５および２３７と、レジスタ（フリップフロップ）２３１および２３３とを含む。乗算器２２１、２２３、および２２５がライン２０１の入力に定数２１１、２１３、および２１５を乗じ、それらの結果を加算器２３５および２３７が合計して、ライン２０３に出力を生成する。ライン２０５のクロック信号Ｃｓが、シングルチャネル回路内の処理のパイプライン化と同期とを制御する。
【００２６】
[0044]図３は、図２の例の様々な場所での信号波形を示す図である。時刻ｔ０（３０１）に、入力信号Ｉ１がライン２０１に到着する。時刻ｔ１（３０３）に、レジスタ２３１が乗算器２２１の結果を出力してラインＡ ２０７に信号ＳＡ ３１３を生成する。時刻ｔ２（３０５）に、レジスタ２３３が加算器２３５の結果を出力してラインＢ ２０９に信号ＳＢ ３１５を生成する。これは、信号ＳＡ ３１３と乗算器２２３の出力との和である。時刻ｔ３に、加算器２３７が信号ＳＢ ３１５と乗算器２２５の出力とを合計して出力ライン２０３に信号Ｏ１ ３１７を生成する。
【００２７】
[0045]図４は、図２のシングルチャネルフィルタの集合体に対応する２チャネルフィルタの例を示す図である。例えば、回路４０１および４０３は、図２の回路２００と同じ要素および構成を有する。ハードウェアシステムの自動合成についての従来のソリューションでは、マルチチャネルシステムを特別に扱うことはしない。従来の方法では、マルチチャネル設計を、シングルチャネルシステムの大きな集合体として扱う。一般に、従来の方法は、設計に内在する高レベル並列処理を何ら示すことなく、図４に示すような２チャネルフィルタを提示する。したがって、ハードウェア合成ソフトウェアプログラムは、大量の計算を要する、並列処理および依存性を抽出するタスクを実行する。時間多重化リソース共有を伴う設計を生成するためには、折り畳み変形を適用することが可能である。したがって、従来の方法は、大量の計算を必要とする。さらに、マルチチャネルシステムがシングルチャネルシステムの集合体として解釈される場合は、内在する高レベル並列処理が見逃される可能性があり、結果として、折り畳み変形が適用される際にさらに多くの計算リソースが費やされること、および／または所与の設計が十分に最適化されないことが起こる。
【００２８】
[0046]本発明の一実施形態では、シングルチャネルシステムの集合体の中の並列処理に関連する情報は、そのシングルチャネル設計から自動的に生成されるが、この情報が生成されるのは、シングルチャネルシステムの集合体が時間多重化回路に自動的に変形される際に折り畳み変形が適用されるように汎用折り畳みアルゴリズムを誘導するためでもある。例えば、一般的な折り畳みアルゴリズム（例えば、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ−Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、１４９〜１８７頁）で説明されている折り畳みアルゴリズムなど）では、折り畳みの集合を識別することは、時間のかかる操作である。折り畳みの集合は、時間多重化によって同一機能単位で実行されることになる操作の集合である。シングルチャネル設計からシングルチャネルシステムの集合体が自動的に生成される場合は、大量の計算を行うことなく、折り畳みの集合を生成することが可能である。そのように識別された折り畳みの集合は、一般的な折り畳みアルゴリズムを、シングルチャネルシステムの集合体を変形することに誘導するために用いられることが可能である（例えば、そのような情報を用いて操作を効率化するように従来の折り畳みアルゴリズムを修正することが可能である）。
【００２９】
[0047]本発明の少なくとも１つの実施形態では、シングルチャネルシステムの大きな集合体に折り畳み変形を適用する代わりに、シングルチャネル設計に自動変形を適用して、時間多重化リソース共有を可能にする設計を生成することによって、マルチチャネル回路内の並列処理を漏れなく探り出す。
【００３０】
[0048]本発明の一実施形態は、並列処理および依存性の抽出、計算スケジュールの最適化、その他に時間を費やすことを避けるために、最初からマルチチャネル動作を想定する。この実施形態は、システムのシングルチャネルバージョンを入力と見なし、シンプルなマッピングを適用して、マルチチャネルシステムに内在する高レベル並列処理を非常に効率的に利用する。結果として得られるマルチチャネル設計の、独立した各スレッド内のデータフローが同一であるので、結果として回路の制御は最小限である。
【００３１】
[0049]図５は、本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成される２チャネルフィルタの例である。機能単位（例えば、乗算器や加算器）は、チャネル固有ではない。定数Ｃ１、Ｃ２、およびＣ３（２１１、２１３、および２１５）はチャネル固有ではないので、これらも修正なしで共有されることが可能である。レジスタは、このケースではチャネル固有である。したがって、シングルチャネル設計２００のレジスタ２３１と２３３とは、２個のシフトレジスタのカスケード接続５３１、５３３と５３５、５３７とに置き換えられる。（例えば、図４のチャネル４０１および４０３の入力４１１および４１３に対応する）入力５０１および５０３が、信号ＳＭ（５０７）に応じて、マルチプレクサ５４１によって入力ライン５０５に時間多重化され、（例えば、図４のチャネル４０１および４０３の出力４２１および４２３に対応する）出力５０９が、デマルチプレクサ５４３によってライン５１３および５１５に多重分離される。マルチプレクサ５４１（またはデマルチプレクサ５４３）の生成は、複数のチャネルが複数のポートで信号を受信（または生成）するかどうかに応じて省略可能であることが理解されよう。
【００３２】
[0050]図６は、図５の例の様々な場所での信号波形を示す図である。入力信号Ｉ１（６１５）およびＩ２（６１７）は、制御信号ＳＭ（６１３）の状態に応じて、信号ＳＩとして時間多重化される。シングルチャネル回路の一般的なクロックサイクル（例えば、図３の時刻ｔ０ ３１０からｔ１ ３０３。これは図６の時刻ｔ０ ６０１からｔ２ ６０３に対応する）では、各入力信号が１つのタイムスロットに割り当てられる（例えば、信号Ｉ１ ６１５がスロット６２１に、信号Ｉ２ ６１７がスロット６２２に割り当てられる）。所与のスロットに割り当てられた入力信号は、論理単位によって処理され、さらなる処理のために、レジスタのカスケード接続によってパイプライン移送される。例えば、ＳＩのスロット６２１に割り当てられた信号Ｉ１ ６１５に定数２１１が乗ぜられて、時刻ｔ1に、レジスタ５３１からのラインＡ１（５２１）に、ＳＡ１の中間結果６３１が生成される。中間結果６３１が、レジスタ５３３によって遅延され、時刻ｔ２ ６０３に、ラインＡ２（５２３）でＳＡ２の出力信号６４１となり、その後に、信号Ｉ１ ６１５が乗算器２２３の入力として、再度ＳＩのスロット６２３に割り当てられる。時刻ｔ３ ６０４に、加算器２３５の結果がレジスタ５３５から出力されて、ラインＢ１（５２５）にＳＢ１の信号６５１が生成され、これが同様にレジスタ５３７によって遅延されて、時刻ｔ４ ６０５に、ラインＢ２（５２７）にＳＢ２の信号６６１が出力される。その後に、信号Ｉ１ ６１５が乗算器２２５の入力として、再度ＳＩのスロット６２５に割り当てられる。時刻ｔ５ ６０６に、ラインＯ（図５の５０９）でＳＯの信号６７１（入力信号Ｉ１ ６１５に対する加算器２３７の結果）が、デマルチプレクサ５１３による出力のために待機している。同様に、信号６７２は、入力信号Ｉ２ ６１７がスロット６２２、６２４、および６２６に割り当てられて計算された結果である。この後も、前の入力に基づく結果が中間的な次のクロックサイクルで利用可能になるように、前の入力からの中間結果がシステム内をパイプライン移送される（例えば、入力Ｉ１のサンプル６２３、６２５、および６２７に基づく結果がタイムスロット６７３で利用可能になる）。
【００３３】
[0051]したがって、図５および６に示すように、シングルチャネル設計におけるレジスタがレジスタのカスケード接続に置き換えられた場合は、レジスタのカスケード接続の出力がマルチチャネル回路における信号処理のためのタイムスロット割り当てに同期するように、シングルチャネル設計のレジスタに格納された中間結果が、マルチチャネル設計におけるレジスタのカスケード接続をパイプライン移送される。本発明の一実施形態では、シングルチャネル設計におけるチャネル固有の各順次要素（例えば、レジスタ、フリップフロップ、メモリ要素）が、Ｎ倍を超える容量の、対応する要素（例えば、レジスタまたはフリップフロップのカスケード接続、タイムスロット割り当てに応じてアドレス指定されるデュアルポートＲＡＭ、ＲＡＭとシフトレジスタの組み合わせ、その他）に置き換えられる。
【００３４】
[0052]図７は、本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。図２のシングルチャネル設計２００を図７の時間多重化Ｎチャネル設計７００に自動的に変換するために、図２のレジスタ２３１がＮ個のシフトレジスタのカスケード接続７１１〜７１９に置き換えられ、図２のレジスタ２３３がＮ個のシフトレジスタのカスケード接続７２１〜７２９に置き換えられる。入力信号に対するタイムスロット割り当てを制御する信号を生成するために、モジュロ−Ｎカウンタ７０５が用いられる。ライン７０７でのモジュロ−Ｎカウンタ７０５の出力がｉ（ｉ＝０，１，．．．，Ｎ−１）の場合、マルチプレクサ７０１は、ライン７０９への入力信号として信号Ｉｉ＋１を選択する。同様に、図７の加算器２３７の出力信号がデマルチプレクサ７０３によってデコードされて、モジュロ−Ｎカウンタ７０５の出力に対応するチャネルの出力信号が生成される。
【００３５】
[0053]図８は、本発明の一実施形態による、マルチチャネルフィルタの出力を多重分離する出力デコーダおよびラッチ回路の例を示す図である。テスタ８１１、８１３、・・・、８１９は、（例えば、図７のモジュロ−Ｎカウンタ７０５からの）選択信号８４１の状態に応じてラッチ８０１、８０３、・・・、８０９を制御する。ライン８４３の信号（例えば、図７の加算器２３７の出力）は、選択信号の状態がテスタ（８１１〜８１９）の定数（８２１〜８２９）のうちの１つと一致したときに、それと対応する、出力ライン８３１、８３３、・・・、８３９のうちの１つでラッチされる。
【００３６】
[0054]図９は、本発明の代替実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの別の例である。図９では、各入力信号を処理するために、回路２００がラウンドロビン様式でアクセスされる。モジュロ−３カウンタ９０７により、各チャネルが次のチャネルの信号の処理に使用されるまでに、各チャネルの入力信号を完全に処理して出力信号を生成することが可能である。モジュロ−Ｎカウンタ９０５は、回路２００で処理されるチャネルの信号を選択する。図９の方法は、マルチチャネル設計の生成時のシングルチャネル回路の修正がより少なくなるが、図９の回路は図７の回路よりスループットが小さい。シングルチャネル設計での信号のパイプライン移送が、図９では、ラウンドロビン方式であるために、十分に利用されていない。入力信号および出力信号の構成によっては、図９のマルチチャネル設計を用いた場合に、各チャネルの信号の処理遅延を最小化できる可能性がある。しかしながら、一般には、異なるチャネルの入力信号はラウンドロビン様式では到着せず、むしろ、異なるチャネルの入力信号は同じタイミングで到着することが理解されよう。入力信号がラウンドロビン様式で到着するように入力信号をリタイミングするために、入力信号とマルチプレクサ９０１との間にバッファを用いることが可能である。そのようなバッファは、入力信号を同じタイミングでサンプルし、チャネルごとに異なる時間量だけ遅延させて、サンプルされた信号がラウンドロビン様式でマルチプレクサ９０１に到着するようにする。
【００３７】
[0055]図７の時間多重化マルチチャネルは、クロック信号ＣＮ（７４１）の周波数がシングルチャネルシステムのクロック信号（例えば、図４のクロック信号ＣＳ）の周波数のＮ倍である場合は、（例えば、図４の）シングルチャネルシステムの集合体を直接置き換えることが可能であることに注意されたい。図９の設計を用いる場合は、入力をリタイミングするために追加回路（例えば、入力信号のタイミングと処理のためのタイムスロット割り当てとに応じてアドレス指定されるＲＡＭのブロック）を用いることが可能である。
【００３８】
[0056]本発明の一実施形態では、シングルチャネル設計の各チャネル固有要素（例えば、レジスタ、定数、ＲＯＭ、またはＲＡＭ）が、マルチチャネル入力の処理をパイプライン化する、対応する要素に置き換えられる。各レジスタ（またはフリップフロップ）は、シフトレジスタのカスケード接続に置き換えられるチャネル固有レジスタと見なすことが可能であるが、パイプラインレジスタは、非チャネル固有レジスタとして識別されることが可能である。パイプラインレジスタがシフトレジスタのカスケード接続に置き換えられない場合でも、時間多重化共有チャネル内のタイミングは、チャネルの入力に対して同期することが可能である。
【００３９】
[0057]パイプラインレジスタの組は、システムグラフのフィードフォワード切断集合である。システムのフィードフォワード切断集合がそうであるように、パイプラインレジスタの組を除去すると、システムが、切断された２つのサブシステムに分割され、その２つのサブシステムの間に単一方向のデータフローがある。ただし、システム内に複数の入力および／または複数の出力がある場合、入力または出力を異なるサブシステムに分割する切断集合は、パイプラインレジスタの組として適格ではない。これは、そのような切断集合がマルチチャネル設計の生成時にパイプライン化されないと、同期が乱れる可能性があるからである。
【００４０】
[0058]フィードフォワード切断集合は、当業者に知られている様々なアルゴリズムによって自動的に識別されることが可能である。例えば、Ｆｒａｎ ＨａｌｐｅｒｉｎとＵｒｉ Ｚｗｉｃｋが「Ｃｏｍｂｉｎａｔｏｒｉａｌ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｍａｘｉｍｕｍ ｄｉｒｅｃｔｅｄ ｃｕｔ ｐｒｏｂｌｅｍ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ １２ｔｈ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｄｉｓｃｒｅｔｅ Ａｌｇｏｒｉｔｈｍｓ、１〜７頁、２００１年）で説明した方法を用いて、フィードフォワード切断集合を決定することが可能である。グラフ理論の文献では、フィードフォワード切断集合は、しばしば、「有向カット（ｄｉｒｅｃｔｅｄ ｃｕｔｓまたはｄｉｃｕｔｓ）」と呼ばれていることに注意されたい。最大数のレジスタを含むフィードフォワード切断集合を見つける場合は、Ｅｒａｎ ＨａｌｐｅｒｉｎとＵｒｉ Ｚｗｉｃｋによる、「最大有向カット」を見つける方法を用いることが可能である。
【００４１】
[0059]図１０は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。図１０の設計は、パイプラインレジスタ１００１〜１００５を含む。フィードフォワード切断集合１０１１は、図１０のシステムを、その間に単一方向のデータフローがある２つのサブシステムに分割する。したがって、レジスタ１００１〜１００５は、非チャネル固有として識別され、したがって、図１０の設計におけるチャネル固有要素は、レジスタ２３１および２３３である。図１０のチャネル固有レジスタ２３１および２３３がレジスタのカスケード接続に置き換えられて、図１１の時間多重化リソース共有設計が生成される。
【００４２】
[0060]図１１は、本発明の一実施形態による、図１０のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。図１１では、パイプラインレジスタ１０１１は不変である。デマルチプレクサ７０３の動作をモジュロ−Ｎカウンタ７０５の状態と同期させるために、レジスタ１２０１が挿入され、これによるカウンタ７０５の出力の１サイクルの遅延が、切断集合１０１１による遅延の影響を相殺する。一般に、Ｍ組のパイプラインレジスタが非チャネル固有要素と識別された場合は、マルチプレクサとデマルチプレクサ（例えば、図１１の７０１と７０３）の動作を同期させるために、モジュロ−Ｎカウンタの集合がｍｏｄ（Ｍ，Ｎ）サイクル遅延される。また、図１０のレジスタ２３１、１００３、および１００５が１組のパイプラインレジスタとして識別される可能性がある点にも注意されたい。この場合は、レジスタ１００１および２３３がシフトレジスタのカスケード接続に置き換えられる。あるいは、パイプラインレジスタとして識別されるレジスタが図１０にない場合は、図１０のすべてのレジスタがレジスタのカスケード接続に置き換えられる。この場合、結果として得られる設計はＮ組のパイプラインレジスタを有し、ｍｏｄ（Ｎ，Ｎ）＝０なので、モジュロ−Ｎカウンタ７０５の出力を遅延させるレジスタは不要である。
【００４３】
[0061]シングルチャネルシステムのチャネル固有レジスタは、マルチチャネルシステムの生成時にＮ個のシフトレジスタのカスケード接続に置き換えられることが可能である。いくつかのＦＰＧＡアーキテクチャ（Ｘｉｌｉｎｘ Ｖｉｒｔｅｘなど）では、シフトレジスタはナチュラルプリミティブである。これにより、ターゲットアーキテクチャがこれらのＦＰＧＡアーキテクチャのいずれかであれば、非常に効率的なメモリの使い方が可能になる。各チャネル固有レジスタは、モジュロ−Ｎカウンタの状態に応じて中間結果をパイプライン移送することが可能な他のメモリ構成（例えば、ＮアイテムのデュアルポートＲＡＭ、ＲＡＭとシフトレジスタの組み合わせ、その他）に置き換えられることも可能であることを理解されたい。
【００４４】
[0062]図１２は、本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル回路の別の例を示す図である。図１２の設計は、レジスタ１２０１、１２０３、２３１とレジスタ１２０５、２３３とを含むフィードフォワード切断集合１２１１および１２１３を含む。したがって、図１２のすべてのレジスタは非チャネル固有として識別されることが可能であり、図１３の設計の生成時にレジスタのカスケード接続に置き換えられるレジスタはない。
【００４５】
[0063]図１３は、本発明の一実施形態による、図１２のシングルチャネル設計から自動的に生成されるマルチチャネルフィルタの例である。マルチプレクサ１３０１とデマルチプレクサ１３０３との間に２組のパイプラインレジスタがあるので、２サイクルの遅延を用いて、マルチチャネルフィルタの動作を同期させることが可能である。図１３の設計では、２組のパイプラインレジスタによる遅延を補償するために、デマルチプレクサ１３０３の定数を２シフトだけ循環させている。したがって、モジュロ−Ｎカウンタがｉ（ｉ＝０，１，．．．，Ｎ−１）を出力すると、マルチプレクサ１３０１が信号Ｉｉ＋１を入力として選択し、デマルチプレクサ１３０３がＯｍｏｄ（ｉ−１，Ｎ）を出力する。
【００４６】
[0064]上述の例から、時間共有設計において不変のままのパイプラインレジスタの組による遅延を補償するために、別の方法（例えば、遅延要素を挿入する、デマルチプレクサに用いる定数をシフトする、別の選択信号を生成する、またはこれらの組み合わせ）を用いることが可能であることが、当業者には明らかであろう。さらに、一般には、有限ステートマシン（ＦＳＭ）（例えば、モジュロ−Ｎカウンタ）を用いて入力信号の時間多重化ならびに設計におけるリソース共有を制御することも可能である。
【００４７】
[0065]上述の例は、単一入力と単一出力とを有するシングルチャネル設計を用いて示されているが、この説明から、複数入力と複数出力とを有するシングルチャネル設計にも、本発明の様々な実施形態の方法が適用可能であることが当業者には明らかであろう。さらに、Ｍチャネル設計（Ｍ＞１）をシングルチャネル設計として扱うことにより、リソース共有を伴うＮ×Ｍチャネル設計を自動的に生成することが可能である。
【００４８】
[0066]本発明の一実施形態では、複数のチャネルのリソース共有設計の生成時の、従来の方法（例えば、折り畳み変形、その他）による自動変形の前および／または後に、シングルチャネル設計が最適化される。
【００４９】
[0067]図１４は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法のフローチャートである。操作１４０１でシングルチャネル設計を受け取り、操作１４０３で、シングルチャネル設計を自動的に変形して時間多重化マルチチャネル設計を生成する。この変形はシングルチャネル設計に基づいており、シングルチャネルシステムの集合体より論理要素が少ないので、大量の計算を要する、高レベル並列処理の抽出操作が不要である。
【００５０】
[0068]図１５は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の詳細なフローチャートである。操作１５０１で、シングルチャネル回路の設計を受け取る。操作１５０３で、シングルチャネル回路の論理要素へのアクセスを時間多重化するために、Ｎステートの有限ステートマシン（ＦＳＭ）（例えば、モジュロ−Ｎカウンタ）を生成する。操作１５０５で、Ｎチャネル入力を、ＦＳＭの状態に応じて、シングルチャネル回路への入力として多重化する多重化回路を生成する。操作１５０７で、シングルチャネル回路の各チャネル固有要素（例えば、ＲＡＭ、ＲＯＭ、定数、レジスタ、フリップフロップ）を、ＦＳＭの状態に応じて複数のチャネルについてアクセスされる、対応する要素に置き換える。操作１５０９で、ＦＳＭの状態に応じて、シングルチャネル回路の対応する出力からＮチャネル出力を多重分離する多重分離回路を生成する。上述の変形の後に、シングルチャネル設計からマルチチャネル設計が生成される。
【００５１】
[0069]図１６は、本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の例である。操作１６０１で、シングルチャネル回路の設計を受け取る。操作１６０３で、モジュロ−Ｎカウンタの値がｉであるときにチャネルｉ（ｉ＝０，１，．．．，Ｎ−ｌ）の信号に対する操作が実施されるようにシングルチャネルの論理要素を制御する、そのモジュロ−Ｎカウンタを生成する。操作１６０５で、カウンタの値がｉのときに、チャネルｉの入力をシングルチャネル回路の入力として受け取るＮアイテムのマルチプレクサを生成する。操作１６０７（オプション）で、シングルチャネル回路内の非チャネル固有の順次要素（例えば、フリップフロップ、レジスタ、ＲＯＭ、定数、ＲＡＭ）を識別する。操作１６０９で、シングルチャネル設計の各チャネル固有レジスタ（例えば、フリップフロップ）を、Ｎ個の順次要素（例えば、Ｎ個のシフトレジスタのカスケード接続、ＮアイテムのデュアルポートＲＡＭ、またはＲＡＭとシフトレジスタの組み合わせ）に置き換える。操作１６１１で、サイズＭの各チャネル固有メモリ（例えば、ＲＡＭまたはＲＯＭ）を、サイズＮ×Ｍの新しいメモリに置き換える（新しいメモリのメモリアイテムＮ×ｊ＋ｉは、シングルチャネル回路においてメモリのアイテムｊがアドレス指定されたときに、チャネルｉに対してアドレス指定される）。操作１６１３で、各チャネル固有定数をＮアイテムのＲＯＭメモリに置き換える（メモリアイテムｉは、チャネルｉの定数に対してアドレス指定される）。操作１６１５で、各チャネルに対して、シングルチャネル回路の対応する出力から出力を生成する、Ｎアイテムのデマルチプレクサを生成する。
【００５２】
[0070]本発明の一実施形態では、マルチチャネル回路の自動生成時に導入されたレジスタを用いて回路のクロックレートを高めるために、リタイミングアルゴリズム（例えば、切断集合のリタイミングおよびパイプライン化、クロック周期の最小化のためのリタイミング（「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、９１〜１１８頁）で説明されている方法や、当業者に知られている他の方法など）をさらに用いる。
【００５３】
[0071]回路設計の過程の中間段階（例えば、周辺機器のリタイミング時やアーキテクチャのリタイミング時）に、負遅延を有する負遅延レジスタを用いることが可能である。物理的な負遅延レジスタは存在しないが、負遅延レジスタは、設計の中間的状態におけるタイミング制約を表すものであることを理解されたい。負遅延レジスタは、設計プロセスの早い段階で用いることが可能であり、一般には、最終的なソリューションを達成するための回路設計の過程で除去される。
【００５４】
[0072]本発明の一実施形態では、シングルチャネルシステムは、１つまたは複数の負遅延レジスタで特徴づけられ、負遅延レジスタは、普通のレジスタと同様の様式で変形されることが可能である。
【００５５】
[0073]図１７は、シングルチャネルシステムの例である。説明のために、レジスタ以外の要素の遅延は無視されている。各レジスタ（例えば、１７３１、１７３３、および１７４１）は、１単位の遅延を有する。要素１７１１、１７１３、および１７１５は定数であって、これらは時間的に変化しない。したがって、ライン１７０１の入力をＩ１（ｔ）とすると、ライン１７０３の信号は、Ｉ１（ｔ）×Ｃ３＋Ｉ１（ｔ−２）×Ｃ２＋Ｉ１（ｔ−２）×Ｃ１である。図１７では、レジスタ１７３１が乗算器１７２１の中間結果を格納してＩ１（ｔ−１）×Ｃ１を生成し、レジスタ１７３３が、乗算器１７２３の中間結果を格納してＩ１（ｔ−１）×Ｃ１を生成する。レジスタ１７４１は、加算器１７５１の中間結果を格納してＩ１（ｔ−２）×Ｃ２＋Ｉ１（ｔ−２）×Ｃ１を生成する。
【００５６】
[0074]乗算器１７２５と加算器１７５３との間の経路に正遅延レジスタと負遅延レジスタのペアを挿入することが可能である。挿入すると、図１７の回路が図１８の回路に変形される。図１８では、レジスタ１７４３が負遅延レジスタであり、レジスタ１７３５が普通のレジスタ（正遅延レジスタ）である。図１８では、レジスタ１７３１、１７３３、および１７３５が、１組のパイプラインレジスタである。このパイプラインレジスタの組（１７３１、１７３３、および１７３５）を除去するとシングルチャネル回路の遅延が変わることに注意されたい（この変化が許容されるか望ましい場合もある）。あるいは、図１９の点１７０１の前にレジスタ（図１９には示されず）を挿入して、図１８の回路と同じ遅延を有するシングルチャネル回路にすることが可能であることにも注意されたい。したがって、図１８のシングルチャネル回路を、図１９のシングルチャネル回路として指定することが可能である。図１９で、ライン１７０１の入力がＩ１（ｔ）であるとすると、ライン１７０３の出力は、Ｉ１（ｔ＋１）×Ｃ３＋Ｉ１（ｔ−１）×Ｃ２＋Ｉ１（ｔ−１）×Ｃ１である。したがって、１単位のタイミングシフトを別にすれば、図１９の回路は、本質的に図１７（または図１８）の回路としての機能を実施する。図１９の回路が入力として指定された場合は、マルチチャネル回路を自動的に生成することが可能である。レジスタ１７４１および１７４３はパイプラインレジスタではなく、これらはカスケード接続された複数のレジスタに置き換えられることが可能である。図２０は、図１９を入力して自動的に生成された２チャネル回路の例である。図１９の負遅延レジスタ１７４３は、カスケード接続された負遅延レジスタ１７７１および１７７３に置き換えられ、図１９のレジスタ１７４１は、カスケード接続されたレジスタ１７６１および１７６３に置き換えられる。入力信号を一度に１つずつ共有チャネルに供給するためにマルチプレクサ１７０５が追加され、共有チャネルから出力を一度に１つずつ復元するためにデマルチプレクサ１７０７が追加される。マルチチャネル回路が生成された後、リタイミングアルゴリズム（例えば、「ＶＬＳＩ ｄｉｇｉｔａｌ ｓｉｇｎａｌ ｐｒｏｃｅｓｓｉｎｇ ｓｙｓｔｅｍｓ： ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ」（Ｋｅｓｈａｂ Ｋ．Ｐａｒｈｉ、Ｗｉｌｅｙ Ｉｎｔｅｒｓｃｉｅｎｃｅ、１９９９年、９１〜１１８頁）で説明されている方法や、当業者に知られている他の方法など）を用いてシステムを最適化することが可能である。例えば、負遅延レジスタを除去するためにパイプラインレジスタの出力を挿入することが可能である。例えば、乗算器１７２１、１７２３、および１７２５の後に２組のパイプラインレジスタを挿入して、図２１の回路を生成することが可能である。前述のとおり、一般に、パイプラインレジスタの組を挿入したり削除したりすると、ライン１７０３の出力の生成のタイミングが変わるので、適切な数のレジスタ（または遅延要素）をライン１７０９に用いて（図１１に示されるように）デマルチプレクサ１７０７の制御信号のタイミングを調整することが可能であり、（図１３に示されるように）制御信号と出力ラインとの間の対応関係を調整することが可能であることに注意されたい。本発明の実施形態によれば、図２１の回路は、図１７の回路から直接生成されることが可能である。図２０の乗算器１７２５と加算器１７５１の後にも２組のパイプラインレジスタを挿入して負遅延レジスタを除去できることに注意されたい。
【００５７】
[0075]さらに、本発明の一実施形態では、パイプラインレジスタを識別する過程で、正遅延レジスタおよび負遅延レジスタの１つまたは複数のペアがシングルチャネルシステムに導入される。例えば、マルチチャネル回路の生成のために図１７のシングルチャネル回路を受け取った後、パイプラインレジスタの識別のために正遅延レジスタと負遅延レジスタのペア（例えば、図１８の１７３５および１７４３）を挿入することが可能である。図１８に示されるように、普通のレジスタ１７３５と負遅延レジスタ１７４３とが挿入されると、パイプラインレジスタの組（１７３１、１７３３、および１７３５）の識別が可能になる。したがって、図１８のレジスタ１７４１および１７４３だけが、対応する、カスケード接続されたレジスタに置き換えられる。同様に、マルチチャネル回路の自動生成の回路を、リタイミングアルゴリズムを用いてさらに最適化することが可能である。
【００５８】
[0076]図２２〜２５は、本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。図２２のシングルチャネルフィルタは、パイプライン化された加算器１８４７（Ａ２）と、パイプライン化された乗算器１８４１〜１８４３（Ｍ１〜Ｍ３）とを有する。パイプライン化された加算器にはレジスタが組み込まれている。例えば、パイプライン化された加算器１８４７はレジスタ１８６５を有し、レジスタ１８６５はパイプライン化された加算器の物理的な一部であって、分離不可能である。同様に、パイプライン化された乗算器にもレジスタが組み込まれている（例えば、パイプライン化された乗算器１８４１、１８４２、および１８４３には、レジスタ１８３１、１８３３、および１８３５がそれぞれ組み込まれている）。
【００５９】
[0077]加算器１８５１を実装するために、パイプライン化された加算器が用いられるとする。加算器１８５１にレジスタを与えるために、負遅延レジスタを用いないのであれば、（例えば、加算器１８５３の両方の入力ラインに）普通のレジスタの組を追加することが可能である。そのような方法では、シングルチャネルシステムの遅延が増える可能性がある。別の方法として、図２３は、加算器１８５１と１８５３との間に正遅延レジスタおよび負遅延レジスタ（１８６１および１８６３）を追加する例を示している。したがって、加算器１８５１とレジスタ１８６１とを、パイプライン化された加算器１８４５（Ａ１）として実装することが可能である。リタイミングを実行してもシングルチャネルシステムの負遅延レジスタを除去することができないことに注意されたい。
【００６０】
[0078]本発明の実施形態によれば、マルチチャネル回路を自動的に生成することが可能である。例えば、図２３は、２チャネル回路について、本発明の一実施形態に従って生成されたマルチチャネル回路の時間共有部分を示している。２チャネル回路の、入力を多重化する部分と、出力を多重分離する部分とは、図２４に示されていないので注意されたい。レジスタ１８３１、１８３３、および１８３５は、図２３においてチャネル固有であり、レジスタ１８３２、１８３４、および１８３６は、図２４においてマルチチャネル回路のために挿入される。同様に、図２３のレジスタ１８６１および１８６３は、図２４の、カスケード接続されたレジスタの組（１８６１、１８６２、および１８６３と１８６４）に置き換えられる。
【００６１】
[0079]本発明の一実施形態に従って生成される２チャネル回路では、パイプライン化された演算器のそれぞれに対して追加レジスタが生成される。そして、負遅延レジスタを除去するためにリタイミング操作が行われる。例えば、リタイミング操作では、図２４のレジスタ１８３２および１８３４を加算器１８５１と１８５３との間の経路に移動して、加算器１８５１と１８５３との間の経路に、負レジスタ（１８６３および１８６４）を相殺するのに十分な、普通のレジスタがあるようにすることが可能である。そのようにして２チャネル回路が得られる例を図２５に示す。図２５では、乗算器２８２１、１８２３、および１８２５と、加算器１８５１および１８５３とを、対応する、パイプライン化された演算器（パイプライン化された乗算器１８４１、１８４２、および１８４３と、パイプライン化された加算器１８４５および１８４７）として実装することが可能である。ただし、負遅延レジスタはすべて、リタイミング後に除去される。
【００６２】
[0080]上述の例では、パイプライン化された加算器と、パイプライン化された乗算器とを示した。しかしながら、次の説明から、他のパイプライン化された論理要素やパイプライン化されたＩＰブロックも同様に扱うことが可能であることを理解されよう。
【００６３】
[0081]本発明の一実施形態では、パイプラインレジスタの組が識別されず、すべてのレジスタがチャネル固有であると見なされる。例えば、シングルチャネルシステムをＮチャネルシステムに自動的に変形する方法は、以下の操作を含む。
【００６４】
[0082]１．モジュロ−ＮカウンタをＮステートの有限ステートマシン（ＦＳＭ）として生成する。ＦＳＭのステート変数はｃｎｔで表される。システムのｍ番目のチャネル（（０≦ｍ≦Ｎ−１）は、ＦＳＭがｍ番目の状態のとき（例えば、ｃｎｔ＝ｍであるとき）に有効にアクティブ化される。
【００６５】
[0083]２．各レジスタを、Ｎ個のシフトレジスタのカスケード接続に置き換える（あるいは、Ｎが大きい場合は、各レジスタを、ＮアイテムのデュアルポートＲＡＭか、ＲＡＭとシフトレジスタの組み合わせに置き換えることが可能である）。
【００６６】
[0084]３．サイズＭの各ＲＡＭメモリを、サイズＮ×ＭのＲＡＭメモリに置き換える。アドレス生成回路は、シングルチャネル設計のメモリアイテムＡがアドレスＮ×Ａ＋ｃｎｔのアイテムに置き換えられるように、メモリアイテムをアドレス指定するよう修正または追加される。新しいメモリからの出力がＦＳＭの状態と同期するようにメモリアイテムを論理的にパイプライン化するために、他のアドレス変換方式を用いることも可能であることを理解されたい。一般に、変換されたアドレスは、元のアドレス、ＦＳＭの状態、およびアクティブなチャネルの番号の関数である。
【００６７】
[0085]４．チャネル固有のＲＯＭがある場合（例えば、ＲＯＭの内容がチャネルごとに異なる場合）は、ＲＯＭアイテムＮ×Ａ＋ｍがｍ番目のチャネルのＲＯＭアイテムＡの内容を保持するように、ＲＡＭの場合と同様の変形を適用する。ＲＯＭがチャネル固有でない場合、変形は不要である。
【００６８】
[0086]５．チャネル固有の定数がある場合（例えば、チャネルごとに定数の値が異なる場合）は、その定数を、ＮアイテムのＲＯＭに置き換える。ＲＯＭのアドレスラインはｃｎｔで駆動される（ＲＯＭアクセスに１クロックの遅延がある場合はｃｎｔ−１で駆動される）。定数がチャネル固有でない場合、変形は不要である。
【００６９】
[0087]異なるチャネルの入力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の入力ポートを有する場合は、これらの入力を、ｃｎｔで駆動される選択ラインを有する、Ｎアイテムのマルチプレクサで多重化する。ｃｎｔは、入力を駆動するクロックよりＮ倍高速である。同様に、異なるチャネルの出力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の出力ポートを有する場合は、これらの出力を、ｃｎｔで駆動される選択ラインを有する、Ｎアイテムのデコーダで多重分離する。この出力は、Ｎ倍低速なクロックでラッチされることが可能である。シングルチャネル設計の他のコンポーネントは、時間多重化されている間中、現状のまま、共有リソースとして保持される。
【００７０】
[0088]本発明の別の実施形態では、レジスタの生成を避けるためにパイプラインレジスタの組が識別される。例えば、シングルチャネルシステムをＮチャネルシステムに自動的に変形する方法は、以下の操作を含む。
【００７１】
[0089]１．可能な限り多くの、かつ幅広のレジスタをカバーするために、システム内のパイプラインレジスタを識別する。パイプラインレジスタの組が複数存在してもよいが、それらの組は相互に排他的でなければならない。どのパイプラインレジスタの組にも分類されないレジスタはすべて状態レジスタである。パイプラインレジスタは非チャネル固有であり、状態レジスタはチャネル固有である。Ｐ個の個別のパイプラインレジスタの組が存在する場合、システムは、まとまりのないＰ＋１個のサブシステムに分割されており、サブシステムが単体でリンクされたリストが形成されている。このリストでは、各フィードフォワード切断集合が、リンクを、データフローの方向を示すリンク方向とともに定義している。リンクされたリストでの順番がｉ（０≦ｉ≦Ｐ）であるサブシステムをＳｉで表す。
【００７２】
[0090]２．少なくとも１つのモジュロ−ＮカウンタからＰ＋１個のＮステートの有限ステートマシン（ＦＳＭ）を生成する。ｉ番目のＦＳＭ（０≦ｉ≦Ｐ）の状態変数をｃｎｔｉで表す。ｉ番目のＦＳＭがｍ番目の状態にある場合（例えば、ｃｎｔｉ＝ｍの場合）、サブシステムＳｉのハードウェアは、ｍ番目のチャネル（０≦ｍ≦Ｎ−１）のデータを処理する。［０，Ｐ］における∀ｉ，ｊに対してｍｏｄ（（ｃｎｔｉ−ｃｎｔｊ），Ｎ）＝ｍｏｄ（（ｊ−ｉ），Ｎ）であれば、サブシステム間で適正な同期が維持される。この関係は、ｃｎｔｉがｃｎｔｉ−１を１クロック遅延させたものである場合に成り立つ（ｉ＝１，２，．．．，Ｎ−１）。したがって、ｃｎｔｉは、レジスタを用いてｃｎｔｉ−１から導出されることが可能であり、ＦＳＭは、１つのモジュロ−Ｎカウンタとレジスタのカスケード接続とを用いて実装されることが可能である。
【００７３】
[0091]３．各状態レジスタを、Ｎ個のシフトレジスタのカスケード接続に置き換える（あるいは、Ｎが大きい場合は、各状態レジスタを、ＮアイテムのデュアルポートＲＡＭか、ＲＡＭとシフトレジスタの組み合わせに置き換えることが可能である）。
【００７４】
[0092]４．サイズＭの各ＲＡＭメモリを、サイズＮ＿ＭのＲＡＭメモリに置き換える。サブシステムＳｉ内のＲＡＭに関しては、シングルチャネル設計のメモリアイテムＡが、アドレスＮ＿Ａ＋ｃｎｔｉにあるアイテムに置き換えられるようにメモリアイテムをアドレス指定するよう、アドレス生成回路が修正または追加される。新しいメモリからの出力がｉ番目のＦＳＭの状態と同期するようにメモリアイテムを論理的にパイプライン化するために、他のアドレス変換方式を用いることも可能であることを理解されたい。一般に、変換されたアドレスは、元のアドレス、ｉ番目のＦＳＭの状態、およびアクティブなチャネルの番号の関数である。
【００７５】
[0093]５．チャネル固有のＲＯＭがある場合（例えば、ＲＯＭの内容がチャネルごとに異なる場合）は、ＲＯＭアイテムＮ＿Ａ＋ｍがｍ番目のチャネルのＲＯＭアイテムＡの内容を保持するように、ＲＡＭの場合と同様の変形を適用する。ＲＯＭがチャネル固有でない場合、変形は不要である。
【００７６】
[0094]６．サブシステムＳｉ内にチャネル固有の定数がある場合（例えば、チャネルごとに定数の値が異なる場合）は、その定数を、ＮアイテムのＲＯＭに置き換える。ＲＯＭのアドレスラインはｃｎｔｉで駆動される（ＲＯＭアクセスに１クロックの遅延がある場合はｃｎｔｉ−１で駆動される）。定数がチャネル固有でない場合、変形は不要である。
【００７７】
[0095]異なるチャネルの入力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の入力ポートを有する場合は、これらの入力を、ｃｎｔ０で駆動される選択ラインを有する、Ｎアイテムのマルチプレクサで多重化する。ｃｎｔ０は、入力を駆動するクロックよりＮ倍高速である。同様に、異なるチャネルの出力を共通ポートで多重化することが可能である。複数のチャネルがそれぞれ別々の出力ポートを有する場合は、これらの出力を、ｃｎｔｐで駆動される選択ラインを有する、Ｎアイテムのデコーダで多重分離する。この出力は、Ｎ倍低速なクロックでラッチされることが可能である。シングルチャネル設計の他のコンポーネントは、時間多重化されている間中、現状のまま、共有リソースとして保持される。
【００７８】
[0096]Ｐ＋１個のＮステートの有限ステートマシンを用いればＰ＋１個のサブシステムのタイミングを個別に制御することが可能であるが、別の方法として、単一のＮステートのＦＳＭを用いてすべてのサブシステムの動作を制御することが可能である。この場合、所与のチャネルに対して、ＦＳＭの状態が別の値に達すると、別のサブシステムが処理を行う。例えば、ＦＳＭが状態ｃｎｔ＝ｍｏｄ（ｍ−１，Ｎ）の場合には、サブシステムＳｉのハードウェアがｍ番目のチャネル（０≦ｍ≦Ｎ−１）のデータを処理する。
【００７９】
[0097]パイプラインレジスタの組は、タイミング制限が許せば、識別および除去されることが可能である。例えば、図１０のパイプラインレジスタの組１０１１は、図２の設計を生成するために除去されることが可能であり、図１１のパイプラインレジスタの組１０１１は、図７の設計を生成するために自動的に除去されることが可能である。同様に、パイプラインレジスタが自動的に設計に追加されることも可能である。一般には、パイプラインレジスタを追加したり削除したりすると、回路の入力から出力までの遅延が変わることに注意されたい。ただし、そのような変化は許容されることが多い。
【００８０】
[0098]本発明の一実施形態では、実行時に構成可能な深さを有するシフトレジスタを用い、実行時に構成可能な法を有するモジュロ−Ｎカウンタを用いると、動作を中断させることなく、折り畳みレートＮを実行時に変更することが可能である。アクティブチャネルの数が動的なパラメータである用途では、折り畳みレートをアクティブチャネルの数に適応させて、状況が許すときに、電力消費を抑えるためにクロックレートを下げることが可能である。
【００８１】
[0099]したがって、本発明の少なくとも１つの実施形態は、入力されたシングルチャネルシステムの設計からマルチチャネルシステムの設計を自動的に生成する。シングルチャネルシステムの設計は、論理（計算）ユニットの時間多重化リソース共有を伴うＮチャネルシステムに自動的に変形される。この変形はシンプルで非常に高速であり、得られる設計のハードウェアは非常に効率的である。
【００８２】
[00100]本発明の様々な実施形態の方法によりシングルチャネル設計から時間多重化マルチチャネル設計が生成されるので、より少ない数の論理要素に対して最適化および合成の操作を高速で実施することが可能である。制御論理の使い方については、最小限にすることが可能である。一部のＦＰＧＡアーキテクチャでは、合成されたシステムのメモリの使い方を非常に効率的にすることが可能である。さらに、本発明の様々な方法が、高次のパイプラインと大幅な高速化を想定している。
【００８３】
[00101]本明細書ではここまで、本発明の特定の例示的実施形態を参照しながら本発明について説明してきた。添付の特許請求項で示されている、本発明の広い趣旨および範囲を逸脱することなく、様々な修正を本発明に施しうることは明らかであろう。したがって、本明細書および添付図面は、制限の意味ではなく例示の意味で解釈されるべきである。
【図面の簡単な説明】
【００８４】
【図１】本発明に使用可能なデータ処理システムのブロック図の例である。
【図２】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能なシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。
【図３】図２の例の様々な場所での信号波形を示す図である。
【図４】図２のシングルチャネルフィルタの集合体に対応する２チャネルフィルタの例を示す図である。
【図５】本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成される２チャネルフィルタの例である。
【図６】図５の例の様々な場所での信号波形を示す図である。
【図７】本発明の一実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図８】本発明の一実施形態による、マルチチャネルフィルタの出力を多重分離する出力デコーダおよびラッチ回路の例を示す図である。
【図９】本発明の代替実施形態による、図２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの別の例である。
【図１０】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル３タップ有限インパルス応答（ＦＩＲ）フィルタの例を示す図である。
【図１１】本発明の一実施形態による、図１０のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図１２】本発明の一実施形態による、マルチチャネルフィルタを自動的に生成することが可能な、パイプラインレジスタを有するシングルチャネル回路の別の例を示す図である。
【図１３】本発明の一実施形態による、図１２のシングルチャネルフィルタから自動的に生成されるマルチチャネルフィルタの例である。
【図１４】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法のフローチャートである。
【図１５】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の詳細なフローチャートである。
【図１６】本発明の一実施形態による、シングルチャネル回路からマルチチャネル回路を生成する方法の例である。
【図１７】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図１８】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図１９】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２０】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２１】本発明の一実施形態による、負遅延レジスタを有するシングルチャネル回路からマルチチャネル回路を生成する例を示す図である。
【図２２】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２３】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２４】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【図２５】本発明の一実施形態による、負遅延レジスタを用いたシングルチャネル回路からマルチチャネル回路を生成する別の例を示す図である。
【特許請求の範囲】
【請求項１】
デジタル回路を設計する方法であって、
シングルチャネル回路である第１の設計を受け取るステップと、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成するステップと
を含む方法。
【請求項２】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項１に記載の方法。
【請求項３】
前記時間多重化マルチチャネル回路をリタイミングするステップをさらに含む、請求項１に記載の方法。
【請求項４】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項３に記載の方法。
【請求項５】
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別するステップと、
前記パイプラインレジスタの組を除去するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記変形するステップが、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成するステップを含む、請求項１に記載の方法。
【請求項８】
前記変形するステップが、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成するステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記変形するステップが、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成するステップをさらに含む、請求項７に記載の方法。
【請求項１０】
前記変形するステップが、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換えるステップをさらに含み、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項７に記載の方法。
【請求項１１】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項１０に記載の方法。
【請求項１２】
前記チャネル固有要素がチャネル固有順次要素である、請求項１０に記載の方法。
【請求項１３】
非チャネル固有順次要素を識別するステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項１３に記載の方法。
【請求項１５】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項１２に記載の方法。
【請求項１６】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項１２に記載の方法。
【請求項１７】
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定するステップをさらに含む、請求項１２に記載の方法。
【請求項１８】
前記変形するステップが、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換えるステップを含み、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項１に記載の方法。
【請求項１９】
前記対応する要素が順次アドレス指定される、請求項１８に記載の方法。
【請求項２０】
前記対応する要素が順次アドレス指定される、請求項１８に記載の方法。
【請求項２１】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項１８に記載の方法。
【請求項２２】
デジタル処理システムで実行されたときに、デジタル回路を設計する方法を前記システムに実施させる、実行可能なコンピュータプログラム命令を格納するマシン可読媒体であって、前記方法が、
シングルチャネル回路である第１の設計を受け取るステップと、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成するステップと
を含む媒体。
【請求項２３】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項２２に記載の媒体。
【請求項２４】
前記方法が、前記時間多重化マルチチャネル回路をリタイミングするステップをさらに含む、請求項２２に記載の媒体。
【請求項２５】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項２４に記載の媒体。
【請求項２６】
前記方法が、
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別するステップと、
前記パイプラインレジスタの組を除去するステップとをさらに含む、請求項２２に記載の媒体。
【請求項２７】
前記方法が、
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入するステップをさらに含む、請求項２２に記載の媒体。
【請求項２８】
前記変形するステップが、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成するステップを含む、請求項２２に記載の媒体。
【請求項２９】
前記変形するステップが、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成するステップをさらに含む、請求項２８に記載の媒体。
【請求項３０】
前記変形するステップが、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成するステップをさらに含む、請求項２８に記載の媒体。
【請求項３１】
前記変形するステップが、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換えるステップをさらに含み、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項２８に記載の媒体。
【請求項３２】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項３１に記載の媒体。
【請求項３３】
前記チャネル固有要素がチャネル固有順次要素である、請求項３１に記載の媒体。
【請求項３４】
前記方法が、
非チャネル固有順次要素を識別するステップをさらに含む、請求項３３に記載の媒体。
【請求項３５】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項３４に記載の媒体。
【請求項３６】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項３３に記載の媒体。
【請求項３７】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項３３に記載の媒体。
【請求項３８】
前記方法が、
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定するステップをさらに含む、請求項３３に記載の媒体。
【請求項３９】
前記変形するステップが、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換えるステップを含み、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項２２に記載の媒体。
【請求項４０】
前記対応する要素が順次アドレス指定される、請求項３９に記載の媒体。
【請求項４１】
前記対応する要素が順次アドレス指定される、請求項３９に記載の媒体。
【請求項４２】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項３９に記載の媒体。
【請求項４３】
デジタル回路を設計するデジタル処理システムであって、
シングルチャネル回路である第１の設計を受け取る手段と、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成する手段と
を備えるデジタル処理システム。
【請求項４４】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項４３に記載のデジタル処理システム。
【請求項４５】
前記時間多重化マルチチャネル回路をリタイミングする手段をさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４６】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項４５に記載のデジタル処理システム。
【請求項４７】
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別する手段と、
前記パイプラインレジスタの組を除去する手段とをさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４８】
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入する手段をさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４９】
前記変形する手段が、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成する手段を備える、請求項４３に記載のデジタル処理システム。
【請求項５０】
前記変形する手段が、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成する手段をさらに備える、請求項４９に記載のデジタル処理システム。
【請求項５１】
前記変形する手段が、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成する手段をさらに備える、請求項４９に記載のデジタル処理システム。
【請求項５２】
前記変形する手段が、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換える手段をさらに備え、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項４９に記載のデジタル処理システム。
【請求項５３】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを備える、請求項５２に記載のデジタル処理システム。
【請求項５４】
前記チャネル固有要素がチャネル固有順次要素である、請求項５２に記載のデジタル処理システム。
【請求項５５】
非チャネル固有順次要素を識別する手段をさらに備える、請求項５４に記載のデジタル処理システム。
【請求項５６】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項５５に記載のデジタル処理システム。
【請求項５７】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項５４に記載のデジタル処理システム。
【請求項５８】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項５４に記載のデジタル処理システム。
【請求項５９】
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定する手段をさらに備える、請求項５４に記載のデジタル処理システム。
【請求項６０】
前記変形する手段が、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換える手段を備え、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項４３に記載のデジタル処理システム。
【請求項６１】
前記対応する要素が順次アドレス指定される、請求項６０に記載のデジタル処理システム。
【請求項６２】
前記対応する要素が順次アドレス指定される、請求項６０に記載のデジタル処理システム。
【請求項６３】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを備える、請求項６０に記載のデジタル処理システム。
【請求項６４】
デジタル回路を設計する方法であって、
シングルチャネル回路である第１の設計を受け取るステップと、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成するステップと、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用するステップと
を含む方法。
【請求項６５】
前記情報が、折り畳みの集合の情報を含む、請求項６４に記載の方法。
【請求項６６】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項６４に記載の方法。
【請求項６７】
デジタル処理システムで実行されたときに、デジタル回路を設計する方法を前記システムに実施させる、実行可能なコンピュータプログラム命令を格納するマシン可読媒体であって、前記方法が、
シングルチャネル回路である第１の設計を受け取るステップと、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成するステップと、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用するステップと
を含む媒体。
【請求項６８】
前記情報が、折り畳みの集合の情報を含む、請求項６７に記載の媒体。
【請求項６９】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項６７に記載の媒体。
【請求項７０】
デジタル回路を設計するデジタル処理システムであって、
シングルチャネル回路である第１の設計を受け取る手段と、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成する手段と、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用する手段と
を備えるデジタル処理システム。
【請求項７１】
前記情報が、折り畳みの集合の情報を含む、請求項７０に記載のデジタル処理システム。
【請求項７２】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項７０に記載のデジタル処理システム。
【請求項１】
デジタル回路を設計する方法であって、
シングルチャネル回路である第１の設計を受け取るステップと、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成するステップと
を含む方法。
【請求項２】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項１に記載の方法。
【請求項３】
前記時間多重化マルチチャネル回路をリタイミングするステップをさらに含む、請求項１に記載の方法。
【請求項４】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項３に記載の方法。
【請求項５】
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別するステップと、
前記パイプラインレジスタの組を除去するステップと
をさらに含む、請求項１に記載の方法。
【請求項６】
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記変形するステップが、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成するステップを含む、請求項１に記載の方法。
【請求項８】
前記変形するステップが、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成するステップをさらに含む、請求項７に記載の方法。
【請求項９】
前記変形するステップが、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成するステップをさらに含む、請求項７に記載の方法。
【請求項１０】
前記変形するステップが、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換えるステップをさらに含み、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項７に記載の方法。
【請求項１１】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項１０に記載の方法。
【請求項１２】
前記チャネル固有要素がチャネル固有順次要素である、請求項１０に記載の方法。
【請求項１３】
非チャネル固有順次要素を識別するステップをさらに含む、請求項１２に記載の方法。
【請求項１４】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項１３に記載の方法。
【請求項１５】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項１２に記載の方法。
【請求項１６】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項１２に記載の方法。
【請求項１７】
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定するステップをさらに含む、請求項１２に記載の方法。
【請求項１８】
前記変形するステップが、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換えるステップを含み、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項１に記載の方法。
【請求項１９】
前記対応する要素が順次アドレス指定される、請求項１８に記載の方法。
【請求項２０】
前記対応する要素が順次アドレス指定される、請求項１８に記載の方法。
【請求項２１】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項１８に記載の方法。
【請求項２２】
デジタル処理システムで実行されたときに、デジタル回路を設計する方法を前記システムに実施させる、実行可能なコンピュータプログラム命令を格納するマシン可読媒体であって、前記方法が、
シングルチャネル回路である第１の設計を受け取るステップと、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成するステップと
を含む媒体。
【請求項２３】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項２２に記載の媒体。
【請求項２４】
前記方法が、前記時間多重化マルチチャネル回路をリタイミングするステップをさらに含む、請求項２２に記載の媒体。
【請求項２５】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項２４に記載の媒体。
【請求項２６】
前記方法が、
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別するステップと、
前記パイプラインレジスタの組を除去するステップとをさらに含む、請求項２２に記載の媒体。
【請求項２７】
前記方法が、
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入するステップをさらに含む、請求項２２に記載の媒体。
【請求項２８】
前記変形するステップが、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成するステップを含む、請求項２２に記載の媒体。
【請求項２９】
前記変形するステップが、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成するステップをさらに含む、請求項２８に記載の媒体。
【請求項３０】
前記変形するステップが、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成するステップをさらに含む、請求項２８に記載の媒体。
【請求項３１】
前記変形するステップが、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換えるステップをさらに含み、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項２８に記載の媒体。
【請求項３２】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項３１に記載の媒体。
【請求項３３】
前記チャネル固有要素がチャネル固有順次要素である、請求項３１に記載の媒体。
【請求項３４】
前記方法が、
非チャネル固有順次要素を識別するステップをさらに含む、請求項３３に記載の媒体。
【請求項３５】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項３４に記載の媒体。
【請求項３６】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項３３に記載の媒体。
【請求項３７】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項３３に記載の媒体。
【請求項３８】
前記方法が、
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定するステップをさらに含む、請求項３３に記載の媒体。
【請求項３９】
前記変形するステップが、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換えるステップを含み、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項２２に記載の媒体。
【請求項４０】
前記対応する要素が順次アドレス指定される、請求項３９に記載の媒体。
【請求項４１】
前記対応する要素が順次アドレス指定される、請求項３９に記載の媒体。
【請求項４２】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを含む、請求項３９に記載の媒体。
【請求項４３】
デジタル回路を設計するデジタル処理システムであって、
シングルチャネル回路である第１の設計を受け取る手段と、
前記シングルチャネル回路を自動的に変形して、時間多重化マルチチャネル回路である第２の設計を生成する手段と
を備えるデジタル処理システム。
【請求項４４】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項４３に記載のデジタル処理システム。
【請求項４５】
前記時間多重化マルチチャネル回路をリタイミングする手段をさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４６】
クロック周波数を上げるために、前記時間多重化マルチチャネル回路がリタイミングされる、請求項４５に記載のデジタル処理システム。
【請求項４７】
前記時間多重化マルチチャネル回路内のパイプラインレジスタの組を識別する手段と、
前記パイプラインレジスタの組を除去する手段とをさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４８】
前記時間多重化マルチチャネル回路にパイプラインレジスタの組を挿入する手段をさらに備える、請求項４３に記載のデジタル処理システム。
【請求項４９】
前記変形する手段が、
複数のチャネルによる前記第１の設計の論理要素へのアクセスを時間多重化するためにマルチステートの有限ステートマシン（ＦＳＭ）を生成する手段を備える、請求項４３に記載のデジタル処理システム。
【請求項５０】
前記変形する手段が、
前記第１の設計の入力ラインへの、前記複数のチャネル用の複数の入力を時間多重化するために、多重化回路を生成する手段をさらに備える、請求項４９に記載のデジタル処理システム。
【請求項５１】
前記変形する手段が、
前記第１の設計の出力ラインからの信号を、複数のチャネル用の複数の出力に時間多重分離するために、多重分離回路を生成する手段をさらに備える、請求項４９に記載のデジタル処理システム。
【請求項５２】
前記変形する手段が、
前記第１の設計内のチャネル固有要素を、対応する複数の要素に置き換える手段をさらに備え、前記対応する複数の要素のそれぞれが、前記ＦＳＭの状態に応じて前記複数のチャネルの１つに対してアクセスされる、請求項４９に記載のデジタル処理システム。
【請求項５３】
前記チャネル固有要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを備える、請求項５２に記載のデジタル処理システム。
【請求項５４】
前記チャネル固有要素がチャネル固有順次要素である、請求項５２に記載のデジタル処理システム。
【請求項５５】
非チャネル固有順次要素を識別する手段をさらに備える、請求項５４に記載のデジタル処理システム。
【請求項５６】
前記非チャネル固有順次要素がパイプラインレジスタの組を含む、請求項５５に記載のデジタル処理システム。
【請求項５７】
前記チャネル固有順次要素が、複数の移動順次要素のカスケード接続に置き換えられる、請求項５４に記載のデジタル処理システム。
【請求項５８】
前記チャネル固有順次要素が、前記ＦＳＭの状態に応じてアドレス指定される複数のメモリ要素に置き換えられる、請求項５４に記載のデジタル処理システム。
【請求項５９】
順次要素の、いくつかのフィードフォワード切断集合を、非チャネル固有の順次要素として決定する手段をさらに備える、請求項５４に記載のデジタル処理システム。
【請求項６０】
前記変形する手段が、
前記第２の設計を生成するために、前記第１の設計内の順次要素を、対応する要素に置き換える手段を備え、前記対応する要素が、複数のチャネルからの信号を処理するタイミングに従って前記第２の設計内で順次アクセスされる、請求項４３に記載のデジタル処理システム。
【請求項６１】
前記対応する要素が順次アドレス指定される、請求項６０に記載のデジタル処理システム。
【請求項６２】
前記対応する要素が順次アドレス指定される、請求項６０に記載のデジタル処理システム。
【請求項６３】
前記順次要素が、
ａ）定数と、
ｂ）ランダムアクセスメモリ（ＲＡＭ）要素と、
ｃ）読み出し専用メモリ（ＲＯＭ）要素と、
ｄ）レジスタと、
ｅ）フリップフロップと、
ｆ）負遅延レジスタとのうちの１つを備える、請求項６０に記載のデジタル処理システム。
【請求項６４】
デジタル回路を設計する方法であって、
シングルチャネル回路である第１の設計を受け取るステップと、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成するステップと、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用するステップと
を含む方法。
【請求項６５】
前記情報が、折り畳みの集合の情報を含む、請求項６４に記載の方法。
【請求項６６】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項６４に記載の方法。
【請求項６７】
デジタル処理システムで実行されたときに、デジタル回路を設計する方法を前記システムに実施させる、実行可能なコンピュータプログラム命令を格納するマシン可読媒体であって、前記方法が、
シングルチャネル回路である第１の設計を受け取るステップと、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成するステップと、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用するステップと
を含む媒体。
【請求項６８】
前記情報が、折り畳みの集合の情報を含む、請求項６７に記載の媒体。
【請求項６９】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項６７に記載の媒体。
【請求項７０】
デジタル回路を設計するデジタル処理システムであって、
シングルチャネル回路である第１の設計を受け取る手段と、
前記第１の設計のシングルチャネル回路の集合体と、シングルチャネル回路の前記集合体の中の並列処理を示す情報とを生成する手段と、
時間多重化マルチチャネル回路である第２の設計を生成するために、前記情報を用いて、シングルチャネル回路の前記集合体に折り畳み変形を適用する手段と
を備えるデジタル処理システム。
【請求項７１】
前記情報が、折り畳みの集合の情報を含む、請求項７０に記載のデジタル処理システム。
【請求項７２】
前記シングルチャネル回路である第１の設計が、少なくとも１つの負遅延レジスタを含む、請求項７０に記載のデジタル処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【公表番号】特表２００７−５２４８９９（Ｐ２００７−５２４８９９Ａ）
【公表日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願番号】特願２００６−５０９５７２（Ｐ２００６−５０９５７２）
【出願日】平成１６年４月２日（２００４．４．２）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１０００６
【国際公開番号】ＷＯ２００４／０９０７５８
【国際公開日】平成１６年１０月２１日（２００４．１０．２１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
２．ＷＩＮＤＯＷＳ
３．イーサネット
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
【公表日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願日】平成１６年４月２日（２００４．４．２）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１０００６
【国際公開番号】ＷＯ２００４／０９０７５８
【国際公開日】平成１６年１０月２１日（２００４．１０．２１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
２．ＷＩＮＤＯＷＳ
３．イーサネット
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
[ Back to top ]