(57)【特許請求の範囲】
【請求項１】
管理ノードと計算ノードとを含むデータ処理システムであって、前記計算ノードは、第1の処理タスクを処理する第1のクラスの計算ノードを含み、
前記管理ノードは、FCxを含むとともに前記第1のクラスの計算ノード内にある少なくとも2つの計算ノードに、第1の処理タスクを割り当てるように構成され、前記FCxは前記少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、
前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた前記第1の処理タスクを同時に処理し、
前記計算ノードFCxは、前記管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得し、
前記データブロックMxおよび前記データブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果V’xを取得するように構成され、前記データブロックMxは、m行n列のデータを含む行列であり、前記データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上であり、前記第1の中間結果V’xは、m次元データを含むベクトルであり、前記第1の中間結果V’xは、要素
【数１】
0006508661.tif 000090
を有し、iは変数であり、iの値は1からmの範囲であり、
【数２】
0006508661.tif 000091
であり、
【数３】
0006508661.tif 000092
は
【数４】
0006508661.tif 000093
に従って取得され、mi,jは、前記データブロックMx内の要素であり、vjは、前記データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲であり、
前記管理ノードは、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された第1の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、データ処理システム。
【請求項２】
前記計算ノードは、第2の処理タスクを処理する第2のクラスの計算ノードをさらに含み、前記管理ノードは、
前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果に従って、SCyを含むとともに前記第2のクラスの計算ノード内にある少なくとも1つの計算ノードに、第2の処理タスクを割り当てるようにさらに構成され、前記SCyは前記少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数であり、
前記計算ノードSCyは、
第2の処理タスクに従って、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果を取得し、
前記SCyによって取得された前記第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するように構成され、前記SCyによって取得された前記第1の中間結果は、前記処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果であり、前記第2の中間結果V’’yは、m次元データを含むベクトルであり、
前記管理ノードは、
前記第2のクラスの計算ノード内の前記少なくとも1つの計算ノードによって取得された第2の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、請求項1に記載のデータ処理システム。
【請求項３】
前記データセットは、データブロックV2xをさらに含み、前記データブロックV2xは、m次元データを含むベクトルであり、前記管理ノードは、
前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードによって取得された前記第2の中間結果に従って、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードに、第3の処理タスクを割り当てるようにさらに構成され、
前記計算ノードSCyは、
前記第3の処理タスクに従って、前記データセット内の前記データブロックV2xを取得し、
前記SCyによって取得された前記第2の中間結果V’’yおよび前記データブロックV2xに対して、割り当てassign操作を実行して、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、請求項2に記載のデータ処理システム。
【請求項４】
m=nであり、前記データブロックV1xと前記データブロックV2xは同じデータブロックである、請求項3に記載のデータ処理システム。
【請求項５】
前記第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、前記第2のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた第2の処理タスクを同時に処理する、請求項2乃至4のいずれか1項に記載のデータ処理システム。
【請求項６】
前記管理ノード、前記第1のクラスの計算ノードおよび前記第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置（CPU）を含む、請求項2乃至5のいずれか1項に記載のデータ処理システム。
【請求項７】
管理ノードと計算ノードとを含むデータ処理システムであって、前記計算ノードは、第1の処理タスクを処理する第1のクラスの計算ノードを含み、
前記管理ノードは、FCxを含むとともに前記第1のクラスの計算ノード内にある少なくとも2つの計算ノードに、第1の処理タスクを割り当てるように構成され、前記FCxは前記少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、
前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた前記第1の処理タスクを同時に処理し、
前記計算ノードFCxは、前記管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得し、
前記データブロックM1xおよび前記データブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果M’xを取得するように構成され、前記データブロックM1xは、m行n列のデータを含む行列であり、前記データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上であり、前記第1の中間結果M’xは、m行p列のデータを含む行列であり、前記第1の中間結果M’xは、要素
【数５】
0006508661.tif 000094
を有し、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【数６】
0006508661.tif 000095
であり、
【数７】
0006508661.tif 000096
は
【数８】
0006508661.tif 000097
に従って取得され、m1[i,k]は、前記データブロックM1xの第i行第k列の要素であり、m2[k,j]は、前記データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲であり、
前記管理ノードは、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された第1の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、データ処理システム。
【請求項８】
前記計算ノードは、第2の処理タスクを処理する第2のクラスの計算ノードをさらに含み、前記管理ノードは、
前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果に従って、SCyを含むとともに前記第2のクラスの計算ノード内にある少なくとも1つの計算ノードに、第2の処理タスクを割り当てるようにさらに構成され、前記SCyは前記少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数であり、
前記計算ノードSCyは、
第2の処理タスクに従って、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果を取得し、
前記SCyによって取得された前記第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するように構成され、前記SCyによって取得された前記第1の中間結果は、前記処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果であり、前記第2の中間結果M’’yは、m行p列のデータを含む行列であり、
前記管理ノードは、
前記第2のクラスの計算ノード内の前記少なくとも1つの計算ノードによって取得された第2の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、請求項7に記載のデータ処理システム。
【請求項９】
前記データセットは、データブロックM3xをさらに含み、前記データブロックM3xは、m行p列のデータを含む行列であり、前記管理ノードは、
前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードによって取得された前記第2の中間結果に従って、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードに、第3の処理タスクを割り当てるようにさらに構成され、
前記計算ノードSCyは、
前記第3の処理タスクに従って、前記データセット内の前記データブロックM3xを取得し、
前記SCyによって取得された前記第2の中間結果M’’yおよび前記データブロックM3xに対して、割り当てassign操作を実行して、前記処理されるべきデータセットのための処理結果を取得するようにさらに構成される、請求項8に記載のデータ処理システム。
【請求項１０】
n=mであり、前記データブロックM2xと前記データブロックM3xは同じデータブロックである、請求項9に記載のデータ処理システム。
【請求項１１】
n=pであり、前記データブロックM1xと前記データブロックM3xは同じデータブロックである、請求項9に記載のデータ処理システム。
【請求項１２】
前記第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、前記第2のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた第2の処理タスクを同時に処理する、請求項8乃至11のいずれか1項に記載のデータ処理システム。
【請求項１３】
前記管理ノード、前記第1のクラスの計算ノードおよび前記第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUを含む、請求項8乃至12のいずれか1項に記載のデータ処理システム。
【請求項１４】
計算ノードであって、
データ処理システム内の管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュールと、
前記管理ノードによって割り当てられ、前記受信モジュールによって受信された前記第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するように構成される取得モジュールであって、前記データブロックMxは、m行n列のデータを含む行列であり、前記データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である、取得モジュールと、
前記データブロックMxおよび前記データブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果V’xを取得するように構成される処理モジュールであって、前記第1の中間結果V’xは、m次元データを含むベクトルであり、前記第1の中間結果V’xは、要素
【数９】
0006508661.tif 000098
を有し、iは変数であり、iの値は1からmの範囲であり、
【数１０】
0006508661.tif 000099
であり、
【数１１】
0006508661.tif 000100
は
【数１２】
0006508661.tif 000101
に従って取得され、mi,jは、前記データブロックMx内の要素であり、vjは、前記データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である、処理モジュールとを含む計算ノード。
【請求項１５】
前記計算ノードは、物理マシン、仮想マシンまたは中央処理装置CPUである、請求項14に記載の計算ノード。
【請求項１６】
計算ノードであって、
データ処理システム内の管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュールであって、前記データ処理システムは、前記計算ノードおよび前記管理ノードを含む、受信モジュールと、
前記管理ノードによって割り当てられ、前記受信モジュールによって受信された前記第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するように構成される取得モジュールであって、前記データブロックM1xは、m行n列のデータを含む行列であり、前記データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である、取得モジュールと、
前記データブロックM1xおよび前記データブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果M’xを取得するように構成される処理モジュールであって、前記第1の中間結果M’xは、m行p列のデータを含む行列であり、前記第1の中間結果M’xは、要素
【数１３】
0006508661.tif 000102
を有し、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【数１４】
0006508661.tif 000103
であり、
【数１５】
0006508661.tif 000104
は
【数１６】
0006508661.tif 000105
に従って取得され、m1[i,k]は、前記データブロックM1xの第i行第k列の要素であり、m2[k,j]は、前記データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である、処理モジュールとを含む計算ノード。
【請求項１７】
前記計算ノードは、物理マシン、仮想マシンまたは中央処理装置CPUである、請求項16に記載の計算ノード。
【請求項１８】
データ処理方法であって、前記方法はデータ処理システムに適用され、前記データ処理システムは、管理ノードと計算ノードとを含み、前記計算ノードは、第1の処理タスクを処理する第1のクラスの計算ノードを含み、前記方法は、
前記管理ノードによって、FCxを含むとともに前記第1のクラスの計算ノード内にある少なくとも2つの計算ノードに、第1の処理タスクを割り当てるステップであって、前記FCxは前記少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた前記第1の処理タスクを同時に処理する、ステップと、
前記計算ノードFCxによって、前記管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するステップであって、前記データブロックMxは、m行n列のデータを含む行列であり、前記データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である、ステップと、
前記計算ノードFCxによって、前記データブロックMxおよび前記データブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果V’xを取得するステップであって、前記第1の中間結果V’xは、m次元データを含むベクトルであり、前記第1の中間結果V’xは、要素
【数１７】
0006508661.tif 000106
を有し、iは変数であり、iの値は1からmの範囲であり、
【数１８】
0006508661.tif 000107
であり、
【数１９】
0006508661.tif 000108
は
【数２０】
0006508661.tif 000109
に従って取得され、mi,jは、前記データブロックMx内の要素であり、vjは、前記データブロックV1x内の要素であり、j は変数であり、jの値は1からnの範囲である、ステップと、
前記管理ノードによって、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された第1の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するステップとを含む方法。
【請求項１９】
前記計算ノードは、第2の処理タスクを処理する第2のクラスの計算ノードをさらに含み、前記方法は、
前記管理ノードによって、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果に従って、SCyを含むとともに前記第2のクラスの計算ノード内にある少なくとも1つの計算ノードに、第2の処理タスクを割り当てるステップであって、前記SCyは前記少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
前記計算ノードSCyによって、前記第2の処理タスクに従って、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果を取得するステップであって、前記SCyによって取得された前記第1の中間結果は、前記処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果である、ステップと、
前記計算ノードSCyによって、前記SCyによって取得された前記第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するステップであって、前記第2の中間結果V’’yは、m次元データを含むベクトルである、ステップと、
前記管理ノードによって、前記第2のクラスの計算ノード内の前記少なくとも1つの計算ノードによって取得された第2の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するステップとをさらに含む、請求項18に記載の方法。
【請求項２０】
前記データセットは、データブロックV2xをさらに含み、前記データブロックV2xは、m次元データを含むベクトルであり、前記方法は、
前記管理ノードによって、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードによって取得された前記第2の中間結果に従って、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードに、第3の処理タスクを割り当てるステップと、
前記計算ノードSCyによって、前記第3の処理タスクに従って、前記データセット内の前記データブロックV2xを取得するステップと、
前記計算ノードSCyによって、前記SCyによって取得された前記第2の中間結果V’’yおよび前記データブロックV2xに対して、割り当てassign操作を実行して、前記処理されるべきデータセットのための処理結果を取得するステップとをさらに含む、請求項19に記載の方法。
【請求項２１】
m=nであり、前記データブロックV1xと前記データブロックV2xは同じデータブロックである、請求項20に記載の方法。
【請求項２２】
前記第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、前記第2のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた第2の処理タスクを同時に処理する、請求項19乃至21のいずれか1項に記載の方法。
【請求項２３】
前記管理ノード、前記第1のクラスの計算ノードおよび前記第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUを含む、請求項19乃至22のいずれか1項に記載の方法。
【請求項２４】
データ処理方法であって、前記方法はデータ処理システムに適用され、前記データ処理システムは、管理ノードと計算ノードとを含み、前記計算ノードは、第1の処理タスクを処理する第1のクラスの計算ノードを含み、前記方法は、
前記管理ノードによって、FCxを含むとともに前記第1のクラスの計算ノード内にある少なくとも2つの計算ノードに、第1の処理タスクを割り当てるステップであって、前記FCxは前記少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた前記第1の処理タスクを同時に処理する、ステップと、
前記計算ノードFCxによって、前記管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するステップであって、前記データブロックM1xは、m行n列のデータを含む行列であり、前記データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である、ステップと、
前記計算ノードFCxによって、前記データブロックM1xおよび前記データブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を交替に実行して、第1の中間結果M’xを取得するステップであって、前記第1の中間結果M’xは、m行p列のデータを含む行列であり、前記第1の中間結果M’xは、要素
【数２１】
0006508661.tif 000110
を有し、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【数２２】
0006508661.tif 000111
であり、
【数２３】
0006508661.tif 000112
は
【数２４】
0006508661.tif 000113
に従って取得され、m1[i,k]は、前記データブロックM1xの第i行第k列の要素であり、m2[k,j]は、前記データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である、ステップと、
前記管理ノードによって、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された第1の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するステップとを含む方法。
【請求項２５】
前記計算ノードは、第2の処理タスクを処理する第2のクラスの計算ノードをさらに含み、前記方法は、
前記管理ノードによって、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果に従って、SCyを含むとともに前記第2のクラスの計算ノード内にある少なくとも1つの計算ノードに、第2の処理タスクを割り当てるステップであって、前記SCyは前記少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
前記計算ノードSCyによって、前記第2の処理タスクに従って、前記第1のクラスの計算ノード内の前記少なくとも2つの計算ノードによって取得された前記第1の中間結果を取得するステップであって、前記SCyによって取得された前記第1の中間結果は、前記処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果である、ステップと、
前記計算ノードSCyによって、前記SCyによって取得された前記第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するステップであって、前記第2の中間結果M’’yは、m行p列のデータを含む行列である、ステップと、
前記管理ノードによって、前記第2のクラスの計算ノード内の前記少なくとも1つの計算ノードによって取得された第2の中間結果に従って、前記処理されるべきデータセットのための処理結果を取得するステップとをさらに含む、請求項24に記載の方法。
【請求項２６】
前記データセットは、データブロックM3xをさらに含み、前記データブロックM3xは、m行p列のデータを含む行列であり、前記方法は、
前記管理ノードによって、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードによって取得された前記第2の中間結果に従って、前記SCyを含むとともに前記第2のクラスの計算ノード内にある前記少なくとも1つの計算ノードに、第3の処理タスクを割り当てるステップと、
前記計算ノードSCyによって、前記第3の処理タスクに従って、前記データセット内の前記データブロックM3xを取得するステップと、
前記計算ノードSCyによって、前記SCyによって取得された前記第2の中間結果M’’yおよび前記データブロックM3xに対して、割り当てassign操作を実行して、前記処理されるべきデータセットのための処理結果を取得するステップとをさらに含む、請求項25に記載の方法。
【請求項２７】
n=mであり、前記データブロックM2xと前記データブロックM3xは同じデータブロックである、請求項26に記載の方法。
【請求項２８】
n=pであり、前記データブロックM1xと前記データブロックM3xは同じデータブロックである、請求項26に記載の方法。
【請求項２９】
前記第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、前記第2のクラスの計算ノード内の前記少なくとも2つの計算ノードは、前記管理ノードによって割り当てられた第2の処理タスクを同時に処理する、請求項25乃至28のいずれか1項に記載の方法。
【請求項３０】
前記管理ノード、前記第1のクラスの計算ノードおよび前記第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUを含む、請求項25乃至29のいずれか1項に記載の方法。
【請求項３１】
1つまたは複数のコンピュータ実行可能命令を含むコンピュータ可読媒体であって、前記1つまたは複数のコンピュータ実行可能命令は、コンピュータシステムの1つまたは複数のプロセッサ上で実行されるとき、前記コンピュータシステムに、請求項18乃至23のいずれか1項に記載の前記方法を実行させる、コンピュータ可読媒体。
【請求項３２】
1つまたは複数のコンピュータ実行可能命令を含むコンピュータ可読媒体であって、前記1つまたは複数のコンピュータ実行可能命令は、コンピュータシステムの1つまたは複数のプロセッサ上で実行されるとき、前記コンピュータシステムに、請求項24乃至30のいずれか1項に記載の前記方法を実行させる、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータ技術の分野に関し、詳細には、図形演算の分野におけるデータ処理システム、計算ノードおよびデータ処理方法に関する。
【背景技術】
【０００２】
情報通信技術（Information and Communication Technology, ICT）がますます発展するにつれて、インターネットで生成されるデータは爆発的に増加した。データに対してデータマイニングおよび機械学習を行うことによって、大量の貴重な情報が取得されることができる。データマイニングおよび機械学習の研究対象は、通常、対象の集合および対象間の関係（例えば、ソーシャルネットワーク）である。全ての前述の研究対象は、数学的なグラフ（Graph）として表現されることができる。グラフは、対象間の関係を説明するために使用される。直感的に、グラフはいくつかの小さな点および点をつなぐ線を含んでよい。点は、グラフの頂点（Vertex）と呼ばれる。点をつなぐ線は、辺（Edge）と呼ばれる。
【０００３】
従って、データマイニングおよび機械学習のアルゴリズムは、グラフに対する操作、すなわち、グラフ計算に転換されることができる。グラフが操作されることができることを保証するために、グラフを表すためにデータ構造が選択される必要がある。現在、主に、隣接テーブルと隣接行列の2つのグラフ表現がある。隣接テーブルでは、頂点を表すために対象が使用され、辺を表すためにポインタまたは参照が使用される。このデータ構造は、グラフに対する同時処理に不利である。隣接行列は、本明細書では行列と略して書かれ、頂点間の隣接関係を記憶する2次元行列である。グラフは、このデータ構造を使用することによって、良好に同時に処理されることができる。加えて、データを記憶するために行列が使用されるとき、記憶されるデータ量は比較的小さい。
【０００４】
グラフ計算における行列計算は、理論的に、行列-ベクトル乗算操作および行列-行列乗算操作を含んでよい。既存の行列-ベクトル累乗操作、例えば、一般化された反復行列-ベクトル乗算（Generalized Iterated Matrix-Vector multiplication, GIMV）は、行列の行の要素およびベクトルの要素に対して対結合操作を行い、行の要素およびベクトルの要素に対する全ての対結合操作が完了した後、対結合操作の結果に対して全結合操作を実行することである。結果として、行列のサイズを持つ中間メモリ空間が、計算プロセスにおいて占有される必要があり、システムハードウェアデバイスに対する要件がより高くなる。加えて、行列-ベクトル乗算が分散環境において使用されるとき、システムは大量のデータを伝送する必要があり、結果として、計算のために多くの時間が費やされる。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の実施形態は、データ処理システム、計算ノードおよびデータ処理方法を提供し、これらは、データ処理中により小さいメモリ空間が占有されることを保証することができ、且つ、計算時間を低減することができる。
【０００６】
第1の態様によると、本発明の実施形態はデータ処理システムを提供し、ここで、データ処理システムは、管理ノードと第1のクラスの計算ノードとを含み、ここで、
管理ノードは、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、
第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理し、
計算ノードFCxは、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得し、
データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するように構成され、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上であり、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【０００７】
【数１】
0006508661.tif 000002
【０００８】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０００９】
【数２】
0006508661.tif 000003
【００１０】
であり、
【００１１】
【数３】
0006508661.tif 000004
【００１２】
は
【００１３】
【数４】
0006508661.tif 000005
【００１４】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲であり、
管理ノードは、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【００１５】
第1の態様を参照すると、第1の態様の第1の可能な実施方式では、データ処理システムは、第2のクラスの計算ノードをさらに含み、管理ノードは、
第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成され、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数であり、
計算ノードSCyは、
第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得し、
SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するように構成され、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果であり、ここで、第2の中間結果V’’yは、m次元データを含むベクトルであり、
管理ノードは、
第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【００１６】
第2の態様によると、本発明の実施形態は別のデータ処理システムを提供し、ここで、データ処理システムは、管理ノードと第1のクラスの計算ノードとを含み、ここで、
管理ノードは、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、
第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理し、
計算ノードFCxは、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得し、
データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するように構成され、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上であり、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【００１７】
【数５】
0006508661.tif 000006
【００１８】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【００１９】
【数６】
0006508661.tif 000007
【００２０】
であり、
【００２１】
【数７】
0006508661.tif 000008
【００２２】
は
【００２３】
【数８】
0006508661.tif 000009
【００２４】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲であり、
管理ノードは、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【００２５】
第2の態様を参照すると、第2の態様の第1の可能な実施方式では、データ処理システムは、第2のクラスの計算ノードをさらに含み、管理ノードは、
第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成され、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数であり、
計算ノードSCyは、
第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得し、
SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するように構成され、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果であり、ここで、第2の中間結果M’’yは、m行p列のデータを含む行列であり、
管理ノードは、
第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【００２６】
第3の態様によると、本発明の実施形態は計算ノードを提供し、計算ノードは、
データ処理システム内の管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュールであって、ここで、データ処理システムは、計算ノードおよび管理ノードを含む、受信モジュールと、
管理ノードによって割り当てられ、受信モジュールによって受信された第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するように構成される取得モジュールであって、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である、取得モジュールと、
データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するように構成される処理モジュールであって、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【００２７】
【数９】
0006508661.tif 000010
【００２８】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【００２９】
【数１０】
0006508661.tif 000011
【００３０】
であり、
【００３１】
【数１１】
0006508661.tif 000012
【００３２】
は
【００３３】
【数１２】
0006508661.tif 000013
【００３４】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である、処理モジュールとを含む。
【００３５】
第3の態様を参照すると、第3の態様の第1の可能な実施方式では、計算ノードは、物理マシン、仮想マシンまたは中央処理装置CPUである。
【００３６】
第4の態様によると、本発明の実施形態は別の計算ノードを提供し、別の計算ノードは、
データ処理システム内の管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュールであって、ここで、データ処理システムは、計算ノードおよび管理ノードを含む、受信モジュールと、
管理ノードによって割り当てられ、受信モジュールによって受信された第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するように構成される取得モジュールであって、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である、取得モジュールと、
データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するように構成される処理モジュールであって、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【００３７】
【数１３】
0006508661.tif 000014
【００３８】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【００３９】
【数１４】
0006508661.tif 000015
【００４０】
であり、
【００４１】
【数１５】
0006508661.tif 000016
【００４２】
は
【００４３】
【数１６】
0006508661.tif 000017
【００４４】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である、処理モジュールとを含む。
【００４５】
第5の態様によると、本発明の実施形態はデータ処理方法を提供し、ここで、方法はデータ処理システムに適用され、データ処理システムは、管理ノードと第1のクラスの計算ノードとを含み、方法は、
管理ノードによって、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当てるステップであって、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理する、ステップと、
計算ノードFCxによって、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するステップであって、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である、ステップと、
計算ノードFCxによって、データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するステップであって、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【００４６】
【数１７】
0006508661.tif 000018
【００４７】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【００４８】
【数１８】
0006508661.tif 000019
【００４９】
であり、
【００５０】
【数１９】
0006508661.tif 000020
【００５１】
は
【００５２】
【数２０】
0006508661.tif 000021
【００５３】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、j は変数であり、jの値は1からnの範囲である、ステップと、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとを含む。
【００５４】
第5の態様を参照すると、第5の態様の第1の可能な実施方式では、データ処理システムは、第2のクラスの計算ノードをさらに含み、方法は、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップであって、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
計算ノードSCyによって、第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するステップであって、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果である、ステップと、
計算ノードSCyによって、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するステップであって、ここで、第2の中間結果V’’yは、m次元データを含むベクトルである、ステップと、
管理ノードによって、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【００５５】
第5の態様の第1の可能な実施方式を参照すると、第2の可能な実施方式では、データセットは、データブロックV2xをさらに含み、データブロックV2xは、m次元データを含むベクトルであり、方法は、
管理ノードによって、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップと、
計算ノードSCyによって、第3の処理タスクに従って、データセット内のデータブロックV2xを取得するステップと、
計算ノードSCyによって、SCyによって取得された第2の中間結果V’’yおよびデータブロックV2xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【００５６】
第6の態様によると、本発明の実施形態は別のデータ処理方法を提供し、ここで、方法はデータ処理システムに適用され、データ処理システムは、管理ノードと第1のクラスの計算ノードとを含み、方法は、
管理ノードによって、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当てるステップであって、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理する、ステップと、
計算ノードFCxによって、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するステップであって、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である、ステップと、
計算ノードFCxによって、データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するステップであって、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【００５７】
【数２１】
0006508661.tif 000022
【００５８】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【００５９】
【数２２】
0006508661.tif 000023
【００６０】
であり、
【００６１】
【数２３】
0006508661.tif 000024
【００６２】
は
【００６３】
【数２４】
0006508661.tif 000025
【００６４】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である、ステップと、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとを含む。
【００６５】
第6の態様を参照すると、第1の可能な実施方式では、データ処理システムは、第2のクラスの計算ノードをさらに含み、方法は、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップであって、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
計算ノードSCyによって、第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するステップであって、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果である、ステップと、
計算ノードSCyによって、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するステップであって、ここで、第2の中間結果M’’yは、m行p列のデータを含む行列である、ステップと、
管理ノードによって、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【００６６】
第6の態様の第1の可能な実施方式を参照すると、第2の可能な実施方式では、データセットは、データブロックM3xをさらに含み、データブロックM3xは、m行p列のデータを含む行列であり、方法は、
管理ノードによって、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップと、
計算ノードSCyによって、第3の処理タスクに従って、データセット内のデータブロックM3xを取得するステップと、
計算ノードSCyによって、SCyによって取得された第2の中間結果M’’yおよびデータブロックM3xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【００６７】
前述の技術的解決手段に基づくと、本発明の実施形態によって提供されるデータ処理システム、計算ノードおよびデータ処理方法によって、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【図面の簡単な説明】
【００６８】
本発明の実施形態における技術的解決手段をより明確に説明するために、以下では、実施形態または従来技術を説明するために必要とされる添付図面を簡潔に導入する。明らかに、以下の説明における添付図面は、単に本発明のいくつかの実施形態を示す。
【００６９】
【図１】図1は、本発明の実施形態に係る、“グラフ”の概略図である。
【図２】図2は、本発明の実施形態に係る、“グラフ”の別の概略図である。
【図３Ａ】図3Aは、対象間の関係を表す“有向グラフ”の概略図である。
【図３Ｂ】図3Bは、図3Aにおける“有向グラフ”に対応する隣接行列を示す。
【図４】図4は、行列-ベクトル乗算操作の概略図である。
【図５】図5は、行列-行列乗算操作の概略図である。
【図６Ａ】図6Aは、対象間の関係を表す“重み付き有向グラフ”の概略図である。
【図６Ｂ】図6Bは、図6Aにおける“重み付き有向グラフ” に対応する隣接行列を示す。
【図７】図7は、別の行列-ベクトル乗算操作の概略図である。
【図８】図8は、本発明の実施形態に係る、データ処理システムの概略ブロック図である。
【図９】図9は、本発明の実施形態に係る、データ処理システムによってデータ処理を実行する概略フローチャートである。
【図１０】図10は、本発明の実施形態に係る、シングルソース最短経路（Single Source Shortest Path, SSSP）アルゴリズムの概略図である。
【図１１】図11は、本発明の実施形態に係る、別のデータ処理システムの概略ブロック図である。
【図１２】図12は、本発明の実施形態に係る、別のデータ処理システムによってデータ処理を実行する概略フローチャートである。
【図１３】図13は、本発明の実施形態に係る、別のデータ処理システムによって確率伝播アルゴリズムを実行する概略図である。
【図１４】図14は、本発明の実施形態に係る、計算ノードの概略ブロック図である。
【図１５】図15は、本発明の実施形態に係る、別の計算ノードの概略ブロック図である。
【図１６】図16は、本発明の実施形態に係る、別の計算ノードの概略ブロック図である。
【図１７】図17は、本発明の実施形態に係る、別の計算ノードの概略ブロック図である。
【図１８】図18は、本発明の実施形態に係る、データ処理方法の概略フローチャートである。
【図１９】図19は、本発明の実施形態に係る、別のデータ処理方法の概略フローチャートである。
【発明を実施するための形態】
【００７０】
以下では、本発明の実施形態における添付図面を参照して、本発明の実施形態における技術的解決手段を明確且つ完全に説明する。明らかに、説明される実施形態は、本発明の実施形態の全てではなく一部である。
【００７１】
理解を容易にするために、本明細書に関係するコンセプトおよび関連技術が、最初に簡潔に説明される。
【００７２】
グラフ：
【００７３】
グラフは、対象間の関係を説明するために使用される。直感的に、グラフはいくつかの小さな点および点をつなぐ線を含む。点は、グラフの頂点と呼ばれる。点をつなぐ線は、辺と呼ばれる。辺は図1に示される無向辺と、図2に示される有向辺とに分類されてよい。図1は、6個の対象1から6を含み、6個の対象間の関係は、6個の対象間の無向辺によって表される。図2は7個の対象0から6を含み、7個の対象間の一方向関係は、7個の対象間の有向辺によって表される。対象間の関係が有向辺によって表されるとき、グラフは有向グラフと呼ばれることができる。
【００７４】
乗算
【００７５】
本明細書では、乗算は、一般化された乗算を表してよく、または、2つの数の乗算を表してよい。例えば、行列-ベクトル乗算における乗算は、一般化された乗算を指す。すなわち、行列内の要素とベクトルに対応する要素の乗算は、従来の数の乗算ではなく、加算、減算、乗算、除算、最大化または最小化等の他の処理であり、これは、本発明の実施形態では限定されない。
【００７６】
隣接行列：
【００７７】
隣接行列は、本明細書では行列と略して書かれ、グラフの頂点間の隣接関係を記憶する2次元行列である。図3Aおよび図3Bに示されるように、図3Aは有向グラフであり、6個の頂点V1からV6を含み、ここで、有向辺は6個の頂点間の相互関係を表し、図3Bは、対応する隣接行列の表現形態を示す。グラフを表すために隣接行列が使用され、これは、グラフに対する同時処理を容易にすることができる。行列は、密行列と疎行列とに分類されてよい。密行列は一般に、ベクトルまたは二重ベクトル（ベクトルのベクトル）を使用することによって表され、行優先順序の行列と列優先順序の行列とに分類される。疎行列（非ゼロ要素が記憶される）は一般に、COO、CSRおよびCSCの3つの記憶形式を有する。行列表現におけるゼロ要素（または、例えば、SSSPアルゴリズムの無限要素）は、記憶中に記憶される必要はなく、従って、記憶されるデータ量は、行列を使用してグラフを表すことによって、低減されることができる。隣接行列表現では、グラフに対するたいていの操作は、行列-ベクトル乗算（すなわち、行列とベクトルの乗算）操作、または、行列-行列乗算（すなわち、行列と行列の乗算）操作に転換されてよい。
【００７８】
行列-ベクトル乗算操作
【００７９】
行列-ベクトル乗算操作は、行列とベクトルとの間の一連の操作を指す。行列-ベクトル乗算操作を使用することによるグラフ計算を表現する例では、図3Aにおける有向グラフ内のV2の全てのフレンドは、図4に示される行列-ベクトル乗算の方式で検索されることができる。初めに、クエリベクトルが構成される。V2のアウトネイバー（OutNeighbors）が検索されるため、ベクトル内の第2の要素は1に設定され、他の要素は0に設定される。次に、outneighborsが検索されるため、隣接行列は転置される必要がある。最後に、転置の後に取得された隣接行列と構成されたベクトルが乗算され（図4に示される）、結果ベクトルを取得する。図に示される結果ベクトルの第6のビットは1であり、V2はフレンドV6のみを有すると示す。この結果は図3Aで検証されることができる。
【００８０】
行列-行列乗算操作
【００８１】
行列-行列乗算操作は行列間の一連の操作を指す。行列-行列乗算操作を使用することによるグラフ計算を表す例では、図3Aにおける2つの頂点毎の相互フレンド（例えば、アウトネイバー）の数は、行列-行列乗算操作を使用することによって計算されることができる。初めに、隣接行列が構成される。図3Bの行列によって示されるように、ここでは、行列はAを使用することによって表される。次いで、B=(bij)=A*AT（図5に示される）を実行することによって行列B内の要素bijの値が取得され、第i頂点と第j頂点の相互アウトネイバーの数を表す。例えば、行3列1の値は1であり、頂点3および頂点1が1つの相互フレンドを有すると示す。
【００８２】
分散行列
【００８３】
計算のために使用される複数の計算ユニットがクラスタ環境に含まれる。行列-ベクトル乗算操作および行列-行列乗算操作は、両方とも、行列分割に基づいて実行される。分割された後、行列は、分散行列と呼ばれてよい。複数の計算ユニットを使用することによって、分散行列への同時処理が実行されてよい。
【００８４】
次いで、従来技術の行列-ベクトル乗算モデルについて簡潔な説明が提供される。
【００８５】
従来の行列操作は、数値に対してのみであり、特定の操作に対して制限が課される。例えば、従来の行列-ベクトル乗算が公式1に示され、MijとVjとの間の操作は乗算以外有り得ず、一行の行列とベクトルの積間の操作は（各積はxj= MijVjとして記録される）、加算以外有り得ない。結果として、行列操作によって表されることができるアルゴリズムは非常に制限される。例えば、SSSPアルゴリズムは、従来の行列-ベクトル乗算によって表されることはできない。
【００８６】
【数２５】
0006508661.tif 000026
【００８７】
ここで、Mはm行n列を持つ行列であり、MijはMが分割された後に取得される行列ブロックであり、Vはn次元列ベクトルであり、VjはVが分割された後のベクトルブロックであり、V’はm次元列ベクトルである。
【００８８】
従来技術の行列-ベクトル乗算モデルに対する制限のために、行列-ベクトル乗算操作に基づくビッグデータ処理システムPEGASUSはGIMVモデルを提案する。GIMVモデルは、従来の行列-ベクトル乗算を拡張する。
【００８９】
1. MijおよびVjに対する処理は、結合操作combine2に拡張され、ここで、combine2は、行列要素とベクトル要素に対して実行される結合操作であり、行列要素とベクトル要素のタイプは異なってよく、combine2操作は、加算、減算、乗算、除算、最大化、最小化等であってよく、これは、本発明の実施形態では限定されず、combine2の後、中間値xjが返される。
【００９０】
2. 行列の行に対するcombine2結果x1, …,およびxnに対して結合操作combineAllが実行され、ここで、combineAllは、複数の数値または記録集合に対して実行される結合操作であり、且つ、一般に、関数（例えば、累積関数であってよい）であり、combineAllの後、中間値
【００９１】
【数２６】
0006508661.tif 000027
【００９２】
が返される。
【００９３】
3. 計算を介して現在取得された
【００９４】
【数２７】
0006508661.tif 000028
【００９５】
と初期ベクトルVの要素Viに対して割り当て操作assignが実行されて、現在計算された結果ベクトルにおける要素の値
【００９６】
【数２８】
0006508661.tif 000029
【００９７】
を取得する。
【００９８】
GIMVモデルによると、行列MとベクトルVが入力され、3つの操作の後にベクトルV’が出力される。操作のために、主に3つの演算子がある：
【００９９】
【数２９】
0006508661.tif 000030
【０１００】
ここで、
1. combine2(Mij,Vj): MijとVjに対して結合操作が実行されて、中間結果xjを取得する；
2. combineAll(x1,..., xn): 行列の行のための中間結果x1, …,およびxnに対して結合操作が実行されて、中間結果
【０１０１】
【数３０】
0006508661.tif 000031
【０１０２】
を取得する；
3. 
【０１０３】
【数３１】
0006508661.tif 000032
【０１０４】
: 初期ベクトルの要素Viおよび対応する中間結果
【０１０５】
【数３２】
0006508661.tif 000033
【０１０６】
に対して割り当て操作が実行されて、結果ベクトル内の要素の値
【０１０７】
【数３３】
0006508661.tif 000034
【０１０８】
を取得する。
【０１０９】
GIMVモデルはより多くのアルゴリズムを表すことができる。例えば、SSSPアルゴリズムは、combine2操作は“加算”操作であり、すなわち、combine2(Mij,Vj)= Mij+Vjであり、combineAll操作は“最小化”操作であり、すなわち、combineAll(x1,..., xn)=min(x1,..., xn)であり、assign操作もまた、“最小化”操作であり、すなわち、
【０１１０】
【数３４】
0006508661.tif 000035
【０１１１】
であることに対応してよい。
【０１１２】
図6Aは重み付き有向グラフを示し、図6Bは対応する隣接行列Mを示す。行列M内の値は、2つの点の距離の重みであり、頂点からその頂点自身までの距離は0であり、到達できないことは無限によって表される。頂点0から全ての他の頂点までの最短距離を求めるために、反復行列-ベクトル乗算が使用されてよい。各反復は、ホップカウントに1追加することによって得られる最短距離を表す（例えば、頂点1から頂点2まで1つのホップがあり、頂点2を通って、頂点1から頂点3まで2つのホップがある）。
【０１１３】
アルゴリズムでは、初期ベクトルVが最初に構成され、頂点0から開始し、従って、図7におけるVによって示されるように、初期ベクトルVの位置0（第1行の要素）における値は0である。計算の間、図6Bにおける隣接行列Mが転置された後に得られる結果は、初期ベクトルVによって乗算され、次いで、SSSPアルゴリズムにおける3つの演算子：combine2(Mij,Vj)= Mij+Vj、combineAll(x1,..., xn)=min(x1,..., xn)および
【０１１４】
【数３５】
0006508661.tif 000036
【０１１５】
を使用することによって操作が実行される。最初の乗算を介して得られた結果ベクトルV’は、1つのホップの後に到達されることができる頂点0から他の頂点までの最短距離を表す。SSSPアルゴリズムにおける反復終了条件は、反復を介して得られた結果ベクトルV’が反復の初期ベクトルVと比較して変化していない場合に、アルゴリズムが終了することである。終了条件が満たされない場合、アルゴリズムにおいて反復は実行され続ける。すなわち、現在の反復の結果ベクトルV’は、次の反復を実行するために次の反復の初期ベクトルVとして使用され、アルゴリズムに従って得られた最後の結果ベクトルV’は、頂点0から他の頂点までの最短距離である。
【０１１６】
GIMVモデルの実行手順は、全てのcombine2操作が完了した後にのみ、行列の行のための全てのcombine2結果に対してcombineAll操作が実行されることができることである。従って、計算プロセスでは、combineAll操作は、行列のサイズを持つ中間メモリ空間を占有する必要がある。加えて、分散環境では、システムは大量のデータを伝送する必要がある。assign操作は、初期ベクトルVとcombineAllを使用することによって得られた中間ベクトル
【０１１７】
【数３６】
0006508661.tif 000037
【０１１８】
に対して実行される操作である。従って、2つのベクトルの次元は等しい必要がある。別の観点から、行列Mは正方行列である必要がある。さらに、assign操作におけるベクトルは初期ベクトルV以外には有り得ず、これはまた、GIMVモデルの表現範囲を制限する。
【０１１９】
本発明では、データ処理のための行列-ベクトル乗算操作プロセスにおいて、中間メモリ占有および伝送されるデータ量を低減するために、前述の解決手段における欠点のためにデータ処理方法が改善される。加えて、本発明における行列-ベクトル乗算操作の原理と同様の原理に基づいて、行列-行列乗算操作モデルが提案され、その結果、より多くのアルゴリズムが表現されることができる。
【０１２０】
図8は、本発明の実施形態に係る、データ処理システム100の概略ブロック図である。図8に示されるように、データ処理システム100は、管理ノード110と第1のクラスの計算ノード120とを含む。
【０１２１】
管理ノード110は、第1の処理タスクを、FCx 121を含み、第1のクラスの計算ノード120内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCx 121は少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数である。
【０１２２】
第1のクラスの計算ノード120内の少なくとも2つの計算ノードは、管理ノード110によって割り当てられた第1の処理タスクを同時に処理する。
【０１２３】
計算ノードFCx 121は、管理ノード110によって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得し、
データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するように構成され、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上であり、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【０１２４】
【数３７】
0006508661.tif 000038
【０１２５】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０１２６】
【数３８】
0006508661.tif 000039
【０１２７】
であり、
【０１２８】
【数３９】
0006508661.tif 000040
【０１２９】
は
【０１３０】
【数４０】
0006508661.tif 000041
【０１３１】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である。
【０１３２】
管理ノード110は、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【０１３３】
従って、本発明の本実施形態によって提供されるデータ処理システムによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０１３４】
具体的には、本発明の本実施形態によって提供されるデータ処理システム100は、ビッグデータ処理に適用されてよい。ビッグデータ処理のためのデータ量は比較的大きいため、計算効率を改善するために、データは通常分割され、異なるデータブロックは、同時計算のために異なる計算ノードに分配される。データ処理システム100は、管理ノード110と第1のクラスの計算ノード120とを含む。管理ノード110は、データ処理タスクを受信し、データ処理タスクを複数の処理タスクに分割し、処理タスクを計算ノードに配送するように構成される。管理ノード110は、データ処理プロセスを管理するために、計算ノードによって計算ノードの処理タスクを実行する状態を受信するようにさらに構成される。計算ノードは、対応する処理タスクを実行するために、管理ノード110によって配送された処理タスクを受信し、処理タスクに従って、データブロックを取得するように構成される。計算ノードは、計算ノードに記憶されたデータブロックを取得して、処理タスクを実行してよく、または、別の計算ノードに記憶されたデータブロックを取得して、処理タスクを実行してよい。処理タスクのクラスは異なるため、計算ノードは、計算ノードの処理タスクのクラスに従って分類されてよい。例えば、第1のクラスのノードは第1の処理タスクを処理し、第2のクラスのノードは第2の処理タスクを処理する。
【０１３５】
本発明の本実施形態では、管理ノード110は、第1の処理タスクを、FCx 121を含み、第1のクラスの計算ノード120内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCx 121は少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数である。第1のクラスの計算ノード120内の少なくとも2つの計算ノードは、管理ノード110によって割り当てられた第1の処理タスクを同時に処理する。
【０１３６】
管理ノード110によって割り当てられた第1の処理タスクを受信した後、計算ノードFCx 121は、第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得し、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である。データブロックMxおよびデータブロックV1xに対する処理は、行列-ベクトル乗算操作とみなされてよい。
【０１３７】
計算ノードFCx 121は、データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得し、ここで、第1の中間結果V’xは、m次元データを含むベクトルである。第1の中間結果V’xは、要素
【０１３８】
【数４１】
0006508661.tif 000042
【０１３９】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０１４０】
【数４２】
0006508661.tif 000043
【０１４１】
であり、
【０１４２】
【数４３】
0006508661.tif 000044
【０１４３】
は
【０１４４】
【数４４】
0006508661.tif 000045
【０１４５】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である。
【０１４６】
具体的には、データブロックMxの第i行第j列の要素およびデータブロックV1xの第j行の要素に対して結合操作が実行されて、データブロックMxの第i行第j列の要素およびデータブロックV1xの第j行の要素に対応する中間結果xjを取得する。ここでの結合操作は、上述のcombine2処理であってよく、且つ、中間結果を表現するための公式：xj= combine2(mi,j, vj)において使用されてよい。
【０１４７】
次いで、データブロックMxの第i行に対応する中間結果xjに対してreduce2操作が実行されて、データブロックMxの第i行に対応する要素
【０１４８】
【数４５】
0006508661.tif 000046
【０１４９】
を取得し、ここで、iの値は1からmの範囲であり、この場合、第1の中間結果V’xが取得されることができる。combine2操作およびreduce2操作は、初めに、x1およびx2を計算して、x1およびx2に対してreduce2操作を実行し；次いで、x3を計算して、x3とx1およびx2に対してreduce2操作が実行された後に得られた結果とに対してreduce2操作を実行し；…,データブロックMxの第i行に対応する中間結果xjの各要素がreduce2操作を受けるまで繰り返されることであってよい。reduce2操作は、全てのcombine2操作が完了した後に実行されないが、combine2操作とreduce2操作は交替で実行される。このようにして、計算プロセスにおいてreduce2操作を受けた中間結果xjは削除されることができ、且つ、メモリ内に全てのcombine2操作の結果を記憶する必要はなく、従ってメモリ空間は低減されることができる。
【０１５０】
前述のプロセスは本質的に更新プロセスであると理解されるべきである。すなわち、reduce2操作が2つのxjに対して実行された後に得られる中間結果を取得するために、reduce2操作が初めに実行され、次いで、中間結果を連続的に更新するために、中間結果を取得するために、取得された中間結果と別のxjまたは別の中間結果に対してreduce2操作が実行される。
【０１５１】
ここでの削減2（reduce2）操作は、加算、減算、乗算、除算、最大化、最小化等であってよく、これは、本発明の本実施形態で限定されない。ここでは、reduce2操作を使用することによって、行列の行の要素に対応する中間結果（例えば、x1,…,xn）に対する処理のために、reduce2処理は、x1,…,xnの全てが計算された後に実行される代わりに、中間結果xjを計算するプロセスにおいて１ステップずつ実行される。
【０１５２】
reduce2操作の利点は、reduce2操作が実行される要素の順序は、計算プロセスにおいて考慮される必要がなく、すなわち、reduce2操作が実行される要素の順序に関わらず結果のみが得られることであることは理解されるべきである。例えば、Scala言語では、配列はit=Array(0,1,2,3,4,5)であり、配列内の要素は合計され、これはit.reduce(_+_)と表現されてよい。計算の具体的な実施中は、左から右へデータを加えることによって得られた値は、データに対して対reduce2操作を実行することによって得られる最終値と同じである。x3とx1およびx2に対してreduce2操作が実行された後に得られた結果とに対してreduce2操作を実行する前述の説明は、1つの実施方式にすぎない。reduce2操作の実行順序は、x1,..., xnの順序に限定されない。シーケンシャルな実行の後に得られた結果と同じ結果が、x1,..., xnのうちの任意の2つに対してreduce2操作を実行し、次いで、取得された結果および別のxjに対してreduce2操作を実行することによって得られることができる。本発明の本実施形態におけるreduce2操作の順序に対して限定は課されない。
【０１５３】
管理ノード110は、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。第1の処理タスクを完了した後、第1のクラスの計算ノード120は管理ノード110に通知する。管理ノード110は、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するか、別の処理タスクのための基礎データとして第1の中間結果を使用することによって、対応する計算ノードに、第1の中間結果を使用することによって計算されるべき別の処理タスクを配送する。
【０１５４】
従って、本発明の本実施形態によって提供されるデータ処理システムによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０１５５】
任意で、実施形態では、データ処理システム100は第2のクラスの計算ノードをさらに含み、且つ、管理ノード110は、
第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成され、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である。
【０１５６】
計算ノードSCyは、
第2の処理タスクに従って、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得し、
SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するように構成され、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果であり、ここで、第2の中間結果V’’yは、m次元データを含むベクトルである。
【０１５７】
管理ノード110は、
第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【０１５８】
具体的には、前述の処理が完了した後、第1のクラスの計算ノード120によって取得された第1の中間結果に対して他の処理がさらに実行されてよい。例えば、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって処理されるデータブロックMxは、処理されるべきデータセット内の1行のデータブロックであり、管理ノード110は、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得される第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当ててよく、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である。
【０１５９】
計算ノードSCyは、第2の処理タスクに従って、第1のクラスの計算ノード120内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するように構成され、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果である。第2の処理タスクは、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得することであり、ここで、第2の中間結果V’’yは、m次元データを含むベクトルである。SCyによって取得された第1の中間結果に対して実行されたreduce2操作は上述のreduce2操作と同様である。すなわち、reduce2操作は、初めに、処理されるべきデータセット内の1行のデータブロックを使用することによって取得された2つの第1の中間結果に対して実行され、次いで、reduce2操作は、前述のreduce2操作の結果および別の第1の中間結果に対して実行される。
【０１６０】
管理ノード110は、具体的には、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するように構成される。
【０１６１】
任意で、実施形態では、データセットはデータブロックV2xをさらに含み、データブロックV2xは、m次元データを含むベクトルである。管理ノード110は、具体的には、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成される。
【０１６２】
計算ノードSCyは、第3の処理タスクに従って、データセット内のデータブロックV2xを取得し、
SCyによって取得された第2の中間結果V’’yおよびデータブロックV2xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【０１６３】
具体的には、処理されるべきデータセット内の1行のデータブロックを使用することによって取得された第1の中間結果に対してreduce2操作が実行された後、処理されるべきデータセットのための処理結果を取得するために、取得された第2の中間結果に対してassign操作がさらに実行されてよい。第2の中間結果V’’yおよびデータブロックV2xの両方は、m次元データを含むベクトルである。結果ベクトルは、対応する要素に対してassign操作を実行することによって取得されてよく、ここで、結果ベクトルはm次元列ベクトルである。ここでの割り当て処理は、上述のassign処理であってよく、且つ、結果ベクトル内の要素V3,i=assign(V’’i,V2,i)を表現するための公式において使用されてよく、ここで、m個のV3,iは結果ベクトルV3xを形成する。
【０１６４】
前述は、行列-ベクトル乗算操作プロセスである。結論として、本発明の本実施形態における行列-ベクトル乗算操作は、以下の公式3：
【０１６５】
【数４６】
0006508661.tif 000047
【０１６６】
として表されてよい。
【０１６７】
既存のGIMVモデルと比較すると、本発明の本実施形態におけるassign処理ではベクトルV2が追加され、従って、結果ベクトルV3は、
V3=α*M*V1+β*V2            (公式4)
として表現されてよく、ここで、αおよびβは数値であり、公式4は、既存のGIMVモデルと比較して、本発明の本実施形態におけるデータ処理システム100によって取得される結果ベクトルV3に重みV2が導入されることを示し、その結果、assign処理はもはや乗算のために使用されるベクトルに限定されず、非正方行列に対する行列-ベクトル乗算操作がサポートされることができ、行列-ベクトル乗算操作の表現範囲を拡張する。
【０１６８】
以下では、行列-ベクトル乗算操作に重みV2を導入する関数を説明するための具体的な例を使用する。例えば、性能テストのために使用されるページランク（PageRank）アルゴリズムでは、“加算のために使用されるベクトル”（前述のベクトルV2に対応する）はしばしば操作のために(1-d)/Nに設定される。ベクトル(1-d)/Nは対応するグラフにおける頂点のPageRank値を調整するために使用されてよく、その結果、頂点のPageRank値は真実性をより良く満たす。PageRank値はRとして表現されてよく、具体的には、公式5として表現される：
【０１６９】
【数４７】
0006508661.tif 000048
【０１７０】
例えば、いくつかの公式ウェブサイトについては、公式ウェブサイトに対応する頂点の値はベクトル内で比較的大きく設定されてよく、この場合、取得される結果PageRank値は一般に比較的大きい。
【０１７１】
任意で、実施形態では、m=nであり、データブロックV1xおよびデータブロックV2xは同じデータブロックである。すなわち、それと共にデータブロックMxに対して操作が実行されるデータブロックV1xとassign操作を実行するために使用されるデータブロックV2xは同じデータブロックである。
【０１７２】
任意で、実施形態では、第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、第2のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第2の処理タスクを同時に処理する。処理されるべきデータセットが行と列両方によって分割されるとき、第2のクラスの計算ノードのうちの少なくとも2つが、第2の処理タスクを処理するために必要とされる。処理されるべきデータセットが列によってのみ分割されるとき、第2のクラスの計算ノードのうちの1つが必要とされる。処理されるべきデータセットが行によってのみ分割されるとき、第2のクラスの計算ノードは必要とされず、すなわち、第2の処理タスクは処理される必要がない。
【０１７３】
任意で、実施形態では、管理ノード、第1のクラスの計算ノードおよび第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUであってよく、これは、本発明の本実施形態では限定されない。
【０１７４】
以下では、具体的な例を参照して、本発明の本実施形態を詳細に説明する。
【０１７５】
図9は、本発明の実施形態に係る、データ処理システム100によってデータ処理を実行する概略フローチャートである。図9に示されるように、データ処理システム100によって実行されるデータ処理は、以下のステップを含む：
【０１７６】
S201：前処理を実行して、データブロックM’、データブロックV1’およびデータブロックV2’を取得し、ここで、データブロックM’は行列であり、データブロックV1’およびデータブロックV2’はベクトルである。
【０１７７】
S202：行列分配を実行し、行列M’を分割し、行列M’のブロックをクラスタの少なくとも2つの計算ノードに分配し、ここで、データブロックMxは計算ノードFCxに分配される。
【０１７８】
S203：データブロックV2’を分配し、データブロックV2’を分割し、分割されたデータブロックV2’をブロードキャストする。
【０１７９】
S204：データブロックV1’を分配し、データブロックV1’を分割し、分割されたデータブロックV1’をブロードキャストする。S202からS204で分割された行列およびベクトルは、対応して、少なくとも2つの計算ノードに分配され、ここで、計算ノードは分散されている。
【０１８０】
S205：各計算ノードは部分combine2処理および部分reduce2処理を実行する。データブロックMxおよびデータブロックV1xに対してcombine2処理が実行され、データブロックMxおよびデータブロックV1xに対応する全ての中間結果が取得される前に、中間結果に対してreduce2処理が実行されて、第1の中間結果を取得する。次いで、第1の中間結果および新たに取得された中間結果に対してreduce2処理が実行されて、新しい第1の中間結果を取得する。最後の第1の中間結果は、データブロックMxおよびデータブロックV1xに対応する全ての中間結果に対してreduce2処理が実行した後に取得される結果である。
【０１８１】
S206：各計算ノードは、S205で取得された最後の第1の中間結果に対して全データ伝送を実行し、その結果、最後の第1の中間結果は1つの計算ノード内に集められる。本発明の本実施形態における方法によると、全データ伝送は、削減処理の後に取得されたデータに対して実行される。従って、既存の行列-ベクトル乗算操作と比較して、伝送されたデータ量は大幅に削減される。
【０１８２】
S207：行列M’内の1つの水平位置における少なくとも2つの行列ブロックに対応する第1の中間結果の要素に対してreduce2処理を実行して、第2の中間結果の要素を取得する。すなわち、1つの水平位置における複数の行列ブロックの各行内の第1の中間結果の要素に対してreduce2処理が実行されて、第2の中間結果の要素を取得する。第2の中間結果の複数の要素は第2の中間結果V’’yを形成する。
【０１８３】
S208：第2の中間結果V’’yの要素およびデータブロックV2x内の対応する要素に対してassign処理を実行して、結果ベクトル内の要素を取得して、結果ベクトルをさらに取得する。
【０１８４】
S209：終了条件が満たされるかどうかを判定し、終了条件が満たされる場合、プロセスは終了し、または、終了条件が満たされない場合、次の反復のためのデータブロックV1’として結果ベクトルを使用することによって、S204からS209 を実行する。
【０１８５】
以下では、上述のSSSPアルゴリズムを使用することによって、頂点0から他の頂点までの最短距離を決定することに関する課題を解決する例を使用することによって、本発明の本実施形態を説明する。SSSPアルゴリズムにおける行列は、図6Bにおける隣接行列Mに対して転置が実行された後に取得される行列であり、且つ、ベクトルV1とベクトルV2の両方は図7におけるVである。図10に示されるように、図6Bにおける隣接行列Mに対して転置が実行された後に取得される行列および初期ベクトルVが最初に分割される。次いで、行列のブロックとVの対応するブロックに対してcombine2処理およびreduce2処理が実行される。ここでは、行列のブロックとVの対応するブロックに対するcombine2処理を介して全ての第1の中間結果が取得される前に、reduce2処理が実行され、すなわち、combine2処理とreduce2処理は交替で実行される。ブロックに対してcombine2処理およびreduce2処理が実行された後、各行列ブロックに対応する第1の中間結果が取得されることができる。1行の行列ブロックに対応する第1の中間結果に対するreduce2処理を実行することによって中間ベクトル
【０１８６】
【数４８】
0006508661.tif 000049
【０１８７】
が取得されることができる。中間ベクトル
【０１８８】
【数４９】
0006508661.tif 000050
【０１８９】
とVに対してassign処理が実行されて、結果ベクトルを取得する。combine2処理は“加算”処理であり、且つ、combine2(Mij,Vj)=Mij+Vjであり；reduce2処理は“最小化”処理であり、且つ、reduce2(x1,x2)=min(x1,x2)であり；assign処理は“最小化”処理であり、且つ、
【０１９０】
【数５０】
0006508661.tif 000051
【０１９１】
である。
【０１９２】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０１９３】
図11は、本発明の別の実施形態に係る、データ処理システム300の概略ブロック図である。図11に示されるように、データ処理システム300は、管理ノード310および第1のクラスの計算ノード320を含む。
【０１９４】
管理ノード310は、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード320内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数である。
第1のクラスの計算ノード320内の少なくとも2つの計算ノードは、管理ノード310によって割り当てられた第1の処理タスクを同時に処理する。
【０１９５】
計算ノードFCxは、管理ノード310によって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得し、
データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するように構成され、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上であり、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【０１９６】
【数５１】
0006508661.tif 000052
【０１９７】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【０１９８】
【数５２】
0006508661.tif 000053
【０１９９】
であり、
【０２００】
【数５３】
0006508661.tif 000054
【０２０１】
は
【０２０２】
【数５４】
0006508661.tif 000055
【０２０３】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である。
【０２０４】
管理ノード310は、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【０２０５】
従って、本発明の本実施形態によって提供されるデータ処理システムによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０２０６】
具体的には、本発明の本実施形態によって提供されるデータ処理システム300は、ビッグデータ処理に適用されてよい。ビッグデータ処理のためのデータ量は比較的大きいため、計算効率を改善するために、データは通常分割され、異なるデータブロックは、同時計算のために異なる計算ノードに分配される。データ処理システム300は、管理ノード310と第1のクラスの計算ノード320とを含む。管理ノード310は、データ処理タスクを受信し、データ処理タスクを複数の処理タスクに分割し、処理タスクを計算ノードに配送するように構成される。管理ノード310は、データ処理プロセスを管理するために、計算ノードによって計算ノードの処理タスクを実行する状態を受信するようにさらに構成される。計算ノードは、対応する処理タスクを実行するために、管理ノード310によって配送された処理タスクを受信し、処理タスクに従って、データブロックを取得するように構成される。計算ノードは、計算ノードに記憶されたデータブロックを取得して、処理タスクを実行してよく、または、別の計算ノードに記憶されたデータブロックを取得して、処理タスクを実行してよい。処理タスクのクラスは異なるため、計算ノードは、計算ノードの処理タスクのクラスに従って分類されてよい。例えば、第1のクラスのノードは第1の処理タスクを処理し、第2のクラスのノードは第2の処理タスクを処理する。
【０２０７】
本発明の本実施形態では、管理ノード310は、第1の処理タスクを、FCx 321を含み、第1のクラスの計算ノード320内にある少なくとも2つの計算ノードに割り当てるように構成され、ここで、FCx 321は少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数である。第1のクラスの計算ノード320内の少なくとも2つの計算ノードは、管理ノード310によって割り当てられた第1の処理タスクを同時に処理する。
【０２０８】
管理ノード310によって割り当てられた第1の処理タスクを受信した後、計算ノードFCx 321は、第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得し、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である。データブロックM1xおよびデータブロックM2xに対する処理は、行列-行列乗算操作とみなされてよい。
【０２０９】
計算ノードFCx 321は、データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得し、ここで、第1の中間結果M’xは、m行p列のデータを含む行列である。第1の中間結果M’xは、要素
【０２１０】
【数５５】
0006508661.tif 000056
【０２１１】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【０２１２】
【数５６】
0006508661.tif 000057
【０２１３】
であり、
【０２１４】
【数５７】
0006508661.tif 000058
【０２１５】
は
【０２１６】
【数５８】
0006508661.tif 000059
【０２１７】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である。
【０２１８】
具体的には、データブロックM1xの第i行第k列の要素およびデータブロックM2xの第k行第j列の要素に対して結合操作が実行されて、データブロックM1xの第i行第k列の要素およびデータブロックM2xの第k行第j列の要素に対応する中間結果xikjを取得する。ここでの結合操作は、上述のcombine2操作であってよく、且つ、中間結果を表現するための公式：xikj= combine2(m1[i,k], m2[k,j])において使用されてよい。
【０２１９】
次いで、データブロックM1xの第i行およびデータブロックM2xの第j列に対応する中間結果xikjに対してreduce2操作が実行されて、データブロックMxの第i行およびデータブロックM2xの第j列に対応する要素
【０２２０】
【数５９】
0006508661.tif 000060
【０２２１】
を取得し、ここで、iの値は1からmの範囲であり、jの値は1からpの範囲であり、この場合、第1の中間結果M’xが取得されることができる。combine2操作およびreduce2操作は、初めに、xi1jおよびxi2jを計算して、xi1jおよびxi2jに対してreduce2操作を実行し；次いで、xi3jを計算して、xi3jとxi1jおよびxi2jに対してreduce2操作が実行された後に得られた結果とに対してreduce2操作を実行し；…,データブロックMxの第i行およびデータブロックM2xの第j列に対応する中間結果xikjの各要素がreduce2操作を受けるまで繰り返されることであってよい。reduce2操作は、全てのcombine2操作が完了した後に実行されないが、combine2操作とreduce2操作は交替で実行される。このようにして、計算プロセスにおいてreduce2操作を受けた中間結果xjは削除されることができ、且つ、メモリ内に全てのcombine2操作の結果を記憶する必要はなく、従ってメモリ空間は低減されることができる。
【０２２２】
前述のプロセスは本質的に更新プロセスであると理解されるべきである。すなわち、reduce2操作が2つのxikjに対して実行された後に得られる中間結果を取得するために、reduce2操作が初めに実行され、次いで、中間結果を連続的に更新するために、中間結果を取得するために、取得された中間結果と別のxikjまたは別の中間結果に対してreduce2操作が実行される。
【０２２３】
ここでの削減2（reduce2）操作は、加算、減算、乗算、除算、最大化、最小化等であってよく、これは、本発明の本実施形態で限定されない。ここでは、reduce2操作を使用することによって、行列の行の要素に対応する中間結果（例えば、xi1j,…, xinj）に対する処理のために、reduce2処理は、x1,…,xnの全てが計算された後に実行される代わりに、中間結果xikjを計算するプロセスにおいて１ステップずつ実行される。
【０２２４】
reduce2操作の利点は、reduce2操作が実行される要素の順序は、計算プロセスにおいて考慮される必要がなく、すなわち、reduce2操作が実行される要素の順序に関わらず結果のみが得られることであることは理解されるべきである。例えば、Scala言語では、配列はit=Array(0,1,2,3,4,5)であり、配列内の要素は合計され、これはit.reduce(_+_)と表現されてよい。計算の具体的な実施中は、左から右へデータを加えることによって得られた値は、データに対して対reduce2操作を実行することによって得られる最終値と同じである。xi3jとxi1jおよびxi2jに対してreduce2操作が実行された後に得られた結果とに対してreduce2操作を実行する前述の説明は、1つの実施方式にすぎない。reduce2操作の実行順序は、xi1j,..., xinjの順序に限定されない。シーケンシャルな実行の後に得られた結果と同じ結果が、xi1j,..., xinjのうちの任意の2つに対してreduce2操作を実行し、次いで、取得された結果および別のxikjに対してreduce2操作を実行することによって得られることができる。本発明の本実施形態におけるreduce2操作の順序に対して限定は課されない。
【０２２５】
管理ノード310は、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。第1の処理タスクを完了した後、第1のクラスの計算ノード320は管理ノード310に通知する。管理ノード310は、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得するか、別の処理タスクのための基礎データとして第1の中間結果を使用することによって、対応する計算ノードに、第1の中間結果を使用することによって計算されるべき別の処理タスクを配送する。
【０２２６】
従って、本発明の本実施形態によって提供されるデータ処理システムによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０２２７】
任意で、実施形態では、データ処理システム300は第2のクラスの計算ノードをさらに含み、管理ノード310は、
第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成され、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である。
【０２２８】
計算ノードSCyは、
第2の処理タスクに従って、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得し、
SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するように構成され、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果であり、ここで、第2の中間結果M’’yは、m行p列のデータを含む行列である。
【０２２９】
管理ノード310は、
第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するように構成される。
【０２３０】
具体的には、前述の処理が完了した後、第1のクラスの計算ノード320によって取得された第1の中間結果に対して他の処理がさらに実行されてよい。例えば、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって処理されたデータブロックM1xが、処理されるべきデータセット内の1行のデータブロックであり、且つ、データブロックM2xが処理されるべきデータセット内の1列のデータブロックであるとき、管理ノード310は、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当ててよく、ここで、SCyは、少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である。
【０２３１】
計算ノードSCyは、第2の処理タスクに従って、第1のクラスの計算ノード320内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するように構成され、ここで、SCyによって取得された第1の中間結果は、データブロックM1xおよびデータブロックM2xに従って取得された第1の中間結果であり、ここで、データブロックM1xは、処理されるべきデータセット内の1行のデータブロックであり、データブロックM2xは、処理されるべきデータセット内の1列のデータブロックである。第2の処理タスクは、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得することであり、ここで、第2の中間結果M’’yは、m行p列のデータを含む行列である。SCyによって取得された第1の中間結果に対して実行されたreduce2操作は上述のreduce2操作と同様である。すなわち、reduce2操作は、初めに、データブロックM1xおよびデータブロックM2xを使用することによって取得された2つの第1の中間結果に対して実行され、次いで、reduce2操作は、前述のreduce2操作の結果および別の第1の中間結果に対して実行され、ここで、データブロックM1xは、処理されるべきデータセット内の1行のデータブロックであり、データブロックM2xは、処理されるべきデータセット内の1列のデータブロックである。
【０２３２】
管理ノード310は、具体的には、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するように構成される。
【０２３３】
任意で、実施形態では、データセットは、データブロックM3xをさらに含み、データブロックM3xは、m行p列のデータを含む行列である。管理ノード310は、
SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるようにさらに構成される。
【０２３４】
計算ノードSCyは、
第3の処理タスクに従って、データセット内のデータブロックM3xを取得し、
SCyによって取得された第2の中間結果M’’yおよびデータブロックM3xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するようにさらに構成される。
【０２３５】
具体的には、処理されるべきデータセット内にあるM1xの1行のデータブロックおよびM2xの1列のデータブロックを使用することによって取得された第1の中間結果に対してreduce2操作が実行された後、処理されるべきデータセットのための処理結果を取得するために、取得された第2の中間結果に対してassign操作がさらに実行されてよい。第2の中間結果M’’yおよびデータブロックM3xの両方は、m行p列のデータを含む行列である。結果行列は、対応する要素に対してassign操作を実行することによって取得されてよく、ここで、結果行列はm行p列のデータを含む行列である。ここでの割り当て処理は、上述のassign処理であってよい。
【０２３６】
前述は、行列-行列乗算操作プロセスである。結論として、本発明の本実施形態における行列-行列乗算操作は、以下の公式6として表現されてよい：
【０２３７】
【数６０】
0006508661.tif 000061
【０２３８】
任意で、実施形態では、データ処理システム300内の第2のクラスの計算ノードは、処理されるべきデータセットのために処理結果の第r行に対して行処理を実行するようにさらに構成され、ここで、行処理は、第r行の要素に対する処理である。
【０２３９】
具体的には、結果行列Dがさらに処理されてよい。例えば、結果行列Dの第r行の要素に対して削減処理が実行されてよく、これは、公式reduceRow(Di1,…,Din)を使用することによって表現されてよく、ここで、reduceRow処理は、最大化、最小化、Q個の最大値の選択、Q個の最小値の選択、行内のデータの和等であってよく、これは、本発明の本実施形態では限定されない。reduceRow処理後に取得される結果は、依然として対応する行列形態で記憶されてよい。例えば、結果行列Dの第i行が最大化され、最大値はDi1であり、この場合、数値Di1は記憶された行列の第i行第1列に記憶され、且つ、数値0は他の列に記憶される（または0は記憶されない）。reduceRow処理後に取得された結果が記憶されるとき、処理後に取得された数値のみが記憶されてよい。例えば、結果行列Dの第i行に対して加算処理が実行され、且つ、加算の結果はYであり、この場合、数値Yが記憶される。本発明の本実施形態における記憶方式に対して限定は課されない。
【０２４０】
同様に、実施形態では、データ処理システム300内の第2のクラスの計算ノードは、処理されるべきデータセットのための処理結果の第c列に対して列処理を実行するようにさらに構成され、ここで、列処理は、第c列の要素に対する処理である。繰返しを回避するために、本明細書では詳細はさらに繰り返されない。
【０２４１】
任意で、実施形態では、n=pであり、データブロックM1xとデータブロックM3xは同じデータブロックである。例えば、データブロックM1xは3行4列を持つ行列であり、データブロックM2xは4行4列を持つ行列であり、データブロックM1xおよびデータブロックM2xに対して結合処理が実行されて、3行4列を持つ行列を取得し、3行4列を持つ行列とデータブロックM3xに対して割り当て処理が実行されて、結果行列を取得し、従って、データブロックM1xおよびデータブロックM3xは同じデータブロックであってよいことは理解されるべきである。
【０２４２】
任意で、実施形態では、n=mであり、データブロックM2xとデータブロックM3xは同じデータブロックである。本発明の本実施形態では、計算要件を満たすために、計算に使用される、データブロックM1x、データブロックM2xまたはデータブロックM3xのうちの少なくとも1つに対して転置等の操作が実行されてよいことは理解されるべきである。従って、データブロックM2xとデータブロックM3xは同じデータブロックである。
【０２４３】
任意で、実施形態では、第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、第2のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第2の処理タスクを同時に処理する。
【０２４４】
任意で、実施形態では、管理ノード、第1のクラスの計算ノードおよび第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUを含んでよい。
【０２４５】
以下では、具体的な例を参照して、本発明の本実施形態を詳細に説明する。
【０２４６】
図12は、本発明の実施形態に係る、データ処理システム300によってデータ処理を実行するための方法400の概略フローチャートである。図12に示されるように、方法400は以下のステップを含む：
【０２４７】
S401：前処理を実行して、データブロックM1、データブロックM2およびデータブロックM3を取得し、ここで、データブロックM1、データブロックM2およびデータブロックM3の全ては行列である。
【０２４８】
S402：行列分割を実行して、データブロックM1およびデータブロックM2を分割し、ここで、データブロックM1は複数のデータブロックM1xに分割され、データブロックM1xはm行n列のデータを含む行列であり、データブロックM2は複数のデータブロックM2xに分割され、データブロックM2x はn行p列のデータを含む行列である。
【０２４９】
S403：行列分配を実行して、データブロックM1xを行ごとに少なくとも1つの計算ノードに分配し、対応して、データブロックM2xを列ごとに少なくとも1つの計算ノードに分配する。
【０２５０】
S404：第1のクラスの計算ノードの各々は、部分combine2処理および部分reduce2処理を実行する。combine2処理はデータブロックM1xおよびデータブロックM2xに対して実行され、データブロックM1xの行およびデータブロックM2xの対応する列に対応する全ての中間結果が取得される前に、中間結果に対してreduce2処理が実行されて、第1の中間結果を取得する。次いで、第1の中間結果および新たに取得された中間結果に対してreduce2処理が実行されて、新しい第1の中間結果を取得する。最後の第1の中間結果は、データブロックM1xの行およびデータブロックM2xの対応する列に対応する全ての中間結果に対してreduce2処理が実行された後に取得される結果である。さらに、類推によって、データブロックM1xの行およびデータブロックM2xの列の全ての組合せに対応する最後の第1の中間結果が取得され、ここで、最後の第1の中間結果は行列を形成することができる。
【０２５１】
S405：第1のクラスの計算ノードの各々は、S404で取得された最後の第1の中間結果に対して全データ伝送を実行し、その結果、最後の第1の中間結果は第2のクラスの計算ノードのうちの1つ内に集められる。本発明の本実施形態における方法によると、全データ伝送は、削減処理の後に取得されたデータに対して実行される。従って、伝送されたデータ量は比較的小さい。
【０２５２】
S406：データブロックM1の行およびデータブロックM2の列に対応する少なくとも2つのデータブロックに対応する第1の中間結果に対してreduce2処理を実行して、第2の中間結果を取得する。複数の第2の中間結果は中間行列Xを形成し、中間行列Xは分割されて、少なくとも1つの計算ノードに分配される。
【０２５３】
S407：データブロックM3を分割および分配し、データブロックM3のデータブロックM3xを中間行列Xの行列ブロックが配置される計算ノードに分配し、ここで、データブロックM3xはm行p列のデータを含む行列である。
【０２５４】
S408：中間行列Xの行列ブロック内の要素およびデータブロックM3x内の対応する要素に対してassign処理を実行して、結果行列Dの行列ブロック内の要素を取得して、結果行列Dの行列ブロックをさらに取得する。
【０２５５】
S409：結果行列Dの各行列ブロックに対して、行ごとにreduceRow処理を実行する。
【０２５６】
S410：データ伝送を実行して、S409において取得される各結果を伝送し、次いで、1行の行列ブロックに対応する結果に対してreduceRow処理を実行して、行列Yを取得する。
【０２５７】
S411：行列Yの各行列ブロックに対して、列ごとにreduceCol処理を実行する。
【０２５８】
S412：データ伝送を実行して、S411において取得された各結果を伝送し、次いで、1列の行列ブロックに対応する結果に対してreduceCol処理を実行して、行列Zを取得する。
【０２５９】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０２６０】
確率伝播は推奨されるアルゴリズムの1つである。“ユーザプロジェクト”相互記録データベースは、各ユーザに対して、ユーザが興味を持ち得るいくつかのプロジェクトを推奨する必要がある。確率伝播はグローバルデータに基づき、且つ、ユーザによって潜在的に興味を持たれている全てのプロジェクトを一度に計算するために使用されることができる。アルゴリズムは、堅実な理論的基礎を有する。確率伝播は、物理学における“エネルギー保存の法則”から発展している。行列の操作は、異なる物質間のエネルギー伝播に類似しており、且つ、最終的に取得される興味度行列および元の行列については、対応する行内の要素の合計は絶対的に等しく、且つ、対応する列内の要素の合計もまた絶対的に等しく、このことはエネルギーの保存を明らかにする。
【０２６１】
確率伝播アルゴリズムは、行列に対する操作を使用することによって実施されてよい。行列を使用する既存の確率伝播アルゴリズムの実施において、“映画によるユーザへの魅力度”の行列および“ユーザ間の興味の類似度”の行列が取得されることができ、次いで、“映画によるユーザへの新しい魅力度”の行列を取得するために行列-行列乗算操作が実行され、次に、ユーザによって視聴された映画がふるいにかけられ、最終的に、視聴されていないtop kの映画のみが各ユーザに対して推奨される。確率伝播アルゴリズムによると、各ユーザに対していくつかの映画のみが提供され、比較的疎な結果行列（比較的多くのゼロ要素がある）が取得され、一般的に、データ量は比較的小さい（このようなシナリオでは、ゼロ要素は記憶される必要がない）。しかしながら、既存の解決手段では、“映画によるユーザへの新しい魅力度”の非常に密な行列は、通常、計算プロセスで取得され、データ量は非常に大きい。これは、大量の占有された中間メモリおよびシステムによって伝送された大量のデータという結果をもたらす。
【０２６２】
本発明の実施形態における行列-行列乗算操作を使用することによって実施された確率伝播アルゴリズムでは、元のデータセットにはm個の映画とn人のユーザがあり、top kの映画が各ユーザに対して推奨される。第1の行列Aはm行n列を持つ“映画によるユーザへの魅力度”の行列であり、第2の行列Bはn行n列を持つ“ユーザ間の興味の類似度”の行列であり、assign処理で使用される第3の行列Cおよび第1の行列Aは同じ行列である。この場合、各ユーザに対して、視聴されていないtop kの映画を推奨するための公式は
【０２６３】
【数６１】
0006508661.tif 000062
【０２６４】
である。
【０２６５】
具体的な計算プロセスは、最初に、第1の行列A内の要素および第2の行列B内の要素に対してcombine2処理およびreduce2処理を実行することである。ここで、reduce2処理は、第1の行列A内の要素および第2の行列B内の要素に対するcombine2処理を介して、全ての中間結果が取得される前に実行され、すなわち、combine2処理とreduce2処理は交替で実行される。第1の行列A内の要素および第2の行列B内の要素に対してcombine2処理およびreduce2処理が実行された後、第1の行列Aおよび第2の行列Bに対応する第1の中間結果が取得されることができる。assign処理で使用される第1の中間結果と第3の行列Cに対してassign処理が実行されて、結果行列Dを取得する。最後に、結果行列Dの列に対してreduceCol処理が実行される。
【０２６６】
combine2処理は“乗算”処理であり、且つ、combine2(Aij,Bjk)=Aij*Bjkである。reduce2処理は“加算”処理であり、且つ、xik=reduce2(xi1k,xi2k)=xi1k+xi2kである。assign処理は“スクリーニング”処理であり、且つ、
【０２６７】
【数６２】
0006508661.tif 000063
【０２６８】
である。すなわち、assign処理が実行される第3の行列C内の対応する位置における要素が非ゼロである場合、要素は、ふるいにかけられる（要素は0に設定される）。換言すると、ユーザが映画を視聴しない場合、データは予約され、または、ユーザが映画を視聴した場合、reduceCol処理を実行するために、データはふるいにかけられる（要素は0に設定される）。reduceCol処理は、“top kの評価”処理であり、reduceCol(D1j,…,Dmj)=(D1j,…,Dmj).topkであり、すなわち、第j列のk個の最大値が評価され、ここで、この例におけるkは1である。
【０２６９】
図13は、本発明の実施形態における行列-行列乗算操作を使用することによって実施される確率伝播アルゴリズムの主なフローチャートである。最初に、第1の行列Aの1行および第2の行列Bの1列に対してcombine2処理およびreduce2処理が実行されて、値
【０２７０】
【数６３】
0006508661.tif 000064
【０２７１】
を取得する。次いで、assign処理で使用される第3の行列C内の対応する位置における値は1であるため、assign処理が実行されて、結果行列D内の対応する要素の値が0であることを取得する（システムがゼロ要素を記憶しない場合、対応するcombine2処理およびreduce2処理は、計算のために実行されなくてよい）。最後に、1つの列内の取得された要素に対してtop k評価処理が実行されて、その魅力度がtop kであり、且つ、ユーザによって視聴されていない映画を取得する。
【０２７２】
本発明の実施形態における行列-行列乗算操作によると、確率伝播アルゴリズムを使用することによって、“ユーザに対する映画の新しい魅力度”の行列を計算するプロセスでは、視聴された映画はふるいにかけられることができ（ふるいにかけられる必要がある記録に対するさらなる計算は直接省略されることができる）、且つ、ユーザからのスコアに従って、top kをランク付けした映画が推奨され、その結果、中間メモリの占有およびシステムによって伝送されたデータ量は低減される。
【０２７３】
本発明の実施形態における行列-ベクトル乗算操作および行列-行列乗算操作のプロセスでは、行に対して計算が実行される必要があるかどうかを判定するためにisCompute演算子が導入されることができることは理解されるべきである。計算が必要とされない場合、行はスキップされ、次の行が続いて計算される。計算が必要とされる場合、combine2操作およびreduce2操作がアルゴリズムに従って実行される。通常、行列-ベクトル乗算操作におけるisCompute演算子は、その要素の数がデータブロックMxの行数と等しい列ベクトルであってよく、行列-行列乗算操作におけるisCompute演算子は行列であってよく、これは、本発明の実施形態では限定されない。
【０２７４】
以下では、本発明の実施形態における行列-ベクトル乗算操作の性能および行列-行列乗算操作の性能を説明する。
【０２７５】
一般的な同時計算フレームワークsparkでは、従来技術における拡張GIMVモデルの性能が、本発明の実施形態における行列-ベクトル乗算操作の性能と比較される。テスト環境は、3つのマシン（3つのRH2285、12コア、24スレッド、192Gメモリ、100G設定）を含むクラスタである。wiki_talkデータセットにおけるデータがテストされ、テスト結果は、本発明の実施形態における行列-ベクトル乗算操作は340sを必要とする一方で、従来技術における拡張GIMVモデルのための計算時間は3600sを超過すると示す。
【０２７６】
同様に、sparkでは、本発明の実施形態における行列-行列乗算操作の性能は、従来技術における“推奨された映画を探すこと”を実施する操作の性能と比較される。表1は、テストされたデータセットのサイズおよびテスト結果を示す。相互インターネットプロトコルテレビジョン（interactive internet protocol television, IPTV）データセットおよびNETFLIX (Nasdaq NFLX, NETFLIX)データセット内のデータがテストされる。テスト結果から、本発明の実施形態によると、中間メモリの占有は有効に低減されることができ、且つ、計算時間は短縮されることができ、従って、より大きいデータセットが処理されることができることがわかる。
【０２７７】
【表１】
0006508661.tif 000065
【０２７８】
図1乃至図13を参照すると、前述では、本発明の実施形態に係るデータ処理システムを詳細に説明する。図14および図17を参照すると、以下では、本発明の実施形態に係るデータ処理システムにおける計算ノードを詳細に説明する。
【０２７９】
図14は、本発明の実施形態に係る計算ノード500を示す。計算ノード500はデータ処理システムに属する。データ処理システムは管理ノードをさらに含む。計算ノード500は、
管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュール501と、
管理ノードによって割り当てられ、受信モジュール501によって受信された第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するように構成される取得モジュール502であって、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である、取得モジュール502と、
データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するように構成される処理モジュール503であって、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【０２８０】
【数６４】
0006508661.tif 000066
【０２８１】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０２８２】
【数６５】
0006508661.tif 000067
【０２８３】
であり、
【０２８４】
【数６６】
0006508661.tif 000068
【０２８５】
は
【０２８６】
【数６７】
0006508661.tif 000069
【０２８７】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である、処理モジュール503とを含む。
【０２８８】
任意で、実施形態では、計算ノードは、物理マシン、仮想マシンまたは中央処理装置CPUであり、これは、本発明の本実施形態では限定されない。
【０２８９】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０２９０】
図15は、本発明の実施形態に係る計算ノード600を示す。計算ノード600はデータ処理システムに属する。データ処理システムは管理ノードをさらに含む。計算ノードは、
管理ノードによって割り当てられた第1の処理タスクを受信するように構成される受信モジュール601と、
管理ノードによって割り当てられ、受信モジュール601によって受信された第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するように構成される取得モジュール602であって、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である、取得モジュール602と、
データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するように構成される処理モジュール603であって、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【０２９１】
【数６８】
0006508661.tif 000070
【０２９２】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【０２９３】
【数６９】
0006508661.tif 000071
【０２９４】
であり、
【０２９５】
【数７０】
0006508661.tif 000072
【０２９６】
は
【０２９７】
【数７１】
0006508661.tif 000073
【０２９８】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である、処理モジュール603とを含む。
【０２９９】
任意で、実施形態では、計算ノードは、物理マシン、仮想マシンまたは中央処理装置CPUであり、これは、本発明の本実施形態では限定されない。
【０３００】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３０１】
図16に示されるように、本発明の実施形態は計算ノード700をさらに提供する。計算ノード700は、プロセッサ701、メモリ702、バスシステム703およびトランシーバ704を含む。プロセッサ701、メモリ702およびトランシーバ704は、バスシステム703を使用することによって接続される。メモリ702は命令を記憶するように構成される。プロセッサ701は、メモリ702によって記憶された命令を実行するように構成される。トランシーバ704は、
管理ノードによって割り当てられた第1の処理タスクを受信し、
管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得するように構成され、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である。
【０３０２】
プロセッサ701は、
データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得するように構成され、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【０３０３】
【数７２】
0006508661.tif 000074
【０３０４】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０３０５】
【数７３】
0006508661.tif 000075
【０３０６】
であり、
【０３０７】
【数７４】
0006508661.tif 000076
【０３０８】
は
【０３０９】
【数７５】
0006508661.tif 000077
【０３１０】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である。
【０３１１】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３１２】
本発明の本実施形態では、プロセッサ701は中央処理装置（Central Processing Unit, CPU）であってよいことは理解されるべきである。プロセッサ701は、あるいは、別の汎用プロセッサ、デジタル信号プロセッサ（Digital Signal Processor, DSP）、特定用途向け集積回路（Application-Specific Integrated Circuit, ASIC）、フィールドプログラマブルゲートアレイ（Field-Programmable Gate Array, FPGA）または別のプログラマブル論理デバイス、離散ゲートまたはトランジスタ論理デバイス、離散ハードウェアコンポーネント等であってよい。汎用プロセッサはマイクロプロセッサであってよく、または、プロセッサは、任意の従来のプロセッサ等であってよい。
【０３１３】
メモリ702は、読出し専用メモリおよびランダムアクセスメモリを含み、且つ、プロセッサ701のための命令およびデータを提供してよい。メモリ702の一部は、不揮発性ランダムアクセスメモリをさらに含んでよい。例えば、メモリ702は、デバイスタイプに関する情報をさらに記憶してよい。
【０３１４】
データバスを含むことに加えて、バスシステム703は、電源バス、制御バス、ステータス信号バス等をさらに含んでよい。しかしながら、明確な説明のために、全ての種類のバスは、図内でバスシステム703としてマークされる。
【０３１５】
実施プロセスでは、前述の方法の全てのステップは、プロセッサ701におけるハードウェアの集積論理回路を使用することによって完了してよく、または、ソフトウェア形態で命令を使用することによって完了してよい。本発明の本実施形態を参照して開示される方法のステップは、ハードウェアプロセッサによって実行および完了されてよく、または、プロセッサにおけるハードウェアおよびソフトウェアモジュールの組合せを使用することによって実行および完了されてよい。ソフトウェアモジュールは、ランダムアクセスメモリ、フラッシュメモリ、読出し専用メモリ、プログラマブル読出し専用メモリ、電気的に消去可能なプログラマブルメモリまたはレジスタ等の当該技術で成熟した記憶媒体内に配置されてよい。記憶媒体はメモリ702内に配置される。プロセッサ701は、メモリ702内の情報を読み出し、プロセッサ701のハードウェアを参照して、前述の方法のステップを完了する。繰返しを回避するために、詳細はここではさらに繰り返されない。
【０３１６】
任意で、実施形態では、計算ノード700は、物理マシン、仮想マシンまたは中央処理装置CPUである。
【０３１７】
本発明の本実施形態における計算ノード700は、本発明の前述の実施形態における方法を実行するためのエンティティに対応してよく、または、本発明の前述の実施形態における計算ノード500に対応してよいことは理解されるべきである。加えて、計算ノード700のモジュールの前述のまたは他の操作および/または機能は、データ処理方法の対応する手順を実施するものである。簡潔さのために、詳細はここではさらに繰り返されない。
【０３１８】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３１９】
図17に示されるように、本発明の実施形態は計算ノード800をさらに提供する。計算ノード800は、プロセッサ801、メモリ802、バスシステム803およびトランシーバ804を含む。プロセッサ801、メモリ802およびトランシーバ804は、バスシステム803を使用することによって接続される。メモリ802は命令を記憶するように構成される。プロセッサ801は、メモリ802によって記憶された命令を実行するように構成される。トランシーバ804は、
管理ノードによって割り当てられた第1の処理タスクを受信し、
管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得するように構成され、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である。
【０３２０】
プロセッサ801は、
データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得するように構成され、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【０３２１】
【数７６】
0006508661.tif 000078
【０３２２】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【０３２３】
【数７７】
0006508661.tif 000079
【０３２４】
であり、
【０３２５】
【数７８】
0006508661.tif 000080
【０３２６】
は
【０３２７】
【数７９】
0006508661.tif 000081
【０３２８】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である。
【０３２９】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３３０】
本発明の本実施形態では、プロセッサ801は中央処理装置（Central Processing Unit, CPU）であってよいことは理解されるべきである。プロセッサ801は、あるいは、別の汎用プロセッサ、デジタル信号プロセッサ（Digital Signal Processor, DSP）、特定用途向け集積回路（Application-Specific Integrated Circuit, ASIC）、フィールドプログラマブルゲートアレイ（Field-Programmable Gate Array, FPGA）または別のプログラマブル論理デバイス、離散ゲートまたはトランジスタ論理デバイス、離散ハードウェアコンポーネント等であってよい。汎用プロセッサはマイクロプロセッサであってよく、または、プロセッサは、任意の従来のプロセッサ等であってよい。
【０３３１】
メモリ802は、読出し専用メモリおよびランダムアクセスメモリを含み、且つ、プロセッサ801のための命令およびデータを提供してよい。メモリ802の一部は、不揮発性ランダムアクセスメモリをさらに含んでよい。例えば、メモリ802は、デバイスタイプに関する情報をさらに記憶してよい。
【０３３２】
データバスを含むことに加えて、バスシステム803は、電源バス、制御バス、ステータス信号バス等をさらに含んでよい。しかしながら、明確な説明のために、全ての種類のバスは、図内でバスシステム803としてマークされる。
【０３３３】
実施プロセスでは、前述の方法の全てのステップは、プロセッサ801におけるハードウェアの集積論理回路を使用することによって完了してよく、または、ソフトウェア形態で命令を使用することによって完了してよい。本発明の本実施形態を参照して開示される方法のステップは、ハードウェアプロセッサによって実行および完了されてよく、または、プロセッサにおけるハードウェアおよびソフトウェアモジュールの組合せを使用することによって実行および完了されてよい。ソフトウェアモジュールは、ランダムアクセスメモリ、フラッシュメモリ、読出し専用メモリ、プログラマブル読出し専用メモリ、電気的に消去可能なプログラマブルメモリまたはレジスタ等の当該技術で成熟した記憶媒体内に配置されてよい。記憶媒体はメモリ802内に配置される。プロセッサ801は、メモリ802内の情報を読み出し、プロセッサ801のハードウェアを参照して、前述の方法のステップを完了する。繰返しを回避するために、詳細はここではさらに繰り返されない。
【０３３４】
任意で、実施形態では、計算ノード800は、物理マシン、仮想マシンまたは中央処理装置CPUである。
【０３３５】
本発明の本実施形態における計算ノード800は、本発明の前述の実施形態における方法を実行するためのエンティティに対応してよく、または、本発明の前述の実施形態における計算ノード600に対応してよいことは理解されるべきである。加えて、計算ノード800のモジュールの前述のまたは他の操作および/または機能は、データ処理方法の対応する手順を実施するものである。簡潔さのために、詳細はここではさらに繰り返されない。
【０３３６】
従って、本発明の本実施形態によって提供される計算ノードによると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３３７】
図1乃至図17を参照して、前述では、本発明の実施形態に係る、データ処理システムおよび計算ノードを詳細に説明する。図18および図19を参照して、以下では、本発明の実施形態に係るデータ処理方法を詳細に説明する。
【０３３８】
図18は、本発明の実施形態に係るデータ処理方法900を示す。方法900はデータ処理システムに適用される。データ処理システムは、管理ノードと第1のクラスの計算ノードとを含む。方法900は以下を含む：
【０３３９】
S901：管理ノードは、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当て、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理する。
【０３４０】
S902：計算ノードFCxは、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックMxおよびデータブロックV1xを取得し、ここで、データブロックMxは、m行n列のデータを含む行列であり、データブロックV1xは、n次元データを含むベクトルであり、mおよびnは正の整数であり、nの値は2以上である。
【０３４１】
S903：計算ノードFCxは、データブロックMxおよびデータブロックV1xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果V’xを取得し、ここで、第1の中間結果V’xは、m次元データを含むベクトルであり、第1の中間結果V’xは、要素
【０３４２】
【数８０】
0006508661.tif 000082
【０３４３】
を有し、ここで、iは変数であり、iの値は1からmの範囲であり、
【０３４４】
【数８１】
0006508661.tif 000083
【０３４５】
であり、
【０３４６】
【数８２】
0006508661.tif 000084
【０３４７】
は
【０３４８】
【数８３】
0006508661.tif 000085
【０３４９】
に従って取得され、mi,jは、データブロックMx内の要素であり、vjは、データブロックV1x内の要素であり、jは変数であり、jの値は1からnの範囲である。
【０３５０】
S904：管理ノードは、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得する。
【０３５１】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３５２】
任意で、実施形態では、データ処理システムは、第2のクラスの計算ノードをさらに含む。方法900は、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップであって、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
計算ノードSCyによって、第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するステップであって、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内の1行のデータブロックに従って取得された第1の中間結果である、ステップと、
計算ノードSCyによって、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果V’’yを取得するステップであって、ここで、第2の中間結果V’’yは、m次元データを含むベクトルである、ステップと、
管理ノードによって、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【０３５３】
任意で、実施形態では、データセットは、データブロックV2xをさらに含み、データブロックV2xは、m次元データを含むベクトルである。方法900は、
管理ノードによって、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップと、
計算ノードSCyによって、第3の処理タスクに従って、データセット内のデータブロックV2xを取得するステップと、
計算ノードSCyによって、SCyによって取得された第2の中間結果V’’yおよびデータブロックV2xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【０３５４】
任意で、実施形態では、m=nであり、データブロックV1xとデータブロックV2xは同じデータブロックである。
【０３５５】
任意で、実施形態では、第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、第2のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第2の処理タスクを同時に処理する。
【０３５６】
任意で、実施形態では、管理ノード、第1のクラスの計算ノードおよび第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUであってよい。
【０３５７】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３５８】
図19は、本発明の実施形態に係るデータ処理方法1000を示す。方法1000はデータ処理システムに適用される。データ処理システムは、管理ノードと第1のクラスの計算ノードとを含む。方法1000は以下を含む：
【０３５９】
S1001：管理ノードは、第1の処理タスクを、FCxを含み、第1のクラスの計算ノード内にある少なくとも2つの計算ノードに割り当て、ここで、FCxは少なくとも2つの計算ノード内の第xの計算ノードであり、xは正の整数であり、第1のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第1の処理タスクを同時に処理する。
【０３６０】
S1002：計算ノードFCxは、管理ノードによって割り当てられた第1の処理タスクに従って、処理されるべきデータセット内にあるデータブロックM1xおよびデータブロックM2xを取得し、ここで、データブロックM1xは、m行n列のデータを含む行列であり、データブロックM2xは、n行p列のデータを含む行列であり、m、nおよびpは正の整数であり、nの値は2以上である。
【０３６１】
S1003：計算ノードFCxは、データブロックM1xおよびデータブロックM2xに対して結合2（combine2）操作および削減2（reduce2）操作を実行して、第1の中間結果M’xを取得し、ここで、第1の中間結果M’xは、m行p列のデータを含む行列であり、第1の中間結果M’xは、要素
【０３６２】
【数８４】
0006508661.tif 000086
【０３６３】
を有し、ここで、iおよびjは変数であり、iの値は1からmの範囲であり、jの値は1からpの範囲であり、
【０３６４】
【数８５】
0006508661.tif 000087
【０３６５】
であり、
【０３６６】
【数８６】
0006508661.tif 000088
【０３６７】
は
【０３６８】
【数８７】
0006508661.tif 000089
【０３６９】
に従って取得され、m1[i,k]は、データブロックM1xの第i行第k列の要素であり、m2[k,j]は、データブロックM2xの第k行第j列の要素であり、kは変数であり、kの値は1からnの範囲である。
【０３７０】
S1004：管理ノードは、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、処理されるべきデータセットのための処理結果を取得する。
【０３７１】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３７２】
任意で、実施形態では、データ処理システムは、第2のクラスの計算ノードをさらに含む。方法1000は、
管理ノードによって、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果に従って、第2の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップであって、ここで、SCyは少なくとも1つの計算ノード内の第yの計算ノードであり、yは正の整数である、ステップと、
計算ノードSCyによって、第2の処理タスクに従って、第1のクラスの計算ノード内の少なくとも2つの計算ノードによって取得された第1の中間結果を取得するステップであって、ここで、SCyによって取得された第1の中間結果は、処理されるべきデータセット内にある1行のデータブロックM1xおよび1列のデータブロックM2xに従って取得された第1の中間結果である、ステップと、
計算ノードSCyによって、SCyによって取得された第1の中間結果に対してreduce2操作を実行して、第2の中間結果M’’yを取得するステップであって、ここで、第2の中間結果M’’yは、m行p列のデータを含む行列である、ステップと、
管理ノードによって、第2のクラスの計算ノード内の少なくとも1つの計算ノードによって取得された第2の中間結果に従って、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【０３７３】
任意で、実施形態では、データセットは、データブロックM3xをさらに含み、データブロックM3xは、m行p列のデータを含む行列である。方法1000は、
管理ノードによって、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードによって取得された第2の中間結果に従って、第3の処理タスクを、SCyを含み、第2のクラスの計算ノード内にある少なくとも1つの計算ノードに割り当てるステップと、
計算ノードSCyによって、第3の処理タスクに従って、データセット内のデータブロックM3xを取得するステップと、
計算ノードSCyによって、SCyによって取得された第2の中間結果M’’yおよびデータブロックM3xに対して、割り当てassign操作を実行して、処理されるべきデータセットのための処理結果を取得するステップとをさらに含む。
【０３７４】
任意で、実施形態では、n=mであり、データブロックM2xとデータブロックM3xは同じデータブロックである。
【０３７５】
任意で、実施形態では、n=pであり、データブロックM1xとデータブロックM3xは同じデータブロックである。
【０３７６】
任意で、実施形態では、第2のクラスの計算ノードが少なくとも2つの計算ノードを含むとき、第2のクラスの計算ノード内の少なくとも2つの計算ノードは、管理ノードによって割り当てられた第2の処理タスクを同時に処理する。
【０３７７】
任意で、実施形態では、管理ノード、第1のクラスの計算ノードおよび第2のクラスの計算ノードはそれぞれ、物理マシン、仮想マシンまたは中央処理装置CPUであってよい。
【０３７８】
従って、本発明の本実施形態によって提供されるデータ処理方法によると、データブロックに対して結合操作および削減操作が実行されているとき、削減操作が実行される前に、全ての結合操作を実行する必要はなく、代わりに、結合操作と削減操作は交替に実行され、その結果、計算によって占有されるメモリ空間は低減されることができ、且つ、計算時間は低減されることができる。
【０３７９】
当業者は、本明細書で開示された実施形態で説明された例と組み合わせて、ユニットおよびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェアまたはそれらの組合せによって実施されてよいことを認識することができる。ハードウェアとソフトウェアとの間の互換性を明確に説明するために、前述では、機能に基づく各例の構成およびステップを一般的に説明した。機能がハードウェアによって実行されるかソフトウェアによって実行されるかは、技術的解決手段の特定の適用および設計制約条件に依存する。当業者は、各特定の適用のために説明された機能を実施するために異なる方法を使用してよいが、実施は、本発明の範囲を超えると考えられるべきではない。
【０３８０】
便利且つ簡潔な説明を目的として、前述のシステム、装置およびユニットの詳細な動作プロセスのために、前述の方法の実施形態における対応するプロセスに対して参照が行われてよいことは当業者によって明確に理解されることができ、詳細はここでは再び説明されない。
【０３８１】
本発明の実施形態における技術は、必要な汎用ハードウェアプラットフォームに加えてソフトウェアによって実施されてよいことは、当業者は明確に理解することができる。このような理解に基づいて、本発明の技術的解決手段は本質的に、または、従来技術に貢献する部分は、または、技術的解決手段の全てまたは一部は、ソフトウェア製品の形態で実施されてよい。ソフトウェア製品は記憶媒体に記憶され、コンピュータデバイス（パーソナルコンピュータ、サーバまたはネットワークデバイスであってよい）に本発明の実施形態で説明された方法のステップの全てまたは一部を実行するように命令するためのいくつかの命令を含む。前述の記憶媒体は、USBフラッシュドライブ、リムーバブルハードディスク、磁気ディスク、光ディスク、ランダムアクセスメモリ（Random-Access Memory, RAM）、ソリッドステートディスク（Solid State Disk, SSD）または不揮発性メモリ（non-volatile memory）等のプログラムコードを記憶することができる任意の非一時的（non-transitory）機械可読媒体を含んでよい。前述の説明は、単に、本発明の具体的な実施形態であるが、本発明の保護範囲を限定するように意図されない。
【符号の説明】
【０３８２】
100  データ処理システム
110  管理ノード
120  第1のクラスの計算ノード
121  計算ノード
300  データ処理システム
310  管理ノード
320  第1のクラスの計算ノード
321  計算ノード
500  計算ノード
501  受信モジュール
502  取得モジュール
503  処理モジュール
600  計算ノード
601  受信モジュール
602  取得モジュール
603  処理モジュール
700  計算ノード
701  プロセッサ
702  メモリ
703  バスシステム
704  トランシーバ
800  計算ノード
801  プロセッサ
802  メモリ
803  バスシステム
804  トランシーバ
【図１】
0006508661.tif 000114
【図２】
0006508661.tif 000115
【図３Ａ】
0006508661.tif 000116
【図３Ｂ】
0006508661.tif 000117
【図４】
0006508661.tif 000118
【図５】
0006508661.tif 000119
【図６Ａ】
0006508661.tif 000120
【図６Ｂ】
0006508661.tif 000121
【図７】
0006508661.tif 000122
【図８】
0006508661.tif 000123
【図９】
0006508661.tif 000124
【図１０】
0006508661.tif 000125
【図１１】
0006508661.tif 000126
【図１２】
0006508661.tif 000127
【図１３】
0006508661.tif 000128
【図１４】
0006508661.tif 000129
【図１５】
0006508661.tif 000130
【図１６】
0006508661.tif 000131
【図１７】
0006508661.tif 000132
【図１８】
0006508661.tif 000133
【図１９】
0006508661.tif 000134