(57)【要約】  反復解法を用いた計算処理の中で、通信オーバーヘッドとして多くの時間を必要とすることを課題とし、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行し、計算処理が開始された後、通信部によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った旨を通知された場合または有意性を判定することが可能な状況に至ったか否かを問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、計算処理を中止する。
2009008086.tif 000002
【特許請求の範囲】
【請求項１】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算装置であって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手段と、
前記反復計算手段によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手段と、
前記有意性判定手段によって前記計算結果が有意であると判定された場合に、前記反復計算手段による計算処理を中止する中止手段と、
を備えたことを特徴とする計算装置。
【請求項２】
前記反復計算手段は、前記計算処理として、連立一次方程式における解ベクトルを反復して算出することを特徴とする請求項１に記載の計算装置。
【請求項３】
前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至った旨を前記通信部から通知された場合に、前記有意性を判定することを特徴とする請求項１記載の計算装置。
【請求項４】
前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせ、当該有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、前記有意性を判定することを特徴とする請求項１記載の計算装置。
【請求項５】
前記有意性判定手段は、前記計算処理における所定の進捗間隔ごとに、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせることを特徴とする請求項４に記載の計算装置。
【請求項６】
前記有意性判定手段は、前記計算処理において他の計算装置と通信が必要になる状況ごとに、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせることを特徴とする請求項４に記載の計算装置。
【請求項７】
前記反復計算手段は、前記計算結果を１回のみ余分に反復して算出することを特徴とする請求項１〜６のいずれか一つに記載の計算装置。
【請求項８】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法であって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算工程と、
前記反復計算工程によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定工程と、
前記有意性判定工程によって前記計算結果が有意であると判定された場合に、前記反復計算工程による計算処理を中止する中止工程と、
を含んだことを特徴とする計算方法。
【請求項９】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法をコンピュータに実行させる計算プログラムであって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手順と、
前記反復計算手順によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手順と、
前記有意性判定手順によって前記計算結果が有意であると判定された場合に、前記反復計算手順による計算処理を中止する中止手順と、
をコンピュータに実行させることを特徴とする計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、計算装置、計算方法および計算プログラムに関する。
【背景技術】
【０００２】
従来より、自動車の衝突シミュレーションやタンパク質構造解析などのコンピュータシミュレーションでは、計算プロセッサごとに一連の計算式を繰り返し実行する反復解法によって計算をしている。例えば、連立一次方程式を用いた反復解法は、既知の「行列Ａ」および「ベクトルｂ」に対して、式「Ａｘ＝ｂ」を満たすような解ベクトル「ｘ」を求める計算を行っている。そして、「行列Ａ」が要素に「０」を多く含む疎行列である場合、例えば、共役勾配法などの収束演算型の反復解法によって解ベクトルを求めることが一般的である。【０００３】
また、収束演算型の反復解法は、近似解ベクトル「ｘｉ」（なお、これは、ｉに対応するｘを表す）を算出する近似解算出計算や近似解ベクトルの精度を示す「ノルム（｜ｂ−Ａｘｉ｜）」を算出する近似解精度計算を含んだ一連の計算処理を繰り返し行うことで、十分な精度まで収束した解ベクトル「ｘ」を計算する（非特許文献１および非特許文献２参照）。そして、近似解精度計算は、残差ベクトルにおける「ノルム」の総和計算が必要であり、「総和計算によって算出された「ノルム」が所定の収束判定閾値「ε」以上である場合には、一連の計算処理を繰り返し行い、「ノルム」が所定の収束判定閾値「ε」未満である場合には、算出された近似解ベクトル「ｘｉ」を解ベクトル「ｘ」とする収束判定」を行うことが一般的である。【０００４】
また、例えば、特許文献１（特開２００２−２８８１４７号公報）に開示された発明のように、複数のプロセッサを搭載したメモリ分散型並列計算装置がある。このメモリ分散型並列計算装置を用いて反復解法を行う場合には、プロセッサごとに一連の計算処理を行い、近似解ベクトルおよび部分ノルムを算出する。そして、プロセッサ間における通信であるリダクション通信によって部分ノルムを通信することでプロセッサごとにノルムを算出し、所定の収束判定閾値「ε」と付き合わせることで収束判定する。【０００５】
また、例えば、メモリ分散型並列計算装置によって前処理付き共役勾配法を行う場合には、図１９の（１）に示したアルゴリズムによって、近似解ベクトル「ｘｉ」および近似解ベクトルに対応した残差ベクトル「ｒｉ」を算出する。そして、図１９の（２）に示したアルゴリズムによって、部分ノルムを算出し、部分ノルムを総和計算することでノルム「｜ｒｉ｜」を算出し、ノルムを所定の収束判定閾値「ε」と付き合わせることで収束判定する。図１９は、従来技術に係るアルゴリズムである。ここで、図１９におけるαｉ、βｉ、γｉおよびρｉはスカラ変数を表し、ｐｉ、ｑｉ、ｒｉ、ｘｉおよびｚｉはベクトル変数を表し、ＡおよびＭ−１（なお、これは、Ｍインバースを表す）は、定数行列を表し、εはスカラ定数を表す。【０００６】
【特許文献１】特開２００２−２８８１４７号公報
【非特許文献１】Ｒ．バーレット、外９名著、長谷川里美、外２名訳、「反復法  Ｔｅｍｐｌａｔｅｓ」、朝倉書店、（１９９６年）
【非特許文献２】Ｒｉｃｈａｒｄ  Ｂａｒｒｅｔｔ、外９名著、「Ｔｅｍｐｌａｔｅｓ  ｆｏｒ  ｔｈｅ  Ｓｏｌｕｔｉｏｎ  ｏｆ  Ｌｉｎｅａｒ  Ｓｙｓｔｅｍｓ：  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋｓ  ｆｏｒ  Ｉｔｅｒａｔｉｖｅ  Ｍｅｔｈｏｄｓ」、［ｏｎｌｉｎｅ］、［平成１８年４月１８日検索］インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｎｅｔｌｉｂ．ｏｒｇ／ｔｅｍｐｌａｔｅｓ／ｔｅｍｐｌａｔｅｓ．ｐｄｆ＞
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上記した従来の技術は、反復解法を用いた計算処理の中で、通信オーバーヘッドとして多くの時間を必要とするという課題があった。【０００８】
具体的には、メモリ分散型並列計算装置は、例えば、浮動小数点計算における単位処理などの計算処理にかかる処理時間が１ナノ秒以下を必要とするのに対して、リダクション通信のレイテンシ（通信時間、実行時間）として数マイクロ秒程度を必要とし、収束判定を行った後に次の繰り返しを行っていた。この結果、収束判定に必要な総和計算におけるリダクション通信が発生する負荷の大きさである通信オーバーヘッドとして、１回の繰り返しに必要とする時間に対して、多くの時間を必要としていた。【０００９】
また、メモリ分散型並列計算装置は、プロセッサを多数にわたって搭載した場合には、各プロセッサが行う計算量が減少するので、計算にかかる処理時間として少ない時間を必要とするのに対して、通信するプロセッサの数が多くなるので、リダクション通信のレイテンシとして多くの時間を必要とする。この結果、各プロセッサにおいて計算にかかる処理時間に対して、通信オーバーヘッドとして多くの時間を必要としていた。【００１０】
また、メモリ分散型並列計算装置は、大規模連立一次方程式に対する反復解法を行う場合には、ノルムが収束判定閾値以上であると判定する確率が極めて高く、少なくとも数十回に渡って一連の計算処理を繰り返し行っていた。この結果、反復解法を用いて解ベクトルを求める計算にかかる処理時間に対して、通信オーバーヘッドとして多くの時間を必要としていた。【００１１】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能な計算装置、計算方法および計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算装置であって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手段と、前記反復計算手段によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手段と、前記有意性判定手段によって前記計算結果が有意であると判定された場合に、前記反復計算手段による計算処理を中止する中止手段とを備えたことを特徴とする。【００１３】
また、請求項２に係る発明は、上記の発明において、前記反復計算手段は、前記計算処理として、連立一次方程式における解ベクトルを反復して算出することを特徴とする。【００１４】
また、請求項３に係る発明は、上記の発明において、前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至った旨を前記通信部から通知された場合に、前記有意性を判定することを特徴とする。【００１５】
また、請求項４に係る発明は、上記の発明において、前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせ、当該有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、前記有意性を判定することを特徴とする。【００１６】
また、請求項５に係る発明は、上記の発明において、前記有意性判定手段は、前記計算処理における所定の進捗間隔ごとに、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせることを特徴とする。【００１７】
また、請求項６に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法であって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算工程と、前記反復計算工程によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定工程と、前記有意性判定工程によって前記計算結果が有意であると判定された場合に、前記反復計算工程による計算処理を中止する中止工程とを含んだことを特徴とする。【００１８】
また、請求項７に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法をコンピュータに実行させる計算プログラムであって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手順と、前記反復計算手順によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手順と、前記有意性判定手順によって前記計算結果が有意であると判定された場合に、前記反復計算手順による計算処理を中止する中止手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００１９】
請求項１、６、７の発明によれば、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行し、計算処理が開始された後、通信部によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、計算処理を中止するので、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。【００２０】
また、請求項２の発明によれば、計算処理として、連立一次方程式における解ベクトルを反復して算出するので、総和計算における通信オーバーヘッドを隠蔽し、短時間で連立一次方程式における解ベクトルを算出することが可能である。【００２１】
また、請求項３の発明によれば、計算処理が開始された後、有意性を判定することが可能な状況に至った旨を通信部から通知された場合に、有意性を判定するので、有意性を判定することが可能な状況を示す割り込み信号によって通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。【００２２】
また、請求項４の発明によれば、計算処理が開始された後、有意性を判定することが可能な状況に至ったか否かを通信部に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定するので、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。【００２３】
また、請求項５の発明によれば、計算処理における所定の進捗間隔ごとに、有意性を判定することが可能な状況に至ったか否かを通信部に対して問い合わせるので、計算パターンごとに残差ノルムが算出されたかを問い合わせつつ近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【図面の簡単な説明】
【００２４】
【図１】図１は、実施例１に係る計算機システムの概要および特徴を説明するための図である。
【図２】図２は、実施例１に係る計算機システムの時間的特徴を説明するための図である。
【図３】図３は、実施例１に係るプロセッサの構成を示すブロック図である。
【図４】図４は、プロセッサ１における他プロセッサ部分ノルム記憶部に記憶される情報の一例を示した図である。
【図５】図５は、実施例１に係る反復計算部における一連の計算処理の流れを示すフローチャートである。
【図６】図６は、実施例１に係る中止信号を受け付けた場合の反復計算部の処理の流れを示すフローチャートである。
【図７】図７は、実施例１に係る解判定部の処理の流れを示すフローチャートである。
【図８】図８は、実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部の処理の流れを示すフローチャートである。
【図９】図９は、実施例１に係る総和計算部の処理の流れを示すフローチャートである。
【図１０】図１０は、実施例１に係る計算機システムにおけるアルゴリズムを示す図である。
【図１１】図１１は、実施例１に係る計算システムによる効果を説明するための図である。
【図１２】図１２は、実施例２に係る概要および特徴を説明するための図である。
【図１３】図１３は、実施例２に係る反復計算部の処理の流れを示すフローチャートである。
【図１４】図１４は、実施例２に係る解判定部の処理の流れを示すフローチャートである。
【図１５】図１５は、実施例２に係る総和計算部の処理の流れを示すフローチャートである。
【図１６】図１６は、実施例２に係る計算機システムにおけるアルゴリズムを示す図である。
【図１７】図１７は、実施例３に係る計算機システムにおけるアルゴリズムを示す図である。
【図１８】図１８は、計算プログラムを実行するコンピュータを示す図である。
【図１９】図１９は、従来技術に係るアルゴリズムを示す図である。
【符号の説明】
【００２５】
１０  プロセッサ
２０  主演算部
２１  処理部
２２  記憶部
２３  近似解ベクトルレジスタ
２４  部分ノルムレジスタ
２５  反復計算部
２６  解判定部
３０  リダクション通信部
３１  処理部
３２  記憶部
３３  総和計算結果レジスタ
３４  他プロセッサ部分ノルム記憶部
３５  総和計算部
３６  他プロセッサ側出入力処理部
３７  計算終了フラグレジスタ
【発明を実施するための最良の形態】
【００２６】
以下に添付図面を参照して、この発明に係る計算装置、計算方法および計算プログラムの実施例を詳細に説明する。なお、以下では、この発明を適用した「主演算部と、リダクション通信部とからなるプロセッサ」が、同じ構成からなる他のプロセッサや、入力部や、出力部とデータ通信用ネットワークを介して接続された計算機システムにおいて、前処理付き共役勾配法を用いて、解ベクトルを計算する例を実施例として説明する。
【実施例１】
【００２７】
以下の実施例１では、実施例１に係る計算機システムの概要および特徴、プロセッサの構成、計算機システムの処理の流れを順に説明し、最後に実施例１の効果を説明する。【００２８】
［実施例１に係る計算機システムの概要および特徴］
まず最初に、図１および図２を用いて実施例１に係る計算機システムの概要および特徴を説明する。図１は、実施例１に係る計算機システムの概要および特徴を説明するための図であり、図２は、実施例１に係る計算機システムの時間的特徴を説明するための図である。【００２９】
図１に示すように、実施例１に係る計算機システムは、主演算部（主演算部１〜ｎ）と、リダクション通信部（リダクション通信部１〜ｎ）とからなるプロセッサ（プロセッサ１〜ｎ）を複数に渡って備え、データ通信用ネットワークを介して接続された各プロセッサや入力部や出力部とから構成され、プロセッサごとに一連の計算を繰り返し実行し、解を計算する。【００３０】
具体的には、計算機システムは、プロセッサごとに一連の計算処理を実行し、「行列Ａ」および「ベクトルｂ」を用いて近似解ベクトル「ｘｉ」（なお、これは、ｉに対応するｘを表す）と、部分ノルムとを繰り返し算出する。そして、計算機システムは、部分ノルムをプロセッサ間で通信し、部分ノルムを総和計算して近似解ベクトルの精度を示すノルムを算出する。さらに、計算機システムは、「「ノルム」が所定の収束判定閾値「ε」以上である場合には、一連の計算処理を繰り返し行い、「ノルム」が所定の収束判定閾値「ε」未満である場合には、算出された近似解ベクトル「ｘｉ」を解ベクトル「ｘ」とする収束判定」を行うことで十分な精度まで収束した解ベクトル「ｘ」を算出する。このような概要の下、実施例１に係る計算機システムは、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことを主たる特徴とする。【００３１】
この主たる特徴について説明すると、実施例１に係る計算機システムは、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行する。具体的には、図１の（１−１）に示すように、各プロセッサにおける主演算部は、一連の計算処理を実行し、近似解および部分ノルムを算出する。そして、図１の（１−２）に示すように、主演算部は、リダクション通信部に対して、部分ノルムの総和計算を要求し、図１の（１−３）に示すように、一連の計算処理を反復して実行し、新たなる近似解ベクトルおよび部分ノルムの計算を開始する。【００３２】
一方では、各プロセッサにおけるリダクション通信部は、図１の（２）に示すように、常時、他のプロセッサから部分ノルムを受信する。そして、リダクション通信部は、図１の（３−１）に示すように、各主演算部から総和計算の要求を受け付けた場合に、自プロセッサにおける主演算部が算出した部分ノルムを他のプロセッサに対して送信する。さらに、リダクション通信部は、図１の（３−２）に示すように、全ての他のプロセッサから部分ノルムを受け付けた後に、部分ノルムを総和計算することでノルムを算出し、図１の（３−３）に示すように、自プロセッサにおける主演算部に対して割り込み信号を送信することで総和計算の終了を通知する。【００３３】
そして、実施例１に係る計算機システムは、リダクション通信部によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、計算処理を中止する。具体的には、割り込み信号を受け付けた主演算部は、図１の（４）に示すように、自プロセッサにおけるリダクション通信部が算出したノルムと、収束判定閾値とを付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合は、反復して実行した一連の計算処理を中止する。【００３４】
このようなことから、実施例１に係る計算機システムは、上記した主たる特徴のごとく、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。すなわち、図２の（Ａ）に示すように、近似解ベクトルおよび部分ノルムを算出する計算時間（図２の（Ａ）の（１）参照）および全ての他のプロセッサから部分ノルムを受け付け、部分ノルムを総和計算するリダクション通信に必要な時間（図２の（Ａ）の（２）参照）を足し合わせた時間が１回の反復（ｉ＝０、１、２）に必要な計算時間（図２の（Ａ）の（３）参照）であったところ、実施例１に係る計算機システムは、リダクション通信に必要な時間の間に一連の計算処理を開始することで、反復するごとにオーバーヘッドを隠蔽し（図２の（Ｂ）の（４）および(５)参照）、全体として短時間で反復解法を用いた計算処理を行う（図２の（Ｂ）の（６）参照）。【００３５】
［実施例１に係るプロセッサの構成］
次に、図３を用いて、実施例１に係るプロセッサの構成を説明する。図３は、実施例１に係るプロセッサの構成を示すブロック図である。同図に示すように、プロセッサ１０は、主演算部２０と、リダクション通信部３０とから構成される。【００３６】
このうち、主演算部２０は、各種計算処理を規定したアルゴリズムを格納するためのメモリを有し、これらによって種々の計算処理を実行する。そして、本発明に密接に関係するものとしては、図３に示すように、処理部２１と、記憶部２２とを備える。【００３７】
主演算部２０における記憶部２２は、データの処理を行うために必要な情報を一時的または長期的に記憶する。そして、本発明に密接に関係するものとしては、図３に示すように、近似解ベクトルレジスタ２３と、部分ノルムレジスタ２４とを備える。【００３８】
近似解ベクトルレジスタ２３は、一連の計算処理によって算出された計算結果を記憶する。具体的に一例をあげて説明すると、近似解ベクトルレジスタ２３は、一連の計算処理によって算出された近似解ベクトル「ｘｉ」を記憶し、後述の反復計算部２５によって一連の計算処理が繰り返されるごとに書き換えられる。【００３９】
部分ノルムレジスタ２４は、一連の計算処理によって算出された部分ノルムを記憶する。具体的に一例をあげて説明すると、部分ノルムレジスタ２４は、一連の計算処理によって算出された部分ノルムを記憶し、後述の反復計算部２５によって一連の計算処理が繰り返されるごとに書き換えられる。【００４０】
主演算部２０における処理部２１は、各種処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、特に本発明に密接に関係するものとしては、反復計算部２５と、解判定部２６とを備える。なお、反復計算部２５は、請求の範囲に記載の「反復計算手段」に対応し、解判定部２６は、請求の範囲に記載の「有意性判定手段」および「中止手段」に対応する。【００４１】
反復計算部２５は、計算処理によって自己の計算結果が算出された後も、この計算結果の有意性に対する判定を待たずに、計算処理を反復して実行する。具体的に一例をあげて説明すると、反復計算部２５は、「行列Ａ」のデータ（例えば、自動車の衝突シミュレーションを実行する場合には、形状から算出されるデータなど）が入力されると、一連の計算処理によって近似解ベクトルを算出し、近似解ベクトルレジスタ２３を書き換える。そして、部分ノルムを算出し、部分ノルムレジスタ２４を書き換える。さらに、反復計算部２５は、部分ノルムの総和計算をリダクション通信部３０に対して要求する。そして、反復計算部２５は、一連の計算処理を反復して新たなる近似解ベクトルの算出を開始する。一方で、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けた場合に、反復して実行した計算処理を中止し、近似解ベクトルレジスタ２３から近似解ベクトルを読み込み、解ベクトルとして出力する。【００４２】
解判定部２６は、反復計算部２５によって計算処理が開始された後、リダクション通信部３０によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定する。具体的に一例をあげて説明すると、解判定部２６は、後述の総和計算部３５から割り込み信号を受け付けると、後述の総和計算結果レジスタ３３からノルムを読み込み、ノルムと収束判定閾値とを付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合に、反復計算部２５に対して、計算処理の中止信号を送信する。【００４３】
リダクション通信部３０は、各種処理を規定したアルゴリズムを格納するためのメモリを有し、これらによって種々の処理を実行する。そして、本発明に密接に関係するものとしては、図３に示すように、処理部３１と、記憶部３２とを備える。【００４４】
リダクション通信部３０における記憶部３２は、データの処理を行うために必要な情報を一時的または長期的に記憶する。そして、本発明に密接に関係するものとしては、図３に示すように、総和計算結果レジスタ３３と、他プロセッサ部分ノルム記憶部３４とを備える。【００４５】
総和計算結果レジスタ３３は、総和計算によって算出された計算結果を記憶する。具体的に一例をあげて説明すると、総和計算結果レジスタ３３は、総和計算によって算出されたノルムを記憶し、後述の総和計算部３５によって書き換えられる。【００４６】
他プロセッサ部分ノルム記憶部３４は、他のプロセッサによって算出された計算結果を記憶する。具体的に一例をあげて説明すると、他プロセッサ部分ノルム記憶部３４は、各プロセッサに予め付与されたプロセッサ番号と、各プロセッサにおけるネットワークアドレスと、各プロセッサが算出した部分ノルムを対応付けて記憶する。例えば、他プロセッサ部分ノルム記憶部３４は、図４に示すように、「ネットワークアドレスが１であるプロセッサ２」によって算出された部分ノルム「０．２１Ｅ−１４」（なお、これは、０．２１に１０のマイナス１４乗をかけた値を表す）を記憶する。なお、図４は、プロセッサ１における他プロセッサ部分ノルム記憶部に記憶される情報の一例を示した図であり、後述の他プロセッサ側出入力処理部３６によって部分ノルムが書き換えられる。【００４７】
リダクション通信部３０における処理部３１は、各種処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、特に本発明に密接に関係するものとしては、総和計算部３５と、他プロセッサ側出入力処理部３６とを備える。【００４８】
総和計算部３５は、自己が算出した計算結果の有意性を判定する際に用いる判定値を計算する。具体的に一例をあげて説明すると、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付け、部分ノルムレジスタ２４から部分ノルムを読み込み、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信する。そして、総和計算部３５は、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納された場合に、部分ノルムレジスタ２４および他プロセッサ部分ノルム記憶部３４から部分ノルムを読み込み、部分ノルムの総和を計算することで、ノルムを算出する。さらに、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し、解判定部２６に対して割り込み信号を送信する。【００４９】
他プロセッサ側出入力処理部３６は、他のプロセッサとの間で出入力処理する。具体的に一例をあげて説明すると、他プロセッサ側出入力処理部３６は、総和計算部３５から部分ノルムを受け付けた場合には、他の全てのプロセッサに対して部分ノルムを送信する。また、他のプロセッサから部分ノルムを受け付けた場合には、他プロセッサ部分ノルム記憶部３４に送信元のプロセッサ番号およびネットワークアドレスと対応付けて格納する。例えば、ネットワークアドレスが１であるプロセッサ２から部分ノルムを受け付けた場合には、ネットワークアドレスが１でありプロセッサ番号が２であるエントリに部分ノルムを格納する。【００５０】
［実施例１に係る計算機システムによる処理］
次に、図５〜図１０を用いて、実施例１に係る計算機システムによる処理の流れを説明する。具体的には、反復計算部２５における一連の計算処理と、中止信号を受け付けた場合の反復計算部２５の処理と、解判定部２６の処理と、他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部３６の処理と、総和計算部３５の処理とを順に説明する。【００５１】
まず最初に、図５を用いて、実施例１に係る反復計算部２５における一連の計算処理の流れを説明する。図５は、実施例１に係る反復計算部２５における一連の計算処理の流れを示すフローチャートである。【００５２】
図５に示すように、反復計算部２５は、「行列Ａ」のデータが入力されると（ステップＳ１０１）、一連の計算処理によって近似解ベクトルを算出し（ステップＳ１０２）、近似解ベクトルを近似解ベクトルレジスタ２３に格納する（ステップＳ１０３）。【００５３】
続いて、反復計算部２５は、部分ノルムを算出し（ステップＳ１０４）、部分ノルムを部分ノルムレジスタ２４に格納し（ステップＳ１０５）、部分ノルムの総和計算をリダクション通信部３０に対して要求し（ステップＳ１０６）、再び近似解ベクトルの算出を開始する（ステップＳ１０２）。このようにして、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けるまで計算処理を反復して実行する（ステップＳ１０２〜ステップＳ１０６）。【００５４】
次に、図６を用いて、実施例１に係る中止信号を受け付けた場合の反復計算部２５の処理の流れを説明する。図６は、実施例１に係る中止信号を受け付けた場合の反復計算部の処理の流れを示すフローチャートである。【００５５】
図６に示すように、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けると（ステップＳ２０１肯定）、近似解ベクトルを読み込み、解ベクトルとして出力し（ステップＳ２０２）、計算機システム全体の処理を終了する。【００５６】
次に、図７を用いて、実施例１に係る解判定部２６の処理の流れを説明する。図７は、実施例１に係る解判定部の処理の流れを示すフローチャートである。【００５７】
図７に示すように、解判定部２６は、総和計算部３５から割り込み信号を受け付けると（ステップＳ３０１肯定）、総和計算結果レジスタ３３からノルムを読み込み（ステップＳ３０２）、ノルムと収束判定閾値と付き合わせ、ノルムが収束判定閾値と等しいか大きいと判定した場合には（ステップＳ３０３肯定）、上記した処理（ステップＳ３０１〜ステップＳ３０３）を終了して、再び割り込み信号を待機する（ステップＳ３０１）。【００５８】
一方で、ノルムが収束判定閾値未満であると判定した場合（ステップＳ３０３否定）、解判定部２６は、反復計算部２５に対して、計算処理の中止信号を送信し（ステップＳ３０４）、上記した処理（ステップＳ３０１〜ステップＳ３０４）を終了する。【００５９】
次に、図８を用いて、実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部３６の処理の流れを説明する。図８は、実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部の処理の流れを示すフローチャートである。【００６０】
図８に示すように、他プロセッサ側出入力処理部３６は、他のプロセッサから部分ノルムを受け付けると（ステップＳ４０１肯定）、部分ノルムを他プロセッサ部分ノルム記憶部３４に送信元のプロセッサ番号およびネットワークアドレスと対応付けて格納し（ステップＳ４０２）、上記した処理を終了して、再び他のプロセッサからの部分ノルムを待機する（ステップＳ４０１）。【００６１】
次に、図９を用いて、実施例１に係る総和計算部３５の処理の流れを説明する。図９は、実施例１に係る総和計算部の処理の流れを示すフローチャートである。【００６２】
図９に示すように、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付けると（ステップ５０１肯定）、部分ノルムレジスタ２４から部分ノルムを読み込み（ステップＳ５０２）、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信し（ステップＳ５０３）、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されるまで待機する（ステップＳ５０４否定）。【００６３】
ここで、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されたことを確認すると（ステップＳ５０４肯定）、総和計算部３５は、部分ノルムレジスタ２４から自プロセッサによって算出された部分ノルムを読み込み（ステップＳ５０５）、他プロセッサ部分ノルム記憶部３４から他のプロセッサによって算出された部分ノルムを読み込み（ステップＳ５０６）、部分ノルムの総和を計算することで、ノルムを算出する（ステップＳ５０７）。【００６４】
続いて、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し（ステップＳ５０８）、解判定部２６に対して割り込み信号を送信し（ステップＳ５０９）、上記した処理を終了して、再び部分ノルムの総和計算要求を待機する（ステップＳ５０１）。【００６５】
次に、図１０を用いて、実施例１に係る計算機システムの処理の流れを説明する。図１０は、実施例１に係る計算機システムにおけるアルゴリズムである。ここで、図１０におけるαｉ、βｉ、γｉおよびρｉはスカラ変数を表し、ｐｉ、ｑｉ、ｒｉ、ｘｉおよびｚｉはベクトル変数を表し、ＡおよびＭ−１（なお、これは、Ｍインバースを表す）は定数行列を表し、εはスカラ定数を表す。【００６６】
実施例１に係る計算機システムは、図１０の（１）に示したアルゴリズムによって、割り込みを待機しつつ、図１０の（２）に示したアルゴリズムによって一連の計算処理を実行する。そして、実施例１に係る計算機システムは、図１０の（３）に示したアルゴリズムによって部分ノルムを算出し、図１０の（４）に示したアルゴリズムによってノルムを算出し、算出した近似解ベクトルが有意か否かを判定し、近似解ベクトルが有意である場合には一連の計算処理を中止する。【００６７】
［実施例１の効果］
上記したように、実施例１によれば、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行し、計算処理が開始された後、リダクション通信部３０によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、反復計算部２０による計算処理を中止するので、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。【００６８】
すなわち、１回の繰り返しに必要な処理時間の中で、大きな比重を占めていた収束判定に必要な総和計算におけるリダクション通信を隠蔽する結果、短時間で反復解法を用いた計算処理を行うことができる。また、総和計算におけるリダクション通信を隠蔽して、計算にかかる処理時間に対してリダクション通信にかかる処理時間の割合を少なくする結果、プロセッサを多数にわたって搭載した場合に、効率よく短時間で反復解法を用いた計算処理を行うことができる。さらに、総和計算におけるリダクション通信を繰り返し隠蔽する結果、反復解法を用いて解ベクトルを求める計算にかかる処理時間として、より短時間で反復解法を用いた計算処理を行うことができる。【００６９】
また、実施例１によれば、計算処理として、連立一次方程式における解ベクトルを反復して算出するので、総和計算における通信オーバーヘッドを隠蔽し、短時間で連立一次方程式における解ベクトルを算出することが可能である。【００７０】
また、実施例１によれば、計算処理が開始された後、有意性を判定することが可能な状況に至った旨をリダクション通信部３０から通知された場合に、有意性を判定するので、有意性を判定することが可能な状況を示す割り込み信号によって通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。【００７１】
ここで、図１１を用いて、実施例１に関る計算システムによる効果を説明する。図１１は、実施例１に係る計算システムによる効果を説明するための図である。図１１の（Ａ）は、一連の計算処理における実行文ごとに、必要な演算コストおよび通信パターンを対応付けて示した図であり、例えば、ノルムを総和計算させる命令文である「if  (|ri|  <  ε)  then  break」を実行する際に必要な演算コストは「Ｏ（２Ｎ＋１）」であり、通信パターンは「リダクション通信を１回」必要とすることを示す。また、図１１の（Ａ）における合計は、従来技術に係るアルゴリズムを１回実行、言い換えると、一連の計算処理を１回実行する際に必要な演算コストおよび通信パターンを示す。ここで、例えば、図１１の（Ａ）における演算コスト「Ｏ（１）」は、掛け算などを１回行う際に必要な演算コストを表し、「近接通信」は、近接するプロセッサとの通信処理を表し、「リダクション通信」は、他の全てのプロセッサとの通信処理を表す。【００７２】
また、図１１の（Ｂ）は、各変数に対して見積もりパラメータおよび内容の説明を示した図であり、例えば、変数「ｐ」は、使用するプロセッサの数として、「５１２０個」のプロセッサを搭載した計算機システム（図１におけるｎに対応する）であることを示す。ここで、図１１の（Ｂ）における「Ｎ」、「ｋ」または「ｐ」は、行列または計算システムの一例として表した数値であり、ＣＮおよびＣＲは、既存のメモリ分散型並列計算装置における実測値の一例として表した数値である。また、変数Ｎの見積もりパラメータ「１０７」は、「１０の７乗」を表す。【００７３】
また、図１１の（Ｃ）は、見積もり式として、プロセッサ数が「ｐ」である計算機システムにおいて、本発明を適用する前または適用後における一連の計算処理を１回実行する際に必要な処理コストを見積もる式を示し、例えば、適用前の見積もり式は、図１１の（Ａ）における合計として示した演算コスト（一部を除く）をプロセッサ数で割り、各通信パターンの相対コストを加えた式となる。そして、この見積もり式に、図１１の（Ｂ）に示した各変数における見積もりパラメータを代入した場合における、見積もり結果および実行時間比を示す。【００７４】
さて、実施例１に関る計算システムは、図１１の（Ａ）において「＊１」で示した、リダクション通信、すなわち、総和計算に必要なリダクション通信を隠蔽するという効果を奏する。ここで、本発明を適用する前または適用した後における一連の計算処理を１回実行するごとにかかる処理コストは、図１１の（Ｃ）における見積もり式によって算出され、図１１の（Ｂ）に示した見積もりパラメータを各変数に代入することで算出される本発明を適用する前または適用した後における見積もり結果から、実行時間比が本発明を適用後には「７７．９０％」となる。すなわち、実施例１に係る計算システムは、本発明適用前に比べ、「７７．９０％」の時間で解ベクトルを算出することが可能である。
【実施例２】
【００７５】
ところで、上記の実施例１では、リダクション通信部が主演算部に対して割り込み番号を割り込みで送信することで総和計算の終了を通知する場合を説明したが、本発明はこれに限定されるものではなく、例えば、主演算部がリダクション通信部に対して、総和計算の終了を問い合わせるようにしてもよい。そこで、以下では、図１２〜図１６を用いて、主演算部がリダクション通信部に対して、総和計算の終了を問い合わせる場合を実施例２として説明する。【００７６】
［実施例２に係る計算機システムの概要および特徴］
図１２は、実施例２に係る概要および特徴を説明するための図であり、同図に示すように、実施例２に係る計算機システムは、実施例１に係る計算機システムと同じ構成および概要の下、一時的に一連の計算処理を停止することなく近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことを特徴とする。具体的には、各プロセッサにおける主演算部は、図１２の（１−１）に示すように、反復して計算しつつ、計算パターンごとに総和計算の終了をリダクション通信装置に対して問い合わせる。そして、図１２の（１−２）に示すように、主演算部は、リダクション通信部に対して、部分ノルムの総和計算を要求する。【００７７】
一方では、各プロセッサにおけるリダクション通信部は、実施例１に係る計算機システムと同様に、図１２の（２）に示すように、常時、他のプロセッサから部分ノルムを受信する。そして、リダクション通信部は、図１２の（３−１）に示すように、各主演算部から総和計算の要求を受け付けた場合に、自プロセッサにおける主演算部が算出した部分ノルムを他のプロセッサに対して送信する。さらに、リダクション通信部は、図１２の（３−２）に示すように。全ての他のプロセッサから部分ノルムを受け付けた後に、部分ノルムを総和計算することでノルムを算出する。【００７８】
そして、実施例２に係る計算機システムは、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定する。具体的には、図１２の（１−１）において、総和計算の終了をリダクション通信装置に対して問い合わせた結果、総和計算が終了していた場合に、図１２の（４）に示すように、近似解ベクトルを判定する。【００７９】
このようなことから、実施例２に係る計算機システムは、上記した特徴のごとく、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。【００８０】
［実施例２に係る計算機システムの構成］
実施例２に係る計算機システムは、リダクション通信部３０における記憶部３２において、計算終了フラグレジスタ３７を新たに備える他は、図３に示した計算機システム１０と同様の構造を有す。また、以下に説明する反復計算部２５、解判定部２６、総和計算部３５および計算終了フラグレジスタ３７を除き同様に動作する。ここでは、計算終了フラグレジスタ３７、解判定部２６のみを説明し、反復計算部２５および総和計算部３５は、後に詳細に説明する。【００８１】
計算終了フラグレジスタ３７は、各処理の実行状態を示す値を記憶する。具体的に一例をあげて説明すると、計算終了フラグレジスタ３７は、ノルムの算出を終了した旨を示し、解判定部２６による有意性の判定の契機となる「１」と、ノルムの算出が終了していない旨を示し、解判定部２６による有意性の判定を待機させる「０」とを記憶し、総和計算部３５および解判定部２６によって書き換えられる。【００８２】
解判定部２６は、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定する。具体的に一例をあげて説明すると、解判定部２６は、反復計算部２５から計算終了フラグレジスタ３７の参照要求を受け付け、計算終了フラグレジスタ３７に有意性の判定の契機となる「１」が記憶されている場合、総和計算結果レジスタ３３からノルムを読み込む。そして、ノルムと収束判定閾値と付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合に、反復計算部２５に対して、計算処理の中止信号を送信する。一方で、ノルムが収束判定閾値以上であった場合に、解判定部２６は、計算終了フラグレジスタ３７を有意性の判定を待機させる「０」に書き換え、近似解ベクトルの判定が終了した旨を反復計算部２５に対して送信する。【００８３】
［実施例２に係る計算機システムによる処理］
次に、図１３を用いて、実施例２に係る反復計算部の処理を説明する。図１３は、実施例２に係る反復計算部の処理の流れを示すフローチャートである。【００８４】
図１３に示すように、反復計算部２５は、「行列Ａ」のデータが入力されると（ステップＳ６０１）、命令文を１つ実行し（ステップＳ６０２）、解判定部２６に対して計算終了フラグレジスタ３７の参照を要求する（ステップＳ６０３）。ここで、解判定部２６から近似解ベクトルの判定が終了した旨を受信していない場合（ステップＳ６０４否定）、反復計算部２５は、残差ベクトルを算出していない場合には（ステップＳ６０５否定）、残差ベクトルを算出するまで、命令文を実行しつつ計算終了フラグレジスタの参照を要求する（ステップＳ６０２〜ステップＳ６０５）。また、残差ベクトルを算出している場合には（ステップＳ６０５肯定）、計算終了フラグレジスタの参照を要求するのみで部分ノルムの算出を待機する（ステップＳ６０３〜ステップＳ６０５）。【００８５】
一方で、１回目の計算処理であるまたは解判定部２６から近似解ベクトルの判定が終了した旨を受信した場合には（ステップＳ６０４肯定）、反復計算部２５は、残差ベクトルを算出するまで命令文を全て実行したか否かを判定し（ステップＳ６０６）、残差ベクトルを算出するまで命令文を全て実行している場合には、そのまま部分ノルムを算出する（ステップＳ６０８）。一方で、残差ベクトルを算出するまで命令文を全て実行していない場合には（ステップＳ６０６否定）、残差ベクトルを算出するまで命令文を実行し（ステップＳ６０７）、部分ノルムを算出する（ステップＳ６０８）。【００８６】
続いて、反復計算部２５は、部分ノルムを部分ノルムレジスタ２４に格納し（ステップＳ６０９）、部分ノルムの総和計算をリダクション通信部３０に対して要求し（ステップＳ６１０）、再び命令文を１つ実行することで計算処理を反復して実行する（ステップＳ６０２〜ステップＳ６１０）。【００８７】
次に、図１４を用いて、実施例２に係る解判定部２６の処理の流れを説明する。図１４は、実施例２に係る解判定部の処理の流れを示すフローチャートである。【００８８】
図１４に示すように、解判定部２６は、反復計算部２５から計算終了フラグレジスタ３７の参照要求を受け付けると（ステップＳ７０１肯定）、計算終了フラグレジスタ３７を参照し（ステップＳ７０２）、計算終了フラグレジスタ３７に「１」が記憶されていない場合には（ステップＳ７０２否定）、再び計算終了フラグレジスタ３７の参照要求を待機する（ステップＳ７０１）。【００８９】
一方で、計算終了フラグレジスタ３７に「１」が記憶されている場合には（ステップＳ７０２肯定）、総和計算結果レジスタ３３からノルムを読み込み（ステップＳ７０３）、ノルムと収束判定閾値と付き合わせることで、算出した近似解ベクトルが有意か否かを判定する（ステップＳ７０４）。【００９０】
ここで、ノルムが収束判定閾値未満であると判定した場合（ステップＳ７０４否定）、解判定部２６は、反復計算部２５に対して、計算処理の中止信号を送信し（ステップＳ７０５）、上記した処理（ステップＳ７０１〜ステップＳ７０５）を終了する。【００９１】
一方で、ノルムが収束判定閾値以上であると判定した場合（ステップＳ７０４肯定）、解判定部２６は、計算終了フラグレジスタ３７を「０」に書き換え、近似解ベクトルの判定が終了した旨を反復計算部２５に対して送信し（ステップＳ７０６）、上記した処理を終了して、再び計算終了フラグレジスタ３７の参照要求を待機する（ステップＳ７０１）。【００９２】
次に、図１５を用いて、実施例２に係る総和計算部３５の処理の流れを説明する。図１５は、実施例２に係る総和計算部の処理の流れを示すフローチャートである。【００９３】
図１５に示すように、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付けると（ステップ８０１肯定）、部分ノルムレジスタ２４から部分ノルムを読み込み（ステップＳ８０２）、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信し（ステップＳ８０３）、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されるまで待機する（ステップＳ８０４否定）。【００９４】
ここで、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されたことを確認すると（ステップＳ８０４肯定）、総和計算部３５は、部分ノルムレジスタ２４から自プロセッサによって算出された部分ノルムを読み込み（ステップＳ８０５）、他プロセッサ部分ノルム記憶部３４から他のプロセッサによって算出された部分ノルムを読み込み（ステップＳ８０６）、部分ノルムの総和を計算することで、ノルムを算出する（ステップＳ８０７）。【００９５】
続いて、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し（ステップＳ８０８）、計算終了フラグレジスタ３７を「１」に書き換え（ステップＳ８０９）、上記した処理を終了して、再び部分ノルムの総和計算要求を待機する（ステップＳ８０１）。【００９６】
次に、図１６を用いて、実施例２に係る計算機システムの処理の流れを説明する。図１６は、実施例２に係る計算機システムにおけるアルゴリズムである。ここで示した変数などは、図１０に示した変数などと同意である。【００９７】
実施例２に係る計算機システムは、図１６の（１）、（１−１）、（２）、および（３）に示したアルゴリズムによって、残差ベクトルを算出するまで（図１６の（１−１）参照）、一連の計算処理における命令文を１つ実行しつつ（図１６の（１）および（１−１）参照）、有意性を判定することが可能な状況に至った旨を問い合わせる（図１６の（２）および（３）参照）。ここで、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合には近似解ベクトルを判定し（図１６の（２）および（３）参照）、ノルムが収束判定閾値以上である場合には、図１６の（４）に示したアルゴリズムによって部分ノルムを算出し、図１６の（５）に示したアルゴリズムによって次のノルムを算出する。【００９８】
［実施例２の効果］
上記したように、実施例２によれば、計算処理が開始された後、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定するので、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。【００９９】
また、実施例２によれば、計算処理における所定の進捗間隔ごとに、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるので、計算パターンごとに総和ノルムが算出されたかを問い合わせつつ近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。【０１００】
また、実施例２によれば、計算結果を１回のみ余分に反復して算出するので、記憶すべき情報を増加させることなく反復解法を用いた計算処理を行うことが可能である。
【実施例３】
【０１０１】
ところで、上記の実施例２では、計算処理における所定の進捗間隔ごとに有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせる場合を説明したが、一連の計算処理に必要なリダクション通信ごとに有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるようにしてもよい。そこで、以下では、図１７を用いて、計算処理においてリダクション通信が必要になる状況ごとに総和計算の終了を問い合わせる場合を実施例３として説明する。ただし、反復計算部２５が解判定部２６に対して計算終了フラグレジスタ３７の参照を要求する時機が異なること以外は、上記した実施例２と同様であるので、実施例３に係る計算機システムによる処理の詳細は省略する。【０１０２】
［実施例３に係る計算機システムの概要および特徴］
実施例３に係る計算機システムは、実施例１に係る計算機システムと同じ構成および概要の下、必要以上にリダクション通信部に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことを特徴とする。【０１０３】
具体的に一例をあげて説明すると、図１１の（Ａ）における「＊２」に示すように、一連の計算処理にもリダクション通信が必要である。ここで、「＊２」に係るリダクション通信と、「＊１」に係るリダクション通信とにおける処理時間が同じである場合、「＊２」に係るリダクション通信が完了する前に、「＊１」に係るリダクション通信が完了する。すなわち、「＊２」に係るリダクション通信が完了した後に主演算部が計算終了フラグレジスタを参照すれば、必然的に総和計算が終了している可能性は高くなるため、必要以上に計算終了フラグレジスタを参照することなく自己の計算結果の有意性を判定することができる。【０１０４】
このようなことから、実施例３に係る計算機システムは、上記した特徴のごとく必要以上にリダクション通信部に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。【０１０５】
［実施例３に係る計算機システムによる処理］
次に、図１７を用いて、実施例３に係る計算機システムの処理の流れを説明する。図１７は、実施例３に係る計算機システムにおけるアルゴリズムである。ここで示した変数などは、図１０および図１６に示した変数などと同意である。【０１０６】
実施例３に係る計算機システムは、図１７の（１）に示したアルゴリズムによって一連の計算処理を実行し、図１７の（１）に示したアルゴリズムが終了した時点で、近似解ベクトルの判定が終了している可能性が高いことから、図１７の（２）に示したアルゴリズムによって近似解ベクトルを判定し、ノルムが収束判定閾値以上である場合には、図１７の（３）に示したアルゴリズムによって一連の計算処理を継続し、図１７の（４）に示したアルゴリズムによって部分ノルムを算出し、図１７の（５）に示したアルゴリズムによって次のノルムを算出する。【０１０７】
［実施例３の効果］
上記したように、実施例３によれば、計算処理において他の計算装置と通信が必要になる状況ごとに、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるので、必要以上にリダクション通信部３０に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【実施例４】
【０１０８】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、実施例４として、他の実施例を説明する。【０１０９】
例えば、実施例１〜３では、前処理付き共役勾配法によって解ベクトルを算出する場合を説明したが、本発明はこれに限定されるものではなく、一連の計算式を繰り返し実行する反復解法によって計算する場合（例えば、ヤコビ法など）であれば本発明を適用することができる。【０１１０】
また、実施例１〜３では、部分ノルムを反復計算部２５が算出する場合を説明したが、本発明はこれに限定されるものではなく、他の処理部（例えば、総和計算部３５など）が算出するようにしてもよい。【０１１１】
（システム構成等）
また、本実施例において説明した各処理のうち、この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報（例えば、図４などに示した記憶情報や、図１０、図１６、図１７などに示したアルゴリズム）については、特記する場合を除いて任意に変更することができる。【０１１２】
また、図示した計算機システムの各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる（例えば、図３において、解判定部２６をリダクション通信部３０における処理部３１に統合するなどできる）。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。【０１１３】
（計算プログラム）
ところで、上記の実施例では、ハードウェアロジックによって各種の処理を実現する場合を説明したが、本発明はこれに限定されるものではなく、あらかじめ用意されたプログラムをコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図１８を用いて、上記の実施例に示した計算システムと同様の機能を有する計算プログラムを実行するコンピュータの一例を説明する。図１８は、計算プログラムを実行するコンピュータを示す図である。【０１１４】
同図に示すように、表示装置としてのコンピュータ１１０は、入力部１２０、ＨＤＤ１３０、ＣＰＵ１４０、ＲＯＭ１５０、ＲＡＭ１６０および出力部１７０をバス１８０などで接続して構成される。【０１１５】
ＲＯＭ１５０には、上記の実施例１に示したプロセッサ１０と同様の機能を発揮する計算プログラム、つまり、図１８に示すように反復計算プログラム１５０ａと、解判定プログラム１５０ｂと、総和計算プログラム１５０ｃと、他プロセッサ側出入力処理プログラム１５０ｄとが、あらかじめ記憶されている。なお、これらのプログラム１５０ａ〜プログラム１５０ｄについては、図３に示したプロセッサ１０の各構成要素と同様、適宜統合または、分散してもよい。【０１１６】
そして、ＣＰＵ１４０がこれらのプログラム１５０ａ〜プログラム１５０ｄをＲＯＭ１５０から読み出して実行することで、図１８に示すように、プログラム１５０ａ〜プログラム１５０ｄは、反復計算プロセス１４０ａと、解判定プロセス１４０ｂと、総和計算プロセス１４０ｃと、他プロセッサ側出入力処理プロセス１４０ｄとして機能するようになる。なお、プロセス１４０ａ〜プロセス１４０ｄは、図３に示した、反復計算部２５と、解判定部２６と、総和計算部３５と、他プロセッサ側出入力処理部３６とにそれぞれ対応する。【０１１７】
そして、ＣＰＵ１４０はＲＡＭ１６０に記録された近似解ベクトルデータ１６０ａと、部分ノルムデータ１６０ｂと、総和計算結果データ１６０ｃと、他プロセッサ部分ノルムデータ１６０ｄとに基づいて計算プログラムを実行する。【０１１８】
なお、上記した各プログラム１５０ａ〜プログラム１５０ｄについては、必ずしも最初からＲＯＭ１５０に記憶させておく必要はなく、例えば、コンピュータ１１０の内外に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、またはコンピュータ１１０の内外に備えられるＨＤＤなどの「固定用の物理媒体」、さらには公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ１１０に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ１１０がこれから各プログラムを読み出して実行するようにしてもよい。
【産業上の利用可能性】
【０１１９】
以上のように、本発明に係る計算装置、計算方法および計算プログラムは、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、計算結果が有意であると判定されるまで計算処理を反復して実行することに有用であり、特に、反復解法を用いた計算処理の中で、通信オーバーヘッドとして多くの時間を必要とすることに適する。
【図１】
2009008086.tif 000003
【図２】
2009008086.tif 000004
【図３】
2009008086.tif 000005
【図４】
2009008086.tif 000006
【図５】
2009008086.tif 000007
【図６】
2009008086.tif 000008
【図７】
2009008086.tif 000009
【図８】
2009008086.tif 000010
【図９】
2009008086.tif 000011
【図１０】
2009008086.tif 000012
【図１１】
2009008086.tif 000013
【図１２】
2009008086.tif 000014
【図１３】
2009008086.tif 000015
【図１４】
2009008086.tif 000016
【図１５】
2009008086.tif 000017
【図１６】
2009008086.tif 000018
【図１７】
2009008086.tif 000019
【図１８】
2009008086.tif 000020
【図１９】
2009008086.tif 000021
【手続補正書】
【提出日】平成21年10月13日(2009.10.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算装置であって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手段と、
前記反復計算手段によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手段と、
前記有意性判定手段によって前記計算結果が有意であると判定された場合に、前記反復計算手段による計算処理を中止する中止手段と、
を備えたことを特徴とする計算装置。
【請求項２】
前記反復計算手段は、前記計算処理として、連立一次方程式における解ベクトルを反復して算出することを特徴とする請求項１に記載の計算装置。
【請求項３】
前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至った旨を前記通信部から通知された場合に、前記有意性を判定することを特徴とする請求項１記載の計算装置。
【請求項４】
前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせ、当該有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、前記有意性を判定することを特徴とする請求項１記載の計算装置。
【請求項５】
前記有意性判定手段は、前記計算処理における所定の進捗間隔ごとに、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせることを特徴とする請求項４に記載の計算装置。
【請求項６】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法であって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算工程と、
前記反復計算工程によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定工程と、
前記有意性判定工程によって前記計算結果が有意であると判定された場合に、前記反復計算工程による計算処理を中止する中止工程と、
を含んだことを特徴とする計算方法。
【請求項７】
通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法をコンピュータに実行させる計算プログラムであって、
前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手順と、
前記反復計算手順によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手順と、
前記有意性判定手順によって前記計算結果が有意であると判定された場合に、前記反復計算手順による計算処理を中止する中止手順と、
をコンピュータに実行させることを特徴とする計算プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、計算装置、計算方法および計算プログラムに関する。
【背景技術】
【０００２】
従来より、自動車の衝突シミュレーションやタンパク質構造解析などのコンピュータシミュレーションでは、計算プロセッサごとに一連の計算式を繰り返し実行する反復解法によって計算をしている。例えば、連立一次方程式を用いた反復解法は、既知の「行列Ａ」および「ベクトルｂ」に対して、式「Ａｘ＝ｂ」を満たすような解ベクトル「ｘ」を求める計算を行っている。そして、「行列Ａ」が要素に「０」を多く含む疎行列である場合、例えば、共役勾配法などの収束演算型の反復解法によって解ベクトルを求めることが一般的である。
【０００３】
また、収束演算型の反復解法は、近似解ベクトル「ｘｉ」（なお、これは、ｉに対応するｘを表す）を算出する近似解算出計算や近似解ベクトルの精度を示す「ノルム（｜ｂ−Ａｘｉ｜）」を算出する近似解精度計算を含んだ一連の計算処理を繰り返し行うことで、十分な精度まで収束した解ベクトル「ｘ」を計算する（非特許文献１および非特許文献２参照）。そして、近似解精度計算は、残差ベクトルにおける「ノルム」の総和計算が必要であり、「総和計算によって算出された「ノルム」が所定の収束判定閾値「ε」以上である場合には、一連の計算処理を繰り返し行い、「ノルム」が所定の収束判定閾値「ε」未満である場合には、算出された近似解ベクトル「ｘｉ」を解ベクトル「ｘ」とする収束判定」を行うことが一般的である。
【０００４】
また、例えば、特許文献１（特開２００２−２８８１４７号公報）に開示された発明のように、複数のプロセッサを搭載したメモリ分散型並列計算装置がある。このメモリ分散型並列計算装置を用いて反復解法を行う場合には、プロセッサごとに一連の計算処理を行い、近似解ベクトルおよび部分ノルムを算出する。そして、プロセッサ間における通信であるリダクション通信によって部分ノルムを通信することでプロセッサごとにノルムを算出し、所定の収束判定閾値「ε」と付き合わせることで収束判定する。
【０００５】
また、例えば、メモリ分散型並列計算装置によって前処理付き共役勾配法を行う場合には、図１９の（１）に示したアルゴリズムによって、近似解ベクトル「ｘｉ」および近似解ベクトルに対応した残差ベクトル「ｒｉ」を算出する。そして、図１９の（２）に示したアルゴリズムによって、部分ノルムを算出し、部分ノルムを総和計算することでノルム「｜ｒｉ｜」を算出し、ノルムを所定の収束判定閾値「ε」と付き合わせることで収束判定する。図１９は、従来技術に係るアルゴリズムである。ここで、図１９におけるαｉ、βｉ、γｉおよびρｉはスカラ変数を表し、ｐｉ、ｑｉ、ｒｉ、ｘｉおよびｚｉはベクトル変数を表し、ＡおよびＭ−１（なお、これは、Ｍインバースを表す）は、定数行列を表し、εはスカラ定数を表す。
【０００６】
【特許文献１】特開２００２−２８８１４７号公報
【非特許文献１】Ｒ．バーレット、外９名著、長谷川里美、外２名訳、「反復法  Ｔｅｍｐｌａｔｅｓ」、朝倉書店、（１９９６年）
【非特許文献２】Ｒｉｃｈａｒｄ  Ｂａｒｒｅｔｔ、外９名著、「Ｔｅｍｐｌａｔｅｓ  ｆｏｒ  ｔｈｅ  Ｓｏｌｕｔｉｏｎ  ｏｆ  Ｌｉｎｅａｒ  Ｓｙｓｔｅｍｓ：  Ｂｕｉｌｄｉｎｇ  Ｂｌｏｃｋｓ  ｆｏｒ  Ｉｔｅｒａｔｉｖｅ  Ｍｅｔｈｏｄｓ」、［ｏｎｌｉｎｅ］、［平成１８年４月１８日検索］インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｎｅｔｌｉｂ．ｏｒｇ／ｔｅｍｐｌａｔｅｓ／ｔｅｍｐｌａｔｅｓ．ｐｄｆ＞
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上記した従来の技術は、反復解法を用いた計算処理の中で、通信オーバーヘッドとして多くの時間を必要とするという課題があった。
【０００８】
具体的には、メモリ分散型並列計算装置は、例えば、浮動小数点計算における単位処理などの計算処理にかかる処理時間が１ナノ秒以下を必要とするのに対して、リダクション通信のレイテンシ（通信時間、実行時間）として数マイクロ秒程度を必要とし、収束判定を行った後に次の繰り返しを行っていた。この結果、収束判定に必要な総和計算におけるリダクション通信が発生する負荷の大きさである通信オーバーヘッドとして、１回の繰り返しに必要とする時間に対して、多くの時間を必要としていた。
【０００９】
また、メモリ分散型並列計算装置は、プロセッサを多数にわたって搭載した場合には、各プロセッサが行う計算量が減少するので、計算にかかる処理時間として少ない時間を必要とするのに対して、通信するプロセッサの数が多くなるので、リダクション通信のレイテンシとして多くの時間を必要とする。この結果、各プロセッサにおいて計算にかかる処理時間に対して、通信オーバーヘッドとして多くの時間を必要としていた。
【００１０】
また、メモリ分散型並列計算装置は、大規模連立一次方程式に対する反復解法を行う場合には、ノルムが収束判定閾値以上であると判定する確率が極めて高く、少なくとも数十回に渡って一連の計算処理を繰り返し行っていた。この結果、反復解法を用いて解ベクトルを求める計算にかかる処理時間に対して、通信オーバーヘッドとして多くの時間を必要としていた。
【００１１】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能な計算装置、計算方法および計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算装置であって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手段と、前記反復計算手段によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手段と、前記有意性判定手段によって前記計算結果が有意であると判定された場合に、前記反復計算手段による計算処理を中止する中止手段とを備えたことを特徴とする。
【００１３】
また、請求項２に係る発明は、上記の発明において、前記反復計算手段は、前記計算処理として、連立一次方程式における解ベクトルを反復して算出することを特徴とする。
【００１４】
また、請求項３に係る発明は、上記の発明において、前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至った旨を前記通信部から通知された場合に、前記有意性を判定することを特徴とする。
【００１５】
また、請求項４に係る発明は、上記の発明において、前記有意性判定手段は、前記反復計算手段によって前記計算処理が開始された後、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせ、当該有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、前記有意性を判定することを特徴とする。
【００１６】
また、請求項５に係る発明は、上記の発明において、前記有意性判定手段は、前記計算処理における所定の進捗間隔ごとに、前記有意性を判定することが可能な状況に至ったか否かを前記通信部に対して問い合わせることを特徴とする。
【００１７】
また、請求項６に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法であって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算工程と、前記反復計算工程によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定工程と、前記有意性判定工程によって前記計算結果が有意であると判定された場合に、前記反復計算工程による計算処理を中止する中止工程とを含んだことを特徴とする。
【００１８】
また、請求項７に係る発明は、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、前記計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、当該計算結果が有意であると判定されるまで前記計算処理を反復して実行する計算方法をコンピュータに実行させる計算プログラムであって、前記計算処理によって自己の計算結果が算出された後も、当該計算結果の有意性に対する判定を待たずに、前記計算処理を反復して実行する反復計算手順と、前記反復計算手順によって前記計算処理が開始された後、前記通信部によって他の計算装置から計算結果が受信されて前記有意性を判定することが可能な状況に至った場合に、前記自己の計算結果の有意性を判定する有意性判定手順と、前記有意性判定手順によって前記計算結果が有意であると判定された場合に、前記反復計算手順による計算処理を中止する中止手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００１９】
請求項１、６、７の発明によれば、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行し、計算処理が開始された後、通信部によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、計算処理を中止するので、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。
【００２０】
また、請求項２の発明によれば、計算処理として、連立一次方程式における解ベクトルを反復して算出するので、総和計算における通信オーバーヘッドを隠蔽し、短時間で連立一次方程式における解ベクトルを算出することが可能である。
【００２１】
また、請求項３の発明によれば、計算処理が開始された後、有意性を判定することが可能な状況に至った旨を通信部から通知された場合に、有意性を判定するので、有意性を判定することが可能な状況を示す割り込み信号によって通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。
【００２２】
また、請求項４の発明によれば、計算処理が開始された後、有意性を判定することが可能な状況に至ったか否かを通信部に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定するので、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【００２３】
また、請求項５の発明によれば、計算処理における所定の進捗間隔ごとに、有意性を判定することが可能な状況に至ったか否かを通信部に対して問い合わせるので、計算パターンごとに残差ノルムが算出されたかを問い合わせつつ近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【発明を実施するための最良の形態】
【００２４】
以下に添付図面を参照して、この発明に係る計算装置、計算方法および計算プログラムの実施例を詳細に説明する。なお、以下では、この発明を適用した「主演算部と、リダクション通信部とからなるプロセッサ」が、同じ構成からなる他のプロセッサや、入力部や、出力部とデータ通信用ネットワークを介して接続された計算機システムにおいて、前処理付き共役勾配法を用いて、解ベクトルを計算する例を実施例として説明する。
【実施例１】
【００２５】
以下の実施例１では、実施例１に係る計算機システムの概要および特徴、プロセッサの構成、計算機システムの処理の流れを順に説明し、最後に実施例１の効果を説明する。
【００２６】
［実施例１に係る計算機システムの概要および特徴］
まず最初に、図１および図２を用いて実施例１に係る計算機システムの概要および特徴を説明する。図１は、実施例１に係る計算機システムの概要および特徴を説明するための図であり、図２は、実施例１に係る計算機システムの時間的特徴を説明するための図である。
【００２７】
図１に示すように、実施例１に係る計算機システムは、主演算部（主演算部１〜ｎ）と、リダクション通信部（リダクション通信部１〜ｎ）とからなるプロセッサ（プロセッサ１〜ｎ）を複数に渡って備え、データ通信用ネットワークを介して接続された各プロセッサや入力部や出力部とから構成され、プロセッサごとに一連の計算を繰り返し実行し、解を計算する。
【００２８】
具体的には、計算機システムは、プロセッサごとに一連の計算処理を実行し、「行列Ａ」および「ベクトルｂ」を用いて近似解ベクトル「ｘｉ」（なお、これは、ｉに対応するｘを表す）と、部分ノルムとを繰り返し算出する。そして、計算機システムは、部分ノルムをプロセッサ間で通信し、部分ノルムを総和計算して近似解ベクトルの精度を示すノルムを算出する。さらに、計算機システムは、「「ノルム」が所定の収束判定閾値「ε」以上である場合には、一連の計算処理を繰り返し行い、「ノルム」が所定の収束判定閾値「ε」未満である場合には、算出された近似解ベクトル「ｘｉ」を解ベクトル「ｘ」とする収束判定」を行うことで十分な精度まで収束した解ベクトル「ｘ」を算出する。このような概要の下、実施例１に係る計算機システムは、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことを主たる特徴とする。
【００２９】
この主たる特徴について説明すると、実施例１に係る計算機システムは、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行する。具体的には、図１の（１−１）に示すように、各プロセッサにおける主演算部は、一連の計算処理を実行し、近似解および部分ノルムを算出する。そして、図１の（１−２）に示すように、主演算部は、リダクション通信部に対して、部分ノルムの総和計算を要求し、図１の（１−３）に示すように、一連の計算処理を反復して実行し、新たなる近似解ベクトルおよび部分ノルムの計算を開始する。
【００３０】
一方では、各プロセッサにおけるリダクション通信部は、図１の（２）に示すように、常時、他のプロセッサから部分ノルムを受信する。そして、リダクション通信部は、図１の（３−１）に示すように、各主演算部から総和計算の要求を受け付けた場合に、自プロセッサにおける主演算部が算出した部分ノルムを他のプロセッサに対して送信する。さらに、リダクション通信部は、図１の（３−２）に示すように、全ての他のプロセッサから部分ノルムを受け付けた後に、部分ノルムを総和計算することでノルムを算出し、図１の（３−３）に示すように、自プロセッサにおける主演算部に対して割り込み信号を送信することで総和計算の終了を通知する。
【００３１】
そして、実施例１に係る計算機システムは、リダクション通信部によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、計算処理を中止する。具体的には、割り込み信号を受け付けた主演算部は、図１の（４）に示すように、自プロセッサにおけるリダクション通信部が算出したノルムと、収束判定閾値とを付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合は、反復して実行した一連の計算処理を中止する。
【００３２】
このようなことから、実施例１に係る計算機システムは、上記した主たる特徴のごとく、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。すなわち、図２の（Ａ）に示すように、近似解ベクトルおよび部分ノルムを算出する計算時間（図２の（Ａ）の（１）参照）および全ての他のプロセッサから部分ノルムを受け付け、部分ノルムを総和計算するリダクション通信に必要な時間（図２の（Ａ）の（２）参照）を足し合わせた時間が１回の反復（ｉ＝０、１、２）に必要な計算時間（図２の（Ａ）の（３）参照）であったところ、実施例１に係る計算機システムは、リダクション通信に必要な時間の間に一連の計算処理を開始することで、反復するごとにオーバーヘッドを隠蔽し（図２の（Ｂ）の（４）および(５)参照）、全体として短時間で反復解法を用いた計算処理を行う（図２の（Ｂ）の（６）参照）。
【００３３】
［実施例１に係るプロセッサの構成］
次に、図３を用いて、実施例１に係るプロセッサの構成を説明する。図３は、実施例１に係るプロセッサの構成を示すブロック図である。同図に示すように、プロセッサ１０は、主演算部２０と、リダクション通信部３０とから構成される。
【００３４】
このうち、主演算部２０は、各種計算処理を規定したアルゴリズムを格納するためのメモリを有し、これらによって種々の計算処理を実行する。そして、本発明に密接に関係するものとしては、図３に示すように、処理部２１と、記憶部２２とを備える。
【００３５】
主演算部２０における記憶部２２は、データの処理を行うために必要な情報を一時的または長期的に記憶する。そして、本発明に密接に関係するものとしては、図３に示すように、近似解ベクトルレジスタ２３と、部分ノルムレジスタ２４とを備える。
【００３６】
近似解ベクトルレジスタ２３は、一連の計算処理によって算出された計算結果を記憶する。具体的に一例をあげて説明すると、近似解ベクトルレジスタ２３は、一連の計算処理によって算出された近似解ベクトル「ｘｉ」を記憶し、後述の反復計算部２５によって一連の計算処理が繰り返されるごとに書き換えられる。
【００３７】
部分ノルムレジスタ２４は、一連の計算処理によって算出された部分ノルムを記憶する。具体的に一例をあげて説明すると、部分ノルムレジスタ２４は、一連の計算処理によって算出された部分ノルムを記憶し、後述の反復計算部２５によって一連の計算処理が繰り返されるごとに書き換えられる。
【００３８】
主演算部２０における処理部２１は、各種処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、特に本発明に密接に関係するものとしては、反復計算部２５と、解判定部２６とを備える。なお、反復計算部２５は、請求の範囲に記載の「反復計算手段」に対応し、解判定部２６は、請求の範囲に記載の「有意性判定手段」および「中止手段」に対応する。
【００３９】
反復計算部２５は、計算処理によって自己の計算結果が算出された後も、この計算結果の有意性に対する判定を待たずに、計算処理を反復して実行する。具体的に一例をあげて説明すると、反復計算部２５は、「行列Ａ」のデータ（例えば、自動車の衝突シミュレーションを実行する場合には、形状から算出されるデータなど）が入力されると、一連の計算処理によって近似解ベクトルを算出し、近似解ベクトルレジスタ２３を書き換える。そして、部分ノルムを算出し、部分ノルムレジスタ２４を書き換える。さらに、反復計算部２５は、部分ノルムの総和計算をリダクション通信部３０に対して要求する。そして、反復計算部２５は、一連の計算処理を反復して新たなる近似解ベクトルの算出を開始する。一方で、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けた場合に、反復して実行した計算処理を中止し、近似解ベクトルレジスタ２３から近似解ベクトルを読み込み、解ベクトルとして出力する。
【００４０】
解判定部２６は、反復計算部２５によって計算処理が開始された後、リダクション通信部３０によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定する。具体的に一例をあげて説明すると、解判定部２６は、後述の総和計算部３５から割り込み信号を受け付けると、後述の総和計算結果レジスタ３３からノルムを読み込み、ノルムと収束判定閾値とを付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合に、反復計算部２５に対して、計算処理の中止信号を送信する。
【００４１】
リダクション通信部３０は、各種処理を規定したアルゴリズムを格納するためのメモリを有し、これらによって種々の処理を実行する。そして、本発明に密接に関係するものとしては、図３に示すように、処理部３１と、記憶部３２とを備える。
【００４２】
リダクション通信部３０における記憶部３２は、データの処理を行うために必要な情報を一時的または長期的に記憶する。そして、本発明に密接に関係するものとしては、図３に示すように、総和計算結果レジスタ３３と、他プロセッサ部分ノルム記憶部３４とを備える。
【００４３】
総和計算結果レジスタ３３は、総和計算によって算出された計算結果を記憶する。具体的に一例をあげて説明すると、総和計算結果レジスタ３３は、総和計算によって算出されたノルムを記憶し、後述の総和計算部３５によって書き換えられる。
【００４４】
他プロセッサ部分ノルム記憶部３４は、他のプロセッサによって算出された計算結果を記憶する。具体的に一例をあげて説明すると、他プロセッサ部分ノルム記憶部３４は、各プロセッサに予め付与されたプロセッサ番号と、各プロセッサにおけるネットワークアドレスと、各プロセッサが算出した部分ノルムを対応付けて記憶する。例えば、他プロセッサ部分ノルム記憶部３４は、図４に示すように、「ネットワークアドレスが１であるプロセッサ２」によって算出された部分ノルム「０．２１Ｅ−１４」（なお、これは、０．２１に１０のマイナス１４乗をかけた値を表す）を記憶する。なお、図４は、プロセッサ１における他プロセッサ部分ノルム記憶部に記憶される情報の一例を示した図であり、後述の他プロセッサ側出入力処理部３６によって部分ノルムが書き換えられる。
【００４５】
リダクション通信部３０における処理部３１は、各種処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。そして、特に本発明に密接に関係するものとしては、総和計算部３５と、他プロセッサ側出入力処理部３６とを備える。
【００４６】
総和計算部３５は、自己が算出した計算結果の有意性を判定する際に用いる判定値を計算する。具体的に一例をあげて説明すると、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付け、部分ノルムレジスタ２４から部分ノルムを読み込み、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信する。そして、総和計算部３５は、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納された場合に、部分ノルムレジスタ２４および他プロセッサ部分ノルム記憶部３４から部分ノルムを読み込み、部分ノルムの総和を計算することで、ノルムを算出する。さらに、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し、解判定部２６に対して割り込み信号を送信する。
【００４７】
他プロセッサ側出入力処理部３６は、他のプロセッサとの間で出入力処理する。具体的に一例をあげて説明すると、他プロセッサ側出入力処理部３６は、総和計算部３５から部分ノルムを受け付けた場合には、他の全てのプロセッサに対して部分ノルムを送信する。また、他のプロセッサから部分ノルムを受け付けた場合には、他プロセッサ部分ノルム記憶部３４に送信元のプロセッサ番号およびネットワークアドレスと対応付けて格納する。例えば、ネットワークアドレスが１であるプロセッサ２から部分ノルムを受け付けた場合には、ネットワークアドレスが１でありプロセッサ番号が２であるエントリに部分ノルムを格納する。
【００４８】
［実施例１に係る計算機システムによる処理］
次に、図５〜図１０を用いて、実施例１に係る計算機システムによる処理の流れを説明する。具体的には、反復計算部２５における一連の計算処理と、中止信号を受け付けた場合の反復計算部２５の処理と、解判定部２６の処理と、他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部３６の処理と、総和計算部３５の処理とを順に説明する。
【００４９】
まず最初に、図５を用いて、実施例１に係る反復計算部２５における一連の計算処理の流れを説明する。図５は、実施例１に係る反復計算部２５における一連の計算処理の流れを示すフローチャートである。
【００５０】
図５に示すように、反復計算部２５は、「行列Ａ」のデータが入力されると（ステップＳ１０１）、一連の計算処理によって近似解ベクトルを算出し（ステップＳ１０２）、近似解ベクトルを近似解ベクトルレジスタ２３に格納する（ステップＳ１０３）。
【００５１】
続いて、反復計算部２５は、部分ノルムを算出し（ステップＳ１０４）、部分ノルムを部分ノルムレジスタ２４に格納し（ステップＳ１０５）、部分ノルムの総和計算をリダクション通信部３０に対して要求し（ステップＳ１０６）、再び近似解ベクトルの算出を開始する（ステップＳ１０２）。このようにして、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けるまで計算処理を反復して実行する（ステップＳ１０２〜ステップＳ１０６）。
【００５２】
次に、図６を用いて、実施例１に係る中止信号を受け付けた場合の反復計算部２５の処理の流れを説明する。図６は、実施例１に係る中止信号を受け付けた場合の反復計算部の処理の流れを示すフローチャートである。
【００５３】
図６に示すように、反復計算部２５は、解判定部２６から計算処理の中止信号を受け付けると（ステップＳ２０１肯定）、近似解ベクトルを読み込み、解ベクトルとして出力し（ステップＳ２０２）、計算機システム全体の処理を終了する。
【００５４】
次に、図７を用いて、実施例１に係る解判定部２６の処理の流れを説明する。図７は、実施例１に係る解判定部の処理の流れを示すフローチャートである。
【００５５】
図７に示すように、解判定部２６は、総和計算部３５から割り込み信号を受け付けると（ステップＳ３０１肯定）、総和計算結果レジスタ３３からノルムを読み込み（ステップＳ３０２）、ノルムと収束判定閾値と付き合わせ、ノルムが収束判定閾値と等しいか大きいと判定した場合には（ステップＳ３０３肯定）、上記した処理（ステップＳ３０１〜ステップＳ３０３）を終了して、再び割り込み信号を待機する（ステップＳ３０１）。
【００５６】
一方で、ノルムが収束判定閾値未満であると判定した場合（ステップＳ３０３否定）、解判定部２６は、反復計算部２５に対して、計算処理の中止信号を送信し（ステップＳ３０４）、上記した処理（ステップＳ３０１〜ステップＳ３０４）を終了する。
【００５７】
次に、図８を用いて、実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部３６の処理の流れを説明する。図８は、実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部の処理の流れを示すフローチャートである。
【００５８】
図８に示すように、他プロセッサ側出入力処理部３６は、他のプロセッサから部分ノルムを受け付けると（ステップＳ４０１肯定）、部分ノルムを他プロセッサ部分ノルム記憶部３４に送信元のプロセッサ番号およびネットワークアドレスと対応付けて格納し（ステップＳ４０２）、上記した処理を終了して、再び他のプロセッサからの部分ノルムを待機する（ステップＳ４０１）。
【００５９】
次に、図９を用いて、実施例１に係る総和計算部３５の処理の流れを説明する。図９は、実施例１に係る総和計算部の処理の流れを示すフローチャートである。
【００６０】
図９に示すように、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付けると（ステップ５０１肯定）、部分ノルムレジスタ２４から部分ノルムを読み込み（ステップＳ５０２）、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信し（ステップＳ５０３）、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されるまで待機する（ステップＳ５０４否定）。
【００６１】
ここで、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されたことを確認すると（ステップＳ５０４肯定）、総和計算部３５は、部分ノルムレジスタ２４から自プロセッサによって算出された部分ノルムを読み込み（ステップＳ５０５）、他プロセッサ部分ノルム記憶部３４から他のプロセッサによって算出された部分ノルムを読み込み（ステップＳ５０６）、部分ノルムの総和を計算することで、ノルムを算出する（ステップＳ５０７）。
【００６２】
続いて、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し（ステップＳ５０８）、解判定部２６に対して割り込み信号を送信し（ステップＳ５０９）、上記した処理を終了して、再び部分ノルムの総和計算要求を待機する（ステップＳ５０１）。
【００６３】
次に、図１０を用いて、実施例１に係る計算機システムの処理の流れを説明する。図１０は、実施例１に係る計算機システムにおけるアルゴリズムである。ここで、図１０におけるαｉ、βｉ、γｉおよびρｉはスカラ変数を表し、ｐｉ、ｑｉ、ｒｉ、ｘｉおよびｚｉはベクトル変数を表し、ＡおよびＭ−１（なお、これは、Ｍインバースを表す）は定数行列を表し、εはスカラ定数を表す。
【００６４】
実施例１に係る計算機システムは、図１０の（１）に示したアルゴリズムによって、割り込みを待機しつつ、図１０の（２）に示したアルゴリズムによって一連の計算処理を実行する。そして、実施例１に係る計算機システムは、図１０の（３）に示したアルゴリズムによって部分ノルムを算出し、図１０の（４）に示したアルゴリズムによってノルムを算出し、算出した近似解ベクトルが有意か否かを判定し、近似解ベクトルが有意である場合には一連の計算処理を中止する。
【００６５】
［実施例１の効果］
上記したように、実施例１によれば、計算処理によって自己の計算結果が算出された後も、計算結果の有意性に対する判定を待たずに、計算処理を反復して実行し、計算処理が開始された後、リダクション通信部３０によって他の計算装置から計算結果が受信されて有意性を判定することが可能な状況に至った場合に、自己の計算結果の有意性を判定し、計算結果が有意であると判定された場合に、反復計算部２０による計算処理を中止するので、通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。
【００６６】
すなわち、１回の繰り返しに必要な処理時間の中で、大きな比重を占めていた収束判定に必要な総和計算におけるリダクション通信を隠蔽する結果、短時間で反復解法を用いた計算処理を行うことができる。また、総和計算におけるリダクション通信を隠蔽して、計算にかかる処理時間に対してリダクション通信にかかる処理時間の割合を少なくする結果、プロセッサを多数にわたって搭載した場合に、効率よく短時間で反復解法を用いた計算処理を行うことができる。さらに、総和計算におけるリダクション通信を繰り返し隠蔽する結果、反復解法を用いて解ベクトルを求める計算にかかる処理時間として、より短時間で反復解法を用いた計算処理を行うことができる。
【００６７】
また、実施例１によれば、計算処理として、連立一次方程式における解ベクトルを反復して算出するので、総和計算における通信オーバーヘッドを隠蔽し、短時間で連立一次方程式における解ベクトルを算出することが可能である。
【００６８】
また、実施例１によれば、計算処理が開始された後、有意性を判定することが可能な状況に至った旨をリダクション通信部３０から通知された場合に、有意性を判定するので、有意性を判定することが可能な状況を示す割り込み信号によって通信オーバーヘッドを隠蔽し、短時間で反復解法を用いた計算処理を行うことが可能である。
【００６９】
ここで、図１１を用いて、実施例１に関る計算システムによる効果を説明する。図１１は、実施例１に係る計算システムによる効果を説明するための図である。図１１の（Ａ）は、一連の計算処理における実行文ごとに、必要な演算コストおよび通信パターンを対応付けて示した図であり、例えば、ノルムを総和計算させる命令文である「if  (|ri|  <  ε)  then  break」を実行する際に必要な演算コストは「Ｏ（２Ｎ＋１）」であり、通信パターンは「リダクション通信を１回」必要とすることを示す。また、図１１の（Ａ）における合計は、従来技術に係るアルゴリズムを１回実行、言い換えると、一連の計算処理を１回実行する際に必要な演算コストおよび通信パターンを示す。ここで、例えば、図１１の（Ａ）における演算コスト「Ｏ（１）」は、掛け算などを１回行う際に必要な演算コストを表し、「近接通信」は、近接するプロセッサとの通信処理を表し、「リダクション通信」は、他の全てのプロセッサとの通信処理を表す。
【００７０】
また、図１１の（Ｂ）は、各変数に対して見積もりパラメータおよび内容の説明を示した図であり、例えば、変数「ｐ」は、使用するプロセッサの数として、「５１２０個」のプロセッサを搭載した計算機システム（図１におけるｎに対応する）であることを示す。ここで、図１１の（Ｂ）における「Ｎ」、「ｋ」または「ｐ」は、行列または計算システムの一例として表した数値であり、ＣＮおよびＣＲは、既存のメモリ分散型並列計算装置における実測値の一例として表した数値である。また、変数Ｎの見積もりパラメータ「１０７」は、「１０の７乗」を表す。
【００７１】
また、図１１の（Ｃ）は、見積もり式として、プロセッサ数が「ｐ」である計算機システムにおいて、本発明を適用する前または適用後における一連の計算処理を１回実行する際に必要な処理コストを見積もる式を示し、例えば、適用前の見積もり式は、図１１の（Ａ）における合計として示した演算コスト（一部を除く）をプロセッサ数で割り、各通信パターンの相対コストを加えた式となる。そして、この見積もり式に、図１１の（Ｂ）に示した各変数における見積もりパラメータを代入した場合における、見積もり結果および実行時間比を示す。
【００７２】
さて、実施例１に関る計算システムは、図１１の（Ａ）において「＊１」で示した、リダクション通信、すなわち、総和計算に必要なリダクション通信を隠蔽するという効果を奏する。ここで、本発明を適用する前または適用した後における一連の計算処理を１回実行するごとにかかる処理コストは、図１１の（Ｃ）における見積もり式によって算出され、図１１の（Ｂ）に示した見積もりパラメータを各変数に代入することで算出される本発明を適用する前または適用した後における見積もり結果から、実行時間比が本発明を適用後には「７７．９０％」となる。すなわち、実施例１に係る計算システムは、本発明適用前に比べ、「７７．９０％」の時間で解ベクトルを算出することが可能である。
【実施例２】
【００７３】
ところで、上記の実施例１では、リダクション通信部が主演算部に対して割り込み番号を割り込みで送信することで総和計算の終了を通知する場合を説明したが、本発明はこれに限定されるものではなく、例えば、主演算部がリダクション通信部に対して、総和計算の終了を問い合わせるようにしてもよい。そこで、以下では、図１２〜図１６を用いて、主演算部がリダクション通信部に対して、総和計算の終了を問い合わせる場合を実施例２として説明する。
【００７４】
［実施例２に係る計算機システムの概要および特徴］
図１２は、実施例２に係る概要および特徴を説明するための図であり、同図に示すように、実施例２に係る計算機システムは、実施例１に係る計算機システムと同じ構成および概要の下、一時的に一連の計算処理を停止することなく近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことを特徴とする。具体的には、各プロセッサにおける主演算部は、図１２の（１−１）に示すように、反復して計算しつつ、計算パターンごとに総和計算の終了をリダクション通信装置に対して問い合わせる。そして、図１２の（１−２）に示すように、主演算部は、リダクション通信部に対して、部分ノルムの総和計算を要求する。
【００７５】
一方では、各プロセッサにおけるリダクション通信部は、実施例１に係る計算機システムと同様に、図１２の（２）に示すように、常時、他のプロセッサから部分ノルムを受信する。そして、リダクション通信部は、図１２の（３−１）に示すように、各主演算部から総和計算の要求を受け付けた場合に、自プロセッサにおける主演算部が算出した部分ノルムを他のプロセッサに対して送信する。さらに、リダクション通信部は、図１２の（３−２）に示すように。全ての他のプロセッサから部分ノルムを受け付けた後に、部分ノルムを総和計算することでノルムを算出する。
【００７６】
そして、実施例２に係る計算機システムは、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定する。具体的には、図１２の（１−１）において、総和計算の終了をリダクション通信装置に対して問い合わせた結果、総和計算が終了していた場合に、図１２の（４）に示すように、近似解ベクトルを判定する。
【００７７】
このようなことから、実施例２に係る計算機システムは、上記した特徴のごとく、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【００７８】
［実施例２に係る計算機システムの構成］
実施例２に係る計算機システムは、リダクション通信部３０における記憶部３２において、計算終了フラグレジスタ３７を新たに備える他は、図３に示した計算機システム１０と同様の構造を有す。また、以下に説明する反復計算部２５、解判定部２６、総和計算部３５および計算終了フラグレジスタ３７を除き同様に動作する。ここでは、計算終了フラグレジスタ３７、解判定部２６のみを説明し、反復計算部２５および総和計算部３５は、後に詳細に説明する。
【００７９】
計算終了フラグレジスタ３７は、各処理の実行状態を示す値を記憶する。具体的に一例をあげて説明すると、計算終了フラグレジスタ３７は、ノルムの算出を終了した旨を示し、解判定部２６による有意性の判定の契機となる「１」と、ノルムの算出が終了していない旨を示し、解判定部２６による有意性の判定を待機させる「０」とを記憶し、総和計算部３５および解判定部２６によって書き換えられる。
【００８０】
解判定部２６は、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定する。具体的に一例をあげて説明すると、解判定部２６は、反復計算部２５から計算終了フラグレジスタ３７の参照要求を受け付け、計算終了フラグレジスタ３７に有意性の判定の契機となる「１」が記憶されている場合、総和計算結果レジスタ３３からノルムを読み込む。そして、ノルムと収束判定閾値と付き合わせることで、算出した近似解ベクトルが有意か否かを判定する。ここで、ノルムが収束判定閾値未満であった場合に、反復計算部２５に対して、計算処理の中止信号を送信する。一方で、ノルムが収束判定閾値以上であった場合に、解判定部２６は、計算終了フラグレジスタ３７を有意性の判定を待機させる「０」に書き換え、近似解ベクトルの判定が終了した旨を反復計算部２５に対して送信する。
【００８１】
［実施例２に係る計算機システムによる処理］
次に、図１３を用いて、実施例２に係る反復計算部の処理を説明する。図１３は、実施例２に係る反復計算部の処理の流れを示すフローチャートである。
【００８２】
図１３に示すように、反復計算部２５は、「行列Ａ」のデータが入力されると（ステップＳ６０１）、命令文を１つ実行し（ステップＳ６０２）、解判定部２６に対して計算終了フラグレジスタ３７の参照を要求する（ステップＳ６０３）。ここで、解判定部２６から近似解ベクトルの判定が終了した旨を受信していない場合（ステップＳ６０４否定）、反復計算部２５は、残差ベクトルを算出していない場合には（ステップＳ６０５否定）、残差ベクトルを算出するまで、命令文を実行しつつ計算終了フラグレジスタの参照を要求する（ステップＳ６０２〜ステップＳ６０５）。また、残差ベクトルを算出している場合には（ステップＳ６０５肯定）、計算終了フラグレジスタの参照を要求するのみで部分ノルムの算出を待機する（ステップＳ６０３〜ステップＳ６０５）。
【００８３】
一方で、１回目の計算処理であるまたは解判定部２６から近似解ベクトルの判定が終了した旨を受信した場合には（ステップＳ６０４肯定）、反復計算部２５は、残差ベクトルを算出するまで命令文を全て実行したか否かを判定し（ステップＳ６０６）、残差ベクトルを算出するまで命令文を全て実行している場合には、そのまま部分ノルムを算出する（ステップＳ６０８）。一方で、残差ベクトルを算出するまで命令文を全て実行していない場合には（ステップＳ６０６否定）、残差ベクトルを算出するまで命令文を実行し（ステップＳ６０７）、部分ノルムを算出する（ステップＳ６０８）。
【００８４】
続いて、反復計算部２５は、部分ノルムを部分ノルムレジスタ２４に格納し（ステップＳ６０９）、部分ノルムの総和計算をリダクション通信部３０に対して要求し（ステップＳ６１０）、再び命令文を１つ実行することで計算処理を反復して実行する（ステップＳ６０２〜ステップＳ６１０）。
【００８５】
次に、図１４を用いて、実施例２に係る解判定部２６の処理の流れを説明する。図１４は、実施例２に係る解判定部の処理の流れを示すフローチャートである。
【００８６】
図１４に示すように、解判定部２６は、反復計算部２５から計算終了フラグレジスタ３７の参照要求を受け付けると（ステップＳ７０１肯定）、計算終了フラグレジスタ３７を参照し（ステップＳ７０２）、計算終了フラグレジスタ３７に「１」が記憶されていない場合には（ステップＳ７０２否定）、再び計算終了フラグレジスタ３７の参照要求を待機する（ステップＳ７０１）。
【００８７】
一方で、計算終了フラグレジスタ３７に「１」が記憶されている場合には（ステップＳ７０２肯定）、総和計算結果レジスタ３３からノルムを読み込み（ステップＳ７０３）、ノルムと収束判定閾値と付き合わせることで、算出した近似解ベクトルが有意か否かを判定する（ステップＳ７０４）。
【００８８】
ここで、ノルムが収束判定閾値未満であると判定した場合（ステップＳ７０４否定）、解判定部２６は、反復計算部２５に対して、計算処理の中止信号を送信し（ステップＳ７０５）、上記した処理（ステップＳ７０１〜ステップＳ７０５）を終了する。
【００８９】
一方で、ノルムが収束判定閾値以上であると判定した場合（ステップＳ７０４肯定）、解判定部２６は、計算終了フラグレジスタ３７を「０」に書き換え、近似解ベクトルの判定が終了した旨を反復計算部２５に対して送信し（ステップＳ７０６）、上記した処理を終了して、再び計算終了フラグレジスタ３７の参照要求を待機する（ステップＳ７０１）。
【００９０】
次に、図１５を用いて、実施例２に係る総和計算部３５の処理の流れを説明する。図１５は、実施例２に係る総和計算部の処理の流れを示すフローチャートである。
【００９１】
図１５に示すように、総和計算部３５は、反復計算部２５から部分ノルムの総和計算要求を受け付けると（ステップ８０１肯定）、部分ノルムレジスタ２４から部分ノルムを読み込み（ステップＳ８０２）、他プロセッサ側出入力処理部３６を介して他のプロセッサに対して部分ノルムを送信し（ステップＳ８０３）、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されるまで待機する（ステップＳ８０４否定）。
【００９２】
ここで、他プロセッサ部分ノルム記憶部３４に全ての他プロセッサから受け付けた部分ノルムが格納されたことを確認すると（ステップＳ８０４肯定）、総和計算部３５は、部分ノルムレジスタ２４から自プロセッサによって算出された部分ノルムを読み込み（ステップＳ８０５）、他プロセッサ部分ノルム記憶部３４から他のプロセッサによって算出された部分ノルムを読み込み（ステップＳ８０６）、部分ノルムの総和を計算することで、ノルムを算出する（ステップＳ８０７）。
【００９３】
続いて、総和計算部３５は、ノルムを総和計算結果レジスタ３３に格納し（ステップＳ８０８）、計算終了フラグレジスタ３７を「１」に書き換え（ステップＳ８０９）、上記した処理を終了して、再び部分ノルムの総和計算要求を待機する（ステップＳ８０１）。
【００９４】
次に、図１６を用いて、実施例２に係る計算機システムの処理の流れを説明する。図１６は、実施例２に係る計算機システムにおけるアルゴリズムである。ここで示した変数などは、図１０に示した変数などと同意である。
【００９５】
実施例２に係る計算機システムは、図１６の（１）、（１−１）、（２）、および（３）に示したアルゴリズムによって、残差ベクトルを算出するまで（図１６の（１−１）参照）、一連の計算処理における命令文を１つ実行しつつ（図１６の（１）および（１−１）参照）、有意性を判定することが可能な状況に至った旨を問い合わせる（図１６の（２）および（３）参照）。ここで、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合には近似解ベクトルを判定し（図１６の（２）および（３）参照）、ノルムが収束判定閾値以上である場合には、図１６の（４）に示したアルゴリズムによって部分ノルムを算出し、図１６の（５）に示したアルゴリズムによって次のノルムを算出する。
【００９６】
［実施例２の効果］
上記したように、実施例２によれば、計算処理が開始された後、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせ、有意性を判定することが可能な状況に至った旨を問い合わせ結果として取得した場合に、有意性を判定するので、有意性を判定することが可能な状況の問い合わせによって通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【００９７】
また、実施例２によれば、計算処理における所定の進捗間隔ごとに、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるので、計算パターンごとに総和ノルムが算出されたかを問い合わせつつ近似解ベクトルを算出することで、通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【００９８】
また、実施例２によれば、計算結果を１回のみ余分に反復して算出するので、記憶すべき情報を増加させることなく反復解法を用いた計算処理を行うことが可能である。
【実施例３】
【００９９】
ところで、上記の実施例２では、計算処理における所定の進捗間隔ごとに有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせる場合を説明したが、一連の計算処理に必要なリダクション通信ごとに有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるようにしてもよい。そこで、以下では、図１７を用いて、計算処理においてリダクション通信が必要になる状況ごとに総和計算の終了を問い合わせる場合を実施例３として説明する。ただし、反復計算部２５が解判定部２６に対して計算終了フラグレジスタ３７の参照を要求する時機が異なること以外は、上記した実施例２と同様であるので、実施例３に係る計算機システムによる処理の詳細は省略する。
【０１００】
［実施例３に係る計算機システムの概要および特徴］
実施例３に係る計算機システムは、実施例１に係る計算機システムと同じ構成および概要の下、必要以上にリダクション通信部に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことを特徴とする。
【０１０１】
具体的に一例をあげて説明すると、図１１の（Ａ）における「＊２」に示すように、一連の計算処理にもリダクション通信が必要である。ここで、「＊２」に係るリダクション通信と、「＊１」に係るリダクション通信とにおける処理時間が同じである場合、「＊２」に係るリダクション通信が完了する前に、「＊１」に係るリダクション通信が完了する。すなわち、「＊２」に係るリダクション通信が完了した後に主演算部が計算終了フラグレジスタを参照すれば、必然的に総和計算が終了している可能性は高くなるため、必要以上に計算終了フラグレジスタを参照することなく自己の計算結果の有意性を判定することができる。
【０１０２】
このようなことから、実施例３に係る計算機システムは、上記した特徴のごとく必要以上にリダクション通信部に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【０１０３】
［実施例３に係る計算機システムによる処理］
次に、図１７を用いて、実施例３に係る計算機システムの処理の流れを説明する。図１７は、実施例３に係る計算機システムにおけるアルゴリズムである。ここで示した変数などは、図１０および図１６に示した変数などと同意である。
【０１０４】
実施例３に係る計算機システムは、図１７の（１）に示したアルゴリズムによって一連の計算処理を実行し、図１７の（１）に示したアルゴリズムが終了した時点で、近似解ベクトルの判定が終了している可能性が高いことから、図１７の（２）に示したアルゴリズムによって近似解ベクトルを判定し、ノルムが収束判定閾値以上である場合には、図１７の（３）に示したアルゴリズムによって一連の計算処理を継続し、図１７の（４）に示したアルゴリズムによって部分ノルムを算出し、図１７の（５）に示したアルゴリズムによって次のノルムを算出する。
【０１０５】
［実施例３の効果］
上記したように、実施例３によれば、計算処理において他の計算装置と通信が必要になる状況ごとに、有意性を判定することが可能な状況に至ったか否かをリダクション通信部３０に対して問い合わせるので、必要以上にリダクション通信部３０に対して問い合わせることなく通信オーバーヘッドを隠蔽し、さらに短時間で反復解法を用いた計算処理を行うことが可能である。
【実施例４】
【０１０６】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、実施例４として、他の実施例を説明する。
【０１０７】
例えば、実施例１〜３では、前処理付き共役勾配法によって解ベクトルを算出する場合を説明したが、本発明はこれに限定されるものではなく、一連の計算式を繰り返し実行する反復解法によって計算する場合（例えば、ヤコビ法など）であれば本発明を適用することができる。
【０１０８】
また、実施例１〜３では、部分ノルムを反復計算部２５が算出する場合を説明したが、本発明はこれに限定されるものではなく、他の処理部（例えば、総和計算部３５など）が算出するようにしてもよい。
【０１０９】
（システム構成等）
また、本実施例において説明した各処理のうち、この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報（例えば、図４などに示した記憶情報や、図１０、図１６、図１７などに示したアルゴリズム）については、特記する場合を除いて任意に変更することができる。
【０１１０】
また、図示した計算機システムの各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる（例えば、図３において、解判定部２６をリダクション通信部３０における処理部３１に統合するなどできる）。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１１１】
（計算プログラム）
ところで、上記の実施例では、ハードウェアロジックによって各種の処理を実現する場合を説明したが、本発明はこれに限定されるものではなく、あらかじめ用意されたプログラムをコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図１８を用いて、上記の実施例に示した計算システムと同様の機能を有する計算プログラムを実行するコンピュータの一例を説明する。図１８は、計算プログラムを実行するコンピュータを示す図である。
【０１１２】
同図に示すように、表示装置としてのコンピュータ１１０は、入力部１２０、ＨＤＤ１３０、ＣＰＵ１４０、ＲＯＭ１５０、ＲＡＭ１６０および出力部１７０をバス１８０などで接続して構成される。
【０１１３】
ＲＯＭ１５０には、上記の実施例１に示したプロセッサ１０と同様の機能を発揮する計算プログラム、つまり、図１８に示すように反復計算プログラム１５０ａと、解判定プログラム１５０ｂと、総和計算プログラム１５０ｃと、他プロセッサ側出入力処理プログラム１５０ｄとが、あらかじめ記憶されている。なお、これらのプログラム１５０ａ〜プログラム１５０ｄについては、図３に示したプロセッサ１０の各構成要素と同様、適宜統合または、分散してもよい。
【０１１４】
そして、ＣＰＵ１４０がこれらのプログラム１５０ａ〜プログラム１５０ｄをＲＯＭ１５０から読み出して実行することで、図１８に示すように、プログラム１５０ａ〜プログラム１５０ｄは、反復計算プロセス１４０ａと、解判定プロセス１４０ｂと、総和計算プロセス１４０ｃと、他プロセッサ側出入力処理プロセス１４０ｄとして機能するようになる。なお、プロセス１４０ａ〜プロセス１４０ｄは、図３に示した、反復計算部２５と、解判定部２６と、総和計算部３５と、他プロセッサ側出入力処理部３６とにそれぞれ対応する。
【０１１５】
そして、ＣＰＵ１４０はＲＡＭ１６０に記録された近似解ベクトルデータ１６０ａと、部分ノルムデータ１６０ｂと、総和計算結果データ１６０ｃと、他プロセッサ部分ノルムデータ１６０ｄとに基づいて計算プログラムを実行する。
【０１１６】
なお、上記した各プログラム１５０ａ〜プログラム１５０ｄについては、必ずしも最初からＲＯＭ１５０に記憶させておく必要はなく、例えば、コンピュータ１１０の内外に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、またはコンピュータ１１０の内外に備えられるＨＤＤなどの「固定用の物理媒体」、さらには公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ１１０に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ１１０がこれから各プログラムを読み出して実行するようにしてもよい。
【産業上の利用可能性】
【０１１７】
以上のように、本発明に係る計算装置、計算方法および計算プログラムは、通信部によって互いに通信可能に接続された複数の計算装置との間で分担して計算処理を実行するとともに、計算処理によって自己が算出した計算結果の有意性を他の計算装置で算出された計算結果を用いて判定し、計算結果が有意であると判定されるまで計算処理を反復して実行することに有用であり、特に、反復解法を用いた計算処理の中で、通信オーバーヘッドとして多くの時間を必要とすることに適する。
【図面の簡単な説明】
【０１１８】
【図１】実施例１に係る計算機システムの概要および特徴を説明するための図である。
【図２】実施例１に係る計算機システムの時間的特徴を説明するための図である。
【図３】実施例１に係るプロセッサの構成を示すブロック図である。
【図４】プロセッサ１における他プロセッサ部分ノルム記憶部に記憶される情報の一例を示した図である。
【図５】実施例１に係る反復計算部における一連の計算処理の流れを示すフローチャートである。
【図６】実施例１に係る中止信号を受け付けた場合の反復計算部の処理の流れを示すフローチャートである。
【図７】実施例１に係る解判定部の処理の流れを示すフローチャートである。
【図８】実施例１に係る他のプロセッサから部分ノルムを受け付けた場合における他プロセッサ側出入力処理部の処理の流れを示すフローチャートである。
【図９】実施例１に係る総和計算部の処理の流れを示すフローチャートである。
【図１０】実施例１に係る計算機システムにおけるアルゴリズムを示す図である。
【図１１】実施例１に係る計算システムによる効果を説明するための図である。
【図１２】実施例２に係る概要および特徴を説明するための図である。
【図１３】実施例２に係る反復計算部の処理の流れを示すフローチャートである。
【図１４】実施例２に係る解判定部の処理の流れを示すフローチャートである。
【図１５】実施例２に係る総和計算部の処理の流れを示すフローチャートである。
【図１６】実施例２に係る計算機システムにおけるアルゴリズムを示す図である。
【図１７】実施例３に係る計算機システムにおけるアルゴリズムを示す図である。
【図１８】計算プログラムを実行するコンピュータを示す図である。
【図１９】従来技術に係るアルゴリズムを示す図である。
【符号の説明】
【０１１９】
１０  プロセッサ
２０  主演算部
２１  処理部
２２  記憶部
２３  近似解ベクトルレジスタ
２４  部分ノルムレジスタ
２５  反復計算部
２６  解判定部
３０  リダクション通信部
３１  処理部
３２  記憶部
３３  総和計算結果レジスタ
３４  他プロセッサ部分ノルム記憶部
３５  総和計算部
３６  他プロセッサ側出入力処理部
３７  計算終了フラグレジスタ
【国際調査報告】
2009008086.tif 000022
2009008086.tif 000023