(57)【要約】【課題】構造が頻繁に変化する大規模なグラフにおいて、キャッシュを用いることなく、排他制御を行いつつ効率よく並列処理を行うことができるデータベース装置を提供すること。【解決手段】データベース装置３は、グラフを構成する要素を示す要素データＥの各々に、並列処理を実行可能とする複数の単位プロセスの一を対応させ、当該複数の単位プロセスの一に、それぞれデータベース装置３が備えるメモリ領域２２のメモリを割り当て、グラフアプリケーション２からリクエストメッセージを受信したことに応じて、メモリ領域２２のメモリを割り当てた複数の単位プロセスとのメッセージ通信のみにより、リクエストメッセージに対応する要素データの書き換えを行うことで排他制御を行い、処理要求メッセージに対応する結果メッセージを取得する。【選択図】図１
2012069072.tif 000002
【特許請求の範囲】
【請求項１】
逐次内容が変化するグラフを取り扱うアプリケーションのために、当該グラフを構成する複数の要素の処理を行う並列処理システムにおいて、データベースを複数のプロセスによって構成するデータベース装置であって、
前記グラフを構成する要素を示す要素データの各々に、並列処理を実行可能とする前記複数のプロセスの一を対応させ、当該複数のプロセスの一に、それぞれ前記データベース装置が備えるメモリを割り当てるメモリ割当手段と、
前記アプリケーションのプロセスから所定の処理を要求する処理要求メッセージを受信するメッセージ受信手段と、
前記処理要求メッセージを受信したことに応じて、前記メモリを割り当てた前記複数のプロセスとのメッセージ通信のみにより、前記処理要求メッセージに対応する前記要素データの書き換えを行うことで排他制御を行い、前記処理要求メッセージに対応する結果メッセージを取得する排他制御手段と、
前記アプリケーションのプロセスに、前記結果メッセージを返信するメッセージ返信手段と、を備えるデータベース装置。
【請求項２】
前記排他制御手段は、前記処理要求メッセージを受信したことに応じて、前記複数のプロセスの処理結果を格納するリストを生成し、前記メモリを割り当てた前記複数のプロセスとのメッセージ通信のみにより、前記処理要求メッセージに対応する前記要素データの書き換えを並列に行うことで排他制御を行い、前記複数のプロセスの各々から応答メッセージを取得したことに応じて、前記各々のプロセスの処理結果を前記リストに格納し、前記リストに前記複数のプロセスの処理結果が格納されたことに応じて、前記結果メッセージを生成する請求項１に記載のデータベース装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逐次内容が変化するグラフを使用するアプリケーションに設けられ、当該グラフを構成する複数の要素の処理を行う並列処理システムにおいて、当該複数の要素をデータベースとし、当該要素をプロセスによって処理するデータベース装置に関する。
【背景技術】
【０００２】
近年、アプリケーションやデータの肥大化による処理速度の低下に対して、処理速度の向上が要求されている。これに対し、一般的な処理速度向上の手法として、複数のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）による並列処理を行う方法が提案されている。
【０００３】
従来、実行効率を意識したアプリケーションの多くは、Ｃ＋＋で作成されていたが、Ｃ＋＋では、並列処理の記述が複雑なものとなる。このため、Ｃ＋＋により作成されたアプリケーションにおいて、さらなる高速化を目的として並列処理を実現させることは、難易度が高いものであった。更に、Ｃ＋＋では、並列化する場合に生成されるプロセスの粒度が大きく、並列処理におけるオーバーヘッドも、高速化を妨げる要因となっていた。
【０００４】
また、並列化を実現させる他の方法として、行列計算を自動的に並列化するＦＯＲＴＲＡＮコンパイラを利用する方法があるが、行列計算を使用する必要があるため、応用範囲が狭いという問題があった。
【０００５】
このような問題に対して、マルチコアを利用して大規模データの並列処理を効率よく行うことができる言語として、例えば、アーラン（Ｅｒｌａｎｇ）が開発されている（例えば、特許文献１参照）。アーランでは、細かい粒度のプロセスを多数生成することで、様々な用途に応じて、効率の良いアプリケーションを作成することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００３−５０５７５８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、アーランでは、多数のプロセスの並列処理を行う場合、このプロセスの規模が一定以上になると、大幅な処理の遅延が発生する場合がある。また、アーランでは、構造が頻繁に変化する大規模なグラフに対して、キャッシュを利用してアクセスしようとすると、キャッシュの更新に係るオーバーヘッドが大きくなるといった問題がある。
このような問題は、構造が頻繁に変化する大規模なグラフにおいて、顕著なものとなるので、大規模なグラフを取り扱うアプリケーションにおいてキャッシュを用いることなく効率よく並列処理を行うことができるデータベース装置が求められている。
【０００８】
本発明は、構造が頻繁に変化する大規模なグラフにおいて、キャッシュを用いることなく、排他制御を行いつつ効率よく並列処理を行うことができるデータベース装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
（１）逐次内容が変化するグラフを取り扱うアプリケーションのために、当該グラフを構成する複数の要素の処理を行う並列処理システムにおいて、データベースを複数のプロセスによって構成するデータベース装置であって、前記グラフを構成する要素を示す要素データの各々に、並列処理を実行可能とする前記複数のプロセスの一を対応させ、当該複数のプロセスの一に、それぞれ前記データベース装置が備えるメモリを割り当てるメモリ割当手段と、前記アプリケーションのプロセスから所定の処理を要求する処理要求メッセージを受信するメッセージ受信手段と、前記処理要求メッセージを受信したことに応じて、前記メモリを割り当てた前記複数のプロセスとのメッセージ通信のみにより、前記処理要求メッセージに対応する前記要素データの書き換えを行うことで排他制御を行い、前記処理要求メッセージに対応する結果メッセージを取得する排他制御手段と、前記アプリケーションのプロセスに、前記結果メッセージを返信するメッセージ返信手段と、を備えるデータベース装置。
【００１０】
（１）のデータベース装置は、メモリ割当手段により、グラフを構成する要素を示す要素データの各々に、並列処理を実行可能とする複数のプロセスの一を対応させ、当該複数のプロセスの一に、それぞれデータベース装置が備えるメモリを割り当て、排他制御手段により、処理要求メッセージを受信したことに応じて、メモリを割り当てた複数のプロセスとのメッセージ通信のみにより、処理要求メッセージに対応する要素データの書き換えを行うことで排他制御を行い、処理要求メッセージに対応する結果メッセージを取得する。
【００１１】
よって、（１）のデータベース装置は、グラフを構成する要素を示す要素データの各々に、並列処理を実行可能とする複数のプロセスの一を対応させ、当該複数のプロセスの一に、それぞれデータベース装置が備えるメモリを割り当てて、メモリを割り当てた複数のプロセスとのメッセージ通信のみにより、グラフに対する排他処理を行うので、アプリケーション側から、排他制御を行うことができる。また、（１）のデータベース装置は、構造が頻繁に変化する大規模なグラフを構成する要素について必要な情報のみ、アプリケーション側から排他制御を行うので、不要な情報に対して排他制御を行うことによる処理の遅延を防止して、全体として並列処理の高速化を実現することができる。
【００１２】
（２）前記排他制御手段は、前記処理要求メッセージを受信したことに応じて、前記複数のプロセスの処理結果を格納するリストを生成し、前記メモリを割り当てた前記複数のプロセスとのメッセージ通信のみにより、前記処理要求メッセージに対応する前記要素データの書き換えを並列に行うことで排他制御を行い、前記複数のプロセスの各々から応答メッセージを取得したことに応じて、前記各々のプロセスの処理結果を前記リストに格納し、前記リストに前記複数のプロセスの処理結果が格納されたことに応じて、前記結果メッセージを生成する（１）に記載のデータベース装置。
【００１３】
（２）のデータベース装置は、排他制御手段により、複数のプロセスの処理結果を格納するリストを生成し、処理要求メッセージに対応する要素データの書き換えを並列に行うことで排他制御を行い、複数のプロセスの各々から応答メッセージを取得したことに応じて、各々のプロセスの処理結果をリストに格納する。よって、（２）のデータベース装置は、不要な情報に対して排他制御を行うとともに、プロセス経由のみで受信した複数のプロセスの処理結果をリストに格納したことに応じて結果メッセージを生成して、当該結果メッセージをアプリケーションのプロセスに提供することができる。
【発明の効果】
【００１４】
本発明によれば、構造が頻繁に変化する大規模なグラフにおいて、キャッシュを用いることなく、排他制御を行いつつ効率よく並列処理を行うことができるデータベース装置を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係るデータベース装置を備える並列処理システムの概要を示す図である。
【図２】本実施形態に係るデータベース装置の構成を示すブロック図である。
【図３】本実施形態に係るメモリ割当部の処理を示すコードである。
【図４】本実施形態に係る並列メッセージ処理実行部及びメッセージ返信部の処理を示すコード（その１）である。
【図５】本実施形態に係る並列メッセージ処理実行部及びメッセージ返信部の処理を示すコード（その２）である。
【図６】本実施形態に係るデータベース装置がリクエストメッセージを受信した場合に行う処理の流れを示すフローチャートである。
【図７】本実施形態に係るレシーブリストが更新される概念を示す図である。
【発明を実施するための形態】
【００１６】
以下、本実施形態について図を参照しながら説明する。
【００１７】
［機能構成］
図１は、本実施形態に係るデータベース装置３を備える並列処理システム１の概要を示す図である。並列処理システム１は、逐次内容が変化するグラフを取り扱うアプリケーションのために、このグラフを構成する複数の要素の並列処理を行う。この並列処理システム１は、逐次内容が変化するグラフを使用するアプリケーションとして、グラフアプリケーション２と、当該グラフを構成する複数の要素をデータベースとし、当該要素をプロセスによって処理するデータベース装置３とを備える。
【００１８】
ここで、グラフは、要素データＥとして、処理内容を示すエッジＤと、複数のエッジＤの関係を示す処理ノードＮとにより構成されており、エッジＤとノードＮは、逐次内容が変化するものである。
【００１９】
グラフアプリケーション２は、例えば、チャットボット等のリアルタイム対話アプリケーションである。このグラフアプリケーション２は、ユーザから処理要求としてのリクエストを受け付けると、リクエストの実行を制御するリクエストプロセスを生成する。続いて、グラフアプリケーション２は、リクエストプロセスにより、このリクエストに対応する処理要求メッセージとしてのリクエストメッセージをデータベース装置３に送信することで、データベース装置３にリクエストを要求する。
【００２０】
データベース装置３は、グラフの要素データＥ、すなわち、グラフのエッジＤ及びノードＮに１対１に対応する単位プロセスを割り当て、更にそれぞれの単位プロセスにメモリを割り当てておき、グラフアプリケーション２からリクエストメッセージを受信したことに応じて、管理プロセスと、ワーカープロセス（以下、ワーカープロセスをＷＰともいう）とを生成する。続いて、データベース装置３は、ワーカープロセスと単位プロセスとのメッセージ通信のみによって要素データＥの書き換えを行うことで排他制御を行い、リクエストメッセージに対応する結果メッセージを取得し、この結果メッセージをグラフアプリケーション２に送信する。
【００２１】
このように、並列処理システム１では、予めデータベース装置３がグラフのエッジＤ及びノードＮと１対１に対応する単位プロセスを割り当て、更にそれぞれの単位プロセスにメモリを割り当てて準備しているので、グラフアプリケーション２からリクエストメッセージをデータベース装置３に送信されると、データベース装置３において、この単位プロセスとのメッセージ通信のみによってエッジＤ及びノードＮの書き換えを行うことで排他制御を行い、リクエストメッセージに対応する結果メッセージを生成することができる。そして、並列処理システム１では、データベース装置３から、この結果メッセージをグラフアプリケーション２に送信することで、メッセージ通信のみによってリクエストに対応する処理を行うことができる。
【００２２】
本実施形態は、コンピュータ（データベース装置３）及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備えるハードウェア並びにこのハードウェアを制御するソフトウェアによって構成される。
【００２３】
上記ハードウェアには、制御部１０として並列に動作する複数のＣＰＵの他、記憶部２０、通信部、表示部及び入力部が含まれる。記憶部２０としては、例えば、メモリ（ＲＡＭ、ＲＯＭ等）、ハードディスクドライブ（ＨＤＤ）及び光ディスク（ＣＤ、ＤＶＤ等）ドライブが挙げられる。通信部としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示部としては、例えば、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイが挙げられる。入力部としては、例えば、キーボード及びポインティング・デバイス（マウス、トラッキングボール等）が挙げられる。
【００２４】
上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部２０により記憶され、制御部１０により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信ネットワークを介して配布することも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布することも可能である。
【００２５】
続いて、図１及び図２を参照しながら、データベース装置３の構成について説明する。
図２は、本実施形態に係るデータベース装置３の構成を示すブロック図である。
【００２６】
データベース装置３の制御部１０は、メモリ割当部１１（メモリ割当手段）と、メッセージ受信部１２（メッセージ受信手段）と、メッセージ返信部１３（メッセージ返信手段）と、並列メッセージ処理実行部２５と、を備える。また、データベース装置３の記憶部２０は、グラフデータ記憶部２１と、メモリ領域２２と、を備える。
【００２７】
メモリ割当部１１は、グラフデータ記憶部２１に記憶されているグラフデータから、このグラフを構成する要素（エッジＤ及びノードＮ）を示す要素データＥの各々に、並列処理を実行可能とする複数のプロセスの一を対応させ、この複数のプロセスの一に、それぞれメモリを割り当てる。
【００２８】
具体的には、グラフデータ記憶部２１には、グラフアプリケーション２で使用するグラフデータが記憶されており、メモリ割当部１１は、予め、このグラフデータを構成する要素（エッジＤ及びノードＮ）を示す要素データＥの各々に、並列処理を実行可能とする単位プロセスの一を対応させて、単位プロセス群２３として、単位プロセス群２３の一に、それぞれメモリ領域２２のメモリを割り当てる。
【００２９】
メッセージ受信部１２は、アプリケーションの実行を制御するプロセス（リクエストプロセス）から所定の処理を要求するリクエストメッセージを受信する。リクエストメッセージには、グラフデータにおいて使用される要素データの情報、すなわち、排他制御範囲の指定情報を含んでいる。
【００３０】
並列メッセージ処理実行部２５は、メモリ割当部１１によりメモリ領域２２のメモリを割り当てられたグラフデータに対応する単位プロセス群２３、並びに、更にこれらに対応するワーカープロセス及び管理プロセス（後述）で構成する管理プロセス群２４を含んで記憶部２０のメモリ領域に実装され、排他処理を実行する。より具体的には、リクエストメッセージを受信したことに応じて、メモリを割り当てた複数のプロセスとのメッセージ通信のみにより、リクエストメッセージに対応する要素データの書き換えを行うことで排他制御を行い、リクエストメッセージに対応する結果メッセージを取得する。
【００３１】
具体的には、並列メッセージ処理実行部２５は、メッセージ受信部１２によりリクエストメッセージを受信したことに応じて、メモリ領域２２に、管理プロセス群２４として、管理プロセス及び複数のワーカープロセスを生成するとともに、複数のワーカープロセスの処理結果を格納するためのレシーブリストを生成する。
【００３２】
すなわち、並列メッセージ処理実行部２５は、リクエストメッセージに含まれる排他制御範囲の指定情報に基づいて、グラフデータにおいて使用される要素データの個数分のワーカープロセスを生成するとともに、ワーカープロセスそれぞれに対応する格納領域を有するレシーブリストを生成する。続いて、並列メッセージ処理実行部２５は、このワーカープロセスそれぞれを、使用される要素データに対応している単位プロセスに関連付ける。続いて、並列メッセージ処理実行部２５（管理プロセス）は、ワーカープロセスそれぞれに、処理要求メッセージを単位プロセスに対して並列に送信させる。
【００３３】
すると、単位プロセスそれぞれは、処理要求メッセージを受信したことに応じて、処理要求メッセージに対応する処理を並列に行うとともに、グラフデータを構成する要素データＥに基づいて応答メッセージを生成し、この応答メッセージをワーカープロセスに送信する。
【００３４】
続いて、並列メッセージ処理実行部２５（ワーカープロセス）が、複数の単位プロセスそれぞれから応答メッセージを受信したことに応じて、並列メッセージ処理実行部２５（管理プロセス）は、複数のワーカープロセスからの応答メッセージに基づいて、レシーブリストにその処理結果を格納し、このレシーブリストに基づいて、リクエストプロセスに返信するための結果メッセージを生成して、後述のメッセージ返信部１３に受け渡す。
また、並列メッセージ処理実行部２５は、結果メッセージをメッセージ返信部１３に受け渡した後、管理プロセス及びワーカープロセスを消去する。
【００３５】
メッセージ返信部１３は、グラフアプリケーション２のリクエストプロセスに、並列メッセージ処理実行部２５により生成された結果メッセージを返信する。
【００３６】
図３及び図４に、並行処理指向のプログラミング言語であるＥｒｌａｎｇにより記述されたコードを用いて、詳細な処理について説明する。
【００３７】
図３は、本実施形態に係るメモリ割当部１１の処理を示すコードである。図３に示されるコードは、グラフを構成する全要素をメモリに展開する処理を行う。図３では、コードの説明を簡潔に行うため、コードの左側に対して、行番号を付している。
【００３８】
図３の１行目に示されるメイン関数としてのｍａｉｎ（）は、本実施形態のメモリ割当部１１の処理に相当する。
３行目に示される｛Ｒ，＿｝＝ｘｍｅｒｌ＿ｓｃａｎ：ｆｉｌｅ（Ｆｉｌｅｎａｍｅ）では、ＸＭＬ処理のライブラリパッケージであるｘｍｅｒｌ＿ｓｃａｎを使用するための準備処理を行う。つまり、変数Ｒに対して、２行目で指定された外部のＸＭＬへのハンドラが格納され、メモリの読み込みが実行される。
【００３９】
５行目に示されるＰａｒｓｅｄａｔａ＝ｐａｒｓｅ（Ｒ）では、上述のＸＭＬ処理のライブラリパッケージであるｘｍｅｒｌ＿ｓｃａｎを用いて、ＸＭＬのデータをパーズ（構文解析）し、Ｅｒｌａｎｇのデータ構造上に、ＤＯＭ（Ｄｏｃｕｍｅｎｔ  Ｏｂｊｅｃｔ  Ｍｏｄｅｌ）ツリーを構成する。このようにして、ＤＯＭ形式のメモリ展開が行われ、変数Ｐａｒｓｅｄａｔａに対して、ＤＯＭツリーが格納される。
【００４０】
７行目に示されるコードでは、ＤＯＭツリーのｒｏｏｔ直下の要素を逐次的に処理し、グラフデータに対応する複数のプロセスを順次起動する。このようにすることで、グラフの要素データＥの各々に対応し、並列処理を実行可能とする複数のプロセスの一に、それぞれメモリが割り当てられる。なお、このプロセスの起動は、７行目に示されるコードにおける、ｒｅｌａｔｉｏｎ＿ｅｌｅｍｅｎｔ．ｅｒｌのｓｔａｒｔ／１という関数により実行される。
【００４１】
図４及び図５は、並列メッセージ処理実行部２５及びメッセージ返信部１３の処理を示すコードである。図４及び図５では、コードの説明を簡潔に行うため、コードの左側に対して、行番号を付している。
【００４２】
図４の１行目に示される関数ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）は、本実施形態の管理プロセスに相当する。すなわち、並列メッセージ処理実行部２５は、この関数ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）を実行することで、管理プロセスを生成し、この管理プロセス内でワーカープロセスを生成して並列処理を実行し、結果メッセージを生成する。
【００４３】
２行目に示されるｒｅｃｉｖｅｌｉｓｔ：ｃｒｅａｔｅ（ＥｉｄＬｉｓｔ）は、並列処理を行う複数のワーカープロセスの処理結果を格納するリストを生成して初期化するものである。この際、当該並列処理を行う複数のワーカープロセスの数に応じたリストサイズを設定する。すなわち、図４に示されるコードでは、予め、応答メッセージを格納するメモリ領域を確保・初期化しておき、このメモリ領域に対して、後述で説明するコードにより、処理結果が格納される。
【００４４】
３行目に示されるｌｏｃｋ＿ｇｌｏｂａｌ（）は、排他制御を行う関数であり、４行目以降に示される処理に係るデータの排他制御を行う。ｌｏｃｋ＿ｇｌｏｂａｌ（）は、具体的には、２３行目から３０行目までの処理を行う。
【００４５】
７行目から１４行目に示される関数であるｌｉｓｔｓ：ｍａｐ（）は、関数と、リストとを引数とする関数であり、この関数を、リストを構成する複数の要素に適用して得られた結果を返す関数、すなわち、高階関数である。図４では、関数として、ｓｐａｗｎ（）を使用して、リストとして、リクエストメッセージに含まれる排他制御範囲の指定情報を示すＥｉｄＬｉｓｔを使用している。
【００４６】
ｓｐａｗｎ（）は、関数を引数とし、並行プロセスを生成する関数である。図４では、このｓｐａｗｎ（）により、リクエストメッセージにおいて指定されたグラフの要素データＥに対応する単位プロセスに対してメッセージを送信するワーカープロセスを生成している。
【００４７】
つまり、管理プロセス（ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）の実行プロセス）は、７行目から１４行目に示されるコードにより、単位プロセスと１対１に対応するワーカープロセスを生成し、このワーカープロセスにより、排他制御範囲の指定情報を含むＥｉｄＬｉｓｔに基づく処理をメッセージとして単位プロセスに送信することで、各要素に対する処理の実行と、処理結果を示す応答メッセージの返信とを実行させる。
【００４８】
また、１６行目に示される関数であるｗａｉｔ＿ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）は、ワーカープロセスの結果を一つずつ並列に受信してリストに格納し、リストサイズを一つデクリメントする（図５の１行目から１５行目参照）。つまり、図５の４行目に示されるように、ｗａｉｔ＿ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）関数の中で、ｒｅｃｅｉｖｅｌｉｓｔモジュールの関数ｃｈａｎｇｅ（ＲｅｓＥｉｄ，ＲｅｓＥｉｄ）が呼び出され、この中で、ワーカープロセスの結果を一つずつ並列に受信してリストに格納し、処理完了の判断に使用されるリストサイズを一つデクリメントする（図５の１７行目から２１行目）。なお、結果がない（ｕｎｓａｔｉｓｆｙ）場合、図５の６行目に示されるように、ｗａｉｔ＿ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）関数の中で、ｒｅｃｅｉｖｅｌｉｓｔモジュールの関数ｃｈａｎｇｅ（ＲｅｓＥｉｄ，ｕｎｓａｔｉｓｆｙ）が呼び出され、この中で、当該ワーカープロセスの結果がない旨をリストに格納し、処理完了の判断に使用されるリストサイズを一つデクリメントする（図５の１７行目から２１行目）。
【００４９】
続いて、ｒｅｃｅｉｖｅｌｉｓｔモジュールの関数ｉｓ＿ｆｉｎｉｓｈｅｄ（）において、リストサイズが０であるか否かを判定する（図５の１０行目及び３８行目から４４行目）。０である場合、ｗａｉｔ＿ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）の処理を終了し、０ではない場合には、再びｗａｉｔ＿ｆｅｔｃｈ＿ｒｅｌａｔｉｏｎ（）を実行し、ワーカープロセスの結果を一つずつ並列に受信する。
【００５０】
その後、１７行目から１９行目に示される処理により、終了処理が行われる。例えば、１８行目に示されるＲｅｃｉｅｖｅｌｉｓｔ＝ｇｅｔ（ｒｅｃｅｉｖｅｌｉｓｔ）では、レシーブリストの更新が行われ、その後、１９行目に示されるｒｅｃｉｅｖｅｌｉｓｔ：ｃｌｅａｒ（）において、ｒｅｃｉｅｖｅｌｉｓｔ、すなわち、応答メッセージを格納しているメモリ領域の消去が行われる。
また、２０行目に示されるｕｎｌｏｃｋ＿ｇｌｏｂａｌ（）は、３行目で開始された排他制御の解除を行う関数である。ｕｎｌｏｃｋ＿ｇｌｏｂａｌ（）は、具体的には、３２行目から３９行目までの処理を行う。
【００５１】
［処理フロー］
図６は、本実施形態に係るデータベース装置３がリクエストメッセージを受信した場合に行う処理の流れを示すフローチャートである。
【００５２】
ステップＳ１では、制御部１０（メモリ割当部１１）は、グラフデータ記憶部２１に記憶されているグラフデータから、このグラフを構成する要素（エッジＤ及びノードＮ）を示す要素データＥに、並列処理を実行可能とする単位プロセスを対応させ、この複数の単位プロセスにメモリを割り当てる。
【００５３】
ステップＳ２では、制御部１０は、メッセージ受信部１２により、グラフアプリケーション２から、リクエストメッセージを受信したか否かを判定する。制御部１０は、この判定がＹＥＳの場合、ステップＳ３に処理を移し、この判定がＮＯの場合、ステップＳ２を再び実行する。
【００５４】
ステップＳ３では、制御部１０（並列メッセージ処理実行部２５）は、メッセージ受信部１２によりリクエストメッセージを受信したことに応じて、管理プロセス群２４として、管理プロセス及び複数のワーカープロセスを生成するとともに、レシーブリストを生成する。
ステップＳ４では、制御部１０（並列メッセージ処理実行部２５）は、管理プロセスにより、ワーカープロセスと単位プロセスとのメッセージの交換を行い、単位プロセスに処理を実行させてエッジＤ及びノードＮの書き換えを行うことにより排他制御を行い、単位プロセスごとに応答メッセージを受信する。
【００５５】
ステップＳ５では、制御部１０（並列メッセージ処理実行部２５）は、単位プロセスごとの応答メッセージに基づいて、レシーブリストを更新することにより、グラフアプリケーション２に返信する結果メッセージを生成する。
【００５６】
図７は、本実施形態に係るレシーブリストが更新される概念を示す図である。制御部１０は、複数の単位プロセスによる処理を並列で実行し、この単位プロセスに対応するワーカープロセスから応答メッセージ（処理結果）を受信することにより、この応答メッセージを処理結果として、ワーカープロセスの各々に対応するレシーブリストの格納領域に格納する。また、制御部１０は、ワーカープロセスから応答メッセージを受信したことに応じて、処理完了の判断に使用されるリストサイズを一つデクリメントし、リストサイズが０になるまで、ワーカープロセスからの応答メッセージの受信を続ける。そして、制御部１０は、全てのワーカープロセスにおける、応答メッセージの受信に係る処理と、このレシーブリストを構成する格納領域に対する処理結果の格納に係る処理が終了した後、レシーブリストに基づいて結果メッセージを生成する。
【００５７】
図６に戻り、ステップＳ６では、制御部１０（メッセージ返信部１３）は、ステップＳ５において生成された結果メッセージをグラフアプリケーション（リクエストプロセス）に返信する。
ステップＳ７では、制御部１０（並列メッセージ処理実行部２５）は、ステップＳ３において生成された管理プロセス、複数のワーカープロセス及びレシーブリストを消去する。
【００５８】
ステップＳ８では、制御部１０は、データベース装置３のユーザから入力部を介して終了操作を受け付けたか否かを判定する。制御部１０は、この判定がＹＥＳの場合、処理を終了し、この判定がＮＯの場合、処理をステップＳ２に移す。
【００５９】
以上のように、データベース装置３は、メモリ割当部１１により、グラフを構成する要素を示す要素データＥの各々に、並列処理を実行可能とする複数の単位プロセスの一を対応させ、当該複数の単位プロセスの一に、それぞれデータベース装置３が備えるメモリを割り当て、並列メッセージ処理実行部２５により、グラフアプリケーション２からリクエストメッセージを受信したことに応じて、メモリを割り当てた複数の単位プロセスとのメッセージ通信のみにより、リクエストメッセージに対応する要素データの書き換えを行うことで排他制御を行い、処理要求メッセージに対応する結果メッセージを取得する。
【００６０】
よって、データベース装置３は、グラフを構成する要素を示す要素データＥの各々に、並列処理を実行可能とする複数の単位プロセスの一を対応させ、当該複数の単位プロセスの一に、それぞれデータベース装置３が備えるメモリを割り当てて、メモリを割り当てた複数の単位プロセスとのメッセージ通信のみにより、グラフに対する排他処理を行うので、アプリケーション側から、排他制御を行うことができる。また、データベース装置３は、構造が頻繁に変化する大規模なグラフを構成する要素について必要な情報のみ、アプリケーション側から排他制御を行うので、不要な情報に対して排他制御を行うことによる処理の遅延を防止して、全体として並列処理の高速化を実現することができる。
【００６１】
また、データベース装置３は、並列メッセージ処理実行部２５により、処理要求メッセージに対応する複数のワーカープロセスの各々の処理結果を格納するリストを生成し、処理要求メッセージに対応する要素データの書き換えを並列に行うことで排他制御を行い、応答メッセージを取得したことに応じて、当該処理結果をリストに格納する。よって、データベース装置３は、不要な情報に対して排他制御を行うとともに、プロセス経由のみで受信した応答メッセージをリストに格納したことに応じて結果メッセージを生成して、当該結果メッセージをアプリケーションのプロセスに提供することができる。
【００６２】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【符号の説明】
【００６３】
１  並列処理システム
２  グラフアプリケーション
３  データベース装置
１０  制御部
１１  メモリ割当部
１２  メッセージ受信部
１３  メッセージ返信部
２０  記憶部
２１  グラフデータ記憶部
２２  メモリ領域
２３  単位プロセス群
２４  管理プロセス群
２５  並列メッセージ処理実行部
Ｅ  要素データ
【図１】
2012069072.tif 000003
【図２】
2012069072.tif 000004
【図３】
2012069072.tif 000005
【図４】
2012069072.tif 000006
【図５】
2012069072.tif 000007
【図６】
2012069072.tif 000008
【図７】
2012069072.tif 000009