(57)【特許請求の範囲】
【請求項１】
共有メモリと複数のプロセッサとを備え、前記複数のプロセッサの各々は前記共有メモリへのアクセス頻度情報をもとに共有メモリ使用レベルが設定された１つ以上のタスクを実行するものであって、
前記複数のプロセッサの各々は、実行中の前記タスクの前記共有メモリ使用レベルの値を共有メモリ使用レベルデータとして相互間で通信し、かつ前記複数のプロセッサの各々は、他のプロセッサの共有メモリ使用レベルデータとタスクの前記共有メモリ使用レベルとを用いて前記共有メモリへのアクセスの競合が少なくなるように前記１つ以上のタスクのスケジュールを調整することを特徴とするマルチプロセッサシステム。
【請求項２】
プロセッサの各々に、共有メモリ使用レベルデータの通信とタスクのスケジュールの調整とを行うタスクスケジュール器を設けた請求項１記載のマルチプロセッサシステム。
【請求項３】
他のプロセッサからの共有メモリ使用レベルデータとタスクの前記共有メモリ使用レベルとを用いて、前記タスクのうちから起動するタスクを選択する請求項１または請求項２に記載のマルチプロセッサシステム。
【請求項４】
他のプロセッサからの共有メモリ使用レベルデータが、しきい値より大きければタスクのうちから共有メモリ使用レベルが一番小さいものを選択し、前記他のプロセッサからの前記共有メモリ使用レベルデータが、前記しきい値より小さければ前記タスクのうちから前記共有メモリ使用レベルが一番大きいものを選択する請求項３記載のマルチプロセッサシステム。
【請求項５】
タスクのうちから、共有メモリ使用レベルと他のプロセッサからの共有メモリ使用レベルデータとの和が目標値に一番近くなるものを選択する請求項３記載のマルチプロセッサシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、組み込み機器に於いて階層構造のメモリ共有方法を採るマルチプロセッサシステムに関するものである。
【０００２】
【従来の技術】
従来の、階層構造のメモリ共有方法を採るマルチプロセッサシステムの構造の一例を図１１に示す。
【０００３】
メモリ１５とプロセッサ１６をローカルバス１９に接続したプロセッサエレメントと、メモリ１７とプロセッサ１８をローカルバス２０に接続したプロセッサエレメントがあり、それらがバスブリッジ２１とバスブリッジ２２を介して共有バス２３上の共有メモリ２４と接続している。バスブリッジ２１及びバスブリッジ２２には共有メモリ調停機構２５が接続されており、共有メモリ２４をそれぞれのプロセッサエレメントがアクセスしようとしたときにアクセスの競合を調停する。共有メモリがあるマルチプロセッサシステムでは共有メモリ内の同じアドレス空間を同時にアクセスされた時に生じる不都合を回避するために、ある期間共有メモリアクセスを他方のプロセッサエレメントからアクセスできないようにする、いわゆる同期化処理が各プロセッサで実行されるプログラム中に記述されている。また、同期化処理が不要である共有メモリ上にある読み出し専用のデータについては各プロセッサエレメントが同時に共有メモリをアクセスしようとすると、共有バス２３上でハードウエア的な衝突が発生するために、共有メモリ調停機構２５によりどちらかのプロセッサエレメントの動作を停止させ、他方のプロセッサエレメントによる共有メモリアクセス終了後に停止させたプロセッサエレメントの動作を再開させる。
【０００４】
図１１の構成のシステムに於いてプロセッサエレメントがそれぞれ共有メモリ２４へアクセスするタイミングを示したものが図１２である。図１２において、２６はプロセッサＡのバスアクセスの動き、２７はプロセッサＢのバスアクセスの動き、２８はプロセッサＡが共有メモリを占有する期間、２９はプロセッサＢが共有メモリの使用を待たされている期間、３０はプロセッサＢが共有メモリを占有する期間、３１はプロセッサＢが共有メモリを占有する期間、３２はプロセッサＡが共有メモリの使用を待たされている期間、３３はプロセッサＡが共有メモリを占有する期間、３４はプロセッサＢが共有メモリの使用を待たされている期間、３５はプロセッサＢが共有メモリを占有する期間である。
【０００５】
図１２の２８のタイミングではプロセッサＡが共有バス２３を占有していることを示している。占有しているかどうかはセマフォ、あるいはミューテックス、クリティカルセッション等のソフトウエア的に共有メモリアクセスの競合を阻止する手段を用いて他方のプロセッサエレメントに伝えることができる。２８のタイミング内に発生したプロセッサＢからの共有メモリアクセス２９は待たされる。プロセッサＡによる共有メモリ２４の占有が終了後、３０のタイミングでプロセッサＢからの共有メモリ２４のアクセスが可能となりプロセッサＢがプログラムの実行を再開する。同様に３２のタイミング、３４のタイミングで他方のプロセッサエレメントによる共有バス２３の占有により待たされることになる。
【０００６】
【発明が解決しようとする課題】
従来の方法では、通常、図１１のプロセッサ１６が実行するプログラムとプロセッサ１８が実行するプログラムは他方のプロセッサの実行状態とは無関係に共有メモリ２４にアクセスすることになるため、双方のプロセッサエレメントの共有メモリ２４へのアクセス頻度が多い場合、共有バスアクセス待ち時間が多発し、マルチプロセッサシステムの良さを活かすことができないといった課題があった。
【０００７】
したがって、この発明の目的は、共有メモリへのアクセスの競合を減らし、共有バスへのアクセスの待ち時間を少なくすることができるマルチプロセッサを提供することである。
【０００８】
【課題を解決するための手段】
請求項１記載のマルチプロセッサシステムは、共有メモリと複数のプロセッサとを備え、複数のプロセッサの各々は共有メモリへのアクセス頻度情報をもとに共有メモリ使用レベルが設定された１つ以上のタスクを実行するものであって、複数のプロセッサの各々は、実行中の前記タスクの前記共有メモリ使用レベルの値を共有メモリ使用レベルデータとして相互間で通信し、かつ複数のプロセッサの各々は、他のプロセッサの共有メモリ使用レベルデータとタスクの共有メモリ使用レベルとを用いて共有メモリへのアクセスの競合が少なくなるように１つ以上のタスクのスケジュールを調整することを特徴とするものである。
【０００９】
請求項１記載のマルチプロセッサシステムによれば、複数のプロセッサ間で共有メモリ使用レベルデータをやり取りし、共有メモリへのアクセス頻度情報を元に共有メモリへのアクセスが少なくなるようにプログラムの実行を制御することで、マルチプロセッサシステムで最も懸念される共有メモリへのアクセスの競合を自律的に減らすことができ、共有バスアクセスの待ち時間を減少することができる。
【００１０】
請求項２記載のマルチプロセッサシステムは、請求項１において、プロセッサの各々に、共有メモリ使用レベルデータの通信とタスクのスケジュールの調整とを行うタスクスケジュール器を設けたものである。
【００１１】
請求項２記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００１２】
請求項３記載のマルチプロセッサシステムは、請求項１または請求項２において、他のプロセッサからの共有メモリ使用レベルデータとタスクの共有メモリ使用レベルとを用いて、タスクのうちから起動するタスクを選択するものである。
【００１３】
請求項３記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００１４】
請求項４記載のマルチプロセッサシステムは、請求項３において、他のプロセッサからの共有メモリ使用レベルデータが、しきい値より大きければタスクのうちから共有メモリ使用レベルが一番小さいものを選択し、他のプロセッサからの共有メモリ使用レベルデータが、しきい値より小さければタスクのうちから共有メモリ使用レベルが一番大きいものを選択するものである。
【００１５】
請求項４記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００１６】
請求項５記載のマルチプロセッサシステムは、請求項３において、タスクのうちから、共有メモリ使用レベルと他のプロセッサからの共有メモリ使用レベルデータとの和が目標値に一番近くなるものを選択するものである。
【００１７】
請求項５記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００１８】
【発明の実施の形態】
本発明の一実施の形態について、図１から図１０を用いて説明する。図１は、本発明の一実施の形態におけるマルチプロセッサシステムの構成のブロック図を示す。
【００１９】
図１において、メモリ１とプロセッサ２がローカルバス５に接続されたプロセッサエレメントがあり、他方、メモリ３とプロセッサ４がローカルバス６に接続されたプロセッサエレメントがある。これらのローカルバス５、６はバスブリッジ７とバスブリッジ８を介して共有バス９上の共有メモリ１０と接続している。共有メモリ１０の同時アクセスを調停するための共有メモリ調停機構１１がバスブリッジ７及びバスブリッジ８に接続されている。ここまでは図２の従来例と同じである。
【００２０】
従来例と異なる点は、共有メモリ使用レベルデータ１４をプロセッサエレメント間でやりとりさせ、それぞれのプロセッサエレメントで共有メモリ使用レベルデータ１４の状態に応じて共有メモリ１０の競合が少なくなるようなプログラムタスクを選択して実行させるタスクスケジュール器１２、１３を持つ点である。
【００２１】
図２に示すように、タスクスケジュール器３６（１２、１３）はプログラムタスクが実行可能状態にあるのかどうか等のプログラムタスクの状態を表すタスク状態データ３７と、プログラムタスク毎の共有メモリ使用レベルを表すタスク共有メモリ使用レベルデータ３８（１４）と、他のプロセッサから伝えられる他のプロセッサで実行中のタスクの共有メモリ使用レベルデータ３９の３つのデータを元にタスクのスケジュールを行う。
【００２２】
図３に図１の共有メモリ使用レベルデータ１４を２つのプロセッサ４２、４３でやりとりする場合の配線例を示す。４０はプロセッサ２の共有メモリ使用レベルデータ、４１はプロセッサ１の共有メモリ使用レベルデータである。この例では２ビットの共有メモリ使用レベル信号線を用いて双方のプロセッサに伝達する。
【００２３】
図４に共有メモリ使用レベルデータを３つのプロセッサ４７〜４９でやりとりする場合の配線例を示す。各プロセッサエレメントは自分で実行しているタスクの持つ共有メモリ使用レベルを他のプロセッサエレメントに伝達することで、お互いの共有メモリ使用レベルを認識することができる。４４はプロセッサ２の共有メモリ使用レベルデータ、４５はプロセッサ３の共有メモリ使用レベルデータ、４６はプロセッサ１の共有メモリ使用レベルデータである。
【００２４】
図５に図２のタスク共有メモリ使用レベルデータ３８を生成するシステムを示す。共有メモリアクセス頻度計数器５３はプロセッサＡが実行する各プログラムタスク５０〜５２毎に共有メモリ１０をアクセスする頻度を計数する。各タスク毎に計数された結果を共有メモリ使用レベル判定器５４に入力し、共有メモリ使用レベル判定器５４は共有メモリ使用レベルデータの最大状態数が共有メモリをアクセスする頻度の最も多いタスクに割り当てられるように、タスク毎の共有メモリ使用レベルを算出してプロセッサＡのタスク共有メモリ使用レベルデータ５５を出力する。
【００２５】
図６は図５の共有メモリアクセス頻度計数器５３での各プログラムタスクに対して行われる処理例を示したものである。各プログラムタスクのソースコードファイルの解析を行い、関数定義があれば、その関数名を登録し、同期化処理を行わない共有メモリ上の読み出し専用データの参照があればその参照を行っている関数名とその関数内での参照回数を登録し、また、共有メモリへのアクセスに対する同期化処理があればその処理を行っている関数名とその関数内での同期化処理の回数を登録し、また、関数の呼び出しがあるならばその関数を呼び出している関数名と呼び出し回数を登録する。これらの処理をファイルの最後まで行い、共有メモリ上の読み出し専用データへの総参照回数、同期化処理の総数を算出し、それらを加算して、タスク毎の共有メモリアクセス頻度を算出する。
【００２６】
図７は図５の共有メモリ使用レベル判定器５４の処理例を示したものである。共有メモリ使用レベル判定器５４は共有メモリアクセス頻度計数器５３で算出された各タスク毎の共有メモリアクセス頻度の情報を取り込み、その中の最大値を求め、その最大値を持つタスクの共有メモリ使用レベルが最大になるように共有メモリ使用レベルの判定基準を決める。この基準と各タスク毎の共有メモリアクセス頻度の情報から各タスク毎の共有メモリ使用レベルを判定し、その結果をタスク共有メモリ使用レベルデータ３８として出力する。
【００２７】
図８に図１のタスクスケジュール器１２，１３で行われるタスクスケジュールの処理例を示す。タスクスケジュール器１２，１３では実行可能なタスクが存在する場合、他のプロセッサエレメントから伝達された他のプロセッサでの共有メモリ使用レベルを観測し、その値が共有メモリ使用レベルが採りうる値の中央値以上かどうかで、自プロセッサエレメントで共有メモリ使用レベルの最も小さいタスクを選択するか、共有メモリ使用レベルの最も大きなタスクを選択するかを決めてそれに該当するタスクを選択する。
【００２８】
図９に図１の動作を説明するために使用するプロセッサ１とプロセッサ２で実行されるタスクを示す。それぞれのプロセッサ５６、５７は４つのタスク１〜タスク８を持ち、共有メモリ使用レベルは０から３までの整数値をとるものとし、図５の装置を使って各タスク毎の共有メモリアクセス頻度から各タスク毎に共有メモリ使用レベルがあらかじめ判定されている。これらのタスクを実行させた例を図１０に示す。
【００２９】
図１０において、５８はプロセッサ１で実行されるタスクのタイミング、５９はプロセッサ１が共有メモリへアクセスする、あるいは共有メモリを占有するタイミング、６０はプロセッサ２で実行されるタスクのタイミング、６１はプロセッサ２が共有メモリへアクセスする、あるいは共有メモリを占有するタイミングである。
【００３０】
先ず、プロセッサ１が共有メモリ使用レベルの最も高いタスク４を選択するものとする。プロセッサ２は共有メモリ使用レベルデータを通じてプロセッサ１が共有メモリ使用レベル３のタスクを実行していることを認識し、プロセッサ２のタスクスケジュール器は共有メモリ使用レベルが最も低いタスク５を選択する。これらのタスクが実行されている期間は共有メモリへのアクセスに係わる競合はほとんど生じない。プロセッサ１はタスク４の実行が終わり、プロセッサ２からの共有メモリ使用レベルデータが最も低い０を示しているので、プロセッサ１のタスクスケジュール器は実行可能なタスクの中で最も高い共有メモリ使用レベルを持つタスク３を実行する。プロセッサ２はタスク５の実行を終え、プロセッサ１からの共有メモリ使用レベルが２なので、プロセッサ２のタスクスケジュール器は実行できるタスクの中で最も共有メモリ使用レベルが低いタスク６を選択して実行する。この状態でもプロセッサ１で実行するタスクとプロセッサ２で実行するタスク間に共有メモリアクセス頻度に差があるため、共有メモリへのアクセスに係わる競合が比較的少ない。プロセッサ２はタスク６の実行を終え、プロセッサ１からの共有メモリ使用レベルが２であるため、プロセッサ２のタスクスケジュール器は実行できるタスクの中で最も共有メモリ使用レベルが低いタスク７を選択して実行する。この段階になると双方のプロセッサで実行されるタスクの共有メモリ使用レベルが２と、比較的共有メモリアクセス頻度が高くなるために共有メモリへのアクセスに係わる競合が生じる可能性が高まる。プロセッサ１はタスク３の実行を終え、プロセッサ２からの共有メモリ使用レベルデータが２を示しているので、プロセッサ１のタスクスケジュール器は実行可能なタスクの中で最も低い共有メモリ使用レベルを持つタスク１を実行する。この段階ではプロセッサ１のタスクの共有メモリ使用レベルが０となり、共有メモリへのアクセスに係わる競合が生じる可能性が非常に低くなる。プロセッサ１はタスク１の実行を終え、プロセッサ２からの共有メモリ使用レベルデータが２を示しているので、プロセッサ１のタスクスケジュール器は実行可能なタスクの中で最も低い共有メモリ使用レベルを持つタスク２を実行する。この段階ではプロセッサ１のタスクの共有メモリ使用レベルが１、プロセッサ２のタスクの共有メモリ使用レベルが２となり、共有メモリへのアクセスに係わる競合が生じる可能性がやや高まる。プロセッサ２はタスク７の実行を終え、プロセッサ２のタスクスケジュール器は実行できるタスクの中で最も共有メモリ使用レベルが高いタスク８を選択して実行する。この段階ではプロセッサ１のタスクの共有メモリ使用レベルが１、プロセッサ２のタスクの共有メモリ使用レベルが３となり、共有メモリへのアクセスに係わる競合が生じる可能性が高まる。プロセッサ１はタスク２の実行を終え、プロセッサ１のタスクスケジュール器は実行可能なタスクがないためアイドル状態となる。この段階では共有メモリへのアクセスに係わる競合が生じない。
【００３１】
この実施の形態のマルチプロセッサシステムは、図１に示すように、ローカルバス５、６上にプロセッサ２、４とメモリ１、３を持つプロセッサエレメントが複数個存在し、それらがバスブリッジ７、８を介して共有メモリ１０と接続されており、複数のプロセッサエレメントからの共有メモリ１０へのアクセスに対しての調停機能を持ち、かつ、プロセッサエレメント間で共有メモリ使用レベルデータをやりとりする信号線と、その信号線の状態を元に各プロセッサで実行するプログラムタスクを選択することができるタスクスケジュール器１２、１３から構成されている。したがって、複数のプロセッサ２、４間で共有メモリ使用レベルデータをやり取りし、共有メモリ１０へのアクセス頻度情報を元に共有メモリ１０へのアクセスが少なくなるようにプログラムの実行を制御することで、マルチプロセッサシステムで最も懸念される共有メモリ１０へのアクセスの競合を自律的に減らすことができる。
【００３２】
尚、図８では他のプロセッサが実行中の共有メモリ使用レベルデータが共有メモリ使用レベルがとりうる値のしきい値として中央値よりも大きいか否かによってタスクの選択方法を替えたが、共有メモリ使用レベルがとりうる値の中央値の代わりに異なる値を用いても構わない。また、他のプロセッサが実行中の共有メモリ使用レベルデータがある値よりも大きいか否かによってタスクの選択方法を替える代わりに、他のプロセッサが実行中の共有メモリ使用レベルデータの値と共有メモリ使用レベルとの和が、ある値（例えば共有メモリ使用レベルがとりうる最大値）に一番近くなるようなタスクを選択してもよい。
【００３３】
【発明の効果】
請求項１記載のマルチプロセッサシステムによれば、複数のプロセッサ間で共有メモリ使用レベルデータをやり取りし、共有メモリへのアクセス頻度情報を元に共有メモリへのアクセスが少なくなるようにプログラムの実行を制御することで、マルチプロセッサシステムで最も懸念される共有メモリへのアクセスの競合を自律的に減らすことができ、共有バスアクセスの待ち時間を減少することができる。
【００３４】
請求項２記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００３５】
請求項３記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００３６】
請求項４記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【００３７】
請求項５記載のマルチプロセッサシステムによれば、請求項１と同様な効果がある。
【図面の簡単な説明】
【図１】本発明の一実施の形態におけるマルチプロセッサシステムのブロック図である。
【図２】図１のタスクスケジュール器でデータをやりとりする様子を表した説明図である。
【図３】２つのプロセッサ間での共有メモリ使用レベルデータのやりとりするための配線例の説明図である。
【図４】３つのプロセッサ間での共有メモリ使用レベルデータのやりとりするための配線例の説明図である。
【図５】図２のタスク共有メモリ使用レベルデータを決定するための装置のブロック図である。
【図６】図５の共有メモリアクセス頻度計数器５３での処理例のフロー図である。
【図７】図５の共有メモリ使用レベル判定器５４での処理例のフロー図である。
【図８】図１のタスクスケジュール器での処理例のフロー図である。
【図９】図１の動作を説明するにあたって用いるプロセッサ１とプロセッサ２のタスク例の説明図である。
【図１０】図１のシステムで図９のタスクを動作させた場合の動作タイミングを表した説明図である。
【図１１】従来例の階層型のバス構造を持つマルチプロセッサシステムの一例のブロック図である。
【図１２】図１１のシステムで２つのプロセッサエレメントがそれぞれ共有メモリへアクセスするタイミングを示した説明図である。
【符号の説明】
１  メモリ
２  プロセッサ
３  メモリ
４  プロセッサ
５  ローカルバス
６  ローカルバス
７  バスブリッジ
８  バスブリッジ
９  共有バス
１０  共有メモリ
１１  共有メモリ調停機構
１２  タスクスケジュール器
１３  タスクスケジュール器
１４  共有メモリ使用レベルデータ
１５  メモリ
１６  プロセッサ
１７  メモリ
１８  プロセッサ
１９  ローカルバス
２０  ローカルバス
２１  バスブリッジ
２２  バスブリッジ
２３  共有バス
２４  共有メモリ
２５  共有メモリ調停機構
２６  プロセッサＡのバスアクセスの動き
２７  プロセッサＢのバスアクセスの動き
２８  プロセッサＡが共有メモリを占有する期間
２９  プロセッサＢが共有メモリの使用を待たされている期間
３０  プロセッサＢが共有メモリを占有する期間
３１  プロセッサＢが共有メモリを占有する期間
３２  プロセッサＡが共有メモリの使用を待たされている期間
３３  プロセッサＡが共有メモリを占有する期間
３４  プロセッサＢが共有メモリの使用を待たされている期間
３５  プロセッサＢが共有メモリを占有する期間
３６  タスクスケジュール器
３７  タスク状態データ
３８  タスク共有メモリ使用レベルデータ
３９  他のプロセッサからの共有メモリ使用レベルデータ
４０  プロセッサ２の共有メモリ使用レベルデータ
４１  プロセッサ１の共有メモリ使用レベルデータ
４２  プロセッサ１
４３  プロセッサ２
４４  プロセッサ２の共有メモリ使用レベルデータ
４５  プロセッサ３の共有メモリ使用レベルデータ
４６  プロセッサ１の共有メモリ使用レベルデータ
４７  プロセッサ１
４８  プロセッサ２
４９  プロセッサ３
５０  プロセッサＡが実行するタスク１のプログラム
５１  プロセッサＡが実行するタスク２のプログラム
５２  プロセッサＡが実行するタスクｎのプログラム
５３  共有メモリアクセス頻度計数器
５４  共有メモリ使用レベル判定器
５５  プロセッサＡのタスク共有メモリ使用レベルデータ
５６  プロセッサ１の４つのタスク
５７  プロセッサ２の４つのタスク
５８  プロセッサ１で実行されるタスクのタイミング
５９  プロセッサ１が共有メモリへアクセスする、あるいは共有メモリを占有するタイミング
６０  プロセッサ２で実行されるタスクのタイミング
６１  プロセッサ２が共有メモリへアクセスする、あるいは共有メモリを占有するタイミング
【図１】
0004190629.tif 000002
【図２】
0004190629.tif 000003
【図３】
0004190629.tif 000004
【図４】
0004190629.tif 000005
【図５】
0004190629.tif 000006
【図６】
0004190629.tif 000007
【図７】
0004190629.tif 000008
【図８】
0004190629.tif 000009
【図９】
0004190629.tif 000010
【図１０】
0004190629.tif 000011
【図１１】
0004190629.tif 000012
【図１２】
0004190629.tif 000013