JP2006031697A - Branch target buffer and usage - Google Patents

Abstract

A branch target buffer for storing a data entry related to a branch instruction and a method of using the same are provided.
A branch target buffer conditionally enables access to a data entry in response to a word line gating circuit associated with a word line in the branch target buffer. The word line gating circuit stores word line gating values derived from branch history data associated with the instruction. A branch prediction unit and a processor coupled to the branch target buffer are also provided along with a method for operating the branch target buffer. This enables implementation and operation of a processor that reduces power consumption, increases branch instruction processing speed, and reduces overall complexity.
[Selection] Figure 2

Description

  The present invention relates to a processor having a branch prediction unit, and more particularly to a branch target buffer in the branch prediction unit. The present invention is preferably used for a process having a pipeline structure. Here, the pipeline includes both a single structure and a superscalar pipeline structure.

  Early computers are designed to finish one instruction in a sequence of instructions before starting the next instruction. For decades, these designs, which were in the early days of major structural development, have developed widely in performance. Pipeline and superscalar structures are good examples of these developments.

  Process performance is also further developed by using caches. A cache is a memory component used to store or provide information that is often used. Here, “information” broadly includes all data and instructions. The cache provides information within a single clock cycle, unlike traditional memory access operations that require many cycles. A so-called branch target buffer (BTB) is a kind of processor cache.

  The usefulness of the branch target buffer is easily understood under the pipeline structure. “Pipelining (or speculative execution) is a term that generally relates to operating approach. With this motion approach, a sequence of instructions is processed using a series of functional or processing steps. Each processing stage normally performs the operations that make it up within a single clock period.

  Unlike a non-pipeline processor that completes each instruction before starting the next instruction, the pipeline process simultaneously processes many instructions in different processing stages. The pipeline stage may be arbitrarily designed by the designer, but generally, an instruction fetching stage, an instruction decoding stage, an instruction execution stage, and an execution analysis An execution resolution stage.

  The instruction fetch stage searches for instructions at the location where the instructions are stored (eg, main system memory or instruction queue). The fetched instruction moves to the instruction decoding stage. In the instruction decoding stage, an instruction address and / or an instruction operand is determined. The instruction moves from the instruction decoding stage to the instruction execution stage. In the instruction execution stage, one or more operations designated by the instruction are executed. The execution resolution stage generally includes writing-back the result (eg, result data) generated by the execution of the instruction to one or more registers or memory for later use.

  Instructions go from one pipeline stage to the next during a defined period. During the first period, the instruction fetch stage fetches the first instruction from the storage and aligns it in the associated hardware register for decoding. During the second period, the instruction fetch stage fetches the second instruction from the storage device and aligns it. At this time, in the instruction decoding stage, the first instruction is decoded. During the third period, the first instruction initiates an execution operation (eg, logic, mathematical, addressing, or indexing operation) at the execution stage. At this time, the instruction decoding stage decodes the second instruction, and the instruction fetch stage fetches the third instruction. The pipeline continues through execution analysis, and in this way the overall operating speed of the processor is much improved compared to the non-pipeline structure.

  In a superscalar structure, two or more instructions are processed or executed simultaneously. That is, a superscalar system has two or more execution (or decoder / execution) paths that can execute multiple instructions concurrently and independently in parallel. Scalar systems execute only one instruction per period while the instruction appears from a pipeline sequence of instructions, or otherwise executed in a non-pipelined manner. Executing many instructions simultaneously further improves process performance.

  Pipelining provides an obvious advantage in operations that can only predict whether the sequence of instructions to be executed is very linear. Unfortunately, in the vast majority of cases, the instruction sequence includes many instructions that can introduce non-sequential execution paths. So-called “branch instructions” (including, for example, jumps, returns, conditional branch instructions, etc.) have significant performance deficiencies unless an effective form of branch prediction is satisfied in the pipeline process. An unpredictable (error-predicted) branch instruction causes a performance defect by leaving the sequence of instructions currently pipelined in the process. If this occurs, the current pipeline sequence of instructions must be discarded or flushed, and a new sequence of instructions must be loaded into the pipeline. Pipeline flushes waste many clock cycles and generally slow the execution of the process.

  One way to improve the execution performance associated with a branch instruction is to predict the result of the branch instruction and immediately insert the predicted instruction into the pipeline after the branch instruction. If such a branch prediction mechanism is successfully implemented in the process, the performance deficiency associated with pipeline removal only occurs when the branch instruction result is predicted incorrectly. Fortunately, according to prior art and analysis, the result of a branch instruction is accurately predicted with a high level of certainty of almost 80%.

  As a result, several forms of conventional branch prediction mechanisms have been developed. One form of branch prediction mechanism is to store a large number of data entries using a branch target buffer. Each data entry is associated with a branch instruction. The branch target buffer stores a number of so-called “branch address tags”. Each branch address tag acts as an index that is classified for the corresponding branch instruction. In addition to the branch address tag, each branch target buffer entry further includes a target address, an instruction opcode, branch history information, and other possible data. In a process that uses a branch target buffer, the branch prediction mechanism monitors each instruction that enters the pipeline. Normally, the instruction address is monitored and the instruction address is aligned with the entry in the branch target buffer, where the instruction is recognized as a branch instruction. From the associated branch history information, the branch prediction mechanism determines whether a branch is easily taken or not. Branch history information typically monitors each branch instruction indexed in the branch target buffer and limits the stored data to branch history information related to whether or not the branch is going on To be determined by a state machine.

  One or more predicted instructions are inserted into the pipeline when the branch history information indicates that a branch instruction will occur. Traditionally, each branch target buffer data entry includes an opcode. The opcode is associated with a branch instruction that is evaluated in connection with the branch history information. As for this branch instruction, such an operation code is immediately inserted into the pipeline in accordance with a suitable instruction from the branch prediction mechanism. Each branch target buffer data entry also includes a “target address” associated with the branch instruction being evaluated. Again, in response to a suitable indication from the branch prediction mechanism, this target address is output by the branch prediction unit as a “predicted address” and used to fetch the next instruction in the instruction sequence.

  Processing of the branch instruction and its successive instructions proceeds through the pipeline for several cycles until the branch instruction is executed in the instruction execution stage. It is at this time that the accuracy of branch prediction is known. If the result of the branch instruction is predicted correctly, the branch target address has already been moved through the pipeline and process execution continues without stopping. However, if the result of the branch instruction is predicted incorrectly, the pipeline is removed and the correct instruction or instruction sequence is inserted into the pipeline. In superscalar processes with two or more pipelines that process multiple instruction sequences, the performance deficits caused by erroneous branch prediction are much greater. This is because in most cases, the number of instructions must be removed at least twice.

  FIG. 1 shows a branch target buffer 1 coupled to a branch prediction logic 2 and associated hardware. Branch target buffer 1 includes an address decoder 3, a memory array 4, and a sense amplifier 5. The address decoder 3 receives an instruction address from the instruction fetch unit, and selects a word line associated with the decoded instruction address. A word line voltage is applied to the selected word line.

  The memory array 4 is composed of a large number of memory cells, and each memory cell stores at least one data bit. Data entries, each containing a number of data bits, are conveniently stored in alignment, so that the selection of a particular word line in principle accesses the corresponding data entry. The data entry includes at least one data area that limits the branch address tag and another data area that limits the target address. The data entry for which the word line is selected is normally output from the memory array 4 via the sense amplifier 5.

  The branch address tag is transmitted from the sense amplifier 5 to the tag comparison register 6 to which the instruction address is input. The target address from the sense amplifier 5 is transmitted to the multiplexer 7. At this time, the address associated with the instruction sequence that is not branched is also transmitted. For example, in the case of a 32-bit instruction word processor, the program counter PC value is +4. One of the two inputs of the multiplexer is selected by the operation of the logic gate 9 for transmission to the instruction queue (PC MUX 8). The logic gate 9 is inputted with a result from the tag comparison register 6 and a take / not take instruction from the branch prediction logic 2.

  The conventional branch target buffer has many drawbacks. First of all, as in the structure shown in FIG. 1, the memory array of the branch target buffer is accessed by all branch instructions regardless of the result of the instruction. Access to the branch target buffer is usually associated with performing a read operation on the word line selected by the address decoder. Each read operation draws power from the power supply, provides power to a plurality of memory cells associated with the selected word line, and outputs data from the memory cells.

  In order to reduce power waste, prior art branch target buffers integrate enable lines into the memory array design. Such an example is disclosed in [Patent Document 1]. According to the aforementioned [Patent Document 1], the branch target buffer includes an enable line that enables or disables a word line driver associated with the memory array during a read operation. The wordline driver is enabled or disabled based on a taken or not-taken state that predicts whether a particular instruction is unlikely or accepted. The For example, if the taken / not-taken state for a particular instruction indicates a “strongly not taken” state, the enable line transitions to an inactive level and the memory array word line driver is disabled. Able to be.

  Unfortunately, the traditional method of reducing power during branch target buffer access operations is expensive. That is, the branch prediction mechanism that generates the enable signal requires time and resources to “pre-decoder” the instruction, determines branch history data and taken / not-taken state, and requires The level of the enable signal is changed accordingly.

  As instruction execution rates and instruction pipeline depths increase, the accuracy and speed of branch prediction becomes increasingly important. Recognizing this importance, many conventional processors employ extended pre-decoding methods. Thereby, all instructions are evaluated and branch instructions are identified. The branch history information is then retrieved or dynamically calculated in association with the branch instruction, so that it is currently evaluated and pre-decoded. Needless to say, these methods of predicting branch instruction behavior take a considerable amount of time and require the addition of a large amount of information resources. The additional delay and complexity in processing the instruction sequence is undesirable in the branch prediction mechanism. However, this is exactly what many conventional methods offer.

  Due to the power consumption problem, the design of considerable branch prediction mechanisms has become more complex. Modern processors place severe restrictions on power consumption. Laptop computers and mobile devices such as handsets and PDAs are examples of devices equipped with processors that consume minimal power.

  As described above, the branch target buffer is a cache type memory that stores a potentially large number of data entries. Accordingly, the branch target buffer has a memory array, preferably a volatile memory array, in its core portion. Such memory arrays, and particularly memory arrays that are large enough to store a large number of data entries, are power intensive. Access to the branch target buffer by the branch prediction mechanism implies a read operation on the branch target buffer memory array. Access operations to the branch target buffer are increasing. And some estimates suggest that read operations on the branch target buffer memory array account for over 10% of the total power consumption in conventional processors.

There is a need for better ways to implement the branch prediction mechanism. Conventional methods that require long real-time evaluation for branch instructions and / or dynamic retrieval and computation for branch history information are too complex and slow. Also, according to the conventional method, since the branch target buffer memory array is accessed continuously but inevitably, power is wasted.
US Patent US 5,740,417

  The technical problem of the present invention is to provide a branch target buffer and a method of use that can be easily applied to a superscalar processor. The decoder / execution unit of the superscalar processor includes a plurality of execution paths, and each execution path includes a decoder and an execution unit. By way of example, the processor is a vectoral processor or a single-instruction-multiple-data (SIMD) processor.

  A branch target buffer memory array according to an embodiment of the present invention for achieving the other technical problems described above includes a word line and a word line gating circuit associated with the word line. The word line gating circuit includes a memory circuit that stores a word line gating value.

  A memory array is provided to store data entries associated with the word lines. The word line gating circuit further includes a gating logic circuit. The gating logic circuit enables an access operation to the data entry according to the word line voltage applied to the word line and the word line gating value. The access operation is a read operation applied to the word line or a write operation applied to the word line.

  The memory array is composed of a volatile memory cell array. For example, the memory array is an SRAM array and the memory circuit is a 1-bit SRAM cell.

  The gating logic circuit includes a first logic gate that receives a write signal and a word line gating value to generate a first logic output, and a second logic that receives a first logic output and a word line voltage. A second logic gate for generating a signal.

  The branch target buffer memory array according to the present invention stores a data entry in response to a write operation and outputs a data entry in response to a read operation. The branch target buffer memory array includes a word line gating circuit that enables access to the data entry during a write operation, and a data entry during a read operation in response to the word line gating value stored in the word line gating circuit. And a word line gating circuit that conditionally enables access to. The word line gating circuit is a memory circuit for storing word line gating values, accepts a write signal and word line gating value input, enables access to data entries during a write operation, and a word And a gating logic circuit that conditionally enables access to the data entry during a read operation during a positive indication by a line gating value.

  The branch target buffer according to the present invention includes a memory array and a decoder. The memory array includes gate word lines. Each of the gate word lines includes a selected word line portion, a word line gating circuit including a memory circuit for storing a word line gating value, and a gate word line portion. The decoder is adapted to accept an instruction part and select one of the gate word lines according to the instruction part. The branch target buffer further includes a sense amplifier provided to receive a data entry from the gate word line selected by the decoder.

  The sense amplifier has a circuit for transmitting a word line gating value to each memory circuit associated with the word line and / or a circuit for transmitting a write signal to each word line gating circuit associated with the gate word line. including.

  The branch prediction unit according to the present invention includes a branch history unit for storing branch history data, a branch prediction logic for receiving an instruction address, providing a predicted address, and updating the branch history data, and an instruction address. Branch target buffer to which is input. The branch target buffer includes a memory array including gate word lines, each gate word line storing a data entry, and a word line with a memory circuit storing a word line gating value derived from the branch history data. Includes gating circuit.

  The branch history unit includes a state machine that calculates branch history data for an instruction by branching execution history.

  A branch prediction unit according to the present invention includes a branch history unit for storing branch history data, and a branch target buffer including a plurality of gate word lines, each gate word line corresponding to a corresponding word line gating circuit. It is accessed by the action of The branch target buffer is employed so as to output a data entry according to the instruction part received by the branch target buffer and the word line gating value derived from the branch history data.

  The processor according to the present invention includes an instruction fetch unit that receives an instruction and provides a corresponding instruction address, a branch prediction unit that receives the instruction address and provides a predicted address to the instruction fetch unit, and an instruction. An instruction decoder / execution unit that provides decoded instructions and provides updated addresses in response to execution of the decoded instructions.

  The branch prediction unit is a branch history unit for storing branch history data, a branch prediction logic for receiving an instruction address and an updated address, providing a predicted address, and updating the branch history data; A branch target buffer for inputting an instruction address and outputting a data entry. The branch target buffer includes a memory array including gate word lines, each gate word line being coupled to a corresponding word line gating circuit, the word line gating circuit being derived from the branch history data. It includes a memory circuit that stores values.

  The present invention provides a branch target buffer that enables implementation and operation of a processor that reduces power consumption, increases branch instruction processing speed, and reduces overall complexity. Power consumption by the processor is reduced by not performing read operations on the branch target buffer depending on conditions. In this connection, branch instruction processing within the processor is performed without delays caused by retrieving existing branch history information or by operations required for computation. This processor then has the advantage of reduced complexity in the component branch prediction unit.

  Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Such an embodiment is presented as an example. The actual scope of the invention is determined by the claims that follow.

  The term “processor” includes digital logic devices or systems that can execute or respond to a wide range of instruction sequences. The terms include central processing units (CPUs) microprocessors, digital signal processors (DSPs), reduced instruction set computer (RISC) processors, vector processors, single-instruction-multiple-data (SIMD) processors, ,including.

  Pipeline processors are particularly suitable for combining branch prediction units designed in accordance with the instructions of the present invention. Accordingly, multiple pipeline processors will be described in detail by way of example embodiments of the present invention, as well as various advantages provided by the present invention. FIG. 2 shows a block diagram of a pipeline processor according to the first embodiment.

  The processor 10 communicates data with the main memory 12 via the bus 14 using any one of a number of conventional data movement techniques. Assume that memory 12 stores a routine that includes one or more software programs and sequences of instructions. It is further assumed that the memory 12 stores data related to the sequence of instructions. This data includes input data used by the processor and result data stored in the memory 12 by the processor 10. The instruction returns from the memory 12 to the processor 10 in accordance with the address from the processor. The address indication may take many forms. However, the program counter PC is one of the well-known techniques, and instructs the processor 10 to store the next instruction to fetch the address into the memory 12 from the processor 10.

  As described above, a simple processor that indicates the next instruction retrieved from the memory is a branch instruction in which one or more instructions can specify a next address under one condition or another next address under another condition. When it is, it becomes very complicated. This is especially true for pipeline processors.

  Referring again to FIG. 2, the pipeline processor 10 generally includes an instruction fetch unit 13 that accepts an instruction IR from the memory 12 and provides the predicted address to the memory 12. The instruction fetch unit 13 issues an instruction to the instruction decoder unit 15. The instruction decoder unit 15 decodes the instructions and generally provides the execution unit 17 with the operational code portion of the instructions. The decoded instruction (or instruction portion) received from the execution unit 17 initiates one or more operations within the execution unit. Such an operation typically produces result data that is written-back to the memory 12 or further locations within the system.

  In addition to providing instructions to the instruction decoder 15, the instruction fetch unit 13 provides instruction parts to the branch prediction unit 19. This instruction portion typically includes an instruction address, but also includes other information. Branch prediction unit 19 also receives a “next address” indication from execution unit 17. That is, upon execution of an instruction, the next instruction executed in the sequence of instructions is actually known (ie, the condition of the branch instruction is determined). Therefore, the next address indication is fed back to the branch prediction unit 19. Using this information, branch prediction unit 19 determines whether the previously predicted next instruction is actually the correct next instruction. The next address indication from the execution unit 17 is typically an instruction address.

  If the next address indication from the execution unit 17 matches the previously predicted instruction address (eg, a “HIT” condition), the processor continues to progress according to the instruction pipeline sequence. However, if the next address indication is different from the previously predicted instruction address (eg, “MISS” condition), the processor removes the pipeline and loads the instruction indicated by the next address indication.

  The comparison between the previously predicted instruction address and the next address indication is preferably performed in the branch prediction unit 19. As will be described later in some additional description, branch prediction unit 19 is also provided within pipeline processor 10 that provides the predicted address to instruction fetch unit 13.

  Before continuing with a more detailed description of the preferred embodiments, it must be described in detail that the present invention is also particularly well suited for superscalar processors. A very simple superscalar processor is shown in FIG. Here, the memory 12 again provides instructions and / or data to the superscalar processor via the bus 14. The branch prediction unit 39 and the instruction fetch unit 33 generally operate as described above. However, the instruction fetch unit 33 provides instructions to the multiple execution paths 34, 35 and 36. Analogously to this, each execution path 34, 35, 36 provides a next address indication to the branch prediction unit 39.

  In the superscalar processor example, three execution paths are shown. However, this number is almost typical and is an arbitrarily chosen number. Further, each execution path is characterized by a decoder / execution unit combined to accept instructions from the joint instruction fetch unit.

  The hardware and functional boundaries associated with typical stages of the processor are generally a matter of routine design design choices by the designer. For example, the decoding and execution functions are fragmented parts of hardware (eg, IC), but can be easily executed with multiple complex ICs. Decoding and / or execution can be performed in hardware, software, firmware, or a combination of these three general platform configurations. Similarly, the hardware and functional boundaries between the instruction fetch unit, instruction decoder unit, and / or branch prediction unit in this embodiment are described.

  Regardless of the type of combined processor, the present invention preferably includes a branch prediction unit that includes several forms of branch prediction logic, several mechanisms for storing data entries associated with branching instructions. And provide several forms for branch history data storage and / or computation. FIG. 4 is a block diagram for explaining the branch prediction unit 19 shown in FIG. 2 in more detail.

  In FIG. 4, the branch prediction logic 20 provides the predicted address to the instruction fetch unit 13. Branch prediction logic 20 receives instruction addresses from instruction fetch unit 13 and generally exchanges information with branch target buffer 22 and branch history unit 24. These three functional blocks are selected for explanation. The present invention is not limited to a specific grouping of components in terms of hardware. For example, in a practical implementation of the present invention, the data storage functionality associated with the branch history unit 24 may be combined in a memory array associated with the branch target buffer 22 or a memory device associated with the branch prediction logic 20. Similarly, the computational functionality associated with the branch history unit 24 can be implemented using hardware or software resources provided by the branch prediction logic 20.

  More specifically, branch prediction logic 20 receives an instruction portion, usually an instruction address (eg, current program counter PC value) from instruction fetch unit 13, after which the processor is associated with the instruction. Predict whether to branch to the target address or to execute the next instruction in the sequence of instructions. The term “prediction” generally refers to an output that is theoretical or computational. This is made by the branch prediction logic associated with the received instruction address and preferably associated with the branch history information associated with the input instruction address. Accordingly, the branch prediction logic 20 has many specific combinations of logic structures, calculation circuits, data registers, comparison circuits, and / or similar hardware resources, and embedded controller software for driving the hardware resources. Consists of

  As previously mentioned, the branch prediction unit 20 provides a write signal to the branch target buffer 22. The write signal controls the write operation within the branch target buffer 22. “Read” and “write” are terms generally used in the operation of a normal memory device such as SRAM or DRAM.

  The decision of the branch prediction logic 20 for branching to the target address is limited to the “Taken” condition. The decision of the branch prediction logic 20 that does not branch is limited to “Not-Take” conditions. The branch prediction unit 20 responds to the state of the branch history data associated with the instruction indicated by the input instruction address. The condition of take or not-taken is predicted.

  The branch history unit 24 serves to provide branch history data to the calculation, storage and / or branch prediction logic 20. Branch history data is any useful data related to the prediction between taken and not taken due to a dropped instruction. Many conventional algorithms and similar methods have been proposed that propose other methods for calculating data indicating whether a branch instruction is taken or not. The present invention is suitable for using any of these similar methods as long as the algorithm or method provides an accurate prediction of branching command behavior.

  Storage and provision for the branch of history data is provided by a memory element associated with the branch history unit. Each branch instruction having a corresponding data entry stored in the branch target buffer has several forms of branch history data stored in the branch history unit. (However, as described above, branch history data can be stored in the branch target buffer along with the corresponding data entry.) The branch history data for an instruction ensures that the instruction is actually branched. To determine the frequency, it is determined experimentally by one or more programs containing instructions. Then, the branch history data determined first is stored in the branch history unit for the next criterion. The initially determined branch history data is updated with each subsequent execution of the instruction. In this way, the simultaneous branching action is used to update currently existing branch history data. Of course, the branch history data need not be predetermined in any way. However, it can occur “on-the-fly” corresponding to actual instruction execution.

  Regardless of when and how it is updated, branch history data can easily be determined using a state machine. The complexity and design of state machines that meet requirements is a matter of routine design choice. However, as described above, the present invention is used as a calculation part of the 2-bit up / down saturation counter branch history unit 24. The operation and use of the 2-bit up / down saturation counter is illustrated in the sequence diagram of FIG. Here, the 2-bit branch history data value is incremented or decremented by execution branching instructions relative to the instruction taking or not taking during actual execution. This branch history data suggests a specific degree of “taken-ness” for the instruction.

  For example, a previous non-taken branch instruction moves from “strongly not take” to a “weakly not take” state. Such a state change is indicated by increasing the corresponding branch history data value from “00” to “01”. An instruction that previously had a “strongly taken” state is changed to a “weakly taken” state by decreasing the corresponding branch history data value.

  In the preferred embodiment, the two bits appear to be sufficient for most applications to accurately predict the likelihood that an instruction will be taken. However, this is not true for all applications. The branch history data requires a larger number of bits in order to accurately perform the take / not-taken determination. Thus, the specific identification of branch history data is a matter of design selection by selecting an algorithm that calculates the branch history design and / or by a state machine that executes the selected algorithm.

  The branch target buffer shown in FIG. 4 will be described in more detail with reference to FIG. Here, the decoder 43 receives an instruction part, preferably an instruction address, and selects a word line indicated by the decoded instruction part. Like a conventional branch target buffer, the memory array 40 is expanded from a decoder 43 of a plurality of word lines. However, the characteristics, operation and implementation of the word line will vary with the present invention. A “gate word line” is used in connection with some embodiments, which is a word line limited by the present invention.

  Memory array 40 is preferably an array of volatile memory cells such as SRAM cells. However, other forms of memory can be used. Like conventional branch target buffer memory arrays, the memory array of the present invention preferably stores a plurality of data entries. Here, each data entry corresponds to an instruction, and preferably includes a branch address tag and a target address. Other forms of data are associated with each data entry. However, generally speaking, some form of branch address tag and target address is required.

  The aforementioned gate word line is shown in FIG. A gate word line generally includes a combination of a word line 70 and a word line gating circuit 60. As described in FIG. 6, the word line gating circuit is preferably in a one-to-one relationship with the corresponding word line. The plurality of word line gating circuits are preferably configured in a column form within the memory array 40. With this structure, each word line gating value stored in the word line gating circuit using the conventional writing technique can be easily updated. In the preferred embodiment, memory array 40 is comprised of an SRAM array and a word line gating circuit, which is comprised of a memory circuit formed of single bit SRAM cells.

  Regardless of the actual configuration of the word line gating circuit, each word line gating circuit has a corresponding word based on the “word line gating value” derived from the branch history data for the instruction associated with the word line. It has a function to make the line accessible or impossible. That is, each branch instruction portion input in the branch target buffer 22 selects a corresponding word line through the operation of the decoder 43. This word line stores a data entry including a target address associated with a branch address tag and a branch instruction portion inputted. The corresponding word line selected by the decoder 43 is a gate word line. That is, the gate word line can only be accessed through the operation of the associated word line gating circuit. The operation of the word line gating circuit is controlled by the word line gating value stored in the word line gating circuit. This word line gating value is derived from branch history data associated with the instruction.

  For branching each instruction, the wordline gating value is preferably derived from branch history data associated with the instruction. A typical guidance method is described in the embodiment described above. Many different methods may be used to derive word line gating values from branch history data. These methods vary depending on the characteristics of the branch history data, the size of the word line gating value, and / or the structure of the word line gating circuit and the memory circuit constituting the word line gating circuit.

  As described with respect to FIG. 5, assuming 2-bit branch history data and a single bit memory cell associated with each word line gating circuit, the word line gating value that satisfies the requirement is the first of the branch history data. Easy to navigate with important bits. In this example, the logic value of “1” for the most important bit is “strongly taken” or “weakly taken” for the instruction. The logic value “0” for the most important bit is “weak not-taken” or “strong not-taken” state for the instruction. By storing this bit value in a single bit memory cell associated with the word line gating circuit, an accurate indication to the extent that it can accept the take-ness instruction level is to control access to the gate word line. Used.

  Referring to FIG. 7 again, the word line 70 is selected by the decoder, and a word line voltage is applied to the word line 70. Usually, such an applied word line voltage increases the voltage potential over the entire length of the word line. However, in the present invention, the application of the word line voltage through the selected word line length is conditionally enabled by the associated word line gating circuit 60. The word line gating circuit 60 is preferably composed of a memory circuit 61 and a gating logic circuit 62.

  The size of the memory circuit 61 varies depending on the stored word line control value. In the above description, a single bit is stored. However, any size word line control value can be stored and used to control access to the gate word line. In FIG. 7, an SRAM memory cell including two P-type transistors and four N-type transistors is used in a memory circuit that stores a word line gating value.

  The logic value (“1” or “0”) of the stored word line gating value is used as an input to the gating logic circuit 62. Specifically, the word line gating value is applied to the first logic gate 82 as one input. The first logic gate 82 also receives a write signal from the branch prediction logic. Since the first logic gate 82 is an OR type logic gate, if at least one input has a logic value of “1”, its output becomes a first logic output having a logic value of “1”. . The first logic output is applied to the second logic gate 80 according to the value of the word line voltage. Since the second logic gate 80 is an AND type logic gate, the second logic output becomes “1” only when all the inputs are “1”. In an embodiment, the second logic output from the second logic gate 80 serves as the word line voltage for the portion of the word line 70 “after” the operation of the word line gating circuit 60.

  Thus, the word line 70 has two different parts. The selected word line portion 71 can be selected by the decoder according to the instruction address, and the gate word line portion 72 can be accessed only through the operation of the word line gating circuit. In the embodiment, the selected word line portion is provided to receive a word line voltage from the decoder. This word line voltage is used as an input to the word line gating circuit associated with the word line 70. This word line voltage, which is conditionally enabled by the word line gating value stored in the word line gating circuit 60, passes to the corresponding gate word line portion 72.

  The word line voltage that conditionally passes (or “gates”) from the selected word line portion to the corresponding gate word line portion is preferably only relevant to the read operation applied to the word line. That is, the word line gating value is a location that indicates that branch history data predicting a branch instruction is accepted, and a read operation applied to the selected word line is enabled. However, the word line gating value is where branch history data predicting a branch instruction is not accepted, and read operations applied to the selected word line are not enabled.

  Such a conditional “access operation” possibility is generally unnecessary during a write operation in which the data entry stored in the memory array 40 is updated. Thus, when the gate word line is selected by the decoder, application of the write signal to the first logic gate allows immediate access to the gate word line. That is, the write operation proceeds regardless of the word line gating value. In this way, conditional read and unconditional write operations are efficiently facilitated with minimal hardware resources.

  The branch target buffer shown in FIG. 6 also includes a sense amplifier 45 that receives a data entry from the memory cell array 40 during a read operation. As described above, the sense amplifier 45 is also used to load a word line control value (WLCV) to each memory circuit associated with the word line gating circuit.

  The operation method of the branch prediction unit according to the present invention will be described with reference to FIG. Data entries corresponding to a plurality of branch instructions are stored in the memory array of the branch target buffer (100). Branch history data for each instruction is developed using a suitable algorithm (101). The respective word line gating value (WLGV) for each instruction is derived from the branch history data (102) and then stored in the memory circuit of the corresponding word line gating circuit (103).

  The branch prediction unit in which the data entry and the stored wordline gating value are stored easily accepts an instruction part such as an instruction address (104). The instruction part is decoded (105) and the corresponding word line is selected (106). By selecting a word line, the stored word line gating value conditionally determines whether the gate portion of the word line is accessed. A “positive” word line gating value indication (eg, an instruction to cause a branch instruction to be taken) enables word line access (108) and outputs a corresponding data entry (109). A “negative” word line gating value indication (eg, an indication that a branch instruction is not taken) does not cause further access or output by the memory array (110). The negative and positive indications described above generally correspond to a taken / not taken state for a particular instruction.

  The branch prediction unit according to the present invention can accept branch instructions and conditionally enable access to corresponding data entries stored in the branch target buffer. Data entries are read from the branch target buffer. In the branch target buffer, the corresponding branch history data predicts that a data entry will be required. Instructions that are unlikely to “take” a branch do not enable read operations on the branch target buffer. As a result, power consumed by unnecessary reading operations is stored.

  For example, FIG. 9 shows the result of an EEMBC benchmark simulation. This uses a branch prediction unit designed in accordance with the present invention. A series of benchmark routines along the horizontal axis shows a comparison between the predicted ratio of branch instructions and the actual ratio of branch instructions. This particular simulation shows that about 40% of the branch prediction is associated with the Not-Taken state. Thus, the power consumption of the branch target buffer associated with the branch target buffer memory array read operation can be reduced to 40%.

  However, the present invention does not provide power conservation at the expense of increased complexity and reduced operating speed. As instructions enter the branch prediction unit, they are processed by an immediate decoder. When enabled, the corresponding data entry output is generated immediately. There is no delay in processing the instruction to precode it and retrieve or calculate branch history data for the instruction and issue a signal to enable / disable the read operation corresponding to the branch target buffer memory array. The present invention does not require complex additional circuitry or functions to conditionally enable read operations on the branch target buffer memory array.

  Instead, the corresponding word line gating values each wait for instruction processing in the branch target buffer. Application of a word line gating value within a simple word line gating circuit enables or disables access to a word line storing a data entry corresponding to an incoming instruction. The word line gating value can be easily and accurately updated in the word line gating circuit by executing each instruction.

  On the other hand, in the detailed description of the present invention, specific embodiments have been described, but various modifications can be made without departing from the scope of the present invention. Therefore, the scope of the present invention should not be determined by limiting to the above-described embodiments, but should be determined not only by the claims described below but also by equivalents to the claims of this invention.

FIG. 5 is a diagram illustrating a branch target buffer and related components necessary for outputting a data entry from the branch target buffer memory array. FIG. 3 is a block diagram illustrating a processor according to an embodiment of the present invention. 1 is a block diagram illustrating a superscalar processor according to an embodiment of the present invention. FIG. 3 is a block diagram showing a branch prediction unit shown in FIG. 2. FIG. 6 is a state diagram illustrating states of a state machine that can be included in a branch history unit according to an embodiment of the present invention. FIG. 3 is a block diagram illustrating a branch target buffer memory array according to an embodiment of the invention. FIG. 4 is a circuit diagram illustrating a gate word line structure according to an embodiment of the present invention. FIG. 6 is a flowchart illustrating an operation method of a branch prediction unit according to the present invention. It is a flowchart which shows the benchmark simulation result about the branch prediction unit by this invention.

Explanation of symbols

10: processor 12: main memory 13: fetch unit 15: instruction decoder unit 17: execution unit 19: prediction unit

Claims (53)

A branch target buffer memory array,
A word line and a word line gating circuit associated with the word line;
The memory array, wherein the word line gating circuit includes a memory circuit for storing a word line gating value.   The memory array of claim 1, wherein the memory array is provided to store a data entry associated with the word line.   The memory array of claim 2, wherein the word line gating circuit further includes a gating logic circuit.   The memory of claim 3, wherein the gating logic circuit activates an access operation to the data entry in response to a word line voltage applied to the word line and the word line gating value. array.   The memory array of claim 4, wherein the gating logic circuit is responsive to a write signal.   The memory array according to claim 4, wherein the access operation is a read operation applied to the word line.   The memory array according to claim 5, wherein the access operation is a write operation applied to the word line.   The memory array according to claim 1, wherein the memory array includes a nonvolatile memory cell array.   The memory array according to claim 8, wherein the memory array is an SRAM array.   The memory array of claim 9, wherein the memory circuit is a 1-bit SRAM cell.   3. The memory array according to claim 2, wherein the data entry includes a branch target tag and a branch address. The memory circuit includes a 1-bit SRAM cell that stores the word line gating value;
The gating logic circuit receives a first logic gate that receives the write signal and the word line gating value to generate a first logic output, and receives the first logic output and the word line voltage. 6. The memory array of claim 5, further comprising a second logic gate that generates a second logic signal.   6. The memory array of claim 5, wherein the word line includes a selected word line portion to which the word line voltage is input and a corresponding gate word line portion.   The memory array of claim 13, wherein the selected word line portion and the gate word line portion are electrically connected through the word line gating circuit.   The memory array of claim 12, wherein the word line includes a selected word line portion to which the word line voltage is input and a corresponding gate word line portion. The selected word line part and the gate word line part are electrically connected through the word line gating circuit,
The memory array of claim 15, wherein the second logic signal includes a word line voltage applied to the gate word line portion. A branch target buffer memory array that stores data entries in response to a write operation and outputs the data entries in response to a read operation;
Enabling access to the data entry during the write operation;
A memory array, comprising: a word line gating circuit that conditionally enables access to the data entry during the read operation period in response to a word line gating value stored in the word line gating circuit. The word line gating circuit is
A memory circuit for storing the word line gating value;
Accepts a write signal and the word line gating value as input, enables access to the data entry during the write operation period, and accesses the data entry during the read operation period when a positive instruction is given by the word line gating value. The memory array of claim 17, further comprising a conditionally enabled gating logic circuit. In the gating logic circuit, a word line voltage is input to the input,
19. The memory array according to claim 18, wherein access to the data entry is conditionally enabled during the read operation period when a positive instruction is given by the word line gating value and the word line voltage.   The memory array of claim 19, wherein the memory array comprises an array of volatile memory cells.   The memory array of claim 20, wherein the memory array is an SRAM array and the memory circuit is a 1-bit SRAM cell. A branch target buffer,
The branch target buffer includes a memory array and a decoder,
The memory array includes gate word lines, and each of the gate word lines includes
Selected word line part,
A word line gating circuit including a memory circuit for storing word line gating values; and a gate word line portion;
The branch target buffer is configured to receive an instruction part and select one of the gate word lines in response to the instruction part.   The branch target buffer according to claim 22, wherein the decoder is provided to apply a word line voltage to a selected word line portion of a gate word line selected by the decoder.   24. The branch target buffer of claim 23, wherein the word line gating circuit further comprises a gating logic circuit that receives the word line voltage and the word line gating value as inputs.   The word line gating circuit is provided to conditionally enable an access operation to a gate word line portion of a gate word line selected by the decoder in response to the word line voltage and the word line gating value. 25. The branch target buffer of claim 24.   The branch target buffer according to claim 25, wherein the access operation is a read operation. The word line gating circuit is provided to accept a write signal at an input;
The branch target buffer according to claim 25, wherein the access operation is a write operation. The memory array includes an SRAM array, a memory circuit including a 1-bit SRAM cell,
And including the gating logic circuit,
The gating logic circuit is
An OR gate that accepts the write signal and the word line gating value as input and outputs a first logic signal;
27. The branch target buffer of claim 26, further comprising an AND gate that receives the word line voltage and the first logic signal as input and outputs a second logic signal.   30. The branch target buffer of claim 28, wherein the second logic signal is a word line voltage applied to the gate word line portion of the gate word line selected by the decoder.   The branch target buffer according to claim 22, further comprising a sense amplifier adapted to receive a data entry from the gate word line selected by the decoder.   The branch target buffer of claim 30, wherein the sense amplifier includes a circuit for transmitting a word line gating value to each memory circuit associated with the word line. The memory array includes an SRAM array;
32. The branch target buffer of claim 31, wherein the memory circuit includes a 1-bit SRAM cell for accepting a word line gating value. The word line gating circuit is
An OR gate that receives the write signal and the word line gating value from the 1-bit SRAM cell as an input and outputs a first logic signal; and the word line voltage and the first logic signal as an input The branch target buffer of claim 32, further comprising an AND gate that receives and outputs a second logic signal. A branch prediction unit,
A branch history unit for storing branch history data;
A branch prediction logic for inputting an instruction address, providing a predicted address, and updating the branch history data;
A branch target buffer to which the instruction address is input,
The branch target buffer includes a memory array including gate word lines, each gate word line storing a data entry and a word line including a memory circuit storing a word line gating value derived from the branch history data. A branch prediction unit comprising a gating circuit.   The branch prediction unit of claim 34, wherein the branch prediction logic provides a write signal to the branch target buffer.   36. The branch prediction unit of claim 35, wherein the branch history unit includes a state machine that calculates branch history data for an instruction according to a branching execution history.   The branch prediction unit according to claim 36, wherein the branch history unit includes a branch history table that stores branch history data, and the state machine includes a 2-bit up / down saturation counter.   The memory array includes an SRAM array, the memory circuit includes 1-bit SRAM cells, and the word line gating value includes a single data bit derived from the branch history data. Item 35. The branch prediction unit according to Item 34. The branch target buffer is:
A decoder for receiving the instruction address and selecting a gate word line in response to the instruction address;
A sense amplifier provided with a circuit for transmitting a word line gating value to each word line gating circuit provided to receive a data entry from the selected gate word line and linked to the gate word line; The branch prediction unit according to claim 38, further comprising: A branch prediction unit,
A branch history unit for storing branch history data;
A plurality of gate word lines, each gate word line including a branch target buffer accessed by operation of a corresponding word line gating circuit;
The branch target buffer is provided to output a data entry in response to an instruction part received by the branch target buffer and a word line gating value derived from the branch history data. unit.   41. The branch prediction logic of claim 40, further comprising branch prediction logic for receiving the instruction portion and providing a predicted address in response to the data entry output by the branch target buffer. unit.   42. The branch prediction unit of claim 41, wherein the branch prediction logic is provided to provide a write signal to the branch target buffer.   The branch prediction unit according to claim 41, wherein the branch history unit includes a branch history table that stores the branch history data.   The memory array includes an SRAM array, the memory circuit includes a 1-bit SRAM cell, and the word line gating value includes a single data bit derived from the branch history data. The branch prediction unit according to claim 43. A processor,
An instruction fetch unit into which an instruction is input and providing a corresponding instruction address;
A branch prediction unit that receives the instruction address and provides the predicted address to the instruction fetch unit;
An instruction decoder / effective unit that receives the instruction, provides a decoded instruction, and provides an updated address in response to execution of the decoded instruction;
The branch prediction unit is:
A branch history unit for storing branch history data;
A branch prediction logic for receiving the instruction address and the updated address, providing the predicted address, and updating the branch history data;
A branch target buffer for receiving the instruction address and outputting a data entry;
The branch target buffer includes a memory array including gate word lines, each gate word line is connected to a corresponding word line gating circuit, and the word line gating circuit is a word line derived from the branch history data. A processor comprising a memory circuit for storing a gating value.   The processor of claim 45, wherein the decoder / execution unit includes a plurality of execution paths, each execution path including a decoder and an execution unit.   The processor of claim 46, wherein the processor is a superscalar processor.   48. The processor of claim 47, wherein the processor is a vector processor or a single-instruction-multiple-data processor.   The processor of claim 45, wherein the branch prediction logic provides a write signal to the branch target buffer.   50. The processor of claim 49, wherein the branch history unit includes a state machine that calculates branch history data for instructions by branching execution history.   51. The processor of claim 50, wherein the branch history unit includes a branch history table that stores the branch history data.   The memory array includes an SRAM array, the memory circuit includes a 1-bit SRAM cell, and the word line gating value includes a single data bit derived from the branch history data. 46. The processor of claim 45. The branch target buffer is:
A decoder that receives the instruction address and selects a gate word line in response to the instruction address;
A sense amplifier having a circuit for inputting the data entry from the selected gate word line and transmitting a word line gating value to each word line gating circuit associated with the gate word line; 53. The processor of claim 52, comprising:

Images