(57)【要約】【課題】バンクアクセスの衝突回数の低減を図ること。【解決手段】入力バッファ１２０は、連続したアドレスが交互に割り振られた複数のバンク１１０を有するデータメモリ１０１からバンクライン長と同一長の入力データ群を読み出して格納し、複数のステージに分割されたＦＦＴのバタフライ演算を行う演算部の入力端子に入力データ群を入力する。出力バッファ１２１は、入力データ群と同一長であって演算部の出力端子から出力される出力データ群を格納し、出力データ群をデータメモリ１０１に格納する。制御部１２２は、複数のステージのうちの特定のステージにおいて、複数のバンク１１０の連続順序に従うように出力データ群の中から出力対象となる出力データを選択し、入力データ群の読み出し対象のバンク１１０とは異なるバンクに、バンク１１０に選択した出力データを複数のバンク１１０の連続順序に従って格納させる制御を行う。【選択図】図１
2017010325.tif 000002
【特許請求の範囲】
【請求項１】
連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリへのアクセスを制御する制御部と、
前記制御部のアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群を前記データメモリから読み出して格納し、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に前記入力データ群を入力する入力バッファと、
前記入力データ群と同一長であって前記演算部の出力端子から出力される出力データ群を格納し、前記制御部を介して前記出力データ群を前記データメモリに出力する出力バッファと、
を有し、
前記制御部は、
前記複数のバンクに割り当てられた前記アドレスの連続順序に従って前記データメモリからの前記入力データ群の読み出しを行う場合に、前記複数のステージのうちの特定のステージにおいて、前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従うように前記出力データ群の中から出力対象となる出力データを選択し、前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なるバンクに、選択した前記出力データを前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とするデータ処理装置。
【請求項２】
前記制御部は、
前記出力データ群の中から前記異なるバンクに格納される出力データのうち前記出力バッファに格納された順序が早い順に出力対象となる前記出力データを選択する、
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記出力バッファは、前記演算部の第１出力端子から出力される前記出力データ群に含まれる第１出力データ群を格納し、前記制御部を介して前記第１出力データ群を前記データメモリに出力する第１出力バッファと、前記演算部の第２出力端子から出力される前記出力データ群に含まれ前記第１出力データ群と異なる第２出力データ群を格納し、前記制御部を介して前記第２出力データ群を前記データメモリに出力する第２出力バッファと、を有し、
前記制御部は、
前記複数のバンクの連続順序に従うように、前記第１出力バッファに格納された前記第１出力データ群と前記第２出力バッファに格納された前記第２出力データ群との中から出力対象となる２つの前記出力データを選択し、前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なる２つのバンクに選択した２つの前記出力データをそれぞれ前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とする請求項１または請求項２のいずれか一つに記載のデータ処理装置。
【請求項４】
前記第１出力データ群のうち前記第１出力バッファに格納された順序が最も早い第１出力データと、前記第１出力データ群のうち前記第１出力バッファに格納された順序が２番目に早い第１出力データと、前記第２出力データ群のうち前記第２出力バッファに格納された順序が最も早い第２出力データと、前記第２出力データ群のうち前記第２出力バッファに格納された順序が２番目に早い第２出力データと、の中から、出力対象となる２つの前記出力データを選択する選択部を有し、
前記制御部は、
前記複数のバンクの連続順序に従う出力対象となる２つの前記出力データを前記選択部に選択させる制御を行い、前記２つのバンクに、前記選択部によって選択された２つの前記出力データをそれぞれ前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とする請求項３に記載のデータ処理装置。
【請求項５】
前記入力バッファは、前記制御部によって前記データメモリから読み出された前記入力データ群に含まれてポイント数がＮの前記フーリエ変換を行う場合に各々が０から（Ｎ／２−１）番目の入力である第１入力データ群を格納し、前記演算部の第１入力端子に前記第１入力データ群を入力する第１入力バッファと、前記制御部によって前記データメモリから読み出された前記入力データ群に含まれ前記第１入力データ群と異なり、前Ｎの前記フーリエ変換を行う場合に各々がＮ／２から（Ｎ−１）番目の入力データである第２入力データ群を格納し、前記演算部の第２入力端子に前記第２入力データ群を入力する第２入力バッファと、を有する、
ことを特徴とする請求項１〜４のいずれか一つに記載のデータ処理装置。
【請求項６】
連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリへのアクセスを制御する制御部と、
前記制御部のアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群を前記データメモリから読み出して格納し、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に前記入力データ群を入力する入力バッファと、
前記入力データ群と同一長であって前記演算部の出力端子から出力される出力データ群を格納し、前記制御部を介して前記出力データ群を前記データメモリに出力する出力バッファと、
を有し、
前記制御部は、
前記複数のバンクに割り当てられた前記アドレスの連続順序に従って前記データメモリからの前記出力データ群の出力を行う場合に、前記複数のステージのうちの特定のステージにおいて、前記複数のバンクのうち前記出力データ群の出力対象であるバンクとは異なるバンクから、前記入力データ群に含まれる入力データを前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従って読み出す制御を行う、
ことを特徴とするデータ処理装置。
【請求項７】
コンピュータが、
連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリのアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群であって、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に入力される入力データ群の前記データメモリからの読み出しを、前記複数のバンクに割り当てられたアドレスの連続順序に従う場合に、
複数のステージのうちの特定のステージにおいて、前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従うように前記出力データ群の中から出力対象となる出力データを選択し、
前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なるバンクに選択した前記出力データを前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とするデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、およびデータ処理方法に関する。
【背景技術】
【０００２】
従来、無線通信ベースバンド処理などでは、大量の行列演算処理やＦＦＴ（Ｆａｓｔ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ，高速フーリエ変換）処理などが行われる場合がある。行列演算処理やＦＦＴ処理などのように配列型データを扱うには、配列処理アーキテクチャが適している。配列型データを扱うプロセッサとしては、例えば、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）方式やベクトル方式のプロセッサがある。ＦＦＴ処理については、バタフライ演算によって演算回数を低減させることができる。
【０００３】
また、従来、ベクトル長を長くしてフーリエ変換を高速に行い、データの不連続なメモリアクセスによるメモリバンク（以下、「バンク」と表記する。）衝突を回避する技術が公知である（例えば、以下特許文献１参照。）。また、例えば、従来、パイプライン制御において複数の命令のそれぞれを分割し、各ステージを並列に処理し、キャッシュメモリへのアクセスが衝突する場合に衝突を回避する技術が公知である（例えば、以下特許文献２参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平６−１１０９１７号公報
【特許文献２】特開平１１−１８４６９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、ＦＦＴ処理についての入力データと出力データとのうちいずれか一方のデータメモリへのアクセスが、複数のバンクに交互に割り当てられたアドレスの連続順序に従わないアクセスであるため、バンクアクセスの衝突が多く発生するという問題点がある。
【０００６】
１つの側面では、本発明は、バンクアクセスの衝突回数の低減を図ることができるデータ処理装置、およびデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリへのアクセスを制御する制御部と、前記制御部のアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群を前記データメモリから読み出して格納し、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に前記入力データ群を入力する入力バッファと、前記入力データ群と同一長であって前記演算部の出力端子から出力される出力データ群を格納し、前記制御部を介して前記出力データ群を前記データメモリに出力する出力バッファと、を有し、前記制御部は、前記複数のバンクに割り当てられた前記アドレスの連続順序に従って前記データメモリからの前記入力データ群の読み出しを行う場合に、前記複数のステージのうちの特定のステージにおいて、前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従うように前記出力データ群の中から出力対象となる出力データを選択し、前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なるバンクに、選択した前記出力データを前記複数のバンクの連続順序に従って格納させる制御を行うデータ処理装置、およびデータ処理方法が提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、バンクアクセスの衝突回数の低減を図ることができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、データ処理装置による一動作例を示す説明図である。
【図２】図２は、データ処理装置の適用例を示す説明図である。
【図３】図３は、データ処理装置の機能的構成例を示す説明図である。
【図４】図４は、データ処理装置の構成例およびデータ処理装置と周辺の装置との接続例を示す説明図である。
【図５】図５は、複素積和演算器例を示す説明図である。
【図６】図６は、バタフライ演算例を示す説明図である。
【図７】図７は、１ステージの演算を複数のステップにより行う例を示す説明図である。
【図８】図８は、アドレス番地例を示す説明図である。
【図９】図９は、シーケンシャルなバンクアクセス例を示す説明図である。
【図１０】図１０は、ステージ１からステージ５までの命令のバンクアクセス例を示す説明図である。
【図１１Ａ】図１１Ａは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その１）である。
【図１１Ｂ】図１１Ｂは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その２）である。
【図１１Ｃ】図１１Ｃは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その３）である。
【図１１Ｄ】図１１Ｄは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その４）である。
【図１１Ｅ】図１１Ｅは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その５）である。
【図１１Ｆ】図１１Ｆは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図（その６）である。
【図１２Ａ】図１２Ａは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その１）である。
【図１２Ｂ】図１２Ｂは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その２）である。
【図１２Ｃ】図１２Ｃは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その３）である。
【図１２Ｄ】図１２Ｄは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その４）である。
【図１２Ｅ】図１２Ｅは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その５）である。
【図１２Ｆ】図１２Ｆは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図（その６）である。
【図１３Ａ】図１３Ａは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その１）である。
【図１３Ｂ】図１３Ｂは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その２）である。
【図１３Ｃ】図１３Ｃは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その３）である。
【図１３Ｄ】図１３Ｄは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その４）である。
【図１３Ｅ】図１３Ｅは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その５）である。
【図１３Ｆ】図１３Ｆは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図（その６）である。
【図１４】図１４は、ステージ１〜５において生成する信号列とアルゴリズム例を示す説明図である。
【図１５】図１５は、ステージ６において生成する信号列とアルゴリズム例を示す説明図である。
【図１６】図１６は、ステージ７以降において生成する信号列とアルゴリズム例を示す説明図である。
【図１７】図１７は、ＦＦＴ命令制御回路例１を示す説明図である。
【図１８】図１８は、ＦＦＴ命令制御回路例２を示す説明図である。
【図１９】図１９は、ＦＩＦＯ選択信号生成回路例を示す説明図である。
【図２０】図２０は、Ｆｓｅｌテーブル例を示す説明図である。
【図２１】図２１は、アドレス信号生成回路例を示す説明図である。
【図２２】図２２は、Ｆａｄｄｒテーブル例を示す説明図である。
【図２３】図２３は、制御部による制御処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明にかかるデータ処理装置、およびデータ処理方法の実施の形態を詳細に説明する。
【００１１】
図１は、データ処理装置による一動作例を示す説明図である。データ処理装置１００は、ストリーム型処理を行うコンピュータである。ストリーム型処理とは、データメモリ１０１から一連のデータを順次読み出して演算を行い、一連の演算結果をデータメモリ１０１に順次書き込む処理である。一連のデータとは、配列型データである。データ処理装置１００の適用の一例は図２に示す。適用例としては、例えば、スマートフォン、携帯電話機、タブレット端末装置、タブレット型ＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）、ＰＨＳ（Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍ）などである。
【００１２】
また、データ処理装置１００は、命令セットとして、単位データを扱う命令群を有する。命令は、例えば、ＦＦＴ処理などの演算命令である。ここで、ＦＦＴは、０（Ｎ）の計算量であるＤＦＴ（Ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ，離散フーリエ変換）を０（ＮｌｏｇＮ）のオーダーで計算する高速なアルゴリズムである。ここで、無線通信信号処理などにおいては、大量のＦＦＴ処理が行われる場合がある。ＦＦＴ処理のような演算量が多い処理を高速に実行することが要求される場合、ＦＦＴ処理のための専用回路が設けられる。上述したように、配列型データを扱うプロセッサとしては、例えば、ＳＩＭＤ方式やベクトルプロセッサ方式のプロセッサがある。
【００１３】
従来、配列型データを扱うプロセッサでは、連続した単位データに同一の演算を施す。そのため、データメモリ１０１から連続的に入力データをＦＦＴ処理の演算器に供給し、演算器からＦＦＴ処理の処理結果である出力データを連続的に取得してデータメモリ１０１に格納させる。
【００１４】
本実施の形態では、前提として、データメモリ１０１のアドレス方式はインターリーブとする。インターリーブとは、複数のバンク１１０に対して連続したアドレスを交互に割り振っておくデータメモリ１０１へのアクセスを高速化する技法の一種である。
【００１５】
ＦＦＴ処理についての入力データと出力データとのうち少なくともいずれかのアクセスがアドレスの順序に従うシーケンシャルアクセスの場合、もう一方のアクセスはアドレスの順序に従わないストライドアクセスとなる。ＦＦＴ処理の複素積和演算を１つだけ実行し、１数値のメモリアクセスの場合には、一方がストライドアクセスであってもよい。しかしながら、ＦＦＴ処理の複素積和演算を並列に実行する場合、並列のサイズに合わせて複数のバンクを有すると、バタフライ演算のステージによっては、シーケンシャルアクセスとストライドアクセスとによりバンク衝突が多く発生するという問題点がある。バンク衝突が発生した場合、一方のバンクアクセスが他方のバンクアクセスの終了を待機する状態となる。この状態をストールとも称する。ストールによってＦＦＴ処理に要する時間が長くなる。
【００１６】
そこで、本実施の形態では、データ処理装置１００が、アドレスの割当順に従って入力データを読み出す際に、該割当順に応じたバンクの順に従って選択した出力データを、読み出し先でないバンクに該バンクの順序に従って格納させる。これにより、バンク衝突を回避することができる。したがって、バンク衝突の回数を低減させることができるため、バンク衝突によるストールの時間が減るため、フーリエ変換の命令の実行に要する時間の短縮を図ることができる。
【００１７】
まず、データ処理装置１００は、入力バッファ１２０と、出力バッファ１２１と、制御部１２２と、を有する。
【００１８】
制御部１２２は、データメモリ１０１へのアクセスを制御する。データメモリ１０１は、インターリーブ方式であるため、連続したアドレスが交互に割り振られた複数のバンク１１０を有する。バンク１１０はメモリバンクである。入力バッファ１２０と出力バッファ１２１とをそれぞれ２個ずつ有する場合、データメモリ１０１は４個以上のバンク１１０を有することとなる。図１の例では、データメモリ１０１は４個のバンク１１０を有する。
【００１９】
入力バッファ１２０は、制御部１２２のアクセス対象である複数のバンク１１０における各々のライン長と同一長の入力データ群をデータメモリ１０１から読み出して格納し、演算部の入力端子に入力データ群を入力する。図１の例では、入力バッファ１２０は第１入力バッファ１２０−Ａと第２入力バッファ１２０−Ｂである。第１入力バッファ１２０−Ａと第２入力バッファ１２０−Ｂは、例えば、ＦＩＦＯである。そのため、第１入力バッファ１２０−Ａは、第１入力データＡをデータメモリ１０１から読み出された順に並べて格納する。第２入力バッファ１２０−Ｂは、第２入力データＢをデータメモリ１０１から読み出された順に並べて格納する。
【００２０】
出力バッファ１２１は、入力データ群と同一長であって演算部の出力端子から出力される出力データ群を格納し、制御部１２２を介して出力データ群をデータメモリ１０１に格納する。出力バッファ１２１は、第１出力バッファ１２１−Ｆと第２出力バッファ１２１−Ｅである。第１出力バッファ１２１−Ｆと第２出力バッファ１２１−Ｅは、例えば、ＦＩＦＯである。そのため、第１出力バッファ１２１−Ｆは、出力データＦを演算部から出力された順に並べて格納する。第２出力バッファ１２１−Ｅは、出力データＥを演算部から出力された順に並べて格納する。
【００２１】
演算部は、入力されたデータに対して複数のステージに分割されたＦＦＴのバタフライ演算を行う。演算部は、入力端子に入力された入力データに対してバタフライ演算を行い、出力端子からバタフライ演算の演算結果として出力データを出力する。
【００２２】
図１では、データメモリ１０１からの入力データ群の読み出し対象が複数のバンク１１０に割り当てられたアドレスの連続順序に従う場合を例に挙げる。アドレスの連続順序は、例えば、バンク１１０−０の領域を示すアドレスＸ、バンク１１０−１の領域を示すアドレスＸ＋１、バンク１１０−２の領域を示すアドレスＸ＋２、バンク１１０−３の領域を示すアドレスＸ＋３のような順序である。制御部１２２は、アドレスの連続順序に読み出し対象が従う場合に、複数のステージのうちの特定のステージにおいて、複数のバンク１１０の連続順序に従うように出力データ群の中から出力対象となる出力データを選択する制御を行う。そして、制御部１２２は、複数のバンク１１０のうち入力データ群の読み出し対象であるバンク１１０とは異なるバンクに、選択した出力データを複数のバンク１１０の連続順序に従って格納させる制御を行う。
【００２３】
複数のバンク１１０の連続順序とは、アドレスの連続順序に応じて連続する順序である。例えば、アドレスがバンク１１０−０からバンク１１０−３の順に割り当てられている場合、バンク１１０の連続順序は、バンク１１０−０からバンク１１０−３の順である。特定のステージについては、例えば、指定されたステージである。複数のステージに分割されたＦＦＴ処理では、ステージによって出力データのストライドアクセスが異なる。特定のステージは、演算部によって実行されているステージである。特定のステージは、例えば、演算部などによって指定される。そのため、制御部１２２は、指定されたステージに応じたバンク１１０の格納先になるようにいずれの出力データを選択するかをバンク１１０の連続順序に従って制御する。
【００２４】
読み出し開始からのサイクル数を例えばｃｙｃｌｅによっても表す。例えば、ｃｙｃｌｅ（０）であればサイクル数が０であり、ｃｙｃｌｅ（ｉ）であればサイクル数がｉである。
【００２５】
例えば、ｃｙｃｌｅ（ｉ）において、制御部１２２は、バンク１１０−３から入力データＡ７を読み出して第１入力バッファ１２０−Ａに格納させる。例えば、ｃｙｃｌｅ（ｉ）において、制御部１２２は、バンク１１０−２から入力データＢ６を読み出して第２入力バッファ１２０−Ｂに格納させる。
【００２６】
そこで、例えば、ｃｙｃｌｅ（ｉ）において、制御部１２２は、バンク１１０−０に、第１出力バッファ１２１−Ｆに格納された出力データＦ０を格納させる。そして、例えば、ｃｙｃｌｅ（ｉ）において、制御部１２２は、バンク１１０−１に、第１出力バッファ１２１−Ｅに格納された出力データＥ０を格納させる。各バンク１１０の入力データおよび出力データに付された（  ）内には、サイクル数が記述されてある。
【００２７】
つぎに、例えば、ｃｙｃｌｅ（ｉ＋１）において、制御部１２２は、バンク１１０−０から入力データＡ８を読み出して第１入力バッファ１２０−Ａに格納させる。例えば、ｃｙｃｌｅ（ｉ＋１）において、制御部１２２は、バンク１１０−３から入力データＢ７を読み出して第２入力バッファ１２０−Ｂに格納させる。ｃｙｃｌｅ（ｉ＋１）において、バンク１１０−１とバンク１１０−２とが読み出し対象のバンク１１０と異なるバンク１１０であるため、例えば、制御部１２２は、バンク１１０−２に、第１出力バッファ１２１−Ｆに格納された出力データＦ１を格納させる。そして、例えば、ｃｙｃｌｅ（ｉ＋１）において、制御部１２２は、バンク１１０−１に、第１出力バッファ１２１−Ｅに格納された出力データＥ２を格納させる。
【００２８】
つぎに、例えば、ｃｙｃｌｅ（ｉ＋２）において、制御部１２２は、バンク１１０−１から入力データＡ９を読み出して第１入力バッファ１２０−Ａに格納させる。例えば、ｃｙｃｌｅ（ｉ＋２）において、制御部１２２は、バンク１１０−０から入力データＢ８を読み出して第２入力バッファ１２０−Ｂに格納させる。ｃｙｃｌｅ（ｉ＋２）において、バンク１１０−２とバンク１１０−３とが読み出し対象のバンク１１０と異なるバンク１１０であるため、例えば、制御部１２２は、バンク１１０−２に、第１出力バッファ１２１−Ｆに格納された出力データＦ３を格納させる。そして、例えば、ｃｙｃｌｅ（ｉ＋２）において、制御部１２２は、バンク１１０−３に、第１出力バッファ１２１−Ｅに格納された出力データＥ１を格納させる。
【００２９】
つぎに、例えば、ｃｙｃｌｅ（ｉ＋３）において、制御部１２２は、バンク１１０−２から入力データＡ１０を読み出して第１入力バッファ１２０−Ａに格納させる。例えば、ｃｙｃｌｅ（ｉ＋３）において、制御部１２２は、バンク１１０−１から入力データＢ９を読み出して第２入力バッファ１２０−Ｂに格納させる。ｃｙｃｌｅ（ｉ＋３）において、バンク１１０−０とバンク１１０−３とが読み出し対象のバンク１１０と異なるバンク１１０であるため、制御部１２２は、バンク１１０−０に、第１出力バッファ１２１−Ｆに格納された出力データＦ２を格納させる。そして、例えば、ｃｙｃｌｅ（ｉ＋３）において、制御部１２２は、バンク１１０−３に、第１出力バッファ１２１−Ｅに格納された出力データＥ３を格納させる。
【００３０】
このように、制御部１２２が、入力データについて読み出しアクセスがアドレスの連続順序に対応している場合、出力データについて書き込みアクセスをバンク１１０の連続順序に対応するように制御を行う。これにより、読み出しおよび書き込みの両方がバンク１１０に対してシーケンシャルなアクセスとなるため、バンク１１０の衝突を回避することができる。したがって、ストールを抑制することができ、ＦＦＴ処理に要する時間の短縮化を図ることができる。
【００３１】
ただし、図１では、理解の容易化のために、演算部のレイテンシを無視した例で有るが、実際には、データ処理装置１００の設計者が、演算部のレイテンシなども考慮して入力データの読み出しと出力データの書き込みとのいずれもバンクに対してシーケンシャルになるようにタイミングを調整する。
【００３２】
また、図示省略するが、出力データについて書き込みアクセスがアドレスの連続順序に対応している場合、入力データについて読み出しアクセスをバンク１１０の連続順序に対応するように制御を行う。複数のバンク１１０に割り当てられたアドレスの連続順序に従ってデータメモリ１０１からの出力データ群の出力を行う場合について簡単に説明する。制御部１２２は、例えば、複数のステージのうちの特定のステージにおいて、出力データ群の出力対象であるバンク１１０とは異なるバンク１１０から、入力データ群に含まれる入力データを複数のバンク１１０の連続順序に従って読み出す制御を行う。複数のバンクの連続順序は、アドレスの連続順序に応じた順序で連続する。これにより、読み出しおよび書き込みの両方がバンク１１０に対してシーケンシャルなアクセスとなるため、バンク１１０の衝突を回避することができる。したがって、ストールを抑制することができ、ＦＦＴ処理に要する時間の短縮化を図ることができる。
【００３３】
（データ処理装置１００の適用例）
ここで、本実施の形態にかかるデータ処理装置１００を携帯電話機のベースバンド処理ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）に適用した場合について説明する。
【００３４】
図２は、データ処理装置の適用例を示す説明図である。図２において、ベースバンド処理ＬＳＩ２００は、ＲＦ（Ｒａｄｉｏ  Ｆｒｅｑｕｅｎｃｙ）部２０１と、専用ハードウェア２０２と、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）２０３−１〜２０３−３と、を有する。
【００３５】
ＲＦ部２０１は、アンテナ２０５を介して受信された無線信号の周波数をダウンコンバートし、デジタル信号に変換してバス２０４に出力する。また、ＲＦ部２０１は、バス２０４に出力されたデジタル信号をアナログ信号に変換し、無線周波数にアップコンバートして、アンテナ２０５に出力する。
【００３６】
専用ハードウェア２０２は、例えば、誤り訂正符号を扱うｔｕｒｂｏ、ビタビアルゴリズムを実行するｖｉｔｅｒｂｉ、複数のアンテナでデータの送受信を行うためのＭＩＭＯ（Ｍｕｌｔｉ  Ｉｎｐｕｔ  Ｍｕｌｔｉ  Ｏｕｔｐｕｔ）等を含む。
【００３７】
ＤＳＰ２０３−１〜２０３−３（以下、単に「ＤＳＰ２０３」と称する）は、プロセッサ２１１と、命令メモリ２１３と、周辺回路２１２と、データメモリ１０１と、を有する。プロセッサ２１１は、ＣＰＵ２２１と、データ処理装置１００と、を有する。各ＤＳＰ２０３にはＳｅａｒｃｈｅｒ（同期）、Ｄｅｍｏｄｕｌａｔｏｒ（復調）、Ｄｅｃｏｄｅｒ（復号）、Ｃｏｄｅｃ（符号化）、Ｍｏｄｕｌａｔｏｒ（変調）等、無線通信信号処理の各要素処理が割り当てられる。
【００３８】
命令メモリ２１３は、プログラムなどの命令を記憶するメモリである。データメモリ１０１は、演算対象となるデータや演算結果などを記憶する。
【００３９】
（データ処理装置１００の機能的構成例）
図３は、データ処理装置の機能的構成例を示す説明図である。データ処理装置１００は、例えば、第１入力バッファ１２０−Ａと、第２入力バッファ１２０−Ｂと、演算部３０１と、第１出力バッファ１２１−Ｆと、第２出力バッファ１２１−Ｅと、選択部３０２と、制御部１２２と、を有する。
【００４０】
また、各部は、論理積回路であるＡＮＤ、否定論理回路であるＩＮＶＥＲＴＥＲ、論理和回路であるＯＲや、ラッチ回路であるＦＦ（Ｆｌｉｐ  Ｆｌｏｐ）などの素子によって形成されてもよい。また、各部は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）によって実現されてもよい。具体的には、例えば、上述した各部の機能をハードウェア記述言語などによってネットリストに機能定義し、そのネットリストを論理合成してＡＳＩＣやＰＬＤに与えることにより、各部を実現してもよい。
【００４１】
第１入力バッファ１２０−Ａは、制御部１２２によってデータメモリ１０１から読み出された第１入力データ群を格納し、演算部３０１の第１入力端子に第１入力データ群を入力するＦＩＦＯである。第２入力バッファ１２０−Ｂは、制御部１２２によってデータメモリ１０１から読み出された第２入力データ群を格納し、演算部３０１の第２入力端子に第２入力データ群を入力するＦＩＦＯである。第１入力データ群と第２入力データ群は異なる入力データである。ポイント数がＮのＦＦＴ処理を行う場合に、第１入力データ群は、０からＮ／２−１番目の入力データであり、第２入力データ群は、Ｎ／２からＮ−１番目の入力データである。
【００４２】
第１出力バッファ１２１−Ｆは、演算部３０１の第１出力端子から出力される第１出力データ群を格納し、制御部１２２を介して第１出力データ群をデータメモリ１０１に出力するＦＩＦＯである。第２出力バッファ１２１−Ｅは、演算部３０１の第２出力端子から出力される第２出力データ群を格納し、制御部１２２を介して第２出力データ群をデータメモリ１０１に出力するＦＩＦＯである。第１出力データ群と第２出力データ群とは異なる。
【００４３】
演算部３０１は、入力されたデータに対して複数のステージに分割されたＦＦＴのバタフライ演算を行う。演算部３０１は、第１入力データを受け付ける第１入力端子と、第２入力データを受け付ける第２入力端子と、第１出力データを出力する第１出力端子と、第２出力データを出力する第２出力端子と、を有する。演算部３０１は、第１入力データと第２入力データとに対してバタフライ演算を行い、第１出力データと第２出力データとを演算結果として出力する。
【００４４】
制御部１２２は、連続したアドレスが交互に割り振られた複数のバンク１１０を有するデータメモリへのアクセスを制御する。アドレスが交互に割り振られる例は、後述する図８に示す。
【００４５】
制御部１２２は、アドレスの連続順序に従ってデータメモリ１０１からの入力データ群の読み出しを行う場合に、特定のステージにおいて、複数のバンク１１０の連続順序に従うように出力データ群の中から出力対象となる出力データを選択する。そして、制御部１２２は、複数のバンク１１０のうち入力データ群の読み出し対象であるバンク１１０とは異なるバンク１１０に、選択した出力データを複数のバンク１１０の連続順序に従って格納させる制御を行う。アドレスの連続順序は、複数のバンク１１０に割り当てられたアドレスの順序で連続する。複数のバンク１１０の連続順序は、アドレスの連続順序に応じた順序で連続する。特定のステージは、複数のステージのうちのステージであり、例えば演算部３０１によって指定されたステージである。
【００４６】
また、具体的に、制御部１２２は、例えば、出力データ群の中から異なるバンク１１０に格納される出力データのうち出力バッファ１２１に格納された順序が早い順に出力対象となる出力データを選択する。
【００４７】
上述したように、出力バッファ１２１が、第１出力バッファ１２１−Ｆと第２出力バッファ１２１−Ｅとのように複数ある場合について説明する。制御部１２２は、複数のバンク１１０の連続順序に従うように、第１出力データ群と第２出力データ群との中から出力対象となる２つの出力データを選択する。そして、制御部１２２は、複数のバンク１１０のうち入力データ群の読み出し対象であるバンク１１０とは異なる２つのバンク１１０に選択した２つの出力データをそれぞれ複数のバンク１１０の連続順序に従って格納させる制御を行う。
【００４８】
また、選択部３０２は、最も早い第１出力データと、２番目に早い第１出力データと、最も早い第２出力データと、２番目に早い第２出力データと、の中から、出力対象となる２つの出力データを制御部１２２の制御によって選択する。
【００４９】
最も早い第１出力データは、第１出力データ群のうち第１出力バッファ１２１−Ｆに格納された順序が最も早いデータであり、ＦＩＦＯである第１出力バッファ１２１−Ｆの先頭に格納されたデータである。２番目に早い第１出力データは、第１出力データ群のうち第１出力バッファ１２１−Ｆに格納された順序が２番目に早いデータであり、ＦＩＦＯである第１出力バッファ１２１−Ｆの先頭から２番目に格納されたデータである。
【００５０】
最も早い第２出力データは、第２出力データ群のうち第２出力バッファ１２１−Ｅに格納された順序が最も早いデータであり、ＦＩＦＯである第２出力バッファ１２１−Ｅの先頭に格納されたデータである。２番目に早い第２出力データは、第２出力データ群のうち第２出力バッファ１２１−Ｅに格納された順序が２番目に早いデータであり、ＦＩＦＯである第２出力バッファ１２１−Ｅの先頭から２番目に格納されたデータである。
【００５１】
また、制御部１２２は、複数のバンク１１０の連続順序に従う出力対象となる２つの出力データを選択部３０２に選択させる制御を行う。そして、制御部１２２は、２つのバンク１１０に、選択部３０２によって選択された２つの出力データをそれぞれ複数のバンク１１０の連続順序に従って格納させる制御を行う。
【００５２】
以上を踏まえて、データ処理装置の詳細な構成や動作の詳細について説明する。
【００５３】
図４は、データ処理装置の構成例およびデータ処理装置と周辺の装置との接続例を示す説明図である。図４には、データ処理装置１００と、データ処理装置１００の周辺の命令メモリ２１３およびデータメモリ１０１と、の簡単な接続例を示す。データ処理装置１００は、演算データパス４１１と、ＦＩＦＯ４１２と、ＭＡＵ（Ｍｅｍｏｒｙ  Ａｃｃｅｓｓ  Ｕｎｉｔ）４１３と、を有する。
【００５４】
命令メモリ２１３には、複数の命令を有する命令列が格納されており、命令列の各命令がデコーダ４０１に順番に供給される。デコーダ４０１は、供給される各命令をデコードし、デコード結果に従いＭＡＵ４１３、演算データパス４１１を制御する。これにより、デコーダ４０１は、データメモリ１０１へのアクセスおよび演算データパス４１１によるＦＦＴ処理を実行する。
【００５５】
ＦＩＦＯ４１２は、例えば、入力ＦＩＦＯ４２１と、出力ＦＩＦＯ４２２と、を有する。入力ＦＩＦＯ４２１は、演算データパス４１１の処理対象のデータをデータメモリ１０１から取得して一時的に格納して演算データパス４１１へ入力する入力バッファ１２０である。出力ＦＩＦＯ４２２は、演算データパス４１１の処理結果などをデータメモリ１０１へ記憶させる前に一時的に格納してＭＡＵ４１３へ出力する出力バッファ１２１である。
【００５６】
具体的に、入力ＦＩＦＯ４２１は、例えば、演算データパス４１１への入力データストリーム用の入力ＦＩＦＯ４２１−Ａと入力ＦＩＦＯ４２１−Ｂとを有する。入力ＦＩＦＯ４２１−Ａは例えば第１入力バッファ１２０−Ａであり、入力ＦＩＦＯ４２１−Ｂは例えば第２入力バッファ１２０−Ｂである。出力ＦＩＦＯ４２２は、演算データパス４１１からの出力データストリーム用の出力ＦＩＦＯ４２２−Ｆと出力ＦＩＦＯ４２２−Ｅとを有する。出力ＦＩＦＯ４２２−Ｆは例えば第１出力バッファ１２１−Ｆであり、出力ＦＩＦＯ４２２−Ｅは例えば第２出力バッファ１２１−Ｅである。ここでは、各ＦＩＦＯは、例えば、５１２ビット幅である。また、データの各々は、複素数であり、１６ビットの実部と、１６ビットの虚部と、を有する。
【００５７】
出力ＦＩＦＯ４２２−Ｆは、例えば、Ｆ＃０とＦ＃１とＦ＃２とＦ＃３との４つのバッファを有する。また、出力ＦＩＦＯ４２２−Ｅは、例えば、Ｅ＃０とＥ＃１とＥ＃２とＥ＃３との４つのバッファを有する。マルチプレクサ４２３−Ｆは、ＦＦＴ命令制御回路４３２から出力される制御信号に基づいて、Ｆ＃０とＦ＃１とＥ＃１とのうちいずれかに格納されたデータをＤＭＡ４３１−Ｆに入力する。マルチプレクサ４２３−Ｅは、ＦＦＴ命令制御回路４３２から出力される制御信号に基づいて、Ｅ＃０とＥ＃１とＦ＃１とのうちいずれかに格納されたデータをＤＭＡ４３１−Ｅに入力する。
【００５８】
データメモリ１０１は、例えば、演算データパス４１１の処理対象のデータや演算データパス４１１の処理結果などを記憶する。データメモリ１０１は、例えば、４つのバンク１１０を有する。バンク１１０の各々のライン長は、５１２ビットであり、３２ビットのデータを１６個記憶可能である。本実施の形態では、アドレッシング方式は、メモリインターリーブである。メモリインターリーブでは、複数のバンク１１０に跨って連続したアドレスを交互に振っておき、あるデータにアクセスする遅延時間の最中につぎのアドレスへアクセス要求を発行して時間を有効利用する。
【００５９】
ＭＡＵ４１３は、データメモリ１０１へのアクセスを制御する制御部１２２である。ＭＡＵ４１３は、ＦＦＴ命令制御回路４３２と、ＤＭＡ４３１−Ａ〜ＤＭＡ４３１−Ｅと、調停回路４３３と、を有する。ＤＭＡ４３１−Ａ〜ＤＭＡ４３１−Ｅの各々は、ＤＭＡ４３１−Ａ〜ＤＭＡ４３１−Ｅに対応する入力ＦＩＦＯ４２１−Ａ〜ＦＩＦＯ４２２−Ｅと、データメモリ１０１と、の間でデータを転送する。調停回路４３３は、ＤＭＡ４３１−Ａ〜ＤＭＡ４３１−Ｅによるアクセスの競合を制御する。また、調停回路４３３は、ＤＭＡ４３１−Ａ〜ＤＭＡ４３１−ＥによるＤＭＡ制御動作およびＤＭＡ転送動作の制御を行う。
【００６０】
ＦＦＴ命令制御回路４３２は、ステージおよびサイクルごとにいずれのバッファに格納されたデータをマルチプレクサ４２３−Ｆとマルチプレクサ４２３−Ｅとに選択させるかを制御する。
【００６１】
演算データパス４１１は、ＦＦＴのバタフライ演算を行う。本実施の形態では、例えば、１６複素ごとに並列処理を行う。
ｆｏｒ（ｉ＝０；ｉ＜Ｎ；ｉ＝ｉ＋１６）
ｆｏｒ（ｊ＝０；ｊ＜１６；ｊ＋＋）    Ｆ［ｉ＋ｊ］＝Ａ［ｉ＋ｊ］×Ｂ［ｉ＋ｊ］
【００６２】
また、データ処理装置１００は、上述したように、例えばベースバンド処理ＬＳＩなどに適用されるため、演算データパス４１１は、行列演算などを行ってもよい。行列演算とは、例えば、積算、加算、減算などが挙げられる。
【００６３】
図５は、複素積和演算器例を示す説明図である。図５では、演算データパス４１１に含まれるバタフライ演算を行う複素積和演算器５００について説明する。図５（１）には、複素積和演算器５００の記号を示す。図５（２）には、複素積和演算器５００の構成例を示す。
【００６４】
図５（１）に示すように、バタフライ演算では、第１入力データＸ１および第２入力データＸ２を入力する。そして、バタフライ演算では、下記のＹ１とＹ２を算出する演算を行う。最後に、バタフライ演算では、第１出力データＹ１および第２出力データＹ２を出力する。ここで、Ｗnは回転因子データである。ｎは１〜Ｎである。ＮはＦＦＴのポイント数である。ＦＦＴポイント数はＦＦＴのデータ数に相当する。
Ｙ１＝Ｘ１＋Ｘ２×Ｗn
Ｙ２＝Ｘ１−Ｘ２×Ｗn
Ｗｎ＝−ｐ（−２πｊ×ｎ／Ｎ）
【００６５】
図５（２）に示すように、複素積和演算器５００は、ＡＬＵ５０１−１と、ＡＬＵ５０１−２と、を有する。回転因子データＷnは、メモリなどに記憶されてある。回転因子データＷnを記憶するメモリについては、図示省略するが、例えばデータ処理装置１００が有し、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やレジスタなどが挙げられる。
【００６６】
ＡＬＵ５０１−１は、第２入力データＸ２および回転因子データＷnの乗算を行い、第２入力データＸ２×Ｗnを出力する。ＡＬＵ５０１−２は、第１入力データＸ１およびＡＬＵ５０１からの出力データを入力し、加算による第１出力データＹ１および減算による第２出力データＹ２を出力する。
【００６７】
本実施の形態では、バタフライ演算について、入力データについては、データメモリ１０１にシーケンシャルアクセスとなり、出力データについては、ＦＦＴのステージに応じてストライドアクセスとなる例を挙げる。ＦＦＴのポイント数がＮの場合、入力ＦＩＦＯ４２１−Ａに格納される第１入力データ群は０番から（Ｎ−１）／２番までのデータであり、入力ＦＩＦＯ４２１−Ｂに格納される第２入力データ群はＮ／２番から（Ｎ−１）番までのデータである。
【００６８】
図６は、バタフライ演算例を示す説明図である。図６には、ＦＦＴのポイント数が３２の場合を例に挙げる。図６の例では、演算データパス４１１は、ステージ１〜ステージ５を実行することにより、ＦＦＴ処理を実現する。図６の例では、各ステージのバタフライ演算は１６個の複素積和演算器５００によって行われる。
【００６９】
ここでは、入力ＦＩＦＯ４２１−Ａに格納される入力データ群は０番から１５番までのデータであり、入力ＦＩＦＯ４２１−Ｂに格納される入力データ群は１６番から３１番までのデータである。実際のデータメモリ１０１上では、０〜３１番の順に入力データが格納されてあるが、ここでは、理解の容易化のために、入力データについて番号順にデータを記載していない。
【００７０】
ステージ１では、３２個の入力データがデータメモリ１０１から入力ＦＩＦＯ４２１−Ａおよび入力ＦＩＦＯ４２１−Ｂを介して１６個の複素積和演算器５００に入力される。１６個の複素積和演算器５００は、３２個のデータを入力し、３２個のデータを出力する。例えば、１つ目の複素積和演算器５００は、０番目の入力データおよび１６番目の入力データを基にバタフライ演算を行い、０番目の出力データおよび１番目の出力データを出力する。２つ目の複素積和演算器５００は、８番目の入力データおよび２４番目の入力データを基にバタフライ演算を行い、１６番目の出力データおよび１７番目の出力データを出力する。１６個の複素積和演算器５００が出力する３２個のデータは、出力ＦＩＦＯ４２２−Ｆおよび出力ＦＩＦＯ４２２−ＥとＤＭＡ４３１−ＦおよびＤＭＡ４３１−Ｅとを介して、データメモリ１０１に書き込まれる。この３２個のデータがステージ２の入力データになる。
【００７１】
ステージ２では、３２個の入力データがデータメモリ１０１から入力ＦＩＦＯ４２１−Ａおよび入力ＦＩＦＯ４２１−Ｂを介して１６個の複素積和演算器５００に入力される。１６個の複素積和演算器５００は、３２個のデータを入力し、３２個のデータを出力する。例えば、１つ目の複素積和演算器５００は、０番目の入力データおよび１６番目の入力データを基にバタフライ演算を行い、０番目の出力データおよび２番目の出力データを出力する。２つ目の複素積和演算器５００は、１番目の入力データおよび１７番目の入力データを基にバタフライ演算を行い、１番目の出力データおよび３番目の出力データを出力する。１６個の複素積和演算器５００が出力する３２個のデータは、出力ＦＩＦＯ４２２−Ｆおよび出力ＦＩＦＯ４２２−ＥとＤＭＡ４３１−ＦおよびＤＭＡ４３１−Ｅとを介して、データメモリ１０１に書き込まれる。この３２個のデータがステージ３の入力データになる。
【００７２】
ステージ３では、３２個の入力データがデータメモリ１０１から入力ＦＩＦＯ４２１−Ａおよび入力ＦＩＦＯ４２１−Ｂを介して１６個の複素積和演算器５００に入力される。１６個の複素積和演算器５００は、３２個のデータを入力し、３２個のデータを出力する。例えば、１６個の複素積和演算器５００は、０番目の入力データおよび１６番目の入力データを基にバタフライ演算を行い、０番目の出力データおよび４番目の出力データを出力する。２つ目の複素積和演算器５００は、１番目の入力データおよび１７番目の入力データを基にバタフライ演算を行い、１番目の出力データおよび５番目の出力データを出力する。１６個の複素積和演算器５００が出力する３２個のデータは、出力ＦＩＦＯ４２２−Ｆおよび出力ＦＩＦＯ４２２−ＥとＤＭＡ４３１−ＦおよびＤＭＡ４３１−Ｅとデータメモリ１０１に書き込まれる。この３２個のデータがステージ４の入力データになる。
【００７３】
ステージ４では、３２個の入力データがデータメモリ１０１から入力ＦＩＦＯ４２１−Ａおよび入力ＦＩＦＯ４２１−Ｂを介して１６個の複素積和演算器５００に入力される。１６個の複素積和演算器５００は、３２個のデータを入力し、３２個のデータを出力する。例えば、１つ目の複素積和演算器５００は、０番目の入力データおよび１６番目の入力データを基にバタフライ演算を行い、０番目の出力データおよび８番目の出力データを出力する。２つ目の複素積和演算器５００は、１番目の入力データおよび１７番目の入力データを基にバタフライ演算を行い、１番目の出力データおよび９番目の出力データを出力する。１６個の複素積和演算器５００が出力する３２個のデータは、出力ＦＩＦＯ４２２−Ｆおよび出力ＦＩＦＯ４２２−ＥとＤＭＡ４３１−ＦおよびＤＭＡ４３１−Ｅとを介して、データメモリ１０１に書き込まれる。この３２個のデータがステージ５の入力データになる。
【００７４】
ステージ５では、３２個の入力データがデータメモリ１０１から入力ＦＩＦＯ４２１−Ａおよび入力ＦＩＦＯ４２１−Ｂを介して１６個の複素積和演算器５００に入力される。１６個の複素積和演算器５００は、３２個のデータを入力し、３２個のデータを出力する。例えば、１つ目の複素積和演算器５００は、０番目の入力データおよび１６番目の入力データを基にバタフライ演算を行い、０番目の出力データおよび１６番目の出力データを出力する。２つ目の複素積和演算器５００は、１番目の入力データおよび１７番目の入力データを基にバタフライ演算を行い、１番目の出力データおよび１７番目の出力データを出力する。１６個の複素積和演算器５００が出力する３２個のデータは、出力ＦＩＦＯ４２２−Ｆおよび出力ＦＩＦＯ４２２−ＥとＤＭＡ４３１−ＦおよびＤＭＡ４３１−Ｅとを介して、データメモリ１０１に書き込まれる。
【００７５】
図７は、１ステージの演算を複数のステップにより行う例を示す説明図である。ここでは、ＦＦＦのポイント数は３２であるが、１ステップで演算可能なポイント数が８の場合の例を示す。換言すれば、複素積和演算器５００は４個である。
【００７６】
図７では１ステップ目の演算を示し、１ステップ目では、点線枠で囲まれた８ポイントの演算が行われる。２ステップ目〜４ステップ目では、点線枠で囲まれていない２４ポイントの演算が８ポイントごとに順次行われる。
【００７７】
図８は、アドレス番地例を示す説明図である。本実施の形態では、上述したようにメモリインターリーブを利用するため、バンク１１０−０〜バンク１１０−３に連続したアドレスが交互に割り振られる。
【００７８】
入力データＡが格納される先頭の領域を示すアドレスはＸである。例えば、バンク１１０−０に含まれる入力データＡの先頭の領域を示すアドレスがＸである。そのため、例えば、先頭の領域のつぎにバンク１１０−１の領域を示すアドレスをＸ＋１、バンク１１０−２の領域を示すアドレスをＸ＋２、バンク１１０−３の領域を示すアドレスをＸ＋３、バンク１１０−０の領域を示すアドレスをＸ＋４とする。このように、本実施の形態では、説明の簡単化のために、アドレスが１インクリメントされるごとにつぎのバンク１１０の領域となる。
【００７９】
例えば、バンク１１０−０の入力データＢの先頭の領域を示すアドレスがＹである。そのため、先頭の領域のつぎにバンク１１０−１の領域を示すアドレスをＹ＋１、バンク１１０−２の領域を示すアドレスをＹ＋２、バンク１１０−３の領域を示すアドレスをＹ＋３、バンク１１０−０の領域を示すアドレスをＹ＋４とする。このように、本実施の形態では、説明の簡単化のために、アドレスが１インクリメントされるごとにつぎのバンク１１０の領域となる。
【００８０】
出力データが格納される先頭の領域を示すアドレスはＺである。例えば、バンク１１０−０の出力データの先頭の領域を示すアドレスがＺである。そのため、先頭の領域のつぎにバンク１１０−１の領域を示すアドレスをＺ＋１、バンク１１０−２の領域を示すアドレスをＺ＋２、バンク１１０−３の領域を示すアドレスをＺ＋３とし、つぎにバンク１１０−０の領域を示すアドレスをＺ＋４とする。このように、本実施の形態では、説明の簡単化のために、アドレスが１インクリメントされるごとにつぎのバンク１１０の領域となる。
【００８１】
つぎに、ＦＦＴ命令制御回路４３２の詳細な説明の前に、バンク１１０アクセス例について簡単に説明する。
【００８２】
図９は、シーケンシャルなバンクアクセス例を示す説明図である。ここでは、入力データストリームは２つであり、出力ストリームデータは１つであり、かつ入力データと出力データとのデータ幅が同じであるような場合を例に挙げる。このような場合の演算命令としては複素乗算命令などが挙げられる。ここでは、入力データ群の格納先として入力ＦＩＦＯ４２１−Ａと入力ＦＩＦＯ４２１−Ｂとが利用され、出力データ群の格納先としては出力ＦＩＦＯ４２２−Ｆが利用される例を示す。図９では、理解の容易化のために、演算データパス４１１のレイテンシを無視した例で有るが、実際には、設計者が、演算によるレイテンシなども考慮して入力データの読み出しと出力データの書き込みとのいずれもバンクに対してシーケンシャルになるようにタイミングを調整する。
【００８３】
１つのバンクラインの中には、１６ポイント分のデータが含まれる。図９の例では、アドレスＸが示すバンク１１０−０の領域から順に入力データＡ０〜入力データＡ５などが格納されてある。具体的に、例えば、アドレスＸが示すバンク１１０−０の領域に入力データＡ０、バンク１１０−１の領域に入力データＡ１、バンク１１０−２の領域に入力データＡ２、バンク１１０−３の領域に入力データＡ３が格納される。そして、例えば、バンク１１０―０の領域に入力データＡ４が格納される。
【００８４】
また、図９の例では、アドレスＹが示すバンク１１０−０の領域から順に入力データＢ０〜入力データＢ５などが格納される。図９の例では、アドレスＺが示すバンク１１０−０の領域から順に出力データＦ０〜出力データＦ５が格納される。バンク１１０に格納された入力データＡ０〜Ａ５、入力データＢ０〜Ｂ５、および出力データＦ０〜Ｆ５に付された（  ）の中の番号は、サイクルの番号である。
【００８５】
まず、ｃｙｃｌｅ（０）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−０に格納された入力データＡ０を読み出して入力ＦＩＦＯ４２１−Ａに格納させる。
【００８６】
つぎに、ｃｙｃｌｅ（１）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−１に格納された入力データＡ１を読み出して入力ＦＩＦＯ４２１−Ａに格納させる。また、ｃｙｃｌｅ（１）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−０に格納された入力データＢ０を読み出して入力ＦＩＦＯ４２１−Ｂに格納させる。ここで、同一バンク１１０に格納された入力データＢ０と入力データＡ０とが異なるタイミングにおいてデータメモリ１０１から読み出されるのは、同一バンク１１０で異なるアドレスが示す領域に格納されデータを同時に読み出すことができないためである。ただし、メモリインターリーブであれば、入力データＡ１と入力データＢ０とのように異なるバンク１１０に格納されたデータ同士は、同じタイミングで読み出すことができる。
【００８７】
ｃｙｃｌｅ（２）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−２に格納された入力データＡ２を読み出して入力ＦＩＦＯ４２１−Ａに格納させる。また、ｃｙｃｌｅ（２）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−１に格納された入力データＢ１を読み出して入力ＦＩＦＯ４２１−Ｂに格納させる。また、ｃｙｃｌｅ（２）において、演算データパス４１１が、入力データＡ２と入力データＢ１とに対して複素演算を行い、演算結果である出力データＦ０を出力ＦＩＦＯ４２２−Ｆに格納させる。そして、ｃｙｃｌｅ（２）において、演算データパス４１１が、出力ＦＩＦＯ４２２−Ｆに格納された出力データＦ０をバンク１１０−０に格納させる。
【００８８】
ｃｙｃｌｅ（３）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−３に格納された入力データＡ３を読み出して入力ＦＩＦＯ４２１−Ａに格納させる。また、ｃｙｃｌｅ（３）において、ＭＡＵ４１３が、データメモリ１０１からバンク１１０−２に格納された入力データＢ２を読み出して入力ＦＩＦＯ４２１−Ｂに格納させる。また、ｃｙｃｌｅ（３）において、演算データパス４１１が、入力データＡ３と入力データＢ２とに対して複素演算を行い、演算結果である出力データＦ１を出力ＦＩＦＯ４２２−Ｆに格納させる。そして、ｃｙｃｌｅ（３）において、演算データパス４１１が、出力ＦＩＦＯ４２２−Ｆに格納された出力データＦ１をバンク１１０−１に格納させる。
【００８９】
このように、シーケンシャルアクセスであれば、入力データおよび出力データの読み出しおよび格納のタイミングをずらすことにより、バンク１１０の衝突を抑制することができる。
【００９０】
図１０は、ステージ１からステージ５までの命令のバンクアクセス例を示す説明図である。例えば、入力データ群については、データメモリ１０１対してシーケンシャルアクセスであるため、バンクアクセスがシーケンシャルである。出力データストリームについては、データメモリ１０１に対してストライドアクセスのため、２つのアクセスのバンク衝突が発生することによりストールが発生する。
【００９１】
例えば、４つのバンク１１０に対して、サイクルごとに１つのバンク１１０が競合するため、３つのバンク１１０しかアクティブにならず、ＦＩＦＯ４１２が溢れてストールが発生する。具体的に、例えば、サイクル９において、出力ＦＩＦＯ４２２−Ｅに格納されたデータがデータメモリ１０１に格納されないため、出力データＥ７が溢れてストールすることになる。
【００９２】
ただし、出力データ群がバンク１１０に対してシーケンシャルアクセスであり、入力データ群がバンク１１０に対してストライドアクセスである場合、入力ＦＩＦＯ４２１に入力データが枯渇してストールが発生する。
【００９３】
そこで、本実施の形態では、データ処理装置１００が、アドレスの割当順に従って入力データを読み出す際に、該割当順に応じたバンクの順に従って選択した出力データを、読み出し先でないバンクに該バンクの順序に従って格納させる。これにより、バンク衝突を回避することができる。したがって、バンクアクセスの衝突回数を低減させることができるため、バンク衝突によるストールの時間が減るため、フーリエ変換の命令の実行に要する時間の短縮を図ることができる。
【００９４】
ここで、ステージ１からステージ５はいずれも同じバンクアクセスパターンになる。そして、ステージ６におけるバンクアクセスはステージ１〜ステージ５、ステージ７以降とは異なるバンクアクセスパターンとなる。ステージ７以降は、ストライドアクセスであるが、バンク単位であるとシーケンシャルアクセスとなる。また、入力データについては、図９や図１０に示したように、シーケンシャルアクセスであるため、図示などの詳細な説明は省略する。
【００９５】
特定のステージがステージ１〜５の場合、制御部１２２は、特定のステージにおける複数のサイクルのうちの第１特定サイクルにおいて、最も早い第１出力データと最も早い第２出力データとの組み合わせを選択部３０２に選択させる制御を行う。ここでの第１特定サイクルは、例えば、ステージ１〜５における複数のサイクルのうちのサイクルであり、ｃｙｃｌｅを４で割った余りが０の場合と３の場合のサイクルである。
【００９６】
また、制御部１２２は、第２特定サイクルにおいて、最も早い第１出力データと２番目に早い第２出力データとの組み合わせと、２番目に早い第１出力データと最も早い第２出力データとの組み合わせと、のうちのいずれかを選択部３０２に選択させる制御を行う。ここでは、第２特定サイクルは、例えば、ステージ１〜５における複数のサイクルのうちのサイクルであり、例えばｃｙｃｌｅを４で割った余りが１の場合と２の場合のサイクルである。後述する図１１Ｂ〜図１１Ｆでは、第２特定サイクルにおいて、制御部１２２は、最も早い第１出力データと２番目に早い第２出力データとの組み合わせを選択部３０２に選択させる制御を行う。後述する図１１Ｂ〜図１１Ｆに示すように、特定のステージにおける第２特定サイクルにおいて選択部３０２に選択させる組み合わせは動的に変化しない。
【００９７】
図１１Ａ〜図１１Ｆは、ステージ１からステージ５までの命令における出力データについてのバンクアクセス制御例を示す説明図である。図１１Ａには、最終的にデータメモリ１０１に出力データ群が格納される例を示す。図１１Ａに示すように、出力データＦは、バンク１１０−０とバンク１１０−２に出力ＦＩＦＯ４２２−Ｆに格納された順の並びで交互に格納される。図１１Ａに示すように、出力データＥは、バンク１１０−１とバンク１１０−３に出力ＦＩＦＯ４２２−Ｅに格納された順の並びで交互に格納される。
【００９８】
まず、図１１Ｂを用いてｃｙｃｌｅ（０）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（０）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−２とバンク１１０−３にアクセスする。そこで、ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ０をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ０をバンク１１０−０に格納させる。ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ０をマルチプレクサ４２３−Ｅに選択させるように制御し、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ０をバンク１１０−１に格納させる。
【００９９】
つぎに、図１１Ｃを用いてｃｙｃｌｅ（１）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（１）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−３とバンク１１０−０にアクセスする。そこで、ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ１をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ１をバンク１１０−２に格納させる。また、ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、Ｅ＃１に格納された出力データＥ２をマルチプレクサ４２３−Ｅに選択させるように制御する。ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ２をバンク１１０−１に格納させる。このように、例えば、ｃｙｃｌｅ（１）において、ＤＭＡ４３１−Ｅがバンク１１０−２に出力データＥ１を格納させる場合、ＤＭＡ４３１−Ａによるバンク１１０−２への入力データの読み出しと衝突してしまう。そのため、ＤＭＡ４３１−Ｅが出力データＥ１よりも先に出力データＥ２をバンク１１０−１に格納させる。これにより、バンクアクセスの衝突を回避することができる。
【０１００】
つぎに、図１１Ｄを用いてｃｙｃｌｅ（２）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（２）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−０とバンク１１０−１にアクセスする。そこで、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｆ＃１に格納された出力データＦ３をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ３をバンク１１０−２に格納させる。ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ１をマルチプレクサ４２３−Ｅにさせるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ１をバンク１１０−３に格納させる。本実施の形態では、ステージ１〜ステージ５までについては、このようなアクセスを４サイクルごとに繰り返す。
【０１０１】
つぎに、図１１Ｅを用いてｃｙｃｌｅ（３）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（３）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−１とバンク１１０−２にアクセスする。そこで、ｃｙｃｌｅ（３）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ２をルチプレクサ４２３−Ｆに選択させるように制御する。ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ２をバンク１１０−０に格納させる。また、ｃｙｃｌｅ（３）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ３をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ３をバンク１１０−３に格納させる。
【０１０２】
つぎに、図１１Ｆを用いてｃｙｃｌｅ（４）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（４）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−２とバンク１１０−３にアクセスする。そこで、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ４をマルチプレクサ４２３−Ｆに選択させるよう制御する。ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ４をバンク１１０−０に格納させる。また、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ４をマルチプレクサ４２３−Ｅに選択させるように制御し、ＤＭＡ４３１−Ｅは、例えば、出力データＥ４をバンク１１０−１に格納させる。
【０１０３】
このように、ｃｙｃｌｅ（０）〜ｃｙｃｌｅ（３）のようなバンクアクセスを４サイクルごとに繰り返すことにより、バンク１１１の衝突を回避することができる。
【０１０４】
また、特定のステージがステージ６の場合について説明する。図３に示す制御部１２２は、第１特定サイクルにおいて、最も早い第１出力データと２番目に早い第１出力データとの組み合わせと、最も早い第２出力データと２番目に早い第２出力データとの組み合わせと、のうちのいずれかを選択部３０２に選択させる制御を行う。第１特定サイクルは、ステージ６における複数のサイクルに含まれるサイクルであり、例えばｃｙｃｌｅを４で割った余りの数が０と２の場合のサイクルである。後述する図１２Ｂ〜図１２Ｆでは、第１特定サイクルがｃｙｃｌｅを４で割った余りの数が０の場合のサイクルであると、制御部１２２は、最も早い第１出力データと２番目に早い第１出力データとの組み合わせを選択部３０２に選択させる制御を行う。また、後述する図１２Ｂ〜図１２Ｆでは、第１特定サイクルがｃｙｃｌｅを４で割った余りの数が２の場合のサイクルであると、制御部１２２は、最も早い第２出力データと２番目に第２出力データとの組み合わせを選択部３０２に選択させる制御を行う。このように、後述する図１２Ｂ〜図１２Ｆに示すように、特定のステージにおける第１特定サイクルにおいて選択部３０２に選択させる組み合わせは動的に変化しない。
【０１０５】
また、制御部１２２は、第２特定サイクルにおいて、最も早い第１出力データと２番目に早い第２出力データとの組み合わせと、最も早い第２出力データと２番目に早い第１出力データとの組み合わせと、のうちのいずれかを選択部３０２に選択させる制御を行う。第２特定サイクルは、ステージ６における複数のサイクルのうちのサイクルであり、例えばｃｙｃｌｅを４で割った余りの数が１の場合のサイクルである。後述する図１２Ｂ〜図１２Ｆでは、第２特定サイクルにおいて、制御部１２２は、最も早い第１出力データと２番目に早い第２出力データとの組み合わせを選択部３０２に選択させる制御を行う。後述する図１２Ｂ〜図１２Ｆに示すように、特定のステージにおける第２特定サイクルにおいて選択部３０２に選択させる組み合わせは動的に変化しない。
【０１０６】
また、制御部１２２は、複数のサイクルのうちの第３特定サイクルにおいて、最も早い第１出力データと最も早い第２出力データを選択部３０２に選択させる制御を行う。ここでの第３特定サイクルは、ステージ６における複数のサイクルのうちのサイクルであり、ｃｙｃｌｅを４で割った余りの数が３の場合のサイクルである。
【０１０７】
図１２Ａ〜図１２Ｆは、ステージ６の命令における出力データについてのバンクアクセス制御例を示す説明図である。図１２Ａには、最終的にデータメモリ１０１に出力データ群が格納される例を示す。図１２Ａに示すように、出力データＦは、バンク１１０−０とバンク１１０−１に出力ＦＩＦＯ４２２−Ｆに格納された順に交互に先頭のアドレスから順に格納される。図１２Ａに示すように、出力データＥは、バンク１１０−２とバンク１１０−３に出力ＦＩＦＯ４２２−Ｅに格納された順に交互にアドレスから順に格納される。図１２Ａに示すように、バンク１１０には、出力データＦがバンク１１０−０とバンク１１０−１に格納され、出力データＥがバンク１１０−２とバンク１１０-３に格納される。このように、ステージ６についても出力データのアクセスがストライドアクセスとなる。
【０１０８】
ステージ６の命令については、ＦＦＴ命令制御回路４３２は、データを少なくとも３つ出力ＦＩＦＯ４２２−Ｆと出力ＦＩＦＯ４２２−Ｅとに溜めてから出力を開始するように制御する。
【０１０９】
まず、図１２Ｂを用いてｃｙｃｌｅ（０）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（０）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとはそれぞれバンク１１０−２とバンク１１０−３にアクセスする。そこで、ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ０をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ０をバンク１１０−０に格納させる。ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、Ｆ＃１に格納された出力データＦ１をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、出力データＦ１をバンク１１０−１に格納させる。
【０１１０】
つぎに、図１２Ｃを用いてｃｙｃｌｅ（１）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（１）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−３とバンク１１０−０にアクセスする。そこで、ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、Ｆ＃１に格納された出力データＦ３をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、出力データＦ３をバンク１１０−１に格納させる。また、ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ０をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、出力データＥ０をバンク１１０−２に格納させる。
【０１１１】
つぎに、図１２Ｄを用いてｃｙｃｌｅ（２）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（２）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−０とバンク１１０−１にアクセスする。そこで、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｅ＃１に格納された出力データＥ２をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＥ２をバンク１１０−２に格納させる。また、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ１をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ１をバンク１１０−３に格納させる。
【０１１２】
つぎに、図１２Ｅを用いてｃｙｃｌｅ（３）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（３）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−０とバンク１１０−１にアクセスする。そこで、ｃｙｃｌｅ（３）において、ＦＦＴ命令制御回路４３２は、Ｅ＃１に格納された出力データＦ２をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ２をバンク１１０−０に格納させる。また、ｃｙｃｌｅ（３）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に格納された出力データＥ３をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、出力データＥ３をバンク１１０−３に格納させる。
【０１１３】
つぎに、図１２Ｆを用いてｃｙｃｌｅ（４）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（４）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−０とバンク１１０−１にアクセスする。そこで、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ４をマルチプレクサ４２３−Ｆに選択させるよう制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ４をバンク１１０−０に格納させる。また、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｆ＃１に格納された出力データＦ５をマルチプレクサ４２３−Ｅに選択させるよう制御する。そして、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＦ５をバンク１１０−１に格納させる。
【０１１４】
このように、ステージ６の命令については、ｃｙｃｌｅ（０）とｃｙｃｌｅ（２）において、一方のマルチプレクサが他のＦＩＦＯ４１２の先頭から２つ目の出力データを選択する。また、ｃｙｃｌｅ（１）において、マルチプレクサの各々が、ＦＩＦＯ４１２の先頭から２つ目の出力を選択する。ＦＦＴ命令制御回路４３２は、このようなアクセスを４サイクルごとに繰り返す。これにより、バンク衝突を回避することができる。
【０１１５】
図１３Ａ〜図１３Ｆは、ステージ７の命令における出力データについてのバンクアクセス制御例を示す説明図である。ステージ７以降のステージでは、バンクアクセスの動きは同じであり、出力データストリームは、データメモリ１０１に対してストライドアクセスである。図１３Ａには、ステージ７において最終的にデータメモリ１０１に出力データ群が格納される例を示す。図１３Ａに示すように、出力データＦは、バンク１１０−０〜バンク１１０−３の同一のメモリラインに出力ＦＩＦＯ４２２−Ｆに格納された順に交互に先頭のアドレスから順に格納される。そして、図１３Ａに示すように、出力データＥは、バンク１１０−０〜バンク１１０−３の出力データＦが格納されたメモリラインのつぎのメモリラインに出力ＦＩＦＯ４２２−Ｅに格納された順に格納される。
【０１１６】
まず、図１３Ｂを用いてｃｙｃｌｅ（０）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（０）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−１とバンク１１０−２にアクセスする。そこで、ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に格納された出力データＦ０をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ０をバンク１１０−０に格納させる。ｃｙｃｌｅ（０）において、ＦＦＴ命令制御回路４３２は、マルチプレクサ４２３−Ｅにいずれも選択させないように制御する。
【０１１７】
つぎに、図１３Ｃを用いてｃｙｃｌｅ（１）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（１）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−２とバンク１１０−３にアクセスする。そこで、ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に記憶された出力データＦ１をマルチプレクサ４２３−Ｆに選択させるよう制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ１をバンク１１０−１に格納させる。ｃｙｃｌｅ（１）において、ＦＦＴ命令制御回路４３２は、マルチプレクサ４２３−ＥにＥ＃０に格納されたデータＥ０を選択させるようにマルチプレクサ４２３−Ｅを制御し、ＤＭＡ４３１−Ｅは、例えば、出力データＥ０をバンク１１０−０に格納させる。
【０１１８】
つぎに、図１３Ｄを用いてｃｙｃｌｅ（２）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（２）において、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−３とバンク１１０−０にアクセスする。そこで、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に記憶された出力データＦ２をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ２をバンク１１０−２に格納させる。また、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に記憶された出力データＥ１をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、出力データＥ１をバンク１１０−１に格納させる。
【０１１９】
つぎに、図１３Ｅを用いてｃｙｃｌｅ（３）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（３）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−０とバンク１１０−１にアクセスする。そこで、ｃｙｃｌｅ（３）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に記憶された出力データＦ３をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、選択された出力データＦ３をバンク１１０−３に格納させる。また、ｃｙｃｌｅ（２）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に記憶された出力データＥ２をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、選択された出力データＥ２をバンク１１０−２に格納させる。
【０１２０】
つぎに、図１３Ｆを用いてｃｙｃｌｅ（４）について説明する。図示省略するが、例えば、ｃｙｃｌｅ（４）においては、ＤＭＡ４３１−ＡとＤＭＡ４３１−Ｂとは、それぞれバンク１１０−１とバンク１１０−２にアクセスする。そこで、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｆ＃０に記憶された出力データＦ４をマルチプレクサ４２３−Ｆに選択させるように制御する。そして、ＤＭＡ４３１−Ｆは、例えば、出力データＦ４をバンク１１０−０に格納させる。また、ｃｙｃｌｅ（４）において、ＦＦＴ命令制御回路４３２は、Ｅ＃０に記憶された出力データＥ３をマルチプレクサ４２３−Ｅに選択させるように制御する。そして、ＤＭＡ４３１−Ｅは、例えば、出力データＥ３をバンク１１０−３に格納させる。
【０１２１】
このように、出力データＥについてのストリームを出力データＦについてのストリームよりも１サイクル遅らせることによって、バンク衝突を回避することができる。
【０１２２】
（ＦＦＴ命令制御回路４３２）
つぎに、ＦＦＴ命令制御回路４３２の構成例とＦＦＴ命令制御回路４３２の信号生成のアルゴリズム例について詳細に説明する。
【０１２３】
図１４は、ステージ１〜５において生成する信号列とアルゴリズム例を示す説明図である。信号は、制御信号Ｆｓｅｌと、制御信号Ｅｓｅｌと、アドレスＦａｄｄｒと、アドレスＥａｄｄｒと、を有する。制御信号Ｆｓｅｌと制御信号Ｅｓｅｌは、４ｃｙｃｌｅごとに同一の値となる。
【０１２４】
まず、マルチプレクサ４２３−Ｆを制御する制御信号Ｆｓｅｌについて説明する。制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（０）において０に設定され、ｃｙｃｌｅ（１）において０に設定される。そして、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（２）において１に設定され、ｃｙｃｌｅ（３）において０に設定される。つぎに、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（４）においてｃｙｃｌｅ（０）と同様に０に設定され、ｃｙｃｌｅ（５）においてｃｙｃｌｅ（１）と同様に０に設定される。そして、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（６）においてｃｙｃｌｅ（２）と同様に１に設定され、ｃｙｃｌｅ（７）においてｃｙｃｌｅ（３）と同様に０に設定される。制御信号Ｆｓｅｌの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２である場合に、制御信号Ｆｓｅｌを１に設定し、余りが２でない場合に、Ｆｓｅｌを０に設定する。
【０１２５】
つぎに、マルチプレクサ４２３−Ｅを制御する制御信号Ｅｓｅｌについて説明する。制御信号Ｅｓｅｌは、例えば、ｃｙｃｌｅ（０）において０に設定され、制御信号Ｅｓｅｌは、ｃｙｃｌｅ（１）〜ｃｙｃｌｅ（３）においてそれぞれ１、０、０に設定される。制御信号Ｅｓｅｌは、例えば、ｃｙｃｌｅ（４）においてｃｙｃｌｅ（０）と同様に０に設定され、制御信号Ｅｓｅｌは、ｃｙｃｌｅ（５）〜ｃｙｃｌｅ（７）においてｃｙｃｌｅ（１）〜ｃｙｃｌｅ（３）と同様にそれぞれ１、０、０に設定される。Ｅｓｅｌの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１である場合に、Ｅｓｅｌを１に設定し、余りが１でない場合に、Ｅｓｅｌを０に設定する。
【０１２６】
つぎに、ＤＭＡ４３１−Ｆが書き込む領域を示すアドレスＦａｄｄｒについて説明する。図１４の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＦａｄｄｒは、ｃｙｃｌｅ（０）において０、ｃｙｃｌｅ（１）において２、ｃｙｃｌｅ（２）において６、ｃｙｃｌｅ（３）において４、ｃｙｃｌｅ（４）において８、ｃｙｃｌｅ（５）において１０、ｃｙｃｌｅ（６）において１４、ｃｙｃｌｅ（７）において１２、に設定される。
【０１２７】
アドレスＦａｄｄｒの生成アルゴリズムに示すように、数ｄは、４サイクルごとに規則的に値が設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは０に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは２に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは６に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは４に設定される。そして、アドレスＦａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１２８】
つぎに、ＤＭＡ４３１−Ｆが書き込む領域を示すアドレスＥａｄｄｒについて説明する。図１４の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＥａｄｄｒは、ｃｙｃｌｅ（０）において１、ｃｙｃｌｅ（１）において５、ｃｙｃｌｅ（２）において３、ｃｙｃｌｅ（３）において７、ｃｙｃｌｅ（４）において９、ｃｙｃｌｅ（５）において１３、ｃｙｃｌｅ（６）において１１、ｃｙｃｌｅ（７）において１５、に設定される。
【０１２９】
アドレスＥａｄｄｒの生成アルゴリズムに示すように、数ｄは４サイクルごとに規則的に値が設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは１に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは５に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは３に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは７に設定される。そして、アドレスＥａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１３０】
図１５は、ステージ６において生成する信号列とアルゴリズム例を示す説明図である。信号は、制御信号Ｆｓｅｌと、制御信号Ｅｓｅｌと、アドレスＦａｄｄｒと、アドレスＥａｄｄｒと、を有する。制御信号Ｆｓｅｌと制御信号Ｅｓｅｌは、４ｃｙｃｌｅごとに同一の値となる。
【０１３１】
まず、マルチプレクサ４２３−Ｆを制御する制御信号Ｆｓｅｌについて説明する。制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（０）において０に設定され、ｃｙｃｌｅ（１）において１に設定される。そして、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（２）において２に設定され、ｃｙｃｌｅ（３）において０に設定される。つぎに、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（４）においてｃｙｃｌｅ（０）と同様に０に設定され、ｃｙｃｌｅ（５）においてｃｙｃｌｅ（１）と同様に１に設定される。そして、制御信号Ｆｓｅｌは、例えば、ｃｙｃｌｅ（６）においてｃｙｃｌｅ（２）と同様に２に設定され、ｃｙｃｌｅ（７）においてｃｙｃｌｅ（３）と同様に０に設定される。制御信号Ｆｓｅｌの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１である場合に、制御信号Ｆｓｅｌを１に設定する。ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２である場合に、Ｆｓｅｌを２に設定し、余りが１および２以外の場合に、Ｆｓｅｌを０に設定する。
【０１３２】
つぎに、マルチプレクサ４２３−Ｅを制御する制御信号Ｅｓｅｌについて説明する。制御信号Ｅｓｅｌは、例えば、ｃｙｃｌｅ（０）において２に設定され、制御信号Ｅｓｅｌは、ｃｙｃｌｅ（１）〜ｃｙｃｌｅ（３）において０に設定される。制御信号Ｅｓｅｌは、例えば、ｃｙｃｌｅ（４）においてｃｙｃｌｅ（０）と同様に２に設定され、制御信号Ｅｓｅｌは、ｃｙｃｌｅ（５）〜ｃｙｃｌｅ（７）においてｃｙｃｌｅ（１）〜ｃｙｃｌｅ（３）と同様に０に設定される。Ｅｓｅｌの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０である場合に、Ｅｓｅｌを２に設定し、余りが０以外の場合に、Ｅｓｅｌを０に設定する。
【０１３３】
つぎに、ＤＭＡ４３１−Ｆが書き込む領域を示すアドレスＦａｄｄｒについて説明する。図１５の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＦａｄｄｒは、ｃｙｃｌｅ（０）において０、ｃｙｃｌｅ（１）において５、ｃｙｃｌｅ（２）において６、ｃｙｃｌｅ（３）において４、ｃｙｃｌｅ（４）において８、ｃｙｃｌｅ（５）において１３、ｃｙｃｌｅ（６）において１４、ｃｙｃｌｅ（７）において１２、に設定される。
【０１３４】
アドレスＦａｄｄｒの生成アルゴリズムに示すように、数ｄは、４サイクルごとに規則的に値が設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは０に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは５に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは６に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは４に設定される。そして、アドレスＦａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１３５】
つぎに、ＤＭＡ４３１−Ｅが書き込む領域を示すアドレスＥａｄｄｒについて説明する。図１５の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＥａｄｄｒは、ｃｙｃｌｅ（０）において１、ｃｙｃｌｅ（１）において２、ｃｙｃｌｅ（２）において３、ｃｙｃｌｅ（３）において７、ｃｙｃｌｅ（４）において９、ｃｙｃｌｅ（５）において１０、ｃｙｃｌｅ（６）において１１、ｃｙｃｌｅ（７）において１５、に設定される。
【０１３６】
アドレスＥａｄｄｒの生成アルゴリズムに示すように、数ｄは、４サイクルごとに規則的に値が設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは１に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは２に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは３に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは７に設定される。そして、アドレスＥａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１３７】
図１６は、ステージ７以降において生成する信号列とアルゴリズム例を示す説明図である。信号は、制御信号Ｆｓｅｌと、制御信号Ｅｓｅｌと、アドレスＦａｄｄｒと、アドレスＥａｄｄｒと、を有する。
【０１３８】
まず、マルチプレクサ４２３−Ｆを制御する制御信号Ｆｓｅｌと、マルチプレクサ４２３−Ｅを制御する制御信号Ｅｓｅｌと、について説明する。制御信号Ｆｓｅｌおよび制御信号Ｅｓｅｌは、例えば、常時０に設定される。制御信号Ｆｓｅｌおよび制御信号Ｅｓｅｌの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ＥｓｅｌおよびＦｓｅｌには０が設定される。
【０１３９】
つぎに、ＤＭＡ４３１−Ｆが書き込む領域を示すアドレスＦａｄｄｒについて説明する。図１６の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＦａｄｄｒは、ｃｙｃｌｅ（０）において０、ｃｙｃｌｅ（１）において１、ｃｙｃｌｅ（２）において２、ｃｙｃｌｅ（３）において３、ｃｙｃｌｅ（４）において８、ｃｙｃｌｅ（５）において９、ｃｙｃｌｅ（６）において１０、ｃｙｃｌｅ（７）において１１、に設定される。
【０１４０】
アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは０に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは１に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは２に設定される。アドレスＦａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは３に設定される。そして、アドレスＦａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１４１】
つぎに、ＤＭＡ４３１−Ｅが書き込む領域を示すアドレスＥａｄｄｒについて説明する。図１６の例では、各アドレスを、アドレスＺに加算するインクリメント値によって表す。アドレスＥａｄｄｒは、ｃｙｃｌｅ（０）において４、ｃｙｃｌｅ（１）において５、ｃｙｃｌｅ（２）において６、ｃｙｃｌｅ（３）において７、ｃｙｃｌｅ（４）において１２、ｃｙｃｌｅ（５）において１３、ｃｙｃｌｅ（６）において１４、ｃｙｃｌｅ（７）において１５、に設定される。
【０１４２】
アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが０の場合に、数ｄは４に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが１の場合に、数ｄは５に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが２の場合に、数ｄは６に設定される。アドレスＥａｄｄｒの生成アルゴリズムに示すように、ＦＦＴ命令制御回路４３２は、ｃｙｃｌｅを４で割った余りが３の場合に、数ｄは７に設定される。そして、アドレスＥａｄｄｒは、アドレスＺと、設定した数ｄと、ｃｙｃｌｅを４で割った値と８との乗算結果と、の合計値である。
【０１４３】
図１７は、ＦＦＴ命令制御回路例１を示す説明図である。ＦＦＴ命令制御回路４３２は、例えば、開始タイミング制御回路１７０１と、ＦＩＦＯ選択信号生成回路１７０２と、アドレス信号生成回路１７０３と、を有する。
【０１４４】
開始タイミング制御回路１７０１は、プロセッサの状態信号を入力として、アドレス信号生成と選択信号生成の動作開始タイミングを制御可能なｃｙｃｌｅ信号を出力する。プロセッサの状態信号とは、例えば、入力についてのＤＭＡ４３１の転送信号、命令のレイテンシを示す情報などが挙げられる。ｃｙｃｌｅ信号は、動作開始タイミングからカウントアップされる。
【０１４５】
ＦＩＦＯ選択信号生成回路１７０２は、ステージ番号、出力先頭ポインタ、ｃｙｃｌｅ信号などを入力として、マルチプレクサ４２３−Ｆとマルチプレクサ４２３−Ｅとを制御する制御信号Ｆｓｅｌ，Ｅｓｅｌを生成する。ステージ番号は、演算データパス４１１から入力される。出力先頭ポインタとは、データメモリ１０１において出力データを格納させる先頭の領域を示すアドレスである。本実施の形態では、出力先頭ポインタは、アドレスＺである。
【０１４６】
アドレス信号生成回路１７０３は、出力データＦと出力データＥとの書き込み先のアドレス信号Ｆａｄｄｒ，Ｅａｄｄｒを生成する。
【０１４７】
図１８は、ＦＦＴ命令制御回路例２を示す説明図である。ＦＦＴ命令制御回路４３２は、開始タイミング制御回路１７０１と、ＦＩＦＯ選択信号生成回路１７０２と、を有する。ＤＭＡ４３１−Ｆに含まれるＦアドレス信号生成回路１８０１とＤＭＡ４３１−Ｅに含まれるＥアドレス信号生成回路１８０２とは、図１８に示したアドレス信号生成回路１７０３に相当する。各回路の機能は、図１７の例と同じである。
【０１４８】
図１９は、ＦＩＦＯ選択信号生成回路例を示す説明図である。ここでは、制御信号Ｆｓｅｌについて説明する。ＦＩＦＯ選択信号生成回路１７０２は、例えば、回路１９０１と、Ｆｓｅｌテーブル１９０２と、を有する。
【０１４９】
回路１９０１は、ｃｙｃｌｅ信号を入力として、ｃｙｃｌｅ信号が示すサイクル数を４で割った余りの数を出力する。これにより、４サイクルごとに制御を行うことができる。
【０１５０】
Ｆｓｅｌテーブル１９０２は、余りの数とステージ番号とによって選択信号Ｆｓｅｌを生成する。
【０１５１】
図２０は、Ｆｓｅｌテーブル例を示す説明図である。Ｆｓｅｌテーブル１９０２は、例えば、ステージ番号およびｃｙｃｌｅを４で割った余りの数に対応付けて制御信号Ｆｓｅｌの値を記憶する。Ｆｓｅｌテーブル１９０２は、例えば、ステージ番号、余りの数、Ｆｓｅｌのフィールドを有する。各フィールドに情報が設定されることによってレコード（例えば、２００１−１など）として記憶される。
【０１５２】
ステージ番号のフィールドには、ＦＦＴ処理のバタフライ演算のステージ番号が設定される。余りの数のフィールドには、ｃｙｃｌｅを４で割った余りの数が設定される。Ｆｓｅｌのフィールドには、制御信号Ｆｓｅｌの値が設定される。
【０１５３】
例えば、レコード２００１−１によれば、ステージ番号がステージ１〜５のいずれかであり、ｃｙｃｌｅを４で割った余りの数が０の場合に、制御信号Ｆｓｅｌは０となる。例えば、レコード２００１−６によれば、ステージ番号がステージ６であり、ｃｙｃｌｅを４で割った余りの数が１の場合に、制御信号Ｆｓｅｌは１となる。また、例えば、レコード２００１−９によれば、ステージ番号がステージ７以降であり、ｃｙｃｌｅを４で割った余りの数が０の場合に、制御信号Ｆｓｅｌは０となる。
【０１５４】
また、Ｆｓｅｌテーブル１９０２については、例えば、ステージ番号がステージ７であれば、制御信号Ｆｓｅｌは０のように表してもよい。
【０１５５】
図２１は、アドレス信号生成回路例を示す説明図である。ここでは、アドレスＦａｄｄｒについて説明する。アドレス信号生成回路１７０３は、回路２１０１と、Ｆａｄｄｒテーブル２１０２と、回路２１０３と、加算回路２１０４と、を有する。回路２１０１は、ｃｙｃｌｅを４で割った余りの数をＦａｄｄｒテーブル２１０２に入力する。
【０１５６】
Ｆａｄｄｒテーブル２１０２は、例えば、ステージ番号と余りの数とによって数ｄを生成する。そして、回路２１０３は、サイクル数を４で割って８を乗算した結果の数を算出して加算回路に入力する。加算回路２１０４は、数ｄと、回路２１０３から入力される数と、アドレスＺと、を合計することによってアドレスＦａｄｄｒを算出する。
【０１５７】
図２２は、Ｆａｄｄｒテーブル例を示す説明図である。Ｆａｄｄｒテーブル２１０２は、ステージ番号およびステージ番号に対応付けて数ｄを記憶する。Ｆａｄｄｒテーブル２１０２は、ステージ番号、余りの数、ｄのフィールドを有する。各フィールドに情報が設定されることによってレコード（例えば、２２０１−１など）として記憶される。
【０１５８】
ステージ番号のフィールドには、ＦＦＴ処理のバタフライ演算のステージ番号が設定される。余りの数のフィールドには、ｃｙｃｌｅを４で割った余りの数が設定される。ｄのフィールドには、アドレスＦａｄｄｒを算出するための数が設定される。
【０１５９】
例えば、レコード２２０１−１によれば、ステージ番号がステージ１〜ステージ５のいずれかであり、ｃｙｃｌｅを４で割った余りの数が０の場合に、数ｄは０となる。また、例えば、レコード２２０１−６によれば、ステージ番号がステージ６であり、ｃｙｃｌｅを４で割った余りの数が１の場合、数ｄは５となる。
【０１６０】
（制御部１２２による制御処理手順例）
図２３は、制御部による制御処理手順例を示すフローチャートである。制御部１２２は、ステージ番号とサイクル数との入力を受け付ける（ステップＳ２３０１）。制御部１２２は、出力データのデータメモリへの書き込みが終了したか否かを判断する（ステップＳ２３０２）。
【０１６１】
ステップＳ２３０２において、終了していないと判断された場合（ステップＳ２３０２：Ｎｏ）、制御部１２２は、ステージ番号とサイクル数とにおいて、バンクの連続順序に従うように出力ＦＩＦＯに格納された順に基づき出力ＦＩＦＯから出力データを選択させる制御を行う（ステップＳ２３０３）。そして、制御部１２２は、ステージ番号とサイクル数とにおいて、選択された出力データをバンクの連続順序に応じたバンクに書き込む制御を行い（ステップＳ２３０４）、ステップＳ２３０２へ戻る。
【０１６２】
ステップＳ２３０２において、終了したと判断された場合（ステップＳ２３０２：Ｙｅｓ）、制御部１２２は、一連の処理を終了する。
【０１６３】
以上説明したように、データ処理装置１００は、アドレスの割当順に従って入力データを読み出す際に、該割当順に応じたバンクの順に従って選択した出力データを、読み出し先でないバンクに該バンクの順序に従って格納させる。これにより、バンク衝突を回避することができる。したがって、バンクアクセスの衝突回数を低減させることができるため、バンク衝突によるストールの時間が減るため、フーリエ変換の命令の実行に要する時間の短縮を図ることができる。
【０１６４】
また、データ処理装置１００は、出力データ群の中からバンクの連続順序に従うバンクに格納される出力データのうち出力バッファ１２１に格納された順序が早い順に出力対象となる出力データを選択する。これにより、先に格納された出力データを先に処理することができ、古いデータが出力バッファ１２１に残るのを抑制することができる。
【０１６５】
また、データ処理装置１００は、出力ストリームが２つの場合に、第１出力データ群および第２出力データ群の中からバンクの連続順序に従って出力データを２つ選択し、選択した２つの出力データをバンクの連続順序に従いバンクに格納させる。これにより、出力ストリームが複数であっても、バンクアクセスについてはシーケンシャルとなるため、バンク衝突の回数を減らすことができる。
【０１６６】
また、データ処理装置１００は、出力ストリームが２つの場合に、各バッファに格納された先頭のデータと２番目のデータとから２つの出力データを選択可能な選択部を設ける。これにより、簡単な制御によって出力データの書き込みアクセスについてシーケンシャルにすることができる。
【０１６７】
また、入力ストリームが２つの場合に、第１入力データ群の各々は、０からＮ／２−１番目の入力データであり、第２入力データ群の各々は、Ｎ／２からＮ−１番目の入力データである。これにより、入力ストリームが複数であっても、出力ストリームのバンクアクセスについてはシーケンシャルとなるため、バンク衝突の回数を減らすことができる。
【０１６８】
なお、本実施の形態で説明したデータ処理方法は、データ処理装置が各部の処理を実行することによって実現することができる。
【０１６９】
また、本実施の形態で説明したデータ処理装置１００は、スタンダードセルやストラクチャードＡＳＩＣなどのＡＳＩＣやＦＰＧＡなどのＰＬＤによっても実現することができる。具体的には、例えば、上述したデータ処理装置の機能をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、データ処理装置を製造することができる。
【０１７０】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１７１】
（付記１）連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリへのアクセスを制御する制御部と、
前記制御部のアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群を前記データメモリから読み出して格納し、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に前記入力データ群を入力する入力バッファと、
前記入力データ群と同一長であって前記演算部の出力端子から出力される出力データ群を格納し、前記制御部を介して前記出力データ群を前記データメモリに出力する出力バッファと、
を有し、
前記制御部は、
前記複数のバンクに割り当てられた前記アドレスの連続順序に従って前記データメモリからの前記入力データ群の読み出しを行う場合に、前記複数のステージのうちの特定のステージにおいて、前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従うように前記出力データ群の中から出力対象となる出力データを選択し、前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なるバンクに、選択した前記出力データを前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とするデータ処理装置。
【０１７２】
（付記２）前記制御部は、
前記出力データ群の中から前記異なるバンクに格納される出力データのうち前記出力バッファに格納された順序が早い順に出力対象となる前記出力データを選択する、
ことを特徴とする付記１に記載のデータ処理装置。
【０１７３】
（付記３）前記出力バッファは、前記演算部の第１出力端子から出力される前記出力データ群に含まれる第１出力データ群を格納し、前記制御部を介して前記第１出力データ群を前記データメモリに出力する第１出力バッファと、前記演算部の第２出力端子から出力される前記出力データ群に含まれ前記第１出力データ群と異なる第２出力データ群を格納し、前記制御部を介して前記第２出力データ群を前記データメモリに出力する第２出力バッファと、を有し、
前記制御部は、
前記複数のバンクの連続順序に従うように、前記第１出力バッファに格納された前記第１出力データ群と前記第２出力バッファに格納された前記第２出力データ群との中から出力対象となる２つの前記出力データを選択し、前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なる２つのバンクに選択した２つの前記出力データをそれぞれ前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とする付記１または付記２のいずれか一つに記載のデータ処理装置。
【０１７４】
（付記４）前記第１出力データ群のうち前記第１出力バッファに格納された順序が最も早い第１出力データと、前記第１出力データ群のうち前記第１出力バッファに格納された順序が２番目に早い第１出力データと、前記第２出力データ群のうち前記第２出力バッファに格納された順序が最も早い第２出力データと、前記第２出力データ群のうち前記第２出力バッファに格納された順序が２番目に早い第２出力データと、の中から、出力対象となる２つの前記出力データを選択する選択部を有し、
前記制御部は、
前記複数のバンクの連続順序に従う出力対象となる２つの前記出力データを前記選択部に選択させる制御を行い、前記２つのバンクに、前記選択部によって選択された２つの前記出力データをそれぞれ前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とする付記３に記載のデータ処理装置。
【０１７５】
（付記５）前記入力バッファは、前記制御部によって前記データメモリから読み出された前記入力データ群に含まれてポイント数がＮの前記フーリエ変換を行う場合に各々が０から（Ｎ／２−１）番目の入力である第１入力データ群を格納し、前記演算部の第１入力端子に前記第１入力データ群を入力する第１入力バッファと、前記制御部によって前記データメモリから読み出された前記入力データ群に含まれ前記第１入力データ群と異なり、前Ｎの前記フーリエ変換を行う場合に各々がＮ／２から（Ｎ−１）番目の入力データである第２入力データ群を格納し、前記演算部の第２入力端子に前記第２入力データ群を入力する第２入力バッファと、を有する、
ことを特徴とする付記１〜４のいずれか一つに記載のデータ処理装置。
【０１７６】
（付記６）前記複数のバンクの数は４以上であることを特徴とする付記５に記載のデータ処理装置。
【０１７７】
（付記７）前記制御部は、
前記特定のステージにおける複数のサイクルのうちの第１特定サイクルにおいて、最も早い前記第１出力データと最も早い前記第２出力データとの組み合わせを前記選択部に選択させ、前記複数のサイクルのうちの第２特定サイクルにおいて、最も早い前記第１出力データと２番目に早い前記第２出力データとの組み合わせと、２番目に早い前記第１出力データと最も早い前記第２出力データとの組み合わせと、のうちのいずれかを前記選択部に選択させる制御を行う、
ことを特徴とする付記４に記載のデータ処理装置。
【０１７８】
（付記８）前記制御部は、
前記特定のステージにおける複数のサイクルのうちの第１特定サイクルにおいて、最も早い前記第１出力データと２番目に早い前記第１出力データとの組み合わせと、最も早い前記第２出力データと２番目に早い前記第２出力データとの組み合わせと、のうちのいずれかを前記選択部に選択させ、前記複数のサイクルのうちの第２特定サイクルにおいて、最も早い前記第１出力データと２番目に早い前記第２出力データとの組み合わせと、最も早い前記第２出力データと２番目に早い前記第１出力データとの組み合わせと、のうちのいずれかを前記選択部に選択させ、前記複数のサイクルのうちの第３特定サイクルにおいて、最も早い前記第１出力データと最も早い前記第２出力データを前記選択部に選択させる制御を行う、
ことを特徴とする付記４に記載のデータ処理装置。
【０１７９】
（付記９）連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリへのアクセスを制御する制御部と、
前記制御部のアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群を前記データメモリから読み出して格納し、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に前記入力データ群を入力する入力バッファと、
前記入力データ群と同一長であって前記演算部の出力端子から出力される出力データ群を格納し、前記制御部を介して前記出力データ群を前記データメモリに出力する出力バッファと、
を有し、
前記制御部は、
前記複数のバンクに割り当てられた前記アドレスの連続順序に従って前記データメモリからの前記出力データ群の出力を行う場合に、前記複数のステージのうちの特定のステージにおいて、前記複数のバンクのうち前記出力データ群の出力対象であるバンクとは異なるバンクから、前記入力データ群に含まれる入力データを前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従って読み出す制御を行う、
ことを特徴とするデータ処理装置。
【０１８０】
（付記１０）コンピュータが、
連続したアドレスが交互に割り振られた複数のバンクを有するデータメモリのアクセス対象である前記複数のバンクにおける各々のライン長と同一長の入力データ群であって、入力されたデータに対して複数のステージに分割されたフーリエ変換のバタフライ演算を行う演算部の入力端子に入力される入力データ群の前記データメモリからの読み出しを、前記複数のバンクに割り当てられたアドレスの連続順序に従う場合に、
複数のステージのうちの特定のステージにおいて、前記アドレスの連続順序に応じた順序で連続する前記複数のバンクの連続順序に従うように前記出力データ群の中から出力対象となる出力データを選択し、
前記複数のバンクのうち前記入力データ群の読み出し対象であるバンクとは異なるバンクに選択した前記出力データを前記複数のバンクの連続順序に従って格納させる制御を行う、
ことを特徴とするデータ処理方法。
【符号の説明】
【０１８１】
１００  データ処理装置
１０１  データメモリ
１１０−０〜１１０−３  バンク
１２０−Ａ，１２０−Ｂ  入力バッファ
１２１−Ｆ，１２１−Ｅ  出力バッファ
１２２  制御部
３０１  演算部
３０２  選択部
４１１  演算データパス
４１２  ＦＩＦＯ
４２１−Ａ，４２１−Ｂ  入力ＦＩＦＯ
４２２−Ｆ，４２２−Ｅ  出力ＦＩＦＯ
４２３−Ｆ，４２３−Ｅ  マルチプレクサ
４３１−Ａ〜４３１−Ｅ  ＤＭＡ
４３２  ＦＦＴ命令制御回路
４３３  調停回路
５００  複素積和演算器
【図１】
2017010325.tif 000003
【図２】
2017010325.tif 000004
【図３】
2017010325.tif 000005
【図４】
2017010325.tif 000006
【図５】
2017010325.tif 000007
【図６】
2017010325.tif 000008
【図７】
2017010325.tif 000009
【図８】
2017010325.tif 000010
【図９】
2017010325.tif 000011
【図１０】
2017010325.tif 000012
【図１１Ａ】
2017010325.tif 000013
【図１１Ｂ】
2017010325.tif 000014
【図１１Ｃ】
2017010325.tif 000015
【図１１Ｄ】
2017010325.tif 000016
【図１１Ｅ】
2017010325.tif 000017
【図１１Ｆ】
2017010325.tif 000018
【図１２Ａ】
2017010325.tif 000019
【図１２Ｂ】
2017010325.tif 000020
【図１２Ｃ】
2017010325.tif 000021
【図１２Ｄ】
2017010325.tif 000022
【図１２Ｅ】
2017010325.tif 000023
【図１２Ｆ】
2017010325.tif 000024
【図１３Ａ】
2017010325.tif 000025
【図１３Ｂ】
2017010325.tif 000026
【図１３Ｃ】
2017010325.tif 000027
【図１３Ｄ】
2017010325.tif 000028
【図１３Ｅ】
2017010325.tif 000029
【図１３Ｆ】
2017010325.tif 000030
【図１４】
2017010325.tif 000031
【図１５】
2017010325.tif 000032
【図１６】
2017010325.tif 000033
【図１７】
2017010325.tif 000034
【図１８】
2017010325.tif 000035
【図１９】
2017010325.tif 000036
【図２０】
2017010325.tif 000037
【図２１】
2017010325.tif 000038
【図２２】
2017010325.tif 000039
【図２３】
2017010325.tif 000040