JP2010079622A - マルチコアプロセッサシステム、および、そのタスク制御方法 - Google Patents

Abstract

【課題】マルチコアプロセッサシステムにおいて、ＣＰＵコアの負荷による処理遅延の増加と、通信時間増加による処理の待ち時間の増加の両者を考慮して、タスクのスケジューリングをおこない、処理化の効率化をおこなう。
【解決手段】タスク複製をおこなって、並列処理プログラムを実行させるための各ＣＰＵコアによって実行されるタスクの実行パターンを複数生成する。そして、専従処理プログラムを実行時の状態を反映した推定負荷を求めて、その推定負荷に基づき、各ＣＰＵコアの処理の実行時間を計算する。また、ＣＰＵコア間での通信時間を計算して、各ＣＰＵコアの処理の実行時間とＣＰＵコア間での通信時間との合計を、各々の実行パターンの推定所要時間し、推定所要時間の一番小さな実行パターンを最適な実行パターンとして選択して、各々の実行パターンに基づき、各タスクを実行する。
【選択図】図５

Description

本発明は、マルチコアプロセッサシステム、および、そのタスク制御方法に係り、特に、ハードウェア資源に制限がある組み込み機器のプロセッサで、並列処理を効率的に実行するのに好適なマルチコアプロセッサシステムのタスク制御方法に関する。

マルチコアプロセッサ（Multiple core Processor、Multi-core Processor）は、一つのＣＰＵパッケージ内に複数のＣＰＵコアを封入したプロセッサである。このマルチコアプロセッサは、外部的には１つのＣＰＵでありながら内部的には２つのＣＰＵとして認識されるため、主に並列処理をおこなわせる環境下において、ＣＰＵチップ全体での処理能力を上げ、性能向上を果たすために用いられる。

特に、近年では、組込み機器向けへのマルチコア技術の応用が期待されている。

このように複数のプロセッサによって、並列処理をおこなうシステムに関しては、特許文献１に開示がある。この特許文献１では、「マルチプロセッサ上でシングルプロセッサ向けＯＳと既存のアプリケーションをそれらに改造を加えることなく動作させる」ために、アプリケーションを並列化が可能な処理単位に分割して、各々のプロセッサで制御する技術が開示されている。

また、特許文献２には、「膨大な繰り返し演算を必要とする分割問題においても全てのＣＰＵを有効に活用しＣＰＵの数が増大しても並列処理効率を向上させる」ために、セルコンピュータの稼働率を勘案し、他のセルコンピュータに元のプログラムを複製したクーロンプログラムを他のセルコンピュータに実行させる技術が開示されている。

さらに、非特許文献１には、「並列プログラムを分散メモリアーキテクチャ上にスケジューリングする際に発生する通信遅延を削減するため」に、「タスク複製による通信コストを定量的に分析し、選ばれたタスクを複製すべきかどうかの条件」を導いている。

特開２００３−３４５６１４号公報 特開２００３−９９４１２号公報 高木ほか「通信時間を削除するためのタスク複製手法」、情報処理学会研究報告．［ハイパフォーマンスコンピューティング］、vol.99, No.21, pp.19-24

上記従来技術は、いずれもマルチプロセッサ上で並列処理をおこなう技術に関するものである。

しかしながら、特許文献１においては、並列処理をどのように効率的に実行していくかについては記載されていない。

また、非特許文献１においては、タスク複製に起因する処理時間の増加が課題となる。一般にタスク複製をおこなうと、タスク複製をおこなわない場合とは異なる通信がおこなわれる。この通信の通信時間が、タスク複製をおこなった場合の処理の効率化される時間と比較して小さい場合、通信によるオーバヘッドは問題とはならない。しかし、タスク複製により、本来存在しないタスクを実行するため、ＣＰＵの処理負荷が増加し、実行しようとしている並列プログラムよりも優先度の低い他の処理は実行が遅延するというおそれがある。反面、実行しようとしている並列プログラム以外の他の処理が優先して実行されると、複製したタスクの実行時間が伸び、反って並列プログラムの処理時間が増加すると言うおそれがある。

さらに、特許文献２においては、並列処理を実行する際のタスク間の通信時間を削減することについては記載がない。この特許文献２で提案されている手法は、通信時間を考慮した並列処理のスケジューリングをおこなっていない。しかしながら、ＣＰＵコア間で共有されるメモリの容量や速度、ＣＰＵコアを結合するバスの速度によって、通信時間が処理時間よりも大きくなる状況が考えられる。例えば、特定の機能を実現する目的で各機器にコンピュータを組み込む組込み機器では、コストが非常に重要であるためメモリ容量が制限されることが多く、通信に使用できるメモリ容量は小さくなる。このような組込み機器においては、大容量のメモリ領域を使用するアプリケーションに対して並列処理を適用する場合、通信用のメモリ容量が小さいと通信回数が増加し、通信スループットが低下し、ひいては処理待ち時間の増加による、並列処理効率の低下が発生するという問題点がある。

本発明は、上記問題点を解決するためになされたもので、その目的は、マルチコアプロセッサシステムにおいて、ＣＰＵコアの負荷による処理遅延の増加と、通信時間増加による処理の待ち時間の増加の両者を考慮して、タスクのスケジューリングをおこない、処理化の効率化をおこなうタスク制御方法を提供することにある。

本発明のマルチコアプロセッサシステムでは、実行パターン生成部により、並列処理プログラムを実行させるための各ＣＰＵコアによって実行されるタスクの実行スケジュールの実行パターンを複数生成するようにする。この実行パターン生成時には、同一のタスクを異なるＣＰＵコアに実行させるためのタスク複製をおこなった実行パターンを生成する。

そして、一つのＣＰＵコアにのみ実行される専従処理プログラムを実行時の状態を反映した推定負荷を求めて、その推定負荷に基づき、各ＣＰＵコアの処理の実行時間を計算する。また、ＣＰＵコア間での通信時間を計算して、各ＣＰＵコアの処理の実行時間とＣＰＵコア間での通信時間との合計を、各々の実行パターンの推定所要時間とする。

スケジューリング部は、推定所要時間の一番小さな実行パターンを最適な実行パターンとして選択して、各々の実行パターンに基づき、各タスクを実行するように、タスク実行部に指示を与える。

本発明によれば、マルチコアプロセッサシステムにおいて、ＣＰＵコアの負荷による処理遅延の増加と、通信時間増加による処理の待ち時間の増加の両者を考慮して、タスクのスケジューリングをおこない、処理化の効率化をおこなうタスク制御方法を提供することができる。

以下、本発明の一実施形態を、図１ないし図１５を用いて説明する。
（I）マルチコアプロセッサシステムのハードウェア環境
先ず、図１を用いて本発明の一実施形態に係るマルチコアプロセッサシステムのハードウェア構成について説明する。
図１は、本発明の一実施形態に係るマルチコアプロセッサシステムのハードウェア構成図である。

現在のマルチコア搭載システムでは、各ＣＰＵコア、およびメモリとＩ／Ｏが単一のバスに結線され、すべてのコアがメモリ、およびＩ／Ｏを共有する構成を取るシステムが多くなっており、本実施形態でもそのような構成を取るものとする。

本実施形態のマルチコアプロセッサシステムは、図１に示されるように、マルチコアプロセッサ１０１が、複数のＣＰＵコア１Ｃ１、１Ｃ２、…、１ＣＮを保持している。そして、各々のＣＰＵコアは、共有メモリ１０２やＩ／Ｏ１０３と、バス１０４により結線されている。

ＣＰＵコアは、プログラムによって様々な数値計算や情報処理、機器制御などをおこない、演算をするＡＬＵ（Arithmetic and Logic Unit）、データを一時記憶するレジスタ、ＣＰＵコア全体を制御する制御部分などで構成されている。

共有メモリは、マルチコア１０１の保持する各ＣＰＵコアがアクセスする情報を保持する記憶装置であり、各ＣＰＵコアが実行する演算に必要な情報は、共有メモリ１０２内の対応する使用領域１Ｍ１、１Ｍ２、…、１ＭＮなどに保持される。

また、共有メモリ１０２内に、複数のコアが相互にデータを通信するための共有領域１ＭＣを設ける。

Ｉ／Ｏ１０３は、各ＣＰＵコアと入出力装置とのインターフェイスをおこなうための制御回路である。
（II）並列プログラムの実行環境のシステム階層
次に、図２を用いてマルチコアプロセッサシステム上で実行される並列プログラムの実行環境のシステム階層について説明する。
図２は、本発明の一実施形態に係るマルチコアプロセッサシステム上で実行される並列プログラムの実行環境のシステム階層を示す図である。

本実施形態のシステム階層としては、図２に示されるように、ハードウェアレイヤＬＩ、ＯＳレイヤＬＩＩ、アプリケーションレイヤＬＩＩＩの三階層により構成されているものとする。

ハードウェアレイヤＬＩに属するＣＰＵコア１Ｃ１、１Ｃ２、…、１ＣＮは、図１で説明したハードウェアの装置である。

そして、各々の上でＯＳレイヤＬＩＩに属するＯＳ（Operating System）（Ｏ１、Ｏ２、…、ＯＮ）を実行する。ＯＳは、アプリケーションプログラムとハードウェアの制御をおこない、各々のアプリケーションプログラムにハードウェアのリソースを分配する。

アプリケーションレイヤＬＩＩＩは、ＯＳレイヤ上で動作するプログラムが属するレイヤであり、並列処理プログラムＰ１、…、ＰＭと、専従処理プログラムＳ１と、ミドルウェアＭ１が含まれている。

並列処理プログラムＰ１、…、ＰＭは、各々の処理を各ＣＰＵコアにより並列実行が可能なプログラムである。ＯＳ上で実行されるプログラム単位は、タスクであり、各ＯＳへの割り当ては、ミドルウェアＭ１でおこなわれる。専従処理プログラムＳ１は、一つのＣＰＵコアで実行されることが想定されるプログラムである。

なお、通常、並列処理プログラムは、プログラム作成者が並行処理について意識してコーディングする必要がある。
（III）タスクと実行パターン
次に、図３および図４を用いて本発明の理解のために、タスクと実行パターンについて説明する。
図３は、本発明の一実施形態の並列処理のタスクグラフを例示した図である。
図４は、図３に示したタスクグラフの並列処理の実行パターンを示した図である。

一般に、複数の演算装置により、処理を並列実行する情報処理システムにおいて、並列実行される個々の処理を「タスク」、各演算装置に対してタスクを割り当てることを「スケジューリング」と呼んでいる。並列処理においては、タスクの実行に他のタスクの実行結果が必要となる場合があり、この場合に、本実施形態では、実行結果を引き渡すタスクを「先行タスク」、実行結果を受け取るタスクを「後続タスク」と呼ぶ。また、先行タスクと後続タスクの関係を、「タスクの依存関係」と呼ぶことにする。

ここで、図３のタスクグラフは、タスクの依存関係を表したものである。

また、図４は、実行パターンの例を表したものである。実行パターンは、タスクグラフ上に、タスクの関係に加え、タスクを実行するＣＰＵコアを示したものを言う。

図３において、Ｔ１、Ｔ２、Ｔ３はタスクを、ｅｎｔｒｙ、ｅｘｉｔは並列処理の始点と終点のタスクを、ａ、ｂ、ｃ、ｄ、ｅはタスク実行結果の引渡し（タスク間の通信）を意味している。

なお、本実施形態を実施する際のタスク、およびタスク間の通信についての受け渡される情報については、後に、図６のタスクグラフ情報のデータ構造の例を示して、詳細に説明する。

図４に示されるように、実行パターン１は、タスクＴ１、Ｔ２、Ｔ３をＣＰＵ１で実行した場合の例を示している。また、実行パターン２は、タスクＴ３をＣＰＵ１で、タスクＴ１、Ｔ２をＣＰＵ２で実行した場合の例である。さらに、実行パターン６は、実行パターン２のタスクＴ１を複製し、タスクＴ１、Ｔ３をＣＰＵ１で、タスクＴ１、Ｔ２をＣＰＵ２で実行した場合の例を示している。

なお、ｅｎｔｒｙ、ｅｘｉｔは並列処理の始点と終点のタスクを意味するため、常に並列処理の実行依頼がおこなわれたＣＰＵコアにおいて実行される。

本実施形態を実施する際の実行パターンの情報については、後に、図８の実行パターンリストのデータ構造の例を示して、詳細に説明する。
（IV）モジュール構成の詳細
次に、図５を用いて本発明の一実施形態に係るマルチコアプロセッサシステムのタスク制御方法をおこなう際のモジュール構成の詳細について説明する。
図５は、本発明の一実施形態に係るマルチコアプロセッサシステムのモジュール構成を示す図である。

各コアが実行するモジュール、データは、図１に示した共有メモリ１０２上の各コア使用領域１Ｍ１、１Ｍ２、…、共有領域１ＭＣに配置される。また、図５において、「〜部」と記述される各々の機能を有するモジュールは、メモリ上に配置される実行コードが、ＣＰＵコア１Ｃ１、１Ｃ２において実行されるモジュールである。

ＣＰＵ１が使用する領域であるＣＰＵ１使用領域１Ｍ１には、並列処理プログラム３１１、並列処理実行部２１１、専従処理プログラム３１７が保持される。同様に、ＣＰＵ１が使用する領域であるＣＰＵ２使用領域１Ｍ２には、並列処理プログラム３２１、並列処理実行部２２１、専従処理プログラム３２３が保持される。また、共有領域１ＭＣは、タスク実行情報３Ｃ１が保持する。

並列処理プログラム３１１は、並列実行する部分を含むアプリケーションプログラムである。なお、並列処理に適したアプリケーションプログラムは、相互にデータ通信が少ない異なる処理を複数実行するアプリケーションプログラムや、複数のデータを入力して各データに対して独立に同じ処理を実行するアプリケーションプログラムである。例えば、複数の画像データを入力し、画像エンコード／デコードを並列実行する画像管理アプリケーションプログラムなどがある。

また、ＣＰＵ１使用領域１Ｍ１上の並列処理プログラム３１１は、並列実行する部分をＣＰＵ１で実行するために必要な実行コード、メモリ領域を保持し、 ＣＰＵ２使用領域１Ｍ２上の並列処理プログラム３２１は、並列実行する部分をＣＰＵ２で実行するために必要な実行コード、メモリ領域を保持する。

並列処理実行部２１１は、並列処理プログラム実行部３１１から並列処理依頼を受け、並列処理を実行するモジュールである。この並列処理実行部２１１は、図２に示したミドルウェアＭ１に該当する。並列処理は、並列処理実行部２１１、２２１において分散実行される。そして、並列処理実行部２１１、２２１において実行された並列処理の結果を、並列処理実行部２１１が統合し、並列処理結果として並列処理プログラム３１１に返す。

専従処理プログラム３１７、３２３は、複数のＣＰＵコアにおいて並列実行されない、各ＣＰＵコア固有のアプリケーションプログラムである。なお、並列実行されないアプリケーションプログラムの例としては、各ＣＰＵコア特有の機能を利用するアプリケーションプログラムや、通信データが多く並列実行効率が低いアプリケーションプログラムが挙げられる。専従処理プログラム３１７は、ＣＰＵ１において実行され、専従処理プログラム３２３は、ＣＰＵ２において実行される。

タスク実行情報３Ｃ１は、各ＣＰＵコアによってタスクを実行するために必要な情報である。タスク実行情報３Ｃ１については、後に、図７にタスク実行情報３Ｃ１のデータ構造の例を示して、詳細に説明する。

並列処理プログラム３１１は、逐次実行部３１２と、並列化対象部３１３により構成され、並列処理プログラム３２１は、並列化対象部３２２により構成される。ここでは、並列処理プログラム３２１は、説明の都合上、逐次実行部を持たないことにしている。

逐次実行部３１２は、並列処理プログラム３１１の逐次処理される部分である。

並列化対象部３１３、３２２は、並列処理プログラム３１１、３１２の各々のＣＰＵ１、２により並列実行される部分である。

並列処理実行部２１１は、実行パターン生成部２１２、タスクスケジューリング部２１３、タスク実行部２１４、タスク実行結果統合部２１５、負荷推定部２１６、タスクグラフ情報３１５、実行パターンリスト３１４、負荷情報３１６により構成され、並列処理実行部２２１は、タスク実行部２２２と、負荷推定部２２３により構成される。

実行パターン生成部２１２は、タスクグラフ情報３１５に基づいて、各タスクを実行するＣＰＵコアを決定した実行パターンの実行パターンリスト３１４を生成する。

タスクスケジューリング部２１３は、負荷情報３１６を読み取り、実行パターンリスト３１４から最適な実行パターンを選択する。また、選択した実行パターンに従い、タスク実行部２１４、２２２にタスクの実行を依頼する。

タスク実行部２１４、２２２は、タスクスケジューリング部２１３からのタスク実行依頼を受け、タスクの実行をおこなう。タスクの実行は、タスク実行情報３Ｃ１に基づいて、並列化対象部３１３、３２２を実行する。また、タスクの完了時にタスク実行結果統合部にタスク完了を通知する。

タスク実行結果統合部２１５は、タスク実行部２１４、２２２からタスク完了通知を受け、タスクの実行結果を統合し、並列処理結果として並列処理プログラム３１１に伝達する。

負荷推定部２１６、２２３は、各ＣＰＵコアにおける専従処理プログラム３１７、３２３による負荷を推定する。そして、推定した各ＣＰＵコアの負荷を負荷情報３１６に書き込む。

タスクグラフ情報３１５は、タスク間の関係やタスクの入出力データなどタスク実行に必要な情報を記述するグラフ情報である。タスクグラフ情報３１５については、後に、図６のタスクグラフ情報のデータ構造の例を示して、詳細に説明する。

実行パターンリスト３１４は、実行パターン生成部２１２により生成されたタスクの実行スケジュールの実行パターンのリストである。実行パターンリスト３１４については、後に、図７のデータ構造の例を示して、詳細に説明する。

負荷情報３１６は、専従処理プログラムによる各ＣＰＵコアの推定負荷や各ＣＰＵコアへのタスクの割当て状況の情報である。負荷情報３１６については、後に、図９のデータ構造の例を示して、詳細に説明する。
（V）データ構造
次に、図６ないし図９を用いて本発明の一実施形態に係るタスク制御方法で用いるデータ構造について説明する。
図６は、タスクグラフ情報３１５のデータ構造の一例を示す図である。
図７は、実行パターンリスト３１４のデータ構造の一例を示す図である。
図８は、タスク実行情報３Ｃ１のデータ構造の一例を示す図である。
図９は、負荷情報３１６のデータ構造の一例を示す図である。

タスクグラフ情報３１５は、図６に示されるように、タスクＩＤ、処理時間、先行タスクＩＤ、通信時間、関数ＩＤ、入力データＩＤ、出力データＩＤの各フィールドを保持する。

タスクＩＤは、タスクグラフ情報において、タスクを一意に識別できるＩＤを格納するフィールドである。処理時間は、ＣＰＵに専従処理プログラムに起因する負荷がかからない場合において、タスクの実行に必要な時間を格納するフィールドである。先行タスクＩＤは、当該タスクの開始時に実行完了していなければならないタスクのＩＤを格納するフィールドである。通信時間は、先行タスクが実行完了してからタスクを開始するまでに必要な時間を格納するフィールドである。関数ＩＤは、タスクを実行する際に呼び出す関数のＩＤを格納するフィールドである。入力データＩＤと出力データＩＤは、タスク間の入出力関係を格納するフィールドである。例えば、図６に示される例では、タスクＩＤ（Ｔ１）は、出力データＩＤ（ｂ、ｃ）を保持し、タスクＩＤ（Ｔ２）は、入力データＩＤ（ｂ）を保持している。これは、タスクＴ１の出力ｂをタスクＴ２が入力として使用することを意味している。

なお、このタスクグラフ情報３１５は、並列処理プログラム３１１により並列処理実行部２１１に受け渡される。

次に、実行パターンリスト３１４は、生成された複数の実行パターンを保持するリストである。各実行パターンは、図７に示されるように、実行パターンＩＤ、パターンタスクＩＤ、処理時間、先行パターンタスクＩＤ、通信時間、関数ＩＤ、入力データＩＤ、出力データＩＤ、ＣＰＵＩＤの各フィールドを保持する。

実行パターンＩＤは、実行パターンを一意に識別できるＩＤを格納するフィールドである。パターンタスクＩＤは、実行パターンリストにおいて、パターンタスクを一意に識別できるＩＤを格納するフィールドである。ここで、パターンタスクとは、実行するＣＰＵが決定されているタスクであり、タスクを複製した各パターンタスクは異なるパターンタスクとして認識される。本実施形態においては、パターンタスクＩＤは、タスクＩＤと実行パターンＩＤとの組合せによって示すことにする。具体的には、パターンタスクＩＤ（Ｐ６ｅｎｔｒｙ）は、パターンＩＤがＰ６のパターンにおけるタスクＩＤが、ｅｎｔｒｙのタスクによるパターンタスクを示し、同様に、パターンタスクＩＤ（Ｐ６Ｔ１）は、パターンＩＤがＰ６のパターンにおけるタスクＩＤがＴ１のタスクのパターンタスクを示している。また、パターンタスクＩＤ（Ｐ６Ｔ１−２）は、パターンＩＤがＰ６のパターンにおけるタスクＩＤがＴ１のタスクの複製タスクを示している。図７の例では、ＣＰＵ２で実行されているパターンタスクＩＤ（Ｐ６Ｔ１）のパターンタスクの複製タスクとして、パターンタスクＩＤ（Ｐ６Ｔ１−２）のパターンタスクが生成され、それがＣＰＵ１で実行されることを示している。

処理時間は、パターンタスクの実行に必要な時間を格納するフィールドである。先行パターンタスクＩＤは、当該パターンタスクを開始時に実行完了していなければならないパターンタスクのＩＤを格納するフィールドである。通信時間は、先行パターンタスクが実行完了してからパターンタスクを開始するまでに必要な時間を格納するフィールドである。ただし、後述するＣＰＵＩＤが当該パターンタスクと、先行パターンタスクとで同一の場合、通信時間は０とする。ＣＰＵＩＤは、当該パターンタスクを実行するＣＰＵコアのＩＤを格納するフィールドである。

実行パターンリスト３１４は、タスク複製の有無を含む複数の実行パターンを保持する。実行パターンを選択することにより、各ＣＰＵコアに割り振る処理時間や、タスク複製の有無を選択することができる。

次に、タスク実行情報３Ｃ１は、図８に示されるように、パターンタスクＩＤ、関数ＩＤ、入力データＩＤ、出力データＩＤ、実行状態の各フィールドからなる情報である。

パターンタスクＩＤ、関数ＩＤ、入力データＩＤ、出力データＩＤの各フィールドは、タスクスケジューリング部２１３によって選択された実行パターンと同一の情報を保持する。実行状態は、タスク実行部２１４、２２２によって実行されるパターンタスクの状態を格納するフィールドである。パターンタスクの状態として、「未実行」、「実行中」、「実行完了」の三つの状態がある。

次に、負荷情報３１６は、図９に示されるように、ＣＰＵＩＤ、推定負荷、実行中パターンタスクＩＤ、実行待ちパターンタスクＩＤの各フィールドからなる情報である。

ＣＰＵＩＤは、対象となるマルチコアプロセッサシステムにおいて、並列処理の負荷分散対象となるＣＰＵコアを一意に識別できるＩＤを格納するフィールドである。推定負荷は、負荷推定部２１６、２２３によって推定された各ＣＰＵコアの推定負荷を格納するフィールドである。実行中パターンタスクＩＤは、タスク実行部において実行中のパターンタスクＩＤを格納するフィールドである。実行待ちパターンタスクＩＤは、当該ＣＰＵコアにおいてつぎに実行予定のパターンタスクＩＤを格納するフィールドである。

負荷推定部２１６、２２３によって推定された各ＣＰＵコアの推定負荷は、専従処理プログラムによる負荷を示しており、１００％から引いた残りの負荷（ＣＰＵ１の場合は、５０％、ＣＰＵ２の場合は、３０％）が、並列処理プログラムによって使用可能なＣＰＵコアのパワーとなる。
（VI）タスク制御方法の処理
次に、既に述べた図５と、図１０ないし図１５を用いて本発明の一実施形態に係るマルチコアプロセッサシステムのタスク制御方法の処理について説明する。

先ず、図５を用いてマルチコアプロセッサシステムのタスク制御方法の処理の概要について説明する。

初めに、並列処理プログラム３１１から、図６に示したタスクグラフ情報３１５が渡されて、並列処理実行部２１１の実行パターン生成部２１２に並列処理実行が依頼される。

実行パターン生成部２１２は、図７に示した実行パターンリスト３１４を生成し、タスクスケジューリング部２１３に並列処理開始を依頼する。

タスクスケジューリング部２１３は、実行パターンリスト３１４と図９に示した負荷情報３１６を参照し、図８に示したタスク実行情報３Ｃ１を生成する。また、タスク実行部２１４、２２２においてタスクが実行されていない場合、タスク実行情報３Ｃ１を参照し、タスク実行部２１４、２２２にタスクの実行開始を通知する。

タスク実行部２１４、２２２は、タスク実行情報３Ｃ１を参照し、パターンタスクＩＤによって特定されるタスクを実行する。そして、タスク実行完了後、タスク実行結果統合部２１５にタスク実行完了を通知する。

タスク実行結果統合部２１５は、タスク実行情報３Ｃ１を参照し、タスクスケジューリング部２１３にタスク実行完了を通知する。また、全てのタスクが実行完了している場合、並列処理結果を出力する。

負荷推定部２１６、２２３は、専従処理プログラム３１７、３２３から推定負荷情報を受け取り、各負荷推定部が実行されているＣＰＵの推定負荷を計算する。負荷推定部２１６と負荷推定部２２３の間で、各ＣＰＵの推定負荷を相互に伝達し、負荷情報３１６を生成する。

なお、専従処理プログラム３１７、３２３が、推定負荷情報を出力するために、専従処理プログラム３１７、３２３に特定のブレークポイントに達すると、処理量を出力するなどのコーディングが必要となる。

以上の処理により、並列処理を実行する。

次に、図１０ないし図１５を用いて本実施形態の各モジュールの処理について説明する。

先ず、図１０を用いて実行パターン生成部２１２の処理について説明する。
図１０は、実行パターン生成部２１２の処理を示すフローチャートである。

先ず、実行パターン生成部２１２は、並列処理プログラム３１１からの、並列処理実行依頼を待ち受ける（ステップ１２１１）。

次に、タスクグラフ情報３１５の基づき、実行パターンを生成し、実行パターンリスト３１４に追加する（ステップ１２１２）。

実行パターンは、タスクグラフ情報３１５を参照し、各タスクにタスクを実行するＣＰＵコアのＩＤを追加して生成する。ただし、実行パターンの始点と終点となるタスクｅｎｔｒｙとタスクｅｘｉｔのＣＰＵＩＤは、並列処理プログラム３１１から、並列処理実行依頼を受けたＣＰＵコアのＩＤとする。

図７に示された実行パターンリスト３１４の処理時間、通信時間、関数ＩＤ、入力データＩＤ、出力データＩＤは、各パターンタスクの基となったタスクのものとする。

ステップ１２１２における、実行パターンの生成手順は、本実施形態では、例えば、以下の手順によりおこなう。
（１）すべてのタスクのＣＰＵＩＤをＣＰＵ１とした実行パターンを生成し、実行パターンリスト３１４に追加する。
（２）実行パターンリスト３１４から、実行パターンを一つ選択する。
（３）選択した実行パターンにおいて、タスクｅｘｉｔを選択するか、または、ＣＰＵＩＤがＣＰＵ２であるタスクを一つ選択する。
（４）選択したタスクの先行タスクから、ＣＰＵＩＤがＣＰＵ１である先行タスクを選択する。
（５）選択した先行タスクのＣＰＵＩＤをＣＰＵ２に変更した実行パターンを生成し、実行パターンリスト３１４に追加する。
（６）新しい実行パターンが生成できなくなるまで、上記の（２）〜（５）の手順を繰り返す。

具体的には、すべてのタスクのＣＰＵＩＤをＣＰＵ１とした図４の実行パターン１が生成され、実行パターンリストに追加される。次に、実行パターン１のタスクｅｘｉｔから先行タスクＴ２を選択し、Ｔ２のＣＰＵＩＤをＣＰＵ２に変更した実行パターン２が生成され、実行パターンリストに追加される。

次に、実行パターンリスト３１４に基づき、タスクを複製する実行パターンを生成し、実行パターンリスト３１４に追加する（ステップ１２１３）。なお、このステップ１２２３については、後に、図１５を用いてタスクを複製する実行パターンの生成手順を示し、詳細に説明をおこなうこととする。

次に、実行パターンリスト３１４における、各パターンタスクの通信時間を計算する（ステップ１２１４）。このパターンタスクの通信時間を計算する場合に、実行パターンリスト３１４を参照し、パターンタスクと先行パターンタスクが同一のＣＰＵＩＤを保持している場合、パターンタスクの通信時間を０に変更する。また、パターンタスクと先行パターンタスクが異なるＣＰＵＩＤを保持している場合、パターンタスクの通信時間を変更しない。

次に、むだな実行パターンを、実行パターンリスト３１４から削除する（ステップ１２１５）。ここで、「むだな実行パターン」とは、いずれの負荷状況においても選択されることのない実行パターンを指す。

例えば、後述するステップ１３１２において詳細に解説するが、本実施形態では実行パターンの推定所要時間と呼ぶものを計算し、推定所要時間が小さい実行パターンを選択する。二つの実行パターンを比較して、いずれの負荷状況においても常に、一方の実行パターンの推定所要時間が小さい場合、もう一方の実行パターンは選択されることはない。例えば、ＣＰＵ１とＣＰＵ２があり、両者の負荷が０から１００％変わるとき、いずれの組み合わせでも、ある実行パターンが他の実行パターンよりも、推定所要時間が大きくなるときには、そのような実行パターンは、「むだな実行パターン」であるとして、削除されることになる。

このように選択されることが無いことが明らかな実行パターンを、実行パターンリスト３１４から削除する。

次に、並列処理開始をタスクスケジューリング部２１３に通知し（ステップ１２１６）、ステップ１２１１に戻る。

なお、実行パターン生成部２１２による実行パターンの生成は、過去に並列処理を依頼されたタスクグラフと同一のタスクグラフに対して、再度生成を依頼された場合、省略してもよいものとする。省略する場合、実行パターンを生成する代わりに、保存しておいた実行パターンリストを採用する。

次に、図１１を用いてタスクスケジューリング部２１３の処理について説明する。
図１１は、タスクスケジューリング部２１３の処理を示すフローチャートである。

先ず、タスクスケジューリング部２１３は、実行パターン生成部２１２からの並列処理開始通知を待ち受ける（ステップ１３１１）。

次に、負荷情報３１６と実行パターンリスト３１４に基づき、各実行パターンの推定所要時間を計算する（ステップ１３１２）。本実施形態では、負荷情報３１６の推定負荷と実行パターンリスト３１４のＣＰＵＩＤ、処理時間、通信時間を用いて、推定所要時間を計算する。

例えば、ＣＰＵ１の処理時間合計をＣＰＵ１の推定負荷に応じて増加させたＣＰＵ１推定所要時間と、ＣＰＵ２の処理時間合計をＣＰＵ２の推定負荷に応じて増加させ、それに通信時間を加算したＣＰＵ２推定所要時間とを比較して、より大きいものを実行パターンの推定所要時間とする。

具体的には、図７の実行パターンＩＤ（Ｐ６）と、図９の負荷情報を例にとった場合、ＣＰＵ１の処理時間合計は、パターンタスクＩＤ（Ｐ６Ｔ１−２）の１０、パターンタスクＩＤ（Ｐ６Ｔ３）の１０を合計して２０となる。また、ＣＰＵ１の推定負荷は５０％なので、並列処理に使われる負荷は、（１００−５０）％＝５０％となる。したがって、ＣＰＵ１推定所要時間は、（１０＋１０）／（１−０．５）により計算され、２０を２倍した４０となる。なお、パターンタスクＩＤ（Ｐ６ｅｎｔｒｙ）からパターンタスクＩＤ（Ｐ６Ｔ１−２）、パターンタスクＩＤ（Ｐ６Ｔ１−２）からパターンタスクＩＤ（Ｐ６Ｔ３）、パターンタスクＩＤ（Ｐ６Ｔ３）からパターンタスクＩＤ（Ｐ６ｅｘｉｔ）の通信時間は、ＣＰＵ１のみで処理するタスクのため、すべて、０になる。

同様にＣＰＵ２の処理時間合計は、パターンタスクＩＤ（Ｐ６Ｔ１）の１０、パターンタスクＩＤ（Ｐ６Ｔ２）の１０を合計して２０となる。また、ＣＰＵ２の推定負荷は７０％なので、並列処理に使われる負荷は、（１００−７０）％＝３０％となり、負荷がない状態と比較して、１／０．３倍の処理時間が必要となる。一方、通信時間は、パターンタスクＩＤ（Ｐ６ｅｎｔｒｙ）からパターンタスクＩＤ（Ｐ６Ｔ１）へは、１０、パターンタスクＩＤ（Ｐ６Ｔ１）からパターンタスクＩＤ（Ｐ６Ｔ２）は、０、パターンタスクＩＤ（Ｐ６Ｔ２）からパターンタスクＩＤ（Ｐ６ｅｘｉｔ）へは、１０となり、これらのすべてを合計して２０となる。

ＣＰＵ２の負荷を考慮した処理時間は、（１０＋１０）／（１−０．７）により、計算され、２０を３．３３倍した６６．６となり、ＣＰＵ２推定所要時間は、これに通信時間の合計２０を加算した８６．６となる。

以上より、実行パターンＩＤ（Ｐ６）の推定所要時間は、ＣＰＵ１推定所要時間の４０とＣＰＵ２推定所要時間の８６．６を比較して、より大きい値の８６．６となる。

次に、ステップ１３１２において計算した推定所要時間が最小となる実行パターンを選択する（ステップ１３１３）。

推定所要時間は、ＣＰＵコアの負荷に応じた並列処理に必要な推定時間なので、推定所要時間が最小となる実行パターンを選択することにより、ＣＰＵコアの負荷に応じて処理効率の良い実行パターンを選択することができる。

次に、ステップ１３１３において選択された実行パターンに基づき、並列処理を開始する（ステップ１３１４）。

このときに、パターンタスクが、負荷情報３１６の実行待ちパターンタスクに追加される。パターンタスクを追加する負荷情報におけるＣＰＵＩＤは、実行パターンのＣＰＵＩＤを同一とする。例えば、図７の実行パターンＩＤ（Ｐ６）が実行パターンに決定された場合、パターンタスクＰ６Ｔ１、Ｐ６Ｔ２は、ＣＰＵ２の実行待ちパターンタスクに、パターンタスクＰ６Ｔ１−２、Ｐ６Ｔ３はＣＰＵ１の実行待ちパターンタスクに追加される。

次に、負荷情報３１６を参照し、実行待ちパターンタスクがあるＣＰＵコアが存在する場合には、ステップ１３１６に進み、存在しない場合には、ステップ１３１１に進む（ステップ１３１５）。

実行待ちパターンタスクがあるＣＰＵコアが存在するときに、負荷情報３１６を参照し、実行可能な実行待ちパターンタスクがあるＣＰＵコアが存在する場合には、ステップ１３１７に進み、存在しない場合には、ステップ１３１ｂに進む（ステップ１３１６）。実行可能な実行待ちパターンタスクとは、実行待ちパターンタスクの中で、すべての先行パターンタスクが実行完了となっているパターンタスクである。

実行可能な実行待ちパターンタスクがあるＣＰＵコアが存在するときに、負荷情報３１６を参照し、当該ＣＰＵコアの実行中パターンタスクが存在する場合には、ステップ１３１ｂに進み、存在しない場合には、ステップ１３１８に進む（ステップ１３１７）。

該当するＣＰＵコアの実行中パターンタスクが存在するときに、負荷情報３１６を参照し、当該ＣＰＵコアの推定負荷が閾値以下の場合には、ステップ１３１９に進み、それ以外の場合には、ステップ１３１ｂに進む（ステップ１３１８）。

閾値はシステム設計者が任意に設定する値で、本実施形態においては、例えば、８０％とする。この閾値を設定するのは、並列処理プログラムの方にＣＰＵのパワーが独占されるのを避けて、ある程度、専従処理プログラムの実行のためのＣＰＵパワーを確保するためである。

ＣＰＵコアの推定負荷が閾値以下のときに、負荷情報３１６において、当該ＣＰＵコアの実行可能な実行待ちパターンタスクを一つ、実行中パターンタスクに変更して、設定する（ステップ１３１９）。

次に、ステップ１３１９において変更されたパターンタスクの実行開始を、当該ＣＰＵコアのタスク実行部に通知する（ステップ１３１ａ）。

次に、タスク実行結果統合部からのタスク完了通知、または、負荷推定部からの負荷情報変化通知を待ち受け（ステップ１３１ｂ）、ステップ１３１５に戻る。

なお、本実施形態では、ＣＰＵの推定負荷について閾値を設ける例を示したが、ステップ１３１３で選択された実行パターンの各パターンタスクの通信時間の合計に、閾値を設けて、その閾値を超える実行パターンは、採用しないようにしてもよい。これは、メモリ容量が少ない組込み用途のマルチコアプロセッサシステムでは、通信のために割り当てられるメモリ容量も少なくなるために、有効な方法となりえる。

次に、図１２を用いてタスク実行部２１４、２２２の処理について説明する。
図１２は、タスク実行部２１４、２２２の処理を示すフローチャートである。

先ず、タスク実行部２１４、２２２は、タスクスケジューリング部２１３からの、タスク実行開始通知を待ち受ける（ステップ１４１１）。

次に、タスク実行情報３Ｃ１における、タスク実行開始通知を受けたパターンタスクの実行状態を、実行中に変更する（ステップ１４１２）。

次に、パターンタスクを実行する（ステップ１４１３）。

タスク実行の際、呼び出す関数アドレス、関数に引数として渡す入力データアドレス、関数の処理結果を保持する出力データアドレスは、タスク実行情報３Ｃ１を参照し、関数ＩＤ、入力データＩＤ、出力データＩＤから特定する。

次に、タスク実行情報３Ｃ１における、タスク実行開始通知を受けたパターンタスクの実行状態を、実行完了に変更する（ステップ１４１４）。

次に、タスク完了を、タスク実行結果統合部２１５に通知し（ステップ１４１５）、ステップ１４１１に戻る。

次に、図１３を用いてタスク実行結果統合部２１５の処理について説明する。
図１３は、タスク実行結果統合部２１５の処理を示すフローチャートである。

先ず、タスク実行結果統合部２１５は、タスク実行部２１４、２２２からのタスク完了通知を待ち受ける（ステップ１５１１）。

次に、タスク実行情報３Ｃ１を参照し、全パターンタスクの実行状態が、実行完了の場合には、ステップ１５１３に進み、それ以外の場合には、ステップ１５１４に進む（ステップ１５１２）。

全パターンタスクの実行状態が、実行完了のときに、タスク実行情報３Ｃ１を参照し、出力データＩＤから関数の処理結果を保持する出力データアドレスを特定する（ステップ１５１３）。

そして、特定した出力データアドレスから、出力データを読み込む。すべてのタスク実行結果を統合して、並列処理結果を並列処理プログラム実行部に出力する。

次に、タスク完了を、タスクスケジューリング部２１３に通知し（ステップ１５１４）、ステップ１５１１に戻る。

次に、図１４を用いて負荷推定部２１６、２２３の処理について説明する。
図１４は、負荷推定部２１６、２２３の処理を示すフローチャートである。

先ず、負荷推定部２１６、２２３は、専従処理プログラム実行部３１７、３２３、負荷推定部２１６、２２３からの、負荷変化通知を待ち受ける（ステップ１６１１）。ここで、負荷変化通知とは、専従処理プログラムによるＣＰＵコアの推定負荷が変化したことや、各負荷推定部を実行しているＣＰＵコアの推定負荷が変化したことを知らせる通知を意味する。具体的には、ユーザの入力により、推定負荷が０％の入力待ち状態から、推定負荷が１００％の処理実行状態に変化したことや、処理が終了し、推定負荷が０％の入力待ち状態に変化したことなどである。

次に、専従処理プログラムからの負荷変化通知の場合には、ステップ１６１３に進み、それ以外の場合には、ステップ１６１５に進む（ステップ１６１２）。

専従処理プログラムからの負荷変化通知を受けたとには、その負荷変化通知に基づき、自ＣＰＵコアの推定負荷を計算する（ステップ１６１３）。

次に、計算した自ＣＰＵコアの推定負荷を、各ＣＰＵコアの負荷推定部に通知する（ステップ１６１４）。

次に、自ＣＰＵコアが、タスクスケジューリング部２１３が動作しているＣＰＵコアである場合には、ステップ１６１６に進み、それ以外の場合、ステップ１６１１に進む（ステップ１６１５）。

次に、ステップ１６１３において計算した自ＣＰＵコアの推定負荷、ステップ１６１４において通知された他ＣＰＵコアの推定負荷を負荷情報３１６に設定して、更新する（ステップ１６１６）。

次に、負荷情報変化を、タスクスケジューリング部２１３に通知し（ステップ１６１７）、ステップ１６１１に戻る。

このようにして、負荷推定部２１６、２２３により推定したＣＰＵコアの負荷を用いることにより、ＣＰＵコアの負荷に応じた実行パターンの選択が可能となる。

次に、図１５を用いて実行パターン生成部において、タスクを複製する実行パターンの生成手順のステップ１２１３の処理について説明する。
図１５は、実行パターン生成部において、タスクを複製する実行パターンの生成手順のステップ１２１３の詳細を示すフローチャートである。

この図１５のフローチャートは、図１０に示したタスクを複製する実行パターンの生成手順のステップ１２１３の詳細を説明するものである。

先ず、実行パターンリスト３１４の全ての実行パターンを一度選択した場合には、タスクを複製する実行パターンの生成手順を終了し。選択したことのない実行パターンがある場合には、ステップ１７１２に進む（ステップ１７１１）。

次に、実行パターンリスト３１４から、選択していない実行パターンを一つ選択する（ステップ１７１２）。

次に、ステップ１７１２において選択した実行パターンの全てのパターンタスクを一度選択したことがある場合には、ステップ１７１１に進み、選択したことがないパターンタスクがある場合、ステップ１７１４に進む（ステップ１７１３）。ただし、タスクｅｎｔｒｙとタスクｅｘｉｔは対象外とする。

ステップ１７１２において選択した実行パターンの全てのパターンタスクを一度選択したことがあるときに、選択した実行パターンから、選択したことのないパターンタスクを選択する（ステップ１７１４）。ただし、タスクｅｎｔｒｙとタスクｅｘｉｔは選択しない。

次に、ステップ１７１４において選択したパターンタスクの全ての先行パターンタスクを一度選択したことがある場合、ステップ１７１３に進み、選択したことがない先行パターンタスクがある場合、ステップ１７１６に進む（ステップ１７１５）。

ステップ１７１４において選択したことがない先行パターンタスクがあるときに、選択したパターンタスクから、選択したことのない先行パターンタスクを選択する（ステップ１７１６）。

次に、ステップ１７１４において選択したパターンタスクのＣＰＵＩＤと、ステップ１７１６において選択した先行パターンタスクのＣＰＵＩＤが同じである場合、ステップ１７１３に進み、異なる場合、ステップ１７１８に進む（ステップ１７１７）。

ステップ１７１４において選択したパターンタスクのＣＰＵＩＤと、ステップ１７１６において選択した先行パターンタスクのＣＰＵＩＤが異なるときに、ステップ１７１６において選択した先行パターンタスクを複製した実行パターンを生成し、実行パターンリスト３１４に追加する（ステップ１７１８）。このとき、複製したパターンタスクのＣＰＵＩＤは、ステップ１７１４において選択したパターンタスクのＣＰＵＩＤを有する。また、複製したパターンタスクを先行パターンタスクとして持つパターンタスクのうち、複製したパターンタスクのＣＰＵＩＤと同一のＣＰＵＩＤを持つパターンタスクは、先行パターンタスクを複製したパターンタスクに変更する。

例えば、図４において、実行パターンとして実行パターン２を、パターンタスクとしてタスクＴ２を、複製元パターンタスクとしてタスクＴ１を選択した場合、タスクＴ１を複製して、実行パターン６が生成される。

本発明の一実施形態に係るマルチコアプロセッサシステムのハードウェア構成図である。 本発明の一実施形態に係るマルチコアプロセッサシステム上で実行される並列プログラムの実行環境のシステム階層を示す図である。 本発明の一実施形態の並列処理のタスクグラフを例示した図である。 図３に示したタスクグラフの並列処理の実行パターンを示した図である。 本発明の一実施形態に係るマルチコアプロセッサシステムのモジュール構成を示す図である。 タスクグラフ情報３１５のデータ構造の一例を示す図である。 実行パターンリスト３１４のデータ構造の一例を示す図である。 タスク実行情報３Ｃ１のデータ構造の一例を示す図である。 負荷情報３１６のデータ構造の一例を示す図である。 実行パターン生成部２１２の処理を示すフローチャートである。 タスクスケジューリング部２１３の処理を示すフローチャートである。 タスク実行部２１４、２２２の処理を示すフローチャートである。 タスク実行結果統合部２１５の処理を示すフローチャートである。 負荷推定部２１６、２２３の処理を示すフローチャートである。 実行パターン生成部において、タスクを複製する実行パターンの生成手順のステップ１２１３の詳細を示すフローチャートである。

符号の説明

１０１…マルチコアプロセッサ、１０２…共有メモリ、１０３…Ｉ／Ｏ、１０４…バス、１Ｃ１…ＣＰＵコア１、１Ｃ２…ＣＰＵコア２、１ＣＮ…ＣＰＵコアＮ、１Ｍ１…ＣＰＵ１使用領域、１Ｍ２…ＣＰＵ２使用領域、１ＭＮ…ＣＰＵＮ使用領域、１ＭＣ…共有領域、３１１…並列処理プログラム、２１１…並列処理実行部、３１７…専従処理プログラム実行部、３１２…逐次実行部、３１３…並列化対象部、２１２…実行パターン生成部、２１３…タスクスケジューリング部、２１４…タスク実行部、２１５…タスク実行結果統合部、２１６・演ラ推定部、３１５…タスクグラフ情報、３１４…実行パターンリスト、３１６…負荷情報、３２１…並列処理プログラム、２２１…並列処理実行部、３２３…専従処理プログラム、３２２…並列化対象部、２２２…タスク実行部、２２３…負荷推定部、３Ｃ１…タスク実行情報。

Claims (8)

1. 複数のＣＰＵコアを搭載し、各ＣＰＵコアにより分散して、処理を実行するマルチコアプロセッサシステムにおいて、
   各ＣＰＵコアによって実行されるタスクの実行スケジュールの実行パターンを複数生成する実行パターン生成部と、
   各ＣＰＵコアの負荷を推定する負荷推定部と、
   前記負荷推定部により推定された推定負荷より計算された各ＣＰＵコアにおける処理の実行時間と、ＣＰＵコア間の通信時間とに基づいて、前記実行パターンを選択するタスクスケジューリング部と、
   前記タスクスケジューリング部の指示に従い、前記実行パターンの各タスクを実行するタスク実行部とを有するマルチコアプロセッサシステム。
2. 前記実行パターン生成部は、同一のタスクを異なるＣＰＵコアに実行させるためのタスク複製をおこなった実行パターンを生成することを特徴とする請求項１記載のマルチコアプロセッサシステム。
3. 前記実行パターンのタスクを実行する際のあるＣＰＵコアの前記推定負荷が、一定の閾値より大きいときには、その実行パターンを選択しないようにすることを特徴とする請求項１記載のマルチコアプロセッサシステム。
4. 前記実行パターンのＣＰＵコア間の通信時間の合計が、一定の閾値より大きいときには、その実行パターンを選択しないようにすることを特徴とする請求項１記載のマルチコアプロセッサシステム。
5. 複数のＣＰＵコアを搭載し、各ＣＰＵコアにより分散して、処理を実行するマルチコアプロセッサシステムのタスク制御方法において、
   各ＣＰＵコアによって実行されるタスクの実行スケジュールの実行パターンを複数生成するステップと、
   各ＣＰＵコアの負荷を推定するステップと、
   前記負荷推定部により推定された推定負荷より計算された各ＣＰＵコアにおける処理の実行時間と、ＣＰＵコア間の通信時間とに基づいて、前記実行パターンを選択するステップと、
   前記タスクスケジューリング部の指示に従い、前記実行パターンの各タスクを実行するステップとを有するマルチコアプロセッサシステムのタスク制御方法。
6. 前記実行パターンを複数生成するステップにおいて、同一のタスクを異なるＣＰＵコアに実行させるためのタスク複製をおこなった実行パターンを生成することを特徴とする請求項５記載のマルチコアプロセッサシステムのタスク制御方法。
7. 前記実行パターンを選択するステップにおいて、前記実行パターンのタスクを実行する際のあるＣＰＵコアの前記推定負荷が、一定の閾値より大きいときには、その実行パターンを選択しないようにすることを特徴とする請求項５記載のマルチコアプロセッサシステムのタスク制御方法。
8. 前記実行パターンを選択するステップにおいて、前記実行パターンのＣＰＵコア間の通信時間の合計が、一定の閾値より大きいときには、その実行パターンを選択しないようにすることを特徴とする請求項５記載のマルチコアプロセッサシステムのタスク制御方法。

Images