t/k-시스템을 이용한 하이퍼큐브 네트워크의 결함 진단

국문 초록 (Abstract)

시스템-레벨 진단 알고리즘은 결함의 개수가 t개를 초과하지 않는다는 t-진단가능 시스템의 특성을 이용한다. 기존의 진단 알고리즘으로 대형 멀티프로세서 시스템에서의 보다 많은 수의 결함을 처리하기에는 한계가 있다. Somani와 진단의 정확 여부를 판단할 수 없는 충분히 작은 개수의 노드가 존재한다는 것을 허용으로써 결함의 갯수가 t개를 초과할 경우에도 시스템을 진단하는 t/k-diagnosable 시스템을 제안하였다. 본 논문에서는 t/k-diagnosable 시스템을 이용한 하이퍼큐브 진단 알고리즘을 제안한다. 결함의 개수가 t개를 초과하는 경우에 대하여, k개의 부정확한 진단을 허용한다. 성능 실험 결과 제안 알고리즘은 HADA알고리즘보다 우수함을 보여 주었다. 또한 제안 알고리즘은 HYP-DIAG알고리즘과의 성능 비교에서도 비슷한 결과를 보여 준다

다국어 초록 (Multilingual Abstract)

System level diagnosis algorithms use the properties of t-diagnosable system where the maximum number of the faults does not exceed t. The existing diagnosis have limit when dealing with large fault sets in large multiprocessor systems. Somani and Peleg proposed t/k-diagnosable system to diagnose more faults than t (dimension) by allowing upper bounded few number of units to be diagnosed incorrectly. In this paper, we propose hypercube diagnosis algorithm using t/k-diagnosable system. When the number of faults exceeds t, we allow k faults to be diagnosed incorrectly. Simulation shows that the performance of the proposed algorithm is better than Feng’s HADA algorithm. The proposed algorithm also gives similar performance compared to HYP-DIAG algorithm.

목차 (Table of Contents)

• 요약
• ABSTRACT
• 1. 서론
• 2. t/k-HYP-DIAG 알고리즘
• 2.1 하이퍼큐브의 t/k-진단성
• 2.2 HYP-DIAG 알고리즘
• 2.3 t/k-HYP-DIAG 알고리즘
• 3. 알고리즘의 성능 분석
• 3.1 HYP-DIAG 알고리즘 성능 분석
• 3.2 t/k-HYP-DIAG 알고리즘 성능 분석
• 3.3 HADA 알고리즘과의 비교
• 4. 결론
• 참고문헌

참고문헌 (Reference)

1 F. P. Preparata, "On the Conection Assignment Problem of Diagnosable Systems" 12 : 848-854, Dec.1967.

2 A. K. Somani, "On Diagnosa-bility of Large Fault Sets in Regular Topology-Based Computer Systems" 45 (45): 892-903, Aug.1996.

3 E. Kranakis, "Better Adaptive Diagnosis of Hypercubes" 49 (49): 1013-1020, Oct.2000.

4 C. Feng, "Adaptive System-Level Diagnosis for Hy-percube Multiprocessors" 45 (45): 1157-1170, Oct.1996.

5 A. D. Friedman, "A New Measure of Digital System Diagnosis" 167-170, 1975

6 A. K. Somani, "A Generalized Theory For System Level Diagnosis" 36 (36): 538-546, May.1987.