(A) fault-tolerant hardwere clock synchroinzationalgorithm for large multiprocessor systems

Abstract

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(\log n)$, 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.