Input and Output Generation for the Verification of ALU: a Use Case


       Ondrej Cekan, Richard Panek, Zdenek Kotasek

Brno University of Technology, Faculty of Information Technology, Centre of Excellence IT4Innovations Bozetechova 2, 612 66 Brno, Czech Republic Tel.: +420 54114-{1361, 1362, 1223} {icekan, ipanek, kotasek}@fit.vutbr.cz

                              Abstract                           devices. Also, these tools do not allow the expected
                                                                 output to be generated, and further efforts must be
The      paper     presents     the approach  to     universal   made to create a reference system [2].
stimuli generation for an arithmetic-logic unit (ALU).                       For the reasons outlined above, we have focused
It is not focused only on input data generation, but it is       on developing a framework for universal stimuli
possible to   generate  also     expected output     in    one   generation that can be used for various circuits.
stimulus. The process of generation is based on a                        The paper is organized as follows. In section 2 our
probabilistic constrained grammar which is designed              previous research is described. In section 3 the related
to universally describe stimuli for various circuits. This       work is   summarized.       Section   4  deals    with  our
grammar    is     processed   by     our   framework.      The   definition of probabilistic constrained grammar that we
experiment in functional verification, which shows the           use for the generation process while section 5 devotes
quality of generated stimuli, is also presented.                 to the grammar definition for the arithmetic-logic unit.
                                                                 Experimental results are mentioned in section 6 and
                                                                 finally in section 7 the paper is concluded.
1. Introduction                                                  2. Previous Research
    Random    stimuli   generation   is  currently  a     very
important process of checking the correct behavior of              In  our     previous   research,    we   designed     and
various circuits [1]. Complex or also simple circuits            developed a framework for universal stimuli generation
must  be      properly  tested   or  verified   before    real   based on     a probabilistic  (stochastic)     context-free
deployment    to   exclude    design    or      implementation   grammar [3]. It is a common context-free grammar that
errors. It is also necessary to verify the correct output        defines probabilities for its production rules with which
for  expected      and  unexpected    input       combinations   they are applied. We have extended this grammar by
(stimuli). Stimuli are typically randomly constructed            restrictive conditions (constraints) and defined the new
and may take many forms from binary values on simple             grammar system - Probabilistic Constrained Grammar
circuit pins to a complex program in the data memory             (PCG) [4] that we use in our research. Constraints are
of a processor.                                                  used to   dynamically    change     the  probabilities   of
             Each system is unique, and therefore, it requires   production rules during the generation.
specific input stimuli for its operation. In order to                     We have also defined the architecture of universal
verify the correct behavior, it is necessary to create a         stimuli generation [5] that is shown in Fig. 1. This
set of test cases (input stimuli and expected outputs) to        architecture   consists   of     two     input   structures
detect   any   possible     mismatches    in    the   circuit.   (Production Rules, Constraints) which are based on
Depending     on the    complexity   of  the    circuit,  this   PCG. The first structure defines the production rules of
activity may be quite challenging, and therefore, tools          a grammar,    while     the   second   structure   includes
that allow to generate random inputs automatically are           constraints for the application      of  production  rules.
created. These tools are targeted to a specific circuit          Together   these two     structures   form   the  resultant
and their  use     is  considerably  limited  for    different   grammar. Grammar defined in this way is processed by





IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018                                                        331

the Generator Core of the framework that assembles 4. Probabilistic Constrained Grammar the resultant stimulus on its output. We applied this framework to more complex A probabilistic constrained grammar is a pair G: circuits (e.g., RISC (Reduced Instruction Set Computer) [6] processors, control unit) to verify the G = (H,C); where: possibility of generating stimuli using PCG. We H is a probabilistic context-free grammar. verified the quality of obtained stimuli from the point C is an ordered list of constraints for the grammar H. of view of the generation speed and the achieved coverage [7] in functional verification. A probabilistic context-free grammar is a 5-tuple H: H = (N,T,R,S,P); where: Probabilistic Constrained Grammar N is a finite set of non-terminal symbols. T is a finite set of terminal symbols, N∩T = 0. Production Rules Constraints R is a finite set of production rules with form A→α, where AϵN and α ϵ (NυT)*. S is the starting non-terminal. P is a finite set of probabilities for production rules. Constraints restrict the grammar in the application Generator Core of production rules. The constraint is a 5-tuple C: Selection Application Modification C = (RS,RD,P,[RE],[O]); where: RS is the activation rule the application of which sets this constraint. RD is the target rule which probability is modified. Stimulus P is the new probability value. RE (optional) is the stop rule which application cancels Fig. 1: The architecture of universal stimuli generation. this constraint. O (optional) is the count of application of the rule RE before canceling this constraint. The constraints limit the application of production 3. Related Work rules for a given non-terminal through probabilities which can be modified throughout the generation The current trend in stimulus generation focuses process, and therefore, we are able to control the primarily on more complex circuits (e.g. processors), resultant stimulus. because it is not trivial to construct a valid stimulus (working program). Simpler stimuli, including test 5. Arithmetic-Logic Unit vectors, can be generated directly in the simulation environment where verification takes place (e.g. In general, this paper focuses on the principles of Modelsim tool from Mentor Graphics [8]) or an random stimuli generation which can be used for many external tool. simple circuits. It is not just generating input values for A number of specific stimuli generators exists for these circuits, as in our previous work, but we would application-specific processors (ASICs) [9], digital like to show the expressive power of PCG and the signal processors (DSPs) [10], protocol interfaces, field ability to simultaneously generate as input values as programmable gate array (FPGA) converters [11], and output values that will be part of the resultant stimulus. more. These tools and their approaches are complex Thanks to this, it is possible to check quickly the and their use is limited to the particular system. correctness of the output in case of circuit testing or As a universal stimuli generator, MicroGP tool [12] functional verification. can be mentioned which does not only generate stimuli The arithmetic-logic unit (ALU) [13] is our test case but it also finds the most optimal solution of hard for which we show the random generation of input problems. stimuli and their result for the selected operation. An In this paper, we use test stimuli which can be arithmetic logic unit performs arithmetic and bitwise obtained directly from the verification environment operations on integer binary numbers. The symbolic from Modelsim tool for comparison with our approach. representation of ALU is shown in Fig. 2.

332 IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018

                A            B                                 of         As can be seen in the figure, stimulus is composed
                                                                          four lines which are represented by integer binary
                                                               numbers.    The lines    are  generated  sequentially      as
            OP               ALU                               outlined, therefore,      it is important to keep the context
                                                               in  which the rules were applied.   The first line is     the
                           R                                            operation code followed by two operands (the numbers
Fig. 2: The symbolic representation of ALU.                        which are summed up) and the last line is a final result.
                                                                         The bit widths of inputs can be entered arbitrarily
                ALU has typically two input operands A and B           based on used ALU, e.g. for our ALU 1 bit can be long

which are N bits long. Its operation is selected by OP operation, 8 bits long operands, and 8 bits long result. input bits. The R output represents the result of the The constraints are also shown in the figure, operation over the operands. ALU can be variously because they are involved in the selection of production complex, therefore, it can contain more input and rules. Based on the random generation of input output bits (e.g. status and control bits), and its operands, certain constraints are set, and therefore, the supported operations can be also different in various logic is modified – the probabilities of production rules versions. are deterministically set to produce an unambiguous In this paper, we limit only to inputs and outputs as result. shown in the figure. Among the operations under In the definition of production rules, each operand is consideration, we include two arithmetic operations – divided into N non-terminals (N is equal to operand bit addition with carry (ADD) and subtraction (SUB), and width). In our case, the operand A is divided into eight four bitwise operations - AND, OR, XOR and NOT. bit non-terminals A7-A0, where A7 is the most However, the principles that we use for the generation significant bit (MSB) and A0 is the least significant bit are applicable to other operations. (LSB). The same applies for the operand B. The rules are as follows:

5.1.1. Arithmetic operations. In this paper, we show A -> A7 A6 A5 A4 A3 A2 A1 A0 the generating of stimuli for the arithmetic addition B -> B7 B6 B5 B4 B3 B2 B1 B0 with carry operation. We can divide the process of creating production rules into several sections - Input Each bit non-terminal A7-A0 can be zero or one, values, Logic, and Result. Each section includes therefore, it can take one of the following two terminals specific rules that are applied during the generation. (comma represents OR, terminals are in quotes): The most complex section is Logic the production rules of which must ensure the correct procedure for A7 -> '0', '1' calculating the result of this operation. The schematic A6 -> '0', '1' representation of these sections is shown in Fig. 3 … which shows also the parts of resultant stimulus. A0 -> '0', '1' Using these production rules, we have random value Stimulus in the first operand. At the moment, we have not Input values information about a carry bit propagation. The carry bit is determined during the generation of the operand B. OPERATION For these purposes, it is necessary to keep the value of operand A. Therefore, each bit non-terminal B7-B0 can OPERAND A CONSTRAINTS be replaced for non-terminal BiA0 (if Ai were zero), BiA1 (if Ai were one), BiA0C (if Ai were zero and a OPERAND B LOGIC carry bit was set) or BiA1C (if Ai were one and a carry bit was set). These possibilities have to be reflected in production rules:

              RESULT R                                             B7   ->  B7A0,    B7A1,       B7A0C,  B7A1C
                                                                   B7A0,    B7A1,    B7A0C,       B7A1C  ->          '0','1'

Fig. 3: The schematic representation of arithmetic … operation in our framework. B0 -> B0A0, B0A1, B0A0C, B0A1C B0A0, B0A1, B0A0C, B0A1C -> '0','1'

IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 333

                                                                   cons(B0A1->'0',          R0->'1',         100);
 It remains to add production rules that will generate             cons(B0A1->'0',          B1->B1A0C,         0);
the final result:                                                  cons(B0A1->'0',          B1->B1A1C,         0);
                                                                   cons(B0A1->'1',          R0->'0',         100);
 R -> R7     R6     R5 R4  R3 R2       R1   R0                     cons(B0A1->'1',          B1->B1A0,      0);
 R8,         R7, …, R0 -> '0', '1'                                 cons(B0A1->'1',          B1->B1A1,      0);
                                                                   ...
 Now it is known which values the input operands
have and whether the carry bits have been propagated.              In this logic, constraints for rules BiA0C and  BiA1C
These rules without any control would generate random          can be easily completed to obtain the correct result.
non-terminals     and the  result would     not reflect   the      The selection of result bit after applying the rules is

operation addition with carry. Therefore, constraints based on the following Tab. 1 which defines the have to be utilized. The framework performs the right classical addition with carry operation. derivations (substitution of the rightmost non- terminals) for the both operands and result, therefore, Tab. 1: Grammar truth table of addition with carry C. the substitution will start with the bit A0 to A7, then Ai bit Bi bit Ri Ci+1 with B0 to B7, and then R0 to R7. Ai->'0' BiA0->'0' Ri->'0' 0 The B0 does not have a carry bit, therefore, we change the probability to zero for two rules with carry Ai->'0' BiA0->'1' Ri->'1' 0 on the start of generation (S is the default starting non- Ai->'0' BiA0C->'0' Ri->'1' 0 terminal): Ai->'0' BiA0C->'1' Ri->'0' 1 cons(->S, B0->B0A0C, 0); Ai->'1' BiA1->'0' Ri->'1' 0 cons(->S, B0->B0A1C, 0); Ai->'1' BiA1->'1' Ri->'0' 1 The context of the application of the rules for Ai->'1' BiA1C->'0' Ri->'0' 1 operand A have to be stored in operand B, therefore, we keep the context by limiting the selection of rules Ai->'1' BiA1C->'1' Ri->'1' 1 for operand B and its corresponding bit: The final real result can be seen as in the following cons(A0->'0', B0->B0A1, 0); example: cons(A0->'0', B0->B0A1C, 0); cons(A0->'1', B0->B0A0, 0); 0 #OP cons(A0->'1', B0->B0A0C, 0); 01101001 #A ... 10001011 #B cons(A7->'0', B7->B7A1, 0); 11110100 #R cons(A7->'0', B7->B7A1C, 0); This process of creation is useful and usable for cons(A7->'1', B7->B7A0, 0); cons(A7->'1', B7->B7A0C, 0); other arithmetic and bitwise operations. The main condition is to cover all possible cases (creation of After this limitation, we have two rules for each bit corresponding production rules) which are then used or B7-B1 which can be used after the generation of the disabled by means of constraints during generation. operand A. The bit B0 have only one deterministic rule The use of the constraints causes a fact that the defined without the carry bit. After the generation of operand A grammar is more deterministic and the output is valid. and the bit B0, we are able to determine the carry bit (rule) for the following bit B1 and the result for bit R0. 5.1.2. Bitwise operations. The process of creation The same applies for the other bits B2-B6: grammar for the bitwise operations is very similar as in the previous subsection in the case of arithmetic cons(B0A0->'0', R0->'0', 100); operations. The basis is again to maintain the context cons(B0A0->'0', B1->B1A0C, 0); through several production rules and their non- cons(B0A0->'0', B1->B1A1C, 0); terminals. The difference is only in the generation of cons(B0A0->'1', R0->'1', 100); results, respectively the limitation of the rules for cons(B0A0->'1', B1->B1A0C, 0); generating the partial bit of the result so that the output cons(B0A0->'1', B1->B1A1C, 0); is correct for the given operation.

334                                     IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018

6. Experimental Results 7. Conclusions and Future Research

   We performed an experiment in functional The aim of this paper was to show the possibility of

verification in which we examined the highest coverage generating as input as expected output. Automatic of the key functions of the presented ALU. Functional generation of random stimuli facilitates the work and verification is the process of checking the correctness time to test or verify a designed circuit. We showed on of a system based on comparing its inputs and outputs an arithmetic logic unit the generation of input and with reference model which implements the same output together for which we defined our probabilistic specification. We had implemented verification constrained grammar. The output stimulus was environment in which we investigate the valid result of composed of as randomly generated input operands as the ALU and the code coverage. The code coverage the expected result for this unit. The introduced measures the system source code through typical mechanism has been shown on addition with carry metrics like statements, branches, expressions, operation, however, the defined principles are general conditions, and states. Through this information, we are and can be used for other arithmetic or bitwise able to determine, when the ALU is sufficiently operations, cyclic redundancy check generation, and so verified. It is a percentage value suitable for on. The experiment in functional verification showed comparison or different generators. that this principle is ductile to get better results than The result of our experiment can be seen in Fig. 4. other ones. From the experiment, it can be seen that there is a This work is one of the partial goals for checking difference between our generator (USG) and the Build- fault tolerance in Field Programmable Gate Array in generator of test stimuli in verification environment. (FPGA). The main goal is to verify the correctness of The both of the generators work on random stimuli affected system under a fault and to determine the construction but in our approach we are able to drive importance of each of the configuration memory bits in the generation process to direct the convergence to the FPGA. The future research will address this topic. better results. Verification environment checks also corner cases for input data (e.g. all ones or zeros in 8. Acknowledgements operands and result) and through probability values, we are able to increase the ability to generate this This research was supported by The Ministry of combinations. Therefore, the USG can hit this coverage Education, Youth and Sports from the National points faster than only with clean random generation. Programme of Sustainability (NPU II); JU ECSEL The coverage was 94.91% for USG and 91.63% for Project SECREDAS (Product Security for Cross Built-in generator for 100 stimuli. For 200 stimuli, the Domain Reliable Dependable Automated Systems), coverage was balanced for both generators on 94.91%. Grant agreement No. 783119; project IT4Innovations excellence in science - LQ1602 and BUT project FIT- S-17-3994. USG Build-in 100 9. References

CODE COVERAGE [%] 90 [1] A. Meyer. Principles of Functional Verification. Elsevier Science, 2003.

                80                                                         [2] N. Kitchen and A. Kuehlmann. Stimulus generation for
                                                                           constrained   random      simulation.               In  2007    IEEE/ACM
                70                                                         International Conference on Computer-Aided Design, pages
                                                                           258-265, Nov 2007.

                60                                                         [3] R. Giegerich.                Introduction to Stochastic Context Free
                      0                     50                    100      Grammars. Humana Press, Totowa, NJ, 2014.
                                  NUMBER OF STIMULI                        [4] O.  Cekan,,   J. Podivinsky, and              Z.  Kotasek.   Program
                                                                           Generation Through a Probabilistic Constrained Grammar. In
                                                                           2018  Euromicro           Conference on        Digital     System Design
                Fig. 4: The code coverage in functional verification.      (DSD), accepted to conference, 8 pages, Aug 2018.

IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018 335

[5] J. Podivinsky, O. Cekan, J. Lojda, M. Zachariasova, M. on Information Technology Interfaces, 527-532, May 2011. Krcma, and Z. Kotasek. Functional verification based platform for evaluating fault tolerance properties. [10] B. Wess. Automatic code generation for integrated Microprocessors and Microsystems, 52:145-159, 2017. digital signal processors. In 1991., IEEE International Sympoisum on Circuits and Systems, pages 33-36 vol.1, Jun [6] D. A. Patterson. Reduced instruction set computers. 1991. Commun. ACM, 28(1):8-21, January 1985. [11] A. M. Amiri, A. Khouas, and M. Boukadoum. [7] S. Tasiran and K. Keutzer. Coverage metrics for Pseudorandom stimuli generation for testing time-to-digital functional validation of hardware designs. Design and Test of converters on an fpga. IEEE Transactions on Computers, IEEE, 18(4):36-45, May 2001. Instrumentation and Measurement, 58(7):2209-2215, July 2009. [8] M. Graphics. Verification academy - the most comprehensive resource for verification training, [Online] [12] G. Squillero. Microgp-an evolutionary assembly (2013). Available: www.verificationacademy.com. program generator. Genetic Programming and Evolvable Machines, 6(3):247-263, 2005. [9] J. Hudec. An efficient technique for processor automatic functional test generation based on evolutionary strategies. In [13] J. G. Bartkowiak and M. A. Nix. Arithmetic logic unit, Proceedings of the ITI, 33rd International Conference Jan. 25 1994. US Patent 5,282,153.

336 IEEE EWDTS, Kazan, Russia, September 14 - 17, 2018