JP2006092519A - スプレッドシート連鎖計算の多重スレッド処理のための方法およびシステム - Google Patents

Abstract

【課題】 スプレッドシートプログラムにおいて個別の再計算エンジンをそれぞれ有する複数のプロセッサを使用して連鎖計算を同時に処理する方法を提供する。
【解決手段】 処理は、まず利用可能なプロセッサの数を決定し、次いで各利用可能なプロセッサに再計算エンジンを割り当て、再計算エンジン間に式を分配し、次いでスプレッドシートプログラムにおいて再計算処理が要求されたときに各再計算エンジンに分配された式を同時に評価することを含む。
【選択図】 図１

Description

本発明は、スプレッドシート演算処理に関し、より詳細には、多重プロセッサ環境で実行されるスプレッドシートプログラムにおける連鎖計算に関する。

マイクロソフトエクセルのような従来のスプレッドシートプログラムは、基本的には、現在エクセルによってロードされているすべてのワークシートに入力されたすべての式の順序リストである、単一の計算鎖を利用するスプレッドシート内での式の計算および再計算を扱う。さらに、この計算鎖に関係する各変数の単一のコピーが存在する。式がワークシートに入力されると、その式は、全計算鎖の最初に追加される。式が依存するセルの内容を修正するか、または手動で再計算工程を要求することによって、再計算工程が開始されると、エクセルは、計算鎖を反復し、「ダーティ」（すなわち再計算待ち）と標示されたあらゆる式を再計算する。したがって、単一の制御スレッドが、式の単一鎖を反復する。計算鎖は保存されて、その順序を保存するための情報とともにファイルされる。次いで、スプレッドシートおよび計算鎖の鎖を再ロードすると、式は、式を処理するために、それらの依存性に応じて適切な順序に配置される。これにより、エクセルは、作業を繰り返して、計算鎖を順序付けなくてもよくなる。

以下のシナリオは、従来のスプレッドシートプログラム連鎖計算ルーチンが各式間の依存性をどのように扱うかを例示するものである。図１５に示されたワークシート１０を考えてみる。スプレッドシート１０のための計算鎖１２を図１６のように表すことができる。この従来のスプレッドシート鎖１２において、符号は、常に左側の第１のセルから評価する。上記の場合は、符号は、第１のセルＣ４を評価することから開始する。式「＝Ａ４＋Ｂ４」を評価しようとするときに、計算符号は、式がセルＡ４に依存すること、およびセルＡ４が「ダーティ」である、すなわちまだ計算されていないことを発見する。この状況において、式「＝Ａ４＋Ｂ４」を「従属」式と呼び、セルＡ４における式を「補助」式と呼ぶ。符号は、式＝Ａ４＋Ｂ４の評価を停止し、セルＡ４に対する式を計算鎖から引き抜き、セルＣ４に対する式の直前にそれを再挿入する。次いで、計算符号は、セルＡ４に対する式から、その作業を再開する。計算符号は、Ａ４を問題なく評価し、Ｃ４に移る。式＝Ａ４＋Ｂ４を（二度目に）評価しようとするときに、計算符号は、計算符号は、現在Ａ４が計算されている（「ダーティ」ではない）ことを知るが、式はセルＢ４にも依存し、Ｂ４もダーティであることを発見する。そこで、符号は、再度式の評価を停止し、Ｂ４に対する式をＣ４に対する式の直前まで移動させる。次いで、符号は、Ｂ４を問題なく評価し、Ｃ４に移る（これで三度目）。ここでＣ４を評価し、プロセスを完了することができる。再順序付けされた鎖１４が図１７に示されている。

次いで、スプレッドシートに加えられた何らかの変化により再計算が手動または自動で要求される毎に、スプレッドシートプログラムがこの解析および再順序付けを再度行わなくてもよいように、この再順序鎖１４を次に再計算工程に向けて保存する。特に大規模な財務予測シナリオにおける極めて複雑なスプレッドシートの需要により、上述のようにして長い連鎖計算を実行するに、実質的な時間量が必要とされている。ユーザは、彼らの予測のシナリオを変更するときに、長時間にわたって結果を待つことを好まない。したがって、この工程時間を短くしようとする動機が存在する。本発明がなされたのは、これらの問題および他の問題に対してである。

本発明によれば、連鎖計算を扱うのに利用可能なときに多重プロセッサを利用する独自の能力を有するスプレッドシートプログラムは、上記の問題および他の問題を解決する。

本発明の実施形態は、スプレッドシートプログラムにおいて補助式および従属式を処理する方法を含む。それらの処理は、基本的には、まず利用可能なプロセッサの数を決定し、次いで再計算エンジンを各々の利用可能なプロセッサに割り当て、式を再計算エンジン間に分配し、次いで、スプレッドシートプログラムで再計算工程が必要とされるときに、各再計算エンジンに分配された式を同時に評価することを含む。より詳細には、例えば２つのプロセッサを有するオペレーティングコンピューティングシステム上のスプレッドシートプログラムにおいて複数の式を処理する方法は、１）第１の再計算エンジンを２つのプロセッサの一方に割り当て、第２の再計算エンジンを２つのプロセッサの他方に割り当てる処理と、２）各式を第１および第２の再計算エンジンの一方に分配する処理と、３）第１および第２の再計算エンジンの各々において、第１の式／次の式が従属式であるか否かを判断し、第１の式／次の式が従属式でない場合は、第１の式／次の式を評価し、あるいは第１の式／次の式が従属式である場合は、補助式の位置を決定する処理と、４）補助式が同じ再計算エンジンに存在する場合は、補助式を第１の式／次の式の前方に移動させ、補助式を評価する処理とを含む。補助式が同じ再計算エンジンに存在しない場合は、従属式を受け取って処理するために、補助式を含むエンジンと調整を行う。

本発明は、コンピュータプロセス、コンピューティングシステム、またはコンピュータプログラム製品のような製造品として具現化されうる。コンピュータプログラム製品は、コンピュータシステムにより読取り可能で、コンピュータプロセスを実行するための命令のコンピュータプログラムを符号化するコンピュータ記憶媒体であってもよい。コンピュータプログラム製品は、コンピューティングシステムにより読取り可能で、コンピュータプロセスを実行するための命令のコンピュータプログラムを符号化する担体上の伝搬信号であってもよい。

以下に簡単に説明する添付の図面、本発明の現在好ましい実施形態についての以下の詳細な説明、および添付の請求項を参照することによって、本発明およびその改良型をより完璧に理解することが可能である。

次に、本発明の実施形態を示す添付の図面を参照しながら、以下に本発明をより詳しく説明する。しかし、本発明を多くの異なる形態で具現化することができ、本明細書に記載されている実施形態に限定されるものと見なすべきではない。むしろ、これらの実施形態は、開示が十分かつ完全なものとなり、本発明の範囲を当業者に十分に伝えるように提示される。

概して、本発明は、スプレッドシート再計算を処理することに関し、特に、２つ以上のプロセッサまたは処理エンジンが利用可能であるときに、多重同時スレッドで連鎖計算を処理することに関する。次に図１を参照すると、スプレッドシートプログラムに使用される機能的構成要素モジュールが、本発明の一実施形態に従って論理的に示されている。基本的には、システム１００は、各々が、その上で動作する再計算エンジン１０４と、データベース１０６と、データベース１０６とデータを送受信するとともに、ロード制御モジュール１１０と通信するように動作可能な入出力すなわち送受信モジュール１０８とを有する、オペレーティングシステムにおけるＮ個の利用可能なプロセッサを含む処理モジュール１０２を備える。ロード制御モジュール１１０は、再計算命令が送受信モジュール１０８から受け取られた場合に再計算しなければならないダーティセルの範囲および領域を決定する境界検知モジュール１１２と通信する。

図２および図３は、第１に示されるシステム１００によって実施される基本的処理を示す図である。まず、本発明によるスプレッドシートアプリケーションが最初にロードされるか、または呼び出されるときに、処理の初期化シーケンス２００が実施される。シーケンス２００は、プログラムが例えばコンピュータシステム４１０上に最初にロードされるときにロードアプリケーション処理２０２において開始する。この処理は、プログラム処理に対する初期情報を設定する。次いで、操作が処理２０４に移行する。処理２０４では、コンピュータシステム４１０における利用可能なプロセッサの数が決定される。これらは、以下に記載するコンピュータシステム４１０における環境に応じて、個別のプロセッサであってもよいし、単一のチップ上の埋め込まれたコプロセッサであってもよい。次いで、操作が処理２０６に移行する。

処理２０６では、利用可能プロセッサおよびそれらのアクセス位置の数が、後の繰り返しおよび使用に向けてデータベース１０６に記憶される。次いで、操作が処理２０８に戻って、特定のスプレッドシートのローディングおよび処理に関するユーザ特有の命令を待つ。

システム１００上で実行される任意のスプレッドシートにおいて、スプレッドシート内の連鎖計算を処理するための手動または自動計算または再計算要求が行われると、図３に示される処理３００が実施される。まず、処理３０２において、再計算要求が、送受信モジュール１０８によって受け取られ、データが、要求が必要とする通りにデータベース１０６から受け取られる。処理３０２は、表示されているスプレッドシートを再計算するためのユーザによる手動要求によって開始されるか、または呼出ルーチンからの要求により自動的に開始されるか、あるいはユーザが式を含むスプレッドシートのセルの値を変更するとき、またはユーザが他の式をスプレッドシートに追加するときに開始されうる。いずれの場合も、再計算要求は、処理３０２で確認される。次いで、操作が処理３０４に移行する。

処理３０４において、再計算要求の効果の領域および範囲が決定される。これは、ただ１つのセル、あるいは変化したセル内容に依存するか、またはそれを補助するセルのアレイを含むことができる。これらは、「ダーティ」セルと呼ばれる。次いで、操作が処理３０６に移行し、本発明による再計算の手法を実施する。再計算が完了すると、操作が移行して、処理３０８を戻し、処理を呼出符号またはユーザインターフェースに戻す。

本発明の実施形態による方法は、基本的には、スプレッドシートアプリケーションの起動時に利用可能なプロセッサの数を決定し、セルおよびそれらの式を利用可能なプロセッサに分配し、次いでダーティセルに対して手動または自動で再計算要求が示される毎に、ダーティ式を同時に評価して、ダーティセルを「クリーン」にする。

本発明の実施形態によれば、本明細書に記載されている方法を単一の独立型コンピュータシステム上で実施してもよいが、典型的には、分散型コンピュータネットワークを形成するように相互接続された多重コンピュータシステム上で実施してもよい。本発明によって想定されるようにスプレッドシート計算を実施するための環境４００を図４に示す。環境４００は、一時的なコンピュータシステムと見なされるコンピュータシステム４１０を有する。本明細書に用いられる「コンピュータシステム」は、広義に捉えられるべきで、「テキスト、図形、符号、音声、ビデオおよび／または数字の表示および操作を行うためのプログラムを実行する１つまたは複数の装置または機械」と定義される。

本発明は、他の多くの汎用または特殊用途のコンピューティングシステム環境または構成で動作可能である。本発明との使用に好適でありうる、よく知られているコンピューティングシステム、環境および／または構成としては、パーソナルコンピュータ、サーバコンピュータ、手持型または卓上用装置、タブレット装置、多重プロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な大衆消費電子製品、ネットワークＰＣ、ミニコンピュータ、大型コンピュータ、および上記システムまたは装置の分散型コンピューティング環境等が挙げられるが、それらに限定されない。

コンピュータによって実行されるプログラムモジュールのようなコンピュータ実行可能命令の広い脈絡のなかで本発明を説明することができる。一般に、プログラムモジュールは、特定の作業を実施し、または特定の抽象データ型を具現化するルーチン、プログラム、オブジェクト、構成要素およびデータ構造等を含むことができる。作業が、通信ネットワークを通じて連結される遠隔処理装置によって実施される分散型コンピューティング環境においても本発明を実践することができる。分散型コンピューティング環境では、メモリ記憶装置を含むローカルまたは遠隔コンピュータ記憶媒体にプログラムモジュールを配置することができる。

図４を参照すると、本発明を具現化するための例示的なシステムは、コンピュータ４１０の形態の汎用コンピューティング装置を含む。コンピュータ４１０の構成要素としては、処理装置４２０、システムメモリ４３０、システムメモリを含む様々なシステム構成要素を処理装置４２０に結合するシステムバス４２１を挙げることができるが、それらに限定されない。システムバス４２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々な構成のいずれかを使用するローカルバスを含むいくつかの種類のバス構造のいずれかであってもよい。限定ではなく、例として、そのような構成としては、ＩＳＡ（Ｉｎｄｕｓｔｒｙ Ｓｔａｎｄａｒｄ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄａｒｄｓ Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、ＡＧＰ（Ａｃｃｅｌｅｒａｔｅｄ Ｇｒａｐｈｉｃｓ Ｐｏｒｔ）バス、およびメザニンバスとしても知られているＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスが挙げられる。

コンピュータ４１０は、典型的には、様々なコンピュータ読取り可能媒体を含む。コンピュータ読取り可能媒体は、コンピュータ４１０によってアクセスできる任意の利用可能な媒体とすることができ、揮発性および不揮発性媒体、取外し可能および取外し不可能媒体を含む。限定ではなく、例として、コンピュータ読取り可能媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュールまたは他のデータのような情報を記憶するための任意の方法または技術で実装される揮発性および不揮発性媒体を含む。コンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他のディスク記憶機構、磁気カセット、磁気テープ、磁気ディスク記憶機構または他の磁気記憶装置、あるいは所望の情報を記憶するのに使用でき、コンピュータ４１０によってアクセスできる任意の他の媒体が挙げられるが、それらに限定されない。通信媒体は、典型的には、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または搬送波または他の輸送機構のような変調データ信号における他のデータを具体化し、任意の情報配信媒体を含む。「変調データ信号」という用語は、その特性の１つ以上を、信号内の情報を符号化するように設定または変更する信号を意味する。限定ではなく、例として、通信媒体としては、有線ネットワークまたは直接有線接続のような有線媒体、ならびに音響、ＲＦ、赤外および他の無線媒体のような無線媒体が挙げられる。上記のいずれかの組合せもコンピュータ読取り可能媒体内に含まれるべきである。

システムメモリ４３０は、読取り専用メモリ（ＲＯＭ）４３１およびランダムアクセスメモリ（ＲＡＭ）４３２のような揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。典型的には、起動時のようにコンピュータ４１０内の要素間で情報を転送するのに役立つ基本ルーチンを含む基本入出力システム４３３（ＢＩＯＳ）が、ＲＯＭ４３１に記憶される。ＲＡＭ４３２は、典型的には、処理装置４２０によりすぐにアクセス可能で、かつ／または現在処理されているデータおよび／またはプログラムモジュールを含む。限定ではなく、例として、図４は、オペレーティングシステム４３４、アプリケーションプログラム４３５、他のプログラムモジュール４３６およびプログラムデータ４３７を示す図である。

コンピュータ４１０は、他の取外し可能／取外し不可能、揮発性／不揮発性記憶媒体を含むこともできる。例示のみを目的として、図４は、取外し不可能な不揮発性磁気媒体に対して読取りまたは書込みを行うハードディスクドライブ４４１、取外し可能な不揮発性磁気ディスク４５２に対して読取り書込みを行う磁気ディスクドライブ４５１、ＣＤ ＲＯＭまたは他の光媒体のような取外し可能な不揮発性光ディスク４５６に対して読取りまたは書込みを行う光ディスクドライブ４５５を示す図である。例示的な動作環境で使用できる他の取外し可能／取外し不可能な揮発性／不揮発性コンピュータ記憶媒体としては、磁気テープカセット、フラッシュメモリカード、デジタルビデオディスク、デジタルビデオテープ、固体ＲＡＭおよび固体ＲＯＭ等が挙げられるが、それらに限定されない。ハードディスクドライブ４４１は、典型的には、インターフェース４４０のような取外し不可能メモリインターフェースを通じてシステムバス４２１に接続され、磁気ディスクドライブ４５１および光ディスクドライブ４５５は、典型的には、インターフェース４５０のような取外し可能メモリインターフェースによってシステムバス４２１に接続される。

上述し、図４に例示したドライブおよびそれぞれの関連コンピュータ記憶媒体は、コンピュータ読取り可能命令、データ構造、プログラムモジュール、およびコンピュータ４１０のための他のデータを記憶する。例えば、図４では、オペレーティングシステム４４４、アプリケーションプログラム４４５、他のプログラムモジュール４４６およびプログラムデータ４４７の記憶としてハードディスクドライブ４４１が示されている。これらの構成要素は、オペレーティングシステム４３４、アプリケーションプログラム４３５、他のプログラムモジュール４３６、およびプログラムデータ４３７と同じ、または異なるものとすることができることに留意されたい。ここでは、オペレーティングシステム４４４、アプリケーションプログラム４４５、他のプログラムモジュール４４６、およびプログラムデータ４４７に異なる番号を割り当てて、最低限、それらが異なるコピーであることを示している。ユーザは、タブレット（電子デジタイザ）４６４、マイクロフォン４６３、キーボード４６２、および一般にはマウスと称するポインティングデバイス４６１、トラックボールまたはタッチパッドを通じて指令および情報をコンピュータ４１０に入力することができる。他の入力装置（不図示）は、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ等を含むことができる。これらおよび他の入力装置は、システムバスに結合されるユーザ入力インターフェース４６０を通じて処理装置４２０にしばしば接続されるが、他のインターフェース、および並列ポート、ゲームポートまたはユニバーサルシリアルバス（ＵＳＢ）のようなバス構造によって接続されてもよい。モニタ４９１または他の種類の表示装置も、ビデオインターフェース４９０のようなインターフェースを介してシステムバス４２１に接続される。モニタ４９１は、タッチスクリーンインターフェース４９２のようなインターフェースを介してコンピュータシステム４１０に手書きのようなデジタル化入力を入力することができるタッチスクリーンパネル４９３等と一体化されてもよい。モニタおよび／またはタッチスクリーンパネルを、タブレット型パーソナルコンピュータのようにコンピューティング装置４１０が組み込まれる筐体に物理的に結合することができ、タッチスクリーンパネル４９３は、基本的にタブレット４６４として機能することに留意されたい。加えて、コンピューティング装置４１０のようなコンピュータは、出力周辺インターフェース４９４等を通じて接続されうるスピーカ４９５およびプリンタ４９６のような他の周辺出力装置を含むこともできる。

コンピュータ４１０は、リモートコンピュータ４８０のような１つまたは複数のリモートコンピュータへの論理接続を用いたネットワーク化環境で動作することができる。リモートコンピュータ４８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、同位装置または他の共通ネットワークノードであってもよく、典型的には、コンピュータ４１０に対して上述した要素の多くまたは全てを含むが、図４にはメモリ記憶装置４８１のみが示されている。図４に示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）４７１および高域エリアネットワーク（ＷＡＮ）４７３を含むが、他のネットワークを含むこともできる。そのようなネットワーキング環境は、オフィス、企業内コンピュータネットワーク、イントラネットおよびインターネットに多く見られる。

ＬＡＮネットワーキング環境に使用されるときは、コンピュータ４１０は、ネットワークインターフェースまたはアダプタ４７０を通じてＬＡＮ４７１に接続される。ＷＡＮネットワーキング環境で使用されるときは、コンピュータ４１０は、典型的には、モデム４７２、またはインターネットのようなＷＡＮ４７３上に通信を確立する他の手段を含む。内部または外部に存在しうるモデム４７２を、ユーザ入力インターフェース４６０または他の適切な機構を介してシステムバス４２１に接続することができる。ネットワーク化環境において、コンピュータ４１０に対して示されるプログラムモジュール、またはその部分を遠隔メモリ記憶装置に記憶することができる。限定ではなく、例として、図４は、メモリ装置４８１に存在する遠隔アプリケーションプログラム４８５を示す図である。示されているネットワーク接続は例示的なものであり、コンピュータ間に通信リンクを確立する他の手段を使用できることが理解されるであろう。

コンピューティング環境を想定し、本発明の様々な実施形態を具体化するプロセスを実施するように実行される論理処理に関して本発明の実施形態を説明する。これらの論理処理は、（１）コンピューティングシステム上で実行されるコンピュータ実施工程またはプログラムモジュールのシーケンスとして、かつ／または（２）コンピューティングシステム内の相互接続機械論理回路または回路モジュールとして実施される。その実施は、本発明を具現化するコンピューティングシステムの性能要件に応じて選択されるものである。よって、本明細書に記載されている本発明の実施形態を構成する論理処理は、処理、構造装置、作用またはモジュールと様々に呼ばれる。これらの処理、構造装置、作用およびモジュールは、本明細書に添付されている請求項に記載されている本発明の主旨および範囲から逸脱することなく、ソフトウェア、ファームウェア、特殊用途デジタル論理、およびそれらの任意の組合せで具現化されうることを当業者なら認識するであろう。

図５は、再計算要求を受け取ったときに行われる基本的な処理５００のプロセスフロー図である。再計算は、処理５０２で開始する。操作が処理５０４に移行して、再計算要求が関係するセルに含まれるダーティ式が存在するか否かを問い合わせる。そのような式が存在しない場合は、操作が終了処理５０６に移行して、再計算要求が終了する。式を含むセルが存在する場合は、操作が処理５０８に移行して、鎖のなかの第１の式を選択する。次いで、操作が処理５０９に移行する。

問い合わせ処理５０９は、第１の式／次の式がダーティ式、すなわち再計算を必要とする処理であるか否かを尋ねる。そうでない場合は、操作が処理５０８に戻って、次の式を選択する。処理５０９における式がダーティである場合は、操作が、問い合わせ処理５０９から、式が従属式であるか否かを判断する問い合わせ処理５１０に移行する。

問い合わせ処理５１０は、第１の式／次の式が従属式、すなわち変数がそのセルに存在しない１つまたは複数の変数に従属する式であるか否かを尋ねる。そうでない場合は、操作が処理５１２に移行する。処理５１０における式が他の式、すなわち補助式である場合は、操作は、処理５１０から、補助式を取り込み、従属式の前方に配置する処理５１４に移行する。次いで、操作が問い合わせ処理５１６に移る。

問い合わせ処理５１６は、補助式を直ちに評価しようとする。この評価の一部として、処理５１６は、この補助式がそれ自体従属式であるか否かを尋ねる。そうでない場合は、操作が処理５１２に移行し、補助式を評価し、次いで従属式を評価する。次いで、操作は処理５０４に戻り、鎖において再計算すべき他の式が存在するか否かを尋ねる。

問い合わせ処理５１６において、答えが肯定的である場合は、第１の補助式がそれ自体従属式であり、操作は、次の式、すなわち第２の補助式を決定し、第１の補助式の前方に配置する処理５１４に戻る。次いで、操作が、問い合わせ処理５１６に再び移行する。ここでも、質問処理５１６は、新たな（第２の）補助式がそれ自体従属式であるか否かを尋ねる。そうである場合は、操作が再び処理５１４に戻り、次の補助式を検索し、前の補助式の前方に配置する。このプロセスは、従属式である補助式が検出されなくなるまで繰り返される。次いで、操作が問い合わせ処理５１６から処理５１２に移行し、第２の補助式を評価し、第１の補助式を評価し、処理５１２において最後に従属式を評価する。次いで、操作が処理５０４に戻り、式がなくなるまで上記のプロセスを繰り返す。次いで、処理５０６において再計算プロセスが終了する。

スプレッドシートプログラムによって使用される利用可能な各再計算エンジン１０４は、上述したのと同様にして処理される計算鎖の部分を受け取って処理する。処理３０２において再計算要求が受け取られ、処理３０４において従属および／または補助式を有する変更セルの範囲および領域が決定されると、データベース１０６は、送受信モジュール１０８を介してロード制御モジュール１１０にセル情報を提供する。境界検知モジュール１１２からの入力を備え、処理のために利用可能な再計算エンジン１０４に変更セルを分配するのはロード制御モジュールの作業である。例えば、２つのプロセッサが利用可能である場合は、プロセッサ毎に１つずつの２つの再計算エンジン１０４が利用可能になる。ロード制御モジュール１１０は、鎖における式を、利用可能なプロセッサ１０２の間に好ましくは公平に分配する。どのエンジンを割り当てるかを選択する１つの方法は、各セルおよびその式を割り当てる再計算エンジン１０４を無作為に選択することである。これは、ロード制御モジュール無作為番号生成器によって、そのセルに割り当てられたエンジンに対応する各セルにフラグを添付することによって行うことができる。理論では、そのような無作為配置は、長期間のうちに各再計算エンジンへのロードを均等化することになる。あるいは、単純に数字的に再割当を分配し、すなわち第１の式を第１のエンジンに、第２の式を第２のエンジンに、第３の式を第３のエンジンにという具合に分配し、次いでプロセッサの数が底をついたときに繰り返すことができる。

本発明の場合のような多重プロセッサ環境において、再計算エンジン処理は、変数の再計算を処理する個別の並列スレッドを構成する。再計算エンジン内のセルのローディングは好ましくは無作為であるため、各スレッドへのロードは、無作為配置の結果として、一般には均衡化する。ロード制御モジュールは、また、いくつかの再計算エンジンのローディングを監視し、各エンジン間にセルを再度割り当てることができる。あるいは、ロード制御モジュールをユーザの要望に応じて、または特定の鎖の演算要件を均衡化するために自動的に１つのエンジンまたは他のエンジンに偏らせることが可能である。

並列プロセッサ処理による式および式内のデータの操作は、結果を無効にする意図せぬ結果を招く可能性がある。例えば、２つの異なるスレッドが、個々のセルへのアクセスを競い、または共通セルに記憶されたデータを変化させるおそれがある。この理由により、本発明の実施形態では、そのような意図せぬ結果を防ぐために、様々な再計算エンジンによって行われるあらゆるデータ操作に適応する一連の規則が設けられている。

以下のソフトウェア規則は、利用可能な再計算エンジンの各々によって行われる評価方法に適応する。本明細書において以下にさらに説明する例では、２つの再計算エンジンが利用されるが、それらの規則の処理を例示するための例として示されるにすぎない。

これらの一般的規則を以下に列記する。

１．オーナ再計算エンジンしか、その再計算鎖における項目（式およびそれらの配置）を修正することができない。

２．オーナ再計算エンジンおよび他の再計算エンジンは、再計算エンジン余剰鎖上の項目を修正することができる。

３．ロッキングは、いずれかの余剰鎖上の項目の同時修正を防ぐ。例えば、再計算エンジン１が、式を再計算エンジン２に移動させたい場合は、まず再計算エンジン２の余剰鎖に対するロックを要求しなければならない。

４．一度ロックを有すると、セルの「余剰」値をＴＲＵＥに設定し、再計算エンジン１からのセルのエンジン値を再計算エンジン２に設定し、式を他のエンジン、すなわち再計算エンジン２に移動し、ロックを解除する。

５．その間、再計算エンジン２は、それ自身の再計算エンジン余剰鎖からセル式を引き抜こうとしてもよい。しかし、その再計算エンジン余剰鎖がロックされている場合は、そのような移動の前にロック解除されるまで待たなければならない。

図６は、本発明の例示的な実施形態における各再計算エンジンによって行われる処理の詳細流れ図６００である。個々の処理のシーケンスが変更されうることを理解すべきである。以下の説明は、一実施形態の説明にすぎない。当業者に容易に理解されるようなそのようなすべての説明が本明細書に組み込まれている。

処理６０２において処理が開始する。ここで、各再計算エンジン１０４が開始され、式の受取りが開始する。ロード制御モジュール１１０が、再計算処理のための式がすべて分配されたことを再計算エンジンに知らせると、操作が処理６０４に移行する。

処理６０４では、再計算エンジン１０４における第１の式が標示されて、評価される。操作は、式が従属式であるか否かを尋ねる問い合わせ処理６０５に移行する。単に一定の、または既に求められた変数が式のなかに存在するか、または参照される場合は、操作が処理６２６に移行し、式が単純に評価され、次いで再計算エンジンにおける鎖のなかのすべての式が評価されるまでシーケンスにおける次の式が同様にして評価される。しかし、遭遇した式のいずれか１つが従属式である場合、すなわち補助式と呼ばれる他のダーティ式を参照する場合は、評価が停止し、操作が問い合わせ処理６０６に移行する。

問い合わせ処理６０６は、補助式が同じ再計算エンジン上に位置するか、他の再計算エンジン上に位置するかを尋ねる。調査対象の従属式における補助式が同じ再計算エンジン上にあることが確認された場合は、操作が問い合わせ処理６０８に移行する。調査対象の従属式における補助式が同じ再計算エンジン上にない場合は、操作が処理６１０に移行する。

処理６１０では、補助式が存在する再計算エンジンにロック要求が送られ、ロックが確立されると、操作が問い合わせ処理６１２に移行する。問い合わせ処理６１２は、補助式を含む再計算エンジンが現在その計算を処理しているか、完了したかを判断する。補助再計算エンジンがアイドル状態で、ロック要求を受け取る前にその計算を完了し、ロックを処理６１０に発した場合は、ロックが解除され、操作が処理６０４に戻って、従属式の評価を再度試みる。一方、補助再計算エンジンが計算でビジー状態にあるときは、問い合わせ処理６１２に対する答えは否定的であり、操作が処理６１６に移行する。

処理６１６では、従属式が再計算エンジンから移動され、補助再計算エンジンの通常の計算鎖に付加された余剰鎖に配置される。次いで、操作が処理６１８に移行し、補助再計算エンジンにおけるロックを解除する。次いで、操作が問い合わせ処理６２０に移行する。

問い合わせ処理６２０では、最初の再計算エンジンが、その通常の計算セルに、評価を必要とするさらなる式を有するか否かについての質問が行われる。答えが肯定的である場合は、操作が処理６０４に移行し、通常の計算鎖における次の式を調査し、評価する。一方、最初の再計算エンジンの通常の鎖に評価すべき式が存在しない場合は、図７に示される最初の再計算エンジンの余剰鎖の評価を行うために、操作がルーチン７００に移行する。したがって、操作が処理７０２に移行して、再計算エンジン独自の余剰鎖のためにロックを要求し、取得することになる。これにより、ロックが活動状態である間は、再計算エンジン独自の余剰鎖における値または式が修正されることはない。ロックが取得されると、操作が問い合わせ処理７０４に移行する。

問い合わせ処理７０４では、余剰鎖上に何らかの式が存在するか否かを問い合わせる。余剰鎖上に式が存在する場合は、操作が処理７０６に移行する。処理７０６は、再計算エンジンの余剰鎖からすべての式を除去し、エンジンの通常鎖の上のシーケンスに配置する。次いで、操作が処理７０８に移行し、セルフロックを解除する。次いで、操作が処理７１０に移る。

処理７１０では、現在通常鎖の上にある式に対して、６０４から再計算が再開される。式の評価は、余剰鎖から採取された第１の式から始まり、上述のようにすべての式が評価されるまで、通常鎖の上のすべての式にわたって順次進められる。

問い合わせ処理７０４における答えが否定的である場合は、エンジンの余剰鎖上の式が存在せず、次いで操作が処理７１４に移行する。ここで、再計算エンジンは、それ自体に計算済の標識を貼り、操作を処理７１６に移行させて、再計算エンジンのセルフロックを解除する。次いで、操作は、この再計算エンジンについて計算および評価が完了している状態を提示する処理７１２に移行する。すべての再計算エンジンが、計算および評価が完了していることを提示すると、全体としての再計算が完了する。

問い合わせ処理６０６に戻って、再計算エンジンにおける第１の式が補助式を有し、補助式が実際に同じ再計算エンジンに存在すると判断される場合は、制御が問い合わせ処理６０８に移行する。問い合わせ処理６０８において、この補助式が、再計算エンジンにおける通常の、すなわち通常の鎖の上に存在するか否かという質問を行い、そこに存在しない場合は、再計算エンジンの余剰鎖上に存在することになる。補助式が、再計算エンジンの通常の鎖の上にある場合は、操作が処理６２２に移る。ここで、補助式は、鎖におけるその位置から従属式の直前まで単純に移動され、直ちに評価される。次いで、操作が問い合わせ処理６２４に移る。

問い合わせ処理６２４では、まずこの補助式を調査して、それ自体が従属式であるか否かを判断する。従属式である場合は、操作が問い合わせ処理６０６に戻って、この補助式に対して補助式を調査する。先述のように、処理６０６から処理の流れが続く。

一方、問い合わせ処理６２４における答えが否定的である場合は、補助式は従属式ではなく、操作が処理６２６に移行して、式をそのまま評価する。処理６２６における評価に続いて、操作は、再計算エンジンの通常鎖上にさらなる式が存在するか否かを尋ねる問い合わせ処理６２０に再び移る。通常鎖上に残留する式が存在しない場合は、上述のように操作が処理ルーチン７００に移る。再計算エンジンの通常鎖上にさらなる式が存在する場合は、操作が処理６０４に戻って、通常鎖における次の式を評価する。

問い合わせ処理６０８における答えが否定的である場合は、補助式は再計算エンジンの通常鎖上に存在せず、エンジンの余剰鎖の上に存在するはずである。したがって、操作は処理６２８に移り、セルフロック要求を発行する。セルフロックが確立されると、操作は処理６３０に移る。処理６３０において、補助式が、余剰鎖から除去される。次いで、操作が処理６３２に移行する。処理６３２では、除去された補助式が、再計算エンジンの通常鎖の呼出従属式の直前に配置される。次いで、操作が処理６３４に移行する。処理６３４では、セルフロックが解除され、操作が上述の問い合わせ処理６２４に移行する。

このプロセスが、図８に示される単純な３×３スプレッドシート８００上で、どのようにして実行されるかについてのいくつかの例を図９から図１４に示す。

図９および図１０は、図８に示される例示的なスプレッドシート８００の式を上述の本発明の方法に従って処理する第１の例を示す図である。図１１および図１２は、図８に示される式の異なるローディングによる同じ方法の第２の例を示す図である。図１３および図１４は、図８に示される同じ式の他の異なるローディングの第３の例を示す図である。

図９は、任意の式の評価の前の時点での図８のスプレッドシートにおける式の無作為分散ローディングの結果として、２つのプロセッサによりシステム９００上で動作するスプレッドプログラムにおける、２つのエンジン、すなわちそれぞれエンジン９０２および９０４として示される再計算エンジン１および２への式の例示的なローディングを示す図である。各エンジン９０２および９０４は、この時点では、式の通常鎖および空の余剰鎖を有する。再計算エンジン１は、セルＡ１、Ｂ１およびＢ２の式を保持する。セルＡ２、Ａ３およびＣ２における定数は再計算エンジン１にロードされず、処理時に再計算エンジン１および２から評価用に利用可能である。再計算エンジン２は、この時点では、セルＢ３、Ｃ１およびＣ３の式を保持する。

示されるように、各エンジンにおける各項目またはセル式は、左側から評価され、図９および図１０における右側に進む。さらに、評価は、各エンジン内で、独立的に、同時に、順次行われる。

まず、再計算エンジン１は、項目Ａ１、すなわち式＝４＊Ｂ３を評価しようとする。しかし、セルＢ３における式は、再計算エンジン１に存在せず、まだ評価されていない。Ｂ３は再計算エンジン２に存在するため、再計算エンジン１は、エンジン２の余剰鎖上のロックを取得し、項目Ａ１は、再計算エンジン２の余剰鎖に移動される。これは、この移動を示す矢印９０６によって図１０に示されている。次いで、ロックが解除される。次いで、エンジン１における操作が移行して、次の項目、すなわちセルＢ１を評価する。セルＢ１は、式「＝Ａ１＊Ｃ３」を含む。項目Ａ１は、評価されておらず、再計算エンジン２に残留している。よって、再計算エンジン２の余剰鎖に対してロック要求が再び発行され、それが受け取られてロックが確立されると、項目Ｂ１が、再計算エンジン２の余剰鎖に移動され、項目Ａ１の後に配置される。これは、図１０の矢印９０８によって示されている。

次いで、エンジン１における操作が移行して、次の項目、すなわちセルＢ２を評価する。セルＢ２は、式「＝３＊Ｂ１」を含む。項目Ｂ１は、評価されておらず、再計算エンジン２に残留している。よって、再計算エンジン２の余剰鎖に対してロック要求が再び発行され、それが受け取られてロックが確立されると、項目Ｂ１が、再計算エンジン２の余剰鎖に移動され、項目Ｂ１の後に配置される。これは、図１０の矢印９１０によって示されている。

再計算エンジン１における上述の処理の第１の処理と同時に、再計算エンジン２は、項目Ｂ３、すなわち式「＝Ａ３＊４」の評価を開始する。項目Ｂ３は、定数２であるため、従属式ではないＡ３を含む。よって、計算が直ちに完了され、エンジン２は、Ｃ１における式の評価に進む。セルＣ１は、式「＝Ａ１＋Ｂ１＋Ｃ２」を含む。この式は従属式である。したがって、エンジン２は、Ａ１の補助式が位置する場所を判断する。それは、エンジン２の余剰鎖上に存在する。したがって、セルフロック要求が発行され、それが確立されると、式は、余剰鎖から、矢印９１２によって示されるセルＣ１における式の直前のプロセス位置まで移動される。セルＡ１の式がエンジン２の余剰鎖上に存在しないため、その中間位置は、長方形の点線によって示される。次いで、エンジン２は式＝４＊Ｂ３を評価し、次いで式＝Ａ１＋Ｂ１＋Ｃ２に戻る。エンジン２は、セルＢ１における式で停止する。この式は、再計算エンジン２の余剰鎖上に見られる補助式である。したがって、セルフロック要求が再び発行され、それが確立されると、式＝Ａ１＊Ｃ３は、矢印９１４に示されるように、セルＣ１における式の前の通常鎖に移動する。エンジン２は、Ｂ１における式を評価し、Ａ１は計算されたが、Ｃ３は、計算を必要とする補助式であることを確認する。したがって、セルフロック要求が発行され、それが確立されると、Ｃ３における式は、Ｂ１の直前の通常鎖に移動される。ここで、エンジン２は、Ｃ３における式を評価する。したがって、Ｃ３における式が直ちに計算される。次に、ここでＡ１およびＣ３が計算されるため、エンジン２はＢ１における式を直ちに計算する。ここで、式＝Ａ１＋Ｂ１＋Ｃ２のすべての要素が把握され、セルＣ１における式が評価される。これによって、再計算エンジン２における通常鎖の処理が完了する。

次いで、エンジン２は移動して、その余剰鎖を調べる。余剰鎖は、１つの式、すなわちセルＢ２における＝３＊Ｂ１を含む。再計算２の鎖にセルフロックが確立され、この式が、余剰鎖から、再計算エンジン２における通常鎖に移動される。通常鎖への移動を示す矢印は、複雑な図を複雑にするだけであるため、示されていない。セルＢ１における式がここで計算され、把握されるため、セルＢ１における式を直ちに評価し、計算を完了する。エンジン２は、その通常および余剰鎖に計算を有しないことを確認し、自らを完了の状態に設定する。

エンジン１は、その通常および余剰鎖に計算を有しないことを確認し、自らを完了の状態に設定する。これにより、エンジン１および２における処理が完了する。

図１１および図１２は、任意の式の評価の前の時点での図８のスプレッドシートにおける式の異なる無作為分散ローディングの結果として、システム１１００のプロセッサ１１０２および１１０４での処理における、再計算エンジン１および２への式の異なる例示的なローディングが生じる第２の例を示す図である。再計算エンジン１は、セルＡ１、Ｃ１およびＣ３の式を保持する。セルＡ２、Ａ３およびＣ２における定数は、ここでも再計算エンジン１にロードされず、処理時に再計算エンジン１および２から評価のために利用可能である。再計算エンジン２は、セルＢ１、Ｂ３およびＢ２の式を同時に保持する。

示されるように、各エンジンにおける各項目またはセル式が左側から評価され、図１１および図１２において右側に進行する。さらに、評価は、各エンジン内で同時に、かつ順次行われる。

まず、再計算エンジン１は、項目Ａ１、すなわち式＝「４＊Ｂ３」を評価しようとする。しかし、セルＢ３における式は、再計算エンジン１に存在せず、まだ評価されていない。セルＢ３の式は再計算エンジン２に存在するため、再計算エンジン１は、エンジン２の余剰鎖上のロックを取得し、項目Ａ１は、矢印１２０２によって示されるように、再計算エンジン２の余剰鎖に移動される。ロックが解除される。次いで、エンジン１における操作が移行して、次の項目、すなわちセルＣ１の式を評価する。セルＣ１は、式＝Ａ１＋Ｂ１＋Ｃ２を含む。項目Ａ１は評価されておらず、ここで再計算エンジン２に残留している。よって、再計算エンジン２の余剰鎖に対してロック要求が再び発行され、それが受け取られると、矢印１２０４で示されるように、項目Ｃ１が再計算エンジン２の余剰鎖に移動され、項目Ａ１の後に配置される。

再計算エンジン１における上記処理の第１の処理と同時に、再計算エンジン２は、項目Ｂ１、すなわち式＝Ａ１＊Ｃ３を評価しようとする。しかし、項目Ｂ１はＡ１を含む。次いで、ソフトウェアは、Ａ１が再計算エンジン２に存在するか、再計算エンジン１に存在するかを判断する。それらのエンジンは並行して動作するため、Ａ１はこの時点では再計算エンジン１に存在する可能性が高い。したがって、項目Ｂ１は、矢印１２０６によって示されるように、再計算エンジン１の余剰鎖上のロックを最初に取得した後で、再計算エンジン１における余剰鎖に移動される。移動すると、ロックが解除される。次いで、再計算エンジン２における操作が移行して、セルＢ３の式を評価する。セルＢ３は、式＝Ａ３＊４を有する。セルＡ３は定数２を含むため、セルＢ３の式は従属式ではなく、直ちに「８」と評価され、次いで操作が移行して、セルＢ２の式を評価する。これと同時に、セルＣ１の式が再計算エンジン１から再計算エンジン２の余剰鎖に移されている可能性が高い。セルＢ２の式は「＝３＊Ｂ１」である。セルＢ１の式は、再計算エンジン１の余剰鎖に移された。その結果として、ここでセルＢ２は、矢印１２０８によって示されるように、再計算エンジン１における余剰鎖に移される。

次いで、再計算エンジン２は、自らをロックし、現在余剰鎖上にあるすべての式を、処理に向けてその通常鎖に移動させる（簡潔にするために、図１２に示していない）。ここで、計算すべき次の式はＡ１（＝４＊Ｂ３）に存在する。Ｂ３は、既に「８」と評価されたため、「クリーン」にされている。したがって、項目Ａ１は、直ちに評価され、「３２」になる。

再計算エンジン２がＢ３を計算するのと同時に、再計算エンジン１はセルＣ３の式を評価している。この従属式は、＝Ｂ３＊Ａ３である。Ｂ３は補助式である。Ｂ３の評価を既に完了できるため、式をすぐに評価できる可能性がある。しかし、そうでない場合は、セルＣ３の式は、点線の矢印１２１０で示されるように、再計算エンジン２の余剰鎖に移されることになる。そのような移送は、２つのエンジンの間で必要とされる処理時間に全面的に依存することを読者は理解すべきである。

再計算エンジン２について継続すると、項目Ｂ３が計算され、項目Ａ１が計算されたため、次の式Ｃ１の評価が試みられる。セルＣ１の式は従属式で、補助式Ｂ１、定数Ｃ２および評価項目Ａ１に依存する。ここで、項目Ｂ１は再計算エンジン１の余剰鎖に存在する。再計算エンジン１において、余剰鎖に存在するセルＢ１およびＢ２の２つの式は、ここで通常鎖に移動され、計算が開始されている可能性が高い（簡潔にするために、図示していない）。セルＢ１の式が計算された場合は、セルＣ１の式が直ちに計算される。そうでない場合は、エンジン１の余剰鎖に対してロックが要求され、セルＣ１の式は、再計算エンジン１の余剰鎖に戻って、処理を待つことになる。この処理は、簡潔にするため、矢印で示されていない。次いで、再び、エンジン２における操作が進行して、セルＣ３の式を評価する。Ｂ３はこの時点で計算されており、Ａ３は定数であるため、セルＣ３の式が直ちに計算される。エンジン２は、その通常鎖および余剰鎖に計算を有さないことを確認し、自らを完了の状態に設定する。これにより、再計算エンジン２における処理が完了する。

最後に、再び再計算エンジン１では、セルフロックが要求され、余剰鎖の式が通常鎖に移動され、ロックが解除され、式が評価される。セルＡ１の式が求められ、Ｃ３の式が求められたため、セルＢ１の式、＝Ａ１＊Ｃ３が直ちに計算される。操作がセルＢ２の式に移る。セルＢ１の値が既に求められているため、セルＢ２の式の値が直ちに計算される。エンジン１は、その通常鎖および余剰鎖に計算を有さないことを確認し、自らを完了の状態に設定する。これにより、再計算鎖１における処理が完了する。これにより、本例における処理が完了する。

図１３および図１４は、上述の本発明の方法に従って、図８に示される例示的なスプレッドシートの式を処理する第３の例を示す図である。図１３は、任意の式の評価の前の時点での図８のスプレッドシートにおける式の無作為分散ローディングの結果としての再計算エンジン１および２への式の例示的なローディング１３００を示す図である。プロセッサ１３０２上の再計算エンジン１は、セルＡ１、Ｃ１、Ｂ２およびＣ３の式を保持する。セルＡ２、Ａ３およびＣ２の定数は再計算エンジン１にロードされず、処理時に再計算エンジン１および２から評価のために利用可能である。再計算エンジン２は、この時点でプロセッサ１３０４上のセルＢ１およびＢ３の式を保持する。

示されるように、各エンジンにおける各項目またはセル式が左側から評価され、図１３および図１４において右側に進行する。さらに、評価は、各エンジン内で同時に、かつ順次行われる。

まず、再計算エンジン１は、項目Ａ１、すなわち式＝４＊Ｂ３を評価しようとする。しかし、セルＢ３は再計算エンジン１に存在せず、まだ評価されていない。セルＢ３の式は再計算エンジン２に存在するため、再計算エンジン１は、エンジン２の余剰鎖上のロックを取得し、項目Ａ１は、矢印１４０２で示されるように、再計算エンジン２の余剰鎖に移動される。ロックが解除される。次いで、操作が移行して、次の項目、すなわちセルＣ１を評価する。セルＣ１は、式＝Ａ１＋Ｂ１＋Ｃ２を含む。項目Ａ１は評価されておらず、ここで再計算エンジン２に存在する。よって、再計算エンジン２の余剰鎖に対してロック要求が再び発行され、それが受け取られると、矢印１４０４で示されるように、項目Ｃ１が再計算エンジン２の余剰鎖に移動され、項目Ａ１の後に配置される。

再計算エンジン１における上記の処理の第１の処理と同時に、再計算エンジン２は、項目Ｂ１、すなわち式＝Ａ１＊Ｃ３を評価しようとする。しかし、項目Ｂ１はＡ１を含む。次いで、ソフトウェアは、Ａ１が再計算エンジン２に存在するか、再計算エンジン１に存在するかを判断する。それらのエンジンは並行して動作するため、Ａ１は、この時点ではまだ再計算エンジン１に存在するものと想定されうる。したがって、項目Ｂ１は、矢印１４０６で示されるように、再計算エンジン１の余剰鎖上のロックを取得した後で再計算エンジン１における余剰鎖に移動される。移動すると、ロックが解除される。次いで、再計算エンジン２における操作が移行して、項目Ｂ３を評価する。項目Ｂ３は、式＝Ａ３＊４を有する。セルＡ３は定数２を含むため、セルＢ３の式が直ちに評価され、再計算エンジン２における通常鎖でのさらなる活動は行われない。これと同時に、項目Ｃ１は、再計算エンジン１から再計算エンジン２の余剰鎖に移されている可能性が高い。

再計算エンジン２は、その通常鎖におけるすべての処理を完了した。よって、次いで余剰鎖式を通常鎖に引き込み、評価を開始する（簡潔にするため、図１４に示さない）。次いで、再計算エンジン２は、第１の式、セルＡ１の評価を開始する。セルＡ１の式は、＝４＊Ｂ３である。Ｂ３は、評価され、ここでは「８」であるため、「クリーン」になる。したがって、項目Ａ１が直ちに評価され、クリーンの「３２」になる。

再計算エンジン２がＢ３を計算するのと同時に、再計算エンジン１は、セルＢ２の式を評価している。この従属式は、＝３＊Ｂ１である。Ｂ１は補助式である。次いで、プログラムは、セルＢ１の式がその余剰鎖におけるそれ自体の再計算エンジン１上に存在すると判断し、セルフロックを確立し、セルＢ１の式を、矢印１４０８で示されるようにセルＢ２の直前の位置に移動し、セルＢ１の式を評価しようとする。セルＢ１の式は、＝Ａ１＊Ｃ３である。この時点で、項目Ａ１は再計算エンジン２の余剰鎖上に存在し、Ａ１は計算されていないと想定する。したがって、再計算エンジン１は、再計算エンジン２の余剰鎖上のロックを取得し、セルＢ１の式を矢印１４１０で示されるように再計算エンジン２の余剰鎖に移し、ロックを解除する。再計算エンジン１では、再びセルＢ２の式の評価が試みられるが、セルＢ２の式は従属式であり、Ｂ１は、再計算エンジン２に移された補助式である。したがって、再計算エンジン１は、ロックを取得し、矢印１４１２で示されるように、セルＢ２の式を再計算エンジン２の余剰鎖に移す。

その間、再計算エンジン２では、セルＢ３の式が計算され、セルＡ１の式が計算されたため、セルＣ１の次の式が評価される。セルＣ１の式は従属式で、セルＢ１の補助式、セルＣ２の定数、およびセルＡ１の評価式に依存する。ここでセルＢ１の式は再計算エンジン２に存在するため、矢印１４１４で示されるようにセルＣ１の式の前方に移動され、直ちに評価される。セルＢ１の式は従属式で、Ａ１およびＣ３に依存する。このとき、セルＡ１の式は評価されたが、セルＣ３の式はまだ評価されていないかも知れず、この場合は再計算エンジン１に配置される。しかし、このときまでにＣ３が評価されていない場合は、その値（１６）を用いて、セルＢ１の式が評価され、次いでセルＣ１の式が評価される。一方、Ｃ３がまだ評価されていない場合は、再計算エンジン１の余剰鎖に対するロックを要求し、ロックされると、項目Ｂ１が再び再計算エンジン１の余剰鎖に移動される（点線の矢印１４１６）。

最後に、再計算エンジン２では、セルＢ２の式の評価が試みられる。Ｂ２の式は従属式で、Ｂ１に依存する。このときまでに、セルＢ１の式が評価されている可能性が高いため、Ｂ２が評価され、再計算が完了する。再計算エンジン１では、処理は、セルＣ３の式の評価とともに、あるいはセルＢ１の式が再び再計算エンジン１の余剰鎖に移動された場合はセルＢ１の式の評価とともに既に完了している。これにより、第３の例における処理が完了する。

構造的特徴、手法的作用、およびそのような作用を含むコンピュータ読取り可能媒体に特有の言葉で本発明を説明したが、添付の請求項に定められている本発明は、記載されている具体的な構造、作用または媒体に必ずしも限定されない。例として、式の評価の処理は、実施例に示されるように左から右に行われなくてもよい。エンジン間で式を物理的に移動させる必要はない。含まれるセルにフラグを割り当て、フラグ、そして処理すべき式、または既に処理または「クリーン」にされた式を示すポインタを単に変更することによっても同じ効果を達成することができる。したがって、具体的な構造、作用または媒体は、主張する発明を具現化する好ましい形態として開示されている。

本発明の一実施形態による例示的なモジュラソフトウェアシステムを示す図である。 本発明の一実施形態によるソフトウェアが起動時に完了する初期の処理を示す図である。 スプレッドシートのセル値が修正されたときに本発明の一実施形態におけるソフトウェアで実施される包括的な処理全体の構成図である。 本発明の特定の態様に従って使用できるコンピュータシステムを示す図である。 本発明の特定の実施形態による連鎖再計算における式を評価するための基本的な処理を示す構成図である。 本発明の一実施形態による多重スレッド再計算エンジンにおける処理を示す詳細流れ図である。 図６の再計算エンジンにおける余剰鎖上の史記を処理するための処理を示す流れ図である。 いくつかの式を示す例示的な３×３スプレッドシートである。 本発明の一実施形態に従って動作する２つの再計算エンジンに最初にロードされる、図８に示されるセルを示す図である。 図９に示される再計算エンジン１および２における式の処理を示す図である。 本発明の一実施形態に従って動作する２つの再計算エンジンに最初にロードされる、図８に示されるセルを示す図である。 図１１に示される再計算エンジン１および２における式の処理を示す図である。 本発明の一実施形態に従って動作する２つの再計算エンジンに最初にロードされる、図８に示されるセルのさらなる例を示す図である。 図１３に示される再計算エンジン１および２における式の処理を示す図である。 例示的な従来のスプレッドシートである。 図１５に示されるスプレッドシートに対する計算鎖の図である。 図１５に示されるスプレッドシートに対する再順序付けされた計算鎖の図である。

符号の説明

１２、１４ 計算鎖
１００ システム
１０２ 処理モジュール
９００、１１００、１３００ システム
９０２、９０４、１１０２、１１０４、１３０２、１３０４ エンジン

Claims (26)

1. 利用可能なプロセッサの数を決定するステップと、
   利用可能なプロセッサの前記数が少なくとも２である場合、各利用可能なプロセッサに再計算エンジンを割り当てるステップと、
   前記式を前記再計算エンジンの間に分配するステップと、
   各再計算エンジンに分配された前記式を評価するステップと
   を備えたことを特徴とするスプレッドシートプログラムにおいて補助式および従属式を処理する方法。
2. 前記処理は、オペレーティングシステムによって実施されることを特徴とする請求項１に記載の方法。
3. 前記決定するステップは、プログラムが起動すると、多重プロセッサが利用可能であるか否かをコンピュータ動作システムに問い合わせるステップを含むことを特徴とする請求項１に記載の方法。
4. 前記分配するステップは、
   第１の式を選択するステップと、
   前記第１の式を前記再計算エンジンの任意の１つに無作為に割り当てるステップと、
   すべての式が前記再計算エンジンの１つに割り当てられるまで、次の式毎に前記選択および割り当て工程を繰り返すステップと
   を含むことを特徴とする請求項１に記載の方法。
5. 各再計算エンジン上での前記評価するステップは、
   第１の式を選択するステップと、
   前記第１の式が従属式か補助式かを判断するステップと、
   前記第１の式が補助式である場合は、該補助式を評価するステップと、
   前記第１の式が従属式である場合は、該従属式に対する補助式が前記再計算エンジンに存在するか否かを判断するステップと、
   前記従属式に対する前記補助式が前記計算エンジンに存在する場合は、前記補助式を前記第１の式の前に配置するステップと
   を含むことを特徴とする請求項１に記載の方法。
6. 前記第１の式の前に配置された前記補助式が従属式であるか否かを判断するステップと、
   前記補助式が従属式でない場合は、該補助式を評価するステップと、
   前記補助式が従属式である場合は、該従属式に対する他の補助式が前記再計算エンジンに存在するか否かを判断し、そうである場合は、前記他の補助式を前記補助式の前に配置し、前記他の補助式を評価するステップと
   をさらに備えたことを特徴とする請求項５に記載の方法。
7. 前記評価するステップは、
   前記第１の式が従属式であり、該従属式に対する前記補助式が前記再計算エンジンに存在しない場合は、前記補助式の前記再計算エンジン位置を決定し、前記第１の式をその再計算エンジンに移動するステップをさらに含むことを特徴とする請求項５に記載の方法。
8. 前記評価するステップは、
   前記第１の式が従属式であり、該従属式に対する前記補助式が前記再計算エンジンに存在しない場合は、前記補助式の前記再計算エンジン位置を決定し、前記補助式を有する前記再計算エンジンが計算を終了しているか否かを問い合わせ、そうである場合は、前記従属式の評価を再度試み、そうでない場合は、前記補助式を有する前記再計算エンジンに前記従属式を移動するステップをさらに含むことを特徴とする請求項５に記載の方法。
9. 前記補助式を有する前記再計算エンジンに移動された前記従属式は、その再計算エンジンにおける余剰鎖に配置されることを特徴とする請求項８に記載の方法。
10. コンピュータシステムにより読取り可能で、請求項１に記載の方法を実施するように前記コンピュータシステムにより実行可能な命令のプログラムを明確に具体化することを特徴とするコンピュータプログラム製品。
11. コンピュータシステムにより読取り可能で、請求項５に記載の方法を実施するように前記コンピュータシステムにより実行可能な命令のプログラムを明確に具体化することを特徴とするコンピュータプログラム製品。
12. ２つのプロセッサを有するオペレーティングコンピューティングシステム上でスプレッドシートプログラムにおける複数の式を処理する方法であって、
    第１の再計算エンジンを前記２つのプロセッサの一方に割り当て、第２の再計算エンジンを前記２つのプロセッサの他方に割り当てるステップと、
    各式を前記第１および第２の再計算エンジンの一方に分配するステップとを備え、
    前記第１および第２の再計算エンジンの各々において、
    第１の式／次の式が従属式であるか否かを判断し、
    前記第１の式／次の式が従属式でない場合は、前記第１の式／次の式を評価し、
    前記第１の式／次の式が従属式である場合は、補助式の位置を決定し、
    前記補助式が同じ再計算エンジンに存在する場合は、前記補助式を前記第１の式／次の式の前まで移動し、および
    前記補助式を評価することを特徴とする方法。
13. 前記再計算エンジンにおける前記次の式に対して前記判断するステップおよび評価するステップを繰り返すことをさらに備えたことを特徴とする請求項１２に記載の処理方法。
14. 前記補助式が従属式であるか否かを判断するステップと、
    前記補助式が従属式である場合は、前記補助式の位置を決定するステップとをさらに備え、
    その補助式が同じ再計算エンジンに存在する場合は、その補助式を、それが補助する前記補助式の前まで移動し、および
    その補助式を評価し、次いで、前記補助式を評価することを特徴とする請求項１２に記載の処理方法。
15. 前記第１および第２の再計算エンジンにおける次の式毎に、前記判断、評価、移動および評価工程を繰り返すステップをさらに備えたことを特徴とする請求項１４に記載の処理方法。
16. 前記補助式が同じ再計算エンジンに存在しない場合は、前記従属式を前記第１および第２の再計算エンジンの他方に移動するステップをさらに備えたことを特徴とする請求項１２に記載の処理方法。
17. 前記従属式を移動するステップは、前記従属式を前記第１および第２の再計算エンジンの他方の余剰鎖に追加するステップを含むことを特徴とする請求項１６に記載の処理方法。
18. スプレッドシートプログラムにおいて式鎖における補助式および従属式を処理するためのシステムであって、
    利用可能なプロセッサの数を決定し、再計算エンジンを各々の利用可能なプロセッサに割り当てるモジュールと、
    前記再計算エンジン間で前記式を分配するロード制御モジュールと、
    各再計算エンジンに分配された前記式を同時に評価する処理モジュールと
    を備えたことを特徴とするシステム。
19. 前記処理モジュールは、オペレーティングシステム内に存在することを特徴とする請求項１に記載のシステム。
20. 前記決定モジュールは、プログラムが起動すると、多重プロセッサが利用可能であるか否かをコンピュータオペレーティングシステムに問い合わせ、再計算エンジンを各々の利用可能なプロセッサに割り当てることを特徴とする請求項１に記載のシステム。
21. 前記ロード制御モジュールは、第１の式を選択し、前記第１の式を前記再計算エンジンの任意の１つに無作為に割り当て、すべての式が前記再計算エンジンに割り当てられるまで、次の式毎に前記選択および割り当て工程を繰り返すことを特徴とする請求項３に記載のシステム。
22. コンピュータによって実行されると、スプレッドシートプログラムにおける補助および従属式を処理する方法であって、
    利用可能なプロセッサの数を決定するステップと、
    利用可能なプロセッサの前記数が少なくとも２である場合に、各利用可能なプロセッサに再計算エンジンを割り当てるステップと、
    前記式を前記再計算エンジンの間で分配するステップと、
    各再計算エンジンに分配された前記式を評価するステップと
    を含む方法を実行するコンピュータ実行可能命令を備えたことを特徴とするコンピュータ読取り可能媒体。
23. 前記処理方法における前記決定するステップは、プログラムが起動すると、多重プロセッサが利用可能であるか否かをコンピュータ動作システムに問い合わせるステップを含むことを特徴とする請求項２２に記載のコンピュータ読取り可能媒体。
24. 前記処理方法における前記分配工程は、
    第１の式を選択するステップと、
    前記第１の式を前記再計算エンジンの任意の１つに無作為に割り当てるステップと、
    すべての式が前記再計算エンジンの１つに割り当てられるまで、次の式毎に前記選択および割り当てるステップを繰り返すステップと
    を含むことを特徴とする請求項２２に記載のコンピュータ読取り可能媒体。
25. 前記処理方法における各再計算エンジン上での前記評価するステップは、
    第１の式を決定するステップと、
    前記第１の式が従属式か補助式かを判断するステップと、
    前記第１の式が補助式である場合は、前記式を評価するステップと、
    前記第１の式が従属式である場合は、この従属式に対する補助式が前記再計算エンジンに存在するか否かを判断するステップと、
    この従属式に対する前記補助式が前記計算エンジンに存在する場合は、前記補助式を前記第１の式の前に配置するステップと
    を含むことを特徴とする請求項２２に記載のコンピュータ読取り可能媒体。
26. コンピュータによって実行されると、２つのプロセッサを有するオペレーティングコンピューティングシステム上でスプレッドシートプログラムにおける複数の式を処理する方法を実行するコンピュータ実行可能命令を含むコンピュータ読取り可能媒体であって、前記方法は、
    第１の再計算エンジンを前記２つのプロセッサの一方に割り当て、第２の再計算エンジンを前記２つのプロセッサの他方に割り当てるステップと、
    各式を前記第１および第２の再計算エンジンの一方に分配するステップとを備え、
    前記第１および第２の再計算エンジンの各々において、
    第１の式／次の式が従属式であるか否かを判断し、
    前記第１の式／次の式が従属式でない場合は、前記第１の式／次の式を評価し、
    前記第１の式／次の式が従属式である場合は、補助式の位置を決定し、
    前記補助式が同じ再計算エンジンに存在する場合は、前記補助式を前記第１の式／次の式の前まで移動し、および
    前記補助式を評価することを特徴とするコンピュータ読取り可能媒体。
    

Images