(57)【特許請求の範囲】
【請求項１】
複数のコアを有する制御手段と、
複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、
複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、
新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と
を有し、
前記属性情報は、前記関連性を表す情報として、前記複数のタスクにおける入力データまたは出力データの共通性を示す情報を含み、
前記属性情報においては、前記入力データの共通性と前記出力データの共通性とが互いに区別されている
情報処理装置。
【請求項２】
複数のコアを有する制御手段と、
複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、
複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、
新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と
を有し、
前記属性情報は、前記関連性の重みを示す情報を含む
情報処理装置。
【請求項３】
複数のコアを有する制御手段と、
複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、
複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、
新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と
を有し、
前記制御手段は、前記複数のコアで共用されるキャッシュメモリを有し、
前記属性情報は、前記複数のタスクの各々における前記キャッシュメモリの使用量を含む
情報処理装置。
【請求項４】
複数のコアを有する制御手段と、
複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、
複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、
新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と、
前記制御手段のハードウェア構成を示す構成情報を取得する第４取得手段と
を有し、
前記割り当て手段は、前記割り当て情報および前記属性情報に加え、前記第４取得手段により取得された構成情報を参照して、前記新たなタスクを割り当てる
情報処理装置。
【請求項５】
複数のコアを有する制御手段と、
複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、
複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、
新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と
を有し、
前記複数のタスクは、ある単位で繰り返される画像処理を含み、
新たな単位分の画像処理に関するタスクの割り当てを決定する際、前記複数のコアに割り当て済みのタスクに関する前記属性情報のうち当該完了した画像処理に関する情報を初期化する初期化手段を有する
情報処理装置。
【請求項６】
前記複数のタスクを実行するためのプログラムコードをコンパイルするコンパイル手段を有し、
前記コンパイル手段は、前記複数のタスクのうち一のタスクを実行するためのプログラムコードをコンパイルする際、当該一のタスクの前記属性情報を生成する
ことを特徴とする請求項１ないし５のいずれか一項に記載の情報処理装置。
【請求項７】
前記複数のタスクの優先度を示す優先度情報を取得する第３取得手段を有し、
前記割り当て手段は、まだ前記複数のコアに割り当てられていないタスクのうち割り当ての対象となるタスクを、前記第３取得手段により取得された優先度情報に応じて選択する
ことを特徴とする請求項１ないし６のいずれか一項に記載の情報処理装置。
【請求項８】
請求項１ないし７のいずれか一項に記載の情報処理装置と、
前記複数のコアに割り当てられたタスクにより出力されたデータに応じて画像を形成する画像形成手段と
を有する画像形成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および画像形成装置に関する。
【背景技術】
【０００２】
複数のコアを有するプロセッサを用いた情報処理装置が知られている。このような情報処理装置においては、新たに発生したタスク（処理）をどのコアに割り振るかが、情報処理装置全体のパフォーマンスを左右する。特許文献１は複数のコアを有するプロセッサではなく複数のプロセッサを用いたシステムに関するものであるが、タスクをグループ化しておき、グループ毎に同一のプロセッサにタスクを割り当てる技術を開示している。特許文献２は、過去のタスクの割り振りを記憶しておき、以前と同じタスクが起動された場合には以前と同じコアにタスクを割り当てる技術を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平１０−７８９４２号公報
【特許文献２】特開平１１−２５９３１８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
複数のコアを有するプロセッサを用いた情報処理装置において、それぞれのコアにタスクを割り振る場合、単に同じタスク（または同じグループに属するタスク）を同じコアに割り当てるだけでは、特定のコアにタスクが集中してしまい、装置全体のパフォーマンスが必ずしも最適化されないという問題があった。
【０００５】
本発明は、同じタスクを同じコアに関連付けて割り当てるよりも効率的に、複数のコアにタスクを割り当てる技術を提供する。
【課題を解決するための手段】
【０００６】
本発明は、複数のコアを有する制御手段と、複数のタスクが各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段とを有する情報処理装置を提供する。
【０００７】
前記属性情報は、前記関連性を表す情報として、前記複数のタスクにおける入力データまたは出力データの共通性を示す情報を含んでもよい。
【０００８】
前記属性情報においては、前記入力データの共通性と前記出力データの共通性とが互いに区別されていてもよい。
【０００９】
前記属性情報は、前記関連性の重みを示す情報を含んでいてもよい。
【００１０】
前記制御手段は、前記複数のコアで共用されるキャッシュメモリを有し、前記属性情報は、前記複数のタスクの各々における前記キャッシュメモリの使用量を含んでいてもよい。
【００１１】
この情報処理装置は、前記複数のタスクを実行するためのプログラムコードをコンパイルするコンパイル手段を有し、前記コンパイル手段は、前記複数のタスクのうち一のタスクを実行するためのプログラムコードをコンパイルする際、当該一のタスクの前記属性情報を生成してもよい。
【００１２】
この情報処理装置は、前記複数のタスクの優先度を示す優先度情報を取得する第３取得手段を有し、前記割り当て手段は、まだ前記複数のコアに割り当てられていないタスクのうち割り当ての対象となるタスクを、前記第３取得手段により取得された優先度情報に応じて選択してもよい。
【００１３】
この情報処理装置は、前記制御手段のハードウェア構成を示す構成情報を取得する第４取得手段を有し、前記割り当て手段は、前記割り当て情報および前記属性情報に加え、前記第４取得手段により取得された構成情報を参照して、前記新たなタスクを割り当ててもよい。
【００１４】
前記複数のタスクは、ある単位で繰り返される画像処理を含み、この情報処理装置は、新たな単位分の画像処理に関するタスクの割り当てを決定する際、前記複数のコアに割り当て済みのタスクに関する前記属性情報のうち当該完了した画像処理に関する情報を初期化する初期化手段を有してもよい。
【００１５】
また、本発明は、複数のコアを有する制御手段と、複数の処理が各々前記複数のコアのうちどのコアに割り当てられたか示す割り当て情報を取得する第１取得手段と、複数のタスク間の関連性を表す属性情報を取得する第２取得手段と、新たなタスクが発生した場合、前記第１取得手段により取得された割り当て情報および前記第２取得手段により取得された属性情報を参照し、前記複数のコアのうち当該新たなタスクと関連するタスクが割り当てられているコアに、当該新たなタスクを割り当てる割り当て手段と、前記複数のコアに割り当てられたタスクにより出力されたデータに応じて画像を形成する画像形成手段とを有する画像形成装置を提供する。
【発明の効果】
【００１６】
請求項１に係る情報処理装置によれば、複数の処理間の関連性に応じて、複数のコアに処理を割り当てることができる。
請求項２に係る情報処理装置によれば、入力データまたは出力データの関連性に応じて、複数のコアに処理を割り当てることができる。
請求項３に係る情報処理装置によれば、入力データの関連性および出力データの関連性をそれぞれ別個に考慮して複数のコアに処理を割り当てることができる。
請求項４に係る情報処理装置によれば、複数の処理間の関連性に重みを付けることができる。
請求項５に係る情報処理装置によれば、キャッシュメモリの使用量を考慮して複数のコアに処理を割り当てることができる。
請求項６に係る情報処理装置によれば、プログラムコードに応じて属性情報を生成することができる。
請求項７に係る情報処理装置によれば、処理の優先度に応じて複数のコアに処理を割り当てることができる。
請求項８に係る情報処理装置によれば、制御手段のハードウェア構成に応じて複数のコアに処理を割り当てることができる。
請求項９に係る情報処理装置によれば、繰り返し行われる画像処理において、複数の処理間の関連性に応じて、複数のコアに処理を割り当てることができる。
請求項１０に係る画像形成装置によれば、複数の処理間の関連性に応じて、複数のコアに処理を割り当てることができる。
【図面の簡単な説明】
【００１７】
【図１】関連技術に係るＣＰＵ９０の構成を例示する図
【図２】関連技術に係るタスク割り当てを例示する図
【図３】タスク構造を例示する図
【図４】関連技術に係るタスク割り当てを例示する図
【図５】一実施形態に係る画像形成装置１の構成を示す図
【図６】画像形成装置１の機能構成を例示する図
【図７】画像形成装置１の動作を例示するフローチャート
【図８】コアに割り当て済みのタスクを例示する図
【図９】図８のタスクの割り当てを示すスケジュール情報を例示する図
【図１０】新規タスクを例示する図
【図１１】図１０のタスクの属性情報を例示する図
【図１２】タスクＧ〜Ｌの割り当て結果を例示する図
【図１３】さらなる新規タスクを例示する図
【図１４】タスクの属性情報を例示する図
【図１５】タスクＭ〜Ｏの割り当て結果を例示する図
【図１６】動作例２に係る割り当て済みのタスクを例示する図
【図１７】動作例２におけるタスクＨおよびタスクＩの属性情報を示す図
【図１８】スケジュール情報を示す図
【図１９】動作例２によるタスクの割り当て結果を示す図
【図２０】動作例３におけるタスクＨおよびタスクＩの属性情報を示す図
【図２１】スケジュール情報を示す図
【図２２】動作例３によるタスクの割り当て結果を示す図
【図２３】動作例４に係る割り当て済みのタスクを示す図
【図２４】スケジュール情報を示す図
【図２５】動作例４によるタスクの割り当て結果を示す図
【図２６】動作例５に係る割り当て済みのタスクを例示する図
【図２７】動作例５におけるタスクＨおよびタスクＩの属性情報を示す図
【図２８】スケジュール情報を示す図
【図２９】動作例５によるタスクの割り当て結果を示す図
【図３０】動作例６に係るタスクを示す図
【図３１】動作例６に係るタスクの属性情報を示す図
【図３２】動作例６によるタスクの割り当てを示す図
【図３３】動作例６によるタスクの割り当てを示す図
【図３４】動作例６によるタスクの割り当てを示す図
【図３５】動作例６によるタスクの割り当てを示す図
【図３６】動作例６によるタスクの割り当てを示す図
【図３７】動作例６によるタスクの割り当てを示す図
【図３８】動作例６によるタスクの割り当てを示す図
【図３９】動作例６によるタスクの割り当てを示す図
【図４０】動作例６によるタスクの割り当てを示す図
【図４１】動作例６によるタスクの割り当てを示す図
【図４２】動作例６によるタスクの割り当てを示す図
【図４３】変形例１に係る新規タスクの割り当て処理を示すフローチャート
【図４４】分類を含むタスク間の関連性を例示する図
【図４５】ＣＰＵのキャッシュメモリの構成を例示する図
【図４６】割り当て制御テーブルを例示する図
【図４７】変形例２に係る新規タスクの割り当て処理を示すフローチャート
【図４８】変形例４に係る属性情報を例示する図
【図４９】変形例５におけるスケジュール情報を例示する図
【図５０】変形例６におけるスケジュール情報を例示する図
【図５１】属性情報の一部が消去されたスケジュール情報を例示する図
【発明を実施するための形態】
【００１８】
１．概要
図１は、関連技術に係るＣＰＵ（Central Processing Unit）９０の構成を例示する図である。ＣＰＵ９０は、複数のコア、この例では、コア９０１〜９０４の４つのコアを有するプロセッサである。ここで、プロセッサの「コア」とは、プロセッサのうち命令の実行および演算を行う部分をいう。ＣＰＵ９０は、さらに、キャッシュメモリ９１１〜９１４およびキャッシュメモリ９２１〜９２２を有する。キャッシュメモリ９１１〜９１４は一次キャッシュ（いわゆるＬ１キャッシュ）であり、それぞれ、コア９０１〜９０４に専用のものである。キャッシュメモリ９２１および９２２は二次キャッシュ（いわゆるＬ２キャッシュ）である。キャッシュメモリ９２１はコア９０１および９０２で共用され、キャッシュメモリ９２２はコア９０３および９０４で共用される。なお一般にはＬ１キャッシュまで含めて「コア」という場合があるが、ここでは「コア」にＬ１キャッシュは含まれない。
【００１９】
一次キャッシュとはコアから最優先にアクセスされるキャッシュメモリをいい、二次キャッシュとは一次キャッシュの次の優先順位でアクセスされるキャッシュメモリをいう。一次キャッシュは、二次キャッシュよりも高速でかつ容量が小さい。メインメモリ（外部メモリ）へのアクセス要求が発生すると、コアはまずアクセス先のアドレスのデータが一次キャッシュに格納されているか調べる。アクセス先のアドレスのデータ（以下単に「アクセス先のデータ」という）が一次キャッシュに格納されていた場合、コアは一次キャッシュからデータを読み出す。アクセス先のデータがキャッシュメモリに格納されていることを「ヒット」といい、ヒットが発生する割合を「ヒット率」という。アクセス先のデータが一次キャッシュに格納されていなかった場合、コアは、アクセス先のデータが二次キャッシュに格納されていないか調べる。アクセス先のデータが二次キャッシュに格納されていた場合、コアは二次キャッシュからデータを読み出す。アクセス先のデータが二次キャッシュに格納されていなかった場合、コアはメインメモリからデータを読み出す。
【００２０】
また、ＣＰＵ９０は、いわゆるＳＭＰ（Symmetric Multi Processing）型のプロセッサであり、各コアの機能は同一である。マルチコア型のプロセッサには、この他、ＡＭＰ（Asymmetric Multi Processing）型のプロセッサも存在するが、例えば、いわゆる複合機のように、処理すべきタスクが多く、かつ、プリント、スキャン、ファクシミリ送受信、ＵＩ処理、ネットワーク処理など、処理の組み合わせが多数ある機器においては、一般にＳＭＰ型のプロセッサが用いられる。例えば、画像処理のようにパイプラインにより連続演算を前提としたデータ処理を行う場合、キャッシュのヒット率が下がるとメインメモリへのアクセスによるコアの待ち時間が発生してプロセッサのパフォーマンスが低下してしまう。したがって、どのコアにどのタスクを割り当てるかというのは、プロセッサのパフォーマンスを左右する問題である。
【００２１】
図２は、関連技術に係るタスク割り当てを例示する図である。この図は、各コアが実行すべきタスクを示しており、各コアがタスクを実行する予定（スケジュール）を示すものである。この例では、タスクＡ〜Ｇがコア９０２〜９０４の４つのコアに割り当てられる。タスクＡおよびＣ、タスクＢおよびＤ、並びにタスクＥおよびＦは、それぞれデータを共有することがあらかじめ分かっている。そこで、タスクＡおよびＣ、タスクＢおよびＤ、並びにタスクＥおよびＦは、それぞれグループ化されている。この例では、同一グループのタスクを同一のコアに割り当てるという規則が適用される。
【００２２】
ここで、複数のタスクが、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ａ、Ｂ、Ｃ、Ｄ、Ｇ、Ｆ、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、およびＧの順番で発生する例を考える。まず最初のタスクＡはコア９０１に割り当てられる。２番目のタスクＢはコア９０２に割り当てられる。３番目のタスクＣは、タスクＡとグループ化されているのでコア９０１に割り当てられる。４番目のタスクＤは、タスクＢとグループ化されているのでコア９０２に割り当てられる。５番目のタスクＥは、コア９０１および９０２は既に処理予定が埋まっているので、コア９０３に割り当てられる。６番目のタスクＦは、タスクＥとグループ化されているのでコア９０３に割り当てられる。７番目のタスクＧは、どのタスクともグループ化されていないので使用率が最も低いコア９０４に割り当てられる。以下同様にタスクを割り当てていくと、図２のように割り当てられる。
【００２３】
この例では、コア９０３およびコア９０４がアイドルになる割合が高く、４つあるコアを必ずしも有効に活用できておらず、改善の余地がある。
【００２４】
さらに別の例を考える。ここでは、画像形成装置のように、複数のタスクが直列に接続された、いわゆるパイプライン処理が、所定の単位（例えばページまたはバンド）毎に繰り返し行われる例を用いる。
【００２５】
図３は、タスク構造を例示する図である。タスクＡ〜Ｅの入力データを、データａ〜ｅという。あるタスクの出力データが次のタスクの入力データとなっている。すなわち、タスクＡ〜Ｅはパイプライン処理を構成している。例えば、パイプライン処理にデータａが入力されると、まずタスクＡによりデータｂが出力される。タスクＢはデータｂを処理し、データｃを出力する。以下同様に直列的に処理が行われ、タスクＥはデータｆを出力する。すなわち、このパイプライン処理にデータａを入力するとデータｆが得られる。
【００２６】
次に、タスクＡ〜Ｅに加え、パイプライン処理に含まれないタスクＦおよびＧをコア９０１〜９０４に割り当てる例を考える。この例では、タスクＡ〜Ｅがグループ化され、同じグループに属するタスクを、同じＬ２キャッシュを共有するコアに割り当てるという規則が適用される。
【００２７】
図４は、関連技術に係るタスク割り当てを例示する図である。この例では、タスクの割り当てはコア９０１および９０２に偏っており、コア９０３および９０４がアイドルになる割合が高い。４つあるコアを必ずしも有効に活用できておらず、改善の余地がある。
【００２８】
ところで、図４の例では、第１ページ、第２ページ、および第３ページのパイプライン処理は、いずれもコア９０１またはコア９０２に割り当てられている。タスクＡ〜Ｅは、図３で説明したように同一ページ内ではデータを共有しているが、ページ間ではデータを共有していない。例えば、第１ページのパイプライン処理の出力であるデータｆは、第２ページのパイプライン処理の入力であるデータａとは無関係である。したがって、キャッシュのヒット率を向上させるという観点では、第１ページのパイプライン処理と第２ページのパイプライン処理とをいずれもコア９０１および９０２に割り当てることはあまり意味がなく、むしろタスク割り当ての偏りを生じさせる一因となる。
【００２９】
これに対し本実施形態では、より効率的にタスクを割り当てる技術を提供する。
【００３０】
２．構成
図５は、一実施形態に係る画像形成装置１の構成を示す図である。画像形成装置１は、画像を形成する機能を有する情報処理装置の一例であり、例えばいわゆる複合機である。画像形成装置１は、ＣＰＵ１０、メモリコントローラー２０、主記憶装置（メインメモリ）３０、ＩＯコントローラー４０、補助記憶装置４１、画像読み取りユニット４２、画像形成ユニット４３、および通信ユニット４４を有する。
【００３１】
ＣＰＵ１０は、画像形成装置１の各部を制御する制御装置（制御手段の一例）であり、各々異なる処理を実行するＮ個のコア（Ｎは２以上の自然数）を含む処理手段の一例である。この例ではＮ＝４である。ＣＰＵ１０は、コア１０１〜１０４、キャッシュメモリ１１１〜１１４、およびキャッシュメモリ１２１〜１２２を有する。キャッシュメモリ１１１〜１１４は一次キャッシュ（Ｌ１キャッシュ）であり、それぞれコア１０１〜１０４に専用のものである。キャッシュメモリ１２１〜１２２は二次キャッシュ（Ｌ２キャッシュ）である。キャッシュメモリ１２１はコア１０１および１０２で共用され、キャッシュメモリ１２２はコア１０３および１０４で共用される。
【００３２】
以下の説明において、同じＬ２キャッシュを共有する複数のコアを「コア群」という。図５の例ではコア１０１およびコア１０２は同一のコア群に属し、コア１０３およびコア１０４はそれと別のコア群に属する。例えば、コア１０２およびコア１０３により構成されるコア群を、「コア１０１／１０２」と記載する。
【００３３】
メモリコントローラー２０は、主記憶装置３０に対するデータの読み書きを制御する。主記憶装置３０は主記憶装置であり、例えばＤＲＡＭ（Dynamic Random Access Memory）を含む。主記憶装置３０は、ＣＰＵ１０がプログラムを実行する際のワークエリアとして機能し、種々のデータを記憶する記憶手段の一例である。
【００３４】
ＩＯコントローラー４０は、周辺装置をＣＰＵ１０に接続して制御する装置である。この例で、ＩＯコントローラー４０には、補助記憶装置４１、画像読み取りユニット４２、画像形成ユニット４３、および通信ユニット４４が接続されている。補助記憶装置４１はデータおよびプログラムを記憶する不揮発性の記憶装置であり、例えばＨＤＤ（Hard Disk Drive）を含む。画像読み取りユニット４２は、原稿を光学的に読み取る装置であり、例えばいわゆるスキャナーを含む。画像形成ユニット４３は、媒体（例えば紙）に画像を形成する装置であり、例えば電子写真技術またはインクジェット技術により画像形成を行う。通信ユニット４４は、他の機器と通信を行うインターフェースである。
【００３５】
図６は、画像形成装置１の機能構成を例示する図である。補助記憶装置４１は、画像形成装置１のＯＳ（Operating System）を機能させるためのプログラム（以下「ＯＳプログラム」という）および各種アプリケーション（コピー機能、スキャナー機能、ファクシミリ送受信機能等）を実現するためのプログラム（以下「アプリケーションプログラム」という）を記憶している。ＣＰＵ１０がこれらのプログラムを実行することにより、画像形成装置１にＯＳ５０およびアプリケーション６１〜６３が実装される。
【００３６】
アプリケーション６１〜６３は、それぞれＯＳ５０に対しタスクの実行を命令する。すなわちタスクを要求する。ここでいうタスクとは、画像形成装置１のハードウェア資源を利用した処理をいい、ジョブを構成するものをいう。ジョブとは、アプリケーション６１〜６３により生成されるものであって、アプリケーションに係る処理、例えば、原稿をコピーする処理、原稿を読み取ってデータ化する処理、原稿を読み取ってファクシミリ送信する処理、与えられたデータに従って画像を形成する処理をいう。例えば、原稿をコピーするジョブは、画像読み取りユニット４２を用いて原稿から画像を読み取るタスク、読み取った画像に対して画像処理をするタスク、および画像形成ユニット４３を用いて媒体に画像を形成するタスクに分解される。ＯＳ５０は、アプリケーションにより要求されたタスクを複数のコアのうちいずれかのコアに割り当てる。コア１０１〜１０４は、ＯＳ５０によってそれぞれ独立したＣＰＵとして認識される。
【００３７】
アプリケーションにおいて新たなタスクの要求が発生すると、ＯＳ５０は、そのタスクをどこコアに実行させるか決定する。詳細には以下のとおりである。ＯＳ５０は、取得手段５１、取得手段５２、取得手段５３、取得手段５４、記憶手段５５、割り当て手段５６、初期化手段５７、および検知手段５８を有する。検知手段５８は、新たなタスクが発生したことを検知する。取得手段５１は、割り当て情報を取得する。割り当て情報は、複数のタスクが各々コア１０１〜１０４のうちどのコアに割り当てられたかを示す。取得手段５２は、属性情報を取得する。属性情報は、複数のタスク間の関連性を示す。タスク間の関連性とは、タスク間でデータを共有することをいう。例えば、あるタスクの出力データが別のタスクの入力データとして用いられる場合、これら２つのタスクは関連性を有するという。あるいはある共通の入力データを用いて、２つのタスクが２つの異なるデータを出力する場合、これら２つのタスクは関連性を有するという。取得手段５３は、優先度情報を取得する。優先度情報は、複数のタスクの優先度を示す。取得手段５４は、構成情報を取得する。構成情報は、ＣＰＵ１０のハードウェア構成を示す。この例では、割り当て情報、属性情報、優先度情報、および構成情報は、記憶手段５５に記憶されており、取得手段５１〜５４は、記憶手段５５から各情報を取得する。属性情報は、例えば、タスクを実行するためのプログラムをコンパイルするコンパイラ（コンパイル手段の一例）により生成される。優先度情報および構成情報は、例えば、システムによりあらかじめ設定されている。割り当て手段５６は、新たなタスクが発生した場合、これらの情報の少なくとも一部を参照し、そのタスクの割り当て先となるコアを決定する（すなわちあるコアに新たなタスクを割り当てる）。初期化手段５７は、特にタスクがある単位（例えばページまたはバンド）で繰り返される画像処理に係るものである場合、一単位分の画像処理が完了すると、コアに割り当て済みのタスクに関する属性情報のうち完了した画像処理に関する情報を初期化する。これらの情報および割り当て方法の詳細は後述する。
【００３８】
なお図６の機能構成は一例であり、この一部が省略されてもよいし、これ以外の機能が追加されてもよい。以下の動作説明においては、初期化手段５７の機能は省略する。
【００３９】
３．動作
３−１．動作フロー
図７は、画像形成装置１の動作を例示するフローチャートである。ここでは特に、タスクをコアに割り当てる処理を記載している。図７のフローは、例えば、画像形成装置１の電源が投入されたことを契機として開始される。以下の説明においてＯＳ５０等のソフトウェアを処理の主体として記載することがあるが、これは、そのソフトウェアを実行しているＣＰＵ１０が他のハードウェア資源と共働して処理を実行することを意味する。
【００４０】
ステップＳ１００において、ＯＳ５０は、新規タスクが発生したか判断する。新規タスクとは、アプリケーション６１〜６３から新たに要求されたタスクをいう。新たなタスクが発生すると、アプリケーション６１〜６３からＯＳ５０に要求が送られるので、ＯＳ５０は新たなタスクの発生を検知することができる。ＯＳ５０は、例えば各タスクに識別番号を付与することにより各タスクを識別する。同じ種類のタスクが繰り返し実行される場合、例えばタスクＡが２回実行される場合には、１回目のタスクＡおよび２回目のタスクＡにはそれぞれ別の識別番号が付与され、別のタスクとして識別される。新規タスクが発生していないと判断された場合（Ｓ１００：ＮＯ）、ＯＳ５０は、新規タスクが発生するまで待機する。新規タスクが発生したと判断された場合（Ｓ１００：ＹＥＳ）、ＯＳ５０は、処理をステップＳ１０１に移行する。
【００４１】
ステップＳ１０１において、ＯＳ５０は、未割り当てのタスクがあるか判断する。未割り当てのタスクとは、そのタスクを実行するコアが決定されていないタスクをいう。ＯＳ５０は、コア毎にタスクの実行予定を記述したスケジュール情報（割り当て情報の一例）を保持しており、このスケジュール情報を参照して、未割り当てのタスクがあるか判断する。未割り当てのタスクがあると判断された場合（Ｓ１０１：ＹＥＳ）、ＯＳ５０は、処理をステップＳ１０２に移行する。未割り当てのタスクがないと判断された場合（Ｓ１０１：ＮＯ）、ＯＳ５０は、処理をステップＳ１００に移行する。
【００４２】
ステップＳ１０２において、ＯＳ５０は、未割り当てのタスクの中から、最も優先度が高い一のタスクを選択する。ここで選択されたタスクを以下「対象タスク」という。優先度が最も高いタスクが複数ある場合、ＯＳ５０は、優先度が最も高い複数のタスクの中から、他の基準に従って対象タスクを選択する。他の基準は、例えば、処理が先に行われるものを先に対象タスクとして選択するという基準である。
【００４３】
ステップＳ１０３において、ＯＳ５０は、対象タスクが、割り当て済みのタスクと関連性を有しているか判断する。割り当て済みのタスクとは、そのタスクを実行するコアが決定されており、そのタスクの実行予定がスケジュール情報に記述されているタスクをいう。すなわち、割り当て済タスクは、まだ実行されていないタスクをいう。実行済のタスクは、スケジュール情報から削除される。ＯＳ５０は、タスク間の関連性を示す属性情報を保持しており、この属性情報を参照して対象タスクが割り当て済みのタスクと関連性を有しているか判断する。対象タスクが割り当て済みのタスクと関連性を有していると判断された場合（Ｓ１０３：ＹＥＳ）、ＯＳ５０は、処理をステップＳ１０４に移行する。対象タスクが割り当て済みのタスクと関連性を有していないと判断された場合（Ｓ１０３：ＮＯ）、ＯＳ５０は、処理をステップＳ１０５に移行する。
【００４４】
ステップＳ１０４において、ＯＳ５０は、対象タスクと関連性を有するタスクが割り当てられているコア群に、対象タスクを割り当てる。以下、対象タスクが割り当てられるコアを「割り当て先」という。割り当て先の候補となるコアが複数ある場合、ＯＳ５０は、例えば以下の優先順位に従って割り当て先を決定する。
（ｉ）割り当て済みのタスクの数が最少のコア群に属するコア。
（ｉｉ）割り当て済みのタスクの数が最少のコア。
（ｉｉｉ）識別番号が先のコア。
あるいは、ＯＳ５０は、以下の優先順位に従って割り当て先を決定してもよい。
（ｉ）割り当て済みのタスクの数が最少のコア群に属するコア。
（ｉｉ）割り当て済みのタスクの数が最少のコア。
（ｉｉｉ）関連性を有するタスクが割り当て済のコア。
（ｉｖ）より新しいタスクが割り当て済のコア。
ＯＳ５０は、対象タスクと割り当て先との関係を、スケジュール情報に追加する。ステップＳ１０４の処理を終えると、ＯＳ５０は、処理をステップＳ１０１に移行する。
【００４５】
ステップＳ１０５において、ＯＳ５０は、未割り当てのタスクの中に対象タスクと関連性を有するタスクが存在するか判断する。未割り当てのタスクの中に対象タスクと関連性を有するタスクがあると判断された場合（Ｓ１０５：ＹＥＳ）、ＯＳ５０は、処理をステップＳ１０６に移行する。未割り当てのタスクの中に対象タスクと関連性を有するタスクがないと判断された場合（Ｓ１０５：ＮＯ）、ＯＳ５０は、処理をステップＳ１０７に移行する。
【００４６】
ステップＳ１０６において、ＯＳ５０は、複数のコア群のうち、割り当て済みのタスクが最も少ないコア群に属するコアにタスクを割り当てる。どのコアとどのコアが同一のコア群に属するかは、構成情報により示される。ＯＳ５０は、構成情報を保持しており、この構成情報を参照して同一のコア群に属するコアを特定する。また、ＯＳ５０は、スケジュール情報を参照して割り当て済みのタスクが最も少ないコア群を特定する。割り当て済タスクが最も少ないコア群が複数ある場合、ＯＳ５０は、例えば以下の優先順位に従って割り当て先の候補となるコア群を１つに絞り込む。
（１）単一のコアに割り当て済タスクの数の最大値が少ないコア群。
（２）識別番号が早いコアを含むコア群。
ＯＳ５０は、特定されたコア群に含まれるコアの中から以下の優先順位に従って割り当て先を決定する。
（ｉ）割り当て済みのタスクの数が最少のコア。
（ｉｉ）識別番号が先のコア。
ＯＳ５０は、対象タスクと割り当て先との関係を、スケジュール情報に追加する。ステップＳ１０６の処理を終えると、ＯＳ５０は、処理をステップＳ１０１に移行する。
【００４７】
ステップＳ１０７において、ＯＳ５０は、コア１０１〜１０４のうち割り当て済みのタスクが最も少ないコアに対象タスクを割り当てる。割り当て済タスクが最少のコアが複数ある場合、ＯＳ５０は、例えば識別番号が先のコアを割り当て先として決定する。ＯＳ５０は、対象タスクと割り当て先との関係を、スケジュール情報に追加する。ステップＳ１０７の処理を終えると、ＯＳ５０は、処理をステップＳ１０１に移行する。
【００４８】
タスクの割り当てとは独立して、ＯＳ５０は、タスクを実行する。ＯＳ５０は、スケジュール情報を参照して各コアに実行させるべきタスクを特定し、そのタスクを実行するよう各コアを制御する。タスクの実行が完了すると、ＯＳ５０は、スケジュール情報からそのタスクに実行予定を削除する。
【００４９】
３−２．動作例１
以下、具体例を用いて図７のフローに係る新規タスクの割り当て処理についてより詳細に説明する。なお動作例１ないし５においては、説明を簡単にするため、タスクの実行については考えない。
【００５０】
図８は、コアに割り当て済みのタスクを例示する図である。この例では、タスク群８０１〜８０３の３群のタスク群がコアに割り当て済みである。タスク群８０１は、タスクＡおよびタスクＢが直列に接続された処理である。タスク群８０１にデータａが入力されると、最終的にタスクＢからデータｃが出力される。タスク群８０１は、例えば画像処理をするためのパイプライン処理である。タスク群８０２は、タスクＤおよびタスクＥが並列に接続された処理である。詳細には、タスク群８０２においてデータｄが入力されると、タスクＣによりデータｅが出力され、さらにタスクＤによりデータｆが出力される。タスク群８０２は、例えばＬＵＴ（Look Up Table）を参照する処理である。タスク群８０３は、他のタスクとの関連性が無いタスクの集合である。タスク群８０３はタスクＥおよびタスクＦを含むが、両者は互いに独立しており、データを共有することはない。タスク群８０３は、例えば、ネットワークまたはＵＳＢ（Universal Serial Bus）などのインターフェース関連の処理である。
【００５１】
図９は、図８のタスクの割り当てを示すスケジュール情報を例示する図である。図９の例では、各コアに割り当て済タスクが、その実行順を示す情報と共に記録されている。この時点で、コア１０１にはタスクＡおよびタスクＥが、コア１０２にはタスクＢおよびタスクＦが、コア１０３にはタスクＣが、コア１０４にはタスクＤが、それぞれ割り当てられている。この図では、より上の階層に記載されているものがより先に実行される。
【００５２】
以上の状況において新規タスクが発生した場合に、その新規タスクがどのコアに割り当てられるか説明する。説明に先立って、まず新規タスクの構造および属性情報について説明する。
【００５３】
図１０は、新規タスクを例示する図である。例えばアプリケーションにより新たなジョブが発生すると、アプリケーションは、このジョブを実行するため、タスク群８０４〜８０６を起動する。タスク群８０４は、タスクＧおよびタスクＨが直列に接続された処理である。タスク群８０４にデータａが入力されると、最終的にタスクＨからデータｌが出力される。タスク群８０５は、タスクＩおよびタスクＪが並列に接続された処理である。タスク群８０５においてデータｍが入力されると、タスクＩによりデータｎが出力され、タスクＪによりデータｏが出力される。タスク群８０６は、他のタスク群と関連性が無いタスクの集合である。この例ではタスクＧ〜Ｌの優先度は以下のとおり設定されている。
タスクＧ：優先度１（最高）
タスクＨ：優先度１（最高）
タスクＩ：優先度２
タスクＪ：優先度３
タスクＫ：優先度４
タスクＬ：優先度５
【００５４】
図１１は、図１０のタスクの属性情報を例示する図である。図１０と図８を対比すると分かるように、タスクＧはタスクＡおよびタスクＨと、タスクＨはタスクＧと、タスクＩはタスクＪと、タスクＪはタスクＩと、それぞれ関連性を有している。
【００５５】
コアへのタスクの割り当ての説明に移る。ＯＳ５０は、図１０の新規タスクが発生したことを検知する（ステップＳ１００）。これらの新規タスクは、検出された時点では当然コアに割り当てられていない。したがって、フローはステップＳ１０１からＳ１０２に進む。ＯＳ５０は、新規タスクの中から対象タスクを選択する。具体的には、ＯＳ５０は、優先度が最も高いものを対象タスクとして選択する。したがって、まずはタスクＧが対象タスクとして選択される（ステップＳ１０２）。処理はステップＳ１０３に進む。タスクＧについて属性情報を見ると、割り当て済タスクＡと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがって処理はステップＳ１０４に進む。タスクＡが割り当て済のコア１０１／１０２が割り当て先の候補である。いまコア１０１およびコア１０２はいずれも割り当て済みのタスクの数が同じなので、識別番号が先のコア１０１に対象タスクが割り当てられる（ステップＳ１０４）。
【００５６】
次にタスクＨが対象タスクとして選択される（ステップＳ１０２）。タスクＨについて属性情報を見ると、タスクＧと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＧが割り当てられているコア１０１／１０２が、割り当て先の候補である。いまコア１０２の方がコア１０１よりも割り当て済みのタスクの数が少ないので、コア１０２に対象タスクが割り当てられる（ステップＳ１０４）。
【００５７】
次にタスクＩが対象タスクとして選択される（ステップＳ１０２）。タスクＩについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｈ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＩについて属性情報を見ると、未割り当てのタスクＪと関連性を有することが示されている（Ｓ１０５：ＹＥＳ）。したがってフローはステップＳ１０６に進む。割り当て済タスクが少ないコア１０３／１０４が割り当て先の候補である。いまコア１０３およびコア１０４はいずれも割り当て済みのタスクの数が同じなので、番号が先のコア１０３に対象タスクが割り当てられる（ステップＳ１０６）。
【００５８】
次にタスクＪが対象タスクとして選択される（ステップＳ１０２）。タスクＪについて属性情報を見ると、タスクＩと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＩが割り当て済のコア１０３／１０４が、割り当て先の候補である。いまコア１０４の方がコア１０３よりも割り当て済みのタスクの数が少ないので、コア１０４に対象タスクが割り当てられる（ステップＳ１０４）。
【００５９】
次にタスクＫが対象タスクとして選択される（ステップＳ１０２）。タスクＫについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｊ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＫについて属性情報を見ると、未割り当てのタスク（タスクＬ）とは関連性を有さないことが示されている（Ｓ１０５：ＮＯ）。したがってフローはステップＳ１０７に進む。この時点で割り当て済みのタスクが最も少ないコア１０３およびコア１０４が、割り当て先の候補である。ＯＳ５０は、番号が先のコア１０３に対象タスクを割り当てる（ステップＳ１０７）。
【００６０】
次にタスクＬが対象タスクとして選択される（ステップＳ１０２）。タスクＬについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｋ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。この時点で未割り当てのタスクは存在しない。したがって、対象タスクは未割り当てのタスクとは関連性を有さない（Ｓ１０５：ＮＯ）。フローはステップＳ１０７に進む。ＯＳ５０は、この時点で割り当て済みのタスクが最も少ないコア１０４に対象タスクを割り当てる（ステップＳ１０７）。
【００６１】
図１２は、タスクＧ〜Ｌの割り当て結果を例示する図である。このように、本実施形態によれば、各コアにより均等にタスクが割り当てられる。引き続き、図１２の状態からさらに新規タスクが発生した場合の、タスクの割り当てについて説明する。まずは、さらなる新規タスクの構造および属性情報について説明する。
【００６２】
図１３は、さらなる新規タスクを例示する図である。タスク群８０７およびタスク群８０８が新規タスクである。タスク群８０７は、タスクＯを含む。タスクＯは、他のタスクと関連性を有さない。タスク群８０８は、タスクＭおよびタスクＮを含む。タスクＭおよびタスクＮは、共通の入力データを用いるタスクである。この例ではタスクＭ〜Ｏの優先度は以下のとおり設定されている。
タスクＭ：優先度３
タスクＮ：優先度２
タスクＯ：優先度１（最高）
【００６３】
図１４は、タスクの属性情報を例示する図である。タスクＭおよびタスクＮが互いに関連性を有していることが示されている。
【００６４】
コアへのタスクの割り当ての説明に移る。ＯＳ５０は、図１３の新規タスクが発生したことを検知する（ステップＳ１００）。これらの新規タスクは、検出された時点では当然コアに割り当てられていない。したがって、フローはステップＳ１０１からＳ１０２に進む。ＯＳ５０は、新規タスクの中から対象タスクを選択する。具体的には、ＯＳ５０は、優先度が最も高いものを対象タスクとして選択する。したがって、まずはタスクＯが対象タスクとして選択される（ステップＳ１０２）。処理はステップＳ１０３に進む。タスクＯについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｌ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＯについて属性情報を見ると、未割り当てのタスク（タスクＭおよびタスクＮ）とは関連性を有さないことが示されている（Ｓ１０５：ＮＯ）。したがってフローはステップＳ１０７に進む。この時点で各コアに割り当て済みのタスクの数は同じであるので、コア１０１〜１０４が割り当て先の候補である。ＯＳ５０は、このうち番号が最先のコア１０１に対象タスクを割り当てる（ステップＳ１０７）。
【００６５】
次にタスクＭが対象タスクとして選択される（ステップＳ１０２）。タスクＭについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜ＬおよびＯ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＭについて属性情報を見ると、未割り当てのタスクＮと関連性を有することが示されている（Ｓ１０５：ＹＥＳ）。したがってフローはステップＳ１０６に進む。コア１０１／１０２、およびコア１０３／１０４に割り当て済みのタスクの数を比較すると、コア１０３／１０４の方が割り当て済タスクが少ないので割り当て先の候補となる。いまコア１０３およびコア１０４はいずれも割り当て済みのタスクの数が同じなので、番号が先のコア１０３に対象タスクが割り当てられる（ステップＳ１０６）。
【００６６】
次にタスクＮが対象タスクとして選択される（ステップＳ１０２）。タスクＮについて属性情報を見ると、タスクＭと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＭが割り当て済のコア１０３／１０４が、割り当て先の候補である。いまコア１０４の方がコア１０３よりも割り当て済みのタスクの数が少ないので、コア１０４に対象タスクが割り当てられる（ステップＳ１０４）。
【００６７】
図１５は、タスクＭ〜Ｏの割り当て結果を例示する図である。このように、本実施形態によれば、各コアにより均等にタスクが割り当てられる。
【００６８】
３−３．動作例２
図１６は、動作例２に係る割り当て済みのタスクを例示する図である。すなわち図１６は、現時点でのスケジュール情報を示している。この例では、タスクＡ〜Ｇがコア１０１〜１０４に割り当てられている。この状況で、タスクＨおよびタスクＩが新たに発生した例を考える。
【００６９】
図１７は、この例におけるタスクＨおよびタスクＩの属性情報を示す。タスクＨはタスクＥおよびタスクＩと関連性を有しており、タスクＩはタスクＨと関連性を有している。新規タスクに関し、これ以外の関連性はない。新規タスクのうち、タスクＨの優先度はタスクＩの優先度よりも高い。
【００７０】
まずタスクＨが対象タスクとして選択される（ステップＳ１０２）。タスクＨについて属性情報を見ると、割り当て済みのタスクＥと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＥが割り当てられているコア１０１／１０２が、割り当て先の候補である。いコア１０１およびコア１０２に割り当て済みのタスクの数は同じなので、識別番号が先のコア１０１に対象タスクが割り当てられる（ステップＳ１０４）。
【００７１】
図１８は、この時点のスケジュール情報を示す図である。
【００７２】
次にタスクＩが対象タスクとして選択される（ステップＳ１０２）。タスクＩについて属性情報を見ると、割り当て済みのタスクＨと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＨが割り当てられているコア１０１／１０２が、割り当て先の候補である。いまコア１０２の方がコア１０１よりも割り当て済みのタスクが少ない。したがって、コア１０２に対象タスクが割り当てられる（ステップＳ１０４）。
【００７３】
図１９は、動作例２によるタスクの割り当て結果を示す図である。
【００７４】
３−４．動作例３
動作例２と同じ割り当て済みのタスク（図１６）を考える。タスクＡ〜Ｇがコア１０１〜１０４に割り当てられている。この状況で、タスクＨおよびタスクＩが新たに発生した例を考える。
【００７５】
図２０は、動作例３におけるタスクＨおよびタスクＩの属性情報を示す。タスクＨはタスクＩと関連性を有しており、タスクＩはタスクＨと関連性を有している。新規タスクに関し、これ以外の関連性はない。新規タスクのうちタスクＨの優先度はタスクＩの優先度よりも高い。
【００７６】
まずタスクＨが対象タスクとして選択される（ステップＳ１０２）。タスクＨについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｇ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＨについて属性情報を見ると、未割り当てのタスクＩと関連性を有することが示されている（Ｓ１０５：ＹＥＳ）。したがってフローはステップＳ１０６に進む。コア１０１／１０２とコア１０３／１０４とを比較すると、コア１０３／１０４に割り当て済みのタスクの方が少ない。したがって、コア１０３／コア１０４が割り当て先の候補である。いまコア１０３の方がコア１０４よりも割り当て済みのタスクの数が少ないので、コア１０３に対象タスクが割り当てられる（ステップＳ１０６）。
【００７７】
図２１は、この時点でのスケジュール情報を示す図である。
【００７８】
次にタスクＩが対象タスクとして選択される（ステップＳ１０２）。タスクＩについて属性情報を見ると、割り当て済みのタスクＨと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＨが割り当てられているコア１０３が属するコア１０３／１０４が割り当て先の候補である。いまコア１０３および１０４に割り当て済みのタスクの数は同じである。したがって、識別番号の早いコア１０３に対象タスクが割り当てられる（ステップＳ１０４）。
【００７９】
図２２は、動作例３によるタスクの割り当て結果を示す図である。
【００８０】
３−５．動作例４
図２３は、動作例４に係る割り当て済みのタスクを示す図である。すなわち図２３は、現時点でのスケジュール情報を示している。この例では、タスクＡ〜ＧおよびＪがコア１０１〜１０４に割り当てられている。この状況で、タスクＨおよびタスクＩが新たに発生した例を考える。タスクＨおよびタスクＩの属性情報は、動作例３（図２０）と同じである。
【００８１】
まずタスクＨが対象タスクとして選択される（ステップＳ１０２）。タスクＨについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜ＧおよびＪ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＨについて属性情報を見ると、未割り当てのタスクＩと関連性を有することが示されている（Ｓ１０５：ＹＥＳ）。したがってフローはステップＳ１０６に進む。コア１０１／１０２とコア１０３／１０４とを比較すると、割り当て済みのタスクの数は同じである。コアに割り当て済みのタスクの最大数を比較すると、コア１０１／１０２が２つであり、コア１０３／１０４が３つである。したがって、コア１０１／１０２が割り当て先の候補となる。いまコア１０１およびコア１０２は割り当て済みのタスクの数が同じなので、識別番号の早いコア１０１に対象タスクが割り当てられる（ステップＳ１０６）。
【００８２】
図２４は、この時点でのスケジュール情報を示す図である。
【００８３】
次にタスクＩが対象タスクとして選択される（ステップＳ１０２）。タスクＩについて属性情報を見ると、割り当て済みのタスクＨと関連性を有することが示されている（Ｓ１０３：ＹＥＳ）。したがってフローはステップＳ１０４に進む。タスクＨが割り当てられているコア１０１が属するコア１０３／１０４が割り当て先の候補である。いまコア１０２の方がコア１０１よりも割り当て済みのタスクが少ない。したがって、コア１０２に対象タスクが割り当てられる（ステップＳ１０４）。
【００８４】
図２５は、動作例４によるタスクの割り当て結果を示す図である。動作例４（図２２）と対比すると、新規タスクの属性情報が同じであっても、その時点で割り当て済みのタスクの状況に応じて割り当て先が変わることがわかる。
【００８５】
３−６．動作例５
図２６は、動作例５に係る割り当て済みのタスクを例示する図である。すなわち図２６は、現時点でのスケジュール情報を示している。この例では、タスクＡ〜ＧおよびＪがコア１０１〜１０４に割り当てられている。タスクＧは２回発生しており、いずれもコア１０４に割り当て済みである。この状況で、タスクＨおよびタスクＩが新たに発生した例を考える。
【００８６】
図２７は、この例におけるタスクＨおよびタスクＩの属性情報を示す。タスクＨおよびタスクＩはいずれも、他のタスクと関連性を有してない。新規タスクのうち、タスクＨの優先度はタスクＩの優先度よりも高い。
【００８７】
まずタスクＨが対象タスクとして選択される（ステップＳ１０２）。タスクＨについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜ＧおよびＪ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。タスクＨについて属性情報を見ると、未割り当てのタスク（タスクＩ）とは関連性を有さないことが示されている（Ｓ１０５：ＮＯ）。したがってフローはステップＳ１０７に進む。この時点でコア１０３に割り当て済みのタスクの数が最も少ない。したがって、コア１０３に対象タスクが割り当てられる（ステップＳ１０７）。
【００８８】
図２８は、この時点でのスケジュール情報を示す図である。
【００８９】
次にタスクＩが対象タスクとして選択される（ステップＳ１０２）。タスクＩについて属性情報を見ると、割り当て済みのタスク（タスクＡ〜Ｇ、Ｊ、およびＨ）とは関連性を有さないことが示されている（Ｓ１０３：ＮＯ）。したがってフローはステップＳ１０５に進む。この時点で未割り当てのタスクはない。つまり対象タスクは未割り当てのタスクとは関連性を有さない（Ｓ１０５：ＮＯ）。したがってフローはステップＳ１０７に進む。この時点でコア１０１〜１０３に割り当て済みのタスクの数が最も少ない。したがって、このうち識別番号が最も早いコア１０１に対象タスクが割り当てられる（ステップＳ１０７）。
【００９０】
図２９は、動作例５によるタスクの割り当て結果を示す図である。
【００９１】
３−７．動作例６
図３０は、動作例６に係るタスクを示す図である。動作例６に係るタスクは、タスクＡ〜Ｇを含む。タスクＡ〜Ｅは、一連のパイプライン処理を構成する。タスクＦおよびＧはそれぞれ他のタスクとは独立している。この例では、タスクＡ〜Ｅが繰り返し発生する。
【００９２】
図３１は、動作例６に係るタスクの属性情報を示す図である。タスクＡはタスクＢと、タスクＢはタスクＡおよびＣと、タスクＣはタスクＢおよびＤと、タスクＤはタスクＣおよびＥと、タスクＥはタスクＤと、それぞれ関連性を有する。タスクＦおよびタスクＧは他のタスクと関連性を有さない。優先度は、高い方から順に、タスクＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇである。
【００９３】
図３２〜４２は、動作例６によるタスクの割り当てを示す図である。ここでは、タスクの発生、割り当て、および実行を時系列で示している。図の縦軸は、タスクの実行に要する時間を単位とする時間の経過を表している。ここでは説明を簡単にするため、各タスクの実行に要する時間は等しい例を用いる。ここでは、繰り返し発生する同種のタスクを区別するため、タスクの後に添字を付している。例えば「Ａ１」は１回目に発生したタスクＡを示している。この図には、タスク発生、タスク割り当て、およびタスク割り当て（比較例）の欄がある。タスク発生の欄には、その時刻に新たに発生したタスクが記載されている。例えば時刻ｔ１に、タスクＡ１、Ｂ１、Ｃ１、Ｄ１、Ｅ１、およびＦ１が発生している。タスク割り当ての欄には、その時刻から次の時刻までの間に実行されるタスクが記載されている。例えば時刻ｔ１から時刻ｔ２の間に、タスクＡ１、Ｂ１、およびＦ１が実行される。タスク割り当て（比較例）の欄には、比較例におけるタスク実行予定が記載されている。なお比較例においては、割り当て先がタスク毎にあらかじめ決められている。また、以下においては、比較例のタスク割り当てについては特に詳細な説明はしない。
【００９４】
時刻ｔ１において、タスクＡ１、Ｂ１、Ｃ１、Ｄ１、Ｅ１、およびＦ１が発生する。時刻ｔ１以前には、どのコアにも割り当て済タスクは無い。コア１０１にタスクＡ１、Ｄ１、およびＥ１が、コア１０２にタスクＢ１およびＣ１が、コア１０３にタスクＦ１が、それぞれ割り当てられる（図３２）。時刻ｔ２になった時点で１行目のタスクは実行が完了している。時刻ｔ２に発生するタスクは無い。
【００９５】
時刻ｔ３において、タスクＡ２、Ｂ２、Ｃ２、Ｄ２、Ｅ２、およびＧ１が発生する。この時点で、コア１０１にタスクＥ１が割り当て済である。コア１０３／１０４に割り当てられているタスクがゼロなので、まずタスクＡ２がコア１０３に割り当てられる。以下、すべてのタスクの割り当てが完了すると、コア１０１にタスクＥ１が、コア１０２にタスクＧ２が、コア１０３にタスクＡ２、Ｄ２、およびＥ２が、コア１０４にタスクＢ２およびＣ２が割り当てられる（図３３）。なお時刻ｔ３において実行済のタスクはハッチングで示している。以下の図において同様である。
【００９６】
時刻ｔ４において、タスクＦ２が発生する。この時点で、コア１０３にタスクＤ２およびＥ２が、コア１０４にタスクＣ２が割り当て済である。タスクＦ２は、コア１０１に割り当てられる（図３４）。
【００９７】
時刻ｔ５において、タスクＡ３、Ｂ３、Ｃ３、Ｄ３、およびＥ３が発生する。この時点で、コア１０３にタスクＥ２が割り当て済である。コア１０１にタスクＡ３、Ｄ３、およびＥ３が、コア１０２にタスクＢ３およびＣ３が割り当てられる（図３５）。時刻ｔ６に発生するタスクは無い。
【００９８】
時刻ｔ７において、タスクＡ４、Ｂ４、Ｃ４、Ｄ４、Ｅ４、およびＦ３が発生する。この時点で、コア１０１にタスクＥ３が割り当て済である。コア１０２にタスクＦ３が、コア１０３にタスクＡ４、Ｃ４、およびＥ４が、コア１０４にタスクＢ４およびＣ４が割り当てられる（図３６）。
【００９９】
時刻ｔ８において、タスクＧ２が発生する。この時点で、コア１０３にタスクＣ４およびＥ４が、コア１０４にタスクＣ４が割り当て済である。コア１０１にタスクＧ２が割り当てられる（図３７）。
【０１００】
時刻ｔ９において、タスクＡ５、Ｂ５、Ｃ５、Ｄ５、Ｅ５、およびＦ４が発生する。この時点で、コア１０３にタスクＥ４が割り当て済である。コア１０１にタスクＡ５、Ｄ５、およびＥ５が、コア１０２にタスクＢ５およびＣ５が、コア１０４にタスクＦ４が割り当てられる（図３８）。時刻ｔ１０において発生するタスクは無い。
【０１０１】
時刻ｔ１１において、タスクＡ６、Ｂ６、Ｃ６、Ｄ６、およびＥ６が発生する。この時点で、コア１０１にタスクＥ５が割り当て済である。コア１０３にタスクＡ６、Ｄ６、およびＥ６が、コア１０４にタスクＢ６およびＣ６が割り当てられる（図３９）。
【０１０２】
時刻ｔ１２において、タスクＦ５およびＧ３が発生する。この時点で、コア１０３にタスクＤ６およびＥ６が、コア１０４にタスクＣ６が割り当て済である。コア１０１にタスクＦ５が、コア１０２にタスクＧ３が割り当てられる（図４０）。
【０１０３】
時刻ｔ１３において、タスクＡ７、Ｂ７、Ｃ７、Ｄ７、およびＥ７が発生する。この時点で、コア１０３にタスクＥ６が割り当て済である。コア１０１にタスクＡ７、Ｄ７、およびＥ７が、コア１０２にタスクＢ７およびＣ７が割り当てられる（図４１）。時刻ｔ１４において発生するタスクは無い。
【０１０４】
時刻ｔ１５において、タスクＡ８、Ｂ８、Ｃ８、Ｄ８、Ｅ８、およびＦ６が発生する。この時点で、コア１０１にタスクＥ７が割り当て済である。コア１０２にタスクＦ６が、コア１０３にタスクＡ８、Ｄ８、およびＥ８が、コア１０４にタスクＢ８およびＣ８が割り当てられる（図４２）。
【０１０５】
時刻ｔ１６において、タスクＧ４が発生する。この時点で、コア１０３にタスクＤ８およびＥ８が、コア１０４にタスクＣ８が割り当て済である。コア１０１にタスクＧ４が割り当てられる（図４３）。
【０１０６】
以上で割り当てられたタスクは、時刻ｔ１８にはすべて実行が完了する。一方で比較例においては、割り当てられたタスクの実行が完了するのは時刻ｔ２１である。このように、本実施形態によれば、タスクがより効率的にコアに割り当てられる。これにより、ＣＰＵ１０のパフォーマンスが向上する。
【０１０７】
４．変形例
本発明は上述の実施形態に限定されるものではなく、種々の変形実施が可能である。以下、変形例をいくつか説明する。以下の変形例のうち２つ以上のものが組み合わせて用いられてもよい。
【０１０８】
４−１．変形例１
図４３は、変形例１に係る新規タスクの割り当て処理を示すフローチャートである。変形例１に係る処理は、タスクの関連性の種類およびＣＰＵのハードウェア構成（キャッシュメモリの構成）の組み合わせによって、タスク割り当てのアルゴリズムを変更する点が図７のフローと異なっている。以下この処理を、図７のフローと対比しつつ説明する。
【０１０９】
ステップＳ２００において、ＯＳ５０は、新規タスクが発生したか判断する。新規タスクが発生していないと判断された場合（Ｓ２００：ＮＯ）、ＯＳ５０は、新規タスクが発生するまで待機する。新規タスクが発生したと判断された場合（Ｓ２００：ＹＥＳ）、ＯＳ５０は、処理をステップＳ２０１に移行する。
ステップＳ２０１において、ＯＳ５０は、未割り当てのタスクがあるか判断する。未割り当てのタスクがあると判断された場合（Ｓ２０１：ＹＥＳ）、ＯＳ５０は、処理をステップＳ２０２に移行する。未割り当てのタスクがないと判断された場合（Ｓ２０１：ＮＯ）、ＯＳ５０は、処理をステップＳ２００に移行する。ステップＳ２０２において、ＯＳ５０は、未割り当てのタスクの中から、最も優先度が高い一のタスクを対象タスクとして選択する。ステップＳ２００〜Ｓ２０２の処理は、ステップＳ１００〜Ｓ１０２の処理に相当する。
【０１１０】
ステップＳ２０３において、ＯＳ５０は、割り当て制御テーブルを読み込む。割り当て制御テーブルは、タスクの割り当てアルゴリズムを決定するための情報が記録されたテーブルである。タスクの割り当てアルゴリズムは、タスク間の関連性およびＣＰＵのキャッシュメモリ構造に応じて決定される。
【０１１１】
まずタスクの関連性の分類について説明する。この例では、タスクの関連性が３つのカテゴリ（カテゴリα〜γという）に分類される。カテゴリαは、いわゆるパイプライン処理における関連性に相当する分類である。これは例えばタスク群８０１（図８）のような構造に相当する。例えば複合機で行われる画像処理ではデータサイズが大きいため、タスク間のデータ受け渡しのレイテンシが大きいとパフォーマンスに大きな悪影響を与える。したがって、この分類の処理においてはキャッシュヒット率が高いことが期待される。
【０１１２】
カテゴリβは、ＬＵＴを参照する処理における関連性に相当する分類であり、例えば、タスク群８０２（図８）のような構造に相当する。この処理は、あるデータテーブルを参照してデータを置換するような処理に用いられる。例えば複合機で行われる色空間変換の場合、参照されるＬＵＴのデータサイズが大きく、また画像により参照するデータが異なる。そのため、カテゴリαと比較すると、キャッシュのヒット率が高いことは期待されない。
【０１１３】
カテゴリγは、他のタスクとは独立した処理における関連性であり、例えば、タスク群８０３（図８）のような構造に相当する。この処理は、例えば、検知系の処理やインターフェース処理に用いられる。これらの処理ではキャッシュのヒット率が高くなることはほとんど期待されないし、その必要もない。
【０１１４】
以上の事情を考慮すると、一般に、タスク間の関連性の強さは、α＞β＞γとなる。したがってこの例では、関連性の強さに応じて、タスク割り当てのアルゴリズムを変更する。例えばソフトウェアをコンパイルするときに、各タスクについて他のタスクとの関連性を、上記の分類を含む情報として抽出することができる。
【０１１５】
図４４は、分類を含むタスク間の関連性を例示する図である。この例では、例えばタスクＡはタスクＢとカテゴリαの関連性を有することが示されている。また、タスクＪはタスクＣとカテゴリαの関連性を有し、かつタスクＩとカテゴリβの関連性を有することが示されている。
【０１１６】
図４５は、ＣＰＵのキャッシュメモリの構成を例示する図である。キャッシュメモリの構成は、例えばカテゴリＷ〜Ｚに分類される。カテゴリＷは、Ｌ２キャッシュを２つのコアで共有する構造に相当する。カテゴリＸは、Ｌ２キャッシュを４つのコアで共有する構造に相当する。カテゴリＹは、Ｌ２キャッシュを２つのコアで共有し、かつＬ３キャッシュを４つのコアで共有する構造に相当する。カテゴリＺは、Ｌ２キャッシュを４つのコアで共有し、かつＬ３キャッシュを４つのコアで共有する構造に相当する。
【０１１７】
図４６は、割り当て制御テーブルを例示する図である。割り当て制御テーブルには、ＣＰＵのキャッシュメモリ構造およびタスクの関連性の分類毎に、タスク割り当てのアルゴリズムを特定する情報が記録されている。この例では、タスク割り当てのアルゴリズムとして第１アルゴリズムおよび第２アルゴリズムが用いられる。第１アルゴリズムは、実施形態で説明したアルゴリズム、すなわち割り当て済タスクとの関連性を考慮したアルゴリズムである。第２アルゴリズムは、第１アルゴリズムと異なるアルゴリズムである。なお、カテゴリα〜γの分類は、適用される割り当てアルゴリズムに影響を与えているという意味において、タスク間の関連性の重みを示しているといえる。
【０１１８】
例えば、ＣＰＵ１０（図５）はカテゴリＷの構造を有しているので、カテゴリαの関連性を有するタスクについては第１アルゴリズムによるタスクの割り当てが、カテゴリβおよびγの関連性を有するタスクについては第２アルゴリズムによるタスクの割り当てが、それぞれ行われる。
【０１１９】
再び図４３を参照する。ステップＳ２０４において、ＯＳ５０は、割り当て済タスクの中に対象タスクと第１アルゴリズムを適用する関係にあるタスクが存在するか判断する。割り当て済タスクの中に対象タスクと第１アルゴリズムを適用する関係タスクが存在すると判断された場合（Ｓ２０４：ＹＥＳ）、ＯＳ５０は、処理をステップＳ２０５に移行する。割り当て済タスクの中に対象タスクと第１アルゴリズムを適用する関係にあるタスクが存在しないと判断された場合（Ｓ２０４：ＮＯ）、ＯＳ５０は、処理をステップＳ２０６に移行する。
【０１２０】
ステップＳ２０５において、ＯＳ５０は、対象タスクと第１アルゴリズムを適用する関係にあるタスクが割り当てられているコア群に、対象タスクを割り当てる。ステップＳ２０５の処理はステップＳ１０４の処理に相当する。ステップＳ２０５の処理を終えると、ＯＳ５０は、処理をステップＳ２０１に移行する。
【０１２１】
ステップＳ２０６において、ＯＳ５０は、未割り当てのタスクの中に対象タスクと第１アルゴリズムを適用する関係にあるタスクが存在するか判断する。未割り当てのタスクの中に対象タスクと第１アルゴリズムを適用する関係にあるタスクが存在すると判断された場合（Ｓ２０６：ＹＥＳ）、ＯＳ５０は、処理をステップＳ２０７に移行する。未割り当てのタスクの中に対象タスクと第１アルゴリズムを適用する関係にあるタスクが存在しないと判断された場合（Ｓ２０６：ＮＯ）、ＯＳ５０は、処理をステップＳ２０８に移行する。
【０１２２】
ステップＳ２０７において、ＯＳ５０は、複数のコア群のうち、割り当て済みのタスクが最も少ないコア群に属するコアにタスクを割り当てる。ステップＳ２０７の処理はステップＳ１０６の処理に相当する。ステップＳ１０６の処理を終えると、ＯＳ５０は、処理をステップＳ２０１に移行する。
【０１２３】
ステップＳ２０８において、ＯＳ５０は、コア１０１〜１０４のうち割り当て済みのタスクが最も少ないコアに対象タスクを割り当てる。ステップＳ２０８の処理はステップＳ１０７の処理に相当する。ステップＳ２０８の処理を終えると、ＯＳ５０は、処理をステップＳ２０１に移行する。
【０１２４】
変形例１においては、ＣＰＵのキャッシュメモリ構造との関係において効果が高いことが期待されるタスクに対してのみ、タスクの関連性を考慮したタスク割り当てが行われる。
【０１２５】
４−２．変形例２
図４７は、変形例２に係る新規タスクの割り当て処理を示すフローチャートである。変形例２に係る処理は、タスク間で共有されるデータのサイズを考慮する点において図７のフローと異なっている。以下この処理を、図７のフローと対比しつつ説明する。
【０１２６】
ステップＳ３００において、ＯＳ５０は、新規タスクが発生したか判断する。新規タスクが発生していないと判断された場合（Ｓ３００：ＮＯ）、ＯＳ５０は、新規タスクが発生するまで待機する。新規タスクが発生したと判断された場合（Ｓ３００：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０１に移行する。
ステップＳ３０１において、ＯＳ５０は、未割り当てのタスクがあるか判断する。未割り当てのタスクがあると判断された場合（Ｓ３０１：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０２に移行する。未割り当てのタスクがないと判断された場合（Ｓ３０１：ＮＯ）、ＯＳ５０は、処理をステップＳ３００に移行する。ステップＳ３０２において、ＯＳ５０は、未割り当てのタスクの中から、最も優先度が高い一のタスクを対象タスクとして選択する。ステップＳ３００〜Ｓ３０２の処理は、ステップＳ１００〜Ｓ１０２の処理に相当する。
【０１２７】
ステップＳ３０３において、ＯＳ５０は、割り当て済タスクの中に対象タスクと関連性を有するタスクが存在するか判断する。割り当て済タスクの中に対象タスクと関連性を有するタスクが存在すると判断された場合（Ｓ３０３：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０４に移行する。割り当て済タスクの中に対象タスクと関連性を有するタスクが存在しないと判断された場合（Ｓ３０４：ＮＯ）、ＯＳ５０は、処理をステップＳ３０７に移行する。ステップＳ３０３の処理はステップＳ１０３の処理に相当する。
【０１２８】
ステップＳ３０４において、ＯＳ５０は、対象タスクおよび対象タスクと関連性を有するタスクとが共有するデータのサイズが、Ｌ１キャッシュのサイズより大きいか判断する。タスク間で共有するデータのサイズは、属性情報により示される。Ｌ１キャッシュのサイズは、構成情報により示される。ＯＳ５０は、これらの情報を参照して判断する。共有するデータのサイズがＬ１キャッシュのサイズより大きいと判断された場合（Ｓ３０４：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０５に移行する。共有するデータのサイズがＬ１キャッシュのサイズ以下であると判断された場合（Ｓ３０４：ＮＯ）、ＯＳ５０は、処理をステップＳ３０６に移行する。
【０１２９】
ステップＳ３０５において、ＯＳ５０は、対象タスクと関連性を有するタスクが割り当て済タスク群に対象タスクを割り当てる。ステップＳ３０５の処理はステップＳ１０４の処理に相当する。ステップＳ３０５の処理を終えると、ＯＳ５０は、処理をステップＳ３０１に移行する。
【０１３０】
ステップＳ３０６において、ＯＳ５０は、対象タスクと関連性を有するタスクが割り当て済タスクに対象タスクを割り当てる。ステップＳ３０６の処理を終えると、ＯＳ５０は、処理をステップＳ３０１に移行する。
【０１３１】
ステップＳ３０７において、ＯＳ５０は、未割り当てのタスクの中に対象タスクと関連性を有するタスクが存在するか判断する。未割り当てのタスクの中に対象タスクと関連性を有するタスクが存在すると判断された場合（Ｓ３０７：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０８に移行する。未割り当てのタスクの中に対象タスクと関連性を有するタスクが存在しないと判断された場合（Ｓ３０７：ＮＯ）、ＯＳ５０は、処理をステップＳ３１０に移行する。ステップＳ３０７の処理はステップＳ１０５の処理に相当する。
【０１３２】
ステップＳ３０８において、ＯＳ５０は、対象タスクおよび対象タスクと関連性を有するタスクとが共有するデータのサイズが、Ｌ１キャッシュのサイズより大きいか判断する。共有するデータのサイズがＬ１キャッシュのサイズより大きいと判断された場合（Ｓ３０８：ＹＥＳ）、ＯＳ５０は、処理をステップＳ３０９に移行する。共有するデータのサイズがＬ１キャッシュのサイズ以下であると判断された場合（Ｓ３０８：ＮＯ）、ＯＳ５０は、処理をステップＳ３１０に移行する。
【０１３３】
ステップＳ３０９において、ＯＳ５０は、複数のコア群のうち、割り当て済タスクが最も少ないコア群に属するコアにタスクを割り当てる。ステップＳ３０９の処理はステップＳ１０６の処理に相当する。ステップＳ３０９の処理を終えると、ＯＳ５０は、処理をステップＳ３０１に移行する。
【０１３４】
ステップＳ３１０において、ＯＳ５０は、コア１０１〜１０４のうち割り当て済みのタスクが最も少ないコアに対象タスクを割り当てる。ステップＳ３１０の処理はステップＳ１０７の処理に相当する。ステップＳ３１０の処理を終えると、ＯＳ５０は、処理をステップＳ３０１に移行する。
【０１３５】
変形例２においては、タスク間で共有されるデータのサイズがＬ１キャッシュのサイズ以下である場合には、これらのタスクは同じコアに割り当てられる。
【０１３６】
４−３．変形例３
変形例１において、ＣＰＵのキャッシュメモリ構造を考慮せず、タスク間の関連性の種類に応じてタスクを割り当ててもよい。
【０１３７】
４−４．変形例４
図４８は、変形例４に係る属性情報を例示する図である。この例では、属性情報において入力データの関連性と出力データの関連性とが区別されている。この図は、図８のタスク群８０１〜８０３における属性情報を示している。タスクＡの出力データがタスクＢの入力データとなっているので、タスクＡの「出力」の項にタスクＢが記録されている。同様に、タスクＢの「入力」の項にタスクＡが、「出力」の項にタスクＣが記録されている。
【０１３８】
このような属性情報を用いることにより、タスク間の関連性がより詳細に定義される。この場合、図７のフローは例えば以下のとおり改変される。ステップＳ１０３において、ＯＳ５０は、割り当て済タスクの中に対象タスクと入力データの関連性を有するタスクがあるか判断する。図４８のタスクＢが対象タスクである場合、対象タスクは、割り当て済タスクＡと入力データの関連性を有すると判断される。タスクＡが対象タスクであった場合、割り当て済タスクにタスクＢが含まれていても、対象タスクと入力データの関連性を有する割り当て済タスクは無いと判断される。割り当て済タスクの中に対象タスクと入力データの関連性を有するタスクがあると判断された場合（Ｓ１０３：ＹＥＳ）、ＯＳ５０は、処理をステップＳ１０４に移行する。割り当て済タスクの中に対象タスクと入力データの関連性を有するタスクが無いと判断された場合（Ｓ１０３：ＮＯ）、ＯＳ５０は、処理をステップＳ１０５に移行する。
【０１３９】
ステップＳ１０５において、ＯＳ５０は、未割り当てのタスクの中に対象タスクと出力データの関連性を有するタスクがあるか判断する。図４８のタスクＢが対象タスクである場合、対象タスクは、未割り当てのタスクにタスクＡが含まれていても、対象タスクと出力データの関連性を有するタスクは無いと判断される。タスクＡが対象タスクであった場合、未割り当てのタスクＢは対象タスクと出力データの関連性を有すると判断される。
【０１４０】
４−５．変形例５
ステップＳ１０３等において対象タスクと割り当て済タスクとの関連性を判断する際に参照する属性情報は、記憶手段５５に独立して記憶されているものに限定されない。「独立して記憶されている」とは、スケジュール情報等の他の情報とは別に記憶されていることをいう。スケジュール情報すなわち割り当て情報に、割り当て済タスクの属性情報を含めてもよい。具体的には以下のとおりである。
【０１４１】
スケジュール情報に記録されていない種類のタスクを新たにスケジュール情報に記録する際、ＯＳ５０は、記憶手段５５に独立して記憶されている属性情報を参照して、対象タスクの属性情報を、対象タスクと割り当て先コアとの関係とともに、スケジュール情報に追加する。
【０１４２】
図４９は、変形例５におけるスケジュール情報を例示する図である。この例では、コア１０１にタスクＡが、コア１０２にタスクＢおよびＣが、コア１０３にタスクＤが、コア１０４にタスクＥが、それぞれ割り当て済である。スケジュール情報には、コアとタスクとの対応関係に加え、各タスクの属性情報が含まれている。例えば、タスクＥの属性情報として、タスクＤおよびＦと関連性を有することが記録されている。なおこの例では、入力データの関連性と出力データの関連性とは区別されていない。
【０１４３】
図４９の状態でタスクＦの割り当てを考える。ＯＳ５０は、スケジュール情報を参照する。すると、タスクＦは割り当て済のタスクＥと関連性を有することが示されている。したがって、ＯＳ５０は、対象タスクが割り当て済タスクと関連性を有すると判断する（Ｓ１０３：ＹＥＳ）。実施形態においては、ステップＳ１０３の判断を行うため、スケジュール情報に加え、それとは別個の属性情報にアクセスする必要があった。これに対し変形例５においては、ＯＳ５０はスケジュール情報にアクセスするだけで判断を行う。
【０１４４】
４−６．変形例６
図５０は、変形例６におけるスケジュール情報を例示する図である。スケジュール情報は、変形例５で説明したように、割り当て済タスクの属性情報も含んでいる。入力データの関連性と出力データの関連性とは区別されていない。ここでは、初期化手段５７の機能の詳細について説明する。
【０１４５】
いま、図５０のようにタスクＡ１〜Ｆ１が割り当てられた状態で、これらのタスクが実行される前にタスクＡ２〜Ｅ２が発生した例を考える。まずタスクＡ２が対象タスクとなる。ＯＳ５０は、スケジュール情報を参照し、割り当て済タスクの中に対象タスクと関連性を有するタスクが存在するか判断する。スケジュール情報にはタスクＢ１の属性情報として、タスクＡと関連を有することが記録されている。したがって、ＯＳ５０は、割り当て済タスクの中に対象タスク（タスクＡ２）と関連性を有するタスク（タスクＢ１）が存在すると判断する（Ｓ１０３：ＹＥＳ）。したがって、タスクＡ２はコア１０２に割り当てられ、以下、タスクＢ２〜Ｅ２もコア１０１／１０２に割り当てられる。
【０１４６】
しかし、例えば、タスクＡ１〜Ｅ１が第１ページの画像処理に関するものであり、タスクＡ２〜Ｅ２が第２ページの画像処理に関するものである場合、共有されるデータが無いことから、キャッシュヒット率の向上という観点ではタスクＡ１〜Ｅ１とタスクＡ２〜Ｅ２とを同じコア群に割り当てる意義は無い。ところが、図５０のスケジュール情報を参照してタスクＡ２〜Ｅ２を割り当てようとすると、タスクＡ２の割り当てを決定する際に、タスクＡとタスクＢとの関連性に引きずられ、タスクＡ２はタスクＢ１が割り当てられているコア群に割り当てられてしまう。これは、タスク割り当ての偏りを生じさせる原因となる。
【０１４７】
変形例６において、ＯＳ５０は、まず対象タスクが新たなページのタスクとなったときに、スケジュール情報に含まれている属性情報を、主記憶装置３０上の記憶領域にコピーする。この例でタスクには処理の対象となるページを特定する情報が含まれており、ＯＳ５０は、この情報を参照して対象タスクが新たなページのタスクとなったと判断する。
【０１４８】
割り当て済タスクの属性情報をコピーすると、ＯＳ５０は、スケジュール情報に記録されている属性情報のうち、消去フラグが「消去」を示しているものを消去すなわち初期化する。一連のパイプライン処理のうち２番目のタスク（この例ではタスクＢ）の属性情報のうち入力データを共有するタスク（この例ではタスクＡ）との関連性を示す情報の消去フラグが「消去」を示している。これ以外の属性情報の消去フラグは「消去」を示していない。
【０１４９】
図５１は、属性情報の一部が消去されたスケジュール情報を例示する図である。属性情報の消去を行った後で、ＯＳ５０は、ステップＳ１０３の判断に進む。ここで、割り当て済タスクの属性情報には、タスクＡとの関連性を示す情報は含まれていない（Ｓ１０３：ＮＯ）。したがって処理はステップＳ１０５に進む。未割り当てのタスクとの関連性を判断するときは、ＯＳ５０は、スケジュール情報を参照する。あるいは、ＯＳ５０は、コピーされた属性情報を参照してもよい。この例では、対象タスクは未割り当てのタスクと関連性を有すると判断される（Ｓ１０５：ＹＥＳ）ので、ステップＳ１０６において、ＯＳ５０は、割り当て済タスクが最も少ないタスク群１０３／１０４に対象タスクを割り当てる。ＯＳ５０は、対象タスクと割り当て先との対応関係に加え、コピーされた属性情報に含まれる関連性の情報を、スケジュール情報に書き込む。この例によれば前述の問題が解消され、より偏りの少ない割り当てが行われる。
【０１５０】
４−７．他の変形例
ＣＰＵ１０の構成は図５に例示したものに限定されない。コアの数やキャッシュメモリの階層構造はあくまで例示である。ＣＰＵ１０は、少なくとも、第１キャッシュメモリを共用する２つのコアと、第１キャッシュメモリと別の第２キャッシュメモリを用いる少なくとも１つのコアを有して入ればよい。第１キャッシュメモリが３つ以上のコアで共用されてもよい。また、ＣＰＵ１０は、Ｌ２キャッシュの下層にＬ３キャッシュを有していてもよい。
【０１５１】
また、ＣＰＵ１０は、物理的に１つのチップに複数のコアおよびキャッシュメモリを搭載したものに限定されない。複数のＣＰＵチップで１つのキャッシュメモリを共用する情報処理装置に対し、本発明が適用されてもよい。
【０１５２】
さらに、実施形態における「複数のコア」は物理的に異なる複数のコアに限定されない。物理的に１つのコアが、時分割で論理的に（擬似的に）複数のコアとして用いられてもよい。
【０１５３】
本発明に係る情報処理装置は、図２に例示した画像形成装置１に限定されない。ＣＰＵ１０を用いて複数の処理を並列実行するものであれば、情報処理装置はどのような装置であってもよい。例えば、情報処理装置は、パーソナルコンピュータ、スマートフォン、またはタブレット端末であってもよい。
【０１５４】
情報処理装置のソフトウェア構成は図３に例示したものに限定されない。ＯＳおよびアプリケーションによる機能の分担はあくまで例示である。情報処理装置は、処理を発生させるソフトウェアコンポーネント、および発生した処理を実行させるコアを決定するソフトウェアコンポーネントを有していればよい。
【符号の説明】
【０１５５】
１…画像形成装置、１０…ＣＰＵ、２０…メモリコントローラー、３０…主記憶装置、４０…ＩＯコントローラー、４１…補助記憶装置、４２…画像読み取りユニット、４３…画像形成ユニット、４４…通信ユニット、５０…ＯＳ、５１…取得手段、５２…取得手段、５３…取得手段、５４…取得手段、５５…記憶手段、５６…割り当て手段、５７…初期化手段、５８…検知手段、６１〜６３…アプリケーション、９０…ＣＰＵ、１０１〜１０４…コア、１１１〜１１４…キャッシュメモリ（Ｌ１）、１２１〜１２２…キャッシュメモリ（Ｌ２）、９０１〜９０４…コア、９１１〜９１４…キャッシュメモリ（Ｌ１）、９２１〜９２２…キャッシュメモリ（Ｌ２）
【図１】
0006631124.tif 000002
【図２】
0006631124.tif 000003
【図３】
0006631124.tif 000004
【図４】
0006631124.tif 000005
【図５】
0006631124.tif 000006
【図６】
0006631124.tif 000007
【図７】
0006631124.tif 000008
【図８】
0006631124.tif 000009
【図９】
0006631124.tif 000010
【図１０】
0006631124.tif 000011
【図１１】
0006631124.tif 000012
【図１２】
0006631124.tif 000013
【図１３】
0006631124.tif 000014
【図１４】
0006631124.tif 000015
【図１５】
0006631124.tif 000016
【図１６】
0006631124.tif 000017
【図１７】
0006631124.tif 000018
【図１８】
0006631124.tif 000019
【図１９】
0006631124.tif 000020
【図２０】
0006631124.tif 000021
【図２１】
0006631124.tif 000022
【図２２】
0006631124.tif 000023
【図２３】
0006631124.tif 000024
【図２４】
0006631124.tif 000025
【図２５】
0006631124.tif 000026
【図２６】
0006631124.tif 000027
【図２７】
0006631124.tif 000028
【図２８】
0006631124.tif 000029
【図２９】
0006631124.tif 000030
【図３０】
0006631124.tif 000031
【図３１】
0006631124.tif 000032
【図３２】
0006631124.tif 000033
【図３３】
0006631124.tif 000034
【図３４】
0006631124.tif 000035
【図３５】
0006631124.tif 000036
【図３６】
0006631124.tif 000037
【図３７】
0006631124.tif 000038
【図３８】
0006631124.tif 000039
【図３９】
0006631124.tif 000040
【図４０】
0006631124.tif 000041
【図４１】
0006631124.tif 000042
【図４２】
0006631124.tif 000043
【図４３】
0006631124.tif 000044
【図４４】
0006631124.tif 000045
【図４５】
0006631124.tif 000046
【図４６】
0006631124.tif 000047
【図４７】
0006631124.tif 000048
【図４８】
0006631124.tif 000049
【図４９】
0006631124.tif 000050
【図５０】
0006631124.tif 000051
【図５１】
0006631124.tif 000052