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