(57)【要約】      （修正有）【課題】メモリアクセス領域がより多く重複するタスクを連続実行できるようスケジュールする、タスクスケジューリング装置を提供する。【解決手段】タスクを特定するタスク特定情報を含むタスク情報を複数取得して、前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納しておき、２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出することにより、前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加え、前記タスク列を表す情報を出力するスケジューリングを行う。【選択図】図１
2013150094.tif 000002
【特許請求の範囲】
【請求項１】
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、
前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、
前記タスク列を表す情報を出力する出力手段と
を含むタスクスケジューリング装置。
【請求項２】
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報と前記アクセス情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段とを含み、
前記タスク相関算出手段は、更に、１個以上の前記タスクの、前記タスク列で構成されるタスクグループ各々の中の、含まれる前記タスク各々の前記処理量の合計が所定値未満である、１個の前記タスクグループである対象タスクグループが含む、各タスクでアクセスされるメモリ領域と、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、前記タスクグループのいずれにも含まれない前記タスク各々に対して算出し、
前記スケジュール手段は、前記タスクグループのいずれにも含まれない前記タスク各々の中で、前記対象タスクグループとの間の前記グループ相関が最も高い前記タスクを、前記対象タスクグループの前記タスク列に加え、
前記出力手段は、前記タスクグループ毎の前記タスク列を表す情報を出力する
請求項１に記載のタスクスケジューリング装置。
【請求項３】
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段とを含み、
前記タスク相関算出手段は、更に、１個以上の前記タスクの、前記タスク列でそれぞれ構成されるタスクグループが含む各タスクでアクセスされるメモリ領域と、複数の前記タスクグループのいずれにも含まれない前記タスク各々から選択された、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、複数の前記タスクグループ各々に対して算出し、
前記スケジュール手段は、複数の前記タスクグループの、いずれにも含まれない前記タスクから対象タスクを順次選択し、複数の前記タスクグループ各々に対して、選択した前記対象タスクとの間の前記グループ相関と、前記対象タスクの前記処理量とから評価値を算出し、複数の前記タスクグループで前記評価値が最も高い前記タスクグループの前記タスク列に、前記対象タスクを加え、
前記出力手段は、前記タスクグループ毎の前記タスク列を表す情報を出力する
請求項１に記載のタスクスケジューリング装置。
【請求項４】
前記タスク内容情報が、前記タスクの種類を表すタスク種類情報と、時系列の複数のフレームを含む動画像中の、前記タスクの処理の対象の領域である対象ブロックを含む前記フレームである対象フレームの中における、前記対象ブロックの位置を特定する情報と、前記動画像中の、前記タスクの前記対象ブロックを対象とする前記処理で参照される前記フレームである参照フレームを特定する情報とを含む、前記タスク情報を取得する前記タスク取得手段と、
前記タスク種類情報が、前記参照フレーム中の、前記対象ブロックに対応する領域の位置の推定と、前記対象フレームの中における前記対象ブロックの位置に対応する、前記参照フレームの中の位置から、前記参照フレームの中の推定した前記位置までの距離と方向を表す、前記対象ブロックの動きベクトルの算出を含む処理である、動き推定を表す場合、前記対象フレーム中における、前記対象ブロックの周囲の複数のブロックの、既に算出されている前記動きベクトル各々を取得し、取得した前記動きベクトル各々から前記対象ブロックの前記動きベクトルの予測値である予測ベクトルを生成し、生成した前記予測ベクトルと前記タスク情報から、前記タスク特定情報で特定される前記タスクでアクセスされる前記参照フレーム内の領域を推定し、推定した前記領域を格納する前記メモリ領域の配置を表す前記アクセス情報を生成し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、取得した前記動きベクトルと前記タスク情報から、前記アクセス情報を生成するタスクアクセス推定手段と
を含む請求項１乃至３のいずれかに記載のタスクスケジューリング装置。
【請求項５】
前記タスク特定情報と、当該タスク特定情報で特定される前記タスクでアクセスされる前記メモリ領域の大きさを含むアクセス情報との組を記憶する前記アクセス領域記憶手段と、
前記タスク種類情報が動き推定を表す場合、前記対象ブロックの、周囲の複数のブロックの前記動きベクトル各々を取得し、取得した前記動きベクトル各々から、前記予測ベクトルの精度を推定する予測ベクトル精度推定手段と、
推定した前記精度を使用して、前記精度が高いほど、対応する前記対象ブロックを処理の対象とする前記タスクでアクセスされる前記メモリ領域の大きさが小さくなるように、前記メモリ領域の大きさを修正するアクセス領域修正手段と
を含む請求項４に記載のタスクスケジューリング装置。
【請求項６】
推定した前記精度を使用して、前記精度が高いほど前記処理量が少なくなるように、前記処理量を修正するタスク処理量修正手段
を含む請求項４又は５に記載のタスクスケジューリング装置。
【請求項７】
前記タスクアクセス取得手段は、前記タスク種類情報が動き推定を表す場合、前記予測ベクトルを取得し、前記アクセス情報として、前記対象ブロックの位置から前記予測ベクトル分移動した点である予測ベクトル指点の座標を算出し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、前記アクセス情報として、前記対象ブロックの位置から前記動きベクトル分移動した点である動きベクトル指点の座標を算出し、
前記タスク相関算出手段は、２つのタスクの前記タスク特定情報に関連付けられている前記アクセス情報である前記座標間の距離を算出して、２つの前記タスク間の前記タスク相関を求める
請求項１乃至４のいずれかに記載のタスクスケジューリング装置。
【請求項８】
請求項１乃至７のいずれかに記載のタスクスケジューリング装置と、
プロセッサと、
当該プロセッサが実行するタスクのタスク情報を生成し、前記タスクスケジューリング装置に入力するタスク生成手段と、
前記タスクスケジューリング装置から前記タスク列を表す情報を取得し、取得した前記タスク列の順序に従い、前記プロセッサに前記タスクを実行させるタスク実行手段と
を含むタスクスケジュールシステム。
【請求項９】
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得し、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納し、
前記タスク特定情報と前記アクセス情報の組をアクセス領域記憶手段に記憶し、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出し、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加え、
前記タスク列を表す情報を出力する
タスクスケジューリング方法。
【請求項１０】
コンピュータを、
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、
前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、
前記タスク列を表す情報を出力する出力手段と
して動作させるタスクスケジューリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
タスクスケジューリング装置、タスクスケジューリング方法およびタスクスケジューリングプログラムに関し、特にキャッシュメモリを持つ演算器のためのタスクスケジューリング装置、スケジューリング方法およびスケジューリングプログラムに関する。
【背景技術】
【０００２】
近年、動画像の画像サイズの拡大要求に伴って、符号化技術もMPEG-2（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ−２）、MPEG-4、H.264/MPEG-4 AVC（Ａｄｖａｎｃｅｄ  Ｖｉｄｅｏ  Ｃｏｄｉｎｇ。H.264）と圧縮効率を向上するように進歩してきた。これらの符号化方式は、フレーム間の動き補償予測を用いて情報を圧縮することで高い符号化効率を達成している。図２０は、H.264の規格に基づいた動画像符号化装置の例を表す図である。なお、非特許文献１にはこの規格に基づく処理の内容が記載されている。また非特許文献２には、この規格に基づいた動画像符号化装置の実装の詳細が記載されている。
【０００３】
動き補償予測は、符号化対象フレームと参照フレームの間の動き情報を用いて、参照フレームの画像を補正した画像（予測画像）を生成する技術である。動画像符号化装置は、動き補償予測により生成した予測画像と符号化対象画像の差分と、フレーム間の動きを表す動きベクトルのみを符号化することで、動画像情報を圧縮する。動き補償予測では、符号化済みの画像から符号化対象となる画像が予測される。参照画像が１枚であるフレームがP（Predictive）フレーム、２枚であるフレームがB（Bi-predictive）フレームである。動画像符号化装置は、複数のフレームの中から、ブロックごとに参照フレームを選択することが可能である。
【０００４】
参照フレームと符号化対象フレームとの間の動き情報を算出する処理が動き推定である。動画像符号化装置は、参照フレームの中から、符号化対象ブロックと類似度が高いブロックを探索することで、動き推定を行う。参照フレームの最も類似度が高いブロックと符号化対象ブロックの位置差が動きベクトルである。参照フレームの候補である参照可能フレームが複数ある場合は、動画像符号化装置は、各参照可能フレームで動きベクトル探索を行う。画像符号化装置は、探索の結果最も類似度が高いブロックを含む参照可能フレームを選択して参照フレームにし、最も類似度が高いブロックと符号化対象ブロックの位置差を動きベクトルにする。参照画像と動きベクトルを用いて予測画像を生成する処理を動き補償と呼ぶ。
【０００５】
動き補償予測を含むH.264動画像符号化の処理は、16x16画素のマクロブロック単位で行われる。H.264などの近年の符号化方式による動画像符号化の処理は演算量が多いため、並列処理によって高速化が図られることも多い。動き推定や動き補償は、マクロブロックごとにほぼ独立な処理であるため、マクロブロック単位で並列化して、これらの処理を行うことができる。
【０００６】
また、動き補償予測では、近接する動きベクトル同士は相関性が高いことが知られている。そのため、符号化の際、すでに探索された周辺のブロックの動きベクトル情報を予測ベクトルとして用いて、予測ベクトルと符号化対象ブロックの動きベクトルの差分のみを符号化することで、動きベクトルの符号量を削減することができる。H.264における予測ベクトルは、処理の終了した左と上と右上のブロックの動きベクトルのメディアンである。
【０００７】
動き推定では、非特許文献２に記載のように、探索開始点に近い点から動きベクトルを探索し、充分に良い動きベクトルが得られたと判断できたら探索を打ち切る適応的な探索アルゴリズムが用いられることが多い。そのため、動きベクトルの探索の際、探索結果である動きベクトルと探索開始点の距離が短ければ探索量は少なく済み、距離が長ければ探索量は多くなる。予測ベクトルは、動きベクトルに近いと予想されるため、予測ベクトルを探索開始点とすることで探索量を削減できる。予測ベクトルを探索開始点とすると、予測ベクトルの精度すなわち予測ベクトルと動きベクトルの距離により探索量が変化する。
【０００８】
次に、プロセッサアーキテクチャにおける技術背景を述べる。
【０００９】
CPU (Central Processing Unit)やGPU (Graphics Processing Unit)などのプロセッサは、メインメモリに格納されたデータを読み出して演算処理を行う。一般的に、演算処理に対してメインメモリアクセスは低速であるため、多くのプロセッサにはメインメモリへのアクセス負荷を軽減するためのキャッシュメモリが備えられている。キャッシュメモリはメインメモリに比べると、容量は少ないが高速にアクセスすることができる。キャッシュメモリには、プロセッサが近い過去にアクセスしたメインメモリの内容が保持される。キャッシュメモリを備えるプロセッサは、メモリアクセスに時間的・空間的な局所性があれば、メインメモリにアクセスせず、キャッシュメモリのみにアクセスすればよくなるので、高速なデータ読み出しが可能になる。
【００１０】
前述の動き推定や動き補償は、演算量に対してメモリアクセスの量が多いため、キャッシュメモリへのアクセスだけで済む割合を示すキャッシュヒット率が、これらの処理の処理時間に大きく影響を与える。そのため、動き推定や動き補償を行うタスクを実行する際、同一データを使用するタスクを連続して実行できるようなタスクスケジューリングが重要である。さらに、一般的なマルチコア/メニコアなどの並列処理環境ではコア毎あるいは複数のコアをまとめたコアグループ毎にキャッシュを持っており、キャッシュを有効利用できるように、同一データを使用するタスクをなるべく同じコアに配置するなどのスケジューリングも必要となる。特に、画像サイズが大きい場合は画像データの全てをキャッシュメモリに保持することができず、一度キャッシュに保存されたデータを多く再利用することが重要である。
【００１１】
また並列処理では、プロセッサコア毎の負荷を均等に分散することで、各プロセッサコアが遊休状態になる時間をできるだけ減少させることが、高速化のためには重要である。さらに、GPUなどのメニコアプロセッサは、コア数がマルチコアCPUなどに比べて多く、並列に実行可能なタスク数が多いので、メニコアプロセッサによる処理では、負荷分散の均等化が処理時間の短縮に与える影響はより大きくなる。
【００１２】
動き補償処理のキャッシュヒット率を向上させるための技術の例が、特許文献１、特許文献２、特許文献３に記載されている。これらの技術は、メモリアクセス領域が近いタスクをまとめ、データがキャッシュに乗っているうちに処理をまとめて実行することでキャッシュヒット率を上げる技術である。
【００１３】
図２１は、エンコード処理におけるフレーム構造の例を表す図である。図２１の例では、Ｐ１、Ｐ２、Ｐ３はＰフレームを、Ｂ１、Ｂ２、Ｂ３、Ｂ４はＢフレームを表す。双予測動き補償を含むエンコード処理では、図２１のようにPフレームの間に２枚のBフレームを挟み、各Bフレームは前後の同じPフレームを参照するフレーム構造がとられることが多い。
【００１４】
以下では、タスクを実行するプロセッサが、例えばタスクａを実行中に、フレームｂの少なくとも一部のデータにアクセスすることを、タスクａがフレームｂを参照すると表記する。また、この場合、フレームｂを、タスクａがアクセスするフレーム又はタスクａでアクセスされるフレームと表記する。さらに、タスクを実行するプロセッサが、例えばタスクａを実行中に、あるメモリ領域にアクセスすることを、タスクａがそのメモリ領域をアクセスすると表記する。また、この場合、このメモリ領域を、タスクａがアクセスするメモリ領域又はタスクａでアクセスされるメモリ領域と表記する。
【００１５】
特許文献１には、連続する２枚のBピクチャの同一位置マクロブロックの処理を続けて行うことにより、キャッシュを有効利用する動画像伸長方法が記載されている。特許文献１に記載の方法は、同一参照フレームの処理を連続して行うことで、キャッシュのヒット率を向上させる。
【００１６】
特許文献２には、複数のフレームを参照可能で参照フレームがブロックごとに異なる場合にもキャッシュがヒットするように、同一フレームを参照するタスクをまとめ、連続して実行する動き補償装置が記載されている。上述のタスクは、いずれかのブロックにおいて１枚のフレームを参照して行う処理を表す。特許文献２に記載の技術は、特許文献１に記載の技術よりも柔軟にタスクの処理順を変更し、同一フレームを参照するタスクをより多く連続して実行することでキャッシュヒット率を上げることができる。
【００１７】
図２２は、タスクが参照するブロックと、特許文献２の動き補償装置によるタスクのプロセッサコアへの割り当ての例を表す図である。図２２において、例えば、タスク１−１は、符号化対象フレーム内のブロックにおける参照フレーム１を参照するタスクを表し、タスク２−１〜タスク２−３は、符号化対象フレーム内のブロックにおける参照フレーム２を参照するタスクを表す。これらのタスクは、必ずしも同一のブロックにおける処理ではない。ＰＥ（Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔ）１〜ＰＥ４は、それぞれプロセッサコアを表す。図２２では、例えば、タスク１−１はＰＥ１で、タスク２−１〜タスク２−３はＰＥ２で行うことを表す。
【００１８】
特許文献２に記載の動き補償装置は、並列処理を行う場合、図２２のように同一フレームを参照する処理を同一プロセッサコアで行うことで、コアごとにキャッシュ内のデータを繰返し使用することができる。
【００１９】
特許文献３には、同一フレームの同一領域を参照するブロックの処理を続けて実行することでキャッシュヒット率を上げる技術による復号装置が記載されている。特許文献２の復号装置は、各タスクのアクセス範囲を算出し、同じアクセス範囲のタスクを連続実行するようタスクスケジュールすることでキャッシュヒット率を上げる。特許文献３に記載の技術は、特許文献２に記載の技術よりもさらにキャッシュヒット率が高くなるように、同じメモリ領域にアクセスする異なるフレームのタスクも連続して実行するように、タスクをスケジューリングすることができる。
【００２０】
図２３は、参照フレーム内のブロックと、そのブロックを参照するタスクが実行される符号化対象フレーム内のブロックの関係の例と、特許文献３の復号装置が決定した、それらのタスクの処理順の例を表す図である。図２３で、例えば、タスク１−１は符号化対象フレーム１のブロック１−１で実行されるタスクを、タスク２−１は符号化対象フレーム２のブロック２−１で実行されるタスクを表す。特許文献３の復号装置が、図２３のタスク１−１〜タスク３−４をスケジューリングした結果が、図２３の処理順である。
【００２１】
図２５は、特許文献３に記載の技術によりタスクをスケジューリングするタスクスケジューリングシステムの構成の例を表す図である。図２５のタスクスケジューリングシステムは、タスクを取得するタスク取得部と、取得されたタスクのアクセス領域を算出するタスクアクセス領域算出部と、タスクのアクセス領域が任意に区切られたメモリ領域のどの部分に含まれるかを判定し、各区分されたメモリ領域毎にタスクをグルーピングするタスクグループ化部と、グループごとにタスクの処理順をソートするスケジュール部から構成される。
【００２２】
図２６は、特許文献３に記載の技術による、図２５のタスクスケジューリングシステムの動作の例を表す図である。また、図３は、タスクＡ、Ｂ、Ｃがアクセスするメモリの範囲の例を表す図である。図３のような範囲のメモリにアクセスするタスクＡ、Ｂ、Ｃをスケジューリングする例について説明する。メモリは図の（１）、（２）で表される領域に区切られており、区切られたメモリ領域の一部は重複している。まず、タスク取得部がタスク、例えばタスクＡを取得する。タスクアクセス領域算出部はタスクＡのアクセス領域を算出する。タスクＡのアクセス領域は（１）のメモリ領域に含まれているため、タスクグループ化部は、タスクＡをグループＧ１に配置する。これを全タスクのグルーピングが完了するまで繰り返す。タスクＢはタスクＡと同様にグループＧ１に配置される。タスクＣは（２）のメモリ領域に含まれているため、グループＧ２に配置される。全タスクのグルーピングが完了すると、スケジュール部は、グループ番号をキーにタスクをソートする。例えば、タスクＡ、Ｂ、Ｃの順にソートされ、ソートされた順番にタスクは処理される。グループ内のタスクの処理順やグループの処理順は実装に依存する。
【００２３】
特許文献４には、プログラムの各ステップ毎に調べた、データ項目に対するアクセス命令の種類及び回数から、プロセス及びデータ項目を分割し、プロセス間のインタフェースを表示するシステム解析装置が記載されている。
【００２４】
特許文献５には、並列処理する複数のタスク各々に、キャッシュメモリを分割した領域を関連付けるキャッシュ制御装置が記載されている。特許文献５に記載の技術では、各タスクは、関連付けられているキャッシュメモリの領域のみを使用する。このことにより、各タスクが使用しているキャッシュメモリの領域のデータは、他のタスクにより上書きされない。
【００２５】
特許文献６には、プロセスがアクセスする対象のファイルにより、関連するプロセスをグループ化し、プロセスのグループ単位で稼働性能を監視する性能監視方法が記載されている。
【先行技術文献】
【特許文献】
【００２６】
【特許文献１】特開２０００−２７８６９３号公報
【特許文献２】特開２０１１−０６１３２０号公報
【特許文献３】ＷＯ２００８／０３８５１３
【特許文献４】特開２００１−０９２６５１号公報
【特許文献５】特開２００４−１７８５７１号公報
【特許文献６】特開２００９−２６５７０７号公報
【非特許文献】
【００２７】
【非特許文献１】ITU-T Recommendation H.264 ''Advanced video coding for generic audiovisual services,'' May 2003.
【非特許文献２】K. P. Lim, G. Sullivan and T. Wiegand, "Text Description of Joint Model Reference Encoding Methods and Decoding Concealment Methods", Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, Busan, Korea, Apr. 2005
【発明の概要】
【発明が解決しようとする課題】
【００２８】
特許文献1に記載の技術には、ブロックごとに参照フレームが異なる場合、キャッシュヒットしにくく、効果が少ないという問題がある。
【００２９】
特許文献２に記載の技術には、画像サイズが大きくなると同一フレーム内であってもキャッシュに載っているとは限らず、キャッシュミスが多発する可能性があるという問題がある。特許文献２に記載の技術には、さらに、各参照フレームあたりのタスク数は一定ではないため、並列処理の場合にプロセッサコアあたりの処理量を均等化するのは困難であるという問題がある。
【００３０】
特許文献３に記載のタスクスケジューリング手法は、決められたメモリ領域内をアクセスするタスクを、連続して実行するようグループ化する。例えば、図３のような範囲にアクセスするタスクをスケジューリングする際、キャッシュのヒット率を向上させるためには、メモリアクセス領域が重複するタスクＡとＣを連続して処理する必要がある。しかし、タスクＡ、Ｂ、Ｃを特許文献３に記載のタスクスケジューリング手法でスケジューリングする場合、まず（１）の領域内をアクセスするタスクとして抽出されたタスクＡ及びＢが連続して処理される。その後、（２）の領域内をアクセスするタスクとして抽出されたタスクＣが処理される。この時、タスクＡ及びＢと、タスクＣの処理は連続して行われるとは限らない。タスクＡとタスクＢのメモリアクセス領域は重複しないため、キャッシュメモリの利用はできない。一方で、タスクＡとタスクＣはメモリアクセス領域の一部が重複しているにもかかわらず連続に処理されないため、キャッシュ内のデータの再利用ができない。
【００３１】
このように、特許文献３の技術は、タスクがアクセスするメモリ領域が同一メモリ領域内か否かだけグループ化する。特許文献３の技術には、メモリアクセス領域が重複するタスクを連続して実行するよう、複数のタスクをスケジューリングすることができないという問題がある。
【００３２】
特許文献４、５、６の技術には、アクセスするメモリ領域が重複するタスクを、連続して実行するよう、複数のタスクをスケジューリングすることができないという問題がある。
【００３３】
本発明の目的は、メモリアクセス領域がより多く重複するタスクを連続実行できるようスケジュールする、タスクスケジューリング装置を提供することにある。
【課題を解決するための手段】
【００３４】
本発明のタスクスケジューリング装置は、処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、前記タスク列を表す情報を出力する出力手段とを含む。
【００３５】
本発明のタスクスケジューリング方法は、処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得し、前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納し、前記タスク特定情報と前記アクセス情報の組をアクセス領域記憶手段に記憶し、２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出し、前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加え、前記タスク列を表す情報を出力する。
【００３６】
本発明のタスクスケジューリングプログラムは、コンピュータを、処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、前記タスク列を表す情報を出力する出力手段として動作させる。
【発明の効果】
【００３７】
本発明には、アクセスするメモリ領域が重複するタスクを含む複数のタスクを実行する場合に、キャッシュのヒット率が向上し、タスクの実行速度が高速化するという効果がある。
【図面の簡単な説明】
【００３８】
【図１】第１、第２の実施形態のタスクスケジューリング装置１の構成を表すブロック図である。
【図２】第１の実施形態のタスクスケジューリング装置１の動作を表すフローチャートである。
【図３】タスクのアクセス領域の例を表す図である。
【図４】タスクのアクセス領域の二番目の例を表す図である。
【図５】第２の実施形態のタスクスケジューリング装置１の動作の例を表すフローチャートである。
【図６】複数のタスクの予測ベクトルの例を表す図である。
【図７】第３実施形態のタスクスケジューリング装置３の構成を表す図である。
【図８】第３実施形態のタスクスケジューリング装置３の動作を表すフローチャートである。
【図９】並列処理が可能な複数のタスクのアクセス領域の例を表す図である。
【図１０】図９の例のタスクがアクセスするアクセス領域を表として表した図である。
【図１１】図９の例のタスクの、タスク間の相関を表す図である。
【図１２】タスクスケジューリング装置４が、図９のタスクをグルーピングした結果を表す図である。
【図１３】第４実施形態のタスクスケジューリング装置４の構成を表す図である。
【図１４】第４実施形態のタスクスケジューリング装置４の動作の例を表すフローチャートである。
【図１５】複数のプロセッサコアへのタスクの割り当ての例を表す図である。
【図１６】第５の実施形態のタスクスケジューリング装置５の構成を表す図である。
【図１７】第５の実施形態のタスクスケジューリング装置５の動作の例を表すフローチャートである。
【図１８】第６の実施形態のタスクスケジューリング装置６の構成を表す図である。
【図１９】第６の実施形態のタスクスケジューリング装置６の動作の例を表すフローチャートである。
【図２０】H.264の規格に基づいた動画像符号化装置の例を表す図である。
【図２１】エンコード処理におけるフレーム構造の例を表す図である。
【図２２】タスクの参照フレームと、特許文献２の動き補償装置によるタスクのプロセッサコアへの割り当ての例を表す図である。
【図２３】参照フレーム内のブロックと、そのブロックを参照するタスクが実行される符号化対象フレーム内のブロックの関係の例と、特許文献３の復号装置が決定した、それらのタスクの処理順の例を表す図である。
【図２４】特許文献３の技術でタスクのグルーピングを行った結果と、タスクのグループのプロセッサコアへの割り当ての例を表す図である。
【図２５】特許文献３に記載の技術によりタスクをスケジューリングするタスクスケジューリングシステムの構成の例を表す図である。
【図２６】特許文献３に記載の技術によるタスクスケジューリングシステムの動作の例を表す図である。
【図２７】第７の実施形態のタスクスケジューリング装置７の構成を表す図である。
【図２８】第７の実施形態のタスクスケジューリング装置７の動作の例を表すフローチャートである。
【図２９】情報処理装置１０００の構成の一例を表すブロック図である。
【発明を実施するための形態】
【００３９】
次に、本発明の実施形態について図面を参照して詳細に説明する。
【００４０】
（第１の実施の形態）
図２９は、本発明の第１の実施形態のタスクスケジューリング装置１を含む、情報処理装置１０００の構成の一例を表すブロック図である。
【００４１】
図２９を参照すると、情報処理装置１０００は、タスク生成部１００１と、タスクスケジューリング装置１と、タスク実行部１００２と、プロセッサ１００３と、実行結果出力部１００４と、データ入力部１００６と、データ記憶部１００７を含む。情報処理装置１０００は、動きベクトル記憶部１００５を含んでいてもよい。
【００４２】
データ入力部１００６は、入力データを受信し、データ記憶部１００７に格納する。入力データは、例えば、時系列の複数のフレームを含む動画像のデータである。
【００４３】
データ記憶部１００７は、入力された入力データを記憶する。
【００４４】
タスク生成部１００１は、データ記憶部１００７に格納されている入力データから、プロセッサ１００３が実行するためのタスクと、そのタスクを表すタスク情報の組を、複数生成する。タスクは、データ記憶部１００７に格納されている入力データに対する処理のまとまりである。タスクは、例えば、動画像中のあるフレーム（符号化対象フレーム）に含まれるあるブロック（符号化対象ブロック）における動き推定の処理である。タスクは、例えば、動画像中のあるフレームに含まれるあるブロックにおける動き補償の処理であってもよい。
【００４５】
タスクスケジューリング装置１は、複数のタスクのタスク情報を受信し、後述のようにタスクの実行順序（タスク列）を決定し、タスクの実行順序を表す情報を出力する。
【００４６】
タスク実行部１００２は、タスク生成部１００１からタスクを受信し、タスクスケジューリング装置１からタスクの実行順序を表す情報を受信する。タスク実行部１００２は、タスクスケジューリング装置１が決定した実行順序に従って、プロセッサ１００３に各タスクを実行させる。
【００４７】
プロセッサ１００３はタスク実行部１００２からの指示に従い、タスクを実行する。プロセッサ１００３はキャッシュメモリを備えている。プロセッサ１００３は、タスクの実行結果のデータを、順次実行結果出力部１００４に送信する。
【００４８】
実行結果出力部１００４は、プロセッサ１００３がタスクを実行した結果を表す情報をプロセッサ１００３から受信し、出力する。タスクの種類が動き推定である場合、実行結果出力部１００４は、符号化対象ブロックを特定する情報と関連付けて、算出した、その符号化対象ブロックの動きベクトルを、動きベクトル記憶部１００５に格納してもよい。
【００４９】
動きベクトル記憶部１００５は、符号化対象ブロックを特定する情報が関連付けられた、動きベクトルを記憶する。
【００５０】
なお、情報処理装置１０００がタスクスケジューリング装置１を含まなくてもよい。この場合、タスクスケジューリング装置１が、情報処理装置１０００からタスク情報を受信し、情報処理装置１０００に実行順序を表す情報を送信することができるよう、タスクスケジューリング装置１と情報処理装置１０００は、通信可能に接続されていればよい。また、後述の他の実施形態では、情報処理装置１０００の構成は、タスクスケジューリング装置１を、各実施形態のタスクスケジューリング装置で置き換えた構成になる。
【００５１】
以下では、タスクの処理が動き推定の処理である例について具体的に説明する。ただし、タスクの処理は、動き推定以外の、例えば動き補償やその他の、タスクがアクセスするメモリ領域であるアクセス領域の推定が可能な処理や、アクセス領域が既知である処理であってもよい。タスクスケジューリング装置１は、スケジューリング時にタスクのアクセス領域がわかれば、同様にしてタスクスケジューリングを行うことが可能である。タスクのアクセス領域は予測値でも良い。また、本実施形態で説明する例では、１個のタスクは１個のマクロブロックにおける処理である。タスクスケジューリング装置１は、１マクロブロックにおける処理を１タスクとしてスケジューリングを行う。
【００５２】
本発明では、タスク同士のメモリアクセス領域の重複量をタスクの相関とし、相関の高いタスクを連続して実行することでキャッシュの有効利用を図る。
【００５３】
図１は、本発明の第１の実施形態のタスクスケジューリング装置１の構成を表す図である。
【００５４】
図１を参照すると、本実施形態のタスクスケジューリング装置１は、タスク取得部１０１と、タスクアクセス取得部１０２と、アクセス情報記憶部１０５と、タスク相関算出部１０３と、スケジュール部１０４と、出力部１０６とを含む。タスクスケジューリング装置１は、タスクアクセス推定部１０７を含んでいてもよい。
【００５５】
タスク取得部１０１は、スケジューリングの対象となる複数のタスクのタスク情報を入力する。
【００５６】
タスクを表すタスク情報は、そのタスクを特定するタスク特定情報を含んでいればよい。タスク情報は、例えば動き推定や動き補償タスク等の、タスクの種類を表す情報を含んでいてもよい。タスク情報は、そのタスクのアクセス領域を表す情報を含んでいてもよい。アクセス領域を表す情報は、アクセス領域の配置を表す（特定する）アクセス情報であればよい。また、アクセス領域を表す情報は、アクセス領域の配置を算出するための情報であってもよい。
【００５７】
タスク情報がアクセス領域の配置を算出するための情報を含み、タスクスケジューリング装置１がタスクアクセス推定部１０７を含むよう構成されていてもよい。タスクアクセス推定部１０７は、タスク情報が含む、アクセス領域の配置を算出するための情報から、アクセス領域の配置を算出する。タスクアクセス推定部１０７は、タスクを特定する情報と、算出したアクセス領域の配置を表すアクセス情報を、タスクアクセス取得部１０２に送信する。
【００５８】
また、タスク情報が、アクセス領域の配置を特定するアクセス情報を含む場合、タスク取得部１０１が、タスク特定情報とアクセス情報をタスクアクセス取得部１０２に送信すればよい。タスク情報が、そのタスクのアクセス領域を表す情報を含まない場合、タスク取得部１０１はタスク特定情報をタスクアクセス取得部１０２に送信すればよい。
【００５９】
タスクアクセス取得部１０２は、タスク取得部１０１がタスク情報を取得したタスクの、アクセス情報を取得する。タスクアクセス取得部１０２は、タスク特定情報と、アクセスアクセス情報を、対応付けてアクセス領域記憶部１０５に格納する。
【００６０】
アクセス領域記憶部１０５は、タスク特定情報とアクセス情報の組を記憶する。
【００６１】
タスク相関算出部１０３は、アクセス領域記憶部１０５が記憶するアクセス情報から、２つのタスク間の相関（タスク相関）を算出する。タスク相関算出部１０３は、２つのタスク間の相関を、例えば、それらのタスクのアクセス領域の重複部分のサイズにより決定すればよい。
【００６２】
スケジュール部１０４は、タスク間の相関が高い２つのタスクが連続して実行されるよう、タスクの実行順序を決定する。
【００６３】
出力部１０６は、決定した実行順序を表す情報を出力する。
【００６４】
次に、本実施形態の動作について、図面を参照して詳細に説明する。
【００６５】
図２は、本実施形態のタスクスケジューリング装置１の動作を表すフローチャートである。
【００６６】
また、図３は、タスクのアクセス領域の例を表す図である。以下で説明する動作の例はは、タスクスケジューリング装置１が、図３のような範囲にアクセスするタスクＡ、Ｂ、Ｃをスケジューリングする場合の動作の例である。
【００６７】
まず、タスク取得部１０１がタスク、例えばタスクＡのタスク情報を取得する（ステップＳ１０１）。
【００６８】
前述のように、タスク情報が、アクセス領域の配置を表すアクセス情報を含んでいてもよい。この場合、タスク取得部１０１が、タスクアクセス取得部１０２にアクセス情報を送信すればよい。また、タスク情報がアクセス領域の配置を算出するための情報を含んでいてもよい。タスク情報がアクセス領域の配置を算出するための情報を含む場合、ステップＳ１０１の動作の後に、タスクアクセス推定部１０７が、タスク情報が含むアクセス領域の配置を算出するための情報から、アクセス領域の配置を算出する。そして、タスクアクセス推定部１０７が、タスクアクセス取得部１０２にアクセス領域の配置を表すアクセス情報を送信すればよい。
【００６９】
アクセス領域の配置は、例えば、メモリ上に配置され、タスクがアクセスして利用するデータが、例えば画像のように二次元のデータで、アクセス領域が矩形で表されるのであれば、メモリ上におけるアクセス領域の左上と右下の座標であればよい。メモリ上に配置されている、タスクがアクセスして利用するデータが、一次元のデータであれば、アクセス領域の配置は、データの始点のアドレスと終点のアドレスや、データの始点のアドレスとデータ長であればよい。
【００７０】
入力データが、２次元の画像であるフレームが複数、時系列で並ぶ動画像のデータであり、タスクの種類が動き推定であれば、タスクは、符号化対象フレーム上の符号化対象ブロックにおける、参照フレーム上のデータを参照して行う処理である。この場合、アクセス領域の配置を表す情報は、参照フレームを特定する情報と、参照フレームにおけるアクセス領域の例えば左上と右下の座標であればよい。この場合、一つの動画像に含まれる各フレームは同じ大きさであり、各フレーム内における座標は、各フレームを重ねた場合に重なる点が原点であり、座標軸が同一方向である座標系における座標であればよい。例えば、全てのフレームで、左上の角の点が原点であり、右方向がｘ軸方向、下方向がｙ軸方向である座標系で、フレーム内の点の座標が表されていればよい。アクセス領域の配置を表す情報は、参照フレームにおけるアクセス領域が格納されているメモリのアドレスを表す情報であってもよい。
【００７１】
また、タスク情報がアクセス領域の配置を算出するための情報を含む場合、アクセス領域の配置を算出するための情報は、例えば、符号化対象フレーム上の符号化対象ブロックの位置を表す座標と、参照フレームを特定する情報であればよい。アクセス領域の配置を算出するための情報は、予測ベクトルを含んでいてもよい。あるいは、タスクアクセス推定部１０７が、例えば符号化対象ブロックの左と上と右上のブロックにおける、探索の結果得られている動きベクトルのメディアンを予測ベクトルとする方法など、既存の任意の方法で、予測ベクトルを算出してもよい。符号化対象ブロックの位置を表す座標は、符号化対象ブロックの、例えば、符号化対象フレームにおける左上の点の座標であればよい。タスクは、参照フレーム上の、符号化対象ブロックの位置を表す座標と同じ座標から、予測ベクトル分移動した点を中心とした探索範囲を探索する。言い換えると、タスクは、探索範囲に対応するメモリ領域（アクセス領域）にアクセスする。探索範囲の大きさは、あらかじめ決められた大きさであればよい。
【００７２】
この場合、タスクアクセス推定部１０７は、参照フレームを特定する情報と、符号化対象ブロックの位置を表す座標と、予測ベクトルから、アクセス領域の配置を算出すればよい。
【００７３】
次に、タスクアクセス取得部１０２が、タスク情報を取得したタスク（例えば、前述のタスクＡ）のアクセス情報を取得し（ステップＳ１０２）、そのタスクのタスク特定情報と取得したアクセス情報を関連付けて、アクセス領域記憶部１０５に格納する。
【００７４】
タスクアクセス取得部１０２は、タスク取得部１０１やタスクアクセス推定部１０７からアクセス情報を取得する。タスクアクセス取得部１０２は、例えば、タスク生成部１００１が算出し、図示はしていないが、各タスクのアクセス情報を格納するための記憶部に格納しておいたアクセス情報を、その記憶部から読み出してもよい。
【００７５】
タスクスケジューリング装置１は、タスクアクセス取得部１０２が全てのタスクのアクセス情報を取得するまで（ステップＳ１０３、Ｎｏ）、ステップＳ１０１からＳ１０２の動作を繰り返す。
【００７６】
タスクアクセス取得部１０２が全てのタスクのアクセス情報の取得を完了すると（ステップＳ１０３、Ｙｅｓ）、タスク相関算出部１０３がタスク間の相関を算出する（ステップＳ１０４）。
【００７７】
タスク相関算出部１０３は、まず、アクセス領域記憶部１０５にアクセス情報が格納されているタスク２つの組合せ全ての相関を、アクセス領域記憶部１０５から読み出した、アクセス情報から算出すればよい。
【００７８】
アクセス情報が、例えばアクセス領域の左上と右下の点の座標などの、アクセス領域の位置と範囲を表す情報であれば、タスク相関算出部１０３は、二つのタスクのアクセス情報から、それらのアクセス領域の重複量を算出すればよい。重複量は例えば重複部分のメモリのサイズである。タスク相関算出部１０３は、算出した重複量を、対応する二つのタスクの相関にすればよい。アクセス情報は、アクセス領域の位置を表す情報（例えばアクセス領域の中心を表す座標）であってもよい。そして、タスク相関算出部１０３は、後述の第２の実施形態のように、そのアクセス情報から二つのタスクの重複量の程度を表す値を算出し、タスクの相関としてもよい。
【００７９】
タスクの相関がアクセス領域の重複量である場合、アクセス領域が図３の領域であるタスクの例では、タスクＡとタスクＢ、タスクＢとタスクＣの相関は０である。また、タスクＡとタスクＣの相関は６である。
【００８０】
次に、スケジュール部１０４が、相関が高いタスクの組が連続するようにタスクの実行順序を決定する（ステップＳ１０５）。
【００８１】
まず、スケジュール部１０４は、例えば、相関が最も高いタスクの組を選択し、それらの二つのタスクの実行順序を決める。スケジュール部１０４は、相関が最も高い二つのタスクの実行順序を、どのように決めてもよい。スケジュール部１０４は、実行順序を決めたタスクをスケジュール済みとする。
【００８２】
全てのタスクのスケジューリングが終了していない場合（ステップＳ１０６、Ｎｏ）、スケジュール部１０４は、既にスケジューリング済みとしたタスクとの相関が最も高いタスクを選択する（ステップＳ１０５）。スケジュール部１０４は、相関が高いタスクが連続して実行されるようそのタスクの実行順序を決める。
【００８３】
スケジュール部１０４は、選択しスケジューリング済みとしたタスクが存在する場合、最後に選択しスケジューリング済みとしたタスクとの相関が最も高いタスクを、選択すればよい。スケジュール部１０４は、相関が最も高い二つのタスクの次のタスクを選択する際には、二つのタスクのいずれかと最も相関が高いタスクを選択すればよい。そして、スケジュール部１０４は、既に選択済みの二つのタスクのうち、次に選択したタスクとの相関が高い方のタスクを後に実行するよう実行順序を決めればよい。
【００８４】
図３の例では、タスクＡとタスクＣの相関が最も高く、タスクＡとタスクＢ、タスクＢとタスクＣの間の相関は０である。この場合、スケジュール部１０４が決定する実行順序は、Ａ、Ｃ、Ｂの順またはＣ、Ａ、Ｂの順となる。
【００８５】
図４は、タスクのアクセス領域の第２の例を表す図である。この例の場合、タスクＡ、Ｂ、Ｃのアクセス領域は、図３の例と同じである。図４の例では、さらに、タスクＣとの相関が１であるタスクＤが存在する。タスクＡとタスクＤの間の相関と、タスクＢとタスクＤの間の相関は、それぞれ０である。
【００８６】
この例の場合、タスクＡとタスクＣの間の相関が最も高く、次に、タスクＣとタスクＤの間の相関が高い。従って、スケジュール部１０４は、まずタスクＡとタスクＣを選択し、スケジューリング済みとする。スケジューリング部１０４は、次に、タスクＡとの間の相関又はタスクＣとの間の相関が、まだ選択されていないタスクの中で最も高いタスクＤを選択する。タスクＡとタスクＤの相関よりタスクＣとタスクＤの相関の方が高いので、スケジューリング部１０４は、タスクＡとタスクＣに加えて、タスクＣとタスクＤも連続して実行されるように、タスクＡ、タスクＣ、タスクＤの実行順序を決定する。スケジューリング部１０４は、タスクＡ、タスクＣ、タスクＤの順になるよう、実行順序を決めればよい。次に、スケジューリング部１０４は、タスクＡとの間の相関又はタスクＣとの間の相関がタスクＤより低いタスクＢを選択し、タスクＢが最後に実行されるよう実行順序を決めればよい。
【００８７】
スケジュール部１０４は、最後に選択しスケジューリング済みとしたタスクとの間の相関だけでなく、他のスケジューリング済みのタスクとの間の相関を使用して、タスクの選択を行ってもよい。スケジュール部１０４は、例えば、タスク処理順におけるタスク間の距離（時間）に応じて、新しくスケジュールされたタスクとの相関ほど影響が大きくなる重み係数算出してもよい。そして、スケジュール部１０４は、算出した係数をスケジューリング済みの各タスクとの間の相関に掛けた値の和の大きさによって、タスクを選択してもよい。
【００８８】
また、スケジュール部１０４は、既に実行順序を決めているタスクのうち、実行順序が最初のタスク又は最後のタスクとの間の相関が、最も高いタスクを選択してもよい。そして、スケジュール部１０４は、選択したタスクと、実行順序が最初のタスクとの間の相関が最も高い場合、その実行順序が最初のタスクの前に選択したタスクを実行するように、実行順序を決めてもよい。また、スケジュール部１０４は、選択したタスクと、実行順序が最後のタスクとの間の相関が最も高い場合、その実行順序が最後のタスクの後に選択したタスクを実行するように、実行順序を決めてもよい。
【００８９】
スケジューリング部１０４が全てのタスクを選択し、全てのタスクの実行順序をの決定が完了すると（ステップＳ１０６、Ｙｅｓ）、出力部１０６は、実行順序を表す情報を出力する（ステップＳ１０７）。
【００９０】
以上で説明した本実施形態には、アクセスするメモリ領域が重複するタスクを含む複数のタスクを実行する場合に、キャッシュのヒット率が向上し、タスクの実行速度が高速化するという効果がある。
【００９１】
その理由は、タスク相関算出部１０３が算出した、タスクがアクセスするメモリ領域の重複の大きさを表す、タスク間の相関が高いタスクの組ほど優先的に、連続して実行されるよう、スケジュール部１０４がタスクの実行順序を決めるからである。スケジュール部１０４が決めた実行順序に従ってプロセッサがタスクを実行することで、キャッシュヒット率が向上してキャッシュメモリの有効利用が可能になる。その結果、タスクの処理速度が高速化する。
【００９２】
例えば、特許文献３の技術で、図３の例の複数のタスクをスケジューリングした場合、アクセスするメモリ領域が重複するタスクＡとタスクＣが連続して実行されるよう実行順序を決めることが出来ない。一方、本実施形態のタスクスケジューリング装置で同様に図３の例のタスクのスケジューリングを行った場合、タスクの実行順序は、アクセスするメモリ領域が重複するタスクＡとタスクＣが連続して実行される順番になる。その結果、キャッシュデータの有効利用が可能になり、キャッシュのヒット率が向上する。
【００９３】
（第２の実施の形態）
次に、本発明の第２の実施形態について、図面を参照して詳細に説明する。
【００９４】
以下、タスクの種類は動き推定である場合について説明を行う。タスクの種類が動き推定である場合に、後述するように、本実施形態のタスク相関算出部１０３は、動き推定に用いる情報の一つである、各タスクの予測ベクトル情報を利用してタスク間の相関を算出する。タスクの種類は、動き補償であってもよい。タスクの種類が動き補償処理の場合は、以下の説明における予測ベクトルを動きベクトルと読み替えればよい。
【００９５】
本実施形態のタスクスケジューリング装置１の構成は、図１の第１の実施形態のタスクスケジューリング装置１の構成と同じである。
【００９６】
ただし、第１の実施形態における、アクセス領域の配置を算出するための情報は、符号化対象ブロックの位置を表す座標（例えば符号化対象ブロックの左上角の点の座標）と、タスクの種類が動き推定である場合は予測ベクトルである。アクセス領域の配置を表すアクセス情報は、符号化対象ブロックの位置を表す座標から予測ベクトル分移動した点である、予測ベクトル指点の座標である。タスクの種類が動き補償である場合は、本実施形態の、予測ベクトルの算出に関する説明を除く説明の、予測ベクトルを動きベクトルと読み替えればよい。
【００９７】
以下では、第１の実施形態との相違点を中心に説明を行う。
【００９８】
アクセス領域推定部１０７は、予測ベクトルを取得し、予測ベクトルと、符号化対象ブロックの位置を表す座標から、予測ベクトル指点の座標を算出する。アクセス領域推定部１０７は、予測ベクトル指点の座標を、アクセス情報とする。タスク情報が予測ベクトルを含む場合、アクセス領域推定部１０７は、タスク情報から予測ベクトルを取得する。予測ベクトルが図示しない記憶部に格納されている場合、アクセス領域推定部１０７は、その記憶部から予測ベクトルを取得する。タスクが動き推定である場合、アクセス領域推定部１０７は、予測ベクトルをタスク情報等から取得せずに、算出してもよい。アクセス領域推定部１０７は、符号化対象ブロックの予測ベクトルの算出に必要な、符号化対象ブロックの周辺の既に算出済みである動きベクトルを取得し、予測ベクトルを算出すればよい。既に算出済みである動きベクトルは、例えば、前述の情報処理装置１０００が含む、既に算出済みの動きベクトルを格納するための、動きベクトル記憶部１００５に格納されていればよい。アクセス領域推定部１０７は、動きベクトル記憶部１００５から、必要な動きベクトルを読み出せばよい。
【００９９】
タスクアクセス取得部１０２は、予測ベクトル指点の座標であるアクセス情報を取得する。
【０１００】
アクセス領域記憶部１０５は、タスク特定情報と、予測ベクトル指点の座標であるアクセス情報を、関連付けて記憶する。
【０１０１】
タスク相関算出部１０３は、２つのタスクの予測ベクトル指点間の距離を算出し、それらの２つのタスクの相関を表す値にする。
【０１０２】
２つのタスクのアクセス領域の重複量は大きいほど、それらの２つのタスクの予測ベクトル指点間の距離が近いはずである。従って、本実施形態では、タスク間の相関は高いほど、タスク間の相関を表す値が小さい。このように、タスク間の相関の高さと、タスク間の相関を表す値の大きさとの関係は、必ずしも、タスク間の相関が高いほどその相関を表す値が大きいという関係でなくてもよい。タスク間の相関の高さとタスク間の相関を表す値の大きさとの関係は、相関を表す値の算出法に応じてあらかじめ定まっていればよい。
【０１０３】
本実施形態のスケジュール部１０４は、相関を表す値が小さく、相関が高い２つのタスクが連続して実行されるよう、タスクの実行順序を決定する。
【０１０４】
次に、本実施形態の動作について、図面を参照して詳細に説明する。
【０１０５】
図５は、本実施形態のタスクスケジューリング装置１の動作の例を表すフローチャートである。第１の実施形態の動作を表す図２と比較すると、図５の動作は、図２の動作のステップＳ１０２をステップＳ２０２に、ステップＳ１０４をステップＳ２０４に、ステップＳ１０５をステップＳ２０５に置き換えた動作である。図２と同じ符号が付与されたステップの動作は、第１の実施形態の、その符号が付与されたステップの動作と同じであるので、説明を省略する。
【０１０６】
図６は、複数のタスクの予測ベクトルの例を表す図である。それぞれの矢印の終点が、予測ベクトル指点である。Ａ、Ｂ、Ｃが付された矢印が、それぞれタスクＡ、タスクＢ、タスクＣの予測ベクトルを表す。
【０１０７】
以下の説明では、タスクスケジューリング装置１が、図６に予測ベクトルを示した各タスクの実行順序を決める場合の動作例についても説明を行う。
【０１０８】
ステップＳ１０１の後、アクセス領域推定部１０７がアクセス領域の配置を算出する場合、アクセス領域推定部１０７は、予測ベクトル指点の座標を算出する。
【０１０９】
タスクアクセス取得部１０２は、ステップＳ１０１でタスク情報を取得したタスクの、予測ベクトル指点の座標であるアクセス情報を取得する（ステップＳ２０２）。
【０１１０】
タスクアクセス取得部１０２は、ステップＳ１０１でタスク情報を取得したタスクの、タスク特定情報とアクセス情報（本実施形態では予測ベクトル指点の座標）を関連付けて、アクセス領域記憶部１０５に格納する。
【０１１１】
前タスクの、タスク特定情報とアクセス情報の組の、アクセス領域記憶部１０５への格納が終了すると（ステップＳ１０３、Ｙｅｓ）、タスク相関算出部１０３は、２つのタスクの組の、予測ベクトル指点間距離を算出する（ステップＳ２０４）。タスク相関算出部１０３は、算出した予測ベクトル指点間距離を、対応する２つのタスク間の相関（相関を表す値）とする。前述のように、本実施形態では、タスク間の相関が高いほど、相関を表す値は小さい。
【０１１２】
タスク相関算出部１０３は、まず、タスク取得部１０１がタスク情報を取得したタスクから選択した２つのタスクの組全ての、予測ベクトル指点間距離を算出すればよい。
【０１１３】
図６のタスクの例の場合、タスクＡとタスクＢの予測ベクトル指点間距離は５、タスクＢとタスクＣの予測ベクトル指点間距離は√３４（約５．８）、タスクＡとタスクＣの予測ベクトル指点間距離は√５（約２．２）である。
【０１１４】
次に、スケジュール部１０４が、最も相関が高い２つのタスクが連続して実行されるよう、それらのタスクの実行順序を決める（Ｓ２０５）。前述のように、相関を表す値である予測ベクトル指点間距離が小さいほど、対応する２つのタスク間の相関が高いので、スケジュール部１０４は、最も予測ベクトル指点間距離が小さいタスクの組を選択する。
【０１１５】
図６のタスクの例の場合、タスクＡとタスクＣの予測ベクトル指点間距離が最も小さいので、スケジュール部１０４はタスクＡとタスクＣを選択し、スケジューリング済みとする。
【０１１６】
スケジュール部１０４が全てのタスクを選択してスケジューリング済みとしていない場合（ステップＳ１０６、Ｎｏ）、スケジュール部１０４は、既にスケジューリング済みのタスクとの間の相関が最も高いタスクを選択する（ステップＳ２０５）。スケジュール部１０４は、選択したタスクをスケジューリング済みにする。スケジュール部１０４は、既に選択したタスクの中で最初に実行されるタスクと最初に実行されるタスクのうち、最後に選択したタスクとの相関が高い方を、最後に選択したタスクと連続して実行されるようタスクの実行順序を決める。スケジュール部１０４は、既に選択したタスクの中で最初に実行されるタスクと間の相関が、最後に実行されるタスクと最後に選択したタスクと間の相関より高い場合、最後に選択したタスクの実行順序を最初にする。逆の場合、スケジュール部１０４は、最後に選択したタスクの実行順序を最後にする。
【０１１７】
図６のタスクの例の場合、タスクＡとタスクＢの予測ベクトル指点間距離より、タスクＢとタスクＣの予測ベクトル指点間距離が小さい。従って、スケジュール部１０４は、既に選択したタスクＡとタスクＣの実行順序がタスクＡ、タスクＣの順であるなら、タスクＢの実行順序をタスクＡの前（最初）にし、タスクＡとタスクＢが連続して実行されるようにする。
【０１１８】
ステップＳ２０５におけるスケジュール部１０４の動作は、相関の高さを予測ベクトル指点間距離の小ささで判定する点以外、第１の実施形態のステップＳ１０５における動作と同じである。
【０１１９】
なお、ステップＳ２０５で、スケジュール部１０４は、予測ベクトル指点と既に選択したタスクの予測ベクトル指点の重心との距離が最も小さいタスクを選択してもよい。その場合、まだ全てのタスクを選択していない場合（ステップＳ１０６、Ｎｏ）、タスクスケジューリング装置１はステップＳ２０４の動作に戻ってもよい。
【０１２０】
そして、ステップＳ２０４では、タスク相関算出部１０３は、既に選択したタスクの予測ベクトル指点の重心を算出し、算出した重心と、まだ選択していないタスクの予測ベクトル指点との距離を算出すればよい。
【０１２１】
スケジュール部１０４が全てのタスクの実行順序を決定すると（ステップＳ１０６、Ｙｅｓ）、出力部１０６は、実行順序を表す情報を出力する（ステップＳ１０７）。
【０１２２】
以上で説明した本実施形態には、第１の実施形態の効果に加えて、タスクの実行順序を決定するための演算量を削減することができるという効果がある。
【０１２３】
その理由は、スケジュール部１０４が、予測ベクトル指点間距離により、相関の高さを判定するからである。そのため、アクセス領域の重複量を算出する必要が無い。さらに、相関の算出に、タスクがアクセスするメモリ領域であるアクセス領域の配置を表す情報が必要も無い。アクセス領域の配置を表す情報が必要であれば、タスクスケジューリング装置１がアクセス領域の配置を算出しない場合であっても、例えば情報処理装置１０００のタスク生成部１００１などの他の処理部が、アクセス領域の配置を算出する必要がある。従って、本実施形態のようにタスクスケジューリング装置を構成することにより、タスクの実行順序を決定するための処理の簡単化が可能になり、その演算量が削減される。
【０１２４】
（第３の実施の形態）
次に、本発明の第３の実施形態について、図面を参照して詳細に説明する。
【０１２５】
図７は、本実施形態のタスクスケジューリング装置３の構成を表す図である。
【０１２６】
図７を参照すると、本実施形態のタスクスケジューリング装置３は、図１の第１の実施形態のタスクスケジューリング装置１の構成に加えて、予測ベクトル精度推定部３０３と、アクセス領域修正部３０４を含む。
【０１２７】
動き推定では、予測ベクトルを中心として動きベクトルの探索が行われる。動きベクトルの探索範囲の上限は設定により決められているが、適応的な探索アルゴリズムを用いる場合には実際に探索する範囲は一定ではない。予測ベクトルと動きベクトルが近い、つまり予測ベクトルの精度が高いことがわかっていれば、探索量は少なく探索範囲即ちメモリアクセス範囲も狭くてよい。反対に予測ベクトルの精度が低いことがわかっていれば、メモリアクセス範囲は広い必要がある。そこで、本実施の形態では、予測ベクトルの精度に応じてメモリアクセス範囲サイズを変更する。
【０１２８】
予測ベクトルの精度の推定は、予測ベクトルの算出に用いた周囲の動きベクトルを比較することで実行することが可能である。周囲のブロックの動きベクトルの向き・大きさが似ていれば、符号化対象ブロックの動きベクトルも似ていることが予想される。従ってこの場合、予測ベクトルの精度は高いと推定される。
【０１２９】
予測ベクトル精度推定部３０３は、符号化対象ブロックの周囲のブロックの、既に算出した動きベクトルの情報を取得する。予測ベクトル精度推定部３０３は、取得した動きベクトルの情報から、符号化対象ブロックの予測ベクトルの精度を推定する。
【０１３０】
アクセス領域修正部３０４は、予測ベクトル精度推定部３０３が推定した予測ベクトルの精度に応じて、アクセス領域記憶部１０５に格納されているアクセス領域の配置を修正する。アクセス領域修正部３０４は、アクセス領域が予測ベクトル指点を中心とした所定の大きさの領域である場合、領域の大きさを予測ベクトルの精度に応じて修正すればよい。
【０１３１】
本実施形態の他の構成要素は、同一の符号を付した第１の実施形態の構成要素と同じなので、説明を省略する。
【０１３２】
なお、アクセス領域修正部３０４が、アクセス領域記億部１０５に格納されているアクセス領域の配置を修正するのではなく、アクセス領域推定部１０７が、予測ベクトルの精度に応じてアクセス領域の大きさを決定し、アクセス領域の配置を推定してもよい。
【０１３３】
次に、本発明のタスクスケジューリング装置３の動作について、図面を参照して詳細に説明する。
【０１３４】
図８は本実施形態のタスクスケジューリング装置３の動作を表すフローチャートである。図８を図１の第１の実施形態のタスクスケジューリング装置１の動作を表すフローチャートと比較すると、ステップＳ１０２とステップＳ１０３の間にステップＳ３０４〜ステップＳ３０６が存在する点が異なる。
【０１３５】
ステップＳ１０１、Ｓ１０２の動作は、第１の実施形態の同じ符号のステップの動作と同じなので説明を省略する。
【０１３６】
予測ベクトル精度測定部３０３は、タスク取得部１０１から、ステップＳ１０１でタスク取得部１０１がタスク情報を取得したタスクの、タスク特定情報と符号化対象ブロックの位置を表す情報を受信する。予測ベクトル精度測定部３０３は、その符号化対象ブロックの周囲のブロックの動きベクトルの情報を取得する（ステップＳ３０４）。
【０１３７】
予測ベクトル精度推定部３０３は、前述の動きベクトル記憶部１００５から、動きベクトルの情報を取得すればよい。予測ベクトル精度推定部３０３が情報を取得する動きベクトルは、符号化対象ブロックの予測ベクトルの算出に使われる動きベクトルであればよい。前述のように、例えばＨ．２６４では、符号化対象ブロックの左と上と右上のブロックの動きベクトルを使って、その符号化対象ブロックの動きベクトルが算出される。この場合、予測ベクトル精度推定部３０３は、符号化対象ブロックの左と上と右上のブロックの動きベクトルを取得すればよい。予測ベクトル精度推定部３０３は、予測ベクトルの算出に使われる動きベクトル以外の、周囲のブロックの算出済みの動きベクトルを取得してもよい。
【０１３８】
予測ベクトル精度推定部３０３は、取得した動きベクトルから、符号化対象ブロックの予測ベクトルの精度を推定する（ステップＳ３０５）。
【０１３９】
予測ベクトル精度推定部３０３は、予測ベクトルの精度の推定を、取得した動きベクトルのばらつきの大きさにより行えばよい。例えば、予測ベクトル精度推定部３０３は、取得した動きベクトルのｘ方向・ｙ方向それぞれの分散を算出すればよい。周囲のベクトルのｘ方向・ｙ方向それぞれの分散が小さいほど、予測ベクトルの精度が高いことになる。予測ベクトル精度推定部３０３は、更に、算出したｘ方向・ｙ方向の分散値の例えば対数をとって正規化した値を算出すればよい。予測ベクトル精度推定部３０３は、算出した値をタスクアクセス領域修正のための係数（修正係数）にすればよい。予測ベクトル精度推定部３０３は、タスク特定情報と、ｘ方向・ｙ方向の２つの修正係数を、アクセス領域修正部３０４に送信する。
【０１４０】
修正係数の詳細な算出手順は、例えば次の通りである。予測ベクトル精度推定部３０３は、まず、動きベクトルのｘ方向・ｙ方向それぞれの分散を算出する。次に、予測ベクトル精度推定部３０３は、算出したｘ方向・ｙ方向それぞれの分散の対数を算出する。対数の底は適宜決めておけばよい。また、分散が１未満の値になる可能性があるなら、予測ベクトル精度推定部３０３は、分散の値に１を足してから対数を算出すればよい。予測ベクトル精度推定部３０３は、算出したｘ方向・ｙ方向それぞれの分散の対数が所定値以上であれば修正係数を１に、所定値未満であれば、算出したｘ方向・ｙ方向それぞれの分散の対数を所定値で割った値をｘ方向・ｙ方向それぞれの修正係数にすればよい。
【０１４１】
各タスクの処理において、そのタスクの符号化対象ブロックの予測ベクトルの精度に応じた探索範囲の変更を行う場合、その変更を行うアルゴリズムが既知であるなら、予測ベクトル精度推定部３０３は、そのアルゴリズムにより修正係数を算出すればよい。すなわち、予測ベクトル精度推定部３０３は、探索範囲変更前後の、ｘ方向の探索範囲の比と、ｙ方向の探索範囲の比を算出し、それぞれｘ方向の修正係数と、ｙ方向の修正係数にすればよい。
【０１４２】
アクセス領域修正部３０４は、アクセス領域記憶部１０５に格納されている、受信したタスク特定情報に対応するアクセス情報を修正する（ステップＳ３０６）。
【０１４３】
アクセス情報が表すアクセス領域は、タスクアクセス取得部１０２がアクセス領域記憶部１０５に格納した時点では、アクセス領域は予測ベクトル指点を中心とした、あらかじめ定められた所定の大きさの領域である。アクセス領域修正部３０４は、受信したｘ方向・ｙ方向の修正係数を、それぞれ、ｘ方向・ｙ方向の領域の大きさに掛ければよい。前述のように算出した修正係数をｘ方向・ｙ方向の領域の大きさに掛けた場合、周囲のブロックの動きベクトルの分散が小さければ小さいほど、アクセス領域は狭くなる。なお、修正係数は、周囲のブロックの動きベクトルの分散が小さければ小さいほど、アクセス領域は狭くなる値であれば、前述のように算出した値でなくてもよい。また、予測ベクトル精度修正部３０３は、精度の程度によらず、アクセス領域の大きさがあらかじめ定められた所定の大きさを超えないように、修正係数の大きさに上限を設定しておけばよい。予測ベクトル精度修正部３０３は、例えば上述の例のように、精度の評価値（上述の例では分散あるいは分散の対数）が、所定の範囲を、精度が悪い方に超えた場合、修正係数を１に設定すればよい。
【０１４４】
ステップＳ１０３〜Ｓ１０７の動作は、第１の実施形態の同じ符号のステップの動作と同じなので説明を省略する。
【０１４５】
また、タスクスケジューリング装置３は、アクセス領域の配置を算出するアクセス領域推定部１０７を含み、予測ベクトル精度推定部３０３は、修正係数をアクセス領域推定部１０７に送信する構成であってもよい。アクセス領域推定部１０７は、あらかじめ定められた所定の大きさに受信した修正係数を掛けて、アクセス領域の大きさにしてもよい。この場合、アクセス領域修正部３０４は、アクセス情報の修正を行わない。更に、アクセス領域修正部３０４は存在しなくてよい。
【０１４６】
次に、本実施の形態の効果について説明する。
【０１４７】
本実施形態には、タスクスケジューリング装置３が決定した実行順序でタスクを実行した場合に、第１の実施形態の効果に加えて、タスクを実行する際のキャッシュヒット率が更に向上し、タスクの実行速度が更に向上するという効果がある。
【０１４８】
その理由は、予測ベクトル精度推定部３０３が予測ベクトルの精度を表す値を算出し、アクセス領域修正部３０４が、予測ベクトルの精度が高いほどアクセス領域の大きさが小さくなるよう、アクセス領域の大きさを修正するからである。
【０１４９】
動き推定では、タスクは設定された探索範囲全体に対して必ずアクセスするとは限らない。例えば、タスクが、設定された探索範囲全体に対して、符号化対象ブロックと類似するブロックの探索を完了する前に、類似度が所定の基準以上であるブロックが発見された場合に、そのブロックの位置を動きベクトルの指点として検出し、探索を終了する場合がある。このような場合、タスクが実際にアクセスする範囲は、探索範囲全体のうち、予測ベクトル指点である探索開始点から、検出した動きベクトル指点までの探索経路でアクセスする範囲だけである。従って、予測ベクトルの精度が高く、予測ベクトル指点と動きベクトル指点が近い場合は、タスクがアクセスする範囲は狭くなる。一方、予測ベクトルの精度が低く、予測ベクトル指点と動きベクトル指点が遠い場合は、タスクがアクセスする範囲は広くなる。
【０１５０】
本実施の形態のアクセス領域修正部３０４は、アクセス領域が、あらかじめ設定された探索範囲全体を探索した場合にアクセスする範囲ではなく、予測ベクトルの精度から推定した、タスクが実際にアクセスする範囲になるように、アクセス領域を修正する。これにより、タスク相関算出部１０３が、実際のメモリアクセス範囲に近い範囲をタスク相関の算出に使用できる。従って、アクセス相関算出部１０３が算出する、アクセス領域の重複部分であるタスク相関の精度が向上する。そのため、タスクスケジューリング装置３が決定した実行順序でタスクを実行した場合のキャッシュヒット率が更に向上し、キャッシュのデータの更に効率的な使用が可能になり、タスクの実行速度が更に向上する。
【０１５１】
（第４の実施の形態）
次に、第４の実施形態について図面を参照して詳細に説明する。
【０１５２】
図１３は本実施形態のタスクスケジューリング装置４の構成を表す図である。
【０１５３】
本実施形態のタスクスケジューリング装置４は、マルチコアプロセッサやメニコアプロセッサによりタスクを並列処理する場合のスケジューリングを行う。コアごとにキャッシュを持つ並列処理プロセッサでキャッシュを有効利用するためには、同じメモリ領域を参照するタスクを同じプロセッサコアで連続して実行することが重要である。さらに、効率よく並列処理するためにはプロセッサコアあたりの処理量を均等化する必要がある。
【０１５４】
特許文献２の技術でスケジューリングをした場合、処理量を考慮せずにスケジューリングするため、プロセッサコア毎の処理量が偏ってしまう。さらに特許文献３の技術で、メモリアクセス領域ごとに分割されたグループごとにプロセッサコアに割り当てた場合、グループ毎の処理量は均等にはならない。
【０１５５】
図２４は、特許文献３の技術でタスクのグルーピングを行った結果と、タスクのグループのプロセッサコア（ＰＥ１、ＰＥ２）への割り当ての例を表す図である。
【０１５６】
図２４に示す範囲にアクセスするタスクの例では、（１）の領域にはタスクＡが、（２）の領域にはタスクＢ、Ｃ、Ｄが含まれる。特許文献３の技術でそれぞれのグループを別のプロセッサコアに割り当てた場合、タスク数は１と３のように偏ってしまう。
【０１５７】
本実施形態では、図２９のプロセッサ１００３は複数のプロセッサコアでタスクを実行する。本実施形態のタスクスケジューリング装置４は、プロセッサ１００３が実行する複数のタスクを、各プロセッサコアに割り当てる、複数のタスクグループにグルーピングする。タスクスケジューリング装置４は、プロセッサコア数をタスクグループのグループ数として受信し、以下で説明する動作により、実行の対象となる複数のタスクを、プロセッサコア数のタスクグループに、数が均等になるよう割り当てる。１つのタスク当たりの処理量は均等であれば、各タスクグループに含まれるタスクの処理量の合計はそれぞれ均等である。そして、タスクの実行時には、例えば図２９のタスク実行部１００２が、各グループをプロセッサコアに割り当てる。
【０１５８】
図１３を参照すると、タスクスケジューリング装置４は、タスク取得部１０１と、タスクアクセス取得部１０２と、アクセス領域記憶部１０５と、タスク相関算出部１０３と、スケジュール部１０４と、出力部１０６と、グループアクセス算出部４０６と、グループ記憶部４０７を含む。タスクスケジューリング装置４は、アクセス領域推定部１０７を含んでいてもよい。
【０１５９】
本実施形態では、タスク取得部１０１がタスク情報を取得するタスクは、並列に処理することが可能なタスクである。
【０１６０】
タスク相関算出部１０３は、２つのタスク間の相関を算出するのに加えて、複数のタスクを含むタスクグループと、タスクとの間の相関を算出する。
【０１６１】
スケジュール部１０４は、相関の高いタスクを同一タスクグループに登録する。また、スケジュール部１０４は、タスクグループ内でタスクの実行順序を決定する。
【０１６２】
グループアクセス算出部４０６は、タスクグループがアクセスするメモリ領域を算出する。
【０１６３】
グループ記憶部４０７は、タスクグループを特定する情報と、タスクグループに含まれるタスクを特定する情報を、関連付けて記憶する。
【０１６４】
タスクスケジューリング装置４の他の構成要素は、同一の符号を付した、第１の実施形態のタスクスケジューリング装置１の構成要素と同じであるので、説明を省略する。
【０１６５】
次に、本実施形態のタスクスケジューリング装置４の動作について、図面を参照して詳細に説明する。
【０１６６】
図９は、並列処理が可能な複数のタスク（タスクＡ、タスクＢ、タスクＣ、タスクＤ）がアクセスするメモリの範囲（アクセス領域）の例を表す図である。本実施形態の動作の説明では、タスクスケジューリング装置４が、これらのタスクを２つのプロセッサコアに割り当ててスケジューリングする動作、すなわち、これらのタスクを２つのグループに分けてスケジューリングする動作の例についても説明する。
【０１６７】
図１４は、タスクスケジューリング装置４の動作の例を表すフローチャートである。
【０１６８】
本実施形態の、例えばスケジュール部１０４は、あらかじめタスクグループのグループ数を保持していればよい。あるいは、ステップＳ１０１で、タスク取得部１０１が、タスク情報に加えて、タスクグループのグループ数の情報も取得してもよい。この場合タスク取得部１０１は、取得したタスクグループのグループ数の情報を、スケジュール部１０４に送信すればよい。
【０１６９】
タスクスケジューリング装置４の、ステップＳ１０１〜ステップＳ１０３の動作は、グループ数を取得してスケジュール部１０４に送信する点を除き、第１の実施形態のタスクスケジューリング装置１のステップＳ１０１〜ステップＳ１０３の動作と同じである。従って、ステップＳ１０１〜ステップＳ１０３の動作の説明は省略する。
【０１７０】
スケジュール部１０４は、受信したグループ数と、アクセス情報記憶部１０５にアクセス情報が格納されているタスクの数から、１タスクグループ当たりのタスク数（グループタスク数）を算出する（ステップＳ４０１）。スケジュール部１０４は、アクセス情報記憶部１０５に格納されているタスクの数を、カウントすることで得ればよい。スケジュール部１０４は、タスク取得部１０１から、スケジューリングを行うタスクの数を受信してもよい。
【０１７１】
図９の例では、１グループ当たりのタスクの数は２である。
【０１７２】
次にタスク相関算出部１０３が、図２のステップＳ１０４と同様に、タスク情報を受信したタスクから選択した２つのタスクの組合せ全ての、タスク間の相関を算出する（ステップＳ１０４）。
【０１７３】
図１０は、図９の例のタスクがアクセスするアクセス領域を表として表した図である。
【０１７４】
図１１は、図１０のアクセス領域を表す情報から算出した、タスク間の相関を表す図である。図１１の重複サイズが、タスク間の相関に相当する。
【０１７５】
次に、スケジュール部１０４が、タスクをいずれかのタスクグループに割り当てるグルーピングがなされていないタスクの中で、最も相関が高いタスクのペアを選択し、新規のタスクグループｉに登録（グルーピング）する（ステップＳ４０５）。ｉはタスクグループの番号である。番号ｉの初期値は例えば０であればよい。スケジュール部１０４は、タスクグループｉを特定する情報と、選択したペアを構成するタスク各々を特定する情報を関連付けて、グループ記憶部４０７に格納する。なお、ステップＳ４０５の動作は、スケジュール部１０４が、最も相関が高いタスクのペアのいずれか一方をタスクグループにまず登録し、さらに、そのタスクグループとの相関が最も高いタスクをそのタスクグループに登録する動作と見なすこともできる。
【０１７６】
図９の例で、グルーピングが行われたタスクがなければ、相関が最も高いタスクのペアは、タスクＣとタスクＤである。また、ｉは初期値の０である。スケジュール部１０４は、タスクＣとタスクＤをグループ０に登録する。スケジュール部１０４は、タスクグループ０を特定する情報と、タスクＣを特定する情報及びタスクＤを特定する情報を関連付けて、グループ記憶部４０７に格納する。
【０１７７】
タスクグループｉに登録されているタスク数がグループタスク数より小さい場合（ステップＳ４０８、Ｙｅｓ）、グループアクセス算出部４０６が、タスクを新たに登録したタスクグループ（タスクグループｉ）のアクセス領域を算出する。グループアクセス算出部４０６は、タスクグループｉが含む各タスクがアクセスするメモリ領域の和を、そのタスクグループｉのアクセス領域にすればよい。グループアクセス算出部４０６は、算出したタスクグループｉのアクセス領域を表す情報を、タスク相関算出部１０３に送信する。
【０１７８】
タスク相関算出部１０３は、グルーピングされていない各タスクとタスクグループｉの相関（グループ相関）を算出する。グループ相関はタスクとグループの間の相関である。スケジュール部１０４は、グルーピングされていないタスクの中から、タスクグループｉとの間の相関が最も高いタスクを選択する。スケジュール部１０４は、選択したタスクをタスクグループｉに登録する（ステップＳ４０７）。
【０１７９】
スケジュール部１０４は、タスク間の相関と同様に、タスクグループｉのアクセス領域とタスクのアクセス領域の重複部分のサイズを、タスクグループｉとそのタスクの相関にすればよい。
【０１８０】
スケジュール部１０４は、タスクグループを特定する情報と、そのタスクグループに含まれる各タスクのタスク特定情報各々とを関連付けて、グループ記憶部４０７に格納する。
【０１８１】
タスクグループｉに登録されているタスク数がグループタスク数以上である場合（ステップＳ４０８、Ｎｏ）、グルーピングが終了していないタスクが存在すれば（ステップＳ４０９、Ｎｏ）、ｉをカウントアップしてステップＳ４０５に戻る。この場合、全てのタスクのグルーピングが終了していれば（ステップＳ４０９、Ｙｅｓ）、タスクスケジューリング装置４は各タスクグループ毎の実行順序を出力し（ステップＳ１０７）、動作を終了する。
【０１８２】
なお、タスクグループｉに登録されているタスク数がグループタスク数以上である場合（ステップＳ４０８、Ｎｏ）、スケジュール部１０４は、タスクグループｉに含まれるタスクの中で、図２のステップＳ１０４〜Ｓ１０６と同様に実行順序を決めればよい。
【０１８３】
図９のタスクの例で、タスクＣとタスクＤがタスクグループ０にグルーピングされ、タスクＡとタスクＢがグルーピングされていない場合、タスクグループ０のタスク数はグループタスク数に等しい。さらに、グルーピングされていないタスクＡとタスクＢが存在する。この場合動作はステップＳ４０５に戻り、タスクＡとタスクＢをタスクグループ１に登録する。
【０１８４】
その結果、タスクスケジューリング装置４は、図９のタスクを、図１２の例のようにグルーピングする。図１２は、タスクスケジューリング装置４が図９のタスクをグルーピングした結果を表す図である。
【０１８５】
なお、スケジュール部１０４は、ステップＳ４０５で、タスクのペアを新規タスクグループｉに登録する際、そのペアが連続して実行されるよう実行順序を決めればよい。そして、スケジュール部１０４は、ステップＳ４０７で、新しくタスクグループｉに登録するタスクの実行順序を、図２のステップＳ１０５と同じように決めればよい。さらに、スケジュール部１０４は、タスク特定情報と、決定したタスクの実行順序の順番に並べたタスク特定情報の組（タスク列を表す情報）を、グループ記憶部４０７に格納すればよい。
【０１８６】
また、タスク相関算出部１０３は、タスクとタスクグループの相関を、そのタスクとそのタスクグループ内で実行順序が最初のタスクとの相関と、そのタスクとそのタスクグループ内で実行順序が最後のタスクとの相関のうち、高い方にしてもよい。その場合、ステップＳ４０６の動作は必要なく、グループアクセス算出部４０６は存在しなくてよい。
【０１８７】
また、スケジュール部１０４は、最初にステップＳ４０５を受信したグループ数と同じ回数だけ繰り返してもよい。そして、ステップＳ４０７で、スケジュール部１０４は、グルーピングされてない各タスクと各グループと組合せのうち、相関が最も高いタスクとグループを選択し、選択したタスクを選択したグループにグルーピングする動作を繰り返してもよい。
【０１８８】
また出力部１０６は、ステップＳ１０７では、グループ毎のタスクの実行順序を表す情報を出力する。
【０１８９】
以上のようにグルーピングされた各タスクグループは、例えばプロセッサ１００３が含むプロセッサコアにそれぞれ割り当てられる。各プロセッサコアは、割り当てられたタスクグループに含まれる各タスクを、タスクグループ毎に並列に処理する。
【０１９０】
図１５は、複数のプロセッサコアへのタスクの割り当ての例を表す図である。プロセッサ１００３が２つのプロセッサコア（ＰＥ１、ＰＥ２）を含む場合、タスクグループ数は２である。タスクグループ数が２であれば、タスクスケジューリング装置４は、図９（図１５の左側）のタスクを、図１５の右側のように２つのタスクグループにグルーピングする。そして、例えばタスク実行部１００２が、２つのタスクグループを、プロセッサ１００３の２つのプロセッサコア（ＰＥ１、ＰＥ２）に割り当てる。
【０１９１】
以上で説明した本実施の形態には、第１の実施形態の効果に加えて、複数のプロセッサコアがタスクを実行する場合に、プロセッサコアごとの処理量を均等にすることができるという効果がある。
【０１９２】
その理由は、スケジューリング部１０４が、プロセッサコアの個数に対応するグループ数のタスクグループ各々が含むタスクの個数が均等になるよう、各タスクグループと相関の最も高いタスクを順次そのタスクグループに割り当てるからである。この場合、各タスクの処理量が均等であれば、各タスクグループが含むタスクの処理量の合計は均等である。
【０１９３】
特許文献２や３のようにスケジューリングしグループごとにプロセッサコアにタスクを割り当てると、グループ内のタスク数はグルーピング時に考慮できない。そのため、図２４のタスク例ではプロセッサあたりのタスク数が偏ってしまう。本実施の形態のタスクスケジューリング装置４は、タスクのグルーピング時に各タスクグループが含むタスク数を均等にすることができる。従って、本実施の形態のタスクスケジューリング装置４は、各タスクの処理量が均等である場合に、プロセッサコアごとの処理量を均等化できる。
【０１９４】
（第５の実施の形態）
次に、本発明の第５の実施形態について、図面を参照して詳細に説明する。
【０１９５】
タスクあたりの処理量がタスクごとに異なる場合は、タスクグループあたりのタスク数のみではなく、タスクの処理量を考慮してスケジュールすることで、グループあたり、引いてはプロセッサコアあたりの処理量を均等化することができる。
【０１９６】
例えば、動き推定におけるタスクあたりの処理量は、参照可能フレーム数などから推定することができる。参照可能フレーム数が２枚である場合の処理量は、１枚の場合の倍の処理量であると推定できる。本実施形態は、タスクあたりの処理量が均等ではない場合にもプロセッサコアあたりの負荷の均等化を図る。なお、処理量は、演算量の程度を表す数値である。演算量の単位は任意で構わない。
【０１９７】
図１６は本実施形態のタスクスケジューリング装置５の構成を表す図である。
【０１９８】
図１６を参照すると、本実施形態のタスクスケジューリング装置５は、図１３に示す第４の実施形態のタスクスケジューリング装置４の各構成要素に加えて、タスク処理量推定部５０８と、タスク処理量記憶部５０９を含む。
【０１９９】
タスク処理量推定部５０８は、タスク取得部１０１が取得したタスク情報から、そのタスクの処理量を推定する。例えば、動き推定におけるタスクあたりの処理量は、参照可能フレーム数や、以下で簡単に説明する探索ブロック種数と相関関係にある。すなわち、動き推定のタスクの演算量は、参照可能フレーム数や探索ブロック種数とおおよそ比例関係にある。従って、タスク処理量推定部５０８は、これらの情報から、動き推定におけるタスクあたりの処理量を推定すればよい。
【０２００】
なお、探索ブロック種数は、一つのタスク内で動きベクトルの探索を行うためのブロックサイズの種類である。タスクが、例えばＨ．２６４の規格で動き探索を行うタスクである場合、そのタスクは、マクロブロック（１６×１６画素）単位での動きベクトルの探索に加えて、マクロブロックを分割した更に小さいブロックでの動きベクトルの探索を行う場合がある。この場合、タスクは、複数のサイズのブロックで行った探索の結果から、最も良い動きベクトルを選択する。このような場合、例えば、探索を行うためのブロックが、１６×１６画素のマクロブロックと、８×８画素及び４×４画素の、マクロブロックを分割したブロックである場合、探索ブロック種数は３である。
【０２０１】
タスク処理量推定部５０８は、例えば、動きベクトル探索の際に、符号化対象ブロックと探索フレーム内のブロックとの間で行われる比較の回数の、想定される最大数を処理量にしてもよい。タスク処理量推定部５０８は、動きベクトル探索の際に符号化対象ブロックと探索フレーム内のブロックとの間で行われる比較のアルゴリズムが各タスクで同一であるなら、例えば、タスクの動き推定における探索範囲の総面積の値を処理量にしてもよい。タスク取得部１０１が取得するタスク情報は、タスクの種類に加えて、参照可能フレーム数や、探索ブロック種数や、タスクの処理量を推定するための他の情報を含んでいればよい。
【０２０２】
スケジュール部１０４は、各タスクグループの処理量が、全タスクの処理量の合計とグループ数から算出した、一つのタスクグループ当たりの処理量の目安に近付くように、タスクを各タスクグループに割り当てる。スケジュール部１０４は、さらに、タスクグループ毎にタスクのスケジューリングを行う。
【０２０３】
タスク処理量推定部５０８は、タスク特定情報と、そのタスク特定情報で特定されるタスクの処理量を、関連付けてタスク処理量記憶部５０９に格納する。
【０２０４】
タスク処理量記憶部５０９は、タスク特定情報と処理量を関連付けて記憶する。
【０２０５】
タスクスケジューリング装置５の他の構成要素は、第４の実施形態のタスクスケジューリング装置４の同一の番号の構成要素と同じであるので、説明を省略する。
【０２０６】
図１７は、本実施形態のタスクスケジューリング装置５の動作の例を表すフローチャートである。図１７と図１４を比較すると、タスクスケジューリング装置５は、ステップＳ１０２の後にステップＳ５０１の動作を行う点と、ステップＳ１０４の前にステップＳ５０２の動作を行う点が、第４の実施形態のタスクスケジューリング装置４と異なる。更に、タスクスケジューリング装置５は、ステップＳ４０８の代わりにステップＳ５０８の動作を行う点タスクスケジューリング装置４と異なる。タスクスケジューリング装置５のその他のステップの動作は、第４の実施形態のタスクスケジューリング装置４の同じ番号のステップの動作と同じなので、説明を省略する。
【０２０７】
ステップＳ１０２の後、タスク処理量推定部５０８が、タスク取得部１０１が取得したタスク情報から、対応するタスクの処理量を推定する（ステップＳ５０１）。タスク処理量推定部５０８は、推定した処理量を、対応するタスクのタスク特定情報に関連付けて、タスク処理量記憶部５０９に格納する。
【０２０８】
タスク取得部１０１がタスク情報を取得した全てのタスクのアクセス領域の取得とタスクの処理量の推定が終了すると（ステップＳ１０３、Ｙｅｓ）、タスク処理量推定部５０８は、１タスクグループ当たりの処理量の目安を算出する（ステップＳ５０２）。
【０２０９】
タスク処理量推定部５０８は、タスク情報に加えて、タスクグループのグループ数をタスク取得部１０１から受信すればよい。タスク処理量推定部５０８は、推定した各タスクの処理量の合計を算出し、算出した合計を受信したグループ数で割ることで、１タスクグループ当たりの処理量の目安（処理量目安）を算出すればよい。
【０２１０】
ステップＳ５０９では、スケジュール部１０４は、タスクグループｉに割り当てられているタスクの処理量の合計と、タスク処理量推定部５０８が推定した処理量目安を比較する。タスクグループｉに割り当てられているタスクの処理量の合計が処理量目安未満である場合（ステップＳ５０９、Ｙｅｓ）、スケジュール部１０４はタスクグループｉへのタスクの割り当て（ステップＳ４０６〜ステップＳ４０７）を継続する。タスクグループｉに割り当てられているタスクの処理量の合計が処理量目安以上である場合（ステップＳ５０９、Ｎｏ）、スケジュール部１０４はタスクグループｉへのタスクの割り当てを終了する。
【０２１１】
以上で説明した本実施形態には、第４の実施形態の効果に加えて、タスク毎の処理量が異なる場合でも、プロセッサコアあたりの処理量を均等化することができ、全てのタスクの処理が完了するまでの処理時間を短縮できるという効果がある。
【０２１２】
その理由は、タスク処理量推定部５０８が、タスク毎に処理量を推定するからである。スケジュール部１０４は、推定したタスク毎の処理量を使用して、個々のプロセッサコアに実行させるタスクの集合であるタスクグループ毎の処理量の合計が均等になるよう、各タスクグループにタスクを割り当てる。各プロセッサコアが実行するタスクの処理量が均等であれば、各プロセッサコアが実行するタスクの処理量が均等でない場合より、全てのタスクの処理が完了するまでの処理時間は短くなる。
【０２１３】
（第６の実施の形態）
次に、本発明の第６の実施形態について図面を参照して詳細に説明する。
【０２１４】
動き推定におけるタスクあたりの処理量は、動きベクトルの探索量で決まる。探索量は、探索を開始してから動きベクトル指点を検出するまでに探索を行った範囲に相当する。１タスク当たりの探索量は、そのタスクの参照可能フレーム数などによって大まかに定まる。ただし、十分によい動きベクトルが見つかったと判断された時点で探索は打ち切られる場合があるので、１タスク当たりの探索量が、参照可能フレーム数に比例するとは限らない。例えば、１フレーム・１ブロックあたりの探索量は、探索開始点と動きベクトルの指点の距離によって異なる。探索開始点と動きベクトルの指点の距離が近ければ少なく、離れていれば多くなる。
【０２１５】
動きベクトルは周囲のブロックの動きベクトルとの相関が高いので、周囲の動きベクトルから算出された予測ベクトルを中心として動きベクトル探索を行うことによって、早期に良い動きベクトルを決定することができる。予測ベクトルと周囲のブロックの動きベクトルの向き・大きさが似ていれば、予測ベクトルは動きベクトルに近く、探索量は少ないことが予想される。一方、周囲のブロックの動きベクトルの向き・大きさが様々であれば、予測ベクトルの精度が不十分で探索量は多くなると考えられる。そこで、本実施形態のタスクスケジューリング装置６は、第３の実施形態のようにして算出した予測ベクトルの精度を使用して、各タスクの処理量を推定する。これにより、各タスクの処理量の推定の精度が高くなる。そのため、本実施形態のタスクスケジューリング装置６は、１タスクグループ当たりの処理量が均等になるよう、タスクをグルーピングできる。
【０２１６】
図１８は、本実施形態のタスクスケジューリング装置６の構成を表す図である。
【０２１７】
図１８を参照すると、タスクスケジューリング装置６は、図１６のタスクスケジューリング装置５の構成に加えて、予測ベクトル精度推定部３０３と、タスク処理量修正部６１４を含む。
【０２１８】
予測ベクトル精度推定部３０３は、第３の実施形態の予測ベクトル精度推定部３０３と同じである。
【０２１９】
タスク処理量修正部６１４は、予測ベクトル精度推定部３０３が算出した、予測ベクトルの精度に応じて、タスク処理量推定部５０８が推定しタスク処理量記憶部５０９に格納した、各タスクの処理量を修正する。
【０２２０】
タスクスケジューリング装置６の他の構成要素は、第５の実施形態のタスクスケジューリング装置５の同じ番号の構成要素と同じなので、説明を省略する。
【０２２１】
次に、本実施形態のタスクスケジューリング装置６の動作について、図面を参照して詳細に説明する。
【０２２２】
図１９は、タスクスケジューリング装置６の動作の例を表すフローチャートである。図１９と第５の実施形態の動作を表す図１７を比較すると、ステップＳ５０１とステップＳ１０３の間にステップＳ３０４、Ｓ３０５、Ｓ６０６がある点以外は同じである。以下では図１７の第５の実施形態の動作との相違点を中心に説明する。
【０２２３】
タスク処理量推定部５０８が、タスク取得部１０１が取得したタスク情報からそのタスクの処理量を推定した（ステップＳ５０１）後、予測ベクトル精度推定部３０３が、符号化対象ブロックの周囲のブロックの動きベクトルを取得する（ステップＳ３０４）。
【０２２４】
予測ベクトル精度推定部３０３は、取得した動きベクトルから、符号化対象ブロックの予測ベクトルの精度を計算する（ステップＳ３０５）。
【０２２５】
ステップＳ３０４及びステップＳ３０５は、それぞれ、図８の第３の実施形態のステップＳ３０４及びステップＳ３０５と同じなので、詳細な説明を省略する。
【０２２６】
タスク処理量修正部６１４は、予測ベクトル精度推定部３０３が推定した精度を表す、修正係数を使用して、タスク処理量推定部５０８が推定してタスク処理量記憶部５０９に格納したタスクの処理量を修正する（ステップＳ６０６）。
【０２２７】
タスク処理量修正部６１４は、例えば、タスク処理量記憶部５０９タスクの処理量に対して、そのタスクが対象とする符号化対象ブロックの予測ベクトルに対応する、ｘ方向の修正係数とｙ方向の修正係数を掛ければよい。
【０２２８】
ステップＳ１０３以降の動作は、第５の実施形態の動作と同じなので、説明を省略する。
【０２２９】
なお、予測ベクトル精度推定部３０３は、算出した修正係数をタスク処理量推定部５０８に送信してもよい。そして、タスク処理量推定部５０８は、算出した処理量に受信した修正係数を掛けた値を、タスク特定情報と対応付けて、タスク処理量記憶部５０９に格納してもよい。この場合、タスク処理量修正部６１４は存在しなくてもよい。
【０２３０】
以上で説明した本実施形態には、第５の実施形態の効果に加えて、複数のプロセッサコアでタスクを実行する場合に、プロセッサコアあたりの処理量を更に均等化することができ、更に高速な並列処理が可能になるという効果がある。
【０２３１】
その理由は、タスク処理量推定部５０８が推定したタスクの処理量を、予測ベクトル精度推定部３０３が推定したそのタスクに対応する予測ベクトルの精度を使用して、タスク処理量修正部６１４が修正するからである。従って、各タスクの処理量の推定精度が向上する。スケジュール部１０４は、タスク毎の修正後の処理量を使用して、個々のプロセッサコアに実行させるタスクの集合であるタスクグループ毎の処理量の合計が均等になるよう、各タスクグループにタスクを割り当てる。そのため、各タスクグループの処理量が更に均等になる。従って、全てのタスクの処理が完了するまでの時間が更に短縮する。すなわち、更に高速な並列処理が可能になる。
【０２３２】
（第７の実施の形態）
次に、本発明の第７の実施形態について、図面を参照して詳細に説明する。
【０２３３】
これまでの各実施形態説明したのは、既にスケジューリングされたタスクグループと、それ以外のタスクの相関を全て算出して、そのタスクグループに割り当てるタスクを選択するタスクスケジューリング装置である。なお、第１から第３の実施形態は、タスクグループが１である場合に相当する。一方、本実施形態では、タスクを順次１個ずつ選択し、選択したタスクと各タスクグループとの間の相関によって、選択したタスクを割り当てるタスクグループを選択することで、タスクのタスクグループへの割り当てとスケジューリングを行う方法を説明する。
【０２３４】
図２７は、本実施形態のタスクスケジューリング装置７の構成を表すブロック図である。
【０２３５】
図２７と図１３を比較すると、タスクスケジューリング装置７は、第４の実施形態のタスクスケジューリング装置４の構成に加えて、グループアクセス記憶部７０４を含む点が異なる。以下では、タスクスケジューリング装置７とタスクスケジューリング装置４の相違点を中心に説明する。
【０２３６】
グループアクセス算出部４０６は、更新されたタスクグループのアクセス領域を算出し、タスクグループを特定する情報と関連付けて、グループアクセス記憶部７０４に格納する。
【０２３７】
グループアクセス記憶部７０４は、グループアクセス算出部４０６が算出した、タスクグループ毎のアクセス領域を表す情報を、タスクグループを特定する情報と関連付けて記憶する。
【０２３８】
タスク相関算出部１０３は、アクセス領域記憶部１０５から読み出したタスクのアクセス情報と、グループアクセス記憶部７０４から読み出したタスクグループのアクセス情報から、相関を算出する。
【０２３９】
次に、本実施形態の動作について、図面を参照して詳細に説明する。
【０２４０】
図２８は、本実施形態のタスクスケジューリング装置７の動作を表すフローチャートである。
【０２４１】
図２８を参照すると、まず、タスクスケジューリング装置７は、グループ数のタスクのタスク情報を取得し、タスク情報を取得した各タスクをそれぞれ別のタスクグループに登録する（ステップＳ７０１）。
【０２４２】
具体的には、まず、タスク取得部１０１がタスクグループの数であるグループ数を受信する。タスク取得部１０１は、グループ数に加えて、スケジューリングの対象となるタスクの数も受信すればよい。タスク取得部１０１は、受信したグループ数分のタスク情報を取得する。タスクアクセス取得部１０２は、タスク取得部１０１が取得したタスク情報が表すタスクのアクセス情報を取得し、タスク特定情報に関連付けてアクセス領域記憶部１０５に格納する。スケジュール部１０４は、取得した各タスクを、それぞれ異なるタスクグループに登録する。スケジュール部１０４は、各タスクを特定する情報を、それぞれ異なるタスクグループを特定する情報に関連付け、グループ記憶部４０７に格納する。この時点では、各タスクグループは１個のタスクしか含んでおらず、各タスクグループのアクセス領域は、各タスクが含むタスクのアクセス領域と等しい。グループアクセス算出部４０６は、各タスクグループに含まれるタスクのアクセス情報を、アクセス領域記憶部１０５から読み出し、タスクグループを特定する情報に関連付けてグループアクセス記憶部７０４に格納する。
【０２４３】
タスク取得部１０１は、ステップＳ７０１におけるタスク情報受信の際、例えば、符号化対象フレームをグループ数の領域に分割し、各領域から一つずつ符号化対象ブロックを選択し、選択した符号化対象ブロックに対して処理を行うタスクを１つずつ取得すればよい。タスク取得部１０１がこのようにタスクを取得すると、タスクグループ毎のタスクの処理位置（符号化対象ブロックの位置）は、符号化対象フレーム内で分散する。あるいは、タスク取得部１０１は、フレーム毎に、そのフレームを参照フレームとするタスクを１つずつ選択し、取得してもよい。タスク取得部１０１がこのようにタスクを取得すると、タスクグループ毎のアクセス領域が分散する。
【０２４４】
次に、タスク取得部１０１は、まだスケジューリングされていないタスクのタスク情報を取得する（ステップＳ１０１）。タスク取得部１０１は、まだスケジューリングされていないタスクから任意のタスクを選択して、選択したタスクのタスク情報を取得すればよい。
【０２４５】
アクセス領域推定部１０７は、タスク取得部１０１から取得したタスク情報から、アクセス領域を推定すればよい。
【０２４６】
次に、タスクアクセス取得部１０２が、タスク情報を選択したタスクのアクセス情報を、例えばアクセス領域を推定するアクセス領域推定部１０７から取得する（ステップＳ１０２）。タスクアクセス取得部１０２は取得したアクセス情報を、対応するタスクのタスク特定情報に関連付けて、アクセス領域記憶部１０５に格納する。
【０２４７】
次に、タスク相関算出部１０３は、アクセス領域記憶部１０５からタスク取得部１０１がタスク情報を取得したタスクのアクセス情報を読み出す。タスク相関算出部１０３は、読み出したアクセス情報と、グループアクセス記憶部７０４が記憶する各タスクグループのアクセス情報から、タスク取得部１０１がタスク情報を取得したタスクと各タスクグループとの間の相関を、それぞれ算出する（ステップＳ７０４）。
【０２４８】
タスク相関算出部１０３は、タスク同士の相関の算出と同様にして、タスクとタスクグループとの間の相関を算出すればよい。例えば、第１の実施形態のように、アクセス情報がアクセス領域の範囲を表す情報である場合、タスク相関算出部１０３は、タスクのアクセス領域とタスクグループのアクセス領域の重複領域の大きさを算出すればよい。タスクグループのアクセス領域は、第４の実施形態と同様に、例えば、タスクグループが含むタスクのアクセス領域の和であればよい。例えば、第２の実施形態のように、アクセス情報が予測ベクトル指点の座標である場合、タスク相関算出部１０３は、タスクの予測ベクトル指点と、タスクグループの予測ベクトル指点の距離を算出して、相関にすればよい。この場合、タスクグループの予測ベクトル指点の座標は、例えば、そのタスクグループが含むタスクの予測ベクトル指点の重心であればよい。
【０２４９】
次に、スケジュール部１０４が、タスク情報を取得したタスクを、そのタスクとの相関が高く、含まれるタスクの数が少ないタスクグループに登録する（ステップＳ７０５）。
【０２５０】
スケジュール部１０４は、例えば、含まれるタスクの数が少ないほど評価値が高く、相関が高いほど評価値が高くなるような、タスク数と相関を変数とする評価式で算出した評価値が、最も高いタスクグループを選択してタスクを登録すればよい。評価式は、含まれるタスクの数が１タスクグループ当たりのタスク数以上になると、タスクグループにタスクが登録されない評価値になる評価式であればよい。スケジュール部１０４は、例えば、含まれるタスクの数が１タスクグループ当たりのタスク数未満であるタスクグループの中で、タスク情報を取得したタスクとの間の相関が最も高いタスクグループを選択し、選択したタスクグループにそのタスクを登録してもよい。この場合のスケジュール部１０４の動作は、タスク数が１タスクグループ当たりのタスク数未満の場合相関に比例する評価値を出力し、タスク数が１タスクグループ当たりのタスク数以上の場合評価値として０を出力する評価式による、上述の動作に相当する。なお、スケジュール部１０４が、タスク取得部１０１が取得したスケジューリング対象のタスク数をグループ数で割ることで、１タスクグループ当たりのタスク数を算出すればよい。
【０２５１】
次に、グループアクセス算出部４０６は、更新されたタスクグループのアクセス領域を算出し、タスクグループを特定する情報と関連付けて、グループアクセス記憶部７０４に格納する（ステップＳ７０６）。グループアクセス算出部４０６は、更新されたタスクグループを表す情報を、スケジュール部１０４から受信すればよい。グループアクセス算出部４０６は、グループ記憶部４０７に格納されている、各タスクグループに含まれるタスクを表す情報の更新を検出してもよい。
【０２５２】
全てのタスクのスケジューリングが終了していない場合（ステップＳ１０６、Ｎｏ）、ステップＳ１０１からステップＳ７０６を繰り返す。なお、グループアクセス算出部４０６は、タスクグループのアクセス情報を更新する動作（ステップＳ７０６）を、ステップＳ７０５終了後、全てのタスクのスケジューリングが終了していない場合に（ステップＳ１０６、Ｎｏ）、行ってもよい。この場合、グループアクセス算出部４０６は、ステップＳ７０６の動作を、ステップＳ７０５の直後には行わなくて良い。
【０２５３】
全てのタスクのスケジューリングが終了した場合（ステップＳ１０６、Ｙｅｓ）、出力部１０６は、タスクグループ毎のタスクの実行順序を表す情報を出力する（ステップＳ１０７）。
【０２５４】
スケジュール部１０４は、タスクの実行順序を表す情報を出力する前に、例えば第１、第２、第３の実施形態のいずれかと同様にして、タスクグループに含まれる各タスクの実行順序を、タスクグループ毎に決定してもよい。この場合、出力部１０６は、スケジュール部１０４が決定したタスクグループ毎の実行順序を表す情報を出力すればよい。タスクグループ毎の実行順序は、例えば、それぞれのタスクグループにタスクが登録された順序でもよい。この場合、スケジュール部１０４は、各タスクグループに含まれるタスクのタスク特定情報が、タスクグループに登録した順序になるように、タスクグループ毎のタスク特定情報をグループ記憶部４０７に格納すればよい。
【０２５５】
また、グループ記憶部４０７は、各タスクグループに割り当てられたタスクの実行順序を、タスクグループを特定する情報に関連付けて記憶していてもよい。ステップＳ７０６で、グループアクセス算出部４０６は、タスクグループ内における実行順序が最初のタスクのアクセス情報と最後のタスクのアクセス情報の組を、タスクグループのアクセス情報にすればよい。そして、グループアクセス算出部４０６は、タスクグループ内における実行順序が最初のタスクのアクセス情報と最後のタスクのアクセス情報の組を、タスクグループを特定する情報に関連付けて、グループアクセス記憶部７０４に格納すればよい。
【０２５６】
この場合、ステップＳ７０４で、タスク相関算出部１０３は、タスク相関算出の対象となるタスクの、タスクグループ内の実行順序が最初のタスクとの間のタスク相関と、同タスクグループ内の実行順序が最後のタスクとの間のタスク相関の、双方を算出すればよい。タスク相関算出部１０３は、算出した２つのタスク相関のいずれか大きい方を、タスク相関の算出の対象となるタスクと、そのタスクグループとの間の相関にすればよい。
【０２５７】
ステップＳ７０５では、スケジュール部１０４は、上述の方法と同様に、タスクを割り当てるタスクグループを選択すればよい。スケジュール部１０４は、選択したタスクグループの実行順序が最初のタスクと最後のタスクのうち、割り当てるタスクとの間のタスク相関が大きい方のタスクと、その割り当てるタスクが連続するよう実行順序を決定すればよい。スケジュール部１０４は、各タスクグループに含まれるタスクのタスク特定情報を、決定した実行順序通りの順番に並べて、グループ記憶部４０７に格納すればよい。
【０２５８】
グループ記憶部４０７が、各タスクグループを特定する情報に関連付けられた、実行順序通りの順番のタスク特定情報の組を記憶している場合、ステップＳ１０６で、出力部１０６は、グループ記憶部４０７が記憶する情報をそのまま出力してもよい。
【０２５９】
また、タスクスケジューリング装置７は、第５の実施形態のタスクスケジューリング装置５と同様に、タスク処理量推定部５０８とタスク処理量記憶部５０９を含んでいてもよい。その場合、スケジュール部１０４は、タスク数の代わりに、タスク処理量推定部５０８が算出した処理量の合計値を使用すればよい。
【０２６０】
さらに、タスクスケジューリング装置７は、第６の実施形態のタスクスケジューリング装置６と同様に、タスク処理量推定部５０８とタスク処理量記憶部５０９に加えて、予測ベクトル精度推定部３０３と、タスク処理量修正部６１４を含んでいてもよい。その場合、タスク処理量修正部６１４が、第６の実施形態と同様にして、タスクの処理量を修正すればよい。さらに、スケジュール部１０４は、タスク数の代わりに、タスク処理量推定部５０８が算出し、タスク処理量修正部６１４が修正した処理量の合計値を使用すればよい。
【０２６１】
以上で説明した本実施形態には、第４の実施形態の効果に加えて、タスクのスケジューリングにおける処理量を削減することができるという効果がある。
【０２６２】
その理由は、タスク相関算出部１０３が、必ずしも、スケジューリングの対象となるタスクから選択した２つのタスクの組合せ全てに対して、タスク相関を算出するわけではないからである。
【０２６３】
次に、第１から第７までの各実施形態の変形例について説明する。
【０２６４】
プロセッサ１００３が、複数のプロセッサコアでタスクを並列に処理する並列プロセッサである場合、プロセッサ１００３の構成は、複数のプロセッサコアと共有する一つのキャッシュでコアグループを構成し、コアグループが複数ある構成でも良い。この場合、タスク実行部１００２は、キャッシュを共有する各コアグループ毎にタスクグループを割り当てればよい。この場合、コアグループ内でも、各プロセッサコアがタスクを並列に処理することが可能である。
【０２６５】
プロセッサ１００３の構成は、プロセッサ同士がメモリを共有しないマルチプロセッサの構成でも良い。この場合、異なるプロセッサ間ではメインメモリを共有しないため、データの局所化がより重要となる。
【０２６６】
また、プロセッサ１００３の構成は、キャッシュメモリのかわりにスクラッチパッドメモリを持つ構成でも良い。スクラッチパッドメモリは、キャッシュメモリと同様に小容量・高速なメモリであり、保持するデータをユーザが明示的に管理できるため、本発明によるデータローカリティをより有効に利用することができる。
【０２６７】
上で説明した各実施形態では、タスクは、異なる複数のフレームを参照するか否かに関わらず、一つのマクロブロックに対して行う処理をまとめた処理を指していた。しかし、例えば特許文献２や特許文献３のように、同一マクロブロックに対する処理であっても、参照フレームが異なれば、別々のタスクであってもよい。
【０２６８】
一般的にキャッシュメモリには、実際に使用されたデータではなくても、使用されたデータに近いにアドレスに存在するデータも格納される。そのため、２つのタスクのアクセス領域が重複する面積が同じであっても、それぞれのアクセス領域のメモリ上の配置により、キャッシュのヒット率が異なることが考えられる。例えば各フレームの各画素のデータが、横方向に隣接する画素でアドレスが連続するようにメモリに格納されているのであれば、タスク実行後にキャッシュに格納されているデータは、そのタスクのアクセス領域とアクセス領域に横方向に隣接する領域のデータである。従って、２つのタスクのアクセス領域の重複領域の面積が同じであっても、例えば、２つのタスクの予測ベクトル指点の座標の縦方向の差が横方向の差より大きい場合より、縦方向の差が横方向の差より小さい場合の方が、キャッシュのヒット率が高いと考えられる。よって、タスク相関算出部１０３は、アクセス領域の重複量や予測ベクトル指点間の距離に方向を加味して、タスク間の相関を算出することもできる。例えば、タスク相関算出部１０３が、２つのタスクの、アクセス領域に横方向で隣接した所定の幅の領域を、アクセス領域に加えた領域の重複量を、それらの２つの領域のタスク相関にすればよい。あるいは、タスク相関算出部１０３は、２つのタスクの、予測ベクトル指点の座標の横方向の成分に、例えば値が１未満の所定の重みを掛けて算出した、予測ベクトル指点間の距離を、その２つのタスクのタスク相関にすればよい。
【０２６９】
第３の実施形態や第５の実施形態の予測ベクトル精度推定部３０３は、例えば、周囲のブロックの予測ベクトルの平均値と、符号化対象ブロックの予測ベクトルとの差など、ベクトルの分散ではない他の値から、予測ベクトルの精度を表す値を算出してもよい。また、第３の実施形態や第５の実施形態では、予測ベクトル精度推定部３０３は、空間的に近い周囲のブロック、すなわち符号化対象フレーム内の符号化対象ブロックの周囲のブロックの予測ベクトルから、符号化対象ブロックの予測ベクトルの精度を表す値を算出する。しかし、予測ベクトル精度推定部３０３は、空間的に近いブロックの予測ベクトルに加えて、時間的に近いブロックの予測ベクトルを使用して、符号化対象ブロックの予測ベクトルの精度を表す値を算出してもよい。なお、時間的に近いブロックは、符号化対象フレームの隣接フレーム内の、符号化対象ブロックと同一位置のブロックである。予測ベクトル精度推定部３０３は、さらに、符号化対象フレームの隣接フレーム内の、符号化対象ブロックと同一の位置から所定範囲内に存在するブロックの予測ベクトルを使用してもよい。
【０２７０】
タスクスケジューリング装置１、タスクスケジューリング装置３、タスクスケジューリング装置４、タスクスケジューリング装置５、タスクスケジューリング装置６、タスクスケジューリング装置７、及び情報処理装置１０００は、それぞれ、コンピュータ及びコンピュータを制御するプログラム、専用のハードウェア、又は、コンピュータ及びコンピュータを制御するプログラムと専用のハードウェアの組合せにより実現することができる。
【０２７１】
タスク取得部１０１、タスクアクセス取得部１０２、タスク相関算出部１０３、スケジュール部１０４、出力部１０６、アクセス領域推定部１０７、予測ベクトル精度推定部３０３、アクセス領域修正部３０４、グループアクセス算出部４０６、タスク処理量推定部５０８、タスク処理量修正部６１４は、例えば、プログラムを記憶する記録媒体からメモリに読み込まれた、各部の機能を実現するための専用のプログラムと、そのプログラムを実行するプロセッサにより実現することができる。また、アクセス領域記憶部１０５、グループ記憶部４０７、タスク処理量記憶部５０９、グループアクセス記憶部７０４は、コンピュータが含むメモリやハードディスク装置により実現することができる。あるいは、タスク取得部１０１、タスクアクセス取得部１０２、タスク相関算出部１０３、スケジュール部１０４、アクセス領域記憶部１０５、出力部１０６、アクセス領域推定部１０７、予測ベクトル精度推定部３０３、アクセス領域修正部３０４、グループアクセス算出部４０６、グループ記憶部４０７、タスク処理量推定部５０８、タスク処理量記憶部５０９、タスク処理量修正部６１４、グループアクセス記憶部７０４の一部又は全部を、各部の機能を実現する専用の回路によって実現することもできる。
【０２７２】
タスク生成部１００１、タスク実行部１００２、実行結果出力部１００４は、例えば、プログラムを記憶する記録媒体からメモリに読み込まれた、各部の機能を実現するための専用のプログラムと、そのプログラムを実行するプロセッサにより実現することができる。また、動きベクトル記憶部１００５は、コンピュータが含むメモリやハードディスク装置により実現することができる。あるいは、タスク生成部１００１、タスク実行部１００２、プロセッサ１００３、実行結果出力部１００４、動きベクトル記憶部１００５の一部又は全部を、各部の機能を実現する専用の回路によって実現することもできる。
【０２７３】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０２７４】
（付記１）
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、
前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、
前記タスク列を表す情報を出力する出力手段と
を含むタスクスケジューリング装置。
【０２７５】
（付記２）
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報と前記アクセス情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段とを含み、
前記タスク相関算出手段は、更に、１個以上の前記タスクの、前記タスク列で構成されるタスクグループ各々の中の、含まれる前記タスク各々の前記処理量の合計が所定値未満である、１個の前記タスクグループである対象タスクグループが含む、各タスクでアクセスされるメモリ領域と、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、前記タスクグループのいずれにも含まれない前記タスク各々に対して算出し、
前記スケジュール手段は、前記タスクグループのいずれにも含まれない前記タスク各々の中で、前記対象タスクグループとの間の前記グループ相関が最も高い前記タスクを、前記対象タスクグループの前記タスク列に加え、
前記出力手段は、前記タスクグループ毎の前記タスク列を表す情報を出力する
付記１に記載のタスクスケジューリング装置。
【０２７６】
（付記３）
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段を含み、
前記タスク相関算出手段は、更に、１個以上の前記タスクの、前記タスク列でそれぞれ構成されるタスクグループが含む各タスクでアクセスされるメモリ領域と、複数の前記タスクグループのいずれにも含まれない前記タスク各々から選択された、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、複数の前記タスクグループ各々に対して算出し、
前記スケジュール手段は、複数の前記タスクグループの、いずれにも含まれない前記タスクから対象タスクを順次選択し、複数の前記タスクグループ各々に対して、選択した前記対象タスクとの間の前記グループ相関と、前記対象タスクの前記処理量とから評価値を算出し、複数の前記タスクグループで前記評価値が最も高い前記タスクグループの前記タスク列に、前記対象タスクを加え、
前記出力手段は、前記タスクグループ毎の前記タスク列を表す情報を出力する
付記１に記載のタスクスケジューリング装置。
【０２７７】
（付記４）
前記タスク内容情報が、前記タスクの種類を表すタスク種類情報と、時系列の複数のフレームを含む動画像中の、前記タスクの処理の対象の領域である対象ブロックを含む前記フレームである対象フレームの中における、前記対象ブロックの位置を特定する情報と、前記動画像中の、前記タスクの前記対象ブロックを対象とする前記処理で参照される前記フレームである参照フレームを特定する情報とを含む、前記タスク情報を取得する前記タスク取得手段と、
前記タスク種類情報が、前記参照フレーム中の、前記対象ブロックに対応する領域の位置の推定と、前記対象フレームの中における前記対象ブロックの位置に対応する、前記参照フレームの中の位置から、前記参照フレームの中の推定した前記位置までの距離と方向を表す、前記対象ブロックの動きベクトルの算出を含む処理である、動き推定を表す場合、前記対象フレーム中における、前記対象ブロックの周囲の複数のブロックの、既に算出されている前記動きベクトル各々を取得し、取得した前記動きベクトル各々から前記対象ブロックの前記動きベクトルの予測値である予測ベクトルを生成し、生成した前記予測ベクトルと前記タスク情報から、前記タスク特定情報で特定される前記タスクでアクセスされる前記参照フレーム内の領域を推定し、推定した前記領域を格納する前記メモリ領域の配置を表す前記アクセス情報を生成し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、取得した前記動きベクトルと前記タスク情報から、前記アクセス情報を生成するタスクアクセス推定手段と
を含む付記１乃至３のいずれかに記載のタスクスケジューリング装置。
【０２７８】
（付記５）
前記タスク特定情報と、当該タスク特定情報で特定される前記タスクでアクセスされる前記メモリ領域の大きさを含むアクセス情報との組を記憶する前記アクセス領域記憶手段と、
前記タスク種類情報が動き推定を表す場合、前記対象ブロックの、周囲の複数のブロックの前記動きベクトル各々を取得し、取得した前記動きベクトル各々から、前記予測ベクトルの精度を推定する予測ベクトル精度推定手段と、
推定した前記精度を使用して、前記精度が高いほど、対応する前記対象ブロックを処理の対象とする前記タスクでアクセスされる前記メモリ領域の大きさが小さくなるように、前記メモリ領域の大きさを修正するアクセス領域修正手段と
を含む付記４に記載のタスクスケジューリング装置。
【０２７９】
（付記６）
推定した前記精度を使用して、前記精度が高いほど前記処理量が少なくなるように、前記処理量を修正するタスク処理量修正手段
を含む付記４又は５に記載のタスクスケジューリング装置。
【０２８０】
（付記７）
前記タスクアクセス取得手段は、前記タスク種類情報が動き推定を表す場合、前記予測ベクトルを取得し、前記アクセス情報として、前記対象ブロックの位置から前記予測ベクトル分移動した点である予測ベクトル指点の座標を算出し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、前記アクセス情報として、前記対象ブロックの位置から前記動きベクトル分移動した点である動きベクトル指点の座標を算出し、
前記タスク相関算出手段は、２つのタスクの前記タスク特定情報に関連付けられている前記アクセス情報である前記座標間の距離を算出して、２つの前記タスク間の前記タスク相関を求める
付記１乃至４のいずれかに記載のタスクスケジューリング装置
（付記８）
付記１乃至７のいずれかに記載のタスクスケジューリング装置と、
プロセッサと、
当該プロセッサが実行するタスクのタスク情報を生成し、前記タスクスケジューリング装置に入力するタスク生成手段と、
前記タスクスケジューリング装置から前記タスク列を表す情報を取得し、取得した前記タスク列の順序に従い、前記プロセッサに前記タスクを実行させるタスク実行手段と
を含むタスクスケジュールシステム。
【０２８１】
（付記９）
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得し、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納し、
前記タスク特定情報と前記アクセス情報の組をアクセス領域記憶手段に記憶し、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出し、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加え、
前記タスク列を表す情報を出力する
タスクスケジューリング方法。
【０２８２】
（付記１０）
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得し、
前記タスク情報と前記アクセス情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定し、
更に、１個以上の前記タスクの、前記タスク列で構成されるタスクグループ各々の中の、含まれる前記タスク各々の前記処理量の合計が所定値未満である、１個の前記タスクグループである対象タスクグループが含む、各タスクでアクセスされるメモリ領域と、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、前記タスクグループのいずれにも含まれない前記タスク各々に対して算出し、
前記タスクグループのいずれにも含まれない前記タスク各々の中で、前記対象タスクグループとの間の前記グループ相関が最も高い前記タスクを、前記対象タスクグループの前記タスク列に加え、
前記タスクグループ毎の前記タスク列を表す情報を出力する
付記９に記載のタスクスケジューリング方法。
【０２８３】
（付記１１）
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得し、
前記タスク情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定し、
更に、１個以上の前記タスクの、前記タスク列でそれぞれ構成されるタスクグループが含む各タスクでアクセスされるメモリ領域と、複数の前記タスクグループのいずれにも含まれない前記タスク各々から選択された、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、複数の前記タスクグループ各々に対して算出し、
複数の前記タスクグループの、いずれにも含まれない前記タスクから対象タスクを順次選択し、複数の前記タスクグループ各々に対して、選択した前記対象タスクとの間の前記グループ相関と、前記対象タスクの前記処理量とから評価値を算出し、複数の前記タスクグループで前記評価値が最も高い前記タスクグループの前記タスク列に、前記対象タスクを加え、
前記タスクグループ毎の前記タスク列を表す情報を出力する
付記９に記載のタスクスケジューリング方法。
【０２８４】
（付記１２）
前記タスク内容情報が、前記タスクの種類を表すタスク種類情報と、時系列の複数のフレームを含む動画像中の、前記タスクの処理の対象の領域である対象ブロックを含む前記フレームである対象フレームの中における、前記対象ブロックの位置を特定する情報と、前記動画像中の、前記タスクの前記対象ブロックを対象とする前記処理で参照される前記フレームである参照フレームを特定する情報とを含む、前記タスク情報を取得し、
前記タスク種類情報が、前記参照フレーム中の、前記対象ブロックに対応する領域の位置の推定と、前記対象フレームの中における前記対象ブロックの位置に対応する、前記参照フレームの中の位置から、前記参照フレームの中の推定した前記位置までの距離と方向を表す、前記対象ブロックの動きベクトルの算出を含む処理である、動き推定を表す場合、前記対象フレーム中における、前記対象ブロックの周囲の複数のブロックの、既に算出されている前記動きベクトル各々を取得し、取得した前記動きベクトル各々から前記対象ブロックの前記動きベクトルの予測値である予測ベクトルを生成し、生成した前記予測ベクトルと前記タスク情報から、前記タスク特定情報で特定される前記タスクでアクセスされる前記参照フレーム内の領域を推定し、推定した前記領域を格納する前記メモリ領域の配置を表す前記アクセス情報を生成し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、取得した前記動きベクトルと前記タスク情報から、前記アクセス情報を生成する
付記９乃至１１のいずれかに記載のタスクスケジューリング方法。
【０２８５】
（付記１３）
前記タスク特定情報と、当該タスク特定情報で特定される前記タスクでアクセスされる前記メモリ領域の大きさを含むアクセス情報との組を前記アクセス領域記憶手段に記憶し、
前記タスク種類情報が動き推定を表す場合、前記対象ブロックの、周囲の複数のブロックの前記動きベクトル各々を取得し、取得した前記動きベクトル各々から、前記予測ベクトルの精度を推定し、
推定した前記精度を使用して、前記精度が高いほど、対応する前記対象ブロックを処理の対象とする前記タスクでアクセスされる前記メモリ領域の大きさが小さくなるように、前記メモリ領域の大きさを修正する
付記１２に記載のタスクスケジューリング方法。
【０２８６】
（付記１４）
推定した前記精度を使用して、前記精度が高いほど前記処理量が少なくなるように、前記処理量を修正する
付記１２又は１３に記載のタスクスケジューリング方法。
【０２８７】
（付記１５）
前記タスク種類情報が動き推定を表す場合、前記予測ベクトルを取得し、前記アクセス情報として、前記対象ブロックの位置から前記予測ベクトル分移動した点である予測ベクトル指点の座標を算出し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、前記アクセス情報として、前記対象ブロックの位置から前記動きベクトル分移動した点である動きベクトル指点の座標を算出し、
２つのタスクの前記タスク特定情報に関連付けられている前記アクセス情報である前記座標間の距離を算出して、２つの前記タスク間の前記タスク相関を求める
付記９乃至１２のいずれかに記載のタスクスケジューリング方法
（付記１６）
コンピュータを、
処理のまとまりであるタスクを特定するタスク特定情報を含むタスク情報を複数取得するタスク取得手段と、
前記タスクでアクセスされるメモリ領域の配置を表すアクセス情報を取得し、前記タスク特定情報に関連付けてアクセス領域記憶手段に格納するタスクアクセス取得手段と、
前記タスク特定情報と前記アクセス情報の組を記憶するアクセス領域記憶手段と、
２つの前記タスクの前記アクセス情報から、２つの前記タスクでアクセスされるメモリ領域の重複量を表すタスク相関を算出するタスク相関算出手段と、
前記タスクの実行順の列であるタスク列の最初又は最後の前記タスクと、前記タスク列に含まれない前記タスクのいずれかとの組合せ中、前記タスク相関が最も高い前記組合せの前記タスクが連続するように、前記タスク列に含まれない前記タスクを前記タスク列に加えるスケジュール手段と、
前記タスク列を表す情報を出力する出力手段と
して動作させるタスクスケジューリングプログラム。
【０２８８】
（付記１７）
コンピュータを、
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報と前記アクセス情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段と、
更に、１個以上の前記タスクの、前記タスク列で構成されるタスクグループ各々の中の、含まれる前記タスク各々の前記処理量の合計が所定値未満である、１個の前記タスクグループである対象タスクグループが含む、各タスクでアクセスされるメモリ領域と、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、前記タスクグループのいずれにも含まれない前記タスク各々に対して算出する前記タスク相関算出手段と、
前記タスクグループのいずれにも含まれない前記タスク各々の中で、前記対象タスクグループとの間の前記グループ相関が最も高い前記タスクを、前記対象タスクグループの前記タスク列に加える前記スケジュール手段と、
前記タスクグループ毎の前記タスク列を表す情報を出力する前記出力手段と
して動作させる付記１６に記載のタスクスケジューリングプログラム。
【０２８９】
（付記１８）
コンピュータを、
前記タスクの処理の内容を表すタスク内容情報を更に含む前記タスク情報を取得する前記タスク取得手段と、
前記タスク情報から、当該タスク情報が表すタスクの計算量の程度を表す処理量を推定するタスク処理量推定手段と、
更に、１個以上の前記タスクの、前記タスク列でそれぞれ構成されるタスクグループが含む各タスクでアクセスされるメモリ領域と、複数の前記タスクグループのいずれにも含まれない前記タスク各々から選択された、前記タスクでアクセスされるメモリ領域の重なりの大きさを表すグループ相関を、複数の前記タスクグループ各々に対して算出する前記タスク相関算出手段と、
複数の前記タスクグループの、いずれにも含まれない前記タスクから対象タスクを順次選択し、複数の前記タスクグループ各々に対して、選択した前記対象タスクとの間の前記グループ相関と、前記対象タスクの前記処理量とから評価値を算出し、複数の前記タスクグループで前記評価値が最も高い前記タスクグループの前記タスク列に、前記対象タスクを加る前記スケジュール手段と、
前記タスクグループ毎の前記タスク列を表す情報を出力する前記出力手段と
して動作させる付記１６に記載のタスクスケジューリングプログラム。
【０２９０】
（付記１９）
コンピュータを、
前記タスク内容情報が、前記タスクの種類を表すタスク種類情報と、時系列の複数のフレームを含む動画像中の、前記タスクの処理の対象の領域である対象ブロックを含む前記フレームである対象フレームの中における、前記対象ブロックの位置を特定する情報と、前記動画像中の、前記タスクの前記対象ブロックを対象とする前記処理で参照される前記フレームである参照フレームを特定する情報とを含む、前記タスク情報を取得する前記タスク取得手段と、
前記タスク種類情報が、前記参照フレーム中の、前記対象ブロックに対応する領域の位置の推定と、前記対象フレームの中における前記対象ブロックの位置に対応する、前記参照フレームの中の位置から、前記参照フレームの中の推定した前記位置までの距離と方向を表す、前記対象ブロックの動きベクトルの算出を含む処理である、動き推定を表す場合、前記対象フレーム中における、前記対象ブロックの周囲の複数のブロックの、既に算出されている前記動きベクトル各々を取得し、取得した前記動きベクトル各々から前記対象ブロックの前記動きベクトルの予測値である予測ベクトルを生成し、生成した前記予測ベクトルと前記タスク情報から、前記タスク特定情報で特定される前記タスクでアクセスされる前記参照フレーム内の領域を推定し、推定した前記領域を格納する前記メモリ領域の配置を表す前記アクセス情報を生成し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、取得した前記動きベクトルと前記タスク情報から、前記アクセス情報を生成するタスクアクセス推定手段と
として動作させる付記１６乃至１８のいずれかに記載のタスクスケジューリングプログラム。
【０２９１】
（付記２０）
コンピュータを、
前記タスク特定情報と、当該タスク特定情報で特定される前記タスクでアクセスされる前記メモリ領域の大きさを含むアクセス情報との組を記憶する前記アクセス領域記憶手段と、
前記タスク種類情報が動き推定を表す場合、前記対象ブロックの、周囲の複数のブロックの前記動きベクトル各々を取得し、取得した前記動きベクトル各々から、前記予測ベクトルの精度を推定する予測ベクトル精度推定手段と、
推定した前記精度を使用して、前記精度が高いほど、対応する前記対象ブロックを処理の対象とする前記タスクでアクセスされる前記メモリ領域の大きさが小さくなるように、前記メモリ領域の大きさを修正するアクセス領域修正手段と
して動作させる付記１９に記載のタスクスケジューリングプログラム。
【０２９２】
（付記２１）
コンピュータを、
推定した前記精度を使用して、前記精度が高いほど前記処理量が少なくなるように、前記処理量を修正するタスク処理量修正手段
として動作させる付記１９又は２０に記載のタスクスケジューリングプログラム。
【０２９３】
（付記２２）
コンピュータを、
前記タスク種類情報が動き推定を表す場合、前記予測ベクトルを取得し、前記アクセス情報として、前記対象ブロックの位置から前記予測ベクトル分移動した点である予測ベクトル指点の座標を算出し、前記タスク種類情報が動き補償を表す場合、前記対象ブロックの前記動きベクトルを取得して、前記アクセス情報として、前記対象ブロックの位置から前記動きベクトル分移動した点である動きベクトル指点の座標を算出する前記タスクアクセス取得手段と、
２つのタスクの前記タスク特定情報に関連付けられている前記アクセス情報である前記座標間の距離を算出して、２つの前記タスク間の前記タスク相関を求める前記タスク相関算出手段と
して動作させる付記１６乃至１９のいずれかに記載のタスクスケジューリングプログラム。
【０２９４】
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０２９５】
本発明は、キャッシュメモリを搭載した装置における処理タスクのスケジューリング装置、また特に、動画像を圧縮符号化する装置や、マルチコアやメニコアに対応した動画像圧縮符号化ソフトウェアなどに適用できる。
【符号の説明】
【０２９６】
１、３、４、５、６、７    タスクスケジューリング装置
１０１    タスク取得部
１０２    タスクアクセス取得部
１０３    タスク相関算出部
１０４    スケジュール部
１０５    アクセス領域記憶部
１０６    出力部
１０７    アクセス領域推定部
３０３    予測ベクトル精度推定部
３０４    アクセス領域修正部
４０６    グループアクセス算出部
４０７    グループ記憶部
５０８    タスク処理量推定部
５０９    タスク処理量記憶部
６１４    タスク処理量修正部
７０４    グループアクセス記憶部
１０００    情報処理装置
１００１    タスク生成部
１００２    タスク実行部
１００３    プロセッサ
１００４    実行結果出力部
１００５    動きベクトル記憶部
１００６    データ入力部
１００７    データ記憶部
【図１】
2013150094.tif 000003
【図２】
2013150094.tif 000004
【図３】
2013150094.tif 000005
【図４】
2013150094.tif 000006
【図５】
2013150094.tif 000007
【図６】
2013150094.tif 000008
【図７】
2013150094.tif 000009
【図８】
2013150094.tif 000010
【図９】
2013150094.tif 000011
【図１０】
2013150094.tif 000012
【図１１】
2013150094.tif 000013
【図１２】
2013150094.tif 000014
【図１３】
2013150094.tif 000015
【図１４】
2013150094.tif 000016
【図１５】
2013150094.tif 000017
【図１６】
2013150094.tif 000018
【図１７】
2013150094.tif 000019
【図１８】
2013150094.tif 000020
【図１９】
2013150094.tif 000021
【図２０】
2013150094.tif 000022
【図２１】
2013150094.tif 000023
【図２２】
2013150094.tif 000024
【図２３】
2013150094.tif 000025
【図２４】
2013150094.tif 000026
【図２５】
2013150094.tif 000027
【図２６】
2013150094.tif 000028
【図２７】
2013150094.tif 000029
【図２８】
2013150094.tif 000030
【図２９】
2013150094.tif 000031