(57)【特許請求の範囲】
【請求項１】
コンピュータに、
複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、
前記複数の領域の各々について、前記領域に含まれる粒子の数に基づいて、前記解析空間のうちの前記領域から所定距離以内の領域に含まれる粒子の数を見積もり、
前記複数の領域の各々について、前記領域に含まれる粒子の数と、見積もった前記粒子の数と、に基づいて、前記領域に含まれる粒子の動きをシミュレートする場合における計算負荷と、前記領域に含まれる粒子と、前記所定距離以内にある領域に含まれる粒子との通信負荷と、を示す評価値を算出し、
前記複数の領域から、前記複数の領域の各々について算出した前記評価値が大きい順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、
前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々について算出した前記評価値が大きい順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち割り当て済みの前記領域について算出した前記評価値に基づいて特定されるプロセスに順次割り当てる、
処理を実行させることを特徴とする粒子シミュレーションプログラム。
【請求項２】
前記コンピュータに、
前記解析空間内の総粒子数を前記所定数により除算して前記所定数のプロセスの各々がシミュレートする平均粒子数を算出する処理を実行させ、
前記特定されるプロセスに順次割り当てる処理は、
前記未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち、割り当て済みの前記領域に含まれる粒子の数と前記未割り当ての領域に含まれる粒子の数との合計粒子数が、算出した前記平均粒子数を超えないプロセスに順次割り当てる、
ことを特徴とする請求項１に記載の粒子シミュレーションプログラム。
【請求項３】
前記特定されるプロセスに順次割り当てる処理は、
前記未割り当ての領域の各々に含まれる粒子の数が多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる、
ことを特徴とする請求項１に記載の粒子シミュレーションプログラム。
【請求項４】
コンピュータが、
複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、
前記複数の領域の各々について、前記領域に含まれる粒子の数に基づいて、前記解析空間のうちの前記領域から所定距離以内の領域に含まれる粒子の数を見積もり、
前記複数の領域の各々について、前記領域に含まれる粒子の数と、見積もった前記粒子の数と、に基づいて、前記領域に含まれる粒子の動きをシミュレートする場合における計算負荷と、前記領域に含まれる粒子と、前記所定距離以内にある領域に含まれる粒子との通信負荷と、を示す評価値を算出し、
前記複数の領域から、前記複数の領域の各々について算出した前記評価値が大きい順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、
前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々について算出した前記評価値が大きい順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち割り当て済みの前記領域について算出した前記評価値に基づいて特定されるプロセスに順次割り当てる、
処理を実行することを特徴とする粒子シミュレーションにおける計算機資源配分方法。
【請求項５】
複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、前記複数の領域の各々について、前記領域に含まれる粒子の数に基づいて、前記解析空間のうちの前記領域から所定距離以内の領域に含まれる粒子の数を見積もり、前記複数の領域の各々について、前記領域に含まれる粒子の数と、見積もった前記粒子の数と、に基づいて、前記領域に含まれる粒子の動きをシミュレートする場合における計算負荷と、前記領域に含まれる粒子と、前記所定距離以内にある領域に含まれる粒子との通信負荷と、を示す評価値を算出し、前記複数の領域から、前記複数の領域の各々について算出した前記評価値が大きい順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々について算出した前記評価値が大きい順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち割り当て済みの前記領域について算出した前記評価値に基づいて特定されるプロセスに順次割り当てる制御部、
を有することを特徴とする粒子シミュレーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、粒子シミュレーションプログラム、粒子シミュレーションにおける計算機資源配分方法、および粒子シミュレーション装置に関する。
【背景技術】
【０００２】
近年、水や空気の流れを調べる流体解析や圧縮されたゴムの振る舞いを調べる弾性体解析などを行うために、粒子法を用いたシミュレーションが利用される。
【０００３】
従来、粒子法を用いたシミュレーションでは、解析空間を複数の領域に分割し、分割した複数の領域の各々を複数のプロセスのいずれかに割り当てることにより、複数のプロセスによって並列に粒子の動きの計算を行う技術がある。例えば、従来、領域内に含まれる粒子の数が均等になるように領域を分割することによって粒子の動きの計算負荷が均等になるように領域を分割する技術がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】「ＭＰＳ法を用いた福島第一原子力発電所第１号機タービン建屋の津波浸水解析」，室谷浩平、塚越誠一、塩谷隆二、萩野正雄、永井英一、藤沢智光、安重晃、計算工学講演会論文集  Ｖｏｌ．２０（２０１５年６月）
【非特許文献２】「ＰａｒＭＥＴＩＳを用いたＭＰＳ陽解法の分散メモリ型並列アルゴリズムの開発」，室谷浩平、大地雅俊、藤沢智光、塚越誠一、吉村忍、Ｔｒａｓａｃｔｉｏｎｓ  оｆ  ＪＳＣＥＳ，Ｐａｐｅｒ  Ｎｏ．２０１２００１２
【非特許文献３】「ＧＰＵスパコンにおける動的負荷分散を用いた大規模流体構造連成シミュレーション」，都築怜理、青木尊之、計算工学講演会論文集  Ｖｏｌ．２０（２０１５年６月）
【非特許文献４】「Ｔｈｅ  ｃоｓｍоｌоｇｉｃａｌ  ｓｉｍｕｌａｔｉоｎ  ｃоｄｅ  ＧＡＤＧＥＴ−２」，Ｖｏｌｋｅｒ  Ｓｐｒｉｎｇｅｌ、Ｍｏｎｔｌｙ  Ｎｏｔｉｃｅｓ  Ｏｆ  ｔｈｅ  Ｒｏｙａｌ  Ａｓｔｒｏｎｏｍｉｃａｌ  Ｓｏｃｉｅｔｙ，３６４，ｐｐ．１１０５−１１３４（２００５）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、各領域についての粒子の動きの計算負荷が均等でない場合、各プロセスの粒子の動きの計算負荷が均等にならないため、いずれかのプロセスに負荷が集中する場合がある。そのため、並列処理を効率よく行うことができないという問題点がある。例えば、従来技術では、領域内に含まれる粒子の数が均等でない場合、粒子の動きの計算負荷が均等にならない。
【０００６】
１つの側面では、本発明は、並列処理を効率よく行うことができる粒子シミュレーションプログラム、粒子シミュレーションにおける計算機資源配分方法、および粒子シミュレーション装置を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、前記複数の領域から、前記複数の領域の各々に含まれる粒子の数の多い順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数に基づいて特定されるプロセスに順次割り当てる粒子シミュレーションプログラム、粒子シミュレーションにおける計算機資源配分方法、および粒子シミュレーション装置が提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、並列処理を効率よく行うことができる。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明にかかる粒子シミュレーション装置による一動作例を示す説明図である。
【図２】図２は、粒子の影響領域と近傍粒子の例を示す説明図である。
【図３】図３は、領域分割例を示す説明図である。
【図４】図４は、袖粒子の通信例を示す説明図である。
【図５】図５は、領域の境界を超えた粒子の通信例を示す説明図である。
【図６】図６は、粒子シミュレーション装置のハードウェア構成例を示す説明図である。
【図７】図７は、粒子シミュレーション装置の機能的構成例を示すブロック図である。
【図８】図８は、領域分割例を示す説明図である。
【図９】図９は、粒子データ例を示す説明図である。
【図１０】図１０は、領域データ例を示す説明図である。
【図１１】図１１は、領域の分割例を示す説明図である。
【図１２】図１２は、領域と袖領域例を示す説明図である。
【図１３】図１３は、評価値が大きい順例を示す説明図である。
【図１４】図１４は、評価値が高い順番に割り当てた例を示す説明図である。
【図１５】図１５は、平均粒子数を超えないように割り当てる例を示す説明図である。
【図１６】図１６は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャート（その１）である。
【図１７】図１７は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャート（その２）である。
【図１８】図１８は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャート（その３）である。
【図１９】図１９は、評価値が最小のプロセスに割り当てる例（その１）を示す説明図である。
【図２０】図２０は、評価値が最小のプロセスに割り当てる例（その２）を示す説明図である。
【図２１】図２１は、評価値が最小のプロセスに割り当てる例（その３）を示す説明図である。
【図２２】図２２は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャートである。
【図２３】図２３は、プロセスと計算ノードとの関係を示す説明図である。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明にかかる粒子シミュレーションプログラム、粒子シミュレーションにおける計算機資源配分方法、および粒子シミュレーション装置の実施の形態を詳細に説明する。
【００１１】
図１は、本発明にかかる粒子シミュレーション装置による一動作例を示す説明図である。粒子シミュレーション装置１００は、粒子法を用いて並列のシミュレーションを行う際に、どのように並列させるか決定するコンピュータである。粒子法は、連続体に関する方程式を数値的に解くための離散化の手法である。粒子法では計算対象物を粒子の集まりとして表す。
【００１２】
粒子法を用いたシミュレーションとしては、例えば、水や空気の流れを調べる流体解析や圧縮されたゴムの振る舞いを調べる弾性体解析などがある。例えば、ＳＰＨ（Ｓｍｏｏｔｈｅｄ  Ｐａｒｔｉｃｌｅｓ  Ｈｙｄｒｏｄｙｎａｍｉｃｓ）法やＭＰＳ（Ｍｏｖｉｎｇ  Ｐａｒｔｉｃｌｅｓ  Ｓｅｍｉ‐ｉｍｐｌｉｃｉｔ）法では、後述する図２に示すように、ある粒子に対する予め設定された領域内に存在する粒子からの相互作用を計算することにより、粒子の運動を解析する。ＳＰＨ法やＭＰＳ法は、流体解析や弾性体解析などにおいて連続体を粒子の分布で表す方法である。
【００１３】
ここでの解析領域はシミュレーション空間に設けられた空間である。シミュレーション空間とは、コンピュータ上でシミュレーションされる仮想的な３次元空間である。具体的には、例えば、シミュレーション空間は、解析空間１０１をシミュレーションするためのＣＡＤ（Ｃｏｍｐｕｔｅｒ  Ａｉｄｅｄ  Ｄｅｓｉｇｎ）によって粒子シミュレーション装置１００内に仮想的に設定された空間である。シミュレーション空間には、例えば、Ｘ軸とＹ軸とＺ軸とを有する３次元の直交座標系が定義される。
【００１４】
粒子法を用いたシミュレーションでは、解析空間１０１を広く取りながら、解析対象の所望の解像度を満たすために多数の粒子を扱う。例えば、津波の浸水計算を行うためには、５［ｋｍ］四方の領域を１［ｍ］の解像度で扱うと、数億体の粒子を用いることとなる。
【００１５】
また、従来、粒子法を用いたシミュレーションでは、解析空間１０１を複数の領域に分割し、分割した複数の領域の各々について複数のプロセスのいずれかに割り当てることにより、複数のプロセスによって並列に計算を行う技術がある。分割した領域について並列に計算を行う手法を領域分割法とも称する。このため、従来、例えば、領域内に含まれる粒子の数が均等になるように分割することによって計算負荷が均等になるように領域を分割する技術がある。
【００１６】
しかしながら、従来技術では、領域間において計算負荷が均等でない場合、各プロセスの計算負荷が均等にならないため、計算時間が長くなる。例えば、解析空間１０１に含まれる粒子の位置の分布の形状が複雑であると、領域内に含まれる粒子の数が均等になるように分割することは困難であるため、領域間において計算負荷が均等とならない場合がある。
【００１７】
そこで、本実施の形態では、粒子シミュレーション装置１００は、粒子数が多い順に複数の領域を、領域数より少ない数のプロセスのうちそれぞれ異なるプロセスに割り当て後、該順で未割当領域を、割当済み領域の粒子数を基にプロセスに順次割り当てる。これにより、並列計算時の負荷の均等化を図ることができる。したがって、並列処理効率の向上を図ることができる。
【００１８】
粒子シミュレーション装置１００は、例えば、複数の領域を有する解析空間１０１内の粒子の動きを領域の数よりも少ない所定数のプロセスによってシミュレートする際に、所定数のプロセスに複数の領域の各々を割り当てる。領域数はｎｄと表し、所定数はｎｐと表す。また、所定数はプロセス数とも称する。本実施の形態では、ｎｄ＞ｎｐという関係である。図１の例では、領域数ｎｄは、領域ａ１〜領域ａ９までの９である。
【００１９】
また、複数の領域の各々は、解析空間１０１に含まれる３次元の立体空間である。本実施の形態では、複数の領域の各々を直方体とする。後述する図２や図４で説明するように、粒子は近傍の粒子からの影響を受ける。近傍の粒子は、自粒子を含む領域の隣接領域に含まれる場合がある。そのため、粒子法を用いたシミュレーションでは、領域に含まれる粒子の動きをシミュレーションする際に、領域の隣接領域を特定する処理が行われる。直方体のように領域の形状が単純であると、領域の隣接領域の特定が容易となるため、領域間におけるデータ通信のルーチンの簡単化を図ることができる。したがって、並列処理にかかる時間の短縮化を図ることができる。
【００２０】
また、プロセスとは、プログラムの実行単位であり、計算ノードに実行させる処理である。プロセスに領域を割り当てるとは、領域に含まれる粒子を計算する処理が当該プロセスによって実現されることを示す。粒子法を用いたシミュレーションを行う装置が、並列計算専用に設計されたコンピュータである場合、計算ノードは、例えば、コアやプロセッサである。また、実際に粒子シミュレーションを行う装置が、コンピュータクラスターである場合、計算ノードは、各コンピュータである。コンピュータクラスターとは、複数のパーソナル・コンピュータやサーバ、スーパーコンピュータを接続することにより並列計算を実現するシステムである。
【００２１】
本実施の形態では、所定数のプロセスを実行する複数の計算ノードの能力は同等とする。所定数については、例えば、計算ノードの数そのものであってもよいし、計算ノードの数の倍数などであってもよい。例えば、計算ノードの数と所定数とが同一である場合、計算ノードと所定数のプロセスとは１対１で対応付けられる。例えば、２つの領域がプロセスｐ１に割り当てられる場合、２つの領域に含まれる粒子の動きを計算するようにプロセスｐ１がコーディングされる。そして、プロセスｐ１に対応付けられた計算ノードが、プロセスｐ１を実行することにより、２つの領域に含まれる粒子の動きがシミュレーションされる。計算ノードの数と所定数とが同一である例を後述する図２３に示す。なお、本実施の形態では、粒子シミュレーション装置１００は、所定数のプロセスに粒子数が均等になるように領域を割り当てるが、所定数の計算ノードに粒子数が均等になるように領域を割り当ててもよい。
【００２２】
まず、粒子シミュレーション装置１００は、複数の領域から、複数の領域の各々に含まれる粒子の数の多い順に選ばれた所定数の領域を、所定数のプロセスのうちのそれぞれ異なるプロセスに割り当てる。図１では、領域に含まれる粒子の数を（  ）内に示す。図１における粒子の数の多い順は、領域ａ４、領域ａ７、領域ａ９、領域ａ８、領域ａ１、領域ａ５、領域ａ６、領域ａ２、領域ａ３の順である。粒子の数が多い順に選ばれた所定数の領域は、例えば、領域ａ４、領域ａ７、領域ａ９、領域ａ８、領域ａ１である。
【００２３】
粒子シミュレーション装置１００は、例えば、最も粒子の数が多い領域ａ４をプロセスｐ５に割り当てる。粒子シミュレーション装置１００は、例えば、領域ａ７をプロセスｐ４に割り当てる。粒子シミュレーション装置１００は、例えば、領域ａ９をプロセスｐ３に割り当てる。そして、粒子シミュレーション装置１００は、例えば、領域ａ８をプロセスｐ２に割り当てる。粒子シミュレーション装置１００は、例えば、領域ａ１をプロセスｐ１に割り当てる。これにより、粒子の数が多い領域同士が同じプロセスに割り当てられないようにできる。
【００２４】
粒子シミュレーション装置１００は、複数の領域のうち割り当て済みの所定数の領域以外の未割り当ての領域の粒子数の多い順に、未割り当ての領域の各々を、所定数のプロセスの各々に割り当て済みの領域の粒子数に基づいて特定されるプロセスに順次割り当てる。
【００２５】
具体的に、粒子シミュレーション装置１００は、例えば、解析空間１０１内の総粒子数を所定数により除算して所定数のプロセスの各々がシミュレートする平均粒子数を算出する。平均粒子数は、例えば、ｍｃとも表す。粒子シミュレーション装置１００は、例えば、未割り当ての領域の粒子数の多い順に、未割り当ての領域の各々を、割り当て済みの領域の粒子数と未割り当ての領域の粒子数との合計粒子数が、平均粒子数ｍｃを超えないプロセスに順次割り当てる。ここで、平均粒子数ｍｃを超えないように割り当てる例については後述する実施例１を用いて詳細に説明する。
【００２６】
また、具体的に、粒子シミュレーション装置１００は、例えば、未割り当ての領域の各々に含まれる粒子の数が多い順に、未割り当ての領域の各々を、所定数のプロセスの各々に割り当て済みの領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる。割り当て済みの領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる例については後述する実施例２を用いて詳細に説明する。
【００２７】
図１には、粒子シミュレーション装置１００が、割り当て済みの領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる例を示す。粒子シミュレーション装置１００は、例えば、割り当て済みの領域に含まれる粒子の数が最も少ないプロセスがプロセスｐ１であるため、プロセスｐ１に領域ａ５を割り当てる。粒子シミュレーション装置１００は、例えば、領域ａ５を割り当てた後、割り当て済みの領域に含まれる粒子の数が最も少ないプロセスがプロセスｐ２であるため、プロセスｐ２に領域ａ６を割り当てる。ここで、プロセスｐ１に割り当て済みの領域に含まれる粒子の数は１２００である。プロセスｐ２に割り当て済みの領域に含まれる粒子の数は１３００である。
【００２８】
つぎに、粒子シミュレーション装置１００は、例えば、領域ａ６を割り当てた後、割り当て済みの領域に含まれる粒子の数が最も少ないプロセスがプロセスｐ３であるため、プロセスｐ３に領域ａ２を割り当てる。最後に、粒子シミュレーション装置１００は、例えば、領域ａ２を割り当てた後、割り当てられた領域に含まれる粒子の数が最も少ないプロセスがプロセスｐ４であるため、プロセスｐ４に領域ａ３を割り当てる。
【００２９】
このように、負荷が大きいと推測される領域を先にプロセスに割り当てておき、負荷が小さい領域によって各プロセス間の残余の未割り当ての領域によってプロセス間の負荷が均等になるように割り当てる。これにより、並列計算時の負荷の均等化を図ることができ、並列処理の効率化を図ることができる。
【００３０】
ここで、本実施の形態の詳細な説明の前に、粒子法を用いたシミュレーションについて図２〜図５を用いて簡単に説明する。
【００３１】
図２は、粒子の影響領域と近傍粒子の例を示す説明図である。例えば、ある粒子ｉに着目すると、粒子ｉは、粒子ｉから半径ｈ以内の近傍に存在する複数の粒子との間に相互作用がある。例えば、粒子ｊと粒子ｉとの距離は、｜ｘ−ｘ’｜であり、半径ｈよりも小さい。そのため、粒子ｊと粒子ｉとの間に相互作用がある。粒子について、相互作用の範囲を影響領域とも称する。相互作用の範囲を決める半径ｈを影響半径とも称する。ここでの相互作用とはシミュレーションにおける相互作用である。
【００３２】
図３は、領域分割例を示す説明図である。領域分割法では、計算対象の領域を分割し、各領域を各計算ノードに割り当てることにより並列に計算を実行する技術である。図３には、各領域が立方体となるように分割した例を示す。上述したように、例えば、計算負荷が均等になるように領域を分割する技術では、解析空間１０１に含まれる粒子の位置の分布の形状が複雑であると、図３のように直方体に分割することは困難である。
【００３３】
図４は、袖粒子の通信例を示す説明図である。粒子については、図２に示したように影響範囲にある粒子からの影響を受ける。ここで、ある粒子について影響範囲にある粒子を袖粒子とも称する。袖粒子は、袖粒子を含む領域の隣接領域に含まれる粒子に対して影響を及ぼすことになる。そのため、粒子法を用いたシミュレーションでは、領域に含まれる粒子についての袖粒子を特定する。そして、粒子法を用いたシミュレーションでは、特定された袖粒子が当該領域の隣接領域の場合、領域が割り当てられたプロセスと、隣接領域が割り当てられたプロセスと、の間のプロセス間通信により、領域が割り当てられたプロセスは袖領域についての粒子データを取得する。粒子データは、例えば、粒子について、位置、質量、体積などの情報が含まれる。
【００３４】
図５は、領域の境界を超えた粒子の通信例を示す説明図である。粒子は領域内を移動する。例えば、時刻ｎにおいて、粒子ｉは、プロセスｐ０に割り当てられた領域に含まれる。そして、例えば、時刻ｎ＋１において、粒子ｉは、プロセスｐ１に割り当てられた領域に含まれる。
【００３５】
このように、粒子法を用いたシミュレーションでは、実際の時間経過と同様に所定単位ごとに時刻を進めて行う。このため、粒子ｉのように、粒子が移動することにより異なる領域に移動した場合、シミュレーションでは、プロセス間通信などによって粒子データを通信し、粒子を移動させる。
【００３６】
つぎに、本実施の形態にかかる粒子シミュレーション装置１００の詳細な説明を行う。
【００３７】
（粒子シミュレーション装置１００のハードウェア構成例）
図６は、粒子シミュレーション装置のハードウェア構成例を示す説明図である。粒子シミュレーション装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）６０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）６０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）６０３と、を有する。粒子シミュレーション装置１００は、ディスクドライブ６０４と、ディスク６０５と、を有する。粒子シミュレーション装置１００は、Ｉ／Ｆ（Ｉｎｔｅｒ／Ｆａｃｅ）６０６と、キーボード６０７と、マウス６０８と、ディスプレイ６０９と、を有する。また、ＣＰＵ６０１と、ＲＯＭ６０２と、ＲＡＭ６０３と、ディスクドライブ６０４と、Ｉ／Ｆ６０６と、キーボード６０７と、マウス６０８と、ディスプレイ６０９とは、バス６００によってそれぞれ接続される。
【００３８】
ここで、ＣＰＵ６０１は、粒子シミュレーション装置１００の全体の制御を司る。ＲＯＭ６０２は、ブートプログラムなどのプログラムを記憶する。ＲＡＭ６０３は、ＣＰＵ６０１のワークエリアとして使用される。ディスクドライブ６０４は、ＣＰＵ６０１の制御にしたがってディスク６０５に対するデータのリード／ライトを制御する。ディスク６０５は、ディスクドライブ６０４の制御で書き込まれたデータを記憶する。ディスク６０５としては、磁気ディスク、光ディスクなどが挙げられる。
【００３９】
Ｉ／Ｆ６０６は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク６１０に接続され、このネットワーク６１０を介して他の装置に接続される。そして、Ｉ／Ｆ６０６は、ネットワーク６１０と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ６０６には、例えばモデムやＬＡＮアダプタなどを採用することができる。
【００４０】
キーボード６０７やマウス６０８は、利用者の操作により、各種データの入力を行うインターフェースである。ディスプレイ６０９は、ＣＰＵ６０１の指示により、データを出力するインターフェースである。
【００４１】
また、図示を省略するが、粒子シミュレーション装置１００には、カメラから画像や動画を取り込む入力装置やマイクから音声を取り込む入力装置が設けられていてもよい。また、図示を省略するが、粒子シミュレーション装置１００には、プリンタなどの出力装置が設けられていてもよい。
【００４２】
また、本実施の形態では、粒子シミュレーション装置１００のハードウェア構成として、パーソナル・コンピュータを例に挙げているが、これに限らず、サーバなどであってもよい。粒子シミュレーション装置１００がサーバである場合、粒子シミュレーション装置１００と利用者の操作可能な装置やディスプレイ６０９などがネットワーク６１０を介して接続されてもよい。
【００４３】
（粒子シミュレーション装置１００の機能的構成例）
図７は、粒子シミュレーション装置の機能的構成例を示すブロック図である。粒子シミュレーション装置１００は、分割部７０１と、見積もり部７０２と、算出部７０３と、第１割り当て部７０４と、第２割り当て部７０５と、を有する。分割部７０１から第１割り当て部７０４までの制御部の処理は、例えば、図６に示すＣＰＵ６０１がアクセス可能なＲＯＭ６０２、ＲＡＭ６０３、ディスク６０５などの記憶装置に記憶されたプログラムにコーディングされている。そして、ＣＰＵ６０１が記憶装置から該プログラムを読み出して、プログラムにコーディングされている処理を実行する。これにより、制御部の処理が実現される。また、制御部の処理結果は、例えば、ＲＡＭ６０３、ＲＯＭ６０２、ディスク６０５などの記憶装置に記憶される。
【００４４】
上述したように、本実施の形態では、粒子シミュレーション装置１００は、複数の領域を有する解析空間１０１内の粒子の動きを所定数のプロセスによってシミュレートを行う。所定数については、例えば、上述したように、計算ノードの数であってもよいし、計算ノードの数の倍数などであってもよいし、解析者によって決定された数であってもよい。上述したように、所定数は、例えば、ｎｐと表し、プロセス数とも称する。
【００４５】
分割部７０１は、予め定められたタイミングによって解析空間１０１を複数の領域に分割する。分割部７０１は、例えば、予め定められた回数程度のシミュレーションが終了する都度、解析空間１０１を複数の領域に分割する。複数の領域の各々は、例えば、直方体である。複数の領域のうち隣り合う領域の面同士は、共通である。これにより、隣接領域を特定する処理に時間がかからないため、粒子の移動や袖領域などによる領域間のデータ通信が簡単になり、通信時間の短縮化を図ることができる。
【００４６】
図８は、領域分割例を示す説明図である。図８の例では、解析空間１０１に含まれる一部の領域をＸ軸とＹ軸との２次元によって示す。図８の例では、解析空間１０１は、例えば、Ａｒｅａ［１］［１］と、Ａｒｅａ［１］［２］と、Ａｒｅａ［２］［１］と、Ａｒｅａ［２］［２］と、の４つの領域に分割される。領域は、例えば、境界線によって定義される。
【００４７】
Ｘｂ［１］、Ｘｂ［２］、Ｘｂ［３］は、後述する図１０に示すようにＸ軸方向における各境界線の位置である。Ｘｂ［１］、Ｘｂ［２］、Ｘｂ［３］は、例えば、座標値の小さい順である。Ｙｂ［１］、Ｙｂ［２］、Ｙｂ［３］は、後述する図１０に示すようにＹ軸方向における各境界線の位置である。Ｙｂ［１］、Ｙｂ［２］、Ｙｂ［３］は、例えば、座標値の小さい順である。また、８の例では、Ｘ軸とＹ軸とを用いて説明するが、Ｚ軸についても境界線の位置が設定される。
【００４８】
そして、領域の境界線の位置と、粒子の位置と、に基づいて、領域に含まれる粒子が特定される。図９には粒子データを示し、図１０には境界線データを示す。
【００４９】
図９は、粒子データ例を示す説明図である。粒子データ９００は、例えば、粒子を表す情報である。粒子データ９００は、例えば、粒子番号、位置情報のフィールドを有する。各フィールドに情報が設定されることによりレコードとして記憶される。
【００５０】
粒子番号のフィールドには、粒子を識別する識別情報が設定される。ここでは、粒子にそれぞれ通し番号を付すことによって粒子の各々が識別される。位置情報のフィールドには、粒子の位置を示すＸ，Ｙ，Ｚの座標値が設定される。粒子は、上述したように移動するため、位置情報については、粒子の移動に伴い、更新される。また、図示省略するが、粒子データ９００には、質量、体積などの情報が含まれていてもよい。
【００５１】
図１０は、領域データ例を示す説明図である。領域データ１０００は、領域を区別するための境界線を示す情報である。境界線データは、例えば、Ｘ軸方向の境界線の数、境界線のＸ座標値、Ｙ軸方向の境界線の数、境界線のＹ座標値、Ｚ軸方向の境界線の数、境界線のＺ座標値のフィールドを有する。境界線データは、領域分割が行われる際にあらたに生成される。
【００５２】
Ｘ軸方向の境界線の数のフィールドには、Ｘ軸方向に設けられる境界線の数が設定される。境界線のＸ座標値のフィールドには、Ｘ軸方向に設けられる境界線のＸ座標値が設定される。
【００５３】
Ｘ軸方向に設けられる境界線の数は、例えば、ｘｍである。Ｘ軸方向に設けられる境界線のＸ座標値は、例えば、Ｘｂ［１］〜Ｘｂ［ｘｍ］である。Ｙ軸方向に設けられる境界線の数は、例えば、ｙｍである。Ｙ軸方向に設けられる境界線のＹ座標値は、例えば、Ｙｂ［１］〜Ｙｂ［ｙｍ］である。Ｙ軸方向に設けられる境界線の数は、例えば、ｚｍである。Ｚ軸方向に設けられる境界線のＺ座標値は、例えば、Ｚｂ［１］〜Ｚｂ［ｚｍ］である。ここで、境界線の座標値は、例えば、各軸の方向において座標値が小さい順に並べられてある。
【００５４】
領域データ１０００によって領域は、特定可能である。領域については、領域の数が（ｘｍ−１）×（ｙｍ−１）×（ｚｍ−１）によって算出できる。例えば、軸ごとの３つのインデックスによって領域を識別する領域番号が規定されてもよい。
【００５５】
例えば、領域（о，ｐ，ｑ）のように規定される。ここで、о，ｐ，ｑはそれぞれ「１≦о＜ｘｍ」、「１≦ｐ＜ｙｍ」、「１≦ｑ＜ｚｍ」である。例えば、領域（о，ｐ，ｑ）に含まれる粒子は以下の（１）〜（３）の条件をすべて満たす粒子である。
（１）Ｘｂ［о］≦粒子のＸ座標値＜Ｘｂ［о＋１］
（２）Ｙｂ［ｐ］≦粒子のＹ座標値＜Ｙｂ［ｐ＋１］
（３）Ｚｂ［ｑ］≦粒子のＺ座標値＜Ｚｂ［ｑ＋１］
【００５６】
例えば、粒子ｐが領域（о，ｐ，ｑ）に含まれるか否かについては、上述の条件を満たすか否かによって判別できる。ここで、上述したように、領域数ｎｄ＜所定数ｎｐである。
【００５７】
図１１は、領域の分割例を示す説明図である。図１１には、領域ａ１〜ａ９までの領域数ｎｄが９の例を示す。太線は、領域の境界である。ハッチが設けられている箇所は、粒子の密な部分である。
【００５８】
また、領域をシミュレーションする場合における計算量を示す評価値として、領域に含まれる粒子の数を用いてもよいし、領域に含まれる粒子の数と、当該領域の袖領域に含まれる粒子の数と、の合計粒子数を用いてもよい。なお、上述した図１の例では、領域に含まれる粒子の数を評価値として用いる。以下の説明では、評価値として、領域に含まれる粒子の数と、当該領域の袖領域に含まれる粒子の数と、の合計粒子数を用いる。
【００５９】
見積もり部７０２は、複数の領域の各々について、領域に含まれる粒子の数に基づいて、解析空間１０１のうちの領域から所定距離以内の領域に含まれる粒子の数を見積もる。粒子の数を見積もるとは、解析空間１０１のうちの領域から所定距離以内の領域に含まれる粒子の数の予測値を算出することである。
【００６０】
より具体的に、見積もり部７０２は、例えば、領域の各々について、領域に含まれる粒子の数を特定する。上述したように、見積もり部７０２は、粒子データ９００と領域データ１０００とに基づいて、領域の各々について、上記の（１）〜（３）の条件を満たす粒子を抽出する。そして、見積もり部７０２は、領域の各々について、抽出した粒子の数を特定する。
【００６１】
つぎに、見積もり部７０２は、例えば、袖領域に含まれる粒子の数の予測値を、領域に含まれる粒子の数と、袖領域の体積と、に基づいて算出する。
【００６２】
図１２は、領域と袖領域例を示す説明図である。例えば、ｘ方向の長さがＬｘであり、ｙ方向の長さがＬｙである領域ａｐの場合に、影響半径がｈであると、見積もり部７０２は、袖領域ａｓｐの大きさを「２（Ｌｘ＋Ｌｙ＋２ｈ）×ｈ」によって算出する。
【００６３】
そして、対象の領域の大きさが（Ｌｘ×Ｌｙ）であり、領域に含まれる粒子の数がｎｘであると、見積もり部７０２は、袖領域に含まれる粒子の数の予測値を「（２（Ｌｘ＋Ｌｙ＋２ｈ）×ｈ／（Ｌｘ×Ｌｙ））×ｎｘ」によって算出する。
【００６４】
そして、見積もり部７０２は、複数の領域の各々について、領域に含まれる粒子の数と、算出した袖領域に含まれる粒子の数の予測値とに基づいて、計算負荷を示す評価値を算出する。ここでの計算負荷は、領域に含まれる粒子の動きをシミュレートする場合における計算負荷と、領域に含まれる粒子と所定距離以内にある領域に含まれる粒子との通信による通信負荷と、を示す。ここで、領域から所定距離以内にある周辺の領域を袖領域とも称する。袖領域の例は、図１２を用いて後述する。所定距離は、例えば、図２に示した相互作用の範囲を決める影響半径とする。上述したように、領域に含まれる粒子は、影響半径以内にある袖粒子による影響を受けるため、領域に含まれる粒子の動きをシミュレーションする際には、袖領域についての粒子データ９００も使用される。このため、袖領域に含まれる粒子の数を領域に含まれる粒子の数に基づいて見積もることによって、通信負荷を含めた評価値を算出することができ、各プロセスの粒子の動きの計算負荷の均等化を図ることができる。
【００６５】
見積もり部７０２は、領域に含まれる粒子の数と、ａ×袖領域に含まれる粒子の数と、の合計値を、領域についての評価値として算出する。ａは、１粒子あたりの通信コストと計算コストの比率を表す実数である。より具体的に、見積もり部７０２は、評価値を以下式（１）によって算出可能である。
【００６６】
評価値＝ｎｘ＋ａ×２（Ｌｘ＋Ｌｙ＋２ｈ）×ｈ／（Ｌｘ×Ｌｙ）×ｎｘ・・・式（１）
【００６７】
つぎに、第１割り当て部７０４は、例えば、複数の領域から、複数の領域の各々に含まれる粒子の数の多い順に選ばれた所定数ｎｐの領域を、所定数ｎｐのプロセスのうちのそれぞれ異なるプロセスに割り当てる。
【００６８】
また、上述したように、評価値として、領域に含まれる粒子の数と、袖領域に含まれる粒子の数との合計粒子数を用いる場合について説明する。第１割り当て部７０４は、例えば、複数の領域から、複数の領域の各々について算出した合計粒子数が多い順に選ばれた所定数ｎｐの領域を、所定数ｎｐのプロセスのうちのそれぞれ異なるプロセスに割り当てる。
【００６９】
図１３は、評価値が大きい順例を示す説明図である。図１３では、図１１に示した領域ａ１〜ａ９までを領域について算出された評価値が大きい順に並べた例を示す。例えば、評価値が大きい順は、領域ａ６、領域ａ３、領域ａ９、領域ａ５、領域ａ８、領域ａ２、領域ａ７、領域ａ４、領域ａ１の順である。
【００７０】
第１割り当て部７０４は、例えば、複数の領域のうち評価値が大きい順に選ばれた所定数ｎｐの領域を、所定数ｎｐのプロセスのうちのそれぞれ異なるプロセスに割り当てる。
【００７１】
図１４は、評価値が高い順に割り当てた例を示す説明図である。ここでは、プロセス数である所定数ｎｐが６である場合を例に挙げる。第１割り当て部７０４は、例えば、評価値が高い順に、６つの領域を６つのプロセスの各々に割り当てる。第１割り当て部７０４は、例えば、領域ａ６、領域ａ３、領域ａ９、領域ａ５、領域ａ８、領域ａ２の順に、所定数ｎｐのプロセスのうちプロセス番号の小さいプロセスに順次割り当てる。
【００７２】
例えば、領域ａ６はプロセスｐ１に割り当てられ、領域ａ３はプロセスｐ２に割り当てられる。また、例えば、領域ａ７と領域ａ４と領域ａ１とが未割り当ての領域である。
【００７３】
つぎに、第２割り当て部７０５は、例えば、未割り当ての領域の各々に含まれる粒子の数の多い順に、未割り当ての領域の各々を、所定数ｎｐのプロセスの各々に割り当て済みの領域に含まれる粒子の数に基づいて特定されるプロセスに順次割り当てる。未割り当ての領域は、複数の領域のうち、第１割り当て部７０４によってそれぞれ異なるプロセスに割り当てられた所定数ｎｐの領域以外の領域である。第２割り当て部７０５による割り当て例については、実施例１と実施例２とに区別して説明する。
【００７４】
（実施例１）
実施例１では、粒子シミュレーション装置１００は、割り当て済みの領域に含まれる粒子数と未割り当ての領域に含まれる粒子数との合計粒子数が、平均粒子数ｍｃを超えないように未割り当ての領域をプロセスに割り当てる。これにより、粒子数が均等になるようにプロセスに領域を割り当てることができる。したがって、並列演算の効率の向上を図ることができる。並列演算の効率が向上するとは、粒子数に対する処理時間が向上することを示す。例えば、プロセスに割り当てられる粒子数が均等になれば、各プロセスの処理時間が均等になるため、処理時間の短縮を図ることができる。
【００７５】
算出部７０３は、例えば、解析空間１０１内の総粒子数を所定数ｎｐにより除算して所定数ｎｐのプロセスの各々がシミュレートする平均粒子数ｍｃを算出する。所定数は、上述したようにプロセス数である。ここでは、複数の領域を有する解析空間１０１内の粒子の動きが所定数ｎｐのプロセスによってシミュレートされる。所定数ｎｐについては、例えば、上述したように、所定数ｎｐのプロセスを実行する計算ノードの数であってもよいし、計算ノードの数の倍数であってもよい。
【００７６】
第２割り当て部７０５は、例えば、算出された平均粒子数ｍｃに基づいて、未割り当ての領域の各々について所定数ｎｐのプロセスのうちのいずれかのプロセスに割り当てる。
【００７７】
第２割り当て部７０５は、算出された平均粒子数ｍｃに基づいて、未割り当ての領域の各々について、所定数ｎｐのプロセスのうちいずれかのプロセスに、領域を割り当てる。具体的に、第２割り当て部７０５は、例えば、プロセスに、未割り当ての領域を割り当てた場合における評価値の合計値が、平均粒子数を超えるか否かを判定する。
【００７８】
第２割り当て部７０５は、例えば、平均粒子数ｍｃを超えると判定された場合に、プロセスに未割り当ての領域を割り当てない。一方、第２割り当て部７０５は、例えば、平均粒子数ｍｃを超えないと判定された場合に、プロセスに未割り当ての領域を割り当てる。
【００７９】
図１５は、平均粒子数を超えないように割り当てる例を示す説明図である。ここでは、第２割り当て部７０５は、例えば、プロセス番号の大きい順に割り当て先の候補プロセスとする。これにより、第１割り当て部７０４によって割り当てられた領域についての評価値が小さい順に割り当て先の候補プロセスとすることができる。
【００８０】
具体的に、第２割り当て部７０５は、例えば、プロセスｐ６に割り当て済みの領域ａ２についての評価値と、領域ａ７についての評価値と、の合計評価値が平均粒子数ｍｃを超えないため、領域ａ７をプロセスｐ６に割り当てる。
【００８１】
第２割り当て部７０５は、例えば、プロセスｐ６に割り当て済みの領域ａ２および領域ａ７についての評価値と、領域ａ４についての評価値と、の合計評価値が平均粒子数を超えるため、領域ａ４をプロセスｐ６に割り当てない。つぎに、第２割り当て部７０５は、例えば、プロセスｐ５に割り当て済みの領域ａ８についての評価値と、領域ａ４についての評価値と、の合計評価値が平均粒子数ｍｃを超えないため、領域ａ４をプロセスｐ５に割り当てる。
【００８２】
つぎに、第２割り当て部７０５は、例えば、プロセスｐ５に割り当て済みの領域ａ８と領域ａ４についての評価値と、領域ａ１についての評価値と、の合計評価値が平均粒子数ｍｃを超えないため、領域ａ１をプロセスｐ５に割り当てる。
【００８３】
これにより、平均粒子数ｍｃに基づいて、プロセスに割り当てられる領域についての評価値の均等化を図ることができる。割り当てに要する計算量は、「所定数ｎｐ＋（２×（ｎｄ−ｎｐ）×（１プロセスの持つ平均の領域数））」である。所定数ｎｐは、第１割り当て部７０４による１回目の割り当てについての計算量の指標値である。（２×（ｎｄ−ｎｐ）×（１プロセスの持つ平均の領域数））は、第２割り当て部７０５による２回目以降の割り当てについての計算量の指標値である。１プロセスの持つ平均の領域数は、領域の数ｎｄ／所定数ｎｐである。
【００８４】
また、図１５の例では、割り当て処理の簡単化のために、プロセスｐ５を、領域ａ１の割り当て対象の候補プロセスとして平均粒子数ｍｃを超えるか否かの判定を行っているが、これに限らない。第２割り当て部７０５は、例えば、割り当て先の候補プロセスをプロセス番号の大きいプロセスｐ６にしてもよい。そして、第２割り当て部７０５は、例えば、プロセスｐ６に割り当て済みの領域ａ２および領域ａ７についての評価値と、領域ａ１についての評価値と、の合計評価値が平均粒子数ｍｃを超えるか否かを判定してもよい。そして、第２割り当て部７０５は、例えば、合計評価値が平均粒子数ｍｃを超えない場合、領域ａ１をプロセスｐ６に割り当てる。第２割り当て部７０５は、例えば、合計評価値が平均粒子数ｍｃを超える場合、プロセスｐ５に割り当て済みの領域ａ８と領域ａ４についての評価値と、領域ａ１についての評価値と、の合計評価値が平均粒子数ｍｃを超えるか否かを判定してもよい。
【００８５】
（粒子シミュレーション装置１００による割り当て処理手順例）
図１６〜図１８は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャートである。粒子シミュレーション装置１００は、領域ごとに領域に含まれる粒子の数を特定する（ステップＳ１６０１）。粒子シミュレーション装置１００は、領域ごとに、解析空間１０１のうち領域から所定距離以内にある領域に含まれる粒子の数を、領域のサイズと所定距離以内にある領域のサイズとの比率と、領域に含まれる粒子の数とに基づいて見積もる（ステップＳ１６０２）。
【００８６】
そして、粒子シミュレーション装置１００は、領域ごとに、領域に含まれる粒子の数と、見積もった所定距離以内にある領域に含まれる粒子の数と、に基づいて負荷の評価値を算出する（ステップＳ１６０３）。粒子シミュレーション装置１００は、全領域を評価値順にソートする（ステップＳ１６０４）。
【００８７】
つぎに、粒子シミュレーション装置１００は、総粒子数をプロセス数で除算して平均粒子数ｍｃを算出する（ステップＳ１６０５）。つづいて、粒子シミュレーション装置１００は、評価値が大きい順に選ばれる所定数の領域をプロセス番号が小さい順にプロセスに順次割り当てる（ステップＳ１６０６）。
【００８８】
そして、粒子シミュレーション装置１００は、ｉ＝所定数ｎｐとする（ステップＳ１７０１）。つぎに、粒子シミュレーション装置１００は、未割り当ての領域があるか否かを判断する（ステップＳ１７０２）。未割り当ての領域がない場合（ステップＳ１７０２：Ｎо）、粒子シミュレーション装置１００は、一連の処理を終了する。未割り当ての領域がある場合（ステップＳ１７０２：Ｙｅｓ）、粒子シミュレーション装置１００は、割り当て対象の領域を決定する（ステップＳ１７０３）。
【００８９】
つぎに、粒子シミュレーション装置１００は、プロセスｐｉに割り当て済みの全領域についての評価値と、領域ｊについての評価値との合計評価値ｍｉｊを算出する（ステップＳ１７０４）。そして、粒子シミュレーション装置１００は、合計評価値ｍｉｊ＞平均粒子数ｍｃであるかを判断する（ステップＳ１７０５）。合計評価値ｍｉｊ＞平均粒子数ｍｃでないと判断された場合（ステップＳ１７０５：Ｎｏ）、粒子シミュレーション装置１００は、領域ｊをプロセスｐｉに割り当て（ステップＳ１７０６）、ステップＳ１７０２へ戻る。
【００９０】
合計評価値ｍｉｊ＞平均粒子数ｍｃであると判断された場合（ステップＳ１７０５：Ｙｅｓ）、粒子シミュレーション装置１００は、ｉが１より大きいか否かを判断する（ステップＳ１７０７）。ｉが１より大きいと判断された場合（ステップＳ１７０７：Ｙｅｓ）、粒子シミュレーション装置１００は、ｉ＝ｉ−１とし（ステップＳ１７０８）、ステップＳ１７０２へ戻る。
【００９１】
ｉが１より大きくないと判断された場合（ステップＳ１７０７：Ｎｏ）、粒子シミュレーション装置１００は、ｉ＝所定数ｎｐとする（ステップＳ１８０１）。そして、粒子シミュレーション装置１００は、割り当て対象の領域ｊを決定する（ステップＳ１８０２）。そして、粒子シミュレーション装置１００は、プロセスｐｉに領域ｊを割り当てる（ステップＳ１８０３）。つぎに、粒子シミュレーション装置１００は、プロセスｐｉに割り当て済みの全領域についての評価値の合計評価値ｍｉｊ＿２を算出する（ステップＳ１８０４）。
【００９２】
そして、粒子シミュレーション装置１００は、未割り当ての領域があるか否かを判断する（ステップＳ１８０５）。未割り当ての領域がないと判断された場合（ステップＳ１８０５：Ｎｏ）、粒子シミュレーション装置１００は、一連の処理を終了する。未割り当ての領域があると判断された場合（ステップＳ１８０５：Ｙｅｓ）、粒子シミュレーション装置１００は、合計評価値ｍｉｊ＿２＞平均粒子数ｍｃであるか否かを判断する（ステップＳ１８０６）。
【００９３】
合計評価値ｍｉｊ＿２＞平均粒子数ｍｃでないと判断された場合（ステップＳ１８０６：Ｎｏ）、粒子シミュレーション装置１００は、ステップＳ１８０２へ戻る。合計評価値ｍｉｊ＿２＞平均粒子数ｍｃであると判断された場合（ステップＳ１８０６：Ｙｅｓ）、粒子シミュレーション装置１００は、ｉは１より大きいか否かを判断する（ステップＳ１８０７）。ｉは１より大きいと判断された場合（ステップＳ１８０７：Ｙｅｓ）、粒子シミュレーション装置１００は、ｉ＝ｉ−１とし（ステップＳ１８０９）、ステップＳ１８０２へ戻る。
【００９４】
ｉは１より大きくないと判断された場合（ステップＳ１８０７：Ｎｏ）、粒子シミュレーション装置１００は、未割り当ての領域をランダムに割り当て（ステップＳ１８０８）、一連の処理を終了する。
【００９５】
（実施例２）
実施例２では、粒子シミュレーション装置１００は、プロセスに領域を順に割り当て、プロセスにすでに割り当てられた領域に含まれる粒子の数が小さい順に未割り当ての領域を割り当てる。これにより、粒子数が均等になるようにプロセスに領域を割り当てることができる。したがって、並列演算の効率の向上を図ることができる。ここで、実施例２では、実施例１において説明した同様の構成や機能については同一の符号を付し、詳細な説明を省略する。また、実施例２では、見積もり部７０２による処理は実施例１と同様であり、算出部７０３による処理は行われない。
【００９６】
まず、第２割り当て部７０５は、例えば、領域についての評価値に応じた順番に基づいて、一つのプロセスに複数の領域を割り当てないように、所定数ｎｐのプロセスのいずれかのプロセスに、領域を割り当てる。ここでは、実施例１と同様に、第２割り当て部７０５は、例えば、評価値の大きい領域順に、プロセス番号順に割り当てる。
【００９７】
図１９は、評価値が最小のプロセスに割り当てる例（その１）を示す説明図である。第２割り当て部７０５は、例えば、未割り当ての領域のうち評価値が最も大きい領域ａ７を、割り当て済みの領域についての評価値が最も小さいプロセスｐ６に割り当てる。つぎに、第２割り当て部７０５は、例えば、プロセスｐ１〜プロセスｐ６を、割り当て済みの領域についての評価値が小さい順にソートする。図１９の例では、プロセスｐ５が、割り当てられた領域についての評価値が最も小さい。
【００９８】
図２０は、評価値が最小のプロセスに割り当てる例（その２）を示す説明図である。第２割り当て部７０５は、例えば、未割り当ての領域のうち評価値が最も大きい領域ａ４を、割り当て済みの領域についての評価値が最も小さいプロセスｐ５に割り当てる。そして、第２割り当て部７０５は、例えば、プロセスｐ１〜プロセスｐ６を、割り当て済みの領域についての評価値が小さい順にソートする。
【００９９】
図２１は、評価値が最小のプロセスに割り当てる例（その３）を示す説明図である。第２割り当て部７０５は、例えば、未割り当ての領域ａ１を、割り当て済みの領域についての評価値が最も小さいプロセスｐ５に割り当てる。
【０１００】
また、実施例２において割り当てに要する計算量は、「所定数ｎｐ＋２回目以降の割り当てについての（２×（ｎｄ−ｎｐ）×ｌоｇ（ｎｐ）×（１プロセスの持つ平均の領域数））」である。所定数ｎｐは、第１割り当て部７０４による１回目の割り当てについての計算量の指標値である。（２×（ｎｄ−ｎｐ）×ｌоｇ（ｎｐ）×（１プロセスの持つ平均の領域数））は、第２割り当て部７０５による２回目以降の割り当てについての計算量の指標値である。
【０１０１】
（粒子シミュレーション装置１００による割り当て処理手順例）
図２２は、粒子シミュレーション装置による割り当て処理手順例を示すフローチャートである。粒子シミュレーション装置１００は、領域ごとに領域に含まれる粒子の数を特定する（ステップＳ２２０１）。粒子シミュレーション装置１００は、領域ごとに、解析空間１０１のうち領域から所定距離以内にある領域に含まれる粒子の数を、領域のサイズと所定距離以内にある領域のサイズとの比率と、領域に含まれる粒子の数とに基づいて見積もる（ステップＳ２２０２）。
【０１０２】
そして、粒子シミュレーション装置１００は、領域ごとに、領域に含まれる粒子の数と、見積もった所定距離以内にある領域に含まれる粒子の数と、に基づいて負荷の評価値を算出する（ステップＳ２２０３）。粒子シミュレーション装置１００は、全領域を評価値順にソートする（ステップＳ２２０４）。そして、粒子シミュレーション装置１００は、評価値が大きい順に領域をプロセス番号が小さいプロセス順に順次割り当てる（ステップＳ２２０５）。
【０１０３】
粒子シミュレーション装置１００は、未割り当ての領域があるか否かを判断する（ステップＳ２２０６）。未割り当ての領域があると判断された場合（ステップＳ２２０６：Ｙｅｓ）、粒子シミュレーション装置１００は、全プロセスを割り当てられた領域の評価値順にソートする（ステップＳ２２０７）。粒子シミュレーション装置１００は、評価値が大きい順に選ばれた所定数ｎｐの領域を、プロセス番号が小さい順にプロセスに割り当て（ステップＳ２２０８）、ステップＳ２２０６へ戻る。
【０１０４】
ステップＳ２２０６において、未割り当ての領域がないと判断された場合（ステップＳ２２０６：Ｎｏ）、粒子シミュレーション装置１００は、一連の処理を終了する。
【０１０５】
図２３は、プロセスと計算ノードとの関係を示す説明図である。例えば、計算ノードｎ１〜ｎ５は、１台のコンピュータに含まれる各プロセッサである。例えば、プロセスｐ１〜プロセスｐ５には粒子の数が均等になるように各領域が割り当てられる。例えば、プロセスｐ１には、領域ａ１と領域ａ５とが割り当てられる。そして、本実施の形態では、上述したように、計算ノードとプロセスとは対応付けられる。例えば、計算ノードｎ１〜ｎ５は、それぞれプロセスｐ１〜ｐ５を実行する。
【０１０６】
このため、例えば、計算ノードｎ１は、プロセスｐ１を実行するため、プロセスｐ１に割り当てられた領域ａ１と領域ａ５に含まれる粒子の動きをシミュレートすることになる。
【０１０７】
以上説明したように、粒子シミュレーション装置１００は、粒子数が多い順に複数の領域を、領域数より少ない数のプロセスのうちそれぞれ異なるプロセスに割り当て後、該順で未割当領域を、割当済み領域の粒子数に基づき特定されたプロセスに順次割り当てる。このように、負荷が大きいと推測される領域を先にプロセスに割り当てておき、負荷が小さい残余の未割り当ての領域をプロセス間の負荷が均等化するように割り当てる。したがって、並列処理の効率化を図ることができる。
【０１０８】
また、粒子シミュレーション装置１００は、粒子数が多い順に、未割り当ての領域の各々を、割り当て済みの領域に含まれる粒子の数と未割り当ての領域に含まれる粒子の数との合計粒子数が、平均粒子数を超えないプロセスに順次割り当てる。このように、各プロセスに割り当てられる領域に含まれる粒子の数が平均粒子数を超えないように、各プロセスに割り当てられる領域に含まれる粒子の数の均等化を図ることができる。したがって、並列処理の効率化を図ることができる。
【０１０９】
また、粒子シミュレーション装置１００は、粒子数が多い順に、所定数のプロセスの各々に割り当て済みの領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる。このように、割り当て済みの領域に含まれる粒子の数が最も少ないプロセスに割り当たられるため、各プロセスに割り当てられる領域に含まれる粒子の数の均等化を図ることができる。したがって、並列処理の効率化を図ることができる。
【０１１０】
また、粒子シミュレーション装置１００は、複数の領域の各々について、袖領域に含まれる粒子の数を見積もり、見積もった袖領域に含まれる粒子の数と、領域に含まれる粒子の数と、に基づいて、領域についての計算負荷および通信負荷を示す評価値を算出する。より具体的に、粒子シミュレーション装置１００は、複数の領域の各々について、領域のサイズと袖領域のサイズとの比率と、領域に含まれる粒子の数と、に基づいて、袖領域に含まれる粒子の数を見積もる。このように、通信負荷を考慮した評価値によって領域を割り当てることができるため、各プロセスの粒子の動きの計算負荷の均等化を図ることができる。したがって、並列処理の効率化を図ることができる。
【０１１１】
また、複数の領域の各々は、直方体である。直方体のように領域の形状が単純であると、領域間におけるデータ通信のルーチンの簡単化を図ることができる。例えば、領域が直方体であれば、領域の隣接領域の特定も容易であり、並列処理にかかる時間の短縮化を図ることができる。
【０１１２】
また、本実施の形態では、複数のプロセスを実行する複数の計算ノードの処理能力については同等であるとする。そして、計算ノードとは、例えば、マルチコアプロセッサに含まれる各コアであってもよいし、プロセッサであってもよい。また、計算ノードの処理能力が異なる場合であっても、複数のプロセスに割り当てられた計算負荷が同等であれば、計算ノードの能力に基づき割り当てるプロセスの数を決定すればよいため、プロセスを計算ノードに割り当てることの容易化を図ることができる。
【０１１３】
なお、本実施の形態で説明した粒子シミュレーションにおける計算機資源配分方法は、予め用意された粒子シミュレーションプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本粒子シミュレーションプログラムは、磁気ディスク、光ディスク、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）フラッシュメモリなどのコンピュータで読み取り可能な記録媒体に記録される。そして、本粒子シミュレーションプログラムは、コンピュータによって記録媒体から読み出されることによって実行される。また、粒子シミュレーションプログラムは、インターネット等のネットワークを介して配布してもよい。なお、本実施の形態では、割り当て対象の領域を粒子の数が多い順としたが、これに限らず、粒子の数が小さい順に処理をさせてもよい。
【０１１４】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１１５】
（付記１）コンピュータに、
複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、
前記複数の領域から、前記複数の領域の各々に含まれる粒子の数の多い順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、
前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数に基づいて特定されるプロセスに順次割り当てる、
処理を実行させることを特徴とする粒子シミュレーションプログラム。
【０１１６】
（付記２）前記コンピュータに、
前記解析空間内の総粒子数を前記所定数により除算して前記所定数のプロセスの各々がシミュレートする平均粒子数を算出する処理を実行させ、
前記特定されるプロセスに順次割り当てる処理は、
前記未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち、割り当て済みの前記領域に含まれる粒子の数と前記未割り当ての領域に含まれる粒子の数との合計粒子数が、算出した前記平均粒子数を超えないプロセスに順次割り当てる、
ことを特徴とする付記１に記載の粒子シミュレーションプログラム。
【０１１７】
（付記３）前記特定されるプロセスに順次割り当てる処理は、
前記未割り当ての領域の各々に含まれる粒子の数が多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数が最も少ないプロセスに順次割り当てる、
ことを特徴とする付記１に記載の粒子シミュレーションプログラム。
【０１１８】
（付記４）前記コンピュータに、
前記複数の領域の各々について、前記領域に含まれる粒子の数に基づいて、前記解析空間のうちの前記領域から所定距離以内の領域に含まれる粒子の数を見積もり、
前記複数の領域の各々について、前記領域に含まれる粒子の数と、見積もった前記粒子の数と、に基づいて、前記領域に含まれる粒子の動きをシミュレートする場合における計算負荷と、前記領域に含まれる粒子と、前記所定距離以内にある領域に含まれる粒子との通信負荷と、を示す評価値を算出する、処理を実行させ、
前記それぞれ異なるプロセスに割り当てる処理は、
前記複数の領域から、前記複数の領域の各々について算出した前記評価値が大きい順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、
前記特定されるプロセスに順次割り当てる処理は、
前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々について算出した前記評価値が大きい順に、前記未割り当ての領域の各々を、前記所定数のプロセスのうち割り当て済みの前記領域について算出した前記評価値に基づいて特定されるプロセスに順次割り当てる、
ことを特徴とする付記１〜３のいずれか一つに記載の粒子シミュレーションプログラム。
【０１１９】
（付記５）前記所定距離以内の領域に含まれる粒子の数を見積もる処理では、
前記複数の領域の各々について、前記領域のサイズと前記所定距離以内の領域のサイズとの比率と、前記領域に含まれる粒子の数と、に基づいて、前記所定距離以内の領域に含まれる粒子の数を見積もる、
ことを特徴とする付記４に記載の粒子シミュレーションプログラム。
【０１２０】
（付記６）前記複数の領域の各々は、直方体であることを特徴とする付記１〜４のいずれか一つに記載の粒子シミュレーションプログラム。
【０１２１】
（付記７）コンピュータが、
複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、
前記複数の領域から、前記複数の領域の各々に含まれる粒子の数の多い順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、
前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数に基づいて特定されるプロセスに順次割り当てる、
処理を実行することを特徴とする粒子シミュレーションにおける計算機資源配分方法。
【０１２２】
（付記８）複数の領域を有する解析空間内の粒子の動きを前記複数の領域よりも少ない所定数のプロセスによってシミュレートする際に、前記複数の領域から、前記複数の領域の各々に含まれる粒子の数の多い順に選ばれた前記所定数の領域を、前記所定数のプロセスのうちのそれぞれ異なるプロセスに割り当て、前記複数の領域のうち、前記それぞれ異なるプロセスに割り当てられた前記所定数の領域以外の未割り当ての領域の各々に含まれる粒子の数の多い順に、前記未割り当ての領域の各々を、前記所定数のプロセスの各々に割り当て済みの前記領域に含まれる粒子の数に基づいて特定されるプロセスに順次割り当てる制御部を有することを特徴とする粒子シミュレーション装置。
【符号の説明】
【０１２３】
１００  粒子シミュレーション装置
１０１  解析空間
７０１  分割部
７０２  見積もり部
７０３  算出部
７０４  第１割り当て部
７０５  第２割り当て部
９００  粒子データ
１０００  領域データ
ｐ１〜ｐ５  プロセス
ａ１〜ａ９，ａｐ  領域
ａｓｐ  袖領域
ｎ１〜ｎ５  計算ノード
ｈ  影響半径
【図１】
0006547547.tif 000002
【図２】
0006547547.tif 000003
【図３】
0006547547.tif 000004
【図４】
0006547547.tif 000005
【図５】
0006547547.tif 000006
【図６】
0006547547.tif 000007
【図７】
0006547547.tif 000008
【図８】
0006547547.tif 000009
【図９】
0006547547.tif 000010
【図１０】
0006547547.tif 000011
【図１１】
0006547547.tif 000012
【図１２】
0006547547.tif 000013
【図１３】
0006547547.tif 000014
【図１４】
0006547547.tif 000015
【図１５】
0006547547.tif 000016
【図１６】
0006547547.tif 000017
【図１７】
0006547547.tif 000018
【図１８】
0006547547.tif 000019
【図１９】
0006547547.tif 000020
【図２０】
0006547547.tif 000021
【図２１】
0006547547.tif 000022
【図２２】
0006547547.tif 000023
【図２３】
0006547547.tif 000024