(57)【要約】  信号ストリーム処理ジョブはタスク（１００）を含み、各タスク（１００）は、ストリームからのデータのチャンクを処理するオペレーションの反復実行で実行されるべきである。各ジョブは、互いにストリーム通信する複数のタスク（１００）を含む。信号ストリームの通信のために互いに結合された複数の処理ユニット（１０）がそのタスクを実行する。タスクの実行を開始する機会が長くともタスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況でジョブの各タスクが実行される場合、各ジョブについての予備決定が個々に実行され、必要な最小ストリーム・スループット速度をジョブがサポートするのに必要な実行パラメータを決定する。ジョブの実行時組合せが実行のために選択される。選択されたジョブの組合せのタスクのグループが処理ユニット（１０）のそれぞれに割り当てられ、特定の各処理ユニット（１０）について、その特定の処理ユニット（１０）に割り当てられたタスクについての最悪実行時間の和がその特定の処理ユニット（１０）に割り当てられたタスク（１００）のいずれかについて定義された定義済みサイクル・タイムＴを超過しないことがチェックされる。処理ユニット（１０）は、選択された前記ジョブの組合せを同時に実行し、各処理ユニット（１０）は、その処理ユニット（１０）に割り当てられたタスク（１００）のグループの実行を時分割多重化する。
2008500627.tif 000002
【特許請求の範囲】
【請求項１】
信号ストリーム処理ジョブの組合せを実行するシステムにおいて、前記ジョブがタスクを含み、各タスクが前記タスクの受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであり、各ジョブが、互いにストリーム通信する複数の前記タスクを含むシステムであって、リアル・タイム要件が満たされるかどうかを判定するためのチェックを実行するように構成され、
信号ストリームの通信のために相互に結合された複数の処理ユニットと、
前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で前記ジョブの各タスクが実行される場合、各ジョブについての予備決定を個々に実行し、必要な最小ストリーム・スループット速度を前記ジョブがサポートするのに必要な実行パラメータを決定するように構成された予備計算ユニットと、
並列に実行されるべきジョブの組合せの実行時間選択のための制御ユニットと、
選択された前記ジョブの組合せのタスクのグループを前記処理ユニットのそれぞれに割り当てるように構成された割当てユニットであって、特定の各処理ユニットについて、前記特定の処理ユニットに割り当てられたタスクについての最悪実行時間の和が前記特定の処理ユニットに割り当てられたタスクのいずれかについて定義された定義済みサイクル・タイムＴを超過しないことをチェックし、前記処理ユニットが、選択された前記ジョブの組合せを同時に実行し、各処理ユニットが、前記処理ユニットに割り当てられたタスクのグループの実行を時分割多重化する割当てユニットと
を備えるシステム。
【請求項２】
前記予備計算ユニットが、タスクのそれぞれの対の間で前記チャンクをバッファリングするバッファのバッファ・メモリ・サイズを計算するように構成され、その結果、前記バッファ・サイズが、前記スループット速度が満たされていることを保証するのに十分となり、少なくとも計算された前記サイズのバッファ・メモリ・スペースが、実行中にタスクの前記対の間でのバッファリングのために確保される請求項１に記載のシステム。
【請求項３】
前記タスクの前記オペレーションを実行するのに使用可能なチャンクが不十分である場合、かつ／または前記オペレーションの結果チャンクを書き込むのに使用可能なバッファ・スペースが不十分である場合、記処理ユニットのうちの少なくとも１つが、前記処理ユニットに割り当てられたグループのタスクの実行をスキップするように構成される請求項１に記載のシステム。
【請求項４】
信号ストリーム処理ジョブの組合せを処理する方法であって、リアル・タイム要件が満たされるかどうかを判定するためにチェックを実行することを含み、
処理タスクを定義するステップであって、各タスクが、前記タスクが受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであるステップと、
互いにストリーム通信する複数の前記処理タスクをそれぞれ含む複数のジョブを定義するステップと、
前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で前記ジョブの各タスクが実行される場合、各ジョブについての予備決定を個々に実行し、必要な最小ストリーム・スループット速度を前記ジョブがサポートするのに必要な実行パラメータを決定するステップと、
並列実行のためのジョブの組合せを選択するステップと、
選択された前記ジョブの組合せの前記タスクのグループをそれぞれの前記処理ユニットに割り当て、特定の各処理ユニットについて、前記特定の処理ユニットに割り当てられたタスクについての最悪実行時間の和が前記特定の処理ユニットに割り当てられたタスクのいずれかについて定義された定義済みサイクル・タイムＴを超過しないことをチェックするステップと、
選択された前記ジョブの組合せを前記処理ユニットで同時に実行し、タスクのグループの実行を時分割多重化するステップと
を含む方法。
【請求項５】
前記予備決定の前記実施がタスクのそれぞれの対の間で前記チャンクをバッファリングするバッファのバッファ・メモリ・サイズを計算することを含み、その結果、前記バッファ・サイズが、前記スループット速度が満たされていることを保証するのに十分となり、少なくとも計算された前記サイズのバッファ・メモリ・スペースが、実行中にタスクの前記対の間でのバッファリングのために確保される請求項４に記載の方法。
【請求項６】
第１タスクと第２タスクの間でデータをバッファリングするためのバッファ・サイズのうちの少なくとも１つが、
前記ジョブの連続するタスクの経路を識別することであって、各経路において、前記経路中の連続する各タスクが、オペレーションを開始するために、前記経路中の先行するタスクの実行に依存し、各経路が前記第１タスクから始まり、前記第２タスクで終了すること、
識別した各経路について、前記経路に沿った前記タスクの最悪実行時間の和に、前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で実行されるときに前記タスクに実行する機会が与えられるまでの最大待ち時間を加えたものについての情報を計算すること、
識別した前記経路のいずれかについての前記和の最大値と、連続するチャンク間の必要な最大スループット時間との比からバッファ・サイズを求めること
によって計算される請求項５に記載の方法。
【請求項７】
前記予備決定の前記実施が、前記処理ユニットのうちの共通のものによって時分割多重化して実行するために前記ジョブのタスクのサブグループを選択することを含み、タスクの前記サブグループの実行を開始する機会が長くとも前記サブグループに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で前記ジョブの各タスクが実行される場合、必要な実行パラメータが必要な最小ストリーム・スループット速度をサポートしているかどうかが判定される請求項４に記載の方法。
【請求項８】
前記タスクの前記オペレーションを実行するのに使用可能なチャンクが不十分である場合、かつ／または前記オペレーションの結果チャンクを書き込むのに使用可能なバッファ・スペースが不十分である場合、前記グループ内のタスクの実行がスキップされる請求項４に記載の方法。
【請求項９】
前記予備計算の前記実施が、スループット速度が前記状況で常に満たされることを保証することが可能かどうかの判定を実施することを含む請求項４に記載の方法。
【請求項１０】
前記スループット速度が常に満たされることを保証することができない場合、前記タスクのうちの少なくとも１つについて定義されたサイクル・タイムＴを短縮すること、および前記短縮したサイクル・タイムで前記予備計算の前記実施を反復することを含む請求項９に記載の方法。
【請求項１１】
同期データ・フロー（ＳＤＦ）グラフの表現と同等の情報を生成すること、およびグラフ分析等価技法を使用してパラメータを計算することを含む請求項４に記載の方法。
【請求項１２】
信号ストリーム処理ジョブの組合せを実行する装置において、前記ジョブがタスクを含み、各タスクが、前記タスクが受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであり、各ジョブが、互いにストリーム通信する複数の処理タスクを含む装置であって、リアル・タイム要件が満たされるかどうかを判定するためのチェックを実行するように構成され、
信号ストリームの通信のために結合された複数の処理ユニットと、
並列に実行されるべきジョブの組合せの実行時間選択のための制御ユニットと、
選択された前記ジョブの組合せのタスクのグループを前記処理ユニットのそれぞれに割り当てるように構成された回路であって、特定の各処理ユニットについて、前記特定の処理ユニットに割り当てられたタスクについての最悪実行時間の和が前記特定の処理ユニットに割り当てられたタスクのいずれかについて定義された定義済みサイクル・タイムＴを超過しないことをチェックし、前記処理ユニットが、選択された前記ジョブの組合せを同時に実行し、各処理ユニットが、前記処理ユニットに割り当てられたタスクのグループの実行を時分割多重化する回路と
を備える装置。
【請求項１３】
ジョブに必要な実行パラメータを計算する装置において、前記ジョブがタスクを含み、各タスクが、前記タスクが受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであり、各ジョブが、互いにストリーム通信する複数の処理タスクを含む装置であって、前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で前記ジョブの各タスクが実行される場合に、各ジョブについての予備計算を個々に実行し、必要な最小ストリーム・スループット速度を前記ジョブがサポートするのに必要な実行パラメータを決定するように構成される装置。
【請求項１４】
予備計算の前記実施が、タスクのそれぞれの対の間で前記チャンクをバッファリングするバッファのバッファ・メモリ・サイズを計算することを含み、その結果、前記バッファ・サイズが、前記スループット速度が満たされていることを保証するのに十分となり、少なくとも計算された前記サイズのバッファ・メモリ・スペースが、実行中にタスクの前記対の間でのバッファリングのために確保される請求項１３に記載の装置。
【請求項１５】
第１タスクと第２タスクの間でデータをバッファリングするためのバッファ・サイズのうちの少なくとも１つが、
前記ジョブの連続するタスクの経路を識別することであって、各経路において、連続する各タスクが、オペレーションを開始するために、前記経路中の先行するタスクの実行に依存し、各経路が前記第１タスクから始まり、前記第２タスクで終了すること、
識別した各経路について、前記経路に沿った前記タスクの最悪実行時間の和に、前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で実行されるときに前記タスクに実行する機会が与えられるまでの最大待ち時間を加えたものについての情報を計算すること、
識別した前記経路のいずれかについての前記和の最大値と、連続するチャンク間の必要な最大スループット時間との比からバッファ・サイズを求めること
によって計算される請求項１４に記載の装置。
【請求項１６】
前記予備計算の前記実施が、スループット速度が前記状況で常に満たされることを保証することが可能かどうかの判定を実施することを含み、前記スループット速度が常に満たされることを保証することができない場合、前記タスクのうちの少なくとも１つについて定義されたサイクル・タイムを短縮すること、および前記短縮したサイクル・タイムで前記予備計算の前記実施を反復することを含む請求項１４に記載の装置。
【請求項１７】
信号ストリーム処理ジョブの組合せを処理する方法であって、リアル・タイム要件が満たされるかどうかを判定するためにチェックを実行することを含み、
処理タスクを定義するステップであって、各タスクが、前記タスクが受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであるステップと、
互いにストリーム通信する複数の前記処理タスクをそれぞれ含む複数のジョブを定義するステップと、
並列実行のためのジョブの組合せを選択するステップと、
選択された前記ジョブの組合せの前記タスクのグループをそれぞれの前記処理ユニットに割り当て、特定の各処理ユニットについて、前記特定の処理ユニットに割り当てられたタスクについての最悪実行時間の和が前記特定の処理ユニットに割り当てられたタスクのいずれかについて定義された定義済みサイクル・タイムＴを超過しないことをチェックするステップと、
選択された前記ジョブの組合せを前記処理ユニットで同時に実行し、タスクのグループの実行を時分割多重化するステップと
を含む方法。
【請求項１８】
信号ストリーム処理ジョブの組合せを実行するための実行パラメータを計算する方法であって、
処理タスクを定義することであって、各タスクが、前記タスクが受け取るストリームからのデータのチャンクを処理し、かつ／または前記タスクが生成するストリームからのチャンクを出力するオペレーションの反復実行で実行されるべきであること、
互いにストリーム通信する複数の前記処理タスクをそれぞれ含む複数のジョブを定義すること、
前記タスクの実行を開始する機会が長くとも前記タスクに対して定義されたサイクル・タイムＴだけ分離して生じるそれぞれの状況で前記ジョブの各タスクが実行される場合、各ジョブについての予備計算を個々に実行し、必要な最小ストリーム・スループット速度を前記ジョブがサポートするのに必要な実行パラメータを決定すること
を含む方法。
【請求項１９】
請求項１７に記載の方法をプログラム可能プロセッサに実行させるための命令を含むコンピュータ・プログラム。
【請求項２０】
請求項１８に記載の方法をプログラム可能プロセッサに実行させるための命令を含むコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、信号ストリームを処理する装置、そのような装置を操作する方法、およびそのような装置を製造する方法に関する。
【背景技術】
【０００２】
例えばテレビジョン／インターネット・アクセス装置、グラフィックス・プロセッサ、カメラ、オーディオ装置などの媒体アクセスのための装置では、信号ストリーム処理が必要である。現代の装置は、ますます膨大な数のストリーム処理計算を実施することを必要としている。ストリーム処理は、（少なくとも原理上は）無限の信号単位のストリームの連続するそのような信号単位を、信号単位の到着と同時に処理するものである。
【０００３】
このタイプの装置では、好ましくは、ストリーム処理計算の実装はいくつかの要求を満たさなければならない。すなわち、ストリーム処理計算の実装は、リアル・タイム信号ストリーム処理制約を満たさなければならず、柔軟なジョブの組合せを実行することが可能でなければならず、毎秒ごとに膨大な量の計算することができなければならない。例えばオーディオ・レンダリングでのヒックアップ（hick-up）、ディスプレイ・イメージのフリーズ、あるいはバッファ・オーバーフローによる入力音声またはビデオ・データの廃棄を回避するために、リアル・タイム・ストリーム処理要件は必要である。常にリアル・タイム制約を満たす、同時に実行されるべき任意の組合せの信号処理ジョブをユーザが実行時に選択することができなければならないので、柔軟性要件は必要である。膨大な量の計算の要件は通常、このすべてが、並列に動作し、信号処理ジョブの一部である異なるタスクを実施する複数のプロセッサのシステムで実現されるべきであることを示唆している。
【０００４】
そのような柔軟な分散システムでは、リアル・タイム制約を満たすことを保証することが極めて難しい可能性がある。データを生成するのに必要な時間は、実際の計算時間に依存するだけでなく、入力データを待機し、バッファ・スペースが出力データを書き込むために使用可能となるのを待機し、プロセッサが使用可能となるまで待機することなどでプロセッサによって消費される待ち時間にも依存する。予測不能の待機は、リアル・タイム性能を予測不能にする可能性がある。各プロセスがデータを生成し、かつ／または資源を解放することに着手するために互いに待機する場合、待機はデッドロックを引き起こす可能性さえある。
【０００５】
待機が、通常の条件下でリアル・タイム性能を妨げるようには思われない場合であっても、信号データが、ある計算タスクを、ストリームのチャンクについて（誤りではなく）著しく短い時間または長い時間で完了させるときに、特殊な環境下でのみリアル・タイム制約を満たすことに失敗することが表面化することがある。もちろん、単に、装置が常にジョブの組合せをサポートすることができるかどうかをユーザに試させるようにしておくことができる。しかしこのことは、例えば、ビデオ信号の一部が記録されていないこと、またはシステムが予測不能の時にクラッシュすることをユーザが後で発見しなければならないという結果となることがある。あるシステムでは、消費者がこの種の性能を受け入れることを余儀なくされているが、もちろんこのことは極めて不十分である。
【０００６】
同期データ・フロー（ＳＤＦ―Synchronous Data Flow―）グラフと呼ばれる理論フレームワークを使用することにより、個々のジョブについてこの問題に対する解決策が与えられた。ＳＤＦグラフの背後にある理論は、ストリーム処理ジョブのタスクが複数のプロセッサに分散されるように実装されるとき、すべての条件下でリアル・タイム制約または他のスループット要件が満たされることを保証できるかどうかをあらかじめ計算することを可能にする。ＳＤＦグラフ理論の基本的手法は、すべてのタスクを並列に実行する理論プロセッサの組について実行時間が計算されることである。ＳＤＦグラフ理論は、一定の条件下で、理論プロセッサの組について計算されるスループット速度（ストリームの連続する各部分の生成間で必要な時間）が常にタスクの実際の実装のスループット速度よりも低速であるという証明を与える。したがって、タスクの組合せがプロセッサの理論的な組についてリアル・タイムで動作することが示されている場合、その実際の実装についてリアル・タイム性能が保証されてよい。
【０００７】
ＳＤＦグラフは、タスクとして実行されなければならないジョブを分割することにより構築される。タスクは、ＳＤＦグラフ中のノードに対応する。典型的には、入力データの１つまたは複数のストリームのチャンクを他のタスクから入力し、かつ／または他のタスクに出力するオペレーションを繰り返し実行することによって各タスクが実行される。ＳＤＦグラフのノード間のエッジは、タスク間のストリームの通信を表す。理論プロセッサの組では、各タスクのオペレーションがプロセッサのうちの１つでそれぞれ実行される。理論プロセッサは、オペレーションの実行を開始する前に、十分なデータを待つ。ＳＤＦモデルでは、各ストリームが、ストリームからのデータのチャンクにそれぞれ対応する一続きの「トークン」から構成されると仮定される。指定の数のトークンがその入力で使用可能であるとき、プロセッサは、直ちに処理を開始し、その入力からトークンを入力（除去）し、得られるトークンをその出力に生成する前に所定の時間間隔がかかると仮定される。この理論モデルでは、トークンが出力される時点が計算されてよい。
【０００８】
こうした計算理論時点を、実際のプロセッサの組に関する最悪時点（worst case timepoint）に変換することを可能にするには、まず、理論プロセッサで必要とされる所定の時間間隔の持続時間を、実際のプロセッサで必要とされる最悪時間間隔と等しく（またはそれより大きく）なるように選択しなければならない。
【０００９】
第２に、理論モデルが実際のプロセッサのいくつかの制限を「認識」しなければならない。例えば、実際には、プロセッサは、前のトークンに関するオペレーションをまだ処理中である場合、オペレーションの実行を開始することができない。ノードからノード自体に戻る「セルフ・エッジ」を追加することにより、この制限をＳＤＦグラフで表現することができる。ノードに対応するプロセッサは、実行を開始する前にこのセルフ・エッジからのトークンを要求し、かつ実行の終了時にトークンを出力するようにモデル化される。もちろん、各実行中に、プロセッサの通常の入力からのトークンも処理される。セルフ・エッジは、１つのトークンを含むように初期化される。このようにして、１つのトークンに対するタスクの実行の開始が前のトークンに関する実行の完了まで待たなければならないという実際の特性が、理論プロセッサの組に与えられる。同様に、ＳＤＦグラフは、出力バッファ内に使用可能なスペースがないときにプロセッサを待機させることがある、バッファ容量による実際の制限を認識することができる。
【００１０】
実際のプロセッサの他の制限はしばしば、各プロセッサが典型的には複数の異なるタスクのオペレーションを時分割多重式に実行することによるものである。これは、実際にはオペレーションの実行の開始がトークンの使用可能性のために待たなければならないことだけでなく、同一のプロセッサで実行される他のタスクに関するオペレーションの完了に関しても待たなければならないことを意味する。一定の条件下では、この制限をＳＤＦグラフで表すことができる。特に、多重化タスクが実行される所定の順序があるとき、その所定の順序に従ってある多重化タスクから次の多重化タスクへのエッジのループをＳＤＦグラフに追加し、このループの第１エッジ上に１つの初期トークンを追加することによってこれを表すことができる。このようにして、ループ中の各タスクの実行の開始が前のタスクの完了を待つという実際の特性が、理論プロセッサの組に与えられる。
【００１１】
実際の実装の制限をＳＤＦグラフ・モデルに「認識」させるこの方式がすべての可能な制限に対して適用可能ではないことに留意されたい。例えば、時分割多重化タスクがプロセッサで実行される順序があらかじめ決定されない場合、タイミングに関する結果をＳＤＦグラフで表現することができない。したがって、例えば、特定のタスクを開始するためのトークンが不十分である場合にプロセッサが（次のタスクに先行する）その特定のタスクをスキップするように構成される場合、その効果をＳＤＦグラフで表現することができない。実際には、このことは、リアル・タイム・スループットをこの場合には保証することができないことを意味する。したがって、リアル・タイム保証はかなりの犠牲となり、使用できるのは一定の実装だけである。一般に、ＳＤＦグラフ理論に適合させるために、実装はタスクをより早く実行した結果として他のタスクの実行が遅くなるべきではないという「単調性条件（monotonicity condition）」を満たさなければならないと言える。
【００１２】
さらに、複数のジョブの柔軟な組合せの並列での実行に対してＳＤＦグラフ理論を適用することは難しいことに留意されたい。原理上は、このことは、並列に実行されるすべての異なるジョブのタスクが同一のＳＤＦグラフ内に含まれることを必要とする。これは、互いのタイミングでのタスクの相互効果を表現するために必要である。しかし、異なるジョブの入力および／または出力データ転送速度が同期されない場合、この方式でリアル・タイム保証を実現することは不可能となる。さらに、並列に実行しなければならないジョブの組にジョブが追加されるとき、またはジョブの組からジョブが削除されるごとに新しいスループット時間の計算を実施することは、かなりのオーバヘッドを生じさせる。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
とりわけ、本発明の一目的は、ほとんどオーバヘッドなしに実行時に適用されることのできるＳＤＦグラフ理論技法を使用してリアル・タイム保証を実現することである。
【００１４】
とりわけ、本発明の一目的は、柔軟なジョブの組合せをプロセッサの組で実行しなければならないときに、ＳＤＦグラフ理論技法を使用してリアル・タイム保証を実現するのに必要な計算量を削減することである。
【００１５】
とりわけ、本発明の一目的は、非同期ジョブの柔軟な組合せをプロセッサの組で実行しなければならないときに、リアル・タイム保証を実現することである。
【００１６】
とりわけ、本発明の一目的は、マルチプロセッサ回路でリアル・タイム保証を実現するのを可能にすることであり、プロセッサがラウンドロビン式に複数のタスクを実行し、前のタスクについて使用可能な入力データが不十分である場合、ラウンドロビン・シーケンス中の次のタスクに進む。
【００１７】
とりわけ、本発明の一目的は、資源をより浪費せずにＳＤＦグラフ理論技法を使用してリアル・タイム保証を実現することである。
【課題を解決するための手段】
【００１８】
本発明は、請求項１に記載の装置と、請求項４に記載の方法とを提供する。本発明によれば、複数の同時に実行されるストリーム処理ジョブについてのリアル・タイム・スループットが、２ステージのプロセスを使用することによって保証される。第１ステージでは個々のジョブが分離しているとみなされ、例えばタスク間のストリームからのデータをバッファリングするためのバッファ・サイズなどの、これらのジョブに関する実行パラメータが、想定される状況に対して選択され、タスクの実行を開始する機会が、長くとも、タスクに対して定義されたサイクル・タイムＴだけ分離して生じる。好ましくは、必要なリアル・タイム要件に従ってジョブが実行されることができるかどうか、すなわち、長くとも指定の遅延で、連続したデータのチャンクを生成するかどうかもチェックされる。第１ステージではどのストリーム処理ジョブの組合せが同時に実行されなければならないかが既知である必要はない。
【００１９】
第２ステージでは、同時に実行される処理ジョブの組合せが考慮される。このステージでは、選択されたジョブの組合せからの１群のタスクが、複数の処理ユニットのそれぞれに割り当てられる。割当て中に、特定の処理ユニットごとに、その特定の処理ユニットに割り当てられたタスクについての最悪実行時間の和が、その特定の処理ユニットに割り当てられたタスクのいずれかについて定義された定義済みサイクル・タイムＴを超過しないことがチェックされる。タスクに対して処理ユニットで使用されるスケジューリング・アルゴリズム（例えばラウンドロビン・スケジューリング）を仮定して、和は、実行するための連続する機会間の最大の可能な遅延に最悪実行時間がどれほど影響を及ぼすかを反映する。最終的に、選択されたジョブの組合せが同時に実行され、それぞれの処理ユニット上でタスクのサイクルの実行が時分割多重化される。典型的には、タスクが実行されることができるまで処理ユニットが待機することは不要である。リアル・タイム性能を保証する本発明のプロセスが使用された場合、処理ユニットは、入力および／または出力バッファ・スペースの不足のためにタスクが続行できない場合に、次のタスクにスキップしてよい。これは、相互に非同期のデータ・ストリームを処理する異なるジョブの性能を促進するのに特に有利である。
【００２０】
サイクル・タイムＴは、すべてのタスクについて同一に選択されるのが好ましい。これは第２ステージでのオペレーションを単純化する。しかし、第２実施形態によれば、リアル・タイム要件が満たされることができないとき、選択されたタスクのサイクル・タイムは調節される。特定のタスクについてのサイクル・タイムを短縮することにより、その特定のタスクとして同一の処理ユニット上で実行されるタスクを実質上少なくし、性能を向上することが可能となる。サイクル・タイムの調節は、第１ステージでの可能なリアル・タイム実装を探索することを可能にする（すなわち、並列に実行されなければならないタスクの組合せが、まだ不明であろう場合）。
【００２１】
想定される状況で必要な最小バッファ・サイズは、ＳＤＦグラフ技法を使用して計算されてもよい。一実施形態では、実際のタスクについてのノードの前でプロセスのＳＤＦグラフに仮想ノードを追加することによってバッファ・サイズが計算される。こうした仮想ノードの最悪実行時間が、タスクのサイクルが実行されるときに処理ユニットがタスクに達するまで待機することによる最悪遅延を表すように設定される。次に、データ・ストリームを生成するあるノードからデータ・ストリームを消費する別のノードまでのＳＤＦグラフを通るすべての経路を考慮し、各経路に沿ったノードの最悪実行時間の和を決定することによってバッファ・サイズが決定される。こうした和のうちの最大のものが使用されて、リアル・タイム・スループット要件によって決定される連続するトークン間の最大許容時間でそれを割ることによってバッファ・サイズが決定される。
【００２２】
実施形態の非限定的例を示す以下の図を使用して、本発明の上記およびその他の目的ならびに有利な態様がより詳細に説明される。
【発明を実施するための最良の形態】
【００２３】
図１はマルチプロセッサ回路の一例を示す。この回路は、相互接続回路１２を介して相互接続された複数の処理ユニット１０を含む。３つの処理ユニット１０だけが図示されているが、より多くの数または少ない数の処理ユニットが設けられてよいことを理解されたい。各処理ユニットは、プロセッサ１４、命令メモリ１５、バッファ・メモリ１６、および相互接続インターフェース１７を含む。図示されていないが、処理ユニット１０は、データ・メモリ、キャッシュ・メモリなどの他の要素を含んでよいことを理解されたい。そのような処理ユニットでは、プロセッサ１４が、命令メモリ１５に結合され、かつバッファ・メモリ１６および相互接続インターフェース１７を介して相互接続回路１２に結合される。相互接続回路１２は、例えば、処理ユニット１０間でデータを伝送するバスまたはネットワークなどを含む。
【００２４】
動作の際に、マルチプロセッサ回路は、複数の信号処理ジョブを並列に実行することができる。信号処理ジョブは、それぞれの複数のタスクを含み、ジョブの異なるタスクは、異なる処理ユニット１０で実行されてよい。信号処理応用例の一例は、２つのＭＰＥＧストリームのＭＰＥＧ復号化と、ストリームのビデオ部分からのデータのミキシングを含む応用例である。そのような応用例は、２つのＭＰＥＧビデオ復号化ジョブ、オーディオ復号化ジョブ、ビデオ・ミキシング・ジョブ、コントラスト補正ジョブなどのジョブに分割されてよい。各ジョブは、１つまたは複数の反復的に実行されるタスクを含む。ＭＰＥＧ復号化ジョブは、例えば可変長復号化タスク、コサイン・ブロック変換タスク（cosine block transformation task）などを含む。
【００２５】
ジョブの異なるタスクが、異なる処理ユニット１０で並列に実行される。このことは、例えば十分なスループットを実現するために行われる。各タスクを異なる処理ユニットで実行する別の理由は、処理ユニット１０の一部が、あるタスクを効率的に実行するように特殊化され、他の処理ユニットが、他のタスクを効率的に実行するように特殊化されてよいことである。各タスクは、信号データの１つまたは複数のストリームを入力および／または出力する。信号データのストリームは、所定の最大サイズのチャンク（通常、所定の時間間隔に関する信号データ、または好ましくは所定のサイズのイメージの所定の部分を表す）としてグループ化され、チャンクは、例えば、伝送パケット、単一ピクセル、ピクセルのライン、ピクセルの８×８ブロック、ピクセルのフレームに関するデータ、オーディオ・サンプル、時間間隔に対するオーディオ・サンプルの組などからなる。
【００２６】
ジョブの実行中、タスクごとにタスクに対応するオペレーションが反復的に実行され、そのたびに、所定の数のストリームのチャンク（例えば１チャンク）が入力として使用され、かつ／または所定の数のチャンクが出力として生成される。タスクの入力データ・チャンクは、一般に他のタスクによって生成され、出力データ・チャンクは、一般に他のタスクで使用される。第１タスクが第２タスクで使用されるストリーム・チャンクを出力するとき、出力後かつ使用前にストリーム・チャンクがバッファ・メモリ１６にバッファリングされる。第１および第２タスクが異なる処理ユニット１０で実行される場合、ストリーム・チャンクが、ストリーム・チャンクを入力として使用する処理ユニット１０のバッファ・メモリ１６に相互接続回路１２を介して送られる。
【００２７】
ＳＤＦグラフ理論
マルチプロセッサ回路の性能は、ＳＤＦ（同期データ・フロー）グラフ理論に基づいて管理される。ＳＤＦグラフ理論は従来技術からそれ自体がほぼ周知である。
【００２８】
図１ａはＳＤＦグラフの一例を示す。概念的に、ＳＤＦグラフ理論は、異なるタスクに対応する各「ノード」１００を有するグラフとしてアプリケーションを示す。ノードは、向きのある「エッジ」１０２でリンクされ、エッジ１０２は、ノードの対をリンクし、ストリーム・チャンクが、対の第１ノードに対応するタスクによって出力され、対の第２ノードに対応するタスクで使用されることを表す。ストリーム・チャンクは「トークン」によって表される。各ノードについて、対応するタスクが実行することができるまでにノードの着信リンク上にトークンがいくつ存在すべきか、タスクが実行されるときにタスクはいくつトークンを出力するかが定義される。ストリーム・チャンクの生成後、かつストリーム・チャンクが使用される前に、トークンはエッジ上に存在すると呼ばれる。これは、バッファ・メモリ１６へのストリーム・チャンクの格納に対応する。エッジ上のトークンの存在または不在は、ＳＤＦグラフの状態を定義する。ノードが１つまたは複数のトークンを「消費」したとき、かつ／または１つまたは複数のトークンを生成したときに、状態が変化する。
【００２９】
基本的に、ＳＤＦグラフは、ジョブの実行中のデータ・フローおよび処理オペレーション、１オペレーションで処理することのできるデータ・ストリームのチャンクに対応するトークンを示している。しかし、バス・アクセス調停、実行並列処理（execution parallelism）の量に対する制限、バッファ・サイズに対する制限などの様々な態様もＳＤＦグラフで表現することができる。
【００３０】
例えば、（所定の時間内のアクセスを保証するバスまたはネットワーク・アクセス機構が使用されると仮定して）伝送タスクを表すノードを追加することにより、バスまたはネットワークを介した伝送がモデル化されてよい。別の例として、原理上は、グラフ内の任意のノードは、十分な入力トークンが使用可能となるとすぐに、タスクの実行を開始すると仮定される。このことは、前のタスクの実行が実行の開始を妨げないという仮定を意味する。これは、同一のタスクについて無制限の数のプロセッサを並列に提供することによって保証されてよい。実際には、プロセッサの数はもちろん制限され、しばしば１つだけに制限され、このことは、次のタスクの実行は前のタスクの実行が終了するまで開始することができないことを意味する。図１ｂは、「セルフ・エッジ」１０４をＳＤＦグラフに追加することにより、当初は、並列に実行することのできる実行の数に対応するセルフ・エッジ上のいくつかのトークン１０６、例えば１つのトークン１０６で、これがどのようにモデル化されうるかを示す。これは、当初はトークンを消費することによってタスクが開始できるが、タスクが完了するまでは再度開始できず、それによってトークンを置換することを表す。実際には、そのようなセルフ・エッジを選択されたノードのみに追加することで十分であることがある。あるノードのタスクの開始可能性が制限されていることがしばしば、リンクされたノードのタスクが開始される回数に対する制限を自動的に示唆するからである。
【００３１】
図１ｃは、第１タスクから第２タスクへの通信のためのバッファのサイズに対する制限が、第２タスクに関するノードから戻るバック・エッジ１０８を第１タスクに関するノードに追加し、初めにいくつかのトークン１１０をこのバック・エッジ１０８上に配置することによって表され、トークン１１０の数が、バッファに格納されてよいストリーム・チャンクの数に対応する一例を示す。これは、第１タスクが初期トークンに対応する回数を初めに実行することができ、第２タスクが実行を終了し、それによってトークンを置換した場合にのみ後続の実行が可能であることを表す。
【００３２】
ＳＤＦグラフは、何らかの特定の実装から抽象化されたタスク間のデータ通信の表現である。思い描きやすいように、各ノードが対応するタスクの実行専用のプロセッサに対応すると考えることができ、各エッジが、１対のプロセッサ間のＦＩＦＯバッファを含む、通信接続に対応すると考えることができる。しかし、ＳＤＦグラフはこのことから抽象化され、異なるタスクが同一のプロセッサで実行され、異なるタスクに関するストリーム・チャンクがバスやネットワークなどの共有接続を介して通信される場合も表す。
【００３３】
ＳＤＦグラフ理論の主な抽象化の１つは、ＳＤＦグラフを実装するプロセッサによる最悪スループットの予測をサポートすることである。この予測に関する開始点は、それぞれ特定のタスク専用であり、タスクを実行するのに十分な入力トークンを受け取ると直ちにタスクの実行を開始するようにそれぞれ構成されたセルフ・タイム式処理ユニットを用いたＳＤＦグラフの理論的実装である。この理論的実装では、各処理ユニットがその対応するタスクの実行ごとに所定の実行時間を必要とすると仮定する。
【００３４】
この実装について、タスク（ラベル「ｖ」で識別される）のそれぞれの実行（異なる値のラベルｋ＝０，１，２．．で識別される）の開始時間ｓ（ｖ，ｋ）が容易に計算されてよい。有限の計算量で、無限の数のｋの値に対する開始時間ｓ（ｖ，ｋ）が決定されてよい。従来技術が、この実装により開始時間ｓ（ｖ，ｋ）が反復的パターンとなることをＳＤＦグラフ理論で証明しているからである。
ｓ（ｖ，ｋ＋Ｎ）＝ｓ（ｖ，ｋ）＋λＮ
【００３５】
上式でＮは、パターンが反復されるまでの実行数であり、λは、２つの連続する実行間の平均遅延であり、すなわち１／λが、単位時間当たりに生成される平均のストリーム・チャンク数である平均スループット速度である。
【００３６】
従来技術のＳＤＦグラフ理論は、ＳＤＦグラフ内の単純なサイクルを識別することによってλが決定されてよいことを示している（単純なサイクルは、多くともノードを１回含むエッジに沿った閉ループである）。そのような各サイクル「ｃ」について、サイクル内のノードの実行時間の和をサイクル内のエッジ上に当初あったトークン数で割ったものである公称平均実行時間（nominal mean execution time）ＣＭ（ｃ）が計算されてよい。λは最長の平均実行時間を有するサイクルｃｍａｘの平均実行時間ＣＭ（ｃｍａｘ）である。同様に、従来技術のＳＤＦグラフ理論は、期間内の実行数であるＮを計算する方法を与えている。現実の環境では、グラフは、少なくとも１つのサイクルを含むことに留意されたい。そうでない場合、グラフは、タスクを無限回並列に実行することのできる無限の数のプロセッサに対応することになり、スループット速度が無限となるからである。
【００３７】
理論実装について得られた結果は、ＳＤＦグラフの実際の実装についての最小スループット速度を求めるのに使用されてよい。基本的概念は、実際の実装での各タスクについて最悪実行時間を求めることである。次いで、この最悪実行時間が、理論的実装でのタスクに対応するノードに実行時間として割り当てられる。最悪実行時間を有する理論的実装についての開始時間ｓｔｈ（ｖ，ｋ）を計算するのにＳＤＦグラフ理論が使用される。一定の条件下で、こうした最悪開始時間が、常に少なくとも実際の実装での実行の開始ｓｉｍｐ（ｖ，ｋ）と同程度に遅いことが保証される。
ｓｉｍｐ（ｖ，ｋ）≦ｓｔｈ（ｖ，ｋ）
【００３８】
これにより、最悪スループット速度およびデータ前の最大遅延が使用可能であることを保証することが可能となる。しかし、タスクの実行を遅延させることのできるすべての実装の詳細がＳＤＦグラフとしてモデル化される場合にしかこの保証を与えることができない。これにより、タスクの実行時間の削減が何らかのタスクの開始時間を遅延させることが決してできない、単調な効果を非モデル化態様が有する実装に実装が制限される。
【００３９】
タスクの所定の組合せのスケジューリング
図２はＳＤＦグラフ理論を使用する図１に示すような処理回路上のタスクの組合せをスケジューリングするためのプロセスのフロー・チャートを示している。第１ステップ２１では、プロセスは、タスクとタスク間の通信の組合せの指定を受け取る。第２ステップ２２では、プロセスは、指定のタスクの実行を異なる処理ユニット１０に割り当てる。実際の回路内の処理ユニットの数はタスクの数よりも通常はずっと少ないので、処理ユニット１０のうちの少なくとも１つに、複数のタスクが割り当てられる。
【００４０】
第３ステップ２３では、プロセスは、シーケンスと、タスクが実行される相対頻度とをスケジューリングする（シーケンスの実行は、実行時に不定の回数だけ反復される）。このシーケンスは、デッドロックがないことを保証しなければならない。処理ユニット１０のシーケンス中の何らかの特定のタスクが処理ユニット１０で実行される別のタスクからのストリーム・チャンクを直接的または間接的に必要とする場合、その別のタスクがその特定のタスクを開始するのに十分なストリーム・チャンクを生成するように、その別のタスクがその特定のタスクの前に頻繁にスケジューリングされるべきである。このことがすべてのプロセッサについて当てはまるべきである。
【００４１】
第４ステップ２４では、プロセスは、ストリーム・チャンクを格納するバッファ・サイズを選択する。同一の処理ユニット１０上で実装されるタスクについて、別のタスクがデータを使用する前、またはスケジュールが反復される前に、タスクによって生成されたデータを格納することが可能でなければならない点で、バッファ・サイズに関する最小値はスケジュールに追従する。異なる処理ユニット上で実行されてよいタスク間のバッファ・サイズが、任意に選択されてよく、以下で議論される第６および第７ステップ２６、２７の結果の影響を受ける。
【００４２】
第５ステップ２５では、プロセスは、ＳＤＦグラフの表現を実質上作成し、指定のタスクおよびその依存関係を使用して、ノードおよびエッジを生成する。口語的には、プロセスがＳＤＦグラフを作成し、このグラフを一定の方式で修正すると言われるが、このことは、ＳＤＦグラフと少なくとも同等である情報、すなわちこのＳＤＦグラフの関連する特性を明白に導出することのできる情報を表すデータが生成されることを意味すると理解されたい。
【００４３】
プロセスは、異なる処理ユニット１０上でスケジューリングされたタスクに関するノード間のエッジ上に「通信プロセッサ」ノードを追加し、バッファ・サイズに関する制限および並列に実行することのできるタスクの実行数を表す追加のエッジを追加する。さらに、プロセスは、それぞれの実行時間ＥＴを特定の各ノードと関連付け、実行時間ＥＴは、特定のノードに対応する特定のタスクと同一の処理ユニット１０上の同一のシーケンスとしてスケジューリングされたタスクの最悪実行時間ＷＣＥＴの和に対応する。これは、可能性のある入力データの到着から実行の完了までの最悪待ち時間に対応する。
【００４４】
第６ステップ２６では、プロセスは、ＳＤＦグラフの分析を実行して、ＳＤＦグラフについての最悪開始時間ｓｔｈ（ｖ，ｋ）を、通常は上述の平均スループット遅延λおよび反復頻度Ｎの計算を含めて計算する。第７ステップ２７では、プロセスは、計算した最悪開始時間ｓｔｈ（ｖ，ｋ）がタスクの組合せについて指定されたリアル・タイム要件（すなわち、ビデオ・フレームを出力する時点などの通常は周期的に繰り返す時点である、ストリーム・チャンクが使用可能でなければならない指定の時点以前にこうした開始時間があること）を満たすかどうかをテストする。そうである場合、プロセスは、第８ステップ２８を実行して、タスクおよび情報に関するプログラム・コードをロードして、タスクがスケジューリングされる処理ユニット１０上でスケジュールを実施し、または少なくとも、このローディングについて後で使用される情報を出力する。スケジュールがリアル・タイム要件を満たさないことを第７ステップが示す場合、プロセスは、処理ユニット１０に対する異なるタスクの割当て、および／または異なる処理ユニット１０上で実行されるタスク間の異なるバッファ・サイズを用いて、第２ステップ２２から反復する。
【００４５】
スケジューリングされたタスクの実行中、スケジュール内のタスクの番であるとき、関連する処理ユニット１０は、タスクを実行するのに十分な入力データおよび出力バッファ・スペースが使用可能となるまで待機する（言い換えれば、タスクが開始されると、タスク自体は待機する）。すなわち、タスクがまだ実行することができず、スケジュール内の後続のタスクが実行することができることが明らかである場合でさえ、スケジュールからの逸脱は許されない。この理由は、そのようなスケジュールからの逸脱によってリアル・タイム制約の違反が生じる可能性があるからである。
【００４６】
柔軟なタスクの実行時間組合せ
図３に、複数のジョブのタスクを処理ユニット１０に動的に割り当てる代替プロセスのフロー・チャートを示す。このプロセスは、プロセスが複数のジョブの指定を受け取る第１ステップ３１を含む。この第１ステップ３１では、ジョブのうちのどれが組み合わされて実行されなければならないかは、必ずしもまだ指定されない。各ジョブは、組み合わせて実行される複数の通信タスクを含んでよい。第２ステップ３２では、プロセスは、各ジョブについて予備バッファ・サイズ選択を個々に実施する。第１および第２ステップは、実際の実行時オペレーションより前にオフラインで実施されてよい。
【００４７】
実行時に、プロセスは、ジョブの組合せを動的にスケジューリングする。通常、ジョブは１つごとに追加され、プロセスは第３ステップ３３を実行し、そのステップで、プロセスは、もしあれば、マルチプロセッサ回路によって実行されるそのジョブにジョブを追加する要求を受け取る。第４ステップ３４では、実行時に、プロセスはタスクを処理ユニット１０に割り当てる。第５ステップ３５では、追加のジョブのタスクが処理ユニット１０にロードされ、開始される（あるいは、あらかじめロードされている場合は単に開始される）。
【００４８】
好ましくは、第４ステップ３４で選択された割当ては、それぞれの処理ユニット１０についてのタスクのそれぞれのシーケンスを指定する。指定のタスクの実行中、非ブロッキング実行が使用される。すなわち、処理ユニット１０についての選択されたシーケンス中のタスクに対して十分なトークンが使用可能かどうかを処理ユニット１０がテストするが、処理ユニット１０は、使用可能なトークンが不十分である場合、タスクの実行をスキップしてよく、十分なトークンが使用可能な、選択されたシーケンス中の次のタスクを実行してよい。このようにして、実行のシーケンスは、トークンの使用可能についてテストするのに使用される、選択されたシーケンスに対応する必要はない。これにより、信号ストリームが同期されないジョブを実行することが可能となる。
【００４９】
予備バッファ・サイズ選択ステップ３２は、各タスクについて入力バッファ・サイズを計算する。同一の処理ユニット１０上の他のジョブを実行するための最悪時間の仮定下では、この計算は、個々のジョブについてのＳＤＦグラフ理論計算に基づく。
【００５０】
図４は、図３の予備バッファ・サイズ選択ステップ３２の詳細なフロー・チャートを示す。第１ステップ４１では、プロセスはジョブを選択する。第２ステップ４２では、ジョブの初期ＳＤＦの表現が、ジョブに関係するタスクを含めて構築される。第３ステップ４３では、各タスクが未知の他のタスクと共に時分割多重式に処理ユニット１０で実行されており、その組合せ最悪実行時間が所定の値を超過しないという仮定の下で、プロセスは実際の実装特性を表すようにノードおよびエッジを追加する。
【００５１】
第４ステップ４４では、プロセスは、ＳＤＦグラフの分析を実施して、タスク間で必要なバッファ・サイズを計算する。オプションで、プロセスは、ＳＤＦグラフに関する最悪開始時間ｓｔｈ（ｖ，ｋ）を、通常は上述の平均スループット遅延λおよび反復頻度Ｎの計算を含めて計算する。第５ステップ４５では、プロセスは、最悪開始時間ｓｔｈ（ｖ，ｋ）がタスクの組合せについて指定されたリアル・タイム要件（すなわち、ビデオ・フレームを出力する時点などの通常は周期的に繰り返す時点である、ストリーム・チャンクが使用可能でなければならない指定の時点以前にこうした開始時間があること）を満たすかどうかをテストする。そうである場合、プロセスは、第６ステップ４６を実行して、ローディングについて後で使用される、選択されたバッファ・サイズおよび予約時間を含む情報を出力する。次に、プロセスは、別のジョブについて第１ステップ４１から反復する。
【００５２】
図５は、この目的で使用されてよい仮想ＳＤＦグラフの一例を示している。仮想タスク５０についてのノードを特定の各タスク１００の前に追加することにより、仮想ＳＤＦグラフが、図１ｂに示されるグラフから得られている。仮想タスク５０は、実行中の現実のタスクに対応しないが、仮想タスク５０に追従する特定のタスク１００と同一の処理ユニットに割り当てられる（未知の）他のタスクによる遅延を表す。さらに、元の各ノード１００から仮想タスク５０についての、その先行ノードに戻る第１追加エッジ５４が追加されている。グラフの初期状態では、こうした各第１追加エッジは１つのトークンを含む。こうした第１追加エッジ５４は、特定のノード１００に対応するタスクの完了により、仮想タスク５０についてのノードで表される遅延時間間隔が開始されることを表す。
【００５３】
さらに、それぞれの特定の元のノード１００から、その特定の元のノード１００へのエッジを有する供給ノード１００に先行する仮想タスク５０についてのノードへの第２追加エッジ５２が追加されている。第２追加エッジ５２のそれぞれは、まだ決定されていないそれぞれのいくつかのトークンＮ１、Ｎ２、Ｎ３で初期設定されているとみなされる。第２追加エッジ５２は、関係するタスク間のバッファ容量の効果を表す。第２追加エッジ５２上のトークンの数Ｎ１、Ｎ２、Ｎ３は、こうしたバッファに少なくとも格納されてよい信号ストリーム・チャンクの数を表す。第２追加エッジ５２は、仮想タスク５０についてのノードに結合され、信号データを下流側タスクに供給するバッファ・メモリがいっぱいであるのでタスクをスキップしなければならない場合に、処理ユニット１０上のタスクの全サイクルの待ち時間が発生する可能性があることを表す。
【００５４】
（ΣＷＣＥＴｉ）／ＭＣＭ
という式の値以上の最も近い整数を使用して、バッファの容量が図５に示されるタイプの仮想グラフから計算されてよいことを証明できることが判明している。
【００５５】
上式で、ＭＣＭは必要なリアル・タイム・スループット時間（連続するストリーム・チャンクの生成間の最大時間）であり、ＷＣＥＴｉは（ｉと標識付けされた）タスクの最悪実行時間である。和に関係するタスクは、容量が計算されるバッファに依存し、またはＳＤＦグラフの点では、バッファを表す第２追加エッジ５２の開始ノードと終了ノード間で生じるノード１００、５０に依存する。終了ノードから開始ノードまでＳＤＦグラフを通る最悪経路内で生じる、選択された数のタスクｉにわたって和が取られる。「単純な」経路だけが考慮されるべきである。グラフがサイクルを含む場合、任意のノードを２回以上通過しない経路のみが考慮されるべきである。
【００５６】
例えば、図５に示す例で、タスクＡ３から仮想タスクＷ１に戻る第２追加エッジ５２を考慮する。Ｎ３（未知である数）個のトークンがこのエッジ上に当初存在し、タスクＡ１からタスクＡ３にデータ・ストリームを送るためのバッファ・サイズＮ３のストリーム・チャンクを表す。次に、バッファ・サイズＮ３が、Ｗ１（Ｎ３個のトークンを有するエッジの終点）からＡ３（このエッジの開始点）までのグラフを通る経路を探すことによって計算される。そのような２つの経路、Ｗ１−Ａ１−Ｗ２−Ａ２−Ｗ３−Ａ３、Ｗ１−Ａ１−Ｗ３−Ａ３が存在する。ループにより、他の経路、例えばＷ１−Ａ１−Ｗ２−Ａ２−Ｗ１−Ａ２（等）−Ｗ３−Ａ３、またはＷ１−Ａ１−Ｗ２−Ａ２−Ｗ１−Ａ２１−Ｗ３−Ａ２も存在するが、これらの経路はいくつかのノードを２回通過するので、これらは考慮されるべきではない。それでも、より複雑なグラフでは、バック・エッジを通る経路が単純である限り、その経路が寄与することがある。２つの単純な各経路、Ｗ１−Ａ１−Ｗ２−Ａ２−Ｗ３−Ａ３、Ｗ１−Ａ１−Ｗ３−Ａ３について、経路に沿ったノード１００、５０で表されるタスクの最悪実行時間の和が求められなければならず、こうした和のうちの最大値が使用されて、トークンの数Ｎ３が計算される。
【００５７】
ここで、最悪実行時間が仮想タスク５０と関連付けられる。これらの最悪実行時間がＴ−Ｔｉに設定される。ただしＴはサイクル・タイムである。特定のタスクのサイクル・タイムＴは、特定のタスクと共に同一の処理ユニット１０に割り当てられるタスクの最悪実行時間の最大の許容可能な和に対応する（特定のタスクの実行時間は和に含まれる）。好ましくは、同一の所定のサイクル・タイムＴが各タスクに割り当てられる。
【００５８】
特定のタスクを再度実行することができるまでの最悪待ち時間はＴ−Ｔｉである。ただしＴｉは特定のタスクの最悪実行時間である。
【００５９】
図の例では、数Ｎ１およびＮ２を計算し、Ｎ１を計算するのに経路Ｗ１−Ａ１−Ｗ２−Ａ２およびＷ１−Ａ１−Ｗ３−Ａ３−Ｗ２−Ａ２を使用し、Ｎ２を計算するのに経路Ｗ２−Ａ２−Ｗ３−Ａ３およびＷ２−Ａ２−Ｗ１−Ａ１−Ｗ３−Ａ３を使用して、他のバッファ・サイズについて同様の計算が実行される。
【００６０】
このようにして、十分なデータおよび出力バッファ容量が使用可能である場合、タスクに循環的に実行される機会が与えられることを条件として、各タスクがまだ未知の他のタスクと共に処理ユニット１０で実行される場合について、タスク間をバッファリングするための最小バッファ容量が求められてよい。
【００６１】
図３の第４ステップ３４では、実行時に、プロセスが処理ユニット１０にタスクを割り当てるとき、プロセスは、同一のプロセッサに割り当てられるタスクの最悪実行時間の和が、バッファ・サイズのオフライン計算中に割り当てられたタスクのいずれかについて仮定されるサイクル・タイムＴを超過しないかどうかを各処理ユニットについてテストする。割り当てられたタスクがこのサイクル・タイムを超過する場合、仮定されるサイクル・タイムＴを超過しない割当てが見つかるまで、処理ユニットに対する異なるタスク割当てが選択される。そのような割当てを見つけることができない場合、プロセスは、リアル・タイム保証を与えることができないことをレポートする。
【００６２】
図４の第５ステップ４５が、リアル・タイム要件を満たすことができないことを既にオフラインで示している場合、オプションで、ノード１００の一部について仮定されるサイクル・タイムＴが短縮されてよい。一方では、これは、仮想タスク５０についての対応するノードによって導入される遅延が短縮されるという効果を有し、リアル・タイム要件を満たすことが容易となる。他方では、これは、図３の第４ステップ３４の間に、仮定されるサイクル・タイムＴが短縮されたそのようなタスクと共にタスクをスケジューリングするために存在する空間が少なくなるという効果を有する。
【００６３】
図６は、本発明を実装する典型的なシステムを示す。図３の予備ステップ３２を実行するためにコンピュータ６０が設けられる。コンピュータ６０は、ジョブのタスク構造および最悪実行時間についての情報を受け取る入力を有する。ジョブを組み合わせるために実行時間制御コンピュータ６２が設けられる。ユーザがジョブを追加または削除することを可能にするために、ユーザ・インターフェース６４が設けられる（通常、このことは、ホーム・ビデオ・システムなどの装置の機能を活動化および非活動化することによって暗黙的に行われる）。ユーザ・インターフェース６４が、時間制御コンピュータ６２を実行するように結合され、時間制御コンピュータ６２は、コンピュータ６０によって選択されたジョブの実行パラメータを受け取る、コンピュータ６０に結合された入力を有する。実行時間制御コンピュータ６２は、処理ユニット１０に結合され、処理ユニット１０のうちのどれが活動化されるか、バッファ・サイズなど、どの実行パラメータが処理ユニット１０上で使用されるかが制御される。
【００６４】
コンピュータ６０と実行時間制御コンピュータ６２は同一のコンピュータでよい。あるいは、コンピュータ６０は、実行時間制御コンピュータ６２に名目上結合されるだけである別々のコンピュータでよい。コンピュータ６０で計算されるパラメータは、コンピュータ６０、６２間の永続的リンクを必要とすることなく、実行時間制御コンピュータ６２に格納され、または実行時間制御コンピュータ６２でプログラムされるからである。実行時間制御コンピュータ６２は、処理ユニット１０と共に同一の集積回路に一体化されてよく、または実行時間制御コンピュータ６２と処理ユニット１０のために別々の回路が設けられてよい。代替実施形態として、処理ユニット１０の１つが実行時間制御コンピュータ６２として機能してよい。
【００６５】
別の実施形態
ここまで、本発明が信号データの潜在的には無限のストリームを処理するジョブの組合せの同時実行についてのリアル・タイム保証を可能とすることを理解されよう。このことは２ステージ・プロセスで行われる。第１ステージは、バッファ・サイズなどの実行パラメータを計算し、個々のジョブについてのリアル・タイム能力を検証する。このことは、ジョブのタスクが、時分割多重化を使用して、まだ指定されていないタスクをジョブのタスクと直列に実行する処理ユニット１０で実行されるという仮定下で行われる。ただし、処理ユニットで実行されるそのタスクについての全サイクル・タイムが仮定されるサイクル・タイムＴを超過しないことを条件とする。第２ステージは、ジョブを組み合わせ、同一の処理ユニット１０に割り当てられるタスクの最悪実行時間が、こうしたタスクのいずれかについての仮定されるサイクル・タイムＴを超過しないことを確認する。
【００６６】
従来のＳＤＦグラフ技法と比較して（ａ）２ステージ・プロセスが使用される、（ｂ）まずリアル・タイム保証が個々のジョブについて計算される、（ｃ）実行されるジョブの組合せについて、リアル・タイム保証の完全な計算は不要であり、処理ユニット１０に割り当てられるタスクのシーケンスの最悪実行時間の和が割り当てられるタスクの仮定されるサイクル・タイムのいずれかを超過しないかどうかを計算することで十分である、および（ｄ）処理ユニット１０は、従来のＳＤＦグラフ技法について必要であるように、十分な入力データおよび出力バッファ・スペースを待機するのではなく、割り当てられたタスクのサイクル内のタスクの実行をスキップしてよい、といういくつかの違いがある。
【００６７】
これには、無関係のジョブの組合せについてリアル・タイム保証が与えられてよい、そのような組合せのスケジューリングが必要とするオーバヘッドは少なく、ジョブのデータ供給および生成が同期される必要がない、といういくつかの利点がある。
【００６８】
本発明は開示の実施形態に限定されないことを理解されたい。まず、ＳＤＦグラフを使用して本発明が説明されたが、プロセスがマシンで実行されるとき、当然ながら明示的なグラフは不要である。こうしたグラフの不可欠な特性を表すデータが生成され、処理されるのに十分である。この目的で、多くの代替表現が使用されてよい。この状況では、待機タスクをグラフに追加することは、好都合な比喩として説明されたに過ぎない。実際のタスクが追加されず、そのような概念的待機タスクの効果と同等である効果を反映するための多数の実際的な方法が存在する。
【００６９】
第２に、個々のジョブについてバッファ・サイズを選択する予備ステージはオフラインで実施されることが好ましいが、もちろん、オンラインですなわち実行されるジョブにジョブが追加される直前のジョブについて実施されてもよい。バッファ・サイズの計算は、計算されてよい実行パラメータの計算の一例に過ぎない。上述のように、タスクについて使用されるサイクル・タイム自体は、第１ステージで計算および決定されてよい別のパラメータである。別の例として、ストリームの連続するチャンクについて同一のタスクを実行してよい処理ユニットの数は、リアル・タイム能力を保証するために第１ステージで決定されてよい別の実行パラメータである。これは、例えば、タスクをＳＤＦグラフに追加して、ストリームのチャンクを連続するプロセッサにわたって周期的に分散させ、タスクのコピーを追加して、分散ストリームの異なるチャンクを処理し、組合せタスクを追加して、コピーの結果を組合せ出力ストリームとして組み合わせることによって実現されてよい。コピーの数に応じて、仮定される状況で、リアル・タイム・スループット条件への準拠が保証されてよい。
【００７０】
さらに、処理ユニット１０に対するより複雑な割当ての形態が使用されてよい。例えば一実施形態では、予備ステージは、ジョブの１群のタスクが同一の処理ユニット１０で実行されるべきであるという制約を課すものでもよい。この場合、追加する必要のある、待ち時間に関する仮想タスク５０は少なく（グループ内のタスクが連続してスケジューリングされる場合）、または待ち時間に関する仮想タスク５０が有する待ち時間は少なくてよく、グループからのタスク間に後でスケジューリングされてよい（まだ知られていない）他のタスクの部分の最悪実行時間を表す。実質上、グループ内のタスクの前の仮想タスク５０の組合せ待ち時間は、ｎ個のタスクが、同一の処理ユニット１０での実行に制限されることなく考慮されるときに必要となるｎ個のサイクル・タイムＴではなく、１つのサイクル・タイムＴに対応するだけでよい。これにより、リアル・タイム制約が満たされてよいことを保証することが容易となる。さらに、必要なバッファの一部のサイズがこのように削減されてよい。
【００７１】
さらに異なるジョブのデータ・ストリームの同期のいくつかの形態が可能である場合、実行中のタスクのスキップを使用する必要はない。この同期はＳＤＦグラフで表現されてよい。
【００７２】
さらに、任意のタスクを実行することのできる汎用処理ユニットについて本発明が説明されたが、その代わりに、処理ユニットの一部は、選択されたタスクだけを実行することのできる専用ユニットでよい。理解するであろうが、このことは本発明の原理に影響を及ぼさず、処理ユニットへのタスクの割当ての最終的可能性に関する制限を示唆するに過ぎない。さらに、図が見やすいように、通信タスクがグラフから省かれている（またはタスクに組み込まれるとみなされる）が、実際には、対応するタイミングおよび待機の関係を有する通信タスクが追加されてよいことを理解されよう。
【００７３】
固定シーケンスで実行する機会がタスクに与えられるラウンドロビン・スケジューリング方式を各処理ユニット１０が使用する実施形態について本発明が説明されたが、（未指定の）タスクの最悪実行時間に関する事前定義された制約を仮定して、タスクが実行する機会を得るまでの最大待ち時間がこのスケジューリング方式について計算されてよい限り、任意のスケジューリング方式が使用されてよいことを理解されたい。明らかに、タスクが実行する十分な機会を得るかどうかを判定するのに使用される最悪実行時間の和のタイプは、スケジューリングのタイプに依存する。
【００７４】
好ましくは、ジョブが実行時に柔軟に追加および／または削除されてよい処理システムでジョブが実行される。この場合、ジョブのタスクに関するプログラム・コードが、必要なバッファ・サイズおよび仮定されるサイクル・タイムＴについての計算された情報と組み合わせて供給されてよい。情報は、別の処理システムから供給されてよく、またはジョブを実行する処理システム内でローカルに生成されてよい。次いで、この情報は、ジョブを追加するために実行時に使用されてよい。あるいは、ジョブの実行をスケジューリングするのに必要な情報は、ジョブを実行する複数の処理ユニットと共に信号処理集積回路に永続的に格納されてよい。所定のジョブの組合せを静的に実行するようにプログラムされる集積回路に適用することさえもされてよい。後者の場合、プロセッサへのタスクの割当ては、実行時に動的に実行される必要はない。
【００７５】
したがって、実装に応じて、ジョブの組合せを実行する実際の装置が、バッファ・サイズを求め、実行時に処理ユニットにタスクを割り当てるための全機能を備えてよく、または実行時に処理ユニットにタスクを割り当てるための機能のみを備えてよく、さらには所定の割当てのみを備えてよい。こうした機能は、適切なプログラムで装置をプログラムすることによって実装されてよく、プログラムは、常駐するか、またはディスク、プログラムを表すインターネット信号などのコンピュータ・プログラム製品から供給される。あるいは、こうした機能をサポートするために専用ハードワイヤド回路が使用されてよい。
【図面の簡単な説明】
【００７６】
【図１】マルチプロセッサ回路の一例を示す図である。
【図１ａ】単純なジョブのＳＤＦグラフを示す図である。
【図１ｂ】単純なジョブのＳＤＦグラフを示す図である。
【図１ｃ】単純なジョブのＳＤＦグラフを示す図である。
【図２】リアル・タイム実行を保証するためプロセスのフロー・チャートを示す図である。
【図３】リアル・タイム実行を保証する２ステージ・プロセスのフロー・チャートを示す図である。
【図４】リアル・タイム実行を保証する２ステージ・プロセスでのステップのフロー・チャートを示す図である。
【図５】単純なジョブの複雑なＳＤＦグラフを示す図である。
【図６】本発明を実装する典型的なシステムを示す図である。
【図１】
2008500627.tif 000003
【図１ａ】
2008500627.tif 000004
【図１ｂ】
2008500627.tif 000005
【図１ｃ】
2008500627.tif 000006
【図２】
2008500627.tif 000007
【図３】
2008500627.tif 000008
【図４】
2008500627.tif 000009
【図５】
2008500627.tif 000010
【図６】
2008500627.tif 000011
【国際調査報告】
2008500627.tif 000012
2008500627.tif 000013
2008500627.tif 000014
2008500627.tif 000015