CROSS-REFERENCE TO RELATED APPLICATIONS

[0001] This application claims priority to United States provisional patent application number 63/034,759, filed June 4, 2020, by Jingliang Wang, and titled “Speculative Branch-Not- Taken Instruction Stream Generation,” which is incorporated by reference.

TECHNICAL FIELD

[0002] The present application relates to central processing unit (CPU) simulation, and more specifically to generating speculative branch-not-taken instruction streams.

BACKGROUND

[0003] Functional verification of a CPU design attempts to verify that the logic design of the CPU conforms to its specification. Such functional verification is complex because a large number of test cases are needed to increase assurance that the design conforms to its specification. For CPU design verification, such test cases include streams of instructions to be executed by a simulated CPU design in a design simulation system.

SUMMARY

[0004] A first aspect relates to a method for simulating a branch instruction by a network device. The method includes generating a branch instruction; and implementing a first loop of the method. The first loop of the method includes generating a branch-not-taken (BNT) instruction; simulating the BNT instruction; determining whether there has been a change in a simulation state resulting from simulation of the BNT instruction; storing in a BNT record the change in the simulation state when it is determined that there has been a change in the simulation state; determining whether a predetermined number of BNT instructions have been generated; and terminating the first loop when the predetermined number of BNT instructions have been generated. The method further includes restoring the simulation state based on the BNT record.

[0005] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the network device is configured as an instruction stream generator (ISG), the method performed by the ISG.

[0006] Optionally, in any of the preceding aspects, another implementation of the aspect provides that, after restoring the simulation state based on the BNT record, the method further comprises generating one or more branch-taken instructions.

[0007] Optionally, in any of the preceding aspects, another implementation of the aspect provides that one BNT instruction is a second branch instruction; and simulating the second branch instruction includes generating a second BNT instruction; simulating the second BNT instruction; determining whether there has been a change in the simulation state resulting from simulation of the second BNT instruction; storing in a second BNT record, the change in the simulation state when it is determined that there has been a change in the simulation state; determining whether a second predetermined number of second BNT instructions have been generated; and terminating the second loop when the second predetermined number of second BNT instructions have been generated. Simulating the second branch instruction further includes restoring the simulation state based on the second BNT record.

[0008] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the branch instruction jumps to a branch target address and the BNT instructions are generated at a next sequential address after the branch instruction. [0009] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the branch instruction continues to a next sequential address after the branch instruction and the BNT instructions are generated at a branch target address.

[0010] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the BNT instructions are generated under one or more constraints on resource dependency, exception triggering, exception prevention, memory paging, data patterns, and memory sharing.

[0011] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the ISG includes an instruction set simulator (ISS) shared library and: each BNT instruction is simulated by the ISS shared library; and the change in the simulation state is received by the ISG from the ISS shared library.

[0012] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the method further includes sending to a central processing unit (CPU) design simulation environment, an executable test case including the branch instruction and the BNT instructions.

[0013] A second aspect relates to a method for simulating a branch instruction by an instruction stream generator (ISG). The method includes generating, by the ISG, a branch instruction; generating, by the ISG, a plurality of branch-not-taken (BNT) instructions; simulating, by the ISG, each BNT instruction of the plurality of BNT instructions; determining, by the ISG, whether there has been a change in a simulation state resulting from simulation of the BNT instructions; storing, by the ISG, in a BNT record, the change in the simulation state when it is determined that there has been a change in the simulation state; and restoring, by the ISG, the simulation state based on the BNT record. [0014] Optionally, in any of the preceding aspects, another implementation of the aspect provides that, after restoring the simulation state based on the BNT record, the method further includes generating, by the ISG, one or more branch-taken instructions.

[0015] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the plurality of BNT instructions is a first plurality of BNT instructions; one BNT instruction of the first plurality of BNT instructions is a second branch instruction; and simulating the second branch instruction includes generating, by the ISG, a second plurality of BNT instructions; simulating, by the ISG, each BNT instruction of the second plurality of BNT instructions; determining, by the ISG, whether there has been a second change in the simulation state resulting from simulation of the second BNT instructions; storing, by the ISG, in a second BNT record, the second change in the simulation state when it is determined that there has been a second change in the simulation state; and restoring, by the ISG, the simulation state based on the second BNT record.

[0016] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the branch instruction jumps to a branch target address and the plurality of BNT instructions are generated at a next sequential address after the branch instruction.

[0017] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the branch instruction continues to a next sequential address after the branch instruction and the plurality of BNT instructions are generated at a branch target address.

[0018] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the plurality of BNT instructions are generated under one or more constraints on resource dependency, exception triggering, exception prevention, memory paging, data patterns, and memory sharing. [0019] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the ISG includes an instruction set simulator (ISS) shared library and: each BNT instruction of the plurality of BNT instructions is simulated by the ISS shared library; and the change in the simulation state is received by the ISG from the ISS shared library.

[0020] Optionally, in any of the preceding aspects, another implementation of the aspect provides that the method further includes sending, by the ISG to a central processing unit (CPU) design simulation environment, an executable test case including the branch instruction and the plurality of BNT instructions.

[0021] For the purpose of clarity, any one of the foregoing embodiments may be combined with any one or more of the other foregoing embodiments to create a new embodiment within the scope of the present disclosure.

[0022] These and other features, and the advantages thereof, will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings and claims.

BRIEF DESCRIPTION OF THE DRAWINGS [0023] For a more complete understanding of this disclosure, reference is now made to the following brief description, taken in connection with the accompanying drawings and detailed description, wherein like reference numerals represent like parts.

[0024] FIG. 1 presents a block diagram of a CPU design simulation system according to the embodiment.

[0025] FIG. 2A presents a flow chart of an overview of a first method according to the embodiment for generating a branch-not-taken (BNT) instruction stream.

[0026] FIG. 2B presents a flow chart of a detail view of the first method of FIG. 2 A. [0027] FIG. 3 presents a schematic view of execution of an instruction stream generated by a method according to the embodiment for generating a BNT instruction stream.

[0028] FIG. 4 presents a flow chart of a second view of the first method of FIG. 2 A.

[0029] FIG. 5 presents a flow chart of a second method according to the embodiment for generating a BNT instruction stream.

[0030] FIG. 6 is a schematic diagram illustrating a network device according to an embodiment of the present disclosure.

[0031] FIG. 7 illustrates an apparatus configured to implement one or more of the methods described herein for generating a BNT instruction stream.

DETAILED DESCRIPTION

[0032] It should be understood at the outset that, although illustrative implementations of one or more embodiments are provided below, the disclosed systems and/or methods may be implemented using any number of techniques, whether currently known or in existence. The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims along with their full scope of equivalents.

[0033] A design simulation system according to the disclosure includes an instruction stream generator (ISG) that generates streams of instructions that test various functions of a CPU design being simulated by the design simulation system. One function that the ISG tests is how the CPU handles branch instructions. A branch instruction includes a test criterion and a branch target address. The test criterion typically compares a value in a CPU register or at an address in memory to another value — which may be a constant value or a value in another CPU register or at another address in memory. When the CPU executes the branch instruction, if the test criterion is met, the CPU jumps to the branch target address and begins executing a sequence of instructions stored at that address. If the test criterion is not met, the CPU begins executing a sequence of instructions that begins at the address that sequentially follows the branch instruction.

[0034] Some CPUs include an instruction pipeline in which some number of instructions are pre-fetched and pre-processed prior to actual execution of the instructions. Such an instruction pipeline can enable faster execution of an instruction stream. Such CPUs may have a branch- predictor function that predicts whether a branch instruction will jump to the branch target address or continue to the next sequential address. In some scenarios, the branch prediction is incorrect and the instructions in the pipeline are referred to as a branch-not-taken (BNT).

[0035] The process of simulating a BNT scenario in a CPU design starts with the branch predictor making an incorrect prediction. The process then begins simulating instructions in the BNT path. When the simulated CPU design recognizes that the branch was incorrectly predicted, the simulation recovers from the BNT instructions and begins simulating instructions of the correct branch. Using an ISG according to the present disclosure, the correct and clean recovery of the BNT simulation can be thoroughly tested. The number of instructions in the BNT path may be based on the depth of the instruction pipeline, or may be larger, in order to test more complex BNT scenarios.

[0036] Simulating a BNT scenario for a branch instruction includes simulating the branch instruction, simulating some number of BNT instructions, resetting the simulation to its state when the branch instruction was executed, and continuing with simulation of branch-taken instructions. Some simulation systems store one or more simulation state variables for use when resetting the simulation after simulating the BNT instructions. It is often impractical (due to storage space and/or time constraints) to store all simulation state variables when the branch instruction is executed, therefore such systems typically store a predetermined group of simulation state variables, the group being a subset of simulation state variables. The BNT instructions may change simulation state variables that are not part of the predetermined group of variables, with the result that the simulation is not fully reset to its pre-branch state after the BNT instructions have been simulated.

[0037] An ISG according to the present disclosure generates and simulates BNT instructions and records in a BNT record the actual changes that the BNT instructions make to the simulation state as they are simulated. When all BNT instructions have been generated and simulated, the ISG according to the present disclosure fully restores the pre-branch state of the simulation using the information stored in the BNT record.

[0038] In some scenarios, the BNT instructions may include a second branch instruction — a nested branch instruction. While simulating the first branch instruction and its BNT instructions, the ISG will simulate the nested branch instruction and its associated BNT instructions, before returning to continue simulation of the original BNT instructions. Because an ISG according to the present disclosure fully restores the pre-branch state of the simulation after both sets of BNT instructions, such a complex simulation scenario may be successfully tested.

[0039] In some ISGs, BNT instructions are generated fully randomly, which can lead to premature termination of a BNT simulation in a test run of the CPU based on branch prediction, preventing full testing of a feature of the CPU design when branch prediction provides incorrect prediction. An ISG according to the present disclosure generates instructions using constraints that reduce the likelihood of generating an instruction that will prematurely terminate a test run. [0040] FIG. 1 presents a block diagram of a CPU design simulation system 100 according to the embodiment. An ISG 104 (which may also be referred to as an instruction sequence generator) receives one or more test templates 102 from a user of the ISG 104. The test templates 102 describe instructions to be generated by the ISG 104. In some embodiments, the ISG 104 is an open FORCE-RISCV ISG. RISCV indicates that a reduced instruction set computer (RISC), more specifically, with RISC-V ISA is being simulated by the CPU design simulation system 100. The ISG 104 uses an instruction set architecture simulator (ISS) shared library 106 of code segments to simulate instructions generated by the ISG 104. Instruction sequences generated by the ISG 104 are used in executable test cases 108 that are executed by a CPU design simulation environment (DSE) 110 using an ISS cosimulation library 112. As the DSE 110 produces simulation results (or test run results) a user of the DSE 110 performs an interactive result checking process 114 on the results, also using the ISS cosimulation library 112

[0041] At least the ISG 104, the ISS shared library 106, the DSE 110, and the ISS cosimulation library 112 are software comprising instructions stored in memory of a computing device and executed by a processor of the computing device. Typically, the CPU design simulation system 100 is implemented on multiple computing devices interconnected by a communication network using an Ethernet network and/or the Internet protocol. Such computing devices may be referred to as network devices. In some embodiments, the ISG 104 and the ISS shared library 106 may be implemented in software on a first network device. In such embodiments, the test templates 102 may be generated on the same network device, or may be received by that network device from another network device. In such embodiments, the DSE 110 and the ISS cosimulation library 112 may be implemented on one or more other network devices.

[0042] In other embodiments, a smaller-scale CPU design simulation system 100 may be implemented on a single network device.

[0043] FIG. 2A presents a flow chart of an overview of a first method 200 according to the embodiment for generating a BNT instruction stream. The BNT instruction stream may also be referred to as a speculative BNT instruction stream. The method 200 may be performed by the ISG 104. In step 202, a branch instruction is generated. The BNT portion of the branch instruction is simulated in the steps enclosed in the box 220.

[0044] In step 204, a predetermined number of BNT instructions are generated and simulated. As each BNT instruction is simulated, any resulting changes to the simulation state are recorded in a BNT record 206. A detailed view of step 204 is presented in FIG. 2B. As described above, the predetermined number of BNT instructions is determined by an instruction pipeline depth or other characteristic of the CPU being simulated.

[0045] In step 208, once all BNT instructions have been generated and simulated, information in the BNT record 206 is used to reset the simulation state variables to their state before step 204 was performed. In step 210, the ISG 104 continues by generating and simulating branch-taken instructions and other succeeding instructions.

[0046] FIG. 2B presents a flow chart of a detail view of the first method 200 of FIG. 2A. Step 204 begins with step 230, where the ISG 104 generates and simulates a first BNT instruction. Any change to the simulation state caused by the simulation of the first BNT instruction is stored in the BNT record 206. [0047] Where the operands of instructions are generated randomly or in an unconstrained manner, they may have the unintended effect when simulated of creating an exception or other condition that causes simulation to stop unexpectedly. Such an unexpected exception or other error may cause premature termination of a BNT simulation in a test run in the DSE 110, thus not providing enough testing of the CPU design’s recovery from incorrect branch prediction, since the BNT simulation does not go deep enough in the pipeline.

[0048] In the ISG 104, instructions and their operands are generated under constraints that reduce unexpected exceptions or that produce desired results when simulated by the DSE 110. Such constraints may include proper or improper resource dependency, deliberate exception triggering or exception prevention, testing of memory paging, use of specified data patterns, and testing of memory sharing functions. As a result, the BNT simulated by the CPU design can cause the recovery from incorrect branch prediction to happen at any stage in the pipeline, include the deepest possible complex scenarios.

[0049] The ISG 104 may use the ISS shared library 106 in simulating the first BNT instruction (and subsequent BNT instructions). The change to the simulation state may be described in information received by the ISG 104 from the ISS shared library 106.

[0050] In step 232, the ISG 104 generates and simulates a second BNT instruction. Again, any change to the simulation state caused by the simulation of the second BNT instruction is stored in the BNT record 206. The step 204 continues generating and simulating the predetermined number of BNT instructions until, in step 234, the last BNT instruction is generated and simulated and any resulting change in the simulation state stored in the BNT record 206. The method 200 then continues in step 206. [0051] In some scenarios, the BNT instruction generated step 232 (or any other step of step 204) may itself be a branch instruction. In such a scenario, the BNT portion of such a branch instruction is simulated in step 220, which was shown in FIG. 2A to comprise step 204 (generating and simulating BNT instructions) and step 208 (restoring the simulation state after simulating BNT instructions). As shown in FIG. 2B, the ‘branch-taken’ instructions that follow the simulation of the BNT portion of the branch instruction in step 220 comprise the final BNT instruction generated in step 234 and any intervening BNT instructions generated in step 204 between step 232 and step 234.

[0052] FIG. 3 presents a schematic view of execution of an instruction stream 300 generated by a method according to the embodiment for generating a BNT instruction stream. The instruction stream 300 includes a first stream 302 of instructions that are simulated before a first branch instruction 304. For the first branch instruction 304, the ISG 104 simulates a scenario where BNT instructions 306 are generated at a next sequential address after the first branch instruction 304. Once the BNT instructions 306 have been generated and simulated, and the system state restored, the first branch instruction 304 jumps to a branch target address that begins a second stream 308 of instructions. When a second branch instruction 310 is generated, the ISG 104 simulates a scenario where BNT instructions 312 are generated at a branch target address. Once the BNT instructions 312 have been generated and simulated, and the system state restored, the second branch instruction 310 continues with a third stream 314 of instructions that are generated at next sequential address after the second branch instruction 310.

[0053] FIG. 4 presents a flow chart 400 showing an alternate view of the first method 200 of FIGS. 2 A and 2B. In step 402 a branch instruction is generated. The BNT portion of the branch instruction is simulated in the steps enclosed in the box 420. [0054] In step 440 a BNT instruction is generated. In step 442, the BNT instruction is simulated and in step 444, any change to the simulation state caused by the simulation of the BNT instruction is stored in the BNT record 206. As described above, the ISG 104 may use the ISS shared library 106 to simulate the BNT instruction and receive from the ISS shared library 106 information relating to a resulting change in the simulation state.

[0055] In step 446, a determination is made whether the predetermined number of BNT instructions have been generated and simulated. If not, the flow chart 400 returns to step 440 to generate another BNT instruction. If it is determined in step 446 that the predetermined number of BNT instructions has been generated and simulated, then in step 448 the simulation state is restored using the BNT record 206 and the flow chart 400 continues to step 410.

[0056] FIG. 5 presents a flow chart of a second method 500 according to the embodiment for generating a BNT instruction stream. In step 502, a branch instruction is generated. In step 504, a predetermined number of BNT instructions are generated. In step 506, the generated BNT instructions are simulated and it is determined whether any change in the simulation state resulted from the simulation of the BNT instructions and, if so, the changes are stored in the BNT record 206. In step 508, the simulation state is restored based on the BNT record 206. [0057] FIG. 6 is a schematic diagram illustrating a network device 600 according to an embodiment of the present disclosure. The network device 600 includes receiver units (RX) 620 or receiving means for receiving data via ingress ports 610. The network device 600 also includes transmitter units (TX) 640 or transmitting means for transmitting via data egress ports 650.

[0058] The network device 600 includes a memory 660 or data storing means configured to store the instructions and various data. The memory 660 can be any type of or combination of memory components capable of storing data and/or instructions. For example, the memory 660 can include volatile and/or non-volatile memory such as read-only memory (ROM), random access memory (RAM), ternary content-addressable memory (TCAM), and/or static random- access memory (SRAM). The memory 660 can also include one or more disks, tape drives, and solid-state drives. In some embodiments, the memory 660 can be used as an over-flow data storage device to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution.

[0059] The network device 600 has one or more processor(s) 630 or other processing means (e.g., central processing unit (CPU)) to process instructions. The processor 630 may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), field- programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor 630 is communicatively coupled via a system bus with the ingress ports 610, RX 620, TX 640, egress ports 650, and memory 660. The processor 630 can be configured to execute instructions stored in the memory 660. Thus, the processor 630 provides a means for performing any computational, comparison, determination, initiation, configuration, or any other action corresponding to the claims when the appropriate instruction is executed by the processor. In some embodiments, the memory 660 can be memory that is integrated with the processor 630.

[0060] In one embodiment, the memory 660 stores an ISG 670. The ISG 670 includes data and executable instructions for implementing the disclosed embodiments. For instance, the ISG 670 can include instructions for implementing the methods described in FIGS. 2A-B, 4, and 5. In some embodiments, the memory 660 also stores an ISS shared library 680. The ISS shared library 680 includes data and executable instructions for implementing the disclosed embodiments. For instance, the ISS shared library 680 can include instructions for simulating a BNT instruction as described in FIGS. 2A-B, 4, and 5. The inclusion of the ISG 670 substantially improves the functionality of the network device 600 by enabling an ISG according to the disclosure to store actual changes to a simulation state while generating and simulating a BNT instruction stream. For similar reasons, the inclusion of the ISS shared library 680 substantially improves the functionality of the network device 600. A network device 600 including an ISG 670 implementing a first of the disclosed methods for generating and simulating a BNT instruction stream is a different system than a network device 600 that includes an ISG 670 that implements a second of the disclosed methods for generating and simulating a BNT instruction stream.

[0061] The network device 600 includes data and executable instructions for implementing an ISG as described in any of FIGS. 2A-B, 4, and 5. In other embodiments, the network device 600 may additionally implement other elements of the CPU design simulation system 100.

[0062] FIG. 7 illustrates an apparatus 700 configured to implement one or more of the methods described herein for generating a BNT instruction stream, such as, for example, the method 200 of FIGS. 2A-B, the method 400 of FIG. 4, or the method 500 of FIG. 5. The apparatus 700 may be implemented in the network device 600. The apparatus 700 comprises means 702 for generating a branch instruction, as described with reference to step 202 of the method 200, step 402 of the method 400, or step 502 of the method 500; and means 704 for generating, simulating, and storing simulation state changes caused by BNT instructions, as described with reference to step 204 of the method 200, steps 440, 442, 444, and 446 of the method 400, or steps 504, 506, and 508 of the method 500; and means 706 for restoring the simulation state based on stored changes, as described with reference to step 208 of the method 200, step 448 of the method 400, or step 510 of the method 500.

[0063] While several embodiments have been provided in the present disclosure, it may be understood that the disclosed systems and methods might be embodied in many other specific forms without departing from the spirit or scope of the present disclosure. The present examples are to be considered as illustrative and not restrictive, and the disclosure is not to be limited to the details given herein. For example, the various elements or components may be combined or integrated in another system or certain features may be omitted, or not implemented.

[0064] In addition, techniques, systems, subsystems, and methods described and illustrated in the various embodiments as discrete or separate may be combined or integrated with other systems, modules, techniques, or methods without departing from the scope of the present disclosure. Other items shown or discussed as coupled or directly coupled or communicating with each other may be indirectly coupled or communicating through some interface, device, or intermediate component whether electrically, mechanically, or otherwise. Other examples of changes, substitutions, and alterations are ascertainable by one skilled in the art and may be made without departing from the spirit and scope disclosed herein.