Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Timing
Reexamination Certificate
2000-03-21
2004-02-10
Thomson, W. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Timing
C703S017000, C703S021000, C713S300000
Reexamination Certificate
active
06691080
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a task execution time estimating method.
As a generally known method of estimating a time required for a CPU (Central Processing Unit) to execute a task, the operation of the CPU is simulated to sum up the execution times of all instructions. This method can advantageously estimate an increase in execution time caused by a pipeline stall or cache miss even for a CPU which performs pipeline control and has a cache memory. However, an increase in execution time by, e.g., an increase in the number of cache misses by an interrupt process cannot be estimated only by simulation of an instruction string. This generates an error in estimating the execution time.
In the conventional execution time estimating method, the estimating precision of the task execution time decreases when an interrupt occurs.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a task execution time estimating method capable of estimating the task execution time at high precision in consideration of an interrupt process.
A task execution time estimating method according to the present invention comprises the steps of: inputting a program, an initial data value, an execution start address, and an execution end address to an instruction level simulation portion, and outputting a first execution trace of an instruction including a pipeline stall caused by a factor including a combination of a branch and an instruction; inputting the first execution trace to a cache simulation portion, simulating a pipeline stall caused by a cache miss in correspondence with a cache scheme and a cache size, and outputting a second execution trace; inputting the second execution trace to an execution clock count portion, obtaining the number of execution clocks per instruction in accordance with the pipeline stall caused by a combination of a branch and an instruction and the pipeline stall caused by a cache miss, and outputting the number of execution clocks as a third execution trace; inputting the third execution trace to a simulator which simulates instruction execution of a central processing unit (to be referred to as a CPU hereinafter) having a cache memory and a pipeline controller, and estimating and outputting a first cache hit ratio and a first execution time of an entire program which does not consider any interrupt; inputting the output first execution trace, the first cache hit ratio, the first execution time, an interrupt generation ratio at which an interrupt occurs during task execution, and a cache memory rewrite ratio to a section hit ratio simulation portion, simulating, by a predetermined number of instructions for all interrupts, the cache rewritten in accordance with a cache memory rewrite pattern for all instructions and all interrupts included in the first execution trace, and calculating and outputting an average cache hit ratio; calculating a weighted average between the first cache hit ratio and the average cache hit ratio for each interrupt, and outputting a fourth execution trace including a cache hit ratio considering an interrupt; inputting the fourth execution trace to the execution clock count portion, counting the number of execution clocks for each instruction in accordance with the cache hit ratio and the pipeline stall caused by a combination of a branch and an instruction for each instruction, and outputting the number of execution clocks as a fifth execution trace; inputting the fifth execution trace, and estimating a cache hit ratio and an execution time of an entire program; and combining instruction execution simulators considering an interrupt, thereby estimating an average cache hit ratio and an execution time considering an interrupt.
A task execution time estimating method according to the present invention is a method of extracting specific instructions by sampling and estimating an execution time, comprising the steps of: inputting a program, an initial data value, an execution start address, and an execution end address to an instruction level simulation portion, and outputting a first execution trace of an instruction including a pipeline stall caused by a factor including a combination of a branch and an instruction; inputting the first execution trace to a cache simulation portion, simulating a pipeline stall caused by a cache miss in correspondence with a cache scheme and a cache size, and outputting a second execution trace; inputting the second execution trace to an execution clock count portion, obtaining the number of execution clocks per instruction in accordance with the pipeline stall caused by a combination of a branch and an instruction and the pipeline stall caused by a cache miss, and outputting the number of execution clocks as a third execution trace; inputting the third execution trace to a simulator which simulates instruction execution of a CPU having a cache memory and a pipeline controller, and estimating and outputting a first cache hit ratio and a first execution time of an entire program which does not consider any interrupt; inputting the output first execution trace, the first cache hit ratio, the first execution time, an interrupt generation ratio at which an interrupt occurs during task execution, and a cache memory rewrite ratio to a section hit ratio simulation portion, simulating the cache rewritten in accordance with a cache memory rewrite pattern for only a number of instructions proportional to the interrupt generation ratio that are extracted by sampling from instructions included in the first execution trace, and calculating and outputting an average cache hit ratio; calculating a weighted average between the first cache hit ratio and the average cache hit ratio for each interrupt, and outputting a fourth execution trace including a cache hit ratio considering an interrupt; inputting the fourth execution trace to the execution clock count portion, counting the number of execution clocks for each instruction in accordance with the cache hit ratio and the pipeline stall caused by a combination of a branch and an instruction for each instruction, and outputting the number of execution clocks as a fifth execution trace; inputting the fifth execution trace, and estimating a cache hit ratio and an execution time of an entire program; and combining instruction execution simulators considering an interrupt, thereby estimating an average cache hit ratio and an execution time considering an interrupt.
When the task execution time estimating method is practiced for a plurality of CPUs in which at least either cache schemes or cache sizes are different, the step of outputting the second execution trace using the cache simulation portion comprises performing a process for the cache scheme and the cache size of each CPU and obtaining the second execution trace for each CPU, and the step of calculating and outputting the average cache hit ratio using the section hit ratio simulation portion comprises performing a process for the cache scheme, the cache size, and an interrupt generation probability of each CPU, calculating the average cache hit ratio for each CPU, estimating the average cache hit ratio and the execution time considering an interrupt for each CPU, and selecting an optimal CPU in accordance with an application purpose.
Alternatively, when the task execution time estimating method is practiced for a plurality of CPUs having different numbers of pipelines, the step of outputting the third execution trace and the step of outputting the fifth execution trace comprise obtaining the third execution trace and the fifth execution trace using a stall penalty of each CPU, estimating the average cache hit ratio and the execution time considering an interrupt for each CPU, and selecting an optimal CPU in accordance with an application purpose.
Further, when the task execution time estimating method is practiced for a plurality of CPUs having different instruction sets, the step of outputting the first execution trace comprises obtaining the first execution trace using a pro
Day Herng-der
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kabushiki Kaisha Toshiba
Thomson W.
LandOfFree
Task execution time estimating method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Task execution time estimating method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Task execution time estimating method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300063