(57)【要約】  本発明の実施形態は、タスク割り当て方法、タスク割り当て装置、およびネットワークオンチップを提供する。本方法は、処理対象タスクに含まれるスレッドの数を明らかにするステップと、マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアに対応するオンチップルータによって形成される連続領域を特定するステップと、前記領域が非矩形の領域である場合に、該領域から拡大される矩形の領域を決定するステップと、非アイドルのプロセッサコアに接続された前記拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが所定のしきい値を超えない場合に、前記処理対象タスクの複数のスレッドを前記領域内のアイドルプロセッサコアに割り当てるステップとを含む。本発明の実施形態においてもたらされるタスク割り当て方法によれば、非矩形の領域が、タスクがすでに割り当てられているエッジルータを使用することによって規則的な矩形の領域に拡大され、タスクの割り当てが、領域の形状の柔軟性との組み合わせにおいて、XY経路指定を使用することによって実行されるため、ハードウェアのオーバヘッドが大きい、ネットワークのスループットが低い、システムの利用率が低い、などの問題が回避される。
2016522488.tif 000002
【特許請求の範囲】
【請求項１】
処理対象タスクに含まれるスレッドの数を明らかにするステップと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定するステップと、
前記ネットワークオンチップにおいて、前記特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップと、
非アイドルのプロセッサコアに接続された前記拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てるステップと
を含むタスク割り当て方法。
【請求項２】
前記非矩形の領域から拡大される矩形の領域は、前記ネットワークオンチップにおいて前記非矩形の領域を含む最小の矩形の領域である請求項1に記載の方法。
【請求項３】
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップの後で、
該特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、矩形の領域である場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てるステップ
をさらに含む請求項1または2に記載の方法。
【請求項４】
前記ネットワークオンチップは、行−列のやり方で配置された複数のプロセッサコアを含み、
したがって、マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップは、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて最初のアイドルプロセッサコアを特定するステップと、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップと
を含む請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って連続する第2のアイドル領域を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む請求項4に記載の方法。
【請求項６】
前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って連続する第4のアイドル領域を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む請求項4に記載の方法。
【請求項７】
非アイドルのプロセッサコアに接続された前記矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクに含まれるスレッドを前記アイドルプロセッサコアにそれぞれ割り当てるステップの前に、
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得るステップ
をさらに含む請求項1から6のいずれか一項に記載の方法。
【請求項８】
処理対象タスクに含まれるスレッドの数を明らかにする第1の決定モジュールと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定する第2の決定モジュールと、
前記第2の決定モジュールによって特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、前記ネットワークオンチップにおいて前記非矩形の領域から拡大される矩形の領域を探索および決定する第3の決定モジュールと、
前記第3の決定モジュールによって決定された矩形の領域内の非アイドルのプロセッサコアに接続された各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てる割り当てモジュールと
を備えるタスク割り当て装置。
【請求項９】
前記第3の決定モジュールは、
前記非矩形の領域から拡大される矩形の領域を、前記ネットワークオンチップにおける前記非矩形の領域を含む最小の矩形の領域であるように決定する
ように特に構成されている請求項8に記載のタスク割り当て装置。
【請求項１０】
前記割り当てモジュールは、
前記第2の決定モジュールによって特定された複数のアイドルプロセッサコアに接続されたオンチップルータが、矩形の領域を形成する場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てる
ようにさらに構成されている請求項8または9に記載のタスク割り当て装置。
【請求項１１】
前記第2の決定モジュールは、
前記マルチコアプロセッサによって形成され、行−列のやり方で配置された複数のプロセッサコアを備えているネットワークオンチップにおいて、最初のアイドルプロセッサコアを特定し、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定する
ように特に構成されている請求項8から10のいずれか一項に記載のタスク割り当て装置。
【請求項１２】
前記第2の決定モジュールは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って連続する第2のアイドル領域を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成されている請求項11に記載のタスク割り当て装置。
【請求項１３】
前記第2の決定モジュールは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って連続する第4のアイドル領域を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成されている請求項11に記載のタスク割り当て装置。
【請求項１４】
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得る予測モジュール
をさらに備える請求項8から13のいずれか一項に記載のタスク割り当て装置。
【請求項１５】
複数のプロセッサコアと、オンチップルータと、配線とを備えており、請求項8から14のいずれか一項に記載のタスク割り当て装置をさらに備えているネットワークオンチップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、2013年5月14日に中国特許庁に出願された「TASK ALLOCATION METHOD, TASK ALLOCATION APPARATUS, AND NETWORK-ON-CHIP」という名称の中国特許出願第201310177172.1号の優先権を主張し、この中国特許出願は、ここでの言及によってその全体が本明細書に援用される。
本発明の実施形態は、マルチコアネットワークオンチップ技術に関し、特にタスク割り当て方法、タスク割り当て装置、およびネットワークオンチップに関する。
【背景技術】
【０００２】
超大規模集積回路（Very Large Scale Integration、略してVLSI）の集積のレベルがより高くなるにつれて、同じチップ上により多数の記憶ユニットおよび信号処理ユニットなどのオンチップ（on-chip）処理ユニットが統合され、各々のオンチップ処理ユニットが、1つのプロセッサコアに相当し、複数のプロセッサコアが、マルチコアプロセッサまたは多コアプロセッサを形成する。ネットワークオンチップ（Network-on-Chip、略してNoC）が、マルチコアプロセッサにおいて異なるプロセッサコア間のデータ伝送を実現するための主たる手段である。プロセッサコアの数が多くなるにつれて、1つのタスクおよび複数のタスクの複数のスレッドが同じプロセッサコアにおいて同時に処理される状況がますます一般的になり、異なるタスクのスレッドが同じプロセッサコアに無作為に割り当てられる場合、NoCにおいて、同じタスクの異なるスレッドを処理しているプロセッサコア間の通信が、他のタスクのデータストリームの影響を被り、その場合、サービス品質（Quality of Service、略してQoS）を保証することができず、システムの性能が低下する。NoCにおいてタスクを無作為に割り当てることによって引き起こされるタスク間のデータストリームの相互の干渉を回避するために、サブネット分割（subnet division）法が通常は使用され、すなわち同じタスクに属するデータストリームが、NoCの特定の領域に制限される。
【０００３】
先行技術においては、NoC内の各々のオンチップルータについて経路指定表（routing table）が設定され、経路指定表が、送信元のオンチップルータから宛て先のオンチップルータまでのパケットの伝送の経路指定機構を決定する。サブネット分割が実行される場合、或るタスクのデータストリームの次のホップ（hop）が到達するオンチップルータが、同じタスクに割り当てられたオンチップルータであるように、内部経路指定アルゴリズムによって保証され、経路指定アルゴリズムは、あらゆる接続形態に適用可能であり、比較的複雑であり、ハードウェアのオーバヘッドが大きく、不規則な形状のサブネットは、トラフィックの輻輳を容易に引き起こす。図1が、先行技術の経路指定アルゴリズムにもとづくタスク割り当て方法の概略図である。図1に示されるように、タスク5内の他のすべてのオンチップルータがDestとの通信を必要とする場合、同じリンクを使用しなければならず、結果としてリンクの輻輳が生じ、ネットワークのスループットに悪影響が及ぶ可能性がある。
【発明の概要】
【０００４】
本発明の実施形態は、経路指定アルゴリズムにもとづくタスク割り当て方法においてハードウェアのオーバヘッドが大きい、ネットワークのスループットが低い、などの先行技術の問題を解決するために使用されるタスク割り当て方法、タスク割り当て装置、およびネットワークオンチップを提供する。
【課題を解決するための手段】
【０００５】
第1の態様によれば、本発明の実施形態は、
処理対象タスクに含まれるスレッドの数を明らかにするステップと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定するステップと、
前記ネットワークオンチップにおいて、前記特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップと、
非アイドルのプロセッサコアに接続された前記拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てるステップと
を含むタスク割り当て方法を提供する。
【０００６】
第1の態様の第1の考えられる実施のやり方においては、前記非矩形の領域から拡大される矩形の領域は、前記ネットワークオンチップにおいて前記非矩形の領域を含む最小の矩形の領域である。
【０００７】
第1の態様または第1の態様の第1の考えられる実施のやり方に関して、第1の態様の第2の考えられる実施のやり方においては、マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップの後で、本方法は、
前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、矩形の領域である場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てるステップ
をさらに含む。
【０００８】
第1の態様、第1の態様の第1の考えられる実施のやり方、および第2の考えられる実施のやり方のうちの任意の1つに関して、第3の考えられる実施のやり方においては、前記ネットワークオンチップが、行−列のやり方で配置された複数のプロセッサコアを含み、
したがって、マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップは、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて最初のアイドルプロセッサコアを特定するステップと、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定するステップと
を含む。
【０００９】
第1の態様の第3の考えられる実施のやり方に関して、第1の態様の第4の考えられる実施のやり方においては、前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップが、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って連続する第2のアイドル領域を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む。
【００１０】
第1の態様の第3の考えられる実施のやり方に関して、第1の態様の第4の考えられる実施のやり方においては、前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップが、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って連続する第4のアイドル領域を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む。
【００１１】
第1の態様および第1の態様の第1〜第5の考えられる実施のやり方のうちの任意の考えられる実施のやり方に関して、第1の態様の第6の考えられる実施のやり方においては、非アイドルのプロセッサコアに接続された前記矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクに含まれるスレッドを前記アイドルプロセッサコアにそれぞれ割り当てるステップの前に、本方法が、
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得るステップ
をさらに含む。
【００１２】
第2の態様によれば、本発明の実施形態は、
処理対象タスクに含まれるスレッドの数を明らかにするように構成された第1の決定モジュールと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定するように構成された第2の決定モジュールと、
前記第2の決定モジュールによって特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、前記ネットワークオンチップにおいて前記非矩形の領域から拡大される矩形の領域を探索および決定するように構成された第3の決定モジュールと、
前記第3の決定モジュールによって決定された矩形の領域内の非アイドルのプロセッサコアに接続された各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てるように構成された割り当てモジュールと
を備えるタスク割り当て装置を提供する。
【００１３】
第2の態様の第1の考えられる実施のやり方ににおては、前記第3の決定モジュールが、
前記非矩形の領域から拡大される矩形の領域を、前記ネットワークオンチップにおける前記非矩形の領域を含む最小の矩形の領域であるように決定する
ように特に構成される。
【００１４】
第2の態様および第2の態様の第1の考えられる実施のやり方に関して、第2の態様の第2の考えられる実施のやり方においては、前記割り当てモジュールが、
前記第2の決定モジュールによって特定された複数のアイドルプロセッサコアに接続されたオンチップルータが、矩形の領域を形成する場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てる
ようにさらに構成される。
【００１５】
第2の態様ならびに第2の態様の第1および第2の考えられる実施のやり方のうちのいずれかの考えられる実施のやり方に関して、第2の態様の第3の考えられる実施のやり方においては、前記第2の決定モジュールが、
前記マルチコアプロセッサによって形成され、行−列のやり方で配置された複数のプロセッサコアを備えているネットワークオンチップにおいて、最初のアイドルプロセッサコアを特定し、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定する
ように特に構成される。
【００１６】
第2の態様の第3の考えられる実施のやり方に関して、第2の態様の第4の考えられる実施のやり方においては、前記第2の決定モジュールが、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って連続する第2のアイドル領域を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成される。
【００１７】
第2の態様の第3の考えられる実施のやり方に関して、第2の態様の第5の考えられる実施のやり方においては、前記第2の決定モジュールが、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に一致しない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って連続する第4のアイドル領域を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成される。
【００１８】
第2の態様および第2の態様の第1〜第5の考えられる実施のやり方のうちの任意の考えられる実施のやり方に関して、第2の態様の第6の考えられる実施のやり方においては、本タスク割り当て装置が、
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得るように構成された予測モジュール
をさらに備える。
【００１９】
第3の態様によれば、本発明の実施形態は、複数のプロセッサコアと、オンチップルータと、配線と、上述の考えられる実施のやり方のいずれか1つにおいて説明されたタスク割り当て装置とを備えるネットワークオンチップをさらに提供する。
【００２０】
本発明の実施形態において提供されるタスク割り当て方法、タスク割り当て装置、およびネットワークオンチップによれば、処理対象タスクに含まれるスレッドの数が明らかにされ、必要とされるスレッドの数に一致する数の複数のアイドルプロセッサコアによって形成される非矩形の領域がネットワークオンチップにおいて特定され、非矩形の領域に隣接するエッジオンチップルータおよびアイドルプロセッサコアに接続された非矩形の領域内のオンチップルータが、規則的な矩形の領域を形成し、次いで非アイドルのプロセッサコアに接続されかつ矩形の領域内に位置するオンチップルータが特定され、すなわちエッジオンチップルータのトラフィックが所定のしきい値を超えるか否かが判断され、エッジオンチップルータのトラフィックが所定のしきい値を超えない場合に、処理対象タスクがアイドル領域内のプロセッサコアに割り当てられる。本発明の実施形態において提供されるタスク割り当て方法によれば、ネットワークオンチップ内のアイドルプロセッサコアリソースの数が、処理対象タスクが必要とするプロセッサコアの数以上であるときに、処理対象タスクが割り当てられる規則的な矩形の領域が存在しない場合に、非矩形の領域が、エッジルータを使用することによって規則的な矩形の領域を形成し、処理対象タスクが割り当てられ、矩形の領域においては、送信元のオンチップルータから宛て先のオンチップルータまでのパケットの経路指定機構を、経路指定表を使用することによって決定する必要がなく、パケットがXY経路指定のやり方で伝送されるため、ネットワークの輻輳が回避され、ネットワークのスループットが改善される。
【００２１】
本発明の実施形態または先行技術における技術的解決策をより分かりやすく説明するために、実施形態または先行技術の説明に必要な添付の図面を、以下で簡単に紹介する。当然ながら、以下の説明において、添付の図面は、本発明のいくつかの実施形態を示し、当業者であれば、創造的な活動を必要とすることなく、これらの添付の図面から他の図面をさらに導き出すことができる。
【図面の簡単な説明】
【００２２】
【図１】先行技術における経路指定サブネットにもとづくタスク割り当て方法の概略図である。
【図２】本発明によるタスク割り当て方法の実施形態1のフロー図である。
【図３】本発明によるタスク割り当て方法の実施形態2におけるネットワークオンチップの概略図である。
【図４Ａ】本発明によるタスク割り当て方法の実施形態3におけるネットワークオンチップの概略図である。
【図４Ｂ】図4Aにおける再度の矩形の領域の探索の概略図である。
【図５Ａ】本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、ユニフォームランダムトラフィックモデルを使用することによる分析の概略図である。
【図５Ｂ】本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、圧縮ビットトラフィックモデルを使用することによる分析の概略図である。
【図５Ｃ】本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、トルネードトラフィックモデルを使用することによる分析の概略図である。
【図６】本発明によるタスク割り当て装置の実施形態1の概略の構造図である。
【図７】本発明によるタスク割り当て装置の実施形態2の概略の構造図である。
【図８】本発明によるタスク割り当て装置の実施形態3の概略の構造図である。
【発明を実施するための形態】
【００２３】
本発明の実施形態の目的、技術的解決策、および利点をさらに明瞭にするために、以下で、本発明の実施形態における技術的解決策を、本発明の実施形態における添付の図面を参照して、明確かつ充分に説明する。当然ながら、説明される実施形態は、本発明の実施形態の一部であり、すべてではない。本発明の実施形態にもとづいて創造的な取り組みを必要とすることなく当業者によって得られるすべての他の実施形態は、本発明の保護の範囲に包含される。
【００２４】
図2は、本発明によるタスク割り当て方法の実施形態1のフロー図である。この実施形態は、複数のコアプロセッサによって形成されるネットワークオンチップに統合されてよいタスク割り当て装置によって実行され、この装置は、例えばネットワークオンチップ内の任意のプロセッサなどであってよい。この実施形態は、ネットワークオンチップ内のアイドルプロセッサコアリソースの数が、処理対象タスクが必要とするプロセッサコアの数以上である状況に適用可能である。具体的には、この実施形態は、以下のステップを含む。
【００２５】
ステップ101：処理対象タスクに含まれるスレッドの数を明らかにする。
【００２６】
タスク割り当て装置は、処理対象タスクに含まれるスレッドの数を明らかにする。一般に、1つのタスクに含まれるスレッドの数は、そのタスクの処理に必要なプロセッサコアの数に1対1に対応している。例えば、1つのタスクが9個のスレッドを含む場合、そのタスクを処理するために9個のプロセッサコアが必要とされる。
【００２７】
ステップ102：マルチコアプロセッサによって形成されるネットワークオンチップにおいて、スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定する。
【００２８】
ネットワークオンチップは、同時のアクセスのサポート、高い信頼性、高い再使用性、などといった特徴を有し、複数のプロセッサコア、オンチップルータ、および配線（チャネル）によって形成される。配線は、オンチップルータとプロセッサコアとの間の内部配線と、オンチップルータ間の外部配線とを含み、各々のプロセッサコアが、1つのオンチップルータに接続され、オンチップルータが、メッシュの接続形態（Mesh Topology、略してメッシュ）を形成するように互いに接続される。このステップにおいて、処理対象タスクに含まれるスレッドの数が明らかにされた後で、タスク割り当て装置は、マルチコアプロセッサによって形成されたネットワークオンチップにおいて、スレッドの数に従って、スレッドの数に等しい数の複数の連続するアイドルプロセッサコアおよび対応するオンチップルータを特定する。
【００２９】
ステップ103：特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合、ネットワークオンチップにおいて、この非矩形の領域から拡大される矩形の領域が探索され、決定される。
【００３０】
タスク割り当て装置が、スレッドの数に等しい数の複数の連続するアイドルプロセッサコアを特定した後で、これらのアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、矩形の領域である場合、タスク割り当て装置は、処理対象タスクに含まれるスレッドをアイドルプロセッサコアに直接的に割り当て、各々のプロセッサコアに1つのスレッドが割り当てられる一方で、アイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合、タスク割り当て装置は、この非矩形の領域から拡大される矩形の領域を探索および決定し、ここでこの領域は、ネットワークオンチップ内で前記非矩形の領域を含む最小の矩形領域である。例えば、1つのNoCが5×5のメッシュ構造であり、処理対象タスクに含まれるスレッドの数が5であり、特定された連続するアイドルプロセッサコアが、同じ行または同じ列内の5つのプロセスコアである場合、処理対象タスクに含まれる5つのスレッドがこれら5つの連続するアイドルプロセッサコアに割り当てられ、各々のプロセッサコアに1つのスレッドが割り当てられる。特定された連続するアイドルプロセッサコアの数が5であるが、これら5つのプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域であり、すなわち形成される領域が不規則な形状の領域である場合、タスク割り当て装置は、この非矩形の領域を含む矩形の領域を決定し、すなわちタスクがすでに割り当てられている非アイドルのプロセッサコアおよび非矩形の領域のアイドルプロセッサコアが、矩形の領域を形成する。具体的には、5つのプロセッサコアが第1の行の最初の3つのプロセッサコアおよび第2の行の最初の2つのプロセッサコアによって形成される例を使用すると、第2の行の3番目のプロセッサコアに接続されたオンチップルータが、エッジオンチップルータとして使用され、タスク割り当て装置は、5つのプロセッサコアに接続されたオンチップルータおよびエッジオンチップルータによって形成される矩形の領域を決定する。
【００３１】
本発明が、以上においては、5つのプロセッサコアが第1の行の最初の3つのプロセッサコアおよび第2の行の最初の2つのプロセッサコアによって形成される例を使用することによって詳しく説明されているが、本発明がこれに限られず、他に考えられる実施のやり方においては、連続するアイドルプロセッサコアが別の組み合わせを有してもよく、プロセッサコアに接続されたオンチップルータによって形成される非矩形の領域も、L字形、E字形、F字形、90度反転のH字形、およびI字形など、多数の様々な形状を有することができ、したがって非矩形の領域を含む矩形の領域も、多数の様々な形状を有することができることに、注意すべきである。
【００３２】
ステップ104：非アイドルのプロセッサコアに接続され、かつ拡大後の矩形の領域に含まれる各々のオンチップルータのトラフィックが、所定のしきい値以下である場合に、処理対象タスクのスレッドをアイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドが割り当てられる。
【００３３】
矩形の領域においては、送信元のオンチップルータから宛て先のオンチップルータまでのパケットの経路指定機構を、経路指定表を使用することによって決定する必要がなく、パケットがXY経路指定のやり方で伝送され、すなわち送信元のオンチップルータおよび宛て先のオンチップルータが決定された後で、送信元のオンチップルータから出発して、パケットが最初に横方向に、宛て先のオンチップルータが位置する列と交わる中間のオンチップルータまで伝送され、次いで宛て先のオンチップルータまで縦方向に伝送され、あるいはパケットが最初に縦方向に、宛て先のオンチップルータが位置する行と交わる中間のオンチップルータまで伝送され、次いで宛て先のオンチップルータまで横方向に伝送される。
【００３４】
非矩形の領域を含む矩形の領域が決定された後で、タスク割り当て装置は、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータの履歴トラフィック情報に従って、予測トラフィックを得るべく予測を行い、予測トラフィックが所定のしきい値を超えるか否かを判断し、予測トラフィックが所定のしきい値を超えない場合に、タスク割り当て装置は、処理対象タスクに含まれるスレッドをそれぞれのアイドルプロセッサコアに割り当てる。
【００３５】
本発明のこの実施形態において提供されるタスク割り当て方法によれば、処理対象タスクに含まれるスレッドの数が明らかにされ、必要とされるスレッドの数に等しい数の複数のアイドルプロセッサコアによって形成される非矩形の領域がネットワークオンチップにおいて特定され、非矩形の領域に隣接する領域に位置するエッジルータおよび非矩形の領域内のオンチップルータが、規則的な矩形の領域を形成し、次いで非アイドルのプロセッサコアに接続されかつ矩形の領域内に位置するオンチップルータが特定され、すなわちエッジオンチップルータのトラフィックが所定のしきい値を超えるか否かが判断され、エッジオンチップルータのトラフィックが所定のしきい値を超えない場合に、処理対象タスクがアイドル領域内のプロセッサコアに割り当てられる。本発明のこの実施形態において提供されるタスク割り当て方法によれば、ネットワークオンチップ内のアイドルプロセッサコアリソースの数が、処理対象タスクが必要とするプロセッサコアの数以上であるときに、処理対象タスクが割り当てられる規則的な矩形の領域が存在しない場合に、非矩形の領域がエッジルータを使用することによって規則的な矩形の領域に拡大されて、処理対象タスクのスレッドが割り当てられ、矩形の領域においては、送信元のオンチップルータから宛て先のオンチップルータまでのパケットの経路指定機構を、経路指定表を使用することによって決定する必要がなく、パケットがXY経路指定のやり方で伝送されるため、他のタスク割り当て方法におけるハードウェアのオーバヘッドが大き、ネットワークのスループットが小さい、およびシステムの利用率が低いという問題が回避される。
【００３６】
以上から知ることができるとおり、NoCは、オンチップルータおよび配線（チャネル）によって形成され、各々のプロセッサコアが1つのオンチップルータに接続され、1つのタスクに含まれるスレッドの数が、そのタスクの処理に必要なプロセッサコアの数に1対1に対応する。したがって、処理対象タスクに含まれるスレッドの数と、処理対象タスクが必要とするプロセッサコアの数と、必要なプロセッサコアに接続されたオンチップルータの数とが等しく、プロセッサコアの状態はオンチップルータの状態に一致し、同時にアイドル状態またはタスクが割り当てられた状態となり、アイドル状態のオンチップルータが探索によって発見されるとき、アイドル状態のプロセッサコアが探索によって発見される。本発明のこの実施形態をさらに分かりやすくするために、以下の図に示されるネットワークオンチップは、オンチップルータだけを示している。
【００３７】
一般に、ネットワークオンチップは、25個のプロセッサコアおよび25個のオンチップルータを5つの行および5つの列にて含んでいる5×5のネットワークオンチップなど、行−列のやり方で配置された複数のプロセッサコアを含む。このやり方で、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが特定されるとき、アイドルプロセッサコアを行によって探索でき、あるいはアイドルプロセッサコアを列によって探索することができる。具体的には、行による探索を例として用いると、複数のコアプロセッサによって形成されるネットワークオンチップにおいて最初のアイドルプロセッサコアを特定でき、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かが、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って順次判断される。第1のアイドル領域に含まれ、同じ行の隣接するオンチップルータに沿って順次判断されて特定された連続するプロセッサコアの数が、スレッドの数に一致しない場合に、連続する第2のアイドル領域が、第1のアイドル領域に含まれるプロセッサコアの数と第2のアイドル領域に含まれるプロセッサコアの数との合計がスレッドの数に一致するように、最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って順次決定される。本発明を、以下で、ネットワークオンチップにおいてタスクを具体的に割り当てるいくつかの実施形態を使用して、詳しく説明する。
【００３８】
図3が、本発明によるタスク割り当て方法の実施形態2におけるネットワークオンチップの概略図である。図3に示されるとおり、この実施形態においては、NoCが5×5のNoCであり、複数のプロセッサコアが行−列のやり方で配置され、タスクの待ち行列に処理対象タスク1(4)が存在し、タスク1(4)は、タスク1が4つのスレッドを含むことを表し、このタスクの処理に4つのプロセッサコアを割り当てる必要がある。オンチップルータR1.1に接続されたプロセッサコアが、最初のアイドルプロセッサコアとして無作為に特定され、4つの連続するアイドルオンチップルータが、R1.1に接続されたオンチップルータと同じ行において隣接するオンチップルータに沿って順次特定され、すなわち合計4つのオンチップルータが特定され、R1.1、R1.2、R1.3、R1.4であり、これら4つのオンチップルータが、規則的な矩形の領域である第1のアイドル領域を形成し、したがってタスク1に含まれる4つのスレッドが、R1.1、R1.2、R1.3、R1.4が位置する矩形の領域内のプロセッサコアに直接割り当てられる。
【００３９】
図4Aが、本発明によるタスク割り当て方法の実施形態3におけるネットワークオンチップの概略図である。図4Aに示されるとおり、この実施形態においては、NoCが5×5のNoCであり、複数のプロセッサコアが行−列のやり方で配置され、
【数１】
2016522488.tif 000003
が高負荷のオンチップルータを表し、
【数２】
2016522488.tif 000004
が低負荷のオンチップルータを表し、
【数３】
2016522488.tif 000005
がアイドル状態のオンチップルータを表しており、すなわちR1.1〜R1.3、R2.1〜R2.4、およびR3.1〜R3.4が高負荷のオンチップルータであり、Rs0.1〜Rs0.6が低負荷のオンチップルータであり、残りがアイドル状態のルータである。具体的には、オンチップルータの負荷を判断するやり方を、必要に応じて設定することができ、例えば、オンチップルータが負うトラフィックが所定のしきい値よりも多い場合に、そのオンチップルータが高負荷のオンチップルータと判断される。
【００４０】
この実施形態においては、タスクの待ち行列に処理対象タスク2(5)が存在し、タスク2が5つのスレッドを含んでおり、このタスクの処理に5つのプロセッサコアを割り当てる必要があることを示している。オンチップルータR5.0に接続されたプロセッサコアが、最初のアイドルプロセッサコアとして無作為に特定され、連続するアイドルオンチップルータがR5.0から探索され、連続するアイドルオンチップルータが矩形の領域を形成できるか否かが判断され、種々の考えられる状況を行または列によって検討した後に適当な規則的な矩形の領域が発見されない場合、探索が行または列によって継続的に実行される。具体的には、探索が行によって実行される場合、第1のアイドル領域がR5.0から探索され、すなわちR5.0が位置する第1の行に沿って合計4つのアイドルオンチップルータ、すなわちR5.0、R5.1、R5.2、およびR5.3を含む第1のアイドル領域を探索することによって、プロセッサコアの数がスレッドの数に一致せず、すなわち第1のアイドル領域に含まれるプロセッサコアの数が、タスクが必要とするプロセッサコアの数を満たさないことが明らかになり、その場合には、第2のアイドル領域が、R5.0が位置する列から継続して探索され、第2のアイドル領域内のプロセッサコアの数と第1のアイドル領域に含まれるプロセッサコアの数との合計が5に等しい場合、すなわちR5.4が第2のアイドル領域の探索によって発見された後で、アイドルオンチップルータの数がスレッドの数に等しく、R5.0〜R5.4、Rs0.1、Rs0.2、および高負荷のオンチップルータR1.1が、規則的な矩形の領域を形成する。
【００４１】
1つの規則的な矩形の領域が、上述の第1のアイドル領域および第2のアイドル領域を使用することによって決定された後で、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータのトラフィックが、所定のしきい値を超えるか否かが判断される。具体的には、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータのトラフィックを、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測することができる。この実施形態においては、Rs0.1、Rs0.2、および高負荷のオンチップルータR1.1のトラフィックが所定のしきい値を超えるか否かを、判断する必要がある。R1.1を例として用いると、タスク2が第1のアイドル領域および第2のアイドル領域を使用することによって決定される規則的な矩形の領域に割り当てられる場合において、R1.1が元より引き受けており、図において太字の黒い矢印1を使用して示されているトラフィックと、タスク2が割り当てられた後に追加され、図において太字の黒い矢印2を使用して示されているトラフィックとの和が、所定のしきい値を超えないならば、R1.1は共有可能であると考えられ、タスク2を図に破線の囲みで示されているとおりの矩形の領域に含まれるプロセッサコアに割り当てることができるとさらに判断され、その場合には、パケットが矩形の領域内であり、XY経路指定のやり方で伝送される。例えば、R5.2が送信元のオンチップルータであり、宛て先のオンチップルータがR5.4であるならば、この場合において、XY経路指定を使用することによって、パケットをR5.2からR5.4にR5.2、R5.1、およびR5.0を通過することによって伝送でき、R5.2からR5.4にRs0.2およびRs0.1を通過することによって伝送でき、そうでないならば、タスク2が第1のアイドル領域および第2のアイドル領域を使用することによって決定される規則的な矩形の領域に割り当てられる場合に、R1.1が元より引き受けているトラフィックと、タスク2が割り当てられた後に追加されるトラフィックとの和が、所定のしきい値を超え、R1.1を共有することができないと考えられ、タスク2をこの矩形の領域に含まれるプロセッサコアに割り当てることができないとさらに判断される。
【００４２】
上記においてオンチップルータが引き受けるトラフィックが割り出された後で、3つのオンチップルータのうちの少なくとも1つが引き受けるトラフィックが所定のしきい値を超えると仮定し、R1.1が引き受けるトラフィックが所定のしきい値を超えると仮定する。この場合、探索が、行または列によってR5.0から再び実行される。具体的には、図4Bに示されるとおり、図4Bは、図4Aにおける再度の矩形の領域の探索の概略図である。
【００４３】
探索が列によって実行される場合、第3のアイドル領域がR5.0から探索され、すなわちR5.0が位置する第1の行に沿って合計3つのアイドルオンチップルータ、すなわちR5.0、R5.4、およびR5.5を含む第3のアイドル領域を探索することによって、プロセッサコアの数がスレッドの数に一致せず、すなわち第3のアイドル領域に含まれるプロセッサコアの数が、タスクが必要とするプロセッサコアの数を満たさないことが明らかになり、その場合には、第4のアイドル領域が、R5.0が位置する行から継続して探索され、第4のアイドル領域内のプロセッサコアの数と第3のアイドル領域に含まれるプロセッサコアの数との合計が5に等しい場合、すなわちR5.1およびR5.2が第4のアイドル領域の探索によって発見された後で、アイドルオンチップルータの数がスレッドの数に等しく、R5.0、R5.4、R5.5、R5.1、R5.2、ならびに第2の行および第3の行の4つの軽負荷のオンチップルータRs0.1、Rs0.2、Rs0.3、およびRs0.4が、規則的な矩形の領域を形成する。この場合、タスク2が第3のアイドル領域および第4のアイドル領域を使用することによって決定される規則的な矩形の領域に割り当てられた後に、共有のRs0.1、Rs0.2、Rs0.3、およびRs0.4が元より引き受けているトラフィックと、タスク2が割り当てられた後に追加されるトラフィックとの和が、所定のしきい値を超えず、4つの共有のオンチップルータの各々のトラフィックが所定のしきい値を超えない場合、タスク2が図4Bに破線の囲みで示されているとおりの矩形の領域に含まれるプロセッサコアに割り当てられ、そうでない場合、4つの共有のオンチップルータのうちの1つが引き受けるトラフィックが所定のしきい値を超える場合、それはタスク2をこの矩形の領域に割り当てることができないことを示しており、プロセッサコアを再び探索する必要がある。
【００４４】
上述の実施形態において、トラフィックの予測がすべての不規則な領域において成功できない場合、タスク2は、次のタスクのスケジューリングを待つべく待ち行列に保たれる。例えば、タスクが必要とするプロセッサコアが、他のタスクが処理されてより多くのプロセッサコアが解放された後で、再び探索される。
【００４５】
以上の実施形態において、第1のアイドル領域、第2のアイドル領域、第3のアイドル領域、および第4のアイドル領域が、規則的な矩形の領域であってよく、あるいは不規則な矩形の領域であってよいことに、注意すべきである。例えば、図4Aを例として使用すると、Rs0.1もアイドルオンチップルータである場合、R5.0からの探索によって発見される連続するアイドルオンチップルータは、R5.0、R5.1、5.2、R5.4、およびRs0.1を含み、Rs0.2がアイドルオンチップルータであり、R5.4、Rs0.1、およびR1.1が非アイドルのオンチップルータである場合、R5.0からの探索によって発見される連続するアイドルオンチップルータは、R5.0、R5.1、R5.2、Rs0.2、およびR5.3を含む。
【００４６】
本発明のタスク割り当て方法の有益な効果を、先行技術の経路指定サブネットにもとづくタスク割り当て方法の有益な効果と明瞭に比較するために、本発明の技術的解決策および既存の技術的解決策を、種々のトラフィックモデルを使用することによって分析する。
【００４７】
図5Aは、本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、ユニフォームランダムトラフィックモデルを使用することによる分析の概略図である。図5Aに示されるように、ユニフォームランダムトラフィックモデル（Uniform）において、横座標は、注入率（injection ratio）であり、ネットワークオンチップのプロセッサコアの利用と理解することができ、縦座標は、ディレイデュレーション（delay duration）であり、
【数４】
2016522488.tif 000006
は、本発明における注入率およびディレイデュレーションの対応する曲線を示し、
【数５】
2016522488.tif 000007
は、経路指定サブネットにもとづくタスク割り当て方法における注入率およびディレイデュレーションの対応する曲線を示している。
【００４８】
図5Aに示されるとおり、注入率が0〜6×10-3である場合、ネットワークオンチップ全体のプロセッサコアの利用は高くなく、このやり方で、本発明の技術的解決策のディレイデュレーションは、既存の技術的解決策のディレイデュレーションに基本的に等しい。しかしながら、プロセッサコアの利用が高くなるにつれて、同じディレイデュレーションに対応する本発明の技術的解決策と既存の技術的解決策との間の差は大きくなり、経路指定サブネットにもとづくタスク割り当て方法においては、より大きい注入率は、より大きいディレイデュレーションを対応して示し、これはネットワークオンチップの性能がより低く、すなわちディレイが明らかに増加し、ネットワークのスループットが低いことを示しているが、本発明のタスク割り当て方法においては、注入率が大きくなってもディレイデュレーションの増加は比較的ゆっくりであり、これはネットワークオンチップの良好な性能、すなわち遅延が明白には増えず、ネットワークのスループットが大きいことを示している。
【００４９】
図5Bは、本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、圧縮ビット（bitcomp）トラフィックモデルを使用することによる分析の概略図である。同様に、図5Aに示されるように、図5Bに示される圧縮ビットトラフィック（Bitcomp）トラフィックモデルにおいて、横座標は、注入率であり、ネットワークオンチップのプロセッサコアの利用と理解することができ、縦座標は、ディレイデュレーションであり、
【数６】
2016522488.tif 000008
は、本発明における注入率およびディレイデュレーションの対応する曲線を示し、
【数７】
2016522488.tif 000009
は、経路指定サブネットにもとづくタスク割り当て方法における注入率およびディレイデュレーションの対応する曲線を示している。注入率が2×10-3よりも大きい場合に、本発明の有益な効果をはっきりと見ることができる。
【００５０】
図5Cは、本発明のタスク割り当て方法および経路指定サブネットにもとづくタスク割り当て方法について、トルネード（tornado）トラフィックモデルを使用することによる分析の概略図である。同様に、図5Aに示されるように、図5Cに示されるトルネード（Tornado）トラフィックモデルにおいて、横座標は、注入率であり、ネットワークオンチップのプロセッサコアの利用と理解することができ、縦座標は、ディレイデュレーションであり、
【数８】
2016522488.tif 000010
は、本発明における注入率およびディレイデュレーションの対応する曲線を示し、
【数９】
2016522488.tif 000011
は、経路指定サブネットにもとづくタスク割り当て方法における注入率およびディレイデュレーションの対応する曲線を示している。注入率が4×10-3よりも大きい場合に、本発明の有益な効果をはっきりと見ることができる。
【００５１】
さらに、本発明のタスク割り当て方法の有益な効果と、先行技術の経路指定サブネットにもとづくタスク割り当て方法の有益な効果とを分かりやすく比較するために、本発明のルータ共有の有益な効果を、システム利用表を使用することによる先行技術におけるサブネットにもとづく分割法と比較する。
【００５２】
【表１】
2016522488.tif 000012
【００５３】
表1が、ネットワークの負荷率が0.5〜1である場合における矩形のサブネット分割法のシステムの利用と本発明のルータ共有法のシステムの利用との間の比較表である。0.5〜1というネットワークの負荷率は、システムが実際に提供することができるプロセッサコアに対する必要なプロセッサコアの比を表し、例えば表1における列は、システムが実際に提供することができるプロセッサコアに対する必要なプロセッサコアの比が0.5であるとき、システムは不飽和の状態にあり、この場合において、矩形のサブネット分割法にもとづくシステムの利用が0.478033である一方で、本発明のルータ共有法にもとづくシステムの利用は0.465374であり、システムの利用の間の差は小さい。しかしながら、ネットワークの負荷が継続的に増加し、ネットワークの負荷率が0.9になると、システムは次第に飽和の状態になり、矩形のサブネット分割法にもとづくシステムの利用は0.701311であり、本発明のルータ共有法にもとづくシステムの利用は0.766011であり、最終的にネットワークの負荷が100%に達し、すなわちシステムが飽和する場合、矩形のサブネット分割法にもとづくシステムの利用は0.707254であり、本発明のルータ共有法にもとづくシステムの利用は0.810507であり、システムの利用の間の差はほぼ10%である。
【００５４】
上述の実施形態において、ネットワークオンチップのアイドルプロセッサコアが最初のアイドルプロセッサコアとして無作為に使用され、プロセッサコアの再度の探索が必要とされる場合に、探索が最初のアイドルプロセッサコアから実行されるが、本発明がこれに限られず、他の考えられる実施のやり方においては、最初のアイドルプロセッサコアを予め設定される規則に従って選択してもよく、探索が実行されるたびに、最初のアイドルプロセッサコアが違ってもよいことに、注意すべきである。さらに、ネットワークオンチップ内の連続するアイドルプロセッサコアが位置する非矩形の領域の数が2以上である場合、或る領域内のプロセッサを最初のアイドルプロセッサコアとして無作為に決定することができる。
【００５５】
図6が、本発明によるタスク割り当て装置の実施形態1の概略の構造図である。図6に示されるように、この実施形態において提供されるタスク割り当て装置は、とりわけ、タスク割り当て装置に適用され、本発明の任意の実施形態において提供される方法の種々のステップを実行することができ、具体的な実施のプロセスの再度の説明は、ここでは行わない。この実施形態において提供されるタスク割り当て装置は、とりわけ、
処理対象タスクに含まれるスレッドの数を明らかにするように構成された第1の決定モジュール11と、
マルチコアプロセッサによって形成されたネットワークオンチップにおいて、スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定するように構成された第2の決定モジュール12と、
第2の決定モジュール12によって特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、ネットワークオンチップにおいて非矩形の領域から拡大された矩形の領域を探索および決定するように構成された第3の決定モジュール13と、
非アイドルのプロセッサコアに接続された第3の決定モジュールによって決定された矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、処理対象タスクのスレッドを各々のアイドルプロセッサコアに1つのスレッドが割り当てられるようにアイドルプロセッサコアに割り当てるように構成された割り当てモジュール14と
を備える。
【００５６】
本発明のこの実施形態において提供されるタスク割り当て装置によれば、第1の決定モジュールが、処理対象タスクに含まれるスレッドの数を明らかにし、第2の決定モジュールが、ネットワークオンチップにおいて、必要とされるスレッドの数に等しい数の複数のアイドルプロセッサコアによって形成される非矩形の領域を特定し、ここで非矩形の領域に隣接するエッジオンチップルータと、アイドルプロセッサコアに接続された非矩形の領域内のオンチップルータとが、規則的な矩形の領域を形成し、次いで第3の決定モジュールが、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータ、すなわちエッジオンチップルータについて、そのトラフィックが所定のしきい値を超えるか否かを判断し、超えない場合に、割り当てモジュールが、処理対象タスクをアイドル領域内のプロセッサコアに割り当てる。本発明のこの実施形態において提供されるタスク割り当て方法によれば、ネットワークオンチップ内のアイドルプロセッサコアリソースの数が、処理対象タスクが必要とするプロセッサコアの数以上であるときに、処理対象タスクが割り当てられる規則的な矩形の領域が存在しない場合に、非矩形の領域が、エッジルータを使用することによって規則的な矩形の領域を形成し、処理対象タスクが割り当てられ、矩形の領域においては、送信元のオンチップルータから宛て先のオンチップルータまでのパケットの経路指定機構を、経路指定表を使用することによって決定する必要がなく、パケットがXY経路指定のやり方で伝送されるため、経路指定サブネットにもとづくタスク割り当て方法におけるハードウェアのオーバヘッドが大き、ネットワークのスループットが小さい、およびシステムの利用率が低いという問題が回避される。
【００５７】
さらに、第3の決定モジュール13は、
非矩形の領域から拡大される矩形の領域を、ネットワークオンチップにおける非矩形の領域を含む最小の矩形領域として決定する
ように特に構成される。
【００５８】
さらに、割り当てモジュール14は、
第2の決定モジュール12によって特定された複数のアイドルプロセッサコアに接続されたオンチップルータが矩形の領域を形成する場合に、処理対象タスクのスレッドを各々のプロセッサコアに1つのスレッドが割り当てられるようにアイドルプロセッサコアにそれぞれ割り当てる
ようにさらに構成される。
【００５９】
さらに、第2の決定モジュール12は、
マルチコアプロセッサによって形成され、複数のプロセッサコアを行−列のやり方で配置して含んでいるネットワークオンチップにおいて、最初のアイドルプロセッサコアを決定し、
マルチコアプロセッサによって形成されたネットワークオンチップにおいて、最初のアイドルプロセッサコアを出発点として使用することによって、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定する
ように特に構成される。
【００６０】
さらに、第2の決定モジュール12は、
スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って順次判断し、
同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、スレッドの数に一致しない場合に、連続する第2のアイドル領域を、最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、第1のアイドル領域内のプロセッサコアの数と第2のアイドル領域内のプロセッサコアの数との合計がスレッドの数に等しくなるように順次決定する
ように特に構成される。
【００６１】
さらに、第2の決定モジュール12は、
スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って順次判断し、
同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、スレッドの数に一致しない場合に、連続する第4のアイドル領域を、最初のアイドルプロセッサに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、第3のアイドル領域内のプロセッサコアの数と第4のアイドル領域内のプロセッサコアの数との合計がスレッドの数に等しくなるように順次決定する
ように特に構成される。
【００６２】
図7が、本発明によるタスク割り当て装置の実施形態2の概略の構造図である。図7に示されるように、図6に示した装置にもとづいて、この実施形態において提供されるタスク割り当て装置は、
非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータの履歴トラフィック情報に従って、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータのトラフィックを予測し、予測トラフィックを得るように構成された予測モジュール15
をさらに備えることができる。
【００６３】
図8が、本発明によるタスク割り当て装置の実施形態3の概略の構造図である。図8に示されるとおり、この実施形態におけるタスク割り当て装置800は、プロセッサ81およびメモリ82を備えることができる。タスク割り当て装置800は、送信機83および受信機84をさらに備えることができる。送信機83および受信機84は、プロセッサ81に接続されてよく、メモリ82は、実行インストラクションを記憶し、タスク割り当て装置800の動作時に、プロセッサ81はメモリ82と通信し、プロセッサ81は、メモリ82内の実行インストラクションを呼び出して、以下の動作を実行し、すなわち
タスク割り当て装置800は、処理対象タスクに含まれるスレッドの数を明らかにし、
マルチコアプロセッサによって形成されたネットワークオンチップにおいて、スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定し、
特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、ネットワークオンチップにおいて非矩形の領域から拡大された矩形の領域を探索および決定し、
非アイドルのプロセッサコアに接続された拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、処理対象タスクのスレッドを、各々のアイドルプロセッサコアに1つのスレッドが割り当てられるように、アイドルプロセッサコアに割り当てる。
【００６４】
随意により、非矩形の領域から拡大される矩形の領域は、ネットワークオンチップにおける非矩形の領域を含む最小の矩形領域である。
【００６５】
随意により、マルチコアプロセッサによって形成されたネットワークオンチップにおいて、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定した後で、本方法は、
特定されたアイドルのプロセッサコアのオンチップルータによって形成される領域が矩形の領域である場合に、処理対象タスクのスレッドを、各々のプロセッサコアに1つのスレッドが割り当てられるようにアイドルプロセッサコアに割り当てること
をさらに含む。
【００６６】
随意により、ネットワークオンチップは、行−列のやり方で配置された複数のプロセッサコアを含み、
したがって、マルチコアプロセッサによって形成されたネットワークオンチップにおいて、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定することは、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、最初のアイドルプロセッサコアを決定すること、および
マルチコアプロセッサによって形成されたネットワークオンチップにおいて、最初のアイドルプロセッサコアを出発点として使用することによって、スレッドの数に一致する数の複数の連続するアイドルプロセッサコアを特定すること
を含む。
【００６７】
随意により、特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、非矩形の領域から拡大された矩形の領域を探索および決定することは、
スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って順次判断すること、および
同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、スレッドの数に一致しない場合に、連続する第2のアイドル領域を、最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、第1のアイドル領域内のプロセッサコアの数と第2のアイドル領域内のプロセッサコアの数との合計がスレッドの数に等しくなるように順次決定すること
を含む。
【００６８】
随意により、特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、非矩形の領域から拡大された矩形の領域を探索および決定することは、
スレッドの数に一致する数の複数の連続するアイドルプロセッサコアが存在するか否かを、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って順次判断すること、および
同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、スレッドの数に一致しない場合に、連続する第4のアイドル領域を、最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、第3のアイドル領域内のプロセッサコアの数と第4のアイドル領域内のプロセッサコアの数との合計がスレッドの数に等しくなるように順次決定すること
を含む。
【００６９】
随意により、非アイドルのプロセッサコアに接続された拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、処理対象タスクのスレッドをアイドルプロセッサコアにそれぞれ割り当てる前に、本方法は、
非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータのトラフィックを、非アイドルのプロセッサコアに接続された矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、予測トラフィックを得ること
をさらに含む。
【００７０】
上述のタスク割り当て方法およびタスク割り当て装置にもとづき、本発明の実施形態は、複数のプロセッサコアと、オンチップルータと、配線と、図6または図7に示され、図2〜図4Aのいずれかの方法の実施形態の技術的解決策を相応に実行することができ、ここでは細部の再度の説明は省略されるいずれかのタスク割り当て装置とを備えるネットワークオンチップをさらに提供する。
【００７１】
最後に、以上の実施形態が、あくまでも本発明の技術的解決策の説明を意図しており、本発明を限定しようとするものではないことに、注意すべきである。本発明を、以上の実施形態を参照して詳しく説明したが、当業者であれば、本発明の実施形態の技術的解決策の技術的範囲から離れることなく、以上の実施形態において説明された技術的解決策について変更を加えることが依然として可能であり、あるいは以上の実施形態において説明された技術的解決策の一部またはすべての技術的特徴について均等な置き換えが依然として可能であることを、理解すべきである。
【図１】
2016522488.tif 000013
【図２】
2016522488.tif 000014
【図３】
2016522488.tif 000015
【図４Ａ】
2016522488.tif 000016
【図４Ｂ】
2016522488.tif 000017
【図５Ａ】
2016522488.tif 000018
【図５Ｂ】
2016522488.tif 000019
【図５Ｃ】
2016522488.tif 000020
【図６】
2016522488.tif 000021
【図７】
2016522488.tif 000022
【図８】
2016522488.tif 000023
【手続補正書】
【提出日】平成27年12月25日(2015.12.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明の実施形態は、マルチコアネットワークオンチップ技術に関し、特にタスク割り当て方法、タスク割り当て装置、およびネットワークオンチップに関する。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
本発明の実施形態の目的、技術的解決策、および利点をさらに明瞭にするために、以下で、本発明の実施形態における技術的解決策を、本発明の実施形態における添付の図面を参照して、明確かつ充分に説明する。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
処理対象タスクに含まれるスレッドの数を明らかにするステップと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定するステップと、
前記ネットワークオンチップにおいて、前記特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップと、
非アイドルのプロセッサコアに接続された前記拡大後の矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てるステップと
を含むタスク割り当て方法。
【請求項２】
前記非矩形の領域から拡大される矩形の領域は、前記ネットワークオンチップにおいて前記非矩形の領域を含む最小の矩形の領域である請求項1に記載の方法。
【請求項３】
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアを特定するステップの後で、
該特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、矩形の領域である場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てるステップ
をさらに含む請求項1または2に記載の方法。
【請求項４】
前記ネットワークオンチップは、行−列のやり方で配置された複数のプロセッサコアを含み、
したがって、マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアを特定するステップは、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて最初のアイドルプロセッサコアを特定するステップと、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアを特定するステップと
を含む請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に等しくない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿った第2のアイドル領域内の連続するプロセッサコアの数を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内の前記プロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む請求項4に記載の方法。
【請求項６】
前記特定されたアイドルプロセッサコアのオンチップルータによって形成される領域が、非矩形の領域である場合に、該非矩形の領域から拡大される矩形の領域を探索および決定するステップは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数等しい数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断するステップと、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に等しくない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿った第4のアイドル領域内の連続するプロセッサコアの数を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定するステップと
を含む請求項4に記載の方法。
【請求項７】
非アイドルのプロセッサコアに接続された前記矩形の領域内の各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクに含まれるスレッドを前記アイドルプロセッサコアにそれぞれ割り当てるステップの前に、
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得るステップ
をさらに含む請求項1から6のいずれか一項に記載の方法。
【請求項８】
処理対象タスクに含まれるスレッドの数を明らかにする第1の決定モジュールと、
マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアであって、各々が1つのオンチップルータに接続されているアイドルプロセッサコアを特定する第2の決定モジュールと、
前記第2の決定モジュールによって特定されたアイドルプロセッサコアに接続されたオンチップルータによって形成される領域が、非矩形の領域である場合に、前記ネットワークオンチップにおいて前記非矩形の領域から拡大される矩形の領域を探索および決定する第3の決定モジュールと、
前記第3の決定モジュールによって決定された矩形の領域内の非アイドルのプロセッサコアに接続された各々のオンチップルータの予測トラフィックが、所定のしきい値を超えない場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアに割り当て、各々のアイドルプロセッサコアに1つのスレッドを割り当てる割り当てモジュールと
を備えるタスク割り当て装置。
【請求項９】
前記第3の決定モジュールは、
前記非矩形の領域から拡大される矩形の領域を、前記ネットワークオンチップにおける前記非矩形の領域を含む最小の矩形の領域であるように決定する
ように特に構成されている請求項8に記載のタスク割り当て装置。
【請求項１０】
前記割り当てモジュールは、
前記第2の決定モジュールによって特定された複数のアイドルプロセッサコアに接続されたオンチップルータが、矩形の領域を形成する場合に、前記処理対象タスクのスレッドを前記アイドルプロセッサコアにそれぞれ割り当て、各々のプロセッサコアに1つのスレッドを割り当てる
ようにさらに構成されている請求項8または9に記載のタスク割り当て装置。
【請求項１１】
前記第2の決定モジュールは、
前記マルチコアプロセッサによって形成され、行−列のやり方で配置された複数のプロセッサコアを備えているネットワークオンチップにおいて、最初のアイドルプロセッサコアを特定し、
前記マルチコアプロセッサによって形成されるネットワークオンチップにおいて、前記最初のアイドルプロセッサコアを出発点として使用することによって、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアを特定する
ように特に構成されている請求項8から10のいずれか一項に記載のタスク割り当て装置。
【請求項１２】
前記第2の決定モジュールは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿って、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ行の隣接するオンチップルータに沿って順次判断される第1のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に等しくない場合に、前記最初のアイドルプロセッサに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿った第2のアイドル領域内の連続するプロセッサコアの数を、前記第1のアイドル領域内のプロセッサコアの数と該第2のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成されている請求項11に記載のタスク割り当て装置。
【請求項１３】
前記第2の決定モジュールは、
前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ列の隣接するオンチップルータに沿って、前記スレッドの数に等しい数の複数の連続するアイドルプロセッサコアが存在するか否かを順次判断し、
前記同じ列の隣接するオンチップルータに沿って順次判断される第3のアイドル領域内の連続するプロセッサコアの数が、前記スレッドの数に等しくない場合に、前記最初のアイドルプロセッサコアに接続されたオンチップルータと同じ行の隣接するオンチップルータに沿った第4のアイドル領域内の連続するプロセッサコアの数を、前記第3のアイドル領域内のプロセッサコアの数と該第4のアイドル領域内のプロセッサコアの数との合計が前記スレッドの数に等しくなるように順次特定する
ように特に構成されている請求項11に記載のタスク割り当て装置。
【請求項１４】
前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータのトラフィックを、前記非アイドルのプロセッサコアに接続された前記矩形の領域内のオンチップルータの履歴トラフィック情報に従って予測し、前記予測トラフィックを得る予測モジュール
をさらに備える請求項8から13のいずれか一項に記載のタスク割り当て装置。
【請求項１５】
複数のプロセッサコアと、オンチップルータと、配線とを備えており、請求項8から14のいずれか一項に記載のタスク割り当て装置をさらに備えているネットワークオンチップ。
【国際調査報告】
2016522488.tif 000024
2016522488.tif 000025
2016522488.tif 000026
2016522488.tif 000027