信号処理
【課題】信号を処理する方法を提供すること。
【解決手段】信号データ値および畳み込みフィルタ係数値を、畳み込み値を計算するために使用される一組のプロセッサ（ｃutil）中の対象プロセッサ（ｃt）にロードするためのプロセス。係数値はｃutilにマッピング（１５０）される。データ値と係数値のインターリーブ（１６０）がｃtについて決定される。係数値がｃtにロードされ、データ値がｃtにロードされ、それによって畳み込み値の計算（１７０）に参加するようｃtを準備する。
【解決手段】信号データ値および畳み込みフィルタ係数値を、畳み込み値を計算するために使用される一組のプロセッサ（ｃutil）中の対象プロセッサ（ｃt）にロードするためのプロセス。係数値はｃutilにマッピング（１５０）される。データ値と係数値のインターリーブ（１６０）がｃtについて決定される。係数値がｃtにロードされ、データ値がｃtにロードされ、それによって畳み込み値の計算（１７０）に参加するようｃtを準備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して信号処理に関する。
【背景技術】
【０００２】
積分変換
多くの既存のシステムおよび新規のシステムは、基本となるシステムを記述する数学に基づいて適切にプログラムされた近代的デジタルプロセッサを使用して解析可能である。例えば、今日この種の解析は、電気回路、光学器械、機械的機構、およびその他の多くのシステムなどの、線形時不変システム（linear time-invariant systems）を解析するためにますます有用である。
【０００３】
数学、およびこれを広範囲に用いる多くの分野、例えば今日の科学と工学のほとんどの部門において、用語「変換（transform）」は、ある種の方程式による解析技術のクラスを言及するために用いられる。変換の概念は、特定の関数が他の関数を引数として持つ関数空間の研究を主として扱う数学の関数解析（functional analysis branch of mathematics）の部門に由来する。このため変換は個々の方程式にも方程式のセット全体にも用いることができ、変換のプロセス（process of transformation）とは、ある定義域で表される元の方程式または複数の方程式を、他の別の定義域で表される他の１つまたは複数の方程式に１対１でマッピングすることである。
【０００４】
変換を行う動機は、しばしば単純である。元の表現では解くのが難しいが、１つまたは複数の他の表現によればより簡単に解決可能である方程式は多い。このため変換が行われ、解が見出され、それから逆変換を行って、その解を元の定義域に戻してマッピングすることができる。積分変換の一般的な形態は次のように定義される。
【０００５】
【数１】
【０００６】
ここでＫ（α，ｔ）は、しばしば変換の「積分核（integral kernel）」と呼ばれる。
【０００７】
ラプラス変換
ラプラス変換は、方程式（１）で定義されるある種の変換のサブセットであり、しばしば特に有用である。システムへの入力またはシステムからの出力が単純な数学または関数で表現されているときに、ラプラス変換は、システムの挙動を簡単に解析できる代替の関数の記述を与えることができる。ラプラス変換の一般的な形態は次のように定義される。
【０００８】
【数２】
【０００９】
ここで方程式（１）から積分の境界および積分核は、ａ＝０で、ｂは∞に置き換え、Ｋ（α，ｔ）＝ｅ-stとして再定義されている。ラプラス変換のｆ（ｔ）への適用は、ｓが十分に大きく、ある条件が満たされる場合のみ可能であるが、これらの条件は通常、ｆ（ｔ）が、実際に見出されるほぼ任意の有用な関数の関数形をとることができるほど十分に柔軟である。
【００１０】
畳み込み定理（CONVOLUTION THEOREM）
ある関数、例えばＦ（ｓ）が単一の既知の関数の変換ではなく、それぞれが、既知のｆ（ｔ）またはｇ（ｔ）の関数の変換結果である２つの関数の積として表せるのは、よくあることである。すなわち、
【００１１】
【数３】
【００１２】
である。ここでｇ（ｔ）は、ｆ（ｔ）と同じ条件を満足しなければならない。Ｆ（ｓ）、ｆ（ｔ）、およびｇ（ｔ）のこの結び付きから、次の関係が成立する。
【００１３】
【数４】
【００１４】
これはしばしば「畳み込み（重積分）定理（convolution theorem）」と呼ばれる。
【００１５】
畳み込み定理の数値近似
畳み込み定理の結果は変数が１つのみの積分変換となることが観察されている。そのため変数が１つのみの積分の数値近似の技術を適用することができる。
【００１６】
積分表現（integral representation）とリーマン和による表現（Riemann sum representation）の間に次の等式が成り立つ。（ここで後者は、特にデジタル回路を用いて行われる数値近似の技術での使用に適切である。）
【００１７】
【数５】
【００１８】
ここでそれぞれのｃt-kおよびｃkはｋ番目のサブ・インターバルから任意に選択される。実際には、方程式（５）の等式の右項は、極めて小さなΔγを用い、選択された計算法およびΔγの値に応じて幾分の誤差があることを了解することによって、近似される。
【００１９】
【数６】
【００２０】
ここでｍは、結果としての合計（resultant sum）で表すことができる正確さの次数（期待可能な精度の桁数でもある）を表し、およびΟは、従来の数学のコンテキストにおけるビッグオー記法（big-O notation）である。
【００２１】
デジタル信号処理
先に述べたように、畳み込み（convolution）を使用することが利点となり得る変換には、重要な応用における既存および潜在的な用途がある。例えばデジタル信号処理（ＤＳＰ：digital signal processing）は幅広く、ますます使われており、ＤＳＰのこの種の重要な用途の１つにデジタル・フィルタリングがある。数学的関数として表現可能な任意のフィルタリングがデジタル・フィルタの使用で実現でき、これは、近年のＤＳＰの仕事のまさに出発点の１つである。例えば、信号からサンプル抽出されたデータ値に関するデジタル・フィルタリングは、信号の不要部分の除去や信号の必要部分の抽出を可能にする。
【００２２】
有限インパルス応答（ＦＩＲ：finite impulse response）および無限インパルス応答（ＩＩＲ：infinite impulse response）は、今日、ＤＳＰの用途に使用される２つの主要なデジタル・フィルタであるが、その中ではＦＩＲフィルタがより一般的である。
【００２３】
ＦＩＲフィルタは、用いる上での優位性があると通常考えられているが、その理由は、内部フィードバック（これは例えば、ＩＩＲフィルタが無限にインパルスに応答する原因となる）を必要としないためである。その名称における「有限」という言葉からもＦＩＲフィルタの別の利点が示唆される。この種のフィルタからのインパルスは最終的にゼロとなり、使用される逐次加算計算中のエラーが伝搬されることがない。すなわちエラー項が計算プロセス全体で一定に保たれる。これはＩＩＲフィルタに対する明確な利点であり、ＩＩＲフィルタでは、例えば追加の逐次出力加算毎にエラーが潜在的に成長する可能性がある。
【００２４】
残念ながら多くの用途において、デジタル・フィルタの大きな限界は、そのスピードが数値計算に用いられるプロセッサまたは複数のプロセッサのスピードによって制限されることである。例えば、高速のフィルタリング速度が必要な場合、これは、高価な、デジタル・フィルタを実装するのに必要なハードウェアを高価にしたり、あるいは単純に実装不可能にしたりする可能性がある。ほとんどすべての用途について、またほとんどの電子的システムに当てはまるが、用いられる速度が速くなればなるほど、電磁雑音の抑制および放熱などの、同時発生する現象に対応することも難しくなる。
【００２５】
デジタル・フィルタリングの事例を越えて一般化すると、ＤＳＰは通常、少なくとも１つの処理される信号のサンプリングを前提にする。サンプリング速度は、ある特定の連続信号についての連続信号を、離散信号（discrete signal）に変換する、単位時間当たりのサンプル数として定義される。連続信号を離散信号に変換する理由は、変調、符号化、および量子化にかかわる用途など、数多くある。サンプル速度は、より一般的にはヘルツ（Ｈｚ）（測定における周波数の単位）で表され、これは波長（λ）（時間の単位で、λ＝Ｈｚ-1および逆もまた同様）と等価である。
【００２６】
連続信号が元の関数を復元しようとしてサンプルすることが可能な方法には、アンダー・サンプリング、ナイキスト速度サンプリング、およびオーバー・サンプリングの３つの方法がある。
【００２７】
連続信号のアンダー・サンプリングは、元の信号から関連する情報のすべてを取得することが可能とは限らないために、しばしば最良の選択ではない。しかし元の信号の復元が重要でない場合は、アンダー・サンプリングによると格納されるデータが減り、サンプリング・プロセスを大幅に速めることができる。
【００２８】
多くの場合、好ましいのはナイキスト速度サンプリングであり、その理由は、その後に特定の信号を正確に復元することを可能にするからである。このサンプリング周期（「ナイキスト速度」と称される）は、サンプリングする信号の帯域幅の２倍を超えていなければならず、この信号は、帯域制限される必要がある。つまり信号は、ある有限の周波数以上でゼロのフーリエ変換やパワー・スペクトラム密度を有することが確定された信号であることを意味する。
【００２９】
オーバー・サンプリングは、３つのサンプリング法の中で最も非効率で無駄が多いが、元の信号の復元が常に可能し、スピードが重要でない場合は利点となり得る。
【００３０】
サンプリングの重要性と、それがＤＳＰおよびＤＳＰを用いるシステムにしばしばどのような制約を及ぼすかについて、さらに述べる。
【００３１】
並列アルゴリズム
計算機（ＤＳＰおよびその他の多くの用途に用いられる計算機）に関連するハードウェアの最近の構成上の変化が起こるまでは、すべてのコンピュータに実装されるアルゴリズムは、連続的にまたは逐次実行されるものと考えられていた。すなわち、１つの作業のみが任意の所与の時間に適時に実行可能であった。この考えから、連続したタスクをより短い時間で実行できるようにするためにますます高速のプロセッサを作製することになった。しかし先に述べたように、この種のプロセッサは、実現可能な処理パワーが現在限界に達しつつある。今日では、この限界は、ハードウェアの速度向上からアルゴリズムの速度向上に力点が移りつつある。
【００３２】
アルゴリズムの速度向上の１つの手法は、並列処理の使用である。アルゴリズムの多くは、それが、今もなお、実行するためのハードウェアに制限されることがあるとはいえ、多くのアルゴリズムがそれ自体ある程度の並列化に極めて適している。別の他のアルゴリズムでは、すべての面で並列的に実行される場合、より速い速度が達成できる。この点に関連して、並列に達成可能なアルゴリズムの率（Ｔp）、連続的に達成可能なアルゴリズムの率（ＴS）、および使用可能な並列プロセッサの数（Ｎ）を与えたとき、並列計算で起こり得る最大速度上昇率（Ｓ）を決定するために、アムダールの法則がしばしば用いられる。アムダールの法則は次のように表すことができる。
【００３３】
【数７】
【００３４】
アルゴリズムの大きな部分を高速化する方が、アルゴリズムの小さな部分を大きく高速化するよりも良いということが幅広く受け入れられ、概してそのような命題を支持するように考えられている。この理由は方程式（７）中において、また収穫逓減の法則を適用することにより。理解できる。
【００３５】
整数プログラミング
線形計画法（ＬＰ：linear programming）の基本の把握は、整数プログラミング（ＩＰ：integer programming）の理解に役立ち、これは、以下述べる理由のために取りこまれた。ＬＰの問題は、線形な目的関数を有する最適化の問題である。この種の問題は、例えばネットワークのフローの用途などでしばしば発生する。
【００３６】
ＬＰ問題は、今日の計算に関するリソースが与えられるとしばしば容易に解決可能である。しかし、この顕著な例外は、ＬＰが、変数の値を整数値のみに限定するという制約があること、すなわち、ＬＰ問題が整数プログラミング（ＩＰ：integer programming）問題であることである。ＬＰ問題を解決するための技術は、ＩＰ問題に、同じ形では適用できないことがしばしばであり、多くの場合これらの技術は、ＩＰ問題のすべてに適用できるわけではない。そのためにＩＰ問題は、より解決が難しくなる。
【００３７】
さらに問題が、ＬＰ問題ではなくＩＰ問題として取り扱われる場合、ＩＰ問題としてその問題を解くのに必要な計算機能力は、ＬＰ問題としてその問題を解くのに必要な計算機能力と比べて、指数的に増加する。そのために４０以上の変数を持つＩＰ問題は、その問題中の変数の数を効果的に最も少なくするのに利用可能な何らかのＩＰ問題の構造（structure）が存在しない限り、今日利用可能な計算機能力では解くのは不可能だとほとんどの研究者が考えている。このためにＩＰ問題の解を開発するのに費やされる時間のほとんどは、問題の構造を利用する方法を見つけて、変数の数を減らし、適時のコンピュータの解決策を可能にすることに向けられている。しかし、それゆえに最適化問題を、ＬＰ問題を超えたＩＰ問題と分類することには大きなトレードオフがある。ＩＰ問題は所与の状況をより現実的にモデル化できるかもしれないが、ＩＰ問題に存在するそれは、あるため解決不能の方程式のセットに行き着く可能性がある。対照的にＬＰ問題は、潜在的な状況のモデル化するためのＩＰ問題の対応物よりも現実性が薄いことが多いが、通常は解決可能であり、速やかに解決することができる。
【発明の開示】
【発明が解決しようとする課題】
【００３８】
そのために、信号を処理するために、例えば特にＤＳＰに使用される数値畳み込み計算を実行するために用いるシステムを改善することで、これらの用途および関連するタスクを、より高速でより経済的に、かつ基本のシステムや周辺システムを損なう影響を減らしつつ実行することが可能となるであろう。
【課題を解決するための手段】
【００３９】
本発明の一態様は、複数の信号データ値および複数の係数値を、畳み込み値を計算するための使用される一組のプロセッサ（ｃutil）の１つである対象プロセッサ（ｃt）に、ロードするプロセスである。複数の係数値はｃutilにマッピングされる。その後ｃt中の複数のデータ値と複数の係数値のインターリーブが決定される。ｃtに前記複数の係数値がロードされ、ｃtに前記複数のデータ値がロードされ、それによって、信号データ値の処理に参加するようｃtを準備させる。ある例では、複数の係数値は、畳み込みフィルタの複数の係数値であり、このプロセスは、複数のフィルタ係数値および複数のデータ値の畳み込みを計算する。
【００４０】
本発明の他の態様は、例えば複数の信号データ値、および畳み込みフィルタ係数値とすることができる複数の係数値に基づいて畳み込みを計算する、信号を処理するシステムである。使用される複数のプロセッサからなる一組のプロセッサ（ｃutil）が与えられ、ここでは、各プロセッサは、順番に、所与の時点で対象プロセッサ（ｃt）と見なすことができる。ロジックが、複数の係数値をｃutilにマッピングする。あるロジックがｃt中の複数のデータ値と複数の係数値のインターリーブを決定する。あるロジックがｃt中の複数の係数値をロードする。またロジックがｃt中の複数のデータ値をロードする。これは、ｃtが、その信号処理に、例えば畳み込み値の計算に参加するように準備させる。
【００４１】
本発明はまた、コンピュータのアレイ上で実行すると、そのアレイに発明の一態様のプロセスを実施することを引き起こすコンピュータ・プログラムを提供する。このコンピュータのアレイは、単一の半導体のダイ上に存在するとすることができる。プログラムは、例えば、記録媒体、電気信号とすることができる信号、またはメモリ・デバイスなどの、キャリア上に存在することができる。
【００４２】
本発明のこれらのおよび他の目的および利点は、本明細書に記載され図面中の各図に示された、本発明を実施する現在知られた最良の形態と好ましい実施形態の産業上の利用可能性の記載を読むことにより、当業者には明瞭になろう。
【発明を実施するための最良の形態】
【００４３】
本発明の目的および利点は、以下の詳細説明、ならびに添付図面の各図から明らかになるであろう。添付図面の各図においては、類似の参照符号が、類似または同様の要素またはステップを表すために用いられている。
【００４４】
本発明の好ましい実施形態は、複数のコンピュータ・プロセッサにより、実行される畳み込み計算のシステムである。本明細書において様々な図に示されるように、特に図１ａ〜ｂに示されるように、本発明の好ましい実施形態を、一般参照符号１００で示す。
【００４５】
図１ａ〜ｂは、本発明による畳み込み計算システム（convolution calculation system）（ＣＣＳ１００）がどのようにセットアップ演算、通常作業演算（formal work operations）、および要約した演算（wrap-up operations）を実行できるかについて、概略を模式的に示すブロック図である。
【００４６】
図１ａに示すように、ホスト・プロセッサ１１２を用いて、信号データ値および畳み込み係数フィルタ値を、ターゲット・アレイ１１４中の複数のプロセッサ、コア、またはノードにマッピングし、信号データ値および係数フィルタ値に基づいてインターリーブのターゲット・アレイ１１４へのロードを開始し、処理結果をターゲット・アレイ１１４から受け取る。
【００４７】
ホスト・プロセッサ１１２は、図１ａに示されるような単一の個別システムであることができる。しかし当業者は、以下を理解すれば、ホスト・プロセッサ１１２は複数の個別システムであることも可能であることをさらに理解しよう。さらに、説明するように、ホスト・プロセッサ１１２はターゲット・アレイ１１４の一部とすることもできる。しかし、通常、ホスト・プロセッサ１１２は、通常のパーソナル・コンピュータ（ＰＣ）またはワークステーションである。
【００４８】
ターゲット・アレイ１１４もまた多くの形態をとり得るが、具体的にはカリフォルニア州クパチーノ所在のＩｎｔｅｌｌａｓｙｓ Ｃｏｒｐ．のＳＥＡｆｏｒｔｈ（ＴＭ）製品などの、マルチ・コアまたはマルチ・ノード、単一ダイの集積回路デバイスとすることができる。
【００４９】
図１ｂは、ＣＣＳ１００の作業の主要なステージを示す。マッピング・ステージ１５０で、畳み込みデジタル・フィルタ値が、ターゲット・アレイ１１４の使用可能なプロセッサ、コア、またはノードに、これらをより効果的に用いるように、マッピングされる。次いで、インターリーブ・ステージ１６０で、インターリーブが、ターゲット・アレイ１１４のプロセッサ、コア、またはノードに効率的に係数をロードするよう構築される。計算ステージ１７０で、畳み込みを実行する。（ハイブリッドのＦＩＲの例が、以に示される。）勿論、信号データ値のロードおよび処理結果のアンロードもまた行われるが、これらは図１ｂにおいてステージとして示されない。
【００５０】
図２（背景技術）は、ターゲット・アレイ１１４に使用されているＳＥＡｆｏｒｔｈ２４Ａデバイスの主な細部を全体的に示す線図である。畳み込み計算の準備、およびその後の実際の使用にかかわるこの態様に、焦点を当てるために、図２において、多くの、重要でない周辺の構成要素は省略されたり、概略的に示されたりしている。しかし当業者は、実際の実施形態の作動ではこの種の要素が存在し、これらは、通常その性質についてはまったく通常通りであることを理解しよう。
【００５１】
図２のシステムは、アレイ１１４と、入力デバイス１６１と、出力デバイス２２１とを備える。入力デバイス１６１は、処理される信号から、畳み込みが実行されることになる入力データの値を与える。この入力データ値は処理される信号のサンプルである。出力デバイス２２１は処理されたデータ値をアレイ１１４から受け取る。
【００５２】
図２で理解されるように、ＳＥＡｆｏｒｔｈ２４Ａのデバイスは、データ・バス１８を介して互いに通信する２４個のコア（集合的にはコア１６、個別的にはコア１６ａ〜ｘ）を備える。（本明細書では用語「コア」が用いられているが、ＳＥＡｆｏｒｔｈ２４Ａのようなデバイス中のプロセッサについて述べるときには用語「ノード」も同様に適切であり、用語「プロセッサ」も一般的に正しい。）
必ずしも必要ではないが、一般的に、１つのコア１６（例えば図２のコア１６ａ）が、データ入力タスクの処理専用にされ、別のコア１６（図２のコア１６ｘ）がデータ出力タスクの処理専用にされる。したがって本明細書にある２４個のコア１６中２２個が、畳み込み計算に通常にかかわる作業の実行に使用可能である。一方、１個のコア１６がデータの入力と出力の両方の専用にされることも可能である、複数のコア１６が他のタスク専用にされることも可能である。例えばホスト・プロセッサ１１２が、１つまたは複数のコア１６内に実装されることも可能である。
【００５３】
本発明のＣＣＳ１００は、畳み込みの性質と、ターゲット・アレイ１１４で畳み込みを効率的に実行するために何をしなければならないかの性質、とに起因して、計算ステージ１７０を実行する前の入力に大きく依存している。これらの入力と用語について下に一般的に述べる。
【００５４】
用語集
概して、ｃは、ターゲット・アレイ１１４中の複数のコア１６を表す変数であり、
ｃtotal＝ターゲット・アレイ１１４中に存在するコア１６の総数（例えば図２中の例では２４）、
ｃavail＝畳み込み計算の実行のためのマッピングに使用可能なコア１６の数（例えば図２中の例では２２）、
ｃutil＝複数のフィルタ値のマッピングに使用されるコア１６の数（すなわちマッピング・ステージ１５０が決定しようとする値）、および
ｃt＝所与の時点における、考察対象の、ｃutilから選ばれる対象コア１６。
【００５５】
一般的に、ｎはデジタル畳み込みフィルタ値の量を表す変数であり、
ｎactual＝ｃtにマッピングされたフィルタ値の実数、
ｎest＝ｃutilの一部であるコア１６のそれぞれにマッピングされたフィルタ値の予測数；
ｎtaps＝所与のコア１６に実際にマッピングされたフィルタ値（「タップ」）（すなわちマッピング・ステージ１５０が決定しようとするｃutil毎に１個の、複数の値からなる集合）の数、および
ｎmax＝任意の特定のコア１６に対する、複数の信号データ値（または係数フィルタ値）のうちの最大マッピング値（すなわちｎmaxはｎtapsの集合の要素であり、具体的には最大値を有する要素である。）
以下が定義される。
Ｓは、サンプル速度、
Ｌは、積分核の時間窓の長さ、
ｔは、ターゲット・アレイ１１４の２つの数を乗じるために必要な時間、および
Ａは、データ値およびフィルタ値の格納に使用される、コア１６中のメモリの使用可能なワード。
【００５６】
ｃに関する簡潔な関係式が次のように論理的に導かれる。例えば、０＜ｃutil≦ｃavail≦ｃtotalであることは容易に分かり、このすべてが整数値である。次いで０＜ｃutil＜ｃavail≦ｃtotalの事例は、最適値ではないかもしれないが、それにもかかわらず現実世界の用途では起こる可能性がある。つまり、フィルタ値が何もマッピングされておらず、そのために畳み込み計算の通常プロセス（formal process）にも使用されない１つまたは複数のコアを備えた方が、より効率的である場合が、よくある。
【００５７】
同様に、ｎに関する関係式もまた次のように論理的に導かれる。例えば、０≠ｎtotalおよび０＜ｎtaps≦ｎest≦ｎtotalであることが分かり、ここでｎtapsとｎtotalは整数値となる。（そしてｎestも整数値となるよう制限することになる。）次いで、ｎtaps＝ｎtotalの場合（すなわち全フィルタ値が、唯一のコアにマップされる場合）が認識されるべきである。本発明のＣＣＳ１００は、最も効率的な解である事例を網羅するが、ＣＣＳ１００の利点はｎtaps＜ｎtotalがより最適な解である事例において具体的に実現される。やはり、事実上、既に説明した点を繰り返すと、一部のコアについて０＝ｎtapsである現実社会の用途に、直面することになる。
【００５８】
定義された値に関する簡潔な関係もまた述べることができる。本明細書ではＳの値を変数として扱っている。すなわち単位時間当たりでより多くのまたはより少ないサンプルが集められてよい。本明細書ではＬの値を変数として扱っていない。ｔの値は、ターゲット・アレイ１１４のハードウェアで指定される最小値を元来有するため、固定される。（そして効率的なプログラミングがなされて、最小値が実現されていると推定する。）Ａの値は減らすことはできるが増やすことはできない。これは、データまたはフィルタ値の格納にＲＡＭおよびＲＯＭのいずれかが使用される場合、ＲＡＭおよびＲＯＭ中の使用可能なワード数によってメモリのワード数が制限されるためである。しかしＡのすべて用いなければならないという要件はない。
【００５９】
図３は、本発明のＣＣＳ１００のマッピング・ステージ１５０の例示的実施形態がどのように実行され得るかを示すフローチャートである。ステップ３３０でマッピング・ステージ１５０が開始する。次いで、一組の入力がホスト・プロセッサ１１２に与えられる。特に、ステップ３３２でサンプル速度（Ｓ）が与えられる。ステップ３３４で、積分核の時間窓の長さ（すなわち持続時間）（Ｌ）が与えられる。ステップ３３６で、ターゲット・アレイ１１４の２つの数を乗じるために必要な時間（ｔ）が与えられる。およびステップ３３８で、任意の特定のコア１６に対する信号データ値（または係数フィルタ値）の最大マッピング値（ｎmax）が与えられる。
【００６０】
ステップ３４０で、ステップ３３２〜３３６の入力が有効か否かが決定される。これらの入力が任意の点で無効の場合は、ステップ３４２が続き、マッピング・ステージ１５０を中止するかを決定する。中止すると決定されれば、ステップ３４４が続き、マッピング・ステージ１５０は停止する。一方、中止しないと決定されれば、マッピング・ステージ１５０は図示のようにステップ３３０に復帰する。
【００６１】
さらにステップ３４０での他の選択肢を述べると、入力が一括して有効と見なされると、ステップ３４６が続き、並列畳み込みアルゴリズムの実行に使用されるコア１６の数（ｃutil）が計算される。
【００６２】
まずｎtapsが計算される。
【００６３】
（８） ｎtaps＝Ｓ＊ｔ、
次いでｎmaxが決定される。ユーザが与える入力（ステップ３３８）であっても計算で算出されてもよい。
【００６４】
【数８】
【００６５】
次いでノード毎のタップの予測数（ｎest）が計算される。
【００６６】
（１０） ｎest＝ｍｉｎ（ｎtaps，ｎmax）、
次いで、ここでノード毎のタップの数（ｎest）が既知であるため、これらのタップがマッピングされることが可能なコアの数（ｃutil）が計算される。
【００６７】
【数９】
【００６８】
ここでｃutilはｃutil≦ｃavail≦ｃtotalとの要件を満たす必要があることに留意されたい。この要件が満たされない場合は、Ｌの値および／またはｎestの値をＬの値を減らすこと、および／またはｎestの値を増やすことによって改変してよい。Ｌを改変することはユーザ入力によりなされる。一方、ｎestの変更はプログラムに基づいてなされることができる。ｎestの値はｎtapsおよびｎmaxの関数であり、これらは両方減らすことができる。このことは、ｎmaxの場合は、ＲＡＭ／ＲＯＭ中で使用可能なワードの総数（Ａ）未満の数を使用することにより可能であり、ｎtapsの場合は（Ｓ≧ｔの関係を保ちながら）Ｓおよびｔの一方または両方を減らすことにより可能である。
【００６９】
図３についてさらに述べると、ステップ３４８でｃutilが整数値であるかが決定される。つまり、方程式（１１）に剰余が生じなかったかということである。
【００７０】
剰余がない場合は、タップのコア１６に対する均一なマッピングが可能であり、これを用いることにより最適の効率が得られる。この場合ステップ３５０が続き、ｎestの値がｃutilのすべてに使用される。次いでステップ３５２が続き、ｃutil中のそれぞれのコア１６に対してインターリーブ・ベクトルがマッピングされる。（インターリーブ・ベクトルについては、いずれ説明する。）ステップ３５４で通常畳み込み計算（formal convolution calculation）をすすめることができる。
【００７１】
今述べたようにすすめると、ステップ３５２からステップ３５４は明らかに一般的事例に対する稀な例外であり、Ｌおよびｎestの除法が負ではない整数の結果をもたらす場合である。ステップ３４８に剰余がある場合、タップのコア１６に対する不均一なマッピングが必要になる。ステップ３５６でこれが実行され、ここでまず可能な最も均一なマッピングを試みる。マッピングの不均一性の性質から、３つ以上でなくとも、少なくとも２つの異なるｎactualの値が必要となるだろう。
【００７２】
ステップ３５６で、発明者にとり好ましい初期の手法はｎactualの値をコア１６のｃutil−１に使用し、異なるマッピングをｃutil中の（ｃ番目）の他のコア１６で使用することである。次いでｃ番目コアはマッピングｍactualを有し、これは以下で示される。
（１２） ｍactual＝Ｌ−ｎest（ｃutil−１）、
ここでｍactual＜ｎactualである。残念ながら、初期の手法もこの型のマッピングを使用するある用途には非効率的である可能性がある。（留意すべきことだが、本明細書に述べる手法は指針を与えるにすぎない。その理由は、このような整数プログラミング（ＩＰ）問題の性質が解を整数の処理結果に制限し、使用可能な解法を大きく制限するためである。）
畳み込み方法はｃutil中のコア１６に制限されている、という事実により、これらのみが通常計算（formal calculation）中に使用されることになるので、ｃutil中のそれぞれのコア１６に対するマッピングが可能な限り均一に近いことは必須である。コア１６間の、接近した均一性は、これらのコア１６のスリープ時間を、コア１６毎の最大タップ数未満に制限する。
【００７３】
ここでマッピングを考える他のやり方は、アムダールの法則に従い、たとえ最速部分の性能が低下する可能性があっても最も遅い部分の性能を向上させることである。不均一なマッピングがここで要求されるとすれば、マッピング・プロセス中にｎestの値が１より大きい値となることを期待するのは合理的である。例えばＬ＝９９およびｎest＝２４とすれば、ｃutil＝５である。この事例は、Ｌおよびｎestが除されたときに剰余が出る。上述した第１の方法を用いると、この場合のマッピングは２４、２４、２４、２４、および３となるだろう。しかしながら今述べた方法を用いれば、より望ましいマッピングは２０、２０、２０、２０、および１９となるだろう。（勿論、同じ全体の処理結果をもたらす他のマッピングが４つ存在する。例えば、１９、２０、２０、２０、および２０））この種の事例では、コア１６を最適にマッピングする包括的なアルゴリズムの概要を説明するのは非常に困難であり、したがって、ここでの骨子は、Ｌおよびｎestの除法が処理結果がゼロではない剰余をもたらしても、このマッピングにおいてある程度の効率性を保持するのはなお可能であり、ｃutil中のコア１６のｎestの値が可能な限り均一に近いときに、この効率性は最大化されるということである。
【００７４】
ステップ３５６の後、ステップ３５８が続き、ｃutil中の各コア１６に対してインターリーブ・ベクトル（インターリーブ・ベクトルについては、いずれ説明する。）がマッピングされ、ステップ３５４で通常畳み込み計算をすすめてよい。
【００７５】
総括すると、マッピング・ステージ１５０はここで完了し、それぞれのコア１６に対する複数のタップの実数の値は既知であり、ＣＣＳ１００全体の次段階、つまりインターリーブ・ステージ１６０でのインターリーブ・ベクトルの決定を実行することができる。図３は、インターリーブ・ステージ１６０はステップ３５２またはステップ３５８で表されており、インターリーブ・ベクトルはｃutil中のコア１６に対して（すなわち通常畳み込み計算（formal convolution calculations）に使用されるそれぞれのコアに対して）マッピングされ、ステップ３５４は計算ステージ１７０である。
【００７６】
簡潔にいえば、インターリーブ・ステージ１６０での目標は、計算ステージ１７０で畳み込みを実行するために、サンプリングされた信号データ値（履歴値としても知られる）と畳み込みデジタル・フィルタ係数との間のインターリーブを使用して設定を行うことである。信号データ値および畳み込みデジタル・フィルタ係数値がベクトルで表されていると仮定すると、それら２つの間のインターリーブは、元の畳み込みデジタル・フィルタ係数値の２倍の大きさのベクトルを生じる。インターリーブ・ベクトルがこの大きさになる理由は、長さが分からずまたは決定されていないデータが連続的にフィードされるという畳み込みの性質によるものである。最終的なインターリーブ・ベクトルは畳み込みデジタル・フィルタ係数値ベクトルの２倍の長さであるが、最終的なインターリーブ・ベクトルは、１列目が空で、次いで２列目に第１の畳み込みデジタル・フィルタ係数が後続し、次に空列を後続し、次の４列目に第２の畳み込みデジタル・フィルタ係数値を後続するように配列される。このことが、すべての畳み込みデジタル・フィルタ係数値が挿入され同じ数の空列ができるまで繰り返される。これらの空スペースは最終的に、任意の通常畳み込み計算が行われる前にインターリーブが実行される際に信号データ値で満たされる。
【００７７】
ステップ３５２で、インターリーブ・ベクトルがｃutil中のそれぞれのコア１６にマッピングされる形は連続的である。使用される第１のコア１６は、第１の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有し、使用される第２のコア１６は次の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有することになる。同様に、それぞれの追加のｃutil中のコア１６は次の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有することになる。最後のこの種のコア１６のマッピング後、インターリーブ・ベクトルはまだ幾つかのデータ値が空であるが、それぞれのコア１６は受け取る値の長さが均一のマッピングを有するはずである。インターリーブ・ステージ１６０はここで完了し、ステップ３５４で計算ステージ１７０中の畳み込みを行う準備が整う。
【００７８】
ところで、ステップ３５８の機能は、ステップ３５２の機能と同様だが、ただしｃutil中のそれぞれのコア１６にマッピングされる量は必ずしも同量ではないために、ここではインターリーブ・ベクトル・マッピングは、それほど単純明快ではない。冒頭から開始して、インターリーブ・ベクトルは、第１の畳み込みノードについて計算されたタップ数の２倍となる複数の値を受け取る。次いで第１のコアのマッピングが終了する時点から続けて、インターリーブ・ベクトルは、第２の畳み込みノードについて計算されたタップ数の２倍に等しい複数の値を受け取る。以降も同様である。すべてのマッピング終了後も、インターリーブ・ベクトルは幾つかのデータ値が空のままであるべきである。これでステップ３５８が行うステップは終了し、インターリーブ・ステージ１６０は完了し、ステップ３５４で計算ステージ１７０中の畳み込みを行う準備が整う。
【００７９】
ステップ３４８における決定からのどの経路も、畳み込みシーケンス（すなわちｃutil中のそれぞれのコア１６用の）中のそれぞれの特定のノードについてある程度のタップ数になる。ステップ３５４で、畳み込みプロセスで使用されるすべてのコア１６は、インターリーブ・ベクトルからの適切な長さの値でマッピングされるが、畳み込みに割り当てられるコア１６の第１、第２、第３などの記述は、ターゲット・アレイ１１４のダイ上の幾何学的配置に関して曖昧である。第１ノード、第２ノードなどと呼ばれるノードの配置は、畳み込みシーケンス中の第１のノードが他のノードを使用せずに外部入力デバイス（図２）に対するアクセスを有し、第２の畳み込みノードに対する直接アクセスを有することを必要とし、そのため第１の畳み込みノードがチップの周辺に配置されなければならないように、限定を受ける。直接アクセスとは、限定されないが、２つのノードが第３のノードを使用せずに通信できること、あるいは直接アクセスを有する２つのノードが同じデータ・バス１８を共有することを示す。畳み込みシーケンスのｃ番目のノードは他のノードを使用せずに外部出力デバイスに対するアクセスを有し、ｃ−１番目のノードに対する直接アクセスを有しなければならない。第２のノードからｃ−１番目のノードまでは、それぞれのノードが畳み込みシーケンス中で前のノードと次のノードに対する直接アクセスを有しなければならないという同じ特性を共に持つ。ｃのある値については、ターゲット・アレイ１１４に有効な配置を同等にもたらす、第１、第２からｃ番目のコアについて多くの可能な構成があることを当業者は理解するだろう。ここから、マッピング・ステージ１５０およびインターリーブ・ステージ１６０があり、計算ステージ１７０で、畳み込み値を実行する準備が整う。
【００８０】
図４は、本発明のＣＣＳ１００のインターリーブ・ステージ１６０がどのように動作可能かの事例を示すチャートである。ここで信号データ値についての信号ベクトル４６０と畳み込みデジタル・フィルタ係数値についての係数ベクトル４７０は、インターリーブされて、インターリーブ・ベクトル４８０を生成する。係数ベクトル４７０の長さのみが（図３のステップ３３４から）既知であり、信号データが実際は固定された長さを持たなくてよいが、信号ベクトル４６０の長さは係数ベクトル４７０の長さに適合されている。信号ベクトル４６０のエレメント４６２、４６４、４６６、および４６８は、第１、第２、第３、および最後の信号データ値に対応する。エレメント４６６および４６８の間に位置する領域、エレメント４８２は、図４に与えられた、文字通りの４つの値より多くの信号データ値用の場所を残す。同様に、係数ベクトル４７０のエレメント４７２、４７４、４７６、および４７８は第１、第２、第３、および最後の畳み込みデジタル・フィルタ係数値に対応し、およびエレメント４７６および４７８の間に位置する領域、エレメント４８４は、図４に与えられた、文字通りの４つの値以上の畳み込みデジタル・フィルタ係数値用の場所を残す。インターリーブは、処理結果のインターリーブ・ベクトル４８０がまずトップ・エレメント４６２を信号ベクトル４６０から受信し、次いでトップ・エレメント４７２を係数ベクトル４７０から受信し、このようにして信号データ値およびフィルタ係数値を最後の係数値４７８がインターリーブ・ベクトル４８０に移動するまで受信し続けるというように、実行される。勿論エレメント４８６でのインターリーブは、エレメント４８２および４８４に見出される任意の値もまた含めるべきである。
【００８１】
ここで、畳み込みに使用されることになるコア１６、およびこれらのコア１６に対するマッピングが均一または不均一であるかは既知である。さらに、全数のタップと空データ値のインターリーブの決定が実行されている。インターリーブのコアに対するマッピングを、マッピングが均一な場合と不均一な場合の両方について以下に説明する。以下の２つの部分で参照されているのは第１、第２、．．．ｃ−１番目、およびｃ番目ノードであるが、この参照は、コア１６の配置を示すものではない。むしろ第１コア、第２コアなどと呼ばれているコア１６の配置は、畳み込みシーケンス中の第１のノードは、外部入力デバイスに対するアクセスを有し、第２の畳み込みノードに対する直接アクセスを有することを必要とする、ように限定を受ける。ＳＥＡｆｏｒｔｈ２４Ａのようなデバイスの事例では、これは第１の畳み込みノードがチップ周辺に位置することを意味する。畳み込みシーケンスのｃ番目ノードは外部入力デバイスに対するアクセスを有すると共に、ｃ−１番目のノードに対する直接アクセスを有しなければならず、そのために第１の畳み込みノードのように周辺に位置しなければならない。ここで直接アクセスとは、２つのノードが第３のノードを使用せずに通信できることを意味する。第２のノードからｃ−１番目までのノードは、それぞれのノードが畳み込みシーケンス中で前のノードと次のノードに対して直接アクセスを有しなければならないという同じ特性を共に持つ。
【００８２】
コア１６に対するインターリーブの均一マッピングは、２つのインターリーブのうちのより簡単な方である。この場合は、第１の畳み込みノードはインターリーブ・ベクトルの最初の２＊ｎactual個のエレメントを含み、第２の畳み込みノードはインターリーブ・ベクトルの次の２＊ｎactual個のエレメントを含む、などとなる。インターリーブの手順が完了すると、すべてのコア１６は、まったく同じ長さのマッピングを収容し、インターリーブ・ベクトルは空であるものとする。
【００８３】
ここでは、不均一マッピングについて２つの小事例を述べる。第１の小事例はｎactual、ｍactualおよびｃutil、の値が十分に定義されているときのマッピングである。第１の畳み込みノードは、インターリーブ・ベクトルの第１の２＊ｎactual個のエレメントを備える。第２の畳み込みノードは、次のインターリーブ・ベクトルの２＊ｎactual個のエレメントを備える。以後同様である。このインターリーブ・ベクトルのマッピングは、最初のｃ−１個のノードについて同じように続き、ここでそれぞれの追加のノードがインターリーブ・ベクトルでの次の２＊ｎactual個のエレメントを受け取る。ｃ番目のノードは２＊ｍactual個のマッピングを受け取り、これは他のインターリーブ・ベクトルとまったく等しくなければならない。再びすべてのマッピングが終了すると、インターリーブ・ベクトルは空になるものとする。
【００８４】
第２の小事例は、一般的なマッピング・ガイドラインのみが与えられている場合のマッピングである。これは、均一マッピングに極力近いことが所望される場合のことであるが、多くの場合マッピングされるｃutil中のコア１６のｎactualについて少なくとも２つの異なる値が存在することに留意されたい。ｎactualの値が十分定義された後でも、同じ全体的なマッピングをもたらす多くのマッピングがなお存在する。そのため、明白なインターリーブマッピングは可能ではなく、やはりガイドラインに従うことができるのみである。第１の畳み込みノードから始めると、このノードはインターリーブ・ベクトルから、この特定ノードについてタップ実数の２倍を受信する。第２の畳み込みノードは、インターリーブ・ベクトルからの第１のノードのマッピングが終了したところから取られたインターリーブ・ベクトルから、この特定ノードについてタップ実数の２倍を受信する。同様に、ｃutil中のそれぞれの追加のコア１６は、先のものが終了した場所のインターリーブ・ベクトルから受信し、マッピングはこの特定ノードについてのタップ実数の２倍となる。
【００８５】
図５は、本発明のＣＣＳ１００の計算ステージ１７０の間の図２のターゲット・アレイ１１４からの特定の畳み込み計算ノード（ｃutil中のコア１６）の詳細な線図である。ここでエレメント５０２〜５２０は、図４のインターリーブ・ベクトル４７２から取られたインターリーブのエントリを格納するメモリ領域を表す。図５のコア１６に対する５つの信号データ値および５つの畳み込みデジタル・フィルタ係数値のこのマッピングは単に行われる可能性のあるマッピングの一例にすぎず、これより大きくまたは小さいマッピングもまたこの特定のコア１６に対して使用可能である。
【００８６】
図５のコア１６において、エレメント５０２、５０６、５１０、５１４、および５１８はそれぞれコア１６を介してわたされる信号データ値に対応し、エレメント５０４、５０８、５１２、５１６、および５２０は、それぞれ畳み込みプロセスの間に動かないという意味で固定されている畳み込みデジタル・フィルタ係数値に対応する。
【００８７】
図５のコア１６を通して畳み込みの１回のパスの間に、その結果得られた合計（resultant sum）が生成される。まずエレメント５０２と５０４の第１の積が、エレメント５２２にわたされる。次いでエレメント５０６と５０８の積がエレメント５２４にわたされ、ここでエレメント５２４は、この積をエレメント５２２中の値と一体化する。同様に、エレメント５１０と５１２の積がエレメント５２６にわたされ、エレメント５２６は、この積をエレメント５２４中の値と一体化する。同様にして、値がエレメント５２８および５３０に到達する。エレメント５３０が持つ値とエレメント５１８が持つ値は、このコア１６から別のコア１６にわたされる２つの値のみである。信号データ値およびフィルタ係数値を乗算し、この積を、先行する部分的な積和が存在すればこれに加算するこのプロセスは、畳み込みに使用される特定のコア１６内部に存在するすべての信号データとフィルタ係数の対について繰り返される。
【００８８】
ハイブリッドＦＩＲ畳み込みの例
以下は、ｃutil中のコア１６のすべてが適切なタップ数でマッピングされ、連続するコア１６間に必要な通信が行えるように配置されている適切なターゲット・アレイ１１４で実行される畳み込みの方法を説明する。用語「ビン」はコア１６の１つにおける、信号データ値または畳み込みデジタル・フィルタ係数値のいずれかの位置を意味する。
１．初期化
１ａ．「ｎ」個のデータ・サンプルのビンが「０」の数値を受け取る。
２．第１の部分合計ｐ0を計算する。
２ａ．第１の部分合計ｐ0の計算前に、第１のデータ・サンプルｄ0は、すべての既存のデータ・サンプルを次の使用可能なデータビン中に「プッシュする」態様で、データ・サンプル・ビンｂ0中に置かれる。
２ａｌ．まず、最後のデータ・サンプル・ビンｂnに見つかったデータ・サンプルが最後のデータ・サンプル・ビンからプッシュされ、実質的に捨てられる。
２ａ２．次いでデータ・サンプル・ビンｂn-1に見つかった値がデータ・サンプル・ビンｂｎに、プッシュされる。
２ａ３．同様にしてデータ・サンプル・ビンｂn-2に見つかった値がデータ・サンプル・ビンｂn-1に、プッシュされる。
２ａ４．データを次の使用可能なデータ・サンプル・ビンにプッシュするこのプロセスは、データ・サンプル・ビンｂ0が一切データを含まなくなるまで実行され、終了する。（何らデータを含まないデータ・サンプル・ビンは、値「０」を含むデータ・サンプル・ビンと同じではない。）
２ａ５．この時点で、第１のデータ・サンプルｄ0は、残りのデータビンに追加の変更を一切加えることなく、データ・サンプル・ビンｂ0にプッシュされる。
２ｂ．次いで、積が、フィルタ係数ビンｃ0およびデータ・サンプル・ビンｂ0に見出された値を被乗数として使用して算出され、これを積ａ0とする。
２ｃ．この処理結果の積を、フィルタ係数ビンｃ1およびデータ・サンプル・ビンｂ1に見出される値として定義される複数の被乗数の乗算として定義された第２の積に加算し、この結果第２の積ａ1が得られる。
２ｄ．先の積を新しい積に加算するこのプロセスは、積ａn-1が最後の積に加算されるまで繰り返され、ａnを示すことになる。
２ｅ．値ａnは、畳み込みのうちの第１の合計ｐ0に対して等価であると考えられる。
３．第２の部分合計ｐ1を算出する。
３ａ．ステップ２ａ１〜２ａ４を繰り返すプロセスを通して第２のデータ・サンプル値ｄ1を第１のデータ・サンプル・ビンｂ0に置く。
３ｂ．ステップ２ｂ〜２ｄを繰り返すことにより、第２の部分合計ｐ1を算出する。
４．部分合計の剰余を計算する。（本アルゴリズムは、無限の量の時間の間データを受け取り、そのために停止条件が要求されない畳み込みのアルゴリズムを記述する。）
４ａ．ステップ２ａ１〜２ａ４を繰り返すプロセスを通じて次のデータ・サンプルを第１のデータ・サンプル・ビンｂ0中に「プッシュする」ステップを繰り返す。
４ｂ．ステップ２ｂ〜２ｄを繰り返すことにより新しい部分合計を計算する。
【００８９】
ノード間のデータの伝送は、上記に記載されておらず、畳み込みを実行すること、フィルタの直接的表現を使用することのみが記載されている。代わりにフィルタが導関数表現（derivative representation）で表されている場合は、畳み込みを実行するのに以下の変更が必要である。
【００９０】
既存のステップ
３ｂ．ステップ２ｂ〜２ｄを繰り返すことにより第２の部分合計ｐ１を算出する。
４ｂ．ステップ２ｂ〜２ｄを繰り返すことにより新しい部分合計を算出する。
上記を次と置換する。
３ｂ．ステップ２ｂ〜２ｄを繰り返し、ステップ２ｂ〜２ｄからのこの値ｐ1を先に計算された部分合計ｐ0に加算することにより、第２の部分合計ｓ1を計算する。
４ｂ．ステップ２ｂ〜２ｄを繰り返し、ステップ２ｂ〜２ｄからのこの値を先に計算された部分合計に加算することにより、新しい部分合計を計算する。
【００９１】
図６Ａ−Ｂは、実質的に今述べたのと同じやり方のハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコード６００の２ページの表である。
【００９２】
要約すると、本発明は特に２つの原理を採用している。第１の原理は、アルゴリズムのうち、大きい方の部分を高速化した方が、小さい方の部分を大幅に高速化するより良いという原理である。第２の原理は、畳み込みアルゴリズムは、連続的および並列的エレメントの両方を有するということを認識し、受け入れることである。畳み込み値は、連続的な、すべての部分が次々計算される形で計算することができる。一方、これとは対極的に、すべての部分を同時にすなわち並列に計算することができる。または中間の手法を使用することもでき、この場合、一部を連続的に計算し一部を並列で計算する。ＣＣＳ１００は、一定量の連続的処理を保ちながらも、並列計算を実行する能力を提供し、これにより、使用される畳み込みアルゴリズムを実際に高速化することもなく、また、使用されるハードウェアの処理能力を増大させることもなく、畳み込みの速度を大幅に向上させることができる。
【００９３】
本発明の実施形態は、図２のシステム上で実行させると、上述したように、信号データ値および畳み込み係数値をアレイ１１４にマッピングするコンピュータ・プログラムを提供する。
【００９４】
本発明の実施形態は、図２のシステム上で実行させると、図６Ａおよび６Ｂについて上述したように、信号データ値および畳み込み係数値を畳み込み計算するコンピュータ・プログラムを与える。
【００９５】
さらに、畳み込み計算は、本発明の例にすぎず、ＣＣＳ１００はまた、連続的および並列的エレメントの両方を有する任意のタイプのアルゴリズムの性能を増大させる現実的手法も与えることも、今や理解されるべきである。
【００９６】
様々な実施形態を上に述べたが、これらは例としてのみ提示されたものであり、本発明の幅と範囲は上に述べた例示的実施形態のいずれにも限定されるものではないことが理解されるべきである。
【図面の簡単な説明】
【００９７】
【図１ａ】本発明による畳み込み計算システムがセットアップ演算、通常作業演算、および要約した演算をどのように実行するかの概観を模式的に示すブロック図である。
【図１ｂ】本発明による畳み込み計算システムがセットアップ演算、通常作業演算、および要約演算をどのように実行するかの概観を模式的に示すブロック図である。
【図２】（背景技術）図１ａにターゲット・アレイとして使用されているＳＥＡｆｏｒｔｈ２４Ａデバイスの主要な詳細を全体的に示す線図である。
【図３】図１ｂのマッピング・ステージの例示的実施形態がどのように実行されるかを示すフローチャートである。
【図４】図１ｂのインターリーブ・ステージがどのように作動するかの事例を示すチャートである。
【図５】図１ｂの計算ステージの間の図２のターゲット・アレイからの特定の畳み込み計算ノードの詳細な線図である。
【図６Ａ】ハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコードの２ページのリストである。
【図６Ｂ】ハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコードの２ページのリストである。
【符号の説明】
【００９８】
１００ 本発明の好ましい実施形態
１１２ ホスト・プロセッサ
１１４ ターゲット・アレイ
１６ コア
１８ データ・バス
１６１ 入力デバイス
２２１ 出力デバイス
３３０ 開始ステップ
３３２ （Ｓ）の入力
３３４ （Ｌ）の入力
３３６ （ｔ）の入力
３３８ （ｎmax）の入力
３４０ 入力が有効か？
３４２ マッピングの中止？
３４４ マッピングの停止
３４６ （ｃutil）の計算
３４８ ｃutilが整数値であるか？
３５０ ｎestの値をｃutilのすべてに使用
３５２ ｃutil中の各コア１６に対してインターリーブ・ベクトルをマッピングする
３５４ 通常畳み込み計算をすすめる
３５６ 例えば、ｎactualの値をコア１６のｃutil−１に使用し、異なるマッピングをｃutil中の（ｃ番目）の他のコア１６で使用する
３５８ ｃutil中の各コア１６に対してインターリーブ・ベクトルを、不均一にマッピングする
４６０ 信号ベクトル
４６２−４６８ 信号ベクトルのエレメント
４７０ 係数ベクトル
４７２−４７８ 係数ベクトルのエレメント
４８０ インターリーブ・ベクトル
４８２ 信号ベクトルのエレメント
４８６ 係数ベクトルのエレメント
５０２−５２０ インターリーブのエントリを格納するメモリ領域
５０２、５０６、５１０、５１４、５１８ 信号データ値の領域
５０４、５０８、５１２、５１６、５２０ 畳み込みデジタル・フィルタ係数値の領域
５２２ 積
５２４−５３０ 部分的な積合計
６００ Ｆｏｒｔｈコード
【技術分野】
【０００１】
本発明は、概して信号処理に関する。
【背景技術】
【０００２】
積分変換
多くの既存のシステムおよび新規のシステムは、基本となるシステムを記述する数学に基づいて適切にプログラムされた近代的デジタルプロセッサを使用して解析可能である。例えば、今日この種の解析は、電気回路、光学器械、機械的機構、およびその他の多くのシステムなどの、線形時不変システム（linear time-invariant systems）を解析するためにますます有用である。
【０００３】
数学、およびこれを広範囲に用いる多くの分野、例えば今日の科学と工学のほとんどの部門において、用語「変換（transform）」は、ある種の方程式による解析技術のクラスを言及するために用いられる。変換の概念は、特定の関数が他の関数を引数として持つ関数空間の研究を主として扱う数学の関数解析（functional analysis branch of mathematics）の部門に由来する。このため変換は個々の方程式にも方程式のセット全体にも用いることができ、変換のプロセス（process of transformation）とは、ある定義域で表される元の方程式または複数の方程式を、他の別の定義域で表される他の１つまたは複数の方程式に１対１でマッピングすることである。
【０００４】
変換を行う動機は、しばしば単純である。元の表現では解くのが難しいが、１つまたは複数の他の表現によればより簡単に解決可能である方程式は多い。このため変換が行われ、解が見出され、それから逆変換を行って、その解を元の定義域に戻してマッピングすることができる。積分変換の一般的な形態は次のように定義される。
【０００５】
【数１】
【０００６】
ここでＫ（α，ｔ）は、しばしば変換の「積分核（integral kernel）」と呼ばれる。
【０００７】
ラプラス変換
ラプラス変換は、方程式（１）で定義されるある種の変換のサブセットであり、しばしば特に有用である。システムへの入力またはシステムからの出力が単純な数学または関数で表現されているときに、ラプラス変換は、システムの挙動を簡単に解析できる代替の関数の記述を与えることができる。ラプラス変換の一般的な形態は次のように定義される。
【０００８】
【数２】
【０００９】
ここで方程式（１）から積分の境界および積分核は、ａ＝０で、ｂは∞に置き換え、Ｋ（α，ｔ）＝ｅ-stとして再定義されている。ラプラス変換のｆ（ｔ）への適用は、ｓが十分に大きく、ある条件が満たされる場合のみ可能であるが、これらの条件は通常、ｆ（ｔ）が、実際に見出されるほぼ任意の有用な関数の関数形をとることができるほど十分に柔軟である。
【００１０】
畳み込み定理（CONVOLUTION THEOREM）
ある関数、例えばＦ（ｓ）が単一の既知の関数の変換ではなく、それぞれが、既知のｆ（ｔ）またはｇ（ｔ）の関数の変換結果である２つの関数の積として表せるのは、よくあることである。すなわち、
【００１１】
【数３】
【００１２】
である。ここでｇ（ｔ）は、ｆ（ｔ）と同じ条件を満足しなければならない。Ｆ（ｓ）、ｆ（ｔ）、およびｇ（ｔ）のこの結び付きから、次の関係が成立する。
【００１３】
【数４】
【００１４】
これはしばしば「畳み込み（重積分）定理（convolution theorem）」と呼ばれる。
【００１５】
畳み込み定理の数値近似
畳み込み定理の結果は変数が１つのみの積分変換となることが観察されている。そのため変数が１つのみの積分の数値近似の技術を適用することができる。
【００１６】
積分表現（integral representation）とリーマン和による表現（Riemann sum representation）の間に次の等式が成り立つ。（ここで後者は、特にデジタル回路を用いて行われる数値近似の技術での使用に適切である。）
【００１７】
【数５】
【００１８】
ここでそれぞれのｃt-kおよびｃkはｋ番目のサブ・インターバルから任意に選択される。実際には、方程式（５）の等式の右項は、極めて小さなΔγを用い、選択された計算法およびΔγの値に応じて幾分の誤差があることを了解することによって、近似される。
【００１９】
【数６】
【００２０】
ここでｍは、結果としての合計（resultant sum）で表すことができる正確さの次数（期待可能な精度の桁数でもある）を表し、およびΟは、従来の数学のコンテキストにおけるビッグオー記法（big-O notation）である。
【００２１】
デジタル信号処理
先に述べたように、畳み込み（convolution）を使用することが利点となり得る変換には、重要な応用における既存および潜在的な用途がある。例えばデジタル信号処理（ＤＳＰ：digital signal processing）は幅広く、ますます使われており、ＤＳＰのこの種の重要な用途の１つにデジタル・フィルタリングがある。数学的関数として表現可能な任意のフィルタリングがデジタル・フィルタの使用で実現でき、これは、近年のＤＳＰの仕事のまさに出発点の１つである。例えば、信号からサンプル抽出されたデータ値に関するデジタル・フィルタリングは、信号の不要部分の除去や信号の必要部分の抽出を可能にする。
【００２２】
有限インパルス応答（ＦＩＲ：finite impulse response）および無限インパルス応答（ＩＩＲ：infinite impulse response）は、今日、ＤＳＰの用途に使用される２つの主要なデジタル・フィルタであるが、その中ではＦＩＲフィルタがより一般的である。
【００２３】
ＦＩＲフィルタは、用いる上での優位性があると通常考えられているが、その理由は、内部フィードバック（これは例えば、ＩＩＲフィルタが無限にインパルスに応答する原因となる）を必要としないためである。その名称における「有限」という言葉からもＦＩＲフィルタの別の利点が示唆される。この種のフィルタからのインパルスは最終的にゼロとなり、使用される逐次加算計算中のエラーが伝搬されることがない。すなわちエラー項が計算プロセス全体で一定に保たれる。これはＩＩＲフィルタに対する明確な利点であり、ＩＩＲフィルタでは、例えば追加の逐次出力加算毎にエラーが潜在的に成長する可能性がある。
【００２４】
残念ながら多くの用途において、デジタル・フィルタの大きな限界は、そのスピードが数値計算に用いられるプロセッサまたは複数のプロセッサのスピードによって制限されることである。例えば、高速のフィルタリング速度が必要な場合、これは、高価な、デジタル・フィルタを実装するのに必要なハードウェアを高価にしたり、あるいは単純に実装不可能にしたりする可能性がある。ほとんどすべての用途について、またほとんどの電子的システムに当てはまるが、用いられる速度が速くなればなるほど、電磁雑音の抑制および放熱などの、同時発生する現象に対応することも難しくなる。
【００２５】
デジタル・フィルタリングの事例を越えて一般化すると、ＤＳＰは通常、少なくとも１つの処理される信号のサンプリングを前提にする。サンプリング速度は、ある特定の連続信号についての連続信号を、離散信号（discrete signal）に変換する、単位時間当たりのサンプル数として定義される。連続信号を離散信号に変換する理由は、変調、符号化、および量子化にかかわる用途など、数多くある。サンプル速度は、より一般的にはヘルツ（Ｈｚ）（測定における周波数の単位）で表され、これは波長（λ）（時間の単位で、λ＝Ｈｚ-1および逆もまた同様）と等価である。
【００２６】
連続信号が元の関数を復元しようとしてサンプルすることが可能な方法には、アンダー・サンプリング、ナイキスト速度サンプリング、およびオーバー・サンプリングの３つの方法がある。
【００２７】
連続信号のアンダー・サンプリングは、元の信号から関連する情報のすべてを取得することが可能とは限らないために、しばしば最良の選択ではない。しかし元の信号の復元が重要でない場合は、アンダー・サンプリングによると格納されるデータが減り、サンプリング・プロセスを大幅に速めることができる。
【００２８】
多くの場合、好ましいのはナイキスト速度サンプリングであり、その理由は、その後に特定の信号を正確に復元することを可能にするからである。このサンプリング周期（「ナイキスト速度」と称される）は、サンプリングする信号の帯域幅の２倍を超えていなければならず、この信号は、帯域制限される必要がある。つまり信号は、ある有限の周波数以上でゼロのフーリエ変換やパワー・スペクトラム密度を有することが確定された信号であることを意味する。
【００２９】
オーバー・サンプリングは、３つのサンプリング法の中で最も非効率で無駄が多いが、元の信号の復元が常に可能し、スピードが重要でない場合は利点となり得る。
【００３０】
サンプリングの重要性と、それがＤＳＰおよびＤＳＰを用いるシステムにしばしばどのような制約を及ぼすかについて、さらに述べる。
【００３１】
並列アルゴリズム
計算機（ＤＳＰおよびその他の多くの用途に用いられる計算機）に関連するハードウェアの最近の構成上の変化が起こるまでは、すべてのコンピュータに実装されるアルゴリズムは、連続的にまたは逐次実行されるものと考えられていた。すなわち、１つの作業のみが任意の所与の時間に適時に実行可能であった。この考えから、連続したタスクをより短い時間で実行できるようにするためにますます高速のプロセッサを作製することになった。しかし先に述べたように、この種のプロセッサは、実現可能な処理パワーが現在限界に達しつつある。今日では、この限界は、ハードウェアの速度向上からアルゴリズムの速度向上に力点が移りつつある。
【００３２】
アルゴリズムの速度向上の１つの手法は、並列処理の使用である。アルゴリズムの多くは、それが、今もなお、実行するためのハードウェアに制限されることがあるとはいえ、多くのアルゴリズムがそれ自体ある程度の並列化に極めて適している。別の他のアルゴリズムでは、すべての面で並列的に実行される場合、より速い速度が達成できる。この点に関連して、並列に達成可能なアルゴリズムの率（Ｔp）、連続的に達成可能なアルゴリズムの率（ＴS）、および使用可能な並列プロセッサの数（Ｎ）を与えたとき、並列計算で起こり得る最大速度上昇率（Ｓ）を決定するために、アムダールの法則がしばしば用いられる。アムダールの法則は次のように表すことができる。
【００３３】
【数７】
【００３４】
アルゴリズムの大きな部分を高速化する方が、アルゴリズムの小さな部分を大きく高速化するよりも良いということが幅広く受け入れられ、概してそのような命題を支持するように考えられている。この理由は方程式（７）中において、また収穫逓減の法則を適用することにより。理解できる。
【００３５】
整数プログラミング
線形計画法（ＬＰ：linear programming）の基本の把握は、整数プログラミング（ＩＰ：integer programming）の理解に役立ち、これは、以下述べる理由のために取りこまれた。ＬＰの問題は、線形な目的関数を有する最適化の問題である。この種の問題は、例えばネットワークのフローの用途などでしばしば発生する。
【００３６】
ＬＰ問題は、今日の計算に関するリソースが与えられるとしばしば容易に解決可能である。しかし、この顕著な例外は、ＬＰが、変数の値を整数値のみに限定するという制約があること、すなわち、ＬＰ問題が整数プログラミング（ＩＰ：integer programming）問題であることである。ＬＰ問題を解決するための技術は、ＩＰ問題に、同じ形では適用できないことがしばしばであり、多くの場合これらの技術は、ＩＰ問題のすべてに適用できるわけではない。そのためにＩＰ問題は、より解決が難しくなる。
【００３７】
さらに問題が、ＬＰ問題ではなくＩＰ問題として取り扱われる場合、ＩＰ問題としてその問題を解くのに必要な計算機能力は、ＬＰ問題としてその問題を解くのに必要な計算機能力と比べて、指数的に増加する。そのために４０以上の変数を持つＩＰ問題は、その問題中の変数の数を効果的に最も少なくするのに利用可能な何らかのＩＰ問題の構造（structure）が存在しない限り、今日利用可能な計算機能力では解くのは不可能だとほとんどの研究者が考えている。このためにＩＰ問題の解を開発するのに費やされる時間のほとんどは、問題の構造を利用する方法を見つけて、変数の数を減らし、適時のコンピュータの解決策を可能にすることに向けられている。しかし、それゆえに最適化問題を、ＬＰ問題を超えたＩＰ問題と分類することには大きなトレードオフがある。ＩＰ問題は所与の状況をより現実的にモデル化できるかもしれないが、ＩＰ問題に存在するそれは、あるため解決不能の方程式のセットに行き着く可能性がある。対照的にＬＰ問題は、潜在的な状況のモデル化するためのＩＰ問題の対応物よりも現実性が薄いことが多いが、通常は解決可能であり、速やかに解決することができる。
【発明の開示】
【発明が解決しようとする課題】
【００３８】
そのために、信号を処理するために、例えば特にＤＳＰに使用される数値畳み込み計算を実行するために用いるシステムを改善することで、これらの用途および関連するタスクを、より高速でより経済的に、かつ基本のシステムや周辺システムを損なう影響を減らしつつ実行することが可能となるであろう。
【課題を解決するための手段】
【００３９】
本発明の一態様は、複数の信号データ値および複数の係数値を、畳み込み値を計算するための使用される一組のプロセッサ（ｃutil）の１つである対象プロセッサ（ｃt）に、ロードするプロセスである。複数の係数値はｃutilにマッピングされる。その後ｃt中の複数のデータ値と複数の係数値のインターリーブが決定される。ｃtに前記複数の係数値がロードされ、ｃtに前記複数のデータ値がロードされ、それによって、信号データ値の処理に参加するようｃtを準備させる。ある例では、複数の係数値は、畳み込みフィルタの複数の係数値であり、このプロセスは、複数のフィルタ係数値および複数のデータ値の畳み込みを計算する。
【００４０】
本発明の他の態様は、例えば複数の信号データ値、および畳み込みフィルタ係数値とすることができる複数の係数値に基づいて畳み込みを計算する、信号を処理するシステムである。使用される複数のプロセッサからなる一組のプロセッサ（ｃutil）が与えられ、ここでは、各プロセッサは、順番に、所与の時点で対象プロセッサ（ｃt）と見なすことができる。ロジックが、複数の係数値をｃutilにマッピングする。あるロジックがｃt中の複数のデータ値と複数の係数値のインターリーブを決定する。あるロジックがｃt中の複数の係数値をロードする。またロジックがｃt中の複数のデータ値をロードする。これは、ｃtが、その信号処理に、例えば畳み込み値の計算に参加するように準備させる。
【００４１】
本発明はまた、コンピュータのアレイ上で実行すると、そのアレイに発明の一態様のプロセスを実施することを引き起こすコンピュータ・プログラムを提供する。このコンピュータのアレイは、単一の半導体のダイ上に存在するとすることができる。プログラムは、例えば、記録媒体、電気信号とすることができる信号、またはメモリ・デバイスなどの、キャリア上に存在することができる。
【００４２】
本発明のこれらのおよび他の目的および利点は、本明細書に記載され図面中の各図に示された、本発明を実施する現在知られた最良の形態と好ましい実施形態の産業上の利用可能性の記載を読むことにより、当業者には明瞭になろう。
【発明を実施するための最良の形態】
【００４３】
本発明の目的および利点は、以下の詳細説明、ならびに添付図面の各図から明らかになるであろう。添付図面の各図においては、類似の参照符号が、類似または同様の要素またはステップを表すために用いられている。
【００４４】
本発明の好ましい実施形態は、複数のコンピュータ・プロセッサにより、実行される畳み込み計算のシステムである。本明細書において様々な図に示されるように、特に図１ａ〜ｂに示されるように、本発明の好ましい実施形態を、一般参照符号１００で示す。
【００４５】
図１ａ〜ｂは、本発明による畳み込み計算システム（convolution calculation system）（ＣＣＳ１００）がどのようにセットアップ演算、通常作業演算（formal work operations）、および要約した演算（wrap-up operations）を実行できるかについて、概略を模式的に示すブロック図である。
【００４６】
図１ａに示すように、ホスト・プロセッサ１１２を用いて、信号データ値および畳み込み係数フィルタ値を、ターゲット・アレイ１１４中の複数のプロセッサ、コア、またはノードにマッピングし、信号データ値および係数フィルタ値に基づいてインターリーブのターゲット・アレイ１１４へのロードを開始し、処理結果をターゲット・アレイ１１４から受け取る。
【００４７】
ホスト・プロセッサ１１２は、図１ａに示されるような単一の個別システムであることができる。しかし当業者は、以下を理解すれば、ホスト・プロセッサ１１２は複数の個別システムであることも可能であることをさらに理解しよう。さらに、説明するように、ホスト・プロセッサ１１２はターゲット・アレイ１１４の一部とすることもできる。しかし、通常、ホスト・プロセッサ１１２は、通常のパーソナル・コンピュータ（ＰＣ）またはワークステーションである。
【００４８】
ターゲット・アレイ１１４もまた多くの形態をとり得るが、具体的にはカリフォルニア州クパチーノ所在のＩｎｔｅｌｌａｓｙｓ Ｃｏｒｐ．のＳＥＡｆｏｒｔｈ（ＴＭ）製品などの、マルチ・コアまたはマルチ・ノード、単一ダイの集積回路デバイスとすることができる。
【００４９】
図１ｂは、ＣＣＳ１００の作業の主要なステージを示す。マッピング・ステージ１５０で、畳み込みデジタル・フィルタ値が、ターゲット・アレイ１１４の使用可能なプロセッサ、コア、またはノードに、これらをより効果的に用いるように、マッピングされる。次いで、インターリーブ・ステージ１６０で、インターリーブが、ターゲット・アレイ１１４のプロセッサ、コア、またはノードに効率的に係数をロードするよう構築される。計算ステージ１７０で、畳み込みを実行する。（ハイブリッドのＦＩＲの例が、以に示される。）勿論、信号データ値のロードおよび処理結果のアンロードもまた行われるが、これらは図１ｂにおいてステージとして示されない。
【００５０】
図２（背景技術）は、ターゲット・アレイ１１４に使用されているＳＥＡｆｏｒｔｈ２４Ａデバイスの主な細部を全体的に示す線図である。畳み込み計算の準備、およびその後の実際の使用にかかわるこの態様に、焦点を当てるために、図２において、多くの、重要でない周辺の構成要素は省略されたり、概略的に示されたりしている。しかし当業者は、実際の実施形態の作動ではこの種の要素が存在し、これらは、通常その性質についてはまったく通常通りであることを理解しよう。
【００５１】
図２のシステムは、アレイ１１４と、入力デバイス１６１と、出力デバイス２２１とを備える。入力デバイス１６１は、処理される信号から、畳み込みが実行されることになる入力データの値を与える。この入力データ値は処理される信号のサンプルである。出力デバイス２２１は処理されたデータ値をアレイ１１４から受け取る。
【００５２】
図２で理解されるように、ＳＥＡｆｏｒｔｈ２４Ａのデバイスは、データ・バス１８を介して互いに通信する２４個のコア（集合的にはコア１６、個別的にはコア１６ａ〜ｘ）を備える。（本明細書では用語「コア」が用いられているが、ＳＥＡｆｏｒｔｈ２４Ａのようなデバイス中のプロセッサについて述べるときには用語「ノード」も同様に適切であり、用語「プロセッサ」も一般的に正しい。）
必ずしも必要ではないが、一般的に、１つのコア１６（例えば図２のコア１６ａ）が、データ入力タスクの処理専用にされ、別のコア１６（図２のコア１６ｘ）がデータ出力タスクの処理専用にされる。したがって本明細書にある２４個のコア１６中２２個が、畳み込み計算に通常にかかわる作業の実行に使用可能である。一方、１個のコア１６がデータの入力と出力の両方の専用にされることも可能である、複数のコア１６が他のタスク専用にされることも可能である。例えばホスト・プロセッサ１１２が、１つまたは複数のコア１６内に実装されることも可能である。
【００５３】
本発明のＣＣＳ１００は、畳み込みの性質と、ターゲット・アレイ１１４で畳み込みを効率的に実行するために何をしなければならないかの性質、とに起因して、計算ステージ１７０を実行する前の入力に大きく依存している。これらの入力と用語について下に一般的に述べる。
【００５４】
用語集
概して、ｃは、ターゲット・アレイ１１４中の複数のコア１６を表す変数であり、
ｃtotal＝ターゲット・アレイ１１４中に存在するコア１６の総数（例えば図２中の例では２４）、
ｃavail＝畳み込み計算の実行のためのマッピングに使用可能なコア１６の数（例えば図２中の例では２２）、
ｃutil＝複数のフィルタ値のマッピングに使用されるコア１６の数（すなわちマッピング・ステージ１５０が決定しようとする値）、および
ｃt＝所与の時点における、考察対象の、ｃutilから選ばれる対象コア１６。
【００５５】
一般的に、ｎはデジタル畳み込みフィルタ値の量を表す変数であり、
ｎactual＝ｃtにマッピングされたフィルタ値の実数、
ｎest＝ｃutilの一部であるコア１６のそれぞれにマッピングされたフィルタ値の予測数；
ｎtaps＝所与のコア１６に実際にマッピングされたフィルタ値（「タップ」）（すなわちマッピング・ステージ１５０が決定しようとするｃutil毎に１個の、複数の値からなる集合）の数、および
ｎmax＝任意の特定のコア１６に対する、複数の信号データ値（または係数フィルタ値）のうちの最大マッピング値（すなわちｎmaxはｎtapsの集合の要素であり、具体的には最大値を有する要素である。）
以下が定義される。
Ｓは、サンプル速度、
Ｌは、積分核の時間窓の長さ、
ｔは、ターゲット・アレイ１１４の２つの数を乗じるために必要な時間、および
Ａは、データ値およびフィルタ値の格納に使用される、コア１６中のメモリの使用可能なワード。
【００５６】
ｃに関する簡潔な関係式が次のように論理的に導かれる。例えば、０＜ｃutil≦ｃavail≦ｃtotalであることは容易に分かり、このすべてが整数値である。次いで０＜ｃutil＜ｃavail≦ｃtotalの事例は、最適値ではないかもしれないが、それにもかかわらず現実世界の用途では起こる可能性がある。つまり、フィルタ値が何もマッピングされておらず、そのために畳み込み計算の通常プロセス（formal process）にも使用されない１つまたは複数のコアを備えた方が、より効率的である場合が、よくある。
【００５７】
同様に、ｎに関する関係式もまた次のように論理的に導かれる。例えば、０≠ｎtotalおよび０＜ｎtaps≦ｎest≦ｎtotalであることが分かり、ここでｎtapsとｎtotalは整数値となる。（そしてｎestも整数値となるよう制限することになる。）次いで、ｎtaps＝ｎtotalの場合（すなわち全フィルタ値が、唯一のコアにマップされる場合）が認識されるべきである。本発明のＣＣＳ１００は、最も効率的な解である事例を網羅するが、ＣＣＳ１００の利点はｎtaps＜ｎtotalがより最適な解である事例において具体的に実現される。やはり、事実上、既に説明した点を繰り返すと、一部のコアについて０＝ｎtapsである現実社会の用途に、直面することになる。
【００５８】
定義された値に関する簡潔な関係もまた述べることができる。本明細書ではＳの値を変数として扱っている。すなわち単位時間当たりでより多くのまたはより少ないサンプルが集められてよい。本明細書ではＬの値を変数として扱っていない。ｔの値は、ターゲット・アレイ１１４のハードウェアで指定される最小値を元来有するため、固定される。（そして効率的なプログラミングがなされて、最小値が実現されていると推定する。）Ａの値は減らすことはできるが増やすことはできない。これは、データまたはフィルタ値の格納にＲＡＭおよびＲＯＭのいずれかが使用される場合、ＲＡＭおよびＲＯＭ中の使用可能なワード数によってメモリのワード数が制限されるためである。しかしＡのすべて用いなければならないという要件はない。
【００５９】
図３は、本発明のＣＣＳ１００のマッピング・ステージ１５０の例示的実施形態がどのように実行され得るかを示すフローチャートである。ステップ３３０でマッピング・ステージ１５０が開始する。次いで、一組の入力がホスト・プロセッサ１１２に与えられる。特に、ステップ３３２でサンプル速度（Ｓ）が与えられる。ステップ３３４で、積分核の時間窓の長さ（すなわち持続時間）（Ｌ）が与えられる。ステップ３３６で、ターゲット・アレイ１１４の２つの数を乗じるために必要な時間（ｔ）が与えられる。およびステップ３３８で、任意の特定のコア１６に対する信号データ値（または係数フィルタ値）の最大マッピング値（ｎmax）が与えられる。
【００６０】
ステップ３４０で、ステップ３３２〜３３６の入力が有効か否かが決定される。これらの入力が任意の点で無効の場合は、ステップ３４２が続き、マッピング・ステージ１５０を中止するかを決定する。中止すると決定されれば、ステップ３４４が続き、マッピング・ステージ１５０は停止する。一方、中止しないと決定されれば、マッピング・ステージ１５０は図示のようにステップ３３０に復帰する。
【００６１】
さらにステップ３４０での他の選択肢を述べると、入力が一括して有効と見なされると、ステップ３４６が続き、並列畳み込みアルゴリズムの実行に使用されるコア１６の数（ｃutil）が計算される。
【００６２】
まずｎtapsが計算される。
【００６３】
（８） ｎtaps＝Ｓ＊ｔ、
次いでｎmaxが決定される。ユーザが与える入力（ステップ３３８）であっても計算で算出されてもよい。
【００６４】
【数８】
【００６５】
次いでノード毎のタップの予測数（ｎest）が計算される。
【００６６】
（１０） ｎest＝ｍｉｎ（ｎtaps，ｎmax）、
次いで、ここでノード毎のタップの数（ｎest）が既知であるため、これらのタップがマッピングされることが可能なコアの数（ｃutil）が計算される。
【００６７】
【数９】
【００６８】
ここでｃutilはｃutil≦ｃavail≦ｃtotalとの要件を満たす必要があることに留意されたい。この要件が満たされない場合は、Ｌの値および／またはｎestの値をＬの値を減らすこと、および／またはｎestの値を増やすことによって改変してよい。Ｌを改変することはユーザ入力によりなされる。一方、ｎestの変更はプログラムに基づいてなされることができる。ｎestの値はｎtapsおよびｎmaxの関数であり、これらは両方減らすことができる。このことは、ｎmaxの場合は、ＲＡＭ／ＲＯＭ中で使用可能なワードの総数（Ａ）未満の数を使用することにより可能であり、ｎtapsの場合は（Ｓ≧ｔの関係を保ちながら）Ｓおよびｔの一方または両方を減らすことにより可能である。
【００６９】
図３についてさらに述べると、ステップ３４８でｃutilが整数値であるかが決定される。つまり、方程式（１１）に剰余が生じなかったかということである。
【００７０】
剰余がない場合は、タップのコア１６に対する均一なマッピングが可能であり、これを用いることにより最適の効率が得られる。この場合ステップ３５０が続き、ｎestの値がｃutilのすべてに使用される。次いでステップ３５２が続き、ｃutil中のそれぞれのコア１６に対してインターリーブ・ベクトルがマッピングされる。（インターリーブ・ベクトルについては、いずれ説明する。）ステップ３５４で通常畳み込み計算（formal convolution calculation）をすすめることができる。
【００７１】
今述べたようにすすめると、ステップ３５２からステップ３５４は明らかに一般的事例に対する稀な例外であり、Ｌおよびｎestの除法が負ではない整数の結果をもたらす場合である。ステップ３４８に剰余がある場合、タップのコア１６に対する不均一なマッピングが必要になる。ステップ３５６でこれが実行され、ここでまず可能な最も均一なマッピングを試みる。マッピングの不均一性の性質から、３つ以上でなくとも、少なくとも２つの異なるｎactualの値が必要となるだろう。
【００７２】
ステップ３５６で、発明者にとり好ましい初期の手法はｎactualの値をコア１６のｃutil−１に使用し、異なるマッピングをｃutil中の（ｃ番目）の他のコア１６で使用することである。次いでｃ番目コアはマッピングｍactualを有し、これは以下で示される。
（１２） ｍactual＝Ｌ−ｎest（ｃutil−１）、
ここでｍactual＜ｎactualである。残念ながら、初期の手法もこの型のマッピングを使用するある用途には非効率的である可能性がある。（留意すべきことだが、本明細書に述べる手法は指針を与えるにすぎない。その理由は、このような整数プログラミング（ＩＰ）問題の性質が解を整数の処理結果に制限し、使用可能な解法を大きく制限するためである。）
畳み込み方法はｃutil中のコア１６に制限されている、という事実により、これらのみが通常計算（formal calculation）中に使用されることになるので、ｃutil中のそれぞれのコア１６に対するマッピングが可能な限り均一に近いことは必須である。コア１６間の、接近した均一性は、これらのコア１６のスリープ時間を、コア１６毎の最大タップ数未満に制限する。
【００７３】
ここでマッピングを考える他のやり方は、アムダールの法則に従い、たとえ最速部分の性能が低下する可能性があっても最も遅い部分の性能を向上させることである。不均一なマッピングがここで要求されるとすれば、マッピング・プロセス中にｎestの値が１より大きい値となることを期待するのは合理的である。例えばＬ＝９９およびｎest＝２４とすれば、ｃutil＝５である。この事例は、Ｌおよびｎestが除されたときに剰余が出る。上述した第１の方法を用いると、この場合のマッピングは２４、２４、２４、２４、および３となるだろう。しかしながら今述べた方法を用いれば、より望ましいマッピングは２０、２０、２０、２０、および１９となるだろう。（勿論、同じ全体の処理結果をもたらす他のマッピングが４つ存在する。例えば、１９、２０、２０、２０、および２０））この種の事例では、コア１６を最適にマッピングする包括的なアルゴリズムの概要を説明するのは非常に困難であり、したがって、ここでの骨子は、Ｌおよびｎestの除法が処理結果がゼロではない剰余をもたらしても、このマッピングにおいてある程度の効率性を保持するのはなお可能であり、ｃutil中のコア１６のｎestの値が可能な限り均一に近いときに、この効率性は最大化されるということである。
【００７４】
ステップ３５６の後、ステップ３５８が続き、ｃutil中の各コア１６に対してインターリーブ・ベクトル（インターリーブ・ベクトルについては、いずれ説明する。）がマッピングされ、ステップ３５４で通常畳み込み計算をすすめてよい。
【００７５】
総括すると、マッピング・ステージ１５０はここで完了し、それぞれのコア１６に対する複数のタップの実数の値は既知であり、ＣＣＳ１００全体の次段階、つまりインターリーブ・ステージ１６０でのインターリーブ・ベクトルの決定を実行することができる。図３は、インターリーブ・ステージ１６０はステップ３５２またはステップ３５８で表されており、インターリーブ・ベクトルはｃutil中のコア１６に対して（すなわち通常畳み込み計算（formal convolution calculations）に使用されるそれぞれのコアに対して）マッピングされ、ステップ３５４は計算ステージ１７０である。
【００７６】
簡潔にいえば、インターリーブ・ステージ１６０での目標は、計算ステージ１７０で畳み込みを実行するために、サンプリングされた信号データ値（履歴値としても知られる）と畳み込みデジタル・フィルタ係数との間のインターリーブを使用して設定を行うことである。信号データ値および畳み込みデジタル・フィルタ係数値がベクトルで表されていると仮定すると、それら２つの間のインターリーブは、元の畳み込みデジタル・フィルタ係数値の２倍の大きさのベクトルを生じる。インターリーブ・ベクトルがこの大きさになる理由は、長さが分からずまたは決定されていないデータが連続的にフィードされるという畳み込みの性質によるものである。最終的なインターリーブ・ベクトルは畳み込みデジタル・フィルタ係数値ベクトルの２倍の長さであるが、最終的なインターリーブ・ベクトルは、１列目が空で、次いで２列目に第１の畳み込みデジタル・フィルタ係数が後続し、次に空列を後続し、次の４列目に第２の畳み込みデジタル・フィルタ係数値を後続するように配列される。このことが、すべての畳み込みデジタル・フィルタ係数値が挿入され同じ数の空列ができるまで繰り返される。これらの空スペースは最終的に、任意の通常畳み込み計算が行われる前にインターリーブが実行される際に信号データ値で満たされる。
【００７７】
ステップ３５２で、インターリーブ・ベクトルがｃutil中のそれぞれのコア１６にマッピングされる形は連続的である。使用される第１のコア１６は、第１の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有し、使用される第２のコア１６は次の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有することになる。同様に、それぞれの追加のｃutil中のコア１６は次の２＊ｎactual個のインターリーブ・ベクトルのエントリのマッピングを有することになる。最後のこの種のコア１６のマッピング後、インターリーブ・ベクトルはまだ幾つかのデータ値が空であるが、それぞれのコア１６は受け取る値の長さが均一のマッピングを有するはずである。インターリーブ・ステージ１６０はここで完了し、ステップ３５４で計算ステージ１７０中の畳み込みを行う準備が整う。
【００７８】
ところで、ステップ３５８の機能は、ステップ３５２の機能と同様だが、ただしｃutil中のそれぞれのコア１６にマッピングされる量は必ずしも同量ではないために、ここではインターリーブ・ベクトル・マッピングは、それほど単純明快ではない。冒頭から開始して、インターリーブ・ベクトルは、第１の畳み込みノードについて計算されたタップ数の２倍となる複数の値を受け取る。次いで第１のコアのマッピングが終了する時点から続けて、インターリーブ・ベクトルは、第２の畳み込みノードについて計算されたタップ数の２倍に等しい複数の値を受け取る。以降も同様である。すべてのマッピング終了後も、インターリーブ・ベクトルは幾つかのデータ値が空のままであるべきである。これでステップ３５８が行うステップは終了し、インターリーブ・ステージ１６０は完了し、ステップ３５４で計算ステージ１７０中の畳み込みを行う準備が整う。
【００７９】
ステップ３４８における決定からのどの経路も、畳み込みシーケンス（すなわちｃutil中のそれぞれのコア１６用の）中のそれぞれの特定のノードについてある程度のタップ数になる。ステップ３５４で、畳み込みプロセスで使用されるすべてのコア１６は、インターリーブ・ベクトルからの適切な長さの値でマッピングされるが、畳み込みに割り当てられるコア１６の第１、第２、第３などの記述は、ターゲット・アレイ１１４のダイ上の幾何学的配置に関して曖昧である。第１ノード、第２ノードなどと呼ばれるノードの配置は、畳み込みシーケンス中の第１のノードが他のノードを使用せずに外部入力デバイス（図２）に対するアクセスを有し、第２の畳み込みノードに対する直接アクセスを有することを必要とし、そのため第１の畳み込みノードがチップの周辺に配置されなければならないように、限定を受ける。直接アクセスとは、限定されないが、２つのノードが第３のノードを使用せずに通信できること、あるいは直接アクセスを有する２つのノードが同じデータ・バス１８を共有することを示す。畳み込みシーケンスのｃ番目のノードは他のノードを使用せずに外部出力デバイスに対するアクセスを有し、ｃ−１番目のノードに対する直接アクセスを有しなければならない。第２のノードからｃ−１番目のノードまでは、それぞれのノードが畳み込みシーケンス中で前のノードと次のノードに対する直接アクセスを有しなければならないという同じ特性を共に持つ。ｃのある値については、ターゲット・アレイ１１４に有効な配置を同等にもたらす、第１、第２からｃ番目のコアについて多くの可能な構成があることを当業者は理解するだろう。ここから、マッピング・ステージ１５０およびインターリーブ・ステージ１６０があり、計算ステージ１７０で、畳み込み値を実行する準備が整う。
【００８０】
図４は、本発明のＣＣＳ１００のインターリーブ・ステージ１６０がどのように動作可能かの事例を示すチャートである。ここで信号データ値についての信号ベクトル４６０と畳み込みデジタル・フィルタ係数値についての係数ベクトル４７０は、インターリーブされて、インターリーブ・ベクトル４８０を生成する。係数ベクトル４７０の長さのみが（図３のステップ３３４から）既知であり、信号データが実際は固定された長さを持たなくてよいが、信号ベクトル４６０の長さは係数ベクトル４７０の長さに適合されている。信号ベクトル４６０のエレメント４６２、４６４、４６６、および４６８は、第１、第２、第３、および最後の信号データ値に対応する。エレメント４６６および４６８の間に位置する領域、エレメント４８２は、図４に与えられた、文字通りの４つの値より多くの信号データ値用の場所を残す。同様に、係数ベクトル４７０のエレメント４７２、４７４、４７６、および４７８は第１、第２、第３、および最後の畳み込みデジタル・フィルタ係数値に対応し、およびエレメント４７６および４７８の間に位置する領域、エレメント４８４は、図４に与えられた、文字通りの４つの値以上の畳み込みデジタル・フィルタ係数値用の場所を残す。インターリーブは、処理結果のインターリーブ・ベクトル４８０がまずトップ・エレメント４６２を信号ベクトル４６０から受信し、次いでトップ・エレメント４７２を係数ベクトル４７０から受信し、このようにして信号データ値およびフィルタ係数値を最後の係数値４７８がインターリーブ・ベクトル４８０に移動するまで受信し続けるというように、実行される。勿論エレメント４８６でのインターリーブは、エレメント４８２および４８４に見出される任意の値もまた含めるべきである。
【００８１】
ここで、畳み込みに使用されることになるコア１６、およびこれらのコア１６に対するマッピングが均一または不均一であるかは既知である。さらに、全数のタップと空データ値のインターリーブの決定が実行されている。インターリーブのコアに対するマッピングを、マッピングが均一な場合と不均一な場合の両方について以下に説明する。以下の２つの部分で参照されているのは第１、第２、．．．ｃ−１番目、およびｃ番目ノードであるが、この参照は、コア１６の配置を示すものではない。むしろ第１コア、第２コアなどと呼ばれているコア１６の配置は、畳み込みシーケンス中の第１のノードは、外部入力デバイスに対するアクセスを有し、第２の畳み込みノードに対する直接アクセスを有することを必要とする、ように限定を受ける。ＳＥＡｆｏｒｔｈ２４Ａのようなデバイスの事例では、これは第１の畳み込みノードがチップ周辺に位置することを意味する。畳み込みシーケンスのｃ番目ノードは外部入力デバイスに対するアクセスを有すると共に、ｃ−１番目のノードに対する直接アクセスを有しなければならず、そのために第１の畳み込みノードのように周辺に位置しなければならない。ここで直接アクセスとは、２つのノードが第３のノードを使用せずに通信できることを意味する。第２のノードからｃ−１番目までのノードは、それぞれのノードが畳み込みシーケンス中で前のノードと次のノードに対して直接アクセスを有しなければならないという同じ特性を共に持つ。
【００８２】
コア１６に対するインターリーブの均一マッピングは、２つのインターリーブのうちのより簡単な方である。この場合は、第１の畳み込みノードはインターリーブ・ベクトルの最初の２＊ｎactual個のエレメントを含み、第２の畳み込みノードはインターリーブ・ベクトルの次の２＊ｎactual個のエレメントを含む、などとなる。インターリーブの手順が完了すると、すべてのコア１６は、まったく同じ長さのマッピングを収容し、インターリーブ・ベクトルは空であるものとする。
【００８３】
ここでは、不均一マッピングについて２つの小事例を述べる。第１の小事例はｎactual、ｍactualおよびｃutil、の値が十分に定義されているときのマッピングである。第１の畳み込みノードは、インターリーブ・ベクトルの第１の２＊ｎactual個のエレメントを備える。第２の畳み込みノードは、次のインターリーブ・ベクトルの２＊ｎactual個のエレメントを備える。以後同様である。このインターリーブ・ベクトルのマッピングは、最初のｃ−１個のノードについて同じように続き、ここでそれぞれの追加のノードがインターリーブ・ベクトルでの次の２＊ｎactual個のエレメントを受け取る。ｃ番目のノードは２＊ｍactual個のマッピングを受け取り、これは他のインターリーブ・ベクトルとまったく等しくなければならない。再びすべてのマッピングが終了すると、インターリーブ・ベクトルは空になるものとする。
【００８４】
第２の小事例は、一般的なマッピング・ガイドラインのみが与えられている場合のマッピングである。これは、均一マッピングに極力近いことが所望される場合のことであるが、多くの場合マッピングされるｃutil中のコア１６のｎactualについて少なくとも２つの異なる値が存在することに留意されたい。ｎactualの値が十分定義された後でも、同じ全体的なマッピングをもたらす多くのマッピングがなお存在する。そのため、明白なインターリーブマッピングは可能ではなく、やはりガイドラインに従うことができるのみである。第１の畳み込みノードから始めると、このノードはインターリーブ・ベクトルから、この特定ノードについてタップ実数の２倍を受信する。第２の畳み込みノードは、インターリーブ・ベクトルからの第１のノードのマッピングが終了したところから取られたインターリーブ・ベクトルから、この特定ノードについてタップ実数の２倍を受信する。同様に、ｃutil中のそれぞれの追加のコア１６は、先のものが終了した場所のインターリーブ・ベクトルから受信し、マッピングはこの特定ノードについてのタップ実数の２倍となる。
【００８５】
図５は、本発明のＣＣＳ１００の計算ステージ１７０の間の図２のターゲット・アレイ１１４からの特定の畳み込み計算ノード（ｃutil中のコア１６）の詳細な線図である。ここでエレメント５０２〜５２０は、図４のインターリーブ・ベクトル４７２から取られたインターリーブのエントリを格納するメモリ領域を表す。図５のコア１６に対する５つの信号データ値および５つの畳み込みデジタル・フィルタ係数値のこのマッピングは単に行われる可能性のあるマッピングの一例にすぎず、これより大きくまたは小さいマッピングもまたこの特定のコア１６に対して使用可能である。
【００８６】
図５のコア１６において、エレメント５０２、５０６、５１０、５１４、および５１８はそれぞれコア１６を介してわたされる信号データ値に対応し、エレメント５０４、５０８、５１２、５１６、および５２０は、それぞれ畳み込みプロセスの間に動かないという意味で固定されている畳み込みデジタル・フィルタ係数値に対応する。
【００８７】
図５のコア１６を通して畳み込みの１回のパスの間に、その結果得られた合計（resultant sum）が生成される。まずエレメント５０２と５０４の第１の積が、エレメント５２２にわたされる。次いでエレメント５０６と５０８の積がエレメント５２４にわたされ、ここでエレメント５２４は、この積をエレメント５２２中の値と一体化する。同様に、エレメント５１０と５１２の積がエレメント５２６にわたされ、エレメント５２６は、この積をエレメント５２４中の値と一体化する。同様にして、値がエレメント５２８および５３０に到達する。エレメント５３０が持つ値とエレメント５１８が持つ値は、このコア１６から別のコア１６にわたされる２つの値のみである。信号データ値およびフィルタ係数値を乗算し、この積を、先行する部分的な積和が存在すればこれに加算するこのプロセスは、畳み込みに使用される特定のコア１６内部に存在するすべての信号データとフィルタ係数の対について繰り返される。
【００８８】
ハイブリッドＦＩＲ畳み込みの例
以下は、ｃutil中のコア１６のすべてが適切なタップ数でマッピングされ、連続するコア１６間に必要な通信が行えるように配置されている適切なターゲット・アレイ１１４で実行される畳み込みの方法を説明する。用語「ビン」はコア１６の１つにおける、信号データ値または畳み込みデジタル・フィルタ係数値のいずれかの位置を意味する。
１．初期化
１ａ．「ｎ」個のデータ・サンプルのビンが「０」の数値を受け取る。
２．第１の部分合計ｐ0を計算する。
２ａ．第１の部分合計ｐ0の計算前に、第１のデータ・サンプルｄ0は、すべての既存のデータ・サンプルを次の使用可能なデータビン中に「プッシュする」態様で、データ・サンプル・ビンｂ0中に置かれる。
２ａｌ．まず、最後のデータ・サンプル・ビンｂnに見つかったデータ・サンプルが最後のデータ・サンプル・ビンからプッシュされ、実質的に捨てられる。
２ａ２．次いでデータ・サンプル・ビンｂn-1に見つかった値がデータ・サンプル・ビンｂｎに、プッシュされる。
２ａ３．同様にしてデータ・サンプル・ビンｂn-2に見つかった値がデータ・サンプル・ビンｂn-1に、プッシュされる。
２ａ４．データを次の使用可能なデータ・サンプル・ビンにプッシュするこのプロセスは、データ・サンプル・ビンｂ0が一切データを含まなくなるまで実行され、終了する。（何らデータを含まないデータ・サンプル・ビンは、値「０」を含むデータ・サンプル・ビンと同じではない。）
２ａ５．この時点で、第１のデータ・サンプルｄ0は、残りのデータビンに追加の変更を一切加えることなく、データ・サンプル・ビンｂ0にプッシュされる。
２ｂ．次いで、積が、フィルタ係数ビンｃ0およびデータ・サンプル・ビンｂ0に見出された値を被乗数として使用して算出され、これを積ａ0とする。
２ｃ．この処理結果の積を、フィルタ係数ビンｃ1およびデータ・サンプル・ビンｂ1に見出される値として定義される複数の被乗数の乗算として定義された第２の積に加算し、この結果第２の積ａ1が得られる。
２ｄ．先の積を新しい積に加算するこのプロセスは、積ａn-1が最後の積に加算されるまで繰り返され、ａnを示すことになる。
２ｅ．値ａnは、畳み込みのうちの第１の合計ｐ0に対して等価であると考えられる。
３．第２の部分合計ｐ1を算出する。
３ａ．ステップ２ａ１〜２ａ４を繰り返すプロセスを通して第２のデータ・サンプル値ｄ1を第１のデータ・サンプル・ビンｂ0に置く。
３ｂ．ステップ２ｂ〜２ｄを繰り返すことにより、第２の部分合計ｐ1を算出する。
４．部分合計の剰余を計算する。（本アルゴリズムは、無限の量の時間の間データを受け取り、そのために停止条件が要求されない畳み込みのアルゴリズムを記述する。）
４ａ．ステップ２ａ１〜２ａ４を繰り返すプロセスを通じて次のデータ・サンプルを第１のデータ・サンプル・ビンｂ0中に「プッシュする」ステップを繰り返す。
４ｂ．ステップ２ｂ〜２ｄを繰り返すことにより新しい部分合計を計算する。
【００８９】
ノード間のデータの伝送は、上記に記載されておらず、畳み込みを実行すること、フィルタの直接的表現を使用することのみが記載されている。代わりにフィルタが導関数表現（derivative representation）で表されている場合は、畳み込みを実行するのに以下の変更が必要である。
【００９０】
既存のステップ
３ｂ．ステップ２ｂ〜２ｄを繰り返すことにより第２の部分合計ｐ１を算出する。
４ｂ．ステップ２ｂ〜２ｄを繰り返すことにより新しい部分合計を算出する。
上記を次と置換する。
３ｂ．ステップ２ｂ〜２ｄを繰り返し、ステップ２ｂ〜２ｄからのこの値ｐ1を先に計算された部分合計ｐ0に加算することにより、第２の部分合計ｓ1を計算する。
４ｂ．ステップ２ｂ〜２ｄを繰り返し、ステップ２ｂ〜２ｄからのこの値を先に計算された部分合計に加算することにより、新しい部分合計を計算する。
【００９１】
図６Ａ−Ｂは、実質的に今述べたのと同じやり方のハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコード６００の２ページの表である。
【００９２】
要約すると、本発明は特に２つの原理を採用している。第１の原理は、アルゴリズムのうち、大きい方の部分を高速化した方が、小さい方の部分を大幅に高速化するより良いという原理である。第２の原理は、畳み込みアルゴリズムは、連続的および並列的エレメントの両方を有するということを認識し、受け入れることである。畳み込み値は、連続的な、すべての部分が次々計算される形で計算することができる。一方、これとは対極的に、すべての部分を同時にすなわち並列に計算することができる。または中間の手法を使用することもでき、この場合、一部を連続的に計算し一部を並列で計算する。ＣＣＳ１００は、一定量の連続的処理を保ちながらも、並列計算を実行する能力を提供し、これにより、使用される畳み込みアルゴリズムを実際に高速化することもなく、また、使用されるハードウェアの処理能力を増大させることもなく、畳み込みの速度を大幅に向上させることができる。
【００９３】
本発明の実施形態は、図２のシステム上で実行させると、上述したように、信号データ値および畳み込み係数値をアレイ１１４にマッピングするコンピュータ・プログラムを提供する。
【００９４】
本発明の実施形態は、図２のシステム上で実行させると、図６Ａおよび６Ｂについて上述したように、信号データ値および畳み込み係数値を畳み込み計算するコンピュータ・プログラムを与える。
【００９５】
さらに、畳み込み計算は、本発明の例にすぎず、ＣＣＳ１００はまた、連続的および並列的エレメントの両方を有する任意のタイプのアルゴリズムの性能を増大させる現実的手法も与えることも、今や理解されるべきである。
【００９６】
様々な実施形態を上に述べたが、これらは例としてのみ提示されたものであり、本発明の幅と範囲は上に述べた例示的実施形態のいずれにも限定されるものではないことが理解されるべきである。
【図面の簡単な説明】
【００９７】
【図１ａ】本発明による畳み込み計算システムがセットアップ演算、通常作業演算、および要約した演算をどのように実行するかの概観を模式的に示すブロック図である。
【図１ｂ】本発明による畳み込み計算システムがセットアップ演算、通常作業演算、および要約演算をどのように実行するかの概観を模式的に示すブロック図である。
【図２】（背景技術）図１ａにターゲット・アレイとして使用されているＳＥＡｆｏｒｔｈ２４Ａデバイスの主要な詳細を全体的に示す線図である。
【図３】図１ｂのマッピング・ステージの例示的実施形態がどのように実行されるかを示すフローチャートである。
【図４】図１ｂのインターリーブ・ステージがどのように作動するかの事例を示すチャートである。
【図５】図１ｂの計算ステージの間の図２のターゲット・アレイからの特定の畳み込み計算ノードの詳細な線図である。
【図６Ａ】ハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコードの２ページのリストである。
【図６Ｂ】ハイブリッドＦＩＲ畳み込みを実行するためのＦｏｒｔｈコードの２ページのリストである。
【符号の説明】
【００９８】
１００ 本発明の好ましい実施形態
１１２ ホスト・プロセッサ
１１４ ターゲット・アレイ
１６ コア
１８ データ・バス
１６１ 入力デバイス
２２１ 出力デバイス
３３０ 開始ステップ
３３２ （Ｓ）の入力
３３４ （Ｌ）の入力
３３６ （ｔ）の入力
３３８ （ｎmax）の入力
３４０ 入力が有効か？
３４２ マッピングの中止？
３４４ マッピングの停止
３４６ （ｃutil）の計算
３４８ ｃutilが整数値であるか？
３５０ ｎestの値をｃutilのすべてに使用
３５２ ｃutil中の各コア１６に対してインターリーブ・ベクトルをマッピングする
３５４ 通常畳み込み計算をすすめる
３５６ 例えば、ｎactualの値をコア１６のｃutil−１に使用し、異なるマッピングをｃutil中の（ｃ番目）の他のコア１６で使用する
３５８ ｃutil中の各コア１６に対してインターリーブ・ベクトルを、不均一にマッピングする
４６０ 信号ベクトル
４６２−４６８ 信号ベクトルのエレメント
４７０ 係数ベクトル
４７２−４７８ 係数ベクトルのエレメント
４８０ インターリーブ・ベクトル
４８２ 信号ベクトルのエレメント
４８６ 係数ベクトルのエレメント
５０２−５２０ インターリーブのエントリを格納するメモリ領域
５０２、５０６、５１０、５１４、５１８ 信号データ値の領域
５０４、５０８、５１２、５１６、５２０ 畳み込みデジタル・フィルタ係数値の領域
５２２ 積
５２４−５３０ 部分的な積合計
６００ Ｆｏｒｔｈコード
【特許請求の範囲】
【請求項１】
複数の信号データ値および複数の畳み込みフィルタ係数値を、畳み込み値を計算するための使用される複数のプロセッサからなる一組のプロセッサ（ｃutil）の１つである対象プロセッサ（ｃt）にロードするプロセスであって、
前記複数の係数値を前記ｃutilにマッピングすること、
前記ｃt中の前記複数のデータ値と複数の係数値のインターリーブを決定すること、
前記ｃtに前記複数の係数値をロードすること、および
前記ｃtに前記複数のデータ値をロードし、それによって前記畳み込み値の計算に参加するよう前記ｃtに準備させること
を含むことを特徴とするプロセス。
【請求項２】
ｎactualが前記ｃtにマッピングされたフィルタ値の実数、ｎestが前記ｃutilのそれぞれにマッピングされたフィルタ値の予測数であるとして、前記マッピングすることは、すべての前記ｃutilにわたって最も均一なマッピングを提供する前記ｎestを、前記ｎactualとなるように選択することを含むことを特徴とする請求項１に記載のプロセス。
【請求項３】
ｎtapsが前記ｃtにマッピングされたフィルタタップの数であり、ｎmaxが前記ｃtにマッピングされた係数値の最大数であり、Ｓが前記複数の信号データ値のサンプル速度を表し、ｔが前記ｃt中の２つの数を乗じるための時間を表し、Ａが前記ｃt中の前記サンプルおよび係数値の格納に使用可能なメモリを表し、Ｌが畳み込みについての積分核の時間窓を表すとして、
ｎtaps＝Ｓ＊ｔを決定すること、
ｎmax＝Ａ／２を決定すること、
ｎest＝ｍｉｎ（ｎtaps，ｎmax）を決定すること、および
ｃutil＝Ｌ／ｎestを決定すること
をさらに含むことを特徴とする請求項２に記載のプロセス。
【請求項４】
ｃutilが非整数値であるように決定された場合、ｎestを変更して、どれが前記最も均一なマッピングを提供するか見つけることをさらに含むことを特徴とする請求項３に記載のプロセス。
【請求項５】
前記決定することは、前記ｃtについての２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを含むことを特徴とする請求項１乃至４のいずれかに記載のプロセス。
【請求項６】
前記決定することは、前記ｃutilのそれぞれについて、それぞれ、２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを含むことを特徴とする請求項１乃至５のいずれかに記載のプロセス。
【請求項７】
前記畳み込みは、デジタル信号処理の過程の前記データ値に対するフィルタリング動作の一部であることを特徴とする請求項１乃至６のいずれかに記載のプロセス。
【請求項８】
複数の信号データ値および複数の畳み込みフィルタ係数値に基づき畳み込み値を計算するシステムであって、
使用される複数のプロセッサ（ｃutil）からなり、それぞれが順番に所与の時点で対象プロセッサ（ｃt）として見なすことが可能な一組のプロセッサと、
前記複数の係数値をｃutilにマッピングするロジックと、
前記ｃt中の前記複数のデータ値と前記複数の係数値のインターリーブを決定するロジックと、
前記ｃtに前記複数の係数値をロードするロジックと、および
前記ｃtに前記複数のデータ値をロードし、それにより畳み込み値の計算に参加するよう前記ｃtに準備させるロジックと
を備えることを特徴とするシステム。
【請求項９】
ｎactualが前記ｃtにマッピングされたフィルタ値の実数、ｎestが前記ｃutilのそれぞれにマッピングされたフィルタ値の予測数であるとして、前記マッピングを行うロジックは、さらにすべての前記ｃutilにわたって最も均一なマッピングを提供する前記ｎestを前記ｎactualとなるよう選択することを特徴とする請求項８に記載のシステム。
【請求項１０】
ｎtapsが前記ｃtにマッピングされたフィルタタップの数であり、ｎmaxが前記ｃtにマッピングされた係数値の最大数であり、Ｓが前記複数の信号データ値のサンプル速度を表し、ｔが前記ｃt中の２つの数を乗じるための時間を表し、Ａが前記ｃt中の前記サンプルおよび係数値の格納に使用可能なメモリを表し、Ｌが畳み込みについての積分核の時間窓を表すとして、前記マッピングを行うロジックはさらに、
ｎtaps＝Ｓ＊ｔを決定し、
ｎmax＝Ａ／２を決定し、
ｎest＝ｍｉｎ（ｎtaps，ｎmax）を決定し、および
ｃutil＝Ｌ／ｎestを決定する
ことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記マッピングを行うロジックは、さらに、ｃutilが非整数値である場合、ｎestを変更して、どれが前記最も均一なマッピングを提供するか見つけることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記決定するロジックはさらに、前記ｃtについての２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを特徴とする請求項８、９、１０または１１に記載のシステム。
【請求項１３】
前記決定するロジックはさらに、前記ｃutilのそれぞれについて、それぞれ、２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを特徴とする請求項８、９、１０、１１または１２に記載のシステム。
【請求項１４】
前記ｃutilは、単一のダイまたはモジュール内のすべてのコアであることを特徴とする請求項８、９、１０、１１、１２または１３に記載のシステム。
【請求項１５】
前記ｃutilは、単一のダイまたはモジュール内の、より大きな複数のコンピュータ化されたプロセッサ（ｃtotal）のサブセットであることを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記畳み込み値を計算する前記ｃutilから分離したホスト・システムをさらに備え、少なくともマッピングする前記ロジックおよび決定する前記ロジックは前記ホスト・システム内にあることを特徴とする請求項８乃至１５のいずれか一項に記載のシステム。
【請求項１７】
前記畳み込みは、デジタル信号プロセッサ内における複数のデータ値に関するフィルタ動作の一部であることを特徴とする請求項８乃至１６のいずれか一項に記載のシステム。
【請求項１８】
請求項１乃至６のいずれか一項に記載のプロセスに従って、信号から前記信号を表すデータ値を取り出すこと、および前記データ値を処理することを備えることを特徴とする信号を処理する方法。
【請求項１９】
信号から前記信号を表すデータ値を取り出す手段と、請求項８乃至１７のいずれか一項に記載のシステムに従ってデータ値を処理するシステムとを備えることを特徴とする信号プロセッサ。
【請求項２０】
コンピュータのアレイで実行させると、アレイに請求項１乃至７および請求項１８のいずれか一項に記載のプロセスを実施させることを特徴とするコンピュータ・プログラム。
【請求項２１】
請求項２０記載のプログラムを備えることを特徴とするキャリア。
【請求項２２】
信号、記憶媒体またはメモリ・デバイスであることを特徴とする請求項２１記載のキャリア。
【請求項１】
複数の信号データ値および複数の畳み込みフィルタ係数値を、畳み込み値を計算するための使用される複数のプロセッサからなる一組のプロセッサ（ｃutil）の１つである対象プロセッサ（ｃt）にロードするプロセスであって、
前記複数の係数値を前記ｃutilにマッピングすること、
前記ｃt中の前記複数のデータ値と複数の係数値のインターリーブを決定すること、
前記ｃtに前記複数の係数値をロードすること、および
前記ｃtに前記複数のデータ値をロードし、それによって前記畳み込み値の計算に参加するよう前記ｃtに準備させること
を含むことを特徴とするプロセス。
【請求項２】
ｎactualが前記ｃtにマッピングされたフィルタ値の実数、ｎestが前記ｃutilのそれぞれにマッピングされたフィルタ値の予測数であるとして、前記マッピングすることは、すべての前記ｃutilにわたって最も均一なマッピングを提供する前記ｎestを、前記ｎactualとなるように選択することを含むことを特徴とする請求項１に記載のプロセス。
【請求項３】
ｎtapsが前記ｃtにマッピングされたフィルタタップの数であり、ｎmaxが前記ｃtにマッピングされた係数値の最大数であり、Ｓが前記複数の信号データ値のサンプル速度を表し、ｔが前記ｃt中の２つの数を乗じるための時間を表し、Ａが前記ｃt中の前記サンプルおよび係数値の格納に使用可能なメモリを表し、Ｌが畳み込みについての積分核の時間窓を表すとして、
ｎtaps＝Ｓ＊ｔを決定すること、
ｎmax＝Ａ／２を決定すること、
ｎest＝ｍｉｎ（ｎtaps，ｎmax）を決定すること、および
ｃutil＝Ｌ／ｎestを決定すること
をさらに含むことを特徴とする請求項２に記載のプロセス。
【請求項４】
ｃutilが非整数値であるように決定された場合、ｎestを変更して、どれが前記最も均一なマッピングを提供するか見つけることをさらに含むことを特徴とする請求項３に記載のプロセス。
【請求項５】
前記決定することは、前記ｃtについての２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを含むことを特徴とする請求項１乃至４のいずれかに記載のプロセス。
【請求項６】
前記決定することは、前記ｃutilのそれぞれについて、それぞれ、２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを含むことを特徴とする請求項１乃至５のいずれかに記載のプロセス。
【請求項７】
前記畳み込みは、デジタル信号処理の過程の前記データ値に対するフィルタリング動作の一部であることを特徴とする請求項１乃至６のいずれかに記載のプロセス。
【請求項８】
複数の信号データ値および複数の畳み込みフィルタ係数値に基づき畳み込み値を計算するシステムであって、
使用される複数のプロセッサ（ｃutil）からなり、それぞれが順番に所与の時点で対象プロセッサ（ｃt）として見なすことが可能な一組のプロセッサと、
前記複数の係数値をｃutilにマッピングするロジックと、
前記ｃt中の前記複数のデータ値と前記複数の係数値のインターリーブを決定するロジックと、
前記ｃtに前記複数の係数値をロードするロジックと、および
前記ｃtに前記複数のデータ値をロードし、それにより畳み込み値の計算に参加するよう前記ｃtに準備させるロジックと
を備えることを特徴とするシステム。
【請求項９】
ｎactualが前記ｃtにマッピングされたフィルタ値の実数、ｎestが前記ｃutilのそれぞれにマッピングされたフィルタ値の予測数であるとして、前記マッピングを行うロジックは、さらにすべての前記ｃutilにわたって最も均一なマッピングを提供する前記ｎestを前記ｎactualとなるよう選択することを特徴とする請求項８に記載のシステム。
【請求項１０】
ｎtapsが前記ｃtにマッピングされたフィルタタップの数であり、ｎmaxが前記ｃtにマッピングされた係数値の最大数であり、Ｓが前記複数の信号データ値のサンプル速度を表し、ｔが前記ｃt中の２つの数を乗じるための時間を表し、Ａが前記ｃt中の前記サンプルおよび係数値の格納に使用可能なメモリを表し、Ｌが畳み込みについての積分核の時間窓を表すとして、前記マッピングを行うロジックはさらに、
ｎtaps＝Ｓ＊ｔを決定し、
ｎmax＝Ａ／２を決定し、
ｎest＝ｍｉｎ（ｎtaps，ｎmax）を決定し、および
ｃutil＝Ｌ／ｎestを決定する
ことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記マッピングを行うロジックは、さらに、ｃutilが非整数値である場合、ｎestを変更して、どれが前記最も均一なマッピングを提供するか見つけることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記決定するロジックはさらに、前記ｃtについての２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを特徴とする請求項８、９、１０または１１に記載のシステム。
【請求項１３】
前記決定するロジックはさらに、前記ｃutilのそれぞれについて、それぞれ、２＊ｎactual個のエレメントを含むインターリーブ・ベクトルを構築することを特徴とする請求項８、９、１０、１１または１２に記載のシステム。
【請求項１４】
前記ｃutilは、単一のダイまたはモジュール内のすべてのコアであることを特徴とする請求項８、９、１０、１１、１２または１３に記載のシステム。
【請求項１５】
前記ｃutilは、単一のダイまたはモジュール内の、より大きな複数のコンピュータ化されたプロセッサ（ｃtotal）のサブセットであることを特徴とする請求項１４に記載のシステム。
【請求項１６】
前記畳み込み値を計算する前記ｃutilから分離したホスト・システムをさらに備え、少なくともマッピングする前記ロジックおよび決定する前記ロジックは前記ホスト・システム内にあることを特徴とする請求項８乃至１５のいずれか一項に記載のシステム。
【請求項１７】
前記畳み込みは、デジタル信号プロセッサ内における複数のデータ値に関するフィルタ動作の一部であることを特徴とする請求項８乃至１６のいずれか一項に記載のシステム。
【請求項１８】
請求項１乃至６のいずれか一項に記載のプロセスに従って、信号から前記信号を表すデータ値を取り出すこと、および前記データ値を処理することを備えることを特徴とする信号を処理する方法。
【請求項１９】
信号から前記信号を表すデータ値を取り出す手段と、請求項８乃至１７のいずれか一項に記載のシステムに従ってデータ値を処理するシステムとを備えることを特徴とする信号プロセッサ。
【請求項２０】
コンピュータのアレイで実行させると、アレイに請求項１乃至７および請求項１８のいずれか一項に記載のプロセスを実施させることを特徴とするコンピュータ・プログラム。
【請求項２１】
請求項２０記載のプログラムを備えることを特徴とするキャリア。
【請求項２２】
信号、記憶媒体またはメモリ・デバイスであることを特徴とする請求項２１記載のキャリア。
【図１ａ】
【図１ｂ】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図１ｂ】
【図２】
【図３】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【公開番号】特開２００９−３７５９０（Ｐ２００９−３７５９０Ａ）
【公開日】平成２１年２月１９日（２００９．２．１９）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−９８９１９（Ｐ２００８−９８９１９）
【出願日】平成２０年４月７日（２００８．４．７）
【出願人】（５０７１０１５４３）テクノロジー プロパティーズ リミテッド (12)
【Ｆターム（参考）】
【公開日】平成２１年２月１９日（２００９．２．１９）
【国際特許分類】
【出願番号】特願２００８−９８９１９（Ｐ２００８−９８９１９）
【出願日】平成２０年４月７日（２００８．４．７）
【出願人】（５０７１０１５４３）テクノロジー プロパティーズ リミテッド (12)
【Ｆターム（参考）】
[ Back to top ]