(57)【要約】【課題】  マルチプロセッサのマルチタスク制御の最適化、高速化を一般化して行なう。【解決手段】  ハード構成として、システムＬＳＩ内部のデータキャッシュを持つプロセッサ群と、大容量の外部共有メモリとからなる。タスクの組み合わせ候補を複数生成して、多数のプロセッサで同一タスクを重複して投機的に実行する。プロセッサ間での通信をペナルティとして、最もペナルティを避けたプロセッサとタスクの組み合わせの結果を採用することで、最も効率の良い処理手順を使いつつ、データキャッシュ−共有メモリ間のシステム全体の整合性をとる。【選択図】  図１
2006039824.tif 000002
【特許請求の範囲】
【請求項１】
マルチプロセッサと、各プロセッサＰ１、Ｐ２、Ｐ３・・・・に対応して接続されたデータキャッシュメモリおよびインストラクションキャッシュメモリと、全てのプロセッサからアクセスできるように共有接続されたバスと、バスを通して外部に共有メモリが接続可能なメモリコントローラと、を少なくとも内部に有したシステムＬＳＩの構成とし、
上記プロセッサはデータキャッシュの遅延書き込みとリフィルのタイミングをユーザーが制御できる手段を持つプロセッサであり、マルチタスクの実行において、タスクＴ１、Ｔ２、Ｔ３・・・・の各プロセッサへの振り分け方法の候補を振り分け方法テーブルＤ１、Ｄ２、Ｄ３・・・・として複数種類用意する手段と、
上記テーブルを用いてプロセッサをタスクに割り当てる事で同一タスクを複数のプロセッサ上で重複して投機的に実行させる手段と、各振り分け方法ごとのタスク間の遷移の進行状況を検知する手段と、
前記検知手段に基づいて最も処理が進んだ振り分け方法の処理に用いたプロセッサの分散メモリの内容を前記共有メモリに書き戻す手段と、を持つことを特徴とするマルチプロセッサ搭載システムＬＳＩのマルチタスク制御方法。
【請求項２】
上記振り分け方法テーブルＤ１、Ｄ２、Ｄ３・・・・の各々において、プロセッサに割り当てられたタスクが同一の場合には振り分け方法テーブル間でプロセッサを共用する事を特徴とする請求項１に記載のマルチプロセッサ搭載システムＬＳＩのマルチタスク制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のＣＰＵすなわちマルチプロセッサを用い、かつ専用ハードウェア回路と共に１つのＬＳＩに組み込んで構成される、いわゆるシステムＬＳＩあるいはシステムオンチップ（ＳＯＣ）と呼ばれるＬＳＩの構成方法と、このＬＳＩ上で異なるプログラムを同時に独立に実行し、プログラム間で通信を行い制御するいわゆるマルチタスクを実行する方法に関する。
【背景技術】
【０００２】
近年、半導体製造プロセスの進歩と集積度の向上に伴い、専用ハードウェア回路と共にＣＰＵを１つのＬＳＩに組み込む事で構成される、いわゆるシステムＬＳＩあるいはシステムオンチップ（ＳＯＣ）と呼ばれるＬＳＩがさかんに利用されるようになってきている。さらに、半導体の集積度の向上により、相対的に複数のＣＰＵの搭載がＬＳＩにおけるＣＰＵの占有面積の点からは容易になってきており、性能を向上させるために数個のＣＰＵを搭載するマルチプロセッサによるＳＯＣが、次第に利用されるようになってきている。今後、さらなる半導体の集積度の向上により、ＬＳＩの価格への影響度は、外部に接続するピンの数による制約がより大きくなり、数十から数百といった非常に多数のＣＰＵの搭載が、ＬＳＩの面積的な観点からは極めて安価にＳＯＣ上で可能になる時代が到来する事が予想される。
【０００３】
また一方で、デジタル機器で利用されるソフトウェアは相対的に複雑になってきており、プログラムを同時に独立に実行し、プログラム間で通信を行い制御するいわゆるマルチタスクで利用できるオペレーティングシステム（ＯＳ）を利用することが多くなってきている。
【０００４】
さらに一方で、半導体の物理的性質の限界や消費電力や発熱の観点から、動作周波数をこれ以上、従来のペースで上げ続けるのは困難と見られており、その点からも、ＳＯＣに限らず、従来から処理の高速化のためにマルチプロセサによるアプリケーションソフトやマルチプロセッサ用マルチタスクのＯＳ開発と利用が行われており、大規模な並列数値計算に数千のプロセッサを用いたもの、あるいは２個から４個のプロセッサを用いたマルチプロセッサ用マルチタスクのＯＳなどが利用されている。
【特許文献１】特開平３−２１１６５６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の方法には以下の課題があった。
【０００６】
１）多数個のマルチプロセセッサによるアプリケーションソフトは特定の並列演算が実行可能な例、例えば画像処理や場の方程式を解く数値計算、等に有効であるが、容易に並列分割できない制御系の処理ではアルゴリズムの自動的な並列化が困難であり、例えばマルチタスクのアプリケーションにおける個々のタスクの依存関係は特定のアプリケーション毎に異なる。このような制御系の処理における並列アルゴリズムの生成に関しては、一般解がなく、自動化が難しい。
【０００７】
２）一つの領域のメモリをマルチプロセッサで同時にアクセスする共有メモリを利用する場合、プロセッサ数が多くなると共有メモリへのバスのトラフィックが増大し、アクセス速度が低下する。そのため、キャッシュ機構などのプロセサごとにアクセス可能なローカルな高速メモリへのコピーを用いて高速化を図る必要があるが、この場合は更に各プロセッサごとのキャッシュと共有メモリとの整合性をとることが難しくなる。各プロセッサに近接して分散メモリだけを配置する方法も考えられるが、この場合は、分散メモリ間でのデータの受け渡しが困難であり、一般の制御アルゴリズムにおいて分散メモリの内容の整合性を取ることが困難である。
【０００８】
３）複数のプロセッサに複数のタスクを割り当てた場合のシステム全体のデータ処理の効率を向上させる為の適切な方法の選択が難しい。
【０００９】
例として、タスクＴａ、Ｔｂ、ＴｃをプロセッサＰｘ、Ｐｙで動作させる場合に、ある一つのタスクＴａに関して、一つのプロセッサに割り当てて、Ｐｘ：（Ｔａ）、Ｐｙ：（Ｔｂ、Ｔｃ）とする方法があり、また複数のタスクＴａ、Ｔｂを一つのプロセッサに割り当てて、Ｐｘ：（Ｔａ、Ｔｂ）、Ｐｙ：（Ｔｃ）とする方法がある。ここで、タスクＴａに関して、前者の方法はプロセッサ内でタスクの遷移が無くプロセッサ内のレジスタデータの入れ替え（コンテキストスイッチ）が不要であるという観点においては、タスクＴａは明らかに高速に動作する。ところが一方で、タスクＴaとＴbの間で互いにメッセージを通信して動作が行なわれる場合、異なるプロセッサ間で同期をとって通信しなければならず、そのためのオーバーヘッドが大きい場合に前者の方法は速度が低下する要因となる。このプロセッサ間の同期のオーバーヘッドは、マルチプロセッサやメモリなどのハードウェアのシステム構成や、マルチタスクのソフトウェアプログラムの制御構成に依存して変化するので、結果として、複雑なタスク数とプロセッサ数の構成になった場合に、前者と後者のどちらの方法がより効率的にデータを処理できるかは、ケースバイケースであると言える。このように、マルチプロセッサへのタスク割り当ての方法の選択が困難である。
【００１０】
こうした上記の課題を解決して、安価に膨大なプロセッサを利用できる環境で、共有メモリへのデータ転送速度がボトルネックとならずに、多数の分散メモリのデータの整合性をとりながら、マルチタスクのソフトウェアを高速に実行するアーキテクチャとアルゴリズムが望まれていた。
【課題を解決するための手段】
【００１１】
本発明は、上述の課題を解決するために、以下の構成であることを特徴とする。
【００１２】
マルチプロセッサと、各プロセッサＰ１、Ｐ２、Ｐ３・・・・に対応して接続されたデータキャッシュメモリおよびインストラクションキャッシュメモリと、全てのプロセッサからアクセスできるように共有接続されたバスと、バスを通して外部に共有メモリが接続可能なメモリコントローラと、を少なくとも内部に有したシステムＬＳＩの構成とし、上記プロセッサはデータキャッシュの遅延書き込みとリフィルのタイミングをユーザーが制御できる手段を持つプロセッサであり、マルチタスクの実行において、タスクＴ１、Ｔ２、Ｔ３・・・・の各プロセッサへの振り分け方法の候補を振り分け方法テーブルＤ１、Ｄ２、Ｄ３・・・・として複数種類用意する手段と、上記テーブルを用いてプロセッサをタスクに割り当てる事で同一タスクを複数のプロセッサ上で重複して実行させる手段と、各振り分け方法ごとのタスク間の遷移の進行状況を検知する手段と、前記検知手段に基づいて最も処理が進んだ振り分け方法の処理に用いたプロセッサの分散メモリの内容を前記共有メモリに書き戻す手段と、を持つことを特徴とするマルチプロセッサ搭載システムＬＳＩのマルチタスク制御方法。
【発明の効果】
【００１３】
以上説明したように、本発明によれば、マルチプロセッサにマルチタスクを割り当てる際に、複数の振り分け方法の候補を上げて、それをプロセッサに適用し、最も効率の良いタスク割り当ての結果を残す事で、以下の効果が得られる。
【００１４】
１）予測困難なマルチプロセッサへのマルチタスクの割り当てスケジューリングが最適化される。
【００１５】
２）履歴（ログ）をとって以降の最適割り当てを予測するのではないので、再現性が乏しく統計的予測が困難な状態遷移に関しても、その瞬間の動的な最適割り当てがなされる。
【００１６】
３）プロセッサの個数が増えてもタスクの個数が増えても同一アルゴリズムでスケーラブルに拡張できる。
【００１７】
特にプロセッサ数が膨大でもパッケージのピン数が少なくて済むようなシステムＬＳＩを利用する場合に有効であり、たとえばタスク数よりもプロセッサの数が十分多いという程プロセッサを多数配置したとしても、プロセッサ数のみではコストに大きく影響しない、という程の高い集積度の構成を利用していく場合や、小さなプロセッサコアを利用する場合には特に有効である。
【発明を実施するための最良の形態】
【００１８】
＜実施形態１＞
以下、本発明の好適な実施例の一例を挙げてその原理を説明する。以下は、本発明の原理に基づく実施形態を例示しまた理解を助ける為に説明を行ったものであり、本発明の適用範囲が必ずしもこの実施例の詳細によって限定されるものではない。
【００１９】
図１は本発明の基本概念を示す図である。
【００２０】
図１（ａ）はシステムＬＳＩのハードウェア構成で、図１（ｂ）はマルチプロセッサ上でどのようにマルチタスクを割り当てるかをしめした制御方法を示している。
【００２１】
図１（ａ）に示す通り、システムＬＳＩ内で、バス１００上に高速な分散メモリＭ１、Ｍ２、Ｍ３・・・・とプロセッサＰ１、Ｐ２、Ｐ３・・・・がそれぞれ対応して接続されている。また、バス１００にメモリコントローラ（図示せず）を介して外部に共有メモリ２００が接続されている。５００は各プロセッサＰｎからの信号を受け取り制御する調停プロセッサ５００である。４００は共有メモリと高速な分散メモリとの間でデータ転送を行なうことができるＤＭＡコントローラ４００である。３００はシステムＬＳＩで構成される部分を示す。一方、プロセッサ上で実行されるソフトウェアプログラムであるタスクはＴ１、Ｔ２、Ｔ３・・・・が用意されている。図１（ｂ）にその一部を抜粋して示す。
【００２２】
各プロセッサにはデータキャッシュＤ＄、インストラクションキャッシュＩ＄が装着されている。データキャッシュＤ＄は遅延書き込み（ライトバック）の機能を有し、さらに本発明では、ユーザーが利用できる命令セットとして、データキャッシュに関してライトバックの停止状態を保持し、またストア命令のキャッシュミスに関してラインが全て有効な場合にキャッシュのライトバックとリフィルを停止してウェイト状態のままプロセッサ外部に通知信号を発行する機能を有している。
【００２３】
ここでは、プロセッサが、７個以上であり、タスクがＴ１，Ｔ２，Ｔ３の３個である場合の例について説明する。まず、タスクの振り分けは以下の可能性が考えられる。これを振り分け方法テーブルＤ１からＤ５までとして以下に示す。ここで、（タスク・・・・）がプロセッサ１個当たりに割り当てられるタスクを示す。例えば（Ｔ１、Ｔ２）は一つのプロセッサにＴ１，Ｔ２のタスクを割り当てることを示す。また、｛（タスク・・・・）・・・・｝は上記割り当てによる全てのタスクのプロセッサへの割り当ての振り分け方法を示す。
【００２４】
例えば、Ｄ２＝｛（Ｔ１、Ｔ２）、（Ｔ３）｝は１個のプロセッサにＴ１，Ｔ２のタスクを割り当て、もう一つのプロセッサにＴ３のタスクを割り当てることで全てのタスクを実行するという振り分け方法Ｄ２を示している。
【００２５】
Ｄ１＝｛（Ｔ１）、（Ｔ２）、（Ｔ３）｝
Ｄ２＝｛（Ｔ１、Ｔ２）、（Ｔ３）｝
Ｄ３＝｛（Ｔ２、Ｔ３）、（Ｔ１）｝
Ｄ４＝｛（Ｔ３、Ｔ１）、（Ｔ２）｝
Ｄ５＝｛（Ｔ１、Ｔ２、Ｔ３）｝
この例の場合には、例えば以下の通りプロセッサＰｎにタスクＴｎを割り当てる。
【００２６】
Ｐ１：（Ｔ１）
Ｐ２：（Ｔ２）
Ｐ３：（Ｔ３）
Ｐ４：（Ｔ１、Ｔ２）
Ｐ５：（Ｔ２、Ｔ３）
Ｐ６：（Ｔ３、Ｔ１）
Ｐ７：（Ｔ１、Ｔ２、Ｔ３）
上記の通り、同じ一つのタスクが複数のプロセッサに割り当てられている。
【００２７】
従って、振り分け方法テーブルＤｎに対しては、プロセッサは以下のように割り当てられていることになる。
【００２８】
Ｄ１＝｛Ｐ１、Ｐ２、Ｐ３｝
Ｄ２＝｛Ｐ４、Ｐ３｝
Ｄ３＝｛Ｐ５、Ｐ１｝
Ｄ４＝｛Ｐ６、Ｐ２｝
Ｄ５＝｛Ｐ７｝
ここで、上記の通り、異なる振り分け方法テーブルＤｎに同じプロセッサＰｎが割り当てられている。例えば、プロセッサＰ１は振り分け方法テーブルＤ１とＤ３で共通に使われており、従って、振り分け方法テーブル毎に必要なプロセッサの合計数よりも、必要なプロセッサ数は少ない。
【００２９】
まず処理開始シーケンスとして、各プロセッサのデータキャッシュは全てのキャッシュラインをデータ無効(invalid)と設定する。プロセッサの動作が開始されると、プロセッサのうち二つ以上のタスクが割り当てられたプロセッサは、図示しないタイマ割り込みによりカーネルがスイッチを行い割り当てられたタスク間の遷移を繰り返す。
【００３０】
この状態が続く中で、各プロセッサは適切なタスクの巡回停止条件を満たしたときに調停プロセッサに通知して動作を停止する。ここで適切なタスクの巡回停止条件とは、たとえば現在のプロセッサで動作しているタスク以外からのメッセージを要求するような場合である。
【００３１】
このときの動作を、上記のプロセッサＰ４にタスクＴ１、Ｔ２が割り当てられている場合の例を挙げて説明する。プロセッサＰ４のＯＳは自分に割り当てられたタスクがＴ１とＴ２である事を実行開始時に知っているので、タスクＴ１が要求したメッセージがタスクＴ３から獲得するものと判定した時点で、Ｐ４はＯＳを通じて調停プロセッサへ停止状態を通知し、停止する。
【００３２】
このようにして、各プロセッサは自身の内部で動作しているタスク以外の外のタスクからの情報が必要になった場合などに調停プロセッサに知らせて停止する。このようにして次々とプロセッサが停止していく。
【００３３】
またここで別の停止条件として、以下の場合がある。初期状態で各プロセッサのデータキャッシュは全てのキャッシュラインがデータ無効(invalid)とされたので、読み込み／書き込みで各ラインがデータ有効(valid)となり埋められていくが、キャッシュのライトバックは停止されている。全てのデータキャッシュラインが有効データで埋められた後に、キャッシュラインが全てラインダーティすなわち全てのキャッシュライン上にプロセッサからの書き込みが行なわれるまで動作を続け、全てダーティラインになった後にストア命令によるキャッシュミスが発生した時点で、ライトバックリフィルを行なわずに、プロセッサは停止し、調停プロセッサへ停止状態を通知する。（データキャッシュヒットによるダーティラインへの再度上書きや、データ有効(valid)でもダーティでないキャッシュラインが残っている場合のラインのリプレースの場合は動作継続する。）
このようにして、データキャッシュ内容を共有メモリへ必ずライトバックしなければならなくなった場合には、調停プロセッサに、データキャッシュを全てダーティラインとしたプロセッサ番号を知らせて全てのプロセッサを停止する。
【００３４】
ここで、前項の発明が解決しようとする課題で述べた通り、停止するまでの各タスクのデータ処理量は、プロセッサ１つにタスク１つを割り当てた場合にタスク遷移が起こらず最もデータ処理効率が高いとは限らないことに注意する。何故ならば、本構成の場合、高速キャッシュ内にタスク間のメッセージを保持しており、もし一つのプロセッサ内で動作しているタスク間で高速キャッシュ内のメッセージを交換できれば、異なるプロセッサ間で動作するタスク間でのメッセージ通信より処理が高効率になる可能性があるからである。
【００３５】
例えば、プロセッサＰｎとタスクＴｎにおいて、以下のように割り当てられているとする。
【００３６】
Ｐ１：（Ｔ１）
Ｐ２：（Ｔ２）
Ｐ４：（Ｔ１、Ｔ２）
このとき、Ｐ１、Ｐ２はタスクの遷移が無いことに関しては高速だが、プロセッサに直結するキャッシュが異なるため、このタスク間でメッセージ通信が起こった場合、異なるプロセッサとキャッシュ間でのデータの同期をとらなければならず、処理時間がかかる。更に、プロセッサの個数が膨大でありタスク間の通信のしくみが複雑である場合、各キャッシュ間で同期をとることは複雑となる。一方、Ｐ４ではタスクが複数でありタスクの遷移が起こるが、このプロセッサ内のタスク間の通信に関しては、同一キャッシュ内でデータの整合性がとれているため、データ同期に要する処理時間は必要ない。従って、どの組み合わせがより効率的かは、実行中の動作にもよりケースバイケースであるといえる。
【００３７】
ここで、調停プロセッサでは上記の振り分け方法テーブルＤｎのうち、プロセッサの止まる毎に止まったプロセッサを含むテーブルを無効にしていく。こうして、最後まで生き残ったテーブルのプロセッサの上で動作するタスク群とキャッシュ内容を有効とする。すなわち、この時点では有効として生き残ったキャッシュ内のタスク制御に関するデータが有効となる。その後、プロセッサが止まった時点でキャッシュの有効な内容を共有メモリに書き戻す。停止した時点で複数のテーブルが有効な場合は、任意の方法、望ましくはプロセッサの数の少ない振り分けテーブルを選択すれば良い。
【００３８】
一方で、前述の通り、あるプロセッサのデータキャッシュが全てダーティラインになり、全てのプロセッサが停止させられた場合には、キャッシュを全てダーティラインにしたプロセッサを含む振り分け方法テーブルを有効とする。例えばプロセッサＰ３のデータキャッシュが全てダーティラインになり、それを調停プロセッサに通知して全プロセッサが停止した場合には、振り分け方法テーブルＤ１、Ｄ２
Ｄ１＝｛Ｐ１、Ｐ２、Ｐ３｝
Ｄ２＝｛Ｐ４、Ｐ３｝
がプロセッサＰ３を含むので、Ｄ１またはＤ２のプロセッサのデータキャッシュを共有メモリに書き戻す。ここでは実施例として、振り分け方法テーブルＤ２のプロセッサＰ４、Ｐ３のデータを書き戻す。
【００３９】
この後、再び処理開始シーケンスに戻り、全てのキャッシュラインをデータ無効(invalid)と設定し、同様の処理を繰り返せばよい。
【００４０】
このとき、生き残った複数のプロセッサ内のキャッシュデータを共有メモリに書き出しているが、この場合に複数プロセッサのデータキャッシュの整合性がとれているかどうかについては以下の通りである。例えば、プロセッサＰｎとタスクＴｎに関して、
Ｐ３：（Ｔ３）
Ｐ４：（Ｔ１、Ｔ２）
が最後まで有効であったとすると、
Ｐ３と、Ｐ４のデータキャッシュを共有メモリへライトバックすることになる。このとき、もしキャッシュラインが同じアドレスをさしている場合には、キャッシュが共有メモリへ書き込むデータが複数ある事になり、排他制御が行なわれておらず、矛盾が生じる事になる。しかし、このような現象が発生する場合は、そもそも独立したタスク間（上記の例では、（Ｔ１、Ｔ２）と（Ｔ３）との間）で勝手に通信手順を無視して共通アドレスにデータを書き込んでいる事になり、不正かあるいは一意な結果を期待しないアクセスである。したがってこの場合、ライトバック実行時に異なるプロセッサのキャッシュに同一アドレスラインが有った場合は調停プロセッサにエラー通知が行なわれる機構（図示せず）が接続されており、ユーザーがプログラムミスであるかどうかを判定できるようになっている。ユーザーが明示的に共通領域にデータを書き込む場合、プロセッサをまたぐタスク間で事前にメッセージ通信を行なう必要があり、その場合、本発明の制御手順により、プロセッサは正常に停止する事になる。（但し例外として、次のようなユーザーが意図しない問題も発生する可能性がある。例えば、グローバル変数として１バイトのデータを用い、キャッシュラインが３２バイトであるような場合である。この時、同じ３２バイトキャッシュライン内に１バイトの異なる２つのグローバル変数が配置される可能性があり、各々独立にタスクでアクセスされる場合などは、たとえタスク間で独立したデータ領域として扱いアクセスしたとしても、プロセッサ間のキャッシュラインのデータに矛盾が生じて上記の問題が起きうる。したがって、この問題を回避する為に、グローバル変数はキャッシュラインのバイト数、たとえば３２バイトでアラインされるようにコンパイル時に設定しておく必要がある。）
また、本発明の構成例においては、入出力データは共有メモリの一部を、入出力データのリングバッファとして用い、リングバッファとＩ／Ｏコントローラの制御は調停プロセッサで行ない、データの整合性を保つ。
【００４１】
なお、上記の実施例では、タスク３つの場合に、全てのマルチプロセッサの組み合わせの振り分け方法テーブルを生成したが、プロセッサの数とタスクの数の組み合わせにより、適切なテーブル数に制限しても良い。
【図面の簡単な説明】
【００４２】
【図１】システムＬＳＩのハードウェア構成とマルチタスクの制御方法
【符号の説明】
【００４３】
１００  バス
２００  共有メモリ
３００  システムＬＳＩで構成される部分
４００  ＤＭＡコントローラ
５００  調停プロセッサ
【図１】
2006039824.tif 000003