(57)【特許請求の範囲】
【請求項１】
複数のタスク処理部に対する負荷を分散させて、複数の目標物の追尾を行う並列多目標追尾装置において、
前記目標物の移動を予測し、その予測結果に応じて予測領域を生成する予測領域生成部と、
入力された観測点情報と、前記予測領域生成部にて生成された予測領域からクラスタを生成するクラスタ生成部と、
前記クラスタ生成部にて生成されたクラスタについて探索木の節を生成し、それをタスクとして分割／統合する節分割／統合部と、
前記節分割／統合部によって分割された個々の節について、その処理を行うと共に、複数単位の節が分配された場合、当該複数単位の節を１単位を除いて保持して、残った１単位の節の処理を行い、当該節の処理が終了すると、次の節の分配を要求するとともに、その要求に対する応答が返される前に保持しておいた次の１単位の節の処理を開始する複数のタスク処理部と、
前記節分割／統合部によって分割された節に対する処理として、前記各タスク処理部に対して最初に複数単位ずつ節の処理を分配し、前記タスク処理部から次の節の分配要求を受けると、当該節の分配を要求したタスク処理部に対して次の節の分配を行う負荷分散部と、
前記節分割／統合部の処理結果に基づいて前記目標物の情報を更新し、それを追尾結果として出力するとともに、前記目標物の移動予測のために前記予測領域生成部に入力する目標物航跡更新部とを備えたことを特徴とする並列多目標追尾装置。
【請求項２】
負荷分散の単位を、時間とともに小さくしていくことを特徴とする請求項１記載の並列多目標追尾装置。
【請求項３】
タスク処理部において１つの負荷分散単位の処理時間が一定時間以上長くなった場合に、当該タスク処理部が処理している節の下位の一部の節群の処理を、負荷分散部へ返すことを特徴とする請求項１記載の並列多目標追尾装置。
【請求項４】
タスク処理部が負荷分散部へ節群の処理を返すと判断する１つの負荷分散単位の処理時間の上限値を、時間とともに小さくしていくことを特徴とする請求項６記載の並列多目標追尾装置。
【請求項５】
複数のタスク処理部の内の１つを、負荷分散部と同一のプロセッサ上で動作させることを特徴とする請求項１記載の並列多目標追尾装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、レーダにおける複数目標物の追尾手法として、ＪＰＤＡ（Ｊｏｉｎｔ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｄａｔａ  Ａｓｓｏｃｉａｔｉｏｎ）のような複数の目標物の組み合わせを想定したものを採用し、処理を複数のタスク処理部に動的に割り当てて負荷分散をはかった並列多目標追尾装置に関するものである。
【０００２】
【従来の技術】
多目標追尾を並列処理する従来の追尾方法としては、例えば、処理を機能分割によって負荷分散する“Ｏｎ  Ｍａｐｐｉｎｇ  ａ  Ｔｒａｃｋｉｎｇ  Ａｌｇｏｒｉｔｈｍ  Ｏｎｔｏ  Ｐａｒａｌｌｅｌ  Ｐｒｏｃｅｓｓｏｒｓ”（ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮ  ＯＮ  ＡＥＲＯＳＰＡＣＥ  ＡＮＤ  ＥＬＥＣＴＲＯＮＩＣ  ＳＹＳＴＥＭＳ  ＶＯＬ．２６，ＮＯ．５，１９９０）に示されたもの等がある。図５および図６は従来の並列多目標追尾装置による追尾方法を示す説明図であり、追尾処理とプロセッサをグラフとして示したものである。この追尾方法では、図５のように処理をタスクグラフとして表現し、各タスクの負荷を情報の流れに基づいて、プロセッサへの分割を行なう。
【０００３】
図５は処理の関係を示すタスクグラフである。タスクグラフとは、処理の相関関係を示すグラフであり、丸印によって示される（１）〜（８）の処理と、それら各処理（１）〜（８）の繋がりを示す矢印１１０〜１１９とによって表現されている。なお、処理（１）〜（８）は計算機などで行なわれる処理自体を示しており、ここでは、タスク（１）１０１〜タスク（８）１０８としている。また、矢印１１０〜１１９はこのタスク（１）１０１〜タスク（８）１０８における計算結果が利用される先を示している。
【０００４】
すなわち、例えば、
Ｃ＝Ａ＋Ｂ  ……  （あ）
Ｅ＝Ｃ＋Ｄ  ……  （い）
という２つの処理（あ）および（い）があった場合、（あ）→（い）という矢印で表す。なお、ここで、“（あ）”および“（い）”は、“あ”および“い”を丸で囲んだ状態を示すものとする。
【０００５】
タスクグラフで表した処理は、全て、バラバラに複数のプロセッサに分割して処理させることができる。先の例でいえば、処理（あ）の計算と処理（い）の計算とをそれぞれ別のプロセッサで行なうことができる。この場合、処理（い）の計算を行うプロセッサは、処理（あ）の計算結果を処理（あ）の計算を行うプロセッサから受け取ることになる。このように、図５に示したタスクグラフにおいて、矢印１１０〜１１９で繋がっているタスク（１）１０１〜タスク（８）１０８は計算結果のやりとりが必要となる。
【０００６】
タスクグラフには当然、矢印１１０〜１１９で繋がったものと繋がっていないものとが存在するが、矢印１１０〜１１９で繋がっていないもの同士はお互いにデータをやりとりする必要はない。図５に示す例でいえば、タスク（１）１０１とタスク（２）１０２〜タスク（５）１０５は矢印１１０、１１３、１１５、１１７を介して直接繋がっており、タスク（２）１０２には矢印１１１を介してタスク（６）１０６が、タスク（５）１０５には矢印１１８を介してタスク（７）１０７がそれぞれ繋がっている。また、タスク（６）１０６、タスク（３）１０３、タスク（４）１０４、タスク（７）１０７とタスク（８）１０８は、それぞれ矢印１１２、１１４、１１６、１１９を介して直接繋がっている。従って、矢印で繋がっていないペアは、タスク（２）１０２とタスク（５）１０５のペア、およびタスク（６）１０６とタスク（７）１０７のペアである。
【０００７】
一方、タスク（１）１０１とタスク（２）１０２のペアや、タスク（２）１０２とタスク（６）１０６のペア、およびタスク（５）１０５とタスク（７）１０７のペア等は矢印１１０，１１１あるいは１１８で繋がっており、例えば、タスク（１）１０１とタスク（２）１０２なら、タスク（１）１０１の計算が終わらない限りタスク（２）１０２の計算も終わらないという関係になっている。
【０００８】
そのとき、以下に示した２通りの分け方があった場合、後者の分け方を選択するようにする。それは、前者の分け方ではプロセッサ間で計算結果を渡す必要が生じるが、後者ではその必要が生じないからである。
【０００９】
・  タスク（２）１０２とタスク（５）１０５を１つのプロセッサに割り当て、タスク（６）１０６とタスク（７）１０７を他の１つのプロセッサに割り当て
る。
・  タスク（２）１０２とタスク（６）１０６を１つのプロセッサに割り当て、タスク（５）１０５とタスク（７）１０７を他の１つのプロセッサに割り当て
る。
【００１０】
さらに、各タスク１０１〜１０８には通常、必要な計算量が示されている（図５では省略）。従って、タスクグラフに与えられている処理を複数のプロセッサに分ける場合、以下の２つの方針に基づいて行うことになる。
【００１１】
各プロセッサに分けたタスクの必要計算量の合計がなるべく同じになるように割り当てる。
【００１２】
矢印１１０〜１１９で繋がっているタスク１０１〜１０８同士は、同じプロセッサに割り当てる。
【００１３】
図６はプロセッサグラフであり、4つのプロセッサ（Ｐ１）１２１〜（Ｐ２）１２４が環状に繋がっている例を示している。すなわち、プロセッサ（Ｐ１）１２１にプロセッサ（Ｐ２）１２２が繋がり、プロセッサ（Ｐ２）１２２にプロセッサ（Ｐ３）１２３が繋がり、プロセッサ（Ｐ３）１２３にプロセッサ（Ｐ４）１２４が繋がり、プロセッサ（Ｐ４）１２４にプロセッサ（Ｐ１）１２１が繋がっている。
【００１４】
このように矢印１１０〜１１９で繋がっているタスク１０１〜１０８同士を同じプロセッサ１２１〜１２４に割り当てるというのが、従来の並列多目標追尾装置で用いられている追尾方法である。この図５に示されているタスクグラフで、丸で表現されているタスク１０１〜１０８は機能的に一塊となる処理である。ＪＰＤＡ等のように、目標物と観測点の組合せを考慮して追尾処理を行う場合、対象とする問題が大きくなると、目標物と観測点との組合せを求めるタスクは、他のタスクに比べて、処理の負荷が非常に大きくなる。
【００１５】
【発明が解決しようとする課題】
従来の並列多目標追尾装置は以上のように構成されているので、ＪＰＤＡのように複数の目標物と観測点の組合せを考慮して追尾処理を行なう方式では、目標物と観測点の組合せを求めるための特定の１つのタスク１０１〜１０８の処理の負荷が特別に非常に大きくなってしまうことがあり、その場合には、上述したように複数のプロセッサ１２１〜１２４を用いて各タスク１０１〜１０８の並列処理を行っても、負荷が特別大きくなってしまうタスク１０１〜１０８の処理を行ったプロセッサ１２１〜１２４だけは処理が終わらず、結果として、全体の処理が完全に終わるまでに長時間を要し、複数のプロセッサ１２１〜１２４を用いた負荷分散効果が得られず、並列処理を行っている意味がなくなってしまうという課題があった。
【００１６】
目標物と観測点の組合せを求めるためのタスク１０１〜１０８を処理負荷ができるだけ均等になるように分割し、それぞれを別プロセッサ１２１〜１２４で処理することは可能である。しかしながら、各プロセッサ１２１〜１２４が汎用のワークステーションで動作する場合、目標物と観測点の組合せを求めるタスク１０１〜１０８以外の他の処理や他のユーザの処理も、同一のプロセッサ１２１〜１２４上で実行される可能性があり、それら他の処理が各プロセッサ１２１〜１２４で一定になるとは限らず、各プロセッサ１２１〜１２４で処理されるタスク１０１〜１０８の実行時間も均等にはならず、最適な負荷分散とはならなくなってしまうという課題があった。
【００１７】
また、各プロセッサ（ワークステーション）１２１〜１２４では、目標物と観測点の組合せを求めるためのタスク１０１〜１０８以外の処理は行なわないことにしても、各プロセッサ１２１〜１２４が汎用のネットワークで接続されている場合は、タスク１０１〜１０８の処理を行うプロセッサ１２１〜１２４以外のプロセッサも、同じネットワークを共有して使用していることが考えられ、そのような場合には、プロセッサ１２１〜１２４間の通信時間が一定にはならないので、各プロセッサ１２１〜１２４でのタスク１０１〜１０８の処理の終了が一定とはならず、最適な負荷分散とはならなくなってしまうという課題があった。
【００１８】
この発明は上記のような課題を解決するためになされたもので、目標物と観測点の組合せを求めるタスク等の特別高負荷となってしまうタスクに対して負荷分散を行い、タスクを実行するプロセッサ上で他の処理が動作していたり、ネットワーク上で他の通信がなされている状態であっても、並列多目標追尾処理において、最適な負荷分散を行なうことが可能な並列多目標追尾装置を得ることを目的とする。
【００１９】
【課題を解決するための手段】
この発明に係る並列多目標追尾装置は、クラスタ生成部が観測点情報と予測領域より生成したクラスタについて、節分割／統合部にて探索木の節を生成し、それをタスクとして複数のタスク処理部に分配して処理する際に、負荷分散部によって、各タスク処理部への節の処理の分配を、各タスク処理部の負荷状況に応じて行うようにし、かつ、負荷分散部より各タスク処理部に対して、最初に複数単位ずつの節の処理を分配し、各タスク処理部では受け取った節の内の１単位の節の処理を開始して、残りを保持しておき、当該節の処理が終了すると、次の節の分配を負荷分散部に要求するとともに、その要求に対する応答が返される前に保持しておいた次の１単位の節の処理を開始し、分配要求を受けた負荷分散部は、節の分配を要求したタスク処理部に対して次の節の分配を行うようにしたものである。
【００２３】
この発明に係る並列多目標追尾装置は、時間とともに負荷分散の単位を小さくしていくようにしたものである。
【００２４】
この発明に係る並列多目標追尾装置は、１つの負荷分散単位の処理時間が一定時間以上になると、処理している節の下の一部の節群の処理を負荷分散部へ返すようにしたものである。
【００２５】
この発明に係る並列多目標追尾装置は、一部の節群の処理を負荷分散部へ返すと判断する際の処理時間の上限値を、時間とともに小さくしていくようにしたものである。
【００２６】
この発明に係る並列多目標追尾装置は、負荷分散部と同一のプロセッサ上でタスク処理部の１つを動作させるようにしたものである。
【００２７】
【発明の実施の形態】
以下、この発明の実施の一形態を説明する。
実施の形態１．
図１はこの発明の実施の形態１による並列多目標追尾装置の構成を示すブロック図である。図において、１は外部からの観測点情報の入力が行われる入力線である。２は目標物の移動を予測し、その予測結果に応じて予測領域を生成する予測領域生成部である。３は入力線１から入力された観測点情報と、予測領域生成部２の生成した予測領域からクラスタを生成するクラスタ生成部である。４はこのクラスタ生成部３で生成されたクラスタについて探索木の節を生成し、これをタスクとして分割／統合を行う節分割／統合部である。５ａ〜５ｄは節分割／統合部４で分割された個々のタスク（節）についての処理を行うタスク処理部である。６は節分割／統合部４で統合されたタスク処理部５ａ〜５ｄの処理結果に基づいて、目標物の持つ情報（航跡）の更新を行う目標物航跡更新部である。７は目標物航跡更新部６で更新された情報を追尾結果として外部に出力する出力線である。８ａ〜８ｄはこれら各部の処理結果の転送に用いる転送線である。
【００２８】
また、９は節分割／統合部４によって分割された節に対する処理を、各タスク処理部５ａ〜５ｄに対して、それぞれの負荷状況に基づいて分散して割り当てる負荷分散部である。８ｆはこの負荷分散部９と節分割／統合部４との間を結ぶ転送線であり、８ｇは負荷分散部９と各タスク処理部５ａ〜５ｄとの間を結ぶ転送線である。
【００２９】
次に動作について説明する。
クラスタ生成部３には、外部からの観測点情報が入力線１を介して、また予測領域生成部２の作成した予測領域が転送路８ａを介してそれぞれ入力される。これら観測点情報および予測領域を受けたクラスタ生成部３は、複数の目標物の予測領域が重なり、かつその重なった領域に観測点が存在する時には、その予測領域を結合して１つのクラスタを生成する。このクラスタ生成部３で生成された１つのクラスタの情報（観測点と目標物の予測領域）は、転送路８ｂを介して節分割／統合部４に送られ、節分割／統合部４は受け取ったクラスタの情報から探索木の節を生成する。
【００３０】
負荷分散部９はこの節分割／統合部４によって生成された節を転送路８ｆを介して取り込み、各タスク処理部５ａ〜５ｄの負荷状況に応じて、その節の処理を転送路８ｇを介して各タスク処理部５ａ〜５ｄに分配する。各タスク処理部５ａ〜５ｄは受け取った節から、探索木の葉（追尾の組合せの１つに相当する）を求め、その処理結果を転送路８ｇおよび８ｆを介して節分割／統合部４へ送る。節分割／統合部４は送られてきた各タスク処理部５ａ〜５ｄの処理結果を統合し、それを転送路８ｃを介して目標物航跡更新部６に送る。目標物航跡更新部６は目標物の情報を持ち、送られてきた個々の組合せの可能性をもとに、目標物の情報を更新する。この目標物航跡更新部６にて更新された目標物の情報は、出力線７を介して外部に出力されるとともに、転送線８ｄを介して予測領域生成部２へも送られる。予測領域生成部２はこの目標物航跡更新部６で更新された目標物の情報に基づいて各目標物について移動予測を行い、その予測領域を生成して転送線８ａよりクラスタ生成部３に送る。
この装置は、以上の動作を繰り返すことによって、動的負荷分散を用いた並列多目標追尾装置として動作する。
【００３１】
以下、ＪＰＤＡを用いる場合を例に、各部の動作を説明する。
ここで、図２はＪＰＤＡにおける目標物と観測点の関係を示す説明図、図３はこの目標物と観測点の関係を表した行列Ωを示す説明図、図４は目標物と観測点の組合せを表した探索木を示す説明図である。図２において、ｔ（１）およびｔ（２）は目標物であり、黒丸で示したこの目標物ｔ（１），ｔ（２）の予測座標を中心とする楕円は予測範囲である。また、ｙ（１）〜ｙ（４）はそれぞれ観測点である。
【００３２】
なお、図３に示す行列Ωはそれぞれ、縦が目標物ｔ（０）〜ｔ（２）、横が観測点ｙ（１）〜ｙ（４）で分かれており、目標物ｔ（０）は対応する目標なしを示している。また、行列Ω内の“１”は可能性ありを、“０”は可能性なしをそれぞれ示しており、この行列Ωは次の内容を表したものである。
・  観測点ｙ（１）は、目標物ｔ（２）、もしくは対応する目標なし
・  観測点ｙ（２）は、目標物ｔ（１）、もしくは目標物ｔ（２）、もしくは対応する目標なし
・  観測点ｙ（３）は、目標物ｔ（１）、もしくは対応する目標なし
・  観測点ｙ（４）は、目標物ｔ（１）、もしくは対応する目標なし
【００３３】
これを満たす目標物と観測点の組合せとしては、次のケースがある。
・  目標物ｔ（１）が観測点ｙ（２）で、目標物ｔ（２）が観測点ｙ（１）
・  目標物ｔ（１）が観測点ｙ（２）で、目標物ｔ（２）が対応なし
・  目標物ｔ（１）が観測点ｙ（３）で、目標物ｔ（２）が観測点ｙ（１）
・  目標物ｔ（１）が観測点ｙ（３）で、目標物ｔ（２）が観測点ｙ（２）
・  目標物ｔ（１）が観測点ｙ（３）で、目標物ｔ（２）が対応なし
・  目標物ｔ（１）が観測点ｙ（４）で、目標物ｔ（２）が観測点ｙ（１）
・  目標物ｔ（１）が観測点ｙ（４）で、目標物ｔ（２）が観測点ｙ（２）
・  目標物ｔ（１）が観測点ｙ（４）で、目標物ｔ（２）が対応なし
・  目標物ｔ（１）が対応なしで、目標物ｔ（２）が観測点ｙ（１）
・  目標物ｔ（１）が対応なしで、目標物ｔ（２）が観測点ｙ（２）
・  目標物ｔ（１）が対応なしで、目標物ｔ（２）が対応なし
【００３４】
図４はこの組合せを探索木として表したものである。この探索木における各呼称は、図４では次の部分に対応しており、組合せは、根から葉までの各ノードの持つ状態に対応する。
・  根      →  Ｒｏｏｔ
・  節      →  木構造の分岐の中段に位置する、図４に楕円で示した部分
・  葉      →  木構造の分岐の先端に位置する、図４に四角で示した部分
・  枝      →  図４の根と節、節と節、節と葉を結ぶ線
・  ノード  →  節と葉の両方を含む概念
・  兄弟    →  根からノードまでに経由する枝数が等しいノード同士
【００３５】
以上を前提として、各部の動作を具体的に説明する。
まず予測領域生成部２が、その内部に保持している目標物の情報（座標や速度など）から、観測点が観測された時間に対応する目標物ｔ（１）およびｔ（２）の予測座標を算出する。また、同様に一定の存在確率以上となる、当該目標物ｔ（１），ｔ（２）の予測座標を中心とする予測領域（図２の楕円）を算出する。次にクラスタ生成部３が、その予測領域と観測点ｙ（１）〜ｙ（４）との包含関係を調べる。複数の予測領域に含まれる観測点が存在する時、その観測点を包含する予測領域同士を結合してクラスタを形成する。図２に示す例では、観測点ｙ（２）が２つの予測領域に含まれるため、この２つの予測領域を１つのクラスタとして結合する。
【００３６】
生成されたクラスタは節分割／統合部４に送られ、節分割／統合部４はそれより図４に示す探索木の節を生成する。負荷分散部９はこの節分割／統合部４が生成した節を取り込み、各タスク処理部５ａ〜５ｄの負荷状況に応じて、その節の処理をタスク処理部５ａ〜５ｄに分配する。ここで、タスク処理部５ａ〜５ｄへ分配する節のレベルは、図４の観測点ｙ（１）であっても、ｙ（２）であっても、ｙ（３）であっても構わない。なお、下位のレベルになるに従って、各節に対する処理量は通常小さくなる。各タスク処理部５ａ〜５ｄは、この負荷分散部９によって分配された節から葉を算出し、各葉が示す組合せごとに信頼度を計算して、目標物と各観測点の対応関係についての重み付けを行う。
【００３７】
例えば、図４において、節１０を受け取ったタスク処理部は、各組合せごとの信頼度として、以下の信頼度E（１）〜E（３）を計算する。
E（１）→  観測点ｙ（１）が対応なし、観測点ｙ（２）が目標物ｔ（２）、観測点ｙ（３）、ｙ（４）が対応なしのケースの信頼度
E（２）→  観測点ｙ（１）が対応なし、観測点ｙ（２）が目標物ｔ（２）、観測点ｙ（３）が対応なし、観測点ｙ（４）が目標物ｔ（１）のケースの信頼度
E（３）→  観測点ｙ（１）が対応なし、観測点ｙ（２）が目標物ｔ（２）、観測点ｙ（３）が目標物ｔ（１）、観測点ｙ（４）が対応なしのケースの信頼度
【００３８】
次に当該タスク処理部５ａ〜５ｄは、計算した信頼度の値をもとに、図４に示した節１０での目標物と各観測点の対応関係について、以下の重み付けを行う。
・  目標物ｔ（１）が観測点ｙ（３）に対応する重みを、E（３）  ・  目標物ｔ（１）が観測点ｙ（４）に対応する重みを、E（２）  ・  目標物ｔ（１）が対応なしとなる重みを、E（１）
・  目標物ｔ（２）が観測点ｙ（２）に対応する重みを、Ｅ（１）＋Ｅ（２）＋Ｅ（３）
【００３９】
次に節分割／統合部４は、各タスク処理部５ａ〜５ｄが算出した「目標物と各観測点の対応関係についての重み」を集計する。例えば、目標物ｔ（２）であれば、観測点ｙ（１）に対応する重み、観測点ｙ（２）に対応する重み、および対応なしとなる重みが得られる。
【００４０】
目標物航跡更新部６はこの節分割／統合部４が統合した後の情報を受け取り、目標物の位置を算出して、目標物の座標や速度等の内部情報の更新を行う。例えば、目標物ｔ（２）であれば、上記３つの重み付けに基づいて目標物ｔ（２）の座標を求める。なお、この重み付けに基づいた計算結果を、当該目標物の座標と見倣す。
以上で各部の動作が終了する。
【００４１】
次に、タスク処理部５ａ〜５ｄにおける、それぞれの負荷状況に応じた節の分配について説明する。
まず、負荷分散部９は、節分割／統合部４が生成した探索木のあるレベルの全ての節の処理を均等に各タスク処理部５ａ〜５ｄに分配する。均等に節の処理を分配する方法には、節の数を均等にする、あるいは、節の下位の葉の数を均等にするなどが考えられる。
【００４２】
次に、負荷分散部９が転送線８ｇを介して各タスク処理部５ａ〜５ｄに負荷の報告要求を出し、各タスク処理部５ａ〜５ｄはその要求に応えて負荷状況を負荷分散部９に報告する。ここで、負荷状況には、オペレーティングシステムで管理しているジョブ・キューの単位時間当たりの長さ、すなわち、ジョブ・キューに入っているジョブの数、あるいは、各タスク処理部５ａ〜５ｄがまだ処理していない節や葉の数などが考えられる。
【００４３】
次に、負荷分散部９は各タスク処理部５ａ〜５ｄからの負荷状況の報告を受け取ると、その情報をもとに、各タスク処理部５ａ〜５ｄの負荷が均等となるように、各タスク処理部５ａ〜５ｄに節の移動を要求する。ここで、例えば負荷状況を各タスク処理部５ａ〜５ｄの未処理の節の数とした場合、各タスク処理部５ａ〜５ｄからの負荷状況の報告が、それぞれ３，５，４，４であったものとする。これより、全てのタスク処理部５ａ〜５ｄにおける未処理の節の数は３＋５＋４＋４＝１６なので、４つのタスク処理部５ａ〜５ｄの負荷状態を均等化した場合、各タスク処理部５ａ〜５ｄの担当すべき節の数は４つずつとなる。従って、負荷分散部９は転送線８ｇを介して、タスク処理部５ｂに１つの節の処理をタスク処理部５ａに移動するように指示する。これにより、各タスク処理部５ａ〜５ｄの未処理の節の数が４つずつと等しくなる。
この負荷状況の収集とそれによる各タスク処理部５ａ〜５ｄ間の節の移動を定期的に行う。
【００４４】
以上のように、この実施の形態１によれば、負荷分散部９が、各タスク処理部５ａ〜５ｄの負荷状況に応じて、節の処理をタスク処理部５ａ〜５ｄに分配しているので、各タスク処理部５ａ〜５ｄが汎用のワークステーションのように他の処理が行われているマシン上で動作する場合でも、各タスク処理部５ａ〜５ｄの処理時間が均等になり、最適な負荷分散を行うことが可能になるという効果が得られる。
【００４５】
また、各タスク処理部５ａ〜５ｄの未処理の節の数が定期的に均等化されるので、節の処理以外の処理がタスク処理部５ａ〜５ｄと同一のプロセッサ上で行われていても、各タスク処理部５ａ〜５ｄの全ての節の処理がほぼ同じ時間で終了し、最適な負荷分散が行えるという効果も得られる。
【００４６】
実施の形態２．
以上の実施の形態１では、負荷分散部９が負荷分散のタイミングの主導権を取って、定期的に各タスク処理部５ａ〜５ｄの負荷を均等化することにより、各タスク処理部５ａ〜５ｄにおける節の処理をほぼ同じ時間で終了させるものについて説明したが、タスク処理部５ａ〜５ｄが負荷分散のタイミングの主導権を取り、負荷分散部９に対して仕事の転送要求を行うようにしてもよい。この実施の形態２はそのような並列多目標追尾装置について述べたもので、その構成は図１に示した実施の形態１の場合と同様であるため、ここではその説明は省略する。
【００４７】
次に動作について説明する。なお、ここでは実施の形態１とは異なる部分についての説明を行う。
まず、負荷分散部９は、節分割／統合部４が生成した探索木の、あるレベルの節の処理を１単位ずつ各タスク処理部５ａ〜５ｄに分配する。各タスク処理部５ａ〜５ｄではその探索木の節を受け取るとその処理を開始する。各タスク処理部５ａ〜５ｄは受け取った節の処理が終了して負荷がなくなると、負荷分散部９に対して次の仕事、すなわち処理する節の転送を要求する。負荷分散部９はその転送要求を受け取ると、当該要求を出したタスク処理部５ａ（〜５ｄ）に対して１単位の節の処理（負荷）を与える。
以上の処理を全ての節がなくなるまで繰り返す。
【００４８】
以上のように、この実施の形態２によれば、各タスク処理部５ａ〜５ｄは仕事がなくなると次の仕事の転送要求を負荷分散部９へ出すので、節の処理以外の処理が同一マシン上で行われていても、各タスク処理部５ａ〜５ｄの全ての節の処理がほぼ同じ時間で終了し、最適な負荷分散が行えるという効果が得られ、さらに、１つの節の処理に対応する処理量が小さい場合でも、定期的な負荷状況の収集処理が必要ないので、負荷分散のオーバヘッドが少なくなるという効果も得られる。
【００４９】
実施の形態３．
上記各実施の形態では、各タスク処理部５ａ〜５ｄは１つの節の処理が完了してから次の節の処理の転送要求を負荷分散部９に出す場合について説明したが、タスク処理部５ａ〜５ｄに仕事をある程度確保しておき、それを順次処理してゆくようにしてもよい。この実施の形態３はそのような並列多目標追尾装置について述べたもので、その構成は図１に示した実施の形態１の場合と同様であるため、ここではその説明は省略する。
【００５０】
次に動作について説明する。なお、この場合にも実施の形態１とは異なる部分についての説明を行う。
まず、負荷分散部９は最初に、節分割／統合部４が生成した探索木のあるレベルの節の処理を複数単位ずつ各タスク処理部５ａ〜５ｄに分配する。各タスク処理部５ａ〜５ｄは、この複数単位の節を受け取ると、その内の１単位を除く残りの節を保持し、保持していない残りの１単位の節の処理を実行する。各タスク処理部５ａ〜５ｄは当該節の処理が終了すると、負荷分散部９に対して次の仕事、すなわち次に処理すべき節の転送を要求する。そしてこの転送要求に対する応答が負荷分散部９より返される前に、保持しておいた節の内の１単位の節を取り出してその処理を開始する。負荷分散部９はタスク処理部５ａ（〜５ｄ）から次に処理する節の転送要求を受け取ると、当該要求を送出したタスク処理部５ａ（〜５ｄ）に対して、次の節の処理の分配を行う。また、要求を出したタスク処理部５ａ（〜５ｄ）は、負荷分散部９から次に処理するの節の分配を受けると、それを保持する。
以上の処理を全ての節がなくなるまで繰り返す。
【００５１】
以上のように、この実施の形態３によれば、各タスク処理部５ａ〜５ｄは仕事がなくなると、負荷分散部９に対して次の仕事の転送要求を出すとともに、保持しておいた節の処理をすぐに開始しているので、負荷分散部９へ次の仕事の転送要求を出してからその応答を受け取るまでの間も、他の節の処理が実行されていて、タスク処理部５ａ〜５ｄが節の処理を行っていない時間がほとんどなくなるため、最適な負荷分散が行えるという効果が得られる。
【００５２】
実施の形態４．
上記各実施の形態では、負荷分散の単位を一定としているものについて説明したが、負荷分散の単位を時間とともに小さくするようにしてもよい。この実施の形態４はそのような並列多目標追尾装置について述べたもので、その構成は図１に示した実施の形態１の場合と同様であるため、ここではその説明は省略する。
【００５３】
ここで、並列多目標追尾装置における負荷分散の単位は節であるが、その処理量に相当するサイズは、例えば節の下位の葉の数で測ることができる。図４に示した探索木からも分かるように、葉の数は節のレベルが上がるほど増加し、レベルが下がるほど減少する。従って、負荷分散に際して、節を分解してよりレベルの低い節を負荷分散の単位とすることにより、より小さなサイズの仕事を生成することは容易である。
【００５４】
ここで、負荷分散の単位のサイズは、小さければ小さいほど負荷を分散する回数が増えるため負荷分散のためのオーバヘッドが大きくなるが、処理の終了を各タスク処理部５ａ〜５ｄで均一化するという面では小さいほどよい。従って、最初は高いレベルの節を負荷分散の単位とし、処理が進むにつれて節を分解し、より低いレベルの節を負荷分散の単位とすることで、負荷分散オーバヘッドを抑えた上で、各タスク処理部５ａ〜５ｄの節の処理の終了を均一化し、最適な負荷分散を行うことができる。
【００５５】
なお、時間とともに負荷分散の単位を小さくする場合、実施の形態１のように各タスク処理部５ａ〜５ｄが仕事（すなわち節の処理）を保持しているときには、各タスク処理部５ａ〜５ｄで節を分解する。また実施の形態２のように負荷分散部９が節の処理を保持しているときには、負荷分散部９で節を分解し、実施の形態３のように負荷分散部９および各タスク処理部５ａ〜５ｄで節の処理を保持しているときには、負荷分散部９および各タスク処理部５ａ〜５ｄの両方で節を分解する。
【００５６】
以上のように、この実施の形態４によれば、時間とともに負荷分散の単位を小さくしているので、負荷分散のオーバヘッドを抑えた上で、各タスク処理部５ａ〜５ｄの節の処理の終了を均一化し、最適な負荷分散を行うことができるという効果が得られる。
【００５７】
実施の形態５．
上記実施の形態４では、時間とともに負荷分散の単位を小さくする場合について説明したが、時間によらずに、１つの負荷分散単位の処理時間が一定以上長くなった場合に負荷分散単位を小さくするようにしてもよい。この実施の形態５はそのような並列多目標追尾装置について述べたもので、その構成は図１に示した実施の形態１の場合と同様であるため、ここではその説明は省略する。
【００５８】
探索木の同じレベルの節の処理を負荷分散の単位としている場合、節によってはその下位の葉の数は均等ではない。従って、ある節の下位の葉の数が非常に多い場合は、その節の処理に非常に長い時間がかかり、最悪の場合、他の節の処理は全て完了しているのに、その節の処理だけが残ってしまうということがあり得る。
【００５９】
そこで、各タスク処理部５ａ〜５ｄでは節の処理時間を監視しており、ある節の処理を行っている最中に、その節の処理を開始してからの実行時間がある一定時間以上経過した場合、その節の下位のまだ処理していない節群の一部を負荷分散部９に返す。そして実施の形態１の場合のように、各タスク処理部５ａ〜５ｄが仕事（節の処理）を保持している場合には、次の負荷分散のタイミングまで返された節群を保持しておき、次回の負荷分散の際に負荷の低いタスク処理部５ａ〜５ｄに対してその節群の処理を分配する。また、実施の形態２の場合のように負荷分散部９が節の処理を保持している場合には、返された節群をそのまま保持して既に保持している節と同様に扱い、実施の形態３の場合のように負荷分散部９および各タスク処理部５ａ〜５ｄで節の処理を保持している場合も同様に、返された節群をそのまま保持して既に保持している節と同様に扱う。
【００６０】
以上のように、この実施の形態５によれば、処理時間の非常にかかる節の処理の一部を負荷分散部９へ返すことにより、処理能力に余裕のある他のタスク処理部５ａ〜５ｄへそれらの節群の処理を分散しているので、負荷が分散され、全体として処理が早く終了するようになり、最適な負荷分散が行えるという効果が得られる。
【００６１】
実施の形態６．
上記実施の形態５では、タスク処理部５ａ〜５ｄが未処理の節群の処理を負荷分散部９に返すと判断する１つの負荷分散単位の処理時間の上限値を、一定にしたものについて説明したが、当該上限値を時間とともに小さくするようにしてもよい。この実施の形態６はそのような並列多目標追尾装置について述べたもので、その構成は図１に示した実施の形態１の場合と同様であるため、ここではその説明は省略する。
【００６２】
タスク処理部５ａ〜５ｄが未処理の節群の処理を負荷分散部９へ返す場合、返すと判断する１つの負荷分散単位の処理時間の上限値は、それが大きいと、負荷分散部９へ返すと判断した時には既に他のタスク処理部５ａ〜５ｄの処理が完了している危険性があり、小さいと他のタスク処理部５ａ〜５ｄの処理が当分完了しないのにも係わらず未処理の節群の処理が負荷分散部９へ返されることになるため、無駄な仕事の移動になるという危険性がある。
【００６３】
そこで、最初のうちは、この未処理の節群の処理を負荷分散部９へ返すと判断する上限値を大きくしておき、時間とともにそれを小さくしていく。それにより、最初のうちは大きな上限値により、無駄となる負荷分散部９への節群の返却を抑えることができる。また、全体の処理の最後の方では、小さな上限値により他のタスク処理部５ａ〜５ｄが処理を完了する前に、処理に時間のかかっているタスク処理部５ａ〜５ｄの仕事の一部を他のタスク処理部５ａ〜５ｄへ分散させることができ、最適な負荷分散とすることができる。
【００６４】
以上のように、この実施の形態６によれば、負荷分散部９に節群を返却する際の負荷量の上限値を時間とともに小さくしているので、最初のうちは無駄となる節群の返却を抑えることができ、処理の最後の方では、処理に時間がかかっているタスク処理部５ａ〜５ｄの仕事の一部を他のタスク処理部５ａ〜５ｄへ確実に分散させることができるようになり、最適な負荷分散を行うことが可能になるという効果が得られる。
【００６５】
実施の形態７．
上記各実施の形態では、各タスク処理部５ａ〜５ｄと負荷分散部９とを異なるプロセッサ上で動作させたものについて説明したが、複数のタスク処理部５ａ〜５ｄの内の１つを負荷分散部９と同一のプロセッサ上で動作させるようにしてもよい。節の処理を行っている際の負荷は、タスク処理部５ａ〜５ｄで最も高く、負荷分散部９にはほとんど負荷がない。従って、負荷分散部９をタスク処理部５ａ〜５ｄの１つと同一プロセッサ上で動作させることにより、全てのプロセッサの負荷を高い状態とすることができる。
【００６６】
以上のように、この実施の形態７によれば、タスク処理部５ａ〜５ｄの１つと同一プロセッサ上で負荷分散部９を動作させているので、全てのプロセッサでその負荷を高い状態とすることができ、無駄のない並列処理が可能となるという効果が得られる。
【００６７】
【発明の効果】
以上のように、この発明によれば、負荷分散部を設け、クラスタについて生成された探索木の節を複数のタスク処理部に分配して処理する際に、各タスク処理部の負荷状況に応じて節の処理を分配するように構成したので、各タスク処理部が、他の処理を実行しているプロセッサ上で動作するような場合でも、各タスク処理部の処理時間を均等にすることができ、最適な負荷分散を行うことが可能な並列多目標追尾装置が得られるという効果がある。
また、この発明によれば、各タスク処理部に対して負荷分散部より、最初に複数単位ずつの節の処理を分配し、各タスク処理部ではその内の１単位の節の処理を開始して、残りを保持しておき、当該節の処理が終了すると、次の節の分配を負荷分散部に要求するとともに、その要求に対する応答が返される前に保持しておいた次の１単位の節の処理を開始するように構成したので、各タスク処理部は仕事がなくなると次の仕事の転送要求を負荷分散部に対して出すとともに、保持しておいた節の処理がすぐに開始されるため、負荷分散部への節の転送要求を出してから対応する節の転送を受けるまでの間も、保持されている他の節の処理が実行されて、タスク処理部が節の処理を行っていない時間がほとんどなくなり、最適な負荷分散が可能になるという効果がある。
【００７１】
この発明によれば、負荷分散の単位を時間とともに小さくしていくように構成したので、負荷分散のオーバヘッドを抑えた上で、各タスク処理部における節の処理の終了を均一化することができ、最適な負荷分散が可能になるという効果がある。
【００７２】
この発明によれば、１つの負荷分散単位の処理時間が一定以上になると、処理している節の下位の一部の節群の処理を負荷分散部へ返すように構成したので、負荷分散により、処理能力に余裕のある他のタスク処理部にそれらの節群の処理を分配することができ、全体として処理が早く終了するようになるため、最適な負荷分散が可能になるという効果がある。
【００７３】
この発明によれば、一部の節群の処理を負荷分散部へ返すと判断する際の処理時間の上限値を、時間とともに小さくしていくように構成したので、最初のうちは大きな上限値により、無駄となる負荷分散部への節群の返却を抑えることができ、全体の処理の最後の方では小さな上限値により、他のタスク処理部の仕事が完了する前に処理に時間のかかっているタスク処理部の仕事の一部を他のタスク処理部へ分散させることができるため、最適な負荷分散が可能になるという効果がある。
【００７４】
この発明によれば、同一のプロセッサ上でタスク処理部の１つと負荷分散部とを動作させるように構成したので、全てのプロセッサでその負荷を高い状態とすることができ、無駄のない並列処理が可能となるという効果がある。
【図面の簡単な説明】
【図１】  この発明による並列多目標追尾装置の構成を示すブロック図である。
【図２】  この発明の並列多目標追尾装置におけるＪＰＤＡによる目標物と観測点の関係を示す説明図である。
【図３】  この発明の並列多目標追尾装置における目標物と観測点の関係を表した行列Ωを示す説明図である。
【図４】  この発明の並列多目標追尾装置における目標物と観測点の組合せを表した探索木を示す説明図である。
【図５】  従来の並列多目標追尾装置における追尾処理のタスクグラフを示す説明図である。
【図６】  従来の並列多目標追尾装置における追尾処理のプロセッサグラフを示す説明図である。
【符号の説明】
１  入力線、２  予測領域生成部、３  クラスタ生成部、４  節分割／統合部、５ａ〜５ｄ  タスク処理部、６  目標物航跡更新部、７  出力線、８ａ〜８ｄ，８ｆ，８ｇ  転送路、９  負荷分散部、１０  節、ｔ（１），ｔ（２）  目標物、ｙ（１）〜ｙ（４）  観測点。
【図１】
0003645135.tif 000002
【図２】
0003645135.tif 000003
【図３】
0003645135.tif 000004
【図４】
0003645135.tif 000005
【図５】
0003645135.tif 000006
【図６】
0003645135.tif 000007