In many multiprocessor system applications fault tolerance is desirable. For such systems to be fault-tolerant, their clocks must also be fault-tolerant. There have been two distinct approaches to the fault-tolerant clock synchronization problem. One is software-based and the other is hardware-based. It is desirable to use hardware clock synchronization algorithms for time-critical applications that need tight clock synchronizations.
In this thesis, a new reference clock selection algorithm for a hardware-based fault-tolerant clock synchronization of large multiprocessor systems and its hardware implementation are proposed. The proposed hardware implementation for the reference clock selection has a lower gate complexity and a smaller time delay, and is more flexible than the past implementations in the literature. This improvement is achieved by replacing the sorter with a counting encoder and comparators and by introducing a threshold generation logic with programmable registers. While the best known scheme has a circuit complexity of $0(n^2)$ and a delay of 0(n), the proposed scheme has a circuit complexity of 0(n) and a delay of 0(logn), where n is the total number of inputs to a particular clock. Also the proposed scheme is programmable for different configurations of n and m, the maximum number of tolerable faults.
The functionality of the proposed implementation is proved by simulation using a logic simulator in the SCALDstar system, which is a VLSI design support system from Valid Logic Systems, Incorporated.
많은 다중처리기 시스템의 응용분야에서는 고장허용성이 요구된다. 이런 시스템이 고장허용성을 갖기 위해서는 시스템의 클럭도 고장허용성을 가져야 된다. 고장허용성 클럭 동기화 문제에는 두가지 해결 방법이 있는데 하나는 소프트웨어에 의존하는 방법이고 다른 하나는 하드웨어에 의존하는 방법이다. 서로 매우 근접한 동기화를 필요로 하는 시간적으로 아주 중요한 응용분야에서는 하드웨어 클럭 동기화 방법이 바람직하다.
본 논문에서는 대형 다중처리기 시스템의 고장허용성 하드웨어 클럭 동기화를 위한 새로운 기준 클럭 선택 알고리즘과 그것의 하드웨어 구현방법을 제안하였다. 제안된 하드웨어 구현방법은 이제까지 발표된 다른 방법에 비해 회로의 복잡도가 낮아지고, 시간지연이 단축되었으며, 확장에 대해 보다 유연성을 갖는다. 이러한 발전은 기존 방법에서 사용하던 정렬기(sorter) 대신 계수부호화기(counting encoder)와 비교기를 사용하고, 또한 프로그램이 가능한 레지스터를 가진 기준치 발생 회로를 도입함으로써 가능해졌다. 기존의 방법에서는 n 을 전체 입력 클럭 수라고 할때 회로의 복잡도가 $O(n^2)$ 이고 시간지연이 0(n) 이었으나 제안된 방법에서는 각각 O(n), O(logn)으로 개선되었다. 또한 입력 클럭의 수와 허용할 수 있는 고장의 최대수의 변화에 대해서도 하드웨어 변화없이 사용할 수 있다. 제안된 방법의 동작성은 초대형 집적회로(VLSI) 설계 장비를 사용하여 모의시험으로 검증하였다.
