Efficient realization of a threshold voter for self-purging redundancy

EFFICIENT REALIZATION OF A THRESHOLD VOTER FOR SELFPURGING REDUNDANCY1 José M. Quintana, María J. Avedillo, and José L. Huertas Instituto de Microelectrónica de Sevilla, IMSE-CNM, Univ. de Sevilla. Edif. CICA, Avda. Reina Mercedes s/n, Sevilla 41012, SPAIN 1This effort was partially supported by the spanish CICYT under Project TIC97-0648. Indexing Terms: Self-purgingRedundancy,FaultTolerance,SortingNetworks,ThresholdLogic. Abstract: The self-purging technique is not commonly used mainly due to the lack of practical implementations of its key component, the threshold voter. A very efficient implementation of this voter is presented which uses a decomposition technique to substantially reduce the circuit complexity and delay, as compared to alternative implementations. Introduction Achieving ultrareliable systems is a goal of increasing importance in many areas. The selfpurginghybridapproach[1]allowsustoimprovethereliabilityofdigitalsystemsandithasverysimple switching mechanisms, a straighforward design and is simpler, cheaper and more reliable than other hybrid approaches. Also, the faulty modules can be replaced from the system without affecting the normal operation of thesystem. This characteristic of self-purging systems is extremely attractive because it eases maintenance and repair. Intheself-purging approacheachoftheNidenticalmodules hasthecapabilitytodisconnect itself from the system in the event that its output disagrees with the voted output of the system. Switches remove their associated module from the system in case the module fails. The voter provides the mean for the masking of any fault that occurs in the module outputs. The voting is done by means of a threshold gate. The choice of the voter threshold is critical for the tolerance of selfpurging systems to multiple faults. In general, the best voter threshold is equal to half the number of the remaining fault-free modules [1]. In spite of the advantages described, the self purging technique is not commonly used in fault-tolerant digital designs. One reason for this limited utilization is that it is difficult to construct a threshold gate because it is claimed as an analog element, which is not practical for digital use. Concerning digital implementations, a direct implementation of the voter can be very expensive in terms of the number of gates [2]. Therefore, some simplifying solutions have been reported. Razavi [3] substitutes the threshold gate with a digitally constructed “strong majority voter” which automatically adjusts its threshold. However, the system presented is of limited use because only single module failures per clock cycle are allowed. A solution which can tolerate multiple module failures at any time is presented in [4], but no solution to build the voter is presented. In this paper a very efficient decomposition technique for the logic function performed by the voter is developed, allowing an extremely compact realization. The Losq Voter The voter that produces the system output and provides fault masking is a threshold gate. A threshold gate (TG) has ntwo-valued inputs x1,x2,…,xnand a single two-valued output, y.Itis defined by n+1 real numbers: threshold Tand weights w1,w2,…,wn, being denoted as ,where weight wiis associated with variable xi. The input-output relation of a TGisdefinedas y=1iff andy=0otherwise.Sumandproductinthe previous definition are the conventional operations, instead of logical ones. The classical solution to the automatic threshold adjustment uses a simple mechanism as shown in Figure 1 [1]. The threshold voter is described as , and it has been represented by a non-standard but widely used symbol. Implementing the Losq voter is a difficult taskbecause the large number of inputs it exhibits. As weights for xiare 1 and weights for yiare 2, the total weight for the gate is 3N. The most economical solutions for implementing this kind of voters are based on sorting networks [2]. Thus, the Losq voter would require a 3N-input SN to be implemented. Proposed Voter Implementation In this section, an efficient and extremely compact decomposition technique for the logic function performed by the voter is developed. w1w2…wnT;,,,[] wixiT≥ i1= n ∑ 1212…12N;,,,, ,,[] Theorem1: The output of the voter from a self-purging scheme with Nreplicatedmodules can be obtained from a two-level network composed by two N-input SNs, and a combinational network L, with inputs, as shown in Figure 2a. The first SN depends on yivariables (i=1, ..., N), and the second one depends on xivariables (i=1, ..., N). Proof: Let us consider the Losq voter for Nmodules given by , i.e. the voter output is asserted if . Let us divide the input set into two disjoint subsets, , and . Let and be two quantities which will be very useful in the following. Input combinations which assert voter output L are: {(a or more variables in S1 are at logic 1) or (a-1 or more variables in S1at logic 1) and (b or more variables in S2at logic 1) or (a-2 or more variables in S1at logic 1) and (b+2 or more variables in S2at logic 1) or .............................................................................. (1 or more variables in S1at logic 1) and (N-2 or more variables in S2at logic 1) or (N variables in S2at logic 1)} This formulation yields the logic expression for the voter output: (1) where stands for a function which asserts when at least rvariables in S1are 1, and has a similar definition but referred to S2. But this definition is exactly that corresponding to an N-input threshold function (inputs from S1or S2) with all the Nweights equal to 1 and threshold in r. There are of such TGs, of them depending on variables xiand another depending on variables yi. The fan-in of all of them is N, as shown in Figure 2b. The solution given in Figure 2a is obtained when the conceptual link between threshold gates and SNs [5] is applied. An n-input SN is a switching network with noutputs which are a sorted (non-increasing order) permutation of the inputs. The set of outputs in an n-input SN are nTGs corresponding to ,where if ,, and 0 2N 2 ---- 12…12N;,, ,,[] xi2yi +() N ≥ i 1= N ∑x1y1…xNyN ,,,, { } S1y1…yN ,,{}=S2x1…xN ,,{}=aN 2 ---- = b2N 2 ---- N 2 ---- –+= f LTYa NTYa1– NTXb N ⋅TYa2– NTXb2+ N ⋅…TY1 NTXN2– N ⋅TX N N ++ ++ += TYr NTXr N 2aa a T1 nT2 n…Tn n ,,,( ) Tm n1=xi i1= n ∑m≥m12…n,, ,= otherwise. Thus, the outputs from both sets of TGs in the first level shown if Figure 2b are specific outputs of two SNs: one of the SNs sorts yivariables (i=1, ..., N) and the other sorts xi variables (i=1, ..., N). ■ To evaluate the performance of both the traditional and the proposed solutions a comparison of their complexity and delay is in order. Concerning the complexity, the number of 1-bit comparators (a 1-bit comparator is implemented by means of a 2-input AND gate and a 2-input OR gate) needed in a n-input SN based on Batcher’s odd-even merge sort is given in [6]: (2) where is the number of comparators required to merge two sorted sequences of sizes and , given by: (3) and , and . Concerning the number of gate levels, the delay time in Batcher’s sorting method for n elements is given by: (4) When these expressions are applied to a self-purging redundancy scheme for N-modules, the cost of the voter is given by , and its delay is . In our approach, the cost of the voter is given by , is the cost of the combinational circuit at the output. The delay is , where delayCC corresponds to the combinational output circuit. Figure 3a clearly shows the difference in complexity between both solutions for typical values of the module number, N, and Figure 3b compares the delay for both approaches for the same range of N. Delay of the combinational output circuits depends on the available gates. For a comparison, we have supposed that 4-input OR gates are available. N 2 ---- Csort n() Csort n 2 ---   Csort n 2 ---   Cmerge n 2 ---n 2 --- ,   ;n2>()++= Cmerge n 2 ---n 2 --- ,   n 2 ---n 2 --- Cmerge n 2 ---n 2 --- ,   Cmerge n 2 --- 2 ---------- n 2 --- 2 ---------- ,     Cmerge n 2 --- 2 ---------- n 2 --- 2 ---------- ,     n 2 ---1–++= Cmerge 11,()1=Cmerge 21,()2=Csort 2() 1= delay n() 1 log2n+ 2   = Cost1Csort 3N()= Delay1 1 log23N+ 2   = Cost22C⋅sort N()CostCC += CostCC Delay2 1 log2N+ 2   delayCC += Example 1: Let us consider the design of a threshold voter from a self-purging scheme with 5 replicated modules. The voter needed is , i.e., the voter output is asserted when . From definitions for in Theorem 1, we obtain and . A logical expression for the voter output in Eq. (1) gives: The sum-of-product for this function has product terms, of three, four and five literals. However, when the voter is implemented as a sorting network, Eq. (2) gives a cost of 2-input comparators. The implementation obtained following the decomposition proposed in Theorem 1 provides a cost of 2-input comparators plus the cost of the combinational circuit at the output, which can be implemented by two 2-input AND gates and one 4-input OR gate, as shown in Figure 4. Further reduction in the number of comparators in both SN-based solutions can be obtained by eliminating comparators which are not used, but exact figures do not substantially modify the above reasonings about complexity. Concerning the delay time of both the traditional and the proposed solutions, Eq. (4) gives time units for the first implementation, and time units (5-input SN) plus two time units (combinational part) for the proposed implementation. ■ Conclusions A low-cost implementation of the classical self-purging approach from Losq has been proposed. It is based on both the application of a decomposition technique and the use of the conceptual link between TGs and SNs. The proposed implementation exhibits an excellent performance when compared to the original solution. 1212121212 5;,,,,,,,,,[] xi2yi +()5≥ i1= 5 ∑ aand ba=5 2 ---=3 b=2 5 2 ---5 2 --- –+ =1 f LTY3 5TY2 5TX1 5 ⋅TY1 5TX3 5 ⋅TX 5 5 +++= 5 3   5 2   5 1   ⋅5 1   5 3   ⋅5 5   +++111= Csort 35×()59= 2Csort 5()×18= delay 15() 1 log215+ 2   10== delay 5() 1 log25+ 2   6== References [1] J. Losq: “A highly efficient redundancy scheme: self-purging redundancy”, IEEE Trans. on Computers, vol. C-25, No. 6, pp. 569-578, June 1976. [2] B. Parhami: “Voting networks”, IEEE Trans. on Reliability, vol. 40, No. 3, pp. 380-394, Aug. 1991. [3] H.M. Razavi: “Self-purging redundancy with automatic threshold adjustment”, IEE Proc.-G, vol. 140, No. 4, pp. 233-236, August 1993. [4] C.W. Chiou and T.C. Yang: “Self-purging redundancy with adjustable threshold for tolerating multiple module failures”, Electron. Lett., 1995, 30, (11), pp. 930-931. [5] E.A. Lamagna, “The complexity of monotone networks for certain bilinear forms, routing problems, sorting, and merging”, IEEE Trans. on Comput., vol. C-28, pp. 773-782, Oct. 1979. [6] D.E. Knuth, The Art of Computer Programming, Vol. III, Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1973, ch. 5. FIGURES & ⊕ Module i Figure 1:Self-purging approach with N modules for optimal tolerance to multiple failures switch i Initialization and retry [1,2,...,1,2;N] 1 2 N Q Qxi yi SR1 2 1 2voter xN yN x1 y1 System output from module N and switch N from module 1 and switch 1 y1 yN 1 1a Figure 2: Two level realization of self-purging voter, (a) using SNs, (b) using TGs Ta N TN N y1 yN x1 xN Bb=Tb N A1=T1 N Aa=Ta N BN=TN N Sorting Network Sorting Network (a) (b) Tb+2 N TN2– N T2 N Ta1– N L Lx1 xN 1 1b Tb N x1 xN 1 1N y1 yN 1 11 T1 N System output System output Figure 3: Cost parameters for the traditional and the proposed solutions (a) (b) 0 5 10 15 0 2 4 6 8 size o f network in hundred o f 2-input gates traditional proposed number of modules, N 0 5 10 15 0 5 10 15 20 25 gate levels traditional proposed number of modules, N (a) Size of network in hundred of 2-input gates, (b) Delay Figure 4: Proposed realization for the self-purging voter in Example 1 y1 y5 T1 5 5-input SN 5-input SN y2 y3 y4 T2 5 T3 5 x1 x5 x2 x3 x4 T1 5 T3 5 T5 5 & & +fL