(57)【特許請求の範囲】
【請求項１】
ソフトウエアシステムにより実行される方法であって、ソフトウエアシステムが、
各々が記憶値と少なくとも一つの関連する属性値を有する一セットの記憶領域を有する手段と、
各アクションが複数の記憶領域の内の少なくとも二つに関連付けられた、複数のアクションを記憶する手段と、
一つのアクションが他の一つのアクションに優先されるべきか否かを指定する優先ポリシーである選択ルールを記憶する手段と、
を備え、
前記ソフトウェアシステムにより実行される前記方法が、
各アクションに関連付けられた前記少なくとも二つの記憶領域に対する前記関連する属性値に基づき一セットの使用可能とされたアクションを決定するステップと、
前記選択ルールに基づいて前記セットの使用可能とされたアクションから一つの使用可能とされたアクションを選択するステップと、
前記選択された使用可能とされたアクションを実行するステップと、
前記選択された使用可能とされたアクションの実行の結果に基づき前記選択された使用可能とされたアクションに関連する前記記憶領域の少なくとも一つに対する記憶値及び前記少なくとも一つの関連する属性値を更新するステップと、
新たなアクション及び記憶領域を追加するステップと、
各アクションに関連するコスト及びアクションの実行によりそのアクションに関連する記憶領域の幾つかの値を変更する変更確率を更新するステップと、
を備え、
前記コスト及び変更確率を更新するステップは、
一つのアクションに関連する更新されたコスト及び変更確率における変化が所定の基準を満足するか否かを決定するステップと、
前記変化が前記所定の基準を満足する場合、前記優先ポリシーを調節するステップと、
を含むソフトウエアシステム実行方法。
【請求項２】
前記セットの使用可能とされたアクションを決定するステップは、
前記記憶領域のうち入力データを関連する前記アクションに提供する全ての使用可能記憶領域が初期化され且つ前記記憶領域のうち関連する前記アクションから出力データを受信する全ての使用不能記憶領域が初期化されているか否か及び前記アクションに関連する少なくとも一つの使用可能記憶領域が前記アクションに関連する全ての使用不能記憶領域の属性値よりも大きい属性値を有するか否かに基づいて、前記使用可能とされたアクションを決定することを含む請求項１に記載の方法。
【請求項３】
前記属性値は一つの値を有するタイムスタンプであり、一セットの使用可能とされたアクションを決定することは、前記アクションに関連する指定された使用可能及び使用不能記憶領域の関連するタイムスタンプ値に従って使用可能とされる一つのアクションを識別することを更に含む請求項１に記載の方法。
【請求項４】
前記属性値はデータ値が前記ソフトウエアシステムへ入力されることに続いて前記記憶領域が更新されたか否かを表す演算スタンプであり、一セットの使用可能とされたアクションを決定することは、前記アクションに関連する指定された使用可能及び使用不能記憶領域の関連する演算スタンプ値に従って使用可能とされる一つのアクションを識別することを更に含む請求項１に記載の方法。
【請求項５】
依存性アクションシステムであって、
各々が記憶値と少なくとも一つの関連する属性値を有する一セットの記憶領域を有する手段と、
各アクションが複数の記憶領域の内の少なくとも二つに関連付けられた、複数のアクションを記憶する手段と、
一つのアクションが他の一つのアクションに優先されるべきか否かを指定する優先ポリシーである選択ルールを記憶する手段と、
前記選択ルールに基づき一セットの使用可能とされたアクションから一つの使用可能とされたアクションを選択する使用可能とされたアクションセレクタと、新たなアクション及び記憶領域を追加する手段と、各アクションに関連するコスト及びアクションの実行によりそのアクションに関連する記憶領域の幾つかの値を変更する変更確率を更新する手段と、を備え、
前記コスト及び変更確率を更新する前記手段は、一つのアクションに関連する更新されたコスト及び変更確率における変化が所定の基準を満足するか否かを決定するための手段と、前記変化が前記所定の基準を満足する場合、新たな優先ポリシーを決定する手段と、を含み、
一つのアクションは、そのアクションと関連付けられた前記二つの記憶領域に対する前記少なくとも一つの関連する属性値に基づき使用可能とされ、
前記選択された使用可能とされたアクションは、選択されると実行され、且つ前記選択された使用可能とされたアクションに関連する前記記憶領域の少なくとも一つに対する記憶値及びそれに関連する属性値は、前記選択された使用可能にされたアクションの実行の結果に基づき更新される依存性アクションシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複雑なソフトウエアを構築し実行するための方法及びシステムに関する。特に、本発明は、学習及びプランニング技術を使用する自己最適化ソフトウエアに関する。より詳細には、この発明は、外部からの干渉に対して耐性があり、ダイナミックな再構成を支援するソフトウエアに関する。
【０００２】
【従来の技術】
従来のソフトウエアシステムは、システムの設計者が予期しなかった問題、故障、又は環境状態に直面したときに、そのようなソフトウエアが故障するという意味において、融通がきかず、もろい傾向がある。ソフトウエア故障の理由の一部は、アルゴリズムの手順が命令で順序付けられる傾向があり、全ての起こり得る偶然性を明示的に考慮する必要があることである。即ち、もし設計において変化が予期されず考慮されなかったならば、その変化の発生によりソフトウエアシステムの故障が生ずる。例外処理メカニズム及びオブジェクト指向言語モジュールのダイナミックなディスパッチングのような幾つかの高レベル言語機能が命令の順序付けの問題をアドレスするために設計される。
【０００３】
これらの問題は、（１）システム構築手順及びダイナミックなシステム構成、（２）ソフトウエア故障に対する耐性、及び（３）形式的なシステム記述及びプログラミングのパラダイムを含む、三つの基本的技術領域に関連する。
【０００４】
システム構築手順及びダイナミックなシステム構成に対する一つのアプローチは、ネルソン  エイチ．エフ．ビード（Nelson H.F. Beede）の１９９０年２月５日のユタ州ソルトレークシティのユタ大学、科学計算及び数学部門センター、技術レポート“ユニックスメークのＧメーク及び拡張実施の設計”［‘The Design of G Make- and Extended Implementation of UNIX Make', Technical report，Center of Scientific Computing and Department of Mathematics, University of Utah, Salt Lake City，UT, February５，1990,］で論じられており、この全文が本明細書に組み込まれる。ビードは、新しいファイルを生成するツールの実行を導出するためにファイルと関連するタイムスタンプを使用するUNIX 'make'ユティリティについて論じている。ツールの実行は、そのツールの入出力のタイムスタンプにより制御される。このメカニズムは、冗長性がない。即ち、ツールが故障すると、演算、即ち、構築処理に失敗する。このUNIX 'make'ユティリティは、冗長性がないので、プランニングを通してその実行を最適化するものではない。'make'ユティリティは、学習をしないし、反復ができない。この場合、反復は、連続する反復を介して直接又は間接的に依存するターゲットを示す。
【０００５】
システム構築手順及びダイナミックなシステム構成に対する他の一つのアプローチは、再構成可能なシステムを達成することである。例えば、アレンら（Allen et al）に付与された米国特許第５、６３４、０５８号は、必要に応じてソフトウエアをダイナミックにロードする方法を述べている。この方法は、一セットの交換モジュールの内の何れのモジュールをロードすべきか決定するのではなくて単にモジュールをロードする仕組みについて扱っている。リンチら（Lynch et al）に付与された米国特許第５、５１５、５２４号に述べられたシステムは、構造的記述、要求、及び制約に基づきソフトウエア構成を指定し構築する。このシステムは、一旦構築されると、システムを実行しながらシステムの構成を変更できないという意味で、静的である。
【０００６】
ソフトウエア構成に対するよりダイナミックなアプローチは、クレーマーら（Kramer et al）の１９８５年、ソフトウエアエンジニアリングＩＥＥＥ会報、１１（４）：４２４〜４３６頁、“分散システムのためのダイナミック構成”［‘Dynamic Configuration for Distributed System' IEEE Transaction on Software Engineering, 11(4):424-436, 1985］により論じられている。このアプローチは、システムを実行しながら、システムを変更し拡張うる能力を提供する。構成における変更は、構成記述を明示的に変えることにより行われるが、所与の問題、故障、及びコスト、即ち、構成要素のランタイム、品質等に基づき自動的に行われるのではない。従って、構成の変化は、システムが問題、故障、及びシステム構成要素のコストパラメータの変更に遭遇したときに直ちに生ずるのではない。
【０００７】
他のダイナミックなシステムの再構成は、マズロら（Marzullo et al）の１９９１年８月、コンピュータ：２４(８)：３２〜５１頁、“分散アプリケーション管理のツール”［‘Tools for Distributed Application Management', Computer, 24(8):32-51, August, 1991］により提供されている。クレーマーのシステムとは対照的に、このマズロは、ダイナミックなシステム再構成を実現するメタと呼ばれるシステムについて述べている。このメタシステムは、遭遇するシステム構成要素の問題、故障、及びコストパラメータの変化に応答して、システムを実行しながら、構成を変化させる。メタは、その機能的構成要素により提供されるセンサー及びアクチュエータを介して実際のプログラムの実行を観察し、制御する別のモニター処理により達成される。モニタープログラム、センサー又はアクチュエータが必要であり、制御フローの変更は、必ずしも変更されたデータの時間順序に基づくものではない。
【０００８】
ソフトウエア故障の耐性（許容範囲）は、設計者により予期されなっかたシステムの故障及び環境状況の問題を解決するために使用される。エクハードら（Eckhardt et al）の１９９１年ソフトウエアエンジシアリングＩＥＥＥ会報：６９２〜７０２頁、“信頼性改良の戦略としてのソフトウエア冗長性の実験評価”［‘An Experimental Evaluation of Software Redundancy As a Strategy for Improving Reliability', IEEE Transaction on Software Engineering, 17(7), page 692-702，1991］に開示されたN-version 方法は、同じ仕様に対して独立で開発される複数の機能構成要素を使用することにより信頼性の高いソフトウエアシステムを生成する。この複数の機能構成要素は同じに実行され、システムは生成された結果の間で決める。この方法は、主に可能な設計及び独立的に開発された構成要素のコード化エラーを扱う。N-version 方法は、同次冗長性のみを使用する。即ち、全ての構成要素は、同じ機能を実行するよう意図される。更に、全ての代案が実行されるが、構成要素のダイナミックな選択はできず、N-versionシステムは、適応性がなく、学習もしない。
【０００９】
ソフトウエア故障に対する耐性を達成するための他のアプローチは、回復ブロック、ロールバック、及び再実行を使用するための異なるアプローチを含む。このようなアプローチは、フューチら（Fuchs et al）の米国特許第５、５３０、８０２号及び第５、４４０、７２６号に記載されている。一般にこれらの方法は、故障しているソフトウエア構成要素のロールバック及び再実行の使用を介してソフトウエアをより故障に対する耐性のあるものとしている。故障が間欠的な場合は、この方法は成功する。もし故障が反復的な場合、フューチらは故障実行パスを回避するために、入力データを再配置することを開示している。このようなシステムは、機能の故障しているシーケンスを再実行しようとするかもしれない。
【００１０】
ぺトリネット（Petri net）は、レイジ（Reisig）の１９８２年、ベルリン、スプリンガー“ペトリネット”［"Petri Net", Springer, Berlin, 1982］に述べられているように、同時システム及び処理を述べる形式主義である。ぺトリネットは、２種類のノード、即ち、データ位置ノード、及び遷移、即ちアクションノードを備える。ぺトリネットは、トークンを使用して何時遷移が実行され得るかを決定する。トークンは、データの利用性を示す。遷移は、トークンが全ての入力記憶位置で利用できる時に実行される。遷移のスケジューリングは、トークンにより決定される。遷移は、全ての入力トークンを消費し、その出力記憶位置にトークンを生成する。ぺトリネットは、演算の方法ではなくて記述的形式であり、適応性がなく学習もしない。
【００１１】
代替のプログラミングパラダイムは、データフロープログラムである。データフロープログラムにおけるアクションの実行は、ハースら（Herath et al）の１９８７年ニューヨーク州ニューヨーク、スプリンガーバーラグ、２５〜３６頁“並行アルゴリズム及びアーキテクチャ”［‘Parallel Algorithms and Architectures", pp. 25-36，Springer-Verlag，New York, New York, 1987］に記述されている。データフロープログラムにおけるアクションの実行は、入力データの利用可能性又は到着によりトリガーされる。データフロープログラムにおけるノードの実行は、本発明のように、出力上におけるデータの利用可能性により制御されない。データフロープログラムは、冗長性を使用しない。
【００１２】
【発明が解決しようとする課題】
これらの従来の方法は、融通性のない命令の順序付けにより生ずる問題に適切にアドレスすることに失敗している。このような技法は、ブランチング、ルーピング、及び非決定性のような一般に理解されている機能性、即ち、同じ変数を演算するための適用できる複数の機能構成要素を使用する。しかしながら、これらの方法は、一般に個々の機能の故障や例えば妨害、演算資源、デバイスの故障やユーザのミスのような環境条件の変化に適用できない。
【００１３】
従って、複雑なセットの構成要素のトラッキングを維持し、簡単な手段で種々のシーケンスのメンバを使用可能にしたり使用不能にするためにデータ駆動最適化演算が必要とされる。
【００１４】
本発明は、複雑なソフトウエアを構築し実行するための方法及び装置を提供する。
【００１５】
本発明は、更に頑強性及び故障耐性を達成するために冗長なセットの機能性構成要素を使用する方法及び装置を提供する。
【００１６】
本発明は、外部からの妨害に対して耐性があり、ダイナミックな再構成を支援する機能性構成要素を構成するための技術を使用する方法及び装置を提供する。
【００１７】
本発明は、学習及びプランニング技法の使用を介して自己最適化を達成する方法及び装置を提供する。
【００１８】
本発明は、タイムスタンプ及び適切な実行ルールの使用を介して機能が実現できる方法及び装置を提供する。
【００１９】
このように、本発明の方法及び装置は、タイムスタンプ、例えば外部からの妨害に対する不変性、の利益を本発明の依存性アクションシステムに埋め込まれた汎用性制御構造の利益と組み合わせる。
【００２０】
【課題を解決するための手段】
本発明の具体的な態様は、以下の通りである。第１の態様は、ソフトウエアシステムにより実行される方法であって、ソフトウエアシステムが、各々が記憶値と少なくとも一つの関連する属性値を有する一セットの記憶領域を有する手段と、各アクションが複数の記憶領域の内の少なくとも二つに関連付けられた、複数のアクションを記憶する手段と、一つのアクションが他の一つのアクションに優先されるべきか否かを指定する優先ポリシーである選択ルールを記憶する手段と、を備え、前記ソフトウェアシステムにより実行される前記方法が、各アクションに関連付けられた前記少なくとも二つの記憶領域に対する前記関連する属性値に基づき一セットの使用可能とされたアクションを決定するステップと、前記選択ルールに基づいて前記セットの使用可能とされたアクションから一つの使用可能とされたアクションを選択するステップと、前記選択された使用可能とされたアクションを実行するステップと、前記選択された使用可能とされたアクションの実行の結果に基づき前記選択された使用可能とされたアクションに関連する前記記憶領域の少なくとも一つに対する記憶値及び前記少なくとも一つの関連する属性値を更新するステップと、新たなアクション及び記憶領域を追加するステップと、各アクションに関連するコスト及びアクションの実行によりそのアクションに関連する記憶領域の幾つかの値を変更する変更確率を更新するステップと、を備え、前記コスト及び変更確率を更新するステップは、一つのアクションに関連する更新されたコスト及び変更確率における変化が所定の基準を満足するか否かを決定するステップと、前記変化が前記所定の基準を満足する場合、前記優先ポリシーを調節するステップと、を含むソフトウエアシステム実行方法である。
【００３０】
第２の態様は、前記第１の態様において、前記セットの使用可能とされたアクションを決定するステップは、前記記憶領域のうち入力データを関連する前記アクションに提供する全ての使用可能記憶領域が初期化され且つ前記記憶領域のうち関連する前記アクションから出力データを受信する全ての使用不能記憶領域が初期化されているか否か及び前記アクションに関連する少なくとも一つの使用可能記憶領域が前記アクションに関連する全ての使用不能記憶領域の属性値よりも大きい属性値を有するか否かに基づいて、前記使用可能とされたアクションを決定することを含む。
【００３２】
第３の態様は、前記第１の態様において、前記属性値は一つの値を有するタイムスタンプであり、一セットの使用可能とされたアクションを決定することは、前記アクションに関連する指定された使用可能及び使用不能記憶領域の関連するタイムスタンプ値に従って使用可能とされる一つのアクションを識別することを更に含む。
【００３３】
第４の態様は、前記第１の態様において、前記属性値はデータ値が前記ソフトウエアシステムへ入力されることに続いて前記記憶領域が更新されたか否かを表す演算スタンプであり、一セットの使用可能とされたアクションを決定することは、前記アクションに関連する指定された使用可能及び使用不能記憶領域の関連する演算スタンプ値に従って使用可能とされる一つのアクションを識別することを更に含む。
【００３５】
第５の態様は、依存性アクションシステムであって、各々が記憶値と少なくとも一つの関連する属性値を有する一セットの記憶領域を有する手段と、各アクションが複数の記憶領域の内の少なくとも二つに関連付けられた、複数のアクションを記憶する手段と、一つのアクションが他の一つのアクションに優先されるべきか否かを指定する優先ポリシーである選択ルールを記憶する手段と、前記選択ルールに基づき一セットの使用可能とされたアクションから一つの使用可能とされたアクションを選択する使用可能とされたアクションセレクタと、新たなアクション及び記憶領域を追加する手段と、各アクションに関連するコスト及びアクションの実行によりそのアクションに関連する記憶領域の幾つかの値を変更する変更確率を更新する手段と、を備え、前記コスト及び変更確率を更新する前記手段は、一つのアクションに関連する更新されたコスト及び変更確率における変化が所定の基準を満足するか否かを決定するための手段と、前記変化が前記所定の基準を満足する場合、新たな優先ポリシーを決定する手段と、を含み、一つのアクションは、そのアクションと関連付けられた前記二つの記憶領域に対する前記少なくとも一つの関連する属性値に基づき使用可能とされ、前記選択された使用可能とされたアクションは、選択されると実行され、且つ前記選択された使用可能とされたアクションに関連する前記記憶領域の少なくとも一つに対する記憶値及びそれに関連する属性値は、前記選択された使用可能にされたアクションの実行の結果に基づき更新される依存性アクションシステム。
【００５０】
本発明のこれらの及びそれらの特徴は、以下の好ましい実施の形態の記述から明らかとなる。
【００５１】
【発明の実施の形態】
本発明の方法及びシステムは、冗長性のある機能構成要素を介して柔軟性と適応性とを達成する生物学系及び生態から導き出され、所与のタスクを達成するようにこれらの構成要素の使用をプランニングし、経験から構成要素の適切性を学習する。冗長性のある機能構成要素を持つことは、複数のインスタンスや同次冗長性と呼ばれる同じ論理機能（関数）の異なる実施が可能であるのみならず、より重要なことは、冗長性のある機能性は、同じ問題を解決するためや異質の冗長性と呼ばれる同じ全体挙動を達成するために異なる方法で異なるセットの機能を組み合わせることを含む。
【００５２】
本発明の方法及びシステムは、同質及び異質の冗長性のある機能性の両方を使用する。結果として、本発明の方法及びシステムは、環境条件や外部からの妨害に対して変化要求に適するシステムを構成するのに有用である。用途は、ループが人間を含むシステム及び故障や予期せぬ挙動を受けるデバイス及び処理を制御するシステムを含むが、それらに限定されるわけではない。
【００５３】
本発明の方法及びシステムは、複数の機能的構成要素を複合するようにタイムスタンプを使用することに基づく。本発明の方法及びシステムは、ビードで述べたように、Unix "Make" ユティティにおいてタイムスタンプの使用を一般化する。このUnix "Make" ユティティに対して、本発明の方法は、異なる出力が異なる実行において生成されてもよいが、同じ変数を決定するために適用できる複数の機能性構成要素を許容できる点において非決定的である。この方法において、記憶位置同士間の依存性は、巡回性があってもよく、反復が可能となる。ブランチングを介して終了が可能である。機能性構成要素の故障は、全体の演算の故障を意味しない。代わりに、代替の機能性構成要素が望ましい出力を決定するようにトライする。このように、故障に応答してバックトラッキングが、合成メカニズムの使用可能ルールに基づき自動化される。
【００５４】
図１は、本発明の依存性アクションシステムの機能要素のブロック図である。依存性アクションシステム１０は、リンク１４を介して記憶又はメモリデバイス１５と通信するプロセッサ１２と、入力デバイス１６と、出力デバイス１７と、異なる依存性アクションシステム処理、即ち‘アクション’の構造的相互関係を記憶するデータ構造１８と、を備える。記憶デバイス１９は、後で詳述される依存性アクションシステムパラメータを記憶する。プロセッサ１２は、入力デバイス１６と通信し、依存性アクションシステム１０を作動するためにユーザからコマンドを受信する。入力デバイス１６は、あらゆる数のマウスやキーボードなどの従来の入力デバイスを含む。
【００５５】
図１に示されるように、システム１０は、プログラムされた汎用コンピュータを用いて実施されることが好ましい。しかしながら、システム１０は、特殊目的コンピュータ、プログラムされたマイクロプロセッサやマイクロコントローラや、あらゆる必要な周辺集積回路、ASICや他の集積回路、離散要素回路のようなハード配線電子回路や論理回路、ディジタル信号プロセッサ、PLD、PLA，FPGA，PALのようなプログラマブル論理デバイス等を使用して実施できる。一般に、システム１０は、図１０乃至１６に示されるフロー図を実行できる有限状態機械を実施できるあらゆるデバイスで実行され得る。
【００５６】
更に、図１に示されるように、記憶又はメモリデバイス１５は、スタティク又はダイナミックRAMを用いて実施されることが好ましい。永久記憶又はメモリデバイス１９は、フロッピーディスク及びディスクドライブ、書き込み可能光学ディスク及びディスクドライブ、ハードドライブ、フラッシュメモリ等を使用して実施されるのが好ましい。更に、記憶又はメモリデバイス１５及び永久記憶又はメモリデバイス１９は、単一のメモリや物理的に複数の個別のメモリの何れであってもよい。
【００５７】
更に、永久記憶又はメモリデバイス１９とプロセッサ１２とを接続するリンク１４は、図示されていないが、ネットワークへのハード配線又は無線リンクである。ネットワークは、ローカルエリアネットワーク、ワイドエリアネットワーク、イントラネット、インターネット、或るいは他のあらゆる分散型処理記憶ネットワークであってもよい。
【００５８】
図２の（ａ）乃至図２の（ｆ）は、本発明の依存性アクションシステムの基本構成を示す。図２の（ａ）に示されるように、依存性アクションシステムの基本構成要素は、アクション２０である。アクション２０は、要求され生成されるデータに関して依存性アクションシステムの機能性構成要素を定義する。図２の（b）乃至図２の（d）に示されるように、要求され生成されたデータ属性スタンプ記憶位置２２−２６に記憶される。データ属性スタンプ記憶位置２２−２６をスタンプするために使用される属性は、タイムスタンプであってもよいし、他のあらゆる属性パラメータであってもよい。好ましくは、使用される属性は、以下に定義されるように、タイムスタンプT又は演算スタンプである。図２の（b）は、一般的タイムスタンプ記憶位置２２を示す。図２の(C)は、タイムスタンプ記憶位置２４を示す。図２の（d）は、タイムスタンプ入力記憶位置２４を示すが、図２の（d）は、タイムスタンプ出力記憶位置２６を示す。記憶位置は、入力と出力記憶位置の両者であってもよく、その場合、図２の(C)及び図２の（ｄ）が組み合わされる。
【００５９】
演算スタンプは、演算カウンタに対するものであり、タイムスタンプは、クロックに対するものである。タイムスタンプの更新は、演算スタンプ属性に演算カウンタの現在の値を記録することを意味する。演算スタンプの更新は、演算スタンプ属性に演算カウンタの現在の値を記録する事を意味する。クロックの値が時間と共に増加するが、演算カウンタの値は、新しい入力データが依存性アクションシステムに与えられる時は何時も増加する。記憶位置は、タイムスタンプ属性又は演算スタンプ属性又は、その両者を持つことができる。特に指定しない場合はスタンプという場合は、タイムスタンプと演算スタンプの両者を含む。記憶位置は、メモリ記憶位置及びパスによりアクセスされるファイルの何れであってもよい。
【００６０】
図２の（e）は、アクション２０を可能にするスタンプされた使用可能記憶位置２８を示す。即ち、アクション２０は、使用可能な記憶位置２８により使用可能にされる。反対に、図２の(f)は、スタンプされた使用不能記憶位置３０に接続されるアクション２０を示す。即ち、アクション２０は、この使用不能記憶位置３０により使用不能にされる。
【００６１】
図３は、アクション１２０、単一の使用可能記憶位置１１０、及び２つの使用不能記憶位置１３０及び１３２を含む例示の依存性アクションシステム１００を示す。記憶位置１１０は、ユーザにより、アクション１２０に対する使用可能記憶意位置であるように定義され、記憶位置１３０及び１３２は、アクション１２０に対する使用不能記憶位置として定義される。下記でより詳細に説明されるように、アクション１２０は、アクション１２０と記憶位置１１０のような記憶位置との間の使用可能関係定義するルールに従って使用可能アクションになる。この関係は、アクション１２０に関連する使用可能及び使用不能記憶位置１１０，１３１及び１３３の相対値、“イーガー（eager）”であるか“レイジー(lazy)”であるかのアクションのタイプ，及び記憶位置１１０，１３０及び１３２に記憶されたデータ値に関して表現される。これらの関係は、図７乃至図９に関して以下でより詳細に述べる。アクション１２０の実行は、アクション１２０の内部ルールにより、使用不能記憶位置１３０及び１３２の何れにも記憶されていない値、これらの位置の一方又は両方に記憶されている値を変化させる。
【００６２】
記憶位置１１２は、存在するがアクション１２０に関連しない他の使用可能な記憶位置を表し、図示されない他のアクションと関連させてもよい。以下で論じられるように、アクションと記憶位置との間の依存性は、入力デバイス１６を介して適切なコマンド及びデータを入力することによりユーザ定義される。これらのコマンド及びデータは、依存性アクションシステムが処理動作を行っている時を含み何時入力されてもよい。このような入力は、永久記憶装置１９への次の転送のために、ランダムアクセスメモリ記憶装置１５内に書き込まれる。
【００６３】
各アクション毎に、１セットの少なくとも一つの使用可能記憶位置及び１セットの少なくとも使用不能記憶位置がある。一般的に、必ずしも必要ではないが、使用可能記憶位置は、入力データを関連するアクションに提供し、使用不能記憶位置は、関連するアクションから出力データを受信する。一般に、イーガーアクションは、使用可能にされ使用可能な記憶位置の何れか一つのタイムスタンプが全ての使用不能記憶位置のタイムスタンプよりも最近である時は実行され得る。レイジーアクションは、使用可能とされ、使用可能記憶位置の何れか一つの演算スタンプが全ての使用不能記憶位置の演算スタンプよりも最近である時は実行され得る。アクションの使用不能記憶位置の何れかのスタンプの更新によりそのアクションが使用不能にされる。このように、アクションの実行はその関連する使用可能及び使用不能記憶位置のタイムスタンプ又は演算スタンプにより制御される。従って、熱心なアクションは、新たなデータがその使用可能記憶位置の一つに到着した時は何時でも使用可能にされ、その記憶位置の関連するタイムスタンプが更新される。反対に、レイジーアクションは、その使用可能記憶位置の一つに到着したその新たなデータが受信された新たな入力データを有する依存性アクションシステムに起因する時のみ使用可能とされる。
【００６４】
使用可能及び使用不能記憶位置は、オペレーティングシステムにより管理されるファイルであってもよいし、メモリ内の位置であってもよい。前者の場合、オペレーティングシステムは、これらの記憶位置のタイムスタンプを維持する。後者の場合、各このような記憶位置毎にタイムスタンプは、メモリ内に維持される。何れの場合も、記憶位置が関連する演算スタンプを有するならば、演算スタンプは、メモリ内に維持されなければならない。各記憶位置は、名前を備え、その名前は、１）値のメモリ位置及びタイムスタンプ又は演算スタンプに対する一対の参照；又は２）ファイルのパスに関連される。
【００６５】
アクションは、以下の三つの種で発生する。１）例えば,Jave, C++のようなネイティブプログラミング言語で実行される機能；２）別の処理としてオペレーティングシステムで実行されるプログラム；及び３）他の依存性アクションシステムにより定義されるアクション。
【００６６】
依存性アクションシステムは、入れ子にされてもよい。これは、アクションが自身が他の完全な依存性アクションシステムを表すことができることを意味する。このようなアクションを実行することは、関連する依存性アクションシステムを実行することに等しい。
【００６７】
各アクションは名前を備えてもよい。使用可能記憶位置及び使用不能記憶位置のリストは、アクションの平均コスト、アクションの種類、及びａ）機能への参照；ｂ）プログラムへのパス；又はｃ）依存性アクションシステムの記述；のアクションの種類への依存として、各アクションに関連する。また、各アクションにはそのアクションが各関連する使用不能記憶位置を更新する確率が関連する。
【００６８】
アクションは、関連する機能を呼び出すか、関連するプログラムを別の処理として実行するか、又は関連する依存性アクションシステムにより実行される。平均コスト属性及び更新確率は、そのアクションが実行される時は何時でも調整される。しかしながら、コストは、他の方法で決定されてもよい。実際のコスト関数は、時間、空間、又は品質のような属性パラメータに基づいてもよく、アプリケーション及び要求で変化し得る。
【００６９】
複数のアクションが使用可能にされると、依存性アクションシステムは、選択ルールを使用して使用可能とされたアクションの内のどのアクションが実行されるべきかを決定する。使用可能とされたアクションのセットの内のどのアクションが実行のために選択されるべきかを定めるポリシーが予め設定されてもよい。依存性アクションシステムの最も安価な実行となるポリシーが最適である。これは、“Introduction to Operations Research", F.S. Hillier and G.J. Leiberman, McGraw-Hill, sixth edition, 1996,  （ここに参照により組み込まれている）に述べられているように、マルコフ決定処理であることが理解されるべきである。
【００７０】
このような決定処理は、各状態において決定が使用可能とされたアクションの内のどのアクションが次に実行されるべきかについて決定がなされることが必要である。もし、使用可能とされたアクションのセットが空の場合は、処理はストップする。決定のコストは、選択されたアクションのコストである。
【００７１】
従って、依存性アクションシステムの効率は、各状態において使用可能とされたアクションの内のどのアクションが選択されるかに依存する。マルコフ決定処理に対する標準のポリシーベースのプランニングが、本発明の依存性アクションシステムの使用可能アクション優先ポリシーを案出するために使用される。マルコフ決定処理を使用して依存性アクションシステムの最適実行を提供すると共に、このような最適ポリシーを決定することは非常に高価である。本発明は、一つのアクションが他の一つのアクションに優先されるべきか否かを指定する優先関係に基づく優先ポリシーと呼ばれる特定のタイプの選択ルールを使用する。
【００７２】
依存性アクションシステムは、望ましい出力記憶位置に直接的且つ間接的に影響を与えないこれらのアクションを除去、即ち、使用可能とは考えられない、することにより最適化され得る。
【００７３】
ダイナミックな変化は、システムが依存性アクションシステムを実行している間に、依存性アクションシステムパラメータ及びアクションがユーザによりあるいは外部エージェントにより変化されうることを意味する。これらのパラメータ及びアクションは、それらの使用可能及び使用不能記憶位置と共に、永久メモリ１９に記憶される。この記憶された情報は、アクションの追加又は削除、記憶位置の追加又は削除、あるいはアクションの使用可能及び使用不能記憶位置の変更を含むオペレーションにより変更され得る。重要なことは、これらのオペレーションは、依存性アクションシステムが実行している時でさえ、何時でも実行され得る。
【００７４】
各アクションは、イーガー或いはレイジーなものとして定義される。イーガーアクションが使用可能か否かを決定する場合、使用可能及び使用不能記憶位置のタイムスタンプが考慮される。レイジーアクションが使用可能か否かを決定する場合は、使用可能及び使用不能記憶位置の演算スタンプが考慮される。そうでない場合は、イーガーアクションとレイジーアクションとの間に差がない。
【００７５】
実行中の依存性アクションシステムは、種々の入力及び出力オペレーションを実行することにより、例えば、他のプログラムやユーザのような環境と対話する事ができる。例えば、下層のオペレーションシステムに基づく出力又は通信オペレーションを実行するアクションは、実行された時に出力データを生成する。入力は、入力値を依存性アクションシステムの適切な入力記憶位置に割り当ててそれらのスタンプを更新する外部処理から依存性アクションシステムへ提供される。
【００７６】
使用可能とされたアクション選択ルールは、実行のための幾つかの使用可能とされたアクションの一つを選択するために使用される。ランダムに使用可能とされたアクションの一つをピックアップするトリビアル選択ルールを含む異なる選択ルールが使用され得る。本発明は、図１３に関して後述される使用可能とされたアクション優先ポリシーを指定する。この優先ポリシーは、記憶された優先関係を使用する。後述される図１４乃至図１６は、優先関係を決定するための方法を示す。
【００７７】
図４は、例示の依存性アクションシステム２００の累積進行を示す。例示の依存性アクションシステム２００は、一セットの記憶位置２１０，２１２，２３０，２３２、及び２５０を含む。各位置は、未定義であってもよい一つの値有する。スタンプ２１１，２１３，２３１，２３３、及び２５１は、記憶位置２１０，２１２，２３０，２３２、及び２５０と夫々関連する。例示の依存性アクションシステム２００は、更に一セットのアクション２２０，２２２、及び２４０を含む。アクション２２０，２２２、及び２４０の各々は、任意の複雑性の処理関数を表す。記憶位置２１０，２１２，２３０，２３２、及び２５０とアクション２２０，２２２、及び２４０との間の依存関係は、予め定義される。即ち、アクション２２０，２２２、及び２４０の各々毎に、記憶位置の内の一つ又は複数が使用可能記憶位置として定義され、記憶位置２１０，２１２，２３０，２３２、及び２５０の内の一つ又は複数が使用不能記憶位置として定義される。例えば、図４の例示の依存性アクションシステムにおいて、アクション２２０及び２２２の両方は、使用可能記憶位置として記憶位置２１０及び２１２に関連付けられる。同様に、記憶位置２３２は使用不能記憶位置としてアクション２２０及び２２２の両方に関連付けられ、記憶位置２３０のみは、使用不能位置としてアクション２２０に関連付けられる。
【００７８】
一般に、アクション２２０、２２２、２４０の各々は、その使用可能記憶位置の一つ又は複数からデータを読み出し、その使用不能記録位置の一つ又は複数へデータを書き込むので、そのアクションは、各そのような記憶位置と関連するスタンプを更新する。
【００７９】
図４において、例示の依存性アクションシステム２００により行われるべきタスクは、出力記憶位置２５０の値を決定することである。もしアクション２２０がイーガーであるならば、それは次の二つの条件を満足する時“使用可能アクション”と呼ばれる。第１の条件は、使用可能及び使用不能記憶位置２１０及び２１２が初期化されなければならない。即ち、それらは有効値を含むように定義されなければならない。第２の条件は、タイムスタンプ２１１及び２１３の内の少なくとも一方は、タイムスタンプ２３１及び２３３の後者よりも遅くなければならない。同様に、アクション２２２は、タイムスタンプ２１１及び２１３の内の少なくとも一方がタイムスタンプ２３１及び２３３の後者よりも遅いならば、使用可能とされる。このように、アクション２２０及び２２２の両方が、使用可能とされると、出力記憶位置２５０の値を生成する二つのパスがある。
【００８０】
依存性アクションシステム２００が事前定義された選択ポリシーに従うと仮定すると、アクション２２０は、アクション２２２より先に選択されて実行される。アクション２２０の実行は、使用不能記憶位置２３２および２３３の値、即ち、恐らくアクション２２０の内部処理に依存して両方、を生成できる。
【００８１】
もしアクション２２０が記憶位置２３２の値を生成するならば、タイムスタンプ２３３は両タイムスタンプ２１０及び２１２より遅れ、両アクション２２０及び２２２はもはや使用可能とされない。しかしながら、もしアクション２２０が記憶位置２３０の値を生成するが記憶位置２３２の値を生成しないならば、アクション２２０は、タイムスタンプ２３１がタイムスタンプ２１０及び２１２よりも遅いので、もはや使用可能にされない。しかし、アクション２２２はなお使用可能とされており、記憶位置２３２の値を生成するために実行され得る。このように、記憶位置２３２の値を決定するための二つの代替方法がある。このように依存性アクションシステムは冗長性を提供する。
【００８２】
アクション２２０又は２２２が新たなデータ値を使用不能位置２３２に書き込む時、関連するタイムスタンプ２３３もまた現在の時間で更新される。記憶位置２３２がアクション２４０の使用可能記憶位置であり、アクション２２０及び２２２の使用不能記憶位置である為、アクション２４０は、アクション２２０及び２２２が使用不能になると同時に使用可能とされる。アクション２４０が使用可能であるので、そのアクションは、記憶位置２３２に記憶されているデータを処理し、その使用不能記憶位置２５０にその結果のデータを配する。同時に、記憶位置２５０に関連するタイムスタンプ２５１は、現在の時間で更新される。このように、全体の例示の依存性アクションシステムの全てのアクションが使用不能にされる。
【００８３】
図４に示される例示の依存性アクションシステムは、また記憶位置２１０が複数のアクション、即ち、二つのアクション２２０及び２２２、に対してどのように使用可能にされるかを示す。従って、いずれかのアクションが多分異なる入力データから使用不能記憶位置２３２のデータを決定するために使用され得る。一つのアクションが成功し出力データを生成するならば、このデータは、使用不能記憶位置２３２に記憶され、タイムスタンプ２３３が更新される。これによりアクション２２０及び２２２が使用可能とされる。一つのアクション２２０又は２２２が記憶位置２３２の出力データを生成するのに失敗すると、他方のアクション２２２又は２２０がまだ使用可能であり、そのアクションが実行され得る。このように、依存性アクションシステム２００は、個々のアクションの失敗から自動回復を支援する。
【００８４】
或る点において、外部メカニズムが使用可能記憶位置２１０又は２１２の値、従ってその記憶位置２１０又は２１２と関連するスタンプ２１１又は２１２を更新するならば、本発明の方法及びシステムは、記憶位置２１０又は２１２により使用可能とされるアクション２２０及び２２２が再実行されて、使用不能位置２３０及び／又は２３２の新たな値を生成することを保証する。
【００８５】
図５は、図４に示される依存性アクションシステム２００を拡張するためにダイナミックに追加される新たな又は変更されたアクション及び記憶位置の組み合わせを有する第２の例示の依存性アクションシステム２００‘を示す。
【００８６】
図５に示されるように、追加のアクション及び記憶位置は、任意ではあるが、各アクションと関連するコストデータと共に、依存性アクションシステムの実行の間に追加され得る。例えば、ユーザ又は別のプログラムは記憶位置２３６及びその関連するタイムスタンプ２３７の変更又は追加及びその記憶位置２３６の依存性を定義するデータを例えばアクション２２４及び２４２で入力できる。このように、実行されるべき依存性アクションシステム処理２００‘は追加された又は変更されたアクション及び関連する記憶位置に遭遇し、次に新たなアクション２２４及び／又は２４２の使用可能記憶位置が更新される。
【００８７】
図４と図５に関連して述べられるタイムスタンプは、使用可能とされたアクションを決定する。一つの使用可能アクションが有効な使用可能なアクション選択ルール及び使用可能なアクションのタイプに従って選択される。このアクションが次に実行され、実行されたアクションに関連する使用不能記憶位置を変更する。次に、依存性アクションシステムは、現在のセットの使用可能アクションを見て、一つを選択してそれを実行し、使用可能なアクションがなくなるまでこの手順を繰り返す。
【００８８】
依存性アクションシステム２００‘において、記憶位置２４２に対する望ましい出力値を決定するための三つの異なるパスがある。これらのパスは、可能なアクションのシーケンス、即ち、アクション２４０が続くアクション２２０、アクション２４０が続くアクション２２２、及びアクション２４２が続くアクション２２４を含む。アクション２２０及び２２２がアクション２４０の入力データを決定するので、それらの両方は、恐らく異なる手段を使用して同じ機能を実行しなければならない。これは、同種の冗長性と呼ばれる。しかしながら、これらのアクション２２４及び２４２は、完全に異なる方法で記憶位置２５０の結果を決定できる。特に、記憶位置２３６の中間値が記憶位置２３２の中間値と異なってもよく、アクション２２４はアクション２２０及び２２２と全く異なる機能（関数）実行できる。これは、異種の冗長性と呼ばれる。
【００８９】
図６は、反復を実行するための一対のシリアルに接続された‘イーガー’アクションと依存性アクションシステムの能力を示す。図６に示される依存性アクションシステム４００は、第１のイーガーアクション４２０及び第２のイーガーアクション４２２を含む。第１の記憶位置４１０は、入力記憶位置であり、またイーガーアクション４２０の使用可能記憶位置であり、イーガーアクション４２２の使用不能記憶位置である。このように、記憶位置４１０は、イーガーアクション４２２の出力をイーガーアクション４２０の入力に接続する。一方、イーガーアクション４２０は、記憶位置４３２の値又は記憶位置４３２をイーガーアクション４２０の内部ルールに依り更新する。
【００９０】
同様に、記憶位置４３０は、イーガーアクション４２２の使用可能記憶位置であり、イーガーアクション４２０の使用不能記憶位置である。このように、記憶位置４３０は、イーガーアクション４２０の出力をイーガーアクション４２０の入力に接続する。最後に、第３の記憶位置４３２は、またイーガーアクション４２２の使用不能記憶位置である。このように、入力記憶位置４１０が有効データを備える時、依存性アクションシステム４００の他のひとつのアクション（図示せず）、ユーザ、又は何らかの依存的に実行される処理により、入力記憶位置４１０に関連するタイムスタンプ４１１が更新される。タイムスタンプ４２０が、イーガーアクション４２０の使用不能記憶位置４３０及び４３２に関連するタイムスタンプ４３１及び４３２の両方よりも遅いので、イーガーアクション４２０は使用可能とされる。このように、もしイーガーアクション４２０が実行され使用不能記憶位置４３０及び／又は４３２を更新すると、更新された記憶位置４３０及び／又は４３２と関連するタイムスタンプ４３１及び／又は４３３が更新されて記憶位置が更新された時間を反映する。
【００９１】
記憶位置４３０が更新されると、記憶位置４３０のタイムスタンプ４３１は記憶位置４１０のタイムスタンプ４１１の時間より遅い。このようにイーガーアクション４２２が使用可能にされる。もしイーガーアクション４２２が実行され記憶位置４１０へデータを出力すると、その関連するタイムスタンプ４１１もまた記憶位置４１０が更新された時間を反映するように更新される。しかしながら、これは記憶位置４１０のタイムスタンプ４１１が記憶位置４３０のタイムスタンプよりも時間が遅いことを意味する。このように、イーガーアクション４２０が再び使用可能とされる。このように、イーガーアクション４２０及び４２２はこの処理を介して記憶位置４３０がイーガーアクション４２０の出力により更新されなくなるまで循環する。即ち、イーガーアクション４２０が記憶位置４３２を更新するが記憶位置４３０を更新しない時のみ、イーガーアクション４２０及び４２２のこの循環実行が停止する。
【００９２】
図７は、依存性アクションシステム５００における一対のシリアルに接続された‘レージー’アクションを示す。例えば、図７に示される依存性アクションシステム５００は、第１のレージーアクション５２０及び第２のレージーアクション５２２を含む。第１の記憶位置５１０は第１のレージーアクション５２０の使用可能記憶位置及び第２のレージーアクション５２２の使用不能記憶位置として働く。このように、記憶位置５１０は、レージーアクション５２０の出力をレージーアクション５２２の入力へ接続する。同様に、第２の記憶位置５３０は、レージーアクション５２２の使用可能記憶位置及びレージーアクション５２０の使用不能記憶位置として働く。このように、記憶位置５３０は、レージーアクション５２０の出力をレージーアクション５２２の入力へ接続する。レージーアクション５２０及び５２２、及び記憶位置５１０及び５３０が最初に初期化されると、記憶位置５１０及び記憶位置５３０の両方が未定義となる。
【００９３】
アクション５２０及び５２２がレージーであるので、記憶位置５１０及び５３０は共に夫々演算スタンプ属性５１１及び５３１を備えなければならない。もし記憶位置５１０がある第３のアクション（図示せず）、ユーザ、又は依存的に作動する処理からデータを受信すると、その演算スタンプが更新される。もしこの入力が新たな演算を構成すると、それはより高い演算数を有し、演算スタンプ５１１は記憶位置５３０の演算スタンプ５３１よりも大きい。記憶位置５１０が使用可能であり、記憶位置５３０がレージーアクション５２０に対して使用不能であるので、レージーアクション５２０が使用可能とされる。もしアクション５２０が実行され、記憶位置５３０を更新すると、演算スタンプ５３１が現在の演算数に更新される。この点、演算数５３１及び５１１は等しく、アクション５２０もアクション５２２も使用可能でない。
【００９４】
もし演算カウントがインクリメントされ、即ち、新たな演算が開始されると、、演算スタンプ５３１が記憶位置５１０の演算スタンプ５１１よりも大きく、アクション５２２が使用可能とされる。もしアクション５２２が実行され記憶位置５１０を更新すると、演算スタンプ５１１が演算スタンプ５３１と等しくなるように更新される。このようにアクション５２０及びアクション５２２の両方が使用可能にされない。
【００９５】
このように、依存性アクションシステム５００において、記憶位置５１０及び５３０の一方が入力記憶位置として取られ、他方が出力記憶位置として取られる。もし記憶位置５１０が入力として取られると、アクション５１０は記憶位置５３０に出力値を生成する。もし記憶位置５３０が入力として取られると、アクション５２２が記憶位置５１０に出力値を生成する。
【００９６】
図８は、本発明の依存性アクションシステムの故障状態態様を詳細に示す。一般に、アクションの故障状態は、アクションの使用可能、使用不能、及び出力記憶位置を定義する時に、提供されなければならない。図８は、各々がアクションの故障を処理する一つの方法にアドレスする二つの故障のケースを示す。図８に示されるように、依存性アクション６００は、第１のアクション６２０、第２のアクション６２２及び第３のアクション６４０を含む。入力記憶位置６１０はアクション６２０及び６２２に対する使用可能記憶位置である。出力記憶位置６３２はアクション６２０及び６２２の各々に対する使用不能記憶位置である。記憶位置６３０はアクション６２０に対する第２の使用不能記憶位置であり、アクション６４０に対する使用可能位置でもある。記憶位置６３２はアクション６４０に対する使用不能記憶位置である。
【００９７】
通常の動作において、記憶位置６１０は、依存性アクションシステム６００の他の一つのアクション（図示せず）、ユーザ、又は依存的に実行する手順により新たなデータが提供される。その結果、スタンプ６１１が更新され、それは記憶位置６３０及び６３２のスタンプ６３１及び６３３よりも遅い。従って、記憶位置６２０及び６２２が使用可能とされる。次に、使用可能とされたアクション選択ルールがアクション６２０を選択すると仮定すると、アクション６２０が実行を開始する。アクション６２０が通常通りに終了すると、そのアクションは、記憶位置６３２に記憶される出力データを生成する。この結果、記憶位置６３２に関連するスタンプ６３３は更新され、従ってアクション６２０を使用可能とする。
【００９８】
しかしながら、もしアクション６２０が通常の終了に失敗すると、即ち、失敗すると、二つの回復モードの何れかが使用されてこの失敗（故障）を処理する。第１の故障モードにおいて、アクション６２０が失敗すると、このアクションは故障記憶位置６３０に記憶されるデータを生成する。その結果、スタンプ６３１が更新される。記憶位置６３０がアクション６４０に対して使用可能記憶位置でもあるので、アクション６４０が使用可能とされる。アクション６４０は記憶位置６３０に記憶されたデータに基づきエラー回復を実行するプログラム又は機能（関数）であってもよく、出力記憶位置６３２に値を生成する他の方法を使用する。
【００９９】
第２の故障モードにおいて、使用可能とされたアクション６２０が、故障記憶位置に記憶される出力値を生成するよりもむしろ失敗すると、アクション６２２はなお使用可能とされ、記憶位置６３２の望ましい値を決定するための代替のメカニズムを使用することにより回復がなされる。これは、“バックトラッキング”を保証する。使用可能とされた選択ルールは、使用可能とされたアクション６２０及び６２２の内最初にどちらがトライされるかを決定する。同様に、もしアクション６２０が記憶位置６３２を更新せずに記憶位置６３０を更新すると、選択ルールは、回復の為にアクション６４０及びアクション６２２のどちらが使用されるかを決定する。この挙動は、依存性アクションシステムの設計者により追加の依存性を追加することにより変更され得る。例えば、記憶位置６３０がアクション６２２に対する使用不能記憶位置とされると、回復アクション６４０は、常にアクション６２２に優先される。
【０１００】
図９は、本発明による依存性アクションシステムの一般的用語における作用の概略を示すフロー図である。依存性アクションシステムは、ステップＳ１０００で始まるルーチンを制御する。制御はステップＳ１１００に移行し、このステップで依存性アクションシステムは全ての記憶位置を‘空’に設定することにより初期化される。即ち、ステップＳ１１００において、依存性アクションシステムは、全ての記憶位置の内容が外部入力の結果又は依存性アクションシステム処理の結果でないことを認識する。全ての空の記憶位置は、未定義と呼ばれる。未定義ではない記憶位置は定義されていると呼ばれる。ファイル記憶位置は、そのファイルが存在しないことを保証することにより未定義としてマークされる。メモリ記憶位置はそのタイムスタンプをイリーガル値に設定することにより未定義としてマークされる。次に、制御は、ステップＳ１２００に移行する。
【０１０１】
ステップＳ１２００において、入力データが定義された記憶位置の一つ又は複数に提供される。次に、ステップＳ１３００において、制御システムは、図４に関して上記されたように、依存性アクションシステムのアクションの内の何れが“使用可能”にされるかを決定する。もし使用可能にされたアクションがあるならば、制御はステップＳ１４００に移行する。そうでない場合は、制御はステップＳ１５００にジャンプする。ステップＳ１４００において、使用可能なアクションの一つが実行される。
【０１０２】
一つのアクションのみが使用可能である場合は、もちろんそのアクションが実行のための選択される。二つ以上のアクションが使用可能である場合、使用可能なアクションの内の一つが実行のための選択される。実行されるべき使用可能なアクション選択のための手順は、図１０に関して以下詳細に説明される。次に、制御はステップＳ１３００にリターンする。
【０１０３】
もはや使用可能なアクションが無くなると、制御はステップＳ１５００にジャンプし、そこで一つ又は複数の使用不能な記憶位置に記憶された得られたデータが出力される。制御システムは、記憶デバイス１５又は１９の適切な記憶位置にアクセスし、及び／又は出力デバイス１７で出力を生成する。次に、制御はステップＳ１６００に移行し、そこで、依存性アクションシステムの制御ルーチンは停止する。
【０１０４】
依存性アクションシステムは、非着信（ｎｏｎ−ｔｅｒｍｉｎａｔｉｎｇ）モニターや制御処理を実現する為に使用され得る。この場合、ステップＳ１３００は、使用可能なアクションがないならば、システムは或るアクションが使用可能にされるまで、待つように変更され得る。これは、一つ又は複数の記憶位置のタイムスタンプに影響を及ぼす外部入力に起因して発生する。
【０１０５】
図１０は、図９のステップＳ１３００及びＳ１４００をより詳細に説明するフロー図である。ステップＳ１３００において、制御はステップＳ１３３０に移行し、そこで、一セットの使用可能アクションが生成される。このセットは、種々のアクションの最新の使用可能／使用不能なステータスを反映しなければならないので、このセットの使用可能アクションは、ステップＳ１３３０が実行される毎に再生成される。最新の使用可能／使用不能なステータスは、使用可能及び使用不能記憶位置のタイムスタンプ又は演算スタンプにより反映され、それはユーザ入力若しくは外部システムにより、又は依存性アクションの実行の結果として変更されていてもよい。
【０１０６】
使用可能とされたアクションのセットがステップＳ１３３０で再発生されると、制御がステップＳ１３６０に移行する。ステップＳ１３６０において、制御ルーチンは、そのセットの使用可能アクションが空か否かを決定する。もし空ならば、制御はステップＳ１３９０に移行して制御を図９のステップＳ１５００にリターンする。そうでない場合、制御は、ステップＳ１４３０にジャンプする。
【０１０７】
ステップＳ１４３０において、好ましい使用可能アクションが或る選択ルールに従って選択される。本発明の好ましい実施形態は、選択ルールとして、優先ポリシーより具体的には優先関係を使用する。この優先ポリシーの詳細は図１３を参照して以下に述べられる。特に単純な選択ルールは、使用可能アクションの内の一つをランダムに選択することである。次に、ステップＳ１４６０において、ステップＳ１４３０で選択された選択アクションが実行される。記憶位置の値がステップＳ１４３０の選択アクションを実行する処理において更新される時は何時でも、記憶位置のタイムスタンプおよび演算スタンプが更新される。次に、制御がステップＳ１３３０にリターンする。
【０１０８】
図１１は、二つの入力数の最大公約数を決定する単純な依存性アクションシステム１０００を示す。図１１に示すように、依存性アクションシステム１０００は、二つの入力記憶位置１０１０及び１０１２よりなる。依存性アクションシステム１０００は、更に四つの異なる演算機能（関数）を実行する四つの中間イーガー記憶位置１０２０，１０２２、１０２４及び１０２６を含む。依存性アクションシステム１０００は、更に四つの中間記憶位置１０３０，１０３２、１０３４及び１０３６を含む。最後に、依存性アクションシステム１０００は、イーガー割り当てアクション１０４０及び出力記憶位置１０５０を含む。
【０１０９】
特に、入力記憶位置１０１０及び１０１２は、テスト関数アクション１０２０及び１０２６に対する使用可能記憶位置として及び演算関数アクション１０２２及び１０２４に対する使用不能記憶位置として働く。同様に、中間記憶位置１０３０及び１０３２は、テスト関数アクション１０２０に対する使用不能記憶位置として働く。中間記憶位置１０３２は、演算関数アクション１０２４に対する使用可能記憶位置として働く。同様に、中間記憶位置１０３４及び１０３６は、テスト関数アクション１０２６に対する使用不能記憶位置として働き、記憶位置１０３４は、演算関数アクション１０２２に対する使用可能記憶位置として働く。出力記憶位置１０５０は、割り当てアクション１０４０に対する使用不能記憶位置として働く。
【０１１０】
特に、テスト関数アクション１０２０は、Ｘ記憶位置１０１０に現在記憶されている数がＹ記憶位置１０１２に現在記憶されている数より小さいか否かを決定する。もし、小さいなら、アクション１０２０は、終了し、有効データを記憶位置１０３２へ提供し、従って、演算関数アクション１０２４を使用可能とする。そうでない場合、テスト関数アクション１０２０は、失敗し、故障状態を記憶位置１０３０に書き込む。演算関数アクション１０２２が使用可能とされると、演算関数アクション１０２４は、Ｘ記憶位置１０１０に記憶された現在の値をＹ記憶位置１０１２に記憶された現在の値から減算し、得られた値をＹ記憶位置１０１２に記憶する。
【０１１１】
反対に、テスト関数アクション１０２６は、Ｙ記憶位置１０１２に記憶されている値がＸ記憶位置１０１０に記憶されている値より小さいか否かを決定する。もし、小さいならば、アクションが終了し、有効データを記憶位置１０３４に提供し、従って、演算関数アクション１０２２を使用可能にする。そうでない場合、演算関数アクション１０２６は失敗し、データを故障記憶位置１０３６に書き込む。演算関数アクション１０２２が使用可能にされて実行されると、アクション１０２２は、Ｙ記憶位置１０１２に記憶されている値をＸ記憶位置１０１０に記憶されている値から減算され、得られた値をＸ記憶位置１０１０に書き込む。
【０１１２】
割り当てアクション１０４０が実行されると、このアクション１０４０は、Ｘ記憶位置１０１０に記憶されている値を出力記憶位置１０５０へ出力する。
【０１１３】
動作において、二つの数Ｘ及びＹがＸ及びＹ記憶位置１０１０及び１０１２に夫々記憶される。これによりテスト関数アクション１０２０及び１０２６、並びに割り当てアクション１０４０が使用可能とされる。最初に、定義された使用可能アクション選択ルールに基づき、テスト関数アクション１０２０と１０２６の一方及び出力アクション１０４０が選択される。各期間毎に、残りの新たな使用可能アクションの一つが選択されて更にアクションを使用可能にしてもよい。依存性アクションシステム１０００は、もはや使用可能にされるアクションが無くなるまで、種々の使用可能アクションを介して循環を続ける。無くなった時点で、依存性アクションシステム１０００が終了し出力記憶位置１０５０に記憶された値が入力値Ｘ及びＹの最大公約数として出力される。
【０１１４】
図１２は、Ｘ及びＹとして値３４及び５７を使用して依存性アクションシステム１０００の一つの実行のためのタイミング図を示す。図１２は、各期間毎に、定義された使用可能アクションルールに従って選択可能な一セットの使用可能アクションを示す。図１１の依存性アクションシステム１０００の実行では、各期間毎にランダムな使用可能選択ルールを使用し、そこでは選択されたアクションには、アンダーラインが付されている。
【０１１５】
最初に、図９のステップＳ１１００が実行された後に、全ての記憶位置１０１０、１０１２，１０３０、１０３２、１０３４，１０３６、及び１０５０は、“空”としてマークされる、即ち、それらは未定義である。次に、図９のステップＳ１２００に従って、Ｘ及びＹ入力記憶位置１０１０及び１０１２が値３４及び５１で夫々初期化される。記憶位置１０１０及び１０１２はここで定義され、それらのタイムスタンプが、この例では現在の時間１に設定される。
【０１１６】
従って、時間１において、テスト関数アクション１０２０及び１０２６、並びに出力アクション１０４０は、それらの使用可能記憶位置の少なくとも一つがそれらの使用不能記憶位置の全てと関連するタイムスタンプよりも遅いタイムスタンプを有するので、使用可能とされる。依存性アクションシステム１０００がランダムな使用可能とされたアクション選択ルールを使用しているので、使用可能とされたアクション１０２０、１０２６又は１０４０の何れか一つが実行の為に選択され得る。このように、この例において、図１２に示すように、ＸがＹ未満であるか否かを決定する使用可能とされたアクション１０２０が選択される。即ち、アクション１０２０は、Ｘ及びＹを比較する。もしＸがＹ未満であるならば、記憶位置１０３２が真に設定され、そのタイムスタンプ１０３３が更新されて２に設定される。そうでない場合、アクション１０２０は失敗し、記憶位置１０３０が偽に設定され、その関連するタイムスタンプ１０３１が２に設定される。何れの場合にも、アクション１０２０は使用不能にされる。理由は、その使用不能記憶位置１０３０及び１０３２の一方がその使用可能記憶位置１０１０及び１０１２の全てよりもより最近のタイムスタンプを有するからである。
【０１１７】
この例では、図１２に示すように、選択されたアクション１０２０が完了し、記憶位置１０３２を真に設定し、タイムスタンプ位置１０３３を２に設定し、従って、アクション１０２４を使用可能とする。これは、図１２の時間３に関連して示される。
【０１１８】
次に、時間３において、使用可能とされたアクション１０４０がランダムに選択され、出力記憶位置１０５０がＸ記憶位置１０１０の値に設定され、そしてその関連するタイムスタンプ１０５７が３に設定される。従って、この時、出力記憶位置１０５０が有効データ、この場合は、３４を含む。このように、出力アクション１０４０はもはや使用可能ではない。
【０１１９】
このように、時間４で、唯二つのアクション、即ち、テスト関数アクション１０２６及び演算関数アクション１０２４が使用可能とされる。図１２に示されるように、時間４では、最後の関数アクション１０２６がランダムに選択される。ＹがＸ未満ではないので、選択されたアクションが失敗する。その結果、値偽が記憶位置１０３６に書き込まれ、その関連するタイムスタンプ１０３７が４に設定され、従って、選択されたアクション１０２６が使用不能とされる。
【０１２０】
しかしながら、その結果、時間５で、アクション１０２４のみが使用可能とされ、もちろん、それが選択される。結果として、Ｘ、即ち、３４がＹ，即ち、５１から減算され、得られた値、１７がＹ記憶位置１０１２へ記憶される。同時に、Ｙ記憶位置１０１２に関連するタイムスタンプ１０１３が５に設定される。これにより、時間６に関連して図１２に示されるように、アクション１０２０，１０２６及び１０４０の各々を再び使用可能にする。
【０１２１】
次に、時間７で、アクション１０２６がランダムに選択される。ＹがＸ未満であるので、選択されたアクション１０２６が終了する。従って、記憶位置１０３４が真に設定され、その関連するタイムスタンプ１０３５が７に設定され、従って、アクション１０２６を使用不能にする。
【０１２２】
次に、図１２に示されるように、時間８において、新たに使用可能とされたアクション１０２２がランダムに選択される。その結果、Ｙ、即ち、１７がＸ、即ち、３４から減算されて得られた１７がＸ記憶位置１０１０に記憶される。同時に、その関連するタイムスタンプ１０１１が８に設定され、従って、アクション１０２０，１０２６及び１０２４の全てを再び使用可能とする。
【０１２３】
次に、時間９において、再び使用可能とされた１０２０が選択される。しかしながら、この時、ＸがＹ未満ではない。アクション１０２０のテストが偽である。従って、使用不能記憶位置１０３０及びその関連のタイムスタンプ１０３１が更新され、従って、アクション１０２０を使用不能とする。次に、時間１０で、アクション１０２６がランダムに選択される。ＹがまたＸ未満ではないので、アクション１０２６が失敗する。これにより使用不能記憶位置１０３６及びその関連のタイムスタンプ１０３７が更新され、従って、アクション１０２６を使用不能にする。最後に、時間１１で、唯一残っているアクション、出力アクション１０４０が選択される。割り当てアクション１０４０がＸ記憶位置１０１０に記憶されている値を出力記憶位置１０５０へ出力し、その関連のタイムスタンプ１０５１を更新する。もはや使用可能アクションが無いので、依存性アクションシステム１０００が終了する。
【０１２４】
図９に示されるように、依存性アクションシステム１０００のこの実行は、もはや使用可能とされたアクションが無くなるまで進む。この点で、出力記憶位置１０５０の値が出力され、有効値として読み出されることができる。
【０１２５】
依存性アクションシステム１０００の実行は、非決定的であることが理解されるべきである。依存性アクションシステム１０００は冗長的決定を行うことができる、例えば、アクション１０４０は、適切な結果が達成される前でさえ複数回実行され得る。この特定の依存性アクションシステム１０００は、冗長関数構成要素を含まないが、このような構成要素が容易に含まれ得る。
【０１２６】
本発明の依存性アクションシステムは、選択ルールを使用して二つ若しくはそれより多くの使用可能とされたアクションの何れが次に実行されるべきかを決定する。依存性アクションシステム１０００の上述された実行はランダムな使用可能とされたアクション選択ルールを使用した。しかしながら、依存性アクションシステム１０００に対するより効率的な選択ルールがテストアクション１０２０及び１０２６よりも演算アクション１０２２及び１０２４を優先し、出力アクション１０４０より他のアクションを優先するかもしれない。
【０１２７】
ランダム選択ルールの代わりに、本発明の好ましい実施の形態は、選択ルールとして二つのアクションの内の一方を他方よりも優先すべきであることを指定する優先関係を使用する。このタイプの優先関係は、一旦決定されメモリに記憶される表により表される。この処理は、図１３乃至１６を参照して以下に説明される。表はもし依存性アクションシステムが変化しその時に再決定される。これは図１８に示されている。
【０１２８】
図１３は、優先関係に基づいてＳ１４３０の実行のための使用可能とされたアクションを選択する方法をより詳細に説明するフロー図である。図１３に示されるように、優先関係はすでに決定されている。従って、ステップＳ１４２０で開始されると、制御がステップＳ１４４０に進む。ステップＳ１４４０において、優先関係は、各使用可能とされたアクション毎に、そのアクションに優先する他のアクションが幾つあるかを決定するために解析される。次に、ステップＳ１４５０において、それに優先した他のアクションの最小数を有する使用可能アクションが実行されるべきアクションとして選択される。次に、ステップＳ１４５５において、制御がステップＳ１４６０にリターンする。
【０１２９】
図１４，１５及び１６は、優先関係を決定すための方法を詳細に説明するフロー図である。図１４は、優先関係を決定するための一般的手順を示す。図１４に示されるように、制御ルーチンはステップＳ１７００で開始し、ステップＳ１８００に続く。ステップＳ１８００において、有向グラフが構成される。次に、ステップＳ１９００において、この有向グラフは、選択されるために残っている有向グラフに少なくとも二つ非選択アクションがあるか否かを決定するためにチックされる。もし少なくとも二つの非選択アクションがあるならば、制御はステップＳ２０００に続く。そうでない場合は、少なくとも二つの非選択アクションが無いならば、制御はステップＳ２４００にジャンプする。ステップＳ１９００において、もし有向グラフに残っている非選択アクションが一つしかない場合、明らかにその非選択アクションが優先する他のアクションが無いので、二つの非選択アクションがチェックされる。
【０１３０】
ステップＳ２０００において、非選択アクションの一つが現在の第１のアクションとして選択されて、選択されたものとしてマークされる。次に、ステップＳ２１００において、残りの非選択アクションの一つが現在の第２のアクションとして選択される。次に、ステップＳ２２００において、有向グラフが現在の第１及び第２のアクションの内どちらが優先するかを決定するためにチェックされ、その結果がこれら二つのアクションに関する依存性アクションシステムのための優先関係に記憶される。次に、制御がステップＳ２３００に続く。
【０１３１】
ステップＳ２３００において、有向グラフは、前に現在の第２のアクションとして選択された非選択アクションを無視した後に残った他の非選択アクションがあるか否かを決定するためにチェックされる。もしそのような非選択アクションが残っているならば、制御は新たな現在の第２のアクションの選択の為にステップＳ２１００にジャンプして戻る。そうでない場合、有向グラフにまだ残っている少なくとも二つの非選択アクションがあるか否かを決定するためにステップＳ１９００にジャンプして戻る。
【０１３２】
ステップＳ２４００において、制御ルーチンがストップする。
【０１３３】
図１５は、ステップＳ１８００の依存性アクションシステムの有向グラフを構築するための方法を詳細に述べる。ステップＳ１８００で開始し、制御はステップＳ１８０５に進み、そこで依存性アクションシステムが依存性アクションシステムに残っている非選択アクションがあるか否かを決定するためにチェックされる。もし残っているならば、制御はステップＳ１８１０に進む。そうでない場合は、制御はステップＳ１８２０にジャンプする。
【０１３４】
ステップＳ１８１０において、依存性アクションシステムの非選択アクションの一つが現在のアクションとして選択される。次に、ステップＳ１８１５において、有向グラフの新たなグラフノードが現在のアクションの為に構築され、そのアクションと関連付けられる。次に、制御はステップＳ１８０５にリターンし、依存性アクションシステムにもはや非選択アクションが無くなるまでステップＳ１８０５乃至Ｓ１８１５をループするように続く。即ち、グラフノードが生成される必要があるアクションがもはや無くなると、制御はステップＳ１８２０に続く。
【０１３５】
ステップＳ１８２０において、ストップノードが生成されて有向グラフに追加される。次に、ステップＳ１８２５において、依存性アクションシステムは、残っている依存性アクションシステムの非選択記憶位置があるか否かを決定するためにチェックされる。もし残っているならば、制御はステップＳ１８３０に続く。そうでない場合は、制御はステップＳ１８８０にジャンプする。
【０１３６】
ステップＳ１８３０において、非選択記憶位置の一つが現在の記憶位置として選択される。次に、ステップＳ１８３５において、依存性アクションシステムは選択された記憶位置が使用不能記憶位置である非選択アクションがあるか否かを決定するためにチェックされる。もし少なくとも一つのそのような非選択アクションがあるならば、制御はステップＳ１８５０に続く。そうでない場合は、制御はステップＳ１８２５にリターンする。
【０１３７】
ステップＳ１８４０において、選択された記憶位置が使用不能記憶位置であるアクションの一つが現在のアクションとして選択される。次に、ステップＳ１８４５において、現在の記憶位置は、出力記憶位置であるか否かを決定するためにチェックされる。もしそうならば、制御はステップＳ１８５０に続く。そうでない場合は、制御はステップＳ１８６０にジャンプする。
【０１３８】
ステップＳ１８５０において、エッジは、現在のアクションに関連するノードからストップノードへのグラフに追加される。次に、ステップＳ１８５５において、重みがそのエッジに割り当てられる。この重みは、現在のアクションが現在の記憶位置を更新する確率により除算される現在のアクションのコストとして決定される。次に、制御はステップＳ１８６０に続く。
【０１３９】
ステップＳ１８６０において、依存性アクションシステムは、現在の記憶位置が使用可能記憶位置である依存性アクションシステムの非選択アクションがあるか否かを決定するためにチェックされる。もし少なくとも一つのそのような非選択アクションがあるならば、制御はステップＳ１８６５に続く。そうでない場合、制御は、再びステップＳ１８３５にリターンする。ステップＳ１８６５において、選択された記憶位置が使用可能記憶位置であるアクションの一つが次のアクションとして選択される。次に、ステップＳ１８７０において、エッジが現在のアクションに関連するノードから次のアクションに関連するノードまでのグラフに追加される。次に、ステップＳ１８７５において、重みがそのエッジに割り当てられる。その重みは、現在のアクションが現在の記憶位置を更新する確率により除算される現在のアクションのコストとして決定される。次に、制御はステップＳ１８６０にリターンする。
【０１４０】
図１６は、ステップＳ２２００に従って第１および第２のアクションの内どちらが優先されるべきかの決定を詳細に示す。ステップＳ２２００で開始して、制御はステップＳ２２０５に続く。ステップＳ２２０５において、第１のアクションに対応する、即ち、関連するノードからストップノードまでの距離がＤ１として定義される。次に、ステップＳ２２１０において、第２のアクションに対応する、即ち、関連するノードからストップノードまでの距離がＤ２として定義される。次に、ステップＳ２２１５において、依存性アクションシステムが第１のアクションがイーガーアクションであるか否かを決定するためにチェックされる。もしそうならば、制御はステップＳ２２２０に続く。そうでない場合は、もし第１のアクションがレイジーアクションであるならば、制御がステップＳ２２４５にジャンプする。
【０１４１】
ステップＳ２２２０において、依存性アクションシステムは、第２のアクションがまたレイジーアクションであるか否かを決定するためにチェックされる。もしそうであるならば、制御がステップＳ２２３０に続く。そうでない場合は、もし第２のアクションがイーガーアクションであるならば、第２のアクションが優先され、制御がステップＳ２２３５にジャンプする。
【０１４２】
ステップＳ２２２５において、距離Ｄ１及びＤ２は、Ｄ１がＤ２よりも小さいか否かを決定するために比較される。もしそうであるならば、第１のアクションが優先され、制御はステップＳ２２３０に進む。そうでない場合、第２のアクションが優先され、制御がステップＳ２２３５にジャンプする。
【０１４３】
ステップＳ２２３０において、第１のアクションは、第２のアクションに優先され、この優先がこれら二つのアクションに関連する依存性アクションシステムに対する優先関係に記録される。次に、制御はステップＳ２２４０にジャンプし、そこで制御がステップＳ２３００へリターンされる。反対に、ステップＳ２２３５において、第２のアクションが第１のアクションに優先され、この優先がこれら二つのに関連する依存性アクションシステムの優先関係へ記録される。次に、制御がステップＳ２２４０へ進む。
【０１４４】
ステップＳ２２４５において、依存性アクションシステムは、第２のアクションがまたイーガーアクションであるか否かを決定するためにチェックされる。もしそうであるならば、制御がステップＳ２２５０に進む。そうでない場合は、第２のアクションがレイジーアクションであるならば、第１のアクションが優先され、制御がステップＳ２２３０にジャンプする。
【０１４５】
ステップＳ２２５０において、第１のアクションに対応する、即ち、関連するノートから第２のアクションに対応する、即ち、関連するノードまでの距離がＤ１２として定義される。もし有向グラフにおいて第２のアクションに対応する、即ち、関連するノードが第１のアクションに対応する、即ち、関連するノードからのパスが届かない場合、距離Ｄ１２が無限であるとして定義される。次に、ステップＳ２２５５において、第２のアクションに対応する、即ち、関連するノードから第１のアクションに対応する、即ち、関連するノードまでの距離がＤ２１２１として定義される。もし有向グラフにおいて第１のアクションに対応する、即ち、関連するノードが第２のに対応する、即ち、関連するノードからのパスが届かない場合は、距離Ｄ２１が無限であると定義される。
【０１４６】
次に、ステップＳ２２６０において、距離Ｄ１２は、それが無限であるか否かを決定するためにチェックされる。もし距離Ｄ１２が無限でないならば、制御がステップＳ２２７０に進む。そうでない場合、もし距離Ｄ１２が無限であれば、制御がステップＳ２２７５にジャンプする。
【０１４７】
ステップＳ２２６５において、距離Ｄ２１は、それが無限であるか否かを決定するためにチェックされる。もし距離Ｄ２１が無限でない場合、制御がステップＳ２２７０に進む。そうでない場合、もし距離Ｄ１２無限であるならば、第２のアクションが優先され、制御がステップＳ２２３５にジャンプする。
【０１４８】
ステップＳ２２７０において、距離Ｄ１及びＤ２は、Ｄ１２がＤ２１未満であるか否かを決定するために比較される。もしそうであるならば、第２のアクションが優先され、制御がステップＳ２２３５へジャンプする。そうでない場合、第１のアクションが優先され、制御がステップＳ２２３０にジャンプする。
【０１４９】
ステップＳ２２７５において距離Ｄ２１は、それが無限であるか否かを決定するためにチェックされる。もし距離Ｄ２１が無限であるならば、制御がステップＳ２２８０に進む。そうでない場合、距離Ｄ１２が無限でないならば、第１のアクションが優先され、制御がステップＳ２２３０にジャンプする。
【０１５０】
ステップＳ２２８０において、依存性アクションシステムは、第１及び第２のアクションが共通の使用不能記憶位置を共有するか否かを決定するためにチェックされる。もし第１及び第２のアクションが共通の使用不能記憶位置を共有しないならば、制御がステップＳ２２８５に進む。ステップＳ２２８５において、距離Ｄ１及びＤ２は、Ｄ１がＤ２未満であるか否かを決定するために比較される。もしそうであるならば、第１のアクションが優先され、制御がステップＳ２２３０に進む。そうでない場合、第２のアクションが優先され、制御がステップＳ２２３０にジャンプする。そうでない場合は、第２のアクションが優先され、制御がステップＳ２２３５にジャンプする。
【０１５１】
第１及び第２のアクションが共通の使用不能記憶位置を共有するならば、制御がステップＳ２２９０にジャンプする。ステップＳ２２８５と同様に、ステップＳ２２９０において、距離Ｄ１及びＤ２は、Ｄ１がＤ２未満であるか否かを決定するために比較される。もしそうなら、第２のアクションが優先され、制御がステップＳ２２３５にジャンプする。そうでない場合、第１のアクションが優先され、制御がステップＳ２２３０にジャンプする。
【０１５２】
図１７は、図４に示された依存性アクションシステム２００から生成された有向グラフ３００を示す。図４のアクション２２０，２２２及び２４０は、夫々図１７に示された有効グラフ３００のノード３２０，３２２及び３４０に対応する。ノード３５０は、新たなＳＴＯＰ(ストップ)ノードである。これらのノードは、矢印されたグラフライン、即ち、“エッジ”により接続される。エッジは次の二つの条件下で存在する。１）記憶位置が一つのアクションを他の一つのアクションに“接続する”、即ち、記憶位置が一方のアクションに対して使用不能記憶位置であり、他方のアクションに対して使用可能記憶位置である時、又は２）アクションが出力記憶位置の値を生成する時、である。その場合、そのアクションに対応するノードからＳＴＯＰ(ストップ)ノードまでのエッジが有る。エッジの長さ、即ち、“重み”は、アクションが使用不能記憶位置又は出力記憶位置を変更する確率に対するアクションのコストの比率として定義される。
【０１５３】
図１７に示される有向グラフ３００は、図４に示される例示の依存性アクションシステム２００に対する図１５に示された方法に従って構成される。図４のアクション２２０，２２２及び２２４の各々毎に、夫々に関連するノード３２０，３２２及び３４０がステップＳ１８１５２従って再構成される。新たなＳＴＯＰノードがステップＳ１８７０に従って構成される。ノード３２０からノード３４０へのエッジ２３５がステップＳ１８７０に従って構成される。このエッジは、記憶位置２３２がノード３２０に関連するアクション２２０に対する使用不能記憶位置であり、且つノード３４０に関連するアクション２４０に対する使用可能記憶位置であるので、構成される。同様に、ノード３２２からノード３４０へのエッジがステップＳ１８７０に従って構成される。このエッジは、記憶位置２３２がノード３２０に関連するアクション２２２に対する使用不能記憶位置であり、且つノード３４０に関連するアクション２４０に対する使用可能記憶位置であるので、構成される。最後に、ノード３４０からＳＴＯＰノード３５０へのエッジ３４５がステップＳ１８５０に従って構成される。このエッジは、出力記憶位置２５０がノード３４０に関連するアクション２４０に対する使用不能記憶位置であるので、構成される。
【０１５４】
一般に、図１５に示される方法に従って構成されるグラフは、第１のノードに関連するアクションを実行することにより第２のノードに関連するアクションが使用可能とされるように記憶位置を変更できるならば第１のノードから第２のノードへのエッジを含む。第１のノードに関連するアクションが実行されることにより出力記憶位置を更新できるならば、第１のノードからＳＴＯＰノードへのエッジがある。
【０１５５】
図６に示される優先アクションを決定するためのが以下のように概略される。１）イーガーアクションが常にレイジーアクションに優先されるべきである。
２）両アクションがレイジーであるならば、最終ノードへの最短距離を有するものが優先される。
３）両アクションがイーガーの場合、
ａ）使用可能アクションサイクルにあるノードに関連するアクションに対して、一方のアクションから他方のアクションへの距離が他方のアクションから一方のアクションへの距離より小さいならば、その一方のアクションが他方のアクションに優先される。
ｂ）使用可能アクションサイクルにはないが、一方のアクションが他方のアクションへ到達できるアクションに対して、その他方のアクションから到達できるその一方のアクションを優先する。
ｃ）二つのアクションと関連するノード同士間にパスが無いが、それらのアクションが一つの共有しよう不能記憶位置を有する場合、最終ノードからの最小距離を有するノードに関連するアクションを優先する。
ｄ）そうでない場合、最終ノードからの最大距離を有するノードに関連するアクションを優先する。
【０１５６】
使用可能にされたアクション優先ポリシーは、使用可能にされたアクションの実行によりその使用不能記憶位置の一つを更新できる確率に基づく。異なる入力データで依存性アクションシステムを繰り返し実行することによりアクションが記憶位置Ｓを更新する確率Ｑ（ａｊ，ｓｉ）を決定できる。コストは、各アクションａｊと関連する。アプリケーションに応じて、時間、空間、品質等の異なるコスト基準であることが好ましい。コストデータは、システム挙動の観察や他の方法により決定され得る。確率Ｑ（ａｊ，ｓｉ）は、ステップＳ１８５５及びＳ１８７５で使用され、有向グラフにおける使用可能アクションａｉ，ａｊを表すノード間のエッジの重みを定義する。ここでａｊはｓｊにより次に使用可能とされるアクションである。
【０１５７】
アクションに関連する変更確率は、アクションの実行によりそのアクションに関連する記憶位置の幾つかを変更する確率である。各アクションに関連するコストと変更確率を更新することは、アクションに関連する更新されたコスト及び変更確率における変化が所定の基準を満足するか否かを決定することと、変化が所定の基準を満足するならば更新されたコストと変更確率に基づく新たな優先関係を計算することと、を含む。
【０１５８】
図１８は、依存性アクションシステム実行をダイナミックに更新する方法を示すフロー図である。図１０乃至１２に示される依存性アクションシステムの動作及び図１８に示される依存性アクションシステムのダイナミックな更新が同時に実行されることが理解されるべきである。その方法はステップｓ３０００で開始し、ステップｓ３１００に進み、そこで依存性アクションシステムがユーザにより提供された入力又は他のシステムにより提供された一つ若しくは複数の変化が発生したか否かを決定するためにチェックされる。そのような入力や変化が検出されると、制御がステップＳ３２００に進む。そうでない場合、制御がステップＳ３１００にリターンする。
【０１５９】
ステップＳ３２００において、依存性アクションシステムの実行は、中断される。ステップＳ３２００において、依存性アクションシステムの動作は、その実行中に何時でも中断でき、パラメータや使用可能とされたアクションの優先ポリシーが更新されることができ又依存性アクションシステムに関連する確率やコストを変更できる。次に、ステップＳ３３００において、ユーザ入力や他の入力や依存性アクションシステムに対する変更が依存性アクションシステムに対して行われる。
【０１６０】
ステップＳ３４００において、検出された入力は、依存性アクションシステムに対する変更がユーザ又は他のデータ入力により入力されたデータであるか否かを決定するためにチェックされる。もしそうならば、制御がステップＳ３５００に進む。そうでない場合、制御がステップＳ３６００に直接ジャンプする。ステップＳ３５００において、入力データは、適切な記憶位置に記憶され、使用可能及び／又は使用不能アクションのセットが更新される。次に、制御がステップＳ３６００に進む。
【０１６１】
ステップＳ３６００において、検出された変更は、それらが使用可能なアクション優先ポリシーを更新することを要求するか否かを決定するためにチェックされる。もしそうならば、制御がステップＳ３７００に進む。そうでない場合、制御がステップＳ３８００にジャンプする。ステップＳ３７００において、使用可能とされたアクション優先ポリシーが、図１４乃至図１６に関して上記されたステップＳ１７００乃至ステップＳ２４００に従って更新される。次に、制御がステップＳ３８００に進む。
【０１６２】
ステップＳ３８００において、依存性アクションシステムの動作はそれが中断された時点で再開される。しかしながら、依存性アクションシステムの更なる動作は、ステップＳ３５００及びステップＳ３７００でなされる更新に基づく。次に、制御がステップＳ３１００にリターンし、そこでダイナミックな更新手順が他のユーザ入力又は他の変化が検出されるまで待機される。
【０１６３】
ステップＳ３５００において、依存性アクションシステムのパラメータは、システムが実行されている間に、最初にシステムに入力されるかまたは更新される。この好ましい実施形態において、少なくとも記憶されたアクション、記憶位置とアクションとの間の依存性、初期記憶位置値、記憶位置属性、後述される変更確率、及び初期コスト値は最初にシステムに入力され、依存性アクションの実行中に更新され得る。しかしながら、記憶位置が何時での追加され得ると共に、再使用された記憶位置のみが削除され得る。
【０１６４】
表Ｉは、図１１のアクションと関連するコストとイーガー／レイジーを示す、及び表ＩＩは、図１１のアクションと関連する変更確率を示す。テストアクション１０２０及び１０２６は、夫々終了の５０／５０のチャンスを有する。演算アクション１０２２及び１０２４は、決して失敗しない。理由は、それらのアクションは、常にそれらの目標記憶位置を変更するからである。表ＩＩに示されるように、例えば、テストアクション１０２０（ＸＬ）が記憶位置１０３０(偽Ｘ（ＦＡＬＳＥ  Ｘ）の値を変える確率が５０％であり、テストアクション１０２２（ＸＬ）が記憶位置１０３２(偽Ｘ（ＴＲＵＥ  Ｘ）の値を変える確率が５０％である。
【表１】
0003965828.tif 000002
【表２】
0003965828.tif 000003
【０１６５】
図１９は、図１４及び図１５に従て構成されるグラフを示す。図１９は、表Ｉ及び表ＩＩに示される値に基づき、図１１のアクション同士間の確率とコスト関係を示す。この例において、表Ｉ及び表ＩＩに述べられたコスト及び確率に基づき、ノード間の全ての重み(長さ)が１である。
【０１６６】
表ＩＩＩは、図１９に示されるノードに対応するノード間で長さ、即ち、重み、として表される最小距離を示す。表ＩＩＩに示されるように、テストアクション１０２０（ＸＬ）から演算アクション１０２２（ＸＤ）へのパスの長さは、３の合計長さに対して、テストアクション１０２０（ＸＬ）から演算アクション１０２４（ＹＤ）までのパスの長さと、演算アクション１０２４（ＹＤ）からテストアクション１０２６（ＹＬ）までのパスの長さと、テストアクション１０２６（ＹＬ）から演算アクション１０２２（ＸＤ）までのパスの長さとの合計として決定される。これは、表ＩＩＩのＸＬを含む行とＸＤを含む列との交点の値に対応する。全ての他の対に対するパス長は、同様に決定される。しかしながら、表ＩＩＩにおいて、無限（∞）の長さ組み合わせが得られないことを意味する。
【表３】
0003965828.tif 000004
【０１６７】
表ＩＶは、アクション１０２０（ＸＬ），１０２２（ＸＤ），１０２４（ＹＤ），１０２６（ＹＬ），１０４０（ＳＯ）の各対毎に、図１６に従って決定される図１１の依存性アクションシステムに対する優先関係を示す表である。この表は、どのアクションが優先されるべきかを指定する。ＸＤは、ルール３ａによりＸＬに優先する。ＹＤは、ルール３ｄによりＸＬに優先される。これは、ＤＹからＳＬまでの距離がＳＬからＤＸまでの距離と等しいので、ルール３ａは適用されない。ルール３ａによりＸＬ、ＸＤ、ＹＤおよびＹＬはＳＯに優先される。上記ルールによりアクションＹＤとＸＤの選択及びアクションＹＬとＸＬの選択はランダムである。
【表４】
0003965828.tif 000005
【０１６８】
本発明は、上述された特定の実施形態と共に説明されたが、本発明は、当業者にとって多くの変化、変更、バリエーションが可能であることは明白である。従って、上述された本発明の好適な実施形態は例示を意図しているに過ぎず、本発明を限定するものではない。特許請求の範囲で画定される精神及び範囲から離れることなく種々の変更が可能である。
【図面の簡単な説明】
【図１】本発明の依存性アクションシステムを実施できるシステムのブロック図である。
【図２】（ａ）乃至（ｆ）は、アクションと使用可能及び使用不能位置を示す図である。
【図３】一つのアクションを含む例示の依存性アクションシステムを示す図である。
【図４】三つのアクションを含む例示の依存性アクションシステムを示す図である。
【図５】新たなアクション及び記憶位置のダイナミックな追加を含む例示の依存性アクションシステムを示す図である。
【図６】例示のイーガー依存性アクションシステムを示す図である。
【図７】例示のレイジー依存性アクションシステムを示す図である。
【図８】故障状態にあるイーガー依存性アクションシステムに対する代替の解決策を示す図である。
【図９】本発明の依存性アクションシステムの動作の一般事項を示すフロー図である。
【図１０】図９のステップＳ１３００及びステップＳ１４００を詳細に示すフロー図である。
【図１１】最大公約数関数を決定する単純な依存性アクションシステムのブロック図である。
【図１２】図１１に示された例示の依存性アクションシステムの実行のタイミング図である。
【図１３】優先関係に基づき図１０の実行のための使用可能とされたアクションを選択する好ましい方法を詳細に示すフロー図である。
【図１４】図１３で使用される優先関係を決定する好ましい方法を示すフロー図である。
【図１５】図１４の有向グラフを決定するための好ましい方法を詳細に示すフロー図である。
【図１６】図１４の二つのアクションの内のどちらが優先されるべきかを決定するための好ましい方法を詳細に示すフロー図である。
【図１７】図４に示される依存性アクションシステムに対応する図１５に示される方法に従って構成される有向グラフである。
【図１８】依存性アクションシステムのダイナミックな更新を示すフロー図である。
【図１９】表Ｉ及び表ＩＩに基づく重みを備える図１１に示される例示の依存性アクションシステムと関連する有向グラフである。
【図１】
0003965828.tif 000006
【図２】
0003965828.tif 000007
【図３】
0003965828.tif 000008
【図４】
0003965828.tif 000009
【図５】
0003965828.tif 000010
【図６】
0003965828.tif 000011
【図７】
0003965828.tif 000012
【図８】
0003965828.tif 000013
【図９】
0003965828.tif 000014
【図１０】
0003965828.tif 000015
【図１１】
0003965828.tif 000016
【図１２】
0003965828.tif 000017
【図１３】
0003965828.tif 000018
【図１４】
0003965828.tif 000019
【図１５】
0003965828.tif 000020
【図１６】
0003965828.tif 000021
【図１７】
0003965828.tif 000022
【図１８】
0003965828.tif 000023
【図１９】
0003965828.tif 000024