Wilhelm points out that the interference between these mechanisms makes for nonintuitive results, in which the best case for one part of the system may lead to longer total execution time. Timing accident can come from many different mechanisms at any stage in program execution. Wilhelm used the term timing accident to describe the cause for an increase in the instruction time in a program, and timing penalty to describe the amount of increase. Parallel memory systems can add further variation, as can DRAM refreshing, page modes, and other details of the types of memory components used. Caches can introduce an order of magnitude, or more variation in memory accesses, depending on whether the access is a hit or a miss. The memory system is an even larger source of variation. Two instructions that compete for the same resource will execute more slowly when executed together than if they were executed at widely separated times. The execution time of an instruction depends in part on the behavior of other instructions in the pipeline. The pipeline is one important source of variation. Today’s processors do not admit this simple approach because the execution time of a processor depends on the processor state in various ways.
#Count run time r code
The execution time for a code fragment could be accurately determined by looking up various instructions’ execution times. The manufacturer provided a table that gave the execution time of the various opcodes. Although it had a large instruction set, it had only a simple pipeline and no cache.
The performance model Park and Shaw developed for the 68000, by today’s standard, was relatively simple. Even the early computers were designed to take varying amounts of time to execute different instructions the PDP-8, for example, exhibited large variations between the fastest and slowest instruction. However, that ideal world has never existed. The simplest case would be if all instructions took the same amount of time to execute we could then simply count instructions and multiply by the execution rate. Given a sequence of instructions and a CPU, we want to determine the WCET of that sequence on the processor.
We can handle this by finding candidate long paths with abstract timing models and then refining the analysis using detailed timing models on a smaller set of paths. If the execution time of an instruction depends on the previous instructions, as is the case for both caches and pipelines, then we cannot easily find long paths without a detailed analysis of the timing of path segments. Path analysis and path timing interact to some extent for complex machines. Research over the past 30 years has improved both the path identification process and the processor performance models. Unfortunately, modern high-performance microprocessors are much more complex, and the timing of instruction sequences is much more difficult. Park and Shaw developed a performance model of a 68000 that gave them good results. The initial step in this methodology was to efficiently identify the worst-case execution path through the program. Measure the execution time along the worst-case path. This problem is sometimes called path analysis. 1.Īnalyze the program to find the worst-case path through a program. They broke WCET analysis into two phases. The basic approach to worst-case execution time analysis still followed today was suggested by Shaw and extended by Park and Shaw.
0 kommentar(er)
