JP2007249710A - Local slack prediction method, local slack prediction mechanism - Google Patents

Abstract

A local slack prediction method and a local slack prediction mechanism capable of predicting local slack with a simpler configuration.
An instruction i0 executed by a processor is executed with an execution latency increased by an amount corresponding to the predicted slack of the instruction i0, and at the time of executing an instruction estimated that the predicted slack has reached target slack. The predicted slack is gradually increased for each execution of the instruction i0 until the behavior of is observed, and finally the predicted slack is matched with the target slack to predict the local slack.
[Selection] Figure 1

Description

  The present invention relates to a method for predicting local slack of instructions executed by a processor, and a mechanism for performing the prediction.

  In recent years, many researches have been made on techniques for speeding up microprocessors and reducing power consumption by scheduling execution of instructions using information on critical paths. A critical path means that the execution latency of an instruction on the path is increased even in one cycle, that is, if the number of cycles from the start of instruction execution until the result becomes available, the number of execution cycles of the entire program increases. This instruction sequence has a decisive influence on the execution time of the program. However, depending on the critical path information, it is only possible to classify instructions in two ways, whether or not they are on the critical path. Also, the number of instructions present on the critical path is usually absolutely smaller than the number of instructions that are not. For this reason, when instructions are classified using critical path information, and the instruction processing systems are divided according to the classified categories, the load balance between the processing systems is deteriorated.

  Therefore, it is considered that instruction slack information is used instead of critical path information. Instruction slack means the number of cycles of instruction execution latency that can be increased without increasing the number of execution cycles of the entire program.

  Here, instruction slack will be described with reference to FIG. FIG. 2B shows the execution mode of the program illustrated in FIG. This program is composed of seven instructions i0 to i6. Note that “i0” to “i6” indicate the values of the program counter corresponding to each instruction. In the figure, the length of the node corresponding to each instruction i0 to i6 represents the execution latency of the instruction. In the figure, the execution latency of the instructions i1 and i4 is 2 cycles, and the other instructions are 1 cycle. It has become. An arrow indicates a dependency between instructions. For example, the instruction i3 depends on the instruction i0 and the instruction i2. Incidentally, the instructions i 1 → i 2 → i 4 → i 6 are critical buses.

  Here, the slack of the instruction i0 is considered. When the execution latency of the instruction i0 is increased by 3 cycles, the execution of the instruction i3 and the instruction i5 that depend directly or indirectly on the instruction i0 is delayed by one cycle. However, even in that case, the instruction i5 is executed at the same time as the instruction i6 executed last in the program, and the number of execution cycles of the entire program does not increase. However, if the execution latency of the instruction i0 is further increased, the execution of the instruction i5 is delayed from the instruction i6. Therefore, the slack of the instruction i0 is “0-3”. On the other hand, even if the execution latency of the instruction i3 or the execution latency of the instruction i5 is increased by one cycle alone, the number of execution cycles of the entire program does not increase. Since the number increases, the slack of these instructions i3 and i5 is “0 to 1”. Of course, the slacks of the instructions i1, i2, i4, i6 on the critical path are all “0”.

  If you know the slack of these instructions, you can see how much the instruction execution latency can be increased without affecting the execution time of the entire program. This makes it possible to classify the instructions more finely. For example, the instructions can be classified into three categories by classification such as an instruction having a maximum slack value of “0”, an instruction of “1-2”, and an instruction of “3” or more.

  Even when the instructions are divided into two categories, for example, it is possible to classify the instructions such as an instruction having a maximum slack value of “0 to 2” and an instruction having “3” or more, so the above critical path is used. It is possible to alleviate the deviation in the number of instructions between categories as in the case.

  In order to make maximum use of such slack information, it is necessary to know the maximum slack value of each instruction, that is, global slack. However, global slack changes dynamically as the execution latency of dependent instructions increases. For example, the global slack of the instruction i5 described above is “1” in the state of FIG. However, if the execution latency of the instruction i0 is increased by 3 cycles, if the execution latency of the instruction i5 is increased even by one cycle, the number of execution cycles of the entire program is increased. Therefore, the global slack of the instruction i5 at this time is “0”. In order to determine global slack, the influence of an increase in instruction execution latency on the final number of execution cycles of a program must be examined while the program is being executed. Therefore, the use of global slack is very difficult to realize.

  Therefore, it is considered to use local slack instead of global slack of instructions. The local slack of an instruction means not only the number of execution cycles of the entire program but also the maximum value of slack that does not affect the execution of subsequent instructions. For example, in the state of FIG. 12B, even if the execution latency of the instruction i0 whose global slack is “3” is increased by 3 cycles, the number of execution cycles of the entire program does not increase, but the instructions i3 and i5 depending on it. Execution will be delayed. On the other hand, even if the execution latency of the instruction i0 is increased by 2 cycles, there is no delay in the execution of the subsequent instructions i3 and i5. Therefore, the local slack of the instruction i0 is “2”. Such local slack of an instruction can be obtained simply by paying attention to the influence of an increase in the execution latency of the instruction on subsequent instructions depending on the instruction.

  Conventionally, as a method for predicting the local slack of such an instruction, a difference between the time when an instruction defines register data or memory data and the time when the defined data is first referenced is determined. A method has been proposed in which local slack is obtained and used as a predicted value of local slack at the next execution of the same instruction.

  FIG. 13 shows a hardware configuration of a local slack prediction mechanism for realizing such a conventional prediction method. As shown in the figure, the processor 50 adopting this prediction mechanism includes a fetch unit 11, a decode unit 12, an instruction window (I-win) 13, a register file (RF) 14, and an execution unit (EU) 15. And a reorder buffer (ROB) 16. On the other hand, as a local slack prediction mechanism, a register definition table 51 and a memory definition table 52 that store and hold the time when an instruction defined register data and memory data, respectively, and prediction of local slack for each obtained instruction A slack table 53 for storing and holding values is provided. The register definition table 51 uses a physical register number as an index, and each index records and holds an instruction that defines data in a register corresponding to the physical register number (an index portion of an instruction address) and the time of the definition. . The memory definition table 52 uses the memory reference address as an index, and each index records and holds an instruction that defines data at the reference address (an instruction address index part) and the time of the definition. The slack table 53 uses an instruction address as an index, and each index stores and holds a local slack operation value of the instruction at the time of previous execution. In addition to these tables, the prediction mechanism is also provided with a computing unit 54 for obtaining the difference between the data definition time and the reference time.

  Here, the local slack prediction operation of the conventional prediction mechanism will be described by taking the instruction i0 of FIG. 12B as an example. When the instruction i0 writes data to the register (memory), the current time “0” is recorded in the register definition table 51 (memory definition table 52) together with “i0” itself (address and index of the instruction). Thereafter, when the instruction i3 uses the data, the instruction i0 defining the data and the defined time “0” of the data are read from the register definition table 51 (memory definition table 52). Then, the difference between the current time “3” and the definition time “0” of the read data is obtained by the computing unit 54, and “2” obtained by subtracting “1” from the value is the previous execution instruction It is stored in the slack table 53 as i0 local slack. When the instruction i0 is fetched again, the slack table 53 is referred to, and “2” stored in the entry corresponding to i0 is used as the predicted value of local slack of the instruction i0.

  According to such a conventional prediction method, it is possible to predict local slack with some accuracy, but in addition to the slack table, two definition tables and a calculator are required, and the hardware cost of the prediction mechanism is required. Is extremely expensive. In parallel with the execution of the program, the definition table must be referenced / updated and the time subtraction must be performed at a high speed, and the increase in power consumption due to the operation of the prediction mechanism may be difficult to ignore.

  The present invention has been made in view of such a situation, and a problem to be solved is to provide a local slack prediction method and a prediction mechanism capable of predicting local slack with a simpler configuration. It is in.

  In order to solve the above-mentioned problem, in the local slack prediction method according to claim 1 of the present invention, instructions executed by the processor are executed by the amount of predicted slack that is a predicted value of local slack of the instruction. It is executed with increased latency, and based on the behavior at the time of execution of the instruction, it is estimated whether or not the predicted slack has reached target slack that is an appropriate value of local slack at present, and has reached. The estimated slack is gradually increased every time the instruction is executed until the above estimation is made.

  In the prediction method, the predicted value of local slack (predicted slack) of an instruction is gradually increased every time the instruction is executed. If the predicted slack is increased in this way, the value eventually reaches the appropriate value (target slack) of the current local slack. On the other hand, the arrival of predicted slack to the target slack is estimated from the behavior of the processor at the time of execution of the instruction, and the increase in predicted slack is stopped at the time when it is estimated that the arrival has been reached. As a result, local slack can be predicted without directly calculating predicted slack.

In addition, the estimation of the arrival of predicted slack to the target slack as described above, as described in claim 2,
(A) A branch prediction error occurred during execution of the instruction,
(B) A cache miss occurred during execution of the instruction;
(C) Operand forwarding for the subsequent instruction has occurred,
(D) that store data forwarding has occurred for subsequent instructions;
(E) the instruction is the oldest instruction in the instruction window;
(F) the instruction is the oldest instruction in the reorder buffer;
(G) The instruction is an instruction that passes an execution result to the oldest instruction among the instructions existing in the instruction window;
(H) The instruction is an instruction that passes the execution result to the most subsequent instructions among the instructions executed in the same cycle;
(I) By passing the execution result of the instruction, it is included that the number of succeeding instructions that can be executed is greater than or equal to a predetermined determination value.

  Here, the behaviors (A) and (B) are observed in a state where the predicted slack exceeds the target slack and the execution of the subsequent instruction is delayed. The behaviors (C) and (D) are observed when the predicted slack matches the target slack. Therefore, when these behaviors are observed, it can be estimated that the predicted slack has reached the target slack.

  On the other hand, the above behaviors (E) to (I) are conventionally used as a determination condition as to whether or not an instruction is on the critical path. When the predicted slack reaches the target slack, if the instruction execution latency is further increased by one cycle, the execution of subsequent instructions will be delayed, resulting in a situation similar to the instruction on the critical path. It can also be used as an estimation condition.

  If the target slack decreases dynamically when the predicted slack matches the target slack until then, the predicted slack exceeds the target slack, and the execution of subsequent instructions is delayed. A misprediction penalty occurs. In this respect, if the predicted slack is reduced when it is estimated that the predicted slack has reached the target slack, the dynamic reduction of the target slack can be reduced. It will be possible to respond.

  If the predicted slack is increased or decreased immediately after the above estimation is established or not established, there is a risk that the frequency of occurrence of a misprediction penalty increases when the target slack frequently increases and decreases. Even in such a case, as described in claim 4, the predicted slack is increased on the condition that the number of times that the estimated condition that the predicted slack has reached the target slack has not been satisfied is the specified number of times. If the predicted slack is decreased on the condition that the number of times that the satisfaction condition is satisfied becomes the specified number, it is possible to suppress an increase in the frequency of the prediction mistake penalty when the target slack frequently increases or decreases.

  In this case, as described in claim 5, if the number of times that the satisfaction condition necessary for increasing the predicted slack is set larger than the number of times that the satisfaction condition necessary for reducing the predicted slack is set, The predicted slack increases carefully and decreases quickly. Therefore, it is possible to effectively suppress an increase in the frequency of misprediction penalties when the target slack is frequently increased and decreased. As described in claim 6, such an effect increases the predicted slack on the condition that the number of times that the estimated success condition of the predicted slack has reached the target slack has become a specified number of times. The slack reduction can be obtained in the same manner even when the satisfaction condition is satisfied.

  Depending on the type of instruction, there is a difference in local slack behavior such as the dynamic change degree and the frequency of the change. Accordingly, in order to predict local slack with higher accuracy, the upper limit value of predicted slack and the amount of update (increase or decrease) per time are specified as described in claims 8 and 9. It is desirable to make it different for each type. In addition, when the predicted slack is updated on the condition that the number of times that the estimated condition is satisfied or the number of times that the estimated condition is not satisfied becomes a specified number, as in the prediction methods according to claims 4 to 6. As described above, by making the prescribed number of times different for each type of instruction, prediction can be performed with higher accuracy. Incidentally, the types of such instructions can be classified into four categories, for example, a load instruction, a store instruction, a branch instruction, and other instructions as described in claim 10.

  By the way, the local slack of an instruction may change greatly depending on the branch path of the program leading to the execution of the instruction. In that respect, if predictive slack is individually set for each branch pattern of the program leading to the execution of the instruction as described in claim 11, it is individually set for each branch path of the program leading to the execution of the instruction. Thus, local slack is predicted, and local slack can be predicted with higher accuracy.

  On the other hand, in order to solve the above-mentioned problem, in the local slack prediction mechanism according to claim 12 of the present invention, as a mechanism for predicting the local slack of the instruction executed by the processor, the predicted value of the local slack of each instruction is used. A slack table in which a certain predicted slack is recorded and stored, and the execution latency setting for acquiring the predicted slack of the instruction by referring to the slack table when executing the instruction and increasing the execution latency by the acquired predicted slack. An estimation means for estimating whether or not the predicted slack has reached target slack, which is an appropriate value of the current local slack of the instruction, based on the behavior at the time of execution of the instruction, and the estimation means Until the predicted slack has reached the target slack, the predicted slack is estimated. Slack so that and an predicted slack update means gradually increasing for each execution of the instruction.

  In the above configuration, the predicted slack of the instruction is gradually increased by the predicted slack updating means every time the instruction is executed, and the execution latency of the instruction is also gradually increased by the execution latency setting means every time the instruction is executed. When the predicted slack reaches the target slack in this way, the behavior of the processor at the time of execution of the instruction indicates that, and the estimation means estimates that. As a result, the predicted slack update means increases the predicted slack. You can stop. As described above, predicted slack is obtained without performing direct calculation.

  The estimation of the arrival of predicted slack to the target slack by the estimating means is performed by estimating any one of the above (A) to (I) or a plurality of them as described in claim 13, for example. This can be done by establishing the conditions for establishment.

  Further, as described in claim 14, when a condition for establishing that the predicted slack has reached the target slack is satisfied, the counter value is increased / decreased, and the condition for establishing the estimation is not satisfied. A reliability counter whose counter value is sometimes decreased / increased, and the predicted slack is increased on the condition that the counter value of the reliability counter becomes an increase determination value, and the counter value of the reliability counter If the predicted slack update means reduces the predicted slack on the condition that the value becomes the subtraction judgment value, it is preferable to increase the frequency of occurrence of a prediction mistake penalty when the target slack is repeatedly increased or decreased. Can be suppressed. In order to more effectively suppress an increase in the frequency of occurrence of a misprediction penalty in such a state, as described in claim 15, the counter value at the time when the condition for establishing the estimation in the reliability counter is satisfied. It is desirable to set the increase / decrease amount to be larger than the decrease / increase amount of the counter value when the establishment condition of the estimation is not satisfied.

  Furthermore, in order to predict local slack with higher accuracy in response to a difference in the aspect of dynamic change of local slack depending on the type of instruction, for example, the prediction of each instruction by the updating means as described in claim 17 It is desirable to vary the amount of slack update (increase and decrease) per time depending on the type of instruction. Further, when an upper limit value is set for the predicted slack of each instruction updated by the updating means, it is also effective to make the upper limit value different depending on the type of instruction as described in claim 18. Furthermore, when the reliability counter according to claim 14 or 15 is provided, it is effective to vary the increment and decrement of the counter value depending on the type of instruction as described in claim 16. It is. Incidentally, as instruction types, for example, as described in claim 19, it is conceivable to classify into four categories of load instructions, store instructions, branch instructions, and other instructions.

  A branch history register for recording a branch history of a program is provided as described in claim 20, and the predicted slack of an instruction is individually recorded in the slack table for each branch pattern obtained by referring to the branch history register. This is also effective for improving the prediction accuracy.

  According to the local slack prediction method and the prediction mechanism of the present invention, an appropriate value is obtained while observing the behavior at the time of execution of an instruction, instead of directly calculating a predicted value of local slack (predicted slack) of an instruction. By gradually increasing the predicted slack until it reaches Therefore, a complicated mechanism required for direct calculation of predicted slack is unnecessary, and local slack can be predicted with a simpler configuration.

Hereinafter, an embodiment of the present invention will be described in detail with reference to FIGS.
First, the basic operation of the local slack prediction method in this embodiment will be described. In this prediction method, while observing the behavior of the processor at the time of instruction execution, the predicted value is updated to increase or decrease the predicted value of the local slack of the instruction. It tries to be close to the value of. In the following description, the predicted value of the local slack of the instruction is described as “predicted slack”, and the actual value of the local slack of the instruction is described as “target slack”.

  The basic operation of this prediction method will be described. In this prediction method, first, when fetching an instruction, the predicted slack of the instruction is acquired, and the execution latency of the instruction is increased by the acquired predicted slack. For example, for an instruction whose execution latency is originally “1 cycle”, when the predicted slack is “2”, the execution latency of the instruction is increased to “3 cycles”. For any instruction, when the instruction is fetched for the first time after the start of the program, the local slack is predicted to be “0”. That is, the initial value of the predicted slack is set to “0” for all instructions. Thereafter, the behavior of the instruction at the time of execution is observed, and the predicted slack is gradually increased until it is estimated that the predicted slack has reached the target slack.

  The determination as to whether the predicted slack has reached the target slack is performed in the following manner. As a result of increasing the predicted slack, when the value reaches a value that matches the target slack, if the execution latency of the instruction is further increased by one cycle, the execution of the subsequent instruction depending on it will be delayed. It is in a state that occurs. In a situation where the predicted slack exceeds the target slack, the execution of the subsequent instruction is already delayed. Under these conditions, the instruction during execution exhibits behavior such as (A) branch prediction miss, (B) cache miss, (C) operand forwarding for subsequent instructions, (D) store data forwarding for subsequent instructions, etc. it is conceivable that. The behavior (A) to (D) of these instructions will be described below.

  First, the branch prediction error (A) will be described. Since a processor that performs pipeline processing simultaneously executes a large number of instructions in a work flow, if the instruction sequence to be executed later is changed by a branch instruction, all subsequent instructions that have already started processing must be discarded. In other words, the processing efficiency decreases. In order to prevent this, it is predicted whether or not the instruction will branch based on the state of occurrence of the branch when the branch instruction was previously executed, and the branch prediction destination instruction is speculatively executed according to the prediction result. Consider the situation where predicted slack exceeds target slack. In such a situation, the execution latency of the preceding instruction is excessively increased, causing a delay in the execution of the succeeding instruction that depends on it. In such a case, proper branch prediction cannot be performed, and branch prediction results are likely to be erroneous. For this reason, when a branch prediction error occurs, it can be considered that there is a high possibility that the predicted slack exceeds the target slack.

  Next, the cache miss (B) will be described. In many processors, frequently used data and the like are stored in a high-speed cache memory, thereby reducing access to a low-speed storage device and increasing the processing speed of the processor. If the predicted slack of the preceding instruction exceeds the target slack, such a cache operation cannot be performed properly, and a cache miss is likely to occur. Therefore, even when a cache miss occurs, it can be considered that there is a high possibility that the predicted slack exceeds the target slack.

  Next, operand forwarding and store data forwarding for the subsequent instructions (C) and (D) will be described. If the execution interval between the preceding instruction and the subsequent instruction that refers to the data defined by the preceding instruction is short, a data hazard may occur when the subsequent instruction tries to read the data before the data writing is completed. Therefore, in many processors with multistage pipelines, a bypass circuit is provided to avoid such data hazards by performing operand forwarding or store data forwarding that directly gives the data before writing to subsequent instructions. I have to. Such forwarding occurs when a subsequent instruction that refers to data defined by the preceding instruction is executed immediately after the preceding instruction. Therefore, when operand forwarding or store data forwarding occurs, it can be determined that the predicted slack matches the target slack.

  In this prediction method, when the behavior at the time of instruction execution corresponds to one of the above (A) to (D), it is estimated that the predicted slack has reached the target slack, and otherwise it is determined that it has not been reached. Like to do. The condition for establishing that such predicted slack has reached the target slack is defined as the OR condition of the above (A) to (D) and described as the target slack arrival condition. A mechanism for detecting the behavior at the time of instruction execution as in the above (A) to (D) is usually provided from the beginning if it is a processor that performs branch prediction, cache, and forwarding. Therefore, it is possible to confirm whether or not the arrival condition is satisfied without newly adding such a detection mechanism for local slack prediction.

  FIG. 1 shows a process of repeatedly executing the program of FIG. 12A based on the basic operation of this prediction method. FIGS. 1A to 1C show the states of the first to third executions of the program, respectively. Here, only the instruction i0 is set as a prediction target for local slack, and the predicted slack is increased by “1” at a time.

  In the first execution of the program, the predicted slack of the instruction i0 is the initial value “0”, and the target slack “2” has not yet been reached, so the predicted slack of the instruction i0 is increased by “1”. As a result, as shown in FIG. 5B, in the second program execution, the predicted slack of the instruction i0 is “1”, and the instruction i0 is executed with the execution latency increased by one cycle. Also at this time, since the predicted slack has not reached the target slack, the predicted slack is further increased by “1”. As a result, in the third program execution, the predicted slack of the instruction i0 is “2”, and the instruction i3 subsequent to the instruction i0 is executed. As a result, when the subsequent instruction i3 is executed, operand forward is performed, and the target slack arrival condition is satisfied. Therefore, the predicted slack of the instruction i0 is not increased any more and “2 Is maintained. As described above, the local slack of the instruction i0 can be predicted by gradually increasing the predicted slack until the arrival at the target slack is confirmed from the behavior at the time of instruction execution.

(Decrease in predicted slack)
The basic operation of the present prediction method as described above works satisfactorily as long as it assumes that the target slack is statically maintained at a constant value. However, the value of the target slack of the instruction is dynamically increased or decreased. When the target slack changes to a larger value after reaching the target slack, the above arrival condition is not satisfied again, and the predicted slack increases again toward the changed target slack. There is no problem. On the other hand, when the target slack has changed to a value smaller than the predicted slack, the predicted slack cannot follow the change only with the basic operation.

  The problem of the basic operation will be described with reference to FIG. FIG. 2A shows the transition of predicted slack and target slack when the target slack decreases to a value lower than the predicted slack at time t1 after the predicted slack of a certain instruction reaches the target slack. It is shown. As shown in the figure, after the start of the program, the predicted slack is increased until reaching the target slack, and is maintained at the value at the time of arrival after reaching the target slack. In this state, when the target slack decreases at time t1, the predicted slack exceeds the target slack. However, in the basic operation, the predicted slack is maintained at the current value without being updated after that even in such a state. As the predicted slack exceeds the target slack, the execution of subsequent instructions is delayed, which adversely affects the processing of the processor.

  These problems can be solved by reducing the predicted slack when the target slack falls below the predicted slack. As a method for realizing such a decrease in predicted slack, a method of using the execution time of the subsequent instruction when slack prediction is not performed can be considered. In other words, if the difference between the time when the subsequent instruction was supposed to be executed and the time when it was actually executed is obtained, the amount of delay in the execution time of the subsequent instruction due to a slack prediction error of the preceding instruction can be found. By reducing the predicted slack of instructions, the predicted slack and target slack can be matched. Another possible method is to directly calculate the target slack and compare it with the current predicted slack. However, in these methods, the original execution time and target slack of subsequent instructions must be calculated in consideration of various factors that determine the execution time of instructions such as resource constraints, data dependency, and control dependency. It cannot be easily realized.

  Therefore, here, it is determined whether the predicted slack exceeds the target slack using the above-described target slack arrival conditions (strictly, including the case where the predicted slack matches the target slack), Use a technique that reduces predicted slack until it falls below the target slack. Such a method can cope with the dynamic decrease of the target slack very easily without performing complicated calculation such as the original execution time of the instruction or calculation of the target slack itself.

  FIG. 2B shows the transition of predicted slack with respect to the dynamic decrease of local slack when such a method is adopted. Again, after the start of the program, the predicted slack is increased until the target slack is reached. However, in this case, when the target slack is reached, the predicted slack is once reduced, but then becomes lower than the target slack, so it immediately increases and reaches the target slack again. become. Therefore, in this case, once the target slack is reached, the predicted slack changes immediately below the target slack while repeating small increases and decreases. Thereafter, when the target slack decreases to a value lower than the predicted slack at time t1, the predicted slack decreases until it falls below the decreased target slack. After falling below the target slack, a slight increase / decrease is repeated again immediately below the target slack.

By adopting the above method in this way, it is possible to cope with a dynamic decrease in local slack.
(Introduction of reliability)
By adopting the method for reducing predicted slack as described above, predicted slack can be made to follow the dynamic reduction of local slack. However, when the target slack repeatedly increases and decreases as shown in FIG. 3A, a penalty of misprediction frequently occurs. In other words, when the predicted slack reduction method described above is employed as it is, if the target slack is not reached, the predicted slack is immediately increased. However, if the target slack decreases immediately thereafter, the predicted slack will exceed the target slack. When the target slack repeatedly increases and decreases, the predicted slack increases and decreases accordingly, and a delay in execution of the subsequent instruction occurs each time the target slack decreases.

  Therefore, here, the concept of reliability is introduced in the operation of increasing / decreasing the predicted slack based on the determination of the target slack arrival condition. That is, instead of immediately increasing or decreasing the predicted slack according to the single determination result of the above reaching condition, the predicted slack is actually increased or decreased only when a certain number of times that the reaching condition is satisfied or not is reached. Let's make it. Specifically, a reliability counter is provided for each predicted slack of the instruction, and the counter value is decreased if the instruction satisfies the target slack arrival condition, and is increased if the instruction does not satisfy the target slack arrival condition. Then, the predicted slack is decreased when the counter value becomes “0” (decrease determination value), and the predicted slack is increased when a certain threshold value (increase determination value) is exceeded. In order to carefully increase the predicted slack, the counter value of the reliability counter is reset to “0” when the predicted slack is increased. When predictive slack is increased or decreased using such a reliability counter, the predicted slack is increased on the condition that the number of consecutive failure of the arrival condition has become the specified number, and the decrease in predicted slack is the same. This is performed under the condition that the number of consecutive arrival conditions reaches the specified number.

  However, in order to avoid delay in execution of subsequent instructions when the predicted slack exceeds the local slack, it is desirable to increase the predicted slack carefully and to decrease the predicted slack quickly. For this purpose, the decrease amount of the counter value when the achievement condition is satisfied may be made larger than the increase amount of the counter value when the achievement condition is not satisfied. Alternatively, if the instruction satisfies the target slack arrival condition, the counter value may be reset to “0”, and the predicted slack may be forcibly decreased when the arrival condition is satisfied once.

  FIG. 3B shows the transition of the prediction counter when reliability is introduced. Here, the reliability counter is reset to “0” when the reaching condition is satisfied. In this case, the predicted slack increases gradually toward the target slack as compared with the case where reliability is not introduced. On the other hand, when the target slack is reached or exceeded, the predicted slack decreases immediately. As a result, even if the target slack repeatedly increases and decreases as shown in the figure, the frequency at which the predicted slack exceeds the target slack is reduced.

(Configuration of local slack prediction mechanism)
Next, the local slack prediction mechanism of the present embodiment that realizes the above-described prediction method will be described. FIG. 4 illustrates the hardware configuration of the local slack prediction mechanism of the present embodiment.

  As shown in FIG. 4, the processor 10 to which the local slack prediction mechanism of the present embodiment is applied includes a fetch unit 11, a decode unit 12, an instruction window (I-win) 13, and a register file (RF). 14, an execution unit (EU) 15 and a reorder buffer (ROB) 16. The function of each unit constituting the processor 10 is as follows. The fetch unit 11 reads an instruction from the main storage device. The decode unit 12 analyzes (decodes) the content of the read instruction and stores it in the instruction window 13 and the reorder buffer 16, respectively. The instruction window 13 is a buffer for temporarily storing an instruction before execution, and the control circuit of the processor takes out the instruction from this buffer and sequentially inputs it to the execution unit 15. On the other hand, the reorder buffer 16 is a FIFO-type stack for storing instructions. When execution of an instruction having the earliest storage order is completed among the stored instructions, the instruction is taken out (committed). The register file 14 is an entity of various registers for storing data necessary for execution of instructions, execution results of instructions, addresses and indexes of instructions being executed and scheduled to be executed, and the like.

  The local slack prediction mechanism of the present embodiment is configured by a slack table 20 that stores and holds predicted slack. In this slack table, the instruction PC (memory address of the main storage device storing the instruction) is used as an index, and the predicted slack of the corresponding instruction and the counter value of the reliability counter are stored and held as entries.

When fetching an instruction, the fetch unit 11 refers to the slack table 20 by using the PC of the instruction as an index, acquires the predicted slack of the corresponding instruction, and increases the execution latency of the corresponding instruction by the acquired predicted slack. Let When the instruction is committed, the value of each entry in the slack table 20 corresponding to the instruction is updated based on the behavior of the instruction at the time of execution. The following parameters are preset as constants for updating each entry in the slack table 20.
Vmax: the maximum value of predicted slack,
Vmin: the minimum value of predicted slack (= 0),
・ Vinc: Increase in predicted slack per time,
Vdec: the amount of decrease in predicted slack per time,
Cmax: Maximum value of the reliability counter,
Cmin: minimum value of the counter value of the reliability counter (= 0),
Cth: reliability counter threshold (increase judgment value),
Cinc: increase amount of the counter value of the reliability counter per time,
Cdec: the amount of decrease in the counter value of the reliability counter per time.

  A manner of updating entries in the slack table 20 will be described. If the target slack arrival condition is satisfied, the counter value of the reliability counter is reset to “0”, otherwise, the counter value is increased by the increase amount Cinc. Here, when the counter value becomes equal to or greater than the threshold value Cth, the predicted slack is increased by the increase amount Vinc, and the counter value is reset to “0”. On the other hand, when the counter value of the reliability counter becomes “0”, the predicted slack is decreased by the decrease amount Vdec. In this embodiment, the reliability is reset to “0” when the target slack arrival condition is satisfied, and the amount of decrease Cdec of the counter value is set equal to the threshold value Cth. In the present embodiment, when the predicted slack is increased, the counter value of the reliability counter is reset to “0”, so the maximum value Cmax of the counter value is the same value as the threshold value Cth.

(Evaluation of local slack prediction mechanism)
Subsequently, the evaluation result of the local slack prediction mechanism of the present embodiment described above will be described. The inventors evaluated the prediction mechanism under the measurement conditions shown in Table 1 while changing each parameter related to the update of the entry in the slack table 20 using a simulator for the superscalar processor (Simple Scalar Tool Set). It is carried out. For this evaluation, “Simple Scalar / PISA” which is an extended instruction set of “MIPS R100000” is used. In this evaluation, eight benchmark programs, “bzip2”, “gcc”, “gzip”, “mcf”, “paser”, “perl”, “votex”, and “vpr”, are used as benchmark programs. The program is being used.

  Of the parameters related to the update of each entry in the slack table 20, those that can be changed are the predicted slack maximum value Vmax, the predicted slack increase amount Vinc, the decrease amount Vdec, the reliability counter threshold Cth, And an increase amount Cinc and a decrease amount Cdec per time of the counter value of the reliability counter. However, if all of these are variable values, the number of combinations becomes enormous. Therefore, evaluation is performed with some parameters fixed to certain values. First, even if the values of both the increase amount Cinc and the threshold value Cth change, the increase rate of the predicted slack is the same unless the ratio thereof changes, so the increase amount Cinc is fixed to “1” and the threshold value Cth. Only variable. Further, in order to make the predicted slack as close as possible to the target slack, the increment Vinc per predicted slack was fixed to “1”. Further, in order to reduce the predicted slack as quickly as possible, the amount of decrease Vdec per predicted slack is fixed to the same value as the maximum value Vmax of the predicted slack. Therefore, there are two variable parameters in this evaluation: the maximum value Vmax of predicted slack and the threshold value Cth of the reliability counter.

  In such evaluation, the number of slack instructions, the total estimated value of predicted slack, and IPC (Instruction Per Clock: the number of instructions executed per cycle) are measured as evaluation values. The slack instruction here is an instruction whose execution latency is increased by one cycle or more based on predicted slack. Note that the IPC is an index value for measuring the processing performance of the processor.

  FIG. 5 shows the number of slack instructions and IPC measurement results in the evaluation. The vertical axis in the figure shows the ratio of the number of slack instructions to the total number of executed instructions and the ratio of the measured IPC to the IPC when no slack prediction is performed in each combination of the maximum value Vmax and the threshold value Cth. ing. In addition, the four vertical bars in each of the maximum value Vmax (“1”, “5”, “10”, “15”) have thresholds Cth of “1”, “5” from the left side in the figure, respectively. , “10” and “15”, the measurement results are respectively shown.

  As shown in the figure, when the threshold value Cth is increased, the number of slack instructions decreases. This is because the increase condition of the predicted slack becomes severe due to the increase of the threshold value Cth, and the increase frequency of the predicted slack becomes low. However, if the threshold value Cth is increased, the frequency at which the predicted slack exceeds the target slack is reduced, so that the IPC is improved. From this result, it was confirmed that the introduction of the reliability can suppress a decrease in instruction processing performance due to the slack prediction miss penalty. On the other hand, if the maximum value Vmax of predicted slack is increased, the predicted slack can take a larger value, so that the penalty for slack prediction mistakes increases and the processing performance (IPC) decreases.

  FIG. 6 shows the relationship between predicted slack and IPC in the above measurement results. The vertical axis in the figure represents the ratio of the benchmark average value of the total integrated value of predicted slack with the parameter (Vmax, Cth) = (1, 1) as the reference (100%), and the horizontal axis represents slack prediction. The ratios of the benchmark average values of IPC are shown with reference to the time when 100% was not performed at all (100%). In addition, the number attached | subjected to each point of the figure has shown the value of threshold value Cth.

  As shown in the figure, when the maximum value Vmax of predicted slack is increased, the processing performance is reduced, but the predicted slack is greatly increased. In addition, by increasing the threshold value Cth together with the maximum value Vmax, some combinations of parameters that increase predicted slack without substantially decreasing IPC were confirmed. For example, when the parameter (Vmax, Cth) = (1, 1), in the case of (5, 15), the predicted slack is about 2.2 while the IPC decrease is only 0.3%. It has doubled.

  As is clear from the above results, the processing performance is in a trade-off relationship with the number of slack instructions and predicted slack, and the optimum value of each parameter varies depending on the request of the application target.

(Reduction of power consumption of functional units)
Next, as an application example of the local slack prediction mechanism of the present embodiment described above, a method for reducing the power consumption of the functional unit (execution unit) of the processor by using the prediction result will be described.

  FIG. 7 shows an example of a processor configured to be able to reduce the power consumption of the functional unit using the prediction result of local slack. The processor illustrated in FIG. 2 includes two types of execution units: an execution unit 15a that operates at high speed with high power consumption, and an execution unit 15b that operates at low speed but has low power consumption. By allocating units that execute instructions, instructions with small predicted slack to high-speed execution units 15a and instructions with large predicted slack to low-speed execution units 15b, the consumption of functional units is reduced. Electric power can be reduced.

  The inventors have evaluated such application examples. In this evaluation, as a function unit (iALU) for integer arithmetic, a processor model including two types of units, a high speed / high power consumption unit and a low speed / low power consumption unit, is used. The power supply voltages of both units are “1.1 V” and “0.7 V”, respectively, and the execution latencies are “1 cycle” and “2 cycles”, respectively. An instruction with predicted slack “1” is assigned to a low-speed iALU, and an instruction with predicted slack “0” is assigned to a high-speed iALU. However, at the time of execution of an instruction, an instruction is assigned to a high-speed iALU if there is no free space in the low-speed iALU, and to a high-speed iALU if there is no free space in the high-speed iALU, regardless of predicted slack.

Also, in this evaluation, the parameter (Vmax, Cth) = (1, 15), and all the parameters related to the change of the slack table entry are fixed. While changing the ratio with the number of low-speed iALU, the energy delay product (EDP) of the entire IPC and iALU was measured. The EDP is an index value for measuring the power consumption of the functional unit. Hereinafter, a model having n high-speed iALUs, that is, having m (= 6-n) low-speed iALUs will be referred to as an (nf, ms) model.

  8 and 9 show the measurement results of IPC and EDP in each benchmark in each model. The vertical axis in FIG. 8 represents the ratio of IPCs based on the IPC in the (6f, 0s) model (a model in which all iALUs are high-speed) (100%), and the vertical axis in FIG. 9 is the same as (6f, 0s). The ratio of EDP based on EDP as a reference (100%) in a model (a model in which all iALUs are high speed) is shown. The six vertical bars in each benchmark program in both figures are (5f, 1s), (4f, 2s), (3f, 3s), (2f, 4s), (1f, 5s) from the left side in the figures. , (0f, 6s) represents the measurement results in each model.

  As shown in both figures, the same trend is seen in all benchmark programs. That is, when the number of high-speed iALUs is decreased, in most cases, EDP decreases monotonously. However, since the instructions are distributed based on the prediction result of local slack, the decrease in IPC accompanying the decrease in the number of high-speed iALUs is suitably suppressed. For example, in the (0f, 6s) model, that is, a model in which all iALUs are low speed, the benchmark average IPC decrease is “20.2%”, and the EDP reduction rate is “41.6%”. On the other hand, in the (1f, 6s) model, although the EDP reduction rate is “34.5%”, the decrease in IPC is only “10.5%”. Furthermore, in the (3f, 3s) model, the reduction rate of IPC is only “3.8%”, but the reduction rate of EDP is also “20.3%”.

  Note that the above evaluation focuses only on the power consumption of the functional unit, and does not consider the power consumption required for the operation of the slack table at all, so the effect of reducing the power consumption of the entire processor is lower than the above result. . However, as long as the power consumption required for the operation of the slack table can be kept sufficiently low, a sufficient effect can be expected to reduce the power consumption of the entire processor. However, the functional unit is one of the typical hot spots on the chip. Even if the power consumption of the entire processor is not suitable, if the power consumption of the functional unit is suppressed, the hot spots on the chip are dispersed. The effect that it can be obtained.

  In the local slack prediction mechanism of this embodiment, the fetch unit 11 also functions as the execution latency setting unit. In addition, the slack table 20 (strictly, the operation circuit related to the update of the entry) also has the functions as the estimation means and the predicted slack update means.

According to the local slack prediction method and local slack prediction mechanism of the present embodiment described above, the following effects can be obtained.
(1) Predicted slack is not calculated directly by calculation, but is calculated by gradually increasing the predicted slack until the target slack is reached while observing the behavior during execution of the instruction. The complicated mechanism required for the direct calculation is not required, and local slack can be predicted with a simpler configuration.

  (2) Since the behavior at the time of instruction execution of the above conditions (A) to (D) that can be detected by the detection mechanism provided by the processor is the local slack arrival condition, a special detection mechanism is provided for local slack prediction. Even without additional installation, the arrival of the predicted slack to the target slack can be confirmed.

  (3) Since the predicted slack is reduced when the target slack arrival condition is satisfied, it is possible to suitably suppress the execution delay of the subsequent instruction due to the excessive evaluation of the predicted slack.

  (4) Since a reliability counter is installed and the predicted slack is carefully increased and decreased rapidly, the subsequent instruction due to overestimation of the predicted slack even when the target slack repeatedly increases and decreases The frequency of occurrence of execution delay can be kept low.

Next, the local slack prediction method and the expansion of further functions of the prediction mechanism will be described.
(Extension of index method for slack table)
In many cases, the behavior of a branch instruction in a program depends on what function or instruction has been executed (hereinafter referred to as a control flow) until the branch is executed. A technique for predicting the result of a branch instruction with higher accuracy using this property has been proposed. Conventionally, such a branch prediction method has been used to improve the accuracy of speculative execution of instructions. However, in the prediction of local slack, further improvement of the prediction accuracy can be expected by introducing the same principle. Hereinafter, a method for performing slack prediction with higher accuracy in consideration of the control flow will be described.

  Since the program uses a branch instruction to determine what function or instruction is executed, the control flow can be simplified by paying attention to the branch condition in the program. Specifically, “1” is recorded if the branch condition is satisfied, and “0” is stored if the branch condition is not satisfied. For example, the branch history when the branch condition is established (1) → established (1) → not established (0) → established (1) in the fetch order is expressed as “1101” when the newer one is recorded in the lower order. The In order to use the branch history for slack prediction, an index to the slack table is generated from the branch history and the PC of the instruction. In this way, slack can be predicted in consideration of both the PC and the control flow. For example, even if the PC is the same, if the control flow is different, different entries in the slack table are used, so that prediction according to the control flow can be performed.

  FIG. 10 shows an example of a hardware configuration of a local slack prediction mechanism that performs slack prediction in consideration of the control flow. In this configuration, in addition to the example shown in FIG. 4, a branch history register 21A, a branch history register 21B, and two index generation circuits 22A and 22B are newly added. The branch history register 21A and the branch history register 21B are registers for recording a branch history.

  The index generation circuits 22A and 22B have the same circuit configuration except for the difference in input. When fetching an instruction, the branch history register 21A and the PC of the instruction are input, and the index generation circuit 22A generates an index to the slack table 20 and refers to the slack table 20. On the other hand, when the instruction is committed, the branch history register 21B and the PC of the instruction are input, and the index generation circuit 22B generates an index to the slack table 20 and updates the entry in the slack table 20. Hereinafter, the branch history registers 21A and 21B and the index generation circuits 22A and 22B will be described in more detail.

First, the update operation of the branch history of the branch history registers 21A and 21B will be described.
The branch history register 21A records a branch history based on the branch prediction result of the processor. Specifically, when a branch instruction is fetched, the value held in the branch history register 22A is shifted to the left by one bit, and if the branch condition of the branch instruction is predicted to be satisfied in the fetch unit 11 If “1” is predicted to be not established, “0” is written in the least significant bit of the branch history register 21A.

  On the other hand, the branch history register 21B records the branch history based on the branch execution result of the processor. Specifically, when the branch instruction is committed, the value held in the branch history register 21B is shifted to the left by 1 bit. If the branch condition of the branch instruction is satisfied, “1” is set. This is performed by a procedure of writing “0” to the least significant bit of the branch history register 21B.

  As described above, there are two ways of taking the branch history. The reason for using the branch history of both branch history registers 21A and 21B is that the slack reference is performed at the fetch time and the slack table is updated at the commit time. There is a difference. At the time of fetching, the branch instruction has not yet been executed, and the processor predicts whether or not the branch condition is satisfied and reads the instruction from the memory. Therefore, the branch history register 21A used at the time of fetching can only record the branch history based on the branch prediction. On the other hand, at the time of commit, the branch instruction has already been executed, and the branch history can be recorded based on the execution result.

  Next, the details of the index generation mode by the index generation circuits 22A and 22B will be described with reference to FIG. FIG. 11A shows the index generation method in the above embodiment, that is, the index generation method using only the PC of the instruction. In this case, some bits of the PC are cut out and used as an index to the slack table 20.

  FIG. 11B shows an example of index generation using the branch history and the PC, and FIG. 11C shows another example of index generation using the branch history and the PC. . When mounting on an actual processor, it is necessary to adopt a common index generation method for both index generation circuits 22A and 22B. The reason is that if different index generation methods are employed in both index generation circuits 22A and 22B, different indexes are generated when the slack table 20 is updated and when the slack table 20 is referenced, and slack cannot be correctly predicted.

  In the case of FIG. 11B, an index is generated by concatenating i bits of the branch history and j bits cut out from the PC. On the other hand, in the case of FIG. 11C, an exclusive OR of i bits of the branch history and the same number (i) of bits extracted from the PC is taken for each bit, and the bit string An index is generated by concatenating j bits further cut out from the PC.

  As shown in FIG. 11C, even when the branch history is monotonous (all established or all not established), the upper bits of the index are monotonic by taking the exclusive OR with the bits cut out from the PC. The entries in the slack table 20 can be used effectively.

  For example, as shown in FIGS. 11B and 11C, when the branch history is 4 bits and the lower bits cut out from the PC are 2 bits, only the lower 2 bits cut out from the PC are the same. Consider the case where the slack of (instruction 1, instruction 2) is updated. In the following description, among the PCs of instruction 1 and instruction 2, bits not related to index generation are omitted, and the upper 4 bits and lower 2 bits of the bits not omitted are separated by a space. indicate. Here, it is assumed that the PC of the instruction 1 is “... 001 01...” And the PC of the instruction 2 is “. When all branch histories of the instruction 1 and the instruction 2 are established (1111), in the method of FIG. 11B, the index to the slack table 20 becomes the same value (11111 01) in both instructions. End up. On the other hand, in the method of FIG. 11C, the index to the slack table 20 is “11000 01” for the instruction 1 and “0011 01” for the instruction 2 and has different values in this case.

  As described above, the method shown in FIG. 11C is advantageous in making effective use of the entry. However, since extra calculation is required, a request for the slack table, that is, higher accuracy of slack prediction is desired. The method to be adopted is selected depending on whether the simplicity of the mechanism is desired. In any case, the accuracy of slack prediction can be further improved by separately recording predicted slack for each branch pattern in consideration of the control flow.

(Expansion of target slack arrival conditions)
In addition to the above-described (A) to (D), for example, (E) to (I) listed below can be considered as behaviors at the time of instruction execution that can be used as the target slack arrival conditions. By adding some or all of these to the target slack arrival condition, there is a possibility that slack can be predicted more accurately.
(E) The instruction becomes the oldest instruction in the instruction window 13 (see FIGS. 4 and 10) (the instruction remains in the instruction window 13 for the longest time).
(F) The oldest instruction in the reorder buffer 16 (see FIGS. 4 and 10) (the instruction remains in the ROB for the longest time).
(G) The instruction is an instruction that passes the execution result to the oldest instruction among the instructions existing in the instruction window.
(H) The instruction is an instruction that passes the execution result to the largest number of subsequent instructions among the instructions executed in the same cycle. For example, if two instructions are executed in the same cycle and one of them passes the execution result to two subsequent instructions and the other passes the execution result to five subsequent instructions, the latter instruction reaches the target slack. It is determined that the condition is satisfied.
(I) The number of subsequent instructions that can be executed by passing the execution result of the instruction is equal to or greater than a predetermined determination value. The executable state here means a state where input data is ready and execution can be started at any time.

For these (E) to (I), the following instructions i1 to i6, that is,
Instruction i1: A = 5 + 3;
Instruction i2: B = 8−3;
Instruction i3: C = 3 + A;
Instruction i4: D = A + C;
Instruction i5: E = 9 + B;
Instruction i6: F = 7−B;
An example of executing is described.

  Assuming that the instruction i1 and the instruction i2 are simultaneously executed in the first cycle, the instruction i1 passes the execution result to the instruction i3 and the instruction i4, and the instruction i2 passes the execution result to the instruction i5 and the instruction i6. Therefore, the number of subsequent instructions that pass the execution result is two, but since the input data of the instruction i4 has not been prepared yet, the number of instructions that can be executed by the execution result of the instruction i1 is one, the instruction i2 The number of instructions that can be executed by the execution result of is two. If the determination value under the condition (I) is “1”, only the instruction i1 and the instruction i2 satisfy the condition (I). If the determination value is “2”, only the instruction i2 is satisfied.

  These conditions (E) to (I) have been proposed to be used as conditions for detecting a critical path in the past, but can be sufficiently used as local slack arrival conditions. is there.

(Expansion of parameters related to slack table update)
In the above-described embodiment, among the parameters relating to the update of the slack table, the decrease amounts Vdec and Cdec per time of the predicted slack and the reliability counter are fixed to the same values as the maximum value Vmax and the threshold value Cth of the predicted slack, respectively. Further, the increments Vinc and Cinc of the prediction slack and the reliability counter per time are both fixed to “1”. However, the optimum value of the parameter varies depending on the situation, for example, when it is important to suppress performance degradation or when it is desired to increase the amount of slack that can be predicted as much as possible. Therefore, it is not always necessary to fix the parameters as described above, and it is desirable to appropriately determine the parameters according to the field to which slack prediction is applied.

  In the above embodiment, each parameter related to the update of the slack table is a uniform value regardless of the type of instruction. For example, the same value is used for the reliability threshold Cth regardless of whether it is a load instruction or a branch instruction.

  However, in practice, depending on the type of instruction, there is a difference in local slack behavior such as the dynamic change degree and the frequency of the change. A typical example is a branch instruction. Branch instructions have a much more variable amount of local slack than other instructions. When branch prediction is successful, the impact on subsequent instructions is very small and local slack tends to be large, but when branch prediction fails, all instructions that were executed incorrectly are discarded, Because it incurs a large penalty, the local slack is “0”. This means that the local slack changes rapidly when the success and failure of branch prediction are switched. Therefore, in the case of a branch instruction, it is desirable that the threshold value Cth of the reliability counter and the amount of decrease Cdec per time be larger than those of other instructions.

  In addition, even in an instruction belonging to a type other than the branch instruction, if there is a characteristic in the operation in the processor, it is considered that an appropriate value of a parameter suitable for the characteristic exists for each type. Therefore, there is a possibility that the prediction accuracy may be further improved by dividing the instructions into several categories and individually setting parameters related to the slack table update for each category. For example, focusing on the difference in operation within the processor, the instructions can be classified into the following four categories: a load instruction category, a store instruction category, a branch instruction category, and other instruction categories.

  Parameters are individually set for each category of instructions thus classified. When updating, it is first determined to which category the instruction belongs. This determination can be easily made by looking at the operation code of the instruction. Then, the slack table is updated using the parameters specific to the category to which the instruction belongs. In addition, as a classification mode of the instruction category, a mode in which the load instruction and the store instruction are set to the same category, and addition and subtraction are divided into different categories is also conceivable. How instructions are classified depends on the range to which slack prediction is applied. If individual parameters are used for each type of instruction in this way, the configuration of the local slack prediction mechanism becomes complicated. To suppress this, it is necessary to reduce the number of categories to the minimum necessary. is there.

(A)-(c) The timing chart for demonstrating the basic operation | movement of the prediction method of the local slack which concerns on one Embodiment of this invention. The graph which shows each transition of the prediction slack with respect to the dynamic reduction of local slack in each when (a) said basic operation and (b) the improvement operation | movement which reduces prediction slack are added to the basic operation. The graph which shows transition of the prediction slack with respect to the repetition of increase / decrease of local slack in each before (a) reliability introduction, and (b) after introduction. The block diagram which shows typically the structure of the local slack prediction mechanism which concerns on one Embodiment of this invention. The graph which shows the measurement result of the number of slack instructions in evaluation of the prediction mechanism, and IPC. The graph which shows the relationship between the prediction slack in the said measurement result, and IPC. The block diagram which shows typically the structure of the processor comprised so that the power consumption of a functional unit could be reduced using the prediction result of the said prediction mechanism. The graph which shows the measurement result of IPC of each benchmark in each model of the processor. The graph which shows the measurement result of EDP of each benchmark in each model of the processor. The block diagram which shows typically the structure of the local slack prediction mechanism which performs slack prediction in consideration of the control flow. A block diagram schematically showing slack table index generation operations in each of (a) a prediction mechanism that performs slack prediction without considering control flow, and (b) and (c) a prediction mechanism that performs slack prediction considering control flow. . (A) The figure which shows together the list of the instructions of the program used for description of local slack, and (b) the timing chart which shows the execution aspect. The block diagram which shows typically the structure of the conventional local slack prediction mechanism.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 ... Processor, 11 ... Fetch unit, 12 ... Decode unit, 13 ... Instruction window, 14 ... Register file, 15, 15A, 15B ... Execution unit, 16 ... Reorder buffer, 20, 53 ... Slack table, 21A , 21B ... branch history register, 22A, 22B ... index generation circuit, 51 ... register definition table, 52 ... memory definition table, 54 ... calculator.

Claims (20)

The instruction executed by the processor is executed by increasing its execution latency by the predicted slack value that is the predicted value of the local slack of the instruction,
Based on the behavior at the time of execution of the instruction, it is estimated whether the predicted slack has reached the target slack that is an appropriate value of the current local slack,
The method for predicting local slack, wherein the predicted slack is gradually increased for each execution of the instruction until it is estimated that the target has been reached. As a condition for the estimation that the predicted slack has reached the target slack,
(A) A branch prediction error occurred during execution of the instruction,
(B) A cache miss occurred during execution of the instruction;
(C) Operand forwarding for the subsequent instruction has occurred,
(D) that store data forwarding has occurred for subsequent instructions;
(E) the instruction is the oldest instruction in the instruction window;
(F) the instruction is the oldest instruction in the reorder buffer;
(G) The instruction is an instruction that passes an execution result to the oldest instruction among the instructions existing in the instruction window;
(H) The instruction is an instruction that passes the execution result to the most subsequent instructions among the instructions executed in the same cycle;
(I) The number of subsequent instructions that can be executed by passing the execution result of the instruction is equal to or greater than a predetermined determination value.
The local slack prediction method according to claim 1, further comprising: 3. The local slack prediction method according to claim 1, wherein the prediction slack is decreased when it is estimated that the prediction slack has reached the target slack. The increase in the predicted slack is performed on the condition that the number of times that the estimated condition that the predicted slack has reached the target slack is not satisfied is a specified number of times, and the decrease in the predicted slack is the above The local slack prediction method according to claim 3, wherein the local slack prediction method is performed under a condition that the number of times the condition is satisfied becomes a specified number. The number of times that the satisfaction condition is not satisfied to increase the predicted slack is set larger than the number of times that the satisfaction condition is required to decrease the predicted slack. Local slack prediction method. The increase in the predicted slack is performed on the condition that the number of times that the estimated condition that the predicted slack has reached the target slack is not satisfied is a specified number of times, and the decrease in the predicted slack is the above The local slack prediction method according to claim 3, wherein the local slack prediction method is performed on condition that the condition is satisfied. The local slack prediction method according to claim 4, wherein the specified number of times is made different depending on a type of instruction. The local slack prediction method according to any one of claims 1 to 7, wherein an update amount of the prediction slack per time is varied depending on a type of instruction. The local slack prediction method according to claim 1, wherein an upper limit value of the predicted slack is varied depending on a type of instruction. The local slack prediction method according to any one of claims 7 to 9, wherein the instruction types are classified into four categories: a load instruction, a store instruction, a branch instruction, and other instructions. The local slack prediction method according to any one of claims 1 to 10, wherein the prediction slack is individually set for each branch pattern of a program leading to execution of the instruction. In a local slack prediction mechanism that predicts local slack of instructions executed by a processor,
A slack table in which predicted slack, which is a predicted value of local slack for each instruction, is recorded and retained;
An execution latency setting means for acquiring the predicted slack of the instruction with reference to the slack table upon execution of the instruction and increasing the execution latency by the acquired predicted slack;
Based on the behavior at the time of execution of the instruction, estimating means for estimating whether the predicted slack has reached the target slack which is an appropriate value of the current local slack of the instruction;
Predicted slack updating means for gradually increasing the predicted slack for each execution of the instruction until the estimation means estimates that the predicted slack has reached the target slack;
A local slack prediction mechanism characterized by comprising: The estimation means includes
(A) A branch prediction error occurred during execution of the instruction,
(B) A cache miss occurred during execution of the instruction;
(C) Operand forwarding for the subsequent instruction has occurred,
(D) that store data forwarding has occurred for subsequent instructions;
(E) the instruction is the oldest instruction in the instruction window;
(F) the instruction is the oldest instruction in the reorder buffer;
(G) The instruction is an instruction that passes an execution result to the oldest instruction among the instructions existing in the instruction window;
(H) The instruction is an instruction that passes the execution result to the most subsequent instructions among the instructions executed in the same cycle;
(I) The number of subsequent instructions that can be executed by passing the execution result of the instruction is equal to or greater than a predetermined determination value.
The local slack prediction mechanism according to claim 12, wherein arrival of the predicted slack to the target slack is estimated using any one of the above as a condition for establishing the estimation. The counter value is increased / decreased when the condition for establishing that the predicted slack has reached the target slack is satisfied, and the counter value is decreased when the condition for establishing the estimation is not satisfied. / Provide an increased reliability counter,
The predicted slack updating means increases the predicted slack on the condition that the counter value of the reliability counter becomes an increase determination value, and on the condition that the counter value of the reliability counter becomes a decrease determination value. The local slack prediction mechanism according to claim 12 or 13, wherein the predicted slack is reduced. The increase / decrease amount of the counter value when the condition for establishment of the estimation is satisfied in the reliability counter is set larger than the decrease / increase amount of the counter value when the condition for establishment of the estimation is not satisfied. 15. The local slack prediction mechanism according to claim 14, wherein: The local slack prediction mechanism according to claim 14 or 15, wherein an increase amount and a decrease amount of the counter value are made different depending on a type of instruction. The local slack prediction according to any one of claims 12 to 16, wherein an update amount of each predicted slack of each instruction by the updating means is different depending on a type of the instruction. mechanism. 18. The local slack according to claim 12, wherein an upper limit value is set in the predicted slack of each instruction updated by the updating unit, and the upper limit value is made different depending on a type of the instruction. Slack prediction mechanism. The local slack prediction mechanism according to any one of claims 16 to 18, wherein the instructions are classified into four categories: a load instruction, a store instruction, a branch instruction, and other instructions. It has a branch history register that records the branch history of the program,
20. The local slack prediction mechanism according to claim 12, wherein prediction slack of the same instruction is separately recorded in the slack table for each branch pattern obtained by referring to the branch history register. .

Images