多處理機的診斷錯誤之研究(I)

Abstract

在這個計劃中，我們要延續過去幾年的成果，研究multiprocessor systems 的錯 誤診斷問題(fault diagnosis problem)。關於多處理機系統的錯誤自我診斷問題，在 文獻中已有幾個不同的模式被提出。Preparata, Metze and Chien 三人最早提出一種 構想及模式。現在稱為PMC-Model。在此模式下，兩個相連接的processor 可以互相偵 測是否faulty。Maeng and Malek 在之後提出一種comparison model 稱為MM-model。 他們對錯誤診斷的基本構想是由一個processor向相鄰的兩個processors送出信號，然 後由回收的訊號，比較並判斷是否有fault。為了要收集到最多的資料以供錯誤診斷， 在MM*-model 下,規定任一個processor 都對其所有相鄰的兩個processors 作偵測及 比較。 錯誤診斷在IEEE Trans. on Computers 及IEEE Trans. on Parallel and Distributed Systems 已有很多文獻研究。我們近年帶領博士班學生也在這個領域作了一些深入研 究．在這些主題上，我們今年(2004)年已有四篇論文年被IEEE Trans. on Computers接 受刊登。 在這個計畫中，我們將繼續研究multiprocessor system 的diagnosis problem．我 們定義出一種新觀念，稱之為strongly t-diagnosable systems .並探討有條件情況 下的診斷能力(conditional diagnosability)．我們對hypercubes 及hypercube-like family 已作了初步的探討獲致很好的結果．未來計畫將這個研究主題拓展到其他的連 接網路． 在以往的diagnosability 研究，我們觀察出是隱含了一種全域（global）性質的診 斷能力研究．這種傳統的定義,對點對稱(node symmetric)的網路是能有效的研究．但 對不是點對稱的網路，或發生有些連線壞了的網路就會產生問題．因此我們提出一種 局部診斷能力（ Local diagnosability）的觀念及定義．我們也將在這個計畫中，對 這個觀念做出具體的結果．