JP3068427B2 - メッセージ制御装置 - Google Patents
メッセージ制御装置Info
- Publication number
- JP3068427B2 JP3068427B2 JP7055665A JP5566595A JP3068427B2 JP 3068427 B2 JP3068427 B2 JP 3068427B2 JP 7055665 A JP7055665 A JP 7055665A JP 5566595 A JP5566595 A JP 5566595A JP 3068427 B2 JP3068427 B2 JP 3068427B2
- Authority
- JP
- Japan
- Prior art keywords
- message
- buffer
- response
- request
- entries
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 230000004044 response Effects 0.000 claims description 106
- 239000000872 buffer Substances 0.000 claims description 89
- 238000001514 detection method Methods 0.000 claims description 6
- 238000010586 diagram Methods 0.000 description 6
- 238000000034 method Methods 0.000 description 4
- 241001522296 Erithacus rubecula Species 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
Landscapes
- Multi Processors (AREA)
Description
【０００１】
【産業上の利用分野】本発明は、メッセージ制御装置に
関し、特に複数の装置が共通バスに接続されたシステム
において、共通バスへ複数の種類のリクエストを送信す
る複数のバッファを備えるメッセージ制御装置に関す
る。
関し、特に複数の装置が共通バスに接続されたシステム
において、共通バスへ複数の種類のリクエストを送信す
る複数のバッファを備えるメッセージ制御装置に関す
る。
【０００２】
【従来の技術】従来この種の技術では、他装置に対する
リクエスト要求を保持する先入れ先出しバッファ（以下
「ＦＩＦＯ」という）である要求ＦＩＦＯと他装置から
のリクエストに応答するための応答ＦＩＦＯという２つ
のＦＩＦＯを有して構成されている。たとえば、特開昭
５−１８９３９１号公報には多段スイッチネットワーク
によって結合されたシステムの技術が記載されている。
リクエスト要求を保持する先入れ先出しバッファ（以下
「ＦＩＦＯ」という）である要求ＦＩＦＯと他装置から
のリクエストに応答するための応答ＦＩＦＯという２つ
のＦＩＦＯを有して構成されている。たとえば、特開昭
５−１８９３９１号公報には多段スイッチネットワーク
によって結合されたシステムの技術が記載されている。
【０００３】図４を参照すると、上記従来技術では、複
数のプロセッサメモリエレメント（以下「ＰＭＥ」とい
う）７０１，７０２，７０３，７０４が、他段スイッチ
交換網７０５を通じて接続される。多段スイッチ交換網
７０５は、複数のステージ７１１，７１２からなり、各
々のステージはＰＭＥと同数のスイッチ７２１〜７２４
から構成される。各々のスイッチは、要求メッセージを
ストアする要求ＦＩＦＯ７３１と応答メッセージをスト
アする応答ＦＩＦＯ７３２、要求ＦＩＦＯと応答ＦＩＦ
Ｏから次に送信されるメッセージを選択するメッセージ
セレクタ７３３を備える。従来技術は、要求ＦＩＦＯと
応答ＦＩＦＯの２種類のＦＩＦＯを備え、応答ＦＩＦＯ
内のメッセージを常に優先的に次段に送信することによ
り、デッドロックが発生しないように制御している。
数のプロセッサメモリエレメント（以下「ＰＭＥ」とい
う）７０１，７０２，７０３，７０４が、他段スイッチ
交換網７０５を通じて接続される。多段スイッチ交換網
７０５は、複数のステージ７１１，７１２からなり、各
々のステージはＰＭＥと同数のスイッチ７２１〜７２４
から構成される。各々のスイッチは、要求メッセージを
ストアする要求ＦＩＦＯ７３１と応答メッセージをスト
アする応答ＦＩＦＯ７３２、要求ＦＩＦＯと応答ＦＩＦ
Ｏから次に送信されるメッセージを選択するメッセージ
セレクタ７３３を備える。従来技術は、要求ＦＩＦＯと
応答ＦＩＦＯの２種類のＦＩＦＯを備え、応答ＦＩＦＯ
内のメッセージを常に優先的に次段に送信することによ
り、デッドロックが発生しないように制御している。
【０００４】
【発明が解決しようとする課題】上述の従来技術では、
デッドロック問題を解決するため、応答メッセージを優
先的に次の段に送信しているため、スイッチ７２１〜７
２４に、先に到達した要求メッセージが後に到達した応
答メッセージに追い越される現象が発生し、要求メッセ
ージの待ちが大きくなるため、一度負荷が上昇し、スイ
ッチ内の応答メッセージが増加することにより、システ
ムの新規要求メッセージが停滞し、負荷がある程度低下
するまでの間は、システム性能の低下が発生する。
デッドロック問題を解決するため、応答メッセージを優
先的に次の段に送信しているため、スイッチ７２１〜７
２４に、先に到達した要求メッセージが後に到達した応
答メッセージに追い越される現象が発生し、要求メッセ
ージの待ちが大きくなるため、一度負荷が上昇し、スイ
ッチ内の応答メッセージが増加することにより、システ
ムの新規要求メッセージが停滞し、負荷がある程度低下
するまでの間は、システム性能の低下が発生する。
【０００５】これを解決するためには、メッセージを各
スイッチに到達した順に次の段に送信する必要がある。
これが実現できれば、負荷にかかわらず一定の性能を実
現可能となる。しかし、メッセージを到達順に処理する
と、以下のようにデッドロックが生じるおそれがある。
スイッチに到達した順に次の段に送信する必要がある。
これが実現できれば、負荷にかかわらず一定の性能を実
現可能となる。しかし、メッセージを到達順に処理する
と、以下のようにデッドロックが生じるおそれがある。
【０００６】図５を参照すると、ＣＰＵ１とＣＰＵ２と
の間でデッドロックが発生している状態を示した図にお
いて、例えばＲＥＱ１２とあるのはＣＰＵ１からＣＰＵ
２へのリクエスト要求を意味し、また、ＲＥＳ１２とあ
るのはＣＰＵ１からＣＰＵ２への応答を意味する。応答
ＦＩＦＯ７３２および７４２はエントリが全てリクエス
トで埋まっており、新たなリクエストを受け付けること
ができない状態になっている。しかも要求ＦＩＦＯ７３
１および７４１の要求の方が先に入力されたものである
ため、この要求が出力されてしまわないと応答ＦＩＦＯ
７３２または７４２から出力できない。一方、要求ＦＩ
ＦＯは互いにＣＰＵ１またはＣＰＵ２の相手側を宛先と
した要求を保持しており、デッドロック状態に陥ってい
ることが分かる。
の間でデッドロックが発生している状態を示した図にお
いて、例えばＲＥＱ１２とあるのはＣＰＵ１からＣＰＵ
２へのリクエスト要求を意味し、また、ＲＥＳ１２とあ
るのはＣＰＵ１からＣＰＵ２への応答を意味する。応答
ＦＩＦＯ７３２および７４２はエントリが全てリクエス
トで埋まっており、新たなリクエストを受け付けること
ができない状態になっている。しかも要求ＦＩＦＯ７３
１および７４１の要求の方が先に入力されたものである
ため、この要求が出力されてしまわないと応答ＦＩＦＯ
７３２または７４２から出力できない。一方、要求ＦＩ
ＦＯは互いにＣＰＵ１またはＣＰＵ２の相手側を宛先と
した要求を保持しており、デッドロック状態に陥ってい
ることが分かる。
【０００７】本発明の目的は、かかるデッドロックの発
生を防止または解消するメッセージ制御装置を提供する
ことにある。
生を防止または解消するメッセージ制御装置を提供する
ことにある。
【０００８】また、本発明の他の目的は、上記メッセー
ジ間の追い越しの発生を防止するメッセージ制御装置を
提供することにある。
ジ間の追い越しの発生を防止するメッセージ制御装置を
提供することにある。
【０００９】
【課題を解決するための手段】上記課題を解決するため
に本発明のメッセージ制御装置は、複数のエントリを有
して他の装置への要求メッセージを保持する要求バッフ
ァと、複数のエントリを有して他の装置への応答メッセ
ージを保持する応答バッファと、複数のエントリを有し
て他の装置からの要求メッセージを保持する受付バッフ
ァと、この受付バッファが満杯になったことを検出する
検出手段と、前記要求バッファおよび前記応答バッファ
のいずれかに保持されているメッセージを選択して当該
メッセージの宛先である他の装置に対して出力する選択
器とを含み、前記選択器は、前記検出手段が前記受付バ
ッファの満杯状態を検出しない場合には最も早くから前
記要求バッファまたは前記応答バッファに入力されたメ
ッセージを出力し、前記検出手段が前記受付バッファの
満杯状態を検出した場合には前記応答バッファに保持さ
れているメッセージを優先的に出力する。
に本発明のメッセージ制御装置は、複数のエントリを有
して他の装置への要求メッセージを保持する要求バッフ
ァと、複数のエントリを有して他の装置への応答メッセ
ージを保持する応答バッファと、複数のエントリを有し
て他の装置からの要求メッセージを保持する受付バッフ
ァと、この受付バッファが満杯になったことを検出する
検出手段と、前記要求バッファおよび前記応答バッファ
のいずれかに保持されているメッセージを選択して当該
メッセージの宛先である他の装置に対して出力する選択
器とを含み、前記選択器は、前記検出手段が前記受付バ
ッファの満杯状態を検出しない場合には最も早くから前
記要求バッファまたは前記応答バッファに入力されたメ
ッセージを出力し、前記検出手段が前記受付バッファの
満杯状態を検出した場合には前記応答バッファに保持さ
れているメッセージを優先的に出力する。
【００１０】また、本発明の他のメッセージ制御装置
は、複数のエントリを有して他の装置への要求メッセー
ジを保持する要求バッファと、複数のエントリを有して
他の装置への応答メッセージを保持する応答バッファ
と、この応答バッファの各エントリ毎に設けられて所定
の値がセットされるフラグと、複数のエントリを有して
他の装置からの要求メッセージを保持する受付バッファ
と、この受付バッファが満杯になったことを検出すると
優先的に出力されるべき旨を示す値を前記フラグの全て
に対してセットする検出手段と、前記要求バッファおよ
び前記応答バッファのいずれかに保持されているメッセ
ージを選択して当該メッセージの宛先である他の装置に
対して出力する選択器とを含み、前記選択器は、前記応
答バッファに最も早く入力されたメッセージに対応する
フラグにおいて優先的に出力されるべき旨を示す値がセ
ットされていない場合には前記要求バッファまたは前記
応答バッファに最も早く入力されたメッセージを出力
し、前記応答バッファに最も早く入力されたメッセージ
に対応するフラグにおいて優先的に出力されるべき旨を
示す値がセットされている場合には前記応答バッファに
最も早く入力された応答メッセージを出力する。
は、複数のエントリを有して他の装置への要求メッセー
ジを保持する要求バッファと、複数のエントリを有して
他の装置への応答メッセージを保持する応答バッファ
と、この応答バッファの各エントリ毎に設けられて所定
の値がセットされるフラグと、複数のエントリを有して
他の装置からの要求メッセージを保持する受付バッファ
と、この受付バッファが満杯になったことを検出すると
優先的に出力されるべき旨を示す値を前記フラグの全て
に対してセットする検出手段と、前記要求バッファおよ
び前記応答バッファのいずれかに保持されているメッセ
ージを選択して当該メッセージの宛先である他の装置に
対して出力する選択器とを含み、前記選択器は、前記応
答バッファに最も早く入力されたメッセージに対応する
フラグにおいて優先的に出力されるべき旨を示す値がセ
ットされていない場合には前記要求バッファまたは前記
応答バッファに最も早く入力されたメッセージを出力
し、前記応答バッファに最も早く入力されたメッセージ
に対応するフラグにおいて優先的に出力されるべき旨を
示す値がセットされている場合には前記応答バッファに
最も早く入力された応答メッセージを出力する。
【００１１】また、本発明の他のメッセージ制御装置
は、複数のエントリを有して他の装置への要求メッセー
ジを保持する要求バッファと、この要求バッファからの
読出し位置を示す読出しポインタと、前記要求バッファ
への書込み位置を示す書込みポインタと、複数のエント
リを有して他の装置への応答メッセージとともにそのと
きの前記書込みポインタの値を保持する応答バッファ
と、この応答バッファの各エントリ毎に設けられて所定
の値がセットされるフラグと、複数のエントリを有して
他の装置からの要求メッセージを保持する受付バッファ
と、この受付バッファが満杯になったことを検出すると
優先的に出力されるべき旨を示す値を前記フラグの全て
に対してセットする検出手段と、前記読出しポインタの
値と前記応答バッファに保持された書込みポインタの値
とを比較して一致したエントリに対応する前記フラグに
対して優先的に出力されるべき旨を示す値をセットする
比較手段と、前記要求バッファおよび前記応答バッファ
のいずれかに保持されているメッセージを選択して当該
メッセージの宛先である他の装置に対して出力する選択
器とを含み、前記選択器は、前記応答バッファに最も早
く入力されたメッセージに対応するフラグにおいて優先
的に出力されるべき旨を示す値がセットされていない場
合には前記要求バッファに最も早く入力された要求メッ
セージを出力し、前記応答バッファに最も早く入力され
たメッセージに対応するフラグにおいて優先的に出力さ
れるべき旨を示す値がセットされている場合には前記応
答バッファに最も早く入力された応答メッセージを出力
する。
は、複数のエントリを有して他の装置への要求メッセー
ジを保持する要求バッファと、この要求バッファからの
読出し位置を示す読出しポインタと、前記要求バッファ
への書込み位置を示す書込みポインタと、複数のエント
リを有して他の装置への応答メッセージとともにそのと
きの前記書込みポインタの値を保持する応答バッファ
と、この応答バッファの各エントリ毎に設けられて所定
の値がセットされるフラグと、複数のエントリを有して
他の装置からの要求メッセージを保持する受付バッファ
と、この受付バッファが満杯になったことを検出すると
優先的に出力されるべき旨を示す値を前記フラグの全て
に対してセットする検出手段と、前記読出しポインタの
値と前記応答バッファに保持された書込みポインタの値
とを比較して一致したエントリに対応する前記フラグに
対して優先的に出力されるべき旨を示す値をセットする
比較手段と、前記要求バッファおよび前記応答バッファ
のいずれかに保持されているメッセージを選択して当該
メッセージの宛先である他の装置に対して出力する選択
器とを含み、前記選択器は、前記応答バッファに最も早
く入力されたメッセージに対応するフラグにおいて優先
的に出力されるべき旨を示す値がセットされていない場
合には前記要求バッファに最も早く入力された要求メッ
セージを出力し、前記応答バッファに最も早く入力され
たメッセージに対応するフラグにおいて優先的に出力さ
れるべき旨を示す値がセットされている場合には前記応
答バッファに最も早く入力された応答メッセージを出力
する。
【００１２】また、本発明の他のメッセージ制御装置に
おいては、前記要求バッファ、前記応答バッファ、およ
び前記受付バッファのそれぞれは、先入れ先出しバッフ
ァにより構成される。
おいては、前記要求バッファ、前記応答バッファ、およ
び前記受付バッファのそれぞれは、先入れ先出しバッフ
ァにより構成される。
【００１３】
【００１４】
【実施例】次に本発明のメッセージ制御装置の一実施例
について図面を参照して詳細に説明する。
について図面を参照して詳細に説明する。
【００１５】図１を参照すると、本発明の一実施例で
は、システムバス２００に複数の中央処理装置２０１，
２０２および主記憶装置２０５，２０６、および入出力
装置２０３，２０４が接続されている。各装置は、シス
テムバス２００に送信するメッセージを待ち合わせる要
求ＦＩＦＯ１１４および応答ＦＩＦＯ１０８を備える。
また、各装置は、システムバス２００に接続された他装
置からのメッセージを受け付ける受付ＲＥＧ１０５、他
装置からのメッセージが自装置に対するものであるかを
判定するアドレスアレイ１０４、判定結果と他装置のメ
ッセージを格納する受付ＦＩＦＯ１０７，受付ＦＩＦＯ
１０７の制御をする受付ＦＩＦＯ制御部１０６、受付Ｆ
ＩＦＯ１０７の状態からデッドロックを検出するデッド
ロック条件検出部１１１、デッドロック条件を検出時に
応答ＦＩＦＯ１０８の優先順位を高める印を付けるため
のマークフラグ１１０、応答ＦＩＦＯ１０８の各エント
リに保持された書込みポインタの値と要求ＦＩＦＯ用読
出しポインタ１１２の値とを比較するポインタ比較装置
１０９、順序制御用マークフラグの出力線１１６の値に
より要求ＦＩＦＯ１１４または応答ＦＩＦＯ１０８のシ
ステムバスを選択するＦＩＦＯセレクタ１１５、複数の
演算処理装置１０１，１０２、および、演算処理装置１
０１，１０２からのメッセージを選択するメッセージセ
レクタ１０３を有している。
は、システムバス２００に複数の中央処理装置２０１，
２０２および主記憶装置２０５，２０６、および入出力
装置２０３，２０４が接続されている。各装置は、シス
テムバス２００に送信するメッセージを待ち合わせる要
求ＦＩＦＯ１１４および応答ＦＩＦＯ１０８を備える。
また、各装置は、システムバス２００に接続された他装
置からのメッセージを受け付ける受付ＲＥＧ１０５、他
装置からのメッセージが自装置に対するものであるかを
判定するアドレスアレイ１０４、判定結果と他装置のメ
ッセージを格納する受付ＦＩＦＯ１０７，受付ＦＩＦＯ
１０７の制御をする受付ＦＩＦＯ制御部１０６、受付Ｆ
ＩＦＯ１０７の状態からデッドロックを検出するデッド
ロック条件検出部１１１、デッドロック条件を検出時に
応答ＦＩＦＯ１０８の優先順位を高める印を付けるため
のマークフラグ１１０、応答ＦＩＦＯ１０８の各エント
リに保持された書込みポインタの値と要求ＦＩＦＯ用読
出しポインタ１１２の値とを比較するポインタ比較装置
１０９、順序制御用マークフラグの出力線１１６の値に
より要求ＦＩＦＯ１１４または応答ＦＩＦＯ１０８のシ
ステムバスを選択するＦＩＦＯセレクタ１１５、複数の
演算処理装置１０１，１０２、および、演算処理装置１
０１，１０２からのメッセージを選択するメッセージセ
レクタ１０３を有している。
【００１６】受付ＦＩＦＯ１０７が他の装置から受け付
けた要求は、（図示しない）メモリアクセス等を経て応
答メッセージとなり、応答ＦＩＦＯ１０８に保持され
る。
けた要求は、（図示しない）メモリアクセス等を経て応
答メッセージとなり、応答ＦＩＦＯ１０８に保持され
る。
【００１７】応答ＦＩＦＯ１０８は応答メッセージとそ
のときの書込みポインタ１１３の値とを対にして各エン
トリに保持する。この応答ＦＩＦＯ１０８の各エントリ
には順序制御マークフラグ１１０が１対１に対応してい
る。
のときの書込みポインタ１１３の値とを対にして各エン
トリに保持する。この応答ＦＩＦＯ１０８の各エントリ
には順序制御マークフラグ１１０が１対１に対応してい
る。
【００１８】要求ＦＩＦＯ１１４は、セレクタ１０３か
ら要求を受け取ると、書込みポインタ１１３の示すエン
トリに該要求を保持する。書込みポインタ１１３はその
後１つカウントアップされる。要求ＦＩＦＯ１１４はセ
レクタ１１５に選択されると、読出しポインタ１１２の
示すエントリから要求を出力する。読出しポインタ１１
２はその後１つカウントアップされる。すなわち、要求
ＦＩＦＯ１１４はリングバッファ構成になっており、読
出しポインタ１１２と書込みポインタ１１３とにより制
御される。
ら要求を受け取ると、書込みポインタ１１３の示すエン
トリに該要求を保持する。書込みポインタ１１３はその
後１つカウントアップされる。要求ＦＩＦＯ１１４はセ
レクタ１１５に選択されると、読出しポインタ１１２の
示すエントリから要求を出力する。読出しポインタ１１
２はその後１つカウントアップされる。すなわち、要求
ＦＩＦＯ１１４はリングバッファ構成になっており、読
出しポインタ１１２と書込みポインタ１１３とにより制
御される。
【００１９】順序制御マークフラグ１１０は、応答メッ
セージの１エントリ毎に備えられ、以下の２つの場合に
１にセットされる。１つ目は、ポインタ比較装置１０９
によって一致が検出されたエントリに個別にセットされ
る場合である。これは要求ＦＩＦＯ１１４または応答Ｆ
ＩＦＯ１０８に要求または応答が入力された順序を保証
するためのものである。前述のように応答ＦＩＦＯ１０
８は、応答メッセージに加えて、入力された時点の書込
みポインタ１１３の値を対にして各エントリに保持して
おり、この書込みポインタの値を参照することによっ
て、要求ＦＩＦＯ１１４と応答ＦＩＦＯ１０８との間の
順序関係を保証することができる。
セージの１エントリ毎に備えられ、以下の２つの場合に
１にセットされる。１つ目は、ポインタ比較装置１０９
によって一致が検出されたエントリに個別にセットされ
る場合である。これは要求ＦＩＦＯ１１４または応答Ｆ
ＩＦＯ１０８に要求または応答が入力された順序を保証
するためのものである。前述のように応答ＦＩＦＯ１０
８は、応答メッセージに加えて、入力された時点の書込
みポインタ１１３の値を対にして各エントリに保持して
おり、この書込みポインタの値を参照することによっ
て、要求ＦＩＦＯ１１４と応答ＦＩＦＯ１０８との間の
順序関係を保証することができる。
【００２０】例えば、第１の要求→第１の応答→第２の
応答→第２の要求、の順にＦＩＦＯに入力があったとす
ると、要求ＦＩＦＯ１１４の第１エントリに第１の要求
が入力された後、応答ＦＩＦＯ１０８の第１のエントリ
に第１の応答が、第２のエントリに第２の応答がそれぞ
れ入力される。このとき、応答ＦＩＦＯ１０８の書込み
ポインタの部分には共にそのときの書込みポインタ１１
３の値である”２”が保持される。その後、要求ＦＩＦ
Ｏ１１４の第２エントリに第２の要求が入力される。こ
れを読み出す際には、まず要求ＦＩＦＯ１１４から第１
の要求が出力されると、読出しポインタ１１２が”２”
になり、ポインタ比較装置１０９によって第１のエント
リと第２のエントリにおいて一致が検出されるため、対
応する順序制御マークフラグ１１０が１にセットされ
る。これにより、セレクタ１１５は応答ＦＩＦＯ１０８
側を選択するようになり、第１の応答に続いて第２の応
答が出力される。
応答→第２の要求、の順にＦＩＦＯに入力があったとす
ると、要求ＦＩＦＯ１１４の第１エントリに第１の要求
が入力された後、応答ＦＩＦＯ１０８の第１のエントリ
に第１の応答が、第２のエントリに第２の応答がそれぞ
れ入力される。このとき、応答ＦＩＦＯ１０８の書込み
ポインタの部分には共にそのときの書込みポインタ１１
３の値である”２”が保持される。その後、要求ＦＩＦ
Ｏ１１４の第２エントリに第２の要求が入力される。こ
れを読み出す際には、まず要求ＦＩＦＯ１１４から第１
の要求が出力されると、読出しポインタ１１２が”２”
になり、ポインタ比較装置１０９によって第１のエント
リと第２のエントリにおいて一致が検出されるため、対
応する順序制御マークフラグ１１０が１にセットされ
る。これにより、セレクタ１１５は応答ＦＩＦＯ１０８
側を選択するようになり、第１の応答に続いて第２の応
答が出力される。
【００２１】順序制御マークフラグ１１０が１にセット
される２つ目の場合は、デッドロック条件検出部１１１
がデッドロック発生の可能性を検出した場合である。こ
の場合には、全ての順序制御マークフラグ１１０が１に
セットされる。すなわち、デッドロックの発生を予知し
た場合には、その時の応答ＦＩＦＯ１０８内の応答を優
先的に出力する。
される２つ目の場合は、デッドロック条件検出部１１１
がデッドロック発生の可能性を検出した場合である。こ
の場合には、全ての順序制御マークフラグ１１０が１に
セットされる。すなわち、デッドロックの発生を予知し
た場合には、その時の応答ＦＩＦＯ１０８内の応答を優
先的に出力する。
【００２２】デッドロック発生の予知は以下のように行
われる。受付ＦＩＦＯ制御部１０６は、受付ＦＩＦＯ１
０７が満杯の状態にあることをデッドロック条件検出部
１１１に送信する。これに応答して、デッドロック条件
検出部１１１は、受付ＦＩＦＯ１０７が満杯である場
合、デッドロックの可能性があると判定して、応答ＦＩ
ＦＯ１０８の全エントリの順序制御マークフラグ１１０
を１にセットする指示を順序制御マークフラグ１１０に
出す。これに応答して、順序制御マークフラグ１１０
は、全エントリの順序制御マークフラグ１１０を１にセ
ットする。
われる。受付ＦＩＦＯ制御部１０６は、受付ＦＩＦＯ１
０７が満杯の状態にあることをデッドロック条件検出部
１１１に送信する。これに応答して、デッドロック条件
検出部１１１は、受付ＦＩＦＯ１０７が満杯である場
合、デッドロックの可能性があると判定して、応答ＦＩ
ＦＯ１０８の全エントリの順序制御マークフラグ１１０
を１にセットする指示を順序制御マークフラグ１１０に
出す。これに応答して、順序制御マークフラグ１１０
は、全エントリの順序制御マークフラグ１１０を１にセ
ットする。
【００２３】このようにして１にセットされた順序制御
マークフラグ１１０は、各々対応するリクエストが発行
されると共に０にクリアされていく。
マークフラグ１１０は、各々対応するリクエストが発行
されると共に０にクリアされていく。
【００２４】このように順序制御マークフラグ１１０を
セットすることにより、デッドロック発生の可能性を予
知しない限り、要求ＦＩＦＯ１１４または応答ＦＩＦＯ
１０８に入力された順序を保ちながら、両ＦＩＦＯから
システムバス２００へ応答または要求を出力することが
できる。
セットすることにより、デッドロック発生の可能性を予
知しない限り、要求ＦＩＦＯ１１４または応答ＦＩＦＯ
１０８に入力された順序を保ちながら、両ＦＩＦＯから
システムバス２００へ応答または要求を出力することが
できる。
【００２５】次に本発明の上記一実施例の動作について
図面を参照して詳細に説明する。
図面を参照して詳細に説明する。
【００２６】図１から図３を参照すると、まず、演算処
理装置１０１または１０２が要求メッセージを発行する
と（ステップ５０１）、発行されたメッセージをメッセ
ージセレクタ１０３が選択する（ステップ５０２）。こ
の選択は、例えばラウンドロビン等により行われる。そ
して、この選択されたメッセージによりアドレスアレイ
１０４を検索する（ステップ５０３）。これにより、要
求メッセージをシステムバス２００に送信すべきか否か
を判断する（ステップ５０４）。検索した結果、要求さ
れたデータを当該中央処理装置２０１が保持していない
場合、要求メッセージを要求ＦＩＦＯ１１４に格納する
（ステップ５０５）。また、当該中央処理装置２０１が
要求されたデータを保持していた場合、中央処理装置内
のデータを演算処理装置１０１または１０２に返却して
処理が終了する。バッファ順位制御マークフラグ１１０
の内容を確認し（ステップ５０６）、バッファ順位制御
マークフラグ＝１の場合、応答ＦＩＦＯ１０８の内容を
ＦＩＦＯセレクタ１１５が選択して（ステップ５０
７）、応答メッセージをシステムバス２００に送信し
（ステップ５０８）、次に要求ＦＩＦＯ１１４側がＦＩ
ＦＯセレクタ１１５により選択されるのを待つ。順序制
御マークフラグ＝０の場合には、ＦＩＦＯセレクタ１１
５が要求ＦＩＦＯ１１４を選択して（ステップ５０
９）、要求メッセージをシステムバス２００に出力する
（ステップ５１０）。この出力された要求メッセージ
は、他の中央処理装置２０２、入出力装置２０３または
２０４、又は主記憶装置２０５または２０６が、その受
付ＲＥＧ１０５に保持する（ステップ５１１）。このよ
うにして受け付けたメッセージは、アドレスアレイ１０
４の検索に使用され（ステップ５１２）、これにより自
装置への要求であるかどうかを判断する（ステップ５１
３）。自装置以外への要求の場合には、処理を終了す
る。自装置への要求である場合には、そのメッセージを
受付ＦＩＦＯ１０７へ格納する（ステップ５１４）。そ
して、（図示しない）メモリアクセス等により要求メッ
セージへの応答を作成して、これを応答メッセージとし
て応答ＦＩＦＯ１０８に格納する（ステップ５１５）。
理装置１０１または１０２が要求メッセージを発行する
と（ステップ５０１）、発行されたメッセージをメッセ
ージセレクタ１０３が選択する（ステップ５０２）。こ
の選択は、例えばラウンドロビン等により行われる。そ
して、この選択されたメッセージによりアドレスアレイ
１０４を検索する（ステップ５０３）。これにより、要
求メッセージをシステムバス２００に送信すべきか否か
を判断する（ステップ５０４）。検索した結果、要求さ
れたデータを当該中央処理装置２０１が保持していない
場合、要求メッセージを要求ＦＩＦＯ１１４に格納する
（ステップ５０５）。また、当該中央処理装置２０１が
要求されたデータを保持していた場合、中央処理装置内
のデータを演算処理装置１０１または１０２に返却して
処理が終了する。バッファ順位制御マークフラグ１１０
の内容を確認し（ステップ５０６）、バッファ順位制御
マークフラグ＝１の場合、応答ＦＩＦＯ１０８の内容を
ＦＩＦＯセレクタ１１５が選択して（ステップ５０
７）、応答メッセージをシステムバス２００に送信し
（ステップ５０８）、次に要求ＦＩＦＯ１１４側がＦＩ
ＦＯセレクタ１１５により選択されるのを待つ。順序制
御マークフラグ＝０の場合には、ＦＩＦＯセレクタ１１
５が要求ＦＩＦＯ１１４を選択して（ステップ５０
９）、要求メッセージをシステムバス２００に出力する
（ステップ５１０）。この出力された要求メッセージ
は、他の中央処理装置２０２、入出力装置２０３または
２０４、又は主記憶装置２０５または２０６が、その受
付ＲＥＧ１０５に保持する（ステップ５１１）。このよ
うにして受け付けたメッセージは、アドレスアレイ１０
４の検索に使用され（ステップ５１２）、これにより自
装置への要求であるかどうかを判断する（ステップ５１
３）。自装置以外への要求の場合には、処理を終了す
る。自装置への要求である場合には、そのメッセージを
受付ＦＩＦＯ１０７へ格納する（ステップ５１４）。そ
して、（図示しない）メモリアクセス等により要求メッ
セージへの応答を作成して、これを応答メッセージとし
て応答ＦＩＦＯ１０８に格納する（ステップ５１５）。
【００２７】このようにして入力された要求ＦＩＦＯ１
１４または応答ＦＩＦＯ１０８からの読出しに当たって
は、順序制御マークフラグ１１０の内容を確認する（ス
テップ５１６）。当該フラグ＝０の場合、ＦＩＦＯセレ
クタ１１５が要求ＦＩＦＯ１１４を選択して（ステップ
５２４）、要求メッセージをシステムバス２００に出力
する（ステップ５２５）。これを当該フラグが１になる
まで繰り返す。順序制御マークフラグ＝１の場合、ＦＩ
ＦＯセレクタ５１７が応答ＦＩＦＯを選択して（ステッ
プ５１７）、応答メッセージをシステムバス２００に出
力する（ステップ５１８）。この出力された要求メッセ
ージは、他の中央処理装置２０２、入出力装置２０３ま
たは２０４、又は主記憶装置２０５または２０６が、そ
の受付ＲＥＧ１０５に保持する（ステップ５１９）。こ
のようにして受け付けたメッセージは、アドレスアレイ
１０４の検索に使用され（ステップ５２０）、これによ
り自装置への要求であるかどうかを判断する（ステップ
５２１）。自装置以外への要求の場合には、処理を終了
する。自装置への要求である場合には、そのメッセージ
を受付ＦＩＦＯ１０７へ格納する（ステップ５２２）。
そして、要求メッセージの送信元である演算処理装置１
０１または１０２へ応答メッセージを返却する（ステッ
プ５２３）。
１４または応答ＦＩＦＯ１０８からの読出しに当たって
は、順序制御マークフラグ１１０の内容を確認する（ス
テップ５１６）。当該フラグ＝０の場合、ＦＩＦＯセレ
クタ１１５が要求ＦＩＦＯ１１４を選択して（ステップ
５２４）、要求メッセージをシステムバス２００に出力
する（ステップ５２５）。これを当該フラグが１になる
まで繰り返す。順序制御マークフラグ＝１の場合、ＦＩ
ＦＯセレクタ５１７が応答ＦＩＦＯを選択して（ステッ
プ５１７）、応答メッセージをシステムバス２００に出
力する（ステップ５１８）。この出力された要求メッセ
ージは、他の中央処理装置２０２、入出力装置２０３ま
たは２０４、又は主記憶装置２０５または２０６が、そ
の受付ＲＥＧ１０５に保持する（ステップ５１９）。こ
のようにして受け付けたメッセージは、アドレスアレイ
１０４の検索に使用され（ステップ５２０）、これによ
り自装置への要求であるかどうかを判断する（ステップ
５２１）。自装置以外への要求の場合には、処理を終了
する。自装置への要求である場合には、そのメッセージ
を受付ＦＩＦＯ１０７へ格納する（ステップ５２２）。
そして、要求メッセージの送信元である演算処理装置１
０１または１０２へ応答メッセージを返却する（ステッ
プ５２３）。
【００２８】このように、本発明の一実施例であるメッ
セージ制御装置によれば、デッドロック条件検出部１１
１によりデッドロック発生の可能性を検出して順序制御
マークフラグ１１０をセットすることにより、応答ＦＩ
ＦＯ１０８から優先的に出力させてデッドロックを回避
することができる。また、応答ＦＩＦＯ１０８に入力時
の要求ＦＩＦＯ１１４への書込みポインタ１１３の値を
保持しておくことにより、要求ＦＩＦＯ１１４と応答Ｆ
ＩＦＯ１０８との間のメッセージの追い越しを防止する
ことができる。
セージ制御装置によれば、デッドロック条件検出部１１
１によりデッドロック発生の可能性を検出して順序制御
マークフラグ１１０をセットすることにより、応答ＦＩ
ＦＯ１０８から優先的に出力させてデッドロックを回避
することができる。また、応答ＦＩＦＯ１０８に入力時
の要求ＦＩＦＯ１１４への書込みポインタ１１３の値を
保持しておくことにより、要求ＦＩＦＯ１１４と応答Ｆ
ＩＦＯ１０８との間のメッセージの追い越しを防止する
ことができる。
【００２９】
【発明の効果】以上の説明で明らかなように、本発明に
よると、デッドロック発生の可能性を検出して応答ＦＩ
ＦＯ側から優先的に出力させることにより、デッドロッ
クを回避することができる。また、応答ＦＩＦＯ入力時
に要求ＦＩＦＯへの書込みポインタの値を保持しておく
ことにより、要求ＦＩＦＯと応答ＦＩＦＯとの間のメッ
セージの追い越しを防止することができる。
よると、デッドロック発生の可能性を検出して応答ＦＩ
ＦＯ側から優先的に出力させることにより、デッドロッ
クを回避することができる。また、応答ＦＩＦＯ入力時
に要求ＦＩＦＯへの書込みポインタの値を保持しておく
ことにより、要求ＦＩＦＯと応答ＦＩＦＯとの間のメッ
セージの追い越しを防止することができる。
【図１】本発明のメッセージ制御装置の一実施例の構成
を示すブロック図である。
を示すブロック図である。
【図２】本発明の一実施例のメッセージ制御装置の動作
を表す図である。
を表す図である。
【図３】本発明の一実施例のメッセージ制御装置の動作
を表す他の図である。
を表す他の図である。
【図４】従来技術によるシステム構成の一例を表す図で
ある。
ある。
【図５】従来技術によるメッセージ制御装置におけるデ
ッドロック発生の状態を表した図である。
ッドロック発生の状態を表した図である。
１０１，１０２ 演算処理装置 １０３ メッセージセレクタ １０４ アドレスアレイ １０５ 受け付けＲＥＧ １０６ 受け付けＦＩＦＯ制御部 １０７ 受け付けＦＩＦＯ １０８ 応答ＦＩＦＯ １０９ ポインタ比較器 １１０ 順序制御マークフラグ １１１ デッドロック条件検出部 １１２ 要求ＦＩＦＯリードポインタ １１３ 要求ＦＩＦＯライトポインタ １１４ 要求ＦＩＦＯ １１５ ＦＩＦＯセレクタ １１６ 順序制御信号 １１７ システムバス出力信号 １１８ システムバス入力信号 ２００ システムバス ２０１，２０２ 中央処理装置 ２０３，２０４ 入出力処理装置 ２０５，２０６ 主記憶装置 ７０１〜７０４ プロセッサ・メモリ・エレメント ７０５ クロスバネットワーク ７１１，７１２ クロスバネットワークの各ステージ ７２１〜７２４ スイッチ ７３１ 要求ＦＩＦＯ ７３２ 応答ＦＩＦＯ ７３３ メッセージセレクタ
───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.7，ＤＢ名) G06F 15/16 - 15/177
Claims (4)
- 【請求項１】 複数のエントリを有して他の装置への要
求メッセージを保持する要求バッファと、 複数のエントリを有して他の装置への応答メッセージを
保持する応答バッファと、 複数のエントリを有して他の装置からの要求メッセージ
を保持する受付バッファと、 この受付バッファが満杯になったことを検出する検出手
段と、 前記要求バッファおよび前記応答バッファのいずれかに
保持されているメッセージを選択して当該メッセージの
宛先である他の装置に対して出力する選択器とを含み、 前記選択器は、前記検出手段が前記受付バッファの満杯
状態を検出しない場合には最も早くから前記要求バッフ
ァまたは前記応答バッファに入力されたメッセージを出
力し、前記検出手段が前記受付バッファの満杯状態を検
出した場合には前記応答バッファに保持されているメッ
セージを優先的に出力することを特徴とするメッセージ
制御装置。 - 【請求項２】 複数のエントリを有して他の装置への要
求メッセージを保持する要求バッファと、 複数のエントリを有して他の装置への応答メッセージを
保持する応答バッファと、 この応答バッファの各エントリ毎に設けられて所定の値
がセットされるフラグと、 複数のエントリを有して他の装置からの要求メッセージ
を保持する受付バッファと、 この受付バッファが満杯になったことを検出すると優先
的に出力されるべき旨を示す値を前記フラグの全てに対
してセットする検出手段と、 前記要求バッファおよび前記応答バッファのいずれかに
保持されているメッセージを選択して当該メッセージの
宛先である他の装置に対して出力する選択器とを含み、 前記選択器は、前記応答バッファに最も早く入力された
メッセージに対応するフラグにおいて優先的に出力され
るべき旨を示す値がセットされていない場合には前記要
求バッファまたは前記応答バッファに最も早く入力され
たメッセージを出力し、前記応答バッファに最も早く入
力されたメッセージに対応するフラグにおいて優先的に
出力されるべき旨を示す値がセットされている場合には
前記応答バッファに最も早く入力された応答メッセージ
を出力することを特徴とするメッセージ制御装置。 - 【請求項３】 複数のエントリを有して他の装置への要
求メッセージを保持する要求バッファと、 この要求バッファからの読出し位置を示す読出しポイン
タと、 前記要求バッファへの書込み位置を示す書込みポインタ
と、 複数のエントリを有して他の装置への応答メッセージと
ともにそのときの前記書込みポインタの値を保持する応
答バッファと、 この応答バッファの各エントリ毎に設けられて所定の値
がセットされるフラグと、 複数のエントリを有して他の装置からの要求メッセージ
を保持する受付バッファと、 この受付バッファが満杯になったことを検出すると優先
的に出力されるべき旨を示す値を前記フラグの全てに対
してセットする検出手段と、前記 読出しポインタの値と前記応答バッファに保持され
た書込みポインタの値とを比較して一致したエントリに
対応する前記フラグに対して優先的に出力されるべき旨
を示す値をセットする比較手段と、 前記要求バッファおよび前記応答バッファのいずれかに
保持されているメッセージを選択して当該メッセージの
宛先である他の装置に対して出力する選択器とを含み、 前記選択器は、前記応答バッファに最も早く入力された
メッセージに対応するフラグにおいて優先的に出力され
るべき旨を示す値がセットされていない場合には前記要
求バッファに最も早く入力された要求メッセージを出力
し、前記応答バッファに最も早く入力されたメッセージ
に対応するフラグにおいて優先的に出力されるべき旨を
示す値がセットされている場合には前記応答バッファに
最も早く入力された応答メッセージを出力することを特
徴とするメッセージ制御装置。 - 【請求項４】 前記要求バッファ、前記応答バッファ、
および前記受付バッファのそれぞれは、先入れ先出しバ
ッファにより構成されることを特徴とする請求項３記載
のメッセージ制御装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7055665A JP3068427B2 (ja) | 1995-03-15 | 1995-03-15 | メッセージ制御装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7055665A JP3068427B2 (ja) | 1995-03-15 | 1995-03-15 | メッセージ制御装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH08249295A JPH08249295A (ja) | 1996-09-27 |
| JP3068427B2 true JP3068427B2 (ja) | 2000-07-24 |
Family
ID=13005159
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7055665A Expired - Fee Related JP3068427B2 (ja) | 1995-03-15 | 1995-03-15 | メッセージ制御装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3068427B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6490630B1 (en) * | 1998-05-08 | 2002-12-03 | Fujitsu Limited | System and method for avoiding deadlock in multi-node network |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5439503A (en) * | 1977-09-05 | 1979-03-27 | Hitachi Ltd | Priority selection system in ring transmission line |
| JPS58182778A (ja) * | 1982-04-19 | 1983-10-25 | Nec Corp | 分散処理方式 |
| JPS6373459A (ja) * | 1986-09-17 | 1988-04-04 | Fanuc Ltd | デ−タ処理方法 |
| JPH01151350U (ja) * | 1988-04-08 | 1989-10-19 | ||
| JP2911931B2 (ja) * | 1989-12-29 | 1999-06-28 | 日本電気株式会社 | プロセッサ間通信におけるデータ転送競合回避方式 |
| JPH05210513A (ja) * | 1992-01-31 | 1993-08-20 | Nec Corp | 状態監視型割り込み制御システム |
| JP3460090B2 (ja) * | 1992-04-23 | 2003-10-27 | 富士通株式会社 | バス・インタフェース制御回路 |
| JP3360856B2 (ja) * | 1992-12-18 | 2003-01-07 | 富士通株式会社 | プロセッサ |
-
1995
- 1995-03-15 JP JP7055665A patent/JP3068427B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH08249295A (ja) | 1996-09-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5046000A (en) | Single-FIFO high speed combining switch | |
| US5781927A (en) | Main memory arbitration with priority scheduling capability including multiple priorty signal connections | |
| US6181705B1 (en) | System and method for management a communications buffer | |
| US4494190A (en) | FIFO buffer to cache memory | |
| KR950033892A (ko) | 데이타 처리 시스템 | |
| US6170003B1 (en) | Apparatus and method for communicating messages between data processing nodes using remote reading of message queues | |
| US5835779A (en) | Message transmission among processing units using interrupt control technique | |
| US5944788A (en) | Message transfer system and control method for multiple sending and receiving modules in a network supporting hardware and software emulated modules | |
| JP3057591B2 (ja) | マルチプロセッサシステム | |
| JPH07262151A (ja) | 並列プロセッサシステムおよびそれに適したパケット廃棄方法 | |
| JP3068427B2 (ja) | メッセージ制御装置 | |
| US6341313B1 (en) | Flow controlling method and apparatus for network between processors | |
| US6625678B1 (en) | Livelock avoidance method | |
| JP3005456B2 (ja) | ベクトル処理装置 | |
| KR20000006575A (ko) | 빈버퍼들에대한포인터들을포함하는프리포인터선입선출메모리를이용하여버퍼들을관리하는시스템및방법 | |
| US5901290A (en) | Data transfer apparatus for transferring data fixedly in predetermined time interval without a transmitter checking a signal from a receiver | |
| US5592680A (en) | Abnormal packet processing system | |
| EP0141753A2 (en) | Adjustable buffer for data communications in data processing system | |
| US6345332B1 (en) | Bus interchange apparatus and dual system for accessing a fault information register without regard to buffer conditions | |
| KR100199033B1 (ko) | 절충식 pci버스용 다중 인터럽트 제어장치 및 방법 | |
| US6092125A (en) | Method and apparatus for transferring data from devices not supporting burst data transfers in burst mode | |
| US11443783B2 (en) | Semiconductor device | |
| JP2926859B2 (ja) | 並列処理システム | |
| JP3149143B2 (ja) | アクセス調停方式 | |
| JP2739949B2 (ja) | 通信バッファ装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20000411 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| LAPS | Cancellation because of no payment of annual fees |