(57)【要約】本発明は、状態セルの複製をベースとした再構成可能な制御システムに関するものであって、多数の物理的状態セル（１）を具備し、これら状態セルどうしが互いに接続され、これにより、アプリケーションに関連したペトリグラフを物理的に形成しており、各状態セルが、ペトリグラフの各プレースに対応しており、状態セルが、トークンを受領し得るとともに、そのトークンを記憶することができ、さらに、そのトークンを伝送することができ、状態セルが、複数のコネクタからなる再構成可能なネットワークを使用して、互いに接続され、状態セルどうしの接続が、次なる状態への前進を意味しているようなトークンの伝送接続と；トークンの伝送を認証するための認証接続と；トークンを破壊するための破壊接続と；という３つのタイプの接続を有している。
2005527897.tif 000002
【特許請求の範囲】
【請求項１】
アプリケーションのうちの、実行すべき操作の実行計画を記述している制御部分を使用するためのシステムであって、
多数の物理的状態セルを具備し、
これら状態セルどうしが互いに接続され、これにより、前記アプリケーションに関連したペトリグラフを物理的に形成しており、
各状態セルが、前記ペトリグラフの各プレースに対応しており、
前記状態セルが、トークンを受領し得るとともに、そのトークンを記憶することができ、さらに、そのトークンを伝送することができ、
前記状態セルが、複数のコネクタからなる再構成可能なネットワークを使用して、互いに接続され、
前記状態セルどうしの前記接続が、次なる状態への前進を意味しているような前記トークンの伝送接続と；前記トークンの伝送を認証するための認証接続と；前記トークンを破壊するための破壊接続と；という３つのタイプの接続を有していることを特徴とするシステム。
【請求項２】
請求項１記載のシステムにおいて、
前記状態セルが、ペトリグラフを構築し得るよう、複数の基本動作を行い、
これら基本動作が、接続の選択と；新たな状態セルに対しての接続と；既存の２つの状態セル間の接続と；を有していることを特徴とするシステム。
【請求項３】
請求項１記載のシステムにおいて、
前記状態セルが、必要な前記コネクタの数を低減し得るようなさらなるタイプの接続を有していることを特徴とするシステム。
【請求項４】
請求項１〜３のいずれか１項に記載のシステムにおいて、
前記システム内において使用されている前記ペトリグラフの転置に際して、外部事象が導入されていることを特徴とするシステム。
【請求項５】
請求項１記載のシステムにおいて、
前記操作と前記状態セルとを関連付ける手段を具備し、
前記ペトリグラフ内を循環する前記トークンを前記状態セルが受領した時点で、前記操作が行われるようになっていることを特徴とするシステム。
【請求項６】
請求項５記載のシステムにおいて、
前記操作と前記状態セルとの前記関連付けが、再構成可能なデータバスを有したメモリによって、行われるようになっていることを特徴とするシステム。
【請求項７】
請求項１〜５のいずれか１項に記載のシステムにおいて、
前記各状態セルが、アクセス可能であるかあるいはアクセス不可能であるかを恒久的に認識することができ、これにより、前記システムが、前記各状態セルのアクセス可能状態またはアクセス不可能状態を検出し得るようになっていることを特徴とするシステム。
【請求項８】
請求項７記載のシステムの使用であって、
メモリキャッシュの形成に際して使用していることを特徴とする使用。
【請求項９】
請求項８記載の使用において、
同期的なまたは非同期的な並列コンピュータのためのメモリキャッシュの形成に際して使用していることを特徴とする使用。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ペトリグラフの使用をベースとした再構成可能な制御システムに関するものである。
【背景技術】
【０００２】
実行すべき操作の実行計画を記述する制御部分およびそのような操作を実行する操作部分という２つの部分へと分解し得るようなすべての処理は、本明細書においては、『アプリケーション』と称される。
【０００３】
本発明は、アプリケーションの制御部分を使用するためのシステムを提案する。本発明によるシステムは、様々な並列パラダイム（データや命令や作業の並列処理）に対して適合している。本発明によるシステムは、既存の様々なタイプの同期コンピュータや非同期コンピュータと一緒に使用することができる。
【０００４】
本発明は、アプリケーションの制御部分をモデル化するに際してペトリグラフを使用することを、ベースとしている。このタイプのモデルは、通常、ソフトウェアドメイン内において使用される。それは、参考文献［１］に記載されているように、アプリケーションに関する形式的チェックを行うための手段を構成するからである。また、ペトリネットワークは、論理コントローラのプログラミングのための基礎を形成する。特に、参考文献［２］に記載されているように、プログラム可能な論理コントローラ（ＰＬＣ）のための基礎を形成する。このモデル化の使用は、種々の問題点をもたらす。特に、このようなグラフのサイズは、アプリケーションのサイズの増大化につれて、かなり急激に増大化する。ＰＬＣは、通常、従来的コンピュータユニットに関連したソフトウェアソリューションをベースとしている。
【０００５】
本発明の目的は、物理的支持体上にペトリグラフを直接的に転置するためのシステムである。
【非特許文献１】James L. Peterson 氏による“Petri net theory and themodelling of systems”(1981, Practice Hall, ISBN: 0136619835)（参考文献［１］）
【非特許文献２】Gary Dunning 氏による“Introduction to programmable logiccontrollers”(second edition, 1998, Delmas, ISBN: 0827378661)（参考文献［２］）
【発明の開示】
【課題を解決するための手段】
【０００６】
本発明は、セルの複製をベースとした再構成可能な制御システムに関するものであって、各状態が、ペトリグラフの各プレースに対応していること、および、再構成によって、関連するペトリグラフのトポロジーをモデル化すること、を特徴としている。
【０００７】
有利には、セルが、３つのタイプの接続（伝送接続、認証接続、および、破壊接続）をもたらすことによって、ペトリグラフがモデル化される。セルは、ペトリグラフを構築し得るよう、複数の基本動作を行い、これら基本動作は、接続の選択と；新たな状態セルに対しての接続と；既存の２つの状態セル間の接続と；を有している。
【０００８】
有利には、各状態セルは、必要なコネクタの数を低減し得るようなさらなるタイプの接続をもたらす。システム内において使用されているペトリグラフの転置に際して、外部事象が導入される。
【０００９】
有利には、本発明によるシステムは、操作と状態セルとを関連付ける手段を具備し、ペトリグラフ内を循環するトークンを状態セルが受領した時点で、操作が行われるようになっている。操作と状態セルとの関連付けは、再構成可能なデータバスを有したメモリによって、行われる。
【００１０】
本発明によるシステムを使用することにより、システム内におけるアクセス不可能セルを検出することができる。
【００１１】
本発明によるシステムを使用することにより、メモリキャッシュを形成することができ、例えば、同期的なまたは非同期的な並列コンピュータのためのメモリキャッシュを形成することができる。
【００１２】
本発明によるシステムは、アプリケーションの制御グラフを動的に（言い換えれば、操作時に）変更し得る手段を提供するような再構成可能コンセプトを使用して、構成されている。再構成可能性により、アプリケーションの制御グラフを管理するためのハードウェア手段の使用を考慮することができる。このようなシステムを使用すれば、部分的にペトリグラフを導入することができる。これにより、アプリケーションのサイズに制限されることなく、アプリケーションを処理することができる。
【発明を実施するための最良の形態】
【００１３】
本発明は、ペトリグラフという形態の表現を使用してアプリケーションをモデル化することを提案する。本発明におけるペトリグラフは、以下の３つの基準を満たさなければならない。
−１つのプレースあたりにつき、ただ１つだけのトークンが存在すること。
−２つのトークンどうしが連結される場合には、それら２つのトークンを組み合わせることによって、単一のトークンが形成されること。
−１つのトークンが、複数のプレースへと伝送され得ること。
【００１４】
アプリケーションは、このようなペトリグラフによって、モデル化することができる。ペトリグラフ内の各プレースは、動作に対してリンクされることができ、２つのプレースの間の遷移は、制御事象によって認証される。このような制御事象を使用することにより、本発明によるシステム内において使用されているペトリグラフの中で、トークンを前進させることができる。そのような制御事象は、モデル化の対象をなすアプリケーションに応じて、様々なモジュールに起因することができる。例えば、制御事象は、センサからの出力や、算術論理演算ユニット（ＡＬＵ）の事象フラグ、とすることができる。
【００１５】
したがって、本発明は、ペトリグラフをモデル化し得る再構成可能なシステムを備えている。つまり、１つまたは複数のトークンが、事象の関数として、本発明によるシステム内を循環する。トークンを配置するプレースは、実行すべき動作を決定する。
【００１６】
ペトリグラフ内の各プレースは、本発明によるシステム内における基本セルに対応している。この基本セルは、以下においては『状態セル』と称されるものであって、
−トークンを受領することができ、
−トークンの到着によって活性化されるものであり、
−認証信号の到着によって活性化された場合には、トークンを他の状態セルへと伝送することができ、
−『リセット』要求の到着時には、トークンを伝送することなくそのトークンを破壊することができる。
【００１７】
各状態セルは、図１に示すように、トークン入力と破壊入力と認証入力とという３つの入力と；１つのトークン出力と；を備えている。
【００１８】
トークンは、状態セル内へと入力され、その状態セルの中に格納される。認証が起動されたときには、トークンは、出力に向けて伝送される。破壊が起動されたときには、状態セルからトークンが削除され、認証は、その時点で無効となる。
【００１９】
状態セルは、非常に大きな数でもって複製され、状態セルどうしは、複数のコネクタからなる再構成可能なネットワークを介して、互いに接続される。２つの状態セルの間においては、以下の３つのタイプの接続態様が存在する。
−伝送接続：次なる状態を示している。
−認証接続：トークンの伝送を認証するためのものである。
−破壊接続：トークンを削除するためのものである。
【００２０】
この場合、再構成においては、状態セルどうしを接続することにより、アプリケーションに関連したペトリグラフをモデル化する。
【００２１】
図２は、様々なタイプの接続を示している。すなわち、
１．伝送接続
２．認証接続
３．破壊接続
ここで、Ｅ−Ｊは、トークン入力を示しており、Ｓ−Ｊは、トークン出力を示しており、Ｄは、破壊を示しており、Ｖは、認証を示している。
【００２２】
ペトリグラフの転置に関する３つの例が、図３，４，５に示されている。
【００２３】
アプリケーションの制御部分を使用することにより、状態セル間の接続を行うことができる。本発明は、再構成可能な技術を使用して、アプリケーションの制御部分を、相互接続の形態に置き換えることを提案する。
【００２４】
第１の例（図３）は、状態セルを使用したペトリグラフの単純な転置とその使用を示している。この場合、転置に際しては、状態セルどうしを互いに接続することによって、トークン伝送経路を形成する（伝送接続）。
【００２５】
第２の例（図４）は、破壊接続の使用を示している。ペトリグラフ（左側）内においては、セル（２）がトークンを有している場合には、２つの事象が起こり得る。すなわち、
−Ｅ２：この場合には、トークンがセル（５）へと伝送される。
−Ｅ３：この場合には、トークンがセル（３）へと伝送される。
【００２６】
トークンは、セル（５）内とセル（３）内とにおいて、同時に存在することはできない。このペトリグラフは、破壊接続を使用しなければ、使用することができない。２つの事象のうちのどちらか（Ｅ２またはＥ３）が起こるとすぐに、他の事象を待っているトークンが、破壊される。すなわち、セル（５）とセル（３）とを、同時に認証することはできない。
【００２７】
第３の例（図５）においては、２つのペトリグラフが使用されていて、同期したものとされている。同期は、認証接続を使用して行われている。言い換えれば、セル（Ｂ）内をトークンが通過することによって、セル（２）から、セル（５）とセル（３）との一方または双方に対しての、トークンの通過が活性化される。
【００２８】
ペトリグラフの形成前には、セルは、完全に相互接続可能なものでなければならない。すなわち、接続すべき１つのセルは、他のすべてのセルに対して接続可能でなければならない。したがって、構造がＮ個のセルを有している場合には、図６ａに示すように、Ｎ２ 個のコネクタ（２）が必要となる。
【００２９】
必要なコネクタ（２）の数を制限するため、上述した３つのタイプの接続に対して、新たなタイプの接続が、追加される。状態セルは、図６ｂに示すように、マルチプレクサ（５）を使用することによって、トークンの入力と出力との間にわたる接続を形成するように、修正されている。この新たな接続は、状態セルをコネクタとして使用するための手段をもたらす。この新たなタイプの接続は、間接的なものと見なされ、必要なコネクタの数を制限することができる。各セル（１）は、限られた数のセルに対してのみ接続するだけで良く、各セルは、コネクタとして使用することができる。これにより、図６ｃに示すように、ネットワークの接続性を増強することができる。
【００３０】
例えば、図７は、間接的な接続を行っている状態セルに関しての、機能的使用を示している。
【００３１】
状態セル間における接続の形成は、自動化することができ、これにより、ペトリグラフの使用が容易なものとされる。これを得るために、各状態セルは、『基本動作』と称される基本的な動作を行うことができる。以下の４つの基本動作を使用することによって、ペトリグラフの形成を容易なものとすることができる。
−形成すべき接続の選択。
−自由な状態セルに対しての接続の形成。
−使用されている状態セルに対しての接続の形成。
−状態セルの解放（接続解除）。
【００３２】
これらすべての基本動作は、各状態セルによって行うことができる。しかしながら、基本動作の送出は、外部制御デバイスによって管理される。このコントローラ（外部制御デバイス）は、状態セルを管理する。特に、セルに対しての基本動作の送出を管理することによって、ペトリグラフを構築できなければならない。そのコントローラは、また、メモリキャッシュ（後述）として、本発明によるシステムの構造のためのハードウェア資源を放出する。
【００３３】
すべての状態セルは、命令を受領することによって、実行すべき基本動作を決定することができる。状態セルは、使用されていなければ、自由なセルとしてマーキングされ、また、使用されていれば、使用されているセルとしてマーキングされる。
【００３４】
第１基本動作においては、状態セルに対して、形成すべき状態セルの接続タイプを送出する。よって、各セルは、形成されるべき接続を記述した情報を有し得る必要がある。セルは、設定されるべき接続タイプ（伝送接続、あるいは、認証接続、あるいは、破壊接続）を記憶しなければならない。
【００３５】
第２基本動作においては、新たな状態セルを接続する。この接続を行う必要がある状態セルは、隣接している複数のセルの中から自由なセルを検索する。言い換えれば、直接的にアクセス可能な状態セルを検索する。自由なセルが見つかれば、接続を形成する。この場合、セルは、隣接する各セルに対して接続要求を送出し得るものでなければならず、また、隣接セルの状態が自由な状態であるかどうかをチェックし得るものでなければならない。よって、接続要求信号が、隣接セルに対して送出されなければならず、隣接セルは、自身の状態（自由な状態、あるいは、使用されているという状態）に特有の信号を供給しなければならない。
【００３６】
第３基本動作においては、２つの状態間において、自動的に接続を形成する。この基本動作は、図８に示したような、連続した３つのステップによって行われる。図８は、特に、複数の自由なセル（１０）と、複数の使用されているセル（１１）と、を示している。
【００３７】
１．互いに接続すべき２つの状態セルを、認識する。接続を形成しようとしている状態セルは、ソース（１５）と称され、接続の相手先をなす第２の状態セルは、目的地（１６）と称される。目的地セルは、自由なセルとしてマーキングされている。ソースセルと目的地セルとは別に、すべてのセルは、間接的な接続を形成する（図８（ａ））。
【００３８】
２．ソースセルから、隣接している自由なセルに対して、接続を形成する。この手順を、目的地セルが見つかるまで、新たに接続された各セルから繰り返す。このステップにおいては、各セルが、隣接したすべての自由なセルに対して接続し得ることが必要とされ、それら隣接したすべての自由なセルに対して同じ操作を課す（図８（ｂ））。
【００３９】
３．不要な接続を、破壊する。残っているすべての接続は、必要な接続である。目的地セルは、認証信号を送出し、これにより、この最終ステップを可能とする。この認証信号を受領しなかったすべてのセルは、接続解除することができる。重要なことは、不要な接続を破壊するよりも前に、ソースセルが、目的地セルから実際に確実に信号を受領することである。これにより、破壊すべき状態セルを、正確に把握することができる。したがって、この基本動作を行いつつ接続されることとなるセルは、目的地セルから信号を受領し得るものでなければならない（図８（ｂ））。
【００４０】
第３基本動作における各ステップは、セルによって実行される。しかしながら、一連をなすこれらステップは、上述したように、外部コントローラからの操作を必要とする。このプロセスを管理する機能グラフであって、外部コントローラ内に組み込まれなければならない機能グラフが、図９に示されている。図９は、以下のステップを順に示している。
−ソースセルと目的地セルとを初期化する（２０）。
−ソースセルから開始して、それまでに接続されたすべてのセルによって、隣接した自由なセルに対しての伝送接続を形成する（２１）。この操作は、目的地セルが得られるまで行う（２２）。
−待受を行う（２３）。この待受は、目的地セルからの信号をソースセルが受領するまで行う（２４）。
−ソース信号と目的地信号とを受領しなかったセルに関するすべての接続を解除する（２５）。
【００４１】
第４基本動作は、安全デバイスである。この安全デバイスは、自由なセルが無いことによってシステムが停止することを防止する。これにより、再使用のために、状態セルを解放することができる。
【００４２】
機構は、事象の取得および分散が可能であるようにして、構成される。これにより、図１０に示すように、本発明によるシステムに対して、事象を供給することができる。いくつかのセルは、このシステムにおいては、他の状態セルに対して接続できないようになっている。そのようなセルは、事象バス（３３）から直接的にトークンを受領し、『事象レシーバ』と称される。事象バスは、ペトリグラフ内における遷移に関連した信号組から構成される。認証接続は、このようなセルから形成することができ、これにより、構造に対して複数の事象を供給することができる。符号（３０）は、事象レシーバを示しており、符号（３１）は、使用されている状態セルを示しており、符号（３２）は、自由な状態セルを示している。
【００４３】
ペトリグラフ内における各プレースは、実行されるべき操作に対応している。したがって、デバイスは、状態セルに対しての操作に関連し得るようにして、構成されなければならない。したがって、各セルは、本発明によるシステムを備えた構造に対して、トークンの存在を信号によって送出し得る必要がある。同様に、各セルは、また、ペトリグラフ内におけるプレースのモデル化に際して使用されるときにも、信号を送出しなければならない。これにより、システムを、適切な操作に対応するように構成することができる。
【００４４】
そのような機構の１つの可能な使用は、図１１に示すように、メモリの使用をベースとすることができる。本発明によるシステム内の各セルは、メモリ隔室（４０）に関連している。これにより、トークンの位置と対応操作との間の関連性を構築することができる。よって、新たなセルに向けてトークンが移動するたびごとに、そのセルに関連したメモリ隔室が読み取られることとなる。同様に、セルが接続された場合には常に、対応操作情報を配置すべきメモリ隔室を見つけ出すことができる。よって、様々な操作者（図１１においては、操作者１〜４）に対して、同時的に、データまたは命令を送出することができる。
【００４５】
このメモリは、再構成可能なデータバス（４１）を有している。各メモリ隔室は、メモリ構成に関する情報（４２）を使用することによって、データバス中の、データが移送されることとなる部分を、選択することができる。各メモリ隔室に関連する構成は、データバス中の、移送に際して使用される部分を特定するような、２値コードである。よって、様々なメモリ隔室を、競合を起こすことなく、同時に活性化することができる。
【００４６】
このメモリに関連したペトリグラフの構造は、必ずしも同期している必要はないものの同期可能であるような複数の並列アーキテクチャーの制御を、管理するための手段をもたらす。ＳＩＳＤ（single instruction stream single data stream, 単一命令ストリームかつ単一データストリーム）処理、ＳＩＭＤ（single instruction stream multiple
data stream,単一命令ストリームかつ複数データストリーム）処理、および、ＭＩＭＤ（multiple instruction stream multiple data stream, 複数命令ストリームかつ複数データストリーム）処理、に関する例が、それぞれ、図１２，１３，１４に示されている。データは、符号（５０）によって示されており、命令は、符号（５１）によって示されている。
【００４７】
ＳＩＳＤ処理の場合には、２つのストリーム（データストリーム、および、命令ストリーム）が、グラフ内におけるトークンの伝搬によって生成される。これら２つのストリームは、ペトリグラフに関連して必要とされた事象を生成することによって処理を実行している操作者に対して、送出される。
【００４８】
ＳＩＭＤ処理の場合には、１つの命令ストリームが、生成されて、各操作者に対して送出される。ペトリグラフは、『並列的』なものとされている。そのため、複数のデータストリームが使用されて、対象をなすＳＩＭＤ構造の様々な操作者に対して入力される。
【００４９】
ＭＩＭＤ処理の場合には、各操作者をそれぞれ管理し得るよう様々なペトリグラフが存在する。各ペトリグラフを使用することによって、各操作者に関連した複数の命令ストリームと複数のデータストリームとが使用される。ペトリグラフどうしを、同期させることができる。これにより、複数の操作者を調和させることができる。
【００５０】
ペトリグラフの使用によって、ＳＩＭＤ処理またはＭＩＭＤ処理に際して、複数の操作者を同期させるためのコントローラを使用する必要性が排除される。ＭＩＭＤモードは、複数のグラフを並列的に記述しかつ閲覧し得るという可能性によって、得られる。この場合、上述した再構成可能なメモリを使用することにより、対象をなすＭＩＭＤ構造に適合しているような、並列的なデータストリームと並列的な命令ストリームとを生成することができる。
【００５１】
ペトリグラフは、再構成可能な構造上へと、動的に導入することができる。ペトリグラフ内におけるトークンの進展は、ペトリグラフの導入とは適合していない。例えば、グラフの全体は、複雑なアプリケーション内の構造上に、フィットしなくても良い。その場合、システムは、キャッシュのようにして機能する。すなわち、システムは、メモリ内のアプリケーションの残部内において、実行すべき操作を維持する。キャッシュの動作、および、従来的実施形態の例については、後述する。
【００５２】
次に、キャッシュに関する従来技術について説明する。これにより、ペトリグラフの物理的使用によってもたらされる利点を説明する。多数のシステムにおけるメモリ階層構成の動作原理は、キャッシュの使用をベースとしている。これらキャッシュは、同じ基本スキームに由来する。様々なメモリ階層アーキテクチャー間の差異は、使用されているキャッシュの数およびサイズに基づいており、また、格納されたデータの管理に基づいている。考慮されているシステムに応じて、１〜３個のキャッシュが存在する。キャッシュのサイズは、プロセッサからの距離が減少するにつれて減少する。したがって、プロセッサに対して、より近くに位置するキャッシュは、より高度な性能を有しており、コンピュータユニットに適合した動作周波数を有している。
【００５３】
図１５は、４つのレベルを有したメモリ階層構成を示している。このメモリ階層構成は、プロセッサ（５６）を起点とし、３つのキャッシュレベル（Ｌ１，５５；Ｌ２，５４；Ｌ３，５３）を経由し、中央メモリ（５２）へと、つながっている。まず最初に、プロセッサに対して最も近いメモリ内にデータまたは命令が存在しているかどうかが、チェックされる。要求されたデータが存在していない場合には、データが見つかるまで、メモリ階層内を下がっていく。キャッシュ内のデータ取込機構は、プロセッサに対して最も近いメモリ（キャッシュＬ１）の使用を容易なものとする。ここで、いくつかのプロセッサアーキテクチャーは、Ｌ１およびＬ２を有している。
【００５４】
キャッシュは、中央メモリのサブ部分を含有したメモリから構成されている。このメモリは、完全なアドレスのサブ部分によって、アドレッシングされる。アドレスの未使用部分を使用することにより、メモリ内のデータの認証を確認することができる。メモリは、キャッシュ内のデータと、中央メモリ内のデータの完全なアドレスを再構成するためのキーと、を有している。したがって、２つのキーを比較することは、データが正当なものであるかどうかを認識するための手段をなす。この機構により、絶対アドレスを、キャッシュアドレスに対して関連付けることができる。言い換えれば、１つのキャッシュアドレスは、互いに競合的なものと見なされる複数の絶対アドレスに対応することができる。キャッシュには、以下の２つの主要なファミリーが存在する。
−『直接的にマップ付けされたキャッシュ（Direct-mapped  cache）』。この場合には、キャッシュメモリは、中央メモリの直接的な部分集合である。このタイプのキャッシュは、競合的な複数のアドレスを管理しないことにより、制限される。
−『Ｎ通りに設定され関連付けされたキャッシュ（N-way set - associative cache）』。このタイプのメモリにおいては、図１６に示すように、同棲しているとともに複数の競合的アドレスを格納しているＮ個のメモリが存在する。『直接的にマップ付けされた』タイプのキャッシュは、Ｎが１である場合と等価である。
【００５５】
このメモリ階層構成は、以下の様々な問題点をもたらす。
−格納されたすべてのデータが、必ずしも使用されない。
−メモリに対するアクセス時間が増大する。
−様々なメモリ間における整合性という問題点。
−強制的な同期。
−データに対する順次的なアクセス。
【００５６】
ペトリグラフを直接的に使用することによって、上記問題点のいくつかを解決することができる。
−格納されたすべてのデータが関連性を有し、それらが使用される可能性がある。
−メモリに対するアクセスが、必ずしも順次的なものではない。複数のデータに対して同時にアクセスすることができる。
−同期システムにおいても、また、非同期システムにおいても、構造を使用することができる。同一の同期機構を有していない複数のシステムによって、構造を使用することができる。
【００５７】
本発明によるシステムは、キャッシュと一緒に使用することができる。アプリケーションに関連したペトリグラフは、大容量すぎてシステム内に含有し得ないものとすることができ、この場合には、複数の部分へと分解しなければならない。したがって、システム内に格納されているペトリグラフ部分は、アプリケーションの進展の関数として、動的に更新する必要がある。アプリケーションの実行時には、いくつかの状態セルに対しては、アクセスすることができない。このことは、これら状態セルが、もはや、トークンを受領し得ないことを意味している。各状態セルは、常にアクセス可能であるかどうかを認識している。したがって、アクセス不可能な状態セルを削除し得るデバイスが構築されることにより、いくつかの状態セルを解放して、グラフの残部を導入することができる。このデバイスは、状態セルの導入と除去とを平衡化させ得るものでなければならない。この機構は、状態セルの基本動作の定義時に、外部コントローラ入力内に組み込まれるべきである。状態セルは、上述した解除基本動作の使用によって、除去される。コントローラは、アクセス可能性に基づいて、また、状態セルの導入と除去との平衡を反映する基準に応じて、状態セルの除去を決定する。状態セルは、除去基本動作を使用して、除去される。例えば、自由な状態セルと使用されている状態セルとの間の比を一定に維持し得るようにして、除去を調節することができる。これにより、十分な経路ハードウェア資源を維持することができる。
【００５８】
各トークン伝送接続は、状態セルがアクセス可能であるかどうかを決定するための接続と関連付けられる。このような接続上を循環する情報は、考慮している状態セルの入力サイド上にトークンが存在しているかを反映する。状態セルの入力サイド上にトークンが存在している場合には、その状態セルは、アクセス可能である。そうでない場合には、その状態セルは、アクセス不可能なものと見なされる。図１７は、そのような機構を示している。図１７は、アクセス可能信号（６０）と、伝送接続（６１）と、アクセス不可能な状態セル（６２）と、トークン（６３）と、を示している。
【図面の簡単な説明】
【００５９】
【図１】状態セルに関する入力／出力を示す図である。
【図２】複数の状態セルの間における様々なタイプの接続を示す図である。
【図３】ペトリグラフの転置を示す図である。
【図４】トークンの破壊を使用したペトリグラフの転置を示す図である。
【図５】２つのペトリグラフの間における同期を示す図である。
【図６ａ】完全に接続されたネットワークを示す図である。
【図６ｂ】回路の短絡によって状態セルをコネクタとして使用し得る様子を示す図である。
【図６ｃ】間接的接続の使用によって低減された場合に必要な接続の数を示す図である。
【図７】状態セルの機能的使用の一例を示す図であって、記憶されたトークンが、伝送後に破壊される。
【図８】既存の２つの状態セルの間の接続に関する一例を示す図であって、ａ）は、ソースをなす状態セルと、目的地をなす状態セルと、のマーキングを示しており、ｂ）は、目的地をなす状態セルの検索を示しており、ｃ）は、不要な接続の破壊を示している。
【図９】２つのセルの間の自動的な接続に関しての一連をなす各ステップを示す図である。
【図１０】本発明によるシステムにおいて使用されているペトリグラフに対しての、事象の供給を示す図である。
【図１１】本発明によるシステムにおいて使用されているペトリグラフに関して、メモリ構造を示す図である。
【図１２】ＳＩＳＤ（single instruction stream single data stream, 単一命令ストリームかつ単一データストリーム）処理に関しての、本発明によるシステムの使用を示す図である。
【図１３】ＳＩＭＤ（single instruction stream multiple data stream, 単一命令ストリームかつ複数データストリーム）処理に関しての、本発明によるシステムの使用を示す図である。
【図１４】ＭＩＭＤ（multiple instruction stream multiple data stream, 複数命令ストリームかつ複数データストリーム）処理に関しての、本発明によるシステムの使用を示す図である。
【図１５】古典的なメモリ階層構成の一例を示す図である。
【図１６】『２通りの設定 − 関連づけ』タイプのキャッシュを示す図である。
【図１７】状態に対するアクセスを示す図である。
【符号の説明】
【００６０】
１  状態セル
２  状態セル
３  状態セル
５  状態セル
１０  自由なセル
１１  使用されているセル
４１  再構成可能なデータバス
６１  伝送接続
６２  アクセス不可能な状態セル
６３  トークン
【図１】
2005527897.tif 000003
【図２】
2005527897.tif 000004
【図３】
2005527897.tif 000005
【図４】
2005527897.tif 000006
【図５】
2005527897.tif 000007
【図６ａ】
2005527897.tif 000008
【図６ｂ】
2005527897.tif 000009
【図６ｃ】
2005527897.tif 000010
【図７】
2005527897.tif 000011
【図８】
2005527897.tif 000012
【図９】
2005527897.tif 000013
【図１０】
2005527897.tif 000014
【図１１】
2005527897.tif 000015
【図１２】
2005527897.tif 000016
【図１３】
2005527897.tif 000017
【図１４】
2005527897.tif 000018
【図１５】
2005527897.tif 000019
【図１６】
2005527897.tif 000020
【図１７】
2005527897.tif 000021
【国際調査報告】
2005527897.tif 000022
2005527897.tif 000023
2005527897.tif 000024
2005527897.tif 000025
2005527897.tif 000026
2005527897.tif 000027