Specification-based Compaction of Directed Tests for
Functional Validation of Pipelined Processors∗

 Heon-Mo Koo†                                                                                   Prabhat Mishra

Intel Corporation Computer & Information Science & Engineering 1900 Prairie City Road University of Florida Folsom, CA 95630, USA Gainesville, FL 32611, USA heon-mo.koo@intel.com prabhat@cise.ufl.edu

ABSTRACT can still be extremely large. Therefore, there is a need for Functional validation is a major bottleneck in micropro- efficient test reduction techniques. cessor design methodology. Simulation is the widely used In directed test generation, although a test is generated for method for functional validation using billions of random activating a particular functional fault, it may go through and biased-random test programs. Although directed tests several pipeline stages and paths over multiple clock cycles require a smaller test set compared to random tests to achieve to reach the target fault. Therefore, there is a high proba- the same functional coverage goal, there is a lack of auto- bility that the test can accompany multiple pipeline inter- mated techniques for directed test generation. Furthermore, actions before and after it reaches the target functionality. the number of directed tests can still be prohibitively large. Based on this fact, we present an FSM coverage-directed This paper presents a methodology for specification-based selection of minimal fault set to reduce the number of func- coverage analysis and test generation. The primary con- tional tests required for validation of pipelined processors. tribution of this paper is a compaction technique that can The goal is to generate a reduced set of test vectors without drastically reduce the required number of directed test pro- sacrificing the coverage requirement. It is important to note grams to achieve a coverage goal. Our experimental results that we perform compaction of required faults before test using a MIPS processor and an industrial processor (e500) generation and therefore only need to generate a reduced set demonstrate more than 90% reduction in number of directed of tests. This is in contrast with the existing test compaction tests without sacrificing the functional coverage goal. approaches, especially in the domain of manufacturing test, where compaction is performed after test generation, there- Categories and Subject Descriptors: B.6.3 [Logic De- fore, the existing approaches does not reduce the cost of test sign]: Design Aids - Verification generation. Our approach can significantly reduce the test generation cost as well as the overall validation effort using General Terms: Design, Verification the reduced set of functional tests. Keywords: Test Compaction, Processor Validation Processor Specification

1. INTRODUCTION
                                   Verification complexity is increasing at an alarming rate
   

since it is directly proportional to the design complexity Processor Model Coverage Model growth of modern processors. A major challenge is how (FSM) (FSM states/transitions) to reduce the overall functional validation effort. In the cur- rent industrial practice [1, 16], random and biased-random test program generation at architecture (ISA) level is most Compaction widely used for simulation-based validation to uncover er- (States & Transitions) rors early in the design cycle. A test program consists of a sequence of instructions. Compared to random or biased- random tests, directed test generation can significantly re- Test Generation duce overall validation effort since the shorter tests can ob- tain the same coverage goal. The number of directed tests ∗ Reduced Test Set Corporation and NSF CAREER award 0746261.†This work was partially supported by grants from Intel Figure 1: Functional test compaction methodology This work was performed when the author was a graduate Figure 1 shows the overall flow of our fault selection and student at the University of Florida. associated test generation methodology. From specification Permission to make digital or hard copies of all or part of this work for of a processor, we create a finite state machine (FSM) model personal or classroom use is granted without fee provided that copies are and define FSM state and transition coverage metrics based not made or distributed for profit or commercial advantage and that copies on pipeline interactions. FSM compaction is performed be- bear this notice and the full citation on the first page. To copy otherwise, to fore test generation by eliminating the states and the tran- republish, to post on servers or to redistribute to lists, requires prior specific sitions that are illegal, redundant, or unreachable based on permission and/or a fee. design constraints. The remaining states and transitions are CODES+ISSS’08, October 19–24, 2008, Atlanta, Georgia, USA. Copyright 2008 ACM 978-1-60558-470-6/08/10 ...$5.00. represented in the proposed binary format. One of the un-

covered states or transitions is chosen as a target for directed has been no significant progress in functional test compaction test generation. A path in FSM is traversed from a given in validation domain because functional tests are considered point by tracing backward to an initial state and tracing as one-time effort in design methodology. However, millions forward to a final state from that point. During the trace of tests are used in the current industrial practice, and re- process, we select an uncovered transition to minimize test gression test is conducted every day during design cycle. redundancy as well as test volume. The number of uncov- Therefore, reduction in functional tests will have significant ered states and transitions are reduced by eliminating the impact on overall design effort by removing redundant tests states and transitions on the path. We use model check- as well as selecting effective tests. ing to generate a test program to exercise the path. Path selection and test generation continues until all states and 3. FSM MODEL AND COVERAGE transitions are covered. This paper makes three important Our FSM model can be generated from an Architecture contributions. First, we propose a simple but efficient FSM Description Language (ADL) [12] specification by defining model of pipelined processors. Second, we define FSM state desired functionalities of a processor using states and their and transition coverage based on pipeline interactions. Fi- transition functions. The proposed FSM model is used to nally, we propose efficient techniques for fault selection and generate a set of test programs based on FSM coverage met- test generation to reduce overall validation effort. rics. The test set is reusable during design validation at dif- The rest of the paper is organized as follows. Section 2 ferent levels of abstraction including specification and im- presents related work addressing FSM modeling and test plementation. compaction in the context of test generation. Section 3 de- scribes our FSM modeling and functional coverage for val- 3.1 FSM Modeling of Pipelined Processors idation of pipelined processors. Section 4 presents our test An FSM model is defined as M = (I, O, S, δ, λ) where I, compaction technique. Section 5 describes coverage-driven O, S, δ, and λ are a finite set of inputs, outputs, states, test generation followed by a case study in Section 6. Fi- state transition function δ : S × I → S, and output func- nally, Section 7 concludes the paper. tion λ : S × I → O, respectively. When the model M is 2. RELATED WORK in the state s (s ∈ S) and receives an input a (a ∈ I), it moves to the next state specified by δ(s, a) and produces an FSM model-based test generation has been developed for output given by λ(s, a). For an initial state s₁, an input validation of pipelined processors where an FSM model is sequence x = a₁, ..., aₖ takes the M successively to states used to generate a test suite based on state, transition, or si+1 = δ(si, ai), i = 1, ..., k with the final state sₖ₊₁. In path coverage [2, 20]. A significant bottleneck in these meth- the pipelined processor FSM model, assuming each ai cor- ods is the high complexity of FSM models, resulting in state responds to instruction(s) fetched from instruction cache (or explosion problem. To alleviate FSM complexity, abstrac- memory), the input instruction sequence x = a₁, ..., aₖ can tion techniques have been proposed [3, 8, 13, 15, 17]. The be used as a test program to exercise the path consisting of abstract FSM models provide feasible ways of concrete test the states and the state transitions from s₁ to sₖ₊₁. generation. Abstract tests are generated from the abstract 3.1.1 Modeling of FSM States FSM and then they are converted into test programs. Com- pared to the existing approaches, our FSM model is easy to We create the functional states S in the form of binary create and analyze because its states describe the functional data from the processor specification that contains both the status of each functional unit. pipelined structure and the behaviors of the processor. The Due to the large volume of test data and the extremely proposed FSM model is based on interactions among func- long test time for manufacturing test, considerable research tional units of the pipelined processor. A group of bits are has been done to reduce the structural test data volume. assigned to describe the functional status of each functional Test compaction techniques are generally categorized into unit. A functional state of the entire processor consists of dynamic and static compactions. Dynamic compaction is bit concatenation of local states of all functional units. We applied during test generation while static compaction is denote the number of activities in the functional unit f uj applied after test generation. Rudnick and Patel [14] have by rj and the number of bits to be assigned to the unit by bj proposed dynamic test compaction for sequential circuits us- where j = 1, ..., U and U is the number of functional units ing fault simulation and genetic algorithms. El-Maleh and in the processor. Therefore, the total number of bits to de- P Osais [5] have presented decomposition-based static com- scribe the processor FSM states is N = Uj=1 bj. We denote paction algorithms where a test vector is decomposed into the number of states in the machine M by N S = |S| = 2ᴺ . atomic components and the test vector is eliminated if its The state of functional unit f uj is denoted as ssj using bj components can be all moved to other test vectors. Set bits and the state sₖ of the processor FSM can be defined covering has been applied to static compaction procedures by concatenating ss₁, ss₂, ..., ssU . for combinational circuits using the fault detection matrix For example, we assign two bits to represent four func- [6, 9]. Dimopoulos and Linardis [4] have modeled static tional states of Fetch (IF) unit: ‘00’ for idle, ‘01’ for normal compaction for sequential circuits as a set-covering prob- operation (instruction fetch), ‘10’ for stall, and ‘11’ for ex- lem. The matrix reduction techniques [18] can be applied ception. Figure 2 shows an example of the FSM states of the to mitigate the complexity of set covering by eliminating re- pipelined processor. Given that all the functional units have dundant rows (faults) and columns (test vectors) in the fault only four possible states, each unit requires 2 bits for its four detection matrix. functionalities. This binary format of functional FSM model A lot of structural test compaction techniques have been provides an efficient indexing mechanism to access and an- proposed in manufacturing test domain because they have alyze each functional state. In addition, next states can be a significant impact on overall testing cost and time. There described as Boolean functions. For example, assuming the

Bit: B B … … … B B B B tion decided by unit interactions. Therefore, the state s of the processor FSM can be expressed by concatenating ssi,j WB MEM ID IF where i = 1, ..., U and 1 ≤ j ≤ D. Figure 2: Binary format of the states in FSM model 3.2 Functional Coverage state transitions (si, sj) and (si, sₖ) with sj = ‘0011’ and s k State coverage and transition coverage are used as cover- ¯ = ‘0010’, the next states of¯ ¯ si are expressed as B₄B¯₃B₂B₁ age metrics to generate a test set. State coverage ensures

• B¯₄B₃B₂B¯₁ = B¯₄B₃B₂. For each state, a corresponding that every state of an FSM has been visited. Transition cov- index number has a list of the next and previous states that erage ensures that every transition between FSM states has are produced using transition functions. The list of neigh- been traversed. boring states are used for selecting a uncovered path during The state coverage of the proposed FSM model is identi- test generation. cal to the pipeline interaction coverage that tries to detect whether a set of pipeline interactions (between functional

3.1.2 Modeling of FSM Transitions units) have been activated at a given clock cycle. Because The state transition functions are based on pipeline be- each FSM state consists of multiple sub-states of each func- haviors of processors. The pipeline behaviors are the rules tional unit in the processor. Therefore, a test program that in each pipeline stage that determine when instructions can covers the FSM state will activate the corresponding pipeline move to the next stage and when they cannot. For pipeline interaction. We can compute the number of theoretically behavior modeling, we decompose the entire processor FSM possible FSM states based on the number of functional units into smaller FSMs at functional unit level. Since not all the and the number of activities at each unit. In general, the functional units affect the next states of other functional number of activities varies for different units depending on units, the transition functions of the FSM can be decom- what activities we want to test, thereby each unit may re- posed into sub-functions each of which is dedicated to a quire different number of bits for its functional states. Con- specific functional unit. sidering an FSM model with m units where each unit has on average r activities, the FSM will have rᵐ states which Time step: t-1 t can be extremely large even for small number of activities. Stagej-1 fu fu fu Stagej-1 fu k, j-1 For example, a MIPS processor [7] with 17 functional units k’, j-1 k, j-1 k”, j-1 and 4 activities has approximately seventeen billion states. From the point of functionality, the proposed state transi- Stage fu Stagej fu i, j fu i, j tion coverage represents temporal pipeline interactions. Based j i, j on the state transition functions, each state has a list of their next states. When a test visits the state and goes to one of fu fu its next state, we put the next state off the list since the Stagej+1 fu l’, j+1 fu l, j+1 fu l”, j+1 Stagej+1 l, j+1 l, j+1 transition between the two states is covered. State transi- tion coverage of the FSM is achieved when the next state (a) Instruction flow (b) Pipeline interaction lists are empty for every states. The number of state transi- tions is determined by the processor’s functional behaviors. Figure 3: Pipeline behavior Theoretically, the maximum number of state transitions is N 2, where N is the number of states, assuming any state Figure 3 shows the general behaviors of pipelined pro- can be reached from another state in one step. This theoret- cessors. Each instruction goes through the current pipeline ical large number of functional states and transitions can be stage to the next stage as shown in Figure 3(a), where f u reduced by eliminating unreachable states using functional is a functional unit, 1 ≤ i, k, l ≤ U , 1 ≤ j ≤ D, and D is constraints described in the processor specification. the pipeline depth. Each functional unit f ui,j can interact 4. COMPACTION OF FSM MODEL with different number of functional units at stage j − 1 and j + 1. For example, a decode unit may have multiple execu- The state and transition compaction of an FSM plays a tion units at its following stage while a fetch unit typically major role in efficient test generation since reduction of one has only one unit (decode unit) at the following stage. state or transition implies one less test vector to generate Figure 3(b) shows the pipeline interaction of the func- and apply on RTL implementation. The basic idea is to tional unit f ui,j. The state of f ui,j at time step t is de- identify and eliminate all the unreachable and redundant cided by the previous and current states of units f uk,j−1 states as well as transitions with respect to coverage-driven and f ul,j₊₁ as well as itself. For example, if f ul,j₊₁ and test generation. f ui,j are on the same pipeline and f ul,j₊₁ is in the stall 4.1 Identifying Unreachable States state at time step t, then f ui,j should be in stall state be- cause the instruction in f ui,j cannot go to the next stage We use functional constraints described in the processor f ul,j₊₁. Considering feedback loop such as data forwarding specification to distinguish unreachable states from reach- in the pipelined processor, f ui,j at time t will be affected by able ones. The constraints are represented as binary pat- the state of f ui,j+α at (t − 1) where 0 ≤ α ≤ D. terns of FSM states. The states with these patterns are Based on the pipeline behavior, the state transition to the removed from the FSM and they are not considered during functional unit f ui,j at time step t is defined as ssi,j(t) = test generation and coverage analysis since they are unreach- f (ssk,j−1(t − 1), ssi,j(t − 1), ssl,j₊₁(t − 1), ssl,j₊₁(t)). Here, able. For example, assume that decode (ID ) unit has the ssi,j(t) represents a set of bits to describe the functional single instruction issue constraint and there are two parallel state of f ui,j at time t, and f represents a transition func- execution units EX1 and EX2 in the next pipeline stage.

Since only one instruction can be passed to either EX1 or redundant state (transition) is called an inevitable state (tran- EX2, both execution units cannot be in normal operation sition ). Identifying a redundant state (transition) is similar (executes a valid instruction) at the same time. Assuming to finding fault dominance in manufacturing test compaction that EX1 and EX2 correspond to the state variables B₆B₅ except the fact that in this case we do not need the generated and B₄B₃ respectively in 8-bit FSM processor state model, tests. the binary pattern ‘xx0101xx’ represents unreachable states for the single issue constraint, where ‘01’ represents the unit State aaaa State eeee state of normal operation and ‘x’ represents ‘0’ or ‘1’. By applying all the functional constraints described in the pro- State cccc State dddd cessor specification, we can identify the unreachable states State bbbb State ffff in the FSM and compute the number of reachable states. Figure 4: Single transitions between states 4.2 Identifying Illegal State Transitions Extracting FSM state transitions at the processor level is We employ various techniques to remove redundant states very difficult since specification documents do not include and transitions. Figure 4 shows inevitable states and transi- relation of processor-level states in general. However, the tions that have single outgoing transition (from states a and processor specification provides the rules in each pipeline b) and single incoming transition (to states e and f ). The unit about when instructions can move to the next stage state c is an inevitable state because all the paths from a and and when they cannot. These pipeline behaviors are used b should include the state c. Similarly, the state d is an in- to identify illegal state transitions. We also leverage the de- evitable state because all the paths to e and f should include composition of a processor state transition into functional the state d. The transitions (a → c), (b → c), (d → e), and unit level transitions. For example, if the state of a func- (d → f ) are inevitable transitions to their neighbors. We can tional unit ssi,j is in normal operation at time t, then the eliminate the test cases that activate these inevitable states state of the unit in the previous stage (ssk,j−1) cannot be and transitions since any test program that exercises their in idle state at time t − 1 since the instruction in f ui,j must neighboring states will also activate the inevitable states. be ready at the previous pipeline stage at time t − 1. The next state lists of each state are used to identify the in- evitable states of the single outgoing transitions. If a state Table 1: Transition rules between ssk,j−1 and ssi,j has only one state in its next state list, the next state is an inevitable state. In the same way, the previous state lists ssk,j−1(t − 1) ssi,j(t) are used to identify the single incoming transitions. idle idle, stall normal op. normal op., stall, exception 5. TEST GENERATION stall idle, stall exception idle, stall FSM coverage metrics provide a mechanism to evaluate verification progress. In FSM coverage-driven test genera- Table 2: Transition rules between ssi,j and ss i,j tion, tests are created to activate a target coverage point (state or transition). ssi,j(t − 1) ssi,j(t) idle idle, normal op., stall, exception 5.1 Coverage-driven Test Selection normal op. idle, normal op., exception Once all the unreachable and redundant tests are removed, stall idle, normal op., stall, exception one of the uncovered states or transitions is chosen as a exception idle target for directed test generation. Each state (binary index Table 3: Transition rules between ssl,j₊₁ and ssi,j number) has a flag to indicate whether the state is covered or not. The flag is called StateCovered flag and is initialized ssl,j+1(t − 1) ssi,j(t) to 0. Each state also has a list of its neighboring states, i.e., idle idle, normal op., stall, exception a list of its transitions. In the list, each neighboring state normal op. idle, normal op., stall, exception has two flags to indicate whether the state is a next state stall idle, normal op., stall, exception or a previous state and whether the transition to/from the exception idle neighboring state is covered or not. The second flag is called TransitionCovered flag and is initialized to 0. Sub-state transition rules between units are shown above Beginning from a target state, we search for an FSM path assuming four functional activities at each unit and one reg- that can cover maximum number of states and transitions. ister between consecutive pipeline stages. For example, in For backward path, one of the previous neighboring states Table 1, if ssk,j−1(t − 1) = stall, then ssi,j(t) can be either is selected that has TransitionCovered =0. A pair of state in idle or stall state because no instruction moves from the and transition is covered by setting value 1 for StateCovered previous stage. In Table 2 and Table 3, if ssk,j−1(t − 1) or of the current state and TransitionCovered of the previous ssl,j₊₁(t − 1) = exception, then ssi,j(t) should be in idle state. This process continues until the path traversal reaches state to flush the following instructions in the pipeline. an initial state. If all of the previous states in the neighbor 4.3 Identifying Redundancy list are covered (TransitionCovered =1) at the current state, we check the neighbor list of the previous states to deter- We define redundant states and transitions in terms of mine whether the path includes any uncovered state and coverage-driven test generation. A state (transition) is re- transition. We extend the search space until an uncovered dundant if the test generated for activating any other states state/transition is encountered, or until the number of back- or transitions has to go through this state (transition). This ward transitions reaches its upper bound (maximum number

of clock cycles in which an instruction can stay in the pro- PC IF Memory cessor pipeline). Similarly, we complete the path by tracing forward to a final state from the target point. We continue RegFile ID path generation until all states and transitions in the FSM are covered, i.e., all of the StateCovered and TransitionCov- ered flags are set to 1. IALU MUL1 FADD1 DIV 5.2 Directed Test Generation MUL2 FADD2 We use model checking for directed test generation be- cause of its capability of automatically producing a coun- FADD3 terexample. Figure 5 shows a test generation framework using model checking [10, 11]. In this scenario, a desired be- havior is expressed in the form of temporal logic property. MUL7 FADD4 A model checker exhaustively searches all reachable states of the processor model to check if the property holds (ver- MEM ification) or not (falsification). If the model checker finds Data−transfer edge any reachable state that does not satisfy the property, it WB Pipeline edge Functional unit produces a counterexample. This falsification can be quite Storage effectively exploited for test generation. Instead of a desired Figure 6: A MIPS architecture property, its negated version is applied to model checking. A model checker produces a counterexample and correspond- (where x is a don’t-care bit) represents the single issue con- ing input requirements. The input requirements of the pro- straint that two execution units IALU and MUL1 cannot cessor model contains a sequence of instructions from an be in normal operation at the same clock cycle. The corre- initial state to the point where the negated version of the sponding number of states is 12.7 × 10⁶. We can eliminate property fails. those states in the FSM model since the states with this pattern are not allowed due to single-issue constraint. Af- Processor Model ter removing all unreachable states, the number of states is Model Checker Counterexample reduced to 87.2 × 10⁶ (43% reduction). Negated Property (Test) WB MEM … IALU ID IF Figure 5: Test generation using model checking 32 31 30 5 4 3 2 1 0 0: idle 00: idle 00: idle 00: idle 00: idle For example, a path selected in the previous section is de- 1: oper 01: oper 01: oper 01: oper 01: oper scribed in the form of a temporal logic property EF p (i.e., 01: stall 10: stall 10: stall 10: stall there exists a path p in the processor model ) where p con- 11: exception sists of the states at every time step on the path. Its negated Figure 7: 33-bit FSM state model property AG¬p (i.e., there is no such path p) is applied to the model checker. The model checker generates a coun- Table 4 presents the results of our test compaction for the terexample path with an input instruction sequence. Since MIPS processor. The first column indicates various com- this counterexample path is the same as the selected path, paction steps. The second and third column present com- the instruction sequence can be used as a test program to paction results for states and transitions respectively. For exercise the selected path. example, the value 87.2×10⁶ (in second row, second column) indicates the total number of reachable states after perform- 6. EXPERIMENTS ing reachability analysis (on original 153 × 10⁶ states). For FSM state compaction, we searched for incoming and outgo- We applied our test compaction methodology on a single- ing single transitions that have inevitable neighboring states. issue MIPS architecture [7] and a superscalar (dual-issue) We do not need to generate a test for those states since the e500 processor [19]. Figure 6 shows the MIPS architecture. test programs to exercise their neighbors will cover them. There are 17 functional units. We consider four functional states (activities) of each unit: ‘00’ for idle, ‘01’ for nor- Table 4: Test compaction results for MIPS processor mal operation, ‘10’ for stall, and ‘11’ for exception. Figure 7 Compaction of Compaction of shows the functional FSM model of the processor in the form of 33-bit binary. We assume that WB has only two states FSM States Transitions (idle and normal operation), and IALU and DIV have the Reachable 87.2 × 106 693.1 × 106 exception state for overflow and divide-by-zero, respectively. States/Transitions All other functional units have three states (idle, normal op- Legal and Required 83.5 × 106 376.3 × 106 States/Transitions eration, and stall). In the figure, the term “oper” represents Selected Tests 16.9 × 106 “normal operation”. Therefore, theoretically possible num- (States/Transitions) ber of states is 2 × 4 × 4 × 3¹⁴ ≃ 153 × 10⁶. Overall Reduction 97.8% Unreachable states are removed by using the constraints of processor behavior such as single issue requirement. For After state compaction, we could reduce the number of example, the unreachable binary pattern ‘xxxx...0101xxxx’ tests by 3.7×10⁶ (4% reduction). As a result, the number of

directed test programs before test selection is 83.5×10⁶. The overall validation effort since directed tests require a smaller FSM transition coverage needs to activate 376.3×10⁶ transi- test set compared to random tests to achieve the same func- tions. Our framework of selecting tests (minimum number of tional coverage goal. However, the number of directed tests states/transitions required to achieve 100% state and transi- can be still extremely large – in the order of millions. tion coverage) produced 16.9×10⁶ test programs. Therefore, This paper presented a functional test compaction tech- our approach generates 97.8%¹ overall reduction of directed nique that can significantly reduce the number of directed tests without sacrificing the functional coverage goal. tests without sacrificing the functional coverage. This pa- per made three important contributions. First, it developed I-cache 7 pipeline stages an efficient FSM model of pipelined processors and defined Fetch stage 1 Superscalar FSM state and transition coverage based on pipeline inter- IQ Fetch stage 2 Dynamic scheduling actions. Second, we developed an FSM compaction tech- GIQ Decode stage Rename nique to eliminate redundant states/transitions that can be Buffers covered by the remaining states/transitions with respect to Issue stage test generation. Finally, we developed efficient techniques for fault selection and test generation to reduce overall val- RS RS RS RS idation effort. Our experimental results using MIPS and Execute stage e500 processors demonstrated more than 90% reduction in LSU stage 1 MU stage 1 SU1 SU2 functional tests without sacrificing the coverage goal. LSU stage 2 MU stage 2 Divide 8. REFERENCES LSU stage 3 MU stage 3 Post-divide MU stage 4 [1] A. Adir et al. Genesys-pro: Innovations in test program D-cache generation for functional processor verification. Design & Test, 21(2):84–93, 2004. Completion stage Completion [2] D. Campenhout et al. High-level test generation for design Write-back stage Queue verification of pipelined microprocessors. DAC, 1999. [3] K.-T. Cheng et al. Automatic generation of functional Figure 8: Instruction pipeline flow of e500 processor vectors using the extended finite state machine model. ACM TODAES, 1(1):57–79, 1996. We also applied our test generation methodology on a sim- [4] M. Dimopoulos and P. Linardis. Efficient static compaction of test sequence sets through the application of set covering plified version of the dual-issue e500 processor based on the techniques. DATE, 194–199, 2004. Power ArchitectureT M Technology² [19]. Figure 8 shows the [5] A. El-Maleh and Y. Osais. Test vector decomposition-based dual-issue e500 architecture. It has seven pipeline stages and static compaction algorithms for combinational circuits. 15 functional units. We used the 29-bit FSM model for the ACM TODAES, 8(4):430–459, 2003. e500 processor with the same assumption as the MIPS pro- [6] P. Flores et al. On applying set covering models to test set cessor. Theoretically possible number of states is 22.7 × 10⁶ . compaction. GLSVLSI, 8–11, 1999. In our experiment, the e500 processor has less number of [7] J. Hennessy and D. Patterson. Computer Architecture: A states compared to the MIPS processor because we mod- Quantitative Approach. Morgan Kaufmann, 2002. eled 15 functional units by assuming only single instruction [8] R. Ho et al. Architecture validation for processors. ISCA, 404–413, 1995. buffer between neighboring pipeline stages. Table 5 presents [9] D. Hochbaum. An optimal test compression procedure for the results of test compaction for e500 architecture. Our ap- combinational circuits. TCAD, 15(10):1294–1299, 1996. proach generates 92.6% overall reduction in directed tests. [10] H.-M. Koo and P. Mishra. Functional test generation using property decompositions for validation of pipelined Table 5: Test compaction results for e500 processor processors. DATE, 1240–1245, 2006. [11] P. Mishra and N. Dutt. Specification-driven directed test Compaction of Compaction of generation for validation of pipelined processors. ACM FSM States Transitions TODAES, 13(2), article 42, 36 pages, 2008. Reachable 14.6 × 106 135.7 × 106 [12] P. Mishra and N. Dutt, Editors. Processor Description States/Transitions Languages. Morgan Kaufmann, 2008. Legal and Required 14.2 × 106 134.6 × 106 [13] D. Moundanos et al. Abstraction techniques for validation States/Transitions coverage analysis and test generation. Computers, Selected Tests 11.1 × 106 47(1):2–14, 1998. (States/Transitions) [14] E. Rudnick et al. Efficient techniques for dynamic test Overall Reduction 92.6% sequence compaction. Computers, 48(3), 1999. [15] J. Shen and J. A. Abraham. An RTL abstraction technique for processor microarchitecture validation and test 7. CONCLUSIONS generation. JETTA, 16(1-2):67–81, 2000. [16] K. Shimizu et al. Verification of the cell broadband engine Functional verification is a major bottleneck in pipelined processor. DAC, 338–343, 2006. processor design methodology. Simulation is widely used for [17] N. Utamaphethai et al. Effectiveness of microarchitecture processor validation using billions of random and constrained- test program generation. Design & Test, 17(4):38–49, 2000. random tests. The directed tests can significantly reduce [18] T. Villa et al. Explicit and implicit algorithms for binate covering problems. IEEE TCAD, 16(7):677–691, 1997. 1(87.2 + 376.3 − 16.9)/(87.2 + 376.3) = 97.8% [19] Freescale PowerPc e500 core family reference manual. 2The Power Architecture and Power.org wordmarks and the http://www.phxmicro.com/Online/E500CORERM.pdf. Power and Power.org logos and related marks are trade- [20] Y. Zhang et al. Using model-based test program generator marks and service marks licensed by Power.org for simulation validation. ESS, (3605):549–556, 2005.