(57)【要約】本発明の目的は、少なくとも１つの排他的資源が少なくとも２つのタスクフローの実行に利用される、マルチタスクデータ処理システムの性能を改良することである。本発明による方法は、個別のタスクフロー向けのスケジュールを構築するテンプレートとして利用される、いわゆるマスタースケジュールを用いることによってこれを達成する。このマスタースケジュールという言葉は、タスクフロー用の排他的資源の予約の組を指す。
2008542902.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムにおける少なくとも１つの排他的資源の利用をスケジューリングする方法であって、少なくとも２つのタスクフロー向けに時間を予約するステップを備え、前記タスクフローを前記少なくとも１つの排他的資源によって実行する方法において、
前記タスクフロー向けに時間を予約する前記ステップは：
−第１のタスクフローへ、少なくとも１つのスケジューリング周期内における第１の固定単位時間を割り当てるステップ；及び
−第２のタスクフローへ、少なくとも１つのスケジューリング周期内における第２の固定単位時間を割り当てるステップを備えることを特徴とする排他的資源の利用をスケジューリングする方法。
【請求項２】
前記第１の固定単位時間及び前記第２の固定単位時間はマスタースケジュールに含まれ、
前記マスタースケジュールは前記タスクフロー向けの予約のスケジューリングを管理するためのものとする、請求項１に記載の方法。
【請求項３】
前記タスクフローは、複数の排他的資源によって実行される、請求項１又は２に記載の方法。
【請求項４】
前記マスタースケジュールは：
−排他的資源毎に、前記タスクフローにおいて前記排他的資源が必要とされる時間の最大量を計算するステップと；
−前記計算ステップで計算された前記最大量の合計が１つのスケジューリング周期に対応する時間内に収まるかどうかチェックするステップと；
−前記最大量を、前記タスクフロー向けに割り当てられる固定周期時間の持続時間に対する下限として利用するステップと；
−最重要タスクフロー向けに、固定周期時間を調整するステップと；
−より重要ではないタスクフロー向けに、前記調整ステップを繰返すステップと；
によって構築される、請求項３記載の方法。
【請求項５】
前記第１のタスクフローをメインのタスクフローとし、前記第２のタスクフローをサブのタスクフローとする、請求項１記載の方法。
【請求項６】
前記メインのタスクフローをメインのビデオフローとし、前記サブのタスクフローをサブのビデオフローとする、請求項５記載の方法。
【請求項７】
少なくとも１つの排他的資源を備えるデータ処理システムであって、該データ処理システムは、少なくとも２つのタスクフロー向けに時間を予約するように構成され、前記少なくとも１つの排他的資源は、前記タスクフローを実行するように構成されるデータ処理システムにおいて、
前記データ処理システムは：
−第１のタスクフローへ、少なくとも１つのスケジューリング周期内における第１の固定単位時間を割り当て；
−第２のタスクフローへ、少なくとも１つのスケジューリング周期内における第２の固定単位時間を割り当てることによって；
時間を予約するように構成されることを特徴とする、データ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理システムにおいて、少なくとも１つの排他的資源の利用をスケジューリングする方法に関し、この方法は、少なくとも２つのタスクフロー向けの時間を予約するステップを備え、このタスクフローは、少なくとも１つの排他的資源によって実行される。
【０００２】
本発明はまた、少なくとも１つの排他的資源を備えるデータ処理システムに関し、このデータ処理システムは少なくとも２つのタスクフロー向けの時間を予約するように構成され、少なくとも１つの排他的資源はこのタスクフローを実行するように構成される。
【背景技術】
【０００３】
信号、例えばビデオ信号の処理は、通常、特定のシーケンスで実行される複数のタスクを含む。図１はこのようなタスクシーケンスの一例を示す。図１に示される長方形は、入力信号毎に、例えば入力ビデオフレーム毎に実行する必要があるタスクを表す。タスクは複数個のプロセッサによって実行することができる。いくつかのプロセッサは同一の入力信号向けに複数のタスクを実行することができる。通常、このようなプロセッサはメモリから入力信号を読出し、いくつかの処理を実行し、メモリへと信号を戻して書込む。図１中の矢印は通常メモリバッファとして実装される。
【０００４】
タスクシーケンスは、また、フロー又はタスクフローとも呼ばれる。例えば、テレビ受信機にはメインのビデオフローがある。このメインのビデオフローは、例えば、タスクｔ０、ｔ１、ｔ２、ｔ１０、ｔ２０、ｔ３１及びｔ３２を含む。タスクｔ１０は入力信号（ビデオフレーム）をメモリへと書き込み、ｔ０、ｔ１及びｔ２は画像のスケーリングを実行し、ｔ２０はノイズ除去を実行し、ｔ３２は計算されたビデオフレームをディスプレイスクリーンに出力し、そして、ｔ３１はビデオフレームを補助出力に出力する。この例では、タスクｔ０はプロセッサｐ０によって実行され、タスクｔ１及びｔ２はプロセッサｐ１によって実行され、タスクｔ１０はプロセッサｐ１０によって実行され、タスクｔ２０はプロセッサｐ２０によって実行され、タスクｔ３１はプロセッサｐ３１によって実行され、そして、タスクｔ３２はプロセッサｐ３２によって実行される。
【０００５】
好適には、フローは周期的な静的スケジュールによって実装される。周期的とは、入力信号毎にタスクが同一の時系列で繰返されることを意味する。この周期性はデータ処理システムの実装に依存する。例えば、タスクの時系列はビデオフレーム又はフィールド毎に繰返されても良い。静的とは、スケジュールが実行前に設計されることを意味する。静的スケジュールにより、フローのエンドツーエンドの遅延のような重要なパラメータの最適化及び制御が可能になる。
【０００６】
図２は、先発及び後発の入力信号に対する同一スケジュールの周期的な繰返しによって囲まれた、１つの入力信号に対するスケジュールの例を（グレー色で）示す。矢印はどのタスクが同じ繰返しに属しているかを示す。通常、データ処理システムにおける多くのプロセッサは排他的資源である。排他的資源とは、一度に１つのタスクのみに対して利用できる資源として定義される。図２において、１つの繰返し中又は繰返し同士の間でも、ｐ１は一度に１つ以上のタスクには利用されていないことがわかる。
【０００７】
スケジュールを構築する場合には、また、システムの利用可能限度に対して、使用する共有資源（例えばメモリ帯域幅、共有プロセッサのプロセッササイクル）をチェックする必要がある。このようなスケジュールを構築する方法及びツールは、非特許文献１に記載されている。
【非特許文献１】"Philips Nexperia Digital Video Platform" by Maurice Penners and Hans van Antwerpen, at the Design, Automation and Test in Europe (DATE) conference in Paris, 2004 February 16-20.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
データ処理システムにおいては、多くのフロー及びこれらフローの変種（ｖａｒｉａｎｔｓ）、例えばメインフローの変種及び１つ以上のサブフローの変種が存在し得る。例えば圧縮又は非圧縮ビデオ、標準解像度又は高解像度、インターレース又はプログレッシブといった入力信号形式に応じて、フローでは異なるタスクが実行される。状況に応じて、組合わせる必要がある複数のフローもまた存在しうる。図３では、例えば、ｆ０は図１に示したようなメインのビデオフローを表し、ｆ１は、第２のビデオ入力はｐ１１によってメモリに収容され、ｐ０とｐ１とによってスケーリングされ、ｐ３２によってメインディスプレイ向けの出力における小ウィンドウに配置される、サブビデオフローを表す。例えばグラフィック用及びＶＢＩ（垂直ブランキング情報）用にいくつかの他のフローがあっても良い。また、サブフローは、入力信号形式に応じて、いくつかの変種を有する。そのため、メインフロー、サブフロー、及び場合によっては他のフローの独立した変種を組合わせることができるようにしなければならない。
【０００９】
要するに、周期的な静的スケジュールによって複数のフローをスケジュールし、フローの性能パラメータを最適化し、且つ制御しうるようにする必要がある。フローは、例えばメインのビデオフローの変種又はサブのビデオフローの変種のような、あるフローの変種とすることができる。
【００１０】
本発明の目的は、少なくとも１つの排他的資源を少なくとも２つのタスクフローの実行用に使用する、マルチタスクデータ処理システムの性能を改善することにある。
【課題を解決するための手段】
【００１１】
この目的は、請求項１の特徴部によって特徴付けられる方法を提供することによって、及び請求項７の特徴部によって特徴付けられるデータ処理システムを提供することによって実現される。
【００１２】
本発明による方法は、個別のタスクフロー向けにスケジュールを構築するのに、テンプレートとして利用される、いわゆるマスタースケジュールを用いることによってこれを達成する。ここで言うのマスタースケジュールとは、タスクフロー向けの排他的資源の予約の組を指す。
【００１３】
請求項２に記載の本発明の態様によれば、
第１の固定単位時間及び第２の固定単位時間をマスタースケジュールに含め、
マスタースケジュールはタスクフロー向けの予約のスケジューリングを管理するためのものとする。
【００１４】
請求項３に記載の本発明の態様によれば、
タスクフローを、複数の排他的資源によって実行する。
【００１５】
請求項４に記載の本発明の更なる態様によれば、
前記マスタースケジュールは：
−排他的資源毎に、タスクフローにおいて排他的資源が必要とされる時間の最大量を計算するステップと；
−前記計算ステップで計算された最大量の合計が１つのスケジューリング周期に対応する時間内に収まるかどうかチェックするステップと；
−前記最大量を、前記タスクフロー向けに割り当てられる固定周期時間の持続時間に対する下限として利用するステップと；
−最重要タスクフロー向けに、固定周期時間を調整するステップと；
−より重要ではないタスクフロー向けに、前記調整ステップを繰返すステップと；
によって構築される。
【００１６】
請求項５に記載の本発明の更なる態様によれば、
前記第１のタスクフローをメインのタスクフローとし、前記第２のタスクフローをサブのタスクフローとする。
【００１７】
請求項６に記載の本発明の更なる態様によれば、
前記メインのタスクフローをメインのビデオフローとし、前記サブのタスクフローをサブビデオフローとする。
【発明を実施するための最良の形態】
【００１８】
本発明を、図面を参照してより詳細に説明する。
【００１９】
図１はデータ処理システムにおけるタスクフローの例を示す。例えばテレビ受信機におけるメインのビデオフローであり、タスクｔ１０は入力信号（ビデオフレーム）をメモリへと書き込み、ｔ０、ｔ１及びｔ２は画像のスケーリングを実行し、ｔ２０はノイズ除去を実行し、ｔ３２は計算されたビデオフレームをディスプレイスクリーンに出力し、そして、ｔ３１はビデオフレームを補助出力に出力する。この例では、タスクｔ０はプロセッサｐ０によって実行され、タスクｔ１及びｔ２はプロセッサｐ１によって実行され、タスクｔ１０はプロセッサｐ１０によって実行され、タスクｔ２０はプロセッサｐ２０によって実行され、タスクｔ３１はプロセッサｐ３１によって実行され、そして、タスクｔ３２はプロセッサｐ３２によって実行される。
【００２０】
図２は周期的な静的スケジュールの例を示す。周期的とは、入力信号毎にタスクが同一の時系列で繰返されることを意味する。静的とは、スケジュールが実行前に設計されることを意味する。静的スケジュールにより、フローのエンドツーエンドの遅延のような重要なパラメータを最適化し、且つ制御することができる。図２は、先発及び後発の入力信号に対する同一スケジュールの周期的繰返しによって囲まれた、１つの入力信号に対するスケジュールの例を（グレー色で）示す。矢印はどのタスクが同じ繰返しに属しているかを示す。システムにおける多くのプロセッサは排他的資源とすることができ、これらは一度に１つのタスクのみに対して利用できる。図２において、１つの繰返し中又は繰返し同士の間でも、ｐ１は一度に１つ以上のタスクに対して利用されていないことをチェックすることが出来る。
【００２１】
図３はデータ処理システムにおける複数タスクフローの例を示す。図３において、ｆ０は図１に示されるようなメインのビデオフローを表し、ｆ１はサブビデオフローを表す。ここで第２のビデオ入力はｐ１１によってメモリに収容され、ｐ０とｐ１とによってスケーリングされ、ｐ３２によってメインディスプレイ向けの出力における小ウィンドウに配置される。
【００２２】
複数タスクフローに対する周期的な静的スケジュールの構築は、特にタスクフローが最大エンドツーエンド遅延のような所定の性能基準に従わなければならない場合には、実行することが困難であることを確かめた。本発明による方法は、個別のタスクフロー向けにスケジュールを構築するのに、テンプレートとして利用される、いわゆるマスタースケジュールを用いることによってこれを達成する。
【００２３】
図４は本発明によるマスタースケジュールの例を示す。ここで言うマスタースケジュールとは、タスクフロー向けの排他的資源予約の組を指す。例えば、図４において、排他的資源ｐ０及びｐ１はタスクフローｆ０及びｆ１の間で分配されている。
【００２４】
マスタースケジュールの構築は複数のステップ、すなわち、
−全てのフロー又はフロー変種をチェックし、排他的資源毎に、フロー又はフロー変種においてこの資源を必要とする時間の最大量を計算するステップ；
−排他的資源毎に、上記ステップの最大量の合計が、１つのスケジューリング周期に対応する時間内に収まるかどうかチェックするステップ；
−そして、これらの最大量を、予約の持続時間に対する下限として利用するステップ；
−最重要フロー又はフロー変種（例えば、エンドツーエンド遅延に最も厳しい要求を有するフロー）向けに、排他的資源の予約を、そのスケジューリング要求が条件を満たすことができるように調整するステップ；
−この調整ステップを他のフローに対して繰返し、毎回、残りのフローのうち最も重要なフローから開始するステップ；
で行われる。
【００２５】
マスタースケジュールは、個別のフロー又はフロー変種に対するスケジュールの構築に利用され、すなわち、
−フロー又はフロー変種毎に、そのフローに対するマスタースケジュールに排他的資源の予約を利用するスケジュールを構築し；
−フロー又はフロー変種の許可された組合せ毎に、利用する共有資源（例えばメモリ帯域幅）がシステム制限以下であるかチェックする。
【００２６】
或るステップが失敗する場合には、その前のステップにおける設計決定を変更するか、又は以前のステップにおける設計決定を再帰的に変更する必要がある
【００２７】
いくつかのデータ処理システムにおいて、排他的資源のクロック周波数を変更することができることに留意されたい。これは、マスタースケジュールを構築する、最初の２つのステップにさらなる自由度を与える。第１のステップにおいて、フロー又はフロー変種において排他的資源毎に必要となるクロックサイクルの最大数を計算することが出来る。第２のステップにおいて、排他的資源のクロック周波数を、予約を１つのスケジューリング周期に対応する時間に収めるために十分高く選定する。
【００２８】
図５は生成されたマスタースケジュール、及びマスタースケジュールによって管理される周期的スケジュールの繰返しの例を示す。図５の下半分は、フローｆ０及びｆ１に対する、排他的資源ｐ０及びｐ１の予約を備えたマスタースケジュールの例を示す。図の上半分はフローｆ０の変種及びフローｆ１の変種の周期的スケジュールの１つの繰返しを示す。例として、ｐ１は、図示したフローｆ０の変種に対し、スケジュール中で２回利用されている。これらのｐ１の利用は、双方ともフローｆ０に対するｐ１の予約の範囲に収まる。
【００２９】
マスタースケジュールを構築する方法の変形例として、フローの変種において排他的資源が複数タスクに対して利用される場合には、フローに対する排他的資源の予約は複数の隣接しない部分に分割されても良い。この場合には、マスタースケジュールを構築するステップはこれらのタスク毎に実行される。例として、図５では、フローｆ０の変種におけるｐ１の２回の利用は、この同じｆ０の他の変種とうまく収まるとするならば、それぞれ別々の予約を有することができる。このような細密な予約は、厳密なスケジューリング要求（例えばエンドツーエンド遅延）を満たすのに役立つが、関連するフローに伴う排他的資源に対するスケジューリングの自由度を減少させることになる。
【００３０】
図６はビデオ処理を実行する通常のデータ処理システムの例を示す。これは本出願人が開発した集積回路、すなわちフィリップスセミコンダクターズの集積回路ＰＮＸ８５５０の一部の概略図である。この集積回路は、特に、ビデオ処理又ビデオ圧縮解除を実行する複数のコプロセッサを含む。これらのコプロセッサの２つは、周期的な静的スケジュールにおいて排他的資源として利用される。
【００３１】
ＭＢＳ−１（メモリベースのスケーラ）は、メモリＭＥＭＯＲＹ−１からビデオフィールド又はフレームを読み、水平及び垂直方向のビデオ解像度のアップスケーリング又はダウンスケーリングを実行し、これにて得られたビデオフィールド又はフレームをメモリへと戻して書込む。インターレース解除の場合には、追加的なフィルタリングを実行することが出来る。１つの入力フィールド又はフレームに対するこれらの操作は１つのタスクで実行できる。
【００３２】
ＱＴＮＲ（品質の一時的ノイズ除去装置：Quality Temporal Noise Reductor）は、メモリから現在及び前のビデオフィールド又はフレームを読み込み、前のフィールド又はフレームとの加重平均を通じて現フィールド又はフレームにおけるノイズを除去し、結果をメモリへと戻して書込む。１つの現入力フィールド又はフレームに対するこれらの操作は１つのタスクで実行できる。
【００３３】
フィリップスセミコンダクターズのもうひとつの集積回路ＰＮＸ２０１５もまた、ビデオ処理及びビデオ圧縮解除用のコプロセッサを含む。このうちＭＢＳ−３が、周期的な静的スケジュールにおいて、排他的資源として利用される。ＭＢＳ−３はＭＥＭＯＲＹ−２にアクセスすることが出来る。ＭＢＳ−３はまた、デバイスｔ１及びｔ２によって表示されるトンネル接続を介して、ＭＥＭＯＲＹ−１にアクセスすることが出来る。集積回路ＰＮＸ８５５０はまた、トライメディア（Ｔｒｉｍｅｄｉａ）ＴＭ３２６０タイプのプログラム可能なプロセッサＴＭ−１を含む。これは特に、静的にスケジュールされたタスクをＰＮＸ８５５０及びＰＮＸ２０１５上のコプロセッサに対し発送する、ランタイムスケジューラのソフトウェアを実行する。
【００３４】
これ以降、メインフローの２つの変種とサブフローの２つの変種につき説明する。その後、マスタースケジュールを構築するステップと、個別のフロー変種に対するスケジュールにつき説明する。
【００３５】
図７はビデオ入力に対する第１のメインフロー変種を示す。これは、７２０×４８０ｉのフォーマットで、ＨＤＭＩを経るビデオ入力に対するメインフロー変種である、フロー変種ｍａｉｎ＿ＡＮＨ＿４８０ｉを示す。タスクｉｐはメモリの中間フィールドバッファの入力ビデオフィールドに配置される。タスクｓｃａｌｅ３及びｓｃａｌｅ＿ｖｃｒは、排他的資源ＭＢＳ−３及びＭＢＳ−１を用いてスケーリングを実行する。このフロー変種において、タスクｓｃａｌｅ３及びｓｃａｌｅ＿ｖｃｒは１００％、しかしフロー変種ｍａｉｎ＿ＡＮＨ＿１０８０ｉ（後で説明する）に対しては、異なるスケーリングファクタを利用する。タスクｎｒは排他的資源ＱＴＮＲを用いてノイズ除去を実行する。タスクｍｃは動き補償を実行する。タスクｓｃａｌｅ１は排他的資源ＭＢＳ−１を用いてスケーリングを実行する（インターレーシング解除も含む）。タスクｓｃａｌｅ＿ｇｆｘはＯＳＤ（オンスクリーンディスプレイ）向けのグラフィック情報のスライスにスケーリングを実行する。
【００３６】
タスクｏｐ１はメインフロー、サブフロー及びグラフィックのビデオレイヤを組合わせて、タイミング特性が液晶（ＬＣＤ）ディスプレイ又はプラズマディスプレイに適した出力信号を生成する。タスクｏｐ１の持続時間は、出力ビデオフレームの全体の周期である。
【００３７】
タスクｓｃａｌｅ２はまたスケーリングを実行する。タスクｓｃａｌｅ２及びｏｐ１を実行するコプロセッサは（ＭＥＭＯＲＹ−１内の中間バッファなしに）直接リンクされる。これは、ｓｃａｌｅ２の持続時間も、ｏｐ１のように、全体のフレーム周期であることを意味する。つまり、ｓｃａｌｅ２を実行するコプロセッサは他のタスクに利用されず、周期的な静的スケジュールにおいて排他的資源として利用されない。
【００３８】
タスクｏｐ１を実行するコプロセッサは出力における現ビデオライン向けのカウンタを備える。このコプロセッサは周期的な静的スケジュールにおいて関連するライン番号に割込みを生成することが出来る。（このスケジュールについては後に説明する。）プログラム可能なプロセッサＴＭ−１上で動作するスケジューラは、これらの割り込みを利用し、スケジュールされた時点において、関連するコプロセッサにタスクを発送する。
【００３９】
図８はビデオ入力に対する第２のメインフロー変種を示す。これは、１９２０×１０８０ｉのフォーマットで、ＨＤＭＩを経るビデオ入力に対するメインフロー変種である、ｍａｉｎ＿ＡＮＨ＿１０８０ｉを示す。これは最大スクリーンでメインフローが表示された場合に利用される最大解像度を示す。これはシングルウィンドウモードで利用される。これはまた、サブフローが小さいＰＩＰ（ピクチャーインピクチャー）として表示される場合には、バックグラウンドウィンドウでも利用される。ＤＷ（デュアルウィンドウ）モードでメインフローがスクリーンの左半分に表示される場合には、解像度はより小さい。この実施形態におけるマスタースケジュールは、ＰＩＰモード及びＤＷモードの双方に利用され、つまり以下の計算は最大解像度に基づく。
【００４０】
図９はビデオ入力に対する第１のサブフロー変種を示す。これは、７２０×４８０ｉのフォーマットで、アナログチューナを経るビデオ入力に対するサブフロー変種である、ｓｕｂ＿ＡＮＡ＿４８０ｉを示す。これは、ＤＷ（デュアルウィンドウ）モードでサブフローがスクリーンの右半分に表示された場合に利用される最大解像度を示す。この解像度は、サブフローがＰＩＰ（ピクチャーインピクチャー）モードで小さいウィンドウに表示される場合には、より低くなる。この実施形態におけるマスタースケジュールは、ＰＩＰモード及びＤＷモードの双方に用いられるため、以下の計算は最大解像度に基づく。
【００４１】
図１０はビデオ入力に対する第２のサブフロー変種を示す。これは、１９２０×１０８０ｉのフォーマットであるＭＰＥＧ−２ビデオ入力に対するサブフロー変種である、ｓｕｂ＿ＭＰ＿１０８０ｉを示す。タスクｍｐは半分の水平解像度での圧縮解除を実行する。
【００４２】
この図はＤＷ（デュアルウィンドウ）モードでスクリーンの右半分にサブフローが表示される場合に利用される最大解像度を示す。ＰＩＰ（ピクチャーインピクチャー）モードで小さいウィンドウにサブフローが表示される場合には、この解像度はより低い。この実施形態におけるマスタースケジュールは、ＰＩＰモード及びＤＷモードの双方に利用され、つまり以下の計算は最大解像度に基づく。
【００４３】
図１１Ａ、１１Ｂ及び１１Ｃは、図６に示すデータ処理システムにおいて排他的資源によって実行されるタスクに必要なクロックサイクルを示す。この計算はマスタースケジュールを構築する方法の第１のステップに対応する。すなわち全フロー又はフロー変種がチェックされ、排他的資源毎に、フロー又はフロー変種において資源が必要とされる時間の最大量が計算される。
【００４４】
図１１Ａは、メインフロー及びサブフローの変種において、排他的資源ＭＢＳ−３上のタスクに対して必要なサイクルを示す。タスクのサイクル数は、タスクの入力及び出力ビデオフィールド又はフレームの最大幅に、タスクの入力及び出力ビデオフィールド又はフレームの最大高を乗じたものに等しい。
【００４５】
図１１Ｂは、メインフロー及びサブフローの変種において、排他的資源ＱＴＮＲ上のタスクに対して必要なサイクルを示す。タスクのサイクル数は、タスクの出力フィールド又はフレーム中のピクセル数に、２を乗じたものに等しい。
【００４６】
図１１Ｃは、メインフロー及びサブフローの変種において、排他的資源ＭＢＳ−１上のタスクに対して必要なサイクルを示す。タスクのサイクル数は、タスクの入力及び出力ビデオフィールド又はフレームの最大幅に、タスクの入力及び出力ビデオフィールド又はフレームの最大高を乗じたものに等しい。
【００４７】
図１２Ａ、１２Ｂ及び１２Ｃは図６に示すデータ処理システムにおいて排他的資源によって実行されるタスクの持続時間を示す。この計算はマスタースケジュールを構築する方法の第２のステップに対応する。すなわち排他的資源毎に、前のステップの最大量の合計が１つのスケジュール周期に対応する時間内に収まるかどうかチェックされ、そしてこれらの最大量は予約の持続時間として利用される。
【００４８】
図１２Ａは１０８ＭＨｚで動作するＭＢＳ−３によって実行されるタスクの持続時間を示す。排他的資源ＭＢＳ−３に対して、プロセッサ周波数は特に１０８ＭＨｚに設定することが出来る。この周波数では、ＭＢＳ−３に対する表中の１、５８９、７６０サイクルは、１、５８９、７６０／１０８、０００、０００秒＝１４．７２ｍｓを必要とする。これは６０Ｈｚスケジュールの１６．６７ｍｓ周期の範囲に収まる。
【００４９】
図１２Ｂは１７３ＭＨｚで動作するＱＴＮＲ向けの各タスクの持続時間を示す。排他的資源ＱＴＮＲに対して、プロセッサ周波数は特に１７３ＭＨｚに設定することが出来る。この周波数では、ＱＴＮＲに対する表中の６９１、２００サイクルは、６９１、２００／１７３、０００、０００秒＝４．００ｍｓを必要とする。これは６０Ｈｚスケジュールの１６．６７ｍｓ周期の範囲に収まる。
【００５０】
図１２Ｃは１２３ＭＨｚで動作するＭＢＳ−１向けの各タスクの持続時間を示す。排他的資源ＭＢＳ−１に対して、プロセッサ周波数は特に１２３ＭＨｚに設定することが出来る。この周波数では、ＭＢＳ−１に対する表中の１、２７５、２４０サイクルは、１、２７５、２４０／１２３、０００、０００秒＝１０．３７ｍｓを必要とする。これは６０Ｈｚスケジュールの１６．６７ｍｓ周期の範囲に収まる。
【００５１】
マスタースケジュールを構築する方法の第三ステップ、すなわち、最重要フロー又はフロー変種（例えば、エンドツーエンド遅延に最も厳しい要求を持つフロー）に対しては、排他的資源の予約は、そのスケジューリング要求が条件を満たすことができるように調整し、このステップは他のフローにも繰返し、毎回、残りのフローのうち最も重要なフローから開始する。
このステップを以下に議論する好適な実施形態を参照して示す。
【００５２】
メインフロー変種のエンドツーエンド遅延は３７ｍｓに制限される。サブフロー変種には厳しいエンドツーエンド遅延要件はない。ｍａｉｎ＿ＡＮＨ＿１０８０ｉに対してこの遅延要件を達成することは、ｍａｉｎ＿ＡＮＨ＿４８０ｉに対してこの要件達成するよりも容易である。後者は順次実行する必要がある数多くのタスクを有する。
【００５３】
図１３は、３７ｍｓのエンドツーエンド遅延を実現するｍａｉｎ＿ＡＮＨ＿４８０ｉ向けの周期的な静的スケジュールを示す。ＭＢＳ−３の行の“３”はタスクｓｃａｌｅ３を意味する。ＱＴＮＲの行の“ｎ”はタスクｎｒを意味する。ＭＢＳ−１の行の“ｇ”、“ｖ”及び“１”は、それぞれ、タスクｓｃａｌｅ＿ｇｆｘ、ｓｃａｌｅ＿ｖｃｒ及びｓｃａｌｅ１を意味する。
【００５４】
グレーのタスクは１つの入力ビデオフィールドに実行されるビデオ処理の１つの繰返しを表す。連続する繰返しは重なり合う。
【００５５】
また、１つの繰返し内のいくつかのタスクも重なり合う。例として、タスクｉｐ、ｓｃａｌｅ３及びｎｒはそれぞれ、一番上のビデオラインから一番下のビデオラインまで順番にビデオ処理を実行する。これらのタスクは重なり合っても良いが、お互いに追い越してはならない。
【００５６】
この図の周期的な静的スケジュールは多くの追加的制約に従う。例として、ＭＥＭＯＲＹ−１に利用できる帯域幅は、タスクｎｒ（ＱＴＮＲ上）とｓｃａｌｅ１（ＭＢＳ−１上）との間で、これらのタスクの繰返しは異なるにもかかわらず、重なり合わないようにする。
【００５７】
図１３の周期的な静的スケジュールは、フロー変種ｍａｉｎ＿ＡＮＨ＿４８０ｉに対して排他的資源ＭＢＳ−３、ＱＴＮＲ及びＭＢＳ−Ｉが利用されない瞬間を示す。図中の点線のボックスはサブフロー向けの予約が可能な場所を示す。点線のボックスの持続時間はサブフロー変種中のタスクに対しては十分に大きい。ＱＴＮＲ向けの点線のボックスの持続時間はサブフロー変種におけるタスクｎｒに対し計算された持続時間の２倍よりもずっと大きい。ＱＴＮＲはメモリアクセスに対し低い優先度を有すため、そのタスクがスローダウンすることもある。図示の予約位置はフロー変種ｍａｉｎ＿ＡＮＨ＿４８０ｉに適しているだけでなく、重要度の低い全てのフロー変種にも適している。図示の位置は全ての残りのフローに対しステップ３が完了した後の結果である。
【００５８】
得られるマスタースケジュールは、
−ＭＢＳ−３はサブフロー変種におけるタスクに対し１．３０〜６．４２ｍｓの間に予約され、
−ＱＴＮＲはサブフロー変種におけるタスクに対し１．３７〜５．３７ｍｓの間に予約され、
−ＭＢＳ−１はサブフロー変種におけるタスクに対し５．５６〜８．９３ｍｓの間に予約され、
−ＭＢＳ−３、ＱＴＮＲ及びＭＢＳ−１は残りの時間に、メインフロー変種におけるタスクに対して予約される。
【００５９】
マスタースケジュールは個別のフロー又はフロー変種に対するスケジュールを構築するために使われ、すなわち、
−フロー又はフロー変種毎に、マスタースケジュールにおけるそのフローに対する予約を利用するスケジュールを構築し、
−フロー又はフロー変種の許可された組合せ毎に、利用する共有資源（例えばメモリ帯域幅）がシステム制限以下かチェックする。
【００６０】
図１３、図１４、図１５及び図１６はマスタースケジュールを利用して構築された周期的な静的スケジュールを示す。図１３は３７ｍｓのエンドツーエンド遅延を実現するｍａｉｎ＿ＡＮＨ＿４８０ｉに対する周期的な静的スケジュールを示す。図１４はマスタースケジュールに従うｍａｉｎ＿ＡＮＨ＿１０８０ｉに対する周期的な静的スケジュールを示す。エンドツーエンド遅延は３７ｍｓである（これはｍａｉｎ＿ＡＮＨ＿４８０ｉに対するエンドツーエンド遅延と同一である）。図１４はマスタースケジュールに従うｓｕｂ＿ＡＮＡ＿４８０ｉに対する周期的な静的スケジュールを示す。図１４はマスタースケジュールに従うｓｕｂ＿ＭＰ＿１０８０ｉに対する周期的な静的スケジュールを示す。
【００６１】
最後のステップを参照すると、すなわち、フロー又はフロー変種の許可された組合せ毎に、利用される共有資源（例えばメモリ帯域幅）がシステム制限以下かチェックすると、以下のことに気づく。上記図中の周期的な静的スケジュールは、何回かの設計を繰返した結果である。これらの結果得られるスケジュールにより、製品中の排他的資源を利用するタスク及び全ての他のタスクは、メインフロー変種及びサブフロー変種の全ての許可された組合せに対して利用できるメモリ帯域幅の範囲に収まる。また、（メモリアクセスに対して低い優先度を有する）ＱＴＮＲ上のタスクの持続時間の増加は十分に小さく、これらの結果として生じるスケジュールによって調整される。
【００６２】
本発明の保護の範囲はここに記載した実施形態に限定されないことに留意されたい。「含む／備える」は請求項に示したもの以外の他の要素を排除しない。１つの要素は、その要素を複数含むことを排除しない。本発明の一部を成す手段は、専用ハードウェアの形式、又はプログラムした汎用目的プロセッサの形式の双方で実装することが出来る。本発明は各新しい機能、又はこれらの機能の組合せにある。
【図面の簡単な説明】
【００６３】
【図１】データ処理システムにおけるタスクフローの例を示す図である。
【図２】周期的な静的スケジュールの例を示す図である。
【図３】データ処理システムにおける複数タスクフローの例を示す図である。
【図４】本発明によるマスタースケジュールの例を示す図である。
【図５】生成されたマスタースケジュールと、マスタースケジュールによって管理された周期的スケジュールの繰返しの例を示す図である。
【図６】ビデオ処理を実行する通常のデータ処理システムの例を示す図である。
【図７】ビデオ入力に対する第１のメインフロー変種を示す図である。
【図８】ビデオ入力に対する第２のメインフロー変種を示す図である。
【図９】ビデオ入力に対する第１のサブフロー変種を示す図である。
【図１０】ビデオ入力に対する第２のサブフロー変種を示す図である。
【図１１Ａ】図６に示すデータ処理システムにおいて排他的資源によって実行されるタスクに必要なクロックサイクルを示す図である。
【図１１Ｂ】図６に示すデータ処理システムにおいて排他的資源によって実行されるタスクに必要なクロックサイクルを示す図である。
【図１１Ｃ】図６に示すデータ処理システムにおいて排他的資源によって実行されるタスクに必要なクロックサイクルを示す図である。
【図１２Ａ】データ処理システムにおいて排他的資源によって実行されるタスクの持続時間を示す図である。
【図１２Ｂ】データ処理システムにおいて排他的資源によって実行されるタスクの持続時間を示す図である。
【図１２Ｃ】データ処理システムにおいて排他的資源によって実行されるタスクの持続時間を示す図である。
【図１３】第１のメインフロー変種に対する周期的な静的スケジュールを示す図である。
【図１４】第２のメインフロー変種に対する周期的な静的スケジュールを示す図である。
【図１５】第１のサブフロー変種に対する周期的な静的スケジュールを示す図である。
【図１６】第２のサブフロー変種に対する周期的な静的スケジュールを示す図である。
【図１】
2008542902.tif 000003
【図２】
2008542902.tif 000004
【図３】
2008542902.tif 000005
【図４】
2008542902.tif 000006
【図５】
2008542902.tif 000007
【図６】
2008542902.tif 000008
【図７】
2008542902.tif 000009
【図８】
2008542902.tif 000010
【図９】
2008542902.tif 000011
【図１０】
2008542902.tif 000012
【図１１Ａ】
2008542902.tif 000013
【図１１Ｂ】
2008542902.tif 000014
【図１１Ｃ】
2008542902.tif 000015
【図１２Ａ】
2008542902.tif 000016
【図１２Ｂ】
2008542902.tif 000017
【図１２Ｃ】
2008542902.tif 000018
【図１３】
2008542902.tif 000019
【図１４】
2008542902.tif 000020
【図１５】
2008542902.tif 000021
【図１６】
2008542902.tif 000022
【国際調査報告】
2008542902.tif 000023
2008542902.tif 000024
2008542902.tif 000025