An Approach to Test Programs Generation for Microprocessors Based on Pipeline Hazards Templates

             Alexander Kamkin, Dmitry Vorobyev

Institute for System Programming of the Russian Academy of Sciences 25, A.Solzhenitsyn Street, Moscow, 109004, Russia E-Mail: {kamkin, vorobyev}@ispras.ru

Abstract  — In     this        paper   we   describe     an     approach  to        The rest of the paper is organized as follows. Section II is
automated  test    programs                generation     intended       for   a survey of the related work. Section III introduces the main
microprocessor verification. The approach is based on formal                   concepts of the suggested approach. The description of the
specification of microprocessor ISA and description of pipeline                approach is given in Section IV. Section V considers a case
hazards templates. The use of formal specifications allows                     study. Finally, Section VI concludes the paper.
automating         development  of          test   program    generators and
systematizing control logic verification. Since the approach is                                     II.         RELATED WORK
underlain  by     high-level           descriptions,  all specifications and
templates developed, as well as the constructed test programs,                 In the paper [1] two mutually complementary techniques are
can be easily reused when the processor’s microarchitecture                    described. The first one is a test generation technique basing
changes. It makes it possible to apply the methodology in early                on model checking, while the second one uses            template-
stages of a microprocessor development cycle when the design                   based   procedures.     Source    information    for    the  both
is frequently modified.¹                                                       approaches   is  a  microprocessor     specification   written in
                                                                               EXPRESSION [2]. Basing on the specification, a generic
                       I.       INTRODUCTION                                   structure-behavior   model    in  SMV     [3]    is automatically
Functioning of          a      modern  pipelined          microprocessor  is   derived. For this model, a test developer defines a         fault
implemented     in a            very   difficult      way.   Pipeline    can   model. For each element of the fault model the negation of
concurrently         process   multiple     instructions,     which,      in   the corresponding property is produced. Then, a counter-
addition, can interact each other via shared resources. At                     example is generated using the SMV model checker. As the
every cycle of execution a microprocessor makes lots of                        authors say, model checking does not scale on complex
decisions  on        hazards            resolution,   branches   processing,   designs. So, the technique employing templates is used as an
exceptions    handling,        and     so on.          The    microprocessor   addition.
mechanisms     responsible             for      controlling     instructions      Templates    are   developed       by  hands    and   describe
execution are called control logic.                                            sequences of instructions that create special situations in
                       Control logic is a key component of a microprocessor;   microprocessor behavior (in the first place, pipeline hazards).
that is why it should be designed and verified thoroughly, not                 Generation is performed with the help of the graph model
missing any detail. However, the common practice is to                         extracted   from    the   specification.  The      template-based
produce    tests   manually        or    using        random      generation   technique requires greater efforts, but it scales well. It should
techniques, which is obviously inefficient and unsystematic.                   be noticed that both approaches are based on rather accurate
The other kinds of methods are based on                       cycle-accurate   specifications, and it is better to apply them in late design
models. Such approaches are aimed at detailed verification of                  stages, when the microarchitecture is stable. Otherwise, there
control logic, but the problem is that accurate models are                     would be a need to modify the specification to keep up its
very hard to develop and maintain.                                             consistency.
                        The approach suggested in this work is thought to be   In    the    approach     [4], pipeline   structure is   formally
somewhere     between     random                generation    techniques and   specified in the form of state machine, which is called OSM
techniques based on cycle-accurate models. The approach                        (Operation State Machine). OSM describes control logic at
uses formal specification (modeling) of a microprocessor                       two levels, called        operational and hardware levels. At the
instruction set (ISA, Instruction Set Architecture). Of course,                first level, “movement” of instructions through the pipeline
instruction-level models are less informative in comparison                    stages is   described   (every    operation  is  described  by  a
with cycle-accurate ones, but they have a number of practical                  separate   state machine).    At  the    second level,   hardware
advantages. First, they are much easier to develop, and                        resources are modeled using so-called token managers. An
second, they can be reused even if the microarchitecture is                    operation state machine changes states by capturing and
considerably altered.                                                          moving tokens. A pipeline model is defined as a composition
                                                                               of operation state machines and resource state machines. The
                                                                               goal of testing is to traverse all the transitions of the joint
This work was supported by the RFBR (grant 08-01-00889-а).

automaton. Like the previous techniques, this approach is where Prei is the initializing instructions of the ith test case, based on accurate specifications. Actioni is the test action, and Posti is the test oracle. In The paper [5] considers the test program generation tool elementary case a test program consists of a singular test Genesys-Pro (IBM Research). A generator is composed of case without a test oracle (Test = 〈Pre, Action〉). two main components, an engine (which does not depend on The assembler code below is a test program fragment that target architecture) and a model (which describes contains one test case (we use MIPS ISA [8] to illustrate microprocessor-specific knowledge). A verification engineer ideas of the approach). develops templates, which specify structure of test programs // Initialization of sub[0]: IntegerOverflow=true and properties they should satisfy. Genesys-Pro transforms // s5[rs]=0xffffffffc1c998db, v0[rt]=0x7def4297 each template into a set of constraints and builds a test lui s5, 0xc1c9 program using constraint solving techniques. The tool is ori s5, s5, 0x98db quite universal and applicable to different microprocessor lui v0, 0x7def ori v0, v0, 0x4297 architectures. However, so far as development of test // Initialization of add[1]: Exception=false templates is done by hand, tests maintenance is hard enough. // a0[rs]=0x1d922e27, a1[rt]=0x32bd66d5 In the paper [6] a technique for test generation basing on ... FSM traversal is described. In one of the stages the technique // Initialization of div[2]: DivisionByZero=true // a2[rs]=0x48f, a1[rt]=0x0 uses Genesys (the previous version of Genesys-Pro). A test ... developer creates a microprocessor model using the SMV // Dependencies: div[2].rt[1]-sub[0].rd[0] language. After this, a set of paths covering all the edges of // Test action: 2010 the state graph extracted from the model is built. Each path sub a1, s5, v0 // IntegerOverflow=true (so-called abstract test) is translated into a Genesys template. add t7, a0, s3 // Exception=false The technique allows achieving good coverage of control div a2, a1 // DivisionByZero=true logic, but it has two principal shortcomings. First, one needs In this fragment, Action is represented as a sequence of a skilled expert to develop a microprocessor model. Second, three instructions: sub, add and div. There is a register to be able to map abstract tests into Genesys templates, a dependency between the rt operand of the div instruction complex description has to be done. Summing up, all the techniques reviewed can be divided and the rd operand of the sub instruction. This dependency into two classes: techniques based on accurate implies using the same register for each of the operands. models [1,4,6] and techniques based on templates [5]. The Initializing instructions Pre load values into the independent techniques of the first class allow achieving high quality of input registers of all instructions of the test action (see verification. However, it is not practical to use them in early preparation of the instruction sub, for example). Post is design stages. Template-based techniques do not have this empty here. shortcoming, but they are unsystematic and cannot guarantee B. Test Templates high quality of verification. Test template is an abstract representation of a test action III. FOUNDATIONS OF THE SUGGESTED APPROACH where constraints (test situations and dependencies) are The suggested approach is based on combinatorial model- specified instead of concrete instructions and their operands’ based generation [7]. It uses formal specifications of values. Generally speaking, each template defines a testing microprocessor ISA, which describe instructions regardless purpose (situation that should be tested). The goal of test of their processing on a pipeline. Description of each program generation is to construct a representative set of test instruction includes a mnemonic, list of operands, templates. One of the possible templates for the example precondition, latency, and semantics in the imperative form. above is shown below. Besides instructions, test situations and dependencies IADDInstruction R, ?, ? @ IntegerOverflow=true between instructions are formally described. Test programs IADDInstruction ?, ?, ? @ Exception=false are generated automatically by combining test situations and IDIVInstruction ?, R @ DivisionByZero=true dependencies for finite sequences of instructions. twoThe template is composed of three instructions. The first instructions belong to the equivalence class A. Structure of a Test Program IADDInstruction, while the third one belongs to Test program is a sequence of test cases. The key part of a IDIVInstruction. For the first instruction the situation test case is a test action, which is a specially prepared IntegerOverflow=true is given (instruction should sequence of instructions intended to create a certain situation throw the integer overflow exception). The situation of the in microprocessor behavior (hazard, exception, and so on). A second instruction is Exception=false (absence of test action is prepared by initializing instructions and exceptions). The third instruction should raise division by followed by a test oracle (sequence of instructions that zero (DivisionByZero=true). In addition, there is a checks correctness of a microprocessor state after execution dependency between the first and the third instructions (the of the test action). Thus structure of a test program can be first register of the first instruction is equal to the second described by the expression: register of the third instruction). Independent operands of the Test = {〈Prei, Actioni, Posti〉}i=0,n-1, instructions, i.e., operands that are not revolved by the dependency are denoted as ?.

Test templates are allowed to be             parameterized. The                            IV.             THE SUGGESTED APPROACH

example below demonstrates a template with four Basing on documentation analysis, a verification engineer parameters: $FirstInstruction (equivalence class of marks out situations “interesting” from the control logic the first instruction), $Situation (test situation of the first point of view (different types of pipeline hazards). For each instruction), $ThirdInstruction (equivalence class of hazard type its generalized specification is developed, which the third instruction), and $Dependency (dependency of is a parameterized template creating the corresponding the third instruction on the first and the second instructions). hazard situation. Such templates are also called pipeline $FirstInstruction @ $Situation hazards templates or basic templates. Basic templates are IADDInstruction @ IntegerOverflow=false usually of a small size, because hazards between instructions $ThirdInstruction @ $Dependency occur if instructions are close to each other. To be able to C. Test Situations generate tests, one should define iterators of templates’ Speaking about control logic verification, test situations parameters. After this, a generator constructs test programs related to execution of instructions on a pipeline are of using different values of the parameters and combining interest. As a rule, processing of an instruction is performed templates together. in the same way for all values of the operands (of course, if A. Specification of Hazards exceptions are not taken into account). Thereby, for an Let us examine a general scheme of pipeline hazards instruction that can raise N exceptions, N+1 test situations specification. All of the situations derived from the are usually defined: Exception=false, Exception₀=true, …, documentation are classified by their types (see Fig. 1). The ExceptionN₋₁=true. For an instruction which handling four main types are exceptions, data hazards, structural depends on the operands values one should specify all hazards, and control hazards. possible paths of its execution. Branch instructions are examined in a particular way. A Pipeline Hazard Situations test situation of a branch instruction includes a target address and truth values of the condition (if the branch instruction is Exceptions Data Hazards Structural Control Hazards Hazards conditional). In general case, a test situation is as follows: Target=Label, Trace={C0, …, CM-1}, where Label is a target Exception GPR Registers Incorrect label (address) and Ci is a truth value of the branch condition IntegerOverflow Hazards ALU Hazards Prediction for the ith time of the instruction execution. Figure 1. Classification of pipeline hazard situations D. Dependencies between Instructions Generally, all situations of the same type are described Dependencies between instructions are thought to have a key by one basic template. The difference between two single- role in creation of pipeline hazards. There are two main types type specifications is connected with various constraints for of dependencies: register dependencies and address template parameters – parameters domain is divided by a dependencies (data dependencies). Register dependencies verification engineer into a number of equivalence classes, are expressed as equality of registers being used as operands and this serves as a basis for the further construction of of two instructions. Such dependencies can be of the iterators (see Fig. 2). following types: • read-read — both instructions read from the same Specification of a Hazard Situation register; Constraints for Parameter $P1 • read-write — the first instruction reads from a Pipeline Hazard … Template register, while the second one writes into it; Constraints for Parameter $PK • write-read — the first instruction writes into a register, while the second one reads from it; • write-write — both instructions write into the same Figure 2. Specification of a hazard situation register. 1) Specification of Exceptions Address dependencies have more complex structure and Exception is a special event that signals that something goes are related to internal organization of memory management wrong during instruction execution. When an exception is units [9]. Some examples of the address dependencies are raised, control flow is switched to a special routine, called itemized below. exception handler, and all the instructions loaded after the • VAEqual — equality of virtual addresses; instruction throwing the exception are flushed. The typical • TLBEqual — equality of TLB entries; errors related to exception handling are incorrect setting of • PAEqual — equality of physical addresses; an exception signal (incorrect calculation of an exception • CacheRowEqual — equality of cache rows. condition) and incorrect flushing of loaded instructions. There are two main strategies for exception handling in test programs. First, if an exception is raised, execution is switched to the next instruction of the test action. Second, execution is switched to the test oracle passing the rest

                   instructions of the test action. To check pipeline flushing       3)                         Specification of Structural Hazards
                    mechanisms, the second strategy is preferable. Generalized

specification of an exception is given by the template below. Structural hazards occur when several instructions try to $PreInstructions access the same unit of a microprocessor (or some other $ExceptionInstruction @ $ExceptionType resource). Usually, such kinds of hazards happen when two $PostInstructions similar multi-cycle instructions are located closely to each The template uses the following parameters: other. In some cases an additional data dependency is required to create a structural hazard between instructions. • $PreInstructions — a sequence of instructions that precedes The typical error related to structural hazard resolution is the • an exception (pre-instructions should not raise exceptions); same as for data hazards (incorrect implementation of $ExceptionInstruction — an instruction that raises an pipeline interlocks). Generalized specification of a structural • exception; hazard is absolutely the same. A concrete example is given • $ExceptionType — an exception type; below. $PostInstructions — a sequence of instructions that succeeds an exception (post-instructions should be flushed). div.s $f11, $f27, $f3 Here is an example of a concrete test action that add.s $f28, $f7, $f30 div.d $f23, $f1, $f20 // Structural hazard corresponds to the template given. add.d $f18, $f2, $f25 dadd r25, r30, r7 4) Specification of Control Hazards lb r22, 0(r4) // TLBInvalid=true daddiu r5, r18, 13457 Control hazards are related to branch instructions. The sequence $PreInstructions consists of the Depending on microprocessor organization, execution of a only instruction dadd. $ExceptionInstruction is branch instruction can result in pipeline stalling or flushing. instantiated by the instruction lb that raises the exception Errors of control hazard resolution relate to pipeline TLBInvalid ($ExceptionType). The sequence interlocks, branch prediction and other control logic $PostInstructions includes the only instruction mechanisms. Generalized specification of a control is given addiu. by the template below. $PreInstructions $BranchInstruction @ $Target, $Trace 2) Specification of Data Hazards $DelaySlots $PostInstructions Data hazards are situations in which different instructions The template uses the following parameters: try to access the same data and at least one instruction tries to write them. Thereby, to describe data hazards, one should • $PreInstructions — a sequence of instructions that precedes use “read-write”, “write-read”, and “write-write” types of a branch instruction; dependencies. The typical error related to data hazard • $BranchInstruction — a branch instruction; resolution is incorrect implementation of pipeline interlocks • $Target — a target address of a branch instruction; resulting in data flow integrity violation. Generalized • $Trace — an execution trace of a branch execution (sequence of specification of a data hazard is given by the template below. • truth values of a branch condition); $DelaySlots — instructions in delay slots; $PreInstructions • $PostInstructions — a sequence of instructions that $FirstInstruction succeeds a branch instruction. $InnerInstructions $SecondInstruction @ $Dependency Here is an example of a concrete test action that $PostInstructions corresponds to the template given. The template uses the following parameters: L:addi r1, r1, 1 beq r1, r0, L // Target=L, Trace={1, 0} • $PreInstructions — a sequence of instructions that precedes a dadd r7, r12, r23 dependency (pre-instructions should not raise exceptions); • $FirstInstruction and $SecondInstruction — a pair of B. Test Programs Generation • dependent instructions that causes a data hazard; Let us consider how test programs are generated on the base $Dependency — a dependency between instructions that causes a data hazard; of test templates. Test actions are divided into two types: • $InnerInstructions — a sequence of instructions between simple test actions (which correspond to a single basic dependent instructions (inner-instructions should not raise exceptions template) and composite test actions (which are constructed • and produce hazards); by composition of several basic templates). $PostInstructions — a sequence of instructions that succeeds a data hazard (post-instructions are usually suspended with the 1) Constructing Simple Test Actions dependent instruction). Simple test actions are targeted at creation of one hazard Here is an example of a concrete test action that situation. A technique for their construction is easy and corresponds to the template given. based on using basic templates and iterators. For each madd.s $f18, $f6, $f28, $f10 situation derived from documentation, a set of test actions is add.s $f8, $f17, $f3 built. Test actions are constructed by iterating parameters ceil.l.s $f2, $f18 // Data hazard div.s $f23, $f13, $f24

values and combining them to each other (commonly, all hazard, and, finally, TC be a control hazard template. The possible combinations are used) (see Fig. 3). main composition operations are given below. Generation of Simple Test Actions a) Overlapping: T=TH₁|TH₂

                                  Iterator for Parameter $P1                  TH.PreInstructions = TH .PreInstructions ≡ TH₂.PreInstructions
        Pipeline Hazard                           …                                                   1
             Template                                                         TH.FirstInstruction = TH1.FirstInstruction ≡ TH2.FirstInstruction
                                  Iterator for Parameter $PK                  TH.SecondInstruction = TH₁.SecondInstruction ≡ TH₂.SecondInstruction
                                                                              TH.Dependency = TH₁.Dependency & TH₂.Dependency
                                                                              TH.InnerInstructions = TH1.InnerInstructions ≡ TH2.InnerInstructions
                                                                              TH.PostInstructions = TH₁.PostInstructions ≡ TH₂.PostInstructions

Figure 3. Generation of simple test actions for a pipeline hazard b) Shift: TH=TH₁↓TH₂ Let us examine simple test action construction for a TH.PreInstructions = TH1.PreInstructions structural hazard on FPU (Floating Point Unit) being TH.FirstInstruction = TH1.FirstInstruction described by the following basic template: TH.SecondInstruction = TH₁.SecondInstruction TH.Dependency = TH₁.Dependency & TH₂.Dependency $PreInstructions TH.InnerInstructions = {TH₁.InnerInstructions, TH₂.FirstInstruction, TH₂.InnerInstructions} $FirstInstruction TH.PostInstructions = {TH1.PostInstructions, TH2.SecondInstruction, TH2.PostInstructions} $InnerInstructions TH .PostInstructions ≡ TH₂.PreInstructions 1 $SecondInstruction @ $Dependency $PostInstructions c) Concatenation: T=T₁→T₂ Some constraints on parameters values are defined for T.PreInstructions = T₁.PreInstructions this hazard. For example, the hazard occurs only between T.MainParameters = T₁.MainParameters² instructions being executed more than one cycle. It is also T.PostInstructions = T₂ obvious that size of $InnerInstructions should not Тype of a template T matches with the type of a template T1 exceed latency of $FirstInstruction subtracted by d) Nesting: TH=TH₁[T] two. In addition, equivalence classes of dependent TH.FirstInstruction = TH .FirstInstruction 1 instructions can be given. Assume that the template’s TH.SecondInstruction = TH₁.SecondInstruction parameters are setup with the following values. TH.Dependency = TH₁.Dependency TH.PreInstructions = TH .PreInstructions 1 FMULInstruction : {mul.s, mul.d} TH.InnerInstructions = T FDIVInstruction : {div.s, div.d} TH.PostInstructions = TH₁.PostInstructions IADDInstruction : {add, sub} $PreInstructions : {} To clearify the semantics of composite templates, let us $FirstInstruction : FMULInstruction, FDIVInstruction consider an example where the overlapping is used to $SecondInstruction : FMULInstruction, FDIVInstruction compose a data hazard and a structural hazard: $Dependency : class($FirstInstruction) == class($SecondInstruction) $PreInstructions1,2 → add.s $f28, $f7, $f30 $InnerInstruction : {IADDInstruction} $PostInstructions : {} $FirstInstruction1,2 → div.s $f11, $f27, $f3 $InnerInstructions1,2 → dsub r25, r30, r7 Given the parameters values, two test actions are $SecondInstruction1,2 generated: @ $Dependency1 & $Dependency2 → div.d $f23, $f11, $f20 $PostInstruction1,2 → lb r22, 0(r4) $PreInstructions → It is intuitively obvious how to iterate test actions for a $FirstInstruction → mul.d $f12, $f3, $f21 $InnerInstructions → sub r6, r15, r3 given composite test template. Some parameters of different $SecondInstruction → mul.s $f9, $f23, $f7 basic test templates are identified. After this, iterators are $PostInstructions → specified for resultant parameters (commonly, iterators $PreInstructions → developed for simple templates are used). Generation of $FirstInstruction → div.s $f18, $f28, $f4 composite test templates is perform by enumeration of $InnerInstructions → add r25, r13, r27 different syntactical structures consisting of a small number $SecondInstruction → div.s $f5, $f12, $f10 of basic templates connection by composition operations. $PostInstructions → 2) Constructing Composite Test Actions V. CASE STUDY The aim of composite test actions as opposed to simple test The suggested approach was applied to verification of actions is creation of several “simultaneous” pipeline control logic of two arithmetical coprocessors, floating point hazards. Composite actions allow testing complex situations coprocessor (CP1) and complex arithmetic coprocessor in microprocessor behavior (parallel hazards, nested (CP2). Coprocessors have common control flow with CPU hazards, parallel exceptions, and so on). Construction of and use three execution channels (functional pipelines): composite actions is performed by composition of several basic templates. • channel of floating point arithmetic; Let T be a template of an arbitrary type, TE be a template 2 MainParameters is set of template parameters excluding PreInstructions of an exception, TH be a template of a data or structural and PostInstructions.

              •    channel of RAM operations;
              •    channel of on-chip memory operations.
                               The control logic supports solving of different types of                                 REFERENCES

hazards. In both coprocessors memory exceptions can occur. [1] P. Mishra, N. Dutt. Specification-Driven Directed Test Generation for In addition, in CP1 arithmetic exceptions can be raised. The CPU implements static branch prediction and speculative Validation of Pipelined Processors. ACM Transactions on Design Automation of Electronic Systems, 2008. execution mechanisms. [2] P. Grun, A. Halambi, A. Khare, V. Ganesh, N. Dutt, A. Nicolau. The test actions were composed of four instructions of EXPRESSION: An ADL for System Level Design Exploration. different types. Structure of the test situations and Technical Report 1998-29, University of California, Irvine, 1998. dependencies was very much the same as it is described in [3] www.cs.cmu.edu/~modelcheck/smv.html. the paper, but some particular features of the [4] T.N. Dang, A. Roychoudhury, T. Mitra, P. Mishra. Generating Test microarchitecture were taken into account and additional Programs to Cover Pipeline Interactions. Design Automation data dependencies were included. [5] Conference, 2009. A. Adir, E. Almog, L. Fournier, E. Marcus, M. Rimon, M. Vinov, TABLE I. CASE STUDY INFORMATION A. Ziv. Genesys-Pro: Innovations in Test Program Generation for Functional Processor Verification. Design and Test of Computers, CPU Code volume Number of Affected Affected code 2004. revision (LOC) instructions instructions (LOC) [6] S. Ur, Y. Yadin. Micro-Architecture Coverage Directed Generation Coprocessor CP18 28500 113 — — [7] of Test Programs. Design Automation Conference, 1999. 20 28650 114 94 485 (1.7%) A. Kamkin. Test Program Generation for Microprocessors. Institute Coprocessor CP2 for System Programming of RAS, 2008. (in Russian) 8 4950 15 — — [8] MIPS64ᵀᴹ Architecture For Programmers. Revision 2.0. MIPS 20 11550 59 5 45 (0.9%) Technologies Inc., 2003. 29 14350 100 18 165 (1.4%) [9] D. Vorobyev, A. Kamkin. Test Program Generation for Memory Management Units of Microprocessors. Institute for System Table I shows code volume (including ISA specifications Programming of RAS, 2009. (in Russian) and pipeline hazards templates), number of implemented instructions, number of instructions affected by the revision and volume of the affected code. As it is seen in the table, when the microprocessor is modified, a small part of the generated code has to be changed. It took us less than half an hour to alter the code. The generated test programs detected a considerable number of errors in both coprocessors which had not been found by randomly generated test programs.

                                VI.         CONCLUSION

Verification of a pipeline microprocessor is a very difficult task that cannot be carried out without using automation techniques. In the paper the technique for automated test programs generation is described. As opposed to the common approaches, like manual development and random generation, the suggested methodology has a high level of automation and allows systematically testing control logic of a microprocessor. At the same time, the methodology differs from the approaches that use accurate models by the possibility of using it in early design stages when microarchitecture is frequently revised. Using accurate models of control logic is reasonable in late stages of a microprocessor design cycle when control logic is stable. Due to the high informativeness of accurate models, such approaches allow finding errors which are really hard to detect. Moreover, accurate models make it possible to create more compact set of tests. In the future we are planning to extend the approach to support accurate models as well. This would make the generator to be more flexible – it would be applicable to both early and late design stages unifying the verification process.