多處理機系統的局部偵錯診斷研究

Abstract

我近期的研究著重在多處理器系統上的偵錯診斷，以及連結網路的容錯子架構之嵌 入。過去幾年間，我的實驗室有九位博士班學生畢業，並且發展出許多研究主題，近五 年內這些成果發表有25 篇國際期刊論文。 在這個計畫中，我們將延續之前的研究，繼續針對多處理器系統上的偵錯能力作深 入的探討，例如幾項我們定義出來的新概念：強診斷系統、條件式診斷能力、以及局部 診斷能力等等。就在今年和去年，我和我所指導的博士班學生也以這幾項新概念發表了 三篇論文刊登在IEEE Transaction on Computer 期刊之上。 為了做到系統的自我診斷，過去的文獻提出了一些診斷模式。Preparata, Metze, and Chien 針對多處理器系統上的系統層診斷狀態，提出一個現在名為PMC 的診斷模型 (PMC model)。而這個診斷模型是以系統中每兩個處理器之間相互作測試為主要的基 礎。 另外，Maeng and Malek 也提出了一個實用的診斷模型，名為比較模型(comparison model) 或MM 模型。在這個模型下，系統由某一個處理器向相連的處理器散發出測試 訊息，再將返傳回來的測試訊息兩兩作比較。在這個狀態之下，這個處理器可稱為另外 兩個被測試處理器之訊息比較者(comparator)；若訊息比較者本身是好的，回傳的測試 訊息就能指出被測試處理器的好壞狀態。以此概念為基礎，另一個延伸的MM*模型則 將系統中所有訊息完全蒐集，再進而偵測所有處理器的好壞狀態。之後，Sengupta and Dahbura 研究了MM 模型和MM*模型，討論有關比較模型之下的系統診斷狀態，並提 出一個能在多項式時間(O(n^5))內完成的演算法來偵測多處理器系統或連結網路中的所 有損壞狀況。 在這個計畫當中，我們將以最近剛研發出來的新概念來探討多處理器系統中的局部 診斷能力，而這個稱之為「局部診斷能力」的新概念則是相對於傳統的全域診斷概念。 我們還提出一個更有效率(O(nlogn))的演算法來作偵錯診斷。在此同時，我們也有一些 新研究成果是關於容錯迴圈(fault-tolerant cycle)和容錯路徑(fault-tolerant path)與連結 網路之間之嵌入性。這些結果也正在修正整理當中，並且預計在近期內再次投稿於國際 期刊IEEE Transaction on Computers。

My recent research focuses on the fault-diagnosis of multiprocessor systems and fault-tolerant substructure embedding of interconnection networks. There are 9 PhD students graduated from my lab in the past several years.We, together with my students, have developed several research topics and published over 25 international journal papers within the last 5 years. In this proposal, we plan to continue our studies on diagnosis problem of multiprocessor systems.We have defined several new concepts; such as strongly t-diagnosable systems, conditional diagnosability, and local diagnosability. I, supervised my PhD students, have already published 3 journal papers on these topics, all in IEEE Transaction on Computers last years. For the purpose of self-diagnosis of a given system, several different models have been proposed in literature. Preparata, Metze, and Chien first introduced a model, so called PMC-model, for system level diagnosis in multiprocessor systems. In this model, it is assumed that a processor can test the faulty or fault-free status of another processor. The comparison model, called MM model, proposed by Maeng and Malek, is considered to be another practical approach for fault diagnosis in multiprocessor systems. In this approach, the diagnosis is carried out by sending the same testing task to a pair {u, v} of processors and comparing their responses. The comparison is performed by a third processor w that has direct communication links to both processors u and v. The third processor w is called a comparator of u and v. If the comparator is fault-free, a disagreement between the two responses is an indication of the existence of a faulty processor. To gain as much knowledge as possible about the faulty status of the system, it was assumed that a comparison is performed by each processor for each pair of distinct neighbors with which it can communicate directly. This special case of MM-model is referred to as the MM*-model. Sengupta and Dahbura studied the MM-model and the MM*-model, gave a characterization of diagnosable systems under the comparison approach, and proposed a polynomial time (O(n^5)) algorithm to determine faulty processors under MM*-model. In this project, we study the local diagnosis problem of multiprocessor systems using our newly defined concept; local diagnosability of a node as oppose to the traditional global diagnosability. We obtain an O(nlogn) algorithm to determine all the faulty processors ..In the mean time, we also have some new results on fault-tolerant cycle and path embedding of interconnection networks We are currently writing papers on local diagnosability and plan to submit our new result to IEEE Transaction on Computers.