(57)【要約】複数の周期タスクから構成される開発対象のシステムにおいて、スケジューリング可能な複数のタスク配置の中から性能がよい配置を探索可能な自動最適化システムを提供する。複数のコアを有するマルチコア向けのタスク配置最適化システムが、コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する。前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する。探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する。
2011102219.tif 000002
【特許請求の範囲】
【請求項１】
複数のコアを有するマルチコア向けのタスク配置最適化システムにおいて、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、
前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、
を備えることを特徴とするタスク配置最適化システム。
【請求項２】
請求項１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、既にコアに配置したタスクを用いて算出した前記評価関数値を用いて前記限界値を算出する既固定タスク累積応答時間算出指示部を有することを特徴とするタスク配置最適化システム。
【請求項３】
請求項１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
各コア内で最低優先度の既にコアに配置したタスクである既固定タスクの応答時間をそれぞれのコアについて比較して、当該比較の結果最も短い応答時間に残りのタスク数を乗じることで限界値を算出する未固定タスク最短応答時間積算部を有することを特徴とするタスク配置最適化システム。
【請求項４】
請求項１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を全て合計することで限界値を算出する未固定タスク実行時間合計部を有することを特徴とするタスク配置最適化システム。
【請求項５】
請求項１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を昇順にソートし、未固定タスク１つ毎に、昇順にソートされた未固定タスクの実行時間に、未固定タスク数÷コア数の小数点以下を繰り上げたものを乗じた値を積算し、未固定タスク数を１つ減じる操作を全ての未固定タスクについて繰り返すことで限界値を算出する未固定タスク実行時間積算部を有することを特徴とするタスク配置最適化システム。
【請求項６】
前記探索部は、既に配置を固定したタスクの数が規定値より少ない場合には、前記限定部による限定を行わないよう抑止する限定抑止部を更に備えることを特徴とする請求項２乃至５の何れか１項に記載のタスク配置最適化システム。
【請求項７】
予め近似解探索を行うことにより、前記探索部より高速にタスク配置候補を発見しておき、発見したタスク配置候補を前記高評価候補保持部に登録する近似解探索部を更に備えることを特徴とする請求項１乃至６の何れか１項に記載のタスク配置最適化システム。
【請求項８】
複数のコアを有するマルチコア向けのタスク配置最適化方法において、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出ステップと、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索ステップと、
前記探索ステップにより探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持ステップと、
を備えることを特徴とするタスク配置最適化方法。
【請求項９】
複数のコアを有するマルチコア向けのタスク配置最適化システムに組み込まれるタスク配置最適化プログラムにおいて、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、
前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、
を備えるシステムとしてコンピュータを機能させることを特徴とするタスク配置最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はタスク配置に関し、より詳細にはリアルタイムシステム用マルチコア向けのタスク配置に関する。
【背景技術】
【０００２】
近年のデジタル機器の高性能化と低消費電力化要求の高まりを受け、組み込みＬＳＩ(Large Scale Integration)に複数のプロセッサを搭載するマルチコア（Multi-core）構成が有望な解決手段として注目を集めている。このようなマルチコア化は、システムの制御を目的とするリアルタイムシステム等においても主要な流れになりつつある。【０００３】
一方で、このようなマルチコアを搭載したリアルタイムシステムにおいては、並列に実行されるアプリケーションがデッドラインミスすることなくスケジューリング可能であることを保障する必要がある。この課題を解決する手法の一例としては、特許文献１に記載されている「リアルタイムスケジューリング可能性判定方法及びリアルタイムシステム」が挙げられる。【０００４】
特許文献１に記載の技術においては、マルチコアを搭載したリアルタイムシステムにおいて、一つのタスクの実行に同時に複数のプロセッサを必要とする場合のスケジューリング可能性判定方法を提供している。【０００５】
次に、図１３を参照して特許文献１に記載の技術について説明する。なお図１３は特許文献１の図２に相当する図である。図１３に示されるスケジューリング可能性判定部３００が以下に示す判定方法によりスケジューリングが可能か否かを判定する。
具体的には、【０００６】
Ｌｋ：タスクｋがデッドラインミスを起こす場合には、ある期間の実際の平均負荷が必ずこれ以上となる値【０００７】
Ｕｋ，ｉ：タスクｋがデッドラインミスを起こす場合に、タスクｋの平均負荷期間におけるタスクｉの平均単一負荷時間以上になっていることが保障されている値
Ｍｉ：タスクｉによって同時に使用されるプロセッサ数
と定義した場合において、
全てのタスクが
Σｉ＝１…Ｎ Ｍｉ＊Ｕｋ，ｉ≦Ｌｋ【０００８】
を満たす場合にリアルタイムスケジューリングすることが可能であると判定する。このような方法を用いることにより、特許文献１に記載の技術では、一つのタスクの実行に同時に複数のプロセッサを必要とする場合のスケジューリング可能性が判定できる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特許第４０１６０１０号
【非特許文献】
【００１０】
【非特許文献１】白石洋充／竹垣盛一著「リアルタイムシステムとその応用」朝倉書店、２００１年９月１日、ｐｐ．３５−５６
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述したように特許文献１に記載の技術を用いることによりスケジューリングが可能か否かが判定できる。【００１２】
しかしながら、この特許文献１に記載の技術に代表されるような、一般的な技術には下述するような複数の問題点が存在する。【００１３】
第１の問題点は、スケジューリング可能な複数のタスク配置の中から性能が良い配置を探索できないことである。【００１４】
その理由は、一般的な技術ではリアルタイムスケジューリングが可能か否かのみ判定が可能であり、スケジューリングが可能な複数の候補それぞれの性能の良さは判定できないためである。【００１５】
第２の問題点は、リアルタイムシステムにおいてシステムの安定性の観点から重要な指標である、デッドラインからの余裕度を大きくできないことである。【００１６】
その理由は、一般的な技術のリアルタイムスケジューリングが可能か否かを判定する手法では、デッドラインからの余裕度が大きい場合も小さい場合も区別なく扱われるからである。【００１７】
そこで、本発明は、スケジューリング可能な複数のタスク配置の中から性能が良い配置を探索可能な、リアルタイムシステム用マルチコア向けタスク配置最適化システム、その方法及びそのプログラムを提供することを第１の目的とする。【００１８】
また、本発明は、リアルタイムシステムにおいてシステムの安定性の観点から重要な指標である、デッドラインからの余裕度を大きくすることが可能なリアルタイムシステム用マルチコア向けタスク配置最適化システム、その方法及びそのプログラムを提供することを第２の目的とする。
【課題を解決するための手段】
【００１９】
本発明の第１の観点によれば、複数のコアを有するマルチコア向けのタスク配置最適化システムにおいて、コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、を備えることを特徴とするタスク配置最適化システムが提供される。【００２０】
本発明の第２の観点によれば、複数のコアを有するマルチコア向けのタスク配置最適化方法において、コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出ステップと、前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索ステップと、前記探索ステップにより探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持ステップと、を備えることを特徴とするタスク配置最適化方法が提供される。【００２１】
本発明の第３の観点によれば、複数のコアを有するマルチコア向けのタスク配置最適化システムに組み込まれるタスク配置最適化プログラムにおいて、コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、を備えるシステムとしてコンピュータを機能させることを特徴とするタスク配置最適化プログラム提供される。
【発明の効果】
【００２２】
本発明によれば、スケジューリング可能な複数のタスク配置の中から性能がよい配置を探索可能となる。【００２３】
その理由は、タスク配置候補の性能の良好さを表す指標である評価関数値を算出し、この評価関数値を用いて最適化を行うことにより、性能がよいタスク配置が得られるからである。【００２４】
また、本発明によれば、リアルタイムシステムにおいてシステムの安定性の観点から重要な指標である、デッドラインからの余裕度を大きくすることが可能となる。【００２５】
その理由は、コア配置決定対象の複数のタスクの各々の応答時間（タスク起動が指示されてから、そのタスクの実行が終了するまでの時間）の累積値を算出し、コア配置決定対象の複数のタスクの各々の応答時間の累積値を最小化する最適化を行うことにより、各タスクの応答時間が極力短くなるタスク配置が得られるからである。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施形態及び各実施例における基本的構成を表すブロック図である。
【図２】本発明の実施形態及び各実施例における累積応答時間算出部の基本的構成を表す図である。
【図３】本発明のハードウェア及びソフトウェアによる実装例（１／２）について示した図である。
【図４】本発明のハードウェア及びソフトウェアによる実装例（２／２）について示した図である
【図５】本発明の実施形態及び各実施例における動作について説明するための分枝図である。
【図６】本発明の実施形態及び各実施例における基本的動作を表すフローチャートである。
【図７】本発明の実施例１における限定部について示すブロック図である。
【図８】本発明の実施例２における限定部について示すブロック図である。
【図９】本発明の実施例３における基本的構成を表すブロック図である。
【図１０】本発明の実施例３における近似解探索部の動作について示すフローチャートである。
【図１１】本発明の実施例４における基本的構成を表すブロック図である。
【図１２】本発明の実施例４における基本的動作を表すフローチャートである。
【図１３】特許文献１に記載の技術について説明するための図である。
【符号の説明】
【００２７】
１００  タスク配置自動最適化システム
１１０  探索部
１１１  分枝部
１１２  限定部
１１２−１  既固定タスク累積応答時間算出指示部
１１２−２  未固定タスク最短応答時間積算部
１１２−３  未固定タスク実行時間合計部
１１２−４  未固定タスク実行時間積算部
１１３  限定抑止部
１２０  累積応答部算出部
１２０−１  応答時間算出部
１２０−２  応答時間累積部
１３０  高評価候補保持部
１４０  近似解探索部
２００  コンピュータ
２１０  プロセッサ
２２０  補助記憶装置
２２１  タスク自動配置最適化プログラム
２２２−１、２２２−２、２２２−３  タスク
２２３  タスク最適配置定義ファイル
２２４  タスクセット定義ファイル
２３０  主記憶装置
３００  スケジューリング可能性判定部
【発明を実施するための形態】
【００２８】
次に、具体的な実施形態を用いて本発明を実施するためのタスク配置最適化システムの構成及び動作を説明する。
【００２９】
本明細書においては例えばコアが複数存在し、そのそれぞれを識別するためにコア番号など番号付けを行う際は、コア０、コア１、コア２…のように０番から付番するものとする。
［実施形態］
【００３０】
図１は、本発明の実施形態による自動最適化システム１００の全体構成を示すブロック図である。図１において、自動最適化システム１００は、探索部１１０、累積応答時間算出部１２０、及び高評価候補保持部１３０を有する。探索部１１０は、更に分枝部１１１と、限定部１１２を有する。なお、後述するが分枝部１１１は、子問題生成に関する部分である。また、限定部１１２は、不要候補排除に関する部分である。
【００３１】
次に図２を用いて、累積応答時間算出部１２０の詳細について説明する。図２に示すように、累積応答時間算出部１２０はさらに、応答時間算出部１２０−１と、応答時間累積部１２０−２を有する。
【００３２】
なお、上述した自動最適化システム１００は、プロセッサ等のハードウェア資源がプログラム（ソフトウェア）を読み込むことにより実現される。
【００３３】
すなわち、ソフトウェアがコンピュータに組み込まれることにより、ソフトウェアとハードウェア資源とが協働した具体的部分によって、使用目的に応じた情報の演算または加工を実現することにより、使用目的に応じた特有の情報処理装置（機械）またはその動作方法が構築される。
【００３４】
具体的なデータ処理装置１００の実装例としてコンピュータ２００を図３及び図４に示す。
【００３５】
図３を参照するとコンピュータ２００は、プロセッサ２１０、補助記憶装置２２０及び主記憶装置２３０を有している。
【００３６】
プロセッサ２１０は演算処理装置である。また、補助記憶装置２２０は、ＨＤＤ（Hard disk drive）やＳＳＤ（solid state drive）に代表される記憶装置であり、各種のデータや、プログラムが格納される。図３においては、タスク自動配置最適化プログラム２２１、タスク（タスク２２２−１、タスク２２２−２及びタスク２２２−３を図示する。）及びタスク最適配置定義ファイル２２３を図示する。また、主記憶装置２３０はＲＡＭ（Random Access Memory）に代表される記憶装置であり、プロセッサ２１０が演算処理を行うにあたり利用される記憶部である。
【００３７】
プロセッサ２１０によって補助記憶装置２２０から読み出されて実行されるタスク自動配置最適化プログラム２２１は、補助記憶装置２２０から最適化対象のタスク２２２−１、タスク２２２−２及びタスク２２２−３の情報を読み出し、記憶装置２３０を利用しながらタスク配置の最適化を行う。最適化を行った結果得られたタスク最適配置は、補助記憶装置２２０上にタスク最適配置定義ファイル２２３として出力される。
【００３８】
次に、図４を参照すると補助記憶装置２２０は、タスク２２２−１、タスク２２２−２及びタスク２２２−３に代わりタスクセット定義ファイル２２４を有している。
【００３９】
そして、プロセッサ２１０によって補助記憶装置２２０から読み出されて実行されるタスク自動配置最適化プログラム２２１は、補助記憶装置２２０から最適化対象の複数のタスクに関する情報が定義されたタスクセット定義ファイル２２４を読み出し、記憶装置２３０を利用しながらタスク配置の最適化を行う。最適化を行った結果得られたタスク最適配置は、補助記憶装置２２０上にタスク最適配置定義ファイル２２３として出力される。
次に、図１及び図２を参照して説明した各部の機能について具体的に説明する。
【００４０】
探索部１１０は、複数あるタスクのコア配置を探索し、タスク配置候補を生成する。探索には、子問題を生成する分枝と、不要な候補を排除する限定操作からなる分枝限定法を用いる。
【００４１】
累積応答時間算出部１２０は、タスク配置候補を入力とし、コア配置決定対象の複数のタスク各々の応答時間を計算し、その累積値をタスク配置の良さを表す指標である評価関数値として算出し、出力する。
【００４２】
高評価候補保持部１３０は、タスク配置候補のうち評価関数値が良好であった候補を保持する。
次に探索部１１０内の分枝部１１１及び限定部１１２について説明する。
【００４３】
分枝部１１１は、図５に示すように、優先度が高いタスクからコアに固定して子問題（図５中では丸で表す）を生成する（図５の上から下に向かう）ことで、探索するタスク配置候補を網羅的に生成する。このとき、子問題の生成が繰り返されて全てのタスクの配置が終了したものがタスク配置候補（図５の最下段）となる。なお、説明の便宜上図５は２コアのシステムを想定した記載となっている。しかし、タスク配置候補を網羅的に生成する本手法は、その対象が２コアに限定されるものではなく、３コア以上の任意のコア数のシステムにおいても同様に拡張が可能である。
【００４４】
限定部１１２では、子問題が取り得る評価関数の限界値（それ以上良くならないと断定できる値で、良い配置が小さい値で表わされる評価関数を用いた場合は下界値、良い配置が大きい値で表わされる評価関数値を用いた場合は上界値となる）を、既にコアに固定したタスクを用いて算出した評価関数値と、既にコア配置を固定したタスクのうち各コアの中で最も優先度が低いタスクの応答時間と、コア配置が未決定なタスクの実行時間のうち少なくともいずれか１つを用いて算出する。
【００４５】
この評価関数値の限界値が、既に見つかっている他のタスク配置候補のスコアより悪い場合には、それ以上その子問題の探索を行っても他のタスク配置候補よりも良いタスク配置候補は得られないため、探索を打ち切る限定処理を行う。限定が行われる場合、それ以上分枝部１１１による子問題の生成が行われなくなる。
【００４６】
次に、図２に示す累積応答時間算出部１２０内の応答時間算出部１２０−１及び応答時間累積部１２０−２について説明する。
【００４７】
応答時間算出部１２０−１は、複数のタスクそれぞれについて、そのタスクの応答時間（タスク起動が指示されてから、そのタスクの実行が終了するまでの時間）を算出する。
【００４８】
応答時間累積部１２０−２は、応答時間算出部１２０−１によって算出された各タスクの応答時間を合計し、累積応答時間を算出する。
【００４９】
次に、図６のフローチャートを用いて、本発明の実施形態における自動最適化システムの動作について説明する。
【００５０】
なお、便宜上ここでは２コアのシステムを想定した動作を記述しているが、本手法は、その適用対象が２コアに限定されるものではなく、３コア以上の任意のコア数のシステムにおいても同様に適用が可能である。
【００５１】
まずステップＳ１１において、探索部１１０は現在扱っている子問題がタスク候補であるか否かを判定する。ここでタスク候補は、全てのタスクが固定された子問題に相当する。タスク候補でない場合（ステップＳ１１においてＮｏ）はステップＳ１２に進む。タスク候補であった場合は（ステップＳ１１においてＹｅｓ）ステップＳ１６に進む。
【００５２】
次にステップＳ１２では、探索部１１０内の限定部１１２が限定式の計算を行い、子問題が取り得る評価関数値の限界値（それ以上良くならないと断定できる値）を算出する。
【００５３】
その後、限定部１１２はステップＳ１３において、評価関数値の限界値と、高評価候補保持部１３０に保持されているタスク配置候補について累積応答時間算出部１２０によって算出される評価関数値とを比較する。比較の結果、評価関数値を更新する可能性がある場合（ステップＳ１３においてＹｅｓ）はステップＳ１４に進む。可能性がない場合（ステップＳ１３においてＮｏ）には限定を行い、それ以上子問題の生成は行わずに処理を終了する。
【００５４】
ステップＳ１３において評価関数値を更新する可能性がある場合（ステップＳ１３においてＹｅｓ）、分枝部１１１はステップＳ１４において、次に固定するタスクのコア配置を０とした子問題を生成する。生成された子問題は、ここで述べている動作と同様に図６のフローチャートに基づいた処理を行う。引き続き分枝部１１１はステップＳ１５において、次に固定するタスクのコア配置を１とした子問題を生成する。生成された子問題は同様に図６のフローチャートに基づいた処理を行う。
【００５５】
一方でステップＳ１１において現在扱っている子問題がタスク候補であった場合（ステップＳ１１においてＹｅｓ）、探索部１１０はステップＳ１６において、累積応答時間生成部１２０にタスク配置候補を渡すことでタスク配置候補の評価関数値の算出を行う。その後探索部１１０はステップＳ１７において、ステップＳ１６で算出した評価関数値と、高評価候補保持部１３０によって保持されているタスク配置候補の評価関数値を比較する。ここで、高評価候補保持部１３０によって保持されているタスク配置候補の評価関数値は毎回計算するのではなく、一度計算したものを保持しておく構成とすることが望ましい。比較した結果、現在のタスク配置候補の評価関数値がより良好な値を示した場合（ステップＳ１７においてＹｅｓ）、探索部１１０はステップＳ１８において、現在のタスク配置候補を高評価候補として高評価候補保持部１３０に登録し、処理を終了する。現在のタスク配置候補の評価関数値が良好でない場合（ステップＳ１７においてＮｏ）には何も行わずに処理を終了する。
次に、本発明の実施形態における効果を説明する。
【００５６】
本発明の実施形態では、累積応答時間算出部１２０によって、タスク配置候補の性能の良好さを表す指標である評価関数値を算出し、この評価関数値を用いて最適化を行うことにより、性能がよいタスク配置を得ることが可能である。このため、スケジューリング可能な複数のタスク配置の中から性能がよい配置を探索可能な自動最適化システムの提供が可能となる。また、累積応答時間算出部１２０によって、コア配置決定対象の複数のタスクの各々の応答時間（タスク起動が指示されてから、そのタスクの実行が終了するまでの時間）の累積値を算出し、コア配置決定対象の複数のタスクの各々の応答時間の累積値を最小化する最適化を行うことにより、各タスクの応答時間が極力短くなるタスク配置を得ることが可能である。このため、リアルタイムシステムにおいてシステムの安定性の観点から重要な指標である、デッドラインからの余裕度を大きくすることが可能となる。更に、タスク配置候補の探索の際に、限定部によって不要なタスク配置候補を探索しないよう限定する。このため、最適化に必要な時間の削減が可能である。
【実施例１】
【００５７】
次に、具体的な実施例を用いて本発明を実施するためのタスク配置最適化システム１００の構成及び動作を説明する。【００５８】
なお、実施例１の基本的構成及びは、図１、図２及び図６に実施形態として示したタスク配置自動化システム１００の構成及び動作と同じであるが、本実施例１では図７を参照して、限定部１１２の具体的な構成例について説明する。また、応答時間算出部１２０−１における算出方法についても説明する。【００５９】
図７を参照すると、限定部１１２は、既固定タスク累積応答時間算出指示部１１２−１と、未固定タスク最短応答時間積算部１１２−２と、未固定タスク実行時間合計部１１２−３を有する。【００６０】
既固定タスク累積応答時間算出指示部１１２−１、未固定タスク最短応答時間積算部１１２−２、未固定タスク実行時間合計部１１２−３は、限定部１１２の機能のうち、評価関数の限界値を求める作用を担当する。なお、評価関数値がより大きいものがより良い配置であるようにする場合と、評価関数値がより小さいものがより良い配置であるようにする場合との２つの場合が考えられるが、以下では、評価関数値がより小さいものがより良い配置である場合を例として説明する。また、以下の説明において、既固定タスクとは、子問題中で既にコア配置を固定されたタスクを指すものとする。未固定タスクとは、まだ子問題中でコア配置を固定されておらず、以後の処理で固定していくタスクを指すものとする。【００６１】
まず、評価関数の限界値の計算においては、既固定タスクによって既に評価関数値が確定している部分（以後、「確定限界値」と呼ぶ）の計算と、未固定タスクが今後タスク配置を固定されることによって増加が見込まれる評価関数値（以後、「増加限界値」と呼ぶ）の計算の大きく２つが存在する。このうち確定限界値の計算を、既固定タスク累積応答時間算出指示部１１２−１が行う。増加限界値の計算は、未固定タスク最短応答時間積算部１１２−２、未固定タスク実行時間合計部１１２−３が行う。【００６２】
既固定タスク累積応答時間算出指示部１１２−１は、累積応答時間算出部１２０に対して既固定タスクのコア配置を渡すことで、累積応答時間を算出する指示を与える。累積応答時間算出部１２０はこの既固定タスクのコア配置を基に累積応答時間を算出し、限定部１１２に渡すことで、確定限界値の計算が行われる。【００６３】
次に、未固定タスク最短応答時間積算部１１２−２は、次のことを利用して増加限界値の計算を行う。【００６４】
まず、既に数段階の子問題生成が行われ、いくつかの既固定タスクが存在する状態を考える。ここで新たに未固定タスクを追加したとき、未固定タスクは既固定タスクより優先度が低い。このことから、未固定タスクの応答時間は、各コア内で最低優先度の既固定タスクの応答時間を、それぞれのコアについて比較して最も短い応答時間（以後、「未固定タスク最短応答時間」と呼ぶ）よりも長くなる。このため、残りのタスクをすべて固定することによって増加する評価関数値は、未固定タスク最短応答時間に残りのタスク数を乗じたものよりも大きい。未固定タスク最短応答時間積算部１１２−２は、未固定タスク最短応答時間に残りのタスク数を乗じたものを増加限界値の一部として算出する。【００６５】
最後に、未固定タスク実行時間合計部１１２−３は、次のことを利用して増加限界値の計算を行う。【００６６】
まず、既に数段階の子問題生成が行われ、いくつかの既固定タスクが存在する状態を考える。ここで新たに未固定タスクを追加したとき、未固定タスクの応答時間は、既固定タスク最短応答時間に加えて、追加したタスクの実行時間が少なくとも加算される。このため、未固定タスク実行時間合計部１１２−３は、未固定タスクの実行時間を全て合計することで、増加限界値の一部を算出する。【００６７】
ここで、未固定タスク最短応答時間積算部１１２−２及び未固定タスク実行時間合計部１１２−３が算出する増加限界値はそれぞれ独立した要素を計算しているため、双方を合計したものを増加限界値として用いることが可能である。【００６８】
次に、応答時間算出部１２０−１における応答時間の算出について説明する。応答時間の算出においては、非特許文献１に記載の最悪応答時間を算出する手法を応用することができる。以下でその手法の概要について述べる。【００６９】
まず、シングルコアにおいて、タスクτｍに対するワークロードである
【数１】
2011102219.tif 000003
は、
【数２】
2011102219.tif 000004
の期間で起動指示が与えられるタスクτｍとそれより優先度が高い全てのタスクによってなされるプロセッサの仕事量の総和を表し、次の式で求められる。【００７０】
【数３】
2011102219.tif 000005
【００７１】
ここで、
【数４】
2011102219.tif 000006
はｘより大きいか等しい最小の整数で、小数点以下を繰り上げたものに相当する。また、ここで、仕事量が１であるとは、時間１においてプロセッサの処理が終了することを表す。このため、貼って【００７２】
【数５】
2011102219.tif 000007
【００７３】
となるｔが存在する、すなわち、時刻ｔまでに蓄積した仕事量が、経過した時間ｔと等しくなる点が存在すれば、そのｔにおいてプロセッサの残り仕事量が０になる。このｔがタスクτｍの最悪応答時間である。この時、ｔが
【数６】
2011102219.tif 000008
（Ｄｍはタスクτｍのデッドライン時刻）の範囲であれば、タスクτｍがデッドライン制約を満たすと判定することができる。
ここで、最悪応答時間の計算は【００７４】
【数７】
2011102219.tif 000009
【００７５】
【数８】
2011102219.tif 000010
の回帰関係を用いて求める。【００７６】
この回帰関係において、
【数９】
2011102219.tif 000011
の範囲において
【数１０】
2011102219.tif 000012
となったときに計算を停止する。【００７７】
一方、
【数１１】
2011102219.tif 000013
の範囲で
【数１２】
2011102219.tif 000014
が成立しない場合はデッドラインミスとなる。【００７８】
マルチコアにおけるタスクτｍの最悪応答時間の計算には、タスクτｍと同じコア上のタスクのみを用いてＷｏｒｋｌｏａｄの式を構築する。【００７９】
最後に応答時間累積部１２０−２は、応答時間算出部１２０−１によって算出された各タスクの応答時間を合計し、累積応答時間を算出する。【００８０】
なお、実施例１の基本的動作は、図６のフローチャートに示した動作と同様であるため説明を省略する。また、本実施例１の構成とすることにより、実施形態の効果として上述した効果と同様の効果を奏することができる。【００８１】
なお、実施例１においては、限定部１１２を構成する要素として既固定タスク累積応答時間算出指示部１１２−１、未固定タスク最短応答時間積算部１１２−２、未固定タスク実行時間合計部１１２−３が含まれるものとした。一方でこれら３つの要素はそれぞれ評価関数の限界値の独立した要素を計算していることから、このうちの一部のみを有する構成とすることもできる。具体的には次のようなバリエーションが考えられる。【００８２】
（１）限定部１１２が既固定タスク累積応答時間算出指示部１１２−１を有する構成【００８３】
（２）限定部１１２が未固定タスク最短応答時間積算部１１２−２を有する構成【００８４】
（３）限定部１１２が未固定タスク実行時間合計部１１２−３を有する構成【００８５】
（４）限定部１１２が既固定タスク累積応答時間算出指示部１１２−１及び未固定タスク最短応答時間積算部１１２−２を有する構成【００８６】
（５）限定部１１２が既固定タスク累積応答時間算出指示部１１２−１及び未固定タスク実行時間合計部１１２−３を有する構成【００８７】
（６）限定部１１２が未固定タスク最短応答時間積算部１１２−２及び実行時間合計部１１２−３を有する構成
【実施例２】
【００８８】
次に、本発明の実施例２におけるタスク配置最適化システム１００の構成及び動作を説明する。【００８９】
実施例２のタスク配置最適化システム１００は、図８に示すように、実施例１のタスク最適化システムの限定部１１２を構成する未固定タスク実行時間合計部１１２−３に代えて、未固定タスク実行時間積算部１１２−４を有する点を除いて実施例１と同一である。【００９０】
次に、未固定タスク実行時間積算部１１２−４の機能について説明する。なお、未固定タスク実行時間積算部１１２−４以外の各部は実施例１と同様の働きをするため、ここでは説明を省略する。また、実施例２の全体的な動作については、未固定タスク実行時間積算部１１２−４による増加限界値の計算以外は実施例１と同様であるため説明を省略する。【００９１】
未固定タスク実行時間積算部１１２−４は、次のことを利用して増加限界値の計算を行う。【００９２】
実施例１の未固定タスク実行時間合計部１１２−３では、未固定タスクの実行時間を全て単純に合計していたが、未固定タスク実行時間積算部１１２−４においては異なる計算手法を用いる。
ここで、シングルコアにおける未固定タスクの応答時間について考える。【００９３】
まず、既に数段階の子問題生成が行われ、いくつかの既固定タスクが存在する状態を考える。ここで新たに１つ未固定タスクＡを追加したとき、未固定タスクＡの応答時間は、既固定タスク最短応答時間に加えて、未固定タスクＡの実行時間が少なくとも加算される。この状態で更に１つ未固定タスクＢを追加すると、未固定タスクＢの応答時間は、既固定タスク最短応答時間及び未固定タスクＡの実行時間に加えて、未固定タスクＢの実行時間が少なくとも加算される。ここで、評価関数は応答時間の累積であることから、未固定タスクＡ及び未固定タスクＢを追加したときに増加する評価関数値には、未固定タスクＡの実行時間は２回加算されることになる。同様に、追加される未固定タスクの数がｘ個の場合には、未固定タスクＡの実行時間はｘ回、未固定タスクＢの実行時間はｘ−１回加算されることになる。【００９４】
マルチコアの場合は、未固定タスクＡを追加したコアと未固定タスクＢ、及びその他の未固定タスクを追加するコアは必ずしも同一でないことから、ｐ個のコアからなるマルチコアにおいては加算される応答時間の回数が概ね１／ｐとなることに注意が必要である。【００９５】
更に、未固定タスクＡと未固定タスクＢの実行時間が加算される回数は、その後の未固定タスクのコア配置次第では未固定タスクＢが多くなることが十分あり得るため、実行時間が長いタスクを最大回数加算してしまうと誤りが生じる。そのため、未固定タスクの実行時間を短い順にソートし、短いものから多数回加算されるものとして算出することで、増加限界値として問題のない値を算出することができる。【００９６】
この処理は次のように表わされる。まず、未固定タスクの実行時間を昇順にソートする。その後未固定タスク１つごとに、昇順にソートされた未固定タスクの実行時間に、未固定タスク数÷コア数の小数点以下を繰り上げたものを乗じた値を積算し、未固定タスク数を１つ減じる操作を全ての未固定タスクについて繰り返す。【００９７】
つまり、ｎを総タスク数、ｍを既固定タスクの数、ｐをコア数、
【数１３】
2011102219.tif 000015
を、残りタスクの実行時間を短い順にソートしたものとしたとき、計算式【００９８】
【数１４】
2011102219.tif 000016
を用いて増加限界値の一部を算出する。【００９９】
ここで、未固定タスク最短応答時間積算部１１２−２及び未固定タスク実行時間積算部１１２−４が算出する増加限界値はそれぞれ独立した要素を計算しているため、双方を合計したものを増加限界値として用いることが可能である。【０１００】
なお、実施例２においては、限定部１１２を構成する要素として既固定タスク累積応答時間算出指示部１１２−１、未固定タスク最短応答時間積算部１１２−２、未固定タスク実行時間積算部１１２−４を有するものとした。一方でこれら３つの要素はそれぞれ評価関数の限界値の独立した要素を計算していることから、このうちの一部のみを備える構成をとることができる。具体的なバリエーションのうち実施例１で述べていないものとして、以下が考えられる。【０１０１】
（１）限定部１１２が未固定タスク実行時間積算部１１２−４を備える構成【０１０２】
（２）限定部１１２が既固定タスク累積応答時間算出指示部１１２−１及び未固定タスク実行時間積算部１１２−４を備える構成【０１０３】
（３）限定部１１２が未固定タスク最短応答時間積算部１１２−２及び実行時間積算部１１２−４を備える構成
【実施例３】
【０１０４】
次に、本発明の実施例３におけるタスク配置最適化システムの構成及び動作を説明する。【０１０５】
実施例３のタスク配置最適化システム１００は、図９に示すように、実施例１または実施例２のタスク最適化システム１００に加えて、近似解探索部１４０を更に有する点を除いて同一である。【０１０６】
次に、近似解探索部１４０の機能について説明する。なお、近似解探索部１４０以外の各部は実施例１又２と同様の働きをするため、ここでは説明を省略する。なお、近似解探索部１４０を設ける実施例３は、実施例１の限定部１１２と組み合わせてもよいし、実施例２の限定部１１２と組み合わせてもよい。【０１０７】
近似解探索部１４０は、探索部１１０が行う最適化より簡便な手法により、探索部１１０より高速にタスク配置候補を発見し、高評価候補保持部１３０に候補を登録する。簡便な方法には、最適化の一般的な近似解法、例えば山登り法などを用いることができる。この探索は、候補の評価関数値は多少劣っていても問題ないが、速度は探索部１１０に比べて十分高速である必要がある。【０１０８】
次に、図１０のフローチャートを用いて、本発明の実施例３における自動最適化システム１００の動作について説明する。【０１０９】
まずステップＳ２１において、近似解探索部１４０は近似解法によるタスク配置候補作成を行う。その後ステップＳ２２において、近似解探索部１４０は作成した候補を登録する。以後ステップＳ２３において、探索部１１０が最適化を行うが、ここでの動作は実施例１及び実施例２の動作として図６のフローチャートに示した動作と同様であるため説明を省略する。
次に、本発明の実施例３における効果を説明する。【０１１０】
最適化を開始した初期の段階では、通常はまだスコアが低いタスク配置候補しか見つかっていない。このため、子問題が取り得る評価関数値の限界値として計算した値は現在見つかっているタスク配置候補のスコアを容易に上回るため、効果的な限定が行われないことがある。ここで本発明の実施例３では、探索部１１０による最適化前に、高速な近似解法によって比較的良好な解の候補を得て、高評価候補保持部１３０にあらかじめ登録している。このため、探索部１１０による最適化の開始時には、その評価関数値を元に限定を行うことが可能となり、処理の高速化を図ることができる。
【実施例４】
【０１１１】
次に、本発明の実施例４におけるタスク配置最適化システム１００の構成及び動作を説明する。実施例４は、概略、最適化の前半では限定を行わず、後半になってから限定を効かせるようにするという実施例である。【０１１２】
実施例４のタスク配置最適化システム１００は、図１１に示すように、実施例１又は実施例２のタスク最適化システムの探索部１１０内に、限定抑止部１１３をさらに有する点を除いて同一である。なお、図９に示す近似解探索部１４０と限定抑止部１１３を組み合わせた構成とすること、すなわち実施例３と実施例４を組み合わせることも可能である。【０１１３】
次に限定抑止部１１３の働きについて説明する。なお、限定抑止部１１３以外の実施例１又は実施例２と同一の要素については実施例１又は実施例２と同様の働きをするため説明を省略する。【０１１４】
限定抑止部１１３は、既固定タスク数が少ないときに、限定部１１２による限定を行わないよう抑止する。抑止を行う既固定タスク数には、総タスク数から算出する方法（例えば総タスク数の１／２とするなど）、あらかじめ総タスク数ごとに抑止が効果的に働く既固定タスク数を計測した値を記録しておく方法等の任意の方法を利用することができる。【０１１５】
次に、図１２のフローチャートを用いて、実施例４における自動最適化システムの動作について説明する。【０１１６】
なお、便宜上ここでは２コアのシステムを想定した動作を記述しているが、本手法は２コアに限定されるものではなく、３コア以上のシステムにおいても同様に適用が可能である。【０１１７】
まずステップＳ３１において、限定抑止部１１３は既固定タスク数が規定値を超えたか否かを判定する。超えていない場合（ステップＳ３１においてＮｏ）はステップＳ３２に進む。超えている場合は（ステップＳ３１においてＹｅｓ）ステップＳ３４に進む。【０１１８】
既固定タスク数が規定値を超えていない場合、分枝部１１１はステップＳ３２において、次に固定するタスクのコア配置を０とした子問題を生成する。このとき生成された子問題は、ここで述べている動作と同様に図１２のフローチャートに基づいた処理を行い、限定に関する処理は行わない。つまり、子問題の生成のみを行う。引き続き分枝部１１１はステップＳ３３において、次に固定するタスクのコア配置を１とした子問題を生成する。生成された子問題は同様に図１２のフローチャートに基づいた処理を行う。【０１１９】
既固定タスク数が規定値を超えている場合、分枝部１１１はステップＳ３４において、次に固定するタスクのコア配置を０とした子問題を生成する。生成された子問題は、ここで述べている動作とは異なり、実施例１などと同様に図６のフローチャートに基づいた処理を行う。つまり、この段階から限定部１１２による限定処理が開始される。引き続き分枝部１１１はステップＳ３５において、次に固定するタスクのコア配置を１とした子問題を生成する。生成された子問題は同様に図６のフローチャートに基づいた処理を行う。
次に、本発明の実施例４における効果を説明する。【０１２０】
既固定タスク数が少ない状態では、その後未固定タスクが追加されることによる評価関数値の変動幅が大きい。このため、限定を行うために計算する、子問題が取り得る評価関数値の限界値として悲観的な値しか算出されない。そのため、限定による子問題の減少による高速化よりも限界値の計算を行うことによるオーバヘッドのほうが大きいことがある。そこで本発明の実施例４では、既固定タスク数が少ない子問題では限定処理を行わず、限界値を計算しないよう構成されている。これにより、限定効果が得られない既固定タスク数が少ない子問題での限界値計算オーバヘッドを無くすことが可能となり、最適化処理の高速化が可能となる。
以上説明した本発明の実施形態が奏する効果をまとめると、以下のようになる。【０１２１】
第１の効果は、スケジューリング可能な複数のタスク配置の中から性能がよい配置を探索可能なことである。【０１２２】
その理由は、累積応答時間算出部によって、タスク配置候補の性能の良好さを表す指標である評価関数値を算出し、この評価関数値を用いて最適化を行うことにより、性能がよいタスク配置が得られるからである。【０１２３】
第２の効果は、リアルタイムシステムにおいてシステムの安定性の観点から重要な指標である、デッドラインからの余裕度を大きくすることが可能なことである。【０１２４】
その理由は、累積応答時間算出部によって、コア配置決定対象の複数のタスクの各々の応答時間（タスク起動が指示されてから、そのタスクの実行が終了するまでの時間）の累積値を算出し、コア配置決定対象の複数のタスクの各々の応答時間の累積値を最小化する最適化を行うことにより、各タスクの応答時間が極力短くなるタスク配置が得られるからである。【０１２５】
第３の効果は、最適化に必要な時間を削減可能なことである。
その第１の理由は、タスク配置候補の探索の際に、限定部によって不要なタスク配置候補を探索しないよう限定するからである。【０１２６】
その第２の理由は、最適化前に、高速な近似解法によって比較的良好な解の候補を得て登録しておき、最適化の開始時には、その評価関数値を元に限定を行うからである。【０１２７】
また、その第３の理由は、既固定タスク数が少ない子問題では限定処理を行わず、限界値を計算しないよう構成されていることから、限定効果が得られない既固定タスク数が少ない子問題での限界値計算オーバヘッドを無くすからである。【０１２８】
なお、本発明の実施形態であるタスク配置最適化システムは、ハードウェアにより実現することもできるが、コンピュータをそのタスク配置最適化システムとして機能させるためのプログラムをコンピュータがコンピュータ読み取り可能な記録媒体から読み込んで実行することによっても実現することができる。【０１２９】
また、本発明の実施形態によるタスク配置最適化方法は、ハードウェアにより実現することもできるが、コンピュータにその方法を実行させるためのプログラムをコンピュータがコンピュータ読み取り可能な記録媒体から読み込んで実行することによっても実現することができる。【０１３０】
また、上述した実施形態は、本発明の好適な実施形態ではあるが、上記実施形態のみに本発明の範囲を限定するものではなく、本発明の要旨を逸脱しない範囲において種々の変更を施した形態での実施が可能である。【０１３１】
本願は、日本の特願２０１０−０３４７３６（２０１０年２月１９日に出願）に基づいたものであり、又、特願２０１０−０３４７３６に基づくパリ条約の優先権を主張するものである。特願２０１０−０３４７３６の開示内容は、特願２０１０−０３４７３６を参照することにより本明細書に援用される。  本発明の代表的な実施の形態が詳細に述べられたが、様々な変更(changes)、置き換え(substitutions)及び選択(alternatives)が請求項で定義された発明の精神と範囲から逸脱することなくなされることが理解されるべきである。また、仮にクレームが出願手続きにおいて補正されたとしても、クレームされた発明の均等の範囲は維持されるものと発明者は意図する。【０１３２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。【０１３３】
（付記１）  複数のコアを有するマルチコア向けのタスク配置最適化システムにおいて、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、
前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、
を備えることを特徴とするタスク配置最適化システム。【０１３４】
（付記２）  付記１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、既にコアに配置したタスクを用いて算出した前記評価関数値を用いて前記限界値を算出する既固定タスク累積応答時間算出指示部を有することを特徴とするタスク配置最適化システム。【０１３５】
（付記３）  付記１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
各コア内で最低優先度の既にコアに配置したタスクである既固定タスクの応答時間をそれぞれのコアについて比較して、当該比較の結果最も短い応答時間に残りのタスク数を乗じることで限界値を算出する未固定タスク最短応答時間積算部を有することを特徴とするタスク配置最適化システム。【０１３６】
（付記４）  付記１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を全て合計することで限界値を算出する未固定タスク実行時間合計部を有することを特徴とするタスク配置最適化システム。【０１３７】
（付記５）  付記１に記載のタスク配置最適化システムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を昇順にソートし、未固定タスク１つ毎に、昇順にソートされた未固定タスクの実行時間に、未固定タスク数÷コア数の小数点以下を繰り上げたものを乗じた値を積算し、未固定タスク数を１つ減じる操作を全ての未固定タスクについて繰り返すことで限界値を算出する未固定タスク実行時間積算部を有することを特徴とするタスク配置最適化システム。【０１３８】
（付記６）  前記探索部は、既に配置を固定したタスクの数が規定値より少ない場合には、前記限定部による限定を行わないよう抑止する限定抑止部を更に備えることを特徴とする付記２乃至５の何れかに記載のタスク配置最適化システム。【０１３９】
（付記７）  予め近似解探索を行うことにより、前記探索部より高速にタスク配置候補を発見しておき、発見したタスク配置候補を前記高評価候補保持部に登録する近似解探索部を更に備えることを特徴とする付記１乃至６の何れかに記載のタスク配置最適化システム。【０１４０】
（付記８）  複数のコアを有するマルチコア向けのタスク配置最適化方法において、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出ステップと、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索ステップと、
前記探索ステップにより探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持ステップと、
を備えることを特徴とするタスク配置最適化方法。【０１４１】
（付記９）  付記８に記載のタスク配置最適化方法において、
前記探索ステップは、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝ステップと、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定ステップと、を含み、
前記限定ステップは、既にコアに配置したタスクを用いて算出した前記評価関数値を用いて前記限界値を算出する既固定タスク累積応答時間算出指示ステップを含むことを特徴とするタスク配置最適化方法。【０１４２】
（付記１０）  付記８に記載のタスク配置最適化方法において、
前記探索ステップは、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝ステップと、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定ステップと、を含み、
前記限定ステップは、
各コア内で最低優先度の既にコアに配置したタスクである既固定タスクの応答時間をそれぞれのコアについて比較して、当該比較の結果最も短い応答時間に残りのタスク数を乗じることで限界値を算出する未固定タスク最短応答時間積算ステップを含むことを特徴とするタスク配置最適化方法。【０１４３】
（付記１１）  付記８に記載のタスク配置最適化方法において、
前記探索ステップは、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝ステップと、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定ステップと、を含み、
前記限定ステップは、
まだ配置を固定されていないタスクである未固定タスクの実行時間を全て合計することで限界値を算出する未固定タスク実行時間合計ステップを含むことを特徴とするタスク配置最適化方法。【０１４４】
（付記１２）  付記８に記載のタスク配置最適化方法において、
前記探索ステップは、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝ステップと、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定ステップと、を含み、
前記限定ステップは、
まだ配置を固定されていないタスクである未固定タスクの実行時間を昇順にソートし、未固定タスク１つ毎に、昇順にソートされた未固定タスクの実行時間に、未固定タスク数÷コア数の小数点以下を繰り上げたものを乗じた値を積算し、未固定タスク数を１つ減じる操作を全ての未固定タスクについて繰り返すことで限界値を算出する未固定タスク実行時間積算ステップを含むことを特徴とするタスク配置最適化方法。【０１４５】
（付記１３）  前記探索ステップは、既に配置を固定したタスクの数が規定値より少ない場合には、前記限定ステップによる限定を行わないよう抑止する限定抑止ステップを更に含むことを特徴とする付記９乃至１２の何れかに記載のタスク配置最適化方法。【０１４６】
（付記１４）  予め近似解探索を行うことにより、前記探索ステップより高速にタスク配置候補を発見しておき、発見したタスク配置候補を前記高評価候補保持ステップに登録する近似解探索ステップを更に含むことを特徴とする付記８乃至１３の何れかに記載のタスク配置最適化方法。【０１４７】
（付記１５）  複数のコアを有するマルチコア向けのタスク配置最適化システムに組み込まれるタスク配置最適化プログラムにおいて、
コア配置決定対象である複数のタスク各々の応答時間を算出し、算出した当該応答時間の累積値を、タスク配置の良好さを表す指標である評価関数値として出力する累積応答時間算出部と、
前記評価関数値に基づいて、良好な評価関数値が算出されるタスク配置を探索する探索部と、
前記探索部により探索された、複数のタスク配置候補のうち評価関数値が良好であった候補を保持する高評価候補保持部と、
を備えるシステムとしてコンピュータを機能させることを特徴とするタスク配置最適化プログラム。【０１４８】
（付記１６）  付記１５に記載のタスク配置最適化プログラムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、既にコアに配置したタスクを用いて算出した前記評価関数値を用いて前記限界値を算出する既固定タスク累積応答時間算出指示部を有するタスク配置最適化システムとしてコンピュータを機能させることを特徴とするタスク配置最適化プログラム。【０１４９】
（付記１７）  付記１５に記載のタスク配置最適化プログラムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
各コア内で最低優先度の既にコアに配置したタスクである既固定タスクの応答時間をそれぞれのコアについて比較して、当該比較の結果最も短い応答時間に残りのタスク数を乗じることで限界値を算出する未固定タスク最短応答時間積算部を有することを特徴とするタスク配置最適化プログラム。【０１５０】
（付記１８）  付記１５に記載のタスク配置最適化プログラムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を全て合計することで限界値を算出する未固定タスク実行時間合計部を有することを特徴とするタスク配置最適化プログラム。【０１５１】
（付記１９）  付記１５に記載のタスク配置最適化プログラムにおいて、
前記探索部は、
優先度が高いタスクから低いタスクへと順にタスクをコアに配置することにより子問題を生成する分枝部と、
前記子問題が取り得る前記評価関数値の限界値を算出し、算出した当該評価関数値の限界値を用いて不要なコア配置候補探索をしないよう限定する限定部と、を有し、
前記限定部は、
まだ配置を固定されていないタスクである未固定タスクの実行時間を昇順にソートし、未固定タスク１つ毎に、昇順にソートされた未固定タスクの実行時間に、未固定タスク数÷コア数の小数点以下を繰り上げたものを乗じた値を積算し、未固定タスク数を１つ減じる操作を全ての未固定タスクについて繰り返すことで限界値を算出する未固定タスク実行時間積算部を有することを特徴とするタスク配置最適化プログラム。【０１５２】
（付記２０）  前記探索部は、既に配置を固定したタスクの数が規定値より少ない場合には、前記限定部による限定を行わないよう抑止する限定抑止部を更に備えることを特徴とする付記１６乃至１９の何れかに記載のタスク配置最適化プログラム。【０１５３】
（付記２１）  予め近似解探索を行うことにより、前記探索部より高速にタスク配置候補を発見しておき、発見したタスク配置候補を前記高評価候補保持部に登録する近似解探索部を前記タスク配置最適化システムが更に備えることを特徴とする付記１５乃至２０の何れかに記載のタスク配置最適化プログラム。
【産業上の利用可能性】
【０１５４】
本発明は、マルチコア構成をとるハードウェアを用いた機器に向けた開発ツール等に好適である。
【図１】
2011102219.tif 000017
【図２】
2011102219.tif 000018
【図３】
2011102219.tif 000019
【図４】
2011102219.tif 000020
【図５】
2011102219.tif 000021
【図６】
2011102219.tif 000022
【図７】
2011102219.tif 000023
【図８】
2011102219.tif 000024
【図９】
2011102219.tif 000025
【図１０】
2011102219.tif 000026
【図１１】
2011102219.tif 000027
【図１２】
2011102219.tif 000028
【図１３】
2011102219.tif 000029
【国際調査報告】
2011102219.tif 000030
2011102219.tif 000031