(57)【要約】【課題】本発明は、通信回数を増やすことなく、演算装置間のネットワークの通信路の数を少なくすることを目的とする。【解決手段】本発明の並列演算方法は、Ｎ個の演算装置がバラバラに記録しているＫ次元のベクトルの和を、リング状のネットワークを利用して計算し、結果をＮ個の演算装置で共有する。具体的には、Ｋ個の成分をＮ個のグループに分け、各演算装置は、１つのグループの成分を隣の演算装置に渡す。受け取った演算装置は自分が保有する当該グループの成分との和を求め、その結果を次の演算装置に渡す。この作業をＮ−１回行い、Ｎ回目からは受け取った演算装置は、当該グループの成分の和として記録すると共に、そのデータを次の演算装置に渡す。この作業を２Ｎ−２回目まで行う。【選択図】図６
2008090769.tif 000002
【特許請求の範囲】
【請求項１】
計算部と記録部と通信部とを有するＮ個の演算装置（Ｎは２以上の整数）を用いてＮ個のＮ次元のベクトルの和を求める並列演算方法であって、
各演算装置が、演算の対象となるＮ次元のベクトルを１つずつ当該演算装置の記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
ｎ番目の演算装置（ｎは１からＮの整数）が、第（ｎ−１＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、通信部の送信手段を用いて（ｎ−２（ｍｏｄ  Ｎ））＋１番目の演算装置に送信する成分送信ステップと、
ｎ番目の演算装置が、通信部の受信手段を用いて第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分をｎ（ｍｏｄ  Ｎ））＋１番目の演算装置から受信する成分受信ステップと、
ｎ番目の演算装置が、（１）τ≦Ｎ−２の場合は、記録部のベクトル記録手段から、第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分との和を求め、結果を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有する並列演算方法。
【請求項２】
計算部と記録部と通信部とを有するＮ個の演算装置（Ｎは２以上の整数）を用いてＮ個のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算方法であって、
あらかじめ、ベクトルのＫ個の成分をＮ個のグループ（１番目のグループからＮ番目のグループ）に分けておき、
各演算装置が、演算の対象となるＫ次元のベクトルを１つずつ当該演算装置の記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
（ｎ−１−τ（ｍｏｄ  Ｎ））＋１番目の各演算装置（ｎは１からＮの整数。）が、（１）当該演算装置の記録部からｎ番目のグループのベクトルの成分を取り出し、（２）当該演算装置の通信部を用いて（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の演算装置に送信する成分送信ステップと、
（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の各演算装置が、当該演算装置の通信部を用いてｎ番目のグループのベクトルの成分を（ｎ−１−τ（ｍｏｄ  Ｎ））＋１番目の演算装置から受信する成分受信ステップと、
（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からｎ番目のグループのベクトルの成分を取り出し、当該演算装置の計算部で、受信したｎ番目のグループのベクトルの成分との和を求め、結果をｎ番目のグループのベクトルの成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、受信したｎ番目のグループのベクトルの成分を、ｎ番目のグループのベクトルの成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有する並列演算方法。
【請求項３】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算方法であって、
各演算装置が、演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を当該演算装置の記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信する成分送信ステップと、
ベクトルｃｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置からそれぞれ受信する成分受信ステップと、
ベクトルｃｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からベクトルｃｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｐの第ｎ成分を、ベクトルｃｑの第ｎ成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有し、ベクトルｃｘ（ｘは、１からＮの任意の整数）をベクトルの和とする並列演算方法。
【請求項４】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算方法であって、
各演算装置が、演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を当該演算装置の記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）τ≦Ｎ−２のときは、当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信し、（３）τ＞Ｎ−２のときは、当該演算装置とベクトルｃｒ（ｒはｐ＋１。ただし、ｐ＝Ｎのときはｒ＝１）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｒを記録部に有する演算装置に送信する成分送信ステップと、
・  （１）τ≦Ｎ−２の場合は、ベクトルｃｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置からそれぞれ受信し、（２）τ＞Ｎ−２の場合は、ベクトルｃｒを記録部に有する各演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置からそれぞれ受信する成分受信ステップと、
（１）τ≦Ｎ−２の場合は、ベクトルｃｑを記録部に有する各演算装置が、当該演算装置の記録部からベクトルｃｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｒを記録部に有する各演算装置が、ベクトルｃｐの第ｎ成分を、ベクトルｃｒの第ｎ成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有し、ベクトルｃｘ（ｘは、１からＮの任意の整数）をベクトルの和とする並列演算方法。
【請求項５】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算方法であって、
各演算装置が、演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を当該演算装置の記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）少なくともτ≦Ｎ−２のときは、当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信する成分送信ステップと、
少なくともτ≦Ｎ−２の場合は、ベクトルｃｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置からそれぞれ受信する成分受信ステップと、
少なくともτ≦Ｎ−２の場合は、ベクトルｃｑを記録部に有する各演算装置が、当該演算装置の記録部からベクトルｃｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、少なくともτがＮ−２以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有し、ベクトルｃｘ（ｘは、１からＮの任意の整数）をベクトルの和とする並列演算方法。
【請求項６】
計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）とＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＢを求める並列演算方法であって、
あらかじめ、行列ＡのＭＮ個の成分ａｍｎ（ｍは１からＭまでの整数、ｎは１からＮまでの整数）をＩ個のグループ（１番目のグループからＩ番目のグループ）に分けておき、
各演算装置が、ｉ番目のグループのすべての成分ａｍｎ（ただし、ｉは当該演算装置の番号であって、１からＩの整数）と、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを当該演算装置の記録部に記録する成分記録ステップと、
各演算装置が、（１）記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｂｎ１〜ａｍｎｂｎＫを計算し、（２）結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録部に記録するベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録する初期設定ステップと、
ベクトルｃｍｐ（ｍは１からＭ、ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｍｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｍｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑを記録部に有する演算装置に送信する成分送信ステップと、
ベクトルｃｍｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｍｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｐを記録部に有する演算装置からそれぞれ受信する成分受信ステップと、
ベクトルｃｍｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からベクトルｃｍｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｍｐの第ｎ成分との和を求め、結果をベクトルｃｍｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑの第ｎ成分として記録部に記録する演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る繰り返しステップと、
を有し、ベクトルｃｍｘ（ｘは、１からＮの任意の整数）を積ＡＢのＭ行目のベクトルとする並列演算方法。
【請求項７】
計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）と行列Ａの転置行列ＡＴとＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＴＡＢを求める並列演算方法であって、
あらかじめ、行列ＡのＭＮ個の成分ａｍｎ（ｍは１からＭまでの整数、ｎは１からＮまでの整数）をＩ個のグループ（１番目のグループからＩ番目のグループ）に分けておき、
各演算装置が、ｉ番目のグループのすべての成分ａｍｎ（ただし、ｉは当該演算装置の番号であって、１からＩの整数）と、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを当該演算装置の記録部に記録する成分記録ステップと、
各演算装置が、（１）記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｂｎ１〜ａｍｎｂｎＫを計算し、（２）結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録部に記録するＡベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録するＡ初期設定ステップと、
ベクトルｃｍｐ（ｍは１からＭ、ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｍｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｍｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑを記録部に有する演算装置に送信するＡ成分送信ステップと、
ベクトルｃｍｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｍｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｐを記録部に有する演算装置からそれぞれ受信するＡ成分受信ステップと、
ベクトルｃｍｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からベクトルｃｍｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｍｐの第ｎ成分との和を求め、結果をベクトルｃｍｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑの第ｎ成分として記録部に記録するＡ演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するＡτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻るＡ繰り返しステップと、
各演算装置が、（１）記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｃｍ１〜ａｍｎｃｍＫを計算し、（２）結果をＫ次元のベクトルｂｎｍ＝（ｂｎｍ１，ｂｎｍ２，…，ｂｎｍＫ）＝（ａｍｎｃｍ１，ａｍｎｃｍ２，…，ａｍｎｃｍＫ）として記録部に記録するＡＴベクトル記録ステップと、
各演算装置が、記録部にτ＝０を記録するＡＴ初期設定ステップと、
ベクトルｂｎｐ（ｎは１からＮ、ｐは（ｎ−１−τ（ｍｏｄ  Ｍ）＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｂｎｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｂｎｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｍ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑを記録部に有する演算装置に送信するＡＴ成分送信ステップと、
ベクトルｂｎｑを記録部に有する各演算装置が、当該演算装置とベクトルｂｎｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｐを記録部に有する演算装置からそれぞれ受信するＡＴ成分受信ステップと、
ベクトルｂｎｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からベクトルｂｎｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｂｎｐの第ｎ成分との和を求め、結果をベクトルｂｎｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑの第ｎ成分として記録部に記録するＡＴ演算結果記録ステップと、
各演算装置が、τにτ＋１を代入して記録部に記録するＡＴτ増加ステップと、
各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻るＡＴ繰り返しステップと、
を有し、ベクトルｂｎｘ（ｘは、１からＭの任意の整数）を積ＡＴＡＢのＮ行目のベクトルとする並列演算方法。
【請求項８】
請求項７記載の並列演算方法であって、
積ＡＴＡＢの演算によって求められた前記ベクトルｂｎｘをＮ行目とするＮ行Ｋ列の行列を行列Ｂとして、前記Ａベクトル記録ステップから前記ＡＴ繰り返しステップまでを繰り返すこと
を特徴とする並列演算方法。
【請求項９】
計算部と記録部と通信部とを有するＮ個の演算装置（Ｎは２以上の整数）を用いてＮ個のＮ次元のベクトルの和を求める並列演算システムを構成するｎ番目の演算装置（ｎは１からＮの整数）であって、
演算の対象となるＮ次元のベクトルを１つ記録する記録部内のベクトル記録手段と、
τの値を記録する記録部内のτ記録手段と、
第（ｎ−１＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、（ｎ−２（ｍｏｄ  Ｎ））＋１番目の演算装置に送信する通信部の送信手段と、
第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分をｎ（ｍｏｄ  Ｎ））＋１番目の演算装置から受信する受信手段と、
（１）τ≦Ｎ−２の場合は、記録部のベクトル記録手段から、第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分との和を求め、結果を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部に記録する演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１０】
計算部と記録部と通信部とを有するＮ個の演算装置（Ｎは２以上の整数）を用いてＮ個のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算システムを構成する演算装置であって、
あらかじめ、ベクトルのＫ個の成分をＮ個のグループ（１番目のグループからＮ番目のグループ）に分けておき、
演算の対象となるＫ次元のベクトルを１つ記録部に記録するベクトル記録手段と、
τの値を記録する記録部内のτ記録手段と、
あるｎ（ｎは１からＮの整数）に対して、当該演算装置の番号が（ｎ−１−τ（ｍｏｄ  Ｎ））＋１の場合、（１）記録部からｎ番目のグループのベクトルの成分を取り出し、（２）（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の演算装置に送信する通信部の送信手段と、
あるｎに対して、当該演算装置の番号が（ｎ−２−τ（ｍｏｄ  Ｎ））＋１の場合、ｎ番目のグループのベクトルの成分を（ｎ−１−τ（ｍｏｄ  Ｎ））＋１番目の演算装置から受信する通信部の受信手段と、
あるｎに対して、当該演算装置の番号が（ｎ−２−τ（ｍｏｄ  Ｎ））＋１の場合、（１）τ≦Ｎ−２のときは、記録部のベクトル記録手段からｎ番目のグループのベクトルの成分を取り出し、受信したｎ番目のグループのベクトルの成分との和を求め、結果をｎ番目のグループのベクトルの成分として記録部に記録し、（２）τ＞Ｎ−２のときは、受信したｎ番目のグループのベクトルの成分を、ｎ番目のグループのベクトルの成分として記録部に記録する演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１１】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算システムを構成する演算装置であって、
演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を記録する記録部内のベクトル記録手段と、
τの値を記録する記録部内のτ記録手段と、
あるｎに対してベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する場合に、（１）記録部のベクトル記録手段からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置が異なる場合には、ベクトルｃｑを記録部に有する演算装置に送信する通信部内の送信手段と、
あるｎに対してベクトルｃｑを記録部に有し、かつ、ベクトルｃｐを記録部に有する演算装置と異なる場合には、ベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する通信部内の受信手段と、
あるｎに対してベクトルｃｑを記録部に有する場合に、（１）τ≦Ｎ−２のときは、記録部のベクトル記録手段からベクトルｃｑの第ｎ成分を取り出し、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部のベクトル記録手段に記録し、（２）τ＞Ｎ−２のときは、ベクトルｃｐの第ｎ成分を、ベクトルｃｑの第ｎ成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１２】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算システムを構成する演算装置であって、
演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を記録する記録部内のベクトル記録手段と、
τの値を記録する記録部内のτ記録手段と、
あるｎに対してベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する場合に、（１）記録部のベクトル記録手段からベクトルｃｐの第ｎ成分を取り出し、（２）τ≦Ｎ−２のときは、当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置が異なる場合には、ベクトルｃｑを記録部に有する演算装置に送信し、（３）τ＞Ｎ−２のときは、当該演算装置とベクトルｃｒ（ｒはｐ＋１。ただし、ｐ＝Ｎのときはｒ＝１）を記録部に有する演算装置が異なる場合には、ベクトルｃｑを記録部に有する演算装置に送信する通信部内の送信手段と、
（１）τ≦Ｎ−２のときは、あるｎに対してベクトルｃｑを記録部に有し、かつ、ベクトルｃｐを記録部に有する演算装置と異なる場合には、ベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信し、（２）τ＞Ｎ−２のときは、あるｎに対してベクトルｃｒを記録部に有し、かつ、ベクトルｃｐを記録部に有する演算装置と異なる場合には、ベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する通信部内の受信手段と、
（１）τ≦Ｎ−２のときは、あるｎに対してベクトルｃｑを記録部に有する場合に、記録部のベクトル記録手段からベクトルｃｑの第ｎ成分を取り出し、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部のベクトル記録手段に記録し、  （２）τ＞Ｎ−２のときは、あるｎに対してベクトルｃｒを記録部に有する場合に、ベクトルｃｐの第ｎ成分を、ベクトルｃｒの第ｎ成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１３】
計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算システムを構成する演算装置であって、
演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を記録する記録部内のベクトル記録手段と、
τの値を記録する記録部内のτ記録手段と、
あるｎに対してベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する場合に、（１）記録部のベクトル記録手段からベクトルｃｐの第ｎ成分を取り出し、（２）少なくともτ≦Ｎ−２のときは、当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置が異なる場合には、ベクトルｃｑを記録部に有する演算装置に送信する通信部内の送信手段と、
少なくともτ≦Ｎ−２のときは、あるｎに対してベクトルｃｑを記録部に有し、かつ、ベクトルｃｐを記録部に有する演算装置と異なる場合には、ベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する通信部内の受信手段と、
少なくともτ≦Ｎ−２のときは、あるｎに対してベクトルｃｑを記録部に有する場合に、記録部のベクトル記録手段からベクトルｃｑの第ｎ成分を取り出し、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
少なくともτがＮ−２以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１４】
計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）とＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＢを求める並列演算システムを構成する演算装置であって、
演算の対象となる行列Ａのすべての成分ａｍｎと、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを記録する記録部内の成分記録手段と、
記録部の成分記録手段に記録された成分ａｍｎのそれぞれについて、ａｍｎｂｎ１〜ａｍｎｂｎＫを計算する計算部内の成分計算手段と、
結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録する記録部内のベクトル記録手段と、
τ＝０を記録する記録部内のτ記録手段と、
あるｎに対してベクトルｃｍｐ（ｍは１からＭ、ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する場合に、（１）記録部のベクトル記録手段からベクトルｃｍｐの第ｎ成分を取り出し、（２）ベクトルｃｍｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑを記録部に有する演算装置に送信する通信部内の送信手段と、
あるｎに対してベクトルｃｍｑを記録部に有し、かつ、ベクトルｃｍｐを記録部に有する演算装置と異なる場合には、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｐを記録部に有する演算装置から受信する通信部内の受信手段と、
あるｎに対してベクトルｃｍｑを記録部に有する場合に、（１）τ≦Ｎ−２のときは、記録部のベクトル記録手段からベクトルｃｍｑの第ｎ成分を取り出し、ベクトルｃｍｐの第ｎ成分との和を求め、結果をベクトルｃｍｑの第ｎ成分として記録部のベクトル記録手段に記録し、（２）τ＞Ｎ−２のときは、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑの第ｎ成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させる繰り返し手段と、
を備える演算装置。
【請求項１５】
計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）と行列Ａの転置行列ＡＴとＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＴＡＢを求める並列演算システムを構成する演算装置であって、
演算の対象となる行列Ａのすべての成分ａｍｎと、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを記録する記録部内の成分記録手段と、
記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｂｎ１〜ａｍｎｂｎＫを計算する計算部内のＡ成分計算手段と、
結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録する記録部内のＡベクトル記録手段と、
τ＝０を記録する記録部内のＡτ記録手段と、
あるｎに対してベクトルｃｍｐ（ｍは１からＭ、ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する場合に、（１）記録部のＡベクトル記録手段からベクトルｃｍｐの第ｎ成分を取り出し、（２）ベクトルｃｍｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑを記録部に有する演算装置に送信する通信部内のＡ送信手段と、
あるｎに対してベクトルｃｍｑを記録部に有し、かつ、ベクトルｃｍｐを記録部に有する演算装置と異なる場合には、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｐを記録部に有する演算装置から受信する通信部内のＡ受信手段と、
あるｎに対してベクトルｃｍｑを記録部に有する場合に、（１）τ≦Ｎ−２のときは、記録部のＡベクトル記録手段からベクトルｃｍｑの第ｎ成分を取り出し、ベクトルｃｍｐの第ｎ成分との和を求め、結果をベクトルｃｍｑの第ｎ成分として記録部のＡベクトル記録手段に記録し、（２）τ＞Ｎ−２のときは、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑの第ｎ成分として記録部のＡベクトル記録手段に記録する計算部のＡ演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するＡτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させるＡ繰り返し手段と、
記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｃｍ１〜ａｍｎｃｍＫを計算する計算部内のＡＴ成分計算手段と、
結果をＫ次元のベクトルｂｎｍ＝（ｂｎｍ１，ｂｎｍ２，…，ｂｎｍＫ）＝（ａｍｎｃｍ１，ａｍｎｃｍ２，…，ａｍｎｃｍＫ）として記録する記録部内のＡＴベクトル記録手段と、
τ＝０を記録する記録部内のＡＴτ記録手段と、
あるｎに対してベクトルｂｎｐ（ｎは１からＮ、ｐは（ｎ−１−τ（ｍｏｄ  Ｍ））＋１）を記録部に有する場合に、（１）記録部のＡＴベクトル記録手段からベクトルｂｎｐの第ｎ成分を取り出し、（２）ベクトルｂｎｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｍ）を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑを記録部に有する演算装置に送信する通信部内のＡＴ送信手段と、
あるｎに対してベクトルｂｎｑを記録部に有し、かつ、ベクトルｂｎｐを記録部に有する演算装置と異なる場合には、ベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｐを記録部に有する演算装置から受信する通信部内のＡＴ受信手段と、
あるｎに対してベクトルｂｎｑを記録部に有する場合に、（１）τ≦Ｎ−２のときは、記録部のＡＴベクトル記録手段からベクトルｂｎｑの第ｎ成分を取り出し、ベクトルｂｎｐの第ｎ成分との和を求め、結果をベクトルｂｎｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２のときは、ベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑの第ｎ成分として記録部のＡＴベクトル記録手段に記録するＡＴ演算結果記録手段と、
τにτ＋１を代入して記録部のτ記録手段に記録するＡＴτ増加手段と、
τが２Ｎ−３以下の場合は、演算を繰り返させるＡＴ繰り返し手段と、
を備える演算装置。
【請求項１６】
請求項１５記載の演算装置であって、
積ＡＴＡＢの演算によって求められた前記ベクトルｂｎｘをＮ行目とするＮ行Ｋ列の行列を行列Ｂとして、前記Ａベクトル記録ステップから前記ＡＴ繰り返しステップまでを繰り返すＡＴＡＢ計算繰り返し手段も
備えることを特徴とする演算装置。
【請求項１７】
請求項１から８のいずれかに記載の演算方法の各ステップを、コンピュータにより実現させる演算装置用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の演算装置を用いてベクトルの和もしくは行列の積を求める並列演算方法、演算装置、演算装置用プログラムに関する。
【背景技術】
【０００２】
ベクトルの和を求める演算や行列の積を求める演算は、多くの情報処理で行われている。例えば、セキュリティ関連では、素因数分解の難しさが、いくつかの公開鍵暗号、電子署名などに利用され、暗号解読の難しさの根拠となっているため、素因数分解がどれだけのリソースで可能かを調べることは、暗号方式の安全性評価として重要である。このような素因数分解の難しさの評価は、複数の演算装置を用いて行われ、その処理の中に、行列の積を求める過程が含まれている。また、行列の積を求める過程にはベクトルの和を求める過程が含まれている。
【０００３】
代表的な素因数分解の手法としては、数体ふるい法がある。数体ふるい法の線形代数部で扱う行列は、巨大であることに加え、０以外の成分の割合が極端に小さい、いわゆる疎行列であるため、ガウスの消去法などの通常の線型方程式に対する解法では、明らかに効率が悪い。このような行列に対する効率的なアルゴリズムとしてBlock Lanczos法が知られている。なお、数体ふるい法におけるBlock Lanczos法は、非特許文献１に具体的に示されており、この方法の処理の中には、疎行列とその行列の転置行列を繰り返し乗算する演算が含まれている。
【０００４】
Ｎ個の演算装置（Ｎは２以上の整数）がそれぞれＫ次元のベクトル（Ｋは２以上の整数）を記録している場合に、それらのベクトルの和を求める最も単純な方法は、ある１つの演算装置（親演算装置）に他のすべての演算装置がベクトルの情報を送り、親演算装置がベクトルの和を求める方法である。なお、すべての演算装置でベクトルの和の結果を共有する必要があるときは、親演算装置が他のすべての演算装置に、結果を送る。この方法の場合、（Ｎ−１）個の演算装置が、Ｋ個ずつのベクトルの要素を、送受信するので、２Ｋ（Ｎ−１）回の通信が必要である。この方法の場合、親演算装置と他のすべての演算装置との間に通信路が必要であり、通信路に流れる情報は常に片方向にのみ送られているので、半二重の（Ｎ−１）個の通信路（スター型）を有するネットワークを構築する必要がある。
【０００５】
非特許文献１では、上述のベクトルの和を求める方法を改良した方法が示されている。非特許文献１の方法を実現するシステム構成（Ｎ＝４の場合）を図１に示す。図２は情報の収集の様子、図３は情報の分配の様子を示す。この方法では、各演算装置９０００、９１００、９２００、９３００は、計算部９０１０、９１１０、９２１０、９３１０と記録部９０２０、９１２０、９２２０、９３２０と通信部９０３０、９１３０、９２３０、９３３０とを備えており、各演算装置９０００、９１００、９２００、９３００は、他の演算装置との間に通信路を有している。
【０００６】
Ｎ個の演算装置（Ｎは２以上の整数）がそれぞれＫ次元のベクトル（Ｋは２以上の整数）を記録している場合に、あらかじめＫ個の要素をＮ個のグループに分ける。ここで、各グループの要素の数を、［Ｋ／Ｎ］と｛Ｋ／Ｎ｝に揃えると効率がよい。ただし、本明細書内では［ｘ］は実数ｘ以下の最大の整数、｛ｘ｝は実数ｘ以上の最小の整数を示す。ＫがＮの倍数の時には、すべてのグループが同じ要素の数Ｋ／Ｎとなる。また、Ｋ＜Ｎの場合には、いくつかのグループは要素の数が０となる。ｎ番目の演算装置以外の演算装置（ｎは１以上Ｎ以下の整数）は、当該演算装置が記録するベクトルのｎ番目のグループに属する要素を、ｎ番目の演算装置に送る。図２は、Ｎ＝４の場合の情報の収集の様子を示している。ｎ番目の演算装置では、ｎ番目のグループに属する要素ごとに和を求め、それぞれの要素の和を、他の演算装置に送る。図３は、Ｎ＝４の場合の情報の分配の様子を示している。このように情報の収集と分配を行うと、最大で２｛Ｋ／Ｎ｝(Ｎ−１）回の通信が必要となる。この方法の場合、単純な方法よりも通信の回数は大きく減っている。しかし、すべての演算装置間に通信路が必要であり、通信路では双方向に情報が送られることになる。つまり、Ｎ（Ｎ−１）／２個の全二重の通信路（すべての演算装置の間で完全グラフ）を有するネットワークが必要である。
【非特許文献１】下山武司、青木和麻呂、植田広樹、木田祐司“一般数体篩法実装実験（４）−線形代数”、電子情報通信学会技術研究報告、ISEC2003-154、2004．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来の技術では、複数の演算装置に記録されているベクトルの和を求め、結果をそれらの演算装置で共有する場合に、通信回数が多くなるか、通信路が多くなるという問題があった。複数の演算装置を用いてベクトルの和を求める並列演算および行列の積を求める並列演算で、通信回数を少なくすることと、演算装置間のネットワークの通信路の数を少なくすることを、本発明の目的とする。
【課題を解決するための手段】
【０００８】
本発明の並列演算方法は、以下のステップによって、計算部と記録部と通信部とを有する複数の演算装置を用いてＮ個（Ｎは２以上の整数）のＫ次元のベクトル（Ｋは２以上の整数）の和を求める。
【０００９】
ベクトル記録ステップで、各演算装置が、演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を当該演算装置の記録部に記録する。
初期設定ステップで、各演算装置が、記録部にτ＝０を記録する。
成分送信ステップで、ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ）＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信する。
【００１０】
成分受信ステップで、ベクトルｃｑを記録部に有する各演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する。
【００１１】
演算結果記録ステップで、ベクトルｃｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、記録部からベクトルｃｑの第ｎ成分を取り出し、計算部でベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｐの第ｎ成分を、ベクトルｃｑの第ｎ成分として記録部に記録する。
τ増加ステップで、各演算装置が、τにτ＋１を代入して記録部に記録する。
繰り返しステップで、各演算装置が、τが２Ｎ−３以下の場合は、成分送信ステップに戻る。
そして、各演算装置の記録部に記録されたベクトルｃｍｘ（ｘは、１からＮの任意の整数）をベクトルの和とする。
【００１２】
なお、Ｋ次元のベクトルを１つずつ各演算装置に記録した場合は、ベクトルｃｑを記録部に有する演算装置は、必ずベクトルｃｐを記録部に有する演算装置と異なるので、処理が少し簡単になる。
【００１３】
また、本発明の並列演算方法は、計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）とＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＢを求める場合にも適用できる。この場合は、あらかじめ、行列ＡのＭＮ個の成分ａｍｎ（ｍは１からＭまでの整数、ｎは１からＮまでの整数）をＩ個のグループ（１番目のグループからＩ番目のグループ）に分けておく。そして、各演算装置は、ｉ番目のグループのすべての成分ａｍｎ（ただし、ｉは当該演算装置の番号であって、１からＩの整数）と、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを当該演算装置の記録部に記録する成分記録ステップを最初に行う。  ベクトル記録ステップでは、各演算装置が、（１）記録部に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｂｎ１〜ａｍｎｂｎＫを計算し、（２）結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録部に記録する。ＭＮ個のＫ次元のベクトルｃｍｎが、ベクトルの和を求める方法でもＫ次元のベクトルに相当する。この後のステップでは、Ｍ組のＮ個のベクトルの和を求める並列演算を行う。
【００１４】
さらに、本発明の並列演算方法は、計算部と記録部と通信部とを有するＩ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）と行列Ａの転置行列ＡＴとＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＴＡＢを求める場合にも適用できる。積ＡＢを求めるまでは、上述の方法と同じである。転置行列ＡＴを掛ける際には、行列ＡＴのｎ行ｍ列の成分の演算を行う演算装置を、積ＡＢの演算で、行列Ａのｍ行ｎ列の成分の演算を行った演算装置と同一にする。
【発明の効果】
【００１５】
本発明によれば、１組のＮ個のＫ次元のベクトルの和をＮ個の演算装置で行う場合、最大で２｛Ｋ／Ｎ｝（Ｎ−１）回の通信で、情報の収集と結果の分配が実現できる。また、データはリング状かつ片方向に送られるため、Ｎ個の片方向通信路（リング状）を有するネットワークを備えればよい。これは、単純な方法の、２Ｋ（Ｎ−１）回の通信回数、半二重の（Ｎ−１）個の通信路に比べ、大幅に通信回数を削減している。また、非特許文献１の方法の、最大で２｛Ｋ／Ｎ｝(Ｎ−１）回の通信回数、Ｎ（Ｎ−１）／２個の全二重の通信路に比べ、大幅に通信路を削減している。
【００１６】
また、同様に、Ｉ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）とＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＢを求める場合にも、Ｍ組のＮ個のベクトルの和を求める場合に、通信回数と通信路を大幅に削減できる。
【００１７】
さらに、行列の積ＡＴＡＢを求める場合には、転置行列ＡＴを掛ける演算では、行列ＡＢのｍ行目の各成分（ｍ行目のベクトル）の情報が必要であるが、この情報は、積ＡＢの演算で、行列Ａのｍ行目の成分の演算を行った演算装置が記録している情報である。本発明によれば、転置行列ＡＴを掛ける際には、行列ＡＴのｎ行ｍ列の成分の演算を行う演算装置を、積ＡＢの演算で、行列Ａのｍ行ｎ列の成分の演算を行った演算装置と同一にするので、転置行列ＡＴを掛ける演算の前に、情報を授受するための通信が不要である。したがって、通信回数と通信路を大幅に削減できる。
【発明を実施するための最良の形態】
【００１８】
以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。
［第１実施形態］
図４に、Ｎ個の演算装置（Ｎ＝４）を用いてＫ次元のベクトル（Ｋは２以上の整数）の和を求める並列演算システムの構成例を示す。この並列演算システムは、演算装置１０００、１１００、１２００、１３００と、隣り合う演算装置とをつなぐ通信路から構成されている。各演算装置１０００、１１００、１２００、１３００は、計算部１０１０、１１１０、１２１０、１３１０と記録部１０２０、１１２０、１２２０、１３２０と通信部１０３０、１１３０、１２３０、１３３０とを備えている。図５に演算装置１０００の機能構成例を示す。計算部１０１０は、τ増加手段１００１と繰り返し手段１００２と演算結果記録手段１０１２とを備える。なお、τ増加手段１００１と繰り返し手段１００２は、計算部１０１０以外の構成部（たとえば、図示していないが制御部などの構成部が考えられる。）が備えてもよい。記録部１０２０は、ベクトル記録手段１０２２とτ記録手段１０２３とを有する。通信部１０３０は、送信手段１０３１と受信手段１０３２とを有する。なお、他の演算装置１１００、１２００、１３００も同じ機能構成である。
【００１９】
原理１
図６に、図４の並列演算システムを用いて４個の４次元ベクトルの和を求める方法の原理を示す。図中の○内の数字ｘは、処理の順番を示しており、以下では第ｘの処理と表現する。なお、同じ番号は同時に（並列に）行う処理を示している。あらかじめ、演算装置１０００がベクトルｃ１を、演算装置１１００がベクトルｃ２を、演算装置１２００がベクトルｃ３を、演算装置１３００がベクトルｃ４を記録している。
【００２０】
第１の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ１の第１成分ｃ１１を演算装置１３００に送信するとともに、ベクトルｃ２の第２成分ｃ２１を演算装置１１００から受信する。演算装置１１００は、ベクトルｃ２の第２成分ｃ２２を演算装置１０００に送信するとともに、ベクトルｃ３の第３成分ｃ３３を演算装置１２００から受信する。演算装置１２００は、ベクトルｃ３の第３成分ｃ３３を演算装置１１００に送信するとともに、ベクトルｃ４の第４成分ｃ４４を演算装置１３００から受信する。演算装置１３００は、ベクトルｃ４の第４成分ｃ４４を演算装置１２００に送信するとともに、ベクトルｃ１の第１成分ｃ１１を演算装置１０００から受信する。
【００２１】
第２の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ１の第２成分ｃ１２と受信したベクトルｃ２の第２成分ｃ２２との和を、ベクトルｃ１の第２成分ｃ１２として記録する。演算装置１１００は、ベクトルｃ２の第３成分ｃ２３と受信したベクトルｃ３の第３成分ｃ３３との和を、ベクトルｃ２の第３成分ｃ２３として記録する。演算装置１２００は、ベクトルｃ３の第４成分ｃ３４と受信したベクトルｃ４の第４成分ｃ４４との和を、ベクトルｃ３の第４成分ｃ３４として記録する。演算装置１３００は、ベクトルｃ４の第１成分ｃ４１と受信したベクトルｃ１の第１成分ｃ１１との和を、ベクトルｃ４の第１成分ｃ４１として記録する。
【００２２】
第１の処理と第２の処理によって、演算前のベクトルｃ４とベクトルｃ１の第１成分の合計ｃ４１＋ｃ１１が、演算装置１３００にベクトルｃ４の第１成分として記録されている。第３の処理から第６の処理は、第１の処理と第２の処理の繰り返しである。第３の処理と第４の処理が終了すると、演算前のベクトルｃ３とベクトルｃ４とベクトルｃ１の第１成分の合計ｃ３１＋ｃ４１＋ｃ１１が、演算装置１２００にベクトルｃ３の第１成分として記録される。第５の処理と第６の処理が終了すると、演算前のベクトルｃ２とベクトルｃ３とベクトルｃ４とベクトルｃ１の第１成分の合計ｃ２１＋ｃ３１＋ｃ４１＋ｃ１１が、演算装置１１００にベクトルｃ２の第１成分として記録される。つまり、第６の処理までで、ベクトルの各成分の合計は求められている。ただし、第１成分の合計は演算装置１１００、第２成分の合計は演算装置１２００、第３成分の合計は演算装置１３００、第４成分の合計は演算装置１０００がそれぞれ記録している。
【００２３】
第７の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ１の第４成分ｃ１４（第４成分の合計）を演算装置１３００に送信するとともに、ベクトルｃ２の第１成分ｃ２１（第１成分の合計）を演算装置１１００から受信する。演算装置１１００は、ベクトルｃ２の第１成分ｃ２１（第１成分の合計）を演算装置１０００に送信するとともに、ベクトルｃ３の第２成分ｃ３２（第２成分の合計）を演算装置１２００から受信する。演算装置１２００は、ベクトルｃ３の第２成分ｃ３２（第２成分の合計）を演算装置１１００に送信するとともに、ベクトルｃ４の第３成分ｃ４３（第３成分の合計）を演算装置１３００から受信する。演算装置１３００は、ベクトルｃ４の第３成分ｃ４３（第３成分の合計）を演算装置１２００に送信するとともに、ベクトルｃ１の第４成分ｃ１４（第４成分の合計）を演算装置１０００から受信する。
【００２４】
第８の処理では、以下の処理を並列に行う。演算装置１０００は、受信したベクトルｃ２の第１成分ｃ２１（第１成分の合計）を、ベクトルｃ１の第１成分ｃ１１として記録する。演算装置１１００は、受信したベクトルｃ３の第２成分ｃ３２（第２成分の合計）を、ベクトルｃ２の第２成分ｃ２２として記録する。演算装置１２００は、受信したベクトルｃ４の第３成分ｃ４３（第３成分の合計）を、ベクトルｃ３の第３成分ｃ３３として記録する。演算装置１３００は、受信したベクトルｃ１の第４成分ｃ１４（第１成分の合計）を、ベクトルｃ４の第４成分ｃ４４として記録する。
【００２５】
第７の処理と第８の処理によって、第１成分の合計は演算装置１１００から演算装置１０００に分配され、第２成分の合計は演算装置１２００から演算装置１１００に分配され、第３成分の合計は演算装置１３００から演算装置１２００に分配され、第４成分の合計は演算装置１０００から演算装置１３００に分配された。第９の処理から第１２の処理は、第７の処理と第８の処理の繰り返しである。この繰り返しによって、各成分の合計はすべての演算装置に分配される。
【００２６】
原理２
図７に、図４の並列演算システムを用いて４個の５次元ベクトルの和を求める方法の原理を示す。この例は、ベクトルの次元がベクトルの数よりも多い例である。この場合、あらかじめ、ベクトルの成分を４つのグループに分けておく。この例では、第１成分と第５成分を１番目のグループ、第２成分を２番目のグループ、第３成分を３番目のグループ、第４成分を４番目のグループとする。この例では、演算装置１０００が１番目の演算装置、演算装置１１００が２番目の演算装置、演算装置１２００が３番目の演算装置、演算装置１３００が４番目の演算装置とする。あらかじめ、ｎ番目の演算装置が、それぞれベクトルｃｎ＝（ｃｎ１，ｃｎ２，ｃｎ３，ｃｎ４，ｃｎ５）を記録部に記録している。ただし、ｎは１から４の整数である。
原理２の処理も、第１の処理から第１２の処理であり、原理１と同じである。原理１との違いは、ベクトルの次元が異なることである。原理２では、１番目のグループに属する第５成分が第１成分と一緒に処理される。
【００２７】
原理３
図８に、図４の並列演算システムを用いて４個の２次元ベクトルの和を求める方法の原理を示す。この例は、ベクトルの次元がベクトルの数よりも少ない例である。この場合、あらかじめ、ベクトルの成分を４つのグループに分けておく。この例では、第１成分を１番目のグループ、第２成分を２番目のグループとする。３番目のグループと４番目のグループに属する成分はない。この例でも、演算装置１０００が１番目の演算装置、演算装置１１００が２番目の演算装置、演算装置１２００が３番目の演算装置、演算装置１３００が４番目の演算装置とする。あらかじめ、ｎ番目の演算装置が、それぞれベクトルｃｎ＝（ｃｎ１，ｃｎ２）を記録部に記録している。ただし、ｎは１から４の整数である。
原理３の処理も、第１の処理から第１２の処理であり、原理１と同じである。原理１との違いは、ベクトルの次元が異なることである。原理３では、属する成分がない３番目のグループと４番目のグループの処理では、演算装置は動作しない。
【００２８】
演算方法１
図９は、Ｎ個の演算装置でＮ個のＮ次元のベクトルの和を求める並列演算システムの処理フローを示す図である。なお、この処理フローは原理１に対応している。
【００２９】
まず、Ｎ個の演算装置が、それぞれの記録部のベクトル記録手段に１つずつベクトルを記録しておく（Ｓ１１０）。また、τに０を代入し、τ記録手段に記録しておく（Ｓ１２０）。
ｎ番目の演算装置（１０００など）は、記録部（１０２０など）のベクトル記録手段（１０２２など）から、第（ｎ−１＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、通信部（１０３０など）の送信手段（１０３１など）を用いて（ｎ−２（ｍｏｄ  Ｎ））＋１番目の演算装置（１３００など）に送信する（Ｓ１３０）。ｎ番目の演算装置（１０００など）は、通信部（１０３０など）の受信手段（１０３２など）を用いて第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分をｎ（ｍｏｄ  Ｎ））＋１番目の演算装置（１１００など）から受信する（Ｓ１４０）。なお、τ＝０のときのステップＳ１３０とＳ１４０が図６の第１の処理、τ＝１のときのステップＳ１３０とＳ１４０が図６の第３の処理、τ＝２のときのステップＳ１３０とＳ１４０が図６の第５の処理、τ＝３のときのステップＳ１３０とＳ１４０が図６の第７の処理、τ＝４のときのステップＳ１３０とＳ１４０が図６の第９の処理、τ＝５のときのステップＳ１３０とＳ１４０が図６の第１１の処理に該当する。
【００３０】
ｎ番目の演算装置（１０００など）は、（１）τ≦Ｎ−２の場合は、記録部（１０２０など）のベクトル記録手段（１０２２など）から、第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を取り出し、ステップＳ１４０で受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分との和を求め、結果を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部（１０２０など）のベクトル記録手段（１０２２など）に記録し、（２）τ＞Ｎ−２の場合は、ステップＳ１４０で受信した第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分を第（ｎ＋τ（ｍｏｄ  Ｎ））＋１成分として記録部（１０２０など）のベクトル記録手段（１０２２など）に記録する（Ｓ１５０）。τ＝０のときのステップＳ１５０が図６の第２の処理、τ＝１のときのステップＳ１５０が図６の第４の処理、τ＝２のときのステップＳ１５０が図６の第６の処理、τ＝３のときのステップＳ１５０が図６の第８の処理、τ＝４のときのステップＳ１５０が図６の第１０の処理、τ＝５のときのステップＳ１５０が図６の第１２の処理に該当する。
各演算装置は、τにτ＋１を代入して記録部に記録する（Ｓ１６０）。各演算装置は、τが２Ｎ−３以下の場合はステップＳ１３０に戻り、２Ｎ−３より大きい場合は処理を終了する（Ｓ１７０）。図６の場合は、２Ｎ−３＝５なので、τ＝５（第１２の処理）までで繰り返し処理は終了する。
【００３１】
演算方法２
図１０は、Ｎ個の演算装置でＮ個のＫ次元のベクトルの和を求める並列演算システムの処理フローを示す図である。なお、この処理フローは原理１から原理３に対応できる。
【００３２】
あらかじめ、ベクトルのＫ個の成分をＮ個のグループ（１番目のグループからＮ番目のグループ）に分けておく。まず、Ｎ個の演算装置が、それぞれの記録部のベクトル記録手段に１つずつベクトルを記録しておく（Ｓ１１０）。また、τに０を代入し、τ記録手段に記録しておく（Ｓ１２０）。
【００３３】
（ｎ−１−τ（ｍｏｄ  Ｎ））＋１番目の演算装置（ただし、ｎは１からＮの整数。）が、（１）当該演算装置の記録部からｎ番目のグループのベクトルの成分を取り出し、（２）当該演算装置の通信部を用いて（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の演算装置に送信する（Ｓ１３１）。（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の演算装置が、当該演算装置の通信部を用いてｎ番目のグループのベクトルの成分を（ｎ−１−τ（ｍｏｄ  Ｎ））＋１番目の演算装置から受信する（Ｓ１４１）。なお、τ＝０のときのステップＳ１３１とＳ１４１が図６〜８の第１の処理、τ＝１のときのステップＳ１３１とＳ１４１が図６〜８の第３の処理、τ＝２のときのステップＳ１３１とＳ１４１が図６〜８の第５の処理、τ＝３のときのステップＳ１３１とＳ１４１が図６〜８の第７の処理、τ＝４のときのステップＳ１３１とＳ１４１が図６〜８の第９の処理、τ＝５のときのステップＳ１３１とＳ１４１が図６〜８の第１１の処理に対応できる。
【００３４】
（ｎ−２−τ（ｍｏｄ  Ｎ））＋１番目の各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からｎ番目のグループのベクトルの成分を取り出し、当該演算装置の記録部で、受信したｎ番目のグループのベクトルの成分との和を求め、結果をｎ番目のグループのベクトルの成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、受信したｎ番目のグループのベクトルの成分を、ｎ番目のグループのベクトルの成分として記録部に記録する（Ｓ１５１）。なお、τ＝０のときのステップＳ１５１が図６〜８の第２の処理、τ＝１のときのステップＳ１５１が図６〜８の第４の処理、τ＝２のときのステップＳ１５１が図６〜８の第６の処理、τ＝３のときのステップＳ１５１が図６〜８の第８の処理、τ＝４のときのステップＳ１５１が図６〜８の第１０の処理、τ＝５のときのステップＳ１５１が図６〜８の第１２の処理に対応できる。
各演算装置は、τにτ＋１を代入して記録部に記録する（Ｓ１６０）。各演算装置は、τが２Ｎ−３以下の場合はステップＳ１３０に戻り、２Ｎ−３より大きい場合は処理を終了する（Ｓ１７０）。図６〜８の場合は、２Ｎ−３＝５なので、τ＝５（第１２の処理）までで繰り返し処理は終了する。
【００３５】
このように処理するので、１組のＮ個のＫ次元のベクトルの和をＮ個の演算装置で行う場合、最大で２｛Ｋ／Ｎ｝（Ｎ−１）回の通信で、情報の収集と結果の分配が実現できる。また、データはリング状かつ片方向に送られるため、Ｎ個の片方向の通信路（リング状）を有するネットワークを備えればよい。
【００３６】
［変形例１］
第１実施形態では、ベクトルの数と演算装置の数が同じ場合を説明した。本変形例では、ベクトルの数が演算装置の数よりも多い場合について説明する。なお、ベクトルの数が演算装置よりも少ない場合、ベクトルを記録していない演算装置が存在することになる。このような演算装置は、並列演算システムに含めなければよい。したがって、ベクトルの数は演算装置の数以上とする。
また、同じ演算装置内の複数のベクトルの和を最初に計算してしまい、１つのベクトルにし、その後、複数の装置間に分散しているベクトルの和を求めることもできる。この場合は、同じ演算装置内のベクトルの和を計算する処理と第１実施形態の処理を組み合わせることで実現できる。
本変形例では、同じ演算装置内のベクトルの和を最初に計算しなくても、１つの演算装置に複数のベクトルがある場合に、本発明の並列演算方法を適用できることを示す。本変形例の演算装置も図４、５に示した演算装置と同じ機能構成である。
【００３７】
原理
図１１に、図４の並列演算システムを用いて５個の５次元ベクトルの和を求める方法の原理を示す。あらかじめ、演算装置１０００がベクトルｃ１とｃ５を、演算装置１１００がベクトルｃ２を、演算装置１２００がベクトルｃ３を、演算装置１３００がベクトルｃ４を記録している。
【００３８】
第１の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ５の第５成分ｃ５５を演算装置１３００に送信するとともに、ベクトルｃ２の第２成分ｃ２２を演算装置１１００から受信する。演算装置１１００は、ベクトルｃ２の第２成分ｃ２２を演算装置１０００に送信するとともに、ベクトルｃ３の第３成分ｃ３３を演算装置１２００から受信する。演算装置１２００は、ベクトルｃ３の第３成分ｃ３３を演算装置１１００に送信するとともに、ベクトルｃ４の第４成分ｃ４４を演算装置１３００から受信する。演算装置１３００は、ベクトルｃ４の第４成分ｃ４４を演算装置１２００に送信するとともに、ベクトルｃ５の第５成分ｃ５５を演算装置１０００から受信する。この処理では、ベクトルｃ１とベクトルｃ５を記録している演算装置が同じなので、ベクトルｃ１を記録している演算装置からベクトルｃ５を記録している演算装置へのベクトルｃ１の第１成分ｃ１１の送信は行わない。
【００３９】
第２の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ１の第２成分ｃ１２と受信したベクトルｃ２の第２成分ｃ２２との和を、ベクトルｃ１の第２成分ｃ１２として記録する。さらに、演算装置１０００は、ベクトルｃ５の第１成分ｃ５１とベクトルｃ１の第１成分ｃ１１との和を、ベクトルｃ５の第１成分ｃ５１として記録する。演算装置１１００は、ベクトルｃ２の第３成分ｃ２３と受信したベクトルｃ３の第３成分ｃ３３との和を、ベクトルｃ２の第３成分ｃ２３として記録する。演算装置１２００は、ベクトルｃ３の第４成分ｃ３４と受信したベクトルｃ４の第４成分ｃ４４との和を、ベクトルｃ３の第４成分ｃ３４として記録する。演算装置１３００は、ベクトルｃ４の第５成分ｃ４５と受信したベクトルｃ５の第５成分ｃ５５との和を、ベクトルｃ４の第５成分ｃ４５として記録する。
【００４０】
第３の処理から第８の処理は、第１の処理と第２の処理の繰り返しである。第８の処理が終了すると、第１成分の合計は演算装置１１００、第２成分の合計は演算装置１２００、第３成分の合計は演算装置１３００、第４成分の合計は演算装置１０００、第５成分の合計は演算装置１０００がそれぞれ記録している。
【００４１】
第９の処理では、以下の処理を並列に行う。演算装置１０００は、ベクトルｃ５の第４成分ｃ５４（第４成分の合計）を演算装置１３００に送信するとともに、ベクトルｃ２の第１成分ｃ２１（第１成分の合計）を演算装置１１００から受信する。演算装置１１００は、ベクトルｃ２の第１成分ｃ２１（第１成分の合計）を演算装置１０００に送信するとともに、ベクトルｃ３の第２成分ｃ３２（第２成分の合計）を演算装置１２００から受信する。演算装置１２００は、ベクトルｃ３の第２成分ｃ３２（第２成分の合計）を演算装置１１００に送信するとともに、ベクトルｃ４の第３成分ｃ４３（第３成分の合計）を演算装置１３００から受信する。演算装置１３００は、ベクトルｃ４の第３成分ｃ４３（第３成分の合計）を演算装置１２００に送信するとともに、ベクトルｃ５の第４成分ｃ５４（第４成分の合計）を演算装置１０００から受信する。この処理では、ベクトルｃ１とベクトルｃ５を記録している演算装置が同じなので、ベクトルｃ１を記録している演算装置からベクトルｃ５を記録している演算装置へのベクトルｃ１の第５成分ｃ１５の送信は行わない。
【００４２】
第１０の処理では、以下の処理を並列に行う。演算装置１０００は、受信したベクトルｃ２の第１成分ｃ２１（第１成分の合計）を、ベクトルｃ１の第１成分ｃ１１として記録する。さらに、演算装置１０００は、ベクトルｃ１の第５成分ｃ１５（第５成分の合計）を、ベクトルｃ５の第５成分ｃ５５として記録する。演算装置１１００は、受信したベクトルｃ３の第２成分ｃ３２（第２成分の合計）を、ベクトルｃ２の第２成分ｃ２２として記録する。演算装置１２００は、受信したベクトルｃ４の第３成分ｃ４３（第３成分の合計）を、ベクトルｃ３の第３成分ｃ３３として記録する。演算装置１３００は、受信したベクトルｃ１の第４成分ｃ１４（第１成分の合計）を、ベクトルｃ４の第４成分ｃ４４として記録する。
第１１の処理から第１６の処理は、第９の処理と第１０の処理の繰り返しである。この繰り返しによって、各成分の合計はすべての演算装置に分配される。
【００４３】
演算方法
図１２は、Ｉ個の演算装置でＮ個のＫ次元のベクトルの和を求める並列演算システムの処理フローを示す図である。ただし、Ｉは２以上Ｎ以下の整数とする。
各演算装置が、演算の対象となるＫ次元のベクトルｃｎ（ｎは１からＮの整数）の中の１つまたは複数を当該演算装置の記録部のベクトル記録手段に記録する（Ｓ１１５）。また、各演算装置が、τに０を代入し、τ記録手段に記録しておく（Ｓ１２０）。
【００４４】
ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信する（Ｓ１３５）。ベクトルｃｑを記録部に有する演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する（Ｓ１４５）。なお、τ＝０のときのステップＳ１３５とＳ１４５が図１１の第１の処理、τ＝１のときのステップＳ１３５とＳ１４５が図１１の第３の処理、τ＝２のときのステップＳ１３５とＳ１４５が図１１の第５の処理、τ＝３のときのステップＳ１３５とＳ１４５が図１１の第７の処理、τ＝４のときのステップＳ１３５とＳ１４５が図１１の第９の処理、τ＝５のときのステップＳ１３５とＳ１４５が図１１の第１１の処理、τ＝６のときのステップＳ１３５とＳ１４５が図１１の第１３の処理、τ＝７のときのステップＳ１３５とＳ１４５が図１１の第１５の処理に該当する。
【００４５】
ベクトルｃｑを記録部に有する各演算装置が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部からベクトルｃｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｐの第ｎ成分を、ベクトルｃｑの第ｎ成分として記録部に記録する（Ｓ１５５）。なお、τ＝０のときのステップＳ１５５が図１１の第２の処理、τ＝１のときのステップＳ１５５が図１１の第４の処理、τ＝２のときのステップＳ１５５が図１１の第６の処理、τ＝３のときのステップＳ１５５が図１１の第８の処理、τ＝４のときのステップＳ１５５が図１１の第１０の処理、τ＝５のときのステップＳ１５５が図１１の第１２の処理、τ＝６のときのステップＳ１５５が図１１の第１４の処理、τ＝７のときのステップＳ１５５が図１１の第１６の処理に該当する。
【００４６】
各演算装置は、τにτ＋１を代入して記録部に記録する（Ｓ１６０）。各演算装置は、τが２Ｎ−３以下の場合はステップＳ１３０に戻り、２Ｎ−３より大きい場合は処理を終了する（Ｓ１７０）。図１１の場合は、２Ｎ−３＝７なので、τ＝７（第１６の処理）までで繰り返し処理は終了する。
このように処理するので、１組のＮ個のＫ次元のベクトルの和をＮ個の演算装置で行う場合、最大で２｛Ｋ／Ｎ｝（Ｎ−１）回の通信で、情報の収集と結果の分配が実現できる。また、データはリング状かつ片方向に送られるため、Ｎ個の片方向の通信路（リング状）を有するネットワークを備えればよい。
【００４７】
本変形例では、ベクトルｃｐを記録部に有する各演算装置が、ベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置に情報を送った。また、第１実施形態でも、情報を降順（演算装置の番号が小さくなる方向）に送った。しかし、ベクトルｃｐを記録部に有する各演算装置が、ベクトルｃｑ（ｑはｐ＋１。ただし、ｐ＝Ｎのときはｒ＝１）を記録部に有する演算装置（昇順）に情報を送ってもよい。また、番号の付け方を逆（ｎ番目をＮ−ｎ番目に変更）にすれば、物理的な送受信の方向を逆にできる。つまり、番号の付け方は、単に人があらかじめ定めるだけなので、ｑ＝ｐ−１としてもｑ＝ｐ＋１としても実質的に等価である。本明細書では、特に明記しない限り、装置やベクトルなどの順番とは、降順と昇順の両方を含んでいるものとする。
【００４８】
なお、１つの演算装置に複数のベクトルが記録されている場合には、先に演算装置内のベクトルの和を求め、１つのベクトルとする方が処理の回数が少なくなる。しかし、Ｎ個のＫ次元ベクトルの和をＭ組並列に（同時に）演算するような場合に、組ごとに計算方法が異なると煩雑となるため、本変形例の方法も有効である。また、本変形例は各演算装置に１つずつベクトルを記録しておく場合にも適用できるので、本変形例の方法の方が、第１実施形態の用法よりも適用できる範囲は広い。
【００４９】
［変形例２］
第１実施形態、変形例１では、収集も分配も、情報の流れは同じ方向であった。しかし、収集での情報の流れと分配での情報の流れを逆向きにしてもよい。
原理
図１３に、図４の並列演算システムを用いて４個の４次元ベクトルの和を求める方法の原理を示す。あらかじめ、演算装置１０００がベクトルｃ１を、演算装置１１００がベクトルｃ２を、演算装置１２００がベクトルｃ３を、演算装置１３００がベクトルｃ４を記録している。第６の処理までは、図６に示した原理と同じである。第７の処理から情報の流れを逆にしている。
演算方法
図１２を用いて処理フローを説明する。本変形例では、τ≦Ｎ−２までは変形例１と同じ処理フローであり、以下のようになる。
【００５０】
τ≦Ｎ−２の場合には、ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｑを記録部に有する演算装置に送信する（Ｓ１３５’）。ベクトルｃｑを記録部に有する演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する（Ｓ１４５’）。ベクトルｃｑを記録部に有する各演算装置が、当該演算装置の記録部からベクトルｃｑの第ｎ成分を取り出し、当該演算装置の計算部で、ベクトルｃｐの第ｎ成分との和を求め、結果をベクトルｃｑの第ｎ成分として記録部に記録する（Ｓ１５５’）。
τ＞Ｎ−２の場合には、  ベクトルｃｐ（ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部に有する各演算装置が、（１）当該演算装置の記録部からベクトルｃｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｒ（ｒはｐ＋１。ただし、ｐ＝Ｎのときはｒ＝１）を記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｒを記録部に有する演算装置に送信する（Ｓ１３５’）。ベクトルｃｒを記録部に有する演算装置が、当該演算装置とベクトルｃｐを記録部に有する演算装置とが異なる場合には、通信部を用いてベクトルｃｐの第ｎ成分を、ベクトルｃｐを記録部に有する演算装置から受信する（Ｓ１４５’）。ベクトルｃｒを記録部に有する各演算装置が、ベクトルｃｐの第ｎ成分を、ベクトルｃｒの第ｎ成分として記録部に記録する（Ｓ１５５’）。
この後の処理も、変形例１と同じである。
【００５１】
このように処理するので、１組のＮ個のＫ次元のベクトルの和をＮ個の演算装置で行う場合、最大で２｛Ｋ／Ｎ｝（Ｎ−１）回の通信で、情報の収集と結果の分配が実現できる。また、データはリング状かつ双方向に送られるため、Ｎ個の半二重の通信路（リング状）を有するネットワークを備えればよい。
【００５２】
［変形例３］
第１実施形態、変形例１、変形例２では、ベクトルの各成分の情報の収集と分配を行ったが、収集するだけでも、各成分の合計値はいずれかの演算装置に記録されている。したがって、τ≦Ｎ−２までの収集の処理までで処理フローを終了させる方法もありうる。
【００５３】
［第２実施形態］
本実施形態では、まず、Ｉ個の演算装置（Ｉは２以上の整数）を用いて、Ｍ行Ｎ列の行列Ａ（Ｍは２以上の整数、Ｎは２以上の整数、かつＭＮ≧Ｉ）とＮ行Ｋ列の行列Ｂ（Ｋは２以上の整数）との積ＡＢを求める方法を示す。次に積ＡＢにさらに行列Ａの転置行列ＡＴを乗算する方法を示す。
原理１
図１４に４行４列の行列Ａと４行４列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す。図１４（Ａ）の内容を説明する。行列Ａのｍ行ｎ列の成分をａｍｎ、行列Ｂのｍ行ｎ列の成分をｂｍｎとすると、積ＡＢのｍ行ｎ列の成分は、ａｍ１ｂ１ｎ＋ａｍ２ｂ２ｎ＋ａｍ３ｂ３ｎ＋ａｍ４ｂ４ｎとなる。行列の積を求める並列演算システムが、行列Ａの成分ａｍｎごとに演算する演算装置を決めるとする。このような並列演算システムでは、例えば、積ａ１１ｂ１１は、成分ａ１１の演算を行う演算装置（言い換えると、記録部に成分ａ１１を有する演算装置）が計算する。この演算装置は、積ａ１１ｂ１２、積ａ１１ｂ１３、積ａ１１ｂ１４の計算も行うので、これらの結果を成分とする４次元ベクトル（ａ１１ｂ１１，ａ１１ｂ１２，ａ１１ｂ１３，ａ１１ｂ１４）を記録部に記録することとなる。積ＡＢの１行目を構成する４次元ベクトルは、成分ａ１１の演算を行う演算装置の結果（ａ１１ｂ１１，ａ１１ｂ１２，ａ１１ｂ１３，ａ１１ｂ１４）、成分ａ１２の演算を行う演算装置の結果（ａ１２ｂ２１，ａ１２ｂ２２，ａ１２ｂ２３，ａ１２ｂ２４）、成分ａ１３の演算を行う演算装置の結果（ａ１３ｂ３１，ａ１３ｂ３２，ａ１３ｂ３３，ａ１３ｂ３４）、成分ａ１４の演算を行う演算装置の結果（ａ１４ｂ４１，ａ１４ｂ４２，ａ１４ｂ４３，ａ１４ｂ４４）の和である。
【００５４】
つまり、図１４（Ｂ）に示すように、ｃｍｎ＝（ａｍｎｂｎ１，ａｍｎｂｎ２，ａｍｎｂｎ３，ａｍｎｂｎ４）とすれば、積ＡＢのｍ行目を構成するベクトルは、ｃｍ１＋ｃｍ２＋ｃｍ３＋ｃｍ４となる。また、第１実施形態のベクトルの和を求める並列演算方法を用いれば、積ＡＢの演算が終了した時には、成分ａｍｎの演算を行う演算装置（成分ａｍｎを記録部に有する演算装置）は、ｃｍ１＋ｃｍ２＋ｃｍ３＋ｃｍ４の計算結果を記録している。なお、このような行列の計算では、各行でｃｍ１＋ｃｍ２＋ｃｍ３＋ｃｍ４の計算を行うので、Ｎ個のＫ次元ベクトルの和をＭ組並列に計算することになる。
【００５５】
図１４（Ｃ）は、転置行列ＡＴを乗算する場合の原理を示す。行列Ａのｍ行ｎ列の成分ａｍｎが転置行列ＡＴのｎ行ｍ列の成分となる。そこで、転置行列ＡＴの演算では、行列Ａのｍ行ｎ列の成分ａｍｎの演算を行った演算装置が、転置行列ＡＴのｎ行ｍ列の成分の演算を行う。この場合、転置行列ＡＴのｎ行ｍ列の成分の演算を行う演算装置には、積ＡＢのｍ行の各成分の情報が必要である。ところが、積ＡＢのｍ行の各成分の情報とは、ｃｍ１＋ｃｍ２＋ｃｍ３＋ｃｍ４の計算結果のことである。つまり、転置行列ＡＴの演算のためにデータを通信する必要はない。
原理２
図１５に、３行４列の行列Ａと４行２列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す。この場合も考え方は原理１と同じである。この場合は、積ＡＢのｍ行目は、４個の２次元ベクトルｃｍｎ＝（ａｍｎｂｎ１，ａｍｎｂｎ２）の和となる。
原理３
図１６に、４行２列の行列Ａと２行４列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す。この場合も考え方は原理１と同じである。この場合は、積ＡＢのｍ行目は、２個の４次元ベクトルｃｍｎ＝（ａｍｎｂｎ１，ａｍｎｂｎ２，ａｍｎｂｎ３，ａｍｎｂｎ４）の和となる。
【００５６】
演算方法１
図１７に、Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＢを求める場合の、１つの演算装置の機能構成例を示す。並列演算システムの構成は図４と同じである。また、図１８に、Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＢを求める場合の処理フローを示す。
【００５７】
演算装置２０００は、計算部２０１０、記録部２０２０、通信部２０３０から構成される。計算部２０１０は、τ増加手段２００１、繰り返し手段２００２、成分計算手段２０１１、演算結果記録手段２０１２を備える。なお、τ増加手段２００１と繰り返し手段２００２は、計算部２０１０以外の構成部（たとえば、図示していないが制御部などの構成部が考えられる。）が備えてもよい。記録部２０２０は、成分記録手段２０２１、ベクトル記録手段２０２２、τ記録手段２０２３を有する。通信部２０３０は、送信手段２０３１と受信手段２０３２とを有する。なお、他の演算装置も同じ機能構成である。
【００５８】
あらかじめ、行列ＡのＭＮ個の成分ａｍｎをＩ個のグループに分けておき、各演算装置（２０００など）が、ｉ番目のグループのすべての成分ａｍｎと、当該成分に乗算する行列Ｂの成分ｂｎ１〜ｂｎＫとを記録部（２０２０など）の成分記録手段（２０２１など）に記録する（Ｓ２１０）。次に、各演算装置（２０００など）が、（１）記録部（２０２０など）の成分記録手段（２０２１など）に記録された成分ａｍｎのそれぞれについて、計算部でａｍｎｂｎ１〜ａｍｎｂｎＫを計算し、（２）結果をＫ次元のベクトルｃｍｎ＝（ｃｍｎ１，ｃｍｎ２，…，ｃｍｎＫ）＝（ａｍｎｂｎ１，ａｍｎｂｎ２，…，ａｍｎｂｎＫ）として記録部（２０２０など）のベクトル記録手段（２０２２など）に記録する（Ｓ２１５）。各演算装置（２０００など）が、記録部（２０２０）のτ記録手段（２０２３など）にτ＝０を記録する（Ｓ２２０）。
【００５９】
ベクトルｃｍｐ（ｍは１からＭ、ｐは（ｎ−１−τ（ｍｏｄ  Ｎ））＋１）を記録部（２０２０など）のベクトル記録手段（２０２２など）に有する各演算装置（２０００など）が、（１）記録部（２０２０など）のベクトル記録手段（２０２２など）からベクトルｃｍｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｃｍｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｎ）を記録部に有する演算装置とが異なる場合（同じ演算装置がベクトルｃｍｐとベクトルｃｍｑとを記録していない場合）には、通信部（２０３０など）の送信手段（２０３１など）を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑを記録部に有する演算装置に送信する（Ｓ２３０）。ベクトルｃｍｑを記録部に有する各演算装置（２０００など）が、当該演算装置とベクトルｃｍｐを記録部に有する演算装置とが異なる場合には、通信部（２０３０など）の受信手段（２０３２など）を用いてベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｐを記録部に有する演算装置からそれぞれ受信する（Ｓ２４０）。
【００６０】
ベクトルｃｍｑを記録部に有する各演算装置（２０００など）が、（１）τ≦Ｎ−２の場合は、当該演算装置の記録部（２０２０など）のベクトル記録手段（２０２２など）からベクトルｃｍｑの第ｎ成分を取り出し、当該演算装置の計算部（２０１０など）の演算結果記録手段（２０１２など）で、ベクトルｃｍｐの第ｎ成分との和を求め、結果をベクトルｃｍｑの第ｎ成分として記録部（２０２０など）のベクトル記録手段（２０２２など）に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｃｍｐの第ｎ成分を、ベクトルｃｍｑの第ｎ成分として記録部（２０２０など）のベクトル記録手段（２０２２など）に記録する（Ｓ２５０）。
【００６１】
各演算装置（２０００など）が、τにτ＋１を代入して記録部（２０２０など）のτ記録手段（２０２３など）に記録する（Ｓ２６０）。各演算装置（２０００など）の折り返し手段（２００２など）が、τが２Ｎ−３以下の場合は処理フローをステップＳ２３０に戻し、それ以外の場合は処理を終了する（Ｓ２７０）。
このような処理によるので、ベクトルの和を求める並列演算と同様に、行列と行列の積を求める並列演算を、通信回数と通信路を少なくしながら実現できる。
【００６２】
演算方法２
図１９に、Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＴＡＢを求める場合の、１つの演算装置の機能構成例を示す。並列演算システムの構成は図４と同じである。また、図２０に、Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＴＡＢを求める場合の処理フローを示す。
【００６３】
演算装置３０００は、計算部３０１０、記録部３０２０、通信部３０３０から構成される。計算部３０１０は、τ増加手段２００１、繰り返し手段２００２、成分計算手段２０１１、演算結果記録手段２０１２、ＡＴτ増加手段３００６、ＡＴ繰り返し手段３００７、ＡＴ成分計算手段３０１６、ＡＴ演算結果記録手段３０１７を備える。なお、τ増加手段２００１、繰り返し手段２００２、ＡＴτ増加手段３００６、ＡＴ繰り返し手段３００７は、計算部３０１０以外の構成部（たとえば、図示していないが制御部などの構成部が考えられる。）が備えてもよい。記録部３０２０は、成分記録手段２０２１、ベクトル記録手段２０２２、τ記録手段２０２３、ＡＴベクトル記録手段３０２２、ＡＴτ記録手段３０２３を有する。通信部３０３０は、送信手段２０３１、受信手段２０３２、ＡＴ送信手段３０３６、ＡＴ受信手段３０３７を有する。なお、他の演算装置も同じ機能構成である。
ステップＳ２１０からＳ２７０までの処理は、図１８の演算方法１と同じである。
【００６４】
各演算装置（３０００など）が、（１）記録部（３０２０など）のベクトル記録手段（２０２２など）に記録された成分ａｍｎのそれぞれについて、計算部（３０１０など）のＡＴ成分計算手段（３０１６など）でａｍｎｃｍ１〜ａｍｎｃｍＫを計算し、（２）結果をＫ次元のベクトルｂｎｍ＝（ｂｎｍ１，ｂｎｍ２，…，ｂｎｍＫ）＝（ａｍｎｃｍ１，ａｍｎｃｍ２，…，ａｍｎｃｍＫ）として記録部（３０２０など）のＡＴベクトル記録手段（３０２７など）に記録する（Ｓ３１５）。各演算装置（３０００など）が、記録部（３０２０）のＡＴτ記録手段（３０２８など）にτ＝０を記録する（Ｓ３２０）。なお、ＡＴτ記録手段（３０２８など）は、τ記録手段（２０２３など）と同じでも良い。
【００６５】
ベクトルｂｎｐ（ｎは１からＮ、ｐは（ｎ−１−τ（ｍｏｄ  Ｍ）＋１）を記録部に有する各演算装置（３０００など）が、（１）記録部（３０２０など）のＡＴベクトル記録手段（３０２７など）からベクトルｂｎｐの第ｎ成分を取り出し、（２）当該演算装置とベクトルｂｎｑ（ｑはｐ−１。ただし、ｐ＝１のときはｑ＝Ｍ）を記録部に有する演算装置とが異なる場合には、通信部（３０３０など）のＡＴ送信手段（３０３６など）を用いてベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑを記録部に有する演算装置に送信する（Ｓ３３０）。ベクトルｂｎｑを記録部に有する各演算装置（３０００など）が、当該演算装置とベクトルｂｎｐを記録部に有する演算装置とが異なる場合には、通信部（３０３０など）のＡＴ受信手段（３０３７など）を用いてベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｐを記録部に有する演算装置からそれぞれ受信する（Ｓ３４０）。なお、ＡＴ送信手段（３０３６など）は送信手段（２０３１など）と同じでもよく、ＡＴ受信手段（３０３７など）は受信手段（２０３２など）と同じでも良い。
【００６６】
ベクトルｂｎｑを記録部に有する各演算装置（３０００など）が、（１）τ≦Ｎ−２の場合は、記録部（３０２０など）のＡＴベクトル記録手段（３０２７など）からベクトルｂｎｑの第ｎ成分を取り出し、計算部（３０１０など）のＡＴ演算結果記録手段３０１７で、ベクトルｂｎｐの第ｎ成分との和を求め、結果をベクトルｂｎｑの第ｎ成分として記録部（３０２０など）のＡＴベクトル記録手段（３０２７など）に記録し、（２）τ＞Ｎ−２の場合は、ベクトルｂｎｐの第ｎ成分を、ベクトルｂｎｑの第ｎ成分として記録部（３０２０など）のＡＴベクトル記録手段（３０２７など）に記録する（Ｓ３５０）。
【００６７】
各演算装置（３０００など）が、τにτ＋１を代入して記録部（３０２０など）のＡＴτ記録手段（３０２８など）に記録する（Ｓ３６０）。各演算装置（３０００など）の折り返し手段（３００７など）が、τが２Ｎ−３以下の場合は処理フローをステップＳ３３０に戻し、それ以外の場合は処理を終了する（Ｓ３７０）。
このような処理によるので、ベクトルの和を求める並列演算と同様に、行列と行列の積を求める並列演算を、通信回数と通信路を少なくしながら実現できる。さらに、転置行列ＡＴの演算のためにデータを通信する必要はない。したがって、Block Lanczos法のように、疎行列とその転置行列とを掛ける演算を含む場合には、通信回数を大幅に削減できる。
【００６８】
演算方法３
さらに、Block Lanczos法のように、疎行列とその行列の転置行列を繰り返し乗算する演算が含まれている演算の例もある。このような場合には、第２実施形態の演算方法２を繰り返すことができる。この場合は、演算装置３０００は、図１９に点線で示す、ＡＴＡＢ計算繰り返し手段３００８も備えている。図２１に行列とその転置行列との乗算を繰り返す場合の処理フローを示す。ステップＳ２１０とＳ３００とは、図２０と同じである。本変形例の方法では、図２０の処理フローに、繰り返しを判断するステップＳ２７０が付加されている。
このような処理によって、さらにBlock Lanczos法のように、疎行列とその転置行列とを掛ける演算を繰り返す場合には、通信回数を大幅に削減できる。
【００６９】
なお、上記の実施形態は、図２２に示すコンピュータの記録部５０２０に読み込ませたプログラムによって、制御部５０１０、記録部５０２０、通信部５０３０などに上記方法の各ステップを実行させることができる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。
【産業上の利用可能性】
【００７０】
本発明は、ベクトルの和を求める演算や行列の積を求める演算を用いる大規模な情報処理システムに利用できる。例えば、暗号を用いたセキュリティシステムの安全性評価システムなどに利用できる。
【図面の簡単な説明】
【００７１】
【図１】従来の方法を実現するシステム構成例を示す図。
【図２】従来の情報の収集の様子を示す図。
【図３】従来の情報の分配の様子を示す図。
【図４】Ｎ個の演算装置（Ｎ＝４）を用いてＫ次元のベクトルの和を求める並列演算システムの構成例を示す図。
【図５】演算装置１０００の機能構成例を示す図。
【図６】並列演算システムを用いて４個の４次元ベクトルの和を求める方法の原理を示す図。
【図７】並列演算システムを用いて４個の５次元ベクトルの和を求める方法の原理を示す図。
【図８】並列演算システムを用いて４個の２次元ベクトルの和を求める方法の原理を示す図。
【図９】Ｎ個の演算装置でＮ個のＮ次元のベクトルの和を求める並列演算システムの処理フローを示す図。
【図１０】Ｎ個の演算装置でＮ個のＫ次元のベクトルの和を求める並列演算システムの処理フローを示す図。
【図１１】並列演算システムを用いて５個の４次元ベクトルの和を求める方法の原理を示す図。
【図１２】Ｉ個の演算装置でＮ個のＫ次元のベクトルの和を求める並列演算システムの処理フローを示す図。
【図１３】並列演算システムを用いて４個の４次元ベクトルの和を求める方法の別の原理を示す図。
【図１４】４行４列の行列Ａと４行４列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す図。
【図１５】３行４列の行列Ａと４行２列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す図。
【図１６】４行２列の行列Ａと２行４列の行列Ｂとの積を求める場合、および行列Ａの転置行列ＡＴを乗算する場合の原理を示す図。
【図１７】Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＢを求める場合の、１つの演算装置の機能構成例を示す図。
【図１８】Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＢを求める場合の処理フローを示す図。
【図１９】Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＴＡＢを求める場合の、１つの演算装置の機能構成例を示す図。
【図２０】Ｉ個の演算装置を用いて、Ｍ行Ｎ列の行列ＡとＮ行Ｋ列の行列Ｂとの積ＡＴＡＢを求める場合の処理フローを示す図。
【図２１】行列とその転置行列との乗算を繰り返す場合の処理フローを示す図。
【図２２】コンピュータの機能構成例を示す図。
【図１】
2008090769.tif 000003
【図２】
2008090769.tif 000004
【図３】
2008090769.tif 000005
【図４】
2008090769.tif 000006
【図５】
2008090769.tif 000007
【図６】
2008090769.tif 000008
【図７】
2008090769.tif 000009
【図８】
2008090769.tif 000010
【図９】
2008090769.tif 000011
【図１０】
2008090769.tif 000012
【図１１】
2008090769.tif 000013
【図１２】
2008090769.tif 000014
【図１３】
2008090769.tif 000015
【図１４】
2008090769.tif 000016
【図１５】
2008090769.tif 000017
【図１６】
2008090769.tif 000018
【図１７】
2008090769.tif 000019
【図１８】
2008090769.tif 000020
【図１９】
2008090769.tif 000021
【図２０】
2008090769.tif 000022
【図２１】
2008090769.tif 000023
【図２２】
2008090769.tif 000024