(57)【特許請求の範囲】
【請求項１】
ＡポートとＢポートとＣポートとを含む複数のＩ／Ｏポートをそれぞれ有するＺ個の実行ユニットＰ（１）〜Ｐ（Ｚ）を用いて、Ｙ個の処理ステージで、Ｎ個のデータポイントを高速フーリエ変換を用いて処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれの前記Ａポートに動作可能に接続されたアドレシング可能なメモリユニットＡ（１）〜Ａ（Ｚ）と、
前記該実行ユニットＰ（１）〜Ｐ（Ｚ）のそれぞれのＢポートに動作可能に接続されたアドレシング可能なメモリユニットＢ（１）〜Ｂ（Ｚ）と、
前記各メモリユニットＡ（１）〜Ａ（Ｚ）に前記Ｎ個のデータポイントを等しく分配するデータルータと、
前記各メモリユニットＡ（１）〜Ａ（Ｚ）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記メモリユニットＡ（１）〜Ａ（Ｚ）の全てに供給する第１のアドレスジェネレータＡＧ−Ａと、
前記各メモリユニットＢ（１）〜Ｂ（Ｚ）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記メモリユニットＢ（１）〜Ｂ（Ｚ）の全てに供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、
前記実行ユニットＰ（１）〜Ｐ（Ｚ）のそれぞれのＣポートには、前記高速フーリエ変換におけるバタフライ演算のひねり因子係数が供給され、
前記各メモリユニットＡ（１）〜Ａ（Ｚ）のそれぞれは、前記データルータによってＮ／Ｚ個のデータポイントをそれぞれ受け取り、
前記第１および第２のアドレスジェネレータＡＧ−ＡおよびＡＧ−Ｂのそれぞれによって供給されるシーケンスで前記各メモリユニットＡ（ｑ）とＢ（ｑ）との間（但し、ｑは、１≦ｑ≦Ｚの任意の整数）でデータを動かすことによって、前記実行ユニットＰ（ｑ）における前記Ｙ個の処理ステージのそれぞれで、前記Ｎ個のデータポイントがＺ個のデータポイント並列ストリームで前記バタフライ演算処理されることを特徴とするデータ処理システム。
【請求項２】
前記メモリユニットＡ（１）〜Ａ（Ｚ）およびＢ（１）〜Ｂ（Ｚ）のそれぞれが単一ポートメモリである、請求項１に記載のデータ処理システム。
【請求項３】
ＡポートとＢポートとＣポートとを含む複数のＩ／Ｏポートをそれぞれ有する４個の実行ユニットＰ（１）〜Ｐ（４）を用いて、Ｙ個の処理ステージで、Ｎ個のデータポイントを高速フーリエ変換を用いて処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれの前記Ａポートに動作可能に接続されたアドレシング可能なメモリユニットＡ（１）〜Ａ（４）と、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれの前記Ｂポートに動作可能に接続されたアドレシング可能なメモリユニットＢ（１）〜Ｂ（４）と、
前記各メモリユニットＡ（１）〜Ａ（４）に、前記Ｎ個のデータポイントを等しく分配するデータルータと、
前記各メモリユニットＡ（１）〜Ａ（４）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記メモリユニットＡ（１）〜Ａ（４）の全てに供給する第１のアドレスジェネレータＡＧ−Ａと、
前記各メモリユニットＢ（１）〜Ｂ（４）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記各メモリユニットＢ（１）〜Ｂ（４）の全てに供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれのＣポートには、前記高速フーリエ変換におけるバタフライ演算のひねり因子係数が供給され、
前記各メモリユニットＡ（１）〜Ａ（４）のそれぞれは、前記データルータによって２５６個のデータポイントをそれぞれ受け取り、
前記第１および第２のアドレスジェネレータＡＧ−ＡおよびＡＧ−Ｂのそれぞれによって供給されるシーケンスで前記各メモリユニットＡ（ｑ）とＢ（ｑ）との間（但し、ｑは、１≦ｑ≦４の任意の整数）でデータを動かすことによって、前記実行ユニットＰ（ｑ）における前記Ｙ個の処理ステージのそれぞれで、前記Ｎ個のデータポイントが４個のデータポイント並列ストリームで前記バタフライ演算処理されることを特徴とするデータ処理システム。
【請求項４】
ＡポートとＢポートとＣポートとを含む複数のＩ／Ｏポートをそれぞれ有する４個の実行ユニットＰ（１）〜Ｐ（４）を用いて、Ｙ個の処理ステージで、１０２４個のデータポイントを高速フーリエ変換を用いて処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれの前記Ａポートに動作可能に接続されたアドレシング可能なメモリユニットＡ（１）〜Ａ（４）と、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれの前記Ｂポートに動作可能に接続されたアドレシング可能なメモリユニットＢ（１）〜Ｂ（４）と、
前記各メモリユニットＡ（１）〜Ａ（４）に、前記１０２４個のデータポイントを２５６個ずつ等しく分配するデータルータと、
前記各メモリユニットＡ（１）〜Ａ（４）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記メモリユニットＡ（１）〜Ａ（４）の全てに供給する第１のアドレスジェネレータＡＧ−Ａと、
前記各メモリユニットＢ（１）〜Ｂ（４）に動作可能に接続され、前記Ｙ個の処理ステージで使用される同じアドレスシーケンスを前記各メモリユニットＢ（１）〜Ｂ（４）の全てに供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、
前記実行ユニットＰ（１）〜Ｐ（４）のそれぞれのＣポートには、前記高速フーリエ変換におけるバタフライ演算のひねり因子係数が供給され、
前記各メモリユニットＡ（１）〜Ａ（４）のそれぞれは、前記データルータによって２５６個のデータポイントをそれぞれ受け取り、
前記第１および第２のアドレスジェネレータＡＧ−ＡおよびＡＧ−Ｂのそれぞれによって供給されるシーケンスで前記各メモリユニットＡ（ｑ）とＢ（ｑ）との間（但し、ｑは
、１≦ｑ≦４の任意の整数）でデータを動かすことによって、前記実行ユニットＰ（ｑ）における前記Ｙ個の処理ステージのそれぞれで、前記１０２４個のデータポイントが４個の２５６データポイント並列ストリームで前記バタフライ演算処理されることを特徴とするデータ処理システム。
【請求項５】
前記メモリユニットＡ（１）〜Ａ（４）およびＢ（１）〜Ｂ（４）のそれぞれが単一ポートメモリである、請求項４に記載のデータ処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ処理システムに関し、具体的には、高データレートアプリケーションにおける、データ待ち時間およびスループットに関する厳しい要件を満たす、高速フーリエ変換（ＦＦＴ）を用いた並列システムに関する。
【０００２】
【従来の技術】
セクションＩ．イントロダクション
ＳｈａｒｐＬＨ９１２４ＦＦＴプロセッサは、レーダー、医療用画像処理、電気通信等のアレイ信号処理アプリケーションにおいて広く使用されている。
【０００３】
ＦＦＴアルゴリズム本来のパイプライン構造のため、ハイエンドＤＳＰアプリケーションのデータスループットを高めるためには、パイプラインシステム（ＢｕｔｔｅｒａｌｙＤＳＰＤＳＰＭＡＸ−Ｖ４およびＣａｔａｌｉｎａＲｅｓｅａｒｃｈＩｎｃ．ＣＲＣＶ１Ｍ４０／５０等）を構築するのが普通である。しかし、データ待ち時間は並列アーキテクチャによってのみ向上され得る。
通常、データ管理は、並列システムの性能低下要因である。多次元、マルチチャネルまたはマルチレートＤＳＰアプリケーションにおいてデータアドレシングシーケンスを処理するアルゴリズムが無い場合にも、ＦＦＴを用いた並列システムを規定する際に問題が生じる。本発明は、この問題を解決するものである。本願は、並列および多次元の問題におけるデータの分割(data partitioning)および管理に関する処理についての新規なアプローチおよびアルゴリズムを提案する。一例として、ＳｈａｒｐＬＨ９３２０アドレスジェネレータを用いて並列データシーケンスを制御することによって、実際の並列システム設計に関する問題についても記載される。
【０００４】
本願においては、効率的な並列ＦＦＴインプリメンテーション（implementation）のための、データ分割およびデータ通信に関する問題の制御に焦点が置かれる。ＦＦＴが優れている点は、ひねり因子(twiddle factor)行列因数分解に見ることができる。セクションＩＩにおいて、どのように行列を分割すれば、インプリメンテーションのための良好な構造を得ることができるのかを記載する。１次元および２次元の両方を、同様のベクトル行列形式で表すことができることを示す。さらにバタフライ演算およびＩ／Ｏデータ転送を複数の行列によって別々に表すことができる。セクションＩＩＩにおいては、ＬＨ９１２４／ＬＨ９３２０チップセットに基づいたバイパス形式ＦＦＴインプリメンテーションを記載する。セクションＩＶにおいては、単一のプロセッサの通常ＦＦＴアドレシングから並列ＦＦＴアドレシングシーケンスを導出する。セクションＶにおいては、バイパス形式並列ＦＦＴシステムを構築する２つの方法を記載する。最終的な結論をセクションＶＩにおいて述べる。
【０００５】
一般に、デジタル信号処理（ＤＳＰ）タスクは、時間領域または周波数領域において行われる。時間領域とは、データを連続的にサンプルし、その後のデジタル処理のために量子化する場合を指す。周波数領域とは、時間的に並べられた元のデータシーケンスを、特定の周波数および振幅を持つ１組のスペクトルに変換する場合を指す。これらのデータもまた、さらなる処理のために量子化される。多くのＤＳＰタスクにおいては、時間領域においてシーケンシャルに並べられたデータポイントを処理するよりも、周波数領域においてスペクトルを処理する方が、より多くの見通しが得られるとともに、より処理し易い問題解決方法が得られる。従って、どのようにすればより効率的に時間領域データを周波数領域データに変換できるかが問題となる。
【０００６】
この変換を行うために用いられる最も一般的なアルゴリズムは、高速フーリエ変換またはＦＦＴと呼ばれるものである。
【０００７】
ＦＦＴは、始めに、より一般的な形式である離散フーリエ変換と呼ばれる処理を行い、その後、その演算結果が、最も一般的には２つの入力データポイントにのみ行われる不可約カーネル演算(irreducible kernel operation)を伴って１つになるまで細分化(subdivision)することによって行われる。この演算は、それを記述する際に用いられる信号フロー図の形から「バタフライ演算」と呼ばれている。最も単純なバタフライ演算（「基底数２(Radix-2)」）の場合、２つのデータポイントの和および差に係数「ひねり」因数を掛ける。その後、この２つのデータポイントについてのデータ順シーケンスを出力時に交換する。この演算を信号フロー図に表したときに、この交換または交叉(crossover)の部分が「バタフライ（蝶々）」を想起させる。
【０００８】
時間領域データセット全体に対して、１度に２データポイントずつ、バタフライ処理を連続的に施し、この処理を複数回または「複数パス(pass)」繰り返す（このとき、部分的に変換された以前の演算パス結果を用いる）ことによって時間領域データが周波数領域データに変換される。基底数２の場合、そのデータセット全体について１対毎に行われる演算（バタフライ演算）の所要パス数は、その基底数を底とする、そのデータ組のデータポイント数の対数に等しい。２基底バタフライ演算(Radix-2 butterfly calculation)の場合は２を底とする対数に等しい。１０２４個のデータポイントを持つデータセットの場合、２を底とする１０２４の対数は１０（２10＝１０２４）であるので、１０２４ポイント（「１Ｋ」）ＦＦＴの算出は、そのデータの１０パスおよびその中間演算結果を要する。よって、１０２４個の時間領域データポイントの変換が、１０×１０２４＝１０２４０回の２基底バタフライ演算を要することが分かる。
【０００９】
最も基本的な基底数２以外の他の基底数を用いることも可能である。その物理的な解釈は以下の通りである。基底数２は、一度に２つの数を処理するバタフライ演算であり、基底数４は、一度に４つの数を処理するより高次元のバタフライ演算であり、基底数１６は、一度に１６個の数を処理するさらに高次元のバタフライ演算であり、より大きい基底数についても同様である。より大きな基底数の演算の利点は、そのデータに対するパスの数が少なくて済む点である。なぜなら、パスを決定する項（基底数を底とする対数）がより小さな数だからである。例えば、２５６ポイントの２基底ＦＦＴは、８パス（２8＝２５６）を要するが、同じデータに対するＦＦＴの基底数１６の評価(evaluation)は２パス（１６2＝２５６）で済む。従って、２基底バタフライ演算の場合と同等の時間／クロック／データポイントで１６基底バタフライの評価を可能にする十分な計算資源がある場合、１６基底バタフライを用いたＦＦＴ演算の方がより高速である。
【００１０】
ＦＦＴ演算の一般的な形は、バイパス形式と呼ばれる。この演算形式の場合、ある決まったデータパスによってバタフライ演算を行うが、データは外部メモリから供給される。データパスは、そこに与えられたデータに対してある決まった組の演算（バタフライ演算）を行う。従って、このデータパスによるバイパスＦＦＴによって、適切なパスのためにこれらの外部メモリにおいてデータを適切に順序付けることが必要である。
【００１１】
ＬＨ９１２４は、ＦＦＴを行うバイパス形式プロセッサの一例である。ＬＨ９１２４は４つのデータポート：Ｑ、Ａ、ＢおよびＣを有する。データは、Ｑ（取得）ポートに入力される。入力データに対する最初のバタフライ演算パスの結果は、ポートＢに出力される。次のバタフライ演算パスにおいて、部分的に変換されたデータを、ポートＢに接続されたメモリから読出し、処理し、そして、ポートＡに接続されたメモリに出力する。以降のパスにおいては、データをポートＡとポートＢの間で「往来(ping-pong)」させる。ポートＣは係数データの入力に使用する。
【００１２】
所与の演算にかかった時間は、待ち時間またはスループットと表され得る。待ち時間とは、初期状態から、初めの有効出力データが得られるまでにかかる時間である。スループットとは、システムが起動し、走っている状態になってから以降の各データ出力間の時間である。
【００１３】
バイパスを用いたシステムのＦＦＴ速度を向上させる方法は主に３つある：
１．基底数の次数を大きくすることによりデータに対する所要パス数を低減する。このアプローチは待ち時間およびスループットの両方を改善するが、各処理要素に必要となる計算資源の点で費用が高い。
【００１４】
２．データパスプロセッサをカスケード（パイプライン）化することにより、各プロセッサが１ＦＦＴパス分のみの演算を行うようにし、異なるデータブロックに対してそのパスを反復的に演算する。カスケード化は、スループットを向上するが、待ち時間は改善されない。従って、初めの１回のＦＦＴは、適切な数のパスまたはカスケード化されたステージによって処理しなければならない。２番目以降の各ＦＦＴは、初めのＦＦＴの１／Ｎ（Ｎはステージ数）の時間で出力される。
【００１５】
３．データパスプロセッサを並列化することにより、１回の大きなＦＦＴをＮ回の比較的小さなＦＦＴに分割する。すると、元の比較的大きなデータ組に対して適切な数のパスがやはり必要であるが、各データパスプロセッサは、元の１／Ｎの大きさになったＦＦＴの演算に割り当てられる。この構成によれば、待ち時間およびスループットの両方が改善する。各データパスプロセッサは、元のポイント数の１／Ｎのポイント数を処理すれば済むので、待ち時間が改善する。これと同じ理由（データパスプロセッサ毎のポイント数が比較的少ない）で、スループットも向上する。
【００１６】
カスケード化と並列処理とを組み合わせることも可能である。
【００１７】
【発明が解決しようとする課題】
本発明は、上記事情に鑑みてなされたものであり、その目的とするところは、（１）データパスプロセッサの並列接続によってＦＦＴ演算における待ち時間を最小化すること、（２）１つのアドレスシーケンサを、並列化された全てのデータパスプロセッサの同じデータポートに使用可能にすることによって、システム接続を単純化すること、および（３）並列データパス接続に通常の単一ポートＳＲＡＭを使用できるようにすることによって、システム設計を単純化することである。
【００１８】
【課題を解決するための手段】
本発明によるデータ処理システムは、ＡポートおよびＢポートを含む複数のＩ／Ｏポートをそれぞれ有するＺ個の実行ユニットＰ（１）〜Ｐ（Ｚ）を用いて、Ｙ個の処理ステージで、Ｎ個のデータポイントを処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、該実行ユニットのそれぞれの該Ａポートおよび該Ｂポートのそれぞれに設けられるアドレシング可能なメモリユニットであって、それぞれ該実行ユニットＰ（１）〜Ｐ（Ｚ）のＡポートに動作可能に接続されるメモリユニットＡ（１）〜Ａ（Ｚ）、および、それぞれ該実行ユニットＰ（１）〜Ｐ（Ｚ）のＢポートに動作可能に接続されるメモリユニットＢ（１）〜Ｂ（Ｚ）を有し、該メモリユニットＡ（ｑ）およびＢ（ｑ）の間で、各実行ユニットＰ（ｑ）を通して、選択されたシーケンスで、データを動かすことによって、該Ｙ個の処理ステージでデータを処理する、アドレシング可能なメモリユニットと、メモリユニットＡ（１）〜Ａ（Ｚ）間に該Ｎ個のデータポイントを分配するデータルータであって、該メモリユニットのそれぞれはＮ／Ｚ個のデータポイントを受け取り、該実行ユニットＰ（１）〜Ｐ（Ｚ）のそれぞれはＮ／Ｚ個のデータポイントを含むデータポイントブロックを該Ｙ個の処理ステージで処理し、該処理は並列して行われる、データルータと、該メモリユニットＡ（１）〜Ａ（Ｚ）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＡ（１）〜Ａ（Ｚ）に供給する第１のアドレスジェネレータＡＧ−Ａと、該メモリユニットＢ（１）〜Ｂ（Ｚ）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＢ（１）〜Ｂ（Ｚ）に供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、該アドレスジェネレータＡＧ−Ａは、該メモリユニットＡ（１）〜Ａ（Ｚ）の全てに同じアドレスシーケンスを供給し、該アドレスジェネレータＡＧ−Ｂは、該メモリユニットＢ（１）〜Ｂ（Ｚ）の全てに同じアドレスシーケンスを供給し、これにより、該Ｎ個のデータポイントが該Ｚ個の実行ユニットを通してＺ個の並列ストリームで処理される。
【００１９】
前記アドレシング可能なメモリユニットのそれぞれが単一ポートメモリであってもよい。
【００２０】
本発明によるデータ処理システムは、ＡポートおよびＢポートを含む複数のＩ／Ｏポートをそれぞれ有する４個の実行ユニットＰ（１）〜Ｐ（４）を用いて、Ｙ個の処理ステージで、Ｎ個のデータポイントを処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、該実行ユニットのそれぞれの該Ａポートおよび該Ｂポートのそれぞれに設けられるアドレシング可能なメモリユニットであって、それぞれ該実行ユニットＰ（１）〜Ｐ（４）のＡポートに動作可能に接続されるメモリユニットＡ（１）〜Ａ（４）、および、それぞれ該実行ユニットＰ（１）〜Ｐ（４）のＢポートに動作可能に接続されるメモリユニットＢ（１）〜Ｂ（４）を有し、該メモリユニットＡ（ｑ）およびＢ（ｑ）の間で、各実行ユニットＰ（ｑ）を通して、選択されたシーケンスで、データを動かすことによって、該Ｙ個の処理ステージでデータを処理する、アドレシング可能なメモリユニットと、メモリユニットＡ（１）〜Ａ（４）間に該Ｎ個のデータポイントを分配するデータルータであって、該メモリユニットのそれぞれはＮ／４個のデータポイントを受け取り、該実行ユニットＰ（１）〜Ｐ（４）のそれぞれはＮ／４個のデータポイントを含むデータポイントブロックを該Ｙ個の処理ステージで処理し、該処理は並列して行われる、データルータと、該メモリユニットＡ（１）〜Ａ（４）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＡ（１）〜Ａ（４）に供給する第１のアドレスジェネレータＡＧ−Ａと、該メモリユニットＢ（１）〜Ｂ（４）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＢ（１）〜Ｂ（４）に供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、該アドレスジェネレータＡＧ−Ａは、該メモリユニットＡ（１）〜Ａ（４）の全てに同じアドレスシーケンスを供給し、該アドレスジェネレータＡＧ−Ｂは、該メモリユニットＢ（１）〜Ｂ（４）の全てに同じアドレスシーケンスを供給し、これにより、該Ｎ個のデータポイントが該４個の実行ユニットを通して４回の並列ストリームで処理される。
【００２１】
本発明によるデータ処理システムは、ＡポートおよびＢポートを含む複数のＩ／Ｏポートをそれぞれ有する４個の実行ユニットＰ（１）〜Ｐ（４）を用いて、Ｙ個の処理ステージで、１０２４個のデータポイントを処理する、デジタル信号処理アプリケーションに使用されるデータ処理システムであって、該実行ユニットのそれぞれの該Ａポートおよび該Ｂポートのそれぞれに設けられるアドレシング可能なメモリユニットであって、それぞれ該実行ユニットＰ（１）〜Ｐ（４）のＡポートに動作可能に接続されるメモリユニットＡ（１）〜Ａ（４）、および、それぞれ該実行ユニットＰ（１）〜Ｐ（４）のＢポートに動作可能に接続されるメモリユニットＢ（１）〜Ｂ（４）を有し、該メモリユニットＡ（ｑ）およびＢ（ｑ）の間で、各実行ユニットＰ（ｑ）を通して、選択されたシーケンスで、データを動かすことによって、該Ｙ個の処理ステージでデータを処理する、アドレシング可能なメモリユニットと、メモリユニットＡ（１）〜Ａ（４）間に該１０２４個のデータポイントを分配するデータルータであって、該メモリユニットのそれぞれは２５６個のデータポイントを受け取り、該実行ユニットＰ（１）〜Ｐ（４）のそれぞれは２５６個のデータポイントを含むデータポイントブロックを該Ｙ個の処理ステージで処理し、該処理は並列して行われる、データルータと、該メモリユニットＡ（１）〜Ａ（４）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＡ（１）〜Ａ（４）に供給する第１のアドレスジェネレータＡＧ−Ａと、該メモリユニットＢ（１）〜Ｂ（４）に動作可能に接続され、該Ｙ個の処理ステージで使用される該アドレスシーケンスを該メモリユニットＢ（１）〜Ｂ（４）に供給する第２のアドレスジェネレータＡＧ−Ｂとを備え、該アドレスジェネレータＡＧ−Ａは、該メモリユニットＡ（１）〜Ａ（４）の全てに同じアドレスシーケンスを供給し、該アドレスジェネレータＡＧ−Ｂは、該メモリユニットＢ（１）〜Ｂ（４）の全てに同じアドレスシーケンスを供給し、これにより、該１０２４個のデータポイントが該４個の実行ユニットを通して４個の２５６データポイント並列ストリームで処理される。
【００２２】
前記アドレシング可能なメモリユニットＡ（１）〜Ａ（４）およびＢ（１）〜Ｂ（４）のそれぞれが単一ポートメモリであってもよい。
【００２３】
【発明の実施の形態】
セクションＩＩ．ＦＦＴの分割および導出
Ｎポイントシーケンス｛ｘ（ｎ）｝の離散フーリエ変換（ＤＦＴ）は以下のように定義される。
【００２４】
【数１】
0003749022.tif 000002
但し、
【００２５】
【数２】
0003749022.tif 000003
である。従って、ＤＦＴのベクトル行列形式は、
【００２６】
【数３】
0003749022.tif 000004
と表すことができる。但し、Ｘ＿およびｘ＿（本願においては、「Ｘ」等の文字の下にアンダースコアを付した記号の代わりに、その文字の後に「＿」を付している）はＮポイントのベクトルであり、ＴＷNはＮ×Ｎのひねり因子行列である。ひねり因子行列自体を再帰的に分解することはできない。実際には、ＤＦＴからＦＦＴへの分解の際に主要な役割を果たすのは、ビット逆行列(bit-reverse matrix)または桁反転行列(digit-reverse matrix)である。
【００２７】
ビット逆入力および線形出力（ＢＩ／ＬＯ）ＦＦＴアルゴリズムは、
【００２８】
【数４】
0003749022.tif 000005
のごとく、ひねり因子行列にＮ×Ｎビット逆行列Ｐbrを右から掛けた(post-multiplication)ものを因数分解することによって得られる。行列ＴNは、
【００２９】
【数５】
0003749022.tif 000006
の再帰方程式(recursive equation)によって因数分解することができる。但し、ＩN、ＡN、ＴNおよび０はＮ×Ｎの行列である。ＩNは単位行列であり、
０Nは零行列である。行列ＡN/2は、
【００３０】
【数６】
0003749022.tif 000007
の対角行列である。ＴNおよびＴN/2の要素は、
【００３１】
【数７】
0003749022.tif 000008
の関係を有する。
【００３２】
１次元ＦＦＴインプリメンテーション
本セクションでは、ＢＩ／ＬＯＦＦＴのひねり因子行列因数分解（数５）をさらに分割できることを示す。従って、各バタフライステージを、バタフライ演算行列および出力接続行列(output interconnection matrix)の前の入力接続行列(input interconnection matrix)によって表すことができる。ＦＦＴアルゴリズムインプリメンテーションの重要な物理的意味の一部を、バタフライステージの３行列表記を通して見ることができる。
【００３３】
再帰的因数分解方程式（数５）を（数３）に挿入し、データ長Ｎ＝２Sを設定すれば、
【００３４】
【数８】
0003749022.tif 000009
のようなカスケード化されたバタフライステージ行列によってＤＦＴを表すことができる。但し、Ｘ＿およびｘ＿は、それぞれＮポイント線形出力ベクトルおよびＮポイント線形入力ベクトルを表す。ＦＧk（ＢＳ（ｋ））は、ＦＦＴアルゴリズムの第ｋステージを表す。
【００３５】
【数９】
0003749022.tif 000010
のように、ＦＦＴの各ステージをさらに３つの行列（入力接続を示す右側順序行列、バタフライを示す中央行列、および出力接続を示す左側順序行列）に分割できる。
【００３６】
Ｐrkは入力とバタフライモジュールとの間の接続を特定する順序行列である。Ｐlkはバタフライモジュールと出力との間の接続を特定する順序行列である。配置済みアルゴリズム(in-placealgorithm)を用いる場合、左側順序行列Ｐlkは右側順序行列Ｐrkの転置行列である。ＢＩ（ｋ）は、第ｋステージバタフライ演算行列であり、ブロック対角行列である。
【００３７】
２次元ＦＦＴインプリメンテーション
通常は、信号フロー図（ＳＦＧ）を用いてＦＦＴアルゴリズムを表す。上記において、多次元ＦＦＴを１次元ＳＦＧにマッピングできることを示した。全ての多次元ＦＦＴアルゴリズムをベクトル行列形式で表すことも可能である。
このことから、次数に関係なく、データ数が同じ全てのＦＦＴが、同じ順序行列を有し得ることが導出される。これは、ＦＦＴが同じＳＦＧ構造を共有していることを意味する。さらに、１次元〜多次元のＦＦＴの第ｋステージのバタフライ順序（接続）行列は同じである。これらの結果は、１次元ＦＦＴのアドレシングを多次元ＦＦＴのアドレシングに利用し得ることを示唆している。１次元ＦＦＴと多次元ＦＦＴとの唯一の差は、多次元ＦＦＴがＳＦＧにおけるひねり因子係数であることである。
【００３８】
行列アプローチにおいて、Ｎ1ＸＮ2＝Ｎの２次元アレイが与えられれば、Ｎ2１次元行ＦＦＴ（ｒｆｆｔ）およびＮ1１次元列ＦＦＴ（ｃｆｆｔ）を計算することができる。このことから、Ｎポイント１次元ＦＦＴの第１ｓ1ステージによってＮ2ｒｆｆｔを、そして、Ｎポイント１次元ＦＦＴの第１ｓ2ステージによってＮ1ｃｆｆｔを実行できることが導出される（但し、Ｎ1＝２s1およびＮ2＝２s2）。ｒｆｆｔおよびｃｆｆｔを（数８）によって実行し、転置行列をｃｆｆｔと組み合わせれば、
【００３９】
【数１０】
0003749022.tif 000011
のように、２次元ＦＦＴのベクトル行列形式を得ることができる。但し、
【００４０】
【数１１】
0003749022.tif 000012
は、線形出力アレイの行優先のＮポイントベクトルであり、
【００４１】
【数１２】
0003749022.tif 000013
は、ビット逆入力アレイの行優先のＮポイントベクトルである。（数１０）および（数８）を比較すると、Ｎ1×Ｎ2２次元ＦＦＴは、Ｎポイント１次元ＦＦＴと同じ接続構造を有している。さらに、行ＦＦＴ、列ＦＦＴおよび１次元ＦＦＴの第ｋステージについて、バタフライ処理行列は同じである。
【００４２】
実際のインプリメンテーションにおいては、１次元〜多次元ＦＦＴの統一ベクトル行列表記は、全てのＦＦＴについて、その次元に関係なく、データ、ひねり因子およびビット反転を含む１次元アドレシングシーケンスを用いることができることを示唆している。従って、１次元ＦＦＴ用に指定された並列ＦＦＴシステムは、自動的に、より高次のＦＦＴに対して実行可能である。
【００４３】
セクションＩＩＩ．バイパス形式によって実行されるＦＦＴ
バイパス形式ＦＦＴインプリメンテーションの場合、データパス内に構築されたオンチップＲＡＭおよびＦＦＴバタフライモジュールはない。バイパス形式インプリメンテーションは、より単純であり、ＦＦＴ構造の信号フローまたはデータフローからマッピングされる。ＳｈａｒｐＬＨ９１２４／ＬＨ９３２０ＦＦＴプロセッサは、ＦＦＴ信号フローを実行する典型的なバイパス形式構造である。以下では、ＳｈａｒｐＬＨ９１２４／ＬＨ９３２０ＦＦＴチップセットを用いて、待ち時間を低減する並列ＦＦＴインプリメンテーションを説明する。
【００４４】
セクションＩＩでは、１次元ＦＦＴおよび２次元ＦＦＴの両方がベクトル行列形式によって表され得ることを示した。バタフライ演算行列は、それぞれ、１つのＬＨ９１２４命令で実行できる。さらに、入力または出力順序行列は、それぞれ、１つのＬＨ９３２０命令で実行できる。従って、少数の命令によって、提案されたアルゴリズムに基づいてこれらのアプリケーションを実行することができる。従って、バイパス形式インプリメンテーションによって、システムおよびアプリケーションの設計時間費用が大幅に低減される。
【００４５】
ＬＨ９１２４実行ユニット
ＬＨ９１２４は、４つのＩ／Ｏポート：Ｑ、Ａ、ＢおよびＣを有する。各ポートは４８ビット（２４ビットの実バス、２４ビットの仮想バス）を有し、複素数データおよびひねり因子係数を伝送する。各ポートは、（数９）に示すようなバタフライ演算行列ＢＩ（ｋ）を実行するために、内蔵型４基底バタフライデータパスを有する。正しいデータおよびひねり因子のシーケンスが与えられる限り、ＦＦＴインプリメンテーションの大きさに制限はない。ＬＨ９１２４の場合、各バタフライ演算行列は、１つのＬＨ９１２４命令によってマッピングおよび実行される。例えば、４ｋポイントＦＦＴを３つの１６基底バタフライステージによって実行する場合、その演算は３つの命令で済む。
【００４６】
汎用ＤＳＰとは異なり、ＬＨ９１２４の場合、単一のプロセッサを用いて大きなＦＦＴ演算を行うためのデータ分割を考慮する必要がない。ＦＦＴは、１バタフライステージ毎に演算される。（数８）および（数９）から、ＦＦＴが本来パイプライン構造であることを理解することができる。バイパス形式のＦＦＴプロセッサの利点は、入力データスループットを高めるために、並列パイプラインアーキテクチャを容易に構築できる点である。データメモリに往来(ping-pong)アプローチを用い、プロセッサの数がバタフライステージの数Ｎに等しい場合、スループットはＮ倍向上する。例えば、ＣａｔａｌｉｎａＲｅｓｅａｒｃｈＣＲＣＶ１Ｍ４０／５０は、１〜６個のカスケード化ＬＨ９１２４ステージを有し得る。３つの１６基底バタフライステージによって実行される４ＫポイントＦＦＴの場合、スループットは、３段(three-deep)パイプラインＬＨ９１２４アーキテクチャによって３倍向上し得る。
【００４７】
ＬＨ９３２０メモリ管理ユニット
ＬＨ９３２０メモリ管理ユニットは、ＬＨ９１２４実行ユニットが必要とする入力および出力データアドレスシーケンスを提供する。（数９）から、順序行列ＰlkおよびＰrkは、ＬＨ９３２０の命令セットによってマッピングおよび実行される。各命令は、１つのアドレスシーケンスを生成し、シーケンスの大きさはＦＦＴの大きさと同等のパラメータＮによって規定され得る。
【００４８】
ＬＨ９３２０は、混合基底ＦＦＴ処理のためのデータシーケンスを提供する。配置済みアルゴリズムを使用しているので、入力および出力データシーケンスは同じになり、順序行列ＰlkはＰrkの転移となる。２基底ＦＦＴの場合、第ｉステージのデータシーケンスを生成するアルゴリズムは、
【００４９】
【数１３】
0003749022.tif 000014
となる。４基底ＦＦＴの場合、第ｉステージのデータシーケンスを生成するアルゴリズムは、
【００５０】
【数１４】
0003749022.tif 000015
となる。１６基底ＦＦＴの場合、第ｉステージのデータシーケンスを生成するアルゴリズムは、
【００５１】
【数１５】
0003749022.tif 000016
となる。
【００５２】
セクションＩＶ．ＦＦＴ並列処理
（数８）および（数９）から、ＦＦＴアルゴリズムは、バイパス形式のパイプライン化されたアーキテクチャによる実行に非常に適していることが分かる。現バタフライステージの出力データを、次のステージの入力データとして直接使用することができる。データスループットは、パイプライン化アーキテクチャまたは並列アーキテクチャによって改善させ得る。しかし、ＦＦＴ演算の待ち時間は、パイプライン構造によっては改善できない。並列アーキテクチャは、待ち時間を改善させ得る唯一の方法である。待ち時間を向上させために、どのようにして直接的に並列構造をとるのかについては、（数８）および（数９）からは自明ではない。データのシャフリングはステージ毎に異なる。従って、並列アーキテクチャによってＦＦＴを実行する場合、データスクランブルに注意する必要がある。
【００５３】
本セクションでは、ＬＨ９３２０を用いてどのようにＦＦＴ演算用並列アーキテクチャを設計して待ち時間を低減するのかを説明する。効率的なＦＦＴ並列処理を行うには、データ分割が鍵になる。バタフライ演算行列ＢＩ（ｋ）がブロック対角行列であることが導出される。さらに、入力および出力順序行列ＰlkおよびＰrkは、一定パターンの繰返し構造を持つ。従って、各ステージにおいて慎重にデータを分割すれば、並列演算構造を得ることができる。ＬＨ９３２０命令セットによっても、データアドレスシーケンスを複数の並列データアドレスシーケンスに分割することができる。Ｐ個（但し、Ｐは２の累乗）のＬＨ９１２４を有する並列ＦＦＴアーキテクチャがあるとする。Ｐ個の並列アドレシングシーケンスを導出することが可能である。２基底ＦＦＴの場合、第ｉステージの並列アドレシングシーケンスは、
【００５４】
【数１６】
0003749022.tif 000017
のように、第ｉステージのＬＨ９３２０の２基底命令ＢＦ２ｉから導出することができる。
【００５５】
４基底ＦＦＴの場合、第ｉステージの並列アドレシングシーケンスは、
【００５６】
【数１７】
0003749022.tif 000018
のように、第ｉステージのＬＨ９３２０の４基底命令ＢＦ４ｉから導出することができる。
【００５７】
１６基底ＦＦＴの場合、第ｉステージの並列アドレシングシーケンスは、
【００５８】
【数１８】
0003749022.tif 000019
のように、第ｉステージのＬＨ９３２０の１６基底命令ＢＦ１６ｉから導出することができる。
【００５９】
同様に、並列桁反転アドレシングシーケンスを、ＬＨ９３２０桁反転シーケンス命令から、導出することができる。
【００６０】
【数１９】
0003749022.tif 000020
のような、ＭステージのＦＦＴの桁反転シーケンスがあるとする。ｎMが基底数Ｐを有する場合、上記のシーケンスを、
【００６１】
【数２０】
0003749022.tif 000021
のようなＰ個の並列サブシーケンスに分割することができる。
【００６２】
セクションＶ．並列ＦＦＴインプリメンテーション
最近になるまで、並列ＦＦＴインプリメンテーション（特に、バイパス形式構造）に関する研究はあまり行われていなかった。バイパス形式の利点は、並列およびパイプラインシステムアーキテクチャを構築することによって容易に高スループットおよび低待ち時間の厳しい要件を満たすことができる点である。本セクションでは、どのようにしてマルチプレクサまたはデュアルポートメモリを用いて、ＬＨ９１２４／ＬＨ９３２０チップセットを有するＦＦＴ並列システムを構築するのかを説明する。重要な点は、どのようにして、実行に適した場所および適した時間にデータを配置するかである。
【００６３】
マルチプレクサを用いた並列ＬＨ９１２４
本サブセクションでは、マルチプレクサを用いてどのように並列ＦＦＴ演算に必要なデータ通信を制御するのかを説明する。説明の便宜上、並列プロセッサの数は４とし、ＦＦＴの大きさを４Ｋとする。４つのＬＨ９１２４を用いたシステム構成を図１に示す。図示した、各ポートにおける各プロセッサのためのローカルメモリは、１ｋポイントの複素数データを格納する。始めに、入力データはＡポートメモリに格納される（例えば、第１データはＡ１、第２データはＡ２、．．．に格納される）。
【００６４】
セクションＩＶより、Ｐ＝４に設定することによって、ＬＨ９３２０桁反転シーケンス命令から桁反転サブシーケンスを得ることができる。ＬＨ９３２０を１つだけ用いて４つのＡポートローカルメモリを制御することができる。なぜなら、入力アドレシングシーケンスは、全てのプロセッサについて同じだからである。後段のバタフライステージにおいて、各プロセッサがそのプロセッサのローカルメモリだけを使用するように、Ｂポートメモリに格納されるデータを配置しなければならない。さらに、セクションＩＶで説明した２基底、４基底または１６基底バタフライの並列命令を使用することができる。従って、マルチプレクサは、ＬＨ９１２４のＢポートに配置され、第１ステージのバタフライ処理において使用される。これらのマルチプレクサは、各プロセッサの出力における第（４ｉ＋ｋ）データ（但し、ｉ＝０、１、２、．．．、１０２３、且つｋ＝０、１、２、３）が第ｋローカルメモリにロードされるように予定されている。図１には、ＬＨ９３２０に接続されるいくつかのバッファが図示されている。これらのバッファは、データシーケンスのインターリーブを制御するために使用される。
【００６５】
４つのＬＨ９１２４によって４ＫポイントＦＦＴを実行するために、ＬＨ９１２４およびＬＨ９３２０が使用する命令を表１に示す。ＬＨ９３２０が使用する表１の命令を参照すれば、１つのプロセッサが命令ＢＦ４ｉを使用すると、４つの並列プロセッサが、セクションＶＩＩにおいて導出されるように命令ＢＦ４（ｉ−１）を使用することが分かる。４つの並列ＬＨ９１２４について、各プロセッサは、各ステージ毎に、４Ｋポイントのデータではなく、１Ｋポイントのデータを演算する。従って、４つの並列プロセッサの待ち時間は、１つのプロセッサの場合と比べて４倍向上する。システムクロックが５０ＭＨｚであるとすると、４ＫポイントＦＦＴを完了するのにかかる時間は、ＬＨ９１２４が１つの場合には２５０μｓであり、４つの並列ＬＨ９１２４の場合には６６μｓである。
【００６６】
【表１】
0003749022.tif 000022
本願において、用語「実行ユニット」、「プロセッサ」、「ＬＨ９１２４」、「データパスプロセッサ」および「ＬＨ９１２４ＦＦＴプロセッサ」は交換可能に用いられている。これらの用語は、デジタル信号処理（ＤＳＰ）を行うための演算ユニットを指す。集積回路チップ上に形成されるデジタル信号プロセッサは、ＤＳＰチップと呼ばれる。用語「アドレスジェネレータ」および「ＬＨ９３２０」も、本願において交換可能に用いられている。メモリユニットＡ（１）〜Ａ（４）を、図１に、ブロック「メモリＡ１」〜「メモリＡ４」のブロックで示す。メモリユニットＢ（１）〜Ｂ（４）を、図１に、ブロック「メモリＢ１」〜「メモリＢ４」のブロックで示す。実行ユニットＰ（１）〜Ｐ（４）を、図１に、「ＬＨ９１２４Ｐ１」〜「ＬＨ９１２４Ｐ４」のブロックで示す。アドレスジェネレータＡＧ−ＡおよびＡＧ−Ｂを、図１に、それぞれ「ＬＨ９３２０Ａポート」および「ＬＨ９３２０Ｂポート」のブロックで示す。
【００６７】
図１に示すプロセッサコンフィギュレーションを用いた本発明による並列ＤＳＰ演算の実施例を以下に示す。以下の実施例においては、各アドレスジェネレータを用いて４つのメモリにアドレスを供給することが可能である。この４つのメモリのそれぞれは、４つの並列実行ユニット上のポート（例えば、ＡポートまたはＢポート）に接続される。本実施例においては、４つの実行ユニットを用いて、１０２４個のデータポイントを処理し、これにより、４つの並列パスにおいて最大５ステージ分の処理を行う。各実行ユニットは２５６個のデータポイントを処理する。
【００６８】
並列システムインプリメンテーションの一形態を以下に示す。説明の便宜上、所望の変換サイズを１Ｋとし、並列データパスプロセッサの数を４つとする。このようなシステム構成を添付の図面に示す。２つのメモリポートＡおよびＢを考える。
【００６９】
先ず、どのようにすれば１つのＬＨ９１２４によって１ＫポイントＦＦＴを実行できるのかを説明する。その後、どのようにすれば４つの並列ＬＨ９１２４によって１ＫポイントＦＦＴを実行できるのかを説明する。システム図に関しては、図１を参照されたい。
【００７０】
ＬＨ９１２４を、４つのＩ／Ｏポート（Ａ、Ｂ、ＣおよびＱ）を持つブラックボックスとして見ることができる。例として、Ｃポートを、ＦＦＴひねり因子係数用の使用に限定する。残りの３つのデータポート（Ａ、ＢおよびＱ）のいずれを用いてデータを入力してもよく、その残りの２つのデータポートのいずれかを用いてデータを出力することができる。
【００７１】
動作の概説（単一データプロセッサ対並列データパスプロセッサ）
本実施例では、１ＫＦＦＴを考える。
【００７２】
単一データパスプロセッサ概説
プロセッサが１つ（単一プロセッサ）の場合、各ステージにおけるデータシーケンスは、以下のようになる。
【００７３】
【数２１】
0003749022.tif 000023
【００７４】
【数２２】
0003749022.tif 000024
【００７５】
【数２３】
0003749022.tif 000025
【００７６】
【数２４】
0003749022.tif 000026
【００７７】
【数２５】
0003749022.tif 000027
並列データパスインプリメンテーション概説
４つのＬＨ９１２４を用いた並列システムインプリメンテーションの場合、以下に示すように、０〜２５５の位置においてメモリバンクに複素数データを格納することができる。
【００７８】
【数２６】
0003749022.tif 000028
従って、バンク１の第ｉ位置には第ｉデータがあり、バンク２の第ｉ位置には第（ｉ＋２５６）データがあり、バンク３の第ｉ位置には第（ｉ＋５１２）データがあり、バンク４の第ｉ位置には第（ｉ＋７６８）データがある。
【００７９】
上記において説明したステージ４から、各バンクは、各４基底バタフライモジュール演算について１つのデータを提供しなければならない。さらに、データ０、２５６、５１２および７６８の第１モジュール演算においては、データが各バンクの第１の位置からのものでなければならないことが分かる。ＬＨ９１２４は、各サイクル毎に１つのデータしか受け取らないので、データはインターリーブでメモリバンクに入れる。同様に、他のモジュール演算についても、データは各バンクの同位置から、インターリーブ方式で入れる。
【００８０】
本願の図１に示すアーキテクチャは、上記段落で説明した概念を実現したものである。図示するバッファは、メモリバンクインターリーブを実現するものである。ここでは、通常の単一ポートＳＲＡＭを用いている。各モジュール演算のためのデータは各バンクの同位置からのものであるので、アドレスジェネレータは１つだけでよいことが分かる。
【００８１】
１ＫＦＦＴ（１データパスプロセッサ（９１２４））の詳細な説明
本実施例においては、４基底バタフライ命令を用いて、１ＫポイントＦＦＴを実現する。従って、５パス分の４基底バタフライ演算を行う。ＬＨ９１２４は、４基底バタフライ実行エンジンとみなすことができる。各４基底バタフライ演算には、４つのデータポイントが必要となる。従って、各パスについて２５６（１０２４／４）回の４基底バタフライ演算を行うことになる。この４基底バタフライ実行エンジンは、そのパスにおける最後のデータまで、割込み(interruption)なしで４基底バタフライ演算を行う。データフロー命令は、各パスの入力および出力ポートを規定する。
【００８２】
Ｂポートにおいて、データは、ｂ（０）、ｂ（１）、ｂ（２）、ｂ（３）、．．．、ｂ（１０２１）、ｂ（１０２２）、ｂ（１０２３）のようなシーケンスで格納されているものとする。
ステージ０：
入力ポート：Ｂ
出力ポート：Ａ
データフロー命令：ＲＢＷＡ（Ｒｅａｄ  Ａ  Ｗｒｉｔｅ  Ｂ）
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４０（桁反転シーケンス中にデータを仮定）
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４０
（配置済みＦＦＴアルゴリズムを用いているので、入力および出力が同一のアドレシング命令を用いることができる）
アドレシングシーケンスは、０、１、２、３、４、５、．．．、１０１９、１０２０、１０２１、１０２２、１０２３のようになる。
【００８３】
第１の４基底バタフライ実行では第１の４つの入力データ０、１、２、３を使用し、第２のバタフライでは、次の４つのデータ４、５、６、７、を使用する。これ以降も同様である。第１の入力データがＬＨ９１２４に入ってから１８サイクル後に、出力結果を収集することができる。第１の４つの出力データが、第１の４基底バタフライの実行結果であり、次の４つのデータが、第２の４基底バタフライの実行結果である。出力データは、０、１、２、３、４、．．．、１０２１、１０２２、１０２３のようなアドレスシーケンスでＡポートメモリに格納される。
ステージ１：
入力ポート：Ａ（入力ポートは、１つ前の演算ステージまたはパスの出力ポートである）
出力ポート：Ｂ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４１
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４１
（配置済みＦＦＴアルゴリズムを用いているので、入力および出力が同一のアドレシング命令を用いることができる）
アドレシングシーケンスは、以下のようになる。
【００８４】
【数２７】
0003749022.tif 000029
第１の４基底バタフライ実行では、メモリアドレス０、４、８および１２にある第１の４つの入力データを使用し、第２のバタフライでは、メモリアドレス１６、２０、２４および２８にある次の４つのデータを使用する。これ以降も同様である。ＬＨ９１２４に入る第１の入力データから１８サイクル後に、出力結果を収集することができる。第１の４つの出力データが、第１の４基底バタフライの実行結果であり、次の４つのデータが、第２の４基底バタフライの実行結果である。出力データは、入力アドレスシーケンスと同様のアドレスシーケンスでＢポートメモリに格納される。
ステージ２：
入力ポート：Ｂ（入力ポートは、１つ前のステージの出力ポートである）
出力ポート：Ａ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４２
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４２
（配置済みＦＦＴアルゴリズムを用いているので、入力および出力が同一のアドレシング命令を用いることができる）
アドレシングシーケンスは、以下のようになる。
【００８５】
【数２８】
0003749022.tif 000030
第１の４基底バタフライ実行では、メモリアドレス０、１６、３２および４８にある第１の４つの入力データを使用し、第２のバタフライでは、メモリアドレス６４、８０、９６および１１２にある次の４つのデータを使用する。これ以降も同様である。第１の入力データがＬＨ９１２４に入ってから１８サイクル後に、出力結果を収集することができる。第１の４つの出力データが、第１の４基底バタフライの実行結果であり、次の４つのデータが、第２の４基底バタフライの実行結果である。出力データは、入力アドレスシーケンスと同様のアドレスシーケンスでＡポートメモリに格納される。
ステージ３：
入力ポート：Ａ（入力ポートは、１つ前のステージの出力ポートである）
出力ポート：Ｂ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４３
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４３
（配置済みＦＦＴアルゴリズムを用いているので、入力および出力が同一のアドレシング命令を用いることができる）
アドレシングシーケンスは、以下のようになる。
【００８６】
【数２９】
0003749022.tif 000031
第１の４基底バタフライ実行では、メモリアドレス０、６４、１２８および１９２にある第１の４つの入力データを使用し、第２のバタフライでは、メモリアドレス２５６、３２０、３８４および４４８にある次の４つのデータを使用する。これ以降も同様である。第１の入力データがＬＨ９１２４に入ってから１８サイクル後に、出力結果を収集することができる。第１の４つの出力データが、第１の４基底バタフライの実行結果であり、次の４つのデータが、第２の４基底バタフライの実行結果である。出力データは、入力アドレスシーケンスと同様のアドレスシーケンスでＢポートメモリに格納される。
ステージ４：
入力ポート：Ｂ（入力ポートは、１つ前のステージの出力ポートである）
出力ポート：Ａ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４４
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４４
（配置済みＦＦＴアルゴリズムを用いているので、入力および出力が同一のアドレシング命令を用いることができる）
アドレシングシーケンスは、以下のようになる。
【００８７】
【数３０】
0003749022.tif 000032
第１の４基底バタフライ実行では、メモリアドレス０、６４、１２８および１９２にある第１の４つの入力データを使用し、第２のバタフライでは、メモリアドレス２５６、３２０、３８４および４４８にある次の４つのデータを使用する。これ以降も同様である。第１の入力データがＬＨ９１２４に入ってから１８サイクル後に、出力結果を収集することができる。第１の４つの出力データが、第１の４基底バタフライの実行結果であり、次の４つのデータが、第２の４基底バタフライの実行結果である。出力データは、入力アドレスシーケンスと同様のアドレスシーケンスでＡポートメモリに格納される。
【００８８】
４つの並列ＬＨ９１２４によって実現される１ＫポイントＦＦＴの詳細な説明
便宜上、入力データは既に桁反転の順序になっているものと仮定する。但し、本発明の実施形態はこれに限定されない。４つのＬＨ９１２４プロセッサのＢポートに格納されるデータを以下のように配列することができる。
プロセッサ１のＢポートのメモリバンク１：ｂ（０）、ｂ（１）、ｂ（２）、ｂ（３）、ｂ（４）、．．．、ｂ（２５３）、ｂ（２５４）、ｂ（２５５）
プロセッサ２のＢポートのメモリバンク２：ｂ（２５６）、ｂ（２５７）、ｂ（２５８）、ｂ（２５９）、ｂ（２６０）、．．．、ｂ（５０９）、ｂ（５１０）、ｂ（５１１）
プロセッサ３のＢポートのメモリバンク３：ｂ（５１２）、ｂ（５１３）、ｂ（５１４）、ｂ（５１５）、ｂ（５１６）、．．．、ｂ（７６５）、ｂ（７６６）、ｂ（７６７）
プロセッサ４のＢポートのメモリバンク４：ｂ（７６８）、ｂ（７６９）、ｂ（７７０）、ｂ（７７１）、ｂ（７７２）、．．．、ｂ（１０２１）、ｂ（１０２２）、ｂ（１０２３）
４基底バタフライ命令を用いて１Ｋポイント並列ＦＦＴを実行する。５つの４基底バタフライステージが必要である。しかし、各ステージにおいて、各ＬＨ９１２４は、１０２４個のデータではなく、２５６個のデータを演算する。
【００８９】
各ステージにおける演算は以下のようになる。
ステージ０：
入力ポート：Ｂ
出力ポート：Ａ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４０
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４０
各バンクにおけるアドレシングシーケンスは、０、１、２、３、４、５、．．．、２５１、２５２、２５３、２５４、２５５のようになる。
【００９０】
データパスプロセッサ１について、第１の４つの入力データは０、１、２、３であり、第２の４つの入力データは４、５、６、７である。これ以降も同様である。
【００９１】
データパスプロセッサ２について、第１の４つの入力データは２５６、２５７、２５８、２５９であり、第２の４つの入力データは２６０、２６１、２６２、２６３である。これ以降も同様である。
【００９２】
データパスプロセッサ３について、第１の４つの入力データは５１２、５１３、５１４、５１５であり、第２の４つの入力データは５１６、５１７、５１８、５１９である。これ以降も同様である。
【００９３】
データパスプロセッサ４について、第１の４つの入力データは７６８、７６９、７７０、７７１であり、第２の４つの入力データは７７２、７７３、７７４、７７５である。これ以降も同様である。
【００９４】
１８サイクル後から、Ａポートからの出力結果を得始める。結果は、入力ポートと同様のアドレスシーケンスでＡポートメモリに格納される。
ステージ１：
入力ポート：Ａ
出力ポート：Ｂ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４１
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４１
アドレシングシーケンスは、以下のようになる。
【００９５】
【数３１】
0003749022.tif 000033
データパスプロセッサ１について、第１の４つの入力データは０、４、８、１２であり、第２の４つの入力データは１６、２０、２４、２８である。これ以降も同様である。
【００９６】
データパスプロセッサ２について、第１の４つの入力データは２５６、２６０、２６４、２６８であり、第２の４つの入力データは２７２、２７６、２８０、２８４である。これ以降も同様である。
【００９７】
データパスプロセッサ３について、第１の４つの入力データは５１２、５１６、５２０、５２４であり、第２の４つの入力データは５２８、５３２、５３６、５４０である。これ以降も同様である。
【００９８】
データパスプロセッサ４について、第１の４つの入力データは７６８、７７２、７７６、７８０であり、第２の４つの入力データは７８４、７８８、７９２、７９６である。これ以降も同様である。
【００９９】
１８サイクル後から、Ｂポートからの出力結果を得始める。結果は、入力ポートと同様のアドレスシーケンスでＢポートメモリに格納される。
ステージ２：
入力ポート：Ｂ
出力ポート：Ａ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４２
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４２
アドレシングシーケンスは、以下のようになる。
【０１００】
【数３２】
0003749022.tif 000034
データパスプロセッサ１について、第１の４つの入力データは０、１６、３２、４８であり、第２の４つの入力データは６４、８０、９６、１１２である。これ以降も同様である。
【０１０１】
データパスプロセッサ２について、第１の４つの入力データは２５６、２７２、２８８、３０４、であり、第２の４つの入力データは３２０、３３６、３５２、３６８である。これ以降も同様である。
【０１０２】
データパスプロセッサ３について、第１の４つの入力データは５１２、５２８、５４４、５６０であり、第２の４つの入力データは５７６、５９２、６０８、６２４である。これ以降も同様である。
【０１０３】
データパスプロセッサ４について、第１の４つの入力データは７６８、７８４、８００、８１６であり、第２の４つの入力データは８３２、８４８、８６４、８８０である。これ以降も同様である。
【０１０４】
１８サイクル後から、Ａポートからの出力結果を得始める。結果は、入力ポートと同様のアドレスシーケンスでＡポートメモリに格納される。
ステージ３：
入力ポート：Ａ
出力ポート：Ｂ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４３
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４３
アドレシングシーケンスは、以下のようになる。
【０１０５】
【数３３】
0003749022.tif 000035
データパスプロセッサ１について、第１の４つの入力データは０、６４、１２８、１９２であり、第２の４つの入力データは１、６５、１２９、１９３である。これ以降も同様である。
【０１０６】
データパスプロセッサ２について、第１の４つの入力データは２５６、３２０、３８４、４４８、であり、第２の４つの入力データは２５７、３２１、３８４、４４８である。これ以降も同様である。
【０１０７】
データパスプロセッサ３について、第１の４つの入力データは５１２、５７６、６４０、７０４であり、第２の４つの入力データは５１３、５７７、６４１、７０５である。これ以降も同様である。
【０１０８】
データパスプロセッサ４について、第１の４つの入力データは７６８、８３２、８９６、９６０であり、第２の４つの入力データは７６９、８３３、８９７、９６１である。これ以降も同様である。
【０１０９】
１８サイクル後から、Ｂポートからの出力結果を得始める。結果は、入力ポートと同様のアドレスシーケンスでＢポートメモリに格納される。
ステージ４：
入力ポート：Ｂ
出力ポート：Ａ
データフロー命令：ＲＢＷＡ
ＬＨ９１２４実行命令：ＢＦＬＹ４
ＢポートＬＨ９３２０アドレシング命令：ＢＦ４０
ＡポートＬＨ９３２０アドレシング命令：ＢＦ４３
このステージでのみ、遅延バッファおよびスイッチング回路を使用する。
（本願において、遅延バッファおよびスイッチング回路は第１ステージにおいて使用する。結果は同じである。ここでは、本アプローチの説明および理解の便宜上、順番を逆にしている。）
入力アドレシングシーケンスは、０、１、２、３、４、５、．．．、２５２、２５３、２５４、２５５のようになる。
【０１１０】
データパスプロセッサ１は、０、４、８、１２、．．．、２４４、２４８、２５２のようなシーケンスを用いる。
【０１１１】
従って、第１の４基底バタフライは４つの全てのバンクのアドレス０から４つのデータを取得し、第２の４基底バタフライは４つの全てのバンクのアドレス４から４つのデータを取得する。これ以降も同様である。
【０１１２】
データパスプロセッサ２は、１、５、９、１３、．．．、２４５、２４９、２５３のようなシーケンスを用いる。
【０１１３】
従って、第１の４基底バタフライは４つの全てのバンクのアドレス１から４つのデータを取得し、第２の４基底バタフライは４つの全てのバンクのアドレス５から４つのデータを取得する。これ以降も同様である。
【０１１４】
データパスプロセッサ３は、２、６、１０、１４、．．．、２４６、２５０、２５４のようなシーケンスを用いる。
【０１１５】
従って、第１の４基底バタフライは４つの全てのバンクのアドレス２から４つのデータを取得し、第２の４基底バタフライは４つの全てのバンクのアドレス６から４つのデータを取得する。これ以降も同様である。
【０１１６】
データパスプロセッサ４は、３、７、１１、１５、．．．、２４７、２５１、２５５のようなシーケンスを用いる。
【０１１７】
従って、第１の４基底バタフライは４つの全てのバンクのアドレス３から４つのデータを取得し、第２の４基底バタフライは４つの全てのバンクのアドレス７から４つのデータを取得する。これ以降も同様である。
【０１１８】
出力シーケンスは入力シーケンスとは異なる。各出力ポートは、時間的インターリーブを伴う同じＢＦ４３命令を用いる。
【０１１９】
各ポートの出力シーケンスは、０、６４、１２８、１９２、１、６５、１２９、１９３、．．．、６３、１２７、１９１、２５５のようになる。
【０１２０】
プロセッサｉのアドレスは、プロセッサｉ＋１のアドレスよりも１サイクル分進んでいる。従って、最終的なデータはＡポートに格納される。
【０１２１】
Ａポートのバンク１に格納される出力結果は、Ｘ（０）、Ｘ（４）、Ｘ（８）、Ｘ（１２）、．．．、Ｘ（１０１６）、Ｘ（１０２０）となる。
【０１２２】
Ａポートのバンク２に格納される出力結果は、Ｘ（１）、Ｘ（５）、Ｘ（９）、Ｘ（１３）．．．、Ｘ（１０１７）、Ｘ（１０２１）となる。
【０１２３】
Ａポートのバンク３に格納される出力結果は、Ｘ（２）、Ｘ（６）、Ｘ（１０）、Ｘ（１４）、．．．、Ｘ（１０１８）、Ｘ（１０２２）となる。
【０１２４】
Ａポートのバンク４に格納される出力結果は、Ｘ（３）、Ｘ（７）、Ｘ（１１）、Ｘ（１５）、．．．、Ｘ（１０１９）、Ｘ（１０２３）となる。
【０１２５】
【発明の効果】
本発明によれば、少なくとも以下の効果が得られる。
【０１２６】
データパスプロセッサを並列化することにより、各データパスプロセッサの処理するデータポイント数を減少させ、ＦＦＴ演算における待ち時間を最小化することができる。各データパスプロセッサの処理するデータポイント数を減少させることにより、データ処理システムのスループットも向上する。
【０１２７】
さらに、１つのアドレスシーケンサを、並列化された全てのデータパスプロセッサの同じデータポートに使用可能にすることによって、システム接続を単純化することができる。また、並列データパス接続に通常の単一ポートＳＲＡＭを使用できるようにすることによって、システム設計を単純化することができる。
【図面の簡単な説明】
【図１】本発明による、４つのＬＨ９１２４実行ユニットを持つ並列システムを示す、デジタル信号処理システムの部分概略図である。
【符号の説明】
Ａ１、Ａ２、Ａ３、Ａ４、Ｂ１、Ｂ２、Ｂ３、Ｂ４  メモリ
Ｐ１、Ｐ２、Ｐ３、Ｐ４  データパスプロセッサ
ＭＵＸ１、ＭＵＸ２、ＭＵＸ３、ＭＵＸ４  マルチプレクサ
【図１】
0003749022.tif 000036