(57)【特許請求の範囲】
【請求項１】
タスクを格納する複数のタスクキューと、
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得部と、
前記タスク周期取得部から得られた周期に基づいて、前記タスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択部と、
前記タスクキュー選択部で選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー部と、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択部は、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択する
情報処理システム。
【請求項２】
タスクを格納する複数のタスクキューと、
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得部と、
前記タスク周期取得部から得られた周期に基づいて、前記タスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択部と、
前記タスクキュー選択部で選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー部と、
前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように前記複数のタスクキューのタスクキュー数を決定するタスクキュー数決定部と、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択部は、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択する
情報処理システム。
【請求項３】
前記情報処理システムは、前記複数のプロセッサをさらに備え、
前記タスクキュー数決定部は、前記複数のプロセッサのプロセッサ数の約数又は倍数と、同一となるように前記複数のタスクキューのタスクキュー数を決定する請求項２に記載の情報処理システム。
【請求項４】
タスクを格納する複数のタスクキューと、
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得部と、
前記タスク周期取得部から得られた周期に基づいて、前記タスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択部と、
前記タスクキュー選択部で選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー部と、
前記複数のタスクキューのそれぞれについて、前記タスクキューが格納先として選択されたタスクの位相の履歴を示すタスクキュー履歴情報を格納するタスクキュー履歴記憶部と、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択部は、前記タスクキュー履歴記憶部に格納されたタスクキュー履歴情報に基づいて、前記格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択するとともに、当該選択結果に基づいて、前記タスクキュー履歴記憶部に格納される履歴情報を更新することでプロセッサ毎のタスクの処理量の総計を分散させる
情報処理システム。
【請求項５】
タスクを格納する複数のタスクキューと、
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得部と、
前記タスク周期取得部から得られた周期に基づいて、前記タスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択部と、
前記タスクキュー選択部で選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー部と、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択部は、１周期における最初のタスクを格納するタスクキューとして当該１周期の前の１周期における最初のタスクとは異なるタスクキューを選択し、その他のタスクを格納するタスクキューを規則的に選択する
情報処理システム。
【請求項６】
前記タスクは、Ｎ行Ｍ列(Ｎ及びＭは、任意の正整数)に区分した画像の画像処理を実行し、
前記周期は、ＮもしくはＭである請求項１乃至５の何れか１項に記載の情報処理システム。
【請求項７】
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得ステップと、
前記得られた周期に基づいて、複数のタスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択ステップと、
前記選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキューステップと、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択ステップでは、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択する
タスク制御方法。
【請求項８】
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得ステップと、
前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように複数のタスクキューのタスクキュー数を決定するタスクキュー数決定ステップと、
前記得られた周期に基づいて、前記複数のタスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択ステップと、
前記選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキューステップと、
を備え、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択ステップでは、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択する
タスク制御方法。
【請求項９】
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得処理と、
前記得られた周期に基づいて、複数のタスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択処理と、
前記選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー処理と、
をコンピュータに実行させ、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択処理では、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択する
タスク制御プログラム。
【請求項１０】
複数のタスクに属する各タスクの処理量の大小関係の周期を得るタスク周期取得処理と、
前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように複数のタスクキューのタスクキュー数を決定するタスクキュー数決定処理と、
前記得られた周期に基づいて、前記複数のタスクキューの各々に格納するタスクの処理量の合計がタスクキュー毎に偏らないタスクキューのうち、いずれか一つを選択するタスクキュー選択処理と、
前記選択されたタスクキューに、タスク蓄積装置から入力されたタスクを追加するエンキュー処理と、
をコンピュータに実行させ、
前記複数のタスクキューは、それぞれ、複数のプロセッサのいずれかに対応付けられ、対応するプロセッサによってタスクが実行され、
前記タスクキュー選択処理では、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択する
タスク制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理システム、タスク制御方法及びタスク制御プログラムに関する。
【背景技術】
【０００２】
演算量が多く、長い計算時間が必要な処理を高速に実行するための手段の一つに、並列処理がある。並列処理ではタスクと呼ばれる処理単位ごとにプロセッサに振り分けられ、それぞれのプロセッサが並列にタスクを処理する。このタスクの振り分け処理をスケジューリングといい、スケジューリング性能やアルゴリズムが並列処理効率に大きな影響を及ぼす。特に、タスクにより処理量が異なる場合には、プロセッサ毎の処理量が不均衡になりやすく、並列処理効率は低くなりがちである。並列処理効率を高めるためには、スケジューラ制御コストやリソース競合などのスケジューリングに必要なオーバヘッドを低く抑えつつ、プロセッサ毎の処理量を均等にする必要がある。
【０００３】
各タスクが独立に実行できる場合のスケジューリング方式の一例として、非特許文献１に記載の複数のタスクキューを使用してスケジュールする手法がある。タスクキューは実行待ちタスクが入っている待ち行列で、プロセッサはタスクキューからタスクを取り出し、そのタスクの処理を行う。そして、取り出したタスクの処理が終わると次のタスクを取り出す。このように、実行するタスクを動的に決定することで、プロセッサ毎の処理量が均等化される。しかし、タスクキューは複数のプロセッサが排他的にアクセスする必要があるため、多くのプロセッサでひとつのタスクキューを共有すると競合コストが大きい。
【０００４】
非特許文献１に記載の技術は、複数のタスクキューを用い、タスクキューあたりのプロセッサ数を制限することで、タスクキューへのアクセス競合コストを抑えることが出来る。しかし、全てのプロセッサでタスクキューを共有するのではないため、タスクキュー間の負荷不均衡がプロセッサ間の負荷不均衡につながり、並列処理効率に影響する。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】L.M. Ni, C.-F.E. Wu, "Design Tradeoffs for Process Scheduling in Shared Memory Multiprocessor Systems," IEEE Transactions on Software Engineering, pp. 327-334, March, 1989.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１の記載に基づいた並列処理システムは、例えば 図３３に示すように、処理すべきタスクが格納されているタスク蓄積装置９１３と、タスクをタスクキューに割り当てるスケジューリング装置９１１と、実行待ちタスク行列である複数のタスクキュー９８１、９８２、・・・、９８ｍと、タスクを並列処理する複数のプロセッサ９１４１、９１４２、９１４３、・・・、９１４ｎからなる並列演算装置９１４で構成される。ここで、ｍ及びｎは、任意の正整数である。なお、図３３に記載した並列処理システム９０１は、本願の発明者が非特許文献１の記載に基づいて想到したものである。
【０００７】
タスクキュー数ｍはプロセッサ数ｎ以下である。１つのタスクキューに対してそれぞれ一つまたは複数のプロセッサが接続されている。スケジューリング装置９１１は、タスクを追加するタスクキューを選択するキュー選択部９１１１と、選択されたタスクを追加（エンキュー）するエンキュー部９１１２からなる。非特許文献１の記載に基づいたシステムは、図３４に示すように、スケジューリング装置９１１がタスクスケジューリングを行ってタスクをタスクキューに入れ（ステップＳ１０１）、並列演算装置９１４内のプロセッサ９１４１、９１４２、９１４３、・・・、９１４ｎは、タスクキュー９８１、９８２、・・・、９８ｍからタスクを取り出し実行する（ステップＳ１０２）。
【０００８】
非特許文献１では、タスクスケジューリング時に新たなタスクを追加するタスクキューの選択法として、ランダム、サイクリック、負荷最小のタスクキューを選択の３手法について述べられている。１つめの乱数を用いてランダムにタスクキューを選択する手法と、２つめのサイクリック、つまり順番かつ循環的にタスクキューを選択する手法の場合は 図３３に示す構成からなり、タスクスケジューリングは図３５に示すように動作する。
【０００９】
まず、エンキュー部９１１２はタスク蓄積装置９１３中にタスクキューに未割り当てのタスクＴがあるかを判断する（ステップＳ１１１）。未割り当てのタスクＴがなければスケジューリングは終了であり、あれば、キュー選択部９１１１がタスクＴを割り当てるタスクキューＱをランダムもしくはサイクリックに選択する（ステップＳ１１２）。エンキュー部９１１２はタスク蓄積装置９１３から取り出したタスクＴをタスクキューＱに追加する（ステップＳ１１３）。
【００１０】
ここで、並列処理するアプリケーションによっては、各タスクの絶対的な処理量は不明だが、順番付けられたタスクの処理量の大小において周期的な相関があることがわかっている場合がある。例えば、後述するように、並列処理システムにおいて動画像を処理するときに、この動画像を任意の行数及び列数の複数の領域に区分して、区分したそれぞれの領域における画像処理を別々のタスクに実行させる場合である。この場合、例えば、図３６に示されるようなタスク群となる。つまり、各タスクをタスク番号順に並べた場合に、各タスクの処理量が周期的に変化する場合がある。この例ではタスク番号１からタスク番号１２の処理量の大小関係と似た処理量の大小関係のタスク群がタスク番号１３以降も繰り返される。この一定タスク数で繰り返されるタスクの処理量の大小関係において、その繰り返されるタスク数をタスク処理量の周期とする。よって、図３６のタスク群の処理量の周期は１２となる。
【００１１】
上述した非特許文献１の記載に基づいた並列処理システム９０１では、タスクをランダムもしくはサイクリックにタスクキューへ割り当てるため、タスクキュー毎の負荷が分散されにくく、そのため、スケジュールされたタスクの並列処理実行時間が長くなるという課題がある。特に、複数タスクの処理量の大小において周期的な相関がある場合には、相関を考慮しない割り当て方では負荷が偏る可能性が高い。
【００１２】
例えば、図３６に例示したタスク群をタスク番号順にサイクリックに４つのタスクキューに割り当てた場合、図３７に例示するように、特定のタスクキューに負荷が偏ってしまう。つまり、タスクキューに含まれるタスクの処理量が、特定のタスクキューに偏ってしまう。ここで、図３７に示される各タスクキュー内の番号は、タスク番号を示す。つまり、タスクキュー１には、タスク番号１、５、９、１３、１７、２１のタスク番号が格納されている。図３７は、タスクの処理量の大きさに比例して、各タスクの幅が広くなるように図示されている。
【００１３】
３つめのタスクの追加時に負荷最小のタスクキューを選択する場合の構成は 図３８に示すように、スケジューリング時に各タスクキューの負荷を測定する負荷取得部９１１２が追加され、キュー選択部９１１１と接続される。なお、図３８に記載した並列処理システム９０２も、本願の発明者が非特許文献１の記載に基づいて想到したものである。
【００１４】
この場合のタスクスケジューリングの動作は、 図３９に示すように、未割り当てのタスクＴがあれば（ステップＳ１１１）、負荷取得部９１１２が各タスクキューの負荷を測定し（ステップＳ１２１）、キュー選択部９１１１が負荷最小のタスクキューＱを選択する（ステップＳ１２２）。エンキュー部１１２はタスク蓄積装置９１３から取り出したタスクＴをタスクキューＱに追加する（ステップＳ１１３）。
【００１５】
図３３、 図３５に示された、タスクをランダムもしくはサイクリックにタスクキューに割り当てる場合には、タスクの情報を必要とせず単純かつ低コストにタスクキューを選択することができる一方、タスクの処理量を考慮しないため、タスクキューの負荷が偏る可能性がある。しかし、図３８、図３９に示された負荷最小のタスクキューにタスクを追加する場合は、タスクキューの負荷を分散させることができるが、タスク実行前に各タスクの処理量が既知である必要があり、また、各タスクキューの負荷を調査し最小値を計算するオーバヘッドが発生するという課題がある。
【００１６】
以上に説明したように、タスクの処理量に周期的な相関があるタスク群をスケジューリングすると、非特許文献１の記載に基づいたシステムでは、タスクキューの負荷が偏るか、もしくは、スケジューリングオーバヘッドが大きくなるかとなり、並列処理効率が悪い。
【００１７】
本発明の目的は、上述したような課題を解決するために、タスクのスケジューリングにおけるオーバヘッドを低減しつつ、タスクキュー毎の負荷を分散することのできる情報処理システム、タスク制御方法及びタスク制御プログラムを提供することにある。
【課題を解決するための手段】
【００１８】
本発明の第１の態様にかかる情報処理システムは、複数タスクの処理量の大小における周期に基づいて、プロセッサ毎のタスクの処理量の総計を分散させるものである。
【００１９】
本発明の第２の態様にかかるタスク制御方法は、複数タスクの処理量の大小における周期に基づいて、プロセッサ毎のタスクの処理量の総計を分散させるものである。
【００２０】
本発明の第３の態様にかかるタスク制御プログラムは、複数タスクの処理量の大小における周期に基づいて、プロセッサ毎のタスクの処理量の総計を分散させるものである。
【発明の効果】
【００２１】
本発明の上述した各態様によれば、上述したような課題を解決するために、タスクのスケジューリングにおけるオーバヘッドを低減しつつ、タスクキュー毎の負荷を分散することのできる情報処理システム、タスク制御方法及びタスク制御プログラムを提供することができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の第１の実施の形態にかかる情報処理システムの構成図である。
【図２】本発明の第１の実施の形態にかかる並列処理システムの構成図である。
【図３】本発明の第１の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図４】本発明の第１の実施の形態におけるタスク番号と対応するキュー番号の例である。
【図５】本発明の第１の実施の形態によるスケジュール結果の例である。
【図６】本発明の第２の実施の形態にかかる情報処理システムの構成図である。
【図７】本発明の第２の実施の形態にかかる並列処理システムの構成図である。
【図８】本発明の第２の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図９】本発明の第２の実施例によるスケジュール結果の例である。
【図１０】本発明の第３の実施の形態にかかる並列処理システムの構成図である。
【図１１】本発明の第３の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図１２】本発明の第４の実施の形態にかかる並列処理システムの構成図である。
【図１３】本発明の第４の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図１４】本発明の第５の実施の形態にかかる情報処理システムの構成図である。
【図１５】本発明の第５の実施の形態にかかる並列処理システムの構成図である。
【図１６】本発明の第５の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図１７】本発明の第５の実施例によるスケジュール結果の例である。
【図１８】本発明の第６の実施の形態にかかる情報処理システムの構成図である。
【図１９】本発明の第６の実施の形態にかかる並列処理システムの構成図である。
【図２０】本発明の第６の実施の形態にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図２１】本発明の第６の実施の形態におけるタスク番号と対応するキュー番号の例である。
【図２２】本発明の第６の実施の形態によるスケジュール結果の例である。
【図２３】他の実施の形態にかかる並列処理システムの構成図である。
【図２４】他の実施の形態にかかる並列処理システムの構成図である。
【図２５】背景と同物体からなる画像の例である。
【図２６】背景と同物体の動きの大きさの例である。
【図２７】タスクとその処理量の例である。
【図２８】本発明の第２の実施の形態と第１の実施例の対応を示す表である。
【図２９】実施例にかかる並列処理システムの構成図である。
【図３０】実施例にかかる並列処理システムのタスクスケジューリングの動作例を示すフローチャートである。
【図３１】実施例における動作例を示す図である。
【図３２】実施例におけるスレッドブロック（プロセッサ）ごとの処理量の偏りを表したグラフである。
【図３３】非特許文献１の記載に基づいた並列処理システムの１つ目の構成例を示す構成図である。
【図３４】並列処理システムの動作例を示すフローチャートである。
【図３５】非特許文献１の記載に基づいた並列処理システムのタスクスケジューリングの１つ目の動作例を示すフローチャートである。
【図３６】スケジュールするタスクの例である。
【図３７】非特許文献１の記載に基づいた並列処理システムによるスケジュール結果の例である。
【図３８】非特許文献１の記載に基づいた並列処理システムの２つ目の構成例を示す構成図である。
【図３９】非特許文献１の記載に基づいた並列処理システムのタスクスケジューリングの２つ目の動作例を示すフローチャートである。
【発明を実施するための形態】
【００２３】
[第１の実施の形態] 
まず、図１を参照して、本発明の第１の実施の形態にかかる並列処理システムの概要となる情報処理システムについて説明する。図１は、本発明の第１の実施の形態にかかる情報処理システムの構成図である。
【００２４】
情報処理システム１００１は、タスクキュー８１、８２、・・・、８ｍ、タスク蓄積部１０１３、タスクキュー選択部１１１１及びエンキュー部１１１２を有する。
タスクキュー８１〜８ｍは、タスクを格納する。なお、ｍは、任意の正整数である。
タスク蓄積部１０１３は、それぞれの処理量が周期的に変化する複数のタスクを格納する。
タスクキュー選択部１１１１は、複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから選択する。
エンキュー部１１１２は、タスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１１１１が選択したタスクキューに格納する。
【００２５】
続いて、本発明の第１の実施の形態にかかる情報処理システムの動作について説明する。
タスクキュー選択部１１１１は、複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから選択する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクをタスクキューに格納する場合に、そのタスクを格納するタスクキューとしてタスクキュー選択部１１１１が選択したタスクキューに格納する。
【００２６】
続いて、本発明の第１の実施の形態にかかる並列処理システムについて説明する。図２は本発明の第１の実施の形態にかかる並列処理システムを示す構成図である。
【００２７】
図２に示されるように、本発明の第１の実施の形態における並列処理システム１は、スケジューリング装置１１、タスク処理量周期取得部１２、タスク蓄積装置１３と、並列演算装置１４と、複数のタスクキュー８１、８２、・・・、８ｍを有する。並列演算装置１４は、複数のプロセッサ１４１、１４２、１４３、・・・、１４ｎを含む。スケジューリング装置１１はキュー選択部１１１とエンキュー部１１２を含む。キュー選択部１１１とエンキュー部１１２は、相互に接続されている。なお、ｎ及びｍは、任意の正整数である。
【００２８】
スケジューリング装置１１は、タスク蓄積装置１３に格納されるタスクをスケジューリングする。
タスク処理量周期取得部１２は、タスク蓄積装置１３内のタスクから、タスク処理量周期を取得しキュー選択部１１１にタスク処理量周期を出力する。例えば、１周期における最初又は最後のタスクに、最初又は最後のタスクであることを示す情報を含めることによって、タスク処理量周期取得部１２がタスク処理量周期を判断して取得可能とする。また、例えば、任意の記憶装置にタスク処理量周期を示す情報を格納しておき、タスク処理量周期取得１２がこの情報を参照することでタスク処理量周期を取得できるようにしてもよい。なお、任意の記憶装置は、タスク蓄積装置１３であってもよく、タスク蓄積装置１３以外のメモリやハードディスク等の記憶装置であってもよい。
【００２９】
ここで、タスク処理量周期とは、一定タスク数で繰り返されるタスクの処理量の大小関係において、その繰り返されるタスク数である。つまり、タスク処理量周期取得部１２は、タスク蓄積装置１３に格納される複数のタスクの処理量の周期を、１周期に含まれるタスクのタスク数として取得する。ここで、タスクの処理量周期は、例えば、ユーザ入力など外部からの入力によって取得しても良い。具体的には、マウスやキーボード等の入力装置を情報処理システム１に備えるようにして、この入力装置によってユーザから入力されたタスク処理量周期を、タスク処理量周期取得部１２が参照する任意の記憶装置に格納するようにする。
【００３０】
タスク蓄積装置１３は、それぞれの処理量が周期的に変化する複数のタスクが格納される。タスク蓄積装置１３は、例えば、メモリやハードディスク等の記憶装置である。タスク蓄積装置１３は、例えば、図３６に例示するように、それぞれの処理量がタスク番号順に周期的に変化する複数のタスクを格納する。タスク番号とは、例えば、タスクが生成された順に、各タスクに割り当てられる番号である。また、タスクは、タスク蓄積装置１３に蓄積せずとも、タスクを生成する他の機器などから直接個々に取得しても良い。
【００３１】
並列演算装置１４は、タスクキュー８１〜８ｍに格納されたタスクを実行する。
タスクキュー８１〜８ｍは、プロセッサ１４１〜１４ｎによって実行されるタスクが格納される。
【００３２】
キュー選択部１１１は、タスク処理量周期取得部１２から入力された処理量周期から推測できるタスクの処理量が、タスクキュー毎に分散されるように、例えば、同一周期のタスクを同一キューに追加するようにタスクキューを選択し、選択されたタスクキューを示す情報をエンキュー部１１２に出力する。
エンキュー部１１２は、キュー選択部１１１から出力された情報に基づいて、キュー選択部１１１によって選択されたタスクキューにタスク蓄積装置１３から入力されたタスクを追加する。
【００３３】
プロセッサ１４１〜１４ｎは、それぞれタスクキュー８１〜８ｍのいずれかと対応付けられる。プロセッサ１４１〜１４ｎは、自身と対応づけられたタスクキュー８１〜８ｍからタスクを取得して実行する。図２では、タスクキュー７１とプロセッサ１４１、１４２が対応付けられ、タスクキュー７２とプロセッサ１４３が対応付けられ、タスクキュー７ｍとプロセッサ１４ｎが対応付けられている場合について例示している。
【００３４】
次に、 図３のフローチャートを参照して本実施の形態のタスクスケジューリングの動作について詳細に説明する。
【００３５】
タスク処理量周期取得部１２はタスク蓄積装置１３からタスク処理量周期を取得し、取得したタスク処理量周期をキュー選択部１１１に出力する（ステップＳ１）。エンキュー部１１２は、タスク蓄積装置１３にタスクキューに未割り当てのタスクＴがあるかを判断する（ステップＳ２）。言い換えると、タスクキューに未格納のタスクＴがあるか否かを判断する。エンキュー部１１２は、例えば、タスク番号順に未割り当てのタスクＴがあるか否かを判断する。エンキュー部１１２は、未割り当てのタスクＴがあった場合、タスク蓄積装置１３からタスクＴを取得する。
【００３６】
ここで、例えば、タスク蓄積装置１３にタスクキューに未割り当てのタスクを格納するようにしている場合、エンキュー部１１１は、タスク蓄積装置１３にタスクが格納されているか否かを判断する。また、例えば、全てのタスクのそれぞれについて、タスクがタスクキューに割り当てられているか否かを示す情報をタスク蓄積装置１３に格納している場合は、エンキュー部１１１は、その情報を参照して判断する。
【００３７】
キュー選択部１１１は、エンキュー部１１２によって未割り当てのタスクＴがあると判断された場合、タスク処理量周期取得１２から入力されたタスク処理量周期を考慮してキュー毎の処理量が偏らないキューＱを選択する（ステップＳ３）。ステップＳ３において、キュー選択部１１１は、例えば、同一周期のタスクを同一タスクキューに追加するように、つまりタスクＴが一つ前のタスクと異なる周期になるまでは同じタスクキューを選択し続ける。
【００３８】
具体的には、エンキュー部１１２は、未割り当てのタスクＴのタスク番号をキュー選択部１１１に出力する。キュー選択部１１１は、エンキュー部１１２から出力されたタスクＴのタスク番号が同一の１周期に含まれ続けている間は、同一のタスクキューを選択し続ける。つまり、図３６に例示するように、タスク処理量周期が１２である場合、エンキュー部１１２から出力されるタスク番号が１〜１２までの間は、同一のタスクキューを選択し続ける。そして、キュー選択部１１１は、選択したタスクキューＱを示す情報をエンキュー部１１２に出力する。
【００３９】
エンキュー部１１２は、タスクＴをキュー選択部１１１により選択されたタスクキューＱに追加する（ステップＳ４）。具体的には、エンキュー部１１２は、キュー選択部１１１から出力された情報が示すタスクキューＱにタスクＴを格納する。キュー選択部１１１及びエンキュー部１１２は、ステップＳ２からステップＳ４をタスク蓄積装置１３に未割り当てのタスクがなくなるまで実行する。
【００４０】
次に、本実施の形態の効果について説明する。本実施の形態では、タスク処理量周期情報を用いて新たなタスクを追加するタスクキューを決定する。これにより、各タスクの処理量がわからずとも、タスク処理量周期を考慮しない場合に比べて負荷が分散される。また、負荷分散を行った結果、全タスクの並列処理時間を短縮することができる。
【００４１】
例えば、図３６に示された周期的に処理量の大小に相関のあるタスクをスケジュールする場合、非特許文献１に基づいた並列処理システム９０１のように、タスク処理量周期を考慮せずにタスクを追加するタスクキューをサイクリックに決定すると、図３７に示すようにタスクキュー毎のタスクの処理量の合計が大きく異なり、偏りが大きい。なお、図３７は、各タスクキューに、図３６に示す複数のタスクがタスク番号１のタスクからタスク番号順にタスクキューに追加された場合について例示している。
【００４２】
これに対して、本実施の形態によりタスクの処理量周期を考慮して図３６に示されるタスクをスケジュールすると、タスクキュー毎のタスク処理量の偏りを小さくすることができる。例えば、前記で述べたように、 図４に示すようにタスクの周期ごとに選択するタスクキューを変えることで、スケジューリング結果は図５に示すようにひとつのタスクキューに処理量の多いタスクが集中することがなくなり、タスクキュー毎の負荷が分散できる。
【００４３】
キュー選択部１１１は、例えば、図５に示すように、１周期毎にサイクリックにタスクキューを選択する。また、キュー選択部１１１によるタスクキューの選択方法は、１周期毎に規則的にタスクキューを選択する方法であれば、サイクリックに選択する方法に限られない。例えば、図５のように４つのタスクキューがある場合において、１周期毎にタスクキュー１、３、２、４、１、３、・・・の順にタスクキューを選択するようにしても、各タスクキューにおける負荷を分散することができる。
【００４４】
また、本実施の形態によれば、タスクをタスクキューに追加する場合に、負荷が最小となっているタスクキューを調査することなく、タスクキューの負荷を分散することができる。したがって、タスクキューの負荷を計算するオーバヘッドを発生させることがない。
【００４５】
[第２の実施の形態]
まず、図６を参照して、本発明の第２の実施の形態にかかる並列処理システムの概要となる情報処理システムについて説明する。図６は、本発明の第２の実施の形態にかかる情報処理システムの構成図である。
【００４６】
情報処理システム１００２は、タスクキュー８１、８２、・・・、８ｍ、タスク蓄積部１０１３、タスクキュー数決定部１０２１、エンキュー部１１１２及びタスクキュー選択部１２２１を有する。なお、ｍは、タスクキュー数決定部１０２１によって決定される任意の正整数である。
【００４７】
タスクキュー８１〜８ｍは、タスクを格納する。
タスク蓄積部１０１３は、それぞれの処理量が周期的に変化する複数のタスクを格納する。
タスクキュー数決定部１０２１は、複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように複数のタスクキュー８１〜８ｍのタスクキュー数を決定する。
エンキュー部１１１２は、タスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１１１１が選択したタスクキューに格納する。
タスクキュー選択部１２２１は、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから規則的に選択する。
【００４８】
続いて、本発明の第２の実施の形態にかかる情報処理システムの動作について説明する。
タスクキュー数決定部１０２１は、複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように複数のタスクキュー８１〜８ｍのタスクキュー数を決定する。
タスクキュー選択部１２２１は、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから規則的に選択する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１２２１が選択したタスクキューに格納する。
【００４９】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。図７に示されるように、本発明の第２の実施の形態における並列処理システム２は、タスク処理量周期取得部１２と、タスク蓄積装置１３と、並列演算装置１４と、キュー数決定部２１と、スケジューリング装置２２と、複数のタスクキュー８１、８２、・・・、８ｍを有する。スケジューリング装置２２は、キュー選択部２２１と、エンキュー部１１２を含む。タスクキュー数ｍは可変であり、キュー数決定部２１によって決められる。第１の実施の形態と同様の構成要素については、同一の符号を付し、詳細な説明を省略する。
【００５０】
キュー数決定部２１は、タスク処理量周期取得部１２が出力したタスク処理量周期を入力とし、タスク処理量周期の約数や倍数と異なるタスクキュー数ｍを決定する。例えば、 図３６に示すようにタスク処理量周期が１２であれば、タスクキュー数ｍは約数でも倍数でもでない例えば５と設定する。
【００５１】
スケジューリング装置２２は、タスク蓄積装置１３に格納されるタスクを規則的にスケジューリングする。
キュー選択部２２１は、タスクを割り当てるタスクキューを規則的に選択する。キュー選択部２２１は、例えば、タスクキュー数ｍが５の場合、次のタスクを割り当てるタスクキューを８１、８２、８３、８４、８５、８１・・・のようにサイクリックに決定する。キュー選択部２２１は、例えば、タスク番号順にサイクリックにタスクを割り当てるタスクキューを選択する。また、キュー選択部２２１は、タスク毎に、選択したタスクキューを示す情報をエンキュー部１１２に出力する。
【００５２】
図８は、本発明の第２の実施の形態における並列処理システム２のタスクスケジューリングの動作の一例を示すフローチャートである。
【００５３】
まず、タスク処理量周期取得部１２はタスク蓄積装置１３からタスクの処理量周期を取得し、キュー数決定部２１に出力する（ステップＳ１１）。キュー数決定部２１はタスクの処理量周期からタスクの処理量周期の約数や倍数と異なるタスクキュー数ｍを決定する（ステップＳ１２）。エンキュー部１１２は、未割り当てのタスクＴがあるかを判断する（ステップＳ３）。エンキュー部１１２によって未割り当てのタスクＴがあると判断された場合、キュー選択部２２１は、タスクキューをサイクリックに選択する（ステップＳ１３）。エンキュー部１１２は、タスクＴを選択されたタスクキューに追加する（ステップＳ４）。
【００５４】
次に、本実施の形態の効果について説明する。本実施の形態では、タスクキュー数を、タスク処理量周期の約数や倍数と異なる数にすることにより、タスクを追加するタスクキューはサイクリックに選択するだけで、タスクキューに入っているタスクと新たにタスクキューに入れるタスクの位相を違えることができる。これにより、スケジュール時にタスクの周期や位相を考慮することなく負荷分散を行うことができる。スケジュール時にタスクの位相を考慮してタスク割り当てタスクキューを決定する必要がないため、スケジュールオーバヘッドを削減することができる。
【００５５】
例えば、図３６のようにタスク処理量周期が１２である場合に、タスクキュー数ｍを１２の約数である４としてサイクリックにタスクキューを選択すると図３７に示すようにタスクキュー毎の処理量が偏るが、タスクキュー数ｍを 図９に示すように１２の約数でも倍数でもではない５とするとサイクリックにタスクキューを選択してもタスクキュー毎の処理量の偏りは小さくなる。つまり、タスクキュー毎の負荷を分散することができる。
【００５６】
また、タスクキューの選択は、サイクリックではなくとも規則的であれば、同様にキュー毎の負荷を分散することができる。例えば、タスクキュー数ｍが５の場合、タスクを割り当てるタスクキューを８１、８３、８５、８２、８４、８１、８３・・・の順に規則的に選択するようにしてもよい。
【００５７】
また、本実施の形態によれば、タスクをタスクキューに追加する場合に、負荷が最小となっているタスクキューを調査することなく、タスクキューの負荷を分散することができる。したがって、タスクキューの負荷を計算するオーバヘッドを発生させることがない。
【００５８】
[第３の実施の形態] 
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。図１０に示されるように本発明の第３の実施の形態における並列処理システム３は、タスク処理量周期取得部１２と、タスク蓄積装置１３と、並列演算装置１４と、スケジューリング装置２２と、キュー数決定部３１と、プロセッサ数取得部３３と、複数のタスクキュー８１、８２、・・・、８ｍを有する。なお、第２の実施の形態と同様の構成要素については、同一の符号を付し、詳細な説明を省略する。
【００５９】
第３の実施の形態では、キュー数決定部３１は、タスク処理量周期取得部１２から得られるタスク処理量周期に加えて、プロセッサ数取得部３３からプロセッサ数が入力されることが第２の実施の形態との違いである。キュー数決定部３１は、タスクの周期の約数や倍数と異なり、かつ、プロセッサ数の約数又は倍数と、同一又は近い数を優先してタスクキュー数ｍとする。例えば、図３６に示すようにタスク処理量周期が１２であり、また、プロセッサ数が８であれば、タスクキュー数ｍは、タスク処理量周期１２の約数でも倍数でもなく、プロセッサ数８の約数に近い、例えば５と設定する。
【００６０】
プロセッサ数取得部３３は、プロセッサ数を取得して、取得したプロセッサ数をキュー数決定部３１に出力する。ここで、任意の記憶装置にプロセッサ数を示す情報を格納しておき、プロセッサ数取得部３３がこの情報を参照することで、プロセッサ数を取得できるようにしてもよい。また、入力装置を情報処理システム１に備えるようにして、この入力装置によってユーザから入力されたプロセッサ数を、プロセッサ数取得部３３が参照する任意の記憶装置に格納するようにしてもよい。
【００６１】
図１１は、本発明を実施するための第３の実施の形態における並列処理システム３のタスクスケジューリングの動作の一例を示すフローチャートである。
【００６２】
タスク処理量周期取得部１２はタスクの処理量周期を取得し（ステップＳ１１）、取得したタスク処理量周期をキュー数決定部３１に出力する。プロセッサ数取得部３３はプロセッサ数を取得し（ステップＳ２１）、取得したプロセッサ数をキュー数決定部３１に出力する。キュー数決定部３１は、タスクの周期の約数や倍数と異なり、かつプロセッサ数の約数と同一又は近いタスクキュー数を決定する（ステップＳ２２）。他のステップは第２の実施の形態と同様であるため、説明を省略する。
【００６３】
次に、本実施の形態の効果について説明する。本実施の形態では、タスク処理量周期の約数や倍数と異なり、かつプロセッサ数の約数又は倍数と、同一又は近い数にタスクキュー数を決定し、タスクを追加するタスクキューをサイクリックに選択する。これにより、スケジュール時にタスクの位相を考慮することなくタスクキューとタスクの位相を違えることができ、かつ、１つのタスクキューを共有するプロセッサ数を均等化することができるため、タスクキュー間の負荷分散を行うことができる上に、プロセッサの性能が全て同等であればプロセッサ間の負荷分散も可能になる。
【００６４】
[第４の実施の形態] 
次に、本発明の第４の発明を実施するための最良の形態について図面を参照して詳細に説明する。図１２に示されるように本発明の第４の実施の形態における並列処理システム４は、タスク処理量周期取得部１２と、タスク蓄積装置１３と、並列演算装置１４と、プロセッサ数取得部３３と、スケジューリング装置２２と、キュー数決定部４１と、タスク数取得部４４と、複数のタスクキュー８１、８２、・・・、８ｍを有する。なお、第３の実施の形態と同様の構成要素については、同一の符号を付し、詳細な説明を省略する。
【００６５】
第４の実施の形態では、キュー数決定部４１は、タスク処理量周期取得部１２から入力されるタスク処理量周期とプロセッサ数取得部３３から入力されるプロセッサ数に加えて、タスク数取得部４４からタスク数が入力されることが第３の実施の形態との違いである。キュー数決定部４１は、タスクの処理量周期の約数や倍数と異なり、プロセッサ数の約数又は倍数と、同一又は近く、さらにタスク数の約数と同一又は近い数を優先してタスクキュー数ｍとする。
タスク数取得部４４は、タスク蓄積装置１３に格納されるタスクを参照することによって、タスク蓄積装置１３に格納されているタスクのタスク数を取得する。タスク数取得部４４は、取得したタスク数をキュー数決定部に出力する。
【００６６】
図１３は、本発明を実施するための第４の実施の形態における並列処理システム４のタスクスケジューリングの動作の一例を示すフローチャートである。
【００６７】
タスク処理量周期取得部１２はタスクの処理量周期を取得し（ステップＳ１１）、取得したタスク処理量周期をキュー決定部４１に出力する。プロセッサ数取得部３３はプロセッサ数を取得し（ステップＳ２１）、取得したプロセッサ数をキュー決定部４１に出力する。タスク数取得部４４はタスク数を取得し（ステップＳ３１）、取得したタスク数をキュー数決定部４１に出力する。キュー数決定部４１は、タスクの周期の約数や倍数と異なり、プロセッサ数の約数又は倍数と、同一又は近く、さらにタスク数の約数と同一又は近いキュー数ｍを決定する（ステップＳ３２）。他のステップは第３の実施の形態と同様であるため、説明を省略する。
【００６８】
次に、本実施の形態の効果について説明する。本実施の形態では、タスク処理量周期と異なり、プロセッサ数の約数に近く、タスク数の約数に近い数にタスクキュー数を決定し、タスクを追加するタスクキューをサイクリックに選択する。これにより、スケジュール時にタスクの位相を考慮することなくタスクキューとタスクの位相を違えることができ、かつ、１つのタスクキューを共有するプロセッサ数を均等化することができる上に、タスクキューあたりのタスク数も均等化できるため、第３の実施の形態の効果に加えて、よりタスクキュー毎の処理量が分散できる。
【００６９】
[第５の実施の形態] 
まず、図１４を参照して、本発明の第５の実施の形態にかかる並列処理システムの概要となる情報処理システムについて説明する。図１４は、本発明の第５の実施の形態にかかる情報処理システムの構成図である。
【００７０】
情報処理システム１００５は、タスクキュー８１、８２、・・・、８ｍ、タスク蓄積部１０１３、エンキュー部１１１２、タスクキュー履歴記憶部１０５３及びタスクキュー選択部１５２１を有する。なお、ｍは、任意の正整数である。
【００７１】
タスクキュー８１〜８ｍは、それぞれの処理量が周期的に変化する複数のタスクを格納する。
タスク蓄積部１０１３は、タスクを格納する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１５２１が選択したタスクキューに格納する。
タスクキュー履歴記憶部１０５３は、複数のタスクキューのそれぞれについて、これらのタスクキューが格納先として選択されたタスクの位相の履歴を示すタスクキュー履歴情報を格納する。
【００７２】
タスクキュー選択部１５２１は、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから選択する。タスクキュー選択部１５２１は、タスクを格納するタスクキューを選択する場合に、タスクキュー履歴記憶部１０５３に格納されたタスクキュー履歴情報に基づいて、格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択する。また、タスクキュー選択部１５２１は、タスクキューの選択結果に基づいて、タスクキュー履歴記憶部１０５３に格納される履歴情報を更新する。
【００７３】
続いて、本発明の第５の実施の形態にかかる情報処理システムの動作について説明する。
タスクキュー選択部１５２１は、タスクキュー履歴記憶部１０５３に格納されたタスクキュー履歴情報に基づいて、格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択する。そして、タスクキュー選択部１５２１は、タスクキューの選択結果に基づいて、タスクキュー履歴記憶部１０５３に格納される履歴情報を更新する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１５２１が選択したタスクキューに格納する。
【００７４】
次に、本発明の第５の実施の形態について図面を参照して詳細に説明する。図１５に示されるように本発明の第５の実施の形態における並列処理システム５は、タスク処理量周期取得部１２と、タスク蓄積装置１３と、並列演算装置１４と、タスク処理量位相算出部５１と、スケジューリング装置５２と、選択キュー記憶装置５３と、複数のタスクキュー８１、８２、・・・、８ｍを有する。スケジューリング装置５２は、キュー選択部５２１と、エンキュー部１１２を含む。なお、ｍは、任意の正整数である。なお、第１の実施の形態と同様の構成要素については、同一の符号を付し、詳細な説明を省略する。
【００７５】
第５の実施の形態におけるキュー選択部５２１は、キュー選択部５２１と接続された選択キュー記憶装置５３に記憶された選択キュー履歴情報を用いて選択するタスクキューを決定することが第１の実施の形態との違いである。
タスク処理量位相算出部５１は、タスク処理量周期取得部１２から入力されたタスク処理量周期に基づいて、タスクキューに追加するタスクのタスク処理量位相を算出し、キュー選択部５２１に出力する。
【００７６】
選択キュー記憶装置５３は、タスクのタスク処理量位相と、そのタスクの格納先として選択されたタスクキューとの組み合わせを示す情報を格納する。つまり、選択キュー記憶装置５３に格納される情報は、タスクキュー８１〜８ｍのそれぞれについて、タスクキューを格納先として選択したタスクの位相の履歴を示す選択キュー履歴情報となる。
キュー選択部５２１は、タスク処理量周期取得部１２から入力されたタスク処理量周期と、タスク処理量位相算出部５１から入力されたタスク処理量位相と、選択キュー記憶装置５３から入力された選択キュー履歴情報を考慮しながら、タスクキューを選択する。
【００７７】
図１６は、本発明を実施するための第５の実施の形態における並列処理システム５のタスクスケジューリングの動作の一例を示すフローチャートである。
【００７８】
まず、タスク処理量周期取得部１２はタスク蓄積装置１３からタスクの処理量周期を取得し（ステップＳ４１）、取得したタスク処理量周期をタスク処理量位相算出部５１に出力する（ステップＳ４１）。エンキュー部１１２は、未割り当てのタスクＴがあるかを判断する（ステップＳ３）。エンキュー部１１２によって未割り当てのタスクＴがあると判断された場合、タスク処理量位相算出部５１はタスク処理量周期取得部１２から出力されたタスク処理量周期に基づいて、タスクＴのタスク処理量位相を算出する（ステップＳ４２）。タスク処理量算出部５１は、算出したタスク処理量位相をキュー選択部５２１に出力する。
【００７９】
具体的には、キュー選択部５２１は、タスクＴを割り当てるタスクキューを選択するときに、タスクＴのタスク番号をタスク処理量位相算出部５１に出力する。タスク処理量位相算出部５１は、タスク処理量周期と、キュー選択部５２１から出力されたタスク番号に基づいて、タスク処理量位相を算出する。タスク処理量位相は、１周期におけるタスクの位置を示す情報である。例えば、図３６に例示するようなタスクの場合、タスク処理量周期が１２であるため、タスク処理量位相は１〜１２で表される。例えば、タスク番号が１４のタスクは、タスク処理量位相は２となる。タスク処理量位相算出部５１は、算出したタスクＴのタスク処理量位相をキュー選択部５２１に出力する。
【００８０】
キュー選択部５２１は、選択キュー記憶装置５３を参照し、次にタスクキューを割り当てるタスクＴと同位相のタスクが少ないタスクキューを選択する（ステップＳ４３）。具体的には、タスク処理量位相算出部５１から出力されたタスクＴのタスク処理量位相と、同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択する。よって、選択キュー記憶装置５３に格納される情報は、どの位相のタスクがどのタスクキューに何回格納されたかが分かる情報であれば、上述した情報に限られない。例えば、タスクキュー８１〜８ｍのそれぞれについて、タスクキューを格納先として選択したタスクの位相を、位相毎にカウントした情報であってもよい。
【００８１】
ステップＳ４３は、例えば、 図３６に示されるタスクを図１７に示すように４つのタスクキューにスケジュールする場合、１周期目のタスク１乃至１２を追加するタスクキューをサイクリックに選択すると、２周期目のタスク１３を追加するタスクキューとして、同位相のタスクがすでに入っているタスクキュー１を避け、同位相のタスクが入っていないタスクキュー２を選択する。ここで、タスクキューの選択方法は、タスクＴと同一位相のタスクが格納先として選択された回数が少ないタスクキューを選択する方法であれば、これに限られない。つまり、１周期の最初のタスク以外のタスクについても、そのタスクと同位相のタスクが選択された回数が少ないタスクキューを選択するようにしてもよい。例えば、図１７に示すように４つのタスクキュー１〜４がある場合に、１周期目のタスク２を追加するタスクキューとしてタスクキュー２を選択したときは、２週目のタスク１４は、タスクキュー１、３、４のいずれかから選択するようにしてもよい。
【００８２】
そして、エンキュー部１１２は、キュー選択部５２１によって選択されたタスクキューにタスクを追加する（ステップＳ４）。キュー選択部１１２は、タスクＴの位相とタスクキューＱの組み合わせを、選択キュー記憶装置５３に保存する（ステップ４４）。
【００８３】
次に、本実施の形態の効果について説明する。本実施の形態では、タスクキューへ追加されたタスクの位相の履歴をもとに新たなタスクを割り当てるタスクキューを決定するので、容易にタスクキュー毎の負荷分散が行える。本実施の形態によりスケジューリングされた 図３６のタスクの例を図１７に示す。また、本実施の形態では、選択キュー履歴情報により、同様の処理量となる同位相のタスクが特定のタスクキューに偏らないようにすることができる。そのため、タスクキュー毎の負荷を分散することができる。
【００８４】
また、非特許文献１に基づいた並列処理システム９２２のようにタスクキューの負荷（処理量）を計測しながらタスクキューを選択するのではないため、タスクキューを選択するコストも小さく、また各タスクの処理量がわからずともタスクキュー毎の負荷分散を行うことができる。つまり、タスクキューの負荷を計算するオーバヘッドを発生させることがない。
【００８５】
[第６の実施の形態] 
まず、図１８を参照して、本発明の第６の実施の形態にかかる並列処理システムの概要となる情報処理システムについて説明する。図１８は、本発明の第６の実施の形態にかかる情報処理システムの構成図である。
【００８６】
情報処理システム１００６は、タスクキュー８１、８２、・・・、８ｍ、タスク蓄積部１０１３、エンキュー部１１１２及びタスクキュー選択部１６２１を有する。なお、ｍは、任意の正整数である。
【００８７】
タスクキュー８１〜８ｍは、それぞれの処理量が周期的に変化する複数のタスクを格納する。
タスク蓄積部１０１３は、タスクを格納する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１６２１が選択したタスクキューに格納する。
タスクキュー選択部１６２１は、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから規則的に選択する。タスクキュー選択部１６２１は、複数のタスクのそれぞれの処理量が周期的に変化する場合に、１周期における最初のタスクを格納するタスクキューとして、その１周期の前の１周期における最初のタスクとは異なるタスクキューを選択する。
【００８８】
続いて、本発明の第６の実施の形態にかかる情報処理システムの動作について説明する。
タスクキュー選択部１６２１は、タスクを格納するタスクキューを複数のタスクキュー８１〜８ｍから規則的に選択する。このとき、タスクキュー選択部１６２１は、格納先のタスクキューを選択するタスクが、１周期における最初のタスクを格納するタスクキューとして、当該１周期の前の１周期における最初のタスクとは異なるタスクキューを選択する。
エンキュー部１１１２は、タスク蓄積部１０１３に格納されるタスクを、そのタスクを格納するタスクキューとしてタスクキュー選択部１６２１が選択したタスクキューに格納する。
【００８９】
次に、本発明の第６の実施の形態について図面を参照して詳細に説明する。本発明を実施するための第６の実施の形態における並列処理システム６の構成を図１９に示す。並列処理システム６は、タスク処理量周期取得部１２と、タスク蓄積装置１３と、並列演算装置１４と、スケジューリング装置６２と、タスクキュー８１〜８ｍを有する。スケジューリング装置６２は、エンキュー部１１２と、キュー選択部６２１を含む。なお、ｍは、任意の正整数である。なお、第１の実施の形態と同様の構成要素については、同一の符号を付し、詳細な説明を省略する。
【００９０】
第６の実施の形態におけるキュー選択部６２１は、タスク処理量周期取得部１２から得られるタスクの処理量周期が入力される。キュー選択部６２１は、タスク処理量周期取得部１２から入力されたタスク処理量周期をタスクキューの選択に使用する。キュー選択部６２１は、タスクを割り当てるタスクキューを規則的に選択する。また、キュー選択部６２１は、１周期における最初のタスクを割り当てるタスクキューを選択する場合、その１周期の前の１周期における最初のタスクとは異なるタスクキューを選択する。
【００９１】
図２０は、本発明を実施するための第６の実施の形態における並列処理システム６のタスクスケジューリングの動作の一例を示すフローチャートである。
【００９２】
まず、タスク処理量周期取得部１２はタスク処理量周期をタスク蓄積装置１３から取得する（ステップＳ１）。タスク処理量周期取得部１２は、取得したタスク処理量周期をキュー選択部６２１に出力する。キュー選択部６２１は変数ｓを−１に、ｉを０に初期化する（ステップＳ５１）。エンキュー部１１２は、未割り当てのタスクＴがあるかを判断する（ステップＳ３）。
【００９３】
エンキュー部１１２が未割り当てのタスクＴがあると判断（ステップＳ３）したら、キュー選択部６２１はタスク処理量周期取得部１２より入力されたタスク処理量周期からタスクＴが周期の開始かを判断する（ステップＳ５２）。具体的には、エンキュー部１１２は、未割り当てのタスクＴのタスク番号をキュー選択部１１１に出力する。キュー選択部６２１は、エンキュー部１１２から出力されたタスクＴのタスク番号が１周期における最初のタスクか否かを判断する。つまり、図３６に例示するように、タスク処理量周期が１２である場合、エンキュー部１１２から出力されるタスク番号が１、１３、２５、・・・等であるか否かを判断する。
【００９４】
タスクＴが周期の開始タスクであれば、変数ｓをインクリメントし、変数ｉを０にする（ステップＳ５３）。開始タスクでなければ変数ｉをインクリメントする（ステップＳ５４）。そして、［(ｓ＋ｉ)をタスクキュー数で割った余り＋１］番目のタスクキューＱを選択する（ステップＳ５５）。エンキュー部１１２はタスクキューＱにタスクＴを追加する（ステップＳ４）。つまり本実施の形態では、 図２１に示すように、毎周期ごとに周期開始のタスクを割り当てるタスクキューをずらし、サイクリックにタスクを割り当てる。
【００９５】
次に、本実施の形態の効果について説明する。本実施の形態では、周期開始のタスクを割り当てるキューを周期ごとに変え、残りのタスクはサイクリックに割り当てることで、タスクキュー数によらず、同位相のタスクを偏ったタスクキューに割り当てることがなく、タスクキュー毎の負荷が分散できる。本実施の形態により、図３６に示すタスクをスケジューリングした例を図２２に示す。また、タスクキューの選択は、サイクリックではなくとも規則的であれば、同様にキュー毎の負荷を分散することができる。
【００９６】
また、本実施の形態によれば、タスクをタスクキューに追加する場合に、負荷が最小となっているタスクキューを調査することなく、タスクキューの負荷を分散することができる。したがって、タスクキューの負荷を計算するオーバヘッドを発生させることがない。
【００９７】
以上、これまで述べてきた各実施の形態は、本発明の好適な実施形態であり、前記実施の形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。例えば、図２３に示すように、タスクキューを用いずに、スケジューリング装置が直接プロセッサへ処理するタスクを指示しても良い。これは、タスクキューとプロセッサ数が同数であるのと同義である。
【００９８】
また、例えば、図２４に示すように、独立したスケジューリング装置を用いずに、並列演算装置１４内のプロセッサ１４１〜１４ｎが、各々タスク処理量周期取得部１２が得たタスク処理量周期をもとに処理するタスクを決定し、処理を行っても良い。具体的には、例えば、タスク処理量周期取得部１２は、タスク処理量周期をプロセッサ１４１〜１４ｎが有する処理タスク決定部１４１２〜１４ｎ２に出力するようにする。処理タスク決定部１４１２〜１４ｎ２は、タスク処理量周期取得部１２から出力されたタスク処理量周期に基づいて、処理するタスクを決定する。処理タスク決定部１４１２〜１４ｎ２は、決定したタスクのタスク番号をタスク処理演算部１４１１〜１４ｎ１に出力する。タスク処理演算部１４１１〜１４ｎ１は、処理タスク決定部１４１２〜１４ｎ２から出力されたタスク番号のタスクをタスク蓄積装置１３から取得して処理する。なお、後述する実施例では、図２４に示すように、独立したスケジューリング装置を用いずに並列演算装置内のプロセッサが処理するタスクを決定している。
【００９９】
なお本発明は、コンピュータを並列処理システムとして機能させる並列処理プログラムとしても実現することができる。コンピュータは、並列処理スケジューリングプログラムが記憶媒体から読み込まれ実行される中央演算処理装置（ＣＰＵ(Central Processing Unit)）や画像演算処理装置(ＧＰＵ(Graphics Processing Unit))などの演算処理装置を備える。本発明の第１の実施の形態を例にとれば、ＣＰＵに読み込まれた並列処理プログラムは、コンピュータを第１の実施の形態において説明された、タスク処理量周期取得部やキュー選択部、エンキュー部として機能させる。即ちこの場合、ＣＰＵ（不図示）は、図３に示すフローチャートに対応するソフトウェアプログラムを実行することにより、上述した第１の実施形態において説明した並列処理システム１の機能を実現することになる。
【０１００】
また、上述したプログラムは、様々なタイプの非一時的なコンピュータ可読媒体(non-transitory computer readable medium)を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体(tangible storage medium)を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体(例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ)、光磁気記録媒体(例えば光磁気ディスク)、ＣＤ−ＲＯＭ(Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ(例えば、マスクＲＯＭ、ＰＲＯＭ(Programmable ROM）、ＥＰＲＯＭ(Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ(Random Access Memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体(transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【０１０１】
また、コンピュータが上述の実施の形態の機能を実現するプログラムを実行することにより、上述の実施の形態の機能が実現されるだけではなく、このプログラムの指示に基づき、コンピュータ上で稼動しているＯＳ(Operating System)もしくはアプリケーションソフトウェアと共同して上述の実施の形態の機能が実現される場合も、発明の実施の形態に含まれる。
【０１０２】
さらに、このプログラムの処理の全てもしくは一部がコンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットにより行われて上述の実施の形態の機能が実現される場合も、発明の実施の形態に含まれる。
【実施例】
【０１０３】
本発明を実施するための実施例を第３の実施の形態と対応付けて説明する。本実施例では、動画像の動き探索処理を行うアプリケーションプログラムを実行する場合について例示する。このアプリケーションプログラムは、並列処理される複数のタスクを含む。各タスクは、１６×１６画素の領域である１マクロブロックの動き探索処理である。
【０１０４】
また、本実施例における並列処理はＧＰＵで実行される。ＧＰＵの統合開発環境であるＮＶＩＤＩＡ社のＣＵＤＡ(Compute Unified Device Architecture)プログラミングモデルでは、最小処理単位である"スレッド"を複数まとめた"スレッドブロック"と呼ばれる単位で、ＳＭ(Streaming Multiprocessor)と呼ばれる演算処理ユニットに割り当てられる。複数のスレッドブロックがＳＭ上で同時に動作するため、スレッドブロック数が実際の並列実行数であると言える。よって、本実施例におけるスレッドブロックは、図１０におけるプロセッサに相当する。
【０１０５】
動き探索処理は対応するマクロブロックにおける画像がどれくらい移動したかを検出する処理で、マクロブロック毎に処理量が異なる。画像は、空間的に連続している部分は似ていることが多い。そのため、動き探索処理では空間的に連続しているマクロブロックの処理量相関が高い、つまり行方向と列方向に連続したマクロブロックの処理量には相関があることが多い。１つのマクロブロックにおける探索処理を１つのタスクで実行し、行と列方向にタスクが順序付けられているとすると、同一列（行）のタスクは相関があり、これは周期的である。
【０１０６】
例えば、図２５に示すような背景と動物体の画像では、図２６の斜線部分である動物体は、空間的に近いマクロブロック群で構成され、また、動きが大きいため動き探索の処理量が多い。一方、それ以外のマクロブロックである背景は、動きが小さく、動き探索の処理量も少ない。背景と動物体の動きの大きさを矢印の大きさとし、動きの方向を矢印の向きとして図２６中に示す。行と列の順にマクロブロックが順序付けられているとすると、マクロブロック列数がタスク処理量の周期となり、図２６の各タスクの処理量を順に表すと 図２７に示すように、周期的に処理量の大きいタスクが現れる。
【０１０７】
具体的に例えると、１行目１列目のマクロブロックに対応するタスクのタスク番号は１、１行目２列目のマクロブロックに対応するタスクのタスク番号は２、・・・となる。以降、列番号が増える毎に、マクロブロックに対応するタスク番号が増加していく。よって、列数が１２０の場合、２行目１列目のマクロブロックに対応するタスクのタスク番号は１２１となる。
【０１０８】
図２７に例示するような動画像の場合、同行や同列のタスクを同タスクキューに割り当てると、動物体部分を処理するタスクが同タスクキューとなり、他タスクキューと比べて処理量が多い。このような場合には、同行や同列のタスクをなるべく同タスクキューに入れないことでタスクキュー間の負荷が分散でき、並列処理効率が向上する。そのため、本発明の実施の形態３を適用した本実施例によれば、タスクキュー数をマクロブロック列数の約数や倍数ではなく、スレッドブロック数の約数と同一又は近い数にし、タスクキューにタスクをサイクリックに割り当てることができるので、行と列に連続したタスクが連続して同一タスクに入ることがなく、タスクキュー毎の負荷を分散できる。
【０１０９】
また、図１０におけるタスクキューは、実際にタスクを格納する配列などを用いるのではなく、各プロセッサから排他的にアクセスされるカウンタを用いて実装してもよい。このようなカウンタの値は処理するマクロブロック（タスク）番号を表す。各カウンタの初期値はカウンタ番号に一致し、処理すべきタスクを取り出したプロセッサによって、カウンタ数（タスクキュー数）が加算される。これにより、タスクキューにサイクリックにタスクが割り当たるのと同じ状態となる。つまり、本発明の実施の形態において、カウンタにタスク番号を格納することも、タスクキューにタスクを格納することに含まれる。
【０１１０】
実施の形態３の並列処理システム２と本実施例の対応を図２８に示す。
本実施例の構成を図２９に示す。本実施例である並列処理システム７は、マクロブロック列数を取得するマクロブロック列数取得部７４と、スレッドブロック数を取得するスレッドブロック数取得部７５と、マクロブロック列数とスレッドブロック数からカウンタ数ｍを決定するカウンタ数決定部７１と、ｍ個のカウンタ７２１１、７２１２、・・・、７２１ｍと、ｎ個のスレッドブロック７２２１、７２２２、７２２３、・・・、７２２ｎからなる並列演算装置７２で構成される。
【０１１１】
カウンタ７２１１、７２１２、・・・、７２１ｍはカウンタ数決定部７１とスレッドブロック７２２１、７２２２、７２２３、・・・、７２２ｎとに接続されている。カウンタ数ｍはスレッドブロック数ｎ以下であり、また、１つのカウンタに対して１つまたは複数のスレッドブロックが接続されている。カウンタ７２１ｍのカウンタ番号はｍとなる。
【０１１２】
次に、本実施例のフローチャートを図３０に示す。マクロブロック列数取得部７４はマクロブロック列数を取得し、取得したマクロブロック列数をカウンタ数決定部７１に出力する。スレッドブロック数取得部７５はスレッドブロック数を取得し（ステップＳ６１）、取得したスレッドブロック数をカウンタ数決定部７１に出力する。カウンタ数決定部７１は、マクロブロック列数７４の約数や倍数と異なり、スレッドブロック数の約数と同一又は近いカウンタ数ｍを設定する（ステップＳ６２）。
【０１１３】
スレッドブロック７２２１、７２２２、７２２３、・・・、７２２ｎ（または図示していないＣＰＵなどの他の演算装置）はカウンタ７２１１、７２１２、・・・、７２１ｍをカウンタ番号で初期化する（ステップＳ６３）。スレッドブロック７２２１、７２２２、７２２３、・・・、７２２ｎは該スレッドブロックが接続されているカウンタ７２１１、７２１２、・・・、７２１ｍに格納されている値ｉを取得し該カウンタにカウンタ数ｍを加算する（ステップＳ６４）。
【０１１４】
各スレッドブロックを実行するＳＭは、ｉがタスク数以下であれば（ステップＳ６５）ｉ番目のタスクを実行し（ステップＳ６６）、ｉがタスク数以上であれば該スレッドブロックが実行すべきタスクはないので処理を終了する。例えば、スレッドブロック数が１８０、カウンタ数が９０であり、スレッドブロック７２２１とスレッドブロック７２２２がともにカウンタ７２１１に接続されているとすると、スレッドブロック７２２１とスレッドブロック７２２２を実行するＳＭは、タスク１、タスク９１、タスク１８１、タスク２７１・・・を分担して処理する。もし、前記タスクの処理量が全て同じであれば、図３１に示すようにスレッドブロック７２２１を実行するＳＭがタスク１、タスク１８１・・・を、スレッドブロック７２２２を実行するＳＭがタスク２、タスク２７１・・・を処理する。
【０１１５】
ステップＳ６４における２つの処理は、複数のスレッドブロックが１つのカウンタを使用することによる競合状態を避けるため、不可分に行われる必要がある。競合状態が起こると、例えば複数のスレッドブロックが同一のカウンタ値を得たり、使用されないカウンタ値が現れたりするため、正常な処理が行えない。
【０１１６】
本実施例の効果の例として、１９２０×１０８０画素のフルＨＤ(High Definition)サイズ画像を１６×１６画素のマクロブロックで分割して動きベクトル探索を行った場合のスケジュール結果を示す。評価画像にはＩＴＥ標準動画像Ｎｏ．３１を用いた。マクロブロック列数つまりタスク処理量周期は１２０となる。スレッドブロック数は１８０とした。 
【０１１７】
図３２は、本実施例においてタスクキュー毎の処理量が偏る場合と分散できる場合のスレッドブロックごとの処理量を表している。カウンタ数６０はタスク処理量周期であるマクロブロック列数１２０の約数であるためタスクキュー毎の処理量が偏り、スレッドブロックごとの処理量が偏っている。カウンタ数９０は１２０の約数ではないため、カウンタ数６０よりも処理量が分散されており、スレッドブロック当たりの最大処理量も小さい。つまり、より短い時間ですべてのタスクを並列処理できたと言える。
【０１１８】
以上、本発明の好適な実施例を説明した。本発明は、前記実施例のみに範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した実施が可能である。前記実施例では、マクロブロックの列を周期としているが、行でも同様にマクロブロックの処理量に周期的な相関が現れ、本発明の適用が可能である。例えば、１列目１行目のマクロブロックに対応するタスクのタスク番号は１、１列目２行目のマクロブロックに対応するタスクのタスク番号は２、・・・としてもよい。つまり、行番号が増える毎に、マクロブロックに対応するタスク番号が増加するように、マクロブロックにタスクを割り当てても良い。
【０１１９】
また、前記実施例は、画像の動き探索処理をマクロブロック毎にタスクとして並列処理を行っているが、１タスクの処理は１マクロブロックの処理に限定されることはなく、マクロブロック以外の領域範囲で分割された画像の処理も周期的に成り得る。つまり、１つの画像をＮ行Ｍ列（Ｎ及びＭは、任意の正整数）に区分した画像の処理に適用することができる。
【０１２０】
また、静止画像や動画像の動き探索処理以外の画像処理、そして、音声処理など、タスクの処理量に周期的な相関があるアプリケーションの並列処理や分散処理であれば本発明を適用することができる。さらに、本実施例では並列演算装置としてＧＰＵを用いているが、これは、複数のＣＰＵが集積されたマルチコアプロセッサや、複数のコンピュータが接続されたコンピュータクラスタなど、他の並列計算機での実施も可能である。
【０１２１】
本発明は、画像処理の並列処理のスケジューリングだけではなく、音声処理や領域ごとに処理量の異なる行列を扱う数値計算の並列処理、定期的に負荷の重い処理を実行するサーバアプリケーションの分散処理などの、タスク間の処理時間に周期的な相関がある用途のスケジューリングに適用できる。
【０１２２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１２３】
（付記１）複数のタスクを格納するタスク蓄積部と、前記タスクを格納する複数のタスクキューと、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するタスクキュー選択部と、前記タスクを、当該タスクを格納するタスクキューとして前記タスクキュー選択部が選択したタスクキューに格納するエンキュー部と、を備えた情報処理システム。
【０１２４】
（付記２）複数のタスクを格納するタスク蓄積部と、前記タスクを格納する複数のタスクキューと、前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように前記複数のタスクキューのタスクキュー数を決定するタスクキュー数決定部と、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するタスクキュー選択部と、前記タスクを、当該タスクを格納するタスクキューとして前記タスクキュー選択部が選択したタスクキューに格納するエンキュー部と、を備えた情報処理システム。
【０１２５】
（付記３）前記情報処理システムは、前記複数のタスクキューに格納されたタスクを実行する複数のプロセッサをさらに備え、前記タスクキュー数決定部は、前記複数のプロセッサのプロセッサ数の約数又は倍数と、同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記２に記載の情報処理システム。
【０１２６】
（付記４）前記タスクキュー数決定部は、前記複数のタスクのタスク数の約数と同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記２または３に記載の情報処理システム。
【０１２７】
（付記５）それぞれの処理量が周期的に変化する複数のタスクを格納するタスク蓄積部と、前記タスクを格納する複数のタスクキューと、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するタスクキュー選択部と、前記複数のタスクキューのそれぞれについて、前記タスクキューが格納先として選択されたタスクの位相の履歴を示すタスクキュー履歴情報を格納するタスクキュー履歴記憶部と、前記タスクを、当該タスクを格納するタスクキューとして前記タスクキュー選択部が選択したタスクキューに格納するエンキュー部と、を備え、前記タスクキュー選択部は、前記タスクキュー履歴記憶部に格納されたタスクキュー履歴情報に基づいて、前記格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択するとともに、当該選択結果に基づいて、前記タスクキュー履歴記憶部に格納される履歴情報を更新する情報処理システム。
【０１２８】
（付記６）前記タスクキュー履歴情報は、前記タスクキューと、当該タスクキューが格納先として選択されたタスクの位相とを対応付けたタスクキュー対応情報を含み、前記タスクキュー選択部は、前記選択したタスクキューと、当該選択したタスクキューを格納先としたタスクの位相とを対応付けたタスクキュー対応情報を前記タスクキュー記憶部に格納する付記５に記載の情報処理システム。
【０１２９】
（付記７）複数のタスクを格納するタスク蓄積部と、前記タスクを格納する複数のタスクキューと、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するタスクキュー選択部と、前記タスクを、当該タスクを格納するタスクキューとして前記タスクキュー選択部が選択したタスクキューに格納するエンキュー部と、を備え、前記タスクキュー選択部は、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、１周期における最初のタスクを格納するタスクキューとして、当該１周期の前の１周期における最初のタスクとは異なるタスクキューを選択する情報処理システム。
【０１３０】
（付記８）前記タスクは、Ｎ行Ｍ列(Ｎ及びＭは、任意の正整数)に区分した画像の画像処理を実行し、前記周期は、ＮもしくはＭである付記１乃至７の何れか１項に記載の情報処理システム。
【０１３１】
（付記９）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御方法であって、前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、を備えたタスク制御方法。
【０１３２】
（付記１０）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御方法であって、前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように前記複数のタスクキューのタスクキュー数を決定するステップと、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、を備えたタスク制御方法。
【０１３３】
（付記１１）前記タスク制御方法は、複数のプロセッサによって、前記複数のタスクキューに格納されたタスクを実行するステップをさらに備え、前記タスクキュー数を決定するステップでは、前記複数のプロセッサのプロセッサ数の約数又は倍数と、同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記１０に記載のタスク制御方法。
【０１３４】
（付記１２）前記タスクキュー数を決定するステップでは、前記複数のタスクのタスク数の約数と同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記１０または１１に記載のタスク制御方法。
【０１３５】
（付記１３）それぞれの処理量が周期的に変化する複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御方法であって、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、を備え、前記タスクキューを選択するステップでは、前記タスクキューが格納先として選択されたタスクの位相の履歴を示すタスクキュー履歴情報に基づいて、前記格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択するとともに、当該選択結果に基づいて、前記タスクキュー履歴記憶部に格納される履歴情報を更新するタスク制御方法。
【０１３６】
（付記１４）前記タスクキュー履歴情報は、前記タスクキューと、当該タスクキューが格納先として選択されたタスクの位相とを対応付けたタスクキュー対応情報を含み、前記タスクキューを選択するステップでは、前記選択したタスクキューと、当該選択したタスクキューを格納先としたタスクの位相とを対応付けたタスクキュー対応情報を前記タスクキュー履歴情報に含める付記１３に記載のタスク制御方法。
【０１３７】
（付記１５）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御方法であって、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、を備え、前記タスクキューを選択するステップでは、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、１周期における最初のタスクを格納するタスクキューとして、当該１周期の前の１周期における最初のタスクとは異なるタスクキューを選択するタスク制御方法。
【０１３８】
（付記１６）前記タスクは、画像をＮ行Ｍ列(Ｎ及びＭは、任意の正整数)に区分した画像の画像処理を実行し、前記周期は、ＮもしくはＭである付記９乃至１５の何れか１項に記載のタスク制御方法。
【０１３９】
（付記１７）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御プログラムであって、前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、同一の１周期に含まれるタスクが同一のタスクキューに格納されるように、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、  をコンピュータに実行させるタスク制御プログラム。
【０１４０】
（付記１８）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御プログラムであって、前記複数のタスクをそれぞれの処理量が周期的に変化する場合に、１周期に含まれるタスク数の約数及び倍数とは異なる数となるように前記複数のタスクキューのタスクキュー数を決定するステップと、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、をコンピュータに実行させるタスク制御プログラム。
【０１４１】
（付記１９）前記タスク制御プログラムは、複数のプロセッサによって、前記複数のタスクキューに格納されたタスクを実行するステップをさらに備え、前記タスクキュー数を決定するステップでは、前記複数のプロセッサのプロセッサ数の約数又は倍数と、同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記１８に記載のタスク制御プログラム。
【０１４２】
（付記２０）前記タスクキュー数を決定するステップでは、前記複数のタスクのタスク数の約数と同一又は相対的に近い数となるように前記複数のタスクキューのタスクキュー数を決定する付記１８または１９に記載のタスク制御プログラム。
【０１４３】
（付記２１）それぞれの処理量が周期的に変化する複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御プログラムであって、前記タスクを格納するタスクキューを前記複数のタスクキューから選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、をコンピュータに実行させ、前記タスクキューを選択するステップでは、前記タスクキューが格納先として選択されたタスクの位相の履歴を示すタスクキュー履歴情報に基づいて、前記格納先のタスクキューを選択するタスクと同一位相のタスクが格納先として選択された回数が少ないタスクキューを優先的に選択するとともに、当該選択結果に基づいて、前記タスクキュー履歴記憶部に格納される履歴情報を更新するタスク制御プログラム。
【０１４４】
（付記２２）前記タスクキュー履歴情報は、前記タスクキューと、当該タスクキューが格納先として選択されたタスクの位相とを対応付けたタスクキュー対応情報を含み、前記タスクキューを選択するステップでは、前記選択したタスクキューと、当該選択したタスクキューを格納先としたタスクの位相とを対応付けたタスクキュー対応情報を前記タスクキュー履歴情報に含める付記２１に記載のタスク制御プログラム。
【０１４５】
（付記２３）複数のタスクを、複数のタスクキューのいずれかに格納するタスク制御プログラムであって、前記タスクを格納するタスクキューを前記複数のタスクキューから規則的に選択するステップと、前記タスクを、当該タスクを格納するタスクキューとして選択したタスクキューに格納するステップと、をコンピュータに実行させ、前記タスクキューを選択するステップでは、前記複数のタスクのそれぞれの処理量が周期的に変化する場合に、１周期における最初のタスクを格納するタスクキューとして、当該１周期の前の１周期における最初のタスクとは異なるタスクキューを選択するタスク制御プログラム。
【０１４６】
（付記２４）前記タスクは、画像をＮ行Ｍ列(Ｎ及びＭは、任意の正整数)に区分した画像の画像処理を実行し、前記周期は、ＮもしくはＭである付記１７乃至２３の何れか１項に記載のタスク制御プログラム。
【符号の説明】
【０１４７】
１、２、３、４、５、６、７、９０１、９０２    並列処理システム
１１、２２、５２、６２、９１１、９２２    スケジューリング装置
１２      タスク処理量周期取得部
１３    タスク蓄積装置
１４、７２、９１４    並列演算装置
２１、３１、４１    キュー数決定部
３３    プロセッサ数取得部
４４    タスク数取得部
５１    タスク処理量位相算出部
５３    選択キュー記憶装置
７１    カウンタ数決定部
７３    マクロブロック列数取得部
７４    スレッドブロック数取得部
８１、８２、８ｎ、９８１、９８２、９８ｍ    タスクキュー
１１１、２２１、５２１、６２１、９１１１、９２２１    キュー選択部
１１２、１１１２、９１１２    エンキュー部
１４１、１４２、１４３、１４ｎ、９１４１、９１４２、９１４３、９１４ｎ    プロセッサ
１００１、１００２、１００５、１０００６    情報処理システム
１０１３    タスク蓄積部
１０２１    タスクキュー数決定部
１０５３    タスクキュー履歴記憶部
１１１１、１２２１、１５２１、１６２１    タスクキュー選択部
７２１１、７２１２、７２１ｍ    カウンタ
７２２１、７２２２、７２２３、７２２ｎ    スレッドブロック
９２２２    負荷取得部
【図１】
0005556326.tif 000002
【図２】
0005556326.tif 000003
【図３】
0005556326.tif 000004
【図４】
0005556326.tif 000005
【図５】
0005556326.tif 000006
【図６】
0005556326.tif 000007
【図７】
0005556326.tif 000008
【図８】
0005556326.tif 000009
【図９】
0005556326.tif 000010
【図１０】
0005556326.tif 000011
【図１１】
0005556326.tif 000012
【図１２】
0005556326.tif 000013
【図１３】
0005556326.tif 000014
【図１４】
0005556326.tif 000015
【図１５】
0005556326.tif 000016
【図１６】
0005556326.tif 000017
【図１７】
0005556326.tif 000018
【図１８】
0005556326.tif 000019
【図１９】
0005556326.tif 000020
【図２０】
0005556326.tif 000021
【図２１】
0005556326.tif 000022
【図２２】
0005556326.tif 000023
【図２３】
0005556326.tif 000024
【図２４】
0005556326.tif 000025
【図２５】
0005556326.tif 000026
【図２６】
0005556326.tif 000027
【図２７】
0005556326.tif 000028
【図２８】
0005556326.tif 000029
【図２９】
0005556326.tif 000030
【図３０】
0005556326.tif 000031
【図３１】
0005556326.tif 000032
【図３２】
0005556326.tif 000033
【図３３】
0005556326.tif 000034
【図３４】
0005556326.tif 000035
【図３５】
0005556326.tif 000036
【図３６】
0005556326.tif 000037
【図３７】
0005556326.tif 000038
【図３８】
0005556326.tif 000039
【図３９】
0005556326.tif 000040