(57)【特許請求の範囲】
【請求項１】
複数のプロセスを実行し、これらプロセスのうちの第１プロセスがプロセス識別子及び複数のデータアイテムを有するデータトークンを発生するのに対し、第２プスセスが前記第１プロセスのデータアイテムを処理する、プロセス実行用の信号処理装置であって、
−  前記第１プロセスを実行し、且つデータアイテムを順次発生する第１処理要素と、
−  前記データトークンの受信に応答して、前記プロセス識別子の制御下で前記複数個のデータアイテムを前記第２プロセスに従って処理する第２処理要素と
を具えている信号処理装置において、前記第２処理要素を前記第１処理要素が前記データトークンのデータアイテムを既に発生してしまったか、否かに無関係に、前記データトークンの受信開始に応答してデータアイテムの処理を開始するように構成したことを特徴とする信号処理装置。
【請求項２】
前記第１及び第２処理要素が、少なくとも３つの処理要素から成り、且つこれらの処理要素間に割当て可能な通信回線を含むシステムの一部を成すようにした請求の範囲１に記載の信号処理装置において、該信号処理装置が、前記処理要素のシステムに前記プロセスに関連する情報をマッピングするように用立てた割当てコントローラを含み、該割当てコントローラが、データトークンの発生開始に応答し、且つデータトークンにおけるプロセス識別子に関連するマッピング時の情報の制御下で、前記第２処理要素の入力端子に他のデータトークン伝送用の通信回線が割当てられていなかった場合に、前記第１処理要素から前記第２処理要素の前記入力端子へのデータトークンの伝送用通信回線を割当てるようにしたことを特徴とする信号処理装置。
【請求項３】
前記第１処理要素に処理ユニット及び該処理ユニットと通信回線との間の出力ＦＩＦＯ（先入れ先出し）を設け、前記処理ユニットが第１プロセスを実行し、データアイテムを発生し、且つこれらのデータアイテムを前記出力ＦＩＦＯに順次書込み、前記割当てコントローラがデータトークンの伝送用通信回線を割当てている場合に、データアイテムが通信回線を介して伝送用に前記出力ＦＩＦＯから順次読取られるようにしたことを特徴とする請求の範囲２に記載の信号処理装置。
【請求項４】
前記出力ＦＩＦＯが、このＦＩＦＯがいっぱいとなる場合に前記第１プロセスの実行を保留するために、前記処理ユニットに結合される“ＦＩＦＯフル”出力端子を有するようにしたことを特徴とする請求の範囲３に記載の信号処理装置。
【請求項５】
前記第２処理要素に処理ユニット及び該処理ユニットと前記第２処理要素の入力端子との間の入力ＦＩＦＯを設け、データアイテムを前記第１処理要素から通信回線を経て前記入力ＦＩＦＯに順次書込み、前記処理ユニットがＦＩＦＯからのデータアイテムを前記第２プロセスに従って処理するために順次読取り、前記割当てコントローラが、先のデータトークンの最終データアイテムが入力ＦＩＦＯに書込まれている旨の検出に応答して、データトークン伝送用の通信回線を前記第２処理要素に割当てるようにしたことを特徴とする請求の範囲２，３又は４のいずれかに記載の信号処理装置。
【請求項６】
前記信号処理装置が、
−多数のプログラマブルに選択されるプロセスから成るプロセスシーケンスをプログラムするためのシーケンスプログラミング手段と、
−伝送シーケンスに関する制限を加え、前記プロセスが前記シーケンスプログラミング手段でプログラムしたプロセスのプロセスシーケンスに従ってデータトークンを通信回線を経て伝送するようにする順序付け手段とを含むようにしたことを特徴とする請求の範囲２〜５のいずれかに記載の信号処理装置。
【請求項７】
前記シーケンスプログラミング手段を前記割当てコントローラに結合させ、前記第２プロセスが前記プロセスシーケンスに従ってまだ満期状態になっていない限り、データトークンの伝送用回線の割当てを阻止するようにしたことを特徴とする請求の範囲６に記載の信号処理装置。
【請求項８】
前記第２処理要素が他の入力端子も有し、前記第２プロセスが第３プロセスと一緒に前記第２処理要素にマップされ、前記第２プロセスが前記入力端子及び他の入力端子を経て前記第１プロセス及び第４プロセスからそれぞれデータトークンを受取り、前記第２プロセスが前記入力端子及び他の入力端子を経て第５及び第６プロセスからそれぞれデータトークンを受取り、前記第１及び第５プロセスのデータトークンが通信回線を経て前記第１及び第２プロセスにそれぞれ伝送されるシーケンスが、前記第４及び第６プロセスのデータトークンが通信回線を経て前記第１及び第２プロセスにそれぞれ伝送されるシーケンスと一致するように前記プログラミング手段をプログラムしたことを特徴とする請求の範囲６又は７に記載の信号処理装置。
【請求項９】
前記第２処理要素が、他のデータトークンを受取るために通信回線に接続される他の入力端子を有し、前記第２プロセスがデータトークン及び前記他のデータトークンからのデータアイテムを共同で処理し、前記割当てコントローラが、データトークンの発生開始並びに前記他のデータトークンの発生開始が前記割当てコントローラによって検出されている場合にのみデータトークン伝送用の通信回線を割当てるようにしたことを特徴とする請求の範囲２〜８のいずれかに記載の信号処理装置。
【発明の詳細な説明】
本発明は、複数のプロセスを実行し、これらプロセスのうちの第１プロセスがプロセス識別子及び複数のデータアイテムを有するデータトークンを発生するのに対し、第２プスセスが前記第１プロセスのデータアイテムを処理する、プロセス実行用の信号処理装置であって、
−  前記第１プロセスを実行し、且つデータアイテムを順次発生する第１処理要素と、
−  前記データトークンの受信に応答して、前記プロセス識別子の制御下で前記複数個のデータアイテムを前記第２プロセスに従って処理する第２処理要素とを具えている信号処理装置関するものである。
斯種の信号処理装置はBang W．Lee外著の論文“Proceedings of the IEEE 1994 Custom Integrated Circuits Conference（CICC；San Diego，1994年５月）pp 103〜106における「Data Flow Processor for Multi-standard Video Codec」”から既知である。
特にビデオ信号を処理するには所定の処理速度が必要であり、現在のＩＣ技術ではこれは多数の処理要素にて並列処理することによってしか達成することができない。この並列処理のスケジューリングには通常、データアイテムに対して実行される様々な並列プロセスのスケジューリングを規定する集中調整のプログラム制御を伴なう制御フローアーキテクチャを利用している。
前記Bang W．Leeによる論文はデータフロー原理に従って並列プロセスをスケジュールすることを提案している。データフロー原理によると、様々なプロセスに従って処理されるデータトークンと称されるデータ単位を使用している。各データトークンは通常のデータアイテムだけでなく、データアイテムについて成すべきプロセスを推論し得るプロセス識別子も包含している。プロセッサは処理すべきデータトークンの可用性に応答してプロセスを開始し、このプロセスは集中調整プログラム制御によってどのプロセスをいつの時点に開始すべきかを前もって決めることなく、プロセス識別子に基づいて選定されている。
本発明の目的は処理効率をさらに高める冒頭にて述べた種類の信号処理装置を提供することにある。
このようにするために、本発明による信号処理装置は、前記第２処理要素を前記第１処理要素が前記データトークンのデータアイテムを既に発生してしまったか、否かに無関係に、前記データトークンの受信開始に応答してデータアイテムの処理を開始するように構成したことを特徴とする。
従ってこの信号処理装置はパイプラインのように作動し、連続するプロセスはデータアイテムのフロー又はそのセグメントで並列に実行される。データトークンは複数のデータアイテムを包含しているフローの一部を表わし、各データアイテムは原則として或るプロセス、例えば時間的に連続するか、又は空間的に連続する信号のサンプルを処理する期間中同じように処理される。従って、或るフローの複数のセグメントは処理要素に交互に到達し、各セグメントの長さは制限され、フローセグメントに関するプロセスの開始は、プロセス識別子を用いて全フローセグメントに対するデータフロー原理に従って一度スケジュールされるだけである。この方法は、これがデータトークンを分割できないものとして処理するプロセスを最早取り扱わないという点でデータフロー原理とは異なるものである。
本発明の好適例では、前記第１及び第２処理要素が、少なくとも３つの処理要素から成り、且つこれらの処理要素間に割当て可能な通信回線を含むシステムの一部を成すようにした信号処理装置において、該信号処理装置が、前記処理要素のシステムに前記プロセスに関連する情報をマッピングするように用立てた割当てコントローラを含み、該割当てコントローラが、データトークンの発生開始に応答し、且つデータトークンにおけるプロセス識別子に関連するマッピング時の情報の制御下で、前記第２処理要素の入力端子に他のデータトークン伝送用の通信回線が割当てられていなかった場合に、前記第１処理要素から前記第２処理要素の前記入力端子へのデータトークンの伝送用通信回線を割当てるようにする。このように、割当てコントローラは実際にはスケジューリングを行なう。割当てコントローラがプロセス識別子を伴なうデータトークンを第２処理要素へ伝える場合に、これに応答して第２処理要素は第２プロセスの実行を開始する。
本発明の他の好適例では、前記第１処理要素に処理ユニット及び該処理ユニットと通信回線との間の出力ＦＩＦＯ（先入れ先出し）を設け、前記処理ユニットが第１プロセスを実行し、データアイテムを発生し、且つこれらのデータアイテムを前記出力ＦＩＦＯに順次書込み、前記割当てコントローラがデータトークンの伝送用通信回線を割当てている場合に、データアイテムが通信回線を介して伝送用に前記出力ＦＩＦＯから順次読取られるようにする。従って、例えば第２処理要素がまだ以前のデータトークンの処理に掛わっているか、又は第２プロセスでの第２データトークンと共同で処理すべき他のデータトークンの生成がまだ開始していないために、割当てコントローラがデータトークン伝送用の通信回線を割当てていなかったとしても第１処理要素はデータアイテムの生産を続行することができる。
本発明による信号処理装置のさらに他の好適例では、前記第２処理要素に処理ユニット及び該処理ユニットと前記第２処理要素の入力端子との間の入力ＦＩＦＯを設け、データアイテムを前記第１処理要素から通信回線を経て前記入力ＦＩＦＯに順次書込み、前記処理ユニットがＦＩＦＯからのデータアイテムを前記第２プロセスに従って処理するために順次読取り、前記割当てコントローラが、先のデータトークンの最終データアイテムが入力ＦＩＦＯに書込まれている旨の検出に応答して、データトークン伝送用の通信回線を前記第２処理要素に割当てるようにする。このように、処理ユニットはデータトークンの到着順にこれらのデータトークンを処理するため、このユニットをデータフローの処理用に特別に設計する必要がない。従って、データトークンの伝送は、前のデータトークンが完全に処理される前に既に開始することがてきる。
データフロー原理による処理はデッドロックのリスクを伴なう。デッドロックは、例えばいずれかのプロセスに対する全入力のデータトークンが使用可能にならず、種々のプロセス用に発生されるデータトークンの数が過剰となるために処理が停止する場合に生じる。これは特に、各々が或る特殊な機能（ＤＣＴ，フィルタリング等）を有するプロセスの実行用に極めて効率的に構成されるも、他のプロセスを実行することができない機能−特定処理要素を複数具えている信号処理装置にとっては問題である。従って、デッドロックは処理要素へのプロセスの割当て選択を変えることによって防ぐことはできない。
同じ処理要素への複数プロセスの割当てのために生じる他の問題は、所謂“飢餓状態”（スターベーション）である。この飢餓状態による影響を受けたプロセスは殆ど実行されず、これは或る処理要素に到達する他のプロセスからのデータトークンの数が当面のブロックのデータトークンの数よりも遥かに多くなるからである。
本発明による信号処理装置のさらに他の好適例では、前記信号処理装置が、
−  多数のプログラマブルに選択されるプロセスから成るプロセスシーケンスをプログラムするためのシーケンスプログラミング手段と、
−  伝送シーケンスに関する制限を加え、前記プロセスが前記シーケンスプログラミング手段でプログラムしたプロセスのプロセスシーケンスに従ってデータトークンを通信回線を経て伝送するようにする順次付け手段とを含むようにする。このように、信号処理装置のプログラミング中にプログラマ又はコンパイラは、デッドロック及び飢餓状態を防ぐために、例えば全く同じ処理要素に割当てられる種々のプロセス用の入力を供給するプロセスが交互に開始されるようにする手段を講じることができる。
本発明による信号処理装置の他の好適例では、前記シーケンスプログラミング手段を前記割当てコントローラに結合させ、前記第２プロセスが前記プロセスシーケンスに従ってまだ満期状態になっていない限り、データトークンの伝送用回線の割当てを阻止するようにする。従って、いずれにしても必要とされる通信上のアービトレーションを用いてシーケンスに制約を課するようにする。
本発明による信号処理装置のさらに他の好適例では、前記第２処理要素が他の入力端子も有し、前記第２プロセスが第３プロセスと一緒に前記第２処理要素にマップされ、前記第２プロセスが前記入力端子及び他の入力端子を経て前記第１プロセス及び第４プロセスからそれぞれデータトークンを受取り、前記第２プロセスが前記入力端子及び他の入力端子を経て第５及び第６プロセスからそれぞれデータトークンを受取り、前記第１及び第５プロセスのデータトークンが通信回線を経て前記第１及び第２プロセスにそれぞれ伝送されるシーケンスが、前記第４及び第６プロセスのデータトークンが通信回線を経て前記第１及び第２プロセスにそれぞれ伝送されるシーケンスと一致するように前記プログラミング手段をプログラムする。このようにすることにより、処理要素が１つの入力端子に対して異なるデータトークンを発生し、従って他の入力端子に対するいずれかの関連データトークンの発生を開始しない場合に生ずるデッドロック状態が妨げられる。
本発明による信号処理装置のさらに他の好適例では、前記第２処理要素が、他のデータトークンを受取るために通信回線に接続される他の入力端子を有し、前記第２プロセスがデータトークン及び前記他のデータトークンからのデータアイテムを共同で処理し、前記割当てコントローラが、データトークンの発生開始並びに前記他のデータトークンの発生開始が前記割当てコントローラによって検出されている場合にのみデータトークン伝送用の通信回線を割当てるようにする。このように、割当てコントローラはデータトークンを所謂整合するのであって、このことは第２処理要素に対を成して到達するデータトークンが同じ第２プロセス用に向けられることを意味している。従って、第２処理要素は到来するデータトークンをさらに整合することなく処理することができる。
以下本発明を図面を参照して説明するに、ここに：
図１は信号処理装置を示し、
図２はデータフローグラフの例を示し、
図３は処理要素を示し、
図４はコントローラ用の表を示し、
図５はコントローラ用のフローチャートを示し、
図６はデータフローグラフの例を示し、
図７はスケジューリングの例を示す。
図１は信号処理装置を示す。この装置は、例えば５つの処理要素１０ａ〜１０ｅと、プログラマブル制御ユニット１２と、クロスバースイッチ１４とを具えている。処理要素１０ａ〜１０ｅはクロスバースイッチ１４を介して互いに接続することができる。クロスバースイッチ１４は制御ユニット１２によって制御される。
図２はデータフローグラフ２０の一例を示す。このデータフローグラフ２０は、複数のプロセス（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｐ，Ｑ）から成る複合データ処理プロセスを表わしている。各プロセス（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｐ，Ｑ）は、或る所定のデータ処理機能に相当する。プロセスＡの機能は、例えばフーリエ変換とすることができるのに対し、プロセスＢ及びＣはフーリエ変換の実及び虚成分の量子化とすることができ、他のプロセスはハフマン復号化又はランレングス復号化処理等を行なうこととすることがてきる。種々のプロセスは、それぞれ異なるデータに対して同じような機能を実行するものとすることができる。
データフローグラフ２０における各プロセスをそれぞれのノード（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｐ，Ｑ）により記号で表わしてある。データフローグラフにおけるそれぞれのエッジＥ０〜Ｅ９はプロセス（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｐ，Ｑ）間のデータ交換を記号で表わしたものである。データフローグラフ２０によると、データはエッジＥ０からプロセスＡに入る。このプロセスＡは２種類の出力データを発生し、これらのデータはエッジＥ１，Ｅ２を経てプロセスＢ及びＣへとそれぞれ供給される。次いでプロセス２Ｂが２種類の出力データを発生し、これらのデータはそれぞれエッジＥ３及びＥ４を経てプロセスＤ及びＰへと供給される。プロセスＣは一種類の出力データを発生し、この出力データはエッジＥ５を経てプロセスＰへと供給される。プロセスＰは２種類の入力データを受取って、一種類の出力データを発生し、この出力データはエッジＥ７を経てプロセスＥへと供給される。プロセスＤはエッジＥ６を経てプロセスＱへ供給される出力データを発生し、プロセスＥはエッジＥ８を経てプロセスＱへ供給される出力データを発生する。プロセスＱはエッジＥ９を経て複合データ処理演算の最終結果を出力する。
図１の信号処理装置はその作動中に、例えば一連の画像信号の各々について、データフローグラフ２０を実行する。このために、様々なプロセス（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｐ，Ｑ）を処理要素１０ａ〜１０ｅのシステムにマップする。例えば、プロセスＡ及びＢを処理要素１０ａにマップし、プロセスＰ及びＱを処理要素１０ｂにマップし、プロセスＣ，Ｄ，Ｅをそれぞれ処理要素１０ｃ〜１０ｅにマップする。このように幾つかのプロセスを同じ処理要素にマップすることができる。本例における処理要素以外に、プロセスをマップしない処理要素も有り得る。
到来する画像信号は、プロセスＡをマップしてある処理要素１０ａに供給される。処理要素１０ａは各画像信号に対してプロセスＡの機能を実行して、各画像信号に対して、プロセスＡの結果として生じる２種類のデータ対象物を発生する。これら２種類のデータ対象物は常にクロスバースイッチ１４を経て、プロセスＢ及びＣをマップしてある処理要素１０ａ及び１０ｃに伝送され、これらの処理要素はデータフローグラフ２０に従ってプロセスＡの結果を受取る。データ対象物はこうして順次処理要素１０ａ及び１０ｃにて処理される。
図３は処理要素の実施例を示す。この処理要素は、それぞれのＦＩＦＯ５２ａ及び５２ｂを経て処理要素の入力端子に接続される２つの入力端子を有する処理ユニット５０を具えている。さらに、処理ユニット５０の出力端子はＦＩＦＯ５４を経てルータ５６の入力端子に結合されている。処理要素は実行制御ユニット５８も具えている。各ＦＩＦＯ５２ａ，５２ｂ及び５４は入力−クロック入力端子と、出力−クロック入力端子と、ＦＩＦＯのフル／非フル出力端子と、ＦＩＦＯの空／非空出力端子とを有している。処理ユニット５０の入力側におけるＦＩＦＯ５２ａ及び５２ｂの出力−クロック入力端子は、これらのＦＩＦＯのＦＩＦＯ空／非空出力端子と一緒に実行制御ユニット５８に結合されている。処理ユニット５０の出力側のＦＩＦＯ５４の入力−クロック入力端子及びフル／非フル出力端子も実行制御ユニット５８に結合されている。
処理ユニットの入力側におけるＦＩＦＯ５２ａ，５２ｂの入力−クロック入力端子及びＦＩＦＯフル／非フル出力端子は制御ユニット１２に結合されている。ＦＩＦＯ５４の出力−クロック入力端子及びこのＦＩＦＯの空／非空出力端子はルータ５６に結合されている。ルータは制御ユニット１２（図示せず）に接続される。
それぞれのデータトークンは作動中に入力ＦＩＩＦＯ５２ａ，５２ｂの入力端子に供給される。データトークンは、例えば多数のデータアイテムを包含しており、こうしたデータアイテムは一緒になって或る画像信号を表わし、これらのデータアイテムは入力ＦＩＦＯ５２ａ，５２ｂに順次書込まれる。データトークンは、例えばそのデータトークンにおけるデータアイテムの数を示す長さコード、画像信号をどんな機能で処理すべきかを示す標識コード及びこの機能の出力データがデータフローグラフにおけるどこのエッジに対応するのかを識別する識別子も包含している。
実行制御ユニット５８は、例えばＦＩＦＯ５２ａ，５２ｂが空でない信号を処理ユニットの入力端子に供給し、且つＦＩＦＯ５４が非フル信号をその出力端子に供給する場合に、処理ユニット５０の起動を制御する。処理ユニット５０が起動すると、これはＦＩＦＯ５２ａ，５２ｂから到来するデータに関して、その長さコード及びそのデータについて成すべき機能の標識コードを読取る。その後、処理ユニット５０は入力ＦＩＦＯ５２ａ，５２ｂからデータアイテムを順次読取る。これらのデータアイテムは機能の標識コードに従って、例えばフーリエ変換を実行するか、又は可変長復号化を実行することにより処理される。この処理は機能標識コード及び最初のデータアイテムが入力ＦＩＦＯ５２ａ，５２ｂにて使用可能になると直ぐに開始することができる。このような処理の開始は全てのデータアイテムが使用可能となるまで延ばす必要はない。一般に、入力ＦＩＦＯ５２ａ，５２ｂはデータトークンにおける全てのデータアイテムを同時に収容するにはあまりにも短か過ぎる。
処理演算操作によって一連の出力データアイテムが発生する。処理ユニット５０はこれらのデータアイテムを出力ＦＩＦＯ５４に順次供給し、これらのアイテムには、この処理ユニットによる機能の出力データがどのエッジに対応するのかを識別する識別子を先行させる。機能に応じて、出力ＦＩＦＯ５４へのデータアイテムの供給は、全てのデータアイテムが処理ユニットの入力端子に到達する前に既に開始することができる。
処理ユニット５０の出力に関するＦＩＦＯ５４からの空／非空信号に基づいて、ルータ５６は出力データが使用可能であるか、否かを検出する。出力データが使用可能で、その可用性がまだ制御ユニット１２に知らされていなかった場合には、その可用性を出力データが対応するデータフローグラフにおけるエッジの識別子と一緒に制御ユニット１２に知らせる。制御ユニットは、これに応答して、出力データについて成すべき処理演算機能及びその処理演算による結果を出力するエッジの識別子をルータ５６に指示する。さらに、制御ユニット１２はクロスバースイッチ１４を介して該当する演算を実行すべき処理要素への回線を割り当てる。
制御ユニット１２がルータ５６に、通信回線が使用可能である旨を知らせた後に、ルータ５６は機能標識コード及びエッジの識別子をクロスバースイッチ１４（図示せず）を経て発送する。処理要素によって実行されたプロセスが１つ以上のエッジ出力データを発生する場合には、これらのエッジに通し番号を付けるのが好適である。この場合に、制御ユニット１２はルータ５６又は処理ユニットに最低の番号を与えるだけで済み；そしてルータ５６又は処理ユニットそのものが連続する出力エッジの番号を生成することができる。
その後ルータ５６が出力ＦＩＦＯ５４の出力−クロック入力端子へクロック信号を供給するため、データアイテムが出力ＦＩＦＯ５４からクロスバースイッチ１４（図示せず）を経て順次発送される。このデータアイテムの発送は、ＦＩＦＯ５４の出力データが空になるか、又はこの出力データが供給されるＦＩＦＯ５２ａ，５２ｂがいっぱいになるフル状態となる場合に中断されるようにする。これは、例えば制御ユニット１２によるか、又は空／非空及びフル／非フル信号をクロスバースイッチ１４を介して関連する処理要素１０ａ，１０ｂ間にてやり取りすことにより制御される。
制御ユニット１２はデータフローグラフの表現を包含しており、これは種々のデータフローグラフをそこに表現し得るようにプログラムすることができる。制御ユニット１２はプログラムしたデータフローグラフを実際に実行するように処理要素１０ａ〜１０ｅ及びクロスバースイッチ１４を制御する。
図４は制御ユニット１２に使用するデータフローグラフを表形態にて表現したものである。この表はデータフローグラフの各エッジに対して別個の行を包含しており、これらの各行は例えば次のようなものを包含している。即ち、
−  関連するエッジの識別子、
−  当該エッジを経て転送されるデータについて実行すべき演算機能の識別子、
−  斯かる機能を実行させるべき処理要素及び必要ならば、データを供給すべき処理要素の入力端子の識別子、
−  関連するエッジを経てデータを転送した後に、データ転送をまだ行なえる別のエッジの識別子。
図５は図４の表を制御ユニット１２により如何にして用いるかの例を示すフローチャートである。このフローチャートは、或るプロセスの出力データが移送用に使用可能である旨を処理要素１０ａ〜１０ｅが制御ユニット１２に知らせ、且つ処理要素１０ａ〜１０ｅが、データフローグラフにおけるどのエッジにこのデータが対応するのかを知らせると云う仮定に基づいている。
制御ユニット１２は各処理要素１０ａ〜１０ｅに対するフローチャートを、例えばラウンドロビン法に基づいて繰返し実行する。フローチャートの第１ステップ４０の期間中に制御ユニット１２は或る関連する第１処理要素１０ａ〜ｅから信号を受信したかどうかをテストする。この信号を受信しない場合には、フローチャートの実行を停止する。信号を受信した場合には、コントローラ１２が第２ステップ４２にて、関連する処理要素１０ａ〜ｅによって知らされたエッジに対応するデータ移送が可能であるかどうかをテストする。このステップの目的及びこのステップを実行する方法については後に詳細に説明するとして、このフローチャートの説明にとっては、エッジが使用可能になっていない場合には、制御ユニット１２がフローチャートの実行を停止し、且つデータ移送が可能になっている場合には、制御ユニットが第３ステップ４４を実行すると云うことに留める。第３ステップ４４の期間中には制御ユニット１２が、知らされたエッジと表とに基づいて、どの処理要素１０ａ〜ｅが使用可能データを処理すべきかを決定すると共にこの（第２）処理要素１０ａ〜１０ｅのどの入力端子に斯かるデータを供給しなければならないのかを決定する。次の第４ステップ４６の期間中には、制御ユニット１２が、斯かる入力端子は他のデータの供給用に既にリザーブされているかどうかをテストする。リザーブされていた場合には、フローチャートの実行を終了させ、リザーブされていなかった場合には、制御ユニット１２がその入力をリザーブして、第５ステップ４８を実行するようにする。
第５ステップ４８の期間中に、制御ユニット１２はクロスバースイッチ１４を制御して、このスイッチが、出力データを使用できる旨を知らされた第１処理要素１０ａ〜ｅの出力端子と、このデータを処理すべき第２処理要素１０ａ〜ｅの入力端子との間の回線を設定するようにする。制御ユニット１２は他の出力用エッジを、例えばエッジの使用可能／使用不能状態を示すメモリ素子を適当にロードすることにより使用不能にすることができる。その後、制御ユニット１２は知らされたエッジ及び表に基づいて、他のどのエッジを使用可能とする必要があるかどうかを確かめる。制御ユニット１２はこのエッジを、例えば関連するメモリ素子をそれ相当にロードすることにより使用可能にする。表から明らかなように＜この場合には元々知らされていたエッジを再び直接使用可能にすることができるため、既に知らされたエッジは実際上永久に使用可能とすることができる。
制御ユニット１２は知らされたエッジに基づいて表から出力データについて実行すべき機能を決定し、この機能の標識コードを第１処理要素１０ａ〜ｅに供給する。さらに、制御ユニットはこの機能を実行するプロセスの最低番号の出力エッジの識別子を決定し、これを第１処理要素１０ａ〜ｅへ供給する。従って、制御ユニット１２は各エッジの行に対して、このエッジがデータを供給するプロセスの機能に関連する情報以外に、関連するプロセスの出力データを伝送する最低の番号を付けたエッジに関連する情報（図示せず）も包含するようにするのが好適である。しかし、この情報はプロセス識別情報とプロセス識別／出力エッジ関連を包含している表とを用いることにより見つけることもできる。
本発明による信号処理装置の作動を単純化したデータフローグラフの例に基づいて以下詳細に説明する。
図６はデータフローグラフの一例を示す。このデータフローグラフは５つのプロセスＲ，Ｔ，Ｕ，Ｖを具えている。第１プロセスＲは２つの出エッジＩ，Ｊを有しており、これらのエッジはそれぞれ第１及び第２の連続プロセスＳ及びＵへと延在している。これらの各連続プスセスＳ及びＵは１つの出エッジを有しており、このエッジはそれぞれ別の連続プロセスＴ又はＶへと延在している。
図７は図６のデータフローグラフのプロセスを実行するスケジューリングの極めて単純化した例を示す。この例は、図６のプロセスＲ，Ｓ及びＵの各々がそれぞれの処理要素によって実行されると共にプロセスＴ及びＶが同じ処理要素によって実行されると云う仮定に基づいている。図７は多数のトレースＯI，ＯJ，ＯS，ＯU，ＯT/Vを包含しており、これらのトレースは処理要素でのデータアイテムの生産を表わしている。図７はトレースＡＬＬも包含しており、このトレースはどの回線がクロスバースイッチを経て割り当てられているのかを示す。最初の２つのトレースＯI，ＯJは第１プロセスＲを実行する処理要素でのデータアイテムの生産を表わしている。第３及び第４トレースＯS，ＯUは第１及び第２の連続プロセスＳ，Ｕをそれぞれ実行する処理要素でのデータアイテムの生産を表わしている。第５トレースは他の連続プロセスＴ，Ｖを実行する処理要素の出力に現われるデータアイテムの生産を表わしている。
図７の例は、入エッジＩを経て到来する順次のデータアイテムに応答して、プロセスＳがデータアイテムの内容に応じて可変数の出力データアイテム、本例では１，３，４，０，４，０，１をそれぞれ発生する。これは、例えばＭＰＥＧ復号化に用いられるような可変長復合器に対する場合である。発生するデータアイテムはデータトークンを形成するように合成される。プロセスＳそのものは１つのデータトークンを形成するように合成されるデータアイテムの数を決定する。このプロセスＳは、例えば発生データアイテムを４つ一組にして１つのデータトークンに組合わせる。プロセスＵも同じように作動するが、このプロセスは本例では順次のデータアイテムに応答して１，２，０，１，３，０のデータアイテムをそれぞれ発生する。
プロセスＳがデータアイテムの生産を開始するとすぐに、制御ユニット１２はクロスバースイッチ１４を介してプロセスＳを実行している処理要素からプロセスＴを実行する処理要素への回線を割当てる。２つのデータアイテムが受信される度毎にプロセスＴは１つの出力データアイテムを発生する。プロセスＴが実行されている間にプロセスＵもデータアイテムを発生し始める。これは制御ユニットに知らされるが、プロセスＶの回線をすぐに割当てることにはならない。その理由は、これらのデータアイテムに関してプロセスＶを実行するための処理要素及びこの処理要素への回線がまだプロセスＴに割当てられているからである。回線がまだ割当てられていなかったら、発生したデータアイテムはプロセスＵを実行する処理要素の出力ＦＩＦＯにバッファされる。従って、必要に応じてこの処理要素は発生したデータアイテムを発送し終える前に次のプロセスを開始することができる。
プロセスＶを実行するための処理要素への回線は、プロセスＳの完全なデータトークン（４つのデータアイテム）がプロセスＴを実行する処理要素に到達した後にだけプロセスＵの出力をプロセスＶに供給するために割当てられる。これに応答して、データアイテムはプロセスＵを実行する処理要素の出力ＦＩＦＯから読取られて、プロセスＶを実行する処理要素へ供給される。この処理要素はこれに応答してプロセスＶの実行を開始する。トレースの他の進路では、この処理要素はデータトークンの始まりの可用性に応じてプロセスＴか、プロセスＶを交互に実行する。従って、この処理要素は、例えばプロセスＶからのデータトークンを使用できない場合には、プロセスＴに２回続けて割当てられる。従って、或る所定瞬時にこの処理要素によって実行されるプロセスは前もって決められず、（例えば、可変長デコーダでは）データアイテムの内容によって決まる。このようにして、処理要素は予定したスケジュールの場合におけるよりももっと有効に用いることができる。
本例では、必要なデータアイテムが到来するとすぐに、プロセスＴ及びＶを実行する処理要素がデータアイテムを処理する。プロセスＴ及びＶが他の入力端子を有している場合には、この処理要素は対応するデータアイテムが斯かる他の入力端子にて使用可能となるまでデータアイテムの実行を保留しなければならなかった。しかし、待機中もクロスバースイッチ１４を介してのデータアイテムの電送は通常通り実行させることができ、これは、このようなデータアイテムは入力ＦＩＦＯに記憶させるからである。従って、クロスバースイッチは他のデータトークンの伝送に対して早めに自由になる。
原則として、各プロセスそのものでは、どれほどのデータアイテムを合成して、１つのデータトーンを形成するようにするのかを決定する。この数の選定には妥協点を見い出さなければならない。数個のデータアイテムだけから成るデータトークンは、スケジューリングの融通性が高くなる（データトークンが続く限り、或る処理要素への回線は、たとえ新規のデータアイテムがそのデータトークン内でまだ使用できなくても再び割当てることはできないから或る面では有利である。
これに対し、多数のデータアイテムから成るデータトークンは、これらの伝送費用が少なくて済み、しかも制御ユニットの負担、特にアービトレーションが少なくて済むために他の面では有利である。さらに、データアイテムは一緒に処理しなければならないことからして、データトークンにおけるデータアイテムの数は最少とする必要もある。データトークンを形成するように合成するデータアイテムを形成するように合成するデータアイテム数の選定は、ビデオデコーディングの如き信号処理用途における平均効率を可調整とし、これは適時応答に関する二次的条件の如き二次的条件付けをすることになる。従って、データトークンを形成するように合成すべきデータアイテムの数は、複数のプロセスを一緒に実行すべき場合に、効率が最適となるように選定するのが好適である。
所定タイプのタスクの場合で、しかも所定の状況下にあっては、特に、特殊な整合ユニットを用いない場合に、データフロー原理に従って作動する信号処理装置がデッドロック状態になり得る。これは図２のデータフローグラフに基づいて説明することができる。プロセスＰとＱが同じ処理要素によって実行されるものとする。双方のプロセスは２つの入力を有している。この処理要素の入力端子に同じプロセスＰ又はＱへの一致するデータトークンが現われると、関連するプロセスを実行することになる。しかし、それぞれ異なるプロセスに対するデータトークンが入力ＦＩＦＯにおける様々な入力端子に使用可能となる場合には、デッドロックが生じ、一方のプロセスを実行することができない。
斯様なデッドロック状態をなくすために、制御ユニット１２は選択したプロセスがデークトークンだけを予定したシーケンスで伝送する回線に割当てられるようにする機構を具えている。これによりプログラマは、例えば図２のデータフローグラフの場合、プロセスＢ，Ｃ，Ｅ及びＤをこの順序で回線に循環的に割当てる（他のプロセスはこれらのプロセスに無関係に回線に割当てることができる）ようにすることができる。従って、プログラマはプロセスＰ及びＱを実行する処理要素の様々な入力端子に現われるデータトークンが同じプロセスＰ又はＱ用のシーケンスで到達するようにすることができる。先ず、例えば回線をプロセスＢかＣにだけ割当てることができる。従って、上述したデッドロック状態は起こり得ない。これは他のプログラム、例えばプロセスＣ及びＤが、プロセスＢ及びＥのように（プロセスＣ及びＤはプロセスＰ及びＱを実行する処理要素の同じ入力端子にデータトークンを供給するものとする）或る回線に交互に割当てられるように特定化することによって達成することができることは明らかである。この場合には先ず例えばプロセスＢ及びＣだけを或る回線に割当てることができる。
選択したプロセスが或る予じめプログラムしたシーケンスで回線に割当てられるようにする機構は、例えば或る所定エッジの起動後にデータフローグラフにおける他のどのエッジを使用可能としなければならないのかを示している図４の表によって図１の装置にて実施される。表では、例えばエッジＥ４（Ｂの出力）の後にエッジＥ５（Ｃの出力）を他のエッジとして使用可能とするようにプログラムすることができる。エッジＥ５に対しては、エッジＥ８を他のエッジとして使用可能としなければならないようにプログラムすることができる。エッジＥ８に対しては、エッジＥ６を他のエッジとして使用可能とし、エッジＥ６に対してはエッジＥ４を他のエッジとして使用可能としなければならないようにプログラムすることができる。他のエッジは永久に使用可能なままとすることができる。従って、エッジの使用可能化に関連する所期設定をすることにより、プログラマはデッドロックが起こらないようにする。
デッドロック問題をなくす他の方法はメモリ機能を有する処理要素を用いるやり方である。他の全ての処理要素と同様に斯様なメモリ機能を有する処理要素は、関連する回線が制御ユニット１２によって割当てられている場合には、クロスバースイッチ１４を経てデータトークンを受取って、これらを発送することができる。メモリタイプの処理要素は後段への発送用の多数のデータアイテムを記憶し得るメモリを具えている。
メモリタイプの処理要素は、例えば整合機能を果たすことができ、これは或るデータトークンが全ての入力端子に対して使用可能となるまで１個以上の入力を有する或る所定のプロセス向けのデータトークンを記憶する。このような可用性に応答して、該当するデータトークンは、これに関連するプロセスを実行するための処理要素へと供給される。さらに、メモリタイプの処理要素は受信したデータトークンのコピーを発送することによりデータトークンを逓倍させるのに役立てることもできる。これは、例えば複数のプロセスが同じデータアイテムを処理しなければならない場合に有効である。
【図１】
0003987581.tif 000002
【図２】
0003987581.tif 000003
【図３】
0003987581.tif 000004
【図４】
0003987581.tif 000005
【図５】
0003987581.tif 000006
【図６】
0003987581.tif 000007
【図７】
0003987581.tif 000008