説明

マルチプロセッサシステム、及びマルチプロセッサシステムの制御方法

【課題】各CPU(プロセッサ)の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステム、マルチプロセッサシステムの制御方法を提供すること
【解決手段】メモリ30は、CPU1及びCPU2からアクセスされる。セマフォ制御回路204は、CPU1、CPU2からメモリ30へのロック命令、アンロック命令を受信して、メモリ30の同期制御を行う。詳細には、セマフォ制御回路204は、ロックを行ったプロセッサがロック処理を行っている時間(ロック処理時間)をカウントする。また、セマフォ制御回路204は、ロック中にロック命令を送信したプロセッサの命令送信順序を保持し、算出済みのロック処理時間と、命令送信順序を基に、ロックに失敗した各プロセッサの待ち時間を算出して通知する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明はマルチプロセッサシステム、及びマルチプロセッサシステムの制御方法に関し、特に共有リソースを扱うマルチプロセッサシステム、及びマルチプロセッサシステムの制御方法に関する。
【背景技術】
【0002】
近年、複数のCPU(Central Processing Unit)を有するマルチコア構成のプロセッサシステムが多く使用されている。これらのプロセッサシステムにおけるCPU数は、年々増加している。そのため、多くのCPUを搭載するマルチプロセッサシステムでは、CPU間の排他制御がシステム全体の性能に大きな影響を与えている。排他制御が適切に行われない場合、CPU数を増加してもシステム全体の性能が十分に向上しない恐れもある。マルチコア構成のプロセッサシステムにおいて、排他制御、すなわちセマフォの使用効率を改善することによりシステム全体の性能向上を実現できる。
【0003】
以下に、一般的なマルチコアシステムの構成、及び当該システムでのセマフォを用いた排他制御等について説明する。図1は、一般的なマルチプロセッサシステムの構成を示すブロック図である。当該マルチプロセッサシステムは、CPU1〜nと、CPU1〜nからアクセス可能なメモリ30と、CPU1〜nからメモリ30へのアクセスを制御するメモリコントローラ20と、を有する。
【0004】
CPU1〜nは、それぞれ独立してメモリ30にアクセスすることができる。そのため、CPU1〜nがメモリ30の共有メモリ(アドレス)にアクセスする場合、複数のCPUが同時に共有メモリにアクセスしないように排他制御処理を行う必要がある。このCPU間で行われる排他制御は、一般的にセマフォと呼ばれる共通フラグを用いて行われる。各CPUは、セマフォを獲得するための命令(LOCK命令)を実行し、共有メモリへのアクセス可否を判定する。
【0005】
以下、図8のフローチャートを参照して具体的な排他制御の動作の流れを説明する。はじめに、あるCPUは、セマフォを獲得するためにLOCK命令を発行する(S1000)。LOCK命令の処理部は、LOCK命令に付与されるアドレスのセマフォを索引し、セマフォの値が1の場合、LOCK失敗(セマフォ獲得失敗)を発行元のCPUに返却する(S1001:NO)。一方、セマフォの値が0の場合、LOCK命令の処理部は、セマフォの値を1に更新して、LOCK成功(セマフォ獲得成功)を発行元のCPUに返却する(S1001:YES)。
【0006】
CPUは、LOCK成功の通知を受け取った場合、共有メモリにアクセスし(S1002)、アクセス後にUNLOCK命令を発行してセマフォの値を0にリセットする、すなわちセマフォを解放する(S1003)。一方、LOCK失敗の通知を受け取った場合、CPUは、一定時間の待ち合わせを行い(S1004)、待ち合わせ後にLOCK命令を再発行する。
【0007】
次に、CPU1〜4を有する一般的なマルチプロセッサシステムにおけるセマフォの処理フローを図9及び図10を参照して説明する。図9及び図10は、セマフォにかかる各CPUの動作を示すフロー図である。図9及び図10における縦軸は、時間軸(単位はStep)を示す。CPU1〜4の発行するLOCK命令は、全て同一アドレスに対する命令とする。図9は、LOCK失敗からLOCK命令の再発行までの時間が短い場合のフローを示す。図10は、LOCK失敗からLOCK命令の再発行までの時間が長い場合のフローを示す。
【0008】
図9において、CPU2〜4は、Step4においてLOCK失敗の通知を受信すると、Step6にLOCK命令を再発行する。また、CPU2〜4は、Step7においてLOCK失敗の通知を受信すると、Step9にLOCK命令を再発行する。
【0009】
次に、図10を参照する。図10において、CPU2〜4は、Step4においてLOCK失敗の通知を受信すると、Step14にLOCK命令を再発行する。この場合、Step8〜Step14の間は、セマフォの値が0(共有メモリへのアクセスがない状態)となる。
【0010】
続いて、セマフォ処理に関連する技術を開示した文献を以下に説明する。特許文献1は、セマフォの使用効率を改善する手法を開示している。当該手法では、LOCK失敗時にLOCK命令の優先順位を登録し、UNLOCK命令実行後に優先順位の高いCPUにLOCK解除を通知している。
【0011】
特許文献2は、メモリ共有型のマルチプロセッサにおいて各プロセッサからのメモリアクセスの沈み込みを防ぐ手法が開示されている。当該手法では、メモリアクセス要求時に実行順序を保持し、当該順序に応じてメモリにアクセスする。
【先行技術文献】
【特許文献】
【0012】
【特許文献1】特開平4−128957号公報
【特許文献2】特開平6−195312号公報
【発明の概要】
【発明が解決しようとする課題】
【0013】
図9に記載したフローでは、図示するようにCPU2〜4は、何度もLOCK命令を再発行する。これにより、各CPU(CPU2〜4)の負荷が高くなってしまう。
【0014】
一方、図10に記載したフローでは、図示するようにCPU2〜4は、Step4においてLOCK失敗を受信すると、Step14までLOCK命令の再発行を行わない。しかし、CPU1は、Step8においてUNLOCK命令を発行している。すなわち、Step8からStep14までのセマフォの値は、0(不使用)となり、セマフォの使用効率が悪い。
【0015】
すなわち、図9、図10を参照して説明したマルチプロセッサシステムでは、LOCK命令発行のための負荷が高くなる(各CPUの処理負荷が高くなる)、または、セマフォの使用効率が悪くなるという問題があった。
【0016】
なお、特許文献1に記載の技術は、図8に示す動作に新規の処理を追加する必要があり、一般的なシステムに適用することが困難である。さらに、特許文献1に記載の技術では、全てのCPUをLOCK解除待ち(セマフォの取得待ち)状態に遷移させると、LOCK解除待ちの状態にあるCPUは、いつLOCK解除(セマフォ取得)が行われるかわからない。
【0017】
特許文献2に記載の技術によっても、各CPUがどの程度セマフォの解放を待てばよいかを把握することができなかった。
【0018】
すなわち、上記したいずれの手法によっても、各CPU(プロセッサ)の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステムを実現することが困難であった。
【0019】
本発明は上記した課題に鑑みてなされたものであり、各CPU(プロセッサ)の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステム、マルチプロセッサシステムの制御方法を提供することを主たる目的とする。
【課題を解決するための手段】
【0020】
本発明にかかるマルチプロセッサシステムの一態様は、
複数のプロセッサと、
前記複数のプロセッサからアクセスされる共有リソースと、
プロセッサからの前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うセマフォ制御回路と、を備え、
前記セマフォ制御回路は、あるプロセッサの前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、を基に前記共有リソースに対するロックに失敗した各プロセッサの待ち時間を算出して通知する、ものである。
【0021】
本発明にかかるマルチプロセッサシステムの制御方法の一態様は、
複数のプロセッサと、前記複数のプロセッサからアクセスされる共有リソースと、を備えるマルチプロセッサにおいて、プロセッサからの前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うマルチプロセッサの制御方法であって、
あるプロセッサの前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、を基に前記共有リソースに対するロックに失敗した各プロセッサの待ち時間を算出して通知する、ものである。
【発明の効果】
【0022】
本発明では、各CPU(プロセッサ)の処理負荷を軽減し、セマフォの使用効率を向上させたマルチプロセッサシステム、マルチプロセッサシステムの制御方法を提供することができる。
【図面の簡単な説明】
【0023】
【図1】実施の形態1にかかるマルチプロセッサシステムの全体構成を示すブロック図である。
【図2】実施の形態1にかかるメインコントローラ20の構成を示すブロック図である。
【図3】実施の形態1にかかるセマフォ制御回路204の構成を示すブロック図である。
【図4】実施の形態1にかかるLOCK成功・失敗判定回路2043によるLOCKの成否の判定方法を示す図である。
【図5】実施の形態1にかかるマルチプロセッサシステム(特にメモリコントローラ20)の動作を示すフロー図である。
【図6】実施の形態1にかかるLAB2041、LCT2042の索引結果、及び更新結果を示す図である。
【図7】実施の形態1にかかるマルチプロセッサシステムの全体構成を示すブロック図である。
【図8】一般的なマルチプロセッサシステムのセマフォ処理を示すフローチャートである。
【図9】一般的なマルチプロセッサシステムの動作を示すフロー図である。
【図10】一般的なマルチプロセッサシステムの動作を示すフロー図である。
【発明を実施するための形態】
【0024】
<実施の形態1>
以下、図面を参照して本発明の実施の形態について説明する。図1は、本実施の形態にかかるマルチプロセッサシステムの全体構成を示すブロック図である。本実施の形態にかかるマルチプロセッサシステムは、一般的なマルチコアプロセッサの構成要素と同一の要素を有する。当該マルチプロセッサシステムは、CPU(Central Processing Unit)1〜nと、CPU1〜nからアクセス可能なメモリ30と、CPU1〜nからメモリ30へのアクセスを制御するメモリコントローラ20と、を有する。
【0025】
CPU1〜nは、それぞれ独立してメモリ30にアクセスする。CPU1〜nは、メモリ30内の共有メモリ(メモリ30内の共有される領域であり、共有リソースの一態様である)にアクセスする場合、セマフォを獲得するためのLOCK命令をメモリコントローラ20に発行する。CPU1〜nは、メモリ30内の共有メモリの使用後に、セマフォを解放するためのUNLOCK命令をメモリコントローラ20に発行する。
【0026】
さらに、CPU1〜nは、メモリコントローラ20からLOCK命令に対するLOCK失敗の通知を受信した場合、LOCK失敗と共に通知される待ち時間だけ待ち合わせを行う。CPU1〜nは、待ち合わせの後にLOCK命令を再発行する。
【0027】
一方、CPU1〜nは、メモリコントローラ20からLOCK命令に対するLOCK成功の通知を受信した場合、メモリ30の共有メモリにアクセスする。CPU1〜nは、処理終了後にメモリコントローラ20に対してUNLOCK命令を発行する。なお、セマフォは、メモリ30の任意のアドレスに配置され、LOCK命令、またはUNLOCK命令に付与するアドレスにより該当するセマフォを指定する。
【0028】
メモリコントローラ20は、CPU1〜nからメモリ30へのアクセスを制御する制御装置である。メモリコントローラ20の詳細は、図2のブロック図を参照して説明する。図2は、メモリコントローラ20の構成を示すブロック図である。
【0029】
メモリコントローラ20は、CPU命令調停回路201と、CPU命令デコーダ202と、メモリ制御回路203と、セマフォ制御回路204と、CPU命令返信回路205と、を備える。
【0030】
CPU命令調停回路201は、CPU1〜nから受信した命令を調停する回路である。CPU命令デコーダ202は、CPU命令調停回路201が調停した命令をデコードし、デコードした命令がメモリ30へのアクセスである場合に、メモリ制御回路203に当該命令を供給する。CPU命令デコーダ202は、デコードした命令がLOCK命令またはUNLOCK命令である場合、LOCK命令またはUNLOCK命令をセマフォ制御回路204に供給する。
【0031】
セマフォ制御回路204は、受信したLOCK命令またはUNLOCK命令に対して、LOCKが成功したか否か(セマフォを獲得できたか否か)の判定を行うとともに、LOCKが失敗した(セマフォを獲得できない)場合の待ち時間の算出を行う。
【0032】
CPU命令返信回路205は、CPU1〜nから受信した命令に対する返信を行う回路である。
【0033】
ここで、セマフォ制御回路204について、図3を参照して更に詳しく説明する。図3は、セマフォ制御回路204の内部構成を示すブロック図である。セマフォ制御回路204は、LOCKアドレスバッファ(以降の説明では、LABと略して記載する)2041と、LOCK競合テーブル(以降の説明では、LCTと略して記載する)2042と、LOCK成功・失敗判定回路2043と、を有する。
【0034】
LAB2041は、ワード0〜n(nは1以上の任意の整数)から構成され、LOCKが成功した(セマフォを獲得できた)LOCK命令の情報を複数(最大n個)登録できるバッファである。なお、同一アドレスに対して、同時にLOCKが成功することはあり得ないため、同一アドレスへのLOCK命令は1ワードしか登録されない。
【0035】
LAB2041のワードnは、Vビット20411と、セマフォアドレス20412と、LOCK時間20413と、から構成される。Vビット20411は、ワードnが有効であるか否かを示すビット値である。Vビット20411は、1が設定された場合にLOCK処理が実行されていること(有効であること)を示す。セマフォアドレス20412は、LOCK命令内に含まれるアドレス(メモリ30内において、アクセスしたい共有メモリのアドレス)である。LOCK時間20413は、Vビット20411に"1"が設定された時間(ステップ数)、すなわちLOCK状態となっている積算時間を保持するカウンタである。
【0036】
さらに、LAB2041は、アドレス比較器20414と、セレクタ20415−1と、セレクタ20415−2と、を有する。アドレス比較器20414は、CPU命令デコーダ202から新たに入力されたLOCK命令内のアドレスと、各ワード内のセマフォアドレス20412と、を比較する。アドレス比較器20414は、CPU命令デコーダ202から新たに入力されたLOCK命令内のアドレスと一致するセマフォアドレス20412のワード番号を検出する。アドレス比較器20414は、検出したワード番号をLOCK成功・失敗判定回路2043、セレクタ20415−1、セレクタ20415−2に通知する。
【0037】
セレクタ20415−1は、通知されたワード番号に対応するVビット20411の値を取得して、取得値をLOCK成功・失敗判定回路2043に通知する。セレクタ20415−2は、通知されたワード番号に対応するLOCK時間20413の値を取得して、取得値をLOCK成功・失敗判定回路2043に通知する。
【0038】
LAB2041は、LOCK成功・失敗判定回路2043によりLOCKが成功したと判定された場合、該当するワードのVビット20411の値を0から1に更新する。LAB2041は、Vビット20411の値を1に更新するとともに、該当するワードのLOCK時間20413のカウント(Vビット20411の有効(1)期間のカウント)を開始する。
【0039】
アドレス比較器20414は、CPU命令デコーダ202からUNLOCK命令を受信した場合、UNLOCK命令に含まれるアドレスと一致するセマフォアドレス20412のワード番号を検出する。LAB2041は、検出したワードのVビット20411を0に更新することによりLOCKを解除し(セマフォを解放し)、当該ワードのLOCK時間20413のカウントを停止する。
【0040】
なお、UNLOCK命令と同一アドレスのLOCK命令がLCT2042に存在する場合、LOCK時間カウンタ20413の値をLCT2042のLOCK時間に登録する。但し、LCT2042のLOCK時間20426に0以外の値が既に登録されている場合は登録しない。
【0041】
続いて、LCT2042について説明する。LCT2042は、LAB2041と同様に、ワード0〜n(nは1以上の任意の整数)から構成され、LOCKが失敗した(セマフォを獲得できなかった)LOCK命令の情報を複数(最大n個)登録できるバッファである。ただし、同一アドレスに対するLOCK命令は1ワードしか登録しない。
【0042】
LCT2042のワードnは、Vビット20421と、セマフォアドレス20422と、ステータスフラグ20423と、受付番号20424と、優先番号20425と、LOCK時間20426と、から構成される。
【0043】
Vビット20421は、ワードnが有効であるか否かを示すビット値である。Vビット20421に1が設定されている場合、有効(該当ワードのセマフォアドレス20422にアクセスするLOCK命令が再発行される)であることを示す。セマフォアドレス20422は、LOCK命令内に含まれるアドレス(メモリ30内において、アクセスしたい共有メモリのアドレス)である。ステータスフラグ20423は、CPUの個数と同じだけ各ワードに設けられる。ステータスフラグ20423は、CPU毎のLOCK成功、失敗のステータスを保持する。ステータスの詳細は後述する。
【0044】
受付番号20424は、CPUの個数と同じだけ各ワードに設けられる。受付番号20424は、各CPUのLOCK命令の受け付け順序(発行順序)を保持する。優先番号20425は、LOCK失敗したLOCK命令のうち、最も優先順位の高い(次に処理を行う)LOCK命令の受付番号を保持する。LOCK時間20426は、セマフォアドレス20422と対応するセマフォアドレス20412を持つLAB2041内のワードのLOCK時間20413の値を保持する。LOCK時間20426は、UNLOCK命令の処理時に、LOCK処理を終了したLOCK命令の処理時間が設定される。具体例は、図5及び図6を参照して再度説明する。
【0045】
さらに、LCT2042は、アドレス比較器20427と、セレクタ20428−1〜20428−5と、を有する。アドレス比較器20427は、CPU命令デコーダ202から新たに入力されたLOCK命令、UNLOCK命令内のアドレスと、各ワード内のセマフォアドレス20422と、を比較する。アドレス比較器20427は、CPU命令デコーダ202から新たに入力されたLOCK命令内、UNLOCK命令内のアドレスと一致するセマフォアドレス20422のワード番号を検出する。アドレス比較器20427は、検出したワード番号をLOCK成功・失敗判定回路2043、及びセレクタ20428−1〜20428−5に通知する。
【0046】
セレクタ20428−1〜20428−5は、通知されたワード番号に対応する値を接続先から取得して、取得値をLOCK成功・失敗判定回路2043に通知する。
【0047】
LCT2042は、入力されたLOCK命令のLOCKが失敗したとLOCK成功・失敗判定回路2043に判定され、当該LOCK命令と同一のLOCK命令がLCT2042内に登録されていない場合(アドレス比較器20427の比較において入力されたLOCK命令と同一のセマフォアドレス20422を持つワードがない、またはワードがあるがVビット20421に0が設定されている場合)、当該LOCK命令の情報をLCT2042に追加する。一方、同一のLOCK命令がLCT2042内に登録されている場合、LOCK成功・失敗判定回路2043は、対応するワードのステータスフラグ20423と、受付番号20424と、の値を更新する。ただし、発行元CPUに対応するステータスフラグ20423に既に"00"以外の値が設定されている場合は処理を行わない。
【0048】
ここで、CPU毎に設定されるステータスフラグ20423は、LOCK命令の処理状態が2ビットで設定される。"00"は、初期状態を示す。"10"は、LOCK失敗により、LOCK命令を再発行している状態を示す。"11"は、LOCKが失敗していたLOCK命令が再発行によりLOCK成功した状態を示す。
【0049】
CPU毎に設定される受付番号20424は、LOCK処理が失敗したLOCK命令の受け付け順序を示す。受付番号20424は、ステータスフラグ20423の更新の際に、ステータスフラグ20423に"10"が設定されている個数をカウントした値となる。つまり、受付番号20424には、LOCK失敗によりLOCK命令の再発行処理を行っているCPUの数が登録される。例えば、CPU1、CPU2、CPU3の順序でLOCK命令が失敗した場合、CPU1の受付番号20424は"0"、CPU2の受付番号20424は"1"、CPU3の受付番号20424は"2"となる。
【0050】
優先番号20425は、LCT2042に登録されているLOCK命令がLOCK成功する毎にインクリメント(1だけ増加)する。なお、詳細な動作例は、図5及び図6を参照して後述する。
【0051】
LOCK成功・失敗判定回路2043の動作について説明する。LOCK成功・失敗判定回路2043は、LAB2041及びLCT2042から索引結果(アドレス比較器、またはセレクタが出力した値)を受信し、受信した情報からLOCKの成否を判定する。LOCK成功・失敗判定回路2043によるLOCKの成否の判定方法を図4に示す。図4は、LAB2041及びLCT2042からの入力と、LOCKの成否判定との関係を示す図である。
【0052】
図4において、Vビットは、LAB2041またはLCT2042から取得したVビットの値を示す。なお、アドレス比較器20414、アドレス比較器20427は、一致するセマフォアドレスを検出できなかった場合、Vビットを0とする。
【0053】
LOCK成功・失敗判定回路2043は、項番1(LAB2041及びLCT2042に該当するワードがあり、共にVビットが0に設定されている)と項番3(LAB2041に設定されたVビットが0であり、LCT2042に設定されたVビットが1であり、かつ優先順位が最も高い)のケースにはLOCKが成功したと判定する。LOCK成功・失敗判定回路205は、項番1、項番3に該当しない場合にはLOCKが失敗したと判定する。詳細な例は、図5、図6を参照して再度説明する。
【0054】
LOCK成功・失敗判定回路2043は、LOCKが失敗したと判定した場合、LOCK命令の発行元のCPUに対して通知する待ち時間を算出する。LOCK成功・失敗判定回路2043は、LOCK命令の発行元の各CPUに対応する受付番号20424と、優先番号20425と、LOCK時間20426と、から以下の計算式を用いて各CPUの待ち時間を算出する。LOCK成功・失敗判定回路2043は、LOCK失敗の情報に算出した待ち時間を付与して、CPU命令返信回路205に送信する。
待ち時間 =(受付番号20243−優先番号20425)×LOCK時間20426
【0055】
次に、図5及び図6を参照して、本実施の形態にかかるマルチプロセッサシステム(特にメモリコントローラ20、セマフォ制御回路204)の動作について説明する。図5は、CPU1〜4を有する本実施の形態にかかるマルチプロセッサシステムの動作フローを示す図である。図中において、縦軸は時間軸(単位はStep)を示し、それぞれの時刻をStep1〜26とする。なお、CPU1〜4が発行するLOCK命令のアドレスは、全て同じアドレスとする。
【0056】
図6は、図5の各ステップにおいて、CPU1〜4が発行したLOCK命令、UNLOCK命令に対するLAB2041、LCT2042の索引結果、及び更新結果を示す図である。Step0では、LAB2041、LCT2042は初期状態に設定され、Vビットは"0"にリセットされている。また、優先番号20425等も全て"0"にリセットされている。
【0057】
はじめにCPU1は、Step1において、メモリコントローラ20にLOCK命令を発行する。メモリコントローラ20は、CPU1からLOCK命令を受信する。メモリコントローラ20内のCPU命令調停回路201は、CPU間の調停を行い、CPU1のLOCK命令を選択する。選択されたCPU1のLOCK命令は、CPU命令デコーダ202によりデコードされる。CPU命令デコーダ202は、デコードの結果、LOCK命令であることを認識する。CPU命令デコーダ202は、LOCK命令をセマフォ制御回路204に供給する。
【0058】
セマフォ制御回路204(詳細にはアドレス比較器)は、受信したLOCK命令のアドレスを用いて、LAB2041とLCT2042を索引する。セマフォ制御回路204(LOCK成功・失敗判定回路2043)は、LAB2041とLCT2042のVビットが0であることを認識し、LOCK成功と判定する。そして、セマフォ制御回路204は、更新処理においてLAB2041に当該LOCK命令を登録し、LOCK時間の計測を開始する(なお、図6においては、"t1"と記載する。)。
【0059】
メモリコントローラ20は、Step2において、LOCK成功をCPU1に通知する。
【0060】
CPU2〜4は、Step3において、ほぼ同時にメモリコントローラ20にLOCK命令を発行する。メモリコントローラ20内のCPU命令調停回路201は、CPU間の調停を行い、CPU2〜4のLOCK命令を選択する。なお、本例では、Step3において、CPU命令調停回路201は、CPU2、CPU3、CPU4の順番でCPU命令デコーダ202にLOCK命令を送信する。
【0061】
CPU命令デコーダ202は、受信した命令をデコードし、LOCK命令をセマフォ制御回路204に供給する。セマフォ制御回路204には、はじめにCPU2からのLOCK命令が入力される。セマフォ制御回路204は、このLOCK命令内のアドレスを基に、LAB2041と、LCT2042を索引する。この索引結果は、図6のStep3内の発行元CPU=CPU2に示す通りである。
【0062】
セマフォ制御回路204は、LAB2041のVビットが1であるため、LOCK処理が失敗したと判定する。さらに、セマフォ制御回路204は、LCT2042のVビットが0であるため、LCT2042に対し、CPU2が発行したLOCK命令を新規登録する。この時、セマフォ制御回路204は、LCT2042のCPU2に対応するステータスフラグ20423に"10"(LOCK失敗により、LOCK命令を再発行している状態)を設定し、受付番号20424に"0"を登録する。Vビット20421には、"1"を設定する。
【0063】
次にセマフォ制御回路204は、CPU3からのLOCK命令が入力される。セマフォ制御回路204は、このLOCK命令内のアドレスを基に、LAB2041と、LCT2042を索引する。セマフォ制御回路204は、LAB2041のVビットが1であるため、CPU2からのLOCK命令と同様に、LOCK処理が失敗したと判定する。さらに、セマフォ制御回路204は、LCT2042のVビットが1であるため、LCT2042に対応するワードが存在すると判定する。そのため、セマフォ制御回路204は、当該ワードに対し、CPU3に対応するステータスフラグ20423に"10" を設定し、受付番号20424に"1"を登録する。
【0064】
セマフォ制御回路204は、CPU4からのLOCK命令についても同様の処理を行う。セマフォ制御回路204は、当該ワードに対し、CPU4に対応するステータスフラグ20423に"10" を設定し、受付番号20424に"2"を登録する。なお、上述した処理結果は、図6のStep3の各欄に記載されている。
【0065】
メモリコントローラ20は、Step4において、LOCK失敗をCPU2〜4に通知する。この際、セマフォ制御回路204は、LCT2042の索引結果からLOCK命令の再発行までの待ち時間を計算し、算出した値をLOCK失敗の情報と合わせて通知する。しかし、Step4の時点では、CPU1のLOCK処理が完了していない。そのため、セマフォ制御回路204は、待ち時間を0とする。
【0066】
CPU2〜4は、メモリコントローラ20からLOCK失敗の通知を受け取ると、LOCK命令の待ち合わせを行う。この場合、待ち時間は0であるため、CPU2〜4は、待ち合わせを行わない。
【0067】
CPU2〜4は、Step6において、メモリコントローラ20に対してLOCK命令を再発行する。メモリコントローラ20は、Step3にて受信したLOCK命令と同様に処理を行う。すなわち、セマフォ制御回路204は、LAB2041とLCT2042を索引し、LOCK失敗の判定を行う。また、LCT2042内にCPU2〜4に対応するステータスフラグ20423が登録されているため、LCT2042の更新は行われない。
【0068】
メモリコントローラ20は、Step7において、LOCK失敗をCPU2〜4に通知する。本処理は、Step4における処理と同一であるため、詳細な説明は省略する。また、Step8におけるCPU2〜4のLOCK命令の発行処理は、Step6と同一であり、Step9におけるメモリコントローラ20の処理は、Step7と同一であるため、図示及び詳細な説明は省略する。
【0069】
CPU1は、Step8において、メモリコントローラ20に対して、共有メモリへのアクセス命令を発行する。メモリコントローラ20は、当該アクセス命令を受信し、CPUメモリ制御回路203を介してメモリ30にアクセスする。
【0070】
CPU1は、Step9において、メモリコントローラ20に対してUNLOCK命令を発行する。メモリコントローラ20は、UNLOCK命令を受信する。メモリコントローラ20内のセマフォ制御回路204は、UNLOCK命令に含まれるアドレスを基にLAB2041と、LCT2042を索引する(索引結果は、図6Step9を参照されたい。)。そして、セマフォ制御回路204は、CPU1のLAB2041のVビットを0に設定することによりLOCK命令を解除する。また、セマフォ制御回路204は、LAB2041にて計測したLOCK時間20413をLCT2042のLOCK時間20426に登録する。
【0071】
CPU2〜4は、Step10において、LOCK命令をメモリコントローラ20に対して再発行する。本例では、メモリコントローラ20内のCPU命令調停回路201は、CPU4、CPU3、CPU2の順番でLOCK命令をCPU命令デコーダ202に送信する。
【0072】
セマフォ制御回路204は、はじめにCPU4からのLOCK命令を受信する。セマフォ制御回路204は、CPU4からのLOCK命令に含まれるアドレスを基にLAB2041と、LCT2042を索引する(索引結果は、図6Step10、CPU=CPU4を参照されたい。)。ここで、LAB2041のVビットは0にリセットされているが、LCT2042のVビットは1である。さらに、CPU4の受付番号20424の値"2"は、優先番号20425の値"0"と異なる(CPU4からのLOCK命令の優先順位が低い)。そのため、セマフォ制御回路204は、CPU4からのLOCK命令についてLOCK失敗と判定する。
【0073】
この際、LOCK時間20426が登録されている、すなわちCPU1のLOCK処理時間が確定している。そのため、セマフォ制御回路204は、CPU4の待ち時間を2t1(CPU4の受付番号20424の値"2"から優先順位20425の値"0"を減算した値に、t1を乗算した値)と算出する。
【0074】
CPU4からのLOCK命令と同様の手法により、セマフォ制御回路204は、CPU3からのLOCK命令に対し、LOCK失敗と判定する。また、セマフォ制御回路204は、CPU3の待ち時間をt1(CPU3の受付番号20424の値"1"から優先順位20425の値"0"を減算した値に、t1を乗算した値)と算出する。
【0075】
次にセマフォ制御回路204は、CPU2からのLOCK命令を受信する。セマフォ制御回路204は、CPU2からのLOCK命令に含まれるアドレスを基にLAB2041と、LCT2042を索引する(索引結果は、図6Step10、CPU=CPU2を参照されたい。)。ここで、LAB2041のVビットは0にリセットされており、LCT2042のVビットは1であり、CPU2の受付番号20424の値"0"は、優先番号20425の値"0"と同一である(CPU2のLOCK命令の優先順位が高い)。そのため、セマフォ制御回路204は、LOCK成功と判定する。セマフォ制御回路204は、CPU2のLOCK命令をLAB2041に登録し、同時にLCT2042のCPU2にかかるステータスフラグ20423を更新し("10"から"11")、優先番号20425の値を更新(カウントアップ、"0"から"1")する。
【0076】
メモリコントローラ20は、Step11において、CPU2に対してLOCK成功を通知する。メモリコントローラ20は、Step11において、CPU3及びCPU4に対してLOCK失敗を通知する。この通知の際に、メモリコントローラ20は、CPU3に対して待ち時間の値(t1)をLOCK失敗の情報に含めて通知する。同様に、メモリコントローラ20は、CPU4に対して待ち時間の値(2t1)をLOCK失敗の情報に含めて通知する。
【0077】
CPU3は、LOCK失敗の通知を受信すると、LOCK失敗の情報に付与された待ち時間(t1)の情報を取得する。同様に、CPU4は、LOCK失敗の通知を受信すると、LOCK失敗の情報に付与された待ち時間(2t1)の情報を取得する。これにより、CPU3は、Step15まで待ち合わせを行う。CPU4は、Step20まで待ち合わせを行う。
【0078】
CPU2は、Step13において、共有メモリへのアクセスを実行し、Step14においてUNLOCK命令を発行する。なお、当該処理は、Step8、9におけるCPU1の動作と同じであるため、詳細な説明は省略する。
【0079】
CPU3は、Step15においてt1時間の待ち合わせ処理を終了し、LOCK命令を再発行する。この時、CPU4は、待ち合わせ処理の実行が終了していないため(残待ち合わせ時間=2t1−t1=t1)、LOCK命令の再発行は行わない。メモリコントローラ20は、CPU3からLOCK命令を受信する。メモリコントローラ20内のセマフォ制御回路204は、CPU3からのLOCK命令に含まれるアドレスを基にLAB2041とLCT2042を索引する。そして、セマフォ制御回路204は、上述の手法によりLOCKが成功したと判定する。
【0080】
メモリコントローラ20は、Step16において、CPU3に対してLOCK成功を通知する。
【0081】
CPU3は、Step18において、共有メモリへのアクセスを実行し、Step19においてUNLOCK命令を発行する。なお、当該処理は、Step8、9におけるCPU1の動作と同じであるため、詳細な説明は省略する。
【0082】
CPU4は、Step20において2t1時間の待ち合わせ処理を終了し、LOCK命令を再発行する。メモリコントローラ20は、CPU4からLOCK命令を受信する。メモリコントローラ20内のセマフォ制御回路204は、CPU4からのLOCK命令に含まれるアドレスを基にLAB2041とLCT2042を索引する。そして、セマフォ制御回路204は、上述の手法によりLOCKが成功したと判定する。
【0083】
この時、LCT2042内のステータスフラグ20423に"10"の値を持つCPUが存在しなくなる。そのため、セマフォ制御回路204は、LCT2042のVビット20421を"0"にリセットする。
【0084】
メモリコントローラ20は、Step21において、CPU4に対してLOCK成功を通知する。
【0085】
CPU4は、Step23において、共有メモリへのアクセスを実行し、Step24においてUNLOCK命令を発行する。なお、当該処理は、Step8、9におけるCPU1の動作と同じであるため、詳細な説明は省略する。
【0086】
続いて、本発明にかかるマルチプロセッサシステムの効果を、図5の動作フロー図を参照して説明する。図5に示すように、CPU2〜4は、CPU1がUNLOCK命令によりLOCKを解除(セマフォを解放)するStep9まで、LOCK命令の再発行を繰り返している。しかし、CPU1のLOCK命令の処理時間が確定する(CPU2のLOCK命令がLOCK成功となる)と、CPU3、4は、メモリコントローラ20からLOCK命令の再発行までの待ち時間を受信する。CPU3、4は、この待ち時間の間、LOCK命令の発行を待ち合わせる。
【0087】
CPU3及びCPU4に通知される待ち時間は、メモリコントローラ20が処理するLOCK命令の順序(優先順位)と、CPU1のLOCK命令の処理時間と、から算出された値である。そのため、CPU3に通知される待ち時間と、CPU4に通知される待ち時間には、異なる時間が指定される。これにより、CPU3及びCPU4がStep11にてLOCK失敗の通知を受信すると、CPU3は、Step15にてLOCK命令を再発行する。一方、CPU4は、Step20にてLOCK命令を再発行する。
【0088】
この待ち時間の設定により、CPU3及びCPU4は、Step11以降に無駄なLOCK命令を発行しない。すなわち、CPU3及びCPU4の処理負荷が、LOCK命令の発行を削減することによって軽減される。
【0089】
さらに、図5に示すように、CPU3及びCPU4は、他のCPUがUNLOCK処理をした直後にLOCK命令を発行している。これにより、セマフォの使用効率を改善することができる(LOCKを効率的に行うことができる)。
【0090】
なお、上述した特許文献1の手法では、図8に示す動作フローに対して、新たな処理(LOCK失敗と判定した場合にLOCK命令の優先順位を登録し、UNLOCK命令の処理後に優先順位の高いCPUにLOCK解除を通知する処理)を追加する必要がある。一方、本実施の形態にかかるマルチプロセッサシステムでは、図8に示す動作フローにおいて、待ち時間の最適化処理のみを行うだけで、上述の効果(CPU処理負荷の軽減、セマフォの使用効率改善)を奏することができる。
【0091】
さらにまた、特許文献1の手法では、前述のようにLOCK解除待ちの状態にあるCPUは、いつLOCK解除(セマフォ取得)が行われるかわからない。そのため、LOCK解除待ちの状態にあるCPUは、他の処理を行うことなく、LOCK解除の命令を待ち続ける必要がある。
【0092】
一方、本実施の形態にかかるマルチプロセッサシステム内の各CPUは、LOCK命令の再発行までの待ち時間を正確に把握することができる。そのため、各CPUは、待ち時間の間に別の処理を実行することができ、CPUリソースを有効に利用することができる。例えば、図5において、CPU3は、Step12〜Step14の間に他の処理を実行できる。また、CPU4は、Step12〜〜Step19の間に他の処理を実行できる。
【0093】
ここで、図7を参照して、本発明の概要を改めて説明する。図7は、本発明にかかるマルチプロセッサシステムの本質的部分のみを抽出して記載したブロック図である。マルチプロセッサシステムは、CPU1と、CPU2と、メモリコントローラ20と、メモリ30と、を有する。メモリコントローラ20は、セマフォ制御回路204を有する。
【0094】
メモリ30は、CPU1及びCPU2からアクセスされる。すなわち、メモリ30は、共有されるリソースである。セマフォ制御回路204は、CPU1、CPU2からメモリ30へのロック命令、アンロック命令を受信して、メモリ30の同期制御を行う。
【0095】
詳細には、セマフォ制御回路204は、ロックを行ったプロセッサがロック処理を行っている時間(ロック処理時間)をカウントする。また、セマフォ制御回路204は、ロック中にロック命令を送信したプロセッサの命令送信順序を保持し、算出済みのロック処理時間と、命令送信順序を基に、ロックに失敗した各プロセッサの待ち時間を算出して通知する。なお、セマフォ制御回路204は、ロック成功時にも、ロック成功をロック命令発行元に対して通知する。
【0096】
上述のように、セマフォ制御回路204は、算出済みのロック処理時間と、命令送信順序を基に、各プロセッサの待ち時間を通知する。ロックに失敗した各プロセッサは、ロック命令の発行順に応じた正確な待ち時間を把握することができるため、適切なタイミングでロック命令を再発行できる。これにより、不要なロック命令の発行を回避することができ、CPUの処理負荷を軽減することができる。さらに、正確な待ち時間に基づいてロック命令を再発行するため、セマフォの使用効率を向上することができる(アンロック後に即座にロック処理ができる)。
【0097】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【0098】
10−1〜10−n CPU(Central Processing Unit)
20 メモリコントローラ
201 CPU命令調停回路
202 CPU命令デコーダ
203 メモリ制御回路
204 セマフォ制御回路
2041 LOCKアドレスバッファ(LAB)
20411 Vビット
20412 セマフォアドレス
20413 LOCK時間
20414 アドレス比較器
20415 セレクタ
2042 LOCK競合テーブル(LCT)
20421 Vビット
20422 セマフォアドレス
20423 ステータスフラグ
20424 受付番号
20425 優先番号
20426 LOCK時間
20427 アドレス比較器
20428 セレクタ
2043 LOCK成功・失敗判定回路
205 CPU命令返信回路
30 メモリ

【特許請求の範囲】
【請求項1】
複数のプロセッサと、
前記複数のプロセッサからアクセスされる共有リソースと、
プロセッサから発行される前記共有リソースに対するロック命令、アンロック命令の受信に応じて、前記共有リソースの同期制御を行うセマフォ制御回路と、を備え、
前記セマフォ制御回路は、あるロック命令にかかる前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を発行したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、に基づいて前記共有リソースに対するロックに失敗した各プロセッサのロック命令再発行までの待ち時間を算出して通知する、マルチプロセッサシステム。
【請求項2】
前記セマフォ制御回路は、
前記共有リソースのロックに成功した前記ロック命令に関する第1エントリをn個(nは1以上の整数)保持する第1バッファと、
前記共有リソースのロックに失敗した前記ロック命令に関する第2エントリをn個(nは1以上の整数)保持する第2バッファと、
前記第1及び第2エントリと、入力されたロック命令との比較に応じて、当該ロック命令に対するロックの成否を判定し、ロック失敗の場合に前記待ち時間を算出する判定回路と、を備える、ことを特徴とする請求項1に記載のマルチプロセッサシステム。
【請求項3】
前記第1エントリは、ロックの有効性を示す第1Vビット値と、前記共有リソースのアドレスを示す第1アドレスと、前記ロック時間をカウントする第1ロック時間と、を有する構成であり、
前記第2エントリは、ロックが失敗したプロセッサがあるか否かを示す第2Vビット値と、前記共有リソースのアドレスを示す第2アドレスと、プロセッサ毎のロック命令の処理状態を示すステータスフラグと、プロセッサ毎のロック命令の入力順序を示す受付番号と、現在ロック中のロック命令のアンロック後にインクリメントされ、アンロック後にロックが許可されるロック命令の識別情報を示す優先番号と、確定した前記ロック時間を保持する第2ロック時間と、を有する構成であることを特徴とする請求項2に記載のマルチプロセッサシステム。
【請求項4】
前記判定回路は、
入力されたロック命令に含まれるアドレスに基づいて、前記第1バッファと、前記第2バッファからそれぞれ対応する前記第1、前記第2エントリを取得し、
当該第1、第2エントリにかかる前記第1及び第2Vビット値が共に無効値(0)である場合、または当該第1エントリにかかる前記第1Vビット値が無効値(0)でありであり、当該第2エントリにかかる前記第2Vビット値が有効値(1)であり、かつ当該第2エントリにかかる前記受付番号と前記優先番号とが同じ場合、入力されたロック命令に対してロックを許可し、それ以外の場合にはロックを許可しないことを特徴とする、請求項3に記載のマルチプロセッサシステム。
【請求項5】
前記判定回路は、
ロックに失敗した各プロセッサに対し、当該プロセッサにかかる前記受付番号から前記優先番号を減算した値に前記第2ロック時間の値を乗算した値を前記待ち時間とすることを特徴とする請求項4に記載のマルチプロセッサシステム。
【請求項6】
前記判定回路は、
前記第2ロック時間に初期値が設定されている場合、ロックに失敗した各プロセッサに対し、前記待ち時間として0(待ち合わせなし)を通知することを特徴とする請求項3乃至請求項5のいずれか1項に記載のマルチプロセッサシステム。
【請求項7】
複数のプロセッサと、前記複数のプロセッサからアクセスされる共有リソースと、を備えるマルチプロセッサにおいて、プロセッサから発行される前記共有リソースに対するロック命令及びアンロック命令の受信に応じて、前記共有リソースの同期制御を行うマルチプロセッサの制御方法であって、
あるロック命令の前記共有リソースのロック時間をカウントし、前記共有リソースのロック中にロック命令を送信したプロセッサの命令送信順序を保持し、確定した前記ロック時間と、前記命令送信順序と、に基づいて、前記共有リソースに対するロックに失敗した各プロセッサのロック命令再発行までの待ち時間を算出して通知する、マルチプロセッサの制御方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate


【公開番号】特開2013−97544(P2013−97544A)
【公開日】平成25年5月20日(2013.5.20)
【国際特許分類】
【出願番号】特願2011−239264(P2011−239264)
【出願日】平成23年10月31日(2011.10.31)
【出願人】(000168285)エヌイーシーコンピュータテクノ株式会社 (572)
【Fターム(参考)】