"マルチタスクシステム上でのいくらかの相互依存タスクの実行方法であって、各タスクTに、前記タスクの現在の発生、及び前記現在の発生が依存する他のタスクTaのセットの発生を示す論理時刻ベクトルHを関連付けるステップと、もし第1のベクトルの全ての構成要素が第2のベクトルのそれぞれの構成要素より大きいか、あるいは第2のベクトルのそれぞれの構成要素に等しいと共に、前記第1のベクトルの少なくとも1つの構成要素が前記第2のベクトルのそれぞれの構成要素より完全に大きいならば、前記第1のベクトルが前記第2のベクトルより大きいと考えられるように、論理時刻ベクトルのセットに関する半順序を定義するステップと、前記半順序関係に従って、前記論理時刻ベクトルを比較するステップと、その論理時刻ベクトルが前記論理時刻ベクトルの他のどれよりも大きくないならば、前記タスクTを実行するステップと、前記タスクの新しい発生に関して、前記ベクトルの少なくとも1つの構成要素の値を増加させることによって、実行された前記タスクTの前記論理時刻ベクトルを更新するステップとを含むことを特徴とする方法。前記タスクの発生を実行するために満たされるべき条件の数を示す依存状態カウンタKを、各タスクに関連付けるステップと、前記タスクTの依存状態カウンタがゼロに到達する場合に前記タスクTの実行を計画するステップと、タスクTが実行された場合に、実行された前記タスクの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクTaの前記依存状態カウンタの値を減少させるステップと、実行された前記タスクTの前記論理時刻ベクトルを更新するステップと、実行された前記タスクの前記論理時刻ベクトルより小さい論理時刻ベクトルを有する各他のタスクTaに関して、実行された前記タスクTの前記依存状態カウンタの値を増加させるステップと、実行された前記タスクTの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクTaの前記依存状態カウンタの値を増加させるステップとを含むことを特徴とする請求項1に記載の方法。現在のタスクの前記論理時刻ベクトルHが、各可能なタスクと関連付けられた構成要素を含み、前記現在のタスクと関連付けられた前記構成要素が、前記現在のタスクの発生番号を含み、別のタスクと関連付けられた構成要素が、前記現在のタスクが実行され得る前に完了されるべきである前記他のタスクの発生を識別すると共に、ゼロの構成要素が、前記現在のタスクが前記ゼロの構成要素と関連付けられたタスクに依存していないことを示すことを特徴とする請求項1に記載の方法。完了されたタスクの前記ベクトルを更新するために、前記完了されたタスクと関連付けられた前記構成要素の値を増加させるステップと、もし前記完了されたタスクと関連付けられた前記構成要素がしきい値に到達したならば、各他の構成要素の値を増加させるステップとを含むことを特徴とする請求項3に記載の方法。前記ベクトルが、Mを法として定義される構成要素を有し、2つのベクトルXx0,x2,xnとYy0,y1,ynとの間の前記半順序関係が、0とnとの間のどのようなiにおいても、xi=yiまたはxi⊂yiであり、0とnとの間にxj⊂yjであるようなjが存在する時に限り、X<Yが真であるとして定義され、x<y及びy-x≦Sであるか、またはx>y及びM-xy≦Sである時に限り、関係x⊂yが真であり、Sが、2S<Mであるような整数であることを特徴とする請求項1に記載の方法。前記タスクが、2つの代替タスクを含み、そのうちの一方または他方が直前のタスクによって生成された結果に基づく実行のために選択可能であり、実行された前記代替タスクの前記ベクトルを更新するステップが、他の代替タスクの前記ベクトルを更新するステップを含むことを特徴とする請求項1に記載の方法。従って、良好な性能と動作安定性の両方を有するスケジューリング方法の必要性が存在する。この必要性は、マルチタスクシステム上でのいくらかの相互依存タスクの実行方法であって、各タスクに、前記タスクの現在の発生occurrence:生起、及び前記現在の発生が依存する他のタスクのセットの発生を示す論理時刻ベクトルlogicaltimevectorを関連付けるステップと、もし第1のベクトルの全ての構成要素が第2のベクトルのそれぞれの構成要素より大きいか、あるいは第2のベクトルのそれぞれの構成要素に等しいと共に、前記第1のベクトルの少なくとも1つの構成要素が前記第2のベクトルのそれぞれの構成要素より完全に大きいならば、前記第1のベクトルが前記第2のベクトルより大きいと考えられるように、論理時刻ベクトルのセットに関する半順序partialorderを定義するステップと、前記半順序関係partialorderrelationに従って、前記論理時刻ベクトルを比較するステップと、その論理時刻ベクトルが前記論理時刻ベクトルの他のどれよりも大きくないならば、前記タスクを実行するステップと、前記タスクの新しい発生に関して、前記ベクトルの少なくとも1つの構成要素の値を増加させることによって、実行された前記タスクTの前記論理時刻ベクトルを更新するステップとを含む方法によって解決される。実施例によれば、前記方法は、前記タスクの発生を実行するために満たされるべき条件の数を示す依存状態カウンタを、各タスクに関連付けるステップと、前記タスクの依存状態カウンタがゼロに到達する場合に前記タスクの実行を計画するステップと、タスクが実行された場合に、実行された前記タスクの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクの前記依存状態カウンタの値を減少させるステップと、実行された前記タスクの前記論理時刻ベクトルを更新するステップと、実行された前記タスクの前記論理時刻ベクトルより小さい論理時刻ベクトルを有する各他のタスクに関して、実行された前記タスクの前記依存状態カウンタの値を増加させるステップと、実行された前記タスクの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクの前記依存状態カウンタの値を増加させるステップとを含む。実施例によれば、現在のタスクの前記論理時刻ベクトルは、各可能なタスクと関連付けられた構成要素を含む。前記現在のタスクと関連付けられた前記構成要素は、前記現在のタスクの発生番号を含む。別のタスクと関連付けられた構成要素は、前記現在のタスクが実行され得る前に完了されるべきである前記他のタスクの発生を識別すると共に、ゼロの構成要素は、前記現在のタスクが前記ゼロの構成要素と関連付けられたタスクに依存していないことを示す。方法の実行を加速するために、プロセッサシステムは、2つのNmビットのデータワードの間の順序関係を示す比較出力を備えた、前記2つのデータワードのためのハードウェア比較器ユニットを備え得ると共に、前記比較器ユニットの機能は、第1のデータワードの可能な連続した値と関連付けられた行と、第2のデータワードの可能な連続した値と関連付けられた列とを含む論理テーブルによって表され、各行は、前記行と同じ値に関連付けられた前記列との交点において1を含むと共に、該1の後には、一連の0が続く。前記一連の0の後には、循環的に前記行を完成する一連の1が続いており、0の数が、各行に関して同じであると共に、前記データワードの最大値の半分より小さい。各ベクトルがNmの倍数である複数のビットを有する構成要素を含む、半順序関係に従った2つの前記ベクトルのための比較器は、キャリー伝搬端子carrypropagationterminal:桁上げ伝搬端子を通してチェーン状に接続された、複数の、上述のタイプの比較器ユニットと、2つの連続したユニットの前記キャリー伝搬端子の間に配置されると共に、ベクトルの構成要素の間の境界を定義する信号のアクティブ状態に応答して、前記連続したユニットの間の前記キャリーの伝搬を遮断するように構成されたゲートと、前記比較出力に配置されると共に、前記境界を定義する信号の非アクティブ状態に応答して、前記比較出力の状態を抑制するように構成されたゲートとを備える。実施例によれば、各ユニットは、前記ユニットに提示された前記データワードの相当性を示す相当性出力を備えると共に、前記比較器は、前記ユニットの全ての比較出力がアクティブであると共に、少なくとも1つのユニットの前記相当性出力が非アクティブである時に限り、アクティブ表示を設定するように構成されたロジックを備える。他の利点及び特徴は、代表的な目的のためにのみ提供され、そして添付の図面に表された、本発明の特定の実施例の下記の説明から更に明らかに明白になるであろう。マルチタスクシステムにおける、特にデータフロー処理のタスクにおけるタスクの発生の始まりにおいて満たされなければならない条件を追跡するために、本開示は、各タスクに関して、タスクの依存状態dependency:従属関係を表す論理時刻ベクトルlogicaltimevectorを保存することを提供する。これ以降、用語タスクは、処理ステップの一般的なセットを示す。専門用語であるタスクの実行またはタスクの発生は、特定のデータセットに関するタスクの実行のことを指す。データフロー処理において、同じタスクの連続した発生は、引き継ぐフローの連続するデータセットに関して実行される。論理時刻ベクトルは、各タスクと関連付けられると共に、タスクの現在の発生の依存状態dependency:従属関係を反映する。論理時刻ベクトルは、論文MRaynal及びMSinghal、Logicaltimecapturingcausalityindistributedsystems、IEEEComputer29、1996及びCFidge、Logicaltimeindistributedcomputingsystems、IEEEComputer24、1991において紹介されている。異なるdistinctチャネルを通してイベントを受け取った各処理が、原因として、それらの順序を付け直すことができるように、半順序関係partialorderrelationと関連付けられた論理時刻ベクトルが、1つの処理から別の処理に送信されたイベントの時期を定めるdate:時点、日時を定めるために使用された。すなわち、従来、論理時刻ベクトルは、イベントを識別すると共に、相対的にイベントの時期dateを定めるために、通常使用される。これ以降で理解されることになるように、この明細書では、論理時刻ベクトルは、いつタスクが実行され得るかを判定するために使用される。言い換えれば、論理時刻ベクトルは、タスクの実行順序を強制するconstrain:強要する、すなわち将来イベントを計画して実行するために使用される。論理時刻ベクトルのこの利用法は、データフロー処理の例と共に、下記で更に詳細に説明されることになる。図1は、基本のデータフロー処理を表す。タスクAは、データをタスクBに提供し、タスクBは、データを処理すると共に、結果をタスクCに提供する。この例では、それらのタスクは、3サイクルの深さを有するFIFOバッファを通してそれらのデータを伝達する。これらのタスクの実行の条件は、下記のとおりである。タスクAは、第1のバッファが満杯fullでない場合のみ実行し得る。タスクBは、第1のバッファが空emptyではないと共に、第2のバッファが満杯fullでない場合のみ実行し得る。タスクCは、第2のバッファが空emptyではない場合のみ実行し得る。図2は、タスクA、タスクB、及びタスクCの発生の間の依存状態を示すグラフである。それらの行は、タスクA、タスクB、及びタスクCに対応する。行の中の連続した円circleは、円の中に示されたように、同じタスクの連続した発生occurrence:生起に対応する。それらの列は、簡単にするために、タスクの各発生が1サイクルで完了すると仮定した場合の、連続した実行サイクルに対応する。矢印は、依存しているdependent:従属している発生を接続する。各矢印は、前に発生しなければならないことを意味する。すなわち、図示されたグラフにおいて、各矢印は、右を指し示すべきであり、それは、左を指し示すことができないと共に、垂直であり得ない。実線solidの矢印は、タスクの実行の順序によって与えられた依存状態を示す。点線の矢印は、バッファの制限された深さによって与えられた依存状態を示す。タスクAの第1の発生は、タスクBの第1の発生の前に実行されるべきであるので、そして、タスクBの第1の発生は、タスクCの第1の発生の前に起こらなければならないので、それらの発生は、1つの行から次の行まで、1サイクルを単位としてオフセットされる。図3は、ここで説明される方法に従ってタスクの各発生が論理時刻ベクトルによって分類されている図2のグラフを示す。論理時刻ベクトルは、各タスクと関連付けられると共に、タスクの各発生の終りに更新される。これらのベクトルの更新が、値を増加させることに対応するので、これらのベクトルは、更に、Hと表示されて論理的クロックと呼ばれ得る。分かりやすいように、各ベクトルもしくはクロックHがマルチタスクシステム上で実行可能な各タスクと関連付けられた構成要素を含む、理解するための最も単純な場合が説明される。論理時刻ベクトルの従来の使用の場合に、タスクの数と比較して構成要素の数を最適化するための技術が存在し、そのような技術がここで同様に適用できる。そのような技術の例は、[PASWard、Anofflinealgorithmfordimensionboundanalysis、Proceedingofthe1999IEEEInternationalConferenceonParallelProcessing、ページ128136]において説明されている。従って、図3では、それぞれタスクA、タスクB、及びタスクCに割り当てられた3つのベクトルHA、ベクトルHB、及びベクトルHCが存在すると共に、各ベクトルは、それぞれタスクA、タスクB、及びタスクCに割り当てられた3つの構成要素を有している。タスクTjと関連付けられたベクトルHTjのタスクTiと関連付けられた構成要素hiは、例えば、タスクTjの現在の発生の実行にとって必要なタスクTiの発生を含む。拡大解釈すれば、タスクTjと関連付けられた構成要素hjは、現在実行中のタスクTjの発生を含む。ゼロのnull:無効の構成要素が示すのは、ベクトルと関連付けられたタスクの現在の発生が、ゼロの構成要素と関連付けられたタスクに依存しないということである。例えば、実行サイクルt7に関して図3において確認されたように、タスクAに対応するベクトルHAの第1の構成要素は7を含み、それはタスクAの現在の発生である。タスクAのこの発生は、第1のバッファ図1が少なくとも1つの利用可能な場所を有すること、すなわちタスクBの第4の発生がメモリバッファからデータを消費したことを必要とし、ベクトルHAにおけるタスクBと関連付けられた第2の構成要素は4を含む。タスクBの第4の発生は、第2のバッファが少なくとも1つの利用可能な場所を有すること、すなわちタスクCの第1の発生がこのバッファからデータを消費したことを必要とし、ベクトルHAにおけるタスクCと関連付けられた第3の構成要素は1を含む。各ベクトルは、熟考した発生から他のタスクのそれぞれの最も近い発生まで矢印を後ろにたどることによって、グラフから組み立てられる。従って、ベクトルHBは、時刻t7において、6,6,3を含むと共に、ベクトルHCは、5,5,5を含む。もし後ろにたどるべきそのような矢印が存在しないならば、その構成要素は、ゼロnull:ヌルであり、それは、タスクA及びタスクBの第1の発生に関する場合である。ベクトルの構築は、タスクを実施するアプリケーションプログラムの実行において達成することが容易である。ある発生タスクAに関する6番目、タスクBに関する3番目、タスクCに関する1番目を越えると、各構成要素は、関連するタスクの各実行で系統的に値が増やされるように思われる。それは、初期値を前もって定義すると共にベクトルの条件を更新するために十分であり、初期値を前もって定義すると共にベクトルの条件を更新することは、タスクの依存状態を記述するグラフの種類に応じてコンパイラによって実行され得る。これらの条件は、k番目の発生から始まるベクトルXの増分構成要素xiの形式で表される。それらのベクトルは、共有メモリに保存されると共に、各タスクがアプリケーションにより記録されるスケジューラによって、更新される。例えば、図3におけるベクトルHAの初期値及び更新条件は、下記のように定義され得る。ここで、そのような論理時刻ベクトルを有効に利用するために、半順序関係がこれらのベクトルのセットに関して定義される。2つのベクトルXx0,x2,xnとYy0,y1,ynとの間の半順序関係は、0とnとの間のどのようなiにおいても、xi≦yiであり、0とnとの間にxj<yjであるようなjが存在する時に限り、X<Yが真であるとして定義される。この順序関係は、それが全てのベクトルを順序付けるとは限らないので、半partial:部分的な、不完全なと呼ばれている。いくらかの場合において、ベクトルX及びYは共通点がなく、それはX||Yによって示される。ここで、タスクTaが実行を待っていると共に、現在の時刻にこのタスクが実行され得るかどうかを判定する必要があると仮定する。この判定のために、タスクTaの現在のベクトルが、他のタスクの現在のベクトルのそれぞれと比較される。他のタスクTが何であっても、次の条件が満たされさえすれば、タスクTaは実行され得る。条件は、更に、下記のように示されることになる。もし少なくとも1つの他のタスクTがHTa>HTを与えるならば、全ての条件がタスクTaを実行するために満たされているとは限らず、従って、タスクTaは待つべきである。単純化した場合に対応する図3のグラフにおいて、3番目からの各列におけるベクトルは、ペアによってペアごとに比較不能であるように思われる。これは、各々の対応するタスクが並列に実行され得ることを意味する。第1の列は、タスクAのみが実行され得ることを意味するHC>HB>HAを形成する。第2の列は、タスクAとタスクBは並列に実行され得るが、しかしタスクCは待たなければならないことを意味するHC>HB、HB||HA及びHA||HCを形成する。更に現実的な状況において、タスクは多かれ少なかれ遅れて到着すると共に、それらは多かれ少なかれ実行するのに時間がかかる。図4は、更に現実に近い状況を例証するように修正された図3のグラフを示す。タスクBの最初の2つの発生は、他の発生の長さの2倍持続する。それに続いて、タスクCの最初の発生は1サイクルの遅延で始まり、タスクCの第2の発生は、2サイクルの遅延で始まると共に、タスクAの第5の発生は、1サイクルの遅延で始まる。タスクの論理時刻ベクトルは、関連するタスクの実行のために必要とされるサイクル数の間変わらないままであり、それはタスクBの最初の2つの発生に関して見られ得る。タスクが終了するときに、ベクトルは更新される。従って、第5列におけるタスクA及びタスクBに関して見られるように、ベクトルの新しい値は関連するタスクの終りに有効になると共に、タスクの新しい発生を待っている間は変わらない。これは、タスクB及びタスクCの最初の発生の実行を待っている間も同様である。論理時刻ベクトルの利用法は、このグラフによって更によく理解されるであろう。第3の列は、HC>HBを形成する。従って、図3の場合と異なり、タスクCは、まだ開始し得ない。タスクCは、第4の列において開始し得ると共に、ここで、それらのベクトルは、ペアによってペアごとに比較不能になる。第5の列は、HA>HB及びHC>HBを形成する。従って、タスクA及びタスクCは、タスクBが実行する間待たなければならない。タスクA及びタスクCは、第6の列において実行され得ると共に、ここで、それらのベクトルは、ペアによってペアごとに比較不能になる。グラフがこのように無限に伸びると共に、従って、あらゆる遅延を有するあらゆる長さの発生に適合し得ることは明白である。これは、デッドロックがないことを保証する。以前に言及されたように、論理時刻ベクトルは、構成要素の系統的な値の増加によって更新される。構成要素が無限になることは実際には考えられない。むしろ、構成要素の折り返しfolding:ひだ形成メカニズムが、整数の部分集合subsetに適した半順序に基づいて提供される。ベクトルの構成要素は、従って、Mを法として定義されると共に、2つのベクトルXx0,x2,xnとYy0,y1,ynとの間の半順序関係が、どのようなiにおいても、xi=yiまたはxi⊂yiであり、xj⊂yjであるようなjが存在する時に限り、X<Yが真であるとして定義され、x<y及びy-x≦Sであるか、またはx>y及びM-xy≦Sである時に限り、関係x⊂yが真であるとして定義される。M及びSは、2S<Mであるような整数であると共に、Mは、ベクトルの構成要素の間の最大のオフセットより大きい。図3の場合は、7番目の発生が提供するベクトルHAに関して、最大のオフセットは6である。この最大のオフセットは、全ての初期条件が考慮される瞬間から、すなわち全てのベクトルの全ての構成要素の値が増加される瞬間から判定される。図3の例では、M=8及びS=3において、ベクトルの構成要素は値7から折り返される。タスクAに関するグラフの最後の2つのベクトルは、従って、0,5,2及び1,6,3によって表されると共に、タスクBに関するグラフの最後のベクトルは、0,0,5によって表される。各構成要素の8つの可能な値を円周上に置くと、上記のように定義されたより小さいという関係である⊂による構成要素の比較は、値xが、円周上後に続く3個S個の値のそれぞれより小さく、そして、前にある4個M-S-1個の値のそれぞれより大きいようになる。一例は下記のようになる。上記で示された方法論によれば、タスクが実行され得るかどうかを判定するために、各実行サイクルで、各タスクの論理時刻ベクトルは、他のタスクの各々のベクトルと比較される。タスクの数が増える場合、これはかなりの計算資源に相当するrepresent:を表すと共に、タスクの数によって、比較の数は二次的に増加する。更に、たとえタスクが実行され得ることを比較の結果が示すとしても、タスクが利用可能な計算資源を与えられてすぐに実行されることができないことは起こり得るこの状況では、タスクは実行可能と言われる。。実行可能なタスクのリストを管理することが、従って必要であり得る。計算資源を減少させるために、そして実行可能なタスクの計画を促進するために、Kで表示されると共に、タスクが実行可能になる前に満たされるべき条件の数を内容が代表する依存状態カウンタが、各タスクに関連付けられる。実際には、カウンタの内容は、まだ満たされていない条件の数と等しくなり得ると共に、その内容がゼロの状態になる場合に、そのタスクは実行可能になる。依存状態カウンタを更新するために、下記の手順が適用され得る。システムの初期化において、HT:=H0T及びKT:=0とし、ここで、H0Tは、タスクTに関する開始ベクトルであり、例えば、図3の例では、タスクAの場合1,0,0であり、タスクBの場合1,1,0であり、タスクCの場合1,1,1である。その場合に、スケジューラプロセスは、依存状態カウンタの内容を監視すると共に、カウンタがゼロである各タスクの実行を開始するか、または、並列にタスクを実行するための資源が不十分であるならば、これらのタスクの実行を計画する。タスクTが終了するときはいつでも、下記の4つのステップが、原子的にatomically、すなわちタスクの新しい発生が実行される前に、実行される。1.HTa>HTを有する各他のタスクTaに関して、KTa:=KTa-1を実行する。すなわち、ちょうど終了したタスクTは、各々のこれらのタスクTaが実行可能になる条件の内の1つを満たす。2.タスクTの新しい発生に関してベクトルHTを更新する。以前に言及されたように、これは、発生の数が初期条件における構成要素に関するしきい値のセットに到達する場合に、ベクトルの各構成要素の値を増加させることによって達成され得る。3.HT>HTaを有する各他のタスクTaに関して、KT:=KT1を実行する。すなわち、タスクTの新しい発生の実行に関する全ての条件が識別されると共に、それらは、タスクTの依存状態カウンタにおいて明らかにされる。4.HTa>HTを有する各他のタスクTaに関して、KTa:=KTa1を実行する。すなわち、タスクTの新しい発生によって生成された新しい条件が、他のタスクTaに関して識別されると共に、それらは、これらの他のタスクの依存状態カウンタにおいて明らかにされる。依存状態カウンタは、ハードウェアにおいて実現され得ると共に、ゼロ内容検出器nullcontentdetectioncircuitによって、並列にinparallel:同時に監視され得る。論理時刻ベクトルは、前述の規則に従ってカウンタの値を増加させると共に減少させるように構成されたハードウェア比較器に連結された、専用のレジスタに保存され得る。当然ながら、システム上で実行されるべきアプリケーションに含まれる多数の異なるタスクを処理するための、ベクトル専用の十分な量のハードウェアカウンタ及びレジスタが、提供されることになる。この場合、システムソフトウェアスケジューラは、専用のレジスタ内のベクトルの更新のみに関与するのみを担当すると共に、カウンタの比較及び更新はハードウェアアクセラレーションhardwareacceleration:ハードウェアの加速によって実行される。例えば、依存状態カウンタは、差し迫ったimminent実行の指標indicator:インジケータであると共に、それらは、従って、データプリフェッチprefetch:先取り動作を制御するために使用され得る。更に、比較の数はタスクの数によって直線的に増加するように思われる。図5は、2つの代替のタスク実行を有するデータフロー処理dataflowprocessにおけるタスクの系列の更に複雑な例を示す。図1のタスクBは、ここでは、2つのタスクB及びタスクB’を含み、タスクAが終了するときに、それらの内の1つが実行のために選択される。タスクAの発生によって生成された各データワードは、選択要素selectionelementSELを通して、タスクB及びタスクB’の内の1つに経路指定される。その選択は、同様にタスクAによって生成されると共に、タスクA、タスクB、及びタスクCの間に配置されたFIFOと同じ深さのFIFOに入れられる制御ワードCTLによって操作される。この制御ワードCTLは、タスクCへの供給のために、アクティブなタスクBまたはアクティブなタスクB’の出力を選択する結合要素mergeelementMRGによって、同時に取り入れられる。図6は、図3のグラフのようにタスクの発生が同じ長さを有すると共に遅延を有さないと仮定された、図5のケースに対応する依存状態のグラフである。論理時刻ベクトルの値は、発生を表すノードの中に示される。ベクトルは、ここでは、4つの構成要素を有している。更に、8を法として定義された構成要素を有する、折り返されたベクトル表記法が使用される。明瞭にするために、必ずしも全ての依存状態の矢印が示されるとは限らない。各タスクの第1の発生及び第4の発生からの矢印のみが示されると共に、他の矢印のセットが1つの発生から次の発生までのコピーであるということがわかる。依存状態は、図3におけるタスクBの発生に到着する矢印、または図3におけるタスクBの発生から離れる矢印は、ここでは、タスクBとタスクB’のそれぞれに複写されることを考慮して、図3のグラフに関する方法と同じ方法で組み込まれる。更に、矢印が、タスクBの各発生からタスクB’の次の発生に向けて離れると共に、矢印が、タスクB’の各発生からタスクBの次の発生に向けて離れる。図5のフローの特殊性は、タスクB及びタスクB’の内の1つだけがタスクAとタスクCとの間で実行されることである。上記で説明された方法論においてこれを考慮するために、これらの2つのタスクの内の1つが実行されるたびに、タスクBとタスクB’の両方が同時に実行されると仮定されている。すなわち、タスクBまたはタスクB’の各実行において、両方のタスクのベクトルが更新されると共に、依存状態カウンタKを使用する場合に、両方のタスクのカウンタが同様に更新される。図7は、図6のグラフによる処理の代表的な実行トレースを示す。実線のノードは、実行されつつあるか、もしくは実行されたタスクの発生に対応する。点線のノードは、実行を待つ発生に対応する。依存状態の矢印だけが、発生の実行の終りにおいて、すなわちベクトルH及びカウンタKが計算されるときに現れる。各ノードは、値が上記で説明された4つの原子的なatomic:分割できない、極小のステップを通して更新される論理時刻ベクトル及び依存状態カウンタKの対応する値correspondingvalueを含む。タスクA、タスクB、タスクB’、及びタスクCのカウンタKの初期値を決定するために、各タスクが完了されたということ、そしてベクトルHがその初期値に更新されたということが仮定されている。カウンタ更新ステップ3を各タスクに適用する際に、カウンタは、それぞれ、0、1、1、及び3に初期化される。開始時に、タスクAの3つの発生が、連続3サイクルにわたって実行される。これらの発生の第1の発生は、完了するために3つのサイクルを要するタスクBの第1の発生を開始する。ベクトル及び依存状態カウンタの観点から、タスクB’の第1の発生がタスクBの第1の発生と同時に進行すると考えられる。タスクAの第4の発生、タスクB/タスクB’、実際にはタスクB’の第2の発生、及びタスクCの第1の発生は、第5のサイクルにおいて開始し得る。タスクB及びタスクB’が同時に第4のサイクルで終了すると見なすと、第5のサイクルのタスクCのカウンタKは、カウンタ更新ステップ1を、1度はタスクBのために、そして1度はタスクB’にために、2回適用することによって、2だけ値が減少される。タスクAの第4の発生は6サイクルを要し、タスクB’の第2の発生は1サイクルを要し、タスクCの第1の発生は2サイクルを要する。第8のサイクルにおいて、タスクAの第4の発生がまだ進行中である一方、タスクB/タスクB’実際にはタスクBの第3の発生が終わり、そしてタスクCの第2の発生が開始されている。タスクB/タスクB’実際にはタスクB’の第4の発生は、タスクAの第4の発生が完了することになる第11のサイクルを待つ。今までのところ説明されたタスク実行の例において、カウンタ更新ステップ4の使用は、明らかにされなかった。図8は、ステップ4が有益である2つのタスクA及びBの実行の単純な例のトレースである。図7と同じ表現の慣例が使用される。タスクAの各発生は、3つのデータワードを生成し、それらの各々は、タスクBの異なるdistinct発生によって消費される。更に、タスクAとタスクBとの間のFIFOが3つのデータワードの深さを有しており、タスクAの各発生がFIFOで利用可能な空間の全てを必要とすると仮定されている。従って、タスクAの第2の発生は、タスクBの第3の発生が最終的にFIFOの空間を解放するまで、開始し得ない。ここでは、タスクAの発生を開始することがタスクBの3つの連続した発生の実行に支配されるので、ベクトルHAの第2の構成要素が、タスクAの発生の各実行において、3だけ値を増やされる点に注意が必要である。更に、ベクトルHBの第1の構成要素が、タスクBの発生の毎回の第3の実行の後で値を増やされる点に注意が必要である。これは、タスクBの3つの連続した発生がタスクAの同じ発生に支配されることを示す。タスクBの第1の発生の終りに4つの依存状態カウンタの更新ステップを適用することは、T=B及びTa=Aとして、下記の関係を形成する。1.HA=2,3>HB=1,1=>KA:=KA-1=0;2.HB:=1,2;3.HB>HAが偽であり、KBは変化しないままである。4.HA=2,3>HB=1,2=>KA:=KA1=1、ステップ1において一時的に変更されたKAのオリジナルの正しい値が回復される。これらの4つのステップは、ステップ1が提供するKの一時的な値がステップ4においてオリジナルの値に回復されると共に、作動可能タスクのリストに影響を及ぼさないように、原子的にatomically実行される。カウンタ更新ステップ1、3、及び4のそれぞれにおいて、N-1個の論理時刻ベクトルの比較が実行され、ここでNはタスクの数であり、各ベクトルの比較は、N個のベクトル構成要素まで、2つずつ比較することを必要とする。構成要素の比較の数は、従って、タスクの数によって二次的に増加する。これらの操作は、スケジューラプロセスによってソフトウェアにおいて実行され得るが、しかし、ソフトウェアリソースを節約するために、これにハードウェアのサポートを提供することが望ましいであろう。半順序を使用する比較演算、及び好ましい実施例において折り返しによって抑制された構成要素に、従来のデジタル型比較器は適当ではない。図9は、これらのニーズを満たし得る、論理時刻ベクトルHA及びHBに関する比較器の実施例の第1の反復の要素を示す。論理時刻ベクトルは、抑制されたビットの数Nv、例えば64ビットで定義されるということ、そして、このベクトルの各構成要素が、最小値Nm、例えば4ビットの倍数であるプログラム可能なビットの数で定義され得るということが仮定されている。この数Nmは、ベクトルの構成要素の最大の数を決定する。従って、64ビットのベクトル、及び構成要素当たり4ビットの最小値に関して、多くても16個の4ビットの構成要素、そして4ビットの倍数によって定義されたより少ない構成要素を有するあらゆる組み合わせを定義することができる。図9の比較器は、チェーン状に接続された一連の比較器ユニット10を備える。各ユニット10は、2つのベクトルHA及びHBから比較するために、2つの4ビットの構成要素を処理する。各ユニット10は、その外部端子に関して、入力Aと入力Bの2の補数~B1とを合計する減算器に基づく比較器に関連付けられ得る。従って、ユニット10は、比較されるべき構成要素のそれぞれのための入力に加えて、キャリーcarry:桁上げ入力Ci、キャリーcarry:桁上げ出力Co、A=Bであるかどうかを示す出力E、そしてA≧Bであるかどうかを示す出力GEを備える。第1のアプローチとして、説明を単純化するために、ユニット10が従来の比較器であると考える。更に下記で論じられたように、ユニットの論理テーブルは、折り返された値を比較するために修正されることになる。2つの64ビットワードの比較器を構築するように、ユニット10は、それらのキャリーcarry:桁上げ出力Co及びキャリーcarry:桁上げ入力Ciによってチェーン状に接続される。ベクトルの構成要素の間の境界がANDゲート12を用いて定義されるように、ゲート12は、ユニットの各キャリー出力Coと次のユニットのキャリー入力Ciとの間に配置される。第1のユニットのキャリー入力は、0を受け取るキャリーが考慮されない。各ゲート12は、アクティブ状態1が構成要素の間の境界を定めるそれぞれの信号SS0,S1,S2...によって制御される。信号Sのアクティブ状態は、ゲート12を遮断し、それによって、対応するユニット10のキャリーは次のユニットに送られず、そして、次のユニットは、比較を伝搬させず、次のユニットは従って独立した比較を行う。非アクティブであるアクティブでない信号S0は、ゲート12を開くと共に、キャリーの伝搬を可能にすることによって、2つのユニット10をチェーン状に接続させる。これらの2つのユニットは、従って、同じベクトルの構成要素と関連付けられる。図9の描写において、もし4つの信号Sが非アクティブである場合、4つのユニット10は、単一の16ビットの構成要素と関連付けられる。もし信号S1及びS3がアクティブであるならば、ユニットは、2つの異なる8ビットの構成要素と関連付けられる。もし信号Sの全てがアクティブであるならば、各ユニットは、異なる4ビットの構成要素と関連付けられる。更に、各信号Sは、対応するORゲート14の反転入力に印加されると共に、ORゲート14の第2の入力は、対応するユニット10の出力GEを受け取る。信号Sが非アクティブであるときに、ゲート14は、ユニットの出力GEを伝搬させないと共に、この出力は、無視され得る中間の比較結果に対応する。信号Sがアクティブであるユニットのみ、その出力GEが対応するゲート14によって伝搬されることが分かると共に、この出力は、現在のユニット及びチェーン状に接続された前のユニット信号Sが非アクティブであるユニットによって生成された比較結果を統合する。ゲート14の出力は、ANDゲート16に到達すると共に、もし全てのユニット10の出力GEがアクティブになるならば、すなわち、ベクトルHAの各構成要素がベクトルHBの対応する構成要素より大きいか、またはベクトルHBの対応する構成要素に等しいHA≧HBならば、従って、その出力はアクティブになる。信号S=0によって遮断されるゲート14の出力は、実際には1になり、従って、それらは、他のゲート14の出力に影響を及ぼさない。反転されたユニット10の出力Eは、ORゲート18に到達する。従って、出力Eの内の少なくとも1つが非アクティブであるならば、すなわち、ベクトルHA及びベクトルHBの少なくとも一組の構成要素に関して不均衡が存在するならばHA≠HB、ゲート18の出力はアクティブになる。ゲート16及びゲート18の出力は、ANDゲート20に到達する。従って、もしベクトルHAの全ての構成要素が、ベクトルHBのそれぞれの構成要素より大きいか、あるいはベクトルHBのそれぞれの構成要素に等しくゲート16がアクティブ、そしてベクトルHAとベクトルHBの少なくとも2つのそれぞれの構成要素が等しくない従って一方が絶対に他方より大きいならば、ゲート20はアクティブな信号HA>HBを提供する。このように、ベクトルの比較は、半順序関係partialorderrelationに従って獲得される。ユニット10が折り返された構成要素を比較する方法が定義されることが残っている。ユニットが4ビットワードA及びBを処理する例に関連して、各ユニット10の出力が下記のとおりに定義され得る。もしA~BCi>15=24-1であるならば、Co=1であり、これは、比較するために使用される加算器におけるキャリービットの従来の定義に対応する。もしA=Bならば、E=1である。もしA⊇Bであるならば、G=1であり、ここで⊇は、MここではM=16を法として折り返された値に対する操作に関して以前に与えられた定義によるより大きいか、または等しいという順序関係である。下記のテーブルは、折り返しの一例に関して、10進法で示された、A及びBの全ての可能な値に基づく、出力GEの値を提供する。従来の比較器において、対角線上の値を含む、下へ向かって行く対角線より下に位置した値は全て1であり、また対角線より上に位置した値は全て0である。ここで使用される比較器では、太字で示されたように、A,B=8,0とA,B=15,7との間を境界とする左下すみlowerleftcornerは、0のみを含み、A,B=0,9とA,B=6,15との間を境界とする右上すみupperrightcornerは、1のみを含む。別の方法で表すと、各行は、対角線の1に続いて8個の連続した0を含み、その後に8個の連続した1が続き、値のパターンは、それが行を循環的に満たすようになる。この例は、折り返された値ここでは2S<Mの間の半順序関係の一般的な定義におけるS=7=8-1に対応する。Sの値を減少させることは、行における連続した0の数を減少させると共に、1の数を増加させる。例えば、S=5は、各行において6個の連続した0、及び10個の連続した1を生成する。もしn個のユニット10が4nビットの構成要素に対応するようにチェーン状に接続されるならば、各ユニット10は4ビットで独立して作動するが、値は15で抑制されるboundedので、キャリーの伝搬のおかげで、チェーン状に一緒に接続された全てのユニットは、24n-1で抑制されたbounded4nビットの値に対して動作する。もしベクトルの構成要素の数が比較器の容量より大きい場合、それにもかかわらず、下記の方法において、いくらかの追加の要素によって、いくらかのサイクルにおいて比較器を使用して、比較を行うことが可能である。第1のサイクルの間、構成要素の最初のセットが比較される。ゲート20の出力は、無視されると共に、ゲート16及びゲート18の出力の状態は、次のサイクルの間、例えばフリップフロップ内に保存される。次のサイクルにおいて、構成要素の新しいセットが比較器に提示される。ORゲート18は、追加の入力として、その出力の以前に保存された状態HA≠HB-1を受け取る。従って、もし不均衡が前のサイクルにおいて検出されたならば、この検出は現在のサイクルに与えられる。更に、追加のANDゲート22が、ゲート16とゲート20との間に挿入される。ゲート22の出力は、ゲート16の出力、及びこの出力の以前に保存された状態HA≧HB-1がアクティブである場合にのみアクティブになる。ゲート20の出力は、比較器によって全ての構成要素を処理するのに十分なサイクル数の後で考慮に入れられることになる。前述の説明が、状態1をアクティブ状態、そして状態0を非アクティブ状態として言及するが、これらの状態の性質が、結果を変えずに、論理回路を応用することによって交換され得るということが理解される。"