(57)【要約】【課題】処理を複数に分割することによって得られる処理単位を効率よく処理できる並列処理スケジューラを提供する。【解決手段】並列処理スケジューラは、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開するタスク展開部１０と、演算の許容並列数を越えない条件下で処理を構成するタスクを再構成するタスク最適化部２０と、タスク最適化部２０が再構成した処理を構成する全てのタスクのステップ数を判定するステップ数判定部３０とを備え、ステップ数判定部３０によってステップ数が減少していないと判定された場合に、タスク展開部１０は、タスクを展開する処理を実行する。【選択図】図２０
2019008444.tif 000002
【特許請求の範囲】
【請求項１】
処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングする並列処理スケジューラであって、
演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開するタスク展開部と、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成するタスク最適化部と、
前記タスク最適化部が再構成した前記処理を構成する全てのタスクのステップ数を判定するステップ数判定部とを備え、
前記ステップ数判定部によって前記ステップ数が減少していないと判定された場合に、前記タスク展開部は、タスクを展開する処理を実行する
ことを特徴とする並列処理スケジューラ。
【請求項２】
タスク最適化部は、あるタイミングにおいてそれぞれ実行されることが可能な複数のタスクを一つにマージするマージ部を含む
請求項１記載の並列処理スケジューラ。
【請求項３】
タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
タスク最適化部は、所定の重みを前記ノードに付与する処理を行い、
マージ部は、前記依存関係を考慮し、グループ内のノードに付与された重みの合計が所定の目標値よりも小さくなるようにノードをグルーピングする
請求項２記載の並列処理スケジューラ。
【請求項４】
タスクはＤＣＴの各処理であり、
タスク展開部は、行列積をバタフライ演算に展開する
請求項１記載の並列処理スケジューラ。
【請求項５】
タスク最適化部は、あるタイミングにおいてそれぞれ実行されることが可能な行列積とバタフライ演算とをそれぞれマージするマージ部を含む
請求項４記載の並列処理スケジューラ。
【請求項６】
タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
タスク最適化部は、並列処理数を前記ノードに付与する処理を行い、
マージ部は、前記依存関係を考慮し、グループ内のノードに付与された並列処理数の合計が許容並列数よりも小さくなるようにノードをグルーピングする
請求項５記載の並列処理スケジューラ。
【請求項７】
処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングする並列処理スケジューリング方法であって、
演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開し、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成し、
再構成された前記処理を構成する全てのタスクのステップ数を判定し、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行する
ことを特徴とする並列処理スケジューリング方法。
【請求項８】
あるタイミングにおいてそれぞれ実行されることが可能な複数のタスクを一つにマージする
請求項７記載の並列処理スケジューリング方法。
【請求項９】
処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングするための並列処理プログラムであって、
コンピュータに、
演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開する処理と、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成する処理と、
再構成された前記処理を構成する全てのタスクのステップ数を判定する処理とを実行させ、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行させる
ための並列処理プログラム。
【請求項１０】
コンピュータに、あるタイミングにおいてそれぞれ実行されることが可能な複数のタスクを一つにマージする処理を実行させる請求項９記載の並列処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理を分割することによって得られる複数の処理単位を並列処理するためにスケジューリングする並列処理スケジューラに関する。
【背景技術】
【０００２】
離散信号を周波数領域の信号に変換する手法として、ＤＣＴ（Discrete Cosine Transform ）がある。ＤＣＴは、例えば、Ｈ．２６４／ＡＶＣ（Advanced Video Coding ）やＨ．２６５／ＨＥＶＣ（High Efficiency Video Coding）に基づく動画像圧縮に用いられる。ＤＣＴは、動画像圧縮において動画像を量子化する前に各画素を空間成分から周波数成分に置き換えるために用いられる。画像を周波数成分に変換することによって、周期が小さく人間の目で認識しにくいノイズなどの画素勾配と、全体の模様などの周期が大きく人間の目で認識しやすい画素勾配とを分離できる。すなわち、人間の目で認識しやすい画素勾配は、低周波成分に集中する。そして、量子化をする際に、分離された周波数成分のうち高周波成分をより多く削減するように重み付けすることによって、より能率的にデータ量が削減される。
【０００３】
例えば、ＨＥＶＣでは、ＴＵ（Transform Unit）と呼ばれるブロック単位でＤＣＴがなされる。ＴＵサイズは４×４、８×８、１６×１６、３２×３２のうちから選択される。
【０００４】
ＨＥＶＣでは、二次元ＤＣＴが採用されている。入力画像に対して水平方向および垂直方向の変換が実施される。また、ＨＥＶＣでは、符号化および復号時の誤差をなくすために、整数精度の直交変換が採用されている。具体的には、ＤＣＴは入力信号と変換行列との行列積で定義される。例えば、３２×３２ＴＵの３２点一次元ＤＣＴは３２個の入力信号と３２×３２変換行列との積になる。なお、ＤＣＴの詳細な処理は、非特許文献１に記載されている。
【０００５】
ＤＣＴはＮ個の入力信号ベクトルとＮ×Ｎ次元の変換行列との行列積で定義されるため、特に３２×３２のような大きなＴＵでは演算量が増加する。そこで、ＨＥＶＣでは、Chenのバタフライ演算が部分的に適用可能な直交変換（以下、Partial バタフライともいう。）が定義されている。
【０００６】
図２２は、Partial バタフライが適用された３２点一次元ＤＣＴを説明するためのブロック図である。図２２において、ＯｄｄＮ（Ｎ：４，８，１６，３２）とＥｖｅｎＮとは、それぞれ、偶数番目の信号、奇数番目の信号に対する（Ｎ／２）×（Ｎ／２）行列積を示す。また、ＡｄｄＳｕｂＮは、Ｎ個の信号に対するバタフライ演算を示す。
【０００７】
図２３は、ＡｄｄＳｕｂ４のバタフライ線図である。Partial バタフライ実装では、Ｎ点の入力信号に対する行列積を、偶数番目と奇数番目の信号に対する（Ｎ／２）点ＤＣＴ二つとＮ点バタフライ演算とに置き換えることができる。また、偶数番目の信号に対する（Ｎ／２）点ＤＣＴを同様に展開することができる。
【０００８】
奇数番目の信号に対する（Ｎ／２）点ＤＣＴをそれ以上展開することはできない。偶数番目の信号に対するＤＣＴのみを小さなＤＣＴに展開できることから、Partial バタフライと呼ばれる。結果として得られるPartial バタフライ実装を表すブロック図は、大きなＤＣＴ内に小さなＤＣＴが内包される形になっている。よって、ハードウェア実装の面積が削減される。
【０００９】
また、Ｎ×Ｎ行列積を（Ｎ／２）×（Ｎ／２）行列積２つとＮ点バタフライ演算とに置き換えることができるので、Partial バタフライ実装によって乗算数と加算数とが削減される。例えば、３２点ＤＣＴを行列積で実装した場合には、１０２４回の乗算と９９２回の加算が必要になるが、３２点ＤＣＴをPartial バタフライで実装した場合には、３４２回の乗算と３７２回の加算とで済み、行列積型の実装と比較して演算量が削減される。
【００１０】
一般に、動画像圧縮処理は、並列処理されることによって、処理速度が向上する。ＤＣＴの並列処理の場合、複数ＴＵを並列処理したり、複数のＮ点ＤＣＴを並列処理することが容易に想定される。Ｎ点ＤＣＴのさらに細かな並列化は、例えばＣＰＵ（Central Processing Unit ）では、ＳＩＭＤ（Single Instruction Multiple Data）命令を利用することによって実現可能である。
【００１１】
ＳＩＭＤ命令を用いたＮ点ＤＣＴの並列処理方法が特許文献１に記載されている。特許文献１に記載された方法では、プロセッサのＳＩＭＤ長（１命令で扱えるbit 数）に合わせて、Ｎ点ＤＣＴは、２ｋ個の（Ｎ／２ｋ）点ＤＣＴとバタフライ演算とである前処理と、後処理とに展開される。Ｎ点ＤＣＴをＳＩＭＤ命令で処理できる（Ｎ／２ｋ）点ＤＣＴまで展開することによって、（Ｎ／２ｋ）点ＤＣＴをＳＩＭＤ命令によって並列処理することができる。ＤＣＴの点数をＮ、1度に並列処理できるデータの数をｎとすると、展開数ｋは以下の式で表すことができる。
【００１２】
ｋ＝ｌｏｇ２（Ｎ／ｎ）                  （１）
【００１３】
特許文献１に記載された技術が対象としているＤＣＴでは、偶数番目の信号と奇数番目の信号との両方のＮ×Ｎ行列積演算を、（Ｎ／２）×（Ｎ／２）行列積演算とバタフライ演算とに展開可能である。従って、特許文献１に記載された技術が対象としているＮ点ＤＣＴをｎ並列で処理したい場合、（１）式を用いて展開数を求め、展開数回分行列積を小さな行列積とバタフライ演算とに展開することによって、ｎ並列で処理が可能である。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特許第３９７７００３号公報
【非特許文献】
【００１５】
【非特許文献１】M. Budagavi, A. Fuldseth, G. Bjontegaard, V. Sze, and M. Sadafale, "Core transform design in the high efficiency video coding (HEVC) standard", IEEE Journal of Selected Topic in Signal Processing, vol. 7, No. 6, Dec. 2013
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかし、上述したように、ＨＥＶＣのＤＣＴでは、偶数番目の信号に関するＮ×Ｎ行列演算ＯｄｄＮのみを、（Ｎ／２）×（Ｎ／２）行列積演算Ｅｖｅｎ（Ｎ／２）および（Ｎ／２）×（Ｎ／２）行列積演算Ｏｄｄ（Ｎ／２）と、Ｎ個の信号に対するバタフライ演算ＡｄｄＳｕｂ（Ｎ／２）とに展開できる。従って、展開数が十分に大きかったとしても（Ｎ／２）×（Ｎ／２）行列積が残ってしまい、（Ｎ／２）がｎよりも大きい場合に、ｎ並列で処理できない。よって、ｎ並列で処理できるようにタスク（ＯｄｄＮやＥｖｅｎＮやＡｄｄＳｕｂＮのような処理単位）を最適化するタスクスケジューラが必要である。
【００１７】
図２４は、特許文献１に記載された技術を用いたＤＣＴの並列処理スケジューラを実現するための構成例を示すブロック図である。図２４に示された並列処理スケジューラは、タスク決定部１５０とタスクスケジューリング部２００とを含む。
【００１８】
タスク決定部１５０は、展開数計算部１０６と、タスク展開部１０１と、タスク分割部１０７とを含む。展開数計算部１０６は、並列数（一時に処理可能な演算数）を入力として、ＤＣＴをバタフライ演算に展開する回数を出力する機能を有する。タスク展開部１０１は、ＤＡＧ（Directed Acyclic Graph：有向非巡回グラフ）と展開数とを入力として、ＤＡＧ上の行列積を、入力された展開数回のバタフライ演算に展開し、展開されたＤＡＧを出力する機能を有する。
【００１９】
タスク分割部１０７は、ＤＡＧ上の各タスクをチェックし、タスクの並列度が目的の並列数（許容される並列数：演算の許容並列数）よりも大きかった場合に、タスクの並列度が目的の並列数に合うようにタスクを分割する機能を有する。
【００２０】
タスクスケジューリング部２００は、ＤＡＧを入力として、各ステップで処理するタスクをスケジューリングし、タスクスケジュールとして出力する機能を有する。
【００２１】
タスクスケジューリング部２００は、ＤＣＴの各タスクを示すＤＡＧと並列数とを入力し、タスクスケジュールを得る。なお、ここでは、ＤＣＴ内の各タスクの依存関係をコンピュータで処理しやすい形で表現するためにＤＡＧを入力する例が示されるが、タスクの表現方法はＤＡＧに限られない。
【００２２】
以下、ＨＥＶＣの３２点ＤＣＴを１６並列で処理する場合を例にして、図２５のフローチャートを参照して並列処理スケジューラの処理を説明する。まず、展開数計算部１０６は、（１）式を用いて展開数を計算する（ステップＳ１１０）。この例では、Ｎ＝３２、ｎ＝１６なので、展開数ｋ＝１である。次いで、タスク展開部１０１は、ＤＣＴの各タスクを表すＤＡＧにおけるＯｄｄＮを、ステップＳ１１０の処理で求められた展開数分バタフライ演算に展開する（ステップＳ１２０）。入力は３２点ＤＣＴのＤＡＧなので、ＤＡＧは、例えば、図２６に示されるようになる。
【００２３】
展開数ｋ＝１なので、図２６に例示されたＤＡＧを一回展開すると、図２７（ａ）に示されるように、ＤＡＧは、Ｅｖｅｎ３２およびＯｄｄ３２と、ＡｄｄＳｕｂ３２とになる。
【００２４】
次に、タスク分割部１０７は、ＤＡＧ上の各タスクをチェックし、並列度が目的の並列数より大きいタスクを目的の並列数に合うように分割する（ステップＳ１３０）。図２７（ａ）に示された例では、ＡｄｄＳｕｂ３２の並列度は、３２と目的の並列数１６より大きい。そこで、タスク分割部１０７は、図２７（ｂ）に示されるように、ＡｄｄＳｕｂ３２を、並列度１６のＡｄｄＳｕｂ３２＿１とＡｄｄＳｕｂ３２＿２とに分割する。
【００２５】
そして、タスクスケジューリング部２００は、部分的にバタフライ演算に展開されたＤＡＧを用いて、各タスクの処理順をスケジューリングする（ステップＳ１４０）。なお、例えば、ＤＡＧをトポロジカルソートし、ソート順に処理するようスケジューリングすることによって、タスクの処理順が決定される。
【００２６】
図２８は、タスク展開を示すフローチャートである。タスク展開部１０１は、まず、現在の展開数ｉを０に初期化する（ステップＳ１２１）。次いで、タスク展開部１０１は、Ｏｄｄ（Ｎ／２ｉ）をバタフライ演算に展開する（ステップＳ１２２）。最初は、ｉ＝０なので、タスク展開部１０１は、Ｏｄｄ３２（３２点ＤＣＴ）をＥｖｅｎ１６とＯｄｄ１６とＡｄｄＳｕｂ１６とに展開する。次に、タスク展開部１０１は、ｉをインクリメントする（ステップＳ１２３）。そして、現在の展開数ｉが目的の展開数ｋより小さい場合にはステップＳ１２２に戻り、ｉがｋに達した場合にはタスク展開を終了する（ステップＳ１２４）。
【００２７】
次に、図２９のフローチャートを参照して、ステップＳ１４０のタスクスケジューリング処理を説明する。３２点ＤＣＴを例にして、タスクスケジューリング部２００がトポロジカルソートによって処理順を決める場合についてする。タスクスケジューリング部２００は、まず、ＳＩＭＤ命令を用いてＥｖｅｎ３２を並列処理することに決定する（ステップＳ２０１）。次いで、タスクスケジューリング部２００は、ＳＩＭＤ命令を用いてＯｄｄ３２を並列処理することに決定する（ステップＳ２０２）。次に、タスクスケジューリング部２００は、ＳＩＭＤ命令を用いてＡｄｄＳｕｂ３２＿１を並列処理することに決定する（ステップＳ２０３）。さらに、タスクスケジューリング部２００は、ＳＩＭＤ命令を用いてＡｄｄＳｕｂ３２＿２を並列処理することに決定する（ステップＳ２０４）。
【００２８】
並列処理スケジュール前のＤＡＧは、３２点ＤＣＴであるから３２×３２の行列積が含まれ、１６並列では効率よく並列処理されない。並列処理スケジュール後のＤＡＧは、３２×３２の行列積が１６×１６の行列積に置き換わるので、１６並列で効率よく並列処理可能である。
【００２９】
しかし、特許文献１に記載された技術は、ＳＩＭＤ向けの並列処理に関する技術である。近年、ＧＰＵ（General Processing Unit ）のようなＳＩＭＴ（Single Instruction Multiple Thread）アーキテクチャによる並列化が広く用いられている。ＳＩＭＴでは、複数データに対して命令を実行するＣＰＵのＳＩＭＤ命令と異なり、複数スレッドが同じ命令を実行する。ＳＩＭＤでは、一度記憶領域上の複数のデータが１つのレジスタにまとめて格納され、まとめてデータが処理され、演算が終わると元の記憶領域に戻される。
【００３０】
ＳＩＭＴでは、同じ命令が複数のプロセッシングコアに同時に発行される。従って、ＳＩＭＴでは、各プロセッシングコアが、固有のレジスタを持ち、アドレス情報や計算途中の中間データといった固有のデータを保持できる。ＳＩＭＴでは、各プロセッシングコアが固有の情報を保持できるので、別々のデータに対する処理であっても、構成される命令が同じであれば並列処理可能である。この特徴を活かすことによって、複数の異なるタスクを１ステップで並列処理できる場合がある。ＤＣＴについて具体的に例を挙げると、ＳＩＭＴアーキテクチャでは、複数のＮ×Ｎ行列積であるＯｄｄＮまたはＥｖｅｎＮを並列に処理できる。しかし、ＳＩＭＤ向けの手法では、異なるタスクを並列処理することが考慮されていないので、効率よいスケジューリング結果が得られない。
【００３１】
本発明は、処理を複数に分割することによって得られる処理単位を効率よく処理できる並列処理スケジューラを提供することを目的とする。
【課題を解決するための手段】
【００３２】
本発明による並列処理スケジューラは、処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングする並列処理スケジューラであって、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開するタスク展開部と、演算の許容並列数を越えない条件下で処理を構成するタスクを再構成するタスク最適化部と、タスク最適化部が再構成した処理を構成する全てのタスクのステップ数を判定するステップ数判定部とを備え、ステップ数判定部によってステップ数が減少していないと判定された場合に、タスク展開部は、タスクを展開する処理を実行することを特徴とする。
【００３３】
本発明による並列処理スケジューリング方法は、処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングする並列処理スケジューリング方法であって、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開し、演算の許容並列数を越えない条件下で処理を構成するタスクを再構成し、再構成された処理を構成する全てのタスクのステップ数を判定し、ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行することを特徴とする。
【００３４】
本発明による並列処理スケジューリングプログラムは、処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングするための並列処理プログラムであって、コンピュータに、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開する処理と、演算の許容並列数を越えない条件下で処理を構成するタスクを再構成する処理と、再構成された処理を構成する全てのタスクのステップ数を判定する処理とを実行させ、ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行させることを特徴とする。
【発明の効果】
【００３５】
本発明によれば、処理を複数に分割することによって得られる処理単位を効率よく処理できる。
【図面の簡単な説明】
【００３６】
【図１】第１の実施形態の並列処理スケジューラの構成を示すブロック図である。
【図２】タスク最適化部の構成例を示すブロック図である。
【図３】第１の実施形態の並列処理スケジューラの全体的な動作を示すフローチャートである。
【図４】第１の実施形態の並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときの０反復目のＤＡＧを示す説明図である。
【図５】第１の実施形態の並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときの１反復目のＤＡＧとステップ数とを示す説明図である。
【図６】第１の実施形態の並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときの２反復目のＤＡＧとステップ数とを示す説明図である。
【図７】第１の実施形態の並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときの３反復目のＤＡＧとステップ数とを示す説明図である。
【図８】第１の実施形態におけるタスク最適化部の動作を示すフローチャートである。
【図９】第１の実施形態におけるタスク最適化部が３２点ＤＣＴをタスク最適化するときの２反復目のＤＡＧとステップ数との様子を示す説明図である。
【図１０】第１の実施形態の並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときのタスクスケジューリング処理を示すフローチャートである。
【図１１】第２の実施形態の並列処理スケジューラの構成を示すブロック図である。
【図１２】第２の実施形態の並列処理スケジューラの全体的な動作を示すフローチャートである。
【図１３】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときの０反復目のＤＡＧとステップ数とを示す説明図である。
【図１４】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときの１反復目のＤＡＧとステップ数とを示す説明図である。
【図１５】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときの２反復目のＤＡＧとステップ数とを示す説明図である。
【図１６】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときの３反復目のＤＡＧとステップ数とを示す説明図である。
【図１７】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときのタスクスケジューリング部の処理を示すフローチャートである。
【図１８】第２の実施形態の並列処理スケジューラが１６点ＤＣＴを並列処理スケジューリングするときのＮｕｌｌタスク除外部が考慮されたタスクスケジューリング処理を示すフローチャートである。
【図１９】本発明による並列処理スケジューラの機能を実現可能な情報処理装置の構成例を示すブロック図である。
【図２０】本発明による並列処理スケジューラの主要部を示すブロック図である。
【図２１】本発明による他の態様の並列処理スケジューラの主要部を示すブロック図である。
【図２２】ＨＥＶＣにおけるPartial バタフライが適用された３２点一次元ＤＣＴを説明するためのブロック図である。
【図２３】ＡｄｄＳｕｂ４のバタフライ線図である。
【図２４】ＤＣＴの並列処理スケジューラを実現するための構成例を示すブロック図である。
【図２５】図２４に示された並列処理スケジューラの動作を示すフローチャートである。
【図２６】３２点ＤＣＴのＤＡＧの一例を示す説明図である。
【図２７】３２点ＤＣＴを１回バタフライ演算に展開した際のＤＡＧの一例を示す説明図である。
【図２８】図２４に示された並列処理スケジューラにおけるタスク展開部の動作を示すフローチャートである。
【図２９】図２４に示された並列処理スケジューラが３２点ＤＣＴを並列処理スケジューリングするときのタスクスケジューリング処理を示すフローチャートである。
【発明を実施するための形態】
【００３７】
以下、本発明の実施形態を図面を参照して説明する。
【００３８】
実施形態１．
図１は、本発明による第１の実施形態の並列処理スケジューラの構成を示すブロック図である。図１に示すように、本実施形態の並列処理スケジューラは、タスク決定部１００とタスクスケジューリング部２００とを含む。タスクスケジューリング部２００の構成および機能は、図２４に示されたものと同じである。
【００３９】
タスク決定部１００は、タスク展開部１０１と、タスク最適化部１０２と、ステップ数判定部１０３と、記憶部１０４とを含む。なお、以下の実施形態では、ＤＣＴ内の各タスクの依存関係をコンピュータで処理しやすい形で表現するために、タスクグラフの一例であるＤＡＧ（具体的には、ＤＡＧで特定されるタスク）が用いられる例が示されるが、タスクの表現方法はＤＡＧに限られない。
【００４０】
タスク展開部１０１は、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに分割する機能を有する。本実施形態では、タスク展開部１０１は、ＤＡＧと展開数を入力し、ＤＡＧ上の行列積を、入力された展開数回バタフライ演算に展開し、展開されたＤＡＧを出力する。タスク最適化部１０２は、タスク展開部１０１でバタフライ演算に展開されたＤＡＧと並列数とを入力し、並列処理向けに補正したＤＡＧとその処理に要するステップ数とを出力する機能を有する。ステップ数判定部１０３は、タスク最適化部１０２で計算された現反復において算出されたステップ数と、記憶部１０４から読み出した最小のステップ数とを比較して、更新された最小ステップ数を記憶部１０４に出力する機能を有する。また、ステップ数判定部１０３は、最小ステップ数におけるＤＡＧをタスクスケジューリング部２００に出力する。さらに、ステップ数判定部１０３は、インクリメントした展開数をタスク展開部１０１に出力する。記憶部１０４は、反復試行された中での最小のステップ数とその際のＤＡＧを記憶する。
【００４１】
図２は、タスク最適化部１０２の構成例を示すブロック図である。図２に示されるタスク最適化部１０２は、タスクコスト計算部１２１と、タスク分割部１２２と、タスクマージ部１２３と、ステップ数計算部１２４とを含む。
【００４２】
タスクコスト計算部１２１は、入力されたＤＡＧの各タスクに対して、演算量と並列度（並列処理数）とを計算し、計算結果（すなわち、演算量および並列度）をＤＡＧ上の各ノード（タスクに相当）に重みとして付与する機能を有する。演算量として、例えば１スレッドあたりの演算数（積和数）がある。
【００４３】
タスク分割部１２２は、ＤＡＧの各タスクをチェックして、同一ステップで処理できないタスクを複数タスクに分割する機能を有する。タスクマージ部１２３は、ＤＡＧの各タスクをチェックして、同一ステップで並列処理できる複数のタスクを一つのタスクグループとしてマージする機能を有する。ステップ数計算部１２４は、処理に要するステップ数を計算する機能を有する。計算するステップ数として、各タスクグループの最大演算数がある。ＧＰＵでは、並列処理に係るステップ数が全スレッド内の最大ステップ数で律速されるためである。
【００４４】
次に、図３のフローチャートを参照して本実施形態の並列処理スケジューラの動作を説明する。図３は、第１の実施形態の並列処理スケジューラの全体的な動作を示すフローチャートである。ここでは、３２点ＤＣＴを１６並列で処理する場合を例にする。従って、入力されるＤＡＧは、図２６に示されたような３２点ＤＣＴ（上述したように、具体的には、ＤＡＧで特定されるタスク）である。
【００４５】
まず、タスク展開部１０１は、ＤＡＧにおけるＮ×Ｎの行列積ＯｄｄＮを、（Ｎ／２）×（Ｎ／２）の行列積Ｅｖｅｎ（Ｎ／２）およびＯｄｄ（Ｎ／２）と、Ｎ個の信号に対するバタフライ演算のＡｄｄＳｕｂＮとに展開する（ステップＳ３１０）。なお、最初は０反復目なので、展開を行わず、タスク展開部１０１の出力は、図４（ａ）に示されるようになる。なお、ｐ反復目は（ｐ：０または自然数）、ステップＳ３１０〜Ｓ３３０のループ処理の（ｐ＋１）回目の処理を示す。
【００４６】
次に、タスク最適化部１０２は、バタフライ演算に展開されたＤＡＧを並列処理に合った形に最適化し、処理に要するステップ数を計算する（ステップＳ３２０）。０反復目の最適化結果が、図４（ｂ）に示されている。合計ステップ数は６４である。なお、最適化の方法とステップ数の計算方法とは後述される。
【００４７】
次いで、ステップ数判定部１０３は、ステップ数が削減されたか否か確認する（ステップＳ３３０）。ステップ数が削減された場合には、ステップ数判定部１０３は、記憶部１０４に記憶されている最小ステップ数とＤＡＧとを、削減後のステップ数とその際のＤＡＧとで更新する。そして、展開数をインクリメントして、ステップＳ３１０に移行する。ステップ数が削減されなかった場合には、最小ステップ数とその際のＤＡＧとをタスクスケジューリング部２００に出力する。タスクスケジューリング部２００は、タスクスケジューリングを行う（ステップＳ３４０）。
【００４８】
なお、最初（０反復目）はステップ数が初めて計算されたので、ステップ数判定部１０３は、計算結果（ステップ数とこのときのＤＡＧ（図４（ｂ）参照）を、記憶部１０４に設定し、１反復目のステップＳ３１０の処理に進む。
【００４９】
１反復目では、タスク展開部１０１は、３２点ＤＣＴをＥｖｅｎ３２とＯｄｄ３２とＡｄｄＳｕｂ３２とに展開する（ステップＳ３１０）。このときのＤＡＧは、図５（ａ）に示されるようになる。次いで、タスク最適化部１０２は、ＤＡＧを最適化する（ステップＳ３２０）。最適化後のＤＡＧは、図５（ｂ）に示されるようになる。図５（ｂ）に示すように、ＡｄｄＳｕｂ３２は、３２並列で１ステップの処理であるが、目的の並列数は１６であるから、ＡｄｄＳｕｂ３２＿１とＡｄｄＳｕｂ３２＿２との二つに分割される。分割後のステップ数は３４である。
【００５０】
ステップ数判定部１０３は、ステップ数が削減したか否か確認する（ステップＳ３３０）。現在最小のステップ数は６４であり、現反復のステップ数は３４である。従って、ステップ数が削減されている。その場合には、ステップ数判定部１０３は、記憶部１０４に記憶されている最小ステップ数とその際のＤＡＧとを、現反復のステップ数（この例では、３４）と分割後のＤＡＧとに更新する。そして、展開数をインクリメントして、２反復目のステップＳ３１０に移行する。
【００５１】
２反復目では、タスク展開部１０１は、３２点ＤＣＴをＥｖｅｎ１６とＯｄｄ１６とＡｄｄＳｕｂ１６とＯｄｄ３２とＡｄｄＳｕｂ３２とに展開する（ステップＳ３１０）。このときのＤＡＧは、図６（ａ）に示されるようになる。次いで、タスク最適化部１０２は、ＤＡＧを最適化する（ステップＳ３２０）。最適化後のＤＡＧは、図６（ｂ）に示されるようになる。図６（ｂ）に示すように、１反復目と同様に、ＡｄｄＳｕｂ３２はＡｄｄＳｕｂ３２＿１とＡｄｄＳｕｂ３２＿２の二つに分割される。Ｅｖｅｎ１６とＯｄｄ１６はそれぞれ８並列で８ステップ要する処理である。目的の並列数は１６であるから、Ｅｖｅｎ１６とＯｄｄ１６とは同時に処理されることが可能である。そこで、タスク最適化部１０２は、それらを、１６並列で８ステップのＥｖｅｎ１６／Ｏｄｄ１６にマージする。マージ後のステップ数は２７である。
【００５２】
なお、本明細書における「同時に処理されることが可能（同時に処理可能）な複数のタスク」は、あるタイミングにおいて当該複数のタスクがそれぞれ実行されていることが可能（すなわち、並列的に、または、疑似並列的に実行されていることが可能）であることを意味し、それらのタスクが同時に実行開始されることに限定されない。
【００５３】
ステップ数判定部１０３は、ステップ数が削減されたか否か確認する（ステップＳ３３０）。そのときの最小のステップ数は３４であり、現反復のステップ数は２７である。ステップ数が削減されているので、記憶部１０４に記憶されている最小ステップ数とその際のＤＡＧとを、現反復のステップ数（この例では、２７）とマージ後のＤＡＧとに更新する。そして、展開数をインクリメントして、３反復目のステップＳ３１０に移行する。
【００５４】
３反復目では、タスク展開部１０１は、３２点ＤＣＴをＥｖｅｎ８とＯｄｄ８とＡｄｄＳｕｂ８とＯｄｄ１６とＡｄｄＳｕｂ１６とＯｄｄ３２とＡｄｄＳｕｂ３２とに展開する（ステップＳ３１０）。このときのＤＡＧは、図７（ａ）に示されるようになる。次いで、タスク最適化部１０２は、ＤＡＧを最適化する（ステップＳ３２０）。最適化後のＤＡＧは、図７（ｂ）に示されるようになる。図７（ｂ）に示すように、２反復目と同様に、ＡｄｄＳｕｂ３２はＡｄｄＳｕｂ３２＿１とＡｄｄＳｕｂ３２＿２の二つに分割される。Ｅｖｅｎ４とＯｄｄ４はそれぞれ４並列で４ステップ要する処理である。また、Ｏｄｄ１６は、８並列で８ステップ要する処理である。目的の並列数は１６であるから、Ｅｖｅｎ８とＯｄｄ８とＯｄｄ１６とは同時に処理されることが可能である。そこで、タスク最適化部１０２は、それらを、１６並列で８ステップのＥｖｅｎ８／Ｏｄｄ８／Ｏｄｄ１６にマージする。マージ後のステップ数は２８である。
【００５５】
ステップ数判定部１０３は、ステップ数が削減したか否か確認する（ステップＳ３３０）。そのときの最小のステップ数は２７であり、現反復のステップ数は２８である。従って、ステップ数が削減されていない。その場合には、ステップ数判定部１０３は、最小ステップ数とその際のＤＡＧとを記憶部１０４から読み出し、タスクスケジューリング部２００に出力する。タスクスケジューリング部２００は、タスクスケジューリングを行う（ステップＳ３４０）。
【００５６】
タスクスケジューリング部２００は、図２４に示された並列処理スケジューラの場合と同様に、例えば、ＤＡＧをトポロジカルソートし、ソート順に処理するようスケジューリングする。ただし、図２４に示された並列処理スケジューラの場合と比較すると、タスクスケジューリング部２００に入力されるＤＡＧにおいて、タスクがマージまたは分割されている点が異なる。
【００５７】
次に、図８のフローチャートを参照して、タスク最適化部１０２の動作をより詳しく説明する。ここでは、３２点ＤＣＴがスケジューリングされた場合の、図３に例示された処理における２反復目の動作を例にする。従って、このときのタスク最適化部１０２の入力は、図６（ａ）に示されたＤＡＧである。
【００５８】
まず、タスクコスト計算部１２１は、ＤＡＧにおける各タスクの並列度とステップ数とを計算し、それらをＤＡＧ上のノードに重みとして与える（ステップＳ３２１）。並列度は、各タスクを何並列で処理できるかを表す。ステップ数は、例えば１並列当たりの積和演算数を表す。ＧＰＵは、積和演算を１命令で処理できるからである。重みは、例えば、（ステップ数、並列度）の形で表すことができる。図６（ａ）を参照すると、タスクコスト計算部１２１の出力は、図９（ａ）に示されるようになる。
【００５９】
次いで、タスク分割部１２２は、ＤＡＧ上の各タスクをチェックする。タスク分割部１２２は、並列度が目的の並列数よりも大きいタスクがあった場合、そのタスクを目的の並列数に合うよう分割する（ステップＳ３２２）。このときのタスク分割部１２２の出力は、図９（ｂ）に示されるようになる。
【００６０】
次に、タスクマージ部１２３は、ＤＡＧ上の各タスクをチェックし、同時に処理できるタスク（並列処理できるタスク）を１つのタスクにマージする（ステップＳ３２３）。同時に処理できるタスクは、例えば、少なくともエッジで接続されていないタスク同士を意味する。エッジで接続されたタスクは処理順に依存関係があるので、それらを並列処理できない。また、上述したように、ＳＩＭＴでは、同じ命令で構成されるタスクであれば、並列処理可能である。
【００６１】
なお、例えばＮＶＩＤＩＡ（登録商標）社のＧＰＵでは、ワープ単位（３２スレッド）で命令が発行される。ワープ内に違う命令が含まれるスレッドがある場合には、そのスレッドは、命令がワープで処理されるときにストールする。ストールによって並列処理効率は下がるものの、並列処理自体は可能である。従って、ＳＩＭＴでは、例えば（Ｎ／２）ステップ要するＯｄｄＮと（Ｎ／４）ステップ要するＯｄｄ（Ｎ／２）とを並列処理する場合、Ｏｄｄ（Ｎ／２）を担当するスレッドが（Ｎ／４）ステップ分ストールしてしまうものの、タスク割り当てがされていないスレッド数が余っている場合には並列処理できるように２つのタスクをマージすることによってステップ数が削減される。さらに、行列積とバタフライ演算とでは構成される演算が異なるので、ＯｄｄＮおよびＥｖｅｎＮが、ＡｄｄＳｕｂＮと分けてグルーピングされることによって、ＳＩＭＴでより効率よく処理できるタスクスケジュールが実現される。
【００６２】
タスクマージ部１２３は、上述したタスクのマージを、例えばＤＡＧ上のタスクをグループ内の並列度の合計が目的の並列数よりも小さくになるようにグルーピングすることによって実現できる。タスクマージ部１２３は、グルーピングを行うときに、例えば、ＤＡＧ上のタスクをトポロジカルソートし、トポロジカルソート順でグループに詰めていく。すなわち、タスクマージ部１２３は、タスクの依存関係を考慮してグルーピングを行う。そして、タスクマージ部１２３は、グループの並列度が目的の並列数を越える場合には、新たなグループを作成する処理を順次繰り返す。
【００６３】
なお、エッジで接続されているタスク同士は同じグループに所属できない制約がある。また、行列積とバタフライ演算とを分けてグルーピングする場合には、例えば、タスクマージ部１２３は、まず行列積（ＯｄｄＮとＥｖｅｎＮ）をトポロジカルソート順にグルーピングし、次いで残ったバタフライ演算（ＡｄｄＳｕｂＮ）をトポロジカルソート順でグルーピングすることによって、容易にグルーピングを実現できる。
【００６４】
図９（ｃ）に、グルーピングされた結果が示されている。  図９（ｃ）において、破線の丸囲いはグループを示す。図９（ｃ）から、Ｅｖｅｎ１６とＯｄｄ１６とがそれぞれ並列度８で同時に処理可能であることがわかる。タスクマージ部１２３の出力、すなわち、グループ内のタスクをマージした結果は、図９（ｄ）に示されるＤＡＧになる。
【００６５】
ステップ数計算部１２４は、最適化したＤＡＧに係るステップ数の合計を計算する（ステップＳ３２４）。ステップ数計算部１２４は、ＤＡＧにおける各タスクのステップ数を合計することによって、ステップ数を算出する。このときの合計ステップ数は、図９（ｄ）に示されているように２７である。
【００６６】
以下、図１０のフローチャートを参照して、ステップＳ３４０のタスクスケジューリング処理（図９（ｄ）参照）を説明する。
【００６７】
タスクスケジューリング部２００は、まず、Ｅｖｅｎ１６とＯｄｄ１６を並列処理することに決定する（ステップＳ４０１）。Ｅｖｅｎ１６もＯｄｄ１６も８×８行列積であるから、用いられる命令は同じであり、並列処理可能である。次いで、タスクスケジューリング部２００は、ＡｄｄＳｕｂ１６を並列処理することに決定する（ステップＳ４０２）。ＡｄｄＳｕｂ１６は１６個の信号に対するバタフライ演算であるから、１６並列で処理することが可能である。次いで、タスクスケジューリング部２００は、Ｏｄｄ３２を並列処理することに決定する（ステップＳ４０３）。Ｏｄｄ３２は１６×１６の行列積であるから、１６並列で処理することが可能である。次に、タスクスケジューリング部２００は、ＡｄｄＳｕｂ３２＿１を並列処理することに決定する（ステップＳ４０４）。そして、タスクスケジューリング部２００は、ＡｄｄＳｕｂ３２＿２を並列処理することに決定する（ステップＳ４０５）。
【００６８】
以上のようにして、タスクスケジューリング部２００は、タスクスケジュールを作成する。
【００６９】
ＡｄｄＳｕｂ３２＿１とＡｄｄＳｕｂ３２＿２は３２個の信号に対するバタフライ演算が２つに分けられたものである。それぞれ１６個の信号に対するバタフライ演算であるから、それぞれを１６並列で処理することが可能である。
【００７０】
本実施形態では、タスク決定部１００がステップ数を最小化するための反復の中で展開数を決定するので、目的の並列数に対して最適なタスクスケジュールが得られる。また、本実施形態では、タスクマージ部１２３が非連続なデータを同時に処理するようスケジューリングするので、ＧＰＵのようなＳＩＭＴアーキテクチャで効率よく並列処理できるタスクスケジュールが得られる。
【００７１】
本実施形態で得られるタスクスケジュールでは、同時に処理できる異なるタスクをマージして並列処理することが考慮されている。よって、タスクは、ＧＰＵのようなＳＩＭＴアーキテクチャで効率よく並列処理される。従って、ＧＰＵのようなＳＩＭＴアーキテクチャで処理した場合に処理を高速化できる。例えば、ＨＥＶＣにおける３２点ＤＣＴを入力とした場合、従前の並列処理スケジュール方法では、３２点ＤＣＴを処理するために３４ステップ必要である。しかし、本実施形態の並列処理スケジュール方法では、３２点ＤＣＴを処理するためのステップ数は２７に低減する。
【００７２】
実施形態２．
図１１は、本発明による第２の実施形態の並列処理スケジューラの構成を示すブロック図である。図１１に示すように、本実施形態の並列処理スケジューラは、第１の実施形態の並列処理スケジューラ（図１参照）に、ＤＡＧ結合部３００と、Ｎｕｌｌタスク除外部４００とが追加されている。
【００７３】
ＤＡＧ結合部３００は、入力された複数のＤＡＧを１つのＤＡＧとして接続する機能を有する。ＤＡＧ結合部３００は、例えば、空のノード（Ｎｕｌｌノード：Ｎｕｌｌタスクのノード：何もしないタスクを示す。）を用意し、各ＤＡＧのトポロジカルソート順で最後のノードをＮｕｌｌノードに接続することによって、複数のＤＡＧを接続する。
【００７４】
Ｎｕｌｌタスク除外部４００は、スケジューリングされたタスクのうち何もしないタスクであるＮｕｌｌタスクを削除する機能を有する。
【００７５】
次に、図１２のフローチャートを参照して本実施形態の並列処理スケジューラの動作を説明する。図１２は、第２の実施形態の並列処理スケジューラの全体的な動作を示すフローチャートである。ここでは、４つの１６点ＤＣＴを３２並列で処理する場合を例にする。
【００７６】
ＤＡＧ結合部３００は、入力された複数のＤＡＧを接続する（ステップＳ３５０）。
【００７７】
図１３（ａ）には、入力される複数のＤＡＧが示されている。図１３（ｂ）には、Ｎｕｌｌノードで接続された複数のＤＡＧが示されている。
【００７８】
ステップＳ３１０〜Ｓ３４０の処理は、図３に示された第１の実施形態での各処理と同じである。
【００７９】
本実施形態では、０反復目では展開数が０であるので、タスク最適化部１０２の入力は、図１３（ｂ）に示されるようになる。タスク最適化部１０２によるタスク最適化（ステップＳ３２０）の結果は、図１３（ｃ）に示されるようになり、ステップ数は３２になる。
【００８０】
１反復目では、展開数が１になるので、タスク最適化部１０２の入力は図１４（ａ）に示されるようになる。タスク最適化部１０２によるタスク最適化（ステップＳ３２０）の結果は、図１４（ｂ）に示されるようになり、ステップ数は１８になる。
【００８１】
２反復目では、展開数が２になるので、タスク最適化部１０２の入力は図１５（ａ）に示されるようになる。タスク最適化部１０２によるタスク最適化（ステップＳ３２０）の結果は、図１５（ｂ）に示されるようになり、ステップ数は１５になる。
【００８２】
３反復目では、展開数が１になるので、タスク最適化部１０２の入力は図１６（ａ）に示されるようになる。タスク最適化部１０２によるタスク最適化（ステップＳ３２０）の結果は、図１６（ｂ）に示されるようになり、ステップ数は１６になる。このときステップ数が増加したので、ステップＳ３１０〜Ｓ３３０の反復処理を抜けてＳ３４０に移行する。
【００８３】
タスクスケジューリング部２００は、図１５（ｂ）に示されたＤＡＧを、例えばトポロジカルソートを用いてスケジューリングする。
【００８４】
以下、図１７のフローチャートを参照して、図１２に示されたステップＳ３４０のタスクスケジューリング処理（図１５（ｂ）参照）を説明する。
【００８５】
タスクスケジューリング部２００は、Ｅｖｅｎ８ １ 、Ｏｄｄ８ １ 、Ｅｖｅｎ８ ２ 、Ｏｄｄ８ ２ 、Ｅｖｅｎ８ ３ 、Ｏｄｄ８ ３ 、およびＥｖｅｎ８ ４ 、Ｏｄｄ８ ４ を並列処理することに決定する（ステップＳ６０１）。Ｅｖｅｎ８ ｍ （ｍ：１〜４）もＯｄｄ８ ｍ も４×４行列積であるから、用いられる命令は同じであり、並列処理可能である。次いで、タスクスケジューリング部２００は、ＡｄｄＳｕｂ８ １ 、ＡｄｄＳｕｂ８ ２ 、ＡｄｄＳｕｂ８ ３ およびＡｄｄＳｕｂ８ ４ を並列処理することに決定する（ステップＳ６０２）。ＡｄｄＳｕｂ８ ｍ は８個の信号に対するバタフライ演算であるから、３２並列で処理することが可能である。次いで、タスクスケジューリング部２００は、Ｏｄｄ１６ １ 、Ｏｄｄ１６ ２ 、Ｏｄｄ１６ ３ 、Ｏｄｄ１６ ４ を並列処理することに決定する（ステップＳ６０３）。Ｏｄｄ１６ ｍ は８×８の行列積であるから、３２並列で処理することが可能である。次に、タスクスケジューリング部２００は、ＡｄｄＳｕｂ１６ １ およびＡｄｄＳｕｂ１６ ２ を並列処理することに決定する（ステップＳ６０４）。また、タスクスケジューリング部２００は、ＡｄｄＳｕｂ１６ ３ およびＡｄｄＳｕｂ１６ ４ を並列処理することに決定する（ステップＳ６０５）。
【００８６】
さらに、タスクスケジューリング部２００は、Ｎｕｌｌタスクをスケジューリングする（ステップＳ６０６）。
【００８７】
以上のようにして、タスクスケジューリング部２００は、Ｎｕｌｌタスクを含むタスクのタスクスケジュールを作成する。
【００８８】
次に、Ｎｕｌｌタスク除外部４００は、作成されたタスクスケジュールからＮｕｌｌタスクのスケジュールを削除する（ステップＳ３６０）。Ｎｕｌｌタスク除外部４００は、Ｎｕｌｌタスクのスケジュールが除外されたタスクスケジュールを出力する。
【００８９】
なお、Ｎｕｌｌタスク除外部４００がＮｕｌｌタスクのスケジュールを削除することによって、実質的に、タスクスケジューリング部２００は、図１８に示されるタスクスケジューリング（ステップＳ６０６の処理が存在しない。）を実行することになる。
【００９０】
第２の実施形態では、ＤＡＧ結合部３００が複数のＤＡＧをＮｕｌｌノードで接続するように構成されているので、複数のＤＡＧをまとめてスケジューリングできる。よって、複数のＮ点ＤＣＴにおける処理のうち、同時に処理できる処理をまとめて並列処理するようにタスクスケジューリングできる。その結果、複数のＮ点ＤＣＴをより少ないステップ数で並列処理することができ、処理をより高速化できる。
【００９１】
上記の各実施形態における各ブロックをハードウェアで構成することも可能であるが、コンピュータプログラムにより実現することも可能である。
【００９２】
図１９に示す情報処理装置は、のプロセッサ（例えば、ＣＰＵ（Central Processing Unit ））１００１、プログラムメモリ１００２、およびデータを格納するための記憶媒体１００３を備える。記憶媒体１００３として、ハードディスク等の磁気記憶媒体を用いることができる。記憶媒体１００３は、図１および図１１に示された記憶部１０４等を実現する。プログラムメモリ１００２として、半導体記憶媒体や磁気記憶媒体を用いることができる。
【００９３】
図１９に示された情報処理装置において、プログラムメモリ１００２には、図１、図２および図１１のそれぞれに示された各ブロック（記憶部１０４を除く。）の機能を実現するためのプログラムが格納される。そして、プロセッサ１００１は、プログラムメモリ１００２に格納されているプログラムに従って処理を実行することによって、図１および図１１のそれぞれに示された並列処理スケジューラの機能を実現する。
【００９４】
上述したように、上記の各実施形態では、Partial バタフライ展開のみ適用可能なＤＣＴを、例えばＳＩＭＴを用いるＧＰＵを用いて効率よく処理できる並列処理スケジューリング方法が提供される。また、メモリ上に非連続なデータに対する複数の行列積を同時に並列処理することを考慮することによって、ＤＣＴをより効率よく処理する並列処理方法が提供される。
【００９５】
すなわち、上記の各実施形態では、処理の高並列化によって高速なＤＣＴが可能になるので、高解像度な画像のより高速な処理を実現でき、高解像度処理が要求される撮像システムやトランスコードシステム等におけるＤＣＴ処理部の設計に好適に適用可能である。
【００９６】
なお、本発明は、ＤＣＴ処理への適用に限定されず、他の種類の演算処理のタスクへの分割およびタスクスケジューリングに適用可能である。
【００９７】
図２０は、本発明による並列処理スケジューラの主要部を示すブロック図である。図２０に示すように、並列処理スケジューラは、演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開するタスク展開部１０（実施形態におけるタスク展開部１０１に相当）と、演算の許容並列数（例えば、タスク最適化部１０２に入力される並列数）を越えない条件下で処理を構成するタスクを再構成するタスク最適化部２０（実施形態におけるタスク最適化部１０２に相当）と、タスク最適化部２０が再構成した処理を構成する全てのタスクのステップ数を判定するステップ数判定部３０（実施形態におけるステップ数判定部１０３に相当）とを備え、ステップ数判定部３０によってステップ数が減少していないと判定された場合に、タスク展開部１０は、タスクを展開する処理を実行する。複数のタスクに展開する処理およびタスクを展開する処理は、一例として、複数のタスクに分割する処理およびタスクを分割する処理である。
【００９８】
図２１は、本発明による他の態様の並列処理スケジューラの主要部を示すブロック図である。図２１に示されるように、タスク最適化部２０は、あるタイミングにおいてそれぞれ実行されることが可能な複数のタスクを一つにマージするマージ部２１（実施形態におけるタスクマージ部１２３に相当）を含むように構成されていてもよい。
【００９９】
上記の実施形態の一部または全部は以下の付記のようにも記載されうるが、本発明の構成は以下の構成に限定されない。
【０１００】
（付記１）演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開し、
演算の許容並列数（例えば、タスク決定部１００に入力される並列数）を越えない条件下で前記処理を構成するタスクを再構成し、
再構成された前記処理を構成する全てのタスクのステップ数を判定し、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行する並列処理スケジューリング方法であって、
タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
所定の重み（一例として、並列度）を前記ノードに付与する処理を行い、
前記依存関係を考慮し、グループ内のノードに付与された重みの合計が所定の目標値（例えば、タスク決定部１００に入力される並列数）よりも小さくなるようにノードをグルーピングする
並列処理スケジューリング方法。
【０１０１】
（付記２）演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開し、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成し、
再構成された前記処理を構成する全てのタスクのステップ数を判定し、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行する並列処理スケジューリング方法であって、
タスクはＤＣＴの各処理であり、
行列積をバタフライ演算に展開する
並列処理スケジューリング方法。
【０１０２】
（付記３）あるタイミングにおいてそれぞれ実行されることが可能な行列積とバタフライ演算とをそれぞれマージする付記２記載の並列処理スケジューリング方法。
【０１０３】
（付記４）タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
タスク最適化部は、並列処理数（例えば、並列度）を前記ノードに付与する処理を行い、
マージ部は、前記依存関係を考慮し、グループ内のノードに付与された並列処理数の合計が許容並列数よりも小さくなるようにノードをグルーピングする
付記３記載の並列処理スケジューリング方法。
【０１０４】
（付記５）処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングするための並列処理プログラムであって、
コンピュータに、
演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開する処理と、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成する処理と、
再構成された前記処理を構成する全てのタスクのステップ数を判定する処理とを実行させ、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行させるための並列処理プログラムであり、
タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
前記コンピュータに、
所定の重みを前記ノードに付与する処理を行わせ、
前記依存関係を考慮し、グループ内のノードに付与された重みの合計が所定の目標値よりも小さくなるようにノードをグルーピングする処理を実行させる
ための並列処理プログラム。
【０１０５】
（付記６）処理を分割することによって得られる複数のタスクを並列処理するためにスケジューリングするための並列処理プログラムであって、
コンピュータに、
演算対象の処理を、当該処理の演算量よりも演算量が少ない複数のタスクに展開する処理と、
演算の許容並列数を越えない条件下で前記処理を構成するタスクを再構成する処理と、
再構成された前記処理を構成する全てのタスクのステップ数を判定する処理とを実行させ、
前記ステップ数が減少していないと判定された場合に、タスクを展開する処理をあらためて実行させるための並列処理プログラムであり、
タスクはＤＣＴの各処理であり、
コンピュータに、行列積をバタフライ演算に展開する処理を実行させる
ための並列処理プログラム。
【０１０６】
（付記７）コンピュータに、あるタイミングにおいてそれぞれ実行されることが可能な行列積とバタフライ演算とをそれぞれマージする処理を実行させる付記６記載の並列処理プログラム。
【０１０７】
（付記８）タスクの依存関係を含むタスクグラフのノードで各タスクが表現され、
コンピュータに、
並列処理数を前記ノードに付与する処理と、
マージ部は、前記依存関係を考慮し、グループ内のノードに付与された並列処理数の合計が許容並列数よりも小さくなるようにノードをグルーピングする処理と
を実行させる付記７記載の並列処理プログラム。
【符号の説明】
【０１０８】
１０      タスク展開部
２０      タスク最適化部
３０      ステップ数判定部
３１      マージ部
１００    タスク決定部
１０１    タスク展開部
１０２    タスク最適化部
１０３    ステップ数判定部
１０４    記憶部
１２１    タスクコスト計算部
１２２    タスク分割部
１２３    タスクマージ部
１２４    ステップ数計算部
２００    タスクスケジューリング部
３００    ＤＡＧ結合部
４００    Ｎｕｌｌタスク除外部
１００１  プロセッサ
１００２  プログラムメモリ
１００３  記憶媒体
【図１】
2019008444.tif 000003
【図２】
2019008444.tif 000004
【図３】
2019008444.tif 000005
【図４】
2019008444.tif 000006
【図５】
2019008444.tif 000007
【図６】
2019008444.tif 000008
【図７】
2019008444.tif 000009
【図８】
2019008444.tif 000010
【図９】
2019008444.tif 000011
【図１０】
2019008444.tif 000012
【図１１】
2019008444.tif 000013
【図１２】
2019008444.tif 000014
【図１３】
2019008444.tif 000015
【図１４】
2019008444.tif 000016
【図１５】
2019008444.tif 000017
【図１６】
2019008444.tif 000018
【図１７】
2019008444.tif 000019
【図１８】
2019008444.tif 000020
【図１９】
2019008444.tif 000021
【図２０】
2019008444.tif 000022
【図２１】
2019008444.tif 000023
【図２２】
2019008444.tif 000024
【図２３】
2019008444.tif 000025
【図２４】
2019008444.tif 000026
【図２５】
2019008444.tif 000027
【図２６】
2019008444.tif 000028
【図２７】
2019008444.tif 000029
【図２８】
2019008444.tif 000030
【図２９】
2019008444.tif 000031