共有経路調停方法及びマルチシステム
【課題】マルチシステム全体でみた平均許可待ち時間を短くできる新しいバス調停方法の実現。
【解決手段】複数の処理装置11-0,1,2,3と、複数の処理装置によりアクセスされる共有資源14と、共有経路13と、共有経路の数の処理装置への割当てを制御する共有経路調停回路12と、を備えるマルチシステムであって、各処理装置は、実行予定の処理において共有資源14へのアクセスを要求する回数をカウントしてアクセス要求回数信号Niを出力するアクセス要求先読みユニット29を備え、共有経路調停回路12は、複数の処理装置から共有経路への割当てを要求された時には、アクセス要求回数の少ない処理装置に共有経路を割当てる。
【解決手段】複数の処理装置11-0,1,2,3と、複数の処理装置によりアクセスされる共有資源14と、共有経路13と、共有経路の数の処理装置への割当てを制御する共有経路調停回路12と、を備えるマルチシステムであって、各処理装置は、実行予定の処理において共有資源14へのアクセスを要求する回数をカウントしてアクセス要求回数信号Niを出力するアクセス要求先読みユニット29を備え、共有経路調停回路12は、複数の処理装置から共有経路への割当てを要求された時には、アクセス要求回数の少ない処理装置に共有経路を割当てる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の処理装置が共有経路を介して共有資源にアクセスするマルチシステム及びそのようなシステムにおいて共有経路を割当てる共有経路調停方法に関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、プロセッサなどの処理装置を複数個設け、並行して処理を進めることにより、処理速度を向上することが従来から行われている。複数個の処理装置は、共有メモリなどの共有資源にアクセスして、処理装置間のデータの転送などを行う。このようなマルチシステムには、各種の方式がある。例えば、通常のＣＰＵなどで構成されるマスタプロセッサと、浮動小数点演算や入出力処理などのマスタプロセッサで行うのが適当でない特定の処理を実行するコプロセッサと、を有するコプロセッサ方式のマルチプロセッサシステムがあり、このシステムはパーソナルコンピュータなどに広く使用されている。このシステムでは、例えばマスタプロセッサが処理した処理結果を外部に出力する場合には、マスタプロセッサは処理結果を共有メモリに記憶し、入出力処理用プロセッサに出力する共有メモリのアドレス範囲を指定する。これに応じて入出力処理用プロセッサは指定された共有メモリのアドレス範囲をアクセスして出力ポートにデータを転送する。この間、共有メモリへのアクセス権は入出力処理用プロセッサが占有し、マスタプロセッサは共有メモリにアクセスできない。もし一度に出力するデータ量が多いと、マスタプロセッサなどのほかのプロセッサが長時間共有メモリにアクセスできないという事態になるので、例えば、一回で連続して転送可能なデータ量の上限を定めて、一回の共有メモリへのアクセスが終了すると、他のプロセッサに共有メモリへのアクセス権を渡すことが行われる。これがバス（共有経路）調停である。
【０００３】
マルチシステムとしては、他にも、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムや、回線などの通信経路を介して複数の処理装置（コンピュータ、プロセッサ）や記憶装置（メモリ）などを接続し、相互に通信などを行いながら処理を進めるシステムもある。いずれの場合も、複数の処理装置が共有する資源にアクセスするための共有経路を有し、共有経路の調停を行う必要がある。
【０００４】
共有経路の調停方式は、従来から各種提案されている。例えば、共有経路へのアクセスが発生した順に割当てる方式（ＦＩＦＯ方式）や、共有経路へのアクセスが発生している処理装置に順に割当てる方式（ラウンドロビン方式）や、共有経路へのアクセス回数の多い処理装置に優先的に割当てる方式や、共有経路へのアクセス回数がもっとも長く行われていない処理装置に優先的に割当てる方式(Least Recently Used: LRU方式)などがある。
【０００５】
本発明は、共有経路の調停を行う構成であれば適用可能であるが、説明を簡単にするために、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムを例として説明を行う。
【０００６】
【特許文献１】特開平５−２１６６８８号公報
【特許文献２】特開平１１−７３３９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
マルチシステムにおける共有経路（バス）調停方式では、共有バスへのアクセス要求が発生してからバスの占有が許可されてアクセスが行えるようになるまでの許可待ち時間をできるだけ短くすることを要求される。
【０００８】
上記のように、マルチシステムにおける共有経路（バス）調停方式には各種の方式があるが、いずれの従来方式も、各プロセッサに平均的にバス占有権を割当てること、言い換えれば許可待ち時間をできるだけ均等にするか、バスを使用する頻度の高いプロセッサに優先的にバス占有権を割当てることを主眼にしている。しかし、従来のバス調停方式では、バスの使用頻度の低いプロセッサに対するバス占有権の割当てが遅くなり、システム全体でみた平均許可待ち時間が長く、システム全体としてはかならずしも効率的でないという問題があった。
【０００９】
本発明は、マルチシステム全体でみた平均許可待ち時間を短くできる、マルチシステムにおける新しいバス調停方法の実現を目的とする。
【課題を解決するための手段】
【００１０】
上記目的を実現するため、本発明の共有経路（バス）調停方法は、各処理装置で実行予定の処理における共有資源へのアクセス要求回数を算出して、複数の処理装置から共有経路への割当てを要求された時には、アクセス要求回数のもっとも少ない処理装置に共有経路を割当てる。
【００１１】
すなわち、本発明の共有経路調停方法は、複数の処理装置と、前記複数の処理装置によりアクセスされる共有資源と、前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、を備えるマルチシステムにおいて、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停方法であって、前記複数の処理装置のそれぞれにおいて、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、アクセス要求回数を算出し、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする。
【００１２】
また、本発明のマルチシステムは、複数の処理装置と、前記複数の処理装置によりアクセスされる共有資源と、前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停回路と、を備えるマルチシステムであって、前記複数の処理装置のそれぞれは、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、前記共有経路調停回路にアクセス要求回数を出力するアクセス要求先読みユニットを備え、前記共有経路調停回路は、前記複数の処理装置のそれぞれの前記アクセス要求先読みユニットから出力される前記アクセス要求回数を受け、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする。
【００１３】
分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数は意味がなくなるので破棄する。図示していないが、条件分岐命令などにおいて、条件の成立か否かによって２つのアドレスに分かれ、これらの２つの中で確率の高い一方の分岐先を予め予測して命令の先読みを行い、パイプラインの流れを円滑にする方式が使われる場合がある。しかしながら、それが失敗した場合に他の一方のアドレスに変更して命令読み出しをやり直すことになり、これを分岐予測の不成功と呼ぶことにする。分岐命令における２つのアドレスとは、該分岐命令の次のアドレスと、該分岐命令に含まれる情報から生成する分岐先アドレスである。一度計算した分岐アドレスや分岐履歴などは、分岐ターゲットバッファと呼ぶバッファに記憶しておき、次回の同一分岐命令実行からはこの記憶されたアドレスや分岐履歴に基づいて分岐先アドレスを予測する。
【００１４】
また、もっとも少ないアクセス要求回数が、複数の処理装置から出力される場合が起こり得るが、その場合には、もっとも少ないアクセス要求回数を出力する処理装置の間で、ラウンドロビン方式で共有経路を割当てる。
【発明の効果】
【００１５】
本発明によれば、マルチシステム全体でみた共有経路（バス）の平均許可待ち時間を、従来方式に比べて短縮することができ、例えばラウンドロビン方式に比べて３０〜５０％短縮することができる。
【発明を実施するための最良の形態】
【００１６】
前述のように、本発明は、共有経路の調停を行う構成であれば適用可能であるが、説明を簡単にするために、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムを例として説明を行う。
【００１７】
図１は、本発明の実施例のマルチプロセッサシステムの全体構成を示すブロック図である。図示のように、本システムは、４個のプロセッサ１１−０〜１１−３と、バス調停回路１２と、共有バス１３と、共有メモリ１４と、を有する。上記の構成要素のうち、共有メモリ１４を除く部分は、１個のチップに実装されており、マルチコア方式のチップとなっている。なお、共有メモリ１４を同一チップ内に設けることも可能であり、逆に各プロセッサ１１−０〜１１−３及びバス調停回路１２を複数のチップに実装することも可能である。
【００１８】
プロセッサ１１−０〜１１−３は、すべて同じ構成で、通常のマイクロプロセッサと同様の構成を有しており、共有バス１３を介して共有メモリ１４と接続するプロセッサバス（アドレスバス及びデータバス）０〜３を有する。また、プロセッサ１１−０〜１１−３からバス調停回路１２にそれぞれバス要求信号Ｒ０〜Ｒ３及びバス要求回数信号Ｎ０〜Ｎ３が出力され、バス調停回路１２からプロセッサ１１−０〜１１−３にそれぞれバス許可信号Ａ０〜Ａ３が出力される。プロセッサ１１−ｉが、共有バス１３の占有権要求（バス要求）を行う時には、バス調停回路１２にバス要求信号Ｒｉをアサートする。プロセッサ１１−ｉからバス調停回路１２に出力されているバス要求回数信号Ｎｉの値は、プロセッサ１１−ｉがバス要求信号を発すると予定される回数である。バス調停回路１２は、バス許可信号Ａｉをアサートすることにより、プロセッサ１１−ｉに共有バス１３の占有権を与える。
【００１９】
同時に複数のプロセッサがバス要求を行った時には、バス調停回路１２はバス要求を行っているプロセッサのバス要求回数信号Ｎｉ（ｉは０〜３の２つ以上）を比較して、その値が最小であるプロセッサ１１−ｉに共有バス１３の占有許可（バス許可）を与える。以上のようにして、プロセッサ１１−ｉは、プロセッサバスｉ及び共有バス１３を介して共有メモリ１４にアクセスできるようになる。
【００２０】
例えば、プロセッサ１１−１及びプロセッサ１１−２がそれぞれバス要求信号Ａ１及びＡ２をアサートしてバス要求を行い、その時にバス要求回数信号Ｎ１＜バス要求回数信号Ｎ２であったとする。この場合、バス調停回路１２は、バス要求回数信号が小さいプロセッサ１１−１にバス許可信号Ａ１をアサートする。これにより、プロセッサ１１−１はプロセッサバス１及び共有バス１３を介して共有メモリ１４にアクセスできるようになる。
【００２１】
また、一個のプロセッサ１１−ｉのみがバス要求信号Ｒｉをアサートしており、他のプロセッサｊ（ｊ≠ｉ）はバス要求信号Ｒｊをアサートしていない時には、バス調停回路１２はバス許可信号Ａｉをアサートする。
【００２２】
システムにおける処理は、プロセッサ１１−０〜１１−３のうちのいずれか１つが、プログラムを共有メモリ１４にロードし、そのプログラムの１個又は複数のスレッドを各プロセッサに割当てる。各プロセッサは割当てられたスレッドを実行し、共有メモリ１４に演算の結果を書き込む。その後、いずれかのプロセッサが演算結果を利用して更に処理を進めるという具合に並列して処理を進める。
【００２３】
図２は、プロセッサ１１−ｉ（ｉ＝０〜３）の構成を示す図であり、プロセッサ１１−０、１１−１、１１−２、１１−３はすべて同じ構成を有する。図示のように、プロセッサ１１−ｉは、内部にプログラムカウンタ２２を有する命令フェッチユニット２１と、プログラムを記憶する命令キャッシュ２３と、実行するために命令キャッシュ２３から読み出した命令を一時的に保持する命令レジスタ２４と、命令を解読する命令デコードユニット２５と、共有メモリ１４からロードした実行する処理に関係する部分のデータを記憶するデータキャッシュ２６と、命令デコードユニット２５で解読した命令に基づいて発生される制御信号を一時的に記憶する制御レジスタ２７と、共有バスを使用する時にバス調停回路１２にバス要求信号Ｒｉを出力すると共にバス調停回路１２からバス許可信号Ａｉを受けるバスステートコントローラ２８と、発生すると予測されるバス要求信号の発生回数を算出してバス要求回数信号Ｎｉを出力するバス要求先読みユニット２９と、を有する。
【００２４】
命令キャッシュ２３は、所定の記憶容量を有し、実行するプログラムを記憶しているが、実行するプログラムが命令キャッシュ２３に記憶されていない時には、共有メモリ１４にアクセスして所定の記憶容量分のプログラムをロードして記憶する。この時には、共有メモリ１４にアクセスするため共有バスの占有権を要求して獲得する必要があり、１回のアクセスでロードするプログラムの量は一定である。
【００２５】
データキャッシュ２６は、所定の記憶容量を有し、その一部は実行するプログラムに関係する所定量のデータを共有メモリ１４からロードして記憶し、他の部分は処理結果などを一時的に記憶する。関係するデータがデータキャッシュ２６に存在しない時には、共有メモリ１４にアクセスして所定の記憶容量分のデータをロードして記憶する。また、１回の処理が終了した時や処理結果が所定量以上になった時には、共有メモリ１４にアクセスして処理結果を共有メモリ１４に転送する。これらの時には、共有メモリ１４にアクセスするため共有バスの占有権を要求して獲得する必要があり、１回のアクセスでロード及び転送するプログラムの量は一定である。
【００２６】
ここでは、説明を簡単にするために、データキャッシュ２６と共有メモリ１４との間で、データのロード及び転送に関するバス要求のみを先読みし、共有メモリ１４から命令キャッシュ２３へのプログラムのロードに関するバス要求は先読みの対象としないが、これを含めることも可能である。
【００２７】
次に図２の回路構成における動作を説明する。まず、プロセッサ１１−ｉ（ｉ＝０〜３）の命令フェッチユニット２１のプログラムカウンタ２２から命令キャッシュ２３に命令アドレスが供給される。命令アドレスで指定された命令が命令キャッシュ２３に保存されている場合、命令キャッシュ２３から命令レジスタ２４に命令がフェッチされる。保存されていない場合、共有メモリ１４から命令キャッシュ２３と命令レジスタ２４に、共有バス１３とプロセッサバスｉを介して命令がフェッチされる。
【００２８】
次に、命令レジスタ２４から命令デコードユニット２５に命令が供給されて、命令デコードユニット２５が命令のデコードを行う。命令デコードユニット２５は、命令のデコード時に、その命令がメモリアクセスを行うかどうかを調べる。メモリアクセスを行う場合、アクセス対象のデータがデータキャッシュ２６に保存されているかどうかを調べる目的で、命令デコードユニット２５からデータキャッシュ２６にデータアドレスが供給される。アクセス対象のデータがデータキャッシュ２６に保存されている場合には、データキャッシュ２６から命令デコードユニット２５に供給されているバス要求起動信号がネゲート（無効に）される。保存されていない場合には、バス要求起動信号がアサート（有効に）される。命令デコードユニット２５から制御レジスタ２７に、バス要求起動信号を含む制御信号群が供給される。なお、アクセス対象のデータがデータキャッシュに保存されていない場合には、バス要求起動信号がアサートされてから適当なクロックサイクル後に、共有メモリ１４からデータキャッシュ２６に、またはデータキャッシュ２６から共有メモリ１４に、共有バス１３とプロセッサバスｉを介してデータが転送される。
【００２９】
次に、制御レジスタ２７からバスステートコントローラ２８にバス要求起動信号が供給される。バス要求起動信号がアサートされている場合、バスステートコントローラ２８からバス調停回路１２に供給されているバス要求信号Ｒｉが適当なクロックサイクル後にアサートされる。バス要求起動信号がネゲートされている場合、バス要求信号Ｒｉはネゲートされたままである。
【００３０】
一方、命令フェッチユニット２１のプログラムカウンタ２２からバス要求先読みユニット２９に命令アドレスが供給され、制御レジスタ２７からバス要求先読みユニット２９にバス要求起動信号が供給され、バス調停回路１２からバス要求先読みユニット２９にバス許可信号Ａｉが供給される。バス要求先読みユニット２９は、命令アドレスとバス要求起動信号とバス許可信号Ａｉに基づいてプロセッサｉの所定時間内に生じると予測されるバス要求回数を計算し、得られた回数をバス要求回数信号Ｎｉとしてバス調停回路１２に供給する。
【００３１】
図３は、バス調停回路１２の構成図である。図示のように、バス調停回路１２は、最小値選択回路３１と、４個の一致回路３２−０〜３２−３と、４個のＡＮＤゲート３３−０〜３３−３と、重複除去回路３４と、を有する。最小値選択回路３１は、プロセッサ１１−０〜１１−３から出力されるバス要求回数信号Ｎ０〜Ｎ３とバス要求信号Ｒ０〜Ｒ３が入力され、バス要求信号ｉがアサートされているプロセッサ１１−ｉのバス要求回数信号Ｎ０〜Ｎ３のうちで値が最小のものを選択し、最小値信号として一致回路３２−０〜３２−３に出力する。ただし、複数のバス要求回数信号が最小値をとる場合もある。この場合、最小値をとっている複数のバス要求回数信号をラウンドロビン方式によって、バス優先権が特定のプロセッサに偏らないようにする。
【００３２】
一致回路３２−ｉ（ｉ＝０〜３）は、それぞれバス要求回数信号Ｎｉの値と最小値選択回路３１から供給される最小値の値が一致するかを判定し、一致する場合には一致信号Ｂｉをアサートし、一致しない場合はＢｉをネゲートする。
【００３３】
ＡＮＤゲート３３−ｉ（ｉ＝０〜３）は、それぞれ一致信号Ｂｉがアサートされ、かつバス要求信号Ｒｉがアサートされた場合に、バス許可候補信号Ｃｉをアサートし、それ以外の場合にはネゲートする。
【００３４】
従って、プロセッサ１１−ｉがバス要求信号Ｒｉをアサートしてバス要求を行った時に、バス要求回数信号Ｎｉの値がすべてのバス要求回数信号Ｎ０〜Ｎ３の中で最小値であれば、バス許可候補信号Ｃｉがアサートされる。
【００３５】
重複除去回路３４は、バス許可候補信号Ｃ０〜Ｃ３が入力され、複数個のバス許可候補信号がアサートされている場合はその中から１個のバス許可候補信号Ｃｉを選択してバス許可信号Ａｉをアサートする。一個のバス許可候補信号Ｃｉだけがアサートされている場合はそれに対応するバス許可信号Ａｉをアサートする。バス許可候補信号Ｃ０〜Ｃ３がすべてネゲートされている場合は、バス許可信号Ａ０〜Ａ３をすべてネゲートする。バス許可信号Ａ０〜Ａ３は、それぞれ重複除去回路３４からプロセッサ１１−０〜１１−３に供給される。
【００３６】
次に、プロセッサのバス要求先読みユニット２９のより詳細な構成を説明する。
【００３７】
図４は、バス要求先読みユニット２９の構成図である。図示のように、バス要求先読みユニット２９は、バス要求解析回路４１と、バス許可解析回路４２と、未来のバス要求カウンタ４３と、長期未許可検出回路４４と、マルチプレクサ４５と、を有する。
【００３８】
バス要求解析回路４１は、命令フェッチユニット２１から命令アドレスを受け、制御レジスタ２７からバス要求起動信号を受け、未来のバス要求カウンタ４３にカウントアップ信号を供給する。バス要求解析回路４１は、命令アドレスとバス要求起動信号に基づき、命令フェッチユニット２１でフェッチされ命令デコードユニット２５でデコードされた命令がバス要求を起動するかどうかを解析し、起動する場合に限りカウントアップ信号をアサートする。従って、プロセッサ１１−ｉが命令キャッシュ２３又はメモリからフェッチしデコードした命令がバス要求を起動する場合、バス先読みユニット２９の未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数が１だけ増加する。
【００３９】
バス許可解析回路４２は、バス調停回路１２からバス許可信号Ａｉが供給され、未来のバス要求カウンタ４３にカウントダウン信号が供給される。バス許可解析回路４２は、バス許可信号Ａｉに基づいてプロセッサ１１−ｉがバス調停回路１２からバス許可を与えられたかどうかを解析し、与えられた場合に限り１クロックサイクル期間だけカウントダウン信号をアサートする。従って、プロセッサ１１−ｉがバス調停回路１２からバス許可を与えられた場合、バス要求先読みユニット２９の未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。
【００４０】
未来のバス要求カウンタ４３からマルチプレクサ４５に未来のバス要求回数候補信号が供給される。未来のバス要求回数候補信号の値は、未来のバス要求カウンタ４３が保持する値であり、カウントアップ信号がアサートされているとクロックエッジに同期して１だけ増加し、カウントダウン信号がアサートされていると１だけ減少する。カウントアップ信号とカウントダウン信号の両方がアサートされている場合は、値は変化しない。
【００４１】
長期未許可検出回路４４は、制御レジスタ２７からバス要求起動信号が供給され、バス調停回路１２からバス許可信号Ａｉが供給され、マルチプレクサ４５に長期未許可信号を供給する。マルチプレクサ４５は、バス調停回路１２にバス要求回数信号Ｎｉを供給する。長期未許可検出回路４４は、バス要求起動信号とバス許可信号Ａｉに基づき、プロセッサ１１−ｉがバス要求を起動してから長期間バス許可を受けていないかどうかを判定し、長期間バス許可を受けていない場合に限り、長期未許可信号をアサートする。マルチプレクサ４５からバス調停回路１２に供給されるバス要求回数信号Ｎｉの値は、長期未許可信号がネゲートされている場合は未来のバス要求回数候補信号の値に一致し、長期未許可信号がアサートされている場合は−１になる。
【００４２】
以上のようにして、プロセッサ１１−ｉのバス要求先読みユニット２９は、命令フェッチユニット２１から供給される命令アドレスと制御レジスタ２７から供給されるバス要求起動信号とバス調停回路１２から供給されるバス許可信号Ａｉに基づきプロセッサ１１−ｉのバス要求回数を先読みし、未来のバス要求カウンタ４３に保持する。そして、プロセッサ１１−ｉのバス要求回数信号Ｎｉが、バス要求先読みユニット２９からバス調停回路１２に供給され、バス調停に活用される。ただし、プロセッサ１１−ｉが長期間バス許可を受けていない場合は、バス要求先読みユニット２９からバス調停回路１２に供給されるバス要求回数信号Ｎｉの値が−１となり、プロセッサ１１−ｉが優先的にバス許可を受けられるようになる。
【００４３】
なお、図示していないが、バス要求先読みユニット２９がプロセッサ１１−ｉのバス要求回数を先読みして分岐命令であることが判明した時には、該分岐命令実行時に分岐予測が不成功の場合に限って未来のバス要求カウンタ４３の値をリセットする。
【００４４】
また、ここでは、各プロセッサは"Out of order"発行を行い、命令キャッシュのヒット率は従来のプロセッサと同様に十分に高いとする。この前提の下で、例えば、プロセッサ１１−０が共有メモリ１４をアクセスしているとする。メモリアクセスはキャッシュアクセスに比べて長時間を要する。そのため、プロセッサ１１−０が共有メモリ１４をアクセスしている間に、他のプロセッサ１１−１〜１１−３は命令キャッシュから後続する命令を複数個フェッチしてデコードできる。これにより、それぞれのプロセッサにおける後続命令のバス要求信号の発生を捕捉できる。従って、命令の先読みは、後続命令を命令キャッシュからフェッチできる限り、共有メモリのアクセス期間が終了するまで続く。
【００４５】
図５は、バス要求解析回路４１の構成図である。図示のように、バス要求解析回路４１は、旧プログラムカウンタ５１と、不一致回路５２と、シフトレジスタ５３と、ＡＮＤゲート５４と、を有する。
【００４６】
命令フェッチユニット２１から旧プログラムカウンタ５１に命令アドレスが供給される。旧プログラムカウンタ５１は、レジスタであり、入力として供給されている命令アドレスをクロックエッジに同期してロードする。命令フェッチユニット２１から不一致回路５２にも命令アドレスが供給され、旧プログラムカウンタ５１から不一致回路５２に旧命令アドレスが供給される。不一致回路５２からシフトレジスタ５３の最上位ビットに命令フェッチ完了信号が供給される。不一致回路５２は、入力として供給される命令アドレスと旧命令アドレスが一致しない場合に限り命令フェッチ完了信号をアサートする。命令フェッチユニット２１が命令のフェッチを完了すると、プログラムカウンタ２２が保持する命令アドレスが更新されるので、命令フェッチユニット２１から不一致回路５２に供給される命令アドレスと旧プログラムカウンタ５１から不一致回路５２に供給される旧命令アドレスが一致しなくなり、不一致回路５２からシフトレジスタ５３の最上位ビットに供給される命令フェッチ完了信号がアサートされる。シフトレジスタ５３はクロックエッジに同期して右に１ビットシフトされる。この時、最上位ビットに命令フェッチ完了信号の値がロードされる。シフトレジスタ５３の最下位ビットからＡＮＤゲート５４に命令デコード完了信号が供給され、制御レジスタ２７からＡＮＤゲート５４にバス要求起動信号が供給される。シフトレジスタ５３のビット数は、命令フェッチユニット２１が命令のフェッチを完了してから命令デコードユニット２５がその命令のデコードを完了するまでに要するクロックサイクル数である。シフトレジスタ５３のビット数をこのように定めることにより、任意の命令について、命令デコード完了信号がアサートされるタイミングとバス要求起動信号がアサートまたはネゲートされるタイミングが一致する。また、命令デコード完了信号とバス要求起動信号が入力として供給されるＡＮＤゲート５４から、未来のバス要求カウンタ４３にカウントアップ信号が供給される。従って、プロセッサ１１−ｉが命令キャッシュ２３またはメモリからフェッチしデコードした命令がバス要求を起動する命令である場合、その命令について命令デコード完了信号とバス要求起動信号がアサートされ、カウントアップ信号がアサートされ、未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ増加する。
【００４７】
図６は、バス許可解析回路４２の構成図である。図示のように、バス許可解析回路４２は、旧バス許可６１と、ＡＮＤゲート６２と、インバータ６３と、を有する。
【００４８】
バス調停回路１２からＡＮＤゲート６２と旧バス許可６１にバス許可信号Ａｉが供給される。旧バス許可６１は、１ビットのレジスタであり、入力として供給されるバス許可信号Ａｉの値をクロックエッジに同期してロードする。旧バス許可６１からインバータ６３に旧バス許可信号が供給され、インバータ６３からＡＮＤゲート６２に旧バス許可信号の反転信号が供給される。ＡＮＤゲート６２から未来のバス要求カウンタ４３にカウントダウン信号が供給される。従って、バス調停回路１２からプロセッサ１１−ｉに供給されるバス許可信号Ａｉがネゲートされていて、適当なクロックサイクル後にバス許可信号Ａｉがアサートされた時に、アサートされた直後の１クロックサイクル間だけ、バス許可解析回路４２から未来のバス要求カウンタ４３に供給されるカウントダウン信号がアサートされ、未来のバス要求カウンタ４３が保持するプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。このようにして、プロセッサ１１−ｉがバス許可を与えられると、プロセッサ１１−ｉからバス調停回路１２に供給されるプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。
【００４９】
図７は、長期未許可検出回路４４の構成図である。図示のように、長期未許可検出回路４４は、インバータ７１と、ＡＮＤゲート７２と、未許可期間カウンタ７３と、長期間レジスタ７４と、比較回路７５と、を有する。
【００５０】
制御レジスタ２７からＡＮＤゲート７２にバス要求起動信号が供給される。バス調停回路１２からインバータ７１にバス許可信号Ａｉが供給される。インバータ７１からＡＮＤゲート７２にバス許可信号Ａｉの反転信号／Ａｉが供給される。ＡＮＤゲート７２から未許可期間カウンタ７３にカウントアップ信号が供給される。バス調停回路１２から未許可期間カウンタ７３にバス許可信号Ａｉがリセット信号として供給される。従って、プロセッサ１１−ｉがバス要求起動信号をアサートしてから、バス調停回路１２によってバス許可信号Ａｉがアサートされるまでの間、未許可期間カウンタ７３の値は上限値に達するまでカウントアップされ続ける。バス調停回路１２によってバス許可信号Ａｉがアサートされると、未許可期間カウンタ７３はリセットされる。未許可期間カウンタ７３から比較回路７５に未許可期間信号が供給され、長期間レジスタ７４から比較回路７５に長期間信号が供給される。比較回路７５からバス要求先読みユニット２９のマルチプレクサ４５へ長期間未許可信号が供給される。比較回路７５は、未許可期間信号の値と長期間信号の値を比較し、未許可期間信号の値が長期間信号の値以上である場合に限り、長期未許可信号をアサートする。なお、長期間レジスタ７４にはあらかじめ長期間を表す値が設定されているものとする。
【００５１】
図８は、バス調停回路１２の最小値選択回路３１の構成図である。図示のように、最小値選択回路３１は、比較回路８１、８２、８７と、マルチプレクサ制御回路８３、８４と、マルチプレクサ８５、８６、８８と、を有する。
【００５２】
比較回路８１は、ａ入力でプロセッサ１１−０のバス要求回数信号Ｎ０を、ｂ入力でプロセッサ１１−１のバス要求回数信号Ｎ１を受け、Ｎ０＜Ｎ１であれば”１”を、Ｎ０＞Ｎ１であれば”０”を、比較結果Ｆ０として出力する。マルチプレクサ８３は、比較回路８１の出力する比較結果Ｆ０及びバス要求信号Ｒ０とＲ１を受け、Ｒ０とＲ１に応じて図９に示すような制御信号Ｇ０を出力する組合せ回路である。すなわち、Ｒ０とＲ１が”０”であれば”２”を、Ｒ０が”０”でＲ１が”１”であれば”０”を、Ｒ０が”１”でＲ１が”０”であれば”１”を、Ｒ０とＲ１が”１”であれば比較結果Ｆ０（０又は１）の値を出力する。マルチプレクサ８５は、制御信号Ｇ０、Ｎ０、Ｎ１及び上限値を受けて、制御信号Ｇ０の値に応じて、Ｎ０、Ｎ１及び上限値のいずれかを出力Ｈ０として出力する。上限値は、バス要求回数信号Ｎｉのとり得る上限値である。すなわち、Ｇ０が”０”であればＮ１を、Ｇ０が”１”であればＮ０を、”２”であれば上限値をＨ０として出力する。従って、Ｒ０とＲ１が”０”であれば上限値が、Ｒ０が”０”でＲ１が”１”であればＮ１が、Ｒ０が”１”でＲ１が”０”であればＮ０が出力され、Ｒ０とＲ１が”１”の時には、Ｎ０＜Ｎ１であればＮ０が、Ｎ０＞Ｎ１であればＮ１が、Ｈ０として出力される。
【００５３】
比較回路８２、マルチプレクサ制御回路８４及びマルチプレクサ８６は、上記の比較回路８１、マルチプレクサ制御回路８３及びマルチプレクサ８５に対応し、対象となる信号がＮ２、Ｎ３及びＲ２、Ｒ３である以外は同じである。従って、Ｒ２とＲ３が”０”であれば上限値が、Ｒ２が”０”でＲ３が”１”であればＮ３が、Ｒ２が”１”でＲ３が”０”であればＮ２が出力され、Ｒ２とＲ３が”１”の時には、Ｎ２＜Ｎ３であればＮ２が、Ｎ２＞Ｎ３であればＮ３が、Ｈ２として出力される。
【００５４】
比較回路８７は、ａ入力でＨ０を、ｂ入力でＨ２を受け、Ｈ０＜Ｈ１であれば”０”を、Ｈ０＞Ｈ１であれば”１”を、比較結果Ｆ１として出力する。マルチプレクサ８８は、Ｈ０とＨ２を受け、Ｆ１が”０”であればＨ０を、Ｆ１が”１”であればＨ１を最小値として出力する。
【００５５】
以上のようにして、最小値選択回路３１は、Ｒ０〜Ｒ３のうちに有効な信号（”１”の信号）があれば、Ｎ０〜Ｎ３のうち有効な信号に対応する信号のうちの最小の値を出力し、Ｎ０〜Ｎ３のいずれも有効でなければ上限値を出力する。
【００５６】
ここで、図３に戻り、一致回路３２−０〜３２−３は、それぞれバス要求回数信号Ｎｉの値と最小値選択回路３１から供給される最小値の値が一致するかを判定し、一致する場合には一致信号Ｂｉをアサートし、一致しない場合はＢｉをネゲートする。ＡＮＤゲート３２−０〜３３−３は、それぞれ一致信号Ｂｉがアサートされ、かつバス要求信号Ｒｉがアサートされた場合に、バス許可候補信号Ｃｉをアサートし、それ以外の場合にはネゲートする。従って、プロセッサ１１−ｉがバス要求信号Ｒｉをアサートしてバス要求を行った時に、バス要求回数信号Ｎｉの値がすべてのバス要求回数信号Ｎ０〜Ｎ３の中で最小値であれば、バス許可候補信号Ｃｉがアサートされる。
【００５７】
図１０は、重複除去回路３４の構成図である。図示のように、重複除去回路３４は、選択回路９１−０〜９１−３と、レジスタＳ９１−０〜９１−３と、ＡＮＤゲート９３−０〜９３−３と、を有する。
【００５８】
図３に示したバス調停回路１２のＡＮＤゲート３３−０〜３３−３から出力されるバス許可候補信号Ｃ０〜Ｃ３が、図示のように選択回路９１−０〜９１−３の４個のｃ入力に順にずらしながら入力される。また、レジスタＳ９２−０〜９２−３の出力Ｄ０〜Ｄ３が、選択回路９１−０〜９１−３の４個のｄ入力に順にずらしながら入力される。これを一般化して表現すると、ｉ＝０，１，２，３とし、ｘ％ｙの表記はｘをｙで除した時の余りとすると、Ｃｉが、選択回路ｉのｃ０入力に、選択回路（ｉ＋１）％４のｃ３入力に、選択回路（ｉ＋２）％４のｃ２入力に、選択回路（ｉ＋３）％４のｃ１入力に、入力される。また、１ビットのレジスタＳ９２−ｉの出力Ｄｉが、選択回路ｉのｄ０入力に、選択回路（ｉ＋１）％４のｄ３入力に、選択回路（ｉ＋２）％４のｄ２入力に、選択回路（ｉ＋３）％４のｄ１入力に、入力される。選択回路ｉは、入力ｃ０〜ｃ３及びｄ０〜ｄ３に応じて図１１に示すような選択信号Ｅｉを出力する組合せ回路である。
【００５９】
１ビットのレジスタＳ９２−ｉは、選択回路ｉから出力される選択信号Ｅｉの値をクロックエッジに同期してロードする。また、レジスタＳ９２−ｉの値は、バス調停回路１２の初期化時に、レジスタＳ９２−０＝１、レジスタＳ９２−ｉ＝０（ｉ≠０）に設定されるものとする。図１１に示すような選択信号Ｅｉを出力する選択回９１−０〜９１−３からレジスタＳ９１−０〜９１−３に供給される選択信号Ｅ０〜Ｅ３のうちで、同時にアサートされる信号は１つだけである。
【００６０】
バス調停回路１２のＡＮＤゲート３３−ｉから重複除去回路３４のＡＮＤゲート９３−ｉにバス許可候補信号Ｃｉが供給され、レジスタＳ９２−ｉから重複除去回路３４のＡＮＤゲート９３−ｉに出力Ｄｉが供給され、重複除去回路３４のＡＮＤゲート９３−ｉからプロセッサ１１−ｉにバス許可信号Ａｉが供給される。従って、バス許可候補信号Ｃｉがアサートされている場合、選択回路ｉが選択信号Ｅｉをアサートし、その値がレジスタＳ９２−ｉにロードされて出力Ｄｉがアサートされた場合に限り、プロセッサ１１−ｉへ供給されるバス許可信号Ａｉがアサートされる。選択回路９１−０〜９１−３からレジスタＳ９２−０〜９２−３に供給される選択信号Ｅ０〜Ｅ３のうちで同時にアサートされる信号は１つだけなので、バス許可候補信号Ｃ０〜Ｃ３のうち２つ以上が同時にアサートされていても、プロセッサ１１−０〜１１−３へ供給されるバス許可信号Ａ０〜Ａ３のうちアサートされる信号は１つだけとなる。
【００６１】
以上本実施例のマルチシステムの構成を説明したが、次に本発明のマルチシステムと従来のラウンドロビン方式のマルチシステムにおける許可待ち時間の比較を行う。
【００６２】
図１２は、従来より一般的に用いられてきたラウンドロビン方式によるバス調停方式と本発明によるバス調停方式における平均許可待ち時間を比較する図であり、（Ａ）はラウンドロビン方式の場合を、（Ｂ）は本発明の場合を示し、同じ条件での比較である。
【００６３】
いずれの場合も、プロセッサはＰ１〜Ｐ４の４個で、ある時点において、プロセッサＰ１〜Ｐ４で、４、２、１、１回の共有メモリアクセスが必要であった場合を示している。ラウンドロビン方式の場合、アクセスはＰ１からＰ４の順に割当てられ、その後再びＰ１にバス権が割当てられる。図示のように、すべてのアクセスが終了するまで、Ｐ１は４期間、Ｐ２は４期間、Ｐ３は２期間、Ｐ４は３期間待つ必要があり、システム全体の平均許可待ち時間は３．２５となる。
【００６４】
これに対して、本発明の方式では、バス要求回数の小さいＰ３及びＰ４を優先するため、Ｐ１は４期間、Ｐ２は４期間、Ｐ３は０期間、Ｐ４は１期間待つ必要があり、システム全体の平均許可待ち時間は１．７５となる。
【００６５】
以上のように、本発明のバス調停方式では、将来のバス要求回数のもっとも少ないプロセッサにバス権を優先して与えることによってシステム全体としてのバスの平均許可待ち時間を低くできるので、システムの性能を向上できる。
【産業上の利用可能性】
【００６６】
本発明は、バスなどのアクセス経路を共有し、アクセス経路を割当てる必要のあるマルチプロセッサシステムであればどのようなものにも適用可能である。
【図面の簡単な説明】
【００６７】
【図１】本発明の実施例のマルチプロセッサシステムの全体構成を示す図である。
【図２】実施例のマルチプロセッサシステムにおけるプロセッサの構成を示す図である。
【図３】実施例のバス調停回路の構成を示す図である。
【図４】バス要求先読みユニットの構成を示す図である。
【図５】バス要求解析回路の構成を示す図である。
【図６】バス許可解析回路の構成を示す図である。
【図７】長期未許可検出回路の構成を示す図である。
【図８】最小値選択回路の構成を示す図である。
【図９】最小値選択回路で使用するマルチプレクサ制御回路の入力と出力の関係を示す真理値表である。
【図１０】重複除去回路の構成を示す図である。
【図１１】重複除去回路で使用する選択回路の入力と出力の関係を示す真理値表である。
【図１２】本発明の従来例に対する効果を説明する図である。
【符号の説明】
【００６８】
１１−０〜１１−３，１１−ｉ プロセッサ
１２ バス調停回路
１３ 共有バス
１４ 共有メモリ
２９ バス要求先読みユニット
３１ 最小値選択回路
【技術分野】
【０００１】
本発明は、複数の処理装置が共有経路を介して共有資源にアクセスするマルチシステム及びそのようなシステムにおいて共有経路を割当てる共有経路調停方法に関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、プロセッサなどの処理装置を複数個設け、並行して処理を進めることにより、処理速度を向上することが従来から行われている。複数個の処理装置は、共有メモリなどの共有資源にアクセスして、処理装置間のデータの転送などを行う。このようなマルチシステムには、各種の方式がある。例えば、通常のＣＰＵなどで構成されるマスタプロセッサと、浮動小数点演算や入出力処理などのマスタプロセッサで行うのが適当でない特定の処理を実行するコプロセッサと、を有するコプロセッサ方式のマルチプロセッサシステムがあり、このシステムはパーソナルコンピュータなどに広く使用されている。このシステムでは、例えばマスタプロセッサが処理した処理結果を外部に出力する場合には、マスタプロセッサは処理結果を共有メモリに記憶し、入出力処理用プロセッサに出力する共有メモリのアドレス範囲を指定する。これに応じて入出力処理用プロセッサは指定された共有メモリのアドレス範囲をアクセスして出力ポートにデータを転送する。この間、共有メモリへのアクセス権は入出力処理用プロセッサが占有し、マスタプロセッサは共有メモリにアクセスできない。もし一度に出力するデータ量が多いと、マスタプロセッサなどのほかのプロセッサが長時間共有メモリにアクセスできないという事態になるので、例えば、一回で連続して転送可能なデータ量の上限を定めて、一回の共有メモリへのアクセスが終了すると、他のプロセッサに共有メモリへのアクセス権を渡すことが行われる。これがバス（共有経路）調停である。
【０００３】
マルチシステムとしては、他にも、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムや、回線などの通信経路を介して複数の処理装置（コンピュータ、プロセッサ）や記憶装置（メモリ）などを接続し、相互に通信などを行いながら処理を進めるシステムもある。いずれの場合も、複数の処理装置が共有する資源にアクセスするための共有経路を有し、共有経路の調停を行う必要がある。
【０００４】
共有経路の調停方式は、従来から各種提案されている。例えば、共有経路へのアクセスが発生した順に割当てる方式（ＦＩＦＯ方式）や、共有経路へのアクセスが発生している処理装置に順に割当てる方式（ラウンドロビン方式）や、共有経路へのアクセス回数の多い処理装置に優先的に割当てる方式や、共有経路へのアクセス回数がもっとも長く行われていない処理装置に優先的に割当てる方式(Least Recently Used: LRU方式)などがある。
【０００５】
本発明は、共有経路の調停を行う構成であれば適用可能であるが、説明を簡単にするために、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムを例として説明を行う。
【０００６】
【特許文献１】特開平５−２１６６８８号公報
【特許文献２】特開平１１−７３３９７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
マルチシステムにおける共有経路（バス）調停方式では、共有バスへのアクセス要求が発生してからバスの占有が許可されてアクセスが行えるようになるまでの許可待ち時間をできるだけ短くすることを要求される。
【０００８】
上記のように、マルチシステムにおける共有経路（バス）調停方式には各種の方式があるが、いずれの従来方式も、各プロセッサに平均的にバス占有権を割当てること、言い換えれば許可待ち時間をできるだけ均等にするか、バスを使用する頻度の高いプロセッサに優先的にバス占有権を割当てることを主眼にしている。しかし、従来のバス調停方式では、バスの使用頻度の低いプロセッサに対するバス占有権の割当てが遅くなり、システム全体でみた平均許可待ち時間が長く、システム全体としてはかならずしも効率的でないという問題があった。
【０００９】
本発明は、マルチシステム全体でみた平均許可待ち時間を短くできる、マルチシステムにおける新しいバス調停方法の実現を目的とする。
【課題を解決するための手段】
【００１０】
上記目的を実現するため、本発明の共有経路（バス）調停方法は、各処理装置で実行予定の処理における共有資源へのアクセス要求回数を算出して、複数の処理装置から共有経路への割当てを要求された時には、アクセス要求回数のもっとも少ない処理装置に共有経路を割当てる。
【００１１】
すなわち、本発明の共有経路調停方法は、複数の処理装置と、前記複数の処理装置によりアクセスされる共有資源と、前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、を備えるマルチシステムにおいて、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停方法であって、前記複数の処理装置のそれぞれにおいて、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、アクセス要求回数を算出し、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする。
【００１２】
また、本発明のマルチシステムは、複数の処理装置と、前記複数の処理装置によりアクセスされる共有資源と、前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停回路と、を備えるマルチシステムであって、前記複数の処理装置のそれぞれは、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、前記共有経路調停回路にアクセス要求回数を出力するアクセス要求先読みユニットを備え、前記共有経路調停回路は、前記複数の処理装置のそれぞれの前記アクセス要求先読みユニットから出力される前記アクセス要求回数を受け、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする。
【００１３】
分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数は意味がなくなるので破棄する。図示していないが、条件分岐命令などにおいて、条件の成立か否かによって２つのアドレスに分かれ、これらの２つの中で確率の高い一方の分岐先を予め予測して命令の先読みを行い、パイプラインの流れを円滑にする方式が使われる場合がある。しかしながら、それが失敗した場合に他の一方のアドレスに変更して命令読み出しをやり直すことになり、これを分岐予測の不成功と呼ぶことにする。分岐命令における２つのアドレスとは、該分岐命令の次のアドレスと、該分岐命令に含まれる情報から生成する分岐先アドレスである。一度計算した分岐アドレスや分岐履歴などは、分岐ターゲットバッファと呼ぶバッファに記憶しておき、次回の同一分岐命令実行からはこの記憶されたアドレスや分岐履歴に基づいて分岐先アドレスを予測する。
【００１４】
また、もっとも少ないアクセス要求回数が、複数の処理装置から出力される場合が起こり得るが、その場合には、もっとも少ないアクセス要求回数を出力する処理装置の間で、ラウンドロビン方式で共有経路を割当てる。
【発明の効果】
【００１５】
本発明によれば、マルチシステム全体でみた共有経路（バス）の平均許可待ち時間を、従来方式に比べて短縮することができ、例えばラウンドロビン方式に比べて３０〜５０％短縮することができる。
【発明を実施するための最良の形態】
【００１６】
前述のように、本発明は、共有経路の調停を行う構成であれば適用可能であるが、説明を簡単にするために、同じような機能の複数のプロセッサを共有バスを介して共有メモリに接続し、処理の進行に応じて、各プロセッサに随時処理を割当て、処理結果を統合して処理を進めるマルチプロセッサシステムを例として説明を行う。
【００１７】
図１は、本発明の実施例のマルチプロセッサシステムの全体構成を示すブロック図である。図示のように、本システムは、４個のプロセッサ１１−０〜１１−３と、バス調停回路１２と、共有バス１３と、共有メモリ１４と、を有する。上記の構成要素のうち、共有メモリ１４を除く部分は、１個のチップに実装されており、マルチコア方式のチップとなっている。なお、共有メモリ１４を同一チップ内に設けることも可能であり、逆に各プロセッサ１１−０〜１１−３及びバス調停回路１２を複数のチップに実装することも可能である。
【００１８】
プロセッサ１１−０〜１１−３は、すべて同じ構成で、通常のマイクロプロセッサと同様の構成を有しており、共有バス１３を介して共有メモリ１４と接続するプロセッサバス（アドレスバス及びデータバス）０〜３を有する。また、プロセッサ１１−０〜１１−３からバス調停回路１２にそれぞれバス要求信号Ｒ０〜Ｒ３及びバス要求回数信号Ｎ０〜Ｎ３が出力され、バス調停回路１２からプロセッサ１１−０〜１１−３にそれぞれバス許可信号Ａ０〜Ａ３が出力される。プロセッサ１１−ｉが、共有バス１３の占有権要求（バス要求）を行う時には、バス調停回路１２にバス要求信号Ｒｉをアサートする。プロセッサ１１−ｉからバス調停回路１２に出力されているバス要求回数信号Ｎｉの値は、プロセッサ１１−ｉがバス要求信号を発すると予定される回数である。バス調停回路１２は、バス許可信号Ａｉをアサートすることにより、プロセッサ１１−ｉに共有バス１３の占有権を与える。
【００１９】
同時に複数のプロセッサがバス要求を行った時には、バス調停回路１２はバス要求を行っているプロセッサのバス要求回数信号Ｎｉ（ｉは０〜３の２つ以上）を比較して、その値が最小であるプロセッサ１１−ｉに共有バス１３の占有許可（バス許可）を与える。以上のようにして、プロセッサ１１−ｉは、プロセッサバスｉ及び共有バス１３を介して共有メモリ１４にアクセスできるようになる。
【００２０】
例えば、プロセッサ１１−１及びプロセッサ１１−２がそれぞれバス要求信号Ａ１及びＡ２をアサートしてバス要求を行い、その時にバス要求回数信号Ｎ１＜バス要求回数信号Ｎ２であったとする。この場合、バス調停回路１２は、バス要求回数信号が小さいプロセッサ１１−１にバス許可信号Ａ１をアサートする。これにより、プロセッサ１１−１はプロセッサバス１及び共有バス１３を介して共有メモリ１４にアクセスできるようになる。
【００２１】
また、一個のプロセッサ１１−ｉのみがバス要求信号Ｒｉをアサートしており、他のプロセッサｊ（ｊ≠ｉ）はバス要求信号Ｒｊをアサートしていない時には、バス調停回路１２はバス許可信号Ａｉをアサートする。
【００２２】
システムにおける処理は、プロセッサ１１−０〜１１−３のうちのいずれか１つが、プログラムを共有メモリ１４にロードし、そのプログラムの１個又は複数のスレッドを各プロセッサに割当てる。各プロセッサは割当てられたスレッドを実行し、共有メモリ１４に演算の結果を書き込む。その後、いずれかのプロセッサが演算結果を利用して更に処理を進めるという具合に並列して処理を進める。
【００２３】
図２は、プロセッサ１１−ｉ（ｉ＝０〜３）の構成を示す図であり、プロセッサ１１−０、１１−１、１１−２、１１−３はすべて同じ構成を有する。図示のように、プロセッサ１１−ｉは、内部にプログラムカウンタ２２を有する命令フェッチユニット２１と、プログラムを記憶する命令キャッシュ２３と、実行するために命令キャッシュ２３から読み出した命令を一時的に保持する命令レジスタ２４と、命令を解読する命令デコードユニット２５と、共有メモリ１４からロードした実行する処理に関係する部分のデータを記憶するデータキャッシュ２６と、命令デコードユニット２５で解読した命令に基づいて発生される制御信号を一時的に記憶する制御レジスタ２７と、共有バスを使用する時にバス調停回路１２にバス要求信号Ｒｉを出力すると共にバス調停回路１２からバス許可信号Ａｉを受けるバスステートコントローラ２８と、発生すると予測されるバス要求信号の発生回数を算出してバス要求回数信号Ｎｉを出力するバス要求先読みユニット２９と、を有する。
【００２４】
命令キャッシュ２３は、所定の記憶容量を有し、実行するプログラムを記憶しているが、実行するプログラムが命令キャッシュ２３に記憶されていない時には、共有メモリ１４にアクセスして所定の記憶容量分のプログラムをロードして記憶する。この時には、共有メモリ１４にアクセスするため共有バスの占有権を要求して獲得する必要があり、１回のアクセスでロードするプログラムの量は一定である。
【００２５】
データキャッシュ２６は、所定の記憶容量を有し、その一部は実行するプログラムに関係する所定量のデータを共有メモリ１４からロードして記憶し、他の部分は処理結果などを一時的に記憶する。関係するデータがデータキャッシュ２６に存在しない時には、共有メモリ１４にアクセスして所定の記憶容量分のデータをロードして記憶する。また、１回の処理が終了した時や処理結果が所定量以上になった時には、共有メモリ１４にアクセスして処理結果を共有メモリ１４に転送する。これらの時には、共有メモリ１４にアクセスするため共有バスの占有権を要求して獲得する必要があり、１回のアクセスでロード及び転送するプログラムの量は一定である。
【００２６】
ここでは、説明を簡単にするために、データキャッシュ２６と共有メモリ１４との間で、データのロード及び転送に関するバス要求のみを先読みし、共有メモリ１４から命令キャッシュ２３へのプログラムのロードに関するバス要求は先読みの対象としないが、これを含めることも可能である。
【００２７】
次に図２の回路構成における動作を説明する。まず、プロセッサ１１−ｉ（ｉ＝０〜３）の命令フェッチユニット２１のプログラムカウンタ２２から命令キャッシュ２３に命令アドレスが供給される。命令アドレスで指定された命令が命令キャッシュ２３に保存されている場合、命令キャッシュ２３から命令レジスタ２４に命令がフェッチされる。保存されていない場合、共有メモリ１４から命令キャッシュ２３と命令レジスタ２４に、共有バス１３とプロセッサバスｉを介して命令がフェッチされる。
【００２８】
次に、命令レジスタ２４から命令デコードユニット２５に命令が供給されて、命令デコードユニット２５が命令のデコードを行う。命令デコードユニット２５は、命令のデコード時に、その命令がメモリアクセスを行うかどうかを調べる。メモリアクセスを行う場合、アクセス対象のデータがデータキャッシュ２６に保存されているかどうかを調べる目的で、命令デコードユニット２５からデータキャッシュ２６にデータアドレスが供給される。アクセス対象のデータがデータキャッシュ２６に保存されている場合には、データキャッシュ２６から命令デコードユニット２５に供給されているバス要求起動信号がネゲート（無効に）される。保存されていない場合には、バス要求起動信号がアサート（有効に）される。命令デコードユニット２５から制御レジスタ２７に、バス要求起動信号を含む制御信号群が供給される。なお、アクセス対象のデータがデータキャッシュに保存されていない場合には、バス要求起動信号がアサートされてから適当なクロックサイクル後に、共有メモリ１４からデータキャッシュ２６に、またはデータキャッシュ２６から共有メモリ１４に、共有バス１３とプロセッサバスｉを介してデータが転送される。
【００２９】
次に、制御レジスタ２７からバスステートコントローラ２８にバス要求起動信号が供給される。バス要求起動信号がアサートされている場合、バスステートコントローラ２８からバス調停回路１２に供給されているバス要求信号Ｒｉが適当なクロックサイクル後にアサートされる。バス要求起動信号がネゲートされている場合、バス要求信号Ｒｉはネゲートされたままである。
【００３０】
一方、命令フェッチユニット２１のプログラムカウンタ２２からバス要求先読みユニット２９に命令アドレスが供給され、制御レジスタ２７からバス要求先読みユニット２９にバス要求起動信号が供給され、バス調停回路１２からバス要求先読みユニット２９にバス許可信号Ａｉが供給される。バス要求先読みユニット２９は、命令アドレスとバス要求起動信号とバス許可信号Ａｉに基づいてプロセッサｉの所定時間内に生じると予測されるバス要求回数を計算し、得られた回数をバス要求回数信号Ｎｉとしてバス調停回路１２に供給する。
【００３１】
図３は、バス調停回路１２の構成図である。図示のように、バス調停回路１２は、最小値選択回路３１と、４個の一致回路３２−０〜３２−３と、４個のＡＮＤゲート３３−０〜３３−３と、重複除去回路３４と、を有する。最小値選択回路３１は、プロセッサ１１−０〜１１−３から出力されるバス要求回数信号Ｎ０〜Ｎ３とバス要求信号Ｒ０〜Ｒ３が入力され、バス要求信号ｉがアサートされているプロセッサ１１−ｉのバス要求回数信号Ｎ０〜Ｎ３のうちで値が最小のものを選択し、最小値信号として一致回路３２−０〜３２−３に出力する。ただし、複数のバス要求回数信号が最小値をとる場合もある。この場合、最小値をとっている複数のバス要求回数信号をラウンドロビン方式によって、バス優先権が特定のプロセッサに偏らないようにする。
【００３２】
一致回路３２−ｉ（ｉ＝０〜３）は、それぞれバス要求回数信号Ｎｉの値と最小値選択回路３１から供給される最小値の値が一致するかを判定し、一致する場合には一致信号Ｂｉをアサートし、一致しない場合はＢｉをネゲートする。
【００３３】
ＡＮＤゲート３３−ｉ（ｉ＝０〜３）は、それぞれ一致信号Ｂｉがアサートされ、かつバス要求信号Ｒｉがアサートされた場合に、バス許可候補信号Ｃｉをアサートし、それ以外の場合にはネゲートする。
【００３４】
従って、プロセッサ１１−ｉがバス要求信号Ｒｉをアサートしてバス要求を行った時に、バス要求回数信号Ｎｉの値がすべてのバス要求回数信号Ｎ０〜Ｎ３の中で最小値であれば、バス許可候補信号Ｃｉがアサートされる。
【００３５】
重複除去回路３４は、バス許可候補信号Ｃ０〜Ｃ３が入力され、複数個のバス許可候補信号がアサートされている場合はその中から１個のバス許可候補信号Ｃｉを選択してバス許可信号Ａｉをアサートする。一個のバス許可候補信号Ｃｉだけがアサートされている場合はそれに対応するバス許可信号Ａｉをアサートする。バス許可候補信号Ｃ０〜Ｃ３がすべてネゲートされている場合は、バス許可信号Ａ０〜Ａ３をすべてネゲートする。バス許可信号Ａ０〜Ａ３は、それぞれ重複除去回路３４からプロセッサ１１−０〜１１−３に供給される。
【００３６】
次に、プロセッサのバス要求先読みユニット２９のより詳細な構成を説明する。
【００３７】
図４は、バス要求先読みユニット２９の構成図である。図示のように、バス要求先読みユニット２９は、バス要求解析回路４１と、バス許可解析回路４２と、未来のバス要求カウンタ４３と、長期未許可検出回路４４と、マルチプレクサ４５と、を有する。
【００３８】
バス要求解析回路４１は、命令フェッチユニット２１から命令アドレスを受け、制御レジスタ２７からバス要求起動信号を受け、未来のバス要求カウンタ４３にカウントアップ信号を供給する。バス要求解析回路４１は、命令アドレスとバス要求起動信号に基づき、命令フェッチユニット２１でフェッチされ命令デコードユニット２５でデコードされた命令がバス要求を起動するかどうかを解析し、起動する場合に限りカウントアップ信号をアサートする。従って、プロセッサ１１−ｉが命令キャッシュ２３又はメモリからフェッチしデコードした命令がバス要求を起動する場合、バス先読みユニット２９の未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数が１だけ増加する。
【００３９】
バス許可解析回路４２は、バス調停回路１２からバス許可信号Ａｉが供給され、未来のバス要求カウンタ４３にカウントダウン信号が供給される。バス許可解析回路４２は、バス許可信号Ａｉに基づいてプロセッサ１１−ｉがバス調停回路１２からバス許可を与えられたかどうかを解析し、与えられた場合に限り１クロックサイクル期間だけカウントダウン信号をアサートする。従って、プロセッサ１１−ｉがバス調停回路１２からバス許可を与えられた場合、バス要求先読みユニット２９の未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。
【００４０】
未来のバス要求カウンタ４３からマルチプレクサ４５に未来のバス要求回数候補信号が供給される。未来のバス要求回数候補信号の値は、未来のバス要求カウンタ４３が保持する値であり、カウントアップ信号がアサートされているとクロックエッジに同期して１だけ増加し、カウントダウン信号がアサートされていると１だけ減少する。カウントアップ信号とカウントダウン信号の両方がアサートされている場合は、値は変化しない。
【００４１】
長期未許可検出回路４４は、制御レジスタ２７からバス要求起動信号が供給され、バス調停回路１２からバス許可信号Ａｉが供給され、マルチプレクサ４５に長期未許可信号を供給する。マルチプレクサ４５は、バス調停回路１２にバス要求回数信号Ｎｉを供給する。長期未許可検出回路４４は、バス要求起動信号とバス許可信号Ａｉに基づき、プロセッサ１１−ｉがバス要求を起動してから長期間バス許可を受けていないかどうかを判定し、長期間バス許可を受けていない場合に限り、長期未許可信号をアサートする。マルチプレクサ４５からバス調停回路１２に供給されるバス要求回数信号Ｎｉの値は、長期未許可信号がネゲートされている場合は未来のバス要求回数候補信号の値に一致し、長期未許可信号がアサートされている場合は−１になる。
【００４２】
以上のようにして、プロセッサ１１−ｉのバス要求先読みユニット２９は、命令フェッチユニット２１から供給される命令アドレスと制御レジスタ２７から供給されるバス要求起動信号とバス調停回路１２から供給されるバス許可信号Ａｉに基づきプロセッサ１１−ｉのバス要求回数を先読みし、未来のバス要求カウンタ４３に保持する。そして、プロセッサ１１−ｉのバス要求回数信号Ｎｉが、バス要求先読みユニット２９からバス調停回路１２に供給され、バス調停に活用される。ただし、プロセッサ１１−ｉが長期間バス許可を受けていない場合は、バス要求先読みユニット２９からバス調停回路１２に供給されるバス要求回数信号Ｎｉの値が−１となり、プロセッサ１１−ｉが優先的にバス許可を受けられるようになる。
【００４３】
なお、図示していないが、バス要求先読みユニット２９がプロセッサ１１−ｉのバス要求回数を先読みして分岐命令であることが判明した時には、該分岐命令実行時に分岐予測が不成功の場合に限って未来のバス要求カウンタ４３の値をリセットする。
【００４４】
また、ここでは、各プロセッサは"Out of order"発行を行い、命令キャッシュのヒット率は従来のプロセッサと同様に十分に高いとする。この前提の下で、例えば、プロセッサ１１−０が共有メモリ１４をアクセスしているとする。メモリアクセスはキャッシュアクセスに比べて長時間を要する。そのため、プロセッサ１１−０が共有メモリ１４をアクセスしている間に、他のプロセッサ１１−１〜１１−３は命令キャッシュから後続する命令を複数個フェッチしてデコードできる。これにより、それぞれのプロセッサにおける後続命令のバス要求信号の発生を捕捉できる。従って、命令の先読みは、後続命令を命令キャッシュからフェッチできる限り、共有メモリのアクセス期間が終了するまで続く。
【００４５】
図５は、バス要求解析回路４１の構成図である。図示のように、バス要求解析回路４１は、旧プログラムカウンタ５１と、不一致回路５２と、シフトレジスタ５３と、ＡＮＤゲート５４と、を有する。
【００４６】
命令フェッチユニット２１から旧プログラムカウンタ５１に命令アドレスが供給される。旧プログラムカウンタ５１は、レジスタであり、入力として供給されている命令アドレスをクロックエッジに同期してロードする。命令フェッチユニット２１から不一致回路５２にも命令アドレスが供給され、旧プログラムカウンタ５１から不一致回路５２に旧命令アドレスが供給される。不一致回路５２からシフトレジスタ５３の最上位ビットに命令フェッチ完了信号が供給される。不一致回路５２は、入力として供給される命令アドレスと旧命令アドレスが一致しない場合に限り命令フェッチ完了信号をアサートする。命令フェッチユニット２１が命令のフェッチを完了すると、プログラムカウンタ２２が保持する命令アドレスが更新されるので、命令フェッチユニット２１から不一致回路５２に供給される命令アドレスと旧プログラムカウンタ５１から不一致回路５２に供給される旧命令アドレスが一致しなくなり、不一致回路５２からシフトレジスタ５３の最上位ビットに供給される命令フェッチ完了信号がアサートされる。シフトレジスタ５３はクロックエッジに同期して右に１ビットシフトされる。この時、最上位ビットに命令フェッチ完了信号の値がロードされる。シフトレジスタ５３の最下位ビットからＡＮＤゲート５４に命令デコード完了信号が供給され、制御レジスタ２７からＡＮＤゲート５４にバス要求起動信号が供給される。シフトレジスタ５３のビット数は、命令フェッチユニット２１が命令のフェッチを完了してから命令デコードユニット２５がその命令のデコードを完了するまでに要するクロックサイクル数である。シフトレジスタ５３のビット数をこのように定めることにより、任意の命令について、命令デコード完了信号がアサートされるタイミングとバス要求起動信号がアサートまたはネゲートされるタイミングが一致する。また、命令デコード完了信号とバス要求起動信号が入力として供給されるＡＮＤゲート５４から、未来のバス要求カウンタ４３にカウントアップ信号が供給される。従って、プロセッサ１１−ｉが命令キャッシュ２３またはメモリからフェッチしデコードした命令がバス要求を起動する命令である場合、その命令について命令デコード完了信号とバス要求起動信号がアサートされ、カウントアップ信号がアサートされ、未来のバス要求カウンタ４３の値、すなわちプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ増加する。
【００４７】
図６は、バス許可解析回路４２の構成図である。図示のように、バス許可解析回路４２は、旧バス許可６１と、ＡＮＤゲート６２と、インバータ６３と、を有する。
【００４８】
バス調停回路１２からＡＮＤゲート６２と旧バス許可６１にバス許可信号Ａｉが供給される。旧バス許可６１は、１ビットのレジスタであり、入力として供給されるバス許可信号Ａｉの値をクロックエッジに同期してロードする。旧バス許可６１からインバータ６３に旧バス許可信号が供給され、インバータ６３からＡＮＤゲート６２に旧バス許可信号の反転信号が供給される。ＡＮＤゲート６２から未来のバス要求カウンタ４３にカウントダウン信号が供給される。従って、バス調停回路１２からプロセッサ１１−ｉに供給されるバス許可信号Ａｉがネゲートされていて、適当なクロックサイクル後にバス許可信号Ａｉがアサートされた時に、アサートされた直後の１クロックサイクル間だけ、バス許可解析回路４２から未来のバス要求カウンタ４３に供給されるカウントダウン信号がアサートされ、未来のバス要求カウンタ４３が保持するプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。このようにして、プロセッサ１１−ｉがバス許可を与えられると、プロセッサ１１−ｉからバス調停回路１２に供給されるプロセッサ１１−ｉのバス要求回数信号Ｎｉが１だけ減少する。
【００４９】
図７は、長期未許可検出回路４４の構成図である。図示のように、長期未許可検出回路４４は、インバータ７１と、ＡＮＤゲート７２と、未許可期間カウンタ７３と、長期間レジスタ７４と、比較回路７５と、を有する。
【００５０】
制御レジスタ２７からＡＮＤゲート７２にバス要求起動信号が供給される。バス調停回路１２からインバータ７１にバス許可信号Ａｉが供給される。インバータ７１からＡＮＤゲート７２にバス許可信号Ａｉの反転信号／Ａｉが供給される。ＡＮＤゲート７２から未許可期間カウンタ７３にカウントアップ信号が供給される。バス調停回路１２から未許可期間カウンタ７３にバス許可信号Ａｉがリセット信号として供給される。従って、プロセッサ１１−ｉがバス要求起動信号をアサートしてから、バス調停回路１２によってバス許可信号Ａｉがアサートされるまでの間、未許可期間カウンタ７３の値は上限値に達するまでカウントアップされ続ける。バス調停回路１２によってバス許可信号Ａｉがアサートされると、未許可期間カウンタ７３はリセットされる。未許可期間カウンタ７３から比較回路７５に未許可期間信号が供給され、長期間レジスタ７４から比較回路７５に長期間信号が供給される。比較回路７５からバス要求先読みユニット２９のマルチプレクサ４５へ長期間未許可信号が供給される。比較回路７５は、未許可期間信号の値と長期間信号の値を比較し、未許可期間信号の値が長期間信号の値以上である場合に限り、長期未許可信号をアサートする。なお、長期間レジスタ７４にはあらかじめ長期間を表す値が設定されているものとする。
【００５１】
図８は、バス調停回路１２の最小値選択回路３１の構成図である。図示のように、最小値選択回路３１は、比較回路８１、８２、８７と、マルチプレクサ制御回路８３、８４と、マルチプレクサ８５、８６、８８と、を有する。
【００５２】
比較回路８１は、ａ入力でプロセッサ１１−０のバス要求回数信号Ｎ０を、ｂ入力でプロセッサ１１−１のバス要求回数信号Ｎ１を受け、Ｎ０＜Ｎ１であれば”１”を、Ｎ０＞Ｎ１であれば”０”を、比較結果Ｆ０として出力する。マルチプレクサ８３は、比較回路８１の出力する比較結果Ｆ０及びバス要求信号Ｒ０とＲ１を受け、Ｒ０とＲ１に応じて図９に示すような制御信号Ｇ０を出力する組合せ回路である。すなわち、Ｒ０とＲ１が”０”であれば”２”を、Ｒ０が”０”でＲ１が”１”であれば”０”を、Ｒ０が”１”でＲ１が”０”であれば”１”を、Ｒ０とＲ１が”１”であれば比較結果Ｆ０（０又は１）の値を出力する。マルチプレクサ８５は、制御信号Ｇ０、Ｎ０、Ｎ１及び上限値を受けて、制御信号Ｇ０の値に応じて、Ｎ０、Ｎ１及び上限値のいずれかを出力Ｈ０として出力する。上限値は、バス要求回数信号Ｎｉのとり得る上限値である。すなわち、Ｇ０が”０”であればＮ１を、Ｇ０が”１”であればＮ０を、”２”であれば上限値をＨ０として出力する。従って、Ｒ０とＲ１が”０”であれば上限値が、Ｒ０が”０”でＲ１が”１”であればＮ１が、Ｒ０が”１”でＲ１が”０”であればＮ０が出力され、Ｒ０とＲ１が”１”の時には、Ｎ０＜Ｎ１であればＮ０が、Ｎ０＞Ｎ１であればＮ１が、Ｈ０として出力される。
【００５３】
比較回路８２、マルチプレクサ制御回路８４及びマルチプレクサ８６は、上記の比較回路８１、マルチプレクサ制御回路８３及びマルチプレクサ８５に対応し、対象となる信号がＮ２、Ｎ３及びＲ２、Ｒ３である以外は同じである。従って、Ｒ２とＲ３が”０”であれば上限値が、Ｒ２が”０”でＲ３が”１”であればＮ３が、Ｒ２が”１”でＲ３が”０”であればＮ２が出力され、Ｒ２とＲ３が”１”の時には、Ｎ２＜Ｎ３であればＮ２が、Ｎ２＞Ｎ３であればＮ３が、Ｈ２として出力される。
【００５４】
比較回路８７は、ａ入力でＨ０を、ｂ入力でＨ２を受け、Ｈ０＜Ｈ１であれば”０”を、Ｈ０＞Ｈ１であれば”１”を、比較結果Ｆ１として出力する。マルチプレクサ８８は、Ｈ０とＨ２を受け、Ｆ１が”０”であればＨ０を、Ｆ１が”１”であればＨ１を最小値として出力する。
【００５５】
以上のようにして、最小値選択回路３１は、Ｒ０〜Ｒ３のうちに有効な信号（”１”の信号）があれば、Ｎ０〜Ｎ３のうち有効な信号に対応する信号のうちの最小の値を出力し、Ｎ０〜Ｎ３のいずれも有効でなければ上限値を出力する。
【００５６】
ここで、図３に戻り、一致回路３２−０〜３２−３は、それぞれバス要求回数信号Ｎｉの値と最小値選択回路３１から供給される最小値の値が一致するかを判定し、一致する場合には一致信号Ｂｉをアサートし、一致しない場合はＢｉをネゲートする。ＡＮＤゲート３２−０〜３３−３は、それぞれ一致信号Ｂｉがアサートされ、かつバス要求信号Ｒｉがアサートされた場合に、バス許可候補信号Ｃｉをアサートし、それ以外の場合にはネゲートする。従って、プロセッサ１１−ｉがバス要求信号Ｒｉをアサートしてバス要求を行った時に、バス要求回数信号Ｎｉの値がすべてのバス要求回数信号Ｎ０〜Ｎ３の中で最小値であれば、バス許可候補信号Ｃｉがアサートされる。
【００５７】
図１０は、重複除去回路３４の構成図である。図示のように、重複除去回路３４は、選択回路９１−０〜９１−３と、レジスタＳ９１−０〜９１−３と、ＡＮＤゲート９３−０〜９３−３と、を有する。
【００５８】
図３に示したバス調停回路１２のＡＮＤゲート３３−０〜３３−３から出力されるバス許可候補信号Ｃ０〜Ｃ３が、図示のように選択回路９１−０〜９１−３の４個のｃ入力に順にずらしながら入力される。また、レジスタＳ９２−０〜９２−３の出力Ｄ０〜Ｄ３が、選択回路９１−０〜９１−３の４個のｄ入力に順にずらしながら入力される。これを一般化して表現すると、ｉ＝０，１，２，３とし、ｘ％ｙの表記はｘをｙで除した時の余りとすると、Ｃｉが、選択回路ｉのｃ０入力に、選択回路（ｉ＋１）％４のｃ３入力に、選択回路（ｉ＋２）％４のｃ２入力に、選択回路（ｉ＋３）％４のｃ１入力に、入力される。また、１ビットのレジスタＳ９２−ｉの出力Ｄｉが、選択回路ｉのｄ０入力に、選択回路（ｉ＋１）％４のｄ３入力に、選択回路（ｉ＋２）％４のｄ２入力に、選択回路（ｉ＋３）％４のｄ１入力に、入力される。選択回路ｉは、入力ｃ０〜ｃ３及びｄ０〜ｄ３に応じて図１１に示すような選択信号Ｅｉを出力する組合せ回路である。
【００５９】
１ビットのレジスタＳ９２−ｉは、選択回路ｉから出力される選択信号Ｅｉの値をクロックエッジに同期してロードする。また、レジスタＳ９２−ｉの値は、バス調停回路１２の初期化時に、レジスタＳ９２−０＝１、レジスタＳ９２−ｉ＝０（ｉ≠０）に設定されるものとする。図１１に示すような選択信号Ｅｉを出力する選択回９１−０〜９１−３からレジスタＳ９１−０〜９１−３に供給される選択信号Ｅ０〜Ｅ３のうちで、同時にアサートされる信号は１つだけである。
【００６０】
バス調停回路１２のＡＮＤゲート３３−ｉから重複除去回路３４のＡＮＤゲート９３−ｉにバス許可候補信号Ｃｉが供給され、レジスタＳ９２−ｉから重複除去回路３４のＡＮＤゲート９３−ｉに出力Ｄｉが供給され、重複除去回路３４のＡＮＤゲート９３−ｉからプロセッサ１１−ｉにバス許可信号Ａｉが供給される。従って、バス許可候補信号Ｃｉがアサートされている場合、選択回路ｉが選択信号Ｅｉをアサートし、その値がレジスタＳ９２−ｉにロードされて出力Ｄｉがアサートされた場合に限り、プロセッサ１１−ｉへ供給されるバス許可信号Ａｉがアサートされる。選択回路９１−０〜９１−３からレジスタＳ９２−０〜９２−３に供給される選択信号Ｅ０〜Ｅ３のうちで同時にアサートされる信号は１つだけなので、バス許可候補信号Ｃ０〜Ｃ３のうち２つ以上が同時にアサートされていても、プロセッサ１１−０〜１１−３へ供給されるバス許可信号Ａ０〜Ａ３のうちアサートされる信号は１つだけとなる。
【００６１】
以上本実施例のマルチシステムの構成を説明したが、次に本発明のマルチシステムと従来のラウンドロビン方式のマルチシステムにおける許可待ち時間の比較を行う。
【００６２】
図１２は、従来より一般的に用いられてきたラウンドロビン方式によるバス調停方式と本発明によるバス調停方式における平均許可待ち時間を比較する図であり、（Ａ）はラウンドロビン方式の場合を、（Ｂ）は本発明の場合を示し、同じ条件での比較である。
【００６３】
いずれの場合も、プロセッサはＰ１〜Ｐ４の４個で、ある時点において、プロセッサＰ１〜Ｐ４で、４、２、１、１回の共有メモリアクセスが必要であった場合を示している。ラウンドロビン方式の場合、アクセスはＰ１からＰ４の順に割当てられ、その後再びＰ１にバス権が割当てられる。図示のように、すべてのアクセスが終了するまで、Ｐ１は４期間、Ｐ２は４期間、Ｐ３は２期間、Ｐ４は３期間待つ必要があり、システム全体の平均許可待ち時間は３．２５となる。
【００６４】
これに対して、本発明の方式では、バス要求回数の小さいＰ３及びＰ４を優先するため、Ｐ１は４期間、Ｐ２は４期間、Ｐ３は０期間、Ｐ４は１期間待つ必要があり、システム全体の平均許可待ち時間は１．７５となる。
【００６５】
以上のように、本発明のバス調停方式では、将来のバス要求回数のもっとも少ないプロセッサにバス権を優先して与えることによってシステム全体としてのバスの平均許可待ち時間を低くできるので、システムの性能を向上できる。
【産業上の利用可能性】
【００６６】
本発明は、バスなどのアクセス経路を共有し、アクセス経路を割当てる必要のあるマルチプロセッサシステムであればどのようなものにも適用可能である。
【図面の簡単な説明】
【００６７】
【図１】本発明の実施例のマルチプロセッサシステムの全体構成を示す図である。
【図２】実施例のマルチプロセッサシステムにおけるプロセッサの構成を示す図である。
【図３】実施例のバス調停回路の構成を示す図である。
【図４】バス要求先読みユニットの構成を示す図である。
【図５】バス要求解析回路の構成を示す図である。
【図６】バス許可解析回路の構成を示す図である。
【図７】長期未許可検出回路の構成を示す図である。
【図８】最小値選択回路の構成を示す図である。
【図９】最小値選択回路で使用するマルチプレクサ制御回路の入力と出力の関係を示す真理値表である。
【図１０】重複除去回路の構成を示す図である。
【図１１】重複除去回路で使用する選択回路の入力と出力の関係を示す真理値表である。
【図１２】本発明の従来例に対する効果を説明する図である。
【符号の説明】
【００６８】
１１−０〜１１−３，１１−ｉ プロセッサ
１２ バス調停回路
１３ 共有バス
１４ 共有メモリ
２９ バス要求先読みユニット
３１ 最小値選択回路
【特許請求の範囲】
【請求項１】
複数の処理装置と、
前記複数の処理装置によりアクセスされる共有資源と、
前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、を備えるマルチシステムにおいて、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停方法であって、
前記複数の処理装置のそれぞれにおいて、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、アクセス要求回数を算出し、
前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする共有経路調停方法。
【請求項２】
分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数を破棄する請求項１に記載の共有経路調停方法。
【請求項３】
もっとも少ない前記アクセス要求回数が、複数の前記処理装置から出力されている時には、当該複数の前記処理装置の間でラウンドロビン方式で前記共有経路を割当てる請求項１に記載の共有経路調停方法。
【請求項４】
複数の処理装置と、
前記複数の処理装置によりアクセスされる共有資源と、
前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、
前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停回路と、を備えるマルチシステムであって、
前記複数の処理装置のそれぞれは、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、前記共有経路調停回路にアクセス要求回数を出力するアクセス要求先読みユニットを備え、
前記共有経路調停回路は、前記複数の処理装置のそれぞれの前記アクセス要求先読みユニットから出力される前記アクセス要求回数を受け、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数の少ない処理装置に前記共有経路を割当てることを特徴とするマルチシステム。
【請求項５】
前記アクセス要求先読みユニットは、分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数をリセットする請求項４に記載のマルチシステム。
【請求項６】
前記共有経路調停回路は、もっとも少ない前記アクセス要求回数が、複数の前記処理装置から出力されている時には、当該複数の前記処理装置の間でラウンドロビン方式で前記共有経路を割当てる請求項４に記載のマルチシステム。
【請求項１】
複数の処理装置と、
前記複数の処理装置によりアクセスされる共有資源と、
前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、を備えるマルチシステムにおいて、前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停方法であって、
前記複数の処理装置のそれぞれにおいて、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、アクセス要求回数を算出し、
前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数のもっとも少ない処理装置に前記共有経路を割当てることを特徴とする共有経路調停方法。
【請求項２】
分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数を破棄する請求項１に記載の共有経路調停方法。
【請求項３】
もっとも少ない前記アクセス要求回数が、複数の前記処理装置から出力されている時には、当該複数の前記処理装置の間でラウンドロビン方式で前記共有経路を割当てる請求項１に記載の共有経路調停方法。
【請求項４】
複数の処理装置と、
前記複数の処理装置によりアクセスされる共有資源と、
前記複数の処理装置が前記共有資源に共通にアクセスするための共有経路と、
前記共有経路の前記複数の処理装置への割当てを制御する共有経路調停回路と、を備えるマルチシステムであって、
前記複数の処理装置のそれぞれは、当該処理装置で実行する予定の処理において前記共有資源へのアクセスを要求する回数をカウントして、前記共有経路調停回路にアクセス要求回数を出力するアクセス要求先読みユニットを備え、
前記共有経路調停回路は、前記複数の処理装置のそれぞれの前記アクセス要求先読みユニットから出力される前記アクセス要求回数を受け、前記複数の処理装置から前記共有経路への割当てを要求された時には、前記アクセス要求回数の少ない処理装置に前記共有経路を割当てることを特徴とするマルチシステム。
【請求項５】
前記アクセス要求先読みユニットは、分岐命令実行時には、分岐予測が不成功の場合に限って算出した前記アクセス要求回数をリセットする請求項４に記載のマルチシステム。
【請求項６】
前記共有経路調停回路は、もっとも少ない前記アクセス要求回数が、複数の前記処理装置から出力されている時には、当該複数の前記処理装置の間でラウンドロビン方式で前記共有経路を割当てる請求項４に記載のマルチシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００７−２１９８２１（Ｐ２００７−２１９８２１Ａ）
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願番号】特願２００６−３９４６２（Ｐ２００６−３９４６２）
【出願日】平成１８年２月１６日（２００６．２．１６）
【出願人】（３９６０２３９９３）株式会社半導体理工学研究センター (150)
【Ｆターム（参考）】
【公開日】平成１９年８月３０日（２００７．８．３０）
【国際特許分類】
【出願日】平成１８年２月１６日（２００６．２．１６）
【出願人】（３９６０２３９９３）株式会社半導体理工学研究センター (150)
【Ｆターム（参考）】
[ Back to top ]