(57)【要約】  ステート評価関数値生成部１３１は、複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成する。統合評価関数値生成部１３２は、各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成する。最適配置探索部１３３は、統合評価関数値に基づいて、複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う。
2012056609.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成するステート評価関数値生成手段と、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成する統合評価関数値生成手段と、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う最適配置探索手段と、を備えるタスク配置最適化システム。
【請求項２】
前記ステート評価関数生成手段は、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の絶対値とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項３】
前記ステート評価関数生成手段は、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の自乗とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項４】
前記ステート評価関数生成手段は、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項５】
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のタスク配置最適化システム。
【請求項６】
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のタスク配置最適化システム。
【請求項７】
外部から入力される前記ステート・タスクセット対応表を保持するステート・タスクセット対応表保持手段と、
外部から入力される前記タスクセットパラメータを保持するタスクセットパラメータ保持手段と、をさらに備えることを特徴とする請求項１乃至請求項６のいずれか１項に記載のタスク配置最適化システム。
【請求項８】
前記他最適配置探索手段は、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする請求項１乃至請求項７のいずれか１項に記載のタスク配置最適化システム。
【請求項９】
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化方法。
【請求項１０】
複数のプロセッサ・コアを有するシステムにおけるタスク配置の最適化処理をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体であって、
前記最適化処理は、
前記システムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＡＭＰ方式のマルチコアシステムを対象としたタスク配置最適化システム、タスク配置最適化方法、及びタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体に関する。
【背景技術】
【０００２】
近年のデジタル機器の高性能化及び低消費電力化要求の高まりをうけ、組み込みＬＳＩ（Large Scale Integration）に複数のプロセッサ・コア（以下、単にコアとも記載する。）を搭載するマルチコア構成が注目を集めている。このＬＳＩのマルチコア化は、システム制御を目的とするリアルタイムシステム等においても重要な技術となってきている。【０００３】
マルチコアシステムは、主にＳＭＰ（Symmetric Multi Processing）方式とＡＭＰ（Asymmetric Multi Processing）方式に大別される。【０００４】
ＳＭＰ方式では、コアの空き状況、現在実行中のタスクの優先度等に応じてタスク切り替えが行われ、それぞれのタスクはいずれのコア上でも実行でされ得る構成となる。このため、自動的に負荷分散が行うことが可能となり、システム全体の性能は向上する。しかし、自動的な負荷分散はリアルタイム性能の予測を困難とするため、ＳＭＰ方式をリアルタイムシステムに適応することは困難である。【０００５】
一方、ＡＭＰ方式では、各タスクが特定のコア上でのみ実行される機能分散型の構成となる。このため、ＡＭＰ方式は、システムの挙動が予測できることが重要なリアルタイムシステム、特定のハードウェアが接続しているコアが限定されるシステム等に好適である。【０００６】
このようなＡＭＰ方式のマルチコアシステムでは、タスクをどのコアに配置するかにより性能が異なってくる。このため、ＡＭＰ方式のマルチコアシステムでは、最適な実行状態となるように様々なタスク配置を探索し、最適配置を決定する必要がある。【０００７】
特許文献１には、複数のコアを備えたマルチコアプロセッサ向けのソフトウェアチューニングを効率的に行うチューニング支援装置に関する技術が開示されている。特許文献１に記載のチューニング支援装置の構成を図１４に示す。【０００８】
当該チューニング支援装置では、はじめに粒度情報取得部２０１が、各コアに割り当てられた粒度に関する情報（粒度情報）を取得する。ここで粒度とは、たとえばプロセッサが行う処理の単位であって、タスク、関数、さらには関数を構成する処理の総称である。【０００９】
構造情報生成部２０４は、取得された粒度情報に基づいて、タスク毎あるいはタスクが有する関数毎に出現回数を算出し、算出された出現回数に関する情報（構造情報）を生成する。【００１０】
依存情報生成部２０６は、取得された粒度情報に基づいて、タスク毎あるいはタスクが有する関数毎の、他タスクあるいは関数への依存に関する情報（依存情報）を生成する。出力部２０３がこれらの各情報を出力する。【００１１】
この構成により、チューニング支援装置は、負荷分散のための構造情報を効率的に解析、及び管理することができる。この解析情報を用いることにより、マルチプロセッサにおいて、性能良くタスクをコアに配置することができる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−２６４７３４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、特許文献１に記載のチューニング支援装置によるタスク配置によっては、ある動作ステートにおいて最適なタスク配置とはならないという問題が生じ得る。当該問題について以下に述べる。【００１４】
一般的なシステム上では、常に全てのタスクが動作しているわけではなく、動作中の動作ステートに応じて動作するタスクの組み合わせが異なる。上述のチューニング支援装置では、全てのタスクを用いてタスク配置を最適化すること、特定の動作ステートでのみ動作するタスクセットを用いてタスク配置を最適化することを想定している。これにより、全てのタスクまたは考察対象の動作ステートで動作するタスクセットに関するタスク配置が最適化され、負荷のバランスを均等にすることができる。しかし、当該チューニング支援装置において考慮されていない動作ステートでは、負荷のバランスが偏るなど、著しく性能が悪化するケースが生じ得る。【００１５】
本発明は、上述の問題を解決するために主になされたものであり、特定の動作ステートにおいて性能劣化が生じないマルチプロセッサシステムのタスク配置を実現するタスク配置最適化システム、タスク配置最適化方法、タスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体を提供することを主たる目的とする。
【課題を解決するための手段】
【００１６】
本発明にかかるタスク配置最適化システムの一態様は、
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成するステート評価関数値生成手段と、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成する統合評価関数値生成手段と、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う最適配置探索手段と、を備える、ものである。【００１７】
本発明にかかるタスク配置最適化方法の一態様は、
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、ものである。【００１８】
本発明にかかるタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体の一態様は、
複数のプロセッサ・コアを有するシステムにおけるタスク配置の最適化処理をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体であって、
前記最適化処理は、
前記システムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、ものである。
【発明の効果】
【００１９】
本発明によれば、特定の動作ステートにおいて性能劣化が生じないマルチプロセッサシステムのタスク配置を実現するタスク配置最適化システム、タスク配置最適化方法、タスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】実施の形態１にかかるタスク配置最適化システムの構成を示すブロック図である。
【図２】実施の形態１にかかるタスク配置最適化システムの処理の流れを示すフローチャートである。
【図３】実施の形態２にかかるタスク配置最適化システムの構成を示すブロック図である。
【図４】実施例１にかかるステート・タスクセット対応表の具体例を示す図である。
【図５】実施例１にかかるタスクセットパラメータの具体例を示す図である。
【図６】実施例１にかかるステート・タスクセット対応表と、タスクパラメータセットと、の統合表である。
【図７】特許文献１にかかるチューニング支援装置の最適化の動作を示す図である。
【図８】実施例１にかかるタスク配置最適化システム最適化の動作を示す図である。
【図９】実施例４にかかるタスクパラメータを示す図である。
【図１０】図９に示されるタスクセットパラメータに記述された依存関係を示す図である。
【図１１】実施例４にかかるステート・タスクセット対応表を示す図である。
【図１２】実施例４において、各動作ステートにおいて動作するタスク、及び有効なコア間依存のみを太線により示す図である。
【図１３】実施の形態１にかかるタスク配置最適化システムの構成を示すブロック図である。
【図１４】特許文献１にかかるチューニング支援装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２１】
＜実施の形態１＞
以下、図面を参照して本発明の実施の形態について説明する。ＡＭＰ方式のマルチコアシステムにおいては、タスクをどのコアに配置するかによって性能が異なってくる。本実施の形態にかかるタスク配置最適化システムは、各タスクが特定のコアで実行される機能分散型の構成をとるＡＭＰ方式のマルチコアシステムを設計・実装する際に、性能のよいタスクの配置となるよう最適化を行うことを目的とする。以下の説明では、本実施の形態にかかるタスク配置最適化システムによる最適化対象のＡＭＰ方式のマルチコアシステムを、単にマルチコアシステムと表記する。
【００２２】
図１は、本実施の形態にかかるタスク配置最適化システムの全体構成を示すブロック図である。タスク配置最適化システム１は、タスクセットパラメータ保持部１１と、ステート・タスクセット対応表保持部１２と、最適化部１３と、を備える構成である。
【００２３】
タスクセットパラメータ保持部１１は、外部から入力されるタスクセットパラメータを保持する。タスクセットパラメータとは、タスクセット（マルチコアシステムに配置される複数のタスクの集合）を構成する各タスクの特性を表わす情報である。タスクセットパラメータには、起動周期、他のタスクとの依存関係、実行時間、必要メモリサイズ等がタスク毎に記載されている。
【００２４】
ステート・タスクセット対応表保持部１２は、マルチコアシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表を保持する。
【００２５】
マルチコアシステムを含む一般的なシステムは、動作状況に応じてその動作ステートを変化させながら動作する。システムの動作ステートが変化することにより、そのシステムの動作は様々に変化する。このため、一般的に特定の動作ステートの際に動作するタスクは、全タスクのうち一部のタスクとなる。ステート・タスクセット対応表は、システムの動作ステートの一覧と、動作ステート毎に動作するタスクセットの対応と、を表わすものである。
【００２６】
最適化部１３は、ステート評価関数値生成部１３１と、統合評価関数値生成部１３２と、最適配置探索部１３３と、を備える。
【００２７】
ステート評価関数値生成部１３１は、特定動作ステートに対応したタスクセットを対象として、ステート評価関数値を生成する。詳細には、ステート評価関数値生成部１３１は、タスクセットパラメータ保持部１１からタスクセットパラメータを読み出し、ステート・タスクセット対応表保持部１２からステート・タスクセット対応表を読み出す。そして、ステート評価関数値生成部１３１は、これらの情報を基に特定動作ステートに対応したタスクセットを対象として、ステート評価関数値を生成する。一般的に、検証対象の全動作ステートに対してそれぞれステート評価関数値が生成される。ステート評価関数値は、動作ステート毎の、タスク配置の良さを示す評価値である。
【００２８】
統合評価関数値生成部１３２は、検討対象の全動作ステートについてのステート評価関数値を統合し、統合評価関数値を生成する。
【００２９】
最適配置探索部１３３は、統合評価関数値生成部１３２が出力する統合評価関数値がより良いタスク配置を探索する。最も単純な探索手法として全探索が挙げられる。全探索では、全ての配置候補を順に生成し、その中で最も統合評価関数値が良好な配置を探索結果として表示画面等に出力する。しかしながら、効率的な探索を実現するため、枝限定法、グリーディー法、遺伝的アルゴリズム等の一般に知られる高速化手法を用いることが望ましい。
【００３０】
なお、タスクセットパラメータ、ステート・タスクセット対応表、ステート評価関数値、及び統合評価関数値の具体例は、後述する実施例１等により説明する。
【００３１】
次に、図２のフローチャートを参照して、本実施の形態にかかるタスク配置最適化システム１の動作について説明する。
【００３２】
初めに、タスクセットパラメータ保持部１１は、外部から入力されたタスクセットパラメータを保持する（ステップＳ１０１）。次に、ステート・タスクセット対応表保持部１２は、外部から入力されたステート・タスクセット対応表を保持する（ステップＳ１０２）。
【００３３】
なお、上述のステップＳ１０１及びＳ１０２は順不同の処理であり、ステップＳ１０２を先に実行することや、ステップＳ１０１及びステップＳ１０２を同時に実行することも可能である。
【００３４】
最適配置探索部１３３は、タスク配置候補（どのタスクをどのコアに配置するかの候補データ）を生成する（Ｓ１０３）。そして、ステート評価関数値生成部１３１は、生成したタスク配置候補について、各動作ステートのステート評価関数値を生成する（Ｓ１０４）。
【００３５】
統合評価関数値生成部１３２は、ステート評価関数値生成部１３１が生成したステート評価関数値を統合した統合評価関数値を生成する（Ｓ１０５）。
【００３６】
最適配置探索部１３３は、統合評価関数値を考慮し、タスク配置の探索終了条件を満たすか否かを判定する（Ｓ１０６）。タスク配置の探索終了条件を満たさない場合（Ｓ１０６：Ｎｏ）、再度Ｓ１０３から処理を繰り返す。一方、タスク配置の探索終了条件を満たす場合（Ｓ１０６：Ｙｅｓ）、最適配置探索部１３３は、タスク配置の最適化結果を出力して処理を終了する。
【００３７】
ここで、タスク配置の探索終了条件とは、どのような最適化アルゴリズムを最適配置探索部１３３が採用するかにより異なる。最適化アルゴリズムとして単純な全探索を用いる場合、探索終了条件は全タスク配置候補の生成終了となる。この場合、最適配置探索部１３３は、最適な統合評価関数値を持つタスク配置候補を最適化結果として出力する。一方、他の一般的な最適化アルゴリズムを採用する場合、統合評価関数値がこれ以上良くなることがないと判定した場合や、タスク配置候補の生成を一定回数繰り返しても統合評価関数値が改善しない場合等、を考慮して探索終了条件を定める。
【００３８】
続いて、本実施の形態にかかるタスク配置最適化システムの効果について説明する。上述のように、ステート評価関数値生成部１３１は、ステート・タスクセット対応表と、タスクセットパラメータと、に基づいて、動作ステート毎にタスク配置の良さを示すステート評価関数値を算出する。統合評価関数値生成部１３２は、このステート評価関数値を全動作ステートについて統合し、マルチコアシステム全体としての評価値である統合評価関数値を算出する。この統合評価関数値を用いてタスク配置の最適化を行うことにより、それぞれの動作ステートにおける処理性能を考慮することが可能になる。これにより、特定動作ステートにおいて著しく性能劣化が起こる問題を回避することができる。
【００３９】
特許文献１に記載のチューニング装置のように全タスクを用いてタスク配置の最適化を行う場合、実際には性能充足するマルチコアシステムにおいても、性能が足りない（たとえばリアルタイムシステムの場合、デッドラインを充足しない等）と誤判定される場合がある。これは、前述の通り、一般的なシステムにおいては全てのタスクが常に動作しているわけではない。例えば、ある２つのタスクは、マルチコアシステム内の動作ステートに応じてどちらか一方しか動作しない等のケースがあり、全てのタスクをまとめて扱うことが不適切なケースがある。
【００４０】
本実施の形態にかかるタスク配置最適化システムは、動作ステート毎のステート評価関数値を算出し、それを統合して最適化を行うことにより、実際には同時に動作しないタスクを考慮した最適化を行うことが可能になる。これにより、本実施の形態にかかるタスク配置最適化システムは、全タスクを用いてタスク配置の最適化を行う場合には性能が足りないと判定されるようなマルチコアシステムを対象とした場合でも、適切に性能充足する最適なタスク配置を出力することができる。
【００４１】
＜実施の形態２＞
次に、本発明の実施の形態２にかかるタスク配置最適化システムを、図面を参照して詳細に説明する。図３は、本実施の形態にかかるタスク配置最適化システムの全体構成を示すブロック図である。本実施の形態にかかるタスク配置最適化システムでは、実施の形態１において説明した処理がコンピュータ５によりプログラムとして実行されることを特徴とする。プログラムとして実行される各処理は、実施の形態１における処理と略同一である。
【００４２】
コンピュータ５は、プロセッサ５１と、記憶装置５２と、を備える。記憶装置５２は、例えばハードディスク等が該当する。プロセッサ５１がプログラムを実行することにより、タスク配置最適化システムとして動作する。
【００４３】
タスクセットは、タスクセット定義ファイル６２上に表現される。ステート・タスクセット対応表は、ステート・タスクセット対応表定義ファイル６３上に表現される。タスクセット定義ファイル６２及びステート・タスクセット対応表定義ファイル６３は、タスク配置最適化プログラム６１が実行される際にプロセッサ５１から読み出される。プロセッサ５１は、タスク配置最適化プログラム６１を実行することにより、タスク配置の最適化を行う。プロセッサ５１は、タスク配置の最適化結果をタスク最適配置定義ファイル６４として記憶装置５２上に出力する。
【００４４】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（random access memory））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００４５】
上述のように、プログラムの形式であっても、ＡＭＰ方式のマルチプロセッサシステムのタスク配置の最適化を実現することができる。
【００４６】
＜実施例１＞
次に、具体的な実施例を用いて実施の形態１にかかるタスク配置最適化システムの動作を説明する。以下の実施例１〜４では、タスク配置最適化システム１が対象とするマルチコアシステムは、コア０及びコア１を備える。
【００４７】
本例では、ステート評価関数値生成部１３１は、コア０の実行時間と、コア１の実行時間と、の差の絶対値をステート評価関数値として生成する。統合評価関数値生成部１３２は、各動作ステートにおけるステート評価関数値の和を統合評価関数値として生成する。最適配置探索部１３３は、統合評価関数値が最小となる配置を探索する最適化を行う。
【００４８】
図４は、ステート・タスクセット対応表の具体例を示す図である。このように、マルチコアシステムが取り得る全動作ステートと、当該動作ステートにて実行されるタスクの関係が示される。図４の例では、マルチコアシステムは、動作ステートとしてＳ１、Ｓ２、Ｓ３、Ｓ４の４つを取り得ることが示されている。さらに、ステートＳ１では、タスクＡ及びタスクＢが実行され、ステートＳ２では、タスクＣ、タスクＥ、タスクＦが実行されることが示されている。同様に、ステートＳ３では、タスクＣ〜Ｇが実行され、ステートＳ２では、タスクＥ、タスクＦ、タスクＧが実行されることが示されている。
【００４９】
図５は、タスクセットパラメータの例を示す図である。本実施例では、各タスクの実行に必要な実行時間がパラメータとして表記されている。図６は、図４のステート・タスクセット対応表の具体例と、図５のタスクセットパラメータの具体例と、を統合した表である。
【００５０】
以下に、図４のステート・タスクセット対応表、図５のタスクセットパラメータが入力された場合の、タスク配置最適化システムによるタスク配置の最適化について説明する。最適化は、各コアに割り当てられたタスクの実行時間を平均化させる観点により行われる。
【００５１】
ここで、ステートＳ１に注目した最適化は独立して行い、ステートＳ２〜Ｓ４の最適化において、特許文献１に記載の最適化手法を用いて行った最適化と、実施の形態１に記載の最適化手法と、の比較を考える。
【００５２】
特許文献１に記載の最適化手法において、最も多くのタスクが動作するステートＳ３に着目した最適化を行った場合を考察する。図７は、当該最適化の様子を示す図である。
【００５３】
図７において、各タスク行には、そのタスクが該当動作ステートにて実行される場合に図５にて示した実行時間が表記されている。このうち、破線に囲まれたタスク（タスクＡ，Ｃ，Ｄ）をコア０に、それ以外のタスクをコア１に配置している。図７において、コア０、コア１の行には、それぞれのステート（Ｓ１〜Ｓ４）における各コアに割り当てられたタスクの実行時間の合計を示している。
【００５４】
ここで、図７の例では、ステートＳ３に着目した最適化が行われている。すなわち、ステートＳ３において、コア０における実行時間と、コア１における実行時間が完全にバランス（すなわち同じ３２という値となる）している。一方、このタスク配置の場合、ステートＳ４ではコア１でのみタスクが実行され、コア０ではまったくタスクが実行されていない。すなわち、ステートＳ４では、タスク配置がアンバランスな状態となってしまっている。
【００５５】
続いて、実施の形態１にかかるタスク配置最適化システムによる最適化結果について例示する。上述の図７のタスク配置での統合評価関数値は２＋５＋０＋３２＝３９となっている。しかしながら、実際には統合評価関数値がさらに小さいタスク配置が存在する。本例のタスク配置最適化システム１は、統合評価関数値が最小となる配置を最適配置とする。最適配置探索部１３３には、様々な既存技術の最適化アルゴリズムが応用可能である。最適配置探索部１３３が算出した最適配置の一例を図８に示す。
【００５６】
図８の配置における統合評価関数値は、２＋９＋４＋０＝１５となり、図７に示した統合評価関数値よりも小さくなっている。図７と比較して、図８の配置は、各ステートでの実行時間のバランスが取れている配置となっている。
【００５７】
＜実施例２＞
実施例２では、実施例１のタスク配置最適化システム１の応用例として、ステート評価関数値生成部１３１がステート評価関数値を実行時間の差の自乗とするものである。すなわち、ステート評価関数値生成部１３１が、コア０の実行時間と、コア１の実行時間と、の差の自乗をステート評価関数値として生成する。統合評価関数値生成部１３２は、各動作ステートにおけるステート評価関数値の和を統合評価関数値として生成する。
【００５８】
以下の説明では、実施例１のタスク配置最適化システム１によっては、統合評価関数値が同一となる２つの配置例について考える。一つ目の配置Ａは、ステートＳ１、Ｓ２、Ｓ３、Ｓ４におけるステート評価関数値が夫々１、１、１、５となる。二つ目の配置Ｂは、ステートＳ１、Ｓ２、Ｓ３、Ｓ４におけるステート評価関数値が夫々２、２、２、２となる。実施例１のタスク配置最適化システム１によりこれらの配置の統合評価関数値を生成すると、配置Ａは１＋１＋１＋５＝８、配置Ｂは２＋２＋２＋２＝８となり同一値となる。
【００５９】
実施例２のタスク配置最適化システム１では、ステート評価値関数値は実行時間の差の自乗であり、統合評価関数値は配置Ａでは１＋１＋１＋２５＝２８、配置Ｂでは４＋４＋４＋４＝１６となる。ここで、最適配置探索部１３３は、統合評価関数値が小さい配置を最適配置とするため、配置Ｂが適切な配置と判断する。
【００６０】
このように、実施例２では、バランスのずれ（ステート評価関数値のずれ）が大きい動作ステートが統合評価関数値に与える影響が大きくなる。そのため、極端にバランスが悪い動作ステートが生じることを極力避けたい場合に、本例のようにステート評価関数値を実行時間の差の自乗とすることが有効である。
【００６１】
＜実施例３＞
実施例３では、実施例１のタスク配置最適化システム１の変形例として、統合評価関数をステート評価関数値の積とする。すなわち、タスク評価関数値生成部１３１は、コア０の実行時間と、コア１の実行時間と、の差の絶対値をステート評価関数値として生成する。統合評価関数値生成部１３２は、各動作ステートにおけるステート評価関数値の積を統合評価関数値として生成する。
【００６２】
ここで、実施例２と同様の配置Ａ及び配置Ｂについて検討する。この場合、統合評価関数値は、配置Ａでは１×１×１×５＝５、配置Ｂでは２×２×２×２＝１６となる。ここで、最適配置探索部１３３は、統合評価関数値が小さい配置を最適配置とするため、配置Ａが適切な配置と判断する。
【００６３】
このように、実施例３では、バランスのずれが小さい動作ステート（ステート評価関数値の差の小さい動作ステート）が数多くある場合に、総合評価関数値が小さくなる。このような性質を持つため、多少負荷バランスが悪い動作ステート（ステート評価関数値の差の大きい動作ステート）が存在する場合であっても、なるべく多くの動作ステートの負荷バランスを小さくしたい場合に実施例３の方式（統合評価関数値をステート評価関数値の積とする方式）が有効である。
【００６４】
ただし、統合評価関数値をステート評価関数値の乗算とする場合、ステート評価関数値が一つでも０であると他の動作ステートのステート評価関数値に関わらず統合評価関数値が０となる。このため、ステート評価関数値の算出方法を定める際に、値が０とならないように注意する必要がある。
【００６５】
＜実施例４＞
実施例４のタスク配置最適化システム１として、タスク間の依存が記載されたタスクパラメータセットが入力される例を示す。ステート評価関数値生成部１３１は、動作ステート毎にコア間依存の数をステート評価関数値として出力する。
【００６６】
コア間依存とは、依存関係が有るタスクが存在し、それらのタスクが異なるコアをまたがって配置されている状態をいう。一例として、タスクＡと、タスクＡに依存するタスクＢという２つのタスクのみを考える。タスクＡとタスクＢが異なるコアに配置された場合、コア間依存数は１となる。一方、タスクＡとタスクＢが同じコアに配置された場合、コア間依存数は０となる。一般的に、コアをまたがってデータ転送をする場合には一定の時間を必要とすることから、コア間依存数は極力少ないことが望ましい。
【００６７】
ここで、全動作ステートにおいて、各コアに割り当てるタスク数が同一または１つのみ異なることを条件に、コア間依存数を最小化する最適化の例を示す。
【００６８】
まず、タスクセットパラメータの例を図９に示す。図９において、依存関係の列には、そのタスクに依存しているタスクの情報が記述されている。例えば、タスクＡの行には、タスクＢ、タスクＣ、及びタスクＧと記載されている。このことより、タスクＢ、タスクＣ、及びタスクＧは、タスクＡに依存していることを示す。すなわち、タスクＢ、タスクＣ、及びタスクＧは、タスクＡの処理結果を利用して、それぞれの処理を行う。
【００６９】
図１０は、図９に示されるタスクセットパラメータに記述された依存関係を図示したものである。
【００７０】
図１１は、システムの動作ステートの一覧、及びその動作ステート毎に動作するタスクのセットの対応を表わすステート・タスクセット対応表を示す。図１１の例では、システムの動作ステートとしてＳ５、Ｓ６、Ｓ７の３つがある。ステートＳ５においては、タスクＡ、タスクＢ、タスクＣ、タスクＤ、タスクＦが動作する。ステートＳ６においては、タスクＡ、タスクＣ、タスクＥ、タスクＦ、タスクＧが動作する。同様に、ステートＳ７においては、タスクＡ、タスクＣ、タスクＦが動作する。
【００７１】
まず、特許文献１に記載の最適化手法による最適配置の決定について説明する。当該手法では、動作ステート毎にどのタスクが動作するかは考慮されない。そのため、タスクセット全体の依存を考えた場合に最も依存が少ない箇所にてタスク配置を分割する配置候補が出力される。図１０の例では、分割位置２１によりタスク配置を分割する。すなわち、タスクＡ、タスクＢ、タスクＧがコア０、タスクＣ、タスクＤ、タスクＥ、タスクＦがコア１（もしくはその逆）となる配置候補が出力される。
【００７２】
ここで、当該手法によるタスク配置候補（図１０における分割位置２１で分割したタスク配置）におけるコア間依存数を以下に示す。図１２は、各動作ステートにおいて動作するタスク、及び有効なコア間依存のみを太線により示したものである。図１２より明らかなように、特許文献１に記載の最適化手法では全ての動作ステートにおいてコア間依存が１つ存在する。
【００７３】
次に、本実施例のタスク配置最適化システム１による最適化について説明する。上述のように、ステート評価関数値生成部１３１は、動作ステート毎のコア間依存数をステート評価関数値として出力する。統合評価関数生成部１３２は、このステート評価関数値を統合した統合評価関数値を算出する。最適配置探索部１３３は、この統合評価関数値を用いて最適化を行う。これにより、図１０及び図１２における分割位置２１以外の分割位置が候補となり得る。
【００７４】
ここで、図１０及び図１２における分割位置２２をタスク配置候補とする場合、ステート評価関数値は、ステートＳ５、Ｓ６、Ｓ７において夫々１、１、０となり、統合評価関数値は１＋１＋０＝２となる（図１１  ステート評価関数値（実施例４）欄）。これは、特許文献１の手法における配置例での統合評価関数値が１＋１＋１＝３（図１１  ステート評価関数値（関連手法）欄）となることから、本例のタスク配置最適化システム１は、よりよい評価値を持つ配置、すなわちタスクＡ、タスクＢ、タスクＣ、タスクＧがコア０に、タスクＤ、タスクＥ、タスクＦがコア１（もしくはその逆）に配置する最適化結果を出力することが可能になる。
【００７５】
上述のように、本例では、ステートＳ７においてコア間依存数が０となる配置を出力することが可能となり、より性能のよいタスク配置を算出することが可能となる。
【００７６】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。例えば、上述の最適化部１３の各処理部の処理を異なるハードウェアで分散して実行してもよい。
【００７７】
なお、本実施の形態１にかかるタスク配置最適化システム１の最小構成を図１３に示す。本構成は、タスクセットパラメータ及びステート・タスクセット対応表が直接ステート評価関数値生成部１３１に供給される点を除いて、図１の構成と同様である。
【００７８】
上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００７９】
（付記１）
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成するステート評価関数値生成手段と、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成する統合評価関数値生成手段と、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う最適配置探索手段と、を備えるタスク配置最適化システム。
【００８０】
（付記２）
前記ステート評価関数生成手段は、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の絶対値とすることを特徴とする付記１に記載のタスク配置最適化システム。
【００８１】
（付記３）
前記ステート評価関数生成手段は、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の自乗とすることを特徴とする付記１に記載のタスク配置最適化システム。
【００８２】
（付記４）
前記ステート評価関数生成手段は、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記１に記載のタスク配置最適化システム。
【００８３】
（付記５）
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記１乃至付記４のいずれか１項に記載のタスク配置最適化システム。
【００８４】
（付記６）
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記１乃至付記４のいずれか１項に記載のタスク配置最適化システム。
【００８５】
（付記７）
外部から入力される前記ステート・タスクセット対応表を保持するステート・タスクセット対応表保持手段と、
外部から入力される前記タスクセットパラメータを保持するタスクセットパラメータ保持手段と、をさらに備えることを特徴とする付記１乃至付記６のいずれか１項に記載のタスク配置最適化システム。
【００８６】
（付記８）
前記他最適配置探索手段は、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記１乃至付記７のいずれか１項に記載のタスク配置最適化システム。
【００８７】
（付記９）
複数のプロセッサ・コアを有するシステムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化方法。
【００８８】
（付記１０）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の絶対値とすることを特徴とする付記９に記載のタスク配置最適化方法。
【００８９】
（付記１１）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の自乗とすることを特徴とする付記９に記載のタスク配置最適化方法。
【００９０】
（付記１２）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記９に記載のタスク配置最適化方法。
【００９１】
（付記１３）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記９乃至付記１２のいずれか１項に記載のタスク配置最適化方法。
【００９２】
（付記１４）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記９乃至付記１２のいずれか１項に記載のタスク配置最適化方法。
【００９３】
（付記１５）
前記タスクの配置の最適化を行う処理では、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記９乃至付記１４のいずれか１項に記載のタスク配置最適化方法。
【００９４】
（付記１６）
複数のプロセッサ・コアを有するシステムにおけるタスク配置の最適化処理をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体であって、
前記最適化処理は、
前記システムの動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、各動作ステートに対してステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合した統合評価関数値を生成し、
前記統合評価関数値に基づいて、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【００９５】
（付記１７）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の絶対値とすることを特徴とする付記１６に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【００９６】
（付記１８）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、各プロセッサ・コアに割り当てたタスクの実行時間の合計値の差の自乗とすることを特徴とする付記１６に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【００９７】
（付記１９）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記１６に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【００９８】
（付記２０）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記１６乃至付記１９のいずれか１項に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【００９９】
（付記２１）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記１６乃至付記１９のいずれか１項に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【０１００】
（付記２２）
前記タスクの配置の最適化を行う処理では、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記１６乃至付記２１のいずれか１項に記載のタスク配置最適化プログラムが格納された非一時的なコンピュータ可読媒体。
【０１０１】
この出願は、２０１０年１０月２８日に出願された日本出願特願２０１０−２４１７０３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１０２】
本発明は、例えば、マルチプロセッサシステムのタスク配置を支援する各種システムに応用可能である。当該システムは、例えば一般的なコンピュータに組み込まれ得る。
【符号の説明】
【０１０３】
１  タスク配置最適化システム
１１  タスクパラメータセット保持部
１２  ステート・タスクセット対応表保持部
１３  最適化部
１３１  ステート評価関数値生成部
１３２  統合評価関数値生成部
１３３  最適配置探索部
５  コンピュータ
５１  プロセッサ
５２  記憶装置
６１  タスク配置最適化プログラム
６２  タスクセット定義ファイル
６３  ステート・タスクセット対応表定義ファイル
６４  タスク最適配置定義ファイル
２０１  粒度情報取得部
２０２  粒度情報登録部
２０３  出力部
２０４  構造情報生成部
２０５  構造情報登録部
２０６  依存情報生成部
２０７  依存情報登録部
２０８  性能情報登録部
【図１】
2012056609.tif 000003
【図２】
2012056609.tif 000004
【図３】
2012056609.tif 000005
【図４】
2012056609.tif 000006
【図５】
2012056609.tif 000007
【図６】
2012056609.tif 000008
【図７】
2012056609.tif 000009
【図８】
2012056609.tif 000010
【図９】
2012056609.tif 000011
【図１０】
2012056609.tif 000012
【図１１】
2012056609.tif 000013
【図１２】
2012056609.tif 000014
【図１３】
2012056609.tif 000015
【図１４】
2012056609.tif 000016
【手続補正書】
【提出日】平成25年4月12日(2013.4.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のプロセッサ・コアを有するシステムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成するステート評価関数値生成手段と、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成する統合評価関数値生成手段と、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う最適配置探索手段と、を備えるタスク配置最適化システム。
【請求項２】
前記ステート評価関数生成手段は、前記最適配置探索手段によって割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の絶対値を前記ステート評価関数値とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項３】
前記ステート評価関数生成手段は、前記最適配置探索手段によって割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の自乗を前記ステート評価関数値とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項４】
前記ステート評価関数生成手段は、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする請求項１に記載のタスク配置最適化システム。
【請求項５】
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のタスク配置最適化システム。
【請求項６】
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする請求項１乃至請求項４のいずれか１項に記載のタスク配置最適化システム。
【請求項７】
外部から入力される前記ステート・タスクセット対応表を保持するステート・タスクセット対応表保持手段と、
外部から入力される前記タスクセットパラメータを保持するタスクセットパラメータ保持手段と、をさらに備えることを特徴とする請求項１乃至請求項６のいずれか１項に記載のタスク配置最適化システム。
【請求項８】
前記他最適配置探索手段は、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする請求項１乃至請求項７のいずれか１項に記載のタスク配置最適化システム。
【請求項９】
複数のプロセッサ・コアを有するシステムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成し、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化方法。
【請求項１０】
複数のプロセッサ・コアを有するシステムにおけるタスク配置の最適化処理をコンピュータに実行させるプログラムであって、
前記最適化処理は、
前記システムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成し、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
（付記１）
複数のプロセッサ・コアを有するシステムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成するステート評価関数値生成手段と、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成する統合評価関数値生成手段と、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う最適配置探索手段と、を備えるタスク配置最適化システム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００８０
【補正方法】変更
【補正の内容】
【００８０】
（付記２）
前記ステート評価関数生成手段は、前記最適配置探索手段によって割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の絶対値を前記ステート評価関数値とすることを特徴とする付記１に記載のタスク配置最適化システム。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００８１
【補正方法】変更
【補正の内容】
【００８１】
（付記３）
前記ステート評価関数生成手段は、前記最適配置探索手段によって割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の自乗を前記ステート評価関数値とすることを特徴とする付記１に記載のタスク配置最適化システム。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００８２
【補正方法】変更
【補正の内容】
【００８２】
（付記４）
前記ステート評価関数生成手段は、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記１に記載のタスク配置最適化システム。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００８３
【補正方法】変更
【補正の内容】
【００８３】
（付記５）
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記１乃至付記４のいずれか１項に記載のタスク配置最適化システム。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００８４
【補正方法】変更
【補正の内容】
【００８４】
（付記６）
前記統合評価関数値生成手段は、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記１乃至付記４のいずれか１項に記載のタスク配置最適化システム。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００８５
【補正方法】変更
【補正の内容】
【００８５】
（付記７）
外部から入力される前記ステート・タスクセット対応表を保持するステート・タスクセット対応表保持手段と、
外部から入力される前記タスクセットパラメータを保持するタスクセットパラメータ保持手段と、をさらに備えることを特徴とする付記１乃至付記６のいずれか１項に記載のタスク配置最適化システム。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８６
【補正方法】変更
【補正の内容】
【００８６】
（付記８）
前記他最適配置探索手段は、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記１乃至付記７のいずれか１項に記載のタスク配置最適化システム。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
（付記９）
複数のプロセッサ・コアを有するシステムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成し、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化方法。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
（付記１０）
前記ステート評価関数値を生成する処理では、割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の絶対値を前記ステート評価関数値とすることを特徴とする付記９に記載のタスク配置最適化方法。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
（付記１１）
前記ステート評価関数値を生成する処理では、割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の自乗を前記ステート評価関数値とすることを特徴とする付記９に記載のタスク配置最適化方法。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
（付記１２）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記９に記載のタスク配置最適化方法。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００９１
【補正方法】変更
【補正の内容】
【００９１】
（付記１３）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記９乃至付記１２のいずれか１項に記載のタスク配置最適化方法。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００９２
【補正方法】変更
【補正の内容】
【００９２】
（付記１４）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記９乃至付記１２のいずれか１項に記載のタスク配置最適化方法。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００９３
【補正方法】変更
【補正の内容】
【００９３】
（付記１５）
前記タスクの配置の最適化を行う処理では、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記９乃至付記１４のいずれか１項に記載のタスク配置最適化方法。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００９４
【補正方法】変更
【補正の内容】
【００９４】
（付記１６）
複数のプロセッサ・コアを有するシステムにおけるタスク配置の最適化処理をコンピュータに実行させるプログラムであって、
前記最適化処理は、
前記システムの動作状況に応じて変化する動作ステートの一覧及び動作ステート毎に動作するタスクセットの対応を示すステート・タスクセット対応表と、タスクの配置の際の参照情報となる前記タスクセットを構成する各タスクの特性を示すタスクセットパラメータと、に基づいて、前記動作ステート毎のタスクは位置の良好度を示す評価値であるステート評価関数値を生成し、
各動作ステートの前記ステート評価関数値を統合したマルチコアシステム全体としての良好度を示す評価値である統合評価関数値を生成し、
前記統合評価関数値の前記良好度を最大化する配置を探索することにより、前記複数のプロセッサ・コアの各々に割り当てるタスクの配置の最適化を行う、タスク配置最適化プログラム。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００９５
【補正方法】変更
【補正の内容】
【００９５】
（付記１７）
前記ステート評価関数値を生成する処理では、割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の絶対値を前記ステート評価関数値とすることを特徴とする付記１６に記載のタスク配置最適化プログラム。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００９６
【補正方法】変更
【補正の内容】
【００９６】
（付記１８）
前記ステート評価関数値を生成する処理では、割り当てられたタスクを前記複数のプロセッサ・コアの各々が実行するときの実行時間を前記複数のプロセッサ・コアごとに合計して合計値を求め、前記プロセッサ・コア間の前記合計値の差の自乗を前記ステート評価関数値とすることを特徴とする付記１６に記載のタスク配置最適化プログラム。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００９７
【補正方法】変更
【補正の内容】
【００９７】
（付記１９）
前記ステート評価関数値を生成する処理では、前記ステート評価関数値を、プロセッサ・コア間の依存数とすることを特徴とする付記１６に記載のタスク配置最適化プログラム。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００９８
【補正方法】変更
【補正の内容】
【００９８】
（付記２０）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総和を前記統合評価関数値とすることを特徴とする付記１６乃至付記１９のいずれか１項に記載のタスク配置最適化プログラム。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
（付記２１）
前記統合評価関数値を生成する処理では、各動作ステートの前記ステート評価関数値の総乗を前記統合評価関数値とすることを特徴とする付記１６乃至付記１９のいずれか１項に記載のタスク配置最適化プログラム。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
（付記２２）
前記タスクの配置の最適化を行う処理では、前記統合評価関数値が小さいタスクの配置候補を、優先的に最適配置として選択することを特徴とする付記１６乃至付記２１のいずれか１項に記載のタスク配置最適化プログラム。
【国際調査報告】
2012056609.tif 000017
2012056609.tif 000018
2012056609.tif 000019
2012056609.tif 000020