(57)【要約】【課題】複数のデータフローに対し、データストレージリソースを効率的に割り当てる。【解決手段】複数のデータフローに割り当てられるデータストレージリソースについての要件を示す、複数のデータフローに予め付与されている属性を取得する。複数のデータフローにおいて、データストレージリソースに対するアクセス競合が発生する関係を示すデータフロー関係グラフを生成する。属性およびデータフロー関係グラフに基づいて、複数のデータフローのそれぞれに対して、アクセス競合が発生しないようにデータストレージリソースの割り当てを決定する。【選択図】  図8
2014059862.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータフローに割り当てられるデータストレージリソースについての要件を示す、前記複数のデータフローに予め付与されている属性を取得する属性取得手段と、
前記複数のデータフローにおいて、データストレージリソースに対するアクセス競合が発生する関係を示すデータフロー関係グラフを生成するグラフ生成手段と、
前記属性および前記データフロー関係グラフに基づいて、前記複数のデータフローのそれぞれに対して、アクセス競合が発生しないようにデータストレージリソースの割り当てを決定する割当決定手段と、
を有することを特徴とするリソース割り当て装置。
【請求項２】
前記グラフ生成手段は、共通のプロセスに対する入力あるいは出力となるデータフロー同士の関係を前記アクセス競合が発生するデータフローの関係として、前記データフロー関係グラフを生成することを特徴とする請求項1に記載のリソース割り当て装置。
【請求項３】
前記属性は前記データストレージリソースのサイズを示すことを特徴とする請求項1に記載のリソース割り当て装置。
【請求項４】
前記属性は前記データフローによって用いられるデータ型を示すデータ型属性を含むことを特徴とする請求項1に記載のリソース割り当て装置。
【請求項５】
前記属性は前記データストレージリソースへのアクセス方法を示すアクセス属性を含むことを特徴とする請求項1に記載のリソース割り当て装置。
【請求項６】
前記割当決定手段は、
前記データフロー関係グラフにおいてデータストレージリソースが未割当であるデータフローのうち、サイズ属性が最大サイズを示すデータフローを抽出する抽出手段と、
前記抽出されたデータフローを頂点とした頂点彩色問題を解くことで前記抽出されたデータフローを彩色する彩色手段と、
前記彩色された色毎に異なるデータストレージリソースを設定することで、前記抽出されたデータフローに対するデータストレージリソースを設定するリソース設定手段と、を有することを特徴とする請求項1に記載のリソース割り当て装置。
【請求項７】
前記抽出手段は、前記未割当のデータフローがなくなるまでデータフローの抽出を繰り返すことを特徴とする請求項6に記載のリソース割り当て装置。
【請求項８】
前記属性は、当該データフローにおけるデータの形式として、基本型、または該基本型を複数包含する複合型のいずれかを示すデータ型属性を含み、
前記リソース設定手段は、前記複合型のデータ型属性が付与されたデータフローが抽出された場合に、当該データフローに対して設定されたデータストレージリソースを、前記複合型が包含する前記基本型の数に応じた複数のエリアに分割し、該分割されたエリアを前記基本型のデータ型属性が付与された他のデータフローに割り当てることを特徴とする請求項6に記載のリソース割り当て装置。
【請求項９】
前記属性は、当該データフローによるデータストレージリソースへのアクセス方法を示すアクセス属性を含み、
前記リソース設定手段は、前記抽出されたデータフローに対し、前記アクセス属性に応じたデータストレージリソースを優先的に割り当てることを特徴とする請求項3に記載のリソース割り当て装置。
【請求項１０】
データフローに対してデータストレージリソースを割り当てるリソース割り当て装置が行うリソース割り当て方法であって、
複数のデータフローに割り当てられるデータストレージリソースについての要件を示す、前記複数のデータフローに予め付与されている属性を取得する工程と、
前記複数のデータフローにおいて、データストレージリソースに対するアクセス競合が発生する関係を示すデータフロー関係グラフを生成する工程と、
前記属性および前記データフロー関係グラフに基づいて、前記複数のデータフローのそれぞれに対して、アクセス競合が発生しないようにデータストレージリソースの割り当てを決定する工程と、
を含むことを特徴とするリソース割り当て方法。
【請求項１１】
コンピュータ装置で実行されることにより、該コンピュータ装置を請求項1乃至9のいずれか1項に記載のリソース割り当て装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データフローに対するデータストレージリソースの割り当てに関する。
【背景技術】
【０００２】
種々のアルゴリズム(システム)をモデル化(表現)する手法として、データの流れに注目したデータフローという考え方がある。アルゴリズムにおけるデータの流れをデータフローと呼び、データフローからデータを受けて何らかの処理を行った結果をデータフローに出力するものをプロセスと呼ぶ。プロセスは入力側のデータフローからデータが届くと、処理を行い、その結果を出力側のデータフローに出力する。データがデータフローに沿ってプロセスにより変換されながら、処理が進んでいく。こうした仕組みのため、データフローはデータ駆動型のアルゴリズム開発ではしばしば用いられている。
【０００３】
データフローをグラフィカルに記述するデータフロー図(DFD、Data Flow Diagram)という表記法がある。例として、図1(a)に示すようなデータフロー図を考える。同図において、外部エンティティA(1001)はカメラであり、撮影した画像は、データフローab(1101)に沿ってプロセスB(1002)に入力される。プロセスB(1002)〜F(1006)はデータフローに従って次々と処理を行い、最後に処理結果をディスプレイである外部エンティティG(1007)に出力する。ここで外部エンティティ(A(1001)およびG(1007))とは、モデル化されるシステムの外部に存在する、システムへのデータ入力元、あるいはシステムからのデータ出力先である。
【０００４】
DFDで記述されたアルゴリズムをコンピュータソフトウェアとして実現する場合、各プロセスをインスタンス(オブジェクト)として生成し、データフローを表すオブジェクトによって、プロセス同士を関連付ければ良い。
【０００５】
データフローによって流れるデータは、各データフローに関連付けられたメモリやファイルといった、データストレージリソースを介してプロセス間で受け渡される。すなわちプロセスは、入力側データフローに関連付けられたデータストレージリソースから入力データを読み出し、その処理結果を出力側データフローに関連付けられたデータストレージリソースに書き込む。
【０００６】
データフローを用いるデータ処理技術として、Cantata(非特許文献1参照)やDirectShow(非特許文献2参照)等が知られている。
【０００７】
Cantataでは、データストレージリソースとしてファイルを用いており、各データフローに個別のファイルが割り当てられる。
【０００８】
またDirectShowでは、データフローに静的なデータストレージリソースは関連付けられておらず、代わりにアロケータが関連付けられている。プロセスは必要時(データ出力時)にアロケータに対してデータストレージリソースの取得要求を出し、それに値をセットした後、データフローの宛先のプロセスに渡す。処理が終わり、データストレージリソースが不要と判断したプロセスは、アロケータにデータストレージリソースの回収を依頼する。また入出力のアロケータが同一であった場合、プロセスは出力のために新たなデータストレージリソースを取得せずに、入力から得たデータストレージリソースをそのまま用いて後段のプロセスに渡すこともできる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】A Hands-on Guide to VisiQuest, AccuSoft Corporation
【非特許文献２】DirectX 9.0 プログラマーズ リファレンス, Microsoft Corporation
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながらCantataでは、ファイルがデータフローの数だけ存在するため、処理中のプロセスとは関係のないデータストレージリソースも数多く存在し、ディスク等におけるファイルストレージの量が莫大となってしまうという課題があった。そこで、処理の高速化を図るために例えばデータストレージリソースをメモリ上に展開することが考えられるが、この場合、システムが必要とするメモリの量が莫大となってしまう。
【００１１】
またDirectShowでは、データストレージリソースの取得・回収を動的に行うことにより、データストレージリソースの再利用(複数のデータフローで同一のデータストレージリソースを使用)が促進される。そのため、プログラムが必要とするメモリ量は抑えられるものの、アロケータに対するデータストレージリソースの取得・回収要求が煩雑に行われるため、これらの呼び出しコストや要求の処理コストが大きい。一般に、こうした呼び出しや要求の処理はCPUのパイプラインを切ってしまうため、大量のデータを処理するシステムでは大きな速度劣化の要因となってしまうという課題があった。
【００１２】
本発明は上記問題に鑑み、複数のデータフローに対し、データストレージリソースを効率的に割り当てることを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本発明のリソース割り当て装置は以下の手段を備える。
【００１４】
すなわち、複数のデータフローに割り当てられるデータストレージリソースについての要件を示す、前記複数のデータフローに予め付与されている属性を取得する属性取得手段と、前記複数のデータフローにおいて、データストレージリソースに対するアクセス競合が発生する関係を示すデータフロー関係グラフを生成するグラフ生成手段と、前記属性および前記データフロー関係グラフに基づいて、前記複数のデータフローのそれぞれに対して、アクセス競合が発生しないようにデータストレージリソースの割り当てを決定する割当決定手段と、を有することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、複数のデータフローに対し、データストレージリソースを効率的に割り当てることが可能となる。
【図面の簡単な説明】
【００１６】
【図１】一般的なデータフロー図と、その各データフローに対するリソースの割り当て例を示す図、
【図２】第1実施形態におけるデータフロー図に対するリソースの割り当て動作を示す図、
【図３】第1実施形態におけるデータサイズ属性が付されたデータフロー図、
【図４】第1実施形態の初期段階におけるリソースの設定状態を示す図、
【図５】第1実施形態の途中段階におけるリソースの設定状態を示す図、
【図６】第1実施形態の途中段階におけるリソースの設定状態を示す図、
【図７】第1実施形態の最終段階におけるリソースの設定状態を示す図、
【図８】第1実施形態におけるリソースの割り当て結果を示す図、
【図９】本発明を情報処理装置において実現した際の機能構成例を示す図、
【図１０】第2実施形態におけるデータ型属性が付されたデータフロー図、
【図１１】第2実施形態の初期段階におけるリソースの設定状態を示す図、
【図１２】第2実施形態の途中段階におけるリソースの設定状態を示す図、
【図１３】第2実施形態の途中段階におけるリソースの設定状態を示す図、
【図１４】第2実施形態の最終段階におけるリソースの設定状態を示す図、
【図１５】第2実施形態におけるリソースの割り当て結果を示す図、
【図１６】第4実施形態におけるデータ型属性が付されたデータフロー図、
【図１７】第4実施形態の初期段階におけるリソースの設定状態を示す図、
【図１８】第4実施形態の最終段階におけるリソースの設定状態を示す図、
【図１９】第4実施形態におけるリソースの割り当て結果を示す図、である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態について、図面を参照して説明する。なお、以下の実施の形態は特許請求の範囲に関わる本発明を限定するものではなく、また、本実施の形態で説明されている特徴の組み合わせの全てが本発明の解決手段に必須のものとは限らない。
【００１８】
＜第1実施形態＞
まず、図1(a)に示すデータフロー図を考える。同図において、外部エンティティA(1001)から出力されたデータはデータフローab(1101)によってプロセスB(1002)に届く。プロセスB(1002)は、このデータを元に処理を行い、2種のデータをデータフローbc(1102)とデータフローbe(1104)に出力する。システムは、データフロー図で表された通りに処理を実行する。以下ではこれを「データフロー図を実行する」と表現する。
【００１９】
以下、図1(a)に示すデータフロー図を実行する場合のデータストレージリソースの割り当てについて、従来例と本実施形態とを対比させて説明する。なお、以下ではデータストレージリソースを単にリソースと称する。
【００２０】
●データフロー図の実行(従来)
従来技術によって図1(a)に示すデータフロー図を実行した場合、そのリソース割り当ては図1(b)のようになる。図1(b)の場合すなわち、データフロー図の実行に先立ち、データフローにリソース(1201〜1207)を割り当てておく。リソースの実体はメモリ上に確保されたメモリブロックや、ディスク上に作成されたファイルといったものであり、ここに各プロセスがデータを読み書きすることにより、プロセス間でのデータの受け渡しを行う。なお、各データフローにはひとつのリソースが関連付けられるが、個々のリソースは複数のデータフローに関連付けられていても良い。ひとつのリソースをより多くのデータフローに関連付けることにより、システムが必要とするメモリの量やディスク等のファイルストレージの量が抑えられる。なお、以下ではリソースの実体をメモリとして説明を行うが、本発明はリソースの実体を規定するものではない。
【００２１】
プロセスB(1002)はリソースab(1201)からデータを読み取り、リソースbc(1202)とリソースbe(1204)にデータを書き込む。ここで、もしもリソースab(1201)とリソースbc(1202)の実体が同一であった場合、読み書きのアクセスが競合してしまうため、正しい処理結果が保証されない。他のリソースの組み合わせについても同様である。したがって、プロセスB(1002)による処理にかかるこれら3つのデータフロー(ab(1201),bc(1202),be(1204))には、それぞれ独立したリソースを割り当てなければならない。他のプロセスに関しても同様である。
【００２２】
ここで図1(c)に、データフローに割り当てるリソースに対するアクセス競合の関係を表したグラフを示す。同図において、頂点がデータフローを表し、頂点間を結ぶエッジがアクセス競合の関係を示す。エッジの両端のデータフローはアクセス競合を起こすため、それぞれに独立したリソースを割り当てる必要がある。アクセス競合を起こさずに割り当て可能なリソースは、図1(c)においてエッジの両端の頂点を互いに異なる色で彩色した場合における"色"に相当する。すなわち、最も少ない色数で頂点を彩色することで、最も少ない数でのリソースの割り当てが行える。この問題は頂点彩色問題(NP困難)として知られているため、具体的な彩色手順についての説明は省略する。なお、図1(c)では各頂点の"色"を塗りつぶし模様として示してある。これによれば、図1(a)に示すデータフロー図を実行するには3つのリソースを確保し、各データフローに割り当てれば良い。このように割り当てた結果を図1(d)に示す。図1(d)によればすなわち、データフローab,dfに第1のリソース、データフローbc,efに第2のリソース、データフローbe,cd,fgに第3のリソースが、それぞれを割り当てられている。
【００２３】
以上が従来技術を用いたリソース割り当て方法である。対して本実施形態におけるリソース割り当て方法ではさらに、データフローに属性を付与し、該属性に基づいてリソースの割り当てを行うことを特徴とする。
【００２４】
●データフロー図の実行(本実施形態)
本実施形態ではすなわち、必要とするデータストレージリソースのサイズを示すサイズ属性が予め付与されたデータフローに対して、アクセス競合が発生しないようにデータストレージリソースを割り当てる。詳細には、複数のデータフローからサイズ属性を取得(属性取得処理)し、複数のデータフローにおいて、データストレージリソースに対するアクセス競合が発生する関係を示すデータフロー関係グラフを生成する(グラフ生成処理)。そして、得られたサイズ属性およびデータフロー関係グラフに基づいて、複数のデータフローのそれぞれに対するデータストレージリソースの割り当てを決定する(割当決定処理)。
【００２５】
以下、本実施形態におけるデータリソースの割り当て方法について、図2を用いて説明する。図2(a)は、データフロー図へ属性を付与する手順を示している。本実施形態では、データフロー図の実行に先立ち、属性付与ステップS01にて属性をデータフローに付与する。属性の付与は例えば、データフロー図の作成を支援するGUI等を通して、各データフローに対して行われる。ここで図3に、上記図1(a)に示すデータフロー図に対し、属性としてデータサイズを付与した例を示す。同図において、データフローab(1101),ef(1106),fg(1107)には、大きなサイズ(Siz1)のデータが流れるとする。同様に、データフローbc(1102),cd(1103),be(1104)には中程度のサイズ(Siz2)のデータが流れ、データフローdf(1105)には小さいサイズ(Siz3)のデータが流れるとする。このとき、それぞれのデータフローには、データサイズとしてSiz1,Siz2,Siz3のいずれかの値が属性として付与されている。  
【００２６】
本実施形態におけるデータリソース割り当て方法では、属性値が付与されたデータフロー図(図3)に基づいて、各データフローにリソースを静的に割り当てる。この手順を図2(b)に示し、説明する。
【００２７】
まず、属性読出しステップS11で、各データフローに付与された属性(データサイズ)を読み出す。この読み出し結果はシステムが処理しやすいようにシステム上に保持される。例えば図4(a)に示すように、属性の読み出し結果が表形式のデータフロー属性表として不図示のメモリ上に作成される。なお、データフロー属性表は、表中の「リソース」欄によって各データフローに対するリソース設定結果を示すが、実際の割り当ては後に行うため初期状態では該欄は空である。
【００２８】
同時に、データフロー関係読出ステップS12により、アクセス競合が起こるため同時にアクセスすべきでないデータフロー間の関係を抽出する。これは共通する1プロセスへの入力あるいは出力となるデータフロー同士の関係を、アクセス競合が発生するデータフローの関係として抽出する。この抽出結果はシステムが処理しやすいようにシステム上に保持される。例えば図4(b)に示すように、アクセス競合が発生するデータフロー関係の抽出結果が、各データフローを頂点とした頂点彩色問題形式のデータフロー関係グラフとして、不図示のメモリ上に作成される。
【００２９】
次に割当リソース決定ステップS13により、S11,S12で作成されたデータフロー属性表とデータフロー関係グラフから、データフローに割り当てるリソースを決定する。ここで図2(c)に、割当リソース決定ステップS13の詳細を示し、説明する。
【００３０】
まず未割当データフローマークステップS131で、データフロー関係グラフにおいて割り当て対象となるデータフロー(頂点)をマークする。マークするデータフローは、リソースが未割当のデータフローのうち、データサイズ属性が最大サイズを示すものをデータフロー属性表を参照して選択する。初期状態ではマークされている頂点はないので、データサイズ属性が最も大きいデータフロー(この場合はSiz1)をマークする。図5(a)に、この初期状態におけるマーク結果(マークされた頂点を太い輪郭で表現)を示す。同図によれば、データフローab,ef,fgがマークされていることが分かる。
【００３１】
次にリソース決定ステップS132で、データフロー関係グラフ中の未彩色かつマークされた頂点の彩色を、頂点彩色問題を解くことによって行う。この彩色結果(頂点色)を図5(b)に示す。なお、同図は上記図5(a)においてマークされた頂点およびそれらを両端とするエッジのみからなる部分グラフとして示している。S132ではこの彩色の際に、新たに使われた頂点色の色毎に対応するリソースの情報を、リソース表に追加する。このリソース表の例を図5(c)に示す。図5(c)によれば、この時点で新たにマークされた、データフローab,efに対する頂点色(図中網点で示す)と、データフローfgに対する頂点色(図中斜線で示す)についてのリソースの情報が、リソース表に追加(作成)されている。ここでリソース表に追加されたリソース(Res1,Res2)の大きさ(リソースサイズ)はSiz1である。S132では、このようにデータフローab,ef,fgに対するリソースの割り当てが決定されると、該割り当てに応じて、図4(a)に初期状態を示したデータフロー属性表を図5(d)に示すように更新する。
【００３２】
次にS133で、未割当データフローがあるか否かのチェックを行う。図5(d)に示すデータフロー属性表によれば、「リソース」に空欄があることから、未割当のデータフローがあると判定され、未割当データフローマークステップS131に戻って処理を継続する。
【００３３】
するとS131では、未割当のデータフローのうち、データサイズ属性が最も大きいデータフロー(この場合はSiz2)をマークする。その結果を図6(a)に示す。同図によれば、データフローbe,bc,cdがマークされていることが分かる。
【００３４】
次にS132で、マークされた頂点を対象として、未彩色の頂点について頂点彩色問題を解くことで彩色する。この際、既に彩色されている頂点の色を変えることはしない。この彩色に伴う処理結果として、図6(b)は彩色結果を示し、図6(c)は更新されたリソース表、図6(d)は更新されたデータフロー属性表を示す。ここで、図6(c)のリソース表に新たに追加されたリソース(Res3)の大きさ(リソースサイズ)はSiz2である。
【００３５】
次にS133で未割当データフローがあるか否かをチェックし、図6(d)に示すデータフロー属性表において「リソース」に空欄があることから、未割当データフローがあると判定され、S131に戻って処理を継続する。
【００３６】
するとS131では、未割当のデータフローのうち、データサイズ属性が最も大きいデータフロー(データサイズはSiz3)をマークする。その結果を図7(a)に示す。同図によれば、データフローdfがマークされていることが分かる。
【００３７】
次にS132で、マークされた頂点を対象として、未彩色の頂点について頂点彩色問題を解くことで彩色する。この際、既に彩色されている頂点の色を変えることはしない。この彩色に伴う処理結果として、図7(b)は彩色結果を示し、図7(c)は更新されたリソース表、図7(d)は更新されたデータフロー属性表を示す。ここで、図7(b)の彩色結果によれば、新たにマークされたデータフローdfについては、データフローbcと同じ色となる。したがってデータフローdfはデータフローbcとアクセス競合しないため、同じリソースを割り当てることができる。したがって、図7(c)のリソース表では、リソースサイズをSize3とする新たなリソースは追加されない。そして図7(d)のデータフロー属性表では、データフローdfに対し、そのデータサイズ属性はSiz3であるが、リソースとしてリソースサイズがSiz2であるRes3が割り当てられている。すなわちデータフローdfについては、データフローbcと同じリソースRes3が割り当てられる。
【００３８】
次にS133で未割当データフローがあるか否かをチェックし、図7(d)に示すデータフロー属性表において「リソース」に空欄がないことから、未割当データフローはないと判定される。これにより、割当リソース決定ステップS13の処理を終了する。
【００３９】
図2(b)に戻り、次にリソース割当ステップS14ではまず、リソース表(図7(c))に基づいて3つのリソース(Res1,Res2,Res3)を確保する。そしてさらに、データフロー属性表(図7(d))に基づいて各データフローにリソースを割り当てる。この割り当て結果を図8に示す。同図によれば、21,22に示す大きさがSiz1である2つのリソース(Res1,Res2)と、23に示す大きさがSiz2である1つのリソース(Res3)が、各データフローに割り当てられている。すなわち、データフロー図に対して割り当てられたリソースの大きさの総計は、Siz1×2＋Siz2である。
【００４０】
ここで従来技術による割り当て結果との比較を行う。従来技術による割り当て結果は図1(d)に示す通りであり、3つのリソースが割り当てられている。これらリソースの大きさについては特に制限されておらず、例えば本システムにおいて最も大きなデータの流れとして想定されるSiz1として設定される。そのため、従来技術において割り当てられたリソースの大きさの総計はSiz1×3となる。すなわち、本実施形態の方が、リソースの大きさの総計をより小さなものとして割り当てられることが分かる。リソースの大きさの総計の差は、そのままシステムが必要とするメモリ量や、ディスク等のファイルストレージ量の差として現れる。
【００４１】
●装置構成
ここで図9に、本実施形態のデータフローに対するリソースの割り当て方法を、情報処理装置において実現した際の機能構成例を示す。この機能構成は、情報処理装置において例えばCPUが、ROMまたはRAMに展開された制御プログラムを実行することで、実現される。
【００４２】
図9において、データ保持部41はRAMやハードディスク等によって実現され、各種データを保持する。具体的には、まず、411に示す実行対象となるデータフロー図を保持する。またリソース情報保持部412において、リソース割り当てを行うための各種情報(データフロー関係グラフ4121、データフロー属性表4122、リソース表4123)を保持する。また、リソース保持部413において、データフローに割り当てられるリソース4131〜を保持する。
【００４３】
情報処理装置においてはさらに、属性付与部42、属性読出部43、データフロー関係読出部44、割当リソース決定部45、リソース割当部46、を機能構成として実現する。属性付与部42では上記図2(a)に示した属性付与ステップS01が実行される。同様に属性読出部43では上記図2(b)に示した属性読出ステップS11が実行され、データフロー関係読出部44ではデータフロー関係読出ステップS12が実行される。また割当リソース決定部45では割当リソース決定ステップS13が実行され、リソース割当部46ではリソース割当ステップS14が実行される。
【００４４】
以上説明したように本実施形態によれば、データフローが必要とするリソースの大きさを考慮して、アクセス競合が発生しないように効率的な割り当てを行うため、従来技術と比べて、全体としてのファイルストレージ量を抑えることができる。
【００４５】
なお、本実施形態では新たに割り当てるリソースの大きさを、データフローに付与されたデータサイズとして説明したが、このデータサイズは最小値であり、少なくともこのデータサイズ以上であれば良い。例えば、キャッシュラインサイズ単位で、データフローに付与されたデータサイズよりも大きい側に丸める、等が考えられる。
【００４６】
また本実施形態では、付与されたデータサイズ属性の値が等しいデータフロー(頂点)のみを順にマークしつつ、リソースの決定を行っていく例を示したが、データサイズが所定の範囲内であるものをまとめてマークしても良い。この場合、新たに割り当てるリソースの大きさは、少なくとも、追加するデータフローのデータサイズ属性の中で最も大きな値とすれば良い。
【００４７】
＜第2実施形態＞
以下、本発明に係る第2実施形態について説明する。上述した第1実施形態では、データフローに対してデータサイズ属性を付与する例を示したが、第2実施形態ではさらに、データ型の属性を付与する例を示す。データ型としては大きく基本型と複合型に分けられ、複合型とは基本型または複合型を複数包含し、すなわち複数の基本型または複合型に分割可能な構造のデータ型である。それに対し基本型とは、他のデータ型を包含せず、これ以上分割できないデータ型である。例えば、"RGBカラー画像"というデータ型はRGB各色の"濃淡画像"を包含している考えることができる。したがって、"RGBカラー画像"というデータ型は、"濃淡画像"というデータ型を3つ包含した複合型であると考えられる。なおこの場合、"濃淡画像"はこれ以上分割できない基本型である。このように、"RGBカラー画像"は3つの"濃淡画像"を包含しているため、1つの"RGBカラー画像"に割り当てられたリソースは、3つの"濃淡画像"のリソースとして使用することができる。
【００４８】
以下、データ型属性として"RGBカラー画像"と"濃淡画像"の2種類を持つ場合を例として、第2実施形態におけるリソース割り当て方法の処理手順を説明する。第2実施形態におけるデータリソースの割り当て方法は、上述した第1実施形態とほぼ同様である。すなわち、まず図2(a)に示すように、S01にてデータフロー図へ属性を付与する。ここで、上記図1(a)に示すデータフロー図に対し、データ型属性を付与した例を図10に示す。同図において、データフローab(1101),ef(1106),fg(1107)には、RGBカラー画像のデータが流れるとする。同様に、データフローbc(1102),cd(1103),be(1104)には濃淡画像のデータが流れ、データフローdf(1105)には矩形の対角頂点座標のデータが流れるとする。このとき、それぞれのデータフローには、データ型として"RGBカラー画像","濃淡画像","頂点座標ペア"のいずれかの値が属性として付与されている。また各データフローには第1実施形態と同様に、データサイズ属性も付与されている。
【００４９】
第2実施形態におけるデータリソース割り当て方法では、属性値が付与されたデータフロー図(図10)に基づいて、各データフローにリソースを割り当てる。この手順についても第1実施形態と同様に、図2(b)に示す通りである。
【００５０】
まず、属性読出しステップS11で、各データフローに付与された属性(データサイズ、データ型)を読み出す。この読み出し結果は例えば図11(a)に示すように、表形式のデータフロー属性表として不図示のメモリ上に作成される。
【００５１】
同時に、データフロー関係読出ステップS12により、アクセス競合が発生するデータフローの関係として、第1実施形態と同様に1つのプロセスに入出力しているデータフロー同士を抽出する。この抽出結果は図11(b)に示すように、頂点彩色問題形式のデータフロー関係グラフとして不図示のメモリ上に作成される。
【００５２】
次に割当リソース決定ステップS13により、S11,S12で作成されたデータフロー属性表とデータフロー関係グラフから、データフローに割り当てるリソースを決定する。第2実施形態におけるS13の詳細は第1実施形態と同様に図2(c)に示す通りであるが、リソース決定ステップS132の動作が第1実施形態とは異なる。ここで、第2実施形態における割当リソース決定ステップS13の詳細について、図2(c)を用いて説明する。
【００５３】
まず未割当データフローマークステップS131で、データフロー関係グラフにおいて割り当て対象となるデータフロー(頂点)をマークする。例えば、データフロー属性表を参照して、リソースが未割当でデータサイズ属性が最大(Siz1)のデータフローをマークする。初期状態におけるマーク結果は第1実施形態と同様に、図12(a)に示すようになる。同図によれば、データフローab,ef,fgがマークされていることが分かる。
【００５４】
次にリソース決定ステップS132で、データフロー関係グラフ中の未彩色かつマークされた頂点の彩色を、頂点彩色問題を解くことによって行う。第2実施形態における彩色結果を図12(b)に示す。第2実施形態でもこの彩色の際に、新たに使われた頂点色に対応するリソースに関する情報をリソース表として作成する。ここで作成されたリソース表の例を図12(c)に示す。同図に追加されたリソース(Res1,Res2)の大きさ(リソースサイズ)はSiz1である。
【００５５】
ここで、第2実施形態におけるリソース表について、詳細に説明する。図12(c)に追加されたリソース(Res1,Res2)が対応するデータフローab,ef,fgは、そのデータ型属性が"RGBカラー画像"である。すなわち、このリソース(Res1,Res2)は複合型のデータフローに対応しているため、それぞれを3つの"濃淡画像"に分割して割り当てることが可能である。そこで第2実施形態では図12(c)に示すリソース表において、各リソース(Res1,Res2)を3分割した分割エリアの項目を設け、各分割エリアに枝番を付す。例えば、リソースRes1に対し、その分割エリアであるRes1-1,Res1-2,Res1-3の項目を設ける。このとき、各分割エリアに対しても、"濃淡画像"に対応するリソースサイズ(Siz2=Siz1×1/3)を記入しておく。また頂点色についても、分割エリアごとの枝番を設定する。すなわち各頂点色として"基本色"を設定し、枝番がないリソースに関してはそのまま"基本色"とし、枝番があるリソースに関しては"基本色＋枝番"で表すとする。
【００５６】
このようにS132において、データフローab,ef,fgに対するリソースの割り当てが決定されると、図11(a)に初期状態を示したデータフロー属性表を図12(d)に示すように更新する。
【００５７】
次にS133で、未割当データフローがあるか否かのチェックを行う。図12(d)に示すデータフロー属性表によれば、「リソース」に空欄があることから、未割当のデータフローがあると判定され、未割当データフローマークステップS131に戻って処理を継続する。
【００５８】
するとS131では、未割当のデータフローのうち、データサイズ属性が最も大きいデータフロー(データサイズはSiz2)をマークする。その結果を図13(a)に示す。同図によれば、データフローbe,bc,cdがマークされていることが分かる。
【００５９】
次にS132で、マークされた頂点を対象として、未彩色の頂点について頂点彩色問題を解くことで彩色する。ここで第2実施形態では、エッジ両端の頂点の"色が異なる"ということを、"基本色＋枝番"の組み合わせが異なる、または、一方の頂点に枝番がない場合であれば"基本色"が異なる、ものとして定義すれば良い。なお第1実施形態と同様に、既に彩色されている頂点の色を変えることはしない。図13(b)にこの彩色結果を示すが、頂点の傍らに枝番を付してある。同図によれば、新たにマークされたデータフローbe,bc,cdについては、データフローfgと同じ基本色となる。したがってデータフローbe,bc,cdはいずれもデータフローfgとアクセス競合しないため、これらにはデータフローfgと同じリソースを割り当てることができる。したがって第2実施形態では、データフローbe,bc,cdに対し、データフローfgに対して割り当てたリソースRes2の分割エリアであるRes2-1,Res2-2,Res2-3をそれぞれ割り当てる。
【００６０】
また図13(c)は更新されたリソース表、図13(d)は更新されたデータフロー属性表を示す。ここで、図13(c)のリソース表においては、リソースサイズをSize2とする新たなリソースは追加されておらず、すなわち新たにリソースを確保することなく、彩色が完了している。そして図13(d)のデータフロー属性表では、データフローbe,bc,cdに対し、リソースRes2-1,Res2-2,Res2-3がそれぞれ割り当てられている。なお、データフローbe,bc,cdのそれぞれに対し、リソースRes1-1,Res1-2,Res1-3のいずれかが1対1で対応して割り当てられていれば良い。
【００６１】
次にS133で未割当データフローがあるか否かをチェックし、図13(d)に示すデータフロー属性表において「リソース」に空欄があることから未割当データフローがあると判定され、S131に戻って処理を継続する。
【００６２】
するとS131では、未割当のデータフローのうち、データサイズ属性が最も大きいデータフロー(データサイズはSiz3)をマークする。その結果を図14(a)に示す。同図によれば、データフローdfがマークされていることが分かる。
【００６３】
次にS132で、マークされた頂点を対象として、未彩色の頂点について頂点彩色問題を解くことで彩色する。この際、既に彩色されている頂点の色を変えることはしない。この彩色に伴う処理結果として、図14(b)は彩色結果を示し、図14(c)は更新されたリソース表、図14(d)は更新されたデータフロー属性表を示す。ここで、図14(b)の彩色結果によれば、新たにマークされたデータフローdfについては、新たな頂点色が設定される。したがって、図14(c)のリソース表ではリソースサイズをSize3とする新たなリソース(Res3)が追加され、図14(d)のデータフロー属性表ではデータフローdfにリソースRes3が割り当てられている。
【００６４】
次にS133で未割当データフローがあるか否かをチェックし、図14(d)に示すデータフロー属性表において「リソース」に空欄がないことから、未割当データフローはないと判定される。これにより、割当リソース決定ステップS13の処理を終了する。
【００６５】
図2(b)に戻り、次にリソース割当ステップS14では、まずリソース表(図14(c))に基づいて3つのリソース(Res1,Res2,Res3)を確保する。そしてデータフロー属性表(図14(d))に基づいて、各データフローにリソースを割り当てる。この割り当ての様子を図15に示す。同図によれば、31,32に示す大きさがSiz1である2つのリソース(Res1,Res2)と、33に示す大きさがSiz3である1つのリソース(Res3)がデータフローに割り当てられている。また、32に示すリソース(Res2)はさらに、321,322,323に示すリソース(Res2-1,Res2-2,Res2-3)の3つに分割されている。この分割されたリソース321,322,323はそれぞれ、データフローbe,bc,cdに割り当てられている。すなわち、この場合のリソースの大きさの総計は、Siz1×2＋Siz3であり、従来技術において割り当てられるリソース(Siz1×3)よりも小さくなる。
【００６６】
以上説明したように第2実施形態によれば、データフローにおけるデータの包含関係を考慮してリソースの割り当てを行うことで、リソースの大きさの総計を抑えることができる。
【００６７】
なお、第2実施形態では包含関係を有するデータ型として、"RGBカラー画像"と"濃淡画像"を例として挙げたが、本発明はこれに限るものではない。例えば、幅×高さ×深さがW×H×Dであるボクセル画像のデータフローを、幅×高さがW×Hの画像のD枚分としてとらえても良い。また、C言語での構造体のようにあらゆるデータタイプの組み合わせとしても良く、配列のように同種のデータがいくつも連なったようなものでも良い。
【００６８】
＜第3実施形態＞
以下、本発明に係る第3実施形態について説明する。上述した第1,第2実施形態では、データフローにおけるデータそのものの特徴を示す属性情報(データサイズ、データ型)を考慮してデータストレージを効率的に割り当てる例を示した。第3実施形態ではさらに、データフローにおけるリソースへのアクセス方法を示すアクセス属性を付与する例を示す。例えば、一部のGPU(Graphics Processing Unit)では、通常のCPUアドレススペースとGPU専用アドレススペースの両方のメモリへアクセスすることができる。GPUアドレススペースへのアクセスは、大きな連続データを一度にアクセスする場合には高速となるが、ランダムアクセスでは低速となってしまう。このような場合、データフローに対する"アクセスパターン"属性として、"ランダムアクセス"や"バーストアクセス"という値を設定し、この属性値によってどちらのアドレススペースからリソースを確保するのかを決定することが有効である。
【００６９】
以下、アクセスパターン属性として"ランダムアクセス"と"バーストアクセス"の2種類を持つ場合を例として、第3実施形態におけるリソース割り当て方法の処理手順を説明する。なお、第3実施形態においても第1実施形態と同様に、各データフローにはデータサイズ属性も付与されている。
【００７０】
第3実施形態におけるデータリソースの割り当て方法は、上述した第1実施形態とほぼ同様であるが、図2(b)における割当リソース決定ステップS13の詳細が異なる。すなわち、第3実施形態におけるS13のおおまかな処理の流れは第1実施形態と同様に図2(c)に示される通りであるが、それぞれの詳細が異なる。
【００７１】
第3実施形態では、未割当データフローマークステップS131におけるデータフローのマークを、各々のアドレススペースごとに行い、リソース決定ステップS132において、各々のアドレススペースごとにデータフローに割り当てるリソースを決定する。
【００７２】
未割当データフローマークステップS131では、まず未割当のデータフローのうち、"アクセスパターン"属性が"ランダムアクセス"のものに関して、"データサイズ"属性の値が大きいものから順にマークする。そして"ランダムアクセス"のデータフローが無くなったら、次に"バーストアクセス"のデータフローに関して、同様に"データサイズ"属性の値が大きいものから順にマークする。
【００７３】
そしてリソース決定ステップS132では、"アクセスパターン"属性が"ランダムアクセス"であるデータフローに関しては、CPUアドレススペース内で割り当てるリソースを決定する。一方、"アクセスパターン"属性が"バーストアクセス"であるデータフローに関しては、GPUアドレススペース内で割り当てるリソースを決定する。これにより、CPUアドレススペース内のみ、あるいはGPUアドレススペース内のみから、割り当てるリソースを決定する場合に比べて、システムの実行速度がより速くなるようなリソース割り当てを行うことができる。
【００７４】
また、実行環境として、容量は限られるが非常な高速なメモリを備える場合も考えられる。このような場合にはデータフローに対し、"高速アクセス効果"属性として、高速アクセスによる効果の度合いを示す値を設定することが有効である。この場合、図2(c)の未割当データフローマークステップS131において、"高速アクセス効果"属性の値の大きいものから順にマークを行う。例えば"高速アクセス効果"属性の値として0,1,2の3種類があった場合、まず属性値が2であるデータフローの集合に関して、"データサイズ"属性の値が大きいものから順にマークする。そして、属性値が2であるデータフローが無くなったら、次に属性値が1であるデータフローに関して同様にマークし、最後に属性値が0であるデータフローに関してマークを行う。
【００７５】
次にリソース決定ステップS132では、各データフローに対するリソースを、まず高速メモリから割り当てることを試みる。そして、高速メモリの容量不足等により割り当てが不可能な場合に、通常のメモリからの割り当てを行う。これにより、高速メモリの容量の範囲内で、システムの実行速度がより速くなるようなリソース割り当てを行うことができる。
【００７６】
以上説明したように第3実施形態によれば、リソースへのアクセス方法を表す属性を用いることで、システムの実行速度がより速くなるようなリソース割り当てを行うことができる。
【００７７】
なお、第3実施形態では実行速度の向上を実現する例を示したが、電力消費量の減少等を目的として、リソースへのアクセス方法の属性を設定することも可能である。
【００７８】
また、リソースへのアクセス方法としては上記例に限定されない。システムが特定のデータアクセス方法に適したリソースを有する場合、そのリソースを使用することによる効果(実行速度向上、電力消費量減少等)が顕著なものから優先的に割り当てを行うような指標を、属性として用いれば良い。例えば、システムがテクスチャメモリを備える場合には、ある画素の周辺画素を煩雑にアクセスしたり画素値を補間したりするような処理に用いられるデータフローを判別するような指標を属性として設定する。すなわち、該属性によって判別される上記データフローに対して優先的に、テクスチャメモリ内に確保したリソースを割り当てれば良い。また、Read-Modify-Writeアクセスを高速に行えるような機能メモリを備える場合、ヒストグラムの更新といった処理に用いられるデータフローを判別するような指標を属性として設定する。そして、該属性によって判別されるデータフローに対して優先的に、機能メモリ内に確保したリソースを割り当てれば良い。
【００７９】
＜第4及び第5実施形態＞
以下、本発明に係る第4及び第5実施形態について説明する。上述した第1、第2、及び第3実施形態では、データフローに対して付与する属性にデータサイズ属性が含まれていた。第4及び第5実施形態では、データフローに対してデータサイズ属性を含まない属性を付与する。
【００８０】
まず、第4実施形態について説明する。第2実施形態では、データフローに対してデータサイズ属性とデータ型属性とを付与したが、第4実施形態ではデータフローに対してデータ型属性のみを付与する。基本的な処理の流れは第2実施形態と同様であり、以下では第2実施形態との違いについて主に説明する。
【００８１】
図16は、属性付与ステップS01にてデータフロー図に付与された属性を示す。図16は、第2実施形態を示す図10に対応する。図10と図16との違いは、データサイズ属性がないこと、すなわちデータ型属性のみがデータフローに付与されていることである。
【００８２】
属性読出ステップS11では、図17(a)に示すデータフロー属性表を、データフロー関係読出ステップS12では、図17(b)に示すデータフロー関係グラフを、それぞれ作成する。これらの図17(a)及び図17(b)は、第2実施形態を示す図11(a)および図11(b)に対応する。
【００８３】
図17(a)のデータフロー属性表においては、図11(a)に示されているデータサイズ属性の代わりに、データ型がいくつの基本データ型を含むかを表す"基本型数"属性を用いる。"基本型数"属性は、図16に示すデータフロー図に明示的には付与されていないが、データ型ごとに予め定められている。"ＲＧＢカラー画像"データ型、"濃淡画像"データ型、及び"頂点座標ペア"データ型の、"基本型数"属性は、それぞれ３、１、及び１である。図17(b)のデータフロー関係グラフは、図11(b)と同様である。
【００８４】
以降の処理は第2実施形態の処理の流れとほぼ同様であるが、未割当データフローマークステップS131とリソース決定ステップS132との詳細が異なる。未割当データフローマークステップS131では、リソースが未割当のデータフローのうち、"基本型数"属性が最大のものがマークされる。リソース決定ステップS132では、データフローに割り当てられるリソースの情報をリソース表に追加する際に、リソースサイズとして、値SizBUに"基本型数"を乗じて得られる値が記録される。このSizBUは、任意の基本型のデータを保持可能なリソースのサイズ（基本型リソースサイズ）を示す。
【００８５】
図17(a)のデータフロー属性表と、図17(b)のデータフロー関係グラフとを参照しながら上述のように処理を行うことにより、割当リソース決定ステップS13の結果として、図18(a)のリソース表及び図18(b)のデータフロー属性表が得られる。図18(a)及び図18(b)は、図14(c)及び図14(d)に対応する。
【００８６】
最後に、リソース割当ステップS14で、図18(a)のリソース表に基づいて、3つのリソース(Res1,Res2,Res3)が確保される。そして、図18(b)のデータフロー属性表に基づいて、各データフローにリソースが割り当てられる。図19は、各データフローへのリソースの割り当てを示す。図19には、各データフローに割り当てられたリソースのリソース名とサイズとが示されている。図19は、第2実施形態を示す図15に対応する。
【００８７】
図19に示されるように、大きさがSizBU×3である2つのリソースRes1(51)及びRes2(52)と、大きさがSizBUである1つのリソースRes3(53)とが、データフローに割り当てられる。また、リソースRes2(52)はさらに、3つのリソースRes2-1(521)、Res2-2(522)及びRes2-3(523)に分割されている。これらの分割リソース521,522,523は、それぞれ、データフローbe,bc,cdに割り当てられている。図19に示されるように、割り当てられるリソースサイズの総計はSizBU×7であり、従来技術を用いた場合に割り当てられるリソースサイズ(SizBU×9)よりも小さい。
【００８８】
次に、第5実施形態について説明する。また、第3実施形態では、データフローに対してデータサイズ属性とアクセス属性とを付与したが、第5実施形態においては、データフローに対してアクセス属性のみを付与する。基本的な処理の流れは第3実施形態と同様であり、以下では第3実施形態との違いについて主に説明する。具体的には、第5実施形態は、未割当データフローマークステップS131とリソース決定ステップS132の詳細が、第3実施形態とは異なる。
【００８９】
まず、アクセス属性として"アクセスパターン"属性を用いる場合について説明する。以下では、"アクセスパターン"属性は、"ランダムアクセス"と"バーストアクセス"のいずれかであるものとする。本実施形態において、1回目の未割当データフローマークステップS131では、"アクセスパターン"属性が"ランダムアクセス"であるデータフローがマークされる。また、2回目の未割当データフローマークステップS131では、"アクセスパターン"属性が"ランダムアクセス"であるデータフローがマークされる。この処理は、第3実施形態において"データサイズ"属性が全て同じ値である場合と同様の処理である。本実施形態において、リソース決定ステップS132でリソース表を作成する際には、任意のデータ型のデータを保持可能なリソースサイズが、各データフローについて記録される。もっとも、別の実施形態において、マークされたデータフローによって流れるデータのそれぞれを保持可能なリソースサイズが、各マークされたデータフローについて記録されてもよい。
【００９０】
アクセス属性として"高速アクセス効果"属性を用いる場合にも、第3実施形態において"データサイズ"属性が全て同じ値である場合と同様の処理が行われる。
【００９１】
以上のようにアクセス属性を用いることにより、ランダムアクセス若しくはバーストアクセスに適したメモリ、又は（小容量の）高速メモリを備えるシステムにおいて、実行速度の向上を図ることができる。
【００９２】
さらに第3実施形態と同様、ある画素の周辺画素を煩雑にアクセスしたり画素値を補間したりするような処理に用いられるデータフローを判別するような指標をアクセス属性として用いることができる。またヒストグラムの更新といった処理に用いられるデータフローを判別するような指標を属性として用いることもできる。こうすることにより、実行速度の向上や電力消費量の減少を図ることができる。
【００９３】
以上のように、割り当てるリソースを決定する際に、データフローによって流れるデータのサイズを考慮することは必須ではない。すなわち、データフローに対してデータサイズ属性を付与することは必須ではない。以上説明したように、データフローに対して付与された、割り当てられるデータストレージリソースについての要件を示す属性を考慮して割り当てるリソースが決定される。この属性には、データサイズ属性、データ型属性、アクセスパターン属性又は高速アクセス効果属性等が含まれる。こうして、例えば必要なリソース量の低減又は処理の高速化のような所望の効果が得られるようにリソースの割り当てを行うことができる。
【００９４】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ(またはCPUやMPU等)がプログラムを読み出して実行する処理である。
【図１】
2014059862.tif 000003
【図２】
2014059862.tif 000004
【図３】
2014059862.tif 000005
【図４】
2014059862.tif 000006
【図５】
2014059862.tif 000007
【図６】
2014059862.tif 000008
【図７】
2014059862.tif 000009
【図８】
2014059862.tif 000010
【図９】
2014059862.tif 000011
【図１０】
2014059862.tif 000012
【図１１】
2014059862.tif 000013
【図１２】
2014059862.tif 000014
【図１３】
2014059862.tif 000015
【図１４】
2014059862.tif 000016
【図１５】
2014059862.tif 000017
【図１６】
2014059862.tif 000018
【図１７】
2014059862.tif 000019
【図１８】
2014059862.tif 000020
【図１９】
2014059862.tif 000021