MM*模式之系統偵錯問題; System Level Diagnosis under the MM* Model

NCU Institutional Repository > 資訊電機學院 > 資訊工程學系 > 研究計畫 > Item 987654321/45983

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/45983

題名:	MM模式之系統偵錯問題;System Level Diagnosis under the MM Model
作者:	張貴雲
貢獻者:	資訊工程系
關鍵詞:	系統偵錯;症狀;偵錯度;偵錯策略;資訊科學--軟體
日期:	2008-07-01
上傳時間:	2010-12-28 15:55:40 (UTC+8)
出版者:	行政院國家科學委員會
摘要:	所謂系統偵錯(system-level diagnosis)是透過系統內處理機(processor)相互測試的結果，找出有誤的(faulty)處理機。顯然地，系統的硬體條件將會影響處理機之間的測試。MM模式是目前最常見的假設之一。MM 模式假設任一個處理機(測試者)可同時送測試資料給二個與它相連的處理機(受測者)。這二個受測者分別將測試資料執行約定的計算並將結果傳回測試者。最後測試者比較二個受測者回傳的結果宣佈測試結果為：受測者皆無誤或是至少一個有誤。若二個受測者回傳的結果相同，則二個受測者皆為無誤，否則至少有一個受測者是有誤的。同時，MM模式假設: 無誤的測試者才能保證測試結果的正確性。若測試者有誤，即使二個受測者皆無誤，測試者仍可能宣佈測試結果為至少一個受測者有誤。另外，對系統中所有未知狀態(有誤或無誤)的處理機進行測試，稱為完整測試。一次完整測試中所有測試結果集合起來，稱之為症狀(syndrome)。為了因應各種不同應用的需求，亦有不同的偵錯策略。最常見的是考慮找出的有誤處理機數量。包括一步偵錯(one-step diagnosis)、循序偵錯(sequential diagnosis)和(t, k)偵錯((t, k)-diagnosis)。一步偵錯要求根據症狀，找出所有有誤的處理機。循序偵錯要求根據症狀，找出一個以上有誤的處理機。被找出的有誤處理機會進行修復或替換，接著再進行下一次的完整測試得到新的症狀、然後找出錯誤處理機，重覆此過程直到所有有誤的處理機都被找出來。(t, k)偵錯推廣了循序偵錯。它要求根據症狀，找出至少k個有誤的處理機或全部有誤的處理機(當系統中有誤的處理機數量小於k時)。另外一類的偵錯策略考慮找出的處理機是否被誤認。其中準確偵錯(precise diagnosis)要求找出的處理機必是有誤的處理機，也就是不允許誤認；而悲觀偵錯(pessimistic diagnosis)要求找出的處理機中大部分是有誤的，但允許有小部分是無誤的，也就是允許少部分的誤認。系統偵錯方面的研究有三個主要的議題: 偵錯度(diagnosability)、偵錯演算法(diagnosis)、和特性描述(characterization)。其中偵錯度和偵錯演算法是目前主要的研究方向。偵錯度是指系統容許有誤處理機的最大數量。一旦系統中有誤處理機的數量超過偵錯度，則系統便無法進行偵錯。在本研究中，我們計畫研究的是MM模式的準確(t, k)偵錯度。過去，一步偵錯的偵錯度曾被廣泛地研究與討論，但由於一步偵錯的偵錯度必小於等於該系統的連結度(connectivity)，所以對大型的處理機系統並不是實用的偵錯策略。而循序偵錯是(t, k)偵錯的特例，所以我們考慮更複雜的(t, k)偵錯的偵錯度問題。我們首先考慮求出格子圖(grid)在MM*模式下準確偵錯策略之(t, k)偵錯的偵錯度。並期望可以推廣至格子圖的變形系統(如：圓環面tori)的偵錯度問題。研究期間：9608 ~ 9707
關聯:	財團法人國家實驗研究院科技政策研究與資訊中心
顯示於類別:	[資訊工程學系] 研究計畫

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	442	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....