JPH0362277A - デッドロック検出方法およびデッドロック検出機構 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明はスーパーコンピュータ等に使用される自己同期
型データフローマイクロプロセッサにおけるデッドロッ
ク検出方法およびデッドロック検出機構に関する。

〈従来の技術〉 従来の自己同期型データブローマイクロプロセッサは第
５図に示すような構成をしている。第５図において、ｌ
は処理機構付きメモリ装置、２は演算処理部、３はトー
クン分岐部、４はトークン待合せ部、５はプログラム記
憶部、６ａ、６ｂ、６ｃはトークン合流部、７はトーク
ン緩衝部、８は外部トークン人力部であり、演算処理部
２から合流部６ｂ、分岐部３、緩衝部７、合流部６ａ、
プログラム記憶部５、待合せ部４、分岐部３を経て演算
処理部２に戻るサーキュラ−パイプラインが形成されて
いる。

〈発明が解決しようとする課題〉 第５図の構成において、サーキュラ−パイプライン内に
トークンか詰まると、プロセッサはデッドロックに陥っ
て、トークンが次のトークンに制御を移さず同じトーク
ンのみがサーキュラ−パイプライン上を回り続ける状態
（無限ループ）等が出現するが、サーキュラ−パイプラ
インでのデータの処理順、単位時間当たりの処理命令が
一定でないため、デッドロックの検出は容易でないとい
う問題がある。しかも、デッドロックの発生を外部から
知ることはまったくできないため、従来はプログラムの
適切な設定によってデッドロックを回避するようにして
いた。したがって、プログラムの作成時にシミュレーシ
ョンを十分実施し、デッドロックが発生しないようにプ
ログラムの調整を行うことが必要であり、プログラムの
作成が非常に面倒であった。

そこで、本発明の目的は、自己同期型データフローマイ
クロプロセッサにおいて、デッドロックの発生を容易に
検出するためのデッドロック検出方法およびデッドロッ
クを検出して外部に知らせることのできるデッドロック
検出機構を提供することである。

〈課題を解決するための手段〉 上記目的を達成するため、本発明のデッドロック検出方
法は、自己同期型データフローマイクロプロセッサにお
いて、ダミートークンをサーキュラ−パイプライン上に
周回させ、上記ダミートークンが上記サーキュラ−パイ
プラインの所定の箇所を通過した後再び通過するまでの
間に上記箇所を通過するトークンのチェックサムを算出
し、次に、今回算出したチェックサムと前回算出したチ
ェックサムとが一致するかどうかを判別し、一致する場
合はチェックサム−数回数として計数し、そうでない場
合はいままでに計数された回数を初期値に戻すことによ
って、同一のチェックサムが連続するチェックサム連続
回数を求め、次に、上記チェックサム連続回数を所定値
と比較し、同じ場合には同じトークンが上記サーキュラ
−パイプラインを周回し続けていると見なしてデッドロ
ックを検出することを特徴としている。

また、本発明のデッドロック検出機構は、自己同期型デ
ータフローマイクロプロセッサにおいて、ダミートーク
ンが周回するサーキュラ−パイプライン上にデッドロッ
ク監視部を設け、上記デッドロック監視部は、上記ダミ
ートークンが上記デッドロック監視部を通過してから再
び通過するまでの間に上記デッドロック監視部を通過す
るトークンのチェックサムを算出するチェックサム算出
部と、上記チェックサム算出部によって算出されたチェ
ックサムを格納するチェックサム格納部と、上記チェッ
クサム格納部から出力されるチェックサムと上記算出部
によって新たに算出されたチェックサムとが一致してい
るかどうかを判別するチェックサム一致判別部と、上記
チェックサム−致判別部による判別結果に基づき、同一
のチェックサムが連続する回数を計数する計数部と、上
記計数部によって計数された値が所定値と等しくなった
ときデッドロックを判定して、デッドロック判定信号を
出力するデッドロック判定部とを備えたことを特徴とし
ている。

〈作用〉 本発明のデッドロック検出機構によれば、デッドロック
監視部のチェックサム算出部によって、ダミートークン
がサーキュラ−パイプライン上を１周する毎にトークン
データのチェックサムが算出される。この算出されたチ
ェックサムはチェックサム格納部に既に格納されている
前回のチェックサムと一致しているかどうかチェックサ
ム一致判別部によって判別される。今回と前回のチェッ
クサムが一致していると判別された場合には、計数部に
よってその一致回数が計数される。そして、上記計数部
による計数値が所定値に達すると、デッドロック判定部
によって、デッドロックが発生していると判定され、デ
ッドロック判定信号が出力される。

〈実施例〉 以下、本発明を図示の実施例により詳細に説明する。

第１図は本発明のデッドロック検出機構を備えた自己同
期型データフローマイクロプロセッサ（以下、プロセッ
サと言う。）の一実施例の概略構成図である。このプロ
セッサの構成は第５図に示した従来のプロセッサと殆ど
同様の構成であるが、サーキュラ−パイプライン上のト
ークン分岐部６ａとプログラム記憶部５との間に、デッ
ドロックの発生を検出して外部に知らせるデッドロック
監視部ＩＯを付加した点で第５図に示した従来のプロセ
ッサ構成と異なる。第１図において、第５図の従来のプ
ロセッサと同一構成部は同一参照番号を付して説明を省
略する。なお、第１図において、白丸はたとえば３バイ
トの情報を有し、サーキュラ−パイプラインの中を回り
、プロセッサの各部で値を変えながら所定のプログラム
を実行するためのトークンを、黒丸は３バイトの情報を
有し、プログラム実行には関与しないで、上記サーキュ
ラ−パイプライン上を値を変えることなく回り続けるダ
ミートークンを示している。

第２図は上記デッドロック監視部ＩＯに設けたレジスタ
構成を示し、Ｘレジスタは上記ダミートークンがデッド
ロック監視部１０を通過して再び通過するまでの間に上
記デッドロック監視部！Ｏを通過する正規のトークンの
チェックサムを算出するレジスタ、Ｘレジスタは上記Ｘ
レジスタによって算出されたチェックサムのスタックと
して用いられるレジスタである。

本実施例では、Ｘレジスタの値とＸレジスタとの値を比
較することによって、同じトークンがデッドロック監視
部１０を通過しているかどうか、すなわち同じトークン
がサーキュラ−パイプラインを回り続けているかどうか
を判別するようにしている。より具体的に言うと、第３
図に示すように、Ｘレジスタによって今回算出されたチ
ェックサムがＸｔであるとすると、この値Ｘｔがスタッ
ク用のＸレジスタに格納され、次回のチェックサムＸ２
の比較値Ｙ１として出力されるのである。したがって、
ＸＩ、Ｘ２．・・・が同じ値である限り、Ｙｌ。

Ｙ２．・・・ら同じ値になり、その間同じトークンがサ
ーキュラ−パイプラインを回り続けていると判断される
のである。

ナ１３、本実施例におけるチェックサムは、３バイトの
各トークンのうちでアドレス情報を表す２バイトのデー
タの和を、とったものである。

上記Ｘレジスタからの出力値Ｙ１．Ｙ２．・・・に変化
がない状態でダミートークンがデッドロック監視部を通
過した回数、つまり上記Ｘレジスタが前回と同じチェッ
クサムを得た回数は計数用レジスタＣＮＴによって計数
される。この計数用レジスタは、Ｘレジスタの値とＸレ
ジスタの値とが異なる場合には、初期値に戻される。上
記計数用レジスタＣＮＴによって計数された値はレジス
タＣＭＡＸに格納された基準値Ｖと比較され、基準値Ｖ
と等しくなったとき、デッドロック監視部ｌＯは無限ル
ープが発生していると判定して、デッドロック判定信号
を外部に出力する。

なお、上記レジスタＣＭＡＸにセットする基準値Ｖを小
さくし過ぎると、チェックサムによるデッドロックの検
出であるため、デッドロックでないのをデッドロックと
したりする等、誤判断のおそれがあるため、デッドロッ
クであると正しく判定できる確率がほぼ１００％になる
ように十分な大きさの値に設定することが重要である。

次に、上記構成のプロセッサを用いたデッドロックの検
出処理の流れを第４図のブローチヤードにしたがって説
明する。

（ステップＳｔ）　　まず、プロセッサ起動と同時に、
ダミートークンがサーキュラ−パイプライン内に投入さ
れる。

（ステップＳ２）　　デッドロック監視部ＩＯにおいて
、チェックサム用のＸ、Ｘレジスタと計数用レジスタＣ
ＮＴがクリアされると共に、レジスタＣＭＡＸに基準値
Ｖがセットされる。

（ステップＳ３）　　続いて、デッドロック監視部ｌＯ
はサーキュラ−パイプラインを回って入ってきたトーク
ンのデータを読み取る。

（ステップＳ４）　　ステップＳ３で読み取ったトーク
ンデータの結果によって、今通過したトークンがダミー
トークンか否かを判別する。

（ステップＳ５）　　ステップＳ４でダミートークンで
はない、つまり正規のトークンであると判断した場合に
は、ステップＳ３で読み取ったトークンデータをＸレジ
スタにプラスして格納し、その後再びステップＳ３に戻
る。

上記のステップＳ３．Ｓ４．Ｓ５の処理は、ダミートー
クンがデッドロック監視部１０を通過してから再び通過
するまでの間繰り返され、その間にデッドロック監視部
ｌＯを通過する正規のトークンのチェックサムがＸレジ
スタによって求められる。

（ステップＳ６）　　ステップＳ４での判別結果によっ
て、デッドロック監視部ｌＯに入力されたトークンがダ
ミートークンである場合は、Ｘレジスタの値（たとえば
第３図のＸ２）を今回のチェックサムとしてＸレジスタ
に格納する一方、Ｘレジスタから出力された値（前回の
チェックサム、たとえば第３図のＹｌ）と等しいかどう
かを判別する。

（ステップＳ７）　　判別結果がｘｆ−Ｙの場合は、計
数用レジスタＣＮＴをゼロにすると共に、Ｘレジスタの
値を今回のチェックサムＸに書き変え、ステップＳ３に
戻る。

つまり、上記のステップＳ６．Ｓ７の処理は、Ｘレジス
タの値とＸレジスタの値とを比較することによって、今
回のトークンのチェックサムが前回のトークンのチェッ
クサムと一致しているかどうかを判別し、異なる場合は
同じデータが流れていないわけであるから、デッドロッ
クは発生していないと判断して、デッドロックの監視を
引き続いて行うものである。

（ステップＳ８）　　ステップＳ６でＸレジスタの値が
Ｘレジスタの値に等しいと判断された場合、計数用レジ
スタＣＮＴに１をプラスする。

（ステップＳ９）　　計数用レジスタＣＮＴの値がレジ
スタＣＭＡＸの値Ｖと等しいかどうかを判断する。両方
の値が等しくない場合は、ステップＳ３に戻る。

つまり、上記のステップＳ８．Ｓ９の処理は、チェック
サムが連続して一致する場合、その連続するチェックサ
ム−数回数を所定の上限回数を表す基準値Ｖと比較し、
上記−数回数がまだその上限回数に達していなければ無
限ループはまだ発生していないものとして、デッドロッ
クの監視を続行するものである。

（ステップ５ＩＯ）　　計数用レジスタＣＮＴの値がレ
ジスタＣＭＡＸの値Ｖに等しくなると、デッドロック監
視部ＩＯは無限ループが発生したと見なして、デッドロ
ック判定信号を出力する。

このように、本実施例によれば、ステップＳｌでダミー
トークンを投入した後、デッドロック監視部ｌＯによっ
て上記のステップ８２〜ＳＩＯの処理を行うことにより
デッドロックを検出して外部に知らせることができるの
で、デッドロックに対して速やかに対処できる。したが
って、従来のように複雑なプログラムの調整を行う必要
がなくなる。

また、本実施例のプロセッサは、上記従来のプロセーＪ
すに単純なレジスタ構成を有するデッドロック監視部１
０を付加しただけなので、従来のプロセッサに比べて構
成が余り複雑にならず、したがって、コスト面でも問題
はない。

なお、本実施例においては、トークンデータのうち２バ
イトのアドレス情報を用いてチェックサムを算出したが
、チェックサム算出に用いるデータ量はこれに限るもの
ではない。

また、ダミートークンは外部からサーキュラ−バイブラ
インに投入する構成にしたが、サーキュラ−パイプライ
ン上のたとえばプログラム記憶部５等でダミートークン
を生成するようにしてもよい。

また、計数用レジスタＣＲＴはチェックサムが一致した
ときにｌをプラスしていき、計数値がレジスタＣＭＡＸ
に格納された所定値Ｖに達したとき、デッドロックの発
生と判定する構成にしたが、計数値レジスタＣＮＴの初
期値を上記所定値Ｖにしておいて、チェックサムが一致
したときに１ずつマイナスしていき、ゼロになったとき
デッドロックの判定を行うようにしてもよい。この場合
は、レジスタＣＭＡＸが不要になるので、レジスタ構成
がさらに簡素化される。

また、デッドロック監視部ＩＯの設置位置は本実施例に
限るものではなく、サーキュラ−パイプライン上であれ
ばよい。

〈発明の効果〉 以上の説明より明らかなように、本発明のデッドロック
検出方法によれば、ダミートークンの１周毎に正規のト
ークンのチェックサムをとり、チェックサムの変化の有
無を利用して、チェックサムの無変化の状態が所定回数
続いたときデッドロックを検出するようにしているので
、簡単にデッドロックを検出できる。ただし、チェック
サム利用のために、間違ってデッドロックを検出する可
能性もあるが、デッドロックの判定基準となる所定回数
を大きくとることで１００％に近い確率でデッドロック
を検出することができる。

また、本発明のデッドロック検出機構は、従来のプロセ
ッサの構成にデッドロック監視部を付加し、ダミートー
クンの１周毎に正規のトークンのチェックサムをとり、
チェックサムの変化の有無を利用して、チェックサムの
無変化の状態が所定回数続いたときデッドロックを検出
するようにしているので、簡単、安価な構成で、デッド
ロックを検出し、外部に知らせることができる。

【図面の簡単な説明】

第１図は本発明のデッドロック検出機構を備えたプロセ
ッサの概略構成図、第２図は第１図に示したデッドロッ
ク監視部のレジスタ構成を概略的に示す図、第３図はＸ
レジスタの値とＹレジスタの値の関係を示す図、第４図
は第１図のプロセッサを用いて行うデッドロック検出処
理の流れを示す図、第５図は従来のプロセッサの概略構
成図である。 ｌ・・・メモリ装置、２・・・演算処理部、３・・・ト
ークン分岐部、 ４・・・トークン待ち合わせ部、 ５・・・プログラム記憶部、 ６　ａ、　６　ｂ、　６　ｃ・・・トークン合流部、７
・・・トークン緩衝部、 １０・・・デッドロック監視部。

Claims (2)

【特許請求の範囲】
1. （１）自己同期型データフローマイクロプロセッサにお
   いて、ダミートークンをサーキュラーパイプライン上に
   周回させ、上記ダミートークンが上記サーキュラーパイ
   プラインの所定の箇所を通過した後再び通過するまでの
   間に上記箇所を通過するトークンのチェックサムを算出
   し、次に、今回算出したチェックサムと前回算出したチ
   ェックサムとが一致するかどうかを判別し、一致する場
   合はチェックサム一致回数として計数し、そうでない場
   合はいままでに計数された回数を初期値に戻すことによ
   って、同一のチェックサムが連続するチェックサム連続
   回数を求め、次に、上記チェックサム連続回数を所定値
   と比較し、同じ場合には同じトークンが上記サーキュラ
   ーパイプラインを周回し続けていると見なしてデッドロ
   ックを検出することを特徴とするデッドロック検出方法
   。
2. （２）自己同期型データフローマイクロプロセッサにお
   いて、ダミートークンが周回するサーキュラーパイプラ
   イン上にデッドロック監視部を設け、上記デッドロック
   監視部は、上記ダミートークンが上記デッドロック監視
   部を通過してから再び通過するまでの間に上記デッドロ
   ック監視部を通過するトークンのチェックサムを算出す
   るチェックサム算出部と、上記チェックサム算出部によ
   って算出されたチェックサムを格納するチェックサム格
   納部と、上記チェックサム格納部から出力されるチェッ
   クサムと上記算出部によって新たに算出されたチェック
   サムとが一致しているかどうかを判別するチェックサム
   一致判別部と、上記チェックサム一致判別部による判別
   結果に基づき、同一のチェックサムが連続する回数を計
   数する計数部と、上記計数部によって計数された値が所
   定値と等しくなったときデッドロックを判定して、デッ
   ドロック判定信号を出力するデッドロック判定部とを備
   えたことを特徴とするデッドロック検出機構。