(57)【特許請求の範囲】
【請求項１】
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストを記述したタスク入力データ量表を格納する第１の格納部と、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを記述した部品別出力データ量表を格納する第２の格納部と、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、を記述したタスクグラフ接続表を格納する第３の格納部と、
前記タスク入力データ量表から、前記入力データ量が全て定まったタスクを対象タスクとして抽出する第１の処理と、前記タスクグラフ接続表から、前記対象タスクを実行する処理部品と前記対象タスクの次タスクの入力のリストとを取り出す第２の処理と、前記部品別出力データ量表から、前記対象タスクを実行する処理部品の各出力の出力データ量のリストを取り出す第３の処理と、前記タスク入力データ量表から、前記対象タスクの各入力の入力データ量のリストを取り出す第４の処理と、前記対象タスクの各入力の入力データ量と前記対象タスクを実行する処理部品の各出力の出力データ量とを基に、前記対象タスクの各出力の出力データ量を算出し、算出した各出力の出力データ量のリストを前記タスク出力データ量表に記述する第５の処理と、前記タスク入力データ量表における前記対象タスクの次タスクの入力の入力データ量として、前記対象タスクの対応する出力の出力データを記述する第６の処理と、を、前記複数のタスクの全てについて、前記入力データ量が全て定まったタスクから順次実行するデータ転送量算出部と、
前記タスクごとに、該タスクが持つ各出力の出力データ量であって前記データ転送量算出部が算出した各出力の出力データ量のリストを記述したタスク出力データ量表を格納する第４の格納部と、を有する、構成装置。
【請求項２】
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストを記述したタスク入力データ量表を格納する第１の格納部と、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを記述した部品別出力データ量表を格納する第２の格納部と、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、を記述したタスクグラフ接続表を格納する第３の格納部と、
前記タスク入力データ量表、前記部品別出力データ量表、および前記タスクグラフ接続表に基づいて、前記タスクごとに、該タスクが持つ各出力の出力データ量を算出するデータ転送量算出部と、
前記タスクごとに、該タスクが持つ各出力の出力データ量であって前記データ転送量算出部が算出した各出力の出力データ量のリストを記述したタスク出力データ量表を格納する第４の格納部と、
前記画像処理システムを、前記処理部品をバスに搭載し前記バス同士をスイッチおよびルータによって接続する特定のＮｏＣ構成にする際に、前記タスクグラフ接続表および前記タスク出力データ量表に基づいて、前記処理部品の配置を決定する構成決定部と、を有する、構成装置。
【請求項３】
前記画像処理システムを、前記処理部品をバスに搭載し前記バス同士をスイッチおよびルータによって接続する特定のＮｏＣ構成にする際に、前記タスクグラフ接続表および前記タスク出力データ量表に基づいて、前記処理部品の配置を決定する構成決定部をさらに有する、請求項１に記載の構成装置。
【請求項４】
前記構成決定部は、
全ての処理部品をバスに搭載可能な個数以下に区分する分け方を生成し、
前記分け方の中から、該分け方で全ての処理部品をバスに搭載した場合において、全てのバスについて、該バスに搭載した処理部品が実行するタスクの出力データ量の総和が該バスのデータ転送能力以内であるという第１の条件と、前記バス同士を接続し前記スイッチおよび前記ルータを経由する全ての転送経路について、該転送経路を転送される転送データ量が該転送経路のデータ転送能力以内であるという第２の条件と、を共に満たす分け方を選択し、
前記選択した分け方で全ての処理部品をバスに搭載するよう、前記処理部品の配置を決定する、請求項２または３に記載の構成装置。
【請求項５】
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置による構成方法であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストをタスク入力データ量表に記述する第１のステップと、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを部品別出力データ量表に記述する第２のステップと、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、をタスクグラフ接続表に記述する第３のステップと、
前記タスク入力データ量表、前記部品別出力データ量表、および前記タスクグラフ接続表に基づいて、前記タスクごとに、該タスクが持つ各出力の出力データ量を算出し、前記タスク入力データ量表から、前記入力データ量が全て定まったタスクを対象タスクとして抽出する第１の処理と、前記タスクグラフ接続表から、前記対象タスクを実行する処理部品と前記対象タスクの次タスクの入力のリストとを取り出す第２の処理と、前記部品別出力データ量表から、前記対象タスクを実行する処理部品の各出力の出力データ量のリストを取り出す第３の処理と、前記タスク入力データ量表から、前記対象タスクの各入力の入力データ量のリストを取り出す第４の処理と、前記対象タスクの各入力の入力データ量と前記対象タスクを実行する処理部品の各出力の出力データ量とを基に、前記対象タスクの各出力の出力データ量を算出し、算出した各出力の出力データ量のリストを前記タスク出力データ量表に記述する第５の処理と、前記タスク入力データ量表における前記対象タスクの次タスクの入力の入力データ量として、前記対象タスクの対応する出力の出力データを記述する第６の処理と、を、前記複数のタスクの全てについて、前記入力データ量が全て定まったタスクから順次実行し、前記タスクごとに、該タスクが持つ各出力の出力データ量であって前記算出した各出力の出力データ量のリストをタスク出力データ量表に記述する第４のステップと、を有する、構成方法。
【請求項６】
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置による構成方法であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストをタスク入力データ量表に記述する第１のステップと、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを部品別出力データ量表に記述する第２のステップと、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、をタスクグラフ接続表に記述する第３のステップと、
前記タスク入力データ量表、前記部品別出力データ量表、および前記タスクグラフ接続表に基づいて、前記タスクごとに、該タスクが持つ各出力の出力データ量を算出し、算出した各出力の出力データ量のリストをタスク出力データ量表に記述する第４のステップと、
前記画像処理システムを、前記処理部品をバスに搭載し前記バス同士をスイッチおよびルータによって接続する特定のＮｏＣ構成にする際に、前記タスクグラフ接続表および前記タスク出力データ量表に基づいて、前記処理部品の配置を決定する第５のステップと、を有する、構成方法。
【請求項７】
前記画像処理システムを、前記処理部品をバスに搭載し前記バス同士をスイッチおよびルータによって接続する特定のＮｏＣ構成にする際に、前記タスクグラフ接続表および前記タスク出力データ量表に基づいて、前記処理部品の配置を決定する第５のステップをさらに有する、請求項５に記載の構成方法。
【請求項８】
前記第５のステップでは、
全ての処理部品をバスに搭載可能な個数以下に区分する分け方を生成し、
前記分け方の中から、該分け方で全ての処理部品をバスに搭載した場合において、全てのバスについて、該バスに搭載した処理部品が実行するタスクの出力データ量の総和が該バスのデータ転送能力以内であるという第１の条件と、前記バス同士を接続し前記スイッチおよび前記ルータを経由する全ての転送経路について、該転送経路を転送される転送データ量が該転送経路のデータ転送能力以内であるという第２の条件と、を共に満たす分け方を選択し、
前記選択した分け方で全ての処理部品をバスに搭載するよう、前記処理部品の配置を決定する、請求項６または７に記載の構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、既存の画像処理システムを複数の処理部品（ＩＰ）に分解し、処理部品間の接続を変更して画像処理システムを再構成するための技術に関する。
【背景技術】
【０００２】
特定の画像処理を行うよう設計された画像処理システムがあったとき、その内部での処理順序の変更など、柔軟性を高めようとした場合には、画像処理システムを複数の処理部品に分解し、処理部品間の接続を変更して画像処理システムを再構成する。
【０００３】
ここで、画像処理システムを構成する処理部品間の接続を変更する一般的な方法の１つに、画像処理システムをＮｏＣ（Network-on-Chip）構成にする方法が挙げられる。
【０００４】
ＮｏＣは、複数の処理部品が集積回路上に搭載されているとき、これらの処理部品間の接続を柔軟に変更するための技術である。この技術は、複数の処理部品のそれぞれに「ルータ」を付加することが特徴である。ルータは、データを送受信するための配線で近隣のルータと相互に接続されている。すなわち、ルータは、複数の送信ポートを持っている。処理部品から出力されるデータには宛先が付随しており、ルータはこの宛先にしたがってデータを適切な送信ポートから送信する。ルータは、受信したデータを処理部品への入力とすること、処理部品の出力を送信すること、ならびに、受信したデータをそのまま送信（転送）することができる。本明細書においては、ルータ間の配線とルータとから形成される系を狭義のＮｏＣと表記する。
【０００５】
ＮｏＣに搭載されたルータの機能により所望の柔軟性を得られるが、ＮｏＣは、ルータを付加するために所要面積が増大するという問題点があった。
【０００６】
この問題に関し、画像処理システムをＢＭＮｏＣ（Bus-Mesh-NoC）構成にすると、ＮｏＣ構成よりも所要面積を小さくできることが、非特許文献１に記載されている。
【０００７】
ＢＭＮｏＣは、ＮｏＣの改良技術の１つであり、処理部品のそれぞれがバスに搭載されることが特徴である。バス上にルータがあり、ルータとルータ間の配線とから形成される部分は従来のＮｏＣに相当する。バス上にはスイッチを置き、複数のスイッチをルータに収容するという構成もありうる。
【０００８】
ここで、ＮｏＣとＢＭＮｏＣとを比較する。
【０００９】
ＮｏＣでは、処理部品間の十分な転送能力を実現するためには、配線を網目状あるいは完全メッシュで構成する必要がある。しかしながら、このように構成すると、ルータ間の配線が多くなる。また、ＮｏＣでは、データの宛先に付随する処理を行うための面積が必要であり、この面積はルータの数に比例して増えることになる。集積回路上では、これらの面積は、処理部品を実現するための面積から差し引かれることなり、処理部品の実現にあてる面積が損失していた。
【００１０】
一方、ＢＭＮｏＣでは、近い処理部品間のデータ転送についてはバスを用いることによって主に後者（ルータの面積）を節約することができる。また、異なるバスに搭載された処理部品間のデータ転送については、スイッチおよびルータを経由することになるが、こうした経路にはデータ量の少ない転送を割り当てることができる。これは、ＢＭＮｏＣ構成アルゴリズムによって実現し、これによって、ルータ間の配線が少なくても性能を維持できるため、主に前者（ルータ間の配線）を節約することができる。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】SeungJu Lee, Masao Yanagisawa, Tatsuo Ohtsuki and Nozomu Togawa, “BusMesh NoC: A Novel NoC Architecture Comprised of Bus-based Connection and Global Mesh Routers”, Circuits and Systems (APCCAS), 2010 IEEE Asia Pacific Conference on, 2010年12月, p. 712-715
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上述したように、画像処理システムをＢＭＮｏＣ構成にすると、ＮｏＣ構成よりも所要面積が小さくなるという利点がある。
【００１３】
ただし、ＢＭＮｏＣ構成アルゴリズムでは、ある処理部品をどのバスに搭載すると、その影響として、各箇所のバスおよびバス間を接続するネットワーク上の転送経路のデータ転送量がどのようになるかを算出し、バスおよび転送経路のそれぞれに固有のデータ転送能力を上限として、処理部品の配置を最適化している。そのため、バスおよび転送経路のそれぞれの固有のデータ転送能力については別に与えつつ、処理部品が実行する各タスクの出力データ量を事前に求めることが必要となる。
【００１４】
しかしながら、タスクの出力データ量は、一般には、実物のプロセッサや、プロセッサを模擬する専用のシミュレータにより計測するため、手間と時間を費やしてしまうという課題がある。
【００１５】
本発明の目的は、実物のプロセッサや専用のシミュレータを用いることなく、タスクの出力データ量を算出することができる技術を提供することにある。
【課題を解決するための手段】
【００１６】
本発明の画像処理システムの構成装置は、
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストを記述したタスク入力データ量表を格納する第１の格納部と、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを記述した部品別出力データ量表を格納する第２の格納部と、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、を記述したタスクグラフ接続表を格納する第３の格納部と、
前記タスク入力データ量表から、前記入力データ量が全て定まったタスクを対象タスクとして抽出する第１の処理と、前記タスクグラフ接続表から、前記対象タスクを実行する処理部品と前記対象タスクの次タスクの入力のリストとを取り出す第２の処理と、前記部品別出力データ量表から、前記対象タスクを実行する処理部品の各出力の出力データ量のリストを取り出す第３の処理と、前記タスク入力データ量表から、前記対象タスクの各入力の入力データ量のリストを取り出す第４の処理と、前記対象タスクの各入力の入力データ量と前記対象タスクを実行する処理部品の各出力の出力データ量とを基に、前記対象タスクの各出力の出力データ量を算出し、算出した各出力の出力データ量のリストを前記タスク出力データ量表に記述する第５の処理と、前記タスク入力データ量表における前記対象タスクの次タスクの入力の入力データ量として、前記対象タスクの対応する出力の出力データを記述する第６の処理と、を、前記複数のタスクの全てについて、前記入力データ量が全て定まったタスクから順次実行するデータ転送量算出部と、
前記タスクごとに、該タスクが持つ各出力の出力データ量であって前記データ転送量算出部が算出した各出力の出力データ量のリストを記述したタスク出力データ量表を格納する第４の格納部と、を有する。
【００１７】
本発明の画像処理システムの構成方法は、
複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成するための構成装置による構成方法であって、
前記タスクごとに、該タスクが持つ各入力の入力データ量のリストをタスク入力データ量表に記述する第１のステップと、
前記処理部品ごとに、該処理部品が持つ各出力の出力データ量のリストを部品別出力データ量表に記述する第２のステップと、
前記タスクごとに、該タスクを実行する処理部品と、該タスクの出力データが入力される次タスクの入力のリストと、をタスクグラフ接続表に記述する第３のステップと、
前記タスク入力データ量表、前記部品別出力データ量表、および前記タスクグラフ接続表に基づいて、前記タスクごとに、該タスクが持つ各出力の出力データ量を算出し、前記タスク入力データ量表から、前記入力データ量が全て定まったタスクを対象タスクとして抽出する第１の処理と、前記タスクグラフ接続表から、前記対象タスクを実行する処理部品と前記対象タスクの次タスクの入力のリストとを取り出す第２の処理と、前記部品別出力データ量表から、前記対象タスクを実行する処理部品の各出力の出力データ量のリストを取り出す第３の処理と、前記タスク入力データ量表から、前記対象タスクの各入力の入力データ量のリストを取り出す第４の処理と、前記対象タスクの各入力の入力データ量と前記対象タスクを実行する処理部品の各出力の出力データ量とを基に、前記対象タスクの各出力の出力データ量を算出し、算出した各出力の出力データ量のリストを前記タスク出力データ量表に記述する第５の処理と、前記タスク入力データ量表における前記対象タスクの次タスクの入力の入力データ量として、前記対象タスクの対応する出力の出力データを記述する第６の処理と、を、前記複数のタスクの全てについて、前記入力データ量が全て定まったタスクから順次実行し、前記タスクごとに、該タスクが持つ各出力の出力データ量であって前記算出した各出力の出力データ量のリストをタスク出力データ量表に記述する第４のステップと、を有する。
【発明の効果】
【００１８】
本発明によれば、処理部品に固有の出力データ量を部品別出力データ表として予め備えておき、この部品別出力データ表を用いてタスクの出力データ量を算出する。
【００１９】
その結果、実物のプロセッサや、プロセッサを模擬する専用のシミュレータが不要となるという効果を奏する。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施形態の構成装置のブロック図である。
【図２】既存の画像処理システムの例を示す図である。
【図３】画像処理システムをＮｏＣ構成にした例を示す図である。
【図４】画像処理システムをＢＭＮｏＣ構成にする際に必要となるタスクグラフの例を示す図である。
【図５】画像処理システムをＢＭＮｏＣ構成にした例を示す図である。
【図６Ａ】タスク入力データ量表の例を示す図である。
【図６Ｂ】部品別出力データ量表の例を示す図である。
【図６Ｃ】タスクグラフ接続表の例を示す図である。
【図６Ｄ】タスク出力データ量表の例を示す図である。
【図６Ｅ】タスク出力データ量表を作成するためのアルゴリズムを説明するフローチャートである。
【図７】ＢＭＮｏＣ構成アルゴリズムを説明するフローチャートである。
【発明を実施するための形態】
【００２１】
以下に、本発明を実施するための形態について図面を参照して説明する。
【００２２】
図１に、本実施形態の構成装置のブロック図を示す。
【００２３】
図１に示すように、本実施形態の構成装置は、タスク入力データ量表格納部１１と、部品別出力データ量表格納部１２と、タスクグラフ接続表格納部１３と、データ転送量算出部１４と、タスク出力データ量表格納部１５と、ＢＭＮｏＣ構成決定部１６と、ＢＭＮｏＣ構成データ格納部１７と、を有している。
【００２４】
本実施形態の構成装置は、複数のタスクのそれぞれを処理部品によって実行する画像処理システムを構成対象とし、その画像処理システムをＢＭＮｏＣ構成にするための装置である。
【００２５】
画像処理システムをＢＭＮｏＣ構成にする際には、タスクの接続関係を表す構成線図と、各タスクの各出力の出力データ量と、を併せて示したタスクグラフが必要となる。
【００２６】
本実施形態においては、タスクグラフを、タスクの接続関係を表すタスクグラフ接続表と、各タスクの各出力の出力データ量を表すタスク出力データ量表と、に分解し、後者のタスク出力データ量表の作成に必要なタスクの出力データ量を算出する手段として、データ転送量算出部１４を備えている。
【００２７】
ここで、本実施形態の構成装置の各構成要素について詳細に説明する。
【００２８】
タスク入力データ量表格納部１１は、タスクごとに、そのタスクが持つ各入力の入力データ量を列挙したリストを記述したタスク入力データ量表を格納する第１の格納部である。なお、タスク入力データ量表の例は、後に図６Ａに示す。
【００２９】
部品別出力データ量表格納部１２は、処理部品ごとに、その処理部品が持つ各出力の出力データ量を列挙したリストを記述した部品別出力データ量表を格納する第２の格納部である。なお、部品別出力データ量表の例は、後に図６Ｂに示す。
【００３０】
タスクグラフ接続表格納部１３は、タスクごとに、そのタスクを実行する処理部品と、そのタスクの出力データが入力される次タスクの入力を列挙したリストと、を記述したタスクグラフ接続表を格納する第３の格納部である。なお、タスクグラフ接続表の例は、後に図６Ｃに示す。
【００３１】
データ転送量算出部１４は、タスク入力データ量表、部品別出力データ量表、およびタスクグラフ接続表に基づいて、タスクごとに、そのタスクが持つ各出力の出力データ量を算出する。なお、データ転送量算出部１４のアルゴリズムの例は、後に図６Ｅに示す。
【００３２】
タスク出力データ量表格納部１５は、タスクごとに、そのタスクが持つ各出力の出力データ量であってデータ転送量算出部１４が算出した出力データ量を列挙したリストを記述したタスク出力データ量表を格納する第４の格納部である。なお、タスク出力データ量表の例は、後に図６Ｄに示す。
【００３３】
ＢＭＮｏＣ構成決定部１６は、タスクグラフ接続表およびタスク出力データ量表に基づいて、ＢＭＮｏＣアルゴリズムを用いて、画像処理システムをＢＭＮｏＣ構成にする際の処理部品の配置を決定する。なお、ＢＭＮｏＣアルゴリズムの例は、後に図７に示す。
【００３４】
ＢＭＮｏＣ構成データ格納部１７は、ＢＭＮｏＣ構成決定部１６が処理部品の配置を決定した画像処理システムのＢＭＮｏＣ構成を表すデータを格納する。
【００３５】
図２に、本実施形態の構成装置が構成対象とする既存の画像処理システムの例を示す。
【００３６】
図２に示すように、この画像処理システムは、入力ＩＦ（入力インターフェース）２１と、複数のタスクをそれぞれ実行する処理部品２２と、出力ＩＦ（出力インターフェース）２３と、を有している。
【００３７】
なお、図２において、処理部品２２を表す角丸四角形における括弧（）内の文字は部品種別を表し、その上の文字は処理内容を表している。ただし、図２に示した処理部品２２は一例であり、画像処理システムをどのような処理部品２２で構成するかは本発明の本質的部分ではない。そのため、処理部品２２の処理内容についての詳細な説明は省略する。
【００３８】
入力ＩＦ２１から入力された画像信号は、処理部品２２のそれぞれで処理される。処理部品２２の出力は、その処理部品２２に接続された次の処理部品２２に渡される。処理部品２２のそれぞれで処理された画像信号は、出力ＩＦ２３から出力される。
【００３９】
いったん、こうして構成した画像処理システムを再構成するには、その画像処理システムを構成する処理部品２２の結線を外し、処理部品２２を接続し直すことになる。
【００４０】
そこで、本実施形態においては、ＮｏＣの改良技術の１つであるＢＭＮｏＣ構成を採用し、画像処理システムをＢＭＮｏＣ構成にしている。以下、その理由を述べる。
【００４１】
図３に、画像処理システムをＮｏＣ構成にした例を示す。
【００４２】
図３に示すように、画像処理システムをＮｏＣ構成にする場合、処理部品２２のそれぞれにルータ２４を付加する。
【００４３】
入力ＩＦ２１から入力された画像信号は、まず、ルータ２４に入る。ルータ２４はいくつかの出力をもち、与えられた入力を、どのように識別してどの出力から送り出すか、予め設定しておくことができる。例えば、画像信号が入力として与えられた場合、処理を行う処理部品２２に送り込むのか、それとも、次のルータ２４に渡すか、などである。
【００４４】
また、画像信号に予め所定の識別子を付与し、識別子の値に応じて、その画像信号をどちらかに送るようにルータ２４の設定を変えることもできる。
【００４５】
画像処理システムをＮｏＣ構成にする場合、画像処理システムの再構成の際に、処理部品２２の組み合わせや順序を変更する際に結線を外す必要はなく、ルータ２４に与える設定を変更するだけでよい。
【００４６】
しかしながら、画像処理システムをＮｏＣ構成にする場合、ルータ２４を付加するために所要面積が増大するという問題があった。
【００４７】
以上の理由で、本実施形態においては、背景技術で説明したように、ＮｏＣ構成よりも所要面積を小さくすることができるＢＭＮｏＣ構成を採用している。
【００４８】
画像処理システムをＢＭＮｏＣ構成にするためには、タスクの接続関係を表す構成線図と、各タスクの各出力の出力データ量と、を併せて示したタスクグラフが必要となる。
【００４９】
図４に、画像処理システムをＢＭＮｏＣ構成にする際に必要となるタスクグラフの例を示す。
【００５０】
図４に示すように、タスクグラフにおいては、タスク３０を丸囲みで表す。タスクグラフ上のタスク３０には一意な番号を与える。これをタスクＩＤ（Identification）とする。タスク３０を表す丸囲みにおける上部の文字はそのタスク３０を実行する処理部品の部品種別を表し、下部の文字はそのタスク３０のタスクＩＤを表す。タスクグラフ上のタスク３０は、画像処理システムの構成線図における処理部品に相当する。タスクＡの出力がタスクＢの入力となるとき、タスクＡからタスクＢに向かう矢印の線で両者をつなぐ。この線は、画像処理システムの構成線図における処理部品間の結線に相当する。全てのタスク３０についてこれを行う。タスク３０間の線の近くに示した数値は、そのタスク３０間で転送されるデータ量を表すものである。本実施形態においては、データ量の単位は任意としている。そのため、データ量は、特に実数である必要はなく、非負整数としている。
【００５１】
ＢＭＮｏＣ構成アルゴリズムでは、このタスクグラフを基にして、画像処理システムをＢＭＮｏＣ構成にすることができる。
【００５２】
図５に、画像処理システムをＢＭＮｏＣ構成にした例を示す。
【００５３】
なお、図５において、ＭＲはルータ、ＥＳはスイッチ、ＮＩはネットワークインタフェース、ＩＰは処理部品、Ｂｕｓはバス、ＣＮはノードを表す。
【００５４】
図５は、図４に示した画像処理システムを、バス上に５つの処理部品、スイッチ配下に３つのバス、ルータ配下に２つのスイッチという条件のＢＭＮｏＣ構成に配置した例である。
【００５５】
ただし、図５に示すように画像処理システムをＢＭＮｏＣ構成にするには、図４に示すようなタスクグラフが必要であり、このタスクグラフを得るためには、各タスクの出力データ量を求める必要がある。
【００５６】
しかしながら、タスクの出力データ量は、一般には、実物のプロセッサや、プロセッサを模擬する専用のシミュレータにより計測するため、手間と時間を費やすものであった。
【００５７】
これに対して、本実施形態においては、データ転送量算出部１４が、タスクの出力データ量を、そのタスクを実行する処理部品に固有の出力データ量を用いて算出する。
【００５８】
ここで、タスクの出力データ量の算出方法について詳細に説明する。
【００５９】
データ転送量算出部１４は、タスク入力データ量表、部品別出力データ量表、およびタスクグラフ接続表に基づいて、タスクごとに、そのタスクが持つ各出力の出力データ量を算出し、各出力の出力データ量を列挙したリストをタスク出力データ量表に記述する。
【００６０】
そのため、タスクの出力データ量を算出する前の初期状態においては、タスク入力データ量表、部品別出力データ量表、およびタスクグラフ接続表の各欄に予め記述をしておく必要がある。なお、この記述は、データ転送量算出部１４が行っても良いし、その他の手段が行っても良い。
【００６１】
ただし、部品別出力データ量表およびタスクグラフ接続表については、数値を全て定めて完成させておく必要があるが、タスク入力データ量表については、数値が定まっていないものは、特別な値としてｎｉｌを記述しておき、未完成のままとしておく。
【００６２】
図６Ａに、タスク入力データ量表の例を示す。
【００６３】
図６Ａに示すように、タスク入力データ量表は、タスクのタスクＩＤに対して、そのタスクが持つ各入力の入力データ量のリストを記述した表である。
【００６４】
タスクは、それぞれ固有の数の入力を持つので、予め入力を線形リストの順に整列しておき、それぞれの入力の入力データ量を、各線形リストの要素として記述する。これを、入力データ量リストと呼ぶ。
【００６５】
タスクの入力のうち、いくつかの入力は、画像処理システムの外部入力に直接接続されている。そのため、これらの入力については、入力データ量リストの要素として、非負整数値を記述する。
【００６６】
タスク間で転送されるデータ量を示す数値については、ＢＭＮｏＣ構成アルゴリズム上は相対値として取り扱われ、その単位は任意としてよい。そのため、入力データ量は、特に実数である必要はなく、ここでは非負整数としている。
【００６７】
例えば、タスクＩＤが１のタスクは２つの入力を持ち、それら入力のそれぞれの入力データ量は、３３と１７である。
【００６８】
なお、入力データ量の単位は、上述のように任意であり、例えば、時間あたりのビット数、画像処理システムの動作の１周期あたりのパケット数などとすることが考えられる。
【００６９】
一方、タスクの入力のうち、いくつかの入力については、画像処理システムの外部入力に直接接続はされていないために、即座には入力データ量が定まらない。
【００７０】
そのため、初期状態では、これらの入力については、入力データ量リストの要素として、特別な値としてｎｉｌを記述したものを用意すればよい。
【００７１】
後述するように、このｎｉｌは、やがて実数に置き換えられていく。
【００７２】
図６Ｂに、部品別出力データ量表の例を示す。
【００７３】
図６Ｂに示すように、部品別出力データ量表は、処理部品の部品種別に対して、その処理部品が持つ各出力の出力データ量のリストを記述した表である。
【００７４】
処理部品は、それぞれ固有の数の出力を持つので、予め出力を線形リストの順に整列しておき、それぞれの出力の出力データ量を、各線形リストの要素として記述する。これを、出力データ量リストと呼ぶ。
【００７５】
タスクグラフ上の２箇所以上のタスクにおいて、同じ処理部品が使われることもあるため、タスクＩＤに対してではなく、部品種別ごとに出力データ量リストを管理できる。
【００７６】
出力データ量リストの要素は、その処理部品に固有の出力データ量である。
【００７７】
処理部品において、出力データ量は、入力データ量に依存する場合があるため、入力データ量を変数とした関数で表現する。
【００７８】
処理部品は、それぞれ固有の数の入力を持つので、予め入力を線形リストの順に整列しておき、それぞれのデータ量をｘ１，ｘ２，ｘ３，…という変数としておく。これらの変数に対して、出力データ量を関数表現する。
【００７９】
例えば、部品種別がＰＲＧの処理部品は、２つの出力を持ちが、そのうちの１つの出力は、入力データ量ｘ１によってｘ１＊５０で表現される、つまり入力データの５０倍の量のデータを出力する。
【００８０】
出力データ量は、処理部品の固有の情報であるので、画像処理システムをどのように構成するかにかかわらず、定めることが可能である。
【００８１】
図６Ｃに、タスクグラフ接続表の例を示す。
【００８２】
図６Ｃに示すように、タスクグラフ接続表は、タスクのタスクＩＤに対して、そのタスクを実行する処理部品の部品種別と、そのタスクの出力データが入力される次タスクの入力のリストと、を記述した表である。
【００８３】
例えば、タスクＩＤ３のタスクは、部品種別がＰＲＧである処理部品で実行される。また、タスクＩＤ３のタスクの出力は２つあり、そのうちの１つの出力は、タスクＩＤ７のタスクの固有番号が１である入力へのデータとなる。次タスクリストは、あるタスクＩＤのタスクについて、こうした要素を全て含むよう、列挙したリストである。
【００８４】
画像処理システムをタスクグラフの構成線図として表すことができれば、タスクグラフ接続表の要素を全て定めることが可能である。
【００８５】
図６Ｄに、タスク出力データ量表の例を示す。
【００８６】
図６Ｄに示すように、タスク出力データ量表は、タスクのタスクＩＤに対して、そのタスクの各出力の出力データ量を記述した表である。
【００８７】
タスクは、それぞれ固有の数の出力を持つので、予め出力を線形リストの順に整列しておき、それぞれの出力の出力データ量を、各線形リストの要素として記述する。これを、出力データ量リストと呼ぶ。
【００８８】
例えば、タスクＩＤが４のタスクは、２つの出力を持ち、それら出力のそれぞれの出力データ量は、１００と２５０である。
【００８９】
データ転送量算出部１４は、このタスク出力データ量表を完成させることを目的とするものであり、そのための入力は、タスク入力データ量表（初期状態のもの）、部品別出力データ表、およびタスクグラフ接続表の３つである。
【００９０】
図６Ｅに、タスク出力データ量表を作成するためのアルゴリズムを説明するフローチャートを示す。
【００９１】
図６Ｅは、図６Ａ、図６Ｂ、および図６Ｃにそれぞれ示す、タスク入力データ量表（初期状態のもの）、部品別出力データ表、タスクグラフ接続表を予め備えておき、それらの表を基に、図６Ｄに示すタスク出力データ量表を作成する例である。
【００９２】
図６Ｅに示すように、まず、データ転送量算出部１４は、リストＬを用意する。そして、タス入力データ量表の中で、入力データ量が全て定まったタスクＩＤを全て抽出し、抽出したタスクＩＤをリストＬの初期値として設定する（ステップＡ１）。リストＬは、タス入力データ量表の中で、入力データ量が全て定まったタスクＩＤを要素とする表である。
【００９３】
次に、データ転送量算出部１４は、タスク出力データ量表の初期化を行う（ステップＡ２）。この初期化の状態は、タスクグラフ接続表に存在するタスクＩＤをタスクＩＤの欄の値とし、それぞれの出力データ量リストを空欄とした状態である。
【００９４】
次に、データ転送量算出部１４は、リストＬからタスクＩＤを１つ取り出す（ステップＡ３）。以下、このタスクＩＤを持つタスクを対象タスクと称す。
【００９５】
次に、データ転送量算出部１４は、ステップＡ３で取り出したタスクＩＤを用いて、タスクグラフ接続表を辞書引きし、対象タスクを実行する処理部品の部品種別と対象タスクの次タスクリストとを取り出す（ステップＡ４）。
【００９６】
次に、データ転送量算出部１４は、ステップＡ４で取り出した部品種別を用いて、部品別出力データ量表を辞書引きし、対象タスクを実行する処理部品の部品種別の出力データ量リストを取り出す（ステップＡ５）。
【００９７】
次に、データ転送量算出部１４は、ステップＡ３で取り出したタスクＩＤを用いて、タスク入力データ量表を辞書引きし、対象タスクの入力データ量リストを取り出す（ステップＡ６）。
【００９８】
次に、データ転送量算出部１４は、ステップＡ５で取り出した部品種別の出力データ量リストの要素である各関数（部品種別の各出力の出力データ量を求める関数）に、ステップＡ６で取り出した入力データ量リストの各入力の入力データ量を作用させることで、対象タスクの各出力の出力データ量を算出し、算出した各出力の出力データ量を列挙した出力データ量リストをタスク出力データ量表に記述する（ステップＡ７）。
【００９９】
次に、データ転送量算出部１４は、ステップＡ４で取り出した次タスクリストから、１つの要素（次タスクの入力）を取り出す。ここで、タスク入力データ量表において、次タスクの入力の入力データ量が空欄（ｎｉｌ）であれば、ここに、対象タスクの各出力のうち次タスクの入力に対応する出力の出力データ量であってステップＡ７で算出した出力データ量を記述する（ステップＡ８）。これを、次タスクリストの全ての要素について行う。
【０１００】
以上が終わったところで、データ転送量算出部１４は、リストＬを確認し、Ｌに未処理のタスクＩＤが存在しないか否かを判断する（ステップＡ９）。
【０１０１】
ステップＡ９において、リストＬに未処理のタスクＩＤが存在する場合は、データ転送量算出部１４は、ステップＡ３の処理に戻り、Ｌから未処理のタスクＩＤを１つ取り出して以降の処理を繰り返す。
【０１０２】
一方、ステップＡ９において、リストＬに未処理のタスクＩＤが存在しない場合は、データ転送量算出部１４は、タスク出力データ量表の出力データ量リストの欄に空欄が存在しないか否かを判断する（ステップＡ１０）。
【０１０３】
ステップＡ１０において、タスク出力データ量表の出力データ量リストの欄にまだ空欄が存在する場合には、複数のタスクの全てについて出力データ量リストが得られていないことになる。そのため、データ転送量算出部１４は、タスク入力データ量表から、新たに入力データ量が全て定まったタスクＩＤを抽出してリストＬに設定する（ステップＡ１１）。そして、データ転送量算出部１４は、ステップＡ３の処理に戻り、ＬからタスクＩＤを１つ取り出して以降の処理を繰り返す。
【０１０４】
一方、ステップＡ１０において、タスク出力データ量表の出力データ量リストの欄に空欄が存在しなかった場合は、複数のタスクの全てについて出力データ量リストが得られたことになる。そのため、データ転送量算出部１４は、処理を終了する。
【０１０５】
以上のようにして、タスク出力データ量表が定まる。
【０１０６】
タスクグラフ接続表と、タスク出力データ量表と、によりタスクグラフを構成することができる。そのため、その後、ＢＭＮｏＣ構成決定部１６は、ＢＭＮｏＣアルゴリズムを用いて、画像処理システムをＢＭＮｏＣ構成にする際の処理部品の配置を決定する。
【０１０７】
図７に、画像処理システムをＢＭＮｏＣ構成にする際の処理部品の配置を決定するためのＢＭＮｏＣ構成アルゴリズムの例を説明するフローチャートを示す。
【０１０８】
図７に示すように、まず、ＢＭＮｏＣ構成決定部１６は、全ての処理部品を、バスに搭載可能な個数以下に区分する分け方を１以上生成する（ステップＢ１）。あらゆる組み合わせの分け方を予め生成しておいてもよいし、逐次的に生成していってもよい。バスは複数あり、例えば、全てのバスは５個ずつとか、あるいは、５個搭載できるバスと７個搭載できるバスとが半数ずつある、など、バスには処理部品を搭載可能な個数の制約を与えておく。
【０１０９】
次に、ＢＭＮｏＣ構成決定部１６は、ステップＢ１で生成した分け方の中から１つを取り出す（ステップＢ２）。
【０１１０】
次に、ＢＭＮｏＣ構成決定部１６は、ステップＢ２で取り出した分け方で全ての処理部品をバスに搭載した場合において、全てのバスについて、そのバスに搭載した処理部品が実行するタスクの出力データ量の総和を算出し、これをそのバスのデータ転送能力と比較する（ステップＢ３）。ここで、出力データ量の総和を算出する際に、バスに搭載された処理部品のそれぞれが実行するタスクの出力データ量、すなわち、タスク出力データ量表が必要となる。
【０１１１】
次に、ＢＭＮｏＣ構成決定部１６は、出力データ量の総和がデータ転送能力を超えるバスがあるか否かを判断する（ステップＢ４）。
【０１１２】
ステップＢ４において、出力データ量の総和がデータ転送能力を超えるバスがあれば、ＢＭＮｏＣ構成決定部１６は、ステップＢ２の処理に戻り、別の分け方を１つ取り出して以降の処理を繰り返す。
【０１１３】
一方、ステップＢ４において、出力データ量の総和がデータ転送能力を超えるバスがなく、全てのバスについて、出力データ量の総和がデータ転送能力以内であれば、ＢＭＮｏＣ構成決定部１６は、バス同士を接続しスイッチおよびルータを経由する全ての転送経路（すなわち、バス間の転送経路）について、その転送経路を転送される転送データ量を算出し、これをその転送経路のデータ転送能力と比較する（ステップＢ５）。ここで、転送データ量を算出する際に、バスに搭載された処理部品のそれぞれが実行するタスクの出力データ量、すなわち、タスク出力データ量表が必要となる。
【０１１４】
次に、ＢＭＮｏＣ構成決定部１６は、転送データ量がデータ転送能力を超える転送経路があるか否かを判断する（ステップＢ６）。
【０１１５】
ステップＢ６において、転送データ量がデータ転送能力を超える転送経路があれば、ＢＭＮｏＣ構成決定部１６は、ステップＢ２の処理に戻り、別の分け方を１つ取り出して以降の処理を繰り返す。
【０１１６】
一方、ステップＢ６において、転送データ量がデータ転送能力を超える転送経路がなく、全ての転送経路について、転送データ量がデータ転送能力以内であれば、ＢＭＮｏＣ構成決定部１６は、処理を終了する。そして、ＢＭＮｏＣ構成決定部１６は、処理の終了に至った分け方を選択し、選択した分け方で全ての処理部品をバスに搭載するよう、ＢＭＮｏＣ構成を決定する。ここで決定されたＢＭＮｏＣ構成のデータは、ＢＭＮｏＣ構成決定部１６がＢＭＮｏＣ構成データ格納部１７に格納する。
【０１１７】
上述したように本実施形態においては、処理部品に固有の出力データ量を部品別出力データ表として予め備えておき、この部品別出力データ表を用いてタスクの出力データ量を算出する。
【０１１８】
その結果、実物のプロセッサや、プロセッサを模擬する専用のシミュレータが不要となるという効果を奏する。
【０１１９】
ここで、上記の効果について詳述する。
【０１２０】
従来、タスクの出力データ量の算出方法としては、対象とするタスクグラフ全体（もしくは、その一部を抜き出したもの）に相当する処理機能を有するプログラム（このプログラムには、メモリへの書き込みアクセスを計測する仕組みが組み込まれる）を特定のプロセッサ上で実行し、処理の途中で計測されるメモリへの書き込みアクセス回数を、タスクの出力データ量へ換算するという方法が使われていた。また、実物のプロセッサを使用することが難しい場合には、専用に開発されたシミュレータ（Ｓｙｎｏｐｓｙｓ社のＣｏＭＥＴなど）を用いてシミュレーションにより行っていた。
【０１２１】
これに対して、本実施形態においては、上述したように、予め備えておいた部品別出力データ表を用いてタスクの出力データ量を算出するため、実物のプロセッサや、プロセッサを模擬する専用のシミュレータが不要となるという効果を奏する。
【０１２２】
また、本実施形態は、実物のプロセッサを用いる従来の方法に対して、手間が削減できるという効果を奏する。実物のプロセッサを用いる従来の方法においては、既にハードウエア部品として保有しているタスクを、一旦ソフトウエアで書き表し、タスクの出力データ量とメモリのアクセスとの関係を定義し、さらに、メモリのアクセスを計測できるようなライブラリを、タスクに相当するソフトウエアに組み合わせ、計測のために適切な（非常に大量の）入力データを用意した上で、計測を実施し、かつまた、その計測が有効であるかどうかを、動作結果から評定しなければならないという手間があったが、本実施形態はこの手間が不要となる。
【０１２３】
また、本実施形態は、専用シミュレータを用いる従来の方法に対して、時間が削減できるという効果を奏する。シミュレータでは、メモリのアクセスの回数の測定などが予めライブラリとして用意されており、また、プロセッサの数やプロセッサ間の構成を組み替える手間が減る。しかしながら、実物のプロセッサを用いる方法に比べて１００〜１０００倍の時間を要していたが、本実施形態はこの時間が不要となる。
【０１２４】
また、本実施形態においては、画像処理システムをＢＭＮｏＣ構成にしているため、ＮｏＣ構成よりも所要面積を小さく、かつ、ＮｏＣ構成と同等以上の性能を持つ画像処理システムを得ることができる。
【０１２５】
なお、ＢＭＮｏＣ構成が、ＮｏＣ構成と比較して、性能が同等以上である点については、非特許文献１に記載されている。非特許文献１によれば、代表的な性能指標であるレイテンシは、５０％以上の改善を図ることができると記載されている。
【０１２６】
また、本実施形態においては、画像処理システムを、ＮｏＣの改良技術の１つであるＢＭＮｏＣ構成にしているが、本発明はこれに限定されず、他のＮｏＣ、具体的には、処理部品をバスに搭載し、バス同士をスイッチおよびルータによって接続する構成の他のＮｏＣにも適用可能である。
【符号の説明】
【０１２７】
１１    タスク入力データ量表格納部
１２    部品別出力データ量表格納部
１３    タスクグラフ接続表格納部
１４    データ転送量算出部
１５    タスク出力データ量表格納部
１６    ＢＭＮｏＣ構成決定部
１７    ＢＭＮｏＣ構成データ格納部
２１    入力ＩＦ（入力インターフェース）
２２    処理部品
２３    出力ＩＦ（出力インターフェース）
２４    ルータ
３０    タスク
【図１】
0005697102.tif 000002
【図２】
0005697102.tif 000003
【図３】
0005697102.tif 000004
【図６Ａ】
0005697102.tif 000005
【図６Ｂ】
0005697102.tif 000006
【図６Ｃ】
0005697102.tif 000007
【図６Ｄ】
0005697102.tif 000008
【図６Ｅ】
0005697102.tif 000009
【図７】
0005697102.tif 000010
【図４】
0005697102.tif 000011
【図５】
0005697102.tif 000012