(57)【要約】同一資源（例えばCPU）上で実行されているプロデューサと対応するコンシューマがコンテクストスイッチの総回数が減るようにコンテクストスイッチをすることができる閾値メカニズムを提供する。その閾値メカニズムはバッファに関連し、コンシューマがパケットを削除できる前にプロデューサが所定閾値までのパケットをそのバッファに格納する。バッファには格納可能なパケット数の上限がある。これから作るパケットが無くなった時には残りのパケットをはき出しバッファを空にする。コンテクストスイッチの総回数が減るので、一般にレイテンシは大きくなるが性能はよくなる。
2006525578.tif 000002
【特許請求の範囲】
【請求項１】
パケットのプロデューサの実行コンテクストと前記パケットのコンシューマの実行コンテクストの間のコンテクストスイッチを制御する装置であって、
前記プロデューサによりパケットを格納され、前記コンシューマによりパケットを削除されるバッファと、
前記バッファへのパケットの格納と前記バッファからのパケットの削除に応じてそれぞれ増加および減少するカウントと、
前記カウントに課される、事前設定値とオン・オフ状態とを有する閾値と、
前記カウントの、事前設定値を有する限度と、
（ａ）前記閾値がオンであり、前記カウントが前記閾値の前記事前設定値より小さいとき、前記プロデューサが前記コンシューマの前記実行コンテクストへのコンテクストスイッチを遅らせ、前記コンテクストがスイッチされる前に前記閾値をオフに設定し、
（ｂ）前記閾値がオンであり、前記バッファ中に残ったパケットを前記コンシューマに処理させるためにバッファはき出しが必要であるとき、前記プロデューサが前記コンシューマの実行コンテクストへのコンテクストスイッチするのをやめさせ、前記コンテクストがスイッチされる前に前記閾値をオフに設定する第１の手段と、
前記カウントがゼロであるとき、前記閾値をオンにし、前記プロデューサにコンテクストスイッチを強制する第２の手段と、を有することを特徴とする装置。
【請求項２】
請求項１に記載の装置であって、前記限度の前記事前設定値は前記閾値の前記事前設定値より大きいことを特徴とする装置。
【請求項３】
請求項１に記載の装置であって、前記第１と第２の手段はソフトウェアとして実施されることを特徴とする装置。
【請求項４】
請求項１に記載の装置であって、前記第１と第２の手段は制御論理として実施されることを特徴とする装置。
【請求項５】
請求項１に記載の装置であって、
前記第１と第２の手段はプライオリティベースのスケジューラであり、
前記プロデューサは前記コンシューマよりプライオリティが高いことを特徴とする装置。
【請求項６】
請求項５に記載の装置であって、前記限度の前記事前設定値は前記閾値の前記事前設定値より大きいことを特徴とする装置。
【請求項７】
請求項５に記載の装置であって、前記プライオリティベースのスケジューラはソフトウェアとして実施されることを特徴とする装置。
【請求項８】
請求項５に記載の装置であって、前記プライオリティベースのスケジューラは制御論理として実施されることを特徴とする装置。
【請求項９】
プロデューサによるパケットの作成とコンシューマによる前記パケットの消費を制御する装置であって、
パケットを格納するバッファ記憶と、
制御論理とを有し、
前記バッファは格納されたパケットの数に課せられた閾値と限度とを有し、
前記閾値と前記限度はそれぞれ事前設定値を有し、
前記閾値はオンおよびオフの状態を有し、
前記閾値がオフである時、前記制御論理は、前記プロデューサにパケットを作らせ前記バッファ記憶に格納させ、前記コンシューマへのコンテクストスイッチをさせ、
前記閾値がオンである時、前記制御論理は、前記プロデューサにパケットを作らせ前記バッファ記憶に格納させ、前記バッファ記憶に格納されたパケットの数が前記閾値と等しくなるまで、前記コンシューマへのコンテクストスイッチを遅らせ、その後、前記閾値をオフに設定し、前記コンシューマへのコンテクストスイッチを可能とし、
前記閾値がオンであり、バッファはき出しが必要な時、前記制御論理は、前記閾値をオフに設定し、前記スケジューラに前記コンシューマの実行コンテクストへのコンテクストスイッチをさせて前記バッファ中に残ったパケットを処理し、
前記バッファが空である時、前記制御論理は前記閾値をオンに設定し、前記プロデューサへのコンテクストスイッチを強制することを特徴とする装置。
【請求項１０】
請求項９に記載の装置であって、前記限度の前記事前設定値は前記閾値の前記事前設定値より大きいことを特徴とする装置。
【請求項１１】
パケットのプロデューサのコンテクストとパケットのコンシューマのコンテクストの間でコンテクストスイッチを制御する方法であって、
作られるパケットの数に、事前設定値をそれぞれ有する、オン・オフ状態を有する閾値と限度とを設けるステップと、
前記コンテクストが前記プロデューサのコンテクストであり、前記閾値がオフである時、前記プロデューサが、パケットを作り、前記コンシューマのコンテクストへのコンテクストスイッチを可能とするステップを実行し、
前記コンテクストが前記プロデューサのコンテクストであり、前記閾値がオンであるとき、前記プロデューサが、
（ａ）閾値数のパケットを作り、前記コンシューマのコンテクストへのコンテクストスイッチを可能とするステップと、
（ｂ）閾値数のパケットを作った時に前記閾値をオフに設定するステップと、を実行し、
前記コンテクストが前記コンシューマのコンテクストであるとき、前記コンシューマが、
（ｃ）前記プロデューサにより作られたパケットを消費するステップと、
（ｄ）消費するパケットが無くなった時、
−前記閾値をオンに設定するサブステップと、
−前記プロデューサのコンテクストにコンテクストスイッチするサブステップと、を実行するステップと、を実行することを特徴とする方法。
【請求項１２】
請求項１１に記載の方法であって、前記限度の前記事前設定値は前記閾値の前記事前設定値より大きいことを特徴とする方法。
【請求項１３】
請求項１１に記載の方法であって、
前記プロデューサにより作られたパケットを格納するバッファを備えるステップをさらに有し、
前記作るステップは各々、前記備えられたバッファに前記作られたパケットを格納するステップをさらに有することを特徴とする方法。
【請求項１４】
請求項１３に記載の方法であって、前記限度の前記事前設定値は前記閾値の前記事前設定値より大きいことを特徴とする方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、同一のCPU上にあるプロデューサとコンシューマの間でデータパケットの交換を制御する閾値に関する。特に、処理ノードのグラフに基づくソフトウェアストリーミングに関する。また、同一のCPU上にある２つの処理ノードの間のデータパケットのパスによりブロックされている処理ノードをアンブロックする閾値を設定するシステムおよび方法である。
【０００２】
ソフトウェアストリーミングは処理ノードのグラフに基づく。ここで、ノード感の通信はデータの離散的パケットを用いてなされる。ノードがその入力端から出力端にパケットを転送すると、グラフを通してデータフローができる。各パケットはグラフを通る一定の経路をたどり、ソースノードから始まり、シンクノードで終わる。
【０００３】
同一資源（例えばCPU）上で実行された２つの処理ノードは、真に並行して実行されるわけではない。その資源は、２つのノードの実行を切り替える。これはコンテクストスイッチと呼ばれる。コンテクストスイッチは、すべてのレジスタをセーブしなければならないため、比較的高くつくし、キャッシュを有するCPUではキャッシュをスラッシュ（thrash）するのでなおさら高くつく（スイッチのため場所が無くなる）。
【０００４】
同一の資源上で２つの処理ノード（プロデューサとコンシューマ）が実行され、プロデューサがパケットを作っている時、コンシューマがこのパケットを使う前にコンテントスイッチが必要である。各パケットの後にコンテクストスイッチをする時には、各パケットにつき（往復で）２回のコンテクストスイッチが必要となる。コンテクストスイッチの回数を減らすために、ストリーミンググラフを構成する時にシステムが利用できるオプションがいくつかある。
−パケットサイズを大きくして、パケット生成の頻度を減らす。このオプションには、プロデューサとコンシューマの両方がパラメータ化されたパケットサイズを取り扱えなければならないという欠点がある。このためノードが複雑になってしまう。
−コンシューマにスイッチする前にプロデューサに複数のパケットを作らせる。
【０００５】
プロデューサにコンシューマより高いプライオリティを与えた場合。プロデューサはもはや進めなくなるまで継続する。通常、その理由は、データを入れる空パケットが無くなり、コンシューマに送れなくなることである。そうすると、コンシューマがパケットを使い始められる。コンシューマがパケットを１つ使い、それを再利用のためにリリースするとすぐに、プロデューサが起動される。空パケットがあり、プロデューサの方がコンシューマよりプライオリティが高いからである。そのため、プロデューサに高いプライオリティを与えてもほとんどの場合問題は解決しない。さらにまた、プライオリティは制御対応のためのものであり、このコンテクストスイッチ問題に使用すべきではない。
【０００６】
プロデューサとコンシューマに同じプライオリティを与えた場合。一般的にはラウンドロビンのように処理される。オペレーティングシステムにより使用される時間スライスに応じてコンテクストスイッチが制限される。しかし、複数のタスクに同じプライオリティを与えると、ワーストケースの振る舞い（ワーストケース応答）に悪い影響が出てしまう。そうすると、このオプションでは、コンテクストスイッチのオーバーヘッドと応答が悪くなることとの間のトレードオフが問題となる。
【０００７】
プロデューサがパケットを作っている時、コンシューマがすぐに消費することを防止する閾値メカニズムを設ける場合。また、コンシューマが再利用するパケットをリリースする時、プロデューサはそのパケットをすぐには消費できないようにする閾値メカニズムを設ける。すなわち、プロデューサはパケット量が閾値に達するまで待たなくてはならない。
【０００８】
上に説明したオプションのすべてに共通する欠点は、エンドツーエンドのレイテンシが大きくなることである。これは閾値メカニズムについても言える。
【０００９】
基本的な閾値メカニズムは、ブロックされたコンシューマが、利用可能なパケットが一定の閾値に達した時にアンブロックされるものである。閾値が５のとき（５つのパケットが利用可能な時に初めてコンシューマにパケットが利用可能であることを通知する）、コンテクストスイッチの数はほぼ同じ係数（５）だけ減少する。
【００１０】
このメカニズムはコンシューマがブロックされている時、すなわち、コンシューマがデータパケットを取ろうとして失敗した時に使用される。コンシューマがデータパケット入力でブロックされておらず、閾値の５に達した場合には、メカニズムは使用されない。閾値メカニズムは処理ノードからは独立である。すなわち、処理ノードは閾値が使用されているかどうか、閾値の値はいくつかということについては知らない。システムインテグレータがシステムインテグレーションの際に閾値を決められる。
【００１１】
しかし、閾値メカニズムにはいくつかの欠点がある。
−閾値が大きすぎると、デッドロックしてしまい、
−コンシューマにはパケットが少し残っていることが通知されないので、データパケットが作られ場合、（閾値より少ない）残りのデータパケットは消費されない。
【００１２】
まとめると、コンテクストスイッチを制限する閾値に関する現在の技術水準は、
−上で説明したように、一般的な閾値、
−データパケットのパス
−データパケット同期、および
−データパケット閾値が使用された時、コールバック機能が起動される。
【００１３】
本発明の閾値メカニズムは、プロセッサ上で行われるデータパケットのパスの結果であるコンテクストスイッチの数を減らすための有効な手段である。コンテクストスイッチの数が減れば、プロセッサの使用がより効果的になる。本発明による閾値メカニズムは、処理ノードには見えないので、ノード内部の複雑性が高くなることはない。
【００１４】
本発明は、ブロックされた処理ノードをアンブロックする閾値を提供することにより、上に説明した欠点を解決し、コンテクストスイッチのオーバーヘッドを減らす。また、本発明は、デッドロックまたはバッファ中でデータが動けなくなることを防止するメカニズムにより、拡張することもできる。拡張の例としては、閾値がコンシューマへの通知を遅らせることができる最大時間を決定する閾値のタイムアウトや、システムが「アイドル」状態になった場合にすべての閾値を削除する、プライオリティが低いシステム中の追加タスクなどがある。
【００１５】
本発明のシステムと方法により、プリエンプティブなプライオリティベースのスケジューラを用いてプライオリティが高いストリーミングコンポーネントにパケットを送る結果生じるコンテクストスイッチの数を減少させる。コンテクストスイッチの数を減らすと、一般に、レイテンシが大きくなる替わりに性能がよくなる。好ましい実施形態において、バッファ閾値は、バッファに十分なパケットが利用可能となるまで、すなわちバッファに閾値量のパケットが蓄積されるまで、パケットを待ってブロックされているコンシューマコンポーネントへの合図を遅らせるメカニズムである。バッファの閾値をｘとした時、そのバッファと関連する、待っているすなわちブロックされているコンポーネントには、ｘ個のパケットがバッファ内に蓄積された時にのみ合図がされる。
【００１６】
図１は、バッファコンポーネント１２０を介してプライオリティが高いコンシューマコンポーネント１１０に接続されたプライオリティが低いプロデューサコンポーネント１００を示す図である。すべてのコンポーネントは同一プロセッサ上にある。図２ａは、データパケットがすぐにパス、すなわち作られて消費される時の、図１に示したバッファコンポーネント１２０のフィリング（filling）を示している。すなわち、プロデューサコンポーネント１００がバッファ１２０にパケットを入れると、コンポーネント１００はすぐにコンシューマコンポーネント１１０により取って代わられる（pre-empted）（コンシューマコンポーネント１１０は実行準備ができていると仮定する）。コンシューマコンポーネント１１０の用意ができていて、新しい入力を待っている時、プロデューサコンポーネント１００が再び実行される。図２ａに示したように、この通信の結果としてコンテクストスイッチ２００の数は、パケットをパスする頻度に応じて変わる。図２ｂは、バッファが関連する閾値５を有すること以外の状況は同じである。コンテクストスイッチ２１０の回数は、ほぼ５に等しい係数だけ減っている。この減少は、コンシューマコンポーネント１１０がまず５つの利用可能パケットをバーストで消費し、新しい入力を待ち、そうするとすぐにプロデューサコンポーネント１００が再実行されるからである。プロデューサコンポーネント１００は、コンシューマコンポーネント１１０により取って代わられる前に５つのパケットを作ることができる。図２ａと２ｂ両方にある不規則性は、コンシューマコンポーネント１１０が、バッファ中にフィリングされたパケットが利用可能であることを通知された時に、例えばコンシューマコンポーネント１１０の結果で空パケットが無いなど何らかの理由で実行準備できていないことが原因である。
【００１７】
バッファに関連した閾値に達しない限り、コンシューマコンポーネントはそのバッファ中のパケットを利用可能ではない。例えば、プロデューサへの入力ファイルが終了してしまうなどの理由で、プロデューサコンポーネント１００によりバッファコンポーネント１２０に格納されたパケットがコンシューマコンポーネント１１０に利用可能とならないことがある。この場合、付加的予防措置を講じて、バッファ１２０中に残っているパケットをはき出す（すなわち、コンシューマに処理させる）ことを保証する。
【００１８】
大きすぎるバッファ閾値を使用して、例えば、作られたパケットの数が不十分でバッファ閾値に達しないようなデッドロックに至らないように予防措置が必要である。基本的な例として、４つのパケットがシステムを循環しているとき、閾値を５に設定すると、その閾値には決して達しないので、システムがロックアップする。そこで、基本的なルールとして、閾値は作られたパケットの数以下でなければならない。より複雑なシステムにおいて、パケットが利用可能かどうかは、他のパケットが利用可能かどうかに応じて決まる場合、この簡単なルールだけでは十分ではなく、複数の閾値を考慮したより複雑なルールが必要となる。
【００１９】
また、バッファ閾値の選択により、その閾値の使用の結果生じるチェーンのレイテンシの増加を最小化するべきである。ほぼすべての場合において、レイテンシは低い方が望ましい（例えば、オーディオは１ないし２ミリ秒遅れてもエンドユーザは気がつかない）ので、システムを循環しているパケットが１０個ある場合、閾値は最大１０とすることができるが、低レイテンシの要請により閾値の設定はこれより低くなる。これはコンテクストスイッチのオーバーヘッドに関しては必ずしも最適ではない。
【００２０】
最初、バッファ閾値はアクティブではない。コンポーネントがブロックされるか、またはファイルの最後に到達した場合、そのチェーンを通じて特別なコマンドパケットが送られ、バッファコンポーネント１２０により保持されたパケットをはき出す。３つのパケットを保持でき、閾値が２に設定されたバッファのとりうる状態を図３に示した。以下の状態遷移が可能である。
−put  310：パケットがセンダーによりバッファに加えられる。
−get  320：パケットがレシーバによりバッファから成功裏に削除される。
−get_that_fails  330：コンシューマがバッファからパケットを取得しようとするが、バッファが空のため失敗する。これにより閾値メカニズムが起動される。
−flush  340：flushコマンドが閾値を不活化するので、コンシューマは閾値に達していなくてもパケットを取得することができる。
−notify  consumer  350：閾値に達し、コンシューマはバッファからパケットを取得開始することができる。
【００２１】
get_that_fails遷移の後、コンシューマは２つのパケットがバッファに格納されたと通知されるまでスケジュールされないので、コンテクストスイッチが防止される。この状態図を容易に拡張して、バッファを大きくしたり閾値を高くしたりすることができる。
【００２２】
ここに説明した本発明の実施形態はソフトウェアとして実施することが好ましいが、上に説明した実施形態の全部または一部をディスクリートのハードウェア要素及び／または論理回路を用いて実施することもできる。
【００２３】
これに関して、本発明を特定の実施形態に関して説明した。当然のことながら、本発明は上で説明した実施形態やその修正に限定されるものではなく、当業者は添付した請求項の精神と範囲から逸脱することなく、いろいろな変更や修正をすることができる。
【図面の簡単な説明】
【００２４】
【図１】バッファコンポーネント１２０を介してプライオリティが高いコンシューマコンポーネント１１０に接続されたプライオリティが低いプロデューサコンポーネント１００を示す図である。
【図２】ａは、閾値を使用していない時に、図１のプライオリティが高いコンシューマコンポーネントのためにバッファしているプライオリティが低いプロデューサコンポーネントのコンテクストスイッチ２００とバッファフィリングを示す図であり、ｂは、閾値５を使用している時に、図１のプライオリティが高いコンシューマコンポーネントのためにバッファしているプライオリティが低いプロデューサコンポーネントのコンテクストスイッチ２００とバッファフィリングを示す図である。
【図３】３つのパケットを保持できるバッファに関連して閾値２を有する、本発明の実施形態を示す状態遷移図である。
【図１】
2006525578.tif 000003
【図２】
2006525578.tif 000004
【図３】
2006525578.tif 000005
【国際調査報告】
2006525578.tif 000006
2006525578.tif 000007
2006525578.tif 000008
2006525578.tif 000009