CN119396472A

CN119396472A - Branch prediction method, branch predictor and electronic equipment

Info

Publication number: CN119396472A
Application number: CN202510004591.8A
Authority: CN
Inventors: 王喜强
Original assignee: Niuxin Semiconductor Shenzhen Co ltd
Current assignee: Niuxin Semiconductor Shenzhen Co ltd
Priority date: 2025-01-02
Filing date: 2025-01-02
Publication date: 2025-02-07

Abstract

The application provides a branch prediction method, a branch predictor and electronic equipment. The branch prediction method comprises the steps of reading a first branch instruction, predicting an execution result of the first branch instruction according to a first prediction information index to obtain a first prediction result, wherein the first prediction result comprises a prediction jump direction and a prediction jump address of the first branch instruction, reading a second branch instruction, predicting the execution result of the second branch instruction to obtain a second prediction result, wherein the second prediction result comprises the prediction jump direction and the prediction jump address of the second branch instruction, the second branch instruction is the next branch instruction of the first branch instruction, and updating the second prediction result according to the execution result of the first branch instruction. The application is used for improving the efficiency of branch prediction.

Description

Branch prediction method, branch predictor and electronic equipment

Technical Field

The present application relates to the field of computer technologies, and in particular, to a branch prediction method, a branch predictor, and an electronic device.

Background

With the continued evolution of computer architecture, the performance and complexity of processors are increasing, and now processor architectures employ pipelining to improve the execution efficiency and throughput of the processor. Branch prediction techniques are core techniques for processors to process branch instructions by predicting branch instructions in a program execution path in order to better execute control flows.

Existing branch strategies have a way to quickly retrieve and predict the target of a branch by storing the target address of the branch instruction, and by integrating the branch predictor, increase the accuracy of the prediction, but also increase hardware costs, introduce additional delay to the contention and selection logic, and require more storage to maintain the state of multiple prediction phases. RAS (Return ADDRESS STACK ) is mainly used to solve the branch prediction problem of function calls and returns, but its performance is limited by the depth of the call stack, and for deep recursion or complex function nesting situations, the capacity of the RAS may be insufficient to effectively predict the Return address, resulting in branch prediction inaccuracy.

In addition, due to the variety of programs, the same branch prediction algorithm may exhibit different accuracies in the branch prediction results in different programs.

Thus, existing branch prediction strategies face challenges as program complexity increases and execution environments change. The complexity of branch instructions, frequent program calls and returns, and other factors have led to the accuracy of branch prediction techniques being continually limited.

Disclosure of Invention

An object of the present application is to provide a branch prediction method, a branch predictor and an electronic device for improving the efficiency of branch prediction.

According to an aspect of an embodiment of the present application, there is provided a branch prediction method, including:

reading a first branch instruction, and predicting an execution result of the first branch instruction according to a first prediction information index to obtain a first prediction result, wherein the first prediction result comprises a predicted jump direction and a predicted jump address of the first branch instruction;

reading a second branch instruction and predicting an execution result of the second branch instruction to obtain a second prediction result, wherein the second prediction result comprises a predicted jump direction and a predicted jump address of the second branch instruction, and the second branch instruction is the next branch instruction of the first branch instruction;

and updating the second prediction result according to the execution result of the first branch instruction.

According to an aspect of an embodiment of the present application, there is provided a branch predictor including:

the branch prediction module is used for receiving a branch instruction and predicting the branch instruction to obtain a prediction result, wherein the prediction result is used for indicating whether the branch instruction jumps or not;

The instruction fetching module is used for reading the branch instruction and sending the branch instruction to the branch prediction module, receiving the prediction result returned by the branch prediction module and performing instruction fetching operation of the next instruction fetching period according to the prediction result;

and the instruction execution module is used for executing the branch instruction to obtain an execution result of the branch instruction and sending the execution result to the branch prediction module so that the branch prediction module updates the prediction result according to the execution result.

According to an aspect of an embodiment of the present application, there is provided an electronic device including:

One or more processors including the branch predictor provided by the above embodiments;

And storage means for storing one or more programs that, when executed by the one or more processors, cause the electronic device to implement the methods provided in the various alternative implementations described above.

According to the branch prediction method provided by the embodiment of the application, the execution result of the first branch instruction is predicted according to the first prediction branch information index by reading the first branch instruction, so as to obtain a first prediction result; the branch predictor provided by the other embodiment of the application reads the branch instruction through the instruction fetching module and sends the branch instruction to the branch prediction module, the branch prediction module predicts the execution result of the branch instruction to obtain a prediction result, and the prediction result is returned to the instruction fetching module, so that the instruction fetching module can perform instruction fetching operation of the next instruction fetching period according to the prediction result, the branch prediction module can predict the execution result of the branch instruction of the next instruction fetching period, and update the prediction result of the branch instruction of the next instruction fetching period according to the execution result of the branch instruction of the current instruction fetching period, the efficiency of branch prediction is improved, the circuit structure for executing the branch prediction method is ensured to be simple, and the occupied area of hardware is small.

Other features and advantages of the application will be apparent from the following detailed description, or may be learned by the practice of the application.

It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the application as claimed.

Drawings

The above and other objects, features and advantages of the present application will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings.

FIG. 1 is a schematic diagram of a branch predictor according to an embodiment of the present application.

FIG. 2 illustrates an application environment schematic of a branch predictor.

FIG. 3 illustrates a schematic workflow diagram of a branch prediction module.

Fig. 4 shows a state jump schematic of a two-bit saturation counter.

Fig. 5 shows a flow chart of a branch prediction method provided in this embodiment.

Fig. 6 shows a schematic structural diagram of an electronic device according to an embodiment of the application.

Detailed Description

Example embodiments will now be described more fully with reference to the accompanying drawings. However, the exemplary embodiments may be embodied in many different forms and should not be construed as limited to the examples set forth herein, but rather, the exemplary embodiments are provided so that the description of the present application will be more complete and thorough, and will fully convey the concept of the exemplary embodiments to those skilled in the art. The drawings are merely schematic illustrations of the present application and are not necessarily drawn to scale. The same reference numerals in the drawings denote the same or similar parts, and thus a repetitive description thereof will be omitted.

Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more example embodiments. In the following description, numerous specific details are provided to give a thorough understanding of example embodiments of the application. However, those skilled in the art will recognize that the aspects of the application may be practiced without one or more of the specific details, or with other methods, components, steps, etc. In other instances, well-known structures, methods, implementations, or operations are not shown or described in detail to avoid obscuring aspects of the application.

Some of the block diagrams shown in the figures are functional entities and do not necessarily correspond to physically or logically separate entities. These functional entities may be implemented in software or in one or more hardware modules or integrated circuits or in different networks and/or processor devices and/or microcontroller devices.

In modern processor microarchitecture designs, pipelining is used to improve the execution efficiency and throughput of the processor, and branch prediction is one of the key technologies to improve instruction pipelining. In pipelining, the processor pre-fetches instructions rather than waiting until the last instruction is completed. However, when a branch instruction is encountered, the next instruction to be executed depends on the result of the branch instruction, which may cause pipeline interruption, greatly reducing the execution efficiency of the processor, and thus a branch prediction technique needs to be introduced to predict the execution result of the branch instruction to satisfy the normal operation of the pipeline. However, for the branch prediction technology itself, a highly accurate branch prediction algorithm means that there are more logic circuits, which occupy more silicon area and consume more power, and also affect the single cycle processing time in the processor pipeline technology. In addition, because of the variety of software programs, the same branch prediction algorithm may differ in branch prediction accuracy among different software programs.

The embodiment provides a branch predictor and a branch prediction method based on a branch instruction in RV64IC instruction set, which are suitable for a branch instruction processing environment in a RISC-V processor.

There are 13 branch instructions in the RISC-V instruction set, with 8 branch instructions in the integer instruction set RV 64I. There are 5 of the compressed instruction sets RVC.

The manner in which branch instructions are addressed is divided into direct addressing and indirect addressing. The direct addressing is that the jump address is the PC value of the current instruction plus the offset address information carried in the instruction. Indirect addressing is where the jump address is equal to the base address in the addressing register plus the offset address information written in the instruction.

All conditional branch instructions are addressed directly. Conditional branch instructions are used to determine the execution path of a program based on the true or False (Ture/False) of a particular condition.

Conditional branch instructions employ a Global History (Global History) branch prediction approach. The global history branch prediction is to record the execution results of all previous conditional branch instructions by using a global history register.

The global history register is a serial shift register, and each time a conditional branch instruction is executed, the execution result is shifted into the register from the right, 1 indicates that the conditional branch instruction has jumped, and 0 indicates that the conditional branch instruction has not jumped.

As shown in fig. 1, the branch predictor includes:

A branch prediction module 50, configured to receive a branch instruction and predict the branch instruction to obtain a prediction result, where the prediction result is used to indicate whether the branch instruction jumps;

The instruction fetching module 10 is used for reading the branch instruction and sending the branch instruction to the branch prediction module 50, receiving the prediction result returned by the branch prediction module 50, and performing instruction fetching operation of the next instruction fetching period according to the prediction result;

The instruction execution module 30 is configured to execute a branch instruction to obtain an execution result of the branch instruction, and send the execution result to the branch prediction module 50, so that the branch prediction module 50 updates the prediction result according to the execution result. Specifically, the branch predictor is combined with the pipeline architecture, so that the normal operation of the pipeline is ensured on one hand. On the other hand, the execution result of the branch instruction is predicted by the branch predictor, and the obtained prediction result is used for guiding the operation of the next branch instruction. FIG. 2 illustrates an application environment schematic of a branch predictor.

As shown in fig. 2, further, the branch predictor further includes:

and one end of the quick decoding module 70 is connected with the instruction fetching module 10, and the other end of the quick decoding module 70 is connected with the branch prediction module 50, and is used for receiving the branch instruction sent by the instruction fetching module 10, extracting the instruction information of the branch instruction, and sending the instruction information of the branch instruction to the branch prediction module 50.

The fast decode module 70 is configured to extract valid information in the branch instruction and send the valid information to the branch prediction module 50.

FIG. 3 shows a schematic workflow diagram of branch prediction module 50.

Further, the branch prediction module 50 includes a first level prediction unit and a second level prediction unit, and the branch prediction module 50 stores the prediction result of the branch instruction through the first level prediction unit and the second level prediction unit.

The first level prediction unit and the second level prediction unit are branch storage units of the branch history table in the branch prediction module 50, and are configured to store the predicted result of the next branch instruction according to two possible jump results, so as to mask the delay of one cycle when the memory interface reads data.

The first-stage prediction unit and the second-stage prediction unit both comprise:

a branch direction prediction unit for predicting a jump direction of the branch instruction;

a branch address prediction unit for predicting a jump address of the branch instruction;

And a return stack for storing return addresses of the branch instructions.

Specifically, the branch direction prediction unit may address a two-bit saturation counter based on the prediction index information. And obtaining a prediction result about the jump direction according to the state value of the two-bit saturation counter.

There are two types of branch instructions in the RISC-V instruction set that require address prediction. The first is the jump address of the conditional branch instruction. The second is JALR instruction in indirect addressing.

JALR (Jump AND LINK REGISTER, jump and connect to registers) instruction, table 1 is used to implement operations such as function call, indirect Jump or dynamic Jump.

Table 1 JALR encoding of instructions and table of operations performed by the return address stack

Wherein rd is a target register for storing a return address, and rs1 is a source register 1 containing a base address.

And returning the stack, namely returning the stack for the subroutine. A last-in-first-Out (LAST IN FIRST Out) structure is used. In the RISC-V architecture, there are two types of instructions, the JAL instruction and the JALR instruction, for invoking a subroutine.

JAL (Jump And Link) instructions are used to implement direct jumps while saving return addresses, commonly used for function calls And control flow jumps of programs.

In the RISC-V architecture, when the destination register in the JAL instruction is an x1 register or an x5 register, which indicates that this is the invoking process of the subroutine, the return address in the JAL instruction needs to be written into the return stack.

Further, in the present embodiment, a five-stage pipeline is used, and the instruction fetch module 10, the instruction decode module 20, the instruction execution module 30, the memory access module 40 and the write-back module 60 are configured.

The branch predictor reads the branch instruction through the fetch module 10 and fetches the instruction information of the branch instruction through the fast decode module 70.

Instruction decode module 20 is responsible for resolving branch instructions, determining the type of operation and operand location.

The instruction execution module 30 is used for executing branch instructions, including performing operations, address calculations, and the like.

The memory module 40 is used for accessing the data memory for reading or writing data.

The write-back module 60 writes back the operation result to a register or a memory.

Pipeline technology breaks the execution process of instructions into a plurality of stages and executes different stages on a plurality of instructions simultaneously to improve instruction throughput.

The branch prediction module 50 sets a branch history table, and the prediction information index of the branch history table is formed by splicing a part of PC value and a global history register value. The prediction information index is used for addressing a two-bit saturation counter value in the branch history table, and predicting whether the current branch instruction jumps according to the two-bit saturation counter value.

Fig. 4 shows a state jump schematic of a two-bit saturation counter. Table 2 shows the correspondence of the state values of the two-bit saturation counters to the predicted behavior.

Table 2 correspondence table of state values and predicted behavior

(1) Strong non-jump (Strongly Not Taken) is that the counter is in saturated state, the conditional branch instruction is predicted not to jump, the update rule is that if the conditional branch instruction does not jump, the current state value is kept, otherwise, the state value is changed to 01;

(2) Weak non-jump (Weakly Not Taken) is that the counter is in unsaturated state, the jump of conditional branch instruction is predicted, the update rule is that if the conditional branch instruction is not jumped, the current state value is kept, otherwise, the value is changed to 10;

(3) Weak jump (WEAKLY TAKEN) is that the counter is in unsaturated state, the jump of conditional branch instruction is predicted, the update rule is that if the conditional branch instruction jumps, the state value is changed to 11, otherwise, the state value is changed to 01;

(4) The strong jump (Strongly Taken) is that the counter is in saturated state, the jump of conditional branch instruction is predicted, the update rule is that if the conditional branch instruction jumps, the current state value is kept, otherwise, the process is changed to 10.

From the above, it can be seen that when the predicted outcome of the branch instruction is consistent with the execution outcome of the branch instruction, the two-bit saturation counter maintains the current prediction and deepens the robustness of the prediction.

When the predicted result of the branch instruction is inconsistent with the execution result of the branch instruction, the state of the two-bit saturation counter is adjusted in the opposite direction.

The method of predicting a branch instruction for the next fetch cycle by the branch prediction module 50 is by the value of the global history register.

Assuming that the branch instruction for the current cycle is A4, the Global History Register (GHR) has a value of 0101.

For the next branch instruction A5, the value of GHR is either 01010 or 01011, 01010 indicating that the result of the execution of A4 is not skipped, 01011 indicating that the result of the execution of A4 is skipped.

In the cycle of prediction for A4, a read access to the branch history table based on the GHR value of branch instruction A4 may be initiated, i.e., the predicted outcome of branch instruction A5 is obtained.

Because the memory read is delayed by one cycle, A5 can get its prediction result during the cycle of A4 execution even if A4 and A5 are continuously executed.

Fig. 5 shows a flow chart of a branch prediction method provided in this embodiment. The branch prediction method can be applied to the branch predictor provided in the above embodiment. As shown in fig. 5, the method includes:

s100, reading a first branch instruction, and predicting an execution result of the first branch instruction according to a first prediction information index to obtain a first prediction result, wherein the first prediction result comprises a predicted jump direction and a predicted jump address of the first branch instruction.

S200, reading the second branch instruction and predicting an execution result of the second branch instruction to obtain a second prediction result, wherein the second prediction result comprises a predicted jump direction and a predicted jump address of the second branch instruction, and the second branch instruction is the next branch instruction of the first branch instruction.

S300, updating the second prediction result according to the execution result of the first branch instruction.

Specifically, the first prediction information index is formed by splicing a part of PC value and a storage value of the global history register, and predicts an execution result of the first branch instruction to obtain a first prediction result.

When executing an instruction, the instruction pointed by the Program Counter (PC) is fetched from the memory by the fetch module 10, and after the instruction is processed according to the PC value processing mode of the branch instruction, the current PC value is transferred to the branch prediction module 50, and the PC value is updated according to the prediction result of the branch prediction module 50.

The instruction executed by the instruction fetching module 10 in the fetch memory is a branch instruction, and the instruction is sent to the branch prediction module 50, where the branch prediction module 50 predicts the execution result of the branch instruction to obtain a first prediction result, where the first prediction result includes a predicted jump direction and a predicted jump address, and the branch prediction module 50 returns the first prediction result to the instruction fetching module 10.

In the fetch module 10 stage, if the first predictor indicates a first branch instruction jump, the fetch module 10 will jump to the predicted jump address included in the first predictor. If the first predictor indicates that the first branch instruction does not jump, the fetch module 10 continues to fetch instructions from sequential addresses.

In the instruction fetching cycle of the next instruction, namely the second branch instruction, access to the branch history table can be initiated according to the first prediction result, so that a second prediction result is obtained, and the second prediction result comprises a predicted jump address and a predicted jump direction of the second branch instruction.

In the period of processing the first branch instruction, when the instruction fetching module acquires the next instruction according to the first prediction unit, the first branch instruction is decoded by the instruction decoding module, and operands are read from the register. In cycles, instruction execution module 30 determines whether the values of the two registers satisfy the branch condition. If the condition is satisfied, executing the jump, and if not, continuing executing the sequential instruction.

In this embodiment, the instruction execution module 30 returns the execution result of the first branch module to the branch prediction module 50, and the branch prediction module 50 updates the prediction result of the second branch instruction after receiving the execution result.

After the instruction fetching module acquires the first branch instruction according to the PC value, the instruction codes such as the PC value of the first branch instruction are sent to the branch prediction module 50, and the branch prediction module 50 is spliced into a first prediction information index according to the partial PC value and the value of the global history register. The first prediction information index is used for initiating read access to the branch history table, and then addressing the two-bit saturation counter, and predicting the execution result of the first branch instruction according to the state value of the two-bit saturation counter.

The jump result of the history branch instruction is recorded through the global history register.

For example, for the first branch instruction, the global history register has a value of 0101.

For the second branch instruction, the value of the global history register is 01011 or 01010, and after the global history register is spliced with a part of the PC value, two prediction results, namely, two results of 0 and 1, for the second branch instruction are obtained respectively.

Two prediction units are reserved in the branch prediction module 50, and two prediction results of the second branch instruction are respectively stored.

When the branch prediction module 50 receives the execution result of the first branch instruction, it first determines a jump result of the first branch instruction according to the execution result, and updates the state value of the two-bit saturation counter according to the jump result. The second predictor may be affected by a change in the state value of the two-bit saturation counter. It is therefore necessary to update the second prediction result based on the execution result of the first branch instruction.

Further, S100, reading the first branch instruction, predicting an execution result of the first branch instruction according to the first prediction information index, to obtain a first prediction result, including:

s110, a first prediction information index is acquired, and the predicted jump direction of the first branch instruction is predicted according to the first prediction information index.

S120, according to the instruction type of the first branch instruction, obtaining the predicted jump address of the first branch instruction.

And indexing the state value of the two-bit saturation counter in the addressing branch history table according to the first prediction information to obtain a prediction result about the jump direction, and calculating the predicted jump address of the first branch instruction according to the prediction result of the jump direction and the instruction type of the first branch instruction.

By way of example, there are two types of branch instructions in RISC-V that require address prediction. The first is the jump address of the conditional branch instruction and the second is the JALR instruction in indirect addressing.

Instruction fetch module 10 may fetch the instruction after the first branch instruction jump based on the predicted jump address, thereby reducing latency.

Further, S120, obtaining a first prediction information index, predicting a predicted jump direction of the first branch instruction according to the first prediction information index, includes:

s1201, acquiring an instruction address value and a global historical data value stored in a program count register.

And S1203, splicing the instruction address value and the global historical data value to obtain a first prediction information index.

S1205, obtaining saturation count data based on the first prediction information index addressing, and obtaining the predicted jump direction of the first branch instruction according to the saturation count data.

Specifically, the saturation count data refers to the state value of the two-bit saturation counter in this embodiment.

The program counter register, also called program counter, is an important register in the processor for storing the address value of the instruction currently being executed.

The first prediction information index is addressed to a two-bit saturation counter in the branch history table, and predicts a predicted jump direction of the first branch instruction based on saturation count data of the two-bit saturation counter.

Further, S200, reading the second branch instruction and predicting an execution result of the second branch instruction to obtain a second prediction result, including:

s210, generating a second prediction information index according to the prediction jump direction in the first prediction result and the first prediction information index.

S220, based on the second prediction information index, the predicted jump direction of the second branch instruction is obtained.

S230, according to the instruction type of the second branch instruction, obtaining the predicted jump address of the second branch instruction.

The execution result prediction method of the second branch instruction is the same as that of the first branch instruction.

The second branch instruction is the next branch instruction to the first branch instruction. When generating the second prediction information index, it is necessary to include a global history data value in which the execution result of the first branch instruction is recorded.

In order to reduce latency, the second branch instruction is not predicted until execution of the first branch instruction is complete.

And predicting the second branch instruction according to the two possible values of the global historical data respectively to obtain a second prediction unit.

Since the memory read instruction is delayed by one cycle, even if the first branch instruction and the second branch instruction are continuously executed, the prediction result of the second branch instruction can be obtained in the current cycle. Further, updating the second prediction information index according to the execution result of the first branch instruction is required, including:

After the execution of the first branch instruction is completed, the execution result of the first branch instruction is obtained.

And updating the second prediction information index according to the execution result of the first branch instruction.

If the actual jump direction of the first branch instruction is inconsistent with the predicted jump direction of the first branch instruction, performing pipeline flushing operation and re-executing the first branch instruction.

Further, as can be seen from fig. 4 and table 2, when the two-bit saturation counter is in the saturation state, the predicted result is changed only when two consecutive predictions fail.

This means that the two-bit saturation counter is saturated when predicting the first branch instruction, and the predicted jump result of the second branch instruction is identical to the predicted jump result of the first branch instruction when predicting the second branch instruction. If the execution result of the first branch instruction is different from the predicted result, the state value is updated to be an unsaturated state with consistent predicted behavior, and the predicted result of the second branch instruction is not affected.

The second prediction result of the second branch instruction is not derived from the prediction result of the first branch instruction, but is instead addressed as a second prediction information index based on the global history table value of the first branch instruction, and the first branch instruction has not yet executed when predicting the execution result of the second branch instruction. After the first branch instruction is executed, the value of the global history register is updated according to the execution result of the first branch instruction, and the branch direction prediction unit is adjusted to return to the second prediction result of the instruction fetching module 10.

In this embodiment, the update is selected in the execution stage, and the first branch instruction is mispredicted, so that only the first branch instruction and the next instruction refresh of the execution result of the branch instruction are affected.

The branch predictor provided by the embodiment has a simple structure, reduces the storage size of a branch history table, is suitable for an embedded processor sensitive to the area of a silicon chip and power consumption, and can reduce the time delay of a pipeline when being applied to the branch predictor.

An electronic device 80 according to one embodiment of the application is described below with reference to fig. 6. The electronic device 80 shown in fig. 6 is merely an example and should not be construed as limiting the functionality and scope of use of embodiments of the present application.

As shown in fig. 6, the electronic device 80 is in the form of a general purpose computing device. The components of the electronic device 80 may include, but are not limited to, the at least one processing unit 510 described above, the at least one memory unit 520 described above, and a bus 530 that connects the various system components, including the memory unit 520 and the processing unit 510.

Wherein the storage unit stores program code that can be executed by the processing unit 510 such that the processing unit 510 performs the steps according to various exemplary embodiments of the present application described in the description of the exemplary methods described above in this specification. For example, the processing unit 510 may perform the various steps as shown in fig. 1.

The storage unit 520 may include readable media in the form of volatile storage units, such as Random Access Memory (RAM) 5201 and/or cache memory unit 5202, and may further include Read Only Memory (ROM) 5203.

The storage unit 520 may also include a program/utility 5204 having a set (at least one) of program modules 5205, such program modules 5205 including, but not limited to, an operating system, one or more application programs, other program modules, and program data, each or some combination of which may include an implementation of a network environment.

Bus 530 may be one or more of several types of bus structures including a memory unit bus or memory unit controller, a peripheral bus, an accelerated graphics port, a processing unit, or a local bus using any of a variety of bus architectures.

The electronic device 80 may also communicate with one or more external devices 600 (e.g., keyboard, pointing device, bluetooth device, etc.), one or more devices that enable a user to interact with the electronic device 80, and/or any device (e.g., router, modem, etc.) that enables the electronic device 80 to communicate with one or more other computing devices. Such communication may occur through an input/output (I/O) interface 550. An input/output (I/O) interface 550 is connected to the display unit 540. Also, electronic device 80 may communicate with one or more networks such as a Local Area Network (LAN), a Wide Area Network (WAN) and/or a public network, such as the Internet, through network adapter 560. As shown, network adapter 560 communicates with other modules of electronic device 80 over bus 530. It should be appreciated that although not shown, other hardware and/or software modules may be used in connection with electronic device 80, including, but not limited to, microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, data backup storage systems, and the like.

From the above description of embodiments, those skilled in the art will readily appreciate that the example embodiments described herein may be implemented in software, or may be implemented in software in combination with the necessary hardware. Thus, the technical solution according to the embodiments of the present application may be embodied in the form of a software product, which may be stored in a non-volatile storage medium (may be a CD-ROM, a U-disk, a mobile hard disk, etc.) or on a network, and includes several instructions to cause a computing device (may be a personal computer, a mobile terminal, etc.) to perform the branch prediction method according to the embodiments of the present application.

It should be noted that although in the above detailed description several modules or units of a device for action execution are mentioned, such a division is not mandatory. Indeed, the features and functions of two or more modules or units described above may be embodied in one module or unit in accordance with embodiments of the application. Conversely, the features and functions of one module or unit described above may be further divided into a plurality of modules or units to be embodied.

Furthermore, although the steps of the methods of the present application are depicted in the accompanying drawings in a particular order, this is not required to or suggested that the steps must be performed in this particular order or that all of the steps shown be performed in order to achieve desirable results. Additionally or alternatively, certain steps may be omitted, multiple steps combined into one step to perform, and/or one step decomposed into multiple steps to perform, etc.

From the above description of embodiments, those skilled in the art will readily appreciate that the example embodiments described herein may be implemented in software, or may be implemented in software in combination with the necessary hardware. Thus, the technical solution according to the embodiments of the present application may be embodied in the form of a software product, which may be stored in a non-volatile storage medium (may be a CD-ROM, a U-disk, a mobile hard disk, etc.) or on a network, comprising several instructions to cause a computing device (may be a personal computer, a mobile terminal, etc.) to perform the method according to the embodiments of the present application.

Other embodiments of the application will be apparent to those skilled in the art from consideration of the specification and practice of the application disclosed herein. This application is intended to cover any variations, uses, or adaptations of the application following, in general, the principles of the application and including such departures from the present disclosure as come within known or customary practice within the art to which the application pertains. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the application being indicated by the following claims.

Claims

1. A branch prediction method, characterized in that the method comprises:

Reading a first branch instruction, and predicting an execution result of the first branch instruction according to a first prediction information index to obtain a first prediction result, wherein the first prediction result includes a predicted jump direction and a predicted jump address of the first branch instruction;

Reading a second branch instruction and predicting an execution result of the second branch instruction to obtain a second prediction result, wherein the second prediction result includes a predicted jump direction and a predicted jump address of the second branch instruction, and the second branch instruction is a next branch instruction of the first branch instruction;

The second prediction result is updated according to the execution result of the first branch instruction.

2. The branch prediction method according to claim 1, wherein the reading the first branch instruction and predicting the execution result of the first branch instruction according to the first prediction information index to obtain the first prediction result comprises:

Obtaining the first prediction information index, and predicting a predicted jump direction of the first branch instruction according to the first prediction information index;

According to the instruction type of the first branch instruction, a predicted jump address of the first branch instruction is obtained.

3. The branch prediction method according to claim 2, wherein obtaining the first prediction information index and predicting the predicted jump direction of the first branch instruction according to the first prediction information index comprises:

Get the instruction address value and global history data value stored in the program counter register;

Concatenate the instruction address value with the global historical data value to obtain the first prediction information index;

Saturation count data is obtained based on the first prediction information index addressing, and the predicted jump direction of the first branch instruction is obtained according to the saturation count data.

4. The branch prediction method according to claim 1, wherein the step of reading the second branch instruction and predicting the execution result of the second branch instruction to obtain the second prediction result comprises:

generating a second prediction information index according to the predicted jump direction in the first prediction result and the first prediction information index;

Based on the second prediction information index, obtaining a predicted jump direction of the second branch instruction;

According to the instruction type of the second branch instruction, a predicted jump address of the second branch instruction is obtained.

5. The branch prediction method according to claim 4, wherein updating the second prediction result according to the execution result of the first branch instruction comprises:

After the execution of the first branch instruction is completed, obtaining the execution result of the first branch instruction;

The second prediction information index is updated according to the execution result of the first branch instruction.

6. The branch prediction method according to claim 5, wherein the execution result comprises an actual jump direction and an actual jump address of the first branch instruction, and after updating the second prediction result according to the execution result of the first branch instruction, the method further comprises:

If the actual jump direction of the first branch instruction is inconsistent with the predicted jump direction of the first branch instruction, a pipeline refresh operation is performed and the first branch instruction is re-executed.

7. A branch predictor, characterized in that the branch predictor comprises:

A branch prediction module, used for receiving a branch instruction and predicting the branch instruction to obtain a prediction result, wherein the prediction result is used to indicate whether the branch instruction jumps;

An instruction fetch module is used to read the branch instruction and send the branch instruction to the branch prediction module; receive the prediction result returned by the branch prediction module, and perform an instruction fetch operation of the next instruction fetch cycle according to the prediction result;

The instruction execution module is used to execute the branch instruction, obtain the execution result of the branch instruction, and send the execution result to the branch prediction module, so that the branch prediction module updates the prediction result according to the execution result.

8. The branch predictor according to claim 7, wherein the branch prediction module comprises a first-level prediction unit and a second-level prediction unit, and the branch prediction module stores the prediction result of the branch instruction through the first-level prediction unit and the second-level prediction unit;

The first-level prediction unit and the second-level prediction unit both include:

A branch direction prediction unit, the branch direction prediction unit is used to predict the jump direction of the branch instruction;

A branch address prediction unit, the branch address prediction unit is used to predict the jump address of the branch instruction;

The return stack is used to store the return address of the branch instruction.

9. The branch predictor according to claim 7, characterized in that the branch predictor further comprises:

A fast decoding module, one end of which is connected to the instruction fetch module, and the other end of which is connected to the branch prediction module, for receiving the branch instruction sent by the instruction fetch module, extracting the instruction information of the branch instruction, and sending the instruction information of the branch instruction to the branch prediction module.

10. An electronic device, comprising:

One or more processors, the processor comprising a branch predictor as claimed in any one of claims 7 to 9;

A storage device for storing one or more programs, when the one or more programs are executed by the one or more processors, enables the electronic device to implement the branch prediction method according to any one of claims 1 to 6.