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