JPS63314670A - マルチプロセッサシステムにおけるクロック同期方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、それぞれのプロセッサが共通にアクセスでき
る共有メモリを持たないマルチプロセッサシステムにお
いて、各々のプロセッサが時刻を示すために有するクロ
ックを互いに調整するためのクロック同期方式に関する
。

（従来の技術） マルチプロセッサシステムにおいては、システムを構成
する各°プロセッサ・のクロックをシステム全体に共通
な時刻を示すように同期させることが必要となる０例え
ば、分散ファイリングシステムにおいて、各ファイルに
記録された作成および編集時刻に基づきファイルのバー
ジョンを識別するためには、各プロセッサ間に共通な時
刻が必要となる。また、各プロセッサが、システムに共
通な時刻に基づき自己の履歴情報を蓄積しておけば、障
害発生時にどのような順番で障害が検出されたかを知る
ことができ、障害の発生箇所を特定するための有力な情
報を得ることができる。

共有メモリを持たないマルチプロセッサシステムの一例
である、通信ネットワークシステムにおいても、各通信
ノードのクロックが共通な時刻を示すようにする同期方
式が必要である。例えば、第６回インターナショナル　
コンファレンス　オン　ディストリビューティド　コン
ピユーテイング　システム（Ｉｎｔｅｒｎａｔｉｏｎａ
ｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎＤＩＳＴＲＩＢＵＴＥ
Ｄ　ＣＯＭＰＬＩＴＩＮＧ　ＳＹＳＴＥＭＳ）の予稿集
９．３６４−３７１に記載されている論文「アン　エレ
クションアルゴリズム　フォー　ディストリビューティ
ドクロック　シンクロナイゼイション　プログラム　（
＾ｎ　　Ｅｌｅｃｔｉｏｎ　　Ａｌｇｏｒｉｔｈｍ　　
ｆｏｒ　　ａ　　ＤｉｓｔｒｉｂｕｔｅｄＣｌｏｃｋ　
５ｙｎｃｈｒｏｎｉｚａｔｉｏｎ　Ｐｒｏ＠ｒａｍ）Ｊ
　　（文献１）で紹介されているクロック同期方式ＴＥ
ＭＰＯは、ＬＩＮＩＸオペレーティングシステム４．３
　ＢＳＤで動作するネットワークにインプリメントされ
ているものである。上述のシステムにおいては、マスク
となる１つのノードが、定められた時間毎にすべてのノ
ードに時刻の問い合せを行い、求められた各ノードの時
刻をもとに平均時刻を計算する。この後すべてのノード
に対してクロックの調整指示を行い、各ノードはこの指
示に従いクロックの調整を行う。

また、第１６回アニュアル　インターナショナル　シン
ポジウム　オン　フォールト　トレラント　コンピユー
テイング（Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ
Ｓｙｍｐｏｓｉｕｍ　ｏｎ　ＦＡＵＬＴ−ＴＯＬＥＲＡ
ＮＴ　ＣＯＭ、ＰＵＴＩＮＧ）のダイジェストペーパー
ｐ、２１Ｂ−２２３に記載されている論文「クロック　
シンクロナイゼーション　インザ　プレゼンス　オン　
木ミッション　アンドパフォーマンス　フォールツ、ア
ンド　プロセッサ　ジョインズ（ＣＬＯＣＫ　５ＹＮＣ
ＨＲＯＮＩＺＡＴＩＯＮ　ＩＮ　ＴＨＥＰＲＥＳＥＮＣ
Ｅ　ＯＦ　０Ｍｌ５ＳＩＯＮ　ＡＮＤ　ＰＥＲＦＯＲ）
！ＡＮＣＥ　ＦＡＵＬＴＳ。

ＡＮＤ　ＰＲＯＣＥＳＳＯＲＪＯＩＮＳ）Ｊ　　（文献
２）で紹介されているクロック同期方式は、上で説明し
た“ＴＥＭＰＯ”のようにマスク・スレーブ型の制御で
はなく分散型の制御を用いている。同方式において、プ
ロセッサはシステム内で定期的に同報される同期メツセ
ージの中で、最も速い時刻を示す同期メツセージに従い
クロックの時刻合せを行なう、このため、結果として最
も速く進むクロックがシステム内の時刻を支配すること
になる。

さらに、ジャーナル　オン　アソシエーションフォー　
コンピユーテイング　マシナリー（Ｊｏｕｒｎａｌ　ｏ
ｆ　Ａｓ５ｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔｉ
ｎｚ　Ｍａｃｈｉｎｅｒｙ）　Ｖｏｌ、３２．　Ｎｏ、
１．　Ｊａｎｕａｒｙ　１９８５．　ｐ、５２−７８に
記載されている論文「シンクロナイズイング　りロック
ス　イン　ザ　プレズンス　オン　フォールツ（Ｓｙｎ
ｃｈｒｏｎｉｚｉｎｇ　Ｃ１ｏｃｋｓ　ｉｎ　ｔｈｅ　
Ｐｒｅｓｅｎｃｅ　ｏｆＦａｕｌｔｓ）Ｊ（文献３）で
紹介されているクロック同期方式は、すべてのプロセッ
サが定期的に互いのプロセッサの時刻を通信しあう完全
分散制御による同期方式である。

（発明が解決しようとする問題点） 上述のＵＮＩＸオペレーティングシステム４．３　ＢＳ
ＤのＴＥＭＰＯの同期方式においては、マスタノードが
必要不可欠である。このため、マスタノードの障害時に
は、他のノードがマスタノードの機能を果すように、マ
スタノードの代行の方法が必要となる。また、すべての
ノードのクロックの問い合せ等を１つのマスタノードが
行うために、ノードの数が増えると、マスタノードへの
通信量が増加するとともに、すべてのノードの時刻の平
均を求める作業が増大する。

これに対し、分散型の制御を採用している文献２記載の
方式では、分散型ではあるものの、最も速いクロックを
もつ１つのプロセッサがシステム内の時刻を支配する結
果となる。また、文献３の方式は、すべてのプロセッサ
が互いにすべてのプロセッサと通信を行なうために、実
際のシステムに適用する場合に通信のオーバヘッドが問
題となる。

本発明においては、集中制御を行なうプロセッサを設け
る必要がなく、システム内のプロセッサ数が増加した場
合にも、通信のメツセージがあるプロセッサに集中する
ことがないとともに°、システム内の総メツセージ数を
従来方式より削減することが可能な分散制御型のマルチ
プロセッサシステムにおけるクロック同期方式を提供す
ることにある。

（問題を解決するための手段） 本発明によれば、ｎ個のプロセッサからなるマルチプロ
セッサシステムのクロック同期方式において、前記プロ
セッサは、時刻を示すクロックを具備し、前記クロック
が予め定められた時刻を示す時に、前記ｎ個のプロセッ
サの中がらｍ個のプロセッサをランダムに選択して該ｍ
個のプロセッサのクロック情報を読み出し、該ｍ個のプ
ロセッサの時刻に基づき前記クロックを制御することを
特徴とするマルチプロセッサシステムにおけるクロック
同期方式が得られる。

（作用） 本発明の原理について、第３図を参照して説明する。第
３図は、マルチプロセッサシステムの具体例を示す、各
プロセッサ３０１，３０２．３０３，３０４，３０５は
、自己の時刻を示すクロックを備えている。さらに各プ
ロセッサは任意のプロセッサのクロック情報を読み出せ
るよう、相互に論理的な通信路３０６により接続されて
いる。互いのプロセッサが共通にアクセスできる共有メ
モリを持たないマルチプロセッサシステムにおいては、
システムが初期状態の時に、各プロセッサのクロックは
同一の時刻を示してはいない、しかも同じ値からスター
トしたクロックも、凡そ同じ割合で時刻を測定するもの
の、時刻の経過にともない徐々にずれて行く、従って、
各プロセッサは以下に説明する本同期方式に従い、メツ
セージ通信により互いにクロックの調整を行う、この結
果、すべてのプロセッサのクロックがある同期精度の範
囲内で同一の時刻を指すように制御される。

本同期方式では、各プロセッサは、自プロセッサのクロ
ックが予め決められた時刻になる毎に、システム内のｎ
個のプロセッサの中からｍ個のプロセッサをランダムに
選択し、同プロセッサのクロック情報を問い合せる。さ
らに、これら問い合せたクロック情報に基づき自分のク
ロックの値を再設定する。例えば、プロセッサ３旧は自
己のクロックが１：００．２：００．３：００、という
ように定められた時刻になる毎に、システム内の５つの
プロセッサの中から、ランダムにプロセッサを選択する
。プロセッサ３０１は、ある時、プロセッサ３０２゜３
０２、３０４を選択し、通信路３０６を介してこれらプ
ロセッサにクロック値を問い合せる。プロセッサ３０１
は、得られた３個のプロセッサのクロック値に基づき、
これらクロック値の平均値を計算し、該平均値をもとに
自分のクロックの値を再設定する。例えば、３個のプロ
セッサの時刻の平均値が自分のクロックの示す時刻より
もδ進んでいる場合は自分のクロックに該差分δを加算
し、該３個のプロセッサの時刻の平均値が自分のクロッ
クが示す時刻よりもδ遅れている場合は、自分のクロッ
クをδ停止させる。以上の操作は、すべてのプロセッサ
が、自分のもつクロックが予め定められた時刻になる毎
に繰り返し行う。

このようにすべてのプロセッサは、完全対等な立場にあ
り全く同一のアルゴリズムを実施する。

この時、各プロセッサはｍ個のプロセッサのクロック情
報をもとに同期制御を行なうため、従来に比べ通信量を
削減することができる。しかもこの際にｍ個のプロセッ
サはランダムに選択されるため、同期制御を繰り返し行
なうことにより、システム内のすべてのプロセッサのク
ロック情報が同期制御に反映される。模擬実験により、
プロセッサのクロックの同期範囲が、ｎの値には依存せ
ずｍ＝２〜１０で充分な同期精度を満足するように収束
することを確認した。

以上のように、特定のプロセッサが共通時刻を定義し同
期制御を実施することがないため、あるプロセッサの障
害がシステムに致命的な障害をもたらすことがない。

（第１の実施例） 第１図（ａ）および（ｂ）に、本発明によるクロック同
期方式を実現するアルゴリズムの第１の実施例を示す。

第１図（ａ）は、プロセッサが自分のクロックが予め定
められた時刻を示した時に実行する同期制御アルゴリズ
ムであり、例えば、自己のクロックが１＝００．２：０
０．３：００、というようにある定められた時刻になる
毎に実行される。第１図（ｂ）は、あるプロセッサが前
記同期制御アルゴリズムを実行し、同プロセッサからの
メツセージを受信した時に、実行されるアルゴリズムを
示す。なお、これら２つのアルゴリズムは並列に実行さ
れるとともに、自分自身に対するクロック情報の送信要
求が発生してもかまわない。

プロセッサは、自分のクロックが予め定められた時刻に
なると発生するように設定されたクロックからの割込み
を、第１図（ａ）に示す制御ブロック１０１において検
出する。このクロックからの割込みの検出により、以降
の同期制御アルゴリズムが起動される。すなわち、制御
ブロック１０２においては、ｎ個のプロセッサの中から
ランダムにｍ個のプロセッサを選択し、引続き制御ブロ
ック１０３ではこれら各プロセッサにクロック情報の送
信を要求するメツセージを送信する。

各プロセッサは、第１図（ｂ）に示したアルゴリズムも
並列に実行しており、同図の制御ブロック１１０では、
プロセッサからのクロック情報の送信要求メツセージの
受信時に発生する受信割込みが検出することができる。

つまり、あるプロセッサが第１図（ａ）の制御ブロック
１０３にてメツセージを送信すると、該メツセージを受
信したプロセッサは第１図（ｂ）の制御ブロック１１０
にて、受信割込みを検出し、続いて第１図（ｂ）の制御
ブロック１１１において該メツセージの送信元プロセッ
サにクロック情報を送信する。この時にプロセッサが送
信するクロック情報は、クロックの示す値自身とするが
、クロック情報を要求するプロセッサが該要求メツセー
ジに自分の時刻を記録するものとすると、該要求プロセ
ッサの時刻との差分をタロツク情報として送信してもか
まわない。

このように、クロック情報の送信要求メツセージを送信
したプロセッサは、ｍ個のプロセッサからクロック情報
を受信する。続く制御ブロック１０４においては、これ
らｍ個のプロセッサのクロック情報に基づきｍ個のプロ
セッサの平均クロック値を計算し、自プロセッサのクロ
ックが示す時刻から該ｍ個のプロセッサの平均時刻を差
引き、差分δを求める。

プロセッサは以上のよう゛にして求めたｍ個のプロセッ
サの平均時刻との差分δに基づき、制御ブロック１０５
以降において次に説明するように自分のクロックの値を
設定する。すなわち、自プロセッサのクロックが示す時
刻が該平均時刻に等しい場合（δ＝０）には、制御ブロ
ックに１０１に戻る。また、該平均時刻よりも自分のク
ロックが示す時刻が遅れている場合（δく０）には、制
御ブロック１０６において自分のクロックに該差分δを
加算して時刻を進めた後に制御ブロック１０１に戻る。

さらに、該平均時刻よりも自分のクロックが示す時刻が
進んでいる場合（δ〉０〉には、制御ブロック１０７に
おいて自プロセッサ内のタイマに該誤差δを設定し、制
御ブロック１０８において、タイマが時間δの経過を通
知するまでクロックを停止させる。このようにして時刻
を遅らせた後に制御ブロック１０１に戻る。いずれの場
合にも制御ブロック１０１では、定められた時刻に発生
する次のクロックからの割込みを検出する。

以上説明したアルゴリズムはすべてのプロセッサが実行
する。

（第２の実施例） 第２図（ａ）および（ｂ）に、本発明によるクロック同
期方式を実現するアルゴリズムの第２の実施例を示す。

マルチプロセッサシステムの一例である通信ネットワー
クシステムにおいては、プロセッサが互いに他のクロッ
ク情報を読み出す場合に、プロセッサ間の通信遅延、も
しくは通信処理・平均時刻の計算に必要な時間がクロッ
クの時間精度に比べて大きくなることが考えられる。ク
ロックの同期制御にこのような処理オーバヘッドによる
悪影響を与えないようにするために、次に説明するよう
なアルゴリズムを用いてクロック情報を読み出したプロ
セッサの時刻を定義する。

第２図（ａ）および（ｂ）は、同アルゴリズムを示して
いる。ここに示したアルゴリズムは、すでに説明した第
１図（ａ）の制御ブロック１０２，１０３および１０４
に相当するアルゴリズムであり、具体的には、プロセッ
サをランダムに選択するとともに、同プロセッサにクロ
ック情報の送信を要求するメツセージの送信をｍ回繰り
返し行ない、さらに逐次受信されるこれらｍ個のプロセ
ッサからのクロック情報に基づき、自プロセッサのクロ
ックが示す時刻と平均時刻との差分δを求める制御を示
している。なお、第２の実施例において、第２図＜ａ）
および（ｂ）以降の制御手、順は、第１図（ａ）の制御
ブロック１０５以下の手順と同一である。

第２図（ａ）に示す結合子２００は、第１図（ａ）の制
御ブロック１０１の後部に接続される。制御ブロック２
０１において、選択すべきプロセッサの数を計数する変
数ｋに値０を代入し、制御ブロック２０２においてシス
テム内のｎ個のプロセッサからランダムにプロセッサｉ
を選択する。続いて制御ブロック２０３において、この
時に自プロセッサ内のクロックが示す時刻を変数Ｔｉ、
０に代入するとともに、制御ブロック２０４において該
プロセッサｉにクロック情報の送信を要求するメツセー
ジを送信する。この後制御ブロック２０５においてラン
ダムに選択したプロセッサ数を計数する変数ｋに１を加
える。制御ブロック２０６において変数ｋを値ｍと比較
し、ｋ＜ｍならば再び制御ブロック２０２に戻り、ｋ＝
ｍならば次の処理に接続される結合子２０７へと続く。

結合子２０７は、第２図（ｂ）に示す制御ブロック２０
８の前部に接続される。制御ブロック２０８では、第２
図（ａ）で説明したようにｍ個のプロセッサに対して送
信したクロック情報の要求メツセージに対する応答を待
っている。該要求メツセージの送信時刻のばらつきおよ
び通信遅延のばらつきにより各プロセッサからの応答の
到着もまちまちとなる。あるプロセッサｉからの応答が
到着すると、制御ブロック２０９において、該応答が到
着した時刻を変数Ｔｉ、１に代入し、さらに制御ブロッ
ク２１０において該応答メツセージの中に記録されたプ
ロセッサｉの時刻を変数Ｔｉに代入する。この後ランダ
ムに選択し、前記要求メツセージを送信したプロセッサ
数を記憶した変数ｋから１を差引き、制御ブロック２１
２において該変数にの値を比較し、ｋ＞Ｏならば制御ブ
ロック２０Ｂに戻って他のプロセッサからの応答を待ち
、すべてのプロセッサからの応答を受信゛し、ｋ＝ｏで
あるならば、制御ブロック２１３を実行する。なお、メ
ツセージの紛失等により一定時間経過してもすべてのプ
ロセッサからの応答が得られない場合が生ずる。この場
合、すでに得られているクロック情報をもとに制御ブロ
ック２１３を実行してもかまわない、同制御ブロック２
１３では、プロセッサｉを選択した時の時刻を示す変数
Ｔｉ、Ｏとプロセッサｉからの応答が到着した時刻を示
す変数Ｔｉ、１およびプロセッサｉからの応答メツセー
ジの中に記録されたプロセッサｉの時刻を示す変数Ｔｉ
をもとに、自プロセッサが時刻Ｔｉ、０の時のプロセッ
サｉの時刻を予測し、プロセッサｉの時刻と自プロセッ
サの時刻の差分δｉを求める。つまり、プロセッサａが
ちプロセッサｉへのメツセージの通信遅延とほぼ同時に
送信されたプロセッサｉからプロセッサａへのメツセー
ジの通信遅延は等しいと仮定し、次式に従いプロセッサ
ｉの時刻を予測する。

Ｔｉ　−＜Ｔｉ、１−　Ｔｉ、０）／２　　　　　　　
　　　　　　　　　　　（１１従って自プロセッサのク
ロックが示す時刻とプロセッサｉのクロックが示す時刻
の差分δｉは次のように示される。

δｉ　＝Ｔｉ、０−　（Ｔｉ　−（Ｔｉ、１−Ｔｉ、０
）　／２）　　（２１制御ブロツク２１４においては、
このようにして求めたｍ個のδｉの平均値を計算し、同
値がランダムに選択されたｍ個のプロセッサの平均時刻
との差分δであるとする。なお、結合子２１５は、第１
図（ａ）の制御ブロック１０５の前部に接続される。

以上のように求めた平均時刻との差分δをもとに、すで
に説明した第１図（ａ）の制御ブロック１０５以降の手
順を実施する。このアルゴリズムでは、プロセッサ間の
通信遅延を考慮してプロセッサの時刻を予測しており、
通信遅延による影響を除くことが可能である。

（発明の効果） このように、本発明のクロック同期方式を用いることに
より、マルチロセッサシステムにおいて、集中制御を行
なうプロセッサを設けることなく、すべてのプロセッサ
を対等に動作させて、各プロセッサのクロックをある範
囲内で共通な時刻を指すように制御することができる。

集中制御を行なうプロセッサが不要であるために、特定
のプロセッサの障害がシステムに致命的な障害を与える
ことがなく高い信頼性が確保できる。また、各プロセッ
サが必要とする情報は、ｍ個のプロセッサの時刻情報だ
けでよく、模擬実験によれば、ｍ＝２〜１０で充分な同
期精度が得られる。従って、すべてのプロセッサのクロ
ック情報を集める必要がないため、プロセッサ数が増え
た場合にも同期制御に要する処理時間が増大することは
ない。しかも、これらプロセッサは周期的にランダムに
選択されるために、すべてのプロセッサのクロック情報
をもとにして同期制御が実施される。

以上のように本発明により得られる効果は大きい。

【図面の簡単な説明】

第１図（ａ＞、（ｂ）は、本発明による第１の実８１例
を示す流れ図５．第２図（ａ）、（ｂ）は通信遅延を考
慮した場合の第２の実施例におけるプロセッサの時刻を
求めるためのアルゴリズムを示す図、第３図は、マルチ
プロセッサシステムの一例を示す図である。 図において、１０１〜１１１、および２０１〜２１４は
制御ブロック、２００．２０７．２１５は結合子、３０
１〜３０５はプロセッサ、３０６はプロセッサ間の論理
的な通信路を示第１図（ａ） 第１図（ｂ） 第　２　図　（ａ） 第２図（ｂ）

Claims (1)

1. 【特許請求の範囲】 １、ｎ個のプロセッサからなるマルチプロセッサシステ
   ムのクロック同期方式において、前記プロセッサは、時
   刻を示すクロックを具備し、前記クロックが予め定めら
   れた時刻を示す時に、前記ｎ個のプロセッサの中からｍ
   個のプロセッサをランダムに選択して該ｍ個のプロセッ
   サのクロック情報を読み出し、該ｍ個のプロセッサの時
   刻に基づき前記クロックを制御することを特徴とするマ
   ルチプロセッサシステムにおけるクロック同期方式。 ２、前記プロセッサは、任意時間の経過を測定できるタ
   イマを具備し、前記ｍ個のクロック情報に基づき求めら
   れるｍ個のプロセッサの平均時刻が、自分のクロックの
   示す時刻よりもδ進んでいる場合は自分のクロックにδ
   を加算し、該ｍ個のプロセッサの平均時刻が自分のクロ
   ックの示す時刻よりもδ遅れている場合は、前記タイマ
   が時間δの経過を通知するまで自分のクロックを停止さ
   せることを特徴とする特許請求の範囲第１項記載のマル
   チプロセッサシステムにおけるクロック同期方式。