図面 (/)

技術 論理時刻ベクトルに基づくタスクの実行をスケジュールするためのシステム

出願人 コミッサリアアレネルジーアトミークエオゼネルジザルタナテイヴ
発明者 ルノー・シルデヴァンサン・ダヴィド
出願日 2011年9月21日 (8年2ヶ月経過) 出願番号 2013-532243
公開日 2013年10月17日 (6年1ヶ月経過) 公開番号 2013-539144
状態 拒絶査定
技術分野 マルチプログラミング データフローマシン
主要キーワード 比較器ユニット 発生番号 比較不能 タスク発生 開始ベクトル データフロー処理 グラフ構築 ハードウェアカウンタ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2013年10月17日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (10)

課題・解決手段

2つの“Nm”ビットデータワード(A,B)の間の順序関係を示す比較出力(GE)を備えた、前記2つのデータワードのための比較器ユニット(10)であって、前記比較器ユニットの機能は、第1のデータワード(A)の可能な連続した値と関連付けられた行と、第2のデータワード(B)の可能な連続した値と関連付けられた列とを含む論理テーブルによって表され、各行は、前記行と同じ値に関連付けられた前記列との交点において“1”を含むと共に、該“1”の後には、一連の“0”が続き、前記一連の“0”の後には、循環的に前記行を完成する一連の“1”が続いており、“0”の数が、各行に関して同じであると共に、前記データワードの最大値(15)の半分より小さいことを特徴とする。

概要

背景

マルチタスクにおいて多発する問題は、タスクスケジューリング、すなわちタスクに関する全ての条件が満たされる時における各タスクの実行である。データフロータイプの処理の場合は、これらの条件は、タスクによって消費されるデータの利用可能性、及びタスクによって生成されたデータを収容するための空間の利用可能性を含む。

例えばグラフ構築、及びナビゲーションに基づいてタスクをスケジュールする様々な方法がある。いくらかの方法は、性能を最適化しようと試みる一方、他のものは、動作安定性に取り組む。動作安定性に取り組む方法は、例えば、方法が2つのタスクの各々の実行が他方のタスクの実行に依存すると判定するのでこれらのタスクを実行することができない状況において起こるデッドロックの発生を減少させるか、もしくは消去しようと試みる。

米国特許出願公開第2008/0005357号明細書は、性能を最適化するためにデータフロー処理に適用できる方法を説明する。その方法は、グラフ、及びトークン循環(token circulation)の構築に基づいている。タスクは、別のタスクによって生成されたトークンを有している場合にのみ実行され得る。そのタスクが実行される場合に、そのトークンは次のタスクに渡される。その方法は、動作安定性を保証する条件(constraint)を考慮しない計算モデルの極めて単純な実装である。

概要

2つの“Nm”ビットデータワード(A,B)の間の順序関係を示す比較出力(GE)を備えた、前記2つのデータワードのための比較器ユニット(10)であって、前記比較器ユニットの機能は、第1のデータワード(A)の可能な連続した値と関連付けられた行と、第2のデータワード(B)の可能な連続した値と関連付けられた列とを含む論理テーブルによって表され、各行は、前記行と同じ値に関連付けられた前記列との交点において“1”を含むと共に、該“1”の後には、一連の“0”が続き、前記一連の“0”の後には、循環的に前記行を完成する一連の“1”が続いており、“0”の数が、各行に関して同じであると共に、前記データワードの最大値(15)の半分より小さいことを特徴とする。

目的

マルチタスクシステムにおける、特にデータフロー処理のタスクにおけるタスクの発生の始まりにおいて満たされなければならない条件を追跡するために、本開示は、各タスクに関して、タスクの依存状態(dependency:従属関係)を表す論理時刻ベクトル(logical time vector)を保存することを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

2つの“Nm”ビットデータワード(A,B)の間の順序関係を示す比較出力(GE)を備えた、前記2つのデータワードのための比較器ユニット(10)であって、前記比較器ユニットの機能は、第1のデータワード(A)の可能な連続した値と関連付けられた行と、第2のデータワード(B)の可能な連続した値と関連付けられた列とを含む論理テーブルによって表され、各行は、前記行と同じ値に関連付けられた前記列との交点において“1”を含むと共に、該“1”の後には、一連の“0”が続き、前記一連の“0”の後には、循環的に前記行を完成する一連の“1”が続いており、“0”の数が、各行に関して同じであると共に、前記データワードの最大値(15)の半分より小さいことを特徴とする比較器ユニット。

請求項2

ベクトルが“Nm”の倍数である複数のビットを有する構成要素を含む、半順序関係に従った2つの前記ベクトルのための比較器であって、キャリー伝搬端子(Co,Ci)を通してチェーン状に接続された、複数の、請求項1に記載の比較器ユニット(10)と、2つの連続したユニットの前記キャリー伝搬端子の間に配置されると共に、ベクトルの構成要素の間の境界を定義する信号(S)のアクティブ状態(1)に応答して、前記連続したユニットの間の前記キャリーの伝搬遮断するように構成されたゲート(12)と、前記比較出力(GE)に配置されると共に、前記境界を定義する信号(S)の非アクティブ状態(0)に応答して、前記比較出力の状態を抑制するように構成されたゲート(14)とを備えることを特徴とする比較器。

請求項3

各ユニット(10)は、前記ユニットに提示された前記データワードの相当性を示す相当性出力(E)を備えると共に、前記比較器は、前記ユニットの全ての比較出力(GE)がアクティブであると共に、少なくとも1つのユニットの前記相当性出力(E)が非アクティブである時に限り、アクティブ表示を設定するように構成されたロジックを備えることを特徴とする請求項2に記載の比較器。

技術分野

0001

本発明は、マルチタスクシステムにおいて、特にデータ依存性制御を含み得るデータフロー処理タスクの実行の文脈において、相互依存タスクの実行をスケジュールすることに関係する。

背景技術

0002

マルチタスクにおいて多発する問題は、タスクのスケジューリング、すなわちタスクに関する全ての条件が満たされる時における各タスクの実行である。データフロータイプの処理の場合は、これらの条件は、タスクによって消費されるデータの利用可能性、及びタスクによって生成されたデータを収容するための空間の利用可能性を含む。

0003

例えばグラフ構築、及びナビゲーションに基づいてタスクをスケジュールする様々な方法がある。いくらかの方法は、性能を最適化しようと試みる一方、他のものは、動作安定性に取り組む。動作安定性に取り組む方法は、例えば、方法が2つのタスクの各々の実行が他方のタスクの実行に依存すると判定するのでこれらのタスクを実行することができない状況において起こるデッドロックの発生を減少させるか、もしくは消去しようと試みる。

0004

米国特許出願公開第2008/0005357号明細書は、性能を最適化するためにデータフロー処理に適用できる方法を説明する。その方法は、グラフ、及びトークン循環(token circulation)の構築に基づいている。タスクは、別のタスクによって生成されたトークンを有している場合にのみ実行され得る。そのタスクが実行される場合に、そのトークンは次のタスクに渡される。その方法は、動作安定性を保証する条件(constraint)を考慮しない計算モデルの極めて単純な実装である。

0005

米国特許出願公開第2008/0005357号明細書

先行技術

0006

“M. Raynal”及び“M. Singhal”、“Logical time: capturing causality in distributed systems”、IEEE Computer 29 (2)、1996
“C. Fidge”、“Logical time in distributed computing systems”、IEEE Computer 24 (8)、1991
“P. A. S. Ward”、“An offline algorithm for dimension-bound analysis”、Proceeding of the 1999 IEEE International Conference on Parallel Processing、ページ128-136

発明が解決しようとする課題

0007

従って、良好な性能と動作安定性の両方を有するスケジューリング方法の必要性が存在する。

課題を解決するための手段

0008

この必要性は、マルチタスクシステム上でのいくらかの相互依存タスクの実行方法であって、各タスクに、前記タスクの現在の発生(occurrence:生起)、及び前記現在の発生が依存する他のタスクのセットの発生を示す論理時刻ベクトル(logical time vector)を関連付けるステップと、もし第1のベクトルの全ての構成要素が第2のベクトルのそれぞれの構成要素より大きいか、あるいは第2のベクトルのそれぞれの構成要素に等しいと共に、前記第1のベクトルの少なくとも1つの構成要素が前記第2のベクトルのそれぞれの構成要素より完全に大きいならば、前記第1のベクトルが前記第2のベクトルより大きいと考えられるように、論理時刻ベクトルのセットに関する半順序(partial order)を定義するステップと、前記半順序関係(partial order relation)に従って、前記論理時刻ベクトルを比較するステップと、その論理時刻ベクトルが前記論理時刻ベクトルの他のどれよりも大きくないならば、前記タスクを実行するステップと、前記タスクの新しい発生に関して、前記ベクトルの少なくとも1つの構成要素の値を増加させることによって、実行された前記タスク(T)の前記論理時刻ベクトルを更新するステップとを含む方法によって解決される。

0009

実施例によれば、前記方法は、前記タスクの発生を実行するために満たされるべき条件の数を示す依存状態カウンタを、各タスクに関連付けるステップと、前記タスクの依存状態カウンタがゼロに到達する場合に前記タスクの実行を計画するステップと、タスクが実行された場合に、実行された前記タスクの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクの前記依存状態カウンタの値を減少させるステップと、実行された前記タスクの前記論理時刻ベクトルを更新するステップと、実行された前記タスクの前記論理時刻ベクトルより小さい論理時刻ベクトルを有する各他のタスクに関して、実行された前記タスクの前記依存状態カウンタの値を増加させるステップと、実行された前記タスクの前記論理時刻ベクトルより大きい論理時刻ベクトルを有する各他のタスクの前記依存状態カウンタの値を増加させるステップとを含む。

0010

実施例によれば、現在のタスクの前記論理時刻ベクトルは、各可能なタスクと関連付けられた構成要素を含む。前記現在のタスクと関連付けられた前記構成要素は、前記現在のタスクの発生番号を含む。別のタスクと関連付けられた構成要素は、前記現在のタスクが実行され得る前に完了されるべきである前記他のタスクの発生を識別すると共に、ゼロの構成要素は、前記現在のタスクが前記ゼロの構成要素と関連付けられたタスクに依存していないことを示す。

0011

方法の実行を加速するために、プロセッサシステムは、2つの“Nm”ビットデータワードの間の順序関係を示す比較出力を備えた、前記2つのデータワードのためのハードウェア比較器ユニットを備え得ると共に、前記比較器ユニットの機能は、第1のデータワードの可能な連続した値と関連付けられた行と、第2のデータワードの可能な連続した値と関連付けられた列とを含む論理テーブルによって表され、各行は、前記行と同じ値に関連付けられた前記列との交点において“1”を含むと共に、該“1”の後には、一連の“0”が続く。前記一連の“0”の後には、循環的に前記行を完成する一連の“1”が続いており、“0”の数が、各行に関して同じであると共に、前記データワードの最大値の半分より小さい。

0012

各ベクトルが“Nm”の倍数である複数のビットを有する構成要素を含む、半順序関係に従った2つの前記ベクトルのための比較器は、キャリー伝搬端子(carry propagation terminal:桁上げ伝搬端子)を通してチェーン状に接続された、複数の、上述のタイプの比較器ユニットと、2つの連続したユニットの前記キャリー伝搬端子の間に配置されると共に、ベクトルの構成要素の間の境界を定義する信号のアクティブ状態応答して、前記連続したユニットの間の前記キャリーの伝搬遮断するように構成されたゲートと、前記比較出力に配置されると共に、前記境界を定義する信号の非アクティブ状態に応答して、前記比較出力の状態を抑制するように構成されたゲートとを備える。

0013

実施例によれば、各ユニットは、前記ユニットに提示された前記データワードの相当性を示す相当性出力を備えると共に、前記比較器は、前記ユニットの全ての比較出力がアクティブであると共に、少なくとも1つのユニットの前記相当性出力が非アクティブである時に限り、アクティブ表示を設定するように構成されたロジックを備える。

0014

他の利点及び特徴は、代表的な目的のためにのみ提供され、そして添付の図面に表された、本発明の特定の実施例の下記の説明から更に明らかに明白になるであろう。

図面の簡単な説明

0015

データフロー処理において実行するための一連のタスクの単純な例を示す図である。
図1の各タスクの異なる発生の間の依存性を示すグラフである。
タスクの各発生がタスクの発生の間の依存性を識別するために使用される論理時刻ベクトルによって分類される図2のグラフに対応する図である。
いくらかのタスク発生に関する異なる実行時刻を有する図3のグラフを示す図である。
2つの代替タスクの実行を有するデータフロー処理における一連のタスクの例を示す図である。
図5のタスクの発生が論理時刻ベクトルによって分類されるグラフである。
論理時刻ベクトル及び依存状態カウンタ値によって分類された、図5に対応する処理に関する代表的な実行トレースを示すグラフである。
実行トレースの別の場合を示すグラフである。
半順序に従ってベクトルを比較するための比較器の実施例を概略的に示す図である。

実施例

0016

マルチタスクシステムにおける、特にデータフロー処理のタスクにおけるタスクの発生の始まりにおいて満たされなければならない条件を追跡するために、本開示は、各タスクに関して、タスクの依存状態(dependency:従属関係)を表す論理時刻ベクトル(logical time vector)を保存することを提供する。

0017

これ以降、用語「タスク」は、処理ステップの一般的なセットを示す。専門用語であるタスクの「実行」またはタスクの「発生」は、特定のデータセットに関するタスクの実行のことを指す。(データフロー処理において、同じタスクの連続した発生は、引き継ぐフロー(incoming flow)の連続するデータセットに関して実行される。)論理時刻ベクトルは、各タスクと関連付けられると共に、タスクの現在の発生の依存状態(dependency:従属関係)を反映する。

0018

論理時刻ベクトルは、論文「“M. Raynal”及び“M. Singhal”、“Logical time: capturing causality in distributed systems”、IEEE Computer 29 (2)、1996」及び「“C. Fidge”、“Logical time in distributed computing systems”、IEEE Computer 24 (8)、1991」において紹介されている。

0019

異なる(distinct)チャネルを通してイベントを受け取った各処理が、原因として、それらの順序を付け直すことができるように、半順序関係(partial order relation)と関連付けられた論理時刻ベクトルが、1つの処理から別の処理に送信されたイベントの時期を定める(date:時点、日時を定める)ために使用された。すなわち、従来、論理時刻ベクトルは、イベントを識別すると共に、相対的にイベントの時期(date)を定めるために、通常使用される。

0020

これ以降で理解されることになるように、この明細書では、論理時刻ベクトルは、いつタスクが実行され得るかを判定するために使用される。言い換えれば、論理時刻ベクトルは、タスクの実行順序強制する(constrain:強要する)、すなわち将来イベントを計画して実行するために使用される。

0021

論理時刻ベクトルのこの利用法は、データフロー処理の例と共に、下記で更に詳細に説明されることになる。

0022

図1は、基本のデータフロー処理を表す。タスクAは、データをタスクBに提供し、タスクBは、データを処理すると共に、結果をタスクCに提供する。この例では、それらのタスクは、3サイクルの深さを有するFIFOバッファを通してそれらのデータを伝達する。

0023

これらのタスクの実行の条件は、下記のとおりである。タスクAは、第1のバッファ満杯(full)でない場合のみ実行し得る。タスクBは、第1のバッファが空(empty)ではないと共に、第2のバッファが満杯(full)でない場合のみ実行し得る。タスクCは、第2のバッファが空(empty)ではない場合のみ実行し得る。

0024

図2は、タスクA、タスクB、及びタスクCの発生の間の依存状態を示すグラフである。それらの行は、タスクA、タスクB、及びタスクCに対応する。行の中の連続した円(circle)は、円の中に示されたように、同じタスクの連続した発生(occurrence:生起)に対応する。それらの列は、簡単にするために、タスクの各発生が1サイクルで完了すると仮定した場合の、連続した実行サイクルに対応する。

0025

矢印は、依存している(dependent:従属している)発生を接続する。各矢印は、“前に発生しなければならない”ことを意味する。すなわち、図示されたグラフにおいて、各矢印は、右を指し示すべきであり、それは、左を指し示すことができないと共に、垂直であり得ない。実線(solid)の矢印は、タスクの実行の順序によって与えられた依存状態を示す。点線の矢印は、バッファの(制限された)深さによって与えられた依存状態を示す。

0026

タスクAの第1の発生は、タスクBの第1の発生の前に実行されるべきであるので、そして、タスクBの第1の発生は、タスクCの第1の発生の前に起こらなければならないので、それらの発生は、1つの行から次の行まで、1サイクルを単位としてオフセットされる。

0027

図3は、ここで説明される方法に従ってタスクの各発生が論理時刻ベクトルによって分類されている図2のグラフを示す。論理時刻ベクトルは、各タスクと関連付けられると共に、タスクの各発生の終りに更新される。これらのベクトルの更新が、値を増加させることに対応するので、これらのベクトルは、更に、Hと表示されて「論理クロック」と呼ばれ得る。

0028

分かりやすいように、各ベクトルもしくはクロックHがマルチタスクシステム上で実行可能な各タスクと関連付けられた構成要素を含む、理解するための最も単純な場合が説明される。論理時刻ベクトルの従来の使用の場合に、タスクの数と比較して構成要素の数を最適化するための技術が存在し、そのような技術がここで同様に適用できる。そのような技術の例は、[“P. A. S. Ward”、“An offline algorithm for dimension-bound analysis”、Proceeding of the 1999IEEE International Conference on Parallel Processing、ページ128-136]において説明されている。

0029

従って、図3では、それぞれタスクA、タスクB、及びタスクCに割り当てられた3つのベクトル“H(A)”、ベクトル“H(B)”、及びベクトル“H(C)”が存在すると共に、各ベクトルは、それぞれタスクA、タスクB、及びタスクCに割り当てられた3つの構成要素を有している。

0030

タスク“Tj”と関連付けられたベクトル“H(Tj)”のタスク“Ti”と関連付けられた構成要素“hi”は、例えば、タスク“Tj”の現在の発生の実行にとって必要なタスク“Ti”の発生を含む。拡大解釈すれば、タスク“Tj”と関連付けられた構成要素“hj”は、現在実行中のタスク“Tj”の発生を含む。ゼロの(null:無効の)構成要素が示すのは、ベクトルと関連付けられたタスクの現在の発生が、ゼロの構成要素と関連付けられたタスクに依存しないということである。

0031

例えば、実行サイクル“t7”に関して図3において確認されたように、タスクAに対応するベクトル“H(A)”の第1の構成要素は7を含み、それはタスクAの現在の発生である。タスクAのこの発生は、第1のバッファ(図1)が少なくとも1つの利用可能な場所を有すること、すなわちタスクBの第4の発生がメモリバッファからデータを消費したことを必要とし、ベクトル“H(A)”におけるタスクBと関連付けられた(第2の)構成要素は4を含む。タスクBの第4の発生は、第2のバッファが少なくとも1つの利用可能な場所を有すること、すなわちタスクCの第1の発生がこのバッファからデータを消費したことを必要とし、ベクトル“H(A)”におけるタスクCと関連付けられた(第3の)構成要素は1を含む。

0032

各ベクトルは、熟考した発生から他のタスクのそれぞれの最も近い発生まで矢印を後ろにたどることによって、グラフから組み立てられる。従って、ベクトル“H(B)”は、時刻t7において、(6,6,3)を含むと共に、ベクトル“H(C)”は、(5,5,5)を含む。もし後ろにたどるべきそのような矢印が存在しないならば、その構成要素は、ゼロ(null:ヌル)であり、それは、タスクA及びタスクBの第1の発生に関する場合である。

0033

ベクトルの構築は、タスクを実施するアプリケーションプログラムの実行において達成することが容易である。ある発生(タスクAに関する6番目、タスクBに関する3番目、タスクCに関する1番目)を越えると、各構成要素は、関連するタスクの各実行で系統的に値が増やされるように思われる。それは、初期値を前もって定義すると共にベクトルの条件を更新するために十分であり、初期値を前もって定義すると共にベクトルの条件を更新することは、タスクの依存状態を記述するグラフの種類に応じてコンパイラによって実行され得る。これらの条件は、“k番目の発生から始まるベクトルXの増分構成要素xi”の形式で表される。それらのベクトルは、共有メモリに保存されると共に、各タスクがアプリケーションにより記録されるスケジューラによって、更新される。

0034

例えば、図3におけるベクトル“H(A)”の初期値及び更新条件は、下記のように定義され得る。

0035

0036

ここで、そのような論理時刻ベクトルを有効に利用するために、半順序関係がこれらのベクトルのセットに関して定義される。2つのベクトルX(x0,x2,・・・xn)とY(y0,y1,・・・yn)との間の半順序関係は、“0”と“n”との間のどのような“i”においても、“xi≦yi”であり、“0”と“n”との間に“xj<yj”であるような“j”が存在する時に限り、“X<Y”が真であるとして定義される。

0037

この順序関係は、それが全てのベクトルを順序付けるとは限らないので、“半(partial:部分的な、不完全な)”と呼ばれている。いくらかの場合において、ベクトルX及びYは共通点がなく、それは“X||Y”によって示される。

0038

ここで、タスクTaが実行を待っていると共に、現在の時刻にこのタスクが実行され得るかどうかを判定する必要があると仮定する。この判定のために、タスクTaの現在のベクトルが、他のタスクの現在のベクトルのそれぞれと比較される。他のタスクTが何であっても、次の条件が満たされさえすれば、タスクTaは実行され得る。

0039

0040

条件は、更に、下記のように示されることになる。

0041

0042

もし少なくとも1つの他のタスクTが“H(Ta)>H(T)”を与えるならば、全ての条件がタスクTaを実行するために満たされているとは限らず、従って、タスクTaは待つべきである。

0043

単純化した場合に対応する図3のグラフにおいて、3番目からの各列におけるベクトルは、ペアによって(ペアごとに)比較不能であるように思われる。これは、各々の対応するタスクが並列に実行され得ることを意味する。

0044

第1の列は、タスクAのみが実行され得ることを意味する“H(C)>H(B)>H(A)”を形成する。

0045

第2の列は、タスクAとタスクBは並列に実行され得るが、しかしタスクCは待たなければならないことを意味する“H(C)>H(B)、H(B)||H(A)及びH(A)||H(C)”を形成する。

0046

更に現実的な状況において、タスクは多かれ少なかれ遅れ到着すると共に、それらは多かれ少なかれ実行するのに時間がかかる。

0047

図4は、更に現実に近い状況を例証するように修正された図3のグラフを示す。タスクBの最初の2つの発生は、他の発生の長さの2倍持続する。それに続いて、タスクCの最初の発生は1サイクルの遅延で始まり、タスクCの第2の発生は、2サイクルの遅延で始まると共に、タスクAの第5の発生は、1サイクルの遅延で始まる。

0048

タスクの論理時刻ベクトルは、関連するタスクの実行のために必要とされるサイクル数の間変わらないままであり、それはタスクBの最初の2つの発生に関して見られ得る。タスクが終了するときに、ベクトルは更新される。従って、第5列におけるタスクA及びタスクBに関して見られるように、ベクトルの新しい値は関連するタスクの終りに有効になると共に、タスクの新しい発生を待っている間は変わらない。(これは、タスクB及びタスクCの最初の発生の実行を待っている間も同様である。)

0049

論理時刻ベクトルの利用法は、このグラフによって更によく理解されるであろう。第3の列は、“H(C)>H(B)”を形成する。従って、図3の場合と異なり、タスクCは、まだ開始し得ない。タスクCは、第4の列において開始し得ると共に、ここで、それらのベクトルは、ペアによって(ペアごとに)比較不能になる。

0050

第5の列は、“H(A)>H(B)”及び“H(C)>H(B)”を形成する。従って、タスクA及びタスクCは、タスクBが実行する間待たなければならない。タスクA及びタスクCは、第6の列において実行され得ると共に、ここで、それらのベクトルは、ペアによって(ペアごとに)比較不能になる。

0051

グラフがこのように無限伸びると共に、従って、あらゆる遅延を有するあらゆる長さの発生に適合し得ることは明白である。これは、デッドロックがないことを保証する。

0052

以前に言及されたように、論理時刻ベクトルは、構成要素の系統的な値の増加によって更新される。構成要素が無限になることは実際には考えられない。むしろ、構成要素の折り返し(folding:ひだ形成メカニズムが、整数部分集合(subset)に適した半順序に基づいて提供される。ベクトルの構成要素は、従って、Mを法として定義されると共に、2つのベクトルX(x0,x2,・・・xn)とY(y0,y1,・・・yn)との間の半順序関係が、どのような“i”においても、“xi=yi”または“xi⊂yi”であり、“xj⊂yj”であるような“j”が存在する時に限り、“X<Y”が真であるとして定義され、“x<y及びy−x≦S”であるか、または“x>y及びM−x+y≦S”である時に限り、関係“x⊂y”が真であるとして定義される。

0053

M及びSは、“2S<M”であるような整数であると共に、Mは、ベクトルの構成要素の間の最大のオフセットより大きい。図3の場合は、7番目の発生が提供するベクトルH(A)に関して、最大のオフセットは6である。この最大のオフセットは、全ての初期条件が考慮される瞬間から、すなわち全てのベクトルの全ての構成要素の値が増加される瞬間から判定される。

0054

図3の例では、“M=8”及び“S=3”において、ベクトルの構成要素は値“7”から折り返される。タスクAに関するグラフの最後の2つのベクトルは、従って、(0,5,2)及び(1,6,3)によって表されると共に、タスクBに関するグラフの最後のベクトルは、(0,0,5)によって表される。

0055

各構成要素の8つの可能な値を円周上に置くと、上記のように定義された“より小さい”という関係である“⊂”による構成要素の比較は、値xが、円周上後に続く3個(S個)の値のそれぞれより小さく、そして、前にある4個(“M−S−1”個)の値のそれぞれより大きいようになる。一例は下記のようになる。

0056

0057

上記で示された方法論によれば、タスクが実行され得るかどうかを判定するために、各実行サイクルで、各タスクの論理時刻ベクトルは、他のタスクの各々のベクトルと比較される。タスクの数が増える場合、これはかなりの計算資源に相当する(represent:を表す)と共に、タスクの数によって、比較の数は二次的に増加する。更に、たとえタスクが実行され得ることを比較の結果が示すとしても、タスクが利用可能な計算資源を与えられてすぐに実行されることができないことは起こり得る(この状況では、タスクは実行可能と言われる。)。実行可能なタスクのリストを管理することが、従って必要であり得る。

0058

計算資源を減少させるために、そして実行可能なタスクの計画を促進するために、“K”で表示されると共に、タスクが実行可能になる前に満たされるべき条件の数を内容が代表する依存状態カウンタが、各タスクに関連付けられる。実際には、カウンタの内容は、まだ満たされていない条件の数と等しくなり得ると共に、その内容がゼロの状態になる場合に、そのタスクは実行可能になる。

0059

依存状態カウンタを更新するために、下記の手順が適用され得る。

0060

ステム初期化において、“H(T):=H0(T)”及び“K(T):=0”とし、ここで、H0(T)は、タスクTに関する開始ベクトルであり、例えば、図3の例では、タスクAの場合(1,0,0)であり、タスクBの場合(1,1,0)であり、タスクCの場合(1,1,1)である。

0061

その場合に、スケジューラプロセスは、依存状態カウンタの内容を監視すると共に、カウンタがゼロである各タスクの実行を開始するか、または、並列にタスクを実行するための資源が不十分であるならば、これらのタスクの実行を計画する。

0062

タスクTが終了するときはいつでも、下記の4つのステップが、原子的に(atomically)、すなわちタスクの新しい発生が実行される前に、実行される。

0063

1.“H(Ta)>H(T)”を有する各他のタスクTaに関して、“K(Ta):=K(Ta)−1”を実行する。すなわち、ちょうど終了したタスクTは、各々のこれらのタスクTaが実行可能になる条件の内の1つを満たす。
2.タスクTの新しい発生に関してベクトルH(T)を更新する。以前に言及されたように、これは、発生の数が初期条件における構成要素に関するしきい値のセットに到達する場合に、ベクトルの各構成要素の値を増加させることによって達成され得る。
3.“H(T)>H(Ta)”を有する各他のタスクTaに関して、“K(T):=K(T)+1”を実行する。すなわち、タスクTの新しい発生の実行に関する全ての条件が識別されると共に、それらは、タスクTの依存状態カウンタにおいて明らかにされる。
4.“H(Ta)>H(T)”を有する各他のタスクTaに関して、“K(Ta):=K(Ta)+1”を実行する。すなわち、タスクTの新しい発生によって生成された新しい条件が、他のタスクTaに関して識別されると共に、それらは、これらの他のタスクの依存状態カウンタにおいて明らかにされる。

0064

依存状態カウンタは、ハードウェアにおいて実現され得ると共に、ゼロ内容検出器(null content detection circuit)によって、並列に(in parallel:同時に)監視され得る。論理時刻ベクトルは、前述の規則に従ってカウンタの値を増加させると共に減少させるように構成されたハードウェア比較器に連結された、専用のレジスタに保存され得る。(当然ながら、システム上で実行されるべきアプリケーションに含まれる多数の異なるタスクを処理するための、ベクトル専用の十分な量のハードウェアカウンタ及びレジスタが、提供されることになる。)この場合、システムソフトウェア(スケジューラ)は、専用のレジスタ内のベクトルの更新のみに関与する(のみを担当する)と共に、カウンタの比較及び更新はハードウェアアクセラレーション(hardware acceleration:ハードウェアの加速)によって実行される。

0065

例えば、依存状態カウンタは、差し迫った(imminent)実行の指標(indicator:インジケータ)であると共に、それらは、従って、データプリフェッチ(prefetch:先取り)動作を制御するために使用され得る。更に、比較の数はタスクの数によって直線的に増加するように思われる。

0066

図5は、2つの代替タスク実行を有するデータフロー処理(dataflow process)におけるタスクの系列の更に複雑な例を示す。図1のタスクBは、ここでは、2つのタスクB及びタスクB’を含み、タスクAが終了するときに、それらの内の1つが実行のために選択される。タスクAの発生によって生成された各データワードは、選択要素(selection element)SELを通して、タスクB及びタスクB’の内の1つに経路指定される。その選択は、同様にタスクAによって生成されると共に、タスクA、タスクB、及びタスクCの間に配置されたFIFOと同じ深さのFIFOに入れられる制御ワードTLによって操作される。この制御ワードCTLは、タスクCへの供給のために、アクティブなタスクBまたはアクティブなタスクB’の出力を選択する結合要素(merge element)MRGによって、同時に取り入れられる。

0067

図6は、(図3のグラフのように)タスクの発生が同じ長さを有すると共に遅延を有さないと仮定された、図5ケースに対応する依存状態のグラフである。論理時刻ベクトルの値は、発生を表すノードの中に示される。ベクトルは、ここでは、4つの構成要素を有している。更に、8を法として定義された構成要素を有する、折り返されたベクトル表記法が使用される。

0068

明瞭にするために、必ずしも全ての依存状態の矢印が示されるとは限らない。各タスクの第1の発生及び第4の発生からの矢印のみが示されると共に、他の矢印のセットが1つの発生から次の発生までのコピーであるということがわかる。依存状態は、図3におけるタスクBの発生に到着する矢印、または図3におけるタスクBの発生から離れる矢印は、ここでは、タスクBとタスクB’のそれぞれに複写されることを考慮して、図3のグラフに関する方法と同じ方法で組み込まれる。更に、矢印が、タスクBの各発生からタスクB’の次の発生に向けて離れると共に、矢印が、タスクB’の各発生からタスクBの次の発生に向けて離れる。

0069

図5のフローの特殊性は、タスクB及びタスクB’の内の1つだけがタスクAとタスクCとの間で実行されることである。上記で説明された方法論においてこれを考慮するために、これらの2つのタスクの内の1つが実行されるたびに、タスクBとタスクB’の両方が同時に実行されると仮定されている。すなわち、タスクBまたはタスクB’の各実行において、両方のタスクのベクトルが更新されると共に、依存状態カウンタKを使用する場合に、両方のタスクのカウンタが同様に更新される。

0070

図7は、図6のグラフによる処理の代表的な実行トレースを示す。実線のノードは、実行されつつあるか、もしくは実行されたタスクの発生に対応する。点線のノードは、実行を待つ発生に対応する。依存状態の矢印だけが、発生の実行の終りにおいて、すなわちベクトルH及びカウンタKが計算されるときに現れる。各ノードは、値が上記で説明された4つの原子的な(atomic:分割できない、極小の)ステップを通して更新される論理時刻ベクトル及び依存状態カウンタKの対応する値(corresponding value)を含む。

0071

タスクA、タスクB、タスクB’、及びタスクCのカウンタKの初期値を決定するために、各タスクが完了されたということ、そしてベクトルHがその初期値に更新されたということが仮定されている。カウンタ更新ステップ3を各タスクに適用する際に、カウンタは、それぞれ、0、1、1、及び3に初期化される。

0072

開始時に、タスクAの3つの発生が、連続3サイクルにわたって実行される。これらの発生の第1の発生は、完了するために3つのサイクルを要するタスクBの第1の発生を開始する。ベクトル及び依存状態カウンタの観点から、タスクB’の第1の発生がタスクBの第1の発生と同時に進行すると考えられる。

0073

タスクAの第4の発生、タスクB/タスクB’、実際にはタスクB’の第2の発生、及びタスクCの第1の発生は、第5のサイクルにおいて開始し得る。タスクB及びタスクB’が同時に第4のサイクルで終了すると見なすと、第5のサイクルのタスクCのカウンタKは、カウンタ更新ステップ1を、1度はタスクBのために、そして1度はタスクB’にために、2回適用することによって、2だけ値が減少される。

0074

タスクAの第4の発生は6サイクルを要し、タスクB’の第2の発生は1サイクルを要し、タスクCの第1の発生は2サイクルを要する。

0075

第8のサイクルにおいて、タスクAの第4の発生がまだ進行中である一方、タスクB/タスクB’(実際にはタスクB)の第3の発生が終わり、そしてタスクCの第2の発生が開始されている。タスクB/タスクB’(実際にはタスクB’)の第4の発生は、タスクAの第4の発生が完了することになる第11のサイクルを待つ。

0076

今までのところ説明されたタスク実行の例において、カウンタ更新ステップ4の使用は、明らかにされなかった。

0077

図8は、ステップ4が有益である2つのタスクA及びBの実行の単純な例のトレースである。図7と同じ表現の慣例が使用される。タスクAの各発生は、3つのデータワードを生成し、それらの各々は、タスクBの異なる(distinct)発生によって消費される。更に、タスクAとタスクBとの間のFIFOが3つのデータワードの深さを有しており、タスクAの各発生がFIFOで利用可能な空間の全てを必要とすると仮定されている。従って、タスクAの第2の発生は、タスクBの第3の発生が最終的にFIFOの空間を解放するまで、開始し得ない。

0078

ここでは、タスクAの発生を開始することがタスクBの3つの連続した発生の実行に支配されるので、ベクトルH(A)の第2の構成要素が、タスクAの発生の各実行において、3だけ値を増やされる点に注意が必要である。更に、ベクトルH(B)の第1の構成要素が、タスクBの発生の毎回の第3の実行の後で値を増やされる点に注意が必要である。これは、タスクBの3つの連続した発生がタスクAの同じ発生に支配されることを示す。

0079

タスクBの第1の発生の終りに4つの依存状態カウンタの更新ステップを適用することは、“T=B”及び“Ta=A”として、下記の関係を形成する。

0080

1.H(A)=(2,3)>H(B)=(1,1)=>K(A):=K(A)−1=0;
2.H(B):=(1,2);
3.H(B)>H(A)がであり、K(B)は変化しないままである。
4.H(A)=(2,3)>H(B)=(1,2)=>K(A):=K(A)+1=1、ステップ1において一時的に変更されたK(A)のオリジナルの正しい値が回復される。

0081

これらの4つのステップは、ステップ1が提供するKの一時的な値がステップ4においてオリジナルの値に回復されると共に、作動可能タスクのリストに影響を及ぼさないように、原子的に(atomically)実行される。

0082

カウンタ更新ステップ1、3、及び4のそれぞれにおいて、”N−1”個の論理時刻ベクトルの比較が実行され、ここで“N”はタスクの数であり、各ベクトルの比較は、N個のベクトル構成要素まで、2つずつ比較することを必要とする。構成要素の比較の数は、従って、タスクの数によって二次的に増加する。これらの操作は、スケジューラプロセスによってソフトウェアにおいて実行され得るが、しかし、ソフトウェアリソースを節約するために、これにハードウェアのサポートを提供することが望ましいであろう。

0083

半順序を使用する比較演算、及び好ましい実施例において折り返しによって抑制された構成要素に、従来のデジタル型比較器は適当ではない。

0084

図9は、これらのニーズを満たし得る、論理時刻ベクトルHA及びHBに関する比較器の実施例の第1の反復の要素を示す。

0085

論理時刻ベクトルは、抑制されたビットの数“Nv”、例えば64ビットで定義されるということ、そして、このベクトルの各構成要素が、最小値“Nm”、例えば4ビットの倍数であるプログラム可能なビットの数で定義され得るということが仮定されている。この数“Nm”は、ベクトルの構成要素の最大の数を決定する。従って、64ビットのベクトル、及び構成要素当たり4ビットの最小値に関して、多くても16個の4ビットの構成要素、そして4ビットの倍数によって定義されたより少ない構成要素を有するあらゆる組み合わせを定義することができる。

0086

図9の比較器は、チェーン状に接続された一連の比較器ユニット10を備える。各ユニット10は、2つのベクトルHA及びHBから比較するために、2つの4ビットの構成要素を処理する。各ユニット10は、その外部端子に関して、入力Aと入力Bの2の補数(〜B+1)とを合計する減算器に基づく比較器に関連付けられ得る。従って、ユニット10は、比較されるべき構成要素のそれぞれのための入力に加えて、キャリー(carry:桁上げ)入力“Ci”、キャリー(carry:桁上げ)出力“Co”、“A=B”であるかどうかを示す出力“E”、そして“A≧B”であるかどうかを示す出力“GE”を備える。

0087

第1のアプローチとして、説明を単純化するために、ユニット10が従来の比較器であると考える。更に下記で論じられたように、ユニットの論理テーブルは、折り返された値を比較するために修正されることになる。

0088

2つの64ビットワードの比較器を構築するように、ユニット10は、それらのキャリー(carry:桁上げ)出力“Co”及びキャリー(carry:桁上げ)入力“Ci”によってチェーン状に接続される。ベクトルの構成要素の間の境界がANDゲート12を用いて定義されるように、ゲート12は、ユニットの各キャリー出力“Co”と次のユニットのキャリー入力“Ci”との間に配置される。第1のユニットのキャリー入力は、0を受け取る(キャリーが考慮されない)。

0089

各ゲート12は、アクティブ状態(1)が構成要素の間の境界を定めるそれぞれの信号“S(S0,S1,S2...)”によって制御される。信号“S”のアクティブ状態は、ゲート12を遮断し、それによって、対応するユニット10のキャリーは次のユニットに送られず、そして、次のユニットは、比較を伝搬させず、次のユニットは従って独立した比較を行う。

0090

非アクティブである(アクティブでない)信号“S”(0)は、ゲート12を開くと共に、キャリーの伝搬を可能にすることによって、2つのユニット10をチェーン状に接続させる。これらの2つのユニットは、従って、同じベクトルの構成要素と関連付けられる。

0091

図9描写において、もし4つの信号“S”が非アクティブである場合、4つのユニット10は、単一の16ビットの構成要素と関連付けられる。もし信号“S1”及び“S3”がアクティブであるならば、ユニットは、2つの異なる8ビットの構成要素と関連付けられる。もし信号“S”の全てがアクティブであるならば、各ユニットは、異なる4ビットの構成要素と関連付けられる。

0092

更に、各信号“S”は、対応するORゲート14の反転入力印加されると共に、ORゲート14の第2の入力は、対応するユニット10の出力“GE”を受け取る。信号“S”が非アクティブであるときに、ゲート14は、ユニットの出力“GE”を伝搬させないと共に、この出力は、無視され得る中間の比較結果に対応する。信号“S”がアクティブであるユニットのみ、その出力“GE”が対応するゲート14によって伝搬されることが分かると共に、この出力は、現在のユニット及びチェーン状に接続された前のユニット(信号“S”が非アクティブであるユニット)によって生成された比較結果を統合する。

0093

ゲート14の出力は、ANDゲート16に到達すると共に、もし全てのユニット10の出力“GE”がアクティブになるならば、すなわち、ベクトルHAの各構成要素がベクトルHBの対応する構成要素より大きいか、またはベクトルHBの対応する構成要素に等しい(HA≧HB)ならば、従って、その出力はアクティブになる。(信号“S=0”によって遮断されるゲート14の出力は、実際には“1”になり、従って、それらは、他のゲート14の出力に影響を及ぼさない。)

0094

反転されたユニット10の出力“E”は、ORゲート18に到達する。従って、出力“E”の内の少なくとも1つが非アクティブであるならば、すなわち、ベクトルHA及びベクトルHBの少なくとも一組の構成要素に関して不均衡が存在するならば(HA≠HB)、ゲート18の出力はアクティブになる。

0095

ゲート16及びゲート18の出力は、ANDゲート20に到達する。従って、もしベクトルHAの全ての構成要素が、ベクトルHBのそれぞれの構成要素より大きいか、あるいはベクトルHBのそれぞれの構成要素に等しく(ゲート16がアクティブ)、そしてベクトルHAとベクトルHBの少なくとも2つのそれぞれの構成要素が等しくない(従って一方が絶対に他方より大きい)ならば、ゲート20はアクティブな信号(HA>HB)を提供する。このように、ベクトルの比較は、半順序関係(partial order relation)に従って獲得される。

0096

ユニット10が折り返された構成要素を比較する方法が定義されることが残っている。ユニットが4ビットワードA及びBを処理する例に関連して、各ユニット10の出力が下記のとおりに定義され得る。

0097

・もし“A+〜B+Ci>15(=24−1)”であるならば、“Co=1”であり、これは、比較するために使用される加算器におけるキャリービットの従来の定義に対応する。
・もし“A=B”ならば、“E=1”である。
・もし“A⊇B”であるならば、“G=1”であり、ここで“⊇”は、M(ここではM=16)を法として折り返された値に対する操作に関して以前に与えられた定義による“より大きいか、または等しい”という順序関係である。

0098

下記のテーブルは、折り返しの一例に関して、10進法で示された、A及びBの全ての可能な値に基づく、出力“GE”の値を提供する。

0099

0100

従来の比較器において、対角線上の値を含む、下へ向かって行く対角線より下に位置した値は全て1であり、また対角線より上に位置した値は全て0である。ここで使用される比較器では、太字で示されたように、(A,B)=(8,0)と(A,B)=(15,7)との間を境界とする左下すみ(lower left corner)は、“0”のみを含み、(A,B)=(0,9)と(A,B)=(6,15)との間を境界とする右上すみ(upper right corner)は、“1”のみを含む。別の方法で表すと、各行は、対角線の“1”に続いて8個の連続した“0”を含み、その後に8個の連続した“1”が続き、値のパターンは、それが行を循環的に満たすようになる。

0101

この例は、折り返された値(ここでは“2S<M”)の間の半順序関係の一般的な定義における“S=7(=8−1)”に対応する。“S”の値を減少させることは、行における連続した“0”の数を減少させると共に、“1”の数を増加させる。例えば、“S=5”は、各行において6個の連続した“0”、及び10個の連続した“1”を生成する。

0102

もしn個のユニット10が4nビットの構成要素に対応するようにチェーン状に接続されるならば、各ユニット10は4ビットで独立して作動するが、値は15で抑制される(bounded)ので、キャリーの伝搬のおかげで、チェーン状に一緒に接続された全てのユニットは、“24n−1”で抑制された(bounded)4nビットの値に対して動作する。

0103

もしベクトルの構成要素の数が比較器の容量より大きい場合、それにもかかわらず、下記の方法において、いくらかの追加の要素によって、いくらかのサイクルにおいて比較器を使用して、比較を行うことが可能である。

0104

第1のサイクルの間、構成要素の最初のセットが比較される。ゲート20の出力は、無視されると共に、ゲート16及びゲート18の出力の状態は、次のサイクルの間、例えばフリップフロップ内に保存される。

0105

次のサイクルにおいて、構成要素の新しいセットが比較器に提示される。ORゲート18は、追加の入力として、その出力の以前に保存された状態“(HA≠HB)−1”を受け取る。従って、もし不均衡が前のサイクルにおいて検出されたならば、この検出は現在のサイクルに与えられる。更に、追加のANDゲート22が、ゲート16とゲート20との間に挿入される。ゲート22の出力は、ゲート16の出力、及びこの出力の以前に保存された状態“(HA≧HB)−1”がアクティブである場合にのみアクティブになる。

0106

ゲート20の出力は、比較器によって全ての構成要素を処理するのに十分なサイクル数の後で考慮に入れられることになる。

0107

前述の説明が、状態“1”をアクティブ状態、そして状態“0”を非アクティブ状態として言及するが、これらの状態の性質が、結果を変えずに、論理回路を応用することによって交換され得るということが理解される。

0108

10比較器ユニット
12ANDゲート
14ORゲート
16 ANDゲート
18 ORゲート
20 ANDゲート
22 ANDゲート

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ