(57)【要約】  マルチプロセッサに、性能がばらついているコア、動作しないコア、設計通りの性能を満たさないコアが存在しても、タスクの割り当てを工夫することで、実行するアプリケーションの要求を満たすことができるものは出荷する。  複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当方法において、演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成し、前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てる。
2008108133.tif 000002
【特許請求の範囲】
【請求項１】
複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当方法において、
演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成し、
前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てることを特徴とするタスク群割当方法。
【請求項２】
請求項１に記載のタスク群割当方法において、
演算部が、プロセッサ上のコアが設計上の速度で動作するという条件の下で所定のコアに割り当てられた各タスク群を、前記プロセッサ上のコアの実際の速度の下において、各タスク群の開始時刻を変えなくても、タスク間通信が行えるように、コアに再割当てすることを特徴とするタスク群割当方法。
【請求項３】
請求項１又は２に記載のタスク群割当方法において、
演算部が、１つのタスク群は、１つのみのコアに割り当てられるという条件を記述した式を作成するステップと、
演算部が、１つのコアに割り当てられるタスク群の数は、０又は１であるという条件を記述した式を作成するステップと、
演算部が、各コアの座標を表す式を作成するステップと、
演算部が、コア−コア間の距離を表す式を作成するステップと、
演算部が、タスク群−タスク群間の各通信につき、タスクをどのコアに割り当てるかを示す変数に所定の乗数を乗じて得た項の和が、最大許容終了時間以下であることを記述した式を作成するステップと、
演算部が、上記の式を連立させて解くことにより、各タスク群の割当先のコアを決定するステップと、
を備えることを特徴とするタスク群割当方法。
【請求項４】
請求項３に記載のタスク群割当方法において、
前記所定の乗数とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクが割り当てられたとされたコアの実測された最大動作周波数で除することにより得られた実測実行所要時間に、コア間通信の遅延時間を加算して得た数であることを特徴とするタスク群割当方法。
【請求項５】
請求項３に記載のタスク群割当方法において、
前記最大許容終了時刻とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクを初期に割り当てられたコアの設計上の最大動作周波数で除することにより得られた設計実行所要時間に、コア間通信の遅延時間及び余裕時間を加算して得た時刻であることを特徴とするタスク群割当方法。
【請求項６】
複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当装置において、
演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成する手段と、
前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てる手段を有することを特徴とするタスク群割当装置。
【請求項７】
請求項６に記載のタスク群割当装置において、
演算部が、プロセッサ上のコアが設計上の速度で動作するという条件の下で所定のコアに割り当てられた各タスク群を、前記プロセッサ上のコアの実際の速度の下において、各タスク群の開始時刻を変えなくても、タスク間通信が行えるように、コアに再割当てすることを特徴とするタスク群割当装置。
【請求項８】
請求項６又は７に記載のタスク群割当装置において、
演算部が、１つのタスク群は、１つのみのコアに割り当てられるという条件を記述した式を作成する手段と、
演算部が、１つのコアに割り当てられるタスク群の数は、０又は１であるという条件を記述した式を作成する手段と、
演算部が、各コアの座標を表す式を作成する手段と、
演算部が、コア−コア間の距離を表す式を作成する手段と、
演算部が、タスク群−タスク群間の各通信につき、タスクをどのコアに割り当てるかを示す変数に所定の乗数を乗じて得た項の和が、最大許容終了時間以下であることを記述した式を作成する手段と、
演算部が、上記の式を連立させて解くことにより、各タスク群の割当先のコアを決定する手段と、
を備えることを特徴とするタスク群割当装置。
【請求項９】
請求項８に記載のタスク群割当装置において、
前記所定の乗数とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクが割り当てられたとされたコアの実測された最大動作周波数で除することにより得られた実測実行所要時間に、コア間通信の遅延時間を加算して得た数であることを特徴とするタスク群割当装置。
【請求項１０】
請求項８に記載のタスク群割当装置において、
前記最大許容終了時刻とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクを初期に割り当てられたコアの設計上の最大動作周波数で除することにより得られた設計実行所要時間に、コア間通信の遅延時間及び余裕時間を加算して得た時刻であることを特徴とするタスク群割当装置。
【請求項１１】
複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当装置としてコンピュータを機能させるためのタスク群割当プログラムにおいて、
演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成する手段と、
前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てる手段を有することを特徴とするタスク群割当装置としてコンピュータを機能させるためのタスク群割当プログラム。
【請求項１２】
請求項１１に記載のタスク群割当プログラムにおいて、
演算部が、プロセッサ上のコアが設計上の速度で動作するという条件の下で所定のコアに割り当てられた各タスク群を、前記プロセッサ上のコアの実際の速度の下において、各タスク群の開始時刻を変えなくても、タスク間通信が行えるように、コアに再割当てすることを特徴とするタスク群割当プログラム。
【請求項１３】
請求項１１又は１２に記載のタスク群割当プログラムにおいて、
演算部が、１つのタスク群は、１つのみのコアに割り当てられるという条件を記述した式を作成する手段と、
演算部が、１つのコアに割り当てられるタスク群の数は、０又は１であるという条件を記述した式を作成する手段と、
演算部が、各コアの座標を表す式を作成する手段と、
演算部が、コア−コア間の距離を表す式を作成する手段と、
演算部が、タスク群−タスク群間の各通信につき、タスクをどのコアに割り当てるかを示す変数に所定の乗数を乗じて得た項の和が、最大許容終了時間以下であることを記述した式を作成する手段と、
演算部が、上記の式を連立させて解くことにより、各タスク群の割当先のコアを決定する手段と、
を備えることを特徴とするタスク群割当プログラム。
【請求項１４】
請求項１３に記載のタスク群割当プログラムにおいて、
前記所定の乗数とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクが割り当てられたとされたコアの実測された最大動作周波数で除することにより得られた実測実行所要時間に、コア間通信の遅延時間を加算して得た数であることを特徴とするタスク群割当プログラム。
【請求項１５】
請求項１３に記載のタスク群割当プログラムにおいて、
前記最大許容終了時刻とは、タスク群に含まれる所定番目のタスクが終了するまでのサイクル数を、タスクを初期に割り当てられたコアの設計上の最大動作周波数で除することにより得られた設計実行所要時間に、コア間通信の遅延時間及び余裕時間を加算して得た時刻であることを特徴とするタスク群割当プログラム。
【請求項１６】
請求項１乃至５の何れか１項に記載のタスク群割当方法によりタスク群が割り当てられたプロセッサ。
【請求項１７】
請求項１乃至５の何れか１項に記載のタスク群割当方法を用いて、複数のコアを備えた半導体装置の出荷の可否を判定することを特徴とする半導体装置の選別方法。
【請求項１８】
請求項６乃至１０の何れか１項に記載のタスク群割当装置を備えることを特徴とするプロセッサ。
【請求項１９】
請求項６乃至１０の何れか１項に記載のタスク群割当装置を備えることを特徴とするコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のコアを備えるプロセッサにタスク群を割り当てるためのタスク群割当方法、タスク群割当装置及びタスク群割当プログラム並びにタスク群割当方法によりタスク群が割り当てられたプロセッサ、タスク群割当装置を備えるプロセッサ及びタスク群割当装置を備えるコンピュータに関する。
【背景技術】
【０００２】
プロセッサコアは、さまざまなアプリケーションを対象とできる汎用性を持っている。プロセッサコアを１チップに複数搭載した、マルチコアプロセッサは、汎用性を提供し、高性能かつ低消費電力を達成する。また、半導体の微細化の進展により、マルチコアプロセッサの製造が可能となった。【０００３】
しかし、半導体の微細化の進展に伴って、チップ上の素子のばらつきが相対的に大きくなってきた。また、素子の故障が増加している。【０００４】
そのため、プロセッサコア単位での、動作周波数、消費電力といったパラメータのばらつきも大きくなってきた。また、プロセッサコア単位での故障が増加している。
【特許文献１】特開２００６−１３３９９５号公報
【特許文献２】特開２００１−２０２３９７号公報
【非特許文献１】Thomas L. Adam, K. M. Chandy, J. R. Dickson, "A comparison of list schedules for parallel processing systems", Communications of the ACM, Volume 17, Issue 12, pp.685-690, December 1974.
【非特許文献２】H. Kasahara, S. Narita, "Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing", IEEE Trans. on Computers, Vol. C-33, No. 11, pp.1023-1029, Nov. 1984.
【非特許文献３】Yu-Kwong Kwok and Ishfaq Ahmad, Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors, ACM Computing Surveys, Vol. 31, No. 4, December 1999.
【非特許文献４】「数理計画法―最適化の手法―」、一森哲男著、共立出版株式会社、１９９４の第１項〜第４７項
【発明の開示】
【発明が解決しようとする課題】
【０００５】
関連技術の一例では、出荷前テストの際に、全チップ全コアで一律の基準を用いる。例えば、全チップ全コアに５００ＭＨｚ動作を要求する。一律基準を満たさない、あるいは故障しているコアが存在したらチップを破棄する。この基準では、チップ良品率は、「１コアの良品率」の「コア数」をべき数とする累乗となるため、コア間バラつきが増大すると、出荷チップ数が急速に減少する。【０００６】
また、関連技術の他の一例では、冗長コアを設け、故障していなくて、かつ、一律基準を満たすコアが一定数以上のものを出荷する。例えば、８コア用意して、７コア動作するものを出荷する。この一例では、コアは通信を行い、かつタスクには実行時間制限があるので、特定のタスクの割当てについては、冗長コアを用意しても救済できない。つまり、タスクの割当てによってはチップは破棄される。【０００７】
関連技術の更に他の一例では、基準を満たさないコア又は故障しているコアを非動作化しチップ全体を低グレード品として出荷する。例えば、８コア用意して、７コアが動作するチップを、８コアが動作するチップより低価格で販売する。この一例では、低グレード品の量を確保するため、高グレード品の量を多くする必要がある。そのため、この方法は、大ボリュームの市場でのみ適用可能である。また、この方法では、低グレード品の需要がある必要がある。そのため、デスクトップＰＣのＣＰＵ市場のように、多グレードの市場でのみ適用可能である。【０００８】
また、製造後のタスクの割当変更に関する関連技術がある（例えば、特許文献１参照）。これは、実行時の誤動作や故障を回避するために、次に述べるようなことを行うものである。すなわち、実行時に、各コアの動作温度を測定し、優先度の順番に従って、温度の低いプロセッサから順にタスクを割り当てる。割当ての後、動作温度を予測し、予測温度が注意温度を超えるコアがあった場合は、そのコアからタスクを退避し、そのコアを停止する。高優先度のタスクが退避された場合は、高優先度のタスクを、最低温度のコアに、もともとあったタスクを高優先度のタスクに置き換える形で、再割当てする。【０００９】
しかし、この関連技術は、上述のように、１つのタスクに対して優先度順でコアを割り当てていくため、複数のタスクが関係し、それらが実行時間制約を満たすというアプリケーションプログラムの要求を満たすようにタスクの割り当てを行うことができない。従って、チップの選別に用いることはできない。【００１０】
加えて、１タスクずつ割り当てを行うため、再割り当てに時間がかかるという問題がある。また、１タスクずつ退避して割当てを行うならば、実行時間制約によって結ばれている複数タスクを同時に動かすことができない。従って、この方法では、最適なタスク群の割当てが行えない。【００１１】
また、タスク割当に関する他の関連技術がある（例えば、特許文献２参照）。この関連技術では、あらかじめ与えられる仕様から、設計のためにタスクに対してＩＰを割り当てる（ここで、ＩＰとは、再利用可能で売買可能なＬＳＩの設計データのことであるが、ここではそれを拡張してＬＳＩの機能モデル、ハードウェアモデル、ソフトウェアまでも意味する。）。割当ての方法としては、既存の方法を利用する。すなわち次のような割当てを行う。まず、アプリケーション（タスク群）、性能の要件、アーキテクチャのテンプレートを与える。次に、タスクに、ハードウェア又はソフトウェアのＩＰを、与えられたＩＰ群から選んで割り当てる。この割り当てを全てのタスクに対して繰り返す。次に、性能の要件を満たすか否かを判定する。要件を満たさない場合は、要件を満たさないタスクに対し、割り当てるハードウェア又はソフトウェアのＩＰを変更し、性能の要件を満たすか否かの判断に戻る。性能の要件を満たすならば、ＩＰ及びそれに割り当てられたタスクを表す情報を出力する。【００１２】
この関連技術を、製造後のチップの性能に応じたタスクの割り当てとチップの選別に用いるためには、以下のいずれかを行う必要がある。すなわち、一つは、何度もこの方法を適用して、大量の割当てをあらかじめ出しておき、割当てから、アプリケーションを実行可能なコア性能とコア配置を出しておき、製造後に当てはまるコア性能とコア配置を探して、割り当てと選別に用いるということ、もう一つは、製造後にこの方法を適用し、可能な割り当てがあればチップを出荷することである。【００１３】
大量の割当てをあらかじめ出しておくとすると、条件を変えながら、割当てを出力することになる。従って条件が非常に多いので、時間がかかる。例えば、タスク０をＰＥ０に縛り付けてタスク割当を行い、１つのコア性能とコア配置を出力して、これを満たすチップは出荷することにする。次に、タスク０をＰＥ１に縛り付けてタスク割当を行う。そして、これを繰り返す。【００１４】
また、製造後にこの関連技術の手法を適用し、可能な割り当てがあれば、チップを出荷し、なければ、チップを破棄する、という方法には、以下の問題がある。まず、条件を変えながら、割り当てが可能か不可能を試す、ということを繰り返す必要があり、選別に長時間を要するという問題がある。【００１５】
更に、タスクに対してコアを割り当てる方法では、コアの選び方が単純なので、割当てが不可能になる場合が多く、救えるチップ数が減少するという問題がある。ここで、単純であるとは、１つのタスクに注目して、よさそうなコアを近視眼的に選ぶので、間違った選択をしやすいということである。【００１６】
更に、タスクに対してＩＰ（コア）を割り当てるので、タスク群に対してＩＰ（コア）群を割り当てるようなことはなく、割当てのステップで貪欲にコアを割り当ててしまい、コアが足りなくなり、結果として割り当てが不可能になることが多く、救えるチップ数が減少するという問題がある。【００１７】
更に、製造後にはＩＰ（コア）とそのパラメータを自由に選べないということを考慮せず、貪欲にコアを割り当ててしまい、割当て変更ステップにおいて割り当て変更が不可能になることが多く、救えるチップ数が減少するという問題がある。【００１８】
更に、条件（例：タスクを割り当てるコア）を変える際に、割当てが可能になるものに限定する、ということを行えないため、条件を単純に変えてしまい、結果として、割当てが不可能な条件のもとで割当ての試みを続けてしまう場合が多く、可能な割り当てに到達するまでに長時間を要するという問題がある。【００１９】
関連技術をコアの選別に使った場合に次に示す何れかの方法を行わなければならないという課題がある。【００２０】
そのうちの１つの方法は、関連技術のタスク割当の出力した割当てを出荷可否に用いる方法である。この方法では、救えるチップ数が減るという問題がある。この方法は、換言すれば、関連技術の手法で分布（コアの性能とコアの配置）を１つ出して、これを満たすチップだけ出荷するという選別を行うとする方法である。これは、本発明より厳しい制約条件を用いて選別することに対応する。その結果、救えるチップ数が少なくなるという問題が生ずる。【００２１】
他の方法は、何度も関連技術の手法を適用して、大量の分布をあらかじめ出しておく方法である。この方法では、条件を変えながら、割当てを出力する。従って、条件が非常に多いので、時間がかかるという問題がある。例えば、タスク０をＰＥ０に縛り付けてタスク割当を行い、１つの分布を出力して、これを満たすチップは出荷することにする。次に、タスク０をＰＥ１に縛り付けてタスク割当を行い同様なことを行う。【００２２】
更に他の方法は、製造後にタスク割当ての方法を適用する方法である。この方法では、救えるチップ数が減る。また、救えるチップを増やすためには、時間がかかる。すなわち、条件を変えながら、割当てが可能か不可能を試す、ということを繰り返す必要がある。また、割当てが可能になるように、タスクを割り当てるコアといった条件を変えられず、条件を単純に変えてしまい、割当てが不可能な条件のもとで割当ての試みを続けてしまう場合が多い。【００２３】
そこで本発明は、マルチプロセッサに、性能がばらついているコア、動作しないコア、設計通りの性能を満たさないコアが存在しても、タスクの割り当てを工夫することで、実行するアプリケーションの要求を満たすことができるものは出荷すること、またその選別を高速に行うことを目的とする。また、それを実現する、タスク群割当方法、タスク群割当装置、タスク群割当プログラム、プロセッサ及びコンピュータを提供することを目的とする。
【課題を解決するための手段】
【００２４】
本発明によれば、複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当方法において、演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成し、前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てることを特徴とするタスク群割当方法が提供される。【００２５】
また、本発明によれば、複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当装置において、演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成する手段と、前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てる手段を有することを特徴とするタスク群割当装置が提供される。【００２６】
更に、本発明によれば、複数のコアを備えるプロセッサに、前記プロセッサが実行するアプリケーションに含まれるタスク群を割り当てるタスク群割当装置としてコンピュータを機能させるためのタスク群割当プログラムにおいて、演算部が、前記コアの性能と前記コアの配置を抽出し、前記抽出されたコアの性能とコアの配置と、前記アプリケーションが実行可能であるか否かを対応付ける、制約条件を生成する手段と、前記制約条件を参照して、あらかじめ前記複数のコアに割り当てられた前記タスク群を再度前記コアに割当てる手段を有することを特徴とするタスク群割当装置としてコンピュータを機能させるためのタスク群割当プログラムが提供される。【００２７】
更に、本発明によれば、上記のタスク群割当方法によりタスク群が割り当てられたプロセッサが提供される。【００２８】
更に、本発明によれば、上記のタスク群割当方法を用いて、複数のコアを備えた半導体装置の出荷の可否を判定することを特徴とする半導体装置の選別方法が提供される。【００２９】
更に、本発明によれば、上記のタスク群割当装置を備えることを特徴とするプロセッサが提供される。【００３０】
更に、本発明によれば、上記のタスク群割当装置を備えることを特徴とするコンピュータが提供される。
【発明の効果】
【００３１】
本発明の効果は、出荷できるチップを増加させることができることである。【００３２】
なぜなら、全チップ全コア一律の基準では破棄されるチップのうち、一部のチップを、タスクの配置を工夫することにより、アプリケーションの要求を満たして出荷することができるためである。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施形態による割当装置の前半部の構成を示すブロック図である。
【図２】本発明の実施形態による割当装置の後半部の構成を示すブロック図である。
【図３】本発明の実施形態による割当方法の前半部を示すフローチャートである。
【図４】タスク間通信における時間的関係を示す第１の図である。
【図５】タスク間通信における時間的関係を示す第２の図である。
【図６】本発明の実施形態による割当方法の後半部を示すフローチャートである。
【図７】本発明の実施例における諸パラメータ及びタスクのコアへの初期割当を示す図である。
【図８】本発明の実施例における実測された動作速度を示す図である。
【図９】本発明の実施例におけるタスクのコアへの再割当てを行った後の割当てなどを示す図である。
【符号の説明】
【００３４】
１０１  処理装置
１１０  コア性能制約条件、タスク位置制約条件生成部
２０１〜２０５  記憶装置
２１０  アプリケーションタスク群
２２０  コア性能制約条件、タスク位置制約条件
２３０  実測コア性能
２４０  出荷可否
２５０  タスク配置
５０１  処理装置
５１０  出荷可否・タスク配置生成部
【発明を実施するための最良の形態】
【００３５】
以下、図面を参照して本発明を実施するための最良の形態について詳細に説明する。【００３６】
図１、図２は、本発明の実施形態によるタスク割当装置の構成を示すブロック図である。【００３７】
図１を参照すると、記憶装置２０１には、アプリケーションのタスク群２１０が格納される。【００３８】
処理装置１０１には、コア性能制約条件とタスク位置制約条件を生成するためのコア性能制約条件、タスク位置制約条件生成部１１０が配置されている。ここで、処理装置１０１は、コア性能制約条件と、タスク位置制約条件が生成できればよく、コア性能制約条件生成部と、タスク位置制約条件生成部が別々に構成されていても良い。【００３９】
記憶装置２０２には、コア性能制約条件とタスク位置制約条件２２０が格納される。【００４０】
記憶装置２０３には、チップ上の各コアの測定された性能（最高動作周波数）２３０が格納される。【００４１】
処理装置５０１には、出荷可否・タスク配置生成部５１０が配置されている。ここで、処理装置５０１は、出荷可否の結果とタスク配置結果が出力できればよく、出荷可否生成部と、タスク位置生成部が別々に構成されていても良い。【００４２】
記憶装置２０４には、出荷可否の結果２４０が格納される。【００４３】
記憶装置２０５には、出荷が可能であるチップについて、各タスク群のコアへの割当てを示すタスク配置２５０が格納される。記憶装置２０５は、チップに含まれていても良いし、別のチップに含まれていても良い。【００４４】
コア性能制約条件、タスク位置制約条件生成部１１０は、図３を参照して次に説明することを行う。【００４５】
Ｓ１００では、コア群への割当てを製造後に変更する、タスク群の集合Ｓｔａｓｋｓｅｔを決定する。最も厳しい制約条件を決定するタスク群がわかっている際はそのタスク群を用いる。わかっていない場合は、実行されるすべてのタスク群を、その集合とする。【００４６】
Ｓ１０１では、タスク群をコア群に割り当てる。この割当てには関連技術の手法のいかなる手法を用いることができ、例えば、非特許文献１乃至３に記載された割当て方法を用いることができる。【００４７】
タスク群は、同時に実行されるタスクの集合である。なお、本発明では、同一のコアに割り当てられたタスク群をタスク移動の単位とする。【００４８】
Ｓ１０２では、割当ての結果を用いて、コアの性能の制約条件と、タスク群の位置関係の制約条件を線形不等式で表し、その条件を追加する。【００４９】
具体的には、コアの実測性能を表す変数と、タスクの完了時刻（単位はサイクル）を表す定数と、タスク間の距離を表す変数と、データの転送時間を表す定数と、タスク間通信の余裕時間を表す定数と、タスク完了時刻の余裕時間を表す定数と、を含む線形不等式で表す。これについては後述する。ここで、タスク間通信の余裕時間とは、タスクＡがタスクＢにデータを渡す場合、タスクＡの完了時刻に通信時間を足すことにより得られた時刻と、タスクＢの開始時刻との差のことである。【００５０】
Ｓｔａｓｋｓｅｔの全てのタスク群についてＳ１０１〜Ｓ１０２を適用する（Ｓ１０３）。【００５１】
Ｓ１０４では、コアの性能の制約条件と、タスク群の位置関係の制約条件の線形不等式を出力する。【００５２】
次に、Ｓ１０２において、コアの性能の制約条件と、タスク群の位置関係の制約条件を線形不等式で表現する点について図４及び図５を用いて説明する。【００５３】
例えば、図４に示されているように、５つのタスクが３つのコアに割り当てられたとする。タスクＴ０が第１のタスク群を構成し、タスクＴ１とタスクＴ３が第２のタスク群を構成し、タスクＴ２とタスクＴ４が第３のタスク群を構成する。第１のタスク群がコア０に割り当てられ、第２のタスク群がコア１に割り当てられ、第３のタスク群がコア２に割り当てられている。【００５４】
有向辺は依存を表す。例えば、Ｅ１２はタスクＴ１が定義するデータＤ１をタスクＴ２が参照するというデータ依存を表し、Ｅ３４はタスクＴ３が定義するデータＤ２をタスクＴ４が参照するというデータ依存を表す。【００５５】
タスクＴ１の終了時刻にコア１とコア２との間の通信時間を加えることにより得られた時刻から、タスクＴ２の開始時刻までの時間が、タスクＴ１からタスクＴ２へのタスク間通信の余裕時間である。【００５６】
同様に、タスクＴ３の終了時刻にコア１とコア２との間の通信時間を加えることにより得られた時刻から、タスクＴ４の開始時刻までの時間が、タスクＴ３からタスクＴ４へのタスク間通信の余裕時間である。【００５７】
このような条件の下で、実行時間を決定する、実行時刻が最も遅いタスク（図４の例ではタスクＴ４）については、実行時間制限をタスク完了時刻の余裕時間を用いて表現する。すなわち、タスクＴ４の終了時刻が制限時刻を表す定数Ｔｌｉｍｉｔ（図４参照）を超えないようにタスク完了時刻の余裕時間を決定する。【００５８】
連立線形不等式では、下記のことを表現する。【００５９】
コア１について、周波数を落としていくと、Ｄ１の生成が遅くなっていくが、転送時間を加えてもＴ２の開始時刻に間に合うまでは、周波数を落としてもよい。【００６０】
また、コア１について、周波数を落としていくと、Ｄ２の生成が遅くなっていくが、転送時間を加えてもＴ４の開始時刻に間に合うまでは、周波数を落としてもよい。【００６１】
Ｄ１の生成時刻（単位は秒）はＴ１の完了時刻（単位はサイクル）とコアの周波数で表現する。【００６２】
コア２について、周波数を落としていくと、Ｔ４の完了が遅くなっていくが、制限時刻に間に合うまでは、周波数を落としてもよい。【００６３】
Ｔ４の完了時刻（単位は秒）はＴ４の完了時刻（単位はサイクル）とコアの周波数で表現する。【００６４】
上記のことをイメージで示すと次の通りとなる。【００６５】
Ｔ１の箱を下に伸ばしていく。Ｔ１の箱の下端に通信時間を足した時刻がＴ２の箱の上端を超えるまでは周波数を落とせる。また、Ｔ３の箱を下に伸ばしていく。Ｔ３の箱の下端に通信時間を足した時刻がＴ４の箱の上端を超えるまでは周波数を落とせる。【００６６】
ここで、Ｔ１の箱を上下に伸ばしていき、Ｔ０の箱の下端に通信時間を足した時刻がＴ１の箱の上端を超えるまで、またはＴ１の箱の下端に通信時間を足した時刻がＴ２の箱の上端を超えるまでは周波数を落とせる、という表現方法もありうる。しかし、上下に伸ばすと、隣接コアの箱の、伸ばせる範囲に影響を与えるため、同時に複数のコアのタスクを考慮する必要が生じ、式が複雑になる。【００６７】
すなわち、タスクの開始時刻は、不変とし、周波数によって、タスクの終了時刻のみが変化していくようにする。こうすることにより、タスクの終了時刻のみならずタスクの開始時刻も可変とする場合と比べ、問題を簡素に表現することが可能となる。【００６８】
さらに、図５に示すように、３つのコアが横一列に並んでいるマルチコアを想定する。【００６９】
コア間の通信時間は、コア０−コア１間、コア１−コア２間では１ｎｓであり、コア０−コア２間では２ｎｓであるとする。図５の様に２つのタスクが２つのコアに割り当てられたとする。有向辺は依存を表す。例えば、Ｅ１１はタスクＴ１０が定義するデータＤ１０をタスクＴ１１が参照するというデータ依存を表す。タスクＴ１０の終了時刻を２ｎｓとし、タスクＴ１１の開始時刻を４ｎｓとする。チップ製造後、この割当てを変更することを考える。【００７０】
線形不等式で表現したいことは次に示すことである。  通信が間に合う距離にあるコアにタスクを割り当てなければならない。この場合は、タスクＴ１０とタスクＴ１１は、それぞれ、図５のようにコア０とコア１に割り当てられてもよいし、コア０とコア２に割り当てられても良い。しかし、コア０の周波数を落とした場合は、タスクＴ１０とタスクＴ１１は距離の近いコア（例えば、それぞれ、コア０とコア１）に割り当てねばならない場合がある。【００７１】
割当てを変更した後の、コア間の距離はマンハッタン・ディスタンス(Manhattan distance)（ｘ座標の差の絶対値とｙ座標の差の絶対値の和）を用いて表現する。【００７２】
Ｓ１０１で各コアに割り当てられたタスク群を、別コアに割り当てることを考える。線形不等式で、割当変更後に満たすべき条件を表現する。【００７３】
最初の割当てによって、コアｉ（ｉはコアにつけられた名前）に割り当てられたタスク群（例えば、図４、コア１に割り当てられたＴ１とＴ３）の、割当変更後のコアの座標が（ａ，ｂ）である場合に１となる変数をＰｉ，ａ，ｂと表す。コアは横Ｄｘ個、縦Ｄｙ個の２次元のタイル状に配置されているとする。割当変更後のｘ座標は整数で、０からＤｘ−１の範囲にあるとする。ｙ座標についても同様に０からＤｙ−１の範囲にあるとする。【００７４】
以下の式で、一つのタスク群が複数のコアにまたがらず、一つのコアに割り当てられることを表現する。【００７５】
【数１】
2008108133.tif 000003
【００７６】
【数２】
2008108133.tif 000004
【００７７】
以下の式で、一つのコアにタスク群が、「全く割り当てられていないか、１つ割り当てられている」ことを表現する。【００７８】
【数３】
2008108133.tif 000005
【００７９】
コアｉに割り当てられたタスク群の、割当変更後のｘ座標をＶｉ，ｘと表す。以下の式で、Ｐｉ，０，０、Ｐｉ，０，１、…からＶｉ，ｘを作る。【００８０】
【数４】
2008108133.tif 000006
割当変更後のｙ座標をＶｉ，ｙと表す。以下の式で、Ｐｉ，０，０、Ｐｉ，０，１、…からＶｉ，ｙを作る。【００８１】
【数５】
2008108133.tif 000007
次に、コアｍとコアｎのマンハッタン・ディスタンス（ｘ座標の差の絶対値とｙ座標の差の絶対値の和）をＨｍ，ｎと表す。以下の式で、Ｖｍ，ｘ、Ｖｍ，ｙ、Ｖｎ，ｘ、Ｖｎ，ｙからマンハッタン・ディスタンスを生成する。【００８２】
【数６】
2008108133.tif 000008
【００８３】
マンハッタン・ディスタンスの例は次の通りとなる。【００８４】
コアが２次元のタイル状に並んでいて、コア同士がメッシュ状のネットワークを用いて通信する場合は、（ｘ１，ｙ１）に位置するコアと（ｘ２，ｙ２）に位置するコアのマンハッタン・ディスタンスは、【００８５】
【数７】
2008108133.tif 000009
【００８６】
である。【００８７】
次に、最初の割り当てによってコアｉに割り当てられたタスク群の、割当変更後のコアの性能と、割当変更後のタスク間の位置関係を考慮した上で、データの受け渡しが間に合う、という制約を以下の式で表す。（ｘ，ｙ）座標に位置するコアの製造後の性能の実測値を、変数としてＦｆａｂｘ，ｙで表す。【００８８】
Ｔｉ，ｐはコアｉに割り当てられたタスク群のｐ番目のタスクが完了する時刻（単位はサイクル）を表す。Ｔｉ，ｐ／Ｆｆａｂｘ，ｙによって、コアｉに割り当てられたタスク群が（ｘ，ｙ）座標に位置するコアで実行された際の完了時刻（単位は秒）を表現する。Ｌｈｏｐはネットワークの１ホップ（１−ｈｏｐ）の遅延時間である。最初のタスク割当時のコアｉの想定周波数をＦｐｒｅｉで表す。最初のタスク割当時のコアｉに割り当てられたタスク群とコアｊに割り当てられたタスク群のマンハッタン・ディスタンスをＨｐｒｅｉ，ｊで表す。割当変更後の、コアｉに割り当てられたタスク群とコアｊに割り当てられたタスク群のマンハッタン・ディスタンスをＨｉ，ｊで表す。Ｈｉ，ｊ、Ｈｐｒｅｉ，ｊはタスク間通信があるコア間についてのみ式に含める。Ｓｉ，ｐ，ｊ，ｑはコアｉに割り当てられた第ｐ番目のタスクとコアｊに割り当てられた第ｑ番目のタスク間通信の余裕時間（単位は秒）を表す。タスク間通信１個につき１個の式が存在する。【００８９】
【数８】
2008108133.tif 000010
【００９０】
最初の割り当てによってコアｉに割り当てられたタスク群が実行時間要件を満たす、という制約を以下の式で表す。Ｓ’ｉ，ｐはコアｉに割り当てられた第ｐ番目のタスクの、タスク終了時刻の余裕時間（単位は秒）を表す。データの通信により決まる順序において、最も遅いタスク１個につき、１個の式が存在する。図４の例ではＴ２の式とＴ４の式の２つの式が存在する。【００９１】
【数９】
2008108133.tif 000011
【００９２】
次に、出荷可否・タスク配置生成部５１０の動作を図６を参照して説明する。【００９３】
Ｓ５０１では、コアの性能の制約条件と、タスクの位置関係の制約条件とを表した線形不等式に、コアの性能の実測値を代入したものを解く。解く方法としては、シンプレックス法（例えば、非特許文献４）を整数解に応用したものや、分枝限定法を利用することができる。【００９４】
Ｓ５０２では、解が存在するかを判定する。【００９５】
Ｓ５０３では、解が存在するので出荷可と判定し、タスクのコアへの配置を出力する。
配置は解から得られる。【００９６】
Ｓ５０４では、解が存在しないので出荷不可と判定する。【００９７】
次に、図６のＳ５０１の説明をする。【００９８】
各コアの性能（例えば動作周波数）を、チップの製造後に測定する。あるコアが故障していて動作しない場合は性能をゼロとする。この値をＦｆａｂｘ，ｙに代入する。すると、Ｓ１０４で作成した不等式が、連立１次不等式（連立線形不等式）になる。この線形不等式を満たす解があるか否かという問題(feasibility problem)を解く。この問題を解くと、通常、解がない、という答えが得られるか、解が１つ得られる。解は、アプリケーション要件を満たすような、タスク群の、コアへの新たな配置に対応する。【００９９】
この問題は、例えば、最大化（あるいは最小化）する目的の式を無意味なものに設定した（例えば、【０１００】
【数１０】
2008108133.tif 000012
【０１０１】
の）整数計画問題として解くことができる。【０１０２】
解く方法としては、シンプレックス法を整数解に応用したものや分枝限定法を利用することができる。【０１０３】
応用例として、例えば、隣接２×２コアをコアの１つのクラスタとしてまとめて扱って、線形不等式の変数の数を減らし、feasibility problemを解くのにかかる時間を減らすことができる。この場合、コアの代わりに、クラスタを用いて、線形不等式を求める。この場合、コアのクラスタの、製造後に測定した性能は、例えば、コアのクラスタの要素の性能のうち最小のものを用いる。【０１０４】
本実施形態によれば、例えばチップ上にある基準を満たさない少数の低性能コアが存在しても、チップ上に基準を満たす多数の高性能コアが存在していれば、低性能コアに、実行時間制限が緩いタスク群を割り当て、高性能コアに、実行時間制限が厳しいタスク群を割り当てることで、実行するアプリケーションが要件を満たすようにできる。【０１０５】
ここで、実行するアプリケーションとは、タスクの集合からなり、タスクは、データを定義したり参照したりすることで相互に通信を行う。通信はタスク開始時・終了時に起こる。ここで、「タスク」の粒度は限定しない。例えば、タスクの粒度として、プロセス、スレッド、命令列、命令を採用することができる。そして、実行時間制約を取得する。例えば、ある作業（例：音声認識処理）を、ある時間（例：１ｍｓ）で終わらせなければならないという実行時間制約を取得する。【０１０６】
アプリケーションは、例えば、あるチップを使用する機器を製造するセットメーカーが持っている、そのチップ上で動作させるアプリケーションである。セットメーカーの要求は、チップがアプリケーションを、ある要件を満たした上で実行できることである。今までは、余裕をもった判断基準で、チップが出荷できるか否かを判定していた。本発明では、この要求に、より厳密に従った判断基準によって、チップが出荷できるか否かを判定する。すなわち、アプリケーションのタスクのコアへの割当てを工夫することで、要件を満たせるチップを出荷する。これによって、今まで破棄されていたチップを救済することが可能となる。【０１０７】
また、コアの性能・コアの配置と、アプリケーションが要件を満たすことが可能であるか否かを対応付ける制約条件は、例えば、アプリケーションが要件を満たすという条件を表現した線形不等式が考えられる。具体的には、コアの性能とタスク群の位置関係を表現した線形不等式である。ここで、コアの性能とは、コアがあるタスクを実行する上で必要な、それぞれのコアが有する性質であり、例えば、コアの周波数や、コアの消費電力等である。【０１０８】
そして、チップ製造後、チップ上の各コアの性能を測定する。連立線形不等式に、測定された性能を代入し、解を求める。解が得られた場合が出荷できる場合である。出荷できると判断された場合は、連立線形不等式の解が、要件を満たすようなアプリケーションのタスク群の各コアへの配置を示している。この配置をチップに記録してチップを出荷する。【０１０９】
また、使用時に故障を検出してから、配置を変更して故障コアの切り離しをすることも可能である。すなわち、使用時に、故障したチップの動作周波数をゼロにして線形不等式を解くことにより、故障したチップにタスク群を割り当てない配置を求めることもできる。【０１１０】
本実施形態の効果としては次に示すようなものが得られる。【０１１１】
第１の効果は、出荷チップ数を増加させることができることである。その理由は次の通りである。【０１１２】
全チップ全コア一律の基準では破棄されるチップのうち、ある量を、タスクの配置を工夫することでアプリケーションの要求を満たして出荷するからである。【０１１３】
また、冗長コアを用いても救済できないようなタスク割当により破棄されるチップのうち、ある量を、タスクの割り当て自身を工夫することで出荷するからである。【０１１４】
更に、高グレード品の量が少ない、または、低グレード品の需要が存在しない市場においては破棄されるチップのうち、ある量を、タスクの配置を工夫することで出荷するからである。【０１１５】
更に、線形不等式を用いることで、出荷できる割当てを網羅的に探すことができるからである。【０１１６】
第２の効果は、高速に選別を行うことができることである。なぜなら、線形不等式を用いることで、出荷できる割り当てを効率的に探すことができるからである。
【実施例１】
【０１１７】
図７に示すように、９個のコアが縦３行×横３列のタイル状に並んだマルチコアプロセッサを考える。コア間は、メッシュ状のネットワークで通信を行うとする。全コアを１０００ＭＨｚで動作するよう製造する。【０１１８】
ステップＳ１０１において、タスク群をスケジュールする。図７にその結果を示す。２次元空間における位置は、タスク群が割り当てられたコアを示す。例えば、タスクＴ１１は、（０，２）のコアに割り当てられている。【０１１９】
ステップＳ１０２において、タスクの処理量（図７でタスクの右上に示す。単位はサイクル）、タスク間通信（図７でタスクを結ぶ線）におけるマンハッタン・ディスタンス（線の左に示す）、各タスク間の余裕時間（線の右に示す。単位はｎｓ）、最後のタスクの余裕時間（タスクの右下に示す。単位はｎｓ）を求める。【０１２０】
ステップＳ１０３において、すべてのタスク群を割り当てたのでステップＳ１０４に進む。【０１２１】
ステップＳ１０４で、ステップＳ１０２で求められた条件を「かつ」条件で合わせたものを出力する。出力結果である線形不等式は以下の通りとなる。【０１２２】
【数１１】
2008108133.tif 000013
【０１２３】
【数１２】
2008108133.tif 000014
【０１２４】
【数１３】
2008108133.tif 000015
【０１２５】
【数１４】
2008108133.tif 000016
【０１２６】
【数１５】
2008108133.tif 000017
【０１２７】
【数１６】
2008108133.tif 000018
【０１２８】
【数１７】
2008108133.tif 000019
【０１２９】
【数１８】
2008108133.tif 000020
【０１３０】
【数１９】
2008108133.tif 000021
上式において、データ通信の際、１ホップで１０ｎｓかかるとする。また、１０００Ｍｈｚのときは１サイクルは１ｎｓかかる。更に、Ｆｆａｂの単位はＧＨｚである。【０１３１】
全コアが１０００ＭＨｚで動作するようにチップを製造するとする。【０１３２】
ステップＳ５０１で、製造後のチップの各コアの動作周波数の最大値を測定する。図８は動作周波数の最大値を示す。例えば、（０，２）に位置するコアは最大９８０ＭＨｚで動作する。（２，２）に位置するコアは故障していて動作しない。この最大動作周波数を、連立線形不等式のＦｆａｂに代入する。【０１３３】
ステップＳ５０２で、この連立線形不等式の解があるかないかを判定する。例えば、分枝限定法で求めることができる。例えば、連立線形不等式を整数計画問題とみなし、さらに線形計画問題とみなし、線形計画問題の解の近傍の格子点を求め、その格子点が整数計画問題の条件を満たすか判定して、整数計画問題の解とする、という方法で求めることができる。【０１３４】
そして、この場合、解は存在する。【０１３５】
解の一つは、以下のとおり：【０１３６】
【数２０】
2008108133.tif 000022
【０１３７】
図９はこの解に対応するタスク群のコアへの割当てを示す。つまり、図７に示す最初の割当てを変更して、図９に示す割当てにすることで、このチップを出荷することができる。ステップＳ５０３で、このチップを出荷可とし、この配置をチップに記録する。【０１３８】
本発明では、出荷チップ数を増加させることができる。その理由は下記の通りである。【０１３９】
まず、一つのタスクに対して順にコアを割り当てていく関連技術を考える。この関連技術は、１タスクずつ退避して割当てを行うため、実行時間制約によって結ばれている複数タスクを同時に動かすことができず、出荷できるような割り当てを発見できずにチップを破棄する可能性がある。一方で、本発明は、タスクの割当てを変更することによって、チップを出荷することができる。【０１４０】
図７を用いて例を示す。関連技術は、最初の割当てから始めて、Ｔ１６を（０，０）に移動しようと試みる。この場合、Ｔ１６からＴ１７へのデータの通信が間に合わなくなり、実行時間制約を満たせなくなる。このため、関連技術は、Ｔ１６を移動することを断念する。その結果、出荷できるような割り当てを発見できずに、チップを破棄する可能性がある。【０１４１】
全コア全チップ一律基準を、最大動作周波数１０００ＭＨｚとする。一律基準を全チップ全コアに適用する手法では、このチップは破棄される。一方で、本発明では、このチップはタスクの割当てを工夫することで出荷される。【０１４２】
一つのコアを冗長コアとする手法では、この例のタスクの割当てにおいては、このチップは破棄される。なぜなら、タスクＴ１６が動作するコアが故障しているからである。一方、本発明では、タスクの割当てを変更することによって、チップを出荷することができる。【０１４３】
高グレード品の量が少ない、または、低グレード品の需要が存在しない市場においては、低グレード化の手法を用いることができないので、このチップは破棄される。一方で、本発明では、タスクの割当てを工夫することで出荷される。【０１４４】
また、本発明によれば、線形不等式を用いることで、出荷できる割当てを網羅的に探すことができる。【０１４５】
当該割当方法をコンピュータで実行し、これにより決定した割当てをプログラムのスケジューラで利用することができる。ここで、スケジューラは、プロセッサに実装されたものであってもよい。スケジューラは、ソフトウェア、ハードウェア又はこれらの組合せにより実現される。【０１４６】
また、割当方法を行う割当装置をプロセッサに実装し、プログラムを実行する際に、この割当装置が割当方法を行ってもよい。【０１４７】
更に、割当方法を行う割当装置をプロセッサ以外のコンピュータ内のＩＣチップに実装し、プログラムを実行する際に、この割当装置が割当方法を行っても良い。【０１４８】
本願は、日本の特願２００７−０５２８４１（２００７年３月２日に出願）に基づいたものであり、又、特願２００７−０５２８４１に基づくパリ条約の優先権を主張するものである。特願２００７−０５２８４１の開示内容は、特願２００７−０５２８４１を参照することにより本明細書に援用される。【０１４９】
本発明の代表的な実施形態が詳細に述べられたが、様々な変更(changes)、置き換え(substitutions)及び選択(alternatives)が請求項で定義された発明の精神と範囲から逸脱することなくなされることが理解されるべきである。また、仮にクレームが出願手続きにおいて補正されたとしても、クレームされた発明の均等の範囲は維持されるものと発明者は意図する。
【産業上の利用可能性】
【０１５０】
本発明は、複数のコアを備えるプロセッサの歩留まりを上げるために利用することができる。
【図１】
2008108133.tif 000023
【図２】
2008108133.tif 000024
【図３】
2008108133.tif 000025
【図４】
2008108133.tif 000026
【図５】
2008108133.tif 000027
【図６】
2008108133.tif 000028
【図７】
2008108133.tif 000029
【図８】
2008108133.tif 000030
【図９】
2008108133.tif 000031
【国際調査報告】
2008108133.tif 000032
2008108133.tif 000033
2008108133.tif 000034
2008108133.tif 000035