JP3292189B2 - Processor performance data collection device and optimization method using the device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a processor performance data collection device for collecting statistical data of events generated in a processor for the purpose of improving the performance of a computer system, and an optimization method using the device.

[0002]

2. Description of the Related Art Conventionally, data relating to various events generated in a processor is collected and statistically processed, and the performance of a computer system is tuned based on the statistical data of the events. The typical prior art is shown below.

(1) Prior art 1 Japanese Patent Application Laid-Open No. 7-191882 (hereinafter referred to as Document 1)
Discloses a technique for obtaining the number of accesses for each continuous area of a memory and for each access type as statistical data of an event, and for tuning the performance based on the statistical data. Specifically, a trace collection routine for collecting the history of memory access is embedded in the target program and executed, and each time memory access is performed once, trace information including the type of memory access and the accessed address is stored in a trace file. collect. Next, the profiling means analyzes each trace information of the trace file, and totals and outputs the number of accesses for each continuous area of the memory and each access type. Then, by referring to the number of accesses, a part that is heavily processed and a variable or a data structure that is frequently accessed are improved.

(2) Prior art 2 JP-A-8-263372 (hereinafter referred to as reference 2)
Discloses a technique of calculating a cache miss rate (ratio of the number of cache misses to the number of accesses) of each data address as statistical data of an event, and tuning the performance based on the statistical data. More specifically, processing means for tracing instructions one by one in accordance with the execution sequence of the object program output by the compiler and extracting an address on the main memory of data accessed by the instruction, and storing the access address in the cache memory. Simulation means for detecting a cache miss when the data is not within the address range of the data regarded as a cache miss and counting up the number of accesses and the number of cache misses of the address in the cache miss information. Then, the compiler calculates a cache miss rate of an address related to each instruction from the cache miss information, and when the cache miss rate is equal to or more than a predetermined value, executes an independent subsequent instruction that is executed in parallel with the instruction in parallel. Optimization is performed by changing the execution order of instructions so that they are executed.

(3) Prior art 3 Japanese Patent Application Laid-Open No. H11-272519 (hereinafter referred to as Reference 3) describes, in advance, statistical data of events such as a cache hit rate for each process and an average memory system waiting time for each thread. There is disclosed a technique for obtaining statistical data of an event set in, and tuning performance based on the statistical data. According to the prior art 3, data on an event is sampled in hardware without adding an additional code to a target program as in the prior art 1 and without performing a simulation as in the prior art 2. Further, additional information such as an instruction cycle lost due to a branch misprediction can be collected as belonging to a specific instruction of the program. Specifically, FIG.
Trigger 1000, counter 1001 as shown in FIG.
And a selector 2000 composed of a marker 1002
Is provided in the processor.

The counter 1001 is initialized with an initial value 1007 arbitrarily settable by hardware or software, and is incremented by a counter event signal 1008. The counter event signal 1008 is the count selection signal 1
According to 009, one or more event signals (event 1, event 2, event 3) 1005 are selected. The event signal 1005 is a clock cycle, a transaction, or the like. The trigger 1000 inputs the current transaction 1003, event 1005, state 1006 in the computer system and determines when and under what conditions the counter 1001 should be enabled. Marker 1002 is
Enter event 1005, state 1006, and transaction to determine which transaction is marked as selected transaction T'1004 when counter 1001 overflows. Marking of the selected transaction is performed, for example, by providing the transaction with additional sample bits from T to T '.

After a transaction has been selected for sampling, the marked transaction 1
The processor that processes 004 checks the sample bits at each relevant processing stage, collects state information that can be used for it, and stores it in a buffer. The status information storage buffer includes a status field indicating a status relating to a specific transaction being processed (for example, if the transaction is a memory reference, a cache hit status or the like), a virtual field related to the transaction, An address field indicating the physical address, a context field indicating the thread identifier of the source of the transaction, a source field indicating the source of the transaction (eg, load or store instruction, DMA request, etc.), and an additional field for identifying the source. An instruction field indicating information (a program counter or an instruction field of an instruction when the source is a fetch unit of a processor pipeline) is included.

When the buffer is full after a certain number of transactions have been recorded, the contents of the buffer are read by software by means of interrupts or software polling, allowing the next sampling. The status information read by the software is statistically analyzed by the profiling application software to obtain statistical data. Then, the statistical data is analyzed, and the performance problem in the running program is dynamically optimized by a method such as recompilation.

[0009]

One of the conventional problems is as follows.
The amount of data that must be stored in order to obtain statistical data of events that is useful for improving performance is large, and the cost of storage is high. The reason is that the prior art 1 requires a trace file having a capacity capable of storing all the samples relating to the occurred event, and the prior art 2 stores the intermediate results of the access count and the cache miss count for each memory address. This is because large-capacity cache miss information is required, and the related art 3 requires a file or the like that can store all the data read from the state information storage buffer.

Another problem in the prior art is that it is difficult to quickly obtain statistical data of events useful for improving performance during actual operation. The reason is that the prior art 1 and the prior art 3
This is because statistical data is obtained by performing statistical processing after collecting all samples. Also, the calculation of the statistical data of the event useful for the performance improvement may be postponed to the calculation of the statistical data of the event not useful for the performance improvement. Here, the statistical data of an event that does not contribute to the performance improvement is statistical data of a continuous area / access type event of a memory with a small number of accesses in the related art 1. Note that the prior art 2 uses a simulator, so that it is essentially impossible to obtain statistical data of an event during the actual operation of a program.

An object of the present invention is to provide a processor performance data collecting apparatus capable of quickly and at low cost obtaining statistical data of an event useful for performance improvement during actual operation.

Another object of the present invention is to provide an optimization method using the processor performance data collection device of the present invention.

[0013]

According to the present invention, there is provided a processor performance data collecting apparatus, comprising: an extracting unit memory for storing statistical data of a fixed number of events having a large effect on the performance degradation of a processor among statistical data of events; Receiving data on events that occurred during actual operation from the processor, and among the statistical data of events calculated up to now, statistical data of a fixed number of events having a large effect on the performance degradation of the processor remains in the extraction unit memory. And control means for updating statistical data of events and replacing statistical data of events.

[0014] The statistics of events that occur in a processor can generally be divided into those that help improve performance and those that do not. For example, when improving the performance of software based on the access frequency, statistical data of events indicating that the number of accesses is large because the effect of improving the heavy processing parts or frequently accessed variables and data structures is greater. Helps to improve performance. Also, when improving the performance of software based on cache miss information,
Statistical data of events with a large cache miss ratio is useful for improving performance. Further, when the performance of software is improved based on the speculation failure rate of each speculative event in a speculatively executable processor, statistical data of events having a large speculation failure rate is useful for performance improvement. In other words, the statistical data of an event that is useful for improving performance can be said to be statistical data of an event that has a large effect on the performance degradation of the processor. Therefore, in the processor performance data collection device of the present invention, among the statistical data of the events calculated up to now, the statistical data of a certain upper number of events having a large effect on the performance degradation of the processor remains in the extraction unit memory. Updates statistical data and replaces statistical data of events. As a result, the limited capacity of the extraction unit memory is effectively used, and statistical processing and collection are performed in parallel, so that statistical data of events useful for improving performance can be collected quickly and at low cost during actual operation. Can be.

If only the extractor memory is used as a place for storing the statistical data of the events calculated up to now, after the extractor memory becomes full, it is necessary to store the statistical data of new events in the extractor memory. An operation to overwrite the statistical data of the event already recorded is required. Even if such an operation is performed, the collection accuracy is reduced, but some of the statistical data of events having an extremely large effect on the performance of the processor can be collected. However, in order to increase the collection accuracy, an auxiliary storage location other than the extraction unit memory is required. The present invention provides a method of using a circulating memory, a method of utilizing an instruction cache in a processor, or a method of using both as auxiliary storage locations.

In the case where the circulating unit memory is used, the extracting unit memory stores statistical data of a certain number of upper-order events which have a large effect on the performance degradation of the processor and whose statistical reliability satisfies the criterion. The memory temporarily stores the statistical data of events whose statistical reliability does not yet meet the criteria or does not fall into the upper fixed number. Whether the statistical reliability satisfies the criterion is determined by, for example, whether the number of appearances is equal to or greater than a certain threshold. The control means receives data on the occurred event from the processor, and among the statistical data of the events calculated up to the present, the statistical data of a fixed number of events having a large influence on the performance degradation of the processor remains in the extraction unit memory. In this way, the update of the statistical data of the event, the exchange of the statistical data of the event between the traveling unit memory and the memory of the extraction unit, and the exchange of the statistical data of the event in the memory of the extraction unit are performed. Specifically, the control unit secures an empty entry in the traveling unit memory when the statistical data of the event received from the processor is not stored in any of the extraction unit memory and the traveling unit memory. The statistical data of the event is registered, and when stored in the traveling unit memory, the stored statistical data of the event is updated and the traveling unit memory and the extraction unit memory are updated as necessary. The statistical data of the event is replaced, and when stored in the extraction unit memory, the stored statistical data of the event is updated.

When both the circulating unit memory and the instruction cache are used, the extracting unit memory stores the statistical data of a certain number of upper-ranked events which have a large effect on the performance degradation of the processor and whose statistical reliability satisfies the standard. An area where statistical data of events whose statistical reliability does not yet meet the standard or does not fall in the upper fixed number is temporarily stored in the circulating unit memory, and is added for each cache line of the instruction cache. Then, in order to narrow down the events registered in the traveling unit memory, simple statistical data on events not registered in either the extraction unit memory or the traveling unit memory is held. The control means receives data on the occurred event from the processor, and among the statistical data of the events calculated up to the present, the statistical data of a fixed number of events having a large influence on the performance degradation of the processor remains in the extraction unit memory. Thus, the update of the statistical data of the event, the exchange of the statistical data of the event between the traveling unit memory and the memory of the extracting unit, the exchange of the statistical data of the event of the memory of the extracting unit, and the update of the simple statistical data are performed. Specifically, when the statistical data of the event received from the processor is not stored in any of the extraction unit memory and the traversing unit memory, the control unit is configured to store the instruction related to the event in the cache line. When the simplified statistical data is updated and the updated simplified statistical data satisfies a certain criterion, a free entry is secured in the traveling unit memory and the statistical data of the event is registered, and stored in the traveling unit memory. When the stored statistical data of the event is updated, the statistical data of the event is exchanged between the traveling unit memory and the extracting unit memory as necessary, and is stored in the extracting unit memory. If so, the stored statistical data of the event is updated.

In the case where only the instruction cache is used, the extractor memory stores statistical data of a certain number of upper-ranked events that have a large effect on the performance degradation of the processor and satisfy a criterion of statistical reliability. In order to narrow down the events registered in the extraction unit memory, simple statistical data on events not registered in the extraction unit memory is held in the area added for each cache line. The control means receives data on the occurred event from the processor, and among the statistical data of the events calculated up to the present, the statistical data of a fixed number of events having a large influence on the performance degradation of the processor remains in the extraction unit memory. like,
The statistical data of the event is updated, the statistical data of the event in the memory of the extracting unit is replaced, and the simplified statistical data is updated. Specifically, when the statistical data of the event received from the processor is not stored in the extraction unit memory, the control unit updates and updates the simple statistical data of the cache line holding the instruction related to the event. When the subsequent simple statistical data satisfies a certain standard, an empty entry is secured in the extracting unit memory, and the statistical data of the event is registered. When the event statistical data is stored in the extracting unit memory, the event is stored. Update event statistics.

The extractor memory and the traveling unit memory are preferably constituted by an associative memory which can be searched by the type of event (for example, an instruction address). In addition, the statistical data of the events in the extraction unit memory are preferably arranged in descending order of the effect on the performance degradation of the processor. The statistical data of the event includes, for example, the number of appearances of the event, the number of failures of the event, and the failure rate. Here, the events include a cache access instruction and a speculative execution instruction. The event statistical data may further include additional information indicating a cost required to rewind the failed event. In the case of a speculative event, the cost is the number of instructions to be rewound or the amount of data loaded during speculation as additional information.

Further, the optimization method using the processor performance data collection device of the present invention optimizes when the program is recompiled based on the statistical data of the events collected during the actual operation of the program by the processor performance data collection device described above. Fixing allows for dynamic performance tuning.

[0021]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

(First Embodiment) In this embodiment, during actual operation of a processor for performing speculative execution, statistical data of speculative performance which is a problem in performance is collected in parallel with the processing of the processor.
Performance tuning is performed based on the collected statistical data.

Speculative execution means that speculative processing is input in advance in accordance with the motion prediction, and if the prediction is incorrect, the result of the speculative execution is canceled and the correct processing is redone as necessary, thereby obtaining the result. Is a processing method that guarantees the validity of Speculative execution is classified into control speculation and data speculation.
The control speculation is a method of ignoring the control dependence and starting the execution of the instruction in advance, and the data speculation ignoring the data dependence and predicting the value of the data or the address of the data and starting the execution. Is the way. A typical example of speculative execution is branch prediction in which a branch destination is predicted before execution in a conditional branch instruction in a program. Branch prediction is classified into static branch prediction predicted at compile time and dynamic branch prediction predicted at execution time. The present embodiment uses a static prediction method of determining a processing part for performing control speculation and data speculation at the time of compilation. Hereinafter, speculative execution based on static prediction, which is a premise of the present embodiment, will be described.

FIG. 1 shows the start Strat of a certain program.
The execution flow from 1 to end 2 is shown.
In this execution flow, the conditions of the condition judgment 4a and the condition judgment 4b are not determined until the process 3a is completed.
Therefore, when the process 3c is performed simultaneously with the process 3a,
The execution of the process 3c is a control speculation. Instead of processing 3b,
The reason for speculation in the process 3c is that it is determined that the process 3c has higher speculation certainty based on static prediction at the time of compilation. On the other hand, since the process 3e is always executed without depending on the results of the condition judgments 4a and 4b, control speculation is unnecessary. However, if the process 3a and the data are dependent, the process 3e is executed at the same time as the process 3a. Execution of the process 3e is data speculation. In the static prediction, such data dependence can be predicted, and performance can be improved by performing speculative execution of a predicted portion. Therefore, when the processing 3c and the processing 3e are executed simultaneously with the processing 3a, both the control speculation and the data speculation are performed.

As a method of executing a program in which a processing part for performing control speculation and data speculation is determined by static prediction, for example, a thread execution method described in Japanese Patent Application Laid-Open No. 10-27108 (hereinafter referred to as Reference 4) is used. is there. In Patent Document 4, a process allocation unit is called a thread, and a plurality of threads in a parent-child relationship are executed in parallel using a plurality of thread execution units. At this time, if it is not known that the child thread will be reliably generated until the processing of the parent thread is determined to some extent, the child thread is generated speculatively, and the child thread is temporarily generated depending on how the processing of the parent thread proceeds. Commit or cancel a child thread. Therefore, a speculative thread generation instruction for speculatively generating a child thread before the parent thread is determined to be valid for program execution, and a speculation for transmitting the result to the child thread after the validity is confirmed. Special instructions such as a success notification instruction and a speculative failure notification instruction for canceling the execution of the child thread in the case of improper generation are prepared. The thread execution unit is provided with a mechanism for canceling an action associated with the execution, and executes a thread temporarily within a range permitted by the function. Further, when the thread execution unit of the parent thread executes the speculative success notification instruction, the information is transmitted to the thread execution unit executing the child thread, and the child thread execution unit transitions to the normal state, while the parent thread executes When the thread execution unit executes the speculation failure notification instruction, the information is transmitted to the thread execution unit that is executing the child thread, cancels the execution of the child thread, and also generates a thread in the thread execution unit of the parent thread. I try to return to the state that has not been.

FIG. 2 shows an operation example when speculation is successful, and FIG. 3 shows an operation example when speculation fails. FIG.
, The thread # 0 is a speculative thread generation instruction 11
Is executed, the thread # 1 is generated, the execution of the thread # 1 is started in the temporary execution state, and the thread # 0 enters the thread temporary generation state. When the thread generation instruction 12 is executed in the temporary execution state of the thread # 1, the thread # 2 generated thereby also inherits the temporary execution attribute of the thread # 1 and is executed in the temporary execution state. After the thread # 0 executes the conditional branch instruction 13, when the speculative creation of the thread is determined to be correct by the conditional branch, the speculative success notification instruction 14 is executed. As a result, thread # 1, thread # 2
Is released, and the thread # 0 enters a thread generation state.

In FIG. 3, the execution is performed in the same manner, but the conditional branch instruction 13 branches in the reverse direction, thereby confirming that the speculation of thread generation is incorrect. At this time, the thread # 0 executes the speculation failure notification instruction 15. As a result, the execution of the thread # 1 and the thread # 2 is canceled. By executing the speculation failure notification instruction 15,
The thread # 0 returns from the thread temporary generation state to the thread non-generation state, and can execute the thread generation instruction 16 again to generate the thread # 3. Note that writing to a shared memory or the like is suppressed so that speculative execution does not cause a side effect when speculative thread generation fails, and a separately provided temporary execution buffer is used instead.

Referring now to FIG. 4, an example of a processor 25 to which the present invention is applied is provided to an MPU operation execution unit 20 via a speculative instruction bus 22, an additional information bus 23, and a result access bus 24. It has a configuration in which a speculative information collecting device 21 which is one embodiment of a processor performance data collecting device according to the present invention is connected.

The MPU operation execution unit 20 is one in which a data collection unit 27 and an optimization unit 28 are incorporated in a processor having a function of performing speculative execution as described above.
The data collection unit 27 outputs the following information to the speculative information collection device 21 during execution of the program on the MPU operation execution unit 20.

(1) At the start of the speculative processing Each time the speculative processing is started during the execution of the program on the MPU operation execution unit 20, the event is detected, and the fact that the speculative processing has been started and the address of the speculative instruction are determined. Speculation instruction bus 22
To the speculation information collection device 21 through The target speculative processing includes, for example, the speculative thread generation instruction 11 shown in FIGS. Of course, other speculative processing such as a memory load instruction or a conditional branch instruction that is executed speculatively can also be targeted.

(2) At the end of the speculative processing Each time the speculative processing is completed during execution of the program on the MPU operation execution unit 20, the event is detected, and the fact that the speculative processing is completed is described as a completion type (success completion or failure). Completion type) and the speculative instruction address are output to the speculative information collecting device 21 through the speculative instruction bus 22. For example, in the case of FIG. 2, the speculative process related to the speculative thread generation instruction 11 is completed successfully at the time of execution of the speculative success notification instruction 14, so that the speculation process is completed, the completion of the speculation is completed, and the speculative thread generation instruction 1
In the case of FIG. 3, the speculative process relating to the speculative thread generation instruction 11 is completed at the time of execution of the speculative failure notification instruction. In the case of FIG. The address of the generation instruction 11 is output.

(3) During speculative execution While speculative processing is being executed by the program on the MPU operation execution unit 20, data necessary for estimating a useless cost when the speculative processing has failed is added to the additional information. And outputs it to the speculative information collecting device 21 through the additional information bus 23 together with the speculative command address of the speculative process. The data necessary for estimating the unnecessary cost includes the number of instructions, the amount of stored / loaded data, and the like.
For example, in the case of FIG. 3, the wasteful cost when the speculative thread generation instruction 11 has failed is determined by the number of instructions executed by the threads # 1 and # 2 in the tentative execution state or stored / stored in the memory.
It can be estimated based on the amount of data loaded. In the case where the number of instructions is used as the additional information, the data collection unit 27 generates the threads # 1, ## generated by the speculative thread generation instruction 11.
Every time the instruction is executed during the period when the instruction 2 is in the provisional execution state, additional information indicating that one instruction has been executed is output with the address of the speculative thread generation instruction 11. In the case where the amount of data stored / loaded in the memory is used as the additional information, the data collection unit 27 performs memory storage during a period in which the threads # 1 and # 2 generated by the speculative thread generation instruction 11 are in the temporary execution state. Each time the / load instruction is executed, the amount of data stored / loaded is output as additional information along with the address of the speculative thread generation instruction 11.

As an implementation example of the data collecting means 27, there is a configuration in which a routine for collecting and outputting necessary information is incorporated in a program as adopted in the literature 1. However, it is desirable to adopt a configuration in which necessary information is collected and output by hardware such as that employed in Reference 3 so as not to lower the execution speed of the program. It is also possible to divert the hardware configuration described in Literature 3, and in this case, the collected information is output to the speculative information collection device 21 through the buses 22 and 23 instead of being stored in the buffer. Of course, other hardware configurations may be employed.

The speculative information collection device 21 is a hardware mechanism that operates in parallel with the MPU operation execution unit 20.
The data output from the data collection means 27 in the PU operation execution unit 20 through the speculation instruction bus 22 is input, and statistical data of speculation which causes a problem in performance is generated in an internal memory. The additional information output through the additional information bus 23 is also stored in the internal memory as a part of the statistical data. The statistical data generated on the internal memory is read from the MPU operation execution unit 20 through the result access bus 24, and is used for optimization of the program by the optimization unit 28.

Referring to FIG. 5, the speculative information collecting device 21
Is an association table 30, a speculative probability data update circuit 43,
Extraction unit transfer limit register 44, replacement candidate determination circuit 4
5. Additional information updating circuit 46, result access control circuit 48
And a speculation instruction processing circuit 49.

The associative table 30 is a fully associative associative memory having n + m entries. Of the n consecutive entries, the extractor associative memory 31 is composed, and the remaining m entries are the cyclic associative memory. 32 are configured. Finally, the extraction unit associative memory 31 stores the statistical data relating to the top n speculative executions that have a large effect on the deterioration of the execution performance. Circuit associative memory 32
Is used to temporarily store statistical data for which the statistical reliability is not yet sufficient or which does not fall into the top n even if the reliability is sufficient.

Each entry of the association table 30 is associated with an association key unit 33.
And a data section. The data section is divided into a speculation probability data section 34, an order / LRU information section 35, and an additional information section 36. The associative key section 33 has a speculative instruction address 3
7 is registered, and the speculative probability data section 34 stores the number of occurrences 38 of the speculative execution uniquely specified by the speculative instruction address.
And a failure rate 39 indicating the ratio of the failure frequency 39 to the appearance frequency 38. In the order / LRU unit 35, order information is registered in the extraction unit associative memory 31. That is, the entries in the extraction unit associative memory 31 are logically arranged in ascending order of the failure rate 40 according to the order information registered in the order / LRU information unit 35, as shown in FIG. In FIG. 6, reference numeral 61 denotes a pointer indicating the entry 60 having the smallest failure rate among the n entries, and is provided in the replacement candidate determination circuit 45.

Further, in the traveling unit associative memory 32, the order / L
The LRU information is registered in the RU information section 35, and the entry that has not been referred to for the longest time is reused according to the LRU algorithm. That is, as shown in FIG. 6, the recurring unit associative memory 32 composed of m entries is logically arranged in order from the most recently referred to, and indicates the entry 62 that has not been referred to for the longest time. The replacement candidate determination circuit 45 having the pointer 63 uses the pointer 63 to determine an entry to be overwritten in the recurring unit associative memory 32 by the LRU method.

Further, in the additional information section 36, additional information 41 such as a data amount for rewinding generated during speculation is registered. The additional information section 36 has a cumulative value (referred to as a total cumulative value) of additional information relating to all speculative executions that have failed up to the present time, and a cumulative value (referred to as a current cumulative value) of additional information relating to the currently executing speculative execution. When the currently executing speculation has been failed, the current cumulative value is added to the total cumulative value.

The speculation instruction processing circuit 49 includes a speculation instruction bus 2
2 is connected to the MPU operation execution unit 20. Each time the speculative processing start and its speculative instruction address or the speculative processing end and its speculative instruction address and completion type are sent from the data collection means 27 via the speculative instruction bus 22, the speculative instruction processing circuit 49 speculates them. At the same time as transmitting to the probability data updating circuit 43 and the additional information updating circuit 46, the speculative command address is output to the speculative command address line 42. The speculative command address line 42 is connected to the associative key section 33 of each entry of the associative table 30,
3, the speculative instruction address registered in the associative key unit 33 and the speculative instruction address on the speculative instruction address line 42 are compared, and the respective comparison results are updated via the comparison result line 26. The signal is transmitted to the circuit 43.

The speculation probability data updating circuit 43 uses the association table 3
0 is a circuit for updating the speculative probability data part 34 of each entry, and the number of occurrences 38, the number of failures 39, and the failure rate in the speculative probability data part 34 of the entry for which the match of the speculative instruction address is reported by the comparison result line 26 Update 40.
Specifically, when the notification from the speculation instruction processing circuit 49 is the start of the speculation process, the number of appearances 38 is incremented by one. Also,
If the notification from the speculation instruction processing circuit 49 is the end of the speculation processing, and if the completion type is failure completion, the number of failures 39
After +1 is added, if the completion is successful, the failure rate 40 is not calculated and the failure rate 40 is recalculated and registered again. The replacement candidate determination circuit 45 specifies the entry.
Activate the replacement process. If none of the comparison result lines 26 indicate a match, that is, if the speculative instruction address output to the speculative instruction address line 42 is not registered in the association table 30, the speculative probability data update circuit 43 A request for securing the entry in the traveling unit associative memory 32 is issued, and the data portion of the secured entry is initialized.

When the replacement process is started by the speculation probability data updating circuit 43, the replacement candidate determination circuit 45 performs the following process. (1) If the current entry whose failure rate 40 has been updated is an entry included in the extraction unit associative memory 31, the m entries in the extraction unit associative memory 31 have the failure rate 40 value as described with reference to FIG. And updates the order information and the pointer 61 of the order / LRU information section 35 as necessary so that they are logically arranged in ascending order. (2) If the current entry whose failure rate 40 has been updated is an entry included in the traveling unit associative memory 32, it is determined whether or not it is necessary to replace the entry with the entry in the extracting unit associative memory 31. When the following conditions are satisfied, it is determined that replacement is necessary. (A) The number of appearances 38 of the entry is equal to or greater than the threshold value set in the extraction unit transfer limit register 44. (B) The failure rate 40 of the entry is equal to or greater than the failure rate 40 of the entry 60 having the minimum failure rate indicated by the pointer 61 in FIG. Then, when the above conditions (a) and (b) are satisfied, the contents registered in the entry and the contents registered in the entry 60 of the minimum failure rate of the extraction unit associative memory 31 are exchanged.

Here, the reason why the condition (a) is defined is that when the number of appearances 38 is smaller than a certain value, the failure rate 40 thereof is not yet sufficiently statistically reliable. By taking this condition into account, it is prevented that statistical data having a high statistical reliability is expelled from the extracting unit associative memory 31 by statistical data having a low statistical reliability.

On the other hand, when there is a request for securing an entry from the speculative probability data update circuit 43, the replacement candidate determination circuit 45 determines that the order / LRU information section 35 of the n The entry that is not referred to, that is, the entry 62 indicated by the pointer 63 in FIG. Then, the present speculative instruction address is registered in the associative key section 33 of the entry 62 by the associative key update instruction line 50, and the additional information section 36 of the entry 62 is initialized through the additional information updating circuit 46. 62 is notified to the speculation probability data update circuit 43.

The replacement candidate determination circuit 45 is provided in the additional information updating circuit 46 every time a new speculative instruction address is registered in the associative key section 33 of an entry in the associative table 30 and each time an entry is replaced. The correspondence table (not shown) between the entry and the speculative instruction address is updated. Also, regardless of whether or not the entry was actually swapped,
When the replacement process is completed, the fact is notified to the additional information updating circuit 46.

The additional information updating circuit 46 is connected to the additional information bus 2
3 is connected to the MPU operation execution unit 20. Each time additional information with a speculative instruction address is sent from the data collection means 27 through the additional information bus 23, the additional information updating circuit 46 refers to the correspondence table for the entry in which the speculative instruction address is registered. Then, the additional information is accumulated in the current accumulated value in the additional information section 36 of the entry. When the speculative instruction address of the failed completion is notified from the speculative instruction processing circuit 49, after receiving the notification that the replacement process is completed from the replacement candidate determination circuit 45, the speculative instruction address of the failed completion is registered. The entry that has been specified is specified with reference to the correspondence table, and the current cumulative value in the additional information section 36 of the entry is added to the total cumulative value.

The result access control circuit 48 is connected to the MPU execution unit 20 through the result access bus 24,
Each entry of the extraction unit associative memory 31 of the associative table 30 is connected to the extracting unit associative memory 31 of the associative table 30 by a result access line 47 including a data line and an address line. Can be read. Further, it is also connected to the extraction unit transition limit register 44, so that a threshold value can be set in advance in the extraction transition limit register 44 from the MPU operation execution unit 20.

Next, an overall operation flow of the speculative information collecting apparatus 21 will be described below with reference to FIGS. 7 and 8.

Data collection means 2 of MPU operation execution unit 20
7, the start of the speculative processing and the speculative instruction address are sent via the speculative instruction bus 22 (S1), and the speculative instruction processing circuit 49 uses the speculative instruction address to associate the associative table 3
The associative key unit 33 of 0 is searched (S2). If there is no entry having the speculation instruction address in the associative key unit 33 (NO in S3), the replacement candidate determination circuit 45
Is determined as the entry to be written out of the entry 62 that has not been referred to for the longest time among the entries of the recurring unit associative memory 32 (S4), and the entry is initialized (S5).
That is, the present speculation instruction address is registered in the associative key unit 33 of the entry 62 by the replacement candidate determination circuit 45, and the additional information unit 36 is registered by the additional information updating circuit 46.
Is initialized, and the speculative probability data updating circuit 43 sets the number of appearances 38 in the speculative probability data section 35 of the entry 62 to the value “1”, the number of failures 39 to the value “0”, and the failure rate 4
The value “0” is registered in “0”. The order / L of the entry 62 is determined by the replacement candidate determination circuit 45.
The LRU information of the RU information section 35 is updated (S8).

On the other hand, if an entry having the speculative instruction address in the associative key section 33 already exists (Y in S3)
ES), the speculation probability data update circuit 43 increments the number of appearances 38 of the entry in the speculation probability data section 34 by 1 (S6). Next, the entry is stored in the traveling unit associative memory 3.
If the entry is No. 2 (YES in S7), the replacement candidate determination circuit 45 updates the order / LRU information in the LRU information section 35 of the entry (S8).

Thereafter, each time additional information accompanied by the speculative instruction address registered in the entry is sent from the data collection means 27 of the MPU execution unit 20 via the additional information bus 23, the additional information updating circuit 46 A process of accumulating the current additional information on the current accumulated value in the additional information section 36 of the entry having the speculative instruction address is performed.

Next, when the end of the speculative processing and the speculative command address and the completion type are sent from the data collecting means 27 of the MPU operation executing section 20 via the speculative instruction bus 22 (S11), the speculative instruction processing circuit 49 The associative key section 33 of the associative table 30 is searched with the speculative instruction address (S12). The entry having the speculation instruction address is always secured at the time of the start of the speculation, and the LRU information thereof has been updated. Therefore, by setting the number of entries m of the traveling unit associative memory 32 to a certain number or more, The search always succeeds. Next, the speculative probability data updating circuit 43
Only when the completion type is failure completion, the failure count 39 of the retrieved entry is incremented by 1, and then the failure rate 40 is updated (S13). Thereafter, the process is divided depending on whether the entry is an entry in the extraction unit associative memory 31 or an entry in the traveling unit associative memory 32.

If the entry is in the extraction unit associative memory 31 (YES in S14), the replacement candidate determination circuit 45
Means that the failure rate 40 of the entry is
Then, it is determined whether or not the failure rate 40 of the next higher entry has exceeded (S15), and if so, the order of the next higher entry and the entry concerned is exchanged (S16).

If the entry is in the traveling unit associative memory 32 (NO in S14), the replacement candidate determination circuit 45
It is determined whether the number of appearances 38 of the entry has exceeded a threshold value set in the extraction unit transfer limit register 44 (S1).
7) If not exceeded, the LRU information of the entry is updated (S18), and the process ends. If so, it is checked whether the failure rate 40 of the entry exceeds the lowest failure rate of the extraction unit associative memory 31 (S19). If not, the LRU information of the entry is updated (S1).
8) Finish the processing. If the lowest failure rate is exceeded, the entry and the entry with the lowest failure rate in the extraction unit associative memory 31 are exchanged (S20), and the LRU information of the entry transferred to the traveling unit associative memory 32 is updated (S2).
1), end the process.

When the speculative process has been completed with failure, the additional information updating circuit 46 adds the current accumulated value of the additional information section 36 in the entry having the failed speculative instruction address to the total accumulated value, and adds the current accumulated value. Initialize to 0.

The above operation is performed by the speculative information collecting device 21.
Finally, the extraction unit associative memory 3
1, the top n speculative instruction addresses having a high failure rate, the number of appearances, the number of failures, the failure rate, and the additional information remain.

Next, the optimizing means 28 for performing performance tuning using the statistical data collected in the extracting unit associative memory 31 of the speculative information collecting apparatus 21 will be described.

FIG. 9 schematically shows the positioning of the optimizing means 28 in the system operation and the processing. The source program or its intermediate code 200 is compiled by an existing compiler 201, and an execution module 202 is generated. At this time, speculation with high certainty is predicted by analyzing the character face of the program and further using the profile 203, and the program is optimized. For example, Japanese Patent Application Laid-Open No. H8-241198 (hereinafter, referred to as Document 5) describes a profile-based optimization technique. In Document 5, a profile 203 is generated by generating a profiler executable object from a source program and temporarily executing the object.
The optimization is performed by recompiling the source program with reference to. However, even if such a profile-based optimization is performed, an optimum result is not always obtained. The reason is that, in actual operation using the execution module 202, various types of actual data 204 are used for each user, but such realistic and varied data is prepared during provisional execution for profile generation. Is difficult and hence the profile 2 generated
This is because 03 differs from the actual operation.

Therefore, in this embodiment, when the execution module 202 using the actual data 204 is actually operated (205), the speculative information is collected by the speculative information collecting device 21 as described above, and based on the collected speculative information. Optimization means 28
Realizes dynamic optimization according to the real environment of each user by optimizing the program again. That is, the optimizing unit 28 accesses the extraction unit associative memory 31 of the speculative information collecting apparatus 21 through the result access bus 24 and the result access control circuit 48, and obtains statistical data on the top n speculative events having a high failure rate. (206) The source or intermediate code 200 is recompiled with reference to the obtained statistical data to generate the optimized execution module 202. The re-optimization by the optimizing unit 28 may be automatically performed each time the execution of the execution module 202 ends, or may be performed when an instruction to that effect is input from the user.

In this embodiment, since the statistical data relating to the top n speculative events having a high failure rate has already been obtained at the end of execution of the execution module 202, the statistical data of each speculative event at the time of optimization as in the prior art is obtained. It is not necessary to select a speculative event having a high failure rate from the data. Also, order /
According to the order information of the LRU information section 35, the sorting is performed in descending order of the failure rate. Therefore, it is unnecessary to rearrange the selected speculative events in the descending order of the failure rate. Therefore,
For example, if the failure rate 40 is equal to or more than a certain reference value, the optimization is redone in order from the speculation event having the higher failure rate, and the optimization should be performed at the time when the failure rate 40 reaches the speculation event less than the reference value. Efficient processing for determining the end of a speculative event is also possible.

Further, in this embodiment, since the cumulative value of the additional information for each speculative failure is accumulated in all the cumulative values of the additional information section 36, the total cumulative value is divided by the number of failures 39 to obtain one failure. It is possible to estimate the wasteful cost per unit.
For this reason, a process in which the failure rate 40 is equal to or more than a certain reference value, and a speculation event having a low cost of re-speculation has few problems in performance and is excluded from the target of reoptimization,
It can be performed based on the additional information.

Next, a specific example of re-optimization by the optimization means 28 will be described.

(1) Re-optimization of control speculation For example, the execution module 202 for performing the speculation execution shown in FIGS. 2 and 3 is generated by the optimization processing of the compiler 201 using the profile 203.
It is assumed that the statistical data indicating that the failure rate of the speculative thread generation instruction 11 is equal to or more than a certain reference value and the cost of re-speculation is equal to or more than a certain reference value during the actual operation using the speculation information collection device 21. I do. In this case, the optimization means 28
Is optimized to speculatively execute thread # 3 instead of speculative execution of threads # 1 and # 2 by using a speculative thread generation instruction for generating thread # 3 instead of speculative thread generation instruction 11. I do.

(2) Re-optimization of Data Speculation For example, as shown on the left side of FIG. 10 by the optimization processing of the compiler 201 using the profile 203, the thread # 2 generated by the thread generation instruction 210 of the thread # 1 And two speculative memory load instructions 212 and 21
Execution module 20 optimized to execute 3
It is assumed that statistical data indicating that the failure rate of the speculative memory load instruction 213 is equal to or more than a certain reference value during actual operation using the actual data 204 is collected by the statistical information collection device 21. In addition, the MPU operation execution unit 20 executes a thread # 2 in a speculative state in order to reduce the amount of hardware.
Is not saved, but only the execution state immediately before executing the speculative memory load instruction 212 for executing the first load is saved. If the speculation of the instruction 213 fails, the first speculative memory load instruction 2
It is assumed that a method of rewinding to the state of the speculative memory load instruction 213 by rewinding to 12 and re-executing the instruction immediately before the speculative memory load instruction 213 is adopted. Then, when many instructions are interposed between the speculative memory load instruction 212 and the speculative memory load instruction 213, the cost of re-speculation due to the failure completion of the speculative memory load instruction 213 increases.

In this case, the optimizing unit 28 can select to eliminate the speculative execution by stopping the insertion of the thread generation instruction 210 and sequentially performing the processing performed by the thread # 2 after the thread # 1. Then, the processing before the speculative memory load instruction 213 of the thread # 2 is also performed by the thread # 2.
1 cannot be executed in parallel, and the performance may return and deteriorate. Therefore, if the speculative memory load instruction 212 is not included in the top n failure rates, the optimizing unit 28 determines that the parallel processing of the thread # 1 and the thread # 2 contributes to the performance improvement. As shown on the right side of FIG. 7, the thread generation instruction 214 is inserted before the speculative memory load instruction 213 having a high failure rate, and the speculative memory load instruction 213 is moved to the head of the newly generated thread # 3. Perform re-optimization. If the actual data 204 does not change even in the program after the reoptimization, the failure rate of the speculative memory load instruction 213 remains high, but the speculative memory load instruction 213 is used as the first speculative memory load instruction of the thread # 3. As a result, the amount of rewinding when speculation fails is reduced, and as a result, performance is improved.

If the speculative memory load instruction 213 is detected as a high failure rate in the following actual operation, it is excluded from the reoptimization target because the rewind amount is small, or a similar reoptimization is performed. Is repeated. In order to prevent the same re-optimization, the compiler 201 and the optimizing unit 28 record in the database the location and the reason why the optimization has been performed. It is sufficient to check whether measures have already been taken at the time of conversion.

As described above, the speculative information collecting apparatus 21 of the present embodiment includes the extracting unit associative memory 31 for storing the statistical data of the top n speculative events having a high failure rate and satisfying the statistical reliability. And a traveling unit associative memory 32 for temporarily storing statistical data of speculative events whose statistical reliability does not satisfy the criteria or fall into the top n, and executes MPU operation on data relating to the speculative events that have occurred. Part 20
When the statistical data of the speculative event is not stored in any of the extraction unit associative memory 31 and the traveling unit associative memory 32, an empty entry is secured in the traveling unit associative memory 32 and the statistical information of the speculative event is received. Register the data. Since the entries in the traveling unit associative memory 32 are reused for storing statistical data of different speculative events, some speculative events are registered once in the traveling unit associative memory 32 and then expelled. Some are not counted correctly. However, most of the speculative events that are likely to be expelled from the traveling unit associative memory 32 are those whose number of appearances is equal to or less than the reference or whose number of executions is small. 32 to the extraction unit associative memory 31 without being expelled. As a result, even if the total number of entries (n + m) in the extraction unit associative memory 31 and the cyclic unit associative memory 32 is smaller than the number of speculative events (the number of speculative instructions),
Statistical data of the top n speculative events with a high failure rate can be collected almost certainly. This makes it possible to collect statistical data useful for improving performance with a small amount of memory.

If the number n of entries in the associative memory 31 of the extraction unit and the number m of entries in the associative memory 32 of the circulating unit are too small, the memory amount can be reduced, but the risk of omission of collection increases. For this reason, it is desirable to determine the minimum values of n and m by preliminary experiments.

When the lower limit of the number of entries n and m is determined, the memory capacity is determined by the capacity per entry × the number of entries.
In order to further reduce the memory amount, it is necessary to reduce the capacity per entry. Hereinafter, a method for realizing the capacity per entry by reducing the number of bits required for the failure rate 40 will be described.

Now, the number of appearances 38 and the number of failures 39 are 3
Assuming that 2-bit data is stored in the association table 30, the possible value of the failure rate 40 obtained by dividing the number of failures 39 by the number of appearances 38 is 1.0 from 2 to the power of -32.
It is a decimal value up to. If this is registered in the failure rate 40 as it is, a large number of bits is required. Therefore, the failure rate 40 is focused on the fact that the replacement of the entries in the associative table 30 should be roughly determined, and the dynamic range of the value is wide, but the number of significant digits is not so necessary, and the failure rate 40 is shown in FIG. 4 bits of the mantissa binary notation 51 are represented by a mantissa 53, and 5 bits of the exponent binary notation 52 are represented by an exponent 54.
Is recorded in the failure rate 40 with a total of 9 bits. As a result, the amount of memory per entry, and consequently, the association table 3
0 overall capacity can be reduced.

FIG. 12 shows an example of a method for calculating the failure rate 40 expressed in the shortened floating-point format as shown in FIG. In FIG. 12, an expression 90 is a calculation expression of the failure rate 40, and the expression form of each value is also described in a subscript form.
The failure rate 40 is calculated as follows.

As shown in (1) of FIG. 12, the LSB side 4 bits following the most significant non-zero bit of the number of failures expressed as a 32-bit unsigned integer are used as a mantissa part S91, and a 32-bit code is also used. Four bits on the LSB side following the most significant non-zero bit of the number of appearances expressed as a null integer are extracted as the mantissa part T93. At the same time, the shift amount of the most significant non-zero bit between the number of failures and the number of appearances is set as a provisional exponent P (92).

As shown in FIG. 12 (2), the mantissas S and T are divided, and the resulting mantissa binary notation 51 is obtained. For P, the correction 94 of the temporary exponent part P is subtracted, and the exponent part binary notation 52 is obtained. Mantissa division 9
5 can be executed at high speed by referencing and adding two small tables as follows, for example. (A) Calculation of the upper division result A by referring to the first table (96) and calculation of the upper division result B by referring to the second table (97). Here, the first table is 96
The second table is a table that holds 97 calculation data. (B) Calculation of the mantissa part R by adding the results A and B (98). (C) When the most significant bit R0 of the above result R is 0,
1 is subtracted from the correction 94 of the temporary exponent P.

(Second Embodiment) As in the first embodiment, during the actual operation of a processor that performs speculative execution, statistical data of speculative performance, which is a performance problem, is collected in parallel with the processing of the processor. An embodiment in which the present invention is applied to a system for performing performance tuning based on the collected statistical data will be described. The difference from the first embodiment is that the number of entries m in the recurring unit associative memory 32 of the associative table 30 can be reduced at low cost by using the instruction cache inherent in the MPU operation execution unit 20 for storing the failure rate. The point is that it can be increased equivalently.

FIG. 13 shows a processor 2 to which the present embodiment is applied.
5 shows a configuration example. 4 is different from FIG. 4 in that a simple failure rate update circuit 131 and a limit register 132 for controlling registration of a failure rate in the instruction cache 130 and the like are provided in the MPU operation execution unit 20, and the management failure rate update circuit 131 is transferred. This is a point connected to the speculation information collection device 21 through the bus 133. The configuration of the speculative information collecting device 21 is the same as that shown in FIG. 5 except for some functions described later, and the transfer bus 133 is connected to the speculative probability data updating circuit 43 inside the speculative information collecting device 21.

Referring to FIG. 14, instruction cache 13
0 is composed of an instruction cache data array 100 and an instruction cache tag array 101, and each instruction cache line 102i to 102i of the instruction cache tag array 101
Simple failure rates 104i to 104 of speculative events every 102k
An area for registering k is newly added. In the first embodiment, when an entry having the same speculative instruction address as a newly generated speculative event does not exist in the associative table 30, the entry in the traveling unit associative memory 32 is immediately reused. The simple failure rate 104 of the instruction cache line 102 that caches the speculative instruction specified by the speculative instruction address is updated when the speculative instruction has failed, and the simple failure rate 104 is set in the limit register 132 in advance. When the threshold value is exceeded, the traveling unit associative memory 32
And secure statistical data.

The simple failure rate updating circuit 131 updates the simple failure rate 104 of the same instruction cache line 102 even if a speculative instruction different from the target speculative instruction is cached in the same instruction cache line 102. This is called a simple failure rate alias. FIG. 15 shows the transition of the simple failure rate 104.
The simple failure rate 104 takes a positive integer value from 0 to N,
When the instruction cache line 102 is refilled, and when an entry for any speculative instruction cached in the instruction cache line 102 is secured in the recurring unit associative memory 32, the simple failure rate update circuit 131 Reset to zero. Thereafter, the address of the speculative instruction cached in the instruction cache line 102 is transferred from the speculative information collecting device 21 to the transfer bus 1.
It is incremented by one each time it is transmitted through the interface 33, that is, each time a speculative instruction in the cache line not registered in the associative table 30 is completed. However, when it reaches the maximum value N, it does not increase any more (saturation addition).

Next, the flow of the entire operation of the speculative information collecting apparatus 21 of the present embodiment will be described below with reference to the flow charts of FIGS. 16 to 18, focusing on the differences from the first embodiment. .

Data collection means 2 of MPU operation execution unit 20
7, the start of the speculative processing and the speculative instruction address are sent via the speculative instruction bus 22 (S1), and the speculative instruction processing circuit 49 uses the speculative instruction address to associate the associative table 3
The associative key unit 33 of 0 is searched (S2), and if an entry already exists (YES in S3), the same operation as in the first embodiment is performed (S6 to S8). On the other hand, if there is no entry having the speculative instruction address in the associative key unit 33 (NO in S3), the process ends, unlike the first embodiment.

Thereafter, each time additional information accompanied by a speculative instruction address is sent from the data collection means 27 of the MPU operation executing unit 20 via the additional information bus 23, the additional information updating circuit 46 sets the entry having the speculative instruction address. Is performed to accumulate the current additional information in the current accumulated value in the additional information section 36 of FIG. However, if there is no entry having the speculation instruction address, the current additional information is discarded.

Next, when the end of the speculative processing and the speculative command address and the completion type are sent from the data collecting means 27 of the MPU operation executing section 20 via the speculative instruction bus 22 (S11), the speculative instruction processing circuit 49 The associative key section 33 of the associative table 30 is searched with the speculative instruction address (S12). Next, the speculative probability data update circuit 43 determines whether or not an entry having the speculative instruction address exists (S31). If the entry exists, the same operation as in the first embodiment is performed (S13). To S21). On the other hand, if it does not exist, the speculative probability data update circuit 43 checks whether or not the completion is a failure (S32).

If the failure has been completed, the speculation probability data updating circuit 43 sends the current speculation instruction address to the transfer bus 13.
3 to the simple failure rate update circuit 131. The simple failure rate update circuit 131 searches the instruction cache 130 with the transferred speculative instruction address, and increments the simple failure rate 104 of the instruction cache line 102 that caches the speculative instruction (S33). Then, it is determined whether or not the simple failure rate 104 has exceeded the threshold value set in the limit register 132 (S34), and if not, the process is terminated. If it exceeds, the simple failure rate 140 is initialized to 0 (S35). Thereafter, the simple failure rate update circuit 13
1 transfers the instruction data for registering the speculation instruction address in the association table 30 to the speculation probability data update circuit 43 through the transfer bus 133.

The speculation probability data updating circuit 43 uses the replacement candidate determining circuit 45 to determine which of the entries in the recurring unit associative memory 32 has not been referred to for the longest time.
Is determined as the entry to be overwritten (S36). And
The entry is initialized (S37). That is, the current speculation instruction address is registered in the associative key unit 33 of the entry 62 by the replacement candidate determination circuit 45, and the additional information unit 36 is initialized by the additional information updating circuit 46.
The speculation probability data update circuit 43 uses the entry 62
In the speculation probability data section 35, the value “1” is registered as the number of appearances 38, the value “1” is registered as the number of failures 39, and the value “1” is registered as the failure rate 40. Then, the replacement candidate determination circuit 45 updates the order / LRU information of the LRU information section 35 of the entry 62 (S38).

In this embodiment, although the alias of the simple failure rate exists, the event that does not cause the speculative failure is determined by the alias in the traveling unit associative memory 3 because of the determination S32.
2 will not be registered. Although there is a possibility that the speculation event A with a low speculation failure rate is registered in the traveling unit associative memory 32 by an alias with the speculation event B with a high speculation failure rate, even if it is registered, the speculation event B with a high speculation failure rate is possible. Unless is registered in the traveling unit associative memory 32, the simple failure rate 1
Since the update of 04 is continued, the speculation event B having a high speculation failure rate is eventually registered in the traveling unit associative memory 32. And
The speculation event B having a high speculative failure rate transferred to the traveling unit associative memory 32 does not contribute to the update of the simple failure rate 104 by the determination S31. Therefore, after this, after the speculative event A having a low speculation failure rate is removed from the traveling unit associative memory 32 by the LRU algorithm, the speculative event A having a low speculative failure rate is registered again in the traveling unit associative memory 32 by an alias. Never.

However, when a speculative event that is executed very frequently, although the speculative failure rate is low, is registered in the entry of the traveling unit associative memory 32 by the alias of the simple failure rate, the entry is subject to sweeping out by the LRU algorithm. Is not selected and remains, so that the utilization rate of the recurring unit associative memory 32 is reduced. In order to prevent this, in the entries of the recurring unit associative memory 32, the number of appearances 38 exceeds the value of the extraction unit transition limit register 44, and the failure rate 40 is the same as the failure rate 40 of the extraction unit end entry 60. If there is an entry that does not satisfy the ratio, a function of registering the entry as the entry that has not been updated for the longest time (the cyclic end entry 62) may be provided in the replacement candidate determination circuit 45.

In the first embodiment, the traveling unit associative memory 3
When the number m of entries is set to be small, if another speculative instruction is executed one after another before the same speculative instruction A is executed again, the speculative instruction A is already executed when the speculative instruction A is executed again. There is a possibility that A will be swept out of the traveling unit associative memory 32. When this happens, the speculation instruction A
Statistics will stay near their initial values forever,
It becomes difficult to collect statistical data. To improve this,
This is to increase the number m of entries in the traveling unit associative memory 32, but increasing the number of entries in the associative table 30 is costly in terms of hardware. According to the second embodiment, the MPU
The number of entries in the recurring unit associative memory 32 can be equivalently increased by only partially expanding the instruction cache 130 originally included in the operation execution unit 20, and it is possible to suppress an increase in cost.

Although the present invention has been described with reference to several embodiments, the present invention is not limited to the above embodiments, and various other modifications can be made. Hereinafter, a modified example thereof will be described.

In each of the above embodiments, the method using the full associative method for the association table 30 has been described.
For example, a set associative method or a direct map method can be used as in a normal cache.

In each of the above embodiments, the traveling unit associative memory 32
The method of using the LRU has been described for the replacement, but the pseudo LRU, the FIFO order, and the random replacement can be used for the replacement of the recurring unit associative memory 32 as in the case of the normal cache.

In the above embodiments, the traveling unit associative memory 32
Is set as a precondition for comparing the entry with the end entry of the extraction unit associative memory 31, the condition that the number of appearances 38 exceeds the value of the extraction unit transition limit register 44 is set. A method of comparing an entry of the unit associative memory 32 with a terminal entry of the extracting unit associative memory 31 is also possible. Also, instead of the condition that the number of appearances 38 exceeds the value of the extraction unit transition limit register 44,
The condition that the number of failures 39 exceeds a certain value may be a precondition. Further, the cost required for rewinding which is found from the additional information 41 may be taken into account.

In the above embodiments, the extraction unit associative memory 31
In the above example, the replacement of the entries is performed only by comparing the failure rate 40. However, as for the effect on the performance of the speculation event, the cost required for rewinding which is found from the additional information 41 is added to the failure rate 40. Is more effective, for example, the failure 1 obtained by dividing the total accumulated value of the additional information 41 by the number of failures 39
A value obtained by multiplying the cost per round by the failure rate may be compared.

In the first embodiment, the mechanism for deleting the recurring unit associative memory 32 from the associative table 30 and registering the simple failure rate in the instruction cache 130 used in the second embodiment is provided. It is also possible to use it instead. The processing in this case is as follows. First, M
The start of the speculative processing and the operation when the speculative instruction address is transmitted from the data collecting means 27 of the PU operation executing unit 20 via the speculative instruction bus 22 are the same as the operations in FIG. 16 in the second embodiment. On the other hand, the MPU operation execution unit 20
When the end of the speculative processing and the speculative instruction address and the completion type are transmitted from the data collecting means 27 through the speculative instruction bus 22, the operation as shown in FIG. 19 is performed.

First, the speculative instruction processing circuit 49 searches the associative key section 33 of the associative table 30 with the speculative instruction address (S12). Next, the speculative probability data updating circuit 43 finds an entry having the speculative instruction address. It is determined whether or not it has been performed (S31). If present, the first
As in the embodiment, the number of failures 39 of the entry and the failure rate 4
0 is updated (S13). Next, it is checked whether or not the failure rate 40 of the entry exceeds the failure rate of the extraction unit associative memory 31 by one rank higher (S15), and if it exceeds, the entry is replaced (S16). On the other hand, when there is no entry having the speculation instruction address (N in S31)
O), the speculative probability data updating circuit 43 checks whether or not the completion is a failure (S32). If the completion is not the failure completion, the processing is terminated. If it failed,
The speculative probability data updating circuit 43 transfers the current speculative instruction address via the transfer bus 133 to the simple failure rate updating circuit
Transfer to 1. The simple failure rate update circuit 131 searches the instruction cache 130 with the transferred speculative instruction address,
The simple failure rate 104 of the instruction cache line 102 that caches the speculative instruction is incremented by 1 (S33). Then, it is checked whether or not the simple failure rate 104 has exceeded the threshold value set in the limit register 132 (S34), and if not, the process is terminated. If it exceeds, the simple failure rate 140 is initialized to 0 (S35). Thereafter, the simple failure rate update circuit 131 transfers instruction data indicating that the speculation instruction address should be registered in the association table 30 to the speculation probability data update circuit 43 via the transfer bus 133. The speculation probability data update circuit 43 determines the entry 60 to be overwritten by the replacement candidate determination circuit 45 as the entry to be overwritten, and initializes the entry (S42). That is, the current speculation instruction address is registered in the associative key section 33 of the entry 60 by the replacement candidate determination circuit 45, the additional information section 36 is initialized by the additional information update circuit 46, and the speculative probability data update circuit 4
3, the value “1” is registered as the number of appearances 38, the value “1” as the number of failures 39, and the value “1” as the failure rate 40 in the speculation probability data section 35 of the entry 60.

In the first embodiment, the speculative events to be registered in the associative table 30 are narrowed down in advance.
It is also possible to delete the traveling unit associative memory 32 from 0. As a method of narrowing down speculative events to be registered in the association table 30 in advance, a hardware method can be used, and only speculative instructions expected to have a high failure rate in advance can be collected by a prefix instruction. A software method that is specified in the program can also be used. In this case, only the data of the limited speculation event is output from the data collection means 27 to the speculation information collection device 21. The processing is as follows. First, the start of the speculative processing and the operation when the speculative instruction address is transmitted from the data collecting means 27 of the MPU operation execution unit 20 via the speculative instruction bus 22 are the same as those in FIG. 16 in the second embodiment. . On the other hand, the data collection unit 27 of the MPU operation execution unit 20
When the end of the speculative processing and the speculative command address and the completion type are sent from the speculative instruction bus 22 via the speculative instruction bus 22, the operation shown in FIG. 20 is performed. Unlike FIG. 19, when the failure is completed, the terminal entry 60 of the extraction unit associative memory 31 is determined as an entry to be overwritten, and the entry is initialized (S42). That is, the replacement speculative instruction address is registered in the associative key section 33 of the entry 60 by the replacement candidate determination circuit 45, the additional information section 36 is initialized by the additional information update circuit 46, and the entry information is updated by the speculation probability data update circuit 43. In the 60 speculation probability data section 35, the value “1” is registered as the number of appearances 38, the value “1” is registered as the number of failures 39, and the value “1” is registered as the failure rate 40. Although the accuracy of the collection is extremely reduced in this embodiment, it is sufficient to detect only some of the speculative events whose failure rate is close to 100%.

In the above embodiment, during actual operation of a processor performing speculative execution, statistical data of speculative performance-related problems are collected in parallel with the processing of the processor, and performance tuning is performed based on the collected statistical data. The present invention is applied to a system for performing the above. In addition to this, the present invention is applicable to collection of various other statistical data and performance tuning, such as a system that collects statistical data of a memory area having a high cache miss rate and performs performance tuning based on the collected statistical data. is there.

[0096]

As described above, according to the present invention, statistical data useful for improving the performance of a memory area having a high cache miss rate and a speculative instruction having a high probability of failure can be obtained quickly in actual operation using real data. And it can be obtained at low cost. Further, it is possible to redo the dynamic optimization based on the collected statistical data.

[Brief description of the drawings]

FIG. 1 is a control flow chart of a program for explaining speculative execution.

FIG. 2 is a diagram illustrating an operation example when speculation is successful.

FIG. 3 is a diagram illustrating an operation example when speculation fails.

FIG. 4 is a block diagram showing a first embodiment of a processor to which the present invention is applied.

FIG. 5 is a block diagram showing an internal configuration of an embodiment of a speculative information collecting device.

FIG. 6 is an explanatory diagram of a method of arranging entries in an associative memory of an extraction unit and an associative memory of a circulating unit that constitute an associative table;

FIG. 7 is a flowchart illustrating an operation example of the speculative information collecting apparatus at the time of starting execution of a speculative command according to the first embodiment.

FIG. 8 is a flowchart illustrating an operation example of the speculative information collecting device at the end of execution of a speculative instruction according to the first embodiment.

FIG. 9 is a diagram showing an outline of the positioning of the optimization means in system operation and an outline of processing;

FIG. 10 is a diagram illustrating an example of re-optimization.

FIG. 11 is a diagram showing a shortened floating-point format expressing a failure rate.

FIG. 12 is a diagram illustrating an example of a method of calculating a failure rate.

FIG. 13 is a block diagram illustrating another example of a processor to which the present invention has been applied.

FIG. 14 is a configuration diagram of an instruction cache extended to store a simple failure rate.

FIG. 15 is an explanatory diagram of transition of a simple failure rate.

FIG. 16 is a flowchart illustrating an operation example of a speculative information collecting apparatus at the time of starting execution of a speculative command according to the second embodiment.

FIG. 17 is a flowchart showing an operation example of the speculative information collecting device at the end of execution of a speculative command according to the second embodiment.

FIG. 18 is a flowchart illustrating an operation example of a speculative information collection device at the end of execution of a speculative command according to the second embodiment.

FIG. 19 is a flowchart showing another example of the operation of the speculation information collection device at the end of execution of a speculation command.

FIG. 20 is a flowchart showing yet another operation example of the speculative information collecting device at the end of speculative command execution.

FIG. 21 is a block diagram illustrating an example of a sampling mechanism that collects various states of a processor by hardware.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 20 ... MPU calculation execution part 21 ... speculation information collection device 22 ... speculation instruction bus 23 ... additional information bus 24 ... result access bus 25 ... processor 26 ... comparison result line 27 ... data collection means 28 ... optimization means 30 ... association table 31 ... Extraction unit associative memory 32. Cyclic unit associative memory 33. Associative key unit 34. Speculation probability data unit 35. Order / LRU information unit 36. Additional information unit 38. Number of appearances 39. Failure count 40. Failure rate 41. 42 ... Speculation instruction address line 43 ... Speculation probability data update circuit 44 ... Extractor shift limit register 45 ... Replacement candidate determination circuit 46 ... Additional information update circuit 47 ... Result access line 48 ... Result access control circuit 49 ... Speculation instruction processing circuit 50 … Association key update instruction line

Claims (15)

(57) [Claims] 1. An apparatus for collecting statistical data of events generated in a processor, comprising: an extracting unit memory for storing statistical data of a fixed number of events having a large influence on performance degradation of a processor among the statistical data of the events; Receiving data relating to an event that occurred during actual operation from the processor, so that among the statistical data of the events calculated up to now, statistical data of a fixed number of events having a large influence on the performance degradation of the processor remains in the extraction unit memory. And control means for updating statistical data of events and replacing statistical data of events. 2. An apparatus for collecting statistical data of events generated in a processor, wherein the statistical data of a fixed number of events having a high influence on performance degradation of the processor and satisfying a standard of statistical reliability is stored. An external memory, a cyclic memory for temporarily storing statistical data of events whose statistical reliability does not satisfy the criterion or does not fall in the upper fixed number, and a processor for transmitting data relating to an event occurring during actual operation. Updating of the statistical data of the event, and updating the statistical data of the event so that statistical data of a certain number of upper events having a large effect on performance degradation of the processor among the statistical data of the events received and calculated so far remain in the extraction unit memory. The statistical data of the event is exchanged between the external memory and the extractor memory, and the statistical data of the event of the extractor memory is exchanged. A processor performance data collection device, comprising: a control unit. 3. When the statistical data of the event received from the processor is not stored in any of the extraction unit memory and the traveling unit memory, the control unit secures an empty entry in the traveling unit memory. The statistical data of the event is registered, and when stored in the traveling unit memory, the stored statistical data of the event is updated and the traveling unit memory and the extraction unit memory are updated as necessary. 3. The processor performance data collection device according to claim 2, wherein the statistical data of the event is replaced, and when the statistical data of the event is stored in the extraction unit memory, the statistical data of the stored event is updated. 4. An apparatus for collecting statistical data of an event occurring in a processor, wherein the statistical data of a fixed number of upper events having a large effect on performance degradation of the processor and satisfying a standard of statistical reliability is stored. Memory for temporarily storing statistical data of events whose statistical reliability does not satisfy the criterion or does not fall into the upper fixed number; and for narrowing down events to be registered in the memory for traveling. A region for each cache line of an instruction cache in the processor, which holds simplified statistical data relating to an event that is not registered in any of the extraction unit memory and the circulating unit memory; Received from the processor and affects the performance degradation of the processor among the statistical data of the events calculated so far. Updating the statistical data of the events, replacing the statistical data of the events between the circulating unit memory and the extracting unit memory, and the extracting unit A processor performance data collection device, comprising: control means for replacing statistical data of events in a memory and updating the simplified statistical data. 5. When the statistical data of an event received from the processor is not stored in any of the extraction unit memory and the circulating unit memory, the control unit may execute a cache line holding an instruction related to the event. When the simplified statistical data is updated and the updated simplified statistical data satisfies a certain standard, an empty entry is secured in the traveling unit memory and the statistical data of the event is registered and stored in the traveling unit memory. When the stored statistical data of the event is updated, the statistical data of the event is exchanged between the traveling unit memory and the extracting unit memory as necessary, and is stored in the extracting unit memory. 5. The processor performance data collection device according to claim 4, wherein said stored statistical data of the event is updated. 6. The processor performance data collection device according to claim 2, wherein the extraction unit memory and the circulating unit memory are configured by an associative memory that can be searched by event type. . 7. An apparatus for collecting statistical data of an event occurring in a processor, wherein the statistical data of a fixed number of upper events having a large effect on the performance degradation of the processor and satisfying a standard of statistical reliability is stored. And an area for each cache line of an instruction cache in the processor, which holds simplified statistical data on events not registered in the extraction unit memory in order to narrow down events registered in the extraction unit memory. Receiving data on events that occurred during operation from the processor, and among the statistical data of events calculated up to now, statistical data of a fixed number of events with a large effect on the performance degradation of the processor remains in the extraction unit memory. Updating the statistical data of the event, replacing the statistical data of the event in the memory of the extraction unit, and And a control unit for updating the simple statistical data. 8. When the statistical data of an event received from the processor is not stored in the extraction unit memory, the control means updates and updates simplified statistical data of a cache line holding an instruction related to the event. When the subsequent simple statistical data satisfies a certain standard, an empty entry is secured in the extracting unit memory, and the statistical data of the event is registered. When the event statistical data is stored in the extracting unit memory, the event is stored. The processor performance data collection device according to claim 7, wherein statistical data of an event is updated. 9. The processor performance data collection device according to claim 7, wherein the extraction unit memory is configured by an associative memory that can be searched by event type. 10. The processor performance data collection device according to claim 6, wherein the statistical data of the events in the extraction unit memory are arranged in descending order of the influence on the performance degradation of the processor. 11. The processor performance data collection device according to claim 10, wherein the statistical data of the event includes the number of occurrences of the event, the number of failures of the event, and the failure rate. 12. The processor performance data collection device according to claim 11, wherein the statistical data of the event further includes additional information indicating a cost required to rewind the failed event. 13. The processor performance data collection device according to claim 11, wherein the processor is a speculatively executable processor, and the event is a speculative event. 14. A method according to claim 1, wherein the processor performance data collecting apparatus is adapted to re-optimize when recompiling a program based on statistical data of events collected during actual operation of the program. An optimization method using a characteristic processor performance data collection device. 15. The optimization method using a processor performance data collection device according to claim 14, wherein the execution speculation is optimized based on the speculative execution statistical data collected from the speculative execution processor.