共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合せプロトコル(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)

概要

論文の詳細を見る
共有メモリマルチプロセッサシステム, 特に, システム内のすべてのプロセッサが大域パルスを共有するフェーズ内システムにおける故障耐性をもつ時計合せプロトコルを考察する.フェーズ内システムでは, 正常なプロセッサはパルス発生時に同期して動作を行う.フェーズ内システムにおいて, パルス発生時にプロセッサが動作しないような故障を居眠り故障と呼ぶ.居眠り故障の起こるフェーズ内システムにおいて, 同期時間と呼ばれるある特定パルス以上正常に動作し続けているすべてのプロセッサ同士の局所時計の時刻を一致させるプロトコルを無待機時計合せプロトコルと呼ぶ.これまで, フェーズ内システムにおける無待機時計合せプロトコルとして, 同期時間4n~2-3n-1のプロトコルが提案されていた(n:プロセッサ数).本論文では, 同期時間12nの無待機時計合せプロトコルを提案する.また, 無待機時計合せプロトコルの同期時間の下界がn-1であることを証明し, 本論文で提案するプロトコルが同期時間に関してオーダ的に最適であることを示す.
社団法人電子情報通信学会の論文
2000-01-25