(57)【要約】  本発明は、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくし、全体としての処理能力を向上させることを目的とし、行列状に配置された複数の処理部は、拡張識別情報に応じてパケットの宛先情報を算出する宛先情報算出部と、パケットのうち、宛先情報が当該処理部を示すパケットのみを取得し、宛先情報が当該処理部を示さないパケットを、宛先情報が示す処理部に近づく方向に隣接する処理部に転送する入出力部と、入出力部によって取得されたパケットの処理命令を実行する演算部と、をそれぞれ有し、宛先情報算出部は、拡張識別情報のうち、少なくとも識別情報の一部を含む第１の部分のビット列に基づいて、複数の処理部全体を分割した何れかの区画を示す第１の宛先情報を算出するとともに、少なくとも第１の部分以外の部分を含む第２の部分のビット列に基づいて、第１の宛先情報が示す区画内の処理部の位置を示す第２の宛先情報を算出する。
2013141290.tif 000002
【特許請求の範囲】
【請求項１】
行列状に配置され、データごとに、当該データを識別する識別情報および当該データに対する１つ以上の処理命令を示す命令情報を含む拡張識別情報が付加されたパケットを処理する複数の処理部を備え、
前記複数の処理部は、
前記拡張識別情報に応じて前記パケットの宛先情報を算出する宛先情報算出部と、
前記パケットのうち、前記宛先情報が当該処理部を示すパケットのみを取得し、前記宛先情報が当該処理部を示さないパケットを、前記宛先情報が示す処理部に近づく方向に隣接する処理部に転送する入出力部と、
前記入出力部によって取得された前記パケットの前記処理命令を実行する演算部と、
をそれぞれ有し、
前記宛先情報算出部は、
前記拡張識別情報のうち、少なくとも前記識別情報の一部を含む第１の部分のビット列に基づいて、前記複数の処理部全体を分割した複数の処理部群の何れかを示す第１の宛先情報を算出するとともに、
前記拡張識別情報のうち、少なくとも前記第１の部分以外の部分を含む第２の部分のビット列に基づいて、前記複数の処理部群のうち前記第１の宛先情報が示す処理部群に含まれる何れかの処理部を示す第２の宛先情報を算出することを特徴とするデータ処理装置。
【請求項２】
前記宛先情報算出部は、
前記第１の部分のビット列から生成される擬似乱数に応じて前記第１の宛先情報を算出するとともに、
前記第２の部分のビット列から生成される擬似乱数に応じて前記第２の宛先情報を算出することを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記識別情報は、ループ処理におけるループの繰り返しごとに設定される識別番号であるループＩＤを含み、
前記演算部は、前記入出力部によって取得された前記パケットの前記処理命令のうち最初に実行されるべき処理命令を実行し、当該実行によって生成されるデータに、実行された前記処理命令の次に実行されるべき処理命令を最初に実行されるべき処理命令とする前記拡張識別情報が付加されたパケットを生成して前記入出力部に入力し、
前記複数の処理部は、
前記入出力部によって取得された前記パケットの最初に実行されるべき処理命令が、前記ループＩＤが異なる複数のパケットからなるパケット群を生成する処理命令である場合に、前記パケット群を生成するためのテンプレート情報が登録されるテンプレート記憶部と、
前記テンプレート記憶部に登録されている前記テンプレート情報に基づいて前記パケット群を生成して前記入出力部に入力するパケット生成部と、
をそれぞれさらに有することを特徴とする請求項１または請求項２に記載のデータ処理装置。
【請求項４】
前記パケット群を生成する処理命令は、前記ループＩＤのみが異なる複数のパケットからなる前記パケット群を生成するリピート命令を含み、
前記入出力部によって取得された２つのパケットの最初に実行されるべき処理命令が前記リピート命令である場合には、前記テンプレート記憶部に登録される前記テンプレート情報は、当該取得された２つのパケットのうちの一方のパケットにおいて前記リピート命令を除いたテンプレートパケットと、当該取得された２つのパケットのうちの他方のパケットの前記データに応じた前記パケット群の生成条件とを含み、
前記パケット生成部は、前記生成条件に基づいて前記テンプレートパケットの前記ループＩＤを変化させた複数のパケットからなる前記パケット群を生成することを特徴とする請求項３に記載のデータ処理装置。
【請求項５】
前記入出力部によって取得された２つのパケットの最初に実行されるべき処理命令が前記リピート命令である場合には、前記生成条件は、生成される前記パケット群に含まれるパケットの個数を示す全生成数と、前記ループＩＤの増分を示すループＩＤピッチとを含み、
前記パケット生成部は、前記テンプレートパケットの前記ループＩＤを前記ループＩＤピッチずつ順次増加させた、前記全生成数が示す個数のパケットからなる前記パケット群を生成することを特徴とする請求項４に記載のデータ処理装置。
【請求項６】
前記パケットの前記命令情報は、前記処理命令として前記リピート命令が格納されている場合には、当該リピート命令に隣接して整数データが格納され、
前記演算部は、前記入出力部によって取得された２つのパケットの最初に実行されるべき処理命令が前記リピート命令である場合には、当該取得された２つのパケットのうちの前記他方のパケットにおいて前記整数データをダウンカウントしたパケットを生成し、
前記宛先情報算出部は、前記パケットの最初に実行されるべき処理命令が前記リピート命令である場合には、前記リピート命令および前記整数データのみを前記命令情報に格納した前記拡張識別情報のうち、
少なくとも前記識別情報の一部を含む前記第１の部分のビット列に基づいて前記第１の宛先情報を算出するとともに、
少なくとも前記第１の部分以外の部分を含む前記第２の部分のビット列に基づいて前記第２の宛先情報を算出することを特徴とする請求項４または請求項５に記載のデータ処理装置。
【請求項７】
前記パケット群を生成する処理命令は、前記ループ処理におけるループ内で使用するループ変数を前記データとする複数のパケットからなる前記パケット群を生成するステップ命令を含み、
前記入出力部によって取得された２つのパケットの最初に実行されるべき処理命令が前記ステップ命令である場合には、前記テンプレート記憶部に登録される前記テンプレート情報は、当該取得された２つのパケットのうちの一方のパケットにおいて前記ループ変数の初期値を前記データとし、前記ステップ命令を除いたテンプレートパケットと、当該取得された２つのパケットの前記データに応じた前記パケット群の生成条件とを含み、
前記パケット生成部は、前記生成条件に基づいて前記テンプレートパケットの前記ループＩＤおよび前記データを変化させた複数のパケットからなる前記パケット群を生成することを特徴とする請求項３に記載のデータ処理装置。
【請求項８】
前記入出力部によって取得された２つのパケットの最初に実行されるべき処理命令が前記ステップ命令である場合には、前記生成条件は、生成される前記パケット群に含まれるパケットの個数を示す全生成数と、前記ループＩＤの増分を示すループＩＤピッチと、前記ループ変数の増分を示すステップピッチとを含み、
前記パケット生成部は、前記テンプレートパケットの前記ループＩＤを前記ループＩＤピッチずつ順次増加させ、前記データを前記ループ変数の初期値から前記ステップピッチずつ順次増加させた、前記全生成数が示す個数のパケットからなる前記パケット群を生成することを特徴とする請求項７に記載のデータ処理装置。
【請求項９】
前記パケットを前記複数の処理部の何れかに発行する制御部をさらに備えることを特徴とする請求項１ないし請求項８の何れかに記載のデータ処理装置。
【請求項１０】
請求項９に記載のデータ処理装置と、
前記制御部によって前記パケットに変換されるプログラム、前記パケットのうち前記識別情報の少なくとも一部が前記制御部によって付加される中間パケット、または前記パケットが記憶されている記憶装置と、
前記データを含み、前記プログラム、前記中間パケット、または前記パケットをさらに含む情報を入出力する入出力装置と、
を備えることを特徴とするデータ処理システム。
【請求項１１】
行列状に配置された複数の処理部を備えるデータ処理装置によって処理される複数のパケットのデータ構造であって、
前記複数のパケットは、データごとに、当該データを識別する識別情報および当該データに対する１つ以上の処理命令を示す命令情報を含む拡張識別情報を付加して構成され、
前記識別情報は、ループ処理におけるループの繰り返しごとに設定される識別番号であるループＩＤを含み、
前記複数のパケットの前記処理命令は、前記ループＩＤのみが異なる複数のパケットからなるパケット群を生成するリピート命令を含み、
前記複数の処理部は、それぞれ、
前記拡張識別情報のうち、少なくとも前記識別情報の一部を含む第１の部分のビット列に基づいて、前記複数の処理部全体を分割した複数の処理部群の何れかを示す第１の宛先情報を算出し、
前記拡張識別情報のうち、少なくとも前記第１の部分以外の部分を含む第２の部分のビット列に基づいて、前記複数の処理部群のうち前記第１の宛先情報が示す処理部群に含まれる何れかの処理部を示す第２の宛先情報を算出し、
前記複数のパケットのうち、前記第１および第２の宛先情報が当該処理部を示すパケットのみを取得し、当該パケットの前記処理命令を実行し、
前記リピート命令を実行する場合には、最初に実行されるべき処理命令が前記リピート命令である２つのパケットのうちの一方のパケットにおいて前記リピート命令を除いたテンプレートパケットと、生成される前記パケット群に含まれるパケットの個数を示す全生成数と、前記ループＩＤの増分を示すループＩＤピッチとを登録し、
前記処理命令の実行とは独立して、前記テンプレートパケットの前記ループＩＤを前記ループＩＤピッチずつ順次増加させた、前記全生成数が示す個数のパケットからなる前記パケット群を生成することを特徴とするデータ構造。
【請求項１２】
行列状に配置された複数の処理部を備えるデータ処理装置によって処理される複数のパケットのデータ構造であって、
前記複数のパケットは、データごとに、当該データを識別する識別情報および当該データに対する１つ以上の処理命令を示す命令情報を含む拡張識別情報を付加して構成され、
前記識別情報は、ループ処理におけるループの繰り返しごとに設定される識別番号であるループＩＤを含み、
前記複数のパケットの前記処理命令は、前記ループ処理におけるループ内で使用するループ変数を前記データとする複数のパケットからなるパケット群を生成するステップ命令を含み、
前記複数の処理部は、それぞれ、
前記拡張識別情報のうち、少なくとも前記識別情報の一部を含む第１の部分のビット列に基づいて、前記複数の処理部全体を分割した複数の処理部群の何れかを示す第１の宛先情報を算出し、
前記拡張識別情報のうち、少なくとも前記第１の部分以外の部分を含む第２の部分のビット列に基づいて、前記複数の処理部群のうち前記第１の宛先情報が示す処理部群に含まれる何れかの処理部を示す第２の宛先情報を算出し、
前記複数のパケットのうち、前記第１および第２の宛先情報が当該処理部を示すパケットのみを取得し、当該パケットの前記処理命令を実行し、
前記ステップ命令を実行する場合には、最初に実行されるべき処理命令が前記ステップ命令である２つのパケットのうちの一方のパケットにおいて前記ループ変数の初期値を前記データとし、前記ステップ命令を除いたテンプレートパケットと、生成される前記パケット群に含まれるパケットの個数を示す全生成数と、前記ループＩＤの増分を示すループＩＤピッチと、前記ループ変数の増分を示すステップピッチとを登録し、
前記処理命令の実行とは独立して、前記テンプレートパケットの前記ループＩＤを前記ループＩＤピッチずつ順次増加させ、前記データを前記ループ変数の初期値から前記ステップピッチずつ順次増加させた、前記全生成数が示す個数のパケットからなる前記パケット群を生成することを特徴とするデータ構造。
【請求項１３】
請求項１１または請求項１２に記載のデータ構造を有するパケットが記録された記録媒体。
【請求項１４】
請求項１１または請求項１２に記載のデータ構造のうち、前記識別情報の少なくとも一部が前記データ処理装置の制御部によって付加される中間パケットが記録された記録媒体。
【請求項１５】
請求項１１または請求項１２に記載のデータ構造を有するパケットが記憶されている記憶装置。
【請求項１６】
請求項１１または請求項１２に記載のデータ構造のうち、前記識別情報の少なくとも一部が前記データ処理装置の制御部によって付加される中間パケットが記憶されている記憶装置。
【請求項１７】
請求項１５または請求項１６に記載の記憶装置と、
前記データ処理装置と、
前記データを含む情報を入出力する入出力装置と、
を備えることを特徴とするデータ処理システム。
【請求項１８】
データごとに、当該データを識別する識別情報および当該データに対する１つ以上の処理命令を示す命令情報を含む拡張識別情報が付加されたパケットを処理するデータ処理方法であって、
行列状に配置された複数の処理部が、それぞれ、
前記拡張識別情報のうち、少なくとも前記識別情報の一部を含む第１の部分のビット列に基づいて、前記複数の処理部全体を分割した複数の処理部群の何れかを示す第１の宛先情報を算出し、
前記拡張識別情報のうち、少なくとも前記第１の部分以外の部分を含む第２の部分のビット列に基づいて、前記複数の処理部群のうち前記第１の宛先情報が示す処理部群に含まれる何れかの処理部を示す第２の宛先情報を算出し、
前記パケットのうち、前記第１および第２の宛先情報が当該処理部を示すパケットのみを取得し、当該パケットの前記処理命令を実行し、
前記パケットのうち、前記第１および第２の宛先情報が当該処理部を示さないパケットを、前記第１および第２の宛先情報が示す処理部に近づく方向に隣接する処理部に転送することを特徴とするデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ処理システム、データ構造、記録媒体、記憶装置、およびデータ処理方法に関する。
【背景技術】
【０００２】
コンピュータアーキテクチャとして、記憶装置（メモリ）から命令を順次読み出して（fetch）、解読し（decode）、実行する（execute）、ノイマン型アーキテクチャが一般に知られている。当該ノイマン型アーキテクチャは、命令の実行順序を予め定め、オペランド（演算対象のデータ）をその都度集めながら処理を行う、命令中心の処理体系となっている。【０００３】
また、ノイマン型コンピュータにおいて、複数の命令を並列処理するＣＰＵ（Central Processing Unit：中央処理装置）アーキテクチャとして、スーパースカラ・プロセッサが知られている。当該スーパースカラ・プロセッサは、オペランドの到着順に、実行ノードに対して命令を発行し（issue）、実行する、アウト・オブ・オーダ処理が可能となっている。しかしながら、スーパースカラ・プロセッサにおいては、スケジューラがデータ依存性を検査しながら実行結果を正しい順序に並べ替えるため、同時に実行可能な命令数の増加は、スケジューラの複雑化を招くこととなる。【０００４】
本出願人は、このようなノイマン型コンピュータの問題を解決するため、新しいデータ駆動型アーキテクチャに基づく並列コンピュータ（以下、新データ駆動型コンピュータと称する）を提案している（特許文献１および特許文献２を参照）。当該新データ駆動型コンピュータは、オペランドとなるデータとオペレータ（演算子）となる命令とが一体となったパケットを処理対象としており、各パケットに含まれる命令は、そのパケットのビット列自体によって決定される宛先のＰＥ（Processor/Processing Element：処理要素／処理素子）で実行される。したがって、複数の命令を含むパケットは、現在のＰＥで１つの命令が実行されると、実行後のビット列によって決定される次のＰＥ（現在のＰＥを含む）に移動し、順次ＰＥ間を移動しながら命令が実行される。【０００５】
このようにして、新データ駆動型コンピュータでは、処理対象のパケットをそのビット列自体に基づいて動的に配置し、汎用性と高速性との両立を図っている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１１−１３８４７９号公報
【特許文献２】国際公開第２０１１／０６８０１８号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１の新データ駆動型コンピュータ（データ処理装置）では、タイルプロセッサと同様に、ＰＥを行列状に配置し、隣接するＰＥ間のみを互いに接続することによって、配線遅延の問題を回避していた。しかしながら、このような行列状の配置および接続では、パケットが常に最短の経路を移動する場合であっても、全体のＰＥ数が増加するほど、各パケットの平均移動距離（経由する平均ＰＥ数）が増加することとなる。したがって、各パケットにとっては、処理時間全体に占める移動時間の割合が増加し、各ＰＥにとっては、取得して処理するパケットに対して隣接するＰＥに転送するパケットの割合が増加し、オーバーヘッドが大きくなってしまう。そのため、ＰＥ数を増加させても、それに見合う装置全体の処理能力の向上を図ることができない。【０００８】
また、特許文献１では、各ＰＥが入出力ポートごとに複数のチャネルを備える構成も提案されており、上記のオーバーヘッドは、このように各ＰＥが備える入出力チャネル数を増加させることによって、小さくすることができる。しかしながら、この方法では、装置全体に占める各ＰＥの入出力部やＰＥ間の通信路の回路規模（ゲート数）が大きくなり、装置に実装可能なＰＥ数が制限されることとなる。そのため、ＰＥ数を増加させて処理能力の向上を図る目的には適さない。
【課題を解決するための手段】
【０００９】
前述した課題を解決する主たる本発明は、行列状に配置され、データごとに、当該データを識別する識別情報および当該データに対する１つ以上の処理命令を示す命令情報を含む拡張識別情報が付加されたパケットを処理する複数の処理部を備え、前記複数の処理部は、前記拡張識別情報に応じて前記パケットの宛先情報を算出する宛先情報算出部と、前記パケットのうち、前記宛先情報が当該処理部を示すパケットのみを取得し、前記宛先情報が当該処理部を示さないパケットを、前記宛先情報が示す処理部に近づく方向に隣接する処理部に転送する入出力部と、前記入出力部によって取得された前記パケットの前記処理命令を実行する演算部と、をそれぞれ有し、前記宛先情報算出部は、前記拡張識別情報のうち、少なくとも前記識別情報の一部を含む第１の部分のビット列に基づいて、前記複数の処理部全体を分割した複数の処理部群の何れかを示す第１の宛先情報を算出するとともに、前記拡張識別情報のうち、少なくとも前記第１の部分以外の部分を含む第２の部分のビット列に基づいて、前記複数の処理部群のうち前記第１の宛先情報が示す処理部群に含まれる何れかの処理部を示す第２の宛先情報を算出することを特徴とするデータ処理装置である。【００１０】
本発明の他の特徴については、添付図面及び本明細書の記載により明らかとなる。【００１１】
＜関連出願の相互参照＞
この出願は、２０１２年３月２３日に出願された日本特許出願第２０１２−６７８５４号に基づく優先権を主張し、その内容を本願に援用する。
【発明の効果】
【００１２】
本発明によれば、新データ駆動型コンピュータにおいて、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくし、全体としての処理能力を向上させることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態におけるＰＥ（処理要素）の構成を示すブロック図である。
【図２】データ処理装置を備えたデータ処理システム全体の構成の概略を示すブロック図である。
【図３】本発明の一実施形態におけるデータ処理装置の構成を示すブロック図である。
【図４】ソースプログラムとデータ処理装置で処理されるプログラム（実行コード）との関係の一例を示す図である。
【図５】データ処理装置で用いられる命令セットの一例を示す図である。
【図６】ＭＣＥ（メモリ制御要素）によって生成されるデータフロー図の一例を示す図である。
【図７】ＭＣＥ（メモリ制御要素）によって生成される初期パケット列の一例を示す図である。
【図８】ソースプログラムとデータ処理装置で処理されるプログラム（実行コード）との関係の他の例を示す図である。
【図９】本発明の一実施形態における宛先情報の算出方法を説明する図である。
【図１０】宛先情報と各ＰＥ（処理要素）との対応関係を示す図である。
【図１１】バッファメモリに実装されるハッシュテーブルの一例を示す図である。
【図１２】パック（梱包）命令の実行によるデータ処理装置の動作を説明する図である。
【図１３】リピート（繰り返し）命令の実行によるデータ処理装置の動作を説明する図である。
【図１４】リピート（繰り返し）命令の実行によるデータ処理装置の他の動作を説明する図である。
【図１５】テンプレートバッファに登録されるテンプレート情報の一例を示す図である。
【図１６】リピート（繰り返し）命令に従って登録されたテンプレート情報に基づいて生成されるパケット群の一例を示す図である。
【図１７】ステップ（段階）命令の実行によるデータ処理装置の動作を説明する図である。
【図１８】ステップ（段階）命令に従って登録されたテンプレート情報に基づいて生成されるパケット群の一例を示す図である。
【図１９】デュプリケート（複製）命令の実行によるデータ処理装置の動作を説明する図である。
【図２０】図７に示した初期パケット列から、ループ関連命令の実行によって生成されるパケット群を示す図である。
【図２１】特許文献１のデータ処理装置において、ＭＣＥ（メモリ制御要素）によって生成される展開後のパケット列の一例を示す図である。
【発明を実施するための形態】
【００１４】
本明細書および添付図面の記載により、少なくとも以下の事項が明らかとなる。
【００１５】
＝＝＝データ処理システム全体の構成の概略＝＝＝
以下、図２を参照して、データ処理装置を備えたデータ処理システム全体の構成の概略について説明する。
【００１６】
図２に示されているデータ処理システムは、データ処理装置１を備えた並列コンピュータシステムであり、データ処理装置１以外に、記憶装置６、入力装置７、出力装置８、およびバス９を含んで構成されている。また、データ処理装置１、記憶装置６、入力装置７、および出力装置８は、バス９を介して互いに接続されている。なお、データ処理装置１の構成についての詳細な説明は後述する。
【００１７】
＝＝＝データ処理システム全体の動作の概略＝＝＝
次に、データ処理システム全体の動作の概略について説明する。
【００１８】
記憶装置６は、ＲＡＭ（Random Access Memory）やＲＯＭ（Read Only Memory）などで構成され、プログラム（実行コード）や当該プログラムの実行に用いられるデータなどを記憶している。また、データ処理装置１は、コンピュータシステムのＣＰＵに相当し、記憶装置６に記憶されているプログラムを実行する。なお、データ処理装置１の動作についての詳細な説明は後述する。
【００１９】
入力装置７は、キーボードやマウスなどで構成され、データやプログラム（ソースプログラムまたは実行コード）を含む情報を外部から当該データ処理システムに入力する。一方、出力装置８は、ディスプレイやプリンタなどで構成され、情報を文字や画像などとして外部に出力する。
【００２０】
なお、上記データ処理装置１、記憶装置６、入力装置７、および出力装置８の分類は、固定的なものではない。例えば、ハードディスクドライブや光ディスクドライブなどの補助記憶装置は、記憶装置６として用いられるが、外部との間で情報を入出力する入力装置７および出力装置８に分類してもよい。
【００２１】
＝＝＝データ処理装置の構成＝＝＝
以下、図３を参照して、本発明の一実施形態におけるデータ処理装置の構成について説明する。
【００２２】
図３に示されているデータ処理装置１は、ＰＥ１００ないし１６３、ＭＣＥ（Memory Control/Controlling Element：メモリ制御要素／メモリ制御素子）３００、キャッシュメモリ４００、および通信路（伝送路）５００を含んで構成されている。
【００２３】
データ処理装置１は、処理部に相当するＰＥを複数備え、各ＰＥが通信路５００を介して互いに接続されている。本実施形態では、一例として、データ処理装置１は、８行８列の行列状に配置された６４個のＰＥ１００ないし１６３を備えているものとする。また、ＰＥ１００ないし１６３は、隣接するＰＥ間のみが互いに接続されているものとする。なお、各ＰＥの構成についての詳細な説明は後述する。
【００２４】
ここで、ＰＥ１００ないし１６３の座標（Ｘ，Ｙ）を、図３に示すように、それぞれ（０，０）ないし（７，７）と表すこととすると、各ＰＥに対して、Ｘ座標を上位３ビット、Ｙ座標を下位３ビットとする識別番号を設定することができる。また、このように設定された識別番号は、図３に示されている各ＰＥの３桁の符号の下２桁と一致している。例えば、座標（０，７）に位置するＰＥ１０７の識別番号は、７（２進表記で０００１１１）となり、座標（７，０）に位置するＰＥ１５６の識別番号は、５６（２進表記で１１１０００）となる。
【００２５】
データ処理装置１は、制御部に相当するＭＣＥを少なくとも１つ備え、各ＭＣＥが通信路５００を介してＰＥ１００ないし１６３の何れかと接続されている。本実施形態では、一例として、データ処理装置１は、１個のＭＣＥ３００のみを備えているものとする。また、図３に示すように、ＭＣＥ３００は、隣接するＰＥ１００ないし１０７と接続されているものとする。
【００２６】
キャッシュメモリ４００は、ＭＣＥ３００と接続されている。また、キャッシュメモリ４００は、前述したバス９を介して、データ処理装置１外の記憶装置６（不図示）と接続されている。
【００２７】
＝＝＝データ処理装置の動作＝＝＝
次に、図４ないし図８を適宜参照して、本実施形態におけるデータ処理装置の動作について説明する。
【００２８】
キャッシュメモリ４００は、キャッシュを行いつつ、ＭＣＥ３００と記憶装置６との間の入出力を制御する。したがって、記憶装置６に記憶されているプログラムやデータなどは、キャッシュメモリ４００を介してＭＣＥ３００に読み込まれる。
【００２９】
ここで、ソースプログラムとデータ処理装置１で処理されるプログラム（実行コード）との関係の一例を図４に示す。高級言語で記述されたソースプログラムＰＲ０は、実行コードＰＲ１に予めコンパイルされたうえで記憶装置６に記憶されており、ＭＣＥ３００には、実行コードＰＲ１が読み込まれる。なお、図４においては、ソースプログラムＰＲ０の一例として、Ｃ＋＋言語で記述された、配列ｓｐ［１０２４］の各要素を２で除算した値を配列ｄｐ［１０２４］に格納する処理が示されている。また、実行コードＰＲ１は、機械語プログラムではなく、機械語と略１対１に対応するアセンブリ言語で記述されたプログラムとしてもよい。
【００３０】
ＭＣＥ３００は、読み込まれた実行コードＰＲ１から、データフロー図に基づいて、後述する初期パケット列を生成する。なお、ＭＣＥ３００は、データフロー図自体を生成する必要はないが、本実施形態においては、説明の便宜上、まずデータフロー図を生成し、次にデータフロー図に基づいて初期パケット列を生成するものとする。
【００３１】
ここで、データ処理装置１で用いられる命令セットの一例を図５に示す。図５において、各命令は、２入力・１出力命令、１入力・１出力命令、およびループ関連命令に大別されている。これらのうち、２入力・１出力命令は、入力された２つのデータをそれぞれ左側および右側オペランドとして２項演算を行う命令であり、１入力・１出力命令は、入力された１つのデータをオペランドとして単項演算を行う命令である。一方、ループ関連命令は、ループ処理を各ＰＥにおいて展開するため、本実施形態のデータ処理装置に対して追加された命令である。
【００３２】
また、図５に示すように、各命令に対して、オペレータ（演算子）に相当する記号と機械語における１６進表記とが設定されており、これらはデータフロー図やパケット列についての説明で適宜用いられる。本実施形態では、各命令は、例えば８ビットの固定長となっている。
【００３３】
まず、２入力・１出力命令について説明する。
【００３４】
２つのデータ（ＡおよびＢ）の加算結果（Ａ＋Ｂ）を出力する加算命令に対しては、記号「＋」と１６進表記１０Ｈとが設定されている。また、２つのデータ（ＡおよびＢ）の乗算結果（Ａ×Ｂ）を出力する乗算命令に対しては、記号「×」と１６進表記１４Ｈとが設定されている。
【００３５】
２つのデータ（ＬおよびＲ）の減算結果（Ｌ−Ｒ）を出力する減算命令の場合、減算は交換法則が成立しない非可換演算であるため、各データを左側または右側オペランドの何れとするかを示す左右情報（方向情報）を必要とする。そのため、減算命令に対する記号「−」には、さらに左右情報「Ｌ」または「Ｒ」が付加され、それぞれ１６進表記１２Ｈまたは１３Ｈが設定されている。また、２つのデータ（ＬおよびＲ）の除算結果（Ｌ／Ｒ）を出力する除算命令に対しては、左右情報が付加された記号「／」（「／Ｌ」および「／Ｒ」）と、１６進表記１６Ｈおよび１７Ｈとが設定されている。
【００３６】
なお、左右情報「Ｌ」は、左側オペランドとなるデータを示し、左右情報「Ｒ」は、右側オペランドとなるデータを示している。また、当該命令セットにおいては、各命令のＬＳＢ（Least Significant Bit：最下位ビット）が左右情報専用に割り当てられている。したがって、以下の命令（ヌル文字を除く）においても、左右情報「Ｌ」を有する命令および左右情報を有しない命令のＬＳＢは０、左右情報「Ｒ」を有する命令のＬＳＢは１となっている。そのため、交換法則が成立する可換演算を行う加算命令や乗算命令などに対しても、容易に左右情報を付加することができる。
【００３７】
左右情報が付加された記号「ｗｒｉｔｅ」（「ｗｒｉｔｅＬ」および「ｗｒｉｔｅＲ」）と、１６進表記１８Ｈおよび１９Ｈとが設定されている書き込み命令は、データ（Ｌ）が示す記憶装置６のアドレスに記憶されているデータ（＊Ｌ）にデータ（Ｒ）を書き込む命令である。なお、「＊」は間接参照演算子である。
【００３８】
左右情報が付加された記号「Ｄａｐ」（「ＤａｐＬ」および「ＤａｐＲ」）と、１６進表記５０Ｈおよび５１Ｈとが設定されているデータ追加命令は、後述するパケット（Ｌ）のデータ部分にパケット（Ｒ）のデータ部分を追加する命令である。また、左右情報が付加された記号「Ｉａｐ１」ないし「Ｉａｐ４」（「Ｉａｐ１Ｌ」ないし「Ｉａｐ４Ｌ」、および「Ｉａｐ１Ｒ」ないし「Ｉａｐ４Ｒ」）と、１６進表記６０Ｈないし６７Ｈとが設定されている命令追加命令は、いずれも、後述するパケット（Ｌ）の処理命令部分にパケット（Ｒ）のデータ部分を追加する命令である。
【００３９】
次に、１入力・１出力命令について説明する。なお、１入力・１出力命令は、１つのデータのみをオペランドとするため、いずれも左右情報を有しない。
【００４０】
記号「ＮＯＰ」と１６進表記００Ｈとが設定されているＮＯＰ命令は、何もしない命令である。また、記号「ｒｅａｄ」と１６進表記０２Ｈとが設定されている読み出し命令は、データ（Ａ）が示す記憶装置６のアドレスに記憶されているデータ（＊Ａ）を読み出す命令である。なお、命令ではないが、パケットの終端を示すヌル文字として、例えば１６進表記ＦＦＨが設定されている。
【００４１】
次に、ループ関連命令について説明する。なお、ここでは概略についてのみ説明し、詳細については具体例を挙げて後述する。
【００４２】
左右情報が付加された記号「ｐａｃｋ」（「ｐａｃｋＬ」および「ｐａｃｋＲ」）と、１６進表記７０Ｈおよび７１Ｈとが設定されているパック（梱包）命令は、パケット（Ｌ）のデータ部分とパケット（Ｒ）のデータ部分とを１つのパケットのデータ部分に同梱する命令である。したがって、パック命令は、２入力・１出力命令となる。
【００４３】
左右情報が付加された記号「ｄｕｐ」（「ｄｕｐＬ」および「ｄｕｐＲ」）と、１６進表記７２Ｈおよび７３Ｈとが設定されているデュプリケート（複製）命令は、パケット（Ｌ）のデータ部分を複製して、２つのパケットのデータ部分に分配する命令である。その際、複製および分配によって新たに生成されたパケットの処理命令部分には、パケット（Ｒ）のデータ部分が追加される。したがって、デュプリケート命令は、２入力・２出力命令となる。
【００４４】
左右情報が付加された記号「ｓｔｅｐ」（「ｓｔｅｐＬ」および「ｓｔｅｐＲ」）と、１６進表記７４Ｈおよび７５Ｈとが設定されているステップ（段階）命令は、パケット（Ｒ）とパケット（Ｌ）のデータ部分とに応じたテンプレート情報（以下、Ｓテンプレートと称する）を生成し、後述するテンプレートバッファに登録する命令である。その際、パケット（Ｒ）およびパケット（Ｌ）自体は消滅する。したがって、ステップ命令は、２入力・０出力（ただし、Ｓテンプレートを生成）命令となる。
【００４５】
左右情報が付加された記号「ｒｅｐ１」ないし「ｒｅｐ４」（「ｒｅｐ１Ｌ」ないし「ｒｅｐ４Ｌ」、および「ｒｅｐ１Ｒ」ないし「ｒｅｐ４Ｒ」）と、１６進表記８０Ｈないし８７Ｈとが設定されているリピート（繰り返し）命令は、いずれも、パケット（Ｒ）とパケット（Ｌ）のデータ部分とに応じたテンプレート情報（以下、Ｒテンプレートと称する）を生成し、テンプレートバッファに登録する命令である。その際、パケット（Ｒ）自体は消滅する。したがって、リピート命令は、２入力・１出力（さらに、Ｒテンプレートを生成）命令となる。
【００４６】
ＭＣＥ３００は、図５に示した命令セットを用いて、データフロー図を生成する。図６は、実行コードＰＲ１から生成されたデータフロー図を示しており、図４に示したソースプログラムＰＲ０に対応している。また、図６において、Ｄ１ないしＤ８はデータを示しており、Ｉ１ないしＩ１３は命令を示している。なお、図６において、２重線は、複数のパケットからなるパケット群の生成、および生成されたパケット群に対する処理を表している。
【００４７】
データＤ１は、ループの全繰り返し数を示し、ソースプログラムにおける「ｉｉ＝０；ｉｉ＜１０２４」から、１０２４となる。また、データＤ２は、後述するループＩＤピッチ（ループＩＤの増分）を示し、１重ループや最内ループの場合には、１となる。そして、データＤ１およびＤ２の組み合わせによって、ループＩＤが１ずつ増加する１０２４個のパケット群を生成すべきことが示されている。
【００４８】
データＤ３およびＤ４は、それぞれ配列ｄｐ［１０２４］およびｓｐ［１０２４］を示すポインタであり、データＤ５はループ内の除算における除数２を示している。また、データＤ６は、デュプリケート命令の実行によって新たに生成されるパケットの処理命令部分に追加される命令を示している。
【００４９】
データＤ７は、ループ内で使用するループ変数（カウンタ変数）ｉｉの初期値を示し、ソースプログラムにおける「ｉｉ＝０」から、０となる。また、データＤ８は、後述するステップピッチ（ループ変数ｉｉに相当するデータの増分）を示し、ソースプログラムにおける「ｉｉ＋＋」から、１となる。そして、データＤ１およびＤ２の組み合わせとデータＤ７およびＤ８の組み合わせとによって、ループＩＤが１ずつ増加し、初期値０から１ずつ増加するループ変数ｉｉをデータとする１０２４個のパケット群を生成すべきことが示されている。
【００５０】
図６において、長破線より上側にある命令Ｉ１ないしＩ８は、いずれもループ関連命令であり、これらの命令が実行されることによって、ループ処理が展開され、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に相当するパケット群が生成される。なお、当該ループ処理の展開についての詳細な説明は、後述する各ループ関連命令についての具体的な説明において行うこととする。また、長破線より下側にある命令Ｉ９ないしＩ１３は、ループ処理の展開によって生成されたパケット群に対する命令であるため、これらについての詳細な説明も後述する。
【００５１】
図７は、図６に示したデータフロー図に基づいて生成される、各命令が実行される前の初期パケット列を示している。
【００５２】
各パケットは、データ部分（data section）と拡張識別情報部分（extended identification information section）とからなる。また、拡張識別情報部分は、識別情報部分（identification information section）と処理命令（命令情報）部分（processing instructions section）とからなる。なお、各パケットは、暗号化や圧縮などの目的で適宜符号化されていてもよい。
【００５３】
識別情報部分は、例えば汎用ＩＤおよびループＩＤを含む。これらのうち、汎用ＩＤは、例えば、当該パケットを生成したＭＣＥを示す発行元情報などに用いられる。一方、ループＩＤは、ループ処理におけるループの繰り返しごとに設定される識別番号であり、例えば、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に対応して、０から１０２３まで設定される。
【００５４】
本実施形態では、一例として、処理命令部分は、８個までの命令１ないし８のほか、命令数情報を含む。また、各命令は、実行順序とは逆順に配列されており、最初に実行されるべき命令が最後尾に配置され、以降はヌル文字となっている。さらに、命令数情報は、未処理の命令数を示すが、その都度計数するようにしてもよい。
【００５５】
データ部分は、データ本体のほか、当該データのデータタイプ情報および延長フラグを含む。また、データタイプ情報は、例えば「整数型（integer）」、「浮動小数点型(floating)」、「ポインタ型（pointer）」などのデータタイプを示す。さらに、データタイプとして「命令型（command）」を備えており、当該命令型のデータは、命令追加命令やデュプリケート命令の実行によって、パケットの処理命令部分に命令として追加される。本実施形態では、データ本体を例えば６４ビットの固定長とすることによって、命令型のデータとして、それぞれ８ビットの命令を８個まで格納することができる。なお、延長フラグは、命令追加命令とは異なる命令の追加機能（特許文献１における命令追加処理）に用いられる。
【００５６】
図７から明らかなように、パケットＰ１ないしＰ８で構成される初期パケット列は、図６に示したデータフロー図を８個のデータＤ１ないしＤ８ごとに再構成したものであり、各パケットは、当該データに識別情報および処理命令を付加して生成され、ＭＣＥ３００から隣接するＰＥ１００ないし１０７の何れかに発行される。
【００５７】
ＭＣＥ３００から発行されたパケットは、ＰＥ１００ないし１６３のうち、後述する宛先情報が示すＰＥまで、通信路５００を介して伝達される。また、各ＰＥは、パケットに含まれる処理命令を実行する実行ノードに相当する。なお、各ＰＥの動作についての詳細な説明は後述する。
【００５８】
なお、本発明のデータ処理装置は、本実施形態に示したように、機械語やアセンブリ言語で記述された実行コードＰＲ１からパケット列を生成するＭＣＥを備える構成に限定されるものではない。
【００５９】
例えば、記憶装置６には、ソースプログラムＰＲ０から実行コードＰＲ１にコンパイルする際の中間の段階で生成される中間コードとして、構文木（syntax tree）で表現されたプログラムが記憶されていてもよい。構文木では、オペランドが葉ノード（leaf node）に配置され、オペレータが内部ノード（internal node）に配置された木構造となっているため、機械語やアセンブリ言語の場合に比べて、データフロー図の生成が容易となる。
【００６０】
また、例えば、記憶装置６には、コンパイラを備える外部装置によって予め生成された初期パケット列（initial packet sequences）が記憶されていてもよい。この場合には、ＭＣＥ３００は、各パケットをそのまま隣接するＰＥに発行することができる。
【００６１】
また、例えば、記憶装置６には、初期パケット列のうち、識別情報部分の一部または全部を省略した、またはヌル文字とした中間パケット列（interim packet sequences）が記憶されていてもよい。この場合には、ＭＣＥ３００は、省略された識別情報部分を付加したうえで、各パケットを隣接するＰＥに発行する。
【００６２】
さらに、例えば、ループ処理の展開によって生成されたパケット群が外部装置からデータ処理装置に直接入力されてもよい。この場合の外部装置には、並列に動作している他のデータ処理装置も含まれ得る。
【００６３】
ここで、ソースプログラムとデータ処理装置１で処理されるプログラム（実行コード）との関係の他の例を図８に示す。この場合、コンパイラは、高級言語で記述されたソースプログラムＰＲ０から、データフロー図に基づいて初期パケット列または中間パケット列を生成する。また、記憶装置６には、これらのパケット列が適宜符号化されたうえで、実行コードＰＲ２として記憶される。そして、ＭＣＥ３００には、実行コードＰＲ２が読み込まれる。
【００６４】
＝＝＝ＰＥ（処理要素）の構成＝＝＝
以下、図１を参照して、本実施形態におけるＰＥの構成について説明する。
【００６５】
図１に示されているＰＥ１００ないし１６３は、入出力部２１０、比較・選択部２３０、バッファメモリ２４０、命令デコーダ２５０、ＡＬＵ（Arithmetic Logic Unit：算術論理演算部）２６０、パケット生成部２７０、およびテンプレートバッファ２８０をそれぞれ含んで構成されている。なお、本実施形態では、命令デコーダ２５０およびＡＬＵ２６０が演算部に相当する。
【００６６】
入出力部２１０は、宛先情報算出部２１１、出力ポート２１４ａないし２１４ｄ、および入力ポート２１５ａないし２１５ｄを含む。また、入出力部２１０には、各入力ポートを介して、パケットや、記憶装置６から読み出されたデータなどが入力されている。さらに、入出力部２１０からは、各出力ポートを介して、パケットや、記憶装置６に書き込まれるデータなどが出力されている。そして、各入出力ポート（入力ポートおよび出力ポート）は、前述した通信路５００（不図示）を介して、隣接するＰＥやＭＣＥと接続されている。
【００６７】
例えば、図３のＰＥ１１０の場合、４組の入出力ポートは、それぞれＰＥ１０９、１０２、１１１、および１１８と接続されている。また、例えばＰＥ１００の場合、２組の入出力ポートは、それぞれＰＥ１０１および１０８と接続され、１組の入出力ポートは、ＭＣＥ３００と接続され、そして、１組の入出力ポートは、使用されない。また、各入出力ポートが複数のチャネルを備え、当該複数のチャネルを使用して、隣接するＰＥ間やＰＥおよびＭＣＥ間でパケットやデータなどを入出力する構成としてもよい。
【００６８】
比較・選択部２３０には、入出力部２１０からパケットが入力されている。また、比較・選択部２３０は、ハッシュ値算出部２３１を含み、パケット記憶部に相当するバッファメモリ２４０との間でパケットを入出力している。さらに、比較・選択部２３０からは、命令デコーダ２５０を介して、それぞれ左側および右側オペランドとなるデータを有するパケットがＡＬＵ２６０に入力されている。そして、ＡＬＵ２６０によって新たに生成されたパケットは、再び入出力部２１０に入力されている。なお、新たに生成されたパケットの宛先情報が当該ＰＥを示している場合には、当該パケットは、入出力部２１０から再び比較・選択部２３０に入力されることとなる。
【００６９】
本実施形態では、命令デコーダ２５０からは、さらにテンプレート情報がパケット生成部２７０に入力されている。また、パケット生成部２７０は、テンプレート記憶部に相当するテンプレートバッファ２８０との間でテンプレート情報を入出力している。そして、パケット生成部２７０によって新たに生成されたパケットは、再び入出力部２１０に入力されている。
【００７０】
＝＝＝ＰＥ（処理要素）の動作＝＝＝
次に、図９ないし図１１を適宜参照して、本実施形態におけるＰＥの動作について説明する。
【００７１】
入出力部２１０は、まず、宛先情報算出部２１１が入力されたパケットの宛先情報を算出する。宛先情報は、パケットを処理すべきＰＥを示す情報であり、当該パケットの拡張識別情報部分から求めることができる。ここで、図９および図１０を参照して、本実施形態における宛先情報の算出方法について説明する。
【００７２】
宛先情報算出部２１１は、まず、各パケットから拡張識別情報部分のみを抽出し、各拡張識別情報のうち、最初に実行されるべき命令の左右情報をマスクする。前述したように、本実施形態では、最初に実行されるべき命令がパケットの最後尾（ヌル文字の直前）に配置され、各命令のＬＳＢが左右情報専用に割り当てられている。したがって、拡張識別情報の最後（ヌル文字の直前）の１ビットを０または１でマスクすればよい。
【００７３】
宛先情報算出部２１１は、次に、上記のマスクされた拡張識別情報を識別情報部分と処理命令部分とに分割し、それぞれの部分に基づいて擬似（疑似）乱数を生成し、当該擬似乱数に応じて、宛先情報を算出する。本実施形態では、図９に示すように、識別情報部分から０ないし３（２進表記で００ないし１１）の２ビットの擬似乱数Ｒｉｄを生成し、処理命令部分から０ないし１５（２進表記で００００ないし１１１１）の４ビットの擬似乱数Ｒｃｍを生成する。そして、擬似乱数Ｒｉｄの上位１ビットＸｉと擬似乱数Ｒｃｍの上位２ビットＸｃとからなる３ビットの値をＸ座標（Ｘ＝４Ｘｉ＋Ｘｃ）とし、擬似乱数Ｒｉｄの下位１ビットＹｉと擬似乱数Ｒｃｍの下位２ビットＹｃとからなる３ビットの値をＹ座標（Ｙ＝４Ｙｉ＋Ｙｃ）として算出する。
【００７４】
このようにして、識別情報および（マスクされた）処理命令からそれぞれ擬似乱数ＲｉｄおよびＲｃｍを生成し、これらの擬似乱数に応じて、図３に示した各ＰＥの座標と同じ形式の座標（Ｘ，Ｙ）を宛先情報として算出することができる。また、前述したように、Ｘ座標を上位３ビット、Ｙ座標を下位３ビットとする各ＰＥの識別番号を宛先情報としてもよい。ここで、擬似乱数は、物理乱数と異なり、再現性があるため、マスクされた拡張識別情報が同一のパケットからは同一の擬似乱数ＲｉｄおよびＲｃｍが生成され、同一の宛先情報が算出される。
【００７５】
図１０は、このように算出された宛先情報と各ＰＥとの対応関係を示している。ここで、擬似乱数Ｒｉｄの２ビットＸｉおよびＹｉは、それぞれＸ座標およびＹ座標の上位１ビット（最上位ビット）となっている。そのため、宛先情報（Ｘ，Ｙ）が示すＰＥ（宛先のＰＥ）は、当該ＸｉおよびＹｉに応じて、図１０において長破線で囲まれた４つの区画（block）の何れかに含まれることとなる。
【００７６】
このことは、６４個（８行８列）のＰＥ１００ないし１６３全体を擬似乱数Ｒｉｄの２ビットの値に対応する４つの区画に分割したことに相当する。そして、算出された宛先情報は、識別情報から生成される擬似乱数Ｒｉｄ（第１の宛先情報）に応じて何れかの区画を示し、処理命令から生成される擬似乱数Ｒｃｍ（第２の宛先情報）に応じて区画内のＰＥの位置を示すこととなる。
【００７７】
図１０に示されているように、各区画は１６個（４行４列）のＰＥを含むＰＥ群（処理部群）であり、Ｒｉｄ＝０（Ｘｉ＝Ｙｉ＝０）に対応する区画には、０≦Ｘ≦３かつ０≦Ｙ≦３の範囲のＰＥが含まれている。また、Ｒｉｄ＝１（Ｘｉ＝０、Ｙｉ＝１）に対応する区画には、０≦Ｘ≦３かつ４≦Ｙ≦７の範囲のＰＥが含まれている。また、Ｒｉｄ＝２（Ｘｉ＝１、Ｙｉ＝０）に対応する区画には、４≦Ｘ≦７かつ０≦Ｙ≦３の範囲のＰＥが含まれている。また、Ｒｉｄ＝３（Ｘｉ＝Ｙｉ＝１）に対応する区画には、４≦Ｘ≦７かつ４≦Ｙ≦７の範囲のＰＥが含まれている。そして、識別情報が同一のパケットからは同一の擬似乱数Ｒｉｄが生成されるため、それらのパケットの宛先のＰＥは、同一の区画に含まれることとなる。
【００７８】
なお、擬似乱数の生成には、公知の方法を用いることができる。宛先情報の算出時間の観点からは、ＬＣＧ（Linear Congruential Generator：線形合同法）やＬＦＳＲ（Linear Feedback Shift Register：線形帰還シフトレジスタ）など、高速な生成方法を用いることが望ましい。また、宛先情報算出部２１１は、予め生成された擬似乱数テーブルを参照して宛先情報を算出する構成としてもよい。この場合、宛先情報算出部２１１は、パケットごとに擬似乱数を生成する必要がないため、宛先情報の算出時間を短縮することができる。
【００７９】
一方、ＰＥの使用効率の観点からは、パケット分布が一様となるよう、擬似乱数が一様分布に近いほど望ましい。また、確率変数族が予測不可能であることは、一様分布であることと等価であるので、ＣＳＰＲＮＧ（Cryptographically Secure Pseudo-Random Number Generator：暗号論的擬似乱数生成器）を用いることによって、ＰＥの使用効率の向上を図ることができる。しかしながら、命令によっても各パケットの処理時間は異なるため、実際には、擬似乱数が一様分布であっても、パケット分布が一様とはならないこともある。そのため、宛先情報の算出時間が長くなり過ぎない程度で、一様分布に近い擬似乱数を用いることが望ましい。
【００８０】
さらに、パケットが入力される度に各ＰＥが宛先情報を算出する代わりに、算出した宛先情報をパケットに付加し、当該宛先情報を再利用してもよい。例えば、ＭＣＥがパケットをＰＥに発行する場合、およびＰＥが新たなパケットを生成する場合に宛先情報を付加することによって、それ以外の場合には付加されている宛先情報をそのまま利用することができる。この場合、宛先情報が付加されているパケットに対して宛先情報を算出する必要はない。
【００８１】
入出力部２１０は、次に、パケットの宛先情報が当該ＰＥを示しているか否かを判定し、当該ＰＥを示している場合には、当該パケットを取得して比較・選択部２３０に入力する。一方、パケットの宛先情報が当該ＰＥを示していない場合には、宛先情報が示すＰＥに近づく方向に隣接するＰＥに当該パケットを転送する。そして、当該動作を各ＰＥの入出力部が行うことによって、各パケットは宛先情報が示すＰＥまで伝達され、取得される。
【００８２】
例えば、各パケットは、まず、宛先情報が示すＰＥとＹ座標が一致するまで、図１０のｙ軸方向に移動し、次に、Ｘ座標が一致するまで、図１０のｘ軸方向に移動する。このような移動規則を採用することによって、パケットの移動経路は常に最短となる。また、移動中の方向転換は１回または０回となり、各ＰＥ間における通信路５００の使用頻度を平均化することができる。
【００８３】
一例として、図３において、ＭＣＥ３００からＰＥ１０３に発行されたパケットの宛先情報がＰＥ１２７を示す場合には、当該パケットは、ＰＥ１１１およびＰＥ１１９を経由して、ＰＥ１２７まで伝達される。また、一例として、ＰＥ１２７によって処理され、新たに生成されたパケットの宛先情報がＰＥ１０８を示す場合には、当該パケットは、ＰＥ１２６、ＰＥ１２５、ＰＥ１２４、およびＰＥ１１６を経由して、ＰＥ１０８まで伝達される。
【００８４】
比較・選択部２３０は、入出力部２１０によって取得されたパケット（以下、取得パケットと称する）のうち、命令の実行が可能なものを処理対象（命令の実行対象）として選択して、命令デコーダ２５０に入力する。また、比較・選択部２３０は、命令の実行が可能でないパケットをバッファメモリ２４０に記憶させるとともに、バッファメモリ２４０に記憶されているパケット（以下、記憶パケットと称する）の読み出しを行う。
【００８５】
より具体的には、取得パケットの最初に実行されるべき（最後尾の）命令が１入力・１出力命令である場合、比較・選択部２３０は、取得パケットのみを命令デコーダ２５０に入力する。一方、取得パケットの最初に実行されるべき（最後尾の）命令がループ関連命令または２入力・１出力命令である場合、比較・選択部２３０は、上記のマスクされた拡張識別情報が取得パケットと一致するパケットを、記憶パケットから検索する。そして、一致する記憶パケットが存在するときには、比較・選択部２３０は、当該一致する２つのパケットを処理対象として選択して、命令デコーダ２５０に入力する。また、一致する記憶パケットが存在しないときには、比較・選択部２３０は、取得パケットをバッファメモリ２４０に記憶させる。
【００８６】
なお、マスクされた拡張識別情報が取得パケットと一致する記憶パケットの検索を効率よく行うため、本実施形態では、バッファメモリ２４０は、ハッシュテーブルを含む。また、比較・選択部２３０は、まず、ハッシュ値算出部２３１が、取得パケットからハッシュ値を算出する。当該ハッシュ値は、宛先情報の場合と同様に、取得パケットのマスクされた拡張識別情報に基づいて算出される。そして、比較・選択部２３０は、取得パケットをバッファメモリ２４０に記憶させる場合には、取得パケットをそのハッシュ値と対応付けてハッシュテーブルに格納する。
【００８７】
なお、ハッシュテーブルには、公知の実装方法を用いることができる。図１１は、バッファメモリ２４０に実装されるハッシュテーブルの一例を示している。当該ハッシュテーブルでは、ハッシュ衝突の解決方法として、オープンアドレス法（open addressing）を用い、再ハッシュ手順として、線形探索法（linear probing）を用いている。
【００８８】
図１１においては、一例として、ハッシュ値がｎ＋３となるパケット１が格納された後に、ハッシュ値がｎとなるパケット２ないし５が格納された場合を示している。パケット１は、ルート配列［２５６］の要素ｎ＋３の位置に格納され、フラグ「１」およびカウント値「１」が設定されている。また、パケット２ないし５は、それぞれ要素ｎ、ｎ＋１、ｎ＋２、ｎ＋４の位置に格納され、要素ｎの位置にフラグ「１」およびカウント値「４」が設定されている。
【００８９】
命令デコーダ２５０は、比較・選択部２３０から入力される１つまたは２つのパケットの最初に実行されるべき命令を読解（解釈）したうえで、当該パケットをＡＬＵ２６０に入力する。また、その際、最初に実行されるべき命令がリピート命令またはステップ命令である場合には、テンプレート情報（ＲテンプレートまたはＳテンプレート）を生成し、パケット生成部２７０に入力する。
【００９０】
ＡＬＵ２６０は、命令デコーダ２５０から入力される１つまたは２つのパケットのデータ部分（オペランド）に対して、算術演算（整数演算および／または浮動小数点演算）や論理演算などを行い、演算結果を出力する。より具体的には、ＡＬＵ２６０は、入力されたパケットのデータに対して、最初に実行されるべき命令を実行し、実行結果のデータに、実行された命令を除いた拡張識別情報を付加して新たなパケットを生成し、再び入出力部２１０に入力する。
【００９１】
パケット生成部２７０は、まず、命令デコーダ２５０から入力されるテンプレート情報をテンプレートバッファ２８０に登録する。また、パケット生成部２７０は、テンプレートバッファ２８０に登録されているテンプレート情報に基づいて、テンプレート情報ごとにループ繰り返し数分のパケット群を生成し、入出力部２１０に入力する。なお、当該パケット群の生成は、パケット生成部２７０以外の各部の動作とは独立して、自動的に（クロックごとに）行われる。
【００９２】
このようにして、各ＰＥは、宛先情報が当該ＰＥを示すパケットのみを取得し、宛先情報が当該ＰＥを示さないパケットを他のＰＥに転送する。そして、取得パケットのデータに対して最初に実行されるべき命令を実行するとともに、実行結果のデータに実行された命令を除いた拡張識別情報を付加して新たなパケットを生成し、生成されたパケットをその宛先情報に応じて転送または取得する。
【００９３】
なお、本実施形態では、最初に実行されるべき命令がリピート命令である場合には、宛先情報算出部２１１およびハッシュ値算出部２３１は、それぞれ、それ以外の場合とは異なる方法で宛先情報およびハッシュ値を算出する。すなわち、最初に実行されるべき命令がリピート命令である場合には、宛先情報およびハッシュ値の算出に用いられる拡張識別情報の部分が、上記のマスクされた拡張識別情報とは異なる。この場合における宛先情報およびハッシュ値の算出方法についての詳細な説明は、後述するリピート命令についての具体的な説明において行うこととする。
【００９４】
＝＝＝データ処理装置の動作の具体例＝＝＝
ここで、図１２ないし図２０を適宜参照しつつ、図６に示したデータフロー図および図７に示した初期パケット列を用いて、データ処理装置１の動作の具体例について説明する。
【００９５】
パケットＰ１およびＰ２は、最初に実行されるべき（最後尾の）命令がいずれもパック命令Ｉ１であり、これらの拡張識別情報は、パック命令Ｉ１の左右情報を除いて一致しているため、同一の宛先情報が算出される。したがって、パケットＰ１およびＰ２は、算出された宛先情報が示す同一のＰＥまで伝達され、取得される。そして、当該ＰＥのＡＬＵ２６０においてパック命令Ｉ１が実行され、その結果、図１２に示すように、データＤ１（１０２４）とデータＤ２（１）とをデータ部分に同梱し、パック命令Ｉ１を除いた新たなパケットＰ９が生成される。同様に、パケットＰ７およびＰ８に対して、パック命令Ｉ２が実行され、その結果、データＤ７（０）とデータＤ８（１）とをデータ部分に同梱し、パック命令Ｉ２を除いた新たなパケットＰ１０が生成される。
【００９６】
なお、本実施形態では、パック命令は、整数型のデータに対して実行され、整数型のデータを例えば３２ビットの固定長とすることによって、２つの整数型のデータを１つのパケットのデータ部分に同梱することができる。また、データ部分が２つの整数型のデータからなることを示すため、パック命令の実行によって生成されたパケットＰ９およびＰ１０のデータタイプは、「梱包型（packed）」となっている。
【００９７】
パケットＰ９およびＰ３は、最初に実行されるべき命令がいずれもリピート命令Ｉ３であり、次に実行されるべき命令が格納される処理命令部分（パケットＰ９の命令５およびパケットＰ３の命令３）には、命令ではなく同一の整数「４」が格納されている。当該整数は、リピート命令の実行の際にダウンカウンタとして用いられ、リピート命令は、ダウンカウンタを備えた実質的に１６ビットの命令として取り扱われる。
【００９８】
また、これらのパケットに対しては、図１３に示すように、最初に実行される実質１６ビットのリピート命令（Ｉ３＋「４」）のみを処理命令部分に含む拡張識別情報Ｐ９’およびＰ３’を用いて、宛先情報およびハッシュ値の算出が行われる。拡張識別情報Ｐ９’およびＰ３’は、リピート命令Ｉ３の左右情報を除いて一致しているため、同一の宛先情報が算出される。したがって、パケットＰ９およびＰ３は、算出された宛先情報が示す同一のＰＥまで伝達され、取得される。そして、当該ＰＥのＡＬＵ２６０においてリピート命令Ｉ３（ｒｅｐ１）が実行され、その結果、パケットＰ９においてリピート命令Ｉ３（ｒｅｐ１Ｌ）のダウンカウンタが「３」にダウンカウントされた新たなパケットＰ１１が生成される。
【００９９】
一方、命令デコーダ２５０は、パケットＰ３においてリピート命令Ｉ３（ｒｅｐ１Ｒ）およびダウンカウンタを除いたテンプレートパケットＴＰ１を含むテンプレート情報（Ｒテンプレート）を生成し、パケット生成部２７０を介してテンプレートバッファ２８０に登録する。ここで、テンプレートパケットＴＰ１は、実際に生成されるパケットではなく、Ｒテンプレートの一部となり、パケット生成部２７０によって生成されるパケット群に反映される。
【０１００】
ここで、テンプレートバッファ２８０の構成例を図１５に示す。図１５に示すように、テンプレートバッファ２８０は、複数のテンプレート情報を登録することができる。また、テンプレート数は、テンプレートバッファ２８０に登録されているテンプレート情報の数を示し、次テンプレート番号は、パケット生成部２７０が参照すべき（次に実行すべき）テンプレート情報を示す。
【０１０１】
図１５において、テンプレート情報ＴＩ１は、リピート命令Ｉ３に従って登録されたテンプレート情報であり、テンプレートパケットＴＰ１とともに、パケット生成部２７０がパケット群を生成する際の生成条件を含んでいる。ここで、ＲＳフラグは、テンプレート情報がＲテンプレートであるかＳテンプレートであるかを示している。テンプレート情報ＴＩ１は、リピート命令Ｉ３に従って登録されたＲテンプレートであるため、ＲＳフラグは、「Ｒ」となっている。
【０１０２】
また、全生成数（ループの全繰り返し数に相当）は、当該テンプレート情報に基づいてパケット生成部２７０が生成すべき全パケット数（パケット群に含まれるパケットの個数）を示し、生成済数は、全生成数のうち、パケット生成部２７０によって既に生成されたパケット数を示している。さらに、ループＩＤピッチは、パケット生成部２７０がパケット群を生成する際のループＩＤの増分を示し、ステップピッチは、パケット生成部２７０がパケット群を生成する際のデータの増分（ループ変数ｉｉの増分に相当）を示している。そして、図１５に示すように、ＲテンプレートＴＩ１の全生成数およびループＩＤピッチには、それぞれパケットＰ９のデータ部分に同梱されたデータＤ１（１０２４）およびデータＤ２（１）が格納され、ステップピッチは、「０」となる。
【０１０３】
同様に、図１４に示すように、パケットＰ１１およびＰ４に対して、リピート命令Ｉ４（ｒｅｐ１）が実行され、その結果、パケットＰ１１においてリピート命令Ｉ４（ｒｅｐ１Ｌ）のダウンカウンタが「２」にダウンカウントされた新たなパケットＰ１２が生成される。一方、パケットＰ４においてリピート命令Ｉ４（ｒｅｐ１Ｒ）およびダウンカウンタを除いたテンプレートパケットＴＰ２を含むＲテンプレートＴＩ２がテンプレートバッファ２８０に登録される。
【０１０４】
また、同様に、パケットＰ１２およびＰ５に対して、リピート命令Ｉ５（ｒｅｐ１）が実行され、その結果、パケットＰ１２においてリピート命令Ｉ５（ｒｅｐ１Ｌ）のダウンカウンタが「１」にダウンカウントされた新たなパケットＰ１３が生成される。一方、パケットＰ５においてリピート命令Ｉ５（ｒｅｐ１Ｒ）およびダウンカウンタを除いたテンプレートパケットＴＰ３を含むＲテンプレートＴＩ３がテンプレートバッファ２８０に登録される。
【０１０５】
さらに、同様に、パケットＰ１３およびＰ６に対して、リピート命令Ｉ６（ｒｅｐ１）が実行され、その結果、パケットＰ１３において、リピート命令Ｉ６（ｒｅｐ１Ｌ）および「０」にダウンカウントされたダウンカウンタを除いた新たなパケットＰ１４が生成される。一方、パケットＰ６においてリピート命令Ｉ６（ｒｅｐ１Ｒ）およびダウンカウンタを除いたテンプレートパケットＴＰ４を含むＲテンプレートＴＩ４がテンプレートバッファ２８０に登録される。
【０１０６】
図１６に示すように、パケット生成部２７０は、テンプレートバッファ２８０に登録されたＲテンプレートＴＩ１に基づいて、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に相当する１０２４個のパケット群ＧＰ１−ｉｉを生成する。ここで、最初に生成されるパケットＧＰ１−０は、テンプレートパケットＴＰ１と同一であり、さらに、ＲテンプレートＴＩ１のループＩＤピッチが「１」であるため、パケットＧＰ１−０ないしＧＰ１−１０２３のループＩＤは、順次１ずつ増加している。また、同様に、パケット生成部２７０は、ＲテンプレートＴＩ２、ＴＩ３、およびＴＩ４に基づいて、それぞれパケット群ＧＰ２−ｉｉ、ＧＰ３−ｉｉ、およびＧＰ４−ｉｉを生成する。
【０１０７】
なお、前述したように、パケット群の生成はクロックごとに行われ、パケット生成部２７０は、テンプレートバッファ２８０を参照して、クロックごとに１つずつパケットを生成する。また、１つのＰＥにおけるテンプレートバッファ２８０に複数のテンプレート情報が登録されている場合には、パケット生成部２７０は、パケットを１つ生成する度にテンプレートバッファ２８０の次テンプレート番号を順次更新する。
【０１０８】
例えば、ＲテンプレートＴＩ１ないしＴＩ３がそれぞれ１番目ないし３番目のテンプレート情報として登録され、次テンプレート番号が１の場合には、まず、ＲテンプレートＴＩ１に基づいて、パケット群ＧＰ１−ｉｉに含まれる１つのパケットが生成される。また、次テンプレート番号は、更新されて２となる。次に、ＲテンプレートＴＩ２に基づいて、パケット群ＧＰ２−ｉｉに含まれる１つのパケットが生成され、次テンプレート番号は、更新されて３となる。次に、ＲテンプレートＴＩ３に基づいて、パケット群ＧＰ３−ｉｉに含まれる１つのパケットが生成され、次テンプレート番号は、更新されて再び１となる。
【０１０９】
以上の動作を繰り返すことによって、テンプレートバッファ２８０に登録されているすべてのテンプレート情報から均等にパケット群を生成することができる。したがって、同一のループＩＤを有するパケットができるだけ近いタイミングで生成されることとなり、未処理のパケットが増大するのを抑制することができる。
【０１１０】
リピート命令Ｉ６の実行によって生成されたパケットＰ１４、およびパック命令Ｉ２の実行によって生成されたパケットＰ１０は、最初に実行されるべき命令がいずれもステップ命令Ｉ７であり、これらの拡張識別情報は、ステップ命令Ｉ７の左右情報を除いて一致しているため、同一の宛先情報が算出される。したがって、パケットＰ１４およびＰ１０は、算出された宛先情報が示す同一のＰＥまで伝達され、取得される。
【０１１１】
そして、命令デコーダ２５０は、図１７に示すように、パケットＰ１０において、データ部分に同梱されている１番目のデータＤ７（０）のみを残し、ステップ命令Ｉ７（ｓｔｅｐＲ）を除いたテンプレートパケットＴＰ５を含むテンプレート情報（Ｓテンプレート）を生成し、パケット生成部２７０を介してテンプレートバッファ２８０に登録する。ここで、テンプレートパケットＴＰ５は、実際に生成されるパケットではなく、Ｓテンプレートの一部となり、パケット生成部２７０によって生成されるパケット群に反映される。なお、テンプレートパケットＴＰ５のデータタイプは、「梱包型」から「整数型」に戻っている。
【０１１２】
図１５において、テンプレート情報ＴＩ５は、ステップ命令Ｉ７に従って登録されたテンプレート情報であり、テンプレートパケットＴＰ５を含んでいる。ここで、テンプレート情報ＴＩ５は、ステップ命令Ｉ７に従って登録されたＳテンプレートであるため、ＲＳフラグは、「Ｓ」となっている。また、図１５に示すように、ＳテンプレートＴＩ５の全生成数およびループＩＤピッチには、それぞれパケットＰ１４のデータ部分に同梱されていたデータＤ１（１０２４）およびデータＤ２（１）が格納される。一方、ステップピッチには、パケットＰ１０のデータ部分に同梱されていた２番目のデータＤ８（１）が格納される。
【０１１３】
図１８に示すように、パケット生成部２７０は、テンプレートバッファ２８０に登録されたＳテンプレートＴＩ５に基づいて、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に相当する１０２４個のパケット群ＧＰ５−ｉｉを生成する。ここで、最初に生成されるパケットＧＰ５−０は、テンプレートパケットＴＰ５と同一であり、さらに、ＳテンプレートＴＩ５のループＩＤピッチが「１」であるため、パケットＧＰ５−０ないしＧＰ５−１０２３のループＩＤは、順次１ずつ増加している。また、ＳテンプレートＴＩ５のステップピッチが「１」であるため、パケットＧＰ５−０ないしＧＰ５−１０２３の整数型のデータは、データＤ７が示す初期値「０」から順次１ずつ増加している。したがって、パケット群ＧＰ５−ｉｉの各データは、ループ変数ｉｉに相当する。
【０１１４】
図１９に示すように、パケット群ＧＰ５−ｉｉおよびＧＰ４−ｉｉに含まれるパケットのうち、それぞれ任意のループＩＤ＝ｉｉを有するパケットＰ１５およびＰ１６は、最初に実行されるべき命令がいずれもデュプリケート命令Ｉ８であり、これらの拡張識別情報は、デュプリケート命令Ｉ８の左右情報を除いて一致しているため、同一の宛先情報が算出される。したがって、パケットＰ１５およびＰ１６は、算出された宛先情報が示す同一のＰＥまで伝達され、取得される。
【０１１５】
そして、当該ＰＥのＡＬＵ２６０においてデュプリケート命令Ｉ８が実行され、その結果、パケットＰ１５においてデュプリケート命令Ｉ８（ｄｕｐＬ）を除いた新たなパケットＰ１７が生成される。さらに、パケットＰ１５のデータ部分を複製して、パケットＰ１６の命令型のデータＤ６をパケットの処理命令部分に命令として追加した新たなパケットＰ１８も生成される。
【０１１６】
このようにして、ループ関連命令Ｉ１ないしＩ８が実行されることによって、ループ処理が展開され、図２０に示すように、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に相当するパケット群が生成される。図２０において、パケットＰ１９ないしＰ２１は、それぞれパケット群ＧＰ１−ｉｉないしＧＰ３−ｉｉに含まれるパケットのうち、任意のループＩＤ＝ｉｉを有するパケットである。そして、図２０に示されているパケットＰ１７ないしＰ２１は、ソースプログラムにおける、任意のループ変数ｉｉについてのｆｏｒループ内の処理に対応している。
【０１１７】
図６において、加算命令Ｉ９は、パケットＰ１９のデータ（ｄｐ）とパケットＰ１７のデータ（ｉｉ）とを加算してデータｄｐ＋ｉｉを出力し、加算命令Ｉ１０は、パケットＰ２０のデータ（ｓｐ）とパケットＰ１８のデータ（ｉｉ）とを加算してデータｓｐ＋ｉｉを出力する。また、読み出し命令Ｉ１１は、記憶装置６からデータ＊（ｓｐ＋ｉｉ）を読み出す。さらに、除算命令Ｉ１２は、データ＊（ｓｐ＋ｉｉ）をパケットＰ２１のデータ（２）で除算してデータ＊（ｓｐ＋ｉｉ）／２を出力する。そして、書き込み命令Ｉ５は、記憶装置６のデータ＊（ｄｐ＋ｉｉ）にデータ＊（ｓｐ＋ｉｉ）／２を書き込む。
【０１１８】
以上のデータフローによって、配列ｓｐ［１０２４］の１つの要素を２で除算した値が配列ｄｐ［１０２４］に格納される。
【０１１９】
以上のように、本実施形態のデータ処理装置は、追加されたループ関連命令を実行することによって、各ＰＥにおいてループ処理を展開し、ループ繰り返し数分のパケット群を生成する点で、特許文献１のデータ処理装置と大きく異なっている。
【０１２０】
ここで、図２０に示した５個のパケットＰ１７ないしＰ２１を１セットとすると、当該５パケットのセットは、ループ変数ｉｉ＝０からｉｉ＝１０２３までの繰り返し処理に対応して１０２４セット生成されている。そして、各セットに含まれる５パケットは、ループＩＤ（＝ｉｉ）が同一であるため、識別情報が同一となり、それらの宛先のＰＥは、いずれも同一の区画に含まれることとなる。さらに、命令Ｉ９ないしＩ１２の実行によって生成されるパケットのループＩＤは変更されないため、当該５パケットから生成されるパケットの宛先のＰＥも、同一の区画に含まれることとなる。
【０１２１】
したがって、ループ処理の展開（ループ関連命令Ｉ１ないしＩ８の実行）によって生成された５×１０２４パケットには、ループＩＤが同一の５パケットのセットごとに同一の区画が割り当てられ、各セットに含まれる５パケットは、この区画内で移動しつつ、命令Ｉ９ないしＩ１３が実行される。すなわち、ループ処理を展開した後には、パケットの移動がループＩＤごとに４行４列の区画内に制限される。そのため、本実施形態のデータ処理装置は、特許文献１のデータ処理装置において１６個（４行４列）のＰＥを備えた場合に比べて、４倍の６４個（８行８列）のＰＥを備えるものの、各パケットの平均移動距離は増加せず、パケットのＰＥ間の移動に伴うオーバーヘッドが大きくならない。
【０１２２】
一方、各５パケットのセットは、互いにループＩＤが異なるため、それらに含まれるパケットには、ループＩＤごとに４つの区画の何れかが割り当てられることとなる。そのため、それぞれの区画（に含まれるＰＥ）を有効に使用することができ、ＰＥの使用効率の向上も図られている。
【０１２３】
なお、各パケットに対する区画の割り当ては、識別情報から生成される擬似乱数Ｒｉｄに応じて行われるため、ループＩＤだけでなく汎用ＩＤによっても割り当てられる区画が異なる。したがって、例えばＭＣＥにおいて異なる汎用ＩＤを設定することによって、処理命令部分にループ関連命令を含まないパケットに対しても、異なる区画の割り当てを行うことができる。
【０１２４】
また、このような区画の割り当ては、ＰＥでループ処理を展開する場合だけでなく、ＭＣＥでループ処理を展開する場合であっても同様の効果を奏する。図２１は、特許文献１のデータ処理装置において、ＭＣＥでループ処理を展開して生成された「展開後のパケット列」を示している。図２１に示されているように、「展開後のパケット列」は、５パケットごとに識別情報が同一の５×１０２４パケットからなるため、図２０に示した５パケットのセットの１０２４セット分と同様に、擬似乱数Ｒｉｄに応じた区画の割り当てを行うことができる。
【０１２５】
さらに、このように区画の割り当てを行うことによって、省電力効果も得られる。論理回路の１つのゲートのスイッチングに伴う消費電力（動的消費電力）Ｐは、
Ｐ＝ａ×（ＣＶ２ｆ／２）
と表される。ここで、ａは活性化率、Ｃは負荷容量、Ｖは電源電圧、ｆは動作周波数である。
【０１２６】
例えば、ループ処理を行わないパケットの識別情報を固定した場合、それらのパケットからは同一の擬似乱数Ｒｉｄが生成され、同一の区画が割り当てられることとなる。したがって、ループ処理を行わない並列性の低いパケットは、１つの区画（使用区画）内で処理されるため、それ以外の区画（不使用区画）では、活性化率ａが０となり、電力を消費しなくなる。なお、実際には、入出力部２１０におけるパケットの転送などにより、不使用区画内であってもスイッチングするゲートがあるため、活性化率ａが完全には０とならない。一方、ループ処理を行う並列性の高いパケットには、ループＩＤに応じて区画が割り当てられるため、すべての区画を動作させて、ループ処理を高速に並列処理することができる。
【０１２７】
前述したように、データ処理装置１において、ＭＣＥ３００は、データごとに、識別情報および処理命令を含む拡張識別情報が付加されたパケットを生成し、８行８列の行列状に配置された６４個のＰＥ１００ないし１６３は、１６個（４行４列）のＰＥをそれぞれ含む４つの区画に分割され、各ＰＥは、宛先情報が当該ＰＥを示すパケットのみを取得し、取得パケットの命令を実行するとともに、識別情報に応じて何れかの区画を示す第１の宛先情報を算出し、（マスクされた）処理命令に応じて区画内のＰＥの位置を示す第２の宛先情報を算出することによって、ループ処理の展開によって生成されたパケットの移動が４行４列の区画内に制限されるため、全体のＰＥ数を増加させても各パケットの平均移動距離が増加せず、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくし、全体としての処理能力を向上させ、ＰＥ数の増加に見合う処理能力の向上を図ることができる。
【０１２８】
また、各パケットに対して、識別情報から生成される擬似乱数Ｒｉｄ（第１の宛先情報）に応じて区画の割り当てを行い、（マスクされた）処理命令から生成される擬似乱数Ｒｃｍ（第２の宛先情報）に応じて区画内のＰＥの割り当てを行うことによって、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくしつつ、パケット分布を一様分布に近づけ、それぞれの区画（に含まれるＰＥ）を有効に使用することができ、ＰＥの使用効率の向上を図ることができる。
【０１２９】
また、各ＰＥは、取得パケットの命令を実行してパケットを生成するとともに、テンプレートバッファ２８０に登録されたテンプレート情報に基づいて、パケット生成部２７０が独立してパケット群を生成することによって、各ＰＥにおいてループ処理を展開することができるため、ループ処理におけるボトルネックを解消し、ループ処理を高速に並列処理することができる。特に、ループ繰り返し数が確定し、同期なしに並列処理を行うことができるＤｏａｌｌ型ループ処理において、ＰＥ数の増加に見合う処理能力の向上を図ることができる。そして、生成されたパケット群に含まれる各パケットは、識別情報に含まれるループＩＤに応じて４つの区画の何れかが割り当てられ、移動が４行４列の区画内に制限されるため、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくして、全体としての処理能力を向上させ、ＰＥ数の増加に見合う処理能力の向上を図ることができる。
【０１３０】
また、リピート命令を実行し、テンプレートパケットとパケット群を生成する際の生成条件とを含むテンプレート情報（Ｒテンプレート）を生成してテンプレートバッファ２８０に登録することによって、テンプレートパケットのループＩＤを変化させたパケット群を生成することができる。
【０１３１】
また、パケット群の生成条件として、全生成数とループＩＤピッチとをテンプレートバッファ２８０に登録することによって、テンプレートパケットのループＩＤをループＩＤピッチずつ順次増加させた、全生成数が示す個数のパケットからなるパケット群を生成することができる。
【０１３２】
また、リピート命令の次に実行されるべき命令が格納される処理命令部分に、命令ではなく整数データを格納することによって、リピート命令を、ダウンカウンタを備えた実質的に１６ビットの命令として取り扱うことができ、ダウンカウントの回数分リピート命令を再利用することができる。そのため、パケットに含まれる命令数を削減することができ、パケット数の削減も図ることができる。そして、最初に実行されるべき命令がリピート命令である場合には、識別情報に応じて第１の宛先情報を算出するとともに、ダウンカウンタを含めた実質１６ビットのリピート命令のみを含む処理命令部分、すなわち、「整数データ＋リピート命令（左右情報を除く）」に応じて第２の宛先情報を算出することによって、ダウンカウンタのカウント値が同一のリピート命令が最初に実行される２つのパケットを同一のＰＥまで伝達することができる。
【０１３３】
また、ステップ命令を実行し、テンプレートパケットとパケット群を生成する際の生成条件とを含むテンプレート情報（Ｓテンプレート）を生成してテンプレートバッファ２８０に登録することによって、テンプレートパケットのループＩＤおよびループ変数（整数型のデータ）を変化させたパケット群を生成することができる。
【０１３４】
また、パケット群の生成条件として、全生成数とループＩＤピッチとステップピッチとをテンプレートバッファ２８０に登録することによって、テンプレートパケットのループＩＤをループＩＤピッチずつ順次増加させ、ループ変数を初期値からステップピッチずつ順次増加させた、全生成数が示す個数のパケットからなるパケット群を生成することができる。
【０１３５】
また、ＭＣＥ３００は、ループ関連命令を含むパケットを各ＰＥに発行することによって、各ＰＥにおいてループ処理を展開し、ＭＣＥの処理能力やＭＣＥ・ＰＥ間の通信能力によるボトルネックを解消することができる。
【０１３６】
また、データ処理システムにおいて、データ処理装置１のＭＣＥ３００が、パケットを逐次生成する、または予め生成されたパケット列を読み込むことによって、インタプリタ型またはコンパイラ型の並列コンピュータシステムを構成することができる。
【０１３７】
また、前述したように、図７に示したパケットのデータ構造において、各パケットは、識別情報に応じて算出される第１の宛先情報が示す区画内において、（マスクされた）処理命令に応じて算出される第２の宛先情報が示す位置のＰＥによって取得されて、命令が実行される。さらに、リピート命令が実行されてＲテンプレートが登録されることによって、命令の実行とは独立して、テンプレートパケットのループＩＤをループＩＤピッチずつ順次増加させた、全生成数が示す個数のパケットからなるパケット群を生成することができる。そのため、ループ処理におけるボトルネックを解消し、ループ処理を高速に並列処理することができる。そして、生成されたパケット群に含まれる各パケットは、識別情報に含まれるループＩＤに応じて区画が割り当てられるため、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくして、全体としての処理能力を向上させ、ＰＥ数の増加に見合う処理能力の向上を図ることができる。
【０１３８】
また、前述したように、ステップ命令が実行されてＳテンプレートが登録されることによって、命令の実行とは独立して、テンプレートパケットのループＩＤをループＩＤピッチずつ順次増加させ、ループ変数を初期値からステップピッチずつ順次増加させた、全生成数が示す個数のパケットからなるパケット群を生成することができる。
【０１３９】
また、ソースプログラムＰＲ０から予め生成された初期パケット列を実行コードＰＲ２として記録媒体に記録することによって、当該実行コードＰＲ２をコンパイラ型の処理系において利用することができる。
【０１４０】
また、初期パケット列のうち、識別情報部分の少なくとも一部を省略した、またはヌル文字とした中間パケット列を記録媒体に記録することによって、当該中間パケット列に省略された識別情報部分を付加したうえで、コンパイラ型の処理系において利用することができる。
【０１４１】
また、ソースプログラムＰＲ０から予め生成された初期パケット列を実行コードＰＲ２として記憶装置６に記憶させることによって、各ＭＣＥは、当該実行コードＰＲ２を読み込んで利用することができる。
【０１４２】
また、初期パケット列のうち、識別情報部分の少なくとも一部を省略した、またはヌル文字とした中間パケット列を記憶装置６に記憶させることによって、各ＭＣＥは、当該中間パケット列を読み込んで、省略された識別情報部分を付加したうえで利用することができる。
【０１４３】
また、データ処理システムにおいて、データ処理装置１が記憶装置６に記憶された初期パケット列または中間パケット列を読み込むことによって、コンパイラ型の並列コンピュータシステムを構成することができる。
【０１４４】
また、前述したように、８行８列の行列状に配置され、１６個（４行４列）のＰＥをそれぞれ含む４つの区画に分割された６４個のＰＥ１００ないし１６３は、それぞれ、識別情報に応じて何れかの区画を示す第１の宛先情報を算出し、（マスクされた）処理命令に応じて区画内のＰＥの位置を示す第２の宛先情報を算出するとともに、第１および第２の宛先情報が当該ＰＥを示すパケットのみを取得し、取得パケットの命令を実行することによって、パケットのＰＥ間の移動に伴うオーバーヘッドを小さくして、全体としての処理能力を向上させ、ＰＥ数の増加に見合う処理能力の向上を図ることができる。
【０１４５】
なお、上記実施形態は、本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更、改良され得るとともに、本発明にはその等価物も含まれる。
【０１４６】
上記実施形態では、原則として、宛先情報算出部２１１における（第１および第２の）宛先情報の算出、ハッシュ値算出部２３１におけるハッシュ値の算出、および比較・選択部２３０におけるパケットの比較（処理対象の２つのパケットの選択）には、いずれもマスクされた拡張識別情報のビット列（以下、原則使用ビット列と称する）が用いられている。ここで、マスクされた拡張識別情報は、拡張識別情報全体から、最初に実行されるべき命令の左右情報のみを除いたものである。また、例外として、最初に実行されるべき命令が実質１６ビットのリピート命令である場合には、当該最初に実行される実質１６ビットのリピート命令（ただし、左右情報を除く）のみを処理命令部分に含む拡張識別情報のビット列（以下、例外使用ビット列と称する）を用いて、宛先情報およびハッシュ値の算出やパケットの比較が行われている。しかしながら、これに限定されるものではない。
【０１４７】
宛先情報算出部２１１における宛先情報の算出では、パケットの分散性が良い（パケット分布が一様に近い）ほど、ＰＥの使用効率が向上するものの、パケットの分散性は、算出に用いるビット列よりも、算出に用いる擬似乱数に大きく依存している。そのため、上記の原則使用ビット列や例外使用ビット列のすべてを宛先情報の算出に用いる必要はなく、それらのビット列が同一のパケットから同一の宛先情報が算出されるよう、少なくともそれらのビット列の一部に基づいて宛先情報を算出すればよい。
【０１４８】
また、ハッシュ値算出部２３１におけるハッシュ値の算出でも、ハッシュテーブルの使用効率や記憶パケットの検索効率は、算出に用いるビット列よりも、算出に用いるハッシュ関数に大きく依存している。そのため、宛先情報算出部２１１における宛先情報の算出と同様に、上記の原則使用ビット列や例外使用ビット列が同一のパケットから同一のハッシュ値が算出されるよう、少なくともそれらのビット列の一部に基づいて宛先情報を算出すればよい。
【０１４９】
したがって、例えば、識別情報のビット列のみを宛先情報やハッシュ値の算出に用いると、最初に実行されるべき命令の左右情報をマスクしたり、拡張識別情報のビット列のうち算出に用いる部分を最初に実行されるべき命令によって変更したりする必要がない。一方、比較・選択部２３０におけるパケットの比較には、上記の原則使用ビット列や例外使用ビット列を用いる必要がある。
【０１５０】
上記実施形態では、宛先情報算出部２１１は、上記の原則使用ビット列や例外使用ビット列のうち、識別情報部分から擬似乱数Ｒｉｄを生成し、処理命令部分から擬似乱数Ｒｃｍを生成しているが、これに限定されるものではない。
【０１５１】
擬似乱数Ｒｉｄは、ＰＥ１００ないし１６３全体を分割した何れかの区画を示す第１の宛先情報として用いられる。そして、当該第１の宛先情報は、上記の原則使用ビット列や例外使用ビット列のうち、少なくとも識別情報の一部を含む部分（第１の部分）に基づいて算出される必要がある。例えば、識別情報のうちループＩＤのビット列のみを第１の宛先情報の算出に用いると、ループＩＤが同一のパケットには同一の区画が割り当てられ、それらのパケットの移動を割り当てた区画内に制限することができる。また、ループＩＤから必要なビット数分（例えば下位２ビット）だけ抽出して、これを擬似乱数Ｒｉｄとして用いてもよい。
【０１５２】
擬似乱数Ｒｃｍは、第１の宛先情報に応じて割り当てられた区画内のＰＥの位置を示す第２の宛先情報として用いられる。そして、当該第２の宛先情報は、上記の原則使用ビット列や例外使用ビット列のうち、少なくとも第１の部分以外の部分を含む部分（第２の部分）に基づいて算出される必要がある。例えば、上記の原則使用ビット列や例外使用ビット列全体から疑似乱数を生成し、これを第２の宛先情報として用いてもよい。
【０１５３】
なお、図７においては、識別情報部分は、汎用ＩＤおよびループＩＤを含んでいるが、これに限定されるものではない。例えば、汎用ＩＤが単にパケットを生成したＭＣＥを示しているに過ぎない場合には、処理対象として選択すべき２つのパケットが異なるＭＣＥで生成されており、異なる汎用ＩＤを有している場合もあり得る。このような場合、上記の原則使用ビット列や例外使用ビット列の一部として、汎用ＩＤを宛先情報およびハッシュ値の算出やパケットの比較に用いることはできないため、汎用ＩＤをデータ部分に含めたり、図７に示した以外の追加情報部分に含めたりする必要がある。
【符号の説明】
【０１５４】
１          データ処理装置
６          記憶装置
７          入力装置
８          出力装置
９          バス
１００〜１６３  ＰＥ（処理要素）
２１０      入出力部
２１１      宛先情報算出部
２１４ａ〜２１４ｄ  出力ポート
２１５ａ〜２１５ｄ  入力ポート
２３０      比較・選択部
２３１      ハッシュ値算出部
２４０      バッファメモリ
２５０      命令デコーダ
２６０      ＡＬＵ（算術論理演算部）
２７０      パケット生成部
２８０      テンプレートバッファ
３００      ＭＣＥ（メモリ制御要素）
４００      キャッシュメモリ
５００      通信路（伝送路）
【図１】
2013141290.tif 000003
【図２】
2013141290.tif 000004
【図３】
2013141290.tif 000005
【図４】
2013141290.tif 000006
【図５】
2013141290.tif 000007
【図６】
2013141290.tif 000008
【図７】
2013141290.tif 000009
【図８】
2013141290.tif 000010
【図９】
2013141290.tif 000011
【図１０】
2013141290.tif 000012
【図１１】
2013141290.tif 000013
【図１２】
2013141290.tif 000014
【図１３】
2013141290.tif 000015
【図１４】
2013141290.tif 000016
【図１５】
2013141290.tif 000017
【図１６】
2013141290.tif 000018
【図１７】
2013141290.tif 000019
【図１８】
2013141290.tif 000020
【図１９】
2013141290.tif 000021
【図２０】
2013141290.tif 000022
【図２１】
2013141290.tif 000023
【国際調査報告】
2013141290.tif 000024
2013141290.tif 000025
2013141290.tif 000026