換刀機(jī)械手設(shè)計(jì)帶CAD圖

換刀機(jī)械手設(shè)計(jì)帶CAD圖,機(jī)械手,設(shè)計(jì),CAD JOURNAL OF ELECTRONIC TESTING: Theory and Applications 19, 537548, 2003c ? 2003 Kluwer Academic Publishers. Manufactured in The Netherlands.On-Line Monitor Design of Finite-State MachinesFENG GAO AND JOHN P. HAYESAdvanced Computer Architecture Lab., University of Michigan, Ann Arbor, MI 48109, USAReceived July 21, 2002; Revised November 24, 2002Editors: C. Metra and M. Sonza ReordaAbstract.On-line monitoring is a useful technique for ensuring system reliability. By continuously supervisingthe systems operation, a wide range of problems, such as physical defects, transient faults and design errors,can be detected. A monitor Ms behavior can be viewed as an abstraction of the target system Ms behavior,and can be represented by a homomorphic mapping from M to M. We present a systematic procedure to selecthomomorphisms for monitor design and measure their costs based on a behavioral fault model. Analysis of themethodshowsthatmonitorswithveryfewstatesandlowareacanprovidehighfaultcoverage.Experimentalresultsare presented which quantify the basic trade-off between area overhead and fault coverage. Simulation results underthe industry-standard single stuck-at fault model are also reported.Keywords:on-line monitoring, homomorphism, finite-state machine1.IntroductionIncreasingly, integrated circuits (ICs) are being usedin safety-critical applications, from anti-lock brakingin automobiles, to fly-by-wire aircraft, to prostheticsystems in the human body. At the same time, ICsare becoming more complex and compact, resultingin their increased susceptibility to transient or in-termittent faults. Such faults affect the behavior ofthe circuits from time to time and must be detectedquickly, suggesting a need for efficient on-line er-ror monitoring. An on-line monitor continuously su-pervises the operation of a circuit and reports illegalbehavior.On-line monitoring strategies can be applied at var-ious levels of abstraction, ranging from the gate andregister-transfer levels to the system level. Run-timeerrors can be caught if we can check whether the cur-rent outputs are valid. In such approaches, the outputsof a circuit are usually encoded with an error-detectingcode, and a monitor detects the occurrence of non-codeoutputs.Astraightforwardapproach18istoap-pendcheckbitstothenormaloutputbits.Theresultingdesigns consist of functional logic, a check-bit gener-ator, and a checker. The functional logic generates thenormal outputs, the check-bit generator generates thecheck bits, and the checker determines if the outputsarevalidcodewords.Variousencodingmethods,forin-stance, group parity codes 20 and Berger codes 14,can be used to encode the outputs. A basic disadvan-tage of these methods is that a single fault inside thecircuit may change the outputs to other codewords andso be undetectable.We can also embed self-testing structures in the tar-getdesign.Testsforfunctionalmodulescanthenbeap-plied during the cycles when the modules are inactive.If the module functions are simple and the free cyclesfor each functional module can be pre-determined, wecanschedulethetestandnormaloperationsatthesametimewithoutclearlydefiningaboundarybetweenthesetwo modes 8. On the other hand, if the cycles duringwhich a module is inactive are irregular, extra controlsignals may be needed to switch between the testingand normal modes 15. The main disadvantage of thistype of self-testing is that it is not good at detectingtransient faults.538Gao and HayesSignatureanalysis12isanotherwidelystudiedap-proach to on-line monitoring of programmable sys-tems. A co-processor, often called a watchdog ordiagnostic processor, whose duties include signaturecomputation and checking, is usually employed. Errordetection by means of a watchdog is a two-phase pro-cess. In the first phase, signatures are computed andassigned to basic blocks of the target program, wherea basic block is a set of instructions with no jumps al-lowed from or into these instructions. During the sec-ond phase, the monitor computes run-time signaturesand compares them with the precomputed signaturesreceived from the target system. Differences betweenthese two sets of signatures reveal permanent or tran-sient errors. Besides their limited ability to detect data-related errors, such methods also cause performancedegradation by increasing the number of instructionsin a program.In this paper, the system to be monitored M is mod-eledasafinite-statemachine(FSM),forwhichasimplebehavior fault model is defined. A monitor Mis thenabstracted systematically from the behavioral descrip-tion of M using homomorphisms selected under theguidance of appropriate cost measures. The effects ofthe number of states in the monitor on its area over-head and fault coverage are analyzed. It is shown thatone-state monitors, i.e. combinational monitors, havesmall area overhead. Moreover, for FSMs with highoutput/state ratios, such monitors also have very highfault coverage under our behavioral fault model. Sim-ulations under the standard single stuck-at fault modelare also performed.The remainder of this paper is organized as follows.After the introduction of some notation and our systemmodel in the next section, we propose an algorithm forFSM behavior abstraction based on homomorphismsin Section 3. Section 4 analyzes how the area overhead 0/1,1/10/0,1/10/1,1/00/01/01/10/00/1,1/1 0/11/1AE FB CGD 0/1,1/10/0,1/10/1,1/00/01/00/00/1,1/1 0/11/1AEFB CGD1/1 0/1,1/1 0/0,1/10/1,1/00/11/0 1/10/00/1,1/1 0/11/1AE FBC GD (a) (b) (c)Fig. 1.(a) An example FSM M, (b) a next-state fault of M, and (c) an output fault of M.and fault coverage of the monitors vary with respectto the number of states in the monitors. Experimentalresults are presented in Section 5, while some conclu-sions are discussed in Section 6.2.System ModelA finite-state machine (FSM) M is defined as a 6-tuple I, S, O, S0, where I is the set of inputs,S is the set of states, : I S 2Sis the state tran-sition function, S is the set of outputs, : I S 2Ois the output function, and S0 S is the set of initialstates 11. An FSM is deterministic if and are de-terministic, that is, no input can map the machine totwo or more outputs or next states at the same time. AnFSM can be described using a state transition graph(STG). The STG of M is denoted by GM(VM, EM),where VMis the set of nodes, representing the state setof M and EM= ?u,v?,u,v VMisthesetofedges,representingthetransitionsetof M.Eachedge?u,v?islabeled with a set of input-output pairs, each of whichdenotes an input that triggers the state transition andthe corresponding output. The number of edges thatstart from or end at a state u VMis called the degreeof u. The maximum degree of all the states is calledthe degree of the STG. For convenience, the degree ofthe STG is also referred to as the degree of the corre-sponding FSM. Fig. 1(a) shows a state transition graphrepresenting a seven-state FSM. The degrees of stateA, D, and F are two, while that of B is four, which isthe maximum degree of all these states. Therefore, thedegree of the STG is four.Let M = I, S, O, S0 be the specification ofan FSM, and M?= I, S,?, O,?, S0 be its imple-mentation. M?has a next-state fault on receiving inputi in state s if (s,i) ?= ?(s,i), where s S and i I.On-Line Monitor Design of Finite-State Machines53900,11 01,11 01,10 00 10 1100 01,11 01 11A E FB C G D(a)00,11 01,1101,10 00 10 1100 01,11 01 11 E FC G D (b)AB Fig. 2.(a) Base monitor M0; (b) monitor M1formed by applying a state homomorphism to M0.M?has an output fault on receiving input i in state sif (s,i) ?= ?(s,i), where s S and i I. We referto next-state faults and output faults as behavior faults.Two versions of M with behavior faults are given inFig.1(b)and(c).Thedottedrectangleshighlightanext-state fault and an output fault of M. For simplicity, weassume that an FSM has at most one next-state or oneoutputfaultatanytime.Wecallthisthesinglebehaviorfault (SBF) model.With the concepts defined above, we now in-troduce our overall system model. Suppose M=I, S, O, S0 is the FSM to be monitored. Wefirst define a base monitor M0=I O, S,0,0,1,0, S0, which is able to detect all the SBFs ofM, where (1) 0(ab,s) = (a,s), for a I,b O,and (2) s S and 0(ab,s) = 0 if (a,s) = b; other-wise, the output is 1 indicating an SBF. For example,the base monitor of the FSM M in Fig. 1(a) is showninFig.2(a).Forbrevity,onlythosetransitionswithout-put 0 are shown, while those with output 1 are omitted.Therefore, the indicated transitions correspond to allvalid transitions in M.We next perform behavior abstraction on the basemonitor using homomorphisms, which provides thetheoretical foundation for our approach. A many-to-one mapping H =(I,S,O) is an FSM homomor-MonitoredFSM MMonitorM*State info.YError EMonitor M*YFSM MCInterface logic ILXZESystem inputs XSystem outputs Z(a)(b)Fig. 3.On-line monitoring system: (a) overall structure; (b) monitor design.phism from M1= I1, S1,1, O1,1, S01 to M2=I2, S2,2, O2,2, S02 if and only if I(i1) I2fori1 I1,S(s1) S2for s1 S1,O(o1) O2for o1 O1,S(1(i1,s1) = 2(I(i1),S(s1) andO(1(i1,s1) = 2(I(i1),S(s1) for i1 I1,o1O1. M2is the homomorphic image of M1. Fig. 2(b)shows a homomorphic image of the FSM M0inFig.2(a).Thisparticularhomomorphismmapsstates Aand B of M0into one state in its image, while all otherstates, inputs and outputs are mapped to themselves.Intuitively, a homomorphism reduces the number ofstates and preserves the mappings of the next-state andoutput functions; hence it is a precise form of behaviorabstraction.The overall monitoring scheme is illustrated inFig. 3(a). The monitor Moperates in lockstep withM, it can mimic the state transitions of M and reportSBFs with just a one-cycle delay. If the monitor is thebase monitor M0, all possible SBFs can be detected.If lower fault coverage is allowed, we can perform ho-momorphismson M0toobtainasmaller,andthereforemore economical, monitor M. As shown in Fig. 3(b),Mis composed of two parts: interface logic whichimplements the homomorphisms from M to M, and acompact FSM Mcwhich approximates the state transi-tions of M.540Gao and Hayes3.Abstraction AlgorithmTo reduce the monitor area, we apply homomorphismsto M0in two stages called the state and input stages.In the state homomorphism stage, we gradually reducethe number of states in the monitor. The fault coveragehencedecreasesduetothelimitedknowledgeavailableconcerning target system states. While in the input ho-momorphism stage, we only perform a simple trans-formation, which does not hurt the fault coverage. Wedonotconsideroutputhomomorphisms,sincethebasemonitor has only a single output. Note that the inputsof M0incorporate both the inputs and outputs of theoriginal machine M.The state homomorphism stage involves construct-ing a series of homomorphisms of the form: M0M1 M2 Mn= M. Each homomor-phism H: Mi Mi+1(0 i n) maps two states ofMito one state of Mi+1. Such mappings are referredto as simple state homomorphisms. While H reducesthe number of states in the monitors, the number of de-tectableSBFsalsodecreasesbecauseofthestatemerg-ing. Homomorphisms that lead to as few undetectableSBFs as possible are desirable, because our goal is toobtain monitors with small area, capable of detectingas many SBFs as possible. Furthermore, the number ofavailable simple state homomorphisms is proportionalto the square of the number of states in the monitor.Therefore, to guide the selection of simple state homo-morphisms, we define a homomorphism cost functionC(H) that measures the homomorphisms impact onfault coverage.For a homomorphism H: Mi Mi+1, C(H) is thenumberofSBFsthatbecomeundetectableifwereplaceFig. 4.The three types of SBFs and the corresponding homomorphism costs.Miwith Mi+1as the monitor. In fact, those faults canreadily be enumerated. To facilitate the calculation, weclassify them into three types, which are defined nextvia an example, along with a calculation method. Wedenotetheinputsthattriggertransitionsfromstates1tostate s2by tr input(s1,s2), and the states in M0that aremappedtos bypre-image(s).Let|T|bethecardinalityof set T. Using the base monitor and its homomorphicimage in Fig. 2 as an example, the base monitor M1in Fig. 2(b) is obtained by applying a simple state ho-momorphism H to M0, which maps states A and Bof M0into one state AB of M1. The three SBF typesintroduced by H are as follows. Next-state-change faults. If the next state of a tran-sition changes erroneously from B to A, this faultbecomesundetectablewhenwereplace M0with M1as the monitor. For example, the transition from Eto A on receiving input 01 or 10 is detectable in M0.This fault is, however, undetectable using M1. Thetransition from G to B on input 11 also belongs tothis type. The associated cost C1(H) is defined as:C1(H) = |pre-image(E)| |pre-image(A)| 2+|pre-image(G)| |pre-image(B)| 1Theconstantcoefficients2and1arethecardinalitiesof tr input(E, B) = 01,10 and tr input(G, A) =11. In general, if states s1and s2are to be mergedand some inputs trigger the transition from a state sto s1or s2, each input corresponds to a next-state-change fault that will escape detection by the imagemonitor. The general formula to compute the costC1(H) is given in the first row of Fig. 4.On-Line Monitor Design of Finite-State Machines541 Current-state-change faults. State transitions withcurrent state A or B can also become undetectable iftheir destinations are different, forming the secondfault type. For instance, next-state fault A00 C isdetectedby M0.Aftermapping A and B toonestate,M1is not able to determine if the transition is ini-tiated from A or B, causing undetectable next-statefault A00 C. Erroneous transitions falling into thistype also include A00 F and B00,11 B. Similarly,we can construct a cost function C2(H) for this faulttype as follows:C2(H) = |pre-image(A)| |pre-image(C)|+|pre-image(A)| |pre-image(F)|+|pre-image(B)| |pre-image(B)| 2The general formula for C2(H) is shown in the sec-ondrowofFig.4.Wecanreadtheformulaasfollows.If states s1and s2are to be merged and some inputstriggersthetransitionfroms1ors2toastates,eachofthe inputs introduces to a current-state-change faultthat will escape detection by the image monitor. Current-next-state-exchangefaults.Theexistenceofa state transition from A to B causes undetectablenext-state faults, which change both the current andnext states of the transition. For example, erroneoustransition B00,11 A, which has different current andnext states from valid transition A00,11 B, becomesundetectablein M1.Thecostcontributedbythistypeof fault isC3(H) = |pre-image(B)| |pre-image(A)| 2In general, suppose that states s1and s2are to bemerged into a single state s, and input i causes atransition from s1to s2, the faulty transition from s2to s1on input i corresponds to a current-next-state-exchange fault that cannot be detected by the imagemonitor. The general formula of C3(H) is shown inthe third row of Fig. 4.ThetotalcostC(H)ofasimplestatehomomorphismH that maps state s1and s2into one image is the sumC1(H)+C2(H)+C3(H) of the costs specified above.The formulas in Fig. 4 indicate the complexity of com-puting C(H). Given a state pair, the only computationisagroupofsetdifferences,whosecomplexityis O(d),whered isthedegreeofthemonitoringFSM.Therearein total |S|2state pairs, resulting in a final complexityof O(d|S|2).We turn next to the selection of the homomorphismsused to construct M. In general, a homomorphismH can introduce non-determinism. For example, M1in Fig. 2(b) is non-deterministic because applying in-put 00 to state AB triggers transitions to itself and toC. Such non-determinism is easily eliminated, but itincreases the number of states. Thus we want to se-lect homomorphisms that have both low cost C anddeterministic images. To aid this heuristic selectionprocess, we introduce the state dependency graph. Astate dependency graph (SDG) G =(V, E) of an FSMM= I, S, O, S0 is a directed graph, whereeach node niis labeled by two states (si,1,si,2) rep-resenting a homomorphism ?i= (i,I,i,S,i,O),where i,S(si,1) = i,S(si,2) = s, and other states, in-puts and outputs are mapped to themselves. There isan edge (ni,nj) from nito njin G if there is an in-put t such that (si,1,t) = sj,1and (si,2,t) = sj,2, orelse (si,1,t) = sj,2and (si,2,t) = sj,1. Intuitively,the edge (ni,nj) indicates that if we apply homomor-phism ?i, we must also apply homomorphism ?jtoeliminate non-determinism due to ?i. In the FSM inFig. 2(a), the next states of states A and B on input 00are B and C, respectively. Therefore, there is an edgefrom node (A, B) to (B,C), as shown in Fig. 5. For astate pair (si,1,si,2), we have to compare the inputs forevery state pair that si,1and si,2may transit to, result-ingind2comparisonsintheworstcase.Theworst-casecomplexityofconstructingtheSDGishence O(d2|S|2)since we have to make the comparison for every statepair. The SDG is similar to the implication graph usedfor FSM minimization 10. The major difference isthat in an SDG, we only consider whether two stateshave the same next states on all inputs, while in anA,BG,EB,C C,DE,AB,FE,BFig. 5.Part of the SDG for M0in Fig. 2(a).542Gao and HayesFig. 6.Heuristic algorithm for state homomorphismselection.implicationgraph,wetakebothnextstatesandoutputsinto consideration.Astronglyconnectedcomponent(SCC)inadirectedgraphisasetofnodesinwhichtherearepathsbetweenany two nodes. The dotted lines in Fig. 5 indicate someSCCs in the SDG. SCCs that do not depend on otherSCCsrepresentsetsofmappingsthatshouldbeappliedtogethertoavoidnon-deterministicimages.Thehomo-morphism cost of an SCC is the sum of the costs of thesimple state homomorphisms represented by the nodesin the SCC. We apply homomorphisms represented bynodes in SCCs with the lowest cost during the abstrac-tionprocessuntilnofurtherhomomorphismscanbeap-plied without violating fault coverage constraints. Thealgorithm is shown in Fig. 6. The complexity of thealgorithm is dominated by SDG construction, whichoccurs in every iteration. Since each iteration reducesthe number of states by at least one, the maximumnumber of iterations is |S|. Therefore, the worst casecomplexity of the overall algorithm is O(d2|S|3).After the state homomorphism stage, homomor-phisms that map the inputs to a smaller input spacecanbeapplied.Fig.7showsamonitor Mobtainedaf-ter the state homomorphism stage on base monitor M0in Fig. 3 has been completed. Note that this monitorsSt0=A, E St1=B,C, FSt2=D,G00,10,01,1100, 1011,0111,01Fig. 7.Sample monitor M.behavior is incompletely specified. For instance, thetransitions of state st2 on inputs 00 and 01 are not de-fined. The reason for this is that valid inputs of thetarget machine M are usually only a non-trivial sub-set of the whole input space. We can think of this assaying there is a dummy state serving as the next stateof the unspecified transitions, and the output of thosetransitions is 1, indicating an error in M.The input space is naturally partitioned into twogroups by the state transitions initiated from state st1by inputs 00, 10 and inputs 11, 01. Similarly, state st2also divides the input space into two groups based onits transitions. The inputs that can be mapped to thesame image are those always in the same group for allpartitions. For example, inputs 01 and 11 of Mare inthe same group because they always trigger transitionswith the same next states and outputs for all currentstates. On the other hand, inputs 00 and 01 cannot bemapped to the same image input because they result inthe same next state when the current state is st0, but re-sultindifferentnextstateswhenthecurrentstateisst1.Therefore, instead of considering inputs pair by pair,we form a cross product of all the partitions made bythe states. All inputs in the same partition of the crossproducts can then be mapped to the same image.In the above algorithm, state abstraction starts di-rectly from the base monitor. One can ask whether it isbeneficial to extend the two-stage approach (state ho-momorphism selection followed by input homomor