(57)【要約】  複数の処理装置１０−１〜１０−ｎと、複数の処理装置１０−１〜１０−ｎと通信可能な割当て装置２０とを備え、各処理装置は、マッチング処理対象のデータを格納するキューイング部１１と、キューイング部１１に格納されたデータについてマッチング処理を実施するマッチング部１２とを含み、割当て装置２０は、マッチング処理すべきデータを入力するたびに、複数の処理装置１０−１〜１０−ｎの中から、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置のキューイング部１１に当該データを格納するタスク割当て部２１と、各処理装置におけるマッチング処理の結果を収集し外部システムに応答する応答部２２とを含む。
2014030300.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理装置と、前記複数の処理装置と通信可能な割当て装置とを備え、
各処理装置は、
マッチング処理対象のデータを格納するキューイング部と、
キューイング部に格納されたデータについてマッチング処理を実施するマッチング部とを含み、
前記割当て装置は、
マッチング処理すべきデータを入力するたびに、前記複数の処理装置の中から、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置のキューイング部に当該データを格納するタスク割当て部と、
各処理装置におけるマッチング処理の結果を収集し外部システムに応答する応答部とを含む
ことを特徴とするマッチングシステム。
【請求項２】
割当て装置のタスク割当て部は、各処理装置における処理負荷が均一になるように、マッチング処理を実施させる処理装置を選択する
請求項１に記載のマッチングシステム。
【請求項３】
処理装置のキューイング部は、マッチング元データを格納する親キューと、マッチング先データを格納する子キューとを含み、
処理装置のマッチング部は、前記キューイング部の親キュー内のデータと、子キュー内のデータとを総当りでマッチングし、
割当て装置のタスク割当て部は、マッチング処理すべきデータを入力するたびに、選択した処理装置の親キューと、全ての処理装置の子キューに当該データを投入する
請求項１または請求項２に記載のマッチングシステム。
【請求項４】
処理装置のマッチング部は、親キュー内のデータとマッチングするデータとして、子キュー内のデータのうち、親キュー内のデータよりも後に到着または発生したデータを選択し、
割当て装置のタスク割当て部は、親キューにデータを投入する処理装置を選択する際、すべての処理装置を順に選択したのち逆順に処理装置を選択する選択処理を繰り返す
請求項３に記載のマッチングシステム。
【請求項５】
割当て装置が、マッチング処理すべきデータを入力するたびに、マッチング処理を実施する複数の処理装置の中から、各処理装置における処理負荷が均一になるように、当該データに対するマッチング処理を実施させる処理装置を選択し、
選択した処理装置が、当該データに対するマッチング処理を実施し、
前記割当て装置が、各処理装置におけるマッチング処理の結果を収集し外部システムに応答する
ことを特徴とするマッチング方法。
【請求項６】
割当て装置が、マッチング処理すべきデータを入力するたびに、マッチング元データを格納する親キューとマッチング先データを格納する子キューとを含む複数の処理装置の中から、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置の親キューと、全ての処理装置の子キューに当該データを投入し、
各処理装置が、親キュー内のデータと子キュー内のデータとを総当りでマッチングする
請求項５に記載のマッチング方法。
【請求項７】
割当て装置が、親キューにデータを投入する処理装置を選択する際、すべての処理装置を順に選択したのち逆順に処理装置を選択する選択処理を繰り返し、
各処理装置が、親キュー内のデータとマッチングするデータとして、子キュー内のデータのうち、親キュー内のデータよりも後に到着または発生したデータを選択する
請求項６に記載のマッチング方法。
【請求項８】
マッチング処理を実施する複数の処理装置と通信可能なコンピュータに、
マッチング処理すべきデータを入力するたびに、前記複数の処理装置の中から、各処理装置における処理負荷が均一になるように、当該データに対するマッチング処理を実施させる処理装置を選択する処理と、
各処理装置が実施したマッチング処理の結果を収集し外部システムに応答する処理とを実行させる
ためのマッチングプログラム。
【請求項９】
コンピュータに、
マッチング処理すべきデータを入力するたびに、マッチング元データを格納する親キューとマッチング先データを格納する子キューとを含む複数の処理装置の中から、当該データに対するマッチング処理を実施させる処理装置を選択する処理と、
選択した処理装置の親キューと、全ての処理装置の子キューに当該データを投入する処理と、
各処理装置が親キュー内のデータと子キュー内のデータとを総当りでマッチングした結果を収集し外部システムに応答する処理とを実行させる
請求項８に記載のマッチングプログラム。
【請求項１０】
コンピュータに、
各処理装置が親キュー内のデータとマッチングするデータとして、子キュー内のデータのうち、親キュー内のデータよりも後に到着または発生したデータを選択する場合には、親キューにデータを投入する処理装置を選択する際、すべての処理装置を順に選択したのち逆順に処理装置を選択する選択処理を繰り返す処理を実行させる
請求項９に記載のマッチングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リアルタイムに収集されるデータのマッチング処理を行うマッチングシステム、マッチング方法およびマッチングプログラムに関する。
【背景技術】
【０００２】
複数のデータを総当りで比較（マッチング）する一般的なマッチング処理は、データ数の増加により計算時間が増大する。このようなデータ数の増加に起因する計算時間増加を短縮するために、非特許文献１に記載されたＭａｐＲｅｄｕｃｅを利用した超並列計算処理が知られている（例えば、特許文献１、特許文献２および特許文献３参照。）。ＭａｐＲｅｄｕｃｅでは、１つのジョブをタスクと呼ばれる細かい単位に分割し、各タスクを処理サーバに割当て、タスク処理結果を併合し応答を返すという動作が基本的な挙動となる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−１１３４８６号公報
【特許文献２】特開２０１１−１７０７７４号公報
【特許文献３】特開２０１１−１５０５０３号公報
【非特許文献】
【０００４】
【非特許文献１】Ｄｅａｎ，Ｊ．  ａｎｄ  Ｇｈｅｍａｗａｔ，Ｓ．，  “ＭａｐＲｅｄｕｃｅ：  ｓｉｍｐｌｉｆｉｅｄ  ｄａｔａ  ｐｒｏｃｅｓｓｉｎｇ  ｏｎ  ｌａｒｇｅ  ｃｌｕｓｔｅｒｓ”，  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，  Ｖｏｌ．５１（２００８），  ｐ．１０７−１１３．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、ＭａｐＲｅｄｕｃｅは、処理するデータ数が明確な条件での処理（バッチ処理）を想定しており、リアルタイムに到着し個数が不定であるデータを処理することができない。また、各タスクの割当てについては自由度があり、適切な割当てがなされない場合、処理サーバの負荷バランスが不均一になり、適切に負荷を分散できない場合がある。【０００６】
そこで、本発明は、マッチング処理を効率的に並列実行することを可能とするマッチングシステム、マッチング方法およびマッチングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明によるマッチングシステムは、複数の処理装置と、複数の処理装置と通信可能な割当て装置とを備え、各処理装置は、マッチング処理対象のデータを格納するキューイング部と、キューイング部に格納されたデータについてマッチング処理を実施するマッチング部とを含み、割当て装置は、マッチング処理すべきデータを入力するたびに、複数の処理装置の中から、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置のキューイング部に当該データを格納するタスク割当て部と、各処理装置におけるマッチング処理の結果を収集し外部システムに応答する応答部とを含むことを特徴とする。【０００８】
本発明によるマッチング方法は、割当て装置が、マッチング処理すべきデータを入力するたびに、マッチング処理を実施する複数の処理装置の中から、各処理装置における処理負荷が均一になるように、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置が、当該データに対するマッチング処理を実施し、割当て装置が、各処理装置におけるマッチング処理の結果を収集し外部システムに応答することを特徴とする。【０００９】
本発明によるマッチングプログラムは、マッチング処理を実施する複数の処理装置と通信可能なコンピュータに、マッチング処理すべきデータを入力するたびに、複数の処理装置の中から、各処理装置における処理負荷が均一になるように、当該データに対するマッチング処理を実施させる処理装置を選択する処理と、各処理装置が実施したマッチング処理の結果を収集し外部システムに応答する処理とを実行させることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、リアルタイムに収集されるデータの総当りマッチングに適したタスク割当てを行うことができ、マッチング処理を効率的に並列実行することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明によるマッチングシステムの第１の実施形態の構成を示すブロック図である。
【図２】折り返しラウンドロビンに基づくタスク割当て結果の一例を示す説明図である。
【図３】単純なラウンドロビンに基づくタスク割当て結果の一例を示す説明図である。
【図４】本発明によるマッチングシステムの第１の実施形態における動作を示すシーケンス図である。
【図５】本発明によるマッチングシステムの最小構成を示すブロック図である。
【発明を実施するための形態】
【００１２】
実施形態１．
以下、本発明の第１の実施形態を図面を参照して説明する。
【００１３】
図１は、本発明によるマッチングシステムの第１の実施形態の構成を示すブロック図である。図１に示すように、本発明によるマッチングシステムは、処理サーバ１００−１〜１００−ｎと、割当サーバ２００とを含む。処理サーバ１００−１〜１００−ｎと、割当てサーバ２００とは、通信可能に接続されている。
【００１４】
割当てサーバ２００は、ネットワーク３００を介して、センサ４００および外部システム５００と通信可能に接続されている。センサ４００は、実世界におけるデータを収集するセンサである。外部システム５００は、例えば、センサ４００が収集したデータをサービス等に活用するシステムである。なお、図１には、１つのセンサ４００が例示されているが、センサはいくつあってもよい。また、図１には、１つの外部システム５００が例示されているが、外部システムはいくつあってもよい。
【００１５】
処理サーバ１００−１は、サーバ装置であって、キューイング部１０１と、マッチング部１０２とを備える。なお、処理サーバ１００−２〜１００−ｎの構成は、処理サーバ１００−１と同様であるため、説明を省略する。
【００１６】
キューイング部１０１は、マッチング対象のデータを管理する。キューイング部１０１は、マッチング元データを格納するキューと、マッチング先データを格納するキュー（以下、それぞれを親キュー、子キューという。）を備える。
【００１７】
マッチング部１０２は、マッチング処理を実施する。マッチング部１０２は、キューイング部１０１が管理する親キュー内のデータと、子キュー内のデータとを総当りでマッチング処理する。このとき、マッチング部１０２は、親キュー内のデータと比較するデータとして、当該親キュー内のデータよりも到着順序あるいは発生順序がより後の子キュー内のデータのみを選択して、マッチングを実施する。
【００１８】
ここで、マッチング処理の内容は、外部システム５００に応じて定めてよい。つまり、マッチング処理は、２つのデータを照合し特定の項目同士で比較して、比較結果に基づく判定処理を行う処理であれば、特に限定されない。
【００１９】
なお、キューイング部１０１は、処理サーバ１００−１が備えるメモリ等の記憶装置によって実現される。また、マッチング部１０２は、処理サーバ１００−１が備えるＣＰＵ等によって実現される。
【００２０】
割当てサーバ２００は、タスク割当て部２０１と、応答部２０２とを含む。
【００２１】
タスク割当て部２０１は、タスクを各処理サーバに割当てる。具体的には、タスク割当て部２０１は、データが到着するたびに、つまり、センサ４００からデータを入力するたびに、選択した処理サーバの親キューに当該データを１個投入する。このとき、タスク割当て部２０１は、単純なラウンドロビンではなく、後述する折り返しラウンドロビンと呼ばれるルールに則って処理サーバを選択する。また、タスク割当て部２０１は、当該データを全ての処理サーバの子キューに１個ずつ投入する。
【００２２】
ここで、折り返しラウンドロビンが示すルールを説明する。折り返しラウンドロビンでは、最初に処理サーバ１００−１を選択し、その後、処理サーバ１００−２，処理サーバ１００−３，…と処理サーバ１００−ｎまで昇順に選択する。そして、処理サーバ１００−ｎを選択したのちは、処理サーバ１００−ｎ，処理サーバ１００−（ｎ−１），…処理サーバ１００−１と降順に選択し、以降同様に繰り返す。
【００２３】
応答部２０２は、処理サーバ１００−１〜１００−ｎでのマッチング結果を外部システム５００に応答する。具体的には、応答部２０２は、各処理サーバのマッチング部１０２の処理結果を収集し、外部システム５００に処理結果を応答する。このとき、応答部２０２は外部システム５００のポリシに応じて、外部システム５００に送信するマッチング結果を取捨選択してもよい。
【００２４】
なお、タスク割当て部２０１および応答部２０２は、割当てサーバ２００が備えるＣＰＵ等によって実現される。
【００２５】
ここで、タスク割当て部２０１におけるタスク割当て処理について、具体例を用いて説明する。例えば、ある時点において１０個のデータ（ＡＢＣＤＥＦＧＨＩＪ）が辞書順（昇順）にセンサ４００から到着する状況下を想定する。この場合、計４５回のマッチング処理が発生する。
【００２６】
図２は、折り返しラウンドロビンを適用する場合のタスク割当ての様子を示す説明図である。図３は、折り返しラウンドロビンを適用せず、単純なラウンドロビンを適用する場合のタスク割当ての様子を示す説明図である。
【００２７】
図２に示すように、折り返しラウンドロビンを適用する場合は、処理サーバ数５台のとき、処理サーバ１００−１の親キューにはデータＡ，Ｊが、処理サーバ１００−２の親キューにはデータＢ，Ｉが、処理サーバ１００−３の親キューにはデータＣ，Ｈが、処理サーバ１００−４の親キューにはデータＤ，Ｇが、処理サーバ１００−５の親キューにはデータＥ，Ｆが投入される。このとき、処理サーバ１００−１〜１００−５の処理回数は、全て９回となり、均一になる。
【００２８】
一方、図３に示すように、同様の条件のもとで、単純なラウンドロビンを適用する場合は、各処理サーバの処理回数は不均一になる。
【００２９】
単純なラウンドロビンでは、最初に処理サーバ１００−１を、その後、処理サーバ１００−２，処理サーバ１００−３，…と処理サーバ１００−ｎまで昇順に選択する。そして、処理サーバ１００−ｎを選択したのちは、再び処理サーバ１００−１から繰り返すように処理サーバを選択する。従って、処理サーバ１００−１の親キューにはデータＡ，Ｆが、処理サーバ１００−２の親キューにはデータＢ，Ｇが、処理サーバ１００−３の親キューにはデータＣ，Ｈが、処理サーバ１００−４の親キューにはデータＤ，Ｉが、処理サーバ１００−５の親キューにはデータＥ，Ｊが投入される。このとき、処理サーバ１００−１〜１００−５の処理回数は、それぞれ１３回，１１回，９回，７回，５回となり、不均一になる。
【００３０】
次に、本実施形態の動作を説明する。
【００３１】
図４は、本発明によるマッチングシステムの第１の実施形態における動作を示すシーケンス図である。
【００３２】
割当てサーバ２００のタスク割当て部２０１は、マッチング処理すべきデータを待ち受ける（ステップＳ１１）。ここでは、タスク割当て部２０１は、マッチング処理すべきデータとして外部のセンサ（図１に示すセンサ４００）等から送信されるデータを待ちうける。
【００３３】
タスク割当て部２０１は、処理すべきデータが到着したタイミングにおいて、折り返しラウンドロビンルールに則って、当該データを投入する処理サーバを選択する（ステップＳ１２）。
【００３４】
タスク割当て部２０１は、選択した処理サーバの親キューにデータを投入するとともに、全ての処理サーバの子キューにも当該データを投入する（ステップＳ１３）。
【００３５】
処理サーバのキューイング部１０１は、割当てサーバ２００から投入されるデータを親キューまたは子キューに格納する（ステップＳ２１）。
【００３６】
処理サーバのマッチング部１０２は、ステップＳ２１の後、キューイング部１０１が管理する親キュー内のデータと、子キュー内のデータとを総当りでマッチング処理する（ステップＳ２２）。このとき、処理サーバのマッチング部１０２は、親キュー内のデータと比較するデータとして、当該親キュー内のデータよりも到着順序あるいは発生順序がより後の子キュー内のデータのみを選択して、マッチングを実施する。
【００３７】
マッチング部１０２は、マッチング結果を割当てサーバ２００に応答（送信）する（ステップＳ２３）。
【００３８】
割当てサーバ２００の応答部２０２は、各処理サーバからのマッチング結果を待ち受ける（ステップＳ１４）。
【００３９】
応答部２０２は、マッチング結果を受信したら、外部システム５００に当該マッチング結果を応答（送信）する（ステップＳ１５）。
【００４０】
なお、ステップＳ２１〜Ｓ２３の処理は、各処理サーバで並列に実行される。
【００４１】
また、本実施形態では、マッチングシステムが複数の装置（処理サーバ１００−１〜１００−ｎおよび割当てサーバ２００）によって実現されている場合について説明したが、マッチングシステムは１つの装置で実現されていてもよい。つまり、各処理サーバのキューイング部１０１およびマッチング部１０２と、割当てサーバ２００のタスク割当て部２０１および応答部２０２とが１つの装置に含まれていてもよい。
【００４２】
また、クラウドコンピューティング上で、処理サーバ１００−１〜１００−ｎおよび割当てサーバ２００を論理的に１台のサーバとして扱うようにしてもよい。
【００４３】
以上に説明したように、本実施形態では、割当てサーバ２００が、マッチング処理すべきデータが到着するたびに、当該データを適切に処理サーバに割当てる。そして、各処理サーバは、データが到着するタイミングで逐次にマッチング処理を行う。また、本実施形態では、単純なラウンドロビンではなく、折り返しラウンドロビンに則って処理サーバを選択する。それにより、処理サーバの負荷バランス均一になり、処理サーバの負荷が分散される。
【００４４】
従って、本実施形態によれば、処理すべきデータが到着するたびに逐次に処理でき、かつ各処理サーバでの計算時間を均等化するようにタスク（データ）を割当てることができる。すなわち、リアルタイムに収集されるデータの総当りマッチングに適したタスク割当てを行うことができ、マッチング処理を効率的に並列計算することができる。よって、本発明は、センサ等により実世界から収集するデータ同士をマッチングし、その結果をサービスに活用するシステムなどにおいて、大規模に収集するデータのマッチング処理を効率化させることができる。
【００４５】
また、本実施形態では、折り返しラウンドロビンに則って処理するだけでよいので、均等負荷分散を図るための特別な構成を必要としない。従って、単純なラウンドロビンを適用する場合と同程度の構成で、均等負荷分散を容易に実現することができる。また、割当てサーバの負荷を、単純なラウンドロビンを適用する場合と同程度に抑えることができる。
【００４６】
図５は、本発明によるマッチングシステムの最小構成を示すブロック図である。図５に示すように、本発明によるマッチングシステムは、複数の処理装置１０−１〜１０−ｎ（図１に示す処理サーバ１００−１〜１００−ｎに相当。）と、複数の処理装置１０−１〜１０−ｎと通信可能な割当て装置２０（図１に示す割当てサーバ２００に相当。）とを備え、各処理装置は、マッチング処理対象のデータを格納するキューイング部１１（図１に示す処理サーバ１００−１におけるキューイング部１０１に相当。）と、キューイング部１１に格納されたデータについてマッチング処理を実施するマッチング部１２（図１に示す処理サーバ１００−１におけるマッチング部１０２に相当。）とを含み、割当て装置２０は、マッチング処理すべきデータを入力するたびに、複数の処理装置１０−１〜１０−ｎの中から、当該データに対するマッチング処理を実施させる処理装置を選択し、選択した処理装置のキューイング部１１に当該データを格納するタスク割当て部２１（図１に示す割当てサーバ２００におけるタスク割当て部２０１に相当。）と、各処理装置におけるマッチング処理の結果を収集し外部システム（図１に示す外部システム５００に相当。）に応答する応答部２２（図１に示す割当てサーバ２００における応答部２０２に相当。）とを含む。
【００４７】
上記の実施形態には、以下のようなマッチングシステムも開示されている。
【００４８】
（１）割当て装置２０のタスク割当て部２１が、各処理装置における処理負荷が均一になるように、マッチング処理を実施させる処理装置を選択するマッチングシステム。
【００４９】
そのような構成によれば、各処理サーバでの計算時間を均等化するようにタスク（データ）を割当てることができる。
【００５０】
（２）処理装置のキューイング部１１が、マッチング元データを格納する親キューと、マッチング先データを格納する子キューとを含み、処理装置のマッチング部１２が、キューイング部１１の親キュー内のデータと、子キュー内のデータとを総当りでマッチングし、割当て装置２０のタスク割当て部２１が、マッチング処理すべきデータを入力するたびに、選択した処理装置の親キューと、全ての処理装置の子キューに当該データを投入するマッチングシステム。
【００５１】
そのような構成によれば、リアルタイムに収集されるデータの総当りマッチングに適したタスク割当てを行うことができ、マッチング処理を効率的に並列計算することができる。
【００５２】
（３）処理装置のマッチング部１２が、親キュー内のデータとマッチングするデータとして、子キュー内のデータのうち、親キュー内のデータよりも後に到着または発生したデータを選択し、割当て装置２０のタスク割当て部２１が、親キューにデータを投入する処理装置を選択する際、すべての処理装置を順に選択したのち逆順に処理装置を選択する選択処理を繰り返すマッチングシステム。
【００５３】
このように、折り返しラウンドロビンに則って処理サーバを選択することにより、単純なラウンドロビンの場合と比べて処理サーバの負荷バランスが均一になり、処理サーバの負荷を分散することができる。そのような構成によれば、折り返しラウンドロビンに則って処理するだけでよいので、均等負荷分散を図るための特別な構成を必要としない。従って、単純なラウンドロビンを適用する場合と同程度の構成で、均等負荷分散を容易に実現することができる。また、割当てサーバの負荷を、単純なラウンドロビンを適用する場合と同程度に抑えることができる。
【００５４】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００５５】
この出願は、２０１２年８月２３日に出願された日本特許出願２０１２−１８３８４０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００５６】
１０−１〜１０−ｎ  処理装置
２０  割当て装置
１１、１０１  キューイング部
１２、１０２  マッチング部
２１、２０１  タスク割当て部
２２、２０２  応答部
１００−１〜１００−ｎ  処理サーバ
２００  割当てサーバ
３００  ネットワーク
４００  センサ
５００  外部システム
【図１】
2014030300.tif 000003
【図２】
2014030300.tif 000004
【図３】
2014030300.tif 000005
【図４】
2014030300.tif 000006
【図５】
2014030300.tif 000007
【国際調査報告】
2014030300.tif 000008
2014030300.tif 000009
2014030300.tif 000010
2014030300.tif 000011