図面 (/)

技術 並列演算システム

出願人 日本電信電話株式会社富士通株式会社
発明者 青木和麻呂下山武司
出願日 2006年10月5日 (14年1ヶ月経過) 出願番号 2006-273556
公開日 2008年4月17日 (12年7ヶ月経過) 公開番号 2008-090768
状態 特許登録済
技術分野 マルチプロセッサ 複合演算
主要キーワード 演算装置間 各演算装置 成分計 完全グラフ 疎行列 トーラス セキュリティ関連 並列演算
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2008年4月17日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (19)

課題

複数の演算装置を用いて行列の積を求める並列演算システムで、演算装置間ネットワーク通信路の数を少なくし、経済的なネットワークを構築することを、本発明の目的とする。

解決手段

本発明の並列演算システムでは、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置は、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、または成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置としか通信しない。したがって、これらの通信路を確保するネットワークを構築する。

概要

背景

ベクトルの和を求める演算行列の積を求める演算は、多くの情報処理で行われている。例えば、セキュリティ関連では、素因数分解の難しさが、いくつかの公開鍵暗号電子署名などに利用され、暗号解読の難しさの根拠となっているため、素因数分解がどれだけのリソースで可能かを調べることは、暗号方式安全性評価として重要である。このような素因数分解の難しさの評価は、複数の演算装置を用いて行われ、その処理の中に、行列の積を求める過程が含まれている。また、行列の積を求める過程にはベクトルの和を求める過程が含まれている。

代表的な素因数分解の手法としては、数体ふるい法がある。数体ふるい法の線形代数部で扱う行列は、巨大であることに加え、0以外の成分の割合が極端に小さい、いわゆる疎行列であるため、ガウス消去法などの通常の線型方程式に対する解法では、明らかに効率が悪い。このような行列に対する効率的なアルゴリズムとしてBlockLanczos法が知られている。なお、数体ふるい法におけるBlock Lanczos法は、非特許文献1に具体的に示されており、この方法の処理の中には、疎行列とその行列の転置行列を繰り返し乗算する演算が含まれている。

N個の演算装置(Nは2以上の整数)がそれぞれK次元のベクトル(Kは2以上の整数)を記録している場合に、それらのベクトルの和を求める最も単純な方法は、ある1つの演算装置(親演算装置)に他のすべての演算装置がベクトルの情報を送り、親演算装置がベクトルの和を求める方法である。なお、すべての演算装置でベクトルの和の結果を共有する必要があるときは、親演算装置が他のすべての演算装置に、結果を送る。この方法の場合、(N−1)個の演算装置が、K個ずつのベクトルの要素を、送受信するので、2K(N−1)回の通信が必要である。この方法の場合、親演算装置と他のすべての演算装置との間に通信路が必要であり、通信路に流れる情報は常に片方向にのみ送られているので、半二重の(N−1)個の通信路(スター型)を有するネットワーク構築する必要がある。

非特許文献1では、上述のベクトルの和を求める方法を改良した方法が示されている。非特許文献1の方法を実現するシステム構成を図1に示す。図2は情報の収集の様子、図3は情報の分配の様子を示す。この方法では、各演算装置9000、9100、9200、9300は、計算部9010、9110、9210、9310と記録部9020、9120、9220、9320と通信部9030、9130、9230、9330とを備えており、各演算装置9000、9100、9200、9300は、他の演算装置との間に通信路を有している。

N個の演算装置(Nは2以上の整数)がそれぞれK次元のベクトル(Kは2以上の整数)を記録している場合に、あらかじめK個の要素をN個のグループに分ける。ここで、各グループの要素の数を、[K/N]と{K/N}に揃えると効率がよい。ただし、本明細書内では[x]は実数x以下の最大の整数、{x}は実数x以上の最小の整数を示す。KがNの倍数の時には、すべてのグループが同じ要素の数K/Nとなる。また、K<Nの場合には、いくつかのグループは要素の数が0となる。n番目の演算装置以外の演算装置(nは1以上N以下の整数)は、当該演算装置が記録するベクトルのn番目のグループに属する要素を、n番目の演算装置に送る。図2は、N=4の場合の情報の収集の様子を示している。n番目の演算装置では、n番目のグループに属する要素ごとに和を求め、それぞれの要素の和を、他の演算装置に送る。図3は、N=4の場合の情報の分配の様子を示している。このように情報の収集と分配を行うと、最大で2{K/N}(N−1)回の通信が必要となる。この方法の場合、単純な方法よりも通信の回数は大きく減っている。しかし、すべての演算装置間に通信路が必要であり、通信路では双方向に情報が送られることになる。つまり、N(N−1)/2個の全二重の通信路(すべての演算装置の間で完全グラフ)を有するネットワークが必要である。

行列の積を求める並列演算システムでは、このようなベクトルの和を求める処理がM行分もしくはN列分生じる。大規模な並列演算システムの場合には、演算装置の数が増えてくるため、すべての演算装置の間で完全グラフのネットワークを構築することは、通信路の数が多くなるため非経済的である。例えば、switching HUBのようなswitching技術を使った製品が、完全グラフのネットワーク構築に用いられている。しかし、あるポート数を超えると、非常に高価になってしまう(2005年現在ならば24ポートまたは48ポートを越えると高価になる)。したがって、演算装置の数が大きくなると、すべての演算装置間で完全グラフのネットワークを構築することが非経済的になってくる。
下山武司、青木和呂、植田広樹、木田祐司“一般数体篩法実装実験(4)−線形代数”、電子情報通信学会技術研究報告、ISEC2003-154、2004.

概要

複数の演算装置を用いて行列の積を求める並列演算システムで、演算装置間のネットワークの通信路の数を少なくし、経済的なネットワークを構築することを、本発明の目的とする。本発明の並列演算システムでは、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置は、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、または成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置としか通信しない。したがって、これらの通信路を確保するネットワークを構築する。

目的

従来の技術では、複数の演算装置で行列の積を求める並列演算システムでは、演算装置間での情報共有に必要な通信路の数が多くなるという問題があった。複数の演算装置を用いて行列の積を求める並列演算システムで、演算装置間のネットワークの通信路の数を少なくし、経済的なネットワークを構築することを、本発明の目的とする。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

計算部と記録部と通信部とを有する複数の演算装置、および演算装置間の複数の通信路とを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列AとN行K列(Kは1以上の整数)の行列Bとの積ABを求める並列演算システムであって、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置が、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置のいずれかと異なる場合には、前記通信路が、少なくとも行列Aのm行n列目の成分amnの演算を行う演算装置と、成分a(m−1)n、成分a(m+1)n、成分am(n−1)、成分am(n+1)の演算を行う異なる演算装置との間に設けられており、前記演算装置は、演算の対象となる行列Aのすべての成分amnと、当該成分に乗算する行列Bの成分bn1〜bnKとを記録する記録部内の成分記録手段と、記録部の成分記録手段に記録された成分amnのそれぞれについて、amnbn1〜amnbnKを計算する計算部内の成分計算手段と、結果をK次元ベクトルcmn=(cmn1,cmn2,…,cmnK)=(amnbn1,amnbn2,…,amnbnK)として記録する記録部内のベクトル記録手段と、τ=0を記録する記録部内のτ記録手段と、あるnに対してベクトルcmp(mは1からM、pは(n−1−τ(modN))+1)を記録部に有する場合に、(1)記録部のベクトル記録手段からベクトルcmpの第n成分を取り出し、(2)ベクトルcmq(qはp−1。ただし、p=1のときはq=N)を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmqを記録部に有する演算装置に送信する通信部内の送信手段と、あるnに対してベクトルcmqを記録部に有し、かつ、ベクトルcmpを記録部に有する演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmpを記録部に有する演算装置から受信する通信部内の受信手段と、あるnに対してベクトルcmqを記録部に有する場合に、(1)τ≦N−2のときは、記録部のベクトル記録手段からベクトルcmqの第n成分を取り出し、ベクトルcmpの第n成分との和を求め、結果をベクトルcmqの第n成分として記録部のベクトル記録手段に記録し、(2)τ>N−2のときは、ベクトルcmpの第n成分を、ベクトルcmqの第n成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、τにτ+1を代入して記録部のτ記録手段に記録するτ増加手段と、τが2N−3以下の場合は、演算を繰り返させる繰り返し手段と、を備えることを特徴とする並列演算システム。

請求項2

計算部と記録部と通信部とを有する複数の演算装置、および演算装置間の複数の通信路とを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列AとK行M列(Kは1以上の整数)の行列Bとの積BAを求める並列演算システムであって、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置が、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置のいずれかと異なる場合には、前記通信路が、少なくとも行列Aのm行n列目の成分amnの演算を行う演算装置と、成分a(m−1)n、成分a(m+1)n、成分am(n−1)、成分am(n+1)の演算を行う異なる演算装置との間に設けられており、前記演算装置は、演算の対象となる行列Aのすべての成分amnと、当該成分に乗算する行列Bの成分b1m〜bKmとを記録する記録部内の成分記録手段と、記録部の成分記録手段に記録された成分amnのそれぞれについて、b1mamn〜bKmamnを計算する計算部内の成分計算手段と、結果をK次元のベクトルdmn=(dmn1,dmn2,…,dmnK)=(b1mamn,b2mamn,…,bKmamn)として記録する記録部内のベクトル記録手段と、τ=0を記録する記録部内のτ記録手段と、あるmに対してベクトルdpn(nは1からN、pは(m−1−τ(modM))+1)を記録部に有する場合に、(1)記録部のベクトル記録手段からベクトルcpnの第m成分を取り出し、(2)ベクトルcqn(qはp−1。ただし、p=1のときはq=M)を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルcpnの第m成分を、ベクトルdqnを記録部に有する演算装置に送信する通信部内の送信手段と、あるmに対してベクトルcqnを記録部に有し、かつ、ベクトルcpnを記録部に有する演算装置と異なる場合には、ベクトルcpnの第m成分を、ベクトルcpnを記録部に有する演算装置から受信する通信部内の受信手段と、あるmに対してベクトルcqnを記録部に有する場合に、(1)τ≦M−2のときは、記録部のベクトル記録手段からベクトルcqnの第m成分を取り出し、ベクトルcpnの第m成分との和を求め、結果をベクトルcqnの第m成分として記録部のベクトル記録手段に記録し、(2)τ>M−2のときは、ベクトルcpnの第m成分を、ベクトルcqnの第m成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、τにτ+1を代入して記録部のτ記録手段に記録するτ増加手段と、τが2M−3以下の場合は、演算を繰り返させる繰り返し手段と、を備えることを特徴とする並列演算システム。

請求項3

計算部と記録部と通信部とを有する複数の演算装置、およびネットワークとを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列AとN行K列(Kは1以上の整数)の行列Bとの積ABを求める並列演算システムであって、前記ネットワークは、演算対象のM行N列の行列Aのm行目の成分am1〜amN(mは1〜Mの整数)の演算を行うすべての演算装置が完全グラフとなり、かつ、n列目の成分a1n〜aMn(nは1〜Nの整数)の演算を行うすべての演算装置が完全グラフとなることを特徴とし、前記演算装置は、演算の対象となる行列Aのすべての成分amnと、当該成分に乗算する行列Bの成分bn1〜bnKとを記録する記録部内の成分記録手段と、記録部の成分記録手段に記録された成分amnのそれぞれについて、amnbn1〜amnbnKを計算する計算部内の成分計算手段と、結果をK次元のベクトルcmn=(cmn1,cmn2,…,cmnK)=(amnbn1,amnbn2,…,amnbnK)として記録する記録部内のベクトル記録手段と、τ=0を記録する記録部内のτ記録手段と、あるnに対してベクトルcmp(mは1からM、pは(n−1−τ(modN))+1)を記録部に有する場合に、(1)記録部のベクトル記録手段からベクトルcmpの第n成分を取り出し、(2)ベクトルcmq(qはp−1。ただし、p=1のときはq=N)を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmqを記録部に有する演算装置に送信する通信部内の送信手段と、あるnに対してベクトルcmqを記録部に有し、かつ、ベクトルcmpを記録部に有する演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmpを記録部に有する演算装置から受信する通信部内の受信手段と、あるnに対してベクトルcmqを記録部に有する場合に、(1)τ≦N−2のときは、記録部のベクトル記録手段からベクトルcmqの第n成分を取り出し、ベクトルcmpの第n成分との和を求め、結果をベクトルcmqの第n成分として記録部のベクトル記録手段に記録し、(2)τ>N−2のときは、ベクトルcmpの第n成分を、ベクトルcmqの第n成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、τにτ+1を代入して記録部のτ記録手段に記録するτ増加手段と、τが2N−3以下の場合は、演算を繰り返させる繰り返し手段と、を備えることを特徴とする並列演算システム。

請求項4

計算部と記録部と通信部とを有する複数の演算装置、およびネットワークとを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列AとK行M列(Kは1以上の整数)の行列Bとの積BAを求める並列演算システムであって、前記ネットワークは、演算対象のM行N列の行列Aのm行目の成分am1〜amN(mは1〜Mの整数)の演算を行うすべての演算装置が完全グラフとなり、かつ、n列目の成分a1n〜aMn(nは1〜Nの整数)の演算を行うすべての演算装置が完全グラフとなることを特徴とし、前記演算装置は、演算の対象となる行列Aのすべての成分amnと、当該成分に乗算する行列Bの成分b1m〜bKmとを記録する記録部内の成分記録手段と、記録部の成分記録手段に記録された成分amnのそれぞれについて、b1mamn〜bKmamnを計算する計算部内の成分計算手段と、結果をK次元のベクトルdmn=(dmn1,dmn2,…,dmnK)=(b1mamn,b2mamn,…,bKmamn)として記録する記録部内のベクトル記録手段と、τ=0を記録する記録部内のτ記録手段と、あるmに対してベクトルdpn(nは1からN、pは(m−1−τ(modM))+1)を記録部に有する場合に、(1)記録部のベクトル記録手段からベクトルcpnの第m成分を取り出し、(2)ベクトルcqn(qはp−1。ただし、p=1のときはq=M)を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルcpnの第m成分を、ベクトルdqnを記録部に有する演算装置に送信する通信部内の送信手段と、あるmに対してベクトルcqnを記録部に有し、かつ、ベクトルcpnを記録部に有する演算装置と異なる場合には、ベクトルcpnの第m成分を、ベクトルcpnを記録部に有する演算装置から受信する通信部内の受信手段と、あるmに対してベクトルcqnを記録部に有する場合に、(1)τ≦M−2のときは、記録部のベクトル記録手段からベクトルcqnの第m成分を取り出し、ベクトルcpnの第m成分との和を求め、結果をベクトルcqnの第m成分として記録部のベクトル記録手段に記録し、(2)τ>M−2のときは、ベクトルcpnの第m成分を、ベクトルcqnの第m成分として記録部のベクトル記録手段に記録する計算部の演算結果記録手段と、τにτ+1を代入して記録部のτ記録手段に記録するτ増加手段と、τが2M−3以下の場合は、演算を繰り返させる繰り返し手段と、を備えることを特徴とする並列演算システム。

請求項5

計算部と記録部と通信部とを有する複数の演算装置、および演算装置間の複数の通信路とを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列Aと行列Bとの積ABまたはBAを求める並列演算システムであって、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置が、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置のいずれかと異なる場合には、前記通信路が、行列Aのm行n列目の成分amnの演算を行う演算装置と、成分a(m−1)n、成分a(m+1)n、成分am(n−1)、成分am(n+1)の演算を行う異なる演算装置との間にのみ備えられている、ことを特徴とする並列演算システム。

技術分野

0001

本発明は、複数の演算装置を用いて行列の積を求める並列演算システムに関する。

背景技術

0002

ベクトルの和を求める演算や行列の積を求める演算は、多くの情報処理で行われている。例えば、セキュリティ関連では、素因数分解の難しさが、いくつかの公開鍵暗号電子署名などに利用され、暗号解読の難しさの根拠となっているため、素因数分解がどれだけのリソースで可能かを調べることは、暗号方式安全性評価として重要である。このような素因数分解の難しさの評価は、複数の演算装置を用いて行われ、その処理の中に、行列の積を求める過程が含まれている。また、行列の積を求める過程にはベクトルの和を求める過程が含まれている。

0003

代表的な素因数分解の手法としては、数体ふるい法がある。数体ふるい法の線形代数部で扱う行列は、巨大であることに加え、0以外の成分の割合が極端に小さい、いわゆる疎行列であるため、ガウス消去法などの通常の線型方程式に対する解法では、明らかに効率が悪い。このような行列に対する効率的なアルゴリズムとしてBlockLanczos法が知られている。なお、数体ふるい法におけるBlock Lanczos法は、非特許文献1に具体的に示されており、この方法の処理の中には、疎行列とその行列の転置行列を繰り返し乗算する演算が含まれている。

0004

N個の演算装置(Nは2以上の整数)がそれぞれK次元のベクトル(Kは2以上の整数)を記録している場合に、それらのベクトルの和を求める最も単純な方法は、ある1つの演算装置(親演算装置)に他のすべての演算装置がベクトルの情報を送り、親演算装置がベクトルの和を求める方法である。なお、すべての演算装置でベクトルの和の結果を共有する必要があるときは、親演算装置が他のすべての演算装置に、結果を送る。この方法の場合、(N−1)個の演算装置が、K個ずつのベクトルの要素を、送受信するので、2K(N−1)回の通信が必要である。この方法の場合、親演算装置と他のすべての演算装置との間に通信路が必要であり、通信路に流れる情報は常に片方向にのみ送られているので、半二重の(N−1)個の通信路(スター型)を有するネットワーク構築する必要がある。

0005

非特許文献1では、上述のベクトルの和を求める方法を改良した方法が示されている。非特許文献1の方法を実現するシステム構成図1に示す。図2は情報の収集の様子、図3は情報の分配の様子を示す。この方法では、各演算装置9000、9100、9200、9300は、計算部9010、9110、9210、9310と記録部9020、9120、9220、9320と通信部9030、9130、9230、9330とを備えており、各演算装置9000、9100、9200、9300は、他の演算装置との間に通信路を有している。

0006

N個の演算装置(Nは2以上の整数)がそれぞれK次元のベクトル(Kは2以上の整数)を記録している場合に、あらかじめK個の要素をN個のグループに分ける。ここで、各グループの要素の数を、[K/N]と{K/N}に揃えると効率がよい。ただし、本明細書内では[x]は実数x以下の最大の整数、{x}は実数x以上の最小の整数を示す。KがNの倍数の時には、すべてのグループが同じ要素の数K/Nとなる。また、K<Nの場合には、いくつかのグループは要素の数が0となる。n番目の演算装置以外の演算装置(nは1以上N以下の整数)は、当該演算装置が記録するベクトルのn番目のグループに属する要素を、n番目の演算装置に送る。図2は、N=4の場合の情報の収集の様子を示している。n番目の演算装置では、n番目のグループに属する要素ごとに和を求め、それぞれの要素の和を、他の演算装置に送る。図3は、N=4の場合の情報の分配の様子を示している。このように情報の収集と分配を行うと、最大で2{K/N}(N−1)回の通信が必要となる。この方法の場合、単純な方法よりも通信の回数は大きく減っている。しかし、すべての演算装置間に通信路が必要であり、通信路では双方向に情報が送られることになる。つまり、N(N−1)/2個の全二重の通信路(すべての演算装置の間で完全グラフ)を有するネットワークが必要である。

0007

行列の積を求める並列演算システムでは、このようなベクトルの和を求める処理がM行分もしくはN列分生じる。大規模な並列演算システムの場合には、演算装置の数が増えてくるため、すべての演算装置の間で完全グラフのネットワークを構築することは、通信路の数が多くなるため非経済的である。例えば、switching HUBのようなswitching技術を使った製品が、完全グラフのネットワーク構築に用いられている。しかし、あるポート数を超えると、非常に高価になってしまう(2005年現在ならば24ポートまたは48ポートを越えると高価になる)。したがって、演算装置の数が大きくなると、すべての演算装置間で完全グラフのネットワークを構築することが非経済的になってくる。
下山武司、青木和呂、植田広樹、木田祐司“一般数体篩法実装実験(4)−線形代数”、電子情報通信学会技術研究報告、ISEC2003-154、2004.

発明が解決しようとする課題

0008

従来の技術では、複数の演算装置で行列の積を求める並列演算システムでは、演算装置間での情報共有に必要な通信路の数が多くなるという問題があった。複数の演算装置を用いて行列の積を求める並列演算システムで、演算装置間のネットワークの通信路の数を少なくし、経済的なネットワークを構築することを、本発明の目的とする。

課題を解決するための手段

0009

本発明の並列演算システムは、計算部と記録部と通信部とを有する複数の演算装置、および演算装置間の複数の通信路とを有し、並列にM行N列(Mは2以上の整数、Nは2以上の整数)の行列Bとの積ABまたは積BAを求める並列演算システムである。

0010

通信路は、少なくとも行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置と、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置との間に設けられている。

0011

演算装置は、例えば積ABを求める場合には、記録部内の成分記録手段に、演算の対象となる行列Aのすべての成分amnと、当該成分に乗算する行列Bの成分bn1〜bnKとを記録する。計算部内の成分計算手段は、記録部の成分記録手段に記録された成分amnのそれぞれについて、amnbn1〜amnbnKを計算する。そして、記録部内のベクトル記録手段に、結果をK次元のベクトルcmn=(cmn1,cmn2,…,cmnK)=(amnbn1,amnbn2,…,amnbnK)として記録する。また、記録部内のτ記録手段に、τ=0を記録する。

0012

通信部内の送信手段は、あるnに対してベクトルcmp(mは1からM、pは(n−1−τ(mod N))+1)を記録部に有する場合に、(1)記録部のベクトル記録手段からベクトルcmpの第n成分を取り出し、(2)ベクトルcmq(qはp−1。ただし、p=1のときはq=N)を記録部に有する演算装置が当該演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmqを記録部に有する演算装置に送信する。通信部内の受信手段は、あるnに対してベクトルcmqを記録部に有し、かつ、ベクトルcmpを記録部に有する演算装置と異なる場合には、ベクトルcmpの第n成分を、ベクトルcmpを記録部に有する演算装置から受信する。

0013

計算部の演算結果記録手段は、あるnに対してベクトルcmqを記録部に有する場合に、(1)τ≦N−2のときは、記録部のベクトル記録手段からベクトルcmqの第n成分を取り出し、ベクトルcmpの第n成分との和を求め、結果をベクトルcmqの第n成分として記録部のベクトル記録手段に記録し、(2)τ>N−2のときは、ベクトルcmpの第n成分を、ベクトルcmqの第n成分として記録部のベクトル記録手段に記録する。
τ増加手段は、τにτ+1を代入して記録部のτ記録手段に記録する。繰り返し手段は、τが2N−3以下の場合は、演算を繰り返させる。

発明の効果

0014

本発明によれば、行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置は、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、または成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置としか通信しない。したがって、これらの通信路を確保するネットワークを構築するだけでよい。なお、switching HUBなどのポート数が安価な範囲であれば、これらの通信路以外の通信路を構築しても、本発明の目的である経済的なネットワーク構築を達成することができる。

発明を実施するための最良の形態

0015

以下では、説明の重複を避けるため同じ機能を有する構成部や同じ処理を行う処理ステップには同一の番号を付与し、説明を省略する。

0016

[第1実施形態]
原理1−1
図4に、4個の演算装置を用いて4個の4次元ベクトルの和を求める方法の原理を示す。この並列演算システムは、演算装置1000、1100、1200、1300と、隣り合う演算装置とをつなぐ通信路から構成されている。図中の○内の数字xは、処理の順番を示しており、以下では第xの処理と表現する。なお、同じ番号は同時に(並列に)行う処理を示している。あらかじめ、演算装置1000がベクトルc1を、演算装置1100がベクトルc2を、演算装置1200がベクトルc3を、演算装置1300がベクトルc4を記録している。

0017

第1の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc1の第1成分c11を演算装置1300に送信するとともに、ベクトルc2の第2成分c21を演算装置1100から受信する。演算装置1100は、ベクトルc2の第2成分c22を演算装置1000に送信するとともに、ベクトルc3の第3成分c33を演算装置1200から受信する。演算装置1200は、ベクトルc3の第3成分c33を演算装置1100に送信するとともに、ベクトルc4の第4成分c44を演算装置1300から受信する。演算装置1300は、ベクトルc4の第4成分c44を演算装置1200に送信するとともに、ベクトルc1の第1成分c11を演算装置1000から受信する。

0018

第2の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc1の第2成分c12と受信したベクトルc2の第2成分c22との和を、ベクトルc1の第2成分c12として記録する。演算装置1100は、ベクトルc2の第3成分c23と受信したベクトルc3の第3成分c33との和を、ベクトルc2の第3成分c23として記録する。演算装置1200は、ベクトルc3の第4成分c34と受信したベクトルc4の第4成分c44との和を、ベクトルc3の第4成分c34として記録する。演算装置1300は、ベクトルc4の第1成分c41と受信したベクトルc1の第1成分c11との和を、ベクトルc4の第1成分c41として記録する。

0019

第1の処理と第2の処理によって、演算前のベクトルc4とベクトルc1の第1成分の合計c41+c11が、演算装置1300にベクトルc4の第1成分として記録されている。第3の処理から第6の処理は、第1の処理と第2の処理の繰り返しである。第3の処理と第4の処理が終了すると、演算前のベクトルc3とベクトルc4とベクトルc1の第1成分の合計c31+c41+c11が、演算装置1200にベクトルc3の第1成分として記録される。第5の処理と第6の処理が終了すると、演算前のベクトルc2とベクトルc3とベクトルc4とベクトルc1の第1成分の合計c21+c31+c41+c11が、演算装置1100にベクトルc2の第1成分として記録される。つまり、第6の処理までで、ベクトルの各成分の合計は求められている。ただし、第1成分の合計は演算装置1100、第2成分の合計は演算装置1200、第3成分の合計は演算装置1300、第4成分の合計は演算装置1000がそれぞれ記録している。

0020

第7の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc1の第4成分c14(第4成分の合計)を演算装置1300に送信するとともに、ベクトルc2の第1成分c21(第1成分の合計)を演算装置1100から受信する。演算装置1100は、ベクトルc2の第1成分c21(第1成分の合計)を演算装置1000に送信するとともに、ベクトルc3の第2成分c32(第2成分の合計)を演算装置1200から受信する。演算装置1200は、ベクトルc3の第2成分c32(第2成分の合計)を演算装置1100に送信するとともに、ベクトルc4の第3成分c43(第3成分の合計)を演算装置1300から受信する。演算装置1300は、ベクトルc4の第3成分c43(第3成分の合計)を演算装置1200に送信するとともに、ベクトルc1の第4成分c14(第4成分の合計)を演算装置1000から受信する。

0021

第8の処理では、以下の処理を並列に行う。演算装置1000は、受信したベクトルc2の第1成分c21(第1成分の合計)を、ベクトルc1の第1成分c11として記録する。演算装置1100は、受信したベクトルc3の第2成分c32(第2成分の合計)を、ベクトルc2の第2成分c22として記録する。演算装置1200は、受信したベクトルc4の第3成分c43(第3成分の合計)を、ベクトルc3の第3成分c33として記録する。演算装置1300は、受信したベクトルc1の第4成分c14(第1成分の合計)を、ベクトルc4の第4成分c44として記録する。

0022

第7の処理と第8の処理によって、第1成分の合計は演算装置1100から演算装置1000に分配され、第2成分の合計は演算装置1200から演算装置1100に分配され、第3成分の合計は演算装置1300から演算装置1200に分配され、第4成分の合計は演算装置1000から演算装置1300に分配された。第9の処理から第12の処理は、第7の処理と第8の処理の繰り返しである。この繰り返しによって、各成分の合計はすべての演算装置に分配される。

0023

原理1−2
図5に、4個の演算装置を用いて5個の5次元ベクトルの和を求める方法の原理を示す。あらかじめ、演算装置1000がベクトルc1とc5を、演算装置1100がベクトルc2を、演算装置1200がベクトルc3を、演算装置1300がベクトルc4を記録している。

0024

第1の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc5の第5成分c55を演算装置1300に送信するとともに、ベクトルc2の第2成分c22を演算装置1100から受信する。演算装置1100は、ベクトルc2の第2成分c22を演算装置1000に送信するとともに、ベクトルc3の第3成分c33を演算装置1200から受信する。演算装置1200は、ベクトルc3の第3成分c33を演算装置1100に送信するとともに、ベクトルc4の第4成分c44を演算装置1300から受信する。演算装置1300は、ベクトルc4の第4成分c44を演算装置1200に送信するとともに、ベクトルc5の第5成分c55を演算装置1000から受信する。この処理では、ベクトルc1とベクトルc5を記録している演算装置が同じなので、ベクトルc1を記録している演算装置からベクトルc5を記録している演算装置へのベクトルc1の第1成分c11の送信は行わない。

0025

第2の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc1の第2成分c12と受信したベクトルc2の第2成分c22との和を、ベクトルc1の第2成分c12として記録する。さらに、演算装置1000は、ベクトルc5の第1成分c51とベクトルc1の第1成分c11との和を、ベクトルc5の第1成分c51として記録する。演算装置1100は、ベクトルc2の第3成分c23と受信したベクトルc3の第3成分c33との和を、ベクトルc2の第3成分c23として記録する。演算装置1200は、ベクトルc3の第4成分c34と受信したベクトルc4の第4成分c44との和を、ベクトルc3の第4成分c34として記録する。演算装置1300は、ベクトルc4の第5成分c45と受信したベクトルc5の第5成分c55との和を、ベクトルc4の第5成分c45として記録する。

0026

第3の処理から第8の処理は、第1の処理と第2の処理の繰り返しである。第8の処理が終了すると、第1成分の合計は演算装置1100、第2成分の合計は演算装置1200、第3成分の合計は演算装置1300、第4成分の合計は演算装置1000、第5成分の合計は演算装置1000がそれぞれ記録している。

0027

第9の処理では、以下の処理を並列に行う。演算装置1000は、ベクトルc5の第4成分c54(第4成分の合計)を演算装置1300に送信するとともに、ベクトルc2の第1成分c21(第1成分の合計)を演算装置1100から受信する。演算装置1100は、ベクトルc2の第1成分c21(第1成分の合計)を演算装置1000に送信するとともに、ベクトルc3の第2成分c32(第2成分の合計)を演算装置1200から受信する。演算装置1200は、ベクトルc3の第2成分c32(第2成分の合計)を演算装置1100に送信するとともに、ベクトルc4の第3成分c43(第3成分の合計)を演算装置1300から受信する。演算装置1300は、ベクトルc4の第3成分c43(第3成分の合計)を演算装置1200に送信するとともに、ベクトルc5の第4成分c54(第4成分の合計)を演算装置1000から受信する。この処理では、ベクトルc1とベクトルc5を記録している演算装置が同じなので、ベクトルc1を記録している演算装置からベクトルc5を記録している演算装置へのベクトルc1の第5成分c15の送信は行わない。

0028

第10の処理では、以下の処理を並列に行う。演算装置1000は、受信したベクトルc2の第1成分c21(第1成分の合計)を、ベクトルc1の第1成分c11として記録する。さらに、演算装置1000は、ベクトルc1の第5成分c15(第5成分の合計)を、ベクトルc5の第5成分c55として記録する。演算装置1100は、受信したベクトルc3の第2成分c32(第2成分の合計)を、ベクトルc2の第2成分c22として記録する。演算装置1200は、受信したベクトルc4の第3成分c43(第3成分の合計)を、ベクトルc3の第3成分c33として記録する。演算装置1300は、受信したベクトルc1の第4成分c14(第1成分の合計)を、ベクトルc4の第4成分c44として記録する。
第11の処理から第16の処理は、第9の処理と第10の処理の繰り返しである。この繰り返しによって、各成分の合計はすべての演算装置に分配される。

0029

原理2
図6に、4行4列の行列Aと4行4列の行列Bとの積ABを求める場合と積BAを求める場合の原理を示す。図6(A)は積ABを求める場合を示し、図6(B)は積BAを求める場合を示している。
図6(A)の内容を説明する。行列Aのm行n列の成分をamn、行列Bのm行n列の成分をbmnとすると、積ABのm行n列の成分は、am1b1n+am2b2n+am3b3n+am4b4nとなる。行列の積を求める並列演算システムが、行列Aの成分amnごとに演算する演算装置を決めるとする。このような並列演算システムでは、例えば、積a11b11は、成分a11の演算を行う演算装置(言い換えると、記録部に成分a11を有する演算装置)が計算する。この演算装置は、積a11b12、積a11b13、積a11b14の計算も行うので、これらの結果を成分とする4次元ベクトル(a11b11,a11b12,a11b13,a11b14)を記録部に記録することとなる。積ABの1行目を構成する4次元ベクトルは、成分a11の演算を行う演算装置の結果(a11b11,a11b12,a11b13,a11b14)、成分a12の演算を行う演算装置の結果(a12b21,a12b22,a12b23,a12b24)、成分a13の演算を行う演算装置の結果(a13b31,a13b32,a13b33,a13b34)、成分a14の演算を行う演算装置の結果(a14b41,a14b42,a14b43,a14b44)の和である。そして、cmn=(amnbn1,amnbn2,amnbn3,amnbn4)とすれば、積ABのm行目を構成するベクトルは、cm1+cm2+cm3+cm4となる。なお、このような行列の計算では、各行でcm1+cm2+cm3+cm4の計算を行うので、N個のK次元ベクトルの和をM組並列に計算することになる。

0030

図6(B)の内容を説明する。行列Aのm行n列の成分をamn、行列Bのm行n列の成分をbmnとすると、積BAのm行n列の成分は、bm1a1n+bm2a2n+bm3a3n+bm4a4nとなる。行列の積を求める並列演算システムが、行列Aの成分amnごとに演算する演算装置を決めるとする。このような並列演算システムでは、例えば、積b11a11は、成分a11の演算を行う演算装置(言い換えると、記録部に成分a11を有する演算装置)が計算する。この演算装置は、積b21a11、積b31a11、積b41a11の計算も行うので、これらの結果を成分とする4次元ベクトル(b11a11,b21a11,b31a11,b41a11)Tを記録部に記録することとなる。積ABの1列目を構成する4次元ベクトルは、成分a11の演算を行う演算装置の結果(b11a11,b21a11,b31a11,b41a11)T、成分a12の演算を行う演算装置の結果(b12a21,b22a21,b32a21,b42a21)T、成分a13の演算を行う演算装置の結果(b13a31,b23a31,b33a31,b43a31)T、成分a14の演算を行う演算装置の結果(b14a41,b24a41,b34a41,b44a41)Tの和である。そして、dmn=(b1mamn,b2mamn,b3mamn,b4mamn)Tとすれば、積BAのn列目を構成するベクトルは、d1n+d2n+d3n+d4nとなる。なお、このような行列の計算では、各列でd1n+d2n+d3n+d4nの計算を行うので、M個のK次元ベクトルの和をN組並列に計算することになる。

0031

演算装置の構成
図7に、複数の演算装置を用いて、行列の積を求める並列演算システムの構成例を示す。この並列演算システムは、演算装置1000、1100、1200、1300と、隣り合う演算装置とをつなぐ通信路から構成されている。各演算装置1000、1100、1200、1300は、計算部1010、1110、1210、1310と記録部1020、1120、1220、1320と通信部1030、1130、1230、1330とを備えている。図8に、I個の演算装置を用いて、M行N列の行列AとN行K列の行列Bとの積ABを求める場合の、1つの演算装置1000の機能構成例を示す。演算装置1000は、計算部1010、記録部1020、通信部1030から構成される。計算部1010は、τ増加手段1001、繰り返し手段1002、成分計算手段1011、演算結果記録手段1012を備える。なお、τ増加手段1001と繰り返し手段1002は、計算部1010以外の構成部(たとえば、図示していないが制御部などの構成部が考えられる。)が備えてもよい。記録部1020は、成分記録手段1021、ベクトル記録手段1022、τ記録手段1023を有する。通信部1030は、送信手段1031と受信手段1032とを有する。なお、他の演算装置も同じ機能構成である。

0032

演算方法
図9に、I個の演算装置を用いて、M行N列の行列AとN行K列の行列Bとの積ABを求める場合の処理フローを示す。
あらかじめ、行列AのMN個の成分amnをI個のグループに分けておき、各演算装置(1000など)が、i番目のグループのすべての成分amnと、当該成分に乗算する行列Bの成分bn1〜bnKとを記録部(1020など)の成分記録手段(1021など)に記録する(S110)。次に、各演算装置(1000など)が、(1)記録部(1020など)の成分記録手段(1021など)に記録された成分amnのそれぞれについて、計算部でamnbn1〜amnbnKを計算し、(2)結果をK次元のベクトルcmn=(cmn1,cmn2,…,cmnK)=(amnbn1,amnbn2,…,amnbnK)として記録部(1020など)のベクトル記録手段(1022など)に記録する(S115)。各演算装置(1000など)が、記録部(1020)のτ記録手段(1023など)にτ=0を記録する(S120)。

0033

ベクトルcmp(mは1からM、pは(n−1−τ(mod N))+1)を記録部(1020など)のベクトル記録手段(1022など)に有する各演算装置(1000など)が、(1)記録部(1020など)のベクトル記録手段(1022など)からベクトルcmpの第n成分を取り出し、(2)当該演算装置とベクトルcmq(qはp−1。ただし、p=1のときはq=N)を記録部に有する演算装置とが異なる場合(同じ演算装置がベクトルcmpとベクトルcmqとを記録していない場合)には、通信部(1030など)の送信手段(1031など)を用いてベクトルcmpの第n成分を、ベクトルcmqを記録部に有する演算装置に送信する(S130)。ベクトルcmqを記録部に有する各演算装置(1000など)が、当該演算装置とベクトルcmpを記録部に有する演算装置とが異なる場合には、通信部(1030など)の受信手段(1032など)を用いてベクトルcmpの第n成分を、ベクトルcmpを記録部に有する演算装置からそれぞれ受信する(S140)。

0034

ベクトルcmqを記録部に有する各演算装置(1000など)が、(1)τ≦N−2の場合は、当該演算装置の記録部(1020など)のベクトル記録手段(1022など)からベクトルcmqの第n成分を取り出し、当該演算装置の計算部(1010など)の演算結果記録手段(1012など)で、ベクトルcmpの第n成分との和を求め、結果をベクトルcmqの第n成分として記録部(1020など)のベクトル記録手段(1022など)に記録し、(2)τ>N−2の場合は、ベクトルcmpの第n成分を、ベクトルcmqの第n成分として記録部(1020など)のベクトル記録手段(1022など)に記録する(S150)。

0035

各演算装置(1000など)が、τにτ+1を代入して記録部(1020など)のτ記録手段(1023など)に記録する(S160)。各演算装置(1000など)の折り返し手段(1002など)が、τが2N−3以下の場合は処理フローをステップS130に戻し、それ以外の場合は処理を終了させる(S170)。
このような処理によるので、行列と行列の積を求める並列演算を、通信路を少なくしながら実現できる。

0036

演算方法2
図10に、I個の演算装置を用いて、M行N列の行列AとK行M列の行列Bとの積BAを求める場合の処理フローを示す。
あらかじめ、行列AのMN個の成分amnをI個のグループに分けておき、各演算装置(1000など)が、i番目のグループのすべての成分amnと、当該成分に乗算する行列Bの成分b1m〜bKmとを記録部(1020など)の成分記録手段(1021など)に記録する(S210)。次に、各演算装置(1000など)が、(1)記録部(1020など)の成分記録手段(1021など)に記録された成分amnのそれぞれについて、計算部でb1mamn〜bKmamnを計算し、(2)結果をK次元のベクトルdmn=(dmn1,dmn2,…,dmnK)T=(amnbn1,amnbn2,…,amnbnK)Tとして記録部(1020など)のベクトル記録手段(1022など)に記録する(S215)。各演算装置(1000など)が、記録部(1020)のτ記録手段(1023など)にτ=0を記録する(S220)。

0037

ベクトルcpn(nは1からN、pは(m−1−τ(mod M))+1)を記録部(1020など)のベクトル記録手段(1022など)に有する各演算装置(1000など)が、(1)記録部(1020など)のベクトル記録手段(1022など)からベクトルdpnの第m成分を取り出し、(2)当該演算装置とベクトルcqn(qはp−1。ただし、p=1のときはq=M)を記録部に有する演算装置とが異なる場合(同じ演算装置がベクトルdpnとベクトルdqnとを記録していない場合)には、通信部(1030など)の送信手段(1031など)を用いてベクトルdpnの第m成分を、ベクトルdqnを記録部に有する演算装置に送信する(S230)。ベクトルdqnを記録部に有する各演算装置(1000など)が、当該演算装置とベクトルdpnを記録部に有する演算装置とが異なる場合には、通信部(1030など)の受信手段(1032など)を用いてベクトルdpnの第m成分を、ベクトルdpnを記録部に有する演算装置からそれぞれ受信する(S240)。

0038

ベクトルdqnを記録部に有する各演算装置(1000など)が、(1)τ≦M−2の場合は、当該演算装置の記録部(1020など)のベクトル記録手段(1022など)からベクトルdqnの第m成分を取り出し、当該演算装置の計算部(1010など)の演算結果記録手段(1012など)で、ベクトルdpnの第m成分との和を求め、結果をベクトルdqnの第m成分として記録部(1020など)のベクトル記録手段(1022など)に記録し、(2)τ>M−2の場合は、ベクトルcpnの第m成分を、ベクトルcqnの第m成分として記録部(1020など)のベクトル記録手段(1022など)に記録する(S250)。

0039

各演算装置(1000など)が、τにτ+1を代入して記録部(1020など)のτ記録手段(1023など)に記録する(S260)。各演算装置(1000など)の折り返し手段(1002など)が、τが2N−3以下の場合は処理フローをステップS230に戻し、それ以外の場合は処理を終了する(S270)。
このような処理によるので、行列と行列の積を求める並列演算を、通信路を少なくしながら実現できる。

0040

ネットワーク構成例1
図11に、複数の演算装置を用いて行列の積を求める並列演算システムのネットワーク構成例を示す。このシステムでは、演算装置2110は、行列Aの1行1列の成分a11に関わる計算を行う演算装置であって、機能構成は、図8の演算装置1000と同じである。演算装置2120は、行列Aの1行2列の成分a12に関わる計算を行う。同様に演算装置2mn0は、行列Aのm行n列の成分amnに関わる計算を行う。通信路3012は、演算装置2110と演算装置2120間の通信路である。なお、図11では16個の演算装置の例を示しているが、演算装置の数はこれに限定されるわけではない。上述の演算方法1および演算方法2を実現するためには、少なくとも行列Aのm行n列目の成分amn(mは1〜Mの整数、nは1〜Nの整数)の演算を行う演算装置と、成分a(m−1)n(ただし、m−1=0の場合はaMn)、成分a(m+1)n(ただし、m+1=M+1の場合はa1n)、成分am(n−1)(ただし、n−1=0の場合はamN)、成分am(n+1)(ただし、n+1=N+1の場合はan1)の演算を行う演算装置との間に通信路を設ければよい。図11のネットワークは最低限必要な通信路を確保した構成となっている。したがって、この構成例の場合、各演算装置は4つの通信ポートを有していれば良い。

0041

このように通信路を構築すると、行列の行方向の演算装置間に構築した通信路によって、行方向のリング状のネットワークが出来上がる。また、列方向もリング状のネットワークが出来上がる。つまり、本発明の行列の並列演算方法では、トーラスネットワーク(2つのリング状のネットワーク)が構築できていれば良い。

0042

また、図11では、1つの成分amnごとに1つの演算装置を示しているが、1つの演算装置が2つ以上の成分amnに関わる計算をしても良い。このように2つ以上の成分amnに関わる計算を1つの演算装置で行う場合には、演算装置が同じという理由で、通信路が不要な場合もある。したがって、行列Aのm行n列目の成分amnの演算を行う演算装置が、成分a(m−1)n、成分a(m+1)n、成分am(n−1)、成分am(n+1)の演算を行ういずれかの演算装置と異なる場合には、前記通信路が、少なくとも行列Aのm行n列目の成分amnの演算を行う演算装置と、成分a(m−1)n、成分a(m+1)n、成分am(n−1)、成分am(n+1)の演算を行う異なる演算装置との間に設けられていればよい。

0043

ネットワーク構成例2
図12に、複数の演算装置を用いて行列の積を求める並列演算システムのネットワーク構成例を示す。ネットワーク4010は、行列Aの1列目の成分a1nの演算を行う演算装置間をつなぐ完全グラフのネットワークである。また、ネットワーク4100は、行列Aの1列目の成分am1の演算を行う演算装置間をつなぐ完全グラフのネットワークである。各演算装置は、2つの通信ポートを有し、2つの完全グラフのネットワークと接続されれば、上述の演算方法1と演算方法2を実現できる。なお、switching HUBなどのポート数が安価な範囲であれば、本構成例のように完全グラフのネットワークを構築しても、本発明の効果を得られる。このネットワークは、トーラスネットワークを含むネットワーク構成となっている。
以下の説明では、図を簡略化するために、図12の構成を図13のように示す。図13は、図12のネットワークを示す部分を省略した図であって、図12と同じ意味を示している。

0044

ネットワーク構成例3
図14に、ネットワーク構成例1とネットワーク構成例2とを組み合わせた構成例を示す。ネットワーク4010’は、演算装置2110、2120、2130間で完全グラフのネットワークである。そして、演算装置2140と演算装置2130、および演算装置2140と演算装置2110の間には通信路3034、3041が個別に設けられている。ネットワーク4100’は、演算装置2110、2210、2310間で完全グラフのネットワークである。そして、演算装置2410と演算装置2310、および演算装置2410と演算装置2110の間には通信路3434、3441が個別に設けられている。演算装置2410、2420、2430、2440の間は、個別の通信路が設けられ、リング状のネットワークが構築されている。また、演算装置2140、2240、2340、2440に間には、個別の通信路が設けられ、リング状のネットワークが構築されている。

0045

図14の構成例では演算装置は4×4個であり、演算装置の数は多くはないが、本構成例は演算装置の数が多くなった場合に有効である。例えば、25×25個の演算装置を用いる場合であって、安価なswitching HUBのポート数が24個のときには、25個の演算装置間で完全グラフのネットワークを構築することは非経済的である。そのような場合に、24個の演算装置間では完全グラフのネットワークを構築し、残りの1つの演算装置は個別の通信路を、通信が必要な演算装置との間のみに構築すればよい。
本構成例のように完全グラフのネットワークと個別の通信路とを組み合わせたネットワークを構築しても、本発明の効果を得られる。このネットワークも、トーラスネットワークを含むネットワーク構成となっている。

0046

ネットワーク構成例4
図15に、複数の演算装置を用いて行列の積を求める並列演算システムのネットワーク構成例を示す。ネットワーク5010は、行列Aの1行目の成分a1nの演算を行う演算装置間と1列目の成分am1の演算を行う演算装置間とをつなぐ完全グラフのネットワークである。本発明の演算方法では、行と列の間で通信する必要はないが、安価なswitching HUBのポートが余っている場合などに有効なネットワーク構成である。このネットワークも、トーラスネットワークを含むネットワーク構成となっている。また、このネットワークはネットワーク構成例2も含むネットワーク構成となっている。

0047

ネットワーク構成例5
図16に、複数の演算装置を用いて行列の積を求める並列演算システムのネットワーク構成例を示す。ネットワーク6010は、行列Aの1行目の成分a1nの演算を行う演算装置間、2行目の成分a2nの演算を行う演算装置間、1列目の成分am1の演算を行う演算装置間、2列目の成分am1の演算を行う演算装置間をつなぐ完全グラフのネットワークである。演算装置の数が、安価なswitching HUBのポート数よりも少し多く、2つのswitching HUBを用いる場合に有効である。このネットワークも、トーラスネットワークを含むネットワーク構成となっている。また、このネットワークはネットワーク構成例2も含むネットワーク構成となっている。

0048

ネットワーク構成例6
図17に、複数の演算装置を用いて行列の積を求める並列演算システムのネットワーク構成例を示す。この構成例は、図16の構成例よりも演算装置が多くなった場合の例を示している。図16と同じように、ネットワーク6010は、行列Aの1行目の成分a1nの演算を行う演算装置間、2行目の成分a2nの演算を行う演算装置間、1列目の成分am1の演算を行う演算装置間、2列目の成分am1の演算を行う演算装置間をつなぐ完全グラフのネットワークである。本発明の演算方法では、他の行や列の間で通信する必要はないが、安価なswitching HUBのポートが余っている場合などに有効である。このネットワークも、トーラスネットワークを含むネットワーク構成となっている。また、このネットワークはネットワーク構成例2も含むネットワーク構成となっている。

0049

なお、上記の実施形態は、図18に示すコンピュータ8000の記録部8020に読み込ませたプログラムによって、制御部8010、記録部8020、通信部8030などに上記方法の各ステップを実行させることができる。また、コンピュータに読み込ませる方法としては、プログラムをコンピュータ読み取り可能な記録媒体に記録しておき、記録媒体からコンピュータに読み込ませる方法、サーバ等に記録されたプログラムを、電気通信回線等を通じてコンピュータに読み込ませる方法などがある。

0050

本発明は、行列の積を求める演算を用いる大規模な情報処理システムに利用できる。例えば、暗号を用いたセキュリティシステムの安全性評価システムなどに利用できる。

図面の簡単な説明

0051

従来の方法を実現するシステム構成例を示す図。
従来の情報の収集の様子を示す図。
従来の情報の分配の様子を示す図。
4個の演算装置を用いて4個の4次元ベクトルの和を求める方法の原理を示す図。
4個の演算装置を用いて5個の5次元ベクトルの和を求める方法の原理を示す図。
4行4列の行列Aと4行4列の行列Bとの積ABを求める場合と積BAを求める場合の原理を示す図。
複数の演算装置を用いて、行列の積を求める並列演算システムの構成例を示す図。
演算装置の機能構成例を示す図。
I個の演算装置を用いて、M行N列の行列AとN行K列の行列Bとの積ABを求める場合の処理フローを示す図。
I個の演算装置を用いて、M行N列の行列AとK行M列の行列Bとの積BAを求める場合の処理フローを示す図。
複数の演算装置を用いて行列の積を求める並列演算システムの第1のネットワーク構成例を示す図。
複数の演算装置を用いて行列の積を求める並列演算システムの第2のネットワーク構成例を示す図。
図12のネットワークを示す部分を省略した図。
複数の演算装置を用いて行列の積を求める並列演算システムの第3のネットワーク構成例を示す図。
複数の演算装置を用いて行列の積を求める並列演算システムの第4のネットワーク構成例を示す図。
複数の演算装置を用いて行列の積を求める並列演算システムの第5のネットワーク構成例を示す図。
複数の演算装置を用いて行列の積を求める並列演算システムの第6のネットワーク構成例を示す図。
コンピュータの機能構成例を示す図。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • テスラ,インコーポレイテッドの「 加速数学エンジン」が 公開されました。( 2020/09/24)

    【課題・解決手段】本開示の様々な実施形態は、加速数学エンジンに関する。特定の実施形態では、ALU、出力レジスタおよびシャドーレジスタを含むサブ回路を含む2次元行列プロセッサを使用することにより画像の畳... 詳細

  • 株式会社東芝の「 ニューラルネットワーク装置」が 公開されました。( 2020/09/24)

    【課題】効率良くデータ転送を可能としつつ、トラフィックの停滞を軽減する。【解決手段】ニューラルネットワーク装置は、複数のコアと、複数のルータと、ツリー経路と、ショートカット経路とを備える。複数のコアは... 詳細

  • 富士ゼロックス株式会社の「 マルチプロセッサシステム」が 公開されました。( 2020/09/24)

    【課題】第2のプロセッサを従来技術より早く起動する。【解決手段】少なくとも第1のプロセッサと第2のプロセッサとを含むマルチプロセッサシステムでは、 第1のプロセッサが実行する第1のプログラムと第2のプ... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ