Estimating the upper bound of the time of execution of a program is of the utmost importance to hard real-time system designers. When a hard real-time system takes more time than a pre-specified value, it leads to system failure. The dissertation focuses on designing a method, which makes the computation of the worst-case execution time (WCET) of a program a tighter one.; The estimating algorithm utilizes a path generating approach to factor into the calculation the effects of processor pipelining. This method enhances the acquisition of tighter estimates. Because the method takes into account the effect of simultaneous execution of two instructions, one of which is at the end of one block and the other at beginning of the block adjacent to it, this being done for every pair of adjacent blocks along a path, it enhances the accuracy of WCET computed. The algorithm tries to identify the mutual exclusions in the program. The algorithm will target assembly language code of a program to account for hardware features of a super-scalar processor.; Also, we introduce a heuristic algorithm that constructs the feasible paths only. It automatically determines the feasibility of paths during the process of constructing them, thus constructing only the feasible paths and eliminating the need to identify all (feasible and infeasible) paths.; We have also developed a new heuristic algorithm that uses the knapsack algorithm to estimate the WCET of hard real-time code. The algorithm is particularly useful for very large programs. The algorithm selects a few numbers of paths to estimate. It guarantees that the generated path has the maximum WCET, without the need to generate all the paths.
展开▼
