(57)【要約】  本出願は、グラフデータに基づくタスクスケジューリング方法、装置、プログラム及び機器に関し、前記方法は、処理すべきグラフデータから分割されたサブグラフデータを取得し、第１の量子化値と第２の量子化値とを取得し、前記第１の量子化値は、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行し、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に完了済の単位計算タスクに対応する量子化値であり、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定し、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。本出願で提供されるスキームはタスクのスケジューリング効率を向上させることができる。
2021524100.tif 000002
【特許請求の範囲】
【請求項１】
計算ノードが実行する、グラフデータに基づくタスクスケジューリング方法であって、
処理すべきグラフデータから分割されたサブグラフデータを取得するステップと、
前記サブグラフデータにおけるグラフノードに対する単位計算タスクを実行するステップと、
第１の量子化値を取得し、前記第１の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に、前記完了済の単位計算タスクに対応する量子化値である、ステップと、
第２の量子化値を取得し、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に前記完了済の単位計算タスクに対応する量子化値である、ステップと、
前記サブグラフデータ内の未完了の単位計算タスクに対応する第３の量子化値を特定するステップと、
第２の量子化値及び前記第３の量子化値が平衡条件を満たさない場合に、前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換するステップとを含む方法。
【請求項２】
前記処理すべきグラフデータから分割されたサブグラフデータを取得するステップは、
ブロックチェーンネットワークでブロードキャストされた前記グラフデータに対応するタスク情報を取得するステップと、
前記タスク情報に基づいて、タスク実行可能ファイルと、前記グラフデータから分割されたサブグラフデータとを読み取るステップを含み、
前記サブグラフデータにおけるグラフノードに対する単位計算タスクを実行するステップは、
前記サブグラフデータに基づいて、前記サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するための前記タスク実行可能ファイルを実行するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第１の量子化値を取得するステップは、
完了済の単位計算タスクに相応するグローバル計算データを新しいブロックに書き込むステップと、
前記新しいブロックがブロックチェーンネットワークによって検証されると、前記新しいブロックを前記ブロックチェーンネットワークに追加して前記ブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成するステップとを含むことを特徴とする請求項１または２に記載の方法。
【請求項４】
前記第２の量子化値を取得するステップは、
前記グローバル計算データを前記新しいブロックに書き込む前の履歴第２の量子化値であって、前記グローバル計算データを前記新しいブロックに書き込む前にブロックチェーンデータが形成されず且つ完了済の単位計算タスクに対応する前記履歴第２の量子化値を取得するステップと、
前記履歴第２の量子化値から前記第１の量子化値を減算して、前記第２の量子化値を取得するステップとを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するステップは、
ブロックチェーンネットワークから最新のグローバル計算データを取得するステップと、
完了済の単位計算タスクに相応するローカル計算データを取得するステップと、
前記サブグラフデータ、完了済の単位計算タスクの数、前記グローバル計算データ及びローカル計算データに基づいて、前記第３の量子化値を特定することを含むことを特徴とする請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記方法は、
前記サブグラフデータの現在の第２の量子化値の第１の合計を取得するステップと、
前記サブグラフデータの現在の第３の量子化値の第２の合計を取得するステップと、
前記第１の合計に対する前記第２の合計のコントラスト値を特定するステップと、
前記コントラスト値が指定範囲外である場合、前記第２の量子化値及び前記第３の量子化値は前記平衡条件を満たさないと特定するステップとをさらに含むことを特徴とする請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記第１の合計に対する前記第２の合計のコントラスト値を特定するステップは、以下の式により、前記コントラスト値を計算するステップを含み、
2021524100.tif 000064
ただし、ａ及びｍはいずれも定数であり、ａ＞０、
2021524100.tif 000065
ｍ≧１であり、
2021524100.tif 000066
は前記第２の合計を表し、
2021524100.tif 000067
は前記第１の合計を表すことを特徴とする請求項６に記載の方法。
【請求項８】
前記指定範囲の最小値  μ(ｔ)  及び最大値λ(ｔ)は、いずれも時間ｔとともに変化する線形減少関数であり、且つ、μ(ｔ)  ＜λ(ｔ)であることを特徴とする請求項７に記載の方法。
【請求項９】
前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換するステップは、
前記コントラスト値が前記指定範囲の最小値よりも小さい場合に、前記第１の量子化値を前記他の計算ノードのグラフノードと交換し、交換後の前記コントラスト値が前記指定範囲内にある、ステップと、
前記コントラスト値が前記指定範囲の最大値よりも大きい場合に、前記グラフノードを前記他の計算ノードの第１の量子化値と交換し、交換後の前記コントラスト値が前記指定範囲内にある、ステップとを含むことを特徴とする請求項６に記載の方法。
【請求項１０】
前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換するステップは、
前記計算ノード及び前記他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び前記交換すべきグラフノードを引き換える第２の計算ノードを特定するステップと、
前記第１の計算ノードによる前記交換すべきグラフノードの第１の推定量子化値を特定するステップと、
前記第２の計算ノードによる前記交換すべきグラフノードの第２の推定量子化値を特定するステップと、
前記第１の推定量子化値及び前記第２の推定量子化値に基づいて、前記交換すべきグラフノードと交換するための第１の量子化値を特定するステップと、
前記計算ノードと前記他の計算ノードとの間で、前記交換すべきグラフノード、及び特定された前記第１の量子化値を交換するステップとを含むことを特徴とする請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記第１の計算ノードによる前記交換すべきグラフノードの第１の推定量子化値を特定するステップは、
以下の式により、前記第１の推定量子化値を計算するステップを含み、
2021524100.tif 000068
ただし、ｖｉは前記交換すべきグラフノードを表し、ｋは前記第１の計算ノードを表し、ｙ１（ｖｉ，ｋ）は前記第１の計算ノードによる前記交換すべきグラフノードの第１の推定量子化値を表し、Ｄｉは前記交換すべきグラフノードの第３の量子化値を表し、Ｃｉは前記交換すべきグラフノードの第２の量子化値を表し、
2021524100.tif 000069
は前記第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000070
は前記第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、α及びβはそれぞれシステムパラメータであり、ｅは自然対数の底であることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記第２の計算ノードによる前記交換すべきグラフノードの第２の推定量子化値を特定するステップは、以下の式により、前記第２の推定量子化値を計算するステップを含み、
2021524100.tif 000071
ただし、ｖｉは前記交換すべきグラフノードを表し、ｌは前記第２の計算ノードを表し、ｙ２（ｖｉ，ｌ）は前記第２の計算ノードによる前記交換すべきグラフノードの第２の推定量子化値を表し、Ｄｉは前記交換すべきグラフノードの第３の量子化値を表し、
2021524100.tif 000072
は前記第２の計算ノードｌにおけるグラフノードｊと前記交換すべきグラフノードｉとの通信距離の合計を表すことを特徴とする請求項１０に記載の方法。
【請求項１３】
以下の式により、前記通信距離を計算し、
2021524100.tif 000073
ただし、ｄｉｓｔ（ｉ，ｊ）は前記第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの間の通信距離を表し、
2021524100.tif 000074
はグラフノードｊとグラフノードｉとの間がエッジにより接続されることを表し、
2021524100.tif 000075
はグラフノードｊとグラフノードｉとの間にエッジがないことを表すことを特徴とする請求項１２に記載の方法。
【請求項１４】
グラフデータに基づくタスクスケジューリング装置であって、
処理すべきグラフデータから分割されたサブグラフデータを取得するための取得モジュールであって、第１の量子化値と第２の量子化値とをさらに取得し、前記第１の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成する際に前記完了済の単位計算タスクに対応する量子化値であり、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に前記完了済の単位計算タスクに対応する量子化値である、前記取得モジュールと、
前記取得モジュールによって取得された前記サブグラフデータにおけるグラフノードに対する単位計算タスクを実行する実行モジュールと、
前記サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するための特定モジュールと、
前記取得モジュールによって取得された前記第２の量子化値及び前記特定モジュールによって取得された前記第３の量子化値が平衡条件を満たさない場合に、他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換するための交換モジュールとを含む装置。
【請求項１５】
コンピュータ機器であって、メモリ及びプロセッサを含み、
前記メモリにコンピュータプログラムが記憶されており、
前記コンピュータプログラムがプロセッサによって実行されると、請求項１〜１３のいずれか一項に記載のグラフデータに基づくタスクスケジューリング方法を前記プロセッサに実行させるコンピュータ機器。
【請求項１６】
プロセッサによりロードされ実行されることで、請求項１〜１３のいずれか一項に記載のグラフデータに基づくタスクスケジューリング方法を実現することを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１８年５月１６日に提出した、出願番号が２０１８１０４６６７３９.Ｘであり、発明の名称が「グラフデータに基づくタスクスケジューリング方法及び装置」である中国特許出願の優先権を主張し、本願でその全ての内容を援用するものとする。
【０００２】
本出願は、グラフ計算技術の分野に関し、特に、グラフデータに基づくタスクスケジューリング方法、装置、プログラム及び機器に関する。
【背景技術】
【０００３】
コンピュータ技術の発展に伴い、「グラフ理論」を基とする、現実世界に対するグラフ構造の抽象的な表現、及びこのデータ構造での計算モード、つまり、グラフ計算が出現している。適用においては、ソーシャルネットワーク、商品購入関係、道路交通ネットワーク、通信ネットワークなどの情報をグラフデータで表すことができ、グラフデータに基づく計算ニーズもますます多くなり、複雑になる。
【０００４】
従来のグラフデータに基づく計算は、通常、分散型計算アーキテクチャに依存するが、現在の主流となるグラフデータのタスクスケジューリング方法は中心化されたスケジューリング方法である。例えば、スケジューリングキュー及びスケジューリングリソースプールに基づくＭａｐＲｅｄｕｃｅ(マップリデュースプログラミングモデル)クラスタスケジューリングアルゴリズムは、通常、パラメータサーバを使用して計算タスクのスケジューリング及び制御を統合に行う。
【０００５】
しかしながら、パラメータサーバを使用して計算タスクのスケジューリング及び制御を統合に行う場合に、計算タスクの処理効率はパラメータサーバの設置及び性能に依存し、一旦、データ量が多すぎになったり、パラメータサーバのフォールトトレラントが保証できなくなったりすると、グラフデータの処理効率が保証できず、且つ進行中の全ての計算タスクもエラーを報告することがある。特に、超大規模のデータを処理する計算タスクである場合に、従来の中心化されたタスクスケジューリング方法では、計算タスクのスケジューリングの効率が低いという課題がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
そこで、従来の中心化された計算タスクスケジューリング方法に計算タスクのスケジューリングの効率が低いことがある技術的課題に対して、グラフデータに基づくタスクスケジューリング方法、装置、記憶媒体及び機器を提供する必要がある。
【課題を解決するための手段】
【０００７】
一局面によれば、計算ノードが実行するグラフデータに基づくタスクスケジューリング方法を提供し、処理すべきグラフデータから分割されたサブグラフデータを取得し、前記サブグラフデータにおけるグラフノードに対する単位計算タスクを実行し、第１の量子化値を取得し、前記完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に前記完了済の単位計算タスクに対応する量子化値であり、第２の量子化値を取得し、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に前記完了済の単位計算タスクに対応する量子化値であり、前記サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定し、第２の量子化値と前記第３の量子化値とが平衡条件を満たさない場合、前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換することを含む。
【０００８】
一局面によれば、グラフデータに基づくタスクスケジューリング装置を提供し、処理すべきグラフデータから分割されたサブグラフデータを取得するための取得モジュールであって、第１の量子化値及び第２の量子化値を取得するために用いられ、前記第１の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に前記完了済の単位計算タスクに対応する量子化値であり、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に前記完了済の単位計算タスクに対応する量子化値である、前記取得モジュールと、前記取得モジュールによって取得された前記サブグラフデータにおけるグラフノードに対する単位計算タスクを実行するための実行モジュールと、前記サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するための特定モジュールと、前記取得モジュールによって取得された前記第２の量子化値と前記特定モジュールによって取得された前記第３の量子化値とが平衡条件を満たさない場合に、前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換するための交換モジュールとを含む。
【０００９】
一局面によれば、プログラムを提供し、プロセッサによりロードされ実行されることで、前記グラフデータに基づくタスクスケジューリング方法を実現する。
【００１０】
一局面によれば、コンピュータ機器を提供し、メモリ及びプロセッサを含み、前記メモリにコンピュータプログラムを記憶し、前記コンピュータプログラムがプロセッサによって実行されると、前記グラフデータに基づくタスクスケジューリング方法を前記プロセッサに実行させる。
【００１１】
処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれ取得することにより、第２の量子化値と第３の量子化値とが平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を指標し、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確かつ直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値と第３の量子化値とが平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がなく、計算ノード同士が互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡が実現され、特定のサーバの単一障害点及びネットワーク輻輳問題が回避され、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採択すれば、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【図面の簡単な説明】
【００１２】
本願実施例における技術案をより明確に説明するために、以下で実施例の記述において使用する必要がある図面を簡単に紹介し、もちろん、以下に記述の図面が本出願のいくつかの実施例に過ぎず、当業者にとって、創造的な労力をしない前提で、これらの図面に基づいて他の図面を得ることもできる。
【図１】一実施形態におけるグラフデータに基づくタスクスケジューリング方法の実行環境図である。
【図２】一実施形態におけるグラフデータに基づくタスクスケジューリング方法の概略フローチャートである。
【図３】一実施形態におけるサブグラフデータの概略図である。
【図４】一実施形態における相応するブロックチェーンデータがすでに形成され且つ完了済の単位計算タスクに対応する第１の量子化値を取得するステップの概略フローチャートである。
【図５】一実施形態におけるサブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するステップの概略フローチャートである。
【図６】一実施形態における第２の量子化値及び第３の量子化値が平衡条件を満たすか否かを判断するステップの概略フローチャートである。
【図７】一実施形態における計算ノードの間でグラフノード及び第１の量子化値を交換するステップの概略フローチャートである。
【図８】別の実施形態におけるグラフデータに基づくタスクスケジューリング方法の概略フローチャートである。
【図９】一実施形態におけるグラフデータに基づくタスクスケジューリング装置の構成ブロック図である。
【図１０】別の実施形態におけるグラフデータに基づくタスクスケジューリング装置の構成ブロック図である。
【図１１】一実施形態におけるコンピュータ機器の構成ブロック図である。
【発明を実施するための形態】
【００１３】
本願の目的、技術案、及び利点をより明確にするために、以下は、添付の図面を参照して、本願の実施形態についてより詳細に説明する。
【００１４】
図１は一実施形態におけるグラフデータに基づくタスクスケジューリング方法の実行環境図である。図１を参照して、当該グラフデータに基づくタスクスケジューリング方法は分散型グラフ計算システムが実行する。当該分散型グラフ計算システムは、制御ノード１１０、計算ノード１２０及びデータウェアハウス１３０を含む。制御ノード１１０及び計算ノード１２０は、ブロックチェーンネットワークを介して接続され、制御ノード１１０及び計算ノード１２０はそれぞれネットワークを介してデータウェアハウス１３０に接続される。制御ノード１１０は端末により実現されてもよく、当該端末はデスクトップ端末又はモバイル端末であってもよく、モバイル端末は例えば、携帯電話、タブレットコンピュータ、又はノートコンピュータなどであってもよい。制御ノード１１０は、スケジューリングのコアではなく、実行状態を監視及び修正するための端末として理解され得る。計算ノード１２０は、１つ又は複数のサーバに配置されたプログラムにより実現されてもよく、例えば、図１に示す計算ノードａ、ｂ、ｃなどはそれぞれ高性能コンピュータ１から高性能コンピュータＮにそれぞれ分散されている。なお、同一のネットワークに分散されている様々な高性能コンピュータは、性能が異なるため、異なる数の計算ノードを占有する。全ての制御ノード１１０及び計算ノード１２０はデータウェアハウス１３０に直接アクセスすることができ、例えば、計算タスクのアルゴリズムの実行可能ファイル及び入力を読み取り、計算結果を指定位置に記憶する。データウェアハウス１３０は集中型ストレージデバイスであってもよく、又は分散型ストレージクラスタ又はデバイスであってもよい。一実施例において、当該分散型グラフ計算システムは複数の計算ノードを有し、当該グラフデータに基づくタスクスケジューリング方法はいずれかの計算ノードが実行することができる。
【００１５】
図２に示すように、一実施例において、グラフデータに基づくタスクスケジューリング方法を提供する。本実施例において、主に、当該方法が上記の図１における計算ノード１２０が実行する例をとって説明する。図２を参照して、当該グラフ計算に基づくタスクスケジューリング方法は以下のステップを含む。
【００１６】
２０２において、処理すべきグラフデータから分割されたサブグラフデータを取得する。
【００１７】
なお、グラフデータは、グラフ構造を採用して組織化された構造化データであり、グラフ理論を適用することでエンティティ間の関係情報を記憶する。一般に、グラフデータはグラフノード及びグラフノード間のエッジからなる。グラフノードはグラフデータの頂点であり、グラフデータの本体を表すために使用できる。例えば、グラフデータを使用してソーシャルネットワークにおける個体間の情報を記憶する場合に、グラフデータにおける異なるグラフノードを使用して異なる個体を表してもよく、グラフデータを使用して商品購入関係を表す場合に、各ユーザー及び各商品はいずれも１つのグラフノードである。なお、グラフノードは、グラフノードのノード識別子及びノード属性などの情報を含んでもよい。グラフノード間のエッジはグラフデータのエッジであり、グラフデータにおける異なる本体間の関係を表すために使用できる。例えば、グラフデータを使用してソーシャルネットワークにおける個体間の情報を記憶する場合に、グラフデータにおける異なるグラフノードを使用して異なる個体を表し、グラフデータのエッジを使用して個体間の関係、例えば友達関係を表してもよく、グラフデータを使用して商品購入関係を表す場合に、各ユーザー及び各商品はいずれも１つのグラフノードであり、ユーザーが商品を購入することは一つのエッジなどとして表される。
【００１８】
数学的には、グラフ構造は、ダブルＧ＝＜Ｖ，Ｅ＞で表すことができ、なお、
2021524100.tif 000003
はグラフデータにおけるＮ個のグラフノードの集合を表し、
2021524100.tif 000004
はグラフノード間の接続エッジを表す。
【００１９】
処理すべきグラフデータは、計算ノードが処理しようとするグラフデータである。
【００２０】
サブグラフデータは、処理すべきグラフデータから分割された一部のグラフデータである。好ましく、１つの大きいグラフを一定数のサブグラフに分割することで、サブグラフにおけるエッジを可能な限り密にし、サブグラフ間のエッジを可能な限り疎にすることができる。図３を参照し、１つのグラフを５つのサブグラフに分割する概略図を示す。
【００２１】
一実施例において、グラフの規模が小さい場合に、Ｎ-ｃｕｔアルゴリズムを通じてサブグラフに分割されてもよく、グラフの規模が大きい場合に、近似アルゴリズムを通じてサブグラフに分割されてもよい。また、サブグラフの分割時に、上記分割要件に加えて、負荷平衡も考慮する必要がある。よって、１つの付加条件をさらに増加する必要があり、即ち、分割により形成されたサブグラフのサイズは計算ノードの能力に合わせる。
【００２２】
一実施例において、各計算ノードは１つ又は複数のサーバに配置されたプログラムであってもよく、計算ノードはブロックチェーンのような媒体により１つの仮想のネットワーク構造を構成してもよい。計算ノードは、データやタスク実行ログ、計算ノード状態などの情報を新しいブロックに書き込み、新しいブロックをブロックチェーンネットワークに追加することにより、計算ノード間の通信協調を便利に行うように寄与し、サブグラフデータに対応する計算タスクを完了させて、処理すべきグラフデータに対応する計算タスクを完了させることができる。なお、ブロックチェーンネットワークはブロックチェーン技術を実行させるキャリアや組織方式であって、各計算ノードの外部通信モジュールからなる１つの非中心化された分散型データベースである。
【００２３】
一実施例において、当該分散型グラフ計算システムには制御ノードを含み、制御ノードは、当該分散型グラフ計算システムにおける１つ又は複数の計算ノードと通信することで、このブロックチェーンネットワークにアクセスすることができる。制御ノードはグラフデータに対応するタスク情報を新しいブロックに記録し、新しいブロックをブロックチェーンネットワークに追加することにより、ブロックチェーンネットワークにおいて当該タスク情報をブロードキャストすることができる。このように、当該ブロックチェーンネットワークにおける全ての計算ノードはブロードキャストされるタスク情報を受信することができる。なお、タスク情報は計算タスクに関する情報である。
【００２４】
一実施例において、計算ノードはタイマーやタイミングプログラムなどによりブロックチェーンネットワークにおける最近追加された新しいブロックに記録されているタスク情報を定期的にチェックすることができる。当該新しいブロックにタスク情報を含んでいることを検出すると、計算ノードは自身の負荷状態を判断し、当該負荷状態は、当該計算ノードが過負荷ではないことを指標する場合に、ブロックチェーンネットワークから当該タスク情報をロードすることができる。
【００２５】
一実施例において、タスク情報は、タスク実行可能ファイルの取得経路、計算タスクを実行するアルゴリズムパラメータ、サブグラフデータの取得経路、計算結果の出力経路、及び所望完了時間などを含んでもよい。計算ノードは、ブロックチェーンネットワークから当該タスク情報をロードした後、グラフデータに対応するグラフ構造におけるサブグラフ構造を取得し、取得したサブグラフ構造に基づいてデータウェアハウスから相応するサブグラフデータを取得することができる。
【００２６】
一実施例において、ブロックチェーンネットワークから当該タスク情報をロードした後、計算ノードは、その自体の負荷状態に基づき、グラフデータに対応するグラフ構造から一定数のグラフノード及び相応するエッジをランダムに取得してサブグラフ構造を構成することができる。計算ノードは、さらに、当該タスク情報に記載されているサブグラフデータの取得経路に従って、データウェアハウスから当該サブグラフ構造に対応するサブグラフデータを取得する。
【００２７】
一実施例において、分散型グラフ計算システムは、現在の計算ノードの数に従って、グラフデータを予め設定された条件に従って相応する数のサブグラフデータに分割することができる。なお、予め設定された条件は、平均分割やランダム分割などであってもよく、本実施例において限定しない。
【００２８】
２０４において、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行する。
【００２９】
なお、単位計算タスクは当該分散型グラフ計算システムにおける最小計算割当単位であり、例えば、今回の反復計算中に、あるグラフノードに対応する計算タスクである。本実施例においては、計算ノードがグラフデータから分割したサブグラフデータを取得した後、取得したサブグラフデータにおけるグラフノードに対して相応する計算を行うことができる。
【００３０】
一実施例において、計算ノードはタスク情報をロードした後、タスク情報に記載されているタスク実行可能ファイルの取得経路、及び計算タスクを実行するアルゴリズムパラメータなどの情報に基づき、データウェアハウスからタスク実行可能ファイル及び計算タスクを実行するアルゴリズムパラメータをプルする。さらに、計算ノードは、サブグラフデータを取得した後に、計算タスクを実行するアルゴリズムパラメータ、プルされたタスク実行可能ファイルを実行して、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行する。
【００３１】
一実施例において、グラフデータグラフデータに対して行う計算は反復計算であり、アルゴリズムの反復更新につれて、毎回の反復において新しい計算タスクを生成する。サブグラフデータにおける各グラフノードはアルゴリズム駆動により、計算完了すべき単位計算タスクを継続的に生成することができる。
【００３２】
２０６において、第１の量子化値を取得し、前記第１の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に、当該完了済の単位計算タスクに対応する量子化値である。
【００３３】
なお、ブロックチェーンデータはブロックチェーンネットワークに追加された新しいブロックに記録されているデータであり、ブロックチェーンネットワークにおける新しいブロックは記録された情報をブロードキャスト方式で共有することができる。量子化値は単位計算タスクを量子化することで得られる値であり、例えば、１つの単位計算タスクは１つの単位の量子化値に対応する。第１の量子化値は、計算ノードにおける完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に、当該完了済の単位計算タスクを量子化することで得られる数値である。第１の量子化値は計算ノードの計算能力を指標し、一部の完了済の単位計算タスクに対応する。第１の量子化値は、ブロックチェーンネットワークにおいて流通及び交換されるリソースであってもよく、通貨値、仮想通貨値などと呼ばれ得る。
【００３４】
本実施例において、計算ノードは、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行した後に、一部の完了済の単位計算タスクに対応するデータをブロックチェーンネットワークに記録してブロックチェーンデータを形成することができ、この一部の完了済の単位計算タスクに対応する量子化値は第１の量子化値である。
【００３５】
一実施例において、計算ノードは、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行した後に、相応する単位計算タスクを完了する。計算ノードは、相応する単位計算タスクを完了済の後に、サブグラフデータを計算するグローバル計算データ及びローカル計算データを得ることができる。なお、グローバル計算データは、各計算ノードがサブグラフデータを計算する過程でグローバルに共有・更新する必要があるデータであり、グローバル計算データの規模は限られる。ローカル計算データは、各計算ノードがサブグラフデータを計算する過程で少数の計算ノードによってのみ使用及び更新されるデータである。
【００３６】
一実施例において、計算ノードは、グローバル計算データを新しいブロックに記録でき、新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加し、この場合、当該グローバル計算データはブロックチェーンデータを形成する。一実施例において、計算ノードは、また、前のブロックから現在の時間までの全ての関連データ、例えば、現在のグローバル計算データ、タスク実行ログ又は計算ノード状態を、新しいブロックに記録し、新しいブロックをブロックチェーンネットワークに追加し、相応する第１の量子化値を取得することもできる。
【００３７】
一実施例において、新しいブロックに記録されている関連データをアクティブにブロードキャストすることで、分散型グラフ計算システムにおける全ての計算ノードは、記録された関連データ、例えば、新しいブロックに記録されているグローバル計算データを共有してもよい。又は、要求の形式で新しいブロックに記録されている関連データを拡散してもよい。なお、要求の形式での拡散は、計算ノードが要求を送信するように新しいブロックに記録されている関連データを取得できることを指す。
【００３８】
１つの例示的な適用シナリオでは、グラフデータに関するグラフ計算問題において、当該グラフデータに対応するグラフ構造は通常、比較的まばらなグラフであり、グラフデータ内のエッジ数Ｍをグラフノード数Ｎの２つずつの組み合わせよりもはるかに少なくし、
2021524100.tif 000005
である。このように、通常グローバルに共有する必要があるグローバル計算データの規模は限られ、ほとんどのデータには一定の局所性があり、少数の計算ノードの計算によってのみ使用され、即ち、ほとんどのデータはローカル計算データである。当該分散型グラフ計算システムを採用し、グローバル計算データをブロックチェーンネットワークを介してグローバルに共有し、ローカル計算データを相応する計算ノードにバッファリングし、要求の形式で当該ローカル計算データを取得することにより、ローカル計算データを大量にブロードキャストすることによって引き起こされるネットワーク通信オーバーヘッドを回避する。
【００３９】
２０８において、第２の量子化値を取得し、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に当該完了済の単位計算タスクに対応する量子化値である。
【００４０】
なお、第２の量子化値は計算ノードにおける完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に、当該完了済の単位計算タスクを量子化することで得られる数値である。第２の量子化値は計算ノードの計算能力を指標し、計算ノードにおける他の一部の完了済の単位計算タスクに対応する。第２の量子化値は、計算ノードが現在所有している、第１の量子化値に引き換えられ得るリソースであってもよく、資産値と呼ばれ得る。計算ノードは、完了済の単位計算タスクに対応するデータを、ブロックチェーンネットワークに記憶しブロックチェーンデータを形成した後に、この一部のブロックチェーンデータに対応する資産値はブロックチェーンネットワークを流通している同じ数額の通貨値に変換することができる。
【００４１】
本実施例において、計算ノードは、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行した後に、データを取得する。計算ノードは、ブロックチェーンネットワークに記録されないデータに応じて、当該データに対応する完了済の単位計算タスクを特定する。コンピュータノードは、また、特定された完了済の単位計算タスクを量子化することで、第２の量子化値を取得する。一実施例において、計算ノードは、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行した後に、相応する単位計算タスクを完了する。計算ノードは相応する単位計算タスクを完了済のと、完了済の単位計算タスクに対応する第２の量子化値を取得することができる。
【００４２】
一実施例において、計算ノードはグローバル計算データを新しいブロックに書き込む前に、完了済の単位計算タスクに対応する履歴第２の量子化値（歴史第２の量子化値は過去第２の量子化値を指す）を取得する。なお、履歴第２の量子化値は、グローバル計算データを新しいブロックに書き込む前にブロックチェーンデータを形成せず、且つ完了済の単位計算タスクに対応する。計算ノードはグローバル計算データを新しいブロックに書き込み、且つ該新しいブロックがブロックチェーンネットワークによって検証されると、履歴第２の量子化値から減算して書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成し、現在の第２の量子化値を取得する。
【００４３】
このように、グローバル計算データを新しいブロックに書き込んでブロックチェーンデータを生成することにより、相応する履歴第２の量子化値を第１の量子化値に変換することができる。会計のように、将来引き換え得る第２の量子化値が相応する流通可能な第１の量子化値に迅速かつ便利に変換される。このようにすれば、第１の量子化値と現在の第２の量子化値との合計は、計算ノードの現在の計算能力を示すことができる。
【００４４】
２１０において、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定する。
【００４５】
なお、第３の量子化値は、計算ノードにおける未完了の単位計算タスクを量子化することで得られる数値である。第３の量子化値は、計算ノードが計算しようとする単位計算タスクに対応する数値であってもよく、負債値と呼ばれ得、計算ノードの負荷状態を指標する。計算ノードは、未完了の単位計算タスクを実行し完了した後に、当該未完了の単位計算タスクに対応する第３の量子化値を、同じ数額の第２の量子化値に変換し、さらに、同じ数額の第１の量子化値に変換することができる。
【００４６】
本実施例において、計算ノードは、現在の未完了の単位計算タスクをリアルタイムで取得し、未完了の単位計算タスクに応じて、第３の量子化値を特定することができる。一実施例において、第１の量子化値、第２の量子化値及び第３の量子化値は単位が同じであり、単位計算タスクに対応する。
【００４７】
一実施例において、グラフデータに対応する全タスクは一定であり、各計算ノードにおけるサブグラフデータから生成されるサブタスクも一定である。計算ノードはサブグラフデータにおけるグラフノードに対する単位計算タスクを実行する場合に、単位計算タスクを継続的に完了する。計算ノードは、サブグラフデータから生成されるサブタスク、及び現在の完了済の単位計算タスクに応じて、現在の未完了の単位計算タスクを取得し、さらに、相応する第３の量子化値を特定する。
【００４８】
一実施例において、グラフデータに対応する全タスクは絶えず変化し、各計算ノードにおけるサブグラフデータから生成されるサブタスクも絶えず変化する。計算ノードはサブグラフデータに応じて計算タスクを繰り返し生成することができる。アルゴリズムの反復更新により、各反復中に新しい計算タスクを生成する。サブグラフデータにおける各グラフノードはアルゴリズム駆動により、計算を完了する必要がある単位計算タスクを継続的に生成することができる。
【００４９】
一実施例において、計算ノードは、サブグラフデータ、完了済の単位計算タスクの数、完了済の単位計算タスクの内容、ブロックチェーンネットワークで共有されるグローバル計算データ、及びローカル計算データに応じて、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定することができる。
【００５０】
２１２において、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換する。
【００５１】
なお、平衡条件は予め設置される、計算ノードの現在の計算能力と負荷状態との間が平衡であるかどうかを測定するための条件である。一実施例において、第２の量子化値及び第３の量子化値が平衡条件を満たすことは、第３の量子化値の第２の合計と第２の量子化値の第１の合計のコントラスト値が指定範囲内にあることを意味する。なお、コントラスト値は２つの数値の差の値であり、数学的な計算によって特定できる。数学的計算は、２つの数値の直接除算、対数取得後の除算、減算、他の演算後の対数取得後の除算などであってもよい。  コントラスト値は、ある値と別の値との差の状態を指標する。
【００５２】
本実施例において、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードの間でグラフノード及び第１の量子化値を交換し、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持する。
【００５３】
一実施例において、平衡条件に対応する指定範囲は予め設定された固定範囲であってもよいし、時間とともに変化する関数によって特定される範囲であってもよい。
【００５４】
上記のグラフデータに基づくタスクスケジューリング方法は、処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれ取得することにより、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を測定でき、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確で直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がないが、計算ノード同士が互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡を実現し、特定のサーバの単一障害点及びネットワーク輻輳問題を回避し、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採用すると、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【００５５】
一実施例において、ステップ２０２は、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、タスク情報に応じて、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取ることを含むことができる。ステップ２０４は、サブグラフデータに応じて、サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するためのタスク実行可能ファイルを実行することを含むことができる。
【００５６】
本実施例において、計算ノードは、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、当該タスク情報に応じて、ローカル又はデータウェアハウスから、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取ることができる。当該サブグラフデータに応じて、タスク実行可能ファイルを実行して、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行する。
【００５７】
一実施例において、当該分散型グラフ計算システムには制御ノードを含み、制御ノードは、グラフデータに対応するタスク情報を新しいブロックに記録し、新しいブロックをブロックチェーンネットワークに追加することにより、ブロックチェーンネットワークにおいて当該タスク情報をブロードキャストすることができる。
【００５８】
一実施例において、ブロックチェーンネットワークにおける全ての計算ノードは、新しいブロックのブロードキャストによりグラフデータに対応するタスク情報を受信することができる。
【００５９】
一実施例において、計算ノードは、タイマーや、タイミングプログラムなどによりブロックチェーンネットワークにおける最近追加された新しいブロックに記録されているタスク情報を定期的にチェックすることで、ブロックチェーンネットワークでブロードキャストされた、グラフデータに対応するタスク情報をアクティブに取得することができる。
【００６０】
上記の実施例において、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、また、当該タスク情報に応じて、タスク実行可能ファイル及びサブグラフデータを読み取り、サブグラフデータに応じて当該タスク実行可能ファイルを実行することにより、単位計算タスクの実行を実現することができる。なお、タスク情報は１つ非常に軽い(即ち、データの量が小さい)ファイルであり得、このように、ブロックチェーンネットワークを介してタスクのリリースを行うことで、分散型グラフ計算システムにおけるタスクのリリース及び取得の通信量を大幅に削減し、タスクのリリースの効率を大幅に向上させることができる。
【００６１】
一実施例において、ステップ２０６は以下のステップを含むことができる。
【００６２】
４０２において、完了済の単位計算タスク相応するグローバル計算データを新しいブロックに書き込む。
【００６３】
一実施例において、上記のブロックチェーンネットワークは、１つのプライベートブロックチェーンからなることができ、ブロックチェーンネットワークにデータを記録するために必要な鍵は、非対称暗号化アルゴリズム標準に従って事前に生成され、データウェアハウスに記憶される。計算ノードは、使用する必要がある際にデータウェアハウスにアクセスして、関連キーを取得することができる。なお、非対称暗号化アルゴリズムは、楕円曲線暗号化アルゴリズム又はＲＳＡ暗号化アルゴリズム(非対称暗号化アルゴリズム)などであってもよい。
【００６４】
一実施例において、計算ノードは、相応するコンセンサスアルゴリズムに応じて新しいブロックを生成することができる。コンセンサスアルゴリズムはコンセンサスハッシュアルゴリズムなどであってもよい。計算ノードは、完了済の単位計算タスクに対応するグローバル計算データを新しいブロックに書き込むことができる。一実施例において、計算ノードは、グローバルデータ、タスク実行ログ、グラフノードの交換データ又は計算ノード状態などの情報を新しいブロックに書き込むことができる。
【００６５】
一実施例において、ブロックチェーンがプライベートブロックチェーンである場合に、コンセンサスハッシュアルゴリズムのビット数を削減し、処理効率を向上し、システムスループットを上げる目的に達成する。例えば、コンセンサスハッシュアルゴリズムのビット数を削減する場合に、２５６ビットのＳＨＡではなく、１２８ビットのＳＨＡ(Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ、セキュアハッシュアルゴリズム)を使用してもよく、コンセンサスハッシュアルゴリズムをＰＯＳ(Ｐｒｏｏｆ  ｏｆ  Ｗｏｒｋ、プルーフオブステーク)に調整し、コイン日数＝第３の量子化値*年齢を使用して次の新しいブロックの生成者を特定する。一般に、グラフデータの交換量が１秒間に１００万回を超える場合、分散型グラフ計算システムは良い通信効率を達成することができる。一例において、以下の分割的関数をコンセンサスハッシュ関数のビット数の標準として採用することができる。
2021524100.tif 000006
2021524100.tif 000007
は交換すべきグラフノードを提供する第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000008
は交換すべきグラフノードを提供する第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、
2021524100.tif 000009
は交換すべきグラフノードを提供する第１の計算ノードｋにおけるグラフノードの平均コイン日数を表し、η及びδはそれぞれ閾値である。
【００６６】
一実施例において、各計算ノードは、デフォルトで、現在所有している第１の量子化値が最も多い計算ノードが新しいブロックを生成することを許容することができる。この場合、第１の量子化値の生成は、第１の量子化値が最も少ない計算ノードに割り当てられ、それにより、より高い協調効率を実現する。ここでの第１の量子化値は第２の量子化値又は第３の量子化値に置き換えられてもよい。
【００６７】
一実施例において、コンセンサスハッシュ関数について、コンセンサスプレフィックス０を制約する数を採用して複雑さを制御することができ、ビット数の制御と類似して、ハッシュ結果プレフィックス０を制約する数が多いほど、コンセンサス問題の難しさが大きくなる。
【００６８】
４０４において、新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成する。
【００６９】
一実施例において、計算ノードで形成された新しいブロックがブロックチェーンネットワークによって検証されると、計算ノードは、当該新しいブロックをブロックチェーンネットワークに追加し、この場合、当該新しいブロックに書き込まれたグローバル計算データはブロックチェーンデータを形成する。計算ノードは書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成することができる。
【００７０】
上記の実施例において、完了済の単位計算タスク相応するグローバル計算データを新しいブロックに書き込み、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、新しいブロックがブロックチェーンネットワークによって検証されると、第１の量子化値を迅速かつ便利に生成し、当該第１の量子化値はブロックチェーンネットワークにおいて流通及び交換することができる。
【００７１】
一実施例において、ステップ２１０は以下のステップを含む。
【００７２】
５０２において、ブロックチェーンネットワークから最新のグローバル計算データを取得する。
【００７３】
一実施例において、計算ノードはブロックチェーンネットワークを介して新しいブロックに記録されている最新のグローバル計算データを取得することができる。一実施例において、計算ノードは新しいブロックを定期的にチェックするように、ブロックチェーンネットワークから最新のグローバル計算データを取得する。
【００７４】
５０４において、完了済の単位計算タスクに相応するローカル計算データを取得する。
【００７５】
一実施例において、計算ノードは、ローカルにバッファリングされたローカル計算データ、又はサブグラフ構造内の隣接する計算ノードから取得されたバッファリングされたローカル計算データを読み取ることができる。
【００７６】
５０６において、サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定する。
【００７７】
一実施例において、計算ノードは、サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定することができる。例えば、以下の式でグラフノードｉの単位計算タスクに対応する第３の量子化値を計算することができ、
2021524100.tif 000010
である。
2021524100.tif 000011
は、現在の単位計算タスクに対応する第３の量子化値を表し、ｖｉはサブグラフデータ、即ち、サブグラフが接続するエッジ、グラフノード属性情報などを表し、
2021524100.tif 000012
は現在の単位計算タスクが依存する前のｓ個の時点の完了済の単位計算タスクを表し、θｔは現在のグローバル計算データであり、
2021524100.tif 000013
は現在のローカル計算データである。
【００７８】
上記の実施例において、サブグラフデータ、完了済の単位計算タスクの数、最新のグローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定でき、計算ノードの将来一定期間における負荷状態を正確かつ効率的に予測することができる。サブグラフデータにおけるグラフノードの数を動的に変化させるか、又はエッジ数を動的増加させても現在のグローバル計算データ及びローカル計算データに影響を与えず、計算ノードは完了済の計算タスクを基にさらに計算し、グラフデータの処理効率を大幅に向上させる。
【００７９】
一実施例において、グラフデータに基づくタスクスケジューリング方法は、第２の量子化値及び第３の量子化値が平衡条件を満たすかどうかを判断するステップをさらに含み、当該ステップは、以下のステップを含むことができる。
【００８０】
６０２において、サブグラフデータの現在の第２の量子化値の第１の合計を取得する。
【００８１】
一実施例において、各計算ノードは、現在の計算ノードにおけるサブグラフデータにおける全てのブロックチェーンデータを形成せず、且つ完了済の単位計算タスクを特定し、さらに、第２の量子化値の第１の合計を特定することができる。
【００８２】
６０４において、サブグラフデータの現在の第３の量子化値の第２の合計を取得する。
【００８３】
一実施例において、各計算ノードは、現在の計算ノードにおけるサブグラフデータにおける全ての未完了の単位計算タスクを特定し、さらに、第３の量子化値の第２の合計を特定する。
【００８４】
６０６において、第１の合計に対する第２の合計のコントラスト値を特定する。
【００８５】
一実施例において、計算ノードは、第１の合計及び第２の合計に対して数学的計算を行うことで、第１の合計に対する第２の合計のコントラスト値を特定することができる。なお、数学的計算は、２つの数の直接除算、対数取得後の除算、減算、別の演算後の対数取得後の除算などであってもよい。
【００８６】
一実施例において、第２の量子化値及び第３の量子化値が時間とともに変化し指数で増加することを考慮したので、計算ノードは、それぞれ第２の合計及び第１の合計について対数をとった後に比を計算することができ、このように、第１の合計に対する第２の合計のコントラスト値は線形に変化し続ける。
【００８７】
一実施例において、計算ノードは以下の式により、コントラスト値を計算することができ、
2021524100.tif 000014
ただし、ａ及びｍは定数であり、ａ＞０、且つａ≠１、ｍ≧１であり、
2021524100.tif 000015
は第２の合計を表し、 
2021524100.tif 000016
は第１の合計を表す。
【００８８】
別の実施形態において、第２の合計を第１の合計で直接除算して、第１の合計に対する第２の合計のコントラスト値を取得することができる。計算ノードは、以下の式により、コントラスト値を計算することができ、
2021524100.tif 000017
ただし、
2021524100.tif 000018
は第２の合計を表し、
2021524100.tif 000019
は第１の合計を表す。
【００８９】
６０８において、コントラスト値が指定範囲外である場合、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定する。
【００９０】
一実施例において、指定範囲を予め設定でき、コントラスト値が当該指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定し、コントラスト値が当該指定範囲内であると、第２の量子化値及び第３の量子化値が平衡条件を満たすと特定する。
【００９１】
一実施例において、コントラスト値が第２の合計と第１の合計が対数をとった後に除算して得られた値である場合、指定範囲の最小値μ(ｔ)  及び最大値λ(ｔ)は時間ｔとともに変化する線形減少関数であり、且つμ(ｔ)  ＜λ(ｔ)である。例えば、以下の式で、コントラスト値が指定範囲内であることを表すことができる。
2021524100.tif 000020
【００９２】
１つの例示的な実施例において、定数ａは１０、定数ｍは１であり得ると、上記の式は、
2021524100.tif 000021
として簡略化することができる。
【００９３】
別の実施形態において、コントラスト値が第２の合計と第１の合計の商である場合、指定範囲の最小値μ(ｔ)  及び最大値λ(ｔ)は時間ｔとともに変化するべき関数であり、且つμ(ｔ)  ＜λ(ｔ)である。例えば、以下の式で、コントラスト値が指定範囲内であることを表すことができる。
2021524100.tif 000022
【００９４】
一実施例において、上記の指定範囲は、固定範囲であってもよく、例えば、第１の閾値及び第２の閾値によって特定される固定範囲である。
【００９５】
一実施例において、コントラスト値が指定範囲の最小値よりも小さい場合、現在の計算ノードの第１の量子化値を他の計算ノードのグラフノードと交換することで、交換後の再計算されたコントラスト値が指定範囲にあることを保持し、コントラスト値が指定範囲の最大値よりも大きい場合、現在の計算ノードのグラフノードを他の計算ノードの第１の量子化値と交換することで、交換後の再計算されたコントラスト値が指定範囲にあることを保持する。
【００９６】
一実施例において、コントラスト値が指定範囲の最小値よりも小さいと、計算ノードは、第１の量子化値の交換により新しいグラフノードを取得することを試み、少ない第１の量子化値を優先的に交換して新しいグラフノードを取得する。コントラスト値が指定範囲の最大値よりも大きい場合、計算ノードは、自己が所有しているグラフノードを交換し出することを試み、交換してより多い第１の量子化値を取得できるグラフノードを優先的に交換する。
【００９７】
なお、上記の実施例において、コントラスト値は第１の合計に対する第２の合計のコントラスト値であり、コントラスト値が指定範囲の最小値よりも小さい場合、現在の計算ノードの第１の量子化値を他の計算ノードのグラフノードと交換し、コントラスト値が指定範囲の最大値よりも大きい場合、現在の計算ノードのグラフノードを他の計算ノードの第１の量子化値と交換し、交換後の再計算されたコントラスト値が指定範囲内にあることを保持する。それに相応し、コントラスト値は第２の合計に対する第１の合計のコントラスト値であり、コントラスト値が指定範囲の最大値よりも大きい場合、現在の計算ノードの第１の量子化値を他の計算ノードのグラフノードと交換し、コントラスト値が指定範囲の最小値よりも小さい場合、現在の計算ノードのグラフノードを他の計算ノードの第１の量子化値と交換し、交換後の再計算されたコントラスト値が指定範囲内にあることを保持する。
【００９８】
上記の実施例において、サブグラフデータの現在の第２の量子化値の第１の合計、及びサブグラフデータの現在の第３の量子化値の第２の合計のコントラスト値を特定することで、コントラスト値が指定範囲内にあるかどうかを判断し、コントラスト値が指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定する。このように、第２の量子化値及び第３の量子化値が平衡条件を満たすかどうかを快速で正確に特定でき、計算ノードの間でグラフノード及び第１の量子化値を効果的に交換し、計算ノード同士が互いに協調してグラフノードを動的に割り当てることで、自己組織化された負荷平衡を実現する。
【００９９】
一実施例において、グラフノード及び第１の量子化値を他の計算ノードと交換するステップは以下のステップを含むことができる。
【０１００】
７０２において、計算ノード及び他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定する。
【０１０１】
一実施例において、計算ノードにおける第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノード間で互いにグラフノード及び第１の量子化値を交換し、各計算ノードにおける第２の量子化値及び第３の量子化値が平衡条件を満たすことを維持する。即ち、現在の計算ノードは他の計算ノードとグラフノード及び第１の量子化値を交換することができる。このように、交換すべき計算ノードの間で、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定する必要がある。
【０１０２】
７０４において、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定する。
【０１０３】
なお、推定量子化値は、推定される、交換すべきグラフノードが所有している未完了の単位計算タスクを量子化する値である。第１の推定量子化値は交換すべきグラフノードを提供する第１の計算ノードが、交換すべきグラフノードが所有している未完了の単位計算タスクを量子化する値である。推定量子化値及び第１の量子化値は単位が同じである。
【０１０４】
一実施例において、計算ノードが第１の計算ノードである場合に、計算ノードは、交換すべきグラフノードに対応する第２の量子化値と第１の計算ノードに対応する第２の量子化値との関係、交換すべきグラフノードに対応する第３の量子化値と第１の計算ノードに対応する第３の量子化値との関係に応じて、第１の推定量子化値を特定することができる。
【０１０５】
一実施例において、計算ノードは、以下の式により第１の推定量子化値を計算することができ、
2021524100.tif 000023
ただし、ｖｉは交換すべきグラフノードを表し、ｋは第１の計算ノードを表し、ｙ１（ｖｉ，ｋ）は第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、Ｃｉは交換すべきグラフノードの第２の量子化値を表し、
2021524100.tif 000024
は第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000025
は第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、α及びβはそれぞれシステムパラメータであり、ｅは自然対数の底である。
【０１０６】
７０６において、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定する。
【０１０７】
なお、第２の推定量子化値は、交換すべきグラフノードを引き換える第２の計算ノードであり、交換すべきグラフノードが所有している未完了の単位計算タスクを量子化する値である。
【０１０８】
一実施例において、計算ノードが第２の計算ノードである場合に、計算ノードは第２の推定量子化値を特定する際に、交換すべきグラフノードを引き換えた後に、第２の計算ノードに対応する計算ノードが増加する必要がある計算タスク及び削減する通信距離量を考慮し、従って、計算ノードは、交換すべきグラフノードの第３の量子化値、及び交換すべきグラフノードと第２の計算ノードにおけるグラフノードとの間の通信距離に応じて、第２の推定量子化値を特定することができる。
【０１０９】
一実施例において、計算ノードは、以下の式により、第２の推定量子化値を計算することができ、
2021524100.tif 000026
ただし、ｖｉは交換すべきグラフノードを表し、ｌは第２の計算ノードを表し、ｙ２（ｖｉ，ｌ）は第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、
2021524100.tif 000027
は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの通信距離の合計を表す。
【０１１０】
一実施例において、ｄｉｓｔ（ｉ，ｊ）はグラフノードｉとグラフノードｊとの間の通信距離を表すことができる。グラフデータにおける任意の２つのグラフノードの間の通信距離を計算する計算量が大きいため、計算ノードは数学の近似法を使用してグラフノード間の通信距離を計算し、例えば、ローカル近似法を採用してグラフノード間の通信距離を計算してもよく、以下の式により、グラフノード間の通信距離を計算することができ、
2021524100.tif 000028
ただし、ｄｉｓｔ（ｉ，ｊ）は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの間の通信距離を表し、
2021524100.tif 000029
はグラフノードｊとグラフノードｉとの間がエッジにより接続されることを表し、
2021524100.tif 000030
はグラフノードｊとグラフノードｉとの間にエッジがないことを表す。
【０１１１】
つまり、当グラフノードｉとグラフノードｊとの間がエッジにより接続される場合に、グラフノードｉとグラフノードｊとの距離が非常に短いとほぼ考えられる。第２の計算ノードに対応する計算ノードが交換すべきグラフノードを引き換えた後に、計算ノードは通信距離を減少でき、従って、第２の推定量子化値は高くなる。グラフノードｉとグラフノードｊとの間にエッジなしで接続されている場合、第２の計算ノードに対応する計算ノードが交換すべきグラフノードを引き換えた後に、計算ノードは通信距離を減少する。
【０１１２】
一実施例において、計算ノードは、さらに、他の近似法方を使用してグラフノード間の通信距離を計算してもよく、例えば、計算すべき２つのグラフノード間に共通の隣接グラフノードがあるかどうかを判断し、２つのグラフノード間に共通の隣接グラフノードがあると、２つのグラフノード間の通信距離が短いと考えられ、第２の計算ノードに対応する計算ノードが交換すべきグラフノードを引き換えると、計算ノードが削減する通信量もより多くなる。また、例えば、計算ノードは、確率的ロードマップ法に従って２つのグラフノードごとに経路を生成することができ、同じ経路上のグラフノードは、通信距離が短いと考えられ、第２の計算ノードに対応する計算ノードが、交換すべきグラフノードと引き換えた後、計算ノードが削減する通信量もより多くなる。
【０１１３】
７０８において、第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定する。
【０１１４】
一実施例において、計算ノードは、第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定することができる。例えば、計算ノードは、第１の推定量子化値と第２の推定量子化値の平均値を計算し、平均値を、交換すべきグラフノードと交換する第１の量子化値としてもよい。又は、計算ノードは、一定の重み比に応じて、第１の推定量子化値及び第２の推定量子化値を重み付けて和を求めた後に平均値をとり、平均値を交換すべきグラフノードと交換する第１の量子化値などとしてもよい。
【０１１５】
７１０において、計算ノードと他の計算ノードとの間に、交換すべきグラフノードと特定された第１の量子化値との交換を行う。
【０１１６】
一実施例において、交換すべき計算ノードの間で、第２の計算ノードは、特定された第１の量子化値で第１の計算ノードの交換すべきグラフノードを引き換えることができる。
【０１１７】
上記の実施例において、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値、及び第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定し、このように、第１の計算ノード及び第２の計算ノードの実際の状況を包括的に考慮することができ、交換すべき計算ノードの間で、交換すべきグラフノードと第１の量子化値の交換を公平に行う。
【０１１８】
図８に示すように、１つの例示的な実施例において、グラフデータに基づくタスクスケジューリング方法は以下のステップを含む。
８０２において、ブロックチェーンネットワークでブロードキャストされた処理すべきグラフデータに対応するタスク情報を取得する。
８０４において、タスク情報に応じて、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取る。
８０６において、サブグラフデータに応じて、サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するためのタスク実行可能ファイルを実行する。
８０８において、完了済の単位計算タスク相応するグローバル計算データを新しいブロックに書き込む。
８１０において、新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成する。
８１２において、グローバル計算データを新しいブロックに書き込む前の履歴第２の量子化値を取得し、履歴第２の量子化値は、グローバル計算データを新しいブロックに書き込む前にブロックチェーンデータを形成せず且つ完了済の単位計算タスクに対応する。
８１４において、履歴第２の量子化値から第１の量子化値を減算して、第２の量子化値を取得する。
８１６において、ブロックチェーンネットワークから最新のグローバル計算データを取得する。
８１８において、完了済の単位計算タスクに相応するローカル計算データを取得する。
８２０において、サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定する。
８２２において、サブグラフデータ現在の第２の量子化値の第１の合計を取得する。
８２４において、サブグラフデータ現在の第３の量子化値の第２の合計を取得する。
８２６において、第１の合計に対する第２の合計のコントラスト値を特定する。
８２８において、コントラスト値が指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定する。
８３０において、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノード及び他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定する。
８３２において、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定する。
８３４において、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定する。
８３６において、第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を交換する。
８３８において、計算ノード及び他の計算ノードの間で、交換すべきグラフノードと特定された第１の量子化値を交換する。
【０１１９】
上記のグラフデータに基づくタスクスケジューリング方法は、処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれ取得することにより、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を指標し、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確かつ直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がないが、計算ノード同士が互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡を実現し、特定のサーバの単一障害点及びネットワーク輻輳問題を回避し、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採用すると、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【０１２０】
図８は一実施形態におけるグラフデータに基づくタスクスケジューリング方法の概略フローチャートである。図８のフローチャートにおける各ステップは矢印で示されるように順に実行されるが、これらのステップは、矢印で示される順序に応じて順に実行されるわけではないと理解すべきである。本明細書に明確に説明しない限り、これらのステップの実行順序が制限されず、これらのステップが他の順序で実行されてもよい。且つ、図８における少なくとも一部のステップは複数のサブステップ又は複数のフェーズを含んでもよく、これらのサブステップ又はフェーズが必ず同じ時刻に実行して完了するわけではなく、異なる時刻に実行されてもよく、これらのサブステップ又はステップの実行順序が必ず順に行われるわけではなく、他のステップ又は他のステップのサブステップ又はステップの少なくとも一部と順番又は交互に実行されてもよい。
【０１２１】
１つの例示的な適用シナリオにおいて、例えば、ＴＳＰ問題(Ｔｒａｖｅｌｉｎｇ  Ｓａｌｅｓｍａｎ  Ｐｒｏｂｌｅｍ、巡回セールスマン問題)において、上記のグラフデータに基づくタスクスケジューリング方法で最適解を効率的に求めることができる。なお、ＴＳＰ問題は、セールスマンが如何に最短距離で全ての都市（グラフノード）を巡り、出発地に戻るかのことを指す。これは１つのＮＰ(Ｎｏｎ-ｄｅｔｅｒｍｉｎｉｓｔｉｃ  Ｐｏｌｙｎｏｍｉａｌ、非特定性多項式)完全問題であり、通常、問題の近似解を求める。このスキームにおけるグラフデータに基づくタスクスケジューリング方法により、当該ＴＳＰ問題をサブグラフにおける最も短いトラバース問題に分割し、即ち、ローカル最適解を見つけることでグローバル最適解に近似してアプローチすることができる。なお、グローバル計算データはグラフデータにおける経路及び全長であり、ローカル計算データは各サブグラフデータにおける最適な経路長さ、及び当該サブグラフを出入りするグラフノードを含む。計算のプロセスは、経路選択を継続的に最適化することであり、計算ノードは互いに協調してグラフノードを動的に割り当て、最適な条件下で最適なサブグラフ分割を取得し、その場合における最適解を求める。
【０１２２】
理解を容易にするために、以下は、１つの例示的な例で上記の実現プロセスを説明する。ブロックチェーンにおける各通貨は１つの完了済の単位計算タスクに対応し、各計算ノードがアルゴリズム駆動により完了する必要のある単位計算タスク、すなわち、負債プロデューサーを継続的に生成できることを理解し得る。異なる計算ノード間で通貨を使用してこれらのグラフノードを取引でき、このようなプロセスは、通常、１つの自己組織化ポリシーを含む。最も簡単な自己組織化ポリシーは自己資金調達であり、即ち、計算ノードが所有しているグラフノードが単位時間あたりに生成するタスクの量が周りの計算ノードの平均生成タスクの量を超えると、当該計算ノードは加速責任状態にあり、自己のグラフノードを「販売」することで自己資金調達を達成する必要があり、即ち、未完了の単位計算タスク(負債)と完了済の単位計算タスク(資産)のバランスをとるプロセスであり、余剰資産を持つ計算ノードは、より多くのグラフノードを「購入」することにより、計算能力を最大限に活用することができる。このように、各計算ノードの目的は、負債と資産のバランスを取ることである。計算ノードｋの資産ポートフォリオは、トリプルである
2021524100.tif 000031
からなることができ、計算ノードｋが所有するグラフノード、グラフノードに対応する資産（完了済の単位計算タスク）及び負債（未完了の単位計算タスク）をそれぞれ代表する。
【０１２３】
グラフノードの最終取引価格は、販売価格と購入価格の平均値に従って取引され、取引中、購入者は実際に、購入価格数のブロックチェーン通貨Ｃを販売者に送信し、ここでの通貨Ｃは、以上で言及されたグラフノードの資産及び負債と同じ単位を持っているが、通貨は資産及び負債とは異なる。ここでの通貨は、ブロックチェーンによって実際に登録され流通できる通貨であるが、上記言及された資産と負債は、アカウントにおける将来の償還可能な資産である。簡単には、計算ノードの負債比率が指定された値を超えない限り、各Ｃｉが会計を通じて実際の通貨Ｃに変換される可能性がある。会計のプロセスは、計算ノードが新しいブロックを追加することで、前のブロックから現在の時刻までの全ての取引情報（ここでは、ログ、グローバル計算パラメータ、ノード状態スレポートを含む）を新しいブロックに記録し、ブロックチェーンの最後に追加し、報酬として一定数の通貨Ｃを取得するプロセスである。この報酬の値は、計算ノードの資産から書き留められる。
【０１２４】
図９に示すように、一実施例において、グラフデータに基づくタスクスケジューリング装置９００を提供し、取得モジュール９０１、実行モジュール９０２、特定モジュール９０３及び交換モジュール９０４を含む。
取得モジュール９０１は、処理すべきグラフデータから分割したサブグラフデータを取得するために用いられる。
実行モジュール９０２は、取得モジュール９０１によって取得されたサブグラフデータにおけるグラフノードに対する単位計算タスクを実行するために用いられる。
取得モジュール９０１は、さらに、第１の量子化値を取得するために用いられ、前記第１の量子化値は、完了済の単位計算タスクに対応するデータをブロックチェーンデータに形成する際に、完了済の単位計算タスクに対応する量子化値である。
取得モジュール９０１は、さらに、第２の量子化値を取得するために用いられ、前記第２の量子化値は、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に、完了済の単位計算タスクに対応する量子化値である。
特定モジュール９０３は、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するために用いられる。
交換モジュール９０４は、取得モジュール９０１によって取得された第２の量子化値、及び特定モジュール９０３によって取得された第３の量子化値が平衡条件を満たさない場合に、前記計算ノードと他の計算ノードとの間で前記グラフノード及び前記第１の量子化値を交換する。
【０１２５】
一実施例において、取得モジュール９０１は、さらに、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、タスク情報に応じて、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取るために用いられる。実行モジュールは、さらに、サブグラフデータに応じて、サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するためのタスク実行可能ファイルを実行するために用いられる。
【０１２６】
一実施例において、取得モジュール９０１は、さらに、完了済の単位計算タスクに相応するグローバル計算データを新しいブロックに書き込み、新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成するために用いられる。
【０１２７】
一実施例において、取得モジュール９０１は、さらに、グローバル計算データを新しいブロックに書き込む前の履歴第２の量子化値を取得し、履歴第２の量子化値は、グローバル計算データを新しいブロックに書き込む前にブロックチェーンデータを形成せず且つ完了済の単位計算タスクに対応し、履歴第２の量子化値から第１の量子化値を減算して、第２の量子化値を取得するために用いられる。
【０１２８】
一実施例において、特定モジュール９０３は、さらに、ブロックチェーンネットワークから最新のグローバル計算データを取得し、完了済の単位計算タスクに相応するローカル計算データを取得し、サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定するために用いられる。
【０１２９】
一実施例において、取得モジュール９０１は、さらに、サブグラフデータの現在の第２の量子化値の第１の合計を取得し、サブグラフデータの現在の第３の量子化値の第２の合計を取得するために用いられる。特定モジュールは、さらに、第１の合計に対する第２の合計のコントラスト値を特定し、コントラスト値が指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定するために用いられる。
【０１３０】
一実施例において、特定モジュール９０３は、さらに、以下の式により、コントラスト値を計算するために用いられ、
2021524100.tif 000032
ただし、ａ及びｍは定数であり、ａ＞０、且つａ≠１、ｍ≧１であり、
2021524100.tif 000033
は第２の合計を表し、
2021524100.tif 000034
は第１の合計を表す。
【０１３１】
一実施例において、指定範囲の最小値μ(ｔ)  及び最大値λ(ｔ)は時間ｔとともに変化する線形減少関数であり、且つμ(ｔ)  ＜λ(ｔ)である。
【０１３２】
一実施例において、交換モジュール９０４は、さらに、コントラスト値が指定範囲の最小値よりも小さい場合、第１の量子化値を他の計算ノードのグラフノードと交換し、交換後のコントラスト値が指定範囲内にあり、コントラスト値が指定範囲の最大値よりも大きい場合、グラフノードを他の計算ノードの第１の量子化値と交換し、交換後のコントラスト値が指定範囲内にあるために用いられる。
【０１３３】
一実施例において、交換モジュール９０４は、さらに、計算ノード及び他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定し、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定し、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定し、第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定し、計算ノードと他の計算ノードとの間で、交換すべきグラフノード、及び特定された第１の量子化値を交換するために用いられる。
【０１３４】
図１０に示すように、一実施例において、交換モジュール９０４は、以下の式により、第１の推定量子化値を計算するための計算サブモジュール９０５をさらに含み、
2021524100.tif 000035
ただし、ｖｉは交換すべきグラフノードを表し、ｋは第１の計算ノードを表し、ｙ１（ｖｉ，ｋ）は第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、Ｃｉは交換すべきグラフノードの第２の量子化値を表し、
2021524100.tif 000036
は第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000037
は第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、α及びβはそれぞれシステムパラメータであり、ｅは自然対数の底である。
【０１３５】
一実施例において、交換モジュール９０４は、以下の式により、第２の推定量子化値を計算するための第２の計算サブモジュール９０６をさらに含み、
2021524100.tif 000038
ｖｉ交換すべきグラフノードを表し、ｌは第２の計算ノードを表し、ｙ２（ｖｉ，ｌ）は第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、
2021524100.tif 000039
は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの通信距離の合計を表す。
【０１３６】
一実施例において、第２の計算サブモジュール９０６は、以下の式により、通信距離を計算するさらに、ために用いられ、
2021524100.tif 000040
ただし、ｄｉｓｔ（ｉ，ｊ）は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの間の通信距離を表し、ｅ(ｉ,ｊ)∈Ｅはグラフノードｊとグラフノードｉとの間がエッジにより接続されることを表し、
2021524100.tif 000041
はグラフノードｊとグラフノードｉとの間にエッジがないことを表す。
【０１３７】
上記のグラフデータに基づくタスクスケジューリング装置は、処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれを取得することにより、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を指標し、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確で直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がないが、計算ノードが互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡を実現し、特定のサーバの単一障害点及びネットワーク輻輳問題を回避し、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採用すると、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【０１３８】
図１１は、一実施形態におけるコンピュータ機器の内部構成図を示す。当該コンピュータ機器は図１における計算ノード１２０が分布するコンピュータ機器であってもよい。図１１に示すように、当該コンピュータ機器はシステムバスにより接続されるプロセッサ、メモリ及びネットワークインターフェースを含む。なお、メモリは非揮発性記憶媒体及び内部メモリを含む。当該コンピュータ機器の非揮発性記憶媒体にはオペレーティングシステムを記憶しており、コンピュータプログラムをさらに記憶し得、当該コンピュータプログラムがプロセッサによって実行される場合に、グラフデータに基づくタスクスケジューリング方法をプロセッサに実現させることができる。当該内部メモリにはコンピュータプログラムも記憶しており、当該コンピュータプログラムがプロセッサによって実行される場合に、グラフデータに基づくタスクスケジューリング方法をプロセッサに実行させる。
【０１３９】
当業者であれば、図１１に示す構成は、本出願のスキームに関連する一部の構成のブロック図であり、本出願のスキームが適用されるコンピュータ機器の制限を構成せず、コンピュータ機器は、図に示されているものよりも多い、もしくは少ない構成要素を含む、又はいくつかの構成要素を組み合わせる、又は別の構成要素の配置を有してもよいことを理解し得る。
【０１４０】
一実施例において、本出願で提供されるグラフデータに基づくタスクスケジューリング装置はコンピュータプログラムの形式として実現されることができ、コンピュータプログラムは図１１に示すコンピュータ機器上で実行され得る。コンピュータ機器のメモリには当該グラフデータに基づくタスクスケジューリング装置を構成するそれぞれのプログラムモジュール、例えば、図９に示された取得モジュール、実行モジュール、特定モジュール及び交換モジュールを記憶することができる。それぞれのプログラムモジュールからなるコンピュータプログラムは、本明細書で説明された本出願の各実施例のグラフデータに基づくタスクスケジューリング方法におけるステップをプロセッサに実行させる。
【０１４１】
例えば、図１１に示すコンピュータ機器は、図９に示されたグラフデータに基づくタスクスケジューリング装置における取得モジュールによりステップ２０２、２０６及び２０８を実行することができる。コンピュータ機器は、モジュールを実行することでステップ２０４を実行することができる。コンピュータ機器は特定モジュールによりステップ２１０を実行することができる。コンピュータ機器は交換モジュールによりステップ２１２を実行することができ、実行の詳細について、上記のステップにおける説明を参照する。
【０１４２】
一実施例において、コンピュータ機器を提供し、メモリ及びプロセッサを含み、メモリにコンピュータプログラムを記憶しており、コンピュータプログラムがプロセッサによって実行される場合には、処理すべきグラフデータから分割したサブグラフデータを取得し、  サブグラフデータにおけるグラフノードに対する単位計算タスクを実行し、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に、完了済の単位計算タスクに対応する量子化値である第１の量子化値を取得し、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に、完了済の単位計算タスクに対応する量子化値である第２の量子化値を取得し、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定し、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、グラフノード及び第１の量子化値を他の計算ノードと交換するステップをプロセッサに実行させる
【０１４３】
一実施例において、コンピュータプログラムがプロセッサに、処理すべきグラフデータから分割したサブグラフデータを取得するステップを実行させる際に、以下のステップを実行でき、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、  タスク情報に応じて、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取ることを含んでおり、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行することは、サブグラフデータに応じて、サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するためのタスク実行可能ファイルを実行する。
【０１４４】
一実施例において、コンピュータプログラムがプロセッサに、第１の量子化値を取得するステップを実行させる際に、以下のステップを実行でき、完了済の単位計算タスクに相応するグローバル計算データを新しいブロックに書き込み、  新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成する。
【０１４５】
一実施例において、コンピュータプログラムがプロセッサに、第２の量子化値を取得するステップを実行させる際に、以下のステップを実行でき、グローバル計算データを新しいブロックに書き込む前の履歴第２の量子化値を取得し、履歴第２の量子化値は、グローバル計算データを新しいブロックに書き込む前にブロックチェーンデータを形成せず且つ完了済の単位計算タスクに対応し、履歴第２の量子化値から第１の量子化値を減算して、第２の量子化値を取得する。
【０１４６】
一実施例において、コンピュータプログラムがプロセッサに、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するステップを実行させる際に、以下のステップを実行でき、ブロックチェーンネットワークから最新のグローバル計算データを取得し、完了済の単位計算タスクに相応するローカル計算データを取得し、  サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定する。
【０１４７】
一実施例において、コンピュータプログラムはプロセッサに以下のステップを実行させ、サブグラフデータの現在の第２の量子化値の第１の合計を取得し、サブグラフデータの現在の第３の量子化値の第２の合計を取得し、  第１の合計に対する第２の合計のコントラスト値を特定し、  コントラスト値が指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定する。
【０１４８】
一実施例において、コンピュータプログラムがプロセッサに、第１の合計に対する第２の合計のコントラスト値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、コントラスト値を計算し、
2021524100.tif 000042
ａ及びｍは定数であり、ａ＞０、ａ≠１、ｍ≧１であり、
2021524100.tif 000043
は第２の合計を表し、
2021524100.tif 000044
は第１の合計を表す。
【０１４９】
一実施例において、指定範囲の最小値μ(ｔ)  及び最大値λ(ｔ)は時間ｔとともに変化する線形減少関数であり、且つμ(ｔ)  ＜λ(ｔ)である。
【０１５０】
一実施例において、コンピュータプログラムがプロセッサに、他の計算ノードとのグラフノード及び第１の量子化値の交換を行うステップを実行させる際に、以下のステップを実行でき、コントラスト値が指定範囲の最小値よりも小さい場合、第１の量子化値を他の計算ノードのグラフノードと交換し、交換後のコントラスト値が指定範囲内にあり、  コントラスト値が指定範囲の最大値よりも大きい場合、グラフノードを他の計算ノードの第１の量子化値と交換し、交換後のコントラスト値が指定範囲内にある。
【０１５１】
一実施例において、コンピュータプログラムがプロセッサに、グラフノード及び第１の量子化値を他の計算ノードと交換するステップを実行させる際には、以下のステップを実行でき、計算ノード及び他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定し、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定し、  第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定し、  第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定し、計算ノードと他の計算ノードとの間で、交換すべきグラフノード、及び特定された第１の量子化値を交換する。
【０１５２】
一実施例において、コンピュータプログラムがプロセッサに、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、第１の推定量子化値を計算し、
2021524100.tif 000045
ただし、ｖｉは交換すべきグラフノードを表し、ｋは第１の計算ノードを表し、ｙ１（ｖｉ，ｋ）は第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を表し、Ｄｉは示交換すべきグラフノードの第３の量子化値を表し、Ｃｉは交換すべきグラフノードの第２の量子化値を表し、
2021524100.tif 000046
は第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000047
は第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、α及びβはそれぞれシステムパラメータであり、ｅは自然対数の底である。
【０１５３】
一実施例において、コンピュータプログラムがプロセッサに、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、第２の推定量子化値を計算し、
2021524100.tif 000048
ただし、ｖｉは交換すべきグラフノードを表し、ｌは第２の計算ノードを表し、ｙ２（ｖｉ，ｌ）は第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し
2021524100.tif 000049
は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの通信距離の合計を表す。
【０１５４】
一実施例において、コンピュータプログラムがプロセッサに、交換すべきグラフノードを引き換える第２の計算ノードにおけるグラフノードと、交換すべきグラフノードとの通信距離の合計を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、通信距離を計算し、
2021524100.tif 000050
ただし、ｄｉｓｔ（ｉ，ｊ）は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの間の通信距離を表し、
2021524100.tif 000051
はグラフノードｊとグラフノードｉとの間がエッジにより接続されることを表し、
2021524100.tif 000052
はグラフノードｊとグラフノードｉとの間にエッジがないことを表す。
【０１５５】
上記のコンピュータ機器は、処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれを取得することにより、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を指標し、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確で直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がないが、計算ノードが互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡を実現し、特定のサーバの単一障害点及びネットワーク輻輳問題を回避し、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採用すると、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【０１５６】
コンピュータ読み取り可能な記憶媒体であって、コンピュータプログラムを記憶しており、当該コンピュータプログラムがプロセッサによって実行される場合には、処理すべきグラフデータから分割したサブグラフデータを取得し、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行し、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成される際に、完了済の単位計算タスクに対応する量子化値である第１の量子化値を取得し、完了済の単位計算タスクに対応するデータがブロックチェーンデータに形成されない際に、完了済の単位計算タスクに対応する量子化値である第２の量子化値を取得し、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定し、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、グラフノード及び第１の量子化値を他の計算ノードと交換するステップを実現する。
【０１５７】
一実施例において、コンピュータプログラムがプロセッサに、処理すべきグラフデータから分割したサブグラフデータを取得するステップを実行させる際に、以下のステップを実行でき、ブロックチェーンネットワークでブロードキャストされたグラフデータに対応するタスク情報を取得し、タスク情報に応じて、タスク実行可能ファイル、及びグラフデータから分割したサブグラフデータを読み取り、コンピュータプログラムがプロセッサに、サブグラフデータにおけるグラフノードに対する単位計算タスクを実行するステップを実行させる際に、以下のステップを実行でき、サブグラフデータに応じて、サブグラフデータにおけるグラフノードに対する単位計算タスクを指示するためのタスク実行可能ファイルを実行する。
【０１５８】
一実施例において、コンピュータプログラムがプロセッサに、第１の量子化値を取得するステップを実行させる際に、以下のステップを実行でき、完了済の単位計算タスクに相応するグローバル計算データを新しいブロックに書き込み、新しいブロックがブロックチェーンネットワークによって検証されると、新しいブロックをブロックチェーンネットワークに追加してブロックチェーンデータを形成し、書き込まれたグローバル計算データに相応する単位計算タスクに対応する第１の量子化値を生成する。
【０１５９】
一実施例において、コンピュータプログラムがプロセッサに、第２の量子化値を取得するステップを実行させる際に、以下のステップを実行でき、グローバル計算データを新しいブロックに書き込む前の履歴第２の量子化値を取得し、履歴第２の量子化値は、グローバル計算データを新しいブロックに書き込む前にブロックチェーンデータを形成せず且つ完了済の単位計算タスクに対応し、履歴第２の量子化値から第１の量子化値を減算して、第２の量子化値を取得する。
【０１６０】
一実施例において、コンピュータプログラムがプロセッサに、サブグラフデータにおける未完了の単位計算タスクに対応する第３の量子化値を特定するステップを実行させる際に、以下のステップを実行でき、ブロックチェーンネットワークから最新のグローバル計算データを取得し、完了済の単位計算タスクに相応するローカル計算データを取得し、据サブグラフデータ、完了済の単位計算タスクの数、グローバル計算データ及びローカル計算データに応じて、第３の量子化値を特定する。
【０１６１】
一実施例において、コンピュータプログラムはさらに、プロセッサに以下のステップを実行させ、サブグラフデータの現在の第２の量子化値の第１の合計を取得し、サブグラフデータの現在の第３の量子化値の第２の合計を取得し、第１の合計に対する第２の合計のコントラスト値を特定し、コントラスト値が指定範囲外であると、第２の量子化値及び第３の量子化値が平衡条件を満たさないと特定する。
【０１６２】
一実施例において、コンピュータプログラムがプロセッサに、第１の合計に対する第２の合計のコントラスト値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、コントラスト値を計算し、
2021524100.tif 000053
ただし、ａ及びｍは定数であり、ａ＞０  、ａ≠１、ｍ≧１であり、
2021524100.tif 000054
は第２の合計を表し、
2021524100.tif 000055
は第１の合計を表す。
【０１６３】
一実施例において、指定範囲の最小値μ(ｔ)  及び最大値λ(ｔ)は時間ｔとともに変化する線形減少関数であり、且つμ(ｔ)  ＜λ(ｔ)である。
【０１６４】
一実施例において、コンピュータプログラムがプロセッサに、グラフノード及び第１の量子化値を他の計算ノードと交換するステップを実行させる際に、以下のステップを実行でき、コントラスト値が指定範囲の最小値よりも小さい場合、第１の量子化値を他の計算ノードのグラフノードと交換し、交換後のコントラスト値が指定範囲内にあり、コントラスト値が指定範囲の最大値よりも大きい場合、グラフノードを他の計算ノードの第１の量子化値と交換し、交換後のコントラスト値が指定範囲内にある。
【０１６５】
一実施例において、コンピュータプログラムがプロセッサに、他の計算ノードとのグラフノード及び第１の量子化値の交換を行うステップを実行させる際に、以下のステップを実行でき、計算ノード及び他の計算ノードのうち、交換すべきグラフノードを提供する第１の計算ノード、及び交換すべきグラフノードを引き換える第２の計算ノードを特定し、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定し、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定し、  第１の推定量子化値及び第２の推定量子化値に応じて、交換すべきグラフノードと交換するための第１の量子化値を特定し、計算ノードと他の計算ノードとの間で、交換すべきグラフノード、及び特定された第１の量子化値を交換する。
【０１６６】
一実施例において、コンピュータプログラムがプロセッサに、第１の計算ノードによる交換すべきグラフノードの第１の推定量子化値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、第１の推定量子化値を計算し、
2021524100.tif 000056
ただし、ｖｉは交換すべきグラフノードを表し、ｋは第１の計算ノードを表し、ｙ１（ｖｉ，ｋ）は第１の計算ノードによる前記交換すべきグラフノードの第１の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、Ｃｉは交換すべきグラフノードの第２の量子化値を表し、
2021524100.tif 000057
は第１の計算ノードｋにおけるグラフノードの平均第３の量子化値を表し、
2021524100.tif 000058
は第１の計算ノードｋにおけるグラフノードの平均第２の量子化値を表し、α及びβはそれぞれシステムパラメータであり、ｅは自然対数の底である。
【０１６７】
一実施例において、コンピュータプログラムがプロセッサに、第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、第２の推定量子化値を計算し、
2021524100.tif 000059
ただし、  ｖｉは前記交換すべきグラフノードを表し、ｌは第２の計算ノードを表し、ｙ２（ｖｉ，ｌ）は第２の計算ノードによる交換すべきグラフノードの第２の推定量子化値を表し、Ｄｉは交換すべきグラフノードの第３の量子化値を表し、
2021524100.tif 000060
は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの通信距離の合計を表す。
【０１６８】
一実施例において、コンピュータプログラムがプロセッサに、交換すべきグラフノードを引き換える第２の計算ノードにおけるグラフノードと交換すべきグラフノードとの通信距離の合計を特定するステップを実行させる際に、以下のステップを実行でき、以下の式により、通信距離を計算し、
2021524100.tif 000061
ただし、ｄｉｓｔ（ｉ，ｊ）は第２の計算ノードｌにおけるグラフノードｊと交換すべきグラフノードｉとの間の通信距離を表し、
2021524100.tif 000062
はグラフノードｊとグラフノードｉとの間がエッジにより接続されることを表し、
2021524100.tif 000063
はグラフノードｊとグラフノードｉとの間にエッジがないことを表す。
【０１６９】
上記のコンピュータ読み取り可能な記憶媒体は、処理すべきグラフデータを複数のサブグラフデータに分割してから、当該複数のサブグラフデータに対して分散処理を行うことにより、グラフデータの処理効率を大幅に向上させることができる。第１の量子化値、第２の量子化値及び第３の量子化値をそれぞれを取得することにより、第２の量子化値及び第３の量子化値が平衡条件を満たさない場合、計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換する。なお、第１の量子化値及び第２の量子化値は計算ノードの計算能力を指標し、第３の量子化値は計算ノードの負荷状態を指標し、このように、計算ノードの計算能力及び負荷状態を単位計算タスクに相応する量子化値で量子化して表すことができ、正確で直感である。計算ノードと他の計算ノードとの間でグラフノード及び第１の量子化値を交換することにより、第２の量子化値及び第３の量子化値が平衡条件を満たすことを保持し、このように、特定のサーバ又はノードに依存してタスクを割り当てる必要がないが、計算ノードが互いに協調してグラフノードを割り当て、割り当てを動的に調整し、自己組織化された負荷平衡を実現し、特定のサーバの単一障害点及びネットワーク輻輳問題を回避し、タスクのスケジューリング効率を大幅に向上させる。そして、このような自己組織化された動的タスクスケジューリング方法を採用すると、より大規模のクラスタの計算タスクのスケジューリングに適合させ、計算ノードの数を動的に増減しても既存の計算タスクに影響を与えず、高いスケーラビリティを有することができる。
【０１７０】
当業者は、上記の実施例の全て又は一部のステップを実現することがハードウェアで完了されてもよいし、プログラムで関連するハードウェアを指令して完了されてもよく、前記プログラムがコンピュータ読み取り可能な記憶媒体に記憶されてもよく、上記で言及された記憶媒体は読み取り専用メモリ（ＲＯＭ：Ｒｅａｄ−Ｏｎｌｙ    Ｍｅｍｏｒｙ）、磁気ディスク又は光ディスクなどであってもよい。
【０１７１】
上述は、本願の好ましい実施例であり、本発明の限定を意図しない。本願の精神及び原則内で、行われるいかなる修正、同等置換、改善等は本願の保護範囲内に含まれるべきである。
【図１】
2021524100.tif 000076
【図２】
2021524100.tif 000077
【図３】
2021524100.tif 000078
【図４】
2021524100.tif 000079
【図５】
2021524100.tif 000080
【図６】
2021524100.tif 000081
【図７】
2021524100.tif 000082
【図８】
2021524100.tif 000083
【図９】
2021524100.tif 000084
【図１０】
2021524100.tif 000085
【図１１】
2021524100.tif 000086
【国際調査報告】
2021524100.tif 000087
2021524100.tif 000088
2021524100.tif 000089
2021524100.tif 000090