| 摘要: | 所謂系統偵錯(system-level diagnosis)是透過系統內處理機(processor)相互測試，診斷出有誤的(faulty)處理機。最常見的測試模式為PMC模式。在PMC模式中，每一次的單一測試都有一個施測處理機與一個受測處理機。施測處理機可送測試資料給相連的受測處理機。受測處理機根據測試資料執行約定的計算並將結果傳回施測處理機。最後施測處理機判斷受測處理機回傳的結果並宣布測試結果為：受測處理機為有誤或是無誤(fault-free)。同時，PMC模式假設: 無誤的施測處理機斷所宣佈的測試結果可信賴，而有誤施測處理機所宣佈的測試結果不可信賴。為了達到偵錯的目的，系統中所有的處理機分別對其相連的處理機(鄰居處理機)進行測試，稱為全面測試。亦即一次全面測試包含許多單一測試。一次全面測試中所有單一測試的測試結果集合起來，稱之為症狀(syndrome)。根據症狀，偵錯演算法可診斷出系統中有誤的處理機。為了因應各種不同應用的需求，亦有不同的偵錯策略。目前被廣泛地研究與討論的是循序偵錯(sequential diagnosis)和(t, k)偵錯((t, k)-diagnosis)。循序偵錯要求根據症狀，診斷出一個以上有誤的處理機。被診斷為有誤的處理機會進行修復或替換，接著再進行下一次的全面測試得到新的症狀、然後診斷出有誤處理機，重覆此過程直到所有有誤的處理機都被診斷出來。(t, k)偵錯推廣了循序偵錯。它要求根據症狀，診斷出至少k個有誤的處理機或全部有誤的處理機(當系統中有誤的處理機數量小於k時)。目前文獻中的偵錯演算法的演算法偵錯度往往遠低於系統偵錯度。所謂演算法偵錯度是指該偵錯演算法可正確診斷某系統時，此系統最多可有之有誤處理機數量。若此系統中有誤處理機數量超過該演算法偵錯度，則該演算法無法正確診斷此系統。而系統偵錯度(或稱為偵錯度)是指系統最大可容忍之有誤處理機的數量。當系統中有誤處理機的數量高於系統偵錯度，則不存在任何偵錯演算法可正確診斷該系統。在本研究中，我們試著在PMC模式下針對格子圖設計一個“高＂演算法偵錯度的(t, k)偵錯演算法。希望藉由格子圖的研究經驗，設計出適合其他常見系統的高演算法偵錯度的偵錯演算法。 ; System-level diagnosis aims to identify faulty processors in a multiprocessor system by analyzing the outcomes of available interprocessor tests. The PMC model, which was originally introduced in [2], is possibly the most well-studied model for system-level diagnosis. It assumes that each processor can test its neighboring processors and declare them fault-free or faulty. The test results are considered reliable if the processor is fault-free. Let u, v denote two neighboring processors. If u is fault-free, then u declares v fault-free (faulty) if v is fault-free (faulty). The collection of all test result is called the syndrome. There are three fundamental diagnosis strategies, i.e., one-step diagnosis [2], sequential diagnosis [2] and (t, k)-diagnosis [1], for system-level diagnosis. By the aid of syndrome, in one-step diagnosis, all faulty processors are identified before replacement (or repair) is made; in sequential diagnosis and (t, k)-diagnosis, faulty processors are identified and replaced iteratively. Differently, in each iteration, at least one faulty processor is identified and replaced in sequential diagnosis, whereas at least k faulty processors (or all faulty processors if fewer than k faulty processors remain) are identified and replaced in (t, k)-diagnosis provided there are at most t faulty processors, where t ≥ k. Notice that one-step diagnosis (when t=k) and sequential diagnosis (when k=1) are two instances of (t, k)-diagnosis. On the other hand, each (t, k)-diagnosis process is guaranteed to require at most (t/k + 1) iterations. Hence, (t, k)-diagnosis is more practical than sequential diagnosis. Determining diagnosability and designing diagnosis algorithms are two most important issues. Given a system S. The diagnosability of S is the maximum number of faults of S that can be identified. And a diagnosis algorithm for S is an algorithm that can identify all faulty processors in S. The diagnosability of S corresponding to a specific diagnosis algorithm A is the maximum number of faults of S that can be identified by A. Based on our observation, the diagnosabilities of S corresponding to previous diagnosis algorithms are much lower than the diagnosability of S. In our plan, we study the problem of designing a precise (t, k)-diagnosis algorithm satisfying that the diagnosability for girds corresponding to it is higher than previous diagnosis algorithm’s. Based on the result of grids, some other popular systems are also investigated. Reference [1] T. Araki and Y. Shibata, ``(t, k)-diagnosable system: a generalization of the PMC models,'' IEEE Transactions on Computers, vol. 52, no. 7, pp. 971-975, 2003. [2] F. P. Preparata, G. Metze, and R. T. Chien, ``On the connection assignment problem of diagnosable systems,'' IEEE Transactions on Electronic Computers, vol. 16, pp. 848-854, 1967. ; 研究期間 9708 ~ 9807 |
