(57)【特許請求の範囲】
【請求項１】
信号処理装置であって、
−  複数の処理要素と、
−  前記複数の処理要素への及びこれら処理要素からの入力端子及び出力端子と、
−  前記入力端子と前記出力端子との間に結合され、前記処理要素上で並列に実行する一群の処理の間での信号ストリームの伝送のために前記入力端子と前記出力端子との間で２以上の選択可能な接続を同時になすのに適したスイッチマトリクスと、
−  前記スイッチマトリクスによりなされる前記接続を選択する仲裁器であって、該仲裁器は前記信号ストリームの所定の部分を伝送するために、互いに接続されるべき入力端子と出力端子との各割り付けを連続するタイムスロットの各々においてなし、該仲裁器は前記一群の処理の間での信号ストリームの前記伝送のため前記各割り付けを複数のタイムスロットにわたって予め固定するような仲裁器と、
を有するような信号処理装置において、
前記仲裁器は、前記複数のタイムスロットの間における他の処理の間での他の伝送のために特定の入力端子と出力端子との間の他の接続をなすための要求を入力すると共に、前記特定の入力端子及び出力端子が前記割り付けの予め固定された信号ストリームの伝送用の前記一群の処理によっては使用されないタイムスロットにおいて前記他の接続の実行を選択するよう構成されていることを特徴とする信号処理装置。
【請求項２】
請求項１に記載の信号処理装置において、前記部分の各々がタイムスロットにおいて入力端子と出力端子との間で伝送される信号ストリームの連続した少なくとも２つのサンプルを有していることを特徴とする信号処理装置。
【請求項３】
請求項１に記載の信号処理装置において、前記仲裁器は前記の各割り付けを、これら割り付けが周期的サイクル内で繰り返されるように固定することを特徴とする信号処理装置。
【請求項４】
請求項３に記載の信号処理装置において、前記周期的サイクル内で各信号ストリームに関して割り付けられるタイムスロットの各数が、これら各信号ストリームの帯域幅に従って相違していることを特徴とする信号処理装置。
【請求項５】
請求項１に記載の信号処理装置において、前記仲裁器は、予め固定されている前記各割り付けの組み合わせを、機器の動作中に並列に実行する前記処理の組み合わせが変化する際に、変化させるように動的に再プログラム可能となっていることを特徴とする信号処理装置。
【請求項６】
請求項５に記載の信号処理装置において、少なくとも１つの処理要素は、各々が少なくとも該１つの処理要素により実行される処理に入力される各ストリームからの連続した信号サンプルを入力するような複数のＦＩＦＯバッファを保持するように構成され、各処理の実行が、当該処理用の信号サンプルが前記スイッチマトリクスを介して伝送されるタイムスロットから独立とされることを特徴とする信号処理装置。
【請求項７】
請求項６に記載の信号処理装置において、前記少なくとも１つの処理要素は、各々が各処理の処理状態を記憶する複数の状態メモリを有し、該処理要素は前記各処理を前記状態メモリ及び前記ＦＩＦＯバッファを切り換えることにより切り換えることを特徴とする信号処理装置。
【請求項８】
請求項７に記載の信号処理装置において、前記少なくとも１つの処理要素は、割り付けが前記スイッチマトリクスを介しての特定の処理の出力用に供される場合に、各タイムスロットにおいて該特定の処理に切り換えることを特徴とする信号処理装置。
【請求項９】
同時並行的な処理を実行する処理要素の入力端子と出力端子とがスイッチマトリクスを介して相互に接続されるようなタイムスロットの割り付けを計画する方法において、
−  タイムスロットの基本周期からの各タイムスロットに対して計画されるべき入力端子−出力端子接続のリストを編集するステップと、
−  前記リストから一群の接続を、各入力端子及び各出力端子が該群内の接続の中で多くても１度だけ発生し、特定の入力端子又は出力端子が前記基本周期内で前記リスト上の接続の中で発生する如何なる他の入力端子又は出力端子よりも少なくはない数のタイムスロットにおいて接続されなければならない場合は、該特定の入力端子又は出力端子が前記一群の接続内に含まれるように、検索するステップと、
−  特定のタイムスロットにおける前記割り付けを、前記群内の全ての入力端子−出力端子接続が該タイムスロット内で発生するように設定するステップと、
−  前記検索するステップと前記設定するステップとを、前記特定のタイムスロット外で計画されたままである前記接続に対して繰り返すステップと、
を有していることを特徴とするタイムスロットの割り付けを計画する方法。
【発明の詳細な説明】
技術分野
本発明は、請求項１の前置特徴部による信号処理装置、及びスイッチマトリクスを介してプロセッサの入力端子と出力端子との間の接続がなされるタイムスロットの割り付けを計画する方法に関する。
背景技術
このような信号処理装置は、米国特許第5103311号から既知である。この装置は、ビデオ信号処理タスクの種々の段階を真に同時並行的に実行する多数の処理要素を有している。一つの処理要素は、入力端子において信号ストリームの信号サンプルを入力し、これら信号サンプルを処理し、処理された信号ストリームの信号サンプルを出力端子において出力する。これらストリームはスイッチマトリクスを介して処理要素間で伝送されるが、該スイッチマトリクスは、各々が或る処理要素の入力端子と該処理要素の入力端子への信号ストリームの信号源の出力端子との間であるような、多数の接続を並列に確立する。上記信号源は他の処理要素であってもよいし、又は当該装置の入力端子であってもよい。
各処理要素は自身のプログラムを有している。処理要素のプログラムは、何の他の処理要素からスイッチマトリクスを介して信号ストリームのサンプルが入力されるかを決定する。
上記処理要素の多くが、幾つかの処理を時間インターリーブされた態様で実行することができる。これを支援するため、上記スイッチマトリクスによりなされる接続は、異なる信号源からの異なる信号ストリームのサンプルを入力するように規則的に切り換えられる。これらの切り換えも処理要素内でプログラムされている。この場合、なされる全ての接続は、処理の実行に充分に先立って、上記プログラムにおいて仲裁されている。このようにして、上記スイッチマトリクス及び処理要素の使用効率は、プログラミングの時点で最適化することができ、リアルタイム動作が保証され得る。
しかしながら、プログラムされた仲裁は、信号処理装置が信号ストリームの種々の組み合わせが異なる態様で（それらの幾つかは対話的に）扱われられなければならないようなマルチメディアアプリケーションを扱うのに必要とされる柔軟性に欠けるという欠点を有している。
１９８９年のＡＣＭオペレーティングシステムレビュー２３（３）の第１４１〜１５１頁にＡ・ダム、Ｊ・ライジンガ、Ｗ・シュワブル及びＨ・コペッツにより掲載された“Ｍａｒｓのリアルタイムオペレーティングシステム”なる題名の論文は、プロセス制御用に設計された分散型のリアルタイムデータ処理システムを教示している。このシステムは、全ての入力端子及び出力端子が接続された単一バスを使用している。リアルタイム動作は、該バスを所定のタイムスロット内で厳しいリアルタイムメッセージの伝送に割り付けることにより保証されている。また、該バスは、要求に応じて、不使用タイムスロット内で厳しいリアルタイムメッセージ以外に割り付けられる。このことが、上記入力端子及び出力端子が、当該バスが割り付けられた場合に伝送用に利用することが可能となることを自動的に保証している。何故なら、バスの場合はスイッチマトリクスの場合とは対照的に、入力端子及び出力端子が、種々の連続した伝送に割り付けられるような単一情報チャンネル専用であるからである。
発明の開示
本発明の目的は、なかでも、処理要素及びスイッチマトリクスの使用の効率が最適化され、多数の信号ストリームに対してリアルタイム動作が保証され、それでいて信号ストリームの扱いにおける一層の柔軟性を可能にするような信号処理装置を提供することにある。
本発明による信号処理装置は、請求項１の特徴部分により特徴付けられる。本発明は一群の処理に対して固定した接続の割り付けを行うので、これら処理の効率を最適化することができると共に、リアルタイム動作が保証される。好ましくは、タイムスロットは周期的な繰り返しパターンで割り付けられるものとし、これは小さなメモリでプログラムすることができる。当該仲裁器は、関連する処理による実行時の要求に応じて、タイムスロットの持続期間の間に他の接続をなすこともできる。これらの接続は、接続が予め割り付けられている上記一群の処理によっては使用されない入力端子及び出力端子の間でなされる。使用されない入力端子及び出力端子は、例えば、これらの入力端子及び出力端子が予め割り付けられていないか、又は割り付けられた入力端子及び／又は出力端子がその時点で上記一群の処理によっては実際に使用されていないことを上記処理要素が示す故に発生する。
本発明による処理装置の一実施例が請求項２に記載されている。この実施例によれば、上記スイッチマトリクスは、２以上の信号値を伝送することができるが、全体のストリーム（又はビデオ）のフレームよりも大幅に少ないような期間にわたって入力端子と出力端子との間の接続を常に維持する。これは、当該装置による電力消費を減少させる。何故なら、上記スイッチマトリクスがより少ない頻度でしか切り換える必要がないからである。同時に、これは、上記処理要素の効率的な利用を保証する。何故なら、処理の間の柔軟な切り換えを可能にするからである。
本発明による処理装置の一実施例においては、タイムスロットの割り付けがプログラム可能となる。このように、使用者が本装置の異なる機能を必要とする場合は、当該装置により実行される上記一群の処理を変更することができ、新たな組の処理に対して最適であるような割り付けを、仲裁器により実施することができる。
本発明による処理装置の他の実施例においては、異なる処理を実行するために、処理要素に到来する異なるストリームに対して先入先出バッファが使用される。このようにして、割り付けの計画は上記異なる処理の実行のタイミングに無関係になすことが可能であるから、最適な計画を使用することができる。
請求項９は、タイムスロットの割り付けを、上記スイッチマトリクスの伝送容量を完全に利用することができるような態様で計画する方法を記載している。
【図面の簡単な説明】
本発明の上記及び他の有利な特徴を、以下の図面を用いて非限定的に説明する。
第１図は、信号処理装置を示す、
第２図は、タスクグラフを示す、
第３図は、周期的割り付けの一例を示す、
第４図は、処理要素を示す、
第５図は、割り付け計画アルゴリズムのフローチャートを示す、
第６図は、仲裁器を示す。
発明を実施するための最良の形態
第１図は信号処理装置を示す。該信号処理装置は、スイッチマトリクス１２により相互接続された多数の処理要素１０a-f（これらのうちの６個が示されている）を有している。伝送仲裁器１４は、上記スイッチマトリクスによりなされる接続を選択するために、処理要素１０a-fと該スイッチマトリクスとへの接続部（図示略）を有している。加えて、当該装置は、中央プロセッサ１８と、上記処理要素１０a-f、仲裁器１４及び該中央プロセッサ１８を接続する制御指向のバス１６とを有している。
動作時において、当該信号処理装置は、例えば、多数のビデオ信号を同時に処理する。これらビデオ信号は連続したピクセル値のストリームとして実現される。処理要素１０a-fは、例えば、外部入力ビデオ信号からの又はグラフィックス処理による入力ストリームのピクセル値を処理することにより導出される斯かるピクセル値のストリームを生成することができる。また、ピクセル値のストリームは処理要素１０a-fに入力することもでき、該ストリームは当該処理要素１０a-fにより実行される何らかの所定の処理に従って処理される。通常、処理された信号ストリームの連続するピクセル値の各々は、入力信号ストリームの連続するピクセル値の各々に又はピクセル値の連続するスライディングウィンドウに依存する。
処理要素１０a-fにより実行される処理の典型的な例は、個々に、ビデオ信号ストリームの水平方向解像度の低減、ビデオ信号ストリームの垂直方向解像度の低減、フィルタ動作、ＭＰＥＧ復号等、即ちパイプラインの間には殆ど交差接続はないが、それら自身では入力されたビデオ信号と表示されるビデオ信号との間の完全な入出力関係をしばしば構成しないような粒状度のレベルでの処理、を含む。これら処理の殆どは、厳しいリアルタイム制約条件を満たす必要がある。何故なら、これらの処理は直接的に又は間接的に結果として、可視的な障害を避けるために時間内に表示されねばならない出力画像となるからである。テレテキスト画像の構築のような他の処理は、厳しいリアルタイム制約条件を満たす必要はないが、保証された平均速度で動作しなければならない。
第２図は、仮想の単純な信号処理タスクのタスクグラフを示す。該タスクグラフは、処理要素１０a-fにより実行されるべき多数の処理“input”（２ｘ）、Ｔ１〜Ｔ７及び“output”を記号的に表すためにノード２０a-c、２２a-c、２４a-c、２６を使用している。また、該タスクグラフは、これら処理の間の信号ストリームＣ１〜Ｃ６、Ａ７、Ａ８の伝送を表すために、ノード２０a-c、２２a-c、２４a-c、２６の間の接続２１a-c、２３a-c、２５a-cを使用している。また、該タスクグラフは、共通の出力処理に集束する３つのパイプラインの処理Ｔ１〜Ｔ７を示している。斯かるタスクグラフにより実行される機能の一例は、例えば、重ねられたグラフィック画像を伴う、２つの異なるビデオ信号の同時的表示である。
複数の接続２１a-c、２３a-cは、信号ストリームＣ１〜Ｃ６の対応する伝送が厳しいリアルタイム制約条件を満たす必要があることを示すために実線で示されている。他の接続２５a-cは、他の信号ストリームＡ７、Ａ８に対しては厳しいリアルタイム制約条件を満たす必要がないことを示すために点線で示されている。これら信号ストリームにより必要とされる帯域幅は異なり得る。例えば、或るストリームＣ１の帯域幅は、該ストリームＣ１が高い解像度の画像を表す場合は、他のストリームＣ２〜Ｃ６の各々に関して個々に必要とされるものの２倍であり得る。
動作時には、種々の処理Ｔ１〜Ｔ７は処理要素１０a-fにより実行される。処理要素１０a-cの各々においては、数個の処理Ｔ１〜Ｔ７を時間インターリーブ態様で実行することができる。例えば、２つの処理Ｔ２、Ｔ３が第１処理要素１０aにより実行され、他の処理Ｔ１、Ｔ４が他の処理要素１０b,cにより実行されることもある。入力処理“input”は２つの別個の入力プロセッサ１０d,e上で実行し、出力処理は別個の出力プロセッサ１０f上で実行することができる。
数個の処理要素１０a-fが１以上の処理を時間インターリーブ態様で実行することができるので、これら処理要素１０a-fは、それらの入力端子で１以上の異なる処理要素１０a-fからピクセル値を受信するか、又はそれらの出力端子から１以上の異なる処理要素１０a-fへピクセル値を送信する必要がある。上記例においては、処理Ｔ２及びＴ３を実行する処理要素は、処理Ｔ１及び入力処理を各々実行する処理要素からピクセル値を受信する必要がある。また、処理Ｔ２及びＴ３を実行する処理要素は、出力処理要素及び処理要素Ｔ４等に対して出力する必要がある。
このことは、これら処理の間の信号ストリームＣ１〜Ｃ６の伝送がスイッチマトリクス１２を介してなされる時間間隔に関して制約を課すことになる。何故なら、信号ストリームは或る処理要素１０a-fの１つの入力端子に１以上の信号源から同時に到達することはできず、また、信号ストリームは或る処理要素１０a-fの１つの出力端子から１以上の宛先に同時に送信することもできないからである。（伝送上への斯かる制約を避けるために、略全ての処理要素１０a-fに、当該処理要素により時間インターリーブ態様で実行される全ての異なる処理に関して、スイッチマトリクス１２に接続された別個の切り換え可能な入力部及びバッファを設ける必要があるであろう。しかしながら、別個の切り換え可能な入力部は、非常に少数であるが全ての処理が時間インターリーブ態様で実行されるならば、著しく大きな集積回路チップ面積を必要とすることが分かった。従って、このような制約を避けることは望ましいものではない。）
これらの制約の下での信号ストリームＣ１〜Ｃ６のリアルタイムな伝送を保証するために、スイッチマトリクス１２の使用がタイムスロットに分割される。各タイムスロット内では、スイッチマトリクス１２は入力端子と出力端子との間の或る組み合わせの接続をなす。この接続の組み合わせは、一つのタイムスロットから次のタイムスロットへと変化させることができる。好ましくは、各タイムスロットは多数の連続したピクセル値の伝送を可能にする。これはスイッチマトリクス１２における電力消費を減少させる。何故なら、ビデオストリームにおいては、１つの信号ストリームの連続したピクセル値の間の方が、異なる信号ストリームのピクセル値の間よりも、少ない信号遷移しか必要とされない傾向にあるからである。一方、１以上の処理を同一の処理要素１０a-f上で過度に大きなバッファを使用することなくリアルタイムで実行することができるように、各タイムスロットはビデオフレーム全体よりも遙かに少ない伝送を可能にする。６４Ｍｈｚなるピクセル周波数（クロック周波数）の場合、タイムスロット当たり１６ピクセル値が良い妥協点であることが分かった。
仲裁器１４は、上記スイッチマトリクスが何の接続をなすかを選択する。処理Ｔ１〜Ｔ７の実行の前に、信号ストリームＣ１〜Ｃ６への接続の割付が、これら信号ストリームのリアルタイム伝送が保証されるような形で各タイムスロットに対して計画される。計画は、プログラムがコンパイルされる際に、即ち処理が実際に実行される前に、なすことができる。好ましくは、上記割付はビデオフレームを処理するのに要する合計時間間隔より大幅に短い繰り返し周期で周期的に繰り返されるようにする。各周期においては、多数のタイムスロットが各信号ストリームＣ１〜Ｃ６に対して、当該信号ストリームに必要とされる帯域幅（単位時間当たりのピクセル値）に比例して割り付けられる。
第３図は、このような周期的な割付のマトリクスにより表された一例を示している。該マトリクスの順次の行は周期内の順次のタイムスロットに対応している。一番左側の３つの列は処理要素１０a-fの種々の入力に対応し、一番右側の４つの列は処理要素１０a-fの種々の出力に対応している。該マトリクスにおいては、何の信号ストリームＣ１〜Ｃ６に対して各入力端子又は出力端子が各タイムスロットに割り付けられるかが示されている。例えば、第１タイムスロット（上側の行）においては第１入力端子は信号ストリームＣ１に割り付けられ、第２入力端子は信号ストリームＣ３に割り付けられている。また、第２出力端子は信号ストリームＣ３に割り付けられ、第３出力端子は信号ストリームＣ１に割り付けられている。第２、第３及び第４行は、第２、第３及び第４タイムスロットの各々において、何の信号ストリームＣ１〜Ｃ６に入力端子及び出力端子が割り付けられるかを示している。第５、第６、第７及び第８タイムスロットにおいても、入力端子及び出力端子は、該マトリクスの第１、第２、第３及び第４行に示されるのと同様に割り付けられ、等々である。このようにして、割付は４つのタイムスロットの周期で繰り返される。
入力端子及び出力端子が各周期における２つのタイムスロット内で第１信号ストリームＣ１に割り付けられ、他の信号ストリームＣ２〜Ｃ６に関しては１つのタイムスロット内で１つの入力端子と出力端子とが割り当てられていることが分かるであろう。これは、Ｃ１の帯域幅が他のストリームＣ２〜Ｃ６のものの２倍であるからである。
処理要素１０a-fは、入力された信号値を使用する処理を、各周期内で平均して入力されたのと丁度同じくらい多くの信号値が処理されるように、実行する。しかしながら、実行は必ずしも伝送とロックステップにある必要はない。処理要素１０a-fは、これを、信号ストリームに関して伝送される信号値をバッファリングすることにより達成することができる。同様にして、処理要素１０a-fは、これら処理により発生された信号ストリームの信号値をバッファする。バッファには最大でＭ個の信号値が記憶される必要があり、ここで、Ｍは１周期内で、即ち割り付けが繰り返される前に伝送することが可能な信号値の数である。これら信号値の処理を開始する時点が注意深く選定される場合は、Ｍ／２の信号値に対する一層小さなバッファでさえ充分である。周期が長すぎない場合は、比較的小さなバッファで、既に、充分な信号値を常に記憶することができることが保証される。
第４図は、２つの入力端子と１つの出力端子とを備える処理要素の一例を示している。該処理要素は２つの入力端子を備えるプロセッサ４０を有している。該処理要素は、プロセッサ４０の各入力端子に入力ＦＩＦＯ（先入先出）ユニット４２及び４４を介して結合された２つの入力端子を有している。入力ＦＩＦＯユニット４２、４４は、当該処理要素により実行される各処理に対して１つずつの多数の論理ＦＩＦＯバッファ４２２、４２４を備えている。実際には、これらＦＩＦＯはＦＩＦＯ態様でアドレス指定されるメモリとして構成することができ、上記論理ＦＩＦＯは同メモリを共用することができる。デマルチプレクサ４２０は、前記スイッチマトリクスに結合された入力端子から入力される信号値を適切なＦＩＦＯバッファ４２２、４２４に指向させる。プロセッサ４０は、当該処理要素の前記単一の出力端子に出力ＦＩＦＯユニット４６を介して結合された１つの出力端子を有している。上記出力ＦＩＦＯユニットは、実行される各処理につき１つずつの多数の論理ＦＩＦＯバッファ４６０、４６２を保持している。ＦＩＦＯバッファ４６０、４６２の出力は、ルータ４６４を介して前記スイッチマトリクスに指向される。ＦＩＦＯバッファ４６０、４６２は例えば別個のＦＩＦＯとしても構成することができ、又は異なるＦＩＦＯからの信号値用の１つのメモリと異なる論理ＦＩＦＯバッファ用に使用されるメモリロケーションを追跡するための多数のポインタとにより構成することもできる。
プロセッサ４０は、無状態処理ロジック部４００（“無状態”：何れの時点における出力信号も１つの時点での入力信号のみに依存し、それ以上の入力又は出力信号には依存しない）と、当該処理要素によりインターリーブ態様で一緒に実行することができる各処理につき１つずつの多数の状態メモリ４０２、４０４とを有している。異なる処理の実行の間の切り換えは、上記無状態処理ロジックへ入力を供給する入力バッファ４２２、４２４と、上記状態メモリとを切り換えることにより達成される。このように、異なる処理の間の切り換えは、如何なる待ち状態を伴わずに実現することができる。各ストリームからの信号値は、通常、それらが到達する順に処理されるが、異なる処理の間の切り換えは異なるストリームに関する信号値の到達に正確に従う必要はない。即ち、異なるストリームからの信号値の処理は、到達順である必要はない。
入力端子及び出力端子の各タイムスロットにおけるリアルタイム処理Ｔ１〜Ｔ７の信号ストリームＣ１〜Ｃ６への割り付けは、リアルタイム仕様を満たすために前もって計画され、これはプログラムがコンパイルされる際又は処理が開始する前の実行時においてなすことができる。該リアルタイム仕様は、処理Ｔ１〜Ｔ７に関わる信号ストリームＣ１〜Ｃ６の所要の帯域幅として、例えば何らかの時間単位における当該処理に要するタイムスロットの数の形で表される。該計画は、全ての信号ストリームＣ１〜Ｃ６に対して、入力端子及び出力端子並びにスイッチマトリクス１２の両方が信号ストリームＣ１〜Ｃ３を伝送するために各周期において充分な数のタイムスロットにわたって利用可能であることを保証するものでなければならない。
好ましくは、スイッチマトリクス１２に接続される入力端子又は出力端子の数Ｍ（どちらか少ない方）と同じ数だけの接続を同時に設けることができるようなスイッチマトリクス１２が使用される。もっと一般的には、該スイッチマトリクスは、単位時間当たりＭ個の入力端子へ又は出力端子から信号値を伝送するために、これらＭ個の入力端子又は出力端子の後又は前のプロセッサが単位時間当たりに処理することができるのと少なくとも同じくらい大きな帯域幅を備えなければならない。かくして、該スイッチマトリクスは上記割り付けに対して制限を課すことはなく、全ての信号ストリームＣ１〜Ｃ６に対して入力端子及び出力端子の両方が充分な数のタイムスロットにわたって利用可能であることのみが保証されなければならない。
時間単位当たりに利用可能なタイムスロットの数Ｋは、特定の信号ストリームＣ１〜Ｃ６に対して必要とされる入力端子及び出力端子の両方が同時に空きであるようなタイムスロットを常に見付けることができることを保証するために、充分に大きくなくてはならない。入力端子及び出力端子が一連の信号ストリームに対して増分的に割り付けられる場合は、上記数Ｋは、１つの入力端子に流れ込む全ての信号ストリームＣ１〜Ｃ６により実際に使用されるタイムスロットの数Ｎの２倍に−１を加えたもの以上でなければならない（Ｋ＞＝２Ｎ−１）ことが分かった。増分的計画においては、上記割付は先ず信号ストリームＣ１〜Ｃ６の部分集合に関して計画され、次いで、入力端子及び出力端子が上記部分集合以外の特定のストリームに対して、これら入力端子及び出力端子の両方が依然として空きであるようなタイムスロットで割り付けられる。この場合、上記特定の信号ストリームにより必要とされる入力端子及び出力端子の両方が、最悪の場合でも、上記Ｋ個のタイムスロットのうちの１つのタイムスロットで空きであることを保証するために、上記数Ｋに対する下限が必要である。上記最悪の場合とは、上記出力端子が、上記入力端子が他の信号ストリームＣ１〜Ｃ６に割り付けられる全ての（Ｎ−１）個のタイムスロットとは異なる（Ｎ−１）個のタイムスロットにおいて他の信号ストリームに割り付けられる場合である。
しかしながら、Ｋ＝Ｎの場合でさえも、割り付け方法が実際に存在することが保証され得ることが分かった。斯かる割り付け方法を見付けるために、リアルタイム仕様を満たすため全てのタイムスロットＫで信号ストリームを伝送しなければならないような全ての入力端子及び出力端子が含まれる異なる入力端子及び出力端子間の信号ストリームＣ１〜Ｃ６用の接続の組み合わせを捜すことから開始されるであろう。このような接続の組み合わせは常に存在するであろうことを証明することができる。この証明は、割り付け問題のグラフ理論の形での再定式化を使用する。各々が各入力端子又は出力端子に対応するノードを備えるグラフが使用される。各入力端子−出力端子対に対応するノードの間には、時間単位内で該タイムスロットが存在するのと同じ数だけのエッジが該グラフに含まれる。この段落の始めで述べた捜された接続の組み合わせは、該グラフのエッジの部分集合に対応し、該部分集合においては１以下のエッジが何れかのノードに接続され、該部分集合には当該グラフの最大数のエッジに接続された全てのノードが接続される。１９３４年にロンドン数学協会の協会誌第１０巻の第２６〜３０頁に公表されたＰ・ホールによる“部分集合の表現について”なる題名の論文に述べられているグラフ理論からの定理は、常に上記のような部分集合が存在することを示している。
第５図は、処理要素１０a-fの入力端子及び出力端子の異なるタイムスロットでの異なる信号ストリームへの割付を計画するアルゴリズムのフローチャートを示している。第１ステップ５０において、タイムスロットカウントＫ１がＫに初期化される。Ｋ個のタイムスロットにおいて何れかのストリームＣ１〜Ｃ６により接続が必要とされる入力端子−出力端子対のリストが、各タイムスロットに対して１つの対を含むように準備される。第２ステップ５２において、該リストが空であるかが判定され、もしそうなら、該計画は終了され、もしそうでないなら、当該アルゴリズムは第３ステップ５４に進む。第３ステップ５４において、当該アルゴリズムは信号ストリームＣ１〜Ｃ６に関する入力端子−出力端子対のリストの第１部分集合を検索する。該検索は或る条件を満たす第１部分集合に限定される。該第１部分集合の対の全てにおいて、各入力端子及び各出力端子は１回のみ発生することができ、該リスト上の対のＫ１において発生する全ての入力端子及び出力端子は該第１部分集合に含まれなければならない。前述した証明は、このような第１部分集合が、例えば全ての可能性のある部分集合の全数検索を使用することにより、又は１９７３年のＳＩＡＭ  Ｊ．Ｃｏｍｐｔ．第２巻、第４号のＰ・ホールによる論文、並びにＪ・Ｅ・ホプクロフト及びＲ・Ｍ・カープによる“２部グラフにおける最大マッチング用n^(5/2)アルゴリズム”なる題名の論文に記載されているようなアルゴリズムをカバーする多項式時間グラフを用いることにより見付けることができることを保証している。該第１部分集合は、各時間単位における第１タイムスロットにおいてなされるであろう接続に対応する。
第４ステップ５６においては、該アルゴリズムは上記第１部分集合の対を上記リストから削除し、Ｋ１をデクリメントする。その後、該アルゴリズムは第２ステップ５２からを繰り返す。各繰り返しにおいて、第３ステップは他のタイムスロットに対する割付を生成する。Ｋ回の繰り返しの後には、上記リストには更なる接続は残存していないであろう。
このアルゴリズムは、仲裁器１４により実施された場合、スイッチマトリクス１２に接続される入力端子及び出力端子が厳しいリアルタイム制約条件を満たすことができるよう充分な数のタイムスロット内で種々のストリームに割り付けられるであろうことを保証するような割り付け計画を作成する。厳しいリアルタイム制約条件を満たさねばならないストリーム用には使用されない残りのタイムスロットにおいては、厳しいリアルタイム制約条件を満たす必要がない他のストリームを伝送することができる。仲裁器１４は、これら残りのタイムスロットを処理要素１０a-fからの要求に応じて割り付ける。処理要素は、斯様な“他の”ストリームに関する信号値がある場合に要求を送出し、仲裁器１４は、該“他の”ストリームの伝送に必要とされる入力端子及び出力端子が、例えば、該入力端子及び出力端子が割り付けられていない又は割り付けられたタイムスロットが使用されていない等の理由で、タイムスロット内で使用されていない場合は、このような要求を受諾する。
Ｋ＝Ｎが常に可能であることを保証するために、上記割付は、プロセッサへの信号値の入力と該プロセッサからの処理された信号値の出力との間の時間差に拘わらず計画される。また、２以上の入力ストリームを伴う処理の場合は、異なる入力ストリームに関する割付の相対タイミングには配慮は払われない。非周期的な要求に対するタイムスロットの割付は、上記時間差が可変でさえあり得ることを意味する。このように、入力と出力との間の時間差に対して、周期的に繰り返す割り付けパターンを使用することから生ずるものを越えて、制限を課すことは望ましくない。
前記ＦＩＦＯバッファ４２２、４２４、４６０、４６２は、これらの条件下で上記処理を実行することができることを保証する。例えば、プロセッサは、該プロセッサが或る処理からの出力に対してタイムスロットが割り付けられたことを検出した場合は、該処理に戻ることができる。この場合、該プロセッサにより実行される別の処理に入力される信号値は、必ずしも、これら信号値が到達したのと同じ順序で実行される必要はない。異なる信号ストリームからの信号値をＦＩＦＯバッファ４２２、４２４において異なる量の時間だけバッファリングすることにより、これらの信号値を、タイムスロットが出力用に利用することができるようになるまで、待たせることができる。この場合、ＦＩＦＯバッファは、通常、当該処理要素の出力端子においては必要とされない。（この場合、ＦＩＦＯバッファは、単一の処理から複数の出力ストリームを生成することができるプロセッサ、又は例えば可変長復号又はサブサンプリング用のように入力信号値と出力信号値との間に１対１の対応がない場合のみにおいて、必要となる。）
第６図は、上記のような割付を実行する仲裁器の一実施例を示す。この仲裁器は、厳しいリアルタイムサービス要求入力端子を備えるロード回路６８を有している。該ロード回路の出力端子は割付メモリ６０に結合されている。該割付メモリ６０は、当該仲裁器の出力端子６７a-dに各合成回路６６a-dを介して結合された出力端子を有している。また、該割付メモリ６０はタイムスロットカウンタ６２に結合された入力端子を有している。また、該タイムスロットカウンタ６２のカウント入力端子には、分周器６３を介して信号値クロック入力が供給される。当該仲裁器は非リアルタイム仲裁器６４を有し、該非リアルタイム仲裁器は伝送要求用のインターフェース６５と、上記合成回路６６a-dに結合された出力端子とを備えている。
動作時には、割付メモリ６０は、スイッチマトリクス１２の入力端子及び出力端子の異なるタイムスロットでの各処理に対する割り付けを決定する情報を記憶する。該割付メモリ６０は各タイムスロットに対して各々ロケーションを有している。各ロケーションの内容はスイッチマトリクス１２に接続された各入力端子及び各出力端子に対するエントリを有している。各エントリは、当該入力端子に接続された何の論理ＦＩＦＯへ、又は当該出力端子に接続された何の論理ＦＩＦＯから信号値が渡されねばならないか、及び該入力端子又は出力端子がスイッチマトリクス内でどの様に内部的に接続されるべきかを特定する。
割付メモリ６０の各ロケーションの内容は順次のタイムスロットで出力される。この目的のため、クロック信号が分周器６３に供給され、該分周器６３はＱクロックサイクル毎にタイムスロットカウンタ６２にカウントパルスを供給する。各クロックサイクルは、スイッチマトリクス１２を介して一群の信号値の同時伝送を指示する。タイムスロットは、Ｑ個の斯かる伝送を含む（例えば、Ｑ＝１６）。タイムスロットカウンタ６２のカウント値はタイムスロットサイクル番号を表し、割付メモリ６０用のアドレスとして使用される。これに応答して、割付メモリ６０は当該タイムスロット用のロケーションの内容を出力する。この内容の種々のエントリが前記機能要素１０a-fとスイッチマトリクス１２とに渡され、これにより適切な論理ＦＩＦＯ及び適切な接続を各々選択する。
ロード回路６８は当該装置に関してなされた割り付け計画を表す情報を含んでいる。この計画は、入力端子及び出力端子を異なるタイムスロットで信号ストリームに割り付ける。該ロード回路６８は厳しいリアルタイムサービス要求入力端子６９を有し、該入力端子を介して、計画された信号ストリームの１つが開始しなければならないことが通知される。これに応じて、ロード回路６８は、割付メモリ６０における入力端子及び出力端子が当該信号ストリームに割り付けられるロケーションに情報をロードする。この情報は、上記スイッチマトリクス及び論理ＦＩＦＯに上記接続をさせるように選択される。上記ローディングは、例えば、各ストリームに対し各々のプログラムをロード回路６８に含ませ、特定のストリームに対するロードプログラムを、該特定のストリームが開始することを通知された場合に実行することにより実現することができる。
信号ストリームが終了した場合は、これがロード回路６８にも通知され、これに応じて該ロード回路は当該ストリームのために割付メモリ６０でなされたエントリをリセットする。このように、信号ストリームが活性状態でない場合は、該信号ストリームに割り付けられたタイムスロット内では、割り付けられた入力端子及び出力端子用の可能化信号が割付メモリ６０からスイッチマトリクス１２に渡されることはない。勿論、入力端子及び出力端子が全く割り付けられていないタイムスロットにおいても、これら入力端子及び出力端子用の可能化信号が割付メモリ６０からスイッチマトリクス１２に渡されることはない。
非リアルタイム仲裁器６４は、厳しいリアルタイム制約条件を満たす必要がない信号ストリームの伝送のために入力端子−出力端子対の使用に関する他の要求を入力する。該非リアルタイム仲裁器６４は、これら他の要求の間の競合を従来の方法で仲裁すると共に、上記スイッチマトリクス及び機能要素に接続された各入力端子及び出力端子用の制御信号を出力して、何の入力端子及び出力端子が接続されるべきか及び何の論理ＦＩＦＯが使用されるべきかを通知する。これらの制御信号は合成回路６６a-dに供給される。該合成回路は、割付メモリ６０から可能化信号を入力しない場合においてのみ、これら制御信号をスイッチマトリクス１２及び処理要素１０a-fに受け渡す。それ以外の場合、合成回路６６a-dは割付メモリ６０からの信号を通過させる。これにより、合成回路６６a-dが、非リアルタイム信号ストリームにより必要とされる入力端子−出力端子対の１個のみの入力端子又は出力端子に関して制御信号を通過させる可能性が残される。これは検出され、スイッチマトリクスにより信号伝送が抑圧される。要求が許諾されたか否かは、これら非リアルタイム要求の信号源に返信される。
このように、割付メモリ６０により決定される入力端子及び出力端子の割り付けは、常に、非リアルタイム要求に対する割り付けに優先する。これら非リアルタイム要求は、入力端子及び出力端子が厳しいリアルタイム信号ストリームのために使用されないタイムスロットにおいて、これら入力端子及び出力端子が割り付けられていないか、又は厳しいリアルタイムストリームが活動状態でないという理由により、許諾される。
前記中央プロセッサ１８はユーザインターフェース（図示略）に接続されている。使用者は、該ユーザインターフェースを使用して、当該装置を含む機器により実行されるべき機能又は機能の組み合わせを選択することができる。当該機器が特定の機能又は機能の組み合わせを実行する場合は、特定の状態にあると言われる。このように、使用者は当該機器を多数の異なる状態の間で切り換えることができる。各状態は、厳しいリアルタイム制約条件の下で同時に実行されねばならない処理の組み合わせに対応する。当該装置を最適に利用するために、好ましくは、各状態に対して別個の割り付け計画を行う。該割り付け計画は処理要素１０a-fの何の入力端子及び出力端子が何のタイムスロットで信号ストリームに割り付けられるかを特定する。原理的に、この割り付け計画は、例えば中央プロセッサ１８により、新たな状態が発生する毎に計画することもできるが、計画は、当該装置が使用される機器の各々の可能性のある状態に関して前もってなされ、当該装置に記憶することもできる。使用者が当該機器を特定の状態に切り換える場合は、該状態用の割り付け計画が取り出され、中央プロセッサ１８により仲裁器１４のロード回路６８にロードされる。
状態間の切り換えも、内部事象により起動することができる。例えば、使用者が第１状態と第２状態との間の切り換えを起動した場合は、該切り換えが起動される前に開始された幾つかの画像の処理を完了させ、これら幾つかの画像の処理が完了した後でのみ別の画像の処理を開始させる必要があるであろう。この場合、多数の中間の状態を規定し、これら中間状態を経て当該機器は前記第１状態から第２状態へ移行する。各中間状態は、自身の処理の組み合わせと、仲裁器１４にロードされる自身の割り付け計画を持つ。上記第１状態、中間状態及び第２状態の間の移行は、処理の完了等の内部事象により起動される。この一連の状態の移行は、例えば、前記ユーザインターフェースから入力される信号により可能化される。
処理要素１０a-fによる処理の実行は、データフロー原理に基づいて開始される。処理要素１０a-fの中には、ビデオ信号のような外部入力を受信する入力プロセッサが存在する。これらの入力プロセッサは、信号ストリームを発生すると共に、これら信号ストリームをスイッチマトリクス１２を介して他の処理要素１０a-fに供給するようにプログラムされている。
入力プロセッサが信号ストリームを発生するようにプログラムされている場合は、該入力プロセッサは、信号ストリームを開始するようにプログラムされているような、ビデオフレームの開始等の外部事象を検出する。これに応じて、該入力プロセッサは厳しいリアルタイム要求を仲裁器１４に送って、当該入力プロセッサの出力端子と、当該信号ストリーム用の他の処理要素１０a-fの対応する入力端子との割り付けを得る。仲裁器１４が当該信号ストリームに対して接続が利用できると通知すると、該入力プロセッサは先ず当該信号ストリームを識別するヘッダを送出し、次いで該信号ストリームの信号値を送出する。該ヘッダ及び後続する信号値は多数のタイムスロットにわたり分散され、これらタイムスロットにおいて仲裁器１４は該入力端子及び出力端子を当該信号ストリームに割り付ける。他のタイムスロット内でインターリーブされて、他の信号ストリームが該入力端子及び出力端子を通過することができる。上記出力端子が利用できない場合は、当該入力プロセッサは信号値をＦＩＦＯバッファ内にバッファする。事前に計画される割り付けは、当該入力プロセッサ内でバッファのオーバーフローが生じないように充分なタイムスロットが割り付けられることを保証する。最終的に、例えば当該ビデオフレームが完了した場合に、当該入力プロセッサは仲裁器１４に対し、上記入力端子及び出力端子が最早割り付けられる必要がないことを通知する。
上記入力プロセッサから信号ストリームを入力した処理要素１０a-fは、先ず、前記ヘッダから何の信号ストリームが開始したかを読み取る。これに応答して、処理要素１０a-fは該信号ストリームを処理する処理を開始する。処理要素１０a-fは、これを、例えば信号ストリームと処理との間の対応付けの記憶されたテーブルから決定することができる。開始された後、当該処理は処理された信号ストリームを発生するが、このストリームは該処理された信号ストリームの信号値が後続する新たなヘッダを含んでいる。これらの信号値（もし必要なら、及び上記ヘッダ）は論理ＦＩＦＯバッファに入力される。前記入力プロセッサと同様に、当該処理要素１０a-fは仲裁器１４からの当該処理された信号ストリーム用の入力端子及び出力端子の割り付けを要求し、仲裁器１４が或るタイムスロットにおいて入力端子及び出力端子が利用可能であることを通知すると上記ヘッダ及び信号値を送出する。前記入力信号ストリームが終了した後、当該処理要素１０a-fは処理された信号ストリームも終了させ、上記仲裁器に対して、入力端子及び出力端子が最早割り付けられる必要はないことを通知する。
このように、入力プロセッサを除く各処理要素１０a-fは、信号ストリームの到来により起動される。上記データフロー原理の更に詳細な説明は本出願の発明者と同じ発明者による同時継続中の出願に示されており、データフロー機構を記載した該同時継続中出願の一部を本明細書に参照文献として組み入れるものとする。
【図１】
0003893625.tif 000002
【図２】
0003893625.tif 000003
【図３】
0003893625.tif 000004
【図４】
0003893625.tif 000005
【図５】
0003893625.tif 000006
【図６】
0003893625.tif 000007