(57)【要約】【課題】  多くの汎用な処理に適用可能な、優れた高速処理性能を有する計算処理を可能とし、特に行列の固有値・固有ベクトルの解法において、高い並列実行性能を有する計算処理を可能とする。【解決手段】  ベクトルデータは、複数の並列処理を行う要素計算機１０〜３０の分散データメモリＭＡに行分散される。各列ベクトルデータ１〜６は分割され、各要素計算機１０〜３０の分散データメモリＭＢに順次再（列）分散される。この状態で、各要素計算機１０〜３０では、再分散された分割データに対して所望の演算処理が行われる。処理後の分割データは、各要素計算機１０〜３０の分散データメモリＭＡに対応するベクトルデータとして逆分散される。並列実行性能が高い行分散方式を利用し、かつ、解法の並列性を引き出す列分散方式を利用して計算処理が実行されるため、計算処理を高速で行うことが可能となり、また、多くの汎用な計算処理にも適用可能である。【選択図】図２
2005135243.tif 000002
【特許請求の範囲】
【請求項１】
通信網によって接続された第１，第２及び第３のメモリを備えた要素計算機を複数有する並列計算機によって、ベクトルデータに対する計算処理を行う計算処理方法であって、
各要素計算機の第１のメモリにベクトルデータを行分散するステップ１，
このステップ１によって分散されたベクトルデータのうち、各要素計算機の第２のメモリによって指定されたベクトルデータを分割するとともに、該ベクトルデータと対応付けて各要素計算機の第３のメモリに順次再分散するステップ２，
このステップ２によって再分散された分割データに対して所望の計算処理を行うステップ３，
このステップ３によって計算処理が行われた分割データを、前記第１のメモリのベクトルデータのうち、前記第２のメモリによって指定されたベクトルデータとして逆分散するステップ４，
を含むことを特徴とする計算処理方法。
【請求項２】
前記ステップ３の計算処理が、前記ベクトルデータに対する再直交化のための計算処理であることを特徴とする請求項１記載の計算処理方法。
【請求項３】
前記再直交化のための計算処理が、行列の固有値ないし固有ベクトルを求める計算処理であることを特徴とする請求項２記載の計算処理方法。
【請求項４】
請求項１ないし３のいずれかに記載の計算処理方法を、コンピュータで実行させるためのプログラム。
【請求項５】
要素計算機を複数有する並列計算機を利用してベクトルデータに対する計算処理を行うためのデータ再分散機構であって、
前記各要素計算機が、
処理対象のベクトルデータが行分散されて格納される第１のメモリ，
この第１のメモリに分散されたベクトルデータのうち、再分散ないし逆分散の対象となるベクトルデータを、各要素計算機に対して共通に指定する第２のメモリ，
この第２のメモリによって指定されたベクトルデータを分割して再分散した分割データを、該当するベクトルデータと対応付けて格納するとともに、この分割データを、前記第１のメモリのベクトルデータのうち、前記第２のメモリによって指定されたベクトルデータとして逆分散するための第３のメモリ，
をそれぞれ備えており、
前記各要素計算機の第１，第２及び第３のメモリを通信網によって接続したことを特徴とするデータ再分散機構。
【請求項６】
請求項５記載のデータ再分散機構を利用して計算処理を行う計算処理装置であって、
前記第３のメモリに再分散された分割データに対して所望の計算処理を行うことを特徴とする計算処理装置。
【請求項７】
前記所望の計算処理が、前記ベクトルデータに対する再直交化のための計算処理であることを特徴とする請求項６記載の計算処理装置。
【請求項８】
前記再直交化のための計算処理が、行列の固有値ないし固有ベクトルを求める計算処理であることを特徴とする請求項７記載の計算処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算機を利用して計算処理を高速実行するための計算処理方法，そのプログラム，データ再分散機構，計算処理装置に関するものであり、例えば、線形代数学の線形変換における固有値や固有ベクトルの計算に好適な計算手法の改良に関するものである。
【背景技術】
【０００２】
並列計算機を利用して行列の固有値や固有ベクトルを計算するものとしては、例えば以下の特許文献１に記載されたものがある。これは、所定の基準によって複数の固有値をグループ化し、これらのグループを並列計算機を構成するプロセッサに分配して固有ベクトルを求める際に、必要以上の直交化を行っていることや、ハードウエアが有効に利用されないなどの不都合に着目したものである。この従来技術によれば、固有値のグループ化を行わず、個々の固有値について自分の固有値からの距離がある基準以下の範囲にある他の固有値に属する固有ベクトルと直交させるという手法が採用されている。
【特許文献１】特開平９−６７６０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、並列計算機を利用してデータ分散を行うことで固有値や固有ベクトルを計算するために必要とされる再直交化処理には、列分散方式というデータ分散方式が採用されている（例えば、下記非特許文献１参照）。しかし、この手法では、データ分散方式に起因して低い並列実行性能しか得られないという不都合がある。これに対し、並列実行性能が高い行分散方式という再直交化処理の方式が知られている。ところが、この行分散方式を採用すると、対象となる再直交化処理以外の処理が逐次化され、固有値・固有ベクトルの解法全体として並列実行性能が低下してしまうという問題点がある。
【非特許文献１】片桐孝洋著，2003年ハイパフォーマンスコンピューティングと計算科学シンポジウム(HPCS2003），HPCS2003論文集(IPSJ Symposium Series Vol.2003, No.4)，pp.75--82，ＩＳＳＮ１３４４−０４６０，社団法人情報処理学会，２００３年１月２０日発行，「スーパーコンピュータ環境におけるGram-Schmidt再直交化の性能評価」
【０００４】
本発明は、以上の点に着目したもので、その目的は、優れた高速処理性能を有する計算処理を可能とすることである。他の目的は、多くの汎用な処理に適用可能な計算処理を可能とすることである。更に他の目的は、固有値・固有ベクトルの解法において、高い並列実行性能を有する計算処理を可能とすることである。
【課題を解決するための手段】
【０００５】
前記目的を達成するため、本発明は、通信網によって接続された第１，第２及び第３のメモリを備えた要素計算機を複数有する並列計算機によって、ベクトルデータに対する計算処理を行う場合に、各要素計算機の第１のメモリにベクトルデータを行分散するとともに、分散されたベクトルデータのうち、各要素計算機の第２のメモリによって指定されたベクトルデータを分割して、該ベクトルデータと対応付けて各要素計算機の第３のメモリに順次再分散し、更に、分割データを、前記第１のメモリのベクトルデータのうち、前記第２のメモリによって指定されたベクトルデータとして逆分散することを特徴とする。
【０００６】
主要な形態によれば、前記再分散された分割データに対して所望の計算処理が行われる。他の形態によれば、前記計算処理が、前記ベクトルデータに対する再直交化のための計算処理であることを特徴とする。更に他の形態によれば、前記再直交化のための計算処理が、行列の固有値ないし固有ベクトルを求める計算処理であることを特徴とする。本発明の前記及び他の目的，特徴，利点は、以下の詳細な説明及び添付図面から明瞭になろう。
【発明の効果】
【０００７】
本発明によれば、優れた高速性能を有する計算処理が可能となるとともに、多くの汎用な処理に適用可能であり、特に固有値・固有ベクトルの解法において高い並列実行性能を有する。
【発明を実施するための最良の形態】
【０００８】
以下、本発明を実施するための最良の形態を、実施例に基づいて詳細に説明する。
【実施例１】
【０００９】
<データ再分散機構の基本構成>・・・最初に、図１〜図９を参照しながら本発明の実施例１を説明する。図１には、本実施例のデータ再分散機構の全体構成が示されている。この例は、並列処理を行う３台の要素計算機（ＰＥ（Processing Element））１０，２０，３０からなる並列計算機によってデータ再分散機構を構成した例である。これらのうち、要素計算機１０は、ＣＰＵ（中央演算装置（Central Processing Unit））１２を中心に構成されており、更に、分散データメモリ１４，１６を備えている。これらの分散データメモリ１４，１６に対しては、ＣＰＵ１２からデータの書き込み，読み出しが可能となっている。
【００１０】
分散データメモリ１４には、長さが「ｎ」のベクトルデータを複数本、書き込むことができるようになっている。図示の例では、ベクトルデータ１及び２が書き込まれている。ベクトルデータ１は、「Ｄ11，Ｄ21，Ｄ31，・・・，Ｄn1」であり、ベクトルデータ２は、「Ｄ12，Ｄ22，Ｄ32，・・・，Ｄn2」という具合である。初期状態では、分散データメモリ１４にのみ、ベクトルデータ１，２が存在し、分散データメモリ１６は空となっている。図１は、この初期状態を示す。また、分散データメモリ１４，１６は、ＣＰＵ１２からデータ消去命令が発行されるまで、それぞれのデータを保持し続ける。
【００１１】
要素計算機２０，３０についても同様の構成となっている。図示の例では、要素計算機２０の分散データメモリ２４にはベクトルデータ３，４が格納されており、要素計算機３０の分散データメモリ３４にはベクトルデータ５，６が格納されている。ちょうど、Ｄij（ｉ＝１〜ｎ，ｊ＝１〜６）の行列の列ベクトルが、２つずつ要素計算機１０，２０，３０に行分散された格好となる。分散データメモリ１４，１６，２４，２６，３４，３６は、いずれも通信網５０と接続されており、相互にデータの授受が行われるように構成されている。
【００１２】
各要素計算機１０，２０，３０は、ＰＳＲ（Parallel Status Register）という並列制御情報を管理する特殊メモリ１８，２８，３８を備えている。これらＰＳＲ１８，２８，３８は、
(1)自分の認識番号「myid」（１からnprocs），
(2)全プロセッサ数「nprocs」（本例では３），
(3)分散データメモリ１４，２４，３４上のベクトルデータ１〜６の次元数「ｎ」，
(4)分散データメモリ１４，２４，３４上のベクトルデータ数「ｎｖ」（本例では６），
(5)現在再分散したい分散データメモリ１４，２４，３４のいずれかのグローバルなデータ番号「ＩＳ」（１からｎｖまで。各要素計算機１０，２０，３０間で重複しない番号），
(6)各要素計算機１０，２０，３０の分散データメモリ１４，２４，３４上で所有するグローバルなデータ番号リスト「ＩＬＬ」（各分散データメモリ１４，２４，３４上にあるベクトルデータ１〜６に関する、自分のプロセッサ内にある大域的な番号リスト，整数データのリスト），
などを管理している。なお、図１〜図７には、発明の理解を容易にするため、データ番号ＩＳの値のみを表示している。
【００１３】
ＰＳＲ１８，２８，３８に格納される一部の情報，例えば前記データ番号「ＩＳ」を保持するメモリは、通信網５０とつながっている。また、通信網５０につながったＰＳＲ１８，２８，３８上の情報は、各要素計算機間で共有化された情報であり、各要素計算機１０，２０，３０がこれらのメモリ内容を書き換えると、並列計算機全体としてその値に関する整合性がとられる。すなわち、ある要素計算機がＰＳＲ上の共有化されたメモリに値を書き込むと、その書き込まれた値が並列計算機を構成するすべての要素計算機のＰＳＲに反映される。例えば、要素計算機１０のＰＳＲ１８に、データ番号「ＩＳ」として「１」がＣＰＵ１２によって書き込まれると、他の要素計算機２０，３０のＰＳＲ２８，３８のデータ番号「ＩＳ」も「１」に書き換えられるという具合である。
【００１４】
<正データ再分散の動作>・・・次に、本実施例の基本的な動作態様である正データ再分散と逆データ再分散について説明する。最初に、正データ再分散の動作から説明する。分散データメモリ１４，２４，３４のいずれかから分散データメモリ１６，２６，３６に対するデータ再分散（列分散）を、正データ再分散と呼ぶ。図２には、その一例が示されており、要素計算機１０の分散データメモリ１４のベクトルデータ１が、矢印Ｆ11，Ｆ12，Ｆ13で示すように、要素計算機１０，２０，３０の分散データメモリ１６，２６，３６に順番に再分散されるという具合である。
【００１５】
図８には、正データ再分散の処理手順がフローチャートとして示されている。同図において、まず適宜のカウンタＪをセットするとともに（ステップＳＦ１）、指定されたデータ番号「ＩＳ」（図２ではＩＳ＝１）を所有するかどうかを各要素計算機１０，２０，３０で判断する（ステップＳＦ２）。その結果、図２のように要素計算機１０がデータ番号「ＩＳ＝１」のベクトルデータ１を所有する場合には（ステップＳＦ２のYes，ＳＦ３）、分散データメモリ１４におけるベクトルデータ１の要素中、「１＋（ｎ／nprocs）＊（Ｊ−１）」から「（ｎ／nprocs）＊Ｊ」までを、認識番号myidがカウンタＪの要素計算機に通信網５０を介して送信する。この動作は、カウンタＪが全プロセッサ数nprocs＋１となるまで、順次実行される（ステップＳＦ４，ＳＦ５）。すなわち、図２では、ベクトルデータ１が３分割され、それぞれ要素計算機１０，２０，３０の分散データメモリ１６，２６，３６に送信される（図２の矢印Ｆ11，Ｆ12，Ｆ13参照）。
【００１６】
一方、ステップＳＦ２において、要素計算機がデータ番号「ＩＳ＝１」のベクトルデータを所有しない場合（ステップＳＦ２のNo）、すなわち要素計算機２０及び３０については、要素計算機１０からの受信ベクトルデータを、分散データメモリ２６，３６に「ＩＳ＝１」番のデータとして対応付けを行って収納する。
【００１７】
このような動作を図２に沿ってまとめると、
(1)要素計算機１０は、分散データメモリ１４のベクトルデータ１の要素を、全プロセッサ数nprocs＝３で分割する。
(2)分割されたデータは、通信網５０を介して、要素計算機１０，２０，３０の分散データメモリ１６，２６，３６に順番に送信される。
(3)要素計算機１０，２０，３０では、受信した分割データを、データ番号「ＩＳ＝１」のデータとしてそれぞれ分散データメモリ１６，２６，３６に収納する（矢印Ｆ11，Ｆ12，Ｆ13参照）。
【００１８】
<逆データ再分散の動作>・・・次に、逆データ再分散の動作について説明する。一方、分散データメモリ１６，２６，３６から分散データメモリ１４，２４，３４上へのデータ再分散を、逆データ再分散と呼ぶ。図５には、その一例が示されており、要素計算機１０，２０，３０の分散データメモリ１６，２６，３６の分割データが、矢印Ｇ11，Ｇ12，Ｇ13で示すように、要素計算機１０の分散データメモリ１４に、演算後のベクトルデータ１として、順序だてて逆分散されるという具合である。
【００１９】
図９には、逆データ再分散の処理手順がフローチャートとして示されている。同図において、まず適宜のカウンタＫをセットするとともに（ステップＳＢ１）、指定されたデータ番号「ＩＳ」（図５ではＩＳ＝１）を所有するかどうかを各要素計算機１０，２０，３０で判断する（ステップＳＢ２）。その結果、要素計算機がデータ番号「ＩＳ＝１」のベクトルデータを所有しない場合（ステップＳＢ２のNo）、図５の例であれば要素計算機２０及び３０は、データ番号「ＩＳ＝１」の分割データを要素計算機１０に通信網５０を介して送信する（ステップＳＢ６）。一方、データ番号「ＩＳ＝１」のベクトルデータ１を有する要素計算機１０の場合は（ステップＳＢ２のYes）、カウンタ「Ｋ」の要素計算機１０からの受信データを、分散データメモリ１４におけるデータ番号「ＩＳ＝１」のベクトルデータ１の要素「１＋（ｎ／nprocs）＊（Ｋ−１）」から「（ｎ／nprocs）＊Ｋ」として収納する（ステップＳＢ３）。この動作は、カウンタＫが全プロセッサ数nprocs＋１となるまで、順次繰り返し実行される（ステップＳＢ４，ＳＢ５）。すなわち、３分割されたベクトルデータ１が、それぞれ要素計算機１０，２０，３０の分散データメモリ１６，２６，３６から要素計算機１０の分散データメモリ１４に送信され、ベクトルデータ１として収納される（図５の矢印Ｇ11，Ｇ12，Ｇ13参照）。
【００２０】
このような動作を図５に沿ってまとめると、
(1)要素計算機１０，２０，３０は、分散データメモリ１６，２６，３６に格納されているベクトルデータ１の分割データのうち、データ番号「ＩＳ＝１」に該当するものを、通信網５０を介して要素計算機１０に送信する（矢印Ｇ11，Ｇ12，Ｇ13参照）。
(2)要素計算機１０では、受信した分割データを、データ番号「ＩＳ＝１」のベクトルデータとして分散データメモリ１４に順序だてて収納する（矢印Ｇ11，Ｇ12，Ｇ13参照）。
【００２１】
以上の正データ再分散及び逆データ再分散の動作は、各ベクトルデータ１〜６について、順次実行される。そして、この動作は、ベクトルデータ１〜６のデータ番号ＩＳ＝１〜６をキーとして実行される。別言すれば、データ番号ＩＳが、いずれのベクトルデータに対する再分散処理なのかを示す各要素計算機共通の指標となっている。
【００２２】
<実施例の全体動作>・・・次に、本実施例の全体的動作を説明する。まず、図１に示すように、６つの列ベクトルデータ１〜６は、それぞれ要素計算機１０，２０，３０の分散データメモリ１４，２４，３４にそれぞれＣＰＵ１２，２２，３２によって分散収納される。分散後の状態が、図２に示されている。次に、各ベクトルデータ１〜６について、順次上述した正データ再分散の処理が行われる。まず、図２に示すように、ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝１」とされるとともに、ベクトルデータ１について正データ再分散がＣＰＵ１２，２２，３２によって行われ、ベクトルデータ１が３分割されて要素計算機１０，２０，３０の分散データメモリ１６，２６，３６にそれぞれ収納される（矢印Ｆ11，Ｆ12，Ｆ13参照）。
【００２３】
次に、図３に示すように，ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝２」とされるとともに、ベクトルデータ２について正データ再分散が行われ、ベクトルデータ２が３分割されて要素計算機１０，２０，３０の分散データメモリ１６，２６，３６にそれぞれ収納される（矢印Ｆ21，Ｆ22，Ｆ23参照）。同様に、ベクトルデータ３，４，５について、順次正データ分散処理が実行される。そして、最後に、図４に示すように、ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝６」とされるとともに、ベクトルデータ６について正データ再分散が行われ、ベクトルデータ６が３分割されて要素計算機１０，２０，３０の分散データメモリ１６，２６，３６にそれぞれ収納される（矢印Ｆ61，Ｆ62，Ｆ63参照）。このようにして、ベクトルデータの正データ分散処理が完了する。
【００２４】
この図４の状態で、各要素計算機１０，２０，３０の分散データメモリ１６，２６，３６上にある分割データを用いて、所望の計算処理が実行され、処理後の分割データに書き換えられる。図５には、ハッチングを換えてデータの書き換えの様子が示されている。なお、分散データメモリ１４，２４，３４のベクトルデータ１〜６は、そのままである。
【００２５】
次に、各要素計算機１０，２０，３０の分散データメモリ１６，２６，３６上にある分割データに対し、ＣＰＵ１２，２２，３２によって上述した逆データ分散処理が行われる。まず、図５に示すように、ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝１」とされるとともに、該当するベクトルデータ１について逆データ再分散が行われ、ベクトルデータ１の分割データが要素計算機１０，２０，３０の分散データメモリ１６，２６，３６から要素計算機１０の分散データメモリ１４に順序だてて収納される（矢印Ｇ11，Ｇ12，Ｇ13参照）。
【００２６】
次に、図６に示すように、ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝２」とされるとともに、ベクトルデータ２について逆データ再分散が行われ、ベクトルデータ２の分割データが要素計算機１０，２０，３０の分散データメモリ１６，２６，３６から要素計算機１０の分散データメモリ１４に順序だてて収納される（矢印Ｇ21，Ｇ22，Ｇ23参照）。同様に、ベクトルデータ３，４，５について、逆データ分散処理が順番に実行される。そして、最後に、図７に示すように、ＰＳＲ１８，２８，３８のデータ番号が「ＩＳ＝６」とされるとともに、ベクトルデータ６について逆データ再分散が行われ、ベクトルデータ６の分割データが要素計算機１０，２０，３０の分散データメモリ１６，２６，３６から要素計算機３０の分散データメモリ３４に順序だてて収納される（矢印Ｇ61，Ｇ62，Ｇ63参照）。
【００２７】
以上のように、本実施例によれば、
(1)ベクトルデータは、複数の並列処理を行う要素計算機の第１のメモリに行分散される。
(2)各列ベクトルデータは分割され、各要素計算機の第２のメモリに再分散される。
(3)この状態で、各要素計算機では、再分散された分割データに対して所望の演算処理が行われる。
(4)処理後の分割データは、各要素計算機の第１のメモリに逆分散される。
【００２８】
このように、並列実行性能が高い行分散方式を利用し、かつ、解法の並列性を引き出す列分散方式を利用して計算処理が実行されるため、計算処理を高速で行うことが可能となり、また、多くの汎用な計算処理にも適用可能である。
【実施例２】
【００２９】
次に、図１０のプログラム（擬似コード）を参照しながら、前記実施例１のデータ再分散機構を利用したベクトルの再直交化方法について説明する。図１０中、「<>」はプログラム行を示す。最初に、再直交化の対象ベクトルｘを、各要素計算機の分散データメモリＭＡ（前記実施例１ではメモリ１４，２４，３４に対応）に行分散して格納・登録する（<A1>参照）。次に、再直交化対象ベクトルの番号を、ＰＳＲのデータ番号「ＩＳ」として登録する（<A2>参照）。ここで、正データ再分散命令を発行し（<A3>参照）、ベクトルｘに対して上述した正データ再分散処理を実行する。これにより、ベクトルｘの分割データが、各要素計算機の分散データメモリＭＢ（前記実施例１ではメモリ１６，２６，３６に対応）に再分散される。この状態で、分散データメモリＭＢ上にある分割ベクトルデータを用いて、ベクトルｘの再直交化処理が行われる（<A4>参照）。処理後、逆データ再分散処理命令が発行され（<A5>参照）、再直交化処理後の分割ベクトルデータに対し、上述した逆データ再分散処理が実行される。これにより、各要素計算機の分散データメモリＭＡ上にあるベクトルｘが、新しい計算後のベクトルデータＸとなる（<A6>参照）。
【実施例３】
【００３０】
次に、図１１，図１２のプログラムを参照しながら、固有値・固有ベクトル計算のための逆反復法に再直交化処理を行う実施例３について説明する。この例は、実施例１のデータ再分散機構を活用し、更に実施例２に示した再直交化手法を実装した例である。図１１，図１２には、前記データ再分散機構を活用した固有値・固有ベクトルの計算手順の一例が示されている。図１１，図１２のプログラム中、点線で囲まれた処理において、実施例２に示した図１０の再直交化手法が利用されている。また、図１２は図１１に連続するプログラムである。
【００３１】
なお、図１１，図１２中における主要な変数の意味は、以下の通りである。
「np」：整数スカラー。各要素計算機が所有する固有ベクトルの本数が入る。
「myid」：整数スカラー。自分の要素計算機の認識番号（ＩＤ）が入る。
「lambda_l(i)」：実数スカラーで１次元配列。第ｉ固有値の下界が入る。
「lambda_u(i)」：実数スカラーで１次元配列。第ｉ固有値の上界が入る。
「hlambda_i」：実数スカラー。第ｉ固有値の推定値が入る。
「x_i」：実数ｎ次元ベクトル。第ｉ固有ベクトルが入る。
「T」：実数三重対角行列を表す。
「I」：単位行列を表す。
【００３２】
図１１，図１２のプログラムでは、よく知られている実数の三重対角行列Ｔにおける固有ベクトルを計算するアルゴリズムである逆反復法において、データ再分散機構を用いた再直交化手法を組み込むことで、新しい計算方式を実現している。これらの図中、<B10>，<B15>，<B25>の各行の処理で、点線で示すように、上述した正データ分散処理及び逆データ分散処理がそれぞれ行われる。
【００３３】
このような固有値・固有ベクトル計算を、８台の要素計算機を有するスーパーコンピュータを利用して行ったときの実行時間を計測したところ、図１３のような結果が得られた。図１３は、実施例１のデータ分散機構と同等の機能を提供するソフトウエアを通信ライブラリＭＰＩ（Message Passing Interface）を用いて作成した上で、そのソフトウエアを利用して図１０の再直交化方式を実現したプログラムの実行時間を示している。この図１０中、「ＭＧ−Ｓ」は、再直交化のアルゴリズムに修正Gram-Schmidt法を用いたものであり、「ＣＧ−Ｓ」は、再直交化のアルゴリズムに古典Gram-Schmidt法を用いたものである。計算する固有ベクトル数は全体で１０，０００個あり、そのうちの何％を計算したかという時間を秒単位で示している。
【００３４】
(1)修正Gram-Schmidt法・・・５％終了まで、従来方式では２０３秒かかるのに対し、本方式ではほぼ４倍高速の５６秒となっている。１００％終了時で比較しても、従来方式では６５，０１９秒かかるのに対し、本方式では１７，５５０秒となっている。
(2)古典Gram-Schmidt法・・・５％終了まで、従来方式では４０秒かかるのに対し、本方式では３０秒となっている。１００％終了時で比較すると、従来方式では１２，０４２秒かかるのに対し、本方式では６，１９３秒となっており、ほぼ２倍速い。
【００３５】
このように、本実施例によれば、逆反復法による固有値・固有ベクトル計算に上述したデータ再分散機構と再直交化方式を適用することで、固有値・固有ベクトルの計算処理速度が大幅に向上し、計算時間が短縮され、高い並列実行性能を有する計算処理が可能となる。また、上述したように、データ再分散機構により並列性の大幅な抽出に成功した結果、図１３の効果が得られた。従って、要素計算機の台数が増えるにつれ、更なる速度向上の効果が期待できる。
【実施例４】
【００３６】
次に、図１４を参照しながら本発明の実施例４について説明する。上述した実施例１では、まず、ベクトルデータ１〜６のすべてについて正データ再分散を行い、再分散後のデータに対して所望の計算処理を行った後に、ベクトルデータ１〜６のすべてについて逆データ再分散を行った。しかし、正データ分散と逆データ再分散の順序は、必ずしもすべてのベクトルデータに対して一度に行う必要はなく、正データ再分散や逆データ再分散は適宜行ってよい。
【００３７】
図１４には、前記実施例１とは異なる順序による再分散処理の例で、主要部のみを示している。最初、同図(A)に示すように、要素計算機１０，２０，３０の分散データメモリ１６，２６，３６に対して、分散データメモリ１４に格納されているベクトルデータ１の再分散が行われる（矢印Ｆ11，Ｆ12，Ｆ13参照）。この処理は、図２に示した処理と同じである。次に、本例では、ベクトルデータ１に対する正データ再分散の処理終了後に、分散データメモリ１６，２６，３６において、分割データに対して所望の処理が行われる。分散データメモリ１６，２６，３６には、ベクトルデータ１以外の分割データは存在しないので、ベクトルデータ１の分割データのみに対して所望の計算処理が施されることになる。処理後の分割データは、図１４(B)に矢印Ｈ11，Ｈ12，Ｈ13で示すように、分散データメモリ１６，２６，３６から分散データメモリ１４に逆データ再分散される。このとき、分散データメモリ１６，２６，３６には、分割データが消去されずにそのまま残る。
【００３８】
次に、図１４(C)に矢印Ｊ21，Ｊ22，Ｊ23で示すように、分散データメモリ１４のベクトルデータ２について、分散データメモリ１６，２６，３６に対する正データ再分散が行われる。そして、図１４(C)に点線で示すように、既に分散データメモリ１６，２６，３６にあるベクトルデータ１の処理後の分割データを参照して、正データ再分散されたベクトルデータ２の分割データに対する所望の計算処理が行われる。処理後のベクトルデータ２の分割データは、図１４(D)に矢印Ｋ21，Ｋ22，Ｋ23で示すように、分散データメモリ１６，２６，３６から分散データメモリ１４に逆データ再分散される。
【００３９】
以後、同様にして、正データ分散→計算処理→逆データ分散→正データ分散→・・・の動作が繰り返される。従って、ベクトルデータ１〜６の分割データをすべて利用して計算処理が行われるのは、ベクトルデータ６の正データ再分散後の１回のみとなる。上述したGram-Shmidt再直交化では、ベクトルが１本のときは、何の計算処理も行われないので、本実施例のような順序による動作でも、所望の計算結果を得ることができる場合がある。
【００４０】
なお、本発明は、上述した実施例に限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加え得ることができる。例えば、以下のものも含まれる。
(1)前記実施例に示した要素計算機の数などは、いずれも一例であり、必要に応じて増減してよい。また、各要素計算機のハードウエア構成も、同様の作用を奏するように変更してよい。
(2)ベクトルデータ要素の分割について、プロセッサ数でちょうど割り切れないときは、例えば余りのデータを最後の分割データに付加するようにする。
(3)上述したように、本発明は、ベクトルの再直交化処理や固有値・固有ベクトル計算処理に極めて効果的であるが、何らそれらの適用例に限定されるものではなく、他の各種の計算処理に適用してよい。
(4)前記実施例１では、すべてのベクトルデータに対して正データ再分散の処理を行った後に、各分割データに対して所望の計算処理を行い、すべての計算処理終了後に逆データ再分散の処理を行った。また、実施例４では、正データ再分散，計算処理，逆データ再分散を繰り返し行った。しかし、本発明は、何らそれらの順序に限定されるものではなく、計算対象に応じて適宜変更してよい。
【産業上の利用可能性】
【００４１】
本発明によれば、並列処理を行う複数の要素計算機に行分散されたベクトルデータを分割して、各要素計算機に再分散する。そして、この列分散した分割データに対して所望の計算処理を行い、計算後の分割データを逆分散する。このため、計算処理を高速で行うことが可能となり、特に行列の固有値・固有ベクトルの計算に好適である。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施例１の構成とベクトルデータの行分散の様子を示すブロック図である。
【図２】前記実施例１のベクトルデータ１に対する正データ再分散の様子を示す図である。
【図３】前記実施例１のベクトルデータ２に対する正データ再分散の様子を示す図である。
【図４】前記実施例１のベクトルデータ６に対する正データ再分散の様子を示す図である。
【図５】前記実施例１のベクトルデータ１に対する逆データ再分散の様子を示す図である。
【図６】前記実施例１のベクトルデータ２に対する逆データ再分散の様子を示す図である。
【図７】前記実施例１のベクトルデータ６に対する逆データ再分散の様子を示す図である。
【図８】前記実施例１の正データ再分散の処理手順を示すフローチャートである。
【図９】前記実施例１の逆データ再分散の処理手順を示すフローチャートである。
【図１０】本発明の実施例２のベクトル再直交化処理手順を示す図である。
【図１１】本発明の実施例３の固有値・固有ベクトル計算手順を示す図である。
【図１２】前記実施例３の固有値・固有ベクトル計算手順を示す図である。
【図１３】前記実施例３による計算時間を従来技術と比較した図である。
【図１４】本発明の実施例４におけるデータの再分散処理・逆分散処理の様子を示す図である。
【符号の説明】
【００４３】
１０，２０，３０：要素計算機
１２，２２，３２：ＣＰＵ
１４，１６，２４，２６，３４，３６:分散データメモリ
１８，２８，３８：ＰＳＲ
５０：通信網
【図１】
2005135243.tif 000003
【図２】
2005135243.tif 000004
【図３】
2005135243.tif 000005
【図４】
2005135243.tif 000006
【図５】
2005135243.tif 000007
【図６】
2005135243.tif 000008
【図７】
2005135243.tif 000009
【図８】
2005135243.tif 000010
【図９】
2005135243.tif 000011
【図１０】
2005135243.tif 000012
【図１１】
2005135243.tif 000013
【図１２】
2005135243.tif 000014
【図１３】
2005135243.tif 000015
【図１４】
2005135243.tif 000016