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