(57)【要約】【課題】処理ユニット間の通信速度を向上させることができる情報処理装置、情報処理方法及びプログラムを提供することを課題とする。【解決手段】情報処理装置は、複数の処理ユニットの各々の間で通信された通信コストを取得する取得部（Ｓ１１０３）と、前記通信コストが第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御する追加制御部（Ｓ１１０９）とを有する。【選択図】図１１
2018207396.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理ユニットの各々の間で通信された通信コストを取得する取得部と、
前記通信コストが第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御する追加制御部と
を有することを特徴とする情報処理装置。
【請求項２】
さらに、前記バイパス通信路が接続された処理ユニット間の通信コストが第２の閾値より小さい場合には、前記バイパス通信路を削除するように制御する削除制御部を有することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記取得部は、一定期間毎に前記通信コストを取得することを特徴とする請求項１又は２に記載の情報処理装置。
【請求項４】
さらに、前記複数の処理ユニット間を接続する通信路に応じて、前記処理ユニット毎に、自己の処理ユニットから他の処理ユニットまでの距離を示すルーティングテーブルを生成し、前記バイパス通信路が追加された場合には、前記ルーティングテーブルを更新し、前記処理ユニットが通信する経路を決定するための前記ルーティングテーブルを前記処理ユニットに供給するテーブル制御部を有することを特徴とする請求項１〜３のいずれか１項に記載の情報処理装置。
【請求項５】
前記追加制御部は、前記通信コストが最大でありかつ前記第１の閾値より大きい処理ユニット間にバイパス通信路を追加することができない場合には、前記通信コストが２番目の大きくかつ前記第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御することを特徴とする請求項１〜４のいずれか１項に記載の情報処理装置。
【請求項６】
前記通信コストは、通信時間又は通信量であることを特徴とする請求項１〜５のいずれか１項に記載の情報処理装置。
【請求項７】
前記通信コストは、通信量及び前記処理ユニット間距離に応じたコストであることを特徴とする請求項１〜６のいずれか１項に記載の情報処理装置。
【請求項８】
前記複数の処理ユニットの各々は、
隣接する処理ユニットに接続するためのポートと、
前記バイパス通信路に接続するためのバイパスポートとを有することを特徴とする請求項１〜７のいずれか１項に記載の情報処理装置。
【請求項９】
前記複数の処理ユニットの各々は、
上に隣接する処理ユニットに接続するための第１のポートと、
右に隣接する処理ユニットに接続するための第２のポートと、
下に隣接する処理ユニットに接続するための第３のポートと、
左に隣接する処理ユニットに接続するための第４のポートと、
前記バイパス通信路に接続するためのバイパスポートとを有することを特徴とする請求項１〜８のいずれか１項に記載の情報処理装置。
【請求項１０】
取得部が、複数の処理ユニットの各々の間で通信された通信コストを取得し、
追加制御部が、前記通信コストが第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御することを特徴とする情報処理方法。
【請求項１１】
複数の処理ユニットの各々の間で通信された通信コストを取得し、
前記通信コストが第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御する、
処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
複数のセルの各セルが一部の隣接セルと接続線を介して接続され、送信元となるセルが送信先となるセルを指定する経路指定情報を順次出力するセル間の通信方法が知られている（特許文献１参照）。各セルは、受信した経路指定情報を解釈して、接続線で接続される隣接セルを順次選択することによりセル間の通信経路を決定する。経路指定情報を受信した各セルは、経路指定情報で指定される接続線の状態に応じて、セルに割り当てられている経路指定情報と、後続のセルに割り当てられている経路指定情報とを置き換えて通信経路を決定する。
【０００３】
また、経路を選択するとき考慮するコスト関数を決定し、コスト関数のそれぞれの優先順位を与えて複合マルチコスト関数を生成するネットワークのノード間のネットワーク経路設定方法が知られている（特許文献２参照）。接続マトリックスは、ネットワーク中のノードの各対間のマルチコストを直接表す順序を与えられたｎ個の要素からなる組を含むネットワークに対する接続マトリックスが決定される。分配特性及び交換特性がコスト関数の値の一般的な加算合計に適用可能であるように一般的加算演算子が定められる。この一般的加算演算子及び順序を使用して接続マトリックスに複合マルチコスト関数を適用することにより最短の経路マトリックスが導出される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−２９７８３４号公報
【特許文献２】特開平１０−１６１９９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１では、各セルは、隣接セルと接続線を介して接続される。セル間の距離が近い場合には、通信時間が短くなるが、セル間の距離が遠い場合には、通信時間が長くなる。通信時間が長くなると、処理性能が低下してしまう。
【０００６】
１つの側面では、本発明の目的は、処理ユニット間の通信速度を向上させることができる情報処理装置、情報処理方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００７】
情報処理装置は、複数の処理ユニットの各々の間で通信された通信コストを取得する取得部と、前記通信コストが第１の閾値より大きい処理ユニット間を接続するためのバイパス通信路を追加するように制御する追加制御部とを有する。
【発明の効果】
【０００８】
１つの側面では、処理ユニット間の通信速度を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、第１の実施形態による情報処理システムの構成例を示す図である。
【図２】図２（Ａ）は処理ユニットの構成例を示す図であり、図２（Ｂ）は処理ユニットのポートの構成例を示す図である。
【図３】図３は、処理ユニットが送信するパケットの例を示す図である。
【図４】図４は、処理ユニットのルーティングテーブルの初期値の例を示す図である。
【図５】図５は、処理ユニット間にバイパス通信路が接続された例を示す図である。
【図６】図６は、バイパス通信路を追加した場合のルーティングテーブルの例を示す図である。
【図７】図７は、情報処理装置がルーティングテーブルを生成する方法を説明するための図である。
【図８】図８は、処理ユニットが送信するポートを決定する方法を説明するための図である。
【図９】図９は、送信先の処理ユニットが生成する通信時間テーブルの例を示す図である。
【図１０】図１０は、情報処理装置が生成する通信時間テーブルの例を示す図である。
【図１１】図１１は、情報処理装置の情報処理方法を示すフローチャートである。
【図１２】図１２は、第２の実施形態による各処理ユニットが生成する通信量テーブルの例を示す図である。
【図１３】図１３は、情報処理装置が生成する通信量テーブルの例を示す図である。
【図１４】図１４（Ａ）は係数テーブルの例を示す図であり、図１４（Ｂ）は係数テーブルの距離と係数の関係を示すグラフである。
【発明を実施するための形態】
【００１０】
（第１の実施形態）
図１は、第１の実施形態による情報処理システムの構成例を示す図である。情報処理システムは、情報処理装置１０１及び再構成可能回路１０２を有する。情報処理装置１０１は、コンピュータであり、中央処理ユニット（ＣＰＵ）１１１と、ランダムアクセスメモリ（ＲＡＭ）１１２と、通信インターフェース１１３と、タイマ１１４と、ハードディスクドライブ（ＨＤＤ）ユニット１１５とを有する。ＣＰＵ１０１は、ＨＤＤユニット１１５からプログラムを読み出し、読み出したプログラムをＲＡＭ１１２に展開し、ＲＡＭ１１２に展開されたプログラムを実行する。ＣＰＵ１１１は、タイマ１１４から時間情報を取得することができる。また、ＣＰＵ１１１は、通信インターフェース１１３を介して、再構成可能回路１０２に対して、通信を行うことができる。情報処理装置１０１は、再構成可能回路１０２を制御することができる。
【００１１】
再構成可能回路１０２は、処理ユニットアレイ１２１及び制御ユニット１２２を有する。処理ユニットアレイ１２１は、例えばＦＰＧＡ（field programmable gate array）で構成されており、２次元行列状に配列された複数の処理ユニット（Processing Unit）ＰＵを有する。例えば、処理ユニットＰＵは、４行４列に配列されている。処理ユニットＰＵは、Ｘ座標値がｘであり、Ｙ座標値がｙである場合、ＰＵ（ｘ，ｙ）で表される。複数の処理ユニットＰＵは、それぞれ、隣接する処理ユニットＰＵに対して通信路で接続されている。制御ユニット１２２は、通信路情報を含んだＦＰＧＡコンフィギュレーションデータを、ＦＰＧＡである処理ユニットアレイ１２１に書き込むことにより、処理ユニットＰＵ間の通信路を変更することができる。
【００１２】
図２（Ａ）は、処理ユニットＰＵの各々の構成例を示す図である。処理ユニットＰＵは、ＣＰＵ２０１と、ＲＡＭ２０２と、通信インターフェース２０３と、タイマ２０４とを有する。情報処理装置１０１は、制御ユニット１２２を介して、ＲＡＭ２０２に対して、プログラム及びデータを書き込むことができる。ＣＰＵ２０１は、ＲＡＭ２０２に記憶されているプログラムを実行する。ＣＰＵ２０１は、タイマ２０４から時間情報を取得することができる。また、ＣＰＵ２０１は、通信インターフェース２０３を介して、他の処理ユニットＰＵに対して、通信を行うことができる。処理ユニットＰＵは、通信路を介して、他の処理ユニットＰＵに対して、通信を行うことができる。
【００１３】
なお、制御ユニット１２２は、処理ユニットＰＵと同様に、ＣＰＵ２０１と、ＲＡＭ２０２と、通信インターフェース２０３と、タイマ２０４とを有する。
【００１４】
図２（Ｂ）は、処理ユニットＰＵの各々のポートの構成例を示す図である。処理ユニットＰＵ（ｘ，ｙ）は、第１のポートＮと、第２のポートＥと、第３のポートＳと、第４のポートＷと、バイパスポートＺとを有する。第１のポートＮは、自己の処理ユニットＰＵ（ｘ，ｙ）の上に隣接する処理ユニットＰＵ（ｘ，ｙ−１）に接続するためのポートである。第２のポートＥは、自己の処理ユニットＰＵ（ｘ，ｙ）の右に隣接する処理ユニットＰＵ（ｘ＋１，ｙ）に接続するためのポートである。第３のポートＳは、自己の処理ユニットＰＵ（ｘ，ｙ）の下に隣接する処理ユニットＰＵ（ｘ，ｙ＋１）に接続するためのポートである。第４のポートＷは、自己の処理ユニットＰＵ（ｘ，ｙ）の左に隣接する処理ユニットＰＵ（ｘ−１，ｙ）に接続するためのポートである。
【００１５】
処理ユニットＰＵ（ｘ，ｙ）は、第１のポートＮを介して、上に隣接する処理ユニットＰＵ（ｘ，ｙ−１）に接続される。また、処理ユニットＰＵ（ｘ，ｙ）は、第２のポートＥを介して、右に隣接する処理ユニットＰＵ（ｘ＋１，ｙ）に接続される。また、処理ユニットＰＵ（ｘ，ｙ）は、第３のポートＳを介して、下に隣接する処理ユニットＰＵ（ｘ，ｙ＋１）に接続される。また、処理ユニットＰＵ（ｘ，ｙ）は、第４のポートＷを介して、左に隣接する処理ユニットＰＵ（ｘ−１，ｙ）に接続される。
【００１６】
バイパスポートＺは、予備のポートであり、初期状態では、いずれの処理ユニットＰＵにも接続されていない。
【００１７】
図３は、処理ユニットＰＵが他の処理ユニットＰＵに送信するパケット３００の例を示す図である。パケット３００は、送信先情報ｄｓｔ、送信元情報ｓｒｃ、データ長ｌｅｎ、データｄｔ、経由情報ｔｃｋ、タイムスタンプｔｓ及びチェックサムｓｍを有する。
【００１８】
送信先情報ｄｓｔは、このパケット３００の送信先の処理ユニットＰＵを示す。送信元情報ｓｒｃは、このパケット３００の送信元の処理ユニットＰＵを示す。送信先情報ｄｓｔ及び送信元情報ｓｒｃは、例えば１６個の処理ユニットＰＵの場合には、それぞれ４ビットである。パケット３００は、送信元情報ｓｒｃが示す処理ユニットＰＵから送信先情報ｄｓｔが示す処理ユニットＰＵに送信される。データ長ｌｅｎは、データｄｔの長さを示す。データｄｔは、データ本体（ペイロード）である。データｄｔは可変長であり、その他は固定長である。
【００１９】
経由情報ｔｃｋは、このパケット３００が経由した処理ユニットＰＵを示し、パケット３００が通信経路をループすることを防止するために用いられる。処理ユニットＰＵが１６個である場合には、経由情報ｔｃｋは１６ビットであり、その１６ビットは、それぞれ、１６個の処理ユニットＰＵに相当する。タイムスタンプｔｓは、送信時刻を示す。チェックサムｓｍは、パケット３００内の経由情報ｔｃｋを除く部分のエラーをチェックするためのエラー検出データである。
【００２０】
送信を行う処理ユニットＰＵは、経由情報ｔｃｋを０に初期設定し、送信先情報ｄｓｔ、送信元情報ｓｒｃ、データ長ｌｅｎ、データｄｔ、経由情報ｔｃｋ、タイムスタンプｔｓ及びチェックサムｓｍを含むパケット３００を生成し、パケット３００を送信先情報ｄｓｔが示す処理ユニットＰＵに向けて送信する。処理ユニットＰＵは、パケット３００を受信した場合には、パケット３００内の経由情報ｔｃｋ内の自己の処理ユニットＰＵに対応するビットを１に設定し、パケット３００を送信先情報ｄｓｔが示す処理ユニットＰＵに向けて送信する。また、処理ユニットＰＵは、パケット３００内の送信先情報ｄｓｔが自己の処理ユニットＰＵである場合には、そのパケット３００内のデータｄｔを取得する。
【００２１】
図４は、処理ユニットＰＵ（０，０）のルーティングテーブル４００の初期値の例を示す図である。初期状態では、図１及び図２（Ｂ）に示すように、各処理ユニットＰＵは、バイパスポートＺがいずれの処理ユニットＰＵにも接続されていない。
【００２２】
処理ユニットＰＵ（０，０）のルーティングテーブル４００を例に説明するが、他の処理ユニットＰＵのルーティングテーブル４００も同様である。情報処理装置１０１は、処理ユニットＰＵ毎に、ルーティングテーブル４００を生成し、複数の処理ユニットＰＵのルーティングテーブル４００をそれぞれ複数の処理ユニットＰＵのＲＡＭ２０２に書き込むように制御する。
【００２３】
ルーティングテーブル４００は、送信先Ｘと、送信先Ｙと、ポートＮと、ポートＥと、ポートＳと、ポートＷと、ポートＺの情報を有する。送信先Ｘは、送信先の処理ユニットＰＵのＸ座標値を示す。送信先Ｙは、送信先の処理ユニットＰＵのＹ座標値を示す。ポートＮは、ポートＮを使用した場合の、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵまでの最短距離（マンハッタン距離）を示す。ポートＥは、ポートＥを使用した場合の、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵまでの最短距離（マンハッタン距離）を示す。ポートＳは、ポートＳを使用した場合の、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵまでの最短距離（マンハッタン距離）を示す。ポートＷは、ポートＷを使用した場合の、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵまでの最短距離（マンハッタン距離）を示す。ポートＺは、ポートＺを使用した場合の、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵまでの最短距離（マンハッタン距離）を示す。
【００２４】
マンハッタン距離は、送信元の処理ユニットＰＵと送信先の処理ユニットＰＵの間の距離であり、送信元の処理ユニットＰＵの座標値と、送信先の処理ユニットＰＵの座標値との差の絶対値の総和である。
【００２５】
ルーティングテーブル４００の第１行では、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（０，０）までの最短距離を示し、すべてのポートにおける最短距離が０である。
【００２６】
ルーティングテーブル４００の第２行では、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（１，０）までの最短距離を示し、ポートＥでは最短距離が１であり、ポートＳでは最短距離が３であり、ポートＮ、Ｗ及びＺでは最短距離が∞である。
【００２７】
ルーティングテーブル４００の第１１行では、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（２，２）までの最短距離を示し、ポートＥ及びＳでは最短距離が４であり、ポートＮ、Ｗ及びＺでは最短距離が∞である。
【００２８】
図１及び図２（Ｂ）に示すように、処理ユニットＰＵ（０，０）は、ポートＮ、Ｗ及びＺがいずれの処理ユニットＰＵにも接続されておらず、ポートＮ、Ｗ及びＺを使用した送信が不可能であるため、すべての送信先に対して、ポートＮ、Ｗ及びＺの最短距離が∞で表される。
【００２９】
また、すべての処理ユニットＰＵは、初期状態では、ポートＺがいずれの処理ユニットＰＵにも接続されておらず、ポートＺを使用した送信が不可能であるため、すべての送信先に対して、ポートＺの最短距離が∞で表される。
【００３０】
以上のように、情報処理装置１０１は、複数の処理ユニットＰＵ間を接続する通信路に応じて、処理ユニットＰＵ毎に、自己の処理ユニットＰＵから他の処理ユニットＰＵまでの距離を示すルーティングテーブル４００を生成する。
【００３１】
図５は、処理ユニットＰＵ（０，０）のバイパスポートＺと処理ユニットＰＵ（２，２）のバイパスポートＺとの間にバイパス通信路が接続された例を示す図である。情報処理装置１０１が上記のバイパス通信路の追加を指示すると、制御ユニット１２２は、バイパス通信路情報を反映したＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込むことにより、処理ユニットＰＵ（０，０）のバイパスポートＺと処理ユニットＰＵ（２，２）のバイパスポートＺとの間にバイパス通信路が構成される。その場合、処理ユニットＰＵ（０，０）は、バイパスポートＺのバイパス通信路を用いることにより、処理ユニットＰＵ（２，２）に対して高速にパケット３００を送信することができる。また、情報処理装置１０１は、図４のルーティングテーブル４００を、バイパス通信路を追加した図６のルーティングテーブル４００に更新し、更新した複数の処理ユニットＰＵのルーティングテーブル４００をそれぞれ複数の処理ユニットＰＵのＲＡＭ２０２に供給する。
【００３２】
図６は、図５のバイパス通信路を追加した場合の処理ユニットＰＵ（０，０）のルーティングテーブル４００の例を示す図である。図６のルーティングテーブル４００が図４のルーティングテーブル４００と異なる点を説明する。図５の状態では、処理ユニットＰＵ（０，０）のバイパスポートＺは、処理ユニットＰＵ（２，２）のバイパスポートＺに接続されている。したがって、ルーティングテーブル４００のポートＺの列は、更新される。
【００３３】
図４のルーティングテーブル４００では、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（２，２）までの最短距離は４であった。これに対し、図６のルーティングテーブル４００では、バイパスポートＺにバイパス通信路を接続することにより、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（２，２）までの最短距離は１になる。バイパス通信路を設けることにより、自己の処理ユニットＰＵ（０，０）から送信先の処理ユニットＰＵ（２，２）までの最短距離（通信時間）が短くなる。
【００３４】
次に、情報処理装置１０１がルーティングテーブル４００を生成する方法を説明する。まず、情報処理装置１０１は、すべての処理ユニットＰＵ間の最短距離Ｄｉｓｔ（（ｘ０，ｙ０），（ｘ１，ｙ１））を求める。最短距離Ｄｉｓｔ（（ｘ０，ｙ０），（ｘ１，ｙ１））は、処理ユニットＰＵ（ｘ０，ｙ０）から処理ユニットＰＵ（ｘ１，ｙ１）までの最短処理であり、処理ユニットＰＵ（ｘ０，ｙ０）から処理ユニットＰＵ（ｘ１，ｙ１）までの間に経由した通信路の数である。
【００３５】
第１のステップでは、情報処理装置１０１は、すべての処理ユニットＰＵ（ｘ，ｙ）と処理ユニットＰＵ（ｘ２，ｙ２）の組みについて、処理ユニットＰＵ（ｘ，ｙ）からポートを経由して距離１で処理ユニットＰＵ（ｘ２，ｙ２）へ到達可能ならば、Ｄｉｓｔ（（ｘ，ｙ），（ｘ２，ｙ２））＝１ とする。そうでなければ、情報処理装置１０１は、Ｄｉｓｔ（（ｘ，ｙ），（ｘ２，ｙ２））＝∞とする。
【００３６】
第２のステップでは、情報処理装置１０１は、すべての処理ユニットＰＵ（ｘ０，ｙ０）と処理ユニットＰＵ（ｘ１，ｙ１）の組みについて、式（１）が成立する処理ユニットＰＵ（ｘ，ｙ）が存在する場合には、式（２）のように、最短距離Ｄｉｓｔを更新する。
Dist((x0,y0),(x,y)) + Dist((x,y),(x1,y1)) < Dist((x0,y0),(x1,y1))      （１）
Dist((x0,y0),(x1,y1)) = Dist((x0,y0),(x,y)) + Dist((x,y),(x1,y1))      （２）
【００３７】
情報処理装置１０１は、上記の更新が可能な限り、第２のステップを繰り返す。そして、情報処理装置１０１は、第２のステップが終了すると、すべての処理ユニットＰＵ間の最短距離Ｄｉｓｔを得ることができる。
【００３８】
図７は、情報処理装置１０１がルーティングテーブル４００を生成する方法を説明するための図である。距離ＲＴ（ｘ，ｙ）（ｘ１，ｙ１）（ｐｔ）は、ルーティングテーブル４００の各ポートについての最短距離に対応し、処理ユニットＰＵ（ｘ，ｙ）から各ポートｐｔを介して送信先の処理ユニットＰＵ（ｘ１，ｙ１）に送信する場合の最短距離を示す。
【００３９】
情報処理装置１０１は、プログラムの関数Ｇｏ（（ｘ，ｙ），ｐｔ）を実行することができる。関数Ｇｏ（（ｘ，ｙ），ｐｔ）は、処理ユニットＰＵのポートｐｔの接続先の処理ユニットＰＵの座標値を返す関数である。例えば、図２（Ｂ）に示すように、処理ユニットＰＵ（ｘ，ｙ）の場合、情報処理装置１０１は、関数Ｇｏ（（ｘ，ｙ），ｐｔ）を実行すると、次式に示す接続先の処理ユニットＰＵの座標値を得ることができる。
Ｇｏ（（ｘ，ｙ），Ｎ）＝（ｘ，ｙ−１）
Ｇｏ（（ｘ，ｙ），Ｅ）＝（ｘ＋１，ｙ）
Ｇｏ（（ｘ，ｙ），Ｗ）＝（ｘ−１，ｙ）
Ｇｏ（（ｘ，ｙ），Ｓ）＝（ｘ，ｙ＋１）
【００４０】
また、処理ユニットＰＵ（ｘ，ｙ）のポートｐｔが接続されていない場合、関数Ｇｏ（（ｘ，ｙ），ｐｔ）は、次式のようになる。
Ｇｏ（（ｘ，ｙ），ｐｔ）＝（∞，∞）
【００４１】
例えば、図１の処理ユニットＰＵ（０，０）の場合、関数Ｇｏ（（ｘ，ｙ），ｐｔ）は、次式のようになる。
Ｇｏ（（０，０），Ｎ）＝（∞，∞）
Ｇｏ（（０，０），Ｅ）＝（１，０）
Ｇｏ（（０，０），Ｗ）＝（∞，∞）
Ｇｏ（（０，０），Ｓ）＝（０，１）
Ｇｏ（（０，０），Ｚ）＝（∞，∞）
【００４２】
また、図５の処理ユニットＰＵ（０，０）の場合、関数Ｇｏ（（ｘ，ｙ），ｐｔ）は、次式のようになる。
Ｇｏ（（０，０），Ｎ）＝（∞，∞）
Ｇｏ（（０，０），Ｅ）＝（１，０）
Ｇｏ（（０，０），Ｗ）＝（∞，∞）
Ｇｏ（（０，０），Ｓ）＝（０，１）
Ｇｏ（（０，０），Ｚ）＝（２，２）
【００４３】
図７に示すように、処理ユニットＰＵ（ｘ，ｙ）のポートｐｔの接続先が処理ユニットＰＵ（ｘ２，ｙ２）である場合、関数Ｇｏ（（ｘ，ｙ），ｐｔ）は、次式のようになる。
Ｇｏ（（ｘ，ｙ），ｐｔ）＝（ｘ２，ｙ２）
【００４４】
この場合、処理ユニットＰＵ（ｘ，ｙ）からポートｐｔを介した処理ユニット（ｘ２，ｙ２）までの最短距離は１である。情報処理装置１０１は、次式のように、ルーティングテーブルＲＴ（ｘ，ｙ）（ｘ１，ｙ１）（ｐｔ）を得ることができる。
RT(x,y)(x1,y1)(pt) = 1 + Dist((x2,y2),(x1,y1))
【００４５】
ここで、最短距離Ｄｉｓｔ（（ｘ２，ｙ２），（ｘ１，ｙ１））は、図７のように、処理ユニットＰＵ（ｘ２，ｙ２）から処理ユニットＰＵ（ｘ１，ｙ１）までの最短距離である。このようにして、情報処理装置１０１は、図４及び図６のルーティングテーブル４００を生成することができる。
【００４６】
図８は、処理ユニットＰＵが送信（通信）するポート（経路）を決定する方法を説明するための図である。処理ユニットＰＵは、ＣＰＵ２０１及びＲＡＭ２０２を有する。ＲＡＭ２０２は、送信キュー８０１〜８０５を有する。送信キュー８０１は、処理ユニットＰＵがポートＮから送信するパケット３００をファーストインファーストアウトで格納する。送信キュー８０２は、処理ユニットＰＵがポートＥから送信するパケット３００をファーストインファーストアウトで格納する。送信キュー８０３は、処理ユニットＰＵがポートＷから送信するパケット３００をファーストインファーストアウトで格納する。送信キュー８０４は、処理ユニットＰＵがポートＳから送信するパケット３００をファーストインファーストアウトで格納する。送信キュー８０５は、処理ユニットＰＵがポートＺから送信するパケット３００をファーストインファーストアウトで格納する。
【００４７】
次に、処理ユニットＰＵがポートＮ、Ｅ、Ｗ、Ｓ及びＺのいずれからパケット３００を送信するのかを決定する方法を説明する。ポートｐｔは、ポートＮ、Ｅ、Ｗ、Ｓ及びＺのうちのいずれか１つのポートである。通信レートＲＡは、パケット３００の通信レート［バイト／秒］を示す。
【００４８】
パケット長Ｌ１は、パケット３００の長さである。図３において、パケット３００は、データｄｔが可変長であり、データｄｔ以外の部分が固定長である。したがって、ＣＰＵ２０１は、パケット３００内のデータ長ｌｅｎを基に、パケット長Ｌ１を算出することができる。キュー長Ｌ２（ｐｔ）は、ポートｐｔの送信キュー８０１〜８０５に格納されている送信待ちのパケット３００の合計の長さを示す。
【００４９】
ＣＰＵ２０１は、式（３）に示すように、ルーティングテーブル４００の距離ＲＴを用いて、すべてのポートｐｔの待ち時間Ｔ１（ｐｔ）を計算する。ここで、式（３）の第１項は、送信キューに格納されている送信待ちのパケット３００の通信時間である。式（３）の第２項は、送信対象のパケット３００の通信時間である。
T1(pt) = L2(pt)/RA + L1/RA×(RT(x,y)(x1,y1)(pt))      （３）
【００５０】
次に、ＣＰＵ２０１は、待ち時間Ｔ１（ｐｔ）が最小となるポートｐｔを選択し、送信キュー８０１〜８０５のうちの選択したポートｐｔの送信キューに送信対象のパケット３００を格納する。
【００５１】
図９は、送信先の処理ユニットＰＵ（ｘ１，ｙ１）が生成する通信時間テーブル９００の例を示す図である。すべての処理ユニットＰＵは、それぞれ、送信元の処理ユニットＰＵ毎に、自己が送信先の処理ユニットＰＵである場合のパケット３００の通信時間を累積した通信時間テーブル９００を生成する。
【００５２】
具体的には、すべての処理ユニットＰＵは、それぞれ、初期状態では、通信時間テーブル９００の通信時間を０にリセットする。そして、各処理ユニットＰＵは、パケット３００を受信した場合、パケット３００内の送信先情報ｄｓｔが自己の処理ユニットＰＵである場合には、パケット３００を受信完了処理し、タイマ２０４から受信時刻を取得する。そして、各処理ユニットＰＵは、受信完了処理後、上記の受信時刻からパケット３００のタイムスタンプ（送信時刻）ｔｓを減算することにより、パケット３００の通信時間を得る。そして、各処理ユニットＰＵは、通信時間テーブル９００内のパケット３００の送信元情報ｓｒｃが示す送信元の処理ユニットＰＵの通信時間に、上記のパケット３００の通信時間を加算する。これにより、各処理ユニットＰＵは、自己の処理ユニットＰＵが送信先情報ｄｓｔであるパケット３００の通信時間の累積値を、通信時間テーブル９００内の送信元情報ｓｒｃが示す送信元の処理ユニットＰＵ毎の通信時間として格納することができる。通信時間テーブル９００は、すべての送信元の処理ユニットＰＵから自己の処理ユニットＰＵまでの通信時間を示す。
【００５３】
図１０は、情報処理装置１０１が生成する通信時間テーブル１０００の例を示す図である。情報処理装置１０１は、一定時間ＴＡ毎に、すべての処理ユニットＰＵの通信時間テーブル９００を取得し、通信時間テーブル１０００を生成する。具体的には、情報処理装置１０１は、各処理ユニットＰＵの通信時間テーブル９００を、通信時間テーブル１０００の各行の送信先の処理ユニットＰＵの通信時間として格納する。例えば、情報処理装置１０１は、処理ユニットＰＵ（ｘ１，ｙ１）の通信時間テーブル９００を、通信時間テーブル１０００の送信先の処理ユニットＰＵ（ｘ１，ｙ１）の行の通信時間として格納する。通信時間テーブル１０００は、すべての送信元の処理ユニットＰＵと送信先の処理ユニットＰＵとの間の通信時間を示す。
【００５４】
まず、バイパス通信路の追加方法を説明する。情報処理装置１０１は、通信時間テーブル１０００内の通信時間（通信コスト）の中の最大の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を取得する。通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）から送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）までの通信時間を示す。情報処理装置１０１は、最大の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より長い場合には、図５のように、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間を接続するためのバイパス通信路を追加するように、再構成可能回路１０２を制御する。これにより、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信時間を短縮することができる。
【００５５】
次に、バイパス通信路の削除方法を説明する。バイパス通信路が追加された後、そのバイパス通信路の使用頻度が少なければ、情報処理装置１０１は、そのバイパス通信路を削除することができる。具体的には、情報処理装置１０１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間にバイパス通信路が追加されている場合、通信時間テーブル１０００を参照し、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より短い場合には、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間を接続するバイパス通信路を削除するように、再構成可能回路１０２を制御する。これにより、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の不要なバイパス通信路を削除することができる。
【００５６】
図１１は、情報処理装置１０１の情報処理方法を示すフローチャートである。情報処理装置１０１では、ＣＰＵ１１１がＲＡＭ１１２内のプログラムを実行することにより、図１１の処理を行うことができる。
【００５７】
ステップＳ１１００では、ＣＰＵ１１１は、初期化処理を行う。具体的には、ＣＰＵ１１１は、図４に示すように、バイパス通信路がない再構成可能回路１０２の各処理ユニットＰＵのルーティングテーブル４００を生成し、各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むための制御を行う。そして、ＣＰＵ１１１は、各処理ユニットＰＵのＲＡＭ２０２内の通信時間テーブル９００をすべて０にリセットするための制御を行う。これにより、制御ユニット１２２は、各処理ユニットＰＵのＲＡＭ２０２にルーティングテーブル４００を書き込み、各処理ユニットＰＵのＲＡＭ２０２内の通信時間テーブル９００をすべて０にリセットする。また、ＣＰＵ１１１は、処理タイマ値を０にリセットする。タイマ１１４は、処理タイマ値のカウントアップを開始する。
【００５８】
次に、ステップＳ１１０１では、ＣＰＵ１１１は、回路情報（通信路情報を含む）のＦＰＧＡコンフィギュレーションデータ及びデータを含む処理開始指示を再構成可能回路１０２に出力する。制御ユニット１２２は、ＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込む。処理ユニットアレイ１２１には、図１に示すように、バイパス通信路がない初期状態の通信路が形成される。各処理ユニットＰＵは、データの処理及び通信を開始する。
【００５９】
また、ＣＰＵ１１１は、各処理ユニットＰＵに対して、通信時間の計測及び通信時間テーブル９００の更新を開始するように制御する。各処理ユニットＰＵは、通信時間の計測及び通信時間テーブル９００の更新を開始する。
【００６０】
次に、ステップＳ１１０２では、ＣＰＵ１１１は、処理タイマ値が一定時間ＴＡを経過するまで待機し、経過した場合にはステップＳ１１０３に処理を進める。
【００６１】
ステップＳ１１０３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信時間（通信コスト）テーブル９００を取得し、通信時間テーブル１０００を生成し、通信時間テーブル１０００をＲＡＭ１１２に書き込む。
【００６２】
次に、ステップＳ１１０４では、ＣＰＵ１１１は、処理ユニットアレイ１２１内にバイパス通信路が存在するときに削除すべきか否かを判定する。初期状態では、ＣＰＵ１１１は、バイパス通信路が存在しないと判定し、ステップＳ１１０６に処理を進める。
【００６３】
ステップＳ１１０６では、ＣＰＵ１１１は、通信時間テーブル１０００内の通信時間（通信コスト）の中の最大の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を取得する。次に、ＣＰＵ１１１は、最大の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より長いか否かを判定し、第１の閾値より長い場合にはステップＳ１１０７に処理を進め、第１の閾値より短い場合にはステップＳ１１１０に処理を進める。
【００６４】
ステップＳ１１０７では、ＣＰＵ１１１は、最大の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））に対応する送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加可能か否かを判定する。例えば、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）又は送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺが使用済みである場合には、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加可能でないと判定する。また、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）及び送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺが未使用であり、かつ、ＦＰＧＡ内にバイパス通信路を配線できるだけの回路リソースの余裕がある場合には、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加可能であると判定する。なお、各処理ユニットＰＵのバイパスポートＺは、１個に限定されず、２個以上でもよい。ＣＰＵ１１１は、バイパス通信路を追加可能であると判定した場合にはステップＳ１１０９に処理を進め、バイパス通信路を追加可能でないと判定した場合にはステップＳ１１０８に処理を進める。
【００６５】
ステップＳ１１０８では、ＣＰＵ１１１は、バイパス通信路の次候補があるか否かを判定する。具体的には、ＣＰＵ１１１は、通信時間テーブル１０００内の通信時間の中の２番目に長い通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を次候補として取得する。次に、ＣＰＵ１１１は、２番目に長い通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より長いか否かを判定し、第１の閾値より長い場合にはステップＳ１１０７に処理を戻し、第１の閾値より短い場合にはステップＳ１１１０に処理を進める。ステップＳ１１０７では、ＣＰＵ１１１は、次候補に対して、バイパス通信路が追加可能か否かを判定する。なお、ステップＳ１１０８では、ＣＰＵ１１１は、ステップＳ１１０７の処理対象の通信時間の次に長い通信時間を次候補とする。
【００６６】
ステップＳ１１０９では、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加するための通信路情報のＦＰＧＡコンフィギュレーションデータを生成し、ステップＳ１１１０に処理を進める。
【００６７】
ステップＳ１１１０では、ＣＰＵ１１１は、再構成可能回路１０２に動的再構成が行われるか否かを判定する。具体的には、ＣＰＵ１１１は、ステップＳ１１０９でバイパス通信路追加のためのＦＰＧＡコンフィギュレーションデータが生成された場合には動的再構成が行われると判定し、バイパス通信路追加のためのＦＰＧＡコンフィギュレーションデータが生成されていない場合には動的再構成が行われないと判定する。ＣＰＵ１１１は、動的再構成が行われると判定した場合にはステップＳ１１１１に処理を進め、動的再構成が行われないと判定した場合にはステップＳ１１１３に処理を進める。
【００６８】
ステップＳ１１１１では、ＣＰＵ１１１は、バイパス通信路追加のためのＦＰＧＡコンフィギュレーションデータを再構成可能回路１０２に出力する。すると、制御ユニット１２２は、ＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込む。これにより、処理ユニットアレイ１２１では、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路が追加される。
【００６９】
次に、ステップＳ１１１２では、ＣＰＵ１１１は、上記のバイパス通信路の追加に対応し、図６のように、各処理ユニットＰＵのルーティングテーブル４００を更新する。そして、ＣＰＵ１１１は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むように制御する。制御ユニット１２２は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２にそれぞれ書き込むように制御する。その後、ＣＰＵ１１１は、ステップＳ１１１３に処理を進める。
【００７０】
ステップＳ１１１３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信時間テーブル９００のすべての通信時間を０にリセットするように、再構成可能回路１０２を制御する。制御ユニット１２２は、各処理ユニットＰＵのＲＡＭ２０２内の通信時間テーブル９００のすべての通信時間を０にリセットする。また、ＣＰＵ１１１は、処理タイマ値を０にリセットし、ステップＳ１１０２に処理を戻す。
【００７１】
ステップＳ１１０２では、ＣＰＵ１１１は、処理タイマ値が一定時間ＴＡを経過するまで待機し、経過した場合にはステップＳ１１０３に処理を進める。ステップＳ１１０３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信時間テーブル９００を取得し、通信時間テーブル１０００を生成し、通信時間テーブル１０００をＲＡＭ１１２に書き込む。
【００７２】
次に、ステップＳ１１０４では、ＣＰＵ１１１は、処理ユニットアレイ１２１内にバイパス通信路が存在するか否かを判定し、バイパス通信路が存在する場合には、バイパス通信路を削除するか否かを判定する。具体的には、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間にバイパス通信路が追加されている場合、通信時間テーブル１０００を参照し、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より短いか否かを判定する。そして、ＣＰＵ１１１は、通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より短いと判定した場合にはステップＳ１１０５に処理を進め、通信時間ＴＴ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より長いと判定した場合にはステップＳ１１０６に処理を進める。ステップＳ１１０６以下の処理は、上記と同様である。
【００７３】
ステップＳ１１０５では、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間のバイパス通信路を削除したＦＰＧＡコンフィギュレーションデータを生成し、ステップＳ１１１０に処理を進める。
【００７４】
ステップＳ１１１０では、ＣＰＵ１１１は、ステップＳ１１０５でバイパス通信路を削除したＦＰＧＡコンフィギュレーションデータが生成された場合には動的再構成が行われると判定し、バイパス通信路を削除したＦＰＧＡコンフィギュレーションデータが生成されていない場合には動的再構成が行われないと判定する。ＣＰＵ１１１は、動的再構成が行われると判定した場合にはステップＳ１１１１に処理を進め、動的再構成が行われないと判定した場合にはステップＳ１１１３に処理を進める。
【００７５】
ステップＳ１１１１では、ＣＰＵ１１１は、バイパス通信路を削除したＦＰＧＡコンフィギュレーションデータを再構成可能回路１０２に出力する。すると、制御ユニット１２２は、ＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込む。これにより、処理ユニットアレイ１２１では、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間のバイパス通信路が削除される。
【００７６】
次に、ステップＳ１１１２では、ＣＰＵ１１１は、上記のバイパス通信路の削除に対応し、図４のように、各処理ユニットＰＵのルーティングテーブル４００を更新する。そして、ＣＰＵ１１１は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むように制御する。制御ユニット１２２は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２にそれぞれ書き込むように制御する。その後、ＣＰＵ１１１は、ステップＳ１１１３に処理を進める。ステップＳ１１１３以降の処理は、上記と同様である。
【００７７】
本実施形態によれば、情報処理装置１０１は、通信時間が第１の閾値より長い場合には、バイパス通信路を追加することができる。これにより、処理ユニットＰＵ間の通信速度を向上させることができる。また、情報処理装置１０１は、バイパス通信路の通信時間が第２の閾値より短い場合には、バイパス通信路を削除することができる。これにより、不要なバイパス通信路を削除することができる。
【００７８】
各処理ユニットＰＵ間の通信時間は、処理ユニットＰＵの処理内容又は処理ユニットＰＵへの入力データに応じて変化する。そのため、バイパス通信路を接続すべき経路は、固定ではない。情報処理装置１０１は、再構成可能回路１０２が動作中に通信時間を計測することにより、適切なバイパス通信路の位置を変えることができる。
【００７９】
また、すべての処理ユニットＰＵ間に最初からより多くの通信路を設ける方法も考えられる。しかし、この場合、多くの通信路のために必要な配線が増加するため、再構成可能回路１０２の面積が大きくなる。もしも半導体チップ面積が増やせないとすると、処理ユニットＰＵの数が減ってしまう。本実施形態によれば、各処理ユニットＰＵのバイパスポートＺ間にバイパス通信路を直接接続するだけであるので、通信路の配線の数は抑えられ、再構成可能回路１０２の面積増加を低減し、構成可能な処理ユニットＰＵの数の減少を低減することができる。
【００８０】
（第２の実施形態）
図１２は、第２の実施形態による各処理ユニットＰＵ（ｘ０，ｙ０）が生成する通信量テーブル１２００の例を示す図である。各処理ユニットＰＵは、図９の通信時間テーブル９００の代わりに、通信量テーブル１２００を生成する。以下、本実施形態が第１の実施形態と異なる点を説明する。
【００８１】
すべての処理ユニットＰＵは、それぞれ、送信先の処理ユニットＰＵ毎に、パケット３００の通信量を累積した通信量テーブル１２００を生成する。具体的には、すべての処理ユニットＰＵは、それぞれ、初期状態では、通信量テーブル１２００の通信量を０にリセットする。そして、各処理ユニットＰＵは、パケット３００を送信する場合、自己の処理ユニットＰＵが送信元の処理ユニットＰＵ又は中継の処理ユニットＰＵである場合には、通信量テーブル１２００内のパケット３００の送信先情報ｄｓｔが示す送信先の処理ユニットＰＵの通信量に、パケット３００のパケット長Ｌ１を加算する。これにより、各処理ユニットＰＵは、自己の処理ユニットＰＵが送信するパケット３００の通信量の累積値を、通信量テーブル１２００内の送信先情報ｄｓｔが示す送信先の処理ユニットＰＵ毎の通信量として格納することができる。通信量テーブル１２００は、自己の処理ユニットＰＵからすべての送信先の処理ユニットＰＵへの通信量を示す。
【００８２】
図１３は、情報処理装置１０１が生成する通信量テーブル１３００の例を示す図である。情報処理装置１０１は、一定時間ＴＡ毎に、すべての処理ユニットＰＵの通信量テーブル１２００を取得し、通信量テーブル１３００を生成する。具体的には、情報処理装置１０１は、各処理ユニットＰＵの通信量テーブル１２００を、通信量テーブル１３００の各列の送信元の処理ユニットＰＵの通信時間として格納する。例えば、情報処理装置１０１は、処理ユニットＰＵ（ｘ０，ｙ０）の通信量テーブル１２００を、通信量テーブル１３００の送信元の処理ユニットＰＵ（ｘ０，ｙ０）の列の通信量として格納する。通信量テーブル１３００は、すべての送信元の処理ユニットＰＵと送信先の処理ユニットＰＵとの間の通信量を示す。
【００８３】
なお、通信量テーブル１３００の通信量は、処理ユニットＰＵ間の距離情報が含まれていない。しかし、情報処理装置１０１は、距離が遠い処理ユニットＰＵ間にバイパス通信路を追加することにより、処理ユニットＰＵ間の通信時間を短縮することが好ましい。以下、上記の通信量を距離情報で補正する方法を説明する。
【００８４】
図１４（Ａ）は係数テーブル１４００の例を示す図であり、図１４（Ｂ）は係数テーブル１４００の距離ｄと係数αの関係を示すグラフである。情報処理装置１０１のＲＡＭ１１２は、係数テーブル１４００を記憶する。係数テーブル１４００は、送信元の処理ユニットＰＵと送信先の処理ユニットＰＵとの間の距離ｄと係数αとの関係を示す。距離ｄは、上記の最短距離Ｄｉｓｔと同じである。距離ｄが長いほど、係数αが大きくなる。情報処理装置１０１は、図１３の通信量テーブル１３００の各通信量に対して、係数テーブル１４００が示す距離ｄに応じた係数αを乗算し、通信量テーブル１３００の各通信量を補正する。
【００８５】
まず、バイパス通信路の追加方法を説明する。情報処理装置１０１は、通信量テーブル１３００内の通信量（通信コスト）の中の最大の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を取得する。通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）から送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）までの通信量を示す。情報処理装置１０１は、最大の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より多い場合には、図５のように、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間を接続するためのバイパス通信路を追加するように、再構成可能回路１０２を制御する。これにより、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信時間を短縮することができる。
【００８６】
次に、バイパス通信路の削除方法を説明する。バイパス通信路が追加された後、そのバイパス通信路の使用頻度が少なければ、情報処理装置１０１は、そのバイパス通信路を削除することができる。具体的には、情報処理装置１０１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間にバイパス通信路が追加されている場合、通信量テーブル１３００を参照し、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より少ない場合には、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間を接続するバイパス通信路を削除するように、再構成可能回路１０２を制御する。これにより、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の不要なバイパス通信路を削除することができる。
【００８７】
次に、図１１を参照しながら、情報処理装置１０１の情報処理方法を説明する。情報処理装置１０１では、ＣＰＵ１１１がＲＡＭ１１２内のプログラムを実行することにより、図１１の処理を行うことができる。
【００８８】
ステップＳ１１００では、ＣＰＵ１１１は、バイパス通信路がない再構成可能回路１０２の各処理ユニットＰＵのルーティングテーブル４００を生成し、各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むための制御を行う。そして、ＣＰＵ１１１は、各処理ユニットＰＵのＲＡＭ２０２内の通信量テーブル１２００をすべて０にリセットするための制御を行う。これにより、制御ユニット１２２は、各処理ユニットＰＵのＲＡＭ２０２にルーティングテーブル４００を書き込み、各処理ユニットＰＵのＲＡＭ２０２内の通信量テーブル１２００をすべて０にリセットする。また、ＣＰＵ１１１は、処理タイマ値を０にリセットする。タイマ１１４は、処理タイマ値のカウントアップを開始する。
【００８９】
次に、ステップＳ１１０１では、ＣＰＵ１１１は、回路情報（通信路情報を含む）のＦＰＧＡコンフィギュレーションデータを含む処理開始指示を再構成可能回路１０２に出力する。処理ユニットアレイ１２１には、図１に示すように、バイパス通信路がない初期状態の通信路が形成される。各処理ユニットＰＵは、データの処理及び通信を開始する。
【００９０】
また、ＣＰＵ１１１は、各処理ユニットＰＵに対して、通信量の計測及び通信量テーブル１２００の更新を開始するように制御する。各処理ユニットＰＵは、通信量の計測及び通信量テーブル１２００の更新を開始する。
【００９１】
次に、ステップＳ１１０２では、ＣＰＵ１１１は、処理タイマ値が一定時間ＴＡを経過するまで待機し、経過した場合にはステップＳ１１０３に処理を進める。
【００９２】
ステップＳ１１０３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信量（通信コスト）テーブル１２００を取得し、通信量テーブル１３００を生成する。そして、ＣＰＵ１１１は、通信量テーブル１３００の各通信量に対して、係数テーブル１４００の距離ｄに応じた係数αを乗算し、通信量テーブル１３００の各通信量を補正し、通信量テーブル１３００をＲＡＭ１１２に書き込む。
【００９３】
次に、ステップＳ１１０４では、ＣＰＵ１１１は、処理ユニットアレイ１２１内にバイパス通信路が存在するか否かを判定する。初期状態では、ＣＰＵ１１１は、バイパス通信路が存在しないと判定し、ステップＳ１１０６に処理を進める。
【００９４】
ステップＳ１１０６では、ＣＰＵ１１１は、通信量テーブル１３００内の通信量（通信コスト）の中の最大の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を取得する。次に、ＣＰＵ１１１は、最大の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より多いか否かを判定し、第１の閾値より多い場合にはステップＳ１１０７に処理を進め、第１の閾値より少ない場合にはステップＳ１１１０に処理を進める。
【００９５】
ステップＳ１１０７では、ＣＰＵ１１１は、最大の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））に対応する送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加可能か否かを判定する。ＣＰＵ１１１は、バイパス通信路を追加可能であると判定した場合にはステップＳ１１０９に処理を進め、バイパス通信路を追加可能でないと判定した場合にはステップＳ１１０８に処理を進める。
【００９６】
ステップＳ１１０８では、ＣＰＵ１１１は、バイパス通信路の次候補があるか否かを判定する。具体的には、ＣＰＵ１１１は、通信量テーブル１３００内の通信量の中の２番目に多い通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））を次候補として取得する。次に、ＣＰＵ１１１は、２番目に多い通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第１の閾値より多いか否かを判定し、第１の閾値より多い場合にはステップＳ１１０７に処理を戻し、第１の閾値より少ない場合にはステップＳ１１１０に処理を進める。ステップＳ１１０７では、ＣＰＵ１１１は、次候補に対して、バイパス通信路が追加可能か否かを判定する。
【００９７】
ステップＳ１１０９では、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路を追加したＦＰＧＡコンフィギュレーションデータを生成し、ステップＳ１１１０に処理を進める。
【００９８】
ステップＳ１１１０では、ＣＰＵ１１１は、再構成可能回路１０２に動的再構成が行われるか否かを判定する。そして、ＣＰＵ１１１は、動的再構成が行われると判定した場合にはステップＳ１１１１に処理を進め、動的再構成が行われないと判定した場合にはステップＳ１１１３に処理を進める。
【００９９】
ステップＳ１１１１では、ＣＰＵ１１１は、バイパス通信路を追加したＦＰＧＡコンフィギュレーションデータを再構成可能回路１０２に出力する。すると、制御ユニット１２２は、ＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込む。これにより、処理ユニットアレイ１２１では、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間にバイパス通信路が追加される。
【０１００】
次に、ステップＳ１１１２では、ＣＰＵ１１１は、上記のバイパス通信路の追加に対応し、図６のように、各処理ユニットＰＵのルーティングテーブル４００を更新する。そして、ＣＰＵ１１１は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むように制御する。その後、ＣＰＵ１１１は、ステップＳ１１１３に処理を進める。
【０１０１】
ステップＳ１１１３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信量テーブル１２００のすべての通信量を０にリセットするように、再構成可能回路１０２を制御する。制御ユニット１２２は、各処理ユニットＰＵのＲＡＭ２０２内の通信量テーブル１２００のすべての通信時間を０にリセットする。また、ＣＰＵ１１１は、処理タイマ値を０にリセットし、ステップＳ１１０２に処理を戻す。
【０１０２】
ステップＳ１１０２では、ＣＰＵ１１１は、処理タイマ値が一定時間ＴＡを経過するまで待機し、経過した場合にはステップＳ１１０３に処理を進める。ステップＳ１１０３では、ＣＰＵ１１１は、各処理ユニットＰＵの通信量テーブル１２００を取得し、通信量テーブル１３００を生成する。そして、ＣＰＵ１１１は、通信量テーブル１３００の各通信量に対して、係数テーブル１４００の距離ｄに応じた係数αを乗算し、通信量テーブル１３００の各通信量を補正し、通信量テーブル１３００をＲＡＭ１１２に書き込む。
【０１０３】
次に、ステップＳ１１０４では、ＣＰＵ１１１は、処理ユニットアレイ１２１内にバイパス通信路が存在するか否かを判定し、バイパス通信路が存在する場合には、バイパス通信路を削除するか否かを判定する。具体的には、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間にバイパス通信路が追加されている場合、通信量テーブル１３００を参照し、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）と送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）との間の通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より少ないか否かを判定する。そして、ＣＰＵ１１１は、通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より少ないと判定した場合にはステップＳ１１０５に処理を進め、通信量ＤＤ（（ｘｓ，ｙｓ），（ｘｄ，ｙｄ））が第２の閾値より多いと判定した場合にはステップＳ１１０６に処理を進める。ステップＳ１１０６以下の処理は、上記と同様である。
【０１０４】
ステップＳ１１０５では、ＣＰＵ１１１は、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間のバイパス通信路を削除したＦＰＧＡコンフィギュレーションデータを生成し、ステップＳ１１１０に処理を進める。
【０１０５】
ステップＳ１１１０では、ＣＰＵ１１１は、ステップＳ１１０５でバイパス通信路を削除したＦＰＧＡコンフィギュレーションデータが生成された場合には動的再構成が行われると判定し、バイパス通信路を削除したＦＰＧＡコンフィギュレーションデータが生成されていない場合には動的再構成が行われないと判定する。ＣＰＵ１１１は、動的再構成が行われると判定した場合にはステップＳ１１１１に処理を進め、動的再構成が行われないと判定した場合にはステップＳ１１１３に処理を進める。
【０１０６】
ステップＳ１１１１では、ＣＰＵ１１１は、バイパス通信路を削除したＦＰＧＡコンフィギュレーションデータを再構成可能回路１０２に出力する。すると、制御ユニット１２２は、ＦＰＧＡコンフィギュレーションデータを処理ユニットアレイ１２１に書き込む。これにより、処理ユニットアレイ１２１では、送信元の処理ユニットＰＵ（ｘｓ，ｙｓ）のバイパスポートＺと送信先の処理ユニットＰＵ（ｘｄ，ｙｄ）のバイパスポートＺとの間のバイパス通信路が削除される。
【０１０７】
次に、ステップＳ１１１２では、ＣＰＵ１１１は、上記のバイパス通信路の削除に対応し、図４のように、各処理ユニットＰＵのルーティングテーブル４００を更新する。そして、ＣＰＵ１１１は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２に書き込むように制御する。制御ユニット１２２は、その各ルーティングテーブル４００を各処理ユニットＰＵのＲＡＭ２０２にそれぞれ書き込むように制御する。その後、ＣＰＵ１１１は、ステップＳ１１１３に処理を進める。ステップＳ１１１３以降の処理は、上記と同様である。
【０１０８】
本実施形態によれば、情報処理装置１０１は、通信量が第１の閾値より多い場合には、バイパス通信路を追加することができる。これにより、処理ユニットＰＵ間の通信速度を向上させることができる。また、情報処理装置１０１は、バイパス通信路の通信量が第２の閾値より少ない場合には、バイパス通信路を削除することができる。これにより、不要なバイパス通信路を削除することができる。
【０１０９】
以上のように、第１及び第２の実施形態によれば、ステップＳ１１０３では、ＣＰＵ１１１は、複数の処理ユニットＰＵの各々の間で通信された通信コストを一定時間ＴＡ毎に取得する。第１の実施形態では、通信コストは通信時間である。第２の実施形態では、通信コストは通信量である。具体的には、第２の実施形態では、通信コストは、通信量及び処理ユニットＰＵ間の距離ｄに応じたコストである。
【０１１０】
ステップＳ１１０６〜Ｓ１１０９では、ＣＰＵ１１１は、通信コストが第１の閾値より大きい処理ユニットＰＵ間を接続するためのバイパス通信路を追加するように制御する。なお、ＣＰＵ１１１は、通信時間が第１の閾値より長い又は通信量が第１の閾値より多い処理ユニットＰＵ間を接続するためのバイパス通信路を追加するように制御してもよい。また、ＣＰＵ１１１は、通信時間が第１の閾値より長く、かつ、通信量が第１の閾値より多い処理ユニットＰＵ間を接続するためのバイパス通信路を追加するように制御してもよい。
【０１１１】
ステップＳ１１０８では、ＣＰＵ１１１は、通信コストが最大でありかつ第１の閾値より大きい処理ユニットＰＵ間にバイパス通信路を追加することができない場合には、通信コストが２番目の大きくかつ第１の閾値より大きい処理ユニットＰＵ間を接続するためのバイパス通信路を追加するように制御する。
【０１１２】
ステップＳ１１０４〜Ｓ１１０５では、ＣＰＵ１１１は、バイパス通信路が接続された処理ユニットＰＵ間の通信コストが第２の閾値より小さい場合には、バイパス通信路を削除するように制御する。なお、ＣＰＵ１１１は、バイパス通信路が接続された処理ユニットＰＵ間の通信時間が第２の閾値より短い又は通信量が第２の閾値より少ない場合には、バイパス通信路を削除するように制御してもよい。また、ＣＰＵ１１１は、バイパス通信路が接続された処理ユニットＰＵ間の通信時間が第２の閾値より短く、かつ、通信量が第２の閾値より少ない場合には、バイパス通信路を削除するように制御してもよい。
【０１１３】
情報処理装置１０１は、通信コストが第１の閾値より大きい場合には、バイパス通信路を追加することができる。これにより、処理ユニットＰＵ間の通信速度を向上させることができる。また、情報処理装置１０１は、バイパス通信路の通信コストが第２の閾値より小さい場合には、バイパス通信路を削除することができる。これにより、不要なバイパス通信路を削除することができる。
【０１１４】
なお、各処理ユニットＰＵは、２個以上のバイパスポートＺを有していてもよい。また、処理ユニットアレイ１２１は、１個のバイパス通信路に限定されず、２個以上のバイパス通信路を設けてもよい。
【０１１５】
本実施形態は、コンピュータがプログラムを実行することによって実現することができる。また、上記のプログラムを記録したコンピュータ読み取り可能な記録媒体及び上記のプログラム等のコンピュータプログラムプロダクトも本発明の実施形態として適用することができる。記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【０１１６】
なお、上記実施形態は、何れも本発明を実施するにあたっての具体化の例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその技術思想、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【０１１７】
１０１  情報処理装置
１０２  再構成可能回路
１１１  ＣＰＵ
１１２  ＲＡＭ
１１３  通信インターフェース
１１４  タイマ
１１５  ハードディスクドライブユニット
１２１  処理ユニットアレイ
１２２  制御ユニット
【図１】
2018207396.tif 000003
【図２】
2018207396.tif 000004
【図３】
2018207396.tif 000005
【図４】
2018207396.tif 000006
【図５】
2018207396.tif 000007
【図６】
2018207396.tif 000008
【図７】
2018207396.tif 000009
【図８】
2018207396.tif 000010
【図９】
2018207396.tif 000011
【図１０】
2018207396.tif 000012
【図１１】
2018207396.tif 000013
【図１２】
2018207396.tif 000014
【図１３】
2018207396.tif 000015
【図１４】
2018207396.tif 000016