PMC 模式準確(t,k)---偵錯度問題;(t,k)-Diagnosabilities under the PMC Model

NCUIR > College of Electrical Engineering & Computer Science > Department of Computer Science and information Engineering > Research Project > Item 987654321/45338

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/45338

Title:	PMC 模式準確(t,k)---偵錯度問題;(t,k)-Diagnosabilities under the PMC Model
Authors:	張貴雲
Contributors:	資訊工程學系
Keywords:	資訊科學--軟體
Date:	2007-07-01
Issue Date:	2010-12-21 17:33:33 (UTC+8)
Publisher:	行政院國家科學委員會
Abstract:	所謂系統偵錯是透過系統內處理機(processor)相互測試的結果，找出有誤的(faulty)處理機。顯然地，系統的硬體條件將會影響處理機之間的測試。PMC 模式是目前最常見的假設。PMC 模式假設任一個處理機(測試者)可送測試資料給相連的處理機(受測者)。受測者將測試資料執行約定的計算並將結果傳回測試者。最後測試者根據受測者回傳的結果宣佈測試結果為：受測者有誤或是無誤(fault-free)。PMC 模式同時假設: 無誤的測試者才能保證測試結果的正確性。對系統中所有必要的處理機進行測試，稱為完整測試。一次完整測試中所有測試結果集合起來，稱之為症狀(syndrome)。除此之外，亦有不同的偵錯策略。最常見的是考慮找出的有誤處理機數量。包括一步偵錯(one-step diagnosis)、循序偵錯(sequential diagnosis)和(t, k)偵錯((t, k)-diagnosis)。一步偵錯要求根據一次完整測試所得的症狀，找出所有有誤的處理機。循序偵錯要求根據一次完整測試所得的症狀，找出一個以上有誤的處理機。被找出的有誤處理機會進行修復或替換，接著再進行下一次的完整測試得到新的症狀、然後偵錯，重覆此過程直到所有有誤的處理機都被找出來。(t, k)偵錯推廣了循序偵錯。它要求根據一次完整測試所得的症狀，找出至少k個有誤的處理機或全部有誤的處理機(當系統中有誤的處理機數量小於k時)。另外一類的偵錯策略考慮找出的處理機是否被誤認。其中準確偵錯是指找出的處理機必是有誤的處理機，也就是不允許誤認；而悲觀偵錯是指找出的處理機中大部分是有誤的，但允許有小部分是無誤的，也就是允許少部分的誤認。偵錯度是指系統容許有誤處理機的最大數量。一旦系統中有誤處理機的數量超過偵錯度，則系統便無法進行偵錯。計算系統的偵錯度是系統偵錯三個最重要的議題之一。而計算循序偵錯偵錯度曾被證明是co-NP的問題。我們考慮更複雜的(t, k)偵錯策略的偵錯度問題。我們首先考慮求出格子系統(grid)在PMC模式下準確偵錯策略之(t, k) 偵錯的偵錯度。並期望根據格子系統的經驗，推廣至格子系統的變形系統(如：圓環面tori)的偵錯度問題。若兩相鄰處理機之狀態(有誤或無誤)已知，則不必進行測試。研究期間：9511 ~ 9607
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Department of Computer Science and information Engineering] Research Project

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	415	View/Open

社群 sharing

Loading...