A combinatorial method for the evaluation of yield of fault-tolerant systems-on-chip
Abstract
In this paper we develop a combinatorial method for the evaluation of yield of fault-tolerant systems-on-chip. The method assumes that defects are produced according to a model in which defects are lethal and affect given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The method is based on the formulation of the yield as 1 minus the probability that a given boolean function with multiple-valued variables has value 1. That probability is computed by analyzing a ROMDD (reduced ordered multiple-valuedecision diagram) representation of the function. For efficiency reasons, we first build a coded ROBDD (reduced ordered binary decision diagram) representation of the function and then transform that coded ROBDD into the ROMDD required by the method. We present numerical experiments showing that the method is able to cope with quite large systems in moderate CPU times.
Full text
A Combinatorial Method for the Evaluation of Yield of Fault-Tolerant Systems-on-Chip Doru P. Munteanu Military Technical Academy G. Cosbuc 81–83 Bucharest 75275, Romania [email protected] V´ıctor Su˜n´e, Rosa Rodr´ıguez-Monta˜n´es, Juan A. Carrasco Departament d’Enginyeria Electr`onica Universitat Polit`ecnica de Catalunya Diagonal 647, plta. 9 08028 Barcelona, Spain f sunye,rosa,carrasco g @eel.upc.es Abstract In this paper we develop a combinatorial method for the evaluation of yield of fault-tolerant systems-on-chip. The method assumes that defects are produced according to a model in which defects are lethal and affect given components of the system following a distribution common to all defects. The distribution of the number of defects is arbitrary. The method is based on the formulation of the yield as 1 minus the probability that a given boolean function with multiple-valued variables has value 1. That probability is computed by analyzing a ROMDD (reduced ordered multiple-valuedecision diagram) representation of the function. For efficiency reasons, we first build a coded ROBDD (reduced ordered binary decision diagram) representation of the function and then transform that coded ROBDD into the ROMDD required by the method. We present numerical experiments showing that the method is able to cope with quite large systems in moderate CPU times. 1 Introduction Systems-on-chip are becoming popular. The high densities and areas of those integrated systems make them very susceptible to manufacturing defects. In fact, complex systems-on-chip are likely to have a very small yield if they are not designed with built-in fault-tolerance. Then, there is a need for efficient methodologies for estimating the yield of complex fault-tolerant systems-on-chip. When the fault-tolerant system-on-chip has a regular structure, it is often possible to make “ad-hoc” evaluations (see, for instance, [11, 12, 17, 18]). However, many fault-tolerant This work was supported by the “Comisi´on Internacional de Ciencia y Tecnolog´ıa” (CICYT) of the Ministry of Science and Technology of Spain under the research grant TAP1999-0443-C05-05. designs do not have a regular structure, particularly those using a sophisticated network-on-chip as a communication subsystem among the intellectual property cores (IPs) [3]. Computing the yield of such systems-on-chip is difficult, mainly because the fact that realistic defect distributions have clustering [7, 13, 14, 15, 16, 18] and, thus, introduce dependencies among the failed states of the components of the system (see, for instance, [18, 27]). Simulation is an approach which is not severely limited by the complexity of the system, but tends to be expensive and does not provide strict error control. The aim of this paper is to develop a combinatorial method for the evaluation of the yield of fault-tolerant systems-on-chip with precise error control which can cope with quite complex systems using currently affordable computational resources. We assume that the fault-tolerantsystem-on-chip is made up of a set f 1 2 ::: C g of components and that whether the system is functioning or not is determined from the failed states of the components through a fault-tree function F ( x 1 ::: x C ) , where variable x i takes the value 1 if and only if component i is failed and the function takes the value 1 if and only if the system is not functioning. No restriction is imposed on F ( x 1 ::: x C ) . It will be assumed that a gate-level description of the function is available. The productionof manufacturing defects will be modeled using the following probabilities: Q k = P number of manufacturing defects is k ] k =0 1 2 ::: P i = P a given defect affects component i and is lethal ] It will be assumed that all defects will be distributed over the components making up the system and will be lethal following the probabilities P i , 1 i C , independently of the number of defects, of which components affect the remaining defects and of whether those defects are lethal 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
or not. That model is useful from the designer’s point of view, since the distribution of the number of defects Q k , k =0 1 2 ::: could beeasily provided by themanufacturer of the system-on-chip and the probabilities P i , 1 i C could be estimated from the final layout of the system-onchip using appropriate tools [19, 21, 31, 32] or from IP layouts and routingestimates [30]. Thus, the methodologies could be used at several design stages. The assumed model is consistent with all compound Poisson yield models [18], which includethewidely used negativebinomial distribution for the number of defects. The assumed model will not be consistent however with yield models accounting for spatial clustering1such as the one proposed in [22]. From a computational point of view, it is convenient to map the previously described model into a model taking into account only lethal manufacturing defects, i.e. defects which effectively make some component of the system to be defective (not to work properly). That model includes the probabilities: Q 0 k = P number of lethal manufacturing defects is k ] k =0 1 2 ::: P 0 i = P a given lethal defect affects component i ] : The reason why the last model is computationally more convenient is basically because, since not all defects will be lethal, the distribution Q 0 k , k =0 1 2 ::: will be shifted to lower values of k in relation to the distribution Q k , k = 0 1 2 ::: and, then, if only up to M defects are analyzed (the computational cost of the methods will increase with M ), higher accuracy will be obtained if the distribution Q 0 k , k =0 1 2 ::: is used instead of Q k , k =0 1 2 ::: .The mapping can be performed using: Q 0 k = 1 X m = k Q m m k P k L (1 P L ) m k (1) P 0 i = P i P L where P L = P C i =1 P i is the probability that any given defect is lethal. As previously commented, the negative binomial distribution is the most widely used distribution for the number of defects affecting a chip. That distributionhas the form: Q k = ( + k ) k !( ) ( = ) k (1 + = ) + k (2) where is the expected number of defects and is the clustering parameter (the clustering increases for decreasing 1Spatial clustering refers to the fact that irrespectively of the expected number of defects on the system-on-chip, defects tend to cluster spatially. ). It is known (see [15]) that, when the distribution of the number of defects is negative binomial, the distribution of the number of lethal defects is also negative binomial with the same clustering parameter. More precisely, when the distribution of the number of defects is given by (2), the distribution of the number of lethal defects is: Q 0 k = ( + k ) k !( ) ( 0 = ) k (1 + 0 = ) + k with 0 = P L . Similar results hold for all compound Poisson distributions [18]. 2Themethod In the method the yield, Y , is computed analyzing whether the system is functioning or not assuming 0 1 2 ::: M lethal defects. Let Y k = P system is functioning j there are k lethal defects ] : We have Y = 1 X k =0 Q 0 k Y k : Analyzingupto M defects we can pessimistically estimate Y by Y M = M X k =0 Q 0 k Y k with error bounded from above by P 1 k = M +1 Q 0 k =1 P M k =0 Q 0 k . Then, given a suitable error control parameter " , we can select M =min ( m 0:1 m X k =0 Q 0 k " ) guaranteeing and absolute error in the yield estimation " . The yield estimate Y M can be formalized as the probability that a boolean function of certain independent integervalued random variables is equal to 1. Assume that the defects are numbered in some arbitrary order. Those random variables are: W = 8 < : k 0 k M if there are k lethal defects M +1 if there are more than M lethal defects and, for 1 k M , V k = i if the k th lethal defect affects component i: 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
Note that the random variable W takes values in f 0 1 ::: M +1 g and each random variable V k takes values in f 1 2 ::: C g . The random variable W has probability distribution P W = k ]= Q 0 k , 0 k M , P W = M +1] = 1 P M k =0 Q 0 k . The random variables V k have probabilitydistributions P V k = i ]= P 0 i , 1 k M , 1 i C . Let I k ( x ) denote the boolean function with integervalued variable x returning the value 1 if x = k and the value 0 otherwise and let I l ( x ) denote the boolean function with integer-valued variable x returning the value 1 if x l and the value 0 otherwise. Let the boolean function G ( w v 1 v 2 ::: v M )= I M +1 ( w ) _ F M _ l =1 I l ( w ) ^ I 1 ( v l ) ::: M _ l =1 I l ( w ) ^ I C ( v l ) ! : (3) Then, we have the following result. Theorem 1. Y M =1 P G ( WV 1 V 2 ::: V M )=1] . Intuitively, the reason why Theorem 1 holds is that I M +1 ( W ) “tells” whether the number of lethal defects is >M , I l ( W ) “tells” whether there is a l th lethal defect, I i ( V l ) “tells” whether the l th lethal defect affects component i and, then, W M l =1 I l ( W ) ^ I i ( V l ) “tells” whether component i is affected by some of the first M lethal defects. A formal proof follows. Proof of Theorem 1 The quantity 1 Y k is the probability that given there are k lethal defects the system is not functioning. Since, assuming there are k lethal defects, component i is failed if and only if W k l =1 I i ( V l )=1 ,we have 1 Y k = P " F k _ l =1 I 1 ( V l ) ::: k _ l =1 I C ( V l ) ! =1 # : (4) Using the theorem of total probability and the independence of the random variables WV 1 ::: V M : P G ( WV 1 ::: V M )=1] = M +1 X k =0 P W = k ] P G ( WV 1 ::: V M )=1 j W = k ] = M X k =0 Q 0 k P G ( k V 1 ::: V M )=1] + 1 M X k =0 Q 0 k ! P G ( M +1 V 1 ::: V M )=1] : (5) But, from the definition of G (3), for 0 k M : G ( k v 1 ::: v M )= F k _ l =1 I 1 ( v l ) ::: k _ l =1 I C ( v l ) ! (6) and G ( M +1 v 1 ::: v M )=1 : (7) Then, using (4)–(7) P G ( WV 1 ::: V M )=1] = M X k =0 Q 0 k (1 Y k )+1 M X k =0 Q 0 k = 1 M X k =0 Q 0 k Y k =1 Y M : In the method, the probability P G ( WV 1 ::: V M )= 1] is computed building an ROMDD (reduced ordered multiple-valued decision diagram) of the function G ( w v 1 ::: v M ) . ROMDDs are a natural extension of the well-known ROBDDs (reduced ordered binary decision diagrams) [5] in which both the variables and the function are allowed to be multiple-valued. A gate-level representation of the function G ( w v 1 ::: v M ) can be obtained from a gate-level representation of F ( x 1 ::: x C ) as shown in Figure 1, where the gate labeled i inside is a “filter” gate returning the value 1 if its integer-valued input has value i and returning the value 0 otherwise and the gate labeled i inside is a “filter” gate returningthe value 1 if its integer-valued input has value i and returning the value 0 otherwise. As ROBDDs, ROMDDs are canonical representations which can be built and manipulated in a similar way as ROBDDs. An ROMDD representing a function F , which can take values in the set S F , of variables x i , i =1 2 ::: n ,which can take values in the sets S i is a directed acyclic graph with up to j S F j terminal nodes each labeled with a distinct value of the set S F . Every non-terminal node is labeled by an input variable x i and has as many as j S i j edges, each labeled by a subset of S i , with subsets associated with different edges being non-intersecting. The ROMDD has a unique non-terminal node without incoming edges, representing the function F ( x 1 ::: x n ) , called the top node. The input variables encountered in every path from the top node to a terminal node form a sequence of non-repeating input variables consistent with an ordering x p (1) ::: x p ( n ) of the input variables of the function. Every non-terminal node of the ROMDD represents a unique function of the set of input variables which are found in some path from the node to some terminal node. That a ROMDD is a canonical representation means that, given F , the ROMDD only 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
. . . . . . . . . . . . . . . . . . ... ... 1 2 C 1 2 M +1 v M C w 1 M w x 1 x 2 x C G F v 1 Figure 1. Gate-level description of the function G ( w v 1 :: : v M ) . depends on the selected ordering x p (1) ::: x p ( n ) for the multiple-valued variables. Using the fact that the random variables WV 1 ::: V M are independent and that the function represented by a nonterminal node only depends on the set of variables found on paths from the non-terminal node to terminal nodes, it is possible to compute P G ( WV 1 ::: V M )=1] from an ROMDD representation of the function G ( w v 1 ::: v M ) . This can be achieved by assigning the value 1 to the terminal node labeled “1” and the value 0 to the terminal node labeled “0”, making a depth-first, left-most traversal [1] of the ROMDD, and computing the probability that the function represented by a non-terminal node has value 1 when returning from each non-terminal node. Assume that node n has associated with it the variable w ,that M =4 ,andthat n has edges to nodes n 1 , n 2 and n 3 with subsets of values of w f 0 1 g , f 3 g and f 2 4 5 g ,respectively. Then, denoting by value ( x ) the “value” variable associated with node x , when returning from node n , value ( n ) would be computed as ( P W =0]+ P W = 1]) value ( n 1 )+ P W =3] value ( n 2 )+ ( P W = 2] + P W =4]+ P W =5]) value ( n 3 ) .Attheendof the traversal, the “value” variable of the top node will hold P G ( WV 1 ::: V M )=1] . We illustrate the computational procedure with the small ROMDD shown in Figure 2 which corresponds to a fault-tolerant system having faulttree function F ( x 1 x 2 x 3 )= x 1 x 2 + x 3 and M =2 under the multiple-valued variable ordering v 1 v 2 w .Thisimplies that the random variable W will take values in the set f 0 1 2 3 g and the random variables V 1 and V 2 will take values in the set f 1 2 3 g . Using a depth-first, left-most traversal of the ROMDD, P G ( WV 1 V 2 ) = 1] = value ( n 1 ) 10 2 1 1,3 1 0,1 0 3 2,3 3 0,1,2 1,2,3 2,3 2 w v 1 v 2 v 2 w w n 1 n 2 n 6 n 3 n 5 n 4 Figure 2. Small ROMDD to illustrate the computation of P G ( WV 1 : :: V M )=1] . would be computed following the sequence: value ( n 4 )= Q 0 3 value ( n 5 )= Q 0 2 + Q 0 3 value ( n 2 )= P 0 1 value ( n 4 )+( P 0 2 + P 0 3 ) value ( n 5 ) value ( n 3 )= P 0 2 value ( n 4 )+( P 0 1 + P 0 3 ) value ( n 5 ) value ( n 6 )= Q 0 1 + Q 0 2 + Q 0 3 P G ( WV 1 V 2 )=1]= value ( n 1 )= P 0 1 value ( n 2 )+ P 0 2 value ( n 3 )+ P 0 3 value ( n 6 ) : Althoughthere are algorithmsand packages for ROMDD manipulation [23, 29], there is currently consensus in the ROMDD community that the most efficient way for analyzing multiple-valued functions of multiple-valued variables is by using coded ROBDDs [23, 24]. A coded ROBDD of a multiple-valued function H ( x 1 x 2 ::: x n ) of multiple-valued variables x i is the ROBDD of any function H 0 ( x 1 1 ::: x 1 k 1 x 2 1 ::: x 2 k 2 ::: x n 1 ::: x nk n ) which represents H ( x 1 x 2 ::: x n ) in terms of groups x i 1 x i 2 ::: x ik i of binary variables encoding the multiple-valued variables x i . Formally, denoting by D i the domain of x i and by x i 1 ( j ) ::: x ik i ( j ) the codeword representing value j 2 D i in the code used for x i , H 0 has to satisfy H 0 ( x 1 1 ( j 1 ) ::: x 1 k 1 ( j 1 ) x 2 1 ( j 2 ) ::: x 2 k 2 ( j 2 ) ::: x n 1 ( j n ) ::: x nk n ( j n )) = H ( j 1 ::: j n ) for every ( j 1 ::: j n ) 2 D 1 D 2 D n . Coded ROBDDs can be used directly in many applications such as formal verification. However, the combinatorial method for yield computation requires the availability of the ROMDD. Given an ordering x p (1) ::: x p ( n ) of the multiple-valued variables, the ROMDD can be efficiently obtained from a coded ROBDD if the coded ROBDD is obtained using an ordering for the binary variables in which the variables encoding each multiple-valued variable are kept grouped and the groups are ordered according to the ordering x p (1) ::: x p ( n ) . The conversion procedure is based on viewing the coded ROMDD as made up of layers, where 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
each layer contains the nodes with binary variables encoding a given multiple-valuedvariable. Some of the nodes in each layer are entry nodes (they have incoming arcs from other layers). The procedure builds incrementally the ROMDD by processing bottom-up each layer of the coded ROBDD. Processed entry nodes of the coded ROBDD are associated with nodes of the constructed ROMDD. Let mapping ( n ) be the node of the ROMDD associated with the entry node n of the coded ROBDD. The bottom layer of the coded ROBDD is processed by creating a copy n 0 0 in the ROMDD of the non-terminal node n 0 of the coded ROBDD with value 0 and creating a copy n 0 1 in the ROMDD of the nonterminal node n 1 of the coded ROBDD with value 1 and making mapping ( n 0 )= n 0 0 and mapping ( n 1 )= n 0 1 .The remaining layers of the coded ROBDD are processed by processing each entry node n of the layer as follows. For each possible value i of the multiple-valued variable x associated with the layer, it is determined which entry node of a different (down) layer is reached from n when the values of the group of binary variables associated with the layer encoding value i are followed. Let n s ( i ) be the node of the coded ROBDD reached when the value i is “simulated”. If all mapping ( n s ( i ) ) are equal to some node n 0 of the ROMDD, then mapping ( n ) must be made equal to n 0 and no node has to be added to the ROMDD. Otherwise, the ROMDD must have a node associated with n with multiple-valued variable x . That node must have successor mapping ( n s ( i ) ) for each value i of x . If there exists in the ROMDD some node n 0 with multiple-valued variable x and successor mapping ( n s ( i ) ) for each value of x , then, mapping ( n ) is set to n 0 and no node is added to the ROMDD. Otherwise, a node n 0 with multiple-valued variable x and successor mapping ( n s ( i ) ) for each value i of x is added to the ROMDD and mapping ( n ) is set to n 0 . When not all combinations of values of the groups of binary variables encode values in the domain of the associated multiple-valued variable, the ROMDD built in that way may have nodes which are unreachable from the top node. Such nodes are identified and deleted by making a depth-first, leftmost traversal of the ROMDD starting from the top node. Figure 3 illustrates the processing of a layer of a coded ROBDD associated with a multiple-valued variable x which takes values in the domain f 1 2 3 g and in which two binary variables x 1 x 0 have been used to encode variable x using the code 1= 00 , 2= 01 and 3= 10 . The coded ROBDD is built by processing an implementation of the function G ( w v 1 ::: v M ) in binary logic obtained by encoding the variable w in binary using a minimum number of bits. For the variables v i , since they have values in the domain f 1 2 ::: C g , a binary code of minimum number of bits encoding v i 1 is used. Such strategy keeps minimum the number of binary variables and tends to result in coded ROBDDs of minimum size. Filter gates are 1,2 2,3 1,3 1 xxx 32 0 1 0 0011 0 1 1 mapping( n 7 ) mapping( n 8 ) mapping( n 3 )mapping( n 1 ) mapping( n 2 ) mapping( n 6 ) n 5 n 2 n 3 n 4 n 6 n 7 n 1 n 8 x 0 x 0 x 0 x 1 x 1 Figure 3. Illustration of the procedure for obtaining the ROMDD from the coded ROBDD substituted by binary logic expressed in terms of the binary variables w l 0 :::w 0 encoding the multiple-valued variable w and the binary variables v l i :::v 0 i encoding each multiplevalued variable v i . Although, with given orderings of the variables, the coded ROBDD and the ROMDD will be independent on the particular implementation of that logic, that implementation may affect the heuristic-based orderings to be described next. This makes convenient to report which logic is used. Calling z k , 1 k M , the output of the “filter” gate labeled k having as input w , and calling z M +1 the output of the “filter” gate labeled M +1 having as input w , the binary logic used for generating z k , 1 k M +1 is: z M +1 = lit ( w l 0 M +1) ^ lit ( w l 0 1 M +1) ^ ^ lit ( w 0 M +1) z k = z k +1 _ lit ( w l 0 k ) ^ lit ( w l 0 1 k ) ^ ^ lit ( w 0 k ) 1 k M where lit ( w i m )= w i if the i th bit of the binary code representing m is 1 and lit ( w i m )= w i if it is 0, where x denotes the complement of the binary variable x . Calling z k i the output of the “filter” gate labeled k having as input v i , the binary logic used for generating z k i is: z k i = lit ( v l i k 1) ^ lit ( v l 1 i k 1) ^ ^ lit ( v 0 i k 1) 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
where lit ( v j i m )= v j i if the j th bit of the binary code representing m is 1 and lit ( v j i m )= v j i if it is 0. For building the coded ROBDD the implementation of the method uses the well-known BDD Library developed at Carnegie-Mellon University [2]. It is well-known that the size of the ROBDD of a boolean function of binary variables depends on the ordering of the binary variables. Similarly, the size of the ROMDD of a multiple-valued function of multiple-valued variables depends on the ordering of the multiple-valued variables. The variables are most often sorted using heuristics and an abundant literature is available about heuristics for ordering the variables of boolean functions of binary variables using gate-level representations of the functions [4, 6, 8, 9, 10, 20, 25, 26]. Those heuristics can be classified into static and dynamic depending on whether the ordering is computed before the ROBDD is built or the ordering may be changed during the ROBDD construction. Three heuristics which are relatively simple to implement and which have good performance are the topology heuristic described in [26], the weight heuristic described in [25] and the H4 heuristic described in [4]. In the topology heuristic, input variables are sorted as found in a depth-first, left-most traversal of the gate description. In the weight heuristic, a weight 1 is assigned to the inputs, and, processing the gate description bottom-up, a weight equal to the sum of the weights of the fan-in nodes is assigned to the non-input nodes. Then, nodes in the fan-in of each non-input node are reordered in order of increasing weight, respecting the original ordering in case of a tie, and input variables are sorted as found in a depth-first, left-most traversal of the gate description with reordered fan-in. In the H4 heuristic, input variables are sorted as found in a depth-first, left-most traversal of the gate description with nodes in the fan-in of a non-input node dynamically sorted when the non-input node is first visited using the following two criteria, in that order: first, nodes having minimum number of non-visited inputs in its dependency cone; second, nodes with minimum sum of indices of visited inputs in its dependency cone (the index of a visited input is the order assigned to the input). As in the case of the weight heuristic, in case of a tie, the original ordering of the fan-in of a non-input node is preserved. We will experiment with the following orderings for the variables w v 1 ::: v M : wv: w v 1 ::: v M . wvr: w v M ::: v 1 . vw: v 1 ::: v M w . vrw: v M ::: v 1 w . t: ordering which results when the heuristic topology is applied to the gate-level description of G ( w v 1 ::: v M ) in binary logic and the multiplevalued variables are sorted in increasing order of the average indices over the groups of binary variables encoding each multiple-valued variables. w: same as t but using the heuristic weight for sorting the binary variables. h: same as t but using the heuristic H4 for sorting the binary variables. The size of the coded ROBDD is affected by the ordering of the group of binary variables encoding each multiplevalued variable. Then, it is convenient to use an ordering for those groups of binary variables yielding ROBDDs of as small size as possible. We will experiment with the following orderings for the groups of binary variables encoding each multiple-valued variable: ml: most to least significant bit. lm: least to most significant bit. t: ordering which results when the binary variables are sorted in increasing ordering of the indices given by the topological heuristic. w: same as t but using the weight heuristic. h: same as h but using the H4 heuristic. We allow the use of orderings ml and lm for the groups of binary variables in combination with any ordering for the multiple-valued variables. However, we will only allow the use of an ordering t for the groups of binary variables in combination with theordering t forthemultiple-valued variables, the use of an ordering w for the group of binary variables in combination with the ordering w for the multiple-valued variables, and the use of the ordering h for the groups of binary variables in combination with the ordering h for the multiple-valued variables. 3 Benchmarks description In this section we describe the benchmarks which will be used to evaluate the performance of the combinatorial method for evaluating the yield. The benchmarks are two scalable examples which instantiate systems-on-chip of increasing numbers of components. The first scalable example, called MS n , is the system-on-chip with the architecture illustrated in Figure 4. The system includes a cluster of two “master” Intellectual Property cores IPM and n clusters including two “slave” Intellectual Property cores IPS. Those Intellectual Property cores are interconnected using communication modules CM and CS and two buses. Buses are assumed to be not affected by manufacturing defects. This 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
IPM_1 IPM_2 CM_1_A CM_1_B CM_2_A CM_2_B CS_1_1_A IPS_1_1 CS_1_1_B CS_1_2_A IPS_1_2 CS_1_2_B CS_n_1_A IPS_n_1 CS_n_1_B CS_n_2_A IPS_n_2 CS_n_2_B Figure 4. Architecture of system-on-chip MSn. implies that the system can be conceptualized as made up of only IPMs, IPSs and communication modules. The system is operational if at least an unfailed IPM can communicate with at least an unfailed IPS of each cluster using unfailed communication modules. The communication between the IPM and each IPS has to be direct, i.e. it can only involve a bus and two communication modules. Manufacturing defects are assumed to follow a negative binomial distribution with clustering parameter =3 ; for the expected number of defects two values will be assumed: =2 and =4 . Furthermore, the probabilities P i will be taken so that P L = P C i =1 P i =0 : 5 (and, then, 0 has the values 1 and 2) and, calling, P IPM the P i probability of an IPM, P IPS the P i probability of an IPS, and P C the P i probability of a communication module, the following relationships are satisfied: P IPS =P IPM =0 : 5 , P C =P IPM =0 : 1 . The second scalable example is the system-on-chip ESEN n m with the architecture described in Figure 5 for the case n =8 , m =2 . The system includes ( n m ) = 2 Intellectual Property cores IPA and ( n m ) = 2 Intellectual Property cores IPB interconnected by a ESEN multiexchange interconnection network with n inputs [28], through m 1 concentrators (C) in case m> 1 , in which each switching element (SE) of the first and last stage have a redundant copy. The system is operational if ( n m ) = 2 1 unfailed IPAs and ( n m ) = 2 1 unfailed IPBs can communicate through the interconnection network. It is assumed that links are not affected by manufacturing defects. Thus, the system can be conceptualized as made up of only IPAs, IPBs, SEs and, in case m> 1 , Cs. As in the first scalable example, manufacturing defects are modeled using a negative binomial distribution with clustering parameter =3 and for the expected number of defects two values will be assumed: =2 and =4 . Furthermore, the probabilities P i will be taken so that P L = P C i =1 P i =0 : 5 (and, then, 0 has the values 1 and 2) and, calling, P IPA the P i probability of an IPA, P IPB the P i probability of an IPB, P SE the P i probability of a SE, and P C the P i probability of a C, the following relationships are satisfied: P IPB =P IPA =0 : 5 , P SE =P IPA =0 : 05 and P C =P IPA =0 : 02 . Table 1 gives the number of components C of the benchmarks which will be used to evaluate the performance of the combinatorial methods and the number of gates of the gateSE_2_0 SE_0_1 SE_0_2 SE_1_2 SE_1_3 SE_2_1 SE_0_3 SE_2_2 SE_2_3 SE_1_1 SE_4_0 SE_4_2 SE_4_3 SE_4_1 C C C C C C C C C C C C C C IPA_0 IPA_1 IPA_2 C C IPA_3 Stage 2Stage 0 Stage 1 Stage 3 SE_1_0 IPB_4 IPB_5 IPB_6 IPB_7 IPB_0 IPB_1 IPB_2 IPB_3 IPA_4 IPA_5 IPA_6 IPA_7 SE_0_0 Figure 5. Architecture of system-on-chip ESEN8x2. Table 1. Number of components ( C ) of the benchmarks and number of gates of the gate-level descriptions of the corresponding fault-tree functions. benchmark C gates MS2 18 27 MS4 30 51 MS6 42 75 MS8 54 99 MS10 66 123 ESEN4x1 14 13 ESEN4x2 26 26 ESEN4x4 34 74 ESEN8x1 32 73 ESEN8x2 56 122 ESEN8x4 72 314 level descriptions of the corresponding fault-tree functions used in the experiments. 4Results All experiments reported in this section were performed in a workstation with a Sun-Blade-1000 processor and 4 GB of memory. We will examine first how the ordering of the multiple-valued variables w v 1 ::: v M affects the size of the ROMDD. After that, we will examine how the ordering of the binary variables within each group of binary variables encoding a multiple-valued variable affects the size of the coded ROBBD which is built to derive from it the ROMDD. We will run the method with an error requirement " =2 10 3 . Table 2 gives the sizes (number of nodes) 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
of the ROMDD for all benchmarks under the orderings of the multiple-valued variables wv, wvr, vw, vrw, t, w, and h defined in Section 2. The heuristic weight (w) is consistently the one which yields better results. The ordering wvr ( W V M ::: V 1 ) gives ROMDDs of exactly the same size as w, but it fails in one case in which the method succeeds under the ordering w. Table 3 gives the sizes (number of nodes) of the coded ROBDDs from which the ROMDDs are obtained for the ordering w for the multiple-valued variables and the orderings ml, lm and w for the groups of binary variables considered in Section 2 to be used in conjunction with the ordering w for the multiple-valued variables. The heuristic ml seems to be the best one: it gives better results in all cases except for MS4, in which the other two heuristics perform slightly better. It is interesting to note that the differences among the three heuristics are small and that the heuristics lm and w give exactly the same results in all cases. Based on our experiments, it seems that the best heuristics are w for the multiple-valuedvariables and ml for the groups of binary variables encoding each multiple-valued variable. We will asses more depthly the performance of the method for those heuristics. Table 4 gives, for the benchmarks in which the method succeeded, the CPU times, peak number of ROBDD nodes (maximum sum of the nodes of the ROBDDs which had to be held simultaneously in memory when processing the generalized fault-tree), size of the coded ROBDD and size of the ROMDD. Several comments are in order. First, CPU times are reasonable in all cases, since in the worst case (ESEN8x2, =2 ) the CPU time is about 18 minutes. Second, the peak number of ROBDD nodes can be or not much larger than the size of the final coded ROBDD. In practice, the application of the method is limited by that peak, since it is that peak which determines the peak memory consumption of the method. Third, the size of the coded ROBDD is always about 10 times the size of the ROMDD. With that factor, even an efficient implementation of ROMDDs is likely to consume more memory than the coded ROBDD, which has a much simpler structure. Thus, the approach of working with coded ROBDDs and translate the final coded ROBDD to the ROMDD required to perform the yield computations seems to be a good approach. This is consistent with the conclusion reached by researchers in the ROMDD community that coded ROBDDs is probably the most efficient way of handling ROMDDs [24]. Putting all results together, it seems that the method can efficiently compute the yield of systems with up to about 60 components when the average number of lethal defects is moderate ( =2 ) and up to about 30 components when the average number of lethal defects is large ( =4 ). The number of components which the method can handle depends, of course, on the value of the truncation parameter M . That parameter had value 6 for the examples with =2 and value 10 for the examples with =4 . 5 Conclusions Systems-on-chip have reached a complexity degree that make them very susceptible to manufacturing defects so that reasonable yields can only be achieved with the use of faulttolerant techniques. That application of fault-tolerance calls for efficient methodologies for evaluation of yield of faulttolerant systems-on-chip. Such evaluation is difficult because realistic models for manufacturing defects production have clustering and, thus, introduce dependencies among the failed states of the components making up the system. In this paper, we have developed a combinatorial method for the evaluation of yield of fault-tolerant systems-on-chip supporting realistic models with clustering for manufacturing defects production. The method builds a ROMDD of a boolean function with multiple-valued variables which allows to compute with a predefined accuracy the yield. The ROMDD is built automatically from a gate-level description of the fault-tree specifying the structure function of the system. The computational complexity of the method increases with the expected number of lethal defects in the fault-tolerant system. We have shown, however, that the method is able to deal using currently affordable computational resources with systems having tens of components. In the future, we are planning to extend the method to allow the evaluation of the operational reliabilityof a fault-tolerant system-on-chip taking into account manufacturing defects. References [1] A. V. Aho, J. E. Hopcroft and J. D. Ullman, Data structures and algorithms, Addison-Wesley, 1983. [2] The BDD Library. Available at http : == www 2 : cs : cmu : ed u = modelche ck = bdd : ht ml . [3] L. Benini and G. De Micheli, “Networks on Chip: A New SoC Paradigm,” IEEE Computer, 2002, vol. 35, no. 1, pp. 70–78. [4] M. Bouissou, F. Bruy`ere and A. Rauzy, “BDD Based Fault-Tree Processing: A Comparison of Variable Ordering Heuristics,” Proc. European Safety and Reliability Association Conference (ESREC’97),1997, C. Guedes Soares, ed., vol. 3, pp. 2045–2052. [5] R. E. Bryant, “Graph-BasedAlgorithmsfor Boolean Function Manipulation,” IEEE Trans. on Computers, 1986, vol. C-35, no. 8, pp. 677–691. [6] K. M. Butler, D. E. Ross, R. KapurandM. Ray Mercer, “Heuristicsto Compute Variable Orderings for Efficient Manipulation of Ordered Binary Decision Diagrams,” Proc. 28th ACM/IEEE Design Automation Conference, 1991, pp. 417–420. [7] J. Cunningham,“The Use and Evaluation of YieldModelsin Integrated Circuit Manufacturing,”IEEE Trans. on SemiconductorManufacturing, 1990, vol. 3, no. 2, pp. 60–71. [8] M. Fujita, H. Fujisawa and N. Kawato, “Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams,” Proc. IEEE Int. Conf. on Computer Aided Design (ICCAD’88), 1988, pp. 2–5. [9] M. Fujita, Y. Matsunaga and T. Kakuda, “On Variable Ordering of Binary Decision Diagrams for the Application of Multi-level Logic Synthesis,” Proc. IEEE European Conference on Design Automation (EDAC’91), 1991, pp. 50–54. [10] M. Fujita, H. Fujisawa and Y. Matsunaga, “Variable Ordering Algorithms for Ordered Binary Decision Diagrams and Their Evaluation,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 1, January 1993, pp. 6–12. 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)
Table 2. Size (number of nodes) of the ROMDDs used in the method for the evaluation of yield for " =2 10 3 for the heuristics for the ordering of the multiple-value variables wv, wvr, vw, vrw, t, w, and h (— indicates that the method failed due to excessive memory requirements). benchmark wv wvr vw vrw t w h MS2, =2 3,202 2,034 2,035 73,405 3,202 2,034 3,202 MS4, =2 28,392 22,760 22,761 882,505 28,392 22,760 28,392 MS6, =2 119,260 103,228 103,229 3,989,917 119,260 103,228 119,260 MS8, =2 344,320 309,136 309,137 — 344,320 309,136 344,320 MS10, =2 797,908 731,748 731,749 — 797,908 731,748 797,908 MS2, =4 25,038 7,534 7,535 — 25,038 7,534 25,038 MS4, =4 1,345,390 — — — 1,345,350 635,530 1,345,350 ESEN4x1, =2 5,090 3,046 3,047 190,059 5.090 3,046 5,090 ESEN4x2, =2 11,031 6,995 6,996 486,205 11,031 6,995 11,031 ESEN4x4, =2 29,391 19,547 19,548 1,469,685 29,391 19,547 29,391 ESEN8x1, =2 169,764 134,512 134,513 — 169,764 134,512 169,764 ESEN8x2, =2 373,117 303,657 303,658 — 373,117 303,657 373,117 ESEN4x1, =4 38,594 11,666 11,667 — 38,594 11,666 38,594 ESEN4x2, =4 97,671 30,783 30,784 — 67,671 30,783 97,671 ESEN4x4, =4 296,175 96,231 96,232 — — 96,231 — Table 3. Size (number of nodes) of the coded ROBDDs used in the method for the evaluation of yield for " =2 10 3 for the heuristic w for the ordering of the multiple-value variables and the heuristic ml, lm and w for the ordering of the groups of binary variables. benchmark ml lm w MS2, =2 24,237 28,418 28,418 MS4, =2 243,254 236,915 236,915 MS6, =2 1,120,255 1,290,274 1,290,274 MS8, =2 3,154,056 3,283,401 3,283,401 MS10, =2 7,954,261 10,019,092 10,019,092 MS2, =4 361,428 439,700 439,700 MS4, =4 11,885,214 11,492,704 11,492,704 ESEN4x1, =2 19,338 20,721 20,721 ESEN4x2, =2 54,705 65,208 65,208 ESEN4x4, =2 184,332 283,338 283,338 ESEN8x1, =2 904,777 972,506 972,506 ESEN8x2, =2 2,244,340 2,796,165 2,796,165 ESEN4x1, =4 105,511 109,692 109,692 ESEN4x2, =4 378,686 414,939 414,939 ESEN4x4, =4 1,513,441 2,117,587 2,117,587 0-7695-1959-8/03 $17.00 (c) 2003 IEEE Proceedings of the 2003 International Conference on Dependable Systems and Networks (DSN’03)