(57)【要約】【課題】装置間の待ち合わせ処理をする必要がなく、あらゆる木構造データフローグラフに対して統一的にストリームデータのパイプライン処理を実行することを可能とするストリームデータ処理方法およびストリームデータ処理装置を提供する。【解決手段】ストリームデータ処理方法は、ストリームデータの処理手順を表す木構造データフローグラフを構成するノードのうち、合流ノードとその合流ノードのデータ処理上流側の各ノードとの間で分割してサブグラフを生成するサブグラフ生成工程Ｓ１と、サブグラフ生成工程Ｓ１で生成されたサブグラフを構成する各ノードに対応する各処理内容を処理装置の処理手段に順番に割り付ける順序を設定する割付順設定工程Ｓ２と、割付順設定工程Ｓ２で設定された順序に従って処理内容を処理手段に順番に割り付けてストリームデータに対して順次処理を行う処理工程Ｓ３とを有する。【選択図】図５
2007164504.tif 000002
【特許請求の範囲】
【請求項１】
ストリームデータの処理手順を表す木構造データフローグラフを構成するノードのうち、複数のストリームデータを入力して処理を行う処理内容に対応する合流ノードとその合流ノードのデータ処理上流側の各ノードとの間で分割してサブグラフを生成するサブグラフ生成工程と、
前記サブグラフ生成工程で生成された前記サブグラフを構成する各ノードに対応する各処理内容を処理装置の処理手段に順番に割り付ける順序を設定する割付順設定工程と、
前記割付順設定工程で設定された順序に従って前記処理内容を前記処理手段に順番に割り付けてストリームデータに対して順次処理を行う処理工程と
を有することを特徴とするストリームデータ処理方法。
【請求項２】
前記サブグラフ生成工程では、前記木構造データフローグラフの中に同じストリームデータに対して同一の処理を行うノード列がある場合には、そのノード列を分割してサブグラフを生成し、生成された前記同一のノード列を有するサブグラフのうち１つのサブグラフを残して他のサブグラフを削除し、残されたサブグラフに前記合流ノードがあれば合流ノードとその合流ノードのデータ処理上流側の各ノードとの間でさらに分割してサブグラフを生成することを特徴とする請求項１に記載のストリームデータ処理方法。
【請求項３】
前記サブグラフ生成工程では、前記木構造データフローグラフの分割により生成された前記サブグラフをさらに分割して前記処理手段が実行可能な長さのサブグラフを生成することを特徴とする請求項１または請求項２に記載のストリームデータ処理方法。
【請求項４】
前記サブグラフ生成工程では、生成された複数のサブグラフのうち、他のサブグラフと同じストリームデータに対して同一の処理を行うサブグラフがあれば、それらのサブグラフのうち１つのサブグラフを残して他のサブグラフを削除することを特徴とする請求項１から請求項３のいずれか一項に記載のストリームデータ処理方法。
【請求項５】
前記サブグラフ生成工程では、前記サブグラフのうち、他のサブグラフの一部と同じストリームデータに対して同一の処理を行うサブグラフの一部があれば、その一部を１つのサブグラフとしてさらに分割することを特徴とする請求項１から請求項４のいずれか一項に記載のストリームデータ処理方法。
【請求項６】
前記割付順設定工程では、同時に処理される前記サブグラフの処理内容の数をそろえるようにサブグラフを再分割して処理装置の処理手段に割り付ける順序を設定することを特徴とする請求項１から請求項５のいずれか一項に記載のストリームデータ処理方法。
【請求項７】
前記割付順設定工程では、前記木構造データフローグラフで前記合流ノードの各枝の処理を行った直後にその合流ノードの処理を行うように処理装置の処理手段に割り付ける順序を設定することを特徴とする請求項１から請求項６のいずれか一項に記載のストリームデータ処理方法。
【請求項８】
ストリームデータに対して処理を行う処理手段と、
処理済みのストリームデータを保存する複数の記憶手段と、
前記処理手段に対して処理内容を割り付け、前記各手段間のストリームデータの流れを制御する制御装置と
を備え、
前記制御装置は、請求項１から請求項７のいずれか一項に記載のストリームデータ処理方法に基づいて前記木構造データフローグラフをサブグラフに分割し、前記処理手段に対して生成された前記サブグラフを構成する各ノードに対応する各処理内容を前記順序に従って順番に割り付けて、処理内容に応じた処理をストリームデータに対して順次行わせるように制御することを特徴とするストリームデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストリームデータ処理方法およびストリームデータ処理装置に係り、特に、ストリームデータをパイプライン処理可能なストリームデータ処理方法およびストリームデータ処理装置に関する。
【背景技術】
【０００２】
画像データや音声データ、各種の観測データ等のシーケンシャルな処理が要求されるストリームデータに対して、種々の処理機能を有する処理手段を直列に接続して入力されたストリームデータに対してパイプライン処理を行うストリームデータ処理装置が知られている（例えば、特許文献１、２等参照）。これらのストリームデータ処理装置は、ストリームデータに対する処理手順を表すデータフローグラフが直線状に表される処理を行う場合に適している。
【０００３】
一方、近年、画像処理の分野で、画像フィルタを木構造状に組み合わせた処理プログラムに従って入力画像データに対して順番に処理を施して出力画像データを得る画像処理技術（非特許文献１参照）が開発されている。
【特許文献１】特開平５−２９８４３６号公報
【特許文献２】特開平１０−３３４２２５号公報
【非特許文献１】青木紳也、外１名、「木構造状画像変換の自動構築法ＡＣＴＩＴ」、映像情報メディア学会誌、社団法人映像情報メディア学会、１９９９年、第５３巻、第６号、ｐ．８８８〜８９４
【発明の開示】
【発明が解決しようとする課題】
【０００４】
このようにデータフローグラフが木構造状に表される処理すなわち木構造データフローグラフに従う処理を行うストリームデータ処理装置を、例えば特許文献１や特許文献２に記載の装置を組み合わせて構成すると、２入力画像フィルタのように２つの画像データの入力を必要とする装置に対する入力のタイミングをそろえるように待ち合わせ処理を行うために、その直前の２つの装置におけるパイプライン処理の実行タイミングの制御や一時的な処理停止を行わざるを得なくなり、制御や一時停止を行わせるためのハードウエアが新たに必要となるとともに、それぞれの装置自体の処理回路の使用効率を著しく低下させてしまうという問題がある。
【０００５】
また、特許文献１等に記載の装置の構成を応用して、１つの装置内に種々の処理機能を有する処理手段を木構造状に接続して構成すると、回路規模が膨大になるうえ、その装置は特定の木構造データフローグラフに対応した１つの処理しか行うことができないという問題があった。
【０００６】
これらの課題を解決するためには、装置間のタイミング調整の必要性を回避するためにストリームデータ処理装置を１つの装置にまとめて構成することが必要である。しかも、異なる木構造データフローグラフにも１つの装置で対応できるように、あらゆる木構造データフローグラフに対して統一的に操作を施してストリームデータ処理を行えるようにするためのストリームデータ処理方法の確立が求められる。
【０００７】
しかも、前記ストリームデータ処理方法においては、木構造データフローグラフに対する操作が複雑な制御を必要とすると、操作に時間がかかって処理速度の低下を招き、リアルタイムの処理が困難になる場合があるから、木構造データフローグラフに対する操作をできるだけ単純にし、かつ高速にパイプライン処理を実行可能であることが望まれる。
【０００８】
また、木構造データフローグラフの実行に際しては、一般に装置のメモリ使用率が高くなる場合が多く、木構造データフローグラフが大規模になると実装された記憶手段より処理に必要な記憶手段の使用率（以下、メモリ使用率という）が大きくなって実行できなくなる場合がある。そのため、木構造データフローグラフの実行においては、メモリ使用率の増大を抑制できる処理方法の確立も望まれている。
【０００９】
本発明は、前記事情に鑑みてなされたものであり、装置間の待ち合わせ処理をする必要がなく、また、あらゆる木構造データフローグラフに対して統一的にストリームデータのパイプライン処理を実行することを可能とするストリームデータ処理方法およびその方法の適用に適したストリームデータ処理装置を提供することを目的とする。また、処理時のメモリ使用率の増大を抑制可能なストリームデータ処理方法およびストリームデータ処理装置を提供することをも目的とする。
【課題を解決するための手段】
【００１０】
前記の問題を解決するために、第１の発明は
ストリームデータ処理方法において、
ストリームデータの処理手順を表す木構造データフローグラフを構成するノードのうち、複数のストリームデータを入力して処理を行う処理内容に対応する合流ノードとその合流ノードのデータ処理上流側の各ノードとの間で分割してサブグラフを生成するサブグラフ生成工程と、
前記サブグラフ生成工程で生成された前記サブグラフを構成する各ノードに対応する各処理内容を処理装置の処理手段に順番に割り付ける順序を設定する割付順設定工程と、
前記割付順設定工程で設定された順序に従って前記処理内容を前記処理手段に順番に割り付けてストリームデータに対して順次処理を行う処理工程と
を有することを特徴とする。
【００１１】
第１の発明によれば、ストリームデータ処理方法では、木構造データフローグラフを合流ノードとその上流側の各ノードとの間で分割してサブグラフが生成され、サブグラフを構成する各ノードに対応する各処理内容を処理装置の処理手段に順番に割り付ける順序が設定され、設定された順序に従って処理内容を処理手段に順番に割り付けてストリームデータに対して順次処理が行われる。
【００１２】
第２の発明は、第１の発明のストリームデータ処理方法において、前記サブグラフ生成工程では、前記木構造データフローグラフの中に同じストリームデータに対して同一の処理を行うノード列がある場合には、そのノード列を分割してサブグラフを生成し、生成された前記同一のノード列を有するサブグラフのうち１つのサブグラフを残して他のサブグラフを削除し、残されたサブグラフに前記合流ノードがあれば合流ノードとその合流ノードのデータ処理上流側の各ノードとの間でさらに分割してサブグラフを生成することを特徴とする。
【００１３】
第２の発明によれば、ストリームデータ処理方法では、木構造データフローグラフの中から同じストリームデータに対して同一の処理を行うノード列が分割されてサブグラフ化され、１つのサブグラフだけが残される。
【００１４】
第３の発明は、第１または第２の発明のストリームデータ処理方法において、前記サブグラフ生成工程では、前記木構造データフローグラフの分割により生成された前記サブグラフをさらに分割して前記処理手段が実行可能な長さのサブグラフを生成することを特徴とする。
【００１５】
第３の発明によれば、ストリームデータ処理方法では、木構造データフローグラフの分割により生成されたサブグラフがさらに分割されて処理手段が実行可能な長さのサブグラフが生成される。
【００１６】
第４の発明は、第１から第３の発明のいずれかのストリームデータ処理方法において、前記サブグラフ生成工程では、生成された複数のサブグラフのうち、他のサブグラフと同じストリームデータに対して同一の処理を行うサブグラフがあれば、それらのサブグラフのうち１つのサブグラフを残して他のサブグラフを削除することを特徴とする。
【００１７】
第４の発明によれば、ストリームデータ処理方法では、木構造データフローグラフを分割して生成されたサブグラフや処理手段が実行可能な長さにさらに分割されたサブグラフの中に、他のサブグラフと同じストリームデータに対して同一の処理を行うサブグラフがあれば、１つのサブグラフだけが残される。
【００１８】
第５の発明は、第１から第４の発明のいずれかのストリームデータ処理方法において、前記サブグラフ生成工程では、前記サブグラフのうち、他のサブグラフの一部と同じストリームデータに対して同一の処理を行うサブグラフの一部があれば、その一部を１つのサブグラフとしてさらに分割することを特徴とする。
【００１９】
第５の発明によれば、ストリームデータ処理方法では、木構造データフローグラフを分割して生成されたサブグラフや処理手段が実行可能な長さにさらに分割されたサブグラフの中に、その一部が他のサブグラフの一部と同じストリームデータに対して同一の処理を行う場合は、その一部が１つのサブグラフとして分割されて１つだけが残される。
【００２０】
第６の発明は、第１から第５の発明のいずれかのストリームデータ処理方法において、前記割付順設定工程では、同時に処理される前記サブグラフの処理内容の数をそろえるようにサブグラフを再分割して処理装置の処理手段に割り付ける順序を設定することを特徴とする。
【００２１】
第６の発明によれば、ストリームデータ処理方法では、例えばサブグラフの処理内容の数にかかわらず同時に処理されるサブグラフに同じ数の処理装置を割り当てるようにして、同時に処理されるサブグラフの処理内容の数をそろえるようにサブグラフが再分割されて、処理装置の処理手段に割り付ける順序が設定される。
【００２２】
第７の発明は、第１から第６の発明のいずれかのストリームデータ処理方法において、前記割付順設定工程では、前記木構造データフローグラフで前記合流ノードの各枝の処理を行った直後にその合流ノードの処理を行うように処理装置の処理手段に割り付ける順序を設定することを特徴とする。
【００２３】
第７の発明によれば、ストリームデータ処理方法では、木構造データフローグラフにおいて合流ノードの各枝の処理を行った直後にその合流ノードの処理が行われるように処理装置の処理手段に割り付ける順序が設定される。
【００２４】
第８の発明は、ストリームデータ処理装置において、
ストリームデータに対して処理を行う処理手段と、
処理済みのストリームデータを保存する複数の記憶手段と、
前記処理手段に対して処理内容を割り付け、前記各手段間のストリームデータの流れを制御する制御装置と、
を備え、
前記制御装置は、請求項１から請求項７のいずれか一項に記載のストリームデータ処理方法に基づいて前記木構造データフローグラフをサブグラフに分割し、前記処理手段に対して生成された前記サブグラフを構成する各ノードに対応する各処理内容を前記順序に従って順番に割り付けて、処理内容に応じた処理をストリームデータに対して順次行わせるように制御することを特徴とする。
【００２５】
第８の発明によれば、ストリームデータ処理装置は、制御装置が、第１から第７の発明のいずれかのストリームデータ処理方法に基づいて木構造データフローグラフをサブグラフに分割し、処理手段に対して生成されたサブグラフを構成する各ノードに対応する各処理内容を順序に従って順番に割り付けて、ストリームデータを記憶手段から読み出して処理手段に入力してその出力を記憶手段に書き込むという処理を繰り返しながら、処理内容に応じた処理を順次行わせる。
【発明の効果】
【００２６】
第１の発明によれば、１つの装置内でストリームデータの処理を行うことが可能となり、装置間の待ち合わせ処理のためにパイプライン処理の実行タイミングの制御や一時的な処理停止を行う必要がなく、処理速度の低下を防止することが可能となる。また、制御や一時停止を行わせるための新たなハードウエアを備える必要もない。
【００２７】
また、処理手段に処理内容を割り付けながら処理を行うため、装置の回路規模がコンパクトになり、しかも、どのような木構造データフローグラフに対応できる汎用性を具備することが可能となる。
【００２８】
さらに、木構造データフローグラフを合流ノードの上流側で分割することで、あらゆる木構造データフローグラフを直線状のサブグラフ群に分割することが可能となり、直線状のサブグラフのノードに対応する処理内容を処理手段に割り付けることで、処理回路を直列に繋いだ処理回路群を複数形成することができ、それらの処理回路群で同時並行処理すなわちパイプライン処理が実行可能となる。
【００２９】
また、処理手段に処理内容を割り付けて処理回路を形成していくため、割り付けの順序を設定しておけばタイムロスなく処理手段に処理内容を割り付けることができ、装置の処理速度の低下を防止することができる。
【００３０】
第２の発明によれば、同じデータに対する同一の処理を重複して行うことを回避することができ、削除されたノード列のノードに対応する処理内容の分だけ処理が減るため処理速度を向上させることが可能となり、前記第１の発明の効果をより有効に発揮させることができる。
【００３１】
第３の発明によれば、前記各発明の効果に加え、サブグラフを処理手段による処理に適したものとすることが可能となるとともに、木構造データフローグラフを合流ノードの上流側で分割して生成された長さにばらつきがあるサブグラフを予め同程度の長さにそろえることが可能となる。
【００３２】
第４の発明によれば、同じデータに対する同一の処理を重複して行うことを回避することができ、削除されたノード列のノードに対応する処理内容の分だけ処理が減るため処理速度を向上させることが可能となり、前記各発明の効果をより有効に発揮させることができる。
【００３３】
第５の発明によれば、同じデータに対する同一の処理を重複して行うことを回避することができ、削除されたノード列のノードに対応する処理内容の分だけ処理が減るため処理速度を向上させることが可能となり、前記各発明の効果をより有効に発揮させることができる。
【００３４】
第６の発明によれば、データの処理段数を小さくすることができ、それに伴って１回あたりの処理時間を短縮することができ、処理速度を向上させることが可能となる。そのため、前記各発明の効果がより有効に発揮される。
【００３５】
第７の発明によれば、前記各発明の効果に加え、処理時に、２つの入力データ（メモリ使用率は２）を１つのデータ（メモリ使用率は１）に収斂させながら処理を行うことでメモリ使用率の増大を抑制することが可能となる。
【００３６】
第８の発明によれば、前記各発明のストリームデータ処理方法の発明の効果を発揮することができるとともに、ストリームデータ処理装置を１つの装置として構成したため、装置間の待ち合わせ処理のためにパイプライン処理の実行タイミングの制御や一時的な処理停止を行う必要がなく、処理速度の低下を防止することが可能となる。それと同時に、制御や一時停止を行わせるための新たなハードウエアを備える必要もなく、装置の処理回路の使用効率の低下も回避することが可能となる。
【００３７】
また、処理手段に処理内容を割り付けながら処理を行うように構成したため、装置の回路規模がコンパクトになり、しかも、どのような木構造データフローグラフに対応できる汎用性を具備することが可能となる。
【００３８】
さらに、木構造データフローグラフを合流ノードの上流側で分割することで、あらゆる木構造データフローグラフを直線状のサブグラフ群に分割することが可能となり、直線状のサブグラフのノードに対応する処理内容を処理手段に割り付けることで、処理回路を直列に繋いだ処理回路群を複数形成することができ、それらの処理回路群で同時並行処理すなわちパイプライン処理が実行可能となる。
【００３９】
また、処理手段に処理内容を割り付けて処理回路を形成していくため、割り付けの順序を設定しておけばタイムロスなく処理手段に処理内容を割り付けることができ、装置の処理速度の低下を防止することができる。特に、処理手段に予め必要な処理回路を具備させておき、制御装置がその処理回路の番号等を特定する情報を送信して処理手段に処理内容を割り付けるようにすれば、処理手段への処理内容の割り付けを瞬間的に行うことが可能となる。
【発明を実施するための最良の形態】
【００４０】
以下、本発明に係るストリームデータ処理方法およびストリームデータ処理装置の実施の形態について、図面を参照して説明する。
【００４１】
本実施形態では、木構造データフローグラフによりストリームデータである入力画像データｔ、ｔ−１、ｔ−２、ｔ−３を画像処理する場合を例として説明するが、本発明はこの場合に限定されない。また、本実施形態では、ストリームデータ処理装置はＦＰＧＡ評価用ボード（ALTERA社製）上に構築されているが、これに限定されない。
【００４２】
まず、本実施形態に係るストリームデータ処理方法を用いたストリームデータ処理装置について説明する。
【００４３】
本実施形態に係るストリームデータ処理装置１は、図１に示すように、図示しない外部装置から送信されてきた入力画像データｔ、ｔ−１、ｔ−２、ｔ−３等のストリームデータを保存する入力バッファ２と、これらのストリームデータに対して処理を行う処理装置３と、処理装置３で処理されたストリームデータを一時保存して送信する出力バッファ４と、それらの動作を制御する制御装置５とを備えている。
【００４４】
なお、入力バッファ２や出力バッファ４は、外部装置から処理装置３にストリームデータが直接入力され或いは処理装置３から外部装置にストリームデータが直接出力される場合には設けられない。また、本発明では、入力バッファ２や出力バッファ４に、処理装置３の処理途中のストリームデータが保存されることはない。
【００４５】
処理装置３は、図２に示すように、入力ポート３１と、ｎ１本の入力データバス３２ａ、３２ｂ、３２ｃ、３２ｄと、処理手段としてのｎ２個のプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄと、プロセッサ３３ａ等の出力側に接続されるｎ２本の出力データバス３４ａ、３４ｂ、３４ｃ、３４ｄと、記憶手段としてのｎ３個のストリームデータバッファメモリ（以下、メモリという）３５ａ、３５ｂ、３５ｃ、３５ｄと、出力ポート３６とを備えるパイプライン構成を有する処理装置である。なお、図２には、ｎ１＝ｎ２＝ｎ３＝４の場合が示されている。
【００４６】
また、入力ポート３１、プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄ、メモリ３５ａ、３５ｂ、３５ｃ、３５ｄおよび出力ポート３６には、タイミングコントローラ３７が接続されており、それらはタイミングコントローラ３７のタイミング制御により同期して動作するようになっている。
【００４７】
入力ポート３１には、ｎ１本の入力データバス３２ａ、３２ｂ、３２ｃ、３２ｄが接続されており、また、前述した入力バッファ２に接続されている。入力ポート３１は、入力されたストリームデータを制御装置５により指定された入力データバス３２ａ等に流すようになっている。
【００４８】
入力データバス３２ａ、３２ｂ、３２ｃ、３２ｄには、メモリ３５ａ、３５ｂ、３５ｃ、３５ｄの出力線およびプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄの２本の入力線がそれぞれスイッチ３８を介して入力データバス３２ａ等の上流側および下流側で接続されている。
【００４９】
スイッチ３８はそれぞれ制御装置５に接続されており、制御装置５が設定したスイッチ設定により切り替えられるようになっている。スイッチ３８は、制御装置５によりスイッチ設定で切り替えられることで、メモリ３５ａ、３５ｂ、３５ｃ、３５ｄのいずれかから読み出されたストリームデータを特定の入力データバス３２ａ、３２ｂ、３２ｃ、３２ｄに伝達して流し、またプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄのいずれかに特定の入力データバス３２ａ、３２ｂ、３２ｃ、３２ｄからストリームデータを伝達して入力させることができるようになっている。
【００５０】
処理手段としてのプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄには、２本の入力線を介して入力データバス３２ａ等から同一の或いは異なる２つのストリームデータが入力できるようになっている。さらに、最上流側のプロセッサ３３ａ以外のプロセッサ３３ｂ、３３ｃ、３３ｄは、それぞれすぐ上流側のプロセッサからの出力が入力できるようになっている。
【００５１】
なお、プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄは、入力データバス３２ａ等からのストリームデータの入力と上流側のプロセッサからのストリームデータの入力とが重なる場合は、入力データバス３２ａ等からの入力を優先するように構成されている。すなわち、プロセッサ３３ａ等は、プロセッサ３３ａ等に取り込まれた画像フィルタが１入力のフィルタである場合に入力データバス３２ａ等からと上流側のプロセッサからの１つずつストリームデータの入力があるときは、入力データバス３２ａ等からのストリームデータを取り込んで処理を行い、プロセッサ３３ａ等に取り込まれた画像フィルタが２入力のフィルタである場合に２本の入力データバス３２ａ等からおよび上流側のプロセッサから計３つのストリームデータの入力がある場合は、２本の入力データバス３２ａ等から入力される２つのストリームデータを取り込んで処理を行うように構成されている。
【００５２】
プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄには、それぞれレジスタ３９ａ、３９ｂ、３９ｃ、３９ｄが接続されており、レジスタ３９ａ、３９ｂ、３９ｃ、３９ｄは制御装置５に接続されている。レジスタ３９ａ等には、それぞれ対応するプロセッサ３３ａ等が実行すべき処理内容が制御装置５により設定された順序に従って制御装置５から順番に送信されて一時的に記憶されるようになっており、プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄは、タイミングコントローラ３７で指定された所定のタイミングでレジスタ３９ａ、３９ｂ、３９ｃ、３９ｄから処理内容を順番に読み出してその処理内容を実行するようになっている。
【００５３】
なお、本実施形態では、ストリームデータ処理装置１における処理のリアルタイム化を図るために、プロセッサ３３ａ等は、入力された画像データに対して決められた演算処理を行う図３に示すような各フィルタ回路を備えるように構成されており、レジスタ３９ａ等にはフィルタ番号やフィルタ回路を表すアルファベット等のフィルタ回路を特定するための情報が一時記憶されて、プロセッサ３３ａ等に用いられるフィルタ回路が指定されるようになっている。
【００５４】
ここで、レジスタ３９ａ等からプロセッサ３３ａ等にフィルタ番号等と同時に随時フィルタ回路の閾値の値を入力して閾値を変更するように構成することも可能である。また、本実施形態のようにストリームデータ処理装置１がＦＰＧＡを用いて構成されていれば、プロセッサ３３ａ等を構成している複数のフィルタ回路をＦＰＧＡのコンフィギュレーションデータで書き換えて追加したり改良したりすることが可能となる。さらに、レジスタ３９ａ等からフィルタ番号等を送信する代わりに、例えば、ＦＰＧＡのコンフィギュレーションデータで書き換えてプロセッサ３３ａ等のフィルタ回路のデータを書き換えるように構成することも可能である。
【００５５】
プロセッサ３３ａ等の出力側に接続された出力データバス３４ａ、３４ｂ、３４ｃ、３４ｄには、メモリ３５ａ、３５ｂ、３５ｃ、３５ｄの入力線がスイッチ３８を介してそれぞれ接続されており、前述した入力データバス３２ａ等の場合と同様に、スイッチ３８は、制御装置５によりスイッチ設定が切り替えられることで、いずれかのプロセッサ３３ａ等から出力された出力データバス３４ａ等を伝達されるストリームデータをいずれかのメモリ３５ａ等に入力するようになっている。
【００５６】
本実施形態では、記憶手段であるメモリ３５ａ、３５ｂ、３５ｃ、３５ｄには、デュアルポートＲＡＭ（dual port RAM）が用いられている。
【００５７】
また、出力データバス３４ａ等の最下流側には、出力ポート３６が接続されていて、出力ポート３１は、制御装置５により指定された出力データバス３４ａ等を流れてくるストリームデータを出力バッファ４に出力するようになっている。
【００５８】
制御装置５には、本実施形態ではＦＰＧＡ内に構築することができる組み込み用プロセッサが用いられている。また、制御装置５には、ストリームデータの処理手順を表す木構造データフローグラフが図示しないメモリに保存されるようになっている。本実施形態では、木構造データフローグラフは、ＬＩＳＰ言語に用いられるＳ式で記述されており、制御装置５は、木構造データフローグラフや後述するサブグラフの各ノードとメモリのアドレスとを対応させながら後述するストリームデータ処理方法に従って木構造データフローグラフを分割してメモリ内にサブグラフを生成するようになっている。
【００５９】
制御装置５は、前記サブグラフを構成する各ノードに対応する各処理内容をプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける順序を設定してレジスタ３９ａ、３９ｂ、３９ｃ、３９ｄに出力し、プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに読み取らせてプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄの処理内容を制御し、また、プロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄへの処理内容の割り付けに応じて切り替えるためのスイッチ設定を形成して各スイッチ３８に送信して各デバイス間のストリームデータの流れを制御するようになっている。
【００６０】
次に、前記ストリームデータ処理装置に用いられるストリームデータ処理方法について説明する。
【００６１】
以下では、処理装置３の処理手段であるプロセッサ３３ａ等に入力される処理内容に対応するノードで構成された図４に示す木構造データフローグラフで表現される処理手順に基づいてストリームデータを処理する場合を例として説明する。なお、図４等で、アルファベットが記載されているノードは一定の処理内容に対応するノードであり、数字が記載されているノードはストリームデータの入力または出力を表すノードである。また、アルファベットは単にノードを順番に表すためのものであり、フィルタ回路を表すアルファベットではない。
【００６２】
本実施形態に係るストリームデータ処理方法による操作は、図５に示す基本フローに従って実行される。すなわち、本実施形態では、まず、木構造データフローグラフを分割してサブグラフを生成するサブグラフ生成工程（ステップＳ１）が行われ、続いて、生成されたサブグラフを構成する各ノードに割り当てられた処理内容を処理装置のプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける順序を設定する割付順設定工程（ステップＳ２）が行われ、最後に、設定された順序に従って処理内容をプロセッサに順番に割り付けてストリームデータの処理を行う処理工程（ステップＳ３）が行われる。
【００６３】
サブグラフ生成工程（ステップＳ１）は、図６に示すフローチャートに従って、ストリームデータの処理手順を表す木構造データフローグラフを、複数のストリームデータを入力して処理を行う処理内容に対応する合流ノード、すなわち前記画像処理の例で言えば２入力の画像フィルタに対応する合流ノードとその合流ノードのデータ処理上流側の各ノードとの間で分割してサブグラフを生成し、さらに前記ストリームデータ処理装置１で実行可能な長さのサブグラフに分割する工程である。
【００６４】
サブグラフ生成工程（ステップＳ１）では、木構造データフローグラフは、複数のストリームデータを入力して処理を行う処理内容に対応する合流ノードとその合流ノードのデータ処理上流側の各ノードとの間で分割される（ステップＳ１１）。例えば、図７に示すように、木構造データフローグラフは合流ノードＧとその上流側のノードＤ、Ｆとの間で分割される。その際、図８に示すように分割された部分に新たに入出力ノード８、９が設定される。
【００６５】
そして、合流ノードの枝としてストリームデータの入力ノード以外のノードが存在しなくなるまでこの操作が繰り返される。すなわち、図８の木構造データフローグラフでは、さらに合流ノードＩ、Ｐ、Ｔとその上流側のノードＢ、Ｈ、Ｍ、Ｏ、Ｋ、Ｓとの間で分割され、入出力ノード７、１０、１２、１３、１１、１４が設定されて、図９に示すような各サブグラフが生成される。
【００６６】
続いて、サブグラフ生成工程では、サブグラフの長さすなわちアルファベットが記載されている処理内容に対応するノードの数がストリームデータ処理装置１の処理可能長であるプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄの数ｎ２より大きい場合、そのサブグラフはそのままでは実行できないから、データ処理の最上流から下流側に向かってｎ２番目のノードとｎ２＋１番目のノードとの間で分割され、入出力ノードが設定されて、新たな２つのサブグラフが生成される（図６：ステップＳ１２）。そして、処理可能長より長いサブグラフがなくなるまでこの操作が繰り返される。
【００６７】
本実施形態では、前述したようにｎ２＝４であり、図９に示した各サブグラフはすべてサブグラフの長さが４以下であるからこの操作は行われないが、例えば図１０に示すように長さが５のサブグラフがある場合には、そのサブグラフは上流側から４番目のノードと５番目のノードの間で再分割され、入出力ノードが設定されて、処理手段が実行可能な長さとされた２つのサブグラフが新たに生成される。
【００６８】
このようにして、サブグラフ生成工程では、図９に示したように、木構造データフローグラフがストリームデータ処理装置１で実行可能な長さの複数のサブグラフａ〜ｉに分割される。サブグラフの番号ａ〜ｉは適宜付される。
【００６９】
サブグラフ生成工程では、続いて、装置の処理速度を向上させるために、重複する処理の削除が行われる（図６：ステップＳ１３）。すなわち、前記工程で分割されて生成された複数のサブグラフのうち、他のサブグラフと同じストリームデータに対して同一の処理を行うサブグラフがあれば、それらのサブグラフのうち１つのサブグラフが残され、他のサブグラフは削除される。
【００７０】
例えば、図９のサブグラフａとサブグラフｅにおいて、入力データ１および入力データ５と処理内容Ａ、Ｂおよび処理内容Ｎ、Ｏが同一であれば、サブグラフｅは削除される。その際、図１１に示すように、削除されるサブグラフｅの出力データ１３を入力データとするサブグラフｈの入力データ１３が、残されるサブグラフａの出力データ７に変更される。このように変更することで、サブグラフｅと同一の処理内容を有するサブグラフａの出力データ７がサブグラフｈに入力されるようになる。
【００７１】
この操作は他のサブグラフと同じストリームデータに対して同一の処理を行うサブグラフが存在しなくなるまで繰り返される。その操作を行うことで、同じデータに対する同一の処理を重複して行わないため処理速度が向上される。
【００７２】
また、この操作はサブグラフの一部について行うことも可能である。本実施形態では、前記サブグラフの削除を行った後、残った複数のサブグラフのうち、他のサブグラフの一部と同じストリームデータに対して同一の処理を行うサブグラフの一部があれば、その一部が１つのサブグラフとしてさらに分割される。
【００７３】
例えば、図１２に示す３つのサブグラフｐ、ｑ、ｒのうち、まず、サブグラフｐ、ｑが入力データ１および入力データ２と処理内容Ａ、Ｂ、Ｃおよび処理内容Ｅ、Ｆ、Ｇが同一であり、処理内容Ｄと処理内容Ｈとが異なれば、サブグラフｐ、ｑはそれぞれノードＣとノードＤとの間およびノードＧとノードＨとの間でそれぞれ分割され、分割された部分に新たな入出力ノード７が設定される。そして、分割された処理内容Ｄと処理内容Ｈを含む新たなサブグラフｓ、ｔがそれぞれ生成され、サブグラフｑは削除される。
【００７４】
さらに、残されたサブグラフｐとサブグラフｒが、入力データ１および入力データ３と処理内容Ａ、Ｂおよび処理内容Ｉ、Ｊが同一であり、処理内容Ｃと処理内容Ｋとが異なれば、サブグラフｐ、ｒはそれぞれノードＢとノードＣとの間およびノードＪとノードＫとの間でそれぞれ分割され、分割された部分に新たな入出力ノード８が設定される。そして、分割された処理内容Ｃと処理内容Ｋを含む新たなサブグラフｕ、ｖがそれぞれ生成され、サブグラフｒは削除される。そして、他のサブグラフの一部と同じストリームデータに対して同一の処理を行う部分を有するサブグラフが存在しなくなるまでこの操作が繰り返される。
【００７５】
なお、例えば、図１２のサブグラフｐ、ｑにおいて、入力データ１と入力データ２とが同じで処理内容Ｂ、Ｃと処理内容Ｆ、Ｇとが同一であっても処理内容Ａと処理内容Ｅが異なれば、処理内容Ｂ、Ｆに入力されるデータは互いに異なるから、このような場合は、サブグラフｐ、ｑは同じストリームデータに対して同一の処理を行う部分を持たない。従って、このようなサブグラフｐ、ｑについては、前記操作は行われない。
【００７６】
また、この操作は、木構造データフローグラフの合流ノードの上流側での分割（図６：ステップＳ１１）の前に行うこと可能である。すなわち、例えば図１３に示すように、木構造データフローグラフに同じストリームデータに対して同一の処理を行うノード列がある場合には、予めそのノード列をサブグラフとして分割して分割された部分に新たな同じ番号の入出力ノードを設定し、そのうちの１つのサブグラフだけを残すようにすることも可能である。この場合、残されたサブグラフに合流ノードがあれば、木構造データフローグラフを合流ノードの上流側で分割する際に、そのサブグラフについても合流ノードの上流側でさらに分割する。
【００７７】
次に、図５に示す基本フローに従って、割付順設定工程（ステップＳ２）が行われる。割付順設定工程は、前記サブグラフ生成工程（ステップＳ１）で生成されたサブグラフを構成する各ノードに対応する各処理内容をストリームデータ処理装置１の処理手段である複数のプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける順序を設定する工程である。この工程では、前述したスイッチ設定もあわせて形成される。
【００７８】
サブグラフを構成する各ノードに対応する各処理内容をプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける方法としては、最も単純には、処理できるサブグラフから順に割り付けていく方法が挙げられる。
【００７９】
例えば、図９の各サブグラフでは、サブグラフｆ〜ｉはサブグラフａ〜ｅの処理が終わらないと処理を実行できないから、まず、サブグラフａ〜ｅの処理を行うように順序を設定する。例えば、まずサブグラフａ、ｂを組み合わせてプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける最初の処理内容の組を［Ａ、Ｂ、Ｃ、Ｄ］とし、サブグラフａの出力データ７をメモリ３５ａに、またサブグラフｂの出力データ８をメモリ３５ｂに書き込むようにスイッチ設定を形成する。続いて、サブグラフｃ、ｄを組み合わせて２番目の処理内容の組を［Ｅ、Ｆ、Ｌ、Ｍ］とし、それぞれの出力データ９、１２をメモリ３５ｃ、３５ｄに書き込むようにスイッチ設定を形成する。このようにサブグラフを構成する各ノードに対応する各処理内容をストリームデータ処理装置１のプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄに割り付ける順序とスイッチ設定とを形成していく方法である。
【００８０】
本実施形態では、ストリームデータ処理装置１の処理速度のさらなる向上やメモリ使用率の低減を目的として、割付順設定工程では、以下に示す規則１、２のいずれか１つ或いはそれらの組み合わせに従って割り付け順序やスイッチ設定が形成されるようになっている。
【００８１】
［規則１：処理速度向上のための処理内容の割り付け］
この規則は、割り付け順序の設定方法は、処理装置３での処理速度を向上させるためすなわち処理時間を短縮するために、同時に処理されるサブグラフの処理内容の数をそろえるようにサブグラフを再分割して処理装置の処理手段に割り付ける順序を設定するものである。
【００８２】
規則１の細則（１−１）、（１−２）は、
（１−１）図４の木構造データフローグラフ上で出力ストリームデータに対応するルートノードすなわち数字６が記入されているノードからの距離が遠いサブグラフを優先して選択する。具体的には、図９に示すサブグラフａ〜ｉをそれぞれ１つのノードに置き換えた場合、図４に示す木構造データフローグラフは図１４に示す木構造データフローグラフに置き換えられるが、グラフ上方に数字で表現されているルートノードからの距離が遠いサブグラフを優先する、
（１−２）ルートノードからの距離が等しい場合は番号が若いサブグラフを優先して選択する、
である。
【００８３】
以上の細則（１−１）、（１−２）によれば、図１４の木構造データフローグラフでは、各サブグラフａ〜ｉの優先順位は各サブグラフに付した数字で表される順番になる。
【００８４】
この細則（１−１）、（１−２）の下で、この規則１では、下記の手順で割り付けの順序を設定する。以下では、仮に図２の処理装置３でプロセッサの数ｎ２が１０個であり、また、図１４の木構造データフローグラフのサブグラフａ〜ｅが図１５に示すようなサブグラフである場合を例に説明する。
【００８５】
なお、下記の規則において、
Ｎ：同時処理可能ストリームデータ数（すなわちデータバスの本数ｎ１、プロセッサの個数ｎ２、メモリの個数ｎ３のうちの最小の数であり、この例では４）
Ｉｎ：サブグラフごとの入力ストリームデータ数（すなわちサブグラフの最上流側のノードが合流ノードの場合は２、それ以外は１）
Ｐ：同時処理するサブグラフの本数
Ｋｎ：ｎ番目のサブグラフへのプロセッサの割り付け数
Ｌｎ：ｎ番目のサブグラフの長さ
である。
【００８６】
［１］Ｉｎの合計がＮとなるように処理するサブグラフを選択する。処理できるサブグラフが足りない場合は処理できるサブグラフだけを選択する。
【００８７】
ここでは、前記細則（１−１）より、まずサブグラフｂ、ｃが選択される。そしてサブグラフｂのＩｎは２、サブグラフｃのＩｎは１だからＩｎの合計は３であり、処理できるサブグラフがあればさらにもう１つ選択することができる。そこで、ルートノードからの距離が２の処理可能なサブグラフａ、ｄ、ｅの中から細則（１−２）に従ってサブグラフａが選択される。すなわち、この段階でサブグラフｂ、ｃ、ａが選択される。
【００８８】
［２］選択されたそれぞれのサブグラフに対するプロセッサの割り当て数Ｋｎをｎ２／Ｐの整数部分とする。Ｌｎがｎ２／Ｐの整数部分より小さい場合はＫｎの値をＬｎの値とする。
【００８９】
ここでは、［１］で選択されたサブグラフがサブグラフｂ、ｃ、ａであるからＰ＝３。また、プロセッサの個数ｎ２が１０であるから１０／３の整数部分は３。そこで、サブグラフｂ、ｃ、ａはＫｂ＝Ｋｃ＝Ｋａ＝３となるが、サブグラフａは長さＬａが１だからＫａ＝１とされる。すなわち、図１５に示すように、この段階で、それぞれのサブグラフｂ、ｃ、ａに対するプロセッサの割り当て数Ｋｎは、Ｋｂ＝３、Ｋｃ＝３、Ｋａ＝１となる。
【００９０】
［３］Ｋｎの合計がプロセッサの個数ｎ２より小さければ、Ｌｎ−Ｋｎが大きいサブグラフから順にＫｎの合計がプロセッサの個数ｎ２に等しくなるまでＫｎを１ずつ増加させる。一巡してもなお条件を満たさなければ、［３］の操作を繰り返す。
【００９１】
ここでは、Ｋｂ＋Ｋｃ＋Ｋａ＝７でｎ２＝１０より小さいから、まず、図１５に示すように、Ｌｎ−Ｋｎが最も大きいサブグラフｂにプロセッサが１つ割り当てられＫｂが１増加されて４となる。Ｋｂ＋Ｋｃ＋Ｋａ＝８となるがまだｎ２より小さいから操作が繰り返される。続いて、サブグラフｂ、ｃのＬｎ−Ｋｎが２で等しいから前記細則（１−２）に従って番号が若いサブグラフｂが選択されてＫｂがさらに１増加されて５になる。しかし、まだＫｂ＋Ｋｃ＋Ｋａ＝９であるからＬｎ−Ｋｎが２で最も大きいサブグラフｃにプロセッサが１つ割り当てられＫｃが１増加されて４になる。
【００９２】
［４］各サブグラフを先頭からＫｎの位置で再分割し、新たな入出力ノードを挿入する。
【００９３】
ここでは、サブグラフｂのＫｂは５であるから、図１６に示すようにサブグラフｂは先頭から５番目のノードと６番目のノードとの間で再分割され、新たな入出力ノード１６が挿入され、サブグラフｂとサブグラフｂ´が生成される。また、サブグラフｃはＫｃ＝４であるから先頭から４番目のノードと５番目のノードとの間で再分割され、新たな入出力ノード１７が挿入されて、サブグラフｃ、ｃ´が生成される。
【００９４】
［５］割り当て個数Ｋｎに従って連続するプロセッサを各サブグラフに割り付ける。
【００９５】
以上のようにしてサブグラフａと再分割されたサブグラフｂ、ｃとを１０個のプロセッサに割り当てる。すなわち、サブグラフｂ、ｃ、ａのそれぞれの処理内容からプロセッサに割り付ける最初の処理内容の組を［Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｈ、Ｉ、Ｊ、Ｋ、Ａ］とし、例えばサブグラフｂ、ｃ、ａの出力データ１０、１１、９をそれぞれメモリ３５ａ、３５ｂ、３５ｃに書き込むようにスイッチ設定を形成する。なお、この場合、処理装置３の構造から分かるように１つのサブグラフに対応する処理内容の組が連続するように割り付けられる。
【００９６】
続いて、以後の処理内容の組を設定するために、前記［１］〜［５］の操作が繰り返される。２番目の処理内容の組の設定について言えば、［１］では、まず前記細則（１−１）が適用されて、サブグラフｂ、ｃの残りのサブグラフｂ´、ｃ´が選択され、サブグラフｂ´、Ｃ´のＩｎはそれぞれ１だから、さらに処理できるサブグラフとしてルートノードからの距離が２の処理可能なサブグラフｄ、ｅの中から細則（１−２）に従ってサブグラフｄが選択される。従って、サブグラフｅは選択されない。
【００９７】
［２］の操作では、Ｐ＝３でｎ２／Ｐの整数部分は３だから、サブグラフｂ´、ｃ´、ｄはＫｂ´＝Ｋｃ´＝Ｋａ＝３となるが、Ｌｂ´とＬｃ´がともに１だからＫｂ´＝Ｋｃ´＝１となり、［３］の操作でＫｎの合計がプロセッサの個数ｎ２より小さいから、サブグラフｄのＫｄを１増加し、さらに１増加してＫｄ＝５となり、サブグラフｄのノードがすべて割り当てられる。そのため、［４］の操作は不必要となり、［５］の操作で、２番目の処理内容の組が［Ｇ、Ｌ、Ｍ、Ｎ、Ｏ、Ｐ、Ｑ、−、−、−］とされ、スイッチ設定が形成される。なお前記組で−はそのプロセッサには処理内容が割り付けられないことを意味する。
【００９８】
なお、この規則１の操作においては、サブグラフ生成工程（図５：ステップＳ１）の重複する処理の削除（図６：ステップＳ１３）でサブグラフや木構造データフローグラフから同一の処理を行うノード列の新たなサブグラフ化および残りのサブグラフの削除が行われた場合、すなわち、例えば図１７（Ａ）に示す木構造データフローグラフでサブグラフａ、ｅが同一の処理を行うサブグラフである場合には、各サブグラフをそれぞれ１つのノードに置き換えた木構造データフローグラフを図１７（Ｂ）に示すグラフのように捉え、サブグラフａをルートノードから最も遠いサブグラフとして扱う。なお、図１７（Ａ）のグラフは図１４と同じグラフである。
【００９９】
［規則２：メモリ使用率の増大を抑制できる処理内容の割り付け］
この規則は、合流ノードの各枝の処理を行った直後にその合流ノードの処理を行い、２つの入力データ（メモリ使用率＝２）を１つのデータ（メモリ使用率＝１）に収斂させながら処理を行うことで記憶手段としてのメモリ３５ａ、３５ｂ、３５ｃ、３５ｄのメモリ使用率の増大を抑制するように処理装置の処理手段に割り付ける順序を設定するものである。
【０１００】
規則２の細則は、木構造データフローグラフのリーフノード、すなわち図４の木構造データフローグラフの最上流側の入力データに対応するノード１〜５の数をＲｎとした場合、
（２−１）ルートノードから見た場合にＲｎが大きい方のノードを優先し、そのノードに付属するノードを優先する、
（２−２）あるノードから見た場合にＲｎが大きい方のノードを優先する、
である。
【０１０１】
この規則２では、図１４と同様に木構造データフローグラフを構成するサブグラフをそれぞれ１つのノードに置き換えた図１８に示すように、まず、細則（２−１）に従ってルートノードから見てリーフノードの数Ｒｎが大きいノードｆが選択され、続いて細則（２−２）に従ってノードｆから見てＲｎが大きいノードｇが選択される。すなわち、最初にサブグラフｂ、ｃの処理が行われ、続いてサブグラフｇとサブグラフａの処理が行われ、続いてサブグラフｆの処理が行われる。そして、ノードｈ側の処理が行われる。
【０１０２】
次に、図５に示した基本フローに従って、処理工程（ステップＳ３）が行われる。処理工程では、前記割付順設定工程（ステップＳ２）で生成された割り付け順序およびスイッチ設定に従ってストリームデータ処理装置１のプロセッサ３３ａ、３３ｂ、３３ｃ、３３ｄにそれぞれ処理内容が順番に割り付けられ、ストリームデータに対して順次処理が行われる。
【０１０３】
具体的な割り付け操作等は、前記ストリームデータ処理装置１の制御装置５の構成およびプロセッサ３３ａ、３３、３３ｂ、３３ｃ、３３ｄやレジスタ３９ａ、３３ｂ、３３ｃ、３３ｄの構成で述べたので、ここでは省略する。なお、割付順設定工程（ステップＳ２）と処理工程（ステップＳ３）とを同時並行で行うように構成することも可能である。
【０１０４】
次に、本実施形態に係るストリームデータ処理方法およびストリームデータ処理装置１の作用について説明する。
【０１０５】
ストリームデータ処理装置１の制御装置５におけるサブグラフａ〜ｉの生成については、前述したストリームデータ処理方法のサブグラフ生成工程（図５：ステップＳ１）で述べられているので、ここでは説明を省略する。
【０１０６】
制御装置５は、仮に図９の各サブグラフａ〜ｉがそれ自体互いに同一の処理内容を有さず、またその一部も同一の処理内容を有しないためさらなる分割を行わないとすると、図９の各サブグラフａ〜ｉを元に割り付け順序を設定する。
【０１０７】
まず、前記規則１に従って割り付け順序を設定する場合、制御装置５は、細則（１−１）、（１−２）の下で、前記［１］に従って、まず、サブグラフｂ、ｃを優先的に選択し、さらにルートノードからの距離が２の処理可能なサブグラフａ、ｄ、ｅの中からサブグラフａ、ｄを選択する。
【０１０８】
次に、［２］に従って、同時処理するサブグラフの本数Ｐはサブグラフｂ、ｃ、ａ、ｄの４、プロセッサの数ｎ２は４だからｎ２／Ｐ＝１となり、それぞれのサブグラフｂ、ｃ、ａ、ｄに対するプロセッサの割り当て数ＫｎはＫｂ＝Ｋｃ＝Ｋａ＝Ｋｄ＝１となる。［３］ではすでにＫｎの合計がプロセッサの個数ｎ２と等しいからＫｎの修正は行われず、［４］の各サブグラフの再分割も行われない。
【０１０９】
このようにしてサブグラフｂ、ｃ、ａ、ｄには１つずつプロセッサが割り当てられ、［５］の割り付けでは、サブグラフｂ、ｃ、ａ、ｄのそれぞれの最初の処理内容からプロセッサ３３ａ〜３３ｄに割り付ける最初の処理内容の組を［Ｃ、Ｅ、Ａ、Ｌ］とし、例えばメモリ設定は、入力ポート３１から入力データ２、３、１、４をそれぞれ入力データバス３２ａ〜３２ｂに流し、それぞれプロセッサ３３ａ〜３３ｄに入力するようにしてプロセッサ３３ａ〜３３ｄからの出力データをそれぞれメモリ３５ａ〜３５ｄに書き込むようにスイッチ設定を形成する。
【０１１０】
続いて、同様にして、プロセッサ３３ａ〜３３ｄに割り付ける２番目の処理内容の組をサブグラフｂ、ｃ、ａ、ｄの残りの処理内容から［Ｄ、Ｆ、Ｂ、Ｍ］とし、スイッチ設定は、メモリ３５ａ〜３５ｄからストリームデータをそれぞれ読み出してプロセッサ３３ａ〜３３ｄに入力し、それらからの出力データ８、９、７、１２をメモリ３５ａ〜３５ｄに書き込むように設定する。
【０１１１】
さらに続いて、制御装置５は、図１４のルートノードから距離が２の残りのサブグラフｅ、ｇを優先的に選択し、この場合はサブグラフｆ、ｈはサブグラフｇ、ｅの処理が終わらないと処理を行うことができないので選択しない。そして、図９からサブグラフｅ、ｇはともに長さＬｎが２であるからプロセッサ３３ａ〜３３ｄに割り付ける３番目の処理内容の組をサブグラフｅ、ｇの処理内容から［Ｎ、Ｏ、Ｇ、Ｈ］とし、スイッチ設定は、入力ポート３１から入力データ５がプロセッサ３３ａに入力されるようにして、また、メモリ３５ａ、３５ｂから入力データ８、９を読み出してプロセッサ３３ｃに入力するようにしてプロセッサ３３ｂ、３３ｄからの出力データ１３、１０をそれぞれメモリ３５ａ、３５ｂに書き込むように設定する。
【０１１２】
同様にして、制御装置５は、プロセッサ３３ａ〜３３ｄに割り付ける４番目の処理内容の組をサブグラフｆ、ｈから設定するが、サブグラフｆ、ｈの長さＬｎがそれぞれ３、４であるから、まず、前記［２］に従って、同時処理するサブグラフの本数Ｐはサブグラフｆ、ｈの２、プロセッサの数ｎ２は４だからｎ２／Ｐ＝２となり、それぞれのサブグラフｆ、ｈに対してプロセッサをそれぞれ２つずつ割り当てる。また、［４］に従って、サブグラフｆ、ｈをそれぞれ２番目と３番目のノードの間で再分割してサブグラフｆ´（処理内容はＫ）とサブグラフｈ´（処理内容はＲとＳ）を生成させる。
【０１１３】
そして、プロセッサ３３ａ〜３３ｄに割り付ける４番目の処理内容の組をサブグラフｆ、ｈの処理内容から［Ｉ、Ｊ、Ｐ、Ｑ］とし、メモリ設定は、入力データ７、１０をメモリ３５ｃ、３５ｂからそれぞれ読み出してプロセッサ３３ａに入力してメモリ３５ｂに書き込み、入力データ１２、１３をメモリ３５ｄ、３５ａからそれぞれ読み出してプロセッサ３３ｃに入力してその出力をメモリ３５ａに書き込むように設定する。
【０１１４】
続いて、制御装置５は、サブグラフｆ´、ｈ´からプロセッサに割り付ける５番目の処理内容の組を［Ｋ、Ｒ、Ｓ、−］とし、メモリ設定は、メモリ３５ｂ、３５ａからそれぞれストリームデータを読み出してプロセッサ３３ａ、３３ｂに入力し、プロセッサ３３ａ、３３ｃからの出力データ１１、１４をそれぞれメモリ３５ｃ、３３ｄに書き込むように設定する。
【０１１５】
最後に、制御装置５は、サブグラフｉからプロセッサに割り付ける６番目の処理内容の組を［Ｔ、Ｕ、Ｖ、−］とし、メモリ設定は、メモリ３５ｃ、３５ｄからストリームデータを読み出してプロセッサ３３ａに入力し、プロセッサ３３ｃからの出力データ６を出力ポート３６から出力するように設定する。
【０１１６】
制御装置５は、実働時には、このようにして設定した割り付け順序に従って処理内容を順番にプロセッサ３３ａ〜３３ｄに割り付けてストリームデータに対する処理を行う。すなわち、制御装置５は、図１９〜図２４に示すように前記最初の処理内容の組から６番目の処理内容の組をプロセッサ３３ａ〜３３ｄに割り付けて最終的に出力ストリームデータ６を出力する。
【０１１７】
このように前記規則１の［１］〜［５］、特に［２］、［３］の手順に従って同時に処理されるサブグラフの処理内容の数をそろえるようにサブグラフを再分割して処理装置の処理手段に割り付けると、データの処理段数を小さくすることができ、データの処理段数をＦ、データの読み出し／書き込みにかかる時間をＤ、プロセッサにストリームデータの先頭が入力されてから先頭が出力されるまでの遅延時間をＥとした場合に
Ｇ＝Ｄ＋Ｅ×Ｆ    …（１）
で表される１回あたりの処理時間を短縮することができる。
【０１１８】
次に、前記規則２に従って割り付け順序を設定する場合、制御装置５は、図１８に示した処理の順番に従って、細則（２−１）、（２−２）の下で、まず、サブグラフｂ、ｃからプロセッサ３３ａ〜３３ｄに割り付ける最初の処理内容の組を［Ｃ、Ｄ、Ｅ、Ｆ］とし、メモリ３５ａ、３５ｂに出力データ８、９が書き込まれるように設定する。
【０１１９】
続いて、サブグラフｇから２番目の処理内容の組を［Ｇ、Ｈ、−、−］とし、メモリ３５ａ、３５ｂからデータ８、９を読み出して出力データ１０をメモリ３５ａに書き込むように設定する。さらに、サブグラフａから３番目の処理内容の組を［Ａ、Ｂ、−、−］とし、出力データ７をメモリ３５ｂに書き込むように設定する。
【０１２０】
続いて、サブグラフｆから４番目の処理内容の組を［Ｉ、Ｊ、Ｋ、−］とし、メモリ３５ｂ、３５ａからデータ７、１０を読み出して出力データ１１をメモリ３５ａに書き込むように設定する。さらに、サブグラフｄ、ｅから５番目の処理内容の組を［Ｌ、Ｍ、Ｎ、Ｏ］とし、出力データ１２、１３をメモリ３５ｂ、３５ｃに書き込むように設定する。
【０１２１】
続いて、サブグラフｈから６番目の処理内容の組を［Ｐ、Ｑ、Ｒ、Ｓ］とし、メモリ３５ｂ、３５ｃからデータ１２、１３を読み出して出力データ１４をメモリ３５ｂに書き込むように設定する。最後に、サブグラフｉから７番目の処理内容の組を［Ｔ、Ｕ、Ｖ、−］とし、出力データ１１、１４をメモリ３５ａ、３５ｂから読み出してプロセッサ３３ｃからの出力データ６を出力ポート３６から出力するように設定する。
【０１２２】
このように前記規則２に従って合流ノードの各枝の処理を行った直後にその合流ノードの処理を行い、２つの入力データを１つのデータに収斂させながら処理を行うことでメモリ使用率の増大を抑制することができる。本実施形態では、前記のようにメモリ３５ａ〜３５ｃの３つだけでストリームデータの処理を行うことができた。
【０１２３】
図２５に示すような一般的な木構造データフローグラフの場合、ルートノードからの距離が遠い順に処理を行っていくとすると、ルートノードからの距離ｎの２ｎ個のノードの処理を行うためには１個のノードにそれぞれ２個ずつ入力させるデータを保存するためのメモリが２ｎ＋１個必要である。しかし、本実施形態の規則２に従った処理では、メモリはｎ＋１個あればその処理を行うことができる。
【０１２４】
以上のように、本実施形態に係るストリームデータ処理方法およびストリームデータ処理装置１によれば、ストリームデータ処理装置を１つの装置として構成したため、装置間の待ち合わせ処理のためにパイプライン処理の実行タイミングの制御や一時的な処理停止を行う必要がなく、処理速度の低下を防止することが可能となる。それと同時に、制御や一時停止を行わせるための新たなハードウエアを備える必要もなく、装置の処理回路の使用効率の低下も回避することが可能となる。
【０１２５】
また、処理手段であるプロセッサに処理内容を割り付けながら処理を行うように構成したため、装置の回路規模がコンパクトになり、しかも、どのような木構造データフローグラフに対応できる汎用性を具備することが可能となる。
【０１２６】
さらに、木構造データフローグラフを合流ノードの上流側で分割することで、あらゆる木構造データフローグラフを直線状のサブグラフ群に分割することが可能となり、直線状のサブグラフのノードに対応する処理内容をプロセッサに割り付けることで、処理回路を直列に繋いだ処理回路群を複数形成することができ、それらの処理回路群で同時並行処理すなわちパイプライン処理が実行可能となる。
【０１２７】
また、プロセッサに処理内容を割り付けて処理回路を形成していくため、割り付けの順序を設定しておけばタイムロスなくプロセッサに処理内容を割り付けることができ、装置の処理速度の低下を防止することができる。また、割り付け順序をプロセッサの処理と同時に行う場合にも、前記規則１に基づけば割り付け順序はプロセッサの処理にかかる時間よりも短い時間で設定されるから、プロセッサへの処理内容の割り付けによりタイムロスが生じることはない。
【０１２８】
特に、プロセッサに予め必要な処理回路を具備させておき、制御装置５がその処理回路の番号等を特定する情報を送信してプロセッサに処理内容を割り付けるようにすれば、プロセッサへの処理内容の割り付けを瞬間的に行うことが可能となる。
【０１２９】
また、木構造データフローグラフやサブグラフには同じデータに対して同一の処理を行うノード列が存在する場合がある。そのような場合、同一の処理内容を有するノード列を木構造データフローグラフやサブグラフから分割して同一の処理内容を有する複数の新たなサブグラフを生成させてそのうちの１つを残して他を削除し、或いは木構造データフローグラフを分割して同一の処理内容を有する複数のサブグラフが生成された場合には、１つのサブグラフを残して他を削除するように構成すれば、同じデータに対する同一の処理を重複して行わなくて済み、削除しない場合と比べて、削除されたノード列のノードに対応する処理内容の分だけ処理が減るため処理速度を向上させることが可能となる。
【０１３０】
また、前記規則１に従って割り付け順序を設定することによって処理速度がさらに向上される。また、前記規則２に従って割り付け順序を設定すれば、装置のメモリ使用率の増大を抑制することが可能となる。
【０１３１】
なお、本実施形態では、前記図５に示した基本フローをすべてストリームデータ処理装置１の制御装置５が行う場合について述べたが、例えば、基本フローのうちサブグラフ生成工程（ステップＳ１）について、木構造データフローグラフを人為的に分割してサブグラフを生成させた後、制御装置５に入力するようにしてもよい。また、割付順設定工程（ステップＳ２）までを人為的に行い、オペレータ等が作成した割り付け順序とスイッチ設定とを制御装置５に入力してもよい。
【０１３２】
また、図４の木構造データフローグラフでは、データ処理の最上流側のサブグラフすなわち図９のサブグラフａ〜ｅが、その最上流側のノードがすべて非合流ノードすなわち１つストリームデータを入力するノードである場合を示したが、最上流側のサブグラフの最上流側のノードが合流ノードであってもよい。
【図面の簡単な説明】
【０１３３】
【図１】本実施形態に係るストリームデータ処理装置の構成を示す図である。
【図２】図１の処理装置の構成を示す図である。
【図３】本実施形態のプロセッサに備えられる各種フィルタ回路を示す表である。
【図４】木構造データフローグラフの例を示す図である。
【図５】本実施形態に係るストリームデータ処理方法の基本フローを示すフローチャートである。
【図６】サブグラフ生成工程における操作手順を示すフローチャートである。
【図７】合流ノード上流側で分割された木構造データフローグラフを表す図である。
【図８】図７の木構造データフローグラフの分割された部分に設定された入出力ノードを表す図である。
【図９】図４の木構造データフローグラフから生成されたサブグラフを表す図である。
【図１０】処理手段が実行可能な長さのサブグラフを生成する手順を説明する図である。
【図１１】同一の処理内容を有するサブグラフを削除する手順を説明する図である。
【図１２】同一の処理内容を有するサブグラフの一部を分割する手順を説明する図である。
【図１３】同一の処理内容を有するノード列を分割された木構造データフローグラフを表す図である。
【図１４】サブグラフをそれぞれ１つのノードに置き換えた場合の木構造データフローグラフを説明する図である。
【図１５】規則１の手順［２］および［３］によるＫｎの変化を説明する図である。
【図１６】規則１の手順［４］で再分割されるサブグラフを示す図である。
【図１７】同一の処理を行うノード列をサブグラフ化した場合のルートノードからの距離を表す図であり、（Ａ）は図１４と同一のグラフ、（Ｂ）は変化後のグラフを表す。
【図１８】規則２による処理の順番を示す図である。
【図１９】最初の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２０】２番目の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２１】３番目の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２２】４番目の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２３】５番目の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２４】６番目の処理内容の組をプロセッサに割り付けた場合のストリームデータの流れを示す図である。
【図２５】一般的な木構造データフローグラフを表す図である。
【符号の説明】
【０１３４】
１  ストリームデータ処理装置
３３ａ、３３ｂ、３３ｃ、３３ｄ  プロセッサ
３５ａ、３５ｂ、３５ｃ、３５ｄ  ストリームデータバッファメモリ
５  制御装置
【図１】
2007164504.tif 000003
【図２】
2007164504.tif 000004
【図３】
2007164504.tif 000005
【図４】
2007164504.tif 000006
【図５】
2007164504.tif 000007
【図６】
2007164504.tif 000008
【図７】
2007164504.tif 000009
【図８】
2007164504.tif 000010
【図９】
2007164504.tif 000011
【図１０】
2007164504.tif 000012
【図１１】
2007164504.tif 000013
【図１２】
2007164504.tif 000014
【図１３】
2007164504.tif 000015
【図１４】
2007164504.tif 000016
【図１５】
2007164504.tif 000017
【図１６】
2007164504.tif 000018
【図１７】
2007164504.tif 000019
【図１８】
2007164504.tif 000020
【図１９】
2007164504.tif 000021
【図２０】
2007164504.tif 000022
【図２１】
2007164504.tif 000023
【図２２】
2007164504.tif 000024
【図２３】
2007164504.tif 000025
【図２４】
2007164504.tif 000026
【図２５】
2007164504.tif 000027