(57)【要約】  アクセラレータを用いた経路計算を高速化すること。経路計算装置は、与えられた処理を複数のスレッドを用いて並列に行う計算手段と、計算手段を制御する制御手段とを備え、制御手段は、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類し、計算手段に対して、スタートノードからの距離が相対的に短いノードのグループに属するノードとスタートノードとの間の経路計算の後、スタートノードからの距離が相対的に長いノードのグループに属するノードとスタートノードとの間の経路計算を行わせる。
2015064683.tif 000002
【特許請求の範囲】
【請求項１】
与えられた処理を複数のスレッドを用いて並列に行う計算手段と、
前記計算手段を制御する制御手段と、を備え、
前記制御手段は、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類し、前記計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる、経路計算装置。
【請求項２】
前記制御手段は、前記グラフに含まれるノードを前記スタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、請求項１に記載の経路計算装置。
【請求項３】
前記制御手段は、前記グラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる、請求項１または２に記載の経路計算装置。
【請求項４】
前記制御手段は、前記スタートノードからの距離が更新されるノードの数を、前回の更新処理に要した処理時間に基づいて予測する、請求項３に記載の経路計算装置。
【請求項５】
複数の前記計算手段を備え、
前記制御手段は、前記グラフを前記複数の計算手段の数よりも大きい数で複数の領域に分割し、前記複数の計算手段に対して、前記複数の領域をランダムに割り当て、割り当てられた領域に含まれるノードと前記スタートノードとの間の経路計算を行わせる、請求項１ないし４のいずれか１項に記載の経路計算装置。
【請求項６】
前記制御手段は、前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じてグループに分類し、前記複数の計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる、請求項５に記載の経路計算装置。
【請求項７】
前記制御手段は、前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、請求項６に記載の経路計算装置。
【請求項８】
前記制御手段は、前記複数の計算手段に対して、経路計算の途中で、割り当てられた領域に含まれるノードの前記スタートノードからの距離が更新されたかどうかを示す情報を交換させる、請求項５ないし７のいずれか１項に記載の経路計算装置。
【請求項９】
与えられた処理を複数のスレッドを用いて並列に行う計算手段と、
前記計算手段を制御する制御手段と、を備え、
前記制御手段は、経路計算対象のグラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる、経路計算装置。
【請求項１０】
前記制御手段は、前記スタートノードからの距離が更新されるノードの数を、前回の更新処理に要した処理時間に基づいて予測する、請求項９に記載の経路計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１３−２２５８０３号（２０１３年１０月３０日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、経路計算装置、経路計算方法およびプログラムに関し、特に、アクセラレータを用いた経路計算装置、経路計算方法およびプログラムに関する。
【背景技術】
【０００２】
アクセラレータを用いた経路計算装置の一例が、非特許文献１に記載されている。アクセラレータとは、ＣＰＵ（Central Processing Unit）で行われる計算において、特に並列性が高い計算を高速に行うことができるデバイスであり、これらの計算をＣＰＵからアクセラレータにオフロードすることで計算を高速に行うことができる。アクセラレータとして用いられるデバイスの一例として、ＧＰＵ（Graphics Processing Unit）が知られている。【０００３】
アクセラレータを用いた関連技術の経路計算装置の構成を、図１０に示す。図１０を参照すると、アクセラレータを用いた経路計算装置は、ＧＰＵを制御するＧＰＵ制御ＣＰＵ１と、ＧＰＵボード６を備えている。ＧＰＵ制御ＣＰＵ１上では、ＧＰＵ制御プログラム１３が動作する。また、ＧＰＵ制御ＣＰＵ１とＧＰＵボード６とは、Ｉ／Ｏバス５で接続される。【０００４】
ＧＰＵボード６は、経路計算を行うＧＰＵ６１と、グラフデータ６２１を保持するＧＰＵメモリ６２を備えている。ＧＰＵ６１上では、経路計算を行う経路計算プログラム６１１が動作する。【０００５】
図１１は、ＧＰＵメモリ６２が保持するグラフデータ６２１を示す。ここでは、一例として、グラフデータ６２１は図４に示すグラフ４１に対応するデータとする。グラフデータ６２１は、グラフ上の各ノード間を接続するエッジ（辺）のコストを保持するエッジ距離配列Ｇ３１と、経路計算を行うスタートノードからグラフ上の全ノードまでの距離を保持するノード距離配列Ｇ３２と、ノード距離配列の更新値を保持するノード更新距離配列Ｇ３３と、各ノードのスタートノードからの最短経路において１つ前のノードを示す経路配列Ｇ３４と、経路計算において各ノードで距離の更新が行われたかどうかを示す更新配列Ｇ３５を保持する。エッジ距離配列Ｇ３１の要素数は、グラフ４１のエッジ数である。一方、ノード距離配列Ｇ３２、ノード更新距離配列Ｇ３３、経路配列Ｇ３４、および、更新配列Ｇ３５の要素数は、グラフ４１のノード数である。【０００６】
ＧＰＵ６１は、計算を行う複数のコア６１２を有する。ＧＰＵ６１は、複数のコア６１２を用いて並列に計算を行うことで、経路計算の高速化を実現する。【０００７】
関連技術の経路計算装置の動作について、図面を参照して説明する。ここでは、一例として、図４に示すグラフにおいて、ノードＡをスタートノードとしてグラフ上のすべてのノード（Ａ〜Ｉ）に対する距離と最短経路を求めるものとする。図１２は、経路計算装置の動作を一例として示すフロー図である。【０００８】
まず、ＧＰＵ制御プログラム１３は、ＧＰＵメモリ６２上のノード距離配列Ｇ３２において、スタートノードであるノードＡの距離を０（ゼロ）に初期化し、その他のノードＢ〜Ｉの距離を無限大に初期化する。また、ＧＰＵ制御プログラム１３は、更新配列Ｇ３５のスタートノードＡに対応する要素をセットする（ステップＳ３３）。【０００９】
次に、ＧＰＵ制御プログラム１３は、グラフの各ノードの経路計算を行うグラフノード数分のスレッドをＧＰＵ６１に生成する（ステップＳ３４）。【００１０】
生成されたスレッドはＧＰＵ６１の各コア６１２で動作し、そのスレッドが計算を担当するグラフのノードの更新配列Ｇ３５の要素がセットされているかどうかを確認し、セットされていれば、ノード距離配列Ｇ３２とエッジ距離配列Ｇ３１を参照し、担当するノードと隣接するノードのノード更新距離配列Ｇ３３の要素に、担当ノードのノード距離配列Ｇ３２の要素と、担当ノードと隣接するノードとを接続するエッジのエッジ距離配列Ｇ３１の要素との和を記憶する（ステップＳ３５）。【００１１】
次に、ＧＰＵ制御プログラム１３は、グラフの各ノードの距離情報と経路情報を更新するグラフノード数分のスレッドをＧＰＵ６１に生成する（ステップＳ３６）。【００１２】
生成されたスレッドは、そのスレッドが計算を担当するグラフのノード距離配列Ｇ３２とノード更新距離配列Ｇ３３とを参照し、ノード更新距離配列Ｇ３３の要素の方がノード距離配列Ｇ３２の要素より小さければ、ノード距離配列Ｇ３２の要素をノード更新距離配列Ｇ３３の要素の値を用いて更新する（ステップＳ３７）。【００１３】
また、スレッドは、更新を行った場合、担当するノードに対応する更新配列Ｇ３５の要素をセットする（ステップＳ３８）。さらに、スレッドは、更新した距離に対応する経路の１つ前のノードを経路配列Ｇ３４の要素に記憶する。【００１４】
次に、ＧＰＵ制御プログラム１３は、ステップＳ３８において更新配列Ｇ３５にセットされた要素が存在すれば（ステップＳ３９のＹｅｓ）、ステップＳ３４の処理に戻り、一方、セットされた要素が存在しなければ（ステップＳ３９のＮｏ）、すべてのノードに関してスタートノードＡからの最短距離と最短経路が求まったため、計算を完了する。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】P. Harish and P. J. Narayanan, “Accelerating Large Graph Algorithms on the GPU Using CUDA,” 14th International Conference, Goa, India, December 18-21, 2007, pp. 197-208.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【００１７】
上記関連技術の経路計算装置によると、アクセラレータを用いた経路計算を高速に行うことができないという問題がある。その理由は、誤った距離情報が先に伝搬して無駄な計算が発生したり、更新ノード数が少ない場合に計算を行わない無駄なスレッドを生成することによる、オーバヘッドが生じるからである。【００１８】
また、上記の関連技術の経路計算装置によると、複数のアクセラレータを用いた経路計算を高速に行うことができないという問題もある。その理由は、複数のアクセラレータ間で計算負荷を均一に分散することができないからである。【００１９】
そこで、アクセラレータを用いた経路計算を高速化することが要望される。本発明の目的は、かかる要望に寄与する経路計算装置、経路計算方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２０】
本発明の第１の視点に係る経路計算装置は、
与えられた処理を複数のスレッドを用いて並列に行う計算手段と、
前記計算手段を制御する制御手段と、を備え、
前記制御手段は、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類し、前記計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる。【００２１】
本発明の第２の視点に係る経路計算装置は、
与えられた処理を複数のスレッドを用いて並列に行う計算手段と、
前記計算手段を制御する制御手段と、を備え、
前記制御手段は、経路計算対象のグラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる。【００２２】
本発明の第３の視点に係る経路計算方法は、
与えられた処理を複数のスレッドを用いて並列に行う計算手段を制御する制御手段が、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類する工程と、
前記計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる工程と、を含む。【００２３】
本発明の第４の視点に係るプログラムは、
与えられた処理を複数のスレッドを用いて並列に行う計算手段を制御するコンピュータに対して、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類する処理と、
前記計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる処理と、を実行させる。
なお、プログラムは、非一時的なコンピュータ可読記録媒体（non-transitory computer-readable storage medium）に記録されたプログラム製品として提供することができる。
【発明の効果】
【００２４】
本発明に係る経路計算装置、経路計算方法およびプログラムによると、アクセラレータを用いた経路計算を高速化することが可能となる。
【図面の簡単な説明】
【００２５】
【図１】一実施形態に係る経路計算装置の構成を一例として示すブロック図である。
【図２】第１の実施形態に係る経路計算装置の構成を一例として示すブロック図である。
【図３】第１の実施形態に係る経路計算装置が有するグラフデータの構成を一例として示す図である。
【図４】第１の実施形態に係る経路計算装置の動作を説明するための図である。
【図５】第１の実施形態に係る経路計算装置の動作を一例として示すフロー図である。
【図６】第２の実施形態に係る経路計算装置の構成を一例として示すブロック図である。
【図７】第２の実施形態を係る経路計算装置が有するグラフデータを一例として示す図である。
【図８】第２の実施形態に係る経路計算装置の動作を説明するための図である。
【図９】第２の実施形態に係る経路計算装置の動作を一例として示すフロー図である。
【図１０】関連技術の経路計算装置の構成を一例として示すブロック図である。
【図１１】関連技術の経路計算装置が有するグラフデータの構成を一例として示す図である。
【図１２】関連技術の経路計算装置の動作を一例として示すフロー図である。
【発明を実施するための形態】
【００２６】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００２７】
図１を参照すると、一実施形態に係る経路計算装置１００は、与えられた処理を複数のスレッドを用いて並列に行う計算手段２０と、計算手段２０を制御する制御手段１０とを備えている。制御手段１０は、経路計算対象のグラフに含まれるノードをスタートノードからの距離に応じてグループに分類する。一例として、制御手段１０は、グラフに含まれるノードをスタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類するようにしてもよい。また、制御手段１０は、計算手段２０に対して、スタートノードからの距離が相対的に短いノードのグループに属するノードとスタートノードとの間の経路計算の後、スタートノードからの距離が相対的に長いノードのグループに属するノードとスタートノードとの間の経路計算を行わせる。
【００２８】
さらに、制御手段１０は、グラフに含まれるノードのうちのスタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、計算手段２０に対して、グラフに含まれるすべてのノードのスタートノードからの距離を更新するスレッドを生成させるか、または、スタートノードからの距離が更新される可能性があるノードのスタートノードからの距離を更新するスレッドを生成させるようにしてもよい。
【００２９】
かかる構成によると、誤った経路情報が先に伝搬し、無駄な計算が発生することに関するオーバヘッドの発生を防ぐことができる。また、情報を更新しない無駄なスレッドの生成によるオーバヘッドが生じることも防ぐことができる。すなわち、かかる構成によると、誤った距離情報が先に伝搬して無駄な計算が発生するオーバヘッドの発生を防ぐとともに、更新ノード数が少ない場合に計算を行わない無駄なスレッドを生成するオーバヘッドを防ぐことが可能になる。したがって、一実施形態に係る経路計算装置によると、アクセラレータを用いた経路計算を高速に行うことが可能となる。
【００３０】
＜実施形態１＞
次に、第１の実施形態に係る経路計算装置について、図面を参照して詳細に説明する。図２を参照すると、本実施形態の経路計算装置は、ＧＰＵを制御するＧＰＵ制御ＣＰＵ１と、ＧＰＵボード３を備えている。
【００３１】
ＧＰＵ制御ＣＰＵ１上では、ＧＰＵ制御プログラム１１が動作する。また、ＧＰＵ制御ＣＰＵ１とＧＰＵボード３とは、Ｉ／Ｏバス２で接続されている。ＧＰＵ制御プログラム１１は、起動時の入力値として経路計算のステップで用いるパラメータΔ（デルタ）を受け取る。
【００３２】
ＧＰＵボード３は、経路計算を行うＧＰＵ３１と、グラフデータ３２１を保持するＧＰＵメモリ３２を備えている。ＧＰＵ３１上では、経路計算を行う経路計算プログラム３１１が動作する。
【００３３】
ＧＰＵメモリ３２が保持するグラフデータ３２１を図３に示す。ここでは、一例として、グラフデータ３２１は、図４に示すグラフ４１に対応するデータとする。グラフデータ３２１は、グラフ上の各ノード間のエッジのコストを保持するエッジ距離配列Ｇ１１と、経路計算を行うスタートノードからグラフ上の全ノードまでの距離を保持するノード距離配列Ｇ１２と、ノード距離配列の更新値を保持するノード更新距離配列Ｇ１３と、各ノードの現在のバケット番号を保持するバケット配列Ｇ１４と、各ノードのスタートノードからの最短経路において１つ前のノードを示す経路配列Ｇ１５と、経路計算において各ノードで距離の更新が行われたかどうかを示す更新配列Ｇ１６を保持する。
【００３４】
エッジ距離配列Ｇ１１の要素数はグラフ４１のエッジ数であり、ノード距離配列Ｇ１２、ノード更新距離配列Ｇ１３、バケット配列Ｇ１４、経路配列Ｇ１５、および、更新配列Ｇ１６の要素数はグラフ４１のノード数である。
【００３５】
ＧＰＵ３１は、計算を行う複数のコア３１２を備えている。ＧＰＵ３１は、複数のコア３１２を用いて並列に計算を行うことで経路計算の高速化を実現する。
【００３６】
かかる構成を有する第１の実施形態の動作を、図面を用いて説明する。図５は、第１の実施形態に係る経路計算装置の動作を一例として示すフロー図である。ここでは、図４のグラフ４１においてノードＡをスタートとしてグラフ上のすべてのノード（Ａ〜Ｉ）に対する距離と最短経路を求めるものとする。
【００３７】
まず、ＧＰＵ制御プログラム１１は、ＧＰＵメモリ３２上のノード距離配列Ｇ１２において、スタートノードＡの距離を０（ゼロ）に初期化し、その他のノードＢ〜Ｉの距離を無限大に初期化する。また、ＧＰＵ制御プログラム１１は、バケット配列Ｇ１４のスタートノードＡに対応する要素を０（ゼロ）に初期化し、その他のノードを無限大に初期化する（ステップＳ１）。
【００３８】
次に、ＧＰＵ制御プログラム１１は、経路計算プログラム３１１において、グラフの各ノードの経路計算を行うグラフノード数分のスレッドをＧＰＵ３１に生成する。また、スレッドには、現在計算しているバケット番号が渡される（ステップＳ２）。ここで、最初の計算では、バケット番号は０（ゼロ）である。
【００３９】
生成されたスレッドは、ＧＰＵ３１の各コア３１２で動作し、そのスレッドが計算を担当するグラフのノードのバケット配列Ｇ１４の要素を参照し、その値がスレッド起動時にＧＰＵ制御プログラム１１から渡された値と一致するかどうかを確認し、一致すれば、ノード距離配列Ｇ１２とエッジ距離配列Ｇ１１を参照し、隣接するノードのノード更新距離配列Ｇ１３の要素に、担当ノードのノード距離配列Ｇ１２の要素と、担当ノードと隣接するノードとを接続するエッジのエッジ距離配列Ｇ１１の要素との和を記憶する（ステップＳ３）。
【００４０】
次に、ＧＰＵ制御プログラム１１は、経路計算プログラム３１１において、グラフの各ノードの距離情報と経路情報を更新するグラフノード数分のスレッドをＧＰＵ３１に生成する（ステップＳ４）。このとき、生成されたスレッドには、現在計算しているバケット番号と、ＧＰＵ制御プログラム１１の起動時に渡されたΔが渡される。
【００４１】
生成されたスレッドは、そのスレッドが計算を担当するグラフのノード距離配列Ｇ１２の要素とノード更新距離配列Ｇ１３の要素とを参照し、ノード更新距離配列Ｇ１３の要素の方がノード距離配列Ｇ１２の要素より小さければ、ノード距離配列Ｇ１２をノード更新距離配列Ｇ１３の要素の値を用いて更新する。また、スレッドは、更新した距離に対応する経路の１つ前のノードを経路配列Ｇ１５の要素に記憶する。さらに、スレッドは、更新した値をΔで除した値の整数部分を新たなバケット値として更新したノードに対応するバケット配列Ｇ１４の要素に記憶する（ステップＳ５）。
【００４２】
ここで、スレッドは、記憶したバケット配列Ｇ１４の値が現在計算を行っているバケット値と一致した場合、更新を行ったノードに対応する更新配列Ｇ１６の要素をセットする（ステップＳ６）。
【００４３】
次に、ＧＰＵ制御プログラム１１は、ステップＳ２またはＳ４で生成したスレッドが担当するグラフノードのすべてにおいて、現在計算しているバケット番号以上のノードが存在しないと通知を受けた場合（ステップＳ７のＹｅｓ）、経路計算の完了を意味するため、経路計算を完了する。
【００４４】
また、ＧＰＵ制御プログラム１１は、ステップＳ６において更新配列Ｇ１６にセットされた要素が存在しなければ（ステップＳ９のＮｏ）、計算するバケットを１増加し（ステップＳ８）、ステップＳ２の処理に戻る。
【００４５】
一方、ＧＰＵ制御プログラム１１は、更新配列Ｇ１６がセットされた要素が存在すれば（ステップＳ９のＹｅｓ）、同じバケット内のノード距離を更新するステップＳ１０の処理に移る。
【００４６】
ステップＳ１０では、ＧＰＵ制御プログラム１１は、経路計算プログラム３１１においてグラフの各ノードの経路計算を行うグラフノード数分のスレッドをＧＰＵ３１に生成する。
【００４７】
生成されたスレッドは、ＧＰＵ３１の各コア３１２で動作し、そのスレッドが計算を担当するグラフのノードの更新配列Ｇ１６の要素を参照し、その要素がセットされていればノード距離配列Ｇ１２とエッジ距離配列Ｇ１１を参照し、隣接するノードのノード更新配列の要素に、担当ノードのノード距離配列Ｇ１２の要素と、担当ノードと隣接するノードとを接続するエッジのエッジ距離配列Ｇ１１の要素との和を記憶する（ステップＳ１１）。
【００４８】
次に、ＧＰＵ制御プログラム１１は、経路計算プログラム３１１においてグラフの各ノードの距離情報と経路情報を更新するグラフノード数分のスレッドをＧＰＵ３１に生成する（ステップＳ１２）。
【００４９】
このとき、生成されたスレッドには、現在計算しているバケット番号と、ＧＰＵ制御プログラム１１の起動時に渡されたΔが渡される。生成されたスレッドは、そのスレッドが計算を担当するグラフのノード距離配列Ｇ１２とノード更新距離配列Ｇ１３とを参照し、ノード更新距離配列Ｇ１３の要素の方がノード距離配列Ｇ１２の要素より小さければ、ノード距離配列Ｇ１２の要素をノード更新距離配列Ｇ１３の要素の値を用いて更新する。また、スレッドは、更新した距離に対応する経路の１つ前のノードを経路配列Ｇ１５の要素に記憶する。さらに、スレッドは、更新した値をΔで除した値の整数部分を新たなバケット値として更新したノードに対応するバケット配列Ｇ１４の要素に記憶する（ステップＳ１３）。
【００５０】
ここで、スレッドは、記憶したバケット配列Ｇ１４の値が現在計算を行っているバケット値と一致した場合、更新を行ったノードに対応する更新配列Ｇ１６の要素をセットする（ステップＳ１４）。
【００５１】
次に、ＧＰＵ制御プログラム１１は、ステップＳ１４でセットされた更新配列Ｇ１６の要素が存在すれば（ステップＳ１５のＹｅｓ）、ステップＳ１０の動作に戻り、一方、存在しなければ（ステップＳ１５のＮｏ）、バケット番号を１増加し（ステップＳ８）、ステップＳ２の動作に戻る。
【００５２】
以上のように、本実施形態では、ＧＰＵ制御プログラム１１は、経路計算を行うノードをスタートノードからの距離に依存して起動時に渡されたパラメータΔ（デルタ）の整数倍毎のグループに分類し、同一グループの経路計算を並列に実行し、次のグループの経路計算は前のグループが完了した後に行う。また、同一グループ内の計算では、距離を更新するノード数に依存してグラフ上の全ノードを計算するスレッドを生成するか、更新するノードに限定してスレッドを生成するかを選択する。
【００５３】
かかる構成によると、スタートノードからの最短距離と経路に関する計算において、情報を更新するノードをバケット内に限定し、そのノードに対して並列計算を行うことにより、正しくない最短距離と経路情報が現在計算しているバケットよりも遠いノードに先に伝搬してそれらに関する無駄な計算が生じることを防ぎ、経路計算時間を削減することができる。特に、本実施形態によると、グラフ上の１点からグラフ上のすべての点への最短経路と距離を高速に求めることができるアクセラレータを用いた経路計算装置が提供される。
【００５４】
＜実施形態２＞
次に、第２の実施形態に係る経路計算装置について、図面を参照して説明する。本実施形態の経路計算装置では、複数のＧＰＵを用いて１つのグラフの経路計算を行う。図６を参照すると、本実施形態の経路計算装置は、計算を行うＧＰＵとしてＧＰＵボード３ＡおよびＧＰＵボード３Ｂを備えている。
【００５５】
以後、ＡやＢは複数のＧＰＵボードを区別するための添え字である。また、本説明では便宜上２つのＧＰＵを用いる場合を説明するが、本発明は２つのＧＰＵのみならず、３つ以上のＧＰＵを用いる場合にも適用可能である。
【００５６】
図６を参照すると、本実施形態の経路計算装置は、ＧＰＵを制御するＧＰＵ制御ＣＰＵ１と、ＧＰＵボード３ＡおよびＧＰＵボード３Ｂを備えている。以下、ＧＰＵ３ＡとＧＰＵ３Ｂに関して説明が同一となる場合、または、ＧＰＵ３Ｂの動作がＧＰＵ３Ａの動作と同様である場合、ＧＰＵ３Ｂについての説明を省略する。
【００５７】
ＧＰＵ制御ＣＰＵ１上では、ＧＰＵ制御プログラム１２が動作する。また、ＧＰＵ制御ＣＰＵ１とＧＰＵボード３Ａとは、Ｉ／Ｏバス２Ａで接続されている。ＧＰＵ制御プログラム１２は、起動時の入力値として経路計算のステップで用いるパラメータΔ（デルタ）を受け取る。
【００５８】
ＧＰＵボード３Ａは、経路計算を行うＧＰＵ３１Ａと、グラフデータ３２２Ａを保持するＧＰＵメモリ３２Ａを備えている。
【００５９】
ＧＰＵ３１Ａ上では、経路計算を行う経路計算プログラム３１３Ａが動作する。
【００６０】
ＧＰＵメモリ３２Ａが保持するグラフデータ３２２Ａを図７に示す。ここでは、一例として、グラフデータ３２２Ａは、図８に示すグラフ４２に対応するデータとする。ここで、グラフ４２に関するデータは、各ＧＰＵに分割して保持されている。
【００６１】
ここで、グラフをＧＰＵ数と同数の領域に分割し、単純に１つのＧＰＵに対し１つの領域を振り分けると、経路計算ではスタートノードに近い方から距離情報が更新されるため、経路計算の初期ではスタートノードに近い領域を割り当てられたＧＰＵのみが計算を行うなど、処理の負荷が不均一となる。そこで、本実施形態では、グラフ４２をＧＰＵ数以上の領域に分割し、各領域をランダムにＧＰＵに割り当てる。
【００６２】
図８のグラフ４２は４つの領域に分割され、各領域がＧＰＵ３１ＡかＧＰＵ３１Ｂにランダムに割り当てられている。ここで、グラフデータ３２２Ａは、ＧＰＵ３１Ａが担当するグラフの領域に関するノードに加え、領域を跨ぐエッジに関する情報と、領域を跨ぐエッジによって接続するＧＰＵ３１Ｂが担当するノードに関する情報とを保持する。
【００６３】
グラフデータ３２２Ａは、担当するグラフ領域上の各ノード間のエッジと境界を跨ぐエッジのコストを保持するエッジ距離配列Ｇ２１Ａと、グラフの担当ノードからスタートノードまでの距離を保持するノード距離配列Ｇ２２Ａと、ノード距離配列Ｇ２２Ａの更新値を保持するノード更新距離配列Ｇ２３Ａとを保持する。
【００６４】
ここで、ノード更新距離配列Ｇ２３Ａは、ＧＰＵ３１Ａが担当するグラフノードの要素数に加え、担当するグラフノードの中でＧＰＵ３１Ｂが担当するノードとエッジで接続するノードに関しては、ＧＰＵ３１Ｂからの更新値を記憶するための要素を保持する。また、ノード更新距離配列Ｇ２３Ａは、担当するグラフノードがエッジで接続するＧＰＵ３１Ｂが担当するノードの更新値を記憶するための要素も保持する。
【００６５】
また、グラフデータ３２２Ａは、担当するグラフノードの現在のバケット番号を保持するバケット配列Ｇ２４Ａと、担当する各ノードのスタートノードからの最短経路において１つ前のノードを示す経路配列Ｇ２５Ａと、経路計算において担当する各ノードで距離の更新が行われたかを示す更新配列Ｇ２６Ａを保持する。
【００６６】
エッジ距離配列Ｇ２１Ａの要素数は、ＧＰＵ３１Ａが担当するグラフ領域および担当する領域の境界を跨ぐエッジ数の総和である。一方、ノード距離配列Ｇ２２Ａの要素数は、ＧＰＵ３１Ａが担当するグラフ領域のノード数と、ＧＰＵ３１Ｂからの更新値を記憶するための要素に対応するＧＰＵ３１Ａが担当するノードの中でＧＰＵ３１Ｂが担当するノードとエッジで接続されているノード数と、ＧＰＵ３１Ｂが担当するノードへの更新値を記録するための要素に対応するＧＰＵ３１Ｂが担当するノードの中でＧＰＵ３１Ａが担当するノードとエッジで接続されているノード数の総和である。また、ノード更新距離配列Ｇ２３Ａ、バケット配列Ｇ２４Ａ、経路配列Ｇ２５Ａ、および、更新配列Ｇ２６Ａの要素数は、ＧＰＵ３１Ａが担当するグラフ４２のノード数である。
【００６７】
ＧＰＵ３１Ａは、計算を行う複数のコア３１２Ａを備えている。ＧＰＵ３１Ａは、複数のコア３１２Ａを用いて並列に計算を行うことで、経路計算の高速化を実現する。
【００６８】
かかる構成を有する第２の実施形態の動作を、図面を用いて説明する。図９は、第２の実施形態の動作を一例として示すフロー図である。ここでは、一例として、図８のグラフにおいてノードＡをスタートノードとしてグラフ上のすべてのノード（Ａ〜Ｒ）に対する距離と最短経路を求めるものとする。
【００６９】
まず、ＧＰＵ制御プログラム１２は、ＧＰＵメモリ３２ＡとＧＰＵメモリ３２Ｂに記憶されているノード距離配列Ｇ２２Ａおよびノード距離配列Ｇ２２Ｂにおいて、スタートノードＡの距離を０（ゼロ）に初期化し、その他のノードＢ〜Ｒの距離を無限大に初期化する。また、ＧＰＵ制御プログラム１２は、バケット配列Ｇ２４Ａおよびバケット配列Ｇ２４ＢのスタートノードＡに対応する要素を０（ゼロ）に初期化し、その他のノードを無限大に初期化する（ステップＳ１６）。
【００７０】
次に、ＧＰＵ制御プログラム１２は、経路計算プログラム３１３Ａおよび経路計算プログラム３１３Ｂにおいて、グラフの各ノードの経路計算を行うグラフノード数分のスレッドをＧＰＵ３１ＡおよびＧＰＵ３１Ｂに生成する。ここで、ＧＰＵ３１Ａに生成されるスレッド数は、ＧＰＵ３１Ａが担当するグラフの領域のノード数である。生成されたスレッドには、現在計算しているバケット番号が渡される（ステップＳ１７）。
【００７１】
以下、ＧＰＵ３１ＡとＧＰＵ３１Ｂに関して説明が重複する場合、ＧＰＵ３１Ａに関してのみ説明し、ＧＰＵ３１Ｂに関する説明を省略する。
【００７２】
ここで、最初の計算ではバケット番号は０（ゼロ）である。生成されたスレッドはＧＰＵ３１Ａの各コア３１２Ａで動作し、そのスレッドが計算を担当するグラフのノードのバケット配列Ｇ２４Ａを参照し、その値がスレッド起動時にＧＰＵ制御プログラム１２から渡された値と一致するか確認し、一致すればノード距離配列Ｇ２２Ａとエッジ距離配列Ｇ２１Ａを参照し、隣接するノードのノード更新配列の要素に、担当ノードのノード距離配列Ｇ２２Ａの要素と、担当ノードと隣接するノードとを接続するエッジのエッジ距離配列Ｇ２１Ａの要素との和を記憶する（ステップＳ１８）。
【００７３】
次に、ＧＰＵ制御プログラム１２は、各グラフボードが計算した更新情報で、境界ノードに関する情報をグラフボード間で交換する。ＧＰＵボード３ＡからＧＰＵボード３Ｂに移動する情報に関しては、ノード更新距離配列Ｇ２３Ａの中で、ＧＰＵ３１Ｂが担当するグラフのノードに対応する要素をグラフデータ３２２Ｂが保持するノード更新距離配列Ｇ２３Ｂ（図示しない）が保持するＧＰＵ３１Ａの更新情報の登録のための要素に記憶する（ステップＳ１９）。
【００７４】
次に、ＧＰＵ制御プログラム１２は、経路計算プログラム３１３ＡにおいてＧＰＵ３１Ａが担当するグラフのノードの距離情報と経路情報を更新する担当ノード数分のスレッドをＧＰＵ３１Ａに生成する（ステップＳ２０）（ＧＰＵボード３Ｂに関しても同様）。このとき、生成されるスレッドには、現在計算しているバケット番号と、ＧＰＵ制御プログラム１２の起動時に渡されたΔが渡される。
【００７５】
生成されたスレッドは、そのスレッドが計算を担当するグラフのノード距離配列Ｇ２２Ａとノード更新距離配列Ｇ２３Ａとを参照し、ノード更新距離配列Ｇ２３Ａの要素の方がノード距離配列Ｇ２２Ａの要素より小さければ、ノード距離配列Ｇ２２Ａの要素をノード更新距離配列Ｇ２３Ａの要素の値を用いて更新する。このとき、スレッドは、ＧＰＵ３１Ｂが担当するノードとエッジで接続するノードに関しては、ステップＳ１８でＧＰＵ３１Ａが記憶したノード更新距離配列Ｇ２３Ａの要素と、ステップＳ１９で記憶されたＧＰＵ３１Ｂが記憶した要素の両方を参照して小さい値を選択する。また、経路計算プログラム３１３Ａは、更新した距離に対応する経路の１つ前のノードを経路配列Ｇ２５Ａの要素に記憶する。さらに、更新した値をΔで除した値の整数部分を新たなバケット値として更新したノードに対応するバケット配列Ｇ２４Ａの要素に記憶する（ステップＳ２１）。
【００７６】
ここで、記憶したバケット配列Ｇ２４Ａの値が現在計算を行っているバケット値と一致した場合、更新を行ったノードに対応する更新配列Ｇ２６Ａの要素をセットする（ステップＳ２２）。
【００７７】
次に、ＧＰＵ制御プログラム１２は、ステップＳ１７またはステップＳ２０で生成した経路計算プログラム３１３Ａと３１３Ｂの処理を行うすべてのスレッドが担当するグラフノードにおいて、現在計算しているバケット番号以上のノードが存在しない通知を受けた場合（ステップＳ２３のＹｅｓ）、経路計算の完了を意味するため、経路計算を完了する。
【００７８】
また、ＧＰＵ制御プログラム１２は、ステップＳ２２において更新配列Ｇ２６Ａにセットされた要素が存在しなければ（ステップＳ２４のＮｏ）、計算するバケットを１増加し（ステップＳ２５）、ステップＳ１７の処理に戻る。
【００７９】
一方、更新配列Ｇ２６Ａがセットされた要素が存在すれば（ステップＳ２４のＹｅｓ）、同一のバケット内のノード距離を更新するステップＳ２６の処理に移る。ここで、ステップＳ２４では、更新配列Ｇ２６Ａと更新配列Ｇ２６Ｂのいずれかの要素にセットされていればＹｅｓと判定され、ステップＳ２６に移る。
【００８０】
ステップＳ２６では、ＧＰＵ制御プログラム１２は、ＧＰＵ３１Ａが担当するノードの経路計算を行う担当領域のノード数分のスレッドをＧＰＵ３１Ａに生成し、経路計算プログラム３１３Ａを行わせる（ステップＳ２６）（ＧＰＵボード３Ｂについても同様）。生成された経路計算プログラム３１３Ａのスレッドは、ＧＰＵ３１Ａの各コア３１２Ａで動作する。
【００８１】
経路計算プログラム３１３Ａは、計算を担当するグラフのノードの更新配列Ｇ２６Ａの要素を参照し、その要素がセットされていればノード距離配列Ｇ２２Ａとエッジ距離配列Ｇ２１Ａを参照し、隣接するノードのノード更新距離配列Ｇ２３Ａの要素に、担当ノードのノード距離配列Ｇ２２Ａの要素と、担当ノードと隣接するノードとを接続するエッジのエッジ距離配列Ｇ２１Ａの要素との和を記憶する（ステップＳ２７）。
【００８２】
次に、ＧＰＵ制御プログラム１２は、各グラフボードが計算した更新情報で、境界ノードに関する情報をグラフボード間で交換する（ステップＳ２８）。ＧＰＵボード３ＡからＧＰＵボード３Ｂに移動する情報は、ノード更新距離配列Ｇ２３Ａの中で、ＧＰＵ３１Ｂが担当するグラフのノードに対応する要素である。このデータは、グラフデータ３２２Ｂが保持するノード更新距離配列Ｇ２３Ｂの要素の中で、ＧＰＵ３１Ａによる更新情報の登録のための要素に記憶する。
【００８３】
次に、ＧＰＵ制御プログラム１２は、ＧＰＵ３１Ａが担当するグラフの各ノードの距離情報と経路情報を更新する経路計算プログラム３１３Ａの処理を行うノード数分のスレッドをＧＰＵ３１Ａに生成する（ステップＳ２９）。このとき、生成されたスレッドには、現在計算しているバケット番号と、ＧＰＵ制御プログラム１２が起動時に渡されたΔが渡される。
【００８４】
生成された経路計算プログラム３１３Ａの各スレッドは、計算を担当するグラフのノード距離配列Ｇ２２Ａとノード更新距離配列Ｇ２３Ａとを参照し、ノード更新距離配列Ｇ２３Ａの要素の方がノード距離配列Ｇ２２Ａの要素より小さければ、ノード距離配列Ｇ２２Ａの要素をノード更新距離配列Ｇ２３Ａの要素の値を用いて更新する。このとき、スレッドは、ＧＰＵ３１Ｂが担当するノードとエッジで接続するノードに関しては、ステップＳ２７においてＧＰＵ３１Ａが記憶したノード更新距離配列Ｇ２３Ａの要素と、ステップＳ２８で記憶されたＧＰＵ３１Ｂが記憶した要素の両方を参照して小さい値を選択する必要がある。また、スレッドは、更新した距離に対応する経路の１つ前のノードを経路配列Ｇ２５Ａの要素に記憶する。さらに、スレッドは、更新した値をΔで除した値の整数部分を新たなバケット値として更新したノードに対応するバケット配列Ｇ２４Ａの要素に記憶する（ステップＳ３０）。
【００８５】
ここで、スレッドは、記憶したバケット配列Ｇ２４Ａの値が現在計算を行っているバケット値と一致した場合、更新を行ったノードに対応する更新配列Ｇ２６Ａの要素をセットする（ステップＳ３１）。
【００８６】
次に、ＧＰＵ制御プログラム１２は、ステップＳ３１でセットされた要素が更新配列Ｇ２６Ａと更新配列Ｇ２６Ｂのいずれかにおいて存在すれば（ステップＳ３２のＹｅｓ）、ステップＳ２６の動作に戻り、一方、存在しなければ（ステップＳ３２のＮｏ）、バケット番号を１増加し（ステップＳ２５）、ステップＳ１７の動作に戻る。
【００８７】
かかる構成を採用し、第２の実施形態は、スタートノードからの最短距離と経路に関する計算において、情報を更新するノードをバケット内に限定し、そのノードに対して並列計算を行うことにより、正しくない最短距離と経路情報が現在計算しているバケットより遠いノードに先に伝搬して、それらに関する無駄な計算が生じることを防ぎ、経路計算時間を削減することができる。
【００８８】
また、第２の実施形態は、グラフの領域を計算を行うＧＰＵ数以上に分割し、各領域を複数のＧＰＵに対してランダムに割り当てることで、経路計算に関する計算負荷を複数のＧＰＵ間で均一に配分することで経路計算時間をさらに削減することができる。
【００８９】
すなわち、本実施形態によると、複数のアクセラレータの間で計算処理の負荷を均一化できるため、複数のアクセラレータを用いた経路計算において、計算を高速に行うことが可能となる。
【００９０】
＜実施形態３＞
次に、第３の実施形態に係る経路計算装置について説明する。第１および第２の実施形態では、ステップＳ１０およびステップＳ２６においてグラフ上のすべてのノードを計算するスレッドを生成したが、距離情報を更新する可能性があるグラフ上のノードに対応するスレッドのみを生成することも可能である。
【００９１】
この場合、ステップＳ６、ステップＳ１４、ステップＳ２２、および、ステップＳ３１でセットされる更新配列の要素番号と要素数を記録し、次のステップＳ１０およびステップＳ２６で生成するスレッドを、更新配列がセットされたノードに関するスレッドだけに限定する。
【００９２】
これにより、ステップＳ１０およびステップＳ２６において距離情報の更新が発生しないグラフ上のノードにもスレッドが生成されることに関するオーバヘッドを削減することができる。
【００９３】
＜実施形態４＞
次に、第４の実施形態に係る経路計算装置について説明する。
【００９４】
第３の実施形態では、距離情報が更新されるグラフ上のノードに関してのみスレッドを生成したが、ステップＳ１０およびステップＳ２６において、更新ノード数が一定数以上の場合、グラフの全ノードに対応するスレッドを生成し、それ以外の場合、更新するノードに対応するスレッドのみを生成する組み合わせも可能である。
【００９５】
また、更新ノード数の測定には、ステップＳ６、ステップＳ１４、ステップＳ２２、およびステップＳ３１でセットされる更新配列の要素数を数えることにより実現できる。
【００９６】
また、別の方法として、例えば、ステップＳ１０の処理がステップＳ１５のＹｅｓ判定により繰り返し行われる場合、前回のステップＳ１０〜ステップＳ１４の処理に要した合計時間から、今回の処理で更新されるグラフ上のノード数を予測することができる。
【００９７】
例えば、前回のステップＳ１０〜ステップＳ１４の合計処理時間がしきい値で定めた時間以上の場合、今回の計算では一定数以上のノードの更新が行われると予測し、ステップＳ１０ではグラフ上の全ノードを計算するスレッドを生成する。一方、前回のステップＳ１０〜ステップＳ１４の処理に要した合計時間がしきい値で定めた時間以下の場合、今回の計算では一定数以下のノードの更新が行われることを予測し、更新が行われるグラフ上のノードに対応するスレッドのみを生成する。
【００９８】
これにより、更新ノード数が多い場合、更新ノード数を数える処理に関するオーバヘッドを削減することができる。
【００９９】
なお、これまでの実施形態の説明において、アクセラレータとしてＧＰＵを用いる手法を説明したが、例えばIntel社のXeon Phiなど、複数の計算コアを持つその他のアクセラレータを用いることも可能である。
【０１００】
本発明によれば、経路計算を行うコンピュータや、経路計算を行うコンピュータを実現するためのプログラムといった用途に適用できる。また、インターネットを通して、経路計算を行うサービスやそのサービスを実現するためのプログラムといった用途に適用できる。また、ナビゲーションを行う装置やその装置を実現するためのプログラムといった用途に適用できる。
【０１０１】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の視点に係る経路計算装置のとおりである。
［形態２］
前記制御手段は、前記グラフに含まれるノードを前記スタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、形態１に記載の経路計算装置。
［形態３］
前記制御手段は、前記グラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる、形態１または２に記載の経路計算装置。
［形態４］
前記制御手段は、前記スタートノードからの距離が更新されるノードの数を、前回の更新処理に要した処理時間に基づいて予測する、形態３に記載の経路計算装置。
［形態５］
複数の前記計算手段を備え、
前記制御手段は、前記グラフを前記複数の計算手段の数よりも大きい数で複数の領域に分割し、前記複数の計算手段に対して、前記複数の領域をランダムに割り当て、割り当てられた領域に含まれるノードと前記スタートノードとの間の経路計算を行わせる、形態１ないし４のいずれか一に記載の経路計算装置。
［形態６］
前記制御手段は、前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じてグループに分類し、前記複数の計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる、形態５に記載の経路計算装置。
［形態７］
前記制御手段は、前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、形態６に記載の経路計算装置。
［形態８］
前記制御手段は、前記複数の計算手段に対して、経路計算の途中で、割り当てられた領域に含まれるノードの前記スタートノードからの距離が更新されたかどうかを示す情報を交換させる、形態５ないし７のいずれか一に記載の経路計算装置。
［形態９］
前記制御手段は、前記複数の計算手段に対して、割り当てられた領域に含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、割り当てられた領域に含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる、形態５ないし８のいずれか一に記載の経路計算装置。
［形態１０］
前記制御手段は、割り当てられた領域に含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数を、前回の更新処理に要した処理時間に基づいて予測する、形態９に記載の経路計算装置。
［形態１１］
上記第３の視点に係る経路計算方法のとおりである。
［形態１２］
前記制御手段は、前記グラフに含まれるノードを前記スタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、形態１１に記載の経路計算方法。
［形態１３］
前記制御手段が、前記グラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる工程を含む、形態１１または１２に記載の経路計算方法。
［形態１４］
前記制御手段が、複数の前記計算手段を制御する工程と、
前記グラフを前記複数の計算手段の数よりも大きい数で複数の領域に分割する工程と、
前記複数の計算手段に対して、前記複数の領域をランダムに割り当て、割り当てられた領域に含まれるノードと前記スタートノードとの間の経路計算を行わせる工程と、を含む、形態１１ないし１３のいずれか一に記載の経路計算方法。
［形態１５］
前記制御手段が、前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じてグループに分類する工程と、
前記複数の計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる工程と、を含む、形態１４に記載の経路計算方法。
［形態１６］
前記制御手段が、前記複数の計算手段に対して、経路計算の途中で、割り当てられた領域に含まれるノードの前記スタートノードからの距離が更新されたかどうかを示す情報を交換させる工程を含む、形態１４または１５に記載の経路計算方法。
［形態１７］
上記第４の視点に係るプログラムのとおりである。
［形態１８］
前記グラフに含まれるノードを前記スタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する処理を、前記コンピュータに実行させる、形態１７に記載のプログラム。
［形態１９］
前記グラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる処理を、前記コンピュータに実行させる、形態１７または１８に記載のプログラム。
［形態２０］
複数の前記計算手段を制御する処理と、
前記グラフを前記複数の計算手段の数よりも大きい数で複数の領域に分割する処理と、
前記複数の計算手段に対して、前記複数の領域をランダムに割り当て、割り当てられた領域に含まれるノードと前記スタートノードとの間の経路計算を行わせる処理と、を前記コンピュータに実行させる、形態１７ないし１９のいずれか一に記載のプログラム。
［形態２１］
前記複数の領域のそれぞれに含まれるノードをスタートノードからの距離に応じてグループに分類する処理と、
前記複数の計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる処理と、を前記コンピュータに実行させる、形態２０に記載のプログラム。
［形態２２］
前記複数の計算手段に対して、経路計算の途中で、割り当てられた領域に含まれるノードの前記スタートノードからの距離が更新されたかどうかを示す情報を交換させる処理を、前記コンピュータに実行させる、形態２０または２１に記載のプログラム。
［形態２３］
上記第２の視点に係る経路計算装置のとおりである。
［形態２４］
前記制御手段は、前記グラフに含まれる各ノードをスタートノードからの距離に応じてグループに分類し、前記計算手段に対して、前記スタートノードからの距離が相対的に短いノードのグループに属するノードと前記スタートノードとの間の経路計算の後、前記スタートノードからの距離が相対的に長いノードのグループに属するノードと前記スタートノードとの間の経路計算を行わせる、形態２３に記載の経路計算装置。
［形態２５］
前記制御手段は、前記グラフに含まれるノードを前記スタートノードからの距離に応じて所定のパラメータの整数倍毎に異なるグループに分類する、形態２４に記載の経路計算装置。
［形態２６］
前記制御手段は、前記スタートノードからの距離が更新されるノードの数を、前回の更新処理に要した処理時間に基づいて予測する、形態２３ないし２５のいずれか一に記載の経路計算装置。
［形態２７］
制御手段が、与えられた処理を複数のスレッドを用いて並列に行う計算手段を制御する工程と、
経路計算対象のグラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる工程と、を含む、経路計算方法。
［形態２８］
与えられた処理を複数のスレッドを用いて並列に行う計算手段を制御する処理と、
経路計算対象のグラフに含まれるノードのうちの前記スタートノードからの距離が更新されるノードの数が所定の数以上であるか否かに応じて、前記計算手段に対して、前記グラフに含まれるすべてのノードの前記スタートノードからの距離を更新するスレッドを生成させるか、または、前記スタートノードからの距離が更新される可能性があるノードの前記スタートノードからの距離を更新するスレッドを生成させる処理と、をコンピュータに実行させる、プログラム。
【０１０２】
なお、上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【０１０３】
１    ＧＰＵ制御ＣＰＵ
２、２Ａ、２Ｂ、５    Ｉ／Ｏバス
３、３Ａ、３Ｂ、６    ＧＰＵボード
１０    制御手段
１１、１２、１３    ＧＰＵ制御プログラム
２０    計算手段
３１、３１Ａ、３１Ｂ、６１    ＧＰＵ
３２、３２Ａ、３２Ｂ、６２    ＧＰＵメモリ
４１、４２    グラフ
１００    経路計算装置
３１１、３１３Ａ、３１３Ｂ、６１１    経路計算プログラム
３１２、３１２Ａ、３１２Ｂ、６１２    コア
３２１、３２２Ａ、３２２Ｂ、６２１    グラフデータ
Ａ〜Ｒ    ノード
Ｇ１１、Ｇ２１Ａ、Ｇ３１    エッジ距離配列
Ｇ１２、Ｇ２２Ａ、Ｇ２２Ｂ、Ｇ３２    ノード距離配列
Ｇ１３、Ｇ２３Ａ、Ｇ３３    ノード更新距離配列
Ｇ１４、Ｇ２４Ａ、Ｇ２４Ｂ    バケット配列
Ｇ１５、Ｇ２５Ａ、Ｇ３４    経路配列
Ｇ１６、Ｇ２６Ａ、Ｇ２６Ｂ、Ｇ３５    更新配列
【図１】
2015064683.tif 000003
【図２】
2015064683.tif 000004
【図３】
2015064683.tif 000005
【図４】
2015064683.tif 000006
【図５】
2015064683.tif 000007
【図６】
2015064683.tif 000008
【図７】
2015064683.tif 000009
【図８】
2015064683.tif 000010
【図９】
2015064683.tif 000011
【図１０】
2015064683.tif 000012
【図１１】
2015064683.tif 000013
【図１２】
2015064683.tif 000014
【国際調査報告】
2015064683.tif 000015
2015064683.tif 000016