Multistage interconnection system (MIS) which is a collection of switching elements (SEs) and links connecting the SEs has been widely used as a promising fabric to communicate between processors and/or memories in multiprocessing (parallel computing) and distributed systems. In the MIS, some failures of SEs may cause disconnection of data paths between several input/output pairs, so the system performance should be in degradation mode before the faulty SEs are repaired. This brings about fault-tolerant MIS for settling fault-sensitive system and enhancing the fault-tolerance of the system.
This thesis deals with performance-related reliability (PRR) management focused on MIS. The first issue in the MIS is how to measure the reliability of MIS more accurately. The more advanced a system, the more important its performance not only its reliability. Therefore we propose PRR measures to characterize the degrading features of fault-tolerant MISs in the presence of faulty SEs. The measures include: mean number of connected input/output pairs, mean number of survivable inputs that are connected to at least one output and finally mean number of outputs connected from a survivable input. We also evaluate the measures for the well-known unique-path shuffle exchange network (SEN) and its two fault-tolerant variants, extra-stage shuffle exchange network (SEN+) and augmented-SEN (ASEN), and then compare the networks through some numerical tests.
The second issue is how to enhance the fault-tolerance of a certain system and to extend the methods. By creating redundant paths we make the system tolerate the faults and enhance its reliability. In chapter 3, we introduce four useful types of system which represent actual topologies of real world communication networks or parallel computing systems. Similar procedures used before are passed through when measuring PRR and comparing its results. Of course it is difficult to describe actual system structures or network classes as conceptual forms. Four proposed systems and combined systems from them, however, can represent most of systems or networks and hence whoever want to design such system can apply the results of this thesis as enough as possible.
In the last, we evaluate our PRR models considering several parts of this thesis. Firstly, we present technologically relevant cost measures that can be a useful guidance in the comparison of MINs. From the original theory of interconnection networks, we basically compute a cost measure-network complexity and then combine it with PRR measure for normalized comparison between MINs. The results can be good guideline to choose appropriate cost/fault-tolerance compromise. Secondly, our models are compared with previous approaches to show how useful the PRR measures proposed in this thesis and how successful it is to incorporate exact tradeoffs in benchmarking for selecting a good cost/fault-tolerance compromise among MINs.
본 논문에서는 다단 상호연결시스템(multistage interconnection system: MIS)을 대상으로 신뢰성을 측정하고 고장감내형(fault-tolerant)망의 성능 기반 신뢰성(performance-related reliability: PRR) 관리에 대해 다루고 있다. 다단 상호연결시스템이란 다수의 교환소자(SEs)와 링크로 이루어진 집합체로서 흔히 우리가 접하게 되는 MIN은 $N=R^n$개의 입력단자와 $M=Q^n$개의 출력단자를 가지고 $n=log_{R} N=log_{Q}M$ 단계를 거쳐 연결된다. 그리고 각 단은 완전접속성(full access property)을 만족시키며 각각의 단계에는 RxQ의 크기로 표현되는 교환소자로 이루어져 있다.
이 분야의 연구는 그 동안 병렬 또는 분산 컴퓨팅을 위한 하드웨어 설계분야에서 주로 연구되어 멀티 프로세서 간의 상호연결성과 그러한 시스템에서의 신뢰성을 주요 주제로 다루어 왔다. 최근에는 고속통신망의 교환체계(switching fabric)로서의 유용성이 인정되어 통신기술적 측면의 접근이 새롭게 시도되고 있다.
이 분야의 대표적인 접근방법은 어떤 특정한 네트워크 유형이나 그룹을 선정하여 신뢰성을 측정하고 이를 높이기 위한 새로운 네트워크를 제안하는 것이 그 하나이다. 또 다른 것은 이와 같이 신뢰성에 관심이 많다고 할 때, 과연 어떤 측정수단을 선택하여 측정하는 것이 좋으냐, 즉 측정수단의 문제이다. 물론 연구의 초창기나 지금이나 가장 관심을 끄는 것은 여하한 방법을 적용하여 대상이 되는 네트워크나 시스템의 고장감내성(fault-tolerance)을 높이느냐에 집중되어 있다. 그리고 끝으로 신뢰성에 관련된 시스템 관리의 문제, 즉, 성능, 비용 등의 문제를 다루어 왔다.
다단 상호연결시스템에서 교환소자의 고장으로 인해 발생하는 시스템의 성능저하를 해결하기 위해 제안된 방법이 고장감내형 다단 상호연결시스템이다. 단일 경로 다단 상호연결망(unique-path MIN)이 가지는 고장에 대한 취약성을 보완하기 위해 제안된 방법은 주로 입출력 단자 쌍간에 경로의 중복성(redundancy)을 제공하여 시스템의 신뢰성을 높여주고 고장에 대해 보다 유연하게 대응할 수 있도록 하는 것이다. 대개 중복성 부여 방법은 다음과 같다.
ㆍ 입출력 단자 쌍간에 다수의 분기선 형성을 목적으로 하나의 네트워크를 둘 이상으로 복제하여 중복성을 부여하는 방법
ㆍ 하나 또는 그 이상의 단계를 추가하는 방법
ㆍ 추가적인 교환소자나 링크를 제공하는 방법
성능기반의 신뢰성은 성능이 일부 저하된 MIN에서 성능의 측면을 고려하여 설계된 신뢰성 측정수단으로 측정되며 보다 그 결과는 단순히 신뢰성만을 측정하는 것보다는 의미있고 보다 많은 관심사를 제공하게 될 것이다. 논문의 2장에서는 3개의 성능 기반 신뢰성 측정수단을 설정하고 기본적인 MIN으로 널리 알려진 SEN(shuffle exchange network)과 그 확장형 네트워크에 대한 측정수단으로, 기존의 확률계산에서 흔히 사용되는 reverse probabilistic argument와 간단한 graph theory를 이용하여 대개 근사해나 시뮬레이션을 이용하는 경우와 달리 보다 쉬우면서도 정확한 해를 제공하며 부분적인 고장 상태인 시스템이나 네트워크의 성능 또는 관련된 신뢰성을 평가하는 데 유용하다.
3장에서는 2장에서 개발된 측정방법을 바탕으로 현실적으로 사용되고 있는 네트워크 형태와 보다 유사한 네 가지 유형의 네트워크에 대해 우리의 방법을 적용하고 필요한 수정과 개선방법을 모색하였다. 물론 실제 네트워크 구조나 유형은 개념적인 형태로 표현하기 어려우며 단일 특성을 가진다고 할 수 없지만 제안된 네 가지 및 그들의 조합에 의해 형성되는 네트워크에 의해 대부분의 통신망이나 시스템 구성이 표현가능하다고 판단되며 따라서 본 논문의 결과도 충분히 적용성을 가진다고 할 수 있다.
4장에서 우리는 각 네트워크 유형의 절대적인 비용(주로 하드웨어 비용)을 계산하는 방법을 정의하고 그에 따라 계산된 결과를 시스템별로 비교한다. 그리고 보다 공정한 비교를 위해 2장과 3장에서 각각 계산된 성능기반 신뢰성 측정수단과 결합하여 정규화함으로써 네트워크 유형의 특성을 비교하여 요구되는 상황(비용과 성능의 절충)에 따른 시스템의 구성 및 선택기준을 제안한다.
